Moved nexthop from struct rta to extended attribute.

This doesn't do anything more than to put the whole structure inside
adata. The overall performance is certainly going downhill; we'll
optimize this later.

Anyway, this is one of the latest items inside rta and in several
commits we may drop rta completely and move to eattrs-only routes.

4 files changed, 202 insertions, 254 deletions

diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index dc4fe785..bd7ca425 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -57,6 +57,7 @@
 #include "lib/string.h"
 
 #include <stddef.h>
+#include <stdlib.h>
 
 const adata null_adata;		/* adata of length 0 */
 
@@ -108,6 +109,11 @@ struct ea_class ea_gen_source = {
   .format = ea_gen_source_format,
 };
 
+struct ea_class ea_gen_nexthop = {
+  .name = "nexthop",
+  .type = T_NEXTHOP_LIST,
+};
+
 struct ea_class ea_mpls_labels = {
   .name = "mpls_labels",
   .type = T_CLIST,
@@ -124,8 +130,7 @@ const char * rta_dest_names[RTD_MAX] = {
 
 pool *rta_pool;
 
-static slab *rta_slab_[4];
-static slab *nexthop_slab_[4];
+static slab *rta_slab;
 static slab *rte_src_slab;
 
 static struct idm src_ids;
@@ -204,50 +209,10 @@ rt_prune_sources(void)
  *	Multipath Next Hop
  */
 
-static inline u32
-nexthop_hash(struct nexthop *x)
-{
-  u32 h = 0;
-  for (; x; x = x->next)
-  {
-    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;
-}
-
-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->flags != y->flags) || (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;
-}
-
 static int
 nexthop_compare_node(const struct nexthop *x, const struct nexthop *y)
 {
   int r;
-
-  if (!x)
-    return 1;
-
-  if (!y)
-    return -1;
-
   /* Should we also compare flags ? */
 
   r = ((int) y->weight) - ((int) x->weight);
@@ -272,23 +237,16 @@ nexthop_compare_node(const struct nexthop *x, const struct nexthop *y)
   return ((int) x->iface->index) - ((int) y->iface->index);
 }
 
-static inline struct nexthop *
-nexthop_copy_node(const struct nexthop *src, linpool *lp)
+static int
+nexthop_compare_qsort(const void *x, const void *y)
 {
-  struct nexthop *n = lp_alloc(lp, nexthop_size(src));
-
-  memcpy(n, src, nexthop_size(src));
-  n->next = NULL;
-
-  return n;
+  return nexthop_compare_node( *(const struct nexthop **) x, *(const struct nexthop **) y );
 }
 
 /**
  * nexthop_merge - merge nexthop lists
  * @x: list 1
  * @y: list 2
- * @rx: reusability of list @x
- * @ry: reusability of list @y
  * @max: max number of nexthops
  * @lp: linpool for allocating nexthops
  *
@@ -305,134 +263,111 @@ nexthop_copy_node(const struct nexthop *src, linpool *lp)
  * resulting list is no longer needed. When reusability is not set, the
  * corresponding lists are not modified nor linked from the resulting list.
  */
-struct nexthop *
-nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp)
+struct nexthop_adata *
+nexthop_merge(struct nexthop_adata *xin, struct nexthop_adata *yin, int max, linpool *lp)
 {
-  struct nexthop *root = NULL;
-  struct nexthop **n = &root;
+  uint outlen = ADATA_SIZE(xin->ad.length) + ADATA_SIZE(yin->ad.length);
+  struct nexthop_adata *out = lp_alloc(lp, outlen);
+  out->ad.length = outlen - sizeof (struct adata);
+
+  struct nexthop *x = &xin->nh, *y = &yin->nh, *cur = &out->nh;
+  int xvalid, yvalid;
 
-  while ((x || y) && max--)
+  while (max--)
   {
-    int cmp = nexthop_compare_node(x, y);
+    xvalid = NEXTHOP_VALID(x, xin);
+    yvalid = NEXTHOP_VALID(y, yin);
+
+    if (!xvalid && !yvalid)
+      break;
+
+    ASSUME(NEXTHOP_VALID(cur, out));
+
+    int cmp = !xvalid ? 1 : !yvalid ? -1 : nexthop_compare_node(x, y);
 
     if (cmp < 0)
     {
-      ASSUME(x);
-      *n = rx ? x : nexthop_copy_node(x, lp);
-      x = x->next;
+      ASSUME(NEXTHOP_VALID(x, xin));
+      memcpy(cur, x, nexthop_size(x));
+      x = NEXTHOP_NEXT(x);
     }
     else if (cmp > 0)
     {
-      ASSUME(y);
-      *n = ry ? y : nexthop_copy_node(y, lp);
-      y = y->next;
+      ASSUME(NEXTHOP_VALID(y, yin));
+      memcpy(cur, y, nexthop_size(y));
+      y = NEXTHOP_NEXT(y);
     }
     else
     {
-      ASSUME(x && y);
-      *n = rx ? x : (ry ? y : nexthop_copy_node(x, lp));
-      x = x->next;
-      y = y->next;
+      ASSUME(NEXTHOP_VALID(x, xin));
+      memcpy(cur, x, nexthop_size(x));
+      x = NEXTHOP_NEXT(x);
+
+      ASSUME(NEXTHOP_VALID(y, yin));
+      y = NEXTHOP_NEXT(y);
     }
-    n = &((*n)->next);
+    cur = NEXTHOP_NEXT(cur);
   }
-  *n = NULL;
 
-  return root;
+  out->ad.length = (void *) cur - (void *) out->ad.data;
+
+  return out;
 }
 
-void
-nexthop_insert(struct nexthop **n, struct nexthop *x)
+struct nexthop_adata *
+nexthop_sort(struct nexthop_adata *nhad, linpool *lp)
 {
-  for (; *n; n = &((*n)->next))
-  {
-    int cmp = nexthop_compare_node(*n, x);
+  /* Count the nexthops */
+  uint cnt = 0;
+  NEXTHOP_WALK(nh, nhad)
+    cnt++;
 
-    if (cmp < 0)
-      continue;
-    else if (cmp > 0)
-      break;
-    else
-      return;
-  }
+  if (cnt <= 1)
+    return nhad;
 
-  x->next = *n;
-  *n = x;
-}
+  /* Get pointers to them */
+  struct nexthop **sptr = tmp_alloc(cnt * sizeof(struct nexthop *));
 
-struct nexthop *
-nexthop_sort(struct nexthop *x)
-{
-  struct nexthop *s = NULL;
+  uint i = 0;
+  NEXTHOP_WALK(nh, nhad)
+    sptr[i++] = nh;
+
+  /* Sort the pointers */
+  qsort(sptr, cnt, sizeof(struct nexthop *), nexthop_compare_qsort);
+
+  /* Allocate the output */
+  struct nexthop_adata *out = (struct nexthop_adata *) lp_alloc_adata(lp, nhad->ad.length);
+  struct nexthop *dest = &out->nh;
 
-  /* Simple insert-sort */
-  while (x)
+  /* Deduplicate nexthops while storing them */
+  for (uint i = 0; i < cnt; i++)
   {
-    struct nexthop *n = x;
-    x = n->next;
-    n->next = NULL;
+    if (i && !nexthop_compare_node(sptr[i], sptr[i-1]))
+      continue;
 
-    nexthop_insert(&s, n);
+    memcpy(dest, sptr[i], NEXTHOP_SIZE(sptr[i]));
+    dest = NEXTHOP_NEXT(dest);
   }
 
-  return s;
+  out->ad.length = (void *) dest - (void *) out->ad.data;
+  return out;
 }
 
 int
-nexthop_is_sorted(struct nexthop *x)
+nexthop_is_sorted(struct nexthop_adata *nhad)
 {
-  for (; x && x->next; x = x->next)
-    if (nexthop_compare_node(x, x->next) >= 0)
+  struct nexthop *prev = NULL;
+  NEXTHOP_WALK(nh, nhad)
+  {
+    if (prev && (nexthop_compare_node(prev, nh) >= 0))
       return 0;
 
-  return 1;
-}
-
-static inline slab *
-nexthop_slab(struct nexthop *nh)
-{
-  return nexthop_slab_[MIN(nh->labels, 3)];
-}
-
-static struct nexthop *
-nexthop_copy(struct nexthop *o)
-{
-  struct nexthop *first = NULL;
-  struct nexthop **last = &first;
-
-  for (; o; o = o->next)
-    {
-      struct nexthop *n = sl_allocz(nexthop_slab(o));
-      n->gw = o->gw;
-      n->iface = o->iface;
-      n->next = NULL;
-      n->flags = o->flags;
-      n->weight = o->weight;
-      n->labels = o->labels;
-      for (int i=0; i<o->labels; i++)
-	n->label[i] = o->label[i];
-
-      *last = n;
-      last = &(n->next);
-    }
-
-  return first;
-}
-
-static void
-nexthop_free(struct nexthop *o)
-{
-  struct nexthop *n;
+    prev = nh;
+  }
 
-  while (o)
-    {
-      n = o->next;
-      sl_free(o);
-      o = n;
-    }
+  return 1;
 }
 
-
 /*
  *	Extended Attributes
  */
@@ -1122,6 +1057,23 @@ ea_show(struct cli *c, const eattr *e)
   cli_printf(c, -1012, "\t%s", buf);
 }
 
