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
9 * This program is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public Licenseas published by the Free
11 * Software Foundation; either version 2 of the License, or (at your option)
14 * This program is distributed in the hope that it will be useful,but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
37 #include "isis_constants.h"
38 #include "isis_common.h"
39 #include "isis_flags.h"
42 #include "isis_misc.h"
43 #include "isis_adjacency.h"
44 #include "isis_circuit.h"
48 #include "isis_dynhn.h"
50 #include "isis_route.h"
53 int isis_run_spf_l1 (struct thread
*thread
);
54 int isis_run_spf_l2 (struct thread
*thread
);
58 remove_excess_adjs (struct list
*adjs
)
60 struct listnode
*node
, *excess
= NULL
;
61 struct isis_adjacency
*adj
, *candidate
= NULL
;
64 for (ALL_LIST_ELEMENTS_RO (adjs
, node
, adj
))
68 candidate
= listgetdata (excess
);
70 if (candidate
->sys_type
< adj
->sys_type
)
76 if (candidate
->sys_type
> adj
->sys_type
)
79 comp
= memcmp (candidate
->sysid
, adj
->sysid
, ISIS_SYS_ID_LEN
);
89 if (candidate
->circuit
->circuit_id
> adj
->circuit
->circuit_id
)
96 if (candidate
->circuit
->circuit_id
< adj
->circuit
->circuit_id
)
99 comp
= memcmp (candidate
->snpa
, adj
->snpa
, ETH_ALEN
);
108 list_delete_node (adjs
, excess
);
114 vtype2string (enum vertextype vtype
)
118 case VTYPE_PSEUDO_IS
:
121 case VTYPE_PSEUDO_TE_IS
:
122 return "pseudo_TE-IS";
124 case VTYPE_NONPSEUDO_IS
:
127 case VTYPE_NONPSEUDO_TE_IS
:
133 case VTYPE_IPREACH_INTERNAL
:
134 return "IP internal";
136 case VTYPE_IPREACH_EXTERNAL
:
137 return "IP external";
139 case VTYPE_IPREACH_TE
:
143 case VTYPE_IP6REACH_INTERNAL
:
144 return "IP6 internal";
146 case VTYPE_IP6REACH_EXTERNAL
:
147 return "IP6 external";
149 #endif /* HAVE_IPV6 */
153 return NULL
; /* Not reached */
157 vid2string (struct isis_vertex
*vertex
, char * buff
, int size
)
159 switch (vertex
->type
)
161 case VTYPE_PSEUDO_IS
:
162 case VTYPE_PSEUDO_TE_IS
:
163 return print_sys_hostname (vertex
->N
.id
);
165 case VTYPE_NONPSEUDO_IS
:
166 case VTYPE_NONPSEUDO_TE_IS
:
168 return print_sys_hostname (vertex
->N
.id
);
170 case VTYPE_IPREACH_INTERNAL
:
171 case VTYPE_IPREACH_EXTERNAL
:
172 case VTYPE_IPREACH_TE
:
174 case VTYPE_IP6REACH_INTERNAL
:
175 case VTYPE_IP6REACH_EXTERNAL
:
176 #endif /* HAVE_IPV6 */
177 prefix2str ((struct prefix
*) &vertex
->N
.prefix
, buff
, size
);
183 return (char *) buff
;
186 static struct isis_vertex
*
187 isis_vertex_new (void *id
, enum vertextype vtype
)
189 struct isis_vertex
*vertex
;
191 vertex
= XCALLOC (MTYPE_ISIS_VERTEX
, sizeof (struct isis_vertex
));
193 vertex
->type
= vtype
;
197 case VTYPE_NONPSEUDO_IS
:
198 case VTYPE_NONPSEUDO_TE_IS
:
199 memcpy (vertex
->N
.id
, (u_char
*) id
, ISIS_SYS_ID_LEN
);
201 case VTYPE_PSEUDO_IS
:
202 case VTYPE_PSEUDO_TE_IS
:
203 memcpy (vertex
->N
.id
, (u_char
*) id
, ISIS_SYS_ID_LEN
+ 1);
205 case VTYPE_IPREACH_INTERNAL
:
206 case VTYPE_IPREACH_EXTERNAL
:
207 case VTYPE_IPREACH_TE
:
209 case VTYPE_IP6REACH_INTERNAL
:
210 case VTYPE_IP6REACH_EXTERNAL
:
211 #endif /* HAVE_IPV6 */
212 memcpy (&vertex
->N
.prefix
, (struct prefix
*) id
,
213 sizeof (struct prefix
));
219 vertex
->Adj_N
= list_new ();
220 vertex
->parents
= list_new ();
221 vertex
->children
= list_new ();
227 isis_vertex_del (struct isis_vertex
*vertex
)
229 list_delete (vertex
->Adj_N
);
230 vertex
->Adj_N
= NULL
;
231 list_delete (vertex
->parents
);
232 vertex
->parents
= NULL
;
233 list_delete (vertex
->children
);
234 vertex
->children
= NULL
;
236 memset(vertex
, 0, sizeof(struct isis_vertex
));
237 XFREE (MTYPE_ISIS_VERTEX
, vertex
);
243 isis_vertex_adj_del (struct isis_vertex
*vertex
, struct isis_adjacency
*adj
)
245 struct listnode
*node
, *nextnode
;
248 for (node
= listhead (vertex
->Adj_N
); node
; node
= nextnode
)
250 nextnode
= listnextnode(node
);
251 if (listgetdata(node
) == adj
)
252 list_delete_node(vertex
->Adj_N
, node
);
257 struct isis_spftree
*
258 isis_spftree_new (struct isis_area
*area
)
260 struct isis_spftree
*tree
;
262 tree
= XCALLOC (MTYPE_ISIS_SPFTREE
, sizeof (struct isis_spftree
));
265 zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
269 tree
->tents
= list_new ();
270 tree
->paths
= list_new ();
272 tree
->last_run_timestamp
= 0;
273 tree
->last_run_duration
= 0;
280 isis_spftree_del (struct isis_spftree
*spftree
)
282 THREAD_TIMER_OFF (spftree
->t_spf
);
284 spftree
->tents
->del
= (void (*)(void *)) isis_vertex_del
;
285 list_delete (spftree
->tents
);
286 spftree
->tents
= NULL
;
288 spftree
->paths
->del
= (void (*)(void *)) isis_vertex_del
;
289 list_delete (spftree
->paths
);
290 spftree
->paths
= NULL
;
292 XFREE (MTYPE_ISIS_SPFTREE
, spftree
);
298 isis_spftree_adj_del (struct isis_spftree
*spftree
, struct isis_adjacency
*adj
)
300 struct listnode
*node
;
303 for (node
= listhead (spftree
->tents
); node
; node
= listnextnode (node
))
304 isis_vertex_adj_del (listgetdata (node
), adj
);
305 for (node
= listhead (spftree
->paths
); node
; node
= listnextnode (node
))
306 isis_vertex_adj_del (listgetdata (node
), adj
);
311 spftree_area_init (struct isis_area
*area
)
313 if (area
->is_type
& IS_LEVEL_1
)
315 if (area
->spftree
[0] == NULL
)
316 area
->spftree
[0] = isis_spftree_new (area
);
318 if (area
->spftree6
[0] == NULL
)
319 area
->spftree6
[0] = isis_spftree_new (area
);
323 if (area
->is_type
& IS_LEVEL_2
)
325 if (area
->spftree
[1] == NULL
)
326 area
->spftree
[1] = isis_spftree_new (area
);
328 if (area
->spftree6
[1] == NULL
)
329 area
->spftree6
[1] = isis_spftree_new (area
);
337 spftree_area_del (struct isis_area
*area
)
339 if (area
->is_type
& IS_LEVEL_1
)
341 if (area
->spftree
[0] != NULL
)
343 isis_spftree_del (area
->spftree
[0]);
344 area
->spftree
[0] = NULL
;
347 if (area
->spftree6
[0])
349 isis_spftree_del (area
->spftree6
[0]);
350 area
->spftree6
[0] = NULL
;
355 if (area
->is_type
& IS_LEVEL_2
)
357 if (area
->spftree
[1] != NULL
)
359 isis_spftree_del (area
->spftree
[1]);
360 area
->spftree
[1] = NULL
;
363 if (area
->spftree6
[1] != NULL
)
365 isis_spftree_del (area
->spftree6
[1]);
366 area
->spftree6
[1] = NULL
;
375 spftree_area_adj_del (struct isis_area
*area
, struct isis_adjacency
*adj
)
377 if (area
->is_type
& IS_LEVEL_1
)
379 if (area
->spftree
[0] != NULL
)
380 isis_spftree_adj_del (area
->spftree
[0], adj
);
382 if (area
->spftree6
[0] != NULL
)
383 isis_spftree_adj_del (area
->spftree6
[0], adj
);
387 if (area
->is_type
& IS_LEVEL_2
)
389 if (area
->spftree
[1] != NULL
)
390 isis_spftree_adj_del (area
->spftree
[1], adj
);
392 if (area
->spftree6
[1] != NULL
)
393 isis_spftree_adj_del (area
->spftree6
[1], adj
);
401 * Find the system LSP: returns the LSP in our LSP database
402 * associated with the given system ID.
404 static struct isis_lsp
*
405 isis_root_system_lsp (struct isis_area
*area
, int level
, u_char
*sysid
)
407 struct isis_lsp
*lsp
;
408 u_char lspid
[ISIS_SYS_ID_LEN
+ 2];
410 memcpy (lspid
, sysid
, ISIS_SYS_ID_LEN
);
411 LSP_PSEUDO_ID (lspid
) = 0;
412 LSP_FRAGMENT (lspid
) = 0;
413 lsp
= lsp_search (lspid
, area
->lspdb
[level
- 1]);
414 if (lsp
&& lsp
->lsp_header
->rem_lifetime
!= 0)
420 * Add this IS to the root of SPT
422 static struct isis_vertex
*
423 isis_spf_add_root (struct isis_spftree
*spftree
, int level
, u_char
*sysid
)
425 struct isis_vertex
*vertex
;
426 struct isis_lsp
*lsp
;
428 char buff
[PREFIX2STR_BUFFER
];
429 #endif /* EXTREME_DEBUG */
431 lsp
= isis_root_system_lsp (spftree
->area
, level
, sysid
);
433 zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level
);
435 if (!spftree
->area
->oldmetric
)
436 vertex
= isis_vertex_new (sysid
, VTYPE_NONPSEUDO_TE_IS
);
438 vertex
= isis_vertex_new (sysid
, VTYPE_NONPSEUDO_IS
);
440 listnode_add (spftree
->paths
, vertex
);
443 zlog_debug ("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
444 vtype2string (vertex
->type
), vid2string (vertex
, buff
, sizeof (buff
)),
445 vertex
->depth
, vertex
->d_N
);
446 #endif /* EXTREME_DEBUG */
451 static struct isis_vertex
*
452 isis_find_vertex (struct list
*list
, void *id
, enum vertextype vtype
)
454 struct listnode
*node
;
455 struct isis_vertex
*vertex
;
456 struct prefix
*p1
, *p2
;
458 for (ALL_LIST_ELEMENTS_RO (list
, node
, vertex
))
460 if (vertex
->type
!= vtype
)
465 case VTYPE_NONPSEUDO_IS
:
466 case VTYPE_NONPSEUDO_TE_IS
:
467 if (memcmp ((u_char
*) id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
) == 0)
470 case VTYPE_PSEUDO_IS
:
471 case VTYPE_PSEUDO_TE_IS
:
472 if (memcmp ((u_char
*) id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1) == 0)
475 case VTYPE_IPREACH_INTERNAL
:
476 case VTYPE_IPREACH_EXTERNAL
:
477 case VTYPE_IPREACH_TE
:
479 case VTYPE_IP6REACH_INTERNAL
:
480 case VTYPE_IP6REACH_EXTERNAL
:
481 #endif /* HAVE_IPV6 */
482 p1
= (struct prefix
*) id
;
483 p2
= (struct prefix
*) &vertex
->N
.id
;
484 if (p1
->family
== p2
->family
&& p1
->prefixlen
== p2
->prefixlen
&&
485 memcmp (&p1
->u
.prefix
, &p2
->u
.prefix
,
486 PSIZE (p1
->prefixlen
)) == 0)
496 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
498 static struct isis_vertex
*
499 isis_spf_add2tent (struct isis_spftree
*spftree
, enum vertextype vtype
,
500 void *id
, uint32_t cost
, int depth
, int family
,
501 struct isis_adjacency
*adj
, struct isis_vertex
*parent
)
503 struct isis_vertex
*vertex
, *v
;
504 struct listnode
*node
;
505 struct isis_adjacency
*parent_adj
;
507 char buff
[PREFIX2STR_BUFFER
];
510 assert (isis_find_vertex (spftree
->paths
, id
, vtype
) == NULL
);
511 assert (isis_find_vertex (spftree
->tents
, id
, vtype
) == NULL
);
512 vertex
= isis_vertex_new (id
, vtype
);
514 vertex
->depth
= depth
;
517 listnode_add (vertex
->parents
, parent
);
518 if (listnode_lookup (parent
->children
, vertex
) == NULL
)
519 listnode_add (parent
->children
, vertex
);
522 if (parent
&& parent
->Adj_N
&& listcount(parent
->Adj_N
) > 0) {
523 for (ALL_LIST_ELEMENTS_RO (parent
->Adj_N
, node
, parent_adj
))
524 listnode_add (vertex
->Adj_N
, parent_adj
);
526 listnode_add (vertex
->Adj_N
, adj
);
530 zlog_debug ("ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
531 print_sys_hostname (vertex
->N
.id
),
532 vtype2string (vertex
->type
), vid2string (vertex
, buff
, sizeof (buff
)),
533 vertex
->depth
, vertex
->d_N
, listcount(vertex
->Adj_N
));
534 #endif /* EXTREME_DEBUG */
536 if (list_isempty (spftree
->tents
))
538 listnode_add (spftree
->tents
, vertex
);
542 /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */
543 for (node
= listhead (spftree
->tents
); node
; node
= listnextnode (node
))
545 v
= listgetdata (node
);
546 if (v
->d_N
> vertex
->d_N
)
548 list_add_node_prev (spftree
->tents
, node
, vertex
);
551 else if (v
->d_N
== vertex
->d_N
&& v
->type
> vertex
->type
)
553 /* Tie break, add according to type */
554 list_add_node_prev (spftree
->tents
, node
, vertex
);
560 listnode_add (spftree
->tents
, vertex
);
566 isis_spf_add_local (struct isis_spftree
*spftree
, enum vertextype vtype
,
567 void *id
, struct isis_adjacency
*adj
, uint32_t cost
,
568 int family
, struct isis_vertex
*parent
)
570 struct isis_vertex
*vertex
;
572 vertex
= isis_find_vertex (spftree
->tents
, id
, vtype
);
577 if (vertex
->d_N
== cost
)
580 listnode_add (vertex
->Adj_N
, adj
);
582 if (listcount (vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
583 remove_excess_adjs (vertex
->Adj_N
);
584 if (parent
&& (listnode_lookup (vertex
->parents
, parent
) == NULL
))
585 listnode_add (vertex
->parents
, parent
);
586 if (parent
&& (listnode_lookup (parent
->children
, vertex
) == NULL
))
587 listnode_add (parent
->children
, vertex
);
590 else if (vertex
->d_N
< cost
)
595 else { /* vertex->d_N > cost */
597 struct listnode
*pnode
, *pnextnode
;
598 struct isis_vertex
*pvertex
;
599 listnode_delete (spftree
->tents
, vertex
);
600 assert (listcount (vertex
->children
) == 0);
601 for (ALL_LIST_ELEMENTS (vertex
->parents
, pnode
, pnextnode
, pvertex
))
602 listnode_delete(pvertex
->children
, vertex
);
603 isis_vertex_del (vertex
);
607 isis_spf_add2tent (spftree
, vtype
, id
, cost
, 1, family
, adj
, parent
);
612 process_N (struct isis_spftree
*spftree
, enum vertextype vtype
, void *id
,
613 uint32_t dist
, uint16_t depth
, int family
,
614 struct isis_vertex
*parent
)
616 struct isis_vertex
*vertex
;
618 char buff
[PREFIX2STR_BUFFER
];
621 assert (spftree
&& parent
);
623 /* RFC3787 section 5.1 */
624 if (spftree
->area
->newmetric
== 1)
626 if (dist
> MAX_WIDE_PATH_METRIC
)
630 else if (spftree
->area
->oldmetric
== 1)
632 if (dist
> MAX_NARROW_PATH_METRIC
)
637 vertex
= isis_find_vertex (spftree
->paths
, id
, vtype
);
641 zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
642 print_sys_hostname (vertex
->N
.id
),
643 vtype2string (vtype
), vid2string (vertex
, buff
, sizeof (buff
)), dist
);
644 #endif /* EXTREME_DEBUG */
645 assert (dist
>= vertex
->d_N
);
649 vertex
= isis_find_vertex (spftree
->tents
, id
, vtype
);
655 zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
656 print_sys_hostname (vertex
->N
.id
),
657 vtype2string (vtype
), vid2string (vertex
, buff
, sizeof (buff
)), dist
,
658 (parent
? print_sys_hostname (parent
->N
.id
) : "null"),
659 (parent
? listcount (parent
->Adj_N
) : 0));
660 #endif /* EXTREME_DEBUG */
661 if (vertex
->d_N
== dist
)
663 struct listnode
*node
;
664 struct isis_adjacency
*parent_adj
;
665 for (ALL_LIST_ELEMENTS_RO (parent
->Adj_N
, node
, parent_adj
))
666 if (listnode_lookup(vertex
->Adj_N
, parent_adj
) == NULL
)
667 listnode_add (vertex
->Adj_N
, parent_adj
);
669 if (listcount (vertex
->Adj_N
) > ISIS_MAX_PATH_SPLITS
)
670 remove_excess_adjs (vertex
->Adj_N
);
671 if (listnode_lookup (vertex
->parents
, parent
) == NULL
)
672 listnode_add (vertex
->parents
, parent
);
673 if (listnode_lookup (parent
->children
, vertex
) == NULL
)
674 listnode_add (parent
->children
, vertex
);
678 else if (vertex
->d_N
< dist
)
685 struct listnode
*pnode
, *pnextnode
;
686 struct isis_vertex
*pvertex
;
687 listnode_delete (spftree
->tents
, vertex
);
688 assert (listcount (vertex
->children
) == 0);
689 for (ALL_LIST_ELEMENTS (vertex
->parents
, pnode
, pnextnode
, pvertex
))
690 listnode_delete(pvertex
->children
, vertex
);
691 isis_vertex_del (vertex
);
696 zlog_debug ("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
697 print_sys_hostname(id
), vtype2string (vtype
), dist
,
698 (parent
? print_sys_hostname (parent
->N
.id
) : "null"));
699 #endif /* EXTREME_DEBUG */
701 isis_spf_add2tent (spftree
, vtype
, id
, dist
, depth
, family
, NULL
, parent
);
709 isis_spf_process_lsp (struct isis_spftree
*spftree
, struct isis_lsp
*lsp
,
710 uint32_t cost
, uint16_t depth
, int family
,
711 u_char
*root_sysid
, struct isis_vertex
*parent
)
713 struct listnode
*node
, *fragnode
= NULL
;
715 struct is_neigh
*is_neigh
;
716 struct te_is_neigh
*te_is_neigh
;
717 struct ipv4_reachability
*ipreach
;
718 struct te_ipv4_reachability
*te_ipv4_reach
;
719 enum vertextype vtype
;
720 struct prefix prefix
;
722 struct ipv6_reachability
*ip6reach
;
723 #endif /* HAVE_IPV6 */
724 static const u_char null_sysid
[ISIS_SYS_ID_LEN
];
726 if (!speaks (lsp
->tlv_data
.nlpids
, family
))
730 if (lsp
->lsp_header
->seq_num
== 0)
732 zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
737 zlog_debug ("ISIS-Spf: process_lsp %s", print_sys_hostname(lsp
->lsp_header
->lsp_id
));
738 #endif /* EXTREME_DEBUG */
740 if (!ISIS_MASK_LSP_OL_BIT (lsp
->lsp_header
->lsp_bits
))
742 if (lsp
->tlv_data
.is_neighs
)
744 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.is_neighs
, node
, is_neigh
))
747 /* Two way connectivity */
748 if (!memcmp (is_neigh
->neigh_id
, root_sysid
, ISIS_SYS_ID_LEN
))
750 if (!memcmp (is_neigh
->neigh_id
, null_sysid
, ISIS_SYS_ID_LEN
))
752 dist
= cost
+ is_neigh
->metrics
.metric_default
;
753 vtype
= LSP_PSEUDO_ID (is_neigh
->neigh_id
) ? VTYPE_PSEUDO_IS
754 : VTYPE_NONPSEUDO_IS
;
755 process_N (spftree
, vtype
, (void *) is_neigh
->neigh_id
, dist
,
756 depth
+ 1, family
, parent
);
759 if (lsp
->tlv_data
.te_is_neighs
)
761 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.te_is_neighs
, node
,
764 if (!memcmp (te_is_neigh
->neigh_id
, root_sysid
, ISIS_SYS_ID_LEN
))
766 if (!memcmp (te_is_neigh
->neigh_id
, null_sysid
, ISIS_SYS_ID_LEN
))
768 dist
= cost
+ GET_TE_METRIC(te_is_neigh
);
769 vtype
= LSP_PSEUDO_ID (te_is_neigh
->neigh_id
) ? VTYPE_PSEUDO_TE_IS
770 : VTYPE_NONPSEUDO_TE_IS
;
771 process_N (spftree
, vtype
, (void *) te_is_neigh
->neigh_id
, dist
,
772 depth
+ 1, family
, parent
);
777 if (family
== AF_INET
&& lsp
->tlv_data
.ipv4_int_reachs
)
779 prefix
.family
= AF_INET
;
780 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.ipv4_int_reachs
, node
, ipreach
))
782 dist
= cost
+ ipreach
->metrics
.metric_default
;
783 vtype
= VTYPE_IPREACH_INTERNAL
;
784 prefix
.u
.prefix4
= ipreach
->prefix
;
785 prefix
.prefixlen
= ip_masklen (ipreach
->mask
);
786 apply_mask (&prefix
);
787 process_N (spftree
, vtype
, (void *) &prefix
, dist
, depth
+ 1,
791 if (family
== AF_INET
&& lsp
->tlv_data
.ipv4_ext_reachs
)
793 prefix
.family
= AF_INET
;
794 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.ipv4_ext_reachs
, node
, ipreach
))
796 dist
= cost
+ ipreach
->metrics
.metric_default
;
797 vtype
= VTYPE_IPREACH_EXTERNAL
;
798 prefix
.u
.prefix4
= ipreach
->prefix
;
799 prefix
.prefixlen
= ip_masklen (ipreach
->mask
);
800 apply_mask (&prefix
);
801 process_N (spftree
, vtype
, (void *) &prefix
, dist
, depth
+ 1,
805 if (family
== AF_INET
&& lsp
->tlv_data
.te_ipv4_reachs
)
807 prefix
.family
= AF_INET
;
808 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.te_ipv4_reachs
,
809 node
, te_ipv4_reach
))
811 assert ((te_ipv4_reach
->control
& 0x3F) <= IPV4_MAX_BITLEN
);
813 dist
= cost
+ ntohl (te_ipv4_reach
->te_metric
);
814 vtype
= VTYPE_IPREACH_TE
;
815 prefix
.u
.prefix4
= newprefix2inaddr (&te_ipv4_reach
->prefix_start
,
816 te_ipv4_reach
->control
);
817 prefix
.prefixlen
= (te_ipv4_reach
->control
& 0x3F);
818 apply_mask (&prefix
);
819 process_N (spftree
, vtype
, (void *) &prefix
, dist
, depth
+ 1,
824 if (family
== AF_INET6
&& lsp
->tlv_data
.ipv6_reachs
)
826 prefix
.family
= AF_INET6
;
827 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.ipv6_reachs
, node
, ip6reach
))
829 assert (ip6reach
->prefix_len
<= IPV6_MAX_BITLEN
);
831 dist
= cost
+ ntohl(ip6reach
->metric
);
832 vtype
= (ip6reach
->control_info
& CTRL_INFO_DISTRIBUTION
) ?
833 VTYPE_IP6REACH_EXTERNAL
: VTYPE_IP6REACH_INTERNAL
;
834 prefix
.prefixlen
= ip6reach
->prefix_len
;
835 memcpy (&prefix
.u
.prefix6
.s6_addr
, ip6reach
->prefix
,
836 PSIZE (ip6reach
->prefix_len
));
837 apply_mask (&prefix
);
838 process_N (spftree
, vtype
, (void *) &prefix
, dist
, depth
+ 1,
842 #endif /* HAVE_IPV6 */
844 if (fragnode
== NULL
)
845 fragnode
= listhead (lsp
->lspu
.frags
);
847 fragnode
= listnextnode (fragnode
);
851 lsp
= listgetdata (fragnode
);
859 isis_spf_process_pseudo_lsp (struct isis_spftree
*spftree
,
860 struct isis_lsp
*lsp
, uint32_t cost
,
861 uint16_t depth
, int family
,
863 struct isis_vertex
*parent
)
865 struct listnode
*node
, *fragnode
= NULL
;
866 struct is_neigh
*is_neigh
;
867 struct te_is_neigh
*te_is_neigh
;
868 enum vertextype vtype
;
873 if (lsp
->lsp_header
->seq_num
== 0)
875 zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
876 " - do not process");
881 zlog_debug ("ISIS-Spf: process_pseudo_lsp %s",
882 print_sys_hostname(lsp
->lsp_header
->lsp_id
));
883 #endif /* EXTREME_DEBUG */
885 /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
887 if (lsp
->tlv_data
.is_neighs
)
888 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.is_neighs
, node
, is_neigh
))
890 /* Two way connectivity */
891 if (!memcmp (is_neigh
->neigh_id
, root_sysid
, ISIS_SYS_ID_LEN
))
893 dist
= cost
+ is_neigh
->metrics
.metric_default
;
894 vtype
= LSP_PSEUDO_ID (is_neigh
->neigh_id
) ? VTYPE_PSEUDO_IS
895 : VTYPE_NONPSEUDO_IS
;
896 process_N (spftree
, vtype
, (void *) is_neigh
->neigh_id
, dist
,
897 depth
+ 1, family
, parent
);
899 if (lsp
->tlv_data
.te_is_neighs
)
900 for (ALL_LIST_ELEMENTS_RO (lsp
->tlv_data
.te_is_neighs
, node
, te_is_neigh
))
902 /* Two way connectivity */
903 if (!memcmp (te_is_neigh
->neigh_id
, root_sysid
, ISIS_SYS_ID_LEN
))
905 dist
= cost
+ GET_TE_METRIC(te_is_neigh
);
906 vtype
= LSP_PSEUDO_ID (te_is_neigh
->neigh_id
) ? VTYPE_PSEUDO_TE_IS
907 : VTYPE_NONPSEUDO_TE_IS
;
908 process_N (spftree
, vtype
, (void *) te_is_neigh
->neigh_id
, dist
,
909 depth
+ 1, family
, parent
);
912 if (fragnode
== NULL
)
913 fragnode
= listhead (lsp
->lspu
.frags
);
915 fragnode
= listnextnode (fragnode
);
919 lsp
= listgetdata (fragnode
);
927 isis_spf_preload_tent (struct isis_spftree
*spftree
, int level
,
928 int family
, u_char
*root_sysid
,
929 struct isis_vertex
*parent
)
931 struct isis_circuit
*circuit
;
932 struct listnode
*cnode
, *anode
, *ipnode
;
933 struct isis_adjacency
*adj
;
934 struct isis_lsp
*lsp
;
935 struct list
*adj_list
;
937 struct prefix_ipv4
*ipv4
;
938 struct prefix prefix
;
939 int retval
= ISIS_OK
;
940 u_char lsp_id
[ISIS_SYS_ID_LEN
+ 2];
941 static u_char null_lsp_id
[ISIS_SYS_ID_LEN
+ 2];
943 struct prefix_ipv6
*ipv6
;
944 #endif /* HAVE_IPV6 */
946 for (ALL_LIST_ELEMENTS_RO (spftree
->area
->circuit_list
, cnode
, circuit
))
948 if (circuit
->state
!= C_STATE_UP
)
950 if (!(circuit
->is_type
& level
))
952 if (family
== AF_INET
&& !circuit
->ip_router
)
955 if (family
== AF_INET6
&& !circuit
->ipv6_router
)
957 #endif /* HAVE_IPV6 */
959 * Add IP(v6) addresses of this circuit
961 if (family
== AF_INET
)
963 prefix
.family
= AF_INET
;
964 for (ALL_LIST_ELEMENTS_RO (circuit
->ip_addrs
, ipnode
, ipv4
))
966 prefix
.u
.prefix4
= ipv4
->prefix
;
967 prefix
.prefixlen
= ipv4
->prefixlen
;
968 apply_mask (&prefix
);
969 isis_spf_add_local (spftree
, VTYPE_IPREACH_INTERNAL
, &prefix
,
970 NULL
, 0, family
, parent
);
974 if (family
== AF_INET6
)
976 prefix
.family
= AF_INET6
;
977 for (ALL_LIST_ELEMENTS_RO (circuit
->ipv6_non_link
, ipnode
, ipv6
))
979 prefix
.prefixlen
= ipv6
->prefixlen
;
980 prefix
.u
.prefix6
= ipv6
->prefix
;
981 apply_mask (&prefix
);
982 isis_spf_add_local (spftree
, VTYPE_IP6REACH_INTERNAL
,
983 &prefix
, NULL
, 0, family
, parent
);
986 #endif /* HAVE_IPV6 */
987 if (circuit
->circ_type
== CIRCUIT_T_BROADCAST
)
990 * Add the adjacencies
992 adj_list
= list_new ();
993 adjdb
= circuit
->u
.bc
.adjdb
[level
- 1];
994 isis_adj_build_up_list (adjdb
, adj_list
);
995 if (listcount (adj_list
) == 0)
997 list_delete (adj_list
);
998 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
999 zlog_debug ("ISIS-Spf: no L%d adjacencies on circuit %s",
1000 level
, circuit
->interface
->name
);
1003 for (ALL_LIST_ELEMENTS_RO (adj_list
, anode
, adj
))
1005 if (!speaks (&adj
->nlpids
, family
))
1007 switch (adj
->sys_type
)
1009 case ISIS_SYSTYPE_ES
:
1010 isis_spf_add_local (spftree
, VTYPE_ES
, adj
->sysid
, adj
,
1011 circuit
->te_metric
[level
- 1],
1014 case ISIS_SYSTYPE_IS
:
1015 case ISIS_SYSTYPE_L1_IS
:
1016 case ISIS_SYSTYPE_L2_IS
:
1017 isis_spf_add_local (spftree
,
1018 spftree
->area
->oldmetric
?
1019 VTYPE_NONPSEUDO_IS
:
1020 VTYPE_NONPSEUDO_TE_IS
,
1022 circuit
->te_metric
[level
- 1],
1024 memcpy (lsp_id
, adj
->sysid
, ISIS_SYS_ID_LEN
);
1025 LSP_PSEUDO_ID (lsp_id
) = 0;
1026 LSP_FRAGMENT (lsp_id
) = 0;
1027 lsp
= lsp_search (lsp_id
, spftree
->area
->lspdb
[level
- 1]);
1028 if (lsp
== NULL
|| lsp
->lsp_header
->rem_lifetime
== 0)
1029 zlog_warn ("ISIS-Spf: No LSP %s found for IS adjacency "
1030 "L%d on %s (ID %u)",
1031 rawlspid_print (lsp_id
), level
,
1032 circuit
->interface
->name
, circuit
->circuit_id
);
1034 case ISIS_SYSTYPE_UNKNOWN
:
1036 zlog_warn ("isis_spf_preload_tent unknow adj type");
1039 list_delete (adj_list
);
1041 * Add the pseudonode
1044 memcpy (lsp_id
, circuit
->u
.bc
.l1_desig_is
, ISIS_SYS_ID_LEN
+ 1);
1046 memcpy (lsp_id
, circuit
->u
.bc
.l2_desig_is
, ISIS_SYS_ID_LEN
+ 1);
1047 /* can happen during DR reboot */
1048 if (memcmp (lsp_id
, null_lsp_id
, ISIS_SYS_ID_LEN
+ 1) == 0)
1050 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1051 zlog_debug ("ISIS-Spf: No L%d DR on %s (ID %d)",
1052 level
, circuit
->interface
->name
, circuit
->circuit_id
);
1055 adj
= isis_adj_lookup (lsp_id
, adjdb
);
1056 /* if no adj, we are the dis or error */
1057 if (!adj
&& !circuit
->u
.bc
.is_dr
[level
- 1])
1059 zlog_warn ("ISIS-Spf: No adjacency found from root "
1060 "to L%d DR %s on %s (ID %d)",
1061 level
, rawlspid_print (lsp_id
),
1062 circuit
->interface
->name
, circuit
->circuit_id
);
1065 lsp
= lsp_search (lsp_id
, spftree
->area
->lspdb
[level
- 1]);
1066 if (lsp
== NULL
|| lsp
->lsp_header
->rem_lifetime
== 0)
1068 zlog_warn ("ISIS-Spf: No lsp (%p) found from root "
1069 "to L%d DR %s on %s (ID %d)",
1070 lsp
, level
, rawlspid_print (lsp_id
),
1071 circuit
->interface
->name
, circuit
->circuit_id
);
1074 isis_spf_process_pseudo_lsp (spftree
, lsp
,
1075 circuit
->te_metric
[level
- 1], 0,
1076 family
, root_sysid
, parent
);
1078 else if (circuit
->circ_type
== CIRCUIT_T_P2P
)
1080 adj
= circuit
->u
.p2p
.neighbor
;
1083 switch (adj
->sys_type
)
1085 case ISIS_SYSTYPE_ES
:
1086 isis_spf_add_local (spftree
, VTYPE_ES
, adj
->sysid
, adj
,
1087 circuit
->te_metric
[level
- 1], family
,
1090 case ISIS_SYSTYPE_IS
:
1091 case ISIS_SYSTYPE_L1_IS
:
1092 case ISIS_SYSTYPE_L2_IS
:
1093 if (speaks (&adj
->nlpids
, family
))
1094 isis_spf_add_local (spftree
,
1095 spftree
->area
->oldmetric
?
1096 VTYPE_NONPSEUDO_IS
:
1097 VTYPE_NONPSEUDO_TE_IS
,
1099 adj
, circuit
->te_metric
[level
- 1],
1102 case ISIS_SYSTYPE_UNKNOWN
:
1104 zlog_warn ("isis_spf_preload_tent unknown adj type");
1108 else if (circuit
->circ_type
== CIRCUIT_T_LOOPBACK
)
1114 zlog_warn ("isis_spf_preload_tent unsupported media");
1115 retval
= ISIS_WARNING
;
1123 * The parent(s) for vertex is set when added to TENT list
1124 * now we just put the child pointer(s) in place
1127 add_to_paths (struct isis_spftree
*spftree
, struct isis_vertex
*vertex
,
1130 char buff
[PREFIX2STR_BUFFER
];
1132 if (isis_find_vertex (spftree
->paths
, vertex
->N
.id
, vertex
->type
))
1134 listnode_add (spftree
->paths
, vertex
);
1136 #ifdef EXTREME_DEBUG
1137 zlog_debug ("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
1138 print_sys_hostname (vertex
->N
.id
),
1139 vtype2string (vertex
->type
), vid2string (vertex
, buff
, sizeof (buff
)),
1140 vertex
->depth
, vertex
->d_N
);
1141 #endif /* EXTREME_DEBUG */
1143 if (vertex
->type
> VTYPE_ES
)
1145 if (listcount (vertex
->Adj_N
) > 0)
1146 isis_route_create ((struct prefix
*) &vertex
->N
.prefix
, vertex
->d_N
,
1147 vertex
->depth
, vertex
->Adj_N
, spftree
->area
, level
);
1148 else if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1149 zlog_debug ("ISIS-Spf: no adjacencies do not install route for "
1150 "%s depth %d dist %d", vid2string (vertex
, buff
, sizeof (buff
)),
1151 vertex
->depth
, vertex
->d_N
);
1158 init_spt (struct isis_spftree
*spftree
)
1160 spftree
->tents
->del
= spftree
->paths
->del
= (void (*)(void *)) isis_vertex_del
;
1161 list_delete_all_node (spftree
->tents
);
1162 list_delete_all_node (spftree
->paths
);
1163 spftree
->tents
->del
= spftree
->paths
->del
= NULL
;
1168 isis_run_spf (struct isis_area
*area
, int level
, int family
, u_char
*sysid
)
1170 int retval
= ISIS_OK
;
1171 struct listnode
*node
;
1172 struct isis_vertex
*vertex
;
1173 struct isis_vertex
*root_vertex
;
1174 struct isis_spftree
*spftree
= NULL
;
1175 u_char lsp_id
[ISIS_SYS_ID_LEN
+ 2];
1176 struct isis_lsp
*lsp
;
1177 struct route_table
*table
= NULL
;
1178 struct timeval time_now
;
1179 unsigned long long start_time
, end_time
;
1181 /* Get time that can't roll backwards. */
1182 quagga_gettime(QUAGGA_CLK_MONOTONIC
, &time_now
);
1183 start_time
= time_now
.tv_sec
;
1184 start_time
= (start_time
* 1000000) + time_now
.tv_usec
;
1186 if (family
== AF_INET
)
1187 spftree
= area
->spftree
[level
- 1];
1189 else if (family
== AF_INET6
)
1190 spftree
= area
->spftree6
[level
- 1];
1195 /* Make all routes in current route table inactive. */
1196 if (family
== AF_INET
)
1197 table
= area
->route_table
[level
- 1];
1199 else if (family
== AF_INET6
)
1200 table
= area
->route_table6
[level
- 1];
1203 isis_route_invalidate_table (area
, table
);
1210 root_vertex
= isis_spf_add_root (spftree
, level
, sysid
);
1212 retval
= isis_spf_preload_tent (spftree
, level
, family
, sysid
, root_vertex
);
1213 if (retval
!= ISIS_OK
)
1215 zlog_warn ("ISIS-Spf: failed to load TENT SPF-root:%s", print_sys_hostname(sysid
));
1222 if (listcount (spftree
->tents
) == 0)
1224 zlog_warn ("ISIS-Spf: TENT is empty SPF-root:%s", print_sys_hostname(sysid
));
1228 while (listcount (spftree
->tents
) > 0)
1230 node
= listhead (spftree
->tents
);
1231 vertex
= listgetdata (node
);
1233 #ifdef EXTREME_DEBUG
1234 zlog_debug ("ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
1235 print_sys_hostname (vertex
->N
.id
),
1236 vtype2string (vertex
->type
), vertex
->depth
, vertex
->d_N
);
1237 #endif /* EXTREME_DEBUG */
1239 /* Remove from tent list and add to paths list */
1240 list_delete_node (spftree
->tents
, node
);
1241 add_to_paths (spftree
, vertex
, level
);
1242 switch (vertex
->type
)
1244 case VTYPE_PSEUDO_IS
:
1245 case VTYPE_NONPSEUDO_IS
:
1246 case VTYPE_PSEUDO_TE_IS
:
1247 case VTYPE_NONPSEUDO_TE_IS
:
1248 memcpy (lsp_id
, vertex
->N
.id
, ISIS_SYS_ID_LEN
+ 1);
1249 LSP_FRAGMENT (lsp_id
) = 0;
1250 lsp
= lsp_search (lsp_id
, area
->lspdb
[level
- 1]);
1251 if (lsp
&& lsp
->lsp_header
->rem_lifetime
!= 0)
1253 if (LSP_PSEUDO_ID (lsp_id
))
1255 isis_spf_process_pseudo_lsp (spftree
, lsp
, vertex
->d_N
,
1256 vertex
->depth
, family
, sysid
,
1261 isis_spf_process_lsp (spftree
, lsp
, vertex
->d_N
,
1262 vertex
->depth
, family
, sysid
, vertex
);
1267 zlog_warn ("ISIS-Spf: No LSP found for %s",
1268 rawlspid_print (lsp_id
));
1276 isis_route_validate (area
);
1277 spftree
->pending
= 0;
1278 spftree
->runcount
++;
1279 spftree
->last_run_timestamp
= time (NULL
);
1280 quagga_gettime(QUAGGA_CLK_MONOTONIC
, &time_now
);
1281 end_time
= time_now
.tv_sec
;
1282 end_time
= (end_time
* 1000000) + time_now
.tv_usec
;
1283 spftree
->last_run_duration
= end_time
- start_time
;
1290 isis_run_spf_l1 (struct thread
*thread
)
1292 struct isis_area
*area
;
1293 int retval
= ISIS_OK
;
1295 area
= THREAD_ARG (thread
);
1298 area
->spftree
[0]->t_spf
= NULL
;
1299 area
->spftree
[0]->pending
= 0;
1301 if (!(area
->is_type
& IS_LEVEL_1
))
1303 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1304 zlog_warn ("ISIS-SPF (%s) area does not share level",
1306 return ISIS_WARNING
;
1309 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1310 zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area
->area_tag
);
1312 if (area
->ip_circuits
)
1313 retval
= isis_run_spf (area
, 1, AF_INET
, isis
->sysid
);
1319 isis_run_spf_l2 (struct thread
*thread
)
1321 struct isis_area
*area
;
1322 int retval
= ISIS_OK
;
1324 area
= THREAD_ARG (thread
);
1327 area
->spftree
[1]->t_spf
= NULL
;
1328 area
->spftree
[1]->pending
= 0;
1330 if (!(area
->is_type
& IS_LEVEL_2
))
1332 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1333 zlog_warn ("ISIS-SPF (%s) area does not share level", area
->area_tag
);
1334 return ISIS_WARNING
;
1337 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1338 zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area
->area_tag
);
1340 if (area
->ip_circuits
)
1341 retval
= isis_run_spf (area
, 2, AF_INET
, isis
->sysid
);
1347 isis_spf_schedule (struct isis_area
*area
, int level
)
1349 struct isis_spftree
*spftree
= area
->spftree
[level
- 1];
1350 time_t now
= time (NULL
);
1351 int diff
= now
- spftree
->last_run_timestamp
;
1354 assert (area
->is_type
& level
);
1356 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1357 zlog_debug ("ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
1358 area
->area_tag
, level
, diff
);
1360 if (spftree
->pending
)
1363 THREAD_TIMER_OFF (spftree
->t_spf
);
1365 /* wait configured min_spf_interval before doing the SPF */
1366 if (diff
>= area
->min_spf_interval
[level
-1])
1367 return isis_run_spf (area
, level
, AF_INET
, isis
->sysid
);
1370 THREAD_TIMER_ON (master
, spftree
->t_spf
, isis_run_spf_l1
, area
,
1371 area
->min_spf_interval
[0] - diff
);
1373 THREAD_TIMER_ON (master
, spftree
->t_spf
, isis_run_spf_l2
, area
,
1374 area
->min_spf_interval
[1] - diff
);
1376 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1377 zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
1378 area
->area_tag
, level
, area
->min_spf_interval
[level
-1] - diff
);
1380 spftree
->pending
= 1;
1387 isis_run_spf6_l1 (struct thread
*thread
)
1389 struct isis_area
*area
;
1390 int retval
= ISIS_OK
;
1392 area
= THREAD_ARG (thread
);
1395 area
->spftree6
[0]->t_spf
= NULL
;
1396 area
->spftree6
[0]->pending
= 0;
1398 if (!(area
->is_type
& IS_LEVEL_1
))
1400 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1401 zlog_warn ("ISIS-SPF (%s) area does not share level", area
->area_tag
);
1402 return ISIS_WARNING
;
1405 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1406 zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area
->area_tag
);
1408 if (area
->ipv6_circuits
)
1409 retval
= isis_run_spf (area
, 1, AF_INET6
, isis
->sysid
);
1415 isis_run_spf6_l2 (struct thread
*thread
)
1417 struct isis_area
*area
;
1418 int retval
= ISIS_OK
;
1420 area
= THREAD_ARG (thread
);
1423 area
->spftree6
[1]->t_spf
= NULL
;
1424 area
->spftree6
[1]->pending
= 0;
1426 if (!(area
->is_type
& IS_LEVEL_2
))
1428 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1429 zlog_warn ("ISIS-SPF (%s) area does not share level", area
->area_tag
);
1430 return ISIS_WARNING
;
1433 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1434 zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area
->area_tag
);
1436 if (area
->ipv6_circuits
)
1437 retval
= isis_run_spf (area
, 2, AF_INET6
, isis
->sysid
);
1443 isis_spf_schedule6 (struct isis_area
*area
, int level
)
1445 int retval
= ISIS_OK
;
1446 struct isis_spftree
*spftree
= area
->spftree6
[level
- 1];
1447 time_t now
= time (NULL
);
1448 time_t diff
= now
- spftree
->last_run_timestamp
;
1451 assert (area
->is_type
& level
);
1453 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1454 zlog_debug ("ISIS-Spf (%s) L%d SPF schedule called, lastrun %lld sec ago",
1455 area
->area_tag
, level
, (long long)diff
);
1457 if (spftree
->pending
)
1460 THREAD_TIMER_OFF (spftree
->t_spf
);
1462 /* wait configured min_spf_interval before doing the SPF */
1463 if (diff
>= area
->min_spf_interval
[level
-1])
1464 return isis_run_spf (area
, level
, AF_INET6
, isis
->sysid
);
1467 THREAD_TIMER_ON (master
, spftree
->t_spf
, isis_run_spf6_l1
, area
,
1468 area
->min_spf_interval
[0] - diff
);
1470 THREAD_TIMER_ON (master
, spftree
->t_spf
, isis_run_spf6_l2
, area
,
1471 area
->min_spf_interval
[1] - diff
);
1473 if (isis
->debugs
& DEBUG_SPF_EVENTS
)
1474 zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %lld sec from now",
1475 area
->area_tag
, level
, (long long)(area
->min_spf_interval
[level
-1] - diff
));
1477 spftree
->pending
= 1;
1484 isis_print_paths (struct vty
*vty
, struct list
*paths
, u_char
*root_sysid
)
1486 struct listnode
*node
;
1487 struct listnode
*anode
;
1488 struct isis_vertex
*vertex
;
1489 struct isis_adjacency
*adj
;
1490 char buff
[PREFIX2STR_BUFFER
];
1492 vty_out (vty
, "Vertex Type Metric "
1493 "Next-Hop Interface Parent%s", VTY_NEWLINE
);
1495 for (ALL_LIST_ELEMENTS_RO (paths
, node
, vertex
)) {
1496 if (memcmp (vertex
->N
.id
, root_sysid
, ISIS_SYS_ID_LEN
) == 0) {
1497 vty_out (vty
, "%-20s %-12s %-6s", print_sys_hostname (root_sysid
),
1499 vty_out (vty
, "%-30s", "");
1502 vty_out (vty
, "%-20s %-12s %-6u ", vid2string (vertex
, buff
, sizeof (buff
)),
1503 vtype2string (vertex
->type
), vertex
->d_N
);
1504 for (ALL_LIST_ELEMENTS_RO (vertex
->Adj_N
, anode
, adj
)) {
1507 vty_out (vty
, "%s", VTY_NEWLINE
);
1508 vty_out (vty
, "%-20s %-12s %-6s ", "", "", "");
1510 vty_out (vty
, "%-20s %-9s ",
1511 print_sys_hostname (adj
->sysid
),
1512 adj
->circuit
->interface
->name
);
1517 vty_out (vty
, "%-30s ", "");
1520 /* Print list of parents for the ECMP DAG */
1521 if (listcount (vertex
->parents
) > 0) {
1522 struct listnode
*pnode
;
1523 struct isis_vertex
*pvertex
;
1525 for (ALL_LIST_ELEMENTS_RO (vertex
->parents
, pnode
, pvertex
)) {
1527 vty_out (vty
, "%s", VTY_NEWLINE
);
1528 vty_out (vty
, "%-72s", "");
1530 vty_out (vty
, "%s(%d)",
1531 vid2string (pvertex
, buff
, sizeof (buff
)), pvertex
->type
);
1535 vty_out (vty
, " NULL ");
1538 vty_out (vty
, "%s", VTY_NEWLINE
);
1542 DEFUN (show_isis_topology
,
1543 show_isis_topology_cmd
,
1544 "show isis topology",
1546 "IS-IS information\n"
1547 "IS-IS paths to Intermediate Systems\n")
1549 struct listnode
*node
;
1550 struct isis_area
*area
;
1553 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1556 for (ALL_LIST_ELEMENTS_RO (isis
->area_list
, node
, area
))
1558 vty_out (vty
, "Area %s:%s", area
->area_tag
? area
->area_tag
: "null",
1561 for (level
= 0; level
< ISIS_LEVELS
; level
++)
1563 if (area
->ip_circuits
> 0 && area
->spftree
[level
]
1564 && area
->spftree
[level
]->paths
->count
> 0)
1566 vty_out (vty
, "IS-IS paths to level-%d routers that speak IP%s",
1567 level
+ 1, VTY_NEWLINE
);
1568 isis_print_paths (vty
, area
->spftree
[level
]->paths
, isis
->sysid
);
1569 vty_out (vty
, "%s", VTY_NEWLINE
);
1572 if (area
->ipv6_circuits
> 0 && area
->spftree6
[level
]
1573 && area
->spftree6
[level
]->paths
->count
> 0)
1576 "IS-IS paths to level-%d routers that speak IPv6%s",
1577 level
+ 1, VTY_NEWLINE
);
1578 isis_print_paths (vty
, area
->spftree6
[level
]->paths
, isis
->sysid
);
1579 vty_out (vty
, "%s", VTY_NEWLINE
);
1581 #endif /* HAVE_IPV6 */
1584 vty_out (vty
, "%s", VTY_NEWLINE
);
1590 DEFUN (show_isis_topology_l1
,
1591 show_isis_topology_l1_cmd
,
1592 "show isis topology level-1",
1594 "IS-IS information\n"
1595 "IS-IS paths to Intermediate Systems\n"
1596 "Paths to all level-1 routers in the area\n")
1598 struct listnode
*node
;
1599 struct isis_area
*area
;
1601 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1604 for (ALL_LIST_ELEMENTS_RO (isis
->area_list
, node
, area
))
1606 vty_out (vty
, "Area %s:%s", area
->area_tag
? area
->area_tag
: "null",
1609 if (area
->ip_circuits
> 0 && area
->spftree
[0]
1610 && area
->spftree
[0]->paths
->count
> 0)
1612 vty_out (vty
, "IS-IS paths to level-1 routers that speak IP%s",
1614 isis_print_paths (vty
, area
->spftree
[0]->paths
, isis
->sysid
);
1615 vty_out (vty
, "%s", VTY_NEWLINE
);
1618 if (area
->ipv6_circuits
> 0 && area
->spftree6
[0]
1619 && area
->spftree6
[0]->paths
->count
> 0)
1621 vty_out (vty
, "IS-IS paths to level-1 routers that speak IPv6%s",
1623 isis_print_paths (vty
, area
->spftree6
[0]->paths
, isis
->sysid
);
1624 vty_out (vty
, "%s", VTY_NEWLINE
);
1626 #endif /* HAVE_IPV6 */
1627 vty_out (vty
, "%s", VTY_NEWLINE
);
1633 DEFUN (show_isis_topology_l2
,
1634 show_isis_topology_l2_cmd
,
1635 "show isis topology level-2",
1637 "IS-IS information\n"
1638 "IS-IS paths to Intermediate Systems\n"
1639 "Paths to all level-2 routers in the domain\n")
1641 struct listnode
*node
;
1642 struct isis_area
*area
;
1644 if (!isis
->area_list
|| isis
->area_list
->count
== 0)
1647 for (ALL_LIST_ELEMENTS_RO (isis
->area_list
, node
, area
))
1649 vty_out (vty
, "Area %s:%s", area
->area_tag
? area
->area_tag
: "null",
1652 if (area
->ip_circuits
> 0 && area
->spftree
[1]
1653 && area
->spftree
[1]->paths
->count
> 0)
1655 vty_out (vty
, "IS-IS paths to level-2 routers that speak IP%s",
1657 isis_print_paths (vty
, area
->spftree
[1]->paths
, isis
->sysid
);
1658 vty_out (vty
, "%s", VTY_NEWLINE
);
1661 if (area
->ipv6_circuits
> 0 && area
->spftree6
[1]
1662 && area
->spftree6
[1]->paths
->count
> 0)
1664 vty_out (vty
, "IS-IS paths to level-2 routers that speak IPv6%s",
1666 isis_print_paths (vty
, area
->spftree6
[1]->paths
, isis
->sysid
);
1667 vty_out (vty
, "%s", VTY_NEWLINE
);
1669 #endif /* HAVE_IPV6 */
1670 vty_out (vty
, "%s", VTY_NEWLINE
);
1677 isis_spf_cmds_init ()
1679 install_element (VIEW_NODE
, &show_isis_topology_cmd
);
1680 install_element (VIEW_NODE
, &show_isis_topology_l1_cmd
);
1681 install_element (VIEW_NODE
, &show_isis_topology_l2_cmd
);
1683 install_element (ENABLE_NODE
, &show_isis_topology_cmd
);
1684 install_element (ENABLE_NODE
, &show_isis_topology_l1_cmd
);
1685 install_element (ENABLE_NODE
, &show_isis_topology_l2_cmd
);