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;
55 ospf_clear_spf_reason_flags (void)
61 ospf_spf_set_reason (ospf_spf_reason_t reason
)
63 spf_reason_flags
|= 1 << reason
;
67 ospf_get_spf_reason_str (char *buf
)
75 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
77 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
79 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
81 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
83 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
84 strcat (buf
, "ABR, ");
85 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
86 strcat (buf
, "ASBR, ");
87 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
89 buf
[strlen(buf
)-2] = '\0'; /* skip the last ", " */
93 static void ospf_vertex_free (void *);
94 /* List of allocated vertices, to simplify cleanup of SPF.
95 * Not thread-safe obviously. If it ever needs to be, it'd have to be
96 * dynamically allocated at begin of ospf_spf_calculate
98 static struct list vertex_list
= { .del
= ospf_vertex_free
};
100 /* Heap related functions, for the managment of the candidates, to
101 * be used with pqueue. */
103 cmp (void * node1
, void * node2
)
105 struct vertex
* v1
= (struct vertex
*) node1
;
106 struct vertex
* v2
= (struct vertex
*) node2
;
107 if (v1
!= NULL
&& v2
!= NULL
)
109 /* network vertices must be chosen before router vertices of same
110 * cost in order to find all shortest paths
112 if ( ((v1
->distance
- v2
->distance
) == 0)
113 && (v1
->type
!= v2
->type
))
117 case OSPF_VERTEX_NETWORK
:
119 case OSPF_VERTEX_ROUTER
:
124 return (v1
->distance
- v2
->distance
);
130 update_stat (void *node
, int position
)
132 struct vertex
*v
= node
;
134 /* Set the status of the vertex, when its position changes. */
135 *(v
->stat
) = position
;
138 static struct vertex_nexthop
*
139 vertex_nexthop_new (void)
141 return XCALLOC (MTYPE_OSPF_NEXTHOP
, sizeof (struct vertex_nexthop
));
145 vertex_nexthop_free (struct vertex_nexthop
*nh
)
147 XFREE (MTYPE_OSPF_NEXTHOP
, nh
);
150 /* Free the canonical nexthop objects for an area, ie the nexthop objects
151 * attached to the first-hop router vertices, and any intervening network
155 ospf_canonical_nexthops_free (struct vertex
*root
)
157 struct listnode
*node
, *nnode
;
158 struct vertex
*child
;
160 for (ALL_LIST_ELEMENTS (root
->children
, node
, nnode
, child
))
162 struct listnode
*n2
, *nn2
;
163 struct vertex_parent
*vp
;
165 /* router vertices through an attached network each
166 * have a distinct (canonical / not inherited) nexthop
167 * which must be freed.
169 * A network vertex can only have router vertices as its
170 * children, so only one level of recursion is possible.
172 if (child
->type
== OSPF_VERTEX_NETWORK
)
173 ospf_canonical_nexthops_free (child
);
175 /* Free child nexthops pointing back to this root vertex */
176 for (ALL_LIST_ELEMENTS (child
->parents
, n2
, nn2
, vp
))
177 if (vp
->parent
== root
&& vp
->nexthop
)
178 vertex_nexthop_free (vp
->nexthop
);
182 /* TODO: Parent list should be excised, in favour of maintaining only
183 * vertex_nexthop, with refcounts.
185 static struct vertex_parent
*
186 vertex_parent_new (struct vertex
*v
, int backlink
, struct vertex_nexthop
*hop
)
188 struct vertex_parent
*new;
190 new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT
, sizeof (struct vertex_parent
));
196 new->backlink
= backlink
;
202 vertex_parent_free (void *p
)
204 XFREE (MTYPE_OSPF_VERTEX_PARENT
, p
);
207 static struct vertex
*
208 ospf_vertex_new (struct ospf_lsa
*lsa
)
212 new = XCALLOC (MTYPE_OSPF_VERTEX
, sizeof (struct vertex
));
215 new->stat
= &(lsa
->stat
);
216 new->type
= lsa
->data
->type
;
217 new->id
= lsa
->data
->id
;
218 new->lsa
= lsa
->data
;
219 new->children
= list_new ();
220 new->parents
= list_new ();
221 new->parents
->del
= vertex_parent_free
;
223 listnode_add (&vertex_list
, new);
225 if (IS_DEBUG_OSPF_EVENT
)
226 zlog_debug ("%s: Created %s vertex %s", __func__
,
227 new->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
228 inet_ntoa (new->lsa
->id
));
233 ospf_vertex_free (void *data
)
235 struct vertex
*v
= data
;
237 if (IS_DEBUG_OSPF_EVENT
)
238 zlog_debug ("%s: Free %s vertex %s", __func__
,
239 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
240 inet_ntoa (v
->lsa
->id
));
242 /* There should be no parents potentially holding references to this vertex
243 * Children however may still be there, but presumably referenced by other
246 //assert (listcount (v->parents) == 0);
249 list_delete (v
->children
);
253 list_delete (v
->parents
);
258 XFREE (MTYPE_OSPF_VERTEX
, v
);
262 ospf_vertex_dump(const char *msg
, struct vertex
*v
,
263 int print_parents
, int print_children
)
265 if ( ! IS_DEBUG_OSPF_EVENT
)
268 zlog_debug("%s %s vertex %s distance %u flags %u",
270 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
271 inet_ntoa(v
->lsa
->id
),
273 (unsigned int)v
->flags
);
277 struct listnode
*node
;
278 struct vertex_parent
*vp
;
280 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
286 zlog_debug ("parent %s backlink %d nexthop %s interface %s",
287 inet_ntoa(vp
->parent
->lsa
->id
), vp
->backlink
,
288 inet_ntop(AF_INET
, &vp
->nexthop
->router
, buf1
, BUFSIZ
),
289 vp
->nexthop
->oi
? IF_NAME(vp
->nexthop
->oi
) : "NULL");
296 struct listnode
*cnode
;
299 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, cv
))
300 ospf_vertex_dump(" child:", cv
, 0, 0);
305 /* Add a vertex to the list of children in each of its parents. */
307 ospf_vertex_add_parent (struct vertex
*v
)
309 struct vertex_parent
*vp
;
310 struct listnode
*node
;
312 assert (v
&& v
->parents
);
314 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
316 assert (vp
->parent
&& vp
->parent
->children
);
318 /* No need to add two links from the same parent. */
319 if (listnode_lookup (vp
->parent
->children
, v
) == NULL
)
320 listnode_add (vp
->parent
->children
, v
);
325 ospf_spf_init (struct ospf_area
*area
)
329 /* Create root node. */
330 v
= ospf_vertex_new (area
->router_lsa_self
);
334 /* Reset ABR and ASBR router counts. */
336 area
->asbr_count
= 0;
339 /* return index of link back to V from W, or -1 if no link found */
341 ospf_lsa_has_link (struct lsa_header
*w
, struct lsa_header
*v
)
343 unsigned int i
, length
;
344 struct router_lsa
*rl
;
345 struct network_lsa
*nl
;
347 /* In case of W is Network LSA. */
348 if (w
->type
== OSPF_NETWORK_LSA
)
350 if (v
->type
== OSPF_NETWORK_LSA
)
353 nl
= (struct network_lsa
*) w
;
354 length
= (ntohs (w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
356 for (i
= 0; i
< length
; i
++)
357 if (IPV4_ADDR_SAME (&nl
->routers
[i
], &v
->id
))
362 /* In case of W is Router LSA. */
363 if (w
->type
== OSPF_ROUTER_LSA
)
365 rl
= (struct router_lsa
*) w
;
367 length
= ntohs (w
->length
);
370 i
< ntohs (rl
->links
) && length
>= sizeof (struct router_lsa
);
373 switch (rl
->link
[i
].type
)
375 case LSA_LINK_TYPE_POINTOPOINT
:
376 case LSA_LINK_TYPE_VIRTUALLINK
:
378 if (v
->type
== OSPF_ROUTER_LSA
&&
379 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
384 case LSA_LINK_TYPE_TRANSIT
:
385 /* Network LSA ID. */
386 if (v
->type
== OSPF_NETWORK_LSA
&&
387 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
392 case LSA_LINK_TYPE_STUB
:
393 /* Stub can't lead anywhere, carry on */
403 /* Find the next link after prev_link from v to w. If prev_link is
404 * NULL, return the first link from v to w. Ignore stub and virtual links;
405 * these link types will never be returned.
407 static struct router_lsa_link
*
408 ospf_get_next_link (struct vertex
*v
, struct vertex
*w
,
409 struct router_lsa_link
*prev_link
)
413 u_char lsa_type
= LSA_LINK_TYPE_TRANSIT
;
414 struct router_lsa_link
*l
;
416 if (w
->type
== OSPF_VERTEX_ROUTER
)
417 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
419 if (prev_link
== NULL
)
420 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
423 p
= (u_char
*) prev_link
;
424 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+
425 (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
428 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
432 l
= (struct router_lsa_link
*) p
;
434 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+ (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
436 if (l
->m
[0].type
!= lsa_type
)
439 if (IPV4_ADDR_SAME (&l
->link_id
, &w
->id
))
447 ospf_spf_flush_parents (struct vertex
*w
)
449 struct vertex_parent
*vp
;
450 struct listnode
*ln
, *nn
;
452 /* delete the existing nexthops */
453 for (ALL_LIST_ELEMENTS (w
->parents
, ln
, nn
, vp
))
455 list_delete_node (w
->parents
, ln
);
456 vertex_parent_free (vp
);
461 * Consider supplied next-hop for inclusion to the supplied list of
462 * equal-cost next-hops, adjust list as neccessary.
465 ospf_spf_add_parent (struct vertex
*v
, struct vertex
*w
,
466 struct vertex_nexthop
*newhop
,
467 unsigned int distance
)
469 struct vertex_parent
*vp
, *wp
;
470 struct listnode
*node
;
472 /* we must have a newhop, and a distance */
473 assert (v
&& w
&& newhop
);
476 /* IFF w has already been assigned a distance, then we shouldn't get here
477 * unless callers have determined V(l)->W is shortest / equal-shortest
478 * path (0 is a special case distance (no distance yet assigned)).
481 assert (distance
<= w
->distance
);
483 w
->distance
= distance
;
485 if (IS_DEBUG_OSPF_EVENT
)
487 char buf
[2][INET_ADDRSTRLEN
];
488 zlog_debug ("%s: Adding %s as parent of %s",
490 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
491 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1], sizeof(buf
[1])));
494 /* Adding parent for a new, better path: flush existing parents from W. */
495 if (distance
< w
->distance
)
497 if (IS_DEBUG_OSPF_EVENT
)
498 zlog_debug ("%s: distance %d better than %d, flushing existing parents",
499 __func__
, distance
, w
->distance
);
500 ospf_spf_flush_parents (w
);
501 w
->distance
= distance
;
504 /* new parent is <= existing parents, add it to parent list (if nexthop
505 * not on parent list)
507 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
))
509 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0)
511 if (IS_DEBUG_OSPF_EVENT
)
512 zlog_debug ("%s: ... nexthop already on parent list, skipping add", __func__
);
517 vp
= vertex_parent_new (v
, ospf_lsa_has_link (w
->lsa
, v
->lsa
), newhop
);
518 listnode_add (w
->parents
, vp
);
523 /* 16.1.1. Calculate nexthop from root through V (parent) to
524 * vertex W (destination), with given distance from root->W.
526 * The link must be supplied if V is the root vertex. In all other cases
529 * Note that this function may fail, hence the state of the destination
530 * vertex, W, should /not/ be modified in a dependent manner until
531 * this function returns. This function will update the W vertex with the
532 * provided distance as appropriate.
535 ospf_nexthop_calculation (struct ospf_area
*area
, struct vertex
*v
,
536 struct vertex
*w
, struct router_lsa_link
*l
,
537 unsigned int distance
, int lsa_pos
)
539 struct listnode
*node
, *nnode
;
540 struct vertex_nexthop
*nh
;
541 struct vertex_parent
*vp
;
542 struct ospf_interface
*oi
= NULL
;
543 unsigned int added
= 0;
547 if (IS_DEBUG_OSPF_EVENT
)
549 zlog_debug ("ospf_nexthop_calculation(): Start");
550 ospf_vertex_dump("V (parent):", v
, 1, 1);
551 ospf_vertex_dump("W (dest) :", w
, 1, 1);
552 zlog_debug ("V->W distance: %d", distance
);
557 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
558 root (the calculating router itself). This means that the
559 destination is either a directly connected network or directly
560 connected router. The outgoing interface in this case is simply
561 the OSPF interface connecting to the destination network/router.
564 /* we *must* be supplied with the link data */
566 oi
= ospf_if_lookup_by_lsa_pos (area
, lsa_pos
);
569 zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
571 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
572 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
576 if (IS_DEBUG_OSPF_EVENT
)
578 zlog_debug("%s: considering link:%s "
579 "type:%d link_id:%s link_data:%s",
580 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
581 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
582 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
585 if (w
->type
== OSPF_VERTEX_ROUTER
)
587 /* l is a link from v to w
588 * l2 will be link from w to v
590 struct router_lsa_link
*l2
= NULL
;
592 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
)
594 struct in_addr nexthop
= { .s_addr
= 0 };
596 /* If the destination is a router which connects to
597 the calculating router via a Point-to-MultiPoint
598 network, the destination's next hop IP address(es)
599 can be determined by examining the destination's
600 router-LSA: each link pointing back to the
601 calculating router and having a Link Data field
602 belonging to the Point-to-MultiPoint network
603 provides an IP address of the next hop router.
605 At this point l is a link from V to W, and V is the
606 root ("us"). If it is a point-to-multipoint interface,
607 then look through the links in the opposite direction (W to V).
608 If any of them have an address that lands within the
609 subnet declared by the PtMP link, then that link
610 is a constituent of the PtMP link, and its address is
611 a nexthop address for V.
613 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
615 /* Having nexthop = 0 is tempting, but NOT acceptable.
616 It breaks AS-External routes with a forwarding address,
617 since ospf_ase_complete_direct_routes() will mistakenly
618 assume we've reached the last hop and should place the
619 forwarding address as nexthop.
620 Also, users may configure multi-access links in p2p mode,
621 so we need the IP to ARP the nexthop.
623 struct ospf_neighbor
*nbr_w
;
625 nbr_w
= ospf_nbr_lookup_by_routerid (oi
->nbrs
, &l
->link_id
);
629 nexthop
= nbr_w
->src
;
632 else if (oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
)
634 struct prefix_ipv4 la
;
637 la
.prefixlen
= oi
->address
->prefixlen
;
639 /* V links to W on PtMP interface
640 - find the interface address on W */
641 while ((l2
= ospf_get_next_link (w
, v
, l2
)))
643 la
.prefix
= l2
->link_data
;
645 if (prefix_cmp ((struct prefix
*) &la
,
648 /* link_data is on our PtMP network */
650 nexthop
= l2
->link_data
;
657 /* found all necessary info to build nexthop */
658 nh
= vertex_nexthop_new ();
660 nh
->router
= nexthop
;
661 ospf_spf_add_parent (v
, w
, nh
, distance
);
665 zlog_info("%s: could not determine nexthop for link %s",
666 __func__
, oi
->ifp
->name
);
667 } /* end point-to-point link from V to W */
668 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
)
670 struct ospf_vl_data
*vl_data
;
672 /* VLink implementation limitations:
673 * a) vl_data can only reference one nexthop, so no ECMP
674 * to backbone through VLinks. Though transit-area
675 * summaries may be considered, and those can be ECMP.
676 * b) We can only use /one/ VLink, even if multiple ones
677 * exist this router through multiple transit-areas.
679 vl_data
= ospf_vl_lookup (area
->ospf
, NULL
, l
->link_id
);
682 && CHECK_FLAG (vl_data
->flags
, OSPF_VL_FLAG_APPROVED
))
684 nh
= vertex_nexthop_new ();
685 nh
->oi
= vl_data
->nexthop
.oi
;
686 nh
->router
= vl_data
->nexthop
.router
;
687 ospf_spf_add_parent (v
, w
, nh
, distance
);
691 zlog_info("ospf_nexthop_calculation(): "
692 "vl_data for VL link not found");
693 } /* end virtual-link from V to W */
695 } /* end W is a Router vertex */
698 assert(w
->type
== OSPF_VERTEX_NETWORK
);
700 nh
= vertex_nexthop_new ();
702 nh
->router
.s_addr
= 0; /* Nexthop not required */
703 ospf_spf_add_parent (v
, w
, nh
, distance
);
706 } /* end V is the root */
707 /* Check if W's parent is a network connected to root. */
708 else if (v
->type
== OSPF_VERTEX_NETWORK
)
710 /* See if any of V's parents are the root. */
711 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
713 if (vp
->parent
== area
->spf
) /* connects to root? */
715 /* 16.1.1 para 5. ...the parent vertex is a network that
716 * directly connects the calculating router to the destination
717 * router. The list of next hops is then determined by
718 * examining the destination's router-LSA...
721 assert(w
->type
== OSPF_VERTEX_ROUTER
);
722 while ((l
= ospf_get_next_link (w
, v
, l
)))
724 /* ...For each link in the router-LSA that points back to the
725 * parent network, the link's Link Data field provides the IP
726 * address of a next hop router. The outgoing interface to
727 * use can then be derived from the next hop IP address (or
728 * it can be inherited from the parent network).
730 nh
= vertex_nexthop_new ();
731 nh
->oi
= vp
->nexthop
->oi
;
732 nh
->router
= l
->link_data
;
734 ospf_spf_add_parent (v
, w
, nh
, distance
);
736 /* Note lack of return is deliberate. See next comment. */
739 /* NB: This code is non-trivial.
741 * E.g. it is not enough to know that V connects to the root. It is
742 * also important that the while above, looping through all links from
743 * W->V found at least one link, so that we know there is
744 * bi-directional connectivity between V and W (which need not be the
745 * case, e.g. when OSPF has not yet converged fully). Otherwise, if
746 * we /always/ return here, without having checked that root->V->-W
747 * actually resulted in a valid nexthop being created, then we we will
748 * prevent SPF from finding/using higher cost paths.
750 * It is important, if root->V->W has not been added, that we continue
751 * through to the intervening-router nexthop code below. So as to
752 * ensure other paths to V may be used. This avoids unnecessary
753 * blackholes while OSPF is convergening.
755 * I.e. we may have arrived at this function, examining V -> W, via
756 * workable paths other than root -> V, and it's important to avoid
757 * getting "confused" by non-working root->V->W path - it's important
758 * to *not* lose the working non-root paths, just because of a
759 * non-viable root->V->W.
761 * See also bug #330 (required reading!), and:
763 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
769 /* 16.1.1 para 4. If there is at least one intervening router in the
770 * current shortest path between the destination and the root, the
771 * destination simply inherits the set of next hops from the
774 if (IS_DEBUG_OSPF_EVENT
)
775 zlog_debug ("%s: Intervening routers, adding parent(s)", __func__
);
777 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
780 ospf_spf_add_parent (v
, w
, vp
->nexthop
, distance
);
786 /* RFC2328 Section 16.1 (2).
787 * v is on the SPF tree. Examine the links in v's LSA. Update the list
788 * of candidates with any vertices not already on the list. If a lower-cost
789 * path is found to a vertex already on the candidate list, store the new cost.
792 ospf_spf_next (struct vertex
*v
, struct ospf_area
*area
,
793 struct pqueue
* candidate
)
795 struct ospf_lsa
*w_lsa
= NULL
;
798 struct router_lsa_link
*l
= NULL
;
800 int type
= 0, lsa_pos
=-1, lsa_pos_next
=0;
802 /* If this is a router-LSA, and bit V of the router-LSA (see Section
803 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
804 if (v
->type
== OSPF_VERTEX_ROUTER
)
806 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa
*) v
->lsa
))
807 area
->transit
= OSPF_TRANSIT_TRUE
;
810 if (IS_DEBUG_OSPF_EVENT
)
811 zlog_debug ("%s: Next vertex of %s vertex %s",
813 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
814 inet_ntoa(v
->lsa
->id
));
816 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
817 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
822 unsigned int distance
;
824 /* In case of V is Router-LSA. */
825 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 next
835 link in V's LSA. Links to stub networks will be
836 considered in the second stage of the shortest path
838 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
841 /* (b) Otherwise, W is a transit vertex (router or transit
842 network). Look up the vertex W's LSA (router-LSA or
843 network-LSA) in Area A's link state database. */
846 case LSA_LINK_TYPE_POINTOPOINT
:
847 case LSA_LINK_TYPE_VIRTUALLINK
:
848 if (type
== LSA_LINK_TYPE_VIRTUALLINK
)
850 if (IS_DEBUG_OSPF_EVENT
)
851 zlog_debug ("looking up LSA through VL: %s",
852 inet_ntoa (l
->link_id
));
855 w_lsa
= ospf_lsa_lookup (area
, OSPF_ROUTER_LSA
, l
->link_id
,
859 if (IS_DEBUG_OSPF_EVENT
)
860 zlog_debug ("found Router LSA %s", inet_ntoa (l
->link_id
));
863 case LSA_LINK_TYPE_TRANSIT
:
864 if (IS_DEBUG_OSPF_EVENT
)
865 zlog_debug ("Looking up Network LSA, ID: %s",
866 inet_ntoa (l
->link_id
));
867 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_NETWORK_LSA
,
870 if (IS_DEBUG_OSPF_EVENT
)
871 zlog_debug ("found the LSA");
874 zlog_warn ("Invalid LSA link type %d", type
);
880 /* In case of V is Network-LSA. */
881 r
= (struct in_addr
*) p
;
882 p
+= sizeof (struct in_addr
);
884 /* Lookup the vertex W's LSA. */
885 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_ROUTER_LSA
, *r
);
888 if (IS_DEBUG_OSPF_EVENT
)
889 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa
->data
->id
));
893 /* (b cont.) If the LSA does not exist, or its LS age is equal
894 to MaxAge, or it does not have a link back to vertex V,
895 examine the next link in V's LSA.[23] */
898 if (IS_DEBUG_OSPF_EVENT
)
899 zlog_debug ("No LSA found");
903 if (IS_LSA_MAXAGE (w_lsa
))
905 if (IS_DEBUG_OSPF_EVENT
)
906 zlog_debug ("LSA is MaxAge");
910 if (ospf_lsa_has_link (w_lsa
->data
, v
->lsa
) < 0 )
912 if (IS_DEBUG_OSPF_EVENT
)
913 zlog_debug ("The LSA doesn't have a link back");
917 /* (c) If vertex W is already on the shortest-path tree, examine
918 the next link in the LSA. */
919 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
)
921 if (IS_DEBUG_OSPF_EVENT
)
922 zlog_debug ("The LSA is already in SPF");
926 /* (d) Calculate the link state cost D of the resulting path
927 from the root to vertex W. D is equal to the sum of the link
928 state cost of the (already calculated) shortest path to
929 vertex V and the advertised cost of the link between vertices
932 /* calculate link cost D. */
933 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
934 distance
= v
->distance
+ ntohs (l
->m
[0].metric
);
935 else /* v is not a Router-LSA */
936 distance
= v
->distance
;
938 /* Is there already vertex W in candidate list? */
939 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
)
941 /* prepare vertex W. */
942 w
= ospf_vertex_new (w_lsa
);
944 /* Calculate nexthop to W. */
945 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
))
946 pqueue_enqueue (w
, candidate
);
947 else if (IS_DEBUG_OSPF_EVENT
)
948 zlog_debug ("Nexthop Calc failed");
950 else if (w_lsa
->stat
>= 0)
952 /* Get the vertex from candidates. */
953 w
= candidate
->array
[w_lsa
->stat
];
955 /* if D is greater than. */
956 if (w
->distance
< distance
)
961 else if (w
->distance
== distance
)
963 /* Found an equal-cost path to W.
964 * Calculate nexthop of to W from V. */
965 ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
);
970 /* Found a lower-cost path to W.
971 * nexthop_calculation is conditional, if it finds
972 * valid nexthop it will call spf_add_parents, which
973 * will flush the old parents
975 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
))
976 /* Decrease the key of the node in the heap.
977 * trickle-sort it up towards root, just in case this
978 * node should now be the new root due the cost change.
979 * (next pqueu_{de,en}queue will fully re-heap the queue).
981 trickle_up (w_lsa
->stat
, candidate
);
983 } /* end W is already on the candidate list */
984 } /* end loop over the links in V's LSA */
988 ospf_spf_dump (struct vertex
*v
, int i
)
990 struct listnode
*cnode
;
991 struct listnode
*nnode
;
992 struct vertex_parent
*parent
;
994 if (v
->type
== OSPF_VERTEX_ROUTER
)
996 if (IS_DEBUG_OSPF_EVENT
)
997 zlog_debug ("SPF Result: %d [R] %s", i
, inet_ntoa (v
->lsa
->id
));
1001 struct network_lsa
*lsa
= (struct network_lsa
*) v
->lsa
;
1002 if (IS_DEBUG_OSPF_EVENT
)
1003 zlog_debug ("SPF Result: %d [N] %s/%d", i
, inet_ntoa (v
->lsa
->id
),
1004 ip_masklen (lsa
->mask
));
1007 if (IS_DEBUG_OSPF_EVENT
)
1008 for (ALL_LIST_ELEMENTS_RO (v
->parents
, nnode
, parent
))
1010 zlog_debug (" nexthop %p %s %s",
1011 (void *)parent
->nexthop
,
1012 inet_ntoa (parent
->nexthop
->router
),
1013 parent
->nexthop
->oi
? IF_NAME(parent
->nexthop
->oi
)
1019 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, v
))
1020 ospf_spf_dump (v
, i
);
1023 /* Second stage of SPF calculation. */
1025 ospf_spf_process_stubs (struct ospf_area
*area
, struct vertex
*v
,
1026 struct route_table
*rt
,
1029 struct listnode
*cnode
, *cnnode
;
1030 struct vertex
*child
;
1032 if (IS_DEBUG_OSPF_EVENT
)
1033 zlog_debug ("ospf_process_stub():processing stubs for area %s",
1034 inet_ntoa (area
->area_id
));
1035 if (v
->type
== OSPF_VERTEX_ROUTER
)
1039 struct router_lsa_link
*l
;
1040 struct router_lsa
*rlsa
;
1043 if (IS_DEBUG_OSPF_EVENT
)
1044 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
1045 inet_ntoa (v
->lsa
->id
));
1046 rlsa
= (struct router_lsa
*) v
->lsa
;
1049 if (IS_DEBUG_OSPF_EVENT
)
1050 zlog_debug ("ospf_process_stubs(): we have %d links to process",
1051 ntohs (rlsa
->links
));
1052 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1053 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
1057 l
= (struct router_lsa_link
*) p
;
1059 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+
1060 (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1062 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1063 ospf_intra_add_stub (rt
, l
, v
, area
, parent_is_root
, lsa_pos
);
1068 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1, 1);
1070 for (ALL_LIST_ELEMENTS (v
->children
, cnode
, cnnode
, child
))
1072 if (CHECK_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
))
1075 /* the first level of routers connected to the root
1076 * should have 'parent_is_root' set, including those
1077 * connected via a network vertex.
1081 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1084 ospf_spf_process_stubs (area
, child
, rt
, parent_is_root
);
1086 SET_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
);
1091 ospf_rtrs_free (struct route_table
*rtrs
)
1093 struct route_node
*rn
;
1094 struct list
*or_list
;
1095 struct ospf_route
*or;
1096 struct listnode
*node
, *nnode
;
1098 if (IS_DEBUG_OSPF_EVENT
)
1099 zlog_debug ("Route: Router Routing Table free");
1101 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1102 if ((or_list
= rn
->info
) != NULL
)
1104 for (ALL_LIST_ELEMENTS (or_list
, node
, nnode
, or))
1105 ospf_route_free (or);
1107 list_delete (or_list
);
1109 /* Unlock the node. */
1111 route_unlock_node (rn
);
1113 route_table_finish (rtrs
);
1118 ospf_rtrs_print (struct route_table
*rtrs
)
1120 struct route_node
*rn
;
1121 struct list
*or_list
;
1122 struct listnode
*ln
;
1123 struct listnode
*pnode
;
1124 struct ospf_route
*or;
1125 struct ospf_path
*path
;
1129 if (IS_DEBUG_OSPF_EVENT
)
1130 zlog_debug ("ospf_rtrs_print() start");
1132 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1133 if ((or_list
= rn
->info
) != NULL
)
1134 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1136 switch (or->path_type
)
1138 case OSPF_PATH_INTRA_AREA
:
1139 if (IS_DEBUG_OSPF_EVENT
)
1140 zlog_debug ("%s [%d] area: %s",
1141 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1142 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1145 case OSPF_PATH_INTER_AREA
:
1146 if (IS_DEBUG_OSPF_EVENT
)
1147 zlog_debug ("%s IA [%d] area: %s",
1148 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1149 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1156 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1158 if (path
->nexthop
.s_addr
== 0)
1160 if (IS_DEBUG_OSPF_EVENT
)
1161 zlog_debug (" directly attached to %s\r\n",
1162 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1166 if (IS_DEBUG_OSPF_EVENT
)
1167 zlog_debug (" via %s, %s\r\n",
1168 inet_ntoa (path
->nexthop
),
1169 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1174 zlog_debug ("ospf_rtrs_print() end");
1178 /* Calculating the shortest-path tree for an area. */
1180 ospf_spf_calculate (struct ospf_area
*area
, struct route_table
*new_table
,
1181 struct route_table
*new_rtrs
)
1183 struct pqueue
*candidate
;
1186 if (IS_DEBUG_OSPF_EVENT
)
1188 zlog_debug ("ospf_spf_calculate: Start");
1189 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1190 inet_ntoa (area
->area_id
));
1193 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1194 return this area's calculation. */
1195 if (!area
->router_lsa_self
)
1197 if (IS_DEBUG_OSPF_EVENT
)
1198 zlog_debug ("ospf_spf_calculate: "
1199 "Skip area %s's calculation due to empty router_lsa_self",
1200 inet_ntoa (area
->area_id
));
1204 /* RFC2328 16.1. (1). */
1205 /* Initialize the algorithm's data structures. */
1207 /* This function scans all the LSA database and set the stat field to
1208 * LSA_SPF_NOT_EXPLORED. */
1209 ospf_lsdb_clean_stat (area
->lsdb
);
1210 /* Create a new heap for the candidates. */
1211 candidate
= pqueue_create();
1212 candidate
->cmp
= cmp
;
1213 candidate
->update
= update_stat
;
1215 /* Initialize the shortest-path tree to only the root (which is the
1216 router doing the calculation). */
1217 ospf_spf_init (area
);
1219 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1221 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1223 /* Set Area A's TransitCapability to FALSE. */
1224 area
->transit
= OSPF_TRANSIT_FALSE
;
1225 area
->shortcut_capability
= 1;
1229 /* RFC2328 16.1. (2). */
1230 ospf_spf_next (v
, area
, candidate
);
1232 /* RFC2328 16.1. (3). */
1233 /* If at this step the candidate list is empty, the shortest-
1234 path tree (of transit vertices) has been completely built and
1235 this stage of the procedure terminates. */
1236 if (candidate
->size
== 0)
1239 /* Otherwise, choose the vertex belonging to the candidate list
1240 that is closest to the root, and add it to the shortest-path
1241 tree (removing it from the candidate list in the
1243 /* Extract from the candidates the node with the lower key. */
1244 v
= (struct vertex
*) pqueue_dequeue (candidate
);
1245 /* Update stat field in vertex. */
1246 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1248 ospf_vertex_add_parent (v
);
1250 /* RFC2328 16.1. (4). */
1251 if (v
->type
== OSPF_VERTEX_ROUTER
)
1252 ospf_intra_add_router (new_rtrs
, v
, area
);
1254 ospf_intra_add_transit (new_table
, v
, area
);
1256 /* RFC2328 16.1. (5). */
1257 /* Iterate the algorithm by returning to Step 2. */
1259 } /* end loop until no more candidate vertices */
1261 if (IS_DEBUG_OSPF_EVENT
)
1263 ospf_spf_dump (area
->spf
, 0);
1264 ospf_route_table_dump (new_table
);
1267 /* Second stage of SPF calculation procedure's */
1268 ospf_spf_process_stubs (area
, area
->spf
, new_table
, 0);
1270 /* Free candidate queue. */
1271 pqueue_delete (candidate
);
1273 ospf_vertex_dump (__func__
, area
->spf
, 0, 1);
1274 /* Free nexthop information, canonical versions of which are attached
1275 * the first level of router vertices attached to the root vertex, see
1276 * ospf_nexthop_calculation.
1278 ospf_canonical_nexthops_free (area
->spf
);
1280 /* Increment SPF Calculation Counter. */
1281 area
->spf_calculation
++;
1283 monotime(&area
->ospf
->ts_spf
);
1284 area
->ts_spf
= area
->ospf
->ts_spf
;
1286 if (IS_DEBUG_OSPF_EVENT
)
1287 zlog_debug ("ospf_spf_calculate: Stop. %zd vertices",
1288 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1290 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1293 list_delete_all_node (&vertex_list
);
1296 /* Timer for SPF calculation. */
1298 ospf_spf_calculate_timer (struct thread
*thread
)
1300 struct ospf
*ospf
= THREAD_ARG (thread
);
1301 struct route_table
*new_table
, *new_rtrs
;
1302 struct ospf_area
*area
;
1303 struct listnode
*node
, *nnode
;
1304 struct timeval start_time
, spf_start_time
;
1305 int areas_processed
= 0;
1306 unsigned long ia_time
, prune_time
, rt_time
;
1307 unsigned long abr_time
, total_spf_time
, spf_time
;
1308 char rbuf
[32]; /* reason_buf */
1310 if (IS_DEBUG_OSPF_EVENT
)
1311 zlog_debug ("SPF: Timer (SPF calculation expire)");
1313 ospf
->t_spf_calc
= NULL
;
1315 monotime(&spf_start_time
);
1316 /* Allocate new table tree. */
1317 new_table
= route_table_init ();
1318 new_rtrs
= route_table_init ();
1320 ospf_vl_unapprove (ospf
);
1322 /* Calculate SPF for each area. */
1323 for (ALL_LIST_ELEMENTS (ospf
->areas
, node
, nnode
, area
))
1325 /* Do backbone last, so as to first discover intra-area paths
1326 * for any back-bone virtual-links
1328 if (ospf
->backbone
&& ospf
->backbone
== area
)
1331 ospf_spf_calculate (area
, new_table
, new_rtrs
);
1335 /* SPF for backbone, if required */
1338 ospf_spf_calculate (ospf
->backbone
, new_table
, new_rtrs
);
1342 spf_time
= monotime_since(&spf_start_time
, NULL
);
1344 ospf_vl_shut_unapproved (ospf
);
1346 monotime(&start_time
);
1347 ospf_ia_routing (ospf
, new_table
, new_rtrs
);
1348 ia_time
= monotime_since(&start_time
, NULL
);
1350 monotime(&start_time
);
1351 ospf_prune_unreachable_networks (new_table
);
1352 ospf_prune_unreachable_routers (new_rtrs
);
1353 prune_time
= monotime_since(&start_time
, NULL
);
1355 /* AS-external-LSA calculation should not be performed here. */
1357 /* If new Router Route is installed,
1358 then schedule re-calculate External routes. */
1360 ospf_ase_calculate_schedule (ospf
);
1362 ospf_ase_calculate_timer_add (ospf
);
1364 /* Update routing table. */
1365 monotime(&start_time
);
1366 ospf_route_install (ospf
, new_table
);
1367 rt_time
= monotime_since(&start_time
, NULL
);
1369 /* Update ABR/ASBR routing table */
1372 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1373 /* ospf_route_delete (ospf->old_rtrs); */
1374 ospf_rtrs_free (ospf
->old_rtrs
);
1377 ospf
->old_rtrs
= ospf
->new_rtrs
;
1378 ospf
->new_rtrs
= new_rtrs
;
1380 monotime(&start_time
);
1381 if (IS_OSPF_ABR (ospf
))
1382 ospf_abr_task (ospf
);
1383 abr_time
= monotime_since(&start_time
, NULL
);
1385 total_spf_time
= monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1387 ospf_get_spf_reason_str (rbuf
);
1389 if (IS_DEBUG_OSPF_EVENT
)
1391 zlog_info ("SPF Processing Time(usecs): %ld", total_spf_time
);
1392 zlog_info ("\t SPF Time: %ld", spf_time
);
1393 zlog_info ("\t InterArea: %ld", ia_time
);
1394 zlog_info ("\t Prune: %ld", prune_time
);
1395 zlog_info ("\tRouteInstall: %ld", rt_time
);
1396 if (IS_OSPF_ABR (ospf
))
1397 zlog_info ("\t ABR: %ld (%d areas)",
1398 abr_time
, areas_processed
);
1399 zlog_info ("Reason(s) for SPF: %s", rbuf
);
1402 ospf_clear_spf_reason_flags ();
1407 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1408 set timer for SPF calc. */
1410 ospf_spf_calculate_schedule (struct ospf
*ospf
, ospf_spf_reason_t reason
)
1412 unsigned long delay
, elapsed
, ht
;
1414 if (IS_DEBUG_OSPF_EVENT
)
1415 zlog_debug ("SPF: calculation timer scheduled");
1417 /* OSPF instance does not exist. */
1421 ospf_spf_set_reason (reason
);
1423 /* SPF calculation timer is already scheduled. */
1424 if (ospf
->t_spf_calc
)
1426 if (IS_DEBUG_OSPF_EVENT
)
1427 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1428 (void *)ospf
->t_spf_calc
);
1432 elapsed
= monotime_since (&ospf
->ts_spf
, NULL
) / 1000;
1434 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1436 if (ht
> ospf
->spf_max_holdtime
)
1437 ht
= ospf
->spf_max_holdtime
;
1439 /* Get SPF calculation delay time. */
1442 /* Got an event within the hold time of last SPF. We need to
1443 * increase the hold_multiplier, if it's not already at/past
1444 * maximum value, and wasn't already increased..
1446 if (ht
< ospf
->spf_max_holdtime
)
1447 ospf
->spf_hold_multiplier
++;
1449 /* always honour the SPF initial delay */
1450 if ( (ht
- elapsed
) < ospf
->spf_delay
)
1451 delay
= ospf
->spf_delay
;
1453 delay
= ht
- elapsed
;
1457 /* Event is past required hold-time of last SPF */
1458 delay
= ospf
->spf_delay
;
1459 ospf
->spf_hold_multiplier
= 1;
1462 if (IS_DEBUG_OSPF_EVENT
)
1463 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
1465 zlog_info ("SPF: Scheduled in %ld msec", delay
);
1467 ospf
->t_spf_calc
= NULL
;
1468 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,