git: 16bc669facc5 - main - libalias: index fully specified inbound links by remote endpoint
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sat, 10 Oct 2026 03:20:21 UTC
The branch main has been updated by glebius:
URL: https://cgit.FreeBSD.org/src/commit/?id=16bc669facc5eba33f7e215adce206bcf6ab2776
commit 16bc669facc5eba33f7e215adce206bcf6ab2776
Author: Paulo Fragoso <paulo@nlink.com.br>
AuthorDate: 2026-09-27 19:25:07 +0000
Commit: Gleb Smirnoff <glebius@FreeBSD.org>
CommitDate: 2026-10-10 02:35:10 +0000
libalias: index fully specified inbound links by remote endpoint
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).
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
Differential Revision: https://reviews.freebsd.org/D60083
---
sys/netinet/libalias/alias_db.c | 144 ++++++++++++++++++++++++++-----------
sys/netinet/libalias/alias_db.h | 8 ++-
sys/netinet/libalias/alias_local.h | 5 +-
3 files changed, 113 insertions(+), 44 deletions(-)
diff --git a/sys/netinet/libalias/alias_db.c b/sys/netinet/libalias/alias_db.c
index 24e05e06b21a..74ca8273956c 100644
--- a/sys/netinet/libalias/alias_db.c
+++ b/sys/netinet/libalias/alias_db.c
@@ -101,6 +101,31 @@ SPLAY_GENERATE(splay_in, group_in, in, cmp_in);
SPLAY_GENERATE(splay_internal_endpoint, alias_link, all.internal_endpoint,
cmp_internal_endpoint);
+/*
+ * Fully specified links of a group, ordered by the remote endpoint
+ * (dst_addr, dst_port). Links that share an endpoint (for example a
+ * permanent redirect that overrides an older one) are ordered newest
+ * first, which keeps the "most recent link wins" behaviour of the former
+ * list. A lookup needle has la == NULL and sorts before every real link
+ * with the same endpoint, so RB_NFIND() returns the newest one.
+ */
+static inline int
+cmp_full(struct alias_link *a, struct alias_link *b)
+{
+ if (a->dst_addr.s_addr != b->dst_addr.s_addr)
+ return (a->dst_addr.s_addr > b->dst_addr.s_addr ? 1 : -1);
+ if (a->dst_port != b->dst_port)
+ return (a->dst_port > b->dst_port ? 1 : -1);
+ if (a == b)
+ return (0);
+ if (a->la == NULL)
+ return (-1);
+ if (b->la == NULL)
+ return (1);
+ return (a->seq > b->seq ? -1 : 1);
+}
+RB_GENERATE_STATIC(full_in, alias_link, all.in_full, cmp_full);
+
static struct group_in *
StartPointIn(struct libalias *la,
struct in_addr alias_addr, u_short alias_port, int link_type,
@@ -119,12 +144,45 @@ StartPointIn(struct libalias *la,
grp->alias_addr = alias_addr;
grp->alias_port = alias_port;
grp->link_type = link_type;
- LIST_INIT(&grp->full);
+ RB_INIT(&grp->full);
LIST_INIT(&grp->partial);
SPLAY_INSERT(splay_in, &la->linkSplayIn, grp);
return (grp);
}
+/*
+ * First fully specified link of grp at or after (dst_addr, dst_port),
+ * or NULL. Callers check which fields actually match.
+ */
+static inline struct alias_link *
+FullInNFind(struct group_in *grp, struct in_addr dst_addr, u_short dst_port)
+{
+ struct alias_link needle = {
+ .la = NULL,
+ .dst_addr = dst_addr,
+ .dst_port = dst_port
+ };
+
+ return (RB_NFIND(full_in, &grp->full, &needle));
+}
+
+/*
+ * Fully specified link of grp for exactly (dst_addr, dst_port), or NULL.
+ * With several links for the same endpoint, the newest one is returned.
+ */
+static inline struct alias_link *
+FullInFind(struct group_in *grp, struct in_addr dst_addr, u_short dst_port)
+{
+ struct alias_link *lnk;
+
+ lnk = FullInNFind(grp, dst_addr, dst_port);
+ if (lnk != NULL &&
+ lnk->dst_addr.s_addr == dst_addr.s_addr &&
+ lnk->dst_port == dst_port)
+ return (lnk);
+ return (NULL);
+}
+
static int
SeqDiff(u_long x, u_long y)
{
@@ -281,14 +339,9 @@ GetNewPort(struct libalias *la, struct alias_link *lnk, int alias_port_param)
lnk->link_type == LINK_UDP)
continue;
- LIST_FOREACH(search_result, &grp->full, all.in) {
- if (lnk->dst_addr.s_addr ==
- search_result->dst_addr.s_addr &&
- lnk->dst_port == search_result->dst_port)
- break; /* found match */
- }
+ search_result = FullInFind(grp, lnk->dst_addr, lnk->dst_port);
if (search_result == NULL)
- break;
+ break; /* port is free */
}
if (i >= max_trials) {
@@ -521,21 +574,31 @@ DeleteLink(struct alias_link **plnk, int deletePermanent)
SPLAY_REMOVE(splay_out, &la->linkSplayOut, lnk);
}
- /* Adjust input table pointers */
- LIST_REMOVE(lnk, all.in);
-
- /* Adjust "internal endpoint" table pointer */
- SPLAY_REMOVE(splay_internal_endpoint,
- &la->linkSplayInternalEndpoint, lnk);
+ /*
+ * Adjust input table pointers. AddLink() put every
+ * non-PPTP link in its group, and the group is freed only
+ * when it is empty, so the group must exist here.
+ */
+ grp = StartPointIn(la, lnk->alias_addr, lnk->alias_port,
+ lnk->link_type, 0);
+#ifdef _KERNEL
+ KASSERT(grp != NULL, ("%s: link %p has no group",
+ __func__, lnk));
+#endif
+ if (lnk->flags & LINK_PARTIALLY_SPECIFIED)
+ LIST_REMOVE(lnk, all.in);
+ else
+ RB_REMOVE(full_in, &grp->full, lnk);
/* Remove intermediate node, if empty */
- grp = StartPointIn(la, lnk->alias_addr, lnk->alias_port, lnk->link_type, 0);
- if (grp != NULL &&
- LIST_EMPTY(&grp->full) &&
- LIST_EMPTY(&grp->partial)) {
+ if (RB_EMPTY(&grp->full) && LIST_EMPTY(&grp->partial)) {
SPLAY_REMOVE(splay_in, &la->linkSplayIn, grp);
free(grp);
}
+
+ /* Adjust "internal endpoint" table pointer */
+ SPLAY_REMOVE(splay_internal_endpoint,
+ &la->linkSplayInternalEndpoint, lnk);
}
break;
}
@@ -624,6 +687,7 @@ AddLink(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr,
lnk->flags = 0;
lnk->pflags = 0;
lnk->timestamp = LibAliasTime;
+ lnk->seq = la->linkSeq++;
/* Expiration time */
switch (link_type) {
@@ -727,7 +791,7 @@ AddLink(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr,
if (lnk->flags & LINK_PARTIALLY_SPECIFIED)
LIST_INSERT_HEAD(&grp->partial, lnk, all.in);
else
- LIST_INSERT_HEAD(&grp->full, lnk, all.in);
+ RB_INSERT(full_in, &grp->full, lnk);
/* Set up pointers for "internal endpoint" lookup table */
SPLAY_INSERT(splay_internal_endpoint,
@@ -902,40 +966,36 @@ _FindLinkIn(struct libalias *la, struct in_addr dst_addr,
switch (flags_in) {
case 0:
- LIST_FOREACH(lnk, &grp->full, all.in) {
- if (lnk->dst_addr.s_addr == dst_addr.s_addr &&
- lnk->dst_port == dst_port) {
- struct alias_link *found;
-
- found = UseLink(la, lnk);
- if (found != NULL)
- return (found);
- /* link expired */
- grp = StartPointIn(la, alias_addr, alias_port, link_type, 0);
- if (grp == NULL)
- return (NULL);
- break;
- }
+ lnk = FullInFind(grp, dst_addr, dst_port);
+ if (lnk != NULL) {
+ struct alias_link *found;
+
+ found = UseLink(la, lnk);
+ if (found != NULL)
+ return (found);
+ /* link expired */
+ grp = StartPointIn(la, alias_addr, alias_port, link_type, 0);
+ if (grp == NULL)
+ return (NULL);
}
break;
case LINK_UNKNOWN_DEST_PORT:
- LIST_FOREACH(lnk, &grp->full, all.in) {
- if(lnk->dst_addr.s_addr == dst_addr.s_addr) {
- lnk_unknown_dst_port = lnk;
- break;
- }
- }
+ /* full links always have dst_port != 0 */
+ lnk = FullInNFind(grp, dst_addr, 0);
+ if (lnk != NULL && lnk->dst_addr.s_addr == dst_addr.s_addr)
+ lnk_unknown_dst_port = lnk;
break;
case LINK_UNKNOWN_DEST_ADDR:
- LIST_FOREACH(lnk, &grp->full, all.in) {
- if(lnk->dst_port == dst_port) {
+ /* the tree is ordered by address first: still a linear scan */
+ RB_FOREACH(lnk, full_in, &grp->full) {
+ if (lnk->dst_port == dst_port) {
lnk_unknown_dst_addr = lnk;
break;
}
}
break;
case LINK_PARTIALLY_SPECIFIED:
- lnk_unknown_all = LIST_FIRST(&grp->full);
+ lnk_unknown_all = RB_MIN(full_in, &grp->full);
break;
}
diff --git a/sys/netinet/libalias/alias_db.h b/sys/netinet/libalias/alias_db.h
index 7175d0a50f4b..9efec0e45939 100644
--- a/sys/netinet/libalias/alias_db.h
+++ b/sys/netinet/libalias/alias_db.h
@@ -286,6 +286,7 @@ struct alias_link {
#define LINK_UNFIREWALLED 0x08
int timestamp; /* Time link was last accessed */
+ uint64_t seq; /* Insertion order within the instance */
#ifndef NO_USE_SOCKETS
int sockfd; /* socket descriptor */
#endif
@@ -293,7 +294,12 @@ struct alias_link {
union {
struct {
SPLAY_ENTRY(alias_link) out;
- LIST_ENTRY (alias_link) in;
+ union {
+ /* in grp->partial */
+ LIST_ENTRY (alias_link) in;
+ /* in grp->full */
+ RB_ENTRY(alias_link) in_full;
+ };
SPLAY_ENTRY(alias_link) internal_endpoint;
} all;
struct {
diff --git a/sys/netinet/libalias/alias_local.h b/sys/netinet/libalias/alias_local.h
index 7c1dcb0c8eb0..0e0cf0863d14 100644
--- a/sys/netinet/libalias/alias_local.h
+++ b/sys/netinet/libalias/alias_local.h
@@ -81,7 +81,8 @@ struct group_in {
u_short alias_port;
int link_type;
SPLAY_ENTRY(group_in) in;
- LIST_HEAD(, alias_link) full, partial;
+ RB_HEAD(full_in, alias_link) full; /* fully specified links */
+ LIST_HEAD(, alias_link) partial; /* partially specified links */
};
struct libalias {
@@ -112,6 +113,8 @@ struct libalias {
unsigned int fragmentIdLinkCount;
unsigned int fragmentPtrLinkCount;
unsigned int sockCount;
+ /* Insertion counter, orders links that share an endpoint */
+ uint64_t linkSeq;
/* log descriptor */
#ifdef _KERNEL
char *logDesc;