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
aggsum_init(aggsum_t * as,uint64_t value)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
aggsum_fini(aggsum_t * as)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
aggsum_lower_bound(aggsum_t * as)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
aggsum_upper_bound(aggsum_t * as)124 aggsum_upper_bound(aggsum_t *as)
125 {
126 return (atomic_load_64(&as->as_upper_bound));
127 }
128
129 uint64_t
aggsum_value(aggsum_t * as)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
aggsum_add(aggsum_t * as,int64_t delta)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
aggsum_compare(aggsum_t * as,uint64_t target)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