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