Convert the UDP hash lock to RCU

Change the UDP hash lock from an rwlock to RCU.

Signed-off-by Corey Minyard <[email protected]>

---
 include/net/udp.h |    9 +++++----
 net/ipv4/udp.c    |   47 +++++++++++++++++++++++++++--------------------
 net/ipv6/udp.c    |   17 +++++++++--------
 3 files changed, 41 insertions(+), 32 deletions(-)

include/net/udp.h +1 -1

index addcdc6..35aa104 100644
@@ -51,7 +51,7 @@ struct udp_skb_cb {
 #define UDP_SKB_CB(__skb)	((struct udp_skb_cb *)((__skb)->cb))
 
 extern struct hlist_head udp_hash[UDP_HTABLE_SIZE];
-extern rwlock_t udp_hash_lock;
+extern spinlock_t udp_hash_wlock;
 
 
 /* Note: this must match 'valbool' in sock_setsockopt */

@@ -112,12 +112,13 @@ static inline void udp_lib_hash(struct sock *sk)
 
 static inline void udp_lib_unhash(struct sock *sk)
 {

Me wondering what impact this synchronize_rcu() can have on mono-threaded VOIP applications using lot of UDP sockets. What is the maximum delay of this function ?

From: Eric Dumazet <[email protected]>
Date: Mon, 06 Oct 2008 23:22:31 +0200

Quoted 4 lines

Me wondering what impact this synchronize_rcu() can have on mono-threaded VOIP applications using lot of UDP sockets. What is the maximum delay of this function ?

The cost is enormous, we really can't use it here.

I have a patch that did top-level socket destruction using RCU, and that didn't use synchronize_rcu(), and that killed connection rates by up to %20.

I can only imagine what the cost would be if I had to add such a call in there.

Really, I can't consider these changes seriously, as-is.

Would using SLAB_DESTROY_BY_RCU be ok, or would that be too expensive?

Quoted 1 line · Corey Minyard

Would using SLAB_DESTROY_BY_RCU be ok, or would that be too expensive?

I tested skb destruction via RCU path, and got 2.5 times worse numbers with small-packets-bulk-transfer workload.

Quoted 5 lines · Evgeniy Polyakov

Quoted 1 line · Corey Minyard

Would using SLAB_DESTROY_BY_RCU be ok, or would that be too expensive?

I tested skb destruction via RCU path, and got 2.5 times worse numbers with small-packets-bulk-transfer workload.

Was this with regular RCU freeing? This will cool down the cacheline before frees. You need SLAB_DESTROY_BY_RCU to keep the objects cache hot.

But care is required -- SLAB_DESTROY_BY_RCU permits objects to be freed and reallocated while a reader holds a reference. The only guarantee is that the -type- of the data structure will not change while a reader holds a reference. With something like UDP, this might well be sufficient.

Quoted 4 lines · Paul E. McKenney

But care is required -- SLAB_DESTROY_BY_RCU permits objects to be freed and reallocated while a reader holds a reference. The only guarantee is that the -type- of the data structure will not change while a reader holds a reference. With something like UDP, this might well be sufficient.

Right so after the hash lookup operation you are not assured that the object has not been freed or even reallocated for a different purpose. So after finding the pointer to the object two things need to happen (under rcu_lock):

1. Verify that the object is still in use
2. Verify that the object is matching the hash

If not then the operation needs to be redone because we have a stale hash pointer.

Quoted 4 lines · Paul E. McKenney

But care is required -- SLAB_DESTROY_BY_RCU permits objects to be freed and reallocated while a reader holds a reference. The only guarantee is that the -type- of the data structure will not change while a reader holds a reference. With something like UDP, this might well be sufficient.

Right so after the hash lookup operation you are not assured that the object has not been freed or even reallocated for a different purpose. So after finding the pointer to the object two things need to happen (under rcu_lock):

1. Verify that the object is still in use
2. Verify that the object is matching the hash

If not then the operation needs to be redone because we have a stale hash pointer.

Quoted 2 lines

I tested skb destruction via RCU path, and got 2.5 times worse numbers with small-packets-bulk-transfer workload.

Was this with regular RCU freeing? This will cool down the cacheline before frees. You need SLAB_DESTROY_BY_RCU to keep the objects cache hot.

Quoted 4 lines · Christoph Lameter

Quoted 2 lines

I tested skb destruction via RCU path, and got 2.5 times worse numbers with small-packets-bulk-transfer workload.

Was this with regular RCU freeing? This will cool down the cacheline before frees. You need SLAB_DESTROY_BY_RCU to keep the objects cache hot.

I believe there were no SLAB_DESTROY_BY_RCU 2 yars ago :)

It was pure call_rcu(&skb->rcu, real_skb_freeing), where real_skb_freeing() just did usual kfree().

From: Eric Dumazet <[email protected]>
Date: Mon, 06 Oct 2008 23:22:31 +0200

Quoted 3 lines

Me wondering what impact this synchronize_rcu() can have on mono-threaded VOIP applications using lot of UDP sockets. What is the maximum delay of this function ?

The cost is enormous, we really can't use it here.

I have a patch that did top-level socket destruction using RCU, and that didn't use synchronize_rcu(), and that killed connection rates by up to %20.

I can only imagine what the cost would be if I had to add such a call in there.

Really, I can't consider these changes seriously, as-is.

Most UDP sockets are setup for long periods (RTP trafic), or if an application really wants to {open/send or receive one UDP frame/close} many sockets, it already hits RCU handling of its file structures and should not be slowed down that much.

By 'long period' I mean thousand of packets sent/received by each RTP session, being voice (50 packets/second) or even worse video...

Quoted 4 lines · Eric Dumazet

Most UDP sockets are setup for long periods (RTP trafic), or if an application really wants to {open/send or receive one UDP frame/close} many sockets, it already hits RCU handling of its file structures and should not be slowed down that much.

Quoted 2 lines

By 'long period' I mean thousand of packets sent/received by each RTP session, being voice (50 packets/second) or even worse video...

Does DNS with port randomization need short lived sockets?

Quoted 6 lines · Benny Amorsen

Quoted 4 lines · Eric Dumazet

Most UDP sockets are setup for long periods (RTP trafic), or if an application really wants to {open/send or receive one UDP frame/close} many sockets, it already hits RCU handling of its file structures and should not be slowed down that much.

I should have say 'Many' instead of 'Most' :)

