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