2 * Copyright (C) 2003 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
31 #include "ospf6_proto.h"
32 #include "ospf6_lsa.h"
33 #include "ospf6_lsdb.h"
34 #include "ospf6_route.h"
35 #include "ospf6_top.h"
36 #include "ospf6_area.h"
37 #include "ospf6_interface.h"
39 #include "ospf6_zebra.h"
41 unsigned char conf_debug_ospf6_route
= 0;
43 static char *ospf6_route_table_name(struct ospf6_route_table
*table
)
46 switch (table
->scope_type
) {
47 case OSPF6_SCOPE_TYPE_GLOBAL
: {
48 switch (table
->table_type
) {
49 case OSPF6_TABLE_TYPE_ROUTES
:
50 snprintf(name
, sizeof(name
), "global route table");
52 case OSPF6_TABLE_TYPE_BORDER_ROUTERS
:
53 snprintf(name
, sizeof(name
), "global brouter table");
55 case OSPF6_TABLE_TYPE_EXTERNAL_ROUTES
:
56 snprintf(name
, sizeof(name
), "global external table");
59 snprintf(name
, sizeof(name
), "global unknown table");
64 case OSPF6_SCOPE_TYPE_AREA
: {
65 struct ospf6_area
*oa
= (struct ospf6_area
*)table
->scope
;
66 switch (table
->table_type
) {
67 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
68 snprintf(name
, sizeof(name
), "area %s spf table",
71 case OSPF6_TABLE_TYPE_ROUTES
:
72 snprintf(name
, sizeof(name
), "area %s route table",
75 case OSPF6_TABLE_TYPE_PREFIX_RANGES
:
76 snprintf(name
, sizeof(name
), "area %s range table",
79 case OSPF6_TABLE_TYPE_SUMMARY_PREFIXES
:
80 snprintf(name
, sizeof(name
),
81 "area %s summary prefix table", oa
->name
);
83 case OSPF6_TABLE_TYPE_SUMMARY_ROUTERS
:
84 snprintf(name
, sizeof(name
),
85 "area %s summary router table", oa
->name
);
88 snprintf(name
, sizeof(name
), "area %s unknown table",
94 case OSPF6_SCOPE_TYPE_INTERFACE
: {
95 struct ospf6_interface
*oi
=
96 (struct ospf6_interface
*)table
->scope
;
97 switch (table
->table_type
) {
98 case OSPF6_TABLE_TYPE_CONNECTED_ROUTES
:
99 snprintf(name
, sizeof(name
),
100 "interface %s connected table",
101 oi
->interface
->name
);
104 snprintf(name
, sizeof(name
),
105 "interface %s unknown table",
106 oi
->interface
->name
);
112 switch (table
->table_type
) {
113 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
114 snprintf(name
, sizeof(name
), "temporary spf table");
117 snprintf(name
, sizeof(name
), "temporary unknown table");
125 void ospf6_linkstate_prefix(u_int32_t adv_router
, u_int32_t id
,
126 struct prefix
*prefix
)
128 memset(prefix
, 0, sizeof(struct prefix
));
129 prefix
->family
= AF_INET6
;
130 prefix
->prefixlen
= 64;
131 memcpy(&prefix
->u
.prefix6
.s6_addr
[0], &adv_router
, 4);
132 memcpy(&prefix
->u
.prefix6
.s6_addr
[4], &id
, 4);
135 void ospf6_linkstate_prefix2str(struct prefix
*prefix
, char *buf
, int size
)
137 u_int32_t adv_router
, id
;
138 char adv_router_str
[16], id_str
[16];
139 memcpy(&adv_router
, &prefix
->u
.prefix6
.s6_addr
[0], 4);
140 memcpy(&id
, &prefix
->u
.prefix6
.s6_addr
[4], 4);
141 inet_ntop(AF_INET
, &adv_router
, adv_router_str
, sizeof(adv_router_str
));
142 inet_ntop(AF_INET
, &id
, id_str
, sizeof(id_str
));
144 snprintf(buf
, size
, "%s Net-ID: %s", adv_router_str
, id_str
);
146 snprintf(buf
, size
, "%s", adv_router_str
);
149 /* Global strings for logging */
150 const char *ospf6_dest_type_str
[OSPF6_DEST_TYPE_MAX
] = {
151 "Unknown", "Router", "Network", "Discard", "Linkstate", "AddressRange",
154 const char *ospf6_dest_type_substr
[OSPF6_DEST_TYPE_MAX
] = {
155 "?", "R", "N", "D", "L", "A",
158 const char *ospf6_path_type_str
[OSPF6_PATH_TYPE_MAX
] = {
159 "Unknown", "Intra-Area", "Inter-Area", "External-1", "External-2",
162 const char *ospf6_path_type_substr
[OSPF6_PATH_TYPE_MAX
] = {
163 "??", "IA", "IE", "E1", "E2",
167 struct ospf6_nexthop
*ospf6_nexthop_create(void)
169 struct ospf6_nexthop
*nh
;
171 nh
= XCALLOC(MTYPE_OSPF6_NEXTHOP
, sizeof(struct ospf6_nexthop
));
175 void ospf6_nexthop_delete(struct ospf6_nexthop
*nh
)
178 XFREE(MTYPE_OSPF6_NEXTHOP
, nh
);
181 void ospf6_free_nexthops(struct list
*nh_list
)
183 struct ospf6_nexthop
*nh
;
184 struct listnode
*node
, *nnode
;
187 for (ALL_LIST_ELEMENTS(nh_list
, node
, nnode
, nh
))
188 ospf6_nexthop_delete(nh
);
192 void ospf6_clear_nexthops(struct list
*nh_list
)
194 struct listnode
*node
;
195 struct ospf6_nexthop
*nh
;
198 for (ALL_LIST_ELEMENTS_RO(nh_list
, node
, nh
))
199 ospf6_nexthop_clear(nh
);
203 static struct ospf6_nexthop
*
204 ospf6_route_find_nexthop(struct list
*nh_list
, struct ospf6_nexthop
*nh_match
)
206 struct listnode
*node
;
207 struct ospf6_nexthop
*nh
;
209 if (nh_list
&& nh_match
) {
210 for (ALL_LIST_ELEMENTS_RO(nh_list
, node
, nh
)) {
211 if (ospf6_nexthop_is_same(nh
, nh_match
))
219 void ospf6_copy_nexthops(struct list
*dst
, struct list
*src
)
221 struct ospf6_nexthop
*nh_new
, *nh
;
222 struct listnode
*node
;
225 for (ALL_LIST_ELEMENTS_RO(src
, node
, nh
)) {
226 if (ospf6_nexthop_is_set(nh
)) {
227 nh_new
= ospf6_nexthop_create();
228 ospf6_nexthop_copy(nh_new
, nh
);
229 listnode_add(dst
, nh_new
);
235 void ospf6_merge_nexthops(struct list
*dst
, struct list
*src
)
237 struct listnode
*node
;
238 struct ospf6_nexthop
*nh
, *nh_new
;
241 for (ALL_LIST_ELEMENTS_RO(src
, node
, nh
)) {
242 if (!ospf6_route_find_nexthop(dst
, nh
)) {
243 nh_new
= ospf6_nexthop_create();
244 ospf6_nexthop_copy(nh_new
, nh
);
245 listnode_add(dst
, nh_new
);
251 int ospf6_route_cmp_nexthops(struct ospf6_route
*a
, struct ospf6_route
*b
)
253 struct listnode
*anode
, *bnode
;
254 struct ospf6_nexthop
*anh
, *bnh
;
257 if (listcount(a
->nh_list
) == listcount(b
->nh_list
)) {
258 for (ALL_LIST_ELEMENTS_RO(a
->nh_list
, anode
, anh
)) {
259 for (ALL_LIST_ELEMENTS_RO(b
->nh_list
, bnode
,
261 if (!ospf6_nexthop_is_same(anh
, bnh
))
268 /* One of the routes doesn't exist ? */
272 int ospf6_num_nexthops(struct list
*nh_list
)
274 return (listcount(nh_list
));
277 void ospf6_add_nexthop(struct list
*nh_list
, int ifindex
, struct in6_addr
*addr
)
279 struct ospf6_nexthop
*nh
;
280 struct ospf6_nexthop nh_match
;
283 nh_match
.ifindex
= ifindex
;
285 memcpy(&nh_match
.address
, addr
,
286 sizeof(struct in6_addr
));
288 memset(&nh_match
.address
, 0, sizeof(struct in6_addr
));
290 if (!ospf6_route_find_nexthop(nh_list
, &nh_match
)) {
291 nh
= ospf6_nexthop_create();
292 ospf6_nexthop_copy(nh
, &nh_match
);
293 listnode_add(nh_list
, nh
);
298 void ospf6_route_zebra_copy_nexthops(struct ospf6_route
*route
,
299 ifindex_t
*ifindexes
,
300 struct in6_addr
**nexthop_addr
,
303 struct ospf6_nexthop
*nh
;
304 struct listnode
*node
;
310 for (ALL_LIST_ELEMENTS_RO(route
->nh_list
, node
, nh
)) {
311 if (IS_OSPF6_DEBUG_ZEBRA(SEND
)) {
313 inet_ntop(AF_INET6
, &nh
->address
, buf
,
315 ifname
= ifindex2ifname(nh
->ifindex
,
317 zlog_debug(" nexthop: %s%%%.*s(%d)", buf
,
318 IFNAMSIZ
, ifname
, nh
->ifindex
);
321 nexthop_addr
[i
] = &nh
->address
;
322 ifindexes
[i
] = nh
->ifindex
;
331 int ospf6_route_get_first_nh_index(struct ospf6_route
*route
)
333 struct ospf6_nexthop
*nh
;
336 if ((nh
= (struct ospf6_nexthop
*)listhead(route
->nh_list
)))
337 return (nh
->ifindex
);
343 struct ospf6_route
*ospf6_route_create(void)
345 struct ospf6_route
*route
;
346 route
= XCALLOC(MTYPE_OSPF6_ROUTE
, sizeof(struct ospf6_route
));
347 route
->nh_list
= list_new();
351 void ospf6_route_delete(struct ospf6_route
*route
)
354 ospf6_free_nexthops(route
->nh_list
);
355 list_free(route
->nh_list
);
356 XFREE(MTYPE_OSPF6_ROUTE
, route
);
360 struct ospf6_route
*ospf6_route_copy(struct ospf6_route
*route
)
362 struct ospf6_route
*new;
364 new = ospf6_route_create();
365 new->type
= route
->type
;
366 memcpy(&new->prefix
, &route
->prefix
, sizeof(struct prefix
));
367 new->installed
= route
->installed
;
368 new->changed
= route
->changed
;
369 new->flag
= route
->flag
;
370 new->route_option
= route
->route_option
;
371 new->linkstate_id
= route
->linkstate_id
;
372 new->path
= route
->path
;
373 ospf6_copy_nexthops(new->nh_list
, route
->nh_list
);
382 void ospf6_route_lock(struct ospf6_route
*route
)
387 void ospf6_route_unlock(struct ospf6_route
*route
)
389 assert(route
->lock
> 0);
391 if (route
->lock
== 0) {
392 /* Can't detach from the table until here
393 because ospf6_route_next () will use
394 the 'route->table' pointer for logging */
396 ospf6_route_delete(route
);
400 /* Route compare function. If ra is more preferred, it returns
401 less than 0. If rb is more preferred returns greater than 0.
402 Otherwise (neither one is preferred), returns 0 */
403 int ospf6_route_cmp(struct ospf6_route
*ra
, struct ospf6_route
*rb
)
405 assert(ospf6_route_is_same(ra
, rb
));
406 assert(OSPF6_PATH_TYPE_NONE
< ra
->path
.type
407 && ra
->path
.type
< OSPF6_PATH_TYPE_MAX
);
408 assert(OSPF6_PATH_TYPE_NONE
< rb
->path
.type
409 && rb
->path
.type
< OSPF6_PATH_TYPE_MAX
);
411 if (ra
->type
!= rb
->type
)
412 return (ra
->type
- rb
->type
);
414 if (ra
->path
.area_id
!= rb
->path
.area_id
)
415 return (ntohl(ra
->path
.area_id
) - ntohl(rb
->path
.area_id
));
417 if (ra
->path
.type
!= rb
->path
.type
)
418 return (ra
->path
.type
- rb
->path
.type
);
420 if (ra
->path
.type
== OSPF6_PATH_TYPE_EXTERNAL2
) {
421 if (ra
->path
.u
.cost_e2
!= rb
->path
.u
.cost_e2
)
422 return (ra
->path
.u
.cost_e2
- rb
->path
.u
.cost_e2
);
424 if (ra
->path
.cost
!= rb
->path
.cost
)
425 return (ra
->path
.cost
- rb
->path
.cost
);
431 struct ospf6_route
*ospf6_route_lookup(struct prefix
*prefix
,
432 struct ospf6_route_table
*table
)
434 struct route_node
*node
;
435 struct ospf6_route
*route
;
437 node
= route_node_lookup(table
->table
, prefix
);
441 route
= (struct ospf6_route
*)node
->info
;
446 ospf6_route_lookup_identical(struct ospf6_route
*route
,
447 struct ospf6_route_table
*table
)
449 struct ospf6_route
*target
;
451 for (target
= ospf6_route_lookup(&route
->prefix
, table
); target
;
452 target
= target
->next
) {
453 if (ospf6_route_is_identical(target
, route
))
460 ospf6_route_lookup_bestmatch(struct prefix
*prefix
,
461 struct ospf6_route_table
*table
)
463 struct route_node
*node
;
464 struct ospf6_route
*route
;
466 node
= route_node_match(table
->table
, prefix
);
469 route_unlock_node(node
);
471 route
= (struct ospf6_route
*)node
->info
;
476 static void route_table_assert(struct ospf6_route_table
*table
)
478 struct ospf6_route
*prev
, *r
, *next
;
479 char buf
[PREFIX2STR_BUFFER
];
480 unsigned int link_error
= 0, num
= 0;
482 r
= ospf6_route_head(table
);
488 next
= ospf6_route_next(r
);
497 for (r
= ospf6_route_head(table
); r
; r
= ospf6_route_next(r
))
500 if (link_error
== 0 && num
== table
->count
)
503 zlog_err("PANIC !!");
504 zlog_err("Something has gone wrong with ospf6_route_table[%p]", table
);
505 zlog_debug("table count = %d, real number = %d", table
->count
, num
);
506 zlog_debug("DUMP START");
507 for (r
= ospf6_route_head(table
); r
; r
= ospf6_route_next(r
)) {
508 prefix2str(&r
->prefix
, buf
, sizeof(buf
));
509 zlog_info("%p<-[%p]->%p : %s", r
->prev
, r
, r
->next
, buf
);
511 zlog_debug("DUMP END");
513 assert(link_error
== 0 && num
== table
->count
);
515 #define ospf6_route_table_assert(t) (route_table_assert (t))
517 #define ospf6_route_table_assert(t) ((void) 0)
520 struct ospf6_route
*ospf6_route_add(struct ospf6_route
*route
,
521 struct ospf6_route_table
*table
)
523 struct route_node
*node
, *nextnode
, *prevnode
;
524 struct ospf6_route
*current
= NULL
;
525 struct ospf6_route
*prev
= NULL
, *old
= NULL
, *next
= NULL
;
526 char buf
[PREFIX2STR_BUFFER
];
529 assert(route
->rnode
== NULL
);
530 assert(route
->lock
== 0);
531 assert(route
->next
== NULL
);
532 assert(route
->prev
== NULL
);
534 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
535 ospf6_linkstate_prefix2str(&route
->prefix
, buf
, sizeof(buf
));
537 prefix2str(&route
->prefix
, buf
, sizeof(buf
));
539 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
540 zlog_debug("%s %p: route add %p: %s",
541 ospf6_route_table_name(table
), (void *)table
,
543 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
544 zlog_debug("%s: route add: %s", ospf6_route_table_name(table
),
549 node
= route_node_get(table
->table
, &route
->prefix
);
552 /* find place to insert */
553 for (current
= node
->info
; current
; current
= current
->next
) {
554 if (!ospf6_route_is_same(current
, route
))
556 else if (current
->type
!= route
->type
)
558 else if (ospf6_route_is_same_origin(current
, route
))
560 else if (ospf6_route_cmp(current
, route
) > 0)
570 /* if route does not actually change, return unchanged */
571 if (ospf6_route_is_identical(old
, route
)) {
572 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
574 "%s %p: route add %p: needless update of %p",
575 ospf6_route_table_name(table
),
576 (void *)table
, (void *)route
,
578 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
579 zlog_debug("%s: route add: needless update",
580 ospf6_route_table_name(table
));
582 ospf6_route_delete(route
);
583 SET_FLAG(old
->flag
, OSPF6_ROUTE_ADD
);
584 ospf6_route_table_assert(table
);
589 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
590 zlog_debug("%s %p: route add %p: update of %p",
591 ospf6_route_table_name(table
), (void *)table
,
592 (void *)route
, (void *)old
);
593 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
594 zlog_debug("%s: route add: update",
595 ospf6_route_table_name(table
));
597 /* replace old one if exists */
598 if (node
->info
== old
) {
600 SET_FLAG(route
->flag
, OSPF6_ROUTE_BEST
);
604 old
->prev
->next
= route
;
605 route
->prev
= old
->prev
;
607 old
->next
->prev
= route
;
608 route
->next
= old
->next
;
610 route
->installed
= old
->installed
;
611 route
->changed
= now
;
612 assert(route
->table
== NULL
);
613 route
->table
= table
;
615 ospf6_route_unlock(old
); /* will be deleted later */
616 ospf6_route_lock(route
);
618 SET_FLAG(route
->flag
, OSPF6_ROUTE_CHANGE
);
619 ospf6_route_table_assert(table
);
622 (*table
->hook_add
)(route
);
627 /* insert if previous or next node found */
629 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
631 "%s %p: route add %p: another path: prev %p, next %p",
632 ospf6_route_table_name(table
), (void *)table
,
633 (void *)route
, (void *)prev
, (void *)next
);
634 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
635 zlog_debug("%s: route add: another path found",
636 ospf6_route_table_name(table
));
650 if (node
->info
== next
) {
651 assert(next
->rnode
== node
);
653 UNSET_FLAG(next
->flag
, OSPF6_ROUTE_BEST
);
654 SET_FLAG(route
->flag
, OSPF6_ROUTE_BEST
);
655 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
657 "%s %p: route add %p: replacing previous best: %p",
658 ospf6_route_table_name(table
),
659 (void *)table
, (void *)route
,
663 route
->installed
= now
;
664 route
->changed
= now
;
665 assert(route
->table
== NULL
);
666 route
->table
= table
;
668 ospf6_route_lock(route
);
670 ospf6_route_table_assert(table
);
672 SET_FLAG(route
->flag
, OSPF6_ROUTE_ADD
);
674 (*table
->hook_add
)(route
);
679 /* Else, this is the brand new route regarding to the prefix */
680 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
681 zlog_debug("%s %p: route add %p: brand new route",
682 ospf6_route_table_name(table
), (void *)table
,
684 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
685 zlog_debug("%s: route add: brand new route",
686 ospf6_route_table_name(table
));
688 assert(node
->info
== NULL
);
690 SET_FLAG(route
->flag
, OSPF6_ROUTE_BEST
);
691 ospf6_route_lock(route
);
692 route
->installed
= now
;
693 route
->changed
= now
;
694 assert(route
->table
== NULL
);
695 route
->table
= table
;
697 /* lookup real existing next route */
699 route_lock_node(nextnode
);
701 nextnode
= route_next(nextnode
);
702 } while (nextnode
&& nextnode
->info
== NULL
);
705 if (nextnode
== NULL
)
708 route_unlock_node(nextnode
);
710 next
= nextnode
->info
;
715 /* lookup real existing prev route */
717 route_lock_node(prevnode
);
719 prevnode
= route_prev(prevnode
);
720 } while (prevnode
&& prevnode
->info
== NULL
);
723 if (prevnode
== NULL
)
726 route_unlock_node(prevnode
);
728 prev
= prevnode
->info
;
729 while (prev
->next
&& ospf6_route_is_same(prev
, prev
->next
))
736 ospf6_route_table_assert(table
);
738 SET_FLAG(route
->flag
, OSPF6_ROUTE_ADD
);
740 (*table
->hook_add
)(route
);
745 void ospf6_route_remove(struct ospf6_route
*route
,
746 struct ospf6_route_table
*table
)
748 struct route_node
*node
;
749 struct ospf6_route
*current
;
750 char buf
[PREFIX2STR_BUFFER
];
752 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
753 ospf6_linkstate_prefix2str(&route
->prefix
, buf
, sizeof(buf
));
755 prefix2str(&route
->prefix
, buf
, sizeof(buf
));
757 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
758 zlog_debug("%s %p: route remove %p: %s",
759 ospf6_route_table_name(table
), (void *)table
,
761 else if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
762 zlog_debug("%s: route remove: %s",
763 ospf6_route_table_name(table
), buf
);
765 node
= route_node_lookup(table
->table
, &route
->prefix
);
768 /* find the route to remove, making sure that the route pointer
769 is from the route table. */
770 current
= node
->info
;
771 while (current
&& ospf6_route_is_same(current
, route
)) {
772 if (current
== route
)
774 current
= current
->next
;
776 assert(current
== route
);
778 /* adjust doubly linked list */
780 route
->prev
->next
= route
->next
;
782 route
->next
->prev
= route
->prev
;
784 if (node
->info
== route
) {
785 if (route
->next
&& route
->next
->rnode
== node
) {
786 node
->info
= route
->next
;
787 SET_FLAG(route
->next
->flag
, OSPF6_ROUTE_BEST
);
789 node
->info
= NULL
; /* should unlock route_node here ? */
793 ospf6_route_table_assert(table
);
795 SET_FLAG(route
->flag
, OSPF6_ROUTE_WAS_REMOVED
);
797 if (table
->hook_remove
)
798 (*table
->hook_remove
)(route
);
800 ospf6_route_unlock(route
);
803 struct ospf6_route
*ospf6_route_head(struct ospf6_route_table
*table
)
805 struct route_node
*node
;
806 struct ospf6_route
*route
;
808 node
= route_top(table
->table
);
812 /* skip to the real existing entry */
813 while (node
&& node
->info
== NULL
)
814 node
= route_next(node
);
818 route_unlock_node(node
);
821 route
= (struct ospf6_route
*)node
->info
;
822 assert(route
->prev
== NULL
);
823 assert(route
->table
== table
);
824 ospf6_route_lock(route
);
826 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
827 zlog_info("%s %p: route head: %p<-[%p]->%p",
828 ospf6_route_table_name(table
), (void *)table
,
829 (void *)route
->prev
, (void *)route
,
830 (void *)route
->next
);
835 struct ospf6_route
*ospf6_route_next(struct ospf6_route
*route
)
837 struct ospf6_route
*next
= route
->next
;
839 if (IS_OSPF6_DEBUG_ROUTE(MEMORY
))
840 zlog_info("%s %p: route next: %p<-[%p]->%p",
841 ospf6_route_table_name(route
->table
),
842 (void *)route
->table
, (void *)route
->prev
,
843 (void *)route
, (void *)route
->next
);
845 ospf6_route_unlock(route
);
847 ospf6_route_lock(next
);
852 struct ospf6_route
*ospf6_route_best_next(struct ospf6_route
*route
)
854 struct route_node
*rnode
;
855 struct ospf6_route
*next
;
857 ospf6_route_unlock(route
);
859 rnode
= route
->rnode
;
860 route_lock_node(rnode
);
861 rnode
= route_next(rnode
);
862 while (rnode
&& rnode
->info
== NULL
)
863 rnode
= route_next(rnode
);
866 route_unlock_node(rnode
);
869 next
= (struct ospf6_route
*)rnode
->info
;
870 ospf6_route_lock(next
);
874 struct ospf6_route
*ospf6_route_match_head(struct prefix
*prefix
,
875 struct ospf6_route_table
*table
)
877 struct route_node
*node
;
878 struct ospf6_route
*route
;
880 /* Walk down tree. */
881 node
= table
->table
->top
;
882 while (node
&& node
->p
.prefixlen
< prefix
->prefixlen
883 && prefix_match(&node
->p
, prefix
))
884 node
= node
->link
[prefix_bit(&prefix
->u
.prefix
,
888 route_lock_node(node
);
889 while (node
&& node
->info
== NULL
)
890 node
= route_next(node
);
893 route_unlock_node(node
);
895 if (!prefix_match(prefix
, &node
->p
))
899 ospf6_route_lock(route
);
903 struct ospf6_route
*ospf6_route_match_next(struct prefix
*prefix
,
904 struct ospf6_route
*route
)
906 struct ospf6_route
*next
;
908 next
= ospf6_route_next(route
);
909 if (next
&& !prefix_match(prefix
, &next
->prefix
)) {
910 ospf6_route_unlock(next
);
917 void ospf6_route_remove_all(struct ospf6_route_table
*table
)
919 struct ospf6_route
*route
;
920 for (route
= ospf6_route_head(table
); route
;
921 route
= ospf6_route_next(route
))
922 ospf6_route_remove(route
, table
);
925 struct ospf6_route_table
*ospf6_route_table_create(int s
, int t
)
927 struct ospf6_route_table
*new;
928 new = XCALLOC(MTYPE_OSPF6_ROUTE
, sizeof(struct ospf6_route_table
));
929 new->table
= route_table_init();
935 void ospf6_route_table_delete(struct ospf6_route_table
*table
)
937 ospf6_route_remove_all(table
);
938 route_table_finish(table
->table
);
939 XFREE(MTYPE_OSPF6_ROUTE
, table
);
944 void ospf6_route_show(struct vty
*vty
, struct ospf6_route
*route
)
947 char destination
[PREFIX2STR_BUFFER
], nexthop
[64];
950 struct timeval now
, res
;
951 struct listnode
*node
;
952 struct ospf6_nexthop
*nh
;
955 timersub(&now
, &route
->changed
, &res
);
956 timerstring(&res
, duration
, sizeof(duration
));
959 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
960 ospf6_linkstate_prefix2str(&route
->prefix
, destination
,
961 sizeof(destination
));
962 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
963 inet_ntop(route
->prefix
.family
, &route
->prefix
.u
.prefix
,
964 destination
, sizeof(destination
));
966 prefix2str(&route
->prefix
, destination
, sizeof(destination
));
969 for (ALL_LIST_ELEMENTS_RO(route
->nh_list
, node
, nh
)) {
971 inet_ntop(AF_INET6
, &nh
->address
, nexthop
, sizeof(nexthop
));
972 ifname
= ifindex2ifname(nh
->ifindex
, VRF_DEFAULT
);
975 vty_out(vty
, "%c%1s %2s %-30s %-25s %6.*s %s\n",
976 (ospf6_route_is_best(route
) ? '*' : ' '),
977 OSPF6_DEST_TYPE_SUBSTR(route
->type
),
978 OSPF6_PATH_TYPE_SUBSTR(route
->path
.type
),
979 destination
, nexthop
, IFNAMSIZ
, ifname
,
983 vty_out(vty
, "%c%1s %2s %-30s %-25s %6.*s %s\n", ' ',
984 "", "", "", nexthop
, IFNAMSIZ
, ifname
, "");
988 void ospf6_route_show_detail(struct vty
*vty
, struct ospf6_route
*route
)
991 char destination
[PREFIX2STR_BUFFER
], nexthop
[64];
992 char area_id
[16], id
[16], adv_router
[16], capa
[16], options
[16];
993 struct timeval now
, res
;
995 struct listnode
*node
;
996 struct ospf6_nexthop
*nh
;
1001 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
1002 ospf6_linkstate_prefix2str(&route
->prefix
, destination
,
1003 sizeof(destination
));
1004 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
1005 inet_ntop(route
->prefix
.family
, &route
->prefix
.u
.prefix
,
1006 destination
, sizeof(destination
));
1008 prefix2str(&route
->prefix
, destination
, sizeof(destination
));
1009 vty_out(vty
, "Destination: %s\n", destination
);
1011 /* destination type */
1012 vty_out(vty
, "Destination type: %s\n",
1013 OSPF6_DEST_TYPE_NAME(route
->type
));
1016 timersub(&now
, &route
->installed
, &res
);
1017 timerstring(&res
, duration
, sizeof(duration
));
1018 vty_out(vty
, "Installed Time: %s ago\n", duration
);
1020 timersub(&now
, &route
->changed
, &res
);
1021 timerstring(&res
, duration
, sizeof(duration
));
1022 vty_out(vty
, " Changed Time: %s ago\n", duration
);
1024 /* Debugging info */
1025 vty_out(vty
, "Lock: %d Flags: %s%s%s%s\n", route
->lock
,
1026 (CHECK_FLAG(route
->flag
, OSPF6_ROUTE_BEST
) ? "B" : "-"),
1027 (CHECK_FLAG(route
->flag
, OSPF6_ROUTE_ADD
) ? "A" : "-"),
1028 (CHECK_FLAG(route
->flag
, OSPF6_ROUTE_REMOVE
) ? "R" : "-"),
1029 (CHECK_FLAG(route
->flag
, OSPF6_ROUTE_CHANGE
) ? "C" : "-"));
1030 vty_out(vty
, "Memory: prev: %p this: %p next: %p\n",
1031 (void *)route
->prev
, (void *)route
, (void *)route
->next
);
1036 inet_ntop(AF_INET
, &route
->path
.area_id
, area_id
, sizeof(area_id
));
1037 vty_out(vty
, "Associated Area: %s\n", area_id
);
1040 vty_out(vty
, "Path Type: %s\n", OSPF6_PATH_TYPE_NAME(route
->path
.type
));
1043 inet_ntop(AF_INET
, &route
->path
.origin
.id
, id
, sizeof(id
));
1044 inet_ntop(AF_INET
, &route
->path
.origin
.adv_router
, adv_router
,
1045 sizeof(adv_router
));
1046 vty_out(vty
, "LS Origin: %s Id: %s Adv: %s\n",
1047 ospf6_lstype_name(route
->path
.origin
.type
), id
, adv_router
);
1050 ospf6_options_printbuf(route
->path
.options
, options
, sizeof(options
));
1051 vty_out(vty
, "Options: %s\n", options
);
1054 ospf6_capability_printbuf(route
->path
.router_bits
, capa
, sizeof(capa
));
1055 vty_out(vty
, "Router Bits: %s\n", capa
);
1057 /* Prefix Options */
1058 vty_out(vty
, "Prefix Options: xxx\n");
1061 vty_out(vty
, "Metric Type: %d\n", route
->path
.metric_type
);
1062 vty_out(vty
, "Metric: %d (%d)\n", route
->path
.cost
,
1063 route
->path
.u
.cost_e2
);
1066 vty_out(vty
, "Nexthop:\n");
1067 for (ALL_LIST_ELEMENTS_RO(route
->nh_list
, node
, nh
)) {
1069 inet_ntop(AF_INET6
, &nh
->address
, nexthop
, sizeof(nexthop
));
1070 ifname
= ifindex2ifname(nh
->ifindex
, VRF_DEFAULT
);
1071 vty_out(vty
, " %s %.*s\n", nexthop
, IFNAMSIZ
, ifname
);
1076 static void ospf6_route_show_table_summary(struct vty
*vty
,
1077 struct ospf6_route_table
*table
)
1079 struct ospf6_route
*route
, *prev
= NULL
;
1080 int i
, pathtype
[OSPF6_PATH_TYPE_MAX
];
1081 unsigned int number
= 0;
1082 int nh_count
= 0, nhinval
= 0, ecmp
= 0;
1083 int alternative
= 0, destination
= 0;
1085 for (i
= 0; i
< OSPF6_PATH_TYPE_MAX
; i
++)
1088 for (route
= ospf6_route_head(table
); route
;
1089 route
= ospf6_route_next(route
)) {
1090 if (prev
== NULL
|| !ospf6_route_is_same(prev
, route
))
1094 nh_count
= ospf6_num_nexthops(route
->nh_list
);
1097 else if (nh_count
> 1)
1099 pathtype
[route
->path
.type
]++;
1105 assert(number
== table
->count
);
1107 vty_out(vty
, "Number of OSPFv3 routes: %d\n", number
);
1108 vty_out(vty
, "Number of Destination: %d\n", destination
);
1109 vty_out(vty
, "Number of Alternative routes: %d\n", alternative
);
1110 vty_out(vty
, "Number of Equal Cost Multi Path: %d\n", ecmp
);
1111 for (i
= OSPF6_PATH_TYPE_INTRA
; i
<= OSPF6_PATH_TYPE_EXTERNAL2
; i
++) {
1112 vty_out(vty
, "Number of %s routes: %d\n",
1113 OSPF6_PATH_TYPE_NAME(i
), pathtype
[i
]);
1117 static void ospf6_route_show_table_prefix(struct vty
*vty
,
1118 struct prefix
*prefix
,
1119 struct ospf6_route_table
*table
)
1121 struct ospf6_route
*route
;
1123 route
= ospf6_route_lookup(prefix
, table
);
1127 ospf6_route_lock(route
);
1128 while (route
&& ospf6_route_is_prefix(prefix
, route
)) {
1129 /* Specifying a prefix will always display details */
1130 ospf6_route_show_detail(vty
, route
);
1131 route
= ospf6_route_next(route
);
1134 ospf6_route_unlock(route
);
1137 static void ospf6_route_show_table_address(struct vty
*vty
,
1138 struct prefix
*prefix
,
1139 struct ospf6_route_table
*table
)
1141 struct ospf6_route
*route
;
1143 route
= ospf6_route_lookup_bestmatch(prefix
, table
);
1147 prefix
= &route
->prefix
;
1148 ospf6_route_lock(route
);
1149 while (route
&& ospf6_route_is_prefix(prefix
, route
)) {
1150 /* Specifying a prefix will always display details */
1151 ospf6_route_show_detail(vty
, route
);
1152 route
= ospf6_route_next(route
);
1155 ospf6_route_unlock(route
);
1158 static void ospf6_route_show_table_match(struct vty
*vty
, int detail
,
1159 struct prefix
*prefix
,
1160 struct ospf6_route_table
*table
)
1162 struct ospf6_route
*route
;
1163 assert(prefix
->family
);
1165 route
= ospf6_route_match_head(prefix
, table
);
1168 ospf6_route_show_detail(vty
, route
);
1170 ospf6_route_show(vty
, route
);
1171 route
= ospf6_route_match_next(prefix
, route
);
1175 static void ospf6_route_show_table_type(struct vty
*vty
, int detail
,
1177 struct ospf6_route_table
*table
)
1179 struct ospf6_route
*route
;
1181 route
= ospf6_route_head(table
);
1183 if (route
->path
.type
== type
) {
1185 ospf6_route_show_detail(vty
, route
);
1187 ospf6_route_show(vty
, route
);
1189 route
= ospf6_route_next(route
);
1193 static void ospf6_route_show_table(struct vty
*vty
, int detail
,
1194 struct ospf6_route_table
*table
)
1196 struct ospf6_route
*route
;
1198 route
= ospf6_route_head(table
);
1201 ospf6_route_show_detail(vty
, route
);
1203 ospf6_route_show(vty
, route
);
1204 route
= ospf6_route_next(route
);
1208 int ospf6_route_table_show(struct vty
*vty
, int argc_start
, int argc
,
1209 struct cmd_token
**argv
,
1210 struct ospf6_route_table
*table
)
1218 struct prefix prefix
;
1221 memset(&prefix
, 0, sizeof(struct prefix
));
1223 for (i
= argc_start
; i
< argc
; i
++) {
1224 if (strmatch(argv
[i
]->text
, "summary")) {
1229 if (strmatch(argv
[i
]->text
, "intra-area")) {
1230 type
= OSPF6_PATH_TYPE_INTRA
;
1234 if (strmatch(argv
[i
]->text
, "inter-area")) {
1235 type
= OSPF6_PATH_TYPE_INTER
;
1239 if (strmatch(argv
[i
]->text
, "external-1")) {
1240 type
= OSPF6_PATH_TYPE_EXTERNAL1
;
1244 if (strmatch(argv
[i
]->text
, "external-2")) {
1245 type
= OSPF6_PATH_TYPE_EXTERNAL2
;
1249 if (strmatch(argv
[i
]->text
, "detail")) {
1254 if (strmatch(argv
[i
]->text
, "match")) {
1259 ret
= str2prefix(argv
[i
]->arg
, &prefix
);
1260 if (ret
== 1 && prefix
.family
== AF_INET6
) {
1262 if (strchr(argv
[i
]->arg
, '/'))
1267 vty_out(vty
, "Malformed argument: %s\n", argv
[i
]->arg
);
1271 /* Give summary of this route table */
1273 ospf6_route_show_table_summary(vty
, table
);
1277 /* Give exact prefix-match route */
1278 if (isprefix
&& !match
) {
1279 /* If exact address, give best matching route */
1281 ospf6_route_show_table_address(vty
, &prefix
, table
);
1283 ospf6_route_show_table_prefix(vty
, &prefix
, table
);
1289 ospf6_route_show_table_match(vty
, detail
, &prefix
, table
);
1291 ospf6_route_show_table_type(vty
, detail
, type
, table
);
1293 ospf6_route_show_table(vty
, detail
, table
);
1298 static void ospf6_linkstate_show_header(struct vty
*vty
)
1300 vty_out(vty
, "%-7s %-15s %-15s %-8s %-14s %s\n", "Type", "Router-ID",
1301 "Net-ID", "Rtr-Bits", "Options", "Cost");
1304 static void ospf6_linkstate_show(struct vty
*vty
, struct ospf6_route
*route
)
1306 u_int32_t router
, id
;
1307 char routername
[16], idname
[16], rbits
[16], options
[16];
1309 router
= ospf6_linkstate_prefix_adv_router(&route
->prefix
);
1310 inet_ntop(AF_INET
, &router
, routername
, sizeof(routername
));
1311 id
= ospf6_linkstate_prefix_id(&route
->prefix
);
1312 inet_ntop(AF_INET
, &id
, idname
, sizeof(idname
));
1314 ospf6_capability_printbuf(route
->path
.router_bits
, rbits
,
1316 ospf6_options_printbuf(route
->path
.options
, options
, sizeof(options
));
1319 vty_out(vty
, "%-7s %-15s %-15s %-8s %-14s %lu\n", "Network",
1320 routername
, idname
, rbits
, options
,
1321 (unsigned long)route
->path
.cost
);
1323 vty_out(vty
, "%-7s %-15s %-15s %-8s %-14s %lu\n", "Router",
1324 routername
, idname
, rbits
, options
,
1325 (unsigned long)route
->path
.cost
);
1329 static void ospf6_linkstate_show_table_exact(struct vty
*vty
,
1330 struct prefix
*prefix
,
1331 struct ospf6_route_table
*table
)
1333 struct ospf6_route
*route
;
1335 route
= ospf6_route_lookup(prefix
, table
);
1339 ospf6_route_lock(route
);
1340 while (route
&& ospf6_route_is_prefix(prefix
, route
)) {
1341 /* Specifying a prefix will always display details */
1342 ospf6_route_show_detail(vty
, route
);
1343 route
= ospf6_route_next(route
);
1346 ospf6_route_unlock(route
);
1349 static void ospf6_linkstate_show_table(struct vty
*vty
, int detail
,
1350 struct ospf6_route_table
*table
)
1352 struct ospf6_route
*route
;
1355 ospf6_linkstate_show_header(vty
);
1357 route
= ospf6_route_head(table
);
1360 ospf6_route_show_detail(vty
, route
);
1362 ospf6_linkstate_show(vty
, route
);
1363 route
= ospf6_route_next(route
);
1367 int ospf6_linkstate_table_show(struct vty
*vty
, int idx_ipv4
, int argc
,
1368 struct cmd_token
**argv
,
1369 struct ospf6_route_table
*table
)
1375 struct prefix router
, id
, prefix
;
1377 memset(&router
, 0, sizeof(struct prefix
));
1378 memset(&id
, 0, sizeof(struct prefix
));
1379 memset(&prefix
, 0, sizeof(struct prefix
));
1381 for (i
= idx_ipv4
; i
< argc
; i
++) {
1382 if (strmatch(argv
[i
]->text
, "detail")) {
1388 ret
= str2prefix(argv
[i
]->arg
, &router
);
1389 if (ret
== 1 && router
.family
== AF_INET
) {
1393 vty_out(vty
, "Malformed argument: %s\n", argv
[i
]->arg
);
1398 ret
= str2prefix(argv
[i
]->arg
, &id
);
1399 if (ret
== 1 && id
.family
== AF_INET
) {
1403 vty_out(vty
, "Malformed argument: %s\n", argv
[i
]->arg
);
1407 vty_out(vty
, "Malformed argument: %s\n", argv
[i
]->arg
);
1412 ospf6_linkstate_prefix(router
.u
.prefix4
.s_addr
,
1413 id
.u
.prefix4
.s_addr
, &prefix
);
1416 ospf6_linkstate_show_table_exact(vty
, &prefix
, table
);
1418 ospf6_linkstate_show_table(vty
, detail
, table
);
1424 void ospf6_brouter_show_header(struct vty
*vty
)
1426 vty_out(vty
, "%-15s %-8s %-14s %-10s %-15s\n", "Router-ID", "Rtr-Bits",
1427 "Options", "Path-Type", "Area");
1430 void ospf6_brouter_show(struct vty
*vty
, struct ospf6_route
*route
)
1432 u_int32_t adv_router
;
1433 char adv
[16], rbits
[16], options
[16], area
[16];
1435 adv_router
= ospf6_linkstate_prefix_adv_router(&route
->prefix
);
1436 inet_ntop(AF_INET
, &adv_router
, adv
, sizeof(adv
));
1437 ospf6_capability_printbuf(route
->path
.router_bits
, rbits
,
1439 ospf6_options_printbuf(route
->path
.options
, options
, sizeof(options
));
1440 inet_ntop(AF_INET
, &route
->path
.area_id
, area
, sizeof(area
));
1442 /* vty_out (vty, "%-15s %-8s %-14s %-10s %-15s\n",
1443 "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area"); */
1444 vty_out(vty
, "%-15s %-8s %-14s %-10s %-15s\n", adv
, rbits
, options
,
1445 OSPF6_PATH_TYPE_NAME(route
->path
.type
), area
);
1448 DEFUN (debug_ospf6_route
,
1449 debug_ospf6_route_cmd
,
1450 "debug ospf6 route <table|intra-area|inter-area|memory>",
1454 "Debug route table calculation\n"
1455 "Debug intra-area route calculation\n"
1456 "Debug inter-area route calculation\n"
1457 "Debug route memory use\n"
1461 unsigned char level
= 0;
1463 if (!strncmp(argv
[idx_type
]->arg
, "table", 5))
1464 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1465 else if (!strncmp(argv
[idx_type
]->arg
, "intra", 5))
1466 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1467 else if (!strncmp(argv
[idx_type
]->arg
, "inter", 5))
1468 level
= OSPF6_DEBUG_ROUTE_INTER
;
1469 else if (!strncmp(argv
[idx_type
]->arg
, "memor", 5))
1470 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1471 OSPF6_DEBUG_ROUTE_ON(level
);
1475 DEFUN (no_debug_ospf6_route
,
1476 no_debug_ospf6_route_cmd
,
1477 "no debug ospf6 route <table|intra-area|inter-area|memory>",
1482 "Debug route table calculation\n"
1483 "Debug intra-area route calculation\n"
1484 "Debug inter-area route calculation\n"
1485 "Debug route memory use\n")
1488 unsigned char level
= 0;
1490 if (!strncmp(argv
[idx_type
]->arg
, "table", 5))
1491 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1492 else if (!strncmp(argv
[idx_type
]->arg
, "intra", 5))
1493 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1494 else if (!strncmp(argv
[idx_type
]->arg
, "inter", 5))
1495 level
= OSPF6_DEBUG_ROUTE_INTER
;
1496 else if (!strncmp(argv
[idx_type
]->arg
, "memor", 5))
1497 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1498 OSPF6_DEBUG_ROUTE_OFF(level
);
1502 int config_write_ospf6_debug_route(struct vty
*vty
)
1504 if (IS_OSPF6_DEBUG_ROUTE(TABLE
))
1505 vty_out(vty
, "debug ospf6 route table\n");
1506 if (IS_OSPF6_DEBUG_ROUTE(INTRA
))
1507 vty_out(vty
, "debug ospf6 route intra-area\n");
1508 if (IS_OSPF6_DEBUG_ROUTE(INTER
))
1509 vty_out(vty
, "debug ospf6 route inter-area\n");
1513 void install_element_ospf6_debug_route(void)
1515 install_element(ENABLE_NODE
, &debug_ospf6_route_cmd
);
1516 install_element(ENABLE_NODE
, &no_debug_ospf6_route_cmd
);
1517 install_element(CONFIG_NODE
, &debug_ospf6_route_cmd
);
1518 install_element(CONFIG_NODE
, &no_debug_ospf6_route_cmd
);