Re: [RFC PATCH] Linux kernel Wait-Free Concurrent Queue Implementation

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* Peter Hurley (peter@hurleysoftware.com) wrote:
> On Mon, 2013-03-11 at 17:36 -0400, Mathieu Desnoyers wrote:
> > +/*
> > + * Do not put head and tail on the same cache-line if concurrent
> > + * enqueue/dequeue are expected from many CPUs. This eliminates
> > + * false-sharing between enqueue and dequeue.
> > + */
> > +struct wfcq_head {
> > +	struct wfcq_node node;
> > +	struct mutex lock;
> > +};
> > +
> > +struct wfcq_tail {
> > +	struct wfcq_node *p;
> > +};
> 
> 
> If you want to force separate cachelines for SMP, this would be
> 
> struct wfcq_head {
> 	struct wfcq_node node;
> 	struct mutex lock;
> } ____cacheline_aligned_in_smp;
> 
> struct wfcq_tail {
> 	struct wfcq_node *p;
> } ____cacheline_aligned_in_smp;

Well, the thing is: I don't want to force it. The queue head and tail
can be used in a few ways:

1) tail used by frequent enqueue on one CPU, head used for frequent
   dequeues on another CPU. In this case, we want head/tail on different
   cache lines.
2) same scenario as 1), but head and tail are placed in per-cpu data
   of the two CPUs. We don't need to align each structure explicitly.
3) tail and head used locally, e.g. on the stack, as splice destination
   followed by iteration or dequeue from the same CPU. We don't want to
   waste precious memory space in this case, so no alignment.

So as you see, only (1) actually requires explicit alignment of head and
tail.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com