[Click] NotifierQueue on multi-threaded Click problem.

[Joonwoo Park]

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