Moving of mulipath merging code from OSPF to nest

5 files changed, 110 insertions, 94 deletions

diff --git a/nest/route.h b/nest/route.h
index 8f3c7c9a..e22f950b 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -482,6 +482,7 @@ void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **na
 int mpnh__same(struct mpnh *x, struct mpnh *y); /* Compare multipath nexthops */
 static inline int mpnh_same(struct mpnh *x, struct mpnh *y)
 { return (x == y) || mpnh__same(x, y); }
+struct mpnh *mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp);
 
 void rta_init(void);
 rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index 85a192c8..32090b52 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -167,7 +167,7 @@ rt_get_source(struct proto *p, u32 id)
   src->private_id = id;
   src->global_id = rte_src_alloc_id();
   src->uc = 0;
-  
+
   HASH_INSERT2(src_hash, RSH, rta_pool, src);
 
   return src;
@@ -215,6 +215,94 @@ mpnh__same(struct mpnh *x, struct mpnh *y)
   return x == y;
 }
 
+static int
+mpnh_compare_node(struct mpnh *x, struct mpnh *y)
+{
+  int r;
+
+  if (!x)
+    return 1;
+
+  if (!y)
+    return -1;
+
+  r = ((int) y->weight) - ((int) x->weight);
+  if (r)
+    return r;
+
+  r = ipa_compare(x->gw, y->gw);
+  if (r)
+    return r;
+
+  return ((int) x->iface->index) - ((int) y->iface->index);
+}
+
+static inline struct mpnh *
+mpnh_copy_node(const struct mpnh *src, linpool *lp)
+{
+  struct mpnh *n = lp_alloc(lp, sizeof(struct mpnh));
+  n->gw = src->gw;
+  n->iface = src->iface;
+  n->next = NULL;
+  n->weight = src->weight;
+  return n;
+}
+
+/**
+ * mpnh_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
+ *
+ * The mpnh_merge() function takes two nexthop lists @x and @y and merges them,
+ * eliminating possible duplicates. The input lists must be sorted and the
+ * result is sorted too. The number of nexthops in result is limited by @max.
+ * New nodes are allocated from linpool @lp.
+ *
+ * The arguments @rx and @ry specify whether corresponding input lists may be
+ * consumed by the function (i.e. their nodes reused in the resulting list), in
+ * that case the caller should not access these lists after that. To eliminate
+ * issues with deallocation of these lists, the caller should use some form of
+ * bulk deallocation (e.g. stack or linpool) to free these nodes when the
+ * resulting list is no longer needed. When reusability is not set, the
+ * corresponding lists are not modified nor linked from the resulting list.
+ */
+struct mpnh *
+mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp)
+{
+  struct mpnh *root = NULL;
+  struct mpnh **n = &root;
+
+  while ((x || y) && max--)
+  {
+    int cmp = mpnh_compare_node(x, y);
+    if (cmp < 0)
+    {
+      *n = rx ? x : mpnh_copy_node(x, lp);
+      x = x->next;
+    }
+    else if (cmp > 0)
+    {
+      *n = ry ? y : mpnh_copy_node(y, lp);
+      y = y->next;
+    }
+    else
+    {
+      *n = rx ? x : (ry ? y : mpnh_copy_node(x, lp));
+      x = x->next;
+      y = y->next;
+    }
+    n = &((*n)->next);
+  }
+  *n = NULL;
+
+  return root;
+}
+
+
 static struct mpnh *
 mpnh_copy(struct mpnh *o)
 {
@@ -635,7 +723,7 @@ get_generic_attr(eattr *a, byte **buf, int buflen UNUSED)
       *buf += bsprintf(*buf, "igp_metric");
       return GA_NAME;
     }
- 
+
   return GA_UNKNOWN;
 }
 
@@ -741,7 +829,7 @@ ea_show(struct cli *c, eattr *e)
     }
   else if (EA_PROTO(e->id))
     pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
-  else 
+  else
     status = get_generic_attr(e, &pos, end - pos);
 
   if (status < GA_NAME)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index e74bcae6..cdf8012a 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -53,88 +53,6 @@ new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
   return nh;
 }
 
