ospfd/ospf_route.c

   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 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. */
 133 static int
 134 ospf_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. */
 156 int
 157 ospf_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  */
 207 static void
 208 ospf_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 */
 238 static void
 239 ospf_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. */
 263 void
 264 ospf_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". */
 301 void
 302 ospf_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. */
 393 void
 394 ospf_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. */
 454 void
 455 ospf_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
 629 const char *ospf_path_type_str[] =
 630 {
 631   "unknown-type",
 632   "intra-area",
 633   "inter-area",
 634   "type1-external",
 635   "type2-external"
 636 };
 637
 638 void
 639 ospf_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. */
 684 static int
 685 ospf_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. */
 706 int
 707 ospf_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
 749 static int
 750 ospf_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
 764 void
 765 ospf_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
 792 struct ospf_path *
 793 ospf_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
 811 void
 812 ospf_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
 825 void
 826 ospf_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
 833 void
 834 ospf_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
 845 void
 846 ospf_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
 866 void
 867 ospf_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
 895 void
 896 ospf_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
 941 int
 942 ospf_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
1000 void
1001 ospf_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