siphash is slower than an rbt lookup. we also save a bit of memory
by not allocating 1024 hash buckets.
tests? ok?
Index: if_bridge.c
===================================================================
RCS file: /cvs/src/sys/net/if_bridge.c,v
retrieving revision 1.304
diff -u -p -r1.304 if_bridge.c
--- if_bridge.c 7 Feb 2018 11:30:01 -0000 1.304
+++ if_bridge.c 9 Feb 2018 23:18:43 -0000
@@ -154,7 +154,6 @@ bridge_clone_create(struct if_clone *ifc
{
struct bridge_softc *sc;
struct ifnet *ifp;
- int i;
sc = malloc(sizeof(*sc), M_DEVBUF, M_WAITOK|M_ZERO);
sc->sc_stp = bstp_create(&sc->sc_if);
@@ -168,9 +167,7 @@ bridge_clone_create(struct if_clone *ifc
timeout_set(&sc->sc_brtimeout, bridge_rtage, sc);
TAILQ_INIT(&sc->sc_iflist);
TAILQ_INIT(&sc->sc_spanlist);
- for (i = 0; i < BRIDGE_RTABLE_SIZE; i++)
- LIST_INIT(&sc->sc_rts[i]);
- arc4random_buf(&sc->sc_hashkey, sizeof(sc->sc_hashkey));
+ RBT_INIT(bridge_rtable, &sc->sc_rts);
ifp = &sc->sc_if;
snprintf(ifp->if_xname, sizeof ifp->if_xname, "%s%d", ifc->ifc_name,
unit);
Index: if_bridge.h
===================================================================
RCS file: /cvs/src/sys/net/if_bridge.h,v
retrieving revision 1.56
diff -u -p -r1.56 if_bridge.h
--- if_bridge.h 5 Feb 2018 03:51:53 -0000 1.56
+++ if_bridge.h 9 Feb 2018 23:18:43 -0000
@@ -36,6 +36,7 @@
#define _NET_IF_BRIDGE_H_
#include <sys/timeout.h>
+#include <sys/tree.h>
#include <net/pfvar.h>
/*
@@ -447,7 +448,7 @@ struct bridge_tunneltag {
* Bridge route node
*/
struct bridge_rtnode {
- LIST_ENTRY(bridge_rtnode) brt_next; /* next in list */
+ RBT_ENTRY(bridge_rtnode) brt_entry;
struct ifnet *brt_if; /* destination ifs */
u_int8_t brt_flags; /* address flags */
u_int8_t brt_age; /* age counter */
@@ -455,10 +456,15 @@ struct bridge_rtnode {
struct bridge_tunneltag brt_tunnel; /* tunnel endpoint */
};
-#ifndef BRIDGE_RTABLE_SIZE
-#define BRIDGE_RTABLE_SIZE 1024
-#endif
-#define BRIDGE_RTABLE_MASK (BRIDGE_RTABLE_SIZE - 1)
+RBT_HEAD(bridge_rtable, bridge_rtnode);
+
+static inline int
+bridge_rtnode_cmp(const struct bridge_rtnode *a, const struct bridge_rtnode *b)
+{
+ return (memcmp(&a->brt_addr, &b->brt_addr, sizeof(a->brt_addr)));
+}
+
+RBT_PROTOTYPE(bridge_rtable, bridge_rtnode, brt_entry, bridge_rtnode_cmp);
/*
* Software state for each bridge
@@ -468,12 +474,11 @@ struct bridge_softc {
u_int32_t sc_brtmax; /* max # addresses */
u_int32_t sc_brtcnt; /* current # addrs */
int sc_brttimeout; /* timeout ticks */
- u_int64_t sc_hashkey[2]; /* siphash key */
struct timeout sc_brtimeout; /* timeout state */
struct bstp_state *sc_stp; /* stp state */
TAILQ_HEAD(, bridge_iflist) sc_iflist; /* interface list */
TAILQ_HEAD(, bridge_iflist) sc_spanlist; /* span ports */
- LIST_HEAD(, bridge_rtnode) sc_rts[BRIDGE_RTABLE_SIZE]; /* hash
table */
+ struct bridge_rtable sc_rts;
};
extern const u_int8_t bstp_etheraddr[];
Index: bridgectl.c
===================================================================
RCS file: /cvs/src/sys/net/bridgectl.c,v
retrieving revision 1.8
diff -u -p -r1.8 bridgectl.c
--- bridgectl.c 5 Feb 2018 05:06:51 -0000 1.8
+++ bridgectl.c 9 Feb 2018 23:18:43 -0000
@@ -41,8 +41,6 @@
#include <sys/timeout.h>
#include <sys/kernel.h>
-#include <crypto/siphash.h>
-
#include <net/if.h>
#include <netinet/in.h>
@@ -173,18 +171,15 @@ struct ifnet *
bridge_rtupdate(struct bridge_softc *sc, struct ether_addr *ea,
struct ifnet *ifp, int setflags, u_int8_t flags, struct mbuf *m)
{
- struct bridge_rtnode *p, *q;
+ struct bridge_rtnode *p;
struct bridge_tunneltag *brtag = NULL;
- u_int32_t h;
- int dir;
if (m != NULL) {
/* Check if the mbuf was tagged with a tunnel endpoint addr */
brtag = bridge_tunnel(m);
}
- h = bridge_hash(sc, ea);
- p = LIST_FIRST(&sc->sc_rts[h]);
+ p = bridge_rtlookup(sc, ea);
if (p == NULL) {
if (sc->sc_brtcnt >= sc->sc_brtmax)
goto done;
@@ -202,105 +197,34 @@ bridge_rtupdate(struct bridge_softc *sc,
else
p->brt_flags = IFBAF_DYNAMIC;
- LIST_INSERT_HEAD(&sc->sc_rts[h], p, brt_next);
+ RBT_INSERT(bridge_rtable, &sc->sc_rts, p);
sc->sc_brtcnt++;
- goto want;
- }
-
- do {
- q = p;
- p = LIST_NEXT(p, brt_next);
-
- dir = memcmp(ea, &q->brt_addr, sizeof(q->brt_addr));
- if (dir == 0) {
- if (setflags) {
- q->brt_if = ifp;
- q->brt_flags = flags;
- } else if (!(q->brt_flags & IFBAF_STATIC))
- q->brt_if = ifp;
-
- if (q->brt_if == ifp)
- q->brt_age = 1;
- ifp = q->brt_if;
- bridge_copytag(brtag, &q->brt_tunnel);
-
- goto want;
- }
-
- if (dir > 0) {
- if (sc->sc_brtcnt >= sc->sc_brtmax)
- goto done;
- p = malloc(sizeof(*p), M_DEVBUF, M_NOWAIT);
- if (p == NULL)
- goto done;
-
- bcopy(ea, &p->brt_addr, sizeof(p->brt_addr));
+ } else {
+ if (setflags) {
p->brt_if = ifp;
- p->brt_age = 1;
- bridge_copytag(brtag, &p->brt_tunnel);
-
- if (setflags)
- p->brt_flags = flags;
- else
- p->brt_flags = IFBAF_DYNAMIC;
-
- LIST_INSERT_BEFORE(q, p, brt_next);
- sc->sc_brtcnt++;
- goto want;
- }
-
- if (p == NULL) {
- if (sc->sc_brtcnt >= sc->sc_brtmax)
- goto done;
- p = malloc(sizeof(*p), M_DEVBUF, M_NOWAIT);
- if (p == NULL)
- goto done;
-
- bcopy(ea, &p->brt_addr, sizeof(p->brt_addr));
+ p->brt_flags = flags;
+ } else if (!(p->brt_flags & IFBAF_STATIC))
p->brt_if = ifp;
- p->brt_age = 1;
- bridge_copytag(brtag, &p->brt_tunnel);
- if (setflags)
- p->brt_flags = flags;
- else
- p->brt_flags = IFBAF_DYNAMIC;
- LIST_INSERT_AFTER(q, p, brt_next);
- sc->sc_brtcnt++;
- goto want;
- }
- } while (p != NULL);
+ if (p->brt_if == ifp)
+ p->brt_age = 1;
+ ifp = p->brt_if;
+ bridge_copytag(brtag, &p->brt_tunnel);
+ }
done:
ifp = NULL;
-want:
return (ifp);
}
struct bridge_rtnode *
bridge_rtlookup(struct bridge_softc *sc, struct ether_addr *ea)
{
- struct bridge_rtnode *p;
- u_int32_t h;
- int dir;
+ struct bridge_rtnode key;
- h = bridge_hash(sc, ea);
- LIST_FOREACH(p, &sc->sc_rts[h], brt_next) {
- dir = memcmp(ea, &p->brt_addr, sizeof(p->brt_addr));
- if (dir == 0)
- return (p);
- if (dir > 0)
- goto fail;
- }
-fail:
- return (NULL);
-}
+ key.brt_addr = *ea;
-u_int32_t
-bridge_hash(struct bridge_softc *sc, struct ether_addr *addr)
-{
- return SipHash24((SIPHASH_KEY *)sc->sc_hashkey, addr, ETHER_ADDR_LEN) &
- BRIDGE_RTABLE_MASK;
+ return (RBT_FIND(bridge_rtable, &sc->sc_rts, &key));
}
/*
@@ -311,28 +235,18 @@ bridge_rtage(void *vsc)
{
struct bridge_softc *sc = vsc;
struct bridge_rtnode *n, *p;
- int i;
KERNEL_ASSERT_LOCKED();
- for (i = 0; i < BRIDGE_RTABLE_SIZE; i++) {
- n = LIST_FIRST(&sc->sc_rts[i]);
- while (n != NULL) {
- if ((n->brt_flags & IFBAF_TYPEMASK) == IFBAF_STATIC) {
- n->brt_age = !n->brt_age;
- if (n->brt_age)
- n->brt_age = 0;
- n = LIST_NEXT(n, brt_next);
- } else if (n->brt_age) {
- n->brt_age = 0;
- n = LIST_NEXT(n, brt_next);
- } else {
- p = LIST_NEXT(n, brt_next);
- LIST_REMOVE(n, brt_next);
- sc->sc_brtcnt--;
- free(n, M_DEVBUF, sizeof *n);
- n = p;
- }
+ RBT_FOREACH_SAFE(n, bridge_rtable, &sc->sc_rts, p) {
+ if ((n->brt_flags & IFBAF_TYPEMASK) == IFBAF_STATIC)
+ n->brt_age = 0;
+ else if (n->brt_age)
+ n->brt_age = 0;
+ else {
+ sc->sc_brtcnt--;
+ RBT_REMOVE(bridge_rtable, &sc->sc_rts, n);
+ free(n, M_DEVBUF, sizeof(*n));
}
}
@@ -345,7 +259,6 @@ bridge_rtagenode(struct ifnet *ifp, int
{
struct bridge_softc *sc;
struct bridge_rtnode *n;
- int i;
sc = ((struct bridge_iflist *)ifp->if_bridgeport)->bridge_sc;
if (sc == NULL)
@@ -355,18 +268,17 @@ bridge_rtagenode(struct ifnet *ifp, int
* If the age is zero then flush, otherwise set all the expiry times to
* age for the interface
*/
- if (age == 0)
+ if (age == 0) {
bridge_rtdelete(sc, ifp, 1);
- else {
- for (i = 0; i < BRIDGE_RTABLE_SIZE; i++) {
- LIST_FOREACH(n, &sc->sc_rts[i], brt_next) {
- /* Cap the expiry time to 'age' */
- if (n->brt_if == ifp &&
- n->brt_age > time_uptime + age &&
- (n->brt_flags & IFBAF_TYPEMASK) ==
IFBAF_DYNAMIC)
- n->brt_age = time_uptime + age;
- }
- }
+ return;
+ }
+
+ RBT_FOREACH(n, bridge_rtable, &sc->sc_rts) {
+ /* Cap the expiry time to 'age' */
+ if (n->brt_if == ifp &&
+ n->brt_age > time_uptime + age &&
+ (n->brt_flags & IFBAF_TYPEMASK) == IFBAF_DYNAMIC)
+ n->brt_age = time_uptime + age;
}
}
@@ -376,22 +288,16 @@ bridge_rtagenode(struct ifnet *ifp, int
void
bridge_rtflush(struct bridge_softc *sc, int full)
{
- int i;
struct bridge_rtnode *p, *n;
- for (i = 0; i < BRIDGE_RTABLE_SIZE; i++) {
- n = LIST_FIRST(&sc->sc_rts[i]);
- while (n != NULL) {
- if (full ||
- (n->brt_flags & IFBAF_TYPEMASK) == IFBAF_DYNAMIC) {
- p = LIST_NEXT(n, brt_next);
- LIST_REMOVE(n, brt_next);
- sc->sc_brtcnt--;
- free(n, M_DEVBUF, sizeof *n);
- n = p;
- } else
- n = LIST_NEXT(n, brt_next);
+ RBT_FOREACH_SAFE(n, bridge_rtable, &sc->sc_rts, p) {
+ if ((n->brt_flags & IFBAF_TYPEMASK) != IFBAF_DYNAMIC) {
+ /* only deleting dynamics */
+ continue;
}
+
+ sc->sc_brtcnt--;
+ RBT_REMOVE(bridge_rtable, &sc->sc_rts, n);
}
}
@@ -401,20 +307,17 @@ bridge_rtflush(struct bridge_softc *sc,
int
bridge_rtdaddr(struct bridge_softc *sc, struct ether_addr *ea)
{
- int h;
- struct bridge_rtnode *p;
+ struct bridge_rtnode *n;
- h = bridge_hash(sc, ea);
- LIST_FOREACH(p, &sc->sc_rts[h], brt_next) {
- if (memcmp(ea, &p->brt_addr, sizeof(p->brt_addr)) == 0) {
- LIST_REMOVE(p, brt_next);
- sc->sc_brtcnt--;
- free(p, M_DEVBUF, sizeof *p);
- return (0);
- }
- }
+ n = bridge_rtlookup(sc, ea);
+ if (n == NULL)
+ return (ENOENT);
- return (ENOENT);
+ sc->sc_brtcnt--;
+ RBT_REMOVE(bridge_rtable, &sc->sc_rts, n);
+ free(n, M_DEVBUF, sizeof(*n));
+
+ return (0);
}
/*
@@ -423,33 +326,25 @@ bridge_rtdaddr(struct bridge_softc *sc,
void
bridge_rtdelete(struct bridge_softc *sc, struct ifnet *ifp, int dynonly)
{
- int i;
struct bridge_rtnode *n, *p;
/*
* Loop through all of the hash buckets and traverse each
* chain looking for routes to this interface.
*/
- for (i = 0; i < BRIDGE_RTABLE_SIZE; i++) {
- n = LIST_FIRST(&sc->sc_rts[i]);
- while (n != NULL) {
- if (n->brt_if != ifp) {
- /* Not ours */
- n = LIST_NEXT(n, brt_next);
- continue;
- }
- if (dynonly &&
- (n->brt_flags & IFBAF_TYPEMASK) != IFBAF_DYNAMIC) {
- /* only deleting dynamics */
- n = LIST_NEXT(n, brt_next);
- continue;
- }
- p = LIST_NEXT(n, brt_next);
- LIST_REMOVE(n, brt_next);
- sc->sc_brtcnt--;
- free(n, M_DEVBUF, sizeof *n);
- n = p;
+ RBT_FOREACH_SAFE(n, bridge_rtable, &sc->sc_rts, p) {
+ if (n->brt_if != ifp) {
+ /* Not ours */
+ continue;
}
+ if (dynonly &&
+ (n->brt_flags & IFBAF_TYPEMASK) != IFBAF_DYNAMIC) {
+ /* only deleting dynamics */
+ continue;
+ }
+
+ sc->sc_brtcnt--;
+ RBT_REMOVE(bridge_rtable, &sc->sc_rts, n);
}
}
@@ -459,40 +354,42 @@ bridge_rtdelete(struct bridge_softc *sc,
int
bridge_rtfind(struct bridge_softc *sc, struct ifbaconf *baconf)
{
- int i, error = 0, onlycnt = 0;
- u_int32_t cnt = 0;
struct bridge_rtnode *n;
struct ifbareq bareq;
+ int error = 0;
+ int cnt = 0;
- if (baconf->ifbac_len == 0)
- onlycnt = 1;
+ if (baconf->ifbac_len == 0) {
+ cnt = sc->sc_brtcnt;
+ goto done;
+ }
- for (i = 0, cnt = 0; i < BRIDGE_RTABLE_SIZE; i++) {
- LIST_FOREACH(n, &sc->sc_rts[i], brt_next) {
- if (!onlycnt) {
- if (baconf->ifbac_len < sizeof(struct ifbareq))
- goto done;
- bcopy(sc->sc_if.if_xname, bareq.ifba_name,
- sizeof(bareq.ifba_name));
- bcopy(n->brt_if->if_xname, bareq.ifba_ifsname,
- sizeof(bareq.ifba_ifsname));
- bcopy(&n->brt_addr, &bareq.ifba_dst,
- sizeof(bareq.ifba_dst));
- bridge_copyaddr(&n->brt_tunnel.brtag_peer.sa,
- sstosa(&bareq.ifba_dstsa));
- bareq.ifba_age = n->brt_age;
- bareq.ifba_flags = n->brt_flags;
- error = copyout((caddr_t)&bareq,
- (caddr_t)(baconf->ifbac_req + cnt),
sizeof(bareq));
- if (error)
- goto done;
- baconf->ifbac_len -= sizeof(struct ifbareq);
- }
- cnt++;
- }
+ RBT_FOREACH(n, bridge_rtable, &sc->sc_rts) {
+ if (baconf->ifbac_len < sizeof(bareq))
+ goto done;
+
+ bcopy(sc->sc_if.if_xname, bareq.ifba_name,
+ sizeof(bareq.ifba_name));
+ bcopy(n->brt_if->if_xname, bareq.ifba_ifsname,
+ sizeof(bareq.ifba_ifsname));
+ bcopy(&n->brt_addr, &bareq.ifba_dst,
+ sizeof(bareq.ifba_dst));
+ bridge_copyaddr(&n->brt_tunnel.brtag_peer.sa,
+ sstosa(&bareq.ifba_dstsa));
+ bareq.ifba_age = n->brt_age;
+ bareq.ifba_flags = n->brt_flags;
+
+ error = copyout(&bareq, baconf->ifbac_req + cnt,
+ sizeof(bareq));
+ if (error)
+ goto done;
+
+ baconf->ifbac_len -= sizeof(bareq);
+ cnt++;
}
+
done:
- baconf->ifbac_len = cnt * sizeof(struct ifbareq);
+ baconf->ifbac_len = cnt * sizeof(bareq);
return (error);
}
@@ -757,3 +654,5 @@ bridge_flushrule(struct bridge_iflist *b
free(p, M_DEVBUF, sizeof *p);
}
}
+
+RBT_GENERATE(bridge_rtable, bridge_rtnode, brt_entry, bridge_rtnode_cmp);
