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
7 * based on ../ospf6d/ospf6_route.[ch]
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)
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
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
37 #include "isis_constants.h"
38 #include "isis_common.h"
39 #include "isis_flags.h"
42 #include "isis_misc.h"
43 #include "isis_adjacency.h"
44 #include "isis_circuit.h"
49 #include "isis_route.h"
50 #include "isis_zebra.h"
52 static struct isis_nexthop
*isis_nexthop_create(struct in_addr
*ip
,
55 struct listnode
*node
;
56 struct isis_nexthop
*nexthop
;
58 for (ALL_LIST_ELEMENTS_RO(isis
->nexthops
, node
, nexthop
)) {
59 if (nexthop
->ifindex
!= ifindex
)
61 if (ip
&& memcmp(&nexthop
->ip
, ip
, sizeof(struct in_addr
)) != 0)
68 nexthop
= XCALLOC(MTYPE_ISIS_NEXTHOP
, sizeof(struct isis_nexthop
));
70 nexthop
->ifindex
= ifindex
;
71 memcpy(&nexthop
->ip
, ip
, sizeof(struct in_addr
));
72 listnode_add(isis
->nexthops
, nexthop
);
78 static void isis_nexthop_delete(struct isis_nexthop
*nexthop
)
81 if (nexthop
->lock
== 0) {
82 listnode_delete(isis
->nexthops
, nexthop
);
83 XFREE(MTYPE_ISIS_NEXTHOP
, nexthop
);
89 static int nexthoplookup(struct list
*nexthops
, struct in_addr
*ip
,
92 struct listnode
*node
;
93 struct isis_nexthop
*nh
;
95 for (ALL_LIST_ELEMENTS_RO(nexthops
, node
, nh
)) {
96 if (!(memcmp(ip
, &nh
->ip
, sizeof(struct in_addr
)))
97 && ifindex
== nh
->ifindex
)
105 static void nexthop_print(struct isis_nexthop
*nh
)
109 inet_ntop(AF_INET
, &nh
->ip
, (char *)buf
, BUFSIZ
);
111 zlog_debug(" %s %u", buf
, nh
->ifindex
);
114 static void nexthops_print(struct list
*nhs
)
116 struct listnode
*node
;
117 struct isis_nexthop
*nh
;
119 for (ALL_LIST_ELEMENTS_RO(nhs
, node
, nh
))
122 #endif /* EXTREME_DEBUG */
124 static struct isis_nexthop6
*isis_nexthop6_new(struct in6_addr
*ip6
,
127 struct isis_nexthop6
*nexthop6
;
129 nexthop6
= XCALLOC(MTYPE_ISIS_NEXTHOP6
, sizeof(struct isis_nexthop6
));
131 nexthop6
->ifindex
= ifindex
;
132 memcpy(&nexthop6
->ip6
, ip6
, sizeof(struct in6_addr
));
138 static struct isis_nexthop6
*isis_nexthop6_create(struct in6_addr
*ip6
,
141 struct listnode
*node
;
142 struct isis_nexthop6
*nexthop6
;
144 for (ALL_LIST_ELEMENTS_RO(isis
->nexthops6
, node
, nexthop6
)) {
145 if (nexthop6
->ifindex
!= ifindex
)
148 && memcmp(&nexthop6
->ip6
, ip6
, sizeof(struct in6_addr
))
156 nexthop6
= isis_nexthop6_new(ip6
, ifindex
);
161 static void isis_nexthop6_delete(struct isis_nexthop6
*nexthop6
)
165 if (nexthop6
->lock
== 0) {
166 listnode_delete(isis
->nexthops6
, nexthop6
);
167 XFREE(MTYPE_ISIS_NEXTHOP6
, nexthop6
);
173 static int nexthop6lookup(struct list
*nexthops6
, struct in6_addr
*ip6
,
176 struct listnode
*node
;
177 struct isis_nexthop6
*nh6
;
179 for (ALL_LIST_ELEMENTS_RO(nexthops6
, node
, nh6
)) {
180 if (!(memcmp(ip6
, &nh6
->ip6
, sizeof(struct in6_addr
)))
181 && ifindex
== nh6
->ifindex
)
189 static void nexthop6_print(struct isis_nexthop6
*nh6
)
193 inet_ntop(AF_INET6
, &nh6
->ip6
, (char *)buf
, BUFSIZ
);
195 zlog_debug(" %s %u", buf
, nh6
->ifindex
);
198 static void nexthops6_print(struct list
*nhs6
)
200 struct listnode
*node
;
201 struct isis_nexthop6
*nh6
;
203 for (ALL_LIST_ELEMENTS_RO(nhs6
, node
, nh6
))
206 #endif /* EXTREME_DEBUG */
208 static void adjinfo2nexthop(struct list
*nexthops
, struct isis_adjacency
*adj
)
210 struct isis_nexthop
*nh
;
211 struct listnode
*node
;
212 struct in_addr
*ipv4_addr
;
214 if (adj
->ipv4_addrs
== NULL
)
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
);
228 static void adjinfo2nexthop6(struct list
*nexthops6
, struct isis_adjacency
*adj
)
230 struct listnode
*node
;
231 struct in6_addr
*ipv6_addr
;
232 struct isis_nexthop6
*nh6
;
234 if (!adj
->ipv6_addrs
)
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
);
248 static struct isis_route_info
*isis_route_info_new(struct prefix
*prefix
,
251 struct list
*adjacencies
)
253 struct isis_route_info
*rinfo
;
254 struct isis_adjacency
*adj
;
255 struct listnode
*node
;
257 rinfo
= XCALLOC(MTYPE_ISIS_ROUTE_INFO
, sizeof(struct isis_route_info
));
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
);
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
);
289 rinfo
->depth
= depth
;
294 static void isis_route_info_delete(struct isis_route_info
*route_info
)
296 if (route_info
->nexthops
) {
297 route_info
->nexthops
->del
=
298 (void (*)(void *))isis_nexthop_delete
;
299 list_delete(route_info
->nexthops
);
302 if (route_info
->nexthops6
) {
303 route_info
->nexthops6
->del
=
304 (void (*)(void *))isis_nexthop6_delete
;
305 list_delete(route_info
->nexthops6
);
308 XFREE(MTYPE_ISIS_ROUTE_INFO
, route_info
);
311 static int isis_route_info_same_attrib(struct isis_route_info
*new,
312 struct isis_route_info
*old
)
314 if (new->cost
!= old
->cost
)
316 if (new->depth
!= old
->depth
)
322 static int isis_route_info_same(struct isis_route_info
*new,
323 struct isis_route_info
*old
, u_char family
)
325 struct listnode
*node
;
326 struct isis_nexthop
*nexthop
;
327 struct isis_nexthop6
*nexthop6
;
329 if (!CHECK_FLAG(old
->flag
, ISIS_ROUTE_FLAG_ZEBRA_SYNCED
))
332 if (CHECK_FLAG(new->flag
, ISIS_ROUTE_FLAG_ZEBRA_RESYNC
))
335 if (!isis_route_info_same_attrib(new, old
))
338 if (family
== AF_INET
) {
339 for (ALL_LIST_ELEMENTS_RO(new->nexthops
, node
, nexthop
))
340 if (nexthoplookup(old
->nexthops
, &nexthop
->ip
,
345 for (ALL_LIST_ELEMENTS_RO(old
->nexthops
, node
, nexthop
))
346 if (nexthoplookup(new->nexthops
, &nexthop
->ip
,
350 } else if (family
== AF_INET6
) {
351 for (ALL_LIST_ELEMENTS_RO(new->nexthops6
, node
, nexthop6
))
352 if (nexthop6lookup(old
->nexthops6
, &nexthop6
->ip6
,
357 for (ALL_LIST_ELEMENTS_RO(old
->nexthops6
, node
, nexthop6
))
358 if (nexthop6lookup(new->nexthops6
, &nexthop6
->ip6
,
367 struct isis_route_info
*isis_route_create(struct prefix
*prefix
, u_int32_t cost
,
369 struct list
*adjacencies
,
370 struct isis_area
*area
, int level
)
372 struct route_node
*route_node
;
373 struct isis_route_info
*rinfo_new
, *rinfo_old
, *route_info
= NULL
;
374 char buff
[PREFIX2STR_BUFFER
];
377 family
= prefix
->family
;
379 prefix2str(prefix
, buff
, sizeof(buff
));
381 rinfo_new
= isis_route_info_new(prefix
, cost
, depth
, adjacencies
);
383 if (family
== AF_INET
)
385 route_node_get(area
->route_table
[level
- 1], prefix
);
386 else if (family
== AF_INET6
)
388 route_node_get(area
->route_table6
[level
- 1], prefix
);
390 isis_route_info_delete(rinfo_new
);
394 rinfo_old
= route_node
->info
;
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
);
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
;
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
);
422 SET_FLAG(route_info
->flag
, ISIS_ROUTE_FLAG_ACTIVE
);
423 route_node
->info
= route_info
;
428 static void isis_route_delete(struct prefix
*prefix
, struct route_table
*table
)
430 struct route_node
*rode
;
431 struct isis_route_info
*rinfo
;
432 char buff
[PREFIX2STR_BUFFER
];
435 prefix2str(prefix
, buff
, sizeof(buff
));
438 rode
= route_node_get(table
, prefix
);
442 if (isis
->debugs
& DEBUG_RTE_EVENTS
)
444 "ISIS-Rte: tried to delete non-existant route %s",
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
);
455 isis_route_info_delete(rinfo
);
461 /* Validating routes in particular table. */
462 static void isis_route_validate_table(struct isis_area
*area
,
463 struct route_table
*table
)
465 struct route_node
*rnode
, *drnode
;
466 struct isis_route_info
*rinfo
;
467 char buff
[PREFIX2STR_BUFFER
];
469 for (rnode
= route_top(table
); rnode
; rnode
= route_next(rnode
)) {
470 if (rnode
->info
== NULL
)
474 if (isis
->debugs
& DEBUG_RTE_EVENTS
) {
475 prefix2str(&rnode
->p
, buff
, sizeof(buff
));
477 "ISIS-Rte (%s): route validate: %s %s %s %s",
479 (CHECK_FLAG(rinfo
->flag
,
480 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
)
483 (CHECK_FLAG(rinfo
->flag
,
484 ISIS_ROUTE_FLAG_ZEBRA_RESYNC
)
487 (CHECK_FLAG(rinfo
->flag
, ISIS_ROUTE_FLAG_ACTIVE
)
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
497 * validating => no problems with deleting routes. */
498 if (area
->is_type
!= IS_LEVEL_1_AND_2
) {
499 isis_route_delete(&rnode
->p
, table
);
502 /* If area is L1L2, we work with merge table and
504 * delete node from level tables as well before deleting
506 * FIXME: Is it performance problem? There has to be the
508 * Like not to deal with it here at all (see the next
510 if (rnode
->p
.family
== AF_INET
) {
511 drnode
= route_node_get(area
->route_table
[0],
513 if (drnode
->info
== rnode
->info
)
515 drnode
= route_node_get(area
->route_table
[1],
517 if (drnode
->info
== rnode
->info
)
521 if (rnode
->p
.family
== AF_INET6
) {
522 drnode
= route_node_get(area
->route_table6
[0],
524 if (drnode
->info
== rnode
->info
)
526 drnode
= route_node_get(area
->route_table6
[1],
528 if (drnode
->info
== rnode
->info
)
532 isis_route_delete(&rnode
->p
, table
);
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.
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.
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
)
549 struct route_table
*table
= NULL
;
550 struct route_table
*merge
;
551 struct route_node
*rnode
, *mrnode
;
553 merge
= route_table_init();
555 if (family
== AF_INET
)
556 table
= area
->route_table
[0];
557 else if (family
== AF_INET6
)
558 table
= area
->route_table6
[0];
560 zlog_warn("ISIS-Rte (%s) %s called for unknown family %d",
561 area
->area_tag
, __func__
, family
);
562 route_table_finish(merge
);
566 for (rnode
= route_top(table
); rnode
; rnode
= route_next(rnode
)) {
567 if (rnode
->info
== NULL
)
569 mrnode
= route_node_get(merge
, &rnode
->p
);
570 mrnode
->info
= rnode
->info
;
573 if (family
== AF_INET
)
574 table
= area
->route_table
[1];
575 else if (family
== AF_INET6
)
576 table
= area
->route_table6
[1];
578 for (rnode
= route_top(table
); rnode
; rnode
= route_next(rnode
)) {
579 if (rnode
->info
== NULL
)
581 mrnode
= route_node_get(merge
, &rnode
->p
);
582 if (mrnode
->info
!= NULL
)
584 mrnode
->info
= rnode
->info
;
587 isis_route_validate_table(area
, merge
);
588 route_table_finish(merge
);
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
)
595 struct listnode
*node
;
596 struct isis_circuit
*circuit
;
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]);
603 isis_route_validate_merge(area
, AF_INET
);
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]);
610 isis_route_validate_merge(area
, AF_INET6
);
612 if (!area
->circuit_list
) {
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
);
622 void isis_route_invalidate_table(struct isis_area
*area
,
623 struct route_table
*table
)
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
)
632 UNSET_FLAG(rinfo
->flag
, ISIS_ROUTE_FLAG_ACTIVE
);
636 void isis_route_invalidate(struct isis_area
*area
)
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]);