diff --git a/sys/net/if_vlan.c b/sys/net/if_vlan.c --- a/sys/net/if_vlan.c +++ b/sys/net/if_vlan.c @@ -88,7 +88,14 @@ #include #include -#define VLAN_DEF_HWIDTH 4 +/* For a fixed-width hash list, the value 8 realizes a list 256 entries wide. + * With 4094 unique VLAN possibilities per interface, this provides an absolute + * maximum VLAN chain length of 16 entries. Performance testing with iperf3 + * suggests that acceptable performance is maintained with chain lengths up to + * 32. Picking a length of 16 allows for margin. + */ +#define VLAN_HWIDTH 8 +#define VLAN_HMASK ((1 << VLAN_HWIDTH) - 1) #define VLAN_IFFLAGS (IFF_BROADCAST | IFF_MULTICAST) #define UP_AND_RUNNING(ifp) \ @@ -104,8 +111,6 @@ struct ifvlan *vlans[VLAN_ARRAY_SIZE]; /* static table */ #else struct ifvlanhead *hash; /* dynamic hash-list table */ - uint16_t hmask; - uint16_t hwidth; #endif int refcnt; }; @@ -137,7 +142,7 @@ #define VLAN_FOREACH(_ifv, _trunk) \ struct ifvlan *_next; \ size_t _i; \ - for (_i = 0; _i < (1 << (_trunk)->hwidth); _i++) \ + for (_i = 0; _i < (1 << VLAN_HWIDTH); _i++) \ CK_SLIST_FOREACH_SAFE((_ifv), &(_trunk)->hash[_i], ifv_list, _next) #endif /* VLAN_ARRAY */ @@ -165,7 +170,7 @@ size_t _i; \ bool _touch = false; \ for (_i = 0; \ - !(_cond) && _i < (1 << (_trunk)->hwidth); \ + !(_cond) && _i < (1 << VLAN_HWIDTH); \ _i = (_touch && ((_trunk) != NULL) ? 0 : _i + 1), _touch = false) \ if (((_ifv) = CK_SLIST_FIRST(&(_trunk)->hash[_i])) != NULL && \ (_touch = true)) @@ -277,7 +282,6 @@ static void vlan_freehash(struct ifvlantrunk *trunk); static int vlan_inshash(struct ifvlantrunk *trunk, struct ifvlan *ifv); static int vlan_remhash(struct ifvlantrunk *trunk, struct ifvlan *ifv); -static void vlan_growhash(struct ifvlantrunk *trunk, int howmuch); static __inline struct ifvlan * vlan_gethash(struct ifvlantrunk *trunk, uint16_t vid); #endif @@ -388,7 +392,7 @@ } #ifndef VLAN_ARRAY -#define HASH(n, m) ((((n) >> 8) ^ ((n) >> 4) ^ (n)) & (m)) +#define HASH(n) ((((n) >> 8) ^ ((n) >> 4) ^ (n)) & VLAN_HMASK) static void vlan_inithash(struct ifvlantrunk *trunk) @@ -401,12 +405,9 @@ * gets hooked up and becomes visible from other threads. */ - KASSERT(trunk->hwidth == 0 && trunk->hash == NULL, - ("%s: hash already initialized", __func__)); + KASSERT(trunk->hash == NULL, ("%s: hash already initialized", __func__)); - trunk->hwidth = VLAN_DEF_HWIDTH; - n = 1 << trunk->hwidth; - trunk->hmask = n - 1; + n = 1 << VLAN_HWIDTH; trunk->hash = malloc(sizeof(struct ifvlanhead) * n, M_VLAN, M_WAITOK); for (i = 0; i < n; i++) CK_SLIST_INIT(&trunk->hash[i]); @@ -418,40 +419,27 @@ #ifdef INVARIANTS int i; - KASSERT(trunk->hwidth > 0, ("%s: hwidth not positive", __func__)); - for (i = 0; i < (1 << trunk->hwidth); i++) + for (i = 0; i <= VLAN_HMASK; i++) KASSERT(CK_SLIST_EMPTY(&trunk->hash[i]), ("%s: hash table not empty", __func__)); #endif free(trunk->hash, M_VLAN); trunk->hash = NULL; - trunk->hwidth = trunk->hmask = 0; } static int vlan_inshash(struct ifvlantrunk *trunk, struct ifvlan *ifv) { - int i, b; + int i; struct ifvlan *ifv2; VLAN_XLOCK_ASSERT(); - KASSERT(trunk->hwidth > 0, ("%s: hwidth not positive", __func__)); - b = 1 << trunk->hwidth; - i = HASH(ifv->ifv_vid, trunk->hmask); + i = HASH(ifv->ifv_vid); CK_SLIST_FOREACH(ifv2, &trunk->hash[i], ifv_list) if (ifv->ifv_vid == ifv2->ifv_vid) return (EEXIST); - /* - * Grow the hash when the number of vlans exceeds half of the number of - * hash buckets squared. This will make the average linked-list length - * buckets/2. - */ - if (trunk->refcnt > (b * b) / 2) { - vlan_growhash(trunk, 1); - i = HASH(ifv->ifv_vid, trunk->hmask); - } CK_SLIST_INSERT_HEAD(&trunk->hash[i], ifv, ifv_list); trunk->refcnt++; @@ -461,20 +449,16 @@ static int vlan_remhash(struct ifvlantrunk *trunk, struct ifvlan *ifv) { - int i, b; + int i; struct ifvlan *ifv2; VLAN_XLOCK_ASSERT(); - KASSERT(trunk->hwidth > 0, ("%s: hwidth not positive", __func__)); - b = 1 << (trunk->hwidth - 1); - i = HASH(ifv->ifv_vid, trunk->hmask); + i = HASH(ifv->ifv_vid); CK_SLIST_FOREACH(ifv2, &trunk->hash[i], ifv_list) if (ifv2 == ifv) { trunk->refcnt--; CK_SLIST_REMOVE(&trunk->hash[i], ifv2, ifvlan, ifv_list); - if (trunk->refcnt < (b * b) / 2) - vlan_growhash(trunk, -1); return (0); } @@ -482,52 +466,6 @@ return (ENOENT); /*NOTREACHED*/ } -/* - * Grow the hash larger or smaller if memory permits. - */ -static void -vlan_growhash(struct ifvlantrunk *trunk, int howmuch) -{ - struct ifvlan *ifv; - struct ifvlanhead *hash2; - int hwidth2, i, j, n, n2; - - VLAN_XLOCK_ASSERT(); - KASSERT(trunk->hwidth > 0, ("%s: hwidth not positive", __func__)); - - if (howmuch == 0) { - /* Harmless yet obvious coding error */ - printf("%s: howmuch is 0\n", __func__); - return; - } - - hwidth2 = trunk->hwidth + howmuch; - n = 1 << trunk->hwidth; - n2 = 1 << hwidth2; - /* Do not shrink the table below the default */ - if (hwidth2 < VLAN_DEF_HWIDTH) - return; - - hash2 = malloc(sizeof(struct ifvlanhead) * n2, M_VLAN, M_WAITOK); - for (j = 0; j < n2; j++) - CK_SLIST_INIT(&hash2[j]); - for (i = 0; i < n; i++) - while ((ifv = CK_SLIST_FIRST(&trunk->hash[i])) != NULL) { - CK_SLIST_REMOVE(&trunk->hash[i], ifv, ifvlan, ifv_list); - j = HASH(ifv->ifv_vid, n2 - 1); - CK_SLIST_INSERT_HEAD(&hash2[j], ifv, ifv_list); - } - NET_EPOCH_WAIT(); - free(trunk->hash, M_VLAN); - trunk->hash = hash2; - trunk->hwidth = hwidth2; - trunk->hmask = n2 - 1; - - if (bootverbose) - if_printf(trunk->parent, - "VLAN hash table resized from %d to %d buckets\n", n, n2); -} - static __inline struct ifvlan * vlan_gethash(struct ifvlantrunk *trunk, uint16_t vid) { @@ -535,7 +473,7 @@ NET_EPOCH_ASSERT(); - CK_SLIST_FOREACH(ifv, &trunk->hash[HASH(vid, trunk->hmask)], ifv_list) + CK_SLIST_FOREACH(ifv, &trunk->hash[HASH(vid)], ifv_list) if (ifv->ifv_vid == vid) return (ifv); return (NULL); @@ -549,7 +487,7 @@ int i; struct ifvlan *ifv; - for (i = 0; i < (1 << trunk->hwidth); i++) { + for (i = 0; i <= VLAN_HMASK; i++) { printf("%d: ", i); CK_SLIST_FOREACH(ifv, &trunk->hash[i], ifv_list) printf("%s ", ifv->ifv_ifp->if_xname);