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