[Click] NotifierQueue on multi-threaded Click problem.

[Beyers Cronje]

Hi Cliff,

On 9/7/07, Cliff Frey <cliff at meraki.net> wrote:
>
> Do _head/_tail need to be declared volatile?  I'm not clear on the rules
> for c++ reordering operations...  It like adding some sort of barrier
> between these lines might be a good idea. (and the similar set for deq, but
> actually the assert() statement probably does that as a side effect...)
>
>     _q[_tail] = p;
>     _tail = next;



You were right, a memory barrier in enq() fixed the problem!

So the enq() code:
    _q[_tail] = p;
    _tail = next;
was actually executed as
    _tail = next;
    _q[_tail] = p;
While the second thread used _tail through deq() in between the above two
instructions, before _q[_tail] = p.

So the final enq() piece now looks like:
    _q[_tail] = p;
    __asm__ __volatile__ ("": : :"memory");  // Where is wmb() defined in
userland??
    _tail = next;

The above works on my i386 architecture, a more portable fix will be a
proper wmb() call.

also, I think that I'm confused about the difference between enq/deq and
> push/pull, but it might be worthwhile to add assert(p); to the push method.


I'm referencing enq/deq directly as my element is not in the normal Queue
push/pull path. To relate them, pull calls  deq() while push does exactly
what enq does. Not sure why push just doesnt just call enq ?

And a side note that might be outside the scope of this discussion.
>
> If we wanted to get rid of the one thread enq/deq constraint, couldn't we
> do it without locks if we used cmpxchg and some other factor to dictate that
> things were actually done their operation.


You can. There are a few methods to do this. From limited online research
the following algorithm seems to scale well:
http://delivery.acm.org/10.1145/380000/378611/p134-tsigas.pdf?key1=378611&key2=4422219811&coll=portal&dl=ACM&CFID=28858073&CFTOKEN=82193380

For interest sake, using mutexes I got ~270k pps throughput. Using the now
working non-locking queue I'm getting ~340k pps.

Beyers