+static void
+nexthop_dump(const struct adata *ad)
+{
+  struct nexthop_adata *nhad = (struct nexthop_adata *) ad;
+
+  debug(":");
+
+  NEXTHOP_WALK(nh, nhad)
+    {
+      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 : "???");
+    }
+}
+
 /**
  * ea_dump - dump an extended attribute
  * @e: attribute to be dumped
@@ -1157,6 +1109,8 @@ ea_dump(ea_list *e)
 	    debug("o");
 	  if (a->type & EAF_EMBEDDED)
 	    debug(":%08x", a->u.data);
+	  else if (a->id == ea_gen_nexthop.id)
+	    nexthop_dump(a->u.ptr);
 	  else
 	    {
 	      int j, len = a->u.ptr->length;
@@ -1258,7 +1212,7 @@ rta_hash(rta *a)
   BMIX(dest);
 #undef MIX
 
-  return mem_hash_value(&h) ^ nexthop_hash(&(a->nh)) ^ ea_hash(a->eattrs);
+  return mem_hash_value(&h) ^ ea_hash(a->eattrs);
 }
 
 static inline int
@@ -1266,24 +1220,16 @@ rta_same(rta *x, rta *y)
 {
   return (x->dest == y->dest &&
 	  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(o));
+  rta *r = sl_alloc(rta_slab);
 
   memcpy(r, o, rta_size(o));
   r->uc = 1;
-  r->nh.next = nexthop_copy(o->nh.next);
   if (!r->eattrs)
     return r;
 
@@ -1375,8 +1321,6 @@ rta__free(rta *a)
   if (a->next)
     a->next->pprev = a->pprev;
   rt_unlock_hostentry(a->hostentry);
-  if (a->nh.next)
-    nexthop_free(a->nh.next);
   ea_free(a->eattrs);
   a->cached = 0;
   sl_free(a);
@@ -1387,12 +1331,6 @@ rta_do_cow(rta *o, linpool *lp)
 {
   rta *r = lp_alloc(lp, rta_size(o));
   memcpy(r, o, rta_size(o));
-  for (struct nexthop **nhn = &(r->nh.next), *nho = o->nh.next; nho; nho = nho->next)
-    {
-      *nhn = lp_alloc(lp, nexthop_size(nho));
-      memcpy(*nhn, nho, nexthop_size(nho));
-      nhn = &((*nhn)->next);
-    }
   r->cached = 0;
   r->uc = 0;
   return r;
@@ -1413,15 +1351,6 @@ rta_dump(rta *a)
 	a->uc, rtd[a->dest], a->hash_key);
   if (!a->cached)
     debug(" !CACHED");
-  if (a->dest == RTD_UNICAST)
-    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)
     {
       debug(" EA: ");
@@ -1471,15 +1400,7 @@ rta_init(void)
 {
   rta_pool = rp_new(&root_pool, "Attributes");
 
-  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)*MPLS_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)*MPLS_MAX_LABEL_STACK);
+  rta_slab = sl_new(rta_pool, sizeof(rta));
 
   rta_alloc_hash();
   rte_src_init();
@@ -1489,6 +1410,7 @@ rta_init(void)
   ea_register_init(&ea_gen_igp_metric);
   ea_register_init(&ea_gen_from);
   ea_register_init(&ea_gen_source);
+  ea_register_init(&ea_gen_nexthop);
 
   ea_register_init(&ea_mpls_labels);
 }
diff --git a/nest/rt-dev.c b/nest/rt-dev.c
index af6506f6..9953e270 100644
--- a/nest/rt-dev.c
+++ b/nest/rt-dev.c
@@ -84,11 +84,16 @@ dev_ifa_notify(struct proto *P, uint flags, struct ifa *ad)
 
       rta a0 = {
 	.dest = RTD_UNICAST,
-	.nh.iface = ad->iface,
+      };
+
+      struct nexthop_adata nhad = {
+	.nh = { .iface = ad->iface, },
+	.ad = { .length = (void *) NEXTHOP_NEXT(&nhad.nh) - (void *) nhad.ad.data, },
       };
 
       ea_set_attr_u32(&a0.eattrs, &ea_gen_preference, 0, c->preference);
       ea_set_attr_u32(&a0.eattrs, &ea_gen_source, 0, RTS_DEVICE);
+      ea_set_attr_data(&a0.eattrs, &ea_gen_nexthop, 0, nhad.ad.data, nhad.ad.length);
 
       a = rta_lookup(&a0);
       e = rte_get_temp(a, src);
diff --git a/nest/rt-show.c b/nest/rt-show.c
index be4c0186..32f7aa2d 100644
--- a/nest/rt-show.c
+++ b/nest/rt-show.c
@@ -45,11 +45,12 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, int primary
   rta *a = e->attrs;
   int sync_error = d->kernel ? krt_get_sync_error(d->kernel, e) : 0;
   void (*get_route_info)(struct rte *, byte *buf);
-  struct nexthop *nh;
+  eattr *nhea = ea_find(a->eattrs, &ea_gen_nexthop);
+  struct nexthop_adata *nhad = nhea ? (struct nexthop_adata *) nhea->u.ptr : NULL;
 
   tm_format_time(tm, &config->tf_route, e->lastmod);
   ip_addr a_from = ea_get_ip(a->eattrs, &ea_gen_from, IPA_NONE);
-  if (ipa_nonzero(a_from) && !ipa_equal(a_from, a->nh.gw))
+  if (ipa_nonzero(a_from) && (!nhad || !ipa_equal(a_from, nhad->nh.gw)))
     bsprintf(from, " from %I", a_from);
   else
     from[0] = 0;
@@ -71,7 +72,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, int primary
 	     e->src->proto->name, tm, from, primary ? (sync_error ? " !" : " *") : "", info);
 
   if (a->dest == RTD_UNICAST)
-    for (nh = &(a->nh); nh; nh = nh->next)
+    NEXTHOP_WALK(nh, nhad)
     {
       char mpls[MPLS_MAX_LABEL_STACK*12 + 5], *lsp = mpls;
       char *onlink = (nh->flags & RNF_ONLINK) ? " onlink" : "";
@@ -85,7 +86,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, int primary
 	}
       *lsp = '\0';
 
-      if (a->nh.next)
+      if (!NEXTHOP_ONE(nhad))
 	bsprintf(weight, " weight %d", nh->weight + 1);
 
       if (ipa_nonzero(nh->gw))
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 37f17bbc..6f948ada 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -940,18 +940,11 @@ rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_chang
     rte_free(new_free);
 }
 
-
-static struct nexthop *
-nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max)
-{
-  return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool);
-}
-
 rte *
 rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent)
 {
   // struct proto *p = c->proto;
-  struct nexthop *nhs = NULL;
+  struct nexthop_adata *nhs = NULL;
   rte *best0, *best, *rt0, *rt, *tmp;
 
   best0 = net->routes;
@@ -976,21 +969,31 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int
       continue;
 
     if (rte_is_reachable(rt))
-      nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit);
+    {
+      eattr *nhea = ea_find(rt->attrs->eattrs, &ea_gen_nexthop);
+      ASSERT_DIE(nhea);
+
+      if (nhs)
+	nhs = nexthop_merge(nhs, (struct nexthop_adata *) nhea->u.ptr, c->merge_limit, pool);
+      else
+	nhs = (struct nexthop_adata *) nhea->u.ptr;
+    }
 
     if (tmp)
       rte_free(tmp);
   }
 
+
   if (nhs)
   {
-    nhs = nexthop_merge_rta(nhs, best->attrs, pool, c->merge_limit);
+    eattr *nhea = ea_find(best->attrs->eattrs, &ea_gen_nexthop);
+    ASSERT_DIE(nhea);
 
-    if (nhs->next)
-    {
-      best = rte_cow_rta(best, pool);
-      nexthop_link(best->attrs, nhs);
-    }
+    nhs = nexthop_merge(nhs, (struct nexthop_adata *) nhea->u.ptr, c->merge_limit, pool);
+
+    best = rte_cow_rta(best, pool);
+    ea_set_attr(&best->attrs->eattrs,
+	EA_LITERAL_DIRECT_ADATA(&ea_gen_nexthop, 0, &nhs->ad));
   }
 
   if (best != best0)
@@ -1184,7 +1187,16 @@ rte_validate(rte *e)
     return 0;
   }
 
-  if ((e->attrs->dest == RTD_UNICAST) && !nexthop_is_sorted(&(e->attrs->nh)))
+  eattr *nhea = ea_find(e->attrs->eattrs, &ea_gen_nexthop);
+  if ((!nhea) != (e->attrs->dest != RTD_UNICAST))
+  {
+    log(L_WARN "Ignoring route %N with destination %d and %snexthop received via %s",
+	n->n.addr, e->attrs->dest, (nhea ? "" : "no "), e->sender->proto->name);
+    return 0;
+  }
+
+  if ((e->attrs->dest == RTD_UNICAST) &&
+      !nexthop_is_sorted((struct nexthop_adata *) nhea->u.ptr))
   {
     log(L_WARN "Ignoring unsorted multipath route %N received via %s",
 	n->n.addr, e->sender->proto->name);
@@ -2395,8 +2407,7 @@ rta_apply_hostentry(rta *a, struct hostentry *he)
   if (a->dest != RTD_UNICAST)
   {
     /* No nexthop */
