From owner-dev-commits-src-all@freebsd.org Sat Jun 19 20:28:27 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 3CF73640C2F; Sat, 19 Jun 2021 20:28: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 "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4G6nRv0yV0z4mTG; Sat, 19 Jun 2021 20:28:27 +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 04BD81CC47; Sat, 19 Jun 2021 20:28:27 +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 15JKSQcS081264; Sat, 19 Jun 2021 20:28:26 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 15JKSQFm081263; Sat, 19 Jun 2021 20:28:26 GMT (envelope-from git) Date: Sat, 19 Jun 2021 20:28:26 GMT Message-Id: <202106192028.15JKSQFm081263@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: d261e57deacb - main - libalias: Switch to efficient data structure for incoming 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: d261e57deacb0d00d9e827447f235df83dda3e3a 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:28:27 -0000 The branch main has been updated by donner: URL: https://cgit.FreeBSD.org/src/commit/?id=d261e57deacb0d00d9e827447f235df83dda3e3a commit d261e57deacb0d00d9e827447f235df83dda3e3a Author: Lutz Donnerhacke AuthorDate: 2021-05-28 20:36:59 +0000 Commit: Lutz Donnerhacke CommitDate: 2021-06-19 20:12:28 +0000 libalias: Switch to efficient data structure for incoming 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. Now the data structure should able to quickly react to external packets without eating CPU cycles for breakfast, preventing a DoS. PR: 192888 Discussed with: Dimitry Luhtionov MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D30536 --- sys/netinet/libalias/alias_db.c | 75 +++++++++++++++++--------------------- sys/netinet/libalias/alias_local.h | 6 +-- 2 files changed, 36 insertions(+), 45 deletions(-) diff --git a/sys/netinet/libalias/alias_db.c b/sys/netinet/libalias/alias_db.c index a5a21e40d0cf..53ad3396d66b 100644 --- a/sys/netinet/libalias/alias_db.c +++ b/sys/netinet/libalias/alias_db.c @@ -424,43 +424,39 @@ cmp_out(struct alias_link *a, struct alias_link *b) { 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 || \ - grp->alias_addr.s_addr != alias_addr.s_addr) \ - continue; +static inline int +cmp_in(struct group_in *a, struct group_in *b) { + int i = a->alias_port - b->alias_port; + if (i != 0) return (i); + i = a->link_type - b->link_type; + if (i != 0) return (i); + i = a->alias_addr.s_addr - b->alias_addr.s_addr; + return (i); +} +SPLAY_PROTOTYPE(splay_in, group_in, in, cmp_in); +SPLAY_GENERATE(splay_in, group_in, in, cmp_in); static struct group_in * StartPointIn(struct libalias *la, struct in_addr alias_addr, u_short alias_port, int link_type, int create) { - u_int n; - struct group_in *grp, *tmp; - - n = alias_addr.s_addr; - n += alias_port; - n += link_type; - n %= LINK_TABLE_IN_SIZE; + struct group_in *grp; + struct group_in needle = { + .alias_addr = alias_addr, + .alias_port = alias_port, + .link_type = link_type + }; - LIST_FOREACH_SAFE(grp, &la->groupTableIn[n], group_in, tmp) { - /* Auto cleanup */ - if (LIST_EMPTY(&grp->full) && LIST_EMPTY(&grp->partial)) { - LIST_REMOVE(grp, group_in); - free(grp); - } else { - INGUARD; - return (grp); - } - } - if (!create || (grp = malloc(sizeof(*grp))) == NULL) + grp = SPLAY_FIND(splay_in, &la->linkSplayIn, &needle); + if (grp != NULL || !create || (grp = malloc(sizeof(*grp))) == NULL) return (grp); grp->alias_addr = alias_addr; grp->alias_port = alias_port; grp->link_type = link_type; LIST_INIT(&grp->full); LIST_INIT(&grp->partial); - LIST_INSERT_HEAD(&la->groupTableIn[n], grp, group_in); + SPLAY_INSERT(splay_in, &la->linkSplayIn, grp); return (grp); } #undef INGUARD @@ -815,25 +811,13 @@ static void CleanupAliasData(struct libalias *la, int deletePermanent) { struct alias_link *lnk, *lnk_tmp; - u_int i; LIBALIAS_LOCK_ASSERT(la); /* permanent entries may stay */ TAILQ_FOREACH_SAFE(lnk, &la->checkExpire, expire.list, lnk_tmp) DeleteLink(&lnk, deletePermanent); - - for (i = 0; i < LINK_TABLE_IN_SIZE; i++) { - struct group_in *grp, *grp_tmp; - - LIST_FOREACH_SAFE(grp, &la->groupTableIn[i], group_in, grp_tmp) - if (LIST_EMPTY(&grp->full) && LIST_EMPTY(&grp->partial)) { - LIST_REMOVE(grp, group_in); - free(grp); - } - } } - static void CleanupLink(struct libalias *la, struct alias_link **lnk, int deletePermanent) { @@ -882,7 +866,9 @@ DeleteLink(struct alias_link **plnk, int deletePermanent) case LINK_PPTP: LIST_REMOVE(lnk, pptp.list); break; - default: + default: { + struct group_in *grp; + /* Free memory allocated for LSNAT server pool */ if (lnk->server != NULL) { struct server *head, *curr, *next; @@ -899,6 +885,16 @@ DeleteLink(struct alias_link **plnk, int deletePermanent) /* Adjust input table pointers */ LIST_REMOVE(lnk, all.in); + + /* 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)) { + SPLAY_REMOVE(splay_in, &la->linkSplayIn, grp); + free(grp); + } + } break; } @@ -2465,8 +2461,6 @@ finishoff(void) struct libalias * LibAliasInit(struct libalias *la) { - int i; - if (la == NULL) { #ifdef _KERNEL #undef malloc /* XXX: ugly */ @@ -2490,9 +2484,8 @@ LibAliasInit(struct libalias *la) LibAliasTime = time(NULL); #endif + SPLAY_INIT(&la->linkSplayIn); SPLAY_INIT(&la->linkSplayOut); - for (i = 0; i < LINK_TABLE_IN_SIZE; i++) - LIST_INIT(&la->groupTableIn[i]); LIST_INIT(&la->pptpList); TAILQ_INIT(&la->checkExpire); #ifdef _KERNEL diff --git a/sys/netinet/libalias/alias_local.h b/sys/netinet/libalias/alias_local.h index a1ad08a979d2..938744924dcc 100644 --- a/sys/netinet/libalias/alias_local.h +++ b/sys/netinet/libalias/alias_local.h @@ -67,8 +67,6 @@ #endif /* Sizes of input and output link tables */ -#define LINK_TABLE_IN_SIZE 4001 - #define GET_ALIAS_PORT -1 #define GET_ALIAS_ID GET_ALIAS_PORT @@ -84,7 +82,7 @@ struct group_in { struct in_addr alias_addr; u_short alias_port; int link_type; - LIST_ENTRY(group_in) group_in; + SPLAY_ENTRY(group_in) in; LIST_HEAD(, alias_link) full, partial; }; @@ -101,7 +99,7 @@ struct libalias { * Each link record is doubly indexed into input and * output lookup tables. */ SPLAY_HEAD(splay_out, alias_link) linkSplayOut; - LIST_HEAD (, group_in) groupTableIn[LINK_TABLE_IN_SIZE]; + SPLAY_HEAD(splay_in, group_in) linkSplayIn; LIST_HEAD (, alias_link) pptpList; /* HouseKeeping */ TAILQ_HEAD (, alias_link) checkExpire;