1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * CDDL HEADER START 4 * 5 * This file and its contents are supplied under the terms of the 6 * Common Development and Distribution License ("CDDL"), version 1.0. 7 * You may only use this file in accordance with the terms of version 8 * 1.0 of the CDDL. 9 * 10 * A full copy of the text of the CDDL should have accompanied this 11 * source. A copy of the CDDL is also available via the Internet at 12 * http://www.illumos.org/license/CDDL. 13 * 14 * CDDL HEADER END 15 */ 16 /* 17 * Copyright (c) 2017, 2018 by Delphix. All rights reserved. 18 */ 19 20 #include <sys/zfs_context.h> 21 #include <sys/aggsum.h> 22 23 /* 24 * Aggregate-sum counters are a form of fanned-out counter, used when atomic 25 * instructions on a single field cause enough CPU cache line contention to 26 * slow system performance. Due to their increased overhead and the expense 27 * involved with precisely reading from them, they should only be used in cases 28 * where the write rate (increment/decrement) is much higher than the read rate 29 * (get value). 30 * 31 * Aggregate sum counters are comprised of two basic parts, the core and the 32 * buckets. The core counter contains a lock for the entire counter, as well 33 * as the current upper and lower bounds on the value of the counter. The 34 * aggsum_bucket structure contains a per-bucket lock to protect the contents of 35 * the bucket, the current amount that this bucket has changed from the global 36 * counter (called the delta), and the amount of increment and decrement we have 37 * "borrowed" from the core counter. 38 * 39 * The basic operation of an aggsum is simple. Threads that wish to modify the 40 * counter will modify one bucket's counter (determined by their current CPU, to 41 * help minimize lock and cache contention). If the bucket already has 42 * sufficient capacity borrowed from the core structure to handle their request, 43 * they simply modify the delta and return. If the bucket does not, we clear 44 * the bucket's current state (to prevent the borrowed amounts from getting too 45 * large), and borrow more from the core counter. Borrowing is done by adding to 46 * the upper bound (or subtracting from the lower bound) of the core counter, 47 * and setting the borrow value for the bucket to the amount added (or 48 * subtracted). Clearing the bucket is the opposite; we add the current delta 49 * to both the lower and upper bounds of the core counter, subtract the borrowed 50 * incremental from the upper bound, and add the borrowed decrement from the 51 * lower bound. Note that only borrowing and clearing require access to the 52 * core counter; since all other operations access CPU-local resources, 53 * performance can be much higher than a traditional counter. 54 * 55 * Threads that wish to read from the counter have a slightly more challenging 56 * task. It is fast to determine the upper and lower bounds of the aggum; this 57 * does not require grabbing any locks. This suffices for cases where an 58 * approximation of the aggsum's value is acceptable. However, if one needs to 59 * know whether some specific value is above or below the current value in the 60 * aggsum, they invoke aggsum_compare(). This function operates by repeatedly 61 * comparing the target value to the upper and lower bounds of the aggsum, and 62 * then clearing a bucket. This proceeds until the target is outside of the 63 * upper and lower bounds and we return a response, or the last bucket has been 64 * cleared and we know that the target is equal to the aggsum's value. Finally, 65 * the most expensive operation is determining the precise value of the aggsum. 66 * To do this, we clear every bucket and then return the upper bound (which must 67 * be equal to the lower bound). What makes aggsum_compare() and aggsum_value() 68 * expensive is clearing buckets. This involves grabbing the global lock 69 * (serializing against themselves and borrow operations), grabbing a bucket's 70 * lock (preventing threads on those CPUs from modifying their delta), and 71 * zeroing out the borrowed value (forcing that thread to borrow on its next 72 * request, which will also be expensive). This is what makes aggsums well 73 * suited for write-many read-rarely operations. 74 * 75 * Note that the aggsums do not expand if more CPUs are hot-added. In that 76 * case, we will have less fanout than boot_ncpus, but we don't want to always 77 * reserve the RAM necessary to create the extra slots for additional CPUs up 78 * front, and dynamically adding them is a complex task. 79 */ 80 81 /* 82 * We will borrow 2^aggsum_borrow_shift times the current request, so we will 83 * have to get the as_lock approximately every 2^aggsum_borrow_shift calls to 84 * aggsum_add(). 85 */ 86 static uint_t aggsum_borrow_shift = 4; 87 88 void 89 aggsum_init(aggsum_t *as, uint64_t value) 90 { 91 memset(as, 0, sizeof (*as)); 92 as->as_lower_bound = as->as_upper_bound = value; 93 mutex_init(&as->as_lock, NULL, MUTEX_DEFAULT, NULL); 94 /* 95 * Too many buckets may hurt read performance without improving 96 * write. From 12 CPUs use bucket per 2 CPUs, from 48 per 4, etc. 97 */ 98 as->as_bucketshift = highbit64(boot_ncpus / 6) / 2; 99 as->as_numbuckets = ((boot_ncpus - 1) >> as->as_bucketshift) + 1; 100 as->as_buckets = kmem_zalloc(as->as_numbuckets * 101 sizeof (aggsum_bucket_t), KM_SLEEP); 102 for (int i = 0; i < as->as_numbuckets; i++) { 103 mutex_init(&as->as_buckets[i].asc_lock, 104 NULL, MUTEX_DEFAULT, NULL); 105 } 106 } 107 108 void 109 aggsum_fini(aggsum_t *as) 110 { 111 for (int i = 0; i < as->as_numbuckets; i++) 112 mutex_destroy(&as->as_buckets[i].asc_lock); 113 kmem_free(as->as_buckets, as->as_numbuckets * sizeof (aggsum_bucket_t)); 114 mutex_destroy(&as->as_lock); 115 } 116 117 int64_t 118 aggsum_lower_bound(aggsum_t *as) 119 { 120 return (atomic_load_64((volatile uint64_t *)&as->as_lower_bound)); 121 } 122 123 uint64_t 124 aggsum_upper_bound(aggsum_t *as) 125 { 126 return (atomic_load_64(&as->as_upper_bound)); 127 } 128 129 uint64_t 130 aggsum_value(aggsum_t *as) 131 { 132 int64_t lb; 133 uint64_t ub; 134 135 mutex_enter(&as->as_lock); 136 lb = as->as_lower_bound; 137 ub = as->as_upper_bound; 138 if (lb == ub) { 139 for (int i = 0; i < as->as_numbuckets; i++) { 140 ASSERT0(as->as_buckets[i].asc_delta); 141 ASSERT0(as->as_buckets[i].asc_borrowed); 142 } 143 mutex_exit(&as->as_lock); 144 return (lb); 145 } 146 for (int i = 0; i < as->as_numbuckets; i++) { 147 struct aggsum_bucket *asb = &as->as_buckets[i]; 148 if (asb->asc_borrowed == 0) 149 continue; 150 mutex_enter(&asb->asc_lock); 151 lb += asb->asc_delta + asb->asc_borrowed; 152 ub += asb->asc_delta - asb->asc_borrowed; 153 asb->asc_delta = 0; 154 asb->asc_borrowed = 0; 155 mutex_exit(&asb->asc_lock); 156 } 157 ASSERT3U(lb, ==, ub); 158 atomic_store_64((volatile uint64_t *)&as->as_lower_bound, lb); 159 atomic_store_64(&as->as_upper_bound, lb); 160 mutex_exit(&as->as_lock); 161 162 return (lb); 163 } 164 165 void 166 aggsum_add(aggsum_t *as, int64_t delta) 167 { 168 struct aggsum_bucket *asb; 169 int64_t borrow; 170 171 asb = &as->as_buckets[(CPU_SEQID_UNSTABLE >> as->as_bucketshift) % 172 as->as_numbuckets]; 173 174 /* Try fast path if we already borrowed enough before. */ 175 mutex_enter(&asb->asc_lock); 176 if (asb->asc_delta + delta <= (int64_t)asb->asc_borrowed && 177 asb->asc_delta + delta >= -(int64_t)asb->asc_borrowed) { 178 asb->asc_delta += delta; 179 mutex_exit(&asb->asc_lock); 180 return; 181 } 182 mutex_exit(&asb->asc_lock); 183 184 /* 185 * We haven't borrowed enough. Take the global lock and borrow 186 * considering what is requested now and what we borrowed before. 187 */ 188 borrow = (delta < 0 ? -delta : delta); 189 borrow <<= aggsum_borrow_shift + as->as_bucketshift; 190 mutex_enter(&as->as_lock); 191 if (borrow >= asb->asc_borrowed) 192 borrow -= asb->asc_borrowed; 193 else 194 borrow = (borrow - (int64_t)asb->asc_borrowed) / 4; 195 mutex_enter(&asb->asc_lock); 196 delta += asb->asc_delta; 197 asb->asc_delta = 0; 198 asb->asc_borrowed += borrow; 199 mutex_exit(&asb->asc_lock); 200 atomic_store_64((volatile uint64_t *)&as->as_lower_bound, 201 as->as_lower_bound + delta - borrow); 202 atomic_store_64(&as->as_upper_bound, 203 as->as_upper_bound + delta + borrow); 204 mutex_exit(&as->as_lock); 205 } 206 207 /* 208 * Compare the aggsum value to target efficiently. Returns -1 if the value 209 * represented by the aggsum is less than target, 1 if it's greater, and 0 if 210 * they are equal. 211 */ 212 int 213 aggsum_compare(aggsum_t *as, uint64_t target) 214 { 215 int64_t lb; 216 uint64_t ub; 217 int i; 218 219 if (atomic_load_64(&as->as_upper_bound) < target) 220 return (-1); 221 lb = atomic_load_64((volatile uint64_t *)&as->as_lower_bound); 222 if (lb > 0 && (uint64_t)lb > target) 223 return (1); 224 mutex_enter(&as->as_lock); 225 lb = as->as_lower_bound; 226 ub = as->as_upper_bound; 227 for (i = 0; i < as->as_numbuckets; i++) { 228 struct aggsum_bucket *asb = &as->as_buckets[i]; 229 if (asb->asc_borrowed == 0) 230 continue; 231 mutex_enter(&asb->asc_lock); 232 lb += asb->asc_delta + asb->asc_borrowed; 233 ub += asb->asc_delta - asb->asc_borrowed; 234 asb->asc_delta = 0; 235 asb->asc_borrowed = 0; 236 mutex_exit(&asb->asc_lock); 237 if (ub < target || (lb > 0 && (uint64_t)lb > target)) 238 break; 239 } 240 if (i >= as->as_numbuckets) 241 ASSERT3U(lb, ==, ub); 242 atomic_store_64((volatile uint64_t *)&as->as_lower_bound, lb); 243 atomic_store_64(&as->as_upper_bound, ub); 244 mutex_exit(&as->as_lock); 245 return (ub < target ? -1 : (uint64_t)lb > target ? 1 : 0); 246 } 247