2 * Copyright (C) 1999 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with GNU Zebra; see the file COPYING. If not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
21 /* Shortest Path First calculation for OSPFv3 */
29 #include "ospf6_proto.h"
30 #include "ospf6_lsa.h"
31 #include "ospf6_lsdb.h"
32 #include "ospf6_route.h"
33 #include "ospf6_spf.h"
34 #include "ospf6_neighbor.h"
35 #include "ospf6_interface.h"
36 #include "ospf6_area.h"
38 #include "ospf6_bintree.h"
39 #include "ospf6_linklist.h"
41 struct bintree
*_candidate_list
;
42 struct linklist
*nexthop_list
;
44 struct ospf6_spf_candidate_node
47 struct linklist
*list
;
51 ospf6_spf_candidate_node_cmp (void *a
, void *b
)
53 struct ospf6_spf_candidate_node
*ca
= a
;
54 struct ospf6_spf_candidate_node
*cb
= b
;
55 return ca
->cost
- cb
->cost
;
59 ospf6_spf_vertex_cmp (void *a
, void *b
)
65 ospf6_spf_candidate_node_print (int indent_num
, void *node
)
67 struct ospf6_spf_candidate_node
*cn
= node
;
70 snprintf (format
, sizeof (format
), "%%%ds %%d (num: %%d)",
72 zlog_info (format
, " ", cn
->cost
, cn
->list
->count
);
76 ospf6_spf_candidate_init ()
78 _candidate_list
= bintree_create ();
79 _candidate_list
->cmp
= ospf6_spf_candidate_node_cmp
;
83 ospf6_spf_candidate_count ()
86 struct bintree_node node
;
87 struct ospf6_spf_candidate_node
*cnode
;
89 for (bintree_head (_candidate_list
, &node
); ! bintree_end (&node
);
93 count
+= cnode
->list
->count
;
100 ospf6_spf_candidate_print ()
102 zlog_info ("---------------------------");
103 bintree_print (ospf6_spf_candidate_node_print
, _candidate_list
);
104 zlog_info ("---------------------------");
108 ospf6_spf_candidate_enqueue (struct ospf6_vertex
*v
)
110 struct ospf6_spf_candidate_node req
, *node
;
112 memset (&req
, 0, sizeof (req
));
113 req
.cost
= v
->distance
;
114 node
= bintree_lookup (&req
, _candidate_list
);
118 node
= malloc (sizeof (struct ospf6_spf_candidate_node
));
119 node
->cost
= v
->distance
;
120 node
->list
= linklist_create ();
121 node
->list
->cmp
= ospf6_spf_vertex_cmp
;
122 bintree_add (node
, _candidate_list
);
125 linklist_add (v
, node
->list
);
128 if (IS_OSPF6_DUMP_SPF
)
129 ospf6_spf_candidate_print ();
133 struct ospf6_vertex
*
134 ospf6_spf_candidate_dequeue ()
136 struct ospf6_spf_candidate_node
*node
;
137 struct linklist_node lnode
;
138 struct ospf6_vertex
*ret
;
140 node
= bintree_lookup_min (_candidate_list
);
144 linklist_head (node
->list
, &lnode
);
147 linklist_remove (ret
, node
->list
);
148 if (node
->list
->count
== 0)
150 linklist_delete (node
->list
);
151 bintree_remove (node
, _candidate_list
);
155 if (IS_OSPF6_DUMP_SPF
)
156 ospf6_spf_candidate_print ();
163 ospf6_spf_candidate_remove (struct ospf6_vertex
*v
)
165 struct bintree_node node
;
166 struct ospf6_spf_candidate_node
*cnode
= NULL
;
168 for (bintree_head (_candidate_list
, &node
); ! bintree_end (&node
);
169 bintree_next (&node
))
172 if (linklist_lookup (v
, cnode
->list
))
174 linklist_remove (v
, cnode
->list
);
179 if (cnode
->list
->count
== 0)
181 linklist_delete (cnode
->list
);
182 bintree_remove (cnode
, _candidate_list
);
187 #define TIMER_SEC_MICRO 1000000
189 /* timeval calculation */
191 ospf6_timeval_add (const struct timeval
*t1
, const struct timeval
*t2
,
192 struct timeval
*result
)
196 result
->tv_usec
= t1
->tv_usec
+ t2
->tv_usec
;
197 while (result
->tv_usec
> TIMER_SEC_MICRO
)
199 result
->tv_usec
-= TIMER_SEC_MICRO
;
203 result
->tv_sec
= t1
->tv_sec
+ t2
->tv_sec
+ moveup
;
207 ospf6_timeval_add_equal (const struct timeval
*t
, struct timeval
*result
)
210 ospf6_timeval_add (t
, result
, &tmp
);
211 result
->tv_sec
= tmp
.tv_sec
;
212 result
->tv_usec
= tmp
.tv_usec
;
215 /* Compare timeval a and b. It returns an integer less than, equal
216 to, or great than zero if a is found, respectively, to be less
217 than, to match, or be greater than b. */
219 ospf6_timeval_cmp (const struct timeval t1
, const struct timeval t2
)
221 return (t1
.tv_sec
== t2
.tv_sec
222 ? t1
.tv_usec
- t2
.tv_usec
: t1
.tv_sec
- t2
.tv_sec
);
227 ospf6_spf_lsd_num (struct ospf6_vertex
*V
, struct ospf6_area
*o6a
)
230 u_int32_t id
, adv_router
;
231 struct ospf6_lsa
*lsa
;
233 if (V
->vertex_id
.id
.s_addr
)
234 type
= htons (OSPF6_LSA_TYPE_NETWORK
);
236 type
= htons (OSPF6_LSA_TYPE_ROUTER
);
237 id
= V
->vertex_id
.id
.s_addr
;
238 adv_router
= V
->vertex_id
.adv_router
.s_addr
;
240 lsa
= ospf6_lsdb_lookup_lsdb (type
, id
, adv_router
, o6a
->lsdb
);
243 zlog_err ("SPF: Can't find associated LSA for %s", V
->string
);
247 return ospf6_lsa_lsd_num ((struct ospf6_lsa_header
*) lsa
->header
);
250 /* RFC2328 section 16.1.1:
251 Check if there is at least one router in the path
252 from the root to this vertex. */
254 ospf6_spf_is_router_to_root (struct ospf6_vertex
*c
,
255 struct ospf6_spftree
*spf_tree
)
258 struct ospf6_vertex
*p
;
260 if (spf_tree
->root
== c
)
263 for (node
= listhead (c
->parent_list
); node
; nextnode (node
))
265 p
= (struct ospf6_vertex
*) getdata (node
);
267 if (p
== spf_tree
->root
)
270 if (p
->vertex_id
.id
.s_addr
== 0) /* this is router */
272 else if (ospf6_spf_is_router_to_root (p
, spf_tree
))
281 static struct in6_addr
*
282 ospf6_spf_get_ipaddr (u_int32_t id
, u_int32_t adv_router
, u_int32_t ifindex
)
284 char buf
[64], nhbuf
[64];
285 struct ospf6_interface
*o6i
;
286 struct ospf6_neighbor
*o6n
;
287 struct ospf6_lsa
*lsa
;
288 struct ospf6_lsdb_node node
;
290 o6i
= ospf6_interface_lookup_by_index (ifindex
);
293 zlog_err ("SPF: Can't find interface: index %d", ifindex
);
294 return (struct in6_addr
*) NULL
;
297 /* Find Link-LSA of the vertex in question */
299 for (ospf6_lsdb_type_router (&node
, htons (OSPF6_LSA_TYPE_LINK
),
300 adv_router
, o6i
->lsdb
);
301 ! ospf6_lsdb_is_end (&node
);
302 ospf6_lsdb_next (&node
))
305 /* return Linklocal Address field if the Link-LSA exists */
306 if (lsa
&& lsa
->header
->adv_router
== adv_router
)
308 struct ospf6_link_lsa
*link_lsa
;
309 link_lsa
= (struct ospf6_link_lsa
*) (lsa
->header
+ 1);
310 return &link_lsa
->llsa_linklocal
;
313 zlog_warn ("SPF: Can't find Link-LSA for %s",
314 inet_ntop (AF_INET
, &adv_router
, buf
, sizeof (buf
)));
316 o6n
= ospf6_neighbor_lookup (adv_router
, o6i
);
319 inet_ntop (AF_INET
, &adv_router
, buf
, sizeof (buf
));
320 zlog_err ("SPF: Can't find neighbor %s in %s, "
321 "unable to find his linklocal address",
322 buf
, o6i
->interface
->name
);
323 return (struct in6_addr
*) NULL
;
326 zlog_warn ("SPF: use packet's source address for %s's nexthop: %s",
327 inet_ntop (AF_INET
, &adv_router
, buf
, sizeof (buf
)),
328 inet_ntop (AF_INET6
, &o6n
->hisaddr
, nhbuf
, sizeof (nhbuf
)));
330 return &o6n
->hisaddr
;
334 ospf6_spf_nexthop_calculation (struct ospf6_vertex
*W
,
336 struct ospf6_vertex
*V
,
337 struct ospf6_spftree
*spf_tree
)
339 struct ospf6_nexthop
*nexthop
, *n
;
340 u_int32_t adv_router
, id
;
341 struct in6_addr nexthop_ipaddr
, *ipaddr
;
342 unsigned int nexthop_ifindex
;
343 struct linklist_node node
;
345 /* until this, nexthop_list should be untouched */
346 assert (list_isempty (W
->nexthop_list
));
348 /* If ther is at least one intervening router from root to W */
349 if (ospf6_spf_is_router_to_root (W
, spf_tree
))
351 /* Create no new nexthop, Inherit from the intervening router */
352 for (linklist_head (V
->nexthop_list
, &node
); ! linklist_end (&node
);
353 linklist_next (&node
))
354 linklist_add (node
.data
, W
->nexthop_list
);
358 /* Create new nexthop */
360 adv_router
= W
->vertex_id
.adv_router
.s_addr
;
361 id
= W
->vertex_id
.id
.s_addr
;
364 memset (&nexthop_ipaddr
, 0, sizeof (struct in6_addr
));
365 if (spf_tree
->root
&& V
== spf_tree
->root
)
367 nexthop_ifindex
= ifindex
;
368 if (! id
) /* xxx, if V is router */
370 ipaddr
= ospf6_spf_get_ipaddr (id
, adv_router
, ifindex
);
373 /* xxx, should trigger error and quit SPF calculation... */
374 memset (&nexthop_ipaddr
, 0xff, sizeof (struct in6_addr
));
378 memcpy (&nexthop_ipaddr
, ipaddr
, sizeof (struct in6_addr
));
383 /* V is broadcast network, W is router */
384 assert (V
->vertex_id
.id
.s_addr
!= 0);
385 assert (W
->vertex_id
.id
.s_addr
== 0);
387 linklist_head (V
->nexthop_list
, &node
);
388 n
= (struct ospf6_nexthop
*) node
.data
;
389 nexthop_ifindex
= n
->ifindex
;
390 ipaddr
= ospf6_spf_get_ipaddr (id
, adv_router
, n
->ifindex
);
393 /* xxx, should trigger error and quit SPF calculation... */
394 memset (&nexthop_ipaddr
, 0xff, sizeof (struct in6_addr
));
398 memcpy (&nexthop_ipaddr
, ipaddr
, sizeof (struct in6_addr
));
401 nexthop
= XCALLOC (MTYPE_OSPF6_VERTEX
, sizeof (struct ospf6_nexthop
));
402 nexthop
->ifindex
= nexthop_ifindex
;
403 memcpy (&nexthop
->address
, &nexthop_ipaddr
, sizeof (nexthop
->address
));
405 linklist_add (nexthop
, W
->nexthop_list
);
407 /* to hold malloced memory */
408 linklist_add (nexthop
, nexthop_list
);
413 static struct ospf6_vertex
*
414 ospf6_spf_vertex_create (int index
, struct ospf6_vertex
*V
,
415 struct ospf6_area
*o6a
)
417 struct ospf6_lsa
*lsa
;
418 struct ospf6_router_lsa
*router_lsa
;
419 struct ospf6_router_lsd
*router_lsd
;
420 struct ospf6_network_lsa
*network_lsa
;
421 struct ospf6_network_lsd
*network_lsd
;
422 u_int32_t id
, adv_router
;
425 struct ospf6_vertex
*W
;
428 int backreference
, lsdnum
, i
;
429 char buf_router
[16], buf_id
[16];
431 type
= id
= adv_router
= 0;
433 /* Get Linkstate description */
434 lsd
= ospf6_lsa_lsd_get (index
, (struct ospf6_lsa_header
*) V
->lsa
->header
);
437 zlog_err ("SPF: Can't find %dth Link description from %s",
439 return (struct ospf6_vertex
*) NULL
;
442 /* Check Link state description */
445 if (V
->lsa
->header
->type
== htons (OSPF6_LSA_TYPE_ROUTER
))
448 if (router_lsd
->type
== OSPF6_ROUTER_LSD_TYPE_POINTTOPOINT
)
450 type
= htons (OSPF6_LSA_TYPE_ROUTER
);
453 else if (router_lsd
->type
== OSPF6_ROUTER_LSD_TYPE_TRANSIT_NETWORK
)
455 type
= htons (OSPF6_LSA_TYPE_NETWORK
);
456 id
= router_lsd
->neighbor_interface_id
;
458 adv_router
= router_lsd
->neighbor_router_id
;
459 distance
= ntohs (router_lsd
->metric
);
460 ifindex
= ntohl (router_lsd
->interface_id
);
462 else if (V
->lsa
->header
->type
== htons (OSPF6_LSA_TYPE_NETWORK
))
465 type
= htons (OSPF6_LSA_TYPE_ROUTER
);
467 adv_router
= network_lsd
->adv_router
;
470 /* Avoid creating candidate of myself */
471 if (adv_router
== o6a
->ospf6
->router_id
&&
472 type
== htons (OSPF6_LSA_TYPE_ROUTER
))
474 return (struct ospf6_vertex
*) NULL
;
477 /* Find Associated LSA for W */
478 lsa
= ospf6_lsdb_lookup_lsdb (type
, id
, adv_router
, o6a
->lsdb
);
482 inet_ntop (AF_INET
, &adv_router
, buf_router
, sizeof (buf_router
));
483 inet_ntop (AF_INET
, &id
, buf_id
, sizeof (buf_id
));
485 if (IS_OSPF6_DUMP_SPF
)
487 if (type
== htons (OSPF6_LSA_TYPE_ROUTER
))
488 zlog_info ("SPF: Can't find LSA for W (%s *): not found",
491 zlog_info ("SPF: Can't find LSA for W (%s %s): not found",
494 return (struct ospf6_vertex
*) NULL
;
497 if (IS_LSA_MAXAGE (lsa
))
499 if (IS_OSPF6_DUMP_SPF
)
500 zlog_info ("SPF: Associated LSA for W is MaxAge: %s", lsa
->str
);
501 return (struct ospf6_vertex
*) NULL
;
504 /* Check back reference from W's lsa to V's lsa */
506 lsdnum
= ospf6_lsa_lsd_num ((struct ospf6_lsa_header
*) lsa
->header
);
507 for (i
= 0; i
< lsdnum
; i
++)
509 if (ospf6_lsa_lsd_is_refer_ok (i
, (struct ospf6_lsa_header
*) lsa
->header
,
510 index
, (struct ospf6_lsa_header
*) V
->lsa
->header
))
515 if (IS_OSPF6_DUMP_SPF
)
516 zlog_info ("SPF: Back reference failed: V: %s, W: %s",
517 V
->lsa
->str
, lsa
->str
);
518 return (struct ospf6_vertex
*) NULL
;
521 /* Allocate new ospf6_vertex for W */
522 W
= (struct ospf6_vertex
*) XMALLOC (MTYPE_OSPF6_VERTEX
,
523 sizeof (struct ospf6_vertex
));
526 zlog_err ("SPF: Can't allocate memory for Vertex");
527 return (struct ospf6_vertex
*) NULL
;
529 memset (W
, 0, sizeof (struct ospf6_vertex
));
532 W
->vertex_id
.family
= AF_UNSPEC
;
533 W
->vertex_id
.prefixlen
= 64; /* xxx */
535 if (type
== htons (OSPF6_LSA_TYPE_ROUTER
))
536 W
->vertex_id
.id
.s_addr
= htonl (0); /* XXX */
538 W
->vertex_id
.id
.s_addr
= W
->lsa
->header
->id
;
539 W
->vertex_id
.adv_router
.s_addr
= W
->lsa
->header
->adv_router
;
540 W
->nexthop_list
= linklist_create ();
541 W
->path_list
= list_new ();
542 W
->parent_list
= list_new ();
543 W
->distance
= V
->distance
+ distance
;
544 W
->depth
= V
->depth
+ 1;
546 inet_ntop (AF_INET
, &W
->vertex_id
.adv_router
.s_addr
,
547 buf_router
, sizeof (buf_router
));
548 inet_ntop (AF_INET
, &W
->vertex_id
.id
.s_addr
, buf_id
, sizeof (buf_id
));
549 snprintf (W
->string
, sizeof (W
->string
), "[%s-%s (%d)]",
550 buf_router
, buf_id
, W
->distance
);
552 /* capability bits and optional capabilities */
553 if (W
->vertex_id
.id
.s_addr
== 0)
555 router_lsa
= (struct ospf6_router_lsa
*) (W
->lsa
->header
+ 1);
556 W
->capability_bits
= router_lsa
->bits
;
557 memcpy (W
->opt_capability
, router_lsa
->options
,
558 sizeof (W
->opt_capability
));
562 network_lsa
= (struct ospf6_network_lsa
*) (W
->lsa
->header
+ 1);
563 W
->capability_bits
= network_lsa
->reserved
;
564 memcpy (W
->opt_capability
, network_lsa
->options
,
565 sizeof (W
->opt_capability
));
568 /* Link to Parent node */
569 listnode_add (W
->parent_list
, V
);
571 /* Nexthop Calculation */
572 if (ospf6_spf_nexthop_calculation (W
, ifindex
, V
, o6a
->spf_tree
) < 0)
579 ospf6_spf_vertex_delete (struct ospf6_vertex
*v
)
581 linklist_delete (v
->nexthop_list
);
582 list_delete (v
->path_list
);
583 list_delete (v
->parent_list
);
584 XFREE (MTYPE_OSPF6_VERTEX
, v
);
588 ospf6_spf_vertex_merge (struct ospf6_vertex
*w
, struct ospf6_vertex
*x
)
591 struct linklist_node lnode
;
593 /* merge should be done on two nodes which are
596 /* these w and x should be both candidate.
597 candidate should not have any children */
598 assert (list_isempty (w
->path_list
));
599 assert (list_isempty (x
->path_list
));
601 /* merge parent list */
602 for (node
= listhead (w
->parent_list
); node
; nextnode (node
))
604 if (listnode_lookup (x
->parent_list
, getdata (node
)))
606 listnode_add (x
->parent_list
, getdata (node
));
609 /* merge nexthop list */
610 for (linklist_head (w
->nexthop_list
, &lnode
); ! linklist_end (&lnode
);
611 linklist_next (&lnode
))
612 linklist_add (lnode
.data
, x
->nexthop_list
);
616 ospf6_spf_initialize (list candidate_list
, struct ospf6_area
*o6a
)
619 struct ospf6_vertex
*v
;
620 struct ospf6_lsa
*lsa
;
622 u_int32_t id
, adv_router
;
623 struct linklist_node lnode
;
625 struct ospf6_nexthop
*nexthop
;
626 struct interface
*ifp
;
627 char buf_router
[64], buf_id
[64];
629 /* delete topology routing table for this area */
630 ospf6_route_remove_all (o6a
->table_topology
);
632 /* Delete previous spf tree */
633 for (node
= listhead (o6a
->spf_tree
->list
); node
; nextnode (node
))
635 v
= (struct ospf6_vertex
*) getdata (node
);
636 ospf6_spf_vertex_delete (v
);
638 list_delete_all_node (o6a
->spf_tree
->list
);
640 for (linklist_head (nexthop_list
, &lnode
); ! linklist_end (&lnode
);
641 linklist_next (&lnode
))
642 XFREE (MTYPE_OSPF6_VERTEX
, lnode
.data
);
643 linklist_remove_all (nexthop_list
);
645 /* Find self originated Router-LSA */
646 type
= htons (OSPF6_LSA_TYPE_ROUTER
);
648 adv_router
= ospf6
->router_id
;
650 lsa
= ospf6_lsdb_lookup_lsdb (type
, id
, adv_router
, o6a
->lsdb
);
654 if (IS_OSPF6_DUMP_SPF
)
655 zlog_info ("SPF: Can't find self originated Router-LSA");
658 if (IS_LSA_MAXAGE (lsa
))
660 zlog_err ("SPF: MaxAge self originated Router-LSA");
664 /* Create root vertex */
665 v
= (struct ospf6_vertex
*) XMALLOC (MTYPE_OSPF6_VERTEX
,
666 sizeof (struct ospf6_vertex
));
669 zlog_err ("SPF: Can't allocate memory for root vertex");
672 memset (v
, 0, sizeof (struct ospf6_vertex
));
674 v
->vertex_id
.family
= AF_UNSPEC
; /* XXX */
675 v
->vertex_id
.prefixlen
= 64; /* XXX */
676 v
->vertex_id
.id
.s_addr
= htonl (0);
677 v
->vertex_id
.adv_router
.s_addr
= ospf6
->router_id
;
678 if (ospf6_is_asbr (ospf6
))
679 OSPF6_OPT_SET (v
->opt_capability
, OSPF6_OPT_E
);
680 OSPF6_OPT_SET (v
->opt_capability
, OSPF6_OPT_V6
);
681 OSPF6_OPT_SET (v
->opt_capability
, OSPF6_OPT_R
);
682 v
->nexthop_list
= linklist_create ();
683 v
->path_list
= list_new ();
684 v
->parent_list
= list_new ();
689 inet_ntop (AF_INET
, &v
->vertex_id
.adv_router
.s_addr
,
690 buf_router
, sizeof (buf_router
));
691 inet_ntop (AF_INET
, &v
->vertex_id
.id
.s_addr
, buf_id
, sizeof (buf_id
));
692 snprintf (v
->string
, sizeof (v
->string
), "[%s-%s (%d)]",
693 buf_router
, buf_id
, v
->distance
);
695 nexthop
= XCALLOC (MTYPE_OSPF6_VERTEX
, sizeof (struct ospf6_nexthop
));
696 ifp
= if_lookup_by_name ("lo0");
698 nexthop
->ifindex
= ifp
->ifindex
;
699 inet_pton (AF_INET6
, "::1", &nexthop
->address
);
700 linklist_add (nexthop
, v
->nexthop_list
);
701 linklist_add (nexthop
, nexthop_list
);
703 o6a
->spf_tree
->root
= v
;
704 listnode_add (candidate_list
, v
);
706 ospf6_spf_candidate_enqueue (v
);
709 static struct ospf6_vertex
*
710 ospf6_spf_get_closest_candidate (list candidate_list
)
713 struct ospf6_vertex
*candidate
, *closest
;
715 closest
= (struct ospf6_vertex
*) NULL
;
716 for (node
= listhead (candidate_list
); node
; nextnode (node
))
718 candidate
= (struct ospf6_vertex
*) getdata (node
);
720 if (closest
&& candidate
->distance
> closest
->distance
)
723 /* always choose network vertices if those're the same cost */
724 if (closest
&& candidate
->distance
== closest
->distance
725 && closest
->vertex_id
.id
.s_addr
!= 0)
734 static struct ospf6_vertex
*
735 ospf6_spf_get_same_candidate (struct ospf6_vertex
*w
, list candidate_list
)
738 struct ospf6_vertex
*c
, *same
;
740 same
= (struct ospf6_vertex
*) NULL
;
741 for (node
= listhead (candidate_list
); node
; nextnode (node
))
743 c
= (struct ospf6_vertex
*) getdata (node
);
744 if (w
->vertex_id
.adv_router
.s_addr
!= c
->vertex_id
.adv_router
.s_addr
)
746 if (w
->vertex_id
.id
.s_addr
!= c
->vertex_id
.id
.s_addr
)
750 zlog_warn ("SPF: duplicate candidates in candidate_list");
759 ospf6_spf_install (struct ospf6_vertex
*vertex
, struct ospf6_area
*o6a
)
762 struct ospf6_vertex
*parent
;
763 struct ospf6_nexthop
*nexthop
;
764 struct ospf6_route_req request
;
765 struct linklist_node lnode
;
767 struct ospf6_router_lsa
*router_lsa
;
768 struct ospf6_network_lsa
*network_lsa
;
770 router_lsa
= OSPF6_LSA_HEADER_END (vertex
->lsa
->header
);
771 network_lsa
= OSPF6_LSA_HEADER_END (vertex
->lsa
->header
);
773 if (IS_OSPF6_DUMP_SPF
)
775 zlog_info ("SPF: Install: %s", vertex
->string
);
778 listnode_add (o6a
->spf_tree
->list
, vertex
);
780 for (node
= listhead (vertex
->parent_list
); node
; nextnode (node
))
782 parent
= (struct ospf6_vertex
*) getdata (node
);
783 listnode_add (parent
->path_list
, vertex
);
784 vertex
->depth
= parent
->depth
+ 1;
788 if (vertex
== o6a
->spf_tree
->root
)
792 /* install route to topology table */
793 memset (&request
, 0, sizeof (request
));
794 if (vertex
->vertex_id
.id
.s_addr
) /* xxx */
795 request
.route
.type
= OSPF6_DEST_TYPE_NETWORK
;
797 request
.route
.type
= OSPF6_DEST_TYPE_ROUTER
;
798 memcpy (&request
.route
.prefix
, &vertex
->vertex_id
,
799 sizeof (struct prefix
));
801 request
.path
.area_id
= o6a
->area_id
;
802 request
.path
.type
= OSPF6_PATH_TYPE_INTRA
;
803 request
.path
.cost
= vertex
->distance
;
804 request
.path
.cost_e2
= 0;
805 request
.path
.origin
.type
= vertex
->lsa
->header
->type
;
806 request
.path
.origin
.id
= vertex
->lsa
->header
->id
;
807 request
.path
.origin
.adv_router
= vertex
->lsa
->header
->adv_router
;
808 if (vertex
->lsa
->header
->type
== htons (OSPF6_LSA_TYPE_ROUTER
))
809 request
.path
.router_bits
= router_lsa
->bits
;
810 memcpy (&request
.path
.capability
, vertex
->opt_capability
,
811 sizeof (request
.path
.capability
));
814 if (IS_OSPF6_DUMP_SPF
)
815 zlog_info ("SPF: install %d nexthops for %s",
816 listcount (vertex
->nexthop_list
), vertex
->string
);
819 for (linklist_head (vertex
->nexthop_list
, &lnode
); ! linklist_end (&lnode
);
820 linklist_next (&lnode
))
822 nexthop
= lnode
.data
;
824 request
.nexthop
.ifindex
= nexthop
->ifindex
;
825 memcpy (&request
.nexthop
.address
, &nexthop
->address
,
826 sizeof (request
.nexthop
.address
));
828 ospf6_route_add (&request
, o6a
->table_topology
);
832 struct ospf6_vertex
*
833 ospf6_spf_lookup (struct ospf6_vertex
*w
, struct ospf6_area
*o6a
)
836 struct ospf6_vertex
*v
;
838 for (node
= listhead (o6a
->spf_tree
->list
); node
; nextnode (node
))
840 v
= (struct ospf6_vertex
*) getdata (node
);
842 if (w
->vertex_id
.adv_router
.s_addr
!= v
->vertex_id
.adv_router
.s_addr
)
844 if (w
->vertex_id
.id
.s_addr
!= v
->vertex_id
.id
.s_addr
)
850 return (struct ospf6_vertex
*) NULL
;
853 u_int32_t stat_node
= 0;
854 u_int32_t stat_candidate
= 0;
855 u_int32_t stat_candidate_max
= 0;
856 u_int32_t stat_spf
= 0;
859 /* RFC2328 section 16.1 , RFC2740 section 3.8.1 */
861 ospf6_spf_calculation (struct ospf6_area
*o6a
)
864 struct ospf6_vertex
*V
, *W
, *X
;
867 if (! o6a
|| ! o6a
->spf_tree
)
869 zlog_err ("SPF: Can't calculate SPF tree: malformed area");
876 stat_candidate_max
= 0;
878 if (IS_OSPF6_DUMP_SPF
)
879 zlog_info ("SPF: Calculation for area %s", o6a
->str
);
881 ospf6_route_table_freeze (o6a
->table_topology
);
882 ospf6_route_remove_all (o6a
->table_topology
);
884 /* (1): Initialize the algorithm's data structures */
885 candidate_list
= list_new ();
886 ospf6_spf_initialize (candidate_list
, o6a
);
889 /* (3): Install closest from candidate list; if empty, break */
890 while (listcount (candidate_list
))
892 V
= ospf6_spf_get_closest_candidate (candidate_list
);
893 listnode_delete (candidate_list
, V
);
896 struct ospf6_vertex
*V_
;
898 if (stat_candidate_max
< ospf6_spf_candidate_count ())
899 stat_candidate_max
= ospf6_spf_candidate_count ();
901 V_
= ospf6_spf_candidate_dequeue ();
904 if (IS_OSPF6_DUMP_SPF
)
906 zlog_info ("Candidate list count: %lu",
907 (u_long
)ospf6_spf_candidate_count ());
908 zlog_info ("*** Candidate %s: %p <-> %p",
909 (V
== V_
? "same" : "*** differ ***"), V
, V_
);
910 zlog_info (" %p: %s", V
, V
->string
);
911 zlog_info (" %p: %s", V_
, V_
->string
);
918 ospf6_spf_install (V
, o6a
);
920 /* (2): Examin LSA of just added vertex */
921 ldnum
= ospf6_spf_lsd_num (V
, o6a
);
922 for (i
= 0; i
< ldnum
; i
++)
924 /* (b): If no LSA, or MaxAge, or LinkBack fail, examin next */
925 W
= ospf6_spf_vertex_create (i
, V
, o6a
);
932 if (ospf6_spf_lookup (W
, o6a
))
934 if (IS_OSPF6_DUMP_SPF
)
935 zlog_info ("SPF: %s: Already in SPF tree", W
->string
);
936 ospf6_spf_vertex_delete (W
);
941 X
= ospf6_spf_get_same_candidate (W
, candidate_list
);
942 if (X
&& X
->distance
< W
->distance
)
944 if (IS_OSPF6_DUMP_SPF
)
945 zlog_info ("SPF: %s: More closer found", W
->string
);
946 ospf6_spf_vertex_delete (W
);
949 if (X
&& X
->distance
== W
->distance
)
951 if (IS_OSPF6_DUMP_SPF
)
952 zlog_info ("SPF: %s: new ECMP candidate", W
->string
);
953 ospf6_spf_vertex_merge (W
, X
);
954 ospf6_spf_vertex_delete (W
);
960 if (IS_OSPF6_DUMP_SPF
)
961 zlog_info ("SPF: %s: Swap with old candidate", W
->string
);
962 listnode_delete (candidate_list
, X
);
963 ospf6_spf_candidate_remove (X
);
964 ospf6_spf_vertex_delete (X
);
968 if (IS_OSPF6_DUMP_SPF
)
969 zlog_info ("SPF: %s: New Candidate", W
->string
);
972 if (stat_candidate_max
< ospf6_spf_candidate_count ())
973 stat_candidate_max
= ospf6_spf_candidate_count ();
975 listnode_add (candidate_list
, W
);
976 ospf6_spf_candidate_enqueue (W
);
980 assert (listcount (candidate_list
) == 0);
981 list_free (candidate_list
);
982 assert (ospf6_spf_candidate_count () == 0);
984 /* Clear thread timer */
985 o6a
->spf_tree
->t_spf_calculation
= (struct thread
*) NULL
;
987 if (IS_OSPF6_DUMP_SPF
)
989 zlog_info ("SPF: Calculation for area %s done", o6a
->str
);
990 zlog_info ("SPF: Statistics: %luth", (u_long
)stat_spf
);
991 zlog_info ("SPF: Node Number: %lu", (u_long
)stat_node
);
992 zlog_info ("SPF: Candidate Number: %lu Max: %lu",
993 (u_long
) stat_candidate
, (u_long
) stat_candidate_max
);
996 ospf6_route_table_thaw (o6a
->table_topology
);
1001 ospf6_spf_calculation_thread (struct thread
*t
)
1003 struct ospf6_area
*o6a
;
1004 struct timeval start
, end
, runtime
, interval
;
1006 o6a
= (struct ospf6_area
*) THREAD_ARG (t
);
1009 zlog_err ("SPF: Thread error");
1013 if (! o6a
->spf_tree
)
1015 zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a
->str
);
1019 /* execute SPF calculation */
1020 gettimeofday (&start
, (struct timezone
*) NULL
);
1021 ospf6_spf_calculation (o6a
);
1022 gettimeofday (&end
, (struct timezone
*) NULL
);
1024 /* update statistics */
1025 o6a
->spf_tree
->timerun
++;
1026 ospf6_timeval_sub (&end
, &start
, &runtime
);
1027 ospf6_timeval_add_equal (&runtime
, &o6a
->spf_tree
->runtime_total
);
1029 if (o6a
->spf_tree
->timerun
== 1)
1031 o6a
->spf_tree
->runtime_min
.tv_sec
= runtime
.tv_sec
;
1032 o6a
->spf_tree
->runtime_min
.tv_usec
= runtime
.tv_usec
;
1033 o6a
->spf_tree
->runtime_max
.tv_sec
= runtime
.tv_sec
;
1034 o6a
->spf_tree
->runtime_max
.tv_usec
= runtime
.tv_usec
;
1036 if (ospf6_timeval_cmp (o6a
->spf_tree
->runtime_min
, runtime
) > 0)
1038 o6a
->spf_tree
->runtime_min
.tv_sec
= runtime
.tv_sec
;
1039 o6a
->spf_tree
->runtime_min
.tv_usec
= runtime
.tv_usec
;
1041 if (ospf6_timeval_cmp (runtime
, o6a
->spf_tree
->runtime_max
) > 0)
1043 o6a
->spf_tree
->runtime_max
.tv_sec
= runtime
.tv_sec
;
1044 o6a
->spf_tree
->runtime_max
.tv_usec
= runtime
.tv_usec
;
1047 if (o6a
->spf_tree
->timerun
== 1)
1049 ospf6_timeval_sub (&start
, &ospf6
->starttime
, &interval
);
1050 ospf6_timeval_add_equal (&interval
, &o6a
->spf_tree
->interval_total
);
1051 o6a
->spf_tree
->interval_min
.tv_sec
= interval
.tv_sec
;
1052 o6a
->spf_tree
->interval_min
.tv_usec
= interval
.tv_usec
;
1053 o6a
->spf_tree
->interval_max
.tv_sec
= interval
.tv_sec
;
1054 o6a
->spf_tree
->interval_max
.tv_usec
= interval
.tv_usec
;
1058 ospf6_timeval_sub (&start
, &o6a
->spf_tree
->updated_time
, &interval
);
1059 ospf6_timeval_add_equal (&interval
, &o6a
->spf_tree
->interval_total
);
1060 if (ospf6_timeval_cmp (o6a
->spf_tree
->interval_min
, interval
) > 0)
1062 o6a
->spf_tree
->interval_min
.tv_sec
= interval
.tv_sec
;
1063 o6a
->spf_tree
->interval_min
.tv_usec
= interval
.tv_usec
;
1065 if (ospf6_timeval_cmp (interval
, o6a
->spf_tree
->interval_max
) > 0)
1067 o6a
->spf_tree
->interval_max
.tv_sec
= interval
.tv_sec
;
1068 o6a
->spf_tree
->interval_max
.tv_usec
= interval
.tv_usec
;
1071 o6a
->spf_tree
->updated_time
.tv_sec
= end
.tv_sec
;
1072 o6a
->spf_tree
->updated_time
.tv_usec
= end
.tv_usec
;
1075 o6a
->spf_tree
->t_spf_calculation
= (struct thread
*) NULL
;
1081 ospf6_spf_database_hook (struct ospf6_lsa
*old
, struct ospf6_lsa
*new)
1083 struct ospf6_area
*o6a
= NULL
;
1084 struct ospf6_interface
*o6i
= NULL
;
1086 if (new->header
->type
== htons (OSPF6_LSA_TYPE_ROUTER
) ||
1087 new->header
->type
== htons (OSPF6_LSA_TYPE_NETWORK
))
1089 else if (new->header
->type
== htons (OSPF6_LSA_TYPE_LINK
))
1096 ospf6_spf_calculation_schedule (o6a
->area_id
);
1100 ospf6_spf_calculation_schedule (u_int32_t area_id
)
1102 struct ospf6_area
*o6a
;
1105 o6a
= ospf6_area_lookup (area_id
, ospf6
);
1108 inet_ntop (AF_INET
, &area_id
, buf
, sizeof (buf
));
1109 zlog_err ("SPF: Can't find area: %s", buf
);
1113 if (! o6a
->spf_tree
)
1115 zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a
->str
);
1119 if (o6a
->spf_tree
->t_spf_calculation
)
1122 o6a
->spf_tree
->t_spf_calculation
=
1123 thread_add_event (master
, ospf6_spf_calculation_thread
, o6a
, 0);
1126 struct ospf6_spftree
*
1127 ospf6_spftree_create ()
1129 struct ospf6_spftree
*spf_tree
;
1130 spf_tree
= (struct ospf6_spftree
*) XMALLOC (MTYPE_OSPF6_SPFTREE
,
1131 sizeof (struct ospf6_spftree
));
1134 zlog_err ("SPF: Can't allocate memory for SPF tree");
1135 return (struct ospf6_spftree
*) NULL
;
1137 memset (spf_tree
, 0, sizeof (spf_tree
));
1139 spf_tree
->list
= list_new ();
1145 ospf6_spftree_delete (struct ospf6_spftree
*spf_tree
)
1148 struct ospf6_vertex
*v
;
1150 /* Delete spf tree */
1151 for (node
= listhead (spf_tree
->list
); node
; nextnode (node
))
1153 v
= (struct ospf6_vertex
*) getdata (node
);
1154 ospf6_spf_vertex_delete (v
);
1156 list_delete_all_node (spf_tree
->list
);
1158 XFREE (MTYPE_OSPF6_SPFTREE
, spf_tree
);
1162 ospf6_nexthop_show (struct vty
*vty
, struct ospf6_nexthop
*nexthop
)
1164 char buf
[128], *ifname
;
1165 struct ospf6_interface
*o6i
;
1169 o6i
= ospf6_interface_lookup_by_index (nexthop
->ifindex
);
1172 zlog_err ("Spf: invalid ifindex %d in nexthop", nexthop
->ifindex
);
1175 ifname
= o6i
->interface
->name
;
1177 inet_ntop (AF_INET6
, &nexthop
->address
, buf
, sizeof (buf
));
1178 vty_out (vty
, " %s%%%s(%d)%s", buf
, ifname
,
1179 nexthop
->ifindex
, VTY_NEWLINE
);
1183 ospf6_vertex_show (struct vty
*vty
, struct ospf6_vertex
*vertex
)
1186 struct ospf6_vertex
*v
;
1187 struct linklist_node lnode
;
1189 vty_out (vty
, "SPF node %s%s", vertex
->string
, VTY_NEWLINE
);
1190 vty_out (vty
, " cost to this node: %d%s", vertex
->distance
, VTY_NEWLINE
);
1191 vty_out (vty
, " hops to this node: %d%s", vertex
->depth
, VTY_NEWLINE
);
1193 vty_out (vty
, " nexthops reachable to this node:%s", VTY_NEWLINE
);
1194 for (linklist_head (vertex
->nexthop_list
, &lnode
);
1195 ! linklist_end (&lnode
);
1196 linklist_next (&lnode
))
1197 ospf6_nexthop_show (vty
, (struct ospf6_nexthop
*) lnode
.data
);
1199 vty_out (vty
, " parent nodes to this node:%s", VTY_NEWLINE
);
1200 if (! list_isempty (vertex
->parent_list
))
1202 for (node
= listhead (vertex
->parent_list
); node
; nextnode (node
))
1204 v
= (struct ospf6_vertex
*) getdata (node
);
1205 vty_out (vty
, "%s ", v
->string
);
1207 if (! list_isempty (vertex
->parent_list
))
1208 vty_out (vty
, "%s", VTY_NEWLINE
);
1210 vty_out (vty
, " child nodes to this node:%s", VTY_NEWLINE
);
1211 if (! list_isempty (vertex
->path_list
))
1213 for (node
= listhead (vertex
->path_list
); node
; nextnode (node
))
1215 v
= (struct ospf6_vertex
*) getdata (node
);
1216 vty_out (vty
, "%s ", v
->string
);
1218 if (! list_isempty (vertex
->path_list
))
1219 vty_out (vty
, "%s", VTY_NEWLINE
);
1221 vty_out (vty
, "%s", VTY_NEWLINE
);
1225 ospf6_spf_statistics_show (struct vty
*vty
, struct ospf6_spftree
*spf_tree
)
1228 struct ospf6_vertex
*vertex
;
1229 u_int router_count
, network_count
, maxdepth
;
1230 struct timeval runtime_avg
, interval_avg
, last_updated
, now
;
1231 char rmin
[64], rmax
[64], ravg
[64];
1232 char imin
[64], imax
[64], iavg
[64];
1233 char last_updated_string
[64];
1235 maxdepth
= router_count
= network_count
= 0;
1236 for (node
= listhead (spf_tree
->list
); node
; nextnode (node
))
1238 vertex
= (struct ospf6_vertex
*) getdata (node
);
1239 if (vertex
->vertex_id
.id
.s_addr
)
1243 if (maxdepth
< vertex
->depth
)
1244 maxdepth
= vertex
->depth
;
1247 ospf6_timeval_div (&spf_tree
->runtime_total
, spf_tree
->timerun
,
1249 ospf6_timeval_string (&spf_tree
->runtime_min
, rmin
, sizeof (rmin
));
1250 ospf6_timeval_string (&spf_tree
->runtime_max
, rmax
, sizeof (rmax
));
1251 ospf6_timeval_string (&runtime_avg
, ravg
, sizeof (ravg
));
1253 ospf6_timeval_div (&spf_tree
->interval_total
, spf_tree
->timerun
,
1255 ospf6_timeval_string (&spf_tree
->interval_min
, imin
, sizeof (imin
));
1256 ospf6_timeval_string (&spf_tree
->interval_max
, imax
, sizeof (imax
));
1257 ospf6_timeval_string (&interval_avg
, iavg
, sizeof (iavg
));
1259 gettimeofday (&now
, (struct timezone
*) NULL
);
1260 ospf6_timeval_sub (&now
, &spf_tree
->updated_time
, &last_updated
);
1261 ospf6_timeval_string (&last_updated
, last_updated_string
,
1262 sizeof (last_updated_string
));
1264 vty_out (vty
, " SPF algorithm executed %d times%s",
1265 spf_tree
->timerun
, VTY_NEWLINE
);
1266 vty_out (vty
, " Average time to run SPF: %s%s",
1268 vty_out (vty
, " Maximum time to run SPF: %s%s",
1270 vty_out (vty
, " Average interval of SPF: %s%s",
1272 vty_out (vty
, " SPF last updated: %s ago%s",
1273 last_updated_string
, VTY_NEWLINE
);
1274 vty_out (vty
, " Current SPF node count: %d%s",
1275 listcount (spf_tree
->list
), VTY_NEWLINE
);
1276 vty_out (vty
, " Router: %d Network: %d%s",
1277 router_count
, network_count
, VTY_NEWLINE
);
1278 vty_out (vty
, " Maximum of Hop count to nodes: %d%s",
1279 maxdepth
, VTY_NEWLINE
);
1282 DEFUN (show_ipv6_ospf6_area_spf_node
,
1283 show_ipv6_ospf6_area_spf_node_cmd
,
1284 "show ipv6 ospf6 area A.B.C.D spf node",
1290 "Shortest Path First caculation\n"
1291 "vertex infomation\n"
1296 struct ospf6_area
*o6a
;
1297 struct ospf6_vertex
*vertex
;
1299 OSPF6_CMD_CHECK_RUNNING ();
1301 inet_pton (AF_INET
, argv
[0], &area_id
);
1302 o6a
= ospf6_area_lookup (area_id
, ospf6
);
1306 for (i
= listhead (o6a
->spf_tree
->list
); i
; nextnode (i
))
1308 vertex
= (struct ospf6_vertex
*) getdata (i
);
1309 ospf6_vertex_show (vty
, vertex
);
1316 ospf6_spftree_show (struct vty
*vty
, char *prefix
, int current_rest
,
1317 struct ospf6_vertex
*v
)
1324 vty_out (vty
, "%s+-%s%s", prefix
, v
->string
, VTY_NEWLINE
);
1326 if (listcount (v
->path_list
) == 0)
1329 psize
= strlen (prefix
) + 3;
1333 vty_out (vty
, "depth too long ...%s", VTY_NEWLINE
);
1337 restnum
= listcount (v
->path_list
);
1338 for (node
= listhead (v
->path_list
); node
; nextnode (node
))
1341 snprintf (p
, psize
, "%s%s", prefix
, (current_rest
? "| " : " "));
1342 ospf6_spftree_show (vty
, p
, restnum
,
1343 (struct ospf6_vertex
*) getdata (node
));
1349 DEFUN (show_ipv6_ospf6_area_spf_tree
,
1350 show_ipv6_ospf6_area_spf_tree_cmd
,
1351 "show ipv6 ospf6 area A.B.C.D spf tree",
1357 "Shortest Path First caculation\n"
1358 "Displays spf tree\n")
1361 struct ospf6_area
*o6a
;
1363 OSPF6_CMD_CHECK_RUNNING ();
1365 inet_pton (AF_INET
, argv
[0], &area_id
);
1366 o6a
= ospf6_area_lookup (area_id
, ospf6
);
1370 vty_out (vty
, "%s SPF tree for Area %s%s%s",
1371 VTY_NEWLINE
, o6a
->str
, VTY_NEWLINE
, VTY_NEWLINE
);
1373 if (! o6a
->spf_tree
->root
)
1376 ospf6_spftree_show (vty
, "", 0, o6a
->spf_tree
->root
);
1380 DEFUN (show_ipv6_ospf6_area_topology
,
1381 show_ipv6_ospf6_area_topology_cmd
,
1382 "show ipv6 ospf6 area A.B.C.D topology",
1389 "Displays SPF topology table\n")
1391 struct ospf6_area
*o6a
;
1394 OSPF6_CMD_CHECK_RUNNING ();
1396 inet_pton (AF_INET
, argv
[0], &area_id
);
1397 o6a
= ospf6_area_lookup (area_id
, ospf6
);
1405 return ospf6_route_table_show (vty
, argc
, argv
, o6a
->table_topology
);
1408 ALIAS (show_ipv6_ospf6_area_topology
,
1409 show_ipv6_ospf6_area_topology_router_cmd
,
1410 "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>|detail)",
1417 "Displays SPF topology table\n"
1422 ALIAS (show_ipv6_ospf6_area_topology
,
1423 show_ipv6_ospf6_area_topology_router_lsid_cmd
,
1424 "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>) (A.B.C.D|<0-4294967295>)",
1431 "Displays SPF topology table\n"
1441 nexthop_list
= linklist_create ();
1442 ospf6_spf_candidate_init ();
1443 install_element (VIEW_NODE
, &show_ipv6_ospf6_area_spf_node_cmd
);
1444 install_element (VIEW_NODE
, &show_ipv6_ospf6_area_spf_tree_cmd
);
1445 install_element (VIEW_NODE
, &show_ipv6_ospf6_area_topology_cmd
);
1446 install_element (VIEW_NODE
, &show_ipv6_ospf6_area_topology_router_cmd
);
1447 install_element (VIEW_NODE
, &show_ipv6_ospf6_area_topology_router_lsid_cmd
);
1448 install_element (ENABLE_NODE
, &show_ipv6_ospf6_area_spf_node_cmd
);
1449 install_element (ENABLE_NODE
, &show_ipv6_ospf6_area_spf_tree_cmd
);
1450 install_element (ENABLE_NODE
, &show_ipv6_ospf6_area_topology_cmd
);
1451 install_element (ENABLE_NODE
, &show_ipv6_ospf6_area_topology_router_cmd
);
1452 install_element (ENABLE_NODE
, &show_ipv6_ospf6_area_topology_router_lsid_cmd
);