Implements ADD-PATH extension for BGP.

Allows to send and receive multiple routes for one network by one BGP
session. Also contains necessary core changes to support this (routing
tables accepting several routes for one network from one protocol).
It needs some more cleanup before merging to the master branch.

1 files changed, 107 insertions, 10 deletions

diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index e5bc84dd..837a6861 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -621,12 +621,14 @@ bgp_encode_attrs(struct bgp_proto *p, byte *w, ea_list *attrs, int remains)
   return -1;
 }
 
+/*
 static void
 bgp_init_prefix(struct fib_node *N)
 {
   struct bgp_prefix *p = (struct bgp_prefix *) N;
   p->bucket_node.next = NULL;
 }
+*/
 
 static int
 bgp_compare_u32(const u32 *x, const u32 *y)
@@ -870,30 +872,125 @@ bgp_free_bucket(struct bgp_proto *p, struct bgp_bucket *buck)
   mb_free(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);
+}
+
+static inline u32 px_hash_size(struct bgp_proto *p)
+{ return 1 << p->px_hash_order; }
+
+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;
+
+  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);
+}
+
+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);
+
+  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;
+
+  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);
+
+  return bp;
+}
+
+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;
+  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);
+}
+
+
 void
 bgp_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
 {
   struct bgp_proto *p = (struct bgp_proto *) P;
   struct bgp_bucket *buck;
   struct bgp_prefix *px;
+  rte *key;
+  u32 path_id;
 
   DBG("BGP: Got route %I/%d %s\n", n->n.prefix, n->n.pxlen, new ? "up" : "down");
 
   if (new)
     {
+      key = new;
       buck = bgp_get_bucket(p, n, attrs, new->attrs->source != RTS_BGP);
       if (!buck)			/* Inconsistent attribute list */
 	return;
     }
   else
     {
+      key = old;
       if (!(buck = p->withdraw_bucket))
 	{
 	  buck = p->withdraw_bucket = mb_alloc(P->pool, sizeof(struct bgp_bucket));
 	  init_list(&buck->prefixes);
 	}
     }
-  px = fib_get(&p->prefix_fib, &n->n.prefix, n->n.pxlen);
+  path_id = p->add_path_tx ? key->attrs->src->global_id : 0;
+  px = bgp_get_prefix(p, n->n.prefix, n->n.pxlen, path_id);
   if (px->bucket_node.next)
     {
       DBG("\tRemoving old entry.\n");
@@ -1021,7 +1118,7 @@ bgp_update_attrs(struct bgp_proto *p, rte *e, ea_list **attrs, struct linpool *p
   if (rr)
     {
       /* Handling route reflection, RFC 4456 */
-      struct bgp_proto *src = (struct bgp_proto *) e->attrs->proto;
+      struct bgp_proto *src = (struct bgp_proto *) e->attrs->src->proto;
 
       a = ea_find(e->attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGINATOR_ID));
       if (!a)
@@ -1071,7 +1168,8 @@ bgp_import_control(struct proto *P, rte **new, ea_list **attrs, struct linpool *
 {
   rte *e = *new;
   struct bgp_proto *p = (struct bgp_proto *) P;
-  struct bgp_proto *new_bgp = (e->attrs->proto->proto == &proto_bgp) ? (struct bgp_proto *) e->attrs->proto : NULL;
+  struct bgp_proto *new_bgp = (e->attrs->src->proto->proto == &proto_bgp) ?
+    (struct bgp_proto *) e->attrs->src->proto : NULL;
 
   if (p == new_bgp)			/* Poison reverse updates */
     return -1;
@@ -1110,7 +1208,7 @@ bgp_get_neighbor(rte *r)
   if (e && as_path_get_first(e->u.ptr, &as))
     return as;
   else
-    return ((struct bgp_proto *) r->attrs->proto)->remote_as;
+    return ((struct bgp_proto *) r->attrs->src->proto)->remote_as;
 }
 
 static inline int
@@ -1123,8 +1221,8 @@ rte_resolvable(rte *rt)
 int
 bgp_rte_better(rte *new, rte *old)
 {
-  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->proto;
-  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->proto;
+  struct bgp_proto *new_bgp = (struct bgp_proto *) new->attrs->src->proto;
+  struct bgp_proto *old_bgp = (struct bgp_proto *) old->attrs->src->proto;
   eattr *x, *y;
   u32 n, o;
 
@@ -1258,7 +1356,7 @@ same_group(rte *r, u32 lpref, u32 lasn)
 static inline int
 use_deterministic_med(rte *r)
 {
-  struct proto *P = r->attrs->proto;
+  struct proto *P = r->attrs->src->proto;
   return (P->proto == &proto_bgp) && ((struct bgp_proto *) P)->cf->deterministic_med;
 }
 
@@ -1543,7 +1641,6 @@ bgp_decode_attrs(struct bgp_conn *conn, byte *attr, unsigned int len, struct lin
   int withdraw = 0;
 
   bzero(a, sizeof(rta));
-  a->proto = &bgp->p;
   a->source = RTS_BGP;
   a->scope = SCOPE_UNIVERSE;
   a->cast = RTC_UNICAST;
@@ -1752,14 +1849,14 @@ bgp_get_attr(eattr *a, byte *buf, int buflen)
 }
 
 void
-bgp_attr_init(struct bgp_proto *p)
+bgp_init_bucket_table(struct bgp_proto *p)
 {
   p->hash_size = 256;
   p->hash_limit = p->hash_size * 4;
   p->bucket_hash = mb_allocz(p->p.pool, p->hash_size * sizeof(struct bgp_bucket *));
   init_list(&p->bucket_queue);
   p->withdraw_bucket = NULL;
-  fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
+  // fib_init(&p->prefix_fib, p->p.pool, sizeof(struct bgp_prefix), 0, bgp_init_prefix);
 }
 
 void