Re: [PATCH v4 1/5] ring: add 64-bit headtail structure

["Eads, Gage" <gage.eads@intel.com>]

> -----Original Message-----
> From: Ola Liljedahl [mailto:Ola.Liljedahl@arm.com]
> Sent: Tuesday, January 29, 2019 6:57 AM
> To: Eads, Gage <gage.eads@intel.com>; dev@dpdk.org
> Cc: jerinj@marvell.com; mczekaj@marvell.com; nd <nd@arm.com>;
> Richardson, Bruce <bruce.richardson@intel.com>; Ananyev, Konstantin
> <konstantin.ananyev@intel.com>; stephen@networkplumber.org;
> olivier.matz@6wind.com; arybchenko@solarflare.com
> Subject: Re: [PATCH v4 1/5] ring: add 64-bit headtail structure
> 
> On Mon, 2019-01-28 at 12:14 -0600, Gage Eads wrote:
> > 64-bit head and tail index widths greatly increases the time it takes
> > for them to wrap-around (with current CPU speeds, it won't happen
> > within the author's lifetime). This is fundamental to avoiding the ABA
> > problem -- in which a thread mistakes reading the same tail index in
> > two accesses to mean that the ring was not modified in the intervening
> > time -- in the upcoming non-blocking ring implementation. Using a
> > 64-bit index makes the possibility of this occurring effectively zero.
> Just an observation.
> The following invariant holds (using ring_size instead of mask):
> ∀ index: ring[index % ring_size].index % ring_size == index % ring_size i.e. the N
> (N=log2 ring size) lsb of ring[].index will always be the same (for a specific slot)
> so serve no purpose.
> 
> This means we don't have to store the whole index in each slot, it is enough to
> store "index / ring_size" (which I call the lap counter). This could be useful for an
> implementation for 32-bit platforms which support 64-bit CAS (to write the slot
> ptr & index (lap counter) atomically) and uses 64-bit head & tail indexes (to avoid
> the quick wrap around you would have with 32-bit ring indexes).
> 
> So
> ring[index % ring_size].lap = index / ring_size;
> 
> An implementation could of course use bitwise-and instead of modulo and
> bitwise- right shift instead of division. The 2-logaritm of ring_size should also be
> pre- calcucated and stored in the ring buffer metadata.
> 

That's a pretty interesting idea. The question is, with such a design, what should DPDK's minimum NB ring size be on 32-bit platforms?

If a ring entry is written on average every M cycles, then a lap occurs every M*N cycles and each counter repeats every M*N*2^32 cycles. If M=100 on a 2GHz system, then the counter repeats every

N=1: 3.33 minutes
...
N=256: 14.22 hours
N=512: 28.44 hours
N=1024: 2.37 days
...
N=16384: 37.92 days

I think a minimum size of 1024 strikes a good balance between not too burdensome and sufficiently low odds of ABA occurring.

Thanks,
Gage

[snip]