2 * IS-IS Rout(e)ing protocol - isis_spf.c
5 * Copyright (C) 2001,2002 Sampo Saaristo
6 * Tampere University of Technology
7 * Institute of Communications Engineering
8 * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org>
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)
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
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
32 #include "termtable.h"
39 #include "spf_backoff.h"
40 #include "srcdest_table.h"
43 #include "isis_errors.h"
44 #include "isis_constants.h"
45 #include "isis_common.h"
46 #include "isis_flags.h"
48 #include "isis_misc.h"
49 #include "isis_adjacency.h"
50 #include "isis_circuit.h"
53 #include "isis_dynhn.h"
55 #include "isis_route.h"
58 #include "isis_tlvs.h"
59 #include "isis_zebra.h"
61 #include "isis_spf_private.h"
63 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPFTREE
, "ISIS SPFtree");
64 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPF_RUN
, "ISIS SPF Run Info");
65 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPF_ADJ
, "ISIS SPF Adjacency");
66 DEFINE_MTYPE_STATIC(ISISD
, ISIS_VERTEX
, "ISIS vertex");
67 DEFINE_MTYPE_STATIC(ISISD
, ISIS_VERTEX_ADJ
, "ISIS SPF Vertex Adjacency");
69 static void spf_adj_list_parse_lsp(struct isis_spftree
*spftree
,
70 struct list
*adj_list
, struct isis_lsp
*lsp
,
71 const uint8_t *pseudo_nodeid
,
72 uint32_t pseudo_metric
);
75 * supports the given af ?
77 static bool speaks(uint8_t *protocols
, uint8_t count
, int family
)
79 for (uint8_t i
= 0; i
< count
; i
++) {
80 if (family
== AF_INET
&& protocols
[i
] == NLPID_IP
)
82 if (family
== AF_INET6
&& protocols
[i
] == NLPID_IPV6
)
89 struct isis_area
*area
;
94 static void remove_excess_adjs(struct list
*adjs
)
96 struct listnode
*node
, *excess
= NULL
;
97 struct isis_vertex_adj
*vadj
, *candidate
= NULL
;
100 for (ALL_LIST_ELEMENTS_RO(adjs
, node
, vadj
)) {
101 struct isis_adjacency
*adj
, *candidate_adj
;
103 adj
= vadj
->sadj
->adj
;
108 candidate
= listgetdata(excess
);
109 candidate_adj
= candidate
->sadj
->adj
;
111 if (candidate_adj
->sys_type
< adj
->sys_type
) {
115 if (candidate_adj
->sys_type
> adj
->sys_type
)
118 comp
= memcmp(candidate_adj
->sysid
, adj
->sysid
,
127 if (candidate_adj
->circuit
->idx
> adj
->circuit
->idx
) {
132 if (candidate_adj
->circuit
->idx
< adj
->circuit
->idx
)
135 comp
= memcmp(candidate_adj
->snpa
, adj
->snpa
, ETH_ALEN
);
142 list_delete_node(adjs
, excess
);
147 const char *vtype2string(enum vertextype vtype
)
150 case VTYPE_PSEUDO_IS
:
152 case VTYPE_PSEUDO_TE_IS
:
153 return "pseudo_TE-IS";
154 case VTYPE_NONPSEUDO_IS
:
156 case VTYPE_NONPSEUDO_TE_IS
:
160 case VTYPE_IPREACH_INTERNAL
:
161 return "IP internal";
162 case VTYPE_IPREACH_EXTERNAL
:
163 return "IP external";
164 case VTYPE_IPREACH_TE
:
166 case VTYPE_IP6REACH_INTERNAL
:
167 return "IP6 internal";
168 case VTYPE_IP6REACH_EXTERNAL
:
169 return "IP6 external";
173 return NULL
; /* Not reached */
176 const char *vid2string(const struct isis_vertex
*vertex
, char *buff
, int size
)
178 if (VTYPE_IS(vertex
->type
) || VTYPE_ES(vertex
->type
)) {
179 const char *hostname
= print_sys_hostname(vertex
->N
.id
);
180 strlcpy(buff
, hostname
, size
);
184 if (VTYPE_IP(vertex
->type
)) {
185 srcdest2str(&vertex
->N
.ip
.p
.dest
, &vertex
->N
.ip
.p
.src
, buff
,
193 static bool prefix_sid_cmp(const void *value1
, const void *value2
)
195 const struct isis_vertex
*c1
= value1
;
196 const struct isis_vertex
*c2
= value2
;
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
))
204 return c1
->N
.ip
.sr
.sid
.value
== c2
->N
.ip
.sr
.sid
.value
;
207 static unsigned int prefix_sid_key_make(const void *value
)
209 const struct isis_vertex
*vertex
= value
;
211 return jhash_1word(vertex
->N
.ip
.sr
.sid
.value
, 0);
214 struct isis_vertex
*isis_spf_prefix_sid_lookup(struct isis_spftree
*spftree
,
215 struct isis_prefix_sid
*psid
)
217 struct isis_vertex lookup
= {};
219 lookup
.N
.ip
.sr
.sid
= *psid
;
220 return hash_lookup(spftree
->prefix_sids
, &lookup
);
223 void isis_vertex_adj_free(void *arg
)
225 struct isis_vertex_adj
*vadj
= arg
;
227 XFREE(MTYPE_ISIS_VERTEX_ADJ
, vadj
);
230 static struct isis_vertex
*isis_vertex_new(struct isis_spftree
*spftree
,
232 enum vertextype vtype
)
234 struct isis_vertex
*vertex
;
236 vertex
= XCALLOC(MTYPE_ISIS_VERTEX
, sizeof(struct isis_vertex
));
238 isis_vertex_id_init(vertex
, id
, vtype
);
240 vertex
->Adj_N
= list_new();
241 vertex
->Adj_N
->del
= isis_vertex_adj_free
;
242 vertex
->parents
= list_new();
244 if (CHECK_FLAG(spftree
->flags
, F_SPFTREE_HOPCOUNT_METRIC
)) {
245 vertex
->firsthops
= hash_create(isis_vertex_queue_hash_key
,
246 isis_vertex_queue_hash_cmp
,
253 void isis_vertex_del(struct isis_vertex
*vertex
)
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
;
263 memset(vertex
, 0, sizeof(struct isis_vertex
));
264 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
267 struct isis_vertex_adj
*
268 isis_vertex_adj_add(struct isis_spftree
*spftree
, struct isis_vertex
*vertex
,
269 struct list
*vadj_list
, struct isis_spf_adj
*sadj
,
270 struct isis_prefix_sid
*psid
, bool last_hop
)
272 struct isis_vertex_adj
*vadj
;
274 vadj
= XCALLOC(MTYPE_ISIS_VERTEX_ADJ
, sizeof(*vadj
));
276 if (spftree
->area
->srdb
.enabled
&& psid
) {
277 if (vertex
->N
.ip
.sr
.present
278 && vertex
->N
.ip
.sr
.sid
.value
!= psid
->value
)
280 "ISIS-SPF: ignoring different Prefix-SID for route %pFX",
281 &vertex
->N
.ip
.p
.dest
);
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;
291 listnode_add(vadj_list
, vadj
);
296 static void isis_vertex_adj_del(struct isis_vertex
*vertex
,
297 struct isis_adjacency
*adj
)
299 struct isis_vertex_adj
*vadj
;
300 struct listnode
*node
, *nextnode
;
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
);
314 bool isis_vertex_adj_exists(const struct isis_spftree
*spftree
,
315 const struct isis_vertex
*vertex
,
316 const struct isis_spf_adj
*sadj
)
318 struct isis_vertex_adj
*tmp
;
319 struct listnode
*node
;
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
))
327 if (sadj
->adj
== tmp
->sadj
->adj
)
335 static void isis_spf_adj_free(void *arg
)
337 struct isis_spf_adj
*sadj
= arg
;
339 XFREE(MTYPE_ISIS_SPF_ADJ
, sadj
);
342 struct isis_spftree
*isis_spftree_new(struct isis_area
*area
,
343 struct lspdb_head
*lspdb
,
344 const uint8_t *sysid
, int level
,
345 enum spf_tree_id tree_id
,
346 enum spf_type type
, uint8_t flags
)
348 struct isis_spftree
*tree
;
350 tree
= XCALLOC(MTYPE_ISIS_SPFTREE
, sizeof(struct isis_spftree
));
352 isis_vertex_queue_init(&tree
->tents
, "IS-IS SPF tents", true);
353 isis_vertex_queue_init(&tree
->paths
, "IS-IS SPF paths", false);
354 tree
->route_table
= srcdest_table_init();
355 tree
->route_table
->cleanup
= isis_route_node_cleanup
;
356 tree
->route_table_backup
= srcdest_table_init();
357 tree
->route_table_backup
->cleanup
= isis_route_node_cleanup
;
360 tree
->prefix_sids
= hash_create(prefix_sid_key_make
, prefix_sid_cmp
,
361 "SR Prefix-SID Entries");
362 tree
->sadj_list
= list_new();
363 tree
->sadj_list
->del
= isis_spf_adj_free
;
364 tree
->last_run_timestamp
= 0;
365 tree
->last_run_monotime
= 0;
366 tree
->last_run_duration
= 0;
369 memcpy(tree
->sysid
, sysid
, ISIS_SYS_ID_LEN
);
371 tree
->tree_id
= tree_id
;
372 tree
->family
= (tree
->tree_id
== SPFTREE_IPV4
) ? AF_INET
: AF_INET6
;
374 isis_rlfa_list_init(tree
);
375 tree
->lfa
.remote
.pc_spftrees
= list_new();
376 tree
->lfa
.remote
.pc_spftrees
->del
= (void (*)(void *))isis_spftree_del
;
377 if (tree
->type
== SPF_TYPE_RLFA
|| tree
->type
== SPF_TYPE_TI_LFA
) {
378 isis_spf_node_list_init(&tree
->lfa
.p_space
);
379 isis_spf_node_list_init(&tree
->lfa
.q_space
);
385 void isis_spftree_del(struct isis_spftree
*spftree
)
387 hash_clean(spftree
->prefix_sids
, NULL
);
388 hash_free(spftree
->prefix_sids
);
389 isis_zebra_rlfa_unregister_all(spftree
);
390 isis_rlfa_list_clear(spftree
);
391 list_delete(&spftree
->lfa
.remote
.pc_spftrees
);
392 if (spftree
->type
== SPF_TYPE_RLFA
393 || spftree
->type
== SPF_TYPE_TI_LFA
) {
394 isis_spf_node_list_clear(&spftree
->lfa
.q_space
);
395 isis_spf_node_list_clear(&spftree
->lfa
.p_space
);
397 isis_spf_node_list_clear(&spftree
->adj_nodes
);
398 list_delete(&spftree
->sadj_list
);
399 isis_vertex_queue_free(&spftree
->tents
);
400 isis_vertex_queue_free(&spftree
->paths
);
401 route_table_finish(spftree
->route_table
);
402 route_table_finish(spftree
->route_table_backup
);
403 spftree
->route_table
= NULL
;
405 XFREE(MTYPE_ISIS_SPFTREE
, spftree
);
409 static void isis_spftree_adj_del(struct isis_spftree
*spftree
,
410 struct isis_adjacency
*adj
)
412 struct listnode
*node
;
413 struct isis_vertex
*v
;
416 assert(!isis_vertex_queue_count(&spftree
->tents
));
417 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, v
))
418 isis_vertex_adj_del(v
, adj
);
422 void spftree_area_init(struct isis_area
*area
)
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
))
428 if (area
->spftree
[tree
][level
- 1])
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);
439 void spftree_area_del(struct isis_area
*area
)
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
))
445 if (!area
->spftree
[tree
][level
- 1])
448 isis_spftree_del(area
->spftree
[tree
][level
- 1]);
453 static int spf_adj_state_change(struct isis_adjacency
*adj
)
455 struct isis_area
*area
= adj
->circuit
->area
;
457 if (adj
->adj_state
== ISIS_ADJ_UP
)
460 /* Remove adjacency from all SPF trees. */
461 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
462 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
463 if (!(area
->is_type
& level
))
465 if (!area
->spftree
[tree
][level
- 1])
467 isis_spftree_adj_del(area
->spftree
[tree
][level
- 1],
472 if (fabricd_spftree(area
) != NULL
)
473 isis_spftree_adj_del(fabricd_spftree(area
), adj
);
479 * Find the system LSP: returns the LSP in our LSP database
480 * associated with the given system ID.
482 struct isis_lsp
*isis_root_system_lsp(struct lspdb_head
*lspdb
,
483 const uint8_t *sysid
)
485 struct isis_lsp
*lsp
;
486 uint8_t lspid
[ISIS_SYS_ID_LEN
+ 2];
488 memcpy(lspid
, sysid
, ISIS_SYS_ID_LEN
);
489 LSP_PSEUDO_ID(lspid
) = 0;
490 LSP_FRAGMENT(lspid
) = 0;
491 lsp
= lsp_search(lspdb
, lspid
);
492 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
498 * Add this IS to the root of SPT
500 static struct isis_vertex
*isis_spf_add_root(struct isis_spftree
*spftree
)
502 struct isis_vertex
*vertex
;
504 char buff
[VID2STR_BUFFER
];
505 #endif /* EXTREME_DEBUG */
507 vertex
= isis_vertex_new(spftree
, spftree
->sysid
,
508 spftree
->area
->oldmetric
510 : VTYPE_NONPSEUDO_TE_IS
);
511 isis_vertex_queue_append(&spftree
->paths
, vertex
);
514 if (IS_DEBUG_SPF_EVENTS
)
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
,
520 #endif /* EXTREME_DEBUG */
525 static void vertex_add_parent_firsthop(struct hash_bucket
*bucket
, void *arg
)
527 struct isis_vertex
*vertex
= arg
;
528 struct isis_vertex
*hop
= bucket
->data
;
530 (void)hash_get(vertex
->firsthops
, hop
, hash_alloc_intern
);
533 static void vertex_update_firsthops(struct isis_vertex
*vertex
,
534 struct isis_vertex
*parent
)
536 if (vertex
->d_N
<= 2)
537 (void)hash_get(vertex
->firsthops
, vertex
, hash_alloc_intern
);
539 if (vertex
->d_N
< 2 || !parent
)
542 hash_iterate(parent
->firsthops
, vertex_add_parent_firsthop
, vertex
);
546 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
548 static struct isis_vertex
*
549 isis_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
)
553 struct isis_vertex
*vertex
;
554 struct listnode
*node
;
556 char buff
[VID2STR_BUFFER
];
558 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
559 if (vertex
!= NULL
) {
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
));
566 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
567 if (vertex
!= NULL
) {
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
));
575 vertex
= isis_vertex_new(spftree
, id
, vtype
);
577 vertex
->depth
= depth
;
578 if (VTYPE_IP(vtype
) && spftree
->area
->srdb
.enabled
&& psid
) {
579 struct isis_area
*area
= spftree
->area
;
580 struct isis_vertex
*vertex_psid
;
583 * Check if the Prefix-SID is already in use by another prefix.
585 vertex_psid
= isis_spf_prefix_sid_lookup(spftree
, psid
);
587 && !prefix_same(&vertex_psid
->N
.ip
.p
.dest
,
588 &vertex
->N
.ip
.p
.dest
)) {
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
)
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;
609 (void)hash_get(spftree
->prefix_sids
, vertex
,
615 listnode_add(vertex
->parents
, parent
);
618 if (CHECK_FLAG(spftree
->flags
, F_SPFTREE_HOPCOUNT_METRIC
))
619 vertex_update_firsthops(vertex
, parent
);
621 last_hop
= (vertex
->depth
== 2);
622 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
623 struct isis_vertex_adj
*parent_vadj
;
625 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
, parent_vadj
))
626 isis_vertex_adj_add(spftree
, vertex
, vertex
->Adj_N
,
627 parent_vadj
->sadj
, psid
, last_hop
);
629 isis_vertex_adj_add(spftree
, vertex
, vertex
->Adj_N
, sadj
, psid
,
634 if (IS_DEBUG_SPF_EVENTS
)
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
));
641 #endif /* EXTREME_DEBUG */
643 isis_vertex_queue_insert(&spftree
->tents
, vertex
);
647 static void isis_spf_add_local(struct isis_spftree
*spftree
,
648 enum vertextype vtype
, void *id
,
649 struct isis_spf_adj
*sadj
, uint32_t cost
,
650 struct isis_prefix_sid
*psid
,
651 struct isis_vertex
*parent
)
653 struct isis_vertex
*vertex
;
655 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
659 if (vertex
->d_N
== cost
) {
661 bool last_hop
= (vertex
->depth
== 2);
663 isis_vertex_adj_add(spftree
, vertex
,
664 vertex
->Adj_N
, sadj
, psid
,
668 if (!CHECK_FLAG(spftree
->flags
,
669 F_SPFTREE_NO_ADJACENCIES
)
670 && listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
671 remove_excess_adjs(vertex
->Adj_N
);
672 if (parent
&& (listnode_lookup(vertex
->parents
, parent
)
674 listnode_add(vertex
->parents
, parent
);
676 } else if (vertex
->d_N
< cost
) {
679 } else { /* vertex->d_N > cost */
681 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
682 isis_vertex_del(vertex
);
686 isis_spf_add2tent(spftree
, vtype
, id
, cost
, 1, sadj
, psid
, parent
);
690 static void process_N(struct isis_spftree
*spftree
, enum vertextype vtype
,
691 void *id
, uint32_t dist
, uint16_t depth
,
692 struct isis_prefix_sid
*psid
, struct isis_vertex
*parent
)
694 struct isis_vertex
*vertex
;
696 char buff
[VID2STR_BUFFER
];
699 assert(spftree
&& parent
);
701 if (CHECK_FLAG(spftree
->flags
, F_SPFTREE_HOPCOUNT_METRIC
)
705 struct prefix_pair p
;
706 if (vtype
>= VTYPE_IPREACH_INTERNAL
) {
707 memcpy(&p
, id
, sizeof(p
));
713 /* RFC3787 section 5.1 */
714 if (spftree
->area
->newmetric
== 1) {
715 if (dist
> MAX_WIDE_PATH_METRIC
)
719 else if (spftree
->area
->oldmetric
== 1) {
720 if (dist
> MAX_NARROW_PATH_METRIC
)
725 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
728 if (IS_DEBUG_SPF_EVENTS
)
730 "ISIS-SPF: process_N %s %s %s dist %d already found from PATH",
731 print_sys_hostname(vertex
->N
.id
),
733 vid2string(vertex
, buff
, sizeof(buff
)), dist
);
734 #endif /* EXTREME_DEBUG */
735 assert(dist
>= vertex
->d_N
);
739 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
744 if (IS_DEBUG_SPF_EVENTS
)
746 "ISIS-SPF: process_N %s %s %s dist %d parent %s adjcount %d",
747 print_sys_hostname(vertex
->N
.id
),
749 vid2string(vertex
, buff
, sizeof(buff
)), dist
,
750 (parent
? print_sys_hostname(parent
->N
.id
)
752 (parent
? listcount(parent
->Adj_N
) : 0));
753 #endif /* EXTREME_DEBUG */
754 if (vertex
->d_N
== dist
) {
755 struct listnode
*node
;
756 struct isis_vertex_adj
*parent_vadj
;
757 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
,
759 if (!isis_vertex_adj_exists(
761 parent_vadj
->sadj
)) {
762 bool last_hop
= (vertex
->depth
== 2);
764 isis_vertex_adj_add(spftree
, vertex
,
769 if (CHECK_FLAG(spftree
->flags
,
770 F_SPFTREE_HOPCOUNT_METRIC
))
771 vertex_update_firsthops(vertex
, parent
);
773 if (!CHECK_FLAG(spftree
->flags
,
774 F_SPFTREE_NO_ADJACENCIES
)
775 && listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
776 remove_excess_adjs(vertex
->Adj_N
);
777 if (listnode_lookup(vertex
->parents
, parent
) == NULL
)
778 listnode_add(vertex
->parents
, parent
);
780 } else if (vertex
->d_N
< dist
) {
784 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
785 isis_vertex_del(vertex
);
790 if (IS_DEBUG_SPF_EVENTS
)
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"));
795 #endif /* EXTREME_DEBUG */
797 isis_spf_add2tent(spftree
, vtype
, id
, dist
, depth
, NULL
, psid
, parent
);
804 static int isis_spf_process_lsp(struct isis_spftree
*spftree
,
805 struct isis_lsp
*lsp
, uint32_t cost
,
806 uint16_t depth
, uint8_t *root_sysid
,
807 struct isis_vertex
*parent
)
809 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
810 struct listnode
*fragnode
= NULL
;
812 enum vertextype vtype
;
813 static const uint8_t null_sysid
[ISIS_SYS_ID_LEN
];
814 struct isis_mt_router_info
*mt_router_info
= NULL
;
815 struct prefix_pair ip_info
;
818 if (isis_lfa_excise_node_check(spftree
, lsp
->hdr
.lsp_id
)) {
820 zlog_debug("ISIS-LFA: excising node %s",
821 print_sys_hostname(lsp
->hdr
.lsp_id
));
828 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
)
829 mt_router_info
= isis_tlvs_lookup_mt_router_info(lsp
->tlvs
,
832 if (!pseudo_lsp
&& (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
833 && !speaks(lsp
->tlvs
->protocols_supported
.protocols
,
834 lsp
->tlvs
->protocols_supported
.count
,
839 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
840 bool no_overload
= (pseudo_lsp
841 || (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
842 && !ISIS_MASK_LSP_OL_BIT(lsp
->hdr
.lsp_bits
))
843 || (mt_router_info
&& !mt_router_info
->overload
));
846 if (lsp
->hdr
.seqno
== 0) {
847 zlog_warn("%s: lsp with 0 seq_num - ignore", __func__
);
852 if (IS_DEBUG_SPF_EVENTS
)
853 zlog_debug("ISIS-SPF: process_lsp %s",
854 print_sys_hostname(lsp
->hdr
.lsp_id
));
855 #endif /* EXTREME_DEBUG */
858 if ((pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
859 && spftree
->area
->oldmetric
) {
860 struct isis_oldstyle_reach
*r
;
861 for (r
= (struct isis_oldstyle_reach
*)
862 lsp
->tlvs
->oldstyle_reach
.head
;
868 /* Two way connectivity */
869 if (!LSP_PSEUDO_ID(r
->id
)
870 && !memcmp(r
->id
, root_sysid
,
874 && !memcmp(r
->id
, null_sysid
,
877 dist
= cost
+ r
->metric
;
881 : VTYPE_NONPSEUDO_IS
,
882 (void *)r
->id
, dist
, depth
+ 1, NULL
,
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
;
892 te_neighs
= isis_lookup_mt_items(
893 &lsp
->tlvs
->mt_reach
, spftree
->mtid
);
895 struct isis_extended_reach
*er
;
896 for (er
= te_neighs
? (struct isis_extended_reach
*)
901 /* Two way connectivity */
902 if (!LSP_PSEUDO_ID(er
->id
)
903 && !memcmp(er
->id
, root_sysid
,
907 && !memcmp(er
->id
, null_sysid
,
911 + (CHECK_FLAG(spftree
->flags
,
912 F_SPFTREE_HOPCOUNT_METRIC
)
916 LSP_PSEUDO_ID(er
->id
)
918 : VTYPE_NONPSEUDO_TE_IS
,
919 (void *)er
->id
, dist
, depth
+ 1, NULL
,
925 if (!fabricd
&& !pseudo_lsp
&& spftree
->family
== AF_INET
926 && spftree
->mtid
== ISIS_MT_IPV4_UNICAST
927 && spftree
->area
->oldmetric
) {
928 struct isis_item_list
*reachs
[] = {
929 &lsp
->tlvs
->oldstyle_ip_reach
,
930 &lsp
->tlvs
->oldstyle_ip_reach_ext
};
932 for (unsigned int i
= 0; i
< array_size(reachs
); i
++) {
933 vtype
= i
? VTYPE_IPREACH_EXTERNAL
934 : VTYPE_IPREACH_INTERNAL
;
936 memset(&ip_info
, 0, sizeof(ip_info
));
937 ip_info
.dest
.family
= AF_INET
;
939 struct isis_oldstyle_ip_reach
*r
;
940 for (r
= (struct isis_oldstyle_ip_reach
*)reachs
[i
]
943 dist
= cost
+ r
->metric
;
944 ip_info
.dest
.u
.prefix4
= r
->prefix
.prefix
;
945 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
946 process_N(spftree
, vtype
, &ip_info
,
947 dist
, depth
+ 1, NULL
, parent
);
952 /* we can skip all the rest if we're using metric style narrow */
953 if (!spftree
->area
->newmetric
)
956 if (!pseudo_lsp
&& spftree
->family
== AF_INET
) {
957 struct isis_item_list
*ipv4_reachs
;
958 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
959 ipv4_reachs
= &lsp
->tlvs
->extended_ip_reach
;
961 ipv4_reachs
= isis_lookup_mt_items(
962 &lsp
->tlvs
->mt_ip_reach
, spftree
->mtid
);
964 memset(&ip_info
, 0, sizeof(ip_info
));
965 ip_info
.dest
.family
= AF_INET
;
967 struct isis_extended_ip_reach
*r
;
969 ? (struct isis_extended_ip_reach
*)
973 dist
= cost
+ r
->metric
;
974 ip_info
.dest
.u
.prefix4
= r
->prefix
.prefix
;
975 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
977 /* Parse list of Prefix-SID subTLVs if SR is enabled */
978 has_valid_psid
= false;
979 if (spftree
->area
->srdb
.enabled
&& r
->subtlvs
) {
980 for (struct isis_item
*i
=
981 r
->subtlvs
->prefix_sids
.head
;
983 struct isis_prefix_sid
*psid
=
984 (struct isis_prefix_sid
*)i
;
986 if (psid
->algorithm
!= SR_ALGORITHM_SPF
)
989 has_valid_psid
= true;
990 process_N(spftree
, VTYPE_IPREACH_TE
,
991 &ip_info
, dist
, depth
+ 1,
994 * Stop the Prefix-SID iteration since
995 * we only support the SPF algorithm for
1001 if (!has_valid_psid
)
1002 process_N(spftree
, VTYPE_IPREACH_TE
, &ip_info
,
1003 dist
, depth
+ 1, NULL
, parent
);
1007 if (!pseudo_lsp
&& spftree
->family
== AF_INET6
) {
1008 struct isis_item_list
*ipv6_reachs
;
1009 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
1010 ipv6_reachs
= &lsp
->tlvs
->ipv6_reach
;
1012 ipv6_reachs
= isis_lookup_mt_items(
1013 &lsp
->tlvs
->mt_ipv6_reach
, spftree
->mtid
);
1015 struct isis_ipv6_reach
*r
;
1016 for (r
= ipv6_reachs
1017 ? (struct isis_ipv6_reach
*)ipv6_reachs
->head
1020 dist
= cost
+ r
->metric
;
1021 vtype
= r
->external
? VTYPE_IP6REACH_EXTERNAL
1022 : VTYPE_IP6REACH_INTERNAL
;
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
;
1028 if (spftree
->area
->srdb
.enabled
&& r
->subtlvs
&&
1029 r
->subtlvs
->source_prefix
&&
1030 r
->subtlvs
->source_prefix
->prefixlen
) {
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",
1036 r
->subtlvs
->source_prefix
,
1042 ip_info
.src
= *r
->subtlvs
->source_prefix
;
1045 /* Parse list of Prefix-SID subTLVs */
1046 has_valid_psid
= false;
1048 for (struct isis_item
*i
=
1049 r
->subtlvs
->prefix_sids
.head
;
1051 struct isis_prefix_sid
*psid
=
1052 (struct isis_prefix_sid
*)i
;
1054 if (psid
->algorithm
!= SR_ALGORITHM_SPF
)
1057 has_valid_psid
= true;
1058 process_N(spftree
, vtype
, &ip_info
,
1059 dist
, depth
+ 1, psid
,
1062 * Stop the Prefix-SID iteration since
1063 * we only support the SPF algorithm for
1069 if (!has_valid_psid
)
1070 process_N(spftree
, vtype
, &ip_info
, dist
,
1071 depth
+ 1, NULL
, parent
);
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
1082 if ((lsp
->hdr
.lsp_bits
& LSPBIT_ATT
) == LSPBIT_ATT
1083 && !spftree
->area
->attached_bit_rcv_ignore
1084 && (spftree
->area
->is_type
& IS_LEVEL_1
)
1085 && !isis_level2_adj_up(spftree
->area
)) {
1086 struct prefix_pair ip_info
= { {0} };
1087 if (IS_DEBUG_RTE_EVENTS
)
1088 zlog_debug("ISIS-Spf (%s): add default %s route",
1089 rawlspid_print(lsp
->hdr
.lsp_id
),
1090 spftree
->family
== AF_INET
? "ipv4"
1093 if (spftree
->family
== AF_INET
) {
1094 ip_info
.dest
.family
= AF_INET
;
1095 vtype
= VTYPE_IPREACH_INTERNAL
;
1097 ip_info
.dest
.family
= AF_INET6
;
1098 vtype
= VTYPE_IP6REACH_INTERNAL
;
1100 process_N(spftree
, vtype
, &ip_info
, cost
, depth
+ 1, NULL
,
1104 if (fragnode
== NULL
)
1105 fragnode
= listhead(lsp
->lspu
.frags
);
1107 fragnode
= listnextnode(fragnode
);
1110 lsp
= listgetdata(fragnode
);
1117 static struct isis_adjacency
*adj_find(struct list
*adj_list
, const uint8_t *id
,
1118 int level
, uint16_t mtid
, int family
)
1120 struct isis_adjacency
*adj
;
1121 struct listnode
*node
;
1123 for (ALL_LIST_ELEMENTS_RO(adj_list
, node
, adj
)) {
1124 if (!(adj
->level
& level
))
1126 if (memcmp(adj
->sysid
, id
, ISIS_SYS_ID_LEN
) != 0)
1128 if (adj
->adj_state
!= ISIS_ADJ_UP
)
1130 if (!adj_has_mt(adj
, mtid
))
1132 if (mtid
== ISIS_MT_IPV4_UNICAST
1133 && !speaks(adj
->nlpids
.nlpids
, adj
->nlpids
.count
, family
))
1141 struct spf_preload_tent_ip_reach_args
{
1142 struct isis_spftree
*spftree
;
1143 struct isis_vertex
*parent
;
1146 static int isis_spf_preload_tent_ip_reach_cb(const struct prefix
*prefix
,
1147 uint32_t metric
, bool external
,
1148 struct isis_subtlvs
*subtlvs
,
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
;
1156 bool has_valid_psid
= false;
1159 return LSP_ITER_CONTINUE
;
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
);
1166 if (prefix
->family
== AF_INET
)
1167 vtype
= VTYPE_IPREACH_INTERNAL
;
1169 vtype
= VTYPE_IP6REACH_INTERNAL
;
1171 /* Parse list of Prefix-SID subTLVs if SR is enabled */
1172 if (spftree
->area
->srdb
.enabled
&& subtlvs
) {
1173 for (struct isis_item
*i
= subtlvs
->prefix_sids
.head
; i
;
1175 struct isis_prefix_sid
*psid
=
1176 (struct isis_prefix_sid
*)i
;
1178 if (psid
->algorithm
!= SR_ALGORITHM_SPF
)
1181 has_valid_psid
= true;
1182 isis_spf_add_local(spftree
, vtype
, &ip_info
, NULL
, 0,
1186 * Stop the Prefix-SID iteration since we only support
1187 * the SPF algorithm for now.
1192 if (!has_valid_psid
)
1193 isis_spf_add_local(spftree
, vtype
, &ip_info
, NULL
, 0, NULL
,
1196 return LSP_ITER_CONTINUE
;
1199 static 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
)
1204 struct spf_preload_tent_ip_reach_args ip_reach_args
;
1205 struct isis_spf_adj
*sadj
;
1206 struct listnode
*node
;
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
);
1216 /* Iterate over adjacencies. */
1217 for (ALL_LIST_ELEMENTS_RO(spftree
->sadj_list
, node
, sadj
)) {
1218 const uint8_t *adj_id
;
1221 if (CHECK_FLAG(sadj
->flags
, F_ISIS_SPF_ADJ_BROADCAST
))
1222 adj_id
= sadj
->lan
.desig_is_id
;
1226 if (isis_lfa_excise_adj_check(spftree
, adj_id
)) {
1228 zlog_debug("ISIS-SPF: excising adjacency %s",
1229 isis_format_id(sadj
->id
,
1230 ISIS_SYS_ID_LEN
+ 1));
1234 metric
= CHECK_FLAG(spftree
->flags
, F_SPFTREE_HOPCOUNT_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
,
1243 sadj
->id
, sadj
, metric
, NULL
,
1245 } else if (sadj
->lsp
) {
1246 isis_spf_process_lsp(spftree
, sadj
->lsp
, metric
, 0,
1247 spftree
->sysid
, parent
);
1252 struct spf_adj_find_reverse_metric_args
{
1253 const uint8_t *id_self
;
1254 uint32_t reverse_metric
;
1257 static int spf_adj_find_reverse_metric_cb(const uint8_t *id
, uint32_t metric
,
1259 struct isis_ext_subtlvs
*subtlvs
,
1262 struct spf_adj_find_reverse_metric_args
*args
= arg
;
1264 if (memcmp(id
, args
->id_self
, ISIS_SYS_ID_LEN
))
1265 return LSP_ITER_CONTINUE
;
1267 args
->reverse_metric
= metric
;
1269 return LSP_ITER_STOP
;
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.
1277 static void spf_adj_get_reverse_metrics(struct isis_spftree
*spftree
)
1279 struct isis_spf_adj
*sadj
;
1280 struct listnode
*node
, *nnode
;
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
;
1288 /* Skip pseudonodes. */
1289 if (LSP_PSEUDO_ID(sadj
->id
))
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
);
1300 isis_spf_adj_free(sadj
);
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
;
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
,
1314 if (args
.reverse_metric
== UINT32_MAX
) {
1315 /* Delete one-way adjacency. */
1316 listnode_delete(spftree
->sadj_list
, sadj
);
1317 isis_spf_adj_free(sadj
);
1320 sadj
->metric
= args
.reverse_metric
;
1324 static 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
,
1329 struct isis_ext_subtlvs
*subtlvs
)
1331 struct isis_spf_adj
*sadj
;
1332 uint8_t lspid
[ISIS_SYS_ID_LEN
+ 2];
1333 struct isis_lsp
*lsp
;
1336 /* Skip self in the pseudonode. */
1337 if (desig_is_id
&& !memcmp(id
, spftree
->sysid
, ISIS_SYS_ID_LEN
))
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",
1346 spftree
->level
, rawlspid_print(lspid
));
1350 sadj
= XCALLOC(MTYPE_ISIS_SPF_ADJ
, sizeof(*sadj
));
1351 memcpy(sadj
->id
, id
, sizeof(sadj
->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
;
1358 sadj
->metric
= metric
;
1360 SET_FLAG(flags
, F_ISIS_SPF_ADJ_OLDMETRIC
);
1362 sadj
->subtlvs
= subtlvs
;
1363 sadj
->flags
= flags
;
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
);
1369 /* Set real adjacency. */
1370 if (!CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ADJACENCIES
)
1371 && !LSP_PSEUDO_ID(id
)) {
1372 struct isis_adjacency
*adj
;
1374 adj
= adj_find(adj_list
, id
, spftree
->level
, spftree
->mtid
,
1377 XFREE(MTYPE_ISIS_SPF_ADJ
, sadj
);
1381 listnode_delete(adj_list
, adj
);
1385 /* Add adjacency to the list. */
1386 listnode_add(spftree
->sadj_list
, sadj
);
1388 if (!LSP_PSEUDO_ID(id
)) {
1389 struct isis_spf_node
*node
;
1391 node
= isis_spf_node_find(&spftree
->adj_nodes
, id
);
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
);
1399 /* Parse pseudonode LSP too. */
1400 if (LSP_PSEUDO_ID(id
))
1401 spf_adj_list_parse_lsp(spftree
, adj_list
, lsp
, id
, metric
);
1404 static 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
)
1409 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
1410 struct isis_lsp
*frag
;
1411 struct listnode
*node
;
1412 struct isis_item
*head
;
1413 struct isis_item_list
*te_neighs
;
1415 if (lsp
->hdr
.seqno
== 0 || lsp
->hdr
.rem_lifetime
== 0)
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
);
1432 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
1433 te_neighs
= &lsp
->tlvs
->extended_reach
;
1435 te_neighs
= isis_get_mt_items(&lsp
->tlvs
->mt_reach
,
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
);
1450 if (LSP_FRAGMENT(lsp
->hdr
.lsp_id
))
1453 /* Parse LSP fragments. */
1454 for (ALL_LIST_ELEMENTS_RO(lsp
->lspu
.frags
, node
, frag
)) {
1458 spf_adj_list_parse_lsp(spftree
, adj_list
, frag
, pseudo_nodeid
,
1463 static void isis_spf_build_adj_list(struct isis_spftree
*spftree
,
1464 struct isis_lsp
*lsp
)
1466 struct list
*adj_list
= NULL
;
1468 if (!CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ADJACENCIES
))
1469 adj_list
= list_dup(spftree
->area
->adjacency_list
);
1471 spf_adj_list_parse_lsp(spftree
, adj_list
, lsp
, NULL
, 0);
1473 if (!CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ADJACENCIES
))
1474 list_delete(&adj_list
);
1476 if (spftree
->type
== SPF_TYPE_REVERSE
)
1477 spf_adj_get_reverse_metrics(spftree
);
1481 * The parent(s) for vertex is set when added to TENT list
1482 * now we just put the child pointer(s) in place
1484 static void add_to_paths(struct isis_spftree
*spftree
,
1485 struct isis_vertex
*vertex
)
1487 #ifdef EXTREME_DEBUG
1488 char buff
[VID2STR_BUFFER
];
1489 #endif /* EXTREME_DEBUG */
1491 if (isis_find_vertex(&spftree
->paths
, &vertex
->N
, vertex
->type
))
1493 isis_vertex_queue_append(&spftree
->paths
, vertex
);
1495 #ifdef EXTREME_DEBUG
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
);
1502 #endif /* EXTREME_DEBUG */
1505 static void init_spt(struct isis_spftree
*spftree
, int mtid
)
1507 /* Clear data from previous run. */
1508 hash_clean(spftree
->prefix_sids
, NULL
);
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
);
1513 isis_zebra_rlfa_unregister_all(spftree
);
1514 isis_rlfa_list_clear(spftree
);
1515 list_delete_all_node(spftree
->lfa
.remote
.pc_spftrees
);
1516 memset(&spftree
->lfa
.protection_counters
, 0,
1517 sizeof(spftree
->lfa
.protection_counters
));
1519 spftree
->mtid
= mtid
;
1522 static enum spf_prefix_priority
1523 spf_prefix_priority(struct isis_spftree
*spftree
, struct isis_vertex
*vertex
)
1525 struct isis_area
*area
= spftree
->area
;
1526 struct prefix
*prefix
= &vertex
->N
.ip
.p
.dest
;
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
;
1533 ppa
= &area
->spf_prefix_priorities
[priority
];
1534 switch (spftree
->family
) {
1536 ret
= access_list_apply(ppa
->list_v4
, prefix
);
1539 ret
= access_list_apply(ppa
->list_v6
, prefix
);
1545 if (ret
== FILTER_PERMIT
)
1549 /* Assign medium priority to loopback prefixes by default. */
1550 if (is_host_route(prefix
))
1551 return SPF_PREFIX_PRIO_MEDIUM
;
1553 return SPF_PREFIX_PRIO_LOW
;
1556 static void spf_path_process(struct isis_spftree
*spftree
,
1557 struct isis_vertex
*vertex
)
1559 struct isis_area
*area
= spftree
->area
;
1560 int level
= spftree
->level
;
1561 char buff
[VID2STR_BUFFER
];
1563 if (spftree
->type
== SPF_TYPE_TI_LFA
&& VTYPE_IS(vertex
->type
)
1564 && !CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ADJACENCIES
)) {
1565 if (listcount(vertex
->Adj_N
) > 0) {
1566 struct isis_adjacency
*adj
;
1568 if (isis_tilfa_check(spftree
, vertex
) != 0)
1571 adj
= isis_adj_find(area
, level
, vertex
->N
.id
);
1573 sr_adj_sid_add_single(adj
, spftree
->family
,
1574 true, vertex
->Adj_N
);
1575 } else if (IS_DEBUG_SPF_EVENTS
)
1577 "ISIS-SPF: no adjacencies, do not install backup Adj-SID for %s depth %d dist %d",
1578 vid2string(vertex
, buff
, sizeof(buff
)),
1579 vertex
->depth
, vertex
->d_N
);
1582 if (VTYPE_IP(vertex
->type
)
1583 && !CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ROUTES
)) {
1584 enum spf_prefix_priority priority
;
1586 priority
= spf_prefix_priority(spftree
, vertex
);
1587 vertex
->N
.ip
.priority
= priority
;
1588 if (vertex
->depth
== 1 || listcount(vertex
->Adj_N
) > 0) {
1589 struct isis_spftree
*pre_spftree
;
1590 struct route_table
*route_table
= NULL
;
1591 bool allow_ecmp
= false;
1593 switch (spftree
->type
) {
1595 case SPF_TYPE_TI_LFA
:
1597 > area
->lfa_priority_limit
[level
- 1]) {
1600 "ISIS-LFA: skipping %s %s (low prefix priority)",
1609 case SPF_TYPE_FORWARD
:
1610 case SPF_TYPE_REVERSE
:
1614 switch (spftree
->type
) {
1616 isis_rlfa_check(spftree
, vertex
);
1618 case SPF_TYPE_TI_LFA
:
1619 if (isis_tilfa_check(spftree
, vertex
) != 0)
1622 pre_spftree
= spftree
->lfa
.old
.spftree
;
1623 route_table
= pre_spftree
->route_table_backup
;
1624 allow_ecmp
= area
->lfa_load_sharing
[level
- 1];
1625 pre_spftree
->lfa
.protection_counters
1626 .tilfa
[vertex
->N
.ip
.priority
] += 1;
1628 case SPF_TYPE_FORWARD
:
1629 case SPF_TYPE_REVERSE
:
1630 route_table
= spftree
->route_table
;
1634 * Update LFA protection counters (ignore local
1637 if (vertex
->depth
> 1) {
1638 spftree
->lfa
.protection_counters
1639 .total
[priority
] += 1;
1640 if (listcount(vertex
->Adj_N
) > 1)
1641 spftree
->lfa
.protection_counters
1642 .ecmp
[priority
] += 1;
1648 &vertex
->N
.ip
.p
.dest
, &vertex
->N
.ip
.p
.src
,
1649 vertex
->d_N
, vertex
->depth
, &vertex
->N
.ip
.sr
,
1650 vertex
->Adj_N
, allow_ecmp
, area
, route_table
);
1651 } else if (IS_DEBUG_SPF_EVENTS
)
1653 "ISIS-SPF: no adjacencies, do not install route for %s depth %d dist %d",
1654 vid2string(vertex
, buff
, sizeof(buff
)),
1655 vertex
->depth
, vertex
->d_N
);
1659 static void isis_spf_loop(struct isis_spftree
*spftree
,
1660 uint8_t *root_sysid
)
1662 struct isis_vertex
*vertex
;
1663 struct isis_lsp
*lsp
;
1664 struct listnode
*node
;
1666 while (isis_vertex_queue_count(&spftree
->tents
)) {
1667 vertex
= isis_vertex_queue_pop(&spftree
->tents
);
1669 #ifdef EXTREME_DEBUG
1670 if (IS_DEBUG_SPF_EVENTS
)
1672 "ISIS-SPF: get TENT node %s %s depth %d dist %d to PATHS",
1673 print_sys_hostname(vertex
->N
.id
),
1674 vtype2string(vertex
->type
), vertex
->depth
,
1676 #endif /* EXTREME_DEBUG */
1678 add_to_paths(spftree
, vertex
);
1679 if (!VTYPE_IS(vertex
->type
))
1682 lsp
= lsp_for_vertex(spftree
, vertex
);
1684 zlog_warn("ISIS-SPF: No LSP found for %s",
1685 isis_format_id(vertex
->N
.id
,
1686 sizeof(vertex
->N
.id
)));
1690 isis_spf_process_lsp(spftree
, lsp
, vertex
->d_N
, vertex
->depth
,
1691 root_sysid
, vertex
);
1694 /* Generate routes once the SPT is formed. */
1695 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, vertex
)) {
1696 /* New-style TLVs take precedence over the old-style TLVs. */
1697 switch (vertex
->type
) {
1698 case VTYPE_IPREACH_INTERNAL
:
1699 case VTYPE_IPREACH_EXTERNAL
:
1700 if (isis_find_vertex(&spftree
->paths
, &vertex
->N
,
1704 case VTYPE_PSEUDO_IS
:
1705 case VTYPE_PSEUDO_TE_IS
:
1706 case VTYPE_NONPSEUDO_IS
:
1707 case VTYPE_NONPSEUDO_TE_IS
:
1709 case VTYPE_IPREACH_TE
:
1710 case VTYPE_IP6REACH_INTERNAL
:
1711 case VTYPE_IP6REACH_EXTERNAL
:
1715 spf_path_process(spftree
, vertex
);
1719 struct isis_spftree
*isis_run_hopcount_spf(struct isis_area
*area
,
1721 struct isis_spftree
*spftree
)
1724 spftree
= isis_spftree_new(area
, &area
->lspdb
[IS_LEVEL_2
- 1],
1725 sysid
, ISIS_LEVEL2
, SPFTREE_IPV4
,
1727 F_SPFTREE_HOPCOUNT_METRIC
);
1729 init_spt(spftree
, ISIS_MT_IPV4_UNICAST
);
1730 if (!memcmp(sysid
, area
->isis
->sysid
, ISIS_SYS_ID_LEN
)) {
1731 struct isis_lsp
*root_lsp
;
1732 struct isis_vertex
*root_vertex
;
1734 root_lsp
= isis_root_system_lsp(spftree
->lspdb
, spftree
->sysid
);
1737 * If we are running locally, initialize with
1738 * information from adjacencies
1740 root_vertex
= isis_spf_add_root(spftree
);
1742 isis_spf_preload_tent(spftree
, sysid
, root_lsp
,
1746 isis_vertex_queue_insert(
1748 isis_vertex_new(spftree
, sysid
, VTYPE_NONPSEUDO_TE_IS
));
1751 isis_spf_loop(spftree
, sysid
);
1756 void isis_run_spf(struct isis_spftree
*spftree
)
1758 struct isis_lsp
*root_lsp
;
1759 struct isis_vertex
*root_vertex
;
1760 struct timeval time_start
;
1761 struct timeval time_end
;
1762 struct isis_mt_router_info
*mt_router_info
;
1765 /* Get time that can't roll backwards. */
1766 monotime(&time_start
);
1768 root_lsp
= isis_root_system_lsp(spftree
->lspdb
, spftree
->sysid
);
1769 if (root_lsp
== NULL
) {
1770 zlog_err("ISIS-SPF: could not find own l%d LSP!",
1775 /* Get Multi-Topology ID. */
1776 switch (spftree
->tree_id
) {
1778 mtid
= ISIS_MT_IPV4_UNICAST
;
1781 mt_router_info
= isis_tlvs_lookup_mt_router_info(
1782 root_lsp
->tlvs
, ISIS_MT_IPV6_UNICAST
);
1784 mtid
= ISIS_MT_IPV6_UNICAST
;
1786 mtid
= ISIS_MT_IPV4_UNICAST
;
1788 case SPFTREE_DSTSRC
:
1789 mtid
= ISIS_MT_IPV6_DSTSRC
;
1793 "%s should never be called with SPFTREE_COUNT as argument!",
1801 init_spt(spftree
, mtid
);
1803 root_vertex
= isis_spf_add_root(spftree
);
1805 isis_spf_build_adj_list(spftree
, root_lsp
);
1806 isis_spf_preload_tent(spftree
, spftree
->sysid
, root_lsp
, root_vertex
);
1811 if (!isis_vertex_queue_count(&spftree
->tents
)
1812 && (IS_DEBUG_SPF_EVENTS
)) {
1813 zlog_warn("ISIS-SPF: TENT is empty SPF-root:%s",
1814 print_sys_hostname(spftree
->sysid
));
1817 isis_spf_loop(spftree
, spftree
->sysid
);
1818 spftree
->runcount
++;
1819 spftree
->last_run_timestamp
= time(NULL
);
1820 spftree
->last_run_monotime
= monotime(&time_end
);
1821 spftree
->last_run_duration
=
1822 ((time_end
.tv_sec
- time_start
.tv_sec
) * 1000000)
1823 + (time_end
.tv_usec
- time_start
.tv_usec
);
1826 static void isis_run_spf_with_protection(struct isis_area
*area
,
1827 struct isis_spftree
*spftree
)
1829 /* Run forward SPF locally. */
1830 memcpy(spftree
->sysid
, area
->isis
->sysid
, ISIS_SYS_ID_LEN
);
1831 isis_run_spf(spftree
);
1833 /* Run LFA protection if configured. */
1834 if (area
->lfa_protected_links
[spftree
->level
- 1] > 0
1835 || area
->tilfa_protected_links
[spftree
->level
- 1] > 0)
1836 isis_spf_run_lfa(area
, spftree
);
1839 void isis_spf_verify_routes(struct isis_area
*area
, struct isis_spftree
**trees
)
1841 if (area
->is_type
== IS_LEVEL_1
) {
1842 isis_route_verify_table(area
, trees
[0]->route_table
,
1843 trees
[0]->route_table_backup
);
1844 } else if (area
->is_type
== IS_LEVEL_2
) {
1845 isis_route_verify_table(area
, trees
[1]->route_table
,
1846 trees
[1]->route_table_backup
);
1848 isis_route_verify_merge(area
, trees
[0]->route_table
,
1849 trees
[0]->route_table_backup
,
1850 trees
[1]->route_table
,
1851 trees
[1]->route_table_backup
);
1855 void isis_spf_invalidate_routes(struct isis_spftree
*tree
)
1857 isis_route_invalidate_table(tree
->area
, tree
->route_table
);
1859 /* Delete backup routes. */
1860 route_table_finish(tree
->route_table_backup
);
1861 tree
->route_table_backup
= srcdest_table_init();
1862 tree
->route_table_backup
->cleanup
= isis_route_node_cleanup
;
1865 void isis_spf_switchover_routes(struct isis_area
*area
,
1866 struct isis_spftree
**trees
, int family
,
1867 union g_addr
*nexthop_ip
, ifindex_t ifindex
,
1870 isis_route_switchover_nexthop(area
, trees
[level
- 1]->route_table
,
1871 family
, nexthop_ip
, ifindex
);
1874 static void isis_run_spf_cb(struct thread
*thread
)
1876 struct isis_spf_run
*run
= THREAD_ARG(thread
);
1877 struct isis_area
*area
= run
->area
;
1878 int level
= run
->level
;
1881 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1883 if (!(area
->is_type
& level
)) {
1884 if (IS_DEBUG_SPF_EVENTS
)
1885 zlog_warn("ISIS-SPF (%s) area does not share level",
1890 isis_area_delete_backup_adj_sids(area
, level
);
1891 isis_area_invalidate_routes(area
, level
);
1893 if (IS_DEBUG_SPF_EVENTS
)
1894 zlog_debug("ISIS-SPF (%s) L%d SPF needed, periodic SPF",
1895 area
->area_tag
, level
);
1897 if (area
->ip_circuits
) {
1898 isis_run_spf_with_protection(
1899 area
, area
->spftree
[SPFTREE_IPV4
][level
- 1]);
1902 if (area
->ipv6_circuits
) {
1903 isis_run_spf_with_protection(
1904 area
, area
->spftree
[SPFTREE_IPV6
][level
- 1]);
1907 if (area
->ipv6_circuits
&& isis_area_ipv6_dstsrc_enabled(area
)) {
1908 isis_run_spf_with_protection(
1909 area
, area
->spftree
[SPFTREE_DSTSRC
][level
- 1]);
1914 area
->spf_run_count
[level
]++;
1916 isis_area_verify_routes(area
);
1918 /* walk all circuits and reset any spf specific flags */
1919 struct listnode
*node
;
1920 struct isis_circuit
*circuit
;
1921 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
))
1922 UNSET_FLAG(circuit
->flags
, ISIS_CIRCUIT_FLAPPED_AFTER_SPF
);
1924 fabricd_run_spf(area
);
1927 static struct isis_spf_run
*isis_run_spf_arg(struct isis_area
*area
, int level
)
1929 struct isis_spf_run
*run
= XMALLOC(MTYPE_ISIS_SPF_RUN
, sizeof(*run
));
1937 void isis_spf_timer_free(void *run
)
1939 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1942 int _isis_spf_schedule(struct isis_area
*area
, int level
,
1943 const char *func
, const char *file
, int line
)
1945 struct isis_spftree
*spftree
;
1947 long tree_diff
, diff
;
1950 now
= monotime(NULL
);
1952 for (tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
1953 spftree
= area
->spftree
[tree
][level
- 1];
1954 tree_diff
= difftime(now
- spftree
->last_run_monotime
, 0);
1955 if (tree_diff
!= now
&& (diff
== 0 || tree_diff
< diff
))
1959 if (CHECK_FLAG(im
->options
, F_ISIS_UNIT_TEST
))
1963 assert(area
->is_type
& level
);
1965 if (IS_DEBUG_SPF_EVENTS
) {
1967 "ISIS-SPF (%s) L%d SPF schedule called, lastrun %ld sec ago Caller: %s %s:%d",
1968 area
->area_tag
, level
, diff
, func
, file
, line
);
1971 THREAD_OFF(area
->t_rlfa_rib_update
);
1972 if (area
->spf_delay_ietf
[level
- 1]) {
1973 /* Need to call schedule function also if spf delay is running
1975 * restart holdoff timer - compare
1976 * draft-ietf-rtgwg-backoff-algo-04 */
1978 spf_backoff_schedule(area
->spf_delay_ietf
[level
- 1]);
1979 if (area
->spf_timer
[level
- 1])
1982 thread_add_timer_msec(master
, isis_run_spf_cb
,
1983 isis_run_spf_arg(area
, level
), delay
,
1984 &area
->spf_timer
[level
- 1]);
1988 if (area
->spf_timer
[level
- 1])
1991 /* wait configured min_spf_interval before doing the SPF */
1993 if (diff
>= area
->min_spf_interval
[level
- 1]
1994 || area
->bfd_force_spf_refresh
) {
1996 * Last run is more than min interval ago or BFD signalled a
1997 * 'down' message, schedule immediate run
2001 if (area
->bfd_force_spf_refresh
) {
2003 "ISIS-SPF (%s) L%d SPF scheduled immediately due to BFD 'down' message",
2004 area
->area_tag
, level
);
2005 area
->bfd_force_spf_refresh
= false;
2008 timer
= area
->min_spf_interval
[level
- 1] - diff
;
2011 thread_add_timer(master
, isis_run_spf_cb
, isis_run_spf_arg(area
, level
),
2012 timer
, &area
->spf_timer
[level
- 1]);
2014 if (IS_DEBUG_SPF_EVENTS
)
2015 zlog_debug("ISIS-SPF (%s) L%d SPF scheduled %ld sec from now",
2016 area
->area_tag
, level
, timer
);
2021 static void isis_print_paths(struct vty
*vty
, struct isis_vertex_queue
*queue
,
2022 uint8_t *root_sysid
)
2024 struct listnode
*node
;
2025 struct isis_vertex
*vertex
;
2026 char buff
[VID2STR_BUFFER
];
2029 "Vertex Type Metric Next-Hop Interface Parent\n");
2031 for (ALL_QUEUE_ELEMENTS_RO(queue
, node
, vertex
)) {
2032 if (VTYPE_IS(vertex
->type
)
2033 && memcmp(vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
2034 vty_out(vty
, "%-20s %-12s %-6s",
2035 print_sys_hostname(root_sysid
), "", "");
2036 vty_out(vty
, "%-30s\n", "");
2041 struct listnode
*anode
= listhead(vertex
->Adj_N
);
2042 struct listnode
*pnode
= listhead(vertex
->parents
);
2043 struct isis_vertex_adj
*vadj
;
2044 struct isis_vertex
*pvertex
;
2046 vty_out(vty
, "%-20s %-12s %-6u ",
2047 vid2string(vertex
, buff
, sizeof(buff
)),
2048 vtype2string(vertex
->type
), vertex
->d_N
);
2049 for (unsigned int i
= 0;
2050 i
< MAX(vertex
->Adj_N
? listcount(vertex
->Adj_N
) : 0,
2051 vertex
->parents
? listcount(vertex
->parents
) : 0);
2054 vadj
= listgetdata(anode
);
2055 anode
= anode
->next
;
2061 pvertex
= listgetdata(pnode
);
2062 pnode
= pnode
->next
;
2069 vty_out(vty
, "%-20s %-12s %-6s ", "", "", "");
2073 struct isis_spf_adj
*sadj
= vadj
->sadj
;
2075 vty_out(vty
, "%-20s %-9s ",
2076 print_sys_hostname(sadj
->id
),
2077 sadj
->adj
? sadj
->adj
->circuit
2084 vty_out(vty
, "%-20s %-9s ", "", "");
2086 vty_out(vty
, "%s(%d)",
2087 vid2string(pvertex
, buff
, sizeof(buff
)),
2097 void isis_print_spftree(struct vty
*vty
, struct isis_spftree
*spftree
)
2099 const char *tree_id_text
= NULL
;
2101 if (!spftree
|| !isis_vertex_queue_count(&spftree
->paths
))
2104 switch (spftree
->tree_id
) {
2106 tree_id_text
= "that speak IP";
2109 tree_id_text
= "that speak IPv6";
2111 case SPFTREE_DSTSRC
:
2112 tree_id_text
= "that support IPv6 dst-src routing";
2115 assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type");
2119 vty_out(vty
, "IS-IS paths to level-%d routers %s\n", spftree
->level
,
2121 isis_print_paths(vty
, &spftree
->paths
, spftree
->sysid
);
2125 static void show_isis_topology_common(struct vty
*vty
, int levels
,
2128 struct listnode
*node
;
2129 struct isis_area
*area
;
2131 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
2134 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
2135 vty_out(vty
, "Area %s:\n",
2136 area
->area_tag
? area
->area_tag
: "null");
2138 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
2139 if ((level
& levels
) == 0)
2142 if (area
->ip_circuits
> 0) {
2145 area
->spftree
[SPFTREE_IPV4
][level
- 1]);
2147 if (area
->ipv6_circuits
> 0) {
2150 area
->spftree
[SPFTREE_IPV6
][level
- 1]);
2152 if (isis_area_ipv6_dstsrc_enabled(area
)) {
2153 isis_print_spftree(vty
,
2154 area
->spftree
[SPFTREE_DSTSRC
]
2159 if (fabricd_spftree(area
)) {
2161 "IS-IS paths to level-2 routers with hop-by-hop metric\n");
2162 isis_print_paths(vty
, &fabricd_spftree(area
)->paths
, isis
->sysid
);
2170 DEFUN(show_isis_topology
, show_isis_topology_cmd
,
2172 " [vrf <NAME|all>] topology"
2174 " [<level-1|level-2>]"
2177 SHOW_STR PROTO_HELP VRF_CMD_HELP_STR
2179 "IS-IS paths to Intermediate Systems\n"
2181 "Paths to all level-1 routers in the area\n"
2182 "Paths to all level-2 routers in the domain\n"
2186 int levels
= ISIS_LEVELS
;
2187 struct listnode
*node
;
2188 struct isis
*isis
= NULL
;
2190 const char *vrf_name
= VRF_DEFAULT_NAME
;
2191 bool all_vrf
= false;
2194 if (argv_find(argv
, argc
, "topology", &idx
)) {
2196 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
2197 else if (strmatch(argv
[idx
+ 1]->arg
, "level-1"))
2198 levels
= ISIS_LEVEL1
;
2200 levels
= ISIS_LEVEL2
;
2204 vty_out(vty
, "IS-IS Routing Process not enabled\n");
2207 ISIS_FIND_VRF_ARGS(argv
, argc
, idx_vrf
, vrf_name
, all_vrf
);
2211 for (ALL_LIST_ELEMENTS_RO(im
->isis
, node
, isis
))
2212 show_isis_topology_common(vty
, levels
, isis
);
2215 isis
= isis_lookup_by_vrfname(vrf_name
);
2217 show_isis_topology_common(vty
, levels
, isis
);
2223 static void isis_print_route(struct ttable
*tt
, const struct prefix
*prefix
,
2224 struct isis_route_info
*rinfo
, bool prefix_sid
,
2225 bool no_adjacencies
)
2227 struct isis_nexthop
*nexthop
;
2228 struct listnode
*node
;
2230 char buf_prefix
[BUFSIZ
];
2232 (void)prefix2str(prefix
, buf_prefix
, sizeof(buf_prefix
));
2233 for (ALL_LIST_ELEMENTS_RO(rinfo
->nexthops
, node
, nexthop
)) {
2234 struct interface
*ifp
;
2235 char buf_iface
[BUFSIZ
];
2236 char buf_nhop
[BUFSIZ
];
2238 if (!no_adjacencies
) {
2239 inet_ntop(nexthop
->family
, &nexthop
->ip
, buf_nhop
,
2241 ifp
= if_lookup_by_index(nexthop
->ifindex
, VRF_DEFAULT
);
2243 strlcpy(buf_iface
, ifp
->name
,
2246 snprintf(buf_iface
, sizeof(buf_iface
),
2247 "ifindex %u", nexthop
->ifindex
);
2249 strlcpy(buf_nhop
, print_sys_hostname(nexthop
->sysid
),
2251 strlcpy(buf_iface
, "-", sizeof(buf_iface
));
2255 char buf_sid
[BUFSIZ
] = {};
2256 char buf_lblop
[BUFSIZ
] = {};
2258 if (nexthop
->sr
.present
) {
2259 snprintf(buf_sid
, sizeof(buf_sid
), "%u",
2260 nexthop
->sr
.sid
.value
);
2261 sr_op2str(buf_lblop
, sizeof(buf_lblop
),
2262 rinfo
->sr
.label
, nexthop
->sr
.label
);
2264 strlcpy(buf_sid
, "-", sizeof(buf_sid
));
2265 strlcpy(buf_lblop
, "-", sizeof(buf_lblop
));
2269 ttable_add_row(tt
, "%s|%u|%s|%s|%s|%s",
2270 buf_prefix
, rinfo
->cost
,
2271 buf_iface
, buf_nhop
, buf_sid
,
2275 ttable_add_row(tt
, "||%s|%s|%s|%s", buf_iface
,
2276 buf_nhop
, buf_sid
, buf_lblop
);
2278 char buf_labels
[BUFSIZ
] = {};
2280 if (nexthop
->label_stack
) {
2282 i
< nexthop
->label_stack
->num_labels
;
2284 char buf_label
[BUFSIZ
];
2287 nexthop
->label_stack
->label
[i
],
2291 strlcat(buf_labels
, "/",
2292 sizeof(buf_labels
));
2293 strlcat(buf_labels
, buf_label
,
2294 sizeof(buf_labels
));
2296 } else if (nexthop
->sr
.present
)
2297 label2str(nexthop
->sr
.label
, 0, buf_labels
,
2298 sizeof(buf_labels
));
2300 strlcpy(buf_labels
, "-", sizeof(buf_labels
));
2303 ttable_add_row(tt
, "%s|%u|%s|%s|%s", buf_prefix
,
2304 rinfo
->cost
, buf_iface
, buf_nhop
,
2308 ttable_add_row(tt
, "||%s|%s|%s", buf_iface
,
2309 buf_nhop
, buf_labels
);
2312 if (list_isempty(rinfo
->nexthops
)) {
2314 char buf_sid
[BUFSIZ
] = {};
2315 char buf_lblop
[BUFSIZ
] = {};
2317 if (rinfo
->sr
.present
) {
2318 snprintf(buf_sid
, sizeof(buf_sid
), "%u",
2319 rinfo
->sr
.sid
.value
);
2320 sr_op2str(buf_lblop
, sizeof(buf_lblop
),
2322 MPLS_LABEL_IMPLICIT_NULL
);
2324 strlcpy(buf_sid
, "-", sizeof(buf_sid
));
2325 strlcpy(buf_lblop
, "-", sizeof(buf_lblop
));
2328 ttable_add_row(tt
, "%s|%u|%s|%s|%s|%s", buf_prefix
,
2329 rinfo
->cost
, "-", "-", buf_sid
,
2332 ttable_add_row(tt
, "%s|%u|%s|%s|%s", buf_prefix
,
2333 rinfo
->cost
, "-", "-", "-");
2337 void isis_print_routes(struct vty
*vty
, struct isis_spftree
*spftree
,
2338 bool prefix_sid
, bool backup
)
2340 struct route_table
*route_table
;
2342 struct route_node
*rn
;
2343 bool no_adjacencies
= false;
2344 const char *tree_id_text
= NULL
;
2349 switch (spftree
->tree_id
) {
2351 tree_id_text
= "IPv4";
2354 tree_id_text
= "IPv6";
2356 case SPFTREE_DSTSRC
:
2357 tree_id_text
= "IPv6 (dst-src routing)";
2360 assert(!"isis_print_routes shouldn't be called with SPFTREE_COUNT as type");
2364 vty_out(vty
, "IS-IS %s %s routing table:\n\n",
2365 circuit_t2string(spftree
->level
), tree_id_text
);
2367 /* Prepare table. */
2368 tt
= ttable_new(&ttable_styles
[TTSTYLE_BLANK
]);
2370 ttable_add_row(tt
, "Prefix|Metric|Interface|Nexthop|SID|Label Op.");
2372 ttable_add_row(tt
, "Prefix|Metric|Interface|Nexthop|Label(s)");
2373 tt
->style
.cell
.rpad
= 2;
2374 tt
->style
.corner
= '+';
2376 ttable_rowseps(tt
, 0, BOTTOM
, true, '-');
2378 if (CHECK_FLAG(spftree
->flags
, F_SPFTREE_NO_ADJACENCIES
))
2379 no_adjacencies
= true;
2382 (backup
) ? spftree
->route_table_backup
: spftree
->route_table
;
2383 for (rn
= route_top(route_table
); rn
; rn
= route_next(rn
)) {
2384 struct isis_route_info
*rinfo
;
2390 isis_print_route(tt
, &rn
->p
, rinfo
, prefix_sid
, no_adjacencies
);
2393 /* Dump the generated table. */
2394 if (tt
->nrows
> 1) {
2397 table
= ttable_dump(tt
, "\n");
2398 vty_out(vty
, "%s\n", table
);
2399 XFREE(MTYPE_TMP
, table
);
2404 static void show_isis_route_common(struct vty
*vty
, int levels
,
2405 struct isis
*isis
, bool prefix_sid
,
2408 struct listnode
*node
;
2409 struct isis_area
*area
;
2411 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
2414 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
2415 vty_out(vty
, "Area %s:\n",
2416 area
->area_tag
? area
->area_tag
: "null");
2418 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
2419 if ((level
& levels
) == 0)
2422 if (area
->ip_circuits
> 0) {
2425 area
->spftree
[SPFTREE_IPV4
][level
- 1],
2426 prefix_sid
, backup
);
2428 if (area
->ipv6_circuits
> 0) {
2431 area
->spftree
[SPFTREE_IPV6
][level
- 1],
2432 prefix_sid
, backup
);
2434 if (isis_area_ipv6_dstsrc_enabled(area
)) {
2435 isis_print_routes(vty
,
2436 area
->spftree
[SPFTREE_DSTSRC
]
2438 prefix_sid
, backup
);
2444 DEFUN(show_isis_route
, show_isis_route_cmd
,
2446 " [vrf <NAME|all>] route"
2448 " [<level-1|level-2>]"
2450 " [<prefix-sid|backup>]",
2451 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
2452 "IS-IS routing table\n"
2457 "Show Prefix-SID information\n"
2458 "Show backup routes\n")
2462 struct listnode
*node
;
2463 const char *vrf_name
= VRF_DEFAULT_NAME
;
2464 bool all_vrf
= false;
2465 bool prefix_sid
= false;
2466 bool backup
= false;
2469 if (argv_find(argv
, argc
, "level-1", &idx
))
2470 levels
= ISIS_LEVEL1
;
2471 else if (argv_find(argv
, argc
, "level-2", &idx
))
2472 levels
= ISIS_LEVEL2
;
2474 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
2477 vty_out(vty
, "IS-IS Routing Process not enabled\n");
2480 ISIS_FIND_VRF_ARGS(argv
, argc
, idx
, vrf_name
, all_vrf
);
2482 if (argv_find(argv
, argc
, "prefix-sid", &idx
))
2484 if (argv_find(argv
, argc
, "backup", &idx
))
2489 for (ALL_LIST_ELEMENTS_RO(im
->isis
, node
, isis
))
2490 show_isis_route_common(vty
, levels
, isis
,
2491 prefix_sid
, backup
);
2494 isis
= isis_lookup_by_vrfname(vrf_name
);
2496 show_isis_route_common(vty
, levels
, isis
, prefix_sid
,
2503 static void isis_print_frr_summary_line(struct ttable
*tt
,
2504 const char *protection
,
2505 uint32_t counters
[SPF_PREFIX_PRIO_MAX
])
2507 uint32_t critical
, high
, medium
, low
, total
;
2509 critical
= counters
[SPF_PREFIX_PRIO_CRITICAL
];
2510 high
= counters
[SPF_PREFIX_PRIO_HIGH
];
2511 medium
= counters
[SPF_PREFIX_PRIO_MEDIUM
];
2512 low
= counters
[SPF_PREFIX_PRIO_LOW
];
2513 total
= critical
+ high
+ medium
+ low
;
2515 ttable_add_row(tt
, "%s|%u|%u|%u|%u|%u", protection
, critical
, high
,
2516 medium
, low
, total
);
2520 isis_print_frr_summary_line_coverage(struct ttable
*tt
, const char *protection
,
2521 double counters
[SPF_PREFIX_PRIO_MAX
],
2524 double critical
, high
, medium
, low
;
2526 critical
= counters
[SPF_PREFIX_PRIO_CRITICAL
] * 100;
2527 high
= counters
[SPF_PREFIX_PRIO_HIGH
] * 100;
2528 medium
= counters
[SPF_PREFIX_PRIO_MEDIUM
] * 100;
2529 low
= counters
[SPF_PREFIX_PRIO_LOW
] * 100;
2532 ttable_add_row(tt
, "%s|%.2f%%|%.2f%%|%.2f%%|%.2f%%|%.2f%%", protection
,
2533 critical
, high
, medium
, low
, total
);
2536 static void isis_print_frr_summary(struct vty
*vty
,
2537 struct isis_spftree
*spftree
)
2541 const char *tree_id_text
= NULL
;
2542 uint32_t protectd
[SPF_PREFIX_PRIO_MAX
] = {0};
2543 uint32_t unprotected
[SPF_PREFIX_PRIO_MAX
] = {0};
2544 double coverage
[SPF_PREFIX_PRIO_MAX
] = {0};
2545 uint32_t protected_total
= 0, grand_total
= 0;
2546 double coverage_total
;
2551 switch (spftree
->tree_id
) {
2553 tree_id_text
= "IPv4";
2556 tree_id_text
= "IPv6";
2558 case SPFTREE_DSTSRC
:
2559 tree_id_text
= "IPv6 (dst-src routing)";
2562 assert(!"isis_print_frr_summary shouldn't be called with SPFTREE_COUNT as type");
2566 vty_out(vty
, " IS-IS %s %s Fast ReRoute summary:\n\n",
2567 circuit_t2string(spftree
->level
), tree_id_text
);
2569 /* Prepare table. */
2570 tt
= ttable_new(&ttable_styles
[TTSTYLE_BLANK
]);
2573 "Protection \\ Priority|Critical|High |Medium |Low |Total");
2574 tt
->style
.cell
.rpad
= 2;
2575 tt
->style
.corner
= '+';
2577 ttable_rowseps(tt
, 0, BOTTOM
, true, '-');
2579 /* Compute unprotected and coverage totals. */
2580 for (int priority
= SPF_PREFIX_PRIO_CRITICAL
;
2581 priority
< SPF_PREFIX_PRIO_MAX
; priority
++) {
2582 uint32_t *lfa
= spftree
->lfa
.protection_counters
.lfa
;
2583 uint32_t *rlfa
= spftree
->lfa
.protection_counters
.rlfa
;
2584 uint32_t *tilfa
= spftree
->lfa
.protection_counters
.tilfa
;
2585 uint32_t *ecmp
= spftree
->lfa
.protection_counters
.ecmp
;
2586 uint32_t *total
= spftree
->lfa
.protection_counters
.total
;
2588 protectd
[priority
] = lfa
[priority
] + rlfa
[priority
]
2589 + tilfa
[priority
] + ecmp
[priority
];
2590 /* Safeguard to protect against possible inconsistencies. */
2591 if (protectd
[priority
] > total
[priority
])
2592 protectd
[priority
] = total
[priority
];
2593 unprotected
[priority
] = total
[priority
] - protectd
[priority
];
2594 protected_total
+= protectd
[priority
];
2595 grand_total
+= total
[priority
];
2597 if (!total
[priority
])
2598 coverage
[priority
] = 0;
2600 coverage
[priority
] =
2601 protectd
[priority
] / (double)total
[priority
];
2607 coverage_total
= protected_total
/ (double)grand_total
;
2610 isis_print_frr_summary_line(tt
, "Classic LFA",
2611 spftree
->lfa
.protection_counters
.lfa
);
2612 isis_print_frr_summary_line(tt
, "Remote LFA",
2613 spftree
->lfa
.protection_counters
.rlfa
);
2614 isis_print_frr_summary_line(tt
, "Topology Independent LFA",
2615 spftree
->lfa
.protection_counters
.tilfa
);
2616 isis_print_frr_summary_line(tt
, "ECMP",
2617 spftree
->lfa
.protection_counters
.ecmp
);
2618 isis_print_frr_summary_line(tt
, "Unprotected", unprotected
);
2619 isis_print_frr_summary_line_coverage(tt
, "Protection coverage",
2620 coverage
, coverage_total
);
2622 /* Dump the generated table. */
2623 table
= ttable_dump(tt
, "\n");
2624 vty_out(vty
, "%s\n", table
);
2625 XFREE(MTYPE_TMP
, table
);
2629 static void show_isis_frr_summary_common(struct vty
*vty
, int levels
,
2632 struct listnode
*node
;
2633 struct isis_area
*area
;
2635 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
2638 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
2639 vty_out(vty
, "Area %s:\n",
2640 area
->area_tag
? area
->area_tag
: "null");
2642 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
2643 if ((level
& levels
) == 0)
2646 if (area
->ip_circuits
> 0) {
2647 isis_print_frr_summary(
2649 area
->spftree
[SPFTREE_IPV4
][level
- 1]);
2651 if (area
->ipv6_circuits
> 0) {
2652 isis_print_frr_summary(
2654 area
->spftree
[SPFTREE_IPV6
][level
- 1]);
2656 if (isis_area_ipv6_dstsrc_enabled(area
)) {
2657 isis_print_frr_summary(
2658 vty
, area
->spftree
[SPFTREE_DSTSRC
]
2665 DEFUN(show_isis_frr_summary
, show_isis_frr_summary_cmd
,
2667 " [vrf <NAME|all>] fast-reroute summary"
2669 " [<level-1|level-2>]"
2672 SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR
2673 "IS-IS FRR information\n"
2683 struct listnode
*node
;
2684 const char *vrf_name
= VRF_DEFAULT_NAME
;
2685 bool all_vrf
= false;
2688 if (argv_find(argv
, argc
, "level-1", &idx
))
2689 levels
= ISIS_LEVEL1
;
2690 else if (argv_find(argv
, argc
, "level-2", &idx
))
2691 levels
= ISIS_LEVEL2
;
2693 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
2696 vty_out(vty
, "IS-IS Routing Process not enabled\n");
2699 ISIS_FIND_VRF_ARGS(argv
, argc
, idx
, vrf_name
, all_vrf
);
2703 for (ALL_LIST_ELEMENTS_RO(im
->isis
, node
, isis
))
2704 show_isis_frr_summary_common(vty
, levels
, isis
);
2707 isis
= isis_lookup_by_vrfname(vrf_name
);
2709 show_isis_frr_summary_common(vty
, levels
, isis
);
2715 void isis_spf_init(void)
2717 install_element(VIEW_NODE
, &show_isis_topology_cmd
);
2718 install_element(VIEW_NODE
, &show_isis_route_cmd
);
2719 install_element(VIEW_NODE
, &show_isis_frr_summary_cmd
);
2721 /* Register hook(s). */
2722 hook_register(isis_adj_state_change_hook
, spf_adj_state_change
);
2725 void isis_spf_print(struct isis_spftree
*spftree
, struct vty
*vty
)
2727 uint64_t last_run_duration
= spftree
->last_run_duration
;
2729 vty_out(vty
, " last run elapsed : ");
2730 vty_out_timestr(vty
, spftree
->last_run_timestamp
);
2733 vty_out(vty
, " last run duration : %" PRIu64
" usec\n",
2736 vty_out(vty
, " run count : %u\n", spftree
->runcount
);
2738 void isis_spf_print_json(struct isis_spftree
*spftree
, struct json_object
*json
)
2740 char uptime
[MONOTIME_STRLEN
];
2743 cur
-= spftree
->last_run_timestamp
;
2744 frrtime_to_interval(cur
, uptime
, sizeof(uptime
));
2745 json_object_string_add(json
, "last-run-elapsed", uptime
);
2746 json_object_int_add(json
, "last-run-duration-usec",
2747 spftree
->last_run_duration
);
2748 json_object_int_add(json
, "last-run-count", spftree
->runcount
);