bgpd: Adds equal-paths check to path comparison. Paths that are

equal to the best path are accumulated onto an ordered list (mp_list)
if maximum-paths is configured. A future commit will add the
multipath markup to the BGP rib table based on the mp_list. Add
unit test for the added mp_list functions.

Deterministic MED is not supported in this commit, it will be
added later.

* bgpd/bgp_aspath.c
  * Make aspath_cmp() an external symbol so it can be used in
    equivalent paths check
* bgpd/bgp_aspath.h
  * Add extern declaration of aspath_cmp()
* bgpd/bgp_mpath.c
  * bgp_info_nexthop_cmp(): Compares nexthops of two paths
  * bgp_info_mpath_cmp(): Compare function to order multipaths by
    nexthop and then by peer address
  * bgp_mp_list_init(): Initialize a list with the multipath order function
  * bgp_mp_list_clear(): Clear out the mp_list
  * bgp_mp_list_add(): Add a multipath to mp_list
* bgpd/bgp_mpath.h
  * External declarations for above added functions in bgp_mpath.c
* bgpd/bgp_route.c
  * bgp_info_cmp(): Add equivalent paths result (paths_eq). If eBGP
    paths are equal down to IGP metric check, flag as equal if peer AS
    matches. Similarly for iBGP paths but compare full AS_PATH.
  * bgp_best_selection(): If multipath is enabled, accumulate equivalent paths
    in mp_list. Add debug bgp event output to see result (will be filtered
    later to display only when change occurs)
  * bgp_process_rsclient(): Pass multipath config to bgp_best_selection()
  * bgp_process_main(): Pass multipath config to bgp_best_selection()
* tests/bgp_mpath_test.c
  * Add unit test case for bgp_mp_list functions

6 files changed, 309 insertions, 23 deletions

diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index cf9304270..de0d6876c 100644
--- a/bgpd/bgp_aspath.c
+++ b/bgpd/bgp_aspath.c
@@ -1821,7 +1821,7 @@ aspath_key_make (void *p)
 }
 
 /* If two aspath have same value then return 1 else return 0 */
