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