git: 935fc93af157 - main - libalias: Switch to efficient data structure for outgoing traffic
Alexander Richardson
arichardson at freebsd.org
Wed Jun 23 10:08:27 UTC 2021
On Sat, 19 Jun 2021 at 21:10, Lutz Donnerhacke <donner at 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 <donner at FreeBSD.org>
> AuthorDate: 2021-05-27 21:42:54 +0000
> Commit: Lutz Donnerhacke <donner at 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 at entry=0x8018100e0,
elm=elm at 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 at entry=0x7fffffffd530,
deletePermanent=<optimized out>, deletePermanent at 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 at entry=0x801809020, resfile=<optimized out>, resfile at entry=0x0) at
/usr/src/contrib/atf/atf-c/tc.c:1060
#7 0x00000008010811de in atf_tp_run (tp=tp at entry=0x7fffffffd9e8,
tcname=tcname at 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
More information about the dev-commits-src-all
mailing list