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