Skip to contentSkip to conversation

udp: optimize lookup of UDP sockets to by including destination address in the hash key

RFC PATCH In review Lucian Adrian Grijincu 4 participants 14 messages Nov 4, 2009 – Nov 6, 2009

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 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

powerpc/configs/ixia_ppc750_defconfig +3 -2
@@ -1,7 +1,7 @@
 #
 # Automatically generated make config: don't edit
-# Linux kernel version: 2.6.31-rc5
-# Thu Aug 13 17:15:17 2009
+# Linux kernel version: 2.6.31
+# Mon Nov  2 22:05:36 2009
 #
 # CONFIG_PPC64 is not set
 
@@ -287,6 +287,7 @@
 #
 # Networking options
 #
+CONFIG_NETDEV_HASHBITS=10
 # CONFIG_NET_SYSCTL_DEV is not set
 CONFIG_PACKET=y
 CONFIG_PACKET_MMAP=y
linux/udp.h +1 -1
@@ -45,7 +45,7 @@
 	return (struct udphdr *)skb_transport_header(skb);
 }
 
-#define UDP_HTABLE_SIZE		128
+#define UDP_HTABLE_SIZE		(1 << CONFIG_NETDEV_HASHBITS)
 
 static inline int udp_hashfn(struct net *net, const unsigned num)
 {
net/sock.h +18 -1
@@ -173,6 +173,7 @@
  *	@skc_bound_rx_dev_if: bound rx device index if != 0
  *	@skc_bound_tx_dev_if: bound tx device index if != 0
  *	@skc_bind_node: bind hash linkage for various protocol lookup tables
+ *	@skc_nulls_bind_node: bind hash linkage for UDP/UDP-Lite protocol
  *	@skc_prot: protocol handlers inside a network family
  *	@skc_net: reference to the network namespace of this socket
  *
@@ -195,7 +196,10 @@
 	unsigned char		skc_reuse;
 	int			skc_bound_rx_dev_if;
 	int			skc_bound_tx_dev_if;
-	struct hlist_node	skc_bind_node;
+	union {
+		struct hlist_node	skc_bind_node;
+		struct hlist_nulls_node skc_nulls_bind_node;
+	};
 	struct proto		*skc_prot;
 #ifdef CONFIG_NET_NS
 	struct net	 	*skc_net;
@@ -287,6 +291,7 @@
 #define sk_bound_rx_dev_if	__sk_common.skc_bound_rx_dev_if
 #define sk_bound_tx_dev_if	__sk_common.skc_bound_tx_dev_if
 #define sk_bind_node		__sk_common.skc_bind_node
+#define sk_nulls_bind_node	__sk_common.skc_nulls_bind_node
 #define sk_prot			__sk_common.skc_prot
 #define sk_net			__sk_common.skc_net
 #define sk_vlanprio		__sk_common.skc_vlanprio
@@ -495,6 +500,11 @@
 	return 0;
 }
 
+static __inline__ void __sk_nulls_del_bind_node_init_rcu(struct sock *sk)
+{
+	hlist_nulls_del_init_rcu(&sk->sk_nulls_bind_node);
+}
+
 static __inline__ int sk_nulls_del_node_init_rcu(struct sock *sk)
 {
 	int rc = __sk_nulls_del_node_init_rcu(sk);
@@ -523,6 +533,11 @@
 	hlist_nulls_add_head_rcu(&sk->sk_nulls_node, list);
 }
 
+static __inline__ void __sk_nulls_add_bind_node_rcu(struct sock *sk, struct hlist_nulls_head *list)
+{
+	hlist_nulls_add_head_rcu(&sk->sk_nulls_bind_node, list);
+}
+
 static __inline__ void sk_nulls_add_node_rcu(struct sock *sk, struct hlist_nulls_head *list)
 {
 	sock_hold(sk);
@@ -559,6 +574,8 @@
 	hlist_for_each_entry_safe(__sk, node, tmp, list, sk_node)
 #define sk_for_each_bound(__sk, node, list) \
 	hlist_for_each_entry(__sk, node, list, sk_bind_node)
+#define sk_nulls_for_each_bound(__sk, node, list) \
+	hlist_nulls_for_each_entry(__sk, node, list, sk_nulls_bind_node)
 
 /* Sock flags */
 enum sock_flags {
net/udp.h +6 -1
@@ -55,7 +55,8 @@
 	spinlock_t		lock;
 } __attribute__((aligned(2 * sizeof(long))));
 struct udp_table {
-	struct udp_hslot	hash[UDP_HTABLE_SIZE];
+	struct udp_hslot	hash[UDP_HTABLE_SIZE]; /* pair hash */
+	struct udp_hslot	port_hash[UDP_HTABLE_SIZE]; /* port hash */
 };
 extern struct udp_table udp_table;
 extern void udp_table_init(struct udp_table *);
@@ -117,7 +118,11 @@
 	BUG();
 }
 
