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