Skip to contentSkip to conversation

eal: add seqlock

PATCH Superseded Mattias Rönnblom 6 participants 20 messages May 15, 2022 – Jun 7, 2022 1 message not in the archive Arm/Amlogic Meson SoC support

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

PATCH v7 1/1 eal: add seqlock

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

---

PATCH v7
* Factor out the sequence number into a separate type rte_seqcount_t.

PATCH v6:
* Check for failed memory allocations in unit test.
* Fix underflow issue in test case for small RTE_LCORE_MAX values.
* Fix test case memory leak.

PATCH v5:
* Add sequence lock section to MAINTAINERS.
* Add entry in the release notes.
* Add seqlock reference in the API index.
* Fix meson build file indentation.
* Use "increment" to describe how a writer changes the sequence number.
* Remove compiler barriers from seqlock test.
* Use appropriate macros (e.g., TEST_SUCCESS) for test return values.

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.

---
 MAINTAINERS                            |   5 +
 app/test/meson.build                   |   2 +
 app/test/test_seqlock.c                | 190 ++++++++++
 doc/api/doxy-api-index.md              |   1 +
 doc/guides/rel_notes/release_22_07.rst |  14 +
 lib/eal/common/meson.build             |   1 +
 lib/eal/common/rte_seqlock.c           |  18 +
 lib/eal/include/meson.build            |   1 +
 lib/eal/include/rte_seqlock.h          | 464 +++++++++++++++++++++++++
 lib/eal/version.map                    |   4 +
 10 files changed, 700 insertions(+)
 create mode 100644 app/test/test_seqlock.c
 create mode 100644 lib/eal/common/rte_seqlock.c
 create mode 100644 lib/eal/include/rte_seqlock.h
MAINTAINERS +5 -0
index 7c4f541dba..2804d8136c 100644
@@ -262,6 +262,11 @@ M: Joyce Kong <[email protected]>
 F: lib/eal/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Sequence Lock
+M: Mattias Rönnblom <[email protected]>
+F: lib/eal/include/rte_seqlock.h
+F: app/test/test_seqlock.c
+
 Pseudo-random Number Generation
 M: Mattias Rönnblom <[email protected]>
 F: lib/eal/include/rte_random.h
