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: %pI4",
 311                            &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: this router is neither ASBR nor ABR, skipping it");
 326                 return;
 327         }
 328
 329         /* Update ABR and ASBR count in this area. */
 330         if (IS_ROUTER_LSA_BORDER(lsa))
 331                 area->abr_count++;
 332         if (IS_ROUTER_LSA_EXTERNAL(lsa))
 333                 area->asbr_count++;
 334
 335         /* The Options field found in the associated router-LSA is copied
 336            into the routing table entry's Optional capabilities field. Call
 337            the newly added vertex Router X. */
 338         or = ospf_route_new();
 339
 340         or->id = v->id;
 341         or->u.std.area_id = area->area_id;
 342         or->u.std.external_routing = area->external_routing;
 343         or->path_type = OSPF_PATH_INTRA_AREA;
 344         or->cost = v->distance;
 345         or->type = OSPF_DESTINATION_ROUTER;
 346         or->u.std.origin = (struct lsa_header *)lsa;
 347         or->u.std.options = lsa->header.options;
 348         or->u.std.flags = lsa->flags;
 349
 350         /* If Router X is the endpoint of one of the calculating router's
 351            virtual links, and the virtual link uses Area A as Transit area:
 352            the virtual link is declared up, the IP address of the virtual
 353            interface is set to the IP address of the outgoing interface
 354            calculated above for Router X, and the virtual neighbor's IP
 355            address is set to Router X's interface address (contained in
 356            Router X's router-LSA) that points back to the root of the
 357            shortest- path tree; equivalently, this is the interface that
 358            points back to Router X's parent vertex on the shortest-path tree
 359            (similar to the calculation in Section 16.1.1). */
 360
 361         p.family = AF_INET;
 362         p.prefix = v->id;
 363         p.prefixlen = IPV4_MAX_BITLEN;
 364         apply_mask_ipv4(&p);
 365
 366         if (IS_DEBUG_OSPF_EVENT)
 367                 zlog_debug("ospf_intra_add_router: talking about %pFX", &p);
 368
 369         rn = route_node_get(rt, (struct prefix *)&p);
 370
 371         /* Note that we keep all routes to ABRs and ASBRs, not only the best */
 372         if (rn->info == NULL)
 373                 rn->info = list_new();
 374         else
 375                 route_unlock_node(rn);
 376
 377         ospf_route_copy_nexthops_from_vertex(area, or, v);
 378
 379         listnode_add(rn->info, or);
 380
 381         if (IS_DEBUG_OSPF_EVENT)
 382                 zlog_debug("ospf_intra_add_router: Stop");
 383 }
 384
 385 /* RFC2328 16.1. (4).  For transit network. */
 386 void ospf_intra_add_transit(struct route_table *rt, struct vertex *v,
 387                             struct ospf_area *area)
 388 {
 389         struct route_node *rn;
 390         struct ospf_route * or ;
 391         struct prefix_ipv4 p;
 392         struct network_lsa *lsa;
 393
 394         lsa = (struct network_lsa *)v->lsa;
 395
 396         /* If the newly added vertex is a transit network, the routing table
 397            entry for the network is located.  The entry's Destination ID is
 398            the IP network number, which can be obtained by masking the
 399            Vertex ID (Link State ID) with its associated subnet mask (found
 400            in the body of the associated network-LSA). */
 401         p.family = AF_INET;
 402         p.prefix = v->id;
 403         p.prefixlen = ip_masklen(lsa->mask);
 404         apply_mask_ipv4(&p);
 405
 406         rn = route_node_get(rt, (struct prefix *)&p);
 407
 408         /* If the routing table entry already exists (i.e., there is already
 409            an intra-area route to the destination installed in the routing
 410            table), multiple vertices have mapped to the same IP network.
 411            For example, this can occur when a new Designated Router is being
 412            established.  In this case, the current routing table entry
 413            should be overwritten if and only if the newly found path is just
 414            as short and the current routing table entry's Link State Origin
 415            has a smaller Link State ID than the newly added vertex' LSA. */
 416         if (rn->info) {
 417                 struct ospf_route *cur_or;
 418
 419                 route_unlock_node(rn);
 420                 cur_or = rn->info;
 421
 422                 if (v->distance > cur_or->cost
 423                     || IPV4_ADDR_CMP(&cur_or->u.std.origin->id, &lsa->header.id)
 424                                > 0)
 425                         return;
 426
 427                 ospf_route_free(rn->info);
 428         }
 429
 430         or = ospf_route_new();
 431
 432         or->id = v->id;
 433         or->u.std.area_id = area->area_id;
 434         or->u.std.external_routing = area->external_routing;
 435         or->path_type = OSPF_PATH_INTRA_AREA;
 436         or->cost = v->distance;
 437         or->type = OSPF_DESTINATION_NETWORK;
 438         or->u.std.origin = (struct lsa_header *)lsa;
 439
 440         ospf_route_copy_nexthops_from_vertex(area, or, v);
 441
 442         rn->info = or ;
 443 }
 444
 445 /* RFC2328 16.1. second stage. */
 446 void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
 447                          struct vertex *v, struct ospf_area *area,
 448                          int parent_is_root, int lsa_pos)
 449 {
 450         uint32_t cost;
 451         struct route_node *rn;
 452         struct ospf_route * or ;
 453         struct prefix_ipv4 p;
 454         struct router_lsa *lsa;
 455         struct ospf_interface *oi = NULL;
 456         struct ospf_path *path;
 457
 458         if (IS_DEBUG_OSPF_EVENT)
 459                 zlog_debug("ospf_intra_add_stub(): Start");
 460
 461         lsa = (struct router_lsa *)v->lsa;
 462
 463         p.family = AF_INET;
 464         p.prefix = link->link_id;
 465         p.prefixlen = ip_masklen(link->link_data);
 466         apply_mask_ipv4(&p);
 467
 468         if (IS_DEBUG_OSPF_EVENT)
 469                 zlog_debug("ospf_intra_add_stub(): processing route to %pFX",
 470                            &p);
 471
 472         /* (1) Calculate the distance D of stub network from the root.  D is
 473            equal to the distance from the root to the router vertex
 474            (calculated in stage 1), plus the stub network link's advertised
 475            cost. */
 476         cost = v->distance + ntohs(link->m[0].metric);
 477
 478         if (IS_DEBUG_OSPF_EVENT)
 479                 zlog_debug(
 480                         "ospf_intra_add_stub(): calculated cost is %d + %d = %d",
 481                         v->distance, ntohs(link->m[0].metric), cost);
 482
 483         /* PtP links with /32 masks adds host routes to remote, directly
 484          * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
 485          * Such routes can just be ignored for the sake of tidyness.
 486          */
 487         if (parent_is_root && link->link_data.s_addr == 0xffffffff
 488             && ospf_if_lookup_by_local_addr(area->ospf, NULL, link->link_id)) {
 489                 if (IS_DEBUG_OSPF_EVENT)
 490                         zlog_debug("%s: ignoring host route %pI4/32 to self.",
 491                                    __func__, &link->link_id);
 492                 return;
 493         }
 494
 495         rn = route_node_get(rt, (struct prefix *)&p);
 496
 497         /* Lookup current routing table. */
 498         if (rn->info) {
 499                 struct ospf_route *cur_or;
 500
 501                 route_unlock_node(rn);
 502
 503                 cur_or = rn->info;
 504
 505                 if (IS_DEBUG_OSPF_EVENT)
 506                         zlog_debug(
 507                                 "ospf_intra_add_stub(): 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(area, 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(area, 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(area, 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                 /*
 597                  * Only deal with interface data when we
 598                  * don't do a dry run
 599                  */
 600                 if (!area->spf_dry_run)
 601                         oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
 602
 603                 if (oi || area->spf_dry_run) {
 604                         if (IS_DEBUG_OSPF_EVENT)
 605                                 zlog_debug(
 606                                         "ospf_intra_add_stub(): the lsa pos is %d",
 607                                         lsa_pos);
 608
 609                         path = ospf_path_new();
 610                         path->nexthop.s_addr = INADDR_ANY;
 611
 612                         if (oi) {
 613                                 path->ifindex = oi->ifp->ifindex;
 614                                 if (CHECK_FLAG(oi->connected->flags,
 615                                                ZEBRA_IFA_UNNUMBERED))
 616                                         path->unnumbered = 1;
 617                         }
 618
 619                         listnode_add(or->paths, path);
 620                 } else {
 621                         if (IS_DEBUG_OSPF_EVENT)
 622                                 zlog_debug(
 623                                         "ospf_intra_add_stub(): where's the interface ?");
 624                 }
 625         }
 626
 627         rn->info = or ;
 628
 629         if (IS_DEBUG_OSPF_EVENT)
 630                 zlog_debug("ospf_intra_add_stub(): Stop");
 631 }
 632
 633 static const char *const ospf_path_type_str[] = {
 634         "unknown-type", "intra-area", "inter-area", "type1-external",
 635         "type2-external"
 636 };
 637
 638 void ospf_route_table_dump(struct route_table *rt)
 639 {
 640         struct route_node *rn;
 641         struct ospf_route * or ;
 642         struct listnode *pnode;
 643         struct ospf_path *path;
 644
 645         zlog_debug("========== OSPF routing table ==========");
 646         for (rn = route_top(rt); rn; rn = route_next(rn))
 647                 if ((or = rn->info) != NULL) {
 648                         if (or->type == OSPF_DESTINATION_NETWORK) {
 649                                 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn->p,
 650                                            &or->u.std.area_id,
 651                                            ospf_path_type_str[or->path_type],
 652                                            or->cost);
 653                                 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
 654                                                           path))
 655                                         zlog_debug("  -> %pI4",
 656                                                    &path->nexthop);
 657                         } else
 658                                 zlog_debug("R %-18pI4 %-15pI4 %s %d",
 659                                            &rn->p.u.prefix4,
 660                                            &or->u.std.area_id,
 661                                            ospf_path_type_str[or->path_type],
 662                                            or->cost);
 663                 }
 664         zlog_debug("========================================");
 665 }
 666
 667 void ospf_route_table_print(struct vty *vty, struct route_table *rt)
 668 {
 669         struct route_node *rn;
 670         struct ospf_route * or ;
 671         struct listnode *pnode;
 672         struct ospf_path *path;
 673
 674         vty_out(vty, "========== OSPF routing table ==========\n");
 675         for (rn = route_top(rt); rn; rn = route_next(rn))
 676                 if ((or = rn->info) != NULL) {
 677                         if (or->type == OSPF_DESTINATION_NETWORK) {
 678                                 vty_out(vty, "N %-18pFX %-15pI4 %s %d\n",
 679                                         &rn->p, & or->u.std.area_id,
 680                                         ospf_path_type_str[or->path_type],
 681                                         or->cost);
 682                                 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
 683                                                           path))
 684                                         if (path->nexthop.s_addr != 0)
 685                                                 vty_out(vty, "  -> %pI4\n",
 686                                                         &path->nexthop);
 687                                         else
 688                                                 vty_out(vty, "  -> %s\n",
 689                                                         "directly connected");
 690                         } else
 691                                 vty_out(vty, "R %-18pI4 %-15pI4 %s %d\n",
 692                                         &rn->p.u.prefix4, & or->u.std.area_id,
 693                                         ospf_path_type_str[or->path_type],
 694                                         or->cost);
 695                 }
 696         vty_out(vty, "========================================\n");
 697 }
 698
 699 /* This is 16.4.1 implementation.
 700    o Intra-area paths using non-backbone areas are always the most preferred.
 701    o The other paths, intra-area backbone paths and inter-area paths,
 702      are of equal preference. */
 703 static int ospf_asbr_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 704                                struct ospf_route *r2)
 705 {
 706         uint8_t r1_type, r2_type;
 707
 708         r1_type = r1->path_type;
 709         r2_type = r2->path_type;
 710
 711         /* r1/r2 itself is backbone, and it's Inter-area path. */
 712         if (OSPF_IS_AREA_ID_BACKBONE(r1->u.std.area_id))
 713                 r1_type = OSPF_PATH_INTER_AREA;
 714         if (OSPF_IS_AREA_ID_BACKBONE(r2->u.std.area_id))
 715                 r2_type = OSPF_PATH_INTER_AREA;
 716
 717         return (r1_type - r2_type);
 718 }
 719
 720 /* Compare two routes.
 721  ret <  0 -- r1 is better.
 722  ret == 0 -- r1 and r2 are the same.
 723  ret >  0 -- r2 is better. */
 724 int ospf_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 725                    struct ospf_route *r2)
 726 {
 727         int ret = 0;
 728
 729         /* Path types of r1 and r2 are not the same. */
 730         if ((ret = (r1->path_type - r2->path_type)))
 731                 return ret;
 732
 733         if (IS_DEBUG_OSPF_EVENT)
 734                 zlog_debug("Route[Compare]: Path types are the same.");
 735         /* Path types are the same, compare any cost. */
 736         switch (r1->path_type) {
 737         case OSPF_PATH_INTRA_AREA:
 738         case OSPF_PATH_INTER_AREA:
 739                 break;
 740         case OSPF_PATH_TYPE1_EXTERNAL:
 741                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 742                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 743                                                   r2->u.ext.asbr);
 744                         if (ret != 0)
 745                                 return ret;
 746                 }
 747                 break;
 748         case OSPF_PATH_TYPE2_EXTERNAL:
 749                 if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
 750                         return ret;
 751
 752                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 753                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 754                                                   r2->u.ext.asbr);
 755                         if (ret != 0)
 756                                 return ret;
 757                 }
 758                 break;
 759         }
 760
 761         /* Anyway, compare the costs. */
 762         return (r1->cost - r2->cost);
 763 }
 764
 765 static int ospf_path_exist(struct list *plist, struct in_addr nexthop,
 766                            struct ospf_interface *oi)
 767 {
 768         struct listnode *node, *nnode;
 769         struct ospf_path *path;
 770
 771         for (ALL_LIST_ELEMENTS(plist, node, nnode, path))
 772                 if (IPV4_ADDR_SAME(&path->nexthop, &nexthop)
 773                     && path->ifindex == oi->ifp->ifindex)
 774                         return 1;
 775
 776         return 0;
 777 }
 778
 779 void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area,
 780                                           struct ospf_route *to,
 781                                           struct vertex *v)
 782 {
 783         struct listnode *node;
 784         struct ospf_path *path;
 785         struct vertex_nexthop *nexthop;
 786         struct vertex_parent *vp;
 787         struct ospf_interface *oi = NULL;
 788
 789         assert(to->paths);
 790
 791         for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
 792                 nexthop = vp->nexthop;
 793
 794                 /*
 795                  * Only deal with interface data when we
 796                  * don't do a dry run
 797                  */
 798                 if (!area->spf_dry_run)
 799                         oi = ospf_if_lookup_by_lsa_pos(area, nexthop->lsa_pos);
 800
 801                 if ((oi && !ospf_path_exist(to->paths, nexthop->router, oi))
 802                     || area->spf_dry_run) {
 803                         path = ospf_path_new();
 804                         path->nexthop = nexthop->router;
 805
 806                         if (oi) {
 807                                 path->ifindex = oi->ifp->ifindex;
 808                                 if (CHECK_FLAG(oi->connected->flags,
 809                                                ZEBRA_IFA_UNNUMBERED))
 810                                         path->unnumbered = 1;
 811                         }
 812
 813                         listnode_add(to->paths, path);
 814                 }
 815         }
 816 }
 817
 818 struct ospf_path *ospf_path_lookup(struct list *plist, struct ospf_path *path)
 819 {
 820         struct listnode *node;
 821         struct ospf_path *op;
 822
 823         for (ALL_LIST_ELEMENTS_RO(plist, node, op)) {
 824                 if (!IPV4_ADDR_SAME(&op->nexthop, &path->nexthop))
 825                         continue;
 826                 if (!IPV4_ADDR_SAME(&op->adv_router, &path->adv_router))
 827                         continue;
 828                 if (op->ifindex != path->ifindex)
 829                         continue;
 830                 return op;
 831         }
 832         return NULL;
 833 }
 834
 835 void ospf_route_copy_nexthops(struct ospf_route *to, struct list *from)
 836 {
 837         struct listnode *node, *nnode;
 838         struct ospf_path *path;
 839
 840         assert(to->paths);
 841
 842         for (ALL_LIST_ELEMENTS(from, node, nnode, path))
 843                 /* The same routes are just discarded. */
 844                 if (!ospf_path_lookup(to->paths, path))
 845                         listnode_add(to->paths, ospf_path_dup(path));
 846 }
 847
 848 void ospf_route_subst_nexthops(struct ospf_route *to, struct list *from)
 849 {
 850
 851         list_delete_all_node(to->paths);
 852         ospf_route_copy_nexthops(to, from);
 853 }
 854
 855 void ospf_route_subst(struct route_node *rn, struct ospf_route *new_or,
 856                       struct ospf_route *over)
 857 {
 858         route_lock_node(rn);
 859         ospf_route_free(rn->info);
 860
 861         ospf_route_copy_nexthops(new_or, over->paths);
 862         rn->info = new_or;
 863         route_unlock_node(rn);
 864 }
 865
 866 void ospf_route_add(struct route_table *rt, struct prefix_ipv4 *p,
 867                     struct ospf_route *new_or, struct ospf_route *over)
 868 {
 869         struct route_node *rn;
 870
 871         rn = route_node_get(rt, (struct prefix *)p);
 872
 873         ospf_route_copy_nexthops(new_or, over->paths);
 874
 875         if (rn->info) {
 876                 if (IS_DEBUG_OSPF_EVENT)
 877                         zlog_debug("ospf_route_add(): something's wrong !");
 878                 route_unlock_node(rn);
 879                 return;
 880         }
 881
 882         rn->info = new_or;
 883 }
 884
 885 void ospf_prune_unreachable_networks(struct route_table *rt)
 886 {
 887         struct route_node *rn, *next;
 888         struct ospf_route * or ;
 889
 890         if (IS_DEBUG_OSPF_EVENT)
 891                 zlog_debug("Pruning unreachable networks");
 892
 893         for (rn = route_top(rt); rn; rn = next) {
 894                 next = route_next(rn);
 895                 if (rn->info != NULL) {
 896                         or = rn->info;
 897                         if (listcount(or->paths) == 0) {
 898                                 if (IS_DEBUG_OSPF_EVENT)
 899                                         zlog_debug("Pruning route to %pFX",
 900                                                    &rn->p);
 901
 902                                 ospf_route_free(or);
 903                                 rn->info = NULL;
 904                                 route_unlock_node(rn);
 905                         }
 906                 }
 907         }
 908 }
 909
 910 void ospf_prune_unreachable_routers(struct route_table *rtrs)
 911 {
 912         struct route_node *rn, *next;
 913         struct ospf_route * or ;
 914         struct listnode *node, *nnode;
 915         struct list *paths;
 916
 917         if (IS_DEBUG_OSPF_EVENT)
 918                 zlog_debug("Pruning unreachable routers");
 919
 920         for (rn = route_top(rtrs); rn; rn = next) {
 921                 next = route_next(rn);
 922                 if ((paths = rn->info) == NULL)
 923                         continue;
 924
 925                 for (ALL_LIST_ELEMENTS(paths, node, nnode, or)) {
 926                         if (listcount(or->paths) == 0) {
 927                                 if (IS_DEBUG_OSPF_EVENT) {
 928                                         zlog_debug("Pruning route to rtr %pI4",
 929                                                    &rn->p.u.prefix4);
 930                                         zlog_debug(
 931                                                 "               via area %pI4",
 932                                                 &or->u.std.area_id);
 933                                 }
 934
 935                                 listnode_delete(paths, or);
 936                                 ospf_route_free(or);
 937                         }
 938                 }
 939
 940                 if (listcount(paths) == 0) {
 941                         if (IS_DEBUG_OSPF_EVENT)
 942                                 zlog_debug("Pruning router node %pI4",
 943                                            &rn->p.u.prefix4);
 944
 945                         list_delete(&paths);
 946                         rn->info = NULL;
 947                         route_unlock_node(rn);
 948                 }
 949         }
 950 }
 951
 952 int ospf_add_discard_route(struct ospf *ospf, struct route_table *rt,
 953                            struct ospf_area *area, struct prefix_ipv4 *p)
 954 {
 955         struct route_node *rn;
 956         struct ospf_route * or, *new_or;
 957
 958         rn = route_node_get(rt, (struct prefix *)p);
 959
 960         if (rn == NULL) {
 961                 if (IS_DEBUG_OSPF_EVENT)
 962                         zlog_debug(
 963                                 "ospf_add_discard_route(): router installation error");
 964                 return 0;
 965         }
 966
 967         if (rn->info) /* If the route to the same destination is found */
 968         {
 969                 route_unlock_node(rn);
 970
 971                 or = rn->info;
 972
 973                 if (or->path_type == OSPF_PATH_INTRA_AREA) {
 974                         if (IS_DEBUG_OSPF_EVENT)
 975                                 zlog_debug(
 976                                         "ospf_add_discard_route(): an intra-area route exists");
 977                         return 0;
 978                 }
 979
 980                 if (or->type == OSPF_DESTINATION_DISCARD) {
 981                         if (IS_DEBUG_OSPF_EVENT)
 982                                 zlog_debug(
 983                                         "ospf_add_discard_route(): discard entry already installed");
 984                         return 0;
 985                 }
 986
 987                 ospf_route_free(rn->info);
 988         }
 989
 990         if (IS_DEBUG_OSPF_EVENT)
 991                 zlog_debug("ospf_add_discard_route(): adding %pFX", p);
 992
 993         new_or = ospf_route_new();
 994         new_or->type = OSPF_DESTINATION_DISCARD;
 995         new_or->id.s_addr = INADDR_ANY;
 996         new_or->cost = 0;
 997         new_or->u.std.area_id = area->area_id;
 998         new_or->u.std.external_routing = area->external_routing;
 999         new_or->path_type = OSPF_PATH_INTER_AREA;
1000         rn->info = new_or;
1001
1002         ospf_zebra_add_discard(ospf, p);
1003
1004         return 1;
1005 }
1006
1007 void ospf_delete_discard_route(struct ospf *ospf, struct route_table *rt,
1008                                struct prefix_ipv4 *p)
1009 {
1010         struct route_node *rn;
1011         struct ospf_route * or ;
1012
1013         if (IS_DEBUG_OSPF_EVENT)
1014                 zlog_debug("ospf_delete_discard_route(): deleting %pFX", p);
1015
1016         rn = route_node_lookup(rt, (struct prefix *)p);
1017
1018         if (rn == NULL) {
1019                 if (IS_DEBUG_OSPF_EVENT)
1020                         zlog_debug(
1021                                 "ospf_delete_discard_route(): no route found");
1022                 return;
1023         }
1024
1025         or = rn->info;
1026
1027         if (or->path_type == OSPF_PATH_INTRA_AREA) {
1028                 if (IS_DEBUG_OSPF_EVENT)
1029                         zlog_debug(
1030                                 "ospf_delete_discard_route(): an intra-area route exists");
1031                 return;
1032         }
1033
1034         if (or->type != OSPF_DESTINATION_DISCARD) {
1035                 if (IS_DEBUG_OSPF_EVENT)
1036                         zlog_debug(
1037                                 "ospf_delete_discard_route(): not a discard entry");
1038                 return;
1039         }
1040
1041         /* free the route entry and the route node */
1042         ospf_route_free(rn->info);
1043
1044         rn->info = NULL;
1045         route_unlock_node(rn);
1046         route_unlock_node(rn);
1047
1048         /* remove the discard entry from the rib */
1049         ospf_zebra_delete_discard(ospf, p);
1050
1051         return;
1052 }