[Click] NotifierQueue on multi-threaded Click problem.

[Eddie Kohler]

Hi Joonwoo,

The problem with this theory is that _head and _tail are each integers that 
fit in a single cache line, and therefore any update to those values are 
ALWAYS implemented atomically, by definition.

I think I agree with Cliff's comment that the variables needed to be 
"volatile", however.  In kernel, the "volatility" probably did not matter for 
simple pushes and pulls, but for the latest notifier updates, I think the 
volatility does matter.  The "atomic_uint32_t" variables are volatile by 
default; perhaps that is why atomic_uint32_t appears to work for you.

I disagree with your theory for several reasons; if the problem was really 
with "next != _head" and "_head != _tail", then a problem would occur with 
SimpleQueue type stuff, rather than notification.

Eddie


Joonwoo Park wrote:
> Hi Eddie,
> 
> 2007/9/7, Eddie Kohler <kohler at cs.ucla.edu>:
>> Hi Joonwoo,
>>
>> I'm really glad that we are making progress!!
>>
>> Now, for the Queue.  I agree that a simple test should be sufficient to
>> test race conditions.
>>
>> Can you verify that in your configuration, there are *never* two threads
>> pushing into a Queue at the same time, and there are *never* two threads
>> pulling from a Queue at the same time?  NotifierQueue and FullNoteQueue
>> are designed for *at most one* pushing thread and *at most one* pulling
>> thread at a time.  The pushing thread can be different from the pulling
>> thread, but NotifierQueue and FullNoteQueue don't support multiple
>> threads pushing at once (or pulling at once).  Send your configuration
>> to the list for us to check.
> 
> I posted it already, please check the link.
> https://pdos.csail.mit.edu/pipermail/click/attachments/20070708/8b2abbd9/infinitereply.obj
> 
>> If you are sure that there aren't multiple pushing threads (or pulling
>> threads), then take a look at the code.  What do you think the race
>> condition is?  Locking the full bodies of those push and pull functions
>> is not required.  Can you help me figure it out?
> 
> I think the enq() and deq() has problem.
> As you said, one enq() and one deq() can be run concurrently.
> But operation of the code, '_tail = next' of enq() and '_head =
> next_i(_head)' is not atomic (I mean the equalizer)
> because of _tail and _head is INT.
> Therefore the code 'if (next != _head) {' of push() and 'if (_head !=
> _tail)' of pull() cannot be worked correctly.
> So I think these are should be atomic.
> I am attaching patch and It made another process on my test.
> 
> -
> Signed-off-by: Joonwoo Park <joonwpark81 at gmail.com>
> 
> diff --git a/elements/standard/simplequeue.hh b/elements/standard/simplequeue.hh
> index 975c062..bee9e1c 100644
> --- a/elements/standard/simplequeue.hh
> +++ b/elements/standard/simplequeue.hh
> @@ -119,6 +119,7 @@ SimpleQueue::enq(Packet *p)
>      int next = next_i(_tail);
>      if (next != _head) {
>  	_q[_tail] = p;
> +	// While doing '_tail = X' pull() can see polluted _tail if it is not atomic
>  	_tail = next;
>  	int s = size();
>  	if (s > _highwater_length)
> @@ -150,6 +151,7 @@ SimpleQueue::deq()
>      if (_head != _tail) {
>  	Packet *p = _q[_head];
>  	assert(p);
> +	// While doing '_head = X' push() can see polluted _head if it is not atomic
>  	_head = next_i(_head);
>  	return p;
>      } else
> diff --git a/include/click/standard/storage.hh
> b/include/click/standard/storage.hh
> index 9b05a08..70da9c6 100644
> --- a/include/click/standard/storage.hh
> +++ b/include/click/standard/storage.hh
> @@ -1,11 +1,12 @@
>  // -*- c-basic-offset: 4 -*-
>   #ifndef CLICK_STORAGE_HH
>  #define CLICK_STORAGE_HH
> +#include <click/atomic.hh>
>  CLICK_DECLS
> 
>  class Storage { public:
> 
> -    Storage()				: _head(0), _tail(0) { }
> +    Storage()	{ }
> 
>      operator bool() const		{ return _head != _tail; }
>      bool empty() const			{ return _head == _tail; }
> @@ -26,8 +27,8 @@ class Storage { public:
>    protected:
> 
>      int _capacity;
> -    int _head;
> -    int _tail;
> +    atomic_uint32_t _head;
> +    atomic_uint32_t _tail;
> 
>  };
> 
> -
> 
> Jason Park (Joonwoo Park)
> 
>> Eddie
>>
>>