+extern void __udp_lib_hash(struct sock *sk);
+extern void __udp_lib_unhash(struct sock *sk);
 extern void udp_lib_unhash(struct sock *sk);
+extern void udp_lock_hashes_bh(struct net *net, struct sock *sk, __u16 num);
+extern void udp_unlock_hashes_bh(struct net *net, struct sock *sk, __u16 num);
 
 static inline void udp_lib_close(struct sock *sk, long timeout)
 {
Kconfig +7 -0
@@ -25,6 +25,13 @@
 
 menu "Networking options"
 
+config NETDEV_HASHBITS
+	int "Network device hash size (10 => 1024, 14 => 16384)"
+	range 10 20
+	default 10
+	help
+	  Select network device hash size as a power of 2.
+
 config NET_SYSCTL_DEV
 	bool "Per device sysctl entries"
 	default y
ipv4/datagram.c +7 -1
@@ -19,6 +19,7 @@
 #include <net/sock.h>
 #include <net/route.h>
 #include <net/tcp_states.h>
+#include <net/udp.h>
 
 int ip4_datagram_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len)
 {
@@ -62,8 +63,13 @@
 	}
 	if (!inet->saddr)
 		inet->saddr = rt->rt_src;	/* Update source address */
-	if (!inet->rcv_saddr)
+	if (!inet->rcv_saddr) {
 		inet->rcv_saddr = rt->rt_src;
+		udp_lock_hashes_bh(sock_net(sk), sk, inet_sk(sk)->num);
+		__udp_lib_unhash(sk);
+		__udp_lib_hash(sk);
+		udp_unlock_hashes_bh(sock_net(sk), sk, inet_sk(sk)->num);
+	}
 	inet->daddr = rt->rt_dst;
 	inet->dport = usin->sin_port;
 	sk->sk_state = TCP_ESTABLISHED;
ipv4/udp.c +450 -86

648 lines not on this page · raw message

/*
* Creates a configurable number of UDP sockets with IPv4 and IPv6 addresses. *
* If run as receiver: counts the number of UDP datagrams received.
* - binds on all addresses on a given port and connects the socket to the
* corresponding IP address and port.
* - Afterwars, if epolls and count the corectly received datagrams.
* - not knowing when to stop listening it must be killed with CTRL+C (or
* other killing signel). On the first CTRL+C received prints the number of
* received datagrams; on the second CTRL+C received it exit()s.
*
* If run as sender: sends a configurable number of UDP datagrams to the
* receiver and prints the number of second passed.
* - binds on all addresses on a given port and connects the socket to the
* corresponding IP address and port.
* - epolls for a free sending slot and send a new datagram to the receiver.
* - at end prints the time it took to send all the datagrams.
*/

#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <termios.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/epoll.h>
#include <time.h>
#include <signal.h>

struct timespec tp;

struct epoll_data_t {
	int fd;
	int count;
	int disabled;
};

static void start_timer(struct timespec *tp)

{
	int rc = clock_gettime(CLOCK_REALTIME, tp);
	if (rc != 0) {
		perror("clock_realtime err in start_timer");
	}
}
static void end_timer(struct timespec *pold, const char * msg)
{
	int rc;
	long unsigned dsec, dnsec;
	struct timespec now;
	rc = clock_gettime(CLOCK_REALTIME, &now);
	if (rc != 0) {
		perror("clock_realtime err in end_timer");
	}

	if (now.tv_nsec < pold->tv_nsec) {
		dnsec = pold->tv_nsec - now.tv_nsec;
		dsec = now.tv_sec - pold->tv_sec - 1;
	} else {
		dnsec = now.tv_nsec - pold->tv_nsec;
		dsec = now.tv_sec - pold->tv_sec;
	}
	printf(">>> %s: %lu s  %lu ns \n", msg, dsec, dnsec);
}

static struct in_addr * make_ip4_addrs(int count, int suffix)

{
	int i = 0;
	char str[INET6_ADDRSTRLEN];
	struct in_addr * ret = malloc(sizeof(struct in_addr) * count);
	for(i = 0; i < count; i++) {
		snprintf(str, INET6_ADDRSTRLEN, "1.%d.%d.%d",
			 (i & 0xFF00) >> 8, i & 0xFF, suffix);
		int s = inet_pton(AF_INET, str, &ret[i]);
		if (s <= 0) {
			if (s == 0)
				fprintf(stderr, "ipv4 Not in presentation format");
			else
				perror("inet_pton");
			exit(EXIT_FAILURE);
		}
	}
	return ret;
}

