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 /* 44*226dd6dbSJeff Roberson * Global Unbounded Sequences (GUS) 45*226dd6dbSJeff Roberson * 46d4665eaaSJeff Roberson * This is a novel safe memory reclamation technique inspired by 47d4665eaaSJeff Roberson * epoch based reclamation from Samy Al Bahra's concurrency kit which 48d4665eaaSJeff Roberson * in turn was based on work described in: 49d4665eaaSJeff Roberson * Fraser, K. 2004. Practical Lock-Freedom. PhD Thesis, University 50d4665eaaSJeff Roberson * of Cambridge Computing Laboratory. 51d4665eaaSJeff Roberson * And shares some similarities with: 52d4665eaaSJeff Roberson * Wang, Stamler, Parmer. 2016 Parallel Sections: Scaling System-Level 53d4665eaaSJeff Roberson * Data-Structures 54d4665eaaSJeff Roberson * 55d4665eaaSJeff Roberson * This is not an implementation of hazard pointers or related 56d4665eaaSJeff Roberson * techniques. The term safe memory reclamation is used as a 57d4665eaaSJeff Roberson * generic descriptor for algorithms that defer frees to avoid 58*226dd6dbSJeff Roberson * use-after-free errors with lockless datastructures or as 59*226dd6dbSJeff Roberson * a mechanism to detect quiescence for writer synchronization. 60d4665eaaSJeff Roberson * 61d4665eaaSJeff Roberson * The basic approach is to maintain a monotonic write sequence 62d4665eaaSJeff Roberson * number that is updated on some application defined granularity. 63d4665eaaSJeff Roberson * Readers record the most recent write sequence number they have 64d4665eaaSJeff Roberson * observed. A shared read sequence number records the lowest 65d4665eaaSJeff Roberson * sequence number observed by any reader as of the last poll. Any 66d4665eaaSJeff Roberson * write older than this value has been observed by all readers 67d4665eaaSJeff Roberson * and memory can be reclaimed. Like Epoch we also detect idle 68d4665eaaSJeff Roberson * readers by storing an invalid sequence number in the per-cpu 69d4665eaaSJeff Roberson * state when the read section exits. Like Parsec we establish 70d4665eaaSJeff Roberson * a global write clock that is used to mark memory on free. 71d4665eaaSJeff Roberson * 72d4665eaaSJeff Roberson * The write and read sequence numbers can be thought of as a two 73*226dd6dbSJeff Roberson * handed clock with readers always advancing towards writers. GUS 74d4665eaaSJeff Roberson * maintains the invariant that all readers can safely access memory 75d4665eaaSJeff Roberson * that was visible at the time they loaded their copy of the sequence 76d4665eaaSJeff Roberson * number. Periodically the read sequence or hand is polled and 77d4665eaaSJeff Roberson * advanced as far towards the write sequence as active readers allow. 78d4665eaaSJeff Roberson * Memory which was freed between the old and new global read sequence 79d4665eaaSJeff Roberson * number can now be reclaimed. When the system is idle the two hands 80d4665eaaSJeff Roberson * meet and no deferred memory is outstanding. Readers never advance 81d4665eaaSJeff Roberson * any sequence number, they only observe them. The shared read 82d4665eaaSJeff Roberson * sequence number is consequently never higher than the write sequence. 83d4665eaaSJeff Roberson * A stored sequence number that falls outside of this range has expired 84d4665eaaSJeff Roberson * and needs no scan to reclaim. 85d4665eaaSJeff Roberson * 86*226dd6dbSJeff Roberson * A notable distinction between GUS and Epoch, qsbr, rcu, etc. is 87d4665eaaSJeff Roberson * that advancing the sequence number is decoupled from detecting its 88*226dd6dbSJeff Roberson * observation. That is to say, the delta between read and write 89*226dd6dbSJeff Roberson * sequence numbers is not bound. This can be thought of as a more 90*226dd6dbSJeff Roberson * generalized form of epoch which requires them at most one step 91*226dd6dbSJeff Roberson * apart. This results in a more granular assignment of sequence 92d4665eaaSJeff Roberson * numbers even as read latencies prohibit all or some expiration. 93d4665eaaSJeff Roberson * It also allows writers to advance the sequence number and save the 94d4665eaaSJeff Roberson * poll for expiration until a later time when it is likely to 95d4665eaaSJeff Roberson * complete without waiting. The batch granularity and free-to-use 96d4665eaaSJeff Roberson * latency is dynamic and can be significantly smaller than in more 97d4665eaaSJeff Roberson * strict systems. 98d4665eaaSJeff Roberson * 99d4665eaaSJeff Roberson * This mechanism is primarily intended to be used in coordination with 100d4665eaaSJeff Roberson * UMA. By integrating with the allocator we avoid all of the callout 101d4665eaaSJeff Roberson * queue machinery and are provided with an efficient way to batch 102d4665eaaSJeff Roberson * sequence advancement and waiting. The allocator accumulates a full 103d4665eaaSJeff Roberson * per-cpu cache of memory before advancing the sequence. It then 104d4665eaaSJeff Roberson * delays waiting for this sequence to expire until the memory is 105d4665eaaSJeff Roberson * selected for reuse. In this way we only increment the sequence 106d4665eaaSJeff Roberson * value once for n=cache-size frees and the waits are done long 107d4665eaaSJeff Roberson * after the sequence has been expired so they need only be verified 108d4665eaaSJeff Roberson * to account for pathological conditions and to advance the read 109d4665eaaSJeff Roberson * sequence. Tying the sequence number to the bucket size has the 110d4665eaaSJeff Roberson * nice property that as the zone gets busier the buckets get larger 111d4665eaaSJeff Roberson * and the sequence writes become fewer. If the coherency of advancing 112d4665eaaSJeff Roberson * the write sequence number becomes too costly we can advance 113d4665eaaSJeff Roberson * it for every N buckets in exchange for higher free-to-use 114d4665eaaSJeff Roberson * latency and consequently higher memory consumption. 115d4665eaaSJeff Roberson * 116d4665eaaSJeff Roberson * If the read overhead of accessing the shared cacheline becomes 117d4665eaaSJeff Roberson * especially burdensome an invariant TSC could be used in place of the 118d4665eaaSJeff Roberson * sequence. The algorithm would then only need to maintain the minimum 119d4665eaaSJeff Roberson * observed tsc. This would trade potential cache synchronization 120d4665eaaSJeff Roberson * overhead for local serialization and cpu timestamp overhead. 121d4665eaaSJeff Roberson */ 122d4665eaaSJeff Roberson 123d4665eaaSJeff Roberson /* 124d4665eaaSJeff Roberson * A simplified diagram: 125d4665eaaSJeff Roberson * 126d4665eaaSJeff Roberson * 0 UINT_MAX 127d4665eaaSJeff Roberson * | -------------------- sequence number space -------------------- | 128d4665eaaSJeff Roberson * ^ rd seq ^ wr seq 129d4665eaaSJeff Roberson * | ----- valid sequence numbers ---- | 130d4665eaaSJeff Roberson * ^cpuA ^cpuC 131d4665eaaSJeff Roberson * | -- free -- | --------- deferred frees -------- | ---- free ---- | 132d4665eaaSJeff Roberson * 133d4665eaaSJeff Roberson * 134d4665eaaSJeff Roberson * In this example cpuA has the lowest sequence number and poll can 135d4665eaaSJeff Roberson * advance rd seq. cpuB is not running and is considered to observe 136d4665eaaSJeff Roberson * wr seq. 137d4665eaaSJeff Roberson * 138d4665eaaSJeff Roberson * Freed memory that is tagged with a sequence number between rd seq and 139d4665eaaSJeff Roberson * wr seq can not be safely reclaimed because cpuA may hold a reference to 140d4665eaaSJeff Roberson * it. Any other memory is guaranteed to be unreferenced. 141d4665eaaSJeff Roberson * 142d4665eaaSJeff Roberson * Any writer is free to advance wr seq at any time however it may busy 143d4665eaaSJeff Roberson * poll in pathological cases. 144d4665eaaSJeff Roberson */ 145d4665eaaSJeff Roberson 146d4665eaaSJeff Roberson static uma_zone_t smr_shared_zone; 147d4665eaaSJeff Roberson static uma_zone_t smr_zone; 148d4665eaaSJeff Roberson 149d4665eaaSJeff Roberson #ifndef INVARIANTS 150d4665eaaSJeff Roberson #define SMR_SEQ_INIT 1 /* All valid sequence numbers are odd. */ 151d4665eaaSJeff Roberson #define SMR_SEQ_INCR 2 152d4665eaaSJeff Roberson 153d4665eaaSJeff Roberson /* 154d4665eaaSJeff Roberson * SMR_SEQ_MAX_DELTA is the maximum distance allowed between rd_seq and 155d4665eaaSJeff Roberson * wr_seq. For the modular arithmetic to work a value of UNIT_MAX / 2 156d4665eaaSJeff Roberson * would be possible but it is checked after we increment the wr_seq so 157d4665eaaSJeff Roberson * a safety margin is left to prevent overflow. 158d4665eaaSJeff Roberson * 159d4665eaaSJeff Roberson * We will block until SMR_SEQ_MAX_ADVANCE sequence numbers have progressed 160d4665eaaSJeff Roberson * to prevent integer wrapping. See smr_advance() for more details. 161d4665eaaSJeff Roberson */ 162d4665eaaSJeff Roberson #define SMR_SEQ_MAX_DELTA (UINT_MAX / 4) 163d4665eaaSJeff Roberson #define SMR_SEQ_MAX_ADVANCE (SMR_SEQ_MAX_DELTA - 1024) 164d4665eaaSJeff Roberson #else 165d4665eaaSJeff Roberson /* We want to test the wrapping feature in invariants kernels. */ 166d4665eaaSJeff Roberson #define SMR_SEQ_INCR (UINT_MAX / 10000) 167d4665eaaSJeff Roberson #define SMR_SEQ_INIT (UINT_MAX - 100000) 168d4665eaaSJeff Roberson /* Force extra polls to test the integer overflow detection. */ 169a40068e5SJeff Roberson #define SMR_SEQ_MAX_DELTA (SMR_SEQ_INCR * 32) 170d4665eaaSJeff Roberson #define SMR_SEQ_MAX_ADVANCE SMR_SEQ_MAX_DELTA / 2 171d4665eaaSJeff Roberson #endif 172d4665eaaSJeff Roberson 173*226dd6dbSJeff Roberson /* 174*226dd6dbSJeff Roberson * The grace period for lazy (tick based) SMR. 175*226dd6dbSJeff Roberson * 176*226dd6dbSJeff Roberson * Hardclock is responsible for advancing ticks on a single CPU while every 177*226dd6dbSJeff Roberson * CPU receives a regular clock interrupt. The clock interrupts are flushing 178*226dd6dbSJeff Roberson * the store buffers and any speculative loads that may violate our invariants. 179*226dd6dbSJeff Roberson * Because these interrupts are not synchronized we must wait one additional 180*226dd6dbSJeff Roberson * tick in the future to be certain that all processors have had their state 181*226dd6dbSJeff Roberson * synchronized by an interrupt. 182*226dd6dbSJeff Roberson * 183*226dd6dbSJeff Roberson * This assumes that the clock interrupt will only be delayed by other causes 184*226dd6dbSJeff Roberson * that will flush the store buffer or prevent access to the section protected 185*226dd6dbSJeff Roberson * data. For example, an idle processor, or an system management interrupt, 186*226dd6dbSJeff Roberson * or a vm exit. 187*226dd6dbSJeff Roberson * 188*226dd6dbSJeff Roberson * We must wait one additional tick if we are around the wrap condition 189*226dd6dbSJeff Roberson * because the write seq will move forward by two with one interrupt. 190*226dd6dbSJeff Roberson */ 191*226dd6dbSJeff Roberson #define SMR_LAZY_GRACE 2 192*226dd6dbSJeff Roberson #define SMR_LAZY_GRACE_MAX (SMR_LAZY_GRACE + 1) 1938d7f16a5SJeff Roberson 194d4665eaaSJeff Roberson /* 195*226dd6dbSJeff Roberson * The maximum sequence number ahead of wr_seq that may still be valid. The 196*226dd6dbSJeff Roberson * sequence may not be advanced on write for lazy or deferred SMRs. In this 197*226dd6dbSJeff Roberson * case poll needs to attempt to forward the sequence number if the goal is 198*226dd6dbSJeff Roberson * within wr_seq + SMR_SEQ_ADVANCE. 199*226dd6dbSJeff Roberson */ 200*226dd6dbSJeff Roberson #define SMR_SEQ_ADVANCE MAX(SMR_SEQ_INCR, SMR_LAZY_GRACE_MAX) 201*226dd6dbSJeff Roberson 202*226dd6dbSJeff Roberson static SYSCTL_NODE(_debug, OID_AUTO, smr, CTLFLAG_RW, NULL, "SMR Stats"); 203*226dd6dbSJeff Roberson static counter_u64_t advance = EARLY_COUNTER; 204*226dd6dbSJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance, CTLFLAG_RW, &advance, ""); 205*226dd6dbSJeff Roberson static counter_u64_t advance_wait = EARLY_COUNTER; 206*226dd6dbSJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, advance_wait, CTLFLAG_RW, &advance_wait, ""); 207*226dd6dbSJeff Roberson static counter_u64_t poll = EARLY_COUNTER; 208*226dd6dbSJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll, CTLFLAG_RW, &poll, ""); 209*226dd6dbSJeff Roberson static counter_u64_t poll_scan = EARLY_COUNTER; 210*226dd6dbSJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll_scan, CTLFLAG_RW, &poll_scan, ""); 211*226dd6dbSJeff Roberson static counter_u64_t poll_fail = EARLY_COUNTER; 212*226dd6dbSJeff Roberson SYSCTL_COUNTER_U64(_debug_smr, OID_AUTO, poll_fail, CTLFLAG_RW, &poll_fail, ""); 213*226dd6dbSJeff Roberson 214*226dd6dbSJeff Roberson /* 215*226dd6dbSJeff Roberson * Advance a lazy write sequence number. These move forward at the rate of 216*226dd6dbSJeff Roberson * ticks. Grace is two ticks in the future. lazy write sequence numbers can 217*226dd6dbSJeff Roberson * be even but not SMR_SEQ_INVALID so we pause time for a tick when we wrap. 218*226dd6dbSJeff Roberson * 219*226dd6dbSJeff Roberson * This returns the _current_ write sequence number. The lazy goal sequence 220*226dd6dbSJeff Roberson * number is SMR_LAZY_GRACE ticks ahead. 221*226dd6dbSJeff Roberson */ 222*226dd6dbSJeff Roberson static smr_seq_t 223*226dd6dbSJeff Roberson smr_lazy_advance(smr_t smr, smr_shared_t s) 224*226dd6dbSJeff Roberson { 225*226dd6dbSJeff Roberson smr_seq_t s_rd_seq, s_wr_seq, goal; 226*226dd6dbSJeff Roberson int t; 227*226dd6dbSJeff Roberson 228*226dd6dbSJeff Roberson CRITICAL_ASSERT(curthread); 229*226dd6dbSJeff Roberson 230*226dd6dbSJeff Roberson /* 231*226dd6dbSJeff Roberson * Load s_wr_seq prior to ticks to ensure that the thread that 232*226dd6dbSJeff Roberson * observes the largest value wins. 233*226dd6dbSJeff Roberson */ 234*226dd6dbSJeff Roberson s_wr_seq = atomic_load_acq_int(&s->s_wr_seq); 235*226dd6dbSJeff Roberson 236*226dd6dbSJeff Roberson /* 237*226dd6dbSJeff Roberson * We must not allow a zero tick value. We go back in time one tick 238*226dd6dbSJeff Roberson * and advance the grace period forward one tick around zero. 239*226dd6dbSJeff Roberson */ 240*226dd6dbSJeff Roberson t = ticks; 241*226dd6dbSJeff Roberson if (t == SMR_SEQ_INVALID) 242*226dd6dbSJeff Roberson t--; 243*226dd6dbSJeff Roberson 244*226dd6dbSJeff Roberson /* 245*226dd6dbSJeff Roberson * The most probable condition that the update already took place. 246*226dd6dbSJeff Roberson */ 247*226dd6dbSJeff Roberson if (__predict_true(t == s_wr_seq)) 248*226dd6dbSJeff Roberson goto out; 249*226dd6dbSJeff Roberson 250*226dd6dbSJeff Roberson /* 251*226dd6dbSJeff Roberson * After long idle periods the read sequence may fall too far 252*226dd6dbSJeff Roberson * behind write. Prevent poll from ever seeing this condition 253*226dd6dbSJeff Roberson * by updating the stale rd_seq. This assumes that there can 254*226dd6dbSJeff Roberson * be no valid section 2bn ticks old. The rd_seq update must 255*226dd6dbSJeff Roberson * be visible before wr_seq to avoid races with other advance 256*226dd6dbSJeff Roberson * callers. 257*226dd6dbSJeff Roberson */ 258*226dd6dbSJeff Roberson s_rd_seq = atomic_load_int(&s->s_rd_seq); 259*226dd6dbSJeff Roberson if (SMR_SEQ_GT(s_rd_seq, t)) 260*226dd6dbSJeff Roberson atomic_cmpset_rel_int(&s->s_rd_seq, s_rd_seq, t); 261*226dd6dbSJeff Roberson 262*226dd6dbSJeff Roberson /* 263*226dd6dbSJeff Roberson * Release to synchronize with the wr_seq load above. Ignore 264*226dd6dbSJeff Roberson * cmpset failures from simultaneous updates. 265*226dd6dbSJeff Roberson */ 266*226dd6dbSJeff Roberson atomic_cmpset_rel_int(&s->s_wr_seq, s_wr_seq, t); 267*226dd6dbSJeff Roberson counter_u64_add(advance, 1); 268*226dd6dbSJeff Roberson /* If we lost either update race another thread did it. */ 269*226dd6dbSJeff Roberson s_wr_seq = t; 270*226dd6dbSJeff Roberson out: 271*226dd6dbSJeff Roberson goal = s_wr_seq + SMR_LAZY_GRACE; 272*226dd6dbSJeff Roberson /* Skip over the SMR_SEQ_INVALID tick. */ 273*226dd6dbSJeff Roberson if (goal < SMR_LAZY_GRACE) 274*226dd6dbSJeff Roberson goal++; 275*226dd6dbSJeff Roberson return (goal); 276*226dd6dbSJeff Roberson } 277*226dd6dbSJeff Roberson 278*226dd6dbSJeff Roberson /* 279*226dd6dbSJeff Roberson * Increment the shared write sequence by 2. Since it is initialized 280*226dd6dbSJeff Roberson * to 1 this means the only valid values are odd and an observed value 281*226dd6dbSJeff Roberson * of 0 in a particular CPU means it is not currently in a read section. 282*226dd6dbSJeff Roberson */ 283*226dd6dbSJeff Roberson static smr_seq_t 284*226dd6dbSJeff Roberson smr_shared_advance(smr_shared_t s) 285*226dd6dbSJeff Roberson { 286*226dd6dbSJeff Roberson 287*226dd6dbSJeff Roberson return (atomic_fetchadd_int(&s->s_wr_seq, SMR_SEQ_INCR) + SMR_SEQ_INCR); 288*226dd6dbSJeff Roberson } 289*226dd6dbSJeff Roberson 290*226dd6dbSJeff Roberson /* 291*226dd6dbSJeff Roberson * Advance the write sequence number for a normal smr section. If the 292*226dd6dbSJeff Roberson * write sequence is too far behind the read sequence we have to poll 293*226dd6dbSJeff Roberson * to advance rd_seq and prevent undetectable wraps. 294*226dd6dbSJeff Roberson */ 295*226dd6dbSJeff Roberson static smr_seq_t 296*226dd6dbSJeff Roberson smr_default_advance(smr_t smr, smr_shared_t s) 297*226dd6dbSJeff Roberson { 298*226dd6dbSJeff Roberson smr_seq_t goal, s_rd_seq; 299*226dd6dbSJeff Roberson 300*226dd6dbSJeff Roberson CRITICAL_ASSERT(curthread); 301*226dd6dbSJeff Roberson KASSERT((zpcpu_get(smr)->c_flags & SMR_LAZY) == 0, 302*226dd6dbSJeff Roberson ("smr_default_advance: called with lazy smr.")); 303*226dd6dbSJeff Roberson 304*226dd6dbSJeff Roberson /* 305*226dd6dbSJeff Roberson * Load the current read seq before incrementing the goal so 306*226dd6dbSJeff Roberson * we are guaranteed it is always < goal. 307*226dd6dbSJeff Roberson */ 308*226dd6dbSJeff Roberson s_rd_seq = atomic_load_acq_int(&s->s_rd_seq); 309*226dd6dbSJeff Roberson goal = smr_shared_advance(s); 310*226dd6dbSJeff Roberson 311*226dd6dbSJeff Roberson /* 312*226dd6dbSJeff Roberson * Force a synchronization here if the goal is getting too 313*226dd6dbSJeff Roberson * far ahead of the read sequence number. This keeps the 314*226dd6dbSJeff Roberson * wrap detecting arithmetic working in pathological cases. 315*226dd6dbSJeff Roberson */ 316*226dd6dbSJeff Roberson if (SMR_SEQ_DELTA(goal, s_rd_seq) >= SMR_SEQ_MAX_DELTA) { 317*226dd6dbSJeff Roberson counter_u64_add(advance_wait, 1); 318*226dd6dbSJeff Roberson smr_wait(smr, goal - SMR_SEQ_MAX_ADVANCE); 319*226dd6dbSJeff Roberson } 320*226dd6dbSJeff Roberson counter_u64_add(advance, 1); 321*226dd6dbSJeff Roberson 322*226dd6dbSJeff Roberson return (goal); 323*226dd6dbSJeff Roberson } 324*226dd6dbSJeff Roberson 325*226dd6dbSJeff Roberson /* 326*226dd6dbSJeff Roberson * Deferred SMRs conditionally update s_wr_seq based on an 327*226dd6dbSJeff Roberson * cpu local interval count. 328*226dd6dbSJeff Roberson */ 329*226dd6dbSJeff Roberson static smr_seq_t 330*226dd6dbSJeff Roberson smr_deferred_advance(smr_t smr, smr_shared_t s, smr_t self) 331*226dd6dbSJeff Roberson { 332*226dd6dbSJeff Roberson 333*226dd6dbSJeff Roberson if (++self->c_deferred < self->c_limit) 334*226dd6dbSJeff Roberson return (smr_shared_current(s) + SMR_SEQ_INCR); 335*226dd6dbSJeff Roberson self->c_deferred = 0; 336*226dd6dbSJeff Roberson return (smr_default_advance(smr, s)); 337*226dd6dbSJeff Roberson } 338*226dd6dbSJeff Roberson 339*226dd6dbSJeff Roberson /* 340*226dd6dbSJeff Roberson * Advance the write sequence and return the value for use as the 341d4665eaaSJeff Roberson * wait goal. This guarantees that any changes made by the calling 342d4665eaaSJeff Roberson * thread prior to this call will be visible to all threads after 343d4665eaaSJeff Roberson * rd_seq meets or exceeds the return value. 344d4665eaaSJeff Roberson * 345d4665eaaSJeff Roberson * This function may busy loop if the readers are roughly 1 billion 346d4665eaaSJeff Roberson * sequence numbers behind the writers. 347*226dd6dbSJeff Roberson * 348*226dd6dbSJeff Roberson * Lazy SMRs will not busy loop and the wrap happens every 49.6 days 349*226dd6dbSJeff Roberson * at 1khz and 119 hours at 10khz. Readers can block for no longer 350*226dd6dbSJeff Roberson * than half of this for SMR_SEQ_ macros to continue working. 351d4665eaaSJeff Roberson */ 352d4665eaaSJeff Roberson smr_seq_t 353d4665eaaSJeff Roberson smr_advance(smr_t smr) 354d4665eaaSJeff Roberson { 355*226dd6dbSJeff Roberson smr_t self; 356d4665eaaSJeff Roberson smr_shared_t s; 357*226dd6dbSJeff Roberson smr_seq_t goal; 358*226dd6dbSJeff Roberson int flags; 359d4665eaaSJeff Roberson 360d4665eaaSJeff Roberson /* 361d4665eaaSJeff Roberson * It is illegal to enter while in an smr section. 362d4665eaaSJeff Roberson */ 363a4d50e49SJeff Roberson SMR_ASSERT_NOT_ENTERED(smr); 364d4665eaaSJeff Roberson 365d4665eaaSJeff Roberson /* 366d4665eaaSJeff Roberson * Modifications not done in a smr section need to be visible 367d4665eaaSJeff Roberson * before advancing the seq. 368d4665eaaSJeff Roberson */ 369d4665eaaSJeff Roberson atomic_thread_fence_rel(); 370d4665eaaSJeff Roberson 371bc650984SJeff Roberson critical_enter(); 372*226dd6dbSJeff Roberson /* Try to touch the line once. */ 373*226dd6dbSJeff Roberson self = zpcpu_get(smr); 374*226dd6dbSJeff Roberson s = self->c_shared; 375*226dd6dbSJeff Roberson flags = self->c_flags; 376bc650984SJeff Roberson goal = SMR_SEQ_INVALID; 377*226dd6dbSJeff Roberson if ((flags & (SMR_LAZY | SMR_DEFERRED)) == 0) 378*226dd6dbSJeff Roberson goal = smr_default_advance(smr, s); 379*226dd6dbSJeff Roberson else if ((flags & SMR_LAZY) != 0) 380*226dd6dbSJeff Roberson goal = smr_lazy_advance(smr, s); 381*226dd6dbSJeff Roberson else if ((flags & SMR_DEFERRED) != 0) 382*226dd6dbSJeff Roberson goal = smr_deferred_advance(smr, s, self); 383bc650984SJeff Roberson critical_exit(); 384*226dd6dbSJeff Roberson 385bc650984SJeff Roberson return (goal); 386bc650984SJeff Roberson } 387bc650984SJeff Roberson 388d4665eaaSJeff Roberson /* 389*226dd6dbSJeff Roberson * Poll to determine the currently observed sequence number on a cpu 390*226dd6dbSJeff Roberson * and spinwait if the 'wait' argument is true. 391d4665eaaSJeff Roberson */ 392*226dd6dbSJeff Roberson static smr_seq_t 393*226dd6dbSJeff Roberson smr_poll_cpu(smr_t c, smr_seq_t s_rd_seq, smr_seq_t goal, bool wait) 394d4665eaaSJeff Roberson { 395*226dd6dbSJeff Roberson smr_seq_t c_seq; 396d4665eaaSJeff Roberson 397d4665eaaSJeff Roberson c_seq = SMR_SEQ_INVALID; 398d4665eaaSJeff Roberson for (;;) { 399d4665eaaSJeff Roberson c_seq = atomic_load_int(&c->c_seq); 400d4665eaaSJeff Roberson if (c_seq == SMR_SEQ_INVALID) 401d4665eaaSJeff Roberson break; 402d4665eaaSJeff Roberson 403d4665eaaSJeff Roberson /* 404d4665eaaSJeff Roberson * There is a race described in smr.h:smr_enter that 405d4665eaaSJeff Roberson * can lead to a stale seq value but not stale data 406d4665eaaSJeff Roberson * access. If we find a value out of range here we 407d4665eaaSJeff Roberson * pin it to the current min to prevent it from 408d4665eaaSJeff Roberson * advancing until that stale section has expired. 409d4665eaaSJeff Roberson * 410d4665eaaSJeff Roberson * The race is created when a cpu loads the s_wr_seq 411d4665eaaSJeff Roberson * value in a local register and then another thread 412d4665eaaSJeff Roberson * advances s_wr_seq and calls smr_poll() which will 413d4665eaaSJeff Roberson * oberve no value yet in c_seq and advance s_rd_seq 414d4665eaaSJeff Roberson * up to s_wr_seq which is beyond the register 415d4665eaaSJeff Roberson * cached value. This is only likely to happen on 416d4665eaaSJeff Roberson * hypervisor or with a system management interrupt. 417d4665eaaSJeff Roberson */ 418d4665eaaSJeff Roberson if (SMR_SEQ_LT(c_seq, s_rd_seq)) 419d4665eaaSJeff Roberson c_seq = s_rd_seq; 420d4665eaaSJeff Roberson 421d4665eaaSJeff Roberson /* 422*226dd6dbSJeff Roberson * If the sequence number meets the goal we are done 423*226dd6dbSJeff Roberson * with this cpu. 424d4665eaaSJeff Roberson */ 425*226dd6dbSJeff Roberson if (SMR_SEQ_LEQ(goal, c_seq)) 426d4665eaaSJeff Roberson break; 427d4665eaaSJeff Roberson 428*226dd6dbSJeff Roberson if (!wait) 429d4665eaaSJeff Roberson break; 430d4665eaaSJeff Roberson cpu_spinwait(); 431d4665eaaSJeff Roberson } 432d4665eaaSJeff Roberson 433*226dd6dbSJeff Roberson return (c_seq); 434*226dd6dbSJeff Roberson } 435*226dd6dbSJeff Roberson 436*226dd6dbSJeff Roberson /* 437*226dd6dbSJeff Roberson * Loop until all cores have observed the goal sequence or have 438*226dd6dbSJeff Roberson * gone inactive. Returns the oldest sequence currently active; 439*226dd6dbSJeff Roberson * 440*226dd6dbSJeff Roberson * This function assumes a snapshot of sequence values has 441*226dd6dbSJeff Roberson * been obtained and validated by smr_poll(). 442*226dd6dbSJeff Roberson */ 443*226dd6dbSJeff Roberson static smr_seq_t 444*226dd6dbSJeff Roberson smr_poll_scan(smr_t smr, smr_shared_t s, smr_seq_t s_rd_seq, 445*226dd6dbSJeff Roberson smr_seq_t s_wr_seq, smr_seq_t goal, bool wait) 446*226dd6dbSJeff Roberson { 447*226dd6dbSJeff Roberson smr_seq_t rd_seq, c_seq; 448*226dd6dbSJeff Roberson int i; 449*226dd6dbSJeff Roberson 450*226dd6dbSJeff Roberson CRITICAL_ASSERT(curthread); 451*226dd6dbSJeff Roberson counter_u64_add_protected(poll_scan, 1); 452*226dd6dbSJeff Roberson 453*226dd6dbSJeff Roberson /* 454*226dd6dbSJeff Roberson * The read sequence can be no larger than the write sequence at 455*226dd6dbSJeff Roberson * the start of the poll. 456*226dd6dbSJeff Roberson */ 457*226dd6dbSJeff Roberson rd_seq = s_wr_seq; 458*226dd6dbSJeff Roberson CPU_FOREACH(i) { 459*226dd6dbSJeff Roberson /* 460*226dd6dbSJeff Roberson * Query the active sequence on this cpu. If we're not 461*226dd6dbSJeff Roberson * waiting and we don't meet the goal we will still scan 462*226dd6dbSJeff Roberson * the rest of the cpus to update s_rd_seq before returning 463*226dd6dbSJeff Roberson * failure. 464*226dd6dbSJeff Roberson */ 465*226dd6dbSJeff Roberson c_seq = smr_poll_cpu(zpcpu_get_cpu(smr, i), s_rd_seq, goal, 466*226dd6dbSJeff Roberson wait); 467*226dd6dbSJeff Roberson 468d4665eaaSJeff Roberson /* 469d4665eaaSJeff Roberson * Limit the minimum observed rd_seq whether we met the goal 470d4665eaaSJeff Roberson * or not. 471d4665eaaSJeff Roberson */ 472*226dd6dbSJeff Roberson if (c_seq != SMR_SEQ_INVALID) 473*226dd6dbSJeff Roberson rd_seq = SMR_SEQ_MIN(rd_seq, c_seq); 474d4665eaaSJeff Roberson } 475d4665eaaSJeff Roberson 476d4665eaaSJeff Roberson /* 477*226dd6dbSJeff Roberson * Advance the rd_seq as long as we observed a more recent value. 478d4665eaaSJeff Roberson */ 479d4665eaaSJeff Roberson s_rd_seq = atomic_load_int(&s->s_rd_seq); 480*226dd6dbSJeff Roberson if (SMR_SEQ_GEQ(rd_seq, s_rd_seq)) { 481*226dd6dbSJeff Roberson atomic_cmpset_int(&s->s_rd_seq, s_rd_seq, rd_seq); 482*226dd6dbSJeff Roberson s_rd_seq = rd_seq; 483*226dd6dbSJeff Roberson } 484d4665eaaSJeff Roberson 485*226dd6dbSJeff Roberson return (s_rd_seq); 486*226dd6dbSJeff Roberson } 487*226dd6dbSJeff Roberson 488*226dd6dbSJeff Roberson /* 489*226dd6dbSJeff Roberson * Poll to determine whether all readers have observed the 'goal' write 490*226dd6dbSJeff Roberson * sequence number. 491*226dd6dbSJeff Roberson * 492*226dd6dbSJeff Roberson * If wait is true this will spin until the goal is met. 493*226dd6dbSJeff Roberson * 494*226dd6dbSJeff Roberson * This routine will updated the minimum observed read sequence number in 495*226dd6dbSJeff Roberson * s_rd_seq if it does a scan. It may not do a scan if another call has 496*226dd6dbSJeff Roberson * advanced s_rd_seq beyond the callers goal already. 497*226dd6dbSJeff Roberson * 498*226dd6dbSJeff Roberson * Returns true if the goal is met and false if not. 499*226dd6dbSJeff Roberson */ 500*226dd6dbSJeff Roberson bool 501*226dd6dbSJeff Roberson smr_poll(smr_t smr, smr_seq_t goal, bool wait) 502*226dd6dbSJeff Roberson { 503*226dd6dbSJeff Roberson smr_shared_t s; 504*226dd6dbSJeff Roberson smr_t self; 505*226dd6dbSJeff Roberson smr_seq_t s_wr_seq, s_rd_seq; 506*226dd6dbSJeff Roberson smr_delta_t delta; 507*226dd6dbSJeff Roberson int flags; 508*226dd6dbSJeff Roberson bool success; 509*226dd6dbSJeff Roberson 510*226dd6dbSJeff Roberson /* 511*226dd6dbSJeff Roberson * It is illegal to enter while in an smr section. 512*226dd6dbSJeff Roberson */ 513*226dd6dbSJeff Roberson KASSERT(!wait || !SMR_ENTERED(smr), 514*226dd6dbSJeff Roberson ("smr_poll: Blocking not allowed in a SMR section.")); 515*226dd6dbSJeff Roberson KASSERT(!wait || (zpcpu_get(smr)->c_flags & SMR_LAZY) == 0, 516*226dd6dbSJeff Roberson ("smr_poll: Blocking not allowed on lazy smrs.")); 517*226dd6dbSJeff Roberson 518*226dd6dbSJeff Roberson /* 519*226dd6dbSJeff Roberson * Use a critical section so that we can avoid ABA races 520*226dd6dbSJeff Roberson * caused by long preemption sleeps. 521*226dd6dbSJeff Roberson */ 522*226dd6dbSJeff Roberson success = true; 523*226dd6dbSJeff Roberson critical_enter(); 524*226dd6dbSJeff Roberson /* Attempt to load from self only once. */ 525*226dd6dbSJeff Roberson self = zpcpu_get(smr); 526*226dd6dbSJeff Roberson s = self->c_shared; 527*226dd6dbSJeff Roberson flags = self->c_flags; 528*226dd6dbSJeff Roberson counter_u64_add_protected(poll, 1); 529*226dd6dbSJeff Roberson 530*226dd6dbSJeff Roberson /* 531*226dd6dbSJeff Roberson * Conditionally advance the lazy write clock on any writer 532*226dd6dbSJeff Roberson * activity. This may reset s_rd_seq. 533*226dd6dbSJeff Roberson */ 534*226dd6dbSJeff Roberson if ((flags & SMR_LAZY) != 0) 535*226dd6dbSJeff Roberson smr_lazy_advance(smr, s); 536*226dd6dbSJeff Roberson 537*226dd6dbSJeff Roberson /* 538*226dd6dbSJeff Roberson * Acquire barrier loads s_wr_seq after s_rd_seq so that we can not 539*226dd6dbSJeff Roberson * observe an updated read sequence that is larger than write. 540*226dd6dbSJeff Roberson */ 541*226dd6dbSJeff Roberson s_rd_seq = atomic_load_acq_int(&s->s_rd_seq); 542*226dd6dbSJeff Roberson 543*226dd6dbSJeff Roberson /* 544*226dd6dbSJeff Roberson * If we have already observed the sequence number we can immediately 545*226dd6dbSJeff Roberson * return success. Most polls should meet this criterion. 546*226dd6dbSJeff Roberson */ 547*226dd6dbSJeff Roberson if (SMR_SEQ_LEQ(goal, s_rd_seq)) 548*226dd6dbSJeff Roberson goto out; 549*226dd6dbSJeff Roberson 550*226dd6dbSJeff Roberson /* 551*226dd6dbSJeff Roberson * wr_seq must be loaded prior to any c_seq value so that a 552*226dd6dbSJeff Roberson * stale c_seq can only reference time after this wr_seq. 553*226dd6dbSJeff Roberson */ 554*226dd6dbSJeff Roberson s_wr_seq = atomic_load_acq_int(&s->s_wr_seq); 555*226dd6dbSJeff Roberson 556*226dd6dbSJeff Roberson /* 557*226dd6dbSJeff Roberson * This is the distance from s_wr_seq to goal. Positive values 558*226dd6dbSJeff Roberson * are in the future. 559*226dd6dbSJeff Roberson */ 560*226dd6dbSJeff Roberson delta = SMR_SEQ_DELTA(goal, s_wr_seq); 561*226dd6dbSJeff Roberson 562*226dd6dbSJeff Roberson /* 563*226dd6dbSJeff Roberson * Detect a stale wr_seq. 564*226dd6dbSJeff Roberson * 565*226dd6dbSJeff Roberson * This goal may have come from a deferred advance or a lazy 566*226dd6dbSJeff Roberson * smr. If we are not blocking we can not succeed but the 567*226dd6dbSJeff Roberson * sequence number is valid. 568*226dd6dbSJeff Roberson */ 569*226dd6dbSJeff Roberson if (delta > 0 && delta <= SMR_SEQ_MAX_ADVANCE && 570*226dd6dbSJeff Roberson (flags & (SMR_LAZY | SMR_DEFERRED)) != 0) { 571*226dd6dbSJeff Roberson if (!wait) { 572*226dd6dbSJeff Roberson success = false; 573*226dd6dbSJeff Roberson goto out; 574*226dd6dbSJeff Roberson } 575*226dd6dbSJeff Roberson /* LAZY is always !wait. */ 576*226dd6dbSJeff Roberson s_wr_seq = smr_shared_advance(s); 577*226dd6dbSJeff Roberson delta = 0; 578*226dd6dbSJeff Roberson } 579*226dd6dbSJeff Roberson 580*226dd6dbSJeff Roberson /* 581*226dd6dbSJeff Roberson * Detect an invalid goal. 582*226dd6dbSJeff Roberson * 583*226dd6dbSJeff Roberson * The goal must be in the range of s_wr_seq >= goal >= s_rd_seq for 584*226dd6dbSJeff Roberson * it to be valid. If it is not then the caller held on to it and 585*226dd6dbSJeff Roberson * the integer wrapped. If we wrapped back within range the caller 586*226dd6dbSJeff Roberson * will harmlessly scan. 587*226dd6dbSJeff Roberson */ 588*226dd6dbSJeff Roberson if (delta > 0) 589*226dd6dbSJeff Roberson goto out; 590*226dd6dbSJeff Roberson 591*226dd6dbSJeff Roberson /* Determine the lowest visible sequence number. */ 592*226dd6dbSJeff Roberson s_rd_seq = smr_poll_scan(smr, s, s_rd_seq, s_wr_seq, goal, wait); 593*226dd6dbSJeff Roberson success = SMR_SEQ_LEQ(goal, s_rd_seq); 594d4665eaaSJeff Roberson out: 595*226dd6dbSJeff Roberson if (!success) 596*226dd6dbSJeff Roberson counter_u64_add_protected(poll_fail, 1); 597d4665eaaSJeff Roberson critical_exit(); 598d4665eaaSJeff Roberson 599915c367eSJeff Roberson /* 600915c367eSJeff Roberson * Serialize with smr_advance()/smr_exit(). The caller is now free 601915c367eSJeff Roberson * to modify memory as expected. 602915c367eSJeff Roberson */ 603915c367eSJeff Roberson atomic_thread_fence_acq(); 604915c367eSJeff Roberson 605d4665eaaSJeff Roberson return (success); 606d4665eaaSJeff Roberson } 607d4665eaaSJeff Roberson 608d4665eaaSJeff Roberson smr_t 609*226dd6dbSJeff Roberson smr_create(const char *name, int limit, int flags) 610d4665eaaSJeff Roberson { 611d4665eaaSJeff Roberson smr_t smr, c; 612d4665eaaSJeff Roberson smr_shared_t s; 613d4665eaaSJeff Roberson int i; 614d4665eaaSJeff Roberson 615d4665eaaSJeff Roberson s = uma_zalloc(smr_shared_zone, M_WAITOK); 6161f2a6b85SJeff Roberson smr = uma_zalloc_pcpu(smr_zone, M_WAITOK); 617d4665eaaSJeff Roberson 618d4665eaaSJeff Roberson s->s_name = name; 619*226dd6dbSJeff Roberson if ((flags & SMR_LAZY) == 0) 620d4665eaaSJeff Roberson s->s_rd_seq = s->s_wr_seq = SMR_SEQ_INIT; 621*226dd6dbSJeff Roberson else 622*226dd6dbSJeff Roberson s->s_rd_seq = s->s_wr_seq = ticks; 623d4665eaaSJeff Roberson 624d4665eaaSJeff Roberson /* Initialize all CPUS, not just those running. */ 625d4665eaaSJeff Roberson for (i = 0; i <= mp_maxid; i++) { 626d4665eaaSJeff Roberson c = zpcpu_get_cpu(smr, i); 627d4665eaaSJeff Roberson c->c_seq = SMR_SEQ_INVALID; 628d4665eaaSJeff Roberson c->c_shared = s; 629*226dd6dbSJeff Roberson c->c_deferred = 0; 630*226dd6dbSJeff Roberson c->c_limit = limit; 631*226dd6dbSJeff Roberson c->c_flags = flags; 632d4665eaaSJeff Roberson } 633d4665eaaSJeff Roberson atomic_thread_fence_seq_cst(); 634d4665eaaSJeff Roberson 635d4665eaaSJeff Roberson return (smr); 636d4665eaaSJeff Roberson } 637d4665eaaSJeff Roberson 638d4665eaaSJeff Roberson void 639d4665eaaSJeff Roberson smr_destroy(smr_t smr) 640d4665eaaSJeff Roberson { 641d4665eaaSJeff Roberson 642d4665eaaSJeff Roberson smr_synchronize(smr); 643d4665eaaSJeff Roberson uma_zfree(smr_shared_zone, smr->c_shared); 6441f2a6b85SJeff Roberson uma_zfree_pcpu(smr_zone, smr); 645d4665eaaSJeff Roberson } 646d4665eaaSJeff Roberson 647d4665eaaSJeff Roberson /* 648d4665eaaSJeff Roberson * Initialize the UMA slab zone. 649d4665eaaSJeff Roberson */ 650d4665eaaSJeff Roberson void 651d4665eaaSJeff Roberson smr_init(void) 652d4665eaaSJeff Roberson { 653d4665eaaSJeff Roberson 654d4665eaaSJeff Roberson smr_shared_zone = uma_zcreate("SMR SHARED", sizeof(struct smr_shared), 655d4665eaaSJeff Roberson NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, 0); 656d4665eaaSJeff Roberson smr_zone = uma_zcreate("SMR CPU", sizeof(struct smr), 657d4665eaaSJeff Roberson NULL, NULL, NULL, NULL, (CACHE_LINE_SIZE * 2) - 1, UMA_ZONE_PCPU); 658d4665eaaSJeff Roberson } 6598d7f16a5SJeff Roberson 6608d7f16a5SJeff Roberson static void 6618d7f16a5SJeff Roberson smr_init_counters(void *unused) 6628d7f16a5SJeff Roberson { 6638d7f16a5SJeff Roberson 6648d7f16a5SJeff Roberson advance = counter_u64_alloc(M_WAITOK); 6658d7f16a5SJeff Roberson advance_wait = counter_u64_alloc(M_WAITOK); 6668d7f16a5SJeff Roberson poll = counter_u64_alloc(M_WAITOK); 6678d7f16a5SJeff Roberson poll_scan = counter_u64_alloc(M_WAITOK); 668*226dd6dbSJeff Roberson poll_fail = counter_u64_alloc(M_WAITOK); 6698d7f16a5SJeff Roberson } 6708d7f16a5SJeff Roberson SYSINIT(smr_counters, SI_SUB_CPU, SI_ORDER_ANY, smr_init_counters, NULL); 671