app/test/meson.build +2 -0
index 5fc1dd1b7b..5e418e8766 100644
@@ -125,6 +125,7 @@ test_sources = files(
         'test_rwlock.c',
         'test_sched.c',
         'test_security.c',
+        'test_seqlock.c',
         'test_service_cores.c',
         'test_spinlock.c',
         'test_stack.c',
@@ -214,6 +215,7 @@ fast_tests = [
         ['rwlock_rde_wro_autotest', true],
         ['sched_autotest', true],
         ['security_autotest', false],
+        ['seqlock_autotest', true],
         ['spinlock_autotest', true],
         ['stack_autotest', false],
         ['stack_lf_autotest', false],
app/test/test_seqlock.c new file +190 -0

190 lines not on this page · raw message

doc/api/doxy-api-index.md +1 -0
index 4245b9635c..f23e33ae30 100644
@@ -77,6 +77,7 @@ The public API headers are grouped by topics:
   [rwlock]             (@ref rte_rwlock.h),
   [spinlock]           (@ref rte_spinlock.h),
   [ticketlock]         (@ref rte_ticketlock.h),
+  [seqlock]            (@ref rte_seqlock.h),
   [RCU]                (@ref rte_rcu_qsbr.h)
 
 - **CPU arch**:
doc/guides/rel_notes/release_22_07.rst +14 -0
index 88d6e96cc1..d2f7bafe7b 100644
@@ -55,6 +55,20 @@ New Features
      Also, make sure to start the actual text at the margin.
      =======================================================
 
+* **Added Sequence Lock.**
+
+  Added a new synchronization primitive: the sequence lock
+  (seqlock). A seqlock allows for low overhead, parallel reads. The
+  DPDK seqlock uses a spinlock to serialize multiple writing threads.
+
+  In particular, seqlocks are useful for protecting data structures
+  which are read very frequently, by threads running on many different
+  cores, and modified relatively infrequently.
+
+  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.
+
 * **Updated Intel iavf driver.**
 
   * Added Tx QoS queue rate limitation support.
lib/eal/common/meson.build +1 -0
index 917758cc65..3c896711e5 100644
@@ -35,6 +35,7 @@ sources += files(
         'rte_malloc.c',
         'rte_random.c',
         'rte_reciprocal.c',
+        'rte_seqlock.c',
         'rte_service.c',
         'rte_version.c',
 )
lib/eal/common/rte_seqlock.c new file +18 -0
new file mode 100644
index 0000000000..370ff9bbb2
@@ -0,0 +1,18 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Ericsson AB
+ */
+
+#include <rte_seqlock.h>
+
+void
+rte_seqcount_init(rte_seqcount_t *seqcount)
+{
+	seqcount->sn = 0;
+}
+
+void
+rte_seqlock_init(rte_seqlock_t *seqlock)
+{
+	rte_seqcount_init(&seqlock->count);
+	rte_spinlock_init(&seqlock->lock);
+}
lib/eal/include/meson.build +1 -0
index 9700494816..48df5f1a21 100644
@@ -36,6 +36,7 @@ headers += files(
         'rte_per_lcore.h',
         'rte_random.h',
         'rte_reciprocal.h',
+        'rte_seqlock.h',
         'rte_service.h',
         'rte_service_component.h',
         'rte_string_fns.h',
lib/eal/include/rte_seqlock.h new file +464 -0

464 lines not on this page · raw message

lib/eal/version.map +4 -0
index b53eeb30d7..19efc13d63 100644
@@ -420,6 +420,10 @@ EXPERIMENTAL {
 	rte_intr_instance_free;
 	rte_intr_type_get;
 	rte_intr_type_set;
+
+	# added in 22.07
+	rte_seqcount_init;
+	rte_seqlock_init;
 };
 
 INTERNAL {
Signature · 1 line
2.25.1
#2 lore raw
Quoted 50 lines · Mattias Rönnblom

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.

Quoted 8 lines

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>

#3 lore raw
Quoted 5 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Sunday, 15 May 2022 14.40

Two questions remain:

Quoted 7 lines

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.

Argument for separate header files: If we add e.g. a rte_seqticketlock_t later, it should be able to include the rte_seqcount_t header file without also getting the contextually irrelevant rte_seqlock_t type and functions.

I don't feel strongly about this.

Quoted 3 lines

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

Agree.

Quoted 2 lines

<snip>

Please move the header files from /lib/eal/include to /lib/eal/include/generic, where the other lock header files reside.

#4 lore raw
Quoted 21 lines · Morten Brørup
Quoted 5 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Sunday, 15 May 2022 14.40

Two questions remain:

Quoted 7 lines

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.

Argument for separate header files: If we add e.g. a rte_seqticketlock_t later, it should be able to include the rte_seqcount_t header file without also getting the contextually irrelevant rte_seqlock_t type and functions.

I don't feel strongly about this.

Quoted 3 lines

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

Quoted 8 lines

Agree.

Quoted 2 lines

<snip>

Please move the header files from /lib/eal/include to /lib/eal/include/generic, where the other lock header files reside.

My guess would be that the lib/eal/include/generic directory is where the generic implementations of APIs for which there also exist machine-specific implementations go. The seqlock is not an example of such.

#5 lore raw
Quoted 36 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Sunday, 15 May 2022 19.54

Quoted 8 lines · Morten Brørup
Quoted 8 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Sunday, 15 May 2022 14.40

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?

Quoted 2 lines
Quoted 2 lines

Question 1 I don't really have an opinion on. Both ways seems

perfectly

Quoted 4 lines
Quoted 2 lines

reasonable to me. I noted Morten wanted a split, and left to my own devices this is probably what I would do as well.

Argument for separate header files: If we add e.g. a

rte_seqticketlock_t later, it should be able to include the rte_seqcount_t header file without also getting the contextually irrelevant rte_seqlock_t type and functions.

Quoted 7 lines

I don't feel strongly about this.

Quoted 3 lines

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

Quoted 6 lines

Agree.

Quoted 2 lines

<snip>

Please move the header files from /lib/eal/include to

Quoted 8 lines

/lib/eal/include/generic, where the other lock header files reside.

Quoted 2 lines

My guess would be that the lib/eal/include/generic directory is where the generic implementations of APIs for which there also exist machine-specific implementations go. The seqlock is not an example of such.

My guess would be the same. However, it is not documented what goes where in the DPDK tree structure, and the community seems to have a preference for following conventions rather than doing things right. So just turn off your brain and be a lemming for a second! ;-)

Or try your luck. You have my support for the patch regardless. :-)

<rant>
I think that most of the EAL has grown into a huge pile of monolithic spaghetti, with very little modularity. E.g. I suggested refactoring and fixing the mempool cache, but could not gather traction. Instead, an increasing amount of the mempool library's implementation details are being promoted from internal to public, and its internal code is being copy-pasted into other modules, so they can bypass both the mbuf and mempool libraries when allocating and freeing mbufs. </rant>

#6 lore raw
In reply to Mattias Rönnblom

(Resent with Konstantin's new email address.)

Quoted 5 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Sunday, 15 May 2022 14.40

Two questions remain:

Quoted 7 lines

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.

Argument for separate header files: If we add e.g. a rte_seqticketlock_t later, it should be able to include the rte_seqcount_t header file without also getting the contextually irrelevant rte_seqlock_t type and functions.

I don't feel strongly about this.

Quoted 3 lines

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

Agree.

Quoted 2 lines

<snip>

Please move the header files from /lib/eal/include to /lib/eal/include/generic, where the other lock header files reside.

#7 lore raw
In reply to Mattias Rönnblom
Quoted 66 lines · Mattias Rönnblom
Quoted 50 lines · Mattias Rönnblom

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.

Quoted 8 lines

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.

Quoted 3 lines

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.

Quoted 11 lines

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>

#8 lore raw

PATCH v8 1/1 eal: add seqlock

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

---

PATCH v8:
* Move the sequence counter into a separate header file.
* Move the initialization code into the header files and eliminate the tiny rte_seqlock.c.

PATCH v7:
* Factor out the sequence number into a separate type rte_seqcount_t.

PATCH v6:
* Check for failed memory allocations in unit test.
* Fix underflow issue in test case for small RTE_LCORE_MAX values.
* Fix test case memory leak.

PATCH v5:
* Add sequence lock section to MAINTAINERS.
* Add entry in the release notes.
* Add seqlock reference in the API index.
* Fix meson build file indentation.
* Use "increment" to describe how a writer changes the sequence number.
* Remove compiler barriers from seqlock test.
* Use appropriate macros (e.g., TEST_SUCCESS) for test return values.

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.

---
 MAINTAINERS                            |   6 +
 app/test/meson.build                   |   2 +
 app/test/test_seqlock.c                | 190 +++++++++++++++++++
 doc/api/doxy-api-index.md              |   2 +
 doc/guides/rel_notes/release_22_07.rst |  18 ++
 lib/eal/include/meson.build            |   2 +
 lib/eal/include/rte_seqcount.h         | 251 ++++++++++++++++++++++++
 lib/eal/include/rte_seqlock.h          | 252 +++++++++++++++++++++++++
 8 files changed, 723 insertions(+)
 create mode 100644 app/test/test_seqlock.c
 create mode 100644 lib/eal/include/rte_seqcount.h
 create mode 100644 lib/eal/include/rte_seqlock.h
MAINTAINERS +6 -0
index 17a0559ee7..458ea7e47c 100644
@@ -263,6 +263,12 @@ M: Joyce Kong <[email protected]>
 F: lib/eal/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Sequence Lock
+M: Mattias Rönnblom <[email protected]>
+F: lib/eal/include/rte_seqcount.h
+F: lib/eal/include/rte_seqlock.h
+F: app/test/test_seqlock.c
+
 Pseudo-random Number Generation
 M: Mattias Rönnblom <[email protected]>
 F: lib/eal/include/rte_random.h
app/test/meson.build +2 -0
index 15591ce5cf..48344e2071 100644
@@ -125,6 +125,7 @@ test_sources = files(
         'test_rwlock.c',
         'test_sched.c',
         'test_security.c',
+        'test_seqlock.c',
         'test_service_cores.c',
         'test_spinlock.c',
         'test_stack.c',
@@ -216,6 +217,7 @@ fast_tests = [
         ['rwlock_rde_wro_autotest', true, true],
         ['sched_autotest', true, true],
         ['security_autotest', false, true],
+        ['seqlock_autotest', true, true],
         ['spinlock_autotest', true, true],
         ['stack_autotest', false, true],
         ['stack_lf_autotest', false, true],
app/test/test_seqlock.c new file +190 -0

190 lines not on this page · raw message

doc/api/doxy-api-index.md +2 -0
index 2b78d796ea..6dd219ef0d 100644
@@ -78,6 +78,8 @@ The public API headers are grouped by topics:
   [rwlock]             (@ref rte_rwlock.h),
   [spinlock]           (@ref rte_spinlock.h),
   [ticketlock]         (@ref rte_ticketlock.h),
+  [seqlock]            (@ref rte_seqlock.h),
+  [seqcount]           (@ref rte_seqcount.h),
   [RCU]                (@ref rte_rcu_qsbr.h)
 
 - **CPU arch**:
doc/guides/rel_notes/release_22_07.rst +18 -0
index e49cacecef..9c48769171 100644
@@ -60,6 +60,24 @@ New Features
   Added an API which can get the number of in-flight packets in
   vhost async data path without using lock.
 
+* **Added Sequence Lock.**
+
+  Added a new synchronization primitive: the sequence lock
+  (seqlock). A seqlock allows for low overhead, parallel reads. The
+  DPDK seqlock uses a spinlock to serialize multiple writing threads.
+
+  In particular, seqlocks are useful for protecting data structures
+  which are read very frequently, by threads running on many different
+  cores, and modified relatively infrequently.
+
+  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.
+
+  In cases where there is only a single writer, or writer-writer
+  synchronization is performed by some means external to the seqlock,
+  direct use of the underlying sequence counter may be more suitable.
+
 * **Updated Intel iavf driver.**
 
   * Added Tx QoS queue rate limitation support.
lib/eal/include/meson.build +2 -0
index 9700494816..40ebb5b63d 100644
@@ -36,6 +36,8 @@ headers += files(
         'rte_per_lcore.h',
         'rte_random.h',
         'rte_reciprocal.h',
+        'rte_seqcount.h',
+        'rte_seqlock.h',
         'rte_service.h',
         'rte_service_component.h',
         'rte_string_fns.h',
lib/eal/include/rte_seqcount.h new file +251 -0

251 lines not on this page · raw message

lib/eal/include/rte_seqlock.h new file +252 -0

252 lines not on this page · raw message

Signature · 1 line
2.25.1
#9 lore raw

PATCH v9 1/1 eal: add seqlock

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

---

PATCH v9:
* Include <rte_compat.h> for __rte_experimental. The failure to do so caused build failures on 32-bit ARM.

PATCH v8:
* Move the sequence counter into a separate header file.
* Move the initialization code into the header files and eliminate the tiny rte_seqlock.c.

PATCH v7:
* Factor out the sequence number into a separate type rte_seqcount_t.

PATCH v6:
* Check for failed memory allocations in unit test.
* Fix underflow issue in test case for small RTE_LCORE_MAX values.
* Fix test case memory leak.

PATCH v5:
* Add sequence lock section to MAINTAINERS.
* Add entry in the release notes.
* Add seqlock reference in the API index.
* Fix meson build file indentation.
* Use "increment" to describe how a writer changes the sequence number.
* Remove compiler barriers from seqlock test.
* Use appropriate macros (e.g., TEST_SUCCESS) for test return values.

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.

---
 MAINTAINERS                            |   6 +
 app/test/meson.build                   |   2 +
 app/test/test_seqlock.c                | 190 +++++++++++++++++++
 doc/api/doxy-api-index.md              |   2 +
 doc/guides/rel_notes/release_22_07.rst |  18 ++
 lib/eal/include/meson.build            |   2 +
 lib/eal/include/rte_seqcount.h         | 252 ++++++++++++++++++++++++
 lib/eal/include/rte_seqlock.h          | 253 +++++++++++++++++++++++++
 8 files changed, 725 insertions(+)
 create mode 100644 app/test/test_seqlock.c
 create mode 100644 lib/eal/include/rte_seqcount.h
 create mode 100644 lib/eal/include/rte_seqlock.h
MAINTAINERS +6 -0
index 17a0559ee7..458ea7e47c 100644
@@ -263,6 +263,12 @@ M: Joyce Kong <[email protected]>
 F: lib/eal/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Sequence Lock
+M: Mattias Rönnblom <[email protected]>
+F: lib/eal/include/rte_seqcount.h
+F: lib/eal/include/rte_seqlock.h
+F: app/test/test_seqlock.c
+
 Pseudo-random Number Generation
 M: Mattias Rönnblom <[email protected]>
 F: lib/eal/include/rte_random.h
app/test/meson.build +2 -0
index 15591ce5cf..48344e2071 100644
@@ -125,6 +125,7 @@ test_sources = files(
         'test_rwlock.c',
         'test_sched.c',
         'test_security.c',
+        'test_seqlock.c',
         'test_service_cores.c',
         'test_spinlock.c',
         'test_stack.c',
@@ -216,6 +217,7 @@ fast_tests = [
         ['rwlock_rde_wro_autotest', true, true],
         ['sched_autotest', true, true],
         ['security_autotest', false, true],
+        ['seqlock_autotest', true, true],
         ['spinlock_autotest', true, true],
         ['stack_autotest', false, true],
         ['stack_lf_autotest', false, true],
app/test/test_seqlock.c new file +190 -0

190 lines not on this page · raw message

doc/api/doxy-api-index.md +2 -0
index 2b78d796ea..6dd219ef0d 100644
@@ -78,6 +78,8 @@ The public API headers are grouped by topics:
   [rwlock]             (@ref rte_rwlock.h),
   [spinlock]           (@ref rte_spinlock.h),
   [ticketlock]         (@ref rte_ticketlock.h),
+  [seqlock]            (@ref rte_seqlock.h),
+  [seqcount]           (@ref rte_seqcount.h),
   [RCU]                (@ref rte_rcu_qsbr.h)
 
 - **CPU arch**:
doc/guides/rel_notes/release_22_07.rst +18 -0
index e49cacecef..9c48769171 100644
@@ -60,6 +60,24 @@ New Features
   Added an API which can get the number of in-flight packets in
   vhost async data path without using lock.
 
+* **Added Sequence Lock.**
+
+  Added a new synchronization primitive: the sequence lock
+  (seqlock). A seqlock allows for low overhead, parallel reads. The
+  DPDK seqlock uses a spinlock to serialize multiple writing threads.
+
+  In particular, seqlocks are useful for protecting data structures
+  which are read very frequently, by threads running on many different
+  cores, and modified relatively infrequently.
+
+  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.
+
+  In cases where there is only a single writer, or writer-writer
+  synchronization is performed by some means external to the seqlock,
+  direct use of the underlying sequence counter may be more suitable.
+
 * **Updated Intel iavf driver.**
 
   * Added Tx QoS queue rate limitation support.
lib/eal/include/meson.build +2 -0
index 9700494816..40ebb5b63d 100644
@@ -36,6 +36,8 @@ headers += files(
         'rte_per_lcore.h',
         'rte_random.h',
         'rte_reciprocal.h',
+        'rte_seqcount.h',
+        'rte_seqlock.h',
         'rte_service.h',
         'rte_service_component.h',
         'rte_string_fns.h',
lib/eal/include/rte_seqcount.h new file +252 -0

252 lines not on this page · raw message

lib/eal/include/rte_seqlock.h new file +253 -0

253 lines not on this page · raw message

Signature · 1 line
2.25.1
Acked-by Morten Brørup Acked-by Konstantin Ananyev Reviewed-by Ola Liljedahl Reviewed-by Chengwen Feng on v9 1/1
#10 lore raw
Quoted 48 lines · Mattias Rönnblom

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.

Quoted 8 lines

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

The SoB and other tags were with annotations, just repeating them here (in the hope patchwork will catch them):

GHA had a hiccup on Ubuntu vm installation at the time of the v9 reception. I had run the checks on my side:
https://github.com/david-marchand/dpdk/actions/runs/2373533127

I noticed a little issue in the example in the doxygen comments that I can fix myself:

lib/eal/include/rte_seqlock.h +1 -1
@@ -63,7 +63,7 @@ extern "C" {
  *                 // An alternative to an immediate retry is to abort and
  *                 // try again at some later time, assuming progress is
  *                 // possible without the data.
- *         } while (rte_seqlock_read_retry(&config->lock));
+ *         } while (rte_seqlock_read_retry(&config->lock, sn));
  * }
  *
  * // Accessor function for writing config fields.

I also have some whitespace fixes here and there.

I may shorten the release notes update to keep only the first paragraph, as the rest is too verbose and repeated in the documentation.

Overall, comments were addressed and the patch looks ready. Last call before merging?

Signature · 1 line
David Marchand
#11 lore raw
Quoted 86 lines · David Marchand
Quoted 48 lines · Mattias Rönnblom

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.

Quoted 8 lines

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

The SoB and other tags were with annotations, just repeating them here (in the hope patchwork will catch them):

GHA had a hiccup on Ubuntu vm installation at the time of the v9 reception. I had run the checks on my side:
https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-b0b15dcc7275f17b&q=1&e=d209ff4b-9405-4dbe-8e79-b8505f61ca68&u=https%3A%2F%2Fgithub.com%2Fdavid-marchand%2Fdpdk%2Factions%2Fruns%2F2373533127

I noticed a little issue in the example in the doxygen comments that I can fix myself:

lib/eal/include/rte_seqlock.h +1 -1
@@ -63,7 +63,7 @@ extern "C" {
   *                 // An alternative to an immediate retry is to abort and
   *                 // try again at some later time, assuming progress is
   *                 // possible without the data.
- *         } while (rte_seqlock_read_retry(&config->lock));
+ *         } while (rte_seqlock_read_retry(&config->lock, sn));
   * }
   *
   * // Accessor function for writing config fields.
Quoted 5 lines

I also have some whitespace fixes here and there.

I may shorten the release notes update to keep only the first paragraph, as the rest is too verbose and repeated in the documentation.

Makes sense.

Quoted 5 lines

Overall, comments were addressed and the patch looks ready. Last call before merging?

I don't have anything to add. Thanks.

#12 lore raw
Quoted 26 lines

From: Mattias Rönnblom [mailto:[email protected]]
Sent: Wednesday, 1 June 2022 11.02

Quoted 4 lines · David Marchand
Quoted 2 lines · Mattias Rönnblom

A sequence lock (seqlock) is a synchronization primitive which

allows

Quoted 11 lines
Quoted 11 lines

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

Quoted 1 line
Quoted 1 line

a seqlock is best off being self-contained (i.e., no pointers

[except

Quoted 3 lines
Quoted 2 lines

to constant data]).

Quoted 6 lines
Quoted 4 lines

Overall, comments were addressed and the patch looks ready. Last call before merging?

I don't have anything to add. Thanks.

Please don't hold back merging on my behalf; you may disregard my previous email regarding the v9 patch.

#13 lore raw
In reply to Mattias Rönnblom

lib/eal/include/rte_seqcount.h line 35

Quoted 6 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +6 -0
+/**
+ * The RTE seqcount type.
+ */
+typedef struct {
+	uint32_t sn; /**< A sequence number for the protected data. */
+} rte_seqcount_t;

Don't need structure for only one element.

typedef uint32_t rte_seqcount_t;

+ if (unlikely(begin_sn != end_sn))
+ return true;
+
+ return false;

Prefer to avoid conditional if possible (compiler will optimize it as):

        return begin_sn == end_sn;
#14 lore raw
Quoted 15 lines

From: Stephen Hemminger [mailto:[email protected]]
Sent: Wednesday, 1 June 2022 00.46

lib/eal/include/rte_seqcount.h line 35

Quoted 6 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +6 -0
+/**
+ * The RTE seqcount type.
+ */
+typedef struct {
+	uint32_t sn; /**< A sequence number for the protected data. */
+} rte_seqcount_t;

Don't need structure for only one element.

Quoted 1 line

typedef uint32_t rte_seqcount_t;

Agree. The rte_seqcount_t type is not going to evolve in any way, so it should be safe not wrapping it into a structure.

Quoted 8 lines
lib/eal/include/rte_seqcount.h new file +4 -0
+	if (unlikely(begin_sn != end_sn))
+		return true;
+
+	return false;

Prefer to avoid conditional if possible (compiler will optimize it as):

        return begin_sn == end_sn;

Typo: return begin_sn != end_sn;

Please keep the unlikely() hint, which could also be added to Stephen's variant.

Considering the comments in the source code related to this comparison, Mattias' version seems more readable. And I suppose the compiler is able to generate optimized code for both.

#15 lore raw
In reply to Stephen Hemminger
Quoted 12 lines · Stephen Hemminger

lib/eal/include/rte_seqcount.h line 35

Quoted 6 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +6 -0
+/**
+ * The RTE seqcount type.
+ */
+typedef struct {
+	uint32_t sn; /**< A sequence number for the protected data. */
+} rte_seqcount_t;

Don't need structure for only one element.

The struct adds a degree of type safety, with no run-time cost.

Quoted 10 lines

typedef uint32_t rte_seqcount_t;

lib/eal/include/rte_seqcount.h new file +4 -0
+	if (unlikely(begin_sn != end_sn))
+		return true;
+
+	return false;

Prefer to avoid conditional if possible (compiler will optimize it as):

         return begin_sn == end_sn;

Is this a readability argument, or a performance one?

The compiler might use the unlikely hint to do something useful, like avoiding a branch in the common case.

#16 lore raw
Quoted 14 lines · On Wed, 1 Jun 2022 08:19:54 +0000 Mattias Rönnblom…
Quoted 12 lines · Stephen Hemminger

lib/eal/include/rte_seqcount.h line 35

Quoted 6 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +6 -0
+/**
+ * The RTE seqcount type.
+ */
+typedef struct {
+	uint32_t sn; /**< A sequence number for the protected data. */
+} rte_seqcount_t;  

Don't need structure for only one element.

Quoted 1 line

The struct adds a degree of type safety, with no run-time cost.

Makes sense.

Quoted 8 lines
Quoted 8 lines

typedef uint32_t rte_seqcount_t;

lib/eal/include/rte_seqcount.h new file +4 -0
+	if (unlikely(begin_sn != end_sn))
+		return true;
+
+	return false;
Quoted 8 lines
Quoted 3 lines

Prefer to avoid conditional if possible (compiler will optimize it as):

         return begin_sn == end_sn;  

Is this a readability argument, or a performance one?

The compiler might use the unlikely hint to do something useful, like avoiding a branch in the common case.

It is a matter of taste. I always prefer writing the smallest (within reason) amount of code as possible. And my preference is to do things with declarative and data statements rather than conditionals.

#17 lore raw
Quoted 35 lines · Stephen Hemminger
Quoted 14 lines · On Wed, 1 Jun 2022 08:19:54 +0000 Mattias Rönnblom…
Quoted 12 lines · Stephen Hemminger

lib/eal/include/rte_seqcount.h line 35

Quoted 6 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +6 -0
+/**
+ * The RTE seqcount type.
+ */
+typedef struct {
+	uint32_t sn; /**< A sequence number for the protected data. */
+} rte_seqcount_t;

Don't need structure for only one element.

Quoted 1 line

The struct adds a degree of type safety, with no run-time cost.

Makes sense.

Quoted 14 lines
Quoted 11 lines

typedef uint32_t rte_seqcount_t;

lib/eal/include/rte_seqcount.h new file +4 -0
+	if (unlikely(begin_sn != end_sn))
+		return true;
+
+	return false;

Prefer to avoid conditional if possible (compiler will optimize it as):

          return begin_sn == end_sn;

Is this a readability argument, or a performance one?

Quoted 6 lines
Quoted 2 lines

The compiler might use the unlikely hint to do something useful, like avoiding a branch in the common case.

It is a matter of taste. I always prefer writing the smallest (within reason) amount of code as possible. And my preference is to do things with declarative and data statements rather than conditionals.

I agree. A one-liner would have been a better choice. (A correct one, with the hint.)

#18 lore raw
In reply to Mattias Rönnblom

lib/eal/include/rte_seqcount.h line 166

Quoted 3 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +3 -0
+
+	/* make sure the data loads happens before the sn load */
+	rte_atomic_thread_fence(__ATOMIC_ACQUIRE);

Why mix __atomic builtin with rte_atomic?
Instead:

        __atomic_thread_fence(__ATOMIC_ACQUIRE);
#19 lore raw

<snip>

Quoted 11 lines

lib/eal/include/rte_seqcount.h line 166

Quoted 3 lines · On Mon, 23 May 2022 16:23:46 +0200 Mattias Rönnblom…
lib/eal/include/rte_seqcount.h new file +3 -0
+
+	/* make sure the data loads happens before the sn load */
+	rte_atomic_thread_fence(__ATOMIC_ACQUIRE);

Why mix __atomic builtin with rte_atomic?
Instead:

        __atomic_thread_fence(__ATOMIC_ACQUIRE);

There was an issue with __atomic_thread_fence(__ATOMIC_SEQ_CST) performance on x86. Hence, it was decided to add the 'rte_atomic_thread_fence' wrapper and use it all the time [1].

[1] https://www.dpdk.org/blog/2021/03/26/dpdk-adopts-the-c11-memory-model/

#20 lore raw
In reply to Mattias Rönnblom
Quoted 54 lines · Mattias Rönnblom

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.

Quoted 8 lines

For more information on seqlocks, see
https://en.wikipedia.org/wiki/Seqlock

As mentionned before, I did some little style fixes, and one last minute update following discussion between Stephen and Mattias. This patch passes my checks and the CI was okay.

Thanks Mattias, and reviewers.
Applied for -rc1.

Signature · 1 line
David Marchand