Annotation of embedaddon/quagga/ospfd/ospf_spf.c, revision 1.1.1.3
1.1 misho 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: 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
53: */
54: static struct list vertex_list = { .del = ospf_vertex_free };
55:
56: /* Heap related functions, for the managment of the candidates, to
57: * be used with pqueue. */
58: static int
59: cmp (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:
85: static void
86: update_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:
94: static struct vertex_nexthop *
95: vertex_nexthop_new (void)
96: {
97: return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
98: }
99:
100: static void
101: vertex_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: */
110: static void
111: ospf_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:
138: /* TODO: Parent list should be excised, in favour of maintaining only
139: * vertex_nexthop, with refcounts.
140: */
141: static struct vertex_parent *
142: vertex_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:
157: static void
158: vertex_parent_free (void *p)
159: {
160: XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
161: }
162:
163: static struct vertex *
164: ospf_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:
188: static void
189: ospf_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:
217: static void
218: ospf_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. */
262: static void
263: ospf_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:
280: static void
281: ospf_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 */
296: static int
297: ospf_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: /* Find the next link after prev_link from v to w. If prev_link is
360: * NULL, return the first link from v to w. Ignore stub and virtual links;
361: * these link types will never be returned.
362: */
363: static struct router_lsa_link *
364: ospf_get_next_link (struct vertex *v, struct vertex *w,
365: struct router_lsa_link *prev_link)
366: {
367: u_char *p;
368: u_char *lim;
369: u_char lsa_type = LSA_LINK_TYPE_TRANSIT;
370: struct router_lsa_link *l;
371:
372: if (w->type == OSPF_VERTEX_ROUTER)
373: lsa_type = LSA_LINK_TYPE_POINTOPOINT;
374:
375: if (prev_link == NULL)
376: p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
377: else
378: {
379: p = (u_char *) prev_link;
380: p += (OSPF_ROUTER_LSA_LINK_SIZE +
381: (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
382: }
383:
384: lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
385:
386: while (p < lim)
387: {
388: l = (struct router_lsa_link *) p;
389:
390: p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
391:
392: if (l->m[0].type != lsa_type)
393: continue;
394:
395: if (IPV4_ADDR_SAME (&l->link_id, &w->id))
396: return l;
397: }
398:
399: return NULL;
400: }
401:
402: static void
403: ospf_spf_flush_parents (struct vertex *w)
404: {
405: struct vertex_parent *vp;
406: struct listnode *ln, *nn;
407:
408: /* delete the existing nexthops */
409: for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
410: {
411: list_delete_node (w->parents, ln);
412: vertex_parent_free (vp);
413: }
414: }
415:
416: /*
417: * Consider supplied next-hop for inclusion to the supplied list of
418: * equal-cost next-hops, adjust list as neccessary.
419: */
420: static void
421: ospf_spf_add_parent (struct vertex *v, struct vertex *w,
422: struct vertex_nexthop *newhop,
423: unsigned int distance)
424: {
1.1.1.3 ! misho 425: struct vertex_parent *vp, *wp;
! 426: struct listnode *node;
1.1 misho 427:
428: /* we must have a newhop, and a distance */
429: assert (v && w && newhop);
430: assert (distance);
431:
432: /* IFF w has already been assigned a distance, then we shouldn't get here
433: * unless callers have determined V(l)->W is shortest / equal-shortest
434: * path (0 is a special case distance (no distance yet assigned)).
435: */
436: if (w->distance)
437: assert (distance <= w->distance);
438: else
439: w->distance = distance;
440:
441: if (IS_DEBUG_OSPF_EVENT)
442: {
443: char buf[2][INET_ADDRSTRLEN];
444: zlog_debug ("%s: Adding %s as parent of %s",
445: __func__,
446: inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
447: inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
448: }
449:
450: /* Adding parent for a new, better path: flush existing parents from W. */
451: if (distance < w->distance)
452: {
453: if (IS_DEBUG_OSPF_EVENT)
454: zlog_debug ("%s: distance %d better than %d, flushing existing parents",
455: __func__, distance, w->distance);
456: ospf_spf_flush_parents (w);
457: w->distance = distance;
458: }
459:
1.1.1.3 ! misho 460: /* new parent is <= existing parents, add it to parent list (if nexthop
! 461: * not on parent list)
! 462: */
! 463: for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp))
! 464: {
! 465: if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0)
! 466: {
! 467: if (IS_DEBUG_OSPF_EVENT)
! 468: zlog_debug ("%s: ... nexthop already on parent list, skipping add", __func__);
! 469: return;
! 470: }
! 471: }
! 472:
1.1 misho 473: vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
474: listnode_add (w->parents, vp);
475:
476: return;
477: }
478:
479: /* 16.1.1. Calculate nexthop from root through V (parent) to
480: * vertex W (destination), with given distance from root->W.
481: *
482: * The link must be supplied if V is the root vertex. In all other cases
483: * it may be NULL.
484: *
485: * Note that this function may fail, hence the state of the destination
486: * vertex, W, should /not/ be modified in a dependent manner until
487: * this function returns. This function will update the W vertex with the
488: * provided distance as appropriate.
489: */
490: static unsigned int
491: ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
492: struct vertex *w, struct router_lsa_link *l,
1.1.1.3 ! misho 493: unsigned int distance, int lsa_pos)
1.1 misho 494: {
495: struct listnode *node, *nnode;
496: struct vertex_nexthop *nh;
497: struct vertex_parent *vp;
498: struct ospf_interface *oi = NULL;
499: unsigned int added = 0;
1.1.1.3 ! misho 500: char buf1[BUFSIZ];
! 501: char buf2[BUFSIZ];
1.1 misho 502:
503: if (IS_DEBUG_OSPF_EVENT)
504: {
505: zlog_debug ("ospf_nexthop_calculation(): Start");
506: ospf_vertex_dump("V (parent):", v, 1, 1);
507: ospf_vertex_dump("W (dest) :", w, 1, 1);
508: zlog_debug ("V->W distance: %d", distance);
509: }
510:
511: if (v == area->spf)
512: {
513: /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
514: root (the calculating router itself). This means that the
515: destination is either a directly connected network or directly
516: connected router. The outgoing interface in this case is simply
517: the OSPF interface connecting to the destination network/router.
518: */
519:
1.1.1.3 ! misho 520: /* we *must* be supplied with the link data */
! 521: assert (l != NULL);
! 522: oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
! 523: if (!oi)
! 524: {
! 525: zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
! 526: __func__, lsa_pos,
! 527: inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
! 528: inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
! 529: return 0;
! 530: }
! 531:
! 532: if (IS_DEBUG_OSPF_EVENT)
! 533: {
! 534: zlog_debug("%s: considering link:%s "
! 535: "type:%d link_id:%s link_data:%s",
! 536: __func__, oi->ifp->name, l->m[0].type,
! 537: inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
! 538: inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
! 539: }
! 540:
1.1 misho 541: if (w->type == OSPF_VERTEX_ROUTER)
542: {
543: /* l is a link from v to w
544: * l2 will be link from w to v
545: */
546: struct router_lsa_link *l2 = NULL;
547:
548: if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
549: {
1.1.1.3 ! misho 550: struct in_addr nexthop;
! 551:
1.1 misho 552: /* If the destination is a router which connects to
553: the calculating router via a Point-to-MultiPoint
554: network, the destination's next hop IP address(es)
555: can be determined by examining the destination's
556: router-LSA: each link pointing back to the
557: calculating router and having a Link Data field
558: belonging to the Point-to-MultiPoint network
559: provides an IP address of the next hop router.
560:
561: At this point l is a link from V to W, and V is the
1.1.1.3 ! misho 562: root ("us"). If it is a point-to-multipoint interface,
! 563: then look through the links in the opposite direction (W to V).
! 564: If any of them have an address that lands within the
1.1 misho 565: subnet declared by the PtMP link, then that link
1.1.1.3 ! misho 566: is a constituent of the PtMP link, and its address is
1.1 misho 567: a nexthop address for V.
568: */
1.1.1.3 ! misho 569: if (oi->type == OSPF_IFTYPE_POINTOPOINT)
! 570: {
! 571: added = 1;
! 572: nexthop.s_addr = 0; /* Nexthop not required */
! 573: }
! 574: else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
! 575: {
! 576: struct prefix_ipv4 la;
! 577:
! 578: la.family = AF_INET;
! 579: la.prefixlen = oi->address->prefixlen;
! 580:
! 581: /* V links to W on PtMP interface
! 582: - find the interface address on W */
! 583: while ((l2 = ospf_get_next_link (w, v, l2)))
! 584: {
! 585: la.prefix = l2->link_data;
! 586:
! 587: if (prefix_cmp ((struct prefix *) &la,
! 588: oi->address) != 0)
! 589: continue;
! 590: /* link_data is on our PtMP network */
! 591: added = 1;
! 592: nexthop = l2->link_data;
! 593: break;
! 594: }
! 595: }
1.1 misho 596:
1.1.1.3 ! misho 597: if (added)
1.1 misho 598: {
599: /* found all necessary info to build nexthop */
600: nh = vertex_nexthop_new ();
601: nh->oi = oi;
1.1.1.3 ! misho 602: nh->router = nexthop;
1.1 misho 603: ospf_spf_add_parent (v, w, nh, distance);
604: return 1;
605: }
606: else
1.1.1.3 ! misho 607: zlog_info("%s: could not determine nexthop for link %s",
! 608: __func__, oi->ifp->name);
1.1 misho 609: } /* end point-to-point link from V to W */
610: else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
611: {
612: struct ospf_vl_data *vl_data;
613:
614: /* VLink implementation limitations:
615: * a) vl_data can only reference one nexthop, so no ECMP
616: * to backbone through VLinks. Though transit-area
617: * summaries may be considered, and those can be ECMP.
618: * b) We can only use /one/ VLink, even if multiple ones
619: * exist this router through multiple transit-areas.
620: */
621: vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
622:
623: if (vl_data
624: && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
625: {
626: nh = vertex_nexthop_new ();
627: nh->oi = vl_data->nexthop.oi;
628: nh->router = vl_data->nexthop.router;
629: ospf_spf_add_parent (v, w, nh, distance);
630: return 1;
631: }
632: else
633: zlog_info("ospf_nexthop_calculation(): "
634: "vl_data for VL link not found");
635: } /* end virtual-link from V to W */
636: return 0;
637: } /* end W is a Router vertex */
638: else
639: {
640: assert(w->type == OSPF_VERTEX_NETWORK);
1.1.1.3 ! misho 641:
! 642: nh = vertex_nexthop_new ();
! 643: nh->oi = oi;
! 644: nh->router.s_addr = 0; /* Nexthop not required */
! 645: ospf_spf_add_parent (v, w, nh, distance);
! 646: return 1;
1.1 misho 647: }
648: } /* end V is the root */
649: /* Check if W's parent is a network connected to root. */
650: else if (v->type == OSPF_VERTEX_NETWORK)
651: {
652: /* See if any of V's parents are the root. */
653: for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
654: {
655: if (vp->parent == area->spf) /* connects to root? */
656: {
657: /* 16.1.1 para 5. ...the parent vertex is a network that
658: * directly connects the calculating router to the destination
659: * router. The list of next hops is then determined by
660: * examining the destination's router-LSA...
661: */
662:
663: assert(w->type == OSPF_VERTEX_ROUTER);
664: while ((l = ospf_get_next_link (w, v, l)))
665: {
666: /* ...For each link in the router-LSA that points back to the
667: * parent network, the link's Link Data field provides the IP
668: * address of a next hop router. The outgoing interface to
669: * use can then be derived from the next hop IP address (or
670: * it can be inherited from the parent network).
671: */
672: nh = vertex_nexthop_new ();
673: nh->oi = vp->nexthop->oi;
674: nh->router = l->link_data;
675: added = 1;
676: ospf_spf_add_parent (v, w, nh, distance);
677: }
1.1.1.3 ! misho 678: /* Note lack of return is deliberate. See next comment. */
! 679: }
1.1 misho 680: }
681: /* NB: This code is non-trivial.
682: *
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
1.1.1.3 ! misho 686: * bi-directional connectivity between V and W (which need not be the
! 687: * case, e.g. when OSPF has not yet converged fully). Otherwise, if
! 688: * we /always/ return here, without having checked that root->V->-W
! 689: * actually resulted in a valid nexthop being created, then we we will
! 690: * prevent SPF from finding/using higher cost paths.
! 691: *
! 692: * It is important, if root->V->W has not been added, that we continue
! 693: * through to the intervening-router nexthop code below. So as to
! 694: * ensure other paths to V may be used. This avoids unnecessary
! 695: * blackholes while OSPF is convergening.
! 696: *
! 697: * I.e. we may have arrived at this function, examining V -> W, via
! 698: * workable paths other than root -> V, and it's important to avoid
! 699: * getting "confused" by non-working root->V->W path - it's important
! 700: * to *not* lose the working non-root paths, just because of a
! 701: * non-viable root->V->W.
1.1 misho 702: *
1.1.1.3 ! misho 703: * See also bug #330 (required reading!), and:
1.1 misho 704: *
1.1.1.3 ! misho 705: * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
1.1 misho 706: */
707: if (added)
708: return added;
709: }
710:
711: /* 16.1.1 para 4. If there is at least one intervening router in the
712: * current shortest path between the destination and the root, the
713: * destination simply inherits the set of next hops from the
714: * parent.
715: */
716: if (IS_DEBUG_OSPF_EVENT)
717: zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
718:
719: for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
720: {
721: added = 1;
722: ospf_spf_add_parent (v, w, vp->nexthop, distance);
723: }
724:
725: return added;
726: }
727:
728: /* RFC2328 Section 16.1 (2).
729: * v is on the SPF tree. Examine the links in v's LSA. Update the list
730: * of candidates with any vertices not already on the list. If a lower-cost
731: * path is found to a vertex already on the candidate list, store the new cost.
732: */
733: static void
734: ospf_spf_next (struct vertex *v, struct ospf_area *area,
735: struct pqueue * candidate)
736: {
737: struct ospf_lsa *w_lsa = NULL;
738: u_char *p;
739: u_char *lim;
740: struct router_lsa_link *l = NULL;
741: struct in_addr *r;
1.1.1.3 ! misho 742: int type = 0, lsa_pos=-1, lsa_pos_next=0;
1.1 misho 743:
744: /* If this is a router-LSA, and bit V of the router-LSA (see Section
745: A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
746: if (v->type == OSPF_VERTEX_ROUTER)
747: {
748: if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
749: area->transit = OSPF_TRANSIT_TRUE;
750: }
751:
752: if (IS_DEBUG_OSPF_EVENT)
753: zlog_debug ("%s: Next vertex of %s vertex %s",
754: __func__,
755: v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
756: inet_ntoa(v->lsa->id));
757:
758: p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
759: lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
760:
761: while (p < lim)
762: {
763: struct vertex *w;
764: unsigned int distance;
765:
766: /* In case of V is Router-LSA. */
767: if (v->lsa->type == OSPF_ROUTER_LSA)
768: {
769: l = (struct router_lsa_link *) p;
770:
1.1.1.3 ! misho 771: lsa_pos = lsa_pos_next; /* LSA link position */
! 772: lsa_pos_next++;
1.1 misho 773: p += (OSPF_ROUTER_LSA_LINK_SIZE +
774: (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
775:
776: /* (a) If this is a link to a stub network, examine the next
777: link in V's LSA. Links to stub networks will be
778: considered in the second stage of the shortest path
779: calculation. */
780: if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
781: continue;
782:
783: /* Infinite distance links shouldn't be followed, except
784: * for local links (a stub-routed router still wants to
785: * calculate tree, so must follow its own links).
786: */
787: if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
788: continue;
789:
790: /* (b) Otherwise, W is a transit vertex (router or transit
791: network). Look up the vertex W's LSA (router-LSA or
792: network-LSA) in Area A's link state database. */
793: switch (type)
794: {
795: case LSA_LINK_TYPE_POINTOPOINT:
796: case LSA_LINK_TYPE_VIRTUALLINK:
797: if (type == LSA_LINK_TYPE_VIRTUALLINK)
798: {
799: if (IS_DEBUG_OSPF_EVENT)
800: zlog_debug ("looking up LSA through VL: %s",
801: inet_ntoa (l->link_id));
802: }
803:
804: w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
805: l->link_id);
806: if (w_lsa)
807: {
808: if (IS_DEBUG_OSPF_EVENT)
809: zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
810: }
811: break;
812: case LSA_LINK_TYPE_TRANSIT:
813: if (IS_DEBUG_OSPF_EVENT)
814: zlog_debug ("Looking up Network LSA, ID: %s",
815: inet_ntoa (l->link_id));
816: w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
817: l->link_id);
818: if (w_lsa)
819: if (IS_DEBUG_OSPF_EVENT)
820: zlog_debug ("found the LSA");
821: break;
822: default:
823: zlog_warn ("Invalid LSA link type %d", type);
824: continue;
825: }
826: }
827: else
828: {
829: /* In case of V is Network-LSA. */
830: r = (struct in_addr *) p;
831: p += sizeof (struct in_addr);
832:
833: /* Lookup the vertex W's LSA. */
834: w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
835: if (w_lsa)
836: {
837: if (IS_DEBUG_OSPF_EVENT)
838: zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
839: }
840: }
841:
842: /* (b cont.) If the LSA does not exist, or its LS age is equal
843: to MaxAge, or it does not have a link back to vertex V,
844: examine the next link in V's LSA.[23] */
845: if (w_lsa == NULL)
846: {
847: if (IS_DEBUG_OSPF_EVENT)
848: zlog_debug ("No LSA found");
849: continue;
850: }
851:
852: if (IS_LSA_MAXAGE (w_lsa))
853: {
854: if (IS_DEBUG_OSPF_EVENT)
855: zlog_debug ("LSA is MaxAge");
856: continue;
857: }
858:
859: if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
860: {
861: if (IS_DEBUG_OSPF_EVENT)
862: zlog_debug ("The LSA doesn't have a link back");
863: continue;
864: }
865:
866: /* (c) If vertex W is already on the shortest-path tree, examine
867: the next link in the LSA. */
868: if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
869: {
870: if (IS_DEBUG_OSPF_EVENT)
871: zlog_debug ("The LSA is already in SPF");
872: continue;
873: }
874:
875: /* (d) Calculate the link state cost D of the resulting path
876: from the root to vertex W. D is equal to the sum of the link
877: state cost of the (already calculated) shortest path to
878: vertex V and the advertised cost of the link between vertices
879: V and W. If D is: */
880:
881: /* calculate link cost D. */
882: if (v->lsa->type == OSPF_ROUTER_LSA)
883: distance = v->distance + ntohs (l->m[0].metric);
884: else /* v is not a Router-LSA */
885: distance = v->distance;
886:
887: /* Is there already vertex W in candidate list? */
888: if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
889: {
890: /* prepare vertex W. */
891: w = ospf_vertex_new (w_lsa);
892:
893: /* Calculate nexthop to W. */
1.1.1.3 ! misho 894: if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
1.1 misho 895: pqueue_enqueue (w, candidate);
896: else if (IS_DEBUG_OSPF_EVENT)
897: zlog_debug ("Nexthop Calc failed");
898: }
899: else if (w_lsa->stat >= 0)
900: {
901: /* Get the vertex from candidates. */
902: w = candidate->array[w_lsa->stat];
903:
904: /* if D is greater than. */
905: if (w->distance < distance)
906: {
907: continue;
908: }
909: /* equal to. */
910: else if (w->distance == distance)
911: {
912: /* Found an equal-cost path to W.
913: * Calculate nexthop of to W from V. */
1.1.1.3 ! misho 914: ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
1.1 misho 915: }
916: /* less than. */
917: else
918: {
919: /* Found a lower-cost path to W.
920: * nexthop_calculation is conditional, if it finds
921: * valid nexthop it will call spf_add_parents, which
922: * will flush the old parents
923: */
1.1.1.3 ! misho 924: if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
1.1 misho 925: /* Decrease the key of the node in the heap.
926: * trickle-sort it up towards root, just in case this
927: * node should now be the new root due the cost change.
928: * (next pqueu_{de,en}queue will fully re-heap the queue).
929: */
930: trickle_up (w_lsa->stat, candidate);
931: }
932: } /* end W is already on the candidate list */
933: } /* end loop over the links in V's LSA */
934: }
935:
936: static void
937: ospf_spf_dump (struct vertex *v, int i)
938: {
939: struct listnode *cnode;
940: struct listnode *nnode;
941: struct vertex_parent *parent;
942:
943: if (v->type == OSPF_VERTEX_ROUTER)
944: {
945: if (IS_DEBUG_OSPF_EVENT)
946: zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
947: }
948: else
949: {
950: struct network_lsa *lsa = (struct network_lsa *) v->lsa;
951: if (IS_DEBUG_OSPF_EVENT)
952: zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
953: ip_masklen (lsa->mask));
954: }
955:
956: if (IS_DEBUG_OSPF_EVENT)
957: for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
958: {
959: zlog_debug (" nexthop %p %s %s",
960: parent->nexthop,
961: inet_ntoa (parent->nexthop->router),
962: parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
963: : "NULL");
964: }
965:
966: i++;
967:
968: for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
969: ospf_spf_dump (v, i);
970: }
971:
972: /* Second stage of SPF calculation. */
973: static void
974: ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
975: struct route_table *rt,
976: int parent_is_root)
977: {
978: struct listnode *cnode, *cnnode;
979: struct vertex *child;
980:
981: if (IS_DEBUG_OSPF_EVENT)
982: zlog_debug ("ospf_process_stub():processing stubs for area %s",
983: inet_ntoa (area->area_id));
984: if (v->type == OSPF_VERTEX_ROUTER)
985: {
986: u_char *p;
987: u_char *lim;
988: struct router_lsa_link *l;
989: struct router_lsa *rlsa;
1.1.1.3 ! misho 990: int lsa_pos = 0;
1.1 misho 991:
992: if (IS_DEBUG_OSPF_EVENT)
993: zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
994: inet_ntoa (v->lsa->id));
995: rlsa = (struct router_lsa *) v->lsa;
996:
997:
998: if (IS_DEBUG_OSPF_EVENT)
999: zlog_debug ("ospf_process_stubs(): we have %d links to process",
1000: ntohs (rlsa->links));
1001: p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
1002: lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
1003:
1004: while (p < lim)
1005: {
1006: l = (struct router_lsa_link *) p;
1007:
1008: p += (OSPF_ROUTER_LSA_LINK_SIZE +
1009: (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1010:
1011: if (l->m[0].type == LSA_LINK_TYPE_STUB)
1.1.1.3 ! misho 1012: ospf_intra_add_stub (rt, l, v, area, parent_is_root, lsa_pos);
! 1013: lsa_pos++;
1.1 misho 1014: }
1015: }
1016:
1017: ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
1018:
1019: for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
1020: {
1021: if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
1022: continue;
1023:
1024: /* the first level of routers connected to the root
1025: * should have 'parent_is_root' set, including those
1026: * connected via a network vertex.
1027: */
1028: if (area->spf == v)
1029: parent_is_root = 1;
1030: else if (v->type == OSPF_VERTEX_ROUTER)
1031: parent_is_root = 0;
1032:
1033: ospf_spf_process_stubs (area, child, rt, parent_is_root);
1034:
1035: SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
1036: }
1037: }
1038:
1039: void
1040: ospf_rtrs_free (struct route_table *rtrs)
1041: {
1042: struct route_node *rn;
1043: struct list *or_list;
1044: struct ospf_route *or;
1045: struct listnode *node, *nnode;
1046:
1047: if (IS_DEBUG_OSPF_EVENT)
1048: zlog_debug ("Route: Router Routing Table free");
1049:
1050: for (rn = route_top (rtrs); rn; rn = route_next (rn))
1051: if ((or_list = rn->info) != NULL)
1052: {
1053: for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
1054: ospf_route_free (or);
1055:
1056: list_delete (or_list);
1057:
1058: /* Unlock the node. */
1059: rn->info = NULL;
1060: route_unlock_node (rn);
1061: }
1062: route_table_finish (rtrs);
1063: }
1064:
1.1.1.2 misho 1065: #if 0
1.1 misho 1066: static void
1067: ospf_rtrs_print (struct route_table *rtrs)
1068: {
1069: struct route_node *rn;
1070: struct list *or_list;
1071: struct listnode *ln;
1072: struct listnode *pnode;
1073: struct ospf_route *or;
1074: struct ospf_path *path;
1075: char buf1[BUFSIZ];
1076: char buf2[BUFSIZ];
1077:
1078: if (IS_DEBUG_OSPF_EVENT)
1079: zlog_debug ("ospf_rtrs_print() start");
1080:
1081: for (rn = route_top (rtrs); rn; rn = route_next (rn))
1082: if ((or_list = rn->info) != NULL)
1083: for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
1084: {
1085: switch (or->path_type)
1086: {
1087: case OSPF_PATH_INTRA_AREA:
1088: if (IS_DEBUG_OSPF_EVENT)
1089: zlog_debug ("%s [%d] area: %s",
1090: inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1091: or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1092: buf2, BUFSIZ));
1093: break;
1094: case OSPF_PATH_INTER_AREA:
1095: if (IS_DEBUG_OSPF_EVENT)
1096: zlog_debug ("%s IA [%d] area: %s",
1097: inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1098: or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1099: buf2, BUFSIZ));
1100: break;
1101: default:
1102: break;
1103: }
1104:
1105: for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
1106: {
1107: if (path->nexthop.s_addr == 0)
1108: {
1109: if (IS_DEBUG_OSPF_EVENT)
1110: zlog_debug (" directly attached to %s\r\n",
1111: ifindex2ifname (path->ifindex));
1112: }
1113: else
1114: {
1115: if (IS_DEBUG_OSPF_EVENT)
1116: zlog_debug (" via %s, %s\r\n",
1117: inet_ntoa (path->nexthop),
1118: ifindex2ifname (path->ifindex));
1119: }
1120: }
1121: }
1122:
1123: zlog_debug ("ospf_rtrs_print() end");
1124: }
1.1.1.2 misho 1125: #endif
1.1 misho 1126:
1127: /* Calculating the shortest-path tree for an area. */
1128: static void
1129: ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
1130: struct route_table *new_rtrs)
1131: {
1132: struct pqueue *candidate;
1133: struct vertex *v;
1134:
1135: if (IS_DEBUG_OSPF_EVENT)
1136: {
1137: zlog_debug ("ospf_spf_calculate: Start");
1138: zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1139: inet_ntoa (area->area_id));
1140: }
1141:
1142: /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1143: return this area's calculation. */
1144: if (!area->router_lsa_self)
1145: {
1146: if (IS_DEBUG_OSPF_EVENT)
1147: zlog_debug ("ospf_spf_calculate: "
1148: "Skip area %s's calculation due to empty router_lsa_self",
1149: inet_ntoa (area->area_id));
1150: return;
1151: }
1152:
1153: /* RFC2328 16.1. (1). */
1154: /* Initialize the algorithm's data structures. */
1155:
1156: /* This function scans all the LSA database and set the stat field to
1157: * LSA_SPF_NOT_EXPLORED. */
1158: ospf_lsdb_clean_stat (area->lsdb);
1159: /* Create a new heap for the candidates. */
1160: candidate = pqueue_create();
1161: candidate->cmp = cmp;
1162: candidate->update = update_stat;
1163:
1164: /* Initialize the shortest-path tree to only the root (which is the
1165: router doing the calculation). */
1166: ospf_spf_init (area);
1167: v = area->spf;
1168: /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1169: * spanning tree. */
1170: *(v->stat) = LSA_SPF_IN_SPFTREE;
1171:
1172: /* Set Area A's TransitCapability to FALSE. */
1173: area->transit = OSPF_TRANSIT_FALSE;
1174: area->shortcut_capability = 1;
1175:
1176: for (;;)
1177: {
1178: /* RFC2328 16.1. (2). */
1179: ospf_spf_next (v, area, candidate);
1180:
1181: /* RFC2328 16.1. (3). */
1182: /* If at this step the candidate list is empty, the shortest-
1183: path tree (of transit vertices) has been completely built and
1184: this stage of the procedure terminates. */
1185: if (candidate->size == 0)
1186: break;
1187:
1188: /* Otherwise, choose the vertex belonging to the candidate list
1189: that is closest to the root, and add it to the shortest-path
1190: tree (removing it from the candidate list in the
1191: process). */
1192: /* Extract from the candidates the node with the lower key. */
1193: v = (struct vertex *) pqueue_dequeue (candidate);
1194: /* Update stat field in vertex. */
1195: *(v->stat) = LSA_SPF_IN_SPFTREE;
1196:
1197: ospf_vertex_add_parent (v);
1198:
1199: /* RFC2328 16.1. (4). */
1200: if (v->type == OSPF_VERTEX_ROUTER)
1201: ospf_intra_add_router (new_rtrs, v, area);
1202: else
1203: ospf_intra_add_transit (new_table, v, area);
1204:
1205: /* RFC2328 16.1. (5). */
1206: /* Iterate the algorithm by returning to Step 2. */
1207:
1208: } /* end loop until no more candidate vertices */
1209:
1210: if (IS_DEBUG_OSPF_EVENT)
1211: {
1212: ospf_spf_dump (area->spf, 0);
1213: ospf_route_table_dump (new_table);
1214: }
1215:
1216: /* Second stage of SPF calculation procedure's */
1217: ospf_spf_process_stubs (area, area->spf, new_table, 0);
1218:
1219: /* Free candidate queue. */
1220: pqueue_delete (candidate);
1221:
1222: ospf_vertex_dump (__func__, area->spf, 0, 1);
1223: /* Free nexthop information, canonical versions of which are attached
1224: * the first level of router vertices attached to the root vertex, see
1225: * ospf_nexthop_calculation.
1226: */
1227: ospf_canonical_nexthops_free (area->spf);
1228:
1229: /* Free SPF vertices, but not the list. List has ospf_vertex_free
1230: * as deconstructor.
1231: */
1232: list_delete_all_node (&vertex_list);
1233:
1234: /* Increment SPF Calculation Counter. */
1235: area->spf_calculation++;
1236:
1237: quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
1238:
1239: if (IS_DEBUG_OSPF_EVENT)
1240: zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
1241: mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1242: }
1243:
1244: /* Timer for SPF calculation. */
1245: static int
1246: ospf_spf_calculate_timer (struct thread *thread)
1247: {
1248: struct ospf *ospf = THREAD_ARG (thread);
1249: struct route_table *new_table, *new_rtrs;
1250: struct ospf_area *area;
1251: struct listnode *node, *nnode;
1252:
1253: if (IS_DEBUG_OSPF_EVENT)
1254: zlog_debug ("SPF: Timer (SPF calculation expire)");
1255:
1256: ospf->t_spf_calc = NULL;
1257:
1258: /* Allocate new table tree. */
1259: new_table = route_table_init ();
1260: new_rtrs = route_table_init ();
1261:
1262: ospf_vl_unapprove (ospf);
1263:
1264: /* Calculate SPF for each area. */
1265: for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
1266: {
1267: /* Do backbone last, so as to first discover intra-area paths
1268: * for any back-bone virtual-links
1269: */
1270: if (ospf->backbone && ospf->backbone == area)
1271: continue;
1272:
1273: ospf_spf_calculate (area, new_table, new_rtrs);
1274: }
1275:
1276: /* SPF for backbone, if required */
1277: if (ospf->backbone)
1278: ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
1279:
1280: ospf_vl_shut_unapproved (ospf);
1281:
1282: ospf_ia_routing (ospf, new_table, new_rtrs);
1283:
1284: ospf_prune_unreachable_networks (new_table);
1285: ospf_prune_unreachable_routers (new_rtrs);
1286:
1287: /* AS-external-LSA calculation should not be performed here. */
1288:
1289: /* If new Router Route is installed,
1290: then schedule re-calculate External routes. */
1291: if (1)
1292: ospf_ase_calculate_schedule (ospf);
1293:
1294: ospf_ase_calculate_timer_add (ospf);
1295:
1296: /* Update routing table. */
1297: ospf_route_install (ospf, new_table);
1298:
1299: /* Update ABR/ASBR routing table */
1300: if (ospf->old_rtrs)
1301: {
1302: /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1303: /* ospf_route_delete (ospf->old_rtrs); */
1304: ospf_rtrs_free (ospf->old_rtrs);
1305: }
1306:
1307: ospf->old_rtrs = ospf->new_rtrs;
1308: ospf->new_rtrs = new_rtrs;
1309:
1310: if (IS_OSPF_ABR (ospf))
1311: ospf_abr_task (ospf);
1312:
1313: if (IS_DEBUG_OSPF_EVENT)
1314: zlog_debug ("SPF: calculation complete");
1315:
1316: return 0;
1317: }
1318:
1319: /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1320: set timer for SPF calc. */
1321: void
1322: ospf_spf_calculate_schedule (struct ospf *ospf)
1323: {
1324: unsigned long delay, elapsed, ht;
1325: struct timeval result;
1326:
1327: if (IS_DEBUG_OSPF_EVENT)
1328: zlog_debug ("SPF: calculation timer scheduled");
1329:
1330: /* OSPF instance does not exist. */
1331: if (ospf == NULL)
1332: return;
1333:
1334: /* SPF calculation timer is already scheduled. */
1335: if (ospf->t_spf_calc)
1336: {
1337: if (IS_DEBUG_OSPF_EVENT)
1338: zlog_debug ("SPF: calculation timer is already scheduled: %p",
1339: ospf->t_spf_calc);
1340: return;
1341: }
1342:
1343: /* XXX Monotic timers: we only care about relative time here. */
1344: result = tv_sub (recent_relative_time (), ospf->ts_spf);
1345:
1346: elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
1347: ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
1348:
1349: if (ht > ospf->spf_max_holdtime)
1350: ht = ospf->spf_max_holdtime;
1351:
1352: /* Get SPF calculation delay time. */
1353: if (elapsed < ht)
1354: {
1355: /* Got an event within the hold time of last SPF. We need to
1356: * increase the hold_multiplier, if it's not already at/past
1357: * maximum value, and wasn't already increased..
1358: */
1359: if (ht < ospf->spf_max_holdtime)
1360: ospf->spf_hold_multiplier++;
1361:
1362: /* always honour the SPF initial delay */
1363: if ( (ht - elapsed) < ospf->spf_delay)
1364: delay = ospf->spf_delay;
1365: else
1366: delay = ht - elapsed;
1367: }
1368: else
1369: {
1370: /* Event is past required hold-time of last SPF */
1371: delay = ospf->spf_delay;
1372: ospf->spf_hold_multiplier = 1;
1373: }
1374:
1375: if (IS_DEBUG_OSPF_EVENT)
1376: zlog_debug ("SPF: calculation timer delay = %ld", delay);
1377:
1378: ospf->t_spf_calc =
1379: thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
1380: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf_spf.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / ospfd