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