diff options
Diffstat (limited to 'bgpd/bgp_mpath.c')
-rw-r--r-- | bgpd/bgp_mpath.c | 313 |
1 files changed, 313 insertions, 0 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); + } +} |