Annotation of embedaddon/quagga/ospfd/ospf_spf.c, revision 1.1.1.4
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:
1.1.1.4 ! misho 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
! 54: ospf_clear_spf_reason_flags ()
! 55: {
! 56: spf_reason_flags = 0;
! 57: }
! 58:
! 59: static void
! 60: ospf_spf_set_reason (ospf_spf_reason_t reason)
! 61: {
! 62: spf_reason_flags |= 1 << reason;
! 63: }
! 64:
! 65: static void
! 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:
1.1 misho 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 };
1.1.1.4 ! misho 98:
1.1 misho 99: /* Heap related functions, for the managment of the candidates, to
100: * be used with pqueue. */
101: static int
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
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: }
1.1.1.4 ! misho 136:
1.1 misho 137: static struct vertex_nexthop *
138: vertex_nexthop_new (void)
139: {
140: return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
141: }
142:
143: static void
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
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: }
1.1.1.4 ! misho 180:
1.1 misho 181: /* TODO: Parent list should be excised, in favour of maintaining only
182: * vertex_nexthop, with refcounts.
183: */
184: static struct vertex_parent *
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
201: vertex_parent_free (void *p)
202: {
203: XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
204: }
1.1.1.4 ! misho 205:
1.1 misho 206: static struct vertex *
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
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
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
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: }
1.1.1.4 ! misho 322:
1.1 misho 323: static void
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
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 *
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
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
464: ospf_spf_add_parent (struct vertex *v, struct vertex *w,
465: struct vertex_nexthop *newhop,
466: unsigned int distance)
467: {
1.1.1.3 misho 468: struct vertex_parent *vp, *wp;
469: struct listnode *node;
1.1 misho 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:
1.1.1.3 misho 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:
1.1 misho 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
534: ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
535: struct vertex *w, struct router_lsa_link *l,
1.1.1.3 misho 536: unsigned int distance, int lsa_pos)
1.1 misho 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;
1.1.1.3 misho 543: char buf1[BUFSIZ];
544: char buf2[BUFSIZ];
1.1 misho 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:
1.1.1.3 misho 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:
1.1 misho 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: {
1.1.1.4 ! misho 593: struct in_addr nexthop = { .s_addr = 0 };
1.1.1.3 misho 594:
1.1 misho 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
1.1.1.3 misho 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
1.1 misho 608: subnet declared by the PtMP link, then that link
1.1.1.3 misho 609: is a constituent of the PtMP link, and its address is
1.1 misho 610: a nexthop address for V.
611: */
1.1.1.3 misho 612: if (oi->type == OSPF_IFTYPE_POINTOPOINT)
613: {
1.1.1.4 ! misho 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: }
1.1.1.3 misho 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: }
1.1 misho 653:
1.1.1.3 misho 654: if (added)
1.1 misho 655: {
656: /* found all necessary info to build nexthop */
657: nh = vertex_nexthop_new ();
658: nh->oi = oi;
1.1.1.3 misho 659: nh->router = nexthop;
1.1 misho 660: ospf_spf_add_parent (v, w, nh, distance);
661: return 1;
662: }
663: else
1.1.1.3 misho 664: zlog_info("%s: could not determine nexthop for link %s",
665: __func__, oi->ifp->name);
1.1 misho 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);
1.1.1.3 misho 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;
1.1 misho 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: }
1.1.1.3 misho 735: /* Note lack of return is deliberate. See next comment. */
736: }
1.1 misho 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
1.1.1.3 misho 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.
1.1 misho 759: *
1.1.1.3 misho 760: * See also bug #330 (required reading!), and:
1.1 misho 761: *
1.1.1.3 misho 762: * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
1.1 misho 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
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;
1.1.1.3 misho 799: int type = 0, lsa_pos=-1, lsa_pos_next=0;
1.1 misho 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:
1.1.1.3 misho 828: lsa_pos = lsa_pos_next; /* LSA link position */
829: lsa_pos_next++;
1.1 misho 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. */
1.1.1.3 misho 951: if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
1.1 misho 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. */
1.1.1.3 misho 971: ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
1.1 misho 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: */
1.1.1.3 misho 981: if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
1.1 misho 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
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",
1.1.1.4 ! misho 1017: (void *)parent->nexthop,
1.1 misho 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
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;
1.1.1.3 misho 1047: int lsa_pos = 0;
1.1 misho 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)
1.1.1.3 misho 1069: ospf_intra_add_stub (rt, l, v, area, parent_is_root, lsa_pos);
1070: lsa_pos++;
1.1 misho 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
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:
1.1.1.2 misho 1122: #if 0
1.1 misho 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: }
1.1.1.2 misho 1182: #endif
1.1 misho 1183:
1184: /* Calculating the shortest-path tree for an area. */
1185: static void
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);
1.1.1.4 ! misho 1278:
1.1 misho 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);
1.1.1.4 ! misho 1285:
1.1 misho 1286: /* Increment SPF Calculation Counter. */
1287: area->spf_calculation++;
1288:
1289: quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
1.1.1.4 ! misho 1290: area->ts_spf = area->ospf->ts_spf;
1.1 misho 1291:
1292: if (IS_DEBUG_OSPF_EVENT)
1293: zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
1294: mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1.1.1.4 ! misho 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);
1.1 misho 1300: }
1.1.1.4 ! misho 1301:
1.1 misho 1302: /* Timer for SPF calculation. */
1303: static int
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;
1.1.1.4 ! misho 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:
1.1 misho 1316: if (IS_DEBUG_OSPF_EVENT)
1317: zlog_debug ("SPF: Timer (SPF calculation expire)");
1318:
1319: ospf->t_spf_calc = NULL;
1320:
1.1.1.4 ! misho 1321: quagga_gettime (QUAGGA_CLK_MONOTONIC, &spf_start_time);
1.1 misho 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;
1.1.1.4 ! misho 1336:
1.1 misho 1337: ospf_spf_calculate (area, new_table, new_rtrs);
1.1.1.4 ! misho 1338: areas_processed++;
1.1 misho 1339: }
1.1.1.4 ! misho 1340:
1.1 misho 1341: /* SPF for backbone, if required */
1342: if (ospf->backbone)
1.1.1.4 ! misho 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:
1.1 misho 1351: ospf_vl_shut_unapproved (ospf);
1352:
1.1.1.4 ! misho 1353: start_time = stop_time; /* saving a call */
! 1354:
1.1 misho 1355: ospf_ia_routing (ospf, new_table, new_rtrs);
1356:
1.1.1.4 ! misho 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);
1.1 misho 1361: ospf_prune_unreachable_networks (new_table);
1362: ospf_prune_unreachable_routers (new_rtrs);
1363:
1.1.1.4 ! misho 1364: quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
! 1365: prune_time = timeval_elapsed (stop_time, start_time);
1.1 misho 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:
1.1.1.4 ! misho 1375: quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
! 1376:
1.1 misho 1377: /* Update routing table. */
1378: ospf_route_install (ospf, new_table);
1379:
1.1.1.4 ! misho 1380: quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
! 1381: rt_time = timeval_elapsed (stop_time, start_time);
1.1 misho 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:
1.1.1.4 ! misho 1393: quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
1.1 misho 1394: if (IS_OSPF_ABR (ospf))
1395: ospf_abr_task (ospf);
1396:
1.1.1.4 ! misho 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:
1.1 misho 1407: if (IS_DEBUG_OSPF_EVENT)
1.1.1.4 ! misho 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 ();
1.1 misho 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
1.1.1.4 ! misho 1428: ospf_spf_calculate_schedule (struct ospf *ospf, ospf_spf_reason_t reason)
1.1 misho 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:
1.1.1.4 ! misho 1440: ospf_spf_set_reason (reason);
! 1441:
1.1 misho 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",
1.1.1.4 ! misho 1447: (void *)ospf->t_spf_calc);
1.1 misho 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);
1.1.1.4 ! misho 1485:
! 1486: zlog_info ("SPF: Scheduled in %ld msec", delay);
1.1 misho 1487:
1488: ospf->t_spf_calc =
1489: thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
1490: }
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