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