Nexthop: Support for label stack in nest

6 files changed, 83 insertions, 29 deletions

diff --git a/nest/route.h b/nest/route.h
index 154e027e..d9a1737b 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -338,6 +338,8 @@ struct nexthop {
   struct iface *iface;			/* Outgoing interface */
   struct nexthop *next;
   byte weight;
+  byte labels;				/* Number of labels appended */
+  u32 label[0];
 };
 
 struct rte_src {
@@ -510,16 +512,21 @@ uint ea_hash(ea_list *e);	/* Calculate 16-bit hash value */
 ea_list *ea_append(ea_list *to, ea_list *what);
 void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max);
 
+#define NEXTHOP_MAX_LABEL_STACK 8
+
+static inline size_t nexthop_size(const struct nexthop *nh)
+{ return sizeof(struct nexthop) + sizeof(u32)*nh->labels; }
 int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath nexthops */
 static inline int nexthop_same(struct nexthop *x, struct nexthop *y)
 { return (x == y) || nexthop__same(x, y); }
 struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp);
 static inline void nexthop_link(struct rta *a, struct nexthop *from)
-{ a->nh.gw = from->gw; a->nh.iface = from->iface; a->nh.weight = from->weight; a->nh.next = from->next; }
+{ memcpy(&a->nh, from, nexthop_size(from)); }
 void nexthop_insert(struct nexthop *n, struct nexthop *y);
 int nexthop_is_sorted(struct nexthop *x);
 
 void rta_init(void);
+static inline size_t rta_size(const rta *a) { return sizeof(rta) + sizeof(u32)*a->nh.labels; }
 rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
 static inline int rta_is_cached(rta *r) { return r->aflags & RTAF_CACHED; }
 static inline rta *rta_clone(rta *r) { r->uc++; return r; }
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index e575ba4a..d3671a53 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -60,8 +60,8 @@
 
 pool *rta_pool;
 
-static slab *rta_slab;
-static slab *nexthop_slab;
+static slab *rta_slab_[4];
+static slab *nexthop_slab_[4];
 static slab *rte_src_slab;
 
 static struct idm src_ids;
@@ -148,7 +148,11 @@ nexthop_hash(struct nexthop *x)
 {
   u32 h = 0;
   for (; x; x = x->next)
-    h ^= ipa_hash(x->gw);
+  {
+    h ^= ipa_hash(x->gw) ^ (h << 5) ^ (h >> 9);
+    for (int i=0; i<x->labels; i++)
+      h ^= x->label[i] ^ (h << 6) ^ (h >> 7);
+  }
 
   return h;
 }
@@ -157,10 +161,15 @@ int
 nexthop__same(struct nexthop *x, struct nexthop *y)
 {
   for (; x && y; x = x->next, y = y->next)
-    if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) || (x->weight != y->weight))
+  {
+    if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) || (x->weight != y->weight) || (x->labels != y->labels))
       return 0;
+    for (int i=0; i<x->labels; i++)
+      if (x->label[i] != y->label[i])
+	return 0;
+  }
 
-  return x == y;
+  return 1;
 }
 
 static int
@@ -182,17 +191,28 @@ nexthop_compare_node(struct nexthop *x, struct nexthop *y)
   if (r)
     return r;
 
+  r = ((int) y->labels) - ((int) x->labels);
+  if (r)
+    return r;
+
+  for (int i=0; i<y->labels; i++)
+  {
+    r = ((int) y->label[i]) - ((int) x->label[i]);
+    if (r)
+      return r;
+  }
+
   return ((int) x->iface->index) - ((int) y->iface->index);
 }
 
 static inline struct nexthop *
 nexthop_copy_node(const struct nexthop *src, linpool *lp)
 {
-  struct nexthop *n = lp_alloc(lp, sizeof(struct nexthop));
-  n->gw = src->gw;
-  n->iface = src->iface;
+  struct nexthop *n = lp_alloc(lp, nexthop_size(src));
+
+  memcpy(n, src, nexthop_size(src));
   n->next = NULL;
-  n->weight = src->weight;
+
   return n;
 }
 
@@ -291,6 +311,12 @@ nexthop_is_sorted(struct nexthop *x)
   return 1;
 }
 
+static inline slab *
+nexthop_slab(struct nexthop *nh)
+{
+  return nexthop_slab_[nh->labels > 2 ? 3 : nh->labels];
+}
+
 static struct nexthop *
 nexthop_copy(struct nexthop *o)
 {
@@ -299,7 +325,7 @@ nexthop_copy(struct nexthop *o)
 
   for (; o; o = o->next)
     {
-      struct nexthop *n = sl_alloc(nexthop_slab);
+      struct nexthop *n = sl_alloc(nexthop_slab(o));
       n->gw = o->gw;
       n->iface = o->iface;
       n->next = NULL;
@@ -320,7 +346,7 @@ nexthop_free(struct nexthop *o)
   while (o)
     {
       n = o->next;
-      sl_free(nexthop_slab, o);
+      sl_free(nexthop_slab(o), o);
       o = n;
     }
 }
@@ -1024,20 +1050,24 @@ rta_same(rta *x, rta *y)
 	  x->scope == y->scope &&
 	  x->dest == y->dest &&
 	  x->igp_metric == y->igp_metric &&
-	  ipa_equal(x->nh.gw, y->nh.gw) &&
 	  ipa_equal(x->from, y->from) &&
-	  x->nh.iface == y->nh.iface &&
 	  x->hostentry == y->hostentry &&
 	  nexthop_same(&(x->nh), &(y->nh)) &&
 	  ea_same(x->eattrs, y->eattrs));
 }
 