-no_nexthop:
-    a->nh = (struct nexthop) {};
+    ea_unset_attr(&a->eattrs, 0, &ea_gen_nexthop);
     return;
   }
 
@@ -2404,74 +2415,71 @@ no_nexthop:
 
   if (!mls_ea && he->nexthop_linkable)
   { /* Just link the nexthop chain, no label append happens. */
-    memcpy(&(a->nh), &(he->src->nh), nexthop_size(&(he->src->nh)));
+    ea_copy_attr(&a->eattrs, he->src->eattrs, &ea_gen_nexthop);
     return;
   }
 
-  struct nexthop *nhp = NULL, *nhr = NULL;
-  int skip_nexthop = 0;
-
   const struct adata *mls = mls_ea ? mls_ea->u.ptr : NULL;
   uint mls_cnt = mls ? mls->length / sizeof(u32) : 0;
 
-  for (struct nexthop *nh = &(he->src->nh); nh; nh = nh->next)
+  eattr *he_nh_ea = ea_find(he->src->eattrs, &ea_gen_nexthop);
+  struct nexthop_adata *nhad = (struct nexthop_adata *) he_nh_ea->u.ptr;
+
+  uint total_size = OFFSETOF(struct nexthop_adata, nh);
+
+  NEXTHOP_WALK(nh, nhad)
   {
-    if (skip_nexthop)
-      skip_nexthop--;
-    else
+    if (nh->labels + mls_cnt > MPLS_MAX_LABEL_STACK)
     {
-      nhr = nhp;
-      nhp = (nhp ? (nhp->next = lp_alloc(rte_update_pool, NEXTHOP_MAX_SIZE)) : &(a->nh));
+      log(L_WARN "Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)",
+	    nh->labels, mls_cnt, nh->labels + mls_cnt, MPLS_MAX_LABEL_STACK);
+      continue;
     }
 
-    memset(nhp, 0, NEXTHOP_MAX_SIZE);
-    nhp->iface = nh->iface;
-    nhp->weight = nh->weight;
+    total_size += NEXTHOP_SIZE_CNT(nh->labels + mls_cnt);
+  }
 
