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