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("%s: Start", __func__);
 375
 376         lsa = (struct router_lsa *)v->lsa;
 377
 378         if (IS_DEBUG_OSPF_EVENT)
 379                 zlog_debug("%s: LS ID: %pI4", __func__, &lsa->header.id);
 380
 381         if (!OSPF_IS_AREA_BACKBONE(area))
 382                 ospf_vl_up_check(area, lsa->header.id, v);
 383
 384         if (!CHECK_FLAG(lsa->flags, ROUTER_LSA_SHORTCUT))
 385                 area->shortcut_capability = 0;
 386
 387         /* If the newly added vertex is an area border router or AS boundary
 388            router, a routing table entry is added whose destination type is
 389            "router". */
 390         if (!add_all && !IS_ROUTER_LSA_BORDER(lsa) &&
 391             !IS_ROUTER_LSA_EXTERNAL(lsa)) {
 392                 if (IS_DEBUG_OSPF_EVENT)
 393                         zlog_debug(
 394                                 "%s: this router is neither ASBR nor ABR, skipping it",
 395                                 __func__);
 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("%s: talking about %pFX", __func__, &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("%s: Stop", __func__);
 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("%s: Start", __func__);
 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("%s: processing route to %pFX", __func__, &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("%s: calculated cost is %d + %d = %d", __func__,
 549                            v->distance, ntohs(link->m[0].metric), cost);
 550
 551         /* PtP links with /32 masks adds host routes to remote, directly
 552          * connected hosts, see RFC 2328, 12.4.1.1, Option 1.
 553          * Such routes can just be ignored for the sake of tidyness.
 554          */
 555         if (parent_is_root && link->link_data.s_addr == 0xffffffff
 556             && ospf_if_lookup_by_local_addr(area->ospf, NULL, link->link_id)) {
 557                 if (IS_DEBUG_OSPF_EVENT)
 558                         zlog_debug("%s: ignoring host route %pI4/32 to self.",
 559                                    __func__, &link->link_id);
 560                 return;
 561         }
 562
 563         rn = route_node_get(rt, (struct prefix *)&p);
 564
 565         /* Lookup current routing table. */
 566         if (rn->info) {
 567                 struct ospf_route *cur_or;
 568
 569                 route_unlock_node(rn);
 570
 571                 cur_or = rn->info;
 572
 573                 if (IS_DEBUG_OSPF_EVENT)
 574                         zlog_debug(
 575                                 "%s: another route to the same prefix found with cost %u",
 576                                 __func__, cur_or->cost);
 577
 578                 /* Compare this distance to the current best cost to the stub
 579                    network.  This is done by looking up the stub network's
 580                    current routing table entry.  If the calculated distance D is
 581                    larger, go on to examine the next stub network link in the
 582                    LSA. */
 583                 if (cost > cur_or->cost) {
 584                         if (IS_DEBUG_OSPF_EVENT)
 585                                 zlog_debug("%s: old route is better, exit",
 586                                            __func__);
 587                         return;
 588                 }
 589
 590                 /* (2) If this step is reached, the stub network's routing table
 591                    entry must be updated.  Calculate the set of next hops that
 592                    would result from using the stub network link.  This
 593                    calculation is shown in Section 16.1.1; input to this
 594                    calculation is the destination (the stub network) and the
 595                    parent vertex (the router vertex). If the distance D is the
 596                    same as the current routing table cost, simply add this set
 597                    of next hops to the routing table entry's list of next hops.
 598                    In this case, the routing table already has a Link State
 599                    Origin.  If this Link State Origin is a router-LSA whose Link
 600                    State ID is smaller than V's Router ID, reset the Link State
 601                    Origin to V's router-LSA. */
 602
 603                 if (cost == cur_or->cost) {
 604                         if (IS_DEBUG_OSPF_EVENT)
 605                                 zlog_debug("%s: routes are equal, merge",
 606                                            __func__);
 607
 608                         ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
 609
 610                         if (IPV4_ADDR_CMP(&cur_or->u.std.origin->id,
 611                                           &lsa->header.id)
 612                             < 0)
 613                                 cur_or->u.std.origin = (struct lsa_header *)lsa;
 614                         return;
 615                 }
 616
 617                 /* Otherwise D is smaller than the routing table cost.
 618                    Overwrite the current routing table entry by setting the
 619                    routing table entry's cost to D, and by setting the entry's
 620                    list of next hops to the newly calculated set.  Set the
 621                    routing table entry's Link State Origin to V's router-LSA.
 622                    Then go on to examine the next stub network link. */
 623
 624                 if (cost < cur_or->cost) {
 625                         if (IS_DEBUG_OSPF_EVENT)
 626                                 zlog_debug("%s: new route is better, set it",
 627                                            __func__);
 628
 629                         cur_or->cost = cost;
 630
 631                         list_delete_all_node(cur_or->paths);
 632
 633                         ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
 634
 635                         cur_or->u.std.origin = (struct lsa_header *)lsa;
 636                         return;
 637                 }
 638         }
 639
 640         if (IS_DEBUG_OSPF_EVENT)
 641                 zlog_debug("%s: installing new route", __func__);
 642
 643         or = ospf_route_new();
 644
 645         or->id = v->id;
 646         or->u.std.area_id = area->area_id;
 647         or->u.std.external_routing = area->external_routing;
 648         or->path_type = OSPF_PATH_INTRA_AREA;
 649         or->cost = cost;
 650         or->type = OSPF_DESTINATION_NETWORK;
 651         or->u.std.origin = (struct lsa_header *)lsa;
 652
 653         /* Nexthop is depend on connection type. */
 654         if (v != area->spf) {
 655                 if (IS_DEBUG_OSPF_EVENT)
 656                         zlog_debug("%s: this network is on remote router",
 657                                    __func__);
 658                 ospf_route_copy_nexthops_from_vertex(area, or, v);
 659         } else {
 660                 if (IS_DEBUG_OSPF_EVENT)
 661                         zlog_debug("%s: this network is on this router",
 662                                    __func__);
 663
 664                 /*
 665                  * Only deal with interface data when we
 666                  * don't do a dry run
 667                  */
 668                 if (!area->spf_dry_run)
 669                         oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
 670
 671                 if (oi || area->spf_dry_run) {
 672                         if (IS_DEBUG_OSPF_EVENT)
 673                                 zlog_debug("%s: the lsa pos is %d", __func__,
 674                                            lsa_pos);
 675
 676                         path = ospf_path_new();
 677                         path->nexthop.s_addr = INADDR_ANY;
 678
 679                         if (oi) {
 680                                 path->ifindex = oi->ifp->ifindex;
 681                                 if (CHECK_FLAG(oi->connected->flags,
 682                                                ZEBRA_IFA_UNNUMBERED))
 683                                         path->unnumbered = 1;
 684                         }
 685
 686                         listnode_add(or->paths, path);
 687                 } else {
 688                         if (IS_DEBUG_OSPF_EVENT)
 689                                 zlog_debug("%s: where's the interface ?",
 690                                            __func__);
 691                 }
 692         }
 693
 694         rn->info = or ;
 695
 696         if (IS_DEBUG_OSPF_EVENT)
 697                 zlog_debug("%s: Stop", __func__);
 698 }
 699
 700 static const char *const ospf_path_type_str[] = {
 701         "unknown-type", "intra-area", "inter-area", "type1-external",
 702         "type2-external"
 703 };
 704
 705 void ospf_route_table_dump(struct route_table *rt)
 706 {
 707         struct route_node *rn;
 708         struct ospf_route * or ;
 709         struct listnode *pnode;
 710         struct ospf_path *path;
 711
 712         zlog_debug("========== OSPF routing table ==========");
 713         for (rn = route_top(rt); rn; rn = route_next(rn))
 714                 if ((or = rn->info) != NULL) {
 715                         if (or->type == OSPF_DESTINATION_NETWORK) {
 716                                 zlog_debug("N %-18pFX %-15pI4 %s %d", &rn->p,
 717                                            &or->u.std.area_id,
 718                                            ospf_path_type_str[or->path_type],
 719                                            or->cost);
 720                                 for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
 721                                                           path))
 722                                         zlog_debug("  -> %pI4",
 723                                                    &path->nexthop);
 724                         } else
 725                                 zlog_debug("R %-18pI4 %-15pI4 %s %d",
 726                                            &rn->p.u.prefix4,
 727                                            &or->u.std.area_id,
 728                                            ospf_path_type_str[or->path_type],
 729                                            or->cost);
 730                 }
 731         zlog_debug("========================================");
 732 }
 733
 734 void ospf_router_route_table_dump(struct route_table *rt)
 735 {
 736         struct route_node *rn;
 737         struct ospf_route *or;
 738         struct listnode *node;
 739
 740         zlog_debug("========== OSPF routing table ==========");
 741         for (rn = route_top(rt); rn; rn = route_next(rn)) {
 742                 for (ALL_LIST_ELEMENTS_RO((struct list *)rn->info, node, or)) {
 743                         assert(or->type == OSPF_DESTINATION_ROUTER);
 744                         zlog_debug("R %-18pI4 %-15pI4 %s %d", &rn->p.u.prefix4,
 745                                    &or->u.std.area_id,
 746                                    ospf_path_type_str[or->path_type], or->cost);
 747                 }
 748         }
 749         zlog_debug("========================================");
 750 }
 751
 752 /* This is 16.4.1 implementation.
 753    o Intra-area paths using non-backbone areas are always the most preferred.
 754    o The other paths, intra-area backbone paths and inter-area paths,
 755      are of equal preference. */
 756 static int ospf_asbr_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 757                                struct ospf_route *r2)
 758 {
 759         uint8_t r1_type, r2_type;
 760
 761         r1_type = r1->path_type;
 762         r2_type = r2->path_type;
 763
 764         /* r1/r2 itself is backbone, and it's Inter-area path. */
 765         if (OSPF_IS_AREA_ID_BACKBONE(r1->u.std.area_id))
 766                 r1_type = OSPF_PATH_INTER_AREA;
 767         if (OSPF_IS_AREA_ID_BACKBONE(r2->u.std.area_id))
 768                 r2_type = OSPF_PATH_INTER_AREA;
 769
 770         return (r1_type - r2_type);
 771 }
 772
 773 /* Compare two routes.
 774  ret <  0 -- r1 is better.
 775  ret == 0 -- r1 and r2 are the same.
 776  ret >  0 -- r2 is better. */
 777 int ospf_route_cmp(struct ospf *ospf, struct ospf_route *r1,
 778                    struct ospf_route *r2)
 779 {
 780         int ret = 0;
 781
 782         /* Path types of r1 and r2 are not the same. */
 783         if ((ret = (r1->path_type - r2->path_type)))
 784                 return ret;
 785
 786         if (IS_DEBUG_OSPF_EVENT)
 787                 zlog_debug("Route[Compare]: Path types are the same.");
 788         /* Path types are the same, compare any cost. */
 789         switch (r1->path_type) {
 790         case OSPF_PATH_INTRA_AREA:
 791         case OSPF_PATH_INTER_AREA:
 792                 break;
 793         case OSPF_PATH_TYPE1_EXTERNAL:
 794                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 795                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 796                                                   r2->u.ext.asbr);
 797                         if (ret != 0)
 798                                 return ret;
 799                 }
 800                 break;
 801         case OSPF_PATH_TYPE2_EXTERNAL:
 802                 if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
 803                         return ret;
 804
 805                 if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE)) {
 806                         ret = ospf_asbr_route_cmp(ospf, r1->u.ext.asbr,
 807                                                   r2->u.ext.asbr);
 808                         if (ret != 0)
 809                                 return ret;
 810                 }
 811                 break;
 812         }
 813
 814         /* Anyway, compare the costs. */
 815         return (r1->cost - r2->cost);
 816 }
 817
 818 static int ospf_path_exist(struct list *plist, struct in_addr nexthop,
 819                            struct ospf_interface *oi)
 820 {
 821         struct listnode *node, *nnode;
 822         struct ospf_path *path;
 823
 824         for (ALL_LIST_ELEMENTS(plist, node, nnode, path))
 825                 if (IPV4_ADDR_SAME(&path->nexthop, &nexthop)
 826                     && path->ifindex == oi->ifp->ifindex)
 827                         return 1;
 828
 829         return 0;
 830 }
 831
 832 void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area,
 833                                           struct ospf_route *to,
 834                                           struct vertex *v)
 835 {
 836         struct listnode *node;
 837         struct ospf_path *path;
 838         struct vertex_nexthop *nexthop;
 839         struct vertex_parent *vp;
 840         struct ospf_interface *oi = NULL;
 841
 842         assert(to->paths);
 843
 844         for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
 845                 nexthop = vp->nexthop;
 846
 847                 /*
 848                  * Only deal with interface data when we
 849                  * don't do a dry run
 850                  */
 851                 if (!area->spf_dry_run)
 852                         oi = ospf_if_lookup_by_lsa_pos(area, nexthop->lsa_pos);
 853
 854                 if ((oi && !ospf_path_exist(to->paths, nexthop->router, oi))
 855                     || area->spf_dry_run) {
 856                         path = ospf_path_new();
 857                         path->nexthop = nexthop->router;
 858                         path->adv_router = v->id;
 859
 860                         if (oi) {
 861                                 path->ifindex = oi->ifp->ifindex;
 862                                 if (CHECK_FLAG(oi->connected->flags,
 863                                                ZEBRA_IFA_UNNUMBERED))
 864                                         path->unnumbered = 1;
 865                         }
 866
 867                         listnode_add(to->paths, path);
 868                 }
 869         }
 870 }
 871
 872 struct ospf_path *ospf_path_lookup(struct list *plist, struct ospf_path *path)
 873 {
 874         struct listnode *node;
 875         struct ospf_path *op;
 876
 877         for (ALL_LIST_ELEMENTS_RO(plist, node, op)) {
 878                 if (!IPV4_ADDR_SAME(&op->nexthop, &path->nexthop))
 879                         continue;
 880                 if (!IPV4_ADDR_SAME(&op->adv_router, &path->adv_router))
 881                         continue;
 882                 if (op->ifindex != path->ifindex)
 883                         continue;
 884                 return op;
 885         }
 886         return NULL;
 887 }
 888
 889 void ospf_route_copy_nexthops(struct ospf_route *to, struct list *from)
 890 {
 891         struct listnode *node, *nnode;
 892         struct ospf_path *path;
 893
 894         assert(to->paths);
 895
 896         for (ALL_LIST_ELEMENTS(from, node, nnode, path))
 897                 /* The same routes are just discarded. */
 898                 if (!ospf_path_lookup(to->paths, path))
 899                         listnode_add(to->paths, ospf_path_dup(path));
 900 }
 901
 902 void ospf_route_subst_nexthops(struct ospf_route *to, struct list *from)
 903 {
 904
 905         list_delete_all_node(to->paths);
 906         ospf_route_copy_nexthops(to, from);
 907 }
 908
 909 void ospf_route_subst(struct route_node *rn, struct ospf_route *new_or,
 910                       struct ospf_route *over)
 911 {
 912         route_lock_node(rn);
 913         ospf_route_free(rn->info);
 914
 915         ospf_route_copy_nexthops(new_or, over->paths);
 916         rn->info = new_or;
 917         route_unlock_node(rn);
 918 }
 919
 920 void ospf_route_add(struct route_table *rt, struct prefix_ipv4 *p,
 921                     struct ospf_route *new_or, struct ospf_route *over)
 922 {
 923         struct route_node *rn;
 924
 925         rn = route_node_get(rt, (struct prefix *)p);
 926
 927         ospf_route_copy_nexthops(new_or, over->paths);
 928
 929         if (rn->info) {
 930                 if (IS_DEBUG_OSPF_EVENT)
 931                         zlog_debug("%s: something's wrong !", __func__);
 932                 route_unlock_node(rn);
 933                 return;
 934         }
 935
 936         rn->info = new_or;
 937 }
 938
 939 void ospf_prune_unreachable_networks(struct route_table *rt)
 940 {
 941         struct route_node *rn, *next;
 942         struct ospf_route * or ;
 943
 944         if (IS_DEBUG_OSPF_EVENT)
 945                 zlog_debug("Pruning unreachable networks");
 946
 947         for (rn = route_top(rt); rn; rn = next) {
 948                 next = route_next(rn);
 949                 if (rn->info != NULL) {
 950                         or = rn->info;
 951                         if (listcount(or->paths) == 0) {
 952                                 if (IS_DEBUG_OSPF_EVENT)
 953                                         zlog_debug("Pruning route to %pFX",
 954                                                    &rn->p);
 955
 956                                 ospf_route_free(or);
 957                                 rn->info = NULL;
 958                                 route_unlock_node(rn);
 959                         }
 960                 }
 961         }
 962 }
 963
 964 void ospf_prune_unreachable_routers(struct route_table *rtrs)
 965 {
 966         struct route_node *rn, *next;
 967         struct ospf_route * or ;
 968         struct listnode *node, *nnode;
 969         struct list *paths;
 970
 971         if (IS_DEBUG_OSPF_EVENT)
 972                 zlog_debug("Pruning unreachable routers");
 973
 974         for (rn = route_top(rtrs); rn; rn = next) {
 975                 next = route_next(rn);
 976                 if ((paths = rn->info) == NULL)
 977                         continue;
 978
 979                 for (ALL_LIST_ELEMENTS(paths, node, nnode, or)) {
 980                         if (listcount(or->paths) == 0) {
 981                                 if (IS_DEBUG_OSPF_EVENT) {
 982                                         zlog_debug("Pruning route to rtr %pI4",
 983                                                    &rn->p.u.prefix4);
 984                                         zlog_debug(
 985                                                 "               via area %pI4",
 986                                                 &or->u.std.area_id);
 987                                 }
 988
 989                                 listnode_delete(paths, or);
 990                                 ospf_route_free(or);
 991                         }
 992                 }
 993
 994                 if (listcount(paths) == 0) {
 995                         if (IS_DEBUG_OSPF_EVENT)
 996                                 zlog_debug("Pruning router node %pI4",
 997                                            &rn->p.u.prefix4);
 998
 999                         list_delete(&paths);
1000                         rn->info = NULL;
1001                         route_unlock_node(rn);
1002                 }
1003         }
1004 }
1005
1006 int ospf_add_discard_route(struct ospf *ospf, struct route_table *rt,
1007                            struct ospf_area *area, struct prefix_ipv4 *p)
1008 {
1009         struct route_node *rn;
1010         struct ospf_route * or, *new_or;
1011
1012         rn = route_node_get(rt, (struct prefix *)p);
1013
1014         if (rn == NULL) {
1015                 if (IS_DEBUG_OSPF_EVENT)
1016                         zlog_debug("%s: router installation error", __func__);
1017                 return 0;
1018         }
1019
1020         if (rn->info) /* If the route to the same destination is found */
1021         {
1022                 route_unlock_node(rn);
1023
1024                 or = rn->info;
1025
1026                 if (or->path_type == OSPF_PATH_INTRA_AREA) {
1027                         if (IS_DEBUG_OSPF_EVENT)
1028                                 zlog_debug("%s: an intra-area route exists",
1029                                            __func__);
1030                         return 0;
1031                 }
1032
1033                 if (or->type == OSPF_DESTINATION_DISCARD) {
1034                         if (IS_DEBUG_OSPF_EVENT)
1035                                 zlog_debug(
1036                                         "%s: discard entry already installed",
1037                                         __func__);
1038                         return 0;
1039                 }
1040
1041                 ospf_route_free(rn->info);
1042         }
1043
1044         if (IS_DEBUG_OSPF_EVENT)
1045                 zlog_debug("%s: adding %pFX", __func__, p);
1046
1047         new_or = ospf_route_new();
1048         new_or->type = OSPF_DESTINATION_DISCARD;
1049         new_or->id.s_addr = INADDR_ANY;
1050         new_or->cost = 0;
1051         new_or->u.std.area_id = area->area_id;
1052         new_or->u.std.external_routing = area->external_routing;
1053         new_or->path_type = OSPF_PATH_INTER_AREA;
1054         rn->info = new_or;
1055
1056         ospf_zebra_add_discard(ospf, p);
1057
1058         return 1;
1059 }
1060
1061 void ospf_delete_discard_route(struct ospf *ospf, struct route_table *rt,
1062                                struct prefix_ipv4 *p)
1063 {
1064         struct route_node *rn;
1065         struct ospf_route * or ;
1066
1067         if (IS_DEBUG_OSPF_EVENT)
1068                 zlog_debug("%s: deleting %pFX", __func__, p);
1069
1070         rn = route_node_lookup(rt, (struct prefix *)p);
1071
1072         if (rn == NULL) {
1073                 if (IS_DEBUG_OSPF_EVENT)
1074                         zlog_debug("%s: no route found", __func__);
1075                 return;
1076         }
1077
1078         or = rn->info;
1079
1080         if (or->path_type == OSPF_PATH_INTRA_AREA) {
1081                 if (IS_DEBUG_OSPF_EVENT)
1082                         zlog_debug("%s: an intra-area route exists", __func__);
1083                 return;
1084         }
1085
1086         if (or->type != OSPF_DESTINATION_DISCARD) {
1087                 if (IS_DEBUG_OSPF_EVENT)
1088                         zlog_debug("%s: not a discard entry", __func__);
1089                 return;
1090         }
1091
1092         /* free the route entry and the route node */
1093         ospf_route_free(rn->info);
1094
1095         rn->info = NULL;
1096         route_unlock_node(rn);
1097         route_unlock_node(rn);
1098
1099         /* remove the discard entry from the rib */
1100         ospf_zebra_delete_discard(ospf, p);
1101
1102         return;
1103 }