-    if (mls)
-    {
-      nhp->labels = nh->labels + mls_cnt;
-      if (nhp->labels <= MPLS_MAX_LABEL_STACK)
-      {
-	memcpy(nhp->label, nh->label, nh->labels * sizeof(u32)); /* First the hostentry labels */
-	memcpy(&(nhp->label[nh->labels]), mls->data, mls->length); /* Then the bottom labels */
-      }
-      else
-      {
-	log(L_WARN "Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)",
-	    nh->labels, mls_cnt, nhp->labels, MPLS_MAX_LABEL_STACK);
-	skip_nexthop++;
-	continue;
-      }
-    }
-    else if (nh->labels)
+  if (total_size == OFFSETOF(struct nexthop_adata, nh))
+  {
+    a->dest = RTD_UNREACHABLE;
+    log(L_WARN "No valid nexthop remaining, setting route unreachable");
+
+    ea_unset_attr(&a->eattrs, 0, &ea_gen_nexthop);
+    return;
+  }
+
+  struct nexthop_adata *new = (struct nexthop_adata *) tmp_alloc_adata(total_size);
+  struct nexthop *dest = &new->nh;
+
+  NEXTHOP_WALK(nh, nhad)
+  {
+    if (nh->labels + mls_cnt > MPLS_MAX_LABEL_STACK)
+      continue;
+
+    memcpy(dest, nh, NEXTHOP_SIZE(nh));
+    if (mls_cnt)
     {
-      nhp->labels = nh->labels;
-      memcpy(nhp->label, nh->label, nh->labels * sizeof(u32));
+      memcpy(&(dest->label[dest->labels]), mls->data, mls->length);
+      dest->labels += mls_cnt;
     }
 
     if (ipa_nonzero(nh->gw))
-    {
-      nhp->gw = nh->gw;			/* Router nexthop */
-      nhp->flags |= (nh->flags & RNF_ONLINK);
-    }
+      /* Router nexthop */
+      dest->flags = (dest->flags & RNF_ONLINK);
     else if (!(nh->iface->flags & IF_MULTIACCESS) || (nh->iface->flags & IF_LOOPBACK))
-      nhp->gw = IPA_NONE;		/* PtP link - no need for nexthop */
+      dest->gw = IPA_NONE;		/* PtP link - no need for nexthop */
     else if (ipa_nonzero(he->link))
-      nhp->gw = he->link;		/* Device nexthop with link-local address known */
+      dest->gw = he->link;		/* Device nexthop with link-local address known */
     else
-      nhp->gw = he->addr;		/* Device nexthop with link-local address unknown */
+      dest->gw = he->addr;		/* Device nexthop with link-local address unknown */
+
+    dest = NEXTHOP_NEXT(dest);
   }
 