static struct in6_addr * make_ip6_addrs(int count, int suffix)

{
	int i = 0;
	char str[INET6_ADDRSTRLEN];
	struct in6_addr * ret = malloc(sizeof(struct in6_addr) * count);
	for(i = 0; i < count; i++) {
		snprintf(str, INET6_ADDRSTRLEN, "1::%x:%x:%x",
			 (i / 0x10000), (i & 0xFFFF), suffix);
		int s = inet_pton(AF_INET6, str, &ret[i]);
		if (s <= 0) {
			if (s == 0)
				fprintf(stderr, "ipv6 Not in presentation format");
			else
				perror("inet_pton");
			exit(EXIT_FAILURE);
		}
	}
	return ret;
}

static int * make_sockets_(int count, int type)

{
	int i = 0;
	int * ret = malloc(sizeof(int)*count);
	for (i = 0; i < count; i++) {
		ret[i] = socket(type, SOCK_DGRAM, 0);
		if (ret[i] < 0) {
			perror("make_ipv4_sockets socket() failed");
			exit(EXIT_FAILURE);
		}
	}
	return ret;
}

static int * make_ip4_sockets(int count)

{
	return make_sockets_(count, AF_INET);
}

static int * make_ip6_sockets(int count)

{
	return make_sockets_(count, AF_INET6);
}

static void print_ip_err(void * in_addr, int addr_type)

{
	char str[INET6_ADDRSTRLEN];
	if (inet_ntop(addr_type, in_addr, str, INET6_ADDRSTRLEN) == NULL) {
		perror("inet_ntop");
		exit(EXIT_FAILURE);
	}
	fprintf(stderr, "failed for addr: %s\n", str);
}

static void for_all_set_sockopt(int * s, int count, int level, int optname, int val)

{
	int i = 0;
	int rc;
	for (i = 0; i < count; i++) {
		rc = setsockopt(s[i], level, optname, (int[]){val}, sizeof(int));
		if (rc != 0) {
			perror("setsockopt");
			exit(EXIT_FAILURE);
		}
	}
}

static void for_all_set_reuseaddr(int * s, int count)

{
	for_all_set_sockopt(s, count, SOL_SOCKET, SO_REUSEADDR, 1);
}

static void for_all_set_rcvbuf(int * s, int count, int size)

{
	for_all_set_sockopt(s, count, SOL_SOCKET, SO_RCVBUF, size);
}

static void for_all_set_sndbuf(int * s, int count, int size)

{
	for_all_set_sockopt(s, count, SOL_SOCKET, SO_SNDBUF, size);
}

static void for_all_set_nonblocking(int * s, int count)

{
	int rc, i;
	for (i = 0; i < count; i++) {
		rc = fcntl(s[i], F_SETFL, O_NONBLOCK);
		if (rc != 0) {
			fprintf(stderr, "i = %d\n", i);
			perror("fcntl O_NONBLOCK");
			exit(EXIT_FAILURE);
		}
	}

}

static void for_all_set_ipv6only(int * s, int count)

{
	for_all_set_sockopt(s, count, IPPROTO_IPV6, IPV6_V6ONLY, 1);
}

static void for_all_bind_or_connect_ip4(int * s, struct in_addr * ip4, int count, int port,
int (*f)(int sockfd, const struct sockaddr *addr,
socklen_t addrlen))

{
	int i, rc;
	struct sockaddr_in sin;
	sin.sin_family = AF_INET;
	sin.sin_port = htons(port);

	for (i = 0; i < count; i++) {
		sin.sin_addr = ip4[i];
		rc = f(s[i], (struct sockaddr*)&sin, sizeof(sin));
		if (rc != 0) {
			if (f == bind)
				perror("bind ipv4");
			else
				perror("connect ipv4");
			fprintf(stderr, "i = %d\n", i);
			print_ip_err(&ip4[i], AF_INET);
			exit(EXIT_FAILURE);
		}
	}
}

static void for_all_bind_or_connect_ip6(int * s, struct in6_addr * ip6, int count, int port,
int (*f)(int sockfd, const struct sockaddr *addr,
socklen_t addrlen))

{
	int i, rc;
	struct sockaddr_in6 sin6;
	sin6.sin6_family = AF_INET6;
	sin6.sin6_port = htons(port);

	for (i = 0; i < count; i++) {
		sin6.sin6_addr = ip6[i];
		rc = f(s[i], (struct sockaddr*)&sin6, sizeof(sin6));
		if (rc != 0) {
			if (f == bind)
				perror("bind ipv6");
			else
				perror("connect ipv6");
			fprintf(stderr, "i = %d\n", i);
			print_ip_err(&ip6[i], AF_INET6);
			exit(EXIT_FAILURE);
		}
	}
}

