diff options
Diffstat (limited to 'bgpd/bgp_mpath.c')
| -rw-r--r-- | bgpd/bgp_mpath.c | 1066 |
1 files changed, 528 insertions, 538 deletions
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c index 7ea5c9e773..6dc6dc6769 100644 --- a/bgpd/bgp_mpath.c +++ b/bgpd/bgp_mpath.c @@ -45,27 +45,25 @@ * * Record maximum-paths configuration for BGP instance */ -int -bgp_maximum_paths_set (struct bgp *bgp, afi_t afi, safi_t safi, - int peertype, u_int16_t maxpaths, u_int16_t options) +int bgp_maximum_paths_set(struct bgp *bgp, afi_t afi, safi_t safi, int peertype, + u_int16_t maxpaths, u_int16_t options) { - if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX)) - return -1; - - switch (peertype) - { - case BGP_PEER_IBGP: - bgp->maxpaths[afi][safi].maxpaths_ibgp = maxpaths; - bgp->maxpaths[afi][safi].ibgp_flags |= options; - break; - case BGP_PEER_EBGP: - bgp->maxpaths[afi][safi].maxpaths_ebgp = maxpaths; - break; - default: - return -1; - } - - return 0; + if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX)) + return -1; + + switch (peertype) { + case BGP_PEER_IBGP: + bgp->maxpaths[afi][safi].maxpaths_ibgp = maxpaths; + bgp->maxpaths[afi][safi].ibgp_flags |= options; + break; + case BGP_PEER_EBGP: + bgp->maxpaths[afi][safi].maxpaths_ebgp = maxpaths; + break; + default: + return -1; + } + + return 0; } /* @@ -73,27 +71,25 @@ bgp_maximum_paths_set (struct bgp *bgp, afi_t afi, safi_t safi, * * Remove maximum-paths configuration from BGP instance */ -int -bgp_maximum_paths_unset (struct bgp *bgp, afi_t afi, safi_t safi, - int peertype) +int bgp_maximum_paths_unset(struct bgp *bgp, afi_t afi, safi_t safi, + int peertype) { - if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX)) - return -1; - - switch (peertype) - { - case BGP_PEER_IBGP: - bgp->maxpaths[afi][safi].maxpaths_ibgp = multipath_num; - bgp->maxpaths[afi][safi].ibgp_flags = 0; - break; - case BGP_PEER_EBGP: - bgp->maxpaths[afi][safi].maxpaths_ebgp = multipath_num; - break; - default: - return -1; - } - - return 0; + if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX)) + return -1; + + switch (peertype) { + case BGP_PEER_IBGP: + bgp->maxpaths[afi][safi].maxpaths_ibgp = multipath_num; + bgp->maxpaths[afi][safi].ibgp_flags = 0; + break; + case BGP_PEER_EBGP: + bgp->maxpaths[afi][safi].maxpaths_ebgp = multipath_num; + break; + default: + return -1; + } + + return 0; } /* @@ -103,57 +99,58 @@ bgp_maximum_paths_unset (struct bgp *bgp, afi_t afi, safi_t safi, * or greater than zero if bi1 is respectively less than, equal to, * or greater than bi2. */ -int -bgp_info_nexthop_cmp (struct bgp_info *bi1, struct bgp_info *bi2) +int bgp_info_nexthop_cmp(struct bgp_info *bi1, struct bgp_info *bi2) { - int compare; - - compare = IPV4_ADDR_CMP (&bi1->attr->nexthop, &bi2->attr->nexthop); - if (!compare) - { - if (bi1->attr->mp_nexthop_len == bi2->attr->mp_nexthop_len) - { - switch (bi1->attr->mp_nexthop_len) - { - case BGP_ATTR_NHLEN_IPV4: - case BGP_ATTR_NHLEN_VPNV4: - compare = IPV4_ADDR_CMP (&bi1->attr->mp_nexthop_global_in, - &bi2->attr->mp_nexthop_global_in); - break; - case BGP_ATTR_NHLEN_IPV6_GLOBAL: - case BGP_ATTR_NHLEN_VPNV6_GLOBAL: - compare = IPV6_ADDR_CMP (&bi1->attr->mp_nexthop_global, - &bi2->attr->mp_nexthop_global); - break; - case BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL: - compare = IPV6_ADDR_CMP (&bi1->attr->mp_nexthop_global, - &bi2->attr->mp_nexthop_global); - if (!compare) - compare = IPV6_ADDR_CMP (&bi1->attr->mp_nexthop_local, - &bi2->attr->mp_nexthop_local); - break; - } - } - - /* This can happen if one IPv6 peer sends you global and link-local - * nexthops but another IPv6 peer only sends you global - */ - else if (bi1->attr->mp_nexthop_len == BGP_ATTR_NHLEN_IPV6_GLOBAL || - bi1->attr->mp_nexthop_len == BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL) - { - compare = IPV6_ADDR_CMP (&bi1->attr->mp_nexthop_global, - &bi2->attr->mp_nexthop_global); - if (!compare) - { - if (bi1->attr->mp_nexthop_len < bi2->attr->mp_nexthop_len) - compare = -1; - else - compare = 1; - } - } - } - - return compare; + int compare; + + compare = IPV4_ADDR_CMP(&bi1->attr->nexthop, &bi2->attr->nexthop); + if (!compare) { + if (bi1->attr->mp_nexthop_len == bi2->attr->mp_nexthop_len) { + switch (bi1->attr->mp_nexthop_len) { + case BGP_ATTR_NHLEN_IPV4: + case BGP_ATTR_NHLEN_VPNV4: + compare = IPV4_ADDR_CMP( + &bi1->attr->mp_nexthop_global_in, + &bi2->attr->mp_nexthop_global_in); + break; + case BGP_ATTR_NHLEN_IPV6_GLOBAL: + case BGP_ATTR_NHLEN_VPNV6_GLOBAL: + compare = IPV6_ADDR_CMP( + &bi1->attr->mp_nexthop_global, + &bi2->attr->mp_nexthop_global); + break; + case BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL: + compare = IPV6_ADDR_CMP( + &bi1->attr->mp_nexthop_global, + &bi2->attr->mp_nexthop_global); + if (!compare) + compare = IPV6_ADDR_CMP( + &bi1->attr->mp_nexthop_local, + &bi2->attr->mp_nexthop_local); + break; + } + } + + /* This can happen if one IPv6 peer sends you global and + * link-local + * nexthops but another IPv6 peer only sends you global + */ + else if (bi1->attr->mp_nexthop_len == BGP_ATTR_NHLEN_IPV6_GLOBAL + || bi1->attr->mp_nexthop_len + == BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL) { + compare = IPV6_ADDR_CMP(&bi1->attr->mp_nexthop_global, + &bi2->attr->mp_nexthop_global); + if (!compare) { + if (bi1->attr->mp_nexthop_len + < bi2->attr->mp_nexthop_len) + compare = -1; + else + compare = 1; + } + } + } + + return compare; } /* @@ -168,30 +165,29 @@ bgp_info_nexthop_cmp (struct bgp_info *bi1, struct bgp_info *bi2) * 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) +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) - { - if (!bi1->peer->su_remote && !bi2->peer->su_remote) - compare = 0; - else if (!bi1->peer->su_remote) - compare = 1; - else if (!bi2->peer->su_remote) - compare = -1; - else - compare = sockunion_cmp (bi1->peer->su_remote, bi2->peer->su_remote); - } - - return compare; + struct bgp_info *bi1, *bi2; + int compare; + + bi1 = val1; + bi2 = val2; + + compare = bgp_info_nexthop_cmp(bi1, bi2); + + if (!compare) { + if (!bi1->peer->su_remote && !bi2->peer->su_remote) + compare = 0; + else if (!bi1->peer->su_remote) + compare = 1; + else if (!bi2->peer->su_remote) + compare = -1; + else + compare = sockunion_cmp(bi1->peer->su_remote, + bi2->peer->su_remote); + } + + return compare; } /* @@ -200,12 +196,11 @@ bgp_info_mpath_cmp (void *val1, void *val2) * Initialize the mp_list, which holds the list of multipaths * selected by bgp_best_selection */ -void -bgp_mp_list_init (struct list *mp_list) +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; + assert(mp_list); + memset(mp_list, 0, sizeof(struct list)); + mp_list->cmp = bgp_info_mpath_cmp; } /* @@ -213,11 +208,10 @@ bgp_mp_list_init (struct list *mp_list) * * Clears all entries out of the mp_list */ -void -bgp_mp_list_clear (struct list *mp_list) +void bgp_mp_list_clear(struct list *mp_list) { - assert (mp_list); - list_delete_all_node (mp_list); + assert(mp_list); + list_delete_all_node(mp_list); } /* @@ -225,11 +219,10 @@ bgp_mp_list_clear (struct list *mp_list) * * Adds a multipath entry to the mp_list */ -void -bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo) +void bgp_mp_list_add(struct list *mp_list, struct bgp_info *mpinfo) { - assert (mp_list && mpinfo); - listnode_add_sort (mp_list, mpinfo); + assert(mp_list && mpinfo); + listnode_add_sort(mp_list, mpinfo); } /* @@ -237,12 +230,12 @@ bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo) * * Allocate and zero memory for a new bgp_info_mpath element */ -static struct bgp_info_mpath * -bgp_info_mpath_new (void) +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; + struct bgp_info_mpath *new_mpath; + new_mpath = + XCALLOC(MTYPE_BGP_MPATH_INFO, sizeof(struct bgp_info_mpath)); + return new_mpath; } /* @@ -250,16 +243,14 @@ bgp_info_mpath_new (void) * * Release resources for a bgp_info_mpath element and zero out pointer */ -void -bgp_info_mpath_free (struct bgp_info_mpath **mpath) +void bgp_info_mpath_free(struct bgp_info_mpath **mpath) { - if (mpath && *mpath) - { - if ((*mpath)->mp_attr) - bgp_attr_unintern (&(*mpath)->mp_attr); - XFREE (MTYPE_BGP_MPATH_INFO, *mpath); - *mpath = NULL; - } + if (mpath && *mpath) { + if ((*mpath)->mp_attr) + bgp_attr_unintern(&(*mpath)->mp_attr); + XFREE(MTYPE_BGP_MPATH_INFO, *mpath); + *mpath = NULL; + } } /* @@ -268,19 +259,17 @@ bgp_info_mpath_free (struct bgp_info_mpath **mpath) * 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) +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; + 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; } /* @@ -289,23 +278,23 @@ bgp_info_mpath_get (struct bgp_info *binfo) * 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) +static void bgp_info_mpath_enqueue(struct bgp_info *prev_info, + struct bgp_info *binfo) { - struct bgp_info_mpath *prev, *mpath; + struct bgp_info_mpath *prev, *mpath; - prev = bgp_info_mpath_get (prev_info); - mpath = bgp_info_mpath_get (binfo); - if (!prev || !mpath) - return; + 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; + 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); + SET_FLAG(binfo->flags, BGP_INFO_MULTIPATH); } /* @@ -313,18 +302,17 @@ bgp_info_mpath_enqueue (struct bgp_info *prev_info, struct bgp_info *binfo) * * Remove a path from the multipath list */ -void -bgp_info_mpath_dequeue (struct bgp_info *binfo) +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); + 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); } /* @@ -332,12 +320,11 @@ bgp_info_mpath_dequeue (struct bgp_info *binfo) * * Given a bgp_info, return the next multipath entry */ -struct bgp_info * -bgp_info_mpath_next (struct bgp_info *binfo) +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; + if (!binfo->mpath || !binfo->mpath->mp_next) + return NULL; + return binfo->mpath->mp_next->mp_info; } /* @@ -345,10 +332,9 @@ bgp_info_mpath_next (struct bgp_info *binfo) * * Given bestpath bgp_info, return the first multipath entry. */ -struct bgp_info * -bgp_info_mpath_first (struct bgp_info *binfo) +struct bgp_info *bgp_info_mpath_first(struct bgp_info *binfo) { - return bgp_info_mpath_next (binfo); + return bgp_info_mpath_next(binfo); } /* @@ -356,12 +342,11 @@ bgp_info_mpath_first (struct bgp_info *binfo) * * Given the bestpath bgp_info, return the number of multipath entries */ -u_int32_t -bgp_info_mpath_count (struct bgp_info *binfo) +u_int32_t bgp_info_mpath_count(struct bgp_info *binfo) { - if (!binfo->mpath) - return 0; - return binfo->mpath->mp_count; + if (!binfo->mpath) + return 0; + return binfo->mpath->mp_count; } /* @@ -369,16 +354,15 @@ bgp_info_mpath_count (struct bgp_info *binfo) * * 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) +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; + struct bgp_info_mpath *mpath; + if (!count && !binfo->mpath) + return; + mpath = bgp_info_mpath_get(binfo); + if (!mpath) + return; + mpath->mp_count = count; } /* @@ -387,12 +371,11 @@ bgp_info_mpath_count_set (struct bgp_info *binfo, u_int32_t count) * Given bestpath bgp_info, return aggregated attribute set used * for advertising the multipath route */ -struct attr * -bgp_info_mpath_attr (struct bgp_info *binfo) +struct attr *bgp_info_mpath_attr(struct bgp_info *binfo) { - if (!binfo->mpath) - return NULL; - return binfo->mpath->mp_attr; + if (!binfo->mpath) + return NULL; + return binfo->mpath->mp_attr; } /* @@ -400,16 +383,15 @@ bgp_info_mpath_attr (struct bgp_info *binfo) * * Sets the aggregated attribute into bestpath's mpath element */ -static void -bgp_info_mpath_attr_set (struct bgp_info *binfo, struct attr *attr) +static void bgp_info_mpath_attr_set(struct bgp_info *binfo, struct attr *attr) { - struct bgp_info_mpath *mpath; - if (!attr && !binfo->mpath) - return; - mpath = bgp_info_mpath_get (binfo); - if (!mpath) - return; - mpath->mp_attr = attr; + struct bgp_info_mpath *mpath; + if (!attr && !binfo->mpath) + return; + mpath = bgp_info_mpath_get(binfo); + if (!mpath) + return; + mpath->mp_attr = attr; } /* @@ -418,196 +400,210 @@ bgp_info_mpath_attr_set (struct bgp_info *binfo, struct attr *attr) * 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) +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[PREFIX2STR_BUFFER], nh_buf[2][INET6_ADDRSTRLEN]; - char path_buf[PATH_ADDPATH_STR_BUFFER]; - - mpath_changed = 0; - maxpaths = multipath_num; - mpath_count = 0; - cur_mpath = NULL; - old_mpath_count = 0; - prev_mpath = new_best; - mp_node = listhead (mp_list); - debug = bgp_debug_bestpath(&rn->p); - - 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 = (new_best->peer->sort == 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); - } - - if (debug) - zlog_debug("%s: starting mpath update, newbest %s num candidates %d old-mpath-count %d", - pfx_buf, new_best ? new_best->peer->host : "NONE", - listcount (mp_list), old_mpath_count); - - /* - * 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) - { - struct bgp_info *tmp_info; - - /* - * 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; - tmp_info = mp_node ? listgetdata (mp_node) : NULL; - - if (debug) - zlog_debug("%s: comparing candidate %s with existing mpath %s", - pfx_buf, tmp_info ? tmp_info->peer->host : "NONE", - cur_mpath ? cur_mpath->peer->host : "NONE"); - - /* - * 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++; - if (debug) - { - bgp_info_path_with_addpath_rx_str(cur_mpath, path_buf); - zlog_debug("%s: %s is still multipath, cur count %d", - pfx_buf, path_buf, mpath_count); - } - } - else - { - mpath_changed = 1; - if (debug) - { - bgp_info_path_with_addpath_rx_str(cur_mpath, path_buf); - zlog_debug ("%s: remove mpath %s nexthop %s, cur count %d", - pfx_buf, path_buf, - inet_ntop (AF_INET, &cur_mpath->attr->nexthop, - nh_buf[0], sizeof (nh_buf[0])), - mpath_count); - } - } - 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) - { - bgp_info_path_with_addpath_rx_str(cur_mpath, path_buf); - zlog_debug ("%s: remove mpath %s nexthop %s, cur count %d", - pfx_buf, path_buf, - inet_ntop (AF_INET, &cur_mpath->attr->nexthop, - nh_buf[0], sizeof (nh_buf[0])), - mpath_count); - } - 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 ((mpath_count < maxpaths) && (new_mpath != new_best) && - bgp_info_nexthop_cmp (prev_mpath, new_mpath)) - { - if (new_mpath == next_mpath) - bgp_info_mpath_next (new_mpath); - bgp_info_mpath_dequeue (new_mpath); - - bgp_info_mpath_enqueue (prev_mpath, new_mpath); - prev_mpath = new_mpath; - mpath_changed = 1; - mpath_count++; - if (debug) - { - bgp_info_path_with_addpath_rx_str(new_mpath, path_buf); - zlog_debug ("%s: add mpath %s nexthop %s, cur count %d", - pfx_buf, path_buf, - inet_ntop (AF_INET, &new_mpath->attr->nexthop, - nh_buf[0], sizeof (nh_buf[0])), - mpath_count); - } - } - mp_node = mp_next_node; - } - } - - if (new_best) - { - if (debug) - zlog_debug("%s: New mpath count (incl newbest) %d mpath-change %s", - pfx_buf, mpath_count, mpath_changed ? "YES" : "NO"); - - 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); - } + 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[PREFIX2STR_BUFFER], nh_buf[2][INET6_ADDRSTRLEN]; + char path_buf[PATH_ADDPATH_STR_BUFFER]; + + mpath_changed = 0; + maxpaths = multipath_num; + mpath_count = 0; + cur_mpath = NULL; + old_mpath_count = 0; + prev_mpath = new_best; + mp_node = listhead(mp_list); + debug = bgp_debug_bestpath(&rn->p); + + 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 = (new_best->peer->sort == 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); + } + + if (debug) + zlog_debug( + "%s: starting mpath update, newbest %s num candidates %d old-mpath-count %d", + pfx_buf, new_best ? new_best->peer->host : "NONE", + listcount(mp_list), old_mpath_count); + + /* + * 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) { + struct bgp_info *tmp_info; + + /* + * 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; + tmp_info = mp_node ? listgetdata(mp_node) : NULL; + + if (debug) + zlog_debug( + "%s: comparing candidate %s with existing mpath %s", + pfx_buf, + tmp_info ? tmp_info->peer->host : "NONE", + cur_mpath ? cur_mpath->peer->host : "NONE"); + + /* + * 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++; + if (debug) { + bgp_info_path_with_addpath_rx_str( + cur_mpath, path_buf); + zlog_debug( + "%s: %s is still multipath, cur count %d", + pfx_buf, path_buf, mpath_count); + } + } else { + mpath_changed = 1; + if (debug) { + bgp_info_path_with_addpath_rx_str( + cur_mpath, path_buf); + zlog_debug( + "%s: remove mpath %s nexthop %s, cur count %d", + pfx_buf, path_buf, + inet_ntop(AF_INET, + &cur_mpath->attr + ->nexthop, + nh_buf[0], + sizeof(nh_buf[0])), + mpath_count); + } + } + 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) { + bgp_info_path_with_addpath_rx_str(cur_mpath, + path_buf); + zlog_debug( + "%s: remove mpath %s nexthop %s, cur count %d", + pfx_buf, path_buf, + inet_ntop(AF_INET, + &cur_mpath->attr->nexthop, + nh_buf[0], sizeof(nh_buf[0])), + mpath_count); + } + 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 ((mpath_count < maxpaths) && (new_mpath != new_best) + && bgp_info_nexthop_cmp(prev_mpath, new_mpath)) { + if (new_mpath == next_mpath) + bgp_info_mpath_next(new_mpath); + bgp_info_mpath_dequeue(new_mpath); + + bgp_info_mpath_enqueue(prev_mpath, new_mpath); + prev_mpath = new_mpath; + mpath_changed = 1; + mpath_count++; + if (debug) { + bgp_info_path_with_addpath_rx_str( + new_mpath, path_buf); + zlog_debug( + "%s: add mpath %s nexthop %s, cur count %d", + pfx_buf, path_buf, + inet_ntop(AF_INET, + &new_mpath->attr + ->nexthop, + nh_buf[0], + sizeof(nh_buf[0])), + mpath_count); + } + } + mp_node = mp_next_node; + } + } + + if (new_best) { + if (debug) + zlog_debug( + "%s: New mpath count (incl newbest) %d mpath-change %s", + pfx_buf, mpath_count, + mpath_changed ? "YES" : "NO"); + + 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); + } } /* @@ -616,23 +612,22 @@ bgp_info_mpath_update (struct bgp_node *rn, struct bgp_info *new_best, * Clean up multipath information for BGP_INFO_DMED_SELECTED path that * is not selected as best path */ -void -bgp_mp_dmed_deselect (struct bgp_info *dmed_best) +void bgp_mp_dmed_deselect(struct bgp_info *dmed_best) { - struct bgp_info *mpinfo, *mpnext; + struct bgp_info *mpinfo, *mpnext; - if (!dmed_best) - return; + if (!dmed_best) + return; - for (mpinfo = bgp_info_mpath_first (dmed_best); mpinfo; mpinfo = mpnext) - { - mpnext = bgp_info_mpath_next (mpinfo); - bgp_info_mpath_dequeue (mpinfo); - } + for (mpinfo = bgp_info_mpath_first(dmed_best); mpinfo; + mpinfo = mpnext) { + mpnext = bgp_info_mpath_next(mpinfo); + bgp_info_mpath_dequeue(mpinfo); + } - bgp_info_mpath_count_set (dmed_best, 0); - UNSET_FLAG (dmed_best->flags, BGP_INFO_MULTIPATH_CHG); - assert (bgp_info_mpath_first (dmed_best) == 0); + bgp_info_mpath_count_set(dmed_best, 0); + UNSET_FLAG(dmed_best->flags, BGP_INFO_MULTIPATH_CHG); + assert(bgp_info_mpath_first(dmed_best) == 0); } /* @@ -647,129 +642,124 @@ bgp_mp_dmed_deselect (struct bgp_info *dmed_best) * is no change in multipath selection and no attribute change in * any multipath. */ -void -bgp_info_mpath_aggregate_update (struct bgp_info *new_best, - struct bgp_info *old_best) +void bgp_info_mpath_aggregate_update(struct bgp_info *new_best, + struct bgp_info *old_best) { - struct bgp_info *mpinfo; - struct aspath *aspath; - struct aspath *asmerge; - struct attr *new_attr, *old_attr; - u_char origin; - struct community *community, *commerge; - struct ecommunity *ecomm, *ecommerge; - struct lcommunity *lcomm, *lcommerge; - struct attr attr = { 0 }; - - if (old_best && (old_best != new_best) && - (old_attr = bgp_info_mpath_attr (old_best))) - { - bgp_attr_unintern (&old_attr); - bgp_info_mpath_attr_set (old_best, NULL); - } - - if (!new_best) - return; - - if (!bgp_info_mpath_count (new_best)) - { - if ((new_attr = bgp_info_mpath_attr (new_best))) - { - bgp_attr_unintern (&new_attr); - bgp_info_mpath_attr_set (new_best, NULL); - SET_FLAG (new_best->flags, BGP_INFO_ATTR_CHANGED); - } - return; - } - - bgp_attr_dup (&attr, new_best->attr); - - if (new_best->peer && - bgp_flag_check (new_best->peer->bgp, BGP_FLAG_MULTIPATH_RELAX_AS_SET)) - { - - /* aggregate attribute from multipath constituents */ - aspath = aspath_dup (attr.aspath); - origin = attr.origin; - community = attr.community ? community_dup (attr.community) : NULL; - ecomm = (attr.ecommunity) ? ecommunity_dup (attr.ecommunity) : NULL; - lcomm = (attr.lcommunity) ? lcommunity_dup (attr.lcommunity) : NULL; - - for (mpinfo = bgp_info_mpath_first (new_best); mpinfo; - mpinfo = bgp_info_mpath_next (mpinfo)) - { - asmerge = aspath_aggregate (aspath, mpinfo->attr->aspath); - aspath_free (aspath); - aspath = asmerge; - - if (origin < mpinfo->attr->origin) - origin = mpinfo->attr->origin; - - if (mpinfo->attr->community) - { - if (community) - { - commerge = community_merge (community, mpinfo->attr->community); - community = community_uniq_sort (commerge); - community_free (commerge); - } - else - community = community_dup (mpinfo->attr->community); - } - - if (mpinfo->attr->ecommunity) - { - if (ecomm) - { - ecommerge = ecommunity_merge (ecomm, mpinfo->attr->ecommunity); - ecomm = ecommunity_uniq_sort (ecommerge); - ecommunity_free (&ecommerge); - } - else - ecomm = ecommunity_dup (mpinfo->attr->ecommunity); - } - if (mpinfo->attr->lcommunity) - { - if (lcomm) - { - lcommerge = lcommunity_merge (lcomm, mpinfo->attr->lcommunity); - lcomm = lcommunity_uniq_sort (lcommerge); - lcommunity_free (&lcommerge); - } - else - lcomm = lcommunity_dup (mpinfo->attr->lcommunity); - } - } - - attr.aspath = aspath; - attr.origin = origin; - if (community) - { - attr.community = community; - attr.flag |= ATTR_FLAG_BIT (BGP_ATTR_COMMUNITIES); - } - if (ecomm) - { - attr.ecommunity = ecomm; - attr.flag |= ATTR_FLAG_BIT (BGP_ATTR_EXT_COMMUNITIES); - } - - /* Zap multipath attr nexthop so we set nexthop to self */ - attr.nexthop.s_addr = 0; - memset (&attr.mp_nexthop_global, 0, sizeof (struct in6_addr)); - - /* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */ - } - - new_attr = bgp_attr_intern (&attr); - - if (new_attr != bgp_info_mpath_attr (new_best)) - { - if ((old_attr = bgp_info_mpath_attr (new_best))) - bgp_attr_unintern (&old_attr); - bgp_info_mpath_attr_set (new_best, new_attr); - SET_FLAG (new_best->flags, BGP_INFO_ATTR_CHANGED); - } - else - bgp_attr_unintern (&new_attr); + struct bgp_info *mpinfo; + struct aspath *aspath; + struct aspath *asmerge; + struct attr *new_attr, *old_attr; + u_char origin; + struct community *community, *commerge; + struct ecommunity *ecomm, *ecommerge; + struct lcommunity *lcomm, *lcommerge; + struct attr attr = {0}; + + if (old_best && (old_best != new_best) + && (old_attr = bgp_info_mpath_attr(old_best))) { + bgp_attr_unintern(&old_attr); + bgp_info_mpath_attr_set(old_best, NULL); + } + + if (!new_best) + return; + + if (!bgp_info_mpath_count(new_best)) { + if ((new_attr = bgp_info_mpath_attr(new_best))) { + bgp_attr_unintern(&new_attr); + bgp_info_mpath_attr_set(new_best, NULL); + SET_FLAG(new_best->flags, BGP_INFO_ATTR_CHANGED); + } + return; + } + + bgp_attr_dup(&attr, new_best->attr); + + if (new_best->peer && bgp_flag_check(new_best->peer->bgp, + BGP_FLAG_MULTIPATH_RELAX_AS_SET)) { + + /* aggregate attribute from multipath constituents */ + aspath = aspath_dup(attr.aspath); + origin = attr.origin; + community = + attr.community ? community_dup(attr.community) : NULL; + ecomm = (attr.ecommunity) ? ecommunity_dup(attr.ecommunity) + : NULL; + lcomm = (attr.lcommunity) ? lcommunity_dup(attr.lcommunity) + : NULL; + + for (mpinfo = bgp_info_mpath_first(new_best); mpinfo; + mpinfo = bgp_info_mpath_next(mpinfo)) { + asmerge = + aspath_aggregate(aspath, mpinfo->attr->aspath); + aspath_free(aspath); + aspath = asmerge; + + if (origin < mpinfo->attr->origin) + origin = mpinfo->attr->origin; + + if (mpinfo->attr->community) { + if (community) { + commerge = community_merge( + community, + mpinfo->attr->community); + community = + community_uniq_sort(commerge); + community_free(commerge); + } else + community = community_dup( + mpinfo->attr->community); + } + + if (mpinfo->attr->ecommunity) { + if (ecomm) { + ecommerge = ecommunity_merge( + ecomm, + mpinfo->attr->ecommunity); + ecomm = ecommunity_uniq_sort(ecommerge); + ecommunity_free(&ecommerge); + } else + ecomm = ecommunity_dup( + mpinfo->attr->ecommunity); + } + if (mpinfo->attr->lcommunity) { + if (lcomm) { + lcommerge = lcommunity_merge( + lcomm, + mpinfo->attr->lcommunity); + lcomm = lcommunity_uniq_sort(lcommerge); + lcommunity_free(&lcommerge); + } else + lcomm = lcommunity_dup( + mpinfo->attr->lcommunity); + } + } + + attr.aspath = aspath; + attr.origin = origin; + if (community) { + attr.community = community; + attr.flag |= ATTR_FLAG_BIT(BGP_ATTR_COMMUNITIES); + } + if (ecomm) { + attr.ecommunity = ecomm; + attr.flag |= ATTR_FLAG_BIT(BGP_ATTR_EXT_COMMUNITIES); + } + + /* Zap multipath attr nexthop so we set nexthop to self */ + attr.nexthop.s_addr = 0; + memset(&attr.mp_nexthop_global, 0, sizeof(struct in6_addr)); + + /* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */ + } + + new_attr = bgp_attr_intern(&attr); + + if (new_attr != bgp_info_mpath_attr(new_best)) { + if ((old_attr = bgp_info_mpath_attr(new_best))) + bgp_attr_unintern(&old_attr); + bgp_info_mpath_attr_set(new_best, new_attr); + SET_FLAG(new_best->flags, BGP_INFO_ATTR_CHANGED); + } else + bgp_attr_unintern(&new_attr); } |