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)}>
84 u_char id
[ISIS_SYS_ID_LEN
+ 1];
88 u_int32_t d_N
; /* d(N) Distance from this IS */
89 u_int16_t depth
; /* The depth in the imaginary tree */
90 struct list
*Adj_N
; /* {Adj(N)} next hop or neighbor list */
91 struct list
*parents
; /* list of parents for ECMP */
92 uint64_t insert_counter
;
95 /* Vertex Queue and associated functions */
97 struct isis_vertex_queue
{
99 struct skiplist
*slist
;
103 uint64_t insert_counter
;
106 static unsigned isis_vertex_queue_hash_key(void *vp
)
108 struct isis_vertex
*vertex
= vp
;
110 if (VTYPE_IP(vertex
->type
))
111 return prefix_hash_key(&vertex
->N
.prefix
);
113 return jhash(vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1, 0x55aa5a5a);
116 static int isis_vertex_queue_hash_cmp(const void *a
, const void *b
)
118 const struct isis_vertex
*va
= a
, *vb
= b
;
120 if (va
->type
!= vb
->type
)
123 if (VTYPE_IP(va
->type
))
124 return prefix_cmp(&va
->N
.prefix
, &vb
->N
.prefix
) == 0;
126 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
130 * Compares vertizes for sorting in the TENT list. Returns true
131 * if candidate should be considered before current, false otherwise.
133 static int isis_vertex_queue_tent_cmp(void *a
, void *b
)
135 struct isis_vertex
*va
= a
;
136 struct isis_vertex
*vb
= b
;
138 if (va
->d_N
< vb
->d_N
)
141 if (va
->d_N
> vb
->d_N
)
144 if (va
->type
< vb
->type
)
147 if (va
->type
> vb
->type
)
150 if (va
->insert_counter
< vb
->insert_counter
)
153 if (va
->insert_counter
> vb
->insert_counter
)
159 static struct skiplist
*isis_vertex_queue_skiplist(void)
161 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
164 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
, 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
,
178 static void isis_vertex_del(struct isis_vertex
*vertex
);
180 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
182 hash_clean(queue
->hash
, NULL
);
184 if (queue
->insert_counter
) {
185 struct isis_vertex
*vertex
;
186 while (0 == skiplist_first(queue
->l
.slist
, NULL
, (void**)&vertex
)) {
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
*isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
246 assert(queue
->insert_counter
);
248 struct isis_vertex
*rv
;
250 if (skiplist_first(queue
->l
.slist
, NULL
, (void**)&rv
))
253 skiplist_delete_first(queue
->l
.slist
);
254 hash_release(queue
->hash
, rv
);
259 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
260 struct isis_vertex
*vertex
)
262 assert(queue
->insert_counter
);
264 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
265 hash_release(queue
->hash
, vertex
);
268 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
269 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
272 /* End of vertex queue definitions */
274 struct isis_spftree
{
275 struct isis_vertex_queue paths
; /* the SPT */
276 struct isis_vertex_queue tents
; /* TENT */
277 struct isis_area
*area
; /* back pointer to area */
278 unsigned int runcount
; /* number of runs since uptime */
279 time_t last_run_timestamp
; /* last run timestamp as wall time for display */
280 time_t last_run_monotime
; /* last run as monotime for scheduling */
281 time_t last_run_duration
; /* last run duration in msec */
290 * supports the given af ?
292 static bool speaks(uint8_t *protocols
, uint8_t count
, int family
)
294 for (uint8_t i
= 0; i
< count
; i
++) {
295 if (family
== AF_INET
&& protocols
[i
] == NLPID_IP
)
297 if (family
== AF_INET6
&& protocols
[i
] == NLPID_IPV6
)
303 struct isis_spf_run
{
304 struct isis_area
*area
;
309 static void remove_excess_adjs(struct list
*adjs
)
311 struct listnode
*node
, *excess
= NULL
;
312 struct isis_adjacency
*adj
, *candidate
= NULL
;
315 for (ALL_LIST_ELEMENTS_RO(adjs
, node
, adj
)) {
318 candidate
= listgetdata(excess
);
320 if (candidate
->sys_type
< adj
->sys_type
) {
324 if (candidate
->sys_type
> adj
->sys_type
)
327 comp
= memcmp(candidate
->sysid
, adj
->sysid
, ISIS_SYS_ID_LEN
);
335 if (candidate
->circuit
->circuit_id
> adj
->circuit
->circuit_id
) {
340 if (candidate
->circuit
->circuit_id
< adj
->circuit
->circuit_id
)
343 comp
= memcmp(candidate
->snpa
, adj
->snpa
, ETH_ALEN
);
350 list_delete_node(adjs
, excess
);
355 static const char *vtype2string(enum vertextype vtype
)
358 case VTYPE_PSEUDO_IS
:
361 case VTYPE_PSEUDO_TE_IS
:
362 return "pseudo_TE-IS";
364 case VTYPE_NONPSEUDO_IS
:
367 case VTYPE_NONPSEUDO_TE_IS
:
373 case VTYPE_IPREACH_INTERNAL
:
374 return "IP internal";
376 case VTYPE_IPREACH_EXTERNAL
:
377 return "IP external";
379 case VTYPE_IPREACH_TE
:
382 case VTYPE_IP6REACH_INTERNAL
:
383 return "IP6 internal";
385 case VTYPE_IP6REACH_EXTERNAL
:
386 return "IP6 external";
391 return NULL
; /* Not reached */
394 static const char *vid2string(struct isis_vertex
*vertex
, char *buff
, int size
)
396 if (VTYPE_IS(vertex
->type
) || VTYPE_ES(vertex
->type
)) {
397 return print_sys_hostname(vertex
->N
.id
);
400 if (VTYPE_IP(vertex
->type
)) {
401 prefix2str((struct prefix
*)&vertex
->N
.prefix
, buff
, size
);
408 static void isis_vertex_id_init(struct isis_vertex
*vertex
, void *id
, enum vertextype vtype
)
410 vertex
->type
= vtype
;
412 if (VTYPE_IS(vtype
) || VTYPE_ES(vtype
)) {
413 memcpy(vertex
->N
.id
, (u_char
*)id
, ISIS_SYS_ID_LEN
+ 1);
414 } else if (VTYPE_IP(vtype
)) {
415 memcpy(&vertex
->N
.prefix
, (struct prefix
*)id
,
416 sizeof(struct prefix
));
422 static struct isis_vertex
*isis_vertex_new(void *id
, enum vertextype vtype
)
424 struct isis_vertex
*vertex
;
426 vertex
= XCALLOC(MTYPE_ISIS_VERTEX
, sizeof(struct isis_vertex
));
428 isis_vertex_id_init(vertex
, id
, vtype
);
430 vertex
->Adj_N
= list_new();
431 vertex
->parents
= list_new();
436 static void isis_vertex_del(struct isis_vertex
*vertex
)
438 list_delete_and_null(&vertex
->Adj_N
);
439 list_delete_and_null(&vertex
->parents
);
441 memset(vertex
, 0, sizeof(struct isis_vertex
));
442 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
447 static void isis_vertex_adj_del(struct isis_vertex
*vertex
,
448 struct isis_adjacency
*adj
)
450 struct listnode
*node
, *nextnode
;
453 for (node
= listhead(vertex
->Adj_N
); node
; node
= nextnode
) {
454 nextnode
= listnextnode(node
);
455 if (listgetdata(node
) == adj
)
456 list_delete_node(vertex
->Adj_N
, node
);
461 struct isis_spftree
*isis_spftree_new(struct isis_area
*area
)
463 struct isis_spftree
*tree
;
465 tree
= XCALLOC(MTYPE_ISIS_SPFTREE
, sizeof(struct isis_spftree
));
467 zlog_err("ISIS-Spf: isis_spftree_new Out of memory!");
471 isis_vertex_queue_init(&tree
->tents
, "IS-IS SPF tents", true);
472 isis_vertex_queue_init(&tree
->paths
, "IS-IS SPF paths", false);
474 tree
->last_run_timestamp
= 0;
475 tree
->last_run_monotime
= 0;
476 tree
->last_run_duration
= 0;
481 void isis_spftree_del(struct isis_spftree
*spftree
)
483 isis_vertex_queue_free(&spftree
->tents
);
484 isis_vertex_queue_free(&spftree
->paths
);
485 XFREE(MTYPE_ISIS_SPFTREE
, spftree
);
490 static void isis_spftree_adj_del(struct isis_spftree
*spftree
,
491 struct isis_adjacency
*adj
)
493 struct listnode
*node
;
494 struct isis_vertex
*v
;
497 assert(!isis_vertex_queue_count(&spftree
->tents
));
498 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, v
))
499 isis_vertex_adj_del(v
, adj
);
503 void spftree_area_init(struct isis_area
*area
)
505 if (area
->is_type
& IS_LEVEL_1
) {
506 if (area
->spftree
[0] == NULL
)
507 area
->spftree
[0] = isis_spftree_new(area
);
508 if (area
->spftree6
[0] == NULL
)
509 area
->spftree6
[0] = isis_spftree_new(area
);
512 if (area
->is_type
& IS_LEVEL_2
) {
513 if (area
->spftree
[1] == NULL
)
514 area
->spftree
[1] = isis_spftree_new(area
);
515 if (area
->spftree6
[1] == NULL
)
516 area
->spftree6
[1] = isis_spftree_new(area
);
522 void spftree_area_del(struct isis_area
*area
)
524 if (area
->is_type
& IS_LEVEL_1
) {
525 if (area
->spftree
[0] != NULL
) {
526 isis_spftree_del(area
->spftree
[0]);
527 area
->spftree
[0] = NULL
;
529 if (area
->spftree6
[0]) {
530 isis_spftree_del(area
->spftree6
[0]);
531 area
->spftree6
[0] = NULL
;
535 if (area
->is_type
& IS_LEVEL_2
) {
536 if (area
->spftree
[1] != NULL
) {
537 isis_spftree_del(area
->spftree
[1]);
538 area
->spftree
[1] = NULL
;
540 if (area
->spftree6
[1] != NULL
) {
541 isis_spftree_del(area
->spftree6
[1]);
542 area
->spftree6
[1] = NULL
;
549 void spftree_area_adj_del(struct isis_area
*area
, struct isis_adjacency
*adj
)
551 if (area
->is_type
& IS_LEVEL_1
) {
552 if (area
->spftree
[0] != NULL
)
553 isis_spftree_adj_del(area
->spftree
[0], adj
);
554 if (area
->spftree6
[0] != NULL
)
555 isis_spftree_adj_del(area
->spftree6
[0], adj
);
558 if (area
->is_type
& IS_LEVEL_2
) {
559 if (area
->spftree
[1] != NULL
)
560 isis_spftree_adj_del(area
->spftree
[1], adj
);
561 if (area
->spftree6
[1] != NULL
)
562 isis_spftree_adj_del(area
->spftree6
[1], adj
);
569 * Find the system LSP: returns the LSP in our LSP database
570 * associated with the given system ID.
572 static struct isis_lsp
*isis_root_system_lsp(struct isis_area
*area
, int level
,
575 struct isis_lsp
*lsp
;
576 u_char lspid
[ISIS_SYS_ID_LEN
+ 2];
578 memcpy(lspid
, sysid
, ISIS_SYS_ID_LEN
);
579 LSP_PSEUDO_ID(lspid
) = 0;
580 LSP_FRAGMENT(lspid
) = 0;
581 lsp
= lsp_search(lspid
, area
->lspdb
[level
- 1]);
582 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
588 * Add this IS to the root of SPT
590 static struct isis_vertex
*isis_spf_add_root(struct isis_spftree
*spftree
,
593 struct isis_vertex
*vertex
;
594 struct isis_lsp
*lsp
;
596 char buff
[PREFIX2STR_BUFFER
];
597 #endif /* EXTREME_DEBUG */
598 u_char id
[ISIS_SYS_ID_LEN
+ 1];
600 memcpy(id
, sysid
, ISIS_SYS_ID_LEN
);
601 LSP_PSEUDO_ID(id
) = 0;
603 lsp
= isis_root_system_lsp(spftree
->area
, spftree
->level
, sysid
);
605 zlog_warn("ISIS-Spf: could not find own l%d LSP!",
608 vertex
= isis_vertex_new(id
,
609 spftree
->area
->oldmetric
611 : VTYPE_NONPSEUDO_TE_IS
);
612 isis_vertex_queue_append(&spftree
->paths
, vertex
);
615 zlog_debug("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
616 vtype2string(vertex
->type
),
617 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
619 #endif /* EXTREME_DEBUG */
624 static struct isis_vertex
*isis_find_vertex(struct isis_vertex_queue
*queue
, void *id
,
625 enum vertextype vtype
)
627 struct isis_vertex querier
;
629 isis_vertex_id_init(&querier
, id
, vtype
);
630 return hash_lookup(queue
->hash
, &querier
);
634 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
636 static struct isis_vertex
*isis_spf_add2tent(struct isis_spftree
*spftree
,
637 enum vertextype vtype
, void *id
,
638 uint32_t cost
, int depth
,
639 struct isis_adjacency
*adj
,
640 struct isis_vertex
*parent
)
642 struct isis_vertex
*vertex
;
643 struct listnode
*node
;
644 struct isis_adjacency
*parent_adj
;
646 char buff
[PREFIX2STR_BUFFER
];
649 assert(isis_find_vertex(&spftree
->paths
, id
, vtype
) == NULL
);
650 assert(isis_find_vertex(&spftree
->tents
, id
, vtype
) == NULL
);
651 vertex
= isis_vertex_new(id
, vtype
);
653 vertex
->depth
= depth
;
656 listnode_add(vertex
->parents
, parent
);
659 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
660 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
, parent_adj
))
661 listnode_add(vertex
->Adj_N
, parent_adj
);
663 listnode_add(vertex
->Adj_N
, adj
);
668 "ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
669 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
670 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
671 vertex
->d_N
, listcount(vertex
->Adj_N
));
672 #endif /* EXTREME_DEBUG */
674 isis_vertex_queue_insert(&spftree
->tents
, vertex
);
678 static void isis_spf_add_local(struct isis_spftree
*spftree
,
679 enum vertextype vtype
, void *id
,
680 struct isis_adjacency
*adj
, uint32_t cost
,
681 struct isis_vertex
*parent
)
683 struct isis_vertex
*vertex
;
685 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
689 if (vertex
->d_N
== cost
) {
691 listnode_add(vertex
->Adj_N
, adj
);
693 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
694 remove_excess_adjs(vertex
->Adj_N
);
695 if (parent
&& (listnode_lookup(vertex
->parents
, parent
)
697 listnode_add(vertex
->parents
, parent
);
699 } else if (vertex
->d_N
< cost
) {
702 } else { /* vertex->d_N > cost */
704 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
705 isis_vertex_del(vertex
);
709 isis_spf_add2tent(spftree
, vtype
, id
, cost
, 1, adj
, parent
);
713 static void process_N(struct isis_spftree
*spftree
, enum vertextype vtype
,
714 void *id
, uint32_t dist
, uint16_t depth
,
715 struct isis_vertex
*parent
)
717 struct isis_vertex
*vertex
;
719 char buff
[PREFIX2STR_BUFFER
];
722 assert(spftree
&& parent
);
725 if (vtype
>= VTYPE_IPREACH_INTERNAL
) {
731 /* RFC3787 section 5.1 */
732 if (spftree
->area
->newmetric
== 1) {
733 if (dist
> MAX_WIDE_PATH_METRIC
)
737 else if (spftree
->area
->oldmetric
== 1) {
738 if (dist
> MAX_NARROW_PATH_METRIC
)
743 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
747 "ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
748 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
749 vid2string(vertex
, buff
, sizeof(buff
)), dist
);
750 #endif /* EXTREME_DEBUG */
751 assert(dist
>= vertex
->d_N
);
755 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
761 "ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
762 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
763 vid2string(vertex
, buff
, sizeof(buff
)), dist
,
764 (parent
? print_sys_hostname(parent
->N
.id
) : "null"),
765 (parent
? listcount(parent
->Adj_N
) : 0));
766 #endif /* EXTREME_DEBUG */
767 if (vertex
->d_N
== dist
) {
768 struct listnode
*node
;
769 struct isis_adjacency
*parent_adj
;
770 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
,
772 if (listnode_lookup(vertex
->Adj_N
, parent_adj
)
774 listnode_add(vertex
->Adj_N
, parent_adj
);
776 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
777 remove_excess_adjs(vertex
->Adj_N
);
778 if (listnode_lookup(vertex
->parents
, parent
) == NULL
)
779 listnode_add(vertex
->parents
, parent
);
781 } else if (vertex
->d_N
< dist
) {
785 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
786 isis_vertex_del(vertex
);
791 zlog_debug("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
792 print_sys_hostname(id
), vtype2string(vtype
), dist
,
793 (parent
? print_sys_hostname(parent
->N
.id
) : "null"));
794 #endif /* EXTREME_DEBUG */
796 isis_spf_add2tent(spftree
, vtype
, id
, dist
, depth
, NULL
, parent
);
803 static int isis_spf_process_lsp(struct isis_spftree
*spftree
,
804 struct isis_lsp
*lsp
, uint32_t cost
,
805 uint16_t depth
, u_char
*root_sysid
,
806 struct isis_vertex
*parent
)
808 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
809 struct listnode
*fragnode
= NULL
;
811 enum vertextype vtype
;
812 static const u_char null_sysid
[ISIS_SYS_ID_LEN
];
813 struct isis_mt_router_info
*mt_router_info
= NULL
;
818 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
)
819 mt_router_info
= isis_tlvs_lookup_mt_router_info(lsp
->tlvs
,
822 if (!pseudo_lsp
&& (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
823 && !speaks(lsp
->tlvs
->protocols_supported
.protocols
,
824 lsp
->tlvs
->protocols_supported
.count
,
829 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
830 bool no_overload
= (pseudo_lsp
831 || (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
832 && !ISIS_MASK_LSP_OL_BIT(lsp
->hdr
.lsp_bits
))
833 || (mt_router_info
&& !mt_router_info
->overload
));
836 if (lsp
->hdr
.seqno
== 0) {
838 "isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
843 zlog_debug("ISIS-Spf: process_lsp %s",
844 print_sys_hostname(lsp
->hdr
.lsp_id
));
845 #endif /* EXTREME_DEBUG */
848 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
849 struct isis_oldstyle_reach
*r
;
850 for (r
= (struct isis_oldstyle_reach
*)
851 lsp
->tlvs
->oldstyle_reach
.head
;
854 /* Two way connectivity */
855 if (!memcmp(r
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
858 && !memcmp(r
->id
, null_sysid
,
861 dist
= cost
+ r
->metric
;
865 : VTYPE_NONPSEUDO_IS
,
866 (void *)r
->id
, dist
, depth
+ 1,
871 struct isis_item_list
*te_neighs
= NULL
;
872 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
873 te_neighs
= &lsp
->tlvs
->extended_reach
;
875 te_neighs
= isis_lookup_mt_items(&lsp
->tlvs
->mt_reach
,
878 struct isis_extended_reach
*er
;
880 ? (struct isis_extended_reach
*)
884 if (!memcmp(er
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
887 && !memcmp(er
->id
, null_sysid
, ISIS_SYS_ID_LEN
))
889 dist
= cost
+ er
->metric
;
891 LSP_PSEUDO_ID(er
->id
) ? VTYPE_PSEUDO_TE_IS
892 : VTYPE_NONPSEUDO_TE_IS
,
893 (void *)er
->id
, dist
, depth
+ 1, parent
);
897 if (!pseudo_lsp
&& spftree
->family
== AF_INET
898 && spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
899 struct isis_item_list
*reachs
[] = {
900 &lsp
->tlvs
->oldstyle_ip_reach
,
901 &lsp
->tlvs
->oldstyle_ip_reach_ext
};
903 for (unsigned int i
= 0; i
< array_size(reachs
); i
++) {
904 vtype
= i
? VTYPE_IPREACH_EXTERNAL
905 : VTYPE_IPREACH_INTERNAL
;
907 struct isis_oldstyle_ip_reach
*r
;
908 for (r
= (struct isis_oldstyle_ip_reach
*)reachs
[i
]
911 dist
= cost
+ r
->metric
;
912 process_N(spftree
, vtype
, (void *)&r
->prefix
,
913 dist
, depth
+ 1, parent
);
918 if (!pseudo_lsp
&& spftree
->family
== AF_INET
) {
919 struct isis_item_list
*ipv4_reachs
;
920 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
921 ipv4_reachs
= &lsp
->tlvs
->extended_ip_reach
;
923 ipv4_reachs
= isis_lookup_mt_items(
924 &lsp
->tlvs
->mt_ip_reach
, spftree
->mtid
);
926 struct isis_extended_ip_reach
*r
;
928 ? (struct isis_extended_ip_reach
*)
932 dist
= cost
+ r
->metric
;
933 process_N(spftree
, VTYPE_IPREACH_TE
, (void *)&r
->prefix
,
934 dist
, depth
+ 1, parent
);
938 if (!pseudo_lsp
&& spftree
->family
== AF_INET6
) {
939 struct isis_item_list
*ipv6_reachs
;
940 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
941 ipv6_reachs
= &lsp
->tlvs
->ipv6_reach
;
943 ipv6_reachs
= isis_lookup_mt_items(
944 &lsp
->tlvs
->mt_ipv6_reach
, spftree
->mtid
);
946 struct isis_ipv6_reach
*r
;
948 ? (struct isis_ipv6_reach
*)ipv6_reachs
->head
951 dist
= cost
+ r
->metric
;
952 vtype
= r
->external
? VTYPE_IP6REACH_EXTERNAL
953 : VTYPE_IP6REACH_INTERNAL
;
954 process_N(spftree
, vtype
, (void *)&r
->prefix
, dist
,
959 if (fragnode
== NULL
)
960 fragnode
= listhead(lsp
->lspu
.frags
);
962 fragnode
= listnextnode(fragnode
);
965 lsp
= listgetdata(fragnode
);
972 static int isis_spf_preload_tent(struct isis_spftree
*spftree
,
973 u_char
*root_sysid
, struct isis_vertex
*parent
)
975 struct isis_circuit
*circuit
;
976 struct listnode
*cnode
, *anode
, *ipnode
;
977 struct isis_adjacency
*adj
;
978 struct isis_lsp
*lsp
;
979 struct list
*adj_list
;
981 struct prefix_ipv4
*ipv4
;
982 struct prefix prefix
;
983 int retval
= ISIS_OK
;
984 u_char lsp_id
[ISIS_SYS_ID_LEN
+ 2];
985 static u_char null_lsp_id
[ISIS_SYS_ID_LEN
+ 2];
986 struct prefix_ipv6
*ipv6
;
987 struct isis_circuit_mt_setting
*circuit_mt
;
989 for (ALL_LIST_ELEMENTS_RO(spftree
->area
->circuit_list
, cnode
,
991 circuit_mt
= circuit_lookup_mt_setting(circuit
, spftree
->mtid
);
992 if (circuit_mt
&& !circuit_mt
->enabled
)
994 if (circuit
->state
!= C_STATE_UP
)
996 if (!(circuit
->is_type
& spftree
->level
))
998 if (spftree
->family
== AF_INET
&& !circuit
->ip_router
)
1000 if (spftree
->family
== AF_INET6
&& !circuit
->ipv6_router
)
1003 * Add IP(v6) addresses of this circuit
1005 if (spftree
->family
== AF_INET
) {
1006 prefix
.family
= AF_INET
;
1007 for (ALL_LIST_ELEMENTS_RO(circuit
->ip_addrs
, ipnode
,
1009 prefix
.u
.prefix4
= ipv4
->prefix
;
1010 prefix
.prefixlen
= ipv4
->prefixlen
;
1011 apply_mask(&prefix
);
1012 isis_spf_add_local(spftree
,
1013 VTYPE_IPREACH_INTERNAL
,
1014 &prefix
, NULL
, 0, parent
);
1017 if (spftree
->family
== AF_INET6
) {
1018 prefix
.family
= AF_INET6
;
1019 for (ALL_LIST_ELEMENTS_RO(circuit
->ipv6_non_link
,
1021 prefix
.prefixlen
= ipv6
->prefixlen
;
1022 prefix
.u
.prefix6
= ipv6
->prefix
;
1023 apply_mask(&prefix
);
1024 isis_spf_add_local(spftree
,
1025 VTYPE_IP6REACH_INTERNAL
,
1026 &prefix
, NULL
, 0, parent
);
1029 if (circuit
->circ_type
== CIRCUIT_T_BROADCAST
) {
1031 * Add the adjacencies
1033 adj_list
= list_new();
1034 adjdb
= circuit
->u
.bc
.adjdb
[spftree
->level
- 1];
1035 isis_adj_build_up_list(adjdb
, adj_list
);
1036 if (listcount(adj_list
) == 0) {
1037 list_delete_and_null(&adj_list
);
1038 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1040 "ISIS-Spf: no L%d adjacencies on circuit %s",
1042 circuit
->interface
->name
);
1045 for (ALL_LIST_ELEMENTS_RO(adj_list
, anode
, adj
)) {
1046 if (!adj_has_mt(adj
, spftree
->mtid
))
1048 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
1049 && !speaks(adj
->nlpids
.nlpids
,
1053 switch (adj
->sys_type
) {
1054 case ISIS_SYSTYPE_ES
:
1055 memcpy(lsp_id
, adj
->sysid
,
1057 LSP_PSEUDO_ID(lsp_id
) = 0;
1059 spftree
, VTYPE_ES
, lsp_id
, adj
,
1061 [spftree
->level
- 1],
1064 case ISIS_SYSTYPE_IS
:
1065 case ISIS_SYSTYPE_L1_IS
:
1066 case ISIS_SYSTYPE_L2_IS
:
1067 memcpy(lsp_id
, adj
->sysid
,
1069 LSP_PSEUDO_ID(lsp_id
) = 0;
1070 LSP_FRAGMENT(lsp_id
) = 0;
1073 spftree
->area
->oldmetric
1074 ? VTYPE_NONPSEUDO_IS
1075 : VTYPE_NONPSEUDO_TE_IS
,
1078 [spftree
->level
- 1],
1083 ->lspdb
[spftree
->level
1086 || lsp
->hdr
.rem_lifetime
== 0)
1088 "ISIS-Spf: No LSP %s found for IS adjacency "
1089 "L%d on %s (ID %u)",
1090 rawlspid_print(lsp_id
),
1092 circuit
->interface
->name
,
1093 circuit
->circuit_id
);
1095 case ISIS_SYSTYPE_UNKNOWN
:
1098 "isis_spf_preload_tent unknow adj type");
1101 list_delete_and_null(&adj_list
);
1103 * Add the pseudonode
1105 if (spftree
->level
== 1)
1106 memcpy(lsp_id
, circuit
->u
.bc
.l1_desig_is
,
1107 ISIS_SYS_ID_LEN
+ 1);
1109 memcpy(lsp_id
, circuit
->u
.bc
.l2_desig_is
,
1110 ISIS_SYS_ID_LEN
+ 1);
1111 /* can happen during DR reboot */
1112 if (memcmp(lsp_id
, null_lsp_id
, ISIS_SYS_ID_LEN
+ 1)
1114 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1116 "ISIS-Spf: No L%d DR on %s (ID %d)",
1118 circuit
->interface
->name
,
1119 circuit
->circuit_id
);
1122 adj
= isis_adj_lookup(lsp_id
, adjdb
);
1123 /* if no adj, we are the dis or error */
1124 if (!adj
&& !circuit
->u
.bc
.is_dr
[spftree
->level
- 1]) {
1126 "ISIS-Spf: No adjacency found from root "
1127 "to L%d DR %s on %s (ID %d)",
1128 spftree
->level
, rawlspid_print(lsp_id
),
1129 circuit
->interface
->name
,
1130 circuit
->circuit_id
);
1135 spftree
->area
->lspdb
[spftree
->level
- 1]);
1136 if (lsp
== NULL
|| lsp
->hdr
.rem_lifetime
== 0) {
1138 "ISIS-Spf: No lsp (%p) found from root "
1139 "to L%d DR %s on %s (ID %d)",
1140 (void *)lsp
, spftree
->level
,
1141 rawlspid_print(lsp_id
),
1142 circuit
->interface
->name
,
1143 circuit
->circuit_id
);
1146 isis_spf_process_lsp(
1148 circuit
->te_metric
[spftree
->level
- 1], 0,
1149 root_sysid
, parent
);
1150 } else if (circuit
->circ_type
== CIRCUIT_T_P2P
) {
1151 adj
= circuit
->u
.p2p
.neighbor
;
1154 if (!adj_has_mt(adj
, spftree
->mtid
))
1156 switch (adj
->sys_type
) {
1157 case ISIS_SYSTYPE_ES
:
1158 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1159 LSP_PSEUDO_ID(lsp_id
) = 0;
1161 spftree
, VTYPE_ES
, lsp_id
, adj
,
1162 circuit
->te_metric
[spftree
->level
- 1],
1165 case ISIS_SYSTYPE_IS
:
1166 case ISIS_SYSTYPE_L1_IS
:
1167 case ISIS_SYSTYPE_L2_IS
:
1168 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1169 LSP_PSEUDO_ID(lsp_id
) = 0;
1170 LSP_FRAGMENT(lsp_id
) = 0;
1171 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
1172 || speaks(adj
->nlpids
.nlpids
,
1177 spftree
->area
->oldmetric
1178 ? VTYPE_NONPSEUDO_IS
1179 : VTYPE_NONPSEUDO_TE_IS
,
1182 [spftree
->level
- 1],
1185 case ISIS_SYSTYPE_UNKNOWN
:
1188 "isis_spf_preload_tent unknown adj type");
1191 } else if (circuit
->circ_type
== CIRCUIT_T_LOOPBACK
) {
1194 zlog_warn("isis_spf_preload_tent unsupported media");
1195 retval
= ISIS_WARNING
;
1203 * The parent(s) for vertex is set when added to TENT list
1204 * now we just put the child pointer(s) in place
1206 static void add_to_paths(struct isis_spftree
*spftree
,
1207 struct isis_vertex
*vertex
)
1209 char buff
[PREFIX2STR_BUFFER
];
1211 if (isis_find_vertex(&spftree
->paths
, vertex
->N
.id
, vertex
->type
))
1213 isis_vertex_queue_append(&spftree
->paths
, vertex
);
1215 #ifdef EXTREME_DEBUG
1216 zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
1217 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
1218 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
1220 #endif /* EXTREME_DEBUG */
1222 if (VTYPE_IP(vertex
->type
)) {
1223 if (listcount(vertex
->Adj_N
) > 0)
1224 isis_route_create((struct prefix
*)&vertex
->N
.prefix
,
1225 vertex
->d_N
, vertex
->depth
,
1226 vertex
->Adj_N
, spftree
->area
,
1228 else if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1230 "ISIS-Spf: no adjacencies do not install route for "
1231 "%s depth %d dist %d",
1232 vid2string(vertex
, buff
, sizeof(buff
)),
1233 vertex
->depth
, vertex
->d_N
);
1239 static void init_spt(struct isis_spftree
*spftree
, int mtid
, int level
,
1242 isis_vertex_queue_clear(&spftree
->tents
);
1243 isis_vertex_queue_clear(&spftree
->paths
);
1245 spftree
->mtid
= mtid
;
1246 spftree
->level
= level
;
1247 spftree
->family
= family
;
1251 static int isis_run_spf(struct isis_area
*area
, int level
, int family
,
1254 int retval
= ISIS_OK
;
1255 struct isis_vertex
*vertex
;
1256 struct isis_vertex
*root_vertex
;
1257 struct isis_spftree
*spftree
= NULL
;
1258 u_char lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1259 struct isis_lsp
*lsp
;
1260 struct route_table
*table
= NULL
;
1261 struct timeval time_now
;
1262 unsigned long long start_time
, end_time
;
1265 /* Get time that can't roll backwards. */
1266 monotime(&time_now
);
1267 start_time
= time_now
.tv_sec
;
1268 start_time
= (start_time
* 1000000) + time_now
.tv_usec
;
1270 if (family
== AF_INET
)
1271 spftree
= area
->spftree
[level
- 1];
1272 else if (family
== AF_INET6
)
1273 spftree
= area
->spftree6
[level
- 1];
1277 /* Make all routes in current route table inactive. */
1278 if (family
== AF_INET
)
1279 table
= area
->route_table
[level
- 1];
1280 else if (family
== AF_INET6
)
1281 table
= area
->route_table6
[level
- 1];
1283 isis_route_invalidate_table(area
, table
);
1285 /* We only support ipv4-unicast and ipv6-unicast as topologies for now
1287 if (family
== AF_INET6
)
1288 mtid
= isis_area_ipv6_topology(area
);
1290 mtid
= ISIS_MT_IPV4_UNICAST
;
1295 init_spt(spftree
, mtid
, level
, family
);
1297 root_vertex
= isis_spf_add_root(spftree
, sysid
);
1299 retval
= isis_spf_preload_tent(spftree
, sysid
, root_vertex
);
1300 if (retval
!= ISIS_OK
) {
1301 zlog_warn("ISIS-Spf: failed to load TENT SPF-root:%s",
1302 print_sys_hostname(sysid
));
1309 if (!isis_vertex_queue_count(&spftree
->tents
)
1310 && (isis
->debugs
& DEBUG_SPF_EVENTS
)) {
1311 zlog_warn("ISIS-Spf: TENT is empty SPF-root:%s",
1312 print_sys_hostname(sysid
));
1315 while (isis_vertex_queue_count(&spftree
->tents
)) {
1316 vertex
= isis_vertex_queue_pop(&spftree
->tents
);
1318 #ifdef EXTREME_DEBUG
1320 "ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
1321 print_sys_hostname(vertex
->N
.id
),
1322 vtype2string(vertex
->type
), vertex
->depth
, vertex
->d_N
);
1323 #endif /* EXTREME_DEBUG */
1325 add_to_paths(spftree
, vertex
);
1326 if (VTYPE_IS(vertex
->type
)) {
1327 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
1328 LSP_FRAGMENT(lsp_id
) = 0;
1329 lsp
= lsp_search(lsp_id
, area
->lspdb
[level
- 1]);
1330 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0) {
1331 isis_spf_process_lsp(spftree
, lsp
, vertex
->d_N
,
1332 vertex
->depth
, sysid
,
1335 zlog_warn("ISIS-Spf: No LSP found for %s",
1336 rawlspid_print(lsp_id
));
1342 isis_route_validate(area
);
1343 spftree
->runcount
++;
1344 spftree
->last_run_timestamp
= time(NULL
);
1345 spftree
->last_run_monotime
= monotime(&time_now
);
1346 end_time
= time_now
.tv_sec
;
1347 end_time
= (end_time
* 1000000) + time_now
.tv_usec
;
1348 spftree
->last_run_duration
= end_time
- start_time
;
1353 static int isis_run_spf_cb(struct thread
*thread
)
1355 struct isis_spf_run
*run
= THREAD_ARG(thread
);
1356 struct isis_area
*area
= run
->area
;
1357 int level
= run
->level
;
1358 int retval
= ISIS_OK
;
1360 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1361 area
->spf_timer
[level
- 1] = NULL
;
1363 if (!(area
->is_type
& level
)) {
1364 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1365 zlog_warn("ISIS-SPF (%s) area does not share level",
1367 return ISIS_WARNING
;
1370 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1371 zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
1372 area
->area_tag
, level
);
1374 if (area
->ip_circuits
)
1375 retval
= isis_run_spf(area
, level
, AF_INET
, isis
->sysid
);
1376 if (area
->ipv6_circuits
)
1377 retval
= isis_run_spf(area
, level
, AF_INET6
, isis
->sysid
);
1382 static struct isis_spf_run
*isis_run_spf_arg(struct isis_area
*area
, int level
)
1384 struct isis_spf_run
*run
= XMALLOC(MTYPE_ISIS_SPF_RUN
, sizeof(*run
));
1392 int isis_spf_schedule(struct isis_area
*area
, int level
)
1394 struct isis_spftree
*spftree
= area
->spftree
[level
- 1];
1395 time_t now
= monotime(NULL
);
1396 int diff
= now
- spftree
->last_run_monotime
;
1399 assert(area
->is_type
& level
);
1401 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1403 "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
1404 area
->area_tag
, level
, diff
);
1406 if (area
->spf_delay_ietf
[level
- 1]) {
1407 /* Need to call schedule function also if spf delay is running
1409 * restart holdoff timer - compare
1410 * draft-ietf-rtgwg-backoff-algo-04 */
1412 spf_backoff_schedule(area
->spf_delay_ietf
[level
- 1]);
1413 if (area
->spf_timer
[level
- 1])
1416 thread_add_timer_msec(master
, isis_run_spf_cb
,
1417 isis_run_spf_arg(area
, level
), delay
,
1418 &area
->spf_timer
[level
- 1]);
1422 if (area
->spf_timer
[level
- 1])
1425 /* wait configured min_spf_interval before doing the SPF */
1427 if (diff
>= area
->min_spf_interval
[level
- 1]) {
1428 /* Last run is more than min interval ago, schedule immediate run */
1431 timer
= area
->min_spf_interval
[level
- 1] - diff
;
1434 thread_add_timer(master
, isis_run_spf_cb
, isis_run_spf_arg(area
, level
),
1435 timer
, &area
->spf_timer
[level
- 1]);
1437 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1438 zlog_debug("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
1439 area
->area_tag
, level
,
1440 area
->min_spf_interval
[level
- 1] - diff
);
1445 static void isis_print_paths(struct vty
*vty
, struct isis_vertex_queue
*queue
,
1448 struct listnode
*node
;
1449 struct isis_vertex
*vertex
;
1450 char buff
[PREFIX2STR_BUFFER
];
1453 "Vertex Type Metric Next-Hop Interface Parent\n");
1455 for (ALL_QUEUE_ELEMENTS_RO(queue
, node
, vertex
)) {
1456 if (memcmp(vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
1457 vty_out(vty
, "%-20s %-12s %-6s",
1458 print_sys_hostname(root_sysid
), "", "");
1459 vty_out(vty
, "%-30s\n", "");
1464 struct listnode
*anode
= listhead(vertex
->Adj_N
);
1465 struct listnode
*pnode
= listhead(vertex
->parents
);
1466 struct isis_adjacency
*adj
;
1467 struct isis_vertex
*pvertex
;
1469 vty_out(vty
, "%-20s %-12s %-6u ",
1470 vid2string(vertex
, buff
, sizeof(buff
)),
1471 vtype2string(vertex
->type
), vertex
->d_N
);
1472 for (unsigned int i
= 0;
1473 i
< MAX(listcount(vertex
->Adj_N
),
1474 listcount(vertex
->parents
)); i
++) {
1476 adj
= listgetdata(anode
);
1477 anode
= anode
->next
;
1483 pvertex
= listgetdata(pnode
);
1484 pnode
= pnode
->next
;
1491 vty_out(vty
, "%-20s %-12s %-6s ", "", "", "");
1495 vty_out(vty
, "%-20s %-9s ",
1496 print_sys_hostname(adj
->sysid
),
1497 adj
->circuit
->interface
->name
);
1502 vty_out(vty
, "%-20s %-9s ", "", "");
1504 vty_out(vty
, "%s(%d)",
1505 vid2string(pvertex
, buff
,
1516 DEFUN (show_isis_topology
,
1517 show_isis_topology_cmd
,
1518 "show isis topology [<level-1|level-2>]",
1520 "IS-IS information\n"
1521 "IS-IS paths to Intermediate Systems\n"
1522 "Paths to all level-1 routers in the area\n"
1523 "Paths to all level-2 routers in the domain\n")
1526 struct listnode
*node
;
1527 struct isis_area
*area
;
1530 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
1531 else if (strmatch(argv
[3]->text
, "level-1"))
1532 levels
= ISIS_LEVEL1
;
1534 levels
= ISIS_LEVEL2
;
1536 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1539 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
1540 vty_out(vty
, "Area %s:\n",
1541 area
->area_tag
? area
->area_tag
: "null");
1543 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
1544 if ((level
& levels
) == 0)
1547 if (area
->ip_circuits
> 0 && area
->spftree
[level
- 1]
1548 && isis_vertex_queue_count(&area
->spftree
[level
- 1]->paths
) > 0) {
1550 "IS-IS paths to level-%d routers that speak IP\n",
1553 vty
, &area
->spftree
[level
- 1]->paths
,
1557 if (area
->ipv6_circuits
> 0 && area
->spftree6
[level
- 1]
1558 && isis_vertex_queue_count(&area
->spftree6
[level
- 1]->paths
) > 0) {
1560 "IS-IS paths to level-%d routers that speak IPv6\n",
1563 vty
, &area
->spftree6
[level
- 1]->paths
,
1575 void isis_spf_cmds_init()
1577 install_element(VIEW_NODE
, &show_isis_topology_cmd
);
1580 void isis_spf_print(struct isis_spftree
*spftree
, struct vty
*vty
)
1582 vty_out(vty
, " last run elapsed : ");
1583 vty_out_timestr(vty
, spftree
->last_run_timestamp
);
1586 vty_out(vty
, " last run duration : %u usec\n",
1587 (u_int32_t
)spftree
->last_run_duration
);
1589 vty_out(vty
, " run count : %u\n",