Quoted 5 lines

Quoted 2 lines

By 'long period' I mean thousand of packets sent/received by each RTP session, being voice (50 packets/second) or even worse video...

Does DNS with port randomization need short lived sockets?

Yes very true, but current allocation of a random port can be very expensive, since we scan all the UDP hash table to select the smaller hash chain.

We stop the scan if we find an empty slot, but on machines with say more than 200 bound UDP sockets, they are probably no empty slots. (UDP_HTABLE_SIZE is 128)

bind(NULL port) algo is then O(N), N being number of bound UDP sockets.

So heavy DNS servers/proxies probably use a pool/range of pre-allocated sockets to avoid costs of allocating/freeing them ? If they dont care about that cost, the extra call_rcu() will be unnoticed.

For pathological (yet very common :) ) cases like single DNS query/answer, RCU would mean :

Pros :
- one few rwlock hit when receiving the answer (if any) Cons :
- one call_rcu() to delay socket freeing/reuse after RCU period.

So it might be a litle bit more expensive than without RCU

I agree I am more interested in optimizing UDP stack for heavy users like RTP servers/proxies handling xxx.000 packets/second than DNS users/servers. Shame on me :)

(2 weeks ago, Corey mentioned a 10x increase on UDP throughput on a 16-way machine, that sounds promising)

The idea of keeping chains short is the problem. That code should just be pulled because it doesn't help that much, and also creates bias on the port randomization.

From: Stephen Hemminger <[email protected]>
Date: Tue, 7 Oct 2008 16:07:29 +0200

Quoted 3 lines

The idea of keeping chains short is the problem. That code should just be pulled because it doesn't help that much, and also creates bias on the port randomization.

I have that patch from Vitaly Mayatskikh which does exactly this.

I keep looking at it, but I can't bring myself to apply it since I'm not completely convinced.

