2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2019,2020 Jeffrey Roberson <jeff@FreeBSD.org>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice unmodified, this list of conditions, and the following
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
31 #include <sys/param.h>
32 #include <sys/systm.h>
33 #include <sys/counter.h>
34 #include <sys/kernel.h>
35 #include <sys/limits.h>
39 #include <sys/sysctl.h>
44 * This is a novel safe memory reclamation technique inspired by
45 * epoch based reclamation from Samy Al Bahra's concurrency kit which
46 * in turn was based on work described in:
47 * Fraser, K. 2004. Practical Lock-Freedom. PhD Thesis, University
48 * of Cambridge Computing Laboratory.
49 * And shares some similarities with:
50 * Wang, Stamler, Parmer. 2016 Parallel Sections: Scaling System-Level
53 * This is not an implementation of hazard pointers or related
54 * techniques. The term safe memory reclamation is used as a
55 * generic descriptor for algorithms that defer frees to avoid
56 * use-after-free errors with lockless datastructures.
58 * The basic approach is to maintain a monotonic write sequence
59 * number that is updated on some application defined granularity.
60 * Readers record the most recent write sequence number they have
61 * observed. A shared read sequence number records the lowest
62 * sequence number observed by any reader as of the last poll. Any
63 * write older than this value has been observed by all readers
64 * and memory can be reclaimed. Like Epoch we also detect idle
65 * readers by storing an invalid sequence number in the per-cpu
66 * state when the read section exits. Like Parsec we establish
67 * a global write clock that is used to mark memory on free.
69 * The write and read sequence numbers can be thought of as a two
70 * handed clock with readers always advancing towards writers. SMR
71 * maintains the invariant that all readers can safely access memory
72 * that was visible at the time they loaded their copy of the sequence
73 * number. Periodically the read sequence or hand is polled and
74 * advanced as far towards the write sequence as active readers allow.
75 * Memory which was freed between the old and new global read sequence
76 * number can now be reclaimed. When the system is idle the two hands
77 * meet and no deferred memory is outstanding. Readers never advance
78 * any sequence number, they only observe them. The shared read
79 * sequence number is consequently never higher than the write sequence.
80 * A stored sequence number that falls outside of this range has expired
81 * and needs no scan to reclaim.
83 * A notable distinction between this SMR and Epoch, qsbr, rcu, etc. is
84 * that advancing the sequence number is decoupled from detecting its
85 * observation. This results in a more granular assignment of sequence
86 * numbers even as read latencies prohibit all or some expiration.
87 * It also allows writers to advance the sequence number and save the
88 * poll for expiration until a later time when it is likely to
89 * complete without waiting. The batch granularity and free-to-use
90 * latency is dynamic and can be significantly smaller than in more
93 * This mechanism is primarily intended to be used in coordination with
94 * UMA. By integrating with the allocator we avoid all of the callout
95 * queue machinery and are provided with an efficient way to batch
96 * sequence advancement and waiting. The allocator accumulates a full
97 * per-cpu cache of memory before advancing the sequence. It then
98 * delays waiting for this sequence to expire until the memory is
99 * selected for reuse. In this way we only increment the sequence
100 * value once for n=cache-size frees and the waits are done long
101 * after the sequence has been expired so they need only be verified
102 * to account for pathological conditions and to advance the read
103 * sequence. Tying the sequence number to the bucket size has the
104 * nice property that as the zone gets busier the buckets get larger
105 * and the sequence writes become fewer. If the coherency of advancing
106 * the write sequence number becomes too costly we can advance
107 * it for every N buckets in exchange for higher free-to-use
108 * latency and consequently higher memory consumption.
110 * If the read overhead of accessing the shared cacheline becomes
111 * especially burdensome an invariant TSC could be used in place of the
112 * sequence. The algorithm would then only need to maintain the minimum
113 * observed tsc. This would trade potential cache synchronization
114 * overhead for local serialization and cpu timestamp overhead.
118 * A simplified diagram:
121 * | -------------------- sequence number space -------------------- |
123 * | ----- valid sequence numbers ---- |
125 * | -- free -- | --------- deferred frees -------- | ---- free ---- |
128 * In this example cpuA has the lowest sequence number and poll can
129 * advance rd seq. cpuB is not running and is considered to observe
132 * Freed memory that is tagged with a sequence number between rd seq and
133 * wr seq can not be safely reclaimed because cpuA may hold a reference to
134 * it. Any other memory is guaranteed to be unreferenced.
136 * Any writer is free to advance wr seq at any time however it may busy
137 * poll in pathological cases.
140 static uma_zone_t smr_shared_zone;
141 static uma_zone_t smr_zone;
144 #define SMR_SEQ_INIT 1 /* All valid sequence numbers are odd. */
145 #define SMR_SEQ_INCR 2
148 * SMR_SEQ_MAX_DELTA is the maximum distance allowed between rd_seq and
149 * wr_seq. For the modular arithmetic to work a value of UNIT_MAX / 2
150 * would be possible but it is checked after we increment the wr_seq so
151 * a safety margin is left to prevent overflow.
153 * We will block until SMR_SEQ_MAX_ADVANCE sequence numbers have progressed
154 * to prevent integer wrapping. See smr_advance() for more details.
156 #define SMR_SEQ_MAX_DELTA (UINT_MAX / 4)
157 #define SMR_SEQ_MAX_ADVANCE (SMR_SEQ_MAX_DELTA - 1024)
159 /* We want to test the wrapping feature in invariants kernels. */
160 #define SMR_SEQ_INCR (UINT_MAX / 10000)
161 #define SMR_SEQ_INIT (UINT_MAX - 100000)
162 /* Force extra polls to test the integer overflow detection. */
163 #define SMR_SEQ_MAX_DELTA (SMR_SEQ_INCR * 32)
164 #define SMR_SEQ_MAX_ADVANCE SMR_SEQ_MAX_DELTA / 2
167 static SYSCTL_NODE(_debug, OID_AUTO, smr, CTLFLAG_RW, NULL, "SMR Stats");
168 static counter_u64_t advance = EARLY_COUNTER;
169 SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance, CTLFLAG_RD, &advance, "");
170 static counter_u64_t advance_wait = EARLY_COUNTER;
171 SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance_wait, CTLFLAG_RD, &advance_wait, "");
172 static counter_u64_t poll = EARLY_COUNTER;
173 SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll, CTLFLAG_RD, &poll, "");
174 static counter_u64_t poll_scan = EARLY_COUNTER;
175 SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll_scan, CTLFLAG_RD, &poll_scan, "");
179 * Advance the write sequence and return the new value for use as the
180 * wait goal. This guarantees that any changes made by the calling
181 * thread prior to this call will be visible to all threads after
182 * rd_seq meets or exceeds the return value.
184 * This function may busy loop if the readers are roughly 1 billion
185 * sequence numbers behind the writers.
188 smr_advance(smr_t smr)
191 smr_seq_t goal, s_rd_seq;
194 * It is illegal to enter while in an smr section.
196 KASSERT(curthread->td_critnest == 0,
197 ("smr_advance: Not allowed in a critical section."));
200 * Modifications not done in a smr section need to be visible
201 * before advancing the seq.
203 atomic_thread_fence_rel();
206 * Load the current read seq before incrementing the goal so
207 * we are guaranteed it is always < goal.
209 s = zpcpu_get(smr)->c_shared;
210 s_rd_seq = atomic_load_acq_int(&s->s_rd_seq);
213 * Increment the shared write sequence by 2. Since it is
214 * initialized to 1 this means the only valid values are
215 * odd and an observed value of 0 in a particular CPU means
216 * it is not currently in a read section.
218 goal = atomic_fetchadd_int(&s->s_wr_seq, SMR_SEQ_INCR) + SMR_SEQ_INCR;
219 counter_u64_add(advance, 1);
222 * Force a synchronization here if the goal is getting too
223 * far ahead of the read sequence number. This keeps the
224 * wrap detecting arithmetic working in pathological cases.
226 if (SMR_SEQ_DELTA(goal, s_rd_seq) >= SMR_SEQ_MAX_DELTA) {
227 counter_u64_add(advance_wait, 1);
228 smr_wait(smr, goal - SMR_SEQ_MAX_ADVANCE);
235 smr_advance_deferred(smr_t smr, int limit)
241 csmr = zpcpu_get(smr);
242 if (++csmr->c_deferred >= limit) {
243 goal = SMR_SEQ_INVALID;
244 csmr->c_deferred = 0;
246 goal = smr_shared_current(csmr->c_shared) + SMR_SEQ_INCR;
248 if (goal != SMR_SEQ_INVALID)
251 return (smr_advance(smr));
255 * Poll to determine whether all readers have observed the 'goal' write
258 * If wait is true this will spin until the goal is met.
260 * This routine will updated the minimum observed read sequence number in
261 * s_rd_seq if it does a scan. It may not do a scan if another call has
262 * advanced s_rd_seq beyond the callers goal already.
264 * Returns true if the goal is met and false if not.
267 smr_poll(smr_t smr, smr_seq_t goal, bool wait)
271 smr_seq_t s_wr_seq, s_rd_seq, rd_seq, c_seq;
276 * It is illegal to enter while in an smr section.
278 KASSERT(!wait || curthread->td_critnest == 0,
279 ("smr_poll: Blocking not allowed in a critical section."));
282 * Use a critical section so that we can avoid ABA races
283 * caused by long preemption sleeps.
287 s = zpcpu_get(smr)->c_shared;
288 counter_u64_add_protected(poll, 1);
291 * Acquire barrier loads s_wr_seq after s_rd_seq so that we can not
292 * observe an updated read sequence that is larger than write.
294 s_rd_seq = atomic_load_acq_int(&s->s_rd_seq);
297 * wr_seq must be loaded prior to any c_seq value so that a stale
298 * c_seq can only reference time after this wr_seq.
300 s_wr_seq = atomic_load_acq_int(&s->s_wr_seq);
303 * This may have come from a deferred advance. Consider one
304 * increment past the current wr_seq valid and make sure we
305 * have advanced far enough to succeed. We simply add to avoid
306 * an additional fence.
308 if (goal == s_wr_seq + SMR_SEQ_INCR) {
309 atomic_add_int(&s->s_wr_seq, SMR_SEQ_INCR);
314 * Detect whether the goal is valid and has already been observed.
316 * The goal must be in the range of s_wr_seq >= goal >= s_rd_seq for
317 * it to be valid. If it is not then the caller held on to it and
318 * the integer wrapped. If we wrapped back within range the caller
319 * will harmlessly scan.
321 * A valid goal must be greater than s_rd_seq or we have not verified
322 * that it has been observed and must fall through to polling.
324 if (SMR_SEQ_GEQ(s_rd_seq, goal) || SMR_SEQ_LT(s_wr_seq, goal))
328 * Loop until all cores have observed the goal sequence or have
329 * gone inactive. Keep track of the oldest sequence currently
332 counter_u64_add_protected(poll_scan, 1);
335 c = zpcpu_get_cpu(smr, i);
336 c_seq = SMR_SEQ_INVALID;
338 c_seq = atomic_load_int(&c->c_seq);
339 if (c_seq == SMR_SEQ_INVALID)
343 * There is a race described in smr.h:smr_enter that
344 * can lead to a stale seq value but not stale data
345 * access. If we find a value out of range here we
346 * pin it to the current min to prevent it from
347 * advancing until that stale section has expired.
349 * The race is created when a cpu loads the s_wr_seq
350 * value in a local register and then another thread
351 * advances s_wr_seq and calls smr_poll() which will
352 * oberve no value yet in c_seq and advance s_rd_seq
353 * up to s_wr_seq which is beyond the register
354 * cached value. This is only likely to happen on
355 * hypervisor or with a system management interrupt.
357 if (SMR_SEQ_LT(c_seq, s_rd_seq))
361 * If the sequence number meets the goal we are
362 * done with this cpu.
364 if (SMR_SEQ_GEQ(c_seq, goal))
368 * If we're not waiting we will still scan the rest
369 * of the cpus and update s_rd_seq before returning
380 * Limit the minimum observed rd_seq whether we met the goal
383 if (c_seq != SMR_SEQ_INVALID && SMR_SEQ_GT(rd_seq, c_seq))
388 * Advance the rd_seq as long as we observed the most recent one.
390 s_rd_seq = atomic_load_int(&s->s_rd_seq);
392 if (SMR_SEQ_LEQ(rd_seq, s_rd_seq))
394 } while (atomic_fcmpset_int(&s->s_rd_seq, &s_rd_seq, rd_seq) == 0);
400 * Serialize with smr_advance()/smr_exit(). The caller is now free
401 * to modify memory as expected.
403 atomic_thread_fence_acq();
409 smr_create(const char *name)
415 s = uma_zalloc(smr_shared_zone, M_WAITOK);
416 smr = uma_zalloc(smr_zone, M_WAITOK);
419 s->s_rd_seq = s->s_wr_seq = SMR_SEQ_INIT;
421 /* Initialize all CPUS, not just those running. */
422 for (i = 0; i <= mp_maxid; i++) {
423 c = zpcpu_get_cpu(smr, i);
424 c->c_seq = SMR_SEQ_INVALID;
427 atomic_thread_fence_seq_cst();
433 smr_destroy(smr_t smr)
436 smr_synchronize(smr);
437 uma_zfree(smr_shared_zone, smr->c_shared);
438 uma_zfree(smr_zone, smr);
442 * Initialize the UMA slab zone.
448 smr_shared_zone = uma_zcreate("SMR SHARED", sizeof(struct smr_shared),
449 NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, 0);
450 smr_zone = uma_zcreate("SMR CPU", sizeof(struct smr),
451 NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, UMA_ZONE_PCPU);
455 smr_init_counters(void *unused)
458 advance = counter_u64_alloc(M_WAITOK);
459 advance_wait = counter_u64_alloc(M_WAITOK);
460 poll = counter_u64_alloc(M_WAITOK);
461 poll_scan = counter_u64_alloc(M_WAITOK);
463 SYSINIT(smr_counters, SI_SUB_CPU, SI_ORDER_ANY, smr_init_counters, NULL);