From owner-dev-commits-src-all@freebsd.org Wed Jun 23 10:08: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 911A764D033; Wed, 23 Jun 2021 10:08:27 +0000 (UTC) (envelope-from arichardson.kde@gmail.com) Received: from mail-ed1-f45.google.com (mail-ed1-f45.google.com [209.85.208.45]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1O1" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4G8zVf4MqTz3wXG; Wed, 23 Jun 2021 10:08:26 +0000 (UTC) (envelope-from arichardson.kde@gmail.com) Received: by mail-ed1-f45.google.com with SMTP id h17so2614289edw.11; Wed, 23 Jun 2021 03:08:26 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=eOO16uLSDCDSk89LRrhA7b3IB+GxhUcogJhqXbQjEpE=; b=PRFYcaNm7e1DIxX6T63fAX/G183CYPcWFHHLC7Q4S4PaEDJqhIv7Vwapj//jBbnfff Ot62pe+F3aKJvN1M/cF5dIdYU2xE6QVfgbtM/L1pQitoCf6ePXN96Y6EixfG5Wt5zsCn 5VpHWE9rmUIKeF4xpRMo9371Vkc2OFaWuCyAYaHmtpZrNZY+KBLG5uVx33Af75cx7kZq EyrAMFXO/ThawR4Cu941xr1TPf62LmFyiG0G/r+bGVVJ28qJ6VuFP9Bh56oJF9LddvQ2 KEUcO5DfEGZw5KYRRFjYG6rjWGhU+pezYuVGi/lBrYVoY8ZMY/d+St3o+oxqZHvem1lf oEjw== X-Gm-Message-State: AOAM533pQw1a3WnPi0qqeVeC/PvtT9FJMMwIPKdOsKSgE7YzRdrcZuDi wC198/1F5PGTulbNZ594iW7VeIwEFQGhBw== X-Google-Smtp-Source: ABdhPJxNUBrCMwavN6T6Fdb46CpWzAGrFQXZAkL+R1FRMFg6+YNrFhwmnODW39uKDiNuoZ47/B4qXg== X-Received: by 2002:a05:6402:50cb:: with SMTP id h11mr1971781edb.97.1624442904785; Wed, 23 Jun 2021 03:08:24 -0700 (PDT) Received: from mail-wm1-f48.google.com (mail-wm1-f48.google.com. [209.85.128.48]) by smtp.gmail.com with ESMTPSA id y6sm796360edr.65.2021.06.23.03.08.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 23 Jun 2021 03:08:24 -0700 (PDT) Received: by mail-wm1-f48.google.com with SMTP id j11-20020a05600c1c0bb02901e23d4c0977so2986156wms.0; Wed, 23 Jun 2021 03:08:24 -0700 (PDT) X-Received: by 2002:a7b:c187:: with SMTP id y7mr9612097wmi.13.1624442904342; Wed, 23 Jun 2021 03:08:24 -0700 (PDT) MIME-Version: 1.0 References: <202106192010.15JKAbQ8061792@gitrepo.freebsd.org> In-Reply-To: <202106192010.15JKAbQ8061792@gitrepo.freebsd.org> From: Alexander Richardson Date: Wed, 23 Jun 2021 11:08:13 +0100 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: git: 935fc93af157 - main - libalias: Switch to efficient data structure for outgoing traffic To: Lutz Donnerhacke Cc: src-committers , "" , dev-commits-src-main@freebsd.org Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: 4G8zVf4MqTz3wXG X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of arichardsonkde@gmail.com designates 209.85.208.45 as permitted sender) smtp.mailfrom=arichardsonkde@gmail.com X-Spamd-Result: default: False [-2.93 / 15.00]; RCVD_VIA_SMTP_AUTH(0.00)[]; TO_DN_SOME(0.00)[]; R_SPF_ALLOW(-0.20)[+ip4:209.85.128.0/17]; RCVD_COUNT_THREE(0.00)[4]; NEURAL_HAM_SHORT(-0.93)[-0.933]; FORGED_SENDER(0.30)[arichardson@freebsd.org,arichardsonkde@gmail.com]; MIME_TRACE(0.00)[0:+]; FREEMAIL_ENVFROM(0.00)[gmail.com]; RBL_DBL_DONT_QUERY_IPS(0.00)[209.85.208.45:from]; R_DKIM_NA(0.00)[]; TAGGED_FROM(0.00)[]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US]; FROM_NEQ_ENVFROM(0.00)[arichardson@freebsd.org,arichardsonkde@gmail.com]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[4]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[freebsd.org]; SPAMHAUS_ZRD(0.00)[209.85.208.45:from:127.0.2.255]; RCVD_IN_DNSWL_NONE(0.00)[209.85.208.45:from]; RWL_MAILSPIKE_POSSIBLE(0.00)[209.85.208.45:from]; RCVD_TLS_ALL(0.00)[]; MAILMAN_DEST(0.00)[dev-commits-src-all,dev-commits-src-main] 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: Wed, 23 Jun 2021 10:08:27 -0000 On Sat, 19 Jun 2021 at 21:10, Lutz Donnerhacke wrote: > > 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 */ Hi, This commit appears to have introduced a SIGBUS when running some of the tests: Program terminated with signal SIGBUS, Bus error. #0 cmp_out (a=0x80180e080, b=0x5a5a5a5a5a5a5a5a) at /usr/src/sys/netinet/libalias/alias_db.c:413 413 /usr/src/sys/netinet/libalias/alias_db.c: No such file or directory. #0 cmp_out (a=0x80180e080, b=0x5a5a5a5a5a5a5a5a) at /usr/src/sys/netinet/libalias/alias_db.c:413 #1 splay_out_SPLAY (head=head@entry=0x8018100e0, elm=elm@entry=0x80180e080) at /usr/src/sys/netinet/libalias/alias_db.c:425 #2 0x00000008010908d9 in splay_out_SPLAY_REMOVE (head=0x8018100e0, elm=0x80180e080) at /usr/src/sys/netinet/libalias/alias_db.c:425 #3 DeleteLink (plnk=plnk@entry=0x7fffffffd530, deletePermanent=, deletePermanent@entry=1) at /usr/src/sys/netinet/libalias/alias_db.c:883 #4 0x0000000801091251 in CleanupAliasData (la=0x8018100c0, deletePermanent=1) at /usr/src/sys/netinet/libalias/alias_db.c:819 #5 LibAliasUninit (la=0x8018100c0) at /usr/src/sys/netinet/libalias/alias_db.c:2542 #6 0x000000080107f0a7 in atf_tc_run (tc=0x102a628, tc@entry=0x801809020, resfile=, resfile@entry=0x0) at /usr/src/contrib/atf/atf-c/tc.c:1060 #7 0x00000008010811de in atf_tp_run (tp=tp@entry=0x7fffffffd9e8, tcname=tcname@entry=0x801809020 "3_redirectany", resfile=) at /usr/src/contrib/atf/atf-c/tp.c:201 #8 0x0000000801081bdb in run_tc (tp=0x7fffffffd9e8, p=0x7fffffffda00, exitcode=) at /usr/src/contrib/atf/atf-c/detail/tp_main.c:504 #9 controlled_main (argc=, argv=0x7fffffffeaa0, add_tcs_hook=0x1023b90, exitcode=) at /usr/src/contrib/atf/atf-c/detail/tp_main.c:574 #10 atf_tp_main (argc=, argv=0x7fffffffeaa0, add_tcs_hook=0x1023b90) at /usr/src/contrib/atf/atf-c/detail/tp_main.c:604 #11 0x000000000102395d in ?? () #12 0x00007fffffffed68 in ?? () #13 0x0000000000000000 in ?? () Source: https://ci.freebsd.org/job/FreeBSD-main-amd64-test/18438/testReport/junit/sys.netinet.libalias/3_natin/1_portforward/ See https://ci.freebsd.org/job/FreeBSD-main-amd64-test/18438/#showFailuresLink Could you have a look? Thanks, Alex