lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Wed, 29 Oct 2008 22:22:57 -0500
From:	Corey Minyard <>
To:	Eric Dumazet <>
Cc:, David Miller <>,,,,
	Christoph Lameter <>,,,
	Christian Bell <>
Subject: Re: [PATCH 2/2] udp: RCU handling for Unicast packets.

Eric Dumazet wrote:
> Paul E. McKenney a écrit :
>> On Wed, Oct 29, 2008 at 09:00:13PM +0100, Eric Dumazet wrote:
>>> 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 ?
>> Kinky!!!  ;-)
>> Then the rcu_dereference() would be supplying the needed memory 
>> barriers.
>> Hmmm...  I guess that the only confusion would be if the element got
>> removed and then added to the same list.  But then if its pointer was
>> pseudo-NULL, then that would mean that all subsequent elements had been
>> removed, and all preceding ones added after the scan started.
>> Which might well be harmless, but I must defer to you on this one at
>> the moment.
>> If you need a larger hash table, another approach would be to set the
>> pointer's low-order bit, allowing the upper bits to be a full-sized
>> index -- or even a pointer to the list header.  Just make very sure
>> to clear the pointer when freeing, or an element on the freelist
>> could end up looking like a legitimate end of list...  Which again
>> might well be safe, but why inflict this on oneself?
> Well, for UDP case, hash table will be <= 65536 anyway, we can assume
> no dynamic kernel memory is in the range [0 .. 65535]
> Here is a patch (untested yet, its really time for a sleep for me ;) )
> [PATCH] udp: Introduce special NULL pointers for hlist termination
> In order to safely detect changes in chains, we would like to have 
> different
> 'NULL' pointers. Each chain in hash table is terminated by an unique 
> 'NULL'
> value, so that the lockless readers can detect their lookups evaded from
> their starting chain.
> We define 'NULL' values as ((unsigned long)values < UDP_HTABLE_SIZE)
> This saves memory barriers (a read barrier to fetch 'next' pointers
> *before* checking key values) we added in commit 
> 96631ed16c514cf8b28fab991a076985ce378c26 (udp: introduce 
> sk_for_each_rcu_safenext())
> This also saves a missing memory barrier spotted by Corey Minyard (a 
> write one in udp_lib_get_port(), between sk_hash update and ->next 
> update)
I think you are right, this will certainly perform a lot better without 
the read barrier in the list traversal.  I haven't seen any problems 
with this approach, though it's unusual enough to perhaps warrant some 
extra comments in the code.

You do need to modify udp_lib_unhash(), as sk_del_node_init_rcu() will 
do a NULL check on the ->next value, so you will need a special version 
of that as well.

To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to
More majordomo info at

Powered by blists - more mailing lists