Re: [PATCH] tcp: efficient port randomisation

[Michael Vittrup Larsen <michael.vittrup.larsen@ericsson.com>]

On Thursday 04 November 2004 19:01, Stephen Hemminger wrote:
> But because of the hashing most ports will be scattered all over the port
> space, because they come from different hosts.
>
> Also, Linux TCP will reuse ports if (saddr, daddr, sport) are different.
> Look at __tcp_v4_check_established.  This means that the ports actually
> have to be in use with real connections to the same host.

__tcp_v4_check_established is the linux version of the uniqueness test from 
the draft, and of course ports ports can be reused when at least one of the 
other parameters (saddr, daddr, sport) are different.

I focus on the situation where (saddr, daddr, sport) is constant since this is 
where we get collisions and need to try another port.  Not storing the port 
found to be unused will result in situations like:

tcp_rover_next is say 2000

Ports 2000-2010 are already used because you are browsing www.osdl.org

Your search will find 2011 to be unused after 10 retries and tcp_rover_next 
will be 2001.

Your next search (you continue to browse www.osdl.org) will result in 2012 - 
again after 10 retries.

In a simple browsing scenario like this, you will usually not have holes 
because of TCP TIME-WAIT and your rover will continue to lag behind and you 
will continue to make 10 retries on ports.

The question is then, when do the rover begin to lack behind?

Everytime you meet a long-lived connection in the port space your rover will 
lag one port behind the real 'unused' rover.  Using wget and browsing 
www.osdl.org may easily produce this problem.

I understand your argument for not holding the lock, and maybe the following 
algorithm is a compromise:

1. Use the current algorithm that does not hold the lock

2. If a port was found in first try, then exit (you have already
   incremented tcp_rover_next by 1 so this is up to date as per
   the old algorithm).

3. If more than one port try was necessary, compute the difference between
   the initial rover to the current unused port, and atomic_add() this to
   tcp_rover_next.

The only drawback of this is, that tcp_rover_next may 'run' a little too fast 
in contention cases, which only has theoretical impact on performance. Also, 
this only happens when we meet a long-lived connection, which we usually do 
not have many of.