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