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