From 96450faf3385a6ed9f4dd5c2c58776c4a664a8da Mon Sep 17 00:00:00 2001 From: Josh Bailey Date: Wed, 20 Jul 2011 20:45:12 -0700 Subject: 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 --- bgpd/bgp_aspath.c | 2 +- bgpd/bgp_aspath.h | 1 + bgpd/bgp_mpath.c | 119 +++++++++++++++++++++++++++++++++++++++++++++++++ bgpd/bgp_mpath.h | 7 +++ bgpd/bgp_route.c | 113 +++++++++++++++++++++++++++++++++++++--------- tests/bgp_mpath_test.c | 90 ++++++++++++++++++++++++++++++++++++- 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 #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" @@ -190,11 +191,98 @@ testcase_t test_bgp_cfg_maximum_paths = { .cleanup = cleanup_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 *)); -- cgit v1.2.1