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
);
404 vertex_parent_free(vp
);
409 * Consider supplied next-hop for inclusion to the supplied list of
410 * equal-cost next-hops, adjust list as neccessary.
412 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
413 struct vertex_nexthop
*newhop
,
414 unsigned int distance
)
416 struct vertex_parent
*vp
, *wp
;
417 struct listnode
*node
;
419 /* we must have a newhop, and a distance */
420 assert(v
&& w
&& newhop
);
423 /* IFF w has already been assigned a distance, then we shouldn't get
425 * unless callers have determined V(l)->W is shortest / equal-shortest
426 * path (0 is a special case distance (no distance yet assigned)).
429 assert(distance
<= w
->distance
);
431 w
->distance
= distance
;
433 if (IS_DEBUG_OSPF_EVENT
) {
434 char buf
[2][INET_ADDRSTRLEN
];
436 "%s: Adding %s as parent of %s", __func__
,
437 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
438 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
442 /* Adding parent for a new, better path: flush existing parents from W.
444 if (distance
< w
->distance
) {
445 if (IS_DEBUG_OSPF_EVENT
)
447 "%s: distance %d better than %d, flushing existing parents",
448 __func__
, distance
, w
->distance
);
449 ospf_spf_flush_parents(w
);
450 w
->distance
= distance
;
453 /* new parent is <= existing parents, add it to parent list (if nexthop
454 * not on parent list)
456 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
457 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
458 if (IS_DEBUG_OSPF_EVENT
)
460 "%s: ... nexthop already on parent list, skipping add",
466 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
467 listnode_add(w
->parents
, vp
);
472 /* 16.1.1. Calculate nexthop from root through V (parent) to
473 * vertex W (destination), with given distance from root->W.
475 * The link must be supplied if V is the root vertex. In all other cases
478 * Note that this function may fail, hence the state of the destination
479 * vertex, W, should /not/ be modified in a dependent manner until
480 * this function returns. This function will update the W vertex with the
481 * provided distance as appropriate.
483 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
484 struct vertex
*v
, struct vertex
*w
,
485 struct router_lsa_link
*l
,
486 unsigned int distance
, int lsa_pos
)
488 struct listnode
*node
, *nnode
;
489 struct vertex_nexthop
*nh
;
490 struct vertex_parent
*vp
;
491 struct ospf_interface
*oi
= NULL
;
492 unsigned int added
= 0;
496 if (IS_DEBUG_OSPF_EVENT
) {
497 zlog_debug("ospf_nexthop_calculation(): Start");
498 ospf_vertex_dump("V (parent):", v
, 1, 1);
499 ospf_vertex_dump("W (dest) :", w
, 1, 1);
500 zlog_debug("V->W distance: %d", distance
);
503 if (v
== area
->spf
) {
504 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
506 root (the calculating router itself). This means that the
507 destination is either a directly connected network or
509 connected router. The outgoing interface in this case is
511 the OSPF interface connecting to the destination
515 /* we *must* be supplied with the link data */
517 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
520 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
522 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
523 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
528 if (IS_DEBUG_OSPF_EVENT
) {
530 "%s: considering link:%s "
531 "type:%d link_id:%s link_data:%s",
532 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
533 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
534 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
538 if (w
->type
== OSPF_VERTEX_ROUTER
) {
539 /* l is a link from v to w
540 * l2 will be link from w to v
542 struct router_lsa_link
*l2
= NULL
;
544 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
545 struct in_addr nexthop
= {.s_addr
= 0};
547 /* If the destination is a router which connects
549 the calculating router via a
551 network, the destination's next hop IP
553 can be determined by examining the
555 router-LSA: each link pointing back to the
556 calculating router and having a Link Data
558 belonging to the Point-to-MultiPoint network
559 provides an IP address of the next hop
562 At this point l is a link from V to W, and V
564 root ("us"). If it is a point-to-multipoint
566 then look through the links in the opposite
568 If any of them have an address that lands
570 subnet declared by the PtMP link, then that
572 is a constituent of the PtMP link, and its
574 a nexthop address for V.
576 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
577 /* Having nexthop = 0 is tempting, but
579 It breaks AS-External routes with a
582 ospf_ase_complete_direct_routes()
584 assume we've reached the last hop and
586 forwarding address as nexthop.
587 Also, users may configure
588 multi-access links in p2p mode,
589 so we need the IP to ARP the nexthop.
591 struct ospf_neighbor
*nbr_w
;
593 nbr_w
= ospf_nbr_lookup_by_routerid(
594 oi
->nbrs
, &l
->link_id
);
597 nexthop
= nbr_w
->src
;
600 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
601 struct prefix_ipv4 la
;
604 la
.prefixlen
= oi
->address
->prefixlen
;
606 /* V links to W on PtMP interface
607 - find the interface address on W */
608 while ((l2
= ospf_get_next_link(w
, v
,
610 la
.prefix
= l2
->link_data
;
612 if (prefix_cmp((struct prefix
617 /* link_data is on our PtMP
620 nexthop
= l2
->link_data
;
626 /* found all necessary info to build
628 nh
= vertex_nexthop_new();
630 nh
->router
= nexthop
;
631 ospf_spf_add_parent(v
, w
, nh
, distance
);
635 "%s: could not determine nexthop for link %s",
636 __func__
, oi
->ifp
->name
);
637 } /* end point-to-point link from V to W */
638 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
639 struct ospf_vl_data
*vl_data
;
641 /* VLink implementation limitations:
642 * a) vl_data can only reference one nexthop, so
644 * to backbone through VLinks. Though
646 * summaries may be considered, and those can
648 * b) We can only use /one/ VLink, even if
650 * exist this router through multiple
653 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
657 && CHECK_FLAG(vl_data
->flags
,
658 OSPF_VL_FLAG_APPROVED
)) {
659 nh
= vertex_nexthop_new();
660 nh
->oi
= vl_data
->nexthop
.oi
;
661 nh
->router
= vl_data
->nexthop
.router
;
662 ospf_spf_add_parent(v
, w
, nh
, distance
);
666 "ospf_nexthop_calculation(): "
667 "vl_data for VL link not found");
668 } /* end virtual-link from V to W */
670 } /* end W is a Router vertex */
672 assert(w
->type
== OSPF_VERTEX_NETWORK
);
674 nh
= vertex_nexthop_new();
676 nh
->router
.s_addr
= 0; /* Nexthop not required */
677 ospf_spf_add_parent(v
, w
, nh
, distance
);
680 } /* end V is the root */
681 /* Check if W's parent is a network connected to root. */
682 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
683 /* See if any of V's parents are the root. */
684 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
685 if (vp
->parent
== area
->spf
) /* connects to root? */
687 /* 16.1.1 para 5. ...the parent vertex is a
689 * directly connects the calculating router to
691 * router. The list of next hops is then
693 * examining the destination's router-LSA...
696 assert(w
->type
== OSPF_VERTEX_ROUTER
);
697 while ((l
= ospf_get_next_link(w
, v
, l
))) {
698 /* ...For each link in the router-LSA
699 * that points back to the
700 * parent network, the link's Link Data
701 * field provides the IP
702 * address of a next hop router. The
703 * outgoing interface to
704 * use can then be derived from the next
706 * it can be inherited from the parent
709 nh
= vertex_nexthop_new();
710 nh
->oi
= vp
->nexthop
->oi
;
711 nh
->router
= l
->link_data
;
713 ospf_spf_add_parent(v
, w
, nh
, distance
);
715 /* Note lack of return is deliberate. See next
719 /* NB: This code is non-trivial.
721 * E.g. it is not enough to know that V connects to the root. It
723 * also important that the while above, looping through all
725 * W->V found at least one link, so that we know there is
726 * bi-directional connectivity between V and W (which need not
728 * case, e.g. when OSPF has not yet converged fully).
730 * we /always/ return here, without having checked that
732 * actually resulted in a valid nexthop being created, then we
734 * prevent SPF from finding/using higher cost paths.
736 * It is important, if root->V->W has not been added, that we
738 * through to the intervening-router nexthop code below. So as
740 * ensure other paths to V may be used. This avoids unnecessary
741 * blackholes while OSPF is convergening.
743 * I.e. we may have arrived at this function, examining V -> W,
745 * workable paths other than root -> V, and it's important to
747 * getting "confused" by non-working root->V->W path - it's
749 * to *not* lose the working non-root paths, just because of a
750 * non-viable root->V->W.
752 * See also bug #330 (required reading!), and:
754 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
760 /* 16.1.1 para 4. If there is at least one intervening router in the
761 * current shortest path between the destination and the root, the
762 * destination simply inherits the set of next hops from the
765 if (IS_DEBUG_OSPF_EVENT
)
766 zlog_debug("%s: Intervening routers, adding parent(s)",
769 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
771 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
777 /* RFC2328 Section 16.1 (2).
778 * v is on the SPF tree. Examine the links in v's LSA. Update the list
779 * of candidates with any vertices not already on the list. If a lower-cost
780 * path is found to a vertex already on the candidate list, store the new cost.
782 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
783 struct pqueue
*candidate
)
785 struct ospf_lsa
*w_lsa
= NULL
;
788 struct router_lsa_link
*l
= NULL
;
790 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
792 /* If this is a router-LSA, and bit V of the router-LSA (see Section
793 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
794 if (v
->type
== OSPF_VERTEX_ROUTER
) {
795 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
796 area
->transit
= OSPF_TRANSIT_TRUE
;
799 if (IS_DEBUG_OSPF_EVENT
)
800 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
801 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
802 inet_ntoa(v
->lsa
->id
));
804 p
= ((u_char
*)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
805 lim
= ((u_char
*)v
->lsa
) + ntohs(v
->lsa
->length
);
809 unsigned int distance
;
811 /* In case of V is Router-LSA. */
812 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
813 l
= (struct router_lsa_link
*)p
;
815 lsa_pos
= lsa_pos_next
; /* LSA link position */
817 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
818 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
820 /* (a) If this is a link to a stub network, examine the
822 link in V's LSA. Links to stub networks will be
823 considered in the second stage of the shortest path
825 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
828 /* (b) Otherwise, W is a transit vertex (router or
830 network). Look up the vertex W's LSA (router-LSA or
831 network-LSA) in Area A's link state database. */
833 case LSA_LINK_TYPE_POINTOPOINT
:
834 case LSA_LINK_TYPE_VIRTUALLINK
:
835 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
836 if (IS_DEBUG_OSPF_EVENT
)
838 "looking up LSA through VL: %s",
839 inet_ntoa(l
->link_id
));
842 w_lsa
= ospf_lsa_lookup(area
, OSPF_ROUTER_LSA
,
843 l
->link_id
, l
->link_id
);
845 if (IS_DEBUG_OSPF_EVENT
)
847 "found Router LSA %s",
848 inet_ntoa(l
->link_id
));
851 case LSA_LINK_TYPE_TRANSIT
:
852 if (IS_DEBUG_OSPF_EVENT
)
854 "Looking up Network LSA, ID: %s",
855 inet_ntoa(l
->link_id
));
856 w_lsa
= ospf_lsa_lookup_by_id(
857 area
, OSPF_NETWORK_LSA
, l
->link_id
);
859 if (IS_DEBUG_OSPF_EVENT
)
860 zlog_debug("found the LSA");
863 zlog_warn("Invalid LSA link type %d", type
);
867 /* In case of V is Network-LSA. */
868 r
= (struct in_addr
*)p
;
869 p
+= sizeof(struct in_addr
);
871 /* Lookup the vertex W's LSA. */
872 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
875 if (IS_DEBUG_OSPF_EVENT
)
876 zlog_debug("found Router LSA %s",
877 inet_ntoa(w_lsa
->data
->id
));
881 /* (b cont.) If the LSA does not exist, or its LS age is equal
882 to MaxAge, or it does not have a link back to vertex V,
883 examine the next link in V's LSA.[23] */
885 if (IS_DEBUG_OSPF_EVENT
)
886 zlog_debug("No LSA found");
890 if (IS_LSA_MAXAGE(w_lsa
)) {
891 if (IS_DEBUG_OSPF_EVENT
)
892 zlog_debug("LSA is MaxAge");
896 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
897 if (IS_DEBUG_OSPF_EVENT
)
898 zlog_debug("The LSA doesn't have a link back");
902 /* (c) If vertex W is already on the shortest-path tree, examine
903 the next link in the LSA. */
904 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
905 if (IS_DEBUG_OSPF_EVENT
)
906 zlog_debug("The LSA is already in SPF");
910 /* (d) Calculate the link state cost D of the resulting path
911 from the root to vertex W. D is equal to the sum of the link
912 state cost of the (already calculated) shortest path to
913 vertex V and the advertised cost of the link between vertices
916 /* calculate link cost D. */
917 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
918 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
919 else /* v is not a Router-LSA */
920 distance
= v
->distance
;
922 /* Is there already vertex W in candidate list? */
923 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
924 /* prepare vertex W. */
925 w
= ospf_vertex_new(w_lsa
);
927 /* Calculate nexthop to W. */
928 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
930 pqueue_enqueue(w
, candidate
);
931 else if (IS_DEBUG_OSPF_EVENT
)
932 zlog_debug("Nexthop Calc failed");
933 } else if (w_lsa
->stat
>= 0) {
934 /* Get the vertex from candidates. */
935 w
= candidate
->array
[w_lsa
->stat
];
937 /* if D is greater than. */
938 if (w
->distance
< distance
) {
942 else if (w
->distance
== distance
) {
943 /* Found an equal-cost path to W.
944 * Calculate nexthop of to W from V. */
945 ospf_nexthop_calculation(area
, v
, w
, l
,
950 /* Found a lower-cost path to W.
951 * nexthop_calculation is conditional, if it
953 * valid nexthop it will call spf_add_parents,
955 * will flush the old parents
957 if (ospf_nexthop_calculation(area
, v
, w
, l
,
959 /* Decrease the key of the node in the
961 * trickle-sort it up towards root, just
963 * node should now be the new root due
965 * (next pqueu_{de,en}queue will fully
966 * re-heap the queue).
968 trickle_up(w_lsa
->stat
, candidate
);
970 } /* end W is already on the candidate list */
971 } /* end loop over the links in V's LSA */
974 static void ospf_spf_dump(struct vertex
*v
, int i
)
976 struct listnode
*cnode
;
977 struct listnode
*nnode
;
978 struct vertex_parent
*parent
;
980 if (v
->type
== OSPF_VERTEX_ROUTER
) {
981 if (IS_DEBUG_OSPF_EVENT
)
982 zlog_debug("SPF Result: %d [R] %s", i
,
983 inet_ntoa(v
->lsa
->id
));
985 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
986 if (IS_DEBUG_OSPF_EVENT
)
987 zlog_debug("SPF Result: %d [N] %s/%d", i
,
988 inet_ntoa(v
->lsa
->id
),
989 ip_masklen(lsa
->mask
));
992 if (IS_DEBUG_OSPF_EVENT
)
993 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
994 zlog_debug(" nexthop %p %s %s", (void *)parent
->nexthop
,
995 inet_ntoa(parent
->nexthop
->router
),
997 ? IF_NAME(parent
->nexthop
->oi
)
1003 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1004 ospf_spf_dump(v
, i
);
1007 /* Second stage of SPF calculation. */
1008 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1009 struct route_table
*rt
, int parent_is_root
)
1011 struct listnode
*cnode
, *cnnode
;
1012 struct vertex
*child
;
1014 if (IS_DEBUG_OSPF_EVENT
)
1015 zlog_debug("ospf_process_stub():processing stubs for area %s",
1016 inet_ntoa(area
->area_id
));
1017 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1020 struct router_lsa_link
*l
;
1021 struct router_lsa
*rlsa
;
1024 if (IS_DEBUG_OSPF_EVENT
)
1026 "ospf_process_stubs():processing router LSA, id: %s",
1027 inet_ntoa(v
->lsa
->id
));
1028 rlsa
= (struct router_lsa
*)v
->lsa
;
1031 if (IS_DEBUG_OSPF_EVENT
)
1033 "ospf_process_stubs(): we have %d links to process",
1034 ntohs(rlsa
->links
));
1035 p
= ((u_char
*)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1036 lim
= ((u_char
*)v
->lsa
) + ntohs(v
->lsa
->length
);
1039 l
= (struct router_lsa_link
*)p
;
1041 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1042 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1044 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1045 ospf_intra_add_stub(rt
, l
, v
, area
,
1046 parent_is_root
, lsa_pos
);
1051 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1054 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1055 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1058 /* the first level of routers connected to the root
1059 * should have 'parent_is_root' set, including those
1060 * connected via a network vertex.
1064 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1067 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1069 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1073 void ospf_rtrs_free(struct route_table
*rtrs
)
1075 struct route_node
*rn
;
1076 struct list
*or_list
;
1077 struct ospf_route
* or ;
1078 struct listnode
*node
, *nnode
;
1080 if (IS_DEBUG_OSPF_EVENT
)
1081 zlog_debug("Route: Router Routing Table free");
1083 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1084 if ((or_list
= rn
->info
) != NULL
) {
1085 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1086 ospf_route_free(or);
1088 list_delete(or_list
);
1090 /* Unlock the node. */
1092 route_unlock_node(rn
);
1094 route_table_finish(rtrs
);
1099 ospf_rtrs_print (struct route_table
*rtrs
)
1101 struct route_node
*rn
;
1102 struct list
*or_list
;
1103 struct listnode
*ln
;
1104 struct listnode
*pnode
;
1105 struct ospf_route
*or;
1106 struct ospf_path
*path
;
1110 if (IS_DEBUG_OSPF_EVENT
)
1111 zlog_debug ("ospf_rtrs_print() start");
1113 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1114 if ((or_list
= rn
->info
) != NULL
)
1115 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1117 switch (or->path_type
)
1119 case OSPF_PATH_INTRA_AREA
:
1120 if (IS_DEBUG_OSPF_EVENT
)
1121 zlog_debug ("%s [%d] area: %s",
1122 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1123 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1126 case OSPF_PATH_INTER_AREA
:
1127 if (IS_DEBUG_OSPF_EVENT
)
1128 zlog_debug ("%s IA [%d] area: %s",
1129 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1130 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1137 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1139 if (path
->nexthop
.s_addr
== 0)
1141 if (IS_DEBUG_OSPF_EVENT
)
1142 zlog_debug (" directly attached to %s\r\n",
1143 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1147 if (IS_DEBUG_OSPF_EVENT
)
1148 zlog_debug (" via %s, %s\r\n",
1149 inet_ntoa (path
->nexthop
),
1150 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1155 zlog_debug ("ospf_rtrs_print() end");
1159 /* Calculating the shortest-path tree for an area. */
1160 static void ospf_spf_calculate(struct ospf_area
*area
,
1161 struct route_table
*new_table
,
1162 struct route_table
*new_rtrs
)
1164 struct pqueue
*candidate
;
1167 if (IS_DEBUG_OSPF_EVENT
) {
1168 zlog_debug("ospf_spf_calculate: Start");
1169 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1170 inet_ntoa(area
->area_id
));
1173 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1174 return this area's calculation. */
1175 if (!area
->router_lsa_self
) {
1176 if (IS_DEBUG_OSPF_EVENT
)
1178 "ospf_spf_calculate: "
1179 "Skip area %s's calculation due to empty router_lsa_self",
1180 inet_ntoa(area
->area_id
));
1184 /* RFC2328 16.1. (1). */
1185 /* Initialize the algorithm's data structures. */
1187 /* This function scans all the LSA database and set the stat field to
1188 * LSA_SPF_NOT_EXPLORED. */
1189 ospf_lsdb_clean_stat(area
->lsdb
);
1190 /* Create a new heap for the candidates. */
1191 candidate
= pqueue_create();
1192 candidate
->cmp
= cmp
;
1193 candidate
->update
= update_stat
;
1195 /* Initialize the shortest-path tree to only the root (which is the
1196 router doing the calculation). */
1197 ospf_spf_init(area
);
1199 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1202 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1204 /* Set Area A's TransitCapability to FALSE. */
1205 area
->transit
= OSPF_TRANSIT_FALSE
;
1206 area
->shortcut_capability
= 1;
1209 /* RFC2328 16.1. (2). */
1210 ospf_spf_next(v
, area
, candidate
);
1212 /* RFC2328 16.1. (3). */
1213 /* If at this step the candidate list is empty, the shortest-
1214 path tree (of transit vertices) has been completely built and
1215 this stage of the procedure terminates. */
1216 if (candidate
->size
== 0)
1219 /* Otherwise, choose the vertex belonging to the candidate list
1220 that is closest to the root, and add it to the shortest-path
1221 tree (removing it from the candidate list in the
1223 /* Extract from the candidates the node with the lower key. */
1224 v
= (struct vertex
*)pqueue_dequeue(candidate
);
1225 /* Update stat field in vertex. */
1226 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1228 ospf_vertex_add_parent(v
);
1230 /* RFC2328 16.1. (4). */
1231 if (v
->type
== OSPF_VERTEX_ROUTER
)
1232 ospf_intra_add_router(new_rtrs
, v
, area
);
1234 ospf_intra_add_transit(new_table
, v
, area
);
1236 /* RFC2328 16.1. (5). */
1237 /* Iterate the algorithm by returning to Step 2. */
1239 } /* end loop until no more candidate vertices */
1241 if (IS_DEBUG_OSPF_EVENT
) {
1242 ospf_spf_dump(area
->spf
, 0);
1243 ospf_route_table_dump(new_table
);
1246 /* Second stage of SPF calculation procedure's */
1247 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1249 /* Free candidate queue. */
1250 pqueue_delete(candidate
);
1252 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1253 /* Free nexthop information, canonical versions of which are attached
1254 * the first level of router vertices attached to the root vertex, see
1255 * ospf_nexthop_calculation.
1257 ospf_canonical_nexthops_free(area
->spf
);
1259 /* Increment SPF Calculation Counter. */
1260 area
->spf_calculation
++;
1262 monotime(&area
->ospf
->ts_spf
);
1263 area
->ts_spf
= area
->ospf
->ts_spf
;
1265 if (IS_DEBUG_OSPF_EVENT
)
1266 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1267 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1269 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1272 list_delete_all_node(&vertex_list
);
1275 /* Timer for SPF calculation. */
1276 static int ospf_spf_calculate_timer(struct thread
*thread
)
1278 struct ospf
*ospf
= THREAD_ARG(thread
);
1279 struct route_table
*new_table
, *new_rtrs
;
1280 struct ospf_area
*area
;
1281 struct listnode
*node
, *nnode
;
1282 struct timeval start_time
, spf_start_time
;
1283 int areas_processed
= 0;
1284 unsigned long ia_time
, prune_time
, rt_time
;
1285 unsigned long abr_time
, total_spf_time
, spf_time
;
1286 char rbuf
[32]; /* reason_buf */
1288 if (IS_DEBUG_OSPF_EVENT
)
1289 zlog_debug("SPF: Timer (SPF calculation expire)");
1291 ospf
->t_spf_calc
= NULL
;
1293 monotime(&spf_start_time
);
1294 /* Allocate new table tree. */
1295 new_table
= route_table_init();
1296 new_rtrs
= route_table_init();
1298 ospf_vl_unapprove(ospf
);
1300 /* Calculate SPF for each area. */
1301 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1302 /* Do backbone last, so as to first discover intra-area paths
1303 * for any back-bone virtual-links
1305 if (ospf
->backbone
&& ospf
->backbone
== area
)
1308 ospf_spf_calculate(area
, new_table
, new_rtrs
);
1312 /* SPF for backbone, if required */
1313 if (ospf
->backbone
) {
1314 ospf_spf_calculate(ospf
->backbone
, new_table
, new_rtrs
);
1318 spf_time
= monotime_since(&spf_start_time
, NULL
);
1320 ospf_vl_shut_unapproved(ospf
);
1322 monotime(&start_time
);
1323 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1324 ia_time
= monotime_since(&start_time
, NULL
);
1326 monotime(&start_time
);
1327 ospf_prune_unreachable_networks(new_table
);
1328 ospf_prune_unreachable_routers(new_rtrs
);
1329 prune_time
= monotime_since(&start_time
, NULL
);
1331 /* AS-external-LSA calculation should not be performed here. */
1333 /* If new Router Route is installed,
1334 then schedule re-calculate External routes. */
1336 ospf_ase_calculate_schedule(ospf
);
1338 ospf_ase_calculate_timer_add(ospf
);
1340 /* Update routing table. */
1341 monotime(&start_time
);
1342 ospf_route_install(ospf
, new_table
);
1343 rt_time
= monotime_since(&start_time
, NULL
);
1345 /* Update ABR/ASBR routing table */
1346 if (ospf
->old_rtrs
) {
1347 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1349 /* ospf_route_delete (ospf->old_rtrs); */
1350 ospf_rtrs_free(ospf
->old_rtrs
);
1353 ospf
->old_rtrs
= ospf
->new_rtrs
;
1354 ospf
->new_rtrs
= new_rtrs
;
1356 monotime(&start_time
);
1357 if (IS_OSPF_ABR(ospf
))
1358 ospf_abr_task(ospf
);
1359 abr_time
= monotime_since(&start_time
, NULL
);
1362 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1365 if (spf_reason_flags
) {
1366 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1367 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1368 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1369 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1370 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1371 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1372 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1373 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1374 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1375 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1376 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1377 strncat(rbuf
, "ASBR, ",
1378 sizeof(rbuf
) - strlen(rbuf
) - 1);
1379 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1380 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1382 size_t rbuflen
= strlen(rbuf
);
1384 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1389 if (IS_DEBUG_OSPF_EVENT
) {
1390 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1391 zlog_info("\t SPF Time: %ld", spf_time
);
1392 zlog_info("\t InterArea: %ld", ia_time
);
1393 zlog_info("\t Prune: %ld", prune_time
);
1394 zlog_info("\tRouteInstall: %ld", rt_time
);
1395 if (IS_OSPF_ABR(ospf
))
1396 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1398 zlog_info("Reason(s) for SPF: %s", rbuf
);
1401 ospf_clear_spf_reason_flags();
1406 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1407 set timer for SPF calc. */
1408 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1410 unsigned long delay
, elapsed
, ht
;
1412 if (IS_DEBUG_OSPF_EVENT
)
1413 zlog_debug("SPF: calculation timer scheduled");
1415 /* OSPF instance does not exist. */
1419 ospf_spf_set_reason(reason
);
1421 /* SPF calculation timer is already scheduled. */
1422 if (ospf
->t_spf_calc
) {
1423 if (IS_DEBUG_OSPF_EVENT
)
1425 "SPF: calculation timer is already scheduled: %p",
1426 (void *)ospf
->t_spf_calc
);
1430 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1432 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1434 if (ht
> ospf
->spf_max_holdtime
)
1435 ht
= ospf
->spf_max_holdtime
;
1437 /* Get SPF calculation delay time. */
1439 /* Got an event within the hold time of last SPF. We need to
1440 * increase the hold_multiplier, if it's not already at/past
1441 * maximum value, and wasn't already increased..
1443 if (ht
< ospf
->spf_max_holdtime
)
1444 ospf
->spf_hold_multiplier
++;
1446 /* always honour the SPF initial delay */
1447 if ((ht
- elapsed
) < ospf
->spf_delay
)
1448 delay
= ospf
->spf_delay
;
1450 delay
= ht
- elapsed
;
1452 /* Event is past required hold-time of last SPF */
1453 delay
= ospf
->spf_delay
;
1454 ospf
->spf_hold_multiplier
= 1;
1457 if (IS_DEBUG_OSPF_EVENT
)
1458 zlog_debug("SPF: calculation timer delay = %ld", delay
);
1460 zlog_info("SPF: Scheduled in %ld msec", delay
);
1462 ospf
->t_spf_calc
= NULL
;
1463 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,