Annotation of embedaddon/quagga/ospfd/ospf_route.c, revision 1.1
1.1 ! misho 1: /*
! 2: * OSPF routing table.
! 3: * Copyright (C) 1999, 2000 Toshiaki Takada
! 4: *
! 5: * This file is part of GNU Zebra.
! 6: *
! 7: * GNU Zebra is free software; you can redistribute it and/or modify it
! 8: * under the terms of the GNU General Public License as published by the
! 9: * Free Software Foundation; either version 2, or (at your option) any
! 10: * later version.
! 11: *
! 12: * GNU Zebra is distributed in the hope that it will be useful, but
! 13: * WITHOUT ANY WARRANTY; without even the implied warranty of
! 14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
! 15: * General Public License for more details.
! 16: *
! 17: * You should have received a copy of the GNU General Public License
! 18: * along with GNU Zebra; see the file COPYING. If not, write to the Free
! 19: * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
! 20: * 02111-1307, USA.
! 21: */
! 22:
! 23: #include <zebra.h>
! 24:
! 25: #include "prefix.h"
! 26: #include "table.h"
! 27: #include "memory.h"
! 28: #include "linklist.h"
! 29: #include "log.h"
! 30: #include "if.h"
! 31: #include "command.h"
! 32: #include "sockunion.h"
! 33:
! 34: #include "ospfd/ospfd.h"
! 35: #include "ospfd/ospf_interface.h"
! 36: #include "ospfd/ospf_asbr.h"
! 37: #include "ospfd/ospf_lsa.h"
! 38: #include "ospfd/ospf_route.h"
! 39: #include "ospfd/ospf_spf.h"
! 40: #include "ospfd/ospf_zebra.h"
! 41: #include "ospfd/ospf_dump.h"
! 42:
! 43: struct ospf_route *
! 44: ospf_route_new ()
! 45: {
! 46: struct ospf_route *new;
! 47:
! 48: new = XCALLOC (MTYPE_OSPF_ROUTE, sizeof (struct ospf_route));
! 49:
! 50: new->ctime = quagga_time (NULL);
! 51: new->mtime = new->ctime;
! 52: new->paths = list_new ();
! 53: new->paths->del = (void (*) (void *))ospf_path_free;
! 54:
! 55: return new;
! 56: }
! 57:
! 58: void
! 59: ospf_route_free (struct ospf_route *or)
! 60: {
! 61: if (or->paths)
! 62: list_delete (or->paths);
! 63:
! 64: XFREE (MTYPE_OSPF_ROUTE, or);
! 65: }
! 66:
! 67: struct ospf_path *
! 68: ospf_path_new ()
! 69: {
! 70: struct ospf_path *new;
! 71:
! 72: new = XCALLOC (MTYPE_OSPF_PATH, sizeof (struct ospf_path));
! 73:
! 74: return new;
! 75: }
! 76:
! 77: static struct ospf_path *
! 78: ospf_path_dup (struct ospf_path *path)
! 79: {
! 80: struct ospf_path *new;
! 81:
! 82: new = ospf_path_new ();
! 83: memcpy (new, path, sizeof (struct ospf_path));
! 84:
! 85: return new;
! 86: }
! 87:
! 88: void
! 89: ospf_path_free (struct ospf_path *op)
! 90: {
! 91: XFREE (MTYPE_OSPF_PATH, op);
! 92: }
! 93:
! 94: void
! 95: ospf_route_delete (struct route_table *rt)
! 96: {
! 97: struct route_node *rn;
! 98: struct ospf_route *or;
! 99:
! 100: for (rn = route_top (rt); rn; rn = route_next (rn))
! 101: if ((or = rn->info) != NULL)
! 102: {
! 103: if (or->type == OSPF_DESTINATION_NETWORK)
! 104: ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p,
! 105: or);
! 106: else if (or->type == OSPF_DESTINATION_DISCARD)
! 107: ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
! 108: }
! 109: }
! 110:
! 111: void
! 112: ospf_route_table_free (struct route_table *rt)
! 113: {
! 114: struct route_node *rn;
! 115: struct ospf_route *or;
! 116:
! 117: for (rn = route_top (rt); rn; rn = route_next (rn))
! 118: if ((or = rn->info) != NULL)
! 119: {
! 120: ospf_route_free (or);
! 121:
! 122: rn->info = NULL;
! 123: route_unlock_node (rn);
! 124: }
! 125:
! 126: route_table_finish (rt);
! 127: }
! 128:
! 129: /* If a prefix and a nexthop match any route in the routing table,
! 130: then return 1, otherwise return 0. */
! 131: int
! 132: ospf_route_match_same (struct route_table *rt, struct prefix_ipv4 *prefix,
! 133: struct ospf_route *newor)
! 134: {
! 135: struct route_node *rn;
! 136: struct ospf_route *or;
! 137: struct ospf_path *op;
! 138: struct ospf_path *newop;
! 139: struct listnode *n1;
! 140: struct listnode *n2;
! 141:
! 142: if (! rt || ! prefix)
! 143: return 0;
! 144:
! 145: rn = route_node_lookup (rt, (struct prefix *) prefix);
! 146: if (! rn || ! rn->info)
! 147: return 0;
! 148:
! 149: route_unlock_node (rn);
! 150:
! 151: or = rn->info;
! 152: if (or->type == newor->type && or->cost == newor->cost)
! 153: {
! 154: if (or->type == OSPF_DESTINATION_NETWORK)
! 155: {
! 156: if (or->paths->count != newor->paths->count)
! 157: return 0;
! 158:
! 159: /* Check each path. */
! 160: for (n1 = listhead (or->paths), n2 = listhead (newor->paths);
! 161: n1 && n2; n1 = listnextnode (n1), n2 = listnextnode (n2))
! 162: {
! 163: op = listgetdata (n1);
! 164: newop = listgetdata (n2);
! 165:
! 166: if (! IPV4_ADDR_SAME (&op->nexthop, &newop->nexthop))
! 167: return 0;
! 168: if (op->ifindex != newop->ifindex)
! 169: return 0;
! 170: }
! 171: return 1;
! 172: }
! 173: else if (prefix_same (&rn->p, (struct prefix *) prefix))
! 174: return 1;
! 175: }
! 176: return 0;
! 177: }
! 178:
! 179: /* delete routes generated from AS-External routes if there is a inter/intra
! 180: * area route
! 181: */
! 182: static void
! 183: ospf_route_delete_same_ext(struct route_table *external_routes,
! 184: struct route_table *routes)
! 185: {
! 186: struct route_node *rn,
! 187: *ext_rn;
! 188:
! 189: if ( (external_routes == NULL) || (routes == NULL) )
! 190: return;
! 191:
! 192: /* Remove deleted routes */
! 193: for ( rn = route_top (routes); rn; rn = route_next (rn) )
! 194: {
! 195: if (rn && rn->info)
! 196: {
! 197: struct prefix_ipv4 *p = (struct prefix_ipv4 *)(&rn->p);
! 198: if ( (ext_rn = route_node_lookup (external_routes, (struct prefix *)p)) )
! 199: {
! 200: if (ext_rn->info)
! 201: {
! 202: ospf_zebra_delete (p, ext_rn->info);
! 203: ospf_route_free( ext_rn->info);
! 204: ext_rn->info = NULL;
! 205: }
! 206: route_unlock_node (ext_rn);
! 207: }
! 208: }
! 209: }
! 210: }
! 211:
! 212: /* rt: Old, cmprt: New */
! 213: static void
! 214: ospf_route_delete_uniq (struct route_table *rt, struct route_table *cmprt)
! 215: {
! 216: struct route_node *rn;
! 217: struct ospf_route *or;
! 218:
! 219: for (rn = route_top (rt); rn; rn = route_next (rn))
! 220: if ((or = rn->info) != NULL)
! 221: if (or->path_type == OSPF_PATH_INTRA_AREA ||
! 222: or->path_type == OSPF_PATH_INTER_AREA)
! 223: {
! 224: if (or->type == OSPF_DESTINATION_NETWORK)
! 225: {
! 226: if (! ospf_route_match_same (cmprt,
! 227: (struct prefix_ipv4 *) &rn->p, or))
! 228: ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p, or);
! 229: }
! 230: else if (or->type == OSPF_DESTINATION_DISCARD)
! 231: if (! ospf_route_match_same (cmprt,
! 232: (struct prefix_ipv4 *) &rn->p, or))
! 233: ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
! 234: }
! 235: }
! 236:
! 237: /* Install routes to table. */
! 238: void
! 239: ospf_route_install (struct ospf *ospf, struct route_table *rt)
! 240: {
! 241: struct route_node *rn;
! 242: struct ospf_route *or;
! 243:
! 244: /* rt contains new routing table, new_table contains an old one.
! 245: updating pointers */
! 246: if (ospf->old_table)
! 247: ospf_route_table_free (ospf->old_table);
! 248:
! 249: ospf->old_table = ospf->new_table;
! 250: ospf->new_table = rt;
! 251:
! 252: /* Delete old routes. */
! 253: if (ospf->old_table)
! 254: ospf_route_delete_uniq (ospf->old_table, rt);
! 255: if (ospf->old_external_route)
! 256: ospf_route_delete_same_ext (ospf->old_external_route, rt);
! 257:
! 258: /* Install new routes. */
! 259: for (rn = route_top (rt); rn; rn = route_next (rn))
! 260: if ((or = rn->info) != NULL)
! 261: {
! 262: if (or->type == OSPF_DESTINATION_NETWORK)
! 263: {
! 264: if (! ospf_route_match_same (ospf->old_table,
! 265: (struct prefix_ipv4 *)&rn->p, or))
! 266: ospf_zebra_add ((struct prefix_ipv4 *) &rn->p, or);
! 267: }
! 268: else if (or->type == OSPF_DESTINATION_DISCARD)
! 269: if (! ospf_route_match_same (ospf->old_table,
! 270: (struct prefix_ipv4 *) &rn->p, or))
! 271: ospf_zebra_add_discard ((struct prefix_ipv4 *) &rn->p);
! 272: }
! 273: }
! 274:
! 275: static void
! 276: ospf_intra_route_add (struct route_table *rt, struct vertex *v,
! 277: struct ospf_area *area)
! 278: {
! 279: struct route_node *rn;
! 280: struct ospf_route *or;
! 281: struct prefix_ipv4 p;
! 282: struct ospf_path *path;
! 283: struct vertex_parent *parent;
! 284: struct listnode *node, *nnode;
! 285:
! 286: p.family = AF_INET;
! 287: p.prefix = v->id;
! 288: if (v->type == OSPF_VERTEX_ROUTER)
! 289: p.prefixlen = IPV4_MAX_BITLEN;
! 290: else
! 291: {
! 292: struct network_lsa *lsa = (struct network_lsa *) v->lsa;
! 293: p.prefixlen = ip_masklen (lsa->mask);
! 294: }
! 295: apply_mask_ipv4 (&p);
! 296:
! 297: rn = route_node_get (rt, (struct prefix *) &p);
! 298: if (rn->info)
! 299: {
! 300: zlog_warn ("Same routing information exists for %s", inet_ntoa (v->id));
! 301: route_unlock_node (rn);
! 302: return;
! 303: }
! 304:
! 305: or = ospf_route_new ();
! 306:
! 307: if (v->type == OSPF_VERTEX_NETWORK)
! 308: {
! 309: or->type = OSPF_DESTINATION_NETWORK;
! 310:
! 311: for (ALL_LIST_ELEMENTS (v->parents, node, nnode, parent))
! 312: {
! 313: path = ospf_path_new ();
! 314: path->nexthop = parent->nexthop->router;
! 315: listnode_add (or->paths, path);
! 316: }
! 317: }
! 318: else
! 319: or->type = OSPF_DESTINATION_ROUTER;
! 320:
! 321: or->id = v->id;
! 322: or->u.std.area_id = area->area_id;
! 323: or->u.std.external_routing= area->external_routing;
! 324: or->path_type = OSPF_PATH_INTRA_AREA;
! 325: or->cost = v->distance;
! 326:
! 327: rn->info = or;
! 328: }
! 329:
! 330: /* RFC2328 16.1. (4). For "router". */
! 331: void
! 332: ospf_intra_add_router (struct route_table *rt, struct vertex *v,
! 333: struct ospf_area *area)
! 334: {
! 335: struct route_node *rn;
! 336: struct ospf_route *or;
! 337: struct prefix_ipv4 p;
! 338: struct router_lsa *lsa;
! 339:
! 340: if (IS_DEBUG_OSPF_EVENT)
! 341: zlog_debug ("ospf_intra_add_router: Start");
! 342:
! 343: lsa = (struct router_lsa *) v->lsa;
! 344:
! 345: if (IS_DEBUG_OSPF_EVENT)
! 346: zlog_debug ("ospf_intra_add_router: LS ID: %s",
! 347: inet_ntoa (lsa->header.id));
! 348:
! 349: if (!OSPF_IS_AREA_BACKBONE(area))
! 350: ospf_vl_up_check (area, lsa->header.id, v);
! 351:
! 352: if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT))
! 353: area->shortcut_capability = 0;
! 354:
! 355: /* If the newly added vertex is an area border router or AS boundary
! 356: router, a routing table entry is added whose destination type is
! 357: "router". */
! 358: if (! IS_ROUTER_LSA_BORDER (lsa) && ! IS_ROUTER_LSA_EXTERNAL (lsa))
! 359: {
! 360: if (IS_DEBUG_OSPF_EVENT)
! 361: zlog_debug ("ospf_intra_add_router: "
! 362: "this router is neither ASBR nor ABR, skipping it");
! 363: return;
! 364: }
! 365:
! 366: /* Update ABR and ASBR count in this area. */
! 367: if (IS_ROUTER_LSA_BORDER (lsa))
! 368: area->abr_count++;
! 369: if (IS_ROUTER_LSA_EXTERNAL (lsa))
! 370: area->asbr_count++;
! 371:
! 372: /* The Options field found in the associated router-LSA is copied
! 373: into the routing table entry's Optional capabilities field. Call
! 374: the newly added vertex Router X. */
! 375: or = ospf_route_new ();
! 376:
! 377: or->id = v->id;
! 378: or->u.std.area_id = area->area_id;
! 379: or->u.std.external_routing = area->external_routing;
! 380: or->path_type = OSPF_PATH_INTRA_AREA;
! 381: or->cost = v->distance;
! 382: or->type = OSPF_DESTINATION_ROUTER;
! 383: or->u.std.origin = (struct lsa_header *) lsa;
! 384: or->u.std.options = lsa->header.options;
! 385: or->u.std.flags = lsa->flags;
! 386:
! 387: /* If Router X is the endpoint of one of the calculating router's
! 388: virtual links, and the virtual link uses Area A as Transit area:
! 389: the virtual link is declared up, the IP address of the virtual
! 390: interface is set to the IP address of the outgoing interface
! 391: calculated above for Router X, and the virtual neighbor's IP
! 392: address is set to Router X's interface address (contained in
! 393: Router X's router-LSA) that points back to the root of the
! 394: shortest- path tree; equivalently, this is the interface that
! 395: points back to Router X's parent vertex on the shortest-path tree
! 396: (similar to the calculation in Section 16.1.1). */
! 397:
! 398: p.family = AF_INET;
! 399: p.prefix = v->id;
! 400: p.prefixlen = IPV4_MAX_BITLEN;
! 401:
! 402: if (IS_DEBUG_OSPF_EVENT)
! 403: zlog_debug ("ospf_intra_add_router: talking about %s/%d",
! 404: inet_ntoa (p.prefix), p.prefixlen);
! 405:
! 406: rn = route_node_get (rt, (struct prefix *) &p);
! 407:
! 408: /* Note that we keep all routes to ABRs and ASBRs, not only the best */
! 409: if (rn->info == NULL)
! 410: rn->info = list_new ();
! 411: else
! 412: route_unlock_node (rn);
! 413:
! 414: ospf_route_copy_nexthops_from_vertex (or, v);
! 415:
! 416: listnode_add (rn->info, or);
! 417:
! 418: if (IS_DEBUG_OSPF_EVENT)
! 419: zlog_debug ("ospf_intra_add_router: Stop");
! 420: }
! 421:
! 422: /* RFC2328 16.1. (4). For transit network. */
! 423: void
! 424: ospf_intra_add_transit (struct route_table *rt, struct vertex *v,
! 425: struct ospf_area *area)
! 426: {
! 427: struct route_node *rn;
! 428: struct ospf_route *or;
! 429: struct prefix_ipv4 p;
! 430: struct network_lsa *lsa;
! 431:
! 432: lsa = (struct network_lsa*) v->lsa;
! 433:
! 434: /* If the newly added vertex is a transit network, the routing table
! 435: entry for the network is located. The entry's Destination ID is
! 436: the IP network number, which can be obtained by masking the
! 437: Vertex ID (Link State ID) with its associated subnet mask (found
! 438: in the body of the associated network-LSA). */
! 439: p.family = AF_INET;
! 440: p.prefix = v->id;
! 441: p.prefixlen = ip_masklen (lsa->mask);
! 442: apply_mask_ipv4 (&p);
! 443:
! 444: rn = route_node_get (rt, (struct prefix *) &p);
! 445:
! 446: /* If the routing table entry already exists (i.e., there is already
! 447: an intra-area route to the destination installed in the routing
! 448: table), multiple vertices have mapped to the same IP network.
! 449: For example, this can occur when a new Designated Router is being
! 450: established. In this case, the current routing table entry
! 451: should be overwritten if and only if the newly found path is just
! 452: as short and the current routing table entry's Link State Origin
! 453: has a smaller Link State ID than the newly added vertex' LSA. */
! 454: if (rn->info)
! 455: {
! 456: struct ospf_route *cur_or;
! 457:
! 458: route_unlock_node (rn);
! 459: cur_or = rn->info;
! 460:
! 461: if (v->distance > cur_or->cost ||
! 462: IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) > 0)
! 463: return;
! 464:
! 465: ospf_route_free (rn->info);
! 466: }
! 467:
! 468: or = ospf_route_new ();
! 469:
! 470: or->id = v->id;
! 471: or->u.std.area_id = area->area_id;
! 472: or->u.std.external_routing = area->external_routing;
! 473: or->path_type = OSPF_PATH_INTRA_AREA;
! 474: or->cost = v->distance;
! 475: or->type = OSPF_DESTINATION_NETWORK;
! 476: or->u.std.origin = (struct lsa_header *) lsa;
! 477:
! 478: ospf_route_copy_nexthops_from_vertex (or, v);
! 479:
! 480: rn->info = or;
! 481: }
! 482:
! 483: /* RFC2328 16.1. second stage. */
! 484: void
! 485: ospf_intra_add_stub (struct route_table *rt, struct router_lsa_link *link,
! 486: struct vertex *v, struct ospf_area *area,
! 487: int parent_is_root)
! 488: {
! 489: u_int32_t cost;
! 490: struct route_node *rn;
! 491: struct ospf_route *or;
! 492: struct prefix_ipv4 p;
! 493: struct router_lsa *lsa;
! 494: struct ospf_interface *oi;
! 495: struct ospf_path *path;
! 496:
! 497: if (IS_DEBUG_OSPF_EVENT)
! 498: zlog_debug ("ospf_intra_add_stub(): Start");
! 499:
! 500: lsa = (struct router_lsa *) v->lsa;
! 501:
! 502: p.family = AF_INET;
! 503: p.prefix = link->link_id;
! 504: p.prefixlen = ip_masklen (link->link_data);
! 505: apply_mask_ipv4 (&p);
! 506:
! 507: if (IS_DEBUG_OSPF_EVENT)
! 508: zlog_debug ("ospf_intra_add_stub(): processing route to %s/%d",
! 509: inet_ntoa (p.prefix), p.prefixlen);
! 510:
! 511: /* (1) Calculate the distance D of stub network from the root. D is
! 512: equal to the distance from the root to the router vertex
! 513: (calculated in stage 1), plus the stub network link's advertised
! 514: cost. */
! 515: cost = v->distance + ntohs (link->m[0].metric);
! 516:
! 517: if (IS_DEBUG_OSPF_EVENT)
! 518: zlog_debug ("ospf_intra_add_stub(): calculated cost is %d + %d = %d",
! 519: v->distance, ntohs(link->m[0].metric), cost);
! 520:
! 521: /* PtP links with /32 masks adds host routes to remote, directly
! 522: * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
! 523: * Such routes can just be ignored for the sake of tidyness.
! 524: */
! 525: if (parent_is_root && link->link_data.s_addr == 0xffffffff &&
! 526: ospf_if_lookup_by_local_addr (area->ospf, NULL, link->link_id))
! 527: {
! 528: if (IS_DEBUG_OSPF_EVENT)
! 529: zlog_debug ("%s: ignoring host route %s/32 to self.",
! 530: __func__, inet_ntoa (link->link_id));
! 531: return;
! 532: }
! 533:
! 534: rn = route_node_get (rt, (struct prefix *) &p);
! 535:
! 536: /* Lookup current routing table. */
! 537: if (rn->info)
! 538: {
! 539: struct ospf_route *cur_or;
! 540:
! 541: route_unlock_node (rn);
! 542:
! 543: cur_or = rn->info;
! 544:
! 545: if (IS_DEBUG_OSPF_EVENT)
! 546: zlog_debug ("ospf_intra_add_stub(): "
! 547: "another route to the same prefix found with cost %u",
! 548: cur_or->cost);
! 549:
! 550: /* Compare this distance to the current best cost to the stub
! 551: network. This is done by looking up the stub network's
! 552: current routing table entry. If the calculated distance D is
! 553: larger, go on to examine the next stub network link in the
! 554: LSA. */
! 555: if (cost > cur_or->cost)
! 556: {
! 557: if (IS_DEBUG_OSPF_EVENT)
! 558: zlog_debug ("ospf_intra_add_stub(): old route is better, exit");
! 559: return;
! 560: }
! 561:
! 562: /* (2) If this step is reached, the stub network's routing table
! 563: entry must be updated. Calculate the set of next hops that
! 564: would result from using the stub network link. This
! 565: calculation is shown in Section 16.1.1; input to this
! 566: calculation is the destination (the stub network) and the
! 567: parent vertex (the router vertex). If the distance D is the
! 568: same as the current routing table cost, simply add this set
! 569: of next hops to the routing table entry's list of next hops.
! 570: In this case, the routing table already has a Link State
! 571: Origin. If this Link State Origin is a router-LSA whose Link
! 572: State ID is smaller than V's Router ID, reset the Link State
! 573: Origin to V's router-LSA. */
! 574:
! 575: if (cost == cur_or->cost)
! 576: {
! 577: if (IS_DEBUG_OSPF_EVENT)
! 578: zlog_debug ("ospf_intra_add_stub(): routes are equal, merge");
! 579:
! 580: ospf_route_copy_nexthops_from_vertex (cur_or, v);
! 581:
! 582: if (IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) < 0)
! 583: cur_or->u.std.origin = (struct lsa_header *) lsa;
! 584: return;
! 585: }
! 586:
! 587: /* Otherwise D is smaller than the routing table cost.
! 588: Overwrite the current routing table entry by setting the
! 589: routing table entry's cost to D, and by setting the entry's
! 590: list of next hops to the newly calculated set. Set the
! 591: routing table entry's Link State Origin to V's router-LSA.
! 592: Then go on to examine the next stub network link. */
! 593:
! 594: if (cost < cur_or->cost)
! 595: {
! 596: if (IS_DEBUG_OSPF_EVENT)
! 597: zlog_debug ("ospf_intra_add_stub(): new route is better, set it");
! 598:
! 599: cur_or->cost = cost;
! 600:
! 601: list_delete_all_node (cur_or->paths);
! 602:
! 603: ospf_route_copy_nexthops_from_vertex (cur_or, v);
! 604:
! 605: cur_or->u.std.origin = (struct lsa_header *) lsa;
! 606: return;
! 607: }
! 608: }
! 609:
! 610: if (IS_DEBUG_OSPF_EVENT)
! 611: zlog_debug ("ospf_intra_add_stub(): installing new route");
! 612:
! 613: or = ospf_route_new ();
! 614:
! 615: or->id = v->id;
! 616: or->u.std.area_id = area->area_id;
! 617: or->u.std.external_routing = area->external_routing;
! 618: or->path_type = OSPF_PATH_INTRA_AREA;
! 619: or->cost = cost;
! 620: or->type = OSPF_DESTINATION_NETWORK;
! 621: or->u.std.origin = (struct lsa_header *) lsa;
! 622:
! 623: /* Nexthop is depend on connection type. */
! 624: if (v != area->spf)
! 625: {
! 626: if (IS_DEBUG_OSPF_EVENT)
! 627: zlog_debug ("ospf_intra_add_stub(): this network is on remote router");
! 628: ospf_route_copy_nexthops_from_vertex (or, v);
! 629: }
! 630: else
! 631: {
! 632: if (IS_DEBUG_OSPF_EVENT)
! 633: zlog_debug ("ospf_intra_add_stub(): this network is on this router");
! 634:
! 635: if ((oi = ospf_if_lookup_by_prefix (area->ospf, &p)))
! 636: {
! 637: if (IS_DEBUG_OSPF_EVENT)
! 638: zlog_debug ("ospf_intra_add_stub(): the interface is %s",
! 639: IF_NAME (oi));
! 640:
! 641: path = ospf_path_new ();
! 642: path->nexthop.s_addr = 0;
! 643: path->ifindex = oi->ifp->ifindex;
! 644: listnode_add (or->paths, path);
! 645: }
! 646: else
! 647: {
! 648: if (IS_DEBUG_OSPF_EVENT)
! 649: zlog_debug ("ospf_intra_add_stub(): where's the interface ?");
! 650: }
! 651: }
! 652:
! 653: rn->info = or;
! 654:
! 655: if (IS_DEBUG_OSPF_EVENT)
! 656: zlog_debug("ospf_intra_add_stub(): Stop");
! 657: }
! 658:
! 659: const char *ospf_path_type_str[] =
! 660: {
! 661: "unknown-type",
! 662: "intra-area",
! 663: "inter-area",
! 664: "type1-external",
! 665: "type2-external"
! 666: };
! 667:
! 668: void
! 669: ospf_route_table_dump (struct route_table *rt)
! 670: {
! 671: struct route_node *rn;
! 672: struct ospf_route *or;
! 673: char buf1[BUFSIZ];
! 674: char buf2[BUFSIZ];
! 675: struct listnode *pnode;
! 676: struct ospf_path *path;
! 677:
! 678: #if 0
! 679: zlog_debug ("Type Dest Area Path Type Cost Next Adv.");
! 680: zlog_debug (" Hop(s) Router(s)");
! 681: #endif /* 0 */
! 682:
! 683: zlog_debug ("========== OSPF routing table ==========");
! 684: for (rn = route_top (rt); rn; rn = route_next (rn))
! 685: if ((or = rn->info) != NULL)
! 686: {
! 687: if (or->type == OSPF_DESTINATION_NETWORK)
! 688: {
! 689: zlog_debug ("N %s/%d\t%s\t%s\t%d",
! 690: inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
! 691: rn->p.prefixlen,
! 692: inet_ntop (AF_INET, &or->u.std.area_id, buf2,
! 693: BUFSIZ),
! 694: ospf_path_type_str[or->path_type],
! 695: or->cost);
! 696: for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
! 697: zlog_debug (" -> %s", inet_ntoa (path->nexthop));
! 698: }
! 699: else
! 700: zlog_debug ("R %s\t%s\t%s\t%d",
! 701: inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
! 702: inet_ntop (AF_INET, &or->u.std.area_id, buf2,
! 703: BUFSIZ),
! 704: ospf_path_type_str[or->path_type],
! 705: or->cost);
! 706: }
! 707: zlog_debug ("========================================");
! 708: }
! 709:
! 710: /* This is 16.4.1 implementation.
! 711: o Intra-area paths using non-backbone areas are always the most preferred.
! 712: o The other paths, intra-area backbone paths and inter-area paths,
! 713: are of equal preference. */
! 714: static int
! 715: ospf_asbr_route_cmp (struct ospf *ospf, struct ospf_route *r1,
! 716: struct ospf_route *r2)
! 717: {
! 718: u_char r1_type, r2_type;
! 719:
! 720: r1_type = r1->path_type;
! 721: r2_type = r2->path_type;
! 722:
! 723: /* r1/r2 itself is backbone, and it's Inter-area path. */
! 724: if (OSPF_IS_AREA_ID_BACKBONE (r1->u.std.area_id))
! 725: r1_type = OSPF_PATH_INTER_AREA;
! 726: if (OSPF_IS_AREA_ID_BACKBONE (r2->u.std.area_id))
! 727: r2_type = OSPF_PATH_INTER_AREA;
! 728:
! 729: return (r1_type - r2_type);
! 730: }
! 731:
! 732: /* Compare two routes.
! 733: ret < 0 -- r1 is better.
! 734: ret == 0 -- r1 and r2 are the same.
! 735: ret > 0 -- r2 is better. */
! 736: int
! 737: ospf_route_cmp (struct ospf *ospf, struct ospf_route *r1,
! 738: struct ospf_route *r2)
! 739: {
! 740: int ret = 0;
! 741:
! 742: /* Path types of r1 and r2 are not the same. */
! 743: if ((ret = (r1->path_type - r2->path_type)))
! 744: return ret;
! 745:
! 746: if (IS_DEBUG_OSPF_EVENT)
! 747: zlog_debug ("Route[Compare]: Path types are the same.");
! 748: /* Path types are the same, compare any cost. */
! 749: switch (r1->path_type)
! 750: {
! 751: case OSPF_PATH_INTRA_AREA:
! 752: case OSPF_PATH_INTER_AREA:
! 753: break;
! 754: case OSPF_PATH_TYPE1_EXTERNAL:
! 755: if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
! 756: {
! 757: ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
! 758: if (ret != 0)
! 759: return ret;
! 760: }
! 761: break;
! 762: case OSPF_PATH_TYPE2_EXTERNAL:
! 763: if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
! 764: return ret;
! 765:
! 766: if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
! 767: {
! 768: ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
! 769: if (ret != 0)
! 770: return ret;
! 771: }
! 772: break;
! 773: }
! 774:
! 775: /* Anyway, compare the costs. */
! 776: return (r1->cost - r2->cost);
! 777: }
! 778:
! 779: static int
! 780: ospf_path_exist (struct list *plist, struct in_addr nexthop,
! 781: struct ospf_interface *oi)
! 782: {
! 783: struct listnode *node, *nnode;
! 784: struct ospf_path *path;
! 785:
! 786: for (ALL_LIST_ELEMENTS (plist, node, nnode, path))
! 787: if (IPV4_ADDR_SAME (&path->nexthop, &nexthop) &&
! 788: path->ifindex == oi->ifp->ifindex)
! 789: return 1;
! 790:
! 791: return 0;
! 792: }
! 793:
! 794: void
! 795: ospf_route_copy_nexthops_from_vertex (struct ospf_route *to,
! 796: struct vertex *v)
! 797: {
! 798: struct listnode *node;
! 799: struct ospf_path *path;
! 800: struct vertex_nexthop *nexthop;
! 801: struct vertex_parent *vp;
! 802:
! 803: assert (to->paths);
! 804:
! 805: for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
! 806: {
! 807: nexthop = vp->nexthop;
! 808:
! 809: if (nexthop->oi != NULL)
! 810: {
! 811: if (! ospf_path_exist (to->paths, nexthop->router, nexthop->oi))
! 812: {
! 813: path = ospf_path_new ();
! 814: path->nexthop = nexthop->router;
! 815: path->ifindex = nexthop->oi->ifp->ifindex;
! 816: listnode_add (to->paths, path);
! 817: }
! 818: }
! 819: }
! 820: }
! 821:
! 822: struct ospf_path *
! 823: ospf_path_lookup (struct list *plist, struct ospf_path *path)
! 824: {
! 825: struct listnode *node;
! 826: struct ospf_path *op;
! 827:
! 828: for (ALL_LIST_ELEMENTS_RO (plist, node, op))
! 829: {
! 830: if (!IPV4_ADDR_SAME (&op->nexthop, &path->nexthop))
! 831: continue;
! 832: if (!IPV4_ADDR_SAME (&op->adv_router, &path->adv_router))
! 833: continue;
! 834: if (op->ifindex != path->ifindex)
! 835: continue;
! 836: return op;
! 837: }
! 838: return NULL;
! 839: }
! 840:
! 841: void
! 842: ospf_route_copy_nexthops (struct ospf_route *to, struct list *from)
! 843: {
! 844: struct listnode *node, *nnode;
! 845: struct ospf_path *path;
! 846:
! 847: assert (to->paths);
! 848:
! 849: for (ALL_LIST_ELEMENTS (from, node, nnode, path))
! 850: /* The same routes are just discarded. */
! 851: if (!ospf_path_lookup (to->paths, path))
! 852: listnode_add (to->paths, ospf_path_dup (path));
! 853: }
! 854:
! 855: void
! 856: ospf_route_subst_nexthops (struct ospf_route *to, struct list *from)
! 857: {
! 858:
! 859: list_delete_all_node (to->paths);
! 860: ospf_route_copy_nexthops (to, from);
! 861: }
! 862:
! 863: void
! 864: ospf_route_subst (struct route_node *rn, struct ospf_route *new_or,
! 865: struct ospf_route *over)
! 866: {
! 867: route_lock_node (rn);
! 868: ospf_route_free (rn->info);
! 869:
! 870: ospf_route_copy_nexthops (new_or, over->paths);
! 871: rn->info = new_or;
! 872: route_unlock_node (rn);
! 873: }
! 874:
! 875: void
! 876: ospf_route_add (struct route_table *rt, struct prefix_ipv4 *p,
! 877: struct ospf_route *new_or, struct ospf_route *over)
! 878: {
! 879: struct route_node *rn;
! 880:
! 881: rn = route_node_get (rt, (struct prefix *) p);
! 882:
! 883: ospf_route_copy_nexthops (new_or, over->paths);
! 884:
! 885: if (rn->info)
! 886: {
! 887: if (IS_DEBUG_OSPF_EVENT)
! 888: zlog_debug ("ospf_route_add(): something's wrong !");
! 889: route_unlock_node (rn);
! 890: return;
! 891: }
! 892:
! 893: rn->info = new_or;
! 894: }
! 895:
! 896: void
! 897: ospf_prune_unreachable_networks (struct route_table *rt)
! 898: {
! 899: struct route_node *rn, *next;
! 900: struct ospf_route *or;
! 901:
! 902: if (IS_DEBUG_OSPF_EVENT)
! 903: zlog_debug ("Pruning unreachable networks");
! 904:
! 905: for (rn = route_top (rt); rn; rn = next)
! 906: {
! 907: next = route_next (rn);
! 908: if (rn->info != NULL)
! 909: {
! 910: or = rn->info;
! 911: if (listcount (or->paths) == 0)
! 912: {
! 913: if (IS_DEBUG_OSPF_EVENT)
! 914: zlog_debug ("Pruning route to %s/%d",
! 915: inet_ntoa (rn->p.u.prefix4), rn->p.prefixlen);
! 916:
! 917: ospf_route_free (or);
! 918: rn->info = NULL;
! 919: route_unlock_node (rn);
! 920: }
! 921: }
! 922: }
! 923: }
! 924:
! 925: void
! 926: ospf_prune_unreachable_routers (struct route_table *rtrs)
! 927: {
! 928: struct route_node *rn, *next;
! 929: struct ospf_route *or;
! 930: struct listnode *node, *nnode;
! 931: struct list *paths;
! 932:
! 933: if (IS_DEBUG_OSPF_EVENT)
! 934: zlog_debug ("Pruning unreachable routers");
! 935:
! 936: for (rn = route_top (rtrs); rn; rn = next)
! 937: {
! 938: next = route_next (rn);
! 939: if ((paths = rn->info) == NULL)
! 940: continue;
! 941:
! 942: for (ALL_LIST_ELEMENTS (paths, node, nnode, or))
! 943: {
! 944: if (listcount (or->paths) == 0)
! 945: {
! 946: if (IS_DEBUG_OSPF_EVENT)
! 947: {
! 948: zlog_debug ("Pruning route to rtr %s",
! 949: inet_ntoa (rn->p.u.prefix4));
! 950: zlog_debug (" via area %s",
! 951: inet_ntoa (or->u.std.area_id));
! 952: }
! 953:
! 954: listnode_delete (paths, or);
! 955: ospf_route_free (or);
! 956: }
! 957: }
! 958:
! 959: if (listcount (paths) == 0)
! 960: {
! 961: if (IS_DEBUG_OSPF_EVENT)
! 962: zlog_debug ("Pruning router node %s", inet_ntoa (rn->p.u.prefix4));
! 963:
! 964: list_delete (paths);
! 965: rn->info = NULL;
! 966: route_unlock_node (rn);
! 967: }
! 968: }
! 969: }
! 970:
! 971: int
! 972: ospf_add_discard_route (struct route_table *rt, struct ospf_area *area,
! 973: struct prefix_ipv4 *p)
! 974: {
! 975: struct route_node *rn;
! 976: struct ospf_route *or, *new_or;
! 977:
! 978: rn = route_node_get (rt, (struct prefix *) p);
! 979:
! 980: if (rn == NULL)
! 981: {
! 982: if (IS_DEBUG_OSPF_EVENT)
! 983: zlog_debug ("ospf_add_discard_route(): router installation error");
! 984: return 0;
! 985: }
! 986:
! 987: if (rn->info) /* If the route to the same destination is found */
! 988: {
! 989: route_unlock_node (rn);
! 990:
! 991: or = rn->info;
! 992:
! 993: if (or->path_type == OSPF_PATH_INTRA_AREA)
! 994: {
! 995: if (IS_DEBUG_OSPF_EVENT)
! 996: zlog_debug ("ospf_add_discard_route(): "
! 997: "an intra-area route exists");
! 998: return 0;
! 999: }
! 1000:
! 1001: if (or->type == OSPF_DESTINATION_DISCARD)
! 1002: {
! 1003: if (IS_DEBUG_OSPF_EVENT)
! 1004: zlog_debug ("ospf_add_discard_route(): "
! 1005: "discard entry already installed");
! 1006: return 0;
! 1007: }
! 1008:
! 1009: ospf_route_free (rn->info);
! 1010: }
! 1011:
! 1012: new_or = ospf_route_new ();
! 1013: new_or->type = OSPF_DESTINATION_DISCARD;
! 1014: new_or->id.s_addr = 0;
! 1015: new_or->cost = 0;
! 1016: new_or->u.std.area_id = area->area_id;
! 1017: new_or->u.std.external_routing = area->external_routing;
! 1018: new_or->path_type = OSPF_PATH_INTER_AREA;
! 1019: rn->info = new_or;
! 1020:
! 1021: ospf_zebra_add_discard (p);
! 1022:
! 1023: return 1;
! 1024: }
! 1025:
! 1026: void
! 1027: ospf_delete_discard_route (struct prefix_ipv4 *p)
! 1028: {
! 1029: ospf_zebra_delete_discard(p);
! 1030: }
! 1031:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf_route.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