From: Stephen Hemminger <[email protected]>
Date: Tue, 7 Oct 2008 16:07:29 +0200

Quoted 3 lines

The idea of keeping chains short is the problem. That code should just be pulled because it doesn't help that much, and also creates bias on the port randomization.

I have that patch from Vitaly Mayatskikh which does exactly this.

I keep looking at it, but I can't bring myself to apply it since I'm not completely convinced.

Quoted 6 lines · David Miller

From: Stephen Hemminger <[email protected]>
Date: Tue, 7 Oct 2008 16:07:29 +0200

Quoted 3 lines

The idea of keeping chains short is the problem. That code should just be pulled because it doesn't help that much, and also creates bias on the port randomization.

Quoted 3 lines

I have that patch from Vitaly Mayatskikh which does exactly this. I keep looking at it, but I can't bring myself to apply it since I'm not completely convinced.

Vitaly patch might be appropriate if only few UDP ports are opened.

We could zap the code to search short chains and extend Vitaly's idea with following patch :

(quoted diff) +1 -0

+	}

	inet_sk(sk)->num = snum;
	sk->sk_hash = snum;
	if (sk_unhashed(sk)) {

net/ipv4/udp.c +1 -1

-		sk_add_node(sk, &udptable[udp_hashfn(net, snum)]);
+		sk_add_node(sk, &hslot->head);

		sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
	}

(quoted diff) +1 -0

+	write_unlock_bh(&hslot->lock);

	error = 0;

fail:

(quoted diff) +0 -1

-	write_unlock_bh(&udp_hash_lock);

	return error;
}

net/ipv4/udp.c int udp_lib_get_port(struct sock *sk, unsigned short snum, · line 185

Quoted 5 lines

net/ipv4/udp.c +5 -0

+	} else {
+		hslot = &udptable->hash[udp_hashfn(net, snum)];
+		write_lock_bh(&hslot->lock);
+		if (udp_lib_lport_inuse(net, snum, hslot, sk, saddr_comp))
+			goto fail;

The fail: label below should still unlock_bh when the above condition fails.

include/net/udp.h struct udp_skb_cb { · line 56

Quoted 6 lines · Eric Dumazet

include/net/udp.h +4 -2

-extern struct hlist_head udp_hash[UDP_HTABLE_SIZE];
-extern rwlock_t udp_hash_lock;
+struct udp_hslot {
+    struct hlist_head    head;
+    rwlock_t        lock;
+};

This structure should be aligned up to cacheline to reduce false sharing of more than one hslot.

net/ipv4/udp.c int udp_lib_get_port(struct sock *sk, unsigned short snum, · line 185

Quoted 6 lines

net/ipv4/udp.c +5 -0

+    } else {
+        hslot = &udptable->hash[udp_hashfn(net, snum)];
+        write_lock_bh(&hslot->lock);
+        if (udp_lib_lport_inuse(net, snum, hslot, sk, saddr_comp))
+            goto fail;

The fail: label below should still unlock_bh when the above condition fails.

Quoted 15 lines

net/ipv4/udp.c +3 -1

+    }
    inet_sk(sk)->num = snum;
    sk->sk_hash = snum;
    if (sk_unhashed(sk)) {
-        sk_add_node(sk, &udptable[udp_hashfn(net, snum)]);
+        sk_add_node(sk, &hslot->head);
        sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
    }
+    write_unlock_bh(&hslot->lock);
    error = 0;

fail:

-    write_unlock_bh(&udp_hash_lock);
    return error;
}

Introducing one rwlock per chain reduces latencies, for port randomization on heavily loaded UDP servers.

Some cleanups were done to ease review of following patch.

Signed-off-by Eric Dumazet <[email protected]>

RCUification of UDP hash tables

Goals are :

1) Optimizing handling of incoming Unicast UDP frames, so that no memory writes should happen in the fast path. Using an array of rwlocks (one per slot for example is not an option in this regard)

Note: Multicasts and broadcasts still will need to take a lock, because doing a full lockless lookup in this case is difficult.

2) No expensive operations in the socket bind/unhash phases :
- No expensive synchronize_rcu() calls.

