ospfd/ospf_ase.c

   1 /*
   2  * OSPF AS external route calculation.
   3  * Copyright (C) 1999, 2000 Alex Zinin, 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 "thread.h"
  25 #include "memory.h"
  26 #include "hash.h"
  27 #include "linklist.h"
  28 #include "prefix.h"
  29 #include "if.h"
  30 #include "table.h"
  31 #include "vty.h"
  32 #include "log.h"
  33
  34 #include "ospfd/ospfd.h"
  35 #include "ospfd/ospf_interface.h"
  36 #include "ospfd/ospf_ism.h"
  37 #include "ospfd/ospf_asbr.h"
  38 #include "ospfd/ospf_lsa.h"
  39 #include "ospfd/ospf_lsdb.h"
  40 #include "ospfd/ospf_neighbor.h"
  41 #include "ospfd/ospf_nsm.h"
  42 #include "ospfd/ospf_spf.h"
  43 #include "ospfd/ospf_route.h"
  44 #include "ospfd/ospf_ase.h"
  45 #include "ospfd/ospf_zebra.h"
  46 #include "ospfd/ospf_dump.h"
  47
  48 struct ospf_route *ospf_find_asbr_route(struct ospf *ospf,
  49                                         struct route_table *rtrs,
  50                                         struct prefix_ipv4 *asbr)
  51 {
  52         struct route_node *rn;
  53         struct ospf_route * or, *best = NULL;
  54         struct listnode *node;
  55         struct list *chosen;
  56
  57         /* Sanity check. */
  58         if (rtrs == NULL)
  59                 return NULL;
  60
  61         rn = route_node_lookup(rtrs, (struct prefix *)asbr);
  62         if (!rn)
  63                 return NULL;
  64
  65         route_unlock_node(rn);
  66
  67         chosen = list_new();
  68
  69         /* First try to find intra-area non-bb paths. */
  70         if (!CHECK_FLAG(ospf->config, OSPF_RFC1583_COMPATIBLE))
  71                 for (ALL_LIST_ELEMENTS_RO((struct list *)rn->info, node, or))
  72                         if (or->cost < OSPF_LS_INFINITY)
  73                                 if (!OSPF_IS_AREA_ID_BACKBONE(or->u.std.area_id)
  74                                             &&
  75                                     or->path_type == OSPF_PATH_INTRA_AREA)
  76                                         listnode_add(chosen, or);
  77
  78         /* If none is found -- look through all. */
  79         if (listcount(chosen) == 0) {
  80                 list_delete_and_null(&chosen);
  81                 chosen = rn->info;
  82         }
  83
  84         /* Now find the route with least cost. */
  85         for (ALL_LIST_ELEMENTS_RO(chosen, node, or))
  86                 if (or->cost < OSPF_LS_INFINITY) {
  87                         if (best == NULL)
  88                                 best = or ;
  89                         else if (best->cost > or->cost)
  90                                 best = or ;
  91                         else if (best->cost ==
  92                                  or->cost
  93                                            && IPV4_ADDR_CMP(
  94                                                       &best->u.std.area_id,
  95                                                       & or->u.std.area_id)
  96                                                       < 0)
  97                                 best = or ;
  98                 }
  99
 100         if (chosen != rn->info)
 101                 list_delete_and_null(&chosen);
 102
 103         return best;
 104 }
 105
 106 struct ospf_route *ospf_find_asbr_route_through_area(struct route_table *rtrs,
 107                                                      struct prefix_ipv4 *asbr,
 108                                                      struct ospf_area *area)
 109 {
 110         struct route_node *rn;
 111
 112         /* Sanity check. */
 113         if (rtrs == NULL)
 114                 return NULL;
 115
 116         rn = route_node_lookup(rtrs, (struct prefix *)asbr);
 117
 118         if (rn) {
 119                 struct listnode *node;
 120                 struct ospf_route * or ;
 121
 122                 route_unlock_node(rn);
 123
 124                 for (ALL_LIST_ELEMENTS_RO((struct list *)rn->info, node, or))
 125                         if (IPV4_ADDR_SAME(& or->u.std.area_id, &area->area_id))
 126                                 return or ;
 127         }
 128
 129         return NULL;
 130 }
 131
 132 static void ospf_ase_complete_direct_routes(struct ospf_route *ro,
 133                                             struct in_addr nexthop)
 134 {
 135         struct listnode *node;
 136         struct ospf_path *op;
 137
 138         for (ALL_LIST_ELEMENTS_RO(ro->paths, node, op))
 139                 if (op->nexthop.s_addr == 0)
 140                         op->nexthop.s_addr = nexthop.s_addr;
 141 }
 142
 143 static int ospf_ase_forward_address_check(struct ospf *ospf,
 144                                           struct in_addr fwd_addr)
 145 {
 146         struct listnode *ifn;
 147         struct ospf_interface *oi;
 148
 149         for (ALL_LIST_ELEMENTS_RO(ospf->oiflist, ifn, oi))
 150                 if (if_is_operative(oi->ifp))
 151                         if (oi->type != OSPF_IFTYPE_VIRTUALLINK)
 152                                 if (IPV4_ADDR_SAME(&oi->address->u.prefix4,
 153                                                    &fwd_addr))
 154                                         return 0;
 155
 156         return 1;
 157 }
 158
 159 #if 0
 160 /* Calculate ASBR route. */
 161 static struct ospf_route *
 162 ospf_ase_calculate_asbr_route (struct ospf *ospf,
 163                                struct route_table *rt_network,
 164                                struct route_table *rt_router,
 165                                struct as_external_lsa *al)
 166 {
 167   struct prefix_ipv4 asbr;
 168   struct ospf_route *asbr_route;
 169   struct route_node *rn;
 170
 171   /* Find ASBR route from Router routing table. */
 172   asbr.family = AF_INET;
 173   asbr.prefix = al->header.adv_router;
 174   asbr.prefixlen = IPV4_MAX_BITLEN;
 175   apply_mask_ipv4 (&asbr);
 176
 177   asbr_route = ospf_find_asbr_route (ospf, rt_router, &asbr);
 178
 179   if (asbr_route == NULL)
 180     {
 181       if (IS_DEBUG_OSPF (lsa, LSA))
 182         zlog_debug ("ospf_ase_calculate(): Route to ASBR %s not found",
 183                     inet_ntoa (asbr.prefix));
 184       return NULL;
 185     }
 186
 187   if (!(asbr_route->u.std.flags & ROUTER_LSA_EXTERNAL))
 188     {
 189       if (IS_DEBUG_OSPF (lsa, LSA))
 190         zlog_debug ("ospf_ase_calculate(): Originating router is not an ASBR");
 191       return NULL;
 192     }
 193
 194   if (al->e[0].fwd_addr.s_addr != 0)
 195     {
 196       if (IS_DEBUG_OSPF (lsa, LSA))
 197         zlog_debug ("ospf_ase_calculate(): "
 198                     "Forwarding address is not 0.0.0.0.");
 199
 200       if (! ospf_ase_forward_address_check (ospf, al->e[0].fwd_addr))
 201         {
 202           if (IS_DEBUG_OSPF (lsa, LSA))
 203             zlog_debug ("ospf_ase_calculate(): "
 204                         "Forwarding address is one of our addresses, Ignore.");
 205           return NULL;
 206         }
 207
 208       if (IS_DEBUG_OSPF (lsa, LSA))
 209         zlog_debug ("ospf_ase_calculate(): "
 210                     "Looking up in the Network Routing Table.");
 211
 212       /* Looking up the path to the fwd_addr from Network route. */
 213       asbr.family = AF_INET;
 214       asbr.prefix = al->e[0].fwd_addr;
 215       asbr.prefixlen = IPV4_MAX_BITLEN;
 216
 217       rn = route_node_match (rt_network, (struct prefix *) &asbr);
 218
 219       if (rn == NULL)
 220         {
 221           if (IS_DEBUG_OSPF (lsa, LSA))
 222             zlog_debug ("ospf_ase_calculate(): "
 223                         "Couldn't find a route to the forwarding address.");
 224           return NULL;
 225         }
 226
 227       route_unlock_node (rn);
 228
 229       if ((asbr_route = rn->info) == NULL)
 230         {
 231           if (IS_DEBUG_OSPF (lsa, LSA))
 232             zlog_debug ("ospf_ase_calculate(): "
 233                         "Somehow OSPF route to ASBR is lost");
 234           return NULL;
 235         }
 236     }
 237
 238   return asbr_route;
 239 }
 240 #endif
 241
 242 static struct ospf_route *
 243 ospf_ase_calculate_new_route(struct ospf_lsa *lsa,
 244                              struct ospf_route *asbr_route, u_int32_t metric)
 245 {
 246         struct as_external_lsa *al;
 247         struct ospf_route *new;
 248
 249         al = (struct as_external_lsa *)lsa->data;
 250
 251         new = ospf_route_new();
 252
 253         /* Set redistributed type -- does make sense? */
 254         /* new->type = type; */
 255         new->id = al->header.id;
 256         new->mask = al->mask;
 257
 258         if (!IS_EXTERNAL_METRIC(al->e[0].tos)) {
 259                 if (IS_DEBUG_OSPF(lsa, LSA))
 260                         zlog_debug("Route[External]: type-1 created.");
 261                 new->path_type = OSPF_PATH_TYPE1_EXTERNAL;
 262                 new->cost = asbr_route->cost + metric; /* X + Y */
 263         } else {
 264                 if (IS_DEBUG_OSPF(lsa, LSA))
 265                         zlog_debug("Route[External]: type-2 created.");
 266                 new->path_type = OSPF_PATH_TYPE2_EXTERNAL;
 267                 new->cost = asbr_route->cost;   /* X */
 268                 new->u.ext.type2_cost = metric; /* Y */
 269         }
 270
 271         new->type = OSPF_DESTINATION_NETWORK;
 272         new->u.ext.origin = lsa;
 273         new->u.ext.tag = ntohl(al->e[0].route_tag);
 274         new->u.ext.asbr = asbr_route;
 275
 276         assert(new != asbr_route);
 277
 278         return new;
 279 }
 280
 281 #define OSPF_ASE_CALC_INTERVAL 1
 282
 283 int ospf_ase_calculate_route(struct ospf *ospf, struct ospf_lsa *lsa)
 284 {
 285         u_int32_t metric;
 286         struct as_external_lsa *al;
 287         struct ospf_route *asbr_route;
 288         struct prefix_ipv4 asbr, p;
 289         struct route_node *rn;
 290         struct ospf_route *new, * or ;
 291         int ret;
 292
 293         assert(lsa);
 294         al = (struct as_external_lsa *)lsa->data;
 295
 296         if (lsa->data->type == OSPF_AS_NSSA_LSA)
 297                 if (IS_DEBUG_OSPF_NSSA)
 298                         zlog_debug("ospf_ase_calc(): Processing Type-7");
 299
 300         /* Stay away from any Local Translated Type-7 LSAs */
 301         if (CHECK_FLAG(lsa->flags, OSPF_LSA_LOCAL_XLT)) {
 302                 if (IS_DEBUG_OSPF_NSSA)
 303                         zlog_debug("ospf_ase_calc(): Rejecting Local Xlt'd");
 304                 return 0;
 305         }
 306
 307         if (IS_DEBUG_OSPF(lsa, LSA))
 308                 zlog_debug(
 309                         "Route[External]: Calculate AS-external-LSA to %s/%d",
 310                         inet_ntoa(al->header.id), ip_masklen(al->mask));
 311         /* (1) If the cost specified by the LSA is LSInfinity, or if the
 312                LSA's LS age is equal to MaxAge, then examine the next LSA. */
 313         if ((metric = GET_METRIC(al->e[0].metric)) >= OSPF_LS_INFINITY) {
 314                 if (IS_DEBUG_OSPF(lsa, LSA))
 315                         zlog_debug(
 316                                 "Route[External]: Metric is OSPF_LS_INFINITY");
 317                 return 0;
 318         }
 319         if (IS_LSA_MAXAGE(lsa)) {
 320                 if (IS_DEBUG_OSPF(lsa, LSA))
 321                         zlog_debug(
 322                                 "Route[External]: AS-external-LSA is MAXAGE");
 323                 return 0;
 324         }
 325
 326         /* (2) If the LSA was originated by the calculating router itself,
 327            examine the next LSA. */
 328         if (IS_LSA_SELF(lsa)) {
 329                 if (IS_DEBUG_OSPF(lsa, LSA))
 330                         zlog_debug(
 331                                 "Route[External]: AS-external-LSA is self originated");
 332                 return 0;
 333         }
 334
 335         /* (3) Call the destination described by the LSA N.  N's address is
 336                obtained by masking the LSA's Link State ID with the
 337                network/subnet mask contained in the body of the LSA.  Look
 338                up the routing table entries (potentially one per attached
 339                area) for the AS boundary router (ASBR) that originated the
 340                LSA. If no entries exist for router ASBR (i.e., ASBR is
 341                unreachable), do nothing with this LSA and consider the next
 342                in the list. */
 343
 344         asbr.family = AF_INET;
 345         asbr.prefix = al->header.adv_router;
 346         asbr.prefixlen = IPV4_MAX_BITLEN;
 347         apply_mask_ipv4(&asbr);
 348
 349         asbr_route = ospf_find_asbr_route(ospf, ospf->new_rtrs, &asbr);
 350         if (asbr_route == NULL) {
 351                 if (IS_DEBUG_OSPF(lsa, LSA))
 352                         zlog_debug(
 353                                 "Route[External]: Can't find originating ASBR route");
 354                 return 0;
 355         }
 356         if (!(asbr_route->u.std.flags & ROUTER_LSA_EXTERNAL)) {
 357                 if (IS_DEBUG_OSPF(lsa, LSA))
 358                         zlog_debug(
 359                                 "Route[External]: Originating router is not an ASBR");
 360                 return 0;
 361         }
 362
 363         /*     Else, this LSA describes an AS external path to destination
 364                N.  Examine the forwarding address specified in the AS-
 365                external-LSA.  This indicates the IP address to which
 366                packets for the destination should be forwarded. */
 367
 368         if (al->e[0].fwd_addr.s_addr == 0) {
 369                 /* If the forwarding address is set to 0.0.0.0, packets should
 370                    be sent to the ASBR itself. Among the multiple routing table
 371                    entries for the ASBR, select the preferred entry as follows.
 372                    If RFC1583Compatibility is set to "disabled", prune the set
 373                    of routing table entries for the ASBR as described in
 374                    Section 16.4.1. In any case, among the remaining routing
 375                    table entries, select the routing table entry with the least
 376                    cost; when there are multiple least cost routing table
 377                    entries the entry whose associated area has the largest OSPF
 378                    Area ID (when considered as an unsigned 32-bit integer) is
 379                    chosen. */
 380
 381                 /* asbr_route already contains the requested route */
 382         } else {
 383                 /* If the forwarding address is non-zero, look up the
 384                    forwarding address in the routing table.[24] The matching
 385                    routing table entry must specify an intra-area or inter-area
 386                    path; if no such path exists, do nothing with the LSA and
 387                    consider the next in the list. */
 388                 if (!ospf_ase_forward_address_check(ospf, al->e[0].fwd_addr)) {
 389                         if (IS_DEBUG_OSPF(lsa, LSA))
 390                                 zlog_debug(
 391                                         "Route[External]: Forwarding address is our router "
 392                                         "address");
 393                         return 0;
 394                 }
 395
 396                 asbr.family = AF_INET;
 397                 asbr.prefix = al->e[0].fwd_addr;
 398                 asbr.prefixlen = IPV4_MAX_BITLEN;
 399
 400                 rn = route_node_match(ospf->new_table, (struct prefix *)&asbr);
 401
 402                 if (rn == NULL || (asbr_route = rn->info) == NULL) {
 403                         if (IS_DEBUG_OSPF(lsa, LSA))
 404                                 zlog_debug(
 405                                         "Route[External]: Can't find route to forwarding "
 406                                         "address");
 407                         if (rn)
 408                                 route_unlock_node(rn);
 409                         return 0;
 410                 }
 411
 412                 route_unlock_node(rn);
 413         }
 414
 415         /* (4) Let X be the cost specified by the preferred routing table
 416                entry for the ASBR/forwarding address, and Y the cost
 417                specified in the LSA.  X is in terms of the link state
 418                metric, and Y is a type 1 or 2 external metric. */
 419
 420
 421         /* (5) Look up the routing table entry for the destination N.  If
 422                no entry exists for N, install the AS external path to N,
 423                with next hop equal to the list of next hops to the
 424                forwarding address, and advertising router equal to ASBR.
 425                If the external metric type is 1, then the path-type is set
 426                to type 1 external and the cost is equal to X+Y.  If the
 427                external metric type is 2, the path-type is set to type 2
 428                external, the link state component of the route's cost is X,
 429                and the type 2 cost is Y. */
 430         new = ospf_ase_calculate_new_route(lsa, asbr_route, metric);
 431
 432         /* (6) Compare the AS external path described by the LSA with the
 433                existing paths in N's routing table entry, as follows. If
 434                the new path is preferred, it replaces the present paths in
 435                N's routing table entry.  If the new path is of equal
 436                preference, it is added to N's routing table entry's list of
 437                paths. */
 438
 439         /* Set prefix. */
 440         p.family = AF_INET;
 441         p.prefix = al->header.id;
 442         p.prefixlen = ip_masklen(al->mask);
 443
 444         /* if there is a Intra/Inter area route to the N
 445            do not install external route */
 446         if ((rn = route_node_lookup(ospf->new_table, (struct prefix *)&p))) {
 447                 route_unlock_node(rn);
 448                 if (rn->info == NULL)
 449                         zlog_info("Route[External]: rn->info NULL");
 450                 if (new)
 451                         ospf_route_free(new);
 452                 return 0;
 453         }
 454         /* Find a route to the same dest */
 455         /* If there is no route, create new one. */
 456         if ((rn = route_node_lookup(ospf->new_external_route,
 457                                     (struct prefix *)&p)))
 458                 route_unlock_node(rn);
 459
 460         if (!rn || (or = rn->info) == NULL) {
 461                 if (IS_DEBUG_OSPF(lsa, LSA))
 462                         zlog_debug("Route[External]: Adding a new route %s/%d",
 463                                    inet_ntoa(p.prefix), p.prefixlen);
 464
 465                 ospf_route_add(ospf->new_external_route, &p, new, asbr_route);
 466
 467                 if (al->e[0].fwd_addr.s_addr)
 468                         ospf_ase_complete_direct_routes(new, al->e[0].fwd_addr);
 469                 return 0;
 470         } else {
 471                 /* (a) Intra-area and inter-area paths are always preferred
 472                        over AS external paths.
 473
 474                    (b) Type 1 external paths are always preferred over type 2
 475                        external paths. When all paths are type 2 external
 476                        paths, the paths with the smallest advertised type 2
 477                        metric are always preferred. */
 478                 ret = ospf_route_cmp(ospf, new, or);
 479
 480                 /*     (c) If the new AS external path is still
 481                    indistinguishable
 482                            from the current paths in the N's routing table
 483                    entry,
 484                            and RFC1583Compatibility is set to "disabled", select
 485                            the preferred paths based on the intra-AS paths to
 486                    the
 487                            ASBR/forwarding addresses, as specified in Section
 488                            16.4.1.
 489
 490                        (d) If the new AS external path is still
 491                    indistinguishable
 492                            from the current paths in the N's routing table
 493                    entry,
 494                            select the preferred path based on a least cost
 495                            comparison.  Type 1 external paths are compared by
 496                            looking at the sum of the distance to the forwarding
 497                            address and the advertised type 1 metric (X+Y).  Type
 498                    2
 499                            external paths advertising equal type 2 metrics are
 500                            compared by looking at the distance to the forwarding
 501                            addresses.
 502                 */
 503                 /* New route is better */
 504                 if (ret < 0) {
 505                         if (IS_DEBUG_OSPF(lsa, LSA))
 506                                 zlog_debug(
 507                                         "Route[External]: New route is better");
 508                         ospf_route_subst(rn, new, asbr_route);
 509                         if (al->e[0].fwd_addr.s_addr)
 510                                 ospf_ase_complete_direct_routes(
 511                                         new, al->e[0].fwd_addr);
 512                         or = new;
 513                         new = NULL;
 514                 }
 515                 /* Old route is better */
 516                 else if (ret > 0) {
 517                         if (IS_DEBUG_OSPF(lsa, LSA))
 518                                 zlog_debug(
 519                                         "Route[External]: Old route is better");
 520                         /* do nothing */
 521                 }
 522                 /* Routes are equal */
 523                 else {
 524                         if (IS_DEBUG_OSPF(lsa, LSA))
 525                                 zlog_debug("Route[External]: Routes are equal");
 526                         ospf_route_copy_nexthops(or, asbr_route->paths);
 527                         if (al->e[0].fwd_addr.s_addr)
 528                                 ospf_ase_complete_direct_routes(
 529                                         or, al->e[0].fwd_addr);
 530                 }
 531         }
 532         /* Make sure setting newly calculated ASBR route.*/
 533         or->u.ext.asbr = asbr_route;
 534         if (new)
 535                 ospf_route_free(new);
 536
 537         lsa->route = or ;
 538         return 0;
 539 }
 540
 541 static int ospf_ase_route_match_same(struct route_table *rt,
 542                                      struct prefix *prefix,
 543                                      struct ospf_route *newor)
 544 {
 545         struct route_node *rn;
 546         struct ospf_route * or ;
 547         struct ospf_path *op;
 548         struct ospf_path *newop;
 549         struct listnode *n1;
 550         struct listnode *n2;
 551
 552         if (!rt || !prefix)
 553                 return 0;
 554
 555         rn = route_node_lookup(rt, prefix);
 556         if (!rn)
 557                 return 0;
 558
 559         route_unlock_node(rn);
 560
 561         or = rn->info;
 562         if (or->path_type != newor->path_type)
 563                 return 0;
 564
 565         switch (or->path_type) {
 566         case OSPF_PATH_TYPE1_EXTERNAL:
 567                 if (or->cost != newor->cost)
 568                         return 0;
 569                 break;
 570         case OSPF_PATH_TYPE2_EXTERNAL:
 571                 if ((or->cost != newor->cost)
 572                     || (or->u.ext.type2_cost != newor->u.ext.type2_cost))
 573                         return 0;
 574                 break;
 575         default:
 576                 assert(0);
 577                 return 0;
 578         }
 579
 580         if (or->paths->count != newor->paths->count)
 581                 return 0;
 582
 583         /* Check each path. */
 584         for (n1 = listhead(or->paths), n2 = listhead(newor->paths); n1 && n2;
 585              n1 = listnextnode(n1), n2 = listnextnode(n2)) {
 586                 op = listgetdata(n1);
 587                 newop = listgetdata(n2);
 588
 589                 if (!IPV4_ADDR_SAME(&op->nexthop, &newop->nexthop))
 590                         return 0;
 591                 if (op->ifindex != newop->ifindex)
 592                         return 0;
 593         }
 594
 595         if (or->u.ext.tag != newor->u.ext.tag)
 596                 return 0;
 597
 598         return 1;
 599 }
 600
 601 static int ospf_ase_compare_tables(struct ospf *ospf,
 602                                    struct route_table *new_external_route,
 603                                    struct route_table *old_external_route)
 604 {
 605         struct route_node *rn, *new_rn;
 606         struct ospf_route * or ;
 607
 608         /* Remove deleted routes */
 609         for (rn = route_top(old_external_route); rn; rn = route_next(rn))
 610                 if ((or = rn->info)) {
 611                         if (!(new_rn = route_node_lookup(new_external_route,
 612                                                          &rn->p)))
 613                                 ospf_zebra_delete(
 614                                         ospf, (struct prefix_ipv4 *)&rn->p, or);
 615                         else
 616                                 route_unlock_node(new_rn);
 617                 }
 618
 619
 620         /* Install new routes */
 621         for (rn = route_top(new_external_route); rn; rn = route_next(rn))
 622                 if ((or = rn->info) != NULL)
 623                         if (!ospf_ase_route_match_same(old_external_route,
 624                                                        &rn->p, or))
 625                                 ospf_zebra_add(
 626                                         ospf, (struct prefix_ipv4 *)&rn->p, or);
 627
 628         return 0;
 629 }
 630
 631 static int ospf_ase_calculate_timer(struct thread *t)
 632 {
 633         struct ospf *ospf;
 634         struct ospf_lsa *lsa;
 635         struct route_node *rn;
 636         struct listnode *node;
 637         struct ospf_area *area;
 638         struct timeval start_time, stop_time;
 639
 640         ospf = THREAD_ARG(t);
 641         ospf->t_ase_calc = NULL;
 642
 643         if (ospf->ase_calc) {
 644                 ospf->ase_calc = 0;
 645
 646                 monotime(&start_time);
 647
 648                 /* Calculate external route for each AS-external-LSA */
 649                 LSDB_LOOP (EXTERNAL_LSDB(ospf), rn, lsa)
 650                         ospf_ase_calculate_route(ospf, lsa);
 651
 652                 /*  This version simple adds to the table all NSSA areas  */
 653                 if (ospf->anyNSSA)
 654                         for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area)) {
 655                                 if (IS_DEBUG_OSPF_NSSA)
 656                                         zlog_debug(
 657                                                 "ospf_ase_calculate_timer(): looking at area %s",
 658                                                 inet_ntoa(area->area_id));
 659
 660                                 if (area->external_routing == OSPF_AREA_NSSA)
 661                                         LSDB_LOOP (NSSA_LSDB(area), rn, lsa)
 662                                                 ospf_ase_calculate_route(ospf,
 663                                                                          lsa);
 664                         }
 665                 /* kevinm: And add the NSSA routes in ospf_top */
 666                 LSDB_LOOP (NSSA_LSDB(ospf), rn, lsa)
 667                         ospf_ase_calculate_route(ospf, lsa);
 668
 669                 /* Compare old and new external routing table and install the
 670                    difference info zebra/kernel */
 671                 ospf_ase_compare_tables(ospf, ospf->new_external_route,
 672                                         ospf->old_external_route);
 673
 674                 /* Delete old external routing table */
 675                 ospf_route_table_free(ospf->old_external_route);
 676                 ospf->old_external_route = ospf->new_external_route;
 677                 ospf->new_external_route = route_table_init();
 678
 679                 monotime(&stop_time);
 680
 681                 if (IS_DEBUG_OSPF_EVENT)
 682                         zlog_info(
 683                                 "SPF Processing Time(usecs): External Routes: %lld\n",
 684                                 (stop_time.tv_sec - start_time.tv_sec)
 685                                                 * 1000000LL
 686                                         + (stop_time.tv_usec
 687                                            - start_time.tv_usec));
 688         }
 689         return 0;
 690 }
 691
 692 void ospf_ase_calculate_schedule(struct ospf *ospf)
 693 {
 694         if (ospf == NULL)
 695                 return;
 696
 697         ospf->ase_calc = 1;
 698 }
 699
 700 void ospf_ase_calculate_timer_add(struct ospf *ospf)
 701 {
 702         if (ospf == NULL)
 703                 return;
 704
 705         thread_add_timer(master, ospf_ase_calculate_timer, ospf,
 706                          OSPF_ASE_CALC_INTERVAL, &ospf->t_ase_calc);
 707 }
 708
 709 void ospf_ase_register_external_lsa(struct ospf_lsa *lsa, struct ospf *top)
 710 {
 711         struct route_node *rn;
 712         struct prefix_ipv4 p;
 713         struct list *lst;
 714         struct as_external_lsa *al;
 715
 716         al = (struct as_external_lsa *)lsa->data;
 717         p.family = AF_INET;
 718         p.prefix = lsa->data->id;
 719         p.prefixlen = ip_masklen(al->mask);
 720         apply_mask_ipv4(&p);
 721
 722         rn = route_node_get(top->external_lsas, (struct prefix *)&p);
 723         if ((lst = rn->info) == NULL)
 724                 rn->info = lst = list_new();
 725         else
 726                 route_unlock_node(rn);
 727
 728         /* We assume that if LSA is deleted from DB
 729            is is also deleted from this RT */
 730         listnode_add(lst, ospf_lsa_lock(lsa)); /* external_lsas lst */
 731 }
 732
 733 void ospf_ase_unregister_external_lsa(struct ospf_lsa *lsa, struct ospf *top)
 734 {
 735         struct route_node *rn;
 736         struct prefix_ipv4 p;
 737         struct list *lst;
 738         struct as_external_lsa *al;
 739
 740         al = (struct as_external_lsa *)lsa->data;
 741         p.family = AF_INET;
 742         p.prefix = lsa->data->id;
 743         p.prefixlen = ip_masklen(al->mask);
 744         apply_mask_ipv4(&p);
 745
 746         rn = route_node_lookup(top->external_lsas, (struct prefix *)&p);
 747
 748         if (rn) {
 749                 lst = rn->info;
 750                 listnode_delete(lst, lsa);
 751                 ospf_lsa_unlock(&lsa); /* external_lsas list */
 752                 route_unlock_node(rn);
 753         }
 754 }
 755
 756 void ospf_ase_external_lsas_finish(struct route_table *rt)
 757 {
 758         struct route_node *rn;
 759         struct ospf_lsa *lsa;
 760         struct list *lst;
 761         struct listnode *node, *nnode;
 762
 763         for (rn = route_top(rt); rn; rn = route_next(rn))
 764                 if ((lst = rn->info) != NULL) {
 765                         for (ALL_LIST_ELEMENTS(lst, node, nnode, lsa))
 766                                 ospf_lsa_unlock(&lsa); /* external_lsas lst */
 767                         list_delete_and_null(&lst);
 768                 }
 769
 770         route_table_finish(rt);
 771 }
 772
 773 void ospf_ase_incremental_update(struct ospf *ospf, struct ospf_lsa *lsa)
 774 {
 775         struct list *lsas;
 776         struct listnode *node;
 777         struct route_node *rn, *rn2;
 778         struct prefix_ipv4 p;
 779         struct route_table *tmp_old;
 780         struct as_external_lsa *al;
 781
 782         al = (struct as_external_lsa *)lsa->data;
 783         p.family = AF_INET;
 784         p.prefix = lsa->data->id;
 785         p.prefixlen = ip_masklen(al->mask);
 786         apply_mask_ipv4(&p);
 787
 788         /* if new_table is NULL, there was no spf calculation, thus
 789            incremental update is unneeded */
 790         if (!ospf->new_table)
 791                 return;
 792
 793         /* If there is already an intra-area or inter-area route
 794            to the destination, no recalculation is necessary
 795            (internal routes take precedence). */
 796
 797         rn = route_node_lookup(ospf->new_table, (struct prefix *)&p);
 798         if (rn) {
 799                 route_unlock_node(rn);
 800                 if (rn->info)
 801                         return;
 802         }
 803
 804         rn = route_node_lookup(ospf->external_lsas, (struct prefix *)&p);
 805         assert(rn);
 806         assert(rn->info);
 807         lsas = rn->info;
 808         route_unlock_node(rn);
 809
 810         for (ALL_LIST_ELEMENTS_RO(lsas, node, lsa))
 811                 ospf_ase_calculate_route(ospf, lsa);
 812
 813         /* prepare temporary old routing table for compare */
 814         tmp_old = route_table_init();
 815         rn = route_node_lookup(ospf->old_external_route, (struct prefix *)&p);
 816         if (rn && rn->info) {
 817                 rn2 = route_node_get(tmp_old, (struct prefix *)&p);
 818                 rn2->info = rn->info;
 819                 route_unlock_node(rn);
 820         }
 821
 822         /* install changes to zebra */
 823         ospf_ase_compare_tables(ospf, ospf->new_external_route, tmp_old);
 824
 825         /* update ospf->old_external_route table */
 826         if (rn && rn->info)
 827                 ospf_route_free((struct ospf_route *)rn->info);
 828
 829         rn2 = route_node_lookup(ospf->new_external_route, (struct prefix *)&p);
 830         /* if new route exists, install it to ospf->old_external_route */
 831         if (rn2 && rn2->info) {
 832                 if (!rn)
 833                         rn = route_node_get(ospf->old_external_route,
 834                                             (struct prefix *)&p);
 835                 rn->info = rn2->info;
 836         } else {
 837                 /* remove route node from ospf->old_external_route */
 838                 if (rn) {
 839                         rn->info = NULL;
 840                         route_unlock_node(rn);
 841                 }
 842         }
 843
 844         if (rn2) {
 845                 /* rn2->info is stored in route node of ospf->old_external_route
 846                  */
 847                 rn2->info = NULL;
 848                 route_unlock_node(rn2);
 849                 route_unlock_node(rn2);
 850         }
 851
 852         route_table_finish(tmp_old);
 853 }