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