From nobody Fri Oct 30 17:25:43 2026 X-Original-To: dev-commits-src-branches@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 4jGSg06VSwz6xFMB for ; Fri, 30 Oct 2026 17:25:48 +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) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 4jGSg03fJBz4TCK for ; Fri, 30 Oct 2026 17:25:48 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1793381148; 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=luJ8jxOKfkS/n53/+40u/ypOVxz9IxE7m5uZVlNf+m4=; b=h99DfWkdXic6OYwttyNkV60ITmaRf3J+YBOJ1NiHEYb/zHqRKs5lwnKwZyOyxMkags+RhV Oz/BkKhCsE3nfDXqIM5/UBaYeuV2+t2YM9Bp26dhCfx02MVG5F5wx8iCeoWOrDz+Q86HaQ KiWmbc3msYHmZsctuvWZC+GbW4+YMpOi1FR2ZktYkbRqM/aeBUsGKmaC1FcwoKaCkSV7dn 2+sTndzpPd0Q7jlWf8rKf8UHQtrD7pkLlnCt/NfTw7CPJM2Z8ozeva1URFxHxzYw4Yl6cU rKG1B1xROB57FYCmwhJy3divpV7+IOupGrw7jOGIUVlPpSuFljTbtxoQp9BEuQ== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1793381148; b=fExkIm0kSl2uEE89aEMtH9xYMz+0SVS0PW298W5NGy6+KD6RO5MhEs3hw61NjQf8d3jSwl pSHiV6br31ViPgprjG5Q8Mlaz4esFZ0zm3/WBzHuF4OvCGEKoqp1zYhljBY7JpAZ+Znfy+ p0cO/N+xkjaRwJPLpG6cQpw//twt/yevh4WAXDDxqWVGANuM5PbRiV1S58hl3D68S6YxfK CJtpM8ma7OW//KDceK/kglRbNB6UeJVMe/upQbuwhzE3nXH/zc2KdM0HT1FGx7tqarRIf/ xxiueTcxDFMaREdNKrg1z1b5EGCTk827JYwrUnUVxNzh95hLd550XtDMdRC1Mw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1793381148; 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=luJ8jxOKfkS/n53/+40u/ypOVxz9IxE7m5uZVlNf+m4=; b=eijJqTKfuBBIaWjZk2gpNcUUmfW3z7w8Bb0X8xhR/doB7AGpeTtHU7zhORW4GevFUAPMCW Y2CHC0rDBkPvw0Tv8lxilBjD+GeGbtk7j+BWdKJ7HI1XgDWcMIjcXAI9msy7oFbGEZ0A3X GpQPZjrxVTEMfNlZB5Rtl27k5+mCzZIivu452RBsjSdFa8jtXePPoO2Vm4WP+jNA/939l1 3BkVuS+20cVpJjmNgn3BKkCDTFEH7883cmuIokyJ+HRbpSZkaJl4wLHTMb56cE7pfOMS85 mLOwqCHYyKq/gOdlpwywBlTBjXZc9EDqxbWWQ+j5YbhRytVjDbS5mZJhP1BTaw== 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 4jGSg02mwZzdDM for ; Fri, 30 Oct 2026 17:25:48 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 3f0d5 by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Fri, 30 Oct 2026 17:25:43 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Cc: Paulo Fragoso From: Gleb Smirnoff Subject: git: 60529b9c1b29 - stable/15 - libalias: index fully specified inbound links by remote endpoint List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches X-BeenThere: dev-commits-src-branches@freebsd.org Sender: owner-dev-commits-src-branches@FreeBSD.org List-Id: Commits to the stable branches of the FreeBSD src repository 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/stable/15 X-Git-Reftype: branch X-Git-Commit: 60529b9c1b29537f40e99cec2be45b5137aa10d7 Auto-Submitted: auto-generated Date: Fri, 30 Oct 2026 17:25:43 +0000 Message-Id: <6ae4d317.3f0d5.54689440@gitrepo.freebsd.org> The branch stable/15 has been updated by glebius: URL: https://cgit.FreeBSD.org/src/commit/?id=60529b9c1b29537f40e99cec2be45b5137aa10d7 commit 60529b9c1b29537f40e99cec2be45b5137aa10d7 Author: Paulo Fragoso AuthorDate: 2026-09-27 19:25:07 +0000 Commit: Gleb Smirnoff CommitDate: 2026-10-30 17:25:00 +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 (cherry picked from commit 16bc669facc5eba33f7e215adce206bcf6ab2776) --- 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 0861743a68dd..3fc65be95255 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;