Import Upstream version 1.2.2
[quagga-debian.git] / isisd / isis_route.c
1 /*
2  * IS-IS Rout(e)ing protocol               - isis_route.c
3  * Copyright (C) 2001,2002   Sampo Saaristo
4  *                           Tampere University of Technology      
5  *                           Institute of Communications Engineering
6  *
7  *                                         based on ../ospf6d/ospf6_route.[ch]
8  *                                         by Yasuhiro Ohara
9  *
10  * This program is free software; you can redistribute it and/or modify it 
11  * under the terms of the GNU General Public Licenseas published by the Free 
12  * Software Foundation; either version 2 of the License, or (at your option) 
13  * any later version.
14  *
15  * This program is distributed in the hope that it will be useful,but WITHOUT 
16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
17  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
18  * more details.
19
20  * You should have received a copy of the GNU General Public License along 
21  * with this program; if not, write to the Free Software Foundation, Inc., 
22  * 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
23  */
24
25 #include <zebra.h>
26
27 #include "thread.h"
28 #include "linklist.h"
29 #include "vty.h"
30 #include "log.h"
31 #include "memory.h"
32 #include "prefix.h"
33 #include "hash.h"
34 #include "if.h"
35 #include "table.h"
36
37 #include "isis_constants.h"
38 #include "isis_common.h"
39 #include "isis_flags.h"
40 #include "dict.h"
41 #include "isisd.h"
42 #include "isis_misc.h"
43 #include "isis_adjacency.h"
44 #include "isis_circuit.h"
45 #include "isis_tlv.h"
46 #include "isis_pdu.h"
47 #include "isis_lsp.h"
48 #include "isis_spf.h"
49 #include "isis_route.h"
50 #include "isis_zebra.h"
51
52 static struct isis_nexthop *
53 isis_nexthop_create (struct in_addr *ip, ifindex_t ifindex)
54 {
55   struct listnode *node;
56   struct isis_nexthop *nexthop;
57
58   for (ALL_LIST_ELEMENTS_RO (isis->nexthops, node, nexthop))
59     {
60       if (nexthop->ifindex != ifindex)
61         continue;
62       if (ip && memcmp (&nexthop->ip, ip, sizeof (struct in_addr)) != 0)
63         continue;
64
65       nexthop->lock++;
66       return nexthop;
67     }
68
69   nexthop = XCALLOC (MTYPE_ISIS_NEXTHOP, sizeof (struct isis_nexthop));
70
71   nexthop->ifindex = ifindex;
72   memcpy (&nexthop->ip, ip, sizeof (struct in_addr));
73   listnode_add (isis->nexthops, nexthop);
74   nexthop->lock++;
75
76   return nexthop;
77 }
78
79 static void
80 isis_nexthop_delete (struct isis_nexthop *nexthop)
81 {
82   nexthop->lock--;
83   if (nexthop->lock == 0)
84     {
85       listnode_delete (isis->nexthops, nexthop);
86       XFREE (MTYPE_ISIS_NEXTHOP, nexthop);
87     }
88
89   return;
90 }
91
92 static int
93 nexthoplookup (struct list *nexthops, struct in_addr *ip,
94                ifindex_t ifindex)
95 {
96   struct listnode *node;
97   struct isis_nexthop *nh;
98
99   for (ALL_LIST_ELEMENTS_RO (nexthops, node, nh))
100     {
101       if (!(memcmp (ip, &nh->ip, sizeof (struct in_addr))) &&
102           ifindex == nh->ifindex)
103         return 1;
104     }
105
106   return 0;
107 }
108
109 #ifdef EXTREME_DEBUG
110 static void
111 nexthop_print (struct isis_nexthop *nh)
112 {
113   u_char buf[BUFSIZ];
114
115   inet_ntop (AF_INET, &nh->ip, (char *) buf, BUFSIZ);
116
117   zlog_debug ("      %s %u", buf, nh->ifindex);
118 }
119
120 static void
121 nexthops_print (struct list *nhs)
122 {
123   struct listnode *node;
124   struct isis_nexthop *nh;
125
126   for (ALL_LIST_ELEMENTS_RO (nhs, node, nh))
127     nexthop_print (nh);
128 }
129 #endif /* EXTREME_DEBUG */
130
131 #ifdef HAVE_IPV6
132 static struct isis_nexthop6 *
133 isis_nexthop6_new (struct in6_addr *ip6, ifindex_t ifindex)
134 {
135   struct isis_nexthop6 *nexthop6;
136
137   nexthop6 = XCALLOC (MTYPE_ISIS_NEXTHOP6, sizeof (struct isis_nexthop6));
138
139   nexthop6->ifindex = ifindex;
140   memcpy (&nexthop6->ip6, ip6, sizeof (struct in6_addr));
141   nexthop6->lock++;
142
143   return nexthop6;
144 }
145
146 static struct isis_nexthop6 *
147 isis_nexthop6_create (struct in6_addr *ip6, ifindex_t ifindex)
148 {
149   struct listnode *node;
150   struct isis_nexthop6 *nexthop6;
151
152   for (ALL_LIST_ELEMENTS_RO (isis->nexthops6, node, nexthop6))
153     {
154       if (nexthop6->ifindex != ifindex)
155         continue;
156       if (ip6 && memcmp (&nexthop6->ip6, ip6, sizeof (struct in6_addr)) != 0)
157         continue;
158
159       nexthop6->lock++;
160       return nexthop6;
161     }
162
163   nexthop6 = isis_nexthop6_new (ip6, ifindex);
164
165   return nexthop6;
166 }
167
168 static void
169 isis_nexthop6_delete (struct isis_nexthop6 *nexthop6)
170 {
171
172   nexthop6->lock--;
173   if (nexthop6->lock == 0)
174     {
175       listnode_delete (isis->nexthops6, nexthop6);
176       XFREE (MTYPE_ISIS_NEXTHOP6, nexthop6);
177     }
178
179   return;
180 }
181
182 static int
183 nexthop6lookup (struct list *nexthops6, struct in6_addr *ip6,
184                 ifindex_t ifindex)
185 {
186   struct listnode *node;
187   struct isis_nexthop6 *nh6;
188
189   for (ALL_LIST_ELEMENTS_RO (nexthops6, node, nh6))
190     {
191       if (!(memcmp (ip6, &nh6->ip6, sizeof (struct in6_addr))) &&
192           ifindex == nh6->ifindex)
193         return 1;
194     }
195
196   return 0;
197 }
198
199 #ifdef EXTREME_DEBUG
200 static void
201 nexthop6_print (struct isis_nexthop6 *nh6)
202 {
203   u_char buf[BUFSIZ];
204
205   inet_ntop (AF_INET6, &nh6->ip6, (char *) buf, BUFSIZ);
206
207   zlog_debug ("      %s %u", buf, nh6->ifindex);
208 }
209
210 static void
211 nexthops6_print (struct list *nhs6)
212 {
213   struct listnode *node;
214   struct isis_nexthop6 *nh6;
215
216   for (ALL_LIST_ELEMENTS_RO (nhs6, node, nh6))
217     nexthop6_print (nh6);
218 }
219 #endif /* EXTREME_DEBUG */
220 #endif /* HAVE_IPV6 */
221
222 static void
223 adjinfo2nexthop (struct list *nexthops, struct isis_adjacency *adj)
224 {
225   struct isis_nexthop *nh;
226   struct listnode *node;
227   struct in_addr *ipv4_addr;
228
229   if (adj->ipv4_addrs == NULL)
230     return;
231
232   for (ALL_LIST_ELEMENTS_RO (adj->ipv4_addrs, node, ipv4_addr))
233     {
234       if (!nexthoplookup (nexthops, ipv4_addr,
235                           adj->circuit->interface->ifindex))
236         {
237           nh = isis_nexthop_create (ipv4_addr,
238                                     adj->circuit->interface->ifindex);
239           nh->router_address = adj->router_address;
240           listnode_add (nexthops, nh);
241         }
242     }
243 }
244
245 #ifdef HAVE_IPV6
246 static void
247 adjinfo2nexthop6 (struct list *nexthops6, struct isis_adjacency *adj)
248 {
249   struct listnode *node;
250   struct in6_addr *ipv6_addr;
251   struct isis_nexthop6 *nh6;
252
253   if (!adj->ipv6_addrs)
254     return;
255
256   for (ALL_LIST_ELEMENTS_RO (adj->ipv6_addrs, node, ipv6_addr))
257     {
258       if (!nexthop6lookup (nexthops6, ipv6_addr,
259                            adj->circuit->interface->ifindex))
260         {
261           nh6 = isis_nexthop6_create (ipv6_addr,
262                                       adj->circuit->interface->ifindex);
263           nh6->router_address6 = adj->router_address6;
264           listnode_add (nexthops6, nh6);
265         }
266     }
267 }
268 #endif /* HAVE_IPV6 */
269
270 static struct isis_route_info *
271 isis_route_info_new (struct prefix *prefix, uint32_t cost, uint32_t depth,
272                      struct list *adjacencies)
273 {
274   struct isis_route_info *rinfo;
275   struct isis_adjacency *adj;
276   struct listnode *node;
277
278   rinfo = XCALLOC (MTYPE_ISIS_ROUTE_INFO, sizeof (struct isis_route_info));
279
280   if (prefix->family == AF_INET)
281     {
282       rinfo->nexthops = list_new ();
283       for (ALL_LIST_ELEMENTS_RO (adjacencies, node, adj))
284         {
285           /* check for force resync this route */
286           if (CHECK_FLAG (adj->circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
287             SET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
288           /* update neighbor router address */
289           if (depth == 2 && prefix->prefixlen == 32)
290             adj->router_address = prefix->u.prefix4;
291           adjinfo2nexthop (rinfo->nexthops, adj);
292         }
293     }
294 #ifdef HAVE_IPV6
295   if (prefix->family == AF_INET6)
296     {
297       rinfo->nexthops6 = list_new ();
298       for (ALL_LIST_ELEMENTS_RO (adjacencies, node, adj))
299         {
300           /* check for force resync this route */
301           if (CHECK_FLAG (adj->circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
302             SET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
303           /* update neighbor router address */
304           if (depth == 2 && prefix->prefixlen == 128)
305             adj->router_address6 = prefix->u.prefix6;
306           adjinfo2nexthop6 (rinfo->nexthops6, adj);
307         }
308     }
309
310 #endif /* HAVE_IPV6 */
311
312   rinfo->cost = cost;
313   rinfo->depth = depth;
314
315   return rinfo;
316 }
317
318 static void
319 isis_route_info_delete (struct isis_route_info *route_info)
320 {
321   if (route_info->nexthops)
322     {
323       route_info->nexthops->del = (void (*)(void *)) isis_nexthop_delete;
324       list_delete (route_info->nexthops);
325     }
326
327 #ifdef HAVE_IPV6
328   if (route_info->nexthops6)
329     {
330       route_info->nexthops6->del = (void (*)(void *)) isis_nexthop6_delete;
331       list_delete (route_info->nexthops6);
332     }
333 #endif /* HAVE_IPV6 */
334
335   XFREE (MTYPE_ISIS_ROUTE_INFO, route_info);
336 }
337
338 static int
339 isis_route_info_same_attrib (struct isis_route_info *new,
340                              struct isis_route_info *old)
341 {
342   if (new->cost != old->cost)
343     return 0;
344   if (new->depth != old->depth)
345     return 0;
346
347   return 1;
348 }
349
350 static int
351 isis_route_info_same (struct isis_route_info *new,
352                       struct isis_route_info *old, u_char family)
353 {
354   struct listnode *node;
355   struct isis_nexthop *nexthop;
356 #ifdef HAVE_IPV6
357   struct isis_nexthop6 *nexthop6;
358 #endif /* HAVE_IPV6 */
359
360   if (!CHECK_FLAG (old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
361     return 0;
362
363   if (CHECK_FLAG (new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
364     return 0;
365
366   if (!isis_route_info_same_attrib (new, old))
367     return 0;
368
369   if (family == AF_INET)
370     {
371       for (ALL_LIST_ELEMENTS_RO (new->nexthops, node, nexthop))
372         if (nexthoplookup (old->nexthops, &nexthop->ip, nexthop->ifindex)
373               == 0)
374           return 0;
375
376       for (ALL_LIST_ELEMENTS_RO (old->nexthops, node, nexthop))
377         if (nexthoplookup (new->nexthops, &nexthop->ip, nexthop->ifindex)
378              == 0)
379           return 0;
380     }
381 #ifdef HAVE_IPV6
382   else if (family == AF_INET6)
383     {
384       for (ALL_LIST_ELEMENTS_RO (new->nexthops6, node, nexthop6))
385         if (nexthop6lookup (old->nexthops6, &nexthop6->ip6,
386                             nexthop6->ifindex) == 0)
387           return 0;
388
389       for (ALL_LIST_ELEMENTS_RO (old->nexthops6, node, nexthop6))
390         if (nexthop6lookup (new->nexthops6, &nexthop6->ip6,
391                             nexthop6->ifindex) == 0)
392           return 0;
393     }
394 #endif /* HAVE_IPV6 */
395
396   return 1;
397 }
398
399 struct isis_route_info *
400 isis_route_create (struct prefix *prefix, u_int32_t cost, u_int32_t depth,
401                    struct list *adjacencies, struct isis_area *area,
402                    int level)
403 {
404   struct route_node *route_node;
405   struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
406   u_char buff[BUFSIZ];
407   u_char family;
408
409   family = prefix->family;
410   /* for debugs */
411   prefix2str (prefix, (char *) buff, BUFSIZ);
412
413   rinfo_new = isis_route_info_new (prefix, cost, depth, adjacencies);
414
415   if (family == AF_INET)
416     route_node = route_node_get (area->route_table[level - 1], prefix);
417 #ifdef HAVE_IPV6
418   else if (family == AF_INET6)
419     route_node = route_node_get (area->route_table6[level - 1], prefix);
420 #endif /* HAVE_IPV6 */
421   else
422     {
423       isis_route_info_delete (rinfo_new);
424       return NULL;
425     }
426
427   rinfo_old = route_node->info;
428   if (!rinfo_old)
429     {
430       if (isis->debugs & DEBUG_RTE_EVENTS)
431         zlog_debug ("ISIS-Rte (%s) route created: %s", area->area_tag, buff);
432       route_info = rinfo_new;
433       UNSET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
434     }
435   else
436     {
437       if (isis->debugs & DEBUG_RTE_EVENTS)
438         zlog_debug ("ISIS-Rte (%s) route already exists: %s", area->area_tag,
439                    buff);
440       if (isis_route_info_same (rinfo_new, rinfo_old, family))
441         {
442           if (isis->debugs & DEBUG_RTE_EVENTS)
443             zlog_debug ("ISIS-Rte (%s) route unchanged: %s", area->area_tag,
444                         buff);
445           isis_route_info_delete (rinfo_new);
446           route_info = rinfo_old;
447         }
448       else
449         {
450           if (isis->debugs & DEBUG_RTE_EVENTS)
451             zlog_debug ("ISIS-Rte (%s) route changed: %s", area->area_tag,
452                         buff);
453           isis_route_info_delete (rinfo_old);
454           route_info = rinfo_new;
455           UNSET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
456         }
457     }
458
459   SET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
460   route_node->info = route_info;
461
462   return route_info;
463 }
464
465 static void
466 isis_route_delete (struct prefix *prefix, struct route_table *table)
467 {
468   struct route_node *rode;
469   struct isis_route_info *rinfo;
470   char buff[BUFSIZ];
471
472   /* for log */
473   prefix2str (prefix, buff, BUFSIZ);
474
475
476   rode = route_node_get (table, prefix);
477   rinfo = rode->info;
478
479   if (rinfo == NULL)
480     {
481       if (isis->debugs & DEBUG_RTE_EVENTS)
482         zlog_debug ("ISIS-Rte: tried to delete non-existant route %s", buff);
483       return;
484     }
485
486   if (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
487     {
488       UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
489       if (isis->debugs & DEBUG_RTE_EVENTS)
490         zlog_debug ("ISIS-Rte: route delete  %s", buff);
491       isis_zebra_route_update (prefix, rinfo);
492     }
493   isis_route_info_delete (rinfo);
494   rode->info = NULL;
495
496   return;
497 }
498
499 /* Validating routes in particular table. */
500 static void
501 isis_route_validate_table (struct isis_area *area, struct route_table *table)
502 {
503   struct route_node *rnode, *drnode;
504   struct isis_route_info *rinfo;
505   u_char buff[BUFSIZ];
506
507   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
508     {
509       if (rnode->info == NULL)
510         continue;
511       rinfo = rnode->info;
512
513       if (isis->debugs & DEBUG_RTE_EVENTS)
514         {
515           prefix2str (&rnode->p, (char *) buff, BUFSIZ);
516           zlog_debug ("ISIS-Rte (%s): route validate: %s %s %s %s",
517                       area->area_tag,
518                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED) ?
519                       "synced" : "not-synced"),
520                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC) ?
521                       "resync" : "not-resync"),
522                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE) ?
523                       "active" : "inactive"), buff);
524         }
525
526       isis_zebra_route_update (&rnode->p, rinfo);
527       if (!CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
528         {
529           /* Area is either L1 or L2 => we use level route tables directly for
530            * validating => no problems with deleting routes. */
531           if (area->is_type != IS_LEVEL_1_AND_2)
532             {
533               isis_route_delete (&rnode->p, table);
534               continue;
535             }
536           /* If area is L1L2, we work with merge table and therefore must
537            * delete node from level tables as well before deleting route info.
538            * FIXME: Is it performance problem? There has to be the better way.
539            * Like not to deal with it here at all (see the next comment)? */
540           if (rnode->p.family == AF_INET)
541             {
542               drnode = route_node_get (area->route_table[0], &rnode->p);
543               if (drnode->info == rnode->info)
544                 drnode->info = NULL;
545               drnode = route_node_get (area->route_table[1], &rnode->p);
546               if (drnode->info == rnode->info)
547                 drnode->info = NULL;
548             }
549
550 #ifdef HAVE_IPV6
551           if (rnode->p.family == AF_INET6)
552             {
553               drnode = route_node_get (area->route_table6[0], &rnode->p);
554               if (drnode->info == rnode->info)
555                 drnode->info = NULL;
556               drnode = route_node_get (area->route_table6[1], &rnode->p);
557               if (drnode->info == rnode->info)
558                 drnode->info = NULL;
559             }
560 #endif
561               
562           isis_route_delete (&rnode->p, table);
563         }
564     }
565 }
566
567 /* Function to validate route tables for L1L2 areas. In this case we can't use
568  * level route tables directly, we have to merge them at first. L1 routes are
569  * preferred over the L2 ones.
570  *
571  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
572  * merge table at first, then L2 paths are added if L1 path for same prefix
573  * doesn't already exists there.
574  *
575  * FIXME: Is it right place to do it at all? Maybe we should push both levels
576  * to the RIB with different zebra route types and let RIB handle this? */
577 static void
578 isis_route_validate_merge (struct isis_area *area, int family)
579 {
580   struct route_table *table = NULL;
581   struct route_table *merge;
582   struct route_node *rnode, *mrnode;
583
584   merge = route_table_init ();
585
586   if (family == AF_INET)
587     table = area->route_table[0];
588 #ifdef HAVE_IPV6
589   else if (family == AF_INET6)
590     table = area->route_table6[0];
591 #endif
592
593   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
594     {
595       if (rnode->info == NULL)
596         continue;
597       mrnode = route_node_get (merge, &rnode->p);
598       mrnode->info = rnode->info;
599     }
600
601   if (family == AF_INET)
602     table = area->route_table[1];
603 #ifdef HAVE_IPV6
604   else if (family == AF_INET6)
605     table = area->route_table6[1];
606 #endif
607
608   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
609     {
610       if (rnode->info == NULL)
611         continue;
612       mrnode = route_node_get (merge, &rnode->p);
613       if (mrnode->info != NULL)
614         continue;
615       mrnode->info = rnode->info;
616     }
617
618   isis_route_validate_table (area, merge);
619   route_table_finish (merge);
620 }
621
622 /* Walk through route tables and propagate necessary changes into RIB. In case
623  * of L1L2 area, level tables have to be merged at first. */
624 void
625 isis_route_validate (struct isis_area *area)
626 {
627   struct listnode *node;
628   struct isis_circuit *circuit;
629
630   if (area->is_type == IS_LEVEL_1)
631     isis_route_validate_table (area, area->route_table[0]);
632   else if (area->is_type == IS_LEVEL_2)
633     isis_route_validate_table (area, area->route_table[1]);
634   else
635     isis_route_validate_merge (area, AF_INET);
636
637 #ifdef HAVE_IPV6
638   if (area->is_type == IS_LEVEL_1)
639     isis_route_validate_table (area, area->route_table6[0]);
640   else if (area->is_type == IS_LEVEL_2)
641     isis_route_validate_table (area, area->route_table6[1]);
642   else
643     isis_route_validate_merge (area, AF_INET6);
644 #endif
645
646   if (!area->circuit_list) {
647     return;
648   }
649   /* walk all circuits and reset any spf specific flags */
650   for (ALL_LIST_ELEMENTS_RO (area->circuit_list, node, circuit))
651     UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
652
653   return;
654 }
655
656 void
657 isis_route_invalidate_table (struct isis_area *area, struct route_table *table)
658 {
659   struct route_node *rode;
660   struct isis_route_info *rinfo;
661   for (rode = route_top (table); rode; rode = route_next (rode))
662     {
663       if (rode->info == NULL)
664         continue;
665       rinfo = rode->info;
666
667       UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
668     }
669 }
670
671 void
672 isis_route_invalidate (struct isis_area *area)
673 {
674   if (area->is_type & IS_LEVEL_1)
675     isis_route_invalidate_table (area, area->route_table[0]);
676   if (area->is_type & IS_LEVEL_2)
677     isis_route_invalidate_table (area, area->route_table[1]);
678 }