diff options
Diffstat (limited to 'nest/rt-attr.c')
| -rw-r--r-- | nest/rt-attr.c | 112 |
1 files changed, 33 insertions, 79 deletions
diff --git a/nest/rt-attr.c b/nest/rt-attr.c index ab0069b5..bb2b3561 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -52,18 +52,19 @@ #include "nest/attrs.h" #include "lib/alloca.h" #include "lib/hash.h" +#include "lib/idm.h" #include "lib/resource.h" #include "lib/string.h" +#include <stddef.h> + pool *rta_pool; static slab *rta_slab; static slab *mpnh_slab; static slab *rte_src_slab; -/* rte source ID bitmap */ -static u32 *src_ids; -static u32 src_id_size, src_id_used, src_id_pos; +static struct idm src_ids; #define SRC_ID_INIT_SIZE 4 /* rte source hash */ @@ -87,64 +88,11 @@ rte_src_init(void) { rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src)); - src_id_pos = 0; - src_id_size = SRC_ID_INIT_SIZE; - src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32)); - - /* ID 0 is reserved */ - src_ids[0] = 1; - src_id_used = 1; + idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE); HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER); } -static inline int u32_cto(uint x) { return ffs(~x) - 1; } - -static inline u32 -rte_src_alloc_id(void) -{ - int i, j; - for (i = src_id_pos; i < src_id_size; i++) - if (src_ids[i] != 0xffffffff) - goto found; - - /* If we are at least 7/8 full, expand */ - if (src_id_used > (src_id_size * 28)) - { - src_id_size *= 2; - src_ids = mb_realloc(src_ids, src_id_size * sizeof(u32)); - bzero(src_ids + i, (src_id_size - i) * sizeof(u32)); - goto found; - } - - for (i = 0; i < src_id_pos; i++) - if (src_ids[i] != 0xffffffff) - goto found; - - ASSERT(0); - - found: - ASSERT(i < 0x8000000); - - src_id_pos = i; - j = u32_cto(src_ids[i]); - - src_ids[i] |= (1 << j); - src_id_used++; - return 32 * i + j; -} - -static inline void -rte_src_free_id(u32 id) -{ - int i = id / 32; - int j = id % 32; - - ASSERT((i < src_id_size) && (src_ids[i] & (1 << j))); - src_ids[i] &= ~(1 << j); - src_id_used--; -} - HASH_DEFINE_REHASH_FN(RSH, struct rte_src) @@ -165,7 +113,7 @@ rt_get_source(struct proto *p, u32 id) src = sl_alloc(rte_src_slab); src->proto = p; src->private_id = id; - src->global_id = rte_src_alloc_id(); + src->global_id = idm_alloc(&src_ids); src->uc = 0; HASH_INSERT2(src_hash, RSH, rta_pool, src); @@ -181,7 +129,7 @@ rt_prune_sources(void) if (src->uc == 0) { HASH_DO_REMOVE(src_hash, RSH, sp); - rte_src_free_id(src->global_id); + idm_free(&src_ids, src->global_id); sl_free(rte_src_slab, src); } } @@ -195,10 +143,10 @@ rt_prune_sources(void) * Multipath Next Hop */ -static inline uint +static inline u32 mpnh_hash(struct mpnh *x) { - uint h = 0; + u32 h = 0; for (; x; x = x->next) h ^= ipa_hash(x->gw); @@ -957,7 +905,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 */ @@ -965,29 +914,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); } /** @@ -1036,8 +974,24 @@ rta_alloc_hash(void) static inline uint rta_hash(rta *a) { - return (((uint) (uintptr_t) a->src) ^ ipa_hash(a->gw) ^ - mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs)) & 0xffff; + u64 h; + mem_hash_init(&h); +#define MIX(f) mem_hash_mix(&h, &(a->f), sizeof(a->f)); + MIX(src); + MIX(hostentry); + MIX(iface); + MIX(gw); + MIX(from); + MIX(igp_metric); + MIX(source); + MIX(scope); + MIX(cast); + MIX(dest); + MIX(flags); + MIX(aflags); +#undef MIX + + return mem_hash_value(&h) ^ mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs); } static inline int |