DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Mattias Rönnblom" <hofors@lysator.liu.se>
To: "David Marchand" <david.marchand@redhat.com>,
	"Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
Cc: dev <dev@dpdk.org>, "Thomas Monjalon" <thomas@monjalon.net>,
	onar.olsen@ericsson.com,
	"Honnappa Nagarahalli" <Honnappa.Nagarahalli@arm.com>,
	nd <nd@arm.com>,
	"Ananyev, Konstantin" <konstantin.ananyev@intel.com>,
	"Morten Brørup" <mb@smartsharesystems.com>,
	"Stephen Hemminger" <stephen@networkplumber.org>,
	"Ola Liljedahl" <ola.liljedahl@arm.com>
Subject: Re: [PATCH v4] eal: add seqlock
Date: Sun, 1 May 2022 15:46:13 +0200	[thread overview]
Message-ID: <3e9b0560-9306-0826-4911-1cf0e72c30d9@lysator.liu.se> (raw)
In-Reply-To: <CAJFAV8xS_egr1Qm7DrcBFs6GU4t7Ehw8FoWm=zBJWpzRTamPYg@mail.gmail.com>

On 2022-04-28 12:28, David Marchand wrote:
> Hello Mattias,
> 
> On Fri, Apr 8, 2022 at 4:25 PM Mattias Rönnblom
> <mattias.ronnblom@ericsson.com> wrote:
>>
>> 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
>> 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 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
> 
> Revisions changelog should be after commitlog, separated with ---.
> 

OK.

>>
>> 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.
>>
>> Acked-by: Morten Brørup <mb@smartsharesystems.com>
>> Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> 
> We are missing a MAINTAINERS update, either with a new section for
> this lock (like for MCS and ticket locks), or adding the new test code
> under the EAL API and common code section (like rest of the locks).
> 

OK. I added a new section, and myself as the maintainer. If you want to 
merge it with EAL and the common code that fine with me as well. Let me 
know in that case. The seqlock is a tiny bit of code, but there are some 
intricacies (like always when C11 memory models matter).

> This new lock is not referenced in doxygen (see doc/api/doxy-api-index.md).
> 

OK.

> It's worth a release notes update for advertising this new lock type.
> 

OK.

> [snip]
> 
> 
>> diff --git a/app/test/test_seqlock.c b/app/test/test_seqlock.c
>> new file mode 100644
>> index 0000000000..3f1ce53678
>> --- /dev/null
>> +++ b/app/test/test_seqlock.c
> 
> [snip]
> 
>> +/* Only a compile-time test */
>> +static rte_seqlock_t __rte_unused static_init_lock = RTE_SEQLOCK_INITIALIZER;
>> +
>> +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 reader_lcore_ids[MAX_READERS];
>> +       unsigned int worker_writer_lcore_id = 0;
>> +       int rc = 0;
> 
> A unit test is supposed to use TEST_* macros as return values.
> I concede other locks unit tests return 0 or -1 (which is equivalent,
> given TEST_SUCCESS / TEST_FAILED values).
> We can go with 0 / -1 (and a cleanup could be done later on app/test
> globally), but at least change to TEST_SKIPPED when lacking lcores
> (see below).
> 

I'll fix it right away instead.

