From de8d5dff1523bb9fe47d54f31c9e5322bd805b44 Mon Sep 17 00:00:00 2001 From: Josh Bailey Date: Wed, 20 Jul 2011 20:46:01 -0700 Subject: bgpd: Adds support to mark up the BGP rib table entry with multipath information based on the multipath list (mp_list) generated during the best path calculation. Display "multipath" for paths that are multipath and also on bestpath if the route is multipath. Flag a best path with the BGP_INFO_MULTIPATH_CHG if the multipath set has changed since the last update. This can be used to trigger updates to zebra and peers. The multipath markup is a lazily allocated bgp_info_mpath structure that is added to the best path and any multipaths. The mpath structures are linked together with the best path element at the head and the other elements ordered by nexthop and then by peer address. This markup scheme is updated by calling bgp_info_mpath_update() and passing in a new mp_list the the current multipath set. There are additional API's for walking the multipath set, querying the count of multipaths, and for cleaning up the multipath markup information when freeing path information. * bgpd/bgp_mpath.c * bgp_info_mpath_new(): Allocation of new mpath element * bgp_info_mpath_free(): Release memory for mpath element * bgp_info_mpath_get(): Access mpath element of path. Allocate memory on-demand * bgp_info_mpath_enqueue(): Enqueue a path onto the multipath list * bgp_info_mpath_dequeue(): Remove a path from the multipath list * bgp_info_mpath_first(): Return first path on the multipath list * bgp_info_mpath_next(): Return next path on the multipath list * bgp_info_mpath_count(): Return the number of paths on the multipath list * bgp_info_mpath_count_set(): Set the number of paths on the multipath list * bgp_info_mpath_update(): Update multipath markup on bgp route table entry and flag any changes. Emit 'debug bgp event' output on any multipath change. * bgpd/bgp_mpath.h * struct bgp_info_mpath: Information added to a bgp_info path to record multipath information * External declarations for new functions in bgp_mpath.c * bgpd/bgp_route.c * bgp_info_free(): Free mpath memory when freeing path information * bgp_info_reap(): Dequeue path from multipath queue before deleting it * bgp_best_selection(): Calls bgp_info_mpath_update() with latest mp_list to mark-up rib table entry * bgp_vty_out_detail(): Add display of multipath flag for a path. Also display 'multipath' for bestpath if it is a multipath route * bgpd/bgp_route.h * struct bgp_info: Add pointer to bgp_info_mpath information * Add flags to mark a path as multipath (BGP_INFO_MULTIPATH) and to mark bestpath if multipath information has changed (BGP_INFO_MULTIPATH_CHG) * lib/memtypes.c * Add MTYPE_BGP_MPATH_INFO for allocating memory for bgp_info_mpath * tests/bgp_mpath_test.c * Add test case for bgp_info_mpath_update() and supporting functions --- bgpd/bgp_mpath.c | 313 +++++++++++++++++++++++++++++++++++++++++++++++++ bgpd/bgp_mpath.h | 32 +++++ bgpd/bgp_route.c | 37 ++---- bgpd/bgp_route.h | 6 + lib/memtypes.c | 1 + tests/bgp_mpath_test.c | 84 ++++++++++++- 6 files changed, 443 insertions(+), 30 deletions(-) diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c index 09b46951..af1c342c 100644 --- a/bgpd/bgp_mpath.c +++ b/bgpd/bgp_mpath.c @@ -27,11 +27,13 @@ #include "prefix.h" #include "linklist.h" #include "sockunion.h" +#include "memory.h" #include "bgpd/bgpd.h" #include "bgpd/bgp_table.h" #include "bgpd/bgp_route.h" #include "bgpd/bgp_attr.h" +#include "bgpd/bgp_debug.h" #include "bgpd/bgp_mpath.h" /* @@ -200,3 +202,314 @@ bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo) assert (mp_list && mpinfo); listnode_add_sort (mp_list, mpinfo); } + +/* + * bgp_info_mpath_new + * + * Allocate and zero memory for a new bgp_info_mpath element + */ +static struct bgp_info_mpath * +bgp_info_mpath_new (void) +{ + struct bgp_info_mpath *new_mpath; + new_mpath = XCALLOC (MTYPE_BGP_MPATH_INFO, sizeof (struct bgp_info_mpath)); + return new_mpath; +} + +/* + * bgp_info_mpath_free + * + * Release resources for a bgp_info_mpath element and zero out pointer + */ +void +bgp_info_mpath_free (struct bgp_info_mpath **mpath) +{ + if (mpath && *mpath) + { + XFREE (MTYPE_BGP_MPATH_INFO, *mpath); + *mpath = NULL; + } +} + +/* + * bgp_info_mpath_get + * + * Fetch the mpath element for the given bgp_info. Used for + * doing lazy allocation. + */ +static struct bgp_info_mpath * +bgp_info_mpath_get (struct bgp_info *binfo) +{ + struct bgp_info_mpath *mpath; + if (!binfo->mpath) + { + mpath = bgp_info_mpath_new(); + if (!mpath) + return NULL; + binfo->mpath = mpath; + mpath->mp_info = binfo; + } + return binfo->mpath; +} + +/* + * bgp_info_mpath_enqueue + * + * Enqueue a path onto the multipath list given the previous multipath + * list entry + */ +static void +bgp_info_mpath_enqueue (struct bgp_info *prev_info, struct bgp_info *binfo) +{ + struct bgp_info_mpath *prev, *mpath; + + prev = bgp_info_mpath_get (prev_info); + mpath = bgp_info_mpath_get (binfo); + if (!prev || !mpath) + return; + + mpath->mp_next = prev->mp_next; + mpath->mp_prev = prev; + if (prev->mp_next) + prev->mp_next->mp_prev = mpath; + prev->mp_next = mpath; + + SET_FLAG (binfo->flags, BGP_INFO_MULTIPATH); +} + +/* + * bgp_info_mpath_dequeue + * + * Remove a path from the multipath list + */ +void +bgp_info_mpath_dequeue (struct bgp_info *binfo) +{ + struct bgp_info_mpath *mpath = binfo->mpath; + if (!mpath) + return; + if (mpath->mp_prev) + mpath->mp_prev->mp_next = mpath->mp_next; + if (mpath->mp_next) + mpath->mp_next->mp_prev = mpath->mp_prev; + mpath->mp_next = mpath->mp_prev = NULL; + UNSET_FLAG (binfo->flags, BGP_INFO_MULTIPATH); +} + +/* + * bgp_info_mpath_next + * + * Given a bgp_info, return the next multipath entry + */ +struct bgp_info * +bgp_info_mpath_next (struct bgp_info *binfo) +{ + if (!binfo->mpath || !binfo->mpath->mp_next) + return NULL; + return binfo->mpath->mp_next->mp_info; +} + +/* + * bgp_info_mpath_first + * + * Given bestpath bgp_info, return the first multipath entry. + */ +struct bgp_info * +bgp_info_mpath_first (struct bgp_info *binfo) +{ + return bgp_info_mpath_next (binfo); +} + +/* + * bgp_info_mpath_count + * + * Given the bestpath bgp_info, return the number of multipath entries + */ +u_int32_t +bgp_info_mpath_count (struct bgp_info *binfo) +{ + if (!binfo->mpath) + return 0; + return binfo->mpath->mp_count; +} + +/* + * bgp_info_mpath_count_set + * + * Sets the count of multipaths into bestpath's mpath element + */ +static void +bgp_info_mpath_count_set (struct bgp_info *binfo, u_int32_t count) +{ + struct bgp_info_mpath *mpath; + if (!count && !binfo->mpath) + return; + mpath = bgp_info_mpath_get (binfo); + if (!mpath) + return; + mpath->mp_count = count; +} + +/* + * bgp_info_mpath_update + * + * Compare and sync up the multipath list with the mp_list generated by + * bgp_best_selection + */ +void +bgp_info_mpath_update (struct bgp_node *rn, struct bgp_info *new_best, + struct bgp_info *old_best, struct list *mp_list, + struct bgp_maxpaths_cfg *mpath_cfg) +{ + u_int16_t maxpaths, mpath_count, old_mpath_count; + struct listnode *mp_node, *mp_next_node; + struct bgp_info *cur_mpath, *new_mpath, *next_mpath, *prev_mpath; + int mpath_changed, debug; + char pfx_buf[INET_ADDRSTRLEN], nh_buf[2][INET_ADDRSTRLEN]; + + mpath_changed = 0; + maxpaths = BGP_DEFAULT_MAXPATHS; + mpath_count = 0; + cur_mpath = NULL; + old_mpath_count = 0; + prev_mpath = new_best; + mp_node = listhead (mp_list); + debug = BGP_DEBUG (events, EVENTS); + + if (debug) + prefix2str (&rn->p, pfx_buf, sizeof (pfx_buf)); + + if (new_best) + { + mpath_count++; + if (new_best != old_best) + bgp_info_mpath_dequeue (new_best); + maxpaths = (peer_sort (new_best->peer) == BGP_PEER_IBGP) ? + mpath_cfg->maxpaths_ibgp : mpath_cfg->maxpaths_ebgp; + } + + if (old_best) + { + cur_mpath = bgp_info_mpath_first (old_best); + old_mpath_count = bgp_info_mpath_count (old_best); + bgp_info_mpath_count_set (old_best, 0); + bgp_info_mpath_dequeue (old_best); + } + + /* + * We perform an ordered walk through both lists in parallel. + * The reason for the ordered walk is that if there are paths + * that were previously multipaths and are still multipaths, the walk + * should encounter them in both lists at the same time. Otherwise + * there will be paths that are in one list or another, and we + * will deal with these separately. + * + * Note that new_best might be somewhere in the mp_list, so we need + * to skip over it + */ + while (mp_node || cur_mpath) + { + /* + * We can bail out of this loop if all existing paths on the + * multipath list have been visited (for cleanup purposes) and + * the maxpath requirement is fulfulled + */ + if (!cur_mpath && (mpath_count >= maxpaths)) + break; + + mp_next_node = mp_node ? listnextnode (mp_node) : NULL; + next_mpath = cur_mpath ? bgp_info_mpath_next (cur_mpath) : NULL; + + /* + * If equal, the path was a multipath and is still a multipath. + * Insert onto new multipath list if maxpaths allows. + */ + if (mp_node && (listgetdata (mp_node) == cur_mpath)) + { + list_delete_node (mp_list, mp_node); + bgp_info_mpath_dequeue (cur_mpath); + if ((mpath_count < maxpaths) && + bgp_info_nexthop_cmp (prev_mpath, cur_mpath)) + { + bgp_info_mpath_enqueue (prev_mpath, cur_mpath); + prev_mpath = cur_mpath; + mpath_count++; + } + else + { + mpath_changed = 1; + if (debug) + zlog_debug ("%s remove mpath nexthop %s peer %s", pfx_buf, + inet_ntop (AF_INET, &cur_mpath->attr->nexthop, + nh_buf[0], sizeof (nh_buf[0])), + sockunion2str (cur_mpath->peer->su_remote, + nh_buf[1], sizeof (nh_buf[1]))); + } + mp_node = mp_next_node; + cur_mpath = next_mpath; + continue; + } + + if (cur_mpath && (!mp_node || + (bgp_info_mpath_cmp (cur_mpath, + listgetdata (mp_node)) < 0))) + { + /* + * If here, we have an old multipath and either the mp_list + * is finished or the next mp_node points to a later + * multipath, so we need to purge this path from the + * multipath list + */ + bgp_info_mpath_dequeue (cur_mpath); + mpath_changed = 1; + if (debug) + zlog_debug ("%s remove mpath nexthop %s peer %s", pfx_buf, + inet_ntop (AF_INET, &cur_mpath->attr->nexthop, + nh_buf[0], sizeof (nh_buf[0])), + sockunion2str (cur_mpath->peer->su_remote, + nh_buf[1], sizeof (nh_buf[1]))); + cur_mpath = next_mpath; + } + else + { + /* + * If here, we have a path on the mp_list that was not previously + * a multipath (due to non-equivalance or maxpaths exceeded), + * or the matching multipath is sorted later in the multipath + * list. Before we enqueue the path on the new multipath list, + * make sure its not on the old_best multipath list or referenced + * via next_mpath: + * - If next_mpath points to this new path, update next_mpath to + * point to the multipath after this one + * - Dequeue the path from the multipath list just to make sure + */ + new_mpath = listgetdata (mp_node); + list_delete_node (mp_list, mp_node); + if (new_mpath == next_mpath) + next_mpath = bgp_info_mpath_next (new_mpath); + bgp_info_mpath_dequeue (new_mpath); + if ((mpath_count < maxpaths) && (new_mpath != new_best) && + bgp_info_nexthop_cmp (prev_mpath, new_mpath)) + { + bgp_info_mpath_enqueue (prev_mpath, new_mpath); + prev_mpath = new_mpath; + mpath_changed = 1; + mpath_count++; + if (debug) + zlog_debug ("%s add mpath nexthop %s peer %s", pfx_buf, + inet_ntop (AF_INET, &new_mpath->attr->nexthop, + nh_buf[0], sizeof (nh_buf[0])), + sockunion2str (new_mpath->peer->su_remote, + nh_buf[1], sizeof (nh_buf[1]))); + } + mp_node = mp_next_node; + } + } + + if (new_best) + { + bgp_info_mpath_count_set (new_best, mpath_count-1); + if (mpath_changed || (bgp_info_mpath_count (new_best) != old_mpath_count)) + SET_FLAG (new_best->flags, BGP_INFO_MULTIPATH_CHG); + } +} diff --git a/bgpd/bgp_mpath.h b/bgpd/bgp_mpath.h index de6461fd..1dc2687e 100644 --- a/bgpd/bgp_mpath.h +++ b/bgpd/bgp_mpath.h @@ -27,6 +27,24 @@ /* BGP default maximum-paths */ #define BGP_DEFAULT_MAXPATHS 1 +/* Supplemental information linked to bgp_info for keeping track of + * multipath selections, lazily allocated to save memory + */ +struct bgp_info_mpath +{ + /* Points to the first multipath (on bestpath) or the next multipath */ + struct bgp_info_mpath *mp_next; + + /* Points to the previous multipath or NULL on bestpath */ + struct bgp_info_mpath *mp_prev; + + /* Points to bgp_info associated with this multipath info */ + struct bgp_info *mp_info; + + /* When attached to best path, the number of selected multipaths */ + u_int32_t mp_count; +}; + /* Functions to support maximum-paths configuration */ 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); @@ -37,5 +55,19 @@ extern int bgp_maximum_paths_unset (struct bgp *, afi_t, safi_t, int); 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 *); +extern void bgp_info_mpath_update (struct bgp_node *, struct bgp_info *, + struct bgp_info *, struct list *, + struct bgp_maxpaths_cfg *); + +/* Unlink and free multipath information associated with a bgp_info */ +extern void bgp_info_mpath_dequeue (struct bgp_info *); +extern void bgp_info_mpath_free (struct bgp_info_mpath **); + +/* Walk list of multipaths associated with a best path */ +extern struct bgp_info *bgp_info_mpath_first (struct bgp_info *); +extern struct bgp_info *bgp_info_mpath_next (struct bgp_info *); + +/* Accessors for multipath information */ +extern u_int32_t bgp_info_mpath_count (struct bgp_info *); #endif /* _QUAGGA_BGP_MPATH_H */ diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 718e25ff..ec17dc61 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -141,6 +141,7 @@ bgp_info_free (struct bgp_info *binfo) bgp_attr_unintern (binfo->attr); bgp_info_extra_free (&binfo->extra); + bgp_info_mpath_free (&binfo->mpath); peer_unlock (binfo->peer); /* bgp_info peer reference */ @@ -211,6 +212,7 @@ bgp_info_reap (struct bgp_node *rn, struct bgp_info *ri) else rn->info = ri->next; + bgp_info_mpath_dequeue (ri); bgp_info_unlock (ri); bgp_unlock_node (rn); } @@ -1384,35 +1386,7 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn, } - /* - * 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_info_mpath_update (rn, new_select, old_select, &mp_list, mpath_cfg); bgp_mp_list_clear (&mp_list); @@ -5995,6 +5969,11 @@ route_vty_out_detail (struct vty *vty, struct bgp *bgp, struct prefix *p, if (attr->flag & ATTR_FLAG_BIT(BGP_ATTR_ATOMIC_AGGREGATE)) vty_out (vty, ", atomic-aggregate"); + if (CHECK_FLAG (binfo->flags, BGP_INFO_MULTIPATH) || + (CHECK_FLAG (binfo->flags, BGP_INFO_SELECTED) && + bgp_info_mpath_count (binfo))) + vty_out (vty, ", multipath"); + if (CHECK_FLAG (binfo->flags, BGP_INFO_SELECTED)) vty_out (vty, ", best"); diff --git a/bgpd/bgp_route.h b/bgpd/bgp_route.h index 3e528596..45e8d2e8 100644 --- a/bgpd/bgp_route.h +++ b/bgpd/bgp_route.h @@ -57,6 +57,10 @@ struct bgp_info /* Extra information */ struct bgp_info_extra *extra; + + /* Multipath information */ + struct bgp_info_mpath *mpath; + /* Uptime. */ time_t uptime; @@ -76,6 +80,8 @@ struct bgp_info #define BGP_INFO_STALE (1 << 8) #define BGP_INFO_REMOVED (1 << 9) #define BGP_INFO_COUNTED (1 << 10) +#define BGP_INFO_MULTIPATH (1 << 11) +#define BGP_INFO_MULTIPATH_CHG (1 << 12) /* BGP route type. This can be static, RIP, OSPF, BGP etc. */ u_char type; diff --git a/lib/memtypes.c b/lib/memtypes.c index 59020671..dca32caa 100644 --- a/lib/memtypes.c +++ b/lib/memtypes.c @@ -115,6 +115,7 @@ struct memory_list memory_list_bgp[] = { MTYPE_BGP_SYNCHRONISE, "BGP synchronise" }, { MTYPE_BGP_ADJ_IN, "BGP adj in" }, { MTYPE_BGP_ADJ_OUT, "BGP adj out" }, + { MTYPE_BGP_MPATH_INFO, "BGP multipath info" }, { 0, NULL }, { MTYPE_AS_LIST, "BGP AS list" }, { MTYPE_AS_FILTER, "BGP AS filter" }, diff --git a/tests/bgp_mpath_test.c b/tests/bgp_mpath_test.c index 4d51ddb8..15e450a2 100644 --- a/tests/bgp_mpath_test.c +++ b/tests/bgp_mpath_test.c @@ -194,7 +194,13 @@ testcase_t test_bgp_cfg_maximum_paths = { /*========================================================= * Testcase for bgp_mp_list */ -struct peer test_mp_list_peer[5]; +struct peer test_mp_list_peer[] = { + { .local_as = 1, .as = 2 }, + { .local_as = 1, .as = 2 }, + { .local_as = 1, .as = 2 }, + { .local_as = 1, .as = 2 }, + { .local_as = 1, .as = 2 }, +}; 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[] = { @@ -277,12 +283,88 @@ testcase_t test_bgp_mp_list = { .cleanup = cleanup_bgp_mp_list, }; +/*========================================================= + * Testcase for bgp_info_mpath_update + */ + +struct bgp_node test_rn; + +static int +setup_bgp_info_mpath_update (testcase_t *t) +{ + int i; + str2prefix ("42.1.1.0/24", &test_rn.p); + setup_bgp_mp_list (t); + for (i = 0; i < test_mp_list_info_count; i++) + bgp_info_add (&test_rn, &test_mp_list_info[i]); + return 0; +} + +static int +run_bgp_info_mpath_update (testcase_t *t) +{ + struct bgp_info *new_best, *old_best, *mpath; + struct list mp_list; + struct bgp_maxpaths_cfg mp_cfg = { 3, 3 }; + int test_result = TEST_PASSED; + bgp_mp_list_init (&mp_list); + bgp_mp_list_add (&mp_list, &test_mp_list_info[4]); + bgp_mp_list_add (&mp_list, &test_mp_list_info[3]); + bgp_mp_list_add (&mp_list, &test_mp_list_info[0]); + bgp_mp_list_add (&mp_list, &test_mp_list_info[1]); + new_best = &test_mp_list_info[3]; + old_best = NULL; + bgp_info_mpath_update (&test_rn, new_best, old_best, &mp_list, &mp_cfg); + bgp_mp_list_clear (&mp_list); + EXPECT_TRUE (bgp_info_mpath_count (new_best) == 2, test_result); + mpath = bgp_info_mpath_first (new_best); + EXPECT_TRUE (mpath == &test_mp_list_info[0], test_result); + EXPECT_TRUE (CHECK_FLAG (mpath->flags, BGP_INFO_MULTIPATH), test_result); + mpath = bgp_info_mpath_next (mpath); + EXPECT_TRUE (mpath == &test_mp_list_info[1], test_result); + EXPECT_TRUE (CHECK_FLAG (mpath->flags, BGP_INFO_MULTIPATH), test_result); + + bgp_mp_list_add (&mp_list, &test_mp_list_info[0]); + bgp_mp_list_add (&mp_list, &test_mp_list_info[1]); + new_best = &test_mp_list_info[0]; + old_best = &test_mp_list_info[3]; + bgp_info_mpath_update (&test_rn, new_best, old_best, &mp_list, &mp_cfg); + bgp_mp_list_clear (&mp_list); + EXPECT_TRUE (bgp_info_mpath_count (new_best) == 1, test_result); + mpath = bgp_info_mpath_first (new_best); + EXPECT_TRUE (mpath == &test_mp_list_info[1], test_result); + EXPECT_TRUE (CHECK_FLAG (mpath->flags, BGP_INFO_MULTIPATH), test_result); + EXPECT_TRUE (!CHECK_FLAG (test_mp_list_info[0].flags, BGP_INFO_MULTIPATH), + test_result); + + return test_result; +} + +static int +cleanup_bgp_info_mpath_update (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_info_mpath_update = { + .desc = "Test bgp_info_mpath_update", + .setup = setup_bgp_info_mpath_update, + .run = run_bgp_info_mpath_update, + .cleanup = cleanup_bgp_info_mpath_update, +}; + /*========================================================= * Set up testcase vector */ testcase_t *all_tests[] = { &test_bgp_cfg_maximum_paths, &test_bgp_mp_list, + &test_bgp_info_mpath_update, }; int all_tests_count = (sizeof(all_tests)/sizeof(testcase_t *)); -- cgit v1.2.1