[PATCH v6] eal: add seqlock

[Mattias Rönnblom]

On 2022-05-08 18:10, Stephen Hemminger wrote:
> 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.
> 

Sounds reasonable. Would that be something like:

typedef struct {
	uint32_t sn;
} rte_seqlock_t;

rte_seqlock_read_begin()
rte_seqlock_read_retry()
rte_seqlock_write_begin()
rte_seqlock_write_end()

typedef struct {
	rte_seqlock_t seqlock;
	rte_spinlock_t wlock;
} rte_<something>_t;

rte_<something>_read_begin()
rte_<something>_read_retry()
rte_<something>_write_lock()
rte_<something>_write_unlock()

or are you suggesting removing the spinlock altogether, and leave 
writer-side synchronization to the application (at least in this DPDK 
release)?

>> 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?

I don't think so, but it is small. Especially if rte_spinlock_init() now 
goes away. :)