9 files changed, 230 insertions, 153 deletions

diff --git a/proto/babel/babel.c b/proto/babel/babel.c
index be75694f..f3456369 100644
--- a/proto/babel/babel.c
+++ b/proto/babel/babel.c
@@ -643,15 +643,34 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
 
   if (r)
   {
+    struct nexthop_adata nhad = {
+      .nh = {
+	.gw = r->next_hop,
+	.iface = r->neigh->ifa->iface,
+      },
+      .ad = {
+	.length = sizeof nhad - sizeof nhad.ad,
+      },
+    };
+
+    /*
+     * If we cannot find a reachable neighbour, set the entry to be onlink. This
+     * makes it possible to, e.g., assign /32 addresses on a mesh interface and
+     * have routing work.
+     */
+    if (!neigh_find(&p->p, r->next_hop, r->neigh->ifa->iface, 0))
+      nhad.nh.flags = RNF_ONLINK;
+    
     struct {
       ea_list l;
-      eattr a[6];
+      eattr a[7];
     } eattrs = {
       .l.count = ARRAY_SIZE(eattrs.a),
       .a = {
 	EA_LITERAL_EMBEDDED(&ea_gen_preference, 0, c->preference),
 	EA_LITERAL_STORE_ADATA(&ea_gen_from, 0, &r->neigh->addr, sizeof(r->neigh->addr)),
 	EA_LITERAL_EMBEDDED(&ea_gen_source, 0, RTS_BABEL),
+	EA_LITERAL_STORE_ADATA(&ea_gen_nexthop, 0, nhad.ad.data, nhad.ad.length),
 	EA_LITERAL_EMBEDDED(&ea_babel_metric, 0, r->metric),
 	EA_LITERAL_STORE_ADATA(&ea_babel_router_id, 0, &r->router_id, sizeof(r->router_id)),
 	EA_LITERAL_EMBEDDED(&ea_babel_seqno, 0, r->seqno),
@@ -660,19 +679,9 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
 
     rta a0 = {
       .dest = RTD_UNICAST,
-      .nh.gw = r->next_hop,
-      .nh.iface = r->neigh->ifa->iface,
       .eattrs = &eattrs.l,
     };
 
-    /*
-     * If we cannot find a reachable neighbour, set the entry to be onlink. This
-     * makes it possible to, e.g., assign /32 addresses on a mesh interface and
-     * have routing work.
-     */
-    if (!neigh_find(&p->p, r->next_hop, r->neigh->ifa->iface, 0))
-      a0.nh.flags = RNF_ONLINK;
-
     rte e0 = {
       .attrs = &a0,
       .src = p->p.main_source,
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index a692c4dc..9e65670d 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -966,10 +966,19 @@ bgp_apply_next_hop(struct bgp_parse_state *s, rta *a, ip_addr gw, ip_addr ll)
     if (nbr->scope == SCOPE_HOST)
       WITHDRAW(BAD_NEXT_HOP " - address %I is local", nbr->addr);
 
-    a->dest = RTD_UNICAST;
-    a->nh.gw = nbr->addr;
-    a->nh.iface = nbr->iface;
     ea_set_attr_u32(&a->eattrs, &ea_gen_igp_metric, 0, c->cf->cost);
+
+    a->dest = RTD_UNICAST;
+    struct nexthop_adata nhad = {
+      .nh = {
+	.gw = nbr->addr,
+	.iface = nbr->iface,
+      },
+      .ad = {
+	.length = sizeof nhad - sizeof nhad.ad,
+      },
+    };
+    ea_set_attr_data(&a->eattrs, &ea_gen_nexthop, 0, nhad.ad.data, nhad.ad.length);
   }
   else /* GW_RECURSIVE */
   {
@@ -998,7 +1007,7 @@ bgp_apply_mpls_labels(struct bgp_parse_state *s, rta *a)
 
     a->dest = RTD_UNREACHABLE;
     a->hostentry = NULL;
-    a->nh = (struct nexthop) { };
+    ea_unset_attr(&a->eattrs, 0, &ea_gen_nexthop);
     return;
   }
 
@@ -1008,8 +1017,16 @@ bgp_apply_mpls_labels(struct bgp_parse_state *s, rta *a)
 
   if (s->channel->cf->gw_mode == GW_DIRECT)
   {
-    a->nh.labels = lnum;
-    memcpy(a->nh.label, labels, 4*lnum);
+    eattr *e = ea_find(a->eattrs, &ea_gen_nexthop);
+    struct {
+      struct nexthop_adata nhad;
+      u32 labels[MPLS_MAX_LABEL_STACK];
+    } nh;
+    
+    memcpy(&nh.nhad, e->u.ptr, sizeof(struct adata) + e->u.ptr->length);
+    nh.nhad.nh.labels = lnum;
+    memcpy(nh.labels, labels, lnum * sizeof(u32));
+    nh.nhad.ad.length = sizeof nh.nhad + lnum * sizeof(u32);
   }
   else /* GW_RECURSIVE */
     rta_apply_hostentry(a, s->hostentry);
@@ -1076,7 +1093,7 @@ bgp_use_next_hop(struct bgp_export_state *s, eattr *a)
   return p->neigh && (p->neigh->iface == ifa);
 }
 
-static inline int
+static inline struct nexthop *
 bgp_use_gateway(struct bgp_export_state *s)
 {
   struct bgp_proto *p = s->proto;
@@ -1085,22 +1102,35 @@ bgp_use_gateway(struct bgp_export_state *s)
 
   /* Handle next hop self option - also applies to gateway */
   if (c->cf->next_hop_self && bgp_match_src(s, c->cf->next_hop_self))
-    return 0;
+    return NULL;
+
+  /* Unreachable */
+  if (ra->dest != RTD_UNICAST)
+    return NULL;
+
+  eattr *nhea = ea_find(ra->eattrs, &ea_gen_nexthop);
+  if (!nhea)
+    return NULL;
 
   /* We need one valid global gateway */
-  if ((ra->dest != RTD_UNICAST) || ra->nh.next || ipa_zero(ra->nh.gw) || ipa_is_link_local(ra->nh.gw))
-    return 0;
+  struct nexthop_adata *nhad = (struct nexthop_adata *) nhea->u.ptr;
+  if (!NEXTHOP_ONE(nhad) || ipa_zero(nhad->nh.gw) ||
+      ipa_is_link_local(nhad->nh.gw))
+    return NULL;
 
   /* Check for non-matching AF */
-  if ((ipa_is_ip4(ra->nh.gw) != bgp_channel_is_ipv4(c)) && !c->ext_next_hop)
-    return 0;
+  if ((ipa_is_ip4(nhad->nh.gw) != bgp_channel_is_ipv4(c)) && !c->ext_next_hop)
+    return NULL;
 
   /* Use it when exported to internal peers */
   if (p->is_interior)
-    return 1;
+    return &nhad->nh;
 
   /* Use it when forwarded to single-hop BGP peer on on the same iface */
-  return p->neigh && (p->neigh->iface == ra->nh.iface);
+  if (p->neigh && (p->neigh->iface == nhad->nh.iface))
+    return &nhad->nh;
+
+  return NULL;
 }
 
 static void
@@ -1108,17 +1138,17 @@ bgp_update_next_hop_ip(struct bgp_export_state *s, eattr *a, ea_list **to)
 {
   if (!a || !bgp_use_next_hop(s, a))
   {
-    if (bgp_use_gateway(s))
+    struct nexthop *nhloc;
+    if (nhloc = bgp_use_gateway(s))
     {
-      rta *ra = s->route->attrs;
-      ip_addr nh[1] = { ra->nh.gw };
+      ip_addr nh[1] = { nhloc->gw };
       bgp_set_attr_data(to, BA_NEXT_HOP, 0, nh, 16);
 
       if (s->mpls)
       {
 	u32 implicit_null = BGP_MPLS_NULL;
-	u32 *labels = ra->nh.labels ? ra->nh.label : &implicit_null;
-	uint lnum = ra->nh.labels ? ra->nh.labels : 1;
+	u32 *labels = nhloc->labels ? nhloc->label : &implicit_null;
+	uint lnum = nhloc->labels ? nhloc->labels : 1;
 	bgp_set_attr_data(to, BA_MPLS_LABEL_STACK, 0, labels, lnum * 4);
       }
     }
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 23b767bc..0498a3c2 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -28,24 +28,30 @@ nh_is_vlink(struct nexthop *nhs)
 static inline int
 unresolved_vlink(ort *ort)
 {
-  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
+  return ort->n.nhs && nh_is_vlink(&ort->n.nhs->nh);
 }
 
-static inline struct nexthop *
+static inline struct nexthop_adata *
 new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
 {
-  struct nexthop *nh = lp_allocz(p->nhpool, sizeof(struct nexthop));
-  nh->gw = gw;
-  nh->iface = iface;
-  nh->weight = weight;
-  return nh;
+  struct nexthop_adata *nhad = lp_alloc(p->nhpool, sizeof(struct nexthop_adata));
+  *nhad = (struct nexthop_adata) {
+    .ad = { .length = sizeof *nhad - sizeof nhad->ad, },
+    .nh = {
+      .gw = gw,
+      .iface = iface,
+      .weight = weight,
+    },
+  };
+
+  return nhad;
 }
 
 /* Returns true if there are device nexthops in n */
 static inline int
-has_device_nexthops(const struct nexthop *n)
+has_device_nexthops(struct nexthop_adata *nhad)
 {
-  for (; n; n = n->next)
+  NEXTHOP_WALK(n, nhad)
     if (ipa_zero(n->gw))
       return 1;
 
@@ -53,38 +59,22 @@ has_device_nexthops(const struct nexthop *n)
 }
 
 /* Replace device nexthops with nexthops to gw */
-static struct nexthop *
-fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
+static struct nexthop_adata *
+fix_device_nexthops(struct ospf_proto *p, struct nexthop_adata *old, ip_addr gw)
 {
-  struct nexthop *root1 = NULL;
-  struct nexthop *root2 = NULL;
-  struct nexthop **nn1 = &root1;
-  struct nexthop **nn2 = &root2;
-
   if (!p->ecmp)
-    return new_nexthop(p, gw, n->iface, n->weight);
-
-  /* This is a bit tricky. We cannot just copy the list and update n->gw,
-     because the list should stay sorted, so we create two lists, one with new
-     gateways and one with old ones, and then merge them. */
-
-  for (; n; n = n->next)
   {
-    struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
+    struct nexthop_adata *new = (struct nexthop_adata *) lp_store_adata(p->nhpool, old->ad.data, old->ad.length);
+    new->nh.gw = gw;
+    return new;
+  }
 
+  struct nexthop_adata *tmp = (struct nexthop_adata *) tmp_copy_adata(&old->ad);
+  NEXTHOP_WALK(n, tmp)
     if (ipa_zero(n->gw))
-    {
-      *nn1 = nn;
-      nn1 = &(nn->next);
-    }
-    else
-    {
-      *nn2 = nn;
-      nn2 = &(nn->next);
-    }
-  }
+      n->gw = gw;
 
-  return nexthop_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
+  return nexthop_sort(tmp, p->nhpool);
 }
 
 
@@ -169,9 +159,9 @@ orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
     return -1;
   if (!new->nhs)
     return 1;
-  if (nh_is_vlink(new->nhs))
+  if (nh_is_vlink(&new->nhs->nh))
     return -1;
-  if (nh_is_vlink(old->nhs))
+  if (nh_is_vlink(&old->nhs->nh))
     return 1;
 
 
@@ -279,11 +269,7 @@ ort_merge(struct ospf_proto *p, ort *o, const orta *new)
   orta *old = &o->n;
 
   if (old->nhs != new->nhs)
-  {
-    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
-			  p->ecmp, p->nhpool);
-    old->nhs_reuse = 1;
-  }
+    old->nhs = nexthop_merge(old->nhs, new->nhs, p->ecmp, p->nhpool);
 
   if (old->rid < new->rid)
     old->rid = new->rid;
@@ -295,11 +281,7 @@ ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
   orta *old = &o->n;
 
   if (old->nhs != new->nhs)
-  {
-    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
-			  p->ecmp, p->nhpool);
-    old->nhs_reuse = 1;
-  }
+    old->nhs = nexthop_merge(old->nhs, new->nhs, p->ecmp, p->nhpool);
 
   if (old->tag != new->tag)
     old->tag = 0;
@@ -1165,7 +1147,7 @@ ospf_check_vlinks(struct ospf_proto *p)
 
       if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
       {
-	struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
+	struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->nh.iface);
 
 	if ((ifa->state != OSPF_IS_PTP)
 	    || (ifa->vifa != nhi)
@@ -1579,10 +1561,7 @@ ospf_ext_spf(struct ospf_proto *p)
 
       /* Replace device nexthops with nexthops to forwarding address from LSA */
       if (has_device_nexthops(nfa.nhs))
-      {
 	nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
-	nfa.nhs_reuse = 1;
-      }
     }
 
     if (rt.ebit)
@@ -1726,10 +1705,10 @@ ospf_rt_spf(struct ospf_proto *p)
 
 
 static inline int
-inherit_nexthops(struct nexthop *pn)
+inherit_nexthops(struct nexthop_adata *pn)
 {
   /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
-  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
+  return pn && (ipa_nonzero(pn->nh.gw) || !pn->nh.iface);
 }
 
 static inline ip_addr
@@ -1744,12 +1723,12 @@ link_lsa_lladdr(struct ospf_proto *p, struct top_hash_entry *en)
   return ospf_is_ip4(p) ? ipa_from_ip4(ospf3_6to4(ll)) : ipa_from_ip6(ll);
 }
 
