Annotation of embedaddon/quagga/ospfd/ospf_spf.c, revision 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