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