[PATCH v7] eal: add seqlock

[Mattias Rönnblom]

On 2022-05-15 14:39, Mattias Rönnblom wrote:
> 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?

Since I received no comments on this, I'll go ahead and make a v8, where 
the seqcount and seqlock structs and functions are 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>
>