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