-static int
+int
 aspath_cmp (const void *arg1, const void *arg2)
 {
   const struct assegment *seg1 = ((const struct aspath *)arg1)->segments;
diff --git a/bgpd/bgp_aspath.h b/bgpd/bgp_aspath.h
index d63b914c1..b881b6544 100644
--- a/bgpd/bgp_aspath.h
+++ b/bgpd/bgp_aspath.h
@@ -72,6 +72,7 @@ extern struct aspath *aspath_prepend (struct aspath *, struct aspath *);
 extern struct aspath *aspath_filter_exclude (struct aspath *, struct aspath *);
 extern struct aspath *aspath_add_seq (struct aspath *, as_t);
 extern struct aspath *aspath_add_confed_seq (struct aspath *, as_t);
+extern int aspath_cmp (const void *, const void *);
 extern int aspath_cmp_left (const struct aspath *, const struct aspath *);
 extern int aspath_cmp_left_confed (const struct aspath *, const struct aspath *);
 extern struct aspath *aspath_delete_confed_seq (struct aspath *);
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 56c703f6d..09b469516 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -24,8 +24,14 @@
 #include <zebra.h>
 
 #include "command.h"
+#include "prefix.h"
+#include "linklist.h"
+#include "sockunion.h"
 
 #include "bgpd/bgpd.h"
+#include "bgpd/bgp_table.h"
+#include "bgpd/bgp_route.h"
+#include "bgpd/bgp_attr.h"
 #include "bgpd/bgp_mpath.h"
 
 /*
@@ -81,3 +87,116 @@ bgp_maximum_paths_unset (struct bgp *bgp, afi_t afi, safi_t safi,
 
   return 0;
 }
+
+/*
+ * bgp_info_nexthop_cmp
+ *
+ * Compare the nexthops of two paths. Return value is less than, equal to,
+ * or greater than zero if bi1 is respectively less than, equal to,
+ * or greater than bi2.
+ */
+static int
+bgp_info_nexthop_cmp (struct bgp_info *bi1, struct bgp_info *bi2)
+{
+  struct attr_extra *ae1, *ae2;
+  int compare;
+
+  ae1 = bgp_attr_extra_get (bi1->attr);
+  ae2 = bgp_attr_extra_get (bi2->attr);
+
+  compare = IPV4_ADDR_CMP (&bi1->attr->nexthop, &bi2->attr->nexthop);
+
+  if (!compare && ae1 && ae2 && (ae1->mp_nexthop_len == ae2->mp_nexthop_len))
+    {
+      switch (ae1->mp_nexthop_len)
+        {
+        case 4:
+        case 12:
+          compare = IPV4_ADDR_CMP (&ae1->mp_nexthop_global_in,
+                                   &ae2->mp_nexthop_global_in);
+          break;
+#ifdef HAVE_IPV6
+        case 16:
+          compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_global,
+                                   &ae2->mp_nexthop_global);
+          break;
+        case 32:
+          compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_global,
+                                   &ae2->mp_nexthop_global);
+          if (!compare)
+            compare = IPV6_ADDR_CMP (&ae1->mp_nexthop_local,
+                                     &ae2->mp_nexthop_local);
+          break;
+#endif /* HAVE_IPV6 */
+        }
+    }
+
+  return compare;
+}
+
+/*
+ * bgp_info_mpath_cmp
+ *
+ * This function determines our multipath list ordering. By ordering
+ * the list we can deterministically select which paths are included
+ * in the multipath set. The ordering also helps in detecting changes
+ * in the multipath selection so we can detect whether to send an
+ * update to zebra.
+ *
+ * The order of paths is determined first by received nexthop, and then
+ * by peer address if the nexthops are the same.
+ */
+static int
+bgp_info_mpath_cmp (void *val1, void *val2)
+{
+  struct bgp_info *bi1, *bi2;
+  int compare;
+
+  bi1 = val1;
+  bi2 = val2;
+
+  compare = bgp_info_nexthop_cmp (bi1, bi2);
+
+  if (!compare)
+    compare = sockunion_cmp (bi1->peer->su_remote, bi2->peer->su_remote);
+
+  return compare;
+}
+
+/*
+ * bgp_mp_list_init
+ *
+ * Initialize the mp_list, which holds the list of multipaths
+ * selected by bgp_best_selection
+ */
+void
+bgp_mp_list_init (struct list *mp_list)
+{
+  assert (mp_list);
+  memset (mp_list, 0, sizeof (struct list));
+  mp_list->cmp = bgp_info_mpath_cmp;
+}
+
+/*
+ * bgp_mp_list_clear
+ *
+ * Clears all entries out of the mp_list
+ */
+void
+bgp_mp_list_clear (struct list *mp_list)
+{
+  assert (mp_list);
+  list_delete_all_node (mp_list);
+}
+
+/*
+ * bgp_mp_list_add
+ *
+ * Adds a multipath entry to the mp_list
+ */
+void
+bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo)
+{
+  assert (mp_list && mpinfo);
+  listnode_add_sort (mp_list, mpinfo);
+}
diff --git a/bgpd/bgp_mpath.h b/bgpd/bgp_mpath.h
index f0ac83679..de6461fda 100644
--- a/bgpd/bgp_mpath.h
+++ b/bgpd/bgp_mpath.h
@@ -31,4 +31,11 @@
 extern int bgp_maximum_paths_set (struct bgp *, afi_t, safi_t, int, u_int16_t);
 extern int bgp_maximum_paths_unset (struct bgp *, afi_t, safi_t, int);
 
+/* Functions used by bgp_best_selection to record current
+ * multipath selections
+ */
+extern void bgp_mp_list_init (struct list *);
+extern void bgp_mp_list_clear (struct list *);
+extern void bgp_mp_list_add (struct list *, struct bgp_info *);
+
 #endif /* _QUAGGA_BGP_MPATH_H */
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 5c516f024..718e25fff 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -54,6 +54,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 #include "bgpd/bgp_advertise.h"
 #include "bgpd/bgp_zebra.h"
 #include "bgpd/bgp_vty.h"
