summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bgpd/bgp_aspath.c2
-rw-r--r--bgpd/bgp_aspath.h1
-rw-r--r--bgpd/bgp_mpath.c119
-rw-r--r--bgpd/bgp_mpath.h7
-rw-r--r--bgpd/bgp_route.c113
-rw-r--r--tests/bgp_mpath_test.c90
6 files changed, 309 insertions, 23 deletions
diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index cf930427..de0d6876 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 d63b914c..b881b654 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 56c703f6..09b46951 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 f0ac8367..de6461fd 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 5c516f02..718e25ff 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 37e97736..4d51ddb8 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 *));
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-04 21:02:48 +0000