xref: /illumos-gate/usr/src/uts/common/fs/zfs/aggsum.c (revision 29bf2d68)
13a2d8a1bSPaul Dagnelie /*
23a2d8a1bSPaul Dagnelie  * CDDL HEADER START
33a2d8a1bSPaul Dagnelie  *
43a2d8a1bSPaul Dagnelie  * This file and its contents are supplied under the terms of the
53a2d8a1bSPaul Dagnelie  * Common Development and Distribution License ("CDDL"), version 1.0.
63a2d8a1bSPaul Dagnelie  * You may only use this file in accordance with the terms of version
73a2d8a1bSPaul Dagnelie  * 1.0 of the CDDL.
83a2d8a1bSPaul Dagnelie  *
93a2d8a1bSPaul Dagnelie  * A full copy of the text of the CDDL should have accompanied this
103a2d8a1bSPaul Dagnelie  * source.  A copy of the CDDL is also available via the Internet at
113a2d8a1bSPaul Dagnelie  * http://www.illumos.org/license/CDDL.
123a2d8a1bSPaul Dagnelie  *
133a2d8a1bSPaul Dagnelie  * CDDL HEADER END
143a2d8a1bSPaul Dagnelie  */
153a2d8a1bSPaul Dagnelie /*
16*29bf2d68SPaul Dagnelie  * Copyright (c) 2017, 2018 by Delphix. All rights reserved.
173a2d8a1bSPaul Dagnelie  */
183a2d8a1bSPaul Dagnelie 
193a2d8a1bSPaul Dagnelie #include <sys/zfs_context.h>
203a2d8a1bSPaul Dagnelie #include <sys/aggsum.h>
213a2d8a1bSPaul Dagnelie 
223a2d8a1bSPaul Dagnelie /*
233a2d8a1bSPaul Dagnelie  * Aggregate-sum counters are a form of fanned-out counter, used when atomic
243a2d8a1bSPaul Dagnelie  * instructions on a single field cause enough CPU cache line contention to
253a2d8a1bSPaul Dagnelie  * slow system performance. Due to their increased overhead and the expense
263a2d8a1bSPaul Dagnelie  * involved with precisely reading from them, they should only be used in cases
273a2d8a1bSPaul Dagnelie  * where the write rate (increment/decrement) is much higher than the read rate
283a2d8a1bSPaul Dagnelie  * (get value).
293a2d8a1bSPaul Dagnelie  *
303a2d8a1bSPaul Dagnelie  * Aggregate sum counters are comprised of two basic parts, the core and the
313a2d8a1bSPaul Dagnelie  * buckets. The core counter contains a lock for the entire counter, as well
323a2d8a1bSPaul Dagnelie  * as the current upper and lower bounds on the value of the counter. The
333a2d8a1bSPaul Dagnelie  * aggsum_bucket structure contains a per-bucket lock to protect the contents of
343a2d8a1bSPaul Dagnelie  * the bucket, the current amount that this bucket has changed from the global
353a2d8a1bSPaul Dagnelie  * counter (called the delta), and the amount of increment and decrement we have
363a2d8a1bSPaul Dagnelie  * "borrowed" from the core counter.
373a2d8a1bSPaul Dagnelie  *
383a2d8a1bSPaul Dagnelie  * The basic operation of an aggsum is simple. Threads that wish to modify the
393a2d8a1bSPaul Dagnelie  * counter will modify one bucket's counter (determined by their current CPU, to
403a2d8a1bSPaul Dagnelie  * help minimize lock and cache contention). If the bucket already has
413a2d8a1bSPaul Dagnelie  * sufficient capacity borrowed from the core structure to handle their request,
423a2d8a1bSPaul Dagnelie  * they simply modify the delta and return.  If the bucket does not, we clear
433a2d8a1bSPaul Dagnelie  * the bucket's current state (to prevent the borrowed amounts from getting too
443a2d8a1bSPaul Dagnelie  * large), and borrow more from the core counter. Borrowing is done by adding to
453a2d8a1bSPaul Dagnelie  * the upper bound (or subtracting from the lower bound) of the core counter,
463a2d8a1bSPaul Dagnelie  * and setting the borrow value for the bucket to the amount added (or
473a2d8a1bSPaul Dagnelie  * subtracted).  Clearing the bucket is the opposite; we add the current delta
483a2d8a1bSPaul Dagnelie  * to both the lower and upper bounds of the core counter, subtract the borrowed
493a2d8a1bSPaul Dagnelie  * incremental from the upper bound, and add the borrowed decrement from the
503a2d8a1bSPaul Dagnelie  * lower bound.  Note that only borrowing and clearing require access to the
513a2d8a1bSPaul Dagnelie  * core counter; since all other operations access CPU-local resources,
523a2d8a1bSPaul Dagnelie  * performance can be much higher than a traditional counter.
533a2d8a1bSPaul Dagnelie  *
543a2d8a1bSPaul Dagnelie  * Threads that wish to read from the counter have a slightly more challenging
553a2d8a1bSPaul Dagnelie  * task. It is fast to determine the upper and lower bounds of the aggum; this
563a2d8a1bSPaul Dagnelie  * does not require grabbing any locks. This suffices for cases where an
573a2d8a1bSPaul Dagnelie  * approximation of the aggsum's value is acceptable. However, if one needs to
583a2d8a1bSPaul Dagnelie  * know whether some specific value is above or below the current value in the
593a2d8a1bSPaul Dagnelie  * aggsum, they invoke aggsum_compare(). This function operates by repeatedly
603a2d8a1bSPaul Dagnelie  * comparing the target value to the upper and lower bounds of the aggsum, and
613a2d8a1bSPaul Dagnelie  * then clearing a bucket. This proceeds until the target is outside of the
623a2d8a1bSPaul Dagnelie  * upper and lower bounds and we return a response, or the last bucket has been
633a2d8a1bSPaul Dagnelie  * cleared and we know that the target is equal to the aggsum's value. Finally,
643a2d8a1bSPaul Dagnelie  * the most expensive operation is determining the precise value of the aggsum.
653a2d8a1bSPaul Dagnelie  * To do this, we clear every bucket and then return the upper bound (which must
663a2d8a1bSPaul Dagnelie  * be equal to the lower bound). What makes aggsum_compare() and aggsum_value()
673a2d8a1bSPaul Dagnelie  * expensive is clearing buckets. This involves grabbing the global lock
683a2d8a1bSPaul Dagnelie  * (serializing against themselves and borrow operations), grabbing a bucket's
693a2d8a1bSPaul Dagnelie  * lock (preventing threads on those CPUs from modifying their delta), and
703a2d8a1bSPaul Dagnelie  * zeroing out the borrowed value (forcing that thread to borrow on its next
713a2d8a1bSPaul Dagnelie  * request, which will also be expensive).  This is what makes aggsums well
723a2d8a1bSPaul Dagnelie  * suited for write-many read-rarely operations.
733a2d8a1bSPaul Dagnelie  */
743a2d8a1bSPaul Dagnelie 
753a2d8a1bSPaul Dagnelie /*
763a2d8a1bSPaul Dagnelie  * We will borrow aggsum_borrow_multiplier times the current request, so we will
773a2d8a1bSPaul Dagnelie  * have to get the as_lock approximately every aggsum_borrow_multiplier calls to
783a2d8a1bSPaul Dagnelie  * aggsum_delta().
793a2d8a1bSPaul Dagnelie  */
803a2d8a1bSPaul Dagnelie static uint_t aggsum_borrow_multiplier = 10;
813a2d8a1bSPaul Dagnelie 
823a2d8a1bSPaul Dagnelie void
aggsum_init(aggsum_t * as,uint64_t value)833a2d8a1bSPaul Dagnelie aggsum_init(aggsum_t *as, uint64_t value)
843a2d8a1bSPaul Dagnelie {
853a2d8a1bSPaul Dagnelie 	bzero(as, sizeof (*as));
863a2d8a1bSPaul Dagnelie 	as->as_lower_bound = as->as_upper_bound = value;
873a2d8a1bSPaul Dagnelie 	mutex_init(&as->as_lock, NULL, MUTEX_DEFAULT, NULL);
883a2d8a1bSPaul Dagnelie 	as->as_numbuckets = boot_ncpus;
893a2d8a1bSPaul Dagnelie 	as->as_buckets = kmem_zalloc(boot_ncpus * sizeof (aggsum_bucket_t),
903a2d8a1bSPaul Dagnelie 	    KM_SLEEP);
913a2d8a1bSPaul Dagnelie 	for (int i = 0; i < as->as_numbuckets; i++) {
923a2d8a1bSPaul Dagnelie 		mutex_init(&as->as_buckets[i].asc_lock,
933a2d8a1bSPaul Dagnelie 		    NULL, MUTEX_DEFAULT, NULL);
943a2d8a1bSPaul Dagnelie 	}
953a2d8a1bSPaul Dagnelie }
963a2d8a1bSPaul Dagnelie 
973a2d8a1bSPaul Dagnelie void
aggsum_fini(aggsum_t * as)983a2d8a1bSPaul Dagnelie aggsum_fini(aggsum_t *as)
993a2d8a1bSPaul Dagnelie {
1003a2d8a1bSPaul Dagnelie 	for (int i = 0; i < as->as_numbuckets; i++)
1013a2d8a1bSPaul Dagnelie 		mutex_destroy(&as->as_buckets[i].asc_lock);
102*29bf2d68SPaul Dagnelie 	kmem_free(as->as_buckets, as->as_numbuckets * sizeof (aggsum_bucket_t));
1033a2d8a1bSPaul Dagnelie 	mutex_destroy(&as->as_lock);
1043a2d8a1bSPaul Dagnelie }
1053a2d8a1bSPaul Dagnelie 
1063a2d8a1bSPaul Dagnelie int64_t
aggsum_lower_bound(aggsum_t * as)1073a2d8a1bSPaul Dagnelie aggsum_lower_bound(aggsum_t *as)
1083a2d8a1bSPaul Dagnelie {
1093a2d8a1bSPaul Dagnelie 	return (as->as_lower_bound);
1103a2d8a1bSPaul Dagnelie }
1113a2d8a1bSPaul Dagnelie 
1123a2d8a1bSPaul Dagnelie int64_t
aggsum_upper_bound(aggsum_t * as)1133a2d8a1bSPaul Dagnelie aggsum_upper_bound(aggsum_t *as)
1143a2d8a1bSPaul Dagnelie {
1153a2d8a1bSPaul Dagnelie 	return (as->as_upper_bound);
1163a2d8a1bSPaul Dagnelie }
1173a2d8a1bSPaul Dagnelie 
1183a2d8a1bSPaul Dagnelie static void
aggsum_flush_bucket(aggsum_t * as,struct aggsum_bucket * asb)1193a2d8a1bSPaul Dagnelie aggsum_flush_bucket(aggsum_t *as, struct aggsum_bucket *asb)
1203a2d8a1bSPaul Dagnelie {
1213a2d8a1bSPaul Dagnelie 	ASSERT(MUTEX_HELD(&as->as_lock));
1223a2d8a1bSPaul Dagnelie 	ASSERT(MUTEX_HELD(&asb->asc_lock));
1233a2d8a1bSPaul Dagnelie 
1243a2d8a1bSPaul Dagnelie 	/*
1253a2d8a1bSPaul Dagnelie 	 * We use atomic instructions for this because we read the upper and
1263a2d8a1bSPaul Dagnelie 	 * lower bounds without the lock, so we need stores to be atomic.
1273a2d8a1bSPaul Dagnelie 	 */
1283a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_lower_bound, asb->asc_delta);
1293a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_upper_bound, asb->asc_delta);
1303a2d8a1bSPaul Dagnelie 	asb->asc_delta = 0;
1313a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_upper_bound,
1323a2d8a1bSPaul Dagnelie 	    -asb->asc_borrowed);
1333a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_lower_bound,
1343a2d8a1bSPaul Dagnelie 	    asb->asc_borrowed);
1353a2d8a1bSPaul Dagnelie 	asb->asc_borrowed = 0;
1363a2d8a1bSPaul Dagnelie }
1373a2d8a1bSPaul Dagnelie 
1383a2d8a1bSPaul Dagnelie uint64_t
aggsum_value(aggsum_t * as)1393a2d8a1bSPaul Dagnelie aggsum_value(aggsum_t *as)
1403a2d8a1bSPaul Dagnelie {
1413a2d8a1bSPaul Dagnelie 	int64_t rv;
1423a2d8a1bSPaul Dagnelie 
1433a2d8a1bSPaul Dagnelie 	mutex_enter(&as->as_lock);
1443a2d8a1bSPaul Dagnelie 	if (as->as_lower_bound == as->as_upper_bound) {
1453a2d8a1bSPaul Dagnelie 		rv = as->as_lower_bound;
1463a2d8a1bSPaul Dagnelie 		for (int i = 0; i < as->as_numbuckets; i++) {
1473a2d8a1bSPaul Dagnelie 			ASSERT0(as->as_buckets[i].asc_delta);
1483a2d8a1bSPaul Dagnelie 			ASSERT0(as->as_buckets[i].asc_borrowed);
1493a2d8a1bSPaul Dagnelie 		}
1503a2d8a1bSPaul Dagnelie 		mutex_exit(&as->as_lock);
1513a2d8a1bSPaul Dagnelie 		return (rv);
1523a2d8a1bSPaul Dagnelie 	}
1533a2d8a1bSPaul Dagnelie 	for (int i = 0; i < as->as_numbuckets; i++) {
1543a2d8a1bSPaul Dagnelie 		struct aggsum_bucket *asb = &as->as_buckets[i];
1553a2d8a1bSPaul Dagnelie 		mutex_enter(&asb->asc_lock);
1563a2d8a1bSPaul Dagnelie 		aggsum_flush_bucket(as, asb);
1573a2d8a1bSPaul Dagnelie 		mutex_exit(&asb->asc_lock);
1583a2d8a1bSPaul Dagnelie 	}
1593a2d8a1bSPaul Dagnelie 	VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound);
1603a2d8a1bSPaul Dagnelie 	rv = as->as_lower_bound;
1613a2d8a1bSPaul Dagnelie 	mutex_exit(&as->as_lock);
1623a2d8a1bSPaul Dagnelie 
1633a2d8a1bSPaul Dagnelie 	return (rv);
1643a2d8a1bSPaul Dagnelie }
1653a2d8a1bSPaul Dagnelie 
1663a2d8a1bSPaul Dagnelie static void
aggsum_borrow(aggsum_t * as,int64_t delta,struct aggsum_bucket * asb)1673a2d8a1bSPaul Dagnelie aggsum_borrow(aggsum_t *as, int64_t delta, struct aggsum_bucket *asb)
1683a2d8a1bSPaul Dagnelie {
1693a2d8a1bSPaul Dagnelie 	int64_t abs_delta = (delta < 0 ? -delta : delta);
1703a2d8a1bSPaul Dagnelie 	mutex_enter(&as->as_lock);
1713a2d8a1bSPaul Dagnelie 	mutex_enter(&asb->asc_lock);
1723a2d8a1bSPaul Dagnelie 
1733a2d8a1bSPaul Dagnelie 	aggsum_flush_bucket(as, asb);
1743a2d8a1bSPaul Dagnelie 
1753a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_upper_bound, abs_delta);
1763a2d8a1bSPaul Dagnelie 	atomic_add_64((volatile uint64_t *)&as->as_lower_bound, -abs_delta);
1773a2d8a1bSPaul Dagnelie 	asb->asc_borrowed = abs_delta;
1783a2d8a1bSPaul Dagnelie 
1793a2d8a1bSPaul Dagnelie 	mutex_exit(&asb->asc_lock);
1803a2d8a1bSPaul Dagnelie 	mutex_exit(&as->as_lock);
1813a2d8a1bSPaul Dagnelie }
1823a2d8a1bSPaul Dagnelie 
1833a2d8a1bSPaul Dagnelie void
aggsum_add(aggsum_t * as,int64_t delta)1843a2d8a1bSPaul Dagnelie aggsum_add(aggsum_t *as, int64_t delta)
1853a2d8a1bSPaul Dagnelie {
1863a2d8a1bSPaul Dagnelie 	struct aggsum_bucket *asb =
1873a2d8a1bSPaul Dagnelie 	    &as->as_buckets[CPU_SEQID % as->as_numbuckets];
1883a2d8a1bSPaul Dagnelie 
1893a2d8a1bSPaul Dagnelie 	for (;;) {
1903a2d8a1bSPaul Dagnelie 		mutex_enter(&asb->asc_lock);
1913a2d8a1bSPaul Dagnelie 		if (asb->asc_delta + delta <= (int64_t)asb->asc_borrowed &&
1923a2d8a1bSPaul Dagnelie 		    asb->asc_delta + delta >= -(int64_t)asb->asc_borrowed) {
1933a2d8a1bSPaul Dagnelie 			asb->asc_delta += delta;
1943a2d8a1bSPaul Dagnelie 			mutex_exit(&asb->asc_lock);
1953a2d8a1bSPaul Dagnelie 			return;
1963a2d8a1bSPaul Dagnelie 		}
1973a2d8a1bSPaul Dagnelie 		mutex_exit(&asb->asc_lock);
1983a2d8a1bSPaul Dagnelie 		aggsum_borrow(as, delta * aggsum_borrow_multiplier, asb);
1993a2d8a1bSPaul Dagnelie 	}
2003a2d8a1bSPaul Dagnelie }
2013a2d8a1bSPaul Dagnelie 
2023a2d8a1bSPaul Dagnelie /*
2033a2d8a1bSPaul Dagnelie  * Compare the aggsum value to target efficiently. Returns -1 if the value
2043a2d8a1bSPaul Dagnelie  * represented by the aggsum is less than target, 1 if it's greater, and 0 if
2053a2d8a1bSPaul Dagnelie  * they are equal.
2063a2d8a1bSPaul Dagnelie  */
2073a2d8a1bSPaul Dagnelie int
aggsum_compare(aggsum_t * as,uint64_t target)2083a2d8a1bSPaul Dagnelie aggsum_compare(aggsum_t *as, uint64_t target)
2093a2d8a1bSPaul Dagnelie {
2103a2d8a1bSPaul Dagnelie 	if (as->as_upper_bound < target)
2113a2d8a1bSPaul Dagnelie 		return (-1);
2123a2d8a1bSPaul Dagnelie 	if (as->as_lower_bound > target)
2133a2d8a1bSPaul Dagnelie 		return (1);
2143a2d8a1bSPaul Dagnelie 	mutex_enter(&as->as_lock);
2153a2d8a1bSPaul Dagnelie 	for (int i = 0; i < as->as_numbuckets; i++) {
2163a2d8a1bSPaul Dagnelie 		struct aggsum_bucket *asb = &as->as_buckets[i];
2173a2d8a1bSPaul Dagnelie 		mutex_enter(&asb->asc_lock);
2183a2d8a1bSPaul Dagnelie 		aggsum_flush_bucket(as, asb);
2193a2d8a1bSPaul Dagnelie 		mutex_exit(&asb->asc_lock);
2203a2d8a1bSPaul Dagnelie 		if (as->as_upper_bound < target) {
2213a2d8a1bSPaul Dagnelie 			mutex_exit(&as->as_lock);
2223a2d8a1bSPaul Dagnelie 			return (-1);
2233a2d8a1bSPaul Dagnelie 		}
2243a2d8a1bSPaul Dagnelie 		if (as->as_lower_bound > target) {
2253a2d8a1bSPaul Dagnelie 			mutex_exit(&as->as_lock);
2263a2d8a1bSPaul Dagnelie 			return (1);
2273a2d8a1bSPaul Dagnelie 		}
2283a2d8a1bSPaul Dagnelie 	}
2293a2d8a1bSPaul Dagnelie 	VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound);
2303a2d8a1bSPaul Dagnelie 	ASSERT3U(as->as_lower_bound, ==, target);
2313a2d8a1bSPaul Dagnelie 	mutex_exit(&as->as_lock);
2323a2d8a1bSPaul Dagnelie 	return (0);
2333a2d8a1bSPaul Dagnelie }