static void for_all_bind_ip4(int * s, struct in_addr * ip4, int count, int port)

{
	for_all_bind_or_connect_ip4(s, ip4, count, port, bind);
}
static void for_all_bind_ip6(int * s, struct in6_addr * ip6, int count, int port)
{
	for_all_bind_or_connect_ip6(s, ip6, count, port, bind);
}
static void for_all_connect_ip4(int * s, struct in_addr * ip4, int count, int port)
{
	for_all_bind_or_connect_ip4(s, ip4, count, port, connect);
}
static void for_all_connect_ip6(int * s, struct in6_addr * ip6, int count, int port)
{
	for_all_bind_or_connect_ip6(s, ip6, count, port, connect);
}

static struct epoll_data_t * for_all_add_to_epoll(int *s, int count, int epollfd, int is_sender)

{
	int rc;
	int i;
	struct epoll_event ev;
	struct epoll_data_t * data = calloc(count, sizeof(struct epoll_data_t));
	ev.events = EPOLLET;
	if (is_sender)
		ev.events |= EPOLLOUT;
	else
		ev.events |= EPOLLIN;
	for (i = 0; i < count; i++) {
		data[i].fd = s[i];
		ev.data.ptr = &data[i];
		rc = epoll_ctl(epollfd, EPOLL_CTL_ADD, s[i], &ev);
		if (rc == -1) {
			fprintf(stderr, "i = %d\n", i);
			perror("epoll_ctl: conn_sock");
			exit(EXIT_FAILURE);
		}
	}
	return data;
}

static void remove_from_epoll(int epollfd, int fd, struct epoll_event * ev)

{
	int rc;
	//printf("removing from epoll fd %d\n", fd);
	rc = epoll_ctl(epollfd, EPOLL_CTL_DEL, fd, ev);
	if (rc != 0)
		perror("epoll_ctl EPOLL_CTL_DEL");
}

static void disable_epoll_event_type(int epollfd, int fd, int event_type, struct epoll_event * ev)

{
	int rc;
	//printf("disabling event %d on fd=%d\n", event_type, fd);
	ev->events &= ~event_type;
	rc = epoll_ctl(epollfd, EPOLL_CTL_MOD, fd, ev);
	if (rc != 0)
		perror("epoll_ctl EPOLL_CTL_MOD");
}

static int handle_events(int epollfd, int fds_in_epoll, int is_sender, int max_packets, int datalen)

{
	char * databuf = malloc(datalen);
	struct epoll_event * events = malloc(sizeof(struct epoll_event) * fds_in_epoll);
	int todo = fds_in_epoll;
	int total = 0;

	for (;todo;) {
		int i, nfds;
		nfds = epoll_wait(epollfd, events, fds_in_epoll, -1);
		if (nfds == -1) {
			if (errno == EINTR) {
				printf("signal interrupted epoll_wait: total= %d\n", total);
				continue;
			}
			perror("epoll_wait");
			exit(EXIT_FAILURE);
		}
		for (i = 0; i < nfds; i++) {
			int fd, rc;
			struct epoll_event  *ev = &events[i];
			struct epoll_data_t *ed = ev->data.ptr;
			fd = ed->fd;
			if (ev->events & (EPOLLERR | EPOLLHUP)) {
				remove_from_epoll(epollfd, fd, ev);
				todo--;
				continue;
			}
			if (ev->events & EPOLLIN) {
				rc = recv(fd, databuf, datalen, 0);
				if (rc == -1) {
					//if (errno != ECONNREFUSED)
						perror("recv");
					continue;
				}
			}
			if (ev->events & EPOLLOUT) {
				rc = send(fd, databuf, datalen, 0);
				if (rc == -1) {
					//if (errno != ECONNREFUSED)
						perror("send");
					continue;
				}
			}
			if (total == 0)
				start_timer(&tp);
			total ++;
			ed->count ++;
			if (ed->count == max_packets) {
				remove_from_epoll(epollfd, fd, ev);
				todo--;
			}
		}
	}
	free(events);
	return total;
}

static int signal_was_delivered = 0;
static void handler(int unused)

{
	if (!signal_was_delivered)
		signal_was_delivered = 1;
	else
		exit(0);
}
static void add_signal()
{
	signal(SIGINT, handler);
}

#define stoi atoi
int main(int argc, char * argv[])

