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