+#include "bgpd/bgp_mpath.h"
 
 /* Extern from bgp_dump.c */
 extern const char *bgp_origin_str[];
@@ -316,7 +317,8 @@ bgp_med_value (struct attr *attr, struct bgp *bgp)
 
 /* Compare two bgp route entity.  br is preferable then return 1. */
 static int
-bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist)
+bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist,
+	      int *paths_eq)
 {
   u_int32_t new_pref;
   u_int32_t exist_pref;
@@ -331,6 +333,9 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist)
   int internal_as_route = 0;
   int confed_as_route = 0;
   int ret;
+  uint32_t newm, existm;
+
+  *paths_eq = 0;
 
   /* 0. Null check. */
   if (new == NULL)
@@ -454,18 +459,32 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist)
     return 0;
 
   /* 8. IGP metric check. */
-  if (new->extra || exist->extra)
-    {
-      uint32_t newm = (new->extra ? new->extra->igpmetric : 0);
-      uint32_t existm = (exist->extra ? exist->extra->igpmetric : 0);
-      
-      if (newm < existm)
-        return 1;
-      if (newm > existm)
-        return 0;
-    }
+  newm = (new->extra ? new->extra->igpmetric : 0);
+  existm = (exist->extra ? exist->extra->igpmetric : 0);
+  if (newm < existm)
+    ret = 1;
+  if (newm > existm)
+    ret = 0;
 
   /* 9. Maximum path check. */
+  if (newm == existm)
+    {
+      if ((peer_sort (new->peer) == BGP_PEER_IBGP))
+	{
+	  if (aspath_cmp (new->attr->aspath, exist->attr->aspath))
+	    *paths_eq = 1;
+	}
+      else if (new->peer->as == exist->peer->as)
+	*paths_eq = 1;
+    }
+  else
+    {
+      /*
+       * TODO: If unequal cost ibgp multipath is enabled we can
+       * mark the paths as equal here instead of returning
+       */
+      return ret;
+    }
 
   /* 10. If both paths are external, prefer the path that was received
      first (the oldest one).  This step minimizes route-flap, since a
@@ -1267,7 +1286,9 @@ struct bgp_info_pair
 };
 
 static void
-bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair *result)
+bgp_best_selection (struct bgp *bgp, struct bgp_node *rn,
+		    struct bgp_maxpaths_cfg *mpath_cfg,
+		    struct bgp_info_pair *result)
 {
   struct bgp_info *new_select;
   struct bgp_info *old_select;
@@ -1275,7 +1296,13 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair *
   struct bgp_info *ri1;
   struct bgp_info *ri2;
   struct bgp_info *nextri = NULL;
-  
+  int paths_eq, do_mpath;
+  struct list mp_list;
+
+  bgp_mp_list_init (&mp_list);
+  do_mpath = (mpath_cfg->maxpaths_ebgp != BGP_DEFAULT_MAXPATHS ||
+	      mpath_cfg->maxpaths_ibgp != BGP_DEFAULT_MAXPATHS);
+
   /* bgp deterministic-med */
   new_select = NULL;
   if (bgp_flag_check (bgp, BGP_FLAG_DETERMINISTIC_MED))
