4 * This file and its contents are supplied under the terms of the
5 * Common Development and Distribution License ("CDDL"), version 1.0.
6 * You may only use this file in accordance with the terms of version
9 * A full copy of the text of the CDDL should have accompanied this
10 * source. A copy of the CDDL is also available via the Internet at
11 * http://www.illumos.org/license/CDDL.
16 * Copyright (c) 2017 by Delphix. All rights reserved.
19 #include <sys/zfs_context.h>
20 #include <sys/aggsum.h>
23 * Aggregate-sum counters are a form of fanned-out counter, used when atomic
24 * instructions on a single field cause enough CPU cache line contention to
25 * slow system performance. Due to their increased overhead and the expense
26 * involved with precisely reading from them, they should only be used in cases
27 * where the write rate (increment/decrement) is much higher than the read rate
30 * Aggregate sum counters are comprised of two basic parts, the core and the
31 * buckets. The core counter contains a lock for the entire counter, as well
32 * as the current upper and lower bounds on the value of the counter. The
33 * aggsum_bucket structure contains a per-bucket lock to protect the contents of
34 * the bucket, the current amount that this bucket has changed from the global
35 * counter (called the delta), and the amount of increment and decrement we have
36 * "borrowed" from the core counter.
38 * The basic operation of an aggsum is simple. Threads that wish to modify the
39 * counter will modify one bucket's counter (determined by their current CPU, to
40 * help minimize lock and cache contention). If the bucket already has
41 * sufficient capacity borrowed from the core structure to handle their request,
42 * they simply modify the delta and return. If the bucket does not, we clear
43 * the bucket's current state (to prevent the borrowed amounts from getting too
44 * large), and borrow more from the core counter. Borrowing is done by adding to
45 * the upper bound (or subtracting from the lower bound) of the core counter,
46 * and setting the borrow value for the bucket to the amount added (or
47 * subtracted). Clearing the bucket is the opposite; we add the current delta
48 * to both the lower and upper bounds of the core counter, subtract the borrowed
49 * incremental from the upper bound, and add the borrowed decrement from the
50 * lower bound. Note that only borrowing and clearing require access to the
51 * core counter; since all other operations access CPU-local resources,
52 * performance can be much higher than a traditional counter.
54 * Threads that wish to read from the counter have a slightly more challenging
55 * task. It is fast to determine the upper and lower bounds of the aggum; this
56 * does not require grabbing any locks. This suffices for cases where an
57 * approximation of the aggsum's value is acceptable. However, if one needs to
58 * know whether some specific value is above or below the current value in the
59 * aggsum, they invoke aggsum_compare(). This function operates by repeatedly
60 * comparing the target value to the upper and lower bounds of the aggsum, and
61 * then clearing a bucket. This proceeds until the target is outside of the
62 * upper and lower bounds and we return a response, or the last bucket has been
63 * cleared and we know that the target is equal to the aggsum's value. Finally,
64 * the most expensive operation is determining the precise value of the aggsum.
65 * To do this, we clear every bucket and then return the upper bound (which must
66 * be equal to the lower bound). What makes aggsum_compare() and aggsum_value()
67 * expensive is clearing buckets. This involves grabbing the global lock
68 * (serializing against themselves and borrow operations), grabbing a bucket's
69 * lock (preventing threads on those CPUs from modifying their delta), and
70 * zeroing out the borrowed value (forcing that thread to borrow on its next
71 * request, which will also be expensive). This is what makes aggsums well
72 * suited for write-many read-rarely operations.
76 * We will borrow aggsum_borrow_multiplier times the current request, so we will
77 * have to get the as_lock approximately every aggsum_borrow_multiplier calls to
80 static uint_t aggsum_borrow_multiplier
= 10;
83 aggsum_init(aggsum_t
*as
, uint64_t value
)
85 bzero(as
, sizeof (*as
));
86 as
->as_lower_bound
= as
->as_upper_bound
= value
;
87 mutex_init(&as
->as_lock
, NULL
, MUTEX_DEFAULT
, NULL
);
88 as
->as_numbuckets
= boot_ncpus
;
89 as
->as_buckets
= kmem_zalloc(boot_ncpus
* sizeof (aggsum_bucket_t
),
91 for (int i
= 0; i
< as
->as_numbuckets
; i
++) {
92 mutex_init(&as
->as_buckets
[i
].asc_lock
,
93 NULL
, MUTEX_DEFAULT
, NULL
);
98 aggsum_fini(aggsum_t
*as
)
100 for (int i
= 0; i
< as
->as_numbuckets
; i
++)
101 mutex_destroy(&as
->as_buckets
[i
].asc_lock
);
102 mutex_destroy(&as
->as_lock
);
106 aggsum_lower_bound(aggsum_t
*as
)
108 return (as
->as_lower_bound
);
112 aggsum_upper_bound(aggsum_t
*as
)
114 return (as
->as_upper_bound
);
118 aggsum_flush_bucket(aggsum_t
*as
, struct aggsum_bucket
*asb
)
120 ASSERT(MUTEX_HELD(&as
->as_lock
));
121 ASSERT(MUTEX_HELD(&asb
->asc_lock
));
124 * We use atomic instructions for this because we read the upper and
125 * lower bounds without the lock, so we need stores to be atomic.
127 atomic_add_64((volatile uint64_t *)&as
->as_lower_bound
, asb
->asc_delta
);
128 atomic_add_64((volatile uint64_t *)&as
->as_upper_bound
, asb
->asc_delta
);
130 atomic_add_64((volatile uint64_t *)&as
->as_upper_bound
,
132 atomic_add_64((volatile uint64_t *)&as
->as_lower_bound
,
134 asb
->asc_borrowed
= 0;
138 aggsum_value(aggsum_t
*as
)
142 mutex_enter(&as
->as_lock
);
143 if (as
->as_lower_bound
== as
->as_upper_bound
) {
144 rv
= as
->as_lower_bound
;
145 for (int i
= 0; i
< as
->as_numbuckets
; i
++) {
146 ASSERT0(as
->as_buckets
[i
].asc_delta
);
147 ASSERT0(as
->as_buckets
[i
].asc_borrowed
);
149 mutex_exit(&as
->as_lock
);
152 for (int i
= 0; i
< as
->as_numbuckets
; i
++) {
153 struct aggsum_bucket
*asb
= &as
->as_buckets
[i
];
154 mutex_enter(&asb
->asc_lock
);
155 aggsum_flush_bucket(as
, asb
);
156 mutex_exit(&asb
->asc_lock
);
158 VERIFY3U(as
->as_lower_bound
, ==, as
->as_upper_bound
);
159 rv
= as
->as_lower_bound
;
160 mutex_exit(&as
->as_lock
);
166 aggsum_borrow(aggsum_t
*as
, int64_t delta
, struct aggsum_bucket
*asb
)
168 int64_t abs_delta
= (delta
< 0 ? -delta
: delta
);
169 mutex_enter(&as
->as_lock
);
170 mutex_enter(&asb
->asc_lock
);
172 aggsum_flush_bucket(as
, asb
);
174 atomic_add_64((volatile uint64_t *)&as
->as_upper_bound
, abs_delta
);
175 atomic_add_64((volatile uint64_t *)&as
->as_lower_bound
, -abs_delta
);
176 asb
->asc_borrowed
= abs_delta
;
178 mutex_exit(&asb
->asc_lock
);
179 mutex_exit(&as
->as_lock
);
183 aggsum_add(aggsum_t
*as
, int64_t delta
)
185 struct aggsum_bucket
*asb
=
186 &as
->as_buckets
[CPU_SEQID
% as
->as_numbuckets
];
189 mutex_enter(&asb
->asc_lock
);
190 if (asb
->asc_delta
+ delta
<= (int64_t)asb
->asc_borrowed
&&
191 asb
->asc_delta
+ delta
>= -(int64_t)asb
->asc_borrowed
) {
192 asb
->asc_delta
+= delta
;
193 mutex_exit(&asb
->asc_lock
);
196 mutex_exit(&asb
->asc_lock
);
197 aggsum_borrow(as
, delta
* aggsum_borrow_multiplier
, asb
);
202 * Compare the aggsum value to target efficiently. Returns -1 if the value
203 * represented by the aggsum is less than target, 1 if it's greater, and 0 if
207 aggsum_compare(aggsum_t
*as
, uint64_t target
)
209 if (as
->as_upper_bound
< target
)
211 if (as
->as_lower_bound
> target
)
213 mutex_enter(&as
->as_lock
);
214 for (int i
= 0; i
< as
->as_numbuckets
; i
++) {
215 struct aggsum_bucket
*asb
= &as
->as_buckets
[i
];
216 mutex_enter(&asb
->asc_lock
);
217 aggsum_flush_bucket(as
, asb
);
218 mutex_exit(&asb
->asc_lock
);
219 if (as
->as_upper_bound
< target
) {
220 mutex_exit(&as
->as_lock
);
223 if (as
->as_lower_bound
> target
) {
224 mutex_exit(&as
->as_lock
);
228 VERIFY3U(as
->as_lower_bound
, ==, as
->as_upper_bound
);
229 ASSERT3U(as
->as_lower_bound
, ==, target
);
230 mutex_exit(&as
->as_lock
);