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
37 #include "spf_backoff.h"
41 #include "isis_constants.h"
42 #include "isis_common.h"
43 #include "isis_flags.h"
46 #include "isis_misc.h"
47 #include "isis_adjacency.h"
48 #include "isis_circuit.h"
51 #include "isis_dynhn.h"
53 #include "isis_route.h"
56 #include "isis_tlvs.h"
58 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPF_RUN
, "ISIS SPF Run Info");
64 VTYPE_NONPSEUDO_TE_IS
,
66 VTYPE_IPREACH_INTERNAL
,
67 VTYPE_IPREACH_EXTERNAL
,
69 VTYPE_IP6REACH_INTERNAL
,
70 VTYPE_IP6REACH_EXTERNAL
73 #define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS)
74 #define VTYPE_ES(t) ((t) == VTYPE_ES)
75 #define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL)
78 * Triple <N, d(N), {Adj(N)}>
81 uint8_t id
[ISIS_SYS_ID_LEN
+ 1];
87 uint32_t d_N
; /* d(N) Distance from this IS */
88 uint16_t depth
; /* The depth in the imaginary tree */
89 struct list
*Adj_N
; /* {Adj(N)} next hop or neighbor list */
90 struct list
*parents
; /* list of parents for ECMP */
91 uint64_t insert_counter
;
94 /* Vertex Queue and associated functions */
96 struct isis_vertex_queue
{
98 struct skiplist
*slist
;
102 uint64_t insert_counter
;
105 static unsigned isis_vertex_queue_hash_key(void *vp
)
107 struct isis_vertex
*vertex
= vp
;
109 if (VTYPE_IP(vertex
->type
))
110 return prefix_hash_key(&vertex
->N
.prefix
);
112 return jhash(vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1, 0x55aa5a5a);
115 static int isis_vertex_queue_hash_cmp(const void *a
, const void *b
)
117 const struct isis_vertex
*va
= a
, *vb
= b
;
119 if (va
->type
!= vb
->type
)
122 if (VTYPE_IP(va
->type
))
123 return prefix_cmp(&va
->N
.prefix
, &vb
->N
.prefix
) == 0;
125 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
129 * Compares vertizes for sorting in the TENT list. Returns true
130 * if candidate should be considered before current, false otherwise.
132 static int isis_vertex_queue_tent_cmp(void *a
, void *b
)
134 struct isis_vertex
*va
= a
;
135 struct isis_vertex
*vb
= b
;
137 if (va
->d_N
< vb
->d_N
)
140 if (va
->d_N
> vb
->d_N
)
143 if (va
->type
< vb
->type
)
146 if (va
->type
> vb
->type
)
149 if (va
->insert_counter
< vb
->insert_counter
)
152 if (va
->insert_counter
> vb
->insert_counter
)
158 static struct skiplist
*isis_vertex_queue_skiplist(void)
160 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
163 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
,
164 const char *name
, bool ordered
)
167 queue
->insert_counter
= 1;
168 queue
->l
.slist
= isis_vertex_queue_skiplist();
170 queue
->insert_counter
= 0;
171 queue
->l
.list
= list_new();
173 queue
->hash
= hash_create(isis_vertex_queue_hash_key
,
174 isis_vertex_queue_hash_cmp
, name
);
177 static void isis_vertex_del(struct isis_vertex
*vertex
);
179 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
181 hash_clean(queue
->hash
, NULL
);
183 if (queue
->insert_counter
) {
184 struct isis_vertex
*vertex
;
185 while (0 == skiplist_first(queue
->l
.slist
, NULL
,
187 isis_vertex_del(vertex
);
188 skiplist_delete_first(queue
->l
.slist
);
190 queue
->insert_counter
= 1;
192 queue
->l
.list
->del
= (void (*)(void *))isis_vertex_del
;
193 list_delete_all_node(queue
->l
.list
);
194 queue
->l
.list
->del
= NULL
;
198 static void isis_vertex_queue_free(struct isis_vertex_queue
*queue
)
200 isis_vertex_queue_clear(queue
);
202 hash_free(queue
->hash
);
205 if (queue
->insert_counter
) {
206 skiplist_free(queue
->l
.slist
);
207 queue
->l
.slist
= NULL
;
209 list_delete_and_null(&queue
->l
.list
);
212 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue
*queue
)
214 return hashcount(queue
->hash
);
217 static void isis_vertex_queue_append(struct isis_vertex_queue
*queue
,
218 struct isis_vertex
*vertex
)
220 assert(!queue
->insert_counter
);
222 listnode_add(queue
->l
.list
, vertex
);
224 struct isis_vertex
*inserted
;
226 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
227 assert(inserted
== vertex
);
230 static void isis_vertex_queue_insert(struct isis_vertex_queue
*queue
,
231 struct isis_vertex
*vertex
)
233 assert(queue
->insert_counter
);
234 vertex
->insert_counter
= queue
->insert_counter
++;
235 assert(queue
->insert_counter
!= (uint64_t)-1);
237 skiplist_insert(queue
->l
.slist
, vertex
, vertex
);
239 struct isis_vertex
*inserted
;
240 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
241 assert(inserted
== vertex
);
244 static struct isis_vertex
*
245 isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
247 assert(queue
->insert_counter
);
249 struct isis_vertex
*rv
;
251 if (skiplist_first(queue
->l
.slist
, NULL
, (void **)&rv
))
254 skiplist_delete_first(queue
->l
.slist
);
255 hash_release(queue
->hash
, rv
);
260 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
261 struct isis_vertex
*vertex
)
263 assert(queue
->insert_counter
);
265 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
266 hash_release(queue
->hash
, vertex
);
269 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
270 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
273 /* End of vertex queue definitions */
275 struct isis_spftree
{
276 struct isis_vertex_queue paths
; /* the SPT */
277 struct isis_vertex_queue tents
; /* TENT */
278 struct isis_area
*area
; /* back pointer to area */
279 unsigned int runcount
; /* number of runs since uptime */
280 time_t last_run_timestamp
; /* last run timestamp as wall time for display */
281 time_t last_run_monotime
; /* last run as monotime for scheduling */
282 time_t last_run_duration
; /* last run duration in msec */
291 * supports the given af ?
293 static bool speaks(uint8_t *protocols
, uint8_t count
, int family
)
295 for (uint8_t i
= 0; i
< count
; i
++) {
296 if (family
== AF_INET
&& protocols
[i
] == NLPID_IP
)
298 if (family
== AF_INET6
&& protocols
[i
] == NLPID_IPV6
)
304 struct isis_spf_run
{
305 struct isis_area
*area
;
310 static void remove_excess_adjs(struct list
*adjs
)
312 struct listnode
*node
, *excess
= NULL
;
313 struct isis_adjacency
*adj
, *candidate
= NULL
;
316 for (ALL_LIST_ELEMENTS_RO(adjs
, node
, adj
)) {
319 candidate
= listgetdata(excess
);
321 if (candidate
->sys_type
< adj
->sys_type
) {
325 if (candidate
->sys_type
> adj
->sys_type
)
328 comp
= memcmp(candidate
->sysid
, adj
->sysid
, ISIS_SYS_ID_LEN
);
336 if (candidate
->circuit
->idx
> adj
->circuit
->idx
) {
341 if (candidate
->circuit
->idx
< adj
->circuit
->idx
)
344 comp
= memcmp(candidate
->snpa
, adj
->snpa
, ETH_ALEN
);
351 list_delete_node(adjs
, excess
);
356 static const char *vtype2string(enum vertextype vtype
)
359 case VTYPE_PSEUDO_IS
:
362 case VTYPE_PSEUDO_TE_IS
:
363 return "pseudo_TE-IS";
365 case VTYPE_NONPSEUDO_IS
:
368 case VTYPE_NONPSEUDO_TE_IS
:
374 case VTYPE_IPREACH_INTERNAL
:
375 return "IP internal";
377 case VTYPE_IPREACH_EXTERNAL
:
378 return "IP external";
380 case VTYPE_IPREACH_TE
:
383 case VTYPE_IP6REACH_INTERNAL
:
384 return "IP6 internal";
386 case VTYPE_IP6REACH_EXTERNAL
:
387 return "IP6 external";
392 return NULL
; /* Not reached */
395 static const char *vid2string(struct isis_vertex
*vertex
, char *buff
, int size
)
397 if (VTYPE_IS(vertex
->type
) || VTYPE_ES(vertex
->type
)) {
398 return print_sys_hostname(vertex
->N
.id
);
401 if (VTYPE_IP(vertex
->type
)) {
402 prefix2str((struct prefix
*)&vertex
->N
.prefix
, buff
, size
);
409 static void isis_vertex_id_init(struct isis_vertex
*vertex
, union isis_N
*n
,
410 enum vertextype vtype
)
412 vertex
->type
= vtype
;
414 if (VTYPE_IS(vtype
) || VTYPE_ES(vtype
)) {
415 memcpy(vertex
->N
.id
, n
->id
, ISIS_SYS_ID_LEN
+ 1);
416 } else if (VTYPE_IP(vtype
)) {
417 memcpy(&vertex
->N
.prefix
, &n
->prefix
, sizeof(struct prefix
));
423 static struct isis_vertex
*isis_vertex_new(union isis_N
*n
,
424 enum vertextype vtype
)
426 struct isis_vertex
*vertex
;
428 vertex
= XCALLOC(MTYPE_ISIS_VERTEX
, sizeof(struct isis_vertex
));
430 isis_vertex_id_init(vertex
, n
, vtype
);
432 vertex
->Adj_N
= list_new();
433 vertex
->parents
= list_new();
438 static void isis_vertex_del(struct isis_vertex
*vertex
)
440 list_delete_and_null(&vertex
->Adj_N
);
441 list_delete_and_null(&vertex
->parents
);
443 memset(vertex
, 0, sizeof(struct isis_vertex
));
444 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
449 static void isis_vertex_adj_del(struct isis_vertex
*vertex
,
450 struct isis_adjacency
*adj
)
452 struct listnode
*node
, *nextnode
;
455 for (node
= listhead(vertex
->Adj_N
); node
; node
= nextnode
) {
456 nextnode
= listnextnode(node
);
457 if (listgetdata(node
) == adj
)
458 list_delete_node(vertex
->Adj_N
, node
);
463 struct isis_spftree
*isis_spftree_new(struct isis_area
*area
)
465 struct isis_spftree
*tree
;
467 tree
= XCALLOC(MTYPE_ISIS_SPFTREE
, sizeof(struct isis_spftree
));
469 zlog_err("ISIS-Spf: isis_spftree_new Out of memory!");
473 isis_vertex_queue_init(&tree
->tents
, "IS-IS SPF tents", true);
474 isis_vertex_queue_init(&tree
->paths
, "IS-IS SPF paths", false);
476 tree
->last_run_timestamp
= 0;
477 tree
->last_run_monotime
= 0;
478 tree
->last_run_duration
= 0;
483 void isis_spftree_del(struct isis_spftree
*spftree
)
485 isis_vertex_queue_free(&spftree
->tents
);
486 isis_vertex_queue_free(&spftree
->paths
);
487 XFREE(MTYPE_ISIS_SPFTREE
, spftree
);
492 static void isis_spftree_adj_del(struct isis_spftree
*spftree
,
493 struct isis_adjacency
*adj
)
495 struct listnode
*node
;
496 struct isis_vertex
*v
;
499 assert(!isis_vertex_queue_count(&spftree
->tents
));
500 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, v
))
501 isis_vertex_adj_del(v
, adj
);
505 void spftree_area_init(struct isis_area
*area
)
507 if (area
->is_type
& IS_LEVEL_1
) {
508 if (area
->spftree
[0] == NULL
)
509 area
->spftree
[0] = isis_spftree_new(area
);
510 if (area
->spftree6
[0] == NULL
)
511 area
->spftree6
[0] = isis_spftree_new(area
);
514 if (area
->is_type
& IS_LEVEL_2
) {
515 if (area
->spftree
[1] == NULL
)
516 area
->spftree
[1] = isis_spftree_new(area
);
517 if (area
->spftree6
[1] == NULL
)
518 area
->spftree6
[1] = isis_spftree_new(area
);
524 void spftree_area_del(struct isis_area
*area
)
526 if (area
->is_type
& IS_LEVEL_1
) {
527 if (area
->spftree
[0] != NULL
) {
528 isis_spftree_del(area
->spftree
[0]);
529 area
->spftree
[0] = NULL
;
531 if (area
->spftree6
[0]) {
532 isis_spftree_del(area
->spftree6
[0]);
533 area
->spftree6
[0] = NULL
;
537 if (area
->is_type
& IS_LEVEL_2
) {
538 if (area
->spftree
[1] != NULL
) {
539 isis_spftree_del(area
->spftree
[1]);
540 area
->spftree
[1] = NULL
;
542 if (area
->spftree6
[1] != NULL
) {
543 isis_spftree_del(area
->spftree6
[1]);
544 area
->spftree6
[1] = NULL
;
551 void spftree_area_adj_del(struct isis_area
*area
, struct isis_adjacency
*adj
)
553 if (area
->is_type
& IS_LEVEL_1
) {
554 if (area
->spftree
[0] != NULL
)
555 isis_spftree_adj_del(area
->spftree
[0], adj
);
556 if (area
->spftree6
[0] != NULL
)
557 isis_spftree_adj_del(area
->spftree6
[0], adj
);
560 if (area
->is_type
& IS_LEVEL_2
) {
561 if (area
->spftree
[1] != NULL
)
562 isis_spftree_adj_del(area
->spftree
[1], adj
);
563 if (area
->spftree6
[1] != NULL
)
564 isis_spftree_adj_del(area
->spftree6
[1], adj
);
571 * Find the system LSP: returns the LSP in our LSP database
572 * associated with the given system ID.
574 static struct isis_lsp
*isis_root_system_lsp(struct isis_area
*area
, int level
,
577 struct isis_lsp
*lsp
;
578 uint8_t lspid
[ISIS_SYS_ID_LEN
+ 2];
580 memcpy(lspid
, sysid
, ISIS_SYS_ID_LEN
);
581 LSP_PSEUDO_ID(lspid
) = 0;
582 LSP_FRAGMENT(lspid
) = 0;
583 lsp
= lsp_search(lspid
, area
->lspdb
[level
- 1]);
584 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
590 * Add this IS to the root of SPT
592 static struct isis_vertex
*isis_spf_add_root(struct isis_spftree
*spftree
,
595 struct isis_vertex
*vertex
;
596 struct isis_lsp
*lsp
;
598 char buff
[PREFIX2STR_BUFFER
];
599 #endif /* EXTREME_DEBUG */
602 memcpy(n
.id
, sysid
, ISIS_SYS_ID_LEN
);
603 LSP_PSEUDO_ID(n
.id
) = 0;
605 lsp
= isis_root_system_lsp(spftree
->area
, spftree
->level
, sysid
);
607 zlog_warn("ISIS-Spf: could not find own l%d LSP!",
610 vertex
= isis_vertex_new(&n
,
611 spftree
->area
->oldmetric
613 : VTYPE_NONPSEUDO_TE_IS
);
614 isis_vertex_queue_append(&spftree
->paths
, vertex
);
617 zlog_debug("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
618 vtype2string(vertex
->type
),
619 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
621 #endif /* EXTREME_DEBUG */
626 static struct isis_vertex
*isis_find_vertex(struct isis_vertex_queue
*queue
,
628 enum vertextype vtype
)
630 struct isis_vertex querier
;
632 isis_vertex_id_init(&querier
, n
, vtype
);
633 return hash_lookup(queue
->hash
, &querier
);
637 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
639 static struct isis_vertex
*isis_spf_add2tent(struct isis_spftree
*spftree
,
640 enum vertextype vtype
, void *id
,
641 uint32_t cost
, int depth
,
642 struct isis_adjacency
*adj
,
643 struct isis_vertex
*parent
)
645 struct isis_vertex
*vertex
;
646 struct listnode
*node
;
647 struct isis_adjacency
*parent_adj
;
649 char buff
[PREFIX2STR_BUFFER
];
652 assert(isis_find_vertex(&spftree
->paths
, id
, vtype
) == NULL
);
653 assert(isis_find_vertex(&spftree
->tents
, id
, vtype
) == NULL
);
654 vertex
= isis_vertex_new(id
, vtype
);
656 vertex
->depth
= depth
;
659 listnode_add(vertex
->parents
, parent
);
662 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
663 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
, parent_adj
))
664 listnode_add(vertex
->Adj_N
, parent_adj
);
666 listnode_add(vertex
->Adj_N
, adj
);
671 "ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
672 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
673 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
674 vertex
->d_N
, listcount(vertex
->Adj_N
));
675 #endif /* EXTREME_DEBUG */
677 isis_vertex_queue_insert(&spftree
->tents
, vertex
);
681 static void isis_spf_add_local(struct isis_spftree
*spftree
,
682 enum vertextype vtype
, void *id
,
683 struct isis_adjacency
*adj
, uint32_t cost
,
684 struct isis_vertex
*parent
)
686 struct isis_vertex
*vertex
;
688 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
692 if (vertex
->d_N
== cost
) {
694 listnode_add(vertex
->Adj_N
, adj
);
696 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
697 remove_excess_adjs(vertex
->Adj_N
);
698 if (parent
&& (listnode_lookup(vertex
->parents
, parent
)
700 listnode_add(vertex
->parents
, parent
);
702 } else if (vertex
->d_N
< cost
) {
705 } else { /* vertex->d_N > cost */
707 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
708 isis_vertex_del(vertex
);
712 isis_spf_add2tent(spftree
, vtype
, id
, cost
, 1, adj
, parent
);
716 static void process_N(struct isis_spftree
*spftree
, enum vertextype vtype
,
717 void *id
, uint32_t dist
, uint16_t depth
,
718 struct isis_vertex
*parent
)
720 struct isis_vertex
*vertex
;
722 char buff
[PREFIX2STR_BUFFER
];
725 assert(spftree
&& parent
);
728 if (vtype
>= VTYPE_IPREACH_INTERNAL
) {
734 /* RFC3787 section 5.1 */
735 if (spftree
->area
->newmetric
== 1) {
736 if (dist
> MAX_WIDE_PATH_METRIC
)
740 else if (spftree
->area
->oldmetric
== 1) {
741 if (dist
> MAX_NARROW_PATH_METRIC
)
746 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
750 "ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
751 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
752 vid2string(vertex
, buff
, sizeof(buff
)), dist
);
753 #endif /* EXTREME_DEBUG */
754 assert(dist
>= vertex
->d_N
);
758 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
764 "ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
765 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
766 vid2string(vertex
, buff
, sizeof(buff
)), dist
,
767 (parent
? print_sys_hostname(parent
->N
.id
) : "null"),
768 (parent
? listcount(parent
->Adj_N
) : 0));
769 #endif /* EXTREME_DEBUG */
770 if (vertex
->d_N
== dist
) {
771 struct listnode
*node
;
772 struct isis_adjacency
*parent_adj
;
773 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
,
775 if (listnode_lookup(vertex
->Adj_N
, parent_adj
)
777 listnode_add(vertex
->Adj_N
, parent_adj
);
779 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
780 remove_excess_adjs(vertex
->Adj_N
);
781 if (listnode_lookup(vertex
->parents
, parent
) == NULL
)
782 listnode_add(vertex
->parents
, parent
);
784 } else if (vertex
->d_N
< dist
) {
788 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
789 isis_vertex_del(vertex
);
794 zlog_debug("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
795 print_sys_hostname(id
), vtype2string(vtype
), dist
,
796 (parent
? print_sys_hostname(parent
->N
.id
) : "null"));
797 #endif /* EXTREME_DEBUG */
799 isis_spf_add2tent(spftree
, vtype
, id
, dist
, depth
, NULL
, parent
);
806 static int isis_spf_process_lsp(struct isis_spftree
*spftree
,
807 struct isis_lsp
*lsp
, uint32_t cost
,
808 uint16_t depth
, uint8_t *root_sysid
,
809 struct isis_vertex
*parent
)
811 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
812 struct listnode
*fragnode
= NULL
;
814 enum vertextype vtype
;
815 static const uint8_t null_sysid
[ISIS_SYS_ID_LEN
];
816 struct isis_mt_router_info
*mt_router_info
= NULL
;
821 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
)
822 mt_router_info
= isis_tlvs_lookup_mt_router_info(lsp
->tlvs
,
825 if (!pseudo_lsp
&& (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
826 && !speaks(lsp
->tlvs
->protocols_supported
.protocols
,
827 lsp
->tlvs
->protocols_supported
.count
,
832 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
833 bool no_overload
= (pseudo_lsp
834 || (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
835 && !ISIS_MASK_LSP_OL_BIT(lsp
->hdr
.lsp_bits
))
836 || (mt_router_info
&& !mt_router_info
->overload
));
839 if (lsp
->hdr
.seqno
== 0) {
841 "isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
846 zlog_debug("ISIS-Spf: process_lsp %s",
847 print_sys_hostname(lsp
->hdr
.lsp_id
));
848 #endif /* EXTREME_DEBUG */
851 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
852 struct isis_oldstyle_reach
*r
;
853 for (r
= (struct isis_oldstyle_reach
*)
854 lsp
->tlvs
->oldstyle_reach
.head
;
857 /* Two way connectivity */
858 if (!memcmp(r
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
861 && !memcmp(r
->id
, null_sysid
,
864 dist
= cost
+ r
->metric
;
868 : VTYPE_NONPSEUDO_IS
,
869 (void *)r
->id
, dist
, depth
+ 1,
874 struct isis_item_list
*te_neighs
= NULL
;
875 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
876 te_neighs
= &lsp
->tlvs
->extended_reach
;
878 te_neighs
= isis_lookup_mt_items(&lsp
->tlvs
->mt_reach
,
881 struct isis_extended_reach
*er
;
883 ? (struct isis_extended_reach
*)
887 if (!memcmp(er
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
890 && !memcmp(er
->id
, null_sysid
, ISIS_SYS_ID_LEN
))
892 dist
= cost
+ er
->metric
;
894 LSP_PSEUDO_ID(er
->id
) ? VTYPE_PSEUDO_TE_IS
895 : VTYPE_NONPSEUDO_TE_IS
,
896 (void *)er
->id
, dist
, depth
+ 1, parent
);
900 if (!pseudo_lsp
&& spftree
->family
== AF_INET
901 && spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
902 struct isis_item_list
*reachs
[] = {
903 &lsp
->tlvs
->oldstyle_ip_reach
,
904 &lsp
->tlvs
->oldstyle_ip_reach_ext
};
906 for (unsigned int i
= 0; i
< array_size(reachs
); i
++) {
907 vtype
= i
? VTYPE_IPREACH_EXTERNAL
908 : VTYPE_IPREACH_INTERNAL
;
910 struct isis_oldstyle_ip_reach
*r
;
911 for (r
= (struct isis_oldstyle_ip_reach
*)reachs
[i
]
914 dist
= cost
+ r
->metric
;
915 process_N(spftree
, vtype
, (void *)&r
->prefix
,
916 dist
, depth
+ 1, parent
);
921 if (!pseudo_lsp
&& spftree
->family
== AF_INET
) {
922 struct isis_item_list
*ipv4_reachs
;
923 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
924 ipv4_reachs
= &lsp
->tlvs
->extended_ip_reach
;
926 ipv4_reachs
= isis_lookup_mt_items(
927 &lsp
->tlvs
->mt_ip_reach
, spftree
->mtid
);
929 struct isis_extended_ip_reach
*r
;
931 ? (struct isis_extended_ip_reach
*)
935 dist
= cost
+ r
->metric
;
936 process_N(spftree
, VTYPE_IPREACH_TE
, (void *)&r
->prefix
,
937 dist
, depth
+ 1, parent
);
941 if (!pseudo_lsp
&& spftree
->family
== AF_INET6
) {
942 struct isis_item_list
*ipv6_reachs
;
943 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
944 ipv6_reachs
= &lsp
->tlvs
->ipv6_reach
;
946 ipv6_reachs
= isis_lookup_mt_items(
947 &lsp
->tlvs
->mt_ipv6_reach
, spftree
->mtid
);
949 struct isis_ipv6_reach
*r
;
951 ? (struct isis_ipv6_reach
*)ipv6_reachs
->head
954 dist
= cost
+ r
->metric
;
955 vtype
= r
->external
? VTYPE_IP6REACH_EXTERNAL
956 : VTYPE_IP6REACH_INTERNAL
;
957 process_N(spftree
, vtype
, (void *)&r
->prefix
, dist
,
962 if (fragnode
== NULL
)
963 fragnode
= listhead(lsp
->lspu
.frags
);
965 fragnode
= listnextnode(fragnode
);
968 lsp
= listgetdata(fragnode
);
975 static int isis_spf_preload_tent(struct isis_spftree
*spftree
,
977 struct isis_vertex
*parent
)
979 struct isis_circuit
*circuit
;
980 struct listnode
*cnode
, *anode
, *ipnode
;
981 struct isis_adjacency
*adj
;
982 struct isis_lsp
*lsp
;
983 struct list
*adj_list
;
985 struct prefix_ipv4
*ipv4
;
986 struct prefix prefix
;
987 int retval
= ISIS_OK
;
988 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
989 static uint8_t null_lsp_id
[ISIS_SYS_ID_LEN
+ 2];
990 struct prefix_ipv6
*ipv6
;
991 struct isis_circuit_mt_setting
*circuit_mt
;
993 for (ALL_LIST_ELEMENTS_RO(spftree
->area
->circuit_list
, cnode
,
995 circuit_mt
= circuit_lookup_mt_setting(circuit
, spftree
->mtid
);
996 if (circuit_mt
&& !circuit_mt
->enabled
)
998 if (circuit
->state
!= C_STATE_UP
)
1000 if (!(circuit
->is_type
& spftree
->level
))
1002 if (spftree
->family
== AF_INET
&& !circuit
->ip_router
)
1004 if (spftree
->family
== AF_INET6
&& !circuit
->ipv6_router
)
1007 * Add IP(v6) addresses of this circuit
1009 if (spftree
->family
== AF_INET
) {
1010 prefix
.family
= AF_INET
;
1011 for (ALL_LIST_ELEMENTS_RO(circuit
->ip_addrs
, ipnode
,
1013 prefix
.u
.prefix4
= ipv4
->prefix
;
1014 prefix
.prefixlen
= ipv4
->prefixlen
;
1015 apply_mask(&prefix
);
1016 isis_spf_add_local(spftree
,
1017 VTYPE_IPREACH_INTERNAL
,
1018 &prefix
, NULL
, 0, parent
);
1021 if (spftree
->family
== AF_INET6
) {
1022 prefix
.family
= AF_INET6
;
1023 for (ALL_LIST_ELEMENTS_RO(circuit
->ipv6_non_link
,
1025 prefix
.prefixlen
= ipv6
->prefixlen
;
1026 prefix
.u
.prefix6
= ipv6
->prefix
;
1027 apply_mask(&prefix
);
1028 isis_spf_add_local(spftree
,
1029 VTYPE_IP6REACH_INTERNAL
,
1030 &prefix
, NULL
, 0, parent
);
1033 if (circuit
->circ_type
== CIRCUIT_T_BROADCAST
) {
1035 * Add the adjacencies
1037 adj_list
= list_new();
1038 adjdb
= circuit
->u
.bc
.adjdb
[spftree
->level
- 1];
1039 isis_adj_build_up_list(adjdb
, adj_list
);
1040 if (listcount(adj_list
) == 0) {
1041 list_delete_and_null(&adj_list
);
1042 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1044 "ISIS-Spf: no L%d adjacencies on circuit %s",
1046 circuit
->interface
->name
);
1049 for (ALL_LIST_ELEMENTS_RO(adj_list
, anode
, adj
)) {
1050 if (!adj_has_mt(adj
, spftree
->mtid
))
1052 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
1053 && !speaks(adj
->nlpids
.nlpids
,
1057 switch (adj
->sys_type
) {
1058 case ISIS_SYSTYPE_ES
:
1059 memcpy(lsp_id
, adj
->sysid
,
1061 LSP_PSEUDO_ID(lsp_id
) = 0;
1063 spftree
, VTYPE_ES
, lsp_id
, adj
,
1065 [spftree
->level
- 1],
1068 case ISIS_SYSTYPE_IS
:
1069 case ISIS_SYSTYPE_L1_IS
:
1070 case ISIS_SYSTYPE_L2_IS
:
1071 memcpy(lsp_id
, adj
->sysid
,
1073 LSP_PSEUDO_ID(lsp_id
) = 0;
1074 LSP_FRAGMENT(lsp_id
) = 0;
1077 spftree
->area
->oldmetric
1078 ? VTYPE_NONPSEUDO_IS
1079 : VTYPE_NONPSEUDO_TE_IS
,
1082 [spftree
->level
- 1],
1087 ->lspdb
[spftree
->level
1090 || lsp
->hdr
.rem_lifetime
== 0)
1092 "ISIS-Spf: No LSP %s found for IS adjacency "
1093 "L%d on %s (ID %u)",
1094 rawlspid_print(lsp_id
),
1096 circuit
->interface
->name
,
1097 circuit
->circuit_id
);
1099 case ISIS_SYSTYPE_UNKNOWN
:
1102 "isis_spf_preload_tent unknow adj type");
1105 list_delete_and_null(&adj_list
);
1107 * Add the pseudonode
1109 if (spftree
->level
== 1)
1110 memcpy(lsp_id
, circuit
->u
.bc
.l1_desig_is
,
1111 ISIS_SYS_ID_LEN
+ 1);
1113 memcpy(lsp_id
, circuit
->u
.bc
.l2_desig_is
,
1114 ISIS_SYS_ID_LEN
+ 1);
1115 /* can happen during DR reboot */
1116 if (memcmp(lsp_id
, null_lsp_id
, ISIS_SYS_ID_LEN
+ 1)
1118 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1120 "ISIS-Spf: No L%d DR on %s (ID %d)",
1122 circuit
->interface
->name
,
1123 circuit
->circuit_id
);
1126 adj
= isis_adj_lookup(lsp_id
, adjdb
);
1127 /* if no adj, we are the dis or error */
1128 if (!adj
&& !circuit
->u
.bc
.is_dr
[spftree
->level
- 1]) {
1130 "ISIS-Spf: No adjacency found from root "
1131 "to L%d DR %s on %s (ID %d)",
1132 spftree
->level
, rawlspid_print(lsp_id
),
1133 circuit
->interface
->name
,
1134 circuit
->circuit_id
);
1139 spftree
->area
->lspdb
[spftree
->level
- 1]);
1140 if (lsp
== NULL
|| lsp
->hdr
.rem_lifetime
== 0) {
1142 "ISIS-Spf: No lsp (%p) found from root "
1143 "to L%d DR %s on %s (ID %d)",
1144 (void *)lsp
, spftree
->level
,
1145 rawlspid_print(lsp_id
),
1146 circuit
->interface
->name
,
1147 circuit
->circuit_id
);
1150 isis_spf_process_lsp(
1152 circuit
->te_metric
[spftree
->level
- 1], 0,
1153 root_sysid
, parent
);
1154 } else if (circuit
->circ_type
== CIRCUIT_T_P2P
) {
1155 adj
= circuit
->u
.p2p
.neighbor
;
1156 if (!adj
|| adj
->adj_state
!= ISIS_ADJ_UP
)
1158 if (!adj_has_mt(adj
, spftree
->mtid
))
1160 switch (adj
->sys_type
) {
1161 case ISIS_SYSTYPE_ES
:
1162 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1163 LSP_PSEUDO_ID(lsp_id
) = 0;
1165 spftree
, VTYPE_ES
, lsp_id
, adj
,
1166 circuit
->te_metric
[spftree
->level
- 1],
1169 case ISIS_SYSTYPE_IS
:
1170 case ISIS_SYSTYPE_L1_IS
:
1171 case ISIS_SYSTYPE_L2_IS
:
1172 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1173 LSP_PSEUDO_ID(lsp_id
) = 0;
1174 LSP_FRAGMENT(lsp_id
) = 0;
1175 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
1176 || speaks(adj
->nlpids
.nlpids
,
1181 spftree
->area
->oldmetric
1182 ? VTYPE_NONPSEUDO_IS
1183 : VTYPE_NONPSEUDO_TE_IS
,
1186 [spftree
->level
- 1],
1189 case ISIS_SYSTYPE_UNKNOWN
:
1192 "isis_spf_preload_tent unknown adj type");
1195 } else if (circuit
->circ_type
== CIRCUIT_T_LOOPBACK
) {
1198 zlog_warn("isis_spf_preload_tent unsupported media");
1199 retval
= ISIS_WARNING
;
1207 * The parent(s) for vertex is set when added to TENT list
1208 * now we just put the child pointer(s) in place
1210 static void add_to_paths(struct isis_spftree
*spftree
,
1211 struct isis_vertex
*vertex
)
1213 char buff
[PREFIX2STR_BUFFER
];
1215 if (isis_find_vertex(&spftree
->paths
, &vertex
->N
, vertex
->type
))
1217 isis_vertex_queue_append(&spftree
->paths
, vertex
);
1219 #ifdef EXTREME_DEBUG
1220 zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
1221 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
1222 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
1224 #endif /* EXTREME_DEBUG */
1226 if (VTYPE_IP(vertex
->type
)) {
1227 if (listcount(vertex
->Adj_N
) > 0)
1228 isis_route_create((struct prefix
*)&vertex
->N
.prefix
,
1229 vertex
->d_N
, vertex
->depth
,
1230 vertex
->Adj_N
, spftree
->area
,
1232 else if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1234 "ISIS-Spf: no adjacencies do not install route for "
1235 "%s depth %d dist %d",
1236 vid2string(vertex
, buff
, sizeof(buff
)),
1237 vertex
->depth
, vertex
->d_N
);
1243 static void init_spt(struct isis_spftree
*spftree
, int mtid
, int level
,
1246 isis_vertex_queue_clear(&spftree
->tents
);
1247 isis_vertex_queue_clear(&spftree
->paths
);
1249 spftree
->mtid
= mtid
;
1250 spftree
->level
= level
;
1251 spftree
->family
= family
;
1255 static int isis_run_spf(struct isis_area
*area
, int level
, int family
,
1256 uint8_t *sysid
, struct timeval
*nowtv
)
1258 int retval
= ISIS_OK
;
1259 struct isis_vertex
*vertex
;
1260 struct isis_vertex
*root_vertex
;
1261 struct isis_spftree
*spftree
= NULL
;
1262 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1263 struct isis_lsp
*lsp
;
1264 struct route_table
*table
= NULL
;
1265 struct timeval time_now
;
1266 unsigned long long start_time
, end_time
;
1269 /* Get time that can't roll backwards. */
1270 start_time
= nowtv
->tv_sec
;
1271 start_time
= (start_time
* 1000000) + nowtv
->tv_usec
;
1273 if (family
== AF_INET
)
1274 spftree
= area
->spftree
[level
- 1];
1275 else if (family
== AF_INET6
)
1276 spftree
= area
->spftree6
[level
- 1];
1280 /* Make all routes in current route table inactive. */
1281 if (family
== AF_INET
)
1282 table
= area
->route_table
[level
- 1];
1283 else if (family
== AF_INET6
)
1284 table
= area
->route_table6
[level
- 1];
1286 isis_route_invalidate_table(area
, table
);
1288 /* We only support ipv4-unicast and ipv6-unicast as topologies for now
1290 if (family
== AF_INET6
)
1291 mtid
= isis_area_ipv6_topology(area
);
1293 mtid
= ISIS_MT_IPV4_UNICAST
;
1298 init_spt(spftree
, mtid
, level
, family
);
1300 root_vertex
= isis_spf_add_root(spftree
, sysid
);
1302 retval
= isis_spf_preload_tent(spftree
, sysid
, root_vertex
);
1303 if (retval
!= ISIS_OK
) {
1304 zlog_warn("ISIS-Spf: failed to load TENT SPF-root:%s",
1305 print_sys_hostname(sysid
));
1312 if (!isis_vertex_queue_count(&spftree
->tents
)
1313 && (isis
->debugs
& DEBUG_SPF_EVENTS
)) {
1314 zlog_warn("ISIS-Spf: TENT is empty SPF-root:%s",
1315 print_sys_hostname(sysid
));
1318 while (isis_vertex_queue_count(&spftree
->tents
)) {
1319 vertex
= isis_vertex_queue_pop(&spftree
->tents
);
1321 #ifdef EXTREME_DEBUG
1323 "ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
1324 print_sys_hostname(vertex
->N
.id
),
1325 vtype2string(vertex
->type
), vertex
->depth
, vertex
->d_N
);
1326 #endif /* EXTREME_DEBUG */
1328 add_to_paths(spftree
, vertex
);
1329 if (VTYPE_IS(vertex
->type
)) {
1330 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
1331 LSP_FRAGMENT(lsp_id
) = 0;
1332 lsp
= lsp_search(lsp_id
, area
->lspdb
[level
- 1]);
1333 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0) {
1334 isis_spf_process_lsp(spftree
, lsp
, vertex
->d_N
,
1335 vertex
->depth
, sysid
,
1338 zlog_warn("ISIS-Spf: No LSP found for %s",
1339 rawlspid_print(lsp_id
));
1345 isis_route_validate(area
);
1346 spftree
->runcount
++;
1347 spftree
->last_run_timestamp
= time(NULL
);
1348 spftree
->last_run_monotime
= monotime(&time_now
);
1349 end_time
= time_now
.tv_sec
;
1350 end_time
= (end_time
* 1000000) + time_now
.tv_usec
;
1351 spftree
->last_run_duration
= end_time
- start_time
;
1356 static int isis_run_spf_cb(struct thread
*thread
)
1358 struct isis_spf_run
*run
= THREAD_ARG(thread
);
1359 struct isis_area
*area
= run
->area
;
1360 int level
= run
->level
;
1361 int retval
= ISIS_OK
;
1363 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1364 area
->spf_timer
[level
- 1] = NULL
;
1366 if (!(area
->is_type
& level
)) {
1367 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1368 zlog_warn("ISIS-SPF (%s) area does not share level",
1370 return ISIS_WARNING
;
1373 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1374 zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
1375 area
->area_tag
, level
);
1377 if (area
->ip_circuits
)
1378 retval
= isis_run_spf(area
, level
, AF_INET
, isis
->sysid
,
1380 if (area
->ipv6_circuits
)
1381 retval
= isis_run_spf(area
, level
, AF_INET6
, isis
->sysid
,
1387 static struct isis_spf_run
*isis_run_spf_arg(struct isis_area
*area
, int level
)
1389 struct isis_spf_run
*run
= XMALLOC(MTYPE_ISIS_SPF_RUN
, sizeof(*run
));
1397 int isis_spf_schedule(struct isis_area
*area
, int level
)
1399 struct isis_spftree
*spftree
= area
->spftree
[level
- 1];
1400 time_t now
= monotime(NULL
);
1401 int diff
= now
- spftree
->last_run_monotime
;
1404 assert(area
->is_type
& level
);
1406 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1408 "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
1409 area
->area_tag
, level
, diff
);
1411 if (area
->spf_delay_ietf
[level
- 1]) {
1412 /* Need to call schedule function also if spf delay is running
1414 * restart holdoff timer - compare
1415 * draft-ietf-rtgwg-backoff-algo-04 */
1417 spf_backoff_schedule(area
->spf_delay_ietf
[level
- 1]);
1418 if (area
->spf_timer
[level
- 1])
1421 thread_add_timer_msec(master
, isis_run_spf_cb
,
1422 isis_run_spf_arg(area
, level
), delay
,
1423 &area
->spf_timer
[level
- 1]);
1427 if (area
->spf_timer
[level
- 1])
1430 /* wait configured min_spf_interval before doing the SPF */
1432 if (diff
>= area
->min_spf_interval
[level
- 1]) {
1433 /* Last run is more than min interval ago, schedule immediate run */
1436 timer
= area
->min_spf_interval
[level
- 1] - diff
;
1439 thread_add_timer(master
, isis_run_spf_cb
, isis_run_spf_arg(area
, level
),
1440 timer
, &area
->spf_timer
[level
- 1]);
1442 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1443 zlog_debug("ISIS-Spf (%s) L%d SPF scheduled %ld sec from now",
1444 area
->area_tag
, level
, timer
);
1449 static void isis_print_paths(struct vty
*vty
, struct isis_vertex_queue
*queue
,
1450 uint8_t *root_sysid
)
1452 struct listnode
*node
;
1453 struct isis_vertex
*vertex
;
1454 char buff
[PREFIX2STR_BUFFER
];
1457 "Vertex Type Metric Next-Hop Interface Parent\n");
1459 for (ALL_QUEUE_ELEMENTS_RO(queue
, node
, vertex
)) {
1460 if (memcmp(vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
1461 vty_out(vty
, "%-20s %-12s %-6s",
1462 print_sys_hostname(root_sysid
), "", "");
1463 vty_out(vty
, "%-30s\n", "");
1468 struct listnode
*anode
= listhead(vertex
->Adj_N
);
1469 struct listnode
*pnode
= listhead(vertex
->parents
);
1470 struct isis_adjacency
*adj
;
1471 struct isis_vertex
*pvertex
;
1473 vty_out(vty
, "%-20s %-12s %-6u ",
1474 vid2string(vertex
, buff
, sizeof(buff
)),
1475 vtype2string(vertex
->type
), vertex
->d_N
);
1476 for (unsigned int i
= 0; i
< MAX(listcount(vertex
->Adj_N
),
1477 listcount(vertex
->parents
));
1480 adj
= listgetdata(anode
);
1481 anode
= anode
->next
;
1487 pvertex
= listgetdata(pnode
);
1488 pnode
= pnode
->next
;
1495 vty_out(vty
, "%-20s %-12s %-6s ", "", "", "");
1499 vty_out(vty
, "%-20s %-9s ",
1500 print_sys_hostname(adj
->sysid
),
1501 adj
->circuit
->interface
->name
);
1506 vty_out(vty
, "%-20s %-9s ", "", "");
1508 vty_out(vty
, "%s(%d)",
1509 vid2string(pvertex
, buff
, sizeof(buff
)),
1519 DEFUN (show_isis_topology
,
1520 show_isis_topology_cmd
,
1521 "show isis topology [<level-1|level-2>]",
1523 "IS-IS information\n"
1524 "IS-IS paths to Intermediate Systems\n"
1525 "Paths to all level-1 routers in the area\n"
1526 "Paths to all level-2 routers in the domain\n")
1529 struct listnode
*node
;
1530 struct isis_area
*area
;
1533 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
1534 else if (strmatch(argv
[3]->text
, "level-1"))
1535 levels
= ISIS_LEVEL1
;
1537 levels
= ISIS_LEVEL2
;
1539 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1542 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
1543 vty_out(vty
, "Area %s:\n",
1544 area
->area_tag
? area
->area_tag
: "null");
1546 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
1547 if ((level
& levels
) == 0)
1550 if (area
->ip_circuits
> 0 && area
->spftree
[level
- 1]
1551 && isis_vertex_queue_count(&area
->spftree
[level
- 1]->paths
) > 0) {
1553 "IS-IS paths to level-%d routers that speak IP\n",
1556 vty
, &area
->spftree
[level
- 1]->paths
,
1560 if (area
->ipv6_circuits
> 0 && area
->spftree6
[level
- 1]
1561 && isis_vertex_queue_count(&area
->spftree6
[level
- 1]->paths
) > 0) {
1563 "IS-IS paths to level-%d routers that speak IPv6\n",
1566 vty
, &area
->spftree6
[level
- 1]->paths
,
1578 void isis_spf_cmds_init()
1580 install_element(VIEW_NODE
, &show_isis_topology_cmd
);
1583 void isis_spf_print(struct isis_spftree
*spftree
, struct vty
*vty
)
1585 vty_out(vty
, " last run elapsed : ");
1586 vty_out_timestr(vty
, spftree
->last_run_timestamp
);
1589 vty_out(vty
, " last run duration : %u usec\n",
1590 (uint32_t)spftree
->last_run_duration
);
1592 vty_out(vty
, " run count : %u\n", spftree
->runcount
);