@@ -1299,7 +1326,7 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair *
 		  || aspath_cmp_left_confed (ri1->attr->aspath,
 					     ri2->attr->aspath))
 		{
-		  if (bgp_info_cmp (bgp, ri2, new_select))
+		  if (bgp_info_cmp (bgp, ri2, new_select, &paths_eq))
 		    {
 		      bgp_info_unset_flag (rn, new_select, BGP_INFO_DMED_SELECTED);
 		      new_select = ri2;
@@ -1341,14 +1368,58 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, struct bgp_info_pair *
       bgp_info_unset_flag (rn, ri, BGP_INFO_DMED_CHECK);
       bgp_info_unset_flag (rn, ri, BGP_INFO_DMED_SELECTED);
 
-      if (bgp_info_cmp (bgp, ri, new_select))
-	new_select = ri;
+      if (bgp_info_cmp (bgp, ri, new_select, &paths_eq))
+	{
+	  new_select = ri;
+
+	  if (do_mpath && !paths_eq)
+	    {
+	      bgp_mp_list_clear (&mp_list);
+	      bgp_mp_list_add (&mp_list, ri);
+	    }
+	}
+
+      if (do_mpath && paths_eq)
+	bgp_mp_list_add (&mp_list, ri);
     }
     
-    result->old = old_select;
-    result->new = new_select;
 
-    return;
+  /*
+   * TODO: Will add some additional filtering later to only
+   * output debugs when multipath state for the route changes
+   */
+  if (BGP_DEBUG (events, EVENTS) && do_mpath)
+    {
+      struct listnode *mp_node;
+      struct bgp_info *mp_info;
+      char buf[2][INET_ADDRSTRLEN];
+
+      prefix2str (&rn->p, buf[0], sizeof (buf[0]));
+      zlog_debug ("%s bestpath nexthop %s, %d mpath candidates",
+		  buf[0],
+		  (new_select ?
+		   inet_ntop(AF_INET, &new_select->attr->nexthop,
+			     buf[1], sizeof (buf[1])) :
+		   "None"),
+		  listcount (&mp_list));
+      for (mp_node = listhead (&mp_list); mp_node;
+	   mp_node = listnextnode (mp_node))
+	{
+	  mp_info = listgetdata (mp_node);
+	  if (mp_info == new_select)
+	    continue;
+	  zlog_debug (" candidate mpath nexthop %s",
+		      inet_ntop(AF_INET, &mp_info->attr->nexthop, buf[0],
+				sizeof (buf[0])));
+	}
+    }
+
+  bgp_mp_list_clear (&mp_list);
+
+  result->old = old_select;
+  result->new = new_select;
+
+  return;
 }
 
 static int
@@ -1422,7 +1493,7 @@ bgp_process_rsclient (struct work_queue *wq, void *data)
   struct peer *rsclient = rn->table->owner;
   
   /* Best path selection. */
-  bgp_best_selection (bgp, rn, &old_and_new);
+  bgp_best_selection (bgp, rn, &bgp->maxpaths[afi][safi], &old_and_new);
   new_select = old_and_new.new;
   old_select = old_and_new.old;
 
@@ -1483,7 +1554,7 @@ bgp_process_main (struct work_queue *wq, void *data)
   struct peer *peer;
   
   /* Best path selection. */
-  bgp_best_selection (bgp, rn, &old_and_new);
+  bgp_best_selection (bgp, rn, &bgp->maxpaths[afi][safi], &old_and_new);
   old_select = old_and_new.old;
   new_select = old_and_new.new;
 
diff --git a/tests/bgp_mpath_test.c b/tests/bgp_mpath_test.c
index 37e977369..4d51ddb88 100644
--- a/tests/bgp_mpath_test.c
+++ b/tests/bgp_mpath_test.c
@@ -31,9 +31,10 @@
 #include "zclient.h"
 
 #include "bgpd/bgpd.h"
-#include "bgpd/bgp_mpath.h"
 #include "bgpd/bgp_table.h"
 #include "bgpd/bgp_route.h"
+#include "bgpd/bgp_attr.h"
+#include "bgpd/bgp_mpath.h"
 
 #define VT100_RESET "\x1b[0m"
 #define VT100_RED "\x1b[31m"
