RE: [RFC] lib/st_ring: add single thread ring

[Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>]

<snip>

> >> Subject: Re: [RFC] lib/st_ring: add single thread ring
> >>
> >> On 2023-08-21 08:04, Honnappa Nagarahalli wrote:
> >>> Add a single thread safe and multi-thread unsafe ring data structure.
> >>
> >> One must have set the bar very low, if one needs to specify that an
> >> API is single-thread safe.
> >>
> >>> This library provides an simple and efficient alternative to
> >>> multi-thread safe ring when multi-thread safety is not required.
> >>>
> >>> Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> >>> ---
> >>> v1:
> >>> 1) The code is very prelimnary and is not even compiled
> >>> 2) This is intended to show the APIs and some thoughts on
> >>> implementation
> >>
> >> If you haven't done it already, maybe it might be worth looking
> >> around in the code base for already-existing, more-or-less open-coded
> >> fifo/circular buffer type data structures. Just to make sure those
> >> can be eliminated if this makes it into DPDK.
> >>
> >> There's one in rte_event_eth_rx_adapter.c, and I think one in the SW
> >> eventdev as well. Seems to be one in cmdline_cirbuf.h as well. I'm
> >> sure there are many more.
> > I knew there are some, but have not looked at them yet. I will look at them.
> >
> >>
> >> You could pick some other name for it, instead of the slightly
> >> awkward "st_ring" (e.g., "fifo", "cbuf", "cbuffer", "circ_buffer").
> >> That would also leave you with more freedom to stray from the MT safe
> >> ring API without surprising the user, if needed (and I think it is needed).
> > The thought was to make it clear that this is for single-thread use (i.e.not even
> producer and consumer on different threads), may be I do not need to try hard.
> > "fifo" might not be good option given that dequeue/enqueue at both ends of
> the ring are required/allowed.
> > Wikipedia [1] and others [2], [3] indicates that this data structure
> > should be called 'deque' (pronounced as deck). I would prefer to go
> > with this (assuming this will be outside of 'rte_ring')
> >
> > [1] https://en.wikipedia.org/wiki/Double-ended_queue
> > [2]
> > https://www.geeksforgeeks.org/deque-set-1-introduction-applications/
> > [3] https://stackoverflow.com/questions/3880254/why-do-we-need-deque-
> data-structures-in-the-real-
> world#:~:text=A%20Deque%20is%20a%20double,thing%20on%20front%20of
> %20queue.
> >
> >>
> >> Hopefully you can reduce API complexity compared to the MT-safe version.
> >> Having a name for these kinds of data structures doesn't make a lot
> >> of sense, for example. Skip the dump function. Relax from
> >> always_inline to just regular inline.
> > Yes, plan is to reduce complexity (compared to rte_ring) and some APIs can be
> skipped until there is a need.
> >
> >>
> >> I'm not sure you need bulk/burst type operations. Without any memory
> >> fences, an optimizing compiler should do a pretty good job of
> >> unrolling multiple-element access type operations, assuming you leave
> >> the ST ring code in the header files (otherwise LTO is needed).
> > IMO, bulk/burst APIs are about the functionality rather than loop unrolling.
> APIs to work with single objects can be skipped (use bulk APIs with n=1).
> >
> 
> Given that this data structure will often be use in conjunction with other
> burst/bulk type operations, I agree.
> 
> What about peek? I guess you could have a burst/bulk peek as well, would that
> operation be needed. I think it will be needed, but the introduction of such API
> elements could always be deferred.
Yes, I will provide this functionality, but will differ for later.

> 
> >>
> >> I think you will want a peek-type operation on the reader side. That
> >> more for convenience, rather than that I think the copies will
> >> actually be there in the object code (such should be eliminated by
> >> the compiler, given that the barriers are gone).
> >>
> >>> 3) More APIs and the rest of the implementation will come in subsequent
> >>>      versions
> >>>
> >>>    lib/st_ring/rte_st_ring.h | 567
> >> ++++++++++++++++++++++++++++++++++++++
> >>>    1 file changed, 567 insertions(+)
> >>>    create mode 100644 lib/st_ring/rte_st_ring.h
> >>>
> >>> diff --git a/lib/st_ring/rte_st_ring.h b/lib/st_ring/rte_st_ring.h
> >>> new file mode 100644 index 0000000000..8cb8832591
> >>> --- /dev/null
> >>> +++ b/lib/st_ring/rte_st_ring.h
> >>> @@ -0,0 +1,567 @@
> >>> +/* SPDX-License-Identifier: BSD-3-Clause
> >>> + * Copyright(c) 2023 Arm Limited
> >>> + */
> >>> +
> >>> +#ifndef _RTE_ST_RING_H_
> >>> +#define _RTE_ST_RING_H_
> >>> +
> >>> +/**
> >>> + * @file
> >>> + * RTE Signle Thread Ring (ST Ring)
> >>> + *
> >>> + * The ST Ring is a fixed-size queue intended to be accessed
> >>> + * by one thread at a time. It does not provide concurrent access
> >>> +to
> >>> + * multiple threads. If there are multiple threads accessing the ST
> >>> +ring,
> >>> + * then the threads have to use locks to protect the ring from
> >>> + * getting corrupted.
> >>
> >> You are basically saying the same thing three times here.
> >>
> >>> + *
> >>> + * - FIFO (First In First Out)
> >>> + * - Maximum size is fixed; the pointers are stored in a table.
> >>> + * - Consumer and producer part of same thread.
> >>> + * - Multi-thread producers and consumers need locking.
> >>
> >> ...two more times here. One might get the impression you really don't
> >> trust the reader.
> >>
> >>> + * - Single/Bulk/burst dequeue at Tail or Head
> >>> + * - Single/Bulk/burst enqueue at Head or Tail
> >>
> >> Does this not sound more like a deque, than a FIFO/circular buffer?
> >> Are there any examples where this functionality (the
> >> double-endedness) is needed in the DPDK code base?
> > I see, you are calling it 'deque' as well. Basically, this patch
> > originated due to a requirement in MLX PMD [1]
> >
> > [1]
> > https://github.com/DPDK/dpdk/blob/main/drivers/net/mlx5/mlx5_hws_cnt.h
> > #L381
> >
> >>
> >>> + *
> >>> + */
> >>> +
> >>> +#ifdef __cplusplus
> >>> +extern "C" {
> >>> +#endif
> >>> +
> >>> +#include <rte_st_ring_core.h>
> >>> +#include <rte_st_ring_elem.h>
> >>
> >> Is the intention to provide a ring with compile-time variable element
> >> size? In other words, where the elements of a particular ring
> >> instance has the same element size, but different rings may have different
> element sizes.
> >>
> >> Seems like a good idea to me, in that case. Although often you will
> >> have pointers, it would be useful to store larger things like small
> >> structs, and maybe smaller elements as well.
> > Yes, the idea is to make the element size flexible and also compile-time
> constant.
> >
> >>
> >>> +
> >>> +/**

<snip>