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