[PATCH v7] eal: add seqlock

[Mattias Rönnblom]

On 2022-05-15 14:24, Mattias Rönnblom 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. A spinlock is used to
> serialize writers. In cases where there is only a single writer, or
> writer-writer synchronization is done by some external means, the
> "raw" sequence counter type (and accompanying rte_seqcount_*()
> functions) may be used instead.
> 
> 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 (and the underlying sequence counters) 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
> 
> ---
> 

A note to previous reviewers: This split of seqlock into 
seqcount+seqlock assumes that the spinlock lock/unlock calls provided no 
additional functionality in regards to MT safety, than writer-writer 
serialization. I believe that to be the case, but I would feel more 
comfortable if someone else re-reviewed this code with this in mind.

Two questions remain:

1) Should the seqlock and the seqcount reside in different header files?
2) Is it it good enough to provided only a spinlock-protected seqlock?

Question 1 I don't really have an opinion on. Both ways seems perfectly 
reasonable to me. I noted Morten wanted a split, and left to my own 
devices this is probably what I would do as well.

I think the answer to 2 is yes. We can provide other variants in the 
future, would the need arise.

<snip>