Date:	Wed, 04 Nov 2009 23:03:20 +0200
From:	Lucian Adrian Grijincu <lgrijincu@...acom.com>
To:	netdev@...r.kernel.org
CC:	Octavian Purdila <opurdila@...acom.com>
Subject: [RFC] [PATCH] udp: optimize lookup of UDP sockets to by including
 destination address in the hash key

Hi,

Before you look at the patch attached: I know it's not the prettiest of patches sent here. It's a work-in-progress and is ugly and incomplete (for example IPv6 is not properly updated to benefit this patch and may even be as buggy as hell right now).
I'm sending it here to ask for an opinion on the approach.

The current approach uses one single hash to lookup UDP sockets.
The key to the hash is calculated based on the port only.
This works well if there aren't many sockets bound to the same port, but becomes a linear linked list search for a setup with many UPD packets bound to the same port, which does not scale much.

In this patch the hashtable lookup key takes into consideration the address the socket is bound to too.
This will lead to better distribution for setup where there are many UDP sockets bound to the same port but different IP addresses.

There's a subtle bug lurking here: because some sockets may be bound to INADDR_ANY when checking whether a given UPD port is already taken one must search two buckets:
* one with the key computed from the port and for the IP address of the socket
* one with the key computed from the port and INADDR_ANY

Now if the address by which we must do the lookup is INADDR_ANY there's another problem: we can't just search it's own bucket and the bucket for INADDR_ANY (the same bucket twice) like above because there might be a socket bound to a specific address and the port we're trying to bind to.

In this case we could search the whole hash (which would take forever) or use another hash that is computed based on the port only (which this patch does).

There are other things to look after: when modifying the hashes we must take spin_locks or spin_lock_bhs. Because we now have two hashtables and one hashtable might be searched twice locks must be taken in the proper order.

I ran the attached UDP tester: it's a program that binds to a lot of UDP sockets and if run as a sender it sends lots of datagrams to the receiver which will just count the number of packets recevied.



== Performance stats ==
I ran this on a 2.6.31 with and without the patch on two powerpc single core processors connected directly by 100Mbps ethernet.

* nsocks      = number of IPv4 bound sockets
* ndgrams     = number of datagrams sent by each socket
* payloadlen  = the lenght of the UPD message sent
* send_time   = how many second did the sending operation take?
* recv_dgrams = how many datagrams were successfully received?


1. nsocks=512 ndgrams=2000 payloadlen=1
- without patch:
	* send_time   = 27s to 31s
	* recv_dgrams = 550 to 850
- with patch:
	* send_time   = 35s to 36s
	* recv_dgrams = 507000 to 516000

2. nsocks=512 ndgrams=4000 payloadlen=1
- without patch:
	* send_time   = 53s to 60s
	* recv_dgrams = 650 to 1100
- with patch:
	* send_time   = ~70s
	* recv_dgrams = 1010000 to 1034000

3. nsocks=512 ndgrams=4000 payloadlen=1000
- without patch:
	* send_time   = ~74s
	* recv_dgrams = 650
- with patch:
	* send_time   = ~88s
	* recv_dgrams = 995000

4. nsocks=256 ndgrams=2000 payloadlen=1
- without patch:
	* send_time   = 13s
	* recv_dgrams = 370 to 720
- with patch:
	* send_time   = 17s
	* recv_dgrams = 267000


As you can see this has a hit on total send time, but the number of received packets increases by two orders of magnitude.

I'd like hear your opinion about this approach.
If you'd like to test this, I'll be happy to port it to net-next and provide the patch.


--
Lucian

View attachment "upd-two-sock-hashes-v1.patch" of type "text/x-patch" (24696 bytes)

View attachment "stressbind.c" of type "text/x-csrc" (11693 bytes)

Powered by blists - more mailing lists