- No added rcu_head in socket structure, increasing memory needs, but more important, forcing us to use call_rcu() calls, that have the bad property of making sockets structure cold. (rcu grace period between socket freeing and its potential reuse make this socket being cold in CPU cache).
David did a previous patch using call_rcu() and noticed a 20% impact on TCP connection rates.
Quoting Cristopher Lameter :
"Right. That results in cacheline cooldown. You'd want to recycle
the object as they are cache hot on a per cpu basis. That is screwed up by the delayed regular rcu processing. We have seen multiple regressions due to cacheline cooldown.
The only choice in cacheline hot sensitive areas is to deal with the complexity that comes with SLAB_DESTROY_BY_RCU or give up on RCU."

- Because udp sockets are allocated from dedicated kmem_cache, use of SLAB_DESTROY_BY_RCU can help here.

Theory of operation :
---------------------

As the lookup is lockfree (using rcu_read_lock()/rcu_read_unlock()), special attention must be taken by readers and writers.

Use of SLAB_DESTROY_BY_RCU is tricky too, because a socket can be freed, reused, inserted in a different chain or in worst case in the same chain while readers could do lookups in the same time.

In order to avoid loops, a reader must check each socket found in a chain really belongs to the chain the reader was traversing. If it finds a mismatch, lookup must start again at the begining. This *restart* loop is the reason we had to use rdlock for the multicast case, because we dont want to send same message several times to the same socket.

We use RCU only for fast path. Thus, /proc/net/udp still take rdlocks.

Signed-off-by Eric Dumazet <[email protected]>

---

include/net/sock.h |   37 ++++++++++++++++++++++++++++++++++++-
net/core/sock.c    |    3 ++-
net/ipv4/udp.c     |   35 ++++++++++++++++++++++++++---------
net/ipv4/udplite.c |    1 +
net/ipv6/udp.c     |   25 ++++++++++++++++++-------
net/ipv6/udplite.c |    1 +
6 files changed, 84 insertions(+), 18 deletions(-)

I will submit a new patch serie tomorrow, with :

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Oct 2008 23:45:15 +0100

Quoted 2 lines

I will submit a new patch serie tomorrow, with :

Quoted 3 lines

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

I very much look forward to this :-)

I like these changes and can't wait to add them to net-next-2.6

Quoted 5 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Oct 2008 23:45:15 +0100

Quoted 2 lines

I will submit a new patch serie tomorrow, with :

Quoted 5 lines

Quoted 3 lines

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

I very much look forward to this :-)
I like these changes and can't wait to add them to net-next-2.6

Thanks David, please find first updated patch 1

From: Eric Dumazet <[email protected]>
Date: Wed, 29 Oct 2008 09:23:03 +0100

Quoted 6 lines

Quoted 5 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Oct 2008 23:45:15 +0100

Quoted 2 lines

I will submit a new patch serie tomorrow, with :

Quoted 6 lines

Quoted 5 lines

Quoted 3 lines

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

I very much look forward to this :-)
I like these changes and can't wait to add them to net-next-2.6

Thanks David, please find first updated patch 1

Applied, please (re-)send the current version of patch 2 as well.

[PATCH] udp: udp_get_next() should use spin_unlock_bh()

Signed-off-by Eric Dumazet <[email protected]>

Quoted 5 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Oct 2008 23:45:15 +0100

Quoted 2 lines

I will submit a new patch serie tomorrow, with :

Quoted 7 lines

Quoted 3 lines

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

I very much look forward to this :-)

I like these changes and can't wait to add them to net-next-2.6

Quoted 12 lines · Eric Dumazet

Quoted 11 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Oct 2008 23:45:15 +0100

Quoted 5 lines

I will submit a new patch serie tomorrow, with :

Patch 1 : spinlocks instead of rwlocks, and bug spotted by Christian Bell

Patch 2 : splited on two parts (2 & 3) , one for IPV4, one for IPV6,

I very much look forward to this :-)

Quoted 2 lines

Quoted 1 line

I like these changes and can't wait to add them to net-next-2.6

Please find updated patch 2

Missing check in __udp6_lib_lookup() was added,
and based on spinlock version ([PATCH] udp: introduce struct udp_table and multiple spinlocks)

