]> git.proxmox.com Git - mirror_frr.git/blame - isisd/isis_spf.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
isisd: fix wrongly disabled flex-algo
[mirror_frr.git] / isisd / isis_spf.c
CommitLineData
acddc0ed 1// SPDX-License-Identifier: GPL-2.0-or-later
eb5d44eb 2/*
3 * IS-IS Rout(e)ing protocol - isis_spf.c
4 * The SPT algorithm
5 *
6 * Copyright (C) 2001,2002 Sampo Saaristo
d62a17ae 7 * Tampere University of Technology
eb5d44eb 8 * Institute of Communications Engineering
1b49e4f0 9 * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org>
eb5d44eb 10 */
11
eb5d44eb 12#include <zebra.h>
eb5d44eb 13
24a58196 14#include "frrevent.h"
eb5d44eb 15#include "linklist.h"
16#include "vty.h"
17#include "log.h"
18#include "command.h"
675269d4 19#include "termtable.h"
eb5d44eb 20#include "memory.h"
21#include "prefix.h"
e886416f 22#include "filter.h"
eb5d44eb 23#include "if.h"
2f7cc7bc 24#include "hash.h"
eb5d44eb 25#include "table.h"
03f7e182 26#include "spf_backoff.h"
321c1bbb 27#include "srcdest_table.h"
eab88f36 28#include "vrf.h"
42ac4485 29#include "lib/json.h"
eb5d44eb 30
2f7cc7bc 31#include "isis_errors.h"
eb5d44eb 32#include "isis_constants.h"
33#include "isis_common.h"
3f045a08 34#include "isis_flags.h"
eb5d44eb 35#include "isisd.h"
36#include "isis_misc.h"
37#include "isis_adjacency.h"
38#include "isis_circuit.h"
eb5d44eb 39#include "isis_pdu.h"
40#include "isis_lsp.h"
41#include "isis_dynhn.h"
42#include "isis_spf.h"
43#include "isis_route.h"
44#include "isis_csm.h"
2b67862c 45#include "isis_mt.h"
841791b6 46#include "isis_tlvs.h"
860b75b4 47#include "isis_flex_algo.h"
16fe8cff 48#include "isis_zebra.h"
b30e837b 49#include "fabricd.h"
cbd8e49e 50#include "isis_spf_private.h"
eb5d44eb 51
66b9a381
DL		 52DEFINE_MTYPE_STATIC(ISISD, ISIS_SPFTREE, "ISIS SPFtree");
53DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info");
54DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_ADJ, "ISIS SPF Adjacency");
55DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX, "ISIS vertex");
7b36d36e
RW		 56DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX_ADJ, "ISIS SPF Vertex Adjacency");
57
58static void spf_adj_list_parse_lsp(struct isis_spftree *spftree,
59 struct list *adj_list, struct isis_lsp *lsp,
60 const uint8_t *pseudo_nodeid,
61 uint32_t pseudo_metric);
1b49e4f0 62
af8ac8f9
CF		 63/*
64 * supports the given af ?
65 */
66static bool speaks(uint8_t *protocols, uint8_t count, int family)
67{
68 for (uint8_t i = 0; i < count; i++) {
69 if (family == AF_INET && protocols[i] == NLPID_IP)
70 return true;
71 if (family == AF_INET6 && protocols[i] == NLPID_IPV6)
72 return true;
73 }
74 return false;
75}
76
1b49e4f0 77struct isis_spf_run {
d62a17ae 78 struct isis_area *area;
79 int level;
1b49e4f0
CF		 80};
81
eb5d44eb 82/* 7.2.7 */
d62a17ae 83static void remove_excess_adjs(struct list *adjs)
eb5d44eb 84{
d62a17ae 85 struct listnode *node, *excess = NULL;
7b36d36e 86 struct isis_vertex_adj *vadj, *candidate = NULL;
d62a17ae 87 int comp;
88
7b36d36e
RW		 89 for (ALL_LIST_ELEMENTS_RO(adjs, node, vadj)) {
90 struct isis_adjacency *adj, *candidate_adj;
91
92 adj = vadj->sadj->adj;
93 assert(adj);
94
d62a17ae 95 if (excess == NULL)
96 excess = node;
97 candidate = listgetdata(excess);
7b36d36e 98 candidate_adj = candidate->sadj->adj;
d62a17ae 99
7b36d36e 100 if (candidate_adj->sys_type < adj->sys_type) {
d62a17ae 101 excess = node;
102 continue;
103 }
7b36d36e 104 if (candidate_adj->sys_type > adj->sys_type)
d62a17ae 105 continue;
f390d2c7 106
7b36d36e
RW		 107 comp = memcmp(candidate_adj->sysid, adj->sysid,
108 ISIS_SYS_ID_LEN);
d62a17ae 109 if (comp > 0) {
110 excess = node;
111 continue;
112 }
113 if (comp < 0)
114 continue;
eb5d44eb 115
7b36d36e 116 if (candidate_adj->circuit->idx > adj->circuit->idx) {
d62a17ae 117 excess = node;
118 continue;
119 }
f390d2c7 120
7b36d36e 121 if (candidate_adj->circuit->idx < adj->circuit->idx)
d62a17ae 122 continue;
f390d2c7 123
7b36d36e 124 comp = memcmp(candidate_adj->snpa, adj->snpa, ETH_ALEN);
d62a17ae 125 if (comp > 0) {
126 excess = node;
127 continue;
128 }
f390d2c7 129 }
f390d2c7 130
d62a17ae 131 list_delete_node(adjs, excess);
eb5d44eb 132
d62a17ae 133 return;
eb5d44eb 134}
135
c951ee6e 136const char *vtype2string(enum vertextype vtype)
eb5d44eb 137{
d62a17ae 138 switch (vtype) {
139 case VTYPE_PSEUDO_IS:
140 return "pseudo_IS";
d62a17ae 141 case VTYPE_PSEUDO_TE_IS:
142 return "pseudo_TE-IS";
d62a17ae 143 case VTYPE_NONPSEUDO_IS:
144 return "IS";
d62a17ae 145 case VTYPE_NONPSEUDO_TE_IS:
146 return "TE-IS";
d62a17ae 147 case VTYPE_ES:
148 return "ES";
d62a17ae 149 case VTYPE_IPREACH_INTERNAL:
150 return "IP internal";
d62a17ae 151 case VTYPE_IPREACH_EXTERNAL:
152 return "IP external";
d62a17ae 153 case VTYPE_IPREACH_TE:
154 return "IP TE";
d62a17ae 155 case VTYPE_IP6REACH_INTERNAL:
156 return "IP6 internal";
d62a17ae 157 case VTYPE_IP6REACH_EXTERNAL:
158 return "IP6 external";
d62a17ae 159 default:
160 return "UNKNOWN";
161 }
162 return NULL; /* Not reached */
eb5d44eb 163}
164
c951ee6e 165const char *vid2string(const struct isis_vertex *vertex, char *buff, int size)
eb5d44eb 166{
d62a17ae 167 if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) {
69052f3d
RW		 168 const char *hostname = print_sys_hostname(vertex->N.id);
169 strlcpy(buff, hostname, size);
170 return buff;
d62a17ae 171 }
172
173 if (VTYPE_IP(vertex->type)) {
d47d6089
RW		 174 srcdest2str(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, buff,
175 size);
d62a17ae 176 return buff;
177 }
178
179 return "UNKNOWN";
eb5d44eb 180}
181
2f7cc7bc
RW		 182static bool prefix_sid_cmp(const void *value1, const void *value2)
183{
184 const struct isis_vertex *c1 = value1;
185 const struct isis_vertex *c2 = value2;
186
187 if (CHECK_FLAG(c1->N.ip.sr.sid.flags,
188 ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL)
189 != CHECK_FLAG(c2->N.ip.sr.sid.flags,
190 ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL))
191 return false;
192
193 return c1->N.ip.sr.sid.value == c2->N.ip.sr.sid.value;
194}
195
196static unsigned int prefix_sid_key_make(const void *value)
197{
198 const struct isis_vertex *vertex = value;
199
200 return jhash_1word(vertex->N.ip.sr.sid.value, 0);
201}
202
203struct isis_vertex *isis_spf_prefix_sid_lookup(struct isis_spftree *spftree,
204 struct isis_prefix_sid *psid)
205{
206 struct isis_vertex lookup = {};
207
208 lookup.N.ip.sr.sid = *psid;
209 return hash_lookup(spftree->prefix_sids, &lookup);
210}
211
e886416f 212void isis_vertex_adj_free(void *arg)
7b36d36e
RW		 213{
214 struct isis_vertex_adj *vadj = arg;
215
216 XFREE(MTYPE_ISIS_VERTEX_ADJ, vadj);
217}
218
686afe9f 219static struct isis_vertex *isis_vertex_new(struct isis_spftree *spftree,
f6ae63ca 220 void *id,
ae9c9aba 221 enum vertextype vtype)
eb919f07
CF		 222{
223 struct isis_vertex *vertex;
224
225 vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex));
226
f6ae63ca 227 isis_vertex_id_init(vertex, id, vtype);
d62a17ae 228
229 vertex->Adj_N = list_new();
7b36d36e 230 vertex->Adj_N->del = isis_vertex_adj_free;
d62a17ae 231 vertex->parents = list_new();
d62a17ae 232
7b36d36e 233 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) {
686afe9f
CF		 234 vertex->firsthops = hash_create(isis_vertex_queue_hash_key,
235 isis_vertex_queue_hash_cmp,
236 NULL);
237 }
238
d62a17ae 239 return vertex;
eb5d44eb 240}
241
66b9a381
DL		 242void isis_vertex_del(struct isis_vertex *vertex)
243{
244 list_delete(&vertex->Adj_N);
245 list_delete(&vertex->parents);
d8bc11a5 246 hash_clean_and_free(&vertex->firsthops, NULL);
66b9a381
DL		 247
248 memset(vertex, 0, sizeof(struct isis_vertex));
249 XFREE(MTYPE_ISIS_VERTEX, vertex);
250}
251
e886416f
RW		 252struct isis_vertex_adj *
253isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex,
254 struct list *vadj_list, struct isis_spf_adj *sadj,
255 struct isis_prefix_sid *psid, bool last_hop)
7b36d36e
RW		 256{
257 struct isis_vertex_adj *vadj;
258
259 vadj = XCALLOC(MTYPE_ISIS_VERTEX_ADJ, sizeof(*vadj));
260 vadj->sadj = sadj;
7700a88a 261 if (spftree->area->srdb.enabled && psid) {
d47d6089
RW		 262 if (vertex->N.ip.sr.present
263 && vertex->N.ip.sr.sid.value != psid->value)
264 zlog_warn(
265 "ISIS-SPF: ignoring different Prefix-SID for route %pFX",
266 &vertex->N.ip.p.dest);
267 else {
d47d6089
RW		 268 vadj->sr.sid = *psid;
269 vadj->sr.label = sr_prefix_out_label(
270 spftree->lspdb, vertex->N.ip.p.dest.family,
271 psid, sadj->id, last_hop);
272 if (vadj->sr.label != MPLS_INVALID_LABEL)
273 vadj->sr.present = true;
274 }
275 }
e886416f 276 listnode_add(vadj_list, vadj);
7b36d36e
RW		 277
278 return vadj;
279}
280
d62a17ae 281static void isis_vertex_adj_del(struct isis_vertex *vertex,
282 struct isis_adjacency *adj)
3f045a08 283{
7b36d36e 284 struct isis_vertex_adj *vadj;
d62a17ae 285 struct listnode *node, *nextnode;
7b36d36e 286
d62a17ae 287 if (!vertex)
288 return;
7b36d36e
RW		 289
290 for (ALL_LIST_ELEMENTS(vertex->Adj_N, node, nextnode, vadj)) {
291 if (vadj->sadj->adj == adj) {
292 listnode_delete(vertex->Adj_N, vadj);
293 isis_vertex_adj_free(vadj);
294 }
d62a17ae 295 }
296 return;
3f045a08
JB		 297}
298
7b36d36e
RW		 299bool isis_vertex_adj_exists(const struct isis_spftree *spftree,
300 const struct isis_vertex *vertex,
301 const struct isis_spf_adj *sadj)
302{
303 struct isis_vertex_adj *tmp;
304 struct listnode *node;
305
306 for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, tmp)) {
307 if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) {
308 if (memcmp(sadj->id, tmp->sadj->id, sizeof(sadj->id))
309 == 0)
310 return true;
311 } else {
312 if (sadj->adj == tmp->sadj->adj)
313 return true;
314 }
315 }
316
317 return false;
318}
319
320static void isis_spf_adj_free(void *arg)
321{
322 struct isis_spf_adj *sadj = arg;
323
324 XFREE(MTYPE_ISIS_SPF_ADJ, sadj);
325}
326
860b75b4 327static void _isis_spftree_init(struct isis_spftree *tree)
3f045a08 328{
bded4060
CF		 329 isis_vertex_queue_init(&tree->tents, "IS-IS SPF tents", true);
330 isis_vertex_queue_init(&tree->paths, "IS-IS SPF paths", false);
321c1bbb 331 tree->route_table = srcdest_table_init();
c951ee6e 332 tree->route_table->cleanup = isis_route_node_cleanup;
860b75b4 333 tree->route_table->info = isis_route_table_info_alloc(tree->algorithm);
c951ee6e 334 tree->route_table_backup = srcdest_table_init();
860b75b4
HS		 335 tree->route_table_backup->info =
336 isis_route_table_info_alloc(tree->algorithm);
c951ee6e 337 tree->route_table_backup->cleanup = isis_route_node_cleanup;
2f7cc7bc
RW		 338 tree->prefix_sids = hash_create(prefix_sid_key_make, prefix_sid_cmp,
339 "SR Prefix-SID Entries");
7b36d36e
RW		 340 tree->sadj_list = list_new();
341 tree->sadj_list->del = isis_spf_adj_free;
860b75b4
HS		 342 isis_rlfa_list_init(tree);
343 tree->lfa.remote.pc_spftrees = list_new();
344 tree->lfa.remote.pc_spftrees->del = (void (*)(void *))isis_spftree_del;
345 if (tree->type == SPF_TYPE_RLFA || tree->type == SPF_TYPE_TI_LFA) {
346 isis_spf_node_list_init(&tree->lfa.p_space);
347 isis_spf_node_list_init(&tree->lfa.q_space);
348 }
349}
350
351struct isis_spftree *
352isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb,
353 const uint8_t *sysid, int level, enum spf_tree_id tree_id,
354 enum spf_type type, uint8_t flags, uint8_t algorithm)
355{
356 struct isis_spftree *tree;
357
358 tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree));
359
360 tree->area = area;
361 tree->lspdb = lspdb;
d62a17ae 362 tree->last_run_timestamp = 0;
3dca3c8c 363 tree->last_run_monotime = 0;
d62a17ae 364 tree->last_run_duration = 0;
365 tree->runcount = 0;
75aa7aa1 366 tree->type = type;
7b36d36e
RW		 367 memcpy(tree->sysid, sysid, ISIS_SYS_ID_LEN);
368 tree->level = level;
369 tree->tree_id = tree_id;
370 tree->family = (tree->tree_id == SPFTREE_IPV4) ? AF_INET : AF_INET6;
371 tree->flags = flags;
329f87b3 372 tree->algorithm = algorithm;
7b36d36e 373
860b75b4
HS		 374 _isis_spftree_init(tree);
375
d62a17ae 376 return tree;
3f045a08
JB		 377}
378
860b75b4 379static void _isis_spftree_del(struct isis_spftree *spftree)
eb5d44eb 380{
d8bc11a5 381 hash_clean_and_free(&spftree->prefix_sids, NULL);
16fe8cff
RW		 382 isis_zebra_rlfa_unregister_all(spftree);
383 isis_rlfa_list_clear(spftree);
384 list_delete(&spftree->lfa.remote.pc_spftrees);
385 if (spftree->type == SPF_TYPE_RLFA
386 || spftree->type == SPF_TYPE_TI_LFA) {
c951ee6e
RW		 387 isis_spf_node_list_clear(&spftree->lfa.q_space);
388 isis_spf_node_list_clear(&spftree->lfa.p_space);
389 }
390 isis_spf_node_list_clear(&spftree->adj_nodes);
7b36d36e 391 list_delete(&spftree->sadj_list);
eb919f07
CF		 392 isis_vertex_queue_free(&spftree->tents);
393 isis_vertex_queue_free(&spftree->paths);
7153c3ca
HS		 394 isis_route_table_info_free(spftree->route_table->info);
395 isis_route_table_info_free(spftree->route_table_backup->info);
771d544a
LS		 396 route_table_finish(spftree->route_table);
397 route_table_finish(spftree->route_table_backup);
860b75b4
HS		 398}
399
400void isis_spftree_del(struct isis_spftree *spftree)
401{
402 _isis_spftree_del(spftree);
403
3dace42d 404 spftree->route_table = NULL;
eb5d44eb 405
3dace42d 406 XFREE(MTYPE_ISIS_SPFTREE, spftree);
d62a17ae 407 return;
eb5d44eb 408}
3f045a08 409
860b75b4
HS		 410#ifndef FABRICD
411static void isis_spftree_clear(struct isis_spftree *spftree)
412{
413 _isis_spftree_del(spftree);
414 _isis_spftree_init(spftree);
415}
416#endif /* ifndef FABRICD */
417
d62a17ae 418static void isis_spftree_adj_del(struct isis_spftree *spftree,
419 struct isis_adjacency *adj)
3f045a08 420{
d62a17ae 421 struct listnode *node;
eb919f07 422 struct isis_vertex *v;
d62a17ae 423 if (!adj)
424 return;
bded4060 425 assert(!isis_vertex_queue_count(&spftree->tents));
eb919f07
CF		 426 for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, v))
427 isis_vertex_adj_del(v, adj);
d62a17ae 428 return;
3f045a08 429}
eb5d44eb 430
d62a17ae 431void spftree_area_init(struct isis_area *area)
eb5d44eb 432{
be985ba0
CF		 433 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
434 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
435 if (!(area->is_type & level))
436 continue;
437 if (area->spftree[tree][level - 1])
438 continue;
d62a17ae 439
329f87b3
HS		 440 area->spftree[tree][level - 1] = isis_spftree_new(
441 area, &area->lspdb[level - 1],
442 area->isis->sysid, level, tree,
443 SPF_TYPE_FORWARD, 0, SR_ALGORITHM_SPF);
be985ba0 444 }
d62a17ae 445 }
eb5d44eb 446}
447
d62a17ae 448void spftree_area_del(struct isis_area *area)
eb5d44eb 449{
be985ba0
CF		 450 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
451 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
452 if (!(area->is_type & level))
453 continue;
454 if (!area->spftree[tree][level - 1])
455 continue;
d62a17ae 456
be985ba0 457 isis_spftree_del(area->spftree[tree][level - 1]);
d62a17ae 458 }
459 }
3f045a08 460}
f390d2c7 461
56ea2b21 462static int spf_adj_state_change(struct isis_adjacency *adj)
3f045a08 463{
56ea2b21
RW		 464 struct isis_area *area = adj->circuit->area;
465
466 if (adj->adj_state == ISIS_ADJ_UP)
467 return 0;
468
469 /* Remove adjacency from all SPF trees. */
be985ba0
CF		 470 for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
471 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
472 if (!(area->is_type & level))
473 continue;
474 if (!area->spftree[tree][level - 1])
475 continue;
476 isis_spftree_adj_del(area->spftree[tree][level - 1],
477 adj);
478 }
d62a17ae 479 }
b30e837b
CF		 480
481 if (fabricd_spftree(area) != NULL)
482 isis_spftree_adj_del(fabricd_spftree(area), adj);
56ea2b21
RW		 483
484 return 0;
3f045a08
JB		 485}
486
d62a17ae 487/*
488 * Find the system LSP: returns the LSP in our LSP database
3f045a08
JB		 489 * associated with the given system ID.
490 */
c951ee6e
RW		 491struct isis_lsp *isis_root_system_lsp(struct lspdb_head *lspdb,
492 const uint8_t *sysid)
3f045a08 493{
d62a17ae 494 struct isis_lsp *lsp;
d7c0a89a 495 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
d62a17ae 496
497 memcpy(lspid, sysid, ISIS_SYS_ID_LEN);
498 LSP_PSEUDO_ID(lspid) = 0;
499 LSP_FRAGMENT(lspid) = 0;
7b36d36e 500 lsp = lsp_search(lspdb, lspid);
af8ac8f9 501 if (lsp && lsp->hdr.rem_lifetime != 0)
d62a17ae 502 return lsp;
503 return NULL;
eb5d44eb 504}
505
506/*
507 * Add this IS to the root of SPT
508 */
7b36d36e 509static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree)
eb5d44eb 510{
d62a17ae 511 struct isis_vertex *vertex;
eb5d44eb 512#ifdef EXTREME_DEBUG
321c1bbb 513 char buff[VID2STR_BUFFER];
eb5d44eb 514#endif /* EXTREME_DEBUG */
f390d2c7 515
7b36d36e 516 vertex = isis_vertex_new(spftree, spftree->sysid,
9d303b37
DL		 517 spftree->area->oldmetric
518 ? VTYPE_NONPSEUDO_IS
519 : VTYPE_NONPSEUDO_TE_IS);
bded4060 520 isis_vertex_queue_append(&spftree->paths, vertex);
eb5d44eb 521
522#ifdef EXTREME_DEBUG
b0814935
PG		 523 if (IS_DEBUG_SPF_EVENTS)
524 zlog_debug(
042ea8f2
LS		 525 "ISIS-SPF: A:%hhu added this IS %s %s depth %d dist %d to PATHS",
526 spftree->algorithm, vtype2string(vertex->type),
b0814935
PG		 527 vid2string(vertex, buff, sizeof(buff)), vertex->depth,
528 vertex->d_N);
eb5d44eb 529#endif /* EXTREME_DEBUG */
530
d62a17ae 531 return vertex;
eb5d44eb 532}
533
e3b78da8 534static void vertex_add_parent_firsthop(struct hash_bucket *bucket, void *arg)
686afe9f
CF		 535{
536 struct isis_vertex *vertex = arg;
e3b78da8 537 struct isis_vertex *hop = bucket->data;
686afe9f 538
8e3aae66 539 (void)hash_get(vertex->firsthops, hop, hash_alloc_intern);
686afe9f
CF		 540}
541
542static void vertex_update_firsthops(struct isis_vertex *vertex,
543 struct isis_vertex *parent)
544{
545 if (vertex->d_N <= 2)
8e3aae66 546 (void)hash_get(vertex->firsthops, vertex, hash_alloc_intern);
686afe9f
CF		 547
548 if (vertex->d_N < 2 || !parent)
549 return;
550
551 hash_iterate(parent->firsthops, vertex_add_parent_firsthop, vertex);
552}
553
eb5d44eb 554/*
555 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
556 */
d47d6089
RW		 557static struct isis_vertex *
558isis_spf_add2tent(struct isis_spftree *spftree, enum vertextype vtype, void *id,
559 uint32_t cost, int depth, struct isis_spf_adj *sadj,
560 struct isis_prefix_sid *psid, struct isis_vertex *parent)
eb5d44eb 561{
eb919f07 562 struct isis_vertex *vertex;
d62a17ae 563 struct listnode *node;
e886416f 564 bool last_hop;
321c1bbb 565 char buff[VID2STR_BUFFER];
eb5d44eb 566
75750ccf
EDP		 567 vertex = isis_find_vertex(&spftree->paths, id, vtype);
568 if (vertex != NULL) {
569 zlog_err(
570 "%s: vertex %s of type %s already in PATH; check for sysId collisions with established neighbors",
571 __func__, vid2string(vertex, buff, sizeof(buff)),
572 vtype2string(vertex->type));
573 return NULL;
574 }
575 vertex = isis_find_vertex(&spftree->tents, id, vtype);
576 if (vertex != NULL) {
577 zlog_err(
578 "%s: vertex %s of type %s already in TENT; check for sysId collisions with established neighbors",
579 __func__, vid2string(vertex, buff, sizeof(buff)),
580 vtype2string(vertex->type));
581 return NULL;
582 }
583
686afe9f 584 vertex = isis_vertex_new(spftree, id, vtype);
d62a17ae 585 vertex->d_N = cost;
586 vertex->depth = depth;
7700a88a 587 if (VTYPE_IP(vtype) && spftree->area->srdb.enabled && psid) {
2f7cc7bc
RW		 588 struct isis_area *area = spftree->area;
589 struct isis_vertex *vertex_psid;
590
591 /*
592 * Check if the Prefix-SID is already in use by another prefix.
593 */
594 vertex_psid = isis_spf_prefix_sid_lookup(spftree, psid);
595 if (vertex_psid
596 && !prefix_same(&vertex_psid->N.ip.p.dest,
597 &vertex->N.ip.p.dest)) {
598 flog_warn(
599 EC_ISIS_SID_COLLISION,
600 "ISIS-Sr (%s): collision detected, prefixes %pFX and %pFX share the same SID %s (%u)",
601 area->area_tag, &vertex->N.ip.p.dest,
602 &vertex_psid->N.ip.p.dest,
603 CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_VALUE)
604 ? "label"
605 : "index",
606 psid->value);
607 psid = NULL;
608 } else {
609 bool local;
610
611 local = (vertex->depth == 1);
612 vertex->N.ip.sr.sid = *psid;
613 vertex->N.ip.sr.label =
614 sr_prefix_in_label(area, psid, local);
7f8dddf4
HS		 615 vertex->N.ip.sr.algorithm = psid->algorithm;
616
2f7cc7bc
RW		 617 if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL)
618 vertex->N.ip.sr.present = true;
619
860b75b4
HS		 620#ifndef FABRICD
621 if (flex_algo_id_valid(spftree->algorithm) &&
622 !isis_flex_algo_elected_supported(
623 spftree->algorithm, spftree->area)) {
624 vertex->N.ip.sr.present = false;
625 vertex->N.ip.sr.label = MPLS_INVALID_LABEL;
626 }
627#endif /* ifndef FABRICD */
628
8e3aae66 629 (void)hash_get(spftree->prefix_sids, vertex,
630 hash_alloc_intern);
2f7cc7bc 631 }
d47d6089 632 }
d62a17ae 633
634 if (parent) {
635 listnode_add(vertex->parents, parent);
d62a17ae 636 }
637
7b36d36e 638 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC))
686afe9f
CF		 639 vertex_update_firsthops(vertex, parent);
640
e886416f 641 last_hop = (vertex->depth == 2);
d62a17ae 642 if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) {
7b36d36e
RW		 643 struct isis_vertex_adj *parent_vadj;
644
645 for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, parent_vadj))
e886416f
RW		 646 isis_vertex_adj_add(spftree, vertex, vertex->Adj_N,
647 parent_vadj->sadj, psid, last_hop);
7b36d36e 648 } else if (sadj) {
e886416f
RW		 649 isis_vertex_adj_add(spftree, vertex, vertex->Adj_N, sadj, psid,
650 last_hop);
d62a17ae 651 }
3f045a08 652
f390d2c7 653#ifdef EXTREME_DEBUG
b0814935
PG		 654 if (IS_DEBUG_SPF_EVENTS)
655 zlog_debug(
042ea8f2
LS		 656 "ISIS-SPF: A:%hhu add to TENT %s %s %s depth %d dist %d adjcount %d",
657 spftree->algorithm, print_sys_hostname(vertex->N.id),
b0814935
PG		 658 vtype2string(vertex->type),
659 vid2string(vertex, buff, sizeof(buff)), vertex->depth,
660 vertex->d_N, listcount(vertex->Adj_N));
eb5d44eb 661#endif /* EXTREME_DEBUG */
3f045a08 662
eb919f07 663 isis_vertex_queue_insert(&spftree->tents, vertex);
d62a17ae 664 return vertex;
665}
666
667static void isis_spf_add_local(struct isis_spftree *spftree,
668 enum vertextype vtype, void *id,
7b36d36e 669 struct isis_spf_adj *sadj, uint32_t cost,
d47d6089 670 struct isis_prefix_sid *psid,
d62a17ae 671 struct isis_vertex *parent)
672{
673 struct isis_vertex *vertex;
674
eb919f07 675 vertex = isis_find_vertex(&spftree->tents, id, vtype);
d62a17ae 676
677 if (vertex) {
678 /* C.2.5 c) */
679 if (vertex->d_N == cost) {
e886416f
RW		 680 if (sadj) {
681 bool last_hop = (vertex->depth == 2);
682
683 isis_vertex_adj_add(spftree, vertex,
684 vertex->Adj_N, sadj, psid,
685 last_hop);
686 }
d62a17ae 687 /* d) */
7b36d36e
RW		 688 if (!CHECK_FLAG(spftree->flags,
689 F_SPFTREE_NO_ADJACENCIES)
690 && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
d62a17ae 691 remove_excess_adjs(vertex->Adj_N);
9d303b37
DL		 692 if (parent && (listnode_lookup(vertex->parents, parent)
693 == NULL))
d62a17ae 694 listnode_add(vertex->parents, parent);
d62a17ae 695 return;
696 } else if (vertex->d_N < cost) {
697 /* e) do nothing */
698 return;
699 } else { /* vertex->d_N > cost */
700 /* f) */
eb919f07 701 isis_vertex_queue_delete(&spftree->tents, vertex);
d62a17ae 702 isis_vertex_del(vertex);
703 }
f390d2c7 704 }
d62a17ae 705
d47d6089 706 isis_spf_add2tent(spftree, vtype, id, cost, 1, sadj, psid, parent);
d62a17ae 707 return;
eb5d44eb 708}
709
d62a17ae 710static void process_N(struct isis_spftree *spftree, enum vertextype vtype,
711 void *id, uint32_t dist, uint16_t depth,
d47d6089 712 struct isis_prefix_sid *psid, struct isis_vertex *parent)
eb5d44eb 713{
d62a17ae 714 struct isis_vertex *vertex;
eb5d44eb 715#ifdef EXTREME_DEBUG
321c1bbb 716 char buff[VID2STR_BUFFER];
eb5d44eb 717#endif
718
d62a17ae 719 assert(spftree && parent);
720
7b36d36e 721 if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)
b30e837b
CF		 722 && !VTYPE_IS(vtype))
723 return;
724
321c1bbb 725 struct prefix_pair p;
af8ac8f9 726 if (vtype >= VTYPE_IPREACH_INTERNAL) {
321c1bbb
CF		 727 memcpy(&p, id, sizeof(p));
728 apply_mask(&p.dest);
8998807f 729 apply_mask(&p.src);
af8ac8f9
CF		 730 id = &p;
731 }
732
d62a17ae 733 /* RFC3787 section 5.1 */
734 if (spftree->area->newmetric == 1) {
735 if (dist > MAX_WIDE_PATH_METRIC)
736 return;
737 }
738 /* C.2.6 b) */
739 else if (spftree->area->oldmetric == 1) {
740 if (dist > MAX_NARROW_PATH_METRIC)
741 return;
742 }
743
744 /* c) */
eb919f07 745 vertex = isis_find_vertex(&spftree->paths, id, vtype);
d62a17ae 746 if (vertex) {
eb5d44eb 747#ifdef EXTREME_DEBUG
b0814935
PG		 748 if (IS_DEBUG_SPF_EVENTS)
749 zlog_debug(
042ea8f2
LS		 750 "ISIS-SPF: A:%hhu process_N %s %s %s dist %d already found from PATH",
751 spftree->algorithm,
b0814935
PG		 752 print_sys_hostname(vertex->N.id),
753 vtype2string(vtype),
754 vid2string(vertex, buff, sizeof(buff)), dist);
eb5d44eb 755#endif /* EXTREME_DEBUG */
d62a17ae 756 assert(dist >= vertex->d_N);
757 return;
758 }
759
eb919f07 760 vertex = isis_find_vertex(&spftree->tents, id, vtype);
d62a17ae 761 /* d) */
762 if (vertex) {
763/* 1) */
eb5d44eb 764#ifdef EXTREME_DEBUG
b0814935
PG		 765 if (IS_DEBUG_SPF_EVENTS)
766 zlog_debug(
042ea8f2
LS		 767 "ISIS-SPF: A:%hhu process_N %s %s %s dist %d parent %s adjcount %d",
768 spftree->algorithm,
b0814935
PG		 769 print_sys_hostname(vertex->N.id),
770 vtype2string(vtype),
771 vid2string(vertex, buff, sizeof(buff)), dist,
772 (parent ? print_sys_hostname(parent->N.id)
773 : "null"),
774 (parent ? listcount(parent->Adj_N) : 0));
eb5d44eb 775#endif /* EXTREME_DEBUG */
d62a17ae 776 if (vertex->d_N == dist) {
777 struct listnode *node;
7b36d36e 778 struct isis_vertex_adj *parent_vadj;
d62a17ae 779 for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node,
7b36d36e 780 parent_vadj))
e886416f
RW		 781 if (!isis_vertex_adj_exists(
782 spftree, vertex,
783 parent_vadj->sadj)) {
784 bool last_hop = (vertex->depth == 2);
785
d47d6089 786 isis_vertex_adj_add(spftree, vertex,
e886416f 787 vertex->Adj_N,
d47d6089 788 parent_vadj->sadj,
e886416f
RW		 789 psid, last_hop);
790 }
7b36d36e
RW		 791 if (CHECK_FLAG(spftree->flags,
792 F_SPFTREE_HOPCOUNT_METRIC))
686afe9f 793 vertex_update_firsthops(vertex, parent);
d62a17ae 794 /* 2) */
7b36d36e
RW		 795 if (!CHECK_FLAG(spftree->flags,
796 F_SPFTREE_NO_ADJACENCIES)
797 && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
d62a17ae 798 remove_excess_adjs(vertex->Adj_N);
799 if (listnode_lookup(vertex->parents, parent) == NULL)
800 listnode_add(vertex->parents, parent);
d62a17ae 801 return;
802 } else if (vertex->d_N < dist) {
803 return;
804 /* 4) */
805 } else {
eb919f07 806 isis_vertex_queue_delete(&spftree->tents, vertex);
d62a17ae 807 isis_vertex_del(vertex);
808 }
f390d2c7 809 }
f390d2c7 810
3f045a08 811#ifdef EXTREME_DEBUG
b0814935
PG		 812 if (IS_DEBUG_SPF_EVENTS)
813 zlog_debug(
042ea8f2
LS		 814 "ISIS-SPF: A:%hhu process_N add2tent %s %s dist %d parent %s",
815 spftree->algorithm, print_sys_hostname(id),
816 vtype2string(vtype), dist,
b0814935 817 (parent ? print_sys_hostname(parent->N.id) : "null"));
3f045a08
JB		 818#endif /* EXTREME_DEBUG */
819
d47d6089 820 isis_spf_add2tent(spftree, vtype, id, dist, depth, NULL, psid, parent);
d62a17ae 821 return;
eb5d44eb 822}
823
824/*
825 * C.2.6 Step 1
826 */
d62a17ae 827static int isis_spf_process_lsp(struct isis_spftree *spftree,
828 struct isis_lsp *lsp, uint32_t cost,
d7c0a89a 829 uint16_t depth, uint8_t *root_sysid,
d62a17ae 830 struct isis_vertex *parent)
eb5d44eb 831{
af8ac8f9
CF		 832 bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id);
833 struct listnode *fragnode = NULL;
d62a17ae 834 uint32_t dist;
d62a17ae 835 enum vertextype vtype;
d7c0a89a 836 static const uint8_t null_sysid[ISIS_SYS_ID_LEN];
af8ac8f9 837 struct isis_mt_router_info *mt_router_info = NULL;
321c1bbb 838 struct prefix_pair ip_info;
d47d6089 839 bool has_valid_psid;
af8ac8f9 840
c951ee6e 841 if (isis_lfa_excise_node_check(spftree, lsp->hdr.lsp_id)) {
2866b119 842 if (IS_DEBUG_LFA)
c951ee6e
RW		 843 zlog_debug("ISIS-LFA: excising node %s",
844 print_sys_hostname(lsp->hdr.lsp_id));
845 return ISIS_OK;
846 }
847
af8ac8f9
CF		 848 if (!lsp->tlvs)
849 return ISIS_OK;
d62a17ae 850
851 if (spftree->mtid != ISIS_MT_IPV4_UNICAST)
af8ac8f9
CF		 852 mt_router_info = isis_tlvs_lookup_mt_router_info(lsp->tlvs,
853 spftree->mtid);
d62a17ae 854
9d303b37 855 if (!pseudo_lsp && (spftree->mtid == ISIS_MT_IPV4_UNICAST
af8ac8f9
CF		 856 && !speaks(lsp->tlvs->protocols_supported.protocols,
857 lsp->tlvs->protocols_supported.count,
858 spftree->family))
d62a17ae 859 && !mt_router_info)
860 return ISIS_OK;
eb5d44eb 861
39a275aa 862 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
98c5bc15
CF		 863 bool no_overload = (pseudo_lsp
864 || (spftree->mtid == ISIS_MT_IPV4_UNICAST
39a275aa 865 && !ISIS_MASK_LSP_OL_BIT(lsp->hdr.lsp_bits))
98c5bc15 866 || (mt_router_info && !mt_router_info->overload));
39a275aa 867
f390d2c7 868lspfragloop:
af8ac8f9 869 if (lsp->hdr.seqno == 0) {
11106e28 870 zlog_warn("%s: lsp with 0 seq_num - ignore", __func__);
d62a17ae 871 return ISIS_WARNING;
872 }
f390d2c7 873
3f045a08 874#ifdef EXTREME_DEBUG
b0814935 875 if (IS_DEBUG_SPF_EVENTS)
042ea8f2
LS		 876 zlog_debug("ISIS-SPF: A:%hhu process_lsp %s",
877 spftree->algorithm,
b0814935 878 print_sys_hostname(lsp->hdr.lsp_id));
3f045a08
JB		 879#endif /* EXTREME_DEBUG */
880
39a275aa 881 if (no_overload) {
f7e61bbe
EDP		 882 if ((pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
883 && spftree->area->oldmetric) {
af8ac8f9
CF		 884 struct isis_oldstyle_reach *r;
885 for (r = (struct isis_oldstyle_reach *)
886 lsp->tlvs->oldstyle_reach.head;
887 r; r = r->next) {
a2d41bb0
CF		 888 if (fabricd)
889 continue;
890
d62a17ae 891 /* C.2.6 a) */
892 /* Two way connectivity */
7b36d36e
RW		 893 if (!LSP_PSEUDO_ID(r->id)
894 && !memcmp(r->id, root_sysid,
895 ISIS_SYS_ID_LEN))
d62a17ae 896 continue;
897 if (!pseudo_lsp
af8ac8f9 898 && !memcmp(r->id, null_sysid,
d62a17ae 899 ISIS_SYS_ID_LEN))
900 continue;
af8ac8f9 901 dist = cost + r->metric;
d62a17ae 902 process_N(spftree,
af8ac8f9 903 LSP_PSEUDO_ID(r->id)
d62a17ae 904 ? VTYPE_PSEUDO_IS
905 : VTYPE_NONPSEUDO_IS,
d47d6089 906 (void *)r->id, dist, depth + 1, NULL,
af8ac8f9 907 parent);
d62a17ae 908 }
909 }
910
f7e61bbe
EDP		 911 if (spftree->area->newmetric) {
912 struct isis_item_list *te_neighs = NULL;
913 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
914 te_neighs = &lsp->tlvs->extended_reach;
915 else
916 te_neighs = isis_lookup_mt_items(
917 &lsp->tlvs->mt_reach, spftree->mtid);
918
919 struct isis_extended_reach *er;
920 for (er = te_neighs ? (struct isis_extended_reach *)
921 te_neighs->head
922 : NULL;
923 er; er = er->next) {
924 /* C.2.6 a) */
925 /* Two way connectivity */
926 if (!LSP_PSEUDO_ID(er->id)
927 && !memcmp(er->id, root_sysid,
928 ISIS_SYS_ID_LEN))
929 continue;
930 if (!pseudo_lsp
931 && !memcmp(er->id, null_sysid,
932 ISIS_SYS_ID_LEN))
933 continue;
860b75b4
HS		 934#ifndef FABRICD
935
936 if (flex_algo_id_valid(spftree->algorithm) &&
937 (!sr_algorithm_participated(
938 lsp, spftree->algorithm) ||
939 isis_flex_algo_constraint_drop(spftree,
940 lsp, er)))
941 continue;
942#endif /* ifndef FABRICD */
943
f7e61bbe
EDP		 944 dist = cost
945 + (CHECK_FLAG(spftree->flags,
946 F_SPFTREE_HOPCOUNT_METRIC)
947 ? 1
948 : er->metric);
949 process_N(spftree,
950 LSP_PSEUDO_ID(er->id)
951 ? VTYPE_PSEUDO_TE_IS
952 : VTYPE_NONPSEUDO_TE_IS,
953 (void *)er->id, dist, depth + 1, NULL,
954 parent);
955 }
d62a17ae 956 }
f390d2c7 957 }
d62a17ae 958
3be6e411 959 if (!fabricd && !pseudo_lsp && spftree->family == AF_INET
f7e61bbe
EDP		 960 && spftree->mtid == ISIS_MT_IPV4_UNICAST
961 && spftree->area->oldmetric) {
af8ac8f9
CF		 962 struct isis_item_list *reachs[] = {
963 &lsp->tlvs->oldstyle_ip_reach,
964 &lsp->tlvs->oldstyle_ip_reach_ext};
d62a17ae 965
d62a17ae 966 for (unsigned int i = 0; i < array_size(reachs); i++) {
af8ac8f9
CF		 967 vtype = i ? VTYPE_IPREACH_EXTERNAL
968 : VTYPE_IPREACH_INTERNAL;
969
321c1bbb
CF		 970 memset(&ip_info, 0, sizeof(ip_info));
971 ip_info.dest.family = AF_INET;
972
af8ac8f9
CF		 973 struct isis_oldstyle_ip_reach *r;
974 for (r = (struct isis_oldstyle_ip_reach *)reachs[i]
975 ->head;
976 r; r = r->next) {
977 dist = cost + r->metric;
321c1bbb
CF		 978 ip_info.dest.u.prefix4 = r->prefix.prefix;
979 ip_info.dest.prefixlen = r->prefix.prefixlen;
980 process_N(spftree, vtype, &ip_info,
d47d6089 981 dist, depth + 1, NULL, parent);
d62a17ae 982 }
983 }
f390d2c7 984 }
d62a17ae 985
f7e61bbe
EDP		 986 /* we can skip all the rest if we're using metric style narrow */
987 if (!spftree->area->newmetric)
988 goto end;
989
d62a17ae 990 if (!pseudo_lsp && spftree->family == AF_INET) {
af8ac8f9
CF		 991 struct isis_item_list *ipv4_reachs;
992 if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
993 ipv4_reachs = &lsp->tlvs->extended_ip_reach;
994 else
995 ipv4_reachs = isis_lookup_mt_items(
996 &lsp->tlvs->mt_ip_reach, spftree->mtid);
997
321c1bbb
CF		 998 memset(&ip_info, 0, sizeof(ip_info));
999 ip_info.dest.family = AF_INET;
1000
af8ac8f9
CF		 1001 struct isis_extended_ip_reach *r;
1002 for (r = ipv4_reachs
1003 ? (struct isis_extended_ip_reach *)
1004 ipv4_reachs->head
1005 : NULL;
1006 r; r = r->next) {
1007 dist = cost + r->metric;
321c1bbb
CF		 1008 ip_info.dest.u.prefix4 = r->prefix.prefix;
1009 ip_info.dest.prefixlen = r->prefix.prefixlen;
d47d6089 1010
7700a88a 1011 /* Parse list of Prefix-SID subTLVs if SR is enabled */
d47d6089 1012 has_valid_psid = false;
7700a88a 1013 if (spftree->area->srdb.enabled && r->subtlvs) {
d47d6089
RW		 1014 for (struct isis_item *i =
1015 r->subtlvs->prefix_sids.head;
1016 i; i = i->next) {
1017 struct isis_prefix_sid *psid =
1018 (struct isis_prefix_sid *)i;
1019
7f8dddf4
HS		 1020 if (psid->algorithm !=
1021 spftree->algorithm)
d47d6089
RW		 1022 continue;
1023
860b75b4
HS		 1024#ifndef FABRICD
1025 if (flex_algo_id_valid(
1026 spftree->algorithm) &&
1027 (!sr_algorithm_participated(
1028 lsp, spftree->algorithm) ||
1029 !isis_flex_algo_elected_supported(
1030 spftree->algorithm,
1031 spftree->area)))
1032 continue;
1033#endif /* ifndef FABRICD */
1034
d47d6089
RW		 1035 has_valid_psid = true;
1036 process_N(spftree, VTYPE_IPREACH_TE,
1037 &ip_info, dist, depth + 1,
1038 psid, parent);
1039 /*
1040 * Stop the Prefix-SID iteration since
1041 * we only support the SPF algorithm for
1042 * now.
1043 */
1044 break;
1045 }
1046 }
1047 if (!has_valid_psid)
1048 process_N(spftree, VTYPE_IPREACH_TE, &ip_info,
1049 dist, depth + 1, NULL, parent);
f390d2c7 1050 }
f390d2c7 1051 }
d62a17ae 1052
1053 if (!pseudo_lsp && spftree->family == AF_INET6) {
af8ac8f9
CF		 1054 struct isis_item_list *ipv6_reachs;
1055 if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
1056 ipv6_reachs = &lsp->tlvs->ipv6_reach;
1057 else
1058 ipv6_reachs = isis_lookup_mt_items(
1059 &lsp->tlvs->mt_ipv6_reach, spftree->mtid);
1060
1061 struct isis_ipv6_reach *r;
1062 for (r = ipv6_reachs
1063 ? (struct isis_ipv6_reach *)ipv6_reachs->head
1064 : NULL;
1065 r; r = r->next) {
1066 dist = cost + r->metric;
1067 vtype = r->external ? VTYPE_IP6REACH_EXTERNAL
1068 : VTYPE_IP6REACH_INTERNAL;
321c1bbb
CF		 1069 memset(&ip_info, 0, sizeof(ip_info));
1070 ip_info.dest.family = AF_INET6;
1071 ip_info.dest.u.prefix6 = r->prefix.prefix;
1072 ip_info.dest.prefixlen = r->prefix.prefixlen;
1073
7700a88a
OD		 1074 if (spftree->area->srdb.enabled && r->subtlvs &&
1075 r->subtlvs->source_prefix &&
1076 r->subtlvs->source_prefix->prefixlen) {
321c1bbb
CF		 1077 if (spftree->tree_id != SPFTREE_DSTSRC) {
1078 char buff[VID2STR_BUFFER];
1079 zlog_warn("Ignoring dest-src route %s in non dest-src topology",
1080 srcdest2str(
1081 &ip_info.dest,
1082 r->subtlvs->source_prefix,
1083 buff, sizeof(buff)
1084 )
1085 );
1086 continue;
1087 }
1088 ip_info.src = *r->subtlvs->source_prefix;
1089 }
d47d6089
RW		 1090
1091 /* Parse list of Prefix-SID subTLVs */
1092 has_valid_psid = false;
1093 if (r->subtlvs) {
1094 for (struct isis_item *i =
1095 r->subtlvs->prefix_sids.head;
1096 i; i = i->next) {
1097 struct isis_prefix_sid *psid =
1098 (struct isis_prefix_sid *)i;
1099
7f8dddf4
HS		 1100 if (psid->algorithm !=
1101 spftree->algorithm)
d47d6089
RW		 1102 continue;
1103
860b75b4
HS		 1104#ifndef FABRICD
1105 if (flex_algo_id_valid(
1106 spftree->algorithm) &&
1107 (!sr_algorithm_participated(
1108 lsp, spftree->algorithm) ||
1109 !isis_flex_algo_elected_supported(
1110 spftree->algorithm,
1111 spftree->area)))
1112 continue;
1113#endif /* ifndef FABRICD */
1114
d47d6089
RW		 1115 has_valid_psid = true;
1116 process_N(spftree, vtype, &ip_info,
1117 dist, depth + 1, psid,
1118 parent);
1119 /*
1120 * Stop the Prefix-SID iteration since
1121 * we only support the SPF algorithm for
1122 * now.
1123 */
1124 break;
1125 }
1126 }
1127 if (!has_valid_psid)
1128 process_N(spftree, vtype, &ip_info, dist,
1129 depth + 1, NULL, parent);
d62a17ae 1130 }
f390d2c7 1131 }
d62a17ae 1132
f7e61bbe 1133end:
f3abc412 1134
77d73edf 1135 /* if attach bit set in LSP, attached-bit receive ignore is
1136 * not configured, we are a level-1 area and we have no other
1137 * level-2 | level1-2 areas then add a default route toward
1138 * this neighbor
f3abc412 1139 */
1140 if ((lsp->hdr.lsp_bits & LSPBIT_ATT) == LSPBIT_ATT
1141 && !spftree->area->attached_bit_rcv_ignore
a4777e46
IR		 1142 && (spftree->area->is_type & IS_LEVEL_1)
1143 && !isis_level2_adj_up(spftree->area)) {
f3abc412 1144 struct prefix_pair ip_info = { {0} };
77d73edf 1145 if (IS_DEBUG_RTE_EVENTS)
5d39a819
OD		 1146 zlog_debug("ISIS-Spf (%pLS): add default %s route",
1147 lsp->hdr.lsp_id,
f3abc412 1148 spftree->family == AF_INET ? "ipv4"
1149 : "ipv6");
1150
1151 if (spftree->family == AF_INET) {
1152 ip_info.dest.family = AF_INET;
1153 vtype = VTYPE_IPREACH_INTERNAL;
1154 } else {
1155 ip_info.dest.family = AF_INET6;
1156 vtype = VTYPE_IP6REACH_INTERNAL;
1157 }
1158 process_N(spftree, vtype, &ip_info, cost, depth + 1, NULL,
1159 parent);
1160 }
1161
d62a17ae 1162 if (fragnode == NULL)
1163 fragnode = listhead(lsp->lspu.frags);
1164 else
1165 fragnode = listnextnode(fragnode);
1166
1167 if (fragnode) {
1168 lsp = listgetdata(fragnode);
1169 goto lspfragloop;
1170 }
1171
1172 return ISIS_OK;
1173}
1174
7b36d36e
RW		 1175static struct isis_adjacency *adj_find(struct list *adj_list, const uint8_t *id,
1176 int level, uint16_t mtid, int family)
d62a17ae 1177{
d62a17ae 1178 struct isis_adjacency *adj;
7b36d36e
RW		 1179 struct listnode *node;
1180
1181 for (ALL_LIST_ELEMENTS_RO(adj_list, node, adj)) {
1182 if (!(adj->level & level))
d62a17ae 1183 continue;
7b36d36e 1184 if (memcmp(adj->sysid, id, ISIS_SYS_ID_LEN) != 0)
d62a17ae 1185 continue;
7b36d36e 1186 if (adj->adj_state != ISIS_ADJ_UP)
d62a17ae 1187 continue;
7b36d36e 1188 if (!adj_has_mt(adj, mtid))
d62a17ae 1189 continue;
7b36d36e
RW		 1190 if (mtid == ISIS_MT_IPV4_UNICAST
1191 && !speaks(adj->nlpids.nlpids, adj->nlpids.count, family))
d62a17ae 1192 continue;
7b36d36e
RW		 1193 return adj;
1194 }
1195
1196 return NULL;
1197}
1198
1199struct spf_preload_tent_ip_reach_args {
1200 struct isis_spftree *spftree;
1201 struct isis_vertex *parent;
1202};
1203
1204static int isis_spf_preload_tent_ip_reach_cb(const struct prefix *prefix,
1205 uint32_t metric, bool external,
1206 struct isis_subtlvs *subtlvs,
1207 void *arg)
1208{
1209 struct spf_preload_tent_ip_reach_args *args = arg;
1210 struct isis_spftree *spftree = args->spftree;
1211 struct isis_vertex *parent = args->parent;
1212 struct prefix_pair ip_info;
1213 enum vertextype vtype;
d47d6089 1214 bool has_valid_psid = false;
7b36d36e
RW		 1215
1216 if (external)
1217 return LSP_ITER_CONTINUE;
1218
1219 assert(spftree->family == prefix->family);
1220 memset(&ip_info, 0, sizeof(ip_info));
1221 prefix_copy(&ip_info.dest, prefix);
1222 apply_mask(&ip_info.dest);
1223
1224 if (prefix->family == AF_INET)
1225 vtype = VTYPE_IPREACH_INTERNAL;
1226 else
1227 vtype = VTYPE_IP6REACH_INTERNAL;
1228
7700a88a
OD		 1229 /* Parse list of Prefix-SID subTLVs if SR is enabled */
1230 if (spftree->area->srdb.enabled && subtlvs) {
d47d6089
RW		 1231 for (struct isis_item *i = subtlvs->prefix_sids.head; i;
1232 i = i->next) {
1233 struct isis_prefix_sid *psid =
1234 (struct isis_prefix_sid *)i;
1235
7f8dddf4 1236 if (psid->algorithm != spftree->algorithm)
d47d6089
RW		 1237 continue;
1238
1239 has_valid_psid = true;
1240 isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0,
1241 psid, parent);
1242
1243 /*
1244 * Stop the Prefix-SID iteration since we only support
1245 * the SPF algorithm for now.
1246 */
1247 break;
1248 }
1249 }
1250 if (!has_valid_psid)
1251 isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0, NULL,
1252 parent);
7b36d36e
RW		 1253
1254 return LSP_ITER_CONTINUE;
1255}
1256
1257static void isis_spf_preload_tent(struct isis_spftree *spftree,
1258 uint8_t *root_sysid,
1259 struct isis_lsp *root_lsp,
1260 struct isis_vertex *parent)
1261{
1262 struct spf_preload_tent_ip_reach_args ip_reach_args;
1263 struct isis_spf_adj *sadj;
1264 struct listnode *node;
1265
1266 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) {
1267 ip_reach_args.spftree = spftree;
1268 ip_reach_args.parent = parent;
1269 isis_lsp_iterate_ip_reach(
1270 root_lsp, spftree->family, spftree->mtid,
1271 isis_spf_preload_tent_ip_reach_cb, &ip_reach_args);
1272 }
1273
1274 /* Iterate over adjacencies. */
1275 for (ALL_LIST_ELEMENTS_RO(spftree->sadj_list, node, sadj)) {
c951ee6e 1276 const uint8_t *adj_id;
7b36d36e
RW		 1277 uint32_t metric;
1278
c951ee6e
RW		 1279 if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST))
1280 adj_id = sadj->lan.desig_is_id;
1281 else
1282 adj_id = sadj->id;
1283
1284 if (isis_lfa_excise_adj_check(spftree, adj_id)) {
2866b119 1285 if (IS_DEBUG_LFA)
5d39a819
OD		 1286 zlog_debug("ISIS-SPF: excising adjacency %pPN",
1287 sadj->id);
c951ee6e
RW		 1288 continue;
1289 }
1290
7b36d36e
RW		 1291 metric = CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)
1292 ? 1
1293 : sadj->metric;
1294 if (!LSP_PSEUDO_ID(sadj->id)) {
1295 isis_spf_add_local(spftree,
1296 CHECK_FLAG(sadj->flags,
1297 F_ISIS_SPF_ADJ_OLDMETRIC)
1298 ? VTYPE_NONPSEUDO_IS
1299 : VTYPE_NONPSEUDO_TE_IS,
d47d6089
RW		 1300 sadj->id, sadj, metric, NULL,
1301 parent);
2d560b3d
RW		 1302 } else if (sadj->lsp) {
1303 isis_spf_process_lsp(spftree, sadj->lsp, metric, 0,
1304 spftree->sysid, parent);
d62a17ae 1305 }
7b36d36e
RW		 1306 }
1307}
1308
75aa7aa1
RW		 1309struct spf_adj_find_reverse_metric_args {
1310 const uint8_t *id_self;
1311 uint32_t reverse_metric;
1312};
1313
1314static int spf_adj_find_reverse_metric_cb(const uint8_t *id, uint32_t metric,
1315 bool oldmetric,
1316 struct isis_ext_subtlvs *subtlvs,
1317 void *arg)
1318{
1319 struct spf_adj_find_reverse_metric_args *args = arg;
1320
1321 if (memcmp(id, args->id_self, ISIS_SYS_ID_LEN))
1322 return LSP_ITER_CONTINUE;
1323
1324 args->reverse_metric = metric;
1325
1326 return LSP_ITER_STOP;
1327}
1328
1329/*
1330 * Change all SPF adjacencies to use the link cost in the direction from the
1331 * next hop back towards root in place of the link cost in the direction away
1332 * from root towards the next hop.
1333 */
1334static void spf_adj_get_reverse_metrics(struct isis_spftree *spftree)
1335{
1336 struct isis_spf_adj *sadj;
1337 struct listnode *node, *nnode;
1338
1339 for (ALL_LIST_ELEMENTS(spftree->sadj_list, node, nnode, sadj)) {
1340 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
1341 struct isis_lsp *lsp_adj;
1342 const uint8_t *id_self;
1343 struct spf_adj_find_reverse_metric_args args;
1344
1345 /* Skip pseudonodes. */
1346 if (LSP_PSEUDO_ID(sadj->id))
1347 continue;
1348
1349 /* Find LSP of the corresponding adjacency. */
1350 memcpy(lspid, sadj->id, ISIS_SYS_ID_LEN);
1351 LSP_PSEUDO_ID(lspid) = 0;
1352 LSP_FRAGMENT(lspid) = 0;
1353 lsp_adj = lsp_search(spftree->lspdb, lspid);
1354 if (lsp_adj == NULL || lsp_adj->hdr.rem_lifetime == 0) {
1355 /* Delete one-way adjacency. */
1356 listnode_delete(spftree->sadj_list, sadj);
63e6e11f 1357 isis_spf_adj_free(sadj);
75aa7aa1
RW		 1358 continue;
1359 }
1360
1361 /* Find root node in the LSP of the adjacent router. */
1362 if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST))
1363 id_self = sadj->lan.desig_is_id;
1364 else
1365 id_self = spftree->sysid;
1366 args.id_self = id_self;
1367 args.reverse_metric = UINT32_MAX;
1368 isis_lsp_iterate_is_reach(lsp_adj, spftree->mtid,
1369 spf_adj_find_reverse_metric_cb,
1370 &args);
1371 if (args.reverse_metric == UINT32_MAX) {
1372 /* Delete one-way adjacency. */
1373 listnode_delete(spftree->sadj_list, sadj);
63e6e11f 1374 isis_spf_adj_free(sadj);
75aa7aa1
RW		 1375 continue;
1376 }
1377 sadj->metric = args.reverse_metric;
1378 }
1379}
1380
7b36d36e
RW		 1381static void spf_adj_list_parse_tlv(struct isis_spftree *spftree,
1382 struct list *adj_list, const uint8_t *id,
1383 const uint8_t *desig_is_id,
1384 uint32_t pseudo_metric, uint32_t metric,
1385 bool oldmetric,
1386 struct isis_ext_subtlvs *subtlvs)
1387{
1388 struct isis_spf_adj *sadj;
2d560b3d
RW		 1389 uint8_t lspid[ISIS_SYS_ID_LEN + 2];
1390 struct isis_lsp *lsp;
7b36d36e
RW		 1391 uint8_t flags = 0;
1392
1393 /* Skip self in the pseudonode. */
1394 if (desig_is_id && !memcmp(id, spftree->sysid, ISIS_SYS_ID_LEN))
1395 return;
1396
2d560b3d
RW		 1397 /* Find LSP from the adjacency. */
1398 memcpy(lspid, id, ISIS_SYS_ID_LEN + 1);
1399 LSP_FRAGMENT(lspid) = 0;
1400 lsp = lsp_search(spftree->lspdb, lspid);
1401 if (lsp == NULL || lsp->hdr.rem_lifetime == 0) {
5d39a819
OD		 1402 zlog_warn("ISIS-SPF: No LSP found from root to L%d %pLS",
1403 spftree->level, lspid);
2d560b3d
RW		 1404 return;
1405 }
1406
7b36d36e
RW		 1407 sadj = XCALLOC(MTYPE_ISIS_SPF_ADJ, sizeof(*sadj));
1408 memcpy(sadj->id, id, sizeof(sadj->id));
1409 if (desig_is_id) {
1410 memcpy(sadj->lan.desig_is_id, desig_is_id,
1411 sizeof(sadj->lan.desig_is_id));
1412 SET_FLAG(flags, F_ISIS_SPF_ADJ_BROADCAST);
1413 sadj->metric = pseudo_metric;
1414 } else
1415 sadj->metric = metric;
1416 if (oldmetric)
1417 SET_FLAG(flags, F_ISIS_SPF_ADJ_OLDMETRIC);
2d560b3d 1418 sadj->lsp = lsp;
7b36d36e
RW		 1419 sadj->subtlvs = subtlvs;
1420 sadj->flags = flags;
1421
e886416f
RW		 1422 if ((oldmetric && metric == ISIS_NARROW_METRIC_INFINITY)
1423 || (!oldmetric && metric == ISIS_WIDE_METRIC_INFINITY))
1424 SET_FLAG(flags, F_ISIS_SPF_ADJ_METRIC_INFINITY);
1425
7b36d36e
RW		 1426 /* Set real adjacency. */
1427 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)
1428 && !LSP_PSEUDO_ID(id)) {
1429 struct isis_adjacency *adj;
1430
1431 adj = adj_find(adj_list, id, spftree->level, spftree->mtid,
1432 spftree->family);
1433 if (!adj) {
1434 XFREE(MTYPE_ISIS_SPF_ADJ, sadj);
1435 return;
d62a17ae 1436 }
7b36d36e
RW		 1437
1438 listnode_delete(adj_list, adj);
1439 sadj->adj = adj;
1440 }
1441
1442 /* Add adjacency to the list. */
1443 listnode_add(spftree->sadj_list, sadj);
1444
c951ee6e
RW		 1445 if (!LSP_PSEUDO_ID(id)) {
1446 struct isis_spf_node *node;
1447
1448 node = isis_spf_node_find(&spftree->adj_nodes, id);
1449 if (!node)
1450 node = isis_spf_node_new(&spftree->adj_nodes, id);
1451 if (node->best_metric == 0 || sadj->metric < node->best_metric)
1452 node->best_metric = sadj->metric;
1453 listnode_add(node->adjacencies, sadj);
1454 }
1455
7b36d36e 1456 /* Parse pseudonode LSP too. */
2d560b3d
RW		 1457 if (LSP_PSEUDO_ID(id))
1458 spf_adj_list_parse_lsp(spftree, adj_list, lsp, id, metric);
7b36d36e
RW		 1459}
1460
cab7be7d
LS		 1461static void spf_adj_list_parse_lsp(struct isis_spftree *spftree,
1462 struct list *adj_list, struct isis_lsp *lsp,
1463 const uint8_t *pseudo_nodeid,
1464 uint32_t pseudo_metric)
7b36d36e
RW		 1465{
1466 bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id);
cab7be7d
LS		 1467 struct isis_lsp *frag;
1468 struct listnode *node;
7b36d36e
RW		 1469 struct isis_item *head;
1470 struct isis_item_list *te_neighs;
1471
1472 if (lsp->hdr.seqno == 0 || lsp->hdr.rem_lifetime == 0)
1473 return;
1474
8c8a5a02 1475 /* Parse LSP. */
7b36d36e
RW		 1476 if (lsp->tlvs) {
1477 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) {
1478 head = lsp->tlvs->oldstyle_reach.head;
1479 for (struct isis_oldstyle_reach *reach =
1480 (struct isis_oldstyle_reach *)head;
1481 reach; reach = reach->next) {
1482 spf_adj_list_parse_tlv(
1483 spftree, adj_list, reach->id,
1484 pseudo_nodeid, pseudo_metric,
1485 reach->metric, true, NULL);
d62a17ae 1486 }
7b36d36e
RW		 1487 }
1488
1489 if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
1490 te_neighs = &lsp->tlvs->extended_reach;
1491 else
1492 te_neighs = isis_get_mt_items(&lsp->tlvs->mt_reach,
1493 spftree->mtid);
1494 if (te_neighs) {
1495 head = te_neighs->head;
1496 for (struct isis_extended_reach *reach =
1497 (struct isis_extended_reach *)head;
1498 reach; reach = reach->next) {
860b75b4
HS		 1499#ifndef FABRICD
1500 /*
1501 * cutting out adjacency by flex-algo link
1502 * affinity attribute
1503 */
1504 if (flex_algo_id_valid(spftree->algorithm) &&
1505 (!sr_algorithm_participated(
1506 lsp, spftree->algorithm) ||
1507 isis_flex_algo_constraint_drop(
1508 spftree, lsp, reach)))
1509 continue;
1510#endif /* ifndef FABRICD */
1511
7b36d36e
RW		 1512 spf_adj_list_parse_tlv(
1513 spftree, adj_list, reach->id,
1514 pseudo_nodeid, pseudo_metric,
1515 reach->metric, false, reach->subtlvs);
d62a17ae 1516 }
d62a17ae 1517 }
f390d2c7 1518 }
eb5d44eb 1519
8c8a5a02
LS		 1520 if (LSP_FRAGMENT(lsp->hdr.lsp_id))
1521 return;
1522
7b36d36e
RW		 1523 /* Parse LSP fragments. */
1524 for (ALL_LIST_ELEMENTS_RO(lsp->lspu.frags, node, frag)) {
1525 if (!frag->tlvs)
1526 continue;
1527
cab7be7d
LS		 1528 spf_adj_list_parse_lsp(spftree, adj_list, frag, pseudo_nodeid,
1529 pseudo_metric);
7b36d36e
RW		 1530 }
1531}
1532
1533static void isis_spf_build_adj_list(struct isis_spftree *spftree,
1534 struct isis_lsp *lsp)
1535{
1536 struct list *adj_list = NULL;
1537
1538 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
1539 adj_list = list_dup(spftree->area->adjacency_list);
1540
1541 spf_adj_list_parse_lsp(spftree, adj_list, lsp, NULL, 0);
1542
1543 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
1544 list_delete(&adj_list);
75aa7aa1
RW		 1545
1546 if (spftree->type == SPF_TYPE_REVERSE)
1547 spf_adj_get_reverse_metrics(spftree);
eb5d44eb 1548}
1549
1550/*
1551 * The parent(s) for vertex is set when added to TENT list
1552 * now we just put the child pointer(s) in place
1553 */
d62a17ae 1554static void add_to_paths(struct isis_spftree *spftree,
1555 struct isis_vertex *vertex)
eb5d44eb 1556{
48c14b34 1557#ifdef EXTREME_DEBUG
321c1bbb 1558 char buff[VID2STR_BUFFER];
48c14b34 1559#endif /* EXTREME_DEBUG */
3f045a08 1560
ae9c9aba 1561 if (isis_find_vertex(&spftree->paths, &vertex->N, vertex->type))
d62a17ae 1562 return;
bded4060 1563 isis_vertex_queue_append(&spftree->paths, vertex);
eb5d44eb 1564
f390d2c7 1565#ifdef EXTREME_DEBUG
b0814935 1566 if (IS_DEBUG_SPF_EVENTS)
042ea8f2
LS		 1567 zlog_debug(
1568 "ISIS-SPF: A:%hhu S:%p added %s %s %s depth %d dist %d to PATHS",
1569 spftree->algorithm, spftree,
1570 print_sys_hostname(vertex->N.id),
1571 vtype2string(vertex->type),
1572 vid2string(vertex, buff, sizeof(buff)), vertex->depth,
1573 vertex->d_N);
f390d2c7 1574#endif /* EXTREME_DEBUG */
48c14b34
RW		 1575}
1576
1577static void init_spt(struct isis_spftree *spftree, int mtid)
1578{
1579 /* Clear data from previous run. */
2f7cc7bc 1580 hash_clean(spftree->prefix_sids, NULL);
48c14b34
RW		 1581 isis_spf_node_list_clear(&spftree->adj_nodes);
1582 list_delete_all_node(spftree->sadj_list);
1583 isis_vertex_queue_clear(&spftree->tents);
1584 isis_vertex_queue_clear(&spftree->paths);
16fe8cff
RW		 1585 isis_zebra_rlfa_unregister_all(spftree);
1586 isis_rlfa_list_clear(spftree);
1587 list_delete_all_node(spftree->lfa.remote.pc_spftrees);
fc156c28
RW		 1588 memset(&spftree->lfa.protection_counters, 0,
1589 sizeof(spftree->lfa.protection_counters));
48c14b34
RW		 1590
1591 spftree->mtid = mtid;
1592}
1593
e886416f
RW		 1594static enum spf_prefix_priority
1595spf_prefix_priority(struct isis_spftree *spftree, struct isis_vertex *vertex)
1596{
1597 struct isis_area *area = spftree->area;
1598 struct prefix *prefix = &vertex->N.ip.p.dest;
1599
1600 for (int priority = SPF_PREFIX_PRIO_CRITICAL;
1601 priority <= SPF_PREFIX_PRIO_MEDIUM; priority++) {
1602 struct spf_prefix_priority_acl *ppa;
1603 enum filter_type ret = FILTER_PERMIT;
1604
1605 ppa = &area->spf_prefix_priorities[priority];
1606 switch (spftree->family) {
1607 case AF_INET:
1608 ret = access_list_apply(ppa->list_v4, prefix);
1609 break;
1610 case AF_INET6:
1611 ret = access_list_apply(ppa->list_v6, prefix);
1612 break;
1613 default:
1614 break;
1615 }
1616
1617 if (ret == FILTER_PERMIT)
1618 return priority;
1619 }
1620
1621 /* Assign medium priority to loopback prefixes by default. */
1622 if (is_host_route(prefix))
1623 return SPF_PREFIX_PRIO_MEDIUM;
1624
1625 return SPF_PREFIX_PRIO_LOW;
1626}
1627
48c14b34
RW		 1628static void spf_path_process(struct isis_spftree *spftree,
1629 struct isis_vertex *vertex)
1630{
1631 struct isis_area *area = spftree->area;
e886416f 1632 int level = spftree->level;
48c14b34 1633 char buff[VID2STR_BUFFER];
3f045a08 1634
e886416f 1635 if (spftree->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type)
054fda12
RW		 1636 && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) {
1637 if (listcount(vertex->Adj_N) > 0) {
e886416f 1638 struct isis_adjacency *adj;
054fda12 1639
e886416f
RW		 1640 if (isis_tilfa_check(spftree, vertex) != 0)
1641 return;
054fda12 1642
e886416f
RW		 1643 adj = isis_adj_find(area, level, vertex->N.id);
1644 if (adj)
1645 sr_adj_sid_add_single(adj, spftree->family,
1646 true, vertex->Adj_N);
054fda12
RW		 1647 } else if (IS_DEBUG_SPF_EVENTS)
1648 zlog_debug(
d240e5c8 1649 "ISIS-SPF: no adjacencies, do not install backup Adj-SID for %s depth %d dist %d",
054fda12
RW		 1650 vid2string(vertex, buff, sizeof(buff)),
1651 vertex->depth, vertex->d_N);
1652 }
1653
7b36d36e
RW		 1654 if (VTYPE_IP(vertex->type)
1655 && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ROUTES)) {
e886416f
RW		 1656 enum spf_prefix_priority priority;
1657
1658 priority = spf_prefix_priority(spftree, vertex);
1659 vertex->N.ip.priority = priority;
d4fcd8bd 1660 if (vertex->depth == 1 || listcount(vertex->Adj_N) > 0) {
16fe8cff 1661 struct isis_spftree *pre_spftree;
a348c945
DS		 1662 struct route_table *route_table = NULL;
1663 bool allow_ecmp = false;
c951ee6e 1664
16fe8cff
RW		 1665 switch (spftree->type) {
1666 case SPF_TYPE_RLFA:
1667 case SPF_TYPE_TI_LFA:
e886416f
RW		 1668 if (priority
1669 > area->lfa_priority_limit[level - 1]) {
1670 if (IS_DEBUG_LFA)
1671 zlog_debug(
1672 "ISIS-LFA: skipping %s %s (low prefix priority)",
1673 vtype2string(
1674 vertex->type),
1675 vid2string(
1676 vertex, buff,
1677 sizeof(buff)));
c951ee6e 1678 return;
e886416f 1679 }
16fe8cff 1680 break;
a348c945
DS		 1681 case SPF_TYPE_FORWARD:
1682 case SPF_TYPE_REVERSE:
16fe8cff
RW		 1683 break;
1684 }
e886416f 1685
16fe8cff
RW		 1686 switch (spftree->type) {
1687 case SPF_TYPE_RLFA:
1688 isis_rlfa_check(spftree, vertex);
1689 return;
1690 case SPF_TYPE_TI_LFA:
e886416f
RW		 1691 if (isis_tilfa_check(spftree, vertex) != 0)
1692 return;
1693
1694 pre_spftree = spftree->lfa.old.spftree;
1695 route_table = pre_spftree->route_table_backup;
1696 allow_ecmp = area->lfa_load_sharing[level - 1];
fc156c28
RW		 1697 pre_spftree->lfa.protection_counters
1698 .tilfa[vertex->N.ip.priority] += 1;
16fe8cff 1699 break;
a348c945
DS		 1700 case SPF_TYPE_FORWARD:
1701 case SPF_TYPE_REVERSE:
c951ee6e 1702 route_table = spftree->route_table;
e886416f 1703 allow_ecmp = true;
fc156c28
RW		 1704
1705 /*
1706 * Update LFA protection counters (ignore local
1707 * routes).
1708 */
1709 if (vertex->depth > 1) {
1710 spftree->lfa.protection_counters
1711 .total[priority] += 1;
1712 if (listcount(vertex->Adj_N) > 1)
1713 spftree->lfa.protection_counters
1714 .ecmp[priority] += 1;
1715 }
16fe8cff 1716 break;
e886416f 1717 }
c951ee6e 1718
042ea8f2
LS		 1719#ifdef EXTREME_DEBUG
1720 struct isis_route_info *ri =
1721#endif /* EXTREME_DEBUG */
1722 isis_route_create(&vertex->N.ip.p.dest,
1723 &vertex->N.ip.p.src,
1724 vertex->d_N, vertex->depth,
1725 &vertex->N.ip.sr,
1726 vertex->Adj_N, allow_ecmp,
1727 area, route_table);
1728
1729#ifdef EXTREME_DEBUG
1730 zlog_debug(
1731 "ISIS-SPF: A:%hhu create route pfx %pFX dist %d, sr.algo %d, table %p, rv %p",
1732 spftree->algorithm, &vertex->N.ip.p.dest,
1733 vertex->d_N, vertex->N.ip.sr.algorithm,
1734 route_table, ri);
1735#endif /* EXTREME_DEBUG */
c951ee6e 1736 } else if (IS_DEBUG_SPF_EVENTS)
d62a17ae 1737 zlog_debug(
d240e5c8 1738 "ISIS-SPF: no adjacencies, do not install route for %s depth %d dist %d",
d62a17ae 1739 vid2string(vertex, buff, sizeof(buff)),
1740 vertex->depth, vertex->d_N);
1741 }
b30e837b
CF		 1742}
1743
1744static void isis_spf_loop(struct isis_spftree *spftree,
1745 uint8_t *root_sysid)
1746{
1747 struct isis_vertex *vertex;
b30e837b 1748 struct isis_lsp *lsp;
48c14b34 1749 struct listnode *node;
b30e837b
CF		 1750
1751 while (isis_vertex_queue_count(&spftree->tents)) {
1752 vertex = isis_vertex_queue_pop(&spftree->tents);
1753
1754#ifdef EXTREME_DEBUG
042ea8f2
LS		 1755 zlog_debug(
1756 "ISIS-SPF: A:%hhu get TENT node %s %s depth %d dist %d to PATHS",
1757 spftree->algorithm, print_sys_hostname(vertex->N.id),
1758 vtype2string(vertex->type), vertex->depth, vertex->d_N);
b30e837b
CF		 1759#endif /* EXTREME_DEBUG */
1760
1761 add_to_paths(spftree, vertex);
cbd8e49e
CF		 1762 if (!VTYPE_IS(vertex->type))
1763 continue;
1764
1765 lsp = lsp_for_vertex(spftree, vertex);
1766 if (!lsp) {
5d39a819
OD		 1767 zlog_warn("ISIS-SPF: No LSP found for %pPN",
1768 vertex->N.id);
cbd8e49e 1769 continue;
b30e837b 1770 }
cbd8e49e
CF		 1771
1772 isis_spf_process_lsp(spftree, lsp, vertex->d_N, vertex->depth,
1773 root_sysid, vertex);
b30e837b 1774 }
48c14b34
RW		 1775
1776 /* Generate routes once the SPT is formed. */
1777 for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) {
1778 /* New-style TLVs take precedence over the old-style TLVs. */
1779 switch (vertex->type) {
1780 case VTYPE_IPREACH_INTERNAL:
1781 case VTYPE_IPREACH_EXTERNAL:
1782 if (isis_find_vertex(&spftree->paths, &vertex->N,
1783 VTYPE_IPREACH_TE))
1784 continue;
1785 break;
a348c945
DS		 1786 case VTYPE_PSEUDO_IS:
1787 case VTYPE_PSEUDO_TE_IS:
1788 case VTYPE_NONPSEUDO_IS:
1789 case VTYPE_NONPSEUDO_TE_IS:
1790 case VTYPE_ES:
1791 case VTYPE_IPREACH_TE:
1792 case VTYPE_IP6REACH_INTERNAL:
1793 case VTYPE_IP6REACH_EXTERNAL:
48c14b34
RW		 1794 break;
1795 }
1796
1797 spf_path_process(spftree, vertex);
1798 }
b30e837b
CF		 1799}
1800
1801struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area,
1802 uint8_t *sysid,
1803 struct isis_spftree *spftree)
1804{
1805 if (!spftree)
329f87b3
HS		 1806 spftree = isis_spftree_new(
1807 area, &area->lspdb[IS_LEVEL_2 - 1], sysid, ISIS_LEVEL2,
1808 SPFTREE_IPV4, SPF_TYPE_FORWARD,
1809 F_SPFTREE_HOPCOUNT_METRIC, SR_ALGORITHM_SPF);
eab88f36 1810
7b36d36e 1811 init_spt(spftree, ISIS_MT_IPV4_UNICAST);
eab88f36 1812 if (!memcmp(sysid, area->isis->sysid, ISIS_SYS_ID_LEN)) {
7b36d36e
RW		 1813 struct isis_lsp *root_lsp;
1814 struct isis_vertex *root_vertex;
1815
1816 root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid);
1817 if (root_lsp) {
1818 /*
1819 * If we are running locally, initialize with
1820 * information from adjacencies
1821 */
1822 root_vertex = isis_spf_add_root(spftree);
1823
1824 isis_spf_preload_tent(spftree, sysid, root_lsp,
1825 root_vertex);
1826 }
b30e837b 1827 } else {
7b36d36e
RW		 1828 isis_vertex_queue_insert(
1829 &spftree->tents,
1830 isis_vertex_new(spftree, sysid, VTYPE_NONPSEUDO_TE_IS));
b30e837b
CF		 1831 }
1832
1833 isis_spf_loop(spftree, sysid);
1834
1835 return spftree;
eb5d44eb 1836}
1837
7b36d36e 1838void isis_run_spf(struct isis_spftree *spftree)
eb5d44eb 1839{
7b36d36e 1840 struct isis_lsp *root_lsp;
d62a17ae 1841 struct isis_vertex *root_vertex;
e26e2c15
RW		 1842 struct timeval time_start;
1843 struct timeval time_end;
7b36d36e 1844 struct isis_mt_router_info *mt_router_info;
6d38d078 1845 uint16_t mtid = 0;
9ed86fe0
LS		 1846#ifndef FABRICD
1847 bool flex_algo_enabled;
1848#endif /* ifndef FABRICD */
d62a17ae 1849
1850 /* Get time that can't roll backwards. */
e26e2c15 1851 monotime(&time_start);
d62a17ae 1852
7b36d36e
RW		 1853 root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid);
1854 if (root_lsp == NULL) {
d240e5c8 1855 zlog_err("ISIS-SPF: could not find own l%d LSP!",
7b36d36e
RW		 1856 spftree->level);
1857 return;
1858 }
1859
1860 /* Get Multi-Topology ID. */
1861 switch (spftree->tree_id) {
6d38d078 1862 case SPFTREE_IPV4:
6d38d078
CF		 1863 mtid = ISIS_MT_IPV4_UNICAST;
1864 break;
1865 case SPFTREE_IPV6:
7b36d36e
RW		 1866 mt_router_info = isis_tlvs_lookup_mt_router_info(
1867 root_lsp->tlvs, ISIS_MT_IPV6_UNICAST);
1868 if (mt_router_info)
1869 mtid = ISIS_MT_IPV6_UNICAST;
1870 else
1871 mtid = ISIS_MT_IPV4_UNICAST;
6d38d078 1872 break;
321c1bbb 1873 case SPFTREE_DSTSRC:
321c1bbb
CF		 1874 mtid = ISIS_MT_IPV6_DSTSRC;
1875 break;
6d38d078 1876 case SPFTREE_COUNT:
7b36d36e 1877 zlog_err(
11106e28 1878 "%s should never be called with SPFTREE_COUNT as argument!",
1879 __func__);
7b36d36e 1880 exit(1);
6d38d078
CF		 1881 }
1882
860b75b4
HS		 1883#ifndef FABRICD
1884 /* If a node is configured to participate in a particular Flexible-
1885 * Algorithm, but there is no valid Flex-Algorithm definition available
1886 * for it, or the selected Flex-Algorithm definition includes
1887 * calculation-type, metric-type, constraint, flag, or Sub-TLV that is
1888 * not supported by the node, it MUST stop participating in such
1889 * Flexible-Algorithm.
1890 */
9ed86fe0
LS		 1891 if (flex_algo_id_valid(spftree->algorithm)) {
1892 flex_algo_enabled = isis_flex_algo_elected_supported(
1893 spftree->algorithm, spftree->area);
1894 if (flex_algo_enabled !=
1895 flex_algo_get_state(spftree->area->flex_algos,
1896 spftree->algorithm)) {
1897 /* actual state is inconsistent with local LSP */
860b75b4
HS		 1898 lsp_regenerate_schedule(spftree->area,
1899 spftree->area->is_type, 0);
9ed86fe0
LS		 1900 goto out;
1901 }
1902 if (!flex_algo_enabled) {
1903 if (!CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
1904 isis_spftree_clear(spftree);
1905 SET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
1906 lsp_regenerate_schedule(spftree->area,
1907 spftree->area->is_type,
1908 0);
1909 }
1910 goto out;
860b75b4 1911 }
860b75b4
HS		 1912 }
1913#endif /* ifndef FABRICD */
1914
d62a17ae 1915 /*
1916 * C.2.5 Step 0
1917 */
7b36d36e 1918 init_spt(spftree, mtid);
d62a17ae 1919 /* a) */
7b36d36e 1920 root_vertex = isis_spf_add_root(spftree);
d62a17ae 1921 /* b) */
7b36d36e
RW		 1922 isis_spf_build_adj_list(spftree, root_lsp);
1923 isis_spf_preload_tent(spftree, spftree->sysid, root_lsp, root_vertex);
d62a17ae 1924
1925 /*
1926 * C.2.7 Step 2
1927 */
ce837d81 1928 if (!isis_vertex_queue_count(&spftree->tents)
e740f9c1 1929 && (IS_DEBUG_SPF_EVENTS)) {
d240e5c8 1930 zlog_warn("ISIS-SPF: TENT is empty SPF-root:%s",
7b36d36e 1931 print_sys_hostname(spftree->sysid));
d62a17ae 1932 }
1933
7b36d36e 1934 isis_spf_loop(spftree, spftree->sysid);
860b75b4
HS		 1935
1936
1937#ifndef FABRICD
1938 /* flex-algo */
1939 if (CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
1940 UNSET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
1941 lsp_regenerate_schedule(spftree->area, spftree->area->is_type,
1942 0);
1943 }
1944
1945out:
1946#endif /* ifndef FABRICD */
d62a17ae 1947 spftree->runcount++;
1948 spftree->last_run_timestamp = time(NULL);
e26e2c15
RW		 1949 spftree->last_run_monotime = monotime(&time_end);
1950 spftree->last_run_duration =
1951 ((time_end.tv_sec - time_start.tv_sec) * 1000000)
1952 + (time_end.tv_usec - time_start.tv_usec);
eb5d44eb 1953}
1954
c951ee6e
RW		 1955static void isis_run_spf_with_protection(struct isis_area *area,
1956 struct isis_spftree *spftree)
1957{
1958 /* Run forward SPF locally. */
1959 memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN);
1960 isis_run_spf(spftree);
1961
1962 /* Run LFA protection if configured. */
e886416f
RW		 1963 if (area->lfa_protected_links[spftree->level - 1] > 0
1964 || area->tilfa_protected_links[spftree->level - 1] > 0)
c951ee6e
RW		 1965 isis_spf_run_lfa(area, spftree);
1966}
1967
80ef2e89
HS		 1968void isis_spf_verify_routes(struct isis_area *area, struct isis_spftree **trees,
1969 int tree)
3dace42d
CF		 1970{
1971 if (area->is_type == IS_LEVEL_1) {
c951ee6e 1972 isis_route_verify_table(area, trees[0]->route_table,
80ef2e89 1973 trees[0]->route_table_backup, tree);
3dace42d 1974 } else if (area->is_type == IS_LEVEL_2) {
c951ee6e 1975 isis_route_verify_table(area, trees[1]->route_table,
80ef2e89 1976 trees[1]->route_table_backup, tree);
3dace42d
CF		 1977 } else {
1978 isis_route_verify_merge(area, trees[0]->route_table,
c951ee6e
RW		 1979 trees[0]->route_table_backup,
1980 trees[1]->route_table,
80ef2e89 1981 trees[1]->route_table_backup, tree);
3dace42d
CF		 1982 }
1983}
1984
1985void isis_spf_invalidate_routes(struct isis_spftree *tree)
1986{
7153c3ca
HS		 1987 struct isis_route_table_info *backup_info;
1988
3dace42d 1989 isis_route_invalidate_table(tree->area, tree->route_table);
c951ee6e
RW		 1990
1991 /* Delete backup routes. */
7153c3ca
HS		 1992
1993 backup_info = tree->route_table_backup->info;
c951ee6e 1994 route_table_finish(tree->route_table_backup);
7153c3ca 1995 isis_route_table_info_free(backup_info);
c951ee6e 1996 tree->route_table_backup = srcdest_table_init();
7153c3ca
HS		 1997 tree->route_table_backup->info =
1998 isis_route_table_info_alloc(tree->algorithm);
c951ee6e 1999 tree->route_table_backup->cleanup = isis_route_node_cleanup;
3dace42d
CF		 2000}
2001
694fa867
LS		 2002void isis_spf_switchover_routes(struct isis_area *area,
2003 struct isis_spftree **trees, int family,
2004 union g_addr *nexthop_ip, ifindex_t ifindex,
2005 int level)
2006{
2007 isis_route_switchover_nexthop(area, trees[level - 1]->route_table,
2008 family, nexthop_ip, ifindex);
2009}
2010
e6685141 2011static void isis_run_spf_cb(struct event *thread)
eb5d44eb 2012{
e16d030c 2013 struct isis_spf_run *run = EVENT_ARG(thread);
d62a17ae 2014 struct isis_area *area = run->area;
2015 int level = run->level;
1ee746d9 2016 int have_run = 0;
860b75b4
HS		 2017 struct listnode *node;
2018 struct isis_circuit *circuit;
2019#ifndef FABRICD
2020 struct flex_algo *fa;
2021 struct isis_flex_algo_data *data;
2022#endif /* ifndef FABRICD */
d62a17ae 2023
2024 XFREE(MTYPE_ISIS_SPF_RUN, run);
d62a17ae 2025
2026 if (!(area->is_type & level)) {
e740f9c1 2027 if (IS_DEBUG_SPF_EVENTS)
d62a17ae 2028 zlog_warn("ISIS-SPF (%s) area does not share level",
2029 area->area_tag);
cc9f21da 2030 return;
d62a17ae 2031 }
eb5d44eb 2032
054fda12 2033 isis_area_delete_backup_adj_sids(area, level);
3dace42d
CF		 2034 isis_area_invalidate_routes(area, level);
2035
e740f9c1 2036 if (IS_DEBUG_SPF_EVENTS)
d240e5c8 2037 zlog_debug("ISIS-SPF (%s) L%d SPF needed, periodic SPF",
d62a17ae 2038 area->area_tag, level);
f390d2c7 2039
1ee746d9 2040 if (area->ip_circuits) {
c951ee6e
RW		 2041 isis_run_spf_with_protection(
2042 area, area->spftree[SPFTREE_IPV4][level - 1]);
860b75b4
HS		 2043#ifndef FABRICD
2044 for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
2045 fa)) {
2046 data = fa->data;
2047 isis_run_spf_with_protection(
2048 area, data->spftree[SPFTREE_IPV4][level - 1]);
2049 }
2050#endif /* ifndef FABRICD */
1ee746d9 2051 have_run = 1;
2052 }
2053 if (area->ipv6_circuits) {
c951ee6e
RW		 2054 isis_run_spf_with_protection(
2055 area, area->spftree[SPFTREE_IPV6][level - 1]);
860b75b4
HS		 2056#ifndef FABRICD
2057 for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
2058 fa)) {
2059 data = fa->data;
2060 isis_run_spf_with_protection(
2061 area, data->spftree[SPFTREE_IPV6][level - 1]);
2062 }
2063#endif /* ifndef FABRICD */
1ee746d9 2064 have_run = 1;
2065 }
2066 if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) {
c951ee6e
RW		 2067 isis_run_spf_with_protection(
2068 area, area->spftree[SPFTREE_DSTSRC][level - 1]);
1ee746d9 2069 have_run = 1;
2070 }
2071
2072 if (have_run)
2073 area->spf_run_count[level]++;
eb5d44eb 2074
3dace42d
CF		 2075 isis_area_verify_routes(area);
2076
2077 /* walk all circuits and reset any spf specific flags */
3dace42d
CF		 2078 for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit))
2079 UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
2080
b30e837b 2081 fabricd_run_spf(area);
eb5d44eb 2082}
2083
d62a17ae 2084static struct isis_spf_run *isis_run_spf_arg(struct isis_area *area, int level)
eb5d44eb 2085{
d62a17ae 2086 struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run));
2087
2088 run->area = area;
2089 run->level = level;
2090
2091 return run;
eb5d44eb 2092}
eb5d44eb 2093
8f15843b
DS		 2094void isis_spf_timer_free(void *run)
2095{
2096 XFREE(MTYPE_ISIS_SPF_RUN, run);
2097}
2098
d62db30d
CF		 2099int _isis_spf_schedule(struct isis_area *area, int level,
2100 const char *func, const char *file, int line)
eb5d44eb 2101{
fcb8ca9a
LS		 2102 struct isis_spftree *spftree;
2103 time_t now;
2104 long tree_diff, diff;
2105 int tree;
2106
2107 now = monotime(NULL);
2108 diff = 0;
2109 for (tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
2110 spftree = area->spftree[tree][level - 1];
2111 tree_diff = difftime(now - spftree->last_run_monotime, 0);
2112 if (tree_diff != now && (diff == 0 || tree_diff < diff))
2113 diff = tree_diff;
2114 }
d62a17ae 2115
52a7c25e
RW		 2116 if (CHECK_FLAG(im->options, F_ISIS_UNIT_TEST))
2117 return 0;
2118
d62a17ae 2119 assert(diff >= 0);
2120 assert(area->is_type & level);
2121
e740f9c1 2122 if (IS_DEBUG_SPF_EVENTS) {
d62a17ae 2123 zlog_debug(
fcb8ca9a 2124 "ISIS-SPF (%s) L%d SPF schedule called, lastrun %ld sec ago Caller: %s %s:%d",
d62db30d
CF		 2125 area->area_tag, level, diff, func, file, line);
2126 }
d62a17ae 2127
e16d030c 2128 EVENT_OFF(area->t_rlfa_rib_update);
d62a17ae 2129 if (area->spf_delay_ietf[level - 1]) {
2130 /* Need to call schedule function also if spf delay is running
2131 * to
2132 * restart holdoff timer - compare
2133 * draft-ietf-rtgwg-backoff-algo-04 */
2134 long delay =
2135 spf_backoff_schedule(area->spf_delay_ietf[level - 1]);
2136 if (area->spf_timer[level - 1])
2137 return ISIS_OK;
2138
907a2395
DS		 2139 event_add_timer_msec(master, isis_run_spf_cb,
2140 isis_run_spf_arg(area, level), delay,
2141 &area->spf_timer[level - 1]);
d62a17ae 2142 return ISIS_OK;
3f045a08 2143 }
d62a17ae 2144
2145 if (area->spf_timer[level - 1])
2146 return ISIS_OK;
2147
2148 /* wait configured min_spf_interval before doing the SPF */
3dca3c8c 2149 long timer;
690497fb
G		 2150 if (diff >= area->min_spf_interval[level - 1]
2151 || area->bfd_force_spf_refresh) {
2152 /*
2153 * Last run is more than min interval ago or BFD signalled a
2154 * 'down' message, schedule immediate run
2155 */
3dca3c8c 2156 timer = 0;
690497fb
G		 2157
2158 if (area->bfd_force_spf_refresh) {
2159 zlog_debug(
d240e5c8 2160 "ISIS-SPF (%s) L%d SPF scheduled immediately due to BFD 'down' message",
690497fb
G		 2161 area->area_tag, level);
2162 area->bfd_force_spf_refresh = false;
2163 }
3dca3c8c
CF		 2164 } else {
2165 timer = area->min_spf_interval[level - 1] - diff;
f390d2c7 2166 }
3f045a08 2167
907a2395
DS		 2168 event_add_timer(master, isis_run_spf_cb, isis_run_spf_arg(area, level),
2169 timer, &area->spf_timer[level - 1]);
d62a17ae 2170
e740f9c1 2171 if (IS_DEBUG_SPF_EVENTS)
d240e5c8 2172 zlog_debug("ISIS-SPF (%s) L%d SPF scheduled %ld sec from now",
013b29d7 2173 area->area_tag, level, timer);
d62a17ae 2174
2175 return ISIS_OK;
2176}
2177
eb919f07 2178static void isis_print_paths(struct vty *vty, struct isis_vertex_queue *queue,
d7c0a89a 2179 uint8_t *root_sysid)
d62a17ae 2180{
2181 struct listnode *node;
d62a17ae 2182 struct isis_vertex *vertex;
321c1bbb 2183 char buff[VID2STR_BUFFER];
d62a17ae 2184
2185 vty_out(vty,
2186 "Vertex Type Metric Next-Hop Interface Parent\n");
2187
eb919f07 2188 for (ALL_QUEUE_ELEMENTS_RO(queue, node, vertex)) {
6f6adeee
RW		 2189 if (VTYPE_IS(vertex->type)
2190 && memcmp(vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) {
d62a17ae 2191 vty_out(vty, "%-20s %-12s %-6s",
2192 print_sys_hostname(root_sysid), "", "");
af88c591
CF		 2193 vty_out(vty, "%-30s\n", "");
2194 continue;
d62a17ae 2195 }
2196
af88c591
CF		 2197 int rows = 0;
2198 struct listnode *anode = listhead(vertex->Adj_N);
2199 struct listnode *pnode = listhead(vertex->parents);
7b36d36e 2200 struct isis_vertex_adj *vadj;
af88c591
CF		 2201 struct isis_vertex *pvertex;
2202
2203 vty_out(vty, "%-20s %-12s %-6u ",
2204 vid2string(vertex, buff, sizeof(buff)),
2205 vtype2string(vertex->type), vertex->d_N);
1230a82d
A		 2206 for (unsigned int i = 0;
2207 i < MAX(vertex->Adj_N ? listcount(vertex->Adj_N) : 0,
2208 vertex->parents ? listcount(vertex->parents) : 0);
996c9314 2209 i++) {
af88c591 2210 if (anode) {
7b36d36e 2211 vadj = listgetdata(anode);
af88c591
CF		 2212 anode = anode->next;
2213 } else {
7b36d36e 2214 vadj = NULL;
af88c591
CF		 2215 }
2216
2217 if (pnode) {
2218 pvertex = listgetdata(pnode);
2219 pnode = pnode->next;
2220 } else {
2221 pvertex = NULL;
2222 }
2223
2224 if (rows) {
2225 vty_out(vty, "\n");
2226 vty_out(vty, "%-20s %-12s %-6s ", "", "", "");
2227 }
2228
7b36d36e
RW		 2229 if (vadj) {
2230 struct isis_spf_adj *sadj = vadj->sadj;
2231
af88c591 2232 vty_out(vty, "%-20s %-9s ",
7b36d36e
RW		 2233 print_sys_hostname(sadj->id),
2234 sadj->adj ? sadj->adj->circuit
2235 ->interface->name
2236 : "-");
af88c591
CF		 2237 }
2238
2239 if (pvertex) {
7b36d36e 2240 if (!vadj)
af88c591
CF		 2241 vty_out(vty, "%-20s %-9s ", "", "");
2242
d62a17ae 2243 vty_out(vty, "%s(%d)",
996c9314 2244 vid2string(pvertex, buff, sizeof(buff)),
d62a17ae 2245 pvertex->type);
d62a17ae 2246 }
d62a17ae 2247
af88c591
CF		 2248 ++rows;
2249 }
d62a17ae 2250 vty_out(vty, "\n");
2251 }
eb5d44eb 2252}
2253
52a7c25e 2254void isis_print_spftree(struct vty *vty, struct isis_spftree *spftree)
321c1bbb
CF		 2255{
2256 const char *tree_id_text = NULL;
2257
7b36d36e
RW		 2258 if (!spftree || !isis_vertex_queue_count(&spftree->paths))
2259 return;
2260
2261 switch (spftree->tree_id) {
321c1bbb
CF		 2262 case SPFTREE_IPV4:
2263 tree_id_text = "that speak IP";
2264 break;
2265 case SPFTREE_IPV6:
2266 tree_id_text = "that speak IPv6";
2267 break;
2268 case SPFTREE_DSTSRC:
2269 tree_id_text = "that support IPv6 dst-src routing";
2270 break;
2271 case SPFTREE_COUNT:
2272 assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type");
2273 return;
2274 }
2275
7b36d36e
RW		 2276 vty_out(vty, "IS-IS paths to level-%d routers %s\n", spftree->level,
2277 tree_id_text);
2278 isis_print_paths(vty, &spftree->paths, spftree->sysid);
321c1bbb
CF		 2279 vty_out(vty, "\n");
2280}
2281
eab88f36 2282static void show_isis_topology_common(struct vty *vty, int levels,
1610e215 2283 struct isis *isis, uint8_t algo)
eb5d44eb 2284{
1610e215
LS		 2285#ifndef FABRICD
2286 struct isis_flex_algo_data *fa_data;
2287 struct flex_algo *fa;
2288#endif /* ifndef FABRICD */
2289 struct isis_spftree *spftree;
d62a17ae 2290 struct listnode *node;
2291 struct isis_area *area;
2292
d62a17ae 2293 if (!isis->area_list || isis->area_list->count == 0)
eab88f36 2294 return;
d62a17ae 2295
2296 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
1610e215
LS		 2297 vty_out(vty,
2298 "Area %s:", area->area_tag ? area->area_tag : "null");
2299
2300#ifndef FABRICD
2301 /*
2302 * The shapes of the flex algo spftree 2-dimensional array
2303 * and the area spftree 2-dimensional array are not guaranteed
2304 * to be identical.
2305 */
2306 fa = NULL;
2307 if (flex_algo_id_valid(algo)) {
2308 fa = flex_algo_lookup(area->flex_algos, algo);
2309 if (!fa)
2310 continue;
2311 fa_data = (struct isis_flex_algo_data *)fa->data;
2312 } else
2313 fa_data = NULL;
2314
2315 if (algo != SR_ALGORITHM_SPF)
2316 vty_out(vty, " Algorithm %hhu\n", algo);
2317 else
2318#endif /* ifndef FABRICD */
2319 vty_out(vty, "\n");
d62a17ae 2320
2321 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
2322 if ((level & levels) == 0)
2323 continue;
2324
321c1bbb 2325 if (area->ip_circuits > 0) {
1610e215
LS		 2326#ifndef FABRICD
2327 if (fa_data)
2328 spftree = fa_data->spftree[SPFTREE_IPV4]
2329 [level - 1];
2330 else
2331#endif /* ifndef FABRICD */
2332 spftree = area->spftree[SPFTREE_IPV4]
2333 [level - 1];
2334
2335 isis_print_spftree(vty, spftree);
d62a17ae 2336 }
321c1bbb 2337 if (area->ipv6_circuits > 0) {
1610e215
LS		 2338#ifndef FABRICD
2339 if (fa_data)
2340 spftree = fa_data->spftree[SPFTREE_IPV6]
2341 [level - 1];
2342 else
2343#endif /* ifndef FABRICD */
2344 spftree = area->spftree[SPFTREE_IPV6]
2345 [level - 1];
2346 isis_print_spftree(vty, spftree);
321c1bbb
CF		 2347 }
2348 if (isis_area_ipv6_dstsrc_enabled(area)) {
1610e215
LS		 2349#ifndef FABRICD
2350 if (fa_data)
2351 spftree =
2352 fa_data->spftree[SPFTREE_DSTSRC]
2353 [level - 1];
2354 else
2355#endif /* ifndef FABRICD */
2356 spftree = area->spftree[SPFTREE_DSTSRC]
2357 [level - 1];
2358 isis_print_spftree(vty, spftree);
d62a17ae 2359 }
2360 }
f390d2c7 2361
b30e837b
CF		 2362 if (fabricd_spftree(area)) {
2363 vty_out(vty,
2364 "IS-IS paths to level-2 routers with hop-by-hop metric\n");
2365 isis_print_paths(vty, &fabricd_spftree(area)->paths, isis->sysid);
2366 vty_out(vty, "\n");
2367 }
2368
d62a17ae 2369 vty_out(vty, "\n");
f390d2c7 2370 }
eab88f36
K		 2371}
2372
2373DEFUN(show_isis_topology, show_isis_topology_cmd,
2374 "show " PROTO_NAME
2375 " [vrf <NAME|all>] topology"
2376#ifndef FABRICD
2377 " [<level-1|level-2>]"
1610e215
LS		 2378 " [algorithm (128-255)]"
2379#endif /* ifndef FABRICD */
eab88f36
K		 2380 ,
2381 SHOW_STR PROTO_HELP VRF_CMD_HELP_STR
2382 "All VRFs\n"
2383 "IS-IS paths to Intermediate Systems\n"
2384#ifndef FABRICD
2385 "Paths to all level-1 routers in the area\n"
2386 "Paths to all level-2 routers in the domain\n"
1610e215
LS		 2387 "Show Flex-algo routes\n"
2388 "Algorithm number\n"
2389#endif /* ifndef FABRICD */
eab88f36
K		 2390)
2391{
2392 int levels = ISIS_LEVELS;
36944791 2393 struct listnode *node;
eab88f36 2394 struct isis *isis = NULL;
eab88f36
K		 2395 const char *vrf_name = VRF_DEFAULT_NAME;
2396 bool all_vrf = false;
2397 int idx_vrf = 0;
1610e215
LS		 2398 uint8_t algorithm = SR_ALGORITHM_SPF;
2399#ifndef FABRICD
2400 int idx = 0;
eab88f36 2401
1610e215
LS		 2402 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
2403 if (argv_find(argv, argc, "level-1", &idx))
2404 levels = ISIS_LEVEL1;
2405 if (argv_find(argv, argc, "level-2", &idx))
2406 levels = ISIS_LEVEL2;
2407 if (argv_find(argv, argc, "algorithm", &idx))
2408 algorithm = (uint8_t)strtoul(argv[idx + 1]->arg, NULL, 10);
2409#endif /* ifndef FABRICD */
eab88f36
K		 2410
2411 if (!im) {
2412 vty_out(vty, "IS-IS Routing Process not enabled\n");
2413 return CMD_SUCCESS;
2414 }
2415 ISIS_FIND_VRF_ARGS(argv, argc, idx_vrf, vrf_name, all_vrf);
2416
2417 if (vrf_name) {
2418 if (all_vrf) {
36944791 2419 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
1610e215
LS		 2420 show_isis_topology_common(vty, levels, isis,
2421 algorithm);
36944791 2422 return CMD_SUCCESS;
eab88f36
K		 2423 }
2424 isis = isis_lookup_by_vrfname(vrf_name);
2425 if (isis != NULL)
1610e215 2426 show_isis_topology_common(vty, levels, isis, algorithm);
eab88f36 2427 }
3f045a08 2428
d62a17ae 2429 return CMD_SUCCESS;
f390d2c7 2430}
eb5d44eb 2431
df2f80a7
LS		 2432#ifndef FABRICD
2433static void show_isis_flex_algo_display_eag(struct vty *vty, char *buf,
2434 int indent,
2435 struct admin_group *admin_group)
2436{
2437 if (admin_group_zero(admin_group))
2438 vty_out(vty, "not-set\n");
2439 else {
2440 vty_out(vty, "%s\n",
2441 admin_group_string(buf, ADMIN_GROUP_PRINT_MAX_SIZE,
2442 indent, admin_group));
2443 admin_group_print(buf, indent, admin_group);
2444 if (buf[0] != '\0')
2445 vty_out(vty, " Bit positions: %s\n", buf);
2446 }
2447}
2448
2449static void show_isis_flex_algo_common(struct vty *vty, struct isis *isis,
2450 uint8_t algorithm)
2451{
2452 struct isis_router_cap_fad *router_fad;
2453 char buf[ADMIN_GROUP_PRINT_MAX_SIZE];
2454 struct admin_group *admin_group;
2455 struct isis_area *area;
2456 struct listnode *node;
2457 struct flex_algo *fa;
2458 int indent, algo;
2459 bool fad_identical, fad_supported;
2460
2461 if (!isis->area_list || isis->area_list->count == 0)
2462 return;
2463
2464 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
2465 /*
2466 * The shapes of the flex algo spftree 2-dimensional array
2467 * and the area spftree 2-dimensional array are not guaranteed
2468 * to be identical.
2469 */
2470
2471 for (algo = 0; algo < SR_ALGORITHM_COUNT; algo++) {
2472 if (algorithm != SR_ALGORITHM_UNSET &&
2473 algorithm != algo)
2474 continue;
2475
2476 fa = flex_algo_lookup(area->flex_algos, algo);
2477 if (!fa)
2478 continue;
2479
2480 vty_out(vty, "Area %s:",
2481 area->area_tag ? area->area_tag : "null");
2482
2483 vty_out(vty, " Algorithm %d\n", algo);
2484 vty_out(vty, "\n");
2485
2486 vty_out(vty, " Enabled Data-Planes:");
2487 if (fa->dataplanes == 0) {
2488 vty_out(vty, " None\n\n");
2489 continue;
2490 }
2491 if (CHECK_FLAG(fa->dataplanes, FLEX_ALGO_SR_MPLS))
2492 vty_out(vty, " SR-MPLS");
2493 if (CHECK_FLAG(fa->dataplanes, FLEX_ALGO_SRV6))
2494 vty_out(vty, " SRv6");
2495 if (CHECK_FLAG(fa->dataplanes, FLEX_ALGO_IP))
2496 vty_out(vty, " IP");
2497 vty_out(vty, "\n\n");
2498
2499
2500 router_fad = isis_flex_algo_elected(algo, area);
2501 vty_out(vty,
2502 " Elected and running Flexible-Algorithm Definition:\n");
2503 if (router_fad)
2504 vty_out(vty, " Source: %pSY\n",
2505 router_fad->sysid);
2506 else
2507 vty_out(vty, " Source: Not found\n");
2508
2509 if (!router_fad) {
2510 vty_out(vty, "\n");
2511 continue;
2512 }
2513
2514 fad_identical =
2515 flex_algo_definition_cmp(fa, &router_fad->fad);
2516 fad_supported =
2517 isis_flex_algo_supported(&router_fad->fad);
2518 vty_out(vty, " Priority: %d\n",
2519 router_fad->fad.priority);
2520 vty_out(vty, " Equal to local: %s\n",
2521 fad_identical ? "yes" : "no");
2522 vty_out(vty, " Local state: %s\n",
2523 fad_supported
2524 ? "enabled"
2525 : "disabled (unsupported definition)");
2526 vty_out(vty, " Calculation type: ");
2527 if (router_fad->fad.calc_type == 0)
2528 vty_out(vty, "spf\n");
2529 else
2530 vty_out(vty, "%d\n", router_fad->fad.calc_type);
2531 vty_out(vty, " Metric type: %s\n",
2532 flex_algo_metric_type_print(
2533 buf, sizeof(buf),
2534 router_fad->fad.metric_type));
2535 vty_out(vty, " Prefix-metric: %s\n",
2536 CHECK_FLAG(router_fad->fad.flags, FAD_FLAG_M)
2537 ? "enabled"
2538 : "disabled");
2539 if (router_fad->fad.flags != 0 &&
2540 router_fad->fad.flags != FAD_FLAG_M)
2541 vty_out(vty, " Flags: 0x%x\n",
2542 router_fad->fad.flags);
2543 vty_out(vty, " Exclude SRLG: %s\n",
2544 router_fad->fad.exclude_srlg ? "enabled"
2545 : "disabled");
2546
2547 admin_group = &router_fad->fad.admin_group_exclude_any;
2548 indent = vty_out(vty, " Exclude-any admin-group: ");
2549 show_isis_flex_algo_display_eag(vty, buf, indent,
2550 admin_group);
2551
2552 admin_group = &router_fad->fad.admin_group_include_all;
2553 indent = vty_out(vty, " Include-all admin-group: ");
2554 show_isis_flex_algo_display_eag(vty, buf, indent,
2555 admin_group);
2556
2557 admin_group = &router_fad->fad.admin_group_include_any;
2558 indent = vty_out(vty, " Include-any admin-group: ");
2559 show_isis_flex_algo_display_eag(vty, buf, indent,
2560 admin_group);
2561
2562 if (router_fad->fad.unsupported_subtlv)
2563 vty_out(vty,
2564 " Unsupported sub-TLV: Present (see logs)");
2565
2566 vty_out(vty, "\n");
2567 }
2568 }
2569}
2570
2571DEFUN(show_isis_flex_algo, show_isis_flex_algo_cmd,
2572 "show " PROTO_NAME
2573 " [vrf <NAME|all>] flex-algo"
2574 " [(128-255)]",
2575 SHOW_STR PROTO_HELP VRF_CMD_HELP_STR
2576 "All VRFs\n"
2577 "IS-IS Flex-algo information\n"
2578 "Algorithm number\n")
2579{
2580 struct isis *isis;
2581 struct listnode *node;
2582 const char *vrf_name = VRF_DEFAULT_NAME;
2583 bool all_vrf = false;
2584 int idx = 0;
2585 int idx_vrf = 0;
2586 uint8_t flex_algo;
2587
2588 if (!im) {
2589 vty_out(vty, "IS-IS Routing Process not enabled\n");
2590 return CMD_SUCCESS;
2591 }
2592
2593 if (argv_find(argv, argc, "flex-algo", &idx) && (idx + 1) < argc)
2594 flex_algo = (uint8_t)strtoul(argv[idx + 1]->arg, NULL, 10);
2595 else
2596 flex_algo = SR_ALGORITHM_UNSET;
2597
2598 ISIS_FIND_VRF_ARGS(argv, argc, idx_vrf, vrf_name, all_vrf);
2599
2600 if (vrf_name) {
2601 if (all_vrf) {
2602 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
2603 show_isis_flex_algo_common(vty, isis,
2604 flex_algo);
2605 return CMD_SUCCESS;
2606 }
2607 isis = isis_lookup_by_vrfname(vrf_name);
2608 if (isis != NULL)
2609 show_isis_flex_algo_common(vty, isis, flex_algo);
2610 }
2611
2612 return CMD_SUCCESS;
2613}
2614#endif /* ifndef FABRICD */
2615
d47d6089
RW		 2616static void isis_print_route(struct ttable *tt, const struct prefix *prefix,
2617 struct isis_route_info *rinfo, bool prefix_sid,
42ac4485 2618 bool no_adjacencies, bool json)
d47d6089
RW		 2619{
2620 struct isis_nexthop *nexthop;
2621 struct listnode *node;
2622 bool first = true;
2623 char buf_prefix[BUFSIZ];
2624
2625 (void)prefix2str(prefix, buf_prefix, sizeof(buf_prefix));
e39af372
EK		 2626 for (int alg = 0; alg < SR_ALGORITHM_COUNT; alg++) {
2627 for (ALL_LIST_ELEMENTS_RO(rinfo->sr_algo[alg].nexthops, node,
2628 nexthop)) {
a0f45d1b
LS		 2629 struct interface *ifp;
2630 char buf_iface[BUFSIZ];
2631 char buf_nhop[BUFSIZ];
2632
2633 if (!no_adjacencies) {
e39af372
EK		 2634 inet_ntop(nexthop->family, &nexthop->ip,
2635 buf_nhop, sizeof(buf_nhop));
2636 ifp = if_lookup_by_index(nexthop->ifindex,
2637 VRF_DEFAULT);
a0f45d1b
LS		 2638 if (ifp)
2639 strlcpy(buf_iface, ifp->name,
2640 sizeof(buf_iface));
2641 else
2642 snprintf(buf_iface, sizeof(buf_iface),
e39af372
EK		 2643 "ifindex %u",
2644 nexthop->ifindex);
d47d6089 2645 } else {
e39af372
EK		 2646 strlcpy(buf_nhop,
2647 print_sys_hostname(nexthop->sysid),
a0f45d1b
LS		 2648 sizeof(buf_nhop));
2649 strlcpy(buf_iface, "-", sizeof(buf_iface));
d47d6089
RW		 2650 }
2651
a0f45d1b
LS		 2652 if (prefix_sid) {
2653 char buf_sid[BUFSIZ] = {};
2654 char buf_lblop[BUFSIZ] = {};
2655
e39af372 2656 if (rinfo->sr_algo[alg].present) {
a0f45d1b 2657 snprintf(buf_sid, sizeof(buf_sid), "%u",
e39af372
EK		 2658 rinfo->sr_algo[alg].sid.value);
2659 sr_op2str(buf_lblop, sizeof(buf_lblop),
2660 rinfo->sr_algo[alg].label,
2661 nexthop->sr.label);
2662 } else if (alg == SR_ALGORITHM_SPF) {
a0f45d1b 2663 strlcpy(buf_sid, "-", sizeof(buf_sid));
e39af372
EK		 2664 strlcpy(buf_lblop, "-",
2665 sizeof(buf_lblop));
2666 } else {
2667 continue;
d47d6089 2668 }
a0f45d1b 2669
42ac4485 2670 if (first || json) {
e39af372
EK		 2671 ttable_add_row(tt,
2672 "%s|%u|%s|%s|%s|%s|%d",
2673 buf_prefix, rinfo->cost,
2674 buf_iface, buf_nhop,
2675 buf_sid, buf_lblop, alg);
a0f45d1b
LS		 2676 first = false;
2677 } else
e39af372
EK		 2678 ttable_add_row(tt, "||%s|%s|%s|%s|%d",
2679 buf_iface, buf_nhop,
2680 buf_sid, buf_lblop, alg);
a0f45d1b
LS		 2681 } else {
2682 char buf_labels[BUFSIZ] = {};
2683
2684 if (nexthop->label_stack) {
2685 for (int i = 0;
e39af372
EK		 2686 i <
2687 nexthop->label_stack->num_labels;
2688 i++) {
a0f45d1b
LS		 2689 char buf_label[BUFSIZ];
2690
e39af372
EK		 2691 label2str(nexthop->label_stack
2692 ->label[i],
2693 0, buf_label,
2694 sizeof(buf_label));
a0f45d1b
LS		 2695 if (i != 0)
2696 strlcat(buf_labels, "/",
2697 sizeof(buf_labels));
2698 strlcat(buf_labels, buf_label,
2699 sizeof(buf_labels));
2700 }
2701 } else if (nexthop->sr.present)
e39af372
EK		 2702 label2str(nexthop->sr.label, 0,
2703 buf_labels,
a0f45d1b
LS		 2704 sizeof(buf_labels));
2705 else
e39af372
EK		 2706 strlcpy(buf_labels, "-",
2707 sizeof(buf_labels));
a0f45d1b 2708
42ac4485 2709 if (first || json) {
e39af372
EK		 2710 ttable_add_row(tt, "%s|%u|%s|%s|%s",
2711 buf_prefix, rinfo->cost,
2712 buf_iface, buf_nhop,
2713 buf_labels);
a0f45d1b
LS		 2714 first = false;
2715 } else
e39af372
EK		 2716 ttable_add_row(tt, "||%s|%s|%s",
2717 buf_iface, buf_nhop,
2718 buf_labels);
a0f45d1b 2719 }
d47d6089 2720 }
e39af372
EK		 2721 }
2722
d47d6089
RW		 2723 if (list_isempty(rinfo->nexthops)) {
2724 if (prefix_sid) {
2725 char buf_sid[BUFSIZ] = {};
2726 char buf_lblop[BUFSIZ] = {};
2727
7153c3ca 2728 if (rinfo->sr_algo[SR_ALGORITHM_SPF].present) {
d47d6089 2729 snprintf(buf_sid, sizeof(buf_sid), "%u",
7153c3ca
HS		 2730 rinfo->sr_algo[SR_ALGORITHM_SPF]
2731 .sid.value);
2732 sr_op2str(
2733 buf_lblop, sizeof(buf_lblop),
2734 rinfo->sr_algo[SR_ALGORITHM_SPF].label,
2735 MPLS_LABEL_IMPLICIT_NULL);
d47d6089
RW		 2736 } else {
2737 strlcpy(buf_sid, "-", sizeof(buf_sid));
2738 strlcpy(buf_lblop, "-", sizeof(buf_lblop));
2739 }
2740
2741 ttable_add_row(tt, "%s|%u|%s|%s|%s|%s", buf_prefix,
2742 rinfo->cost, "-", "-", buf_sid,
2743 buf_lblop);
2744 } else
2745 ttable_add_row(tt, "%s|%u|%s|%s|%s", buf_prefix,
2746 rinfo->cost, "-", "-", "-");
2747 }
2748}
2749
c951ee6e 2750void isis_print_routes(struct vty *vty, struct isis_spftree *spftree,
42ac4485 2751 struct json_object **json, bool prefix_sid, bool backup)
675269d4 2752{
c951ee6e 2753 struct route_table *route_table;
675269d4
RW		 2754 struct ttable *tt;
2755 struct route_node *rn;
d47d6089 2756 bool no_adjacencies = false;
675269d4
RW		 2757 const char *tree_id_text = NULL;
2758
2759 if (!spftree)
2760 return;
2761
2762 switch (spftree->tree_id) {
2763 case SPFTREE_IPV4:
2764 tree_id_text = "IPv4";
2765 break;
2766 case SPFTREE_IPV6:
2767 tree_id_text = "IPv6";
2768 break;
2769 case SPFTREE_DSTSRC:
2770 tree_id_text = "IPv6 (dst-src routing)";
2771 break;
2772 case SPFTREE_COUNT:
2773 assert(!"isis_print_routes shouldn't be called with SPFTREE_COUNT as type");
2774 return;
2775 }
2776
42ac4485
EK		 2777 if (json == NULL)
2778 vty_out(vty, "IS-IS %s %s routing table:\n\n",
2779 circuit_t2string(spftree->level), tree_id_text);
675269d4
RW		 2780
2781 /* Prepare table. */
2782 tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
d47d6089 2783 if (prefix_sid)
e39af372
EK		 2784 ttable_add_row(
2785 tt,
2786 "Prefix|Metric|Interface|Nexthop|SID|Label Op.|Algo");
d47d6089
RW		 2787 else
2788 ttable_add_row(tt, "Prefix|Metric|Interface|Nexthop|Label(s)");
675269d4
RW		 2789 tt->style.cell.rpad = 2;
2790 tt->style.corner = '+';
2791 ttable_restyle(tt);
2792 ttable_rowseps(tt, 0, BOTTOM, true, '-');
2793
d47d6089
RW		 2794 if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES))
2795 no_adjacencies = true;
2796
c951ee6e
RW		 2797 route_table =
2798 (backup) ? spftree->route_table_backup : spftree->route_table;
2799 for (rn = route_top(route_table); rn; rn = route_next(rn)) {
675269d4 2800 struct isis_route_info *rinfo;
675269d4
RW		 2801
2802 rinfo = rn->info;
2803 if (!rinfo)
2804 continue;
2805
42ac4485
EK		 2806 isis_print_route(tt, &rn->p, rinfo, prefix_sid, no_adjacencies,
2807 json != NULL);
675269d4
RW		 2808 }
2809
2810 /* Dump the generated table. */
42ac4485 2811 if (json == NULL && tt->nrows > 1) {
675269d4
RW		 2812 char *table;
2813
2814 table = ttable_dump(tt, "\n");
2815 vty_out(vty, "%s\n", table);
2816 XFREE(MTYPE_TMP, table);
42ac4485
EK		 2817 } else if (json) {
2818 *json = ttable_json(tt, prefix_sid ? "sdssdsdd" : "sdsss");
675269d4
RW		 2819 }
2820 ttable_del(tt);
2821}
2822
2823static void show_isis_route_common(struct vty *vty, int levels,
d47d6089 2824 struct isis *isis, bool prefix_sid,
0833c251
LS		 2825 bool backup, uint8_t algo,
2826 json_object **json)
675269d4 2827{
42ac4485 2828 json_object *json_level = NULL, *jstr = NULL, *json_val;
0833c251
LS		 2829#ifndef FABRICD
2830 struct isis_flex_algo_data *fa_data;
2831 struct flex_algo *fa;
2832#endif /* ifndef FABRICD */
2833 struct isis_spftree *spftree;
675269d4
RW		 2834 struct listnode *node;
2835 struct isis_area *area;
42ac4485 2836 char key[8];
675269d4
RW		 2837
2838 if (!isis->area_list || isis->area_list->count == 0)
2839 return;
2840
42ac4485
EK		 2841 if (json)
2842 *json = json_object_new_object();
2843
675269d4 2844 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
0833c251
LS		 2845#ifndef FABRICD
2846 /*
2847 * The shapes of the flex algo spftree 2-dimensional array
2848 * and the area spftree 2-dimensional array are not guaranteed
2849 * to be identical.
2850 */
2851 fa = NULL;
2852 if (flex_algo_id_valid(algo)) {
2853 fa = flex_algo_lookup(area->flex_algos, algo);
2854 if (!fa)
2855 continue;
2856 fa_data = (struct isis_flex_algo_data *)fa->data;
2857 } else {
2858 fa_data = NULL;
2859 }
2860#endif /* ifndef FABRICD */
2861
42ac4485
EK		 2862 if (json) {
2863 jstr = json_object_new_string(
2864 area->area_tag ? area->area_tag : "null");
2865 json_object_object_add(*json, "area", jstr);
2866 } else {
0833c251 2867 vty_out(vty, "Area %s:",
42ac4485 2868 area->area_tag ? area->area_tag : "null");
0833c251
LS		 2869#ifndef FABRICD
2870 if (algo != SR_ALGORITHM_SPF)
2871 vty_out(vty, " Algorithm %hhu\n", algo);
2872 else
2873#endif /* ifndef FABRICD */
2874 vty_out(vty, "\n");
42ac4485 2875 }
675269d4
RW		 2876
2877 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
2878 if ((level & levels) == 0)
2879 continue;
2880
42ac4485
EK		 2881 if (json) {
2882 json_level = json_object_new_object();
2883 jstr = json_object_new_string(
2884 area->area_tag ? area->area_tag
2885 : "null");
2886 json_object_object_add(json_level, "area",
2887 jstr);
2888 }
2889
675269d4 2890 if (area->ip_circuits > 0) {
42ac4485 2891 json_val = NULL;
0833c251
LS		 2892#ifndef FABRICD
2893 if (fa_data)
2894 spftree = fa_data->spftree[SPFTREE_IPV4]
2895 [level - 1];
2896 else
2897#endif /* ifndef FABRICD */
2898 spftree = area->spftree[SPFTREE_IPV4]
2899 [level - 1];
2900
3ae589b8
LS		 2901 if (!json)
2902 isis_print_spftree(vty, spftree);
0833c251
LS		 2903
2904 isis_print_routes(vty, spftree,
2905 json ? &json_val : NULL,
2906 prefix_sid, backup);
42ac4485
EK		 2907 if (json && json_val) {
2908 json_object_object_add(
2909 json_level, "ipv4", json_val);
2910 }
675269d4
RW		 2911 }
2912 if (area->ipv6_circuits > 0) {
42ac4485 2913 json_val = NULL;
0833c251
LS		 2914#ifndef FABRICD
2915 if (fa_data)
2916 spftree = fa_data->spftree[SPFTREE_IPV6]
2917 [level - 1];
2918 else
2919#endif /* ifndef FABRICD */
2920 spftree = area->spftree[SPFTREE_IPV6]
2921 [level - 1];
2922
3ae589b8
LS		 2923 if (!json)
2924 isis_print_spftree(vty, spftree);
0833c251
LS		 2925
2926 isis_print_routes(vty, spftree,
2927 json ? &json_val : NULL,
2928 prefix_sid, backup);
42ac4485
EK		 2929 if (json && json_val) {
2930 json_object_object_add(
2931 json_level, "ipv6", json_val);
2932 }
675269d4
RW		 2933 }
2934 if (isis_area_ipv6_dstsrc_enabled(area)) {
42ac4485 2935 json_val = NULL;
0833c251
LS		 2936#ifndef FABRICD
2937 if (fa_data)
2938 spftree =
2939 fa_data->spftree[SPFTREE_DSTSRC]
2940 [level - 1];
2941 else
2942#endif /* ifndef FABRICD */
2943 spftree = area->spftree[SPFTREE_DSTSRC]
2944 [level - 1];
2945
3ae589b8
LS		 2946 if (!json)
2947 isis_print_spftree(vty, spftree);
0833c251 2948 isis_print_routes(vty, spftree,
42ac4485 2949 json ? &json_val : NULL,
d47d6089 2950 prefix_sid, backup);
42ac4485
EK		 2951 if (json && json_val) {
2952 json_object_object_add(json_level,
2953 "ipv6-dstsrc",
2954 json_val);
2955 }
2956 }
2957 if (json) {
2958 snprintf(key, sizeof(key), "level-%d", level);
2959 json_object_object_add(*json, key, json_level);
675269d4
RW		 2960 }
2961 }
2962 }
2963}
2964
2965DEFUN(show_isis_route, show_isis_route_cmd,
2966 "show " PROTO_NAME
2967 " [vrf <NAME|all>] route"
2968#ifndef FABRICD
2969 " [<level-1|level-2>]"
0833c251 2970#endif /* ifndef FABRICD */
42ac4485 2971 " [<prefix-sid|backup>]"
0833c251
LS		 2972#ifndef FABRICD
2973 " [algorithm (128-255)]"
2974#endif /* ifndef FABRICD */
42ac4485 2975 " [json$uj]",
675269d4
RW		 2976 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
2977 "IS-IS routing table\n"
2978#ifndef FABRICD
2979 "level-1 routes\n"
2980 "level-2 routes\n"
0833c251 2981#endif /* ifndef FABRICD */
d47d6089 2982 "Show Prefix-SID information\n"
0833c251
LS		 2983 "Show backup routes\n"
2984#ifndef FABRICD
2985 "Show Flex-algo routes\n"
2986 "Algorithm number\n"
2987#endif /* ifndef FABRICD */
2988 JSON_STR)
675269d4
RW		 2989{
2990 int levels;
2991 struct isis *isis;
2992 struct listnode *node;
2993 const char *vrf_name = VRF_DEFAULT_NAME;
2994 bool all_vrf = false;
d47d6089 2995 bool prefix_sid = false;
c951ee6e 2996 bool backup = false;
42ac4485 2997 bool uj = use_json(argc, argv);
675269d4 2998 int idx = 0;
42ac4485 2999 json_object *json = NULL, *json_vrf = NULL;
0833c251 3000 uint8_t algorithm = SR_ALGORITHM_SPF;
675269d4
RW		 3001
3002 if (argv_find(argv, argc, "level-1", &idx))
3003 levels = ISIS_LEVEL1;
3004 else if (argv_find(argv, argc, "level-2", &idx))
3005 levels = ISIS_LEVEL2;
3006 else
3007 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
3008
3009 if (!im) {
3010 vty_out(vty, "IS-IS Routing Process not enabled\n");
3011 return CMD_SUCCESS;
3012 }
3013 ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf);
3014
d47d6089
RW		 3015 if (argv_find(argv, argc, "prefix-sid", &idx))
3016 prefix_sid = true;
c951ee6e
RW		 3017 if (argv_find(argv, argc, "backup", &idx))
3018 backup = true;
3019
0833c251
LS		 3020#ifndef FABRICD
3021 if (argv_find(argv, argc, "algorithm", &idx))
3022 algorithm = (uint8_t)strtoul(argv[idx + 1]->arg, NULL, 10);
3023#endif /* ifndef FABRICD */
3024
42ac4485
EK		 3025 if (uj)
3026 json = json_object_new_array();
3027
675269d4
RW		 3028 if (vrf_name) {
3029 if (all_vrf) {
42ac4485 3030 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis)) {
0833c251
LS		 3031 show_isis_route_common(
3032 vty, levels, isis, prefix_sid, backup,
3033 algorithm, uj ? &json_vrf : NULL);
42ac4485
EK		 3034 if (uj) {
3035 json_object_object_add(
3036 json_vrf, "vrf_id",
3037 json_object_new_int(
3038 isis->vrf_id));
3039 json_object_array_add(json, json_vrf);
3040 }
3041 }
3042 goto out;
675269d4
RW		 3043 }
3044 isis = isis_lookup_by_vrfname(vrf_name);
42ac4485 3045 if (isis != NULL) {
d47d6089 3046 show_isis_route_common(vty, levels, isis, prefix_sid,
0833c251
LS		 3047 backup, algorithm,
3048 uj ? &json_vrf : NULL);
42ac4485
EK		 3049 if (uj) {
3050 json_object_object_add(
3051 json_vrf, "vrf_id",
3052 json_object_new_int(isis->vrf_id));
3053 json_object_array_add(json, json_vrf);
3054 }
3055 }
3056 }
3057
3058out:
3059 if (uj) {
3060 vty_out(vty, "%s\n",
3061 json_object_to_json_string_ext(
3062 json, JSON_C_TO_STRING_PRETTY));
3063 json_object_free(json);
675269d4
RW		 3064 }
3065
3066 return CMD_SUCCESS;
3067}
3068
fc156c28
RW		 3069static void isis_print_frr_summary_line(struct ttable *tt,
3070 const char *protection,
3071 uint32_t counters[SPF_PREFIX_PRIO_MAX])
3072{
3073 uint32_t critical, high, medium, low, total;
3074
3075 critical = counters[SPF_PREFIX_PRIO_CRITICAL];
3076 high = counters[SPF_PREFIX_PRIO_HIGH];
3077 medium = counters[SPF_PREFIX_PRIO_MEDIUM];
3078 low = counters[SPF_PREFIX_PRIO_LOW];
3079 total = critical + high + medium + low;
3080
3081 ttable_add_row(tt, "%s|%u|%u|%u|%u|%u", protection, critical, high,
3082 medium, low, total);
3083}
3084
3085static void
3086isis_print_frr_summary_line_coverage(struct ttable *tt, const char *protection,
3087 double counters[SPF_PREFIX_PRIO_MAX],
3088 double total)
3089{
3090 double critical, high, medium, low;
3091
3092 critical = counters[SPF_PREFIX_PRIO_CRITICAL] * 100;
3093 high = counters[SPF_PREFIX_PRIO_HIGH] * 100;
3094 medium = counters[SPF_PREFIX_PRIO_MEDIUM] * 100;
3095 low = counters[SPF_PREFIX_PRIO_LOW] * 100;
3096 total *= 100;
3097
3098 ttable_add_row(tt, "%s|%.2f%%|%.2f%%|%.2f%%|%.2f%%|%.2f%%", protection,
3099 critical, high, medium, low, total);
3100}
3101
3102static void isis_print_frr_summary(struct vty *vty,
3103 struct isis_spftree *spftree)
3104{
3105 struct ttable *tt;
3106 char *table;
3107 const char *tree_id_text = NULL;
3108 uint32_t protectd[SPF_PREFIX_PRIO_MAX] = {0};
3109 uint32_t unprotected[SPF_PREFIX_PRIO_MAX] = {0};
3110 double coverage[SPF_PREFIX_PRIO_MAX] = {0};
3111 uint32_t protected_total = 0, grand_total = 0;
3112 double coverage_total;
3113
3114 if (!spftree)
3115 return;
3116
3117 switch (spftree->tree_id) {
3118 case SPFTREE_IPV4:
3119 tree_id_text = "IPv4";
3120 break;
3121 case SPFTREE_IPV6:
3122 tree_id_text = "IPv6";
3123 break;
3124 case SPFTREE_DSTSRC:
3125 tree_id_text = "IPv6 (dst-src routing)";
3126 break;
3127 case SPFTREE_COUNT:
3128 assert(!"isis_print_frr_summary shouldn't be called with SPFTREE_COUNT as type");
3129 return;
3130 }
3131
3132 vty_out(vty, " IS-IS %s %s Fast ReRoute summary:\n\n",
3133 circuit_t2string(spftree->level), tree_id_text);
3134
3135 /* Prepare table. */
3136 tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
3137 ttable_add_row(
3138 tt,
3139 "Protection \\ Priority|Critical|High |Medium |Low |Total");
3140 tt->style.cell.rpad = 2;
3141 tt->style.corner = '+';
3142 ttable_restyle(tt);
3143 ttable_rowseps(tt, 0, BOTTOM, true, '-');
3144
3145 /* Compute unprotected and coverage totals. */
3146 for (int priority = SPF_PREFIX_PRIO_CRITICAL;
3147 priority < SPF_PREFIX_PRIO_MAX; priority++) {
3148 uint32_t *lfa = spftree->lfa.protection_counters.lfa;
3149 uint32_t *rlfa = spftree->lfa.protection_counters.rlfa;
3150 uint32_t *tilfa = spftree->lfa.protection_counters.tilfa;
3151 uint32_t *ecmp = spftree->lfa.protection_counters.ecmp;
3152 uint32_t *total = spftree->lfa.protection_counters.total;
3153
3154 protectd[priority] = lfa[priority] + rlfa[priority]
3155 + tilfa[priority] + ecmp[priority];
3156 /* Safeguard to protect against possible inconsistencies. */
3157 if (protectd[priority] > total[priority])
3158 protectd[priority] = total[priority];
3159 unprotected[priority] = total[priority] - protectd[priority];
3160 protected_total += protectd[priority];
3161 grand_total += total[priority];
3162
3163 if (!total[priority])
3164 coverage[priority] = 0;
3165 else
3166 coverage[priority] =
3167 protectd[priority] / (double)total[priority];
3168 }
3169
3170 if (!grand_total)
3171 coverage_total = 0;
3172 else
3173 coverage_total = protected_total / (double)grand_total;
3174
3175 /* Add rows. */
3176 isis_print_frr_summary_line(tt, "Classic LFA",
3177 spftree->lfa.protection_counters.lfa);
3178 isis_print_frr_summary_line(tt, "Remote LFA",
3179 spftree->lfa.protection_counters.rlfa);
3180 isis_print_frr_summary_line(tt, "Topology Independent LFA",
3181 spftree->lfa.protection_counters.tilfa);
3182 isis_print_frr_summary_line(tt, "ECMP",
3183 spftree->lfa.protection_counters.ecmp);
3184 isis_print_frr_summary_line(tt, "Unprotected", unprotected);
3185 isis_print_frr_summary_line_coverage(tt, "Protection coverage",
3186 coverage, coverage_total);
3187
3188 /* Dump the generated table. */
3189 table = ttable_dump(tt, "\n");
3190 vty_out(vty, "%s\n", table);
3191 XFREE(MTYPE_TMP, table);
3192 ttable_del(tt);
3193}
3194
3195static void show_isis_frr_summary_common(struct vty *vty, int levels,
3196 struct isis *isis)
3197{
3198 struct listnode *node;
3199 struct isis_area *area;
3200
3201 if (!isis->area_list || isis->area_list->count == 0)
3202 return;
3203
3204 for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) {
3205 vty_out(vty, "Area %s:\n",
3206 area->area_tag ? area->area_tag : "null");
3207
3208 for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) {
3209 if ((level & levels) == 0)
3210 continue;
3211
3212 if (area->ip_circuits > 0) {
3213 isis_print_frr_summary(
3214 vty,
3215 area->spftree[SPFTREE_IPV4][level - 1]);
3216 }
3217 if (area->ipv6_circuits > 0) {
3218 isis_print_frr_summary(
3219 vty,
3220 area->spftree[SPFTREE_IPV6][level - 1]);
3221 }
3222 if (isis_area_ipv6_dstsrc_enabled(area)) {
3223 isis_print_frr_summary(
3224 vty, area->spftree[SPFTREE_DSTSRC]
3225 [level - 1]);
3226 }
3227 }
3228 }
3229}
3230
3231DEFUN(show_isis_frr_summary, show_isis_frr_summary_cmd,
3232 "show " PROTO_NAME
3233 " [vrf <NAME|all>] fast-reroute summary"
3234#ifndef FABRICD
3235 " [<level-1|level-2>]"
3236#endif
3237 ,
3238 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
3239 "IS-IS FRR information\n"
3240 "FRR summary\n"
3241#ifndef FABRICD
3242 "level-1 routes\n"
3243 "level-2 routes\n"
3244#endif
3245)
3246{
3247 int levels;
3248 struct isis *isis;
3249 struct listnode *node;
3250 const char *vrf_name = VRF_DEFAULT_NAME;
3251 bool all_vrf = false;
3252 int idx = 0;
3253
3254 if (argv_find(argv, argc, "level-1", &idx))
3255 levels = ISIS_LEVEL1;
3256 else if (argv_find(argv, argc, "level-2", &idx))
3257 levels = ISIS_LEVEL2;
3258 else
3259 levels = ISIS_LEVEL1 | ISIS_LEVEL2;
3260
3261 if (!im) {
3262 vty_out(vty, "IS-IS Routing Process not enabled\n");
3263 return CMD_SUCCESS;
3264 }
3265 ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf);
3266
3267 if (vrf_name) {
3268 if (all_vrf) {
3269 for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis))
3270 show_isis_frr_summary_common(vty, levels, isis);
3271 return CMD_SUCCESS;
3272 }
3273 isis = isis_lookup_by_vrfname(vrf_name);
3274 if (isis != NULL)
3275 show_isis_frr_summary_common(vty, levels, isis);
3276 }
3277
3278 return CMD_SUCCESS;
3279}
3280
56ea2b21 3281void isis_spf_init(void)
eb5d44eb 3282{
df2f80a7
LS		 3283#ifndef FABRICD
3284 install_element(VIEW_NODE, &show_isis_flex_algo_cmd);
3285#endif /* ifndef FABRICD */
d62a17ae 3286 install_element(VIEW_NODE, &show_isis_topology_cmd);
675269d4 3287 install_element(VIEW_NODE, &show_isis_route_cmd);
fc156c28 3288 install_element(VIEW_NODE, &show_isis_frr_summary_cmd);
56ea2b21
RW		 3289
3290 /* Register hook(s). */
3291 hook_register(isis_adj_state_change_hook, spf_adj_state_change);
eb5d44eb 3292}
02cd317e
CF		 3293
3294void isis_spf_print(struct isis_spftree *spftree, struct vty *vty)
3295{
5d543b3f
RZ		 3296 uint64_t last_run_duration = spftree->last_run_duration;
3297
02cd317e
CF		 3298 vty_out(vty, " last run elapsed : ");
3299 vty_out_timestr(vty, spftree->last_run_timestamp);
3300 vty_out(vty, "\n");
3301
5d543b3f
RZ		 3302 vty_out(vty, " last run duration : %" PRIu64 " usec\n",
3303 last_run_duration);
02cd317e 3304
996c9314 3305 vty_out(vty, " run count : %u\n", spftree->runcount);
02cd317e 3306}
471bb5da
JG		 3307void isis_spf_print_json(struct isis_spftree *spftree, struct json_object *json)
3308{
3309 char uptime[MONOTIME_STRLEN];
3310 time_t cur;
3311 cur = time(NULL);
3312 cur -= spftree->last_run_timestamp;
3313 frrtime_to_interval(cur, uptime, sizeof(uptime));
3314 json_object_string_add(json, "last-run-elapsed", uptime);
3315 json_object_int_add(json, "last-run-duration-usec",
3316 spftree->last_run_duration);
3317 json_object_int_add(json, "last-run-count", spftree->runcount);
3318}
FRRouting mirror