From nobody Sat Oct 10 03:20:21 2026 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4j1prq1rCBz6jkt5 for ; Sat, 10 Oct 2026 03:20:27 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange x25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "YR2" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 4j1prp6fn5z4yjl for ; Sat, 10 Oct 2026 03:20:26 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1791602426; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=0MzLfkIbtPsaPa/u8xn/wA6N17BcJLEKTcaqGLsvJws=; b=vJjcDf6xCOgGLI5qVUWiPjTuTVGG8kK2PHm/TeP+8JxpGvTdNpBc50x5TOi9y8BOS/MBZB JDR99/AqedB8zuQCgRvSJw2rqDJ9lU2HM34KpI8JJr2a1gdi4eD7CLSUvWDyWF1UBMQElP 4lDBtK30j3APEp84i2EaV19RbKR9Io/JCaZhbS+SvEmaVZxuibPv2+dHNnuUErMIOKRJ3/ Z3YYRYEGUYH9MnrkWiV6eE/EizT7t3qu5CYiw7ZCKzEU1j3IKEoAWeqOH1YFTXordbn2mO OjSDPdVk2AlIUJcz/0RxfS/CmVdI3UgfedpX1bHgUldoI446Y/vlJn0jeo2m/g== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1791602426; b=fYAqbMo+VbnZT99bFLNI3a5RWEid5jX9T7kauLiwjBBUU/5y4U4nNvJa6LYw3N3TgVtti/ 24Y2pbktYOom9W64ctJA7Z4CfzT9iTv/mnAAl+iXmU7XozcaymIKg+EGBfTQDU/sebky3U eF9yhTxXQHs+usx7V8YN4st06H8lzqJI5oNGLguJ3HYr4Ll+R7ELFjGWrudoUbXBiBwrBp cC12lC6BiMndQmV5qZaeRLA2qSYfnJLWexsW/U3s1DtTrHFo9JGBoiS6FXSrZzzwWj6VhJ 8EZv6WFLjFfO1YojLvI/bP5cXUsuiOxcFzlWMgPWq6JiL9qZggbG5e+YeFY/Nw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1791602426; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=0MzLfkIbtPsaPa/u8xn/wA6N17BcJLEKTcaqGLsvJws=; b=BIAnPxRtXtDnckix2RHlwODs2slglj4c4/iRhtoc/E+Pnj8NwbPCgNqbNP+HBokYqNbR1Y /dlJpgNDCBliZt4Sq6dgJ7wRqXL2Ojl6y34fJwHO4ztjBg12mCcbDrHXDVk5EHCM/1Emak zmBGhAoeH2NxguLMr6YDIbml75NfVJRLGcr+e88pMuJG8binPFTZX4l7y93pAK0tAxOq3E w1/nrkllhHwu0H43ekQRKLa3v8m0fdY3QBUV34opXyI8n57Bx/UDy+iQ5fyI4VkeWLRQX4 0eDBN2bRRbCdFXTXK3o1ILULZOvG4Sdqaz4UeBGK2+4yDiPr0kxKbnGoj+n3CA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4j1prp59rlzg1t for ; Sat, 10 Oct 2026 03:20:26 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 39a57 by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Sat, 10 Oct 2026 03:20:21 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Cc: Paulo Fragoso From: Gleb Smirnoff Subject: git: 16bc669facc5 - main - libalias: index fully specified inbound links by remote endpoint List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@FreeBSD.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: glebius X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 16bc669facc5eba33f7e215adce206bcf6ab2776 Auto-Submitted: auto-generated Date: Sat, 10 Oct 2026 03:20:21 +0000 Message-Id: <6ac9aef5.39a57.14ee53f4@gitrepo.freebsd.org> The branch main has been updated by glebius: URL: https://cgit.FreeBSD.org/src/commit/?id=16bc669facc5eba33f7e215adce206bcf6ab2776 commit 16bc669facc5eba33f7e215adce206bcf6ab2776 Author: Paulo Fragoso AuthorDate: 2026-09-27 19:25:07 +0000 Commit: Gleb Smirnoff 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;