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(ospf,
 614                                                   (struct prefix_ipv4 *)&rn->p,
 615                                                   or);
 616                         else
 617                                 route_unlock_node(new_rn);
 618                 }
 619
 620
 621         /* Install new routes */
 622         for (rn = route_top(new_external_route); rn; rn = route_next(rn))
 623                 if ((or = rn->info) != NULL)
 624                         if (!ospf_ase_route_match_same(old_external_route,
 625                                                        &rn->p, or))
 626                                 ospf_zebra_add(ospf,
 627                                                (struct prefix_ipv4 *)&rn->p,
 628                                                or);
 629
 630         return 0;
 631 }
 632
 633 static int ospf_ase_calculate_timer(struct thread *t)
 634 {
 635         struct ospf *ospf;
 636         struct ospf_lsa *lsa;
 637         struct route_node *rn;
 638         struct listnode *node;
 639         struct ospf_area *area;
 640         struct timeval start_time, stop_time;
 641
 642         ospf = THREAD_ARG(t);
 643         ospf->t_ase_calc = NULL;
 644
 645         if (ospf->ase_calc) {
 646                 ospf->ase_calc = 0;
 647
 648                 monotime(&start_time);
 649
 650                 /* Calculate external route for each AS-external-LSA */
 651                 LSDB_LOOP(EXTERNAL_LSDB(ospf), rn, lsa)
 652                         ospf_ase_calculate_route(ospf, lsa);
 653
 654                 /*  This version simple adds to the table all NSSA areas  */
 655                 if (ospf->anyNSSA)
 656                         for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area)) {
 657                                 if (IS_DEBUG_OSPF_NSSA)
 658                                         zlog_debug(
 659                                                 "ospf_ase_calculate_timer(): looking at area %s",
 660                                                 inet_ntoa(area->area_id));
 661
 662                                 if (area->external_routing == OSPF_AREA_NSSA)
 663                                         LSDB_LOOP(NSSA_LSDB(area), rn, lsa)
 664                                                 ospf_ase_calculate_route(ospf,
 665                                                                          lsa);
 666                         }
 667                 /* kevinm: And add the NSSA routes in ospf_top */
 668                 LSDB_LOOP(NSSA_LSDB(ospf), rn, lsa)
 669                         ospf_ase_calculate_route(ospf, lsa);
 670
 671                 /* Compare old and new external routing table and install the
 672                    difference info zebra/kernel */
 673                 ospf_ase_compare_tables(ospf, ospf->new_external_route,
 674                                         ospf->old_external_route);
 675
 676                 /* Delete old external routing table */
 677                 ospf_route_table_free(ospf->old_external_route);
 678                 ospf->old_external_route = ospf->new_external_route;
 679                 ospf->new_external_route = route_table_init();
 680
 681                 monotime(&stop_time);
 682
 683                 if (IS_DEBUG_OSPF_EVENT)
 684                         zlog_info("SPF Processing Time(usecs): External Routes: %lld\n",
 685                                   (stop_time.tv_sec - start_time.tv_sec) * 1000000LL
 686                                   + (stop_time.tv_usec - start_time.tv_usec));
 687         }
 688         return 0;
 689 }
 690
 691 void ospf_ase_calculate_schedule(struct ospf *ospf)
 692 {
 693         if (ospf == NULL)
 694                 return;
 695
 696         ospf->ase_calc = 1;
 697 }
 698
 699 void ospf_ase_calculate_timer_add(struct ospf *ospf)
 700 {
 701         if (ospf == NULL)
 702                 return;
 703
 704         thread_add_timer(master, ospf_ase_calculate_timer, ospf,
 705                          OSPF_ASE_CALC_INTERVAL, &ospf->t_ase_calc);
 706 }
 707
 708 void ospf_ase_register_external_lsa(struct ospf_lsa *lsa, struct ospf *top)
 709 {
 710         struct route_node *rn;
 711         struct prefix_ipv4 p;
 712         struct list *lst;
 713         struct as_external_lsa *al;
 714
 715         al = (struct as_external_lsa *)lsa->data;
 716         p.family = AF_INET;
 717         p.prefix = lsa->data->id;
 718         p.prefixlen = ip_masklen(al->mask);
 719         apply_mask_ipv4(&p);
 720
 721         rn = route_node_get(top->external_lsas, (struct prefix *)&p);
 722         if ((lst = rn->info) == NULL)
 723                 rn->info = lst = list_new();
 724         else
 725                 route_unlock_node(rn);
 726
 727         /* We assume that if LSA is deleted from DB
 728            is is also deleted from this RT */
 729         listnode_add(lst, ospf_lsa_lock(lsa)); /* external_lsas lst */
 730 }
 731
 732 void ospf_ase_unregister_external_lsa(struct ospf_lsa *lsa, struct ospf *top)
 733 {
 734         struct route_node *rn;
 735         struct prefix_ipv4 p;
 736         struct list *lst;
 737         struct as_external_lsa *al;
 738
 739         al = (struct as_external_lsa *)lsa->data;
 740         p.family = AF_INET;
 741         p.prefix = lsa->data->id;
 742         p.prefixlen = ip_masklen(al->mask);
 743         apply_mask_ipv4(&p);
 744
 745         rn = route_node_lookup(top->external_lsas, (struct prefix *)&p);
 746
 747         if (rn) {
 748                 lst = rn->info;
 749                 listnode_delete(lst, lsa);
 750                 ospf_lsa_unlock(&lsa); /* external_lsas list */
 751                 route_unlock_node(rn);
 752         }
 753 }
 754
 755 void ospf_ase_external_lsas_finish(struct route_table *rt)
 756 {
 757         struct route_node *rn;
 758         struct ospf_lsa *lsa;
 759         struct list *lst;
 760         struct listnode *node, *nnode;
 761
 762         for (rn = route_top(rt); rn; rn = route_next(rn))
 763                 if ((lst = rn->info) != NULL) {
 764                         for (ALL_LIST_ELEMENTS(lst, node, nnode, lsa))
 765                                 ospf_lsa_unlock(&lsa); /* external_lsas lst */
 766                         list_delete_and_null(&lst);
 767                 }
 768
 769         route_table_finish(rt);
 770 }
 771
 772 void ospf_ase_incremental_update(struct ospf *ospf, struct ospf_lsa *lsa)
 773 {
 774         struct list *lsas;
 775         struct listnode *node;
 776         struct route_node *rn, *rn2;
 777         struct prefix_ipv4 p;
 778         struct route_table *tmp_old;
 779         struct as_external_lsa *al;
 780
 781         al = (struct as_external_lsa *)lsa->data;
 782         p.family = AF_INET;
 783         p.prefix = lsa->data->id;
 784         p.prefixlen = ip_masklen(al->mask);
 785         apply_mask_ipv4(&p);
 786
 787         /* if new_table is NULL, there was no spf calculation, thus
 788            incremental update is unneeded */
 789         if (!ospf->new_table)
 790                 return;
 791
 792         /* If there is already an intra-area or inter-area route
 793            to the destination, no recalculation is necessary
 794            (internal routes take precedence). */
 795
 796         rn = route_node_lookup(ospf->new_table, (struct prefix *)&p);
 797         if (rn) {
 798                 route_unlock_node(rn);
 799                 if (rn->info)
 800                         return;
 801         }
 802
 803         rn = route_node_lookup(ospf->external_lsas, (struct prefix *)&p);
 804         assert(rn);
 805         assert(rn->info);
 806         lsas = rn->info;
 807         route_unlock_node(rn);
 808
 809         for (ALL_LIST_ELEMENTS_RO(lsas, node, lsa))
 810                 ospf_ase_calculate_route(ospf, lsa);
 811
 812         /* prepare temporary old routing table for compare */
 813         tmp_old = route_table_init();
 814         rn = route_node_lookup(ospf->old_external_route, (struct prefix *)&p);
 815         if (rn && rn->info) {
 816                 rn2 = route_node_get(tmp_old, (struct prefix *)&p);
 817                 rn2->info = rn->info;
 818                 route_unlock_node(rn);
 819         }
 820
 821         /* install changes to zebra */
 822         ospf_ase_compare_tables(ospf, ospf->new_external_route, tmp_old);
 823
 824         /* update ospf->old_external_route table */
 825         if (rn && rn->info)
 826                 ospf_route_free((struct ospf_route *)rn->info);
 827
 828         rn2 = route_node_lookup(ospf->new_external_route, (struct prefix *)&p);
 829         /* if new route exists, install it to ospf->old_external_route */
 830         if (rn2 && rn2->info) {
 831                 if (!rn)
 832                         rn = route_node_get(ospf->old_external_route,
 833                                             (struct prefix *)&p);
 834                 rn->info = rn2->info;
 835         } else {
 836                 /* remove route node from ospf->old_external_route */
 837                 if (rn) {
 838                         rn->info = NULL;
 839                         route_unlock_node(rn);
 840                 }
 841         }
 842
 843         if (rn2) {
 844                 /* rn2->info is stored in route node of ospf->old_external_route
 845                  */
 846                 rn2->info = NULL;
 847                 route_unlock_node(rn2);
 848                 route_unlock_node(rn2);
 849         }
 850
 851         route_table_finish(tmp_old);
 852 }