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
17 along with GNU Zebra; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
31 #include "sockunion.h" /* for inet_ntop () */
34 #include "ospfd/ospfd.h"
35 #include "ospfd/ospf_interface.h"
36 #include "ospfd/ospf_ism.h"
37 #include "ospfd/ospf_asbr.h"
38 #include "ospfd/ospf_lsa.h"
39 #include "ospfd/ospf_lsdb.h"
40 #include "ospfd/ospf_neighbor.h"
41 #include "ospfd/ospf_nsm.h"
42 #include "ospfd/ospf_spf.h"
43 #include "ospfd/ospf_route.h"
44 #include "ospfd/ospf_ia.h"
45 #include "ospfd/ospf_ase.h"
46 #include "ospfd/ospf_abr.h"
47 #include "ospfd/ospf_dump.h"
49 static void ospf_vertex_free (void *);
50 /* List of allocated vertices, to simplify cleanup of SPF.
51 * Not thread-safe obviously. If it ever needs to be, it'd have to be
52 * dynamically allocated at begin of ospf_spf_calculate
54 static struct list vertex_list
= { .del
= ospf_vertex_free
};
56 /* Heap related functions, for the managment of the candidates, to
57 * be used with pqueue. */
59 cmp (void * node1
, void * node2
)
61 struct vertex
* v1
= (struct vertex
*) node1
;
62 struct vertex
* v2
= (struct vertex
*) node2
;
63 if (v1
!= NULL
&& v2
!= NULL
)
65 /* network vertices must be chosen before router vertices of same
66 * cost in order to find all shortest paths
68 if ( ((v1
->distance
- v2
->distance
) == 0)
69 && (v1
->type
!= v2
->type
))
73 case OSPF_VERTEX_NETWORK
:
75 case OSPF_VERTEX_ROUTER
:
80 return (v1
->distance
- v2
->distance
);
86 update_stat (void *node
, int position
)
88 struct vertex
*v
= node
;
90 /* Set the status of the vertex, when its position changes. */
91 *(v
->stat
) = position
;
94 static struct vertex_nexthop
*
95 vertex_nexthop_new (void)
97 return XCALLOC (MTYPE_OSPF_NEXTHOP
, sizeof (struct vertex_nexthop
));
101 vertex_nexthop_free (struct vertex_nexthop
*nh
)
103 XFREE (MTYPE_OSPF_NEXTHOP
, nh
);
106 /* Free the canonical nexthop objects for an area, ie the nexthop objects
107 * attached to the first-hop router vertices, and any intervening network
111 ospf_canonical_nexthops_free (struct vertex
*root
)
113 struct listnode
*node
, *nnode
;
114 struct vertex
*child
;
116 for (ALL_LIST_ELEMENTS (root
->children
, node
, nnode
, child
))
118 struct listnode
*n2
, *nn2
;
119 struct vertex_parent
*vp
;
121 /* router vertices through an attached network each
122 * have a distinct (canonical / not inherited) nexthop
123 * which must be freed.
125 * A network vertex can only have router vertices as its
126 * children, so only one level of recursion is possible.
128 if (child
->type
== OSPF_VERTEX_NETWORK
)
129 ospf_canonical_nexthops_free (child
);
131 /* Free child nexthops pointing back to this root vertex */
132 for (ALL_LIST_ELEMENTS (child
->parents
, n2
, nn2
, vp
))
133 if (vp
->parent
== root
&& vp
->nexthop
)
134 vertex_nexthop_free (vp
->nexthop
);
138 /* TODO: Parent list should be excised, in favour of maintaining only
139 * vertex_nexthop, with refcounts.
141 static struct vertex_parent
*
142 vertex_parent_new (struct vertex
*v
, int backlink
, struct vertex_nexthop
*hop
)
144 struct vertex_parent
*new;
146 new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT
, sizeof (struct vertex_parent
));
152 new->backlink
= backlink
;
158 vertex_parent_free (void *p
)
160 XFREE (MTYPE_OSPF_VERTEX_PARENT
, p
);
163 static struct vertex
*
164 ospf_vertex_new (struct ospf_lsa
*lsa
)
168 new = XCALLOC (MTYPE_OSPF_VERTEX
, sizeof (struct vertex
));
171 new->stat
= &(lsa
->stat
);
172 new->type
= lsa
->data
->type
;
173 new->id
= lsa
->data
->id
;
174 new->lsa
= lsa
->data
;
175 new->children
= list_new ();
176 new->parents
= list_new ();
177 new->parents
->del
= vertex_parent_free
;
179 listnode_add (&vertex_list
, new);
181 if (IS_DEBUG_OSPF_EVENT
)
182 zlog_debug ("%s: Created %s vertex %s", __func__
,
183 new->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
184 inet_ntoa (new->lsa
->id
));
189 ospf_vertex_free (void *data
)
191 struct vertex
*v
= data
;
193 if (IS_DEBUG_OSPF_EVENT
)
194 zlog_debug ("%s: Free %s vertex %s", __func__
,
195 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
196 inet_ntoa (v
->lsa
->id
));
198 /* There should be no parents potentially holding references to this vertex
199 * Children however may still be there, but presumably referenced by other
202 //assert (listcount (v->parents) == 0);
205 list_delete (v
->children
);
209 list_delete (v
->parents
);
214 XFREE (MTYPE_OSPF_VERTEX
, v
);
218 ospf_vertex_dump(const char *msg
, struct vertex
*v
,
219 int print_parents
, int print_children
)
221 if ( ! IS_DEBUG_OSPF_EVENT
)
224 zlog_debug("%s %s vertex %s distance %u flags %u",
226 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
227 inet_ntoa(v
->lsa
->id
),
229 (unsigned int)v
->flags
);
233 struct listnode
*node
;
234 struct vertex_parent
*vp
;
236 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
242 zlog_debug ("parent %s backlink %d nexthop %s interface %s",
243 inet_ntoa(vp
->parent
->lsa
->id
), vp
->backlink
,
244 inet_ntop(AF_INET
, &vp
->nexthop
->router
, buf1
, BUFSIZ
),
245 vp
->nexthop
->oi
? IF_NAME(vp
->nexthop
->oi
) : "NULL");
252 struct listnode
*cnode
;
255 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, cv
))
256 ospf_vertex_dump(" child:", cv
, 0, 0);
261 /* Add a vertex to the list of children in each of its parents. */
263 ospf_vertex_add_parent (struct vertex
*v
)
265 struct vertex_parent
*vp
;
266 struct listnode
*node
;
268 assert (v
&& v
->parents
);
270 for (ALL_LIST_ELEMENTS_RO (v
->parents
, node
, vp
))
272 assert (vp
->parent
&& vp
->parent
->children
);
274 /* No need to add two links from the same parent. */
275 if (listnode_lookup (vp
->parent
->children
, v
) == NULL
)
276 listnode_add (vp
->parent
->children
, v
);
281 ospf_spf_init (struct ospf_area
*area
)
285 /* Create root node. */
286 v
= ospf_vertex_new (area
->router_lsa_self
);
290 /* Reset ABR and ASBR router counts. */
292 area
->asbr_count
= 0;
295 /* return index of link back to V from W, or -1 if no link found */
297 ospf_lsa_has_link (struct lsa_header
*w
, struct lsa_header
*v
)
299 unsigned int i
, length
;
300 struct router_lsa
*rl
;
301 struct network_lsa
*nl
;
303 /* In case of W is Network LSA. */
304 if (w
->type
== OSPF_NETWORK_LSA
)
306 if (v
->type
== OSPF_NETWORK_LSA
)
309 nl
= (struct network_lsa
*) w
;
310 length
= (ntohs (w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
312 for (i
= 0; i
< length
; i
++)
313 if (IPV4_ADDR_SAME (&nl
->routers
[i
], &v
->id
))
318 /* In case of W is Router LSA. */
319 if (w
->type
== OSPF_ROUTER_LSA
)
321 rl
= (struct router_lsa
*) w
;
323 length
= ntohs (w
->length
);
326 i
< ntohs (rl
->links
) && length
>= sizeof (struct router_lsa
);
329 switch (rl
->link
[i
].type
)
331 case LSA_LINK_TYPE_POINTOPOINT
:
332 case LSA_LINK_TYPE_VIRTUALLINK
:
334 if (v
->type
== OSPF_ROUTER_LSA
&&
335 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
340 case LSA_LINK_TYPE_TRANSIT
:
341 /* Network LSA ID. */
342 if (v
->type
== OSPF_NETWORK_LSA
&&
343 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
348 case LSA_LINK_TYPE_STUB
:
349 /* Stub can't lead anywhere, carry on */
359 #define ROUTER_LSA_MIN_SIZE 12
360 #define ROUTER_LSA_TOS_SIZE 4
362 /* Find the next link after prev_link from v to w. If prev_link is
363 * NULL, return the first link from v to w. Ignore stub and virtual links;
364 * these link types will never be returned.
366 static struct router_lsa_link
*
367 ospf_get_next_link (struct vertex
*v
, struct vertex
*w
,
368 struct router_lsa_link
*prev_link
)
372 u_char lsa_type
= LSA_LINK_TYPE_TRANSIT
;
373 struct router_lsa_link
*l
;
375 if (w
->type
== OSPF_VERTEX_ROUTER
)
376 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
378 if (prev_link
== NULL
)
379 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
382 p
= (u_char
*) prev_link
;
383 p
+= (ROUTER_LSA_MIN_SIZE
+
384 (prev_link
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
387 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
391 l
= (struct router_lsa_link
*) p
;
393 p
+= (ROUTER_LSA_MIN_SIZE
+ (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
395 if (l
->m
[0].type
!= lsa_type
)
398 if (IPV4_ADDR_SAME (&l
->link_id
, &w
->id
))
406 ospf_spf_flush_parents (struct vertex
*w
)
408 struct vertex_parent
*vp
;
409 struct listnode
*ln
, *nn
;
411 /* delete the existing nexthops */
412 for (ALL_LIST_ELEMENTS (w
->parents
, ln
, nn
, vp
))
414 list_delete_node (w
->parents
, ln
);
415 vertex_parent_free (vp
);
420 * Consider supplied next-hop for inclusion to the supplied list of
421 * equal-cost next-hops, adjust list as neccessary.
424 ospf_spf_add_parent (struct vertex
*v
, struct vertex
*w
,
425 struct vertex_nexthop
*newhop
,
426 unsigned int distance
)
428 struct vertex_parent
*vp
;
430 /* we must have a newhop, and a distance */
431 assert (v
&& w
&& newhop
);
434 /* IFF w has already been assigned a distance, then we shouldn't get here
435 * unless callers have determined V(l)->W is shortest / equal-shortest
436 * path (0 is a special case distance (no distance yet assigned)).
439 assert (distance
<= w
->distance
);
441 w
->distance
= distance
;
443 if (IS_DEBUG_OSPF_EVENT
)
445 char buf
[2][INET_ADDRSTRLEN
];
446 zlog_debug ("%s: Adding %s as parent of %s",
448 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
449 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1], sizeof(buf
[1])));
452 /* Adding parent for a new, better path: flush existing parents from W. */
453 if (distance
< w
->distance
)
455 if (IS_DEBUG_OSPF_EVENT
)
456 zlog_debug ("%s: distance %d better than %d, flushing existing parents",
457 __func__
, distance
, w
->distance
);
458 ospf_spf_flush_parents (w
);
459 w
->distance
= distance
;
462 /* new parent is <= existing parents, add it to parent list */
463 vp
= vertex_parent_new (v
, ospf_lsa_has_link (w
->lsa
, v
->lsa
), newhop
);
464 listnode_add (w
->parents
, vp
);
469 /* 16.1.1. Calculate nexthop from root through V (parent) to
470 * vertex W (destination), with given distance from root->W.
472 * The link must be supplied if V is the root vertex. In all other cases
475 * Note that this function may fail, hence the state of the destination
476 * vertex, W, should /not/ be modified in a dependent manner until
477 * this function returns. This function will update the W vertex with the
478 * provided distance as appropriate.
481 ospf_nexthop_calculation (struct ospf_area
*area
, struct vertex
*v
,
482 struct vertex
*w
, struct router_lsa_link
*l
,
483 unsigned int distance
)
485 struct listnode
*node
, *nnode
;
486 struct vertex_nexthop
*nh
;
487 struct vertex_parent
*vp
;
488 struct ospf_interface
*oi
= NULL
;
489 unsigned int added
= 0;
491 if (IS_DEBUG_OSPF_EVENT
)
493 zlog_debug ("ospf_nexthop_calculation(): Start");
494 ospf_vertex_dump("V (parent):", v
, 1, 1);
495 ospf_vertex_dump("W (dest) :", w
, 1, 1);
496 zlog_debug ("V->W distance: %d", distance
);
501 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
502 root (the calculating router itself). This means that the
503 destination is either a directly connected network or directly
504 connected router. The outgoing interface in this case is simply
505 the OSPF interface connecting to the destination network/router.
508 if (w
->type
== OSPF_VERTEX_ROUTER
)
510 /* l is a link from v to w
511 * l2 will be link from w to v
513 struct router_lsa_link
*l2
= NULL
;
515 /* we *must* be supplied with the link data */
518 if (IS_DEBUG_OSPF_EVENT
)
523 zlog_debug("ospf_nexthop_calculation(): considering link "
524 "type %d link_id %s link_data %s",
526 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
527 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
530 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
)
532 /* If the destination is a router which connects to
533 the calculating router via a Point-to-MultiPoint
534 network, the destination's next hop IP address(es)
535 can be determined by examining the destination's
536 router-LSA: each link pointing back to the
537 calculating router and having a Link Data field
538 belonging to the Point-to-MultiPoint network
539 provides an IP address of the next hop router.
541 At this point l is a link from V to W, and V is the
542 root ("us"). Find the local interface associated
543 with l (its address is in l->link_data). If it
544 is a point-to-multipoint interface, then look through
545 the links in the opposite direction (W to V). If
546 any of them have an address that lands within the
547 subnet declared by the PtMP link, then that link
548 is a constituent of the PtMP link, and its address is
549 a nexthop address for V.
551 oi
= ospf_if_is_configured (area
->ospf
, &l
->link_data
);
552 if (oi
&& oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
)
554 struct prefix_ipv4 la
;
557 la
.prefixlen
= oi
->address
->prefixlen
;
559 /* V links to W on PtMP interface
560 - find the interface address on W */
561 while ((l2
= ospf_get_next_link (w
, v
, l2
)))
563 la
.prefix
= l2
->link_data
;
565 if (prefix_cmp ((struct prefix
*) &la
,
567 /* link_data is on our PtMP network */
570 } /* end l is on point-to-multipoint link */
573 /* l is a regular point-to-point link.
574 Look for a link from W to V.
576 while ((l2
= ospf_get_next_link (w
, v
, l2
)))
578 oi
= ospf_if_is_configured (area
->ospf
,
584 if (!IPV4_ADDR_SAME (&oi
->address
->u
.prefix4
,
594 /* found all necessary info to build nexthop */
595 nh
= vertex_nexthop_new ();
597 nh
->router
= l2
->link_data
;
598 ospf_spf_add_parent (v
, w
, nh
, distance
);
602 zlog_info("ospf_nexthop_calculation(): "
603 "could not determine nexthop for link");
604 } /* end point-to-point link from V to W */
605 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
)
607 struct ospf_vl_data
*vl_data
;
609 /* VLink implementation limitations:
610 * a) vl_data can only reference one nexthop, so no ECMP
611 * to backbone through VLinks. Though transit-area
612 * summaries may be considered, and those can be ECMP.
613 * b) We can only use /one/ VLink, even if multiple ones
614 * exist this router through multiple transit-areas.
616 vl_data
= ospf_vl_lookup (area
->ospf
, NULL
, l
->link_id
);
619 && CHECK_FLAG (vl_data
->flags
, OSPF_VL_FLAG_APPROVED
))
621 nh
= vertex_nexthop_new ();
622 nh
->oi
= vl_data
->nexthop
.oi
;
623 nh
->router
= vl_data
->nexthop
.router
;
624 ospf_spf_add_parent (v
, w
, nh
, distance
);
628 zlog_info("ospf_nexthop_calculation(): "
629 "vl_data for VL link not found");
630 } /* end virtual-link from V to W */
632 } /* end W is a Router vertex */
635 assert(w
->type
== OSPF_VERTEX_NETWORK
);
636 oi
= ospf_if_is_configured (area
->ospf
, &(l
->link_data
));
639 nh
= vertex_nexthop_new ();
641 nh
->router
.s_addr
= 0;
642 ospf_spf_add_parent (v
, w
, nh
, distance
);
646 zlog_info("ospf_nexthop_calculation(): "
647 "Unknown attached link");
649 } /* end V is the root */
650 /* Check if W's parent is a network connected to root. */
651 else if (v
->type
== OSPF_VERTEX_NETWORK
)
653 /* See if any of V's parents are the root. */
654 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
656 if (vp
->parent
== area
->spf
) /* connects to root? */
658 /* 16.1.1 para 5. ...the parent vertex is a network that
659 * directly connects the calculating router to the destination
660 * router. The list of next hops is then determined by
661 * examining the destination's router-LSA...
664 assert(w
->type
== OSPF_VERTEX_ROUTER
);
665 while ((l
= ospf_get_next_link (w
, v
, l
)))
667 /* ...For each link in the router-LSA that points back to the
668 * parent network, the link's Link Data field provides the IP
669 * address of a next hop router. The outgoing interface to
670 * use can then be derived from the next hop IP address (or
671 * it can be inherited from the parent network).
673 nh
= vertex_nexthop_new ();
674 nh
->oi
= vp
->nexthop
->oi
;
675 nh
->router
= l
->link_data
;
677 ospf_spf_add_parent (v
, w
, nh
, distance
);
681 /* NB: This code is non-trivial.
683 * E.g. it is not enough to know that V connects to the root. It is
684 * also important that the while above, looping through all links from
685 * W->V found at least one link, so that we know there is
686 * bi-directional connectivity between V and W. Otherwise, if we
687 * /always/ return here, but don't check that W->V exists then we
688 * we will prevent SPF from finding/using higher cost paths..
690 * See also bug #330, and also:
692 * http://blogs.sun.com/paulj/entry/the_difference_a_line_makes
698 /* 16.1.1 para 4. If there is at least one intervening router in the
699 * current shortest path between the destination and the root, the
700 * destination simply inherits the set of next hops from the
703 if (IS_DEBUG_OSPF_EVENT
)
704 zlog_debug ("%s: Intervening routers, adding parent(s)", __func__
);
706 for (ALL_LIST_ELEMENTS (v
->parents
, node
, nnode
, vp
))
709 ospf_spf_add_parent (v
, w
, vp
->nexthop
, distance
);
715 /* RFC2328 Section 16.1 (2).
716 * v is on the SPF tree. Examine the links in v's LSA. Update the list
717 * of candidates with any vertices not already on the list. If a lower-cost
718 * path is found to a vertex already on the candidate list, store the new cost.
721 ospf_spf_next (struct vertex
*v
, struct ospf_area
*area
,
722 struct pqueue
* candidate
)
724 struct ospf_lsa
*w_lsa
= NULL
;
727 struct router_lsa_link
*l
= NULL
;
731 /* If this is a router-LSA, and bit V of the router-LSA (see Section
732 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
733 if (v
->type
== OSPF_VERTEX_ROUTER
)
735 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa
*) v
->lsa
))
736 area
->transit
= OSPF_TRANSIT_TRUE
;
739 if (IS_DEBUG_OSPF_EVENT
)
740 zlog_debug ("%s: Next vertex of %s vertex %s",
742 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
743 inet_ntoa(v
->lsa
->id
));
745 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
746 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
751 unsigned int distance
;
753 /* In case of V is Router-LSA. */
754 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
756 l
= (struct router_lsa_link
*) p
;
758 p
+= (ROUTER_LSA_MIN_SIZE
+
759 (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
761 /* (a) If this is a link to a stub network, examine the next
762 link in V's LSA. Links to stub networks will be
763 considered in the second stage of the shortest path
765 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
768 /* Infinite distance links shouldn't be followed, except
769 * for local links (a stub-routed router still wants to
770 * calculate tree, so must follow its own links).
772 if ((v
!= area
->spf
) && l
->m
[0].metric
>= OSPF_OUTPUT_COST_INFINITE
)
775 /* (b) Otherwise, W is a transit vertex (router or transit
776 network). Look up the vertex W's LSA (router-LSA or
777 network-LSA) in Area A's link state database. */
780 case LSA_LINK_TYPE_POINTOPOINT
:
781 case LSA_LINK_TYPE_VIRTUALLINK
:
782 if (type
== LSA_LINK_TYPE_VIRTUALLINK
)
784 if (IS_DEBUG_OSPF_EVENT
)
785 zlog_debug ("looking up LSA through VL: %s",
786 inet_ntoa (l
->link_id
));
789 w_lsa
= ospf_lsa_lookup (area
, OSPF_ROUTER_LSA
, l
->link_id
,
793 if (IS_DEBUG_OSPF_EVENT
)
794 zlog_debug ("found Router LSA %s", inet_ntoa (l
->link_id
));
797 case LSA_LINK_TYPE_TRANSIT
:
798 if (IS_DEBUG_OSPF_EVENT
)
799 zlog_debug ("Looking up Network LSA, ID: %s",
800 inet_ntoa (l
->link_id
));
801 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_NETWORK_LSA
,
804 if (IS_DEBUG_OSPF_EVENT
)
805 zlog_debug ("found the LSA");
808 zlog_warn ("Invalid LSA link type %d", type
);
814 /* In case of V is Network-LSA. */
815 r
= (struct in_addr
*) p
;
816 p
+= sizeof (struct in_addr
);
818 /* Lookup the vertex W's LSA. */
819 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_ROUTER_LSA
, *r
);
822 if (IS_DEBUG_OSPF_EVENT
)
823 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa
->data
->id
));
827 /* (b cont.) If the LSA does not exist, or its LS age is equal
828 to MaxAge, or it does not have a link back to vertex V,
829 examine the next link in V's LSA.[23] */
832 if (IS_DEBUG_OSPF_EVENT
)
833 zlog_debug ("No LSA found");
837 if (IS_LSA_MAXAGE (w_lsa
))
839 if (IS_DEBUG_OSPF_EVENT
)
840 zlog_debug ("LSA is MaxAge");
844 if (ospf_lsa_has_link (w_lsa
->data
, v
->lsa
) < 0 )
846 if (IS_DEBUG_OSPF_EVENT
)
847 zlog_debug ("The LSA doesn't have a link back");
851 /* (c) If vertex W is already on the shortest-path tree, examine
852 the next link in the LSA. */
853 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
)
855 if (IS_DEBUG_OSPF_EVENT
)
856 zlog_debug ("The LSA is already in SPF");
860 /* (d) Calculate the link state cost D of the resulting path
861 from the root to vertex W. D is equal to the sum of the link
862 state cost of the (already calculated) shortest path to
863 vertex V and the advertised cost of the link between vertices
866 /* calculate link cost D. */
867 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
868 distance
= v
->distance
+ ntohs (l
->m
[0].metric
);
869 else /* v is not a Router-LSA */
870 distance
= v
->distance
;
872 /* Is there already vertex W in candidate list? */
873 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
)
875 /* prepare vertex W. */
876 w
= ospf_vertex_new (w_lsa
);
878 /* Calculate nexthop to W. */
879 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
))
880 pqueue_enqueue (w
, candidate
);
881 else if (IS_DEBUG_OSPF_EVENT
)
882 zlog_debug ("Nexthop Calc failed");
884 else if (w_lsa
->stat
>= 0)
886 /* Get the vertex from candidates. */
887 w
= candidate
->array
[w_lsa
->stat
];
889 /* if D is greater than. */
890 if (w
->distance
< distance
)
895 else if (w
->distance
== distance
)
897 /* Found an equal-cost path to W.
898 * Calculate nexthop of to W from V. */
899 ospf_nexthop_calculation (area
, v
, w
, l
, distance
);
904 /* Found a lower-cost path to W.
905 * nexthop_calculation is conditional, if it finds
906 * valid nexthop it will call spf_add_parents, which
907 * will flush the old parents
909 if (ospf_nexthop_calculation (area
, v
, w
, l
, distance
))
910 /* Decrease the key of the node in the heap.
911 * trickle-sort it up towards root, just in case this
912 * node should now be the new root due the cost change.
913 * (next pqueu_{de,en}queue will fully re-heap the queue).
915 trickle_up (w_lsa
->stat
, candidate
);
917 } /* end W is already on the candidate list */
918 } /* end loop over the links in V's LSA */
922 ospf_spf_dump (struct vertex
*v
, int i
)
924 struct listnode
*cnode
;
925 struct listnode
*nnode
;
926 struct vertex_parent
*parent
;
928 if (v
->type
== OSPF_VERTEX_ROUTER
)
930 if (IS_DEBUG_OSPF_EVENT
)
931 zlog_debug ("SPF Result: %d [R] %s", i
, inet_ntoa (v
->lsa
->id
));
935 struct network_lsa
*lsa
= (struct network_lsa
*) v
->lsa
;
936 if (IS_DEBUG_OSPF_EVENT
)
937 zlog_debug ("SPF Result: %d [N] %s/%d", i
, inet_ntoa (v
->lsa
->id
),
938 ip_masklen (lsa
->mask
));
941 if (IS_DEBUG_OSPF_EVENT
)
942 for (ALL_LIST_ELEMENTS_RO (v
->parents
, nnode
, parent
))
944 zlog_debug (" nexthop %p %s %s",
946 inet_ntoa (parent
->nexthop
->router
),
947 parent
->nexthop
->oi
? IF_NAME(parent
->nexthop
->oi
)
953 for (ALL_LIST_ELEMENTS_RO (v
->children
, cnode
, v
))
954 ospf_spf_dump (v
, i
);
957 /* Second stage of SPF calculation. */
959 ospf_spf_process_stubs (struct ospf_area
*area
, struct vertex
*v
,
960 struct route_table
*rt
,
963 struct listnode
*cnode
, *cnnode
;
964 struct vertex
*child
;
966 if (IS_DEBUG_OSPF_EVENT
)
967 zlog_debug ("ospf_process_stub():processing stubs for area %s",
968 inet_ntoa (area
->area_id
));
969 if (v
->type
== OSPF_VERTEX_ROUTER
)
973 struct router_lsa_link
*l
;
974 struct router_lsa
*rlsa
;
976 if (IS_DEBUG_OSPF_EVENT
)
977 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
978 inet_ntoa (v
->lsa
->id
));
979 rlsa
= (struct router_lsa
*) v
->lsa
;
982 if (IS_DEBUG_OSPF_EVENT
)
983 zlog_debug ("ospf_process_stubs(): we have %d links to process",
984 ntohs (rlsa
->links
));
985 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
986 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
990 l
= (struct router_lsa_link
*) p
;
992 p
+= (ROUTER_LSA_MIN_SIZE
+
993 (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
995 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
996 ospf_intra_add_stub (rt
, l
, v
, area
, parent_is_root
);
1000 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1, 1);
1002 for (ALL_LIST_ELEMENTS (v
->children
, cnode
, cnnode
, child
))
1004 if (CHECK_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
))
1007 /* the first level of routers connected to the root
1008 * should have 'parent_is_root' set, including those
1009 * connected via a network vertex.
1013 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1016 ospf_spf_process_stubs (area
, child
, rt
, parent_is_root
);
1018 SET_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
);
1023 ospf_rtrs_free (struct route_table
*rtrs
)
1025 struct route_node
*rn
;
1026 struct list
*or_list
;
1027 struct ospf_route
*or;
1028 struct listnode
*node
, *nnode
;
1030 if (IS_DEBUG_OSPF_EVENT
)
1031 zlog_debug ("Route: Router Routing Table free");
1033 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1034 if ((or_list
= rn
->info
) != NULL
)
1036 for (ALL_LIST_ELEMENTS (or_list
, node
, nnode
, or))
1037 ospf_route_free (or);
1039 list_delete (or_list
);
1041 /* Unlock the node. */
1043 route_unlock_node (rn
);
1045 route_table_finish (rtrs
);
1049 ospf_rtrs_print (struct route_table
*rtrs
)
1051 struct route_node
*rn
;
1052 struct list
*or_list
;
1053 struct listnode
*ln
;
1054 struct listnode
*pnode
;
1055 struct ospf_route
*or;
1056 struct ospf_path
*path
;
1060 if (IS_DEBUG_OSPF_EVENT
)
1061 zlog_debug ("ospf_rtrs_print() start");
1063 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1064 if ((or_list
= rn
->info
) != NULL
)
1065 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1067 switch (or->path_type
)
1069 case OSPF_PATH_INTRA_AREA
:
1070 if (IS_DEBUG_OSPF_EVENT
)
1071 zlog_debug ("%s [%d] area: %s",
1072 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1073 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1076 case OSPF_PATH_INTER_AREA
:
1077 if (IS_DEBUG_OSPF_EVENT
)
1078 zlog_debug ("%s IA [%d] area: %s",
1079 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1080 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1087 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1089 if (path
->nexthop
.s_addr
== 0)
1091 if (IS_DEBUG_OSPF_EVENT
)
1092 zlog_debug (" directly attached to %s\r\n",
1093 ifindex2ifname (path
->ifindex
));
1097 if (IS_DEBUG_OSPF_EVENT
)
1098 zlog_debug (" via %s, %s\r\n",
1099 inet_ntoa (path
->nexthop
),
1100 ifindex2ifname (path
->ifindex
));
1105 zlog_debug ("ospf_rtrs_print() end");
1108 /* Calculating the shortest-path tree for an area. */
1110 ospf_spf_calculate (struct ospf_area
*area
, struct route_table
*new_table
,
1111 struct route_table
*new_rtrs
)
1113 struct pqueue
*candidate
;
1116 if (IS_DEBUG_OSPF_EVENT
)
1118 zlog_debug ("ospf_spf_calculate: Start");
1119 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1120 inet_ntoa (area
->area_id
));
1123 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1124 return this area's calculation. */
1125 if (!area
->router_lsa_self
)
1127 if (IS_DEBUG_OSPF_EVENT
)
1128 zlog_debug ("ospf_spf_calculate: "
1129 "Skip area %s's calculation due to empty router_lsa_self",
1130 inet_ntoa (area
->area_id
));
1134 /* RFC2328 16.1. (1). */
1135 /* Initialize the algorithm's data structures. */
1137 /* This function scans all the LSA database and set the stat field to
1138 * LSA_SPF_NOT_EXPLORED. */
1139 ospf_lsdb_clean_stat (area
->lsdb
);
1140 /* Create a new heap for the candidates. */
1141 candidate
= pqueue_create();
1142 candidate
->cmp
= cmp
;
1143 candidate
->update
= update_stat
;
1145 /* Initialize the shortest-path tree to only the root (which is the
1146 router doing the calculation). */
1147 ospf_spf_init (area
);
1149 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1151 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1153 /* Set Area A's TransitCapability to FALSE. */
1154 area
->transit
= OSPF_TRANSIT_FALSE
;
1155 area
->shortcut_capability
= 1;
1159 /* RFC2328 16.1. (2). */
1160 ospf_spf_next (v
, area
, candidate
);
1162 /* RFC2328 16.1. (3). */
1163 /* If at this step the candidate list is empty, the shortest-
1164 path tree (of transit vertices) has been completely built and
1165 this stage of the procedure terminates. */
1166 if (candidate
->size
== 0)
1169 /* Otherwise, choose the vertex belonging to the candidate list
1170 that is closest to the root, and add it to the shortest-path
1171 tree (removing it from the candidate list in the
1173 /* Extract from the candidates the node with the lower key. */
1174 v
= (struct vertex
*) pqueue_dequeue (candidate
);
1175 /* Update stat field in vertex. */
1176 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1178 ospf_vertex_add_parent (v
);
1180 /* RFC2328 16.1. (4). */
1181 if (v
->type
== OSPF_VERTEX_ROUTER
)
1182 ospf_intra_add_router (new_rtrs
, v
, area
);
1184 ospf_intra_add_transit (new_table
, v
, area
);
1186 /* RFC2328 16.1. (5). */
1187 /* Iterate the algorithm by returning to Step 2. */
1189 } /* end loop until no more candidate vertices */
1191 if (IS_DEBUG_OSPF_EVENT
)
1193 ospf_spf_dump (area
->spf
, 0);
1194 ospf_route_table_dump (new_table
);
1197 /* Second stage of SPF calculation procedure's */
1198 ospf_spf_process_stubs (area
, area
->spf
, new_table
, 0);
1200 /* Free candidate queue. */
1201 pqueue_delete (candidate
);
1203 ospf_vertex_dump (__func__
, area
->spf
, 0, 1);
1204 /* Free nexthop information, canonical versions of which are attached
1205 * the first level of router vertices attached to the root vertex, see
1206 * ospf_nexthop_calculation.
1208 ospf_canonical_nexthops_free (area
->spf
);
1210 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1213 list_delete_all_node (&vertex_list
);
1215 /* Increment SPF Calculation Counter. */
1216 area
->spf_calculation
++;
1218 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &area
->ospf
->ts_spf
);
1220 if (IS_DEBUG_OSPF_EVENT
)
1221 zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
1222 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1225 /* Timer for SPF calculation. */
1227 ospf_spf_calculate_timer (struct thread
*thread
)
1229 struct ospf
*ospf
= THREAD_ARG (thread
);
1230 struct route_table
*new_table
, *new_rtrs
;
1231 struct ospf_area
*area
;
1232 struct listnode
*node
, *nnode
;
1234 if (IS_DEBUG_OSPF_EVENT
)
1235 zlog_debug ("SPF: Timer (SPF calculation expire)");
1237 ospf
->t_spf_calc
= NULL
;
1239 /* Allocate new table tree. */
1240 new_table
= route_table_init ();
1241 new_rtrs
= route_table_init ();
1243 ospf_vl_unapprove (ospf
);
1245 /* Calculate SPF for each area. */
1246 for (ALL_LIST_ELEMENTS (ospf
->areas
, node
, nnode
, area
))
1248 /* Do backbone last, so as to first discover intra-area paths
1249 * for any back-bone virtual-links
1251 if (ospf
->backbone
&& ospf
->backbone
== area
)
1254 ospf_spf_calculate (area
, new_table
, new_rtrs
);
1257 /* SPF for backbone, if required */
1259 ospf_spf_calculate (ospf
->backbone
, new_table
, new_rtrs
);
1261 ospf_vl_shut_unapproved (ospf
);
1263 ospf_ia_routing (ospf
, new_table
, new_rtrs
);
1265 ospf_prune_unreachable_networks (new_table
);
1266 ospf_prune_unreachable_routers (new_rtrs
);
1268 /* AS-external-LSA calculation should not be performed here. */
1270 /* If new Router Route is installed,
1271 then schedule re-calculate External routes. */
1273 ospf_ase_calculate_schedule (ospf
);
1275 ospf_ase_calculate_timer_add (ospf
);
1277 /* Update routing table. */
1278 ospf_route_install (ospf
, new_table
);
1280 /* Update ABR/ASBR routing table */
1283 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1284 /* ospf_route_delete (ospf->old_rtrs); */
1285 ospf_rtrs_free (ospf
->old_rtrs
);
1288 ospf
->old_rtrs
= ospf
->new_rtrs
;
1289 ospf
->new_rtrs
= new_rtrs
;
1291 if (IS_OSPF_ABR (ospf
))
1292 ospf_abr_task (ospf
);
1294 if (IS_DEBUG_OSPF_EVENT
)
1295 zlog_debug ("SPF: calculation complete");
1300 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1301 set timer for SPF calc. */
1303 ospf_spf_calculate_schedule (struct ospf
*ospf
)
1305 unsigned long delay
, elapsed
, ht
;
1306 struct timeval result
;
1308 if (IS_DEBUG_OSPF_EVENT
)
1309 zlog_debug ("SPF: calculation timer scheduled");
1311 /* OSPF instance does not exist. */
1315 /* SPF calculation timer is already scheduled. */
1316 if (ospf
->t_spf_calc
)
1318 if (IS_DEBUG_OSPF_EVENT
)
1319 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1324 /* XXX Monotic timers: we only care about relative time here. */
1325 result
= tv_sub (recent_relative_time (), ospf
->ts_spf
);
1327 elapsed
= (result
.tv_sec
* 1000) + (result
.tv_usec
/ 1000);
1328 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1330 if (ht
> ospf
->spf_max_holdtime
)
1331 ht
= ospf
->spf_max_holdtime
;
1333 /* Get SPF calculation delay time. */
1336 /* Got an event within the hold time of last SPF. We need to
1337 * increase the hold_multiplier, if it's not already at/past
1338 * maximum value, and wasn't already increased..
1340 if (ht
< ospf
->spf_max_holdtime
)
1341 ospf
->spf_hold_multiplier
++;
1343 /* always honour the SPF initial delay */
1344 if ( (ht
- elapsed
) < ospf
->spf_delay
)
1345 delay
= ospf
->spf_delay
;
1347 delay
= ht
- elapsed
;
1351 /* Event is past required hold-time of last SPF */
1352 delay
= ospf
->spf_delay
;
1353 ospf
->spf_hold_multiplier
= 1;
1356 if (IS_DEBUG_OSPF_EVENT
)
1357 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
1360 thread_add_timer_msec (master
, ospf_spf_calculate_timer
, ospf
, delay
);