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

1 files changed, 89 insertions, 1 deletions

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 *));