> 
>> +
>> +       num_lcores = rte_lcore_count();
>> +
>> +       if (num_lcores < MIN_LCORE_COUNT) {
>> +               printf("Too few cores to run test. Skipping.\n");
>> +               return 0;
> 
> return TEST_SKIPPED;
> 
> 

Excellent. I remember asking myself if there was such a return code when 
I wrote that code, but then I forgot to actually go look for it.

>> +       }
>> +
>> +       num_readers = num_lcores - NUM_WRITERS;
>> +
>> +       struct data *data = rte_zmalloc(NULL, sizeof(struct data), 0);
>> +
>> +       i = 0;
>> +       RTE_LCORE_FOREACH_WORKER(lcore_id) {
>> +               if (i == 0) {
>> +                       rte_eal_remote_launch(writer_run, data, lcore_id);
>> +                       worker_writer_lcore_id = lcore_id;
>> +               } else {
>> +                       unsigned int reader_idx = i - 1;
>> +                       struct reader *reader = &readers[reader_idx];
>> +
>> +                       reader->data = data;
>> +                       reader->stop = 0;
>> +
>> +                       rte_eal_remote_launch(reader_run, reader, lcore_id);
>> +                       reader_lcore_ids[reader_idx] = lcore_id;
>> +               }
>> +               i++;
>> +       }
>> +
>> +       if (writer_run(data) != 0 ||
>> +           rte_eal_wait_lcore(worker_writer_lcore_id) != 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',
> 
> Indent is not correct, please use spaces for meson files.
> 

OK.

> 
>>           'rte_service.c',
>>           'rte_version.c',
>>   )
>> diff --git a/lib/eal/include/rte_seqlock.h b/lib/eal/include/rte_seqlock.h
>> new file mode 100644
>> index 0000000000..961816aa10
>> --- /dev/null
>> +++ b/lib/eal/include/rte_seqlock.h
>> @@ -0,0 +1,319 @@
>> +/* SPDX-License-Identifier: BSD-3-Clause
>> + * Copyright(c) 2022 Ericsson AB
>> + */
>> +
>> +#ifndef _RTE_SEQLOCK_H_
>> +#define _RTE_SEQLOCK_H_
>> +
>> +#ifdef __cplusplus
>> +extern "C" {
>> +#endif
>> +
>> +/** >> + * @file
>> + * RTE Seqlock
> 
> Nit: mention of RTE adds nothing, I'd remove it.
> 

I agree, but there seemed to be a convention that called for this.

> 
>> + *
>> + * A sequence lock (seqlock) is a synchronization primitive allowing
>> + * multiple, parallel, readers to efficiently and safely (i.e., in a
>> + * data-race free manner) access lock-protected data. The RTE seqlock
>> + * permits multiple writers as well. A spinlock is used to
>> + * writer-writer synchronization.
>> + *
>> + * A reader never blocks a writer. Very high frequency writes may
>> + * prevent readers from making progress.
>> + *
>> + * A seqlock is not preemption-safe on the writer side. If a writer is
>> + * preempted, it may block readers until the writer thread is allowed
>> + * to continue. Heavy computations should be kept out of the
>> + * writer-side critical section, to avoid delaying readers.
>> + *
>> + * Seqlocks are useful for data which are read by many cores, at a
>> + * high frequency, and relatively infrequently written to.
>> + *
>> + * One way to think about seqlocks is that they provide means to
>> + * perform atomic operations on objects larger than what the native
>> + * machine instructions allow for.
>> + *
>> + * To avoid resource reclamation issues, the data protected by a
>> + * seqlock should typically be kept self-contained (e.g., no pointers
>> + * to mutable, dynamically allocated data).
>> + *
>> + * Example usage:
>> + * @code{.c}
>> + * #define MAX_Y_LEN (16)
>> + * // Application-defined example data structure, protected by a seqlock.
>> + * struct config {
>> + *         rte_seqlock_t lock;
>> + *         int param_x;
>> + *         char param_y[MAX_Y_LEN];
>> + * };
>> + *
>> + * // Accessor function for reading config fields.
>> + * void
>> + * config_read(const struct config *config, int *param_x, char *param_y)
>> + * {
>> + *         uint32_t sn;
>> + *
>> + *         do {
>> + *                 sn = rte_seqlock_read_begin(&config->lock);
>> + *
>> + *                 // Loads may be atomic or non-atomic, as in this example.
>> + *                 *param_x = config->param_x;
>> + *                 strcpy(param_y, config->param_y);
>> + *                 // 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));
>> + * }
>> + *
>> + * // Accessor function for writing config fields.
>> + * void
>> + * config_update(struct config *config, int param_x, const char *param_y)
>> + * {
>> + *         rte_seqlock_write_lock(&config->lock);
>> + *         // Stores may be atomic or non-atomic, as in this example.
>> + *         config->param_x = param_x;
>> + *         strcpy(config->param_y, param_y);
>> + *         rte_seqlock_write_unlock(&config->lock);
>> + * }
>> + * @endcode
>> + *
>> + * @see
>> + * https://en.wikipedia.org/wiki/Seqlock.
>> + */
> 
> 
> The rest lgtm.
> 
> 

Thanks a lot David for the review!

  reply	other threads:[~2022-05-01 13:46 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       ` [RFC] eal: add seqlock Mattias Rönnblom
2022-03-25 21:10         ` 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 [this message]
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=3e9b0560-9306-0826-4911-1cf0e72c30d9@lysator.liu.se \
    --to=hofors@lysator.liu.se \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=david.marchand@redhat.com \
    --cc=dev@dpdk.org \
    --cc=konstantin.ananyev@intel.com \
    --cc=mattias.ronnblom@ericsson.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).