> A sequence lock (seqlock) is synchronization primitive which allows > for data-race free, low-overhead, high-frequency reads, especially for > data structures shared across many cores and which are updated > relatively infrequently. > > A seqlock permits multiple parallel readers. The variant of seqlock > implemented in this patch supports multiple writers as well. A > spinlock is used for writer-writer serialization. > > To avoid resource reclamation and other issues, the data protected by > a seqlock is best off being self-contained (i.e., no pointers [except > to constant data]). > > One way to think about seqlocks is that they provide means to perform > atomic operations on data objects larger what the native atomic > machine instructions allow for. > > DPDK seqlocks are not preemption safe on the writer side. A thread > preemption affects performance, not correctness. > > A seqlock contains a sequence number, which can be thought of as the > generation of the data it protects. > > A reader will > 1. Load the sequence number (sn). > 2. Load, in arbitrary order, the seqlock-protected data. > 3. Load the sn again. > 4. Check if the first and second sn are equal, and even numbered. > If they are not, discard the loaded data, and restart from 1. > > The first three steps need to be ordered using suitable memory fences. > > A writer will > 1. Take the spinlock, to serialize writer access. > 2. Load the sn. > 3. Store the original sn + 1 as the new sn. > 4. Perform load and stores to the seqlock-protected data. > 5. Store the original sn + 2 as the new sn. > 6. Release the spinlock. > > Proper memory fencing is required to make sure the first sn store, the > data stores, and the second sn store appear to the reader in the > mentioned order. > > The sn loads and stores must be atomic, but the data loads and stores > need not be. > > The original seqlock design and implementation was done by Stephen > Hemminger. This is an independent implementation, using C11 atomics. > > For more information on seqlocks, see > https://en.wikipedia.org/wiki/Seqlock > > PATCH v4: > * Reverted to Linux kernel style naming on the read side. > * Bail out early from the retry function if an odd sequence > number is encountered. > * Added experimental warnings in the API documentation. > * Static initializer now uses named field initialization. > * Various tweaks to API documentation (including the example). > > PATCH v3: > * Renamed both read and write-side critical section begin/end functions > to better match rwlock naming, per Ola Liljedahl's suggestion. > * Added 'extern "C"' guards for C++ compatibility. > * Refer to the main lcore as the main lcore, and nothing else. > > PATCH v2: > * Skip instead of fail unit test in case too few lcores are available. > * Use main lcore for testing, reducing the minimum number of lcores > required to run the unit tests to four. > * Consistently refer to sn field as the "sequence number" in the > documentation. > * Fixed spelling mistakes in documentation. > > Updates since RFC: > * Added API documentation. > * Added link to Wikipedia article in the commit message. > * Changed seqlock sequence number field from uint64_t (which was > overkill) to uint32_t. The sn type needs to be sufficiently large > to assure no reader will read a sn, access the data, and then read > the same sn, but the sn has been incremented enough times to have > wrapped during the read, and arrived back at the original sn. > * Added RTE_SEQLOCK_INITIALIZER macro for static initialization. > * Removed the rte_seqlock struct + separate rte_seqlock_t typedef > with an anonymous struct typedef:ed to rte_seqlock_t. > > Acked-by: Morten Brørup <m...@smartsharesystems.com> > Reviewed-by: Ola Liljedahl <ola.liljed...@arm.com> > Signed-off-by: Mattias Rönnblom <mattias.ronnb...@ericsson.com> > ---
Acked-by: Konstantin Ananyev <konstantin.anan...@intel.com> > -- > 2.25.1
