From owner-dev-commits-src-all@freebsd.org Sat Jun 19 20:10:38 2021 Return-Path: Delivered-To: dev-commits-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 3BC63640918; Sat, 19 Jun 2021 20:10:38 +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 "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4G6n3L10MQz4kLZ; Sat, 19 Jun 2021 20:10:38 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (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 did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 0A6011CB3D; Sat, 19 Jun 2021 20:10:38 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 15JKAb6V061793; Sat, 19 Jun 2021 20:10:37 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 15JKAbQ8061792; Sat, 19 Jun 2021 20:10:37 GMT (envelope-from git) Date: Sat, 19 Jun 2021 20:10:37 GMT Message-Id: <202106192010.15JKAbQ8061792@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Lutz Donnerhacke Subject: git: 935fc93af157 - main - libalias: Switch to efficient data structure for outgoing traffic MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: donner X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e Auto-Submitted: auto-generated X-BeenThere: dev-commits-src-all@freebsd.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Commit messages for all branches of the src repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 19 Jun 2021 20:10:38 -0000 The branch main has been updated by donner: URL: https://cgit.FreeBSD.org/src/commit/?id=935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e commit 935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e Author: Lutz Donnerhacke AuthorDate: 2021-05-27 21:42:54 +0000 Commit: Lutz Donnerhacke CommitDate: 2021-06-19 20:09:44 +0000 libalias: Switch to efficient data structure for outgoing traffic Current data structure is using a hash of unordered lists. Those unordered lists are quite efficient, because the least recently inserted entries are most likely to be used again. In order to avoid long search times in other cases, the lists are hashed into many buckets. Unfortunatly a search for a miss needs an exhaustive inspection and a careful definition of the hash. Splay trees offer a similar feature - almost O(1) for access of the least recently used entries), and amortized O(ln(n) - for almost all other cases. Get rid of the hash. Discussed with: Dimitry Luhtionov MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D30516 --- sys/netinet/libalias/alias_db.c | 81 ++++++++++++++++---------------------- sys/netinet/libalias/alias_local.h | 4 +- 2 files changed, 36 insertions(+), 49 deletions(-) diff --git a/sys/netinet/libalias/alias_db.c b/sys/netinet/libalias/alias_db.c index c5ecc49ed191..a5a21e40d0cf 100644 --- a/sys/netinet/libalias/alias_db.c +++ b/sys/netinet/libalias/alias_db.c @@ -324,11 +324,11 @@ struct alias_link { /* Linked list of pointers for input and output lookup tables */ union { struct { - LIST_ENTRY(alias_link) in; - LIST_ENTRY(alias_link) out; + SPLAY_ENTRY(alias_link) out; + LIST_ENTRY (alias_link) in; } all; struct { - LIST_ENTRY(alias_link) list; + LIST_ENTRY (alias_link) list; } pptp; }; struct { @@ -389,8 +389,6 @@ Miscellaneous: /* Local prototypes */ static struct group_in * StartPointIn(struct libalias *, struct in_addr, u_short, int, int); -static u_int -StartPointOut(struct in_addr, struct in_addr, u_short, u_short, int); static int SeqDiff(u_long, u_long); #ifndef NO_FW_PUNCH @@ -408,6 +406,24 @@ static void UninitPacketAliasLog(struct libalias *); void SctpShowAliasStats(struct libalias *la); + +/* Splay handling */ +static inline int +cmp_out(struct alias_link *a, struct alias_link *b) { + int i = a->src_port - b->src_port; + if (i != 0) return (i); + i = a->src_addr.s_addr - b->src_addr.s_addr; + if (i != 0) return (i); + i = a->dst_addr.s_addr - b->dst_addr.s_addr; + if (i != 0) return (i); + i = a->dst_port - b->dst_port; + if (i != 0) return (i); + i = a->link_type - b->link_type; + return (i); +} +SPLAY_PROTOTYPE(splay_out, alias_link, all.out, cmp_out); +SPLAY_GENERATE(splay_out, alias_link, all.out, cmp_out); + #define INGUARD \ if (grp->alias_port != alias_port || \ grp->link_type != link_type || \ @@ -449,21 +465,6 @@ StartPointIn(struct libalias *la, } #undef INGUARD -static u_int -StartPointOut(struct in_addr src_addr, struct in_addr dst_addr, - u_short src_port, u_short dst_port, int link_type) -{ - u_int n; - - n = src_addr.s_addr; - n += dst_addr.s_addr; - n += src_port; - n += dst_port; - n += link_type; - - return (n % LINK_TABLE_OUT_SIZE); -} - static int SeqDiff(u_long x, u_long y) { @@ -893,7 +894,7 @@ DeleteLink(struct alias_link **plnk, int deletePermanent) } while ((curr = next) != head); } else { /* Adjust output table pointers */ - LIST_REMOVE(lnk, all.out); + SPLAY_REMOVE(splay_out, &la->linkSplayOut, lnk); } /* Adjust input table pointers */ @@ -956,7 +957,6 @@ AddLink(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr, struct in_addr alias_addr, u_short src_port, u_short dst_port, int alias_port_param, int link_type) { - u_int start_point; struct alias_link *lnk; LIBALIAS_LOCK_ASSERT(la); @@ -1085,9 +1085,7 @@ AddLink(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr, } /* Set up pointers for output lookup table */ - start_point = StartPointOut(src_addr, dst_addr, - src_port, dst_port, link_type); - LIST_INSERT_HEAD(&la->linkTableOut[start_point], lnk, all.out); + SPLAY_INSERT(splay_out, &la->linkSplayOut, lnk); /* Set up pointers for input lookup table */ if (lnk->flags & LINK_PARTIALLY_SPECIFIED) @@ -1140,35 +1138,25 @@ ReLink(struct alias_link *old_lnk, return (new_lnk); } - -#define OUTGUARD \ - if (lnk->src_port != src_port || \ - lnk->src_addr.s_addr != src_addr.s_addr || \ - lnk->dst_addr.s_addr != dst_addr.s_addr || \ - lnk->dst_port != dst_port || \ - lnk->link_type != link_type) \ - continue; - static struct alias_link * _SearchLinkOut(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr, u_short src_port, u_short dst_port, int link_type) { - u_int i; struct alias_link *lnk; + struct alias_link needle = { + .src_addr = src_addr, + .dst_addr = dst_addr, + .src_port = src_port, + .dst_port = dst_port, + .link_type = link_type + }; - i = StartPointOut(src_addr, dst_addr, src_port, dst_port, link_type); - LIST_FOREACH(lnk, &la->linkTableOut[i], all.out) { - OUTGUARD; - return (UseLink(la, lnk)); - } - - return (NULL); + lnk = SPLAY_FIND(splay_out, &la->linkSplayOut, &needle); + return (UseLink(la, lnk)); } -#undef OUTGUARD - static struct alias_link * _FindLinkOut(struct libalias *la, struct in_addr src_addr, struct in_addr dst_addr, @@ -2333,7 +2321,7 @@ LibAliasAddServer(struct libalias *la, struct alias_link *lnk, struct in_addr ad if (head == NULL) { server->next = server; /* not usable for outgoing connections */ - LIST_REMOVE(lnk, all.out); + SPLAY_REMOVE(splay_out, &la->linkSplayOut, lnk); } else { struct server *s; @@ -2502,8 +2490,7 @@ LibAliasInit(struct libalias *la) LibAliasTime = time(NULL); #endif - for (i = 0; i < LINK_TABLE_OUT_SIZE; i++) - LIST_INIT(&la->linkTableOut[i]); + SPLAY_INIT(&la->linkSplayOut); for (i = 0; i < LINK_TABLE_IN_SIZE; i++) LIST_INIT(&la->groupTableIn[i]); LIST_INIT(&la->pptpList); diff --git a/sys/netinet/libalias/alias_local.h b/sys/netinet/libalias/alias_local.h index 5628adac203e..a1ad08a979d2 100644 --- a/sys/netinet/libalias/alias_local.h +++ b/sys/netinet/libalias/alias_local.h @@ -48,6 +48,7 @@ #ifndef _ALIAS_LOCAL_H_ #define _ALIAS_LOCAL_H_ +#include #include #include @@ -66,7 +67,6 @@ #endif /* Sizes of input and output link tables */ -#define LINK_TABLE_OUT_SIZE 4001 #define LINK_TABLE_IN_SIZE 4001 #define GET_ALIAS_PORT -1 @@ -100,7 +100,7 @@ struct libalias { /* Lookup table of pointers to chains of link records. * Each link record is doubly indexed into input and * output lookup tables. */ - LIST_HEAD (, alias_link) linkTableOut[LINK_TABLE_OUT_SIZE]; + SPLAY_HEAD(splay_out, alias_link) linkSplayOut; LIST_HEAD (, group_in) groupTableIn[LINK_TABLE_IN_SIZE]; LIST_HEAD (, alias_link) pptpList; /* HouseKeeping */