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"
40 #include "srcdest_table.h"
41 #include "lib_errors.h"
43 #include "isis_constants.h"
44 #include "isis_common.h"
45 #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"
60 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPF_RUN
, "ISIS SPF Run Info");
66 VTYPE_NONPSEUDO_TE_IS
,
68 VTYPE_IPREACH_INTERNAL
,
69 VTYPE_IPREACH_EXTERNAL
,
71 VTYPE_IP6REACH_INTERNAL
,
72 VTYPE_IP6REACH_EXTERNAL
75 #define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS)
76 #define VTYPE_ES(t) ((t) == VTYPE_ES)
77 #define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL)
81 struct prefix_ipv6 src
;
85 * Triple <N, d(N), {Adj(N)}>
88 uint8_t id
[ISIS_SYS_ID_LEN
+ 1];
89 struct prefix_pair ip
;
94 uint32_t d_N
; /* d(N) Distance from this IS */
95 uint16_t depth
; /* The depth in the imaginary tree */
96 struct list
*Adj_N
; /* {Adj(N)} next hop or neighbor list */
97 struct list
*parents
; /* list of parents for ECMP */
98 uint64_t insert_counter
;
101 /* Vertex Queue and associated functions */
103 struct isis_vertex_queue
{
105 struct skiplist
*slist
;
109 uint64_t insert_counter
;
112 static unsigned isis_vertex_queue_hash_key(void *vp
)
114 struct isis_vertex
*vertex
= vp
;
116 if (VTYPE_IP(vertex
->type
)) {
119 key
= prefix_hash_key(&vertex
->N
.ip
.dest
);
120 key
= jhash_1word(prefix_hash_key(&vertex
->N
.ip
.src
), key
);
124 return jhash(vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1, 0x55aa5a5a);
127 static int isis_vertex_queue_hash_cmp(const void *a
, const void *b
)
129 const struct isis_vertex
*va
= a
, *vb
= b
;
131 if (va
->type
!= vb
->type
)
134 if (VTYPE_IP(va
->type
)) {
135 if (prefix_cmp(&va
->N
.ip
.dest
, &vb
->N
.ip
.dest
))
138 return prefix_cmp((struct prefix
*)&va
->N
.ip
.src
,
139 (struct prefix
*)&vb
->N
.ip
.src
) == 0;
142 return memcmp(va
->N
.id
, vb
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0;
146 * Compares vertizes for sorting in the TENT list. Returns true
147 * if candidate should be considered before current, false otherwise.
149 static int isis_vertex_queue_tent_cmp(void *a
, void *b
)
151 struct isis_vertex
*va
= a
;
152 struct isis_vertex
*vb
= b
;
154 if (va
->d_N
< vb
->d_N
)
157 if (va
->d_N
> vb
->d_N
)
160 if (va
->type
< vb
->type
)
163 if (va
->type
> vb
->type
)
166 if (va
->insert_counter
< vb
->insert_counter
)
169 if (va
->insert_counter
> vb
->insert_counter
)
175 static struct skiplist
*isis_vertex_queue_skiplist(void)
177 return skiplist_new(0, isis_vertex_queue_tent_cmp
, NULL
);
180 static void isis_vertex_queue_init(struct isis_vertex_queue
*queue
,
181 const char *name
, bool ordered
)
184 queue
->insert_counter
= 1;
185 queue
->l
.slist
= isis_vertex_queue_skiplist();
187 queue
->insert_counter
= 0;
188 queue
->l
.list
= list_new();
190 queue
->hash
= hash_create(isis_vertex_queue_hash_key
,
191 isis_vertex_queue_hash_cmp
, name
);
194 static void isis_vertex_del(struct isis_vertex
*vertex
);
196 static void isis_vertex_queue_clear(struct isis_vertex_queue
*queue
)
198 hash_clean(queue
->hash
, NULL
);
200 if (queue
->insert_counter
) {
201 struct isis_vertex
*vertex
;
202 while (0 == skiplist_first(queue
->l
.slist
, NULL
,
204 isis_vertex_del(vertex
);
205 skiplist_delete_first(queue
->l
.slist
);
207 queue
->insert_counter
= 1;
209 queue
->l
.list
->del
= (void (*)(void *))isis_vertex_del
;
210 list_delete_all_node(queue
->l
.list
);
211 queue
->l
.list
->del
= NULL
;
215 static void isis_vertex_queue_free(struct isis_vertex_queue
*queue
)
217 isis_vertex_queue_clear(queue
);
219 hash_free(queue
->hash
);
222 if (queue
->insert_counter
) {
223 skiplist_free(queue
->l
.slist
);
224 queue
->l
.slist
= NULL
;
226 list_delete_and_null(&queue
->l
.list
);
229 static unsigned int isis_vertex_queue_count(struct isis_vertex_queue
*queue
)
231 return hashcount(queue
->hash
);
234 static void isis_vertex_queue_append(struct isis_vertex_queue
*queue
,
235 struct isis_vertex
*vertex
)
237 assert(!queue
->insert_counter
);
239 listnode_add(queue
->l
.list
, vertex
);
241 struct isis_vertex
*inserted
;
243 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
244 assert(inserted
== vertex
);
247 static void isis_vertex_queue_insert(struct isis_vertex_queue
*queue
,
248 struct isis_vertex
*vertex
)
250 assert(queue
->insert_counter
);
251 vertex
->insert_counter
= queue
->insert_counter
++;
252 assert(queue
->insert_counter
!= (uint64_t)-1);
254 skiplist_insert(queue
->l
.slist
, vertex
, vertex
);
256 struct isis_vertex
*inserted
;
257 inserted
= hash_get(queue
->hash
, vertex
, hash_alloc_intern
);
258 assert(inserted
== vertex
);
261 static struct isis_vertex
*
262 isis_vertex_queue_pop(struct isis_vertex_queue
*queue
)
264 assert(queue
->insert_counter
);
266 struct isis_vertex
*rv
;
268 if (skiplist_first(queue
->l
.slist
, NULL
, (void **)&rv
))
271 skiplist_delete_first(queue
->l
.slist
);
272 hash_release(queue
->hash
, rv
);
277 static void isis_vertex_queue_delete(struct isis_vertex_queue
*queue
,
278 struct isis_vertex
*vertex
)
280 assert(queue
->insert_counter
);
282 skiplist_delete(queue
->l
.slist
, vertex
, vertex
);
283 hash_release(queue
->hash
, vertex
);
286 #define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
287 ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
290 /* End of vertex queue definitions */
292 struct isis_spftree
{
293 struct isis_vertex_queue paths
; /* the SPT */
294 struct isis_vertex_queue tents
; /* TENT */
295 struct route_table
*route_table
;
296 struct isis_area
*area
; /* back pointer to area */
297 unsigned int runcount
; /* number of runs since uptime */
298 time_t last_run_timestamp
; /* last run timestamp as wall time for display */
299 time_t last_run_monotime
; /* last run as monotime for scheduling */
300 time_t last_run_duration
; /* last run duration in msec */
305 enum spf_tree_id tree_id
;
310 * supports the given af ?
312 static bool speaks(uint8_t *protocols
, uint8_t count
, int family
)
314 for (uint8_t i
= 0; i
< count
; i
++) {
315 if (family
== AF_INET
&& protocols
[i
] == NLPID_IP
)
317 if (family
== AF_INET6
&& protocols
[i
] == NLPID_IPV6
)
323 struct isis_spf_run
{
324 struct isis_area
*area
;
329 static void remove_excess_adjs(struct list
*adjs
)
331 struct listnode
*node
, *excess
= NULL
;
332 struct isis_adjacency
*adj
, *candidate
= NULL
;
335 for (ALL_LIST_ELEMENTS_RO(adjs
, node
, adj
)) {
338 candidate
= listgetdata(excess
);
340 if (candidate
->sys_type
< adj
->sys_type
) {
344 if (candidate
->sys_type
> adj
->sys_type
)
347 comp
= memcmp(candidate
->sysid
, adj
->sysid
, ISIS_SYS_ID_LEN
);
355 if (candidate
->circuit
->idx
> adj
->circuit
->idx
) {
360 if (candidate
->circuit
->idx
< adj
->circuit
->idx
)
363 comp
= memcmp(candidate
->snpa
, adj
->snpa
, ETH_ALEN
);
370 list_delete_node(adjs
, excess
);
375 static const char *vtype2string(enum vertextype vtype
)
378 case VTYPE_PSEUDO_IS
:
381 case VTYPE_PSEUDO_TE_IS
:
382 return "pseudo_TE-IS";
384 case VTYPE_NONPSEUDO_IS
:
387 case VTYPE_NONPSEUDO_TE_IS
:
393 case VTYPE_IPREACH_INTERNAL
:
394 return "IP internal";
396 case VTYPE_IPREACH_EXTERNAL
:
397 return "IP external";
399 case VTYPE_IPREACH_TE
:
402 case VTYPE_IP6REACH_INTERNAL
:
403 return "IP6 internal";
405 case VTYPE_IP6REACH_EXTERNAL
:
406 return "IP6 external";
411 return NULL
; /* Not reached */
414 #define VID2STR_BUFFER SRCDEST2STR_BUFFER
415 static const char *vid2string(struct isis_vertex
*vertex
, char *buff
, int size
)
417 if (VTYPE_IS(vertex
->type
) || VTYPE_ES(vertex
->type
)) {
418 return print_sys_hostname(vertex
->N
.id
);
421 if (VTYPE_IP(vertex
->type
)) {
422 srcdest2str(&vertex
->N
.ip
.dest
,
431 static void isis_vertex_id_init(struct isis_vertex
*vertex
, union isis_N
*n
,
432 enum vertextype vtype
)
434 vertex
->type
= vtype
;
436 if (VTYPE_IS(vtype
) || VTYPE_ES(vtype
)) {
437 memcpy(vertex
->N
.id
, n
->id
, ISIS_SYS_ID_LEN
+ 1);
438 } else if (VTYPE_IP(vtype
)) {
439 memcpy(&vertex
->N
.ip
, &n
->ip
, sizeof(n
->ip
));
441 flog_err(LIB_ERR_DEVELOPMENT
, "Unknown Vertex Type");
445 static struct isis_vertex
*isis_vertex_new(union isis_N
*n
,
446 enum vertextype vtype
)
448 struct isis_vertex
*vertex
;
450 vertex
= XCALLOC(MTYPE_ISIS_VERTEX
, sizeof(struct isis_vertex
));
452 isis_vertex_id_init(vertex
, n
, vtype
);
454 vertex
->Adj_N
= list_new();
455 vertex
->parents
= list_new();
460 static void isis_vertex_del(struct isis_vertex
*vertex
)
462 list_delete_and_null(&vertex
->Adj_N
);
463 list_delete_and_null(&vertex
->parents
);
465 memset(vertex
, 0, sizeof(struct isis_vertex
));
466 XFREE(MTYPE_ISIS_VERTEX
, vertex
);
471 static void isis_vertex_adj_del(struct isis_vertex
*vertex
,
472 struct isis_adjacency
*adj
)
474 struct listnode
*node
, *nextnode
;
477 for (node
= listhead(vertex
->Adj_N
); node
; node
= nextnode
) {
478 nextnode
= listnextnode(node
);
479 if (listgetdata(node
) == adj
)
480 list_delete_node(vertex
->Adj_N
, node
);
485 struct isis_spftree
*isis_spftree_new(struct isis_area
*area
)
487 struct isis_spftree
*tree
;
489 tree
= XCALLOC(MTYPE_ISIS_SPFTREE
, sizeof(struct isis_spftree
));
491 isis_vertex_queue_init(&tree
->tents
, "IS-IS SPF tents", true);
492 isis_vertex_queue_init(&tree
->paths
, "IS-IS SPF paths", false);
493 tree
->route_table
= srcdest_table_init();
495 tree
->last_run_timestamp
= 0;
496 tree
->last_run_monotime
= 0;
497 tree
->last_run_duration
= 0;
502 void isis_spftree_del(struct isis_spftree
*spftree
)
504 isis_vertex_queue_free(&spftree
->tents
);
505 isis_vertex_queue_free(&spftree
->paths
);
506 route_table_finish(spftree
->route_table
);
507 spftree
->route_table
= NULL
;
509 XFREE(MTYPE_ISIS_SPFTREE
, spftree
);
513 static void isis_spftree_adj_del(struct isis_spftree
*spftree
,
514 struct isis_adjacency
*adj
)
516 struct listnode
*node
;
517 struct isis_vertex
*v
;
520 assert(!isis_vertex_queue_count(&spftree
->tents
));
521 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, v
))
522 isis_vertex_adj_del(v
, adj
);
526 void spftree_area_init(struct isis_area
*area
)
528 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
529 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
530 if (!(area
->is_type
& level
))
532 if (area
->spftree
[tree
][level
- 1])
535 area
->spftree
[tree
][level
- 1] = isis_spftree_new(area
);
540 void spftree_area_del(struct isis_area
*area
)
542 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
543 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
544 if (!(area
->is_type
& level
))
546 if (!area
->spftree
[tree
][level
- 1])
549 isis_spftree_del(area
->spftree
[tree
][level
- 1]);
554 void spftree_area_adj_del(struct isis_area
*area
, struct isis_adjacency
*adj
)
556 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
557 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
558 if (!(area
->is_type
& level
))
560 if (!area
->spftree
[tree
][level
- 1])
562 isis_spftree_adj_del(area
->spftree
[tree
][level
- 1],
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 uint8_t 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
[VID2STR_BUFFER
];
597 #endif /* EXTREME_DEBUG */
600 memcpy(n
.id
, sysid
, ISIS_SYS_ID_LEN
);
601 LSP_PSEUDO_ID(n
.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(&n
,
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
,
626 enum vertextype vtype
)
628 struct isis_vertex querier
;
630 isis_vertex_id_init(&querier
, n
, vtype
);
631 return hash_lookup(queue
->hash
, &querier
);
635 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
637 static struct isis_vertex
*isis_spf_add2tent(struct isis_spftree
*spftree
,
638 enum vertextype vtype
, void *id
,
639 uint32_t cost
, int depth
,
640 struct isis_adjacency
*adj
,
641 struct isis_vertex
*parent
)
643 struct isis_vertex
*vertex
;
644 struct listnode
*node
;
645 struct isis_adjacency
*parent_adj
;
647 char buff
[VID2STR_BUFFER
];
650 assert(isis_find_vertex(&spftree
->paths
, id
, vtype
) == NULL
);
651 assert(isis_find_vertex(&spftree
->tents
, id
, vtype
) == NULL
);
652 vertex
= isis_vertex_new(id
, vtype
);
654 vertex
->depth
= depth
;
657 listnode_add(vertex
->parents
, parent
);
660 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
661 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
, parent_adj
))
662 listnode_add(vertex
->Adj_N
, parent_adj
);
664 listnode_add(vertex
->Adj_N
, adj
);
669 "ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
670 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
671 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
672 vertex
->d_N
, listcount(vertex
->Adj_N
));
673 #endif /* EXTREME_DEBUG */
675 isis_vertex_queue_insert(&spftree
->tents
, vertex
);
679 static void isis_spf_add_local(struct isis_spftree
*spftree
,
680 enum vertextype vtype
, void *id
,
681 struct isis_adjacency
*adj
, uint32_t cost
,
682 struct isis_vertex
*parent
)
684 struct isis_vertex
*vertex
;
686 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
690 if (vertex
->d_N
== cost
) {
692 listnode_add(vertex
->Adj_N
, adj
);
694 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
695 remove_excess_adjs(vertex
->Adj_N
);
696 if (parent
&& (listnode_lookup(vertex
->parents
, parent
)
698 listnode_add(vertex
->parents
, parent
);
700 } else if (vertex
->d_N
< cost
) {
703 } else { /* vertex->d_N > cost */
705 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
706 isis_vertex_del(vertex
);
710 isis_spf_add2tent(spftree
, vtype
, id
, cost
, 1, adj
, parent
);
714 static void process_N(struct isis_spftree
*spftree
, enum vertextype vtype
,
715 void *id
, uint32_t dist
, uint16_t depth
,
716 struct isis_vertex
*parent
)
718 struct isis_vertex
*vertex
;
720 char buff
[VID2STR_BUFFER
];
723 assert(spftree
&& parent
);
725 struct prefix_pair p
;
726 if (vtype
>= VTYPE_IPREACH_INTERNAL
) {
727 memcpy(&p
, id
, sizeof(p
));
729 apply_mask((struct prefix
*)&p
.src
);
733 /* RFC3787 section 5.1 */
734 if (spftree
->area
->newmetric
== 1) {
735 if (dist
> MAX_WIDE_PATH_METRIC
)
739 else if (spftree
->area
->oldmetric
== 1) {
740 if (dist
> MAX_NARROW_PATH_METRIC
)
745 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
749 "ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
750 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
751 vid2string(vertex
, buff
, sizeof(buff
)), dist
);
752 #endif /* EXTREME_DEBUG */
753 assert(dist
>= vertex
->d_N
);
757 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
763 "ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
764 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
765 vid2string(vertex
, buff
, sizeof(buff
)), dist
,
766 (parent
? print_sys_hostname(parent
->N
.id
) : "null"),
767 (parent
? listcount(parent
->Adj_N
) : 0));
768 #endif /* EXTREME_DEBUG */
769 if (vertex
->d_N
== dist
) {
770 struct listnode
*node
;
771 struct isis_adjacency
*parent_adj
;
772 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
,
774 if (listnode_lookup(vertex
->Adj_N
, parent_adj
)
776 listnode_add(vertex
->Adj_N
, parent_adj
);
778 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
779 remove_excess_adjs(vertex
->Adj_N
);
780 if (listnode_lookup(vertex
->parents
, parent
) == NULL
)
781 listnode_add(vertex
->parents
, parent
);
783 } else if (vertex
->d_N
< dist
) {
787 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
788 isis_vertex_del(vertex
);
793 zlog_debug("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
794 print_sys_hostname(id
), vtype2string(vtype
), dist
,
795 (parent
? print_sys_hostname(parent
->N
.id
) : "null"));
796 #endif /* EXTREME_DEBUG */
798 isis_spf_add2tent(spftree
, vtype
, id
, dist
, depth
, NULL
, parent
);
805 static int isis_spf_process_lsp(struct isis_spftree
*spftree
,
806 struct isis_lsp
*lsp
, uint32_t cost
,
807 uint16_t depth
, uint8_t *root_sysid
,
808 struct isis_vertex
*parent
)
810 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
811 struct listnode
*fragnode
= NULL
;
813 enum vertextype vtype
;
814 static const uint8_t null_sysid
[ISIS_SYS_ID_LEN
];
815 struct isis_mt_router_info
*mt_router_info
= NULL
;
816 struct prefix_pair ip_info
;
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 memset(&ip_info
, 0, sizeof(ip_info
));
911 ip_info
.dest
.family
= AF_INET
;
913 struct isis_oldstyle_ip_reach
*r
;
914 for (r
= (struct isis_oldstyle_ip_reach
*)reachs
[i
]
917 dist
= cost
+ r
->metric
;
918 ip_info
.dest
.u
.prefix4
= r
->prefix
.prefix
;
919 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
920 process_N(spftree
, vtype
, &ip_info
,
921 dist
, depth
+ 1, parent
);
926 if (!pseudo_lsp
&& spftree
->family
== AF_INET
) {
927 struct isis_item_list
*ipv4_reachs
;
928 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
929 ipv4_reachs
= &lsp
->tlvs
->extended_ip_reach
;
931 ipv4_reachs
= isis_lookup_mt_items(
932 &lsp
->tlvs
->mt_ip_reach
, spftree
->mtid
);
934 memset(&ip_info
, 0, sizeof(ip_info
));
935 ip_info
.dest
.family
= AF_INET
;
937 struct isis_extended_ip_reach
*r
;
939 ? (struct isis_extended_ip_reach
*)
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_IPREACH_TE
, &ip_info
,
947 dist
, depth
+ 1, parent
);
951 if (!pseudo_lsp
&& spftree
->family
== AF_INET6
) {
952 struct isis_item_list
*ipv6_reachs
;
953 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
954 ipv6_reachs
= &lsp
->tlvs
->ipv6_reach
;
956 ipv6_reachs
= isis_lookup_mt_items(
957 &lsp
->tlvs
->mt_ipv6_reach
, spftree
->mtid
);
959 struct isis_ipv6_reach
*r
;
961 ? (struct isis_ipv6_reach
*)ipv6_reachs
->head
964 dist
= cost
+ r
->metric
;
965 vtype
= r
->external
? VTYPE_IP6REACH_EXTERNAL
966 : VTYPE_IP6REACH_INTERNAL
;
967 memset(&ip_info
, 0, sizeof(ip_info
));
968 ip_info
.dest
.family
= AF_INET6
;
969 ip_info
.dest
.u
.prefix6
= r
->prefix
.prefix
;
970 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
973 && r
->subtlvs
->source_prefix
974 && r
->subtlvs
->source_prefix
->prefixlen
) {
975 if (spftree
->tree_id
!= SPFTREE_DSTSRC
) {
976 char buff
[VID2STR_BUFFER
];
977 zlog_warn("Ignoring dest-src route %s in non dest-src topology",
980 r
->subtlvs
->source_prefix
,
986 ip_info
.src
= *r
->subtlvs
->source_prefix
;
988 process_N(spftree
, vtype
, &ip_info
, dist
,
993 if (fragnode
== NULL
)
994 fragnode
= listhead(lsp
->lspu
.frags
);
996 fragnode
= listnextnode(fragnode
);
999 lsp
= listgetdata(fragnode
);
1006 static int isis_spf_preload_tent(struct isis_spftree
*spftree
,
1007 uint8_t *root_sysid
,
1008 struct isis_vertex
*parent
)
1010 struct isis_circuit
*circuit
;
1011 struct listnode
*cnode
, *anode
, *ipnode
;
1012 struct isis_adjacency
*adj
;
1013 struct isis_lsp
*lsp
;
1014 struct list
*adj_list
;
1016 struct prefix_ipv4
*ipv4
;
1017 struct prefix_pair ip_info
;
1018 int retval
= ISIS_OK
;
1019 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1020 static uint8_t null_lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1021 struct prefix_ipv6
*ipv6
;
1022 struct isis_circuit_mt_setting
*circuit_mt
;
1024 for (ALL_LIST_ELEMENTS_RO(spftree
->area
->circuit_list
, cnode
,
1026 circuit_mt
= circuit_lookup_mt_setting(circuit
, spftree
->mtid
);
1027 if (circuit_mt
&& !circuit_mt
->enabled
)
1029 if (circuit
->state
!= C_STATE_UP
)
1031 if (!(circuit
->is_type
& spftree
->level
))
1033 if (spftree
->family
== AF_INET
&& !circuit
->ip_router
)
1035 if (spftree
->family
== AF_INET6
&& !circuit
->ipv6_router
)
1038 * Add IP(v6) addresses of this circuit
1040 if (spftree
->family
== AF_INET
) {
1041 memset(&ip_info
, 0, sizeof(ip_info
));
1042 ip_info
.dest
.family
= AF_INET
;
1043 for (ALL_LIST_ELEMENTS_RO(circuit
->ip_addrs
, ipnode
,
1045 ip_info
.dest
.u
.prefix4
= ipv4
->prefix
;
1046 ip_info
.dest
.prefixlen
= ipv4
->prefixlen
;
1047 apply_mask(&ip_info
.dest
);
1048 isis_spf_add_local(spftree
,
1049 VTYPE_IPREACH_INTERNAL
,
1050 &ip_info
, NULL
, 0, parent
);
1053 if (spftree
->family
== AF_INET6
) {
1054 memset(&ip_info
, 0, sizeof(ip_info
));
1055 ip_info
.dest
.family
= AF_INET6
;
1056 for (ALL_LIST_ELEMENTS_RO(circuit
->ipv6_non_link
,
1058 ip_info
.dest
.u
.prefix6
= ipv6
->prefix
;
1059 ip_info
.dest
.prefixlen
= ipv6
->prefixlen
;
1060 apply_mask(&ip_info
.dest
);
1061 isis_spf_add_local(spftree
,
1062 VTYPE_IP6REACH_INTERNAL
,
1063 &ip_info
, NULL
, 0, parent
);
1066 if (circuit
->circ_type
== CIRCUIT_T_BROADCAST
) {
1068 * Add the adjacencies
1070 adj_list
= list_new();
1071 adjdb
= circuit
->u
.bc
.adjdb
[spftree
->level
- 1];
1072 isis_adj_build_up_list(adjdb
, adj_list
);
1073 if (listcount(adj_list
) == 0) {
1074 list_delete_and_null(&adj_list
);
1075 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1077 "ISIS-Spf: no L%d adjacencies on circuit %s",
1079 circuit
->interface
->name
);
1082 for (ALL_LIST_ELEMENTS_RO(adj_list
, anode
, adj
)) {
1083 if (!adj_has_mt(adj
, spftree
->mtid
))
1085 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
1086 && !speaks(adj
->nlpids
.nlpids
,
1090 switch (adj
->sys_type
) {
1091 case ISIS_SYSTYPE_ES
:
1092 memcpy(lsp_id
, adj
->sysid
,
1094 LSP_PSEUDO_ID(lsp_id
) = 0;
1096 spftree
, VTYPE_ES
, lsp_id
, adj
,
1098 [spftree
->level
- 1],
1101 case ISIS_SYSTYPE_IS
:
1102 case ISIS_SYSTYPE_L1_IS
:
1103 case ISIS_SYSTYPE_L2_IS
:
1104 memcpy(lsp_id
, adj
->sysid
,
1106 LSP_PSEUDO_ID(lsp_id
) = 0;
1107 LSP_FRAGMENT(lsp_id
) = 0;
1110 spftree
->area
->oldmetric
1111 ? VTYPE_NONPSEUDO_IS
1112 : VTYPE_NONPSEUDO_TE_IS
,
1115 [spftree
->level
- 1],
1120 ->lspdb
[spftree
->level
1123 || lsp
->hdr
.rem_lifetime
== 0)
1125 "ISIS-Spf: No LSP %s found for IS adjacency "
1126 "L%d on %s (ID %u)",
1127 rawlspid_print(lsp_id
),
1129 circuit
->interface
->name
,
1130 circuit
->circuit_id
);
1132 case ISIS_SYSTYPE_UNKNOWN
:
1135 "isis_spf_preload_tent unknow adj type");
1138 list_delete_and_null(&adj_list
);
1140 * Add the pseudonode
1142 if (spftree
->level
== 1)
1143 memcpy(lsp_id
, circuit
->u
.bc
.l1_desig_is
,
1144 ISIS_SYS_ID_LEN
+ 1);
1146 memcpy(lsp_id
, circuit
->u
.bc
.l2_desig_is
,
1147 ISIS_SYS_ID_LEN
+ 1);
1148 /* can happen during DR reboot */
1149 if (memcmp(lsp_id
, null_lsp_id
, ISIS_SYS_ID_LEN
+ 1)
1151 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1153 "ISIS-Spf: No L%d DR on %s (ID %d)",
1155 circuit
->interface
->name
,
1156 circuit
->circuit_id
);
1159 adj
= isis_adj_lookup(lsp_id
, adjdb
);
1160 /* if no adj, we are the dis or error */
1161 if (!adj
&& !circuit
->u
.bc
.is_dr
[spftree
->level
- 1]) {
1163 "ISIS-Spf: No adjacency found from root "
1164 "to L%d DR %s on %s (ID %d)",
1165 spftree
->level
, rawlspid_print(lsp_id
),
1166 circuit
->interface
->name
,
1167 circuit
->circuit_id
);
1172 spftree
->area
->lspdb
[spftree
->level
- 1]);
1173 if (lsp
== NULL
|| lsp
->hdr
.rem_lifetime
== 0) {
1175 "ISIS-Spf: No lsp (%p) found from root "
1176 "to L%d DR %s on %s (ID %d)",
1177 (void *)lsp
, spftree
->level
,
1178 rawlspid_print(lsp_id
),
1179 circuit
->interface
->name
,
1180 circuit
->circuit_id
);
1183 isis_spf_process_lsp(
1185 circuit
->te_metric
[spftree
->level
- 1], 0,
1186 root_sysid
, parent
);
1187 } else if (circuit
->circ_type
== CIRCUIT_T_P2P
) {
1188 adj
= circuit
->u
.p2p
.neighbor
;
1189 if (!adj
|| adj
->adj_state
!= ISIS_ADJ_UP
)
1191 if (!adj_has_mt(adj
, spftree
->mtid
))
1193 switch (adj
->sys_type
) {
1194 case ISIS_SYSTYPE_ES
:
1195 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1196 LSP_PSEUDO_ID(lsp_id
) = 0;
1198 spftree
, VTYPE_ES
, lsp_id
, adj
,
1199 circuit
->te_metric
[spftree
->level
- 1],
1202 case ISIS_SYSTYPE_IS
:
1203 case ISIS_SYSTYPE_L1_IS
:
1204 case ISIS_SYSTYPE_L2_IS
:
1205 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1206 LSP_PSEUDO_ID(lsp_id
) = 0;
1207 LSP_FRAGMENT(lsp_id
) = 0;
1208 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
1209 || speaks(adj
->nlpids
.nlpids
,
1214 spftree
->area
->oldmetric
1215 ? VTYPE_NONPSEUDO_IS
1216 : VTYPE_NONPSEUDO_TE_IS
,
1219 [spftree
->level
- 1],
1222 case ISIS_SYSTYPE_UNKNOWN
:
1225 "isis_spf_preload_tent unknown adj type");
1228 } else if (circuit
->circ_type
== CIRCUIT_T_LOOPBACK
) {
1231 zlog_warn("isis_spf_preload_tent unsupported media");
1232 retval
= ISIS_WARNING
;
1240 * The parent(s) for vertex is set when added to TENT list
1241 * now we just put the child pointer(s) in place
1243 static void add_to_paths(struct isis_spftree
*spftree
,
1244 struct isis_vertex
*vertex
)
1246 char buff
[VID2STR_BUFFER
];
1248 if (isis_find_vertex(&spftree
->paths
, &vertex
->N
, vertex
->type
))
1250 isis_vertex_queue_append(&spftree
->paths
, vertex
);
1252 #ifdef EXTREME_DEBUG
1253 zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
1254 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
1255 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
1257 #endif /* EXTREME_DEBUG */
1259 if (VTYPE_IP(vertex
->type
)) {
1260 if (listcount(vertex
->Adj_N
) > 0)
1261 isis_route_create(&vertex
->N
.ip
.dest
,
1263 vertex
->d_N
, vertex
->depth
,
1264 vertex
->Adj_N
, spftree
->area
,
1265 spftree
->route_table
);
1266 else if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1268 "ISIS-Spf: no adjacencies do not install route for "
1269 "%s depth %d dist %d",
1270 vid2string(vertex
, buff
, sizeof(buff
)),
1271 vertex
->depth
, vertex
->d_N
);
1277 static void init_spt(struct isis_spftree
*spftree
, int mtid
, int level
,
1278 int family
, enum spf_tree_id tree_id
)
1280 isis_vertex_queue_clear(&spftree
->tents
);
1281 isis_vertex_queue_clear(&spftree
->paths
);
1283 spftree
->mtid
= mtid
;
1284 spftree
->level
= level
;
1285 spftree
->family
= family
;
1286 spftree
->tree_id
= tree_id
;
1290 static int isis_run_spf(struct isis_area
*area
, int level
,
1291 enum spf_tree_id tree_id
,
1292 uint8_t *sysid
, struct timeval
*nowtv
)
1294 int retval
= ISIS_OK
;
1295 struct isis_vertex
*vertex
;
1296 struct isis_vertex
*root_vertex
;
1297 struct isis_spftree
*spftree
= area
->spftree
[tree_id
][level
- 1];
1298 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1299 struct isis_lsp
*lsp
;
1300 struct timeval time_now
;
1301 unsigned long long start_time
, end_time
;
1304 /* Get time that can't roll backwards. */
1305 start_time
= nowtv
->tv_sec
;
1306 start_time
= (start_time
* 1000000) + nowtv
->tv_usec
;
1312 mtid
= ISIS_MT_IPV4_UNICAST
;
1316 mtid
= isis_area_ipv6_topology(area
);
1318 case SPFTREE_DSTSRC
:
1320 mtid
= ISIS_MT_IPV6_DSTSRC
;
1323 assert(!"isis_run_spf should never be called with SPFTREE_COUNT as argument!");
1324 return ISIS_WARNING
;
1333 init_spt(spftree
, mtid
, level
, family
, tree_id
);
1335 root_vertex
= isis_spf_add_root(spftree
, sysid
);
1337 retval
= isis_spf_preload_tent(spftree
, sysid
, root_vertex
);
1338 if (retval
!= ISIS_OK
) {
1339 zlog_warn("ISIS-Spf: failed to load TENT SPF-root:%s",
1340 print_sys_hostname(sysid
));
1347 if (!isis_vertex_queue_count(&spftree
->tents
)
1348 && (isis
->debugs
& DEBUG_SPF_EVENTS
)) {
1349 zlog_warn("ISIS-Spf: TENT is empty SPF-root:%s",
1350 print_sys_hostname(sysid
));
1353 while (isis_vertex_queue_count(&spftree
->tents
)) {
1354 vertex
= isis_vertex_queue_pop(&spftree
->tents
);
1356 #ifdef EXTREME_DEBUG
1358 "ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
1359 print_sys_hostname(vertex
->N
.id
),
1360 vtype2string(vertex
->type
), vertex
->depth
, vertex
->d_N
);
1361 #endif /* EXTREME_DEBUG */
1363 add_to_paths(spftree
, vertex
);
1364 if (VTYPE_IS(vertex
->type
)) {
1365 memcpy(lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
1366 LSP_FRAGMENT(lsp_id
) = 0;
1367 lsp
= lsp_search(lsp_id
, area
->lspdb
[level
- 1]);
1368 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0) {
1369 isis_spf_process_lsp(spftree
, lsp
, vertex
->d_N
,
1370 vertex
->depth
, sysid
,
1373 zlog_warn("ISIS-Spf: No LSP found for %s",
1374 rawlspid_print(lsp_id
));
1380 spftree
->runcount
++;
1381 spftree
->last_run_timestamp
= time(NULL
);
1382 spftree
->last_run_monotime
= monotime(&time_now
);
1383 end_time
= time_now
.tv_sec
;
1384 end_time
= (end_time
* 1000000) + time_now
.tv_usec
;
1385 spftree
->last_run_duration
= end_time
- start_time
;
1390 void isis_spf_verify_routes(struct isis_area
*area
, struct isis_spftree
**trees
)
1392 if (area
->is_type
== IS_LEVEL_1
) {
1393 isis_route_verify_table(area
, trees
[0]->route_table
);
1394 } else if (area
->is_type
== IS_LEVEL_2
) {
1395 isis_route_verify_table(area
, trees
[1]->route_table
);
1397 isis_route_verify_merge(area
, trees
[0]->route_table
,
1398 trees
[1]->route_table
);
1402 void isis_spf_invalidate_routes(struct isis_spftree
*tree
)
1404 isis_route_invalidate_table(tree
->area
, tree
->route_table
);
1407 static int isis_run_spf_cb(struct thread
*thread
)
1409 struct isis_spf_run
*run
= THREAD_ARG(thread
);
1410 struct isis_area
*area
= run
->area
;
1411 int level
= run
->level
;
1412 int retval
= ISIS_OK
;
1414 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1415 area
->spf_timer
[level
- 1] = NULL
;
1417 if (!(area
->is_type
& level
)) {
1418 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1419 zlog_warn("ISIS-SPF (%s) area does not share level",
1421 return ISIS_WARNING
;
1424 isis_area_invalidate_routes(area
, level
);
1426 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1427 zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
1428 area
->area_tag
, level
);
1430 if (area
->ip_circuits
)
1431 retval
= isis_run_spf(area
, level
, SPFTREE_IPV4
, isis
->sysid
,
1433 if (area
->ipv6_circuits
)
1434 retval
= isis_run_spf(area
, level
, SPFTREE_IPV6
, isis
->sysid
,
1436 if (area
->ipv6_circuits
1437 && isis_area_ipv6_dstsrc_enabled(area
))
1438 retval
= isis_run_spf(area
, level
, SPFTREE_DSTSRC
, isis
->sysid
,
1441 isis_area_verify_routes(area
);
1443 /* walk all circuits and reset any spf specific flags */
1444 struct listnode
*node
;
1445 struct isis_circuit
*circuit
;
1446 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
))
1447 UNSET_FLAG(circuit
->flags
, ISIS_CIRCUIT_FLAPPED_AFTER_SPF
);
1452 static struct isis_spf_run
*isis_run_spf_arg(struct isis_area
*area
, int level
)
1454 struct isis_spf_run
*run
= XMALLOC(MTYPE_ISIS_SPF_RUN
, sizeof(*run
));
1462 int isis_spf_schedule(struct isis_area
*area
, int level
)
1464 struct isis_spftree
*spftree
= area
->spftree
[SPFTREE_IPV4
][level
- 1];
1465 time_t now
= monotime(NULL
);
1466 int diff
= now
- spftree
->last_run_monotime
;
1469 assert(area
->is_type
& level
);
1471 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1473 "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
1474 area
->area_tag
, level
, diff
);
1476 if (area
->spf_delay_ietf
[level
- 1]) {
1477 /* Need to call schedule function also if spf delay is running
1479 * restart holdoff timer - compare
1480 * draft-ietf-rtgwg-backoff-algo-04 */
1482 spf_backoff_schedule(area
->spf_delay_ietf
[level
- 1]);
1483 if (area
->spf_timer
[level
- 1])
1486 thread_add_timer_msec(master
, isis_run_spf_cb
,
1487 isis_run_spf_arg(area
, level
), delay
,
1488 &area
->spf_timer
[level
- 1]);
1492 if (area
->spf_timer
[level
- 1])
1495 /* wait configured min_spf_interval before doing the SPF */
1497 if (diff
>= area
->min_spf_interval
[level
- 1]) {
1498 /* Last run is more than min interval ago, schedule immediate run */
1501 timer
= area
->min_spf_interval
[level
- 1] - diff
;
1504 thread_add_timer(master
, isis_run_spf_cb
, isis_run_spf_arg(area
, level
),
1505 timer
, &area
->spf_timer
[level
- 1]);
1507 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1508 zlog_debug("ISIS-Spf (%s) L%d SPF scheduled %ld sec from now",
1509 area
->area_tag
, level
, timer
);
1514 static void isis_print_paths(struct vty
*vty
, struct isis_vertex_queue
*queue
,
1515 uint8_t *root_sysid
)
1517 struct listnode
*node
;
1518 struct isis_vertex
*vertex
;
1519 char buff
[VID2STR_BUFFER
];
1522 "Vertex Type Metric Next-Hop Interface Parent\n");
1524 for (ALL_QUEUE_ELEMENTS_RO(queue
, node
, vertex
)) {
1525 if (memcmp(vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
1526 vty_out(vty
, "%-20s %-12s %-6s",
1527 print_sys_hostname(root_sysid
), "", "");
1528 vty_out(vty
, "%-30s\n", "");
1533 struct listnode
*anode
= listhead(vertex
->Adj_N
);
1534 struct listnode
*pnode
= listhead(vertex
->parents
);
1535 struct isis_adjacency
*adj
;
1536 struct isis_vertex
*pvertex
;
1538 vty_out(vty
, "%-20s %-12s %-6u ",
1539 vid2string(vertex
, buff
, sizeof(buff
)),
1540 vtype2string(vertex
->type
), vertex
->d_N
);
1541 for (unsigned int i
= 0;
1542 i
< MAX(vertex
->Adj_N
? listcount(vertex
->Adj_N
) : 0,
1543 vertex
->parents
? listcount(vertex
->parents
) : 0);
1546 adj
= listgetdata(anode
);
1547 anode
= anode
->next
;
1553 pvertex
= listgetdata(pnode
);
1554 pnode
= pnode
->next
;
1561 vty_out(vty
, "%-20s %-12s %-6s ", "", "", "");
1565 vty_out(vty
, "%-20s %-9s ",
1566 print_sys_hostname(adj
->sysid
),
1567 adj
->circuit
->interface
->name
);
1572 vty_out(vty
, "%-20s %-9s ", "", "");
1574 vty_out(vty
, "%s(%d)",
1575 vid2string(pvertex
, buff
, sizeof(buff
)),
1585 static void isis_print_spftree(struct vty
*vty
, int level
,
1586 struct isis_area
*area
,
1587 enum spf_tree_id tree_id
)
1589 const char *tree_id_text
= NULL
;
1593 tree_id_text
= "that speak IP";
1596 tree_id_text
= "that speak IPv6";
1598 case SPFTREE_DSTSRC
:
1599 tree_id_text
= "that support IPv6 dst-src routing";
1602 assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type");
1606 if (!area
->spftree
[tree_id
][level
- 1]
1607 || !isis_vertex_queue_count(
1608 &area
->spftree
[tree_id
][level
- 1]->paths
))
1611 vty_out(vty
, "IS-IS paths to level-%d routers %s\n",
1612 level
, tree_id_text
);
1613 isis_print_paths(vty
, &area
->spftree
[tree_id
][level
- 1]->paths
,
1618 DEFUN (show_isis_topology
,
1619 show_isis_topology_cmd
,
1620 "show " PROTO_NAME
" topology"
1622 " [<level-1|level-2>]"
1626 "IS-IS paths to Intermediate Systems\n"
1628 "Paths to all level-1 routers in the area\n"
1629 "Paths to all level-2 routers in the domain\n"
1634 struct listnode
*node
;
1635 struct isis_area
*area
;
1638 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
1639 else if (strmatch(argv
[3]->text
, "level-1"))
1640 levels
= ISIS_LEVEL1
;
1642 levels
= ISIS_LEVEL2
;
1644 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1647 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
1648 vty_out(vty
, "Area %s:\n",
1649 area
->area_tag
? area
->area_tag
: "null");
1651 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
1652 if ((level
& levels
) == 0)
1655 if (area
->ip_circuits
> 0) {
1656 isis_print_spftree(vty
, level
, area
,
1659 if (area
->ipv6_circuits
> 0) {
1660 isis_print_spftree(vty
, level
, area
,
1663 if (isis_area_ipv6_dstsrc_enabled(area
)) {
1664 isis_print_spftree(vty
, level
, area
,
1675 void isis_spf_cmds_init()
1677 install_element(VIEW_NODE
, &show_isis_topology_cmd
);
1680 void isis_spf_print(struct isis_spftree
*spftree
, struct vty
*vty
)
1682 vty_out(vty
, " last run elapsed : ");
1683 vty_out_timestr(vty
, spftree
->last_run_timestamp
);
1686 vty_out(vty
, " last run duration : %u usec\n",
1687 (uint32_t)spftree
->last_run_duration
);
1689 vty_out(vty
, " run count : %u\n", spftree
->runcount
);