{
	int port = 1212;

	if (argc < 8) {
		printf("Usage: %s nr_interfaces4 nr_interfaces6 my_last_suffix their_last_suffix [s|r] max_packets datalen [recvsize]\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	int count4       = stoi(argv[1]);
	int count6       = stoi(argv[2]);
	int my_suffix    = stoi(argv[3]);
	int their_suffix = stoi(argv[4]);
	int is_sender    = argv[5][0] == 's';
	int max_packets  = stoi(argv[6]);
	int datalen      = stoi(argv[7]);
	int recvsize = -1;
	if (argc >= 8)
		recvsize = stoi(argv[8]);
	add_signal();
	printf("args = count4=%d count6=%d my_suffix=%d their_suffix=%d is_sender=%d max_packets=%d datalen=%d recvsize=%d\n",
	       count4, count6, my_suffix, their_suffix, is_sender, max_packets, datalen, recvsize);
	int epollfd;
	struct in_addr  * ip4_src = make_ip4_addrs(count4, my_suffix);
	struct in6_addr * ip6_src = make_ip6_addrs(count6, my_suffix);

	struct in_addr  * ip4_dst = make_ip4_addrs(count4, their_suffix);
	struct in6_addr * ip6_dst = make_ip6_addrs(count6, their_suffix);

	struct epoll_data_t *ep_data_ip4, *ep_data_ip6;

	int * s4 = make_ip4_sockets(count4);
	int * s6 = make_ip6_sockets(count6);
	int total = 0;

	for_all_set_reuseaddr(s4, count4);
	for_all_set_reuseaddr(s6, count6);

	if (recvsize != -1) {
		for_all_set_rcvbuf(s4, count4, recvsize);
		for_all_set_rcvbuf(s6, count6, recvsize);
	}
	//for_all_set_sndbuf(s4, count4, 1);
	//for_all_set_sndbuf(s6, count6, 1);

	start_timer(&tp);
	for_all_bind_ip6(s6, ip6_src, count6, port);
	for_all_bind_ip4(s4, ip4_src, count4, port);
	end_timer(&tp, "bound     IPv4 and IPv6");

	start_timer(&tp);
	for_all_connect_ip4(s4, ip4_dst, count4, port);
	for_all_connect_ip6(s6, ip6_dst, count6, port);
	end_timer(&tp, "connected IPv4 and IPv6");

	free(ip4_src); free(ip6_src);
	free(ip4_dst); free(ip6_dst);

	for_all_set_nonblocking(s4, count4);
	for_all_set_nonblocking(s6, count6);
	printf("done builing sockets.\n");


	epollfd = epoll_create(count4+count6);
	if (epollfd == -1) {
		perror("epoll_create");
		exit(EXIT_FAILURE);
	}
	ep_data_ip4 = for_all_add_to_epoll(s4, count4, epollfd, is_sender);
	ep_data_ip6 = for_all_add_to_epoll(s6, count6, epollfd, is_sender);
	printf("done builing epoll.\n");



	total = handle_events(epollfd, count4 + count6, is_sender, max_packets, datalen);
	end_timer(&tp, "handled all events");

	free(ep_data_ip4); free(ep_data_ip6);
	free(s4); free(s6);
	printf("done total= %d\n", total);
	return 0;
}
#1 lore raw
Quoted 69 lines · Lucian Adrian Grijincu

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

Quoted 6 lines

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.

I knew someone would do this kind of patch one day, I tried it one year ago :)

First of all, you are mixing several things in this patch.

Dont do this, its not possible for us to correctly review such complex patch.

Then, your patch is not based on net-next-2.6, and you really need to work on this tree.

Then, if you had worked on net-next-2.6, you whould have noticed UDP hash tables are now dynamically sized at boot.
An admin can even force a 65536 slots hash table for heavy duty UDP servers.

Then, last point : Say I have a machine with 65000 udp sockets bound to a different port, and a 65536 slots hash table, (sane values in fact, in order to have best performances), then your two phase lookup will be slower than the one-phase current lookup (two cache misses instead of one)

So your patch seems to solve a pathological case (where many udp sockets are bounded to a particular port, but on many different IPs), and slow down 99% of other uses.

Thanks

#2 lore raw
Quoted 3 lines · On Wednesday 04 November 2009 23:30:27 you wrote:

I knew someone would do this kind of patch one day, I tried it one year ago
:)

And I knew you would give us feedback, thanks ! You are unstoppable lately, how many of are out there? :)

Quoted 8 lines

First of all, you are mixing several things in this patch.

Dont do this, its not possible for us to correctly review such complex
patch.

Then, your patch is not based on net-next-2.6, and you really need to work
on this tree.