-static struct nexthop *
+static struct nexthop_adata *
 calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
 	      struct top_hash_entry *par, int pos, uint data, uint lif, uint nif)
 {
   struct ospf_proto *p = oa->po;
-  struct nexthop *pn = par->nhs;
+  struct nexthop_adata *pn = par->nhs;
   struct top_hash_entry *link = NULL;
   struct ospf_iface *ifa = NULL;
   ip_addr nh = IPA_NONE;
@@ -1827,10 +1806,10 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
 	return NULL;
     }
 
-    struct nexthop *nhs = new_nexthop(p, nh, ifa->iface, ifa->ecmp_weight);
+    struct nexthop_adata *nhs = new_nexthop(p, nh, ifa->iface, ifa->ecmp_weight);
 
     if (ifa->addr->flags & IA_HOST)
-      nhs->flags = RNF_ONLINK;
+      nhs->nh.flags = RNF_ONLINK;
 
     return nhs;
   }
@@ -1851,7 +1830,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
       if (ipa_zero(en->lb))
 	goto bad;
 
-      return new_nexthop(p, en->lb, pn->iface, pn->weight);
+      return new_nexthop(p, en->lb, pn->nh.iface, pn->nh.weight);
     }
     else /* OSPFv3 */
     {
@@ -1859,7 +1838,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
        * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
        * is computed in link_back().
        */
-      link = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
+      link = ospf_hash_find(p->gr, pn->nh.iface->index, en->lb_id, rid, LSA_T_LINK);
       if (!link)
 	return NULL;
 
@@ -1867,7 +1846,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
       if (ipa_zero(nh))
 	return NULL;
 
-      return new_nexthop(p, nh, pn->iface, pn->weight);
+      return new_nexthop(p, nh, pn->nh.iface, pn->nh.weight);
     }
   }
 
