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