[PATCH v6] eal: add seqlock

[Stephen Hemminger]

On Sun, 8 May 2022 14:12:42 +0200
Mattias Rönnblom <mattias.ronnblom at ericsson.com> wrote:
> A sequence lock (seqlock) is a synchronization primitive which allows
> for data-race free, low-overhead, high-frequency reads, suitable 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 than 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

I think would be good to have the sequence count (read side only) like
the kernel and sequence lock (sequence count + spinlock) as separate things.

That way the application could use sequence count + ticket lock if it
needed to scale to more writers.

> diff --git a/lib/eal/common/rte_seqlock.c b/lib/eal/common/rte_seqlock.c
> new file mode 100644
> index 0000000000..d4fe648799
> --- /dev/null
> +++ b/lib/eal/common/rte_seqlock.c
> @@ -0,0 +1,12 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2022 Ericsson AB
> + */
> +
> +#include <rte_seqlock.h>
> +
> +void
> +rte_seqlock_init(rte_seqlock_t *seqlock)
> +{
> +	seqlock->sn = 0;
> +	rte_spinlock_init(&seqlock->lock);
> +}

So small, worth just making inline?