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