1331400Smav/* 2331400Smav * CDDL HEADER START 3331400Smav * 4331400Smav * This file and its contents are supplied under the terms of the 5331400Smav * Common Development and Distribution License ("CDDL"), version 1.0. 6331400Smav * You may only use this file in accordance with the terms of version 7331400Smav * 1.0 of the CDDL. 8331400Smav * 9331400Smav * A full copy of the text of the CDDL should have accompanied this 10331400Smav * source. A copy of the CDDL is also available via the Internet at 11331400Smav * http://www.illumos.org/license/CDDL. 12331400Smav * 13331400Smav * CDDL HEADER END 14331400Smav */ 15331400Smav/* 16331400Smav * Copyright (c) 2017 by Delphix. All rights reserved. 17331400Smav */ 18331400Smav 19331400Smav#include <sys/zfs_context.h> 20331400Smav#include <sys/aggsum.h> 21331400Smav 22331400Smav/* 23331400Smav * Aggregate-sum counters are a form of fanned-out counter, used when atomic 24331400Smav * instructions on a single field cause enough CPU cache line contention to 25331400Smav * slow system performance. Due to their increased overhead and the expense 26331400Smav * involved with precisely reading from them, they should only be used in cases 27331400Smav * where the write rate (increment/decrement) is much higher than the read rate 28331400Smav * (get value). 29331400Smav * 30331400Smav * Aggregate sum counters are comprised of two basic parts, the core and the 31331400Smav * buckets. The core counter contains a lock for the entire counter, as well 32331400Smav * as the current upper and lower bounds on the value of the counter. The 33331400Smav * aggsum_bucket structure contains a per-bucket lock to protect the contents of 34331400Smav * the bucket, the current amount that this bucket has changed from the global 35331400Smav * counter (called the delta), and the amount of increment and decrement we have 36331400Smav * "borrowed" from the core counter. 37331400Smav * 38331400Smav * The basic operation of an aggsum is simple. Threads that wish to modify the 39331400Smav * counter will modify one bucket's counter (determined by their current CPU, to 40331400Smav * help minimize lock and cache contention). If the bucket already has 41331400Smav * sufficient capacity borrowed from the core structure to handle their request, 42331400Smav * they simply modify the delta and return. If the bucket does not, we clear 43331400Smav * the bucket's current state (to prevent the borrowed amounts from getting too 44331400Smav * large), and borrow more from the core counter. Borrowing is done by adding to 45331400Smav * the upper bound (or subtracting from the lower bound) of the core counter, 46331400Smav * and setting the borrow value for the bucket to the amount added (or 47331400Smav * subtracted). Clearing the bucket is the opposite; we add the current delta 48331400Smav * to both the lower and upper bounds of the core counter, subtract the borrowed 49331400Smav * incremental from the upper bound, and add the borrowed decrement from the 50331400Smav * lower bound. Note that only borrowing and clearing require access to the 51331400Smav * core counter; since all other operations access CPU-local resources, 52331400Smav * performance can be much higher than a traditional counter. 53331400Smav * 54331400Smav * Threads that wish to read from the counter have a slightly more challenging 55331400Smav * task. It is fast to determine the upper and lower bounds of the aggum; this 56331400Smav * does not require grabbing any locks. This suffices for cases where an 57331400Smav * approximation of the aggsum's value is acceptable. However, if one needs to 58331400Smav * know whether some specific value is above or below the current value in the 59331400Smav * aggsum, they invoke aggsum_compare(). This function operates by repeatedly 60331400Smav * comparing the target value to the upper and lower bounds of the aggsum, and 61331400Smav * then clearing a bucket. This proceeds until the target is outside of the 62331400Smav * upper and lower bounds and we return a response, or the last bucket has been 63331400Smav * cleared and we know that the target is equal to the aggsum's value. Finally, 64331400Smav * the most expensive operation is determining the precise value of the aggsum. 65331400Smav * To do this, we clear every bucket and then return the upper bound (which must 66331400Smav * be equal to the lower bound). What makes aggsum_compare() and aggsum_value() 67331400Smav * expensive is clearing buckets. This involves grabbing the global lock 68331400Smav * (serializing against themselves and borrow operations), grabbing a bucket's 69331400Smav * lock (preventing threads on those CPUs from modifying their delta), and 70331400Smav * zeroing out the borrowed value (forcing that thread to borrow on its next 71331400Smav * request, which will also be expensive). This is what makes aggsums well 72331400Smav * suited for write-many read-rarely operations. 73331400Smav */ 74331400Smav 75331400Smav/* 76331400Smav * We will borrow aggsum_borrow_multiplier times the current request, so we will 77331400Smav * have to get the as_lock approximately every aggsum_borrow_multiplier calls to 78331400Smav * aggsum_delta(). 79331400Smav */ 80331400Smavstatic uint_t aggsum_borrow_multiplier = 10; 81331400Smav 82331400Smavvoid 83331400Smavaggsum_init(aggsum_t *as, uint64_t value) 84331400Smav{ 85331400Smav bzero(as, sizeof (*as)); 86331400Smav as->as_lower_bound = as->as_upper_bound = value; 87331400Smav mutex_init(&as->as_lock, NULL, MUTEX_DEFAULT, NULL); 88331400Smav as->as_numbuckets = boot_ncpus; 89331400Smav as->as_buckets = kmem_zalloc(boot_ncpus * sizeof (aggsum_bucket_t), 90331400Smav KM_SLEEP); 91331400Smav for (int i = 0; i < as->as_numbuckets; i++) { 92331400Smav mutex_init(&as->as_buckets[i].asc_lock, 93331400Smav NULL, MUTEX_DEFAULT, NULL); 94331400Smav } 95331400Smav} 96331400Smav 97331400Smavvoid 98331400Smavaggsum_fini(aggsum_t *as) 99331400Smav{ 100331400Smav for (int i = 0; i < as->as_numbuckets; i++) 101331400Smav mutex_destroy(&as->as_buckets[i].asc_lock); 102331400Smav mutex_destroy(&as->as_lock); 103331400Smav} 104331400Smav 105331400Smavint64_t 106331400Smavaggsum_lower_bound(aggsum_t *as) 107331400Smav{ 108331400Smav return (as->as_lower_bound); 109331400Smav} 110331400Smav 111331400Smavint64_t 112331400Smavaggsum_upper_bound(aggsum_t *as) 113331400Smav{ 114331400Smav return (as->as_upper_bound); 115331400Smav} 116331400Smav 117331400Smavstatic void 118331400Smavaggsum_flush_bucket(aggsum_t *as, struct aggsum_bucket *asb) 119331400Smav{ 120331400Smav ASSERT(MUTEX_HELD(&as->as_lock)); 121331400Smav ASSERT(MUTEX_HELD(&asb->asc_lock)); 122331400Smav 123331400Smav /* 124331400Smav * We use atomic instructions for this because we read the upper and 125331400Smav * lower bounds without the lock, so we need stores to be atomic. 126331400Smav */ 127331400Smav atomic_add_64((volatile uint64_t *)&as->as_lower_bound, asb->asc_delta); 128331400Smav atomic_add_64((volatile uint64_t *)&as->as_upper_bound, asb->asc_delta); 129331400Smav asb->asc_delta = 0; 130331400Smav atomic_add_64((volatile uint64_t *)&as->as_upper_bound, 131331400Smav -asb->asc_borrowed); 132331400Smav atomic_add_64((volatile uint64_t *)&as->as_lower_bound, 133331400Smav asb->asc_borrowed); 134331400Smav asb->asc_borrowed = 0; 135331400Smav} 136331400Smav 137331400Smavuint64_t 138331400Smavaggsum_value(aggsum_t *as) 139331400Smav{ 140331400Smav int64_t rv; 141331400Smav 142331400Smav mutex_enter(&as->as_lock); 143331400Smav if (as->as_lower_bound == as->as_upper_bound) { 144331400Smav rv = as->as_lower_bound; 145331400Smav for (int i = 0; i < as->as_numbuckets; i++) { 146331400Smav ASSERT0(as->as_buckets[i].asc_delta); 147331400Smav ASSERT0(as->as_buckets[i].asc_borrowed); 148331400Smav } 149331400Smav mutex_exit(&as->as_lock); 150331400Smav return (rv); 151331400Smav } 152331400Smav for (int i = 0; i < as->as_numbuckets; i++) { 153331400Smav struct aggsum_bucket *asb = &as->as_buckets[i]; 154331400Smav mutex_enter(&asb->asc_lock); 155331400Smav aggsum_flush_bucket(as, asb); 156331400Smav mutex_exit(&asb->asc_lock); 157331400Smav } 158331400Smav VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound); 159331400Smav rv = as->as_lower_bound; 160331400Smav mutex_exit(&as->as_lock); 161331400Smav 162331400Smav return (rv); 163331400Smav} 164331400Smav 165331400Smavstatic void 166331400Smavaggsum_borrow(aggsum_t *as, int64_t delta, struct aggsum_bucket *asb) 167331400Smav{ 168331400Smav int64_t abs_delta = (delta < 0 ? -delta : delta); 169331400Smav mutex_enter(&as->as_lock); 170331400Smav mutex_enter(&asb->asc_lock); 171331400Smav 172331400Smav aggsum_flush_bucket(as, asb); 173331400Smav 174331400Smav atomic_add_64((volatile uint64_t *)&as->as_upper_bound, abs_delta); 175331400Smav atomic_add_64((volatile uint64_t *)&as->as_lower_bound, -abs_delta); 176331400Smav asb->asc_borrowed = abs_delta; 177331400Smav 178331400Smav mutex_exit(&asb->asc_lock); 179331400Smav mutex_exit(&as->as_lock); 180331400Smav} 181331400Smav 182331400Smavvoid 183331400Smavaggsum_add(aggsum_t *as, int64_t delta) 184331400Smav{ 185331400Smav struct aggsum_bucket *asb = 186331400Smav &as->as_buckets[CPU_SEQID % as->as_numbuckets]; 187331400Smav 188331400Smav for (;;) { 189331400Smav mutex_enter(&asb->asc_lock); 190331400Smav if (asb->asc_delta + delta <= (int64_t)asb->asc_borrowed && 191331400Smav asb->asc_delta + delta >= -(int64_t)asb->asc_borrowed) { 192331400Smav asb->asc_delta += delta; 193331400Smav mutex_exit(&asb->asc_lock); 194331400Smav return; 195331400Smav } 196331400Smav mutex_exit(&asb->asc_lock); 197331400Smav aggsum_borrow(as, delta * aggsum_borrow_multiplier, asb); 198331400Smav } 199331400Smav} 200331400Smav 201331400Smav/* 202331400Smav * Compare the aggsum value to target efficiently. Returns -1 if the value 203331400Smav * represented by the aggsum is less than target, 1 if it's greater, and 0 if 204331400Smav * they are equal. 205331400Smav */ 206331400Smavint 207331400Smavaggsum_compare(aggsum_t *as, uint64_t target) 208331400Smav{ 209331400Smav if (as->as_upper_bound < target) 210331400Smav return (-1); 211331400Smav if (as->as_lower_bound > target) 212331400Smav return (1); 213331400Smav mutex_enter(&as->as_lock); 214331400Smav for (int i = 0; i < as->as_numbuckets; i++) { 215331400Smav struct aggsum_bucket *asb = &as->as_buckets[i]; 216331400Smav mutex_enter(&asb->asc_lock); 217331400Smav aggsum_flush_bucket(as, asb); 218331400Smav mutex_exit(&asb->asc_lock); 219331400Smav if (as->as_upper_bound < target) { 220331400Smav mutex_exit(&as->as_lock); 221331400Smav return (-1); 222331400Smav } 223331400Smav if (as->as_lower_bound > target) { 224331400Smav mutex_exit(&as->as_lock); 225331400Smav return (1); 226331400Smav } 227331400Smav } 228331400Smav VERIFY3U(as->as_lower_bound, ==, as->as_upper_bound); 229331400Smav ASSERT3U(as->as_lower_bound, ==, target); 230331400Smav mutex_exit(&as->as_lock); 231331400Smav return (0); 232331400Smav} 233