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