3 * Copyright (C) 2010 Google Inc.
5 * This file is part of Quagga
7 * Quagga is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2, or (at your option) any
12 * Quagga is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 #include "sockunion.h"
32 #include "bgpd/bgpd.h"
33 #include "bgpd/bgp_table.h"
34 #include "bgpd/bgp_route.h"
35 #include "bgpd/bgp_attr.h"
36 #include "bgpd/bgp_debug.h"
37 #include "bgpd/bgp_aspath.h"
38 #include "bgpd/bgp_community.h"
39 #include "bgpd/bgp_ecommunity.h"
40 #include "bgpd/bgp_lcommunity.h"
41 #include "bgpd/bgp_mpath.h"
44 * bgp_maximum_paths_set
46 * Record maximum-paths configuration for BGP instance
48 int bgp_maximum_paths_set(struct bgp
*bgp
, afi_t afi
, safi_t safi
, int peertype
,
49 u_int16_t maxpaths
, u_int16_t options
)
51 if (!bgp
|| (afi
>= AFI_MAX
) || (safi
>= SAFI_MAX
))
56 bgp
->maxpaths
[afi
][safi
].maxpaths_ibgp
= maxpaths
;
57 bgp
->maxpaths
[afi
][safi
].ibgp_flags
|= options
;
60 bgp
->maxpaths
[afi
][safi
].maxpaths_ebgp
= maxpaths
;
70 * bgp_maximum_paths_unset
72 * Remove maximum-paths configuration from BGP instance
74 int bgp_maximum_paths_unset(struct bgp
*bgp
, afi_t afi
, safi_t safi
,
77 if (!bgp
|| (afi
>= AFI_MAX
) || (safi
>= SAFI_MAX
))
82 bgp
->maxpaths
[afi
][safi
].maxpaths_ibgp
= multipath_num
;
83 bgp
->maxpaths
[afi
][safi
].ibgp_flags
= 0;
86 bgp
->maxpaths
[afi
][safi
].maxpaths_ebgp
= multipath_num
;
96 * bgp_info_nexthop_cmp
98 * Compare the nexthops of two paths. Return value is less than, equal to,
99 * or greater than zero if bi1 is respectively less than, equal to,
100 * or greater than bi2.
102 int bgp_info_nexthop_cmp(struct bgp_info
*bi1
, struct bgp_info
*bi2
)
105 struct in6_addr addr1
, addr2
;
107 compare
= IPV4_ADDR_CMP(&bi1
->attr
->nexthop
, &bi2
->attr
->nexthop
);
109 if (bi1
->attr
->mp_nexthop_len
== bi2
->attr
->mp_nexthop_len
) {
110 switch (bi1
->attr
->mp_nexthop_len
) {
111 case BGP_ATTR_NHLEN_IPV4
:
112 case BGP_ATTR_NHLEN_VPNV4
:
113 compare
= IPV4_ADDR_CMP(
114 &bi1
->attr
->mp_nexthop_global_in
,
115 &bi2
->attr
->mp_nexthop_global_in
);
117 case BGP_ATTR_NHLEN_IPV6_GLOBAL
:
118 case BGP_ATTR_NHLEN_VPNV6_GLOBAL
:
119 compare
= IPV6_ADDR_CMP(
120 &bi1
->attr
->mp_nexthop_global
,
121 &bi2
->attr
->mp_nexthop_global
);
123 case BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL
:
124 addr1
= (bi1
->attr
->mp_nexthop_prefer_global
) ?
125 bi1
->attr
->mp_nexthop_global
126 : bi1
->attr
->mp_nexthop_local
;
127 addr2
= (bi2
->attr
->mp_nexthop_prefer_global
) ?
128 bi2
->attr
->mp_nexthop_global
129 : bi2
->attr
->mp_nexthop_local
;
131 if (!bi1
->attr
->mp_nexthop_prefer_global
&&
132 !bi2
->attr
->mp_nexthop_prefer_global
)
133 compare
= !(bi1
->peer
->ifindex
== bi2
->peer
->ifindex
);
135 compare
= IPV6_ADDR_CMP(&addr1
, &addr2
);
140 /* This can happen if one IPv6 peer sends you global and
142 * nexthops but another IPv6 peer only sends you global
144 else if (bi1
->attr
->mp_nexthop_len
== BGP_ATTR_NHLEN_IPV6_GLOBAL
145 || bi1
->attr
->mp_nexthop_len
146 == BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL
) {
147 compare
= IPV6_ADDR_CMP(&bi1
->attr
->mp_nexthop_global
,
148 &bi2
->attr
->mp_nexthop_global
);
150 if (bi1
->attr
->mp_nexthop_len
151 < bi2
->attr
->mp_nexthop_len
)
165 * This function determines our multipath list ordering. By ordering
166 * the list we can deterministically select which paths are included
167 * in the multipath set. The ordering also helps in detecting changes
168 * in the multipath selection so we can detect whether to send an
171 * The order of paths is determined first by received nexthop, and then
172 * by peer address if the nexthops are the same.
174 static int bgp_info_mpath_cmp(void *val1
, void *val2
)
176 struct bgp_info
*bi1
, *bi2
;
182 compare
= bgp_info_nexthop_cmp(bi1
, bi2
);
185 if (!bi1
->peer
->su_remote
&& !bi2
->peer
->su_remote
)
187 else if (!bi1
->peer
->su_remote
)
189 else if (!bi2
->peer
->su_remote
)
192 compare
= sockunion_cmp(bi1
->peer
->su_remote
,
193 bi2
->peer
->su_remote
);
202 * Initialize the mp_list, which holds the list of multipaths
203 * selected by bgp_best_selection
205 void bgp_mp_list_init(struct list
*mp_list
)
208 memset(mp_list
, 0, sizeof(struct list
));
209 mp_list
->cmp
= bgp_info_mpath_cmp
;
215 * Clears all entries out of the mp_list
217 void bgp_mp_list_clear(struct list
*mp_list
)
220 list_delete_all_node(mp_list
);
226 * Adds a multipath entry to the mp_list
228 void bgp_mp_list_add(struct list
*mp_list
, struct bgp_info
*mpinfo
)
230 assert(mp_list
&& mpinfo
);
231 listnode_add_sort(mp_list
, mpinfo
);
237 * Allocate and zero memory for a new bgp_info_mpath element
239 static struct bgp_info_mpath
*bgp_info_mpath_new(void)
241 struct bgp_info_mpath
*new_mpath
;
243 XCALLOC(MTYPE_BGP_MPATH_INFO
, sizeof(struct bgp_info_mpath
));
248 * bgp_info_mpath_free
250 * Release resources for a bgp_info_mpath element and zero out pointer
252 void bgp_info_mpath_free(struct bgp_info_mpath
**mpath
)
254 if (mpath
&& *mpath
) {
255 if ((*mpath
)->mp_attr
)
256 bgp_attr_unintern(&(*mpath
)->mp_attr
);
257 XFREE(MTYPE_BGP_MPATH_INFO
, *mpath
);
265 * Fetch the mpath element for the given bgp_info. Used for
266 * doing lazy allocation.
268 static struct bgp_info_mpath
*bgp_info_mpath_get(struct bgp_info
*binfo
)
270 struct bgp_info_mpath
*mpath
;
272 mpath
= bgp_info_mpath_new();
275 binfo
->mpath
= mpath
;
276 mpath
->mp_info
= binfo
;
282 * bgp_info_mpath_enqueue
284 * Enqueue a path onto the multipath list given the previous multipath
287 static void bgp_info_mpath_enqueue(struct bgp_info
*prev_info
,
288 struct bgp_info
*binfo
)
290 struct bgp_info_mpath
*prev
, *mpath
;
292 prev
= bgp_info_mpath_get(prev_info
);
293 mpath
= bgp_info_mpath_get(binfo
);
297 mpath
->mp_next
= prev
->mp_next
;
298 mpath
->mp_prev
= prev
;
300 prev
->mp_next
->mp_prev
= mpath
;
301 prev
->mp_next
= mpath
;
303 SET_FLAG(binfo
->flags
, BGP_INFO_MULTIPATH
);
307 * bgp_info_mpath_dequeue
309 * Remove a path from the multipath list
311 void bgp_info_mpath_dequeue(struct bgp_info
*binfo
)
313 struct bgp_info_mpath
*mpath
= binfo
->mpath
;
317 mpath
->mp_prev
->mp_next
= mpath
->mp_next
;
319 mpath
->mp_next
->mp_prev
= mpath
->mp_prev
;
320 mpath
->mp_next
= mpath
->mp_prev
= NULL
;
321 UNSET_FLAG(binfo
->flags
, BGP_INFO_MULTIPATH
);
325 * bgp_info_mpath_next
327 * Given a bgp_info, return the next multipath entry
329 struct bgp_info
*bgp_info_mpath_next(struct bgp_info
*binfo
)
331 if (!binfo
->mpath
|| !binfo
->mpath
->mp_next
)
333 return binfo
->mpath
->mp_next
->mp_info
;
337 * bgp_info_mpath_first
339 * Given bestpath bgp_info, return the first multipath entry.
341 struct bgp_info
*bgp_info_mpath_first(struct bgp_info
*binfo
)
343 return bgp_info_mpath_next(binfo
);
347 * bgp_info_mpath_count
349 * Given the bestpath bgp_info, return the number of multipath entries
351 u_int32_t
bgp_info_mpath_count(struct bgp_info
*binfo
)
355 return binfo
->mpath
->mp_count
;
359 * bgp_info_mpath_count_set
361 * Sets the count of multipaths into bestpath's mpath element
363 static void bgp_info_mpath_count_set(struct bgp_info
*binfo
, u_int32_t count
)
365 struct bgp_info_mpath
*mpath
;
366 if (!count
&& !binfo
->mpath
)
368 mpath
= bgp_info_mpath_get(binfo
);
371 mpath
->mp_count
= count
;
375 * bgp_info_mpath_attr
377 * Given bestpath bgp_info, return aggregated attribute set used
378 * for advertising the multipath route
380 struct attr
*bgp_info_mpath_attr(struct bgp_info
*binfo
)
384 return binfo
->mpath
->mp_attr
;
388 * bgp_info_mpath_attr_set
390 * Sets the aggregated attribute into bestpath's mpath element
392 static void bgp_info_mpath_attr_set(struct bgp_info
*binfo
, struct attr
*attr
)
394 struct bgp_info_mpath
*mpath
;
395 if (!attr
&& !binfo
->mpath
)
397 mpath
= bgp_info_mpath_get(binfo
);
400 mpath
->mp_attr
= attr
;
404 * bgp_info_mpath_update
406 * Compare and sync up the multipath list with the mp_list generated by
409 void bgp_info_mpath_update(struct bgp_node
*rn
, struct bgp_info
*new_best
,
410 struct bgp_info
*old_best
, struct list
*mp_list
,
411 struct bgp_maxpaths_cfg
*mpath_cfg
)
413 u_int16_t maxpaths
, mpath_count
, old_mpath_count
;
414 struct listnode
*mp_node
, *mp_next_node
;
415 struct bgp_info
*cur_mpath
, *new_mpath
, *next_mpath
, *prev_mpath
;
416 int mpath_changed
, debug
;
417 char pfx_buf
[PREFIX2STR_BUFFER
], nh_buf
[2][INET6_ADDRSTRLEN
];
418 char path_buf
[PATH_ADDPATH_STR_BUFFER
];
421 maxpaths
= multipath_num
;
425 prev_mpath
= new_best
;
426 mp_node
= listhead(mp_list
);
427 debug
= bgp_debug_bestpath(&rn
->p
);
430 prefix2str(&rn
->p
, pfx_buf
, sizeof(pfx_buf
));
434 if (new_best
!= old_best
)
435 bgp_info_mpath_dequeue(new_best
);
436 maxpaths
= (new_best
->peer
->sort
== BGP_PEER_IBGP
)
437 ? mpath_cfg
->maxpaths_ibgp
438 : mpath_cfg
->maxpaths_ebgp
;
442 cur_mpath
= bgp_info_mpath_first(old_best
);
443 old_mpath_count
= bgp_info_mpath_count(old_best
);
444 bgp_info_mpath_count_set(old_best
, 0);
445 bgp_info_mpath_dequeue(old_best
);
450 "%s: starting mpath update, newbest %s num candidates %d old-mpath-count %d",
451 pfx_buf
, new_best
? new_best
->peer
->host
: "NONE",
452 listcount(mp_list
), old_mpath_count
);
455 * We perform an ordered walk through both lists in parallel.
456 * The reason for the ordered walk is that if there are paths
457 * that were previously multipaths and are still multipaths, the walk
458 * should encounter them in both lists at the same time. Otherwise
459 * there will be paths that are in one list or another, and we
460 * will deal with these separately.
462 * Note that new_best might be somewhere in the mp_list, so we need
465 while (mp_node
|| cur_mpath
) {
466 struct bgp_info
*tmp_info
;
469 * We can bail out of this loop if all existing paths on the
470 * multipath list have been visited (for cleanup purposes) and
471 * the maxpath requirement is fulfulled
473 if (!cur_mpath
&& (mpath_count
>= maxpaths
))
476 mp_next_node
= mp_node
? listnextnode(mp_node
) : NULL
;
477 next_mpath
= cur_mpath
? bgp_info_mpath_next(cur_mpath
) : NULL
;
478 tmp_info
= mp_node
? listgetdata(mp_node
) : NULL
;
482 "%s: comparing candidate %s with existing mpath %s",
484 tmp_info
? tmp_info
->peer
->host
: "NONE",
485 cur_mpath
? cur_mpath
->peer
->host
: "NONE");
488 * If equal, the path was a multipath and is still a multipath.
489 * Insert onto new multipath list if maxpaths allows.
491 if (mp_node
&& (listgetdata(mp_node
) == cur_mpath
)) {
492 list_delete_node(mp_list
, mp_node
);
493 bgp_info_mpath_dequeue(cur_mpath
);
494 if ((mpath_count
< maxpaths
)
495 && bgp_info_nexthop_cmp(prev_mpath
, cur_mpath
)) {
496 bgp_info_mpath_enqueue(prev_mpath
, cur_mpath
);
497 prev_mpath
= cur_mpath
;
500 bgp_info_path_with_addpath_rx_str(
501 cur_mpath
, path_buf
);
503 "%s: %s is still multipath, cur count %d",
504 pfx_buf
, path_buf
, mpath_count
);
509 bgp_info_path_with_addpath_rx_str(
510 cur_mpath
, path_buf
);
512 "%s: remove mpath %s nexthop %s, cur count %d",
522 mp_node
= mp_next_node
;
523 cur_mpath
= next_mpath
;
529 || (bgp_info_mpath_cmp(cur_mpath
, listgetdata(mp_node
))
532 * If here, we have an old multipath and either the
534 * is finished or the next mp_node points to a later
535 * multipath, so we need to purge this path from the
538 bgp_info_mpath_dequeue(cur_mpath
);
541 bgp_info_path_with_addpath_rx_str(cur_mpath
,
544 "%s: remove mpath %s nexthop %s, cur count %d",
547 &cur_mpath
->attr
->nexthop
,
548 nh_buf
[0], sizeof(nh_buf
[0])),
551 cur_mpath
= next_mpath
;
554 * If here, we have a path on the mp_list that was not
556 * a multipath (due to non-equivalance or maxpaths
558 * or the matching multipath is sorted later in the
560 * list. Before we enqueue the path on the new multipath
562 * make sure its not on the old_best multipath list or
565 * - If next_mpath points to this new path, update
567 * point to the multipath after this one
568 * - Dequeue the path from the multipath list just to
571 new_mpath
= listgetdata(mp_node
);
572 list_delete_node(mp_list
, mp_node
);
573 if ((mpath_count
< maxpaths
) && (new_mpath
!= new_best
)
574 && bgp_info_nexthop_cmp(prev_mpath
, new_mpath
)) {
575 if (new_mpath
== next_mpath
)
576 bgp_info_mpath_next(new_mpath
);
577 bgp_info_mpath_dequeue(new_mpath
);
579 bgp_info_mpath_enqueue(prev_mpath
, new_mpath
);
580 prev_mpath
= new_mpath
;
584 bgp_info_path_with_addpath_rx_str(
585 new_mpath
, path_buf
);
587 "%s: add mpath %s nexthop %s, cur count %d",
597 mp_node
= mp_next_node
;
604 "%s: New mpath count (incl newbest) %d mpath-change %s",
605 pfx_buf
, mpath_count
,
606 mpath_changed
? "YES" : "NO");
608 bgp_info_mpath_count_set(new_best
, mpath_count
- 1);
610 || (bgp_info_mpath_count(new_best
) != old_mpath_count
))
611 SET_FLAG(new_best
->flags
, BGP_INFO_MULTIPATH_CHG
);
616 * bgp_mp_dmed_deselect
618 * Clean up multipath information for BGP_INFO_DMED_SELECTED path that
619 * is not selected as best path
621 void bgp_mp_dmed_deselect(struct bgp_info
*dmed_best
)
623 struct bgp_info
*mpinfo
, *mpnext
;
628 for (mpinfo
= bgp_info_mpath_first(dmed_best
); mpinfo
;
630 mpnext
= bgp_info_mpath_next(mpinfo
);
631 bgp_info_mpath_dequeue(mpinfo
);
634 bgp_info_mpath_count_set(dmed_best
, 0);
635 UNSET_FLAG(dmed_best
->flags
, BGP_INFO_MULTIPATH_CHG
);
636 assert(bgp_info_mpath_first(dmed_best
) == 0);
640 * bgp_info_mpath_aggregate_update
642 * Set the multipath aggregate attribute. We need to see if the
643 * aggregate has changed and then set the ATTR_CHANGED flag on the
644 * bestpath info so that a peer update will be generated. The
645 * change is detected by generating the current attribute,
646 * interning it, and then comparing the interned pointer with the
647 * current value. We can skip this generate/compare step if there
648 * is no change in multipath selection and no attribute change in
651 void bgp_info_mpath_aggregate_update(struct bgp_info
*new_best
,
652 struct bgp_info
*old_best
)
654 struct bgp_info
*mpinfo
;
655 struct aspath
*aspath
;
656 struct aspath
*asmerge
;
657 struct attr
*new_attr
, *old_attr
;
659 struct community
*community
, *commerge
;
660 struct ecommunity
*ecomm
, *ecommerge
;
661 struct lcommunity
*lcomm
, *lcommerge
;
662 struct attr attr
= {0};
664 if (old_best
&& (old_best
!= new_best
)
665 && (old_attr
= bgp_info_mpath_attr(old_best
))) {
666 bgp_attr_unintern(&old_attr
);
667 bgp_info_mpath_attr_set(old_best
, NULL
);
673 if (!bgp_info_mpath_count(new_best
)) {
674 if ((new_attr
= bgp_info_mpath_attr(new_best
))) {
675 bgp_attr_unintern(&new_attr
);
676 bgp_info_mpath_attr_set(new_best
, NULL
);
677 SET_FLAG(new_best
->flags
, BGP_INFO_ATTR_CHANGED
);
682 bgp_attr_dup(&attr
, new_best
->attr
);
684 if (new_best
->peer
&& bgp_flag_check(new_best
->peer
->bgp
,
685 BGP_FLAG_MULTIPATH_RELAX_AS_SET
)) {
687 /* aggregate attribute from multipath constituents */
688 aspath
= aspath_dup(attr
.aspath
);
689 origin
= attr
.origin
;
691 attr
.community
? community_dup(attr
.community
) : NULL
;
692 ecomm
= (attr
.ecommunity
) ? ecommunity_dup(attr
.ecommunity
)
694 lcomm
= (attr
.lcommunity
) ? lcommunity_dup(attr
.lcommunity
)
697 for (mpinfo
= bgp_info_mpath_first(new_best
); mpinfo
;
698 mpinfo
= bgp_info_mpath_next(mpinfo
)) {
700 aspath_aggregate(aspath
, mpinfo
->attr
->aspath
);
704 if (origin
< mpinfo
->attr
->origin
)
705 origin
= mpinfo
->attr
->origin
;
707 if (mpinfo
->attr
->community
) {
709 commerge
= community_merge(
711 mpinfo
->attr
->community
);
713 community_uniq_sort(commerge
);
714 community_free(commerge
);
716 community
= community_dup(
717 mpinfo
->attr
->community
);
720 if (mpinfo
->attr
->ecommunity
) {
722 ecommerge
= ecommunity_merge(
724 mpinfo
->attr
->ecommunity
);
725 ecomm
= ecommunity_uniq_sort(ecommerge
);
726 ecommunity_free(&ecommerge
);
728 ecomm
= ecommunity_dup(
729 mpinfo
->attr
->ecommunity
);
731 if (mpinfo
->attr
->lcommunity
) {
733 lcommerge
= lcommunity_merge(
735 mpinfo
->attr
->lcommunity
);
736 lcomm
= lcommunity_uniq_sort(lcommerge
);
737 lcommunity_free(&lcommerge
);
739 lcomm
= lcommunity_dup(
740 mpinfo
->attr
->lcommunity
);
744 attr
.aspath
= aspath
;
745 attr
.origin
= origin
;
747 attr
.community
= community
;
748 attr
.flag
|= ATTR_FLAG_BIT(BGP_ATTR_COMMUNITIES
);
751 attr
.ecommunity
= ecomm
;
752 attr
.flag
|= ATTR_FLAG_BIT(BGP_ATTR_EXT_COMMUNITIES
);
755 attr
.lcommunity
= lcomm
;
756 attr
.flag
|= ATTR_FLAG_BIT(BGP_ATTR_LARGE_COMMUNITIES
);
759 /* Zap multipath attr nexthop so we set nexthop to self */
760 attr
.nexthop
.s_addr
= 0;
761 memset(&attr
.mp_nexthop_global
, 0, sizeof(struct in6_addr
));
763 /* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */
766 new_attr
= bgp_attr_intern(&attr
);
768 if (new_attr
!= bgp_info_mpath_attr(new_best
)) {
769 if ((old_attr
= bgp_info_mpath_attr(new_best
)))
770 bgp_attr_unintern(&old_attr
);
771 bgp_info_mpath_attr_set(new_best
, new_attr
);
772 SET_FLAG(new_best
->flags
, BGP_INFO_ATTR_CHANGED
);
774 bgp_attr_unintern(&new_attr
);