bgpd/bgp_mpath.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * BGP Multipath
   4  * Copyright (C) 2010 Google Inc.
   5  *
   6  * This file is part of Quagga
   7  */
   8
   9 #include <zebra.h>
  10
  11 #include "command.h"
  12 #include "prefix.h"
  13 #include "linklist.h"
  14 #include "sockunion.h"
  15 #include "memory.h"
  16 #include "queue.h"
  17 #include "filter.h"
  18
  19 #include "bgpd/bgpd.h"
  20 #include "bgpd/bgp_table.h"
  21 #include "bgpd/bgp_route.h"
  22 #include "bgpd/bgp_attr.h"
  23 #include "bgpd/bgp_debug.h"
  24 #include "bgpd/bgp_aspath.h"
  25 #include "bgpd/bgp_community.h"
  26 #include "bgpd/bgp_ecommunity.h"
  27 #include "bgpd/bgp_lcommunity.h"
  28 #include "bgpd/bgp_mpath.h"
  29
  30 /*
  31  * bgp_maximum_paths_set
  32  *
  33  * Record maximum-paths configuration for BGP instance
  34  */
  35 int bgp_maximum_paths_set(struct bgp *bgp, afi_t afi, safi_t safi, int peertype,
  36                           uint16_t maxpaths, bool same_clusterlen)
  37 {
  38         if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX))
  39                 return -1;
  40
  41         switch (peertype) {
  42         case BGP_PEER_IBGP:
  43                 bgp->maxpaths[afi][safi].maxpaths_ibgp = maxpaths;
  44                 bgp->maxpaths[afi][safi].same_clusterlen = same_clusterlen;
  45                 break;
  46         case BGP_PEER_EBGP:
  47                 bgp->maxpaths[afi][safi].maxpaths_ebgp = maxpaths;
  48                 break;
  49         default:
  50                 return -1;
  51         }
  52
  53         return 0;
  54 }
  55
  56 /*
  57  * bgp_maximum_paths_unset
  58  *
  59  * Remove maximum-paths configuration from BGP instance
  60  */
  61 int bgp_maximum_paths_unset(struct bgp *bgp, afi_t afi, safi_t safi,
  62                             int peertype)
  63 {
  64         if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX))
  65                 return -1;
  66
  67         switch (peertype) {
  68         case BGP_PEER_IBGP:
  69                 bgp->maxpaths[afi][safi].maxpaths_ibgp = multipath_num;
  70                 bgp->maxpaths[afi][safi].same_clusterlen = false;
  71                 break;
  72         case BGP_PEER_EBGP:
  73                 bgp->maxpaths[afi][safi].maxpaths_ebgp = multipath_num;
  74                 break;
  75         default:
  76                 return -1;
  77         }
  78
  79         return 0;
  80 }
  81
  82 /*
  83  * bgp_interface_same
  84  *
  85  * Return true if ifindex for ifp1 and ifp2 are the same, else return false.
  86  */
  87 static int bgp_interface_same(struct interface *ifp1, struct interface *ifp2)
  88 {
  89         if (!ifp1 && !ifp2)
  90                 return 1;
  91
  92         if (!ifp1 && ifp2)
  93                 return 0;
  94
  95         if (ifp1 && !ifp2)
  96                 return 0;
  97
  98         return (ifp1->ifindex == ifp2->ifindex);
  99 }
 100
 101
 102 /*
 103  * bgp_path_info_nexthop_cmp
 104  *
 105  * Compare the nexthops of two paths. Return value is less than, equal to,
 106  * or greater than zero if bpi1 is respectively less than, equal to,
 107  * or greater than bpi2.
 108  */
 109 int bgp_path_info_nexthop_cmp(struct bgp_path_info *bpi1,
 110                               struct bgp_path_info *bpi2)
 111 {
 112         int compare;
 113         struct in6_addr addr1, addr2;
 114
 115         compare = IPV4_ADDR_CMP(&bpi1->attr->nexthop, &bpi2->attr->nexthop);
 116         if (!compare) {
 117                 if (bpi1->attr->mp_nexthop_len == bpi2->attr->mp_nexthop_len) {
 118                         switch (bpi1->attr->mp_nexthop_len) {
 119                         case BGP_ATTR_NHLEN_IPV4:
 120                         case BGP_ATTR_NHLEN_VPNV4:
 121                                 compare = IPV4_ADDR_CMP(
 122                                         &bpi1->attr->mp_nexthop_global_in,
 123                                         &bpi2->attr->mp_nexthop_global_in);
 124                                 break;
 125                         case BGP_ATTR_NHLEN_IPV6_GLOBAL:
 126                         case BGP_ATTR_NHLEN_VPNV6_GLOBAL:
 127                                 compare = IPV6_ADDR_CMP(
 128                                         &bpi1->attr->mp_nexthop_global,
 129                                         &bpi2->attr->mp_nexthop_global);
 130                                 break;
 131                         case BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL:
 132                                 addr1 = (bpi1->attr->mp_nexthop_prefer_global)
 133                                                 ? bpi1->attr->mp_nexthop_global
 134                                                 : bpi1->attr->mp_nexthop_local;
 135                                 addr2 = (bpi2->attr->mp_nexthop_prefer_global)
 136                                                 ? bpi2->attr->mp_nexthop_global
 137                                                 : bpi2->attr->mp_nexthop_local;
 138
 139                                 if (!bpi1->attr->mp_nexthop_prefer_global
 140                                     && !bpi2->attr->mp_nexthop_prefer_global)
 141                                         compare = !bgp_interface_same(
 142                                                 bpi1->peer->ifp,
 143                                                 bpi2->peer->ifp);
 144
 145                                 if (!compare)
 146                                         compare = IPV6_ADDR_CMP(&addr1, &addr2);
 147                                 break;
 148                         }
 149                 }
 150
 151                 /* This can happen if one IPv6 peer sends you global and
 152                  * link-local
 153                  * nexthops but another IPv6 peer only sends you global
 154                  */
 155                 else if (bpi1->attr->mp_nexthop_len
 156                                  == BGP_ATTR_NHLEN_IPV6_GLOBAL
 157                          || bpi1->attr->mp_nexthop_len
 158                                     == BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL) {
 159                         compare = IPV6_ADDR_CMP(&bpi1->attr->mp_nexthop_global,
 160                                                 &bpi2->attr->mp_nexthop_global);
 161                         if (!compare) {
 162                                 if (bpi1->attr->mp_nexthop_len
 163                                     < bpi2->attr->mp_nexthop_len)
 164                                         compare = -1;
 165                                 else
 166                                         compare = 1;
 167                         }
 168                 }
 169         }
 170
 171         /*
 172          * If both nexthops are same then check
 173          * if they belong to same VRF
 174          */
 175         if (!compare && bpi1->attr->nh_type != NEXTHOP_TYPE_BLACKHOLE) {
 176                 if (bpi1->extra && bpi1->extra->bgp_orig && bpi2->extra
 177                     && bpi2->extra->bgp_orig) {
 178                         if (bpi1->extra->bgp_orig->vrf_id
 179                             != bpi2->extra->bgp_orig->vrf_id) {
 180                                 compare = 1;
 181                         }
 182                 }
 183         }
 184
 185         return compare;
 186 }
 187
 188 /*
 189  * bgp_path_info_mpath_cmp
 190  *
 191  * This function determines our multipath list ordering. By ordering
 192  * the list we can deterministically select which paths are included
 193  * in the multipath set. The ordering also helps in detecting changes
 194  * in the multipath selection so we can detect whether to send an
 195  * update to zebra.
 196  *
 197  * The order of paths is determined first by received nexthop, and then
 198  * by peer address if the nexthops are the same.
 199  */
 200 static int bgp_path_info_mpath_cmp(void *val1, void *val2)
 201 {
 202         struct bgp_path_info *bpi1, *bpi2;
 203         int compare;
 204
 205         bpi1 = val1;
 206         bpi2 = val2;
 207
 208         compare = bgp_path_info_nexthop_cmp(bpi1, bpi2);
 209
 210         if (!compare) {
 211                 if (!bpi1->peer->su_remote && !bpi2->peer->su_remote)
 212                         compare = 0;
 213                 else if (!bpi1->peer->su_remote)
 214                         compare = 1;
 215                 else if (!bpi2->peer->su_remote)
 216                         compare = -1;
 217                 else
 218                         compare = sockunion_cmp(bpi1->peer->su_remote,
 219                                                 bpi2->peer->su_remote);
 220         }
 221
 222         return compare;
 223 }
 224
 225 /*
 226  * bgp_mp_list_init
 227  *
 228  * Initialize the mp_list, which holds the list of multipaths
 229  * selected by bgp_best_selection
 230  */
 231 void bgp_mp_list_init(struct list *mp_list)
 232 {
 233         assert(mp_list);
 234         memset(mp_list, 0, sizeof(struct list));
 235         mp_list->cmp = bgp_path_info_mpath_cmp;
 236 }
 237
 238 /*
 239  * bgp_mp_list_clear
 240  *
 241  * Clears all entries out of the mp_list
 242  */
 243 void bgp_mp_list_clear(struct list *mp_list)
 244 {
 245         assert(mp_list);
 246         list_delete_all_node(mp_list);
 247 }
 248
 249 /*
 250  * bgp_mp_list_add
 251  *
 252  * Adds a multipath entry to the mp_list
 253  */
 254 void bgp_mp_list_add(struct list *mp_list, struct bgp_path_info *mpinfo)
 255 {
 256         assert(mp_list && mpinfo);
 257         listnode_add_sort(mp_list, mpinfo);
 258 }
 259
 260 /*
 261  * bgp_path_info_mpath_new
 262  *
 263  * Allocate and zero memory for a new bgp_path_info_mpath element
 264  */
 265 static struct bgp_path_info_mpath *bgp_path_info_mpath_new(void)
 266 {
 267         struct bgp_path_info_mpath *new_mpath;
 268
 269         new_mpath = XCALLOC(MTYPE_BGP_MPATH_INFO,
 270                             sizeof(struct bgp_path_info_mpath));
 271
 272         return new_mpath;
 273 }
 274
 275 /*
 276  * bgp_path_info_mpath_free
 277  *
 278  * Release resources for a bgp_path_info_mpath element and zero out pointer
 279  */
 280 void bgp_path_info_mpath_free(struct bgp_path_info_mpath **mpath)
 281 {
 282         if (mpath && *mpath) {
 283                 if ((*mpath)->mp_attr)
 284                         bgp_attr_unintern(&(*mpath)->mp_attr);
 285                 XFREE(MTYPE_BGP_MPATH_INFO, *mpath);
 286         }
 287 }
 288
 289 /*
 290  * bgp_path_info_mpath_get
 291  *
 292  * Fetch the mpath element for the given bgp_path_info. Used for
 293  * doing lazy allocation.
 294  */
 295 static struct bgp_path_info_mpath *
 296 bgp_path_info_mpath_get(struct bgp_path_info *path)
 297 {
 298         struct bgp_path_info_mpath *mpath;
 299
 300         if (!path)
 301                 return NULL;
 302
 303         if (!path->mpath) {
 304                 mpath = bgp_path_info_mpath_new();
 305                 path->mpath = mpath;
 306                 mpath->mp_info = path;
 307         }
 308         return path->mpath;
 309 }
 310
 311 /*
 312  * bgp_path_info_mpath_enqueue
 313  *
 314  * Enqueue a path onto the multipath list given the previous multipath
 315  * list entry
 316  */
 317 static void bgp_path_info_mpath_enqueue(struct bgp_path_info *prev_info,
 318                                         struct bgp_path_info *path)
 319 {
 320         struct bgp_path_info_mpath *prev, *mpath;
 321
 322         prev = bgp_path_info_mpath_get(prev_info);
 323         mpath = bgp_path_info_mpath_get(path);
 324         if (!prev || !mpath)
 325                 return;
 326
 327         mpath->mp_next = prev->mp_next;
 328         mpath->mp_prev = prev;
 329         if (prev->mp_next)
 330                 prev->mp_next->mp_prev = mpath;
 331         prev->mp_next = mpath;
 332
 333         SET_FLAG(path->flags, BGP_PATH_MULTIPATH);
 334 }
 335
 336 /*
 337  * bgp_path_info_mpath_dequeue
 338  *
 339  * Remove a path from the multipath list
 340  */
 341 void bgp_path_info_mpath_dequeue(struct bgp_path_info *path)
 342 {
 343         struct bgp_path_info_mpath *mpath = path->mpath;
 344         if (!mpath)
 345                 return;
 346         if (mpath->mp_prev)
 347                 mpath->mp_prev->mp_next = mpath->mp_next;
 348         if (mpath->mp_next)
 349                 mpath->mp_next->mp_prev = mpath->mp_prev;
 350         mpath->mp_next = mpath->mp_prev = NULL;
 351         UNSET_FLAG(path->flags, BGP_PATH_MULTIPATH);
 352 }
 353
 354 /*
 355  * bgp_path_info_mpath_next
 356  *
 357  * Given a bgp_path_info, return the next multipath entry
 358  */
 359 struct bgp_path_info *bgp_path_info_mpath_next(struct bgp_path_info *path)
 360 {
 361         if (!path->mpath || !path->mpath->mp_next)
 362                 return NULL;
 363         return path->mpath->mp_next->mp_info;
 364 }
 365
 366 /*
 367  * bgp_path_info_mpath_first
 368  *
 369  * Given bestpath bgp_path_info, return the first multipath entry.
 370  */
 371 struct bgp_path_info *bgp_path_info_mpath_first(struct bgp_path_info *path)
 372 {
 373         return bgp_path_info_mpath_next(path);
 374 }
 375
 376 /*
 377  * bgp_path_info_mpath_count
 378  *
 379  * Given the bestpath bgp_path_info, return the number of multipath entries
 380  */
 381 uint32_t bgp_path_info_mpath_count(struct bgp_path_info *path)
 382 {
 383         if (!path->mpath)
 384                 return 0;
 385         return path->mpath->mp_count;
 386 }
 387
 388 /*
 389  * bgp_path_info_mpath_count_set
 390  *
 391  * Sets the count of multipaths into bestpath's mpath element
 392  */
 393 static void bgp_path_info_mpath_count_set(struct bgp_path_info *path,
 394                                           uint16_t count)
 395 {
 396         struct bgp_path_info_mpath *mpath;
 397         if (!count && !path->mpath)
 398                 return;
 399         mpath = bgp_path_info_mpath_get(path);
 400         if (!mpath)
 401                 return;
 402         mpath->mp_count = count;
 403 }
 404
 405 /*
 406  * bgp_path_info_mpath_lb_update
 407  *
 408  * Update cumulative info related to link-bandwidth
 409  */
 410 static void bgp_path_info_mpath_lb_update(struct bgp_path_info *path, bool set,
 411                                           bool all_paths_lb, uint64_t cum_bw)
 412 {
 413         struct bgp_path_info_mpath *mpath;
 414
 415         mpath = path->mpath;
 416         if (mpath == NULL) {
 417                 if (!set || (cum_bw == 0 && !all_paths_lb))
 418                         return;
 419
 420                 mpath = bgp_path_info_mpath_get(path);
 421                 if (!mpath)
 422                         return;
 423         }
 424         if (set) {
 425                 if (cum_bw)
 426                         SET_FLAG(mpath->mp_flags, BGP_MP_LB_PRESENT);
 427                 else
 428                         UNSET_FLAG(mpath->mp_flags, BGP_MP_LB_PRESENT);
 429                 if (all_paths_lb)
 430                         SET_FLAG(mpath->mp_flags, BGP_MP_LB_ALL);
 431                 else
 432                         UNSET_FLAG(mpath->mp_flags, BGP_MP_LB_ALL);
 433                 mpath->cum_bw = cum_bw;
 434         } else {
 435                 mpath->mp_flags = 0;
 436                 mpath->cum_bw = 0;
 437         }
 438 }
 439
 440 /*
 441  * bgp_path_info_mpath_attr
 442  *
 443  * Given bestpath bgp_path_info, return aggregated attribute set used
 444  * for advertising the multipath route
 445  */
 446 struct attr *bgp_path_info_mpath_attr(struct bgp_path_info *path)
 447 {
 448         if (!path->mpath)
 449                 return NULL;
 450         return path->mpath->mp_attr;
 451 }
 452
 453 /*
 454  * bgp_path_info_chkwtd
 455  *
 456  * Return if we should attempt to do weighted ECMP or not
 457  * The path passed in is the bestpath.
 458  */
 459 bool bgp_path_info_mpath_chkwtd(struct bgp *bgp, struct bgp_path_info *path)
 460 {
 461         /* Check if told to ignore weights or not multipath */
 462         if (bgp->lb_handling == BGP_LINK_BW_IGNORE_BW || !path->mpath)
 463                 return false;
 464
 465         /* All paths in multipath should have associated weight (bandwidth)
 466          * unless told explicitly otherwise.
 467          */
 468         if (bgp->lb_handling != BGP_LINK_BW_SKIP_MISSING &&
 469             bgp->lb_handling != BGP_LINK_BW_DEFWT_4_MISSING)
 470                 return (path->mpath->mp_flags & BGP_MP_LB_ALL);
 471
 472         /* At least one path should have bandwidth. */
 473         return (path->mpath->mp_flags & BGP_MP_LB_PRESENT);
 474 }
 475
 476 /*
 477  * bgp_path_info_mpath_attr
 478  *
 479  * Given bestpath bgp_path_info, return cumulative bandwidth
 480  * computed for all multipaths with bandwidth info
 481  */
 482 uint64_t bgp_path_info_mpath_cumbw(struct bgp_path_info *path)
 483 {
 484         if (!path->mpath)
 485                 return 0;
 486         return path->mpath->cum_bw;
 487 }
 488
 489 /*
 490  * bgp_path_info_mpath_attr_set
 491  *
 492  * Sets the aggregated attribute into bestpath's mpath element
 493  */
 494 static void bgp_path_info_mpath_attr_set(struct bgp_path_info *path,
 495                                          struct attr *attr)
 496 {
 497         struct bgp_path_info_mpath *mpath;
 498         if (!attr && !path->mpath)
 499                 return;
 500         mpath = bgp_path_info_mpath_get(path);
 501         if (!mpath)
 502                 return;
 503         mpath->mp_attr = attr;
 504 }
 505
 506 /*
 507  * bgp_path_info_mpath_update
 508  *
 509  * Compare and sync up the multipath list with the mp_list generated by
 510  * bgp_best_selection
 511  */
 512 void bgp_path_info_mpath_update(struct bgp *bgp, struct bgp_dest *dest,
 513                                 struct bgp_path_info *new_best,
 514                                 struct bgp_path_info *old_best,
 515                                 struct list *mp_list,
 516                                 struct bgp_maxpaths_cfg *mpath_cfg)
 517 {
 518         uint16_t maxpaths, mpath_count, old_mpath_count;
 519         uint32_t bwval;
 520         uint64_t cum_bw, old_cum_bw;
 521         struct listnode *mp_node, *mp_next_node;
 522         struct bgp_path_info *cur_mpath, *new_mpath, *next_mpath, *prev_mpath;
 523         int mpath_changed, debug;
 524         bool all_paths_lb;
 525         char path_buf[PATH_ADDPATH_STR_BUFFER];
 526
 527         mpath_changed = 0;
 528         maxpaths = multipath_num;
 529         mpath_count = 0;
 530         cur_mpath = NULL;
 531         old_mpath_count = 0;
 532         old_cum_bw = cum_bw = 0;
 533         prev_mpath = new_best;
 534         mp_node = listhead(mp_list);
 535         debug = bgp_debug_bestpath(dest);
 536
 537         if (new_best) {
 538                 mpath_count++;
 539                 if (new_best != old_best)
 540                         bgp_path_info_mpath_dequeue(new_best);
 541                 maxpaths = (new_best->peer->sort == BGP_PEER_IBGP)
 542                                    ? mpath_cfg->maxpaths_ibgp
 543                                    : mpath_cfg->maxpaths_ebgp;
 544         }
 545
 546         if (old_best) {
 547                 cur_mpath = bgp_path_info_mpath_first(old_best);
 548                 old_mpath_count = bgp_path_info_mpath_count(old_best);
 549                 old_cum_bw = bgp_path_info_mpath_cumbw(old_best);
 550                 bgp_path_info_mpath_count_set(old_best, 0);
 551                 bgp_path_info_mpath_lb_update(old_best, false, false, 0);
 552                 bgp_path_info_mpath_dequeue(old_best);
 553         }
 554
 555         if (debug)
 556                 zlog_debug(
 557                         "%pRN(%s): starting mpath update, newbest %s num candidates %d old-mpath-count %d old-cum-bw %" PRIu64,
 558                         bgp_dest_to_rnode(dest), bgp->name_pretty,
 559                         new_best ? new_best->peer->host : "NONE",
 560                         mp_list ? listcount(mp_list) : 0, old_mpath_count,
 561                         old_cum_bw);
 562
 563         /*
 564          * We perform an ordered walk through both lists in parallel.
 565          * The reason for the ordered walk is that if there are paths
 566          * that were previously multipaths and are still multipaths, the walk
 567          * should encounter them in both lists at the same time. Otherwise
 568          * there will be paths that are in one list or another, and we
 569          * will deal with these separately.
 570          *
 571          * Note that new_best might be somewhere in the mp_list, so we need
 572          * to skip over it
 573          */
 574         all_paths_lb = true; /* We'll reset if any path doesn't have LB. */
 575         while (mp_node || cur_mpath) {
 576                 struct bgp_path_info *tmp_info;
 577
 578                 /*
 579                  * We can bail out of this loop if all existing paths on the
 580                  * multipath list have been visited (for cleanup purposes) and
 581                  * the maxpath requirement is fulfulled
 582                  */
 583                 if (!cur_mpath && (mpath_count >= maxpaths))
 584                         break;
 585
 586                 mp_next_node = mp_node ? listnextnode(mp_node) : NULL;
 587                 next_mpath =
 588                         cur_mpath ? bgp_path_info_mpath_next(cur_mpath) : NULL;
 589                 tmp_info = mp_node ? listgetdata(mp_node) : NULL;
 590
 591                 if (debug)
 592                         zlog_debug(
 593                                 "%pRN(%s): comparing candidate %s with existing mpath %s",
 594                                 bgp_dest_to_rnode(dest), bgp->name_pretty,
 595                                 tmp_info ? tmp_info->peer->host : "NONE",
 596                                 cur_mpath ? cur_mpath->peer->host : "NONE");
 597
 598                 /*
 599                  * If equal, the path was a multipath and is still a multipath.
 600                  * Insert onto new multipath list if maxpaths allows.
 601                  */
 602                 if (mp_node && (listgetdata(mp_node) == cur_mpath)) {
 603                         list_delete_node(mp_list, mp_node);
 604                         bgp_path_info_mpath_dequeue(cur_mpath);
 605                         if ((mpath_count < maxpaths)
 606                             && prev_mpath
 607                             && bgp_path_info_nexthop_cmp(prev_mpath,
 608                                                          cur_mpath)) {
 609                                 bgp_path_info_mpath_enqueue(prev_mpath,
 610                                                             cur_mpath);
 611                                 prev_mpath = cur_mpath;
 612                                 mpath_count++;
 613                                 if (ecommunity_linkbw_present(
 614                                             bgp_attr_get_ecommunity(
 615                                                     cur_mpath->attr),
 616                                             &bwval))
 617                                         cum_bw += bwval;
 618                                 else
 619                                         all_paths_lb = false;
 620                                 if (debug) {
 621                                         bgp_path_info_path_with_addpath_rx_str(
 622                                                 cur_mpath, path_buf,
 623                                                 sizeof(path_buf));
 624                                         zlog_debug(
 625                                                 "%pRN: %s is still multipath, cur count %d",
 626                                                 bgp_dest_to_rnode(dest),
 627                                                 path_buf, mpath_count);
 628                                 }
 629                         } else {
 630                                 mpath_changed = 1;
 631                                 if (debug) {
 632                                         bgp_path_info_path_with_addpath_rx_str(
 633                                                 cur_mpath, path_buf,
 634                                                 sizeof(path_buf));
 635                                         zlog_debug(
 636                                                 "%pRN: remove mpath %s nexthop %pI4, cur count %d",
 637                                                 bgp_dest_to_rnode(dest),
 638                                                 path_buf,
 639                                                 &cur_mpath->attr->nexthop,
 640                                                 mpath_count);
 641                                 }
 642                         }
 643                         mp_node = mp_next_node;
 644                         cur_mpath = next_mpath;
 645                         continue;
 646                 }
 647
 648                 if (cur_mpath
 649                     && (!mp_node
 650                         || (bgp_path_info_mpath_cmp(cur_mpath,
 651                                                     listgetdata(mp_node))
 652                             < 0))) {
 653                         /*
 654                          * If here, we have an old multipath and either the
 655                          * mp_list
 656                          * is finished or the next mp_node points to a later
 657                          * multipath, so we need to purge this path from the
 658                          * multipath list
 659                          */
 660                         bgp_path_info_mpath_dequeue(cur_mpath);
 661                         mpath_changed = 1;
 662                         if (debug) {
 663                                 bgp_path_info_path_with_addpath_rx_str(
 664                                         cur_mpath, path_buf, sizeof(path_buf));
 665                                 zlog_debug(
 666                                         "%pRN: remove mpath %s nexthop %pI4, cur count %d",
 667                                         bgp_dest_to_rnode(dest), path_buf,
 668                                         &cur_mpath->attr->nexthop, mpath_count);
 669                         }
 670                         cur_mpath = next_mpath;
 671                 } else {
 672                         /*
 673                          * If here, we have a path on the mp_list that was not
 674                          * previously
 675                          * a multipath (due to non-equivalance or maxpaths
 676                          * exceeded),
 677                          * or the matching multipath is sorted later in the
 678                          * multipath
 679                          * list. Before we enqueue the path on the new multipath
 680                          * list,
 681                          * make sure its not on the old_best multipath list or
 682                          * referenced
 683                          * via next_mpath:
 684                          * - If next_mpath points to this new path, update
 685                          * next_mpath to
 686                          *   point to the multipath after this one
 687                          * - Dequeue the path from the multipath list just to
 688                          * make sure
 689                          */
 690                         new_mpath = listgetdata(mp_node);
 691                         list_delete_node(mp_list, mp_node);
 692                         assert(new_mpath);
 693                         assert(prev_mpath);
 694                         if ((mpath_count < maxpaths) && (new_mpath != new_best)
 695                             && bgp_path_info_nexthop_cmp(prev_mpath,
 696                                                          new_mpath)) {
 697                                 bgp_path_info_mpath_dequeue(new_mpath);
 698
 699                                 bgp_path_info_mpath_enqueue(prev_mpath,
 700                                                             new_mpath);
 701                                 prev_mpath = new_mpath;
 702                                 mpath_changed = 1;
 703                                 mpath_count++;
 704                                 if (ecommunity_linkbw_present(
 705                                             bgp_attr_get_ecommunity(
 706                                                     new_mpath->attr),
 707                                             &bwval))
 708                                         cum_bw += bwval;
 709                                 else
 710                                         all_paths_lb = false;
 711                                 if (debug) {
 712                                         bgp_path_info_path_with_addpath_rx_str(
 713                                                 new_mpath, path_buf,
 714                                                 sizeof(path_buf));
 715                                         zlog_debug(
 716                                                 "%pRN: add mpath %s nexthop %pI4, cur count %d",
 717                                                 bgp_dest_to_rnode(dest),
 718                                                 path_buf,
 719                                                 &new_mpath->attr->nexthop,
 720                                                 mpath_count);
 721                                 }
 722                         }
 723                         mp_node = mp_next_node;
 724                 }
 725         }
 726
 727         if (new_best) {
 728                 bgp_path_info_mpath_count_set(new_best, mpath_count - 1);
 729                 if (mpath_count <= 1 ||
 730                     !ecommunity_linkbw_present(
 731                             bgp_attr_get_ecommunity(new_best->attr), &bwval))
 732                         all_paths_lb = false;
 733                 else
 734                         cum_bw += bwval;
 735                 bgp_path_info_mpath_lb_update(new_best, true,
 736                                               all_paths_lb, cum_bw);
 737
 738                 if (debug)
 739                         zlog_debug(
 740                                 "%pRN(%s): New mpath count (incl newbest) %d mpath-change %s all_paths_lb %d cum_bw %" PRIu64,
 741                                 bgp_dest_to_rnode(dest), bgp->name_pretty,
 742                                 mpath_count, mpath_changed ? "YES" : "NO",
 743                                 all_paths_lb, cum_bw);
 744
 745                 if (mpath_changed
 746                     || (bgp_path_info_mpath_count(new_best) != old_mpath_count))
 747                         SET_FLAG(new_best->flags, BGP_PATH_MULTIPATH_CHG);
 748                 if ((mpath_count - 1) != old_mpath_count ||
 749                     old_cum_bw != cum_bw)
 750                         SET_FLAG(new_best->flags, BGP_PATH_LINK_BW_CHG);
 751         }
 752 }
 753
 754 /*
 755  * bgp_mp_dmed_deselect
 756  *
 757  * Clean up multipath information for BGP_PATH_DMED_SELECTED path that
 758  * is not selected as best path
 759  */
 760 void bgp_mp_dmed_deselect(struct bgp_path_info *dmed_best)
 761 {
 762         struct bgp_path_info *mpinfo, *mpnext;
 763
 764         if (!dmed_best)
 765                 return;
 766
 767         for (mpinfo = bgp_path_info_mpath_first(dmed_best); mpinfo;
 768              mpinfo = mpnext) {
 769                 mpnext = bgp_path_info_mpath_next(mpinfo);
 770                 bgp_path_info_mpath_dequeue(mpinfo);
 771         }
 772
 773         bgp_path_info_mpath_count_set(dmed_best, 0);
 774         UNSET_FLAG(dmed_best->flags, BGP_PATH_MULTIPATH_CHG);
 775         UNSET_FLAG(dmed_best->flags, BGP_PATH_LINK_BW_CHG);
 776         assert(bgp_path_info_mpath_first(dmed_best) == NULL);
 777 }
 778
 779 /*
 780  * bgp_path_info_mpath_aggregate_update
 781  *
 782  * Set the multipath aggregate attribute. We need to see if the
 783  * aggregate has changed and then set the ATTR_CHANGED flag on the
 784  * bestpath info so that a peer update will be generated. The
 785  * change is detected by generating the current attribute,
 786  * interning it, and then comparing the interned pointer with the
 787  * current value. We can skip this generate/compare step if there
 788  * is no change in multipath selection and no attribute change in
 789  * any multipath.
 790  */
 791 void bgp_path_info_mpath_aggregate_update(struct bgp_path_info *new_best,
 792                                           struct bgp_path_info *old_best)
 793 {
 794         struct bgp_path_info *mpinfo;
 795         struct aspath *aspath;
 796         struct aspath *asmerge;
 797         struct attr *new_attr, *old_attr;
 798         uint8_t origin;
 799         struct community *community, *commerge;
 800         struct ecommunity *ecomm, *ecommerge;
 801         struct lcommunity *lcomm, *lcommerge;
 802         struct attr attr = {0};
 803
 804         if (old_best && (old_best != new_best)
 805             && (old_attr = bgp_path_info_mpath_attr(old_best))) {
 806                 bgp_attr_unintern(&old_attr);
 807                 bgp_path_info_mpath_attr_set(old_best, NULL);
 808         }
 809
 810         if (!new_best)
 811                 return;
 812
 813         if (!bgp_path_info_mpath_count(new_best)) {
 814                 if ((new_attr = bgp_path_info_mpath_attr(new_best))) {
 815                         bgp_attr_unintern(&new_attr);
 816                         bgp_path_info_mpath_attr_set(new_best, NULL);
 817                         SET_FLAG(new_best->flags, BGP_PATH_ATTR_CHANGED);
 818                 }
 819                 return;
 820         }
 821
 822         attr = *new_best->attr;
 823
 824         if (new_best->peer
 825             && CHECK_FLAG(new_best->peer->bgp->flags,
 826                           BGP_FLAG_MULTIPATH_RELAX_AS_SET)) {
 827
 828                 /* aggregate attribute from multipath constituents */
 829                 aspath = aspath_dup(attr.aspath);
 830                 origin = attr.origin;
 831                 community =
 832                         bgp_attr_get_community(&attr)
 833                                 ? community_dup(bgp_attr_get_community(&attr))
 834                                 : NULL;
 835                 ecomm = (bgp_attr_get_ecommunity(&attr))
 836                                 ? ecommunity_dup(bgp_attr_get_ecommunity(&attr))
 837                                 : NULL;
 838                 lcomm = (bgp_attr_get_lcommunity(&attr))
 839                                 ? lcommunity_dup(bgp_attr_get_lcommunity(&attr))
 840                                 : NULL;
 841
 842                 for (mpinfo = bgp_path_info_mpath_first(new_best); mpinfo;
 843                      mpinfo = bgp_path_info_mpath_next(mpinfo)) {
 844                         asmerge =
 845                                 aspath_aggregate(aspath, mpinfo->attr->aspath);
 846                         aspath_free(aspath);
 847                         aspath = asmerge;
 848
 849                         if (origin < mpinfo->attr->origin)
 850                                 origin = mpinfo->attr->origin;
 851
 852                         if (bgp_attr_get_community(mpinfo->attr)) {
 853                                 if (community) {
 854                                         commerge = community_merge(
 855                                                 community,
 856                                                 bgp_attr_get_community(
 857                                                         mpinfo->attr));
 858                                         community =
 859                                                 community_uniq_sort(commerge);
 860                                         community_free(&commerge);
 861                                 } else
 862                                         community = community_dup(
 863                                                 bgp_attr_get_community(
 864                                                         mpinfo->attr));
 865                         }
 866
 867                         if (bgp_attr_get_ecommunity(mpinfo->attr)) {
 868                                 if (ecomm) {
 869                                         ecommerge = ecommunity_merge(
 870                                                 ecomm, bgp_attr_get_ecommunity(
 871                                                                mpinfo->attr));
 872                                         ecomm = ecommunity_uniq_sort(ecommerge);
 873                                         ecommunity_free(&ecommerge);
 874                                 } else
 875                                         ecomm = ecommunity_dup(
 876                                                 bgp_attr_get_ecommunity(
 877                                                         mpinfo->attr));
 878                         }
 879                         if (bgp_attr_get_lcommunity(mpinfo->attr)) {
 880                                 if (lcomm) {
 881                                         lcommerge = lcommunity_merge(
 882                                                 lcomm, bgp_attr_get_lcommunity(
 883                                                                mpinfo->attr));
 884                                         lcomm = lcommunity_uniq_sort(lcommerge);
 885                                         lcommunity_free(&lcommerge);
 886                                 } else
 887                                         lcomm = lcommunity_dup(
 888                                                 bgp_attr_get_lcommunity(
 889                                                         mpinfo->attr));
 890                         }
 891                 }
 892
 893                 attr.aspath = aspath;
 894                 attr.origin = origin;
 895                 if (community)
 896                         bgp_attr_set_community(&attr, community);
 897                 if (ecomm)
 898                         bgp_attr_set_ecommunity(&attr, ecomm);
 899                 if (lcomm)
 900                         bgp_attr_set_lcommunity(&attr, lcomm);
 901
 902                 /* Zap multipath attr nexthop so we set nexthop to self */
 903                 attr.nexthop.s_addr = INADDR_ANY;
 904                 memset(&attr.mp_nexthop_global, 0, sizeof(struct in6_addr));
 905
 906                 /* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */
 907         }
 908
 909         new_attr = bgp_attr_intern(&attr);
 910
 911         if (new_attr != bgp_path_info_mpath_attr(new_best)) {
 912                 if ((old_attr = bgp_path_info_mpath_attr(new_best)))
 913                         bgp_attr_unintern(&old_attr);
 914                 bgp_path_info_mpath_attr_set(new_best, new_attr);
 915                 SET_FLAG(new_best->flags, BGP_PATH_ATTR_CHANGED);
 916         } else
 917                 bgp_attr_unintern(&new_attr);
 918 }