]> git.proxmox.com Git - mirror_frr.git/blob - isisd/isis_spf.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
isisd: calculate flex-algo constraint spf
[mirror_frr.git] / isisd / isis_spf.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * IS-IS Rout(e)ing protocol - isis_spf.c
4 * The SPT algorithm
5 *
6 * Copyright (C) 2001,2002 Sampo Saaristo
7 * Tampere University of Technology
8 * Institute of Communications Engineering
9 * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org>
10 */
11
12 #include <zebra.h>
13
14 #include "frrevent.h"
15 #include "linklist.h"
16 #include "vty.h"
17 #include "log.h"
18 #include "command.h"
19 #include "termtable.h"
20 #include "memory.h"
21 #include "prefix.h"
22 #include "filter.h"
23 #include "if.h"
24 #include "hash.h"
25 #include "table.h"
26 #include "spf_backoff.h"
27 #include "srcdest_table.h"
28 #include "vrf.h"
29
30 #include "isis_errors.h"
31 #include "isis_constants.h"
32 #include "isis_common.h"
33 #include "isis_flags.h"
34 #include "isisd.h"
35 #include "isis_misc.h"
36 #include "isis_adjacency.h"
37 #include "isis_circuit.h"
38 #include "isis_pdu.h"
39 #include "isis_lsp.h"
40 #include "isis_dynhn.h"
41 #include "isis_spf.h"
42 #include "isis_route.h"
43 #include "isis_csm.h"
44 #include "isis_mt.h"
45 #include "isis_tlvs.h"
46 #include "isis_flex_algo.h"
47 #include "isis_zebra.h"
48 #include "fabricd.h"
49 #include "isis_spf_private.h"
50
51 DEFINE_MTYPE_STATIC(ISISD, ISIS_SPFTREE, "ISIS SPFtree");
52 DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info");
53 DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_ADJ, "ISIS SPF Adjacency");
54 DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX, "ISIS vertex");
55 DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX_ADJ, "ISIS SPF Vertex Adjacency");
56
57 static void spf_adj_list_parse_lsp(struct isis_spftree *spftree,
58 struct list *adj_list, struct isis_lsp *lsp,
59 const uint8_t *pseudo_nodeid,
60 uint32_t pseudo_metric);
61
62 /*
63 * supports the given af ?
64 */
65 static bool speaks(uint8_t *protocols, uint8_t count, int family)
66 {
67 for (uint8_t i = 0; i < count; i++) {
68 if (family == AF_INET && protocols[i] == NLPID_IP)
69 return true;
70 if (family == AF_INET6 && protocols[i] == NLPID_IPV6)
71 return true;
72 }
73 return false;
74 }
75
76 struct isis_spf_run {
77 struct isis_area *area;
78 int level;
79 };
80
81 /* 7.2.7 */
82 static void remove_excess_adjs(struct list *adjs)
83 {
84 struct listnode *node, *excess = NULL;
85 struct isis_vertex_adj *vadj, *candidate = NULL;
86 int comp;
87
88 for (ALL_LIST_ELEMENTS_RO(adjs, node, vadj)) {
89 struct isis_adjacency *adj, *candidate_adj;
90
91 adj = vadj->sadj->adj;
92 assert(adj);
93
94 if (excess == NULL)
95 excess = node;
96 candidate = listgetdata(excess);
97 candidate_adj = candidate->sadj->adj;
98
99 if (candidate_adj->sys_type < adj->sys_type) {
100 excess = node;
101 continue;
102 }
103 if (candidate_adj->sys_type > adj->sys_type)
104 continue;
105
106 comp = memcmp(candidate_adj->sysid, adj->sysid,
107 ISIS_SYS_ID_LEN);
108 if (comp > 0) {
109 excess = node;
110 continue;
111 }
112 if (comp < 0)
113 continue;
114
115 if (candidate_adj->circuit->idx > adj->circuit->idx) {
116 excess = node;
117 continue;
118 }
119
120 if (candidate_adj->circuit->idx < adj->circuit->idx)
121 continue;
122
123 comp = memcmp(candidate_adj->snpa, adj->snpa, ETH_ALEN);
124 if (comp > 0) {
125 excess = node;
126 continue;
127 }
128 }
129
130 list_delete_node(adjs, excess);
131
132 return;
133 }
134
135 const char *vtype2string(enum vertextype vtype)
136 {
137 switch (vtype) {
138 case VTYPE_PSEUDO_IS:
139 return "pseudo_IS";
140 case VTYPE_PSEUDO_TE_IS:
141 return "pseudo_TE-IS";
142 case VTYPE_NONPSEUDO_IS:
143 return "IS";
144 case VTYPE_NONPSEUDO_TE_IS:
145 return "TE-IS";
146 case VTYPE_ES:
147 return "ES";
148 case VTYPE_IPREACH_INTERNAL:
149 return "IP internal";
150 case VTYPE_IPREACH_EXTERNAL:
151 return "IP external";
152 case VTYPE_IPREACH_TE:
153 return "IP TE";
154 case VTYPE_IP6REACH_INTERNAL:
155 return "IP6 internal";
156 case VTYPE_IP6REACH_EXTERNAL:
157 return "IP6 external";
158 default:
159 return "UNKNOWN";
160 }
161 return NULL; /* Not reached */
162 }
163
164 const char *vid2string(const struct isis_vertex *vertex, char *buff, int size)
165 {
166 if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) {
167 const char *hostname = print_sys_hostname(vertex->N.id);
168 strlcpy(buff, hostname, size);
169 return buff;
170 }
171
172 if (VTYPE_IP(vertex->type)) {
173 srcdest2str(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, buff,
174 size);
175 return buff;
176 }
177
178 return "UNKNOWN";
179 }
180
181 static bool prefix_sid_cmp(const void *value1, const void *value2)
182 {
183 const struct isis_vertex *c1 = value1;
184 const struct isis_vertex *c2 = value2;
185
186 if (CHECK_FLAG(c1->N.ip.sr.sid.flags,
187 ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL)
188 != CHECK_FLAG(c2->N.ip.sr.sid.flags,
189 ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL))
190 return false;
191
192 return c1->N.ip.sr.sid.value == c2->N.ip.sr.sid.value;
193 }
194
195 static unsigned int prefix_sid_key_make(const void *value)
196 {
197 const struct isis_vertex *vertex = value;
198
199 return jhash_1word(vertex->N.ip.sr.sid.value, 0);
200 }
201
202 struct isis_vertex *isis_spf_prefix_sid_lookup(struct isis_spftree *spftree,
203 struct isis_prefix_sid *psid)
204 {
205 struct isis_vertex lookup = {};
206
207 lookup.N.ip.sr.sid = *psid;
208 return hash_lookup(spftree->prefix_sids, &lookup);
209 }
210
211 void isis_vertex_adj_free(void *arg)
212 {
213 struct isis_vertex_adj *vadj = arg;
214
215 XFREE(MTYPE_ISIS_VERTEX_ADJ, vadj);
216 }
217
218 static struct isis_vertex *isis_vertex_new(struct isis_spftree *spftree,
219 void *id,
220 enum vertextype vtype)
221 {
222 struct isis_vertex *vertex;
223
224 vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex));
225
226 isis_vertex_id_init(vertex, id, vtype);
227
228 vertex->Adj_N = list_new();
229 vertex->Adj_N->del = isis_vertex_adj_free;
230 vertex->parents = list_new();
231
232 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) {
233 vertex->firsthops = hash_create(isis_vertex_queue_hash_key,
234 isis_vertex_queue_hash_cmp,
235 NULL);
236 }
237
238 return vertex;
239 }
240
241 void isis_vertex_del(struct isis_vertex *vertex)
242 {
243 list_delete(&vertex->Adj_N);
244 list_delete(&vertex->parents);
245 hash_clean_and_free(&vertex->firsthops, NULL);
246
247 memset(vertex, 0, sizeof(struct isis_vertex));
248 XFREE(MTYPE_ISIS_VERTEX, vertex);
249 }
250
251 struct isis_vertex_adj *
252 isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex,
253 struct list *vadj_list, struct isis_spf_adj *sadj,
254 struct isis_prefix_sid *psid, bool last_hop)
255 {
256 struct isis_vertex_adj *vadj;
257
258 vadj = XCALLOC(MTYPE_ISIS_VERTEX_ADJ, sizeof(*vadj));
259 vadj->sadj = sadj;
260 if (spftree->area->srdb.enabled && psid) {
261 if (vertex->N.ip.sr.present
262 && vertex->N.ip.sr.sid.value != psid->value)
263 zlog_warn(
264 "ISIS-SPF: ignoring different Prefix-SID for route %pFX",
265 &vertex->N.ip.p.dest);
266 else {
267 vadj->sr.sid = *psid;
268 vadj->sr.label = sr_prefix_out_label(
269 spftree->lspdb, vertex->N.ip.p.dest.family,
270 psid, sadj->id, last_hop);
271 if (vadj->sr.label != MPLS_INVALID_LABEL)
272 vadj->sr.present = true;
273 }
274 }
275 listnode_add(vadj_list, vadj);
276
277 return vadj;
278 }
279
280 static void isis_vertex_adj_del(struct isis_vertex *vertex,
281 struct isis_adjacency *adj)
282 {
283 struct isis_vertex_adj *vadj;
284 struct listnode *node, *nextnode;
285
286 if (!vertex)
287 return;
288
289 for (ALL_LIST_ELEMENTS(vertex->Adj_N, node, nextnode, vadj)) {
290 if (vadj->sadj->adj == adj) {
291 listnode_delete(vertex->Adj_N, vadj);
292 isis_vertex_adj_free(vadj);
293 }
294 }
295 return;
296 }
297
298 bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
299 const struct isis_vertex *vertex,
300 const struct isis_spf_adj *sadj)
301 {
302 struct isis_vertex_adj *tmp;
303 struct listnode *node;
304
305 for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, tmp)) {
306 if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) {
307 if (memcmp(sadj->id, tmp->sadj->id, sizeof(sadj->id))
308 == 0)
309 return true;
310 } else {
311 if (sadj->adj == tmp->sadj->adj)
312 return true;
313 }
314 }
315
316 return false;
317 }
318
319 static void isis_spf_adj_free(void *arg)
320 {
321 struct isis_spf_adj *sadj = arg;
322
323 XFREE(MTYPE_ISIS_SPF_ADJ, sadj);
324 }
325
326 static void _isis_spftree_init(struct isis_spftree *tree)
327 {
328 isis_vertex_queue_init(&tree->tents, "IS-IS SPF tents", true);
329 isis_vertex_queue_init(&tree->paths, "IS-IS SPF paths", false);
330 tree->route_table = srcdest_table_init();
331 tree->route_table->cleanup = isis_route_node_cleanup;
332 tree->route_table->info = isis_route_table_info_alloc(tree->algorithm);
333 tree->route_table_backup = srcdest_table_init();
334 tree->route_table_backup->info =
335 isis_route_table_info_alloc(tree->algorithm);
336 tree->route_table_backup->cleanup = isis_route_node_cleanup;
337 tree->prefix_sids = hash_create(prefix_sid_key_make, prefix_sid_cmp,
338 "SR Prefix-SID Entries");
339 tree->sadj_list = list_new();
340 tree->sadj_list->del = isis_spf_adj_free;
341 isis_rlfa_list_init(tree);
342 tree->lfa.remote.pc_spftrees = list_new();
343 tree->lfa.remote.pc_spftrees->del = (void (*)(void *))isis_spftree_del;
344 if (tree->type == SPF_TYPE_RLFA || tree->type == SPF_TYPE_TI_LFA) {
345 isis_spf_node_list_init(&tree->lfa.p_space);
346 isis_spf_node_list_init(&tree->lfa.q_space);
347 }
348 }
349
350 struct isis_spftree *
351 isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb,
352 const uint8_t *sysid, int level, enum spf_tree_id tree_id,
353 enum spf_type type, uint8_t flags, uint8_t algorithm)
354 {
355 struct isis_spftree *tree;
356
357 tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree));
358
359 tree->area = area;
360 tree->lspdb = lspdb;
361 tree->last_run_timestamp = 0;
362 tree->last_run_monotime = 0;
363 tree->last_run_duration = 0;
364 tree->runcount = 0;
365 tree->type = type;
366 memcpy(tree->sysid, sysid, ISIS_SYS_ID_LEN);
367 tree->level = level;
368 tree->tree_id = tree_id;
369 tree->family = (tree->tree_id == SPFTREE_IPV4) ? AF_INET : AF_INET6;
370 tree->flags = flags;
371 tree->algorithm = algorithm;
372
373 _isis_spftree_init(tree);
374
375 return tree;
376 }
377
378 static void _isis_spftree_del(struct isis_spftree *spftree)
379 {
380 hash_clean_and_free(&spftree->prefix_sids, NULL);
381 isis_zebra_rlfa_unregister_all(spftree);
382 isis_rlfa_list_clear(spftree);
383 list_delete(&spftree->lfa.remote.pc_spftrees);
384 if (spftree->type == SPF_TYPE_RLFA
385 || spftree->type == SPF_TYPE_TI_LFA) {
386 isis_spf_node_list_clear(&spftree->lfa.q_space);
387 isis_spf_node_list_clear(&spftree->lfa.p_space);
388 }
389 isis_spf_node_list_clear(&spftree->adj_nodes);
390 list_delete(&spftree->sadj_list);
391 isis_vertex_queue_free(&spftree->tents);
392 isis_vertex_queue_free(&spftree->paths);
393 isis_route_table_info_free(spftree->route_table->info);
394 isis_route_table_info_free(spftree->route_table_backup->info);
395 }
396
397 void isis_spftree_del(struct isis_spftree *spftree)
398 {
399 _isis_spftree_del(spftree);
400
401 route_table_finish(spftree->route_table);
402 route_table_finish(spftree->route_table_backup);
403 spftree->route_table = NULL;
404
405 XFREE(MTYPE_ISIS_SPFTREE, spftree);
406 return;
407 }
408
409 #ifndef FABRICD
410 static void isis_spftree_clear(struct isis_spftree *spftree)
411 {
412 _isis_spftree_del(spftree);
413 _isis_spftree_init(spftree);
414 }
415 #endif /* ifndef FABRICD */
416
417 static void isis_spftree_adj_del(struct isis_spftree *spftree,
418 struct isis_adjacency *adj)
419 {
420 struct listnode *node;
421 struct isis_vertex *v;
422 if (!adj)
423 return;
424 assert(!isis_vertex_queue_count(&spftree->tents));
425 for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, v))
426 isis_vertex_adj_del(v, adj);
427 return;
428 }
429
430 void spftree_area_init(struct isis_area *area)
431 {
432 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
433 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
434 if (!(area->is_type & level))
435 continue;
436 if (area->spftree[tree][level - 1])
437 continue;
438
439 area->spftree[tree][level - 1] = isis_spftree_new(
440 area, &area->lspdb[level - 1],
441 area->isis->sysid, level, tree,
442 SPF_TYPE_FORWARD, 0, SR_ALGORITHM_SPF);
443 }
444 }
445 }
446
447 void spftree_area_del(struct isis_area *area)
448 {
449 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
450 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
451 if (!(area->is_type & level))
452 continue;
453 if (!area->spftree[tree][level - 1])
454 continue;
455
456 isis_spftree_del(area->spftree[tree][level - 1]);
457 }
458 }
459 }
460
461 static int spf_adj_state_change(struct isis_adjacency *adj)
462 {
463 struct isis_area *area = adj->circuit->area;
464
465 if (adj->adj_state == ISIS_ADJ_UP)
466 return 0;
467
468 /* Remove adjacency from all SPF trees. */
469 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
470 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
471 if (!(area->is_type & level))
472 continue;
473 if (!area->spftree[tree][level - 1])
474 continue;
475 isis_spftree_adj_del(area->spftree[tree][level - 1],
476 adj);
477 }
478 }
479
480 if (fabricd_spftree(area) != NULL)
481 isis_spftree_adj_del(fabricd_spftree(area), adj);
482
483 return 0;
484 }
485
486 /*
487 * Find the system LSP: returns the LSP in our LSP database
488 * associated with the given system ID.
489 */
490 struct isis_lsp *isis_root_system_lsp(struct lspdb_head *lspdb,
491 const uint8_t *sysid)
492 {
493 struct isis_lsp *lsp;
494 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
495
496 memcpy(lspid, sysid, ISIS_SYS_ID_LEN);
497 LSP_PSEUDO_ID(lspid) = 0;
498 LSP_FRAGMENT(lspid) = 0;
499 lsp = lsp_search(lspdb, lspid);
500 if (lsp && lsp->hdr.rem_lifetime != 0)
501 return lsp;
502 return NULL;
503 }
504
505 /*
506 * Add this IS to the root of SPT
507 */
508 static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree)
509 {
510 struct isis_vertex *vertex;
511 #ifdef EXTREME_DEBUG
512 char buff[VID2STR_BUFFER];
513 #endif /* EXTREME_DEBUG */
514
515 vertex = isis_vertex_new(spftree, spftree->sysid,
516 spftree->area->oldmetric
517 ? VTYPE_NONPSEUDO_IS
518 : VTYPE_NONPSEUDO_TE_IS);
519 isis_vertex_queue_append(&spftree->paths, vertex);
520
521 #ifdef EXTREME_DEBUG
522 if (IS_DEBUG_SPF_EVENTS)
523 zlog_debug(
524 "ISIS-SPF: added this IS %s %s depth %d dist %d to PATHS",
525 vtype2string(vertex->type),
526 vid2string(vertex, buff, sizeof(buff)), vertex->depth,
527 vertex->d_N);
528 #endif /* EXTREME_DEBUG */
529
530 return vertex;
531 }
532
533 static void vertex_add_parent_firsthop(struct hash_bucket *bucket, void *arg)
534 {
535 struct isis_vertex *vertex = arg;
536 struct isis_vertex *hop = bucket->data;
537
538 (void)hash_get(vertex->firsthops, hop, hash_alloc_intern);
539 }
540
541 static void vertex_update_firsthops(struct isis_vertex *vertex,
542 struct isis_vertex *parent)
543 {
544 if (vertex->d_N <= 2)
545 (void)hash_get(vertex->firsthops, vertex, hash_alloc_intern);
546
547 if (vertex->d_N < 2 || !parent)
548 return;
549
550 hash_iterate(parent->firsthops, vertex_add_parent_firsthop, vertex);
551 }
552
553 /*
554 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
555 */
556 static struct isis_vertex *
557 isis_spf_add2tent(struct isis_spftree *spftree, enum vertextype vtype, void *id,
558 uint32_t cost, int depth, struct isis_spf_adj *sadj,
559 struct isis_prefix_sid *psid, struct isis_vertex *parent)
560 {
561 struct isis_vertex *vertex;
562 struct listnode *node;
563 bool last_hop;
564 char buff[VID2STR_BUFFER];
565
566 vertex = isis_find_vertex(&spftree->paths, id, vtype);
567 if (vertex != NULL) {
568 zlog_err(
569 "%s: vertex %s of type %s already in PATH; check for sysId collisions with established neighbors",
570 __func__, vid2string(vertex, buff, sizeof(buff)),
571 vtype2string(vertex->type));
572 return NULL;
573 }
574 vertex = isis_find_vertex(&spftree->tents, id, vtype);
575 if (vertex != NULL) {
576 zlog_err(
577 "%s: vertex %s of type %s already in TENT; check for sysId collisions with established neighbors",
578 __func__, vid2string(vertex, buff, sizeof(buff)),
579 vtype2string(vertex->type));
580 return NULL;
581 }
582
583 vertex = isis_vertex_new(spftree, id, vtype);
584 vertex->d_N = cost;
585 vertex->depth = depth;
586 if (VTYPE_IP(vtype) && spftree->area->srdb.enabled && psid) {
587 struct isis_area *area = spftree->area;
588 struct isis_vertex *vertex_psid;
589
590 /*
591 * Check if the Prefix-SID is already in use by another prefix.
592 */
593 vertex_psid = isis_spf_prefix_sid_lookup(spftree, psid);
594 if (vertex_psid
595 && !prefix_same(&vertex_psid->N.ip.p.dest,
596 &vertex->N.ip.p.dest)) {
597 flog_warn(
598 EC_ISIS_SID_COLLISION,
599 "ISIS-Sr (%s): collision detected, prefixes %pFX and %pFX share the same SID %s (%u)",
600 area->area_tag, &vertex->N.ip.p.dest,
601 &vertex_psid->N.ip.p.dest,
602 CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_VALUE)
603 ? "label"
604 : "index",
605 psid->value);
606 psid = NULL;
607 } else {
608 bool local;
609
610 local = (vertex->depth == 1);
611 vertex->N.ip.sr.sid = *psid;
612 vertex->N.ip.sr.label =
613 sr_prefix_in_label(area, psid, local);
614 vertex->N.ip.sr.algorithm = psid->algorithm;
615
616 if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL)
617 vertex->N.ip.sr.present = true;
618
619 #ifndef FABRICD
620 if (flex_algo_id_valid(spftree->algorithm) &&
621 !isis_flex_algo_elected_supported(
622 spftree->algorithm, spftree->area)) {
623 vertex->N.ip.sr.present = false;
624 vertex->N.ip.sr.label = MPLS_INVALID_LABEL;
625 }
626 #endif /* ifndef FABRICD */
627
628 (void)hash_get(spftree->prefix_sids, vertex,
629 hash_alloc_intern);
630 }
631 }
632
633 if (parent) {
634 listnode_add(vertex->parents, parent);
635 }
636
637 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC))
638 vertex_update_firsthops(vertex, parent);
639
640 last_hop = (vertex->depth == 2);
641 if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) {
642 struct isis_vertex_adj *parent_vadj;
643
644 for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, parent_vadj))
645 isis_vertex_adj_add(spftree, vertex, vertex->Adj_N,
646 parent_vadj->sadj, psid, last_hop);
647 } else if (sadj) {
648 isis_vertex_adj_add(spftree, vertex, vertex->Adj_N, sadj, psid,
649 last_hop);
650 }
651
652 #ifdef EXTREME_DEBUG
653 if (IS_DEBUG_SPF_EVENTS)
654 zlog_debug(
655 "ISIS-SPF: add to TENT %s %s %s depth %d dist %d adjcount %d",
656 print_sys_hostname(vertex->N.id),
657 vtype2string(vertex->type),
658 vid2string(vertex, buff, sizeof(buff)), vertex->depth,
659 vertex->d_N, listcount(vertex->Adj_N));
660 #endif /* EXTREME_DEBUG */
661
662 isis_vertex_queue_insert(&spftree->tents, vertex);
663 return vertex;
664 }
665
666 static void isis_spf_add_local(struct isis_spftree *spftree,
667 enum vertextype vtype, void *id,
668 struct isis_spf_adj *sadj, uint32_t cost,
669 struct isis_prefix_sid *psid,
670 struct isis_vertex *parent)
671 {
672 struct isis_vertex *vertex;
673
674 vertex = isis_find_vertex(&spftree->tents, id, vtype);
675
676 if (vertex) {
677 /* C.2.5 c) */
678 if (vertex->d_N == cost) {
679 if (sadj) {
680 bool last_hop = (vertex->depth == 2);
681
682 isis_vertex_adj_add(spftree, vertex,
683 vertex->Adj_N, sadj, psid,
684 last_hop);
685 }
686 /* d) */
687 if (!CHECK_FLAG(spftree->flags,
688 F_SPFTREE_NO_ADJACENCIES)
689 && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
690 remove_excess_adjs(vertex->Adj_N);
691 if (parent && (listnode_lookup(vertex->parents, parent)
692 == NULL))
693 listnode_add(vertex->parents, parent);
694 return;
695 } else if (vertex->d_N < cost) {
696 /* e) do nothing */
697 return;
698 } else { /* vertex->d_N > cost */
699 /* f) */
700 isis_vertex_queue_delete(&spftree->tents, vertex);
701 isis_vertex_del(vertex);
702 }
703 }
704
705 isis_spf_add2tent(spftree, vtype, id, cost, 1, sadj, psid, parent);
706 return;
707 }
708
709 static void process_N(struct isis_spftree *spftree, enum vertextype vtype,
710 void *id, uint32_t dist, uint16_t depth,
711 struct isis_prefix_sid *psid, struct isis_vertex *parent)
712 {
713 struct isis_vertex *vertex;
714 #ifdef EXTREME_DEBUG
715 char buff[VID2STR_BUFFER];
716 #endif
717
718 assert(spftree && parent);
719
720 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)
721 && !VTYPE_IS(vtype))
722 return;
723
724 struct prefix_pair p;
725 if (vtype >= VTYPE_IPREACH_INTERNAL) {
726 memcpy(&p, id, sizeof(p));
727 apply_mask(&p.dest);
728 apply_mask(&p.src);
729 id = &p;
730 }
731
732 /* RFC3787 section 5.1 */
733 if (spftree->area->newmetric == 1) {
734 if (dist > MAX_WIDE_PATH_METRIC)
735 return;
736 }
737 /* C.2.6 b) */
738 else if (spftree->area->oldmetric == 1) {
739 if (dist > MAX_NARROW_PATH_METRIC)
740 return;
741 }
742
743 /* c) */
744 vertex = isis_find_vertex(&spftree->paths, id, vtype);
745 if (vertex) {
746 #ifdef EXTREME_DEBUG
747 if (IS_DEBUG_SPF_EVENTS)
748 zlog_debug(
749 "ISIS-SPF: process_N %s %s %s dist %d already found from PATH",
750 print_sys_hostname(vertex->N.id),
751 vtype2string(vtype),
752 vid2string(vertex, buff, sizeof(buff)), dist);
753 #endif /* EXTREME_DEBUG */
754 assert(dist >= vertex->d_N);
755 return;
756 }
757
758 vertex = isis_find_vertex(&spftree->tents, id, vtype);
759 /* d) */
760 if (vertex) {
761 /* 1) */
762 #ifdef EXTREME_DEBUG
763 if (IS_DEBUG_SPF_EVENTS)
764 zlog_debug(
765 "ISIS-SPF: process_N %s %s %s dist %d parent %s adjcount %d",
766 print_sys_hostname(vertex->N.id),
767 vtype2string(vtype),
768 vid2string(vertex, buff, sizeof(buff)), dist,
769 (parent ? print_sys_hostname(parent->N.id)
770 : "null"),
771 (parent ? listcount(parent->Adj_N) : 0));
772 #endif /* EXTREME_DEBUG */
773 if (vertex->d_N == dist) {
774 struct listnode *node;
775 struct isis_vertex_adj *parent_vadj;
776 for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node,
777 parent_vadj))
778 if (!isis_vertex_adj_exists(
779 spftree, vertex,
780 parent_vadj->sadj)) {
781 bool last_hop = (vertex->depth == 2);
782
783 isis_vertex_adj_add(spftree, vertex,
784 vertex->Adj_N,
785 parent_vadj->sadj,
786 psid, last_hop);
787 }
788 if (CHECK_FLAG(spftree->flags,
789 F_SPFTREE_HOPCOUNT_METRIC))
790 vertex_update_firsthops(vertex, parent);
791 /* 2) */
792 if (!CHECK_FLAG(spftree->flags,
793 F_SPFTREE_NO_ADJACENCIES)
794 && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
795 remove_excess_adjs(vertex->Adj_N);
796 if (listnode_lookup(vertex->parents, parent) == NULL)
797 listnode_add(vertex->parents, parent);
798 return;
799 } else if (vertex->d_N < dist) {
800 return;
801 /* 4) */
802 } else {
803 isis_vertex_queue_delete(&spftree->tents, vertex);
804 isis_vertex_del(vertex);
805 }
806 }
807
808 #ifdef EXTREME_DEBUG
809 if (IS_DEBUG_SPF_EVENTS)
810 zlog_debug(
811 "ISIS-SPF: process_N add2tent %s %s dist %d parent %s",
812 print_sys_hostname(id), vtype2string(vtype), dist,
813 (parent ? print_sys_hostname(parent->N.id) : "null"));
814 #endif /* EXTREME_DEBUG */
815
816 isis_spf_add2tent(spftree, vtype, id, dist, depth, NULL, psid, parent);
817 return;
818 }
819
820 /*
821 * C.2.6 Step 1
822 */
823 static int isis_spf_process_lsp(struct isis_spftree *spftree,
824 struct isis_lsp *lsp, uint32_t cost,
825 uint16_t depth, uint8_t *root_sysid,
826 struct isis_vertex *parent)
827 {
828 bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id);
829 struct listnode *fragnode = NULL;
830 uint32_t dist;
831 enum vertextype vtype;
832 static const uint8_t null_sysid[ISIS_SYS_ID_LEN];
833 struct isis_mt_router_info *mt_router_info = NULL;
834 struct prefix_pair ip_info;
835 bool has_valid_psid;
836
837 if (isis_lfa_excise_node_check(spftree, lsp->hdr.lsp_id)) {
838 if (IS_DEBUG_LFA)
839 zlog_debug("ISIS-LFA: excising node %s",
840 print_sys_hostname(lsp->hdr.lsp_id));
841 return ISIS_OK;
842 }
843
844 if (!lsp->tlvs)
845 return ISIS_OK;
846
847 if (spftree->mtid != ISIS_MT_IPV4_UNICAST)
848 mt_router_info = isis_tlvs_lookup_mt_router_info(lsp->tlvs,
849 spftree->mtid);
850
851 if (!pseudo_lsp && (spftree->mtid == ISIS_MT_IPV4_UNICAST
852 && !speaks(lsp->tlvs->protocols_supported.protocols,
853 lsp->tlvs->protocols_supported.count,
854 spftree->family))
855 && !mt_router_info)
856 return ISIS_OK;
857
858 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
859 bool no_overload = (pseudo_lsp
860 || (spftree->mtid == ISIS_MT_IPV4_UNICAST
861 && !ISIS_MASK_LSP_OL_BIT(lsp->hdr.lsp_bits))
862 || (mt_router_info && !mt_router_info->overload));
863
864 lspfragloop:
865 if (lsp->hdr.seqno == 0) {
866 zlog_warn("%s: lsp with 0 seq_num - ignore", __func__);
867 return ISIS_WARNING;
868 }
869
870 #ifdef EXTREME_DEBUG
871 if (IS_DEBUG_SPF_EVENTS)
872 zlog_debug("ISIS-SPF: process_lsp %s",
873 print_sys_hostname(lsp->hdr.lsp_id));
874 #endif /* EXTREME_DEBUG */
875
876 if (no_overload) {
877 if ((pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
878 && spftree->area->oldmetric) {
879 struct isis_oldstyle_reach *r;
880 for (r = (struct isis_oldstyle_reach *)
881 lsp->tlvs->oldstyle_reach.head;
882 r; r = r->next) {
883 if (fabricd)
884 continue;
885
886 /* C.2.6 a) */
887 /* Two way connectivity */
888 if (!LSP_PSEUDO_ID(r->id)
889 && !memcmp(r->id, root_sysid,
890 ISIS_SYS_ID_LEN))
891 continue;
892 if (!pseudo_lsp
893 && !memcmp(r->id, null_sysid,
894 ISIS_SYS_ID_LEN))
895 continue;
896 dist = cost + r->metric;
897 process_N(spftree,
898 LSP_PSEUDO_ID(r->id)
899 ? VTYPE_PSEUDO_IS
900 : VTYPE_NONPSEUDO_IS,
901 (void *)r->id, dist, depth + 1, NULL,
902 parent);
903 }
904 }
905
906 if (spftree->area->newmetric) {
907 struct isis_item_list *te_neighs = NULL;
908 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
909 te_neighs = &lsp->tlvs->extended_reach;
910 else
911 te_neighs = isis_lookup_mt_items(
912 &lsp->tlvs->mt_reach, spftree->mtid);
913
914 struct isis_extended_reach *er;
915 for (er = te_neighs ? (struct isis_extended_reach *)
916 te_neighs->head
917 : NULL;
918 er; er = er->next) {
919 /* C.2.6 a) */
920 /* Two way connectivity */
921 if (!LSP_PSEUDO_ID(er->id)
922 && !memcmp(er->id, root_sysid,
923 ISIS_SYS_ID_LEN))
924 continue;
925 if (!pseudo_lsp
926 && !memcmp(er->id, null_sysid,
927 ISIS_SYS_ID_LEN))
928 continue;
929 #ifndef FABRICD
930
931 if (flex_algo_id_valid(spftree->algorithm) &&
932 (!sr_algorithm_participated(
933 lsp, spftree->algorithm) ||
934 isis_flex_algo_constraint_drop(spftree,
935 lsp, er)))
936 continue;
937 #endif /* ifndef FABRICD */
938
939 dist = cost
940 + (CHECK_FLAG(spftree->flags,
941 F_SPFTREE_HOPCOUNT_METRIC)
942 ? 1
943 : er->metric);
944 process_N(spftree,
945 LSP_PSEUDO_ID(er->id)
946 ? VTYPE_PSEUDO_TE_IS
947 : VTYPE_NONPSEUDO_TE_IS,
948 (void *)er->id, dist, depth + 1, NULL,
949 parent);
950 }
951 }
952 }
953
954 if (!fabricd && !pseudo_lsp && spftree->family == AF_INET
955 && spftree->mtid == ISIS_MT_IPV4_UNICAST
956 && spftree->area->oldmetric) {
957 struct isis_item_list *reachs[] = {
958 &lsp->tlvs->oldstyle_ip_reach,
959 &lsp->tlvs->oldstyle_ip_reach_ext};
960
961 for (unsigned int i = 0; i < array_size(reachs); i++) {
962 vtype = i ? VTYPE_IPREACH_EXTERNAL
963 : VTYPE_IPREACH_INTERNAL;
964
965 memset(&ip_info, 0, sizeof(ip_info));
966 ip_info.dest.family = AF_INET;
967
968 struct isis_oldstyle_ip_reach *r;
969 for (r = (struct isis_oldstyle_ip_reach *)reachs[i]
970 ->head;
971 r; r = r->next) {
972 dist = cost + r->metric;
973 ip_info.dest.u.prefix4 = r->prefix.prefix;
974 ip_info.dest.prefixlen = r->prefix.prefixlen;
975 process_N(spftree, vtype, &ip_info,
976 dist, depth + 1, NULL, parent);
977 }
978 }
979 }
980
981 /* we can skip all the rest if we're using metric style narrow */
982 if (!spftree->area->newmetric)
983 goto end;
984
985 if (!pseudo_lsp && spftree->family == AF_INET) {
986 struct isis_item_list *ipv4_reachs;
987 if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
988 ipv4_reachs = &lsp->tlvs->extended_ip_reach;
989 else
990 ipv4_reachs = isis_lookup_mt_items(
991 &lsp->tlvs->mt_ip_reach, spftree->mtid);
992
993 memset(&ip_info, 0, sizeof(ip_info));
994 ip_info.dest.family = AF_INET;
995
996 struct isis_extended_ip_reach *r;
997 for (r = ipv4_reachs
998 ? (struct isis_extended_ip_reach *)
999 ipv4_reachs->head
1000 : NULL;
1001 r; r = r->next) {
1002 dist = cost + r->metric;
1003 ip_info.dest.u.prefix4 = r->prefix.prefix;
1004 ip_info.dest.prefixlen = r->prefix.prefixlen;
1005
1006 /* Parse list of Prefix-SID subTLVs if SR is enabled */
1007 has_valid_psid = false;
1008 if (spftree->area->srdb.enabled && r->subtlvs) {
1009 for (struct isis_item *i =
1010 r->subtlvs->prefix_sids.head;
1011 i; i = i->next) {
1012 struct isis_prefix_sid *psid =
1013 (struct isis_prefix_sid *)i;
1014
1015 if (psid->algorithm !=
1016 spftree->algorithm)
1017 continue;
1018
1019 #ifndef FABRICD
1020 if (flex_algo_id_valid(
1021 spftree->algorithm) &&
1022 (!sr_algorithm_participated(
1023 lsp, spftree->algorithm) ||
1024 !isis_flex_algo_elected_supported(
1025 spftree->algorithm,
1026 spftree->area)))
1027 continue;
1028 #endif /* ifndef FABRICD */
1029
1030 has_valid_psid = true;
1031 process_N(spftree, VTYPE_IPREACH_TE,
1032 &ip_info, dist, depth + 1,
1033 psid, parent);
1034 /*
1035 * Stop the Prefix-SID iteration since
1036 * we only support the SPF algorithm for
1037 * now.
1038 */
1039 break;
1040 }
1041 }
1042 if (!has_valid_psid)
1043 process_N(spftree, VTYPE_IPREACH_TE, &ip_info,
1044 dist, depth + 1, NULL, parent);
1045 }
1046 }
1047
1048 if (!pseudo_lsp && spftree->family == AF_INET6) {
1049 struct isis_item_list *ipv6_reachs;
1050 if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
1051 ipv6_reachs = &lsp->tlvs->ipv6_reach;
1052 else
1053 ipv6_reachs = isis_lookup_mt_items(
1054 &lsp->tlvs->mt_ipv6_reach, spftree->mtid);
1055
1056 struct isis_ipv6_reach *r;
1057 for (r = ipv6_reachs
1058 ? (struct isis_ipv6_reach *)ipv6_reachs->head
1059 : NULL;
1060 r; r = r->next) {
1061 dist = cost + r->metric;
1062 vtype = r->external ? VTYPE_IP6REACH_EXTERNAL
1063 : VTYPE_IP6REACH_INTERNAL;
1064 memset(&ip_info, 0, sizeof(ip_info));
1065 ip_info.dest.family = AF_INET6;
1066 ip_info.dest.u.prefix6 = r->prefix.prefix;
1067 ip_info.dest.prefixlen = r->prefix.prefixlen;
1068
1069 if (spftree->area->srdb.enabled && r->subtlvs &&
1070 r->subtlvs->source_prefix &&
1071 r->subtlvs->source_prefix->prefixlen) {
1072 if (spftree->tree_id != SPFTREE_DSTSRC) {
1073 char buff[VID2STR_BUFFER];
1074 zlog_warn("Ignoring dest-src route %s in non dest-src topology",
1075 srcdest2str(
1076 &ip_info.dest,
1077 r->subtlvs->source_prefix,
1078 buff, sizeof(buff)
1079 )
1080 );
1081 continue;
1082 }
1083 ip_info.src = *r->subtlvs->source_prefix;
1084 }
1085
1086 /* Parse list of Prefix-SID subTLVs */
1087 has_valid_psid = false;
1088 if (r->subtlvs) {
1089 for (struct isis_item *i =
1090 r->subtlvs->prefix_sids.head;
1091 i; i = i->next) {
1092 struct isis_prefix_sid *psid =
1093 (struct isis_prefix_sid *)i;
1094
1095 if (psid->algorithm !=
1096 spftree->algorithm)
1097 continue;
1098
1099 #ifndef FABRICD
1100 if (flex_algo_id_valid(
1101 spftree->algorithm) &&
1102 (!sr_algorithm_participated(
1103 lsp, spftree->algorithm) ||
1104 !isis_flex_algo_elected_supported(
1105 spftree->algorithm,
1106 spftree->area)))
1107 continue;
1108 #endif /* ifndef FABRICD */
1109
1110 has_valid_psid = true;
1111 process_N(spftree, vtype, &ip_info,
1112 dist, depth + 1, psid,
1113 parent);
1114 /*
1115 * Stop the Prefix-SID iteration since
1116 * we only support the SPF algorithm for
1117 * now.
1118 */
1119 break;
1120 }
1121 }
1122 if (!has_valid_psid)
1123 process_N(spftree, vtype, &ip_info, dist,
1124 depth + 1, NULL, parent);
1125 }
1126 }
1127
1128 end:
1129
1130 /* if attach bit set in LSP, attached-bit receive ignore is
1131 * not configured, we are a level-1 area and we have no other
1132 * level-2 | level1-2 areas then add a default route toward
1133 * this neighbor
1134 */
1135 if ((lsp->hdr.lsp_bits & LSPBIT_ATT) == LSPBIT_ATT
1136 && !spftree->area->attached_bit_rcv_ignore
1137 && (spftree->area->is_type & IS_LEVEL_1)
1138 && !isis_level2_adj_up(spftree->area)) {
1139 struct prefix_pair ip_info = { {0} };
1140 if (IS_DEBUG_RTE_EVENTS)
1141 zlog_debug("ISIS-Spf (%pLS): add default %s route",
1142 lsp->hdr.lsp_id,
1143 spftree->family == AF_INET ? "ipv4"
1144 : "ipv6");
1145
1146 if (spftree->family == AF_INET) {
1147 ip_info.dest.family = AF_INET;
1148 vtype = VTYPE_IPREACH_INTERNAL;
1149 } else {
1150 ip_info.dest.family = AF_INET6;
1151 vtype = VTYPE_IP6REACH_INTERNAL;
1152 }
1153 process_N(spftree, vtype, &ip_info, cost, depth + 1, NULL,
1154 parent);
1155 }
1156
1157 if (fragnode == NULL)
1158 fragnode = listhead(lsp->lspu.frags);
1159 else
1160 fragnode = listnextnode(fragnode);
1161
1162 if (fragnode) {
1163 lsp = listgetdata(fragnode);
1164 goto lspfragloop;
1165 }
1166
1167 return ISIS_OK;
1168 }
1169
1170 static struct isis_adjacency *adj_find(struct list *adj_list, const uint8_t *id,
1171 int level, uint16_t mtid, int family)
1172 {
1173 struct isis_adjacency *adj;
1174 struct listnode *node;
1175
1176 for (ALL_LIST_ELEMENTS_RO(adj_list, node, adj)) {
1177 if (!(adj->level & level))
1178 continue;
1179 if (memcmp(adj->sysid, id, ISIS_SYS_ID_LEN) != 0)
1180 continue;
1181 if (adj->adj_state != ISIS_ADJ_UP)
1182 continue;
1183 if (!adj_has_mt(adj, mtid))
1184 continue;
1185 if (mtid == ISIS_MT_IPV4_UNICAST
1186 && !speaks(adj->nlpids.nlpids, adj->nlpids.count, family))
1187 continue;
1188 return adj;
1189 }
1190
1191 return NULL;
1192 }
1193
1194 struct spf_preload_tent_ip_reach_args {
1195 struct isis_spftree *spftree;
1196 struct isis_vertex *parent;
1197 };
1198
1199 static int isis_spf_preload_tent_ip_reach_cb(const struct prefix *prefix,
1200 uint32_t metric, bool external,
1201 struct isis_subtlvs *subtlvs,
1202 void *arg)
1203 {
1204 struct spf_preload_tent_ip_reach_args *args = arg;
1205 struct isis_spftree *spftree = args->spftree;
1206 struct isis_vertex *parent = args->parent;
1207 struct prefix_pair ip_info;
1208 enum vertextype vtype;
1209 bool has_valid_psid = false;
1210
1211 if (external)
1212 return LSP_ITER_CONTINUE;
1213
1214 assert(spftree->family == prefix->family);
1215 memset(&ip_info, 0, sizeof(ip_info));
1216 prefix_copy(&ip_info.dest, prefix);
1217 apply_mask(&ip_info.dest);
1218
1219 if (prefix->family == AF_INET)
1220 vtype = VTYPE_IPREACH_INTERNAL;
1221 else
1222 vtype = VTYPE_IP6REACH_INTERNAL;
1223
1224 /* Parse list of Prefix-SID subTLVs if SR is enabled */
1225 if (spftree->area->srdb.enabled && subtlvs) {
1226 for (struct isis_item *i = subtlvs->prefix_sids.head; i;
1227 i = i->next) {
1228 struct isis_prefix_sid *psid =
1229 (struct isis_prefix_sid *)i;
1230
1231 if (psid->algorithm != spftree->algorithm)
1232 continue;
1233
1234 has_valid_psid = true;
1235 isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0,
1236 psid, parent);
1237
1238 /*
1239 * Stop the Prefix-SID iteration since we only support
1240 * the SPF algorithm for now.
1241 */
1242 break;
1243 }
1244 }
1245 if (!has_valid_psid)
1246 isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0, NULL,
1247 parent);
1248
1249 return LSP_ITER_CONTINUE;
1250 }
1251
1252 static void isis_spf_preload_tent(struct isis_spftree *spftree,
1253 uint8_t *root_sysid,
1254 struct isis_lsp *root_lsp,
1255 struct isis_vertex *parent)
1256 {
1257 struct spf_preload_tent_ip_reach_args ip_reach_args;
1258 struct isis_spf_adj *sadj;
1259 struct listnode *node;
1260
1261 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) {
1262 ip_reach_args.spftree = spftree;
1263 ip_reach_args.parent = parent;
1264 isis_lsp_iterate_ip_reach(
1265 root_lsp, spftree->family, spftree->mtid,
1266 isis_spf_preload_tent_ip_reach_cb, &ip_reach_args);
1267 }
1268
1269 /* Iterate over adjacencies. */
1270 for (ALL_LIST_ELEMENTS_RO(spftree->sadj_list, node, sadj)) {
1271 const uint8_t *adj_id;
1272 uint32_t metric;
1273
1274 if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST))
1275 adj_id = sadj->lan.desig_is_id;
1276 else
1277 adj_id = sadj->id;
1278
1279 if (isis_lfa_excise_adj_check(spftree, adj_id)) {
1280 if (IS_DEBUG_LFA)
1281 zlog_debug("ISIS-SPF: excising adjacency %pPN",
1282 sadj->id);
1283 continue;
1284 }
1285
1286 metric = CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)
1287 ? 1
1288 : sadj->metric;
1289 if (!LSP_PSEUDO_ID(sadj->id)) {
1290 isis_spf_add_local(spftree,
1291 CHECK_FLAG(sadj->flags,
1292 F_ISIS_SPF_ADJ_OLDMETRIC)
1293 ? VTYPE_NONPSEUDO_IS
1294 : VTYPE_NONPSEUDO_TE_IS,
1295 sadj->id, sadj, metric, NULL,
1296 parent);
1297 } else if (sadj->lsp) {
1298 isis_spf_process_lsp(spftree, sadj->lsp, metric, 0,
1299 spftree->sysid, parent);
1300 }
1301 }
1302 }
1303
1304 struct spf_adj_find_reverse_metric_args {
1305 const uint8_t *id_self;
1306 uint32_t reverse_metric;
1307 };
1308
1309 static int spf_adj_find_reverse_metric_cb(const uint8_t *id, uint32_t metric,
1310 bool oldmetric,
1311 struct isis_ext_subtlvs *subtlvs,
1312 void *arg)
1313 {
1314 struct spf_adj_find_reverse_metric_args *args = arg;
1315
1316 if (memcmp(id, args->id_self, ISIS_SYS_ID_LEN))
1317 return LSP_ITER_CONTINUE;
1318
1319 args->reverse_metric = metric;
1320
1321 return LSP_ITER_STOP;
1322 }
1323
1324 /*
1325 * Change all SPF adjacencies to use the link cost in the direction from the
1326 * next hop back towards root in place of the link cost in the direction away
1327 * from root towards the next hop.
1328 */
1329 static void spf_adj_get_reverse_metrics(struct isis_spftree *spftree)
1330 {
1331 struct isis_spf_adj *sadj;
1332 struct listnode *node, *nnode;
1333
1334 for (ALL_LIST_ELEMENTS(spftree->sadj_list, node, nnode, sadj)) {
1335 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
1336 struct isis_lsp *lsp_adj;
1337 const uint8_t *id_self;
1338 struct spf_adj_find_reverse_metric_args args;
1339
1340 /* Skip pseudonodes. */
1341 if (LSP_PSEUDO_ID(sadj->id))
1342 continue;
1343
1344 /* Find LSP of the corresponding adjacency. */
1345 memcpy(lspid, sadj->id, ISIS_SYS_ID_LEN);
1346 LSP_PSEUDO_ID(lspid) = 0;
1347 LSP_FRAGMENT(lspid) = 0;
1348 lsp_adj = lsp_search(spftree->lspdb, lspid);
1349 if (lsp_adj == NULL || lsp_adj->hdr.rem_lifetime == 0) {
1350 /* Delete one-way adjacency. */
1351 listnode_delete(spftree->sadj_list, sadj);
1352 isis_spf_adj_free(sadj);
1353 continue;
1354 }
1355
1356 /* Find root node in the LSP of the adjacent router. */
1357 if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST))
1358 id_self = sadj->lan.desig_is_id;
1359 else
1360 id_self = spftree->sysid;
1361 args.id_self = id_self;
1362 args.reverse_metric = UINT32_MAX;
1363 isis_lsp_iterate_is_reach(lsp_adj, spftree->mtid,
1364 spf_adj_find_reverse_metric_cb,
1365 &args);
1366 if (args.reverse_metric == UINT32_MAX) {
1367 /* Delete one-way adjacency. */
1368 listnode_delete(spftree->sadj_list, sadj);
1369 isis_spf_adj_free(sadj);
1370 continue;
1371 }
1372 sadj->metric = args.reverse_metric;
1373 }
1374 }
1375
1376 static void spf_adj_list_parse_tlv(struct isis_spftree *spftree,
1377 struct list *adj_list, const uint8_t *id,
1378 const uint8_t *desig_is_id,
1379 uint32_t pseudo_metric, uint32_t metric,
1380 bool oldmetric,
1381 struct isis_ext_subtlvs *subtlvs)
1382 {
1383 struct isis_spf_adj *sadj;
1384 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
1385 struct isis_lsp *lsp;
1386 uint8_t flags = 0;
1387
1388 /* Skip self in the pseudonode. */
1389 if (desig_is_id && !memcmp(id, spftree->sysid, ISIS_SYS_ID_LEN))
1390 return;
1391
1392 /* Find LSP from the adjacency. */
1393 memcpy(lspid, id, ISIS_SYS_ID_LEN + 1);
1394 LSP_FRAGMENT(lspid) = 0;
1395 lsp = lsp_search(spftree->lspdb, lspid);
1396 if (lsp == NULL || lsp->hdr.rem_lifetime == 0) {
1397 zlog_warn("ISIS-SPF: No LSP found from root to L%d %pLS",
1398 spftree->level, lspid);
1399 return;
1400 }
1401
1402 sadj = XCALLOC(MTYPE_ISIS_SPF_ADJ, sizeof(*sadj));
1403 memcpy(sadj->id, id, sizeof(sadj->id));
1404 if (desig_is_id) {
1405 memcpy(sadj->lan.desig_is_id, desig_is_id,
1406 sizeof(sadj->lan.desig_is_id));
1407 SET_FLAG(flags, F_ISIS_SPF_ADJ_BROADCAST);
1408 sadj->metric = pseudo_metric;
1409 } else
1410 sadj->metric = metric;
1411 if (oldmetric)
1412 SET_FLAG(flags, F_ISIS_SPF_ADJ_OLDMETRIC);
1413 sadj->lsp = lsp;
1414 sadj->subtlvs = subtlvs;
1415 sadj->flags = flags;
1416
1417 if ((oldmetric && metric == ISIS_NARROW_METRIC_INFINITY)
1418 || (!oldmetric && metric == ISIS_WIDE_METRIC_INFINITY))
1419 SET_FLAG(flags, F_ISIS_SPF_ADJ_METRIC_INFINITY);
1420
1421 /* Set real adjacency. */
1422 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)
1423 && !LSP_PSEUDO_ID(id)) {
1424 struct isis_adjacency *adj;
1425
1426 adj = adj_find(adj_list, id, spftree->level, spftree->mtid,
1427 spftree->family);
1428 if (!adj) {
1429 XFREE(MTYPE_ISIS_SPF_ADJ, sadj);
1430 return;
1431 }
1432
1433 listnode_delete(adj_list, adj);
1434 sadj->adj = adj;
1435 }
1436
1437 /* Add adjacency to the list. */
1438 listnode_add(spftree->sadj_list, sadj);
1439
1440 if (!LSP_PSEUDO_ID(id)) {
1441 struct isis_spf_node *node;
1442
1443 node = isis_spf_node_find(&spftree->adj_nodes, id);
1444 if (!node)
1445 node = isis_spf_node_new(&spftree->adj_nodes, id);
1446 if (node->best_metric == 0 || sadj->metric < node->best_metric)
1447 node->best_metric = sadj->metric;
1448 listnode_add(node->adjacencies, sadj);
1449 }
1450
1451 /* Parse pseudonode LSP too. */
1452 if (LSP_PSEUDO_ID(id))
1453 spf_adj_list_parse_lsp(spftree, adj_list, lsp, id, metric);
1454 }
1455
1456 static void spf_adj_list_parse_lsp(struct isis_spftree *spftree,
1457 struct list *adj_list, struct isis_lsp *lsp,
1458 const uint8_t *pseudo_nodeid,
1459 uint32_t pseudo_metric)
1460 {
1461 bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id);
1462 struct isis_lsp *frag;
1463 struct listnode *node;
1464 struct isis_item *head;
1465 struct isis_item_list *te_neighs;
1466
1467 if (lsp->hdr.seqno == 0 || lsp->hdr.rem_lifetime == 0)
1468 return;
1469
1470 /* Parse LSP. */
1471 if (lsp->tlvs) {
1472 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) {
1473 head = lsp->tlvs->oldstyle_reach.head;
1474 for (struct isis_oldstyle_reach *reach =
1475 (struct isis_oldstyle_reach *)head;
1476 reach; reach = reach->next) {
1477 spf_adj_list_parse_tlv(
1478 spftree, adj_list, reach->id,
1479 pseudo_nodeid, pseudo_metric,
1480 reach->metric, true, NULL);
1481 }
1482 }
1483
1484 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
1485 te_neighs = &lsp->tlvs->extended_reach;
1486 else
1487 te_neighs = isis_get_mt_items(&lsp->tlvs->mt_reach,
1488 spftree->mtid);
1489 if (te_neighs) {
1490 head = te_neighs->head;
1491 for (struct isis_extended_reach *reach =
1492 (struct isis_extended_reach *)head;
1493 reach; reach = reach->next) {
1494 #ifndef FABRICD
1495 /*
1496 * cutting out adjacency by flex-algo link
1497 * affinity attribute
1498 */
1499 if (flex_algo_id_valid(spftree->algorithm) &&
1500 (!sr_algorithm_participated(
1501 lsp, spftree->algorithm) ||
1502 isis_flex_algo_constraint_drop(
1503 spftree, lsp, reach)))
1504 continue;
1505 #endif /* ifndef FABRICD */
1506
1507 spf_adj_list_parse_tlv(
1508 spftree, adj_list, reach->id,
1509 pseudo_nodeid, pseudo_metric,
1510 reach->metric, false, reach->subtlvs);
1511 }
1512 }
1513 }
1514
1515 if (LSP_FRAGMENT(lsp->hdr.lsp_id))
1516 return;
1517
1518 /* Parse LSP fragments. */
1519 for (ALL_LIST_ELEMENTS_RO(lsp->lspu.frags, node, frag)) {
1520 if (!frag->tlvs)
1521 continue;
1522
1523 spf_adj_list_parse_lsp(spftree, adj_list, frag, pseudo_nodeid,
1524 pseudo_metric);
1525 }
1526 }
1527
1528 static void isis_spf_build_adj_list(struct isis_spftree *spftree,
1529 struct isis_lsp *lsp)
1530 {
1531 struct list *adj_list = NULL;
1532
1533 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
1534 adj_list = list_dup(spftree->area->adjacency_list);
1535
1536 spf_adj_list_parse_lsp(spftree, adj_list, lsp, NULL, 0);
1537
1538 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
1539 list_delete(&adj_list);
1540
1541 if (spftree->type == SPF_TYPE_REVERSE)
1542 spf_adj_get_reverse_metrics(spftree);
1543 }
1544
1545 /*
1546 * The parent(s) for vertex is set when added to TENT list
1547 * now we just put the child pointer(s) in place
1548 */
1549 static void add_to_paths(struct isis_spftree *spftree,
1550 struct isis_vertex *vertex)
1551 {
1552 #ifdef EXTREME_DEBUG
1553 char buff[VID2STR_BUFFER];
1554 #endif /* EXTREME_DEBUG */
1555
1556 if (isis_find_vertex(&spftree->paths, &vertex->N, vertex->type))
1557 return;
1558 isis_vertex_queue_append(&spftree->paths, vertex);
1559
1560 #ifdef EXTREME_DEBUG
1561 if (IS_DEBUG_SPF_EVENTS)
1562 zlog_debug("ISIS-SPF: added %s %s %s depth %d dist %d to PATHS",
1563 print_sys_hostname(vertex->N.id),
1564 vtype2string(vertex->type),
1565 vid2string(vertex, buff, sizeof(buff)),
1566 vertex->depth, vertex->d_N);
1567 #endif /* EXTREME_DEBUG */
1568 }
1569
1570 static void init_spt(struct isis_spftree *spftree, int mtid)
1571 {
1572 /* Clear data from previous run. */
1573 hash_clean(spftree->prefix_sids, NULL);
1574 isis_spf_node_list_clear(&spftree->adj_nodes);
1575 list_delete_all_node(spftree->sadj_list);
1576 isis_vertex_queue_clear(&spftree->tents);
1577 isis_vertex_queue_clear(&spftree->paths);
1578 isis_zebra_rlfa_unregister_all(spftree);
1579 isis_rlfa_list_clear(spftree);
1580 list_delete_all_node(spftree->lfa.remote.pc_spftrees);
1581 memset(&spftree->lfa.protection_counters, 0,
1582 sizeof(spftree->lfa.protection_counters));
1583
1584 spftree->mtid = mtid;
1585 }
1586
1587 static enum spf_prefix_priority
1588 spf_prefix_priority(struct isis_spftree *spftree, struct isis_vertex *vertex)
1589 {
1590 struct isis_area *area = spftree->area;
1591 struct prefix *prefix = &vertex->N.ip.p.dest;
1592
1593 for (int priority = SPF_PREFIX_PRIO_CRITICAL;
1594 priority <= SPF_PREFIX_PRIO_MEDIUM; priority++) {
1595 struct spf_prefix_priority_acl *ppa;
1596 enum filter_type ret = FILTER_PERMIT;
1597
1598 ppa = &area->spf_prefix_priorities[priority];
1599 switch (spftree->family) {
1600 case AF_INET:
1601 ret = access_list_apply(ppa->list_v4, prefix);
1602 break;
1603 case AF_INET6:
1604 ret = access_list_apply(ppa->list_v6, prefix);
1605 break;
1606 default:
1607 break;
1608 }
1609
1610 if (ret == FILTER_PERMIT)
1611 return priority;
1612 }
1613
1614 /* Assign medium priority to loopback prefixes by default. */
1615 if (is_host_route(prefix))
1616 return SPF_PREFIX_PRIO_MEDIUM;
1617
1618 return SPF_PREFIX_PRIO_LOW;
1619 }
1620
1621 static void spf_path_process(struct isis_spftree *spftree,
1622 struct isis_vertex *vertex)
1623 {
1624 struct isis_area *area = spftree->area;
1625 int level = spftree->level;
1626 char buff[VID2STR_BUFFER];
1627
1628 if (spftree->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type)
1629 && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) {
1630 if (listcount(vertex->Adj_N) > 0) {
1631 struct isis_adjacency *adj;
1632
1633 if (isis_tilfa_check(spftree, vertex) != 0)
1634 return;
1635
1636 adj = isis_adj_find(area, level, vertex->N.id);
1637 if (adj)
1638 sr_adj_sid_add_single(adj, spftree->family,
1639 true, vertex->Adj_N);
1640 } else if (IS_DEBUG_SPF_EVENTS)
1641 zlog_debug(
1642 "ISIS-SPF: no adjacencies, do not install backup Adj-SID for %s depth %d dist %d",
1643 vid2string(vertex, buff, sizeof(buff)),
1644 vertex->depth, vertex->d_N);
1645 }
1646
1647 if (VTYPE_IP(vertex->type)
1648 && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ROUTES)) {
1649 enum spf_prefix_priority priority;
1650
1651 priority = spf_prefix_priority(spftree, vertex);
1652 vertex->N.ip.priority = priority;
1653 if (vertex->depth == 1 || listcount(vertex->Adj_N) > 0) {
1654 struct isis_spftree *pre_spftree;
1655 struct route_table *route_table = NULL;
1656 bool allow_ecmp = false;
1657
1658 switch (spftree->type) {
1659 case SPF_TYPE_RLFA:
1660 case SPF_TYPE_TI_LFA:
1661 if (priority
1662 > area->lfa_priority_limit[level - 1]) {
1663 if (IS_DEBUG_LFA)
1664 zlog_debug(
1665 "ISIS-LFA: skipping %s %s (low prefix priority)",
1666 vtype2string(
1667 vertex->type),
1668 vid2string(
1669 vertex, buff,
1670 sizeof(buff)));
1671 return;
1672 }
1673 break;
1674 case SPF_TYPE_FORWARD:
1675 case SPF_TYPE_REVERSE:
1676 break;
1677 }
1678
1679 switch (spftree->type) {
1680 case SPF_TYPE_RLFA:
1681 isis_rlfa_check(spftree, vertex);
1682 return;
1683 case SPF_TYPE_TI_LFA:
1684 if (isis_tilfa_check(spftree, vertex) != 0)
1685 return;
1686
1687 pre_spftree = spftree->lfa.old.spftree;
1688 route_table = pre_spftree->route_table_backup;
1689 allow_ecmp = area->lfa_load_sharing[level - 1];
1690 pre_spftree->lfa.protection_counters
1691 .tilfa[vertex->N.ip.priority] += 1;
1692 break;
1693 case SPF_TYPE_FORWARD:
1694 case SPF_TYPE_REVERSE:
1695 route_table = spftree->route_table;
1696 allow_ecmp = true;
1697
1698 /*
1699 * Update LFA protection counters (ignore local
1700 * routes).
1701 */
1702 if (vertex->depth > 1) {
1703 spftree->lfa.protection_counters
1704 .total[priority] += 1;
1705 if (listcount(vertex->Adj_N) > 1)
1706 spftree->lfa.protection_counters
1707 .ecmp[priority] += 1;
1708 }
1709 break;
1710 }
1711
1712 isis_route_create(
1713 &vertex->N.ip.p.dest, &vertex->N.ip.p.src,
1714 vertex->d_N, vertex->depth, &vertex->N.ip.sr,
1715 vertex->Adj_N, allow_ecmp, area, route_table);
1716 } else if (IS_DEBUG_SPF_EVENTS)
1717 zlog_debug(
1718 "ISIS-SPF: no adjacencies, do not install route for %s depth %d dist %d",
1719 vid2string(vertex, buff, sizeof(buff)),
1720 vertex->depth, vertex->d_N);
1721 }
1722 }
1723
1724 static void isis_spf_loop(struct isis_spftree *spftree,
1725 uint8_t *root_sysid)
1726 {
1727 struct isis_vertex *vertex;
1728 struct isis_lsp *lsp;
1729 struct listnode *node;
1730
1731 while (isis_vertex_queue_count(&spftree->tents)) {
1732 vertex = isis_vertex_queue_pop(&spftree->tents);
1733
1734 #ifdef EXTREME_DEBUG
1735 if (IS_DEBUG_SPF_EVENTS)
1736 zlog_debug(
1737 "ISIS-SPF: get TENT node %s %s depth %d dist %d to PATHS",
1738 print_sys_hostname(vertex->N.id),
1739 vtype2string(vertex->type), vertex->depth,
1740 vertex->d_N);
1741 #endif /* EXTREME_DEBUG */
1742
1743 add_to_paths(spftree, vertex);
1744 if (!VTYPE_IS(vertex->type))
1745 continue;
1746
1747 lsp = lsp_for_vertex(spftree, vertex);
1748 if (!lsp) {
1749 zlog_warn("ISIS-SPF: No LSP found for %pPN",
1750 vertex->N.id);
1751 continue;
1752 }
1753
1754 isis_spf_process_lsp(spftree, lsp, vertex->d_N, vertex->depth,
1755 root_sysid, vertex);
1756 }
1757
1758 /* Generate routes once the SPT is formed. */
1759 for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) {
1760 /* New-style TLVs take precedence over the old-style TLVs. */
1761 switch (vertex->type) {
1762 case VTYPE_IPREACH_INTERNAL:
1763 case VTYPE_IPREACH_EXTERNAL:
1764 if (isis_find_vertex(&spftree->paths, &vertex->N,
1765 VTYPE_IPREACH_TE))
1766 continue;
1767 break;
1768 case VTYPE_PSEUDO_IS:
1769 case VTYPE_PSEUDO_TE_IS:
1770 case VTYPE_NONPSEUDO_IS:
1771 case VTYPE_NONPSEUDO_TE_IS:
1772 case VTYPE_ES:
1773 case VTYPE_IPREACH_TE:
1774 case VTYPE_IP6REACH_INTERNAL:
1775 case VTYPE_IP6REACH_EXTERNAL:
1776 break;
1777 }
1778
1779 spf_path_process(spftree, vertex);
1780 }
1781 }
1782
1783 struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area,
1784 uint8_t *sysid,
1785 struct isis_spftree *spftree)
1786 {
1787 if (!spftree)
1788 spftree = isis_spftree_new(
1789 area, &area->lspdb[IS_LEVEL_2 - 1], sysid, ISIS_LEVEL2,
1790 SPFTREE_IPV4, SPF_TYPE_FORWARD,
1791 F_SPFTREE_HOPCOUNT_METRIC, SR_ALGORITHM_SPF);
1792
1793 init_spt(spftree, ISIS_MT_IPV4_UNICAST);
1794 if (!memcmp(sysid, area->isis->sysid, ISIS_SYS_ID_LEN)) {
1795 struct isis_lsp *root_lsp;
1796 struct isis_vertex *root_vertex;
1797
1798 root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid);
1799 if (root_lsp) {
1800 /*
1801 * If we are running locally, initialize with
1802 * information from adjacencies
1803 */
1804 root_vertex = isis_spf_add_root(spftree);
1805
1806 isis_spf_preload_tent(spftree, sysid, root_lsp,
1807 root_vertex);
1808 }
1809 } else {
1810 isis_vertex_queue_insert(
1811 &spftree->tents,
1812 isis_vertex_new(spftree, sysid, VTYPE_NONPSEUDO_TE_IS));
1813 }
1814
1815 isis_spf_loop(spftree, sysid);
1816
1817 return spftree;
1818 }
1819
1820 void isis_run_spf(struct isis_spftree *spftree)
1821 {
1822 struct isis_lsp *root_lsp;
1823 struct isis_vertex *root_vertex;
1824 struct timeval time_start;
1825 struct timeval time_end;
1826 struct isis_mt_router_info *mt_router_info;
1827 uint16_t mtid = 0;
1828
1829 /* Get time that can't roll backwards. */
1830 monotime(&time_start);
1831
1832 root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid);
1833 if (root_lsp == NULL) {
1834 zlog_err("ISIS-SPF: could not find own l%d LSP!",
1835 spftree->level);
1836 return;
1837 }
1838
1839 /* Get Multi-Topology ID. */
1840 switch (spftree->tree_id) {
1841 case SPFTREE_IPV4:
1842 mtid = ISIS_MT_IPV4_UNICAST;
1843 break;
1844 case SPFTREE_IPV6:
1845 mt_router_info = isis_tlvs_lookup_mt_router_info(
1846 root_lsp->tlvs, ISIS_MT_IPV6_UNICAST);
1847 if (mt_router_info)
1848 mtid = ISIS_MT_IPV6_UNICAST;
1849 else
1850 mtid = ISIS_MT_IPV4_UNICAST;
1851 break;
1852 case SPFTREE_DSTSRC:
1853 mtid = ISIS_MT_IPV6_DSTSRC;
1854 break;
1855 case SPFTREE_COUNT:
1856 zlog_err(
1857 "%s should never be called with SPFTREE_COUNT as argument!",
1858 __func__);
1859 exit(1);
1860 }
1861
1862 #ifndef FABRICD
1863 /* If a node is configured to participate in a particular Flexible-
1864 * Algorithm, but there is no valid Flex-Algorithm definition available
1865 * for it, or the selected Flex-Algorithm definition includes
1866 * calculation-type, metric-type, constraint, flag, or Sub-TLV that is
1867 * not supported by the node, it MUST stop participating in such
1868 * Flexible-Algorithm.
1869 */
1870 if (flex_algo_id_valid(spftree->algorithm) &&
1871 !isis_flex_algo_elected_supported(spftree->algorithm,
1872 spftree->area)) {
1873 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
1874 isis_spftree_clear(spftree);
1875 SET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
1876 lsp_regenerate_schedule(spftree->area,
1877 spftree->area->is_type, 0);
1878 }
1879 goto out;
1880 }
1881 #endif /* ifndef FABRICD */
1882
1883 /*
1884 * C.2.5 Step 0
1885 */
1886 init_spt(spftree, mtid);
1887 /* a) */
1888 root_vertex = isis_spf_add_root(spftree);
1889 /* b) */
1890 isis_spf_build_adj_list(spftree, root_lsp);
1891 isis_spf_preload_tent(spftree, spftree->sysid, root_lsp, root_vertex);
1892
1893 /*
1894 * C.2.7 Step 2
1895 */
1896 if (!isis_vertex_queue_count(&spftree->tents)
1897 && (IS_DEBUG_SPF_EVENTS)) {
1898 zlog_warn("ISIS-SPF: TENT is empty SPF-root:%s",
1899 print_sys_hostname(spftree->sysid));
1900 }
1901
1902 isis_spf_loop(spftree, spftree->sysid);
1903
1904
1905 #ifndef FABRICD
1906 /* flex-algo */
1907 if (CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
1908 UNSET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
1909 lsp_regenerate_schedule(spftree->area, spftree->area->is_type,
1910 0);
1911 }
1912
1913 out:
1914 #endif /* ifndef FABRICD */
1915 spftree->runcount++;
1916 spftree->last_run_timestamp = time(NULL);
1917 spftree->last_run_monotime = monotime(&time_end);
1918 spftree->last_run_duration =
1919 ((time_end.tv_sec - time_start.tv_sec) * 1000000)
1920 + (time_end.tv_usec - time_start.tv_usec);
1921 }
1922
1923 static void isis_run_spf_with_protection(struct isis_area *area,
1924 struct isis_spftree *spftree)
1925 {
1926 /* Run forward SPF locally. */
1927 memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN);
1928 isis_run_spf(spftree);
1929
1930 /* Run LFA protection if configured. */
1931 if (area->lfa_protected_links[spftree->level - 1] > 0
1932 || area->tilfa_protected_links[spftree->level - 1] > 0)
1933 isis_spf_run_lfa(area, spftree);
1934 }
1935
1936 void isis_spf_verify_routes(struct isis_area *area, struct isis_spftree **trees)
1937 {
1938 if (area->is_type == IS_LEVEL_1) {
1939 isis_route_verify_table(area, trees[0]->route_table,
1940 trees[0]->route_table_backup);
1941 } else if (area->is_type == IS_LEVEL_2) {
1942 isis_route_verify_table(area, trees[1]->route_table,
1943 trees[1]->route_table_backup);
1944 } else {
1945 isis_route_verify_merge(area, trees[0]->route_table,
1946 trees[0]->route_table_backup,
1947 trees[1]->route_table,
1948 trees[1]->route_table_backup);
1949 }
1950 }
1951
1952 void isis_spf_invalidate_routes(struct isis_spftree *tree)
1953 {
1954 struct isis_route_table_info *backup_info;
1955
1956 isis_route_invalidate_table(tree->area, tree->route_table);
1957
1958 /* Delete backup routes. */
1959
1960 backup_info = tree->route_table_backup->info;
1961 route_table_finish(tree->route_table_backup);
1962 isis_route_table_info_free(backup_info);
1963 tree->route_table_backup = srcdest_table_init();
1964 tree->route_table_backup->info =
1965 isis_route_table_info_alloc(tree->algorithm);
1966 tree->route_table_backup->cleanup = isis_route_node_cleanup;
1967 }
1968
1969 void isis_spf_switchover_routes(struct isis_area *area,
1970 struct isis_spftree **trees, int family,
1971 union g_addr *nexthop_ip, ifindex_t ifindex,
1972 int level)
1973 {
1974 isis_route_switchover_nexthop(area, trees[level - 1]->route_table,
1975 family, nexthop_ip, ifindex);
1976 }
1977
1978 static void isis_run_spf_cb(struct event *thread)
1979 {
1980 struct isis_spf_run *run = EVENT_ARG(thread);
1981 struct isis_area *area = run->area;
1982 int level = run->level;
1983 int have_run = 0;
1984 struct listnode *node;
1985 struct isis_circuit *circuit;
1986 #ifndef FABRICD
1987 struct flex_algo *fa;
1988 struct isis_flex_algo_data *data;
1989 #endif /* ifndef FABRICD */
1990
1991 XFREE(MTYPE_ISIS_SPF_RUN, run);
1992
1993 if (!(area->is_type & level)) {
1994 if (IS_DEBUG_SPF_EVENTS)
1995 zlog_warn("ISIS-SPF (%s) area does not share level",
1996 area->area_tag);
1997 return;
1998 }
1999
2000 isis_area_delete_backup_adj_sids(area, level);
2001 isis_area_invalidate_routes(area, level);
2002
2003 if (IS_DEBUG_SPF_EVENTS)
2004 zlog_debug("ISIS-SPF (%s) L%d SPF needed, periodic SPF",
2005 area->area_tag, level);
2006
2007 if (area->ip_circuits) {
2008 isis_run_spf_with_protection(
2009 area, area->spftree[SPFTREE_IPV4][level - 1]);
2010 #ifndef FABRICD
2011 for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
2012 fa)) {
2013 data = fa->data;
2014 isis_run_spf_with_protection(
2015 area, data->spftree[SPFTREE_IPV4][level - 1]);
2016 }
2017 #endif /* ifndef FABRICD */
2018 have_run = 1;
2019 }
2020 if (area->ipv6_circuits) {
2021 isis_run_spf_with_protection(
2022 area, area->spftree[SPFTREE_IPV6][level - 1]);
2023 #ifndef FABRICD
2024 for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
2025 fa)) {
2026 data = fa->data;
2027 isis_run_spf_with_protection(
2028 area, data->spftree[SPFTREE_IPV6][level - 1]);
2029 }
2030 #endif /* ifndef FABRICD */
2031 have_run = 1;
2032 }
2033 if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) {
2034 isis_run_spf_with_protection(
2035 area, area->spftree[SPFTREE_DSTSRC][level - 1]);
2036 have_run = 1;
2037 }
2038
2039 if (have_run)
2040 area->spf_run_count[level]++;
2041
2042 isis_area_verify_routes(area);
2043
2044 /* walk all circuits and reset any spf specific flags */
2045 for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit))
2046 UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
2047
2048 fabricd_run_spf(area);
2049 }
2050
2051 static struct isis_spf_run *isis_run_spf_arg(struct isis_area *area, int level)
2052 {
2053 struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run));
2054
2055 run->area = area;
2056 run->level = level;
2057
2058 return run;
2059 }
2060
2061 void isis_spf_timer_free(void *run)
2062 {
2063 XFREE(MTYPE_ISIS_SPF_RUN, run);
2064 }
2065
2066 int _isis_spf_schedule(struct isis_area *area, int level,
2067 const char *func, const char *file, int line)
2068 {
2069 struct isis_spftree *spftree;
2070 time_t now;
2071 long tree_diff, diff;
2072 int tree;
2073
2074 now = monotime(NULL);
2075 diff = 0;
2076 for (tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
2077 spftree = area->spftree[tree][level - 1];
2078 tree_diff = difftime(now - spftree->last_run_monotime, 0);
2079 if (tree_diff != now && (diff == 0 || tree_diff < diff))
2080 diff = tree_diff;
2081 }
2082
2083 if (CHECK_FLAG(im->options, F_ISIS_UNIT_TEST))
2084 return 0;
2085
2086 assert(diff >= 0);
2087 assert(area->is_type & level);
2088
2089 if (IS_DEBUG_SPF_EVENTS) {
2090 zlog_debug(
2091 "ISIS-SPF (%s) L%d SPF schedule called, lastrun %ld sec ago Caller: %s %s:%d",
2092 area->area_tag, level, diff, func, file, line);
2093 }
2094
2095 EVENT_OFF(area->t_rlfa_rib_update);
2096 if (area->spf_delay_ietf[level - 1]) {
2097 /* Need to call schedule function also if spf delay is running
2098 * to
2099 * restart holdoff timer - compare
2100 * draft-ietf-rtgwg-backoff-algo-04 */
2101 long delay =
2102 spf_backoff_schedule(area->spf_delay_ietf[level - 1]);
2103 if (area->spf_timer[level - 1])
2104 return ISIS_OK;
2105
2106 event_add_timer_msec(master, isis_run_spf_cb,
2107 isis_run_spf_arg(area, level), delay,
2108 &area->spf_timer[level - 1]);
2109 return ISIS_OK;
2110 }
2111
2112 if (area->spf_timer[level - 1])
2113 return ISIS_OK;
2114
2115 /* wait configured min_spf_interval before doing the SPF */
2116 long timer;
2117 if (diff >= area->min_spf_interval[level - 1]
2118 || area->bfd_force_spf_refresh) {
2119 /*
2120 * Last run is more than min interval ago or BFD signalled a
2121 * 'down' message, schedule immediate run
2122 */
2123 timer = 0;
2124
2125 if (area->bfd_force_spf_refresh) {
2126 zlog_debug(
2127 "ISIS-SPF (%s) L%d SPF scheduled immediately due to BFD 'down' message",
2128 area->area_tag, level);
2129 area->bfd_force_spf_refresh = false;
2130 }
2131 } else {
2132 timer = area->min_spf_interval[level - 1] - diff;
2133 }
2134
2135 event_add_timer(master, isis_run_spf_cb, isis_run_spf_arg(area, level),
2136 timer, &area->spf_timer[level - 1]);
2137
2138 if (IS_DEBUG_SPF_EVENTS)
2139 zlog_debug("ISIS-SPF (%s) L%d SPF scheduled %ld sec from now",
2140 area->area_tag, level, timer);
2141
2142 return ISIS_OK;
2143 }
2144
2145 static void isis_print_paths(struct vty *vty, struct isis_vertex_queue *queue,
2146 uint8_t *root_sysid)
2147 {
2148 struct listnode *node;
2149 struct isis_vertex *vertex;
2150 char buff[VID2STR_BUFFER];
2151
2152 vty_out(vty,
2153 "Vertex Type Metric Next-Hop Interface Parent\n");
2154
2155 for (ALL_QUEUE_ELEMENTS_RO(queue, node, vertex)) {
2156 if (VTYPE_IS(vertex->type)
2157 && memcmp(vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) {
2158 vty_out(vty, "%-20s %-12s %-6s",
2159 print_sys_hostname(root_sysid), "", "");
2160 vty_out(vty, "%-30s\n", "");
2161 continue;
2162 }
2163
2164 int rows = 0;
2165 struct listnode *anode = listhead(vertex->Adj_N);
2166 struct listnode *pnode = listhead(vertex->parents);
2167 struct isis_vertex_adj *vadj;
2168 struct isis_vertex *pvertex;
2169
2170 vty_out(vty, "%-20s %-12s %-6u ",
2171 vid2string(vertex, buff, sizeof(buff)),
2172 vtype2string(vertex->type), vertex->d_N);
2173 for (unsigned int i = 0;
2174 i < MAX(vertex->Adj_N ? listcount(vertex->Adj_N) : 0,
2175 vertex->parents ? listcount(vertex->parents) : 0);
2176 i++) {
2177 if (anode) {
2178 vadj = listgetdata(anode);
2179 anode = anode->next;
2180 } else {
2181 vadj = NULL;
2182 }
2183
2184 if (pnode) {
2185 pvertex = listgetdata(pnode);
2186 pnode = pnode->next;
2187 } else {
2188 pvertex = NULL;
2189 }
2190
2191 if (rows) {
2192 vty_out(vty, "\n");
2193 vty_out(vty, "%-20s %-12s %-6s ", "", "", "");
2194 }
2195
2196 if (vadj) {
2197 struct isis_spf_adj *sadj = vadj->sadj;
2198
2199 vty_out(vty, "%-20s %-9s ",
2200 print_sys_hostname(sadj->id),
2201 sadj->adj ? sadj->adj->circuit
2202 ->interface->name
2203 : "-");
2204 }
2205
2206 if (pvertex) {
2207 if (!vadj)
2208 vty_out(vty, "%-20s %-9s ", "", "");
2209
2210 vty_out(vty, "%s(%d)",
2211 vid2string(pvertex, buff, sizeof(buff)),
2212 pvertex->type);
2213 }
2214
2215 ++rows;
2216 }
2217 vty_out(vty, "\n");
2218 }
2219 }
2220
2221 void isis_print_spftree(struct vty *vty, struct isis_spftree *spftree)
2222 {
2223 const char *tree_id_text = NULL;
2224
2225 if (!spftree || !isis_vertex_queue_count(&spftree->paths))
2226 return;
2227
2228 switch (spftree->tree_id) {
2229 case SPFTREE_IPV4:
2230 tree_id_text = "that speak IP";
2231 break;
2232 case SPFTREE_IPV6:
2233 tree_id_text = "that speak IPv6";
2234 break;
2235 case SPFTREE_DSTSRC:
2236 tree_id_text = "that support IPv6 dst-src routing";
2237 break;
2238 case SPFTREE_COUNT:
2239 assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type");
2240 return;
2241 }
2242
2243 vty_out(vty, "IS-IS paths to level-%d routers %s\n", spftree->level,
2244 tree_id_text);
2245 isis_print_paths(vty, &spftree->paths, spftree->sysid);
2246 vty_out(vty, "\n");
2247 }
2248
2249 static void show_isis_topology_common(struct vty *vty, int levels,
2250 struct isis *isis)
2251 {
2252 struct listnode *node;
2253 struct isis_area *area;
2254
2255 if (!isis->area_list || isis->area_list->count == 0)
2256 return;
2257
2258 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
2259 vty_out(vty, "Area %s:\n",
2260 area->area_tag ? area->area_tag : "null");
2261
2262 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
2263 if ((level & levels) == 0)
2264 continue;
2265
2266 if (area->ip_circuits > 0) {
2267 isis_print_spftree(
2268 vty,
2269 area->spftree[SPFTREE_IPV4][level - 1]);
2270 }
2271 if (area->ipv6_circuits > 0) {
2272 isis_print_spftree(
2273 vty,
2274 area->spftree[SPFTREE_IPV6][level - 1]);
2275 }
2276 if (isis_area_ipv6_dstsrc_enabled(area)) {
2277 isis_print_spftree(vty,
2278 area->spftree[SPFTREE_DSTSRC]
2279 [level - 1]);
2280 }
2281 }
2282
2283 if (fabricd_spftree(area)) {
2284 vty_out(vty,
2285 "IS-IS paths to level-2 routers with hop-by-hop metric\n");
2286 isis_print_paths(vty, &fabricd_spftree(area)->paths, isis->sysid);
2287 vty_out(vty, "\n");
2288 }
2289
2290 vty_out(vty, "\n");
2291 }
2292 }
2293
2294 DEFUN(show_isis_topology, show_isis_topology_cmd,
2295 "show " PROTO_NAME
2296 " [vrf <NAME|all>] topology"
2297 #ifndef FABRICD
2298 " [<level-1|level-2>]"
2299 #endif
2300 ,
2301 SHOW_STR PROTO_HELP VRF_CMD_HELP_STR
2302 "All VRFs\n"
2303 "IS-IS paths to Intermediate Systems\n"
2304 #ifndef FABRICD
2305 "Paths to all level-1 routers in the area\n"
2306 "Paths to all level-2 routers in the domain\n"
2307 #endif
2308 )
2309 {
2310 int levels = ISIS_LEVELS;
2311 struct listnode *node;
2312 struct isis *isis = NULL;
2313 int idx = 0;
2314 const char *vrf_name = VRF_DEFAULT_NAME;
2315 bool all_vrf = false;
2316 int idx_vrf = 0;
2317
2318 if (argv_find(argv, argc, "topology", &idx)) {
2319 if (argc < idx + 2)
2320 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
2321 else if (strmatch(argv[idx + 1]->arg, "level-1"))
2322 levels = ISIS_LEVEL1;
2323 else
2324 levels = ISIS_LEVEL2;
2325 }
2326
2327 if (!im) {
2328 vty_out(vty, "IS-IS Routing Process not enabled\n");
2329 return CMD_SUCCESS;
2330 }
2331 ISIS_FIND_VRF_ARGS(argv, argc, idx_vrf, vrf_name, all_vrf);
2332
2333 if (vrf_name) {
2334 if (all_vrf) {
2335 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
2336 show_isis_topology_common(vty, levels, isis);
2337 return CMD_SUCCESS;
2338 }
2339 isis = isis_lookup_by_vrfname(vrf_name);
2340 if (isis != NULL)
2341 show_isis_topology_common(vty, levels, isis);
2342 }
2343
2344 return CMD_SUCCESS;
2345 }
2346
2347 static void isis_print_route(struct ttable *tt, const struct prefix *prefix,
2348 struct isis_route_info *rinfo, bool prefix_sid,
2349 bool no_adjacencies)
2350 {
2351 struct isis_nexthop *nexthop;
2352 struct listnode *node;
2353 bool first = true;
2354 char buf_prefix[BUFSIZ];
2355
2356 (void)prefix2str(prefix, buf_prefix, sizeof(buf_prefix));
2357 for (ALL_LIST_ELEMENTS_RO(rinfo->nexthops, node, nexthop)) {
2358 struct interface *ifp;
2359 char buf_iface[BUFSIZ];
2360 char buf_nhop[BUFSIZ];
2361
2362 if (!no_adjacencies) {
2363 inet_ntop(nexthop->family, &nexthop->ip, buf_nhop,
2364 sizeof(buf_nhop));
2365 ifp = if_lookup_by_index(nexthop->ifindex, VRF_DEFAULT);
2366 if (ifp)
2367 strlcpy(buf_iface, ifp->name,
2368 sizeof(buf_iface));
2369 else
2370 snprintf(buf_iface, sizeof(buf_iface),
2371 "ifindex %u", nexthop->ifindex);
2372 } else {
2373 strlcpy(buf_nhop, print_sys_hostname(nexthop->sysid),
2374 sizeof(buf_nhop));
2375 strlcpy(buf_iface, "-", sizeof(buf_iface));
2376 }
2377
2378 if (prefix_sid) {
2379 char buf_sid[BUFSIZ] = {};
2380 char buf_lblop[BUFSIZ] = {};
2381
2382 if (nexthop->sr.present) {
2383 snprintf(buf_sid, sizeof(buf_sid), "%u",
2384 nexthop->sr.sid.value);
2385 sr_op2str(
2386 buf_lblop, sizeof(buf_lblop),
2387 rinfo->sr_algo[SR_ALGORITHM_SPF].label,
2388 nexthop->sr.label);
2389 } else {
2390 strlcpy(buf_sid, "-", sizeof(buf_sid));
2391 strlcpy(buf_lblop, "-", sizeof(buf_lblop));
2392 }
2393
2394 if (first) {
2395 ttable_add_row(tt, "%s|%u|%s|%s|%s|%s",
2396 buf_prefix, rinfo->cost,
2397 buf_iface, buf_nhop, buf_sid,
2398 buf_lblop);
2399 first = false;
2400 } else
2401 ttable_add_row(tt, "||%s|%s|%s|%s", buf_iface,
2402 buf_nhop, buf_sid, buf_lblop);
2403 } else {
2404 char buf_labels[BUFSIZ] = {};
2405
2406 if (nexthop->label_stack) {
2407 for (int i = 0;
2408 i < nexthop->label_stack->num_labels;
2409 i++) {
2410 char buf_label[BUFSIZ];
2411
2412 label2str(
2413 nexthop->label_stack->label[i],
2414 0, buf_label,
2415 sizeof(buf_label));
2416 if (i != 0)
2417 strlcat(buf_labels, "/",
2418 sizeof(buf_labels));
2419 strlcat(buf_labels, buf_label,
2420 sizeof(buf_labels));
2421 }
2422 } else if (nexthop->sr.present)
2423 label2str(nexthop->sr.label, 0, buf_labels,
2424 sizeof(buf_labels));
2425 else
2426 strlcpy(buf_labels, "-", sizeof(buf_labels));
2427
2428 if (first) {
2429 ttable_add_row(tt, "%s|%u|%s|%s|%s", buf_prefix,
2430 rinfo->cost, buf_iface, buf_nhop,
2431 buf_labels);
2432 first = false;
2433 } else
2434 ttable_add_row(tt, "||%s|%s|%s", buf_iface,
2435 buf_nhop, buf_labels);
2436 }
2437 }
2438 if (list_isempty(rinfo->nexthops)) {
2439 if (prefix_sid) {
2440 char buf_sid[BUFSIZ] = {};
2441 char buf_lblop[BUFSIZ] = {};
2442
2443 if (rinfo->sr_algo[SR_ALGORITHM_SPF].present) {
2444 snprintf(buf_sid, sizeof(buf_sid), "%u",
2445 rinfo->sr_algo[SR_ALGORITHM_SPF]
2446 .sid.value);
2447 sr_op2str(
2448 buf_lblop, sizeof(buf_lblop),
2449 rinfo->sr_algo[SR_ALGORITHM_SPF].label,
2450 MPLS_LABEL_IMPLICIT_NULL);
2451 } else {
2452 strlcpy(buf_sid, "-", sizeof(buf_sid));
2453 strlcpy(buf_lblop, "-", sizeof(buf_lblop));
2454 }
2455
2456 ttable_add_row(tt, "%s|%u|%s|%s|%s|%s", buf_prefix,
2457 rinfo->cost, "-", "-", buf_sid,
2458 buf_lblop);
2459 } else
2460 ttable_add_row(tt, "%s|%u|%s|%s|%s", buf_prefix,
2461 rinfo->cost, "-", "-", "-");
2462 }
2463 }
2464
2465 void isis_print_routes(struct vty *vty, struct isis_spftree *spftree,
2466 bool prefix_sid, bool backup)
2467 {
2468 struct route_table *route_table;
2469 struct ttable *tt;
2470 struct route_node *rn;
2471 bool no_adjacencies = false;
2472 const char *tree_id_text = NULL;
2473
2474 if (!spftree)
2475 return;
2476
2477 switch (spftree->tree_id) {
2478 case SPFTREE_IPV4:
2479 tree_id_text = "IPv4";
2480 break;
2481 case SPFTREE_IPV6:
2482 tree_id_text = "IPv6";
2483 break;
2484 case SPFTREE_DSTSRC:
2485 tree_id_text = "IPv6 (dst-src routing)";
2486 break;
2487 case SPFTREE_COUNT:
2488 assert(!"isis_print_routes shouldn't be called with SPFTREE_COUNT as type");
2489 return;
2490 }
2491
2492 vty_out(vty, "IS-IS %s %s routing table:\n\n",
2493 circuit_t2string(spftree->level), tree_id_text);
2494
2495 /* Prepare table. */
2496 tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
2497 if (prefix_sid)
2498 ttable_add_row(tt, "Prefix|Metric|Interface|Nexthop|SID|Label Op.");
2499 else
2500 ttable_add_row(tt, "Prefix|Metric|Interface|Nexthop|Label(s)");
2501 tt->style.cell.rpad = 2;
2502 tt->style.corner = '+';
2503 ttable_restyle(tt);
2504 ttable_rowseps(tt, 0, BOTTOM, true, '-');
2505
2506 if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
2507 no_adjacencies = true;
2508
2509 route_table =
2510 (backup) ? spftree->route_table_backup : spftree->route_table;
2511 for (rn = route_top(route_table); rn; rn = route_next(rn)) {
2512 struct isis_route_info *rinfo;
2513
2514 rinfo = rn->info;
2515 if (!rinfo)
2516 continue;
2517
2518 isis_print_route(tt, &rn->p, rinfo, prefix_sid, no_adjacencies);
2519 }
2520
2521 /* Dump the generated table. */
2522 if (tt->nrows > 1) {
2523 char *table;
2524
2525 table = ttable_dump(tt, "\n");
2526 vty_out(vty, "%s\n", table);
2527 XFREE(MTYPE_TMP, table);
2528 }
2529 ttable_del(tt);
2530 }
2531
2532 static void show_isis_route_common(struct vty *vty, int levels,
2533 struct isis *isis, bool prefix_sid,
2534 bool backup)
2535 {
2536 struct listnode *node;
2537 struct isis_area *area;
2538
2539 if (!isis->area_list || isis->area_list->count == 0)
2540 return;
2541
2542 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
2543 vty_out(vty, "Area %s:\n",
2544 area->area_tag ? area->area_tag : "null");
2545
2546 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
2547 if ((level & levels) == 0)
2548 continue;
2549
2550 if (area->ip_circuits > 0) {
2551 isis_print_routes(
2552 vty,
2553 area->spftree[SPFTREE_IPV4][level - 1],
2554 prefix_sid, backup);
2555 }
2556 if (area->ipv6_circuits > 0) {
2557 isis_print_routes(
2558 vty,
2559 area->spftree[SPFTREE_IPV6][level - 1],
2560 prefix_sid, backup);
2561 }
2562 if (isis_area_ipv6_dstsrc_enabled(area)) {
2563 isis_print_routes(vty,
2564 area->spftree[SPFTREE_DSTSRC]
2565 [level - 1],
2566 prefix_sid, backup);
2567 }
2568 }
2569 }
2570 }
2571
2572 DEFUN(show_isis_route, show_isis_route_cmd,
2573 "show " PROTO_NAME
2574 " [vrf <NAME|all>] route"
2575 #ifndef FABRICD
2576 " [<level-1|level-2>]"
2577 #endif
2578 " [<prefix-sid|backup>]",
2579 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
2580 "IS-IS routing table\n"
2581 #ifndef FABRICD
2582 "level-1 routes\n"
2583 "level-2 routes\n"
2584 #endif
2585 "Show Prefix-SID information\n"
2586 "Show backup routes\n")
2587 {
2588 int levels;
2589 struct isis *isis;
2590 struct listnode *node;
2591 const char *vrf_name = VRF_DEFAULT_NAME;
2592 bool all_vrf = false;
2593 bool prefix_sid = false;
2594 bool backup = false;
2595 int idx = 0;
2596
2597 if (argv_find(argv, argc, "level-1", &idx))
2598 levels = ISIS_LEVEL1;
2599 else if (argv_find(argv, argc, "level-2", &idx))
2600 levels = ISIS_LEVEL2;
2601 else
2602 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
2603
2604 if (!im) {
2605 vty_out(vty, "IS-IS Routing Process not enabled\n");
2606 return CMD_SUCCESS;
2607 }
2608 ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf);
2609
2610 if (argv_find(argv, argc, "prefix-sid", &idx))
2611 prefix_sid = true;
2612 if (argv_find(argv, argc, "backup", &idx))
2613 backup = true;
2614
2615 if (vrf_name) {
2616 if (all_vrf) {
2617 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
2618 show_isis_route_common(vty, levels, isis,
2619 prefix_sid, backup);
2620 return CMD_SUCCESS;
2621 }
2622 isis = isis_lookup_by_vrfname(vrf_name);
2623 if (isis != NULL)
2624 show_isis_route_common(vty, levels, isis, prefix_sid,
2625 backup);
2626 }
2627
2628 return CMD_SUCCESS;
2629 }
2630
2631 static void isis_print_frr_summary_line(struct ttable *tt,
2632 const char *protection,
2633 uint32_t counters[SPF_PREFIX_PRIO_MAX])
2634 {
2635 uint32_t critical, high, medium, low, total;
2636
2637 critical = counters[SPF_PREFIX_PRIO_CRITICAL];
2638 high = counters[SPF_PREFIX_PRIO_HIGH];
2639 medium = counters[SPF_PREFIX_PRIO_MEDIUM];
2640 low = counters[SPF_PREFIX_PRIO_LOW];
2641 total = critical + high + medium + low;
2642
2643 ttable_add_row(tt, "%s|%u|%u|%u|%u|%u", protection, critical, high,
2644 medium, low, total);
2645 }
2646
2647 static void
2648 isis_print_frr_summary_line_coverage(struct ttable *tt, const char *protection,
2649 double counters[SPF_PREFIX_PRIO_MAX],
2650 double total)
2651 {
2652 double critical, high, medium, low;
2653
2654 critical = counters[SPF_PREFIX_PRIO_CRITICAL] * 100;
2655 high = counters[SPF_PREFIX_PRIO_HIGH] * 100;
2656 medium = counters[SPF_PREFIX_PRIO_MEDIUM] * 100;
2657 low = counters[SPF_PREFIX_PRIO_LOW] * 100;
2658 total *= 100;
2659
2660 ttable_add_row(tt, "%s|%.2f%%|%.2f%%|%.2f%%|%.2f%%|%.2f%%", protection,
2661 critical, high, medium, low, total);
2662 }
2663
2664 static void isis_print_frr_summary(struct vty *vty,
2665 struct isis_spftree *spftree)
2666 {
2667 struct ttable *tt;
2668 char *table;
2669 const char *tree_id_text = NULL;
2670 uint32_t protectd[SPF_PREFIX_PRIO_MAX] = {0};
2671 uint32_t unprotected[SPF_PREFIX_PRIO_MAX] = {0};
2672 double coverage[SPF_PREFIX_PRIO_MAX] = {0};
2673 uint32_t protected_total = 0, grand_total = 0;
2674 double coverage_total;
2675
2676 if (!spftree)
2677 return;
2678
2679 switch (spftree->tree_id) {
2680 case SPFTREE_IPV4:
2681 tree_id_text = "IPv4";
2682 break;
2683 case SPFTREE_IPV6:
2684 tree_id_text = "IPv6";
2685 break;
2686 case SPFTREE_DSTSRC:
2687 tree_id_text = "IPv6 (dst-src routing)";
2688 break;
2689 case SPFTREE_COUNT:
2690 assert(!"isis_print_frr_summary shouldn't be called with SPFTREE_COUNT as type");
2691 return;
2692 }
2693
2694 vty_out(vty, " IS-IS %s %s Fast ReRoute summary:\n\n",
2695 circuit_t2string(spftree->level), tree_id_text);
2696
2697 /* Prepare table. */
2698 tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
2699 ttable_add_row(
2700 tt,
2701 "Protection \\ Priority|Critical|High |Medium |Low |Total");
2702 tt->style.cell.rpad = 2;
2703 tt->style.corner = '+';
2704 ttable_restyle(tt);
2705 ttable_rowseps(tt, 0, BOTTOM, true, '-');
2706
2707 /* Compute unprotected and coverage totals. */
2708 for (int priority = SPF_PREFIX_PRIO_CRITICAL;
2709 priority < SPF_PREFIX_PRIO_MAX; priority++) {
2710 uint32_t *lfa = spftree->lfa.protection_counters.lfa;
2711 uint32_t *rlfa = spftree->lfa.protection_counters.rlfa;
2712 uint32_t *tilfa = spftree->lfa.protection_counters.tilfa;
2713 uint32_t *ecmp = spftree->lfa.protection_counters.ecmp;
2714 uint32_t *total = spftree->lfa.protection_counters.total;
2715
2716 protectd[priority] = lfa[priority] + rlfa[priority]
2717 + tilfa[priority] + ecmp[priority];
2718 /* Safeguard to protect against possible inconsistencies. */
2719 if (protectd[priority] > total[priority])
2720 protectd[priority] = total[priority];
2721 unprotected[priority] = total[priority] - protectd[priority];
2722 protected_total += protectd[priority];
2723 grand_total += total[priority];
2724
2725 if (!total[priority])
2726 coverage[priority] = 0;
2727 else
2728 coverage[priority] =
2729 protectd[priority] / (double)total[priority];
2730 }
2731
2732 if (!grand_total)
2733 coverage_total = 0;
2734 else
2735 coverage_total = protected_total / (double)grand_total;
2736
2737 /* Add rows. */
2738 isis_print_frr_summary_line(tt, "Classic LFA",
2739 spftree->lfa.protection_counters.lfa);
2740 isis_print_frr_summary_line(tt, "Remote LFA",
2741 spftree->lfa.protection_counters.rlfa);
2742 isis_print_frr_summary_line(tt, "Topology Independent LFA",
2743 spftree->lfa.protection_counters.tilfa);
2744 isis_print_frr_summary_line(tt, "ECMP",
2745 spftree->lfa.protection_counters.ecmp);
2746 isis_print_frr_summary_line(tt, "Unprotected", unprotected);
2747 isis_print_frr_summary_line_coverage(tt, "Protection coverage",
2748 coverage, coverage_total);
2749
2750 /* Dump the generated table. */
2751 table = ttable_dump(tt, "\n");
2752 vty_out(vty, "%s\n", table);
2753 XFREE(MTYPE_TMP, table);
2754 ttable_del(tt);
2755 }
2756
2757 static void show_isis_frr_summary_common(struct vty *vty, int levels,
2758 struct isis *isis)
2759 {
2760 struct listnode *node;
2761 struct isis_area *area;
2762
2763 if (!isis->area_list || isis->area_list->count == 0)
2764 return;
2765
2766 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
2767 vty_out(vty, "Area %s:\n",
2768 area->area_tag ? area->area_tag : "null");
2769
2770 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
2771 if ((level & levels) == 0)
2772 continue;
2773
2774 if (area->ip_circuits > 0) {
2775 isis_print_frr_summary(
2776 vty,
2777 area->spftree[SPFTREE_IPV4][level - 1]);
2778 }
2779 if (area->ipv6_circuits > 0) {
2780 isis_print_frr_summary(
2781 vty,
2782 area->spftree[SPFTREE_IPV6][level - 1]);
2783 }
2784 if (isis_area_ipv6_dstsrc_enabled(area)) {
2785 isis_print_frr_summary(
2786 vty, area->spftree[SPFTREE_DSTSRC]
2787 [level - 1]);
2788 }
2789 }
2790 }
2791 }
2792
2793 DEFUN(show_isis_frr_summary, show_isis_frr_summary_cmd,
2794 "show " PROTO_NAME
2795 " [vrf <NAME|all>] fast-reroute summary"
2796 #ifndef FABRICD
2797 " [<level-1|level-2>]"
2798 #endif
2799 ,
2800 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
2801 "IS-IS FRR information\n"
2802 "FRR summary\n"
2803 #ifndef FABRICD
2804 "level-1 routes\n"
2805 "level-2 routes\n"
2806 #endif
2807 )
2808 {
2809 int levels;
2810 struct isis *isis;
2811 struct listnode *node;
2812 const char *vrf_name = VRF_DEFAULT_NAME;
2813 bool all_vrf = false;
2814 int idx = 0;
2815
2816 if (argv_find(argv, argc, "level-1", &idx))
2817 levels = ISIS_LEVEL1;
2818 else if (argv_find(argv, argc, "level-2", &idx))
2819 levels = ISIS_LEVEL2;
2820 else
2821 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
2822
2823 if (!im) {
2824 vty_out(vty, "IS-IS Routing Process not enabled\n");
2825 return CMD_SUCCESS;
2826 }
2827 ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf);
2828
2829 if (vrf_name) {
2830 if (all_vrf) {
2831 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
2832 show_isis_frr_summary_common(vty, levels, isis);
2833 return CMD_SUCCESS;
2834 }
2835 isis = isis_lookup_by_vrfname(vrf_name);
2836 if (isis != NULL)
2837 show_isis_frr_summary_common(vty, levels, isis);
2838 }
2839
2840 return CMD_SUCCESS;
2841 }
2842
2843 void isis_spf_init(void)
2844 {
2845 install_element(VIEW_NODE, &show_isis_topology_cmd);
2846 install_element(VIEW_NODE, &show_isis_route_cmd);
2847 install_element(VIEW_NODE, &show_isis_frr_summary_cmd);
2848
2849 /* Register hook(s). */
2850 hook_register(isis_adj_state_change_hook, spf_adj_state_change);
2851 }
2852
2853 void isis_spf_print(struct isis_spftree *spftree, struct vty *vty)
2854 {
2855 uint64_t last_run_duration = spftree->last_run_duration;
2856
2857 vty_out(vty, " last run elapsed : ");
2858 vty_out_timestr(vty, spftree->last_run_timestamp);
2859 vty_out(vty, "\n");
2860
2861 vty_out(vty, " last run duration : %" PRIu64 " usec\n",
2862 last_run_duration);
2863
2864 vty_out(vty, " run count : %u\n", spftree->runcount);
2865 }
2866 void isis_spf_print_json(struct isis_spftree *spftree, struct json_object *json)
2867 {
2868 char uptime[MONOTIME_STRLEN];
2869 time_t cur;
2870 cur = time(NULL);
2871 cur -= spftree->last_run_timestamp;
2872 frrtime_to_interval(cur, uptime, sizeof(uptime));
2873 json_object_string_add(json, "last-run-elapsed", uptime);
2874 json_object_int_add(json, "last-run-duration-usec",
2875 spftree->last_run_duration);
2876 json_object_int_add(json, "last-run-count", spftree->runcount);
2877 }
FRRouting mirror