1d4665eaaSJeff Roberson /*- 2d4665eaaSJeff Roberson * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3d4665eaaSJeff Roberson * 4da6e9935SJeff Roberson * Copyright (c) 2019,2020 Jeffrey Roberson <jeff@FreeBSD.org> 5d4665eaaSJeff Roberson * 6d4665eaaSJeff Roberson * Redistribution and use in source and binary forms, with or without 7d4665eaaSJeff Roberson * modification, are permitted provided that the following conditions 8d4665eaaSJeff Roberson * are met: 9d4665eaaSJeff Roberson * 1. Redistributions of source code must retain the above copyright 10d4665eaaSJeff Roberson * notice unmodified, this list of conditions, and the following 11d4665eaaSJeff Roberson * disclaimer. 12d4665eaaSJeff Roberson * 2. Redistributions in binary form must reproduce the above copyright 13d4665eaaSJeff Roberson * notice, this list of conditions and the following disclaimer in the 14d4665eaaSJeff Roberson * documentation and/or other materials provided with the distribution. 15d4665eaaSJeff Roberson * 16d4665eaaSJeff Roberson * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17d4665eaaSJeff Roberson * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18d4665eaaSJeff Roberson * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19d4665eaaSJeff Roberson * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20d4665eaaSJeff Roberson * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21d4665eaaSJeff Roberson * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22d4665eaaSJeff Roberson * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23d4665eaaSJeff Roberson * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24d4665eaaSJeff Roberson * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25d4665eaaSJeff Roberson * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26d4665eaaSJeff Roberson */ 27d4665eaaSJeff Roberson 28d4665eaaSJeff Roberson #include <sys/cdefs.h> 29d4665eaaSJeff Roberson __FBSDID("$FreeBSD$"); 30d4665eaaSJeff Roberson 31d4665eaaSJeff Roberson #include <sys/param.h> 32d4665eaaSJeff Roberson #include <sys/systm.h> 338d7f16a5SJeff Roberson #include <sys/counter.h> 34d4665eaaSJeff Roberson #include <sys/kernel.h> 358d7f16a5SJeff Roberson #include <sys/limits.h> 36d4665eaaSJeff Roberson #include <sys/proc.h> 37d4665eaaSJeff Roberson #include <sys/smp.h> 38d4665eaaSJeff Roberson #include <sys/smr.h> 398d7f16a5SJeff Roberson #include <sys/sysctl.h> 40d4665eaaSJeff Roberson 41d4665eaaSJeff Roberson #include <vm/uma.h> 42d4665eaaSJeff Roberson 43d4665eaaSJeff Roberson /* 44d4665eaaSJeff Roberson * This is a novel safe memory reclamation technique inspired by 45d4665eaaSJeff Roberson * epoch based reclamation from Samy Al Bahra's concurrency kit which 46d4665eaaSJeff Roberson * in turn was based on work described in: 47d4665eaaSJeff Roberson * Fraser, K. 2004. Practical Lock-Freedom. PhD Thesis, University 48d4665eaaSJeff Roberson * of Cambridge Computing Laboratory. 49d4665eaaSJeff Roberson * And shares some similarities with: 50d4665eaaSJeff Roberson * Wang, Stamler, Parmer. 2016 Parallel Sections: Scaling System-Level 51d4665eaaSJeff Roberson * Data-Structures 52d4665eaaSJeff Roberson * 53d4665eaaSJeff Roberson * This is not an implementation of hazard pointers or related 54d4665eaaSJeff Roberson * techniques. The term safe memory reclamation is used as a 55d4665eaaSJeff Roberson * generic descriptor for algorithms that defer frees to avoid 56d4665eaaSJeff Roberson * use-after-free errors with lockless datastructures. 57d4665eaaSJeff Roberson * 58d4665eaaSJeff Roberson * The basic approach is to maintain a monotonic write sequence 59d4665eaaSJeff Roberson * number that is updated on some application defined granularity. 60d4665eaaSJeff Roberson * Readers record the most recent write sequence number they have 61d4665eaaSJeff Roberson * observed. A shared read sequence number records the lowest 62d4665eaaSJeff Roberson * sequence number observed by any reader as of the last poll. Any 63d4665eaaSJeff Roberson * write older than this value has been observed by all readers 64d4665eaaSJeff Roberson * and memory can be reclaimed. Like Epoch we also detect idle 65d4665eaaSJeff Roberson * readers by storing an invalid sequence number in the per-cpu 66d4665eaaSJeff Roberson * state when the read section exits. Like Parsec we establish 67d4665eaaSJeff Roberson * a global write clock that is used to mark memory on free. 68d4665eaaSJeff Roberson * 69d4665eaaSJeff Roberson * The write and read sequence numbers can be thought of as a two 70d4665eaaSJeff Roberson * handed clock with readers always advancing towards writers. SMR 71d4665eaaSJeff Roberson * maintains the invariant that all readers can safely access memory 72d4665eaaSJeff Roberson * that was visible at the time they loaded their copy of the sequence 73d4665eaaSJeff Roberson * number. Periodically the read sequence or hand is polled and 74d4665eaaSJeff Roberson * advanced as far towards the write sequence as active readers allow. 75d4665eaaSJeff Roberson * Memory which was freed between the old and new global read sequence 76d4665eaaSJeff Roberson * number can now be reclaimed. When the system is idle the two hands 77d4665eaaSJeff Roberson * meet and no deferred memory is outstanding. Readers never advance 78d4665eaaSJeff Roberson * any sequence number, they only observe them. The shared read 79d4665eaaSJeff Roberson * sequence number is consequently never higher than the write sequence. 80d4665eaaSJeff Roberson * A stored sequence number that falls outside of this range has expired 81d4665eaaSJeff Roberson * and needs no scan to reclaim. 82d4665eaaSJeff Roberson * 83d4665eaaSJeff Roberson * A notable distinction between this SMR and Epoch, qsbr, rcu, etc. is 84d4665eaaSJeff Roberson * that advancing the sequence number is decoupled from detecting its 85d4665eaaSJeff Roberson * observation. This results in a more granular assignment of sequence 86d4665eaaSJeff Roberson * numbers even as read latencies prohibit all or some expiration. 87d4665eaaSJeff Roberson * It also allows writers to advance the sequence number and save the 88d4665eaaSJeff Roberson * poll for expiration until a later time when it is likely to 89d4665eaaSJeff Roberson * complete without waiting. The batch granularity and free-to-use 90d4665eaaSJeff Roberson * latency is dynamic and can be significantly smaller than in more 91d4665eaaSJeff Roberson * strict systems. 92d4665eaaSJeff Roberson * 93d4665eaaSJeff Roberson * This mechanism is primarily intended to be used in coordination with 94d4665eaaSJeff Roberson * UMA. By integrating with the allocator we avoid all of the callout 95d4665eaaSJeff Roberson * queue machinery and are provided with an efficient way to batch 96d4665eaaSJeff Roberson * sequence advancement and waiting. The allocator accumulates a full 97d4665eaaSJeff Roberson * per-cpu cache of memory before advancing the sequence. It then 98d4665eaaSJeff Roberson * delays waiting for this sequence to expire until the memory is 99d4665eaaSJeff Roberson * selected for reuse. In this way we only increment the sequence 100d4665eaaSJeff Roberson * value once for n=cache-size frees and the waits are done long 101d4665eaaSJeff Roberson * after the sequence has been expired so they need only be verified 102d4665eaaSJeff Roberson * to account for pathological conditions and to advance the read 103d4665eaaSJeff Roberson * sequence. Tying the sequence number to the bucket size has the 104d4665eaaSJeff Roberson * nice property that as the zone gets busier the buckets get larger 105d4665eaaSJeff Roberson * and the sequence writes become fewer. If the coherency of advancing 106d4665eaaSJeff Roberson * the write sequence number becomes too costly we can advance 107d4665eaaSJeff Roberson * it for every N buckets in exchange for higher free-to-use 108d4665eaaSJeff Roberson * latency and consequently higher memory consumption. 109d4665eaaSJeff Roberson * 110d4665eaaSJeff Roberson * If the read overhead of accessing the shared cacheline becomes 111d4665eaaSJeff Roberson * especially burdensome an invariant TSC could be used in place of the 112d4665eaaSJeff Roberson * sequence. The algorithm would then only need to maintain the minimum 113d4665eaaSJeff Roberson * observed tsc. This would trade potential cache synchronization 114d4665eaaSJeff Roberson * overhead for local serialization and cpu timestamp overhead. 115d4665eaaSJeff Roberson */ 116d4665eaaSJeff Roberson 117d4665eaaSJeff Roberson /* 118d4665eaaSJeff Roberson * A simplified diagram: 119d4665eaaSJeff Roberson * 120d4665eaaSJeff Roberson * 0 UINT_MAX 121d4665eaaSJeff Roberson * | -------------------- sequence number space -------------------- | 122d4665eaaSJeff Roberson * ^ rd seq ^ wr seq 123d4665eaaSJeff Roberson * | ----- valid sequence numbers ---- | 124d4665eaaSJeff Roberson * ^cpuA ^cpuC 125d4665eaaSJeff Roberson * | -- free -- | --------- deferred frees -------- | ---- free ---- | 126d4665eaaSJeff Roberson * 127d4665eaaSJeff Roberson * 128d4665eaaSJeff Roberson * In this example cpuA has the lowest sequence number and poll can 129d4665eaaSJeff Roberson * advance rd seq. cpuB is not running and is considered to observe 130d4665eaaSJeff Roberson * wr seq. 131d4665eaaSJeff Roberson * 132d4665eaaSJeff Roberson * Freed memory that is tagged with a sequence number between rd seq and 133d4665eaaSJeff Roberson * wr seq can not be safely reclaimed because cpuA may hold a reference to 134d4665eaaSJeff Roberson * it. Any other memory is guaranteed to be unreferenced. 135d4665eaaSJeff Roberson * 136d4665eaaSJeff Roberson * Any writer is free to advance wr seq at any time however it may busy 137d4665eaaSJeff Roberson * poll in pathological cases. 138d4665eaaSJeff Roberson */ 139d4665eaaSJeff Roberson 140d4665eaaSJeff Roberson static uma_zone_t smr_shared_zone; 141d4665eaaSJeff Roberson static uma_zone_t smr_zone; 142d4665eaaSJeff Roberson 143d4665eaaSJeff Roberson #ifndef INVARIANTS 144d4665eaaSJeff Roberson #define SMR_SEQ_INIT 1 /* All valid sequence numbers are odd. */ 145d4665eaaSJeff Roberson #define SMR_SEQ_INCR 2 146d4665eaaSJeff Roberson 147d4665eaaSJeff Roberson /* 148d4665eaaSJeff Roberson * SMR_SEQ_MAX_DELTA is the maximum distance allowed between rd_seq and 149d4665eaaSJeff Roberson * wr_seq. For the modular arithmetic to work a value of UNIT_MAX / 2 150d4665eaaSJeff Roberson * would be possible but it is checked after we increment the wr_seq so 151d4665eaaSJeff Roberson * a safety margin is left to prevent overflow. 152d4665eaaSJeff Roberson * 153d4665eaaSJeff Roberson * We will block until SMR_SEQ_MAX_ADVANCE sequence numbers have progressed 154d4665eaaSJeff Roberson * to prevent integer wrapping. See smr_advance() for more details. 155d4665eaaSJeff Roberson */ 156d4665eaaSJeff Roberson #define SMR_SEQ_MAX_DELTA (UINT_MAX / 4) 157d4665eaaSJeff Roberson #define SMR_SEQ_MAX_ADVANCE (SMR_SEQ_MAX_DELTA - 1024) 158d4665eaaSJeff Roberson #else 159d4665eaaSJeff Roberson /* We want to test the wrapping feature in invariants kernels. */ 160d4665eaaSJeff Roberson #define SMR_SEQ_INCR (UINT_MAX / 10000) 161d4665eaaSJeff Roberson #define SMR_SEQ_INIT (UINT_MAX - 100000) 162d4665eaaSJeff Roberson /* Force extra polls to test the integer overflow detection. */ 163*a40068e5SJeff Roberson #define SMR_SEQ_MAX_DELTA (SMR_SEQ_INCR * 32) 164d4665eaaSJeff Roberson #define SMR_SEQ_MAX_ADVANCE SMR_SEQ_MAX_DELTA / 2 165d4665eaaSJeff Roberson #endif 166d4665eaaSJeff Roberson 1678d7f16a5SJeff Roberson static SYSCTL_NODE(_debug, OID_AUTO, smr, CTLFLAG_RW, NULL, "SMR Stats"); 1688d7f16a5SJeff Roberson static counter_u64_t advance = EARLY_COUNTER; 1698d7f16a5SJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance, CTLFLAG_RD, &advance, ""); 1708d7f16a5SJeff Roberson static counter_u64_t advance_wait = EARLY_COUNTER; 1718d7f16a5SJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance_wait, CTLFLAG_RD, &advance_wait, ""); 1728d7f16a5SJeff Roberson static counter_u64_t poll = EARLY_COUNTER; 1738d7f16a5SJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll, CTLFLAG_RD, &poll, ""); 1748d7f16a5SJeff Roberson static counter_u64_t poll_scan = EARLY_COUNTER; 1758d7f16a5SJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll_scan, CTLFLAG_RD, &poll_scan, ""); 1768d7f16a5SJeff Roberson 1778d7f16a5SJeff Roberson 178d4665eaaSJeff Roberson /* 179d4665eaaSJeff Roberson * Advance the write sequence and return the new value for use as the 180d4665eaaSJeff Roberson * wait goal. This guarantees that any changes made by the calling 181d4665eaaSJeff Roberson * thread prior to this call will be visible to all threads after 182d4665eaaSJeff Roberson * rd_seq meets or exceeds the return value. 183d4665eaaSJeff Roberson * 184d4665eaaSJeff Roberson * This function may busy loop if the readers are roughly 1 billion 185d4665eaaSJeff Roberson * sequence numbers behind the writers. 186d4665eaaSJeff Roberson */ 187d4665eaaSJeff Roberson smr_seq_t 188d4665eaaSJeff Roberson smr_advance(smr_t smr) 189d4665eaaSJeff Roberson { 190d4665eaaSJeff Roberson smr_shared_t s; 191*a40068e5SJeff Roberson smr_seq_t goal, s_rd_seq; 192d4665eaaSJeff Roberson 193d4665eaaSJeff Roberson /* 194d4665eaaSJeff Roberson * It is illegal to enter while in an smr section. 195d4665eaaSJeff Roberson */ 196d4665eaaSJeff Roberson KASSERT(curthread->td_critnest == 0, 197d4665eaaSJeff Roberson ("smr_advance: Not allowed in a critical section.")); 198d4665eaaSJeff Roberson 199d4665eaaSJeff Roberson /* 200d4665eaaSJeff Roberson * Modifications not done in a smr section need to be visible 201d4665eaaSJeff Roberson * before advancing the seq. 202d4665eaaSJeff Roberson */ 203d4665eaaSJeff Roberson atomic_thread_fence_rel(); 204d4665eaaSJeff Roberson 205d4665eaaSJeff Roberson /* 206*a40068e5SJeff Roberson * Load the current read seq before incrementing the goal so 207*a40068e5SJeff Roberson * we are guaranteed it is always < goal. 208*a40068e5SJeff Roberson */ 209*a40068e5SJeff Roberson s = zpcpu_get(smr)->c_shared; 210*a40068e5SJeff Roberson s_rd_seq = atomic_load_acq_int(&s->s_rd_seq); 211*a40068e5SJeff Roberson 212*a40068e5SJeff Roberson /* 213d4665eaaSJeff Roberson * Increment the shared write sequence by 2. Since it is 214d4665eaaSJeff Roberson * initialized to 1 this means the only valid values are 215d4665eaaSJeff Roberson * odd and an observed value of 0 in a particular CPU means 216d4665eaaSJeff Roberson * it is not currently in a read section. 217d4665eaaSJeff Roberson */ 218d4665eaaSJeff Roberson goal = atomic_fetchadd_int(&s->s_wr_seq, SMR_SEQ_INCR) + SMR_SEQ_INCR; 2198d7f16a5SJeff Roberson counter_u64_add(advance, 1); 220d4665eaaSJeff Roberson 221d4665eaaSJeff Roberson /* 222d4665eaaSJeff Roberson * Force a synchronization here if the goal is getting too 223d4665eaaSJeff Roberson * far ahead of the read sequence number. This keeps the 224d4665eaaSJeff Roberson * wrap detecting arithmetic working in pathological cases. 225d4665eaaSJeff Roberson */ 226*a40068e5SJeff Roberson if (SMR_SEQ_DELTA(goal, s_rd_seq) >= SMR_SEQ_MAX_DELTA) { 2278d7f16a5SJeff Roberson counter_u64_add(advance_wait, 1); 228d4665eaaSJeff Roberson smr_wait(smr, goal - SMR_SEQ_MAX_ADVANCE); 2298d7f16a5SJeff Roberson } 230d4665eaaSJeff Roberson 231d4665eaaSJeff Roberson return (goal); 232d4665eaaSJeff Roberson } 233d4665eaaSJeff Roberson 234bc650984SJeff Roberson smr_seq_t 235bc650984SJeff Roberson smr_advance_deferred(smr_t smr, int limit) 236bc650984SJeff Roberson { 237bc650984SJeff Roberson smr_seq_t goal; 238bc650984SJeff Roberson smr_t csmr; 239bc650984SJeff Roberson 240bc650984SJeff Roberson critical_enter(); 241bc650984SJeff Roberson csmr = zpcpu_get(smr); 242bc650984SJeff Roberson if (++csmr->c_deferred >= limit) { 243bc650984SJeff Roberson goal = SMR_SEQ_INVALID; 244bc650984SJeff Roberson csmr->c_deferred = 0; 245bc650984SJeff Roberson } else 246bc650984SJeff Roberson goal = smr_shared_current(csmr->c_shared) + SMR_SEQ_INCR; 247bc650984SJeff Roberson critical_exit(); 248bc650984SJeff Roberson if (goal != SMR_SEQ_INVALID) 249bc650984SJeff Roberson return (goal); 250bc650984SJeff Roberson 251bc650984SJeff Roberson return (smr_advance(smr)); 252bc650984SJeff Roberson } 253bc650984SJeff Roberson 254d4665eaaSJeff Roberson /* 255d4665eaaSJeff Roberson * Poll to determine whether all readers have observed the 'goal' write 256d4665eaaSJeff Roberson * sequence number. 257d4665eaaSJeff Roberson * 258d4665eaaSJeff Roberson * If wait is true this will spin until the goal is met. 259d4665eaaSJeff Roberson * 260d4665eaaSJeff Roberson * This routine will updated the minimum observed read sequence number in 261d4665eaaSJeff Roberson * s_rd_seq if it does a scan. It may not do a scan if another call has 262d4665eaaSJeff Roberson * advanced s_rd_seq beyond the callers goal already. 263d4665eaaSJeff Roberson * 264d4665eaaSJeff Roberson * Returns true if the goal is met and false if not. 265d4665eaaSJeff Roberson */ 266d4665eaaSJeff Roberson bool 267d4665eaaSJeff Roberson smr_poll(smr_t smr, smr_seq_t goal, bool wait) 268d4665eaaSJeff Roberson { 269d4665eaaSJeff Roberson smr_shared_t s; 270d4665eaaSJeff Roberson smr_t c; 271d4665eaaSJeff Roberson smr_seq_t s_wr_seq, s_rd_seq, rd_seq, c_seq; 272d4665eaaSJeff Roberson int i; 273d4665eaaSJeff Roberson bool success; 274d4665eaaSJeff Roberson 275d4665eaaSJeff Roberson /* 276d4665eaaSJeff Roberson * It is illegal to enter while in an smr section. 277d4665eaaSJeff Roberson */ 278d4665eaaSJeff Roberson KASSERT(!wait || curthread->td_critnest == 0, 279d4665eaaSJeff Roberson ("smr_poll: Blocking not allowed in a critical section.")); 280d4665eaaSJeff Roberson 281d4665eaaSJeff Roberson /* 282d4665eaaSJeff Roberson * Use a critical section so that we can avoid ABA races 283d4665eaaSJeff Roberson * caused by long preemption sleeps. 284d4665eaaSJeff Roberson */ 285d4665eaaSJeff Roberson success = true; 286d4665eaaSJeff Roberson critical_enter(); 287915c367eSJeff Roberson s = zpcpu_get(smr)->c_shared; 2888d7f16a5SJeff Roberson counter_u64_add_protected(poll, 1); 289d4665eaaSJeff Roberson 290d4665eaaSJeff Roberson /* 291d4665eaaSJeff Roberson * Acquire barrier loads s_wr_seq after s_rd_seq so that we can not 292d4665eaaSJeff Roberson * observe an updated read sequence that is larger than write. 293d4665eaaSJeff Roberson */ 294d4665eaaSJeff Roberson s_rd_seq = atomic_load_acq_int(&s->s_rd_seq); 295915c367eSJeff Roberson 296915c367eSJeff Roberson /* 297915c367eSJeff Roberson * wr_seq must be loaded prior to any c_seq value so that a stale 298915c367eSJeff Roberson * c_seq can only reference time after this wr_seq. 299915c367eSJeff Roberson */ 300915c367eSJeff Roberson s_wr_seq = atomic_load_acq_int(&s->s_wr_seq); 301d4665eaaSJeff Roberson 302d4665eaaSJeff Roberson /* 303bc650984SJeff Roberson * This may have come from a deferred advance. Consider one 304bc650984SJeff Roberson * increment past the current wr_seq valid and make sure we 305bc650984SJeff Roberson * have advanced far enough to succeed. We simply add to avoid 306bc650984SJeff Roberson * an additional fence. 307bc650984SJeff Roberson */ 308bc650984SJeff Roberson if (goal == s_wr_seq + SMR_SEQ_INCR) { 309bc650984SJeff Roberson atomic_add_int(&s->s_wr_seq, SMR_SEQ_INCR); 310bc650984SJeff Roberson s_wr_seq = goal; 311bc650984SJeff Roberson } 312bc650984SJeff Roberson 313bc650984SJeff Roberson /* 314d4665eaaSJeff Roberson * Detect whether the goal is valid and has already been observed. 315d4665eaaSJeff Roberson * 316d4665eaaSJeff Roberson * The goal must be in the range of s_wr_seq >= goal >= s_rd_seq for 317d4665eaaSJeff Roberson * it to be valid. If it is not then the caller held on to it and 318d4665eaaSJeff Roberson * the integer wrapped. If we wrapped back within range the caller 319d4665eaaSJeff Roberson * will harmlessly scan. 320d4665eaaSJeff Roberson * 321d4665eaaSJeff Roberson * A valid goal must be greater than s_rd_seq or we have not verified 322d4665eaaSJeff Roberson * that it has been observed and must fall through to polling. 323d4665eaaSJeff Roberson */ 324d4665eaaSJeff Roberson if (SMR_SEQ_GEQ(s_rd_seq, goal) || SMR_SEQ_LT(s_wr_seq, goal)) 325d4665eaaSJeff Roberson goto out; 326d4665eaaSJeff Roberson 327d4665eaaSJeff Roberson /* 328d4665eaaSJeff Roberson * Loop until all cores have observed the goal sequence or have 329d4665eaaSJeff Roberson * gone inactive. Keep track of the oldest sequence currently 330d4665eaaSJeff Roberson * active as rd_seq. 331d4665eaaSJeff Roberson */ 3328d7f16a5SJeff Roberson counter_u64_add_protected(poll_scan, 1); 333d4665eaaSJeff Roberson rd_seq = s_wr_seq; 334d4665eaaSJeff Roberson CPU_FOREACH(i) { 335d4665eaaSJeff Roberson c = zpcpu_get_cpu(smr, i); 336d4665eaaSJeff Roberson c_seq = SMR_SEQ_INVALID; 337d4665eaaSJeff Roberson for (;;) { 338d4665eaaSJeff Roberson c_seq = atomic_load_int(&c->c_seq); 339d4665eaaSJeff Roberson if (c_seq == SMR_SEQ_INVALID) 340d4665eaaSJeff Roberson break; 341d4665eaaSJeff Roberson 342d4665eaaSJeff Roberson /* 343d4665eaaSJeff Roberson * There is a race described in smr.h:smr_enter that 344d4665eaaSJeff Roberson * can lead to a stale seq value but not stale data 345d4665eaaSJeff Roberson * access. If we find a value out of range here we 346d4665eaaSJeff Roberson * pin it to the current min to prevent it from 347d4665eaaSJeff Roberson * advancing until that stale section has expired. 348d4665eaaSJeff Roberson * 349d4665eaaSJeff Roberson * The race is created when a cpu loads the s_wr_seq 350d4665eaaSJeff Roberson * value in a local register and then another thread 351d4665eaaSJeff Roberson * advances s_wr_seq and calls smr_poll() which will 352d4665eaaSJeff Roberson * oberve no value yet in c_seq and advance s_rd_seq 353d4665eaaSJeff Roberson * up to s_wr_seq which is beyond the register 354d4665eaaSJeff Roberson * cached value. This is only likely to happen on 355d4665eaaSJeff Roberson * hypervisor or with a system management interrupt. 356d4665eaaSJeff Roberson */ 357d4665eaaSJeff Roberson if (SMR_SEQ_LT(c_seq, s_rd_seq)) 358d4665eaaSJeff Roberson c_seq = s_rd_seq; 359d4665eaaSJeff Roberson 360d4665eaaSJeff Roberson /* 361d4665eaaSJeff Roberson * If the sequence number meets the goal we are 362d4665eaaSJeff Roberson * done with this cpu. 363d4665eaaSJeff Roberson */ 364d4665eaaSJeff Roberson if (SMR_SEQ_GEQ(c_seq, goal)) 365d4665eaaSJeff Roberson break; 366d4665eaaSJeff Roberson 367d4665eaaSJeff Roberson /* 368d4665eaaSJeff Roberson * If we're not waiting we will still scan the rest 369d4665eaaSJeff Roberson * of the cpus and update s_rd_seq before returning 370d4665eaaSJeff Roberson * an error. 371d4665eaaSJeff Roberson */ 372d4665eaaSJeff Roberson if (!wait) { 373d4665eaaSJeff Roberson success = false; 374d4665eaaSJeff Roberson break; 375d4665eaaSJeff Roberson } 376d4665eaaSJeff Roberson cpu_spinwait(); 377d4665eaaSJeff Roberson } 378d4665eaaSJeff Roberson 379d4665eaaSJeff Roberson /* 380d4665eaaSJeff Roberson * Limit the minimum observed rd_seq whether we met the goal 381d4665eaaSJeff Roberson * or not. 382d4665eaaSJeff Roberson */ 383d4665eaaSJeff Roberson if (c_seq != SMR_SEQ_INVALID && SMR_SEQ_GT(rd_seq, c_seq)) 384d4665eaaSJeff Roberson rd_seq = c_seq; 385d4665eaaSJeff Roberson } 386d4665eaaSJeff Roberson 387d4665eaaSJeff Roberson /* 388d4665eaaSJeff Roberson * Advance the rd_seq as long as we observed the most recent one. 389d4665eaaSJeff Roberson */ 390d4665eaaSJeff Roberson s_rd_seq = atomic_load_int(&s->s_rd_seq); 391d4665eaaSJeff Roberson do { 392d4665eaaSJeff Roberson if (SMR_SEQ_LEQ(rd_seq, s_rd_seq)) 3938d7f16a5SJeff Roberson goto out; 394d4665eaaSJeff Roberson } while (atomic_fcmpset_int(&s->s_rd_seq, &s_rd_seq, rd_seq) == 0); 395d4665eaaSJeff Roberson 396d4665eaaSJeff Roberson out: 397d4665eaaSJeff Roberson critical_exit(); 398d4665eaaSJeff Roberson 399915c367eSJeff Roberson /* 400915c367eSJeff Roberson * Serialize with smr_advance()/smr_exit(). The caller is now free 401915c367eSJeff Roberson * to modify memory as expected. 402915c367eSJeff Roberson */ 403915c367eSJeff Roberson atomic_thread_fence_acq(); 404915c367eSJeff Roberson 405d4665eaaSJeff Roberson return (success); 406d4665eaaSJeff Roberson } 407d4665eaaSJeff Roberson 408d4665eaaSJeff Roberson smr_t 409d4665eaaSJeff Roberson smr_create(const char *name) 410d4665eaaSJeff Roberson { 411d4665eaaSJeff Roberson smr_t smr, c; 412d4665eaaSJeff Roberson smr_shared_t s; 413d4665eaaSJeff Roberson int i; 414d4665eaaSJeff Roberson 415d4665eaaSJeff Roberson s = uma_zalloc(smr_shared_zone, M_WAITOK); 416d4665eaaSJeff Roberson smr = uma_zalloc(smr_zone, M_WAITOK); 417d4665eaaSJeff Roberson 418d4665eaaSJeff Roberson s->s_name = name; 419d4665eaaSJeff Roberson s->s_rd_seq = s->s_wr_seq = SMR_SEQ_INIT; 420d4665eaaSJeff Roberson 421d4665eaaSJeff Roberson /* Initialize all CPUS, not just those running. */ 422d4665eaaSJeff Roberson for (i = 0; i <= mp_maxid; i++) { 423d4665eaaSJeff Roberson c = zpcpu_get_cpu(smr, i); 424d4665eaaSJeff Roberson c->c_seq = SMR_SEQ_INVALID; 425d4665eaaSJeff Roberson c->c_shared = s; 426d4665eaaSJeff Roberson } 427d4665eaaSJeff Roberson atomic_thread_fence_seq_cst(); 428d4665eaaSJeff Roberson 429d4665eaaSJeff Roberson return (smr); 430d4665eaaSJeff Roberson } 431d4665eaaSJeff Roberson 432d4665eaaSJeff Roberson void 433d4665eaaSJeff Roberson smr_destroy(smr_t smr) 434d4665eaaSJeff Roberson { 435d4665eaaSJeff Roberson 436d4665eaaSJeff Roberson smr_synchronize(smr); 437d4665eaaSJeff Roberson uma_zfree(smr_shared_zone, smr->c_shared); 438d4665eaaSJeff Roberson uma_zfree(smr_zone, smr); 439d4665eaaSJeff Roberson } 440d4665eaaSJeff Roberson 441d4665eaaSJeff Roberson /* 442d4665eaaSJeff Roberson * Initialize the UMA slab zone. 443d4665eaaSJeff Roberson */ 444d4665eaaSJeff Roberson void 445d4665eaaSJeff Roberson smr_init(void) 446d4665eaaSJeff Roberson { 447d4665eaaSJeff Roberson 448d4665eaaSJeff Roberson smr_shared_zone = uma_zcreate("SMR SHARED", sizeof(struct smr_shared), 449d4665eaaSJeff Roberson NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, 0); 450d4665eaaSJeff Roberson smr_zone = uma_zcreate("SMR CPU", sizeof(struct smr), 451d4665eaaSJeff Roberson NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, UMA_ZONE_PCPU); 452d4665eaaSJeff Roberson } 4538d7f16a5SJeff Roberson 4548d7f16a5SJeff Roberson static void 4558d7f16a5SJeff Roberson smr_init_counters(void *unused) 4568d7f16a5SJeff Roberson { 4578d7f16a5SJeff Roberson 4588d7f16a5SJeff Roberson advance = counter_u64_alloc(M_WAITOK); 4598d7f16a5SJeff Roberson advance_wait = counter_u64_alloc(M_WAITOK); 4608d7f16a5SJeff Roberson poll = counter_u64_alloc(M_WAITOK); 4618d7f16a5SJeff Roberson poll_scan = counter_u64_alloc(M_WAITOK); 4628d7f16a5SJeff Roberson } 4638d7f16a5SJeff Roberson SYSINIT(smr_counters, SI_SUB_CPU, SI_ORDER_ANY, smr_init_counters, NULL); 464