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