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