diff options
Diffstat (limited to 'sys/contrib/openzfs/module/zfs/aggsum.c')
| -rw-r--r-- | sys/contrib/openzfs/module/zfs/aggsum.c | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/sys/contrib/openzfs/module/zfs/aggsum.c b/sys/contrib/openzfs/module/zfs/aggsum.c new file mode 100644 index 000000000000..488c6ef3b6fc --- /dev/null +++ b/sys/contrib/openzfs/module/zfs/aggsum.c @@ -0,0 +1,245 @@ +/* + * CDDL HEADER START + * + * This file and its contents are supplied under the terms of the + * Common Development and Distribution License ("CDDL"), version 1.0. + * You may only use this file in accordance with the terms of version + * 1.0 of the CDDL. + * + * A full copy of the text of the CDDL should have accompanied this + * source. A copy of the CDDL is also available via the Internet at + * http://www.illumos.org/license/CDDL. + * + * CDDL HEADER END + */ +/* + * Copyright (c) 2017, 2018 by Delphix. All rights reserved. + */ + +#include <sys/zfs_context.h> +#include <sys/aggsum.h> + +/* + * Aggregate-sum counters are a form of fanned-out counter, used when atomic + * instructions on a single field cause enough CPU cache line contention to + * slow system performance. Due to their increased overhead and the expense + * involved with precisely reading from them, they should only be used in cases + * where the write rate (increment/decrement) is much higher than the read rate + * (get value). + * + * Aggregate sum counters are comprised of two basic parts, the core and the + * buckets. The core counter contains a lock for the entire counter, as well + * as the current upper and lower bounds on the value of the counter. The + * aggsum_bucket structure contains a per-bucket lock to protect the contents of + * the bucket, the current amount that this bucket has changed from the global + * counter (called the delta), and the amount of increment and decrement we have + * "borrowed" from the core counter. + * + * The basic operation of an aggsum is simple. Threads that wish to modify the + * counter will modify one bucket's counter (determined by their current CPU, to + * help minimize lock and cache contention). If the bucket already has + * sufficient capacity borrowed from the core structure to handle their request, + * they simply modify the delta and return. If the bucket does not, we clear + * the bucket's current state (to prevent the borrowed amounts from getting too + * large), and borrow more from the core counter. Borrowing is done by adding to + * the upper bound (or subtracting from the lower bound) of the core counter, + * and setting the borrow value for the bucket to the amount added (or + * subtracted). Clearing the bucket is the opposite; we add the current delta + * to both the lower and upper bounds of the core counter, subtract the borrowed + * incremental from the upper bound, and add the borrowed decrement from the + * lower bound. Note that only borrowing and clearing require access to the + * core counter; since all other operations access CPU-local resources, + * performance can be much higher than a traditional counter. + * + * Threads that wish to read from the counter have a slightly more challenging + * task. It is fast to determine the upper and lower bounds of the aggum; this + * does not require grabbing any locks. This suffices for cases where an + * approximation of the aggsum's value is acceptable. However, if one needs to + * know whether some specific value is above or below the current value in the + * aggsum, they invoke aggsum_compare(). This function operates by repeatedly + * comparing the target value to the upper and lower bounds of the aggsum, and + * then clearing a bucket. This proceeds until the target is outside of the + * upper and lower bounds and we return a response, or the last bucket has been + * cleared and we know that the target is equal to the aggsum's value. Finally, + * the most expensive operation is determining the precise value of the aggsum. + * To do this, we clear every bucket and then return the upper bound (which must + * be equal to the lower bound). What makes aggsum_compare() and aggsum_value() + * expensive is clearing buckets. This involves grabbing the global lock + * (serializing against themselves and borrow operations), grabbing a bucket's + * lock (preventing threads on those CPUs from modifying their delta), and + * zeroing out the borrowed value (forcing that thread to borrow on its next + * request, which will also be expensive). This is what makes aggsums well + * suited for write-many read-rarely operations. + * + * Note that the aggsums do not expand if more CPUs are hot-added. In that + * case, we will have less fanout than boot_ncpus, but we don't want to always + * reserve the RAM necessary to create the extra slots for additional CPUs up + * front, and dynamically adding them is a complex task. + */ + +/* + * We will borrow 2^aggsum_borrow_shift times the current request, so we will + * have to get the as_lock approximately every 2^aggsum_borrow_shift calls to + * aggsum_add(). + */ +static uint_t aggsum_borrow_shift = 4; + +void +aggsum_init(aggsum_t *as, uint64_t value) +{ + memset(as, 0, sizeof (*as)); + as->as_lower_bound = as->as_upper_bound = value; + mutex_init(&as->as_lock, NULL, MUTEX_DEFAULT, NULL); + /* + * Too many buckets may hurt read performance without improving + * write. From 12 CPUs use bucket per 2 CPUs, from 48 per 4, etc. + */ + as->as_bucketshift = highbit64(boot_ncpus / 6) / 2; + as->as_numbuckets = ((boot_ncpus - 1) >> as->as_bucketshift) + 1; + as->as_buckets = kmem_zalloc(as->as_numbuckets * + sizeof (aggsum_bucket_t), KM_SLEEP); + for (int i = 0; i < as->as_numbuckets; i++) { + mutex_init(&as->as_buckets[i].asc_lock, + NULL, MUTEX_DEFAULT, NULL); + } +} + +void +aggsum_fini(aggsum_t *as) +{ + for (int i = 0; i < as->as_numbuckets; i++) + mutex_destroy(&as->as_buckets[i].asc_lock); + kmem_free(as->as_buckets, as->as_numbuckets * sizeof (aggsum_bucket_t)); + mutex_destroy(&as->as_lock); +} + +int64_t +aggsum_lower_bound(aggsum_t *as) +{ + return (atomic_load_64((volatile uint64_t *)&as->as_lower_bound)); +} + +uint64_t +aggsum_upper_bound(aggsum_t *as) +{ + return (atomic_load_64(&as->as_upper_bound)); +} + +uint64_t +aggsum_value(aggsum_t *as) +{ + int64_t lb; + uint64_t ub; + + mutex_enter(&as->as_lock); + lb = as->as_lower_bound; + ub = as->as_upper_bound; + if (lb == ub) { + for (int i = 0; i < as->as_numbuckets; i++) { + ASSERT0(as->as_buckets[i].asc_delta); + ASSERT0(as->as_buckets[i].asc_borrowed); + } + mutex_exit(&as->as_lock); + return (lb); + } + for (int i = 0; i < as->as_numbuckets; i++) { + struct aggsum_bucket *asb = &as->as_buckets[i]; + if (asb->asc_borrowed == 0) + continue; + mutex_enter(&asb->asc_lock); + lb += asb->asc_delta + asb->asc_borrowed; + ub += asb->asc_delta - asb->asc_borrowed; + asb->asc_delta = 0; + asb->asc_borrowed = 0; + mutex_exit(&asb->asc_lock); + } + ASSERT3U(lb, ==, ub); + atomic_store_64((volatile uint64_t *)&as->as_lower_bound, lb); + atomic_store_64(&as->as_upper_bound, lb); + mutex_exit(&as->as_lock); + + return (lb); +} + +void +aggsum_add(aggsum_t *as, int64_t delta) +{ + struct aggsum_bucket *asb; + int64_t borrow; + + asb = &as->as_buckets[(CPU_SEQID_UNSTABLE >> as->as_bucketshift) % + as->as_numbuckets]; + + /* Try fast path if we already borrowed enough before. */ + mutex_enter(&asb->asc_lock); + if (asb->asc_delta + delta <= (int64_t)asb->asc_borrowed && + asb->asc_delta + delta >= -(int64_t)asb->asc_borrowed) { + asb->asc_delta += delta; + mutex_exit(&asb->asc_lock); + return; + } + mutex_exit(&asb->asc_lock); + + /* + * We haven't borrowed enough. Take the global lock and borrow + * considering what is requested now and what we borrowed before. + */ + borrow = (delta < 0 ? -delta : delta); + borrow <<= aggsum_borrow_shift + as->as_bucketshift; + mutex_enter(&as->as_lock); + if (borrow >= asb->asc_borrowed) + borrow -= asb->asc_borrowed; + else + borrow = (borrow - (int64_t)asb->asc_borrowed) / 4; + mutex_enter(&asb->asc_lock); + delta += asb->asc_delta; + asb->asc_delta = 0; + asb->asc_borrowed += borrow; + mutex_exit(&asb->asc_lock); + atomic_store_64((volatile uint64_t *)&as->as_lower_bound, + as->as_lower_bound + delta - borrow); + atomic_store_64(&as->as_upper_bound, + as->as_upper_bound + delta + borrow); + mutex_exit(&as->as_lock); +} + +/* + * Compare the aggsum value to target efficiently. Returns -1 if the value + * represented by the aggsum is less than target, 1 if it's greater, and 0 if + * they are equal. + */ +int +aggsum_compare(aggsum_t *as, uint64_t target) +{ + int64_t lb; + uint64_t ub; + int i; + + if (atomic_load_64(&as->as_upper_bound) < target) + return (-1); + lb = atomic_load_64((volatile uint64_t *)&as->as_lower_bound); + if (lb > 0 && (uint64_t)lb > target) + return (1); + mutex_enter(&as->as_lock); + lb = as->as_lower_bound; + ub = as->as_upper_bound; + for (i = 0; i < as->as_numbuckets; i++) { + struct aggsum_bucket *asb = &as->as_buckets[i]; + if (asb->asc_borrowed == 0) + continue; + mutex_enter(&asb->asc_lock); + lb += asb->asc_delta + asb->asc_borrowed; + ub += asb->asc_delta - asb->asc_borrowed; + asb->asc_delta = 0; + asb->asc_borrowed = 0; + mutex_exit(&asb->asc_lock); + if (ub < target || (lb > 0 && (uint64_t)lb > target)) + break; + } + if (i >= as->as_numbuckets) + ASSERT3U(lb, ==, ub); + atomic_store_64((volatile uint64_t *)&as->as_lower_bound, lb); + atomic_store_64(&as->as_upper_bound, ub); + mutex_exit(&as->as_lock); + return (ub < target ? -1 : (uint64_t)lb > target ? 1 : 0); +} |