Hi,
On 03/29/2016 10:54 AM, Bruce Richardson wrote:
> On Mon, Mar 28, 2016 at 06:48:07PM +0300, Lazaros Koromilas wrote:
>> Hi Olivier,
>>
>> We could have two threads (running on different cores in the general
>> case) that both succeed the cmpset operation. In the dequeue path,
>> when n == 0, then cons_next == cons_head, and cmpset will always
>> succeed. Now, if they both see an old r->cons.tail value from a
>> previous dequeue, they can get stuck in the while
>
> Hi,
>
> I don't see how threads reading an "old r->cons.tail" value is even possible.
> The head and tail pointers on the ring are marked in the code as volatile, so
> all reads and writes to those values are always done from memory and not
> cached
> in registers. No deadlock should be possible on that while loop, unless a
> process crashes in the middle of a ring operation. Each thread which updates
> the head pointer from x to y, is responsible for updating the tail pointer in
> a similar manner. The loop ensures the tail updates are in the same order as
> the
> head updates.
>
> If you believe deadlock is possible, can you outline the sequence of
> operations
> which would lead to such a state, because I cannot see how it could occur
> without
> a crash inside one of the threads.
I think the deadlock Lazaros describes could occur in the following
condition:
current ring state
r->prod.head = 0
r->prod.tail = 0
core 0 core 1
====================================================================
enqueue 0 object
cmpset(&r->prod.head, 0, 0)
core 0 is interrupted here
enqueue 1 object
cmpset(&r->prod.head, 0, 1)
copy the objects in box 0
while (r->prod.tail != prod_head))
r->prod.tail = prod_next
copy 0 object (-> nothing to do)
while (r->prod.tail != prod_head))
<loop forever>
I think this issue is indeed fixed by Lazaros' patch (I missed it
in previous review). However, I don't think this deadlock could
happen once we avoided the (n == 0) case.
Olivier