@@ -1914,7 +1893,7 @@ add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
   if (!link_back(oa, en, par, lif, nif))
     return;
 
-  struct nexthop *nhs = calc_next_hop(oa, en, par, pos, data, lif, nif);
+  struct nexthop_adata *nhs = calc_next_hop(oa, en, par, pos, data, lif, nif);
   if (!nhs)
   {
     log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
@@ -1923,7 +1902,7 @@ add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
   }
 
   /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
-  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
+  if ((dist == en->dist) && !nh_is_vlink(&en->nhs->nh))
   {
     /*
      * For multipath, we should merge nexthops. We merge regular nexthops only.
@@ -1947,13 +1926,11 @@ add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
      */
 
     /* Keep old ones */
-    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
+    if (!p->ecmp || nh_is_vlink(&nhs->nh) || (nhs == en->nhs))
       return;
 
     /* Merge old and new */
-    int new_reuse = (par->nhs != nhs);
-    en->nhs = nexthop_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
-    en->nhs_reuse = 1;
+    en->nhs = nexthop_merge(en->nhs, nhs, p->ecmp, p->nhpool);
     return;
   }
 
@@ -1967,7 +1944,6 @@ add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
   en->nhs = nhs;
   en->dist = dist;
   en->color = CANDIDATE;
-  en->nhs_reuse = (par->nhs != nhs);
 
   prev = NULL;
 
