[Click] NotifierQueue on multi-threaded Click problem.
Eddie Kohler
kohler at cs.ucla.edu
Fri Sep 7 15:44:50 EDT 2007
OK, too bad.
I still doubt that replacing _head and _tail with atomic_uint32_t would fix
the underlying problem. The atomic_uint32_t, in kernel, is read with
atomic_read() and written with atomic_set(). Here's how they are implemented
on x86 (LINUX/include/asm-i386/atomic.h):
typedef struct { volatile int counter; } atomic_t;
#define atomic_read(v) ((v)->counter)
#define atomic_set(v,i) (((v)->counter) = (i))
I.e., just with reads and assignments! Once we declare the _head and _tail
variables as volatile, it's the same as atomic_uint32_t for reads and
assignments. (Atomic_uint32_t DOES make a difference for operations like +=,
-=, &=, dec_and_test; but _head and _tail are never touched that way.)
I am happy to be proved wrong, as usual; can you explain in more detail why
atomic operations would help? I am looking for a sample list of interleaved
instructions that would cause an error.
-*-
But: There are some remaining places where I can see potential race conditions
involving notification. For example:
Initial state: _head = 0, _tail = 2, _capacity = 1000
Thread 1 push(): int h = _head, t = _tail, nt = next_i(t);
=> int h = 0, t = 2, nt = 3;
=> Thread 1 sleeps
Thread 2 pull(): (executes once)
=> _head = 1, _tail = 2
Thread 2 pull(): (executes once)
=> _head = 2, _tail = 2
Thread 2 pull(): (executes, returns null, _sleepiness++)
Thread 2 pull(): => _empty_note.sleep()
Thread 1 push(): => wakes up
=> executes "if (s == 1) _empty_note.wake();"
=> But s == 3!
=> So notifier is not woken, the bug happens.
I have attached a diff to address these problems. Does this do anything?
Eddie
Joonwoo Park wrote:
> 2007/9/8, Eddie Kohler <kohler at cs.ucla.edu>:
>> P.S. Do you still see a problem without the ToHosts?
>>
>
> Yes I do,
> Problem still occurs without ToHosts and Tees.
> I tried 1652d76b7a7685105bcb244e7f58a55a9226c19e
>
> Joonwoo Park
-------------- next part --------------
A non-text attachment was scrubbed...
Name: notifieragain.diff
Type: text/x-patch
Size: 1020 bytes
Desc: not available
Url : https://pdos.csail.mit.edu/pipermail/click/attachments/20070907/11e83c92/notifieragain.bin
More information about the click
mailing list