speed regression in udp_lib_lport_inuse()

[Vitaly Mayatskikh <v.mayatskih@gmail.com>]

Hello!

I found your latest patches w.r.t. udp port randomization really solve
the "finding shortest chain kills randomness" problem, but
significantly slow down system in the case when almost every port is
in use. Kernel spends too much time trying to find free port number.

Try to compile and run this reproducer (after increasing open files
limit).

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <pthread.h>
#include <assert.h>

#define PORTS 65536
#define NP 64
#define THREADS

void* foo(void* arg)
{
	int s, err, i, j;
	struct sockaddr_in sa;
	int optval = 1, port;
	unsigned int p[PORTS] = { 0 };

	for (i = 0; i < PORTS * 100; ++i) {
		s = socket(PF_INET, SOCK_DGRAM, IPPROTO_UDP);
		assert(s > 0);
		memset(&sa, 0, sizeof(sa));
		sa.sin_addr.s_addr = htonl(INADDR_ANY);
		sa.sin_family = AF_INET;
		sa.sin_port = 0;
		err = bind(s, (const struct sockaddr*)&sa, sizeof(sa));

		getsockname(s, (struct sockaddr*)&sa, &j);
		port = ntohs(sa.sin_port);
		p[port] = s;
// free some ports
		if (p[port + 1]) {
			close(p[port + 1]);
			p[port + 1] = 0;
		}
		if (p[port - 1]) {
			close(p[port - 1]);
			p[port - 1] = 0;
		}
	}
}

int main()
{
	int i, err;
#ifdef THREADS
	pthread_t t[NP];

	for (i = 0; i < NP; ++i)
	{
		err = pthread_create(&t[i], NULL, foo, NULL);
		assert(err == 0);
	}
	for (i = 0; i < NP; ++i)
	{
		err = pthread_join(t[i], NULL);
		assert(err == 0);
	}
#else
	for (i = 0; i < NP; ++i) {
		err = fork();
		if (err == 0)
			foo(NULL);
	}
#endif
}

I ran glxgears and had these numbers:

$ glxgears 
3297 frames in 5.0 seconds = 659.283 FPS
3680 frames in 5.0 seconds = 735.847 FPS
3840 frames in 5.0 seconds = 767.891 FPS
3574 frames in 5.0 seconds = 714.704 FPS
-> here I ran reproducer
2507 frames in 5.1 seconds = 493.173 FPS
56 frames in 7.7 seconds =  7.316 FPS
14 frames in 5.1 seconds =  2.752 FPS
1 frames in 6.8 seconds =  0.146 FPS
9 frames in 7.6 seconds =  1.188 FPS
1 frames in 9.3 seconds =  0.108 FPS
12 frames in 5.5 seconds =  2.187 FPS
30 frames in 9.0 seconds =  3.338 FPS
25 frames in 5.1 seconds =  4.888 FPS
<- here I killed reproducer
1034 frames in 5.0 seconds = 206.764 FPS
3728 frames in 5.0 seconds = 745.541 FPS
3668 frames in 5.0 seconds = 733.496 FPS

Last stable kernel survives it more or less smoothly.

Thanks!
--
wbr, Vitaly