-static inline struct mpnh *
-copy_nexthop(struct ospf_proto *p, const struct mpnh *src)
-{
-  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
-  nh->gw = src->gw;
-  nh->iface = src->iface;
-  nh->next = NULL;
-  nh->weight = src->weight;
-  return nh;
-}
-
-/* Compare nexthops during merge.
-   We need to maintain nhs sorted to eliminate duplicities */
-static int
-cmp_nhs(struct mpnh *s1, struct mpnh *s2)
-{
-  int r;
-
-  if (!s1)
-    return 1;
-
-  if (!s2)
-    return -1;
-
-  r = ((int) s2->weight) - ((int) s1->weight);
-  if (r)
-    return r;
-
-  r = ipa_compare(s1->gw, s2->gw);
-  if (r)
-    return r;
-
-  return ((int) s1->iface->index) - ((int) s2->iface->index);
-}
-
-static struct mpnh *
-merge_nexthops(struct ospf_proto *p, struct mpnh *s1, struct mpnh *s2, int r1, int r2)
-{
-  struct mpnh *root = NULL;
-  struct mpnh **n = &root;
-  int count = p->ecmp;
-
-  ASSERT(p->ecmp);
-
-  /*
-   * r1, r2 signalize whether we can reuse nexthops from s1, s2.
-   * New nexthops (s2, new) can be reused if they are not inherited
-   * from the parent (i.e. it is allocated in calc_next_hop()).
-   * Current nexthops (s1, en->nhs) can be reused if they weren't
-   * inherited in previous steps (that is stored in nhs_reuse,
-   * i.e. created by merging or allocalted in calc_next_hop()).
-   *
-   * Generally, a node first inherits shared nexthops from its
-   * parent and later possibly gets reusable copy during merging.
-   */
-
-  while ((s1 || s2) && count--)
-  {
-    int cmp = cmp_nhs(s1, s2);
-    if (cmp < 0)
-    {
-      *n = r1 ? s1 : copy_nexthop(p, s1);
-      s1 = s1->next;
-    }
-    else if (cmp > 0)
-    {
-      *n = r2 ? s2 : copy_nexthop(p, s2);
-      s2 = s2->next;
-    }
-    else
-    {
-      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(p, s1));
-      s1 = s1->next;
-      s2 = s2->next;
-    }
-    n = &((*n)->next);
-  }
-  *n = NULL;
-
-  return root;
-}
-
 /* Returns true if there are device nexthops in n */
 static inline int
 has_device_nexthops(const struct mpnh *n)
@@ -178,7 +96,7 @@ fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)
     }
   }
 
-  return merge_nexthops(p, root1, root2, 1, 1);
+  return mpnh_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
 }
 
 
@@ -374,7 +292,8 @@ ort_merge(struct ospf_proto *p, ort *o, const orta *new)
 
   if (old->nhs != new->nhs)
   {
-    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
+    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
+			  p->ecmp, p->nhpool);
     old->nhs_reuse = 1;
   }
 
@@ -389,7 +308,8 @@ ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
 
   if (old->nhs != new->nhs)
   {
-    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
+    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
+			  p->ecmp, p->nhpool);
     old->nhs_reuse = 1;
   }
 
@@ -1885,8 +1805,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
     return;
   }
 
-  /* We know that en->color == CANDIDATE and en->nhs is defined. */
-
+  /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
   if ((dist == en->dist) && !nh_is_vlink(en->nhs))
   {
     /*
@@ -1900,7 +1819,14 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
      * allocated in calc_next_hop()).
      *
      * Generally, a node first inherits shared nexthops from its parent and
-     * later possibly gets reusable copy during merging.
+     * later possibly gets reusable (private) copy during merging. This is more
+     * or less same for both top_hash_entry nodes and orta nodes.
+     *
+     * Note that when a child inherits a private nexthop from its parent, it
+     * should make the nexthop shared for both parent and child, while we only
+     * update nhs_reuse for the child node. This makes nhs_reuse field for the
+     * parent technically incorrect, but it is not a problem as parent's nhs
+     * will not be modified (and nhs_reuse examined) afterwards.
      */
 
     /* Keep old ones */
@@ -1909,7 +1835,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
 
     /* Merge old and new */
     int new_reuse = (par->nhs != nhs);
-    en->nhs = merge_nexthops(p, en->nhs, nhs, en->nhs_reuse, new_reuse);
+    en->nhs = mpnh_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
     en->nhs_reuse = 1;
     return;
   }
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
index 61936f3c..30332f3b 100644
--- a/proto/ospf/rt.h
+++ b/proto/ospf/rt.h
@@ -18,7 +18,8 @@
 typedef struct orta
 {
   u8 type;			/* RTS_OSPF_* */
-  u8 nhs_reuse;			/* Whether nhs nodes can be reused during merging */
+  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
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index e2d6c773..5652ced0 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -39,7 +39,7 @@ struct top_hash_entry
 #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:merge_nexthops() */
+				   See a note in rt.c:add_cand() */
 };