diff options
| -rw-r--r-- | bgpd/bgp_mpath.c | 313 | ||||
| -rw-r--r-- | bgpd/bgp_mpath.h | 32 | ||||
| -rw-r--r-- | bgpd/bgp_route.c | 37 | ||||
| -rw-r--r-- | bgpd/bgp_route.h | 6 | ||||
| -rw-r--r-- | lib/memtypes.c | 1 | ||||
| -rw-r--r-- | 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[] = { @@ -278,11 +284,87 @@ testcase_t test_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 *)); |