ospfd/ospf_route.c

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