1 files changed, 34 insertions, 80 deletions

diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index edf27d44..94f25de8 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)
-{
-  uint 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);
 
@@ -580,7 +528,7 @@ ea_do_prune(ea_list *e)
       if ((s0->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF)
 	{
 	  *d = *s0;
-	  d->type = (d->type & ~EAF_ORIGINATED) | (s[-1].type & EAF_ORIGINATED);
+	  d->type = (d->type & ~(EAF_ORIGINATED|EAF_FRESH)) | (s[-1].type & EAF_ORIGINATED);
 	  d++;
 	  i++;
 	}
@@ -972,7 +920,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 */
@@ -980,29 +929,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);
 }
 
 /**
@@ -1051,8 +989,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