DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
To: <dev@dpdk.org>
Cc: "Thomas Monjalon" <thomas@monjalon.net>,
	"David Marchand" <david.marchand@redhat.com>,
	onar.olsen@ericsson.com, Honnappa.Nagarahalli@arm.com,
	nd@arm.com, konstantin.ananyev@intel.com,
	mb@smartsharesystems.com, stephen@networkplumber.org,
	"Mattias Rönnblom" <mattias.ronnblom@ericsson.com>,
	"Ola Liljedahl" <ola.liljedahl@arm.com>
Subject: [RFC] eal: add seqlock
Date: Fri, 25 Mar 2022 21:24:28 +0100	[thread overview]
Message-ID: <20220325202428.94628-1-mattias.ronnblom@ericsson.com> (raw)
In-Reply-To: <ef0fe83b-0af0-3210-4c40-e26c5b7d416b@ericsson.com>

A sequence lock (seqlock) is synchronization primitive which allows
for data-race free, low-overhead, high-frequency reads, especially for
data structures shared across many cores and which are updated with
relatively low frequency.

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

This RFC version lacks API documentation.

Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/meson.build          |   2 +
 app/test/test_seqlock.c       | 197 ++++++++++++++++++++++++++++++++++
 lib/eal/common/meson.build    |   1 +
 lib/eal/common/rte_seqlock.c  |  12 +++
 lib/eal/include/meson.build   |   1 +
 lib/eal/include/rte_seqlock.h |  84 +++++++++++++++
 lib/eal/version.map           |   3 +
 7 files changed, 300 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

