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
36 #include "spf_backoff.h"
37 #include "srcdest_table.h"
39 #include "isis_constants.h"
40 #include "isis_common.h"
41 #include "isis_flags.h"
44 #include "isis_misc.h"
45 #include "isis_adjacency.h"
46 #include "isis_circuit.h"
49 #include "isis_dynhn.h"
51 #include "isis_route.h"
54 #include "isis_tlvs.h"
56 #include "isis_spf_private.h"
58 DEFINE_MTYPE_STATIC(ISISD
, ISIS_SPF_RUN
, "ISIS SPF Run Info");
61 * supports the given af ?
63 static bool speaks(uint8_t *protocols
, uint8_t count
, int family
)
65 for (uint8_t i
= 0; i
< count
; i
++) {
66 if (family
== AF_INET
&& protocols
[i
] == NLPID_IP
)
68 if (family
== AF_INET6
&& protocols
[i
] == NLPID_IPV6
)
75 struct isis_area
*area
;
80 static void remove_excess_adjs(struct list
*adjs
)
82 struct listnode
*node
, *excess
= NULL
;
83 struct isis_adjacency
*adj
, *candidate
= NULL
;
86 for (ALL_LIST_ELEMENTS_RO(adjs
, node
, adj
)) {
89 candidate
= listgetdata(excess
);
91 if (candidate
->sys_type
< adj
->sys_type
) {
95 if (candidate
->sys_type
> adj
->sys_type
)
98 comp
= memcmp(candidate
->sysid
, adj
->sysid
, ISIS_SYS_ID_LEN
);
106 if (candidate
->circuit
->idx
> adj
->circuit
->idx
) {
111 if (candidate
->circuit
->idx
< adj
->circuit
->idx
)
114 comp
= memcmp(candidate
->snpa
, adj
->snpa
, ETH_ALEN
);
121 list_delete_node(adjs
, excess
);
126 static const char *vtype2string(enum vertextype vtype
)
129 case VTYPE_PSEUDO_IS
:
132 case VTYPE_PSEUDO_TE_IS
:
133 return "pseudo_TE-IS";
135 case VTYPE_NONPSEUDO_IS
:
138 case VTYPE_NONPSEUDO_TE_IS
:
144 case VTYPE_IPREACH_INTERNAL
:
145 return "IP internal";
147 case VTYPE_IPREACH_EXTERNAL
:
148 return "IP external";
150 case VTYPE_IPREACH_TE
:
153 case VTYPE_IP6REACH_INTERNAL
:
154 return "IP6 internal";
156 case VTYPE_IP6REACH_EXTERNAL
:
157 return "IP6 external";
162 return NULL
; /* Not reached */
165 const char *vid2string(struct isis_vertex
*vertex
, char *buff
, int size
)
167 if (VTYPE_IS(vertex
->type
) || VTYPE_ES(vertex
->type
)) {
168 return print_sys_hostname(vertex
->N
.id
);
171 if (VTYPE_IP(vertex
->type
)) {
172 srcdest2str(&vertex
->N
.ip
.dest
,
181 static struct isis_vertex
*isis_vertex_new(struct isis_spftree
*spftree
,
183 enum vertextype vtype
)
185 struct isis_vertex
*vertex
;
187 vertex
= XCALLOC(MTYPE_ISIS_VERTEX
, sizeof(struct isis_vertex
));
189 isis_vertex_id_init(vertex
, id
, vtype
);
191 vertex
->Adj_N
= list_new();
192 vertex
->parents
= list_new();
194 if (spftree
->hopcount_metric
) {
195 vertex
->firsthops
= hash_create(isis_vertex_queue_hash_key
,
196 isis_vertex_queue_hash_cmp
,
203 static void isis_vertex_adj_del(struct isis_vertex
*vertex
,
204 struct isis_adjacency
*adj
)
206 struct listnode
*node
, *nextnode
;
209 for (node
= listhead(vertex
->Adj_N
); node
; node
= nextnode
) {
210 nextnode
= listnextnode(node
);
211 if (listgetdata(node
) == adj
)
212 list_delete_node(vertex
->Adj_N
, node
);
217 struct isis_spftree
*isis_spftree_new(struct isis_area
*area
)
219 struct isis_spftree
*tree
;
221 tree
= XCALLOC(MTYPE_ISIS_SPFTREE
, sizeof(struct isis_spftree
));
223 isis_vertex_queue_init(&tree
->tents
, "IS-IS SPF tents", true);
224 isis_vertex_queue_init(&tree
->paths
, "IS-IS SPF paths", false);
225 tree
->route_table
= srcdest_table_init();
227 tree
->last_run_timestamp
= 0;
228 tree
->last_run_monotime
= 0;
229 tree
->last_run_duration
= 0;
234 void isis_spftree_del(struct isis_spftree
*spftree
)
236 isis_vertex_queue_free(&spftree
->tents
);
237 isis_vertex_queue_free(&spftree
->paths
);
238 route_table_finish(spftree
->route_table
);
239 spftree
->route_table
= NULL
;
241 XFREE(MTYPE_ISIS_SPFTREE
, spftree
);
245 static void isis_spftree_adj_del(struct isis_spftree
*spftree
,
246 struct isis_adjacency
*adj
)
248 struct listnode
*node
;
249 struct isis_vertex
*v
;
252 assert(!isis_vertex_queue_count(&spftree
->tents
));
253 for (ALL_QUEUE_ELEMENTS_RO(&spftree
->paths
, node
, v
))
254 isis_vertex_adj_del(v
, adj
);
258 void spftree_area_init(struct isis_area
*area
)
260 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
261 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
262 if (!(area
->is_type
& level
))
264 if (area
->spftree
[tree
][level
- 1])
267 area
->spftree
[tree
][level
- 1] = isis_spftree_new(area
);
272 void spftree_area_del(struct isis_area
*area
)
274 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
275 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
276 if (!(area
->is_type
& level
))
278 if (!area
->spftree
[tree
][level
- 1])
281 isis_spftree_del(area
->spftree
[tree
][level
- 1]);
286 void spftree_area_adj_del(struct isis_area
*area
, struct isis_adjacency
*adj
)
288 for (int tree
= SPFTREE_IPV4
; tree
< SPFTREE_COUNT
; tree
++) {
289 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVEL2
; level
++) {
290 if (!(area
->is_type
& level
))
292 if (!area
->spftree
[tree
][level
- 1])
294 isis_spftree_adj_del(area
->spftree
[tree
][level
- 1],
299 if (fabricd_spftree(area
) != NULL
)
300 isis_spftree_adj_del(fabricd_spftree(area
), adj
);
304 * Find the system LSP: returns the LSP in our LSP database
305 * associated with the given system ID.
307 static struct isis_lsp
*isis_root_system_lsp(struct isis_area
*area
, int level
,
310 struct isis_lsp
*lsp
;
311 uint8_t lspid
[ISIS_SYS_ID_LEN
+ 2];
313 memcpy(lspid
, sysid
, ISIS_SYS_ID_LEN
);
314 LSP_PSEUDO_ID(lspid
) = 0;
315 LSP_FRAGMENT(lspid
) = 0;
316 lsp
= lsp_search(lspid
, area
->lspdb
[level
- 1]);
317 if (lsp
&& lsp
->hdr
.rem_lifetime
!= 0)
323 * Add this IS to the root of SPT
325 static struct isis_vertex
*isis_spf_add_root(struct isis_spftree
*spftree
,
328 struct isis_vertex
*vertex
;
329 struct isis_lsp
*lsp
;
331 char buff
[VID2STR_BUFFER
];
332 #endif /* EXTREME_DEBUG */
334 lsp
= isis_root_system_lsp(spftree
->area
, spftree
->level
, sysid
);
336 zlog_warn("ISIS-Spf: could not find own l%d LSP!",
339 vertex
= isis_vertex_new(spftree
, sysid
,
340 spftree
->area
->oldmetric
342 : VTYPE_NONPSEUDO_TE_IS
);
343 isis_vertex_queue_append(&spftree
->paths
, vertex
);
346 zlog_debug("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
347 vtype2string(vertex
->type
),
348 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
350 #endif /* EXTREME_DEBUG */
355 static void vertex_add_parent_firsthop(struct hash_backet
*backet
, void *arg
)
357 struct isis_vertex
*vertex
= arg
;
358 struct isis_vertex
*hop
= backet
->data
;
360 hash_get(vertex
->firsthops
, hop
, hash_alloc_intern
);
363 static void vertex_update_firsthops(struct isis_vertex
*vertex
,
364 struct isis_vertex
*parent
)
366 if (vertex
->d_N
<= 2)
367 hash_get(vertex
->firsthops
, vertex
, hash_alloc_intern
);
369 if (vertex
->d_N
< 2 || !parent
)
372 hash_iterate(parent
->firsthops
, vertex_add_parent_firsthop
, vertex
);
376 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
378 static struct isis_vertex
*isis_spf_add2tent(struct isis_spftree
*spftree
,
379 enum vertextype vtype
, void *id
,
380 uint32_t cost
, int depth
,
381 struct isis_adjacency
*adj
,
382 struct isis_vertex
*parent
)
384 struct isis_vertex
*vertex
;
385 struct listnode
*node
;
386 struct isis_adjacency
*parent_adj
;
388 char buff
[VID2STR_BUFFER
];
391 assert(isis_find_vertex(&spftree
->paths
, id
, vtype
) == NULL
);
392 assert(isis_find_vertex(&spftree
->tents
, id
, vtype
) == NULL
);
393 vertex
= isis_vertex_new(spftree
, id
, vtype
);
395 vertex
->depth
= depth
;
398 listnode_add(vertex
->parents
, parent
);
401 if (spftree
->hopcount_metric
)
402 vertex_update_firsthops(vertex
, parent
);
404 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
405 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
, parent_adj
))
406 listnode_add(vertex
->Adj_N
, parent_adj
);
408 listnode_add(vertex
->Adj_N
, adj
);
413 "ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
414 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
415 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
416 vertex
->d_N
, listcount(vertex
->Adj_N
));
417 #endif /* EXTREME_DEBUG */
419 isis_vertex_queue_insert(&spftree
->tents
, vertex
);
423 static void isis_spf_add_local(struct isis_spftree
*spftree
,
424 enum vertextype vtype
, void *id
,
425 struct isis_adjacency
*adj
, uint32_t cost
,
426 struct isis_vertex
*parent
)
428 struct isis_vertex
*vertex
;
430 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
434 if (vertex
->d_N
== cost
) {
436 listnode_add(vertex
->Adj_N
, adj
);
438 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
439 remove_excess_adjs(vertex
->Adj_N
);
440 if (parent
&& (listnode_lookup(vertex
->parents
, parent
)
442 listnode_add(vertex
->parents
, parent
);
444 } else if (vertex
->d_N
< cost
) {
447 } else { /* vertex->d_N > cost */
449 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
450 isis_vertex_del(vertex
);
454 isis_spf_add2tent(spftree
, vtype
, id
, cost
, 1, adj
, parent
);
458 static void process_N(struct isis_spftree
*spftree
, enum vertextype vtype
,
459 void *id
, uint32_t dist
, uint16_t depth
,
460 struct isis_vertex
*parent
)
462 struct isis_vertex
*vertex
;
464 char buff
[VID2STR_BUFFER
];
467 assert(spftree
&& parent
);
469 if (spftree
->hopcount_metric
473 struct prefix_pair p
;
474 if (vtype
>= VTYPE_IPREACH_INTERNAL
) {
475 memcpy(&p
, id
, sizeof(p
));
477 apply_mask((struct prefix
*)&p
.src
);
481 /* RFC3787 section 5.1 */
482 if (spftree
->area
->newmetric
== 1) {
483 if (dist
> MAX_WIDE_PATH_METRIC
)
487 else if (spftree
->area
->oldmetric
== 1) {
488 if (dist
> MAX_NARROW_PATH_METRIC
)
493 vertex
= isis_find_vertex(&spftree
->paths
, id
, vtype
);
497 "ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
498 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
499 vid2string(vertex
, buff
, sizeof(buff
)), dist
);
500 #endif /* EXTREME_DEBUG */
501 assert(dist
>= vertex
->d_N
);
505 vertex
= isis_find_vertex(&spftree
->tents
, id
, vtype
);
511 "ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
512 print_sys_hostname(vertex
->N
.id
), vtype2string(vtype
),
513 vid2string(vertex
, buff
, sizeof(buff
)), dist
,
514 (parent
? print_sys_hostname(parent
->N
.id
) : "null"),
515 (parent
? listcount(parent
->Adj_N
) : 0));
516 #endif /* EXTREME_DEBUG */
517 if (vertex
->d_N
== dist
) {
518 struct listnode
*node
;
519 struct isis_adjacency
*parent_adj
;
520 for (ALL_LIST_ELEMENTS_RO(parent
->Adj_N
, node
,
522 if (listnode_lookup(vertex
->Adj_N
, parent_adj
)
524 listnode_add(vertex
->Adj_N
, parent_adj
);
525 if (spftree
->hopcount_metric
)
526 vertex_update_firsthops(vertex
, parent
);
528 if (listcount(vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
529 remove_excess_adjs(vertex
->Adj_N
);
530 if (listnode_lookup(vertex
->parents
, parent
) == NULL
)
531 listnode_add(vertex
->parents
, parent
);
533 } else if (vertex
->d_N
< dist
) {
537 isis_vertex_queue_delete(&spftree
->tents
, vertex
);
538 isis_vertex_del(vertex
);
543 zlog_debug("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
544 print_sys_hostname(id
), vtype2string(vtype
), dist
,
545 (parent
? print_sys_hostname(parent
->N
.id
) : "null"));
546 #endif /* EXTREME_DEBUG */
548 isis_spf_add2tent(spftree
, vtype
, id
, dist
, depth
, NULL
, parent
);
555 static int isis_spf_process_lsp(struct isis_spftree
*spftree
,
556 struct isis_lsp
*lsp
, uint32_t cost
,
557 uint16_t depth
, uint8_t *root_sysid
,
558 struct isis_vertex
*parent
)
560 bool pseudo_lsp
= LSP_PSEUDO_ID(lsp
->hdr
.lsp_id
);
561 struct listnode
*fragnode
= NULL
;
563 enum vertextype vtype
;
564 static const uint8_t null_sysid
[ISIS_SYS_ID_LEN
];
565 struct isis_mt_router_info
*mt_router_info
= NULL
;
566 struct prefix_pair ip_info
;
571 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
)
572 mt_router_info
= isis_tlvs_lookup_mt_router_info(lsp
->tlvs
,
575 if (!pseudo_lsp
&& (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
576 && !speaks(lsp
->tlvs
->protocols_supported
.protocols
,
577 lsp
->tlvs
->protocols_supported
.count
,
582 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
583 bool no_overload
= (pseudo_lsp
584 || (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
585 && !ISIS_MASK_LSP_OL_BIT(lsp
->hdr
.lsp_bits
))
586 || (mt_router_info
&& !mt_router_info
->overload
));
589 if (lsp
->hdr
.seqno
== 0) {
591 "isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
596 zlog_debug("ISIS-Spf: process_lsp %s",
597 print_sys_hostname(lsp
->hdr
.lsp_id
));
598 #endif /* EXTREME_DEBUG */
601 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
602 struct isis_oldstyle_reach
*r
;
603 for (r
= (struct isis_oldstyle_reach
*)
604 lsp
->tlvs
->oldstyle_reach
.head
;
610 /* Two way connectivity */
611 if (!memcmp(r
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
614 && !memcmp(r
->id
, null_sysid
,
617 dist
= cost
+ r
->metric
;
621 : VTYPE_NONPSEUDO_IS
,
622 (void *)r
->id
, dist
, depth
+ 1,
627 struct isis_item_list
*te_neighs
= NULL
;
628 if (pseudo_lsp
|| spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
629 te_neighs
= &lsp
->tlvs
->extended_reach
;
631 te_neighs
= isis_lookup_mt_items(&lsp
->tlvs
->mt_reach
,
634 struct isis_extended_reach
*er
;
636 ? (struct isis_extended_reach
*)
640 if (!memcmp(er
->id
, root_sysid
, ISIS_SYS_ID_LEN
))
643 && !memcmp(er
->id
, null_sysid
, ISIS_SYS_ID_LEN
))
645 dist
= cost
+ (spftree
->hopcount_metric
? 1 : er
->metric
);
647 LSP_PSEUDO_ID(er
->id
) ? VTYPE_PSEUDO_TE_IS
648 : VTYPE_NONPSEUDO_TE_IS
,
649 (void *)er
->id
, dist
, depth
+ 1, parent
);
653 if (!fabricd
&& !pseudo_lsp
&& spftree
->family
== AF_INET
654 && spftree
->mtid
== ISIS_MT_IPV4_UNICAST
) {
655 struct isis_item_list
*reachs
[] = {
656 &lsp
->tlvs
->oldstyle_ip_reach
,
657 &lsp
->tlvs
->oldstyle_ip_reach_ext
};
659 for (unsigned int i
= 0; i
< array_size(reachs
); i
++) {
660 vtype
= i
? VTYPE_IPREACH_EXTERNAL
661 : VTYPE_IPREACH_INTERNAL
;
663 memset(&ip_info
, 0, sizeof(ip_info
));
664 ip_info
.dest
.family
= AF_INET
;
666 struct isis_oldstyle_ip_reach
*r
;
667 for (r
= (struct isis_oldstyle_ip_reach
*)reachs
[i
]
670 dist
= cost
+ r
->metric
;
671 ip_info
.dest
.u
.prefix4
= r
->prefix
.prefix
;
672 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
673 process_N(spftree
, vtype
, &ip_info
,
674 dist
, depth
+ 1, parent
);
679 if (!pseudo_lsp
&& spftree
->family
== AF_INET
) {
680 struct isis_item_list
*ipv4_reachs
;
681 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
682 ipv4_reachs
= &lsp
->tlvs
->extended_ip_reach
;
684 ipv4_reachs
= isis_lookup_mt_items(
685 &lsp
->tlvs
->mt_ip_reach
, spftree
->mtid
);
687 memset(&ip_info
, 0, sizeof(ip_info
));
688 ip_info
.dest
.family
= AF_INET
;
690 struct isis_extended_ip_reach
*r
;
692 ? (struct isis_extended_ip_reach
*)
696 dist
= cost
+ r
->metric
;
697 ip_info
.dest
.u
.prefix4
= r
->prefix
.prefix
;
698 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
699 process_N(spftree
, VTYPE_IPREACH_TE
, &ip_info
,
700 dist
, depth
+ 1, parent
);
704 if (!pseudo_lsp
&& spftree
->family
== AF_INET6
) {
705 struct isis_item_list
*ipv6_reachs
;
706 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
)
707 ipv6_reachs
= &lsp
->tlvs
->ipv6_reach
;
709 ipv6_reachs
= isis_lookup_mt_items(
710 &lsp
->tlvs
->mt_ipv6_reach
, spftree
->mtid
);
712 struct isis_ipv6_reach
*r
;
714 ? (struct isis_ipv6_reach
*)ipv6_reachs
->head
717 dist
= cost
+ r
->metric
;
718 vtype
= r
->external
? VTYPE_IP6REACH_EXTERNAL
719 : VTYPE_IP6REACH_INTERNAL
;
720 memset(&ip_info
, 0, sizeof(ip_info
));
721 ip_info
.dest
.family
= AF_INET6
;
722 ip_info
.dest
.u
.prefix6
= r
->prefix
.prefix
;
723 ip_info
.dest
.prefixlen
= r
->prefix
.prefixlen
;
726 && r
->subtlvs
->source_prefix
727 && r
->subtlvs
->source_prefix
->prefixlen
) {
728 if (spftree
->tree_id
!= SPFTREE_DSTSRC
) {
729 char buff
[VID2STR_BUFFER
];
730 zlog_warn("Ignoring dest-src route %s in non dest-src topology",
733 r
->subtlvs
->source_prefix
,
739 ip_info
.src
= *r
->subtlvs
->source_prefix
;
741 process_N(spftree
, vtype
, &ip_info
, dist
,
746 if (fragnode
== NULL
)
747 fragnode
= listhead(lsp
->lspu
.frags
);
749 fragnode
= listnextnode(fragnode
);
752 lsp
= listgetdata(fragnode
);
759 static int isis_spf_preload_tent(struct isis_spftree
*spftree
,
761 struct isis_vertex
*parent
)
763 struct isis_circuit
*circuit
;
764 struct listnode
*cnode
, *anode
, *ipnode
;
765 struct isis_adjacency
*adj
;
766 struct isis_lsp
*lsp
;
767 struct list
*adj_list
;
769 struct prefix_ipv4
*ipv4
;
770 struct prefix_pair ip_info
;
771 int retval
= ISIS_OK
;
772 uint8_t lsp_id
[ISIS_SYS_ID_LEN
+ 2];
773 static uint8_t null_lsp_id
[ISIS_SYS_ID_LEN
+ 2];
774 struct prefix_ipv6
*ipv6
;
775 struct isis_circuit_mt_setting
*circuit_mt
;
777 for (ALL_LIST_ELEMENTS_RO(spftree
->area
->circuit_list
, cnode
,
779 circuit_mt
= circuit_lookup_mt_setting(circuit
, spftree
->mtid
);
780 if (circuit_mt
&& !circuit_mt
->enabled
)
782 if (circuit
->state
!= C_STATE_UP
)
784 if (!(circuit
->is_type
& spftree
->level
))
786 if (spftree
->family
== AF_INET
&& !circuit
->ip_router
)
788 if (spftree
->family
== AF_INET6
&& !circuit
->ipv6_router
)
791 * Add IP(v6) addresses of this circuit
793 if (spftree
->family
== AF_INET
&& !spftree
->hopcount_metric
) {
794 memset(&ip_info
, 0, sizeof(ip_info
));
795 ip_info
.dest
.family
= AF_INET
;
796 for (ALL_LIST_ELEMENTS_RO(circuit
->ip_addrs
, ipnode
,
798 ip_info
.dest
.u
.prefix4
= ipv4
->prefix
;
799 ip_info
.dest
.prefixlen
= ipv4
->prefixlen
;
800 apply_mask(&ip_info
.dest
);
801 isis_spf_add_local(spftree
,
802 VTYPE_IPREACH_INTERNAL
,
803 &ip_info
, NULL
, 0, parent
);
806 if (spftree
->family
== AF_INET6
&& !spftree
->hopcount_metric
) {
807 memset(&ip_info
, 0, sizeof(ip_info
));
808 ip_info
.dest
.family
= AF_INET6
;
809 for (ALL_LIST_ELEMENTS_RO(circuit
->ipv6_non_link
,
811 ip_info
.dest
.u
.prefix6
= ipv6
->prefix
;
812 ip_info
.dest
.prefixlen
= ipv6
->prefixlen
;
813 apply_mask(&ip_info
.dest
);
814 isis_spf_add_local(spftree
,
815 VTYPE_IP6REACH_INTERNAL
,
816 &ip_info
, NULL
, 0, parent
);
819 if (circuit
->circ_type
== CIRCUIT_T_BROADCAST
) {
821 * Add the adjacencies
823 adj_list
= list_new();
824 adjdb
= circuit
->u
.bc
.adjdb
[spftree
->level
- 1];
825 isis_adj_build_up_list(adjdb
, adj_list
);
826 if (listcount(adj_list
) == 0) {
827 list_delete(&adj_list
);
828 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
830 "ISIS-Spf: no L%d adjacencies on circuit %s",
832 circuit
->interface
->name
);
835 for (ALL_LIST_ELEMENTS_RO(adj_list
, anode
, adj
)) {
836 if (!adj_has_mt(adj
, spftree
->mtid
))
838 if (spftree
->mtid
== ISIS_MT_IPV4_UNICAST
839 && !speaks(adj
->nlpids
.nlpids
,
843 switch (adj
->sys_type
) {
844 case ISIS_SYSTYPE_ES
:
845 memcpy(lsp_id
, adj
->sysid
,
847 LSP_PSEUDO_ID(lsp_id
) = 0;
849 spftree
, VTYPE_ES
, lsp_id
, adj
,
850 spftree
->hopcount_metric
? 1 :
852 [spftree
->level
- 1],
855 case ISIS_SYSTYPE_IS
:
856 case ISIS_SYSTYPE_L1_IS
:
857 case ISIS_SYSTYPE_L2_IS
:
858 memcpy(lsp_id
, adj
->sysid
,
860 LSP_PSEUDO_ID(lsp_id
) = 0;
861 LSP_FRAGMENT(lsp_id
) = 0;
864 spftree
->area
->oldmetric
866 : VTYPE_NONPSEUDO_TE_IS
,
868 spftree
->hopcount_metric
? 1 :
870 [spftree
->level
- 1],
875 ->lspdb
[spftree
->level
878 || lsp
->hdr
.rem_lifetime
== 0)
880 "ISIS-Spf: No LSP %s found for IS adjacency "
882 rawlspid_print(lsp_id
),
884 circuit
->interface
->name
,
885 circuit
->circuit_id
);
887 case ISIS_SYSTYPE_UNKNOWN
:
890 "isis_spf_preload_tent unknown adj type");
893 list_delete(&adj_list
);
897 if (spftree
->level
== 1)
898 memcpy(lsp_id
, circuit
->u
.bc
.l1_desig_is
,
899 ISIS_SYS_ID_LEN
+ 1);
901 memcpy(lsp_id
, circuit
->u
.bc
.l2_desig_is
,
902 ISIS_SYS_ID_LEN
+ 1);
903 /* can happen during DR reboot */
904 if (memcmp(lsp_id
, null_lsp_id
, ISIS_SYS_ID_LEN
+ 1)
906 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
908 "ISIS-Spf: No L%d DR on %s (ID %d)",
910 circuit
->interface
->name
,
911 circuit
->circuit_id
);
914 adj
= isis_adj_lookup(lsp_id
, adjdb
);
915 /* if no adj, we are the dis or error */
916 if (!adj
&& !circuit
->u
.bc
.is_dr
[spftree
->level
- 1]) {
918 "ISIS-Spf: No adjacency found from root "
919 "to L%d DR %s on %s (ID %d)",
920 spftree
->level
, rawlspid_print(lsp_id
),
921 circuit
->interface
->name
,
922 circuit
->circuit_id
);
927 spftree
->area
->lspdb
[spftree
->level
- 1]);
928 if (lsp
== NULL
|| lsp
->hdr
.rem_lifetime
== 0) {
930 "ISIS-Spf: No lsp (%p) found from root "
931 "to L%d DR %s on %s (ID %d)",
932 (void *)lsp
, spftree
->level
,
933 rawlspid_print(lsp_id
),
934 circuit
->interface
->name
,
935 circuit
->circuit_id
);
938 isis_spf_process_lsp(spftree
, lsp
,
939 spftree
->hopcount_metric
?
940 1 : circuit
->te_metric
[spftree
->level
- 1],
941 0, root_sysid
, parent
);
942 } else if (circuit
->circ_type
== CIRCUIT_T_P2P
) {
943 adj
= circuit
->u
.p2p
.neighbor
;
944 if (!adj
|| adj
->adj_state
!= ISIS_ADJ_UP
)
946 if (!adj_has_mt(adj
, spftree
->mtid
))
948 switch (adj
->sys_type
) {
949 case ISIS_SYSTYPE_ES
:
950 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
951 LSP_PSEUDO_ID(lsp_id
) = 0;
953 spftree
, VTYPE_ES
, lsp_id
, adj
,
954 spftree
->hopcount_metric
? 1 :
955 circuit
->te_metric
[spftree
->level
- 1],
958 case ISIS_SYSTYPE_IS
:
959 case ISIS_SYSTYPE_L1_IS
:
960 case ISIS_SYSTYPE_L2_IS
:
961 memcpy(lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
962 LSP_PSEUDO_ID(lsp_id
) = 0;
963 LSP_FRAGMENT(lsp_id
) = 0;
964 if (spftree
->mtid
!= ISIS_MT_IPV4_UNICAST
965 || speaks(adj
->nlpids
.nlpids
,
970 spftree
->area
->oldmetric
972 : VTYPE_NONPSEUDO_TE_IS
,
974 spftree
->hopcount_metric
? 1 :
976 [spftree
->level
- 1],
979 case ISIS_SYSTYPE_UNKNOWN
:
982 "isis_spf_preload_tent unknown adj type");
985 } else if (circuit
->circ_type
== CIRCUIT_T_LOOPBACK
) {
988 zlog_warn("isis_spf_preload_tent unsupported media");
989 retval
= ISIS_WARNING
;
997 * The parent(s) for vertex is set when added to TENT list
998 * now we just put the child pointer(s) in place
1000 static void add_to_paths(struct isis_spftree
*spftree
,
1001 struct isis_vertex
*vertex
)
1003 char buff
[VID2STR_BUFFER
];
1005 if (isis_find_vertex(&spftree
->paths
, &vertex
->N
, vertex
->type
))
1007 isis_vertex_queue_append(&spftree
->paths
, vertex
);
1009 #ifdef EXTREME_DEBUG
1010 zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
1011 print_sys_hostname(vertex
->N
.id
), vtype2string(vertex
->type
),
1012 vid2string(vertex
, buff
, sizeof(buff
)), vertex
->depth
,
1014 #endif /* EXTREME_DEBUG */
1016 if (VTYPE_IP(vertex
->type
)) {
1017 if (listcount(vertex
->Adj_N
) > 0)
1018 isis_route_create(&vertex
->N
.ip
.dest
,
1020 vertex
->d_N
, vertex
->depth
,
1021 vertex
->Adj_N
, spftree
->area
,
1022 spftree
->route_table
);
1023 else if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1025 "ISIS-Spf: no adjacencies do not install route for "
1026 "%s depth %d dist %d",
1027 vid2string(vertex
, buff
, sizeof(buff
)),
1028 vertex
->depth
, vertex
->d_N
);
1034 static void init_spt(struct isis_spftree
*spftree
, int mtid
, int level
,
1035 int family
, enum spf_tree_id tree_id
,
1036 bool hopcount_metric
)
1038 isis_vertex_queue_clear(&spftree
->tents
);
1039 isis_vertex_queue_clear(&spftree
->paths
);
1041 spftree
->mtid
= mtid
;
1042 spftree
->level
= level
;
1043 spftree
->family
= family
;
1044 spftree
->tree_id
= tree_id
;
1045 spftree
->hopcount_metric
= hopcount_metric
;
1048 static void isis_spf_loop(struct isis_spftree
*spftree
,
1049 uint8_t *root_sysid
)
1051 struct isis_vertex
*vertex
;
1052 struct isis_lsp
*lsp
;
1054 while (isis_vertex_queue_count(&spftree
->tents
)) {
1055 vertex
= isis_vertex_queue_pop(&spftree
->tents
);
1057 #ifdef EXTREME_DEBUG
1059 "ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
1060 print_sys_hostname(vertex
->N
.id
),
1061 vtype2string(vertex
->type
), vertex
->depth
, vertex
->d_N
);
1062 #endif /* EXTREME_DEBUG */
1064 add_to_paths(spftree
, vertex
);
1065 if (!VTYPE_IS(vertex
->type
))
1068 lsp
= lsp_for_vertex(spftree
, vertex
);
1070 zlog_warn("ISIS-Spf: No LSP found for %s",
1071 isis_format_id(vertex
->N
.id
,
1072 sizeof(vertex
->N
.id
)));
1076 isis_spf_process_lsp(spftree
, lsp
, vertex
->d_N
, vertex
->depth
,
1077 root_sysid
, vertex
);
1081 struct isis_spftree
*isis_run_hopcount_spf(struct isis_area
*area
,
1083 struct isis_spftree
*spftree
)
1086 spftree
= isis_spftree_new(area
);
1088 init_spt(spftree
, ISIS_MT_IPV4_UNICAST
, ISIS_LEVEL2
,
1089 AF_INET
, SPFTREE_IPV4
, true);
1090 if (!memcmp(sysid
, isis
->sysid
, ISIS_SYS_ID_LEN
)) {
1091 /* If we are running locally, initialize with information from adjacencies */
1092 struct isis_vertex
*root
= isis_spf_add_root(spftree
, sysid
);
1093 isis_spf_preload_tent(spftree
, sysid
, root
);
1095 isis_vertex_queue_insert(&spftree
->tents
, isis_vertex_new(
1097 VTYPE_NONPSEUDO_TE_IS
));
1100 isis_spf_loop(spftree
, sysid
);
1105 static int isis_run_spf(struct isis_area
*area
, int level
,
1106 enum spf_tree_id tree_id
,
1107 uint8_t *sysid
, struct timeval
*nowtv
)
1109 int retval
= ISIS_OK
;
1110 struct isis_vertex
*root_vertex
;
1111 struct isis_spftree
*spftree
= area
->spftree
[tree_id
][level
- 1];
1112 struct timeval time_now
;
1113 unsigned long long start_time
, end_time
;
1116 /* Get time that can't roll backwards. */
1117 start_time
= nowtv
->tv_sec
;
1118 start_time
= (start_time
* 1000000) + nowtv
->tv_usec
;
1124 mtid
= ISIS_MT_IPV4_UNICAST
;
1128 mtid
= isis_area_ipv6_topology(area
);
1130 case SPFTREE_DSTSRC
:
1132 mtid
= ISIS_MT_IPV6_DSTSRC
;
1135 assert(!"isis_run_spf should never be called with SPFTREE_COUNT as argument!");
1136 return ISIS_WARNING
;
1145 init_spt(spftree
, mtid
, level
, family
, tree_id
, false);
1147 root_vertex
= isis_spf_add_root(spftree
, sysid
);
1149 retval
= isis_spf_preload_tent(spftree
, sysid
, root_vertex
);
1150 if (retval
!= ISIS_OK
) {
1151 zlog_warn("ISIS-Spf: failed to load TENT SPF-root:%s",
1152 print_sys_hostname(sysid
));
1159 if (!isis_vertex_queue_count(&spftree
->tents
)
1160 && (isis
->debugs
& DEBUG_SPF_EVENTS
)) {
1161 zlog_warn("ISIS-Spf: TENT is empty SPF-root:%s",
1162 print_sys_hostname(sysid
));
1165 isis_spf_loop(spftree
, sysid
);
1167 spftree
->runcount
++;
1168 spftree
->last_run_timestamp
= time(NULL
);
1169 spftree
->last_run_monotime
= monotime(&time_now
);
1170 end_time
= time_now
.tv_sec
;
1171 end_time
= (end_time
* 1000000) + time_now
.tv_usec
;
1172 spftree
->last_run_duration
= end_time
- start_time
;
1177 void isis_spf_verify_routes(struct isis_area
*area
, struct isis_spftree
**trees
)
1179 if (area
->is_type
== IS_LEVEL_1
) {
1180 isis_route_verify_table(area
, trees
[0]->route_table
);
1181 } else if (area
->is_type
== IS_LEVEL_2
) {
1182 isis_route_verify_table(area
, trees
[1]->route_table
);
1184 isis_route_verify_merge(area
, trees
[0]->route_table
,
1185 trees
[1]->route_table
);
1189 void isis_spf_invalidate_routes(struct isis_spftree
*tree
)
1191 isis_route_invalidate_table(tree
->area
, tree
->route_table
);
1194 static int isis_run_spf_cb(struct thread
*thread
)
1196 struct isis_spf_run
*run
= THREAD_ARG(thread
);
1197 struct isis_area
*area
= run
->area
;
1198 int level
= run
->level
;
1199 int retval
= ISIS_OK
;
1201 XFREE(MTYPE_ISIS_SPF_RUN
, run
);
1202 area
->spf_timer
[level
- 1] = NULL
;
1204 if (!(area
->is_type
& level
)) {
1205 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1206 zlog_warn("ISIS-SPF (%s) area does not share level",
1208 return ISIS_WARNING
;
1211 isis_area_invalidate_routes(area
, level
);
1213 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1214 zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
1215 area
->area_tag
, level
);
1217 if (area
->ip_circuits
)
1218 retval
= isis_run_spf(area
, level
, SPFTREE_IPV4
, isis
->sysid
,
1220 if (area
->ipv6_circuits
)
1221 retval
= isis_run_spf(area
, level
, SPFTREE_IPV6
, isis
->sysid
,
1223 if (area
->ipv6_circuits
1224 && isis_area_ipv6_dstsrc_enabled(area
))
1225 retval
= isis_run_spf(area
, level
, SPFTREE_DSTSRC
, isis
->sysid
,
1228 isis_area_verify_routes(area
);
1230 /* walk all circuits and reset any spf specific flags */
1231 struct listnode
*node
;
1232 struct isis_circuit
*circuit
;
1233 for (ALL_LIST_ELEMENTS_RO(area
->circuit_list
, node
, circuit
))
1234 UNSET_FLAG(circuit
->flags
, ISIS_CIRCUIT_FLAPPED_AFTER_SPF
);
1236 fabricd_run_spf(area
);
1241 static struct isis_spf_run
*isis_run_spf_arg(struct isis_area
*area
, int level
)
1243 struct isis_spf_run
*run
= XMALLOC(MTYPE_ISIS_SPF_RUN
, sizeof(*run
));
1251 int _isis_spf_schedule(struct isis_area
*area
, int level
,
1252 const char *func
, const char *file
, int line
)
1254 struct isis_spftree
*spftree
= area
->spftree
[SPFTREE_IPV4
][level
- 1];
1255 time_t now
= monotime(NULL
);
1256 int diff
= now
- spftree
->last_run_monotime
;
1259 assert(area
->is_type
& level
);
1261 if (isis
->debugs
& DEBUG_SPF_EVENTS
) {
1263 "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago"
1264 " Caller: %s %s:%d",
1265 area
->area_tag
, level
, diff
, func
, file
, line
);
1268 if (area
->spf_delay_ietf
[level
- 1]) {
1269 /* Need to call schedule function also if spf delay is running
1271 * restart holdoff timer - compare
1272 * draft-ietf-rtgwg-backoff-algo-04 */
1274 spf_backoff_schedule(area
->spf_delay_ietf
[level
- 1]);
1275 if (area
->spf_timer
[level
- 1])
1278 thread_add_timer_msec(master
, isis_run_spf_cb
,
1279 isis_run_spf_arg(area
, level
), delay
,
1280 &area
->spf_timer
[level
- 1]);
1284 if (area
->spf_timer
[level
- 1])
1287 /* wait configured min_spf_interval before doing the SPF */
1289 if (diff
>= area
->min_spf_interval
[level
- 1]) {
1290 /* Last run is more than min interval ago, schedule immediate run */
1293 timer
= area
->min_spf_interval
[level
- 1] - diff
;
1296 thread_add_timer(master
, isis_run_spf_cb
, isis_run_spf_arg(area
, level
),
1297 timer
, &area
->spf_timer
[level
- 1]);
1299 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1300 zlog_debug("ISIS-Spf (%s) L%d SPF scheduled %ld sec from now",
1301 area
->area_tag
, level
, timer
);
1306 static void isis_print_paths(struct vty
*vty
, struct isis_vertex_queue
*queue
,
1307 uint8_t *root_sysid
)
1309 struct listnode
*node
;
1310 struct isis_vertex
*vertex
;
1311 char buff
[VID2STR_BUFFER
];
1314 "Vertex Type Metric Next-Hop Interface Parent\n");
1316 for (ALL_QUEUE_ELEMENTS_RO(queue
, node
, vertex
)) {
1317 if (memcmp(vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
1318 vty_out(vty
, "%-20s %-12s %-6s",
1319 print_sys_hostname(root_sysid
), "", "");
1320 vty_out(vty
, "%-30s\n", "");
1325 struct listnode
*anode
= listhead(vertex
->Adj_N
);
1326 struct listnode
*pnode
= listhead(vertex
->parents
);
1327 struct isis_adjacency
*adj
;
1328 struct isis_vertex
*pvertex
;
1330 vty_out(vty
, "%-20s %-12s %-6u ",
1331 vid2string(vertex
, buff
, sizeof(buff
)),
1332 vtype2string(vertex
->type
), vertex
->d_N
);
1333 for (unsigned int i
= 0;
1334 i
< MAX(vertex
->Adj_N
? listcount(vertex
->Adj_N
) : 0,
1335 vertex
->parents
? listcount(vertex
->parents
) : 0);
1338 adj
= listgetdata(anode
);
1339 anode
= anode
->next
;
1345 pvertex
= listgetdata(pnode
);
1346 pnode
= pnode
->next
;
1353 vty_out(vty
, "%-20s %-12s %-6s ", "", "", "");
1357 vty_out(vty
, "%-20s %-9s ",
1358 print_sys_hostname(adj
->sysid
),
1359 adj
->circuit
->interface
->name
);
1364 vty_out(vty
, "%-20s %-9s ", "", "");
1366 vty_out(vty
, "%s(%d)",
1367 vid2string(pvertex
, buff
, sizeof(buff
)),
1377 static void isis_print_spftree(struct vty
*vty
, int level
,
1378 struct isis_area
*area
,
1379 enum spf_tree_id tree_id
)
1381 const char *tree_id_text
= NULL
;
1385 tree_id_text
= "that speak IP";
1388 tree_id_text
= "that speak IPv6";
1390 case SPFTREE_DSTSRC
:
1391 tree_id_text
= "that support IPv6 dst-src routing";
1394 assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type");
1398 if (!area
->spftree
[tree_id
][level
- 1]
1399 || !isis_vertex_queue_count(
1400 &area
->spftree
[tree_id
][level
- 1]->paths
))
1403 vty_out(vty
, "IS-IS paths to level-%d routers %s\n",
1404 level
, tree_id_text
);
1405 isis_print_paths(vty
, &area
->spftree
[tree_id
][level
- 1]->paths
,
1410 DEFUN (show_isis_topology
,
1411 show_isis_topology_cmd
,
1412 "show " PROTO_NAME
" topology"
1414 " [<level-1|level-2>]"
1418 "IS-IS paths to Intermediate Systems\n"
1420 "Paths to all level-1 routers in the area\n"
1421 "Paths to all level-2 routers in the domain\n"
1426 struct listnode
*node
;
1427 struct isis_area
*area
;
1430 levels
= ISIS_LEVEL1
| ISIS_LEVEL2
;
1431 else if (strmatch(argv
[3]->text
, "level-1"))
1432 levels
= ISIS_LEVEL1
;
1434 levels
= ISIS_LEVEL2
;
1436 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1439 for (ALL_LIST_ELEMENTS_RO(isis
->area_list
, node
, area
)) {
1440 vty_out(vty
, "Area %s:\n",
1441 area
->area_tag
? area
->area_tag
: "null");
1443 for (int level
= ISIS_LEVEL1
; level
<= ISIS_LEVELS
; level
++) {
1444 if ((level
& levels
) == 0)
1447 if (area
->ip_circuits
> 0) {
1448 isis_print_spftree(vty
, level
, area
,
1451 if (area
->ipv6_circuits
> 0) {
1452 isis_print_spftree(vty
, level
, area
,
1455 if (isis_area_ipv6_dstsrc_enabled(area
)) {
1456 isis_print_spftree(vty
, level
, area
,
1461 if (fabricd_spftree(area
)) {
1463 "IS-IS paths to level-2 routers with hop-by-hop metric\n");
1464 isis_print_paths(vty
, &fabricd_spftree(area
)->paths
, isis
->sysid
);
1474 void isis_spf_cmds_init(void)
1476 install_element(VIEW_NODE
, &show_isis_topology_cmd
);
1479 void isis_spf_print(struct isis_spftree
*spftree
, struct vty
*vty
)
1481 vty_out(vty
, " last run elapsed : ");
1482 vty_out_timestr(vty
, spftree
->last_run_timestamp
);
1485 vty_out(vty
, " last run duration : %u usec\n",
1486 (uint32_t)spftree
->last_run_duration
);
1488 vty_out(vty
, " run count : %u\n", spftree
->runcount
);