On Sat, 19 Jun 2021 at 21:10, Lutz Donnerhacke <don...@freebsd.org> wrote: > > The branch main has been updated by donner: > > URL: > https://cgit.FreeBSD.org/src/commit/?id=935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e > > commit 935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e > Author: Lutz Donnerhacke <don...@freebsd.org> > AuthorDate: 2021-05-27 21:42:54 +0000 > Commit: Lutz Donnerhacke <don...@freebsd.org> > 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 <sys/tree.h> > #include <sys/types.h> > #include <sys/sysctl.h> > > @@ -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=<optimized out>, 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=<optimized out>, 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=<optimized out>) at /usr/src/contrib/atf/atf-c/tp.c:201 #8 0x0000000801081bdb in run_tc (tp=0x7fffffffd9e8, p=0x7fffffffda00, exitcode=<optimized out>) at /usr/src/contrib/atf/atf-c/detail/tp_main.c:504 #9 controlled_main (argc=<optimized out>, argv=0x7fffffffeaa0, add_tcs_hook=0x1023b90, exitcode=<optimized out>) at /usr/src/contrib/atf/atf-c/detail/tp_main.c:574 #10 atf_tp_main (argc=<optimized out>, 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 _______________________________________________ dev-commits-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/dev-commits-src-all To unsubscribe, send any mail to "dev-commits-src-all-unsubscr...@freebsd.org"
