1 /* OSPF SPF calculation.
2 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
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 along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
32 #include "sockunion.h" /* for inet_ntop () */
35 #include "ospfd/ospfd.h"
36 #include "ospfd/ospf_interface.h"
37 #include "ospfd/ospf_ism.h"
38 #include "ospfd/ospf_asbr.h"
39 #include "ospfd/ospf_lsa.h"
40 #include "ospfd/ospf_lsdb.h"
41 #include "ospfd/ospf_neighbor.h"
42 #include "ospfd/ospf_nsm.h"
43 #include "ospfd/ospf_spf.h"
44 #include "ospfd/ospf_route.h"
45 #include "ospfd/ospf_ia.h"
46 #include "ospfd/ospf_ase.h"
47 #include "ospfd/ospf_abr.h"
48 #include "ospfd/ospf_dump.h"
50 /* Variables to ensure a SPF scheduled log message is printed only once */
52 static unsigned int spf_reason_flags
= 0;
54 static void ospf_clear_spf_reason_flags(void)
59 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
61 spf_reason_flags
|= 1 << reason
;
64 static void ospf_vertex_free(void *);
65 /* List of allocated vertices, to simplify cleanup of SPF.
66 * Not thread-safe obviously. If it ever needs to be, it'd have to be
67 * dynamically allocated at begin of ospf_spf_calculate
69 static struct list vertex_list
= {.del
= ospf_vertex_free
};
71 /* Heap related functions, for the managment of the candidates, to
72 * be used with pqueue. */
73 static int cmp(void *node1
, void *node2
)
75 struct vertex
*v1
= (struct vertex
*)node1
;
76 struct vertex
*v2
= (struct vertex
*)node2
;
77 if (v1
!= NULL
&& v2
!= NULL
) {
78 /* network vertices must be chosen before router vertices of
80 * cost in order to find all shortest paths
82 if (((v1
->distance
- v2
->distance
) == 0)
83 && (v1
->type
!= v2
->type
)) {
85 case OSPF_VERTEX_NETWORK
:
87 case OSPF_VERTEX_ROUTER
:
91 return (v1
->distance
- v2
->distance
);
96 static void update_stat(void *node
, int position
)
98 struct vertex
*v
= node
;
100 /* Set the status of the vertex, when its position changes. */
101 *(v
->stat
) = position
;
104 static struct vertex_nexthop
*vertex_nexthop_new(void)
106 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
109 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
111 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
114 /* Free the canonical nexthop objects for an area, ie the nexthop objects
115 * attached to the first-hop router vertices, and any intervening network
118 static void ospf_canonical_nexthops_free(struct vertex
*root
)
120 struct listnode
*node
, *nnode
;
121 struct vertex
*child
;
123 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
124 struct listnode
*n2
, *nn2
;
125 struct vertex_parent
*vp
;
127 /* router vertices through an attached network each
128 * have a distinct (canonical / not inherited) nexthop
129 * which must be freed.
131 * A network vertex can only have router vertices as its
132 * children, so only one level of recursion is possible.
134 if (child
->type
== OSPF_VERTEX_NETWORK
)
135 ospf_canonical_nexthops_free(child
);
137 /* Free child nexthops pointing back to this root vertex */
138 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
))
139 if (vp
->parent
== root
&& vp
->nexthop
)
140 vertex_nexthop_free(vp
->nexthop
);
144 /* TODO: Parent list should be excised, in favour of maintaining only
145 * vertex_nexthop, with refcounts.
147 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
148 struct vertex_nexthop
*hop
)
150 struct vertex_parent
*new;
152 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
158 new->backlink
= backlink
;
163 static void vertex_parent_free(void *p
)
165 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
168 static struct vertex
*ospf_vertex_new(struct ospf_lsa
*lsa
)
172 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
175 new->stat
= &(lsa
->stat
);
176 new->type
= lsa
->data
->type
;
177 new->id
= lsa
->data
->id
;
178 new->lsa
= lsa
->data
;
179 new->children
= list_new();
180 new->parents
= list_new();
181 new->parents
->del
= vertex_parent_free
;
183 listnode_add(&vertex_list
, new);
185 if (IS_DEBUG_OSPF_EVENT
)
186 zlog_debug("%s: Created %s vertex %s", __func__
,
187 new->type
== OSPF_VERTEX_ROUTER
? "Router"
189 inet_ntoa(new->lsa
->id
));
193 static void ospf_vertex_free(void *data
)
195 struct vertex
*v
= data
;
197 if (IS_DEBUG_OSPF_EVENT
)
198 zlog_debug("%s: Free %s vertex %s", __func__
,
199 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
200 inet_ntoa(v
->lsa
->id
));
202 /* There should be no parents potentially holding references to this
204 * Children however may still be there, but presumably referenced by
208 // assert (listcount (v->parents) == 0);
211 list_delete(v
->children
);
215 list_delete(v
->parents
);
220 XFREE(MTYPE_OSPF_VERTEX
, v
);
223 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
224 int print_parents
, int print_children
)
226 if (!IS_DEBUG_OSPF_EVENT
)
229 zlog_debug("%s %s vertex %s distance %u flags %u", msg
,
230 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
231 inet_ntoa(v
->lsa
->id
), v
->distance
, (unsigned int)v
->flags
);
234 struct listnode
*node
;
235 struct vertex_parent
*vp
;
237 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
242 "parent %s backlink %d nexthop %s interface %s",
243 inet_ntoa(vp
->parent
->lsa
->id
),
245 inet_ntop(AF_INET
, &vp
->nexthop
->router
,
248 ? IF_NAME(vp
->nexthop
->oi
)
254 if (print_children
) {
255 struct listnode
*cnode
;
258 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
259 ospf_vertex_dump(" child:", cv
, 0, 0);
264 /* Add a vertex to the list of children in each of its parents. */
265 static void ospf_vertex_add_parent(struct vertex
*v
)
267 struct vertex_parent
*vp
;
268 struct listnode
*node
;
270 assert(v
&& v
->parents
);
272 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
273 assert(vp
->parent
&& vp
->parent
->children
);
275 /* No need to add two links from the same parent. */
276 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
277 listnode_add(vp
->parent
->children
, v
);
281 static void ospf_spf_init(struct ospf_area
*area
)
285 /* Create root node. */
286 v
= ospf_vertex_new(area
->router_lsa_self
);
290 /* Reset ABR and ASBR router counts. */
292 area
->asbr_count
= 0;
295 /* return index of link back to V from W, or -1 if no link found */
296 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
298 unsigned int i
, length
;
299 struct router_lsa
*rl
;
300 struct network_lsa
*nl
;
302 /* In case of W is Network LSA. */
303 if (w
->type
== OSPF_NETWORK_LSA
) {
304 if (v
->type
== OSPF_NETWORK_LSA
)
307 nl
= (struct network_lsa
*)w
;
308 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
310 for (i
= 0; i
< length
; i
++)
311 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
316 /* In case of W is Router LSA. */
317 if (w
->type
== OSPF_ROUTER_LSA
) {
318 rl
= (struct router_lsa
*)w
;
320 length
= ntohs(w
->length
);
322 for (i
= 0; i
< ntohs(rl
->links
)
323 && length
>= sizeof(struct router_lsa
);
325 switch (rl
->link
[i
].type
) {
326 case LSA_LINK_TYPE_POINTOPOINT
:
327 case LSA_LINK_TYPE_VIRTUALLINK
:
329 if (v
->type
== OSPF_ROUTER_LSA
330 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
335 case LSA_LINK_TYPE_TRANSIT
:
336 /* Network LSA ID. */
337 if (v
->type
== OSPF_NETWORK_LSA
338 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
343 case LSA_LINK_TYPE_STUB
:
344 /* Stub can't lead anywhere, carry on */
354 /* Find the next link after prev_link from v to w. If prev_link is
355 * NULL, return the first link from v to w. Ignore stub and virtual links;
356 * these link types will never be returned.
358 static struct router_lsa_link
*
359 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
360 struct router_lsa_link
*prev_link
)
364 u_char lsa_type
= LSA_LINK_TYPE_TRANSIT
;
365 struct router_lsa_link
*l
;
367 if (w
->type
== OSPF_VERTEX_ROUTER
)
368 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
370 if (prev_link
== NULL
)
371 p
= ((u_char
*)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
373 p
= (u_char
*)prev_link
;
374 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
375 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
378 lim
= ((u_char
*)v
->lsa
) + ntohs(v
->lsa
->length
);
381 l
= (struct router_lsa_link
*)p
;
383 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
384 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
386 if (l
->m
[0].type
!= lsa_type
)
389 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
396 static void ospf_spf_flush_parents(struct vertex
*w
)
398 struct vertex_parent
*vp
;
399 struct listnode
*ln
, *nn
;
401 /* delete the existing nexthops */
402 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
403 list_delete_node(w
->parents
, ln
);
405 vertex_nexthop_free(vp
->nexthop
);
406 vertex_parent_free(vp
);
411 * Consider supplied next-hop for inclusion to the supplied list of
412 * equal-cost next-hops, adjust list as neccessary.
414 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
415 struct vertex_nexthop
*newhop
,
416 unsigned int distance
)
418 struct vertex_parent
*vp
, *wp
;
419 struct listnode
*node
;
421 /* we must have a newhop, and a distance */
422 assert(v
&& w
&& newhop
);
425 /* IFF w has already been assigned a distance, then we shouldn't get
427 * unless callers have determined V(l)->W is shortest / equal-shortest
428 * path (0 is a special case distance (no distance yet assigned)).
431 assert(distance
<= w
->distance
);
433 w
->distance
= distance
;
435 if (IS_DEBUG_OSPF_EVENT
) {
436 char buf
[2][INET_ADDRSTRLEN
];
438 "%s: Adding %s as parent of %s", __func__
,
439 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
440 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
444 /* Adding parent for a new, better path: flush existing parents from W.
446 if (distance
< w
->distance
) {
447 if (IS_DEBUG_OSPF_EVENT
)
449 "%s: distance %d better than %d, flushing existing parents",
450 __func__
, distance
, w
->distance
);
451 ospf_spf_flush_parents(w
);
452 w
->distance
= distance
;
455 /* new parent is <= existing parents, add it to parent list (if nexthop
456 * not on parent list)
458 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
459 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
460 if (IS_DEBUG_OSPF_EVENT
)
462 "%s: ... nexthop already on parent list, skipping add",
468 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
469 listnode_add(w
->parents
, vp
);
474 /* 16.1.1. Calculate nexthop from root through V (parent) to
475 * vertex W (destination), with given distance from root->W.
477 * The link must be supplied if V is the root vertex. In all other cases
480 * Note that this function may fail, hence the state of the destination
481 * vertex, W, should /not/ be modified in a dependent manner until
482 * this function returns. This function will update the W vertex with the
483 * provided distance as appropriate.
485 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
486 struct vertex
*v
, struct vertex
*w
,
487 struct router_lsa_link
*l
,
488 unsigned int distance
, int lsa_pos
)
490 struct listnode
*node
, *nnode
;
491 struct vertex_nexthop
*nh
;
492 struct vertex_parent
*vp
;
493 struct ospf_interface
*oi
= NULL
;
494 unsigned int added
= 0;
498 if (IS_DEBUG_OSPF_EVENT
) {
499 zlog_debug("ospf_nexthop_calculation(): Start");
500 ospf_vertex_dump("V (parent):", v
, 1, 1);
501 ospf_vertex_dump("W (dest) :", w
, 1, 1);
502 zlog_debug("V->W distance: %d", distance
);
505 if (v
== area
->spf
) {
506 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
508 root (the calculating router itself). This means that the
509 destination is either a directly connected network or
511 connected router. The outgoing interface in this case is
513 the OSPF interface connecting to the destination
517 /* we *must* be supplied with the link data */
519 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
522 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
524 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
525 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
530 if (IS_DEBUG_OSPF_EVENT
) {
532 "%s: considering link:%s "
533 "type:%d link_id:%s link_data:%s",
534 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
535 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
536 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
540 if (w
->type
== OSPF_VERTEX_ROUTER
) {
541 /* l is a link from v to w
542 * l2 will be link from w to v
544 struct router_lsa_link
*l2
= NULL
;
546 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
547 struct in_addr nexthop
= {.s_addr
= 0};
549 /* If the destination is a router which connects
551 the calculating router via a
553 network, the destination's next hop IP
555 can be determined by examining the
557 router-LSA: each link pointing back to the
558 calculating router and having a Link Data
560 belonging to the Point-to-MultiPoint network
561 provides an IP address of the next hop
564 At this point l is a link from V to W, and V
566 root ("us"). If it is a point-to-multipoint
568 then look through the links in the opposite
570 If any of them have an address that lands
572 subnet declared by the PtMP link, then that
574 is a constituent of the PtMP link, and its
576 a nexthop address for V.
578 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
579 /* Having nexthop = 0 is tempting, but
581 It breaks AS-External routes with a
584 ospf_ase_complete_direct_routes()
586 assume we've reached the last hop and
588 forwarding address as nexthop.
589 Also, users may configure
590 multi-access links in p2p mode,
591 so we need the IP to ARP the nexthop.
593 struct ospf_neighbor
*nbr_w
;
595 nbr_w
= ospf_nbr_lookup_by_routerid(
596 oi
->nbrs
, &l
->link_id
);
599 nexthop
= nbr_w
->src
;
602 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
603 struct prefix_ipv4 la
;
606 la
.prefixlen
= oi
->address
->prefixlen
;
608 /* V links to W on PtMP interface
609 - find the interface address on W */
610 while ((l2
= ospf_get_next_link(w
, v
,
612 la
.prefix
= l2
->link_data
;
614 if (prefix_cmp((struct prefix
619 /* link_data is on our PtMP
622 nexthop
= l2
->link_data
;
628 /* found all necessary info to build
630 nh
= vertex_nexthop_new();
632 nh
->router
= nexthop
;
633 ospf_spf_add_parent(v
, w
, nh
, distance
);
637 "%s: could not determine nexthop for link %s",
638 __func__
, oi
->ifp
->name
);
639 } /* end point-to-point link from V to W */
640 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
641 struct ospf_vl_data
*vl_data
;
643 /* VLink implementation limitations:
644 * a) vl_data can only reference one nexthop, so
646 * to backbone through VLinks. Though
648 * summaries may be considered, and those can
650 * b) We can only use /one/ VLink, even if
652 * exist this router through multiple
655 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
659 && CHECK_FLAG(vl_data
->flags
,
660 OSPF_VL_FLAG_APPROVED
)) {
661 nh
= vertex_nexthop_new();
662 nh
->oi
= vl_data
->nexthop
.oi
;
663 nh
->router
= vl_data
->nexthop
.router
;
664 ospf_spf_add_parent(v
, w
, nh
, distance
);
668 "ospf_nexthop_calculation(): "
669 "vl_data for VL link not found");
670 } /* end virtual-link from V to W */
672 } /* end W is a Router vertex */
674 assert(w
->type
== OSPF_VERTEX_NETWORK
);
676 nh
= vertex_nexthop_new();
678 nh
->router
.s_addr
= 0; /* Nexthop not required */
679 ospf_spf_add_parent(v
, w
, nh
, distance
);
682 } /* end V is the root */
683 /* Check if W's parent is a network connected to root. */
684 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
685 /* See if any of V's parents are the root. */
686 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
687 if (vp
->parent
== area
->spf
) /* connects to root? */
689 /* 16.1.1 para 5. ...the parent vertex is a
691 * directly connects the calculating router to
693 * router. The list of next hops is then
695 * examining the destination's router-LSA...
698 assert(w
->type
== OSPF_VERTEX_ROUTER
);
699 while ((l
= ospf_get_next_link(w
, v
, l
))) {
700 /* ...For each link in the router-LSA
701 * that points back to the
702 * parent network, the link's Link Data
703 * field provides the IP
704 * address of a next hop router. The
705 * outgoing interface to
706 * use can then be derived from the next
708 * it can be inherited from the parent
711 nh
= vertex_nexthop_new();
712 nh
->oi
= vp
->nexthop
->oi
;
713 nh
->router
= l
->link_data
;
715 ospf_spf_add_parent(v
, w
, nh
, distance
);
717 /* Note lack of return is deliberate. See next
721 /* NB: This code is non-trivial.
723 * E.g. it is not enough to know that V connects to the root. It
725 * also important that the while above, looping through all
727 * W->V found at least one link, so that we know there is
728 * bi-directional connectivity between V and W (which need not
730 * case, e.g. when OSPF has not yet converged fully).
732 * we /always/ return here, without having checked that
734 * actually resulted in a valid nexthop being created, then we
736 * prevent SPF from finding/using higher cost paths.
738 * It is important, if root->V->W has not been added, that we
740 * through to the intervening-router nexthop code below. So as
742 * ensure other paths to V may be used. This avoids unnecessary
743 * blackholes while OSPF is convergening.
745 * I.e. we may have arrived at this function, examining V -> W,
747 * workable paths other than root -> V, and it's important to
749 * getting "confused" by non-working root->V->W path - it's
751 * to *not* lose the working non-root paths, just because of a
752 * non-viable root->V->W.
754 * See also bug #330 (required reading!), and:
756 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
762 /* 16.1.1 para 4. If there is at least one intervening router in the
763 * current shortest path between the destination and the root, the
764 * destination simply inherits the set of next hops from the
767 if (IS_DEBUG_OSPF_EVENT
)
768 zlog_debug("%s: Intervening routers, adding parent(s)",
771 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
773 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
779 /* RFC2328 Section 16.1 (2).
780 * v is on the SPF tree. Examine the links in v's LSA. Update the list
781 * of candidates with any vertices not already on the list. If a lower-cost
782 * path is found to a vertex already on the candidate list, store the new cost.
784 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
785 struct pqueue
*candidate
)
787 struct ospf_lsa
*w_lsa
= NULL
;
790 struct router_lsa_link
*l
= NULL
;
792 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
794 /* If this is a router-LSA, and bit V of the router-LSA (see Section
795 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
796 if (v
->type
== OSPF_VERTEX_ROUTER
) {
797 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
798 area
->transit
= OSPF_TRANSIT_TRUE
;
801 if (IS_DEBUG_OSPF_EVENT
)
802 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
803 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
804 inet_ntoa(v
->lsa
->id
));
806 p
= ((u_char
*)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
807 lim
= ((u_char
*)v
->lsa
) + ntohs(v
->lsa
->length
);
811 unsigned int distance
;
813 /* In case of V is Router-LSA. */
814 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
815 l
= (struct router_lsa_link
*)p
;
817 lsa_pos
= lsa_pos_next
; /* LSA link position */
819 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
820 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
822 /* (a) If this is a link to a stub network, examine the
824 link in V's LSA. Links to stub networks will be
825 considered in the second stage of the shortest path
827 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
830 /* (b) Otherwise, W is a transit vertex (router or
832 network). Look up the vertex W's LSA (router-LSA or
833 network-LSA) in Area A's link state database. */
835 case LSA_LINK_TYPE_POINTOPOINT
:
836 case LSA_LINK_TYPE_VIRTUALLINK
:
837 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
838 if (IS_DEBUG_OSPF_EVENT
)
840 "looking up LSA through VL: %s",
841 inet_ntoa(l
->link_id
));
844 w_lsa
= ospf_lsa_lookup(area
, OSPF_ROUTER_LSA
,
845 l
->link_id
, l
->link_id
);
847 if (IS_DEBUG_OSPF_EVENT
)
849 "found Router LSA %s",
850 inet_ntoa(l
->link_id
));
853 case LSA_LINK_TYPE_TRANSIT
:
854 if (IS_DEBUG_OSPF_EVENT
)
856 "Looking up Network LSA, ID: %s",
857 inet_ntoa(l
->link_id
));
858 w_lsa
= ospf_lsa_lookup_by_id(
859 area
, OSPF_NETWORK_LSA
, l
->link_id
);
861 if (IS_DEBUG_OSPF_EVENT
)
862 zlog_debug("found the LSA");
865 zlog_warn("Invalid LSA link type %d", type
);
869 /* In case of V is Network-LSA. */
870 r
= (struct in_addr
*)p
;
871 p
+= sizeof(struct in_addr
);
873 /* Lookup the vertex W's LSA. */
874 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
877 if (IS_DEBUG_OSPF_EVENT
)
878 zlog_debug("found Router LSA %s",
879 inet_ntoa(w_lsa
->data
->id
));
883 /* (b cont.) If the LSA does not exist, or its LS age is equal
884 to MaxAge, or it does not have a link back to vertex V,
885 examine the next link in V's LSA.[23] */
887 if (IS_DEBUG_OSPF_EVENT
)
888 zlog_debug("No LSA found");
892 if (IS_LSA_MAXAGE(w_lsa
)) {
893 if (IS_DEBUG_OSPF_EVENT
)
894 zlog_debug("LSA is MaxAge");
898 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
899 if (IS_DEBUG_OSPF_EVENT
)
900 zlog_debug("The LSA doesn't have a link back");
904 /* (c) If vertex W is already on the shortest-path tree, examine
905 the next link in the LSA. */
906 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
907 if (IS_DEBUG_OSPF_EVENT
)
908 zlog_debug("The LSA is already in SPF");
912 /* (d) Calculate the link state cost D of the resulting path
913 from the root to vertex W. D is equal to the sum of the link
914 state cost of the (already calculated) shortest path to
915 vertex V and the advertised cost of the link between vertices
918 /* calculate link cost D. */
919 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
920 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
921 else /* v is not a Router-LSA */
922 distance
= v
->distance
;
924 /* Is there already vertex W in candidate list? */
925 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
926 /* prepare vertex W. */
927 w
= ospf_vertex_new(w_lsa
);
929 /* Calculate nexthop to W. */
930 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
932 pqueue_enqueue(w
, candidate
);
933 else if (IS_DEBUG_OSPF_EVENT
)
934 zlog_debug("Nexthop Calc failed");
935 } else if (w_lsa
->stat
>= 0) {
936 /* Get the vertex from candidates. */
937 w
= candidate
->array
[w_lsa
->stat
];
939 /* if D is greater than. */
940 if (w
->distance
< distance
) {
944 else if (w
->distance
== distance
) {
945 /* Found an equal-cost path to W.
946 * Calculate nexthop of to W from V. */
947 ospf_nexthop_calculation(area
, v
, w
, l
,
952 /* Found a lower-cost path to W.
953 * nexthop_calculation is conditional, if it
955 * valid nexthop it will call spf_add_parents,
957 * will flush the old parents
959 if (ospf_nexthop_calculation(area
, v
, w
, l
,
961 /* Decrease the key of the node in the
963 * trickle-sort it up towards root, just
965 * node should now be the new root due
967 * (next pqueu_{de,en}queue will fully
968 * re-heap the queue).
970 trickle_up(w_lsa
->stat
, candidate
);
972 } /* end W is already on the candidate list */
973 } /* end loop over the links in V's LSA */
976 static void ospf_spf_dump(struct vertex
*v
, int i
)
978 struct listnode
*cnode
;
979 struct listnode
*nnode
;
980 struct vertex_parent
*parent
;
982 if (v
->type
== OSPF_VERTEX_ROUTER
) {
983 if (IS_DEBUG_OSPF_EVENT
)
984 zlog_debug("SPF Result: %d [R] %s", i
,
985 inet_ntoa(v
->lsa
->id
));
987 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
988 if (IS_DEBUG_OSPF_EVENT
)
989 zlog_debug("SPF Result: %d [N] %s/%d", i
,
990 inet_ntoa(v
->lsa
->id
),
991 ip_masklen(lsa
->mask
));
994 if (IS_DEBUG_OSPF_EVENT
)
995 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
996 zlog_debug(" nexthop %p %s %s", (void *)parent
->nexthop
,
997 inet_ntoa(parent
->nexthop
->router
),
999 ? IF_NAME(parent
->nexthop
->oi
)
1005 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1006 ospf_spf_dump(v
, i
);
1009 /* Second stage of SPF calculation. */
1010 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1011 struct route_table
*rt
, int parent_is_root
)
1013 struct listnode
*cnode
, *cnnode
;
1014 struct vertex
*child
;
1016 if (IS_DEBUG_OSPF_EVENT
)
1017 zlog_debug("ospf_process_stub():processing stubs for area %s",
1018 inet_ntoa(area
->area_id
));
1019 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1022 struct router_lsa_link
*l
;
1023 struct router_lsa
*rlsa
;
1026 if (IS_DEBUG_OSPF_EVENT
)
1028 "ospf_process_stubs():processing router LSA, id: %s",
1029 inet_ntoa(v
->lsa
->id
));
1030 rlsa
= (struct router_lsa
*)v
->lsa
;
1033 if (IS_DEBUG_OSPF_EVENT
)
1035 "ospf_process_stubs(): we have %d links to process",
1036 ntohs(rlsa
->links
));
1037 p
= ((u_char
*)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1038 lim
= ((u_char
*)v
->lsa
) + ntohs(v
->lsa
->length
);
1041 l
= (struct router_lsa_link
*)p
;
1043 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1044 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1046 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1047 ospf_intra_add_stub(rt
, l
, v
, area
,
1048 parent_is_root
, lsa_pos
);
1053 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1056 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1057 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1060 /* the first level of routers connected to the root
1061 * should have 'parent_is_root' set, including those
1062 * connected via a network vertex.
1066 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1069 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1071 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1075 void ospf_rtrs_free(struct route_table
*rtrs
)
1077 struct route_node
*rn
;
1078 struct list
*or_list
;
1079 struct ospf_route
* or ;
1080 struct listnode
*node
, *nnode
;
1082 if (IS_DEBUG_OSPF_EVENT
)
1083 zlog_debug("Route: Router Routing Table free");
1085 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1086 if ((or_list
= rn
->info
) != NULL
) {
1087 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1088 ospf_route_free(or);
1090 list_delete(or_list
);
1092 /* Unlock the node. */
1094 route_unlock_node(rn
);
1096 route_table_finish(rtrs
);
1101 ospf_rtrs_print (struct route_table
*rtrs
)
1103 struct route_node
*rn
;
1104 struct list
*or_list
;
1105 struct listnode
*ln
;
1106 struct listnode
*pnode
;
1107 struct ospf_route
*or;
1108 struct ospf_path
*path
;
1112 if (IS_DEBUG_OSPF_EVENT
)
1113 zlog_debug ("ospf_rtrs_print() start");
1115 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1116 if ((or_list
= rn
->info
) != NULL
)
1117 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1119 switch (or->path_type
)
1121 case OSPF_PATH_INTRA_AREA
:
1122 if (IS_DEBUG_OSPF_EVENT
)
1123 zlog_debug ("%s [%d] area: %s",
1124 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1125 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1128 case OSPF_PATH_INTER_AREA
:
1129 if (IS_DEBUG_OSPF_EVENT
)
1130 zlog_debug ("%s IA [%d] area: %s",
1131 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1132 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1139 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1141 if (path
->nexthop
.s_addr
== 0)
1143 if (IS_DEBUG_OSPF_EVENT
)
1144 zlog_debug (" directly attached to %s\r\n",
1145 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1149 if (IS_DEBUG_OSPF_EVENT
)
1150 zlog_debug (" via %s, %s\r\n",
1151 inet_ntoa (path
->nexthop
),
1152 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1157 zlog_debug ("ospf_rtrs_print() end");
1161 /* Calculating the shortest-path tree for an area. */
1162 static void ospf_spf_calculate(struct ospf_area
*area
,
1163 struct route_table
*new_table
,
1164 struct route_table
*new_rtrs
)
1166 struct pqueue
*candidate
;
1169 if (IS_DEBUG_OSPF_EVENT
) {
1170 zlog_debug("ospf_spf_calculate: Start");
1171 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1172 inet_ntoa(area
->area_id
));
1175 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1176 return this area's calculation. */
1177 if (!area
->router_lsa_self
) {
1178 if (IS_DEBUG_OSPF_EVENT
)
1180 "ospf_spf_calculate: "
1181 "Skip area %s's calculation due to empty router_lsa_self",
1182 inet_ntoa(area
->area_id
));
1186 /* RFC2328 16.1. (1). */
1187 /* Initialize the algorithm's data structures. */
1189 /* This function scans all the LSA database and set the stat field to
1190 * LSA_SPF_NOT_EXPLORED. */
1191 ospf_lsdb_clean_stat(area
->lsdb
);
1192 /* Create a new heap for the candidates. */
1193 candidate
= pqueue_create();
1194 candidate
->cmp
= cmp
;
1195 candidate
->update
= update_stat
;
1197 /* Initialize the shortest-path tree to only the root (which is the
1198 router doing the calculation). */
1199 ospf_spf_init(area
);
1201 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1204 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1206 /* Set Area A's TransitCapability to FALSE. */
1207 area
->transit
= OSPF_TRANSIT_FALSE
;
1208 area
->shortcut_capability
= 1;
1211 /* RFC2328 16.1. (2). */
1212 ospf_spf_next(v
, area
, candidate
);
1214 /* RFC2328 16.1. (3). */
1215 /* If at this step the candidate list is empty, the shortest-
1216 path tree (of transit vertices) has been completely built and
1217 this stage of the procedure terminates. */
1218 if (candidate
->size
== 0)
1221 /* Otherwise, choose the vertex belonging to the candidate list
1222 that is closest to the root, and add it to the shortest-path
1223 tree (removing it from the candidate list in the
1225 /* Extract from the candidates the node with the lower key. */
1226 v
= (struct vertex
*)pqueue_dequeue(candidate
);
1227 /* Update stat field in vertex. */
1228 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1230 ospf_vertex_add_parent(v
);
1232 /* RFC2328 16.1. (4). */
1233 if (v
->type
== OSPF_VERTEX_ROUTER
)
1234 ospf_intra_add_router(new_rtrs
, v
, area
);
1236 ospf_intra_add_transit(new_table
, v
, area
);
1238 /* RFC2328 16.1. (5). */
1239 /* Iterate the algorithm by returning to Step 2. */
1241 } /* end loop until no more candidate vertices */
1243 if (IS_DEBUG_OSPF_EVENT
) {
1244 ospf_spf_dump(area
->spf
, 0);
1245 ospf_route_table_dump(new_table
);
1248 /* Second stage of SPF calculation procedure's */
1249 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1251 /* Free candidate queue. */
1252 pqueue_delete(candidate
);
1254 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1255 /* Free nexthop information, canonical versions of which are attached
1256 * the first level of router vertices attached to the root vertex, see
1257 * ospf_nexthop_calculation.
1259 ospf_canonical_nexthops_free(area
->spf
);
1261 /* Increment SPF Calculation Counter. */
1262 area
->spf_calculation
++;
1264 monotime(&area
->ospf
->ts_spf
);
1265 area
->ts_spf
= area
->ospf
->ts_spf
;
1267 if (IS_DEBUG_OSPF_EVENT
)
1268 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1269 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1271 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1274 list_delete_all_node(&vertex_list
);
1277 /* Timer for SPF calculation. */
1278 static int ospf_spf_calculate_timer(struct thread
*thread
)
1280 struct ospf
*ospf
= THREAD_ARG(thread
);
1281 struct route_table
*new_table
, *new_rtrs
;
1282 struct ospf_area
*area
;
1283 struct listnode
*node
, *nnode
;
1284 struct timeval start_time
, spf_start_time
;
1285 int areas_processed
= 0;
1286 unsigned long ia_time
, prune_time
, rt_time
;
1287 unsigned long abr_time
, total_spf_time
, spf_time
;
1288 char rbuf
[32]; /* reason_buf */
1290 if (IS_DEBUG_OSPF_EVENT
)
1291 zlog_debug("SPF: Timer (SPF calculation expire)");
1293 ospf
->t_spf_calc
= NULL
;
1295 monotime(&spf_start_time
);
1296 /* Allocate new table tree. */
1297 new_table
= route_table_init();
1298 new_rtrs
= route_table_init();
1300 ospf_vl_unapprove(ospf
);
1302 /* Calculate SPF for each area. */
1303 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1304 /* Do backbone last, so as to first discover intra-area paths
1305 * for any back-bone virtual-links
1307 if (ospf
->backbone
&& ospf
->backbone
== area
)
1310 ospf_spf_calculate(area
, new_table
, new_rtrs
);
1314 /* SPF for backbone, if required */
1315 if (ospf
->backbone
) {
1316 ospf_spf_calculate(ospf
->backbone
, new_table
, new_rtrs
);
1320 spf_time
= monotime_since(&spf_start_time
, NULL
);
1322 ospf_vl_shut_unapproved(ospf
);
1324 monotime(&start_time
);
1325 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1326 ia_time
= monotime_since(&start_time
, NULL
);
1328 monotime(&start_time
);
1329 ospf_prune_unreachable_networks(new_table
);
1330 ospf_prune_unreachable_routers(new_rtrs
);
1331 prune_time
= monotime_since(&start_time
, NULL
);
1333 /* AS-external-LSA calculation should not be performed here. */
1335 /* If new Router Route is installed,
1336 then schedule re-calculate External routes. */
1338 ospf_ase_calculate_schedule(ospf
);
1340 ospf_ase_calculate_timer_add(ospf
);
1342 /* Update routing table. */
1343 monotime(&start_time
);
1344 ospf_route_install(ospf
, new_table
);
1345 rt_time
= monotime_since(&start_time
, NULL
);
1347 /* Update ABR/ASBR routing table */
1348 if (ospf
->old_rtrs
) {
1349 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1351 /* ospf_route_delete (ospf->old_rtrs); */
1352 ospf_rtrs_free(ospf
->old_rtrs
);
1355 ospf
->old_rtrs
= ospf
->new_rtrs
;
1356 ospf
->new_rtrs
= new_rtrs
;
1358 monotime(&start_time
);
1359 if (IS_OSPF_ABR(ospf
))
1360 ospf_abr_task(ospf
);
1361 abr_time
= monotime_since(&start_time
, NULL
);
1364 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1367 if (spf_reason_flags
) {
1368 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1369 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1370 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1371 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1372 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1373 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1374 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1375 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1376 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1377 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1378 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1379 strncat(rbuf
, "ASBR, ",
1380 sizeof(rbuf
) - strlen(rbuf
) - 1);
1381 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1382 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1384 size_t rbuflen
= strlen(rbuf
);
1386 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1391 if (IS_DEBUG_OSPF_EVENT
) {
1392 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1393 zlog_info("\t SPF Time: %ld", spf_time
);
1394 zlog_info("\t InterArea: %ld", ia_time
);
1395 zlog_info("\t Prune: %ld", prune_time
);
1396 zlog_info("\tRouteInstall: %ld", rt_time
);
1397 if (IS_OSPF_ABR(ospf
))
1398 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1400 zlog_info("Reason(s) for SPF: %s", rbuf
);
1403 ospf_clear_spf_reason_flags();
1408 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1409 set timer for SPF calc. */
1410 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1412 unsigned long delay
, elapsed
, ht
;
1414 if (IS_DEBUG_OSPF_EVENT
)
1415 zlog_debug("SPF: calculation timer scheduled");
1417 /* OSPF instance does not exist. */
1421 ospf_spf_set_reason(reason
);
1423 /* SPF calculation timer is already scheduled. */
1424 if (ospf
->t_spf_calc
) {
1425 if (IS_DEBUG_OSPF_EVENT
)
1427 "SPF: calculation timer is already scheduled: %p",
1428 (void *)ospf
->t_spf_calc
);
1432 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1434 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1436 if (ht
> ospf
->spf_max_holdtime
)
1437 ht
= ospf
->spf_max_holdtime
;
1439 /* Get SPF calculation delay time. */
1441 /* Got an event within the hold time of last SPF. We need to
1442 * increase the hold_multiplier, if it's not already at/past
1443 * maximum value, and wasn't already increased..
1445 if (ht
< ospf
->spf_max_holdtime
)
1446 ospf
->spf_hold_multiplier
++;
1448 /* always honour the SPF initial delay */
1449 if ((ht
- elapsed
) < ospf
->spf_delay
)
1450 delay
= ospf
->spf_delay
;
1452 delay
= ht
- elapsed
;
1454 /* Event is past required hold-time of last SPF */
1455 delay
= ospf
->spf_delay
;
1456 ospf
->spf_hold_multiplier
= 1;
1459 if (IS_DEBUG_OSPF_EVENT
)
1460 zlog_debug("SPF: calculation timer delay = %ld", delay
);
1462 zlog_info("SPF: Scheduled in %ld msec", delay
);
1464 ospf
->t_spf_calc
= NULL
;
1465 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,