libalias: index fully specified inbound links by remote endpoint

[paulo_nlink.com.br]

Summary

Inbound lookups find the (alias address, alias port, link type) group
with a splay tree and then walk grp->full, a list of every fully
specified link in that group, comparing the remote address and port.
With redirect_addr in front of a busy server, every client connection
to public:443 lands in the same group, so each inbound packet that is
not near the head of the list walks all of it. TCP links live up to
24 hours unless libalias sees a clean close, so the list can grow to
hundreds of thousands of entries and saturate a core at a few hundred
packets per second.

Keep the fully specified links of a group in an RB tree ordered by
(dst_addr, dst_port). Links that share an endpoint are ordered newest
first by a per-instance insertion counter, which keeps the "most recent
link wins" behaviour of the list (tested by 3_natin:2_portoverlap).
The counter is appended at the end of struct libalias because ipfw_nat
and ng_nat access fields of that structure directly.

Lookups with an unknown remote address and a known port still scan the
group. Each link grows by 16 bytes.

With ~170,000 links in one group, LibAliasIn() took 1-2 ms per packet
and one core saturated at ~720 packets/s. With this change it takes
2-4 us per packet and the offered 1,000 packets/s are handled with the
thread nearly idle.

Sponsored by: NLINK

Test Plan

Lab reproduction on 16.0-CURRENT (main-n289577), amd64, three VNET jails:

natlab_cli (198.51.100.10-.14) --epair-- natlab_rtr --epair-- natlab_srv (10.0.0.2)

natlab_rtr runs ipfw nat with the configuration that exposed the problem
in production:

ipfw nat 1 config ip 198.51.100.1 log same_ports unreg_only redirect_addr 10.0.0.2 198.51.100.50

The client sends 1,000 SYN/s to 198.51.100.50:443 for 300 s (non-blocking
connect() then close(), so one SYN per connection). natlab_srv drops the
SYNs, so every link stays for TCP_EXPIRE_INITIAL. Link counts come from
ipfw nat show log; latency from DTrace (fbt::LibAliasIn and
fbt::FindUdpTcpIn entry/return, quantize) plus profile-997 per thread.

Experiment A: all SYNs to one port (one group).
Experiment B (control): same rate spread over ports 1000-60000.

Experiment A	before (~170k links)	after (~141k links)
LibAliasIn per packet	1-2 ms	2-4 us
packets handled per 10 s	~7,200 (saturated)	~10,000 (all offered)
epair_task CPU	99%	0.0-0.15%
_FindLinkIn profile samples	9,911 of ~9,970	2

Before the change, experiment B (~280k links spread over many groups)
already ran at 2-4 us per packet, which shows the cost came from the
length of one group's list, not from the total number of links. After
the change, the cost of A did not grow between 60k and 141k links.

Userland (tests/sys/netinet/libalias, built on the same sources):

• 1_instance, 2_natout (including the UDP EIM cases), 3_natin: all pass. 3_natin:2_portoverlap caught an early version that broke ties between links with the same endpoint by pointer; ties are now ordered newest first, as with the list.
• perf: no regression (existing links ~0.14 us per packet before and after; random inbound 3.2 us -> 1.7 us).
• Additional one-group benchmark (100k links on one port): new SYN 1,252,985 ns -> ~600 ns; existing link 606,210 ns -> ~1,100 ns. I can submit it separately as tests/sys/netinet/libalias/perf_onegroup.c.

Kernel module checks:

• Only libalias.ko was rebuilt; ipfw nat show log works with the stock ipfw_nat.ko, which confirms struct libalias offsets are unchanged (an earlier version with linkSeq in the middle broke it).
• FullInFind()/FullInNFind() and the full_in RB functions are fully inlined at -O2 (no fbt probes, no symbols).

[adrian]

oh, nice catch! remind me again why they're all ending up in one group here?

[paulo_nlink.com.br]

Thanks! It comes from how inbound links are keyed.

In StartPointIn() all inbound traffic is indexed by
(alias_addr, alias_port, link_type), and the links inside the group
were a plain list, walked comparing (dst_addr, dst_port).

For connections from outside towards a redirect, the alias port is
the port the client connected to. When no link exists yet,
FindUdpTcpIn() does:

target_addr = FindOriginalAddress(la, alias_addr);
lnk = AddLink(la, target_addr, dst_addr, alias_addr,
    alias_port, dst_port, alias_port, link_type);

The case where I hit this was a 1:1 redirect in front of a busy web
server, a common setup in a hosting datacenter:

browser  <->  ipfw nat (redirect_addr)  <->  web server (443)
client        public address                 private address

