[Click] NotifierQueue on multi-threaded Click problem.

[Eddie Kohler]

P.S. Do you still see a problem without the ToHosts?


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
>>
>>