From mboxrd@z Thu Jan  1 00:00:00 1970
From: Vitaly Mayatskikh <v.mayatskih@gmail.com>
Subject: Re: speed regression in udp_lib_lport_inuse()
Date: Fri, 23 Jan 2009 10:42:24 +0100
Message-ID: <m3bpty1hq7.wl%vmayatsk@redhat.com>
References: <m3sknbuqf9.wl%vmayatsk@redhat.com>
	<4978EE03.9040207@cosmosbay.com>
	<m3iqo7dkw4.wl%vmayatsk@redhat.com>
	<49790C02.90800@cosmosbay.com>
Mime-Version: 1.0 (generated by SEMI 1.14.6 - "Maruoka")
Content-Type: text/plain; charset=US-ASCII
Cc: Vitaly Mayatskikh <v.mayatskih@gmail.com>,
	David Miller <davem@davemloft.net>, netdev@vger.kernel.org
To: Eric Dumazet <dada1@cosmosbay.com>
Return-path: <netdev-owner@vger.kernel.org>
Received: from mail-ew0-f20.google.com ([209.85.219.20]:56619 "EHLO
	mail-ew0-f20.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1753740AbZAWJm2 (ORCPT
	<rfc822;netdev@vger.kernel.org>); Fri, 23 Jan 2009 04:42:28 -0500
Received: by ewy13 with SMTP id 13so3341574ewy.13
        for <netdev@vger.kernel.org>; Fri, 23 Jan 2009 01:42:26 -0800 (PST)
In-Reply-To: <49790C02.90800@cosmosbay.com>
Sender: netdev-owner@vger.kernel.org
List-ID: <netdev.vger.kernel.org>

At Fri, 23 Jan 2009 01:14:58 +0100, Eric Dumazet wrote:

> Could you try following patch ?
> 
> Thank you
> 
> [PATCH] udp: optimize bind(0) if many ports are in use
> 
> commit 9088c5609584684149f3fb5b065aa7f18dcb03ff
> (udp: Improve port randomization) introduced a regression for UDP bind() syscall
> to null port (getting a random port) in case lot of ports are already in use.
> 
> This is because we do about 28000 scans of very long chains (220 sockets per chain),
> with many spin_lock_bh()/spin_unlock_bh() calls.
> 
> Fix this using a bitmap (64 bytes for current value of UDP_HTABLE_SIZE)
> so that we scan chains at most once.
> 
> Instead of 250 ms per bind() call, we get after patch a time of 2.9 ms 

It's much better, thanks. FPS in glxgears now drops down only 2x
harder if compare with 2.6.28. However, this again kills randomness :)
Now number distribution is k*x^2 with x-axis zero in the (high - low)
/ 2. Try this program, it produces input file for Octave + Gnuplot.

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

#define PORTS 65536

int main()
{
	int s, err, i, j;
	char buf[256];
	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);
		memset(&sa, 0, sizeof(sa));
		sa.sin_addr.s_addr = htonl(INADDR_ANY);
		sa.sin_family = AF_INET;
		sa.sin_port = 0;
		setsockopt(s, IPPROTO_UDP, SO_REUSEADDR, &optval, sizeof(optval));
		err = bind(s, (const struct sockaddr*)&sa, sizeof(sa));
		getsockname(s, (struct sockaddr*)&sa, &j);
		port = ntohs(sa.sin_port);
		p[port]++;
		close(s);
	}
	printf("x = 32766:1:65535;\ny = [-100; ");
	for (i = 32767; i < PORTS; i++)
		printf("%d%s", p[i], (i + 1 < PORTS ? "; " : ""));
	printf("];\nplot(x,y,'.');pause;");
}

I was thinking about bitmap also, but in a bit different approach. It
is also uses bias (delta) value instead of exact port number. When we
get next random port value (from rng or in the next iteration), we can
calculate byte offset in that bitmap:

    A        B        C        D
76543210 76543210 7654321 076543210
11110111 11011110 1001111 011110111
            ^

We here land in the byte B in the marked bit position, but it is
already busy. If there're any free bits in this byte B, we can stop
further iterations and use any free bit. I don't think it can kill
randomness too much, because average bias will be small. May be it
only needs some more complicated logic for searching free bit in the
byte, because it's not good to do scanning always from the beginning.

--
wbr, Vitaly