Every browser connection to <public>:443 creates one link with alias
(<public>, 443, TCP), so all clients of the server land in the same
group. Only the client address and port differ, which is exactly what
the list was scanned for.

On a heavily used HTTPS service that list gets long: browsers open
several connections each, and many clients (mobile, CGNAT, scanners)
disappear without a FIN or RST that libalias can see. Those links stay
for TCP_EXPIRE_CONNECTED (24 h) or TCP_EXPIRE_INITIAL (300 s). Every
new SYN, and every packet whose link is not near the head, walks the
whole list. In production this pinned one core in the NAT's network
thread at only a few hundred packets per second, which is what the lab
in the test plan reproduces.

Outbound-initiated flows don't have this problem, because GetNewPort()
spreads them over many alias ports (many small groups). A published
server is the opposite: one alias port for all of its clients.

[paulo_nlink.com.br]

For the record, the per-alias-port list is as old as libalias itself.

Before the 2021 rework, StartPointIn() hashed inbound links on alias
address, alias port and link type only. The remote endpoint was not in
the hash, so every client of a redirected service fell into the same
bucket and was found with a linear walk:

3.0 (lib/libalias/alias_db.c):

n  = alias_addr.s_addr;
n += alias_port;
n += link_type;
return(n % LINK_TABLE_IN_SIZE);

13.0 (sys/netinet/libalias/alias_db.c), same hash plus a PPTP exception:

n = alias_addr.s_addr;
if (link_type != LINK_PPTP)
    n += alias_port;
n += link_type;
return (n % LINK_TABLE_IN_SIZE);

The 2021 rework split the groups properly with a splay tree, but kept
the list inside each group, so the cost for redirects stayed the same.

So natd, ipfw nat and ng_nat have all had this with busy redirected
services for a long time, and every supported branch is affected.

[adrian]

i think is this conceptually just fine. I'd like some other networking-y people to review it and ok it too!

[paulo_nlink.com.br]

Also posted to freebsd-net@ for wider review.

Testing: all 22 libalias ATF cases pass, the existing perf test shows
no regression, and "ipfw nat show log" works with the stock
ipfw_nat.ko (new field appended at the end of struct libalias).

[glebius]

sys/netinet/libalias/alias_db.c

101

Looks like you use it only in this file. Can you move cmp_full() right here?

157

You don't need underscores before inline in C files. Only in public headers that are installed in /usr/include and could be used for compilation by old compilers.

173

576–602

Just a suggestion: leave all the grp cleanup associated code together. Up to you to accept the suggestion or not.

This rewrite actually raised some questions. Can we assert that the lnk is either on the &grp->full or on &grp->partial? Can we assert that grp is always not NULL? Note that older code does LIST REMOVE unconditionally and doesn't crash. So if both above questions answers is "yes", then this can be optimized further.

sys/netinet/libalias/alias_local.h

171–173

You need this only if you target to MFC this code. For the 16.0-CURRENT feel free to check the structure layout and find an optimal placement.

[paulo_nlink.com.br]

Address glebius' review

[paulo_nlink.com.br]

sys/netinet/libalias/alias_db.c

576–602

Yes to both, as far as I can see:

• AddLink() is the only place that inserts a non-PPTP link in a group, and it always puts it in grp->full or grp->partial. LINK_PARTIALLY_SPECIFIED is set only there, from dst_addr/dst_port, and is never cleared (only LINK_PERMANENT is).
• dst_addr, dst_port, alias_addr, alias_port and link_type do not change after insertion. struct alias_link is private to alias_db.c, and GetNewPort() sets alias_port before the link is inserted. splay_out already depends on this.
• DeleteLink() is the only place that removes a link from a group, and the group is freed only when both lists are empty.

So in Diff 2 the group cleanup is together, the NULL checks are gone and there is a KASSERT(grp != NULL). The StartPointIn() lookup is not new, the old code already did it for the empty check.

Other comments are addressed in Diff 2 as well: cmp_full() moved next to RB_GENERATE_STATIC(), "inline" without underscores, and linkSeq now sits after sockCount. For the MFC I will keep it at the end of struct libalias.

Tested on 16.0-CURRENT (INVARIANTS): ~150k links in one group at 1,000 SYN/s, FindUdpTcpIn 2-4 us, epair_task 0.15%, and tearing down the lab with all links freed cleanly.

[glebius]

Paulo, do you have a public git repo (e.g. github) with your branch? I'd like to take your commit as is (with your name and your commit message) for pushing.

[paulo_nlink.com.br]

Thanks, Gleb! Here it is:

https://github.com/jailedengineer/freebsd-src/tree/libalias-full-rbtree

The top commit is 488b02966e34. For stable/15 and stable/14 I can prepare a version with linkSeq at the end of struct libalias, if that helps for the MFC.