Line data Source code
1 : /* A generic nexthop structure
2 : * Copyright (C) 2013 Cumulus Networks, Inc.
3 : *
4 : * This file is part of Quagga.
5 : *
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
9 : * later version.
10 : *
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.
15 : *
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
19 : */
20 : #include <zebra.h>
21 :
22 : #include "prefix.h"
23 : #include "table.h"
24 : #include "memory.h"
25 : #include "command.h"
26 : #include "log.h"
27 : #include "sockunion.h"
28 : #include "linklist.h"
29 : #include "prefix.h"
30 : #include "nexthop.h"
31 : #include "mpls.h"
32 : #include "jhash.h"
33 : #include "printfrr.h"
34 : #include "vrf.h"
35 : #include "nexthop_group.h"
36 :
37 36 : DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop");
38 36 : DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label");
39 36 : DEFINE_MTYPE_STATIC(LIB, NH_SRV6, "Nexthop srv6");
40 :
41 178 : static int _nexthop_labels_cmp(const struct nexthop *nh1,
42 : const struct nexthop *nh2)
43 : {
44 178 : const struct mpls_label_stack *nhl1 = NULL;
45 178 : const struct mpls_label_stack *nhl2 = NULL;
46 :
47 178 : nhl1 = nh1->nh_label;
48 178 : nhl2 = nh2->nh_label;
49 :
50 : /* No labels is a match */
51 178 : if (!nhl1 && !nhl2)
52 : return 0;
53 :
54 0 : if (nhl1 && !nhl2)
55 : return 1;
56 :
57 0 : if (nhl2 && !nhl1)
58 : return -1;
59 :
60 0 : if (nhl1->num_labels > nhl2->num_labels)
61 : return 1;
62 :
63 0 : if (nhl1->num_labels < nhl2->num_labels)
64 : return -1;
65 :
66 0 : return memcmp(nhl1->label, nhl2->label,
67 0 : (nhl1->num_labels * sizeof(mpls_label_t)));
68 : }
69 :
70 178 : static int _nexthop_srv6_cmp(const struct nexthop *nh1,
71 : const struct nexthop *nh2)
72 : {
73 178 : int ret = 0;
74 :
75 178 : if (!nh1->nh_srv6 && !nh2->nh_srv6)
76 : return 0;
77 :
78 0 : if (nh1->nh_srv6 && !nh2->nh_srv6)
79 : return 1;
80 :
81 0 : if (!nh1->nh_srv6 && nh2->nh_srv6)
82 : return -1;
83 :
84 0 : if (nh1->nh_srv6->seg6local_action > nh2->nh_srv6->seg6local_action)
85 : return 1;
86 :
87 0 : if (nh2->nh_srv6->seg6local_action < nh1->nh_srv6->seg6local_action)
88 : return -1;
89 :
90 0 : ret = memcmp(&nh1->nh_srv6->seg6local_ctx,
91 0 : &nh2->nh_srv6->seg6local_ctx,
92 : sizeof(struct seg6local_context));
93 0 : if (ret != 0)
94 : return ret;
95 :
96 0 : ret = memcmp(&nh1->nh_srv6->seg6_segs,
97 0 : &nh2->nh_srv6->seg6_segs,
98 : sizeof(struct in6_addr));
99 :
100 0 : return ret;
101 : }
102 :
103 178 : int nexthop_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
104 : const union g_addr *addr2)
105 : {
106 178 : int ret = 0;
107 :
108 178 : switch (type) {
109 0 : case NEXTHOP_TYPE_IPV4:
110 : case NEXTHOP_TYPE_IPV4_IFINDEX:
111 0 : ret = IPV4_ADDR_CMP(&addr1->ipv4, &addr2->ipv4);
112 0 : break;
113 0 : case NEXTHOP_TYPE_IPV6:
114 : case NEXTHOP_TYPE_IPV6_IFINDEX:
115 0 : ret = IPV6_ADDR_CMP(&addr1->ipv6, &addr2->ipv6);
116 0 : break;
117 : case NEXTHOP_TYPE_IFINDEX:
118 : case NEXTHOP_TYPE_BLACKHOLE:
119 : /* No addr here */
120 : break;
121 : }
122 :
123 178 : return ret;
124 : }
125 :
126 0 : static int _nexthop_gateway_cmp(const struct nexthop *nh1,
127 : const struct nexthop *nh2)
128 : {
129 0 : return nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
130 : }
131 :
132 178 : static int _nexthop_source_cmp(const struct nexthop *nh1,
133 : const struct nexthop *nh2)
134 : {
135 178 : return nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
136 : }
137 :
138 181 : static int _nexthop_cmp_no_labels(const struct nexthop *next1,
139 : const struct nexthop *next2)
140 : {
141 181 : int ret = 0;
142 :
143 181 : if (next1->vrf_id < next2->vrf_id)
144 : return -1;
145 :
146 181 : if (next1->vrf_id > next2->vrf_id)
147 : return 1;
148 :
149 181 : if (next1->type < next2->type)
150 : return -1;
151 :
152 181 : if (next1->type > next2->type)
153 : return 1;
154 :
155 181 : if (next1->weight < next2->weight)
156 : return -1;
157 :
158 181 : if (next1->weight > next2->weight)
159 : return 1;
160 :
161 181 : switch (next1->type) {
162 : case NEXTHOP_TYPE_IPV4:
163 : case NEXTHOP_TYPE_IPV6:
164 0 : ret = _nexthop_gateway_cmp(next1, next2);
165 0 : if (ret != 0)
166 : return ret;
167 : break;
168 : case NEXTHOP_TYPE_IPV4_IFINDEX:
169 : case NEXTHOP_TYPE_IPV6_IFINDEX:
170 0 : ret = _nexthop_gateway_cmp(next1, next2);
171 0 : if (ret != 0)
172 : return ret;
173 : /* Intentional Fall-Through */
174 : case NEXTHOP_TYPE_IFINDEX:
175 181 : if (next1->ifindex < next2->ifindex)
176 : return -1;
177 :
178 181 : if (next1->ifindex > next2->ifindex)
179 : return 1;
180 : break;
181 0 : case NEXTHOP_TYPE_BLACKHOLE:
182 0 : if (next1->bh_type < next2->bh_type)
183 : return -1;
184 :
185 0 : if (next1->bh_type > next2->bh_type)
186 : return 1;
187 : break;
188 : }
189 :
190 178 : if (next1->srte_color < next2->srte_color)
191 : return -1;
192 178 : if (next1->srte_color > next2->srte_color)
193 : return 1;
194 :
195 178 : ret = _nexthop_source_cmp(next1, next2);
196 178 : if (ret != 0)
197 0 : goto done;
198 :
199 178 : if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
200 178 : !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
201 : return 0;
202 :
203 0 : if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
204 0 : CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
205 : return -1;
206 :
207 0 : if (CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
208 0 : !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
209 : return 1;
210 :
211 0 : if (next1->backup_num == 0 && next2->backup_num == 0)
212 0 : goto done;
213 :
214 0 : if (next1->backup_num < next2->backup_num)
215 : return -1;
216 :
217 0 : if (next1->backup_num > next2->backup_num)
218 : return 1;
219 :
220 0 : ret = memcmp(next1->backup_idx,
221 0 : next2->backup_idx, next1->backup_num);
222 :
223 : done:
224 : return ret;
225 : }
226 :
227 181 : int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
228 : {
229 181 : int ret = 0;
230 :
231 181 : ret = _nexthop_cmp_no_labels(next1, next2);
232 181 : if (ret != 0)
233 : return ret;
234 :
235 178 : ret = _nexthop_labels_cmp(next1, next2);
236 178 : if (ret != 0)
237 : return ret;
238 :
239 178 : ret = _nexthop_srv6_cmp(next1, next2);
240 :
241 178 : return ret;
242 : }
243 :
244 : /*
245 : * More-limited comparison function used to detect duplicate
246 : * nexthops. This is used in places where we don't need the full
247 : * comparison of 'nexthop_cmp()'.
248 : */
249 0 : int nexthop_cmp_basic(const struct nexthop *nh1,
250 : const struct nexthop *nh2)
251 : {
252 0 : int ret = 0;
253 0 : const struct mpls_label_stack *nhl1 = NULL;
254 0 : const struct mpls_label_stack *nhl2 = NULL;
255 :
256 0 : if (nh1 == NULL && nh2 == NULL)
257 : return 0;
258 :
259 0 : if (nh1 && !nh2)
260 : return 1;
261 :
262 0 : if (!nh1 && nh2)
263 : return -1;
264 :
265 0 : if (nh1->vrf_id < nh2->vrf_id)
266 : return -1;
267 :
268 0 : if (nh1->vrf_id > nh2->vrf_id)
269 : return 1;
270 :
271 0 : if (nh1->type < nh2->type)
272 : return -1;
273 :
274 0 : if (nh1->type > nh2->type)
275 : return 1;
276 :
277 0 : if (nh1->weight < nh2->weight)
278 : return -1;
279 :
280 0 : if (nh1->weight > nh2->weight)
281 : return 1;
282 :
283 0 : switch (nh1->type) {
284 0 : case NEXTHOP_TYPE_IPV4:
285 : case NEXTHOP_TYPE_IPV6:
286 0 : ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
287 0 : if (ret != 0)
288 : return ret;
289 : break;
290 0 : case NEXTHOP_TYPE_IPV4_IFINDEX:
291 : case NEXTHOP_TYPE_IPV6_IFINDEX:
292 0 : ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
293 0 : if (ret != 0)
294 : return ret;
295 : /* Intentional Fall-Through */
296 : case NEXTHOP_TYPE_IFINDEX:
297 0 : if (nh1->ifindex < nh2->ifindex)
298 : return -1;
299 :
300 0 : if (nh1->ifindex > nh2->ifindex)
301 : return 1;
302 : break;
303 0 : case NEXTHOP_TYPE_BLACKHOLE:
304 0 : if (nh1->bh_type < nh2->bh_type)
305 : return -1;
306 :
307 0 : if (nh1->bh_type > nh2->bh_type)
308 : return 1;
309 : break;
310 : }
311 :
312 : /* Compare source addr */
313 0 : ret = nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
314 0 : if (ret != 0)
315 0 : goto done;
316 :
317 0 : nhl1 = nh1->nh_label;
318 0 : nhl2 = nh2->nh_label;
319 :
320 : /* No labels is a match */
321 0 : if (!nhl1 && !nhl2)
322 : return 0;
323 :
324 0 : if (nhl1 && !nhl2)
325 : return 1;
326 :
327 0 : if (nhl2 && !nhl1)
328 : return -1;
329 :
330 0 : if (nhl1->num_labels > nhl2->num_labels)
331 : return 1;
332 :
333 0 : if (nhl1->num_labels < nhl2->num_labels)
334 : return -1;
335 :
336 0 : ret = memcmp(nhl1->label, nhl2->label,
337 0 : (nhl1->num_labels * sizeof(mpls_label_t)));
338 :
339 : done:
340 : return ret;
341 : }
342 :
343 : /*
344 : * nexthop_type_to_str
345 : */
346 0 : const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
347 : {
348 0 : static const char *const desc[] = {
349 : "none", "Directly connected",
350 : "IPv4 nexthop", "IPv4 nexthop with ifindex",
351 : "IPv6 nexthop", "IPv6 nexthop with ifindex",
352 : "Null0 nexthop",
353 : };
354 :
355 0 : return desc[nh_type];
356 : }
357 :
358 : /*
359 : * Check if the labels match for the 2 nexthops specified.
360 : */
361 0 : bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
362 : {
363 0 : if (_nexthop_labels_cmp(nh1, nh2) != 0)
364 0 : return false;
365 :
366 : return true;
367 : }
368 :
369 396 : struct nexthop *nexthop_new(void)
370 : {
371 396 : struct nexthop *nh;
372 :
373 396 : nh = XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
374 :
375 : /*
376 : * Default the weight to 1 here for all nexthops.
377 : * The linux kernel does some weird stuff with adding +1 to
378 : * all nexthop weights it gets over netlink.
379 : * To handle this, just default everything to 1 right from
380 : * from the beginning so we don't have to special case
381 : * default weights in the linux netlink code.
382 : *
383 : * 1 should be a valid on all platforms anyway.
384 : */
385 396 : nh->weight = 1;
386 :
387 396 : return nh;
388 : }
389 :
390 : /* Free nexthop. */
391 396 : void nexthop_free(struct nexthop *nexthop)
392 : {
393 396 : nexthop_del_labels(nexthop);
394 396 : nexthop_del_srv6_seg6local(nexthop);
395 396 : nexthop_del_srv6_seg6(nexthop);
396 396 : if (nexthop->resolved)
397 0 : nexthops_free(nexthop->resolved);
398 396 : XFREE(MTYPE_NEXTHOP, nexthop);
399 396 : }
400 :
401 : /* Frees a list of nexthops */
402 560 : void nexthops_free(struct nexthop *nexthop)
403 : {
404 560 : struct nexthop *nh, *next;
405 :
406 956 : for (nh = nexthop; nh; nh = next) {
407 396 : next = nh->next;
408 396 : nexthop_free(nh);
409 : }
410 560 : }
411 :
412 181 : bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2)
413 : {
414 181 : if (nh1 && !nh2)
415 : return false;
416 :
417 181 : if (!nh1 && nh2)
418 : return false;
419 :
420 181 : if (nh1 == nh2)
421 : return true;
422 :
423 181 : if (nexthop_cmp(nh1, nh2) != 0)
424 : return false;
425 :
426 : return true;
427 : }
428 :
429 0 : bool nexthop_same_no_labels(const struct nexthop *nh1,
430 : const struct nexthop *nh2)
431 : {
432 0 : if (nh1 && !nh2)
433 : return false;
434 :
435 0 : if (!nh1 && nh2)
436 : return false;
437 :
438 0 : if (nh1 == nh2)
439 : return true;
440 :
441 0 : if (_nexthop_cmp_no_labels(nh1, nh2) != 0)
442 : return false;
443 :
444 : return true;
445 : }
446 :
447 : /*
448 : * Allocate a new nexthop object and initialize it from various args.
449 : */
450 0 : struct nexthop *nexthop_from_ifindex(ifindex_t ifindex, vrf_id_t vrf_id)
451 : {
452 0 : struct nexthop *nexthop;
453 :
454 0 : nexthop = nexthop_new();
455 0 : nexthop->type = NEXTHOP_TYPE_IFINDEX;
456 0 : nexthop->ifindex = ifindex;
457 0 : nexthop->vrf_id = vrf_id;
458 :
459 0 : return nexthop;
460 : }
461 :
462 0 : struct nexthop *nexthop_from_ipv4(const struct in_addr *ipv4,
463 : const struct in_addr *src,
464 : vrf_id_t vrf_id)
465 : {
466 0 : struct nexthop *nexthop;
467 :
468 0 : nexthop = nexthop_new();
469 0 : nexthop->type = NEXTHOP_TYPE_IPV4;
470 0 : nexthop->vrf_id = vrf_id;
471 0 : nexthop->gate.ipv4 = *ipv4;
472 0 : if (src)
473 0 : nexthop->src.ipv4 = *src;
474 :
475 0 : return nexthop;
476 : }
477 :
478 0 : struct nexthop *nexthop_from_ipv4_ifindex(const struct in_addr *ipv4,
479 : const struct in_addr *src,
480 : ifindex_t ifindex, vrf_id_t vrf_id)
481 : {
482 0 : struct nexthop *nexthop;
483 :
484 0 : nexthop = nexthop_new();
485 0 : nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
486 0 : nexthop->vrf_id = vrf_id;
487 0 : nexthop->gate.ipv4 = *ipv4;
488 0 : if (src)
489 0 : nexthop->src.ipv4 = *src;
490 0 : nexthop->ifindex = ifindex;
491 :
492 0 : return nexthop;
493 : }
494 :
495 0 : struct nexthop *nexthop_from_ipv6(const struct in6_addr *ipv6,
496 : vrf_id_t vrf_id)
497 : {
498 0 : struct nexthop *nexthop;
499 :
500 0 : nexthop = nexthop_new();
501 0 : nexthop->vrf_id = vrf_id;
502 0 : nexthop->type = NEXTHOP_TYPE_IPV6;
503 0 : nexthop->gate.ipv6 = *ipv6;
504 :
505 0 : return nexthop;
506 : }
507 :
508 0 : struct nexthop *nexthop_from_ipv6_ifindex(const struct in6_addr *ipv6,
509 : ifindex_t ifindex, vrf_id_t vrf_id)
510 : {
511 0 : struct nexthop *nexthop;
512 :
513 0 : nexthop = nexthop_new();
514 0 : nexthop->vrf_id = vrf_id;
515 0 : nexthop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
516 0 : nexthop->gate.ipv6 = *ipv6;
517 0 : nexthop->ifindex = ifindex;
518 :
519 0 : return nexthop;
520 : }
521 :
522 0 : struct nexthop *nexthop_from_blackhole(enum blackhole_type bh_type,
523 : vrf_id_t nh_vrf_id)
524 : {
525 0 : struct nexthop *nexthop;
526 :
527 0 : nexthop = nexthop_new();
528 0 : nexthop->vrf_id = nh_vrf_id;
529 0 : nexthop->type = NEXTHOP_TYPE_BLACKHOLE;
530 0 : nexthop->bh_type = bh_type;
531 :
532 0 : return nexthop;
533 : }
534 :
535 : /* Update nexthop with label information. */
536 0 : void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t ltype,
537 : uint8_t num_labels, const mpls_label_t *labels)
538 : {
539 0 : struct mpls_label_stack *nh_label;
540 0 : int i;
541 :
542 0 : if (num_labels == 0)
543 : return;
544 :
545 : /* Enforce limit on label stack size */
546 0 : if (num_labels > MPLS_MAX_LABELS)
547 : num_labels = MPLS_MAX_LABELS;
548 :
549 0 : nexthop->nh_label_type = ltype;
550 :
551 0 : nh_label = XCALLOC(MTYPE_NH_LABEL,
552 : sizeof(struct mpls_label_stack)
553 : + num_labels * sizeof(mpls_label_t));
554 0 : nh_label->num_labels = num_labels;
555 0 : for (i = 0; i < num_labels; i++)
556 0 : nh_label->label[i] = *(labels + i);
557 0 : nexthop->nh_label = nh_label;
558 : }
559 :
560 : /* Free label information of nexthop, if present. */
561 396 : void nexthop_del_labels(struct nexthop *nexthop)
562 : {
563 396 : XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
564 396 : nexthop->nh_label_type = ZEBRA_LSP_NONE;
565 396 : }
566 :
567 0 : void nexthop_add_srv6_seg6local(struct nexthop *nexthop, uint32_t action,
568 : const struct seg6local_context *ctx)
569 : {
570 0 : if (action == ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
571 : return;
572 :
573 0 : if (!nexthop->nh_srv6)
574 0 : nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
575 : sizeof(struct nexthop_srv6));
576 :
577 0 : nexthop->nh_srv6->seg6local_action = action;
578 0 : nexthop->nh_srv6->seg6local_ctx = *ctx;
579 : }
580 :
581 396 : void nexthop_del_srv6_seg6local(struct nexthop *nexthop)
582 : {
583 396 : if (!nexthop->nh_srv6)
584 : return;
585 :
586 0 : nexthop->nh_srv6->seg6local_action = ZEBRA_SEG6_LOCAL_ACTION_UNSPEC;
587 :
588 0 : if (sid_zero(&nexthop->nh_srv6->seg6_segs))
589 0 : XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
590 : }
591 :
592 0 : void nexthop_add_srv6_seg6(struct nexthop *nexthop,
593 : const struct in6_addr *segs)
594 : {
595 0 : if (!segs)
596 : return;
597 :
598 0 : if (!nexthop->nh_srv6)
599 0 : nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
600 : sizeof(struct nexthop_srv6));
601 :
602 0 : nexthop->nh_srv6->seg6_segs = *segs;
603 : }
604 :
605 396 : void nexthop_del_srv6_seg6(struct nexthop *nexthop)
606 : {
607 396 : if (!nexthop->nh_srv6)
608 : return;
609 :
610 0 : memset(&nexthop->nh_srv6->seg6_segs, 0,
611 : sizeof(nexthop->nh_srv6->seg6_segs));
612 :
613 0 : if (nexthop->nh_srv6->seg6local_action ==
614 : ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
615 0 : XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
616 : }
617 :
618 0 : const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
619 : {
620 0 : switch (nexthop->type) {
621 0 : case NEXTHOP_TYPE_IFINDEX:
622 0 : snprintf(str, size, "if %u", nexthop->ifindex);
623 0 : break;
624 0 : case NEXTHOP_TYPE_IPV4:
625 : case NEXTHOP_TYPE_IPV4_IFINDEX:
626 0 : snprintfrr(str, size, "%pI4 if %u", &nexthop->gate.ipv4,
627 0 : nexthop->ifindex);
628 0 : break;
629 0 : case NEXTHOP_TYPE_IPV6:
630 : case NEXTHOP_TYPE_IPV6_IFINDEX:
631 0 : snprintfrr(str, size, "%pI6 if %u", &nexthop->gate.ipv6,
632 0 : nexthop->ifindex);
633 0 : break;
634 0 : case NEXTHOP_TYPE_BLACKHOLE:
635 0 : snprintf(str, size, "blackhole");
636 0 : break;
637 : }
638 :
639 0 : return str;
640 : }
641 :
642 : /*
643 : * Iteration step for ALL_NEXTHOPS macro:
644 : * This is the tricky part. Check if `nexthop' has
645 : * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
646 : * at least one nexthop attached to `nexthop->resolved', which will be
647 : * the next one.
648 : *
649 : * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
650 : * current chain. In case its current chain end is reached, it will move
651 : * upwards in the recursion levels and progress there. Whenever a step
652 : * forward in a chain is done, recursion will be checked again.
653 : * In a nustshell, it's equivalent to a pre-traversal order assuming that
654 : * left branch is 'resolved' and right branch is 'next':
655 : * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
656 : */
657 780 : struct nexthop *nexthop_next(const struct nexthop *nexthop)
658 : {
659 780 : if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
660 0 : return nexthop->resolved;
661 :
662 780 : if (nexthop->next)
663 : return nexthop->next;
664 :
665 780 : for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
666 0 : if (par->next)
667 0 : return par->next;
668 :
669 : return NULL;
670 : }
671 :
672 : /* Return the next nexthop in the tree that is resolved and active */
673 41 : struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop)
674 : {
675 41 : struct nexthop *next = nexthop_next(nexthop);
676 :
677 41 : while (next
678 41 : && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE)
679 : || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE)))
680 0 : next = nexthop_next(next);
681 :
682 41 : return next;
683 : }
684 :
685 0 : unsigned int nexthop_level(const struct nexthop *nexthop)
686 : {
687 0 : unsigned int rv = 0;
688 :
689 0 : for (const struct nexthop *par = nexthop->rparent;
690 0 : par; par = par->rparent)
691 0 : rv++;
692 :
693 0 : return rv;
694 : }
695 :
696 : /* Only hash word-sized things, let cmp do the rest. */
697 296 : uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
698 : {
699 296 : uint32_t key = 0x45afe398;
700 296 : int i;
701 :
702 592 : key = jhash_3words(nexthop->type, nexthop->vrf_id,
703 296 : nexthop->nh_label_type, key);
704 :
705 296 : if (nexthop->nh_label) {
706 0 : int labels = nexthop->nh_label->num_labels;
707 :
708 0 : i = 0;
709 :
710 0 : while (labels >= 3) {
711 0 : key = jhash_3words(nexthop->nh_label->label[i],
712 0 : nexthop->nh_label->label[i + 1],
713 0 : nexthop->nh_label->label[i + 2],
714 : key);
715 0 : labels -= 3;
716 0 : i += 3;
717 : }
718 :
719 0 : if (labels >= 2) {
720 0 : key = jhash_2words(nexthop->nh_label->label[i],
721 0 : nexthop->nh_label->label[i + 1],
722 : key);
723 0 : labels -= 2;
724 0 : i += 2;
725 : }
726 :
727 0 : if (labels >= 1)
728 0 : key = jhash_1word(nexthop->nh_label->label[i], key);
729 : }
730 :
731 592 : key = jhash_2words(nexthop->ifindex,
732 296 : CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK),
733 : key);
734 :
735 : /* Include backup nexthops, if present */
736 296 : if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
737 0 : int backups = nexthop->backup_num;
738 :
739 0 : i = 0;
740 :
741 0 : while (backups >= 3) {
742 0 : key = jhash_3words(nexthop->backup_idx[i],
743 0 : nexthop->backup_idx[i + 1],
744 0 : nexthop->backup_idx[i + 2], key);
745 0 : backups -= 3;
746 0 : i += 3;
747 : }
748 :
749 0 : while (backups >= 2) {
750 0 : key = jhash_2words(nexthop->backup_idx[i],
751 0 : nexthop->backup_idx[i + 1], key);
752 0 : backups -= 2;
753 0 : i += 2;
754 : }
755 :
756 0 : if (backups >= 1)
757 0 : key = jhash_1word(nexthop->backup_idx[i], key);
758 : }
759 :
760 296 : if (nexthop->nh_srv6) {
761 0 : key = jhash_1word(nexthop->nh_srv6->seg6local_action, key);
762 0 : key = jhash(&nexthop->nh_srv6->seg6local_ctx,
763 : sizeof(nexthop->nh_srv6->seg6local_ctx), key);
764 0 : key = jhash(&nexthop->nh_srv6->seg6_segs,
765 : sizeof(nexthop->nh_srv6->seg6_segs), key);
766 : }
767 :
768 296 : return key;
769 : }
770 :
771 :
772 : #define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
773 :
774 : /* For a more granular hash */
775 296 : uint32_t nexthop_hash(const struct nexthop *nexthop)
776 : {
777 296 : uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
778 : /* Get all the quick stuff */
779 296 : uint32_t key = nexthop_hash_quick(nexthop);
780 :
781 296 : assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
782 : + sizeof(nexthop->rmap_src))
783 : / 3)
784 : == (GATE_SIZE * sizeof(uint32_t)));
785 :
786 296 : memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
787 296 : memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
788 296 : memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
789 : GATE_SIZE);
790 :
791 296 : key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key);
792 :
793 296 : return key;
794 : }
795 :
796 396 : void nexthop_copy_no_recurse(struct nexthop *copy,
797 : const struct nexthop *nexthop,
798 : struct nexthop *rparent)
799 : {
800 396 : copy->vrf_id = nexthop->vrf_id;
801 396 : copy->ifindex = nexthop->ifindex;
802 396 : copy->type = nexthop->type;
803 396 : copy->flags = nexthop->flags;
804 396 : copy->weight = nexthop->weight;
805 :
806 396 : assert(nexthop->backup_num < NEXTHOP_MAX_BACKUPS);
807 396 : copy->backup_num = nexthop->backup_num;
808 396 : if (copy->backup_num > 0)
809 0 : memcpy(copy->backup_idx, nexthop->backup_idx, copy->backup_num);
810 :
811 396 : copy->srte_color = nexthop->srte_color;
812 396 : memcpy(©->gate, &nexthop->gate, sizeof(nexthop->gate));
813 396 : memcpy(©->src, &nexthop->src, sizeof(nexthop->src));
814 396 : memcpy(©->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
815 396 : copy->rparent = rparent;
816 396 : if (nexthop->nh_label)
817 0 : nexthop_add_labels(copy, nexthop->nh_label_type,
818 0 : nexthop->nh_label->num_labels,
819 0 : &nexthop->nh_label->label[0]);
820 :
821 396 : if (nexthop->nh_srv6) {
822 0 : if (nexthop->nh_srv6->seg6local_action !=
823 : ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
824 0 : nexthop_add_srv6_seg6local(copy,
825 : nexthop->nh_srv6->seg6local_action,
826 0 : &nexthop->nh_srv6->seg6local_ctx);
827 0 : if (!sid_zero(&nexthop->nh_srv6->seg6_segs))
828 0 : nexthop_add_srv6_seg6(copy,
829 : &nexthop->nh_srv6->seg6_segs);
830 : }
831 396 : }
832 :
833 396 : void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop,
834 : struct nexthop *rparent)
835 : {
836 396 : nexthop_copy_no_recurse(copy, nexthop, rparent);
837 :
838 : /* Bit of a special case here, we need to handle the case
839 : * of a nexthop resolving to a group. Hence, we need to
840 : * use a nexthop_group API.
841 : */
842 396 : if (CHECK_FLAG(copy->flags, NEXTHOP_FLAG_RECURSIVE))
843 0 : copy_nexthops(©->resolved, nexthop->resolved, copy);
844 396 : }
845 :
846 0 : struct nexthop *nexthop_dup_no_recurse(const struct nexthop *nexthop,
847 : struct nexthop *rparent)
848 : {
849 0 : struct nexthop *new = nexthop_new();
850 :
851 0 : nexthop_copy_no_recurse(new, nexthop, rparent);
852 0 : return new;
853 : }
854 :
855 396 : struct nexthop *nexthop_dup(const struct nexthop *nexthop,
856 : struct nexthop *rparent)
857 : {
858 396 : struct nexthop *new = nexthop_new();
859 :
860 396 : nexthop_copy(new, nexthop, rparent);
861 396 : return new;
862 : }
863 :
864 : /*
865 : * Parse one or more backup index values, as comma-separated numbers,
866 : * into caller's array of uint8_ts. The array must be NEXTHOP_MAX_BACKUPS
867 : * in size. Mails back the number of values converted, and returns 0 on
868 : * success, <0 if an error in parsing.
869 : */
870 0 : int nexthop_str2backups(const char *str, int *num_backups,
871 : uint8_t *backups)
872 : {
873 0 : char *ostr; /* copy of string (start) */
874 0 : char *lstr; /* working copy of string */
875 0 : char *nump; /* pointer to next segment */
876 0 : char *endp; /* end pointer */
877 0 : int i, ret;
878 0 : uint8_t tmp[NEXTHOP_MAX_BACKUPS];
879 0 : uint32_t lval;
880 :
881 : /* Copy incoming string; the parse is destructive */
882 0 : lstr = ostr = XSTRDUP(MTYPE_TMP, str);
883 0 : *num_backups = 0;
884 0 : ret = 0;
885 :
886 0 : for (i = 0; i < NEXTHOP_MAX_BACKUPS && lstr; i++) {
887 0 : nump = strsep(&lstr, ",");
888 0 : lval = strtoul(nump, &endp, 10);
889 :
890 : /* Format check */
891 0 : if (*endp != '\0') {
892 : ret = -1;
893 : break;
894 : }
895 :
896 : /* Empty value */
897 0 : if (endp == nump) {
898 : ret = -1;
899 : break;
900 : }
901 :
902 : /* Limit to one octet */
903 0 : if (lval > 255) {
904 : ret = -1;
905 : break;
906 : }
907 :
908 0 : tmp[i] = lval;
909 : }
910 :
911 : /* Excess values */
912 0 : if (ret == 0 && i == NEXTHOP_MAX_BACKUPS && lstr)
913 : ret = -1;
914 :
915 0 : if (ret == 0) {
916 0 : *num_backups = i;
917 0 : memcpy(backups, tmp, i);
918 : }
919 :
920 0 : XFREE(MTYPE_TMP, ostr);
921 :
922 0 : return ret;
923 : }
924 :
925 12 : ssize_t printfrr_nhs(struct fbuf *buf, const struct nexthop *nexthop)
926 : {
927 12 : ssize_t ret = 0;
928 :
929 12 : if (!nexthop)
930 0 : return bputs(buf, "(null)");
931 :
932 12 : switch (nexthop->type) {
933 12 : case NEXTHOP_TYPE_IFINDEX:
934 12 : ret += bprintfrr(buf, "if %u", nexthop->ifindex);
935 12 : break;
936 0 : case NEXTHOP_TYPE_IPV4:
937 : case NEXTHOP_TYPE_IPV4_IFINDEX:
938 0 : ret += bprintfrr(buf, "%pI4 if %u", &nexthop->gate.ipv4,
939 0 : nexthop->ifindex);
940 0 : break;
941 0 : case NEXTHOP_TYPE_IPV6:
942 : case NEXTHOP_TYPE_IPV6_IFINDEX:
943 0 : ret += bprintfrr(buf, "%pI6 if %u", &nexthop->gate.ipv6,
944 0 : nexthop->ifindex);
945 0 : break;
946 0 : case NEXTHOP_TYPE_BLACKHOLE:
947 0 : ret += bputs(buf, "blackhole");
948 0 : break;
949 : }
950 : return ret;
951 : }
952 :
953 : /*
954 : * nexthop printing variants:
955 : * %pNHvv
956 : * via 1.2.3.4
957 : * via 1.2.3.4, eth0
958 : * is directly connected, eth0
959 : * unreachable (blackhole)
960 : * %pNHv
961 : * 1.2.3.4
962 : * 1.2.3.4, via eth0
963 : * directly connected, eth0
964 : * unreachable (blackhole)
965 : * %pNHs
966 : * nexthop2str()
967 : * %pNHcg
968 : * 1.2.3.4
969 : * (0-length if no IP address present)
970 : * %pNHci
971 : * eth0
972 : * (0-length if no interface present)
973 : */
974 12 : printfrr_ext_autoreg_p("NH", printfrr_nh);
975 0 : static ssize_t printfrr_nh(struct fbuf *buf, struct printfrr_eargs *ea,
976 : const void *ptr)
977 : {
978 0 : const struct nexthop *nexthop = ptr;
979 0 : bool do_ifi = false;
980 0 : const char *v_is = "", *v_via = "", *v_viaif = "via ";
981 0 : ssize_t ret = 0;
982 :
983 0 : switch (*ea->fmt) {
984 0 : case 'v':
985 0 : ea->fmt++;
986 0 : if (*ea->fmt == 'v') {
987 0 : v_is = "is ";
988 0 : v_via = "via ";
989 0 : v_viaif = "";
990 0 : ea->fmt++;
991 : }
992 :
993 0 : if (!nexthop)
994 0 : return bputs(buf, "(null)");
995 :
996 0 : switch (nexthop->type) {
997 0 : case NEXTHOP_TYPE_IPV4:
998 : case NEXTHOP_TYPE_IPV4_IFINDEX:
999 0 : ret += bprintfrr(buf, "%s%pI4", v_via,
1000 : &nexthop->gate.ipv4);
1001 0 : do_ifi = true;
1002 0 : break;
1003 0 : case NEXTHOP_TYPE_IPV6:
1004 : case NEXTHOP_TYPE_IPV6_IFINDEX:
1005 0 : ret += bprintfrr(buf, "%s%pI6", v_via,
1006 : &nexthop->gate.ipv6);
1007 0 : do_ifi = true;
1008 0 : break;
1009 0 : case NEXTHOP_TYPE_IFINDEX:
1010 0 : ret += bprintfrr(buf, "%sdirectly connected, %s", v_is,
1011 0 : ifindex2ifname(nexthop->ifindex,
1012 0 : nexthop->vrf_id));
1013 0 : break;
1014 0 : case NEXTHOP_TYPE_BLACKHOLE:
1015 0 : ret += bputs(buf, "unreachable");
1016 :
1017 0 : switch (nexthop->bh_type) {
1018 0 : case BLACKHOLE_REJECT:
1019 0 : ret += bputs(buf, " (ICMP unreachable)");
1020 0 : break;
1021 0 : case BLACKHOLE_ADMINPROHIB:
1022 0 : ret += bputs(buf, " (ICMP admin-prohibited)");
1023 0 : break;
1024 0 : case BLACKHOLE_NULL:
1025 0 : ret += bputs(buf, " (blackhole)");
1026 0 : break;
1027 : case BLACKHOLE_UNSPEC:
1028 : break;
1029 : }
1030 : break;
1031 : }
1032 0 : if (do_ifi && nexthop->ifindex)
1033 0 : ret += bprintfrr(buf, ", %s%s", v_viaif,
1034 : ifindex2ifname(nexthop->ifindex,
1035 0 : nexthop->vrf_id));
1036 :
1037 : return ret;
1038 0 : case 's':
1039 0 : ea->fmt++;
1040 :
1041 0 : ret += printfrr_nhs(buf, nexthop);
1042 0 : return ret;
1043 0 : case 'c':
1044 0 : ea->fmt++;
1045 0 : if (*ea->fmt == 'g') {
1046 0 : ea->fmt++;
1047 0 : if (!nexthop)
1048 0 : return bputs(buf, "(null)");
1049 0 : switch (nexthop->type) {
1050 0 : case NEXTHOP_TYPE_IPV4:
1051 : case NEXTHOP_TYPE_IPV4_IFINDEX:
1052 0 : ret += bprintfrr(buf, "%pI4",
1053 : &nexthop->gate.ipv4);
1054 0 : break;
1055 0 : case NEXTHOP_TYPE_IPV6:
1056 : case NEXTHOP_TYPE_IPV6_IFINDEX:
1057 0 : ret += bprintfrr(buf, "%pI6",
1058 : &nexthop->gate.ipv6);
1059 0 : break;
1060 : case NEXTHOP_TYPE_IFINDEX:
1061 : case NEXTHOP_TYPE_BLACKHOLE:
1062 : break;
1063 : }
1064 0 : } else if (*ea->fmt == 'i') {
1065 0 : ea->fmt++;
1066 0 : if (!nexthop)
1067 0 : return bputs(buf, "(null)");
1068 0 : switch (nexthop->type) {
1069 0 : case NEXTHOP_TYPE_IFINDEX:
1070 0 : ret += bprintfrr(
1071 : buf, "%s",
1072 0 : ifindex2ifname(nexthop->ifindex,
1073 0 : nexthop->vrf_id));
1074 0 : break;
1075 0 : case NEXTHOP_TYPE_IPV4:
1076 : case NEXTHOP_TYPE_IPV4_IFINDEX:
1077 : case NEXTHOP_TYPE_IPV6:
1078 : case NEXTHOP_TYPE_IPV6_IFINDEX:
1079 0 : if (nexthop->ifindex)
1080 0 : ret += bprintfrr(
1081 : buf, "%s",
1082 : ifindex2ifname(
1083 : nexthop->ifindex,
1084 0 : nexthop->vrf_id));
1085 : break;
1086 : case NEXTHOP_TYPE_BLACKHOLE:
1087 : break;
1088 : }
1089 : }
1090 : return ret;
1091 : }
1092 : return -1;
1093 : }
|
