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