Subject: Re: [PATCH 2/3] udp: Use hlist_nulls in UDP RCU code

From: Eric Dumazet <[email-masked]>
Date: Wed, 19 Nov 2008 18:53:08 +0100

Paul E. McKenney a écrit :
> On Thu, Nov 13, 2008 at 02:15:19PM +0100, Eric Dumazet wrote:
>> This is a straightforward patch, using hlist_nulls infrastructure.
>>
>> RCUification already done on UDP two weeks ago.
>>
>> Using hlist_nulls permits us to avoid some memory barriers, both
>> at lookup time and delete time.
>>
>> Patch is large because it adds new macros to include/net/sock.h.
>> These macros will be used by TCP & DCCP in next patch.
> 
> Looks good, one question below about the lockless searches.  If the
> answer is that the search must complete undisturbed by deletions and
> additions, then:
> 
> Reviewed-by: Paul E. McKenney <[email-masked]>
> 
>> Signed-off-by: Eric Dumazet <[email-masked]>
>> ---
>> include/linux/rculist.h |   17 -----------
>> include/net/sock.h      |   57 ++++++++++++++++++++++++++++++--------
>> include/net/udp.h       |    2 -
>> net/ipv4/udp.c          |   47 ++++++++++++++-----------------
>> net/ipv6/udp.c          |   26 +++++++++--------
>> 5 files changed, 83 insertions(+), 66 deletions(-)
>>
> 
...
>>  	result = NULL;
>>  	badness = -1;
>> -	sk_for_each_rcu_safenext(sk, node, &hslot->head, next) {
>> -		/*
>> -		 * lockless reader, and SLAB_DESTROY_BY_RCU items:
>> -		 * We must check this item was not moved to another chain
>> -		 */
>> -		if (udp_hashfn(net, sk->sk_hash) != hash)
>> -			goto begin;
>> +	sk_nulls_for_each_rcu(sk, node, &hslot->head) {
>>  		score = compute_score(sk, net, saddr, hnum, sport,
>>  				      daddr, dport, dif);
>>  		if (score > badness) {
>> @@ -285,6 +274,14 @@ begin:
>>  			badness = score;
>>  		}
>>  	}
>> +	/*
>> +	 * if the nulls value we got at the end of this lookup is
>> +	 * not the expected one, we must restart lookup.
>> +	 * We probably met an item that was moved to another chain.
>> +	 */
>> +	if (get_nulls_value(node) != hash)
>> +		goto begin;
>> +
> 
> Shouldn't this check go -after- the check for "result"?  Or is this a
> case where the readers absolutely must have traversed a chain without
> modification to be guaranteed of finding the correct result?

Very good question

Yes, we really have to look at all the sockets, to find the one with higher score, not
one with a low score, and the one with higher score being ignored because we didnt examined it.

So we really must check we finished our lookup on the right chain end, not an alien one.

(Previous UDP code had a shortcut if we found the socket with the maximal possible score,
I deleted this test as it had basically 0.0001 % of chance being hit)

Thanks a lot for your patient review Paul.