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
17 * along with GNU Zebra; see the file COPYING. If not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
32 #include "ospf6_proto.h"
33 #include "ospf6_lsa.h"
34 #include "ospf6_lsdb.h"
35 #include "ospf6_route.h"
36 #include "ospf6_top.h"
37 #include "ospf6_area.h"
38 #include "ospf6_interface.h"
40 #include "ospf6_zebra.h"
42 unsigned char conf_debug_ospf6_route
= 0;
45 ospf6_route_table_name (struct ospf6_route_table
*table
)
48 switch (table
->scope_type
)
50 case OSPF6_SCOPE_TYPE_GLOBAL
:
52 switch (table
->table_type
)
54 case OSPF6_TABLE_TYPE_ROUTES
:
55 snprintf (name
, sizeof (name
), "global route table");
57 case OSPF6_TABLE_TYPE_BORDER_ROUTERS
:
58 snprintf (name
, sizeof (name
), "global brouter table");
60 case OSPF6_TABLE_TYPE_EXTERNAL_ROUTES
:
61 snprintf (name
, sizeof (name
), "global external table");
64 snprintf (name
, sizeof (name
), "global unknown table");
70 case OSPF6_SCOPE_TYPE_AREA
:
72 struct ospf6_area
*oa
= (struct ospf6_area
*) table
->scope
;
73 switch (table
->table_type
)
75 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
76 snprintf (name
, sizeof (name
),
77 "area %s spf table", oa
->name
);
79 case OSPF6_TABLE_TYPE_ROUTES
:
80 snprintf (name
, sizeof (name
),
81 "area %s route table", oa
->name
);
83 case OSPF6_TABLE_TYPE_PREFIX_RANGES
:
84 snprintf (name
, sizeof (name
),
85 "area %s range table", oa
->name
);
87 case OSPF6_TABLE_TYPE_SUMMARY_PREFIXES
:
88 snprintf (name
, sizeof (name
),
89 "area %s summary prefix table", oa
->name
);
91 case OSPF6_TABLE_TYPE_SUMMARY_ROUTERS
:
92 snprintf (name
, sizeof (name
),
93 "area %s summary router table", oa
->name
);
96 snprintf (name
, sizeof (name
),
97 "area %s unknown table", oa
->name
);
103 case OSPF6_SCOPE_TYPE_INTERFACE
:
105 struct ospf6_interface
*oi
= (struct ospf6_interface
*) table
->scope
;
106 switch (table
->table_type
)
108 case OSPF6_TABLE_TYPE_CONNECTED_ROUTES
:
109 snprintf (name
, sizeof (name
), "interface %s connected table",
110 oi
->interface
->name
);
113 snprintf (name
, sizeof (name
), "interface %s unknown table",
114 oi
->interface
->name
);
122 switch (table
->table_type
)
124 case OSPF6_TABLE_TYPE_SPF_RESULTS
:
125 snprintf (name
, sizeof (name
), "temporary spf table");
128 snprintf (name
, sizeof (name
), "temporary unknown table");
138 ospf6_linkstate_prefix (u_int32_t adv_router
, u_int32_t id
,
139 struct prefix
*prefix
)
141 memset (prefix
, 0, sizeof (struct prefix
));
142 prefix
->family
= AF_INET6
;
143 prefix
->prefixlen
= 64;
144 memcpy (&prefix
->u
.prefix6
.s6_addr
[0], &adv_router
, 4);
145 memcpy (&prefix
->u
.prefix6
.s6_addr
[4], &id
, 4);
149 ospf6_linkstate_prefix2str (struct prefix
*prefix
, char *buf
, int size
)
151 u_int32_t adv_router
, id
;
152 char adv_router_str
[16], id_str
[16];
153 memcpy (&adv_router
, &prefix
->u
.prefix6
.s6_addr
[0], 4);
154 memcpy (&id
, &prefix
->u
.prefix6
.s6_addr
[4], 4);
155 inet_ntop (AF_INET
, &adv_router
, adv_router_str
, sizeof (adv_router_str
));
156 inet_ntop (AF_INET
, &id
, id_str
, sizeof (id_str
));
158 snprintf (buf
, size
, "%s Net-ID: %s", adv_router_str
, id_str
);
160 snprintf (buf
, size
, "%s", adv_router_str
);
163 /* Global strings for logging */
164 const char *ospf6_dest_type_str
[OSPF6_DEST_TYPE_MAX
] =
165 { "Unknown", "Router", "Network", "Discard", "Linkstate", "AddressRange", };
167 const char *ospf6_dest_type_substr
[OSPF6_DEST_TYPE_MAX
] =
168 { "?", "R", "N", "D", "L", "A", };
170 const char *ospf6_path_type_str
[OSPF6_PATH_TYPE_MAX
] =
171 { "Unknown", "Intra-Area", "Inter-Area", "External-1", "External-2", };
173 const char *ospf6_path_type_substr
[OSPF6_PATH_TYPE_MAX
] =
174 { "??", "IA", "IE", "E1", "E2", };
177 struct ospf6_nexthop
*
178 ospf6_nexthop_create (void)
180 struct ospf6_nexthop
*nh
;
182 nh
= XCALLOC (MTYPE_OSPF6_NEXTHOP
, sizeof (struct ospf6_nexthop
));
187 ospf6_nexthop_delete (struct ospf6_nexthop
*nh
)
190 XFREE (MTYPE_OSPF6_NEXTHOP
, nh
);
194 ospf6_free_nexthops (struct list
*nh_list
)
196 struct ospf6_nexthop
*nh
;
197 struct listnode
*node
, *nnode
;
201 for (ALL_LIST_ELEMENTS (nh_list
, node
, nnode
, nh
))
202 ospf6_nexthop_delete (nh
);
207 ospf6_clear_nexthops (struct list
*nh_list
)
209 struct listnode
*node
;
210 struct ospf6_nexthop
*nh
;
214 for (ALL_LIST_ELEMENTS_RO (nh_list
, node
, nh
))
215 ospf6_nexthop_clear (nh
);
219 static struct ospf6_nexthop
*
220 ospf6_route_find_nexthop (struct list
*nh_list
, struct ospf6_nexthop
*nh_match
)
222 struct listnode
*node
;
223 struct ospf6_nexthop
*nh
;
225 if (nh_list
&& nh_match
)
227 for (ALL_LIST_ELEMENTS_RO (nh_list
, node
, nh
))
229 if (ospf6_nexthop_is_same (nh
, nh_match
))
238 ospf6_copy_nexthops (struct list
*dst
, struct list
*src
)
240 struct ospf6_nexthop
*nh_new
, *nh
;
241 struct listnode
*node
;
245 for (ALL_LIST_ELEMENTS_RO (src
, node
, nh
))
247 if (ospf6_nexthop_is_set (nh
))
249 nh_new
= ospf6_nexthop_create ();
250 ospf6_nexthop_copy (nh_new
, nh
);
251 listnode_add (dst
, nh_new
);
258 ospf6_merge_nexthops (struct list
*dst
, struct list
*src
)
260 struct listnode
*node
;
261 struct ospf6_nexthop
*nh
, *nh_new
;
265 for (ALL_LIST_ELEMENTS_RO (src
, node
, nh
))
267 if (!ospf6_route_find_nexthop (dst
, nh
))
269 nh_new
= ospf6_nexthop_create ();
270 ospf6_nexthop_copy (nh_new
, nh
);
271 listnode_add (dst
, nh_new
);
278 ospf6_route_cmp_nexthops (struct ospf6_route
*a
, struct ospf6_route
*b
)
280 struct listnode
*anode
, *bnode
;
281 struct ospf6_nexthop
*anh
, *bnh
;
285 if (listcount(a
->nh_list
) == listcount(b
->nh_list
))
287 for (ALL_LIST_ELEMENTS_RO (a
->nh_list
, anode
, anh
))
289 for (ALL_LIST_ELEMENTS_RO (b
->nh_list
, bnode
, bnh
))
290 if (!ospf6_nexthop_is_same (anh
, bnh
))
298 /* One of the routes doesn't exist ? */
303 ospf6_num_nexthops (struct list
*nh_list
)
305 return (listcount(nh_list
));
309 ospf6_add_nexthop (struct list
*nh_list
, int ifindex
,
310 struct in6_addr
*addr
)
312 struct ospf6_nexthop
*nh
;
313 struct ospf6_nexthop nh_match
;
317 nh_match
.ifindex
= ifindex
;
319 memcpy (&nh_match
.address
, addr
, sizeof (struct in6_addr
));
321 memset (&nh_match
.address
, 0, sizeof (struct in6_addr
));
323 if (!ospf6_route_find_nexthop (nh_list
, &nh_match
))
325 nh
= ospf6_nexthop_create();
326 ospf6_nexthop_copy (nh
, &nh_match
);
327 listnode_add (nh_list
, nh
);
333 ospf6_route_zebra_copy_nexthops (struct ospf6_route
*route
,
334 unsigned int *ifindexes
,
335 struct in6_addr
**nexthop_addr
,
338 struct ospf6_nexthop
*nh
;
339 struct listnode
*node
;
346 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
348 if (IS_OSPF6_DEBUG_ZEBRA (SEND
))
350 char ifname
[IFNAMSIZ
];
351 inet_ntop (AF_INET6
, &nh
->address
, buf
, sizeof (buf
));
352 if (!if_indextoname(nh
->ifindex
, ifname
))
353 strlcpy(ifname
, "unknown", sizeof(ifname
));
354 zlog_debug (" nexthop: %s%%%.*s(%d)", buf
, IFNAMSIZ
, ifname
,
359 nexthop_addr
[i
] = &nh
->address
;
360 ifindexes
[i
] = nh
->ifindex
;
372 ospf6_route_get_first_nh_index (struct ospf6_route
*route
)
374 struct ospf6_nexthop
*nh
;
378 if (nh
= (struct ospf6_nexthop
*)listhead (route
->nh_list
))
379 return (nh
->ifindex
);
386 ospf6_route_create (void)
388 struct ospf6_route
*route
;
389 route
= XCALLOC (MTYPE_OSPF6_ROUTE
, sizeof (struct ospf6_route
));
390 route
->nh_list
= list_new();
395 ospf6_route_delete (struct ospf6_route
*route
)
399 ospf6_free_nexthops (route
->nh_list
);
400 list_free (route
->nh_list
);
401 XFREE (MTYPE_OSPF6_ROUTE
, route
);
406 ospf6_route_copy (struct ospf6_route
*route
)
408 struct ospf6_route
*new;
410 new = ospf6_route_create ();
411 new->type
= route
->type
;
412 memcpy (&new->prefix
, &route
->prefix
, sizeof (struct prefix
));
413 new->installed
= route
->installed
;
414 new->changed
= route
->changed
;
415 new->flag
= route
->flag
;
416 new->route_option
= route
->route_option
;
417 new->linkstate_id
= route
->linkstate_id
;
418 new->path
= route
->path
;
419 ospf6_copy_nexthops (new->nh_list
, route
->nh_list
);
429 ospf6_route_lock (struct ospf6_route
*route
)
435 ospf6_route_unlock (struct ospf6_route
*route
)
437 assert (route
->lock
> 0);
439 if (route
->lock
== 0)
441 /* Can't detach from the table until here
442 because ospf6_route_next () will use
443 the 'route->table' pointer for logging */
445 ospf6_route_delete (route
);
449 /* Route compare function. If ra is more preferred, it returns
450 less than 0. If rb is more preferred returns greater than 0.
451 Otherwise (neither one is preferred), returns 0 */
453 ospf6_route_cmp (struct ospf6_route
*ra
, struct ospf6_route
*rb
)
455 assert (ospf6_route_is_same (ra
, rb
));
456 assert (OSPF6_PATH_TYPE_NONE
< ra
->path
.type
&&
457 ra
->path
.type
< OSPF6_PATH_TYPE_MAX
);
458 assert (OSPF6_PATH_TYPE_NONE
< rb
->path
.type
&&
459 rb
->path
.type
< OSPF6_PATH_TYPE_MAX
);
461 if (ra
->type
!= rb
->type
)
462 return (ra
->type
- rb
->type
);
464 if (ra
->path
.area_id
!= rb
->path
.area_id
)
465 return (ntohl (ra
->path
.area_id
) - ntohl (rb
->path
.area_id
));
467 if (ra
->path
.type
!= rb
->path
.type
)
468 return (ra
->path
.type
- rb
->path
.type
);
470 if (ra
->path
.type
== OSPF6_PATH_TYPE_EXTERNAL2
)
472 if (ra
->path
.u
.cost_e2
!= rb
->path
.u
.cost_e2
)
473 return (ra
->path
.u
.cost_e2
- rb
->path
.u
.cost_e2
);
477 if (ra
->path
.cost
!= rb
->path
.cost
)
478 return (ra
->path
.cost
- rb
->path
.cost
);
485 ospf6_route_lookup (struct prefix
*prefix
,
486 struct ospf6_route_table
*table
)
488 struct route_node
*node
;
489 struct ospf6_route
*route
;
491 node
= route_node_lookup (table
->table
, prefix
);
495 route
= (struct ospf6_route
*) node
->info
;
500 ospf6_route_lookup_identical (struct ospf6_route
*route
,
501 struct ospf6_route_table
*table
)
503 struct ospf6_route
*target
;
505 for (target
= ospf6_route_lookup (&route
->prefix
, table
);
506 target
; target
= target
->next
)
508 if (ospf6_route_is_identical (target
, route
))
515 ospf6_route_lookup_bestmatch (struct prefix
*prefix
,
516 struct ospf6_route_table
*table
)
518 struct route_node
*node
;
519 struct ospf6_route
*route
;
521 node
= route_node_match (table
->table
, prefix
);
524 route_unlock_node (node
);
526 route
= (struct ospf6_route
*) node
->info
;
532 route_table_assert (struct ospf6_route_table
*table
)
534 struct ospf6_route
*prev
, *r
, *next
;
536 unsigned int link_error
= 0, num
= 0;
538 r
= ospf6_route_head (table
);
545 next
= ospf6_route_next (r
);
554 for (r
= ospf6_route_head (table
); r
; r
= ospf6_route_next (r
))
557 if (link_error
== 0 && num
== table
->count
)
560 zlog_err ("PANIC !!");
561 zlog_err ("Something has gone wrong with ospf6_route_table[%p]", table
);
562 zlog_debug ("table count = %d, real number = %d", table
->count
, num
);
563 zlog_debug ("DUMP START");
564 for (r
= ospf6_route_head (table
); r
; r
= ospf6_route_next (r
))
566 prefix2str (&r
->prefix
, buf
, sizeof (buf
));
567 zlog_info ("%p<-[%p]->%p : %s", r
->prev
, r
, r
->next
, buf
);
569 zlog_debug ("DUMP END");
571 assert (link_error
== 0 && num
== table
->count
);
573 #define ospf6_route_table_assert(t) (route_table_assert (t))
575 #define ospf6_route_table_assert(t) ((void) 0)
579 ospf6_route_add (struct ospf6_route
*route
,
580 struct ospf6_route_table
*table
)
582 struct route_node
*node
, *nextnode
, *prevnode
;
583 struct ospf6_route
*current
= NULL
;
584 struct ospf6_route
*prev
= NULL
, *old
= NULL
, *next
= NULL
;
588 assert (route
->rnode
== NULL
);
589 assert (route
->lock
== 0);
590 assert (route
->next
== NULL
);
591 assert (route
->prev
== NULL
);
593 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
594 ospf6_linkstate_prefix2str (&route
->prefix
, buf
, sizeof (buf
));
596 prefix2str (&route
->prefix
, buf
, sizeof (buf
));
598 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
599 zlog_debug ("%s %p: route add %p: %s", ospf6_route_table_name (table
),
601 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
602 zlog_debug ("%s: route add: %s", ospf6_route_table_name (table
), buf
);
604 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &now
);
606 node
= route_node_get (table
->table
, &route
->prefix
);
609 /* find place to insert */
610 for (current
= node
->info
; current
; current
= current
->next
)
612 if (! ospf6_route_is_same (current
, route
))
614 else if (current
->type
!= route
->type
)
616 else if (ospf6_route_is_same_origin (current
, route
))
618 else if (ospf6_route_cmp (current
, route
) > 0)
629 /* if route does not actually change, return unchanged */
630 if (ospf6_route_is_identical (old
, route
))
632 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
633 zlog_debug ("%s %p: route add %p: needless update of %p",
634 ospf6_route_table_name (table
), table
, route
, old
);
635 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
636 zlog_debug ("%s: route add: needless update",
637 ospf6_route_table_name (table
));
639 ospf6_route_delete (route
);
640 SET_FLAG (old
->flag
, OSPF6_ROUTE_ADD
);
641 ospf6_route_table_assert (table
);
646 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
647 zlog_debug ("%s %p: route add %p: update of %p",
648 ospf6_route_table_name (table
), table
, route
, 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
), table
, route
, prev
, next
);
690 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
691 zlog_debug ("%s: route add: another path found",
692 ospf6_route_table_name (table
));
706 if (node
->info
== next
)
708 assert (next
->rnode
== node
);
710 UNSET_FLAG (next
->flag
, OSPF6_ROUTE_BEST
);
711 SET_FLAG (route
->flag
, OSPF6_ROUTE_BEST
);
712 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
713 zlog_info ("%s %p: route add %p: replacing previous best: %p",
714 ospf6_route_table_name (table
), table
, route
, next
);
717 route
->installed
= now
;
718 route
->changed
= now
;
719 assert (route
->table
== NULL
);
720 route
->table
= table
;
722 ospf6_route_lock (route
);
724 ospf6_route_table_assert (table
);
726 SET_FLAG (route
->flag
, OSPF6_ROUTE_ADD
);
728 (*table
->hook_add
) (route
);
733 /* Else, this is the brand new route regarding to the prefix */
734 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
735 zlog_debug ("%s %p: route add %p: brand new route",
736 ospf6_route_table_name (table
), table
, route
);
737 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
738 zlog_debug ("%s: route add: brand new route",
739 ospf6_route_table_name (table
));
741 assert (node
->info
== NULL
);
743 SET_FLAG (route
->flag
, OSPF6_ROUTE_BEST
);
744 ospf6_route_lock (route
);
745 route
->installed
= now
;
746 route
->changed
= now
;
747 assert (route
->table
== NULL
);
748 route
->table
= table
;
750 /* lookup real existing next route */
752 route_lock_node (nextnode
);
754 nextnode
= route_next (nextnode
);
755 } while (nextnode
&& nextnode
->info
== NULL
);
758 if (nextnode
== NULL
)
762 route_unlock_node (nextnode
);
764 next
= nextnode
->info
;
769 /* lookup real existing prev route */
771 route_lock_node (prevnode
);
773 prevnode
= route_prev (prevnode
);
774 } while (prevnode
&& prevnode
->info
== NULL
);
777 if (prevnode
== NULL
)
781 route_unlock_node (prevnode
);
783 prev
= prevnode
->info
;
784 while (prev
->next
&& ospf6_route_is_same (prev
, prev
->next
))
791 ospf6_route_table_assert (table
);
793 SET_FLAG (route
->flag
, OSPF6_ROUTE_ADD
);
795 (*table
->hook_add
) (route
);
801 ospf6_route_remove (struct ospf6_route
*route
,
802 struct ospf6_route_table
*table
)
804 struct route_node
*node
;
805 struct ospf6_route
*current
;
808 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
809 ospf6_linkstate_prefix2str (&route
->prefix
, buf
, sizeof (buf
));
811 prefix2str (&route
->prefix
, buf
, sizeof (buf
));
813 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
814 zlog_debug ("%s %p: route remove %p: %s",
815 ospf6_route_table_name (table
), table
, route
, buf
);
816 else if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
817 zlog_debug ("%s: route remove: %s", ospf6_route_table_name (table
), buf
);
819 node
= route_node_lookup (table
->table
, &route
->prefix
);
822 /* find the route to remove, making sure that the route pointer
823 is from the route table. */
824 current
= node
->info
;
825 while (current
&& ospf6_route_is_same (current
, route
))
827 if (current
== route
)
829 current
= current
->next
;
831 assert (current
== route
);
833 /* adjust doubly linked list */
835 route
->prev
->next
= route
->next
;
837 route
->next
->prev
= route
->prev
;
839 if (node
->info
== route
)
841 if (route
->next
&& ospf6_route_is_same (route
->next
, route
))
843 node
->info
= route
->next
;
844 SET_FLAG (route
->next
->flag
, OSPF6_ROUTE_BEST
);
847 node
->info
= NULL
; /* should unlock route_node here ? */
851 ospf6_route_table_assert (table
);
853 SET_FLAG (route
->flag
, OSPF6_ROUTE_WAS_REMOVED
);
855 if (table
->hook_remove
)
856 (*table
->hook_remove
) (route
);
858 ospf6_route_unlock (route
);
862 ospf6_route_head (struct ospf6_route_table
*table
)
864 struct route_node
*node
;
865 struct ospf6_route
*route
;
867 node
= route_top (table
->table
);
871 /* skip to the real existing entry */
872 while (node
&& node
->info
== NULL
)
873 node
= route_next (node
);
877 route_unlock_node (node
);
880 route
= (struct ospf6_route
*) node
->info
;
881 assert (route
->prev
== NULL
);
882 assert (route
->table
== table
);
883 ospf6_route_lock (route
);
885 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
886 zlog_info ("%s %p: route head: %p<-[%p]->%p",
887 ospf6_route_table_name (table
), table
,
888 route
->prev
, route
, route
->next
);
894 ospf6_route_next (struct ospf6_route
*route
)
896 struct ospf6_route
*next
= route
->next
;
898 if (IS_OSPF6_DEBUG_ROUTE (MEMORY
))
899 zlog_info ("%s %p: route next: %p<-[%p]->%p",
900 ospf6_route_table_name (route
->table
), route
->table
,
901 route
->prev
, route
, route
->next
);
903 ospf6_route_unlock (route
);
905 ospf6_route_lock (next
);
911 ospf6_route_best_next (struct ospf6_route
*route
)
913 struct route_node
*rnode
;
914 struct ospf6_route
*next
;
916 ospf6_route_unlock (route
);
918 rnode
= route
->rnode
;
919 route_lock_node (rnode
);
920 rnode
= route_next (rnode
);
921 while (rnode
&& rnode
->info
== NULL
)
922 rnode
= route_next (rnode
);
925 route_unlock_node (rnode
);
927 assert (rnode
->info
);
928 next
= (struct ospf6_route
*) rnode
->info
;
929 ospf6_route_lock (next
);
934 ospf6_route_match_head (struct prefix
*prefix
,
935 struct ospf6_route_table
*table
)
937 struct route_node
*node
;
938 struct ospf6_route
*route
;
940 /* Walk down tree. */
941 node
= table
->table
->top
;
942 while (node
&& node
->p
.prefixlen
< prefix
->prefixlen
&&
943 prefix_match (&node
->p
, prefix
))
944 node
= node
->link
[prefix_bit(&prefix
->u
.prefix
, node
->p
.prefixlen
)];
947 route_lock_node (node
);
948 while (node
&& node
->info
== NULL
)
949 node
= route_next (node
);
952 route_unlock_node (node
);
954 if (! prefix_match (prefix
, &node
->p
))
958 ospf6_route_lock (route
);
963 ospf6_route_match_next (struct prefix
*prefix
,
964 struct ospf6_route
*route
)
966 struct ospf6_route
*next
;
968 next
= ospf6_route_next (route
);
969 if (next
&& ! prefix_match (prefix
, &next
->prefix
))
971 ospf6_route_unlock (next
);
979 ospf6_route_remove_all (struct ospf6_route_table
*table
)
981 struct ospf6_route
*route
;
982 for (route
= ospf6_route_head (table
); route
;
983 route
= ospf6_route_next (route
))
984 ospf6_route_remove (route
, table
);
987 struct ospf6_route_table
*
988 ospf6_route_table_create (int s
, int t
)
990 struct ospf6_route_table
*new;
991 new = XCALLOC (MTYPE_OSPF6_ROUTE
, sizeof (struct ospf6_route_table
));
992 new->table
= route_table_init ();
999 ospf6_route_table_delete (struct ospf6_route_table
*table
)
1001 ospf6_route_remove_all (table
);
1002 route_table_finish (table
->table
);
1003 XFREE (MTYPE_OSPF6_ROUTE
, table
);
1009 ospf6_route_show (struct vty
*vty
, struct ospf6_route
*route
)
1012 char destination
[64], nexthop
[64];
1013 char duration
[16], ifname
[IFNAMSIZ
];
1014 struct timeval now
, res
;
1015 struct listnode
*node
;
1016 struct ospf6_nexthop
*nh
;
1018 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &now
);
1019 timersub (&now
, &route
->changed
, &res
);
1020 timerstring (&res
, duration
, sizeof (duration
));
1023 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
1024 ospf6_linkstate_prefix2str (&route
->prefix
, destination
,
1025 sizeof (destination
));
1026 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
1027 inet_ntop (route
->prefix
.family
, &route
->prefix
.u
.prefix
,
1028 destination
, sizeof (destination
));
1030 prefix2str (&route
->prefix
, destination
, sizeof (destination
));
1034 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
1037 inet_ntop (AF_INET6
, &nh
->address
, nexthop
,
1039 if (! if_indextoname (nh
->ifindex
, ifname
))
1040 snprintf (ifname
, sizeof (ifname
), "%d", nh
->ifindex
);
1044 vty_out (vty
, "%c%1s %2s %-30s %-25s %6.*s %s%s",
1045 (ospf6_route_is_best (route
) ? '*' : ' '),
1046 OSPF6_DEST_TYPE_SUBSTR (route
->type
),
1047 OSPF6_PATH_TYPE_SUBSTR (route
->path
.type
),
1048 destination
, nexthop
, IFNAMSIZ
, ifname
, duration
, VNL
);
1052 vty_out (vty
, "%c%1s %2s %-30s %-25s %6.*s %s%s",
1053 ' ', "", "", "", nexthop
, IFNAMSIZ
, ifname
, "", VNL
);
1058 ospf6_route_show_detail (struct vty
*vty
, struct ospf6_route
*route
)
1060 char destination
[64], nexthop
[64], ifname
[IFNAMSIZ
];
1061 char area_id
[16], id
[16], adv_router
[16], capa
[16], options
[16];
1062 struct timeval now
, res
;
1064 struct listnode
*node
;
1065 struct ospf6_nexthop
*nh
;
1067 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &now
);
1070 if (route
->type
== OSPF6_DEST_TYPE_LINKSTATE
)
1071 ospf6_linkstate_prefix2str (&route
->prefix
, destination
,
1072 sizeof (destination
));
1073 else if (route
->type
== OSPF6_DEST_TYPE_ROUTER
)
1074 inet_ntop (route
->prefix
.family
, &route
->prefix
.u
.prefix
,
1075 destination
, sizeof (destination
));
1077 prefix2str (&route
->prefix
, destination
, sizeof (destination
));
1078 vty_out (vty
, "Destination: %s%s", destination
, VNL
);
1080 /* destination type */
1081 vty_out (vty
, "Destination type: %s%s",
1082 OSPF6_DEST_TYPE_NAME (route
->type
),
1086 timersub (&now
, &route
->installed
, &res
);
1087 timerstring (&res
, duration
, sizeof (duration
));
1088 vty_out (vty
, "Installed Time: %s ago%s", duration
, VNL
);
1090 timersub (&now
, &route
->changed
, &res
);
1091 timerstring (&res
, duration
, sizeof (duration
));
1092 vty_out (vty
, " Changed Time: %s ago%s", duration
, VNL
);
1094 /* Debugging info */
1095 vty_out (vty
, "Lock: %d Flags: %s%s%s%s%s", route
->lock
,
1096 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_BEST
) ? "B" : "-"),
1097 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_ADD
) ? "A" : "-"),
1098 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_REMOVE
) ? "R" : "-"),
1099 (CHECK_FLAG (route
->flag
, OSPF6_ROUTE_CHANGE
) ? "C" : "-"),
1101 vty_out (vty
, "Memory: prev: %p this: %p next: %p%s",
1102 route
->prev
, route
, route
->next
, VNL
);
1107 inet_ntop (AF_INET
, &route
->path
.area_id
, area_id
, sizeof (area_id
));
1108 vty_out (vty
, "Associated Area: %s%s", area_id
, VNL
);
1111 vty_out (vty
, "Path Type: %s%s",
1112 OSPF6_PATH_TYPE_NAME (route
->path
.type
), VNL
);
1115 inet_ntop (AF_INET
, &route
->path
.origin
.id
, id
, sizeof (id
));
1116 inet_ntop (AF_INET
, &route
->path
.origin
.adv_router
, adv_router
,
1117 sizeof (adv_router
));
1118 vty_out (vty
, "LS Origin: %s Id: %s Adv: %s%s",
1119 ospf6_lstype_name (route
->path
.origin
.type
),
1120 id
, adv_router
, VNL
);
1123 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1124 vty_out (vty
, "Options: %s%s", options
, VNL
);
1127 ospf6_capability_printbuf (route
->path
.router_bits
, capa
, sizeof (capa
));
1128 vty_out (vty
, "Router Bits: %s%s", capa
, VNL
);
1130 /* Prefix Options */
1131 vty_out (vty
, "Prefix Options: xxx%s", VNL
);
1134 vty_out (vty
, "Metric Type: %d%s", route
->path
.metric_type
,
1136 vty_out (vty
, "Metric: %d (%d)%s",
1137 route
->path
.cost
, route
->path
.u
.cost_e2
, VNL
);
1140 vty_out (vty
, "Nexthop:%s", VNL
);
1141 for (ALL_LIST_ELEMENTS_RO (route
->nh_list
, node
, nh
))
1144 inet_ntop (AF_INET6
, &nh
->address
, nexthop
, sizeof (nexthop
));
1145 if (! if_indextoname (nh
->ifindex
, ifname
))
1146 snprintf (ifname
, sizeof (ifname
), "%d", nh
->ifindex
);
1147 vty_out (vty
, " %s %.*s%s", nexthop
, IFNAMSIZ
, ifname
, VNL
);
1149 vty_out (vty
, "%s", VNL
);
1153 ospf6_route_show_table_summary (struct vty
*vty
,
1154 struct ospf6_route_table
*table
)
1156 struct ospf6_route
*route
, *prev
= NULL
;
1157 int i
, pathtype
[OSPF6_PATH_TYPE_MAX
];
1158 unsigned int number
= 0;
1159 int nh_count
=0 , nhinval
= 0, ecmp
= 0;
1160 int alternative
= 0, destination
= 0;
1162 for (i
= 0; i
< OSPF6_PATH_TYPE_MAX
; i
++)
1165 for (route
= ospf6_route_head (table
); route
;
1166 route
= ospf6_route_next (route
))
1168 if (prev
== NULL
|| ! ospf6_route_is_same (prev
, route
))
1172 nh_count
= ospf6_num_nexthops (route
->nh_list
);
1175 else if (nh_count
> 1)
1177 pathtype
[route
->path
.type
]++;
1183 assert (number
== table
->count
);
1185 vty_out (vty
, "Number of OSPFv3 routes: %d%s", number
, VNL
);
1186 vty_out (vty
, "Number of Destination: %d%s", destination
, VNL
);
1187 vty_out (vty
, "Number of Alternative routes: %d%s", alternative
, VNL
);
1188 vty_out (vty
, "Number of Equal Cost Multi Path: %d%s", ecmp
, VNL
);
1189 for (i
= OSPF6_PATH_TYPE_INTRA
; i
<= OSPF6_PATH_TYPE_EXTERNAL2
; i
++)
1191 vty_out (vty
, "Number of %s routes: %d%s",
1192 OSPF6_PATH_TYPE_NAME (i
), pathtype
[i
], VNL
);
1197 ospf6_route_show_table_prefix (struct vty
*vty
,
1198 struct prefix
*prefix
,
1199 struct ospf6_route_table
*table
)
1201 struct ospf6_route
*route
;
1203 route
= ospf6_route_lookup (prefix
, table
);
1207 ospf6_route_lock (route
);
1208 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1210 /* Specifying a prefix will always display details */
1211 ospf6_route_show_detail (vty
, route
);
1212 route
= ospf6_route_next (route
);
1215 ospf6_route_unlock (route
);
1219 ospf6_route_show_table_address (struct vty
*vty
,
1220 struct prefix
*prefix
,
1221 struct ospf6_route_table
*table
)
1223 struct ospf6_route
*route
;
1225 route
= ospf6_route_lookup_bestmatch (prefix
, table
);
1229 prefix
= &route
->prefix
;
1230 ospf6_route_lock (route
);
1231 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1233 /* Specifying a prefix will always display details */
1234 ospf6_route_show_detail (vty
, route
);
1235 route
= ospf6_route_next (route
);
1238 ospf6_route_unlock (route
);
1242 ospf6_route_show_table_match (struct vty
*vty
, int detail
,
1243 struct prefix
*prefix
,
1244 struct ospf6_route_table
*table
)
1246 struct ospf6_route
*route
;
1247 assert (prefix
->family
);
1249 route
= ospf6_route_match_head (prefix
, table
);
1253 ospf6_route_show_detail (vty
, route
);
1255 ospf6_route_show (vty
, route
);
1256 route
= ospf6_route_match_next (prefix
, route
);
1261 ospf6_route_show_table_type (struct vty
*vty
, int detail
, u_char type
,
1262 struct ospf6_route_table
*table
)
1264 struct ospf6_route
*route
;
1266 route
= ospf6_route_head (table
);
1269 if (route
->path
.type
== type
)
1272 ospf6_route_show_detail (vty
, route
);
1274 ospf6_route_show (vty
, route
);
1276 route
= ospf6_route_next (route
);
1281 ospf6_route_show_table (struct vty
*vty
, int detail
,
1282 struct ospf6_route_table
*table
)
1284 struct ospf6_route
*route
;
1286 route
= ospf6_route_head (table
);
1290 ospf6_route_show_detail (vty
, route
);
1292 ospf6_route_show (vty
, route
);
1293 route
= ospf6_route_next (route
);
1298 ospf6_route_table_show (struct vty
*vty
, int argc
, const char *argv
[],
1299 struct ospf6_route_table
*table
)
1307 struct prefix prefix
;
1310 memset (&prefix
, 0, sizeof (struct prefix
));
1312 for (i
= 0; i
< argc
; i
++)
1314 if (! strcmp (argv
[i
], "summary"))
1320 if (! strcmp (argv
[i
], "intra-area"))
1322 type
= OSPF6_PATH_TYPE_INTRA
;
1326 if (! strcmp (argv
[i
], "inter-area"))
1328 type
= OSPF6_PATH_TYPE_INTER
;
1332 if (! strcmp (argv
[i
], "external-1"))
1334 type
= OSPF6_PATH_TYPE_EXTERNAL1
;
1338 if (! strcmp (argv
[i
], "external-2"))
1340 type
= OSPF6_PATH_TYPE_EXTERNAL2
;
1344 if (! strcmp (argv
[i
], "detail"))
1350 if (! strcmp (argv
[i
], "match"))
1356 ret
= str2prefix (argv
[i
], &prefix
);
1357 if (ret
== 1 && prefix
.family
== AF_INET6
)
1360 if (strchr (argv
[i
], '/'))
1365 vty_out (vty
, "Malformed argument: %s%s", argv
[i
], VNL
);
1369 /* Give summary of this route table */
1372 ospf6_route_show_table_summary (vty
, table
);
1376 /* Give exact prefix-match route */
1377 if (isprefix
&& ! match
)
1379 /* If exact address, give best matching route */
1381 ospf6_route_show_table_address (vty
, &prefix
, table
);
1383 ospf6_route_show_table_prefix (vty
, &prefix
, table
);
1389 ospf6_route_show_table_match (vty
, detail
, &prefix
, table
);
1391 ospf6_route_show_table_type (vty
, detail
, type
, table
);
1393 ospf6_route_show_table (vty
, detail
, table
);
1399 ospf6_linkstate_show_header (struct vty
*vty
)
1401 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %s%s",
1402 "Type", "Router-ID", "Net-ID", "Rtr-Bits", "Options", "Cost", VNL
);
1406 ospf6_linkstate_show (struct vty
*vty
, struct ospf6_route
*route
)
1408 u_int32_t router
, id
;
1409 char routername
[16], idname
[16], rbits
[16], options
[16];
1411 router
= ospf6_linkstate_prefix_adv_router (&route
->prefix
);
1412 inet_ntop (AF_INET
, &router
, routername
, sizeof (routername
));
1413 id
= ospf6_linkstate_prefix_id (&route
->prefix
);
1414 inet_ntop (AF_INET
, &id
, idname
, sizeof (idname
));
1416 ospf6_capability_printbuf (route
->path
.router_bits
, rbits
, sizeof (rbits
));
1417 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1420 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %lu%s",
1421 "Network", routername
, idname
, rbits
, options
,
1422 (unsigned long) route
->path
.cost
, VNL
);
1424 vty_out (vty
, "%-7s %-15s %-15s %-8s %-14s %lu%s",
1425 "Router", routername
, idname
, rbits
, options
,
1426 (unsigned long) route
->path
.cost
, VNL
);
1431 ospf6_linkstate_show_table_exact (struct vty
*vty
,
1432 struct prefix
*prefix
,
1433 struct ospf6_route_table
*table
)
1435 struct ospf6_route
*route
;
1437 route
= ospf6_route_lookup (prefix
, table
);
1441 ospf6_route_lock (route
);
1442 while (route
&& ospf6_route_is_prefix (prefix
, route
))
1444 /* Specifying a prefix will always display details */
1445 ospf6_route_show_detail (vty
, route
);
1446 route
= ospf6_route_next (route
);
1449 ospf6_route_unlock (route
);
1453 ospf6_linkstate_show_table (struct vty
*vty
, int detail
,
1454 struct ospf6_route_table
*table
)
1456 struct ospf6_route
*route
;
1459 ospf6_linkstate_show_header (vty
);
1461 route
= ospf6_route_head (table
);
1465 ospf6_route_show_detail (vty
, route
);
1467 ospf6_linkstate_show (vty
, route
);
1468 route
= ospf6_route_next (route
);
1473 ospf6_linkstate_table_show (struct vty
*vty
, int argc
, const char *argv
[],
1474 struct ospf6_route_table
*table
)
1480 struct prefix router
, id
, prefix
;
1482 memset (&router
, 0, sizeof (struct prefix
));
1483 memset (&id
, 0, sizeof (struct prefix
));
1484 memset (&prefix
, 0, sizeof (struct prefix
));
1486 for (i
= 0; i
< argc
; i
++)
1488 if (! strcmp (argv
[i
], "detail"))
1496 ret
= str2prefix (argv
[i
], &router
);
1497 if (ret
== 1 && router
.family
== AF_INET
)
1502 vty_out (vty
, "Malformed argument: %s%s", argv
[i
], VNL
);
1508 ret
= str2prefix (argv
[i
], &id
);
1509 if (ret
== 1 && id
.family
== AF_INET
)
1514 vty_out (vty
, "Malformed argument: %s%s", argv
[i
], VNL
);
1518 vty_out (vty
, "Malformed argument: %s%s", argv
[i
], VNL
);
1523 ospf6_linkstate_prefix (router
.u
.prefix4
.s_addr
,
1524 id
.u
.prefix4
.s_addr
, &prefix
);
1527 ospf6_linkstate_show_table_exact (vty
, &prefix
, table
);
1529 ospf6_linkstate_show_table (vty
, detail
, table
);
1536 ospf6_brouter_show_header (struct vty
*vty
)
1538 vty_out (vty
, "%-15s %-8s %-14s %-10s %-15s%s",
1539 "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area", VNL
);
1543 ospf6_brouter_show (struct vty
*vty
, struct ospf6_route
*route
)
1545 u_int32_t adv_router
;
1546 char adv
[16], rbits
[16], options
[16], area
[16];
1548 adv_router
= ospf6_linkstate_prefix_adv_router (&route
->prefix
);
1549 inet_ntop (AF_INET
, &adv_router
, adv
, sizeof (adv
));
1550 ospf6_capability_printbuf (route
->path
.router_bits
, rbits
, sizeof (rbits
));
1551 ospf6_options_printbuf (route
->path
.options
, options
, sizeof (options
));
1552 inet_ntop (AF_INET
, &route
->path
.area_id
, area
, sizeof (area
));
1554 /* vty_out (vty, "%-15s %-8s %-14s %-10s %-15s%s",
1555 "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area", VNL); */
1556 vty_out (vty
, "%-15s %-8s %-14s %-10s %-15s%s",
1557 adv
, rbits
, options
, OSPF6_PATH_TYPE_NAME (route
->path
.type
),
1561 DEFUN (debug_ospf6_route
,
1562 debug_ospf6_route_cmd
,
1563 "debug ospf6 route (table|intra-area|inter-area|memory)",
1566 "Debug route table calculation\n"
1568 "Debug intra-area route calculation\n"
1569 "Debug inter-area route calculation\n"
1570 "Debug route memory use\n"
1573 unsigned char level
= 0;
1575 if (! strncmp (argv
[0], "table", 5))
1576 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1577 else if (! strncmp (argv
[0], "intra", 5))
1578 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1579 else if (! strncmp (argv
[0], "inter", 5))
1580 level
= OSPF6_DEBUG_ROUTE_INTER
;
1581 else if (! strncmp (argv
[0], "memor", 5))
1582 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1583 OSPF6_DEBUG_ROUTE_ON (level
);
1587 DEFUN (no_debug_ospf6_route
,
1588 no_debug_ospf6_route_cmd
,
1589 "no debug ospf6 route (table|intra-area|inter-area|memory)",
1593 "Debug route table calculation\n"
1594 "Debug intra-area route calculation\n"
1595 "Debug route memory use\n")
1597 unsigned char level
= 0;
1599 if (! strncmp (argv
[0], "table", 5))
1600 level
= OSPF6_DEBUG_ROUTE_TABLE
;
1601 else if (! strncmp (argv
[0], "intra", 5))
1602 level
= OSPF6_DEBUG_ROUTE_INTRA
;
1603 else if (! strncmp (argv
[0], "inter", 5))
1604 level
= OSPF6_DEBUG_ROUTE_INTER
;
1605 else if (! strncmp (argv
[0], "memor", 5))
1606 level
= OSPF6_DEBUG_ROUTE_MEMORY
;
1607 OSPF6_DEBUG_ROUTE_OFF (level
);
1612 config_write_ospf6_debug_route (struct vty
*vty
)
1614 if (IS_OSPF6_DEBUG_ROUTE (TABLE
))
1615 vty_out (vty
, "debug ospf6 route table%s", VNL
);
1616 if (IS_OSPF6_DEBUG_ROUTE (INTRA
))
1617 vty_out (vty
, "debug ospf6 route intra-area%s", VNL
);
1618 if (IS_OSPF6_DEBUG_ROUTE (INTER
))
1619 vty_out (vty
, "debug ospf6 route inter-area%s", VNL
);
1624 install_element_ospf6_debug_route (void)
1626 install_element (ENABLE_NODE
, &debug_ospf6_route_cmd
);
1627 install_element (ENABLE_NODE
, &no_debug_ospf6_route_cmd
);
1628 install_element (CONFIG_NODE
, &debug_ospf6_route_cmd
);
1629 install_element (CONFIG_NODE
, &no_debug_ospf6_route_cmd
);