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