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"
49 #include "ospfd/ospf_sr.h"
50 #include "ospfd/ospf_errors.h"
52 /* Variables to ensure a SPF scheduled log message is printed only once */
54 static unsigned int spf_reason_flags
= 0;
56 static void ospf_clear_spf_reason_flags(void)
61 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
63 spf_reason_flags
|= 1 << reason
;
66 static void ospf_vertex_free(void *);
67 /* List of allocated vertices, to simplify cleanup of SPF.
68 * Not thread-safe obviously. If it ever needs to be, it'd have to be
69 * dynamically allocated at begin of ospf_spf_calculate
71 static struct list vertex_list
= {.del
= ospf_vertex_free
};
73 /* Heap related functions, for the managment of the candidates, to
74 * be used with pqueue. */
75 static int cmp(void *node1
, void *node2
)
77 struct vertex
*v1
= (struct vertex
*)node1
;
78 struct vertex
*v2
= (struct vertex
*)node2
;
79 if (v1
!= NULL
&& v2
!= NULL
) {
80 /* network vertices must be chosen before router vertices of
82 * cost in order to find all shortest paths
84 if (((v1
->distance
- v2
->distance
) == 0)
85 && (v1
->type
!= v2
->type
)) {
87 case OSPF_VERTEX_NETWORK
:
89 case OSPF_VERTEX_ROUTER
:
93 return (v1
->distance
- v2
->distance
);
98 static void update_stat(void *node
, int position
)
100 struct vertex
*v
= node
;
102 /* Set the status of the vertex, when its position changes. */
103 *(v
->stat
) = position
;
106 static struct vertex_nexthop
*vertex_nexthop_new(void)
108 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
111 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
113 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
116 /* Free the canonical nexthop objects for an area, ie the nexthop objects
117 * attached to the first-hop router vertices, and any intervening network
120 static void ospf_canonical_nexthops_free(struct vertex
*root
)
122 struct listnode
*node
, *nnode
;
123 struct vertex
*child
;
125 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
126 struct listnode
*n2
, *nn2
;
127 struct vertex_parent
*vp
;
129 /* router vertices through an attached network each
130 * have a distinct (canonical / not inherited) nexthop
131 * which must be freed.
133 * A network vertex can only have router vertices as its
134 * children, so only one level of recursion is possible.
136 if (child
->type
== OSPF_VERTEX_NETWORK
)
137 ospf_canonical_nexthops_free(child
);
139 /* Free child nexthops pointing back to this root vertex */
140 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
))
141 if (vp
->parent
== root
&& vp
->nexthop
) {
142 vertex_nexthop_free(vp
->nexthop
);
148 /* TODO: Parent list should be excised, in favour of maintaining only
149 * vertex_nexthop, with refcounts.
151 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
152 struct vertex_nexthop
*hop
)
154 struct vertex_parent
*new;
156 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
159 new->backlink
= backlink
;
164 static void vertex_parent_free(void *p
)
166 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
169 static int vertex_parent_cmp(void *aa
, void *bb
)
171 struct vertex_parent
*a
= aa
, *b
= bb
;
172 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
175 static struct vertex
*ospf_vertex_new(struct ospf_lsa
*lsa
)
179 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
182 new->stat
= &(lsa
->stat
);
183 new->type
= lsa
->data
->type
;
184 new->id
= lsa
->data
->id
;
185 new->lsa
= lsa
->data
;
186 new->children
= list_new();
187 new->parents
= list_new();
188 new->parents
->del
= vertex_parent_free
;
189 new->parents
->cmp
= vertex_parent_cmp
;
191 listnode_add(&vertex_list
, new);
193 if (IS_DEBUG_OSPF_EVENT
)
194 zlog_debug("%s: Created %s vertex %s", __func__
,
195 new->type
== OSPF_VERTEX_ROUTER
? "Router"
197 inet_ntoa(new->lsa
->id
));
201 static void ospf_vertex_free(void *data
)
203 struct vertex
*v
= data
;
205 if (IS_DEBUG_OSPF_EVENT
)
206 zlog_debug("%s: Free %s vertex %s", __func__
,
207 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
208 inet_ntoa(v
->lsa
->id
));
210 /* There should be no parents potentially holding references to this
212 * Children however may still be there, but presumably referenced by
216 // assert (listcount (v->parents) == 0);
219 list_delete(&v
->children
);
222 list_delete(&v
->parents
);
226 XFREE(MTYPE_OSPF_VERTEX
, v
);
229 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
230 int print_parents
, int print_children
)
232 if (!IS_DEBUG_OSPF_EVENT
)
235 zlog_debug("%s %s vertex %s distance %u flags %u", msg
,
236 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
237 inet_ntoa(v
->lsa
->id
), v
->distance
, (unsigned int)v
->flags
);
240 struct listnode
*node
;
241 struct vertex_parent
*vp
;
243 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
248 "parent %s backlink %d nexthop %s interface %s",
249 inet_ntoa(vp
->parent
->lsa
->id
),
251 inet_ntop(AF_INET
, &vp
->nexthop
->router
,
254 ? IF_NAME(vp
->nexthop
->oi
)
260 if (print_children
) {
261 struct listnode
*cnode
;
264 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
265 ospf_vertex_dump(" child:", cv
, 0, 0);
270 /* Add a vertex to the list of children in each of its parents. */
271 static void ospf_vertex_add_parent(struct vertex
*v
)
273 struct vertex_parent
*vp
;
274 struct listnode
*node
;
276 assert(v
&& v
->parents
);
278 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
279 assert(vp
->parent
&& vp
->parent
->children
);
281 /* No need to add two links from the same parent. */
282 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
283 listnode_add(vp
->parent
->children
, v
);
287 static void ospf_spf_init(struct ospf_area
*area
)
291 /* Create root node. */
292 v
= ospf_vertex_new(area
->router_lsa_self
);
296 /* Reset ABR and ASBR router counts. */
298 area
->asbr_count
= 0;
301 /* return index of link back to V from W, or -1 if no link found */
302 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
304 unsigned int i
, length
;
305 struct router_lsa
*rl
;
306 struct network_lsa
*nl
;
308 /* In case of W is Network LSA. */
309 if (w
->type
== OSPF_NETWORK_LSA
) {
310 if (v
->type
== OSPF_NETWORK_LSA
)
313 nl
= (struct network_lsa
*)w
;
314 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
316 for (i
= 0; i
< length
; i
++)
317 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
322 /* In case of W is Router LSA. */
323 if (w
->type
== OSPF_ROUTER_LSA
) {
324 rl
= (struct router_lsa
*)w
;
326 length
= ntohs(w
->length
);
328 for (i
= 0; i
< ntohs(rl
->links
)
329 && length
>= sizeof(struct router_lsa
);
331 switch (rl
->link
[i
].type
) {
332 case LSA_LINK_TYPE_POINTOPOINT
:
333 case LSA_LINK_TYPE_VIRTUALLINK
:
335 if (v
->type
== OSPF_ROUTER_LSA
336 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
341 case LSA_LINK_TYPE_TRANSIT
:
342 /* Network LSA ID. */
343 if (v
->type
== OSPF_NETWORK_LSA
344 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
349 case LSA_LINK_TYPE_STUB
:
350 /* Stub can't lead anywhere, carry on */
360 /* Find the next link after prev_link from v to w. If prev_link is
361 * NULL, return the first link from v to w. Ignore stub and virtual links;
362 * these link types will never be returned.
364 static struct router_lsa_link
*
365 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
366 struct router_lsa_link
*prev_link
)
370 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
371 struct router_lsa_link
*l
;
373 if (w
->type
== OSPF_VERTEX_ROUTER
)
374 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
376 if (prev_link
== NULL
)
377 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
379 p
= (uint8_t *)prev_link
;
380 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
381 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
384 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
387 l
= (struct router_lsa_link
*)p
;
389 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
390 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
392 if (l
->m
[0].type
!= lsa_type
)
395 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
402 static void ospf_spf_flush_parents(struct vertex
*w
)
404 struct vertex_parent
*vp
;
405 struct listnode
*ln
, *nn
;
407 /* delete the existing nexthops */
408 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
409 list_delete_node(w
->parents
, ln
);
410 vertex_parent_free(vp
);
415 * Consider supplied next-hop for inclusion to the supplied list of
416 * equal-cost next-hops, adjust list as neccessary.
418 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
419 struct vertex_nexthop
*newhop
,
420 unsigned int distance
)
422 struct vertex_parent
*vp
, *wp
;
423 struct listnode
*node
;
425 /* we must have a newhop, and a distance */
426 assert(v
&& w
&& newhop
);
429 /* IFF w has already been assigned a distance, then we shouldn't get
431 * unless callers have determined V(l)->W is shortest / equal-shortest
432 * path (0 is a special case distance (no distance yet assigned)).
435 assert(distance
<= w
->distance
);
437 w
->distance
= distance
;
439 if (IS_DEBUG_OSPF_EVENT
) {
440 char buf
[2][INET_ADDRSTRLEN
];
442 "%s: Adding %s as parent of %s", __func__
,
443 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
444 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
448 /* Adding parent for a new, better path: flush existing parents from W.
450 if (distance
< w
->distance
) {
451 if (IS_DEBUG_OSPF_EVENT
)
453 "%s: distance %d better than %d, flushing existing parents",
454 __func__
, distance
, w
->distance
);
455 ospf_spf_flush_parents(w
);
456 w
->distance
= distance
;
459 /* new parent is <= existing parents, add it to parent list (if nexthop
460 * not on parent list)
462 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
463 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
464 if (IS_DEBUG_OSPF_EVENT
)
466 "%s: ... nexthop already on parent list, skipping add",
472 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
473 listnode_add_sort(w
->parents
, vp
);
478 /* 16.1.1. Calculate nexthop from root through V (parent) to
479 * vertex W (destination), with given distance from root->W.
481 * The link must be supplied if V is the root vertex. In all other cases
484 * Note that this function may fail, hence the state of the destination
485 * vertex, W, should /not/ be modified in a dependent manner until
486 * this function returns. This function will update the W vertex with the
487 * provided distance as appropriate.
489 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
490 struct vertex
*v
, struct vertex
*w
,
491 struct router_lsa_link
*l
,
492 unsigned int distance
, int lsa_pos
)
494 struct listnode
*node
, *nnode
;
495 struct vertex_nexthop
*nh
;
496 struct vertex_parent
*vp
;
497 struct ospf_interface
*oi
= NULL
;
498 unsigned int added
= 0;
502 if (IS_DEBUG_OSPF_EVENT
) {
503 zlog_debug("ospf_nexthop_calculation(): Start");
504 ospf_vertex_dump("V (parent):", v
, 1, 1);
505 ospf_vertex_dump("W (dest) :", w
, 1, 1);
506 zlog_debug("V->W distance: %d", distance
);
509 if (v
== area
->spf
) {
510 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
512 root (the calculating router itself). This means that the
513 destination is either a directly connected network or
515 connected router. The outgoing interface in this case is
517 the OSPF interface connecting to the destination
521 /* we *must* be supplied with the link data */
523 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
526 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
528 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
529 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
534 if (IS_DEBUG_OSPF_EVENT
) {
536 "%s: considering link:%s "
537 "type:%d link_id:%s link_data:%s",
538 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
539 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
540 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
544 if (w
->type
== OSPF_VERTEX_ROUTER
) {
545 /* l is a link from v to w
546 * l2 will be link from w to v
548 struct router_lsa_link
*l2
= NULL
;
550 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
551 struct in_addr nexthop
= {.s_addr
= 0};
553 /* If the destination is a router which connects
555 the calculating router via a
557 network, the destination's next hop IP
559 can be determined by examining the
561 router-LSA: each link pointing back to the
562 calculating router and having a Link Data
564 belonging to the Point-to-MultiPoint network
565 provides an IP address of the next hop
568 At this point l is a link from V to W, and V
570 root ("us"). If it is a point-to-multipoint
572 then look through the links in the opposite
574 If any of them have an address that lands
576 subnet declared by the PtMP link, then that
578 is a constituent of the PtMP link, and its
580 a nexthop address for V.
582 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
583 /* Having nexthop = 0 is tempting, but
585 It breaks AS-External routes with a
588 ospf_ase_complete_direct_routes()
590 assume we've reached the last hop and
592 forwarding address as nexthop.
593 Also, users may configure
594 multi-access links in p2p mode,
595 so we need the IP to ARP the nexthop.
597 struct ospf_neighbor
*nbr_w
;
599 nbr_w
= ospf_nbr_lookup_by_routerid(
600 oi
->nbrs
, &l
->link_id
);
603 nexthop
= nbr_w
->src
;
606 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
607 struct prefix_ipv4 la
;
610 la
.prefixlen
= oi
->address
->prefixlen
;
612 /* V links to W on PtMP interface
613 - find the interface address on W */
614 while ((l2
= ospf_get_next_link(w
, v
,
616 la
.prefix
= l2
->link_data
;
618 if (prefix_cmp((struct prefix
623 /* link_data is on our PtMP
626 nexthop
= l2
->link_data
;
632 /* found all necessary info to build
634 nh
= vertex_nexthop_new();
636 nh
->router
= nexthop
;
637 ospf_spf_add_parent(v
, w
, nh
, distance
);
641 "%s: could not determine nexthop for link %s",
642 __func__
, oi
->ifp
->name
);
643 } /* end point-to-point link from V to W */
644 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
645 struct ospf_vl_data
*vl_data
;
647 /* VLink implementation limitations:
648 * a) vl_data can only reference one nexthop, so
650 * to backbone through VLinks. Though
652 * summaries may be considered, and those can
654 * b) We can only use /one/ VLink, even if
656 * exist this router through multiple
659 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
663 && CHECK_FLAG(vl_data
->flags
,
664 OSPF_VL_FLAG_APPROVED
)) {
665 nh
= vertex_nexthop_new();
666 nh
->oi
= vl_data
->nexthop
.oi
;
667 nh
->router
= vl_data
->nexthop
.router
;
668 ospf_spf_add_parent(v
, w
, nh
, distance
);
672 "ospf_nexthop_calculation(): "
673 "vl_data for VL link not found");
674 } /* end virtual-link from V to W */
676 } /* end W is a Router vertex */
678 assert(w
->type
== OSPF_VERTEX_NETWORK
);
680 nh
= vertex_nexthop_new();
682 nh
->router
.s_addr
= 0; /* Nexthop not required */
683 ospf_spf_add_parent(v
, w
, nh
, distance
);
686 } /* end V is the root */
687 /* Check if W's parent is a network connected to root. */
688 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
689 /* See if any of V's parents are the root. */
690 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
691 if (vp
->parent
== area
->spf
) /* connects to root? */
693 /* 16.1.1 para 5. ...the parent vertex is a
695 * directly connects the calculating router to
697 * router. The list of next hops is then
699 * examining the destination's router-LSA...
702 assert(w
->type
== OSPF_VERTEX_ROUTER
);
703 while ((l
= ospf_get_next_link(w
, v
, l
))) {
704 /* ...For each link in the router-LSA
705 * that points back to the
706 * parent network, the link's Link Data
707 * field provides the IP
708 * address of a next hop router. The
709 * outgoing interface to
710 * use can then be derived from the next
712 * it can be inherited from the parent
715 nh
= vertex_nexthop_new();
716 nh
->oi
= vp
->nexthop
->oi
;
717 nh
->router
= l
->link_data
;
719 ospf_spf_add_parent(v
, w
, nh
, distance
);
721 /* Note lack of return is deliberate. See next
725 /* NB: This code is non-trivial.
727 * E.g. it is not enough to know that V connects to the root. It
729 * also important that the while above, looping through all
731 * W->V found at least one link, so that we know there is
732 * bi-directional connectivity between V and W (which need not
734 * case, e.g. when OSPF has not yet converged fully).
736 * we /always/ return here, without having checked that
738 * actually resulted in a valid nexthop being created, then we
740 * prevent SPF from finding/using higher cost paths.
742 * It is important, if root->V->W has not been added, that we
744 * through to the intervening-router nexthop code below. So as
746 * ensure other paths to V may be used. This avoids unnecessary
747 * blackholes while OSPF is convergening.
749 * I.e. we may have arrived at this function, examining V -> W,
751 * workable paths other than root -> V, and it's important to
753 * getting "confused" by non-working root->V->W path - it's
755 * to *not* lose the working non-root paths, just because of a
756 * non-viable root->V->W.
758 * See also bug #330 (required reading!), and:
760 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
766 /* 16.1.1 para 4. If there is at least one intervening router in the
767 * current shortest path between the destination and the root, the
768 * destination simply inherits the set of next hops from the
771 if (IS_DEBUG_OSPF_EVENT
)
772 zlog_debug("%s: Intervening routers, adding parent(s)",
775 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
777 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
783 /* RFC2328 Section 16.1 (2).
784 * v is on the SPF tree. Examine the links in v's LSA. Update the list
785 * of candidates with any vertices not already on the list. If a lower-cost
786 * path is found to a vertex already on the candidate list, store the new cost.
788 static void ospf_spf_next(struct vertex
*v
, struct ospf
*ospf
,
789 struct ospf_area
*area
, struct pqueue
*candidate
)
791 struct ospf_lsa
*w_lsa
= NULL
;
794 struct router_lsa_link
*l
= NULL
;
796 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
798 /* If this is a router-LSA, and bit V of the router-LSA (see Section
799 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
800 if (v
->type
== OSPF_VERTEX_ROUTER
) {
801 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
802 area
->transit
= OSPF_TRANSIT_TRUE
;
805 if (IS_DEBUG_OSPF_EVENT
)
806 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
807 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
808 inet_ntoa(v
->lsa
->id
));
810 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
811 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
815 unsigned int distance
;
817 /* In case of V is Router-LSA. */
818 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
819 l
= (struct router_lsa_link
*)p
;
821 lsa_pos
= lsa_pos_next
; /* LSA link position */
823 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
824 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
826 /* (a) If this is a link to a stub network, examine the
828 link in V's LSA. Links to stub networks will be
829 considered in the second stage of the shortest path
831 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
834 /* (b) Otherwise, W is a transit vertex (router or
836 network). Look up the vertex W's LSA (router-LSA or
837 network-LSA) in Area A's link state database. */
839 case LSA_LINK_TYPE_POINTOPOINT
:
840 case LSA_LINK_TYPE_VIRTUALLINK
:
841 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
842 if (IS_DEBUG_OSPF_EVENT
)
844 "looking up LSA through VL: %s",
845 inet_ntoa(l
->link_id
));
848 w_lsa
= ospf_lsa_lookup(ospf
, area
,
850 l
->link_id
, l
->link_id
);
852 if (IS_DEBUG_OSPF_EVENT
)
854 "found Router LSA %s",
855 inet_ntoa(l
->link_id
));
858 case LSA_LINK_TYPE_TRANSIT
:
859 if (IS_DEBUG_OSPF_EVENT
)
861 "Looking up Network LSA, ID: %s",
862 inet_ntoa(l
->link_id
));
863 w_lsa
= ospf_lsa_lookup_by_id(
864 area
, OSPF_NETWORK_LSA
, l
->link_id
);
866 if (IS_DEBUG_OSPF_EVENT
)
867 zlog_debug("found the LSA");
870 flog_warn(EC_OSPF_LSA
,
871 "Invalid LSA link type %d", type
);
875 /* In case of V is Network-LSA. */
876 r
= (struct in_addr
*)p
;
877 p
+= sizeof(struct in_addr
);
879 /* Lookup the vertex W's LSA. */
880 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
883 if (IS_DEBUG_OSPF_EVENT
)
884 zlog_debug("found Router LSA %s",
885 inet_ntoa(w_lsa
->data
->id
));
889 /* (b cont.) If the LSA does not exist, or its LS age is equal
890 to MaxAge, or it does not have a link back to vertex V,
891 examine the next link in V's LSA.[23] */
893 if (IS_DEBUG_OSPF_EVENT
)
894 zlog_debug("No LSA found");
898 if (IS_LSA_MAXAGE(w_lsa
)) {
899 if (IS_DEBUG_OSPF_EVENT
)
900 zlog_debug("LSA is MaxAge");
904 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
905 if (IS_DEBUG_OSPF_EVENT
)
906 zlog_debug("The LSA doesn't have a link back");
910 /* (c) If vertex W is already on the shortest-path tree, examine
911 the next link in the LSA. */
912 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
913 if (IS_DEBUG_OSPF_EVENT
)
914 zlog_debug("The LSA is already in SPF");
918 /* (d) Calculate the link state cost D of the resulting path
919 from the root to vertex W. D is equal to the sum of the link
920 state cost of the (already calculated) shortest path to
921 vertex V and the advertised cost of the link between vertices
924 /* calculate link cost D. */
925 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
926 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
927 else /* v is not a Router-LSA */
928 distance
= v
->distance
;
930 /* Is there already vertex W in candidate list? */
931 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
932 /* prepare vertex W. */
933 w
= ospf_vertex_new(w_lsa
);
935 /* Calculate nexthop to W. */
936 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
938 pqueue_enqueue(w
, candidate
);
939 else if (IS_DEBUG_OSPF_EVENT
)
940 zlog_debug("Nexthop Calc failed");
941 } else if (w_lsa
->stat
>= 0) {
942 /* Get the vertex from candidates. */
943 w
= candidate
->array
[w_lsa
->stat
];
945 /* if D is greater than. */
946 if (w
->distance
< distance
) {
950 else if (w
->distance
== distance
) {
951 /* Found an equal-cost path to W.
952 * Calculate nexthop of to W from V. */
953 ospf_nexthop_calculation(area
, v
, w
, l
,
958 /* Found a lower-cost path to W.
959 * nexthop_calculation is conditional, if it
961 * valid nexthop it will call spf_add_parents,
963 * will flush the old parents
965 if (ospf_nexthop_calculation(area
, v
, w
, l
,
967 /* Decrease the key of the node in the
969 * trickle-sort it up towards root, just
971 * node should now be the new root due
973 * (next pqueu_{de,en}queue will fully
974 * re-heap the queue).
976 trickle_up(w_lsa
->stat
, candidate
);
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 pqueue
*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 ospf_lsdb_clean_stat(area
->lsdb
);
1198 /* Create a new heap for the candidates. */
1199 candidate
= pqueue_create();
1200 candidate
->cmp
= cmp
;
1201 candidate
->update
= update_stat
;
1203 /* Initialize the shortest-path tree to only the root (which is the
1204 router doing the calculation). */
1205 ospf_spf_init(area
);
1207 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1210 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1212 /* Set Area A's TransitCapability to FALSE. */
1213 area
->transit
= OSPF_TRANSIT_FALSE
;
1214 area
->shortcut_capability
= 1;
1217 /* RFC2328 16.1. (2). */
1218 ospf_spf_next(v
, ospf
, area
, candidate
);
1220 /* RFC2328 16.1. (3). */
1221 /* If at this step the candidate list is empty, the shortest-
1222 path tree (of transit vertices) has been completely built and
1223 this stage of the procedure terminates. */
1224 if (candidate
->size
== 0)
1227 /* Otherwise, choose the vertex belonging to the candidate list
1228 that is closest to the root, and add it to the shortest-path
1229 tree (removing it from the candidate list in the
1231 /* Extract from the candidates the node with the lower key. */
1232 v
= (struct vertex
*)pqueue_dequeue(candidate
);
1233 /* Update stat field in vertex. */
1234 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1236 ospf_vertex_add_parent(v
);
1238 /* RFC2328 16.1. (4). */
1239 if (v
->type
== OSPF_VERTEX_ROUTER
)
1240 ospf_intra_add_router(new_rtrs
, v
, area
);
1242 ospf_intra_add_transit(new_table
, v
, area
);
1244 /* RFC2328 16.1. (5). */
1245 /* Iterate the algorithm by returning to Step 2. */
1247 } /* end loop until no more candidate vertices */
1249 if (IS_DEBUG_OSPF_EVENT
) {
1250 ospf_spf_dump(area
->spf
, 0);
1251 ospf_route_table_dump(new_table
);
1254 /* Second stage of SPF calculation procedure's */
1255 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1257 /* Free candidate queue. */
1258 pqueue_delete(candidate
);
1260 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1261 /* Free nexthop information, canonical versions of which are attached
1262 * the first level of router vertices attached to the root vertex, see
1263 * ospf_nexthop_calculation.
1265 ospf_canonical_nexthops_free(area
->spf
);
1267 /* Increment SPF Calculation Counter. */
1268 area
->spf_calculation
++;
1270 monotime(&area
->ospf
->ts_spf
);
1271 area
->ts_spf
= area
->ospf
->ts_spf
;
1273 if (IS_DEBUG_OSPF_EVENT
)
1274 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1275 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1277 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1280 list_delete_all_node(&vertex_list
);
1283 /* Timer for SPF calculation. */
1284 static int ospf_spf_calculate_timer(struct thread
*thread
)
1286 struct ospf
*ospf
= THREAD_ARG(thread
);
1287 struct route_table
*new_table
, *new_rtrs
;
1288 struct ospf_area
*area
;
1289 struct listnode
*node
, *nnode
;
1290 struct timeval start_time
, spf_start_time
;
1291 int areas_processed
= 0;
1292 unsigned long ia_time
, prune_time
, rt_time
;
1293 unsigned long abr_time
, total_spf_time
, spf_time
;
1294 char rbuf
[32]; /* reason_buf */
1296 if (IS_DEBUG_OSPF_EVENT
)
1297 zlog_debug("SPF: Timer (SPF calculation expire)");
1299 ospf
->t_spf_calc
= NULL
;
1301 monotime(&spf_start_time
);
1302 /* Allocate new table tree. */
1303 new_table
= route_table_init();
1304 new_rtrs
= route_table_init();
1306 ospf_vl_unapprove(ospf
);
1308 /* Calculate SPF for each area. */
1309 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1310 /* Do backbone last, so as to first discover intra-area paths
1311 * for any back-bone virtual-links
1313 if (ospf
->backbone
&& ospf
->backbone
== area
)
1316 ospf_spf_calculate(ospf
, area
, new_table
, new_rtrs
);
1320 /* SPF for backbone, if required */
1321 if (ospf
->backbone
) {
1322 ospf_spf_calculate(ospf
, ospf
->backbone
, new_table
, new_rtrs
);
1326 spf_time
= monotime_since(&spf_start_time
, NULL
);
1328 ospf_vl_shut_unapproved(ospf
);
1330 monotime(&start_time
);
1331 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1332 ia_time
= monotime_since(&start_time
, NULL
);
1334 monotime(&start_time
);
1335 ospf_prune_unreachable_networks(new_table
);
1336 ospf_prune_unreachable_routers(new_rtrs
);
1337 prune_time
= monotime_since(&start_time
, NULL
);
1339 /* AS-external-LSA calculation should not be performed here. */
1341 /* If new Router Route is installed,
1342 then schedule re-calculate External routes. */
1344 ospf_ase_calculate_schedule(ospf
);
1346 ospf_ase_calculate_timer_add(ospf
);
1348 if (IS_DEBUG_OSPF_EVENT
)
1350 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1351 __PRETTY_FUNCTION__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1352 ospf
->vrf_id
, new_table
->count
);
1353 /* Update routing table. */
1354 monotime(&start_time
);
1355 ospf_route_install(ospf
, new_table
);
1356 rt_time
= monotime_since(&start_time
, NULL
);
1358 /* Update ABR/ASBR routing table */
1359 if (ospf
->old_rtrs
) {
1360 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1362 /* ospf_route_delete (ospf->old_rtrs); */
1363 ospf_rtrs_free(ospf
->old_rtrs
);
1366 ospf
->old_rtrs
= ospf
->new_rtrs
;
1367 ospf
->new_rtrs
= new_rtrs
;
1369 monotime(&start_time
);
1370 if (IS_OSPF_ABR(ospf
))
1371 ospf_abr_task(ospf
);
1372 abr_time
= monotime_since(&start_time
, NULL
);
1374 /* Schedule Segment Routing update */
1375 ospf_sr_update_timer_add(ospf
);
1378 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1381 if (spf_reason_flags
) {
1382 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1383 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1384 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1385 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1386 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1387 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1388 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1389 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1390 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1391 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1392 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1393 strncat(rbuf
, "ASBR, ",
1394 sizeof(rbuf
) - strlen(rbuf
) - 1);
1395 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1396 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1398 size_t rbuflen
= strlen(rbuf
);
1400 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1405 if (IS_DEBUG_OSPF_EVENT
) {
1406 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1407 zlog_info("\t SPF Time: %ld", spf_time
);
1408 zlog_info("\t InterArea: %ld", ia_time
);
1409 zlog_info("\t Prune: %ld", prune_time
);
1410 zlog_info("\tRouteInstall: %ld", rt_time
);
1411 if (IS_OSPF_ABR(ospf
))
1412 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1414 zlog_info("Reason(s) for SPF: %s", rbuf
);
1417 ospf_clear_spf_reason_flags();
1422 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1423 set timer for SPF calc. */
1424 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1426 unsigned long delay
, elapsed
, ht
;
1428 if (IS_DEBUG_OSPF_EVENT
)
1429 zlog_debug("SPF: calculation timer scheduled");
1431 /* OSPF instance does not exist. */
1435 ospf_spf_set_reason(reason
);
1437 /* SPF calculation timer is already scheduled. */
1438 if (ospf
->t_spf_calc
) {
1439 if (IS_DEBUG_OSPF_EVENT
)
1441 "SPF: calculation timer is already scheduled: %p",
1442 (void *)ospf
->t_spf_calc
);
1446 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1448 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1450 if (ht
> ospf
->spf_max_holdtime
)
1451 ht
= ospf
->spf_max_holdtime
;
1453 /* Get SPF calculation delay time. */
1455 /* Got an event within the hold time of last SPF. We need to
1456 * increase the hold_multiplier, if it's not already at/past
1457 * maximum value, and wasn't already increased..
1459 if (ht
< ospf
->spf_max_holdtime
)
1460 ospf
->spf_hold_multiplier
++;
1462 /* always honour the SPF initial delay */
1463 if ((ht
- elapsed
) < ospf
->spf_delay
)
1464 delay
= ospf
->spf_delay
;
1466 delay
= ht
- elapsed
;
1468 /* Event is past required hold-time of last SPF */
1469 delay
= ospf
->spf_delay
;
1470 ospf
->spf_hold_multiplier
= 1;
1473 if (IS_DEBUG_OSPF_EVENT
)
1474 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
1476 ospf
->t_spf_calc
= NULL
;
1477 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,