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