Yes, the patch is not in any shape for review, we just wanted some early feedback on the approach itself, and I've noticed its more likely to get feedback when code is posted.

Quoted 5 lines

Then, if you had worked on net-next-2.6, you whould have noticed UDP hash
tables are now dynamically sized at boot.
An admin can even force a 65536 slots hash table for heavy duty UDP
servers.

Quoted 9 lines

Then, last point : Say I have a machine with 65000 udp sockets bound to a
different port, and a 65536 slots hash table, (sane values in fact, in order to have best performances), then your two phase lookup will be slower than the one-phase current lookup (two cache misses instead of one)

So your patch seems to solve a pathological case (where many udp sockets
are bounded to a particular port, but on many different IPs), and slow down 99% of other uses.

Very true, the benchmark itself shows a significant overhead increase on the TX side and indeed this case is not very common. But for us its an important usecase.

Maybe there is a more clever way of fixing this specific use-case without hurting the common case?

Also, are there any other folks out there who would benefit by fixing this corner case?

Thanks,
tavi

#3 lore raw
Quoted 37 lines · Octavian Purdila
Quoted 3 lines · On Wednesday 04 November 2009 23:30:27 you wrote:

I knew someone would do this kind of patch one day, I tried it one year ago
:)

And I knew you would give us feedback, thanks ! You are unstoppable lately, how many of are out there? :)

Quoted 8 lines

First of all, you are mixing several things in this patch.

Dont do this, its not possible for us to correctly review such complex
patch.

Then, your patch is not based on net-next-2.6, and you really need to work
on this tree.

Yes, the patch is not in any shape for review, we just wanted some early feedback on the approach itself, and I've noticed its more likely to get feedback when code is posted.

Quoted 5 lines

Then, if you had worked on net-next-2.6, you whould have noticed UDP hash
tables are now dynamically sized at boot.
An admin can even force a 65536 slots hash table for heavy duty UDP
servers.

Quoted 9 lines

Then, last point : Say I have a machine with 65000 udp sockets bound to a
different port, and a 65536 slots hash table, (sane values in fact, in order to have best performances), then your two phase lookup will be slower than the one-phase current lookup (two cache misses instead of one)

So your patch seems to solve a pathological case (where many udp sockets
are bounded to a particular port, but on many different IPs), and slow down 99% of other uses.

Quoted 7 lines

Very true, the benchmark itself shows a significant overhead increase on the TX side and indeed this case is not very common. But for us its an important usecase.

Maybe there is a more clever way of fixing this specific use-case without hurting the common case?

Clever way ? Well, we will see :)

I now understand previous Lucian patch (best match) :)

Could you please describe your usecase ? I guess something is possible, not necessarly hurting performance of regular usecases :)

I have struct reorderings in progress to reduce number of cache lines read per socket from two to one. So this would reduce by 50% time to find a particular socket in the chain.

But if you *really* want/need 512 sockets bound to _same_ port, we probably can use secondary hash tables (or rbtree), as soon as we stack more than XX sockets on a particular slot.

At lookup, we check if extended hash table exists before doing normal rcu lookup.

Probably can be done under 300 lines of code.
On normal machines, these extra tables/trees would not be used/allocated

#4 lore raw
Quoted 4 lines · Eric Dumazet

I have struct reorderings in progress to reduce number of cache lines read per socket from two to one. So this would reduce by 50% time to find a particular socket in the chain.

Assuming that each access takes equal time seems like a rather dubious assumption. Consider caches.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#5 lore raw
Quoted 7 lines · Andi Kleen
Quoted 3 lines · Eric Dumazet

I have struct reorderings in progress to reduce number of cache lines read per socket from two to one. So this would reduce by 50% time to find a particular socket in the chain.

Assuming that each access takes equal time seems like a rather dubious assumption. Consider caches.

Yes, and it depends on SMP affinities too.

I assume cache is cold or even on other cpu (worst case), dealing with 100.000+ sockets or so...

If workload fits in one CPU cache/registers, we dont mind taking one or two cache lines per object, obviously.

#6 lore raw
Quoted 2 lines

I assume cache is cold or even on other cpu (worst case), dealing with 100.000+ sockets or so...

