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