diff --git a/app/test/meson.build b/app/test/meson.build
index 5fc1dd1b7b..5e418e8766 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -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],
diff --git a/app/test/test_seqlock.c b/app/test/test_seqlock.c
new file mode 100644
index 0000000000..a727e16caf
--- /dev/null
+++ b/app/test/test_seqlock.c
@@ -0,0 +1,197 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Ericsson AB
+ */
+
+#include <rte_seqlock.h>
+
+#include <rte_cycles.h>
+#include <rte_malloc.h>
+#include <rte_random.h>
+
+#include <inttypes.h>
+
+#include "test.h"
+
+struct data {
+	rte_seqlock_t lock;
+
+	uint64_t a;
+	uint64_t b __rte_cache_aligned;
+	uint64_t c __rte_cache_aligned;
+} __rte_cache_aligned;
+
+struct reader {
+	struct data *data;
+	uint8_t stop;
+};
+
+#define WRITER_RUNTIME (2.0) /* s */
+
+#define WRITER_MAX_DELAY (100) /* us */
+
+#define INTERRUPTED_WRITER_FREQUENCY (1000)
+#define WRITER_INTERRUPT_TIME (1) /* us */
+
+static int
+writer_start(void *arg)
+{
+	struct data *data = arg;
+	uint64_t deadline;
+
+	deadline = rte_get_timer_cycles() +
+		WRITER_RUNTIME * rte_get_timer_hz();
+
+	while (rte_get_timer_cycles() < deadline) {
+		bool interrupted;
+		uint64_t new_value;
+		unsigned int delay;
+
+		new_value = rte_rand();
+
+		interrupted = rte_rand_max(INTERRUPTED_WRITER_FREQUENCY) == 0;
+
+		rte_seqlock_write_begin(&data->lock);
+
+		data->c = new_value;
+
+		/* These compiler barriers (both on the test reader
+		 * and the test writer side) are here to ensure that
+		 * loads/stores *usually* happen in test program order
+		 * (always on a TSO machine). They are arrange in such
+		 * a way that the writer stores in a different order
+		 * than the reader loads, to emulate an arbitrary
+		 * order. A real application using a seqlock does not
+		 * require any compiler barriers.
+		 */
+		rte_compiler_barrier();
+		data->b = new_value;
+
+		if (interrupted)
+			rte_delay_us_block(WRITER_INTERRUPT_TIME);
+
+		rte_compiler_barrier();
+		data->a = new_value;
+
+		rte_seqlock_write_end(&data->lock);
+
+		delay = rte_rand_max(WRITER_MAX_DELAY);
+
+		rte_delay_us_block(delay);
+	}
+
+	return 0;
+}
+
+#define INTERRUPTED_READER_FREQUENCY (1000)
+#define READER_INTERRUPT_TIME (1000) /* us */
+
+static int
+reader_start(void *arg)
+{
+	struct reader *r = arg;
+	int rc = 0;
+
+	while (__atomic_load_n(&r->stop, __ATOMIC_RELAXED) == 0 && rc == 0) {
+		struct data *data = r->data;
+		bool interrupted;
+		uint64_t a;
+		uint64_t b;
+		uint64_t c;
+		uint64_t sn;
+
+		interrupted = rte_rand_max(INTERRUPTED_READER_FREQUENCY) == 0;
+
+		do {
+			sn = rte_seqlock_read_begin(&data->lock);
+
+			a = data->a;
+			/* See writer_start() for an explaination why
+			 * these barriers are here.
+			 */
+			rte_compiler_barrier();
+
+			if (interrupted)
+				rte_delay_us_block(READER_INTERRUPT_TIME);
+
+			c = data->c;
+
+			rte_compiler_barrier();
+			b = data->b;
+
+		} while (rte_seqlock_read_retry(&data->lock, sn));
+
+		if (a != b || b != c) {
+			printf("Reader observed inconsistent data values "
+			       "%" PRIu64 " %" PRIu64 " %" PRIu64 "\n",
+			       a, b, c);
+			rc = -1;
+		}
+	}
+
+	return rc;
+}
+
+static void
+reader_stop(struct reader *reader)
+{
+	__atomic_store_n(&reader->stop, 1, __ATOMIC_RELAXED);
+}
+
+#define NUM_WRITERS (2)
+#define MIN_NUM_READERS (2)
+#define MAX_READERS (RTE_MAX_LCORE - NUM_WRITERS - 1)
+#define MIN_LCORE_COUNT (NUM_WRITERS + MIN_NUM_READERS + 1)
+
+static int
+test_seqlock(void)
+{
+	struct reader readers[MAX_READERS];
+	unsigned int num_readers;
+	unsigned int num_lcores;
+	unsigned int i;
+	unsigned int lcore_id;
+	unsigned int writer_lcore_ids[NUM_WRITERS] = { 0 };
+	unsigned int reader_lcore_ids[MAX_READERS];
+	int rc = 0;
+
+	num_lcores = rte_lcore_count();
+
+	if (num_lcores < MIN_LCORE_COUNT)
+		return -1;
+
+	num_readers = num_lcores - NUM_WRITERS - 1;
+
+	struct data *data = rte_zmalloc(NULL, sizeof(struct data), 0);
+
+	i = 0;
+	RTE_LCORE_FOREACH_WORKER(lcore_id) {
+		if (i < NUM_WRITERS) {
+			rte_eal_remote_launch(writer_start, data, lcore_id);
+			writer_lcore_ids[i] = lcore_id;
+		} else {
+			unsigned int reader_idx = i - NUM_WRITERS;
+			struct reader *reader = &readers[reader_idx];
+
+			reader->data = data;
+			reader->stop = 0;
+
+			rte_eal_remote_launch(reader_start, reader, lcore_id);
+			reader_lcore_ids[reader_idx] = lcore_id;
+		}
+		i++;
+	}
+
+	for (i = 0; i < NUM_WRITERS; i++)
+		if (rte_eal_wait_lcore(writer_lcore_ids[i]) != 0)
+			rc = -1;
+
+	for (i = 0; i < num_readers; i++) {
+		reader_stop(&readers[i]);
+		if (rte_eal_wait_lcore(reader_lcore_ids[i]) != 0)
+			rc = -1;
+	}
+
+	return rc;
+}
+
+REGISTER_TEST_COMMAND(seqlock_autotest, test_seqlock);
diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build
index 917758cc65..a41343bfed 100644
--- a/lib/eal/common/meson.build
+++ b/lib/eal/common/meson.build
@@ -35,6 +35,7 @@ sources += files(
         'rte_malloc.c',
         'rte_random.c',
         'rte_reciprocal.c',
+	'rte_seqlock.c',
         'rte_service.c',
         'rte_version.c',
 )
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);
+}
diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build
index 9700494816..48df5f1a21 100644
--- a/lib/eal/include/meson.build
+++ b/lib/eal/include/meson.build
@@ -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',
diff --git a/lib/eal/include/rte_seqlock.h b/lib/eal/include/rte_seqlock.h
new file mode 100644
index 0000000000..b975ca848a
--- /dev/null
+++ b/lib/eal/include/rte_seqlock.h
@@ -0,0 +1,84 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Ericsson AB
+ */
+
+#ifndef _RTE_SEQLOCK_H_
+#define _RTE_SEQLOCK_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include <rte_atomic.h>
+#include <rte_branch_prediction.h>
+#include <rte_spinlock.h>
+
+struct rte_seqlock {
+	uint64_t sn;
+	rte_spinlock_t lock;
+};
+
+typedef struct rte_seqlock rte_seqlock_t;
+
+__rte_experimental
+void
+rte_seqlock_init(rte_seqlock_t *seqlock);
+
+__rte_experimental
+static inline uint64_t
+rte_seqlock_read_begin(const rte_seqlock_t *seqlock)
+{
+	/* __ATOMIC_ACQUIRE to prevent loads after (in program order)
+	 * from happening before the sn load. Syncronizes-with the
+	 * store release in rte_seqlock_end().
+	 */
+	return __atomic_load_n(&seqlock->sn, __ATOMIC_ACQUIRE);
+}
+
+__rte_experimental
+static inline bool
+rte_seqlock_read_retry(const rte_seqlock_t *seqlock, uint64_t begin_sn)
+{
+	uint64_t end_sn;
+
+	/* make sure the data loads happens before the sn load */
+	rte_atomic_thread_fence(__ATOMIC_ACQUIRE);
+
+	end_sn = __atomic_load_n(&seqlock->sn, __ATOMIC_RELAXED);
+
+	return unlikely(begin_sn & 1 || begin_sn != end_sn);
+}
+
+__rte_experimental
+static inline void
+rte_seqlock_write_begin(rte_seqlock_t *seqlock)
+{
+	uint64_t sn;
+
+	/* to synchronize with other writers */
+	rte_spinlock_lock(&seqlock->lock);
+
+	sn = seqlock->sn + 1;
+
+	__atomic_store_n(&seqlock->sn, sn, __ATOMIC_RELAXED);
+
+	/* __ATOMIC_RELEASE to prevent stores after (in program order)
+	 * from happening before the sn store.
+	 */
+	rte_atomic_thread_fence(__ATOMIC_RELEASE);
+}
+
+__rte_experimental
+static inline void
+rte_seqlock_write_end(rte_seqlock_t *seqlock)
+{
+	uint64_t sn;
+
+	sn = seqlock->sn + 1;
+
+	/* synchronizes-with the load acquire in rte_seqlock_begin() */
+	__atomic_store_n(&seqlock->sn, sn, __ATOMIC_RELEASE);
+
+	rte_spinlock_unlock(&seqlock->lock);
+}
+
+#endif  /* _RTE_SEQLOCK_H_ */
diff --git a/lib/eal/version.map b/lib/eal/version.map
index b53eeb30d7..4a9d0ed899 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -420,6 +420,9 @@ EXPERIMENTAL {
 	rte_intr_instance_free;
 	rte_intr_type_get;
 	rte_intr_type_set;
+
+	# added in 22.07
+	rte_seqlock_init;
 };
 
 INTERNAL {
-- 
2.25.1


  reply	other threads:[~2022-03-25 20:25 UTC|newest]

Thread overview: 104+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-03-22 16:10 DPDK seqlock Mattias Rönnblom
2022-03-22 16:46 ` Ananyev, Konstantin
2022-03-24  4:52   ` Honnappa Nagarahalli
2022-03-24  5:06     ` Stephen Hemminger
2022-03-24 11:34     ` Mattias Rönnblom
2022-03-25 20:24       ` Mattias Rönnblom [this message]
2022-03-25 21:10         ` [RFC] eal: add seqlock Stephen Hemminger
2022-03-26 14:57           ` Mattias Rönnblom
2022-03-27 14:49         ` Ananyev, Konstantin
2022-03-27 17:42           ` Mattias Rönnblom
2022-03-28 10:53             ` Ananyev, Konstantin
2022-03-28 14:06               ` Ola Liljedahl
2022-03-29  8:32                 ` Mattias Rönnblom
2022-03-29 13:20                   ` Ananyev, Konstantin
2022-03-30 10:07                     ` [PATCH] " Mattias Rönnblom
2022-03-30 10:50                       ` Morten Brørup
2022-03-30 11:24                         ` Tyler Retzlaff
2022-03-30 11:25                         ` Mattias Rönnblom
2022-03-30 14:26                         ` [PATCH v2] " Mattias Rönnblom
2022-03-31  7:46                           ` Mattias Rönnblom
2022-03-31  9:04                             ` Ola Liljedahl
2022-03-31  9:25                               ` Morten Brørup
2022-03-31  9:38                                 ` Ola Liljedahl
2022-03-31 10:03                                   ` Morten Brørup
2022-03-31 11:44                                     ` Ola Liljedahl
2022-03-31 11:50                                       ` Morten Brørup
2022-03-31 14:02                                       ` Mattias Rönnblom
2022-04-01 15:07                                         ` [PATCH v3] " Mattias Rönnblom
2022-04-02  0:21                                           ` Honnappa Nagarahalli
2022-04-02 11:01                                             ` Morten Brørup
2022-04-02 19:38                                               ` Honnappa Nagarahalli
2022-04-10 13:51                                                 ` [RFC 1/3] eal: add macro to warn for unused function return values Mattias Rönnblom
2022-04-10 13:51                                                   ` [RFC 2/3] eal: emit warning for unused trylock return value Mattias Rönnblom
2022-04-10 13:51                                                   ` [RFC 3/3] examples/bond: fix invalid use of trylock Mattias Rönnblom
2022-04-11  1:01                                                     ` Min Hu (Connor)
2022-04-11 14:32                                                       ` Mattias Rönnblom
2022-04-11 11:25                                                     ` David Marchand
2022-04-11 14:33                                                       ` Mattias Rönnblom
2022-04-10 18:02                                                   ` [RFC 1/3] eal: add macro to warn for unused function return values Stephen Hemminger
2022-04-10 18:50                                                     ` Mattias Rönnblom
2022-04-11  7:17                                                   ` Morten Brørup
2022-04-11 14:29                                                     ` Mattias Rönnblom
2022-04-11  9:16                                                   ` Bruce Richardson
2022-04-11 14:27                                                     ` Mattias Rönnblom
2022-04-11 15:15                                                     ` [PATCH " Mattias Rönnblom
2022-04-11 15:15                                                       ` [PATCH 2/3] eal: emit warning for unused trylock return value Mattias Rönnblom
2022-04-11 15:29                                                         ` Morten Brørup
2022-04-11 15:15                                                       ` [PATCH 3/3] examples/bond: fix invalid use of trylock Mattias Rönnblom
2022-04-14 12:06                                                         ` David Marchand
2022-04-11 15:25                                                       ` [PATCH 1/3] eal: add macro to warn for unused function return values Morten Brørup
2022-04-11 18:24                                                     ` [RFC " Tyler Retzlaff
2022-04-03  6:10                                             ` [PATCH v3] eal: add seqlock Mattias Rönnblom
2022-04-03 17:27                                               ` Honnappa Nagarahalli
2022-04-03 18:37                                                 ` Ola Liljedahl
2022-04-04 21:56                                                   ` Honnappa Nagarahalli
2022-04-03  6:33                                             ` Mattias Rönnblom
2022-04-03 17:37                                               ` Honnappa Nagarahalli
2022-04-08 13:45                                                 ` Mattias Rönnblom
2022-04-02 18:15                                           ` Ola Liljedahl
2022-04-02 19:31                                             ` Honnappa Nagarahalli
2022-04-02 20:36                                               ` Morten Brørup
2022-04-02 22:01                                                 ` Honnappa Nagarahalli
2022-04-03 18:11                                               ` Ola Liljedahl
2022-04-03  6:51                                             ` Mattias Rönnblom
2022-03-31 13:51                                 ` [PATCH v2] " Mattias Rönnblom
2022-04-02  0:54                                   ` Stephen Hemminger
2022-04-02 10:25                                     ` Morten Brørup
2022-04-02 17:43                                       ` Ola Liljedahl
2022-03-31 13:38                               ` Mattias Rönnblom
2022-03-31 14:53                                 ` Ola Liljedahl
2022-04-02  0:52                                   ` Stephen Hemminger
2022-04-03  6:23                                     ` Mattias Rönnblom
2022-04-02  0:50                           ` Stephen Hemminger
2022-04-02 17:54                             ` Ola Liljedahl
2022-04-02 19:37                               ` Honnappa Nagarahalli
2022-04-05 20:16                           ` Stephen Hemminger
2022-04-08 13:50                             ` Mattias Rönnblom
2022-04-08 14:24                               ` [PATCH v4] " Mattias Rönnblom
2022-04-08 15:17                                 ` Stephen Hemminger
2022-04-08 16:24                                   ` Mattias Rönnblom
2022-04-08 15:19                                 ` Stephen Hemminger
2022-04-08 16:37                                   ` Mattias Rönnblom
2022-04-08 16:48                                 ` Mattias Rönnblom
2022-04-12 17:27                                 ` Ananyev, Konstantin
2022-04-28 10:28                                 ` David Marchand
2022-05-01 13:46                                   ` Mattias Rönnblom
2022-05-01 14:03                                     ` [PATCH v5] " Mattias Rönnblom
2022-05-01 14:22                                       ` Mattias Rönnblom
2022-05-02  6:47                                         ` David Marchand
2022-05-01 20:17                                       ` Stephen Hemminger
2022-05-02  4:51                                         ` Mattias Rönnblom
2022-05-06  1:26                                       ` fengchengwen
2022-05-06  1:33                                         ` Honnappa Nagarahalli
2022-05-06  4:17                                           ` fengchengwen
2022-05-06  5:19                                             ` Honnappa Nagarahalli
2022-05-06  7:03                                               ` fengchengwen
2022-05-08 11:56                                         ` Mattias Rönnblom
2022-05-08 12:12                                           ` [PATCH v6] " Mattias Rönnblom
2022-05-08 16:10                                             ` Stephen Hemminger
2022-05-08 19:40                                               ` Mattias Rönnblom
2022-05-09  3:48                                                 ` Stephen Hemminger
2022-05-09  6:26                                                   ` Morten Brørup
2022-05-13  6:27                                                   ` Mattias Rönnblom
2022-03-23 12:04 ` DPDK seqlock Morten Brørup

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220325202428.94628-1-mattias.ronnblom@ericsson.com \
    --to=mattias.ronnblom@ericsson.com \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=david.marchand@redhat.com \
    --cc=dev@dpdk.org \
    --cc=konstantin.ananyev@intel.com \
    --cc=mb@smartsharesystems.com \
    --cc=nd@arm.com \
    --cc=ola.liljedahl@arm.com \
    --cc=onar.olsen@ericsson.com \
    --cc=stephen@networkplumber.org \
    --cc=thomas@monjalon.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).