From: "Eads, Gage" <gage.eads@intel.com>
To: Ola Liljedahl <Ola.Liljedahl@arm.com>,
"jerinj@marvell.com" <jerinj@marvell.com>,
"mczekaj@marvell.com" <mczekaj@marvell.com>,
"dev@dpdk.org" <dev@dpdk.org>
Cc: "olivier.matz@6wind.com" <olivier.matz@6wind.com>,
"stephen@networkplumber.org" <stephen@networkplumber.org>,
nd <nd@arm.com>, "Richardson, Bruce" <bruce.richardson@intel.com>,
"arybchenko@solarflare.com" <arybchenko@solarflare.com>,
"Ananyev, Konstantin" <konstantin.ananyev@intel.com>
Subject: Re: [dpdk-dev] [PATCH v3 2/5] ring: add a non-blocking implementation
Date: Mon, 28 Jan 2019 18:54:25 +0000 [thread overview]
Message-ID: <9184057F7FC11744A2107296B6B8EB1E541CC312@FMSMSX108.amr.corp.intel.com> (raw)
In-Reply-To: <1548671766.3076.16.camel@arm.com>
> -----Original Message-----
> From: Ola Liljedahl [mailto:Ola.Liljedahl@arm.com]
> Sent: Monday, January 28, 2019 4:36 AM
> To: jerinj@marvell.com; mczekaj@marvell.com; Eads, Gage
> <gage.eads@intel.com>; dev@dpdk.org
> Cc: olivier.matz@6wind.com; stephen@networkplumber.org; nd
> <nd@arm.com>; Richardson, Bruce <bruce.richardson@intel.com>;
> arybchenko@solarflare.com; Ananyev, Konstantin
> <konstantin.ananyev@intel.com>
> Subject: Re: [dpdk-dev] [PATCH v3 2/5] ring: add a non-blocking implementation
>
> On Fri, 2019-01-25 at 17:21 +0000, Eads, Gage wrote:
> >
> > >
> > > -----Original Message-----
> > > From: Ola Liljedahl [mailto:Ola.Liljedahl@arm.com]
> > > Sent: Wednesday, January 23, 2019 4:16 AM
> > > To: Eads, Gage <gage.eads@intel.com>; dev@dpdk.org
> > > Cc: olivier.matz@6wind.com; stephen@networkplumber.org; nd
> > > <nd@arm.com>; Richardson, Bruce <bruce.richardson@intel.com>;
> > > arybchenko@solarflare.com; Ananyev, Konstantin
> > > <konstantin.ananyev@intel.com>
> > > Subject: Re: [dpdk-dev] [PATCH v3 2/5] ring: add a non-blocking
> > > implementation
> > >
> > > On Tue, 2019-01-22 at 21:31 +0000, Eads, Gage wrote:
> > > >
> > > > Hi Ola,
> > > >
> > > > <snip>
> > > >
> > > > >
> > > > >
> > > > > >
> > > > > >
> > > > > > @@ -331,6 +433,319 @@ void rte_ring_dump(FILE *f, const struct
> > > > > > rte_ring *r);
> > > > > > #endif
> > > > > > #include "rte_ring_generic_64.h"
> > > > > >
> > > > > > +/* @internal 128-bit structure used by the non-blocking ring
> > > > > > +*/ struct nb_ring_entry {
> > > > > > + void *ptr; /**< Data pointer */
> > > > > > + uint64_t cnt; /**< Modification counter */
> > > > > Why not make 'cnt' uintptr_t? This way 32-bit architectures will
> > > > > also be supported. I think there are some claims that DPDK still
> > > > > supports e.g.
> > > > > ARMv7a
> > > > > and possibly also 32-bit x86?
> > > > I chose a 64-bit modification counter because (practically
> > > > speaking) the ABA problem will not occur with such a large counter
> > > > -- definitely not within my lifetime. See the "Discussion" section
> > > > of the commit message for more information.
> > > >
> > > > With a 32-bit counter, there is a very (very) low likelihood of
> > > > it, but it is possible. Personally, I don't feel comfortable
> > > > providing such code, because a) I doubt all users would understand
> > > > the implementation well enough to do the risk/reward analysis, and
> > > > b) such a bug would be near impossible to reproduce and root-cause
> > > > if it did occur.
> > > With a 64-bit counter (and 32-bit pointer), 32-bit architectures (e.g.
> > > ARMv7a and
> > > probably x86 as well) won't be able to support this as they at best
> > > support 64-bit CAS (ARMv7a has LDREXD/STREXD). So you are
> > > essentially putting a 64-bit (and 128-bit CAS) requirement on the
> > > implementation.
> > >
> > Yes, I am. I tried to make that clear in the cover letter.
> >
> > >
> > > >
> > > >
> > > > >
> > > > >
> > > > >
> > > > > >
> > > > > >
> > > > > > +};
> > > > > > +
> > > > > > +/* The non-blocking ring algorithm is based on the original
> > > > > > +rte ring (derived
> > > > > > + * from FreeBSD's bufring.h) and inspired by Michael and
> > > > > > +Scott's non-blocking
> > > > > > + * concurrent queue.
> > > > > > + */
> > > > > > +
> > > > > > +/**
> > > > > > + * @internal
> > > > > > + * Enqueue several objects on the non-blocking ring
> > > > > > +(single-producer only)
> > > > > > + *
> > > > > > + * @param r
> > > > > > + * A pointer to the ring structure.
> > > > > > + * @param obj_table
> > > > > > + * A pointer to a table of void * pointers (objects).
> > > > > > + * @param n
> > > > > > + * The number of objects to add in the ring from the obj_table.
> > > > > > + * @param behavior
> > > > > > + * RTE_RING_QUEUE_FIXED: Enqueue a fixed number of items
> > > > > > +to the ring
> > > > > > + * RTE_RING_QUEUE_VARIABLE: Enqueue as many items as
> > > > > > +possible to the ring
> > > > > > + * @param free_space
> > > > > > + * returns the amount of space after the enqueue operation
> > > > > > +has finished
> > > > > > + * @return
> > > > > > + * Actual number of objects enqueued.
> > > > > > + * If behavior == RTE_RING_QUEUE_FIXED, this will be 0 or n only.
> > > > > > + */
> > > > > > +static __rte_always_inline unsigned int
> > > > > > +__rte_ring_do_nb_enqueue_sp(struct rte_ring *r, void * const
> > > > > > *obj_table,
> > > > > > + unsigned int n,
> > > > > > + enum rte_ring_queue_behavior behavior,
> > > > > > + unsigned int *free_space) {
> > > > > > + uint32_t free_entries;
> > > > > > + size_t head, next;
> > > > > > +
> > > > > > + n = __rte_ring_move_prod_head_64(r, 1, n, behavior,
> > > > > > + &head, &next,
> > > > > > &free_entries);
> > > > > > + if (n == 0)
> > > > > > + goto end;
> > > > > > +
> > > > > > + ENQUEUE_PTRS_NB(r, &r[1], head, obj_table, n);
> > > > > > +
> > > > > > + r->prod_64.tail += n;
> > > > > Don't we need release order when (or smp_wmb between) writing of
> > > > > the ring pointers and the update of tail? By updating the tail
> > > > > pointer, we are synchronising with a consumer.
> > > > >
> > > > > I prefer using __atomic operations even for load and store. You
> > > > > can see which parts of the code that synchronise with each other, e.g.
> > > > > store-release to some location synchronises with load-acquire
> > > > > from the same location. If you don't know how different threads
> > > > > synchronise with each other, you are very likely to make mistakes.
> > > > >
> > > > You can tell this code was written when I thought x86-64 was the
> > > > only viable target :). Yes, you are correct.
> > > >
> > > > With regards to using __atomic intrinsics, I'm planning on taking
> > > > a similar approach to the functions duplicated in
> > > > rte_ring_generic.h and
> > > > rte_ring_c11_mem.h: one version that uses rte_atomic functions
> > > > (and thus stricter memory ordering) and one that uses __atomic
> > > > intrinsics (and thus can benefit from more relaxed memory ordering).
> From a code point of view, I strongly prefer the atomic operations to be visible
> in the top level code, not hidden in subroutines. For correctness, it is vital that
> memory accesses are performed with the required ordering and that acquire and
> release matches up. Hiding e.g. load-acquire and store-release in subroutines (in
> a different file!) make this difficult. There have already been such bugs found in
> rte_ring.
>
After working on the acq/rel ordering this weekend, I agree. This'll be easier/cleaner if we end up only using the C11 version.
> > > What's the advantage of having two different implementations? What
> > > is the disadvantage?
> > >
> > > The existing ring buffer code originally had only the "legacy"
> > > implementation
> > > which was kept when the __atomic implementation was added. The
> > > reason claimed was that some older compilers for x86 do not support
> > > GCC __atomic builtins. But I thought there was consensus that new
> > > functionality could have only __atomic implementations.
> > >
> > When CONFIG_RTE_RING_USE_C11_MEM_MODEL was introduced, it was left
> > disabled for thunderx[1] for performance reasons. Assuming that hasn't
> > changed, the advantage to having two versions is to best support all of DPDK's
> platforms.
> > The disadvantage is of course duplicated code and the additional
> > maintenance burden.
> The only way I see that a C11 memory model implementation can be slower
> than using smp_wmb/rmb is if you need to order loads before a synchronizing
> store and there are also outstanding stores which do not require ordering.
> smp_rmb() handles this while store-release will also (unnecessarily) order those
> outstanding stores. This situation occurs e.g. in ring buffer dequeue operations
> where ring slots are read (and possibly written to thread-private memory) before
> the ring slots are release (e.g. using CAS-release or store-release).
>
> I imagine that the LSU/cache subsystem on ThunderX/OCTEON-TX also have
> something to do with this problem. If there are a large amounts of stores
> pending in the load/store unit, store-release might have to wait for a long time
> before the synchronizing store can complete.
>
> >
> > That said, if the thunderx maintainers are ok with it, I'm certainly
> > open to only doing the __atomic version. Note that even in the
> > __atomic version, based on Honnapa's findings[2], using a DPDK-defined
> > rte_atomic128_cmpset() (with additional arguments to support machines
> > with weak consistency) appears to be a better option than
> __atomic_compare_exchange_16.
> __atomic_compare_exchange_16() is not guaranteed to be lock-free. It is not
> lock-free on ARM/AArch64 and the support in GCC is formally broken (can't use
> cmpexchg16b to implement __atomic_load_16).
>
> So yes, I think DPDK will have to define and implement the 128-bit atomic
> compare and exchange operation (whatever it will be called). For compatibility
> with ARMv8.0, we can't require the "old" value returned by a failed compare-
> exchange operation to be read atomically (LDXP does not guaranteed atomicity
> by itself). But this is seldom a problem, many designs read the memory location
> using two separate 64-bit loads (so not atomic) anyway, it is a successful atomic
> compare exchange operation which provides atomicity.
>
Ok. I agree, I don't expect that to be a problem. The 128-bit CAS patch I just submitted[1] (which was developed before reading this) will have to be changed.
[1] http://mails.dpdk.org/archives/dev/2019-January/124159.html
Thanks,
Gage
</snip>
next prev parent reply other threads:[~2019-01-28 18:54 UTC|newest]
Thread overview: 123+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-10 21:01 [dpdk-dev] [PATCH 0/6] Add non-blocking ring Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 1/6] ring: change head and tail to pointer-width size Gage Eads
2019-01-11 4:38 ` Stephen Hemminger
2019-01-11 19:07 ` Eads, Gage
2019-01-11 10:25 ` Burakov, Anatoly
2019-01-11 19:12 ` Eads, Gage
2019-01-11 19:55 ` Stephen Hemminger
2019-01-15 15:48 ` Eads, Gage
2019-01-11 10:40 ` Burakov, Anatoly
2019-01-11 10:58 ` Bruce Richardson
2019-01-11 11:30 ` Burakov, Anatoly
[not found] ` <20190111115851.GC3336@bricha3-MOBL.ger.corp.intel.com>
2019-01-11 19:27 ` Eads, Gage
2019-01-21 14:14 ` Burakov, Anatoly
2019-01-22 18:27 ` Eads, Gage
2019-01-10 21:01 ` [dpdk-dev] [PATCH 2/6] ring: add a non-blocking implementation Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 3/6] test_ring: add non-blocking ring autotest Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 4/6] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-10 21:01 ` [dpdk-dev] [PATCH 5/6] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-13 13:43 ` Andrew Rybchenko
2019-01-10 21:01 ` [dpdk-dev] [PATCH 6/6] doc: add NB ring comment to EAL "known issues" Gage Eads
2019-01-11 2:51 ` Varghese, Vipin
2019-01-11 19:30 ` Eads, Gage
2019-01-14 0:07 ` Varghese, Vipin
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 0/5] Add non-blocking ring Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 1/5] ring: change head and tail to pointer-width size Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-15 23:52 ` [dpdk-dev] [PATCH v2 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-16 0:26 ` [dpdk-dev] [PATCH v2 0/5] Add non-blocking ring Stephen Hemminger
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 " Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 1/5] ring: add 64-bit headtail structure Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-22 10:12 ` Ola Liljedahl
2019-01-22 14:49 ` Ola Liljedahl
2019-01-22 21:31 ` Eads, Gage
2019-01-23 10:16 ` Ola Liljedahl
2019-01-25 17:21 ` Eads, Gage
2019-01-28 10:35 ` Ola Liljedahl
2019-01-28 18:54 ` Eads, Gage [this message]
2019-01-28 22:31 ` Ola Liljedahl
2019-01-28 13:34 ` Jerin Jacob Kollanukkaran
2019-01-28 13:43 ` Ola Liljedahl
2019-01-28 14:04 ` Jerin Jacob Kollanukkaran
2019-01-28 14:06 ` Ola Liljedahl
2019-01-28 18:59 ` Eads, Gage
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-18 15:23 ` [dpdk-dev] [PATCH v3 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-01-22 9:27 ` [dpdk-dev] [PATCH v3 0/5] Add non-blocking ring Ola Liljedahl
2019-01-22 10:15 ` Ola Liljedahl
2019-01-22 19:15 ` Eads, Gage
2019-01-23 16:02 ` Jerin Jacob Kollanukkaran
2019-01-23 16:29 ` Ola Liljedahl
2019-01-28 13:10 ` [dpdk-dev] [EXT] " Jerin Jacob Kollanukkaran
2019-01-25 5:20 ` [dpdk-dev] " Honnappa Nagarahalli
2019-01-25 17:42 ` Eads, Gage
2019-01-25 17:56 ` Eads, Gage
2019-01-28 10:41 ` Ola Liljedahl
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 " Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 1/5] ring: add 64-bit headtail structure Gage Eads
2019-01-29 12:56 ` Ola Liljedahl
2019-01-30 4:26 ` Eads, Gage
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 2/5] ring: add a non-blocking implementation Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 3/5] test_ring: add non-blocking ring autotest Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 4/5] test_ring_perf: add non-blocking ring perf test Gage Eads
2019-01-28 18:14 ` [dpdk-dev] [PATCH v4 5/5] mempool/ring: add non-blocking ring handlers Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 2/6] ring: add a ring start marker Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 3/6] ring: add a lock-free implementation Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-05 17:40 ` [dpdk-dev] [PATCH v5 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 2/6] ring: add a ring start marker Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 3/6] ring: add a lock-free implementation Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-06 15:03 ` [dpdk-dev] [PATCH v6 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 0/6] Add lock-free ring and mempool handler Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 2/6] ring: add a ring start marker Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 3/6] ring: add a lock-free implementation Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-19 15:50 ` Stephen Hemminger
2019-03-19 15:50 ` Stephen Hemminger
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:35 ` [dpdk-dev] [PATCH v7 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-18 21:35 ` Gage Eads
2019-03-18 21:49 ` [dpdk-dev] [PATCH v7 0/6] Add lock-free ring and mempool handler Eads, Gage
2019-03-18 21:49 ` Eads, Gage
2019-03-19 15:51 ` Stephen Hemminger
2019-03-19 15:51 ` Stephen Hemminger
2019-04-01 19:23 ` Eads, Gage
2019-04-01 19:23 ` Eads, Gage
2019-04-02 10:16 ` Ola Liljedahl
2019-04-02 10:16 ` Ola Liljedahl
2019-04-04 22:28 ` Eads, Gage
2019-04-04 22:28 ` Eads, Gage
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 " Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 1/6] ring: add a pointer-width headtail structure Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 2/6] ring: add a ring start marker Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 3/6] ring: add a lock-free implementation Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 4/6] test_ring: add lock-free ring autotest Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 5/6] test_ring_perf: add lock-free ring perf test Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-03-19 1:20 ` [dpdk-dev] [PATCH v8 6/6] mempool/ring: add lock-free ring handlers Gage Eads
2019-03-19 1:20 ` Gage Eads
2019-04-03 16:46 ` [dpdk-dev] [PATCH v8 0/6] Add lock-free ring and mempool handler Thomas Monjalon
2019-04-03 16:46 ` Thomas Monjalon
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=9184057F7FC11744A2107296B6B8EB1E541CC312@FMSMSX108.amr.corp.intel.com \
--to=gage.eads@intel.com \
--cc=Ola.Liljedahl@arm.com \
--cc=arybchenko@solarflare.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=jerinj@marvell.com \
--cc=konstantin.ananyev@intel.com \
--cc=mczekaj@marvell.com \
--cc=nd@arm.com \
--cc=olivier.matz@6wind.com \
--cc=stephen@networkplumber.org \
/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).