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