@@ -191,10 +192,97 @@ testcase_t test_bgp_cfg_maximum_paths = {
 };
 
 /*=========================================================
+ * Testcase for bgp_mp_list
+ */
+struct peer test_mp_list_peer[5];
+int test_mp_list_peer_count = sizeof (test_mp_list_peer)/ sizeof (struct peer);
+struct attr test_mp_list_attr[4];
+struct bgp_info test_mp_list_info[] = {
+  { .peer = &test_mp_list_peer[0], .attr = &test_mp_list_attr[0] },
+  { .peer = &test_mp_list_peer[1], .attr = &test_mp_list_attr[1] },
+  { .peer = &test_mp_list_peer[2], .attr = &test_mp_list_attr[1] },
+  { .peer = &test_mp_list_peer[3], .attr = &test_mp_list_attr[2] },
+  { .peer = &test_mp_list_peer[4], .attr = &test_mp_list_attr[3] },
+};
+int test_mp_list_info_count =
+  sizeof (test_mp_list_info)/sizeof (struct bgp_info);
+
+static int
+setup_bgp_mp_list (testcase_t *t)
+{
+  test_mp_list_attr[0].nexthop.s_addr = 0x01010101;
+  test_mp_list_attr[1].nexthop.s_addr = 0x02020202;
+  test_mp_list_attr[2].nexthop.s_addr = 0x03030303;
+  test_mp_list_attr[3].nexthop.s_addr = 0x04040404;
+
+  if ((test_mp_list_peer[0].su_remote = sockunion_str2su ("1.1.1.1")) == NULL)
+    return -1;
+  if ((test_mp_list_peer[1].su_remote = sockunion_str2su ("2.2.2.2")) == NULL)
+    return -1;
+  if ((test_mp_list_peer[2].su_remote = sockunion_str2su ("3.3.3.3")) == NULL)
+    return -1;
+  if ((test_mp_list_peer[3].su_remote = sockunion_str2su ("4.4.4.4")) == NULL)
+    return -1;
+  if ((test_mp_list_peer[4].su_remote = sockunion_str2su ("5.5.5.5")) == NULL)
+    return -1;
+
+  return 0;
+}
+
+static int
+run_bgp_mp_list (testcase_t *t)
+{
+  struct list mp_list;
+  struct listnode *mp_node;
+  struct bgp_info *info;
+  int i;
+  int test_result = TEST_PASSED;
+  bgp_mp_list_init (&mp_list);
+  EXPECT_TRUE (listcount(&mp_list) == 0, test_result);
+
+  bgp_mp_list_add (&mp_list, &test_mp_list_info[1]);
+  bgp_mp_list_add (&mp_list, &test_mp_list_info[4]);
+  bgp_mp_list_add (&mp_list, &test_mp_list_info[2]);
+  bgp_mp_list_add (&mp_list, &test_mp_list_info[3]);
+  bgp_mp_list_add (&mp_list, &test_mp_list_info[0]);
+
+  for (i = 0, mp_node = listhead(&mp_list); i < test_mp_list_info_count;
+       i++, mp_node = listnextnode(mp_node))
+    {
+      info = listgetdata(mp_node);
+      EXPECT_TRUE (info == &test_mp_list_info[i], test_result);
+    }
+
+  bgp_mp_list_clear (&mp_list);
+  EXPECT_TRUE (listcount(&mp_list) == 0, test_result);
+
+  return test_result;
+}
+
+static int
+cleanup_bgp_mp_list (testcase_t *t)
+{
+  int i;
+
+  for (i = 0; i < test_mp_list_peer_count; i++)
+    sockunion_free (test_mp_list_peer[i].su_remote);
+
+  return 0;
+}
+
+testcase_t test_bgp_mp_list = {
+  .desc = "Test bgp_mp_list",
+  .setup = setup_bgp_mp_list,
+  .run = run_bgp_mp_list,
+  .cleanup = cleanup_bgp_mp_list,
+};
+
+/*=========================================================
  * Set up testcase vector
  */
 testcase_t *all_tests[] = {
   &test_bgp_cfg_maximum_paths,
+  &test_bgp_mp_list,
 };
 
 int all_tests_count = (sizeof(all_tests)/sizeof(testcase_t *));