1 /* A generic nexthop structure
2 * Copyright (C) 2013 Cumulus Networks, Inc.
4 * This file is part of Quagga.
6 * Quagga is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * Quagga is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
28 #include "sockunion.h"
37 #include "nexthop_group.h"
39 DEFINE_MTYPE_STATIC(LIB
, NEXTHOP
, "Nexthop")
40 DEFINE_MTYPE_STATIC(LIB
, NH_LABEL
, "Nexthop label")
42 static int _nexthop_labels_cmp(const struct nexthop
*nh1
,
43 const struct nexthop
*nh2
)
45 const struct mpls_label_stack
*nhl1
= NULL
;
46 const struct mpls_label_stack
*nhl2
= NULL
;
51 /* No labels is a match */
61 if (nhl1
->num_labels
> nhl2
->num_labels
)
64 if (nhl1
->num_labels
< nhl2
->num_labels
)
67 return memcmp(nhl1
->label
, nhl2
->label
, nhl1
->num_labels
);
70 int nexthop_g_addr_cmp(enum nexthop_types_t type
, const union g_addr
*addr1
,
71 const union g_addr
*addr2
)
76 case NEXTHOP_TYPE_IPV4
:
77 case NEXTHOP_TYPE_IPV4_IFINDEX
:
78 ret
= IPV4_ADDR_CMP(&addr1
->ipv4
, &addr2
->ipv4
);
80 case NEXTHOP_TYPE_IPV6
:
81 case NEXTHOP_TYPE_IPV6_IFINDEX
:
82 ret
= IPV6_ADDR_CMP(&addr1
->ipv6
, &addr2
->ipv6
);
84 case NEXTHOP_TYPE_IFINDEX
:
85 case NEXTHOP_TYPE_BLACKHOLE
:
93 static int _nexthop_gateway_cmp(const struct nexthop
*nh1
,
94 const struct nexthop
*nh2
)
96 return nexthop_g_addr_cmp(nh1
->type
, &nh1
->gate
, &nh2
->gate
);
99 static int _nexthop_source_cmp(const struct nexthop
*nh1
,
100 const struct nexthop
*nh2
)
102 return nexthop_g_addr_cmp(nh1
->type
, &nh1
->src
, &nh2
->src
);
105 static int _nexthop_cmp_no_labels(const struct nexthop
*next1
,
106 const struct nexthop
*next2
)
110 if (next1
->vrf_id
< next2
->vrf_id
)
113 if (next1
->vrf_id
> next2
->vrf_id
)
116 if (next1
->type
< next2
->type
)
119 if (next1
->type
> next2
->type
)
122 if (next1
->weight
< next2
->weight
)
125 if (next1
->weight
> next2
->weight
)
128 switch (next1
->type
) {
129 case NEXTHOP_TYPE_IPV4
:
130 case NEXTHOP_TYPE_IPV6
:
131 ret
= _nexthop_gateway_cmp(next1
, next2
);
135 case NEXTHOP_TYPE_IPV4_IFINDEX
:
136 case NEXTHOP_TYPE_IPV6_IFINDEX
:
137 ret
= _nexthop_gateway_cmp(next1
, next2
);
140 /* Intentional Fall-Through */
141 case NEXTHOP_TYPE_IFINDEX
:
142 if (next1
->ifindex
< next2
->ifindex
)
145 if (next1
->ifindex
> next2
->ifindex
)
148 case NEXTHOP_TYPE_BLACKHOLE
:
149 if (next1
->bh_type
< next2
->bh_type
)
152 if (next1
->bh_type
> next2
->bh_type
)
157 ret
= _nexthop_source_cmp(next1
, next2
);
162 int nexthop_cmp(const struct nexthop
*next1
, const struct nexthop
*next2
)
166 ret
= _nexthop_cmp_no_labels(next1
, next2
);
170 ret
= _nexthop_labels_cmp(next1
, next2
);
175 int nexthop_same_firsthop(struct nexthop
*next1
, struct nexthop
*next2
)
177 int type1
= NEXTHOP_FIRSTHOPTYPE(next1
->type
);
178 int type2
= NEXTHOP_FIRSTHOPTYPE(next2
->type
);
183 case NEXTHOP_TYPE_IPV4_IFINDEX
:
184 if (!IPV4_ADDR_SAME(&next1
->gate
.ipv4
, &next2
->gate
.ipv4
))
186 if (next1
->ifindex
!= next2
->ifindex
)
189 case NEXTHOP_TYPE_IFINDEX
:
190 if (next1
->ifindex
!= next2
->ifindex
)
193 case NEXTHOP_TYPE_IPV6_IFINDEX
:
194 if (!IPV6_ADDR_SAME(&next1
->gate
.ipv6
, &next2
->gate
.ipv6
))
196 if (next1
->ifindex
!= next2
->ifindex
)
207 * nexthop_type_to_str
209 const char *nexthop_type_to_str(enum nexthop_types_t nh_type
)
211 static const char *const desc
[] = {
212 "none", "Directly connected",
213 "IPv4 nexthop", "IPv4 nexthop with ifindex",
214 "IPv6 nexthop", "IPv6 nexthop with ifindex",
218 return desc
[nh_type
];
222 * Check if the labels match for the 2 nexthops specified.
224 bool nexthop_labels_match(const struct nexthop
*nh1
, const struct nexthop
*nh2
)
226 if (_nexthop_labels_cmp(nh1
, nh2
) != 0)
232 struct nexthop
*nexthop_new(void)
236 nh
= XCALLOC(MTYPE_NEXTHOP
, sizeof(struct nexthop
));
239 * Default the weight to 1 here for all nexthops.
240 * The linux kernel does some weird stuff with adding +1 to
241 * all nexthop weights it gets over netlink.
242 * To handle this, just default everything to 1 right from
243 * from the beggining so we don't have to special case
244 * default weights in the linux netlink code.
246 * 1 should be a valid on all platforms anyway.
254 void nexthop_free(struct nexthop
*nexthop
)
256 nexthop_del_labels(nexthop
);
257 if (nexthop
->resolved
)
258 nexthops_free(nexthop
->resolved
);
259 XFREE(MTYPE_NEXTHOP
, nexthop
);
262 /* Frees a list of nexthops */
263 void nexthops_free(struct nexthop
*nexthop
)
265 struct nexthop
*nh
, *next
;
267 for (nh
= nexthop
; nh
; nh
= next
) {
273 bool nexthop_same(const struct nexthop
*nh1
, const struct nexthop
*nh2
)
284 if (nexthop_cmp(nh1
, nh2
) != 0)
290 bool nexthop_same_no_labels(const struct nexthop
*nh1
,
291 const struct nexthop
*nh2
)
302 if (_nexthop_cmp_no_labels(nh1
, nh2
) != 0)
309 * Allocate a new nexthop object and initialize it from various args.
311 struct nexthop
*nexthop_from_ifindex(ifindex_t ifindex
, vrf_id_t vrf_id
)
313 struct nexthop
*nexthop
;
315 nexthop
= nexthop_new();
316 nexthop
->type
= NEXTHOP_TYPE_IFINDEX
;
317 nexthop
->ifindex
= ifindex
;
318 nexthop
->vrf_id
= vrf_id
;
323 struct nexthop
*nexthop_from_ipv4(const struct in_addr
*ipv4
,
324 const struct in_addr
*src
,
327 struct nexthop
*nexthop
;
329 nexthop
= nexthop_new();
330 nexthop
->type
= NEXTHOP_TYPE_IPV4
;
331 nexthop
->vrf_id
= vrf_id
;
332 nexthop
->gate
.ipv4
= *ipv4
;
334 nexthop
->src
.ipv4
= *src
;
339 struct nexthop
*nexthop_from_ipv4_ifindex(const struct in_addr
*ipv4
,
340 const struct in_addr
*src
,
341 ifindex_t ifindex
, vrf_id_t vrf_id
)
343 struct nexthop
*nexthop
;
345 nexthop
= nexthop_new();
346 nexthop
->type
= NEXTHOP_TYPE_IPV4_IFINDEX
;
347 nexthop
->vrf_id
= vrf_id
;
348 nexthop
->gate
.ipv4
= *ipv4
;
350 nexthop
->src
.ipv4
= *src
;
351 nexthop
->ifindex
= ifindex
;
356 struct nexthop
*nexthop_from_ipv6(const struct in6_addr
*ipv6
,
359 struct nexthop
*nexthop
;
361 nexthop
= nexthop_new();
362 nexthop
->vrf_id
= vrf_id
;
363 nexthop
->type
= NEXTHOP_TYPE_IPV6
;
364 nexthop
->gate
.ipv6
= *ipv6
;
369 struct nexthop
*nexthop_from_ipv6_ifindex(const struct in6_addr
*ipv6
,
370 ifindex_t ifindex
, vrf_id_t vrf_id
)
372 struct nexthop
*nexthop
;
374 nexthop
= nexthop_new();
375 nexthop
->vrf_id
= vrf_id
;
376 nexthop
->type
= NEXTHOP_TYPE_IPV6_IFINDEX
;
377 nexthop
->gate
.ipv6
= *ipv6
;
378 nexthop
->ifindex
= ifindex
;
383 struct nexthop
*nexthop_from_blackhole(enum blackhole_type bh_type
)
385 struct nexthop
*nexthop
;
387 nexthop
= nexthop_new();
388 nexthop
->vrf_id
= VRF_DEFAULT
;
389 nexthop
->type
= NEXTHOP_TYPE_BLACKHOLE
;
390 nexthop
->bh_type
= bh_type
;
395 /* Update nexthop with label information. */
396 void nexthop_add_labels(struct nexthop
*nexthop
, enum lsp_types_t type
,
397 uint8_t num_labels
, mpls_label_t
*label
)
399 struct mpls_label_stack
*nh_label
;
405 nexthop
->nh_label_type
= type
;
406 nh_label
= XCALLOC(MTYPE_NH_LABEL
,
407 sizeof(struct mpls_label_stack
)
408 + num_labels
* sizeof(mpls_label_t
));
409 nh_label
->num_labels
= num_labels
;
410 for (i
= 0; i
< num_labels
; i
++)
411 nh_label
->label
[i
] = *(label
+ i
);
412 nexthop
->nh_label
= nh_label
;
415 /* Free label information of nexthop, if present. */
416 void nexthop_del_labels(struct nexthop
*nexthop
)
418 if (nexthop
->nh_label
) {
419 XFREE(MTYPE_NH_LABEL
, nexthop
->nh_label
);
420 nexthop
->nh_label_type
= ZEBRA_LSP_NONE
;
424 const char *nexthop2str(const struct nexthop
*nexthop
, char *str
, int size
)
426 switch (nexthop
->type
) {
427 case NEXTHOP_TYPE_IFINDEX
:
428 snprintf(str
, size
, "if %u", nexthop
->ifindex
);
430 case NEXTHOP_TYPE_IPV4
:
431 case NEXTHOP_TYPE_IPV4_IFINDEX
:
432 snprintf(str
, size
, "%s if %u", inet_ntoa(nexthop
->gate
.ipv4
),
435 case NEXTHOP_TYPE_IPV6
:
436 case NEXTHOP_TYPE_IPV6_IFINDEX
:
437 snprintf(str
, size
, "%s if %u", inet6_ntoa(nexthop
->gate
.ipv6
),
440 case NEXTHOP_TYPE_BLACKHOLE
:
441 snprintf(str
, size
, "blackhole");
444 snprintf(str
, size
, "unknown");
452 * Iteration step for ALL_NEXTHOPS macro:
453 * This is the tricky part. Check if `nexthop' has
454 * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
455 * at least one nexthop attached to `nexthop->resolved', which will be
458 * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
459 * current chain. In case its current chain end is reached, it will move
460 * upwards in the recursion levels and progress there. Whenever a step
461 * forward in a chain is done, recursion will be checked again.
462 * In a nustshell, it's equivalent to a pre-traversal order assuming that
463 * left branch is 'resolved' and right branch is 'next':
464 * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
466 struct nexthop
*nexthop_next(const struct nexthop
*nexthop
)
468 if (CHECK_FLAG(nexthop
->flags
, NEXTHOP_FLAG_RECURSIVE
))
469 return nexthop
->resolved
;
472 return nexthop
->next
;
474 for (struct nexthop
*par
= nexthop
->rparent
; par
; par
= par
->rparent
)
481 /* Return the next nexthop in the tree that is resolved and active */
482 struct nexthop
*nexthop_next_active_resolved(const struct nexthop
*nexthop
)
484 struct nexthop
*next
= nexthop_next(nexthop
);
487 && (CHECK_FLAG(next
->flags
, NEXTHOP_FLAG_RECURSIVE
)
488 || !CHECK_FLAG(next
->flags
, NEXTHOP_FLAG_ACTIVE
)))
489 next
= nexthop_next(next
);
494 unsigned int nexthop_level(struct nexthop
*nexthop
)
498 for (struct nexthop
*par
= nexthop
->rparent
; par
; par
= par
->rparent
)
504 /* Only hash word-sized things, let cmp do the rest. */
505 uint32_t nexthop_hash_quick(const struct nexthop
*nexthop
)
507 uint32_t key
= 0x45afe398;
509 key
= jhash_3words(nexthop
->type
, nexthop
->vrf_id
,
510 nexthop
->nh_label_type
, key
);
512 if (nexthop
->nh_label
) {
513 int labels
= nexthop
->nh_label
->num_labels
;
516 while (labels
>= 3) {
517 key
= jhash_3words(nexthop
->nh_label
->label
[i
],
518 nexthop
->nh_label
->label
[i
+ 1],
519 nexthop
->nh_label
->label
[i
+ 2],
526 key
= jhash_2words(nexthop
->nh_label
->label
[i
],
527 nexthop
->nh_label
->label
[i
+ 1],
534 key
= jhash_1word(nexthop
->nh_label
->label
[i
], key
);
537 key
= jhash_2words(nexthop
->ifindex
,
538 CHECK_FLAG(nexthop
->flags
, NEXTHOP_FLAG_ONLINK
),
545 #define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
547 /* For a more granular hash */
548 uint32_t nexthop_hash(const struct nexthop
*nexthop
)
550 uint32_t gate_src_rmap_raw
[GATE_SIZE
* 3] = {};
551 /* Get all the quick stuff */
552 uint32_t key
= nexthop_hash_quick(nexthop
);
554 assert(((sizeof(nexthop
->gate
) + sizeof(nexthop
->src
)
555 + sizeof(nexthop
->rmap_src
))
557 == (GATE_SIZE
* sizeof(uint32_t)));
559 memcpy(gate_src_rmap_raw
, &nexthop
->gate
, GATE_SIZE
);
560 memcpy(gate_src_rmap_raw
+ GATE_SIZE
, &nexthop
->src
, GATE_SIZE
);
561 memcpy(gate_src_rmap_raw
+ (2 * GATE_SIZE
), &nexthop
->rmap_src
,
564 key
= jhash2(gate_src_rmap_raw
, (GATE_SIZE
* 3), key
);
569 void nexthop_copy_no_recurse(struct nexthop
*copy
,
570 const struct nexthop
*nexthop
,
571 struct nexthop
*rparent
)
573 copy
->vrf_id
= nexthop
->vrf_id
;
574 copy
->ifindex
= nexthop
->ifindex
;
575 copy
->type
= nexthop
->type
;
576 copy
->flags
= nexthop
->flags
;
577 copy
->weight
= nexthop
->weight
;
578 memcpy(©
->gate
, &nexthop
->gate
, sizeof(nexthop
->gate
));
579 memcpy(©
->src
, &nexthop
->src
, sizeof(nexthop
->src
));
580 memcpy(©
->rmap_src
, &nexthop
->rmap_src
, sizeof(nexthop
->rmap_src
));
581 copy
->rparent
= rparent
;
582 if (nexthop
->nh_label
)
583 nexthop_add_labels(copy
, nexthop
->nh_label_type
,
584 nexthop
->nh_label
->num_labels
,
585 &nexthop
->nh_label
->label
[0]);
588 void nexthop_copy(struct nexthop
*copy
, const struct nexthop
*nexthop
,
589 struct nexthop
*rparent
)
591 nexthop_copy_no_recurse(copy
, nexthop
, rparent
);
593 /* Bit of a special case here, we need to handle the case
594 * of a nexthop resolving to agroup. Hence, we need to
595 * use a nexthop_group API.
597 if (CHECK_FLAG(copy
->flags
, NEXTHOP_FLAG_RECURSIVE
))
598 copy_nexthops(©
->resolved
, nexthop
->resolved
, copy
);
601 struct nexthop
*nexthop_dup_no_recurse(const struct nexthop
*nexthop
,
602 struct nexthop
*rparent
)
604 struct nexthop
*new = nexthop_new();
606 nexthop_copy_no_recurse(new, nexthop
, rparent
);
610 struct nexthop
*nexthop_dup(const struct nexthop
*nexthop
,
611 struct nexthop
*rparent
)
613 struct nexthop
*new = nexthop_new();
615 nexthop_copy(new, nexthop
, rparent
);
620 * nexthop printing variants:
624 * is directly connected, eth0
625 * unreachable (blackhole)
629 * directly connected, eth0
630 * unreachable (blackhole)
634 printfrr_ext_autoreg_p("NH", printfrr_nh
)
635 static ssize_t
printfrr_nh(char *buf
, size_t bsz
, const char *fmt
,
636 int prec
, const void *ptr
)
638 const struct nexthop
*nexthop
= ptr
;
639 struct fbuf fb
= { .buf
= buf
, .pos
= buf
, .len
= bsz
- 1 };
641 const char *s
, *v_is
= "", *v_via
= "", *v_viaif
= "via ";
653 switch (nexthop
->type
) {
654 case NEXTHOP_TYPE_IPV4
:
655 case NEXTHOP_TYPE_IPV4_IFINDEX
:
656 bprintfrr(&fb
, "%s%pI4", v_via
, &nexthop
->gate
.ipv4
);
659 case NEXTHOP_TYPE_IPV6
:
660 case NEXTHOP_TYPE_IPV6_IFINDEX
:
661 bprintfrr(&fb
, "%s%pI6", v_via
, &nexthop
->gate
.ipv6
);
664 case NEXTHOP_TYPE_IFINDEX
:
665 bprintfrr(&fb
, "%sdirectly connected, %s", v_is
,
666 ifindex2ifname(nexthop
->ifindex
,
669 case NEXTHOP_TYPE_BLACKHOLE
:
670 switch (nexthop
->bh_type
) {
671 case BLACKHOLE_REJECT
:
672 s
= " (ICMP unreachable)";
674 case BLACKHOLE_ADMINPROHIB
:
675 s
= " (ICMP admin-prohibited)";
684 bprintfrr(&fb
, "unreachable%s", s
);
689 if (do_ifi
&& nexthop
->ifindex
)
690 bprintfrr(&fb
, ", %s%s", v_viaif
, ifindex2ifname(
697 nexthop2str(nexthop
, buf
, bsz
);