Other CPU cache hit is actually typically significantly faster than a DRAM access (unless you're talking about a very large NUMA system and a remote CPU far away)

Quoted 3 lines

If workload fits in one CPU cache/registers, we dont mind taking one or two cache lines per object, obviously.

It's more like part of your workload needs to fit.

For example if you use a tree and the higher levels fit into the cache, having a few levels in the tree is (approximately) free.

That's why I'm not always fond of large hash tables. They pretty much guarantee a lot of cache misses under high load, because they have little locality.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#7 lore raw
Quoted 6 lines · Andi Kleen
Quoted 2 lines

I assume cache is cold or even on other cpu (worst case), dealing with 100.000+ sockets or so...

Other CPU cache hit is actually typically significantly faster than a DRAM access (unless you're talking about a very large NUMA system and a remote CPU far away)

Even if data is dirty in remote CPU cache ?

I dont speak of shared data. (if data is shared, workload mostly fits caches)

Quoted 11 lines
Quoted 2 lines

If workload fits in one CPU cache/registers, we dont mind taking one or two cache lines per object, obviously.

It's more like part of your workload needs to fit.

For example if you use a tree and the higher levels fit into the cache, having a few levels in the tree is (approximately) free.

That's why I'm not always fond of large hash tables. They pretty much guarantee a lot of cache misses under high load, because they have little locality.

We already had this discussion Andi, and you know some servers handle 1.000.000+ sockets, 100.000+ frames per second on XX.XXX different flows, and a binary tree means 20 accesses before target. Only 5 or 6 first levels are in cache. Machine is barely usable.

hash table with 2.000.000 slots gives one or two accesses before target, and rcu is trivial with hash tables.

btree are ok for generalist workloads, and rcu is more complex.

#8 lore raw
Quoted 9 lines · Eric Dumazet
Quoted 6 lines · Andi Kleen
Quoted 2 lines

I assume cache is cold or even on other cpu (worst case), dealing with 100.000+ sockets or so...

Other CPU cache hit is actually typically significantly faster than a DRAM access (unless you're talking about a very large NUMA system and a remote CPU far away)

Even if data is dirty in remote CPU cache ?

Some cache protocols have to force dirty data through DRAM, but modern ones usually do not.

-Andi

#9 lore raw
In reply to Eric Dumazet
Quoted 8 lines · On Thursday 05 November 2009 01:32:18 you wrote:
Quoted 7 lines

Very true, the benchmark itself shows a significant overhead increase on the TX side and indeed this case is not very common. But for us its an important usecase.

Maybe there is a more clever way of fixing this specific use-case without hurting the common case?

Quoted 7 lines

Clever way ? Well, we will see :)

I now understand previous Lucian patch (best match) :)

Could you please describe your usecase ? I guess something is possible, not necessarly hurting performance of regular usecases :)

IIRC, we first saw this issue in VoIP tests with up to 16000 sockets bound on a certain port and IP addresses (each IP address is assigned to a particular interface). We need this setup in order to emulate lots of VoIP users each with a different IP address and possible a different L2 encapsulation.

Now, as a general note I should say that our usecases can seem absurd if you take them out of the network testing field :) but my _personal_ opinion is that a better integration between our code base and upstream code may benefit both upstream and us:

- for us it gives the ability to stay close to upstream and get all of the new shiny features without painful upgrades

- for upstream, even if most systems don't run into these scalability issues now, I see that some people are moving in that direction (see the recent PPP problems); also, stressing Linux in that regard can only make the code better
- as long as the approach taken is clean and sound

- we (or our customers) use a plethora of networking devices for testing so exposing Linux early to those devices can only help catching issues earlier

In short: expect more absurd patches from us :)

Quoted 8 lines

I have struct reorderings in progress to reduce number of cache lines read per socket from two to one. So this would reduce by 50% time to find a particular socket in the chain.

But if you *really* want/need 512 sockets bound to _same_ port, we probably
can use secondary hash tables (or rbtree), as soon as we stack more than XX sockets on a particular slot.

Quoted 6 lines

At lookup, we check if extended hash table exists before doing normal rcu lookup.

Probably can be done under 300 lines of code.
On normal machines, these extra tables/trees would not be used/allocated

Yep, that should work. Will respin the patch based on this idea and see what we get, but it will take a while.

Thanks,
tavi

#10 lore raw
Quoted 4 lines · Octavian Purdila

IIRC, we first saw this issue in VoIP tests with up to 16000 sockets bound on a certain port and IP addresses (each IP address is assigned to a particular interface). We need this setup in order to emulate lots of VoIP users each with a different IP address and possible a different L2 encapsulation.

Interesting case indeed, is it SIP 5060 port or RTP ports ? (I want to know how many messages per second you want to receive)

An rbtree with 16000 elements has 15 levels, its a lot, but OK for small trafic.

Quoted 14 lines

Now, as a general note I should say that our usecases can seem absurd if you take them out of the network testing field :) but my _personal_ opinion is that a better integration between our code base and upstream code may benefit both upstream and us:

- for us it gives the ability to stay close to upstream and get all of the new shiny features without painful upgrades

