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
;
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. */
76 cmp (void * node1
, void * node2
)
78 struct vertex
* v1
= (struct vertex
*) node1
;
79 struct vertex
* v2
= (struct vertex
*) node2
;
80 if (v1
!= NULL
&& v2
!= NULL
)
82 /* network vertices must be chosen before router vertices of same
83 * cost in order to find all shortest paths
85 if ( ((v1
->distance
- v2
->distance
) == 0)
86 && (v1
->type
!= v2
->type
))
90 case OSPF_VERTEX_NETWORK
:
92 case OSPF_VERTEX_ROUTER
:
97 return (v1
->distance
- v2
->distance
);
103 update_stat (void *node
, int position
)
105 struct vertex
*v
= node
;
107 /* Set the status of the vertex, when its position changes. */
108 *(v
->stat
) = position
;
111 static struct vertex_nexthop
*
112 vertex_nexthop_new (void)
114 return XCALLOC (MTYPE_OSPF_NEXTHOP
, sizeof (struct vertex_nexthop
));
118 vertex_nexthop_free (struct vertex_nexthop
*nh
)
120 XFREE (MTYPE_OSPF_NEXTHOP
, nh
);
123 /* Free the canonical nexthop objects for an area, ie the nexthop objects
124 * attached to the first-hop router vertices, and any intervening network
128 ospf_canonical_nexthops_free (struct vertex
*root
)
130 struct listnode
*node
, *nnode
;
131 struct vertex
*child
;
133 for (ALL_LIST_ELEMENTS (root
->children
, node
, nnode
, child
))
135 struct listnode
*n2
, *nn2
;
136 struct vertex_parent
*vp
;
138 /* router vertices through an attached network each
139 * have a distinct (canonical / not inherited) nexthop
140 * which must be freed.
142 * A network vertex can only have router vertices as its
143 * children, so only one level of recursion is possible.
145 if (child
->type
== OSPF_VERTEX_NETWORK
)
146 ospf_canonical_nexthops_free (child
);
148 /* Free child nexthops pointing back to this root vertex */
149 for (ALL_LIST_ELEMENTS (child
->parents
, n2
, nn2
, vp
))
150 if (vp
->parent
== root
&& vp
->nexthop
)
151 vertex_nexthop_free (vp
->nexthop
);
155 /* TODO: Parent list should be excised, in favour of maintaining only
156 * vertex_nexthop, with refcounts.
158 static struct vertex_parent
*
159 vertex_parent_new (struct vertex
*v
, int backlink
, struct vertex_nexthop
*hop
)
161 struct vertex_parent
*new;
163 new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT
, sizeof (struct vertex_parent
));
169 new->backlink
= backlink
;
175 vertex_parent_free (void *p
)
177 XFREE (MTYPE_OSPF_VERTEX_PARENT
, p
);
180 static struct vertex
*
181 ospf_vertex_new (struct ospf_lsa
*lsa
)
185 new = XCALLOC (MTYPE_OSPF_VERTEX
, sizeof (struct vertex
));
188 new->stat
= &(lsa
->stat
);
189 new->type
= lsa
->data
->type
;
190 new->id
= lsa
->data
->id
;
191 new->lsa
= lsa
->data
;
192 new->children
= list_new ();
193 new->parents
= list_new ();
194 new->parents
->del
= vertex_parent_free
;
196 listnode_add (&vertex_list
, new);
198 if (IS_DEBUG_OSPF_EVENT
)
199 zlog_debug ("%s: Created %s vertex %s", __func__
,
200 new->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
201 inet_ntoa (new->lsa
->id
));
206 ospf_vertex_free (void *data
)
208 struct vertex
*v
= data
;
210 if (IS_DEBUG_OSPF_EVENT
)
211 zlog_debug ("%s: Free %s vertex %s", __func__
,
212 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
213 inet_ntoa (v
->lsa
->id
));
215 /* There should be no parents potentially holding references to this vertex
216 * Children however may still be there, but presumably referenced by other
219 //assert (listcount (v->parents) == 0);
222 list_delete (v
->children
);
226 list_delete (v
->parents
);
231 XFREE (MTYPE_OSPF_VERTEX
, v
);
235 ospf_vertex_dump(const char *msg
, struct vertex
*v
,
236 int print_parents
, int print_children
)
238 if ( ! IS_DEBUG_OSPF_EVENT
)
241 zlog_debug("%s %s vertex %s distance %u flags %u",
243 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
244 inet_ntoa(v
->lsa
->id
),
246 (unsigned int)v
->flags
);
250 struct listnode
*node
;
251 struct vertex_parent
*vp
;
253 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
259 zlog_debug ("parent %s backlink %d nexthop %s interface %s",
260 inet_ntoa(vp
->parent
->lsa
->id
), vp
->backlink
,
261 inet_ntop(AF_INET
, &vp
->nexthop
->router
, buf1
, BUFSIZ
),
262 vp
->nexthop
->oi
? IF_NAME(vp
->nexthop
->oi
) : "NULL");
269 struct listnode
*cnode
;
272 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, cv
))
273 ospf_vertex_dump(" child:", cv
, 0, 0);
278 /* Add a vertex to the list of children in each of its parents. */
280 ospf_vertex_add_parent (struct vertex
*v
)
282 struct vertex_parent
*vp
;
283 struct listnode
*node
;
285 assert (v
&& v
->parents
);
287 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
289 assert (vp
->parent
&& vp
->parent
->children
);
291 /* No need to add two links from the same parent. */
292 if (listnode_lookup (vp
->parent
->children
, v
) == NULL
)
293 listnode_add (vp
->parent
->children
, v
);
298 ospf_spf_init (struct ospf_area
*area
)
302 /* Create root node. */
303 v
= ospf_vertex_new (area
->router_lsa_self
);
307 /* Reset ABR and ASBR router counts. */
309 area
->asbr_count
= 0;
312 /* return index of link back to V from W, or -1 if no link found */
314 ospf_lsa_has_link (struct lsa_header
*w
, struct lsa_header
*v
)
316 unsigned int i
, length
;
317 struct router_lsa
*rl
;
318 struct network_lsa
*nl
;
320 /* In case of W is Network LSA. */
321 if (w
->type
== OSPF_NETWORK_LSA
)
323 if (v
->type
== OSPF_NETWORK_LSA
)
326 nl
= (struct network_lsa
*) w
;
327 length
= (ntohs (w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
329 for (i
= 0; i
< length
; i
++)
330 if (IPV4_ADDR_SAME (&nl
->routers
[i
], &v
->id
))
335 /* In case of W is Router LSA. */
336 if (w
->type
== OSPF_ROUTER_LSA
)
338 rl
= (struct router_lsa
*) w
;
340 length
= ntohs (w
->length
);
343 i
< ntohs (rl
->links
) && length
>= sizeof (struct router_lsa
);
346 switch (rl
->link
[i
].type
)
348 case LSA_LINK_TYPE_POINTOPOINT
:
349 case LSA_LINK_TYPE_VIRTUALLINK
:
351 if (v
->type
== OSPF_ROUTER_LSA
&&
352 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
357 case LSA_LINK_TYPE_TRANSIT
:
358 /* Network LSA ID. */
359 if (v
->type
== OSPF_NETWORK_LSA
&&
360 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
365 case LSA_LINK_TYPE_STUB
:
366 /* Stub can't lead anywhere, carry on */
376 /* Find the next link after prev_link from v to w. If prev_link is
377 * NULL, return the first link from v to w. Ignore stub and virtual links;
378 * these link types will never be returned.
380 static struct router_lsa_link
*
381 ospf_get_next_link (struct vertex
*v
, struct vertex
*w
,
382 struct router_lsa_link
*prev_link
)
386 u_char lsa_type
= LSA_LINK_TYPE_TRANSIT
;
387 struct router_lsa_link
*l
;
389 if (w
->type
== OSPF_VERTEX_ROUTER
)
390 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
392 if (prev_link
== NULL
)
393 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
396 p
= (u_char
*) prev_link
;
397 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+
398 (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
401 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
405 l
= (struct router_lsa_link
*) p
;
407 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+ (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
409 if (l
->m
[0].type
!= lsa_type
)
412 if (IPV4_ADDR_SAME (&l
->link_id
, &w
->id
))
420 ospf_spf_flush_parents (struct vertex
*w
)
422 struct vertex_parent
*vp
;
423 struct listnode
*ln
, *nn
;
425 /* delete the existing nexthops */
426 for (ALL_LIST_ELEMENTS (w
->parents
, ln
, nn
, vp
))
428 list_delete_node (w
->parents
, ln
);
429 vertex_parent_free (vp
);
434 * Consider supplied next-hop for inclusion to the supplied list of
435 * equal-cost next-hops, adjust list as neccessary.
438 ospf_spf_add_parent (struct vertex
*v
, struct vertex
*w
,
439 struct vertex_nexthop
*newhop
,
440 unsigned int distance
)
442 struct vertex_parent
*vp
, *wp
;
443 struct listnode
*node
;
445 /* we must have a newhop, and a distance */
446 assert (v
&& w
&& newhop
);
449 /* IFF w has already been assigned a distance, then we shouldn't get here
450 * unless callers have determined V(l)->W is shortest / equal-shortest
451 * path (0 is a special case distance (no distance yet assigned)).
454 assert (distance
<= w
->distance
);
456 w
->distance
= distance
;
458 if (IS_DEBUG_OSPF_EVENT
)
460 char buf
[2][INET_ADDRSTRLEN
];
461 zlog_debug ("%s: Adding %s as parent of %s",
463 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
464 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1], sizeof(buf
[1])));
467 /* Adding parent for a new, better path: flush existing parents from W. */
468 if (distance
< w
->distance
)
470 if (IS_DEBUG_OSPF_EVENT
)
471 zlog_debug ("%s: distance %d better than %d, flushing existing parents",
472 __func__
, distance
, w
->distance
);
473 ospf_spf_flush_parents (w
);
474 w
->distance
= distance
;
477 /* new parent is <= existing parents, add it to parent list (if nexthop
478 * not on parent list)
480 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
))
482 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0)
484 if (IS_DEBUG_OSPF_EVENT
)
485 zlog_debug ("%s: ... nexthop already on parent list, skipping add", __func__
);
490 vp
= vertex_parent_new (v
, ospf_lsa_has_link (w
->lsa
, v
->lsa
), newhop
);
491 listnode_add (w
->parents
, vp
);
496 /* 16.1.1. Calculate nexthop from root through V (parent) to
497 * vertex W (destination), with given distance from root->W.
499 * The link must be supplied if V is the root vertex. In all other cases
502 * Note that this function may fail, hence the state of the destination
503 * vertex, W, should /not/ be modified in a dependent manner until
504 * this function returns. This function will update the W vertex with the
505 * provided distance as appropriate.
508 ospf_nexthop_calculation (struct ospf_area
*area
, struct vertex
*v
,
509 struct vertex
*w
, struct router_lsa_link
*l
,
510 unsigned int distance
, int lsa_pos
)
512 struct listnode
*node
, *nnode
;
513 struct vertex_nexthop
*nh
;
514 struct vertex_parent
*vp
;
515 struct ospf_interface
*oi
= NULL
;
516 unsigned int added
= 0;
520 if (IS_DEBUG_OSPF_EVENT
)
522 zlog_debug ("ospf_nexthop_calculation(): Start");
523 ospf_vertex_dump("V (parent):", v
, 1, 1);
524 ospf_vertex_dump("W (dest) :", w
, 1, 1);
525 zlog_debug ("V->W distance: %d", distance
);
530 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
531 root (the calculating router itself). This means that the
532 destination is either a directly connected network or directly
533 connected router. The outgoing interface in this case is simply
534 the OSPF interface connecting to the destination network/router.
537 /* we *must* be supplied with the link data */
539 oi
= ospf_if_lookup_by_lsa_pos (area
, lsa_pos
);
542 zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
544 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
545 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
549 if (IS_DEBUG_OSPF_EVENT
)
551 zlog_debug("%s: considering link:%s "
552 "type:%d link_id:%s link_data:%s",
553 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
554 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
555 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
558 if (w
->type
== OSPF_VERTEX_ROUTER
)
560 /* l is a link from v to w
561 * l2 will be link from w to v
563 struct router_lsa_link
*l2
= NULL
;
565 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
)
567 struct in_addr nexthop
= { .s_addr
= 0 };
569 /* If the destination is a router which connects to
570 the calculating router via a Point-to-MultiPoint
571 network, the destination's next hop IP address(es)
572 can be determined by examining the destination's
573 router-LSA: each link pointing back to the
574 calculating router and having a Link Data field
575 belonging to the Point-to-MultiPoint network
576 provides an IP address of the next hop router.
578 At this point l is a link from V to W, and V is the
579 root ("us"). If it is a point-to-multipoint interface,
580 then look through the links in the opposite direction (W to V).
581 If any of them have an address that lands within the
582 subnet declared by the PtMP link, then that link
583 is a constituent of the PtMP link, and its address is
584 a nexthop address for V.
586 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
588 /* Having nexthop = 0 is tempting, but NOT acceptable.
589 It breaks AS-External routes with a forwarding address,
590 since ospf_ase_complete_direct_routes() will mistakenly
591 assume we've reached the last hop and should place the
592 forwarding address as nexthop.
593 Also, users may configure multi-access links in p2p mode,
594 so we need the IP to ARP the nexthop.
596 struct ospf_neighbor
*nbr_w
;
598 nbr_w
= ospf_nbr_lookup_by_routerid (oi
->nbrs
, &l
->link_id
);
602 nexthop
= nbr_w
->src
;
605 else if (oi
->type
== 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
, l2
)))
616 la
.prefix
= l2
->link_data
;
618 if (prefix_cmp ((struct prefix
*) &la
,
621 /* link_data is on our PtMP network */
623 nexthop
= l2
->link_data
;
630 /* found all necessary info to build nexthop */
631 nh
= vertex_nexthop_new ();
633 nh
->router
= nexthop
;
634 ospf_spf_add_parent (v
, w
, nh
, distance
);
638 zlog_info("%s: could not determine nexthop for link %s",
639 __func__
, oi
->ifp
->name
);
640 } /* end point-to-point link from V to W */
641 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
)
643 struct ospf_vl_data
*vl_data
;
645 /* VLink implementation limitations:
646 * a) vl_data can only reference one nexthop, so no ECMP
647 * to backbone through VLinks. Though transit-area
648 * summaries may be considered, and those can be ECMP.
649 * b) We can only use /one/ VLink, even if multiple ones
650 * exist this router through multiple transit-areas.
652 vl_data
= ospf_vl_lookup (area
->ospf
, NULL
, l
->link_id
);
655 && CHECK_FLAG (vl_data
->flags
, OSPF_VL_FLAG_APPROVED
))
657 nh
= vertex_nexthop_new ();
658 nh
->oi
= vl_data
->nexthop
.oi
;
659 nh
->router
= vl_data
->nexthop
.router
;
660 ospf_spf_add_parent (v
, w
, nh
, distance
);
664 zlog_info("ospf_nexthop_calculation(): "
665 "vl_data for VL link not found");
666 } /* end virtual-link from V to W */
668 } /* end W is a Router vertex */
671 assert(w
->type
== OSPF_VERTEX_NETWORK
);
673 nh
= vertex_nexthop_new ();
675 nh
->router
.s_addr
= 0; /* Nexthop not required */
676 ospf_spf_add_parent (v
, w
, nh
, distance
);
679 } /* end V is the root */
680 /* Check if W's parent is a network connected to root. */
681 else if (v
->type
== OSPF_VERTEX_NETWORK
)
683 /* See if any of V's parents are the root. */
684 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
686 if (vp
->parent
== area
->spf
) /* connects to root? */
688 /* 16.1.1 para 5. ...the parent vertex is a network that
689 * directly connects the calculating router to the destination
690 * router. The list of next hops is then determined by
691 * examining the destination's router-LSA...
694 assert(w
->type
== OSPF_VERTEX_ROUTER
);
695 while ((l
= ospf_get_next_link (w
, v
, l
)))
697 /* ...For each link in the router-LSA that points back to the
698 * parent network, the link's Link Data field provides the IP
699 * address of a next hop router. The outgoing interface to
700 * use can then be derived from the next hop IP address (or
701 * it can be inherited from the parent network).
703 nh
= vertex_nexthop_new ();
704 nh
->oi
= vp
->nexthop
->oi
;
705 nh
->router
= l
->link_data
;
707 ospf_spf_add_parent (v
, w
, nh
, distance
);
709 /* Note lack of return is deliberate. See next comment. */
712 /* NB: This code is non-trivial.
714 * E.g. it is not enough to know that V connects to the root. It is
715 * also important that the while above, looping through all links from
716 * W->V found at least one link, so that we know there is
717 * bi-directional connectivity between V and W (which need not be the
718 * case, e.g. when OSPF has not yet converged fully). Otherwise, if
719 * we /always/ return here, without having checked that root->V->-W
720 * actually resulted in a valid nexthop being created, then we we will
721 * prevent SPF from finding/using higher cost paths.
723 * It is important, if root->V->W has not been added, that we continue
724 * through to the intervening-router nexthop code below. So as to
725 * ensure other paths to V may be used. This avoids unnecessary
726 * blackholes while OSPF is convergening.
728 * I.e. we may have arrived at this function, examining V -> W, via
729 * workable paths other than root -> V, and it's important to avoid
730 * getting "confused" by non-working root->V->W path - it's important
731 * to *not* lose the working non-root paths, just because of a
732 * non-viable root->V->W.
734 * See also bug #330 (required reading!), and:
736 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
742 /* 16.1.1 para 4. If there is at least one intervening router in the
743 * current shortest path between the destination and the root, the
744 * destination simply inherits the set of next hops from the
747 if (IS_DEBUG_OSPF_EVENT
)
748 zlog_debug ("%s: Intervening routers, adding parent(s)", __func__
);
750 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
753 ospf_spf_add_parent (v
, w
, vp
->nexthop
, distance
);
759 /* RFC2328 Section 16.1 (2).
760 * v is on the SPF tree. Examine the links in v's LSA. Update the list
761 * of candidates with any vertices not already on the list. If a lower-cost
762 * path is found to a vertex already on the candidate list, store the new cost.
765 ospf_spf_next (struct vertex
*v
, struct ospf_area
*area
,
766 struct pqueue
* candidate
)
768 struct ospf_lsa
*w_lsa
= NULL
;
771 struct router_lsa_link
*l
= NULL
;
773 int type
= 0, lsa_pos
=-1, lsa_pos_next
=0;
775 /* If this is a router-LSA, and bit V of the router-LSA (see Section
776 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
777 if (v
->type
== OSPF_VERTEX_ROUTER
)
779 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa
*) v
->lsa
))
780 area
->transit
= OSPF_TRANSIT_TRUE
;
783 if (IS_DEBUG_OSPF_EVENT
)
784 zlog_debug ("%s: Next vertex of %s vertex %s",
786 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
787 inet_ntoa(v
->lsa
->id
));
789 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
790 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
795 unsigned int distance
;
797 /* In case of V is Router-LSA. */
798 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
800 l
= (struct router_lsa_link
*) p
;
802 lsa_pos
= lsa_pos_next
; /* LSA link position */
804 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+
805 (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
807 /* (a) If this is a link to a stub network, examine the next
808 link in V's LSA. Links to stub networks will be
809 considered in the second stage of the shortest path
811 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
814 /* (b) Otherwise, W is a transit vertex (router or transit
815 network). Look up the vertex W's LSA (router-LSA or
816 network-LSA) in Area A's link state database. */
819 case LSA_LINK_TYPE_POINTOPOINT
:
820 case LSA_LINK_TYPE_VIRTUALLINK
:
821 if (type
== LSA_LINK_TYPE_VIRTUALLINK
)
823 if (IS_DEBUG_OSPF_EVENT
)
824 zlog_debug ("looking up LSA through VL: %s",
825 inet_ntoa (l
->link_id
));
828 w_lsa
= ospf_lsa_lookup (area
, OSPF_ROUTER_LSA
, l
->link_id
,
832 if (IS_DEBUG_OSPF_EVENT
)
833 zlog_debug ("found Router LSA %s", inet_ntoa (l
->link_id
));
836 case LSA_LINK_TYPE_TRANSIT
:
837 if (IS_DEBUG_OSPF_EVENT
)
838 zlog_debug ("Looking up Network LSA, ID: %s",
839 inet_ntoa (l
->link_id
));
840 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_NETWORK_LSA
,
843 if (IS_DEBUG_OSPF_EVENT
)
844 zlog_debug ("found the LSA");
847 zlog_warn ("Invalid LSA link type %d", type
);
853 /* In case of V is Network-LSA. */
854 r
= (struct in_addr
*) p
;
855 p
+= sizeof (struct in_addr
);
857 /* Lookup the vertex W's LSA. */
858 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_ROUTER_LSA
, *r
);
861 if (IS_DEBUG_OSPF_EVENT
)
862 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa
->data
->id
));
866 /* (b cont.) If the LSA does not exist, or its LS age is equal
867 to MaxAge, or it does not have a link back to vertex V,
868 examine the next link in V's LSA.[23] */
871 if (IS_DEBUG_OSPF_EVENT
)
872 zlog_debug ("No LSA found");
876 if (IS_LSA_MAXAGE (w_lsa
))
878 if (IS_DEBUG_OSPF_EVENT
)
879 zlog_debug ("LSA is MaxAge");
883 if (ospf_lsa_has_link (w_lsa
->data
, v
->lsa
) < 0 )
885 if (IS_DEBUG_OSPF_EVENT
)
886 zlog_debug ("The LSA doesn't have a link back");
890 /* (c) If vertex W is already on the shortest-path tree, examine
891 the next link in the LSA. */
892 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
)
894 if (IS_DEBUG_OSPF_EVENT
)
895 zlog_debug ("The LSA is already in SPF");
899 /* (d) Calculate the link state cost D of the resulting path
900 from the root to vertex W. D is equal to the sum of the link
901 state cost of the (already calculated) shortest path to
902 vertex V and the advertised cost of the link between vertices
905 /* calculate link cost D. */
906 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
907 distance
= v
->distance
+ ntohs (l
->m
[0].metric
);
908 else /* v is not a Router-LSA */
909 distance
= v
->distance
;
911 /* Is there already vertex W in candidate list? */
912 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
)
914 /* prepare vertex W. */
915 w
= ospf_vertex_new (w_lsa
);
917 /* Calculate nexthop to W. */
918 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
))
919 pqueue_enqueue (w
, candidate
);
920 else if (IS_DEBUG_OSPF_EVENT
)
921 zlog_debug ("Nexthop Calc failed");
923 else if (w_lsa
->stat
>= 0)
925 /* Get the vertex from candidates. */
926 w
= candidate
->array
[w_lsa
->stat
];
928 /* if D is greater than. */
929 if (w
->distance
< distance
)
934 else if (w
->distance
== distance
)
936 /* Found an equal-cost path to W.
937 * Calculate nexthop of to W from V. */
938 ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
);
943 /* Found a lower-cost path to W.
944 * nexthop_calculation is conditional, if it finds
945 * valid nexthop it will call spf_add_parents, which
946 * will flush the old parents
948 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
, lsa_pos
))
949 /* Decrease the key of the node in the heap.
950 * trickle-sort it up towards root, just in case this
951 * node should now be the new root due the cost change.
952 * (next pqueu_{de,en}queue will fully re-heap the queue).
954 trickle_up (w_lsa
->stat
, candidate
);
956 } /* end W is already on the candidate list */
957 } /* end loop over the links in V's LSA */
961 ospf_spf_dump (struct vertex
*v
, int i
)
963 struct listnode
*cnode
;
964 struct listnode
*nnode
;
965 struct vertex_parent
*parent
;
967 if (v
->type
== OSPF_VERTEX_ROUTER
)
969 if (IS_DEBUG_OSPF_EVENT
)
970 zlog_debug ("SPF Result: %d [R] %s", i
, inet_ntoa (v
->lsa
->id
));
974 struct network_lsa
*lsa
= (struct network_lsa
*) v
->lsa
;
975 if (IS_DEBUG_OSPF_EVENT
)
976 zlog_debug ("SPF Result: %d [N] %s/%d", i
, inet_ntoa (v
->lsa
->id
),
977 ip_masklen (lsa
->mask
));
980 if (IS_DEBUG_OSPF_EVENT
)
981 for (ALL_LIST_ELEMENTS_RO (v
->parents
, nnode
, parent
))
983 zlog_debug (" nexthop %p %s %s",
984 (void *)parent
->nexthop
,
985 inet_ntoa (parent
->nexthop
->router
),
986 parent
->nexthop
->oi
? IF_NAME(parent
->nexthop
->oi
)
992 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, v
))
993 ospf_spf_dump (v
, i
);
996 /* Second stage of SPF calculation. */
998 ospf_spf_process_stubs (struct ospf_area
*area
, struct vertex
*v
,
999 struct route_table
*rt
,
1002 struct listnode
*cnode
, *cnnode
;
1003 struct vertex
*child
;
1005 if (IS_DEBUG_OSPF_EVENT
)
1006 zlog_debug ("ospf_process_stub():processing stubs for area %s",
1007 inet_ntoa (area
->area_id
));
1008 if (v
->type
== OSPF_VERTEX_ROUTER
)
1012 struct router_lsa_link
*l
;
1013 struct router_lsa
*rlsa
;
1016 if (IS_DEBUG_OSPF_EVENT
)
1017 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
1018 inet_ntoa (v
->lsa
->id
));
1019 rlsa
= (struct router_lsa
*) v
->lsa
;
1022 if (IS_DEBUG_OSPF_EVENT
)
1023 zlog_debug ("ospf_process_stubs(): we have %d links to process",
1024 ntohs (rlsa
->links
));
1025 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1026 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
1030 l
= (struct router_lsa_link
*) p
;
1032 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
+
1033 (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1035 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1036 ospf_intra_add_stub (rt
, l
, v
, area
, parent_is_root
, lsa_pos
);
1041 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1, 1);
1043 for (ALL_LIST_ELEMENTS (v
->children
, cnode
, cnnode
, child
))
1045 if (CHECK_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
))
1048 /* the first level of routers connected to the root
1049 * should have 'parent_is_root' set, including those
1050 * connected via a network vertex.
1054 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1057 ospf_spf_process_stubs (area
, child
, rt
, parent_is_root
);
1059 SET_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
);
1064 ospf_rtrs_free (struct route_table
*rtrs
)
1066 struct route_node
*rn
;
1067 struct list
*or_list
;
1068 struct ospf_route
*or;
1069 struct listnode
*node
, *nnode
;
1071 if (IS_DEBUG_OSPF_EVENT
)
1072 zlog_debug ("Route: Router Routing Table free");
1074 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1075 if ((or_list
= rn
->info
) != NULL
)
1077 for (ALL_LIST_ELEMENTS (or_list
, node
, nnode
, or))
1078 ospf_route_free (or);
1080 list_delete (or_list
);
1082 /* Unlock the node. */
1084 route_unlock_node (rn
);
1086 route_table_finish (rtrs
);
1091 ospf_rtrs_print (struct route_table
*rtrs
)
1093 struct route_node
*rn
;
1094 struct list
*or_list
;
1095 struct listnode
*ln
;
1096 struct listnode
*pnode
;
1097 struct ospf_route
*or;
1098 struct ospf_path
*path
;
1102 if (IS_DEBUG_OSPF_EVENT
)
1103 zlog_debug ("ospf_rtrs_print() start");
1105 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1106 if ((or_list
= rn
->info
) != NULL
)
1107 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1109 switch (or->path_type
)
1111 case OSPF_PATH_INTRA_AREA
:
1112 if (IS_DEBUG_OSPF_EVENT
)
1113 zlog_debug ("%s [%d] area: %s",
1114 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1115 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1118 case OSPF_PATH_INTER_AREA
:
1119 if (IS_DEBUG_OSPF_EVENT
)
1120 zlog_debug ("%s IA [%d] area: %s",
1121 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1122 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1129 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1131 if (path
->nexthop
.s_addr
== 0)
1133 if (IS_DEBUG_OSPF_EVENT
)
1134 zlog_debug (" directly attached to %s\r\n",
1135 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1139 if (IS_DEBUG_OSPF_EVENT
)
1140 zlog_debug (" via %s, %s\r\n",
1141 inet_ntoa (path
->nexthop
),
1142 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1147 zlog_debug ("ospf_rtrs_print() end");
1151 /* Calculating the shortest-path tree for an area. */
1153 ospf_spf_calculate (struct ospf_area
*area
, struct route_table
*new_table
,
1154 struct route_table
*new_rtrs
)
1156 struct pqueue
*candidate
;
1159 if (IS_DEBUG_OSPF_EVENT
)
1161 zlog_debug ("ospf_spf_calculate: Start");
1162 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1163 inet_ntoa (area
->area_id
));
1166 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1167 return this area's calculation. */
1168 if (!area
->router_lsa_self
)
1170 if (IS_DEBUG_OSPF_EVENT
)
1171 zlog_debug ("ospf_spf_calculate: "
1172 "Skip area %s's calculation due to empty router_lsa_self",
1173 inet_ntoa (area
->area_id
));
1177 /* RFC2328 16.1. (1). */
1178 /* Initialize the algorithm's data structures. */
1180 /* This function scans all the LSA database and set the stat field to
1181 * LSA_SPF_NOT_EXPLORED. */
1182 ospf_lsdb_clean_stat (area
->lsdb
);
1183 /* Create a new heap for the candidates. */
1184 candidate
= pqueue_create();
1185 candidate
->cmp
= cmp
;
1186 candidate
->update
= update_stat
;
1188 /* Initialize the shortest-path tree to only the root (which is the
1189 router doing the calculation). */
1190 ospf_spf_init (area
);
1192 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1194 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1196 /* Set Area A's TransitCapability to FALSE. */
1197 area
->transit
= OSPF_TRANSIT_FALSE
;
1198 area
->shortcut_capability
= 1;
1202 /* RFC2328 16.1. (2). */
1203 ospf_spf_next (v
, area
, candidate
);
1205 /* RFC2328 16.1. (3). */
1206 /* If at this step the candidate list is empty, the shortest-
1207 path tree (of transit vertices) has been completely built and
1208 this stage of the procedure terminates. */
1209 if (candidate
->size
== 0)
1212 /* Otherwise, choose the vertex belonging to the candidate list
1213 that is closest to the root, and add it to the shortest-path
1214 tree (removing it from the candidate list in the
1216 /* Extract from the candidates the node with the lower key. */
1217 v
= (struct vertex
*) pqueue_dequeue (candidate
);
1218 /* Update stat field in vertex. */
1219 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1221 ospf_vertex_add_parent (v
);
1223 /* RFC2328 16.1. (4). */
1224 if (v
->type
== OSPF_VERTEX_ROUTER
)
1225 ospf_intra_add_router (new_rtrs
, v
, area
);
1227 ospf_intra_add_transit (new_table
, v
, area
);
1229 /* RFC2328 16.1. (5). */
1230 /* Iterate the algorithm by returning to Step 2. */
1232 } /* end loop until no more candidate vertices */
1234 if (IS_DEBUG_OSPF_EVENT
)
1236 ospf_spf_dump (area
->spf
, 0);
1237 ospf_route_table_dump (new_table
);
1240 /* Second stage of SPF calculation procedure's */
1241 ospf_spf_process_stubs (area
, area
->spf
, new_table
, 0);
1243 /* Free candidate queue. */
1244 pqueue_delete (candidate
);
1246 ospf_vertex_dump (__func__
, area
->spf
, 0, 1);
1247 /* Free nexthop information, canonical versions of which are attached
1248 * the first level of router vertices attached to the root vertex, see
1249 * ospf_nexthop_calculation.
1251 ospf_canonical_nexthops_free (area
->spf
);
1253 /* Increment SPF Calculation Counter. */
1254 area
->spf_calculation
++;
1256 monotime(&area
->ospf
->ts_spf
);
1257 area
->ts_spf
= area
->ospf
->ts_spf
;
1259 if (IS_DEBUG_OSPF_EVENT
)
1260 zlog_debug ("ospf_spf_calculate: Stop. %zd vertices",
1261 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1263 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1266 list_delete_all_node (&vertex_list
);
1269 /* Timer for SPF calculation. */
1271 ospf_spf_calculate_timer (struct thread
*thread
)
1273 struct ospf
*ospf
= THREAD_ARG (thread
);
1274 struct route_table
*new_table
, *new_rtrs
;
1275 struct ospf_area
*area
;
1276 struct listnode
*node
, *nnode
;
1277 struct timeval start_time
, spf_start_time
;
1278 int areas_processed
= 0;
1279 unsigned long ia_time
, prune_time
, rt_time
;
1280 unsigned long abr_time
, total_spf_time
, spf_time
;
1281 char rbuf
[32]; /* reason_buf */
1283 if (IS_DEBUG_OSPF_EVENT
)
1284 zlog_debug ("SPF: Timer (SPF calculation expire)");
1286 ospf
->t_spf_calc
= NULL
;
1288 monotime(&spf_start_time
);
1289 /* Allocate new table tree. */
1290 new_table
= route_table_init ();
1291 new_rtrs
= route_table_init ();
1293 ospf_vl_unapprove (ospf
);
1295 /* Calculate SPF for each area. */
1296 for (ALL_LIST_ELEMENTS (ospf
->areas
, node
, nnode
, area
))
1298 /* Do backbone last, so as to first discover intra-area paths
1299 * for any back-bone virtual-links
1301 if (ospf
->backbone
&& ospf
->backbone
== area
)
1304 ospf_spf_calculate (area
, new_table
, new_rtrs
);
1308 /* SPF for backbone, if required */
1311 ospf_spf_calculate (ospf
->backbone
, new_table
, new_rtrs
);
1315 spf_time
= monotime_since(&spf_start_time
, NULL
);
1317 ospf_vl_shut_unapproved (ospf
);
1319 monotime(&start_time
);
1320 ospf_ia_routing (ospf
, new_table
, new_rtrs
);
1321 ia_time
= monotime_since(&start_time
, NULL
);
1323 monotime(&start_time
);
1324 ospf_prune_unreachable_networks (new_table
);
1325 ospf_prune_unreachable_routers (new_rtrs
);
1326 prune_time
= monotime_since(&start_time
, NULL
);
1328 /* AS-external-LSA calculation should not be performed here. */
1330 /* If new Router Route is installed,
1331 then schedule re-calculate External routes. */
1333 ospf_ase_calculate_schedule (ospf
);
1335 ospf_ase_calculate_timer_add (ospf
);
1337 /* Update routing table. */
1338 monotime(&start_time
);
1339 ospf_route_install (ospf
, new_table
);
1340 rt_time
= monotime_since(&start_time
, NULL
);
1342 /* Update ABR/ASBR routing table */
1345 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1346 /* ospf_route_delete (ospf->old_rtrs); */
1347 ospf_rtrs_free (ospf
->old_rtrs
);
1350 ospf
->old_rtrs
= ospf
->new_rtrs
;
1351 ospf
->new_rtrs
= new_rtrs
;
1353 monotime(&start_time
);
1354 if (IS_OSPF_ABR (ospf
))
1355 ospf_abr_task (ospf
);
1356 abr_time
= monotime_since(&start_time
, NULL
);
1358 total_spf_time
= monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1361 if (spf_reason_flags
)
1363 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1364 strncat (rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1365 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1366 strncat (rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1367 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1368 strncat (rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1369 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1370 strncat (rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1371 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1372 strncat (rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1373 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1374 strncat (rbuf
, "ASBR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1375 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1376 strncat (rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1378 size_t rbuflen
= strlen(rbuf
);
1380 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1385 if (IS_DEBUG_OSPF_EVENT
)
1387 zlog_info ("SPF Processing Time(usecs): %ld", total_spf_time
);
1388 zlog_info ("\t SPF Time: %ld", spf_time
);
1389 zlog_info ("\t InterArea: %ld", ia_time
);
1390 zlog_info ("\t Prune: %ld", prune_time
);
1391 zlog_info ("\tRouteInstall: %ld", rt_time
);
1392 if (IS_OSPF_ABR (ospf
))
1393 zlog_info ("\t ABR: %ld (%d areas)",
1394 abr_time
, areas_processed
);
1395 zlog_info ("Reason(s) for SPF: %s", rbuf
);
1398 ospf_clear_spf_reason_flags ();
1403 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1404 set timer for SPF calc. */
1406 ospf_spf_calculate_schedule (struct ospf
*ospf
, ospf_spf_reason_t reason
)
1408 unsigned long delay
, elapsed
, ht
;
1410 if (IS_DEBUG_OSPF_EVENT
)
1411 zlog_debug ("SPF: calculation timer scheduled");
1413 /* OSPF instance does not exist. */
1417 ospf_spf_set_reason (reason
);
1419 /* SPF calculation timer is already scheduled. */
1420 if (ospf
->t_spf_calc
)
1422 if (IS_DEBUG_OSPF_EVENT
)
1423 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1424 (void *)ospf
->t_spf_calc
);
1428 elapsed
= monotime_since (&ospf
->ts_spf
, NULL
) / 1000;
1430 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1432 if (ht
> ospf
->spf_max_holdtime
)
1433 ht
= ospf
->spf_max_holdtime
;
1435 /* Get SPF calculation delay time. */
1438 /* Got an event within the hold time of last SPF. We need to
1439 * increase the hold_multiplier, if it's not already at/past
1440 * maximum value, and wasn't already increased..
1442 if (ht
< ospf
->spf_max_holdtime
)
1443 ospf
->spf_hold_multiplier
++;
1445 /* always honour the SPF initial delay */
1446 if ( (ht
- elapsed
) < ospf
->spf_delay
)
1447 delay
= ospf
->spf_delay
;
1449 delay
= ht
- elapsed
;
1453 /* Event is past required hold-time of last SPF */
1454 delay
= ospf
->spf_delay
;
1455 ospf
->spf_hold_multiplier
= 1;
1458 if (IS_DEBUG_OSPF_EVENT
)
1459 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
1461 zlog_info ("SPF: Scheduled in %ld msec", delay
);
1463 ospf
->t_spf_calc
= NULL
;
1464 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,