inpcb: add single peer local port caching

[glebius]

Summary

A typical caching proxy problem is port allocation to backends. We
usually have a few of them, with thousands connections to each. Upon
creation of a new connection we need to find a new unique local port for
the peer:port. This is achieved by linear search in in_pcb_lport_dest().
The closer we get to the port exhaustion the more expensive this loop is.
It needs to be executed tens thousands of times to find a port or fail.

Address the problem by adding advisory negative cache that is lazily
allocated upon first conflict. Once the cache is in action we skip trying
those ports that are already marked in the cache. During the search we
may encounter a cache allocated by other lookup. In this case the caches
are merged into one. The expectation is that under a stable heavy load we
are going to stabilize at a very low number of allocated caches, ideally
one per peer:port. The cache is a bitset of IPPORT_MAX, which makes it 8k.
Unfortunately metadata pushes allocation size to 16k UMA bucket. However,
the expectation is that we are going to have a very few allocated, thus
current decisions is to not create a separate UMA zone.

[glebius]

Some performance data. The test that pushes local port allocation to the corner run on CURRENT as base, then D58131 as unlock and then on D58131 and this revision combined as cache. Using virtual machine with 8 CPUs.

x base
+ unlock
* cache
+------------------------------------------------------------------------------+
|*                                                                             |
|*                                                                             |
|*                                                                             |
|*                                                                             |
|*                                                                             |
|*                                                                             |
|*    +                                                                        |
|*    ++                                                                       |
|*    ++                                                                       |
|*    +++++                     xx x    x x       xx          x  x            x|
|A    |A|                        |____________M__A______________|              |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  10         14.44         36.24         21.28        22.525     7.2199696
+  10          2.39          4.14         2.835         3.021    0.59897041
Difference at 95.0% confidence
        -19.504 +/- 4.81339
        -86.5882% +/- 3.35841%
        (Student's t, pooled s = 5.12283)
*  10          0.14          0.21          0.14         0.147   0.022135944
Difference at 95.0% confidence
        -22.378 +/- 4.79693
        -99.3474% +/- 0.153552%
        (Student's t, pooled s = 5.10531)

First, I want to note that playing with different number of CPUs you may obtain very different results, as the test launches as many threads as CPUs are present. With more CPUs, e.g. 16 or 32, it likely will provide more amazing results as long as the host can provide them to the guest. Anyway, with my test 8 CPU test we got 150x improvement in the test that pushes local port allocation to the corner.

If run with a patch that counts how long does the cycle in in_pcb_lport_dest() loops, after 10 executions of the test with just D58131 we got:

net.inet.ip.lport_dest_histgram: 277448 109723 57270 34964 23172 15904 11043 7523 5436 3828 2868 2226 1628 1043 861 426

This reads as 426 times the loop required 32k to 64k iterations and 861 times 16k to 32k iterations. Note that on unmodified CURRENT you will obtain roughly 8 times smaller numbers, while the test will take 6-7 times longer to finish. This is explained by the fact that with single-locked inpcb database, threads are mostly waiting for each other rather than spinning in a search of an available port.
Anyway, adding this revision on top we got after 10 runs:

net.inet.ip.lport_dest_histgram: 277296 190500 74492 12327 730 18 0 0 0 0 0 0 0 0 0 0

This reads as 18 times the loop required 32 to 64 iterations and 730 times 16 to 32 iterations.

An interesting point is that at how many memory allocations are we going to stabilize as we run with some stable number of port numbers. I will provide this data later when we got some production testing results.

[vova_fbsd.ru]

worth to release the bit on closeing?

[vova_fbsd.ru]

sys/netinet/in_pcb.c

1656

replace to -

in_pcbremhash(inp);
in_pcb_lport_release(inp); // drop bit
in_pcb_lport_cache_detach(inp); // detach cache from pcb

?

[glebius]

• Don't forget to clear the bit on inpcb disconnect/free. Thanks, Vova!

[pouria]

sys/netinet/in_pcb.c

955

Can we use inp->inc_fibnum here for faster lookup instead of RT_ALL_FIBS? (and below calls to in[6]_pcblookup_internal...)

[glebius]

sys/netinet/in_pcb.c

955

That's a legitimate question! I think you are right here, but that needs to be checked.

Anyway, not related to this revision. Or am I missing something?

[pouria]

sys/netinet/in_pcb.c

955

Not related to caching of course. Just asking...

[pouria]

sys/netinet/in_pcb.c

846–848

Maybe?

873

use_cache only sets to true if fsa is not NULL.
At the beginning of this function we make sure we don't have lport_cache with mpass and only set it under fsa != NULL block.

943

We only have inp->inp_lport_cache != NULL when we match use_cache below, so It might be redundant to use use_cache here.

959

Not related to this revision, but comment above function said "lsa can be NULL for IPv6".

1011

We only have inp->inp_lport_cache != NULL when we match use_cache above, so It might be redundant to use use_cache here.

[pouria]

sys/netinet/in_pcb.h

387

Specifying the lock protecting it, maybe?