- for upstream, even if most systems don't run into these scalability issues now, I see that some people are moving in that direction (see the recent PPP problems); also, stressing Linux in that regard can only make the code better
- as long as the approach taken is clean and sound

Quoted 4 lines

- we (or our customers) use a plethora of networking devices for testing so exposing Linux early to those devices can only help catching issues earlier

In short: expect more absurd patches from us :)

I might cook something too :)

#11 lore raw
Quoted 7 lines · On Thursday 05 November 2009 18:36:50 you wrote:
Quoted 5 lines · Octavian Purdila

IIRC, we first saw this issue in VoIP tests with up to 16000 sockets bound on a certain port and IP addresses (each IP address is assigned to a particular interface). We need this setup in order to emulate lots of VoIP users each with a different IP address and possible a different L2 encapsulation.

Quoted 6 lines

Interesting case indeed, is it SIP 5060 port or RTP ports ? (I want to know how many messages per second you want to receive)

An rbtree with 16000 elements has 15 levels, its a lot, but OK for small trafic.

Yep the signaling port not the RTP port, and yes I think there is a fairly small amount of traffic and rbtree might work.

BTW, there is another side of this problem, the time to bind() those 16K sockets before starting the test - at least on 2.6.7 we didn't yet get to look at this issue on a recent kernel.

Thanks,
tavi

#12 lore raw
Quoted 14 lines · Octavian Purdila
Quoted 6 lines · On Thursday 05 November 2009 18:36:50 you wrote:
Quoted 5 lines · Octavian Purdila

IIRC, we first saw this issue in VoIP tests with up to 16000 sockets bound on a certain port and IP addresses (each IP address is assigned to a particular interface). We need this setup in order to emulate lots of VoIP users each with a different IP address and possible a different L2 encapsulation.

Quoted 6 lines

Interesting case indeed, is it SIP 5060 port or RTP ports ? (I want to know how many messages per second you want to receive)

An rbtree with 16000 elements has 15 levels, its a lot, but OK for small trafic.

Quoted 7 lines

Yep the signaling port not the RTP port, and yes I think there is a fairly small amount of traffic and rbtree might work.

BTW, there is another side of this problem, the time to bind() those 16K sockets before starting the test - at least on 2.6.7 we didn't yet get to look at this issue on a recent kernel.

Yes, this is O(N^2) algo :

0.3 seconds to bind 8000 UDP sockets on same port (different IPs) 1.5 secs / 12000 sockets
5.3 secs / 16000 sockets
18 secs / 24000 sockets
36 secs / 32000 sockets

#13 lore raw
In reply to Eric Dumazet
Quoted 26 lines · Eric Dumazet
Quoted 4 lines · Octavian Purdila

IIRC, we first saw this issue in VoIP tests with up to 16000 sockets bound on a certain port and IP addresses (each IP address is assigned to a particular interface). We need this setup in order to emulate lots of VoIP users each with a different IP address and possible a different L2 encapsulation.

Interesting case indeed, is it SIP 5060 port or RTP ports ? (I want to know how many messages per second you want to receive)

An rbtree with 16000 elements has 15 levels, its a lot, but OK for small trafic.

Quoted 13 lines

Now, as a general note I should say that our usecases can seem absurd if you take them out of the network testing field :) but my _personal_ opinion is that a better integration between our code base and upstream code may benefit both upstream and us:

- for us it gives the ability to stay close to upstream and get all of the new shiny features without painful upgrades

- for upstream, even if most systems don't run into these scalability issues now, I see that some people are moving in that direction (see the recent PPP problems); also, stressing Linux in that regard can only make the code better
- as long as the approach taken is clean and sound

Quoted 7 lines
Quoted 4 lines

- we (or our customers) use a plethora of networking devices for testing so exposing Linux early to those devices can only help catching issues earlier

In short: expect more absurd patches from us :)

I might cook something too :)

I tried the rbtree thing and suddenly realized it was not possible at all.

This is not possible because of all wildcards we have in UDP.

1) You can for example bind a socket s1 on address X, port p, dev eth0
2) You can bind socket s2 on adress X, port p (same values as previous socket), and dev eth1

As bindtodevice can be called after bind() itself, we can get several sockets with same rbtree key (port, address), but rbtree doesnt allow duplicates.

I'll try hash based extent.
(Ie allocate an hash extent for given primary hash slot in case number of sockets in this hash chain exceeds 10 or some threshold)

key hash would be function_of(port, address), duplicates allowed.

allocating 4096 bytes secondary hashes would divide per 1024 or 512 time of lookups, but keeping rcu lookup might be difficult.