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;
44 ospf6_route_table_name (struct ospf6_route_table
*table
)
47 switch (table
->scope_type
)
49 case OSPF6_SCOPE_TYPE_GLOBAL
:
51 switch (table
->table_type
)
53 case OSPF6_TABLE_TYPE_ROUTES
:
54 snprintf (name
, sizeof (name
), "global route table");
56 case OSPF6_TABLE_TYPE_BORDER_ROUTERS
:
57 snprintf (name
, sizeof (name
), "global brouter table");
59 case OSPF6_TABLE_TYPE_EXTERNAL_ROUTES
:
60 snprintf (name
, sizeof (name
), "global external table");
63 snprintf (name
, sizeof (name
), "global unknown table");
69 case OSPF6_SCOPE_TYPE_AREA
:
71 struct ospf6_area
*oa
= (struct ospf6_area
*) table
->scope
;
72 switch (table
->table_type
)
74 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
75 snprintf (name
, sizeof (name
),
76 "area %s spf table", oa
->name
);
78 case OSPF6_TABLE_TYPE_ROUTES
:
79 snprintf (name
, sizeof (name
),
80 "area %s route table", oa
->name
);
82 case OSPF6_TABLE_TYPE_PREFIX_RANGES
:
83 snprintf (name
, sizeof (name
),
84 "area %s range table", oa
->name
);
86 case OSPF6_TABLE_TYPE_SUMMARY_PREFIXES
:
87 snprintf (name
, sizeof (name
),
88 "area %s summary prefix table", oa
->name
);
90 case OSPF6_TABLE_TYPE_SUMMARY_ROUTERS
:
91 snprintf (name
, sizeof (name
),
92 "area %s summary router table", oa
->name
);
95 snprintf (name
, sizeof (name
),
96 "area %s unknown table", oa
->name
);
102 case OSPF6_SCOPE_TYPE_INTERFACE
:
104 struct ospf6_interface
*oi
= (struct ospf6_interface
*) table
->scope
;
105 switch (table
->table_type
)
107 case OSPF6_TABLE_TYPE_CONNECTED_ROUTES
:
108 snprintf (name
, sizeof (name
), "interface %s connected table",
109 oi
->interface
->name
);
112 snprintf (name
, sizeof (name
), "interface %s unknown table",
113 oi
->interface
->name
);
121 switch (table
->table_type
)
123 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
124 snprintf (name
, sizeof (name
), "temporary spf table");
127 snprintf (name
, sizeof (name
), "temporary unknown table");
137 ospf6_linkstate_prefix (u_int32_t adv_router
, u_int32_t id
,
138 struct prefix
*prefix
)
140 memset (prefix
, 0, sizeof (struct prefix
));
141 prefix
->family
= AF_INET6
;
142 prefix
->prefixlen
= 64;
143 memcpy (&prefix
->u
.prefix6
.s6_addr
[0], &adv_router
, 4);
144 memcpy (&prefix
->u
.prefix6
.s6_addr
[4], &id
, 4);
148 ospf6_linkstate_prefix2str (struct prefix
*prefix
, char *buf
, int size
)
150 u_int32_t adv_router
, id
;
151 char adv_router_str
[16], id_str
[16];
152 memcpy (&adv_router
, &prefix
->u
.prefix6
.s6_addr
[0], 4);
153 memcpy (&id
, &prefix
->u
.prefix6
.s6_addr
[4], 4);
154 inet_ntop (AF_INET
, &adv_router
, adv_router_str
, sizeof (adv_router_str
));
155 inet_ntop (AF_INET
, &id
, id_str
, sizeof (id_str
));
157 snprintf (buf
, size
, "%s Net-ID: %s", adv_router_str
, id_str
);
159 snprintf (buf
, size
, "%s", adv_router_str
);
162 /* Global strings for logging */
163 const char *ospf6_dest_type_str
[OSPF6_DEST_TYPE_MAX
] =
164 { "Unknown", "Router", "Network", "Discard", "Linkstate", "AddressRange", };
166 const char *ospf6_dest_type_substr
[OSPF6_DEST_TYPE_MAX
] =
167 { "?", "R", "N", "D", "L", "A", };
169 const char *ospf6_path_type_str
[OSPF6_PATH_TYPE_MAX
] =
170 { "Unknown", "Intra-Area", "Inter-Area", "External-1", "External-2", };
172 const char *ospf6_path_type_substr
[OSPF6_PATH_TYPE_MAX
] =
173 { "??", "IA", "IE", "E1", "E2", };
176 struct ospf6_nexthop
*
177 ospf6_nexthop_create (void)
179 struct ospf6_nexthop
*nh
;
181 nh
= XCALLOC (MTYPE_OSPF6_NEXTHOP
, sizeof (struct ospf6_nexthop
));
186 ospf6_nexthop_delete (struct ospf6_nexthop
*nh
)
189 XFREE (MTYPE_OSPF6_NEXTHOP
, nh
);
193 ospf6_free_nexthops (struct list
*nh_list
)
195 struct ospf6_nexthop
*nh
;
196 struct listnode
*node
, *nnode
;
200 for (ALL_LIST_ELEMENTS (nh_list
, node
, nnode
, nh
))
201 ospf6_nexthop_delete (nh
);
206 ospf6_clear_nexthops (struct list
*nh_list
)
208 struct listnode
*node
;
209 struct ospf6_nexthop
*nh
;
213 for (ALL_LIST_ELEMENTS_RO (nh_list
, node
, nh
))
214 ospf6_nexthop_clear (nh
);
218 static struct ospf6_nexthop
*
219 ospf6_route_find_nexthop (struct list
*nh_list
, struct ospf6_nexthop
*nh_match
)
221 struct listnode
*node
;
222 struct ospf6_nexthop
*nh
;
224 if (nh_list
&& nh_match
)
226 for (ALL_LIST_ELEMENTS_RO (nh_list
, node
, nh
))
228 if (ospf6_nexthop_is_same (nh
, nh_match
))
237 ospf6_copy_nexthops (struct list
*dst
, struct list
*src
)
239 struct ospf6_nexthop
*nh_new
, *nh
;
240 struct listnode
*node
;
244 for (ALL_LIST_ELEMENTS_RO (src
, node
, nh
))
246 if (ospf6_nexthop_is_set (nh
))
248 nh_new
= ospf6_nexthop_create ();
249 ospf6_nexthop_copy (nh_new
, nh
);
250 listnode_add (dst
, nh_new
);
257 ospf6_merge_nexthops (struct list
*dst
, struct list
*src
)
259 struct listnode
*node
;
260 struct ospf6_nexthop
*nh
, *nh_new
;
264 for (ALL_LIST_ELEMENTS_RO (src
, node
, nh
))
266 if (!ospf6_route_find_nexthop (dst
, nh
))
268 nh_new
= ospf6_nexthop_create ();
269 ospf6_nexthop_copy (nh_new
, nh
);
270 listnode_add (dst
, nh_new
);
277 ospf6_route_cmp_nexthops (struct ospf6_route
*a
, struct ospf6_route
*b
)
279 struct listnode
*anode
, *bnode
;
280 struct ospf6_nexthop
*anh
, *bnh
;
284 if (listcount(a
->nh_list
) == listcount(b
->nh_list
))
286 for (ALL_LIST_ELEMENTS_RO (a
->nh_list
, anode
, anh
))
288 for (ALL_LIST_ELEMENTS_RO (b
->nh_list
, bnode
, bnh
))
289 if (!ospf6_nexthop_is_same (anh
, bnh
))
297 /* One of the routes doesn't exist ? */
302 ospf6_num_nexthops (struct list
*nh_list
)
304 return (listcount(nh_list
));
308 ospf6_add_nexthop (struct list
*nh_list
, int ifindex
,
309 struct in6_addr
*addr
)
311 struct ospf6_nexthop
*nh
;
312 struct ospf6_nexthop nh_match
;
316 nh_match
.ifindex
= ifindex
;
318 memcpy (&nh_match
.address
, addr
, sizeof (struct in6_addr
));
320 memset (&nh_match
.address
, 0, sizeof (struct in6_addr
));
322 if (!ospf6_route_find_nexthop (nh_list
, &nh_match
))
324 nh
= ospf6_nexthop_create();
325 ospf6_nexthop_copy (nh
, &nh_match
);
326 listnode_add (nh_list
, nh
);
332 ospf6_route_zebra_copy_nexthops (struct ospf6_route
*route
,
333 ifindex_t
*ifindexes
,
334 struct in6_addr
**nexthop_addr
,
337 struct ospf6_nexthop
*nh
;
338 struct listnode
*node
;
345 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
347 if (IS_OSPF6_DEBUG_ZEBRA (SEND
))
350 inet_ntop (AF_INET6
, &nh
->address
, buf
, sizeof (buf
));
351 ifname
= ifindex2ifname (nh
->ifindex
, VRF_DEFAULT
);
352 zlog_debug (" nexthop: %s%%%.*s(%d)", buf
, IFNAMSIZ
, ifname
,
357 nexthop_addr
[i
] = &nh
->address
;
358 ifindexes
[i
] = nh
->ifindex
;
370 ospf6_route_get_first_nh_index (struct ospf6_route
*route
)
372 struct ospf6_nexthop
*nh
;
376 if ((nh
= (struct ospf6_nexthop
*)listhead (route
->nh_list
)))
377 return (nh
->ifindex
);
384 ospf6_route_create (void)
386 struct ospf6_route
*route
;
387 route
= XCALLOC (MTYPE_OSPF6_ROUTE
, sizeof (struct ospf6_route
));
388 route
->nh_list
= list_new();
393 ospf6_route_delete (struct ospf6_route
*route
)
397 ospf6_free_nexthops (route
->nh_list
);
398 list_free (route
->nh_list
);
399 XFREE (MTYPE_OSPF6_ROUTE
, route
);
404 ospf6_route_copy (struct ospf6_route
*route
)
406 struct ospf6_route
*new;
408 new = ospf6_route_create ();
409 new->type
= route
->type
;
410 memcpy (&new->prefix
, &route
->prefix
, sizeof (struct prefix
));
411 new->installed
= route
->installed
;
412 new->changed
= route
->changed
;
413 new->flag
= route
->flag
;
414 new->route_option
= route
->route_option
;
415 new->linkstate_id
= route
->linkstate_id
;
416 new->path
= route
->path
;
417 ospf6_copy_nexthops (new->nh_list
, route
->nh_list
);
427 ospf6_route_lock (struct ospf6_route
*route
)
433 ospf6_route_unlock (struct ospf6_route
*route
)
435 assert (route
->lock
> 0);
437 if (route
->lock
== 0)
439 /* Can't detach from the table until here
440 because ospf6_route_next () will use
441 the 'route->table' pointer for logging */
443 ospf6_route_delete (route
);
447 /* Route compare function. If ra is more preferred, it returns
448 less than 0. If rb is more preferred returns greater than 0.
449 Otherwise (neither one is preferred), returns 0 */
451 ospf6_route_cmp (struct ospf6_route
*ra
, struct ospf6_route
*rb
)
453 assert (ospf6_route_is_same (ra
, rb
));
454 assert (OSPF6_PATH_TYPE_NONE
< ra
->path
.type
&&
455 ra
->path
.type
< OSPF6_PATH_TYPE_MAX
);
456 assert (OSPF6_PATH_TYPE_NONE
< rb
->path
.type
&&
457 rb
->path
.type
< OSPF6_PATH_TYPE_MAX
);
459 if (ra
->type
!= rb
->type
)
460 return (ra
->type
- rb
->type
);
462 if (ra
->path
.area_id
!= rb
->path
.area_id
)
463 return (ntohl (ra
->path
.area_id
) - ntohl (rb
->path
.area_id
));
465 if (ra
->path
.type
!= rb
->path
.type
)
466 return (ra
->path
.type
- rb
->path
.type
);
468 if (ra
->path
.type
== OSPF6_PATH_TYPE_EXTERNAL2
)
470 if (ra
->path
.u
.cost_e2
!= rb
->path
.u
.cost_e2
)
471 return (ra
->path
.u
.cost_e2
- rb
->path
.u
.cost_e2
);
475 if (ra
->path
.cost
!= rb
->path
.cost
)
476 return (ra
->path
.cost
- rb
->path
.cost
);
483 ospf6_route_lookup (struct prefix
*prefix
,
484 struct ospf6_route_table
*table
)
486 struct route_node
*node
;
487 struct ospf6_route
*route
;
489 node
= route_node_lookup (table
->table
, prefix
);
493 route
= (struct ospf6_route
*) node
->info
;
498 ospf6_route_lookup_identical (struct ospf6_route
*route
,
499 struct ospf6_route_table
*table
)
501 struct ospf6_route
*target
;
503 for (target
= ospf6_route_lookup (&route
->prefix
, table
);
504 target
; target
= target
->next
)
506 if (ospf6_route_is_identical (target
, route
))
513 ospf6_route_lookup_bestmatch (struct prefix
*prefix
,
514 struct ospf6_route_table
*table
)
516 struct route_node
*node
;
517 struct ospf6_route
*route
;
519 node
= route_node_match (table
->table
, prefix
);
522 route_unlock_node (node
);
524 route
= (struct ospf6_route
*) node
->info
;
530 route_table_assert (struct ospf6_route_table
*table
)
532 struct ospf6_route
*prev
, *r
, *next
;
533 char buf
[PREFIX2STR_BUFFER
];
534 unsigned int link_error
= 0, num
= 0;
536 r
= ospf6_route_head (table
);
543 next
= ospf6_route_next (r
);
552 for (r
= ospf6_route_head (table
); r
; r
= ospf6_route_next (r
))
555 if (link_error
== 0 && num
== table
->count
)
558 zlog_err ("PANIC !!");
559 zlog_err ("Something has gone wrong with ospf6_route_table[%p]", table
);
560 zlog_debug ("table count = %d, real number = %d", table
->count
, num
);
561 zlog_debug ("DUMP START");
562 for (r
= ospf6_route_head (table
); r
; r
= ospf6_route_next (r
))
564 prefix2str (&r
->prefix
, buf
, sizeof (buf
));
565 zlog_info ("%p<-[%p]->%p : %s", r
->prev
, r
, r
->next
, buf
);
567 zlog_debug ("DUMP END");
569 assert (link_error
== 0 && num
== table
->count
);
571 #define ospf6_route_table_assert(t) (route_table_assert (t))
573 #define ospf6_route_table_assert(t) ((void) 0)
577 ospf6_route_add (struct ospf6_route
*route
,
578 struct ospf6_route_table
*table
)
580 struct route_node
*node
, *nextnode
, *prevnode
;
581 struct ospf6_route
*current
= NULL
;
582 struct ospf6_route
*prev
= NULL
, *old
= NULL
, *next
= NULL
;
583 char buf
[PREFIX2STR_BUFFER
];
586 assert (route
->rnode
== NULL
);
587 assert (route
->lock
== 0);
588 assert (route
->next
== NULL
);
589 assert (route
->prev
== NULL
);
591 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
592 ospf6_linkstate_prefix2str (&route
->prefix
, buf
, sizeof (buf
));
594 prefix2str (&route
->prefix
, buf
, sizeof (buf
));
596 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
597 zlog_debug ("%s %p: route add %p: %s", ospf6_route_table_name (table
),
598 (void *)table
, (void *)route
, buf
);
599 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
600 zlog_debug ("%s: route add: %s", ospf6_route_table_name (table
), buf
);
604 node
= route_node_get (table
->table
, &route
->prefix
);
607 /* find place to insert */
608 for (current
= node
->info
; current
; current
= current
->next
)
610 if (! ospf6_route_is_same (current
, route
))
612 else if (current
->type
!= route
->type
)
614 else if (ospf6_route_is_same_origin (current
, route
))
616 else if (ospf6_route_cmp (current
, route
) > 0)
627 /* if route does not actually change, return unchanged */
628 if (ospf6_route_is_identical (old
, route
))
630 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
631 zlog_debug ("%s %p: route add %p: needless update of %p",
632 ospf6_route_table_name (table
),
633 (void *)table
, (void *)route
, (void *)old
);
634 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
635 zlog_debug ("%s: route add: needless update",
636 ospf6_route_table_name (table
));
638 ospf6_route_delete (route
);
639 SET_FLAG (old
->flag
, OSPF6_ROUTE_ADD
);
640 ospf6_route_table_assert (table
);
645 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
646 zlog_debug ("%s %p: route add %p: update of %p",
647 ospf6_route_table_name (table
),
648 (void *)table
, (void *)route
, (void *)old
);
649 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
650 zlog_debug ("%s: route add: update",
651 ospf6_route_table_name (table
));
653 /* replace old one if exists */
654 if (node
->info
== old
)
657 SET_FLAG (route
->flag
, OSPF6_ROUTE_BEST
);
661 old
->prev
->next
= route
;
662 route
->prev
= old
->prev
;
664 old
->next
->prev
= route
;
665 route
->next
= old
->next
;
667 route
->installed
= old
->installed
;
668 route
->changed
= now
;
669 assert (route
->table
== NULL
);
670 route
->table
= table
;
672 ospf6_route_unlock (old
); /* will be deleted later */
673 ospf6_route_lock (route
);
675 SET_FLAG (route
->flag
, OSPF6_ROUTE_CHANGE
);
676 ospf6_route_table_assert (table
);
679 (*table
->hook_add
) (route
);
684 /* insert if previous or next node found */
687 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
688 zlog_debug ("%s %p: route add %p: another path: prev %p, next %p",
689 ospf6_route_table_name (table
),
690 (void *)table
, (void *)route
, (void *)prev
, (void *)next
);
691 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
692 zlog_debug ("%s: route add: another path found",
693 ospf6_route_table_name (table
));
707 if (node
->info
== next
)
709 assert (next
->rnode
== node
);
711 UNSET_FLAG (next
->flag
, OSPF6_ROUTE_BEST
);
712 SET_FLAG (route
->flag
, OSPF6_ROUTE_BEST
);
713 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
714 zlog_info ("%s %p: route add %p: replacing previous best: %p",
715 ospf6_route_table_name (table
),
716 (void *)table
, (void *)route
, (void *)next
);
719 route
->installed
= now
;
720 route
->changed
= now
;
721 assert (route
->table
== NULL
);
722 route
->table
= table
;
724 ospf6_route_lock (route
);
726 ospf6_route_table_assert (table
);
728 SET_FLAG (route
->flag
, OSPF6_ROUTE_ADD
);
730 (*table
->hook_add
) (route
);
735 /* Else, this is the brand new route regarding to the prefix */
736 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
737 zlog_debug ("%s %p: route add %p: brand new route",
738 ospf6_route_table_name (table
), (void *)table
, (void *)route
);
739 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
740 zlog_debug ("%s: route add: brand new route",
741 ospf6_route_table_name (table
));
743 assert (node
->info
== NULL
);
745 SET_FLAG (route
->flag
, OSPF6_ROUTE_BEST
);
746 ospf6_route_lock (route
);
747 route
->installed
= now
;
748 route
->changed
= now
;
749 assert (route
->table
== NULL
);
750 route
->table
= table
;
752 /* lookup real existing next route */
754 route_lock_node (nextnode
);
756 nextnode
= route_next (nextnode
);
757 } while (nextnode
&& nextnode
->info
== NULL
);
760 if (nextnode
== NULL
)
764 route_unlock_node (nextnode
);
766 next
= nextnode
->info
;
771 /* lookup real existing prev route */
773 route_lock_node (prevnode
);
775 prevnode
= route_prev (prevnode
);
776 } while (prevnode
&& prevnode
->info
== NULL
);
779 if (prevnode
== NULL
)
783 route_unlock_node (prevnode
);
785 prev
= prevnode
->info
;
786 while (prev
->next
&& ospf6_route_is_same (prev
, prev
->next
))
793 ospf6_route_table_assert (table
);
795 SET_FLAG (route
->flag
, OSPF6_ROUTE_ADD
);
797 (*table
->hook_add
) (route
);
803 ospf6_route_remove (struct ospf6_route
*route
,
804 struct ospf6_route_table
*table
)
806 struct route_node
*node
;
807 struct ospf6_route
*current
;
808 char buf
[PREFIX2STR_BUFFER
];
810 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
811 ospf6_linkstate_prefix2str (&route
->prefix
, buf
, sizeof (buf
));
813 prefix2str (&route
->prefix
, buf
, sizeof (buf
));
815 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
816 zlog_debug ("%s %p: route remove %p: %s",
817 ospf6_route_table_name (table
),
818 (void *)table
, (void *)route
, buf
);
819 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
820 zlog_debug ("%s: route remove: %s", ospf6_route_table_name (table
), buf
);
822 node
= route_node_lookup (table
->table
, &route
->prefix
);
825 /* find the route to remove, making sure that the route pointer
826 is from the route table. */
827 current
= node
->info
;
828 while (current
&& ospf6_route_is_same (current
, route
))
830 if (current
== route
)
832 current
= current
->next
;
834 assert (current
== route
);
836 /* adjust doubly linked list */
838 route
->prev
->next
= route
->next
;
840 route
->next
->prev
= route
->prev
;
842 if (node
->info
== route
)
844 if (route
->next
&& route
->next
->rnode
== node
)
846 node
->info
= route
->next
;
847 SET_FLAG (route
->next
->flag
, OSPF6_ROUTE_BEST
);
850 node
->info
= NULL
; /* should unlock route_node here ? */
854 ospf6_route_table_assert (table
);
856 SET_FLAG (route
->flag
, OSPF6_ROUTE_WAS_REMOVED
);
858 if (table
->hook_remove
)
859 (*table
->hook_remove
) (route
);
861 ospf6_route_unlock (route
);
865 ospf6_route_head (struct ospf6_route_table
*table
)
867 struct route_node
*node
;
868 struct ospf6_route
*route
;
870 node
= route_top (table
->table
);
874 /* skip to the real existing entry */
875 while (node
&& node
->info
== NULL
)
876 node
= route_next (node
);
880 route_unlock_node (node
);
883 route
= (struct ospf6_route
*) node
->info
;
884 assert (route
->prev
== NULL
);
885 assert (route
->table
== table
);
886 ospf6_route_lock (route
);
888 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
889 zlog_info ("%s %p: route head: %p<-[%p]->%p",
890 ospf6_route_table_name (table
), (void *)table
,
891 (void *)route
->prev
, (void *)route
, (void *)route
->next
);
897 ospf6_route_next (struct ospf6_route
*route
)
899 struct ospf6_route
*next
= route
->next
;
901 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
902 zlog_info ("%s %p: route next: %p<-[%p]->%p",
903 ospf6_route_table_name (route
->table
), (void *)route
->table
,
904 (void *)route
->prev
, (void *)route
, (void *)route
->next
);
906 ospf6_route_unlock (route
);
908 ospf6_route_lock (next
);
914 ospf6_route_best_next (struct ospf6_route
*route
)
916 struct route_node
*rnode
;
917 struct ospf6_route
*next
;
919 ospf6_route_unlock (route
);
921 rnode
= route
->rnode
;
922 route_lock_node (rnode
);
923 rnode
= route_next (rnode
);
924 while (rnode
&& rnode
->info
== NULL
)
925 rnode
= route_next (rnode
);
928 route_unlock_node (rnode
);
930 assert (rnode
->info
);
931 next
= (struct ospf6_route
*) rnode
->info
;
932 ospf6_route_lock (next
);
937 ospf6_route_match_head (struct prefix
*prefix
,
938 struct ospf6_route_table
*table
)
940 struct route_node
*node
;
941 struct ospf6_route
*route
;
943 /* Walk down tree. */
944 node
= table
->table
->top
;
945 while (node
&& node
->p
.prefixlen
< prefix
->prefixlen
&&
946 prefix_match (&node
->p
, prefix
))
947 node
= node
->link
[prefix_bit(&prefix
->u
.prefix
, node
->p
.prefixlen
)];
950 route_lock_node (node
);
951 while (node
&& node
->info
== NULL
)
952 node
= route_next (node
);
955 route_unlock_node (node
);
957 if (! prefix_match (prefix
, &node
->p
))
961 ospf6_route_lock (route
);
966 ospf6_route_match_next (struct prefix
*prefix
,
967 struct ospf6_route
*route
)
969 struct ospf6_route
*next
;
971 next
= ospf6_route_next (route
);
972 if (next
&& ! prefix_match (prefix
, &next
->prefix
))
974 ospf6_route_unlock (next
);
982 ospf6_route_remove_all (struct ospf6_route_table
*table
)
984 struct ospf6_route
*route
;
985 for (route
= ospf6_route_head (table
); route
;
986 route
= ospf6_route_next (route
))
987 ospf6_route_remove (route
, table
);
990 struct ospf6_route_table
*
991 ospf6_route_table_create (int s
, int t
)
993 struct ospf6_route_table
*new;
994 new = XCALLOC (MTYPE_OSPF6_ROUTE
, sizeof (struct ospf6_route_table
));
995 new->table
= route_table_init ();
1002 ospf6_route_table_delete (struct ospf6_route_table
*table
)
1004 ospf6_route_remove_all (table
);
1005 route_table_finish (table
->table
);
1006 XFREE (MTYPE_OSPF6_ROUTE
, table
);
1012 ospf6_route_show (struct vty
*vty
, struct ospf6_route
*route
)
1015 char destination
[PREFIX2STR_BUFFER
], nexthop
[64];
1018 struct timeval now
, res
;
1019 struct listnode
*node
;
1020 struct ospf6_nexthop
*nh
;
1023 timersub (&now
, &route
->changed
, &res
);
1024 timerstring (&res
, duration
, sizeof (duration
));
1027 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
1028 ospf6_linkstate_prefix2str (&route
->prefix
, destination
,
1029 sizeof (destination
));
1030 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
1031 inet_ntop (route
->prefix
.family
, &route
->prefix
.u
.prefix
,
1032 destination
, sizeof (destination
));
1034 prefix2str (&route
->prefix
, destination
, sizeof (destination
));
1037 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
1040 inet_ntop (AF_INET6
, &nh
->address
, nexthop
,
1042 ifname
= ifindex2ifname (nh
->ifindex
, VRF_DEFAULT
);
1046 vty_out (vty
, "%c%1s %2s %-30s %-25s %6.*s %s%s",
1047 (ospf6_route_is_best (route
) ? '*' : ' '),
1048 OSPF6_DEST_TYPE_SUBSTR (route
->type
),
1049 OSPF6_PATH_TYPE_SUBSTR (route
->path
.type
),
1050 destination
, nexthop
, IFNAMSIZ
, ifname
, duration
, VNL
);
1054 vty_out (vty
, "%c%1s %2s %-30s %-25s %6.*s %s%s",
1055 ' ', "", "", "", nexthop
, IFNAMSIZ
, ifname
, "", VNL
);
1060 ospf6_route_show_detail (struct vty
*vty
, struct ospf6_route
*route
)
1063 char destination
[PREFIX2STR_BUFFER
], nexthop
[64];
1064 char area_id
[16], id
[16], adv_router
[16], capa
[16], options
[16];
1065 struct timeval now
, res
;
1067 struct listnode
*node
;
1068 struct ospf6_nexthop
*nh
;
1073 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
1074 ospf6_linkstate_prefix2str (&route
->prefix
, destination
,
1075 sizeof (destination
));
1076 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
1077 inet_ntop (route
->prefix
.family
, &route
->prefix
.u
.prefix
,
1078 destination
, sizeof (destination
));
1080 prefix2str (&route
->prefix
, destination
, sizeof (destination
));
1081 vty_out (vty
, "Destination: %s%s", destination
, VNL
);
1083 /* destination type */
1084 vty_out (vty
, "Destination type: %s%s",
1085 OSPF6_DEST_TYPE_NAME (route
->type
),
1089 timersub (&now
, &route
->installed
, &res
);
1090 timerstring (&res
, duration
, sizeof (duration
));
1091 vty_out (vty
, "Installed Time: %s ago%s", duration
, VNL
);
1093 timersub (&now
, &route
->changed
, &res
);
1094 timerstring (&res
, duration
, sizeof (duration
));
1095 vty_out (vty
, " Changed Time: %s ago%s", duration
, VNL
);
1097 /* Debugging info */
1098 vty_out (vty
, "Lock: %d Flags: %s%s%s%s%s", route
->lock
,
1099 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_BEST
) ? "B" : "-"),
1100 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_ADD
) ? "A" : "-"),
1101 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_REMOVE
) ? "R" : "-"),
1102 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_CHANGE
) ? "C" : "-"),
1104 vty_out (vty
, "Memory: prev: %p this: %p next: %p%s",
1105 (void *)route
->prev
, (void *)route
, (void *)route
->next
, VNL
);
1110 inet_ntop (AF_INET
, &route
->path
.area_id
, area_id
, sizeof (area_id
));
1111 vty_out (vty
, "Associated Area: %s%s", area_id
, VNL
);
1114 vty_out (vty
, "Path Type: %s%s",
1115 OSPF6_PATH_TYPE_NAME (route
->path
.type
), VNL
);
1118 inet_ntop (AF_INET
, &route
->path
.origin
.id
, id
, sizeof (id
));
1119 inet_ntop (AF_INET
, &route
->path
.origin
.adv_router
, adv_router
,
1120 sizeof (adv_router
));
1121 vty_out (vty
, "LS Origin: %s Id: %s Adv: %s%s",
1122 ospf6_lstype_name (route
->path
.origin
.type
),
1123 id
, adv_router
, VNL
);
1126 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1127 vty_out (vty
, "Options: %s%s", options
, VNL
);
1130 ospf6_capability_printbuf (route
->path
.router_bits
, capa
, sizeof (capa
));
1131 vty_out (vty
, "Router Bits: %s%s", capa
, VNL
);
1133 /* Prefix Options */
1134 vty_out (vty
, "Prefix Options: xxx%s", VNL
);
1137 vty_out (vty
, "Metric Type: %d%s", route
->path
.metric_type
,
1139 vty_out (vty
, "Metric: %d (%d)%s",
1140 route
->path
.cost
, route
->path
.u
.cost_e2
, VNL
);
1143 vty_out (vty
, "Nexthop:%s", VNL
);
1144 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
1147 inet_ntop (AF_INET6
, &nh
->address
, nexthop
, sizeof (nexthop
));
1148 ifname
= ifindex2ifname (nh
->ifindex
, VRF_DEFAULT
);
1149 vty_out (vty
, " %s %.*s%s", nexthop
, IFNAMSIZ
, ifname
, VNL
);
1151 vty_out (vty
, "%s", VNL
);
1155 ospf6_route_show_table_summary (struct vty
*vty
,
1156 struct ospf6_route_table
*table
)
1158 struct ospf6_route
*route
, *prev
= NULL
;
1159 int i
, pathtype
[OSPF6_PATH_TYPE_MAX
];
1160 unsigned int number
= 0;
1161 int nh_count
=0 , nhinval
= 0, ecmp
= 0;
1162 int alternative
= 0, destination
= 0;
1164 for (i
= 0; i
< OSPF6_PATH_TYPE_MAX
; i
++)
1167 for (route
= ospf6_route_head (table
); route
;
1168 route
= ospf6_route_next (route
))
1170 if (prev
== NULL
|| ! ospf6_route_is_same (prev
, route
))
1174 nh_count
= ospf6_num_nexthops (route
->nh_list
);
1177 else if (nh_count
> 1)
1179 pathtype
[route
->path
.type
]++;
1185 assert (number
== table
->count
);
1187 vty_out (vty
, "Number of OSPFv3 routes: %d%s", number
, VNL
);
1188 vty_out (vty
, "Number of Destination: %d%s", destination
, VNL
);
1189 vty_out (vty
, "Number of Alternative routes: %d%s", alternative
, VNL
);
1190 vty_out (vty
, "Number of Equal Cost Multi Path: %d%s", ecmp
, VNL
);
1191 for (i
= OSPF6_PATH_TYPE_INTRA
; i
<= OSPF6_PATH_TYPE_EXTERNAL2
; i
++)
1193 vty_out (vty
, "Number of %s routes: %d%s",
1194 OSPF6_PATH_TYPE_NAME (i
), pathtype
[i
], VNL
);
1199 ospf6_route_show_table_prefix (struct vty
*vty
,
1200 struct prefix
*prefix
,
1201 struct ospf6_route_table
*table
)
1203 struct ospf6_route
*route
;
1205 route
= ospf6_route_lookup (prefix
, table
);
1209 ospf6_route_lock (route
);
1210 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1212 /* Specifying a prefix will always display details */
1213 ospf6_route_show_detail (vty
, route
);
1214 route
= ospf6_route_next (route
);
1217 ospf6_route_unlock (route
);
1221 ospf6_route_show_table_address (struct vty
*vty
,
1222 struct prefix
*prefix
,
1223 struct ospf6_route_table
*table
)
1225 struct ospf6_route
*route
;
1227 route
= ospf6_route_lookup_bestmatch (prefix
, table
);
1231 prefix
= &route
->prefix
;
1232 ospf6_route_lock (route
);
1233 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1235 /* Specifying a prefix will always display details */
1236 ospf6_route_show_detail (vty
, route
);
1237 route
= ospf6_route_next (route
);
1240 ospf6_route_unlock (route
);
1244 ospf6_route_show_table_match (struct vty
*vty
, int detail
,
1245 struct prefix
*prefix
,
1246 struct ospf6_route_table
*table
)
1248 struct ospf6_route
*route
;
1249 assert (prefix
->family
);
1251 route
= ospf6_route_match_head (prefix
, table
);
1255 ospf6_route_show_detail (vty
, route
);
1257 ospf6_route_show (vty
, route
);
1258 route
= ospf6_route_match_next (prefix
, route
);
1263 ospf6_route_show_table_type (struct vty
*vty
, int detail
, u_char type
,
1264 struct ospf6_route_table
*table
)
1266 struct ospf6_route
*route
;
1268 route
= ospf6_route_head (table
);
1271 if (route
->path
.type
== type
)
1274 ospf6_route_show_detail (vty
, route
);
1276 ospf6_route_show (vty
, route
);
1278 route
= ospf6_route_next (route
);
1283 ospf6_route_show_table (struct vty
*vty
, int detail
,
1284 struct ospf6_route_table
*table
)
1286 struct ospf6_route
*route
;
1288 route
= ospf6_route_head (table
);
1292 ospf6_route_show_detail (vty
, route
);
1294 ospf6_route_show (vty
, route
);
1295 route
= ospf6_route_next (route
);
1300 ospf6_route_table_show (struct vty
*vty
, int argc_start
, int argc
, struct cmd_token
**argv
,
1301 struct ospf6_route_table
*table
)
1309 struct prefix prefix
;
1312 memset (&prefix
, 0, sizeof (struct prefix
));
1314 for (i
= argc_start
; i
< argc
; i
++)
1316 if (! strcmp (argv
[i
]->arg
, "summary"))
1322 if (! strcmp (argv
[i
]->arg
, "intra-area"))
1324 type
= OSPF6_PATH_TYPE_INTRA
;
1328 if (! strcmp (argv
[i
]->arg
, "inter-area"))
1330 type
= OSPF6_PATH_TYPE_INTER
;
1334 if (! strcmp (argv
[i
]->arg
, "external-1"))
1336 type
= OSPF6_PATH_TYPE_EXTERNAL1
;
1340 if (! strcmp (argv
[i
]->arg
, "external-2"))
1342 type
= OSPF6_PATH_TYPE_EXTERNAL2
;
1346 if (! strcmp (argv
[i
]->arg
, "detail"))
1352 if (! strcmp (argv
[i
]->arg
, "match"))
1358 ret
= str2prefix (argv
[i
]->arg
, &prefix
);
1359 if (ret
== 1 && prefix
.family
== AF_INET6
)
1362 if (strchr (argv
[i
]->arg
, '/'))
1367 vty_out (vty
, "Malformed argument: %s%s", argv
[i
]->arg
, VNL
);
1371 /* Give summary of this route table */
1374 ospf6_route_show_table_summary (vty
, table
);
1378 /* Give exact prefix-match route */
1379 if (isprefix
&& ! match
)
1381 /* If exact address, give best matching route */
1383 ospf6_route_show_table_address (vty
, &prefix
, table
);
1385 ospf6_route_show_table_prefix (vty
, &prefix
, table
);
1391 ospf6_route_show_table_match (vty
, detail
, &prefix
, table
);
1393 ospf6_route_show_table_type (vty
, detail
, type
, table
);
1395 ospf6_route_show_table (vty
, detail
, table
);
1401 ospf6_linkstate_show_header (struct vty
*vty
)
1403 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %s%s",
1404 "Type", "Router-ID", "Net-ID", "Rtr-Bits", "Options", "Cost", VNL
);
1408 ospf6_linkstate_show (struct vty
*vty
, struct ospf6_route
*route
)
1410 u_int32_t router
, id
;
1411 char routername
[16], idname
[16], rbits
[16], options
[16];
1413 router
= ospf6_linkstate_prefix_adv_router (&route
->prefix
);
1414 inet_ntop (AF_INET
, &router
, routername
, sizeof (routername
));
1415 id
= ospf6_linkstate_prefix_id (&route
->prefix
);
1416 inet_ntop (AF_INET
, &id
, idname
, sizeof (idname
));
1418 ospf6_capability_printbuf (route
->path
.router_bits
, rbits
, sizeof (rbits
));
1419 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1422 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %lu%s",
1423 "Network", routername
, idname
, rbits
, options
,
1424 (unsigned long) route
->path
.cost
, VNL
);
1426 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %lu%s",
1427 "Router", routername
, idname
, rbits
, options
,
1428 (unsigned long) route
->path
.cost
, VNL
);
1433 ospf6_linkstate_show_table_exact (struct vty
*vty
,
1434 struct prefix
*prefix
,
1435 struct ospf6_route_table
*table
)
1437 struct ospf6_route
*route
;
1439 route
= ospf6_route_lookup (prefix
, table
);
1443 ospf6_route_lock (route
);
1444 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1446 /* Specifying a prefix will always display details */
1447 ospf6_route_show_detail (vty
, route
);
1448 route
= ospf6_route_next (route
);
1451 ospf6_route_unlock (route
);
1455 ospf6_linkstate_show_table (struct vty
*vty
, int detail
,
1456 struct ospf6_route_table
*table
)
1458 struct ospf6_route
*route
;
1461 ospf6_linkstate_show_header (vty
);
1463 route
= ospf6_route_head (table
);
1467 ospf6_route_show_detail (vty
, route
);
1469 ospf6_linkstate_show (vty
, route
);
1470 route
= ospf6_route_next (route
);
1475 ospf6_linkstate_table_show (struct vty
*vty
, int idx_ipv4
, int argc
,
1476 struct cmd_token
**argv
,
1477 struct ospf6_route_table
*table
)
1483 struct prefix router
, id
, prefix
;
1485 memset (&router
, 0, sizeof (struct prefix
));
1486 memset (&id
, 0, sizeof (struct prefix
));
1487 memset (&prefix
, 0, sizeof (struct prefix
));
1489 for (i
= idx_ipv4
; i
< argc
; i
++)
1491 if (! strcmp (argv
[i
]->arg
, "detail"))
1499 ret
= str2prefix (argv
[i
]->arg
, &router
);
1500 if (ret
== 1 && router
.family
== AF_INET
)
1505 vty_out (vty
, "Malformed argument: %s%s", argv
[i
]->arg
, VNL
);
1511 ret
= str2prefix (argv
[i
]->arg
, &id
);
1512 if (ret
== 1 && id
.family
== AF_INET
)
1517 vty_out (vty
, "Malformed argument: %s%s", argv
[i
]->arg
, VNL
);
1521 vty_out (vty
, "Malformed argument: %s%s", argv
[i
]->arg
, VNL
);
1526 ospf6_linkstate_prefix (router
.u
.prefix4
.s_addr
,
1527 id
.u
.prefix4
.s_addr
, &prefix
);
1530 ospf6_linkstate_show_table_exact (vty
, &prefix
, table
);
1532 ospf6_linkstate_show_table (vty
, detail
, table
);
1539 ospf6_brouter_show_header (struct vty
*vty
)
1541 vty_out (vty
, "%-15s %-8s %-14s %-10s %-15s%s",
1542 "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area", VNL
);
1546 ospf6_brouter_show (struct vty
*vty
, struct ospf6_route
*route
)
1548 u_int32_t adv_router
;
1549 char adv
[16], rbits
[16], options
[16], area
[16];
1551 adv_router
= ospf6_linkstate_prefix_adv_router (&route
->prefix
);
1552 inet_ntop (AF_INET
, &adv_router
, adv
, sizeof (adv
));
1553 ospf6_capability_printbuf (route
->path
.router_bits
, rbits
, sizeof (rbits
));
1554 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1555 inet_ntop (AF_INET
, &route
->path
.area_id
, area
, sizeof (area
));
1557 /* vty_out (vty, "%-15s %-8s %-14s %-10s %-15s%s",
1558 "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area", VNL); */
1559 vty_out (vty
, "%-15s %-8s %-14s %-10s %-15s%s",
1560 adv
, rbits
, options
, OSPF6_PATH_TYPE_NAME (route
->path
.type
),
1564 DEFUN (debug_ospf6_route
,
1565 debug_ospf6_route_cmd
,
1566 "debug ospf6 route <table|intra-area|inter-area|memory>",
1570 "Debug route table calculation\n"
1571 "Debug intra-area route calculation\n"
1572 "Debug inter-area route calculation\n"
1573 "Debug route memory use\n"
1577 unsigned char level
= 0;
1579 if (! strncmp (argv
[idx_type
]->arg
, "table", 5))
1580 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1581 else if (! strncmp (argv
[idx_type
]->arg
, "intra", 5))
1582 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1583 else if (! strncmp (argv
[idx_type
]->arg
, "inter", 5))
1584 level
= OSPF6_DEBUG_ROUTE_INTER
;
1585 else if (! strncmp (argv
[idx_type
]->arg
, "memor", 5))
1586 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1587 OSPF6_DEBUG_ROUTE_ON (level
);
1591 DEFUN (no_debug_ospf6_route
,
1592 no_debug_ospf6_route_cmd
,
1593 "no debug ospf6 route <table|intra-area|inter-area|memory>",
1598 "Debug route table calculation\n"
1599 "Debug intra-area route calculation\n"
1600 "Debug inter-area route calculation\n"
1601 "Debug route memory use\n")
1604 unsigned char level
= 0;
1606 if (! strncmp (argv
[idx_type
]->arg
, "table", 5))
1607 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1608 else if (! strncmp (argv
[idx_type
]->arg
, "intra", 5))
1609 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1610 else if (! strncmp (argv
[idx_type
]->arg
, "inter", 5))
1611 level
= OSPF6_DEBUG_ROUTE_INTER
;
1612 else if (! strncmp (argv
[idx_type
]->arg
, "memor", 5))
1613 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1614 OSPF6_DEBUG_ROUTE_OFF (level
);
1619 config_write_ospf6_debug_route (struct vty
*vty
)
1621 if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
1622 vty_out (vty
, "debug ospf6 route table%s", VNL
);
1623 if (IS_OSPF6_DEBUG_ROUTE (INTRA
))
1624 vty_out (vty
, "debug ospf6 route intra-area%s", VNL
);
1625 if (IS_OSPF6_DEBUG_ROUTE (INTER
))
1626 vty_out (vty
, "debug ospf6 route inter-area%s", VNL
);
1631 install_element_ospf6_debug_route (void)
1633 install_element (ENABLE_NODE
, &debug_ospf6_route_cmd
);
1634 install_element (ENABLE_NODE
, &no_debug_ospf6_route_cmd
);
1635 install_element (CONFIG_NODE
, &debug_ospf6_route_cmd
);
1636 install_element (CONFIG_NODE
, &no_debug_ospf6_route_cmd
);