[PATCH 1/8] udp: add a counter into udp_hslot

[PATCH 1/8] udp: add a counter into udp_hslot

[Eric Dumazet]

Adds a counter in udp_hslot to keep an accurate count
of sockets present in chain.

This will permit to upcoming UDP lookup algo to chose
the shortest chain when secondary hash is added.

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
 include/net/udp.h |    8 ++++++++
 net/ipv4/udp.c    |    3 +++
 2 files changed, 11 insertions(+)

diff --git a/include/net/udp.h b/include/net/udp.h
index 22aa2e7..9167281 100644
--- a/include/net/udp.h
+++ b/include/net/udp.h
@@ -50,8 +50,16 @@ struct udp_skb_cb {
 };
 #define UDP_SKB_CB(__skb)	((struct udp_skb_cb *)((__skb)->cb))
 
+/**
+ *	struct udp_hslot - UDP hash slot
+ *
+ *	@head:	head of list of sockets
+ *	@count:	number of sockets in 'head' list
+ *	@lock:	spinlock protecting changes to head/count
+ */
 struct udp_hslot {
 	struct hlist_nulls_head	head;
+	int			count;
 	spinlock_t		lock;
 } __attribute__((aligned(2 * sizeof(long))));
 
diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index d5e75e9..ffc8376 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -218,6 +218,7 @@ found:
 	sk->sk_hash = snum;
 	if (sk_unhashed(sk)) {
 		sk_nulls_add_node_rcu(sk, &hslot->head);
+		hslot->count++;
 		sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
 	}
 	error = 0;
@@ -1053,6 +1054,7 @@ void udp_lib_unhash(struct sock *sk)
 
 		spin_lock_bh(&hslot->lock);
 		if (sk_nulls_del_node_init_rcu(sk)) {
+			hslot->count--;
 			inet_sk(sk)->inet_num = 0;
 			sock_prot_inuse_add(sock_net(sk), sk->sk_prot, -1);
 		}
@@ -1862,6 +1864,7 @@ void __init udp_table_init(struct udp_table *table, const char *name)
 	}
 	for (i = 0; i <= table->mask; i++) {
 		INIT_HLIST_NULLS_HEAD(&table->hash[i].head, i);
+		table->hash[i].count = 0;
 		spin_lock_init(&table->hash[i].lock);
 	}
 }

Re: [PATCH 1/8] udp: add a counter into udp_hslot

[Andi Kleen]

Eric Dumazet <eric.dumazet@gmail.com> writes:
>  
> +/**
> + *	struct udp_hslot - UDP hash slot
> + *
> + *	@head:	head of list of sockets
> + *	@count:	number of sockets in 'head' list
> + *	@lock:	spinlock protecting changes to head/count
> + */
>  struct udp_hslot {
>  	struct hlist_nulls_head	head;
> +	int			count;

Do you really need an int? On 64bit it's free due to the alignment, 
but on 32bit x86 it's costly and you blow up the table considerably,
increasing cache misses.
 
Again it would be nicer if that was a separate smaller table together
with the spinlock.

In theory could also put a short counter into the low level alignment
bits of the pointer and perhaps convert the spinlock to a bitlock?
Then all could collapse into a single pointer.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH 1/8] udp: add a counter into udp_hslot

[Eric Dumazet]

Andi Kleen a écrit :
> Eric Dumazet <eric.dumazet@gmail.com> writes:
>>  
>> +/**
>> + *	struct udp_hslot - UDP hash slot
>> + *
>> + *	@head:	head of list of sockets
>> + *	@count:	number of sockets in 'head' list
>> + *	@lock:	spinlock protecting changes to head/count
>> + */
>>  struct udp_hslot {
>>  	struct hlist_nulls_head	head;
>> +	int			count;
> 
> Do you really need an int? On 64bit it's free due to the alignment, 
> but on 32bit x86 it's costly and you blow up the table considerably,
> increasing cache misses.

Even a short (16 bits) might be too small for IXIACOM :)

On 32bit x86, size of hash table is 512 slots max.
(one slot per 2MB of LOWMEM, rounded to power of two)

You are speaking of <= 4096 bytes overhead :)

>  
> Again it would be nicer if that was a separate smaller table together
> with the spinlock.

Nice for space, not nice for fast path, because this means additional
cache miss to get the spinlock (multicast rx still needs to take spinlock),
and some guys want really fast (low latency) multicast rx.

> 
> In theory could also put a short counter into the low level alignment
> bits of the pointer and perhaps convert the spinlock to a bitlock?
> Then all could collapse into a single pointer.
> 

Not enough bits in low level alignment unfortunatly. We only could give a
hint (one bit is enough) of possibly long chain, but not allowing precise 
choice of shortest chain.

Once multicast is converted to RCU, then we wont need one spinlock per slot
(it wont be used in fast path, only at bind()/close() time)
and yes, we can use a separate small array to contain hashed spinlocks,
or even a single spinlock for CONFIG_BASE_SMALL :)

Re: [PATCH 1/8] udp: add a counter into udp_hslot

[Andi Kleen]

> > Do you really need an int? On 64bit it's free due to the alignment, 
> > but on 32bit x86 it's costly and you blow up the table considerably,
> > increasing cache misses.
> 
> Even a short (16 bits) might be too small for IXIACOM :)

True, but see below.


> 
> On 32bit x86, size of hash table is 512 slots max.
> (one slot per 2MB of LOWMEM, rounded to power of two)
> 
> You are speaking of <= 4096 bytes overhead :)

Well it's cache line overhead too. 32bit systems have often
small caches (i.e. Atom)

> 
> >  
> > Again it would be nicer if that was a separate smaller table together
> > with the spinlock.
> 
> Nice for space, not nice for fast path, because this means additional
> cache miss to get the spinlock (multicast rx still needs to take spinlock),
> and some guys want really fast (low latency) multicast rx.

When the spinlock use is mostly local it should be in cache
(that's the nice thing about small tables, they don't drop out of cache)

> 
> > 
> > In theory could also put a short counter into the low level alignment
> > bits of the pointer and perhaps convert the spinlock to a bitlock?
> > Then all could collapse into a single pointer.
> > 
> 
> Not enough bits in low level alignment unfortunatly. We only could give a
> hint (one bit is enough) of possibly long chain, but not allowing precise 
> choice of shortest chain.

Do we really need a precise answer here? I would assume an approximate
answer would be good enough using a saturating counter. 
e.g. if both have >N  just round robin.

Ok it would be tricky to decrement that again on unbind, but I assume just 
continuing to RR later wouldn't be too bad.

The question is just if there are enough bits even for that.

> Once multicast is converted to RCU, then we wont need one spinlock per slot
> (it wont be used in fast path, only at bind()/close() time)
> and yes, we can use a separate small array to contain hashed spinlocks,
> or even a single spinlock for CONFIG_BASE_SMALL :)

Or a bit spinlock in the bucket low pointer bits.

With that (and the saturating counter) even the 64bit table could be shortened to half.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.