]> git.proxmox.com Git - mirror_frr.git/blame_incremental - ospfd/ospf_spf.c
projects / mirror_frr.git / blame_incremental
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (non-incremental) | history | HEAD
Fix last commit - add back in closing paren which was apparently
[mirror_frr.git] / ospfd / ospf_spf.c
... / ...
CommitLineData
1/* OSPF SPF calculation.
2 Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
3
4This file is part of GNU Zebra.
5
6GNU Zebra is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 2, or (at your option) any
9later version.
10
11GNU Zebra is distributed in the hope that it will be useful, but
12WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU Zebra; see the file COPYING. If not, write to the Free
18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
1902111-1307, USA. */
20
21#include <zebra.h>
22
23#include "thread.h"
24#include "memory.h"
25#include "hash.h"
26#include "linklist.h"
27#include "prefix.h"
28#include "if.h"
29#include "table.h"
30#include "log.h"
31#include "sockunion.h" /* for inet_ntop () */
32#include "pqueue.h"
33
34#include "ospfd/ospfd.h"
35#include "ospfd/ospf_interface.h"
36#include "ospfd/ospf_ism.h"
37#include "ospfd/ospf_asbr.h"
38#include "ospfd/ospf_lsa.h"
39#include "ospfd/ospf_lsdb.h"
40#include "ospfd/ospf_neighbor.h"
41#include "ospfd/ospf_nsm.h"
42#include "ospfd/ospf_spf.h"
43#include "ospfd/ospf_route.h"
44#include "ospfd/ospf_ia.h"
45#include "ospfd/ospf_ase.h"
46#include "ospfd/ospf_abr.h"
47#include "ospfd/ospf_dump.h"
48
49static 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
53 */
54static struct list vertex_list = { .del = ospf_vertex_free };
55\f
56/* Heap related functions, for the managment of the candidates, to
57 * be used with pqueue. */
58static int
59cmp (void * node1 , void * node2)
60{
61 struct vertex * v1 = (struct vertex *) node1;
62 struct vertex * v2 = (struct vertex *) node2;
63 if (v1 != NULL && v2 != NULL )
64 {
65 /* network vertices must be chosen before router vertices of same
66 * cost in order to find all shortest paths
67 */
68 if ( ((v1->distance - v2->distance) == 0)
69 && (v1->type != v2->type))
70 {
71 switch (v1->type)
72 {
73 case OSPF_VERTEX_NETWORK:
74 return -1;
75 case OSPF_VERTEX_ROUTER:
76 return 1;
77 }
78 }
79 else
80 return (v1->distance - v2->distance);
81 }
82 return 0;
83}
84
85static void
86update_stat (void *node , int position)
87{
88 struct vertex *v = node;
89
90 /* Set the status of the vertex, when its position changes. */
91 *(v->stat) = position;
92}
93\f
94static struct vertex_nexthop *
95vertex_nexthop_new (void)
96{
97 return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
98}
99
100static void
101vertex_nexthop_free (struct vertex_nexthop *nh)
102{
103 XFREE (MTYPE_OSPF_NEXTHOP, nh);
104}
105
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
108 * vertices.
109 */
110static void
111ospf_canonical_nexthops_free (struct vertex *root)
112{
113 struct listnode *node, *nnode;
114 struct vertex *child;
115
116 for (ALL_LIST_ELEMENTS (root->children, node, nnode, child))
117 {
118 struct listnode *n2, *nn2;
119 struct vertex_parent *vp;
120
121 /* router vertices through an attached network each
122 * have a distinct (canonical / not inherited) nexthop
123 * which must be freed.
124 *
125 * A network vertex can only have router vertices as its
126 * children, so only one level of recursion is possible.
127 */
128 if (child->type == OSPF_VERTEX_NETWORK)
129 ospf_canonical_nexthops_free (child);
130
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);
135 }
136}
137\f
138/* TODO: Parent list should be excised, in favour of maintaining only
139 * vertex_nexthop, with refcounts.
140 */
141static struct vertex_parent *
142vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
143{
144 struct vertex_parent *new;
145
146 new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent));
147
148 if (new == NULL)
149 return NULL;
150
151 new->parent = v;
152 new->backlink = backlink;
153 new->nexthop = hop;
154 return new;
155}
156
157static void
158vertex_parent_free (void *p)
159{
160 XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
161}
162\f
163static struct vertex *
164ospf_vertex_new (struct ospf_lsa *lsa)
165{
166 struct vertex *new;
167
168 new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
169
170 new->flags = 0;
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;
178
179 listnode_add (&vertex_list, new);
180
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));
185 return new;
186}
187
188static void
189ospf_vertex_free (void *data)
190{
191 struct vertex *v = data;
192
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));
197
198 /* There should be no parents potentially holding references to this vertex
199 * Children however may still be there, but presumably referenced by other
200 * vertices
201 */
202 //assert (listcount (v->parents) == 0);
203
204 if (v->children)
205 list_delete (v->children);
206 v->children = NULL;
207
208 if (v->parents)
209 list_delete (v->parents);
210 v->parents = NULL;
211
212 v->lsa = NULL;
213
214 XFREE (MTYPE_OSPF_VERTEX, v);
215}
216
217static void
218ospf_vertex_dump(const char *msg, struct vertex *v,
219 int print_parents, int print_children)
220{
221 if ( ! IS_DEBUG_OSPF_EVENT)
222 return;
223
224 zlog_debug("%s %s vertex %s distance %u flags %u",
225 msg,
226 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
227 inet_ntoa(v->lsa->id),
228 v->distance,
229 (unsigned int)v->flags);
230
231 if (print_parents)
232 {
233 struct listnode *node;
234 struct vertex_parent *vp;
235
236 for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
237 {
238 char buf1[BUFSIZ];
239
240 if (vp)
241 {
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");
246 }
247 }
248 }
249
250 if (print_children)
251 {
252 struct listnode *cnode;
253 struct vertex *cv;
254
255 for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv))
256 ospf_vertex_dump(" child:", cv, 0, 0);
257 }
258}
259
260
261/* Add a vertex to the list of children in each of its parents. */
262static void
263ospf_vertex_add_parent (struct vertex *v)
264{
265 struct vertex_parent *vp;
266 struct listnode *node;
267
268 assert (v && v->parents);
269
270 for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
271 {
272 assert (vp->parent && vp->parent->children);
273
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);
277 }
278}
279\f
280static void
281ospf_spf_init (struct ospf_area *area)
282{
283 struct vertex *v;
284
285 /* Create root node. */
286 v = ospf_vertex_new (area->router_lsa_self);
287
288 area->spf = v;
289
290 /* Reset ABR and ASBR router counts. */
291 area->abr_count = 0;
292 area->asbr_count = 0;
293}
294
295/* return index of link back to V from W, or -1 if no link found */
296static int
297ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
298{
299 unsigned int i, length;
300 struct router_lsa *rl;
301 struct network_lsa *nl;
302
303 /* In case of W is Network LSA. */
304 if (w->type == OSPF_NETWORK_LSA)
305 {
306 if (v->type == OSPF_NETWORK_LSA)
307 return -1;
308
309 nl = (struct network_lsa *) w;
310 length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
311
312 for (i = 0; i < length; i++)
313 if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
314 return i;
315 return -1;
316 }
317
318 /* In case of W is Router LSA. */
319 if (w->type == OSPF_ROUTER_LSA)
320 {
321 rl = (struct router_lsa *) w;
322
323 length = ntohs (w->length);
324
325 for (i = 0;
326 i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
327 i++, length -= 12)
328 {
329 switch (rl->link[i].type)
330 {
331 case LSA_LINK_TYPE_POINTOPOINT:
332 case LSA_LINK_TYPE_VIRTUALLINK:
333 /* Router LSA ID. */
334 if (v->type == OSPF_ROUTER_LSA &&
335 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
336 {
337 return i;
338 }
339 break;
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))
344 {
345 return i;
346 }
347 break;
348 case LSA_LINK_TYPE_STUB:
349 /* Stub can't lead anywhere, carry on */
350 continue;
351 default:
352 break;
353 }
354 }
355 }
356 return -1;
357}
358
359#define ROUTER_LSA_MIN_SIZE 12
360#define ROUTER_LSA_TOS_SIZE 4
361
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.
365 */
366static struct router_lsa_link *
367ospf_get_next_link (struct vertex *v, struct vertex *w,
368 struct router_lsa_link *prev_link)
369{
370 u_char *p;
371 u_char *lim;
372 struct router_lsa_link *l;
373
374 if (prev_link == NULL)
375 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
376 else
377 {
378 p = (u_char *) prev_link;
379 p += (ROUTER_LSA_MIN_SIZE +
380 (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
381 }
382
383 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
384
385 while (p < lim)
386 {
387 l = (struct router_lsa_link *) p;
388
389 p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
390
391 if (l->m[0].type == LSA_LINK_TYPE_STUB)
392 continue;
393
394 /* Defer NH calculation via VLs until summaries from
395 transit areas area confidered */
396
397 if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
398 continue;
399
400 if (IPV4_ADDR_SAME (&l->link_id, &w->id))
401 return l;
402 }
403
404 return NULL;
405}
406
407static void
408ospf_spf_flush_parents (struct vertex *w)
409{
410 struct vertex_parent *vp;
411 struct listnode *ln, *nn;
412
413 /* delete the existing nexthops */
414 for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
415 {
416 list_delete_node (w->parents, ln);
417 vertex_parent_free (vp);
418 }
419}
420
421/*
422 * Consider supplied next-hop for inclusion to the supplied list of
423 * equal-cost next-hops, adjust list as neccessary.
424 */
425static void
426ospf_spf_add_parent (struct vertex *v, struct vertex *w,
427 struct vertex_nexthop *newhop,
428 unsigned int distance)
429{
430 struct vertex_parent *vp;
431
432 /* we must have a newhop, and a distance */
433 assert (v && w && newhop);
434 assert (distance);
435
436 /* IFF w has already been assigned a distance, then we shouldn't get here
437 * unless callers have determined V(l)->W is shortest / equal-shortest
438 * path (0 is a special case distance (no distance yet assigned)).
439 */
440 if (w->distance)
441 assert (distance <= w->distance);
442 else
443 w->distance = distance;
444
445 if (IS_DEBUG_OSPF_EVENT)
446 {
447 char buf[2][INET_ADDRSTRLEN];
448 zlog_debug ("%s: Adding %s as parent of %s",
449 __func__,
450 inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
451 inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
452 }
453
454 /* Adding parent for a new, better path: flush existing parents from W. */
455 if (distance < w->distance)
456 {
457 if (IS_DEBUG_OSPF_EVENT)
458 zlog_debug ("%s: distance %d better than %d, flushing existing parents",
459 __func__, distance, w->distance);
460 ospf_spf_flush_parents (w);
461 w->distance = distance;
462 }
463
464 /* new parent is <= existing parents, add it to parent list */
465 vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
466 listnode_add (w->parents, vp);
467
468 return;
469}
470
471/* 16.1.1. Calculate nexthop from root through V (parent) to
472 * vertex W (destination), with given distance from root->W.
473 *
474 * The link must be supplied if V is the root vertex. In all other cases
475 * it may be NULL.
476 *
477 * Note that this function may fail, hence the state of the destination
478 * vertex, W, should /not/ be modified in a dependent manner until
479 * this function returns. This function will update the W vertex with the
480 * provided distance as appropriate.
481 */
482static unsigned int
483ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
484 struct vertex *w, struct router_lsa_link *l,
485 unsigned int distance)
486{
487 struct listnode *node, *nnode;
488 struct vertex_nexthop *nh;
489 struct vertex_parent *vp;
490 struct ospf_interface *oi = NULL;
491 unsigned int added = 0;
492
493 if (IS_DEBUG_OSPF_EVENT)
494 {
495 zlog_debug ("ospf_nexthop_calculation(): Start");
496 ospf_vertex_dump("V (parent):", v, 1, 1);
497 ospf_vertex_dump("W (dest) :", w, 1, 1);
498 zlog_debug ("V->W distance: %d", distance);
499 }
500
501 if (v == area->spf)
502 {
503 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
504 root (the calculating router itself). This means that the
505 destination is either a directly connected network or directly
506 connected router. The outgoing interface in this case is simply
507 the OSPF interface connecting to the destination network/router.
508 */
509
510 if (w->type == OSPF_VERTEX_ROUTER)
511 {
512 /* l is a link from v to w
513 * l2 will be link from w to v
514 */
515 struct router_lsa_link *l2 = NULL;
516
517 /* we *must* be supplied with the link data */
518 assert (l != NULL);
519
520 if (IS_DEBUG_OSPF_EVENT)
521 {
522 char buf1[BUFSIZ];
523 char buf2[BUFSIZ];
524
525 zlog_debug("ospf_nexthop_calculation(): considering link "
526 "type %d link_id %s link_data %s",
527 l->m[0].type,
528 inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
529 inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
530 }
531
532 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
533 {
534 /* If the destination is a router which connects to
535 the calculating router via a Point-to-MultiPoint
536 network, the destination's next hop IP address(es)
537 can be determined by examining the destination's
538 router-LSA: each link pointing back to the
539 calculating router and having a Link Data field
540 belonging to the Point-to-MultiPoint network
541 provides an IP address of the next hop router.
542
543 At this point l is a link from V to W, and V is the
544 root ("us"). Find the local interface associated
545 with l (its address is in l->link_data). If it
546 is a point-to-multipoint interface, then look through
547 the links in the opposite direction (W to V). If
548 any of them have an address that lands within the
549 subnet declared by the PtMP link, then that link
550 is a constituent of the PtMP link, and its address is
551 a nexthop address for V.
552 */
553 oi = ospf_if_is_configured (area->ospf, &l->link_data);
554 if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
555 {
556 struct prefix_ipv4 la;
557
558 la.family = AF_INET;
559 la.prefixlen = oi->address->prefixlen;
560
561 /* V links to W on PtMP interface
562 - find the interface address on W */
563 while ((l2 = ospf_get_next_link (w, v, l2)))
564 {
565 la.prefix = l2->link_data;
566
567 if (prefix_cmp ((struct prefix *) &la,
568 oi->address) == 0)
569 /* link_data is on our PtMP network */
570 break;
571 }
572 } /* end l is on point-to-multipoint link */
573 else
574 {
575 /* l is a regular point-to-point link.
576 Look for a link from W to V.
577 */
578 while ((l2 = ospf_get_next_link (w, v, l2)))
579 {
580 oi = ospf_if_is_configured (area->ospf,
581 &(l2->link_data));
582
583 if (oi == NULL)
584 continue;
585
586 if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
587 &l->link_data))
588 continue;
589
590 break;
591 }
592 }
593
594 if (oi && l2)
595 {
596 /* found all necessary info to build nexthop */
597 nh = vertex_nexthop_new ();
598 nh->oi = oi;
599 nh->router = l2->link_data;
600 ospf_spf_add_parent (v, w, nh, distance);
601 return 1;
602 }
603 else
604 zlog_info("ospf_nexthop_calculation(): "
605 "could not determine nexthop for link");
606 } /* end point-to-point link from V to W */
607 else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
608 {
609 struct ospf_vl_data *vl_data;
610
611 /* VLink implementation limitations:
612 * a) vl_data can only reference one nexthop, so no ECMP
613 * to backbone through VLinks. Though transit-area
614 * summaries may be considered, and those can be ECMP.
615 * b) We can only use /one/ VLink, even if multiple ones
616 * exist this router through multiple transit-areas.
617 */
618 vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
619
620 if (vl_data
621 && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
622 {
623 nh = vertex_nexthop_new ();
624 nh->oi = vl_data->nexthop.oi;
625 nh->router = vl_data->nexthop.router;
626 ospf_spf_add_parent (v, w, nh, distance);
627 return 1;
628 }
629 else
630 zlog_info("ospf_nexthop_calculation(): "
631 "vl_data for VL link not found");
632 } /* end virtual-link from V to W */
633 return 0;
634 } /* end W is a Router vertex */
635 else
636 {
637 assert(w->type == OSPF_VERTEX_NETWORK);
638 oi = ospf_if_is_configured (area->ospf, &(l->link_data));
639 if (oi)
640 {
641 nh = vertex_nexthop_new ();
642 nh->oi = oi;
643 nh->router.s_addr = 0;
644 ospf_spf_add_parent (v, w, nh, distance);
645 return 1;
646 }
647 }
648 zlog_info("ospf_nexthop_calculation(): "
649 "Unknown attached link");
650 return 0;
651 } /* end V is the root */
652 /* Check if W's parent is a network connected to root. */
653 else if (v->type == OSPF_VERTEX_NETWORK)
654 {
655 /* See if any of V's parents are the root. */
656 for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
657 {
658 if (vp->parent == area->spf) /* connects to root? */
659 {
660 /* 16.1.1 para 5. ...the parent vertex is a network that
661 * directly connects the calculating router to the destination
662 * router. The list of next hops is then determined by
663 * examining the destination's router-LSA...
664 */
665
666 assert(w->type == OSPF_VERTEX_ROUTER);
667 while ((l = ospf_get_next_link (w, v, l)))
668 {
669 /* ...For each link in the router-LSA that points back to the
670 * parent network, the link's Link Data field provides the IP
671 * address of a next hop router. The outgoing interface to
672 * use can then be derived from the next hop IP address (or
673 * it can be inherited from the parent network).
674 */
675 nh = vertex_nexthop_new ();
676 nh->oi = vp->nexthop->oi;
677 nh->router = l->link_data;
678 added = 1;
679 ospf_spf_add_parent (v, w, nh, distance);
680 }
681 }
682 }
683 if (added)
684 return added;
685 }
686
687 /* 16.1.1 para 4. If there is at least one intervening router in the
688 * current shortest path between the destination and the root, the
689 * destination simply inherits the set of next hops from the
690 * parent.
691 */
692 if (IS_DEBUG_OSPF_EVENT)
693 zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
694
695 for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
696 {
697 added = 1;
698 ospf_spf_add_parent (v, w, vp->nexthop, distance);
699 }
700
701 return added;
702}
703
704/* RFC2328 Section 16.1 (2).
705 * v is on the SPF tree. Examine the links in v's LSA. Update the list
706 * of candidates with any vertices not already on the list. If a lower-cost
707 * path is found to a vertex already on the candidate list, store the new cost.
708 */
709static void
710ospf_spf_next (struct vertex *v, struct ospf_area *area,
711 struct pqueue * candidate)
712{
713 struct ospf_lsa *w_lsa = NULL;
714 u_char *p;
715 u_char *lim;
716 struct router_lsa_link *l = NULL;
717 struct in_addr *r;
718 int type = 0;
719
720 /* If this is a router-LSA, and bit V of the router-LSA (see Section
721 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
722 if (v->type == OSPF_VERTEX_ROUTER)
723 {
724 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
725 area->transit = OSPF_TRANSIT_TRUE;
726 }
727
728 if (IS_DEBUG_OSPF_EVENT)
729 zlog_debug ("%s: Next vertex of %s vertex %s",
730 __func__,
731 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
732 inet_ntoa(v->lsa->id));
733
734 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
735 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
736
737 while (p < lim)
738 {
739 struct vertex *w;
740 unsigned int distance;
741
742 /* In case of V is Router-LSA. */
743 if (v->lsa->type == OSPF_ROUTER_LSA)
744 {
745 l = (struct router_lsa_link *) p;
746
747 p += (ROUTER_LSA_MIN_SIZE +
748 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
749
750 /* (a) If this is a link to a stub network, examine the next
751 link in V's LSA. Links to stub networks will be
752 considered in the second stage of the shortest path
753 calculation. */
754 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
755 continue;
756
757 /* Infinite distance links shouldn't be followed, except
758 * for local links (a stub-routed router still wants to
759 * calculate tree, so must follow its own links).
760 */
761 if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
762 continue;
763
764 /* (b) Otherwise, W is a transit vertex (router or transit
765 network). Look up the vertex W's LSA (router-LSA or
766 network-LSA) in Area A's link state database. */
767 switch (type)
768 {
769 case LSA_LINK_TYPE_POINTOPOINT:
770 case LSA_LINK_TYPE_VIRTUALLINK:
771 if (type == LSA_LINK_TYPE_VIRTUALLINK)
772 {
773 if (IS_DEBUG_OSPF_EVENT)
774 zlog_debug ("looking up LSA through VL: %s",
775 inet_ntoa (l->link_id));
776 }
777
778 w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
779 l->link_id);
780 if (w_lsa)
781 {
782 if (IS_DEBUG_OSPF_EVENT)
783 zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
784 }
785 break;
786 case LSA_LINK_TYPE_TRANSIT:
787 if (IS_DEBUG_OSPF_EVENT)
788 zlog_debug ("Looking up Network LSA, ID: %s",
789 inet_ntoa (l->link_id));
790 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
791 l->link_id);
792 if (w_lsa)
793 if (IS_DEBUG_OSPF_EVENT)
794 zlog_debug ("found the LSA");
795 break;
796 default:
797 zlog_warn ("Invalid LSA link type %d", type);
798 continue;
799 }
800 }
801 else
802 {
803 /* In case of V is Network-LSA. */
804 r = (struct in_addr *) p;
805 p += sizeof (struct in_addr);
806
807 /* Lookup the vertex W's LSA. */
808 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
809 if (w_lsa)
810 {
811 if (IS_DEBUG_OSPF_EVENT)
812 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
813 }
814 }
815
816 /* (b cont.) If the LSA does not exist, or its LS age is equal
817 to MaxAge, or it does not have a link back to vertex V,
818 examine the next link in V's LSA.[23] */
819 if (w_lsa == NULL)
820 {
821 if (IS_DEBUG_OSPF_EVENT)
822 zlog_debug ("No LSA found");
823 continue;
824 }
825
826 if (IS_LSA_MAXAGE (w_lsa))
827 {
828 if (IS_DEBUG_OSPF_EVENT)
829 zlog_debug ("LSA is MaxAge");
830 continue;
831 }
832
833 if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
834 {
835 if (IS_DEBUG_OSPF_EVENT)
836 zlog_debug ("The LSA doesn't have a link back");
837 continue;
838 }
839
840 /* (c) If vertex W is already on the shortest-path tree, examine
841 the next link in the LSA. */
842 if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
843 {
844 if (IS_DEBUG_OSPF_EVENT)
845 zlog_debug ("The LSA is already in SPF");
846 continue;
847 }
848
849 /* (d) Calculate the link state cost D of the resulting path
850 from the root to vertex W. D is equal to the sum of the link
851 state cost of the (already calculated) shortest path to
852 vertex V and the advertised cost of the link between vertices
853 V and W. If D is: */
854
855 /* calculate link cost D. */
856 if (v->lsa->type == OSPF_ROUTER_LSA)
857 distance = v->distance + ntohs (l->m[0].metric);
858 else /* v is not a Router-LSA */
859 distance = v->distance;
860
861 /* Is there already vertex W in candidate list? */
862 if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
863 {
864 /* prepare vertex W. */
865 w = ospf_vertex_new (w_lsa);
866
867 /* Calculate nexthop to W. */
868 if (ospf_nexthop_calculation (area, v, w, l, distance))
869 pqueue_enqueue (w, candidate);
870 else if (IS_DEBUG_OSPF_EVENT)
871 zlog_debug ("Nexthop Calc failed");
872 }
873 else if (w_lsa->stat >= 0)
874 {
875 /* Get the vertex from candidates. */
876 w = candidate->array[w_lsa->stat];
877
878 /* if D is greater than. */
879 if (w->distance < distance)
880 {
881 continue;
882 }
883 /* equal to. */
884 else if (w->distance == distance)
885 {
886 /* Found an equal-cost path to W.
887 * Calculate nexthop of to W from V. */
888 ospf_nexthop_calculation (area, v, w, l, distance);
889 }
890 /* less than. */
891 else
892 {
893 /* Found a lower-cost path to W.
894 * nexthop_calculation is conditional, if it finds
895 * valid nexthop it will call spf_add_parents, which
896 * will flush the old parents
897 */
898 if (ospf_nexthop_calculation (area, v, w, l, distance))
899 /* Decrease the key of the node in the heap,
900 * re-sort the heap. */
901 trickle_down (w_lsa->stat, candidate);
902 }
903 } /* end W is already on the candidate list */
904 } /* end loop over the links in V's LSA */
905}
906
907static void
908ospf_spf_dump (struct vertex *v, int i)
909{
910 struct listnode *cnode;
911 struct listnode *nnode;
912 struct vertex_parent *parent;
913
914 if (v->type == OSPF_VERTEX_ROUTER)
915 {
916 if (IS_DEBUG_OSPF_EVENT)
917 zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
918 }
919 else
920 {
921 struct network_lsa *lsa = (struct network_lsa *) v->lsa;
922 if (IS_DEBUG_OSPF_EVENT)
923 zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
924 ip_masklen (lsa->mask));
925 }
926
927 if (IS_DEBUG_OSPF_EVENT)
928 for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
929 {
930 zlog_debug (" nexthop %p %s %s",
931 parent->nexthop,
932 inet_ntoa (parent->nexthop->router),
933 parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
934 : "NULL");
935 }
936
937 i++;
938
939 for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
940 ospf_spf_dump (v, i);
941}
942
943/* Second stage of SPF calculation. */
944static void
945ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
946 struct route_table *rt)
947{
948 struct listnode *cnode, *cnnode;
949 struct vertex *child;
950
951 if (IS_DEBUG_OSPF_EVENT)
952 zlog_debug ("ospf_process_stub():processing stubs for area %s",
953 inet_ntoa (area->area_id));
954 if (v->type == OSPF_VERTEX_ROUTER)
955 {
956 u_char *p;
957 u_char *lim;
958 struct router_lsa_link *l;
959 struct router_lsa *rlsa;
960
961 if (IS_DEBUG_OSPF_EVENT)
962 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
963 inet_ntoa (v->lsa->id));
964 rlsa = (struct router_lsa *) v->lsa;
965
966
967 if (IS_DEBUG_OSPF_EVENT)
968 zlog_debug ("ospf_process_stubs(): we have %d links to process",
969 ntohs (rlsa->links));
970 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
971 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
972
973 while (p < lim)
974 {
975 l = (struct router_lsa_link *) p;
976
977 p += (ROUTER_LSA_MIN_SIZE +
978 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
979
980 if (l->m[0].type == LSA_LINK_TYPE_STUB)
981 ospf_intra_add_stub (rt, l, v, area);
982 }
983 }
984
985 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
986
987 for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
988 {
989 if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
990 continue;
991
992 ospf_spf_process_stubs (area, child, rt);
993
994 SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
995 }
996}
997
998void
999ospf_rtrs_free (struct route_table *rtrs)
1000{
1001 struct route_node *rn;
1002 struct list *or_list;
1003 struct ospf_route *or;
1004 struct listnode *node, *nnode;
1005
1006 if (IS_DEBUG_OSPF_EVENT)
1007 zlog_debug ("Route: Router Routing Table free");
1008
1009 for (rn = route_top (rtrs); rn; rn = route_next (rn))
1010 if ((or_list = rn->info) != NULL)
1011 {
1012 for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
1013 ospf_route_free (or);
1014
1015 list_delete (or_list);
1016
1017 /* Unlock the node. */
1018 rn->info = NULL;
1019 route_unlock_node (rn);
1020 }
1021 route_table_finish (rtrs);
1022}
1023
1024static void
1025ospf_rtrs_print (struct route_table *rtrs)
1026{
1027 struct route_node *rn;
1028 struct list *or_list;
1029 struct listnode *ln;
1030 struct listnode *pnode;
1031 struct ospf_route *or;
1032 struct ospf_path *path;
1033 char buf1[BUFSIZ];
1034 char buf2[BUFSIZ];
1035
1036 if (IS_DEBUG_OSPF_EVENT)
1037 zlog_debug ("ospf_rtrs_print() start");
1038
1039 for (rn = route_top (rtrs); rn; rn = route_next (rn))
1040 if ((or_list = rn->info) != NULL)
1041 for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
1042 {
1043 switch (or->path_type)
1044 {
1045 case OSPF_PATH_INTRA_AREA:
1046 if (IS_DEBUG_OSPF_EVENT)
1047 zlog_debug ("%s [%d] area: %s",
1048 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1049 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1050 buf2, BUFSIZ));
1051 break;
1052 case OSPF_PATH_INTER_AREA:
1053 if (IS_DEBUG_OSPF_EVENT)
1054 zlog_debug ("%s IA [%d] area: %s",
1055 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1056 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1057 buf2, BUFSIZ));
1058 break;
1059 default:
1060 break;
1061 }
1062
1063 for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
1064 {
1065 if (path->nexthop.s_addr == 0)
1066 {
1067 if (IS_DEBUG_OSPF_EVENT)
1068 zlog_debug (" directly attached to %s\r\n",
1069 IF_NAME (path->oi));
1070 }
1071 else
1072 {
1073 if (IS_DEBUG_OSPF_EVENT)
1074 zlog_debug (" via %s, %s\r\n",
1075 inet_ntoa (path->nexthop), IF_NAME (path->oi));
1076 }
1077 }
1078 }
1079
1080 zlog_debug ("ospf_rtrs_print() end");
1081}
1082
1083/* Calculating the shortest-path tree for an area. */
1084static void
1085ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
1086 struct route_table *new_rtrs)
1087{
1088 struct pqueue *candidate;
1089 struct vertex *v;
1090
1091 if (IS_DEBUG_OSPF_EVENT)
1092 {
1093 zlog_debug ("ospf_spf_calculate: Start");
1094 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1095 inet_ntoa (area->area_id));
1096 }
1097
1098 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1099 return this area's calculation. */
1100 if (!area->router_lsa_self)
1101 {
1102 if (IS_DEBUG_OSPF_EVENT)
1103 zlog_debug ("ospf_spf_calculate: "
1104 "Skip area %s's calculation due to empty router_lsa_self",
1105 inet_ntoa (area->area_id));
1106 return;
1107 }
1108
1109 /* RFC2328 16.1. (1). */
1110 /* Initialize the algorithm's data structures. */
1111
1112 /* This function scans all the LSA database and set the stat field to
1113 * LSA_SPF_NOT_EXPLORED. */
1114 ospf_lsdb_clean_stat (area->lsdb);
1115 /* Create a new heap for the candidates. */
1116 candidate = pqueue_create();
1117 candidate->cmp = cmp;
1118 candidate->update = update_stat;
1119
1120 /* Initialize the shortest-path tree to only the root (which is the
1121 router doing the calculation). */
1122 ospf_spf_init (area);
1123 v = area->spf;
1124 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1125 * spanning tree. */
1126 *(v->stat) = LSA_SPF_IN_SPFTREE;
1127
1128 /* Set Area A's TransitCapability to FALSE. */
1129 area->transit = OSPF_TRANSIT_FALSE;
1130 area->shortcut_capability = 1;
1131
1132 for (;;)
1133 {
1134 /* RFC2328 16.1. (2). */
1135 ospf_spf_next (v, area, candidate);
1136
1137 /* RFC2328 16.1. (3). */
1138 /* If at this step the candidate list is empty, the shortest-
1139 path tree (of transit vertices) has been completely built and
1140 this stage of the procedure terminates. */
1141 if (candidate->size == 0)
1142 break;
1143
1144 /* Otherwise, choose the vertex belonging to the candidate list
1145 that is closest to the root, and add it to the shortest-path
1146 tree (removing it from the candidate list in the
1147 process). */
1148 /* Extract from the candidates the node with the lower key. */
1149 v = (struct vertex *) pqueue_dequeue (candidate);
1150 /* Update stat field in vertex. */
1151 *(v->stat) = LSA_SPF_IN_SPFTREE;
1152
1153 ospf_vertex_add_parent (v);
1154
1155 /* Note that when there is a choice of vertices closest to the
1156 root, network vertices must be chosen before router vertices
1157 in order to necessarily find all equal-cost paths. */
1158 /* We don't do this at this moment, we should add the treatment
1159 above codes. -- kunihiro. */
1160
1161 /* RFC2328 16.1. (4). */
1162 if (v->type == OSPF_VERTEX_ROUTER)
1163 ospf_intra_add_router (new_rtrs, v, area);
1164 else
1165 ospf_intra_add_transit (new_table, v, area);
1166
1167 /* RFC2328 16.1. (5). */
1168 /* Iterate the algorithm by returning to Step 2. */
1169
1170 } /* end loop until no more candidate vertices */
1171
1172 if (IS_DEBUG_OSPF_EVENT)
1173 {
1174 ospf_spf_dump (area->spf, 0);
1175 ospf_route_table_dump (new_table);
1176 }
1177
1178 /* Second stage of SPF calculation procedure's */
1179 ospf_spf_process_stubs (area, area->spf, new_table);
1180
1181 /* Free candidate queue. */
1182 pqueue_delete (candidate);
1183
1184 ospf_vertex_dump (__func__, area->spf, 0, 1);
1185 /* Free nexthop information, canonical versions of which are attached
1186 * the first level of router vertices attached to the root vertex, see
1187 * ospf_nexthop_calculation.
1188 */
1189 ospf_canonical_nexthops_free (area->spf);
1190
1191 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1192 * as deconstructor.
1193 */
1194 list_delete_all_node (&vertex_list);
1195
1196 /* Increment SPF Calculation Counter. */
1197 area->spf_calculation++;
1198
1199 quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
1200
1201 if (IS_DEBUG_OSPF_EVENT)
1202 zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
1203 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1204}
1205\f
1206/* Timer for SPF calculation. */
1207static int
1208ospf_spf_calculate_timer (struct thread *thread)
1209{
1210 struct ospf *ospf = THREAD_ARG (thread);
1211 struct route_table *new_table, *new_rtrs;
1212 struct ospf_area *area;
1213 struct listnode *node, *nnode;
1214
1215 if (IS_DEBUG_OSPF_EVENT)
1216 zlog_debug ("SPF: Timer (SPF calculation expire)");
1217
1218 ospf->t_spf_calc = NULL;
1219
1220 /* Allocate new table tree. */
1221 new_table = route_table_init ();
1222 new_rtrs = route_table_init ();
1223
1224 ospf_vl_unapprove (ospf);
1225
1226 /* Calculate SPF for each area. */
1227 for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
1228 {
1229 /* Do backbone last, so as to first discover intra-area paths
1230 * for any back-bone virtual-links
1231 */
1232 if (ospf->backbone && ospf->backbone == area)
1233 continue;
1234
1235 ospf_spf_calculate (area, new_table, new_rtrs);
1236 }
1237
1238 /* SPF for backbone, if required */
1239 if (ospf->backbone)
1240 ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
1241
1242 ospf_vl_shut_unapproved (ospf);
1243
1244 ospf_ia_routing (ospf, new_table, new_rtrs);
1245
1246 ospf_prune_unreachable_networks (new_table);
1247 ospf_prune_unreachable_routers (new_rtrs);
1248
1249 /* AS-external-LSA calculation should not be performed here. */
1250
1251 /* If new Router Route is installed,
1252 then schedule re-calculate External routes. */
1253 if (1)
1254 ospf_ase_calculate_schedule (ospf);
1255
1256 ospf_ase_calculate_timer_add (ospf);
1257
1258 /* Update routing table. */
1259 ospf_route_install (ospf, new_table);
1260
1261 /* Update ABR/ASBR routing table */
1262 if (ospf->old_rtrs)
1263 {
1264 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1265 /* ospf_route_delete (ospf->old_rtrs); */
1266 ospf_rtrs_free (ospf->old_rtrs);
1267 }
1268
1269 ospf->old_rtrs = ospf->new_rtrs;
1270 ospf->new_rtrs = new_rtrs;
1271
1272 if (IS_OSPF_ABR (ospf))
1273 ospf_abr_task (ospf);
1274
1275 if (IS_DEBUG_OSPF_EVENT)
1276 zlog_debug ("SPF: calculation complete");
1277
1278 return 0;
1279}
1280
1281/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1282 set timer for SPF calc. */
1283void
1284ospf_spf_calculate_schedule (struct ospf *ospf)
1285{
1286 unsigned long delay, elapsed, ht;
1287 struct timeval result;
1288
1289 if (IS_DEBUG_OSPF_EVENT)
1290 zlog_debug ("SPF: calculation timer scheduled");
1291
1292 /* OSPF instance does not exist. */
1293 if (ospf == NULL)
1294 return;
1295
1296 /* SPF calculation timer is already scheduled. */
1297 if (ospf->t_spf_calc)
1298 {
1299 if (IS_DEBUG_OSPF_EVENT)
1300 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1301 ospf->t_spf_calc);
1302 return;
1303 }
1304
1305 /* XXX Monotic timers: we only care about relative time here. */
1306 result = tv_sub (recent_relative_time (), ospf->ts_spf);
1307
1308 elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
1309 ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
1310
1311 if (ht > ospf->spf_max_holdtime)
1312 ht = ospf->spf_max_holdtime;
1313
1314 /* Get SPF calculation delay time. */
1315 if (elapsed < ht)
1316 {
1317 /* Got an event within the hold time of last SPF. We need to
1318 * increase the hold_multiplier, if it's not already at/past
1319 * maximum value, and wasn't already increased..
1320 */
1321 if (ht < ospf->spf_max_holdtime)
1322 ospf->spf_hold_multiplier++;
1323
1324 /* always honour the SPF initial delay */
1325 if ( (ht - elapsed) < ospf->spf_delay)
1326 delay = ospf->spf_delay;
1327 else
1328 delay = ht - elapsed;
1329 }
1330 else
1331 {
1332 /* Event is past required hold-time of last SPF */
1333 delay = ospf->spf_delay;
1334 ospf->spf_hold_multiplier = 1;
1335 }
1336
1337 if (IS_DEBUG_OSPF_EVENT)
1338 zlog_debug ("SPF: calculation timer delay = %ld", delay);
1339
1340 ospf->t_spf_calc =
1341 thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
1342}
FRRouting mirror