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