]> git.proxmox.com Git - mirror_frr.git/blame - zebra/zebra_nhg.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
tests: clean up all_proto_startup a bit
[mirror_frr.git] / zebra / zebra_nhg.c
CommitLineData
ad28e79a
SW		 1/* Zebra Nexthop Group Code.
2 * Copyright (C) 2019 Cumulus Networks, Inc.
3 * Donald Sharp
4 * Stephen Worley
5 *
6 * This file is part of FRR.
7 *
8 * FRR is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
11 * later version.
12 *
13 * FRR is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with FRR; see the file COPYING. If not, write to the Free
20 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21 * 02111-1307, USA.
22 */
23#include <zebra.h>
24
25#include "lib/nexthop.h"
50d89650 26#include "lib/nexthop_group_private.h"
ad28e79a 27#include "lib/routemap.h"
b43434ad 28#include "lib/mpls.h"
69171da2 29#include "lib/jhash.h"
51d80884 30#include "lib/debug.h"
31f937fb 31#include "lib/lib_errors.h"
ad28e79a
SW		 32
33#include "zebra/connected.h"
34#include "zebra/debug.h"
35#include "zebra/zebra_router.h"
5948f013 36#include "zebra/zebra_nhg_private.h"
ad28e79a
SW		 37#include "zebra/zebra_rnh.h"
38#include "zebra/zebra_routemap.h"
31f937fb 39#include "zebra/zebra_srte.h"
51d80884 40#include "zebra/zserv.h"
ad28e79a 41#include "zebra/rt.h"
d9f5b2f5 42#include "zebra_errors.h"
0c8215cb 43#include "zebra_dplane.h"
fe593b78 44#include "zebra/interface.h"
ee94437e 45#include "zebra/zapi_msg.h"
d9f5b2f5 46
51d80884 47DEFINE_MTYPE_STATIC(ZEBRA, NHG, "Nexthop Group Entry");
a15d4c00 48DEFINE_MTYPE_STATIC(ZEBRA, NHG_CONNECTED, "Nexthop Group Connected");
e22e8001 49DEFINE_MTYPE_STATIC(ZEBRA, NHG_CTX, "Nexthop Group Context");
0c8215cb 50
5530d55d
MS		 51/* Map backup nexthop indices between two nhes */
52struct backup_nh_map_s {
53 int map_count;
54
55 struct {
56 uint8_t orig_idx;
57 uint8_t new_idx;
58 } map[MULTIPATH_NUM];
59};
60
38e40db1
SW		 61/* id counter to keep in sync with kernel */
62uint32_t id_counter;
63
aa458838 64/* Controlled through ui */
7c99d51b 65static bool g_nexthops_enabled = true;
73937edb 66static bool proto_nexthops_only;
aa458838 67static bool use_recursive_backups = true;
7c99d51b 68
0885b1e3 69static struct nhg_hash_entry *depends_find(const struct nexthop *nh, afi_t afi,
5588801e 70 int type, bool from_dplane);
37c6708b 71static void depends_add(struct nhg_connected_tree_head *head,
5657e7e9 72 struct nhg_hash_entry *depend);
38e40db1
SW		 73static struct nhg_hash_entry *
74depends_find_add(struct nhg_connected_tree_head *head, struct nexthop *nh,
5588801e 75 afi_t afi, int type, bool from_dplane);
38e40db1
SW		 76static struct nhg_hash_entry *
77depends_find_id_add(struct nhg_connected_tree_head *head, uint32_t id);
37c6708b 78static void depends_decrement_free(struct nhg_connected_tree_head *head);
0c8215cb 79
1d48702e
MS		 80static struct nhg_backup_info *
81nhg_backup_copy(const struct nhg_backup_info *orig);
82
ac5d1091 83/* Helper function for getting the next allocatable ID */
73937edb 84static uint32_t nhg_get_next_id(void)
ac5d1091
SW		 85{
86 while (1) {
87 id_counter++;
88
89 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
90 zlog_debug("%s: ID %u checking", __func__, id_counter);
91
92 if (id_counter == ZEBRA_NHG_PROTO_LOWER) {
93 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
94 zlog_debug("%s: ID counter wrapped", __func__);
95
96 id_counter = 0;
97 continue;
98 }
99
100 if (zebra_nhg_lookup_id(id_counter)) {
101 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
102 zlog_debug("%s: ID already exists", __func__);
103
104 continue;
105 }
106
107 break;
108 }
109
110 return id_counter;
111}
e22e8001 112
5948f013 113static void nhg_connected_free(struct nhg_connected *dep)
0c8215cb 114{
a15d4c00 115 XFREE(MTYPE_NHG_CONNECTED, dep);
0c8215cb
SW		 116}
117
5948f013 118static struct nhg_connected *nhg_connected_new(struct nhg_hash_entry *nhe)
0c8215cb 119{
a15d4c00 120 struct nhg_connected *new = NULL;
0c8215cb 121
a15d4c00 122 new = XCALLOC(MTYPE_NHG_CONNECTED, sizeof(struct nhg_connected));
0c8215cb
SW		 123 new->nhe = nhe;
124
125 return new;
126}
127
37c6708b 128void nhg_connected_tree_free(struct nhg_connected_tree_head *head)
0c8215cb 129{
a15d4c00 130 struct nhg_connected *rb_node_dep = NULL;
0c8215cb 131
37c6708b 132 if (!nhg_connected_tree_is_empty(head)) {
fec211ad 133 frr_each_safe(nhg_connected_tree, head, rb_node_dep) {
37c6708b 134 nhg_connected_tree_del(head, rb_node_dep);
fe593b78
SW		 135 nhg_connected_free(rb_node_dep);
136 }
0c8215cb 137 }
0c8215cb
SW		 138}
139
37c6708b 140bool nhg_connected_tree_is_empty(const struct nhg_connected_tree_head *head)
0c8215cb 141{
fec211ad 142 return nhg_connected_tree_count(head) ? false : true;
0c8215cb
SW		 143}
144
98cda54a 145struct nhg_connected *
37c6708b 146nhg_connected_tree_root(struct nhg_connected_tree_head *head)
98cda54a 147{
37c6708b 148 return nhg_connected_tree_first(head);
98cda54a
SW		 149}
150
5bf15faa
SW		 151struct nhg_hash_entry *
152nhg_connected_tree_del_nhe(struct nhg_connected_tree_head *head,
153 struct nhg_hash_entry *depend)
0c8215cb 154{
a15d4c00 155 struct nhg_connected lookup = {};
085304dc 156 struct nhg_connected *remove = NULL;
5bf15faa 157 struct nhg_hash_entry *removed_nhe;
0c8215cb
SW		 158
159 lookup.nhe = depend;
3119f6a1 160
085304dc 161 /* Lookup to find the element, then remove it */
37c6708b 162 remove = nhg_connected_tree_find(head, &lookup);
085304dc 163 if (remove)
5bf15faa
SW		 164 /* Re-returning here just in case this API changes..
165 * the _del list api's are a bit undefined at the moment.
166 *
167 * So hopefully returning here will make it fail if the api
168 * changes to something different than currently expected.
169 */
170 remove = nhg_connected_tree_del(head, remove);
171
172 /* If the entry was sucessfully removed, free the 'connected` struct */
173 if (remove) {
174 removed_nhe = remove->nhe;
085304dc 175 nhg_connected_free(remove);
5bf15faa
SW		 176 return removed_nhe;
177 }
178
179 return NULL;
3119f6a1
SW		 180}
181
5bf15faa
SW		 182/* Assuming UNIQUE RB tree. If this changes, assumptions here about
183 * insertion need to change.
184 */
185struct nhg_hash_entry *
186nhg_connected_tree_add_nhe(struct nhg_connected_tree_head *head,
187 struct nhg_hash_entry *depend)
3119f6a1 188{
a15d4c00 189 struct nhg_connected *new = NULL;
0c8215cb 190
a15d4c00 191 new = nhg_connected_new(depend);
0c8215cb 192
5bf15faa
SW		 193 /* On success, NULL will be returned from the
194 * RB code.
195 */
196 if (new && (nhg_connected_tree_add(head, new) == NULL))
197 return NULL;
198
199 /* If it wasn't successful, it must be a duplicate. We enforce the
200 * unique property for the `nhg_connected` tree.
201 */
202 nhg_connected_free(new);
203
204 return depend;
3119f6a1
SW		 205}
206
37c6708b
SW		 207static void
208nhg_connected_tree_decrement_ref(struct nhg_connected_tree_head *head)
32e29e79
SW		 209{
210 struct nhg_connected *rb_node_dep = NULL;
32e29e79 211
fec211ad 212 frr_each_safe(nhg_connected_tree, head, rb_node_dep) {
32e29e79
SW		 213 zebra_nhg_decrement_ref(rb_node_dep->nhe);
214 }
215}
216
37c6708b
SW		 217static void
218nhg_connected_tree_increment_ref(struct nhg_connected_tree_head *head)
32e29e79
SW		 219{
220 struct nhg_connected *rb_node_dep = NULL;
221
fec211ad 222 frr_each(nhg_connected_tree, head, rb_node_dep) {
32e29e79
SW		 223 zebra_nhg_increment_ref(rb_node_dep->nhe);
224 }
225}
226
98cda54a
SW		 227struct nhg_hash_entry *zebra_nhg_resolve(struct nhg_hash_entry *nhe)
228{
229 if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_RECURSIVE)
230 && !zebra_nhg_depends_is_empty(nhe)) {
37c6708b 231 nhe = nhg_connected_tree_root(&nhe->nhg_depends)->nhe;
98cda54a
SW		 232 return zebra_nhg_resolve(nhe);
233 }
234
235 return nhe;
236}
237
fe593b78 238unsigned int zebra_nhg_depends_count(const struct nhg_hash_entry *nhe)
a15d4c00 239{
37c6708b 240 return nhg_connected_tree_count(&nhe->nhg_depends);
a15d4c00
SW		 241}
242
fe593b78 243bool zebra_nhg_depends_is_empty(const struct nhg_hash_entry *nhe)
a15d4c00 244{
37c6708b 245 return nhg_connected_tree_is_empty(&nhe->nhg_depends);
a15d4c00
SW		 246}
247
5948f013
SW		 248static void zebra_nhg_depends_del(struct nhg_hash_entry *from,
249 struct nhg_hash_entry *depend)
3119f6a1 250{
37c6708b 251 nhg_connected_tree_del_nhe(&from->nhg_depends, depend);
3119f6a1
SW		 252}
253
5948f013 254static void zebra_nhg_depends_init(struct nhg_hash_entry *nhe)
148a0103 255{
37c6708b 256 nhg_connected_tree_init(&nhe->nhg_depends);
148a0103
SW		 257}
258
fe593b78
SW		 259unsigned int zebra_nhg_dependents_count(const struct nhg_hash_entry *nhe)
260{
37c6708b 261 return nhg_connected_tree_count(&nhe->nhg_dependents);
fe593b78
SW		 262}
263
5948f013 264
fe593b78
SW		 265bool zebra_nhg_dependents_is_empty(const struct nhg_hash_entry *nhe)
266{
37c6708b 267 return nhg_connected_tree_is_empty(&nhe->nhg_dependents);
fe593b78
SW		 268}
269
5948f013
SW		 270static void zebra_nhg_dependents_del(struct nhg_hash_entry *from,
271 struct nhg_hash_entry *dependent)
fe593b78 272{
37c6708b 273 nhg_connected_tree_del_nhe(&from->nhg_dependents, dependent);
fe593b78
SW		 274}
275
5948f013
SW		 276static void zebra_nhg_dependents_add(struct nhg_hash_entry *to,
277 struct nhg_hash_entry *dependent)
fe593b78 278{
37c6708b 279 nhg_connected_tree_add_nhe(&to->nhg_dependents, dependent);
fe593b78
SW		 280}
281
5948f013 282static void zebra_nhg_dependents_init(struct nhg_hash_entry *nhe)
fe593b78 283{
37c6708b 284 nhg_connected_tree_init(&nhe->nhg_dependents);
fe593b78
SW		 285}
286
21615102
SW		 287/* Release this nhe from anything depending on it */
288static void zebra_nhg_dependents_release(struct nhg_hash_entry *nhe)
289{
80286aa5 290 struct nhg_connected *rb_node_dep = NULL;
21615102 291
80286aa5
SW		 292 frr_each_safe(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep) {
293 zebra_nhg_depends_del(rb_node_dep->nhe, nhe);
294 /* recheck validity of the dependent */
295 zebra_nhg_check_valid(rb_node_dep->nhe);
21615102
SW		 296 }
297}
298
5948f013
SW		 299/* Release this nhe from anything that it depends on */
300static void zebra_nhg_depends_release(struct nhg_hash_entry *nhe)
301{
302 if (!zebra_nhg_depends_is_empty(nhe)) {
303 struct nhg_connected *rb_node_dep = NULL;
304
305 frr_each_safe(nhg_connected_tree, &nhe->nhg_depends,
306 rb_node_dep) {
307 zebra_nhg_dependents_del(rb_node_dep->nhe, nhe);
308 }
309 }
310}
311
312
d9f5b2f5
SW		 313struct nhg_hash_entry *zebra_nhg_lookup_id(uint32_t id)
314{
0c8215cb 315 struct nhg_hash_entry lookup = {};
d9f5b2f5
SW		 316
317 lookup.id = id;
318 return hash_lookup(zrouter.nhgs_id, &lookup);
319}
320
5948f013 321static int zebra_nhg_insert_id(struct nhg_hash_entry *nhe)
d9f5b2f5
SW		 322{
323 if (hash_lookup(zrouter.nhgs_id, nhe)) {
324 flog_err(
325 EC_ZEBRA_NHG_TABLE_INSERT_FAILED,
326 "Failed inserting NHG id=%u into the ID hash table, entry already exists",
327 nhe->id);
328 return -1;
329 }
330
331 hash_get(zrouter.nhgs_id, nhe, hash_alloc_intern);
332
333 return 0;
334}
ad28e79a 335
5948f013
SW		 336static void zebra_nhg_set_if(struct nhg_hash_entry *nhe, struct interface *ifp)
337{
338 nhe->ifp = ifp;
339 if_nhg_dependents_add(ifp, nhe);
340}
341
38e40db1
SW		 342static void
343zebra_nhg_connect_depends(struct nhg_hash_entry *nhe,
377e29f7 344 struct nhg_connected_tree_head *nhg_depends)
4e49c8b8 345{
a15d4c00
SW		 346 struct nhg_connected *rb_node_dep = NULL;
347
38e40db1
SW		 348 /* This has been allocated higher above in the stack. Could probably
349 * re-allocate and free the old stuff but just using the same memory
350 * for now. Otherwise, their might be a time trade-off for repeated
351 * alloc/frees as startup.
352 */
377e29f7 353 nhe->nhg_depends = *nhg_depends;
4e49c8b8 354
a15d4c00 355 /* Attach backpointer to anything that it depends on */
fe593b78 356 zebra_nhg_dependents_init(nhe);
a15d4c00 357 if (!zebra_nhg_depends_is_empty(nhe)) {
fec211ad 358 frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
377e29f7
MS		 359 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
360 zlog_debug("%s: nhe %p (%u), dep %p (%u)",
361 __func__, nhe, nhe->id,
362 rb_node_dep->nhe,
363 rb_node_dep->nhe->id);
364
a15d4c00
SW		 365 zebra_nhg_dependents_add(rb_node_dep->nhe, nhe);
366 }
367 }
377e29f7 368}
4e49c8b8 369
377e29f7
MS		 370/* Init an nhe, for use in a hash lookup for example */
371void zebra_nhe_init(struct nhg_hash_entry *nhe, afi_t afi,
372 const struct nexthop *nh)
373{
374 memset(nhe, 0, sizeof(struct nhg_hash_entry));
375 nhe->vrf_id = VRF_DEFAULT;
376 nhe->type = ZEBRA_ROUTE_NHG;
377 nhe->afi = AFI_UNSPEC;
7b683a96 378
377e29f7
MS		 379 /* There are some special rules that apply to groups representing
380 * a single nexthop.
381 */
382 if (nh && (nh->next == NULL)) {
383 switch (nh->type) {
9b4ab909
MS		 384 case NEXTHOP_TYPE_IFINDEX:
385 case NEXTHOP_TYPE_BLACKHOLE:
377e29f7
MS		 386 /*
387 * This switch case handles setting the afi different
388 * for ipv4/v6 routes. Ifindex/blackhole nexthop
389 * objects cannot be ambiguous, they must be Address
390 * Family specific. If we get here, we will either use
391 * the AF of the route, or the one we got passed from
392 * here from the kernel.
393 */
394 nhe->afi = afi;
395 break;
9b4ab909
MS		 396 case NEXTHOP_TYPE_IPV4_IFINDEX:
397 case NEXTHOP_TYPE_IPV4:
377e29f7
MS		 398 nhe->afi = AFI_IP;
399 break;
9b4ab909
MS		 400 case NEXTHOP_TYPE_IPV6_IFINDEX:
401 case NEXTHOP_TYPE_IPV6:
377e29f7
MS		 402 nhe->afi = AFI_IP6;
403 break;
404 }
7b683a96 405 }
38e40db1
SW		 406}
407
0eb97b86 408struct nhg_hash_entry *zebra_nhg_alloc(void)
38e40db1
SW		 409{
410 struct nhg_hash_entry *nhe;
411
412 nhe = XCALLOC(MTYPE_NHG, sizeof(struct nhg_hash_entry));
413
0eb97b86
MS		 414 return nhe;
415}
416
f727646a
MS		 417/*
418 * Allocate new nhe and make shallow copy of 'orig'; no
419 * recursive info is copied.
420 */
421struct nhg_hash_entry *zebra_nhe_copy(const struct nhg_hash_entry *orig,
422 uint32_t id)
0eb97b86
MS		 423{
424 struct nhg_hash_entry *nhe;
425
426 nhe = zebra_nhg_alloc();
427
38e40db1
SW		 428 nhe->id = id;
429
1d48702e 430 nexthop_group_copy(&(nhe->nhg), &(orig->nhg));
38e40db1 431
1d48702e
MS		 432 nhe->vrf_id = orig->vrf_id;
433 nhe->afi = orig->afi;
434 nhe->type = orig->type ? orig->type : ZEBRA_ROUTE_NHG;
38e40db1
SW		 435 nhe->refcnt = 0;
436 nhe->dplane_ref = zebra_router_get_next_sequence();
437
1d48702e
MS		 438 /* Copy backup info also, if present */
439 if (orig->backup_info)
440 nhe->backup_info = nhg_backup_copy(orig->backup_info);
441
38e40db1
SW		 442 return nhe;
443}
444
445/* Allocation via hash handler */
446static void *zebra_nhg_hash_alloc(void *arg)
447{
448 struct nhg_hash_entry *nhe = NULL;
449 struct nhg_hash_entry *copy = arg;
7b683a96 450
f727646a 451 nhe = zebra_nhe_copy(copy, copy->id);
9ef49038
SW		 452
453 /* Mark duplicate nexthops in a group at creation time. */
c415d895 454 nexthop_group_mark_duplicates(&(nhe->nhg));
9ef49038 455
bf157b92
SW		 456 /*
457 * Add the ifp now if it's not a group or recursive and has ifindex.
458 *
459 * A proto-owned ID is always a group.
460 */
461 if (!PROTO_OWNED(nhe) && nhe->nhg.nexthop && !nhe->nhg.nexthop->next
462 && !nhe->nhg.nexthop->resolved && nhe->nhg.nexthop->ifindex) {
377e29f7
MS		 463 struct interface *ifp = NULL;
464
465 ifp = if_lookup_by_index(nhe->nhg.nexthop->ifindex,
466 nhe->nhg.nexthop->vrf_id);
467 if (ifp)
468 zebra_nhg_set_if(nhe, ifp);
30672034
SW		 469 else {
470 if (IS_ZEBRA_DEBUG_NHG)
471 zlog_debug(
472 "Failed to lookup an interface with ifindex=%d in vrf=%u for NHE id=%u",
473 nhe->nhg.nexthop->ifindex,
474 nhe->nhg.nexthop->vrf_id, nhe->id);
475 }
377e29f7
MS		 476 }
477
4e49c8b8
DS		 478 return nhe;
479}
480
4e49c8b8
DS		 481uint32_t zebra_nhg_hash_key(const void *arg)
482{
483 const struct nhg_hash_entry *nhe = arg;
0885b1e3
SW		 484 uint32_t key = 0x5a351234;
485 uint32_t primary = 0;
486 uint32_t backup = 0;
487
488 primary = nexthop_group_hash(&(nhe->nhg));
489 if (nhe->backup_info)
490 backup = nexthop_group_hash(&(nhe->backup_info->nhe->nhg));
d9f5b2f5 491
0885b1e3
SW		 492 key = jhash_3words(primary, backup, nhe->type, key);
493
494 key = jhash_2words(nhe->vrf_id, nhe->afi, key);
d9f5b2f5 495
d9f5b2f5 496 return key;
4e49c8b8
DS		 497}
498
a95b8020
SW		 499uint32_t zebra_nhg_id_key(const void *arg)
500{
501 const struct nhg_hash_entry *nhe = arg;
502
503 return nhe->id;
504}
505
1d48702e
MS		 506/* Helper with common nhg/nhe nexthop comparison logic */
507static bool nhg_compare_nexthops(const struct nexthop *nh1,
508 const struct nexthop *nh2)
509{
f924db49 510 assert(nh1 != NULL && nh2 != NULL);
1d48702e
MS		 511
512 /*
513 * We have to check the active flag of each individual one,
514 * not just the overall active_num. This solves the special case
515 * issue of a route with a nexthop group with one nexthop
516 * resolving to itself and thus marking it inactive. If we
517 * have two different routes each wanting to mark a different
518 * nexthop inactive, they need to hash to two different groups.
519 *
520 * If we just hashed on num_active, they would hash the same
521 * which is incorrect.
522 *
523 * ex)
524 * 1.1.1.0/24
525 * -> 1.1.1.1 dummy1 (inactive)
526 * -> 1.1.2.1 dummy2
527 *
528 * 1.1.2.0/24
529 * -> 1.1.1.1 dummy1
530 * -> 1.1.2.1 dummy2 (inactive)
531 *
532 * Without checking each individual one, they would hash to
533 * the same group and both have 1.1.1.1 dummy1 marked inactive.
534 *
535 */
536 if (CHECK_FLAG(nh1->flags, NEXTHOP_FLAG_ACTIVE)
537 != CHECK_FLAG(nh2->flags, NEXTHOP_FLAG_ACTIVE))
538 return false;
539
540 if (!nexthop_same(nh1, nh2))
541 return false;
542
543 return true;
544}
545
4e49c8b8
DS		 546bool zebra_nhg_hash_equal(const void *arg1, const void *arg2)
547{
548 const struct nhg_hash_entry *nhe1 = arg1;
549 const struct nhg_hash_entry *nhe2 = arg2;
148813c2
SW		 550 struct nexthop *nexthop1;
551 struct nexthop *nexthop2;
4e49c8b8 552
98cda54a
SW		 553 /* No matter what if they equal IDs, assume equal */
554 if (nhe1->id && nhe2->id && (nhe1->id == nhe2->id))
555 return true;
556
0885b1e3
SW		 557 if (nhe1->type != nhe2->type)
558 return false;
559
4e49c8b8
DS		 560 if (nhe1->vrf_id != nhe2->vrf_id)
561 return false;
562
77b76fc9
SW		 563 if (nhe1->afi != nhe2->afi)
564 return false;
565
1d48702e 566 /* Nexthops should be in-order, so we simply compare them in-place */
c415d895 567 for (nexthop1 = nhe1->nhg.nexthop, nexthop2 = nhe2->nhg.nexthop;
f924db49 568 nexthop1 && nexthop2;
148813c2 569 nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {
148813c2 570
1d48702e 571 if (!nhg_compare_nexthops(nexthop1, nexthop2))
148813c2 572 return false;
1d48702e 573 }
148813c2 574
f924db49
MS		 575 /* Check for unequal list lengths */
576 if (nexthop1 || nexthop2)
577 return false;
578
1d48702e
MS		 579 /* If there's no backup info, comparison is done. */
580 if ((nhe1->backup_info == NULL) && (nhe2->backup_info == NULL))
581 return true;
582
583 /* Compare backup info also - test the easy things first */
584 if (nhe1->backup_info && (nhe2->backup_info == NULL))
585 return false;
586 if (nhe2->backup_info && (nhe1->backup_info == NULL))
587 return false;
588
589 /* Compare number of backups before actually comparing any */
590 for (nexthop1 = nhe1->backup_info->nhe->nhg.nexthop,
591 nexthop2 = nhe2->backup_info->nhe->nhg.nexthop;
592 nexthop1 && nexthop2;
593 nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {
594 ;
595 }
596
597 /* Did we find the end of one list before the other? */
598 if (nexthop1 || nexthop2)
599 return false;
600
601 /* Have to compare the backup nexthops */
602 for (nexthop1 = nhe1->backup_info->nhe->nhg.nexthop,
603 nexthop2 = nhe2->backup_info->nhe->nhg.nexthop;
f924db49 604 nexthop1 && nexthop2;
1d48702e 605 nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {
148813c2 606
1d48702e 607 if (!nhg_compare_nexthops(nexthop1, nexthop2))
148813c2
SW		 608 return false;
609 }
e4ac313b 610
4e49c8b8
DS		 611 return true;
612}
613
d9f5b2f5 614bool zebra_nhg_hash_id_equal(const void *arg1, const void *arg2)
4e49c8b8 615{
d9f5b2f5
SW		 616 const struct nhg_hash_entry *nhe1 = arg1;
617 const struct nhg_hash_entry *nhe2 = arg2;
4e49c8b8 618
d9f5b2f5
SW		 619 return nhe1->id == nhe2->id;
620}
4e49c8b8 621
1b366e63
SW		 622static int zebra_nhg_process_grp(struct nexthop_group *nhg,
623 struct nhg_connected_tree_head *depends,
624 struct nh_grp *grp, uint8_t count)
e22e8001 625{
37c6708b 626 nhg_connected_tree_init(depends);
e22e8001
SW		 627
628 for (int i = 0; i < count; i++) {
629 struct nhg_hash_entry *depend = NULL;
630 /* We do not care about nexthop_grp.weight at
631 * this time. But we should figure out
632 * how to adapt this to our code in
633 * the future.
634 */
38e40db1 635 depend = depends_find_id_add(depends, grp[i].id);
e22e8001 636
38e40db1 637 if (!depend) {
e22e8001
SW		 638 flog_err(
639 EC_ZEBRA_NHG_SYNC,
640 "Received Nexthop Group from the kernel with a dependent Nexthop ID (%u) which we do not have in our table",
641 grp[i].id);
1b366e63 642 return -1;
e22e8001 643 }
38e40db1
SW		 644
645 /*
646 * If this is a nexthop with its own group
647 * dependencies, add them as well. Not sure its
648 * even possible to have a group within a group
649 * in the kernel.
650 */
651
c415d895 652 copy_nexthops(&nhg->nexthop, depend->nhg.nexthop, NULL);
e22e8001 653 }
1b366e63
SW		 654
655 return 0;
e22e8001
SW		 656}
657
6384cbcb 658static void handle_recursive_depend(struct nhg_connected_tree_head *nhg_depends,
0885b1e3 659 struct nexthop *nh, afi_t afi, int type)
6384cbcb
SW		 660{
661 struct nhg_hash_entry *depend = NULL;
662 struct nexthop_group resolved_ng = {};
663
1d049aba 664 resolved_ng.nexthop = nh;
6384cbcb 665
377e29f7
MS		 666 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
667 zlog_debug("%s: head %p, nh %pNHv",
668 __func__, nhg_depends, nh);
669
0885b1e3 670 depend = zebra_nhg_rib_find(0, &resolved_ng, afi, type);
a7e1b02d 671
377e29f7
MS		 672 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
673 zlog_debug("%s: nh %pNHv => %p (%u)",
674 __func__, nh, depend,
675 depend ? depend->id : 0);
676
a7e1b02d
SW		 677 if (depend)
678 depends_add(nhg_depends, depend);
6384cbcb 679}
e22e8001 680
377e29f7
MS		 681/*
682 * Lookup an nhe in the global hash, using data from another nhe. If 'lookup'
683 * has an id value, that's used. Create a new global/shared nhe if not found.
684 */
685static bool zebra_nhe_find(struct nhg_hash_entry **nhe, /* return value */
686 struct nhg_hash_entry *lookup,
687 struct nhg_connected_tree_head *nhg_depends,
5588801e 688 afi_t afi, bool from_dplane)
377e29f7
MS		 689{
690 bool created = false;
691 bool recursive = false;
0328a5bd 692 struct nhg_hash_entry *newnhe, *backup_nhe;
377e29f7
MS		 693 struct nexthop *nh = NULL;
694
695 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
5588801e
SW		 696 zlog_debug(
697 "%s: id %u, lookup %p, vrf %d, type %d, depends %p%s",
698 __func__, lookup->id, lookup, lookup->vrf_id,
699 lookup->type, nhg_depends,
700 (from_dplane ? " (from dplane)" : ""));
377e29f7
MS		 701
702 if (lookup->id)
703 (*nhe) = zebra_nhg_lookup_id(lookup->id);
704 else
705 (*nhe) = hash_lookup(zrouter.nhgs, lookup);
706
707 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
708 zlog_debug("%s: lookup => %p (%u)",
709 __func__, (*nhe),
710 (*nhe) ? (*nhe)->id : 0);
711
712 /* If we found an existing object, we're done */
713 if (*nhe)
714 goto done;
715
716 /* We're going to create/insert a new nhe:
717 * assign the next global id value if necessary.
718 */
719 if (lookup->id == 0)
ac5d1091 720 lookup->id = nhg_get_next_id();
0885b1e3 721
475852b2 722 if (!from_dplane && lookup->id < ZEBRA_NHG_PROTO_LOWER) {
0885b1e3
SW		 723 /*
724 * This is a zebra hashed/owned NHG.
725 *
726 * It goes in HASH and ID table.
727 */
728 newnhe = hash_get(zrouter.nhgs, lookup, zebra_nhg_hash_alloc);
729 zebra_nhg_insert_id(newnhe);
730 } else {
731 /*
475852b2
SW		 732 * This is upperproto owned NHG or one we read in from dataplane
733 * and should not be hashed to.
0885b1e3
SW		 734 *
735 * It goes in ID table.
736 */
737 newnhe =
738 hash_get(zrouter.nhgs_id, lookup, zebra_nhg_hash_alloc);
739 }
740
377e29f7
MS		 741 created = true;
742
743 /* Mail back the new object */
744 *nhe = newnhe;
745
746 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
747 zlog_debug("%s: => created %p (%u)", __func__, newnhe,
748 newnhe->id);
749
750 /* Only hash/lookup the depends if the first lookup
751 * fails to find something. This should hopefully save a
752 * lot of cycles for larger ecmp sizes.
753 */
754 if (nhg_depends) {
755 /* If you don't want to hash on each nexthop in the
756 * nexthop group struct you can pass the depends
757 * directly. Kernel-side we do this since it just looks
758 * them up via IDs.
759 */
760 zebra_nhg_connect_depends(newnhe, nhg_depends);
761 goto done;
762 }
763
764 /* Prepare dependency relationships if this is not a
765 * singleton nexthop. There are two cases: a single
766 * recursive nexthop, where we need a relationship to the
767 * resolving nexthop; or a group of nexthops, where we need
768 * relationships with the corresponding singletons.
769 */
84591282 770 zebra_nhg_depends_init(newnhe);
377e29f7
MS		 771
772 nh = newnhe->nhg.nexthop;
773
774 if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_ACTIVE))
775 SET_FLAG(newnhe->flags, NEXTHOP_GROUP_VALID);
776
54c89c93 777 if (nh->next == NULL && newnhe->id < ZEBRA_NHG_PROTO_LOWER) {
377e29f7
MS		 778 if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE)) {
779 /* Single recursive nexthop */
780 handle_recursive_depend(&newnhe->nhg_depends,
0885b1e3
SW		 781 nh->resolved, afi,
782 newnhe->type);
377e29f7
MS		 783 recursive = true;
784 }
785 } else {
dd1e105f 786 /* Proto-owned are groups by default */
377e29f7
MS		 787 /* List of nexthops */
788 for (nh = newnhe->nhg.nexthop; nh; nh = nh->next) {
789 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
790 zlog_debug("%s: depends NH %pNHv %s",
791 __func__, nh,
792 CHECK_FLAG(nh->flags,
793 NEXTHOP_FLAG_RECURSIVE) ?
794 "(R)" : "");
795
0885b1e3 796 depends_find_add(&newnhe->nhg_depends, nh, afi,
5588801e 797 newnhe->type, from_dplane);
377e29f7
MS		 798 }
799 }
800
0328a5bd 801 if (recursive)
84591282
SW		 802 SET_FLAG(newnhe->flags, NEXTHOP_GROUP_RECURSIVE);
803
804 /* Attach dependent backpointers to singletons */
805 zebra_nhg_connect_depends(newnhe, &newnhe->nhg_depends);
806
807 /**
808 * Backup Nexthops
809 */
0328a5bd 810
377e29f7
MS		 811 if (zebra_nhg_get_backup_nhg(newnhe) == NULL ||
812 zebra_nhg_get_backup_nhg(newnhe)->nexthop == NULL)
0328a5bd
MS		 813 goto done;
814
815 /* If there are backup nexthops, add them to the backup
816 * depends tree. The rules here are a little different.
817 */
818 recursive = false;
819 backup_nhe = newnhe->backup_info->nhe;
377e29f7 820
0328a5bd 821 nh = backup_nhe->nhg.nexthop;
377e29f7
MS		 822
823 /* Singleton recursive NH */
824 if (nh->next == NULL &&
825 CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE)) {
826 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
827 zlog_debug("%s: backup depend NH %pNHv (R)",
828 __func__, nh);
829
830 /* Single recursive nexthop */
0885b1e3
SW		 831 handle_recursive_depend(&backup_nhe->nhg_depends, nh->resolved,
832 afi, backup_nhe->type);
377e29f7
MS		 833 recursive = true;
834 } else {
835 /* One or more backup NHs */
836 for (; nh; nh = nh->next) {
837 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
838 zlog_debug("%s: backup depend NH %pNHv %s",
839 __func__, nh,
840 CHECK_FLAG(nh->flags,
841 NEXTHOP_FLAG_RECURSIVE) ?
842 "(R)" : "");
843
0885b1e3 844 depends_find_add(&backup_nhe->nhg_depends, nh, afi,
5588801e 845 backup_nhe->type, from_dplane);
377e29f7
MS		 846 }
847 }
848
377e29f7 849 if (recursive)
0328a5bd 850 SET_FLAG(backup_nhe->flags, NEXTHOP_GROUP_RECURSIVE);
377e29f7
MS		 851
852done:
45691de9
SW		 853 /* Reset time since last update */
854 (*nhe)->uptime = monotime(NULL);
377e29f7
MS		 855
856 return created;
857}
858
859/*
860 * Lookup or create an nhe, based on an nhg or an nhe id.
861 */
4505578b
SW		 862static bool zebra_nhg_find(struct nhg_hash_entry **nhe, uint32_t id,
863 struct nexthop_group *nhg,
37c6708b 864 struct nhg_connected_tree_head *nhg_depends,
5588801e
SW		 865 vrf_id_t vrf_id, afi_t afi, int type,
866 bool from_dplane)
a95b8020 867{
0c8215cb 868 struct nhg_hash_entry lookup = {};
4505578b
SW		 869 bool created = false;
870
1d48702e
MS		 871 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
872 zlog_debug("%s: id %u, nhg %p, vrf %d, type %d, depends %p",
873 __func__, id, nhg, vrf_id, type,
874 nhg_depends);
875
377e29f7
MS		 876 /* Use a temporary nhe and call into the superset/common code */
877 lookup.id = id;
9a1588c4 878 lookup.type = type ? type : ZEBRA_ROUTE_NHG;
c415d895 879 lookup.nhg = *nhg;
e22e8001 880
88cafda7 881 lookup.vrf_id = vrf_id;
475852b2 882 if (nhg_depends || lookup.nhg.nexthop->next) {
6384cbcb
SW		 883 /* Groups can have all vrfs and AF's in them */
884 lookup.afi = AFI_UNSPEC;
6384cbcb 885 } else {
c415d895 886 switch (lookup.nhg.nexthop->type) {
4d21c7c0
SW		 887 case (NEXTHOP_TYPE_IFINDEX):
888 case (NEXTHOP_TYPE_BLACKHOLE):
889 /*
890 * This switch case handles setting the afi different
891 * for ipv4/v6 routes. Ifindex/blackhole nexthop
892 * objects cannot be ambiguous, they must be Address
893 * Family specific. If we get here, we will either use
894 * the AF of the route, or the one we got passed from
895 * here from the kernel.
896 */
897 lookup.afi = afi;
898 break;
899 case (NEXTHOP_TYPE_IPV4_IFINDEX):
900 case (NEXTHOP_TYPE_IPV4):
901 lookup.afi = AFI_IP;
902 break;
903 case (NEXTHOP_TYPE_IPV6_IFINDEX):
904 case (NEXTHOP_TYPE_IPV6):
905 lookup.afi = AFI_IP6;
906 break;
907 }
6384cbcb 908 }
a95b8020 909
5588801e 910 created = zebra_nhe_find(nhe, &lookup, nhg_depends, afi, from_dplane);
d9f5b2f5 911
4505578b 912 return created;
a95b8020
SW		 913}
914
e22e8001 915/* Find/create a single nexthop */
5588801e
SW		 916static struct nhg_hash_entry *zebra_nhg_find_nexthop(uint32_t id,
917 struct nexthop *nh,
918 afi_t afi, int type,
919 bool from_dplane)
3057df51 920{
6384cbcb 921 struct nhg_hash_entry *nhe = NULL;
e22e8001 922 struct nexthop_group nhg = {};
88cafda7 923 vrf_id_t vrf_id = !vrf_is_backend_netns() ? VRF_DEFAULT : nh->vrf_id;
e22e8001 924
0eb97b86 925 nexthop_group_add_sorted(&nhg, nh);
e22e8001 926
5588801e 927 zebra_nhg_find(&nhe, id, &nhg, NULL, vrf_id, afi, type, from_dplane);
8a507796 928
377e29f7
MS		 929 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
930 zlog_debug("%s: nh %pNHv => %p (%u)",
931 __func__, nh, nhe, nhe ? nhe->id : 0);
932
6384cbcb 933 return nhe;
e22e8001
SW		 934}
935
10200d40
SW		 936static uint32_t nhg_ctx_get_id(const struct nhg_ctx *ctx)
937{
938 return ctx->id;
939}
940
1b366e63 941static void nhg_ctx_set_status(struct nhg_ctx *ctx, enum nhg_ctx_status status)
e22e8001
SW		 942{
943 ctx->status = status;
944}
945
1b366e63 946static enum nhg_ctx_status nhg_ctx_get_status(const struct nhg_ctx *ctx)
e22e8001
SW		 947{
948 return ctx->status;
949}
950
951static void nhg_ctx_set_op(struct nhg_ctx *ctx, enum nhg_ctx_op_e op)
952{
953 ctx->op = op;
954}
955
956static enum nhg_ctx_op_e nhg_ctx_get_op(const struct nhg_ctx *ctx)
957{
958 return ctx->op;
959}
960
10200d40
SW		 961static vrf_id_t nhg_ctx_get_vrf_id(const struct nhg_ctx *ctx)
962{
963 return ctx->vrf_id;
964}
965
966static int nhg_ctx_get_type(const struct nhg_ctx *ctx)
967{
968 return ctx->type;
969}
970
971static int nhg_ctx_get_afi(const struct nhg_ctx *ctx)
972{
973 return ctx->afi;
974}
975
976static struct nexthop *nhg_ctx_get_nh(struct nhg_ctx *ctx)
977{
978 return &ctx->u.nh;
979}
980
981static uint8_t nhg_ctx_get_count(const struct nhg_ctx *ctx)
982{
983 return ctx->count;
984}
985
986static struct nh_grp *nhg_ctx_get_grp(struct nhg_ctx *ctx)
987{
988 return ctx->u.grp;
989}
990
99e7ab12 991static struct nhg_ctx *nhg_ctx_new(void)
7c6d5f25 992{
99e7ab12 993 struct nhg_ctx *new;
7c6d5f25
SW		 994
995 new = XCALLOC(MTYPE_NHG_CTX, sizeof(struct nhg_ctx));
996
997 return new;
998}
999
04bec7b2 1000void nhg_ctx_free(struct nhg_ctx **ctx)
7c6d5f25
SW		 1001{
1002 struct nexthop *nh;
1003
1004 if (ctx == NULL)
1005 return;
1006
1007 assert((*ctx) != NULL);
1008
1009 if (nhg_ctx_get_count(*ctx))
1010 goto done;
1011
1012 nh = nhg_ctx_get_nh(*ctx);
1013
1014 nexthop_del_labels(nh);
eab0f8f0
HS		 1015 nexthop_del_srv6_seg6local(nh);
1016 nexthop_del_srv6_seg6(nh);
7c6d5f25
SW		 1017
1018done:
1019 XFREE(MTYPE_NHG_CTX, *ctx);
7c6d5f25
SW		 1020}
1021
81505946
SW		 1022static struct nhg_ctx *nhg_ctx_init(uint32_t id, struct nexthop *nh,
1023 struct nh_grp *grp, vrf_id_t vrf_id,
1024 afi_t afi, int type, uint8_t count)
1025{
1026 struct nhg_ctx *ctx = NULL;
1027
1028 ctx = nhg_ctx_new();
1029
1030 ctx->id = id;
1031 ctx->vrf_id = vrf_id;
1032 ctx->afi = afi;
1033 ctx->type = type;
1034 ctx->count = count;
1035
1036 if (count)
1037 /* Copy over the array */
1038 memcpy(&ctx->u.grp, grp, count * sizeof(struct nh_grp));
1039 else if (nh)
1040 ctx->u.nh = *nh;
1041
1042 return ctx;
1043}
1044
80286aa5
SW		 1045static void zebra_nhg_set_valid(struct nhg_hash_entry *nhe)
1046{
1047 struct nhg_connected *rb_node_dep;
1048
1049 SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
1050
1051 frr_each(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
1052 zebra_nhg_set_valid(rb_node_dep->nhe);
1053}
1054
1055static void zebra_nhg_set_invalid(struct nhg_hash_entry *nhe)
1056{
1057 struct nhg_connected *rb_node_dep;
1058
1059 UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
1060
1061 /* Update validity of nexthops depending on it */
1062 frr_each(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
1063 zebra_nhg_check_valid(rb_node_dep->nhe);
1064}
1065
1066void zebra_nhg_check_valid(struct nhg_hash_entry *nhe)
1067{
1068 struct nhg_connected *rb_node_dep = NULL;
1069 bool valid = false;
1070
1071 /* If anthing else in the group is valid, the group is valid */
1072 frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
1073 if (CHECK_FLAG(rb_node_dep->nhe->flags, NEXTHOP_GROUP_VALID)) {
1074 valid = true;
1075 goto done;
1076 }
1077 }
1078
1079done:
1080 if (valid)
1081 zebra_nhg_set_valid(nhe);
1082 else
1083 zebra_nhg_set_invalid(nhe);
1084}
1085
dd1e105f 1086static void zebra_nhg_release_all_deps(struct nhg_hash_entry *nhe)
9a1588c4
SW		 1087{
1088 /* Remove it from any lists it may be on */
1089 zebra_nhg_depends_release(nhe);
1090 zebra_nhg_dependents_release(nhe);
1091 if (nhe->ifp)
1092 if_nhg_dependents_del(nhe->ifp, nhe);
dd1e105f
SW		 1093}
1094
1095static void zebra_nhg_release(struct nhg_hash_entry *nhe)
1096{
1097 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1098 zlog_debug("%s: nhe %p (%u)", __func__, nhe, nhe->id);
1099
1100 zebra_nhg_release_all_deps(nhe);
9a1588c4
SW		 1101
1102 /*
0885b1e3 1103 * If its not zebra owned, we didn't store it here and have to be
9a1588c4
SW		 1104 * sure we don't clear one thats actually being used.
1105 */
3bccc0f5 1106 if (nhe->id < ZEBRA_NHG_PROTO_LOWER)
9a1588c4 1107 hash_release(zrouter.nhgs, nhe);
9a1588c4 1108
9a1588c4
SW		 1109 hash_release(zrouter.nhgs_id, nhe);
1110}
1111
9a1588c4
SW		 1112static void zebra_nhg_handle_uninstall(struct nhg_hash_entry *nhe)
1113{
177e711d 1114 zebra_nhg_release(nhe);
9a1588c4
SW		 1115 zebra_nhg_free(nhe);
1116}
1117
80286aa5
SW		 1118static void zebra_nhg_handle_install(struct nhg_hash_entry *nhe)
1119{
1120 /* Update validity of groups depending on it */
1121 struct nhg_connected *rb_node_dep;
1122
1123 frr_each_safe(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
1124 zebra_nhg_set_valid(rb_node_dep->nhe);
1125}
1126
9a1588c4
SW		 1127/*
1128 * The kernel/other program has changed the state of a nexthop object we are
1129 * using.
1130 */
1131static void zebra_nhg_handle_kernel_state_change(struct nhg_hash_entry *nhe,
1132 bool is_delete)
1133{
1134 if (nhe->refcnt) {
1135 flog_err(
1136 EC_ZEBRA_NHG_SYNC,
1137 "Kernel %s a nexthop group with ID (%u) that we are still using for a route, sending it back down",
1138 (is_delete ? "deleted" : "updated"), nhe->id);
1139
1140 UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
1141 zebra_nhg_install_kernel(nhe);
177e711d 1142 } else
9a1588c4 1143 zebra_nhg_handle_uninstall(nhe);
9a1588c4
SW		 1144}
1145
e22e8001
SW		 1146static int nhg_ctx_process_new(struct nhg_ctx *ctx)
1147{
1148 struct nexthop_group *nhg = NULL;
37c6708b 1149 struct nhg_connected_tree_head nhg_depends = {};
9a1588c4 1150 struct nhg_hash_entry *lookup = NULL;
3057df51
SW		 1151 struct nhg_hash_entry *nhe = NULL;
1152
10200d40
SW		 1153 uint32_t id = nhg_ctx_get_id(ctx);
1154 uint8_t count = nhg_ctx_get_count(ctx);
1155 vrf_id_t vrf_id = nhg_ctx_get_vrf_id(ctx);
1156 int type = nhg_ctx_get_type(ctx);
1157 afi_t afi = nhg_ctx_get_afi(ctx);
1158
1159 lookup = zebra_nhg_lookup_id(id);
9a1588c4 1160
377e29f7
MS		 1161 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1162 zlog_debug("%s: id %u, count %d, lookup => %p",
1163 __func__, id, count, lookup);
1164
9a1588c4
SW		 1165 if (lookup) {
1166 /* This is already present in our table, hence an update
1167 * that we did not initate.
1168 */
1169 zebra_nhg_handle_kernel_state_change(lookup, false);
1170 return 0;
1171 }
1172
10200d40 1173 if (nhg_ctx_get_count(ctx)) {
e22e8001 1174 nhg = nexthop_group_new();
1b366e63
SW		 1175 if (zebra_nhg_process_grp(nhg, &nhg_depends,
1176 nhg_ctx_get_grp(ctx), count)) {
1177 depends_decrement_free(&nhg_depends);
d3a35138 1178 nexthop_group_delete(&nhg);
fec211ad 1179 return -ENOENT;
1b366e63
SW		 1180 }
1181
0885b1e3 1182 if (!zebra_nhg_find(&nhe, id, nhg, &nhg_depends, vrf_id, afi,
5588801e 1183 type, true))
38e40db1 1184 depends_decrement_free(&nhg_depends);
4505578b 1185
e22e8001 1186 /* These got copied over in zebra_nhg_alloc() */
d3a35138 1187 nexthop_group_delete(&nhg);
38e40db1 1188 } else
5588801e
SW		 1189 nhe = zebra_nhg_find_nexthop(id, nhg_ctx_get_nh(ctx), afi, type,
1190 true);
e22e8001 1191
5b27c09d 1192 if (!nhe) {
e22e8001
SW		 1193 flog_err(
1194 EC_ZEBRA_TABLE_LOOKUP_FAILED,
1195 "Zebra failed to find or create a nexthop hash entry for ID (%u)",
10200d40 1196 id);
e22e8001
SW		 1197 return -1;
1198 }
1199
5b27c09d
SW		 1200 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1201 zlog_debug("%s: nhe %p (%u) is new", __func__, nhe, nhe->id);
1202
dc65cd99
SW		 1203 /*
1204 * If daemon nhg from the kernel, add a refcnt here to indicate the
1205 * daemon owns it.
1206 */
1207 if (PROTO_OWNED(nhe))
1208 zebra_nhg_increment_ref(nhe);
1209
5b27c09d
SW		 1210 SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
1211 SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
1212
e22e8001
SW		 1213 return 0;
1214}
1215
9a1588c4
SW		 1216static int nhg_ctx_process_del(struct nhg_ctx *ctx)
1217{
1218 struct nhg_hash_entry *nhe = NULL;
10200d40 1219 uint32_t id = nhg_ctx_get_id(ctx);
9a1588c4 1220
10200d40 1221 nhe = zebra_nhg_lookup_id(id);
9a1588c4
SW		 1222
1223 if (!nhe) {
1224 flog_warn(
1225 EC_ZEBRA_BAD_NHG_MESSAGE,
1226 "Kernel delete message received for nexthop group ID (%u) that we do not have in our ID table",
10200d40 1227 id);
81505946 1228 return -1;
9a1588c4
SW		 1229 }
1230
1231 zebra_nhg_handle_kernel_state_change(nhe, true);
1232
1233 return 0;
1234}
1235
7c6d5f25 1236static void nhg_ctx_fini(struct nhg_ctx **ctx)
e22e8001
SW		 1237{
1238 /*
1239 * Just freeing for now, maybe do something more in the future
1240 * based on flag.
1241 */
1242
7134ba70 1243 nhg_ctx_free(ctx);
e22e8001
SW		 1244}
1245
1b366e63
SW		 1246static int queue_add(struct nhg_ctx *ctx)
1247{
1248 /* If its queued or already processed do nothing */
1249 if (nhg_ctx_get_status(ctx) == NHG_CTX_QUEUED)
1250 return 0;
1251
04bec7b2 1252 if (rib_queue_nhg_ctx_add(ctx)) {
1b366e63
SW		 1253 nhg_ctx_set_status(ctx, NHG_CTX_FAILURE);
1254 return -1;
1255 }
1256
1257 nhg_ctx_set_status(ctx, NHG_CTX_QUEUED);
1258
1259 return 0;
1260}
1261
e22e8001
SW		 1262int nhg_ctx_process(struct nhg_ctx *ctx)
1263{
1264 int ret = 0;
1265
1266 switch (nhg_ctx_get_op(ctx)) {
1267 case NHG_CTX_OP_NEW:
1268 ret = nhg_ctx_process_new(ctx);
fec211ad 1269 if (nhg_ctx_get_count(ctx) && ret == -ENOENT
1b366e63 1270 && nhg_ctx_get_status(ctx) != NHG_CTX_REQUEUED) {
e1292378
SW		 1271 /**
1272 * We have entered a situation where we are
1273 * processing a group from the kernel
1274 * that has a contained nexthop which
1275 * we have not yet processed.
1b366e63 1276 *
e1292378
SW		 1277 * Re-enqueue this ctx to be handled exactly one
1278 * more time (indicated by the flag).
1279 *
1280 * By the time we get back to it, we
1281 * should have processed its depends.
1b366e63
SW		 1282 */
1283 nhg_ctx_set_status(ctx, NHG_CTX_NONE);
1284 if (queue_add(ctx) == 0) {
1285 nhg_ctx_set_status(ctx, NHG_CTX_REQUEUED);
1286 return 0;
1287 }
1288 }
e22e8001
SW		 1289 break;
1290 case NHG_CTX_OP_DEL:
9a1588c4 1291 ret = nhg_ctx_process_del(ctx);
e22e8001
SW		 1292 case NHG_CTX_OP_NONE:
1293 break;
1294 }
1295
1296 nhg_ctx_set_status(ctx, (ret ? NHG_CTX_FAILURE : NHG_CTX_SUCCESS));
1297
7c6d5f25 1298 nhg_ctx_fini(&ctx);
e22e8001
SW		 1299
1300 return ret;
1301}
3057df51 1302
e22e8001
SW		 1303/* Kernel-side, you either get a single new nexthop or a array of ID's */
1304int zebra_nhg_kernel_find(uint32_t id, struct nexthop *nh, struct nh_grp *grp,
38e40db1
SW		 1305 uint8_t count, vrf_id_t vrf_id, afi_t afi, int type,
1306 int startup)
e22e8001 1307{
e22e8001
SW		 1308 struct nhg_ctx *ctx = NULL;
1309
377e29f7
MS		 1310 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1311 zlog_debug("%s: nh %pNHv, id %u, count %d",
1312 __func__, nh, id, (int)count);
1313
54c89c93 1314 if (id > id_counter && id < ZEBRA_NHG_PROTO_LOWER)
38e40db1
SW		 1315 /* Increase our counter so we don't try to create
1316 * an ID that already exists
1317 */
1318 id_counter = id;
1319
81505946 1320 ctx = nhg_ctx_init(id, nh, grp, vrf_id, afi, type, count);
e22e8001
SW		 1321 nhg_ctx_set_op(ctx, NHG_CTX_OP_NEW);
1322
38e40db1
SW		 1323 /* Under statup conditions, we need to handle them immediately
1324 * like we do for routes. Otherwise, we are going to get a route
1325 * with a nhe_id that we have not handled.
1326 */
1327 if (startup)
1328 return nhg_ctx_process(ctx);
1329
e22e8001 1330 if (queue_add(ctx)) {
7c6d5f25 1331 nhg_ctx_fini(&ctx);
e22e8001
SW		 1332 return -1;
1333 }
1334
1335 return 0;
1336}
1337
9a1588c4 1338/* Kernel-side, received delete message */
88cafda7 1339int zebra_nhg_kernel_del(uint32_t id, vrf_id_t vrf_id)
9a1588c4
SW		 1340{
1341 struct nhg_ctx *ctx = NULL;
1342
88cafda7 1343 ctx = nhg_ctx_init(id, NULL, NULL, vrf_id, 0, 0, 0);
9a1588c4
SW		 1344
1345 nhg_ctx_set_op(ctx, NHG_CTX_OP_DEL);
1346
1347 if (queue_add(ctx)) {
7c6d5f25 1348 nhg_ctx_fini(&ctx);
9a1588c4
SW		 1349 return -1;
1350 }
1351
1352 return 0;
1353}
1354
5657e7e9 1355/* Some dependency helper functions */
0fff714e 1356static struct nhg_hash_entry *depends_find_recursive(const struct nexthop *nh,
0885b1e3 1357 afi_t afi, int type)
98cda54a 1358{
0fff714e
SW		 1359 struct nhg_hash_entry *nhe;
1360 struct nexthop *lookup = NULL;
98cda54a 1361
77bf9504 1362 lookup = nexthop_dup(nh, NULL);
0fff714e 1363
5588801e 1364 nhe = zebra_nhg_find_nexthop(0, lookup, afi, type, false);
0fff714e
SW		 1365
1366 nexthops_free(lookup);
1367
1368 return nhe;
1369}
1370
1371static struct nhg_hash_entry *depends_find_singleton(const struct nexthop *nh,
5588801e
SW		 1372 afi_t afi, int type,
1373 bool from_dplane)
0fff714e
SW		 1374{
1375 struct nhg_hash_entry *nhe;
1376 struct nexthop lookup = {};
606fa9e5 1377
cb86eba3
MS		 1378 /* Capture a snapshot of this single nh; it might be part of a list,
1379 * so we need to make a standalone copy.
1380 */
77bf9504 1381 nexthop_copy_no_recurse(&lookup, nh, NULL);
8a507796 1382
5588801e 1383 nhe = zebra_nhg_find_nexthop(0, &lookup, afi, type, from_dplane);
8a507796 1384
cb86eba3
MS		 1385 /* The copy may have allocated labels; free them if necessary. */
1386 nexthop_del_labels(&lookup);
eab0f8f0
HS		 1387 nexthop_del_srv6_seg6local(&lookup);
1388 nexthop_del_srv6_seg6(&lookup);
4505578b 1389
377e29f7
MS		 1390 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1391 zlog_debug("%s: nh %pNHv => %p (%u)",
1392 __func__, nh, nhe, nhe ? nhe->id : 0);
1393
0fff714e
SW		 1394 return nhe;
1395}
1396
0885b1e3 1397static struct nhg_hash_entry *depends_find(const struct nexthop *nh, afi_t afi,
5588801e 1398 int type, bool from_dplane)
0fff714e
SW		 1399{
1400 struct nhg_hash_entry *nhe = NULL;
1401
1402 if (!nh)
1403 goto done;
1404
1405 /* We are separating these functions out to increase handling speed
1406 * in the non-recursive case (by not alloc/freeing)
1407 */
bed74d17 1408 if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE))
0885b1e3 1409 nhe = depends_find_recursive(nh, afi, type);
bed74d17 1410 else
5588801e 1411 nhe = depends_find_singleton(nh, afi, type, from_dplane);
377e29f7 1412
bed74d17
DS		 1413
1414 if (IS_ZEBRA_DEBUG_NHG_DETAIL) {
1415 zlog_debug("%s: nh %pNHv %s => %p (%u)", __func__, nh,
1416 CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE) ? "(R)"
1417 : "",
377e29f7 1418 nhe, nhe ? nhe->id : 0);
bed74d17 1419 }
0fff714e 1420
606fa9e5 1421done:
4505578b 1422 return nhe;
98cda54a
SW		 1423}
1424
37c6708b 1425static void depends_add(struct nhg_connected_tree_head *head,
5657e7e9
SW		 1426 struct nhg_hash_entry *depend)
1427{
377e29f7
MS		 1428 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1429 zlog_debug("%s: head %p nh %pNHv",
1430 __func__, head, depend->nhg.nexthop);
1431
5bf15faa
SW		 1432 /* If NULL is returned, it was successfully added and
1433 * needs to have its refcnt incremented.
1434 *
1435 * Else the NHE is already present in the tree and doesn't
1436 * need to increment the refcnt.
1437 */
1438 if (nhg_connected_tree_add_nhe(head, depend) == NULL)
1439 zebra_nhg_increment_ref(depend);
5657e7e9
SW		 1440}
1441
38e40db1
SW		 1442static struct nhg_hash_entry *
1443depends_find_add(struct nhg_connected_tree_head *head, struct nexthop *nh,
5588801e 1444 afi_t afi, int type, bool from_dplane)
5657e7e9
SW		 1445{
1446 struct nhg_hash_entry *depend = NULL;
1447
5588801e 1448 depend = depends_find(nh, afi, type, from_dplane);
1b366e63 1449
1d48702e
MS		 1450 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1451 zlog_debug("%s: nh %pNHv => %p",
1452 __func__, nh, depend);
1453
1b366e63
SW		 1454 if (depend)
1455 depends_add(head, depend);
38e40db1
SW		 1456
1457 return depend;
1458}
1459
1460static struct nhg_hash_entry *
1461depends_find_id_add(struct nhg_connected_tree_head *head, uint32_t id)
1462{
1463 struct nhg_hash_entry *depend = NULL;
1464
1465 depend = zebra_nhg_lookup_id(id);
1b366e63
SW		 1466
1467 if (depend)
1468 depends_add(head, depend);
38e40db1
SW		 1469
1470 return depend;
5657e7e9
SW		 1471}
1472
37c6708b 1473static void depends_decrement_free(struct nhg_connected_tree_head *head)
5657e7e9 1474{
37c6708b
SW		 1475 nhg_connected_tree_decrement_ref(head);
1476 nhg_connected_tree_free(head);
5657e7e9
SW		 1477}
1478
377e29f7 1479/* Find an nhe based on a list of nexthops */
0885b1e3
SW		 1480struct nhg_hash_entry *zebra_nhg_rib_find(uint32_t id,
1481 struct nexthop_group *nhg,
1482 afi_t rt_afi, int type)
e22e8001
SW		 1483{
1484 struct nhg_hash_entry *nhe = NULL;
88cafda7
DS		 1485 vrf_id_t vrf_id;
1486
1487 /*
1488 * CLANG SA is complaining that nexthop may be NULL
1489 * Make it happy but this is ridonc
1490 */
1491 assert(nhg->nexthop);
1492 vrf_id = !vrf_is_backend_netns() ? VRF_DEFAULT : nhg->nexthop->vrf_id;
98cda54a 1493
5588801e 1494 zebra_nhg_find(&nhe, id, nhg, NULL, vrf_id, rt_afi, type, false);
4505578b 1495
377e29f7
MS		 1496 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1497 zlog_debug("%s: => nhe %p (%u)",
1498 __func__, nhe, nhe ? nhe->id : 0);
1499
1500 return nhe;
1501}
1502
1503/* Find an nhe based on a route's nhe */
1504struct nhg_hash_entry *
1505zebra_nhg_rib_find_nhe(struct nhg_hash_entry *rt_nhe, afi_t rt_afi)
1506{
1507 struct nhg_hash_entry *nhe = NULL;
1508
1509 if (!(rt_nhe && rt_nhe->nhg.nexthop)) {
1510 flog_err(EC_ZEBRA_TABLE_LOOKUP_FAILED,
1511 "No nexthop passed to %s", __func__);
1512 return NULL;
1513 }
1514
1515 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
f924db49 1516 zlog_debug("%s: rt_nhe %p (%u)", __func__, rt_nhe, rt_nhe->id);
377e29f7 1517
5588801e 1518 zebra_nhe_find(&nhe, rt_nhe, NULL, rt_afi, false);
377e29f7
MS		 1519
1520 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1521 zlog_debug("%s: => nhe %p (%u)",
1522 __func__, nhe, nhe ? nhe->id : 0);
1523
3057df51
SW		 1524 return nhe;
1525}
1526
1d48702e
MS		 1527/*
1528 * Allocate backup nexthop info object. Typically these are embedded in
1529 * nhg_hash_entry objects.
1530 */
1531struct nhg_backup_info *zebra_nhg_backup_alloc(void)
1532{
1533 struct nhg_backup_info *p;
1534
1535 p = XCALLOC(MTYPE_NHG, sizeof(struct nhg_backup_info));
1536
1537 p->nhe = zebra_nhg_alloc();
1538
1539 /* Identify the embedded group used to hold the list of backups */
1540 SET_FLAG(p->nhe->flags, NEXTHOP_GROUP_BACKUP);
1541
1542 return p;
1543}
1544
1545/*
1546 * Free backup nexthop info object, deal with any embedded allocations
1547 */
1548void zebra_nhg_backup_free(struct nhg_backup_info **p)
1549{
1550 if (p && *p) {
1551 if ((*p)->nhe)
1552 zebra_nhg_free((*p)->nhe);
1553
1554 XFREE(MTYPE_NHG, (*p));
1555 }
1556}
1557
1d48702e
MS		 1558/* Accessor for backup nexthop group */
1559struct nexthop_group *zebra_nhg_get_backup_nhg(struct nhg_hash_entry *nhe)
1560{
1561 struct nexthop_group *p = NULL;
1562
1563 if (nhe) {
1564 if (nhe->backup_info && nhe->backup_info->nhe)
1565 p = &(nhe->backup_info->nhe->nhg);
1566 }
1567
1568 return p;
1569}
1570
1571/*
1572 * Helper to return a copy of a backup_info - note that this is a shallow
1573 * copy, meant to be used when creating a new nhe from info passed in with
1574 * a route e.g.
1575 */
1576static struct nhg_backup_info *
1577nhg_backup_copy(const struct nhg_backup_info *orig)
1578{
1579 struct nhg_backup_info *b;
1580
1581 b = zebra_nhg_backup_alloc();
1582
1583 /* Copy list of nexthops */
1584 nexthop_group_copy(&(b->nhe->nhg), &(orig->nhe->nhg));
1585
1586 return b;
1587}
1588
5948f013 1589static void zebra_nhg_free_members(struct nhg_hash_entry *nhe)
b599cd2a 1590{
c415d895
MS		 1591 nexthops_free(nhe->nhg.nexthop);
1592
1d48702e
MS		 1593 zebra_nhg_backup_free(&nhe->backup_info);
1594
58396544 1595 /* Decrement to remove connection ref */
37c6708b
SW		 1596 nhg_connected_tree_decrement_ref(&nhe->nhg_depends);
1597 nhg_connected_tree_free(&nhe->nhg_depends);
1598 nhg_connected_tree_free(&nhe->nhg_dependents);
b599cd2a
SW		 1599}
1600
0eb97b86 1601void zebra_nhg_free(struct nhg_hash_entry *nhe)
a95b8020 1602{
377e29f7
MS		 1603 if (IS_ZEBRA_DEBUG_NHG_DETAIL) {
1604 /* Group or singleton? */
1605 if (nhe->nhg.nexthop && nhe->nhg.nexthop->next)
1606 zlog_debug("%s: nhe %p (%u), refcnt %d",
f924db49 1607 __func__, nhe, nhe->id, nhe->refcnt);
377e29f7
MS		 1608 else
1609 zlog_debug("%s: nhe %p (%u), refcnt %d, NH %pNHv",
f924db49 1610 __func__, nhe, nhe->id, nhe->refcnt,
377e29f7
MS		 1611 nhe->nhg.nexthop);
1612 }
1613
38e40db1
SW		 1614 if (nhe->refcnt)
1615 zlog_debug("nhe_id=%u hash refcnt=%d", nhe->id, nhe->refcnt);
1616
8e401b25 1617 zebra_nhg_free_members(nhe);
51d80884
SW		 1618
1619 XFREE(MTYPE_NHG, nhe);
a95b8020
SW		 1620}
1621
0eb97b86
MS		 1622void zebra_nhg_hash_free(void *p)
1623{
84591282 1624 zebra_nhg_release_all_deps((struct nhg_hash_entry *)p);
0eb97b86
MS		 1625 zebra_nhg_free((struct nhg_hash_entry *)p);
1626}
1627
d9f5b2f5
SW		 1628void zebra_nhg_decrement_ref(struct nhg_hash_entry *nhe)
1629{
377e29f7
MS		 1630 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1631 zlog_debug("%s: nhe %p (%u) %d => %d",
1632 __func__, nhe, nhe->id, nhe->refcnt,
1633 nhe->refcnt - 1);
1634
e22e8001
SW		 1635 nhe->refcnt--;
1636
32e29e79 1637 if (!zebra_nhg_depends_is_empty(nhe))
37c6708b 1638 nhg_connected_tree_decrement_ref(&nhe->nhg_depends);
f54ef6a5 1639
38e40db1 1640 if (ZEBRA_NHG_CREATED(nhe) && nhe->refcnt <= 0)
cb50cbc9 1641 zebra_nhg_uninstall_kernel(nhe);
7fd392cc
SW		 1642}
1643
7fd392cc
SW		 1644void zebra_nhg_increment_ref(struct nhg_hash_entry *nhe)
1645{
377e29f7
MS		 1646 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
1647 zlog_debug("%s: nhe %p (%u) %d => %d",
1648 __func__, nhe, nhe->id, nhe->refcnt,
1649 nhe->refcnt + 1);
1650
e22e8001
SW		 1651 nhe->refcnt++;
1652
32e29e79 1653 if (!zebra_nhg_depends_is_empty(nhe))
37c6708b 1654 nhg_connected_tree_increment_ref(&nhe->nhg_depends);
e22e8001 1655}
d9f5b2f5 1656
5530d55d
MS		 1657static struct nexthop *nexthop_set_resolved(afi_t afi,
1658 const struct nexthop *newhop,
1659 struct nexthop *nexthop,
1660 struct zebra_sr_policy *policy)
ad28e79a
SW		 1661{
1662 struct nexthop *resolved_hop;
b43434ad
SW		 1663 uint8_t num_labels = 0;
1664 mpls_label_t labels[MPLS_MAX_LABELS];
1665 enum lsp_types_t label_type = ZEBRA_LSP_NONE;
1666 int i = 0;
ad28e79a
SW		 1667
1668 resolved_hop = nexthop_new();
1669 SET_FLAG(resolved_hop->flags, NEXTHOP_FLAG_ACTIVE);
1670
1671 resolved_hop->vrf_id = nexthop->vrf_id;
1672 switch (newhop->type) {
1673 case NEXTHOP_TYPE_IPV4:
1674 case NEXTHOP_TYPE_IPV4_IFINDEX:
1675 /* If the resolving route specifies a gateway, use it */
1676 resolved_hop->type = newhop->type;
1677 resolved_hop->gate.ipv4 = newhop->gate.ipv4;
1678
1679 if (newhop->ifindex) {
1680 resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
1681 resolved_hop->ifindex = newhop->ifindex;
1682 }
1683 break;
1684 case NEXTHOP_TYPE_IPV6:
1685 case NEXTHOP_TYPE_IPV6_IFINDEX:
1686 resolved_hop->type = newhop->type;
1687 resolved_hop->gate.ipv6 = newhop->gate.ipv6;
1688
1689 if (newhop->ifindex) {
1690 resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
1691 resolved_hop->ifindex = newhop->ifindex;
1692 }
1693 break;
1694 case NEXTHOP_TYPE_IFINDEX:
1695 /* If the resolving route is an interface route,
1696 * it means the gateway we are looking up is connected
1697 * to that interface. (The actual network is _not_ onlink).
1698 * Therefore, the resolved route should have the original
1699 * gateway as nexthop as it is directly connected.
1700 *
1701 * On Linux, we have to set the onlink netlink flag because
1702 * otherwise, the kernel won't accept the route.
1703 */
1704 resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;
1705 if (afi == AFI_IP) {
1706 resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
1707 resolved_hop->gate.ipv4 = nexthop->gate.ipv4;
1708 } else if (afi == AFI_IP6) {
1709 resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
1710 resolved_hop->gate.ipv6 = nexthop->gate.ipv6;
1711 }
1712 resolved_hop->ifindex = newhop->ifindex;
1713 break;
1714 case NEXTHOP_TYPE_BLACKHOLE:
1715 resolved_hop->type = NEXTHOP_TYPE_BLACKHOLE;
2dc359a6 1716 resolved_hop->bh_type = newhop->bh_type;
ad28e79a
SW		 1717 break;
1718 }
1719
1720 if (newhop->flags & NEXTHOP_FLAG_ONLINK)
1721 resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;
1722
b43434ad 1723 /* Copy labels of the resolved route and the parent resolving to it */
31f937fb
SM		 1724 if (policy) {
1725 int i = 0;
1726
1727 /*
1728 * Don't push the first SID if the corresponding action in the
1729 * LFIB is POP.
1730 */
1731 if (!newhop->nh_label || !newhop->nh_label->num_labels
1732 || newhop->nh_label->label[0] == MPLS_LABEL_IMPLICIT_NULL)
1733 i = 1;
1734
1735 for (; i < policy->segment_list.label_num; i++)
1736 labels[num_labels++] = policy->segment_list.labels[i];
1737 label_type = policy->segment_list.type;
1738 } else if (newhop->nh_label) {
6bc5d977
MS		 1739 for (i = 0; i < newhop->nh_label->num_labels; i++) {
1740 /* Be a bit picky about overrunning the local array */
1741 if (num_labels >= MPLS_MAX_LABELS) {
1742 if (IS_ZEBRA_DEBUG_NHG || IS_ZEBRA_DEBUG_RIB)
1743 zlog_debug("%s: too many labels in newhop %pNHv",
1744 __func__, newhop);
1745 break;
1746 }
b43434ad 1747 labels[num_labels++] = newhop->nh_label->label[i];
6bc5d977
MS		 1748 }
1749 /* Use the "outer" type */
b43434ad
SW		 1750 label_type = newhop->nh_label_type;
1751 }
1752
1753 if (nexthop->nh_label) {
6bc5d977
MS		 1754 for (i = 0; i < nexthop->nh_label->num_labels; i++) {
1755 /* Be a bit picky about overrunning the local array */
1756 if (num_labels >= MPLS_MAX_LABELS) {
1757 if (IS_ZEBRA_DEBUG_NHG || IS_ZEBRA_DEBUG_RIB)
1758 zlog_debug("%s: too many labels in nexthop %pNHv",
1759 __func__, nexthop);
1760 break;
1761 }
b43434ad 1762 labels[num_labels++] = nexthop->nh_label->label[i];
6bc5d977 1763 }
b43434ad 1764
6bc5d977
MS		 1765 /* If the parent has labels, use its type if
1766 * we don't already have one.
1767 */
1768 if (label_type == ZEBRA_LSP_NONE)
1769 label_type = nexthop->nh_label_type;
b43434ad
SW		 1770 }
1771
1772 if (num_labels)
1773 nexthop_add_labels(resolved_hop, label_type, num_labels,
1774 labels);
ad28e79a 1775
24b3c59c
RS		 1776 if (nexthop->nh_srv6) {
1777 nexthop_add_srv6_seg6local(resolved_hop,
1778 nexthop->nh_srv6->seg6local_action,
1779 &nexthop->nh_srv6->seg6local_ctx);
1780 nexthop_add_srv6_seg6(resolved_hop,
1781 &nexthop->nh_srv6->seg6_segs);
1782 }
1783
ad28e79a 1784 resolved_hop->rparent = nexthop;
50d89650 1785 _nexthop_add(&nexthop->resolved, resolved_hop);
5530d55d
MS		 1786
1787 return resolved_hop;
ad28e79a
SW		 1788}
1789
6913cb1b
SW		 1790/* Checks if nexthop we are trying to resolve to is valid */
1791static bool nexthop_valid_resolve(const struct nexthop *nexthop,
1792 const struct nexthop *resolved)
1793{
1794 /* Can't resolve to a recursive nexthop */
1795 if (CHECK_FLAG(resolved->flags, NEXTHOP_FLAG_RECURSIVE))
1796 return false;
1797
9d43854d
MS		 1798 /* Must be ACTIVE */
1799 if (!CHECK_FLAG(resolved->flags, NEXTHOP_FLAG_ACTIVE))
1800 return false;
1801
3d30f6de
SW		 1802 /* Must not be duplicate */
1803 if (CHECK_FLAG(resolved->flags, NEXTHOP_FLAG_DUPLICATE))
1804 return false;
1805
6913cb1b
SW		 1806 switch (nexthop->type) {
1807 case NEXTHOP_TYPE_IPV4_IFINDEX:
1808 case NEXTHOP_TYPE_IPV6_IFINDEX:
1809 /* If the nexthop we are resolving to does not match the
1810 * ifindex for the nexthop the route wanted, its not valid.
1811 */
1812 if (nexthop->ifindex != resolved->ifindex)
1813 return false;
1814 break;
1815 case NEXTHOP_TYPE_IPV4:
1816 case NEXTHOP_TYPE_IPV6:
1817 case NEXTHOP_TYPE_IFINDEX:
1818 case NEXTHOP_TYPE_BLACKHOLE:
1819 break;
1820 }
1821
1822 return true;
1823}
1824
ad28e79a 1825/*
5530d55d
MS		 1826 * When resolving a recursive nexthop, capture backup nexthop(s) also
1827 * so they can be conveyed through the dataplane to the FIB. We'll look
1828 * at the backups in the resolving nh 'nexthop' and its nhe, and copy them
1829 * into the route's resolved nh 'resolved' and its nhe 'nhe'.
1830 */
1831static int resolve_backup_nexthops(const struct nexthop *nexthop,
1832 const struct nhg_hash_entry *nhe,
1833 struct nexthop *resolved,
1834 struct nhg_hash_entry *resolve_nhe,
1835 struct backup_nh_map_s *map)
1836{
1837 int i, j, idx;
1838 const struct nexthop *bnh;
1839 struct nexthop *nh, *newnh;
a082cd9a
MS		 1840 mpls_label_t labels[MPLS_MAX_LABELS];
1841 uint8_t num_labels;
5530d55d
MS		 1842
1843 assert(nexthop->backup_num <= NEXTHOP_MAX_BACKUPS);
1844
5530d55d
MS		 1845 /* Locate backups from the original nexthop's backup index and nhe */
1846 for (i = 0; i < nexthop->backup_num; i++) {
1847 idx = nexthop->backup_idx[i];
1848
1849 /* Do we already know about this particular backup? */
1850 for (j = 0; j < map->map_count; j++) {
1851 if (map->map[j].orig_idx == idx)
1852 break;
1853 }
1854
1855 if (j < map->map_count) {
1856 resolved->backup_idx[resolved->backup_num] =
1857 map->map[j].new_idx;
1858 resolved->backup_num++;
1859
c56c16eb
MS		 1860 SET_FLAG(resolved->flags, NEXTHOP_FLAG_HAS_BACKUP);
1861
5530d55d
MS		 1862 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1863 zlog_debug("%s: found map idx orig %d, new %d",
1864 __func__, map->map[j].orig_idx,
1865 map->map[j].new_idx);
1866
1867 continue;
1868 }
1869
1870 /* We can't handle any new map entries at this point. */
1871 if (map->map_count == MULTIPATH_NUM)
1872 break;
1873
1874 /* Need to create/copy a new backup */
1875 bnh = nhe->backup_info->nhe->nhg.nexthop;
1876 for (j = 0; j < idx; j++) {
1877 if (bnh == NULL)
1878 break;
1879 bnh = bnh->next;
1880 }
1881
1882 /* Whoops - bad index in the nexthop? */
1883 if (bnh == NULL)
1884 continue;
1885
c56c16eb
MS		 1886 if (resolve_nhe->backup_info == NULL)
1887 resolve_nhe->backup_info = zebra_nhg_backup_alloc();
1888
5530d55d
MS		 1889 /* Update backup info in the resolving nexthop and its nhe */
1890 newnh = nexthop_dup_no_recurse(bnh, NULL);
1891
a082cd9a
MS		 1892 /* We may need some special handling for mpls labels: the new
1893 * backup needs to carry the recursive nexthop's labels,
1894 * if any: they may be vrf labels e.g.
1895 * The original/inner labels are in the stack of 'resolve_nhe',
1896 * if that is longer than the stack in 'nexthop'.
1897 */
1898 if (newnh->nh_label && resolved->nh_label &&
1899 nexthop->nh_label) {
1900 if (resolved->nh_label->num_labels >
1901 nexthop->nh_label->num_labels) {
1902 /* Prepare new label stack */
1903 num_labels = 0;
1904 for (j = 0; j < newnh->nh_label->num_labels;
1905 j++) {
1906 labels[j] = newnh->nh_label->label[j];
1907 num_labels++;
1908 }
1909
1910 /* Include inner labels */
1911 for (j = nexthop->nh_label->num_labels;
1912 j < resolved->nh_label->num_labels;
1913 j++) {
1914 labels[num_labels] =
1915 resolved->nh_label->label[j];
1916 num_labels++;
1917 }
1918
1919 /* Replace existing label stack in the backup */
1920 nexthop_del_labels(newnh);
1921 nexthop_add_labels(newnh, bnh->nh_label_type,
1922 num_labels, labels);
1923 }
1924 }
1925
5530d55d
MS		 1926 /* Need to compute the new backup index in the new
1927 * backup list, and add to map struct.
1928 */
1929 j = 0;
1930 nh = resolve_nhe->backup_info->nhe->nhg.nexthop;
1931 if (nh) {
1932 while (nh->next) {
1933 nh = nh->next;
1934 j++;
1935 }
1936
1937 nh->next = newnh;
c56c16eb 1938 j++;
5530d55d
MS		 1939
1940 } else /* First one */
1941 resolve_nhe->backup_info->nhe->nhg.nexthop = newnh;
1942
1943 /* Capture index */
1944 resolved->backup_idx[resolved->backup_num] = j;
1945 resolved->backup_num++;
1946
c56c16eb
MS		 1947 SET_FLAG(resolved->flags, NEXTHOP_FLAG_HAS_BACKUP);
1948
5530d55d
MS		 1949 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
1950 zlog_debug("%s: added idx orig %d, new %d",
1951 __func__, idx, j);
1952
1953 /* Update map/cache */
1954 map->map[map->map_count].orig_idx = idx;
1955 map->map[map->map_count].new_idx = j;
1956 map->map_count++;
1957 }
1958
1959 return 0;
1960}
1961
1962/*
1963 * Given a nexthop we need to properly recursively resolve,
1964 * do a table lookup to find and match if at all possible.
1965 * Set the nexthop->ifindex and resolution info as appropriate.
ad28e79a 1966 */
5530d55d 1967static int nexthop_active(struct nexthop *nexthop, struct nhg_hash_entry *nhe,
9b4ab909
MS		 1968 const struct prefix *top, int type, uint32_t flags,
1969 uint32_t *pmtu)
ad28e79a
SW		 1970{
1971 struct prefix p;
1972 struct route_table *table;
1973 struct route_node *rn;
1974 struct route_entry *match = NULL;
1975 int resolved;
f2595bd5 1976 struct zebra_nhlfe *nhlfe;
ad28e79a
SW		 1977 struct nexthop *newhop;
1978 struct interface *ifp;
1979 rib_dest_t *dest;
5a0bdc78 1980 struct zebra_vrf *zvrf;
31f937fb
SM		 1981 struct in_addr local_ipv4;
1982 struct in_addr *ipv4;
5530d55d 1983 afi_t afi = AFI_IP;
ad28e79a 1984
9b4ab909 1985 /* Reset some nexthop attributes that we'll recompute if necessary */
ad28e79a 1986 if ((nexthop->type == NEXTHOP_TYPE_IPV4)
9b4ab909 1987 || (nexthop->type == NEXTHOP_TYPE_IPV6))
ad28e79a
SW		 1988 nexthop->ifindex = 0;
1989
1990 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
1991 nexthops_free(nexthop->resolved);
1992 nexthop->resolved = NULL;
377e29f7 1993
ad28e79a 1994 /*
5530d55d 1995 * Set afi based on nexthop type.
9b4ab909
MS		 1996 * Some nexthop types get special handling, possibly skipping
1997 * the normal processing.
ad28e79a 1998 */
9b4ab909
MS		 1999 switch (nexthop->type) {
2000 case NEXTHOP_TYPE_IFINDEX:
5530d55d 2001
9b4ab909
MS		 2002 ifp = if_lookup_by_index(nexthop->ifindex, nexthop->vrf_id);
2003 /*
2004 * If the interface exists and its operative or its a kernel
2005 * route and interface is up, its active. We trust kernel routes
2006 * to be good.
2007 */
2008 if (ifp
2009 && (if_is_operative(ifp)
2010 || (if_is_up(ifp)
2011 && (type == ZEBRA_ROUTE_KERNEL
2012 || type == ZEBRA_ROUTE_SYSTEM))))
2013 return 1;
2014 else
2015 return 0;
2016 break;
2017
2018 case NEXTHOP_TYPE_IPV6_IFINDEX:
5530d55d
MS		 2019 afi = AFI_IP6;
2020
9b4ab909
MS		 2021 if (IN6_IS_ADDR_LINKLOCAL(&nexthop->gate.ipv6)) {
2022 ifp = if_lookup_by_index(nexthop->ifindex,
2023 nexthop->vrf_id);
2024 if (ifp && if_is_operative(ifp))
2025 return 1;
2026 else
2027 return 0;
2028 }
2029 break;
2030
9b4ab909
MS		 2031 case NEXTHOP_TYPE_IPV4:
2032 case NEXTHOP_TYPE_IPV4_IFINDEX:
5530d55d
MS		 2033 afi = AFI_IP;
2034 break;
9b4ab909 2035 case NEXTHOP_TYPE_IPV6:
5530d55d 2036 afi = AFI_IP6;
9b4ab909 2037 break;
5530d55d
MS		 2038
2039 case NEXTHOP_TYPE_BLACKHOLE:
2040 return 1;
9b4ab909
MS		 2041 }
2042
ad28e79a 2043 /*
12b4d77b 2044 * If the nexthop has been marked as 'onlink' we just need to make
2045 * sure the nexthop's interface is known and is operational.
ad28e79a
SW		 2046 */
2047 if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK)) {
2048 ifp = if_lookup_by_index(nexthop->ifindex, nexthop->vrf_id);
2049 if (!ifp) {
a24d04f4 2050 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
12b4d77b 2051 zlog_debug("nexthop %pNHv marked onlink but nhif %u doesn't exist",
2052 nexthop, nexthop->ifindex);
ad28e79a
SW		 2053 return 0;
2054 }
12b4d77b 2055 if (!if_is_operative(ifp)) {
a24d04f4 2056 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
12b4d77b 2057 zlog_debug("nexthop %pNHv marked onlink but nhif %s is not operational",
2058 nexthop, ifp->name);
2d3c57e6 2059 return 0;
ad28e79a 2060 }
12b4d77b 2061 return 1;
ad28e79a
SW		 2062 }
2063
13ccce6e 2064 if (top
12256b84 2065 && ((top->family == AF_INET && top->prefixlen == IPV4_MAX_BITLEN
13ccce6e
DA		 2066 && nexthop->gate.ipv4.s_addr == top->u.prefix4.s_addr)
2067 || (top->family == AF_INET6 && top->prefixlen == IPV6_MAX_BITLEN
8643c2e5
DA		 2068 && memcmp(&nexthop->gate.ipv6, &top->u.prefix6,
2069 IPV6_MAX_BYTELEN)
13ccce6e 2070 == 0))) {
4dcc2276
DS		 2071 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
2072 zlog_debug(
d6951e5e 2073 " :%s: Attempting to install a max prefixlength route through itself",
5e81f5dd 2074 __func__);
4dcc2276
DS		 2075 return 0;
2076 }
2077
92d6f769
K		 2078 /* Validation for ipv4 mapped ipv6 nexthop. */
2079 if (IS_MAPPED_IPV6(&nexthop->gate.ipv6)) {
2080 afi = AFI_IP;
31f937fb
SM		 2081 ipv4 = &local_ipv4;
2082 ipv4_mapped_ipv6_to_ipv4(&nexthop->gate.ipv6, ipv4);
2083 } else {
2084 ipv4 = &nexthop->gate.ipv4;
2085 }
2086
9b4ab909
MS		 2087 /* Processing for nexthops with SR 'color' attribute, using
2088 * the corresponding SR policy object.
2089 */
31f937fb
SM		 2090 if (nexthop->srte_color) {
2091 struct ipaddr endpoint = {0};
2092 struct zebra_sr_policy *policy;
2093
2094 switch (afi) {
2095 case AFI_IP:
2096 endpoint.ipa_type = IPADDR_V4;
2097 endpoint.ipaddr_v4 = *ipv4;
2098 break;
2099 case AFI_IP6:
2100 endpoint.ipa_type = IPADDR_V6;
2101 endpoint.ipaddr_v6 = nexthop->gate.ipv6;
2102 break;
2103 default:
2104 flog_err(EC_LIB_DEVELOPMENT,
2105 "%s: unknown address-family: %u", __func__,
2106 afi);
2107 exit(1);
2108 }
2109
2110 policy = zebra_sr_policy_find(nexthop->srte_color, &endpoint);
2111 if (policy && policy->status == ZEBRA_SR_POLICY_UP) {
2112 resolved = 0;
2113 frr_each_safe (nhlfe_list, &policy->lsp->nhlfe_list,
2114 nhlfe) {
2115 if (!CHECK_FLAG(nhlfe->flags,
2116 NHLFE_FLAG_SELECTED)
2117 || CHECK_FLAG(nhlfe->flags,
2118 NHLFE_FLAG_DELETED))
2119 continue;
2120 SET_FLAG(nexthop->flags,
2121 NEXTHOP_FLAG_RECURSIVE);
2122 nexthop_set_resolved(afi, nhlfe->nexthop,
2123 nexthop, policy);
2124 resolved = 1;
2125 }
2126 if (resolved)
2127 return 1;
2128 }
92d6f769
K		 2129 }
2130
ad28e79a
SW		 2131 /* Make lookup prefix. */
2132 memset(&p, 0, sizeof(struct prefix));
2133 switch (afi) {
2134 case AFI_IP:
2135 p.family = AF_INET;
936fbaef 2136 p.prefixlen = IPV4_MAX_BITLEN;
31f937fb 2137 p.u.prefix4 = *ipv4;
ad28e79a
SW		 2138 break;
2139 case AFI_IP6:
2140 p.family = AF_INET6;
f4d81e55 2141 p.prefixlen = IPV6_MAX_BITLEN;
ad28e79a
SW		 2142 p.u.prefix6 = nexthop->gate.ipv6;
2143 break;
2144 default:
2145 assert(afi != AFI_IP && afi != AFI_IP6);
2146 break;
2147 }
2148 /* Lookup table. */
2149 table = zebra_vrf_table(afi, SAFI_UNICAST, nexthop->vrf_id);
5a0bdc78
PG		 2150 /* get zvrf */
2151 zvrf = zebra_vrf_lookup_by_id(nexthop->vrf_id);
2152 if (!table || !zvrf) {
ad28e79a 2153 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
d6951e5e 2154 zlog_debug(" %s: Table not found", __func__);
ad28e79a
SW		 2155 return 0;
2156 }
2157
2158 rn = route_node_match(table, (struct prefix *)&p);
2159 while (rn) {
2160 route_unlock_node(rn);
2161
2162 /* Lookup should halt if we've matched against ourselves ('top',
2163 * if specified) - i.e., we cannot have a nexthop NH1 is
2164 * resolved by a route NH1. The exception is if the route is a
2165 * host route.
2166 */
9b4ab909 2167 if (prefix_same(&rn->p, top))
12256b84
DA		 2168 if (((afi == AFI_IP)
2169 && (rn->p.prefixlen != IPV4_MAX_BITLEN))
13ccce6e
DA		 2170 || ((afi == AFI_IP6)
2171 && (rn->p.prefixlen != IPV6_MAX_BITLEN))) {
ad28e79a
SW		 2172 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
2173 zlog_debug(
d6951e5e 2174 " %s: Matched against ourself and prefix length is not max bit length",
5e81f5dd 2175 __func__);
ad28e79a
SW		 2176 return 0;
2177 }
2178
2179 /* Pick up selected route. */
2180 /* However, do not resolve over default route unless explicitly
2d3c57e6
SW		 2181 * allowed.
2182 */
ad28e79a 2183 if (is_default_prefix(&rn->p)
5a0bdc78 2184 && !rnh_resolve_via_default(zvrf, p.family)) {
ad28e79a
SW		 2185 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
2186 zlog_debug(
d6951e5e 2187 " :%s: Resolved against default route",
5e81f5dd 2188 __func__);
ad28e79a
SW		 2189 return 0;
2190 }
2191
2192 dest = rib_dest_from_rnode(rn);
2193 if (dest && dest->selected_fib
2194 && !CHECK_FLAG(dest->selected_fib->status,
2195 ROUTE_ENTRY_REMOVED)
2196 && dest->selected_fib->type != ZEBRA_ROUTE_TABLE)
2197 match = dest->selected_fib;
2198
2199 /* If there is no selected route or matched route is EGP, go up
2d3c57e6
SW		 2200 * tree.
2201 */
ad28e79a
SW		 2202 if (!match) {
2203 do {
2204 rn = rn->parent;
2205 } while (rn && rn->info == NULL);
2206 if (rn)
2207 route_lock_node(rn);
2208
2209 continue;
2210 }
2211
2212 if (match->type == ZEBRA_ROUTE_CONNECT) {
2213 /* Directly point connected route. */
c415d895 2214 newhop = match->nhe->nhg.nexthop;
ad28e79a
SW		 2215 if (newhop) {
2216 if (nexthop->type == NEXTHOP_TYPE_IPV4
2217 || nexthop->type == NEXTHOP_TYPE_IPV6)
2218 nexthop->ifindex = newhop->ifindex;
c479909b 2219 else if (nexthop->ifindex != newhop->ifindex) {
a24d04f4 2220 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
81194fee
DS		 2221 zlog_debug(
2222 "%s: %pNHv given ifindex does not match nexthops ifindex found found: %pNHv",
2223 __func__, nexthop,
2224 newhop);
c479909b
SW		 2225 /*
2226 * NEXTHOP_TYPE_*_IFINDEX but ifindex
2227 * doesn't match what we found.
2228 */
2229 return 0;
2230 }
ad28e79a 2231 }
377e29f7
MS		 2232
2233 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2234 zlog_debug("%s: CONNECT match %p (%u), newhop %pNHv",
2235 __func__, match,
2236 match->nhe->id, newhop);
2237
ad28e79a 2238 return 1;
9b4ab909 2239 } else if (CHECK_FLAG(flags, ZEBRA_FLAG_ALLOW_RECURSION)) {
f2646720 2240 struct nexthop_group *nhg;
5530d55d
MS		 2241 struct nexthop *resolver;
2242 struct backup_nh_map_s map = {};
f2646720 2243
ad28e79a 2244 resolved = 0;
f2646720 2245
92ad0c55
MS		 2246 /* Only useful if installed */
2247 if (!CHECK_FLAG(match->status, ROUTE_ENTRY_INSTALLED)) {
a24d04f4 2248 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
92ad0c55
MS		 2249 zlog_debug("%s: match %p (%u) not installed",
2250 __func__, match,
2251 match->nhe->id);
2252
2253 goto done_with_match;
2254 }
2255
3c0e1622
MS		 2256 /* Examine installed nexthops; note that there
2257 * may not be any installed primary nexthops if
2258 * only backups are installed.
2259 */
2260 nhg = rib_get_fib_nhg(match);
f2646720 2261 for (ALL_NEXTHOPS_PTR(nhg, newhop)) {
6913cb1b 2262 if (!nexthop_valid_resolve(nexthop, newhop))
ad28e79a
SW		 2263 continue;
2264
377e29f7
MS		 2265 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2266 zlog_debug("%s: RECURSIVE match %p (%u), newhop %pNHv",
2267 __func__, match,
2268 match->nhe->id, newhop);
2269
ad28e79a
SW		 2270 SET_FLAG(nexthop->flags,
2271 NEXTHOP_FLAG_RECURSIVE);
5530d55d
MS		 2272 resolver = nexthop_set_resolved(afi, newhop,
2273 nexthop, NULL);
ad28e79a 2274 resolved = 1;
5530d55d
MS		 2275
2276 /* If there are backup nexthops, capture
2277 * that info with the resolving nexthop.
2278 */
2279 if (resolver && newhop->backup_num > 0) {
2280 resolve_backup_nexthops(newhop,
2281 match->nhe,
2282 resolver, nhe,
2283 &map);
2284 }
ad28e79a 2285 }
f924db49 2286
9959f1da
MS		 2287 /* Examine installed backup nexthops, if any. There
2288 * are only installed backups *if* there is a
aa458838
MS		 2289 * dedicated fib list. The UI can also control use
2290 * of backups for resolution.
9959f1da
MS		 2291 */
2292 nhg = rib_get_fib_backup_nhg(match);
aa458838
MS		 2293 if (!use_recursive_backups ||
2294 nhg == NULL || nhg->nexthop == NULL)
f2646720
MS		 2295 goto done_with_match;
2296
2297 for (ALL_NEXTHOPS_PTR(nhg, newhop)) {
f2646720
MS		 2298 if (!nexthop_valid_resolve(nexthop, newhop))
2299 continue;
2300
2301 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2302 zlog_debug("%s: RECURSIVE match backup %p (%u), newhop %pNHv",
2303 __func__, match,
2304 match->nhe->id, newhop);
2305
2306 SET_FLAG(nexthop->flags,
2307 NEXTHOP_FLAG_RECURSIVE);
31f937fb
SM		 2308 nexthop_set_resolved(afi, newhop, nexthop,
2309 NULL);
f2646720
MS		 2310 resolved = 1;
2311 }
9b4ab909 2312
f2646720 2313done_with_match:
9b4ab909
MS		 2314 /* Capture resolving mtu */
2315 if (resolved) {
2316 if (pmtu)
2317 *pmtu = match->mtu;
2318
2319 } else if (IS_ZEBRA_DEBUG_RIB_DETAILED)
d6951e5e
DL		 2320 zlog_debug(
2321 " %s: Recursion failed to find",
2322 __func__);
f924db49 2323
ad28e79a 2324 return resolved;
ad28e79a
SW		 2325 } else {
2326 if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
2327 zlog_debug(
d6951e5e 2328 " %s: Route Type %s has not turned on recursion",
9b4ab909
MS		 2329 __func__, zebra_route_string(type));
2330 if (type == ZEBRA_ROUTE_BGP
2331 && !CHECK_FLAG(flags, ZEBRA_FLAG_IBGP))
ad28e79a 2332 zlog_debug(
d6951e5e 2333 " EBGP: see \"disable-ebgp-connected-route-check\" or \"disable-connected-check\"");
ad28e79a
SW		 2334 }
2335 return 0;
2336 }
2337 }
2338 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
d6951e5e
DL		 2339 zlog_debug(" %s: Nexthop did not lookup in table",
2340 __func__);
ad28e79a
SW		 2341 return 0;
2342}
2343
2344/* This function verifies reachability of one given nexthop, which can be
2345 * numbered or unnumbered, IPv4 or IPv6. The result is unconditionally stored
2346 * in nexthop->flags field. The nexthop->ifindex will be updated
5530d55d
MS		 2347 * appropriately as well.
2348 *
2349 * An existing route map can turn an otherwise active nexthop into inactive,
2350 * but not vice versa.
ad28e79a
SW		 2351 *
2352 * The return value is the final value of 'ACTIVE' flag.
2353 */
2354static unsigned nexthop_active_check(struct route_node *rn,
2355 struct route_entry *re,
5530d55d
MS		 2356 struct nexthop *nexthop,
2357 struct nhg_hash_entry *nhe)
ad28e79a 2358{
b68885f9 2359 route_map_result_t ret = RMAP_PERMITMATCH;
f5b7e50f 2360 afi_t family;
ad28e79a
SW		 2361 const struct prefix *p, *src_p;
2362 struct zebra_vrf *zvrf;
9b4ab909 2363 uint32_t mtu = 0;
ad28e79a
SW		 2364
2365 srcdest_rnode_prefixes(rn, &p, &src_p);
2366
2367 if (rn->p.family == AF_INET)
2368 family = AFI_IP;
2369 else if (rn->p.family == AF_INET6)
2370 family = AFI_IP6;
2371 else
2372 family = 0;
ee94437e 2373
9b4ab909
MS		 2374 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2375 zlog_debug("%s: re %p, nexthop %pNHv", __func__, re, nexthop);
2376
2377 /*
2378 * If the kernel has sent us a NEW route, then
2379 * by golly gee whiz it's a good route.
2380 *
2381 * If its an already INSTALLED route we have already handled, then the
2382 * kernel route's nexthop might have became unreachable
2383 * and we have to handle that.
2384 */
2385 if (!CHECK_FLAG(re->status, ROUTE_ENTRY_INSTALLED) &&
2386 (re->type == ZEBRA_ROUTE_KERNEL ||
2387 re->type == ZEBRA_ROUTE_SYSTEM)) {
2388 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2389 goto skip_check;
2390 }
2391
ad28e79a
SW		 2392 switch (nexthop->type) {
2393 case NEXTHOP_TYPE_IFINDEX:
5530d55d 2394 if (nexthop_active(nexthop, nhe, &rn->p, re->type,
9b4ab909 2395 re->flags, &mtu))
ad28e79a
SW		 2396 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2397 else
2398 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2399 break;
2400 case NEXTHOP_TYPE_IPV4:
2401 case NEXTHOP_TYPE_IPV4_IFINDEX:
2402 family = AFI_IP;
5530d55d 2403 if (nexthop_active(nexthop, nhe, &rn->p, re->type,
9b4ab909 2404 re->flags, &mtu))
ad28e79a
SW		 2405 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2406 else
2407 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2408 break;
2409 case NEXTHOP_TYPE_IPV6:
2410 family = AFI_IP6;
5530d55d 2411 if (nexthop_active(nexthop, nhe, &rn->p, re->type,
9b4ab909 2412 re->flags, &mtu))
ad28e79a
SW		 2413 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2414 else
2415 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2416 break;
2417 case NEXTHOP_TYPE_IPV6_IFINDEX:
2418 /* RFC 5549, v4 prefix with v6 NH */
2419 if (rn->p.family != AF_INET)
2420 family = AFI_IP6;
9b4ab909 2421
5530d55d 2422 if (nexthop_active(nexthop, nhe, &rn->p, re->type,
9b4ab909
MS		 2423 re->flags, &mtu))
2424 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2425 else
2426 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
ad28e79a
SW		 2427 break;
2428 case NEXTHOP_TYPE_BLACKHOLE:
2429 SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2430 break;
2431 default:
2432 break;
2433 }
377e29f7 2434
9b4ab909
MS		 2435skip_check:
2436
ad28e79a
SW		 2437 if (!CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE)) {
2438 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
377e29f7
MS		 2439 zlog_debug(" %s: Unable to find active nexthop",
2440 __func__);
ad28e79a
SW		 2441 return 0;
2442 }
2443
9b4ab909
MS		 2444 /* Capture recursive nexthop mtu.
2445 * TODO -- the code used to just reset the re's value to zero
2446 * for each nexthop, and then jam any resolving route's mtu value in,
2447 * whether or not that was zero, or lt/gt any existing value? The
2448 * way this is used appears to be as a floor value, so let's try
2449 * using it that way here.
2450 */
2451 if (mtu > 0) {
2452 if (re->nexthop_mtu == 0 || re->nexthop_mtu > mtu)
2453 re->nexthop_mtu = mtu;
2454 }
2455
ad28e79a
SW		 2456 /* XXX: What exactly do those checks do? Do we support
2457 * e.g. IPv4 routes with IPv6 nexthops or vice versa?
2458 */
2459 if (RIB_SYSTEM_ROUTE(re) || (family == AFI_IP && p->family != AF_INET)
2460 || (family == AFI_IP6 && p->family != AF_INET6))
2461 return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2462
2463 /* The original code didn't determine the family correctly
2464 * e.g. for NEXTHOP_TYPE_IFINDEX. Retrieve the correct afi
2465 * from the rib_table_info in those cases.
2466 * Possibly it may be better to use only the rib_table_info
2467 * in every case.
2468 */
9b4ab909 2469 if (family == 0) {
630d5962 2470 struct rib_table_info *info;
ad28e79a
SW		 2471
2472 info = srcdest_rnode_table_info(rn);
2473 family = info->afi;
2474 }
2475
2476 memset(&nexthop->rmap_src.ipv6, 0, sizeof(union g_addr));
2477
2478 zvrf = zebra_vrf_lookup_by_id(nexthop->vrf_id);
2479 if (!zvrf) {
2480 if (IS_ZEBRA_DEBUG_RIB_DETAILED)
d6951e5e 2481 zlog_debug(" %s: zvrf is NULL", __func__);
ad28e79a
SW		 2482 return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2483 }
2484
2485 /* It'll get set if required inside */
2486 ret = zebra_route_map_check(family, re->type, re->instance, p, nexthop,
2487 zvrf, re->tag);
2488 if (ret == RMAP_DENYMATCH) {
2489 if (IS_ZEBRA_DEBUG_RIB) {
ad28e79a 2490 zlog_debug(
7e010c4b
DS		 2491 "%u:%pRN: Filtering out with NH out %s due to route map",
2492 re->vrf_id, rn,
ad28e79a
SW		 2493 ifindex2ifname(nexthop->ifindex,
2494 nexthop->vrf_id));
2495 }
2496 UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2497 }
2498 return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2499}
2500
086e4e02
SW		 2501/* Helper function called after resolution to walk nhg rb trees
2502 * and toggle the NEXTHOP_GROUP_VALID flag if the nexthop
2503 * is active on singleton NHEs.
2504 */
2505static bool zebra_nhg_set_valid_if_active(struct nhg_hash_entry *nhe)
2506{
2507 struct nhg_connected *rb_node_dep = NULL;
2508 bool valid = false;
2509
2510 if (!zebra_nhg_depends_is_empty(nhe)) {
2511 /* Is at least one depend valid? */
2512 frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
2513 if (zebra_nhg_set_valid_if_active(rb_node_dep->nhe))
2514 valid = true;
2515 }
2516
2517 goto done;
2518 }
2519
2520 /* should be fully resolved singleton at this point */
2521 if (CHECK_FLAG(nhe->nhg.nexthop->flags, NEXTHOP_FLAG_ACTIVE))
2522 valid = true;
2523
2524done:
2525 if (valid)
2526 SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
2527
2528 return valid;
2529}
2530
ad28e79a 2531/*
5530d55d 2532 * Process a list of nexthops, given an nhe, determining
377e29f7 2533 * whether each one is ACTIVE/installable at this time.
ad28e79a 2534 */
377e29f7
MS		 2535static uint32_t nexthop_list_active_update(struct route_node *rn,
2536 struct route_entry *re,
5530d55d
MS		 2537 struct nhg_hash_entry *nhe,
2538 bool is_backup)
ad28e79a 2539{
ad28e79a
SW		 2540 union g_addr prev_src;
2541 unsigned int prev_active, new_active;
2542 ifindex_t prev_index;
377e29f7 2543 uint32_t counter = 0;
f2646720 2544 struct nexthop *nexthop;
5530d55d 2545 struct nexthop_group *nhg = &nhe->nhg;
f2646720
MS		 2546
2547 nexthop = nhg->nexthop;
e22e8001 2548
9b4ab909
MS		 2549 /* Init recursive nh mtu */
2550 re->nexthop_mtu = 0;
2551
377e29f7
MS		 2552 /* Process nexthops one-by-one */
2553 for ( ; nexthop; nexthop = nexthop->next) {
ad28e79a 2554
ad28e79a 2555 /* No protocol daemon provides src and so we're skipping
377e29f7
MS		 2556 * tracking it
2557 */
ad28e79a
SW		 2558 prev_src = nexthop->rmap_src;
2559 prev_active = CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
2560 prev_index = nexthop->ifindex;
5530d55d
MS		 2561
2562 /* Include the containing nhe for primary nexthops: if there's
2563 * recursive resolution, we capture the backup info also.
2564 */
2565 new_active =
2566 nexthop_active_check(rn, re, nexthop,
2567 (is_backup ? NULL : nhe));
2568
ad28e79a
SW		 2569 /*
2570 * We need to respect the multipath_num here
2571 * as that what we should be able to install from
377e29f7 2572 * a multipath perspective should not be a data plane
ad28e79a
SW		 2573 * decision point.
2574 */
377e29f7 2575 if (new_active && counter >= zrouter.multipath_num) {
4c55b5ff
SW		 2576 struct nexthop *nh;
2577
2578 /* Set it and its resolved nexthop as inactive. */
2579 for (nh = nexthop; nh; nh = nh->resolved)
2580 UNSET_FLAG(nh->flags, NEXTHOP_FLAG_ACTIVE);
2581
ad28e79a
SW		 2582 new_active = 0;
2583 }
9a0d4dd3 2584
df31a989 2585 if (new_active)
377e29f7 2586 counter++;
9a0d4dd3 2587
5530d55d 2588 /* Check for changes to the nexthop - set ROUTE_ENTRY_CHANGED */
ad28e79a
SW		 2589 if (prev_active != new_active || prev_index != nexthop->ifindex
2590 || ((nexthop->type >= NEXTHOP_TYPE_IFINDEX
2591 && nexthop->type < NEXTHOP_TYPE_IPV6)
2592 && prev_src.ipv4.s_addr
2593 != nexthop->rmap_src.ipv4.s_addr)
2594 || ((nexthop->type >= NEXTHOP_TYPE_IPV6
2595 && nexthop->type < NEXTHOP_TYPE_BLACKHOLE)
2596 && !(IPV6_ADDR_SAME(&prev_src.ipv6,
2597 &nexthop->rmap_src.ipv6)))
8a507796 2598 || CHECK_FLAG(re->status, ROUTE_ENTRY_LABELS_CHANGED))
ad28e79a 2599 SET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
ad28e79a
SW		 2600 }
2601
377e29f7
MS		 2602 return counter;
2603}
2604
2c41ef8c
SW		 2605
2606static uint32_t proto_nhg_nexthop_active_update(struct nexthop_group *nhg)
2607{
2608 struct nexthop *nh;
2609 uint32_t curr_active = 0;
2610
2611 /* Assume all active for now */
2612
2613 for (nh = nhg->nexthop; nh; nh = nh->next) {
2614 SET_FLAG(nh->flags, NEXTHOP_FLAG_ACTIVE);
2615 curr_active++;
2616 }
2617
2618 return curr_active;
2619}
2620
377e29f7
MS		 2621/*
2622 * Iterate over all nexthops of the given RIB entry and refresh their
2623 * ACTIVE flag. If any nexthop is found to toggle the ACTIVE flag,
2624 * the whole re structure is flagged with ROUTE_ENTRY_CHANGED.
2625 *
2626 * Return value is the new number of active nexthops.
2627 */
2628int nexthop_active_update(struct route_node *rn, struct route_entry *re)
2629{
2630 struct nhg_hash_entry *curr_nhe;
2631 uint32_t curr_active = 0, backup_active = 0;
2632
65f137fe 2633 if (PROTO_OWNED(re->nhe))
2c41ef8c
SW		 2634 return proto_nhg_nexthop_active_update(&re->nhe->nhg);
2635
377e29f7
MS		 2636 afi_t rt_afi = family2afi(rn->p.family);
2637
2638 UNSET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
2639
2640 /* Make a local copy of the existing nhe, so we don't work on/modify
2641 * the shared nhe.
2642 */
f727646a 2643 curr_nhe = zebra_nhe_copy(re->nhe, re->nhe->id);
377e29f7
MS		 2644
2645 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2646 zlog_debug("%s: re %p nhe %p (%u), curr_nhe %p",
2647 __func__, re, re->nhe, re->nhe->id,
2648 curr_nhe);
2649
2650 /* Clear the existing id, if any: this will avoid any confusion
2651 * if the id exists, and will also force the creation
2652 * of a new nhe reflecting the changes we may make in this local copy.
2653 */
2654 curr_nhe->id = 0;
2655
2656 /* Process nexthops */
5530d55d 2657 curr_active = nexthop_list_active_update(rn, re, curr_nhe, false);
377e29f7
MS		 2658
2659 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2660 zlog_debug("%s: re %p curr_active %u", __func__, re,
2661 curr_active);
2662
2663 /* If there are no backup nexthops, we are done */
2664 if (zebra_nhg_get_backup_nhg(curr_nhe) == NULL)
2665 goto backups_done;
2666
2667 backup_active = nexthop_list_active_update(
5530d55d 2668 rn, re, curr_nhe->backup_info->nhe, true /*is_backup*/);
377e29f7
MS		 2669
2670 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2671 zlog_debug("%s: re %p backup_active %u", __func__, re,
2672 backup_active);
2673
2674backups_done:
2675
2676 /*
2677 * Ref or create an nhe that matches the current state of the
2678 * nexthop(s).
2679 */
8a507796 2680 if (CHECK_FLAG(re->status, ROUTE_ENTRY_CHANGED)) {
98cda54a 2681 struct nhg_hash_entry *new_nhe = NULL;
98cda54a 2682
377e29f7
MS		 2683 new_nhe = zebra_nhg_rib_find_nhe(curr_nhe, rt_afi);
2684
2685 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2686 zlog_debug("%s: re %p CHANGED: nhe %p (%u) => new_nhe %p (%u)",
2687 __func__, re, re->nhe,
2688 re->nhe->id, new_nhe, new_nhe->id);
98cda54a 2689
5463ce26 2690 route_entry_update_nhe(re, new_nhe);
e22e8001
SW		 2691 }
2692
377e29f7 2693
086e4e02
SW		 2694 /* Walk the NHE depends tree and toggle NEXTHOP_GROUP_VALID
2695 * flag where appropriate.
2696 */
715e5c70 2697 if (curr_active)
086e4e02 2698 zebra_nhg_set_valid_if_active(re->nhe);
98cda54a
SW		 2699
2700 /*
377e29f7
MS		 2701 * Do not need the old / copied nhe anymore since it
2702 * was either copied over into a new nhe or not
98cda54a
SW		 2703 * used at all.
2704 */
377e29f7 2705 zebra_nhg_free(curr_nhe);
9a0d4dd3 2706 return curr_active;
ad28e79a 2707}
5be96a2d 2708
497ff579
SW		 2709/* Recursively construct a grp array of fully resolved IDs.
2710 *
2711 * This function allows us to account for groups within groups,
2712 * by converting them into a flat array of IDs.
2713 *
2714 * nh_grp is modified at every level of recursion to append
2715 * to it the next unique, fully resolved ID from the entire tree.
2716 *
2717 *
2718 * Note:
2719 * I'm pretty sure we only allow ONE level of group within group currently.
2720 * But making this recursive just in case that ever changes.
2721 */
2722static uint8_t zebra_nhg_nhe2grp_internal(struct nh_grp *grp,
2723 uint8_t curr_index,
2724 struct nhg_hash_entry *nhe,
2725 int max_num)
98cda54a
SW		 2726{
2727 struct nhg_connected *rb_node_dep = NULL;
2728 struct nhg_hash_entry *depend = NULL;
497ff579 2729 uint8_t i = curr_index;
98cda54a 2730
fec211ad 2731 frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
8dbc800f
SW		 2732 bool duplicate = false;
2733
497ff579
SW		 2734 if (i >= max_num)
2735 goto done;
2736
98cda54a
SW		 2737 depend = rb_node_dep->nhe;
2738
2739 /*
2740 * If its recursive, use its resolved nhe in the group
2741 */
2742 if (CHECK_FLAG(depend->flags, NEXTHOP_GROUP_RECURSIVE)) {
2743 depend = zebra_nhg_resolve(depend);
2744 if (!depend) {
2745 flog_err(
2746 EC_ZEBRA_NHG_FIB_UPDATE,
df31a989
SW		 2747 "Failed to recursively resolve Nexthop Hash Entry in the group id=%u",
2748 nhe->id);
98cda54a
SW		 2749 continue;
2750 }
2751 }
2752
497ff579
SW		 2753 if (!zebra_nhg_depends_is_empty(depend)) {
2754 /* This is a group within a group */
2755 i = zebra_nhg_nhe2grp_internal(grp, i, depend, max_num);
2756 } else {
086e4e02
SW		 2757 if (!CHECK_FLAG(depend->flags, NEXTHOP_GROUP_VALID)) {
2758 if (IS_ZEBRA_DEBUG_RIB_DETAILED
2759 || IS_ZEBRA_DEBUG_NHG)
2760 zlog_debug(
2761 "%s: Nexthop ID (%u) not valid, not appending to dataplane install group",
2762 __func__, depend->id);
2763 continue;
2764 }
2765
1866b3af
SW		 2766 /* If the nexthop not installed/queued for install don't
2767 * put in the ID array.
2768 */
2769 if (!(CHECK_FLAG(depend->flags, NEXTHOP_GROUP_INSTALLED)
2770 || CHECK_FLAG(depend->flags,
2771 NEXTHOP_GROUP_QUEUED))) {
2772 if (IS_ZEBRA_DEBUG_RIB_DETAILED
2773 || IS_ZEBRA_DEBUG_NHG)
2774 zlog_debug(
2775 "%s: Nexthop ID (%u) not installed or queued for install, not appending to dataplane install group",
2776 __func__, depend->id);
2777 continue;
2778 }
2779
b1c3f7ef 2780 /* Check for duplicate IDs, ignore if found. */
497ff579 2781 for (int j = 0; j < i; j++) {
d43122b5 2782 if (depend->id == grp[j].id) {
497ff579 2783 duplicate = true;
d43122b5
SW		 2784 break;
2785 }
497ff579 2786 }
8dbc800f 2787
b1c3f7ef
SW		 2788 if (duplicate) {
2789 if (IS_ZEBRA_DEBUG_RIB_DETAILED
2790 || IS_ZEBRA_DEBUG_NHG)
2791 zlog_debug(
2792 "%s: Nexthop ID (%u) is duplicate, not appending to dataplane install group",
2793 __func__, depend->id);
2794 continue;
497ff579 2795 }
b1c3f7ef
SW		 2796
2797 grp[i].id = depend->id;
2798 grp[i].weight = depend->nhg.nexthop->weight;
2799 i++;
8dbc800f 2800 }
98cda54a 2801 }
8dbc800f 2802
0328a5bd
MS		 2803 if (nhe->backup_info == NULL || nhe->backup_info->nhe == NULL)
2804 goto done;
2805
2806 /* TODO -- For now, we are not trying to use or install any
2807 * backup info in this nexthop-id path: we aren't prepared
2808 * to use the backups here yet. We're just debugging what we find.
2809 */
2810 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
2811 zlog_debug("%s: skipping backup nhe", __func__);
2812
8dbc800f 2813done:
98cda54a
SW		 2814 return i;
2815}
2816
497ff579
SW		 2817/* Convert a nhe into a group array */
2818uint8_t zebra_nhg_nhe2grp(struct nh_grp *grp, struct nhg_hash_entry *nhe,
2819 int max_num)
2820{
2821 /* Call into the recursive function */
2822 return zebra_nhg_nhe2grp_internal(grp, 0, nhe, max_num);
2823}
2824
5be96a2d
SW		 2825void zebra_nhg_install_kernel(struct nhg_hash_entry *nhe)
2826{
f429bd1b
SW		 2827 struct nhg_connected *rb_node_dep = NULL;
2828
2829 /* Resolve it first */
2830 nhe = zebra_nhg_resolve(nhe);
2831
2832 /* Make sure all depends are installed/queued */
fec211ad 2833 frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
f429bd1b
SW		 2834 zebra_nhg_install_kernel(rb_node_dep->nhe);
2835 }
2836
086e4e02 2837 if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_VALID)
e3b9c0f2 2838 && !CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED)
e22e8001 2839 && !CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED)) {
724583ed 2840 /* Change its type to us since we are installing it */
0885b1e3
SW		 2841 if (!ZEBRA_NHG_CREATED(nhe))
2842 nhe->type = ZEBRA_ROUTE_NHG;
724583ed 2843
147bad16 2844 int ret = dplane_nexthop_add(nhe);
2d3c57e6 2845
147bad16
SW		 2846 switch (ret) {
2847 case ZEBRA_DPLANE_REQUEST_QUEUED:
2848 SET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
2849 break;
2850 case ZEBRA_DPLANE_REQUEST_FAILURE:
2851 flog_err(
2852 EC_ZEBRA_DP_INSTALL_FAIL,
2853 "Failed to install Nexthop ID (%u) into the kernel",
2854 nhe->id);
2855 break;
2856 case ZEBRA_DPLANE_REQUEST_SUCCESS:
2857 SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
80286aa5 2858 zebra_nhg_handle_install(nhe);
147bad16
SW		 2859 break;
2860 }
2861 }
2862}
2863
147bad16
SW		 2864void zebra_nhg_uninstall_kernel(struct nhg_hash_entry *nhe)
2865{
2866 if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED)) {
2867 int ret = dplane_nexthop_delete(nhe);
2d3c57e6 2868
147bad16
SW		 2869 switch (ret) {
2870 case ZEBRA_DPLANE_REQUEST_QUEUED:
2871 SET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
2872 break;
2873 case ZEBRA_DPLANE_REQUEST_FAILURE:
2874 flog_err(
2875 EC_ZEBRA_DP_DELETE_FAIL,
2876 "Failed to uninstall Nexthop ID (%u) from the kernel",
2877 nhe->id);
2878 break;
2879 case ZEBRA_DPLANE_REQUEST_SUCCESS:
2880 UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
2881 break;
2882 }
177e711d
SW		 2883 }
2884
2885 zebra_nhg_handle_uninstall(nhe);
147bad16
SW		 2886}
2887
5f3c9e52
SW		 2888void zebra_nhg_dplane_result(struct zebra_dplane_ctx *ctx)
2889{
2890 enum dplane_op_e op;
2891 enum zebra_dplane_result status;
2892 uint32_t id = 0;
2893 struct nhg_hash_entry *nhe = NULL;
2894
2895 op = dplane_ctx_get_op(ctx);
2896 status = dplane_ctx_get_status(ctx);
2897
0c8215cb 2898 id = dplane_ctx_get_nhe_id(ctx);
e22e8001 2899
377e29f7 2900 if (IS_ZEBRA_DEBUG_DPLANE_DETAIL || IS_ZEBRA_DEBUG_NHG_DETAIL)
177e711d
SW		 2901 zlog_debug(
2902 "Nexthop dplane ctx %p, op %s, nexthop ID (%u), result %s",
2903 ctx, dplane_op2str(op), id, dplane_res2str(status));
5f3c9e52 2904
177e711d
SW		 2905 switch (op) {
2906 case DPLANE_OP_NH_DELETE:
2907 if (status != ZEBRA_DPLANE_REQUEST_SUCCESS)
2908 flog_err(
2909 EC_ZEBRA_DP_DELETE_FAIL,
2910 "Failed to uninstall Nexthop ID (%u) from the kernel",
2911 id);
ee94437e 2912
177e711d
SW		 2913 /* We already free'd the data, nothing to do */
2914 break;
2915 case DPLANE_OP_NH_INSTALL:
2916 case DPLANE_OP_NH_UPDATE:
2917 nhe = zebra_nhg_lookup_id(id);
2918
2919 if (!nhe) {
30672034
SW		 2920 if (IS_ZEBRA_DEBUG_NHG)
2921 zlog_debug(
2922 "%s operation preformed on Nexthop ID (%u) in the kernel, that we no longer have in our table",
2923 dplane_op2str(op), id);
2924
5f3c9e52
SW		 2925 break;
2926 }
177e711d
SW		 2927
2928 UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
2929 if (status == ZEBRA_DPLANE_REQUEST_SUCCESS) {
2930 SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
2931 SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
80286aa5 2932 zebra_nhg_handle_install(nhe);
ee94437e
MS		 2933
2934 /* If daemon nhg, send it an update */
65f137fe 2935 if (PROTO_OWNED(nhe))
ee94437e
MS		 2936 zsend_nhg_notify(nhe->type, nhe->zapi_instance,
2937 nhe->zapi_session, nhe->id,
2938 ZAPI_NHG_INSTALLED);
2939 } else {
2940 /* If daemon nhg, send it an update */
65f137fe 2941 if (PROTO_OWNED(nhe))
ee94437e
MS		 2942 zsend_nhg_notify(nhe->type, nhe->zapi_instance,
2943 nhe->zapi_session, nhe->id,
2944 ZAPI_NHG_FAIL_INSTALL);
2945
177e711d
SW		 2946 flog_err(
2947 EC_ZEBRA_DP_INSTALL_FAIL,
2948 "Failed to install Nexthop ID (%u) into the kernel",
2949 nhe->id);
ee94437e 2950 }
177e711d 2951 break;
ee94437e 2952
177e711d
SW		 2953 case DPLANE_OP_ROUTE_INSTALL:
2954 case DPLANE_OP_ROUTE_UPDATE:
2955 case DPLANE_OP_ROUTE_DELETE:
2956 case DPLANE_OP_ROUTE_NOTIFY:
2957 case DPLANE_OP_LSP_INSTALL:
2958 case DPLANE_OP_LSP_UPDATE:
2959 case DPLANE_OP_LSP_DELETE:
2960 case DPLANE_OP_LSP_NOTIFY:
2961 case DPLANE_OP_PW_INSTALL:
2962 case DPLANE_OP_PW_UNINSTALL:
2963 case DPLANE_OP_SYS_ROUTE_ADD:
2964 case DPLANE_OP_SYS_ROUTE_DELETE:
2965 case DPLANE_OP_ADDR_INSTALL:
2966 case DPLANE_OP_ADDR_UNINSTALL:
2967 case DPLANE_OP_MAC_INSTALL:
2968 case DPLANE_OP_MAC_DELETE:
2969 case DPLANE_OP_NEIGH_INSTALL:
2970 case DPLANE_OP_NEIGH_UPDATE:
2971 case DPLANE_OP_NEIGH_DELETE:
0a27a2fe
PG		 2972 case DPLANE_OP_NEIGH_IP_INSTALL:
2973 case DPLANE_OP_NEIGH_IP_DELETE:
177e711d
SW		 2974 case DPLANE_OP_VTEP_ADD:
2975 case DPLANE_OP_VTEP_DELETE:
60d8d43b
JU		 2976 case DPLANE_OP_RULE_ADD:
2977 case DPLANE_OP_RULE_DELETE:
2978 case DPLANE_OP_RULE_UPDATE:
d68e74b4 2979 case DPLANE_OP_NEIGH_DISCOVER:
c60522f7 2980 case DPLANE_OP_BR_PORT_UPDATE:
177e711d 2981 case DPLANE_OP_NONE:
5162e000
PG		 2982 case DPLANE_OP_IPTABLE_ADD:
2983 case DPLANE_OP_IPTABLE_DELETE:
ef524230
PG		 2984 case DPLANE_OP_IPSET_ADD:
2985 case DPLANE_OP_IPSET_DELETE:
2986 case DPLANE_OP_IPSET_ENTRY_ADD:
2987 case DPLANE_OP_IPSET_ENTRY_DELETE:
e18747a9 2988 case DPLANE_OP_NEIGH_TABLE_UPDATE:
62b4b7e4 2989 case DPLANE_OP_GRE_SET:
9d59df63
MS		 2990 case DPLANE_OP_INTF_ADDR_ADD:
2991 case DPLANE_OP_INTF_ADDR_DEL:
177e711d
SW		 2992 break;
2993 }
71593b3f
SW		 2994
2995 dplane_ctx_fini(&ctx);
5be96a2d
SW		 2996}
2997
38e40db1
SW		 2998static void zebra_nhg_sweep_entry(struct hash_bucket *bucket, void *arg)
2999{
3000 struct nhg_hash_entry *nhe = NULL;
3001
3002 nhe = (struct nhg_hash_entry *)bucket->data;
3003
dc65cd99
SW		 3004 /*
3005 * same logic as with routes.
3006 *
3007 * If older than startup time, we know we read them in from the
3008 * kernel and have not gotten and update for them since startup
3009 * from an upper level proto.
3010 */
3011 if (zrouter.startup_time < nhe->uptime)
3012 return;
3013
3014 /*
3015 * If it's proto-owned and not being used by a route, remove it since
3016 * we haven't gotten an update about it from the proto since startup.
3017 * This means that either the config for it was removed or the daemon
3018 * didn't get started. This handles graceful restart & retain scenario.
3019 */
3020 if (PROTO_OWNED(nhe) && nhe->refcnt == 1) {
3021 zebra_nhg_decrement_ref(nhe);
3022 return;
3023 }
3024
3025 /*
3026 * If its being ref'd by routes, just let it be uninstalled via a route
3027 * removal.
3028 */
38e40db1
SW		 3029 if (ZEBRA_NHG_CREATED(nhe) && nhe->refcnt <= 0)
3030 zebra_nhg_uninstall_kernel(nhe);
3031}
3032
3033void zebra_nhg_sweep_table(struct hash *hash)
3034{
3035 hash_iterate(hash, zebra_nhg_sweep_entry, NULL);
3036}
7c99d51b 3037
b1b07ef5
DS		 3038static void zebra_nhg_mark_keep_entry(struct hash_bucket *bucket, void *arg)
3039{
3040 struct nhg_hash_entry *nhe = bucket->data;
3041
3042 UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
3043}
3044
3045/*
3046 * When we are shutting down and we have retain mode enabled
3047 * in zebra the process is to mark each vrf that it's
3048 * routes should not be deleted. The problem with that
3049 * is that shutdown actually free's up memory which
3050 * causes the nexthop group's ref counts to go to zero
3051 * we need a way to subtly tell the system to not remove
3052 * the nexthop groups from the kernel at the same time.
3053 * The easiest just looks like that we should not mark
3054 * the nhg's as installed any more and when the ref count
3055 * goes to zero we'll attempt to delete and do nothing
3056 */
3057void zebra_nhg_mark_keep(void)
3058{
3059 hash_iterate(zrouter.nhgs_id, zebra_nhg_mark_keep_entry, NULL);
3060}
3061
7c99d51b
MS		 3062/* Global control to disable use of kernel nexthops, if available. We can't
3063 * force the kernel to support nexthop ids, of course, but we can disable
3064 * zebra's use of them, for testing e.g. By default, if the kernel supports
3065 * nexthop ids, zebra uses them.
3066 */
3067void zebra_nhg_enable_kernel_nexthops(bool set)
3068{
3069 g_nexthops_enabled = set;
3070}
3071
3072bool zebra_nhg_kernel_nexthops_enabled(void)
3073{
3074 return g_nexthops_enabled;
3075}
0885b1e3 3076
aa458838
MS		 3077/* Global control for use of activated backups for recursive resolution. */
3078void zebra_nhg_set_recursive_use_backups(bool set)
3079{
3080 use_recursive_backups = set;
3081}
3082
3083bool zebra_nhg_recursive_use_backups(void)
3084{
3085 return use_recursive_backups;
3086}
3087
6c67f41f
SW		 3088/*
3089 * Global control to only use kernel nexthops for protocol created NHGs.
3090 * There are some use cases where you may not want zebra to implicitly
3091 * create kernel nexthops for all routes and only create them for NHGs
3092 * passed down by upper level protos.
3093 *
3094 * Default is off.
3095 */
3096void zebra_nhg_set_proto_nexthops_only(bool set)
3097{
3098 proto_nexthops_only = set;
3099}
3100
3101bool zebra_nhg_proto_nexthops_only(void)
3102{
3103 return proto_nexthops_only;
3104}
3105
0885b1e3
SW		 3106/* Add NHE from upper level proto */
3107struct nhg_hash_entry *zebra_nhg_proto_add(uint32_t id, int type,
ee94437e 3108 uint16_t instance, uint32_t session,
0885b1e3
SW		 3109 struct nexthop_group *nhg, afi_t afi)
3110{
3111 struct nhg_hash_entry lookup;
dd1e105f 3112 struct nhg_hash_entry *new, *old;
0885b1e3 3113 struct nhg_connected *rb_node_dep = NULL;
1f655680
SW		 3114 struct nexthop *newhop;
3115 bool replace = false;
3116
3117 if (!nhg->nexthop) {
3118 if (IS_ZEBRA_DEBUG_NHG)
3119 zlog_debug("%s: id %u, no nexthops passed to add",
3120 __func__, id);
3121 return NULL;
3122 }
3123
3124
3125 /* Set nexthop list as active, since they wont go through rib
3126 * processing.
3127 *
3128 * Assuming valid/onlink for now.
3129 *
3130 * Once resolution is figured out, we won't need this!
3131 */
70347b7a 3132 for (ALL_NEXTHOPS_PTR(nhg, newhop)) {
21735352
SW		 3133 if (CHECK_FLAG(newhop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
3134 if (IS_ZEBRA_DEBUG_NHG)
3135 zlog_debug(
3136 "%s: id %u, backup nexthops not supported",
3137 __func__, id);
3138 return NULL;
3139 }
3140
70f3cda6
SW		 3141 if (newhop->type == NEXTHOP_TYPE_BLACKHOLE) {
3142 if (IS_ZEBRA_DEBUG_NHG)
3143 zlog_debug(
3144 "%s: id %u, blackhole nexthop not supported",
3145 __func__, id);
3146 return NULL;
3147 }
3148
3149 if (newhop->type == NEXTHOP_TYPE_IFINDEX) {
3150 if (IS_ZEBRA_DEBUG_NHG)
3151 zlog_debug(
3152 "%s: id %u, nexthop without gateway not supported",
3153 __func__, id);
3154 return NULL;
3155 }
3156
70347b7a
SW		 3157 if (!newhop->ifindex) {
3158 if (IS_ZEBRA_DEBUG_NHG)
3159 zlog_debug(
70f3cda6 3160 "%s: id %u, nexthop without ifindex is not supported",
70347b7a
SW		 3161 __func__, id);
3162 return NULL;
3163 }
1f655680 3164 SET_FLAG(newhop->flags, NEXTHOP_FLAG_ACTIVE);
70347b7a 3165 }
0885b1e3
SW		 3166
3167 zebra_nhe_init(&lookup, afi, nhg->nexthop);
3168 lookup.nhg.nexthop = nhg->nexthop;
3169 lookup.id = id;
3170 lookup.type = type;
3171
dd1e105f
SW		 3172 old = zebra_nhg_lookup_id(id);
3173
3174 if (old) {
3175 /*
3176 * This is a replace, just release NHE from ID for now, The
84591282
SW		 3177 * depends/dependents may still be used in the replacement so
3178 * we don't touch them other than to remove their refs to their
3179 * old parent.
dd1e105f 3180 */
1f655680 3181 replace = true;
dd1e105f 3182 hash_release(zrouter.nhgs_id, old);
84591282
SW		 3183
3184 /* Free all the things */
3185 zebra_nhg_release_all_deps(old);
dd1e105f
SW		 3186 }
3187
0885b1e3
SW		 3188 new = zebra_nhg_rib_find_nhe(&lookup, afi);
3189
1f655680
SW		 3190 zebra_nhg_increment_ref(new);
3191
ee94437e
MS		 3192 /* Capture zapi client info */
3193 new->zapi_instance = instance;
3194 new->zapi_session = session;
3195
1f655680
SW		 3196 zebra_nhg_set_valid_if_active(new);
3197
3198 zebra_nhg_install_kernel(new);
3199
dd1e105f 3200 if (old) {
8155e8c5
SW		 3201 /*
3202 * Check to handle recving DEL while routes still in use then
3203 * a replace.
3204 *
3205 * In this case we would have decremented the refcnt already
3206 * but set the FLAG here. Go ahead and increment once to fix
3207 * the misordering we have been sent.
3208 */
3209 if (CHECK_FLAG(old->flags, NEXTHOP_GROUP_PROTO_RELEASED))
3210 zebra_nhg_increment_ref(old);
3211
1f655680 3212 rib_handle_nhg_replace(old, new);
dd1e105f 3213
1f655680
SW		 3214 /* if this != 1 at this point, we have a bug */
3215 assert(old->refcnt == 1);
0885b1e3 3216
1f655680
SW		 3217 /* We have to decrement its singletons
3218 * because some might not exist in NEW.
3219 */
3220 if (!zebra_nhg_depends_is_empty(old)) {
3221 frr_each (nhg_connected_tree, &old->nhg_depends,
3222 rb_node_dep)
3223 zebra_nhg_decrement_ref(rb_node_dep->nhe);
3224 }
3225
1f655680
SW		 3226 /* Dont call the dec API, we dont want to uninstall the ID */
3227 old->refcnt = 0;
3228 zebra_nhg_free(old);
3229 old = NULL;
0885b1e3
SW		 3230 }
3231
3232 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
dd1e105f 3233 zlog_debug("%s: %s nhe %p (%u), vrf %d, type %s", __func__,
1f655680 3234 (replace ? "replaced" : "added"), new, new->id,
dd1e105f 3235 new->vrf_id, zebra_route_string(new->type));
0885b1e3
SW		 3236
3237 return new;
3238}
3239
1f655680 3240/* Delete NHE from upper level proto, caller must decrement ref */
aaa42e05 3241struct nhg_hash_entry *zebra_nhg_proto_del(uint32_t id, int type)
0885b1e3
SW		 3242{
3243 struct nhg_hash_entry *nhe;
3244
3245 nhe = zebra_nhg_lookup_id(id);
3246
3247 if (!nhe) {
8155e8c5 3248 if (IS_ZEBRA_DEBUG_NHG)
0885b1e3
SW		 3249 zlog_debug("%s: id %u, lookup failed", __func__, id);
3250
3251 return NULL;
3252 }
3253
aaa42e05
SW		 3254 if (type != nhe->type) {
3255 if (IS_ZEBRA_DEBUG_NHG)
3256 zlog_debug(
3257 "%s: id %u, type %s mismatch, sent by %s, ignoring",
3258 __func__, id, zebra_route_string(nhe->type),
3259 zebra_route_string(type));
3260 return NULL;
3261 }
3262
8155e8c5
SW		 3263 if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_PROTO_RELEASED)) {
3264 if (IS_ZEBRA_DEBUG_NHG)
3265 zlog_debug("%s: id %u, already released", __func__, id);
3266
3267 return NULL;
3268 }
3269
3270 SET_FLAG(nhe->flags, NEXTHOP_GROUP_PROTO_RELEASED);
3271
1f655680 3272 if (nhe->refcnt > 1) {
0885b1e3 3273 if (IS_ZEBRA_DEBUG_NHG)
1f655680
SW		 3274 zlog_debug(
3275 "%s: id %u, still being used by routes refcnt %u",
3276 __func__, nhe->id, nhe->refcnt);
9c6c48bc 3277 return nhe;
0885b1e3
SW		 3278 }
3279
3280 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
3281 zlog_debug("%s: deleted nhe %p (%u), vrf %d, type %s", __func__,
3282 nhe, nhe->id, nhe->vrf_id,
3283 zebra_route_string(nhe->type));
3284
3285 return nhe;
3286}
3287
24db1a7b
SW		 3288struct nhg_score_proto_iter {
3289 int type;
8f830b8c 3290 struct list *found;
24db1a7b
SW		 3291};
3292
3293static void zebra_nhg_score_proto_entry(struct hash_bucket *bucket, void *arg)
3294{
3295 struct nhg_hash_entry *nhe;
3296 struct nhg_score_proto_iter *iter;
3297
3298 nhe = (struct nhg_hash_entry *)bucket->data;
3299 iter = arg;
3300
3301 /* Needs to match type and outside zebra ID space */
65f137fe 3302 if (nhe->type == iter->type && PROTO_OWNED(nhe)) {
24db1a7b
SW		 3303 if (IS_ZEBRA_DEBUG_NHG_DETAIL)
3304 zlog_debug(
3305 "%s: found nhe %p (%u), vrf %d, type %s after client disconnect",
3306 __func__, nhe, nhe->id, nhe->vrf_id,
3307 zebra_route_string(nhe->type));
3308
8f830b8c
SW		 3309 /* Add to removal list */
3310 listnode_add(iter->found, nhe);
24db1a7b
SW		 3311 }
3312}
3313
3314/* Remove specific by proto NHGs */
3315unsigned long zebra_nhg_score_proto(int type)
3316{
8f830b8c 3317 struct nhg_hash_entry *nhe;
24db1a7b 3318 struct nhg_score_proto_iter iter = {};
8f830b8c
SW		 3319 struct listnode *ln;
3320 unsigned long count;
24db1a7b
SW		 3321
3322 iter.type = type;
8f830b8c 3323 iter.found = list_new();
24db1a7b 3324
8f830b8c 3325 /* Find matching entries to remove */
24db1a7b
SW		 3326 hash_iterate(zrouter.nhgs_id, zebra_nhg_score_proto_entry, &iter);
3327
8f830b8c
SW		 3328 /* Now remove them */
3329 for (ALL_LIST_ELEMENTS_RO(iter.found, ln, nhe)) {
3330 /*
3331 * This should be the last ref if we remove client routes too,
3332 * and thus should remove and free them.
3333 */
3334 zebra_nhg_decrement_ref(nhe);
3335 }
3336
3337 count = iter.found->count;
3338 list_delete(&iter.found);
3339
3340 return count;
24db1a7b 3341}
FRRouting mirror