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 () */
34 #include "ospfd/ospfd.h"
35 #include "ospfd/ospf_interface.h"
36 #include "ospfd/ospf_ism.h"
37 #include "ospfd/ospf_asbr.h"
38 #include "ospfd/ospf_lsa.h"
39 #include "ospfd/ospf_lsdb.h"
40 #include "ospfd/ospf_neighbor.h"
41 #include "ospfd/ospf_nsm.h"
42 #include "ospfd/ospf_spf.h"
43 #include "ospfd/ospf_route.h"
44 #include "ospfd/ospf_ia.h"
45 #include "ospfd/ospf_ase.h"
46 #include "ospfd/ospf_abr.h"
47 #include "ospfd/ospf_dump.h"
48 #include "ospfd/ospf_sr.h"
49 #include "ospfd/ospf_errors.h"
51 /* Variables to ensure a SPF scheduled log message is printed only once */
53 static unsigned int spf_reason_flags
= 0;
55 /* dummy vertex to flag "in spftree" */
56 static const struct vertex vertex_in_spftree
= {};
57 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
58 #define LSA_SPF_NOT_EXPLORED NULL
60 static void ospf_clear_spf_reason_flags(void)
65 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
67 spf_reason_flags
|= 1 << reason
;
70 static void ospf_vertex_free(void *);
71 /* List of allocated vertices, to simplify cleanup of SPF.
72 * Not thread-safe obviously. If it ever needs to be, it'd have to be
73 * dynamically allocated at begin of ospf_spf_calculate
75 static struct list vertex_list
= {.del
= ospf_vertex_free
};
77 /* Heap related functions, for the managment of the candidates, to
78 * be used with pqueue. */
79 static int vertex_cmp(const struct vertex
*v1
, const struct vertex
*v2
)
81 if (v1
->distance
!= v2
->distance
)
82 return v1
->distance
- v2
->distance
;
84 if (v1
->type
!= v2
->type
) {
86 case OSPF_VERTEX_NETWORK
:
88 case OSPF_VERTEX_ROUTER
:
94 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue
, struct vertex
, pqi
, vertex_cmp
)
96 static void lsdb_clean_stat(struct ospf_lsdb
*lsdb
)
98 struct route_table
*table
;
99 struct route_node
*rn
;
100 struct ospf_lsa
*lsa
;
103 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
104 table
= lsdb
->type
[i
].db
;
105 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
106 if ((lsa
= (rn
->info
)) != NULL
)
107 lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
111 static struct vertex_nexthop
*vertex_nexthop_new(void)
113 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
116 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
118 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
121 /* Free the canonical nexthop objects for an area, ie the nexthop objects
122 * attached to the first-hop router vertices, and any intervening network
125 static void ospf_canonical_nexthops_free(struct vertex
*root
)
127 struct listnode
*node
, *nnode
;
128 struct vertex
*child
;
130 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
131 struct listnode
*n2
, *nn2
;
132 struct vertex_parent
*vp
;
134 /* router vertices through an attached network each
135 * have a distinct (canonical / not inherited) nexthop
136 * which must be freed.
138 * A network vertex can only have router vertices as its
139 * children, so only one level of recursion is possible.
141 if (child
->type
== OSPF_VERTEX_NETWORK
)
142 ospf_canonical_nexthops_free(child
);
144 /* Free child nexthops pointing back to this root vertex */
145 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
))
146 if (vp
->parent
== root
&& vp
->nexthop
) {
147 vertex_nexthop_free(vp
->nexthop
);
153 /* TODO: Parent list should be excised, in favour of maintaining only
154 * vertex_nexthop, with refcounts.
156 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
157 struct vertex_nexthop
*hop
)
159 struct vertex_parent
*new;
161 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
164 new->backlink
= backlink
;
169 static void vertex_parent_free(void *p
)
171 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
174 static int vertex_parent_cmp(void *aa
, void *bb
)
176 struct vertex_parent
*a
= aa
, *b
= bb
;
177 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
180 static struct vertex
*ospf_vertex_new(struct ospf_lsa
*lsa
)
184 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
187 new->type
= lsa
->data
->type
;
188 new->id
= lsa
->data
->id
;
189 new->lsa
= lsa
->data
;
190 new->children
= list_new();
191 new->parents
= list_new();
192 new->parents
->del
= vertex_parent_free
;
193 new->parents
->cmp
= vertex_parent_cmp
;
198 listnode_add(&vertex_list
, new);
200 if (IS_DEBUG_OSPF_EVENT
)
201 zlog_debug("%s: Created %s vertex %s", __func__
,
202 new->type
== OSPF_VERTEX_ROUTER
? "Router"
204 inet_ntoa(new->lsa
->id
));
208 static void ospf_vertex_free(void *data
)
210 struct vertex
*v
= data
;
212 if (IS_DEBUG_OSPF_EVENT
)
213 zlog_debug("%s: Free %s vertex %s", __func__
,
214 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
215 inet_ntoa(v
->lsa
->id
));
217 /* There should be no parents potentially holding references to this
219 * Children however may still be there, but presumably referenced by
223 // assert (listcount (v->parents) == 0);
226 list_delete(&v
->children
);
229 list_delete(&v
->parents
);
233 XFREE(MTYPE_OSPF_VERTEX
, v
);
236 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
237 int print_parents
, int print_children
)
239 if (!IS_DEBUG_OSPF_EVENT
)
242 zlog_debug("%s %s vertex %s distance %u flags %u", msg
,
243 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
244 inet_ntoa(v
->lsa
->id
), v
->distance
, (unsigned int)v
->flags
);
247 struct listnode
*node
;
248 struct vertex_parent
*vp
;
250 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
255 "parent %s backlink %d nexthop %s interface %s",
256 inet_ntoa(vp
->parent
->lsa
->id
),
258 inet_ntop(AF_INET
, &vp
->nexthop
->router
,
261 ? IF_NAME(vp
->nexthop
->oi
)
267 if (print_children
) {
268 struct listnode
*cnode
;
271 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
272 ospf_vertex_dump(" child:", cv
, 0, 0);
277 /* Add a vertex to the list of children in each of its parents. */
278 static void ospf_vertex_add_parent(struct vertex
*v
)
280 struct vertex_parent
*vp
;
281 struct listnode
*node
;
283 assert(v
&& v
->parents
);
285 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
286 assert(vp
->parent
&& vp
->parent
->children
);
288 /* No need to add two links from the same parent. */
289 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
290 listnode_add(vp
->parent
->children
, v
);
294 static void ospf_spf_init(struct ospf_area
*area
)
298 /* Create root node. */
299 v
= ospf_vertex_new(area
->router_lsa_self
);
303 /* Reset ABR and ASBR router counts. */
305 area
->asbr_count
= 0;
308 /* return index of link back to V from W, or -1 if no link found */
309 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
311 unsigned int i
, length
;
312 struct router_lsa
*rl
;
313 struct network_lsa
*nl
;
315 /* In case of W is Network LSA. */
316 if (w
->type
== OSPF_NETWORK_LSA
) {
317 if (v
->type
== OSPF_NETWORK_LSA
)
320 nl
= (struct network_lsa
*)w
;
321 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
323 for (i
= 0; i
< length
; i
++)
324 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
329 /* In case of W is Router LSA. */
330 if (w
->type
== OSPF_ROUTER_LSA
) {
331 rl
= (struct router_lsa
*)w
;
333 length
= ntohs(w
->length
);
335 for (i
= 0; i
< ntohs(rl
->links
)
336 && length
>= sizeof(struct router_lsa
);
338 switch (rl
->link
[i
].type
) {
339 case LSA_LINK_TYPE_POINTOPOINT
:
340 case LSA_LINK_TYPE_VIRTUALLINK
:
342 if (v
->type
== OSPF_ROUTER_LSA
343 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
348 case LSA_LINK_TYPE_TRANSIT
:
349 /* Network LSA ID. */
350 if (v
->type
== OSPF_NETWORK_LSA
351 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
356 case LSA_LINK_TYPE_STUB
:
357 /* Stub can't lead anywhere, carry on */
367 /* Find the next link after prev_link from v to w. If prev_link is
368 * NULL, return the first link from v to w. Ignore stub and virtual links;
369 * these link types will never be returned.
371 static struct router_lsa_link
*
372 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
373 struct router_lsa_link
*prev_link
)
377 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
378 struct router_lsa_link
*l
;
380 if (w
->type
== OSPF_VERTEX_ROUTER
)
381 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
383 if (prev_link
== NULL
)
384 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
386 p
= (uint8_t *)prev_link
;
387 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
388 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
391 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
394 l
= (struct router_lsa_link
*)p
;
396 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
397 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
399 if (l
->m
[0].type
!= lsa_type
)
402 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
409 static void ospf_spf_flush_parents(struct vertex
*w
)
411 struct vertex_parent
*vp
;
412 struct listnode
*ln
, *nn
;
414 /* delete the existing nexthops */
415 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
416 list_delete_node(w
->parents
, ln
);
417 vertex_parent_free(vp
);
422 * Consider supplied next-hop for inclusion to the supplied list of
423 * equal-cost next-hops, adjust list as neccessary.
425 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
426 struct vertex_nexthop
*newhop
,
427 unsigned int distance
)
429 struct vertex_parent
*vp
, *wp
;
430 struct listnode
*node
;
432 /* we must have a newhop, and a distance */
433 assert(v
&& w
&& newhop
);
436 /* IFF w has already been assigned a distance, then we shouldn't get
438 * unless callers have determined V(l)->W is shortest / equal-shortest
439 * path (0 is a special case distance (no distance yet assigned)).
442 assert(distance
<= w
->distance
);
444 w
->distance
= distance
;
446 if (IS_DEBUG_OSPF_EVENT
) {
447 char buf
[2][INET_ADDRSTRLEN
];
449 "%s: Adding %s as parent of %s", __func__
,
450 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
451 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
455 /* Adding parent for a new, better path: flush existing parents from W.
457 if (distance
< w
->distance
) {
458 if (IS_DEBUG_OSPF_EVENT
)
460 "%s: distance %d better than %d, flushing existing parents",
461 __func__
, distance
, w
->distance
);
462 ospf_spf_flush_parents(w
);
463 w
->distance
= distance
;
466 /* new parent is <= existing parents, add it to parent list (if nexthop
467 * not on parent list)
469 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
470 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
471 if (IS_DEBUG_OSPF_EVENT
)
473 "%s: ... nexthop already on parent list, skipping add",
479 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
480 listnode_add_sort(w
->parents
, vp
);
485 /* 16.1.1. Calculate nexthop from root through V (parent) to
486 * vertex W (destination), with given distance from root->W.
488 * The link must be supplied if V is the root vertex. In all other cases
491 * Note that this function may fail, hence the state of the destination
492 * vertex, W, should /not/ be modified in a dependent manner until
493 * this function returns. This function will update the W vertex with the
494 * provided distance as appropriate.
496 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
497 struct vertex
*v
, struct vertex
*w
,
498 struct router_lsa_link
*l
,
499 unsigned int distance
, int lsa_pos
)
501 struct listnode
*node
, *nnode
;
502 struct vertex_nexthop
*nh
;
503 struct vertex_parent
*vp
;
504 struct ospf_interface
*oi
= NULL
;
505 unsigned int added
= 0;
509 if (IS_DEBUG_OSPF_EVENT
) {
510 zlog_debug("ospf_nexthop_calculation(): Start");
511 ospf_vertex_dump("V (parent):", v
, 1, 1);
512 ospf_vertex_dump("W (dest) :", w
, 1, 1);
513 zlog_debug("V->W distance: %d", distance
);
516 if (v
== area
->spf
) {
517 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
519 root (the calculating router itself). This means that the
520 destination is either a directly connected network or
522 connected router. The outgoing interface in this case is
524 the OSPF interface connecting to the destination
528 /* we *must* be supplied with the link data */
530 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
533 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
535 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
536 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
541 if (IS_DEBUG_OSPF_EVENT
) {
543 "%s: considering link:%s "
544 "type:%d link_id:%s link_data:%s",
545 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
546 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
547 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
551 if (w
->type
== OSPF_VERTEX_ROUTER
) {
552 /* l is a link from v to w
553 * l2 will be link from w to v
555 struct router_lsa_link
*l2
= NULL
;
557 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
558 struct in_addr nexthop
= {.s_addr
= 0};
560 /* If the destination is a router which connects
562 the calculating router via a
564 network, the destination's next hop IP
566 can be determined by examining the
568 router-LSA: each link pointing back to the
569 calculating router and having a Link Data
571 belonging to the Point-to-MultiPoint network
572 provides an IP address of the next hop
575 At this point l is a link from V to W, and V
577 root ("us"). If it is a point-to-multipoint
579 then look through the links in the opposite
581 If any of them have an address that lands
583 subnet declared by the PtMP link, then that
585 is a constituent of the PtMP link, and its
587 a nexthop address for V.
589 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
590 /* Having nexthop = 0 is tempting, but
592 It breaks AS-External routes with a
595 ospf_ase_complete_direct_routes()
597 assume we've reached the last hop and
599 forwarding address as nexthop.
600 Also, users may configure
601 multi-access links in p2p mode,
602 so we need the IP to ARP the nexthop.
604 struct ospf_neighbor
*nbr_w
;
606 nbr_w
= ospf_nbr_lookup_by_routerid(
607 oi
->nbrs
, &l
->link_id
);
610 nexthop
= nbr_w
->src
;
613 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
614 struct prefix_ipv4 la
;
617 la
.prefixlen
= oi
->address
->prefixlen
;
619 /* V links to W on PtMP interface
620 - find the interface address on W */
621 while ((l2
= ospf_get_next_link(w
, v
,
623 la
.prefix
= l2
->link_data
;
625 if (prefix_cmp((struct prefix
630 /* link_data is on our PtMP
633 nexthop
= l2
->link_data
;
639 /* found all necessary info to build
641 nh
= vertex_nexthop_new();
643 nh
->router
= nexthop
;
644 ospf_spf_add_parent(v
, w
, nh
, distance
);
648 "%s: could not determine nexthop for link %s",
649 __func__
, oi
->ifp
->name
);
650 } /* end point-to-point link from V to W */
651 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
652 struct ospf_vl_data
*vl_data
;
654 /* VLink implementation limitations:
655 * a) vl_data can only reference one nexthop, so
657 * to backbone through VLinks. Though
659 * summaries may be considered, and those can
661 * b) We can only use /one/ VLink, even if
663 * exist this router through multiple
666 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
670 && CHECK_FLAG(vl_data
->flags
,
671 OSPF_VL_FLAG_APPROVED
)) {
672 nh
= vertex_nexthop_new();
673 nh
->oi
= vl_data
->nexthop
.oi
;
674 nh
->router
= vl_data
->nexthop
.router
;
675 ospf_spf_add_parent(v
, w
, nh
, distance
);
679 "ospf_nexthop_calculation(): "
680 "vl_data for VL link not found");
681 } /* end virtual-link from V to W */
683 } /* end W is a Router vertex */
685 assert(w
->type
== OSPF_VERTEX_NETWORK
);
687 nh
= vertex_nexthop_new();
689 nh
->router
.s_addr
= 0; /* Nexthop not required */
690 ospf_spf_add_parent(v
, w
, nh
, distance
);
693 } /* end V is the root */
694 /* Check if W's parent is a network connected to root. */
695 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
696 /* See if any of V's parents are the root. */
697 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
698 if (vp
->parent
== area
->spf
) /* connects to root? */
700 /* 16.1.1 para 5. ...the parent vertex is a
702 * directly connects the calculating router to
704 * router. The list of next hops is then
706 * examining the destination's router-LSA...
709 assert(w
->type
== OSPF_VERTEX_ROUTER
);
710 while ((l
= ospf_get_next_link(w
, v
, l
))) {
711 /* ...For each link in the router-LSA
712 * that points back to the
713 * parent network, the link's Link Data
714 * field provides the IP
715 * address of a next hop router. The
716 * outgoing interface to
717 * use can then be derived from the next
719 * it can be inherited from the parent
722 nh
= vertex_nexthop_new();
723 nh
->oi
= vp
->nexthop
->oi
;
724 nh
->router
= l
->link_data
;
726 ospf_spf_add_parent(v
, w
, nh
, distance
);
728 /* Note lack of return is deliberate. See next
732 /* NB: This code is non-trivial.
734 * E.g. it is not enough to know that V connects to the root. It
736 * also important that the while above, looping through all
738 * W->V found at least one link, so that we know there is
739 * bi-directional connectivity between V and W (which need not
741 * case, e.g. when OSPF has not yet converged fully).
743 * we /always/ return here, without having checked that
745 * actually resulted in a valid nexthop being created, then we
747 * prevent SPF from finding/using higher cost paths.
749 * It is important, if root->V->W has not been added, that we
751 * through to the intervening-router nexthop code below. So as
753 * ensure other paths to V may be used. This avoids unnecessary
754 * blackholes while OSPF is convergening.
756 * I.e. we may have arrived at this function, examining V -> W,
758 * workable paths other than root -> V, and it's important to
760 * getting "confused" by non-working root->V->W path - it's
762 * to *not* lose the working non-root paths, just because of a
763 * non-viable root->V->W.
765 * See also bug #330 (required reading!), and:
767 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
773 /* 16.1.1 para 4. If there is at least one intervening router in the
774 * current shortest path between the destination and the root, the
775 * destination simply inherits the set of next hops from the
778 if (IS_DEBUG_OSPF_EVENT
)
779 zlog_debug("%s: Intervening routers, adding parent(s)",
782 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
784 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
790 /* RFC2328 Section 16.1 (2).
791 * v is on the SPF tree. Examine the links in v's LSA. Update the list
792 * of candidates with any vertices not already on the list. If a lower-cost
793 * path is found to a vertex already on the candidate list, store the new cost.
795 static void ospf_spf_next(struct vertex
*v
, struct ospf
*ospf
,
796 struct ospf_area
*area
,
797 struct vertex_pqueue_head
*candidate
)
799 struct ospf_lsa
*w_lsa
= NULL
;
802 struct router_lsa_link
*l
= NULL
;
804 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
806 /* If this is a router-LSA, and bit V of the router-LSA (see Section
807 A.4.2:RFC2328) is set, set Area A's TransitCapability to true. */
808 if (v
->type
== OSPF_VERTEX_ROUTER
) {
809 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
810 area
->transit
= OSPF_TRANSIT_TRUE
;
813 if (IS_DEBUG_OSPF_EVENT
)
814 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
815 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
816 inet_ntoa(v
->lsa
->id
));
818 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
819 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
823 unsigned int distance
;
825 /* In case of V is Router-LSA. */
826 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
827 l
= (struct router_lsa_link
*)p
;
829 lsa_pos
= lsa_pos_next
; /* LSA link position */
831 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
832 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
834 /* (a) If this is a link to a stub network, examine the
836 link in V's LSA. Links to stub networks will be
837 considered in the second stage of the shortest path
839 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
842 /* (b) Otherwise, W is a transit vertex (router or
844 network). Look up the vertex W's LSA (router-LSA or
845 network-LSA) in Area A's link state database. */
847 case LSA_LINK_TYPE_POINTOPOINT
:
848 case LSA_LINK_TYPE_VIRTUALLINK
:
849 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
850 if (IS_DEBUG_OSPF_EVENT
)
852 "looking up LSA through VL: %s",
853 inet_ntoa(l
->link_id
));
856 w_lsa
= ospf_lsa_lookup(ospf
, area
,
858 l
->link_id
, l
->link_id
);
860 if (IS_DEBUG_OSPF_EVENT
)
862 "found Router LSA %s",
863 inet_ntoa(l
->link_id
));
866 case LSA_LINK_TYPE_TRANSIT
:
867 if (IS_DEBUG_OSPF_EVENT
)
869 "Looking up Network LSA, ID: %s",
870 inet_ntoa(l
->link_id
));
871 w_lsa
= ospf_lsa_lookup_by_id(
872 area
, OSPF_NETWORK_LSA
, l
->link_id
);
874 if (IS_DEBUG_OSPF_EVENT
)
875 zlog_debug("found the LSA");
878 flog_warn(EC_OSPF_LSA
,
879 "Invalid LSA link type %d", type
);
884 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
886 /* In case of V is Network-LSA. */
887 r
= (struct in_addr
*)p
;
888 p
+= sizeof(struct in_addr
);
890 /* Lookup the vertex W's LSA. */
891 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
894 if (IS_DEBUG_OSPF_EVENT
)
895 zlog_debug("found Router LSA %s",
896 inet_ntoa(w_lsa
->data
->id
));
900 distance
= v
->distance
;
903 /* (b cont.) If the LSA does not exist, or its LS age is equal
904 to MaxAge, or it does not have a link back to vertex V,
905 examine the next link in V's LSA.[23] */
907 if (IS_DEBUG_OSPF_EVENT
)
908 zlog_debug("No LSA found");
912 if (IS_LSA_MAXAGE(w_lsa
)) {
913 if (IS_DEBUG_OSPF_EVENT
)
914 zlog_debug("LSA is MaxAge");
918 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
919 if (IS_DEBUG_OSPF_EVENT
)
920 zlog_debug("The LSA doesn't have a link back");
924 /* (c) If vertex W is already on the shortest-path tree, examine
925 the next link in the LSA. */
926 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
927 if (IS_DEBUG_OSPF_EVENT
)
928 zlog_debug("The LSA is already in SPF");
932 /* (d) Calculate the link state cost D of the resulting path
933 from the root to vertex W. D is equal to the sum of the link
934 state cost of the (already calculated) shortest path to
935 vertex V and the advertised cost of the link between vertices
938 /* calculate link cost D -- moved above */
940 /* Is there already vertex W in candidate list? */
941 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
942 /* prepare vertex W. */
943 w
= ospf_vertex_new(w_lsa
);
945 /* Calculate nexthop to W. */
946 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
948 vertex_pqueue_add(candidate
, w
);
949 else if (IS_DEBUG_OSPF_EVENT
)
950 zlog_debug("Nexthop Calc failed");
951 } else if (w_lsa
->stat
!= LSA_SPF_IN_SPFTREE
) {
953 /* if D is greater than. */
954 if (w
->distance
< distance
) {
958 else if (w
->distance
== distance
) {
959 /* Found an equal-cost path to W.
960 * Calculate nexthop of to W from V. */
961 ospf_nexthop_calculation(area
, v
, w
, l
,
966 /* Found a lower-cost path to W.
967 * nexthop_calculation is conditional, if it
969 * valid nexthop it will call spf_add_parents,
971 * will flush the old parents
973 vertex_pqueue_del(candidate
, w
);
974 ospf_nexthop_calculation(area
, v
, w
, l
,
976 vertex_pqueue_add(candidate
, w
);
978 } /* end W is already on the candidate list */
979 } /* end loop over the links in V's LSA */
982 static void ospf_spf_dump(struct vertex
*v
, int i
)
984 struct listnode
*cnode
;
985 struct listnode
*nnode
;
986 struct vertex_parent
*parent
;
988 if (v
->type
== OSPF_VERTEX_ROUTER
) {
989 if (IS_DEBUG_OSPF_EVENT
)
990 zlog_debug("SPF Result: %d [R] %s", i
,
991 inet_ntoa(v
->lsa
->id
));
993 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
994 if (IS_DEBUG_OSPF_EVENT
)
995 zlog_debug("SPF Result: %d [N] %s/%d", i
,
996 inet_ntoa(v
->lsa
->id
),
997 ip_masklen(lsa
->mask
));
1000 if (IS_DEBUG_OSPF_EVENT
)
1001 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1002 zlog_debug(" nexthop %p %s %s", (void *)parent
->nexthop
,
1003 inet_ntoa(parent
->nexthop
->router
),
1005 ? IF_NAME(parent
->nexthop
->oi
)
1011 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1012 ospf_spf_dump(v
, i
);
1015 /* Second stage of SPF calculation. */
1016 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1017 struct route_table
*rt
, int parent_is_root
)
1019 struct listnode
*cnode
, *cnnode
;
1020 struct vertex
*child
;
1022 if (IS_DEBUG_OSPF_EVENT
)
1023 zlog_debug("ospf_process_stub():processing stubs for area %s",
1024 inet_ntoa(area
->area_id
));
1025 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1028 struct router_lsa_link
*l
;
1029 struct router_lsa
*rlsa
;
1032 if (IS_DEBUG_OSPF_EVENT
)
1034 "ospf_process_stubs():processing router LSA, id: %s",
1035 inet_ntoa(v
->lsa
->id
));
1036 rlsa
= (struct router_lsa
*)v
->lsa
;
1039 if (IS_DEBUG_OSPF_EVENT
)
1041 "ospf_process_stubs(): we have %d links to process",
1042 ntohs(rlsa
->links
));
1043 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1044 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1047 l
= (struct router_lsa_link
*)p
;
1049 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1050 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1052 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1053 ospf_intra_add_stub(rt
, l
, v
, area
,
1054 parent_is_root
, lsa_pos
);
1059 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1062 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1063 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1066 /* the first level of routers connected to the root
1067 * should have 'parent_is_root' set, including those
1068 * connected via a network vertex.
1072 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1075 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1077 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1081 void ospf_rtrs_free(struct route_table
*rtrs
)
1083 struct route_node
*rn
;
1084 struct list
*or_list
;
1085 struct ospf_route
* or ;
1086 struct listnode
*node
, *nnode
;
1088 if (IS_DEBUG_OSPF_EVENT
)
1089 zlog_debug("Route: Router Routing Table free");
1091 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1092 if ((or_list
= rn
->info
) != NULL
) {
1093 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1094 ospf_route_free(or);
1096 list_delete(&or_list
);
1098 /* Unlock the node. */
1100 route_unlock_node(rn
);
1102 route_table_finish(rtrs
);
1107 ospf_rtrs_print (struct route_table
*rtrs
)
1109 struct route_node
*rn
;
1110 struct list
*or_list
;
1111 struct listnode
*ln
;
1112 struct listnode
*pnode
;
1113 struct ospf_route
*or;
1114 struct ospf_path
*path
;
1118 if (IS_DEBUG_OSPF_EVENT
)
1119 zlog_debug ("ospf_rtrs_print() start");
1121 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1122 if ((or_list
= rn
->info
) != NULL
)
1123 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1125 switch (or->path_type
)
1127 case OSPF_PATH_INTRA_AREA
:
1128 if (IS_DEBUG_OSPF_EVENT
)
1129 zlog_debug ("%s [%d] area: %s",
1130 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1131 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1134 case OSPF_PATH_INTER_AREA
:
1135 if (IS_DEBUG_OSPF_EVENT
)
1136 zlog_debug ("%s IA [%d] area: %s",
1137 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1138 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1145 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1147 if (path
->nexthop
.s_addr
== 0)
1149 if (IS_DEBUG_OSPF_EVENT
)
1150 zlog_debug (" directly attached to %s\r",
1151 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1155 if (IS_DEBUG_OSPF_EVENT
)
1156 zlog_debug (" via %s, %s\r",
1157 inet_ntoa (path
->nexthop
),
1158 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1163 zlog_debug ("ospf_rtrs_print() end");
1167 /* Calculating the shortest-path tree for an area. */
1168 static void ospf_spf_calculate(struct ospf
*ospf
, struct ospf_area
*area
,
1169 struct route_table
*new_table
,
1170 struct route_table
*new_rtrs
)
1172 struct vertex_pqueue_head candidate
;
1175 if (IS_DEBUG_OSPF_EVENT
) {
1176 zlog_debug("ospf_spf_calculate: Start");
1177 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1178 inet_ntoa(area
->area_id
));
1181 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1182 return this area's calculation. */
1183 if (!area
->router_lsa_self
) {
1184 if (IS_DEBUG_OSPF_EVENT
)
1186 "ospf_spf_calculate: "
1187 "Skip area %s's calculation due to empty router_lsa_self",
1188 inet_ntoa(area
->area_id
));
1192 /* RFC2328 16.1. (1). */
1193 /* Initialize the algorithm's data structures. */
1195 /* This function scans all the LSA database and set the stat field to
1196 * LSA_SPF_NOT_EXPLORED. */
1197 lsdb_clean_stat(area
->lsdb
);
1198 /* Create a new heap for the candidates. */
1199 vertex_pqueue_init(&candidate
);
1201 /* Initialize the shortest-path tree to only the root (which is the
1202 router doing the calculation). */
1203 ospf_spf_init(area
);
1205 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1208 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1210 /* Set Area A's TransitCapability to false. */
1211 area
->transit
= OSPF_TRANSIT_FALSE
;
1212 area
->shortcut_capability
= 1;
1215 /* RFC2328 16.1. (2). */
1216 ospf_spf_next(v
, ospf
, area
, &candidate
);
1218 /* RFC2328 16.1. (3). */
1219 /* If at this step the candidate list is empty, the shortest-
1220 path tree (of transit vertices) has been completely built and
1221 this stage of the procedure terminates. */
1222 /* Otherwise, choose the vertex belonging to the candidate list
1223 that is closest to the root, and add it to the shortest-path
1224 tree (removing it from the candidate list in the
1226 /* Extract from the candidates the node with the lower key. */
1227 v
= vertex_pqueue_pop(&candidate
);
1230 /* Update stat field in vertex. */
1231 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1233 ospf_vertex_add_parent(v
);
1235 /* RFC2328 16.1. (4). */
1236 if (v
->type
== OSPF_VERTEX_ROUTER
)
1237 ospf_intra_add_router(new_rtrs
, v
, area
);
1239 ospf_intra_add_transit(new_table
, v
, area
);
1241 /* RFC2328 16.1. (5). */
1242 /* Iterate the algorithm by returning to Step 2. */
1244 } /* end loop until no more candidate vertices */
1246 if (IS_DEBUG_OSPF_EVENT
) {
1247 ospf_spf_dump(area
->spf
, 0);
1248 ospf_route_table_dump(new_table
);
1251 /* Second stage of SPF calculation procedure's */
1252 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1254 /* Free candidate queue. */
1255 //vertex_pqueue_fini(&candidate);
1257 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1258 /* Free nexthop information, canonical versions of which are attached
1259 * the first level of router vertices attached to the root vertex, see
1260 * ospf_nexthop_calculation.
1262 ospf_canonical_nexthops_free(area
->spf
);
1264 /* Increment SPF Calculation Counter. */
1265 area
->spf_calculation
++;
1267 monotime(&area
->ospf
->ts_spf
);
1268 area
->ts_spf
= area
->ospf
->ts_spf
;
1270 if (IS_DEBUG_OSPF_EVENT
)
1271 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1272 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1274 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1277 list_delete_all_node(&vertex_list
);
1280 /* Timer for SPF calculation. */
1281 static int ospf_spf_calculate_timer(struct thread
*thread
)
1283 struct ospf
*ospf
= THREAD_ARG(thread
);
1284 struct route_table
*new_table
, *new_rtrs
;
1285 struct ospf_area
*area
;
1286 struct listnode
*node
, *nnode
;
1287 struct timeval start_time
, spf_start_time
;
1288 int areas_processed
= 0;
1289 unsigned long ia_time
, prune_time
, rt_time
;
1290 unsigned long abr_time
, total_spf_time
, spf_time
;
1291 char rbuf
[32]; /* reason_buf */
1293 if (IS_DEBUG_OSPF_EVENT
)
1294 zlog_debug("SPF: Timer (SPF calculation expire)");
1296 ospf
->t_spf_calc
= NULL
;
1298 monotime(&spf_start_time
);
1299 /* Allocate new table tree. */
1300 new_table
= route_table_init();
1301 new_rtrs
= route_table_init();
1303 ospf_vl_unapprove(ospf
);
1305 /* Calculate SPF for each area. */
1306 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1307 /* Do backbone last, so as to first discover intra-area paths
1308 * for any back-bone virtual-links
1310 if (ospf
->backbone
&& ospf
->backbone
== area
)
1313 ospf_spf_calculate(ospf
, area
, new_table
, new_rtrs
);
1317 /* SPF for backbone, if required */
1318 if (ospf
->backbone
) {
1319 ospf_spf_calculate(ospf
, ospf
->backbone
, new_table
, new_rtrs
);
1323 spf_time
= monotime_since(&spf_start_time
, NULL
);
1325 ospf_vl_shut_unapproved(ospf
);
1327 monotime(&start_time
);
1328 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1329 ia_time
= monotime_since(&start_time
, NULL
);
1331 monotime(&start_time
);
1332 ospf_prune_unreachable_networks(new_table
);
1333 ospf_prune_unreachable_routers(new_rtrs
);
1334 prune_time
= monotime_since(&start_time
, NULL
);
1336 /* AS-external-LSA calculation should not be performed here. */
1338 /* If new Router Route is installed,
1339 then schedule re-calculate External routes. */
1341 ospf_ase_calculate_schedule(ospf
);
1343 ospf_ase_calculate_timer_add(ospf
);
1345 if (IS_DEBUG_OSPF_EVENT
)
1347 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1348 __PRETTY_FUNCTION__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1349 ospf
->vrf_id
, new_table
->count
);
1350 /* Update routing table. */
1351 monotime(&start_time
);
1352 ospf_route_install(ospf
, new_table
);
1353 rt_time
= monotime_since(&start_time
, NULL
);
1355 /* Update ABR/ASBR routing table */
1356 if (ospf
->old_rtrs
) {
1357 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1359 /* ospf_route_delete (ospf->old_rtrs); */
1360 ospf_rtrs_free(ospf
->old_rtrs
);
1363 ospf
->old_rtrs
= ospf
->new_rtrs
;
1364 ospf
->new_rtrs
= new_rtrs
;
1366 monotime(&start_time
);
1367 if (IS_OSPF_ABR(ospf
))
1368 ospf_abr_task(ospf
);
1369 abr_time
= monotime_since(&start_time
, NULL
);
1371 /* Schedule Segment Routing update */
1372 ospf_sr_update_timer_add(ospf
);
1375 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1378 if (spf_reason_flags
) {
1379 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1380 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1381 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1382 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1383 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1384 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1385 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1386 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1387 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1388 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1389 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1390 strncat(rbuf
, "ASBR, ",
1391 sizeof(rbuf
) - strlen(rbuf
) - 1);
1392 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1393 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1395 size_t rbuflen
= strlen(rbuf
);
1397 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1402 if (IS_DEBUG_OSPF_EVENT
) {
1403 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1404 zlog_info("\t SPF Time: %ld", spf_time
);
1405 zlog_info("\t InterArea: %ld", ia_time
);
1406 zlog_info("\t Prune: %ld", prune_time
);
1407 zlog_info("\tRouteInstall: %ld", rt_time
);
1408 if (IS_OSPF_ABR(ospf
))
1409 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1411 zlog_info("Reason(s) for SPF: %s", rbuf
);
1414 ospf_clear_spf_reason_flags();
1419 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1420 set timer for SPF calc. */
1421 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1423 unsigned long delay
, elapsed
, ht
;
1425 if (IS_DEBUG_OSPF_EVENT
)
1426 zlog_debug("SPF: calculation timer scheduled");
1428 /* OSPF instance does not exist. */
1432 ospf_spf_set_reason(reason
);
1434 /* SPF calculation timer is already scheduled. */
1435 if (ospf
->t_spf_calc
) {
1436 if (IS_DEBUG_OSPF_EVENT
)
1438 "SPF: calculation timer is already scheduled: %p",
1439 (void *)ospf
->t_spf_calc
);
1443 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1445 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1447 if (ht
> ospf
->spf_max_holdtime
)
1448 ht
= ospf
->spf_max_holdtime
;
1450 /* Get SPF calculation delay time. */
1452 /* Got an event within the hold time of last SPF. We need to
1453 * increase the hold_multiplier, if it's not already at/past
1454 * maximum value, and wasn't already increased..
1456 if (ht
< ospf
->spf_max_holdtime
)
1457 ospf
->spf_hold_multiplier
++;
1459 /* always honour the SPF initial delay */
1460 if ((ht
- elapsed
) < ospf
->spf_delay
)
1461 delay
= ospf
->spf_delay
;
1463 delay
= ht
- elapsed
;
1465 /* Event is past required hold-time of last SPF */
1466 delay
= ospf
->spf_delay
;
1467 ospf
->spf_hold_multiplier
= 1;
1470 if (IS_DEBUG_OSPF_EVENT
)
1471 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
1473 ospf
->t_spf_calc
= NULL
;
1474 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,