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