-  if (skip_nexthop)
-    if (nhr)
-      nhr->next = NULL;
-    else
-    {
-      a->dest = RTD_UNREACHABLE;
-      log(L_WARN "No valid nexthop remaining, setting route unreachable");
-      goto no_nexthop;
-    }
+  /* Fix final length */
+  new->ad.length = (void *) dest - (void *) new->ad.data;
+  ea_set_attr(&a->eattrs, EA_LITERAL_DIRECT_ADATA(
+	&ea_gen_nexthop, 0, &new->ad));
 }
 
 static inline int
@@ -2485,9 +2493,14 @@ rta_next_hop_outdated(rta *a)
   if (!he->src)
     return a->dest != RTD_UNREACHABLE;
 
+  eattr *he_nh_ea = ea_find(he->src->eattrs, &ea_gen_nexthop);
+  eattr *a_nh_ea = ea_find(a->eattrs, &ea_gen_nexthop);
+
   return (a->dest != he->dest) ||
     (ea_get_int(a->eattrs, &ea_gen_igp_metric, IGP_METRIC_UNKNOWN) != he->igp_metric) ||
-    (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh));
+    (!he->nexthop_linkable) ||
+    (!he_nh_ea != !a_nh_ea) ||
+    (he_nh_ea && a_nh_ea && !adata_same(he_nh_ea->u.ptr, a_nh_ea->u.ptr));
 }
 
 static inline rte *
@@ -3507,7 +3520,14 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
 
       if (a->dest == RTD_UNICAST)
 	{
-	  for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
+	  eattr *ea = ea_find(a->eattrs, &ea_gen_nexthop);
+	  if (!ea)
+	    {
+	      log(L_WARN "No nexthop in unicast route");
+	      goto done;
+	    }
+	    
+	  NEXTHOP_WALK(nh, (struct nexthop_adata *) ea->u.ptr)
 	    if (ipa_zero(nh->gw))
 	      {
 		if (if_local_addr(he->addr, nh->iface))