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