diff options
| -rw-r--r-- | lib/hash.h | 12 | ||||
| -rw-r--r-- | nest/route.h | 18 | ||||
| -rw-r--r-- | nest/rt-attr.c | 29 |
3 files changed, 31 insertions, 28 deletions
@@ -178,3 +178,15 @@ #define HASH_WALK_FILTER_END } while (0) +static inline uint +mem_hash(void *p, int s) +{ + const char *pp = p; + const u64 multiplier = 0xb38bc09a61202731ULL; + u64 value = 0x001047d54778bcafULL; + for (int i=0;i<s;i++) + value = value*multiplier + pp[i]; + + return ((value >> 32) ^ (value & 0xffffffff)); +} + diff --git a/nest/route.h b/nest/route.h index b68f614f..22fca331 100644 --- a/nest/route.h +++ b/nest/route.h @@ -345,22 +345,22 @@ struct rte_src { typedef struct rta { struct rta *next, **pprev; /* Hash chain */ + u32 uc; /* Use count */ + u32 hash_key; /* Hash over important fields */ + struct mpnh *nexthops; /* Next-hops for multipath routes */ + struct ea_list *eattrs; /* Extended Attribute chain */ struct rte_src *src; /* Route source that created the route */ - unsigned uc; /* Use count */ + struct hostentry *hostentry; /* Hostentry for recursive next-hops */ + struct iface *iface; /* Outgoing interface */ + ip_addr gw; /* Next hop */ + ip_addr from; /* Advertising router */ + u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */ byte source; /* Route source (RTS_...) */ byte scope; /* Route scope (SCOPE_... -- see ip.h) */ byte cast; /* Casting type (RTC_...) */ byte dest; /* Route destination type (RTD_...) */ byte flags; /* Route flags (RTF_...), now unused */ byte aflags; /* Attribute cache flags (RTAF_...) */ - u16 hash_key; /* Hash over important fields */ - u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */ - ip_addr gw; /* Next hop */ - ip_addr from; /* Advertising router */ - struct hostentry *hostentry; /* Hostentry for recursive next-hops */ - struct iface *iface; /* Outgoing interface */ - struct mpnh *nexthops; /* Next-hops for multipath routes */ - struct ea_list *eattrs; /* Extended Attribute chain */ } rta; #define RTS_DUMMY 0 /* Dummy route to be removed soon */ diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 0637867b..9777a2d2 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -56,6 +56,8 @@ #include "lib/resource.h" #include "lib/string.h" +#include <stddef.h> + pool *rta_pool; static slab *rta_slab; @@ -875,7 +877,8 @@ ea_dump(ea_list *e) inline uint ea_hash(ea_list *e) { - u32 h = 0; + const u64 mul = 0x68576150f3d6847; + u64 h = 0xafcef24eda8b29; int i; if (e) /* Assuming chain of length 1 */ @@ -883,29 +886,18 @@ ea_hash(ea_list *e) for(i=0; i<e->count; i++) { struct eattr *a = &e->attrs[i]; - h ^= a->id; + h ^= a->id; h *= mul; if (a->type & EAF_EMBEDDED) h ^= a->u.data; else { struct adata *d = a->u.ptr; - int size = d->length; - byte *z = d->data; - while (size >= 4) - { - h ^= *(u32 *)z; - z += 4; - size -= 4; - } - while (size--) - h = (h >> 24) ^ (h << 8) ^ *z++; + h ^= mem_hash(d->data, d->length); } + h *= mul; } - h ^= h >> 16; - h ^= h >> 6; - h &= 0xffff; } - return h; + return (h >> 32) ^ (h & 0xffffffff); } /** @@ -954,9 +946,8 @@ rta_alloc_hash(void) static inline uint rta_hash(rta *a) { - /* XXXX fully convert to u32 hashing */ - return (((uint) (uintptr_t) a->src) ^ (ipa_hash(a->gw) >> 16) ^ - (mpnh_hash(a->nexthops) >> 16) ^ ea_hash(a->eattrs)) & 0xffff; + return mem_hash(a + offsetof(rta, src), sizeof(rta) - offsetof(rta, src)) ^ + mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs); } static inline int |