Re: [PATCH 2/2] udp: RCU handling for Unicast packets.

[Eric Dumazet <dada1@cosmosbay.com>]

Paul E. McKenney a écrit :
> On Wed, Oct 29, 2008 at 01:28:15PM -0500, Corey Minyard wrote:
>> Eric Dumazet wrote:
>>> Corey Minyard a écrit :
>>>> Paul E. McKenney wrote:
>>>>> On Wed, Oct 29, 2008 at 05:09:53PM +0100, Eric Dumazet wrote:
>>>>>  
>>>>>> Corey Minyard a écrit :
>>>>>>   
>>>>>>> Eric Dumazet wrote:
>>>>>>>     
>>>>>>>> Corey Minyard found a race added in commit 
>>>>>>>> 271b72c7fa82c2c7a795bc16896149933110672d
>>>>>>>> (udp: RCU handling for Unicast packets.)
>>>>>>>>
>>>>>>>> "If the socket is moved from one list to another list in-between the 
>>>>>>>> time  the hash is calculated and the next field is accessed, and the 
>>>>>>>> socket  has moved to the end of the new list, the traversal will not 
>>>>>>>> complete  properly on the list it should have, since the socket will 
>>>>>>>> be on the end  of the new list and there's not a way to tell it's on 
>>>>>>>> a new list and  restart the list traversal.  I think that this can be 
>>>>>>>> solved by  pre-fetching the "next" field (with proper barriers) 
>>>>>>>> before checking the  hash."
>>>>>>>>
>>>>>>>> This patch corrects this problem, introducing a new 
>>>>>>>> sk_for_each_rcu_safenext()
>>>>>>>> macro.
>>>>>>>>         
>>>>>>> You also need the appropriate smp_wmb() in udp_lib_get_port() after 
>>>>>>> sk_hash is set, I think, so the next field is guaranteed to be changed 
>>>>>>> after the hash value is changed.
>>>>>>>       
>>>>>> Not sure about this one Corey.
>>>>>>
>>>>>> If a reader catches previous value of item->sk_hash, two cases are to 
>>>>>> be taken into :
>>>>>>
>>>>>> 1) its udp_hashfn(net, sk->sk_hash) is != hash   -> goto begin : Reader 
>>>>>> will redo its scan
>>>>>>
>>>>>> 2) its udp_hashfn(net, sk->sk_hash) is == hash
>>>>>>  -> next pointer is good enough : it points to next item in same hash 
>>>>>> chain.
>>>>>>     No need to rescan the chain at this point.
>>>>>>     Yes we could miss the fact that a new port was bound and this UDP 
>>>>>> message could be lost.
>>>>>>     
>>>>> 3) its udp_hashfn(net, sk-sk_hash) is == hash, but only because it was
>>>>> removed, freed, reallocated, and then readded with the same hash value,
>>>>> possibly carrying the reader to a new position in the same list.
>>>>>   
>>>> If I understand this, without the smp_wmb(), it is possible that the next 
>>>> field can be written to main memory before the hash value is written.  If 
>>>> that happens, the following can occur:
>>>>
>>>>  CPU1                    CPU2
>>>>  next is set to NULL (end of new list)
>>> Well, if this item is injected to the same chain, next wont be set to 
>>> NULL.
>>>
>>> That would mean previous writers deleted all items from the chain.
>> I put my comment in the wrong place, I wasn't talking about being injected 
>> into the same chain.
>>
>>> In this case, readers can see NULL, it is not a problem at all.
>>> List is/was empty.
>>> An application cannot complain a packet is not
>>> handled if its bind() syscall is not yet completed :)
>>>
>>> If item is injected on another chain, we will detect hash mismatch and 
>>> redo full scan.
>> If the item is injected onto the end of another chain, the next field will 
>> be NULL and you won't detect a hash mismatch.  It's basically the same 
>> issue as the previous race, though a lot more subtle and unlikely.  If you 
>> get (from the previous socket) an old value of "sk_hash" and (from the new 
>> socket) a new value of "next" that is NULL, you will terminate the loop 
>> when you should have restarted it.  I'm pretty sure that can occur without 
>> the write barrier.
> 
> One way of dealing with this is to keep a tail pointer.  Then, if the
> element containing the NULL pointer doesn't match the tail pointer seen
> at the start of the search, or if the tail pointer has changed,
> restart the search.  Memory barriers will be needed.  ;-)
> 

Hum... Another way of handling all those cases and avoid memory barriers
would be to have different "NULL" pointers.

Each hash chain should have a unique "NULL" pointer (in the case of UDP, it
can be the 128 values : [ (void*)0 .. (void *)127 ]

Then, when performing a lookup, a reader should check the "NULL" pointer
it get at the end of its lookup has is the "hash" value of its chain.

If not -> restart the loop, aka "goto begin;" :)

We could avoid memory barriers then.

In the two cases Corey mentioned, this trick could let us avoid memory barriers.
(existing one in sk_add_node_rcu(sk, &hslot->head); should be enough)

What do you think ?