@@ -2008,10 +1984,23 @@ ort_changed(ort *nf, rta *nr)
   if (!or ||
     (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
     (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
-    (nr->dest != or->dest) ||
-    !nexthop_same(&(nr->nh), &(or->nh)))
+    (nr->dest != or->dest))
     return 1;
 
+  eattr *nhea_n = ea_find(nr->eattrs, &ea_gen_nexthop);
+  eattr *nhea_o = ea_find(or->eattrs, &ea_gen_nexthop);
+  if (!nhea_n != !nhea_o)
+    return 1;
+
+  if (nhea_n && nhea_o)
+  {
+    struct nexthop_adata *nhad_n = (struct nexthop_adata *) nhea_n->u.ptr;
+    struct nexthop_adata *nhad_o = (struct nexthop_adata *) nhea_o->u.ptr;
+
+    if (!nexthop_same(nhad_n, nhad_o))
+      return 1;
+  }
+
   if (	ea_get_int(nr->eattrs, &ea_gen_source, 0)
      != ea_get_int(or->eattrs, &ea_gen_source, 0))
     return 1;
@@ -2038,10 +2027,9 @@ again1:
   FIB_ITERATE_START(fib, &fit, ort, nf)
   {
     /* Sanity check of next-hop addresses, failure should not happen */
-    if (nf->n.type)
+    if (nf->n.type && nf->n.nhs)
     {
-      struct nexthop *nh;
-      for (nh = nf->n.nhs; nh; nh = nh->next)
+      NEXTHOP_WALK(nh, nf->n.nhs)
 	if (ipa_nonzero(nh->gw))
 	{
 	  neighbor *nbr = neigh_find(&p->p, nh->gw, nh->iface,
@@ -2062,9 +2050,24 @@ again1:
     {
       rta a0 = {
 	.dest = RTD_UNICAST,
-	.nh = *(nf->n.nhs),
       };
 
+      struct {
+	ea_list l;
+	eattr a[7];
+      } eattrs;
+
+      eattrs.l = (ea_list) {};
+
+      eattrs.a[eattrs.l.count++] =
+	EA_LITERAL_EMBEDDED(&ea_gen_preference, 0, p->p.main_channel->preference);
+
+      eattrs.a[eattrs.l.count++] = 
+	EA_LITERAL_EMBEDDED(&ea_gen_source, 0, nf->n.type);
+
+      eattrs.a[eattrs.l.count++] =
+	EA_LITERAL_DIRECT_ADATA(&ea_gen_nexthop, 0, &nf->n.nhs->ad);
+
       if (reload || ort_changed(nf, &a0))
       {
 	nf->old_metric1 = nf->n.metric1;
@@ -2072,19 +2075,6 @@ again1:
 	nf->old_tag = nf->n.tag;
 	nf->old_rid = nf->n.rid;
 
-	struct {
-	  ea_list l;
-	  eattr a[6];
-	} eattrs;
-
-	eattrs.l = (ea_list) {};
-
-	eattrs.a[eattrs.l.count++] =
-	  EA_LITERAL_EMBEDDED(&ea_gen_preference, 0, p->p.main_channel->preference);
-
-	eattrs.a[eattrs.l.count++] = 
-	  EA_LITERAL_EMBEDDED(&ea_gen_source, 0, nf->n.type);
-
 	eattrs.a[eattrs.l.count++] =
 	  EA_LITERAL_EMBEDDED(&ea_ospf_metric1, 0, nf->n.metric1);
 
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
index 094e125b..180216b7 100644
--- a/proto/ospf/rt.h
+++ b/proto/ospf/rt.h
@@ -18,8 +18,6 @@
 typedef struct orta
 {
   u8 type;			/* RTS_OSPF_* */
-  u8 nhs_reuse;			/* Whether nhs nodes can be reused during merging.
-				   See a note in rt.c:add_cand() */
   u32 options;
   /*
    * For ORT_ROUTER routes, options field are router-LSA style
@@ -53,7 +51,7 @@ typedef struct orta
   struct ospf_area *oa;
   struct ospf_area *voa;	/* Used when route is replaced in ospf_rt_sum_tr(),
 				   NULL otherwise */
-  struct nexthop *nhs;		/* Next hops computed during SPF */
+  struct nexthop_adata *nhs;	/* Next hops computed during SPF */
   struct top_hash_entry *en;	/* LSA responsible for this orta */
 }
 orta;
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 81207e68..c2b12cfc 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -1366,8 +1366,20 @@ ospf_rt_notify(struct proto *P, struct channel *ch UNUSED, const net_addr *n, rt
   uint tag = ea_get_int(a->eattrs, &ea_ospf_tag, 0);
 
   ip_addr fwd = IPA_NONE;
-  if ((a->dest == RTD_UNICAST) && use_gw_for_fwaddr(p, a->nh.gw, a->nh.iface))
-    fwd = a->nh.gw;
+  if (a->dest == RTD_UNICAST)
+  {
+    eattr *nhea = ea_find(a->eattrs, &ea_gen_nexthop);
+    if (!nhea)
+    {
+      log(L_ERR "%s: Unicast route without nexthop for %N",
+	  p->p.name, n);
+      return;
+    }
+
+    struct nexthop_adata *nhad = (struct nexthop_adata *) nhea->u.ptr;
+    if (use_gw_for_fwaddr(p, nhad->nh.gw, nhad->nh.iface))
+      fwd = nhad->nh.gw;
+  }
 
   /* NSSA-LSA with P-bit set must have non-zero forwarding address */
   if (oa && ipa_zero(fwd))
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index c36d0b50..3c92b431 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -28,7 +28,7 @@ struct top_hash_entry
   u16 next_lsa_opts;		/* For postponed LSA origination */
   btime inst_time;		/* Time of installation into DB */
   struct ort *nf;		/* Reference fibnode for sum and ext LSAs, NULL for otherwise */
-  struct nexthop *nhs;		/* Computed nexthops - valid only in ospf_rt_spf() */
+  struct nexthop_adata *nhs;	/* Computed nexthops - valid only in ospf_rt_spf() */
   ip_addr lb;			/* In OSPFv2, link back address. In OSPFv3, any global address in the area useful for vlinks */
   u32 lb_id;			/* Interface ID of link back iface (for bcast or NBMA networks) */
   u32 dist;			/* Distance from the root */
@@ -39,8 +39,6 @@ struct top_hash_entry
 #define CANDIDATE 1
 #define INSPF 2
   u8 mode;			/* LSA generated during RT calculation (LSA_RTCALC or LSA_STALE)*/
-  u8 nhs_reuse;			/* Whether nhs nodes can be reused during merging.
-				   See a note in rt.c:add_cand() */
 };
 
 
diff --git a/proto/perf/perf.c b/proto/perf/perf.c
index 2cb60e3e..71925bf1 100644
--- a/proto/perf/perf.c
+++ b/proto/perf/perf.c
@@ -144,13 +144,19 @@ perf_loop(void *data)
     if (!p->attrs_per_rte || !(i % p->attrs_per_rte)) {
       struct rta a0 = {
 	.dest = RTD_UNICAST,
+      };
+
+      ea_set_attr_u32(&a0.eattrs, &ea_gen_preference, 0, p->p.main_channel->preference);
+      ea_set_attr_u32(&a0.eattrs, &ea_gen_source, 0, RTS_PERF);
+
+      struct nexthop_adata nhad = {
 	.nh.iface = p->ifa->iface,
 	.nh.gw = gw,
 	.nh.weight = 1,
       };
 
-      ea_set_attr_u32(&a0.eattrs, &ea_gen_preference, 0, p->p.main_channel->preference);
-      ea_set_attr_u32(&a0.eattrs, &ea_gen_source, 0, RTS_PERF);
+      ea_set_attr_data(&a0.eattrs, &ea_gen_nexthop, 0,
+	  &nhad.ad.data, sizeof nhad - sizeof nhad.ad);
 
       p->data[i].a = rta_lookup(&a0);
     }
diff --git a/proto/rip/rip.c b/proto/rip/rip.c
index fbf91b94..5a66a1be 100644
--- a/proto/rip/rip.c
+++ b/proto/rip/rip.c
@@ -169,38 +169,58 @@ rip_announce_rte(struct rip_proto *p, struct rip_entry *en)
     a0.eattrs = &ea_block.l;
 
     u16 rt_tag = rt->tag;
+    struct iface *rt_from = NULL;
 
     if (p->ecmp)
     {
       /* ECMP route */
-      struct nexthop *nhs = NULL;
       int num = 0;
 
       for (rt = en->routes; rt && (num < p->ecmp); rt = rt->next)
+	if (rip_valid_rte(rt))
+	  num++;
+
+      struct nexthop_adata *nhad = (struct nexthop_adata *) tmp_alloc_adata((num+1) * sizeof(struct nexthop));
+      struct nexthop *nh = &nhad->nh;
+
+      for (rt = en->routes; rt && (num < p->ecmp); rt = rt->next)
       {
 	if (!rip_valid_rte(rt))
-	    continue;
+	  continue;
 
-	struct nexthop *nh = allocz(sizeof(struct nexthop));
+	*nh = (struct nexthop) {
+	  .gw = rt->next_hop,
+	  .iface = rt->from->ifa->iface,
+	  .weight = rt->from->ifa->cf->ecmp_weight,
+	};
 
-	nh->gw = rt->next_hop;
-	nh->iface = rt->from->ifa->iface;
-	nh->weight = rt->from->ifa->cf->ecmp_weight;
+	if (!rt_from)
+	  rt_from = rt->from->ifa->iface;
 
-	nexthop_insert(&nhs, nh);
-	num++;
+	nh = NEXTHOP_NEXT(nh);
 
 	if (rt->tag != rt_tag)
 	  rt_tag = 0;
       }
 
-      a0.nh = *nhs;
+      nhad->ad.length = ((void *) nh - (void *) nhad->ad.data);
+
+      ea_set_attr(&a0.eattrs,
+	  EA_LITERAL_DIRECT_ADATA(&ea_gen_nexthop, 0,
+	    &(nexthop_sort(nhad, tmp_linpool)->ad)));
     }
     else
     {
       /* Unipath route */
-      a0.nh.gw = rt->next_hop;
-      a0.nh.iface = rt->from->ifa->iface;
+      rt_from = rt->from->ifa->iface;
+
+      struct nexthop_adata nhad = {
+	.nh.gw = rt->next_hop,
+	.nh.iface = rt->from->ifa->iface,
+      };
+
+      ea_set_attr_data(&a0.eattrs, &ea_gen_nexthop, 0,
+	  &nhad.ad.data, sizeof nhad - sizeof nhad.ad);
       ea_set_attr_data(&a0.eattrs, &ea_gen_from, 0, &rt->from->nbr->addr, sizeof(ip_addr));
     }
 
@@ -208,7 +228,7 @@ rip_announce_rte(struct rip_proto *p, struct rip_entry *en)
 
     struct rip_iface_adata riad = {
       .ad = { .length = sizeof(struct rip_iface_adata) - sizeof(struct adata) },
-      .iface = a0.nh.iface,
+      .iface = rt_from,
     };
     ea_set_attr(&a0.eattrs,
 	EA_LITERAL_DIRECT_ADATA(&ea_rip_from, 0, &riad.ad));
@@ -361,8 +381,14 @@ rip_rt_notify(struct proto *P, struct channel *ch UNUSED, const net_addr *net, s
     en->metric = rt_metric;
     en->tag = rt_tag;
     en->from = (new->src->proto == P) ? rt_from : NULL;
-    en->iface = new->attrs->nh.iface;
-    en->next_hop = new->attrs->nh.gw;
+
+    eattr *nhea = ea_find(new->attrs->eattrs, &ea_gen_nexthop);
+    if (nhea)
+    {
+      struct nexthop_adata *nhad = (struct nexthop_adata *) nhea->u.ptr;
+      en->iface = nhad->nh.iface;
+      en->next_hop = nhad->nh.gw;
+    }
   }
   else
   {
diff --git a/proto/static/static.c b/proto/static/static.c
index dffc4882..8e389390 100644
--- a/proto/static/static.c
+++ b/proto/static/static.c
@@ -61,32 +61,40 @@ static_announce_rte(struct static_proto *p, struct static_route *r)
 
   if (r->dest == RTD_UNICAST)
   {
-    struct static_route *r2;
-    struct nexthop *nhs = NULL;
+    uint sz = 0;
+    for (struct static_route *r2 = r; r2; r2 = r2->mp_next)
+      if (r2->active)
+	sz += NEXTHOP_SIZE_CNT(r2->mls ? r2->mls->length / sizeof(u32) : 0);
 
-    for (r2 = r; r2; r2 = r2->mp_next)
+    if (!sz)
+      goto withdraw;
+
+    struct nexthop_adata *nhad = allocz(sz + sizeof *nhad);
+    struct nexthop *nh = &nhad->nh;
+
+    for (struct static_route *r2 = r; r2; r2 = r2->mp_next)
     {
       if (!r2->active)
 	continue;
 
-      struct nexthop *nh = allocz(NEXTHOP_MAX_SIZE);
-      nh->gw = r2->via;
-      nh->iface = r2->neigh->iface;
-      nh->flags = r2->onlink ? RNF_ONLINK : 0;
-      nh->weight = r2->weight;
+      *nh = (struct nexthop) {
+	.gw = r2->via,
+	.iface = r2->neigh->iface,
+	.flags = r2->onlink ? RNF_ONLINK : 0,
+	.weight = r2->weight,
+      };
+
       if (r2->mls)
       {
 	nh->labels = r2->mls->length / sizeof(u32);
 	memcpy(nh->label, r2->mls->data, r2->mls->length);
       }
 
-      nexthop_insert(&nhs, nh);
+      nh = NEXTHOP_NEXT(nh);
     }
 
-    if (!nhs)
-      goto withdraw;
-
-    nexthop_link(a, nhs);
+    ea_set_attr_data(&a->eattrs, &ea_gen_nexthop, 0,
+	nhad->ad.data, (void *) nh - (void *) nhad->ad.data);
   }
 
   if (r->dest == RTDX_RECURSIVE)