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(void)
  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(void)
  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 static const char *const ospf_path_type_str[] = {
 626         "unknown-type", "intra-area", "inter-area", "type1-external",
 627         "type2-external"
 628 };
 629
 630 void ospf_route_table_dump(struct route_table *rt)
 631 {
 632         struct route_node *rn;
 633         struct ospf_route * or ;
 634         char buf1[BUFSIZ];
 635         char buf2[BUFSIZ];
 636         struct listnode *pnode;
 637         struct ospf_path *path;
 638
 639 #if 0
 640   zlog_debug ("Type   Dest   Area   Path         Type    Cost   Next     Adv.");
 641   zlog_debug ("                                 Hop(s)   Router(s)");
 642 #endif /* 0 */
 643
 644         zlog_debug("========== OSPF routing table ==========");
 645         for (rn = route_top(rt); rn; rn = route_next(rn))
 646                 if ((or = rn->info) != NULL) {
 647                         if (or->type == OSPF_DESTINATION_NETWORK) {
 648                                 zlog_debug("N %s/%d\t%s\t%s\t%d",
 649                                            inet_ntop(AF_INET, &rn->p.u.prefix4,
 650                                                      buf1, BUFSIZ),
 651                                            rn->p.prefixlen,
 652                                            inet_ntop(AF_INET,
 653                                                      & or->u.std.area_id, buf2,
 654                                                      BUFSIZ),
 655                                            ospf_path_type_str[or->path_type],
 656                                            or->cost);
 657                                 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
 658                                                           path))
 659                                         zlog_debug("  -> %s",
 660                                                    inet_ntoa(path->nexthop));
 661                         } else
 662                                 zlog_debug("R %s\t%s\t%s\t%d",
 663                                            inet_ntop(AF_INET, &rn->p.u.prefix4,
 664                                                      buf1, BUFSIZ),
 665                                            inet_ntop(AF_INET,
 666                                                      & or->u.std.area_id, buf2,
 667                                                      BUFSIZ),
 668                                            ospf_path_type_str[or->path_type],
 669                                            or->cost);
 670                 }
 671         zlog_debug("========================================");
 672 }
 673
 674 /* This is 16.4.1 implementation.
 675    o Intra-area paths using non-backbone areas are always the most preferred.
 676    o The other paths, intra-area backbone paths and inter-area paths,
 677      are of equal preference. */
 678 static int ospf_asbr_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 679                                struct ospf_route *r2)
 680 {
 681         uint8_t r1_type, r2_type;
 682
 683         r1_type = r1->path_type;
 684         r2_type = r2->path_type;
 685
 686         /* r1/r2 itself is backbone, and it's Inter-area path. */
 687         if (OSPF_IS_AREA_ID_BACKBONE(r1->u.std.area_id))
 688                 r1_type = OSPF_PATH_INTER_AREA;
 689         if (OSPF_IS_AREA_ID_BACKBONE(r2->u.std.area_id))
 690                 r2_type = OSPF_PATH_INTER_AREA;
 691
 692         return (r1_type - r2_type);
 693 }
 694
 695 /* Compare two routes.
 696  ret <  0 -- r1 is better.
 697  ret == 0 -- r1 and r2 are the same.
 698  ret >  0 -- r2 is better. */
 699 int ospf_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 700                    struct ospf_route *r2)
 701 {
 702         int ret = 0;
 703
 704         /* Path types of r1 and r2 are not the same. */
 705         if ((ret = (r1->path_type - r2->path_type)))
 706                 return ret;
 707
 708         if (IS_DEBUG_OSPF_EVENT)
 709                 zlog_debug("Route[Compare]: Path types are the same.");
 710         /* Path types are the same, compare any cost. */
 711         switch (r1->path_type) {
 712         case OSPF_PATH_INTRA_AREA:
 713         case OSPF_PATH_INTER_AREA:
 714                 break;
 715         case OSPF_PATH_TYPE1_EXTERNAL:
 716                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 717                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 718                                                   r2->u.ext.asbr);
 719                         if (ret != 0)
 720                                 return ret;
 721                 }
 722                 break;
 723         case OSPF_PATH_TYPE2_EXTERNAL:
 724                 if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
 725                         return ret;
 726
 727                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 728                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 729                                                   r2->u.ext.asbr);
 730                         if (ret != 0)
 731                                 return ret;
 732                 }
 733                 break;
 734         }
 735
 736         /* Anyway, compare the costs. */
 737         return (r1->cost - r2->cost);
 738 }
 739
 740 static int ospf_path_exist(struct list *plist, struct in_addr nexthop,
 741                            struct ospf_interface *oi)
 742 {
 743         struct listnode *node, *nnode;
 744         struct ospf_path *path;
 745
 746         for (ALL_LIST_ELEMENTS(plist, node, nnode, path))
 747                 if (IPV4_ADDR_SAME(&path->nexthop, &nexthop)
 748                     && path->ifindex == oi->ifp->ifindex)
 749                         return 1;
 750
 751         return 0;
 752 }
 753
 754 void ospf_route_copy_nexthops_from_vertex(struct ospf_route *to,
 755                                           struct vertex *v)
 756 {
 757         struct listnode *node;
 758         struct ospf_path *path;
 759         struct vertex_nexthop *nexthop;
 760         struct vertex_parent *vp;
 761
 762         assert(to->paths);
 763
 764         for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
 765                 nexthop = vp->nexthop;
 766
 767                 if (nexthop->oi != NULL) {
 768                         if (!ospf_path_exist(to->paths, nexthop->router,
 769                                              nexthop->oi)) {
 770                                 path = ospf_path_new();
 771                                 path->nexthop = nexthop->router;
 772                                 path->ifindex = nexthop->oi->ifp->ifindex;
 773                                 if (CHECK_FLAG(nexthop->oi->connected->flags,
 774                                                ZEBRA_IFA_UNNUMBERED))
 775                                         path->unnumbered = 1;
 776                                 listnode_add(to->paths, path);
 777                         }
 778                 }
 779         }
 780 }
 781
 782 struct ospf_path *ospf_path_lookup(struct list *plist, struct ospf_path *path)
 783 {
 784         struct listnode *node;
 785         struct ospf_path *op;
 786
 787         for (ALL_LIST_ELEMENTS_RO(plist, node, op)) {
 788                 if (!IPV4_ADDR_SAME(&op->nexthop, &path->nexthop))
 789                         continue;
 790                 if (!IPV4_ADDR_SAME(&op->adv_router, &path->adv_router))
 791                         continue;
 792                 if (op->ifindex != path->ifindex)
 793                         continue;
 794                 return op;
 795         }
 796         return NULL;
 797 }
 798
 799 void ospf_route_copy_nexthops(struct ospf_route *to, struct list *from)
 800 {
 801         struct listnode *node, *nnode;
 802         struct ospf_path *path;
 803
 804         assert(to->paths);
 805
 806         for (ALL_LIST_ELEMENTS(from, node, nnode, path))
 807                 /* The same routes are just discarded. */
 808                 if (!ospf_path_lookup(to->paths, path))
 809                         listnode_add(to->paths, ospf_path_dup(path));
 810 }
 811
 812 void ospf_route_subst_nexthops(struct ospf_route *to, struct list *from)
 813 {
 814
 815         list_delete_all_node(to->paths);
 816         ospf_route_copy_nexthops(to, from);
 817 }
 818
 819 void ospf_route_subst(struct route_node *rn, struct ospf_route *new_or,
 820                       struct ospf_route *over)
 821 {
 822         route_lock_node(rn);
 823         ospf_route_free(rn->info);
 824
 825         ospf_route_copy_nexthops(new_or, over->paths);
 826         rn->info = new_or;
 827         route_unlock_node(rn);
 828 }
 829
 830 void ospf_route_add(struct route_table *rt, struct prefix_ipv4 *p,
 831                     struct ospf_route *new_or, struct ospf_route *over)
 832 {
 833         struct route_node *rn;
 834
 835         rn = route_node_get(rt, (struct prefix *)p);
 836
 837         ospf_route_copy_nexthops(new_or, over->paths);
 838
 839         if (rn->info) {
 840                 if (IS_DEBUG_OSPF_EVENT)
 841                         zlog_debug("ospf_route_add(): something's wrong !");
 842                 route_unlock_node(rn);
 843                 return;
 844         }
 845
 846         rn->info = new_or;
 847 }
 848
 849 void ospf_prune_unreachable_networks(struct route_table *rt)
 850 {
 851         struct route_node *rn, *next;
 852         struct ospf_route * or ;
 853
 854         if (IS_DEBUG_OSPF_EVENT)
 855                 zlog_debug("Pruning unreachable networks");
 856
 857         for (rn = route_top(rt); rn; rn = next) {
 858                 next = route_next(rn);
 859                 if (rn->info != NULL) {
 860                         or = rn->info;
 861                         if (listcount(or->paths) == 0) {
 862                                 if (IS_DEBUG_OSPF_EVENT)
 863                                         zlog_debug("Pruning route to %s/%d",
 864                                                    inet_ntoa(rn->p.u.prefix4),
 865                                                    rn->p.prefixlen);
 866
 867                                 ospf_route_free(or);
 868                                 rn->info = NULL;
 869                                 route_unlock_node(rn);
 870                         }
 871                 }
 872         }
 873 }
 874
 875 void ospf_prune_unreachable_routers(struct route_table *rtrs)
 876 {
 877         struct route_node *rn, *next;
 878         struct ospf_route * or ;
 879         struct listnode *node, *nnode;
 880         struct list *paths;
 881
 882         if (IS_DEBUG_OSPF_EVENT)
 883                 zlog_debug("Pruning unreachable routers");
 884
 885         for (rn = route_top(rtrs); rn; rn = next) {
 886                 next = route_next(rn);
 887                 if ((paths = rn->info) == NULL)
 888                         continue;
 889
 890                 for (ALL_LIST_ELEMENTS(paths, node, nnode, or)) {
 891                         if (listcount(or->paths) == 0) {
 892                                 if (IS_DEBUG_OSPF_EVENT) {
 893                                         zlog_debug("Pruning route to rtr %s",
 894                                                    inet_ntoa(rn->p.u.prefix4));
 895                                         zlog_debug(
 896                                                 "               via area %s",
 897                                                 inet_ntoa(or->u.std.area_id));
 898                                 }
 899
 900                                 listnode_delete(paths, or);
 901                                 ospf_route_free(or);
 902                         }
 903                 }
 904
 905                 if (listcount(paths) == 0) {
 906                         if (IS_DEBUG_OSPF_EVENT)
 907                                 zlog_debug("Pruning router node %s",
 908                                            inet_ntoa(rn->p.u.prefix4));
 909
 910                         list_delete(&paths);
 911                         rn->info = NULL;
 912                         route_unlock_node(rn);
 913                 }
 914         }
 915 }
 916
 917 int ospf_add_discard_route(struct ospf *ospf, struct route_table *rt,
 918                            struct ospf_area *area, struct prefix_ipv4 *p)
 919 {
 920         struct route_node *rn;
 921         struct ospf_route * or, *new_or;
 922
 923         rn = route_node_get(rt, (struct prefix *)p);
 924
 925         if (rn == NULL) {
 926                 if (IS_DEBUG_OSPF_EVENT)
 927                         zlog_debug(
 928                                 "ospf_add_discard_route(): router installation error");
 929                 return 0;
 930         }
 931
 932         if (rn->info) /* If the route to the same destination is found */
 933         {
 934                 route_unlock_node(rn);
 935
 936                 or = rn->info;
 937
 938                 if (or->path_type == OSPF_PATH_INTRA_AREA) {
 939                         if (IS_DEBUG_OSPF_EVENT)
 940                                 zlog_debug(
 941                                         "ospf_add_discard_route(): "
 942                                         "an intra-area route exists");
 943                         return 0;
 944                 }
 945
 946                 if (or->type == OSPF_DESTINATION_DISCARD) {
 947                         if (IS_DEBUG_OSPF_EVENT)
 948                                 zlog_debug(
 949                                         "ospf_add_discard_route(): "
 950                                         "discard entry already installed");
 951                         return 0;
 952                 }
 953
 954                 ospf_route_free(rn->info);
 955         }
 956
 957         if (IS_DEBUG_OSPF_EVENT)
 958                 zlog_debug(
 959                         "ospf_add_discard_route(): "
 960                         "adding %s/%d",
 961                         inet_ntoa(p->prefix), p->prefixlen);
 962
 963         new_or = ospf_route_new();
 964         new_or->type = OSPF_DESTINATION_DISCARD;
 965         new_or->id.s_addr = 0;
 966         new_or->cost = 0;
 967         new_or->u.std.area_id = area->area_id;
 968         new_or->u.std.external_routing = area->external_routing;
 969         new_or->path_type = OSPF_PATH_INTER_AREA;
 970         rn->info = new_or;
 971
 972         ospf_zebra_add_discard(ospf, p);
 973
 974         return 1;
 975 }
 976
 977 void ospf_delete_discard_route(struct ospf *ospf, struct route_table *rt,
 978                                struct prefix_ipv4 *p)
 979 {
 980         struct route_node *rn;
 981         struct ospf_route * or ;
 982
 983         if (IS_DEBUG_OSPF_EVENT)
 984                 zlog_debug(
 985                         "ospf_delete_discard_route(): "
 986                         "deleting %s/%d",
 987                         inet_ntoa(p->prefix), p->prefixlen);
 988
 989         rn = route_node_lookup(rt, (struct prefix *)p);
 990
 991         if (rn == NULL) {
 992                 if (IS_DEBUG_OSPF_EVENT)
 993                         zlog_debug(
 994                                 "ospf_delete_discard_route(): no route found");
 995                 return;
 996         }
 997
 998         or = rn->info;
 999
1000         if (or->path_type == OSPF_PATH_INTRA_AREA) {
1001                 if (IS_DEBUG_OSPF_EVENT)
1002                         zlog_debug(
1003                                 "ospf_delete_discard_route(): "
1004                                 "an intra-area route exists");
1005                 return;
1006         }
1007
1008         if (or->type != OSPF_DESTINATION_DISCARD) {
1009                 if (IS_DEBUG_OSPF_EVENT)
1010                         zlog_debug(
1011                                 "ospf_delete_discard_route(): "
1012                                 "not a discard entry");
1013                 return;
1014         }
1015
1016         /* free the route entry and the route node */
1017         ospf_route_free(rn->info);
1018
1019         rn->info = NULL;
1020         route_unlock_node(rn);
1021         route_unlock_node(rn);
1022
1023         /* remove the discard entry from the rib */
1024         ospf_zebra_delete_discard(ospf, p);
1025
1026         return;
1027 }