Merge branch 'add-path'

5 files changed, 25 insertions, 64 deletions

diff --git a/proto/bfd/bfd.c b/proto/bfd/bfd.c
index b697e84c..315d132b 100644
--- a/proto/bfd/bfd.c
+++ b/proto/bfd/bfd.c
@@ -106,13 +106,13 @@
 
 #define HASH_ID_KEY(n)		n->loc_id
 #define HASH_ID_NEXT(n)		n->next_id
-#define HASH_ID_EQ(a,b)		(a == b)
-#define HASH_ID_FN(k)		(k)
+#define HASH_ID_EQ(a,b)		a == b
+#define HASH_ID_FN(k)		k
 
 #define HASH_IP_KEY(n)		n->addr
 #define HASH_IP_NEXT(n)		n->next_ip
 #define HASH_IP_EQ(a,b)		ipa_equal(a,b)
-#define HASH_IP_FN(k)		ipa_hash(k)
+#define HASH_IP_FN(k)		ipa_hash32(k)
 
 static list bfd_proto_list;
 static list bfd_wait_list;
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index d34e2ae3..1d37bfd7 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -58,6 +58,7 @@
  * bgp_reconstruct_4b_attrs()).
  */
 
+
 static byte bgp_mandatory_attrs[] = { BA_ORIGIN, BA_AS_PATH
 #ifndef IPV6
 ,BA_NEXT_HOP
@@ -875,70 +876,40 @@ bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
 
 /* Prefix hash table */
 
-static inline u32 prefix_hash(ip_addr prefix, int pxlen, u32 path_id, u32 order)
-{
-  u32 x = ipa_hash(prefix) + pxlen + path_id;
-  return (x * 2902958171u) >> (32 - order);
-}
+#define PXH_KEY(n1)		n1->n.prefix, n1->n.pxlen, n1->path_id
+#define PXH_NEXT(n)		n->next
+#define PXH_EQ(p1,l1,i1,p2,l2,i2) ipa_equal(p1, p2) && l1 == l2 && i1 == i2
+#define PXH_FN(p,l,i)		ipa_hash32(p) ^ u32_hash((l << 16) ^ i)
+
+#define PXH_REHASH		bgp_pxh_rehash
+#define PXH_PARAMS		/8, *2, 2, 2, 8, 20
+
 
-static inline u32 px_hash_size(struct bgp_proto *p)
-{ return 1 << p->px_hash_order; }
+HASH_DEFINE_REHASH_FN(PXH, struct bgp_prefix)
 
 void
 bgp_init_prefix_table(struct bgp_proto *p, u32 order)
 {
-  p->px_hash_count = 0;
-  p->px_hash_order = order;
-  p->prefix_table = mb_allocz(p->p.pool, px_hash_size(p) * sizeof(struct bgp_prefix *));
-  p->prefix_slab = sl_new(p->p.pool, sizeof(struct bgp_prefix));
-}
-
-static void
-bgp_rehash_prefix_table(struct bgp_proto *p, int step)
-{
-  struct bgp_prefix **old_tab, *px, *px_next;
-  u32 old_size, hash, i;
+  HASH_INIT(p->prefix_hash, p->p.pool, order);
 
-  old_tab = p->prefix_table;
-  old_size = px_hash_size(p);
-
-  p->px_hash_order += step;
-  p->prefix_table = mb_allocz(p->p.pool, px_hash_size(p) * sizeof(struct bgp_prefix *));
-  
-  for (i = 0; i < old_size; i++)
-    for (px = old_tab[i]; px; px = px_next)
-      {
-	px_next = px->next;
-	hash = prefix_hash(px->n.prefix, px->n.pxlen, px->path_id, p->px_hash_order);
-	px->next = p->prefix_table[hash];
-	p->prefix_table[hash] = px;
-      }
-
-  mb_free(old_tab);
+  p->prefix_slab = sl_new(p->p.pool, sizeof(struct bgp_prefix));
 }
 
 static struct bgp_prefix *
 bgp_get_prefix(struct bgp_proto *p, ip_addr prefix, int pxlen, u32 path_id)
 {
-  struct bgp_prefix *bp;
-  u32 hash = prefix_hash(prefix, pxlen, path_id, p->px_hash_order);
+  struct bgp_prefix *bp = HASH_FIND(p->prefix_hash, PXH, prefix, pxlen, path_id);
 
-  for (bp = p->prefix_table[hash]; bp; bp = bp->next)
-    if (bp->n.pxlen == pxlen && ipa_equal(bp->n.prefix, prefix) && bp->path_id == path_id)
-      return bp;
+  if (bp)
+    return bp;
 
   bp = sl_alloc(p->prefix_slab);
   bp->n.prefix = prefix;
   bp->n.pxlen = pxlen;
   bp->path_id = path_id;
-  bp->next = p->prefix_table[hash];
-  p->prefix_table[hash] = bp;
-
   bp->bucket_node.next = NULL;
 
-  p->px_hash_count++;
-  if ((p->px_hash_count > px_hash_size(p)) && (p->px_hash_order < 18))
-    bgp_rehash_prefix_table(p, 1);
+  HASH_INSERT2(p->prefix_hash, PXH, p->p.pool, bp);
 
   return bp;
 }
@@ -946,19 +917,8 @@ bgp_get_prefix(struct bgp_proto *p, ip_addr prefix, int pxlen, u32 path_id)
 void
 bgp_free_prefix(struct bgp_proto *p, struct bgp_prefix *bp)
 {
-  struct bgp_prefix **bpp;
-  u32 hash = prefix_hash(bp->n.prefix, bp->n.pxlen, bp->path_id, p->px_hash_order);
-
-  for (bpp = &p->prefix_table[hash]; *bpp; *bpp = (*bpp)->next)
-    if (*bpp == bp)
-      break;
-
-  *bpp = bp->next;
+  HASH_REMOVE2(p->prefix_hash, PXH, p->p.pool, bp);
   sl_free(p->prefix_slab, bp);
-
-  p->px_hash_count--;
-  if ((p->px_hash_count < (px_hash_size(p) / 4)) && (p->px_hash_order > 10))
-    bgp_rehash_prefix_table(p, -1);
 }
 
 
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index 98c49b30..a748669d 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -68,6 +68,7 @@
 
 #include "bgp.h"
 
+
 struct linpool *bgp_linpool;		/* Global temporary pool */
 static sock *bgp_listen_sk;		/* Global listening socket */
 static int bgp_counter;			/* Number of protocol instances using the listening socket */
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index a35c362c..170b6bbe 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -12,6 +12,7 @@
 #include <stdint.h>
 #include "nest/route.h"
 #include "nest/bfd.h"
+#include "lib/hash.h"
 
 struct linpool;
 struct eattr;
@@ -118,10 +119,8 @@ struct bgp_proto {
   struct timer *startup_timer;		/* Timer used to delay protocol startup due to previous errors (startup_delay) */
   struct bgp_bucket **bucket_hash;	/* Hash table of attribute buckets */
   unsigned int hash_size, hash_count, hash_limit;
-  // struct fib prefix_fib;		/* Prefixes to be sent */
-  struct bgp_prefix **prefix_table;	/* Prefixes to be sent */
+  HASH(struct bgp_prefix) prefix_hash;	/* Prefixes to be sent */
   slab *prefix_slab;			/* Slab holding prefix nodes */
-  u32 px_hash_order, px_hash_count;
   list bucket_queue;			/* Queue of buckets to send */
   struct bgp_bucket *withdraw_bucket;	/* Withdrawn routes */
   unsigned startup_delay;		/* Time to delay protocol startup by due to errors */
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 42064332..649d8078 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -244,7 +244,7 @@ bgp_encode_prefixes(struct bgp_proto *p, byte *w, struct bgp_bucket *buck, unsig
   ip_addr a;
   int bytes;
 
-  while (!EMPTY_LIST(buck->prefixes) && remains >= (1+sizeof(ip_addr)))
+  while (!EMPTY_LIST(buck->prefixes) && (remains >= (5+sizeof(ip_addr))))
     {
       struct bgp_prefix *px = SKIP_BACK(struct bgp_prefix, bucket_node, HEAD(buck->prefixes));
       DBG("\tDequeued route %I/%d\n", px->n.prefix, px->n.pxlen);
@@ -253,6 +253,7 @@ bgp_encode_prefixes(struct bgp_proto *p, byte *w, struct bgp_bucket *buck, unsig
 	{
 	  put_u32(w, px->path_id);
 	  w += 4;
+	  remains -= 4;
 	}
 
       *w++ = px->n.pxlen;