+static inline slab *
+rta_slab(rta *a)
+{
+  return rta_slab_[a->nh.labels > 2 ? 3 : a->nh.labels];
+}
+
 static rta *
 rta_copy(rta *o)
 {
-  rta *r = sl_alloc(rta_slab);
+  rta *r = sl_alloc(rta_slab(o));
 
-  memcpy(r, o, sizeof(rta));
+  memcpy(r, o, rta_size(o));
   r->uc = 1;
   r->nh.next = nexthop_copy(o->nh.next);
   r->eattrs = ea_list_copy(o->eattrs);
@@ -1138,14 +1168,14 @@ rta__free(rta *a)
   if (a->nh.next)
     nexthop_free(a->nh.next);
   ea_free(a->eattrs);
-  sl_free(rta_slab, a);
+  sl_free(rta_slab(a), a);
 }
 
 rta *
 rta_do_cow(rta *o, linpool *lp)
 {
-  rta *r = lp_alloc(lp, sizeof(rta));
-  memcpy(r, o, sizeof(rta));
+  rta *r = lp_alloc(lp, rta_size(o));
+  memcpy(r, o, rta_size(o));
   r->aflags = 0;
   r->uc = 0;
   return r;
@@ -1176,6 +1206,9 @@ rta_dump(rta *a)
     for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
       {
 	if (ipa_nonzero(nh->gw)) debug(" ->%I", nh->gw);
+	if (nh->labels) debug(" L %d", nh->label[0]);
+	for (int i=1; i<nh->labels; i++)
+	  debug("/%d", nh->label[i]);
 	debug(" [%s]", nh->iface ? nh->iface->name : "???");
       }
   if (a->eattrs)
@@ -1233,8 +1266,17 @@ void
 rta_init(void)
 {
   rta_pool = rp_new(&root_pool, "Attributes");
-  rta_slab = sl_new(rta_pool, sizeof(rta));
-  nexthop_slab = sl_new(rta_pool, sizeof(struct nexthop));
+
+  rta_slab_[0] = sl_new(rta_pool, sizeof(rta));
+  rta_slab_[1] = sl_new(rta_pool, sizeof(rta) + sizeof(u32));
+  rta_slab_[2] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*2);
+  rta_slab_[3] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*NEXTHOP_MAX_LABEL_STACK);
+
+  nexthop_slab_[0] = sl_new(rta_pool, sizeof(struct nexthop));
+  nexthop_slab_[1] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32));
+  nexthop_slab_[2] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*2);
+  nexthop_slab_[3] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*NEXTHOP_MAX_LABEL_STACK);
+
   rta_alloc_hash();
   rte_src_init();
 }
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 46857d0d..a7ceddb8 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -1782,7 +1782,7 @@ static inline rte *
 rt_next_hop_update_rte(rtable *tab UNUSED, rte *old)
 {
   rta a;
-  memcpy(&a, old->attrs, sizeof(rta));
+  memcpy(&a, old->attrs, rta_size(old->attrs));
   rta_apply_hostentry(&a, old->attrs->hostentry);
   a.aflags = 0;
 
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index d28d463b..74f47810 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -37,6 +37,7 @@ static inline struct nexthop *
 new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
 {
   struct nexthop *nh = lp_alloc(p->nhpool, sizeof(struct nexthop));
+  nh->labels = 0;
   nh->gw = gw;
   nh->iface = iface;
   nh->next = NULL;
diff --git a/proto/pipe/pipe.c b/proto/pipe/pipe.c
index 8924c200..a4d371fe 100644
--- a/proto/pipe/pipe.c
+++ b/proto/pipe/pipe.c
@@ -43,6 +43,8 @@
 
 #include "pipe.h"
 
+#include <alloca.h>
+
 static void
 pipe_rt_notify(struct proto *P, struct channel *src_ch, net *n, rte *new, rte *old, ea_list *attrs)
 {
@@ -51,7 +53,7 @@ pipe_rt_notify(struct proto *P, struct channel *src_ch, net *n, rte *new, rte *o
   struct rte_src *src;
 
   rte *e;
-  rta a;
+  rta *a;
 
   if (!new && !old)
     return;
@@ -65,12 +67,13 @@ pipe_rt_notify(struct proto *P, struct channel *src_ch, net *n, rte *new, rte *o
 
   if (new)
     {
-      memcpy(&a, new->attrs, sizeof(rta));
+      a = alloca(rta_size(new->attrs));
+      memcpy(a, new->attrs, rta_size(new->attrs));
 
-      a.aflags = 0;
-      a.eattrs = attrs;
-      a.hostentry = NULL;
-      e = rte_get_temp(&a);
+      a->aflags = 0;
+      a->eattrs = attrs;
+      a->hostentry = NULL;
+      e = rte_get_temp(a);
       e->pflags = 0;
 
       /* Copy protocol specific embedded attributes. */
@@ -78,7 +81,7 @@ pipe_rt_notify(struct proto *P, struct channel *src_ch, net *n, rte *new, rte *o
       e->pref = new->pref;
       e->pflags = new->pflags;
 
-      src = a.src;
+      src = a->src;
     }
   else
     {
diff --git a/proto/static/static.c b/proto/static/static.c
index a63d4d29..9ecf6df8 100644
--- a/proto/static/static.c
+++ b/proto/static/static.c
@@ -88,6 +88,7 @@ static_install(struct proto *p, struct static_route *r)
 	    nh->gw = r2->via;
 	    nh->iface = r2->neigh->iface;
 	    nh->weight = r2->weight;
+	    nh->labels = 0;
 	    if (a.nh.next)
 	      nexthop_insert(&(a.nh), nh);
 	    r2->state |= STS_INSTALLED;