I believe there is a race in this patch:

(quoted diff) +7 -0

+    sk_for_each_rcu(sk, node, &hslot->head) {
+        /*
+         * 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;
        score = compute_score(sk, net, hnum, saddr, sport, daddr, dport, 

dif);
        if (score > badness) {
            result = sk;
            badness = score;
        }
    }

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.

I also might be nice to have a way to avoid recomputing the score the second time, perhaps using a sequence number of some type.

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.

Quoted 7 lines · Eric Dumazet

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.

Quoted 14 lines · Corey Minyard

Quoted 13 lines · Eric Dumazet

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."

Quoted 6 lines

Quoted 3 lines

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.

If we force a smp_wmb(), reader would fetch pointer to begin of list.

1) its udp_hashfn(net, sk->sk_hash) is != hash -> goto begin : Reader
will redo its scan : next pointer value had no meaning

2) its udp_hashfn(net, sk->sk_hash) is == hash
->next pointer "force reader" to rescan the chain, but wont find new
items.

In any case, we cannot lost an UDP message sent to a stable port (previously bound)

Thanks

--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 20 lines · Eric Dumazet

Quoted 5 lines · Corey Minyard

Quoted 3 lines · Eric Dumazet

Corey Minyard found a race added in commit 271b72c7fa82c2c7a795bc16896149933110672d (udp: RCU handling for Unicast packets.)

Quoted 9 lines

Quoted 7 lines

"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 :

Quoted 9 lines

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.

Quoted 30 lines · Paul E. McKenney

Quoted 27 lines · Eric Dumazet

Quoted 5 lines · Corey Minyard

Quoted 3 lines · Eric Dumazet

Corey Minyard found a race added in commit 271b72c7fa82c2c7a795bc16896149933110672d (udp: RCU handling for Unicast packets.)

Quoted 7 lines

Quoted 5 lines

"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.

Quoted 4 lines

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)

fetch next
calculate hash and compare to sk_hash
sk_hash is set to new value

So I think in the above cases, your case #2 is not necessarily valid without the barrier.

And another possible issue. If sk_hash is written before next, and CPU1 is interrupted before CPU2, CPU2 will continually spin on the list until CPU1 comes back and moves it to the new list. Note sure if that is an issue.

Quoted 35 lines · Corey Minyard

Quoted 34 lines · Paul E. McKenney

Quoted 18 lines · Eric Dumazet

Quoted 5 lines · Corey Minyard

Quoted 3 lines · Eric Dumazet

Corey Minyard found a race added in commit 271b72c7fa82c2c7a795bc16896149933110672d (udp: RCU handling for Unicast packets.)

Quoted 7 lines

Quoted 5 lines

"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 :

Quoted 9 lines

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.

Quoted 4 lines

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.

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.

Quoted 5 lines

fetch next
calculate hash and compare to sk_hash
sk_hash is set to new value

Quoted 3 lines

So I think in the above cases, your case #2 is not necessarily valid without the barrier.

And another possible issue. If sk_hash is written before next, and CPU1 is interrupted before CPU2, CPU2 will continually spin on the list until CPU1 comes back and moves it to the new list. Note sure if that is an issue.

Probably not. Previously, readers were spining on read_lock(), when a writer was inside its critical section (write_lock()/write_unlock()). So instead of spining inside read_unlock(), issuing stupid memory transactions, the readers can now spin reading hash chain and populate cpu cache :)

Quoted 53 lines · Eric Dumazet

Quoted 52 lines · Corey Minyard

Quoted 43 lines · Paul E. McKenney

Quoted 33 lines · Eric Dumazet

Quoted 15 lines · Corey Minyard

Quoted 13 lines · Eric Dumazet

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."

Quoted 8 lines

Quoted 4 lines

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

Quoted 7 lines

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.

Quoted 4 lines

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:

Quoted 7 lines

Quoted 2 lines

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.

Quoted 8 lines

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.

Quoted 12 lines

Quoted 11 lines

fetch next
calculate hash and compare to sk_hash
sk_hash is set to new value

So I think in the above cases, your case #2 is not necessarily valid without the barrier.

And another possible issue. If sk_hash is written before next, and CPU1 is interrupted before CPU2, CPU2 will continually spin on the list until CPU1 comes back and moves it to the new list. Note sure if that is an issue.

Quoted 5 lines

Probably not. Previously, readers were spining on read_lock(), when a writer was inside its critical section (write_lock()/write_unlock()). So instead of spining inside read_unlock(), issuing stupid memory transactions, the readers can now spin reading hash chain and populate cpu cache :)

Yes, I thought about that and thought I would point it out, but I agree, what you have is certainly better than spinning on a lock :).

-corey

Quoted 50 lines · Corey Minyard

Quoted 35 lines · Eric Dumazet

Quoted 34 lines · Corey Minyard

Quoted 33 lines · Paul E. McKenney

Quoted 18 lines · Eric Dumazet

Quoted 5 lines · Corey Minyard

Quoted 3 lines · Eric Dumazet

Corey Minyard found a race added in commit 271b72c7fa82c2c7a795bc16896149933110672d (udp: RCU handling for Unicast packets.)

Quoted 7 lines

Quoted 5 lines

"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 :

Quoted 9 lines

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.

Quoted 7 lines

Quoted 4 lines

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.

Quoted 5 lines

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 :)

Quoted 2 lines

Quoted 1 line

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. ;-)

Quoted 78 lines · Paul E. McKenney

Quoted 70 lines · Corey Minyard

Quoted 53 lines · Eric Dumazet

Quoted 52 lines · Corey Minyard

Quoted 42 lines · Paul E. McKenney

Quoted 33 lines · Eric Dumazet

Quoted 15 lines · Corey Minyard

Quoted 13 lines · Eric Dumazet

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."

Quoted 8 lines

Quoted 4 lines

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

Quoted 7 lines

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.

Quoted 5 lines

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:

Quoted 6 lines

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 7 lines

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.

Quoted 4 lines

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 ?

O

Quoted 13 lines

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.

Quoted 5 lines

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?

Quoted 1 line · Paul E. McKenney

O

..snip

Quoted 14 lines

Quoted 14 lines

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.

Quoted 9 lines

Quoted 6 lines

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!!! ;-)

My thought exactly ;-).

Quoted 10 lines

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.

I believe that is harmless, as re-scanning the same data should be fine.

Quoted 7 lines

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?

Kind of my thought, too. That's a lot of work to avoid a single smb_wmb() on the socket creation path. Plus this could be extra confusing.

Quoted 1 line · Paul E. McKenney

O

..snip

Quoted 13 lines

Quoted 13 lines

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.

Quoted 8 lines

Quoted 5 lines

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!!! ;-)

My thought exactly ;-).

Quoted 10 lines

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.

I believe that is harmless, as re-scanning the same data should be fine.

Quoted 7 lines

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?

Kind of my thought, too. That's a lot of work to avoid a single smb_wmb() on the socket creation path. Plus this could be extra confusing.

Quoted 9 lines · Eric Dumazet

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.

Quoted 8 lines

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?

Quoted 31 lines · Paul E. McKenney

Quoted 9 lines · Eric Dumazet

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.

Quoted 8 lines

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.

Quoted 6 lines

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)

Quoted 51 lines · Eric Dumazet

Quoted 31 lines · Paul E. McKenney

Quoted 9 lines · Eric Dumazet

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.

Quoted 8 lines

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.

Quoted 6 lines

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.

Quoted 5 lines

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.

[PATCH] udp: add a missing smp_wmb() in udp_lib_get_port()

Corey Minyard spotted a missing memory barrier in udp_lib_get_port()

We need to make sure a reader cannot read the new 'sk->sk_next' value and previous value of 'sk->sk_hash'. Or else, an item could be deleted from a chain, and inserted into another chain. If new chain was empty before the move, 'next' pointer is NULL, and lockless reader can not detect it missed following items in original chain.

This patch is temporary, since we expect an upcoming patch to introduce another way of handling the problem.

Signed-off-by Eric Dumazet <[email protected]>

From: Eric Dumazet <[email protected]>
Date: Wed, 29 Oct 2008 23:08:30 +0100

net/ipv4/udp.c void __init udp_table_init(struct udp_table *table) · line 1756

Quoted 6 lines

net/ipv4/udp.c +1 -1

@@ -1746,7 +1753,7 @@ void __init udp_table_init(struct udp_table *table)
 	int i;
 
 	for (i = 0; i < UDP_HTABLE_SIZE; i++) {
-		INIT_HLIST_HEAD(&table->hash[i].head);
+		table->hash[i].head.first = (struct hlist_node *)i;

Please hide this behind some list.h interface macro, even something as simple as INIT_HLIST_HEAD_NULLS(X, index) would suffice.

And as Corey said, the code needs more comments for something as clever as this! :-)

Quoted 14 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Wed, 29 Oct 2008 23:08:30 +0100

net/ipv4/udp.c void __init udp_table_init(struct udp_table · line 1757

Quoted 7 lines

net/ipv4/udp.c +1 -1

@@ -1746,7 +1753,7 @@ void __init udp_table_init(struct udp_table 
 *table)
     int i;
 
     for (i = 0; i < UDP_HTABLE_SIZE; i++) {
-        INIT_HLIST_HEAD(&table->hash[i].head);
+        table->hash[i].head.first = (struct hlist_node *)i;

Please hide this behind some list.h interface macro, even something as simple as INIT_HLIST_HEAD_NULLS(X, index) would suffice.

Quoted 3 lines

And as Corey said, the code needs more comments for something as clever as this! :-)

Yes I agree 100%, please give me one day to prepare a real patch, or else akpm will kill us :)

If we design something that could be reused, say for TCP sockets, we need to be able to handle very large number of 'NULL' pointers, say, up to 64*1024*1024

So lets use the low order bit, set to one for "NULL" pointers, and 0 for regular pointers.

This gives us 31 bits (or 63 bits) to store any valuable info :)

and all ...._nulls() macros would not need to know the max value (UDP_HTABLE_SIZE in UDP case), since all they have to do is a test ((unsigned long)pos & 1)

At iterator exit, pos would contain the 'index' value, (pos >> 1), to hide this implementation detail.

Quoted 31 lines · Paul E. McKenney

Quoted 9 lines · Eric Dumazet

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.

Quoted 8 lines

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.

Quoted 6 lines

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?

Quoted 34 lines · Eric Dumazet

Quoted 33 lines · Paul E. McKenney

Quoted 12 lines · Eric Dumazet

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;" :)

Quoted 7 lines

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.

Quoted 7 lines

Quoted 6 lines

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?

Ok, here is an updated and tested patch.

Thanks everybody

[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 introduce a new type of hlist implementation, named hlist_nulls, were we use the least significant bit of the 'ptr' to tell if its a "NULL" value or a pointer to an object. We expect to use this new hlist variant for TCP as well.

For UDP/UDP-Lite hash table, we use 128 different "NULL" values, (UDP_HTABLE_SIZE=128)

Using hlist_nulls 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 write memory barrier in udp_lib_get_port(), between sk->sk_hash update and sk->next update)

Signed-off-by Eric Dumazet <[email protected]>

---

Quoted 69 lines · On Thu, 30 Oct 2008 16:40:01 +0100 Eric Dumazet <[email protected]> wrote:

Quoted 34 lines · Eric Dumazet

Quoted 32 lines · Paul E. McKenney

Quoted 9 lines · Eric Dumazet

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.

Quoted 9 lines

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.

Quoted 7 lines

Quoted 7 lines

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?

Ok, here is an updated and tested patch.

Thanks everybody

[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 introduce a new type of hlist implementation, named hlist_nulls, were we use the least significant bit of the 'ptr' to tell if its a "NULL" value or a pointer to an object. We expect to use this new hlist variant for TCP as well.

For UDP/UDP-Lite hash table, we use 128 different "NULL" values, (UDP_HTABLE_SIZE=128)

Using hlist_nulls 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 write memory barrier in udp_lib_get_port(), between sk->sk_hash update and sk->next update)

Quoted 3 lines

Signed-off-by Eric Dumazet <[email protected]>

---

IMHO this goes over the edge into tricky hack. Is it really worth it? Is there a better simpler way?

It is annoying that it doesn't help the performance for multicast. However, I think the current patch will solve the DOS issue for multicast, since it switches to a normal spinlock and has a per-list lock.

Well, looking at current implementation, I found that udp_v4_mcast_next() doesnt take into account the 'struct net *net', so we have a bug here...

udp_v6_mcast_next() is buggy too (or at least its caller is)

David, please find a patch against net-2.6

Thanks

[PATCH] udp: multicast packets need to check namespace

Current UDP multicast delivery is not namespace aware.

Signed-off-by Eric Dumazet <[email protected]>

---
 net/ipv4/udp.c |   14 ++++++++------
 net/ipv6/udp.c |    8 ++++----
 2 files changed, 12 insertions(+), 10 deletions(-)

Quoted 9 lines

Well, looking at current implementation, I found that udp_v4_mcast_next() doesnt take into account the 'struct net *net', so we have a bug here...

udp_v6_mcast_next() is buggy too (or at least its caller is)

David, please find a patch against net-2.6

Thanks

Quoted 6 lines

[PATCH] udp: multicast packets need to check namespace

Current UDP multicast delivery is not namespace aware.

Signed-off-by Eric Dumazet <[email protected]>

Acked-by Pavel Emelyanov <[email protected]>

Quoted 20 lines · On Thu, 30 Oct 2008 16:40:01 +0100 Eric Dumazet <[email protected]> wrote:

[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 introduce a new type of hlist implementation, named hlist_nulls, were we use the least significant bit of the 'ptr' to tell if its a "NULL" value or a pointer to an object. We expect to use this new hlist variant for TCP as well.

For UDP/UDP-Lite hash table, we use 128 different "NULL" values, (UDP_HTABLE_SIZE=128)

Using hlist_nulls 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())

Quoted 5 lines

This also saves a write memory barrier in udp_lib_get_port(), between sk->sk_hash update and sk->next update)

Signed-off-by Eric Dumazet <[email protected]>

---

IMHO this goes over the edge into tricky hack. Is it really worth it? Is there a better simpler way?

More seriously Stephen, if the infrastructure is clean, and well tested on a relative simple case (UDP), it can then be deployed on a much more interesting protocol : TCP

The moment we switch to RCU, we have to accept the pain of really understand what we did. Details are scary yes.

[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 introduce a new type of hlist implementation, named hlist_nulls, were we use the least significant bit of the 'ptr' to tell if its a "NULL" value or a pointer to an object. We expect to use this new hlist variant for TCP as well.

For UDP/UDP-Lite hash table, we use 128 different "NULL" values, (UDP_HTABLE_SIZE=128)

Using hlist_nulls 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 write memory barrier in udp_lib_get_port(), between sk->sk_hash update and sk->next update)

Signed-off-by Eric Dumazet <[email protected]>

---
 include/linux/list_nulls.h    |   97 ++++++++++++++++++++++++++++++++
 include/linux/rculist.h       |   17 -----
 include/linux/rculist_nulls.h |   55 ++++++++++++++++++
 include/net/sock.h            |   50 ++++++++++++----
 include/net/udp.h             |    2
 net/ipv4/udp.c                |   40 ++++++-------
 net/ipv6/udp.c                |   22 ++++---
 7 files changed, 228 insertions(+), 55 deletions(-)

+/**
+ * ptr_is_a_nulls - Test if a ptr to struct hlist_nulls_node is a nulls

+ * @ptr: ptr to be tested
+ *
+ */

include/linux/list_nulls.h +4 -0

+static inline int is_a_nulls(struct hlist_nulls_node *ptr)
+{
+	return ((unsigned long)ptr & 1);
+}

1) Introduce hlist_nulls variant of hlist

hlist uses NULL value to finish a chain.
hlist_nulls variant use the low order bit set to 1 to signal an end marker. This allows to store many different end markers, so that some RCU lockless algos (used in TCP/UDP stack for example) can save some memory barriers in fast paths.

Here is a serie of three patches (based on net-next-2.6), to continue work with RCU on UDP/TCP/DCCP stacks

These patches are incredibly cool!