Initial revision

1 files changed, 1130 insertions, 0 deletions

diff --git a/ospf6d/ospf6_route.c b/ospf6d/ospf6_route.c
new file mode 100644
index 00000000..c35efa6e
--- /dev/null
+++ b/ospf6d/ospf6_route.c
@@ -0,0 +1,1130 @@
+/*
+ * Copyright (C) 1999 Yasuhiro Ohara
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the 
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 
+ * Boston, MA 02111-1307, USA.  
+ */
+
+#include "ospf6d.h"
+
+char *
+dtype_name[OSPF6_DEST_TYPE_MAX] =
+{
+  "Unknown", "Router", "Network", "Discard"
+};
+#define DTYPE_NAME(x) \
+  (0 < (x) && (x) < sizeof (dtype_name) ? \
+   dtype_name[(x)] : dtype_name[0])
+
+char *
+dtype_abname[OSPF6_DEST_TYPE_MAX] =
+{
+  "?", "R", "N", "D"
+};
+#define DTYPE_ABNAME(x) \
+  (0 < (x) && (x) < sizeof (dtype_abname) ? \
+   dtype_abname[(x)] : dtype_abname[0])
+
+char *
+ptype_name[OSPF6_PATH_TYPE_MAX] =
+{
+  "Unknown", "Intra", "Inter", "External-1", "External-2",
+  "System", "Kernel", "Connect", "Static", "RIP", "RIPng",
+  "OSPF", "OSPF6", "BGP"
+};
+#define PTYPE_NAME(x) \
+  (0 < (x) && (x) < sizeof (ptype_name) ? \
+   ptype_name[(x)] : ptype_name[0])
+
+char *
+ptype_abname[OSPF6_PATH_TYPE_MAX] =
+{
+  "??", "Ia", "Ie", "E1", "E2",
+  "-X", "-K", "-C", "-S", "-R", "-R",
+  "-O", "-O", "-B"
+};
+#define PTYPE_ABNAME(x) \
+  (0 < (x) && (x) < sizeof (ptype_abname) ? \
+   ptype_abname[(x)] : ptype_abname[0])
+
+
+
+int
+ospf6_path_cmp (void *arg1, void *arg2)
+{
+  struct ospf6_path_node *pn1 = arg1;
+  struct ospf6_path_node *pn2 = arg2;
+  struct ospf6_path *p1 = &pn1->path;
+  struct ospf6_path *p2 = &pn2->path;
+
+  if (p1->type < p2->type)
+    return -1;
+  else if (p1->type > p2->type)
+    return 1;
+
+  if (p1->type == OSPF6_PATH_TYPE_EXTERNAL2)
+    {
+      if (p1->cost_e2 < p2->cost_e2)
+        return -1;
+      else if (p1->cost_e2 > p2->cost_e2)
+        return 1;
+    }
+
+  if (p1->cost < p2->cost)
+    return -1;
+  else if (p1->cost > p2->cost)
+    return 1;
+
+  /* if from the same source, recognize as identical
+     (and treat this as update) */
+  if (! memcmp (&p1->origin, &p2->origin, sizeof (struct ls_origin)) &&
+      p1->area_id == p2->area_id)
+    return 0;
+
+  /* else, always prefer left */
+  return -1;
+}
+
+int
+ospf6_nexthop_cmp (void *arg1, void *arg2)
+{
+  int i, ret = 0;
+  struct ospf6_nexthop_node *nn1 = arg1;
+  struct ospf6_nexthop_node *nn2 = arg2;
+  struct ospf6_nexthop *n1 = &nn1->nexthop;
+  struct ospf6_nexthop *n2 = &nn2->nexthop;
+
+  if (memcmp (n1, n2, sizeof (struct ospf6_nexthop)) == 0)
+    return 0;
+
+  for (i = 0; i < sizeof (struct in6_addr); i++)
+    {
+      if (nn1->nexthop.address.s6_addr[i] != nn2->nexthop.address.s6_addr[i])
+        {
+          ret = nn1->nexthop.address.s6_addr[i] -
+                nn2->nexthop.address.s6_addr[i];
+          break;
+        }
+    }
+
+  if (ret == 0)
+    ret = -1;
+
+  return ret;
+}
+
+static void
+ospf6_route_request (struct ospf6_route_req *request,
+                     struct ospf6_route_node   *rn,
+                     struct ospf6_path_node    *pn,
+                     struct ospf6_nexthop_node *nn)
+{
+  assert (request);
+  assert (rn && pn && nn);
+
+  request->route_node = rn->route_node;
+
+  linklist_head (rn->path_list, &request->path_lnode);
+  while (request->path_lnode.data != pn)
+    {
+      //assert (! linklist_end (&request->path_lnode));
+      if (linklist_end (&request->path_lnode))
+        {
+          struct linklist_node node;
+
+          zlog_info ("rn: %p, pn: %p", rn, pn);
+          zlog_info ("origin: %hx %x %x bits: %x opt: %x%x%x popt: %x area: %x type: %d cost  %d %d %d",
+          pn->path.origin.type, pn->path.origin.id, pn->path.origin.adv_router, (int)pn->path.router_bits, (int)pn->path.capability[0],
+          (int)pn->path.capability[1], (int)pn->path.capability[2],
+          (int)pn->path.prefix_options, pn->path.area_id,
+          pn->path.type, pn->path.metric_type, pn->path.cost, pn->path.cost_e2);
+
+          for (linklist_head (rn->path_list, &node); ! linklist_end (&node);
+               linklist_next (&node))
+            {
+              struct ospf6_path_node *pn2 = node.data;
+
+              zlog_info (" %p: path data with pn(%p): %s", pn2, pn,
+                         (memcmp (&pn->path, &pn2->path,
+                                  sizeof (struct ospf6_path)) ?
+                          "different" : "same"));
+
+          zlog_info ("  origin: %hx %x %x bits: %x opt: %x%x%x popt: %x area: %x type: %d cost  %d %d %d",
+          pn2->path.origin.type, pn2->path.origin.id, pn2->path.origin.adv_router, (int)pn2->path.router_bits, (int)pn2->path.capability[0],
+          (int)pn2->path.capability[1], (int)pn2->path.capability[2],
+          (int)pn2->path.prefix_options, pn2->path.area_id,
+          pn2->path.type, pn2->path.metric_type, pn2->path.cost, pn2->path.cost_e2);
+
+              if (! memcmp (&pn->path, &pn2->path, sizeof (struct ospf6_path)))
+                {
+                  pn = pn2;
+                  request->nexthop_lnode.data = pn2;
+                }
+            }
+          break;
+        }
+      linklist_next (&request->path_lnode);
+    }
+  assert (request->path_lnode.data == pn);
+
+  linklist_head (pn->nexthop_list, &request->nexthop_lnode);
+  while (request->nexthop_lnode.data != nn)
+    {
+      assert (! linklist_end (&request->nexthop_lnode));
+      linklist_next (&request->nexthop_lnode);
+    }
+  assert (request->nexthop_lnode.data == nn);
+
+  request->table = rn->table;
+  request->count = rn->count;
+  request->route_id = rn->route_id;
+  memcpy (&request->route,   &rn->route,   sizeof (struct ospf6_route));
+  memcpy (&request->path,    &pn->path,    sizeof (struct ospf6_path));
+  memcpy (&request->nexthop, &nn->nexthop, sizeof (struct ospf6_nexthop));
+}
+
+int
+ospf6_route_count (struct ospf6_route_req *request)
+{
+  return request->count;
+}
+
+int
+ospf6_route_lookup (struct ospf6_route_req *request,
+                    struct prefix *prefix,
+                    struct ospf6_route_table *table)
+{
+  struct route_node *node;
+  struct ospf6_route_node   *rn = NULL;
+  struct ospf6_path_node    *pn = NULL;
+  struct ospf6_nexthop_node *nn = NULL;
+  struct linklist_node lnode;
+
+  if (request)
+    memset ((void *) request, 0, sizeof (struct ospf6_route_req));
+
+  node = route_node_lookup (table->table, prefix);
+  if (! node)
+    return 0;
+
+  rn = (struct ospf6_route_node *) node->info;
+  if (! rn)
+    return 0;
+
+  if (request)
+    {
+      linklist_head (rn->path_list, &lnode);
+      pn = lnode.data;
+      linklist_head (pn->nexthop_list, &lnode);
+      nn = lnode.data;
+
+      ospf6_route_request (request, rn, pn, nn);
+    }
+
+  return 1;
+}
+
+void
+ospf6_route_head (struct ospf6_route_req *request,
+                  struct ospf6_route_table *table)
+{
+  struct route_node *node;
+  struct ospf6_route_node   *rn = NULL;
+  struct ospf6_path_node    *pn = NULL;
+  struct ospf6_nexthop_node *nn = NULL;
+  struct linklist_node lnode;
+
+  if (request)
+    memset (request, 0, sizeof (struct ospf6_route_req));
+
+  node = route_top (table->table);
+  if (! node)
+    return;
+
+  while (node && node->info == NULL)
+    node = route_next (node);
+  if (! node)
+    return;
+
+  rn = (struct ospf6_route_node *) node->info;
+  linklist_head (rn->path_list, &lnode);
+  pn = lnode.data;
+  linklist_head (pn->nexthop_list, &lnode);
+  nn = lnode.data;
+
+  ospf6_route_request (request, rn, pn, nn);
+}
+
+int
+ospf6_route_end (struct ospf6_route_req *request)
+{
+  if (request->route_node == NULL &&
+      linklist_end (&request->path_lnode) &&
+      linklist_end (&request->nexthop_lnode) &&
+      request->nexthop.ifindex == 0 &&
+      IN6_IS_ADDR_UNSPECIFIED (&request->nexthop.address))
+    return 1;
+  return 0;
+}
+
+void
+ospf6_route_next (struct ospf6_route_req *request)
+{
+  struct ospf6_route_node   *route_node = NULL;
+  struct ospf6_path_node    *path_node = NULL;
+  struct ospf6_nexthop_node *nexthop_node = NULL;
+
+  linklist_next (&request->nexthop_lnode);
+  if (linklist_end (&request->nexthop_lnode))
+    {
+      linklist_next (&request->path_lnode);
+      if (linklist_end (&request->path_lnode))
+        {
+          request->route_node = route_next (request->route_node);
+          while (request->route_node && request->route_node->info == NULL)
+            request->route_node = route_next (request->route_node);
+          if (request->route_node)
+            {
+              route_node = request->route_node->info;
+              if (route_node)
+                linklist_head (route_node->path_list, &request->path_lnode);
+            }
+        }
+
+      path_node = request->path_lnode.data;
+      if (path_node)
+        linklist_head (path_node->nexthop_list, &request->nexthop_lnode);
+    }
+
+  nexthop_node = request->nexthop_lnode.data;
+
+  if (nexthop_node == NULL)
+    {
+      assert (path_node == NULL);
+      assert (route_node == NULL);
+
+      memset (&request->route,   0, sizeof (struct ospf6_route));
+      memset (&request->path,    0, sizeof (struct ospf6_path));
+      memset (&request->nexthop, 0, sizeof (struct ospf6_nexthop));
+    }
+  else
+    {
+      path_node = request->path_lnode.data;
+      route_node = request->route_node->info;
+
+      assert (path_node != NULL);
+      assert (route_node != NULL);
+
+      memcpy (&request->route,   &route_node->route,
+              sizeof (struct ospf6_route));
+      memcpy (&request->path,    &path_node->path,
+              sizeof (struct ospf6_path));
+      memcpy (&request->nexthop, &nexthop_node->nexthop,
+              sizeof (struct ospf6_nexthop));
+    }
+}
+
+#define ADD    0
+#define CHANGE 1
+#define REMOVE 2
+
+void
+ospf6_route_hook_call (int type,
+                       struct ospf6_route_req *request,
+                       struct ospf6_route_table *table)
+{
+  struct linklist_node node;
+  void (*func) (struct ospf6_route_req *);
+
+  for (linklist_head (table->hook_list[type], &node);
+       ! linklist_end (&node);
+       linklist_next (&node))
+    {
+      func = node.data;
+      (*func) (request);
+    }
+}
+
+void
+ospf6_route_hook_register (void (*add)    (struct ospf6_route_req *),
+                           void (*change) (struct ospf6_route_req *),
+                           void (*remove) (struct ospf6_route_req *),
+                           struct ospf6_route_table *table)
+{
+  linklist_add (add,    table->hook_list[ADD]);
+  linklist_add (change, table->hook_list[CHANGE]);
+  linklist_add (remove, table->hook_list[REMOVE]);
+}
+
+void
+ospf6_route_hook_unregister (void (*add)    (struct ospf6_route_req *),
+                             void (*change) (struct ospf6_route_req *),
+                             void (*remove) (struct ospf6_route_req *),
+                             struct ospf6_route_table *table)
+{
+  linklist_remove (add,    table->hook_list[ADD]);
+  linklist_remove (change, table->hook_list[CHANGE]);
+  linklist_remove (remove, table->hook_list[REMOVE]);
+}
+
+
+int
+prefix_ls2str (struct prefix *p, char *str, int size)
+{
+  char id[BUFSIZ], adv_router[BUFSIZ];
+  struct prefix_ls *pl = (struct prefix_ls *) p;
+
+  inet_ntop (AF_INET, &pl->id, id, BUFSIZ);
+  inet_ntop (AF_INET, &pl->adv_router, adv_router, BUFSIZ);
+  snprintf (str, size, "%s-%s", adv_router, id);
+  return 0;
+}
+
+void
+ospf6_route_log_request (char *what, char *where,
+                         struct ospf6_route_req *request)
+{
+  char prefix[64];
+  char area_id[16];
+  char type[16], id[16], adv[16];
+  char address[64], ifname[IFNAMSIZ];
+
+  if (request->route.prefix.family != AF_INET &&
+      request->route.prefix.family != AF_INET6)
+    prefix_ls2str (&request->route.prefix, prefix, sizeof (prefix));
+  else
+    prefix2str (&request->route.prefix, prefix, sizeof (prefix));
+
+  inet_ntop (AF_INET, &request->path.area_id, area_id, sizeof (area_id));
+
+  ospf6_lsa_type_string (request->path.origin.type, type, sizeof (type));
+  inet_ntop (AF_INET, &request->path.origin.id, id, sizeof (id));
+  inet_ntop (AF_INET, &request->path.origin.adv_router, adv, sizeof (adv));
+
+  inet_ntop (AF_INET6, &request->nexthop.address, address, sizeof (address));
+
+  zlog_info ("ROUTE: %s %s %s %s %s",
+             what, DTYPE_ABNAME (request->route.type), prefix,
+             ((strcmp ("Add", what) == 0) ? "to" : "from"), where);
+  zlog_info ("ROUTE:     Area: %s type: %s cost: %lu (E2: %lu)",
+             area_id, PTYPE_NAME (request->path.type),
+             (u_long) request->path.cost, (u_long) request->path.cost_e2);
+  zlog_info ("ROUTE:     Origin: Type: %s", type);
+  zlog_info ("ROUTE:     Origin: Id: %s Adv: %s", id, adv);
+  zlog_info ("ROUTE:     Nexthop: %s", address);
+  zlog_info ("ROUTE:     Nexthop: Ifindex: %u (%s)",
+             request->nexthop.ifindex,
+             if_indextoname (request->nexthop.ifindex, ifname));
+}
+
+struct ospf6_path_node *
+ospf6_route_find_path_node (struct ospf6_route_req *request,
+                            struct ospf6_route_node *rn)
+{
+  struct linklist_node node;
+
+  for (linklist_head (rn->path_list, &node); ! linklist_end (&node);
+       linklist_next (&node))
+    {
+      struct ospf6_path_node *path_node = node.data;
+
+      if (path_node->path.area_id == request->path.area_id &&
+          path_node->path.origin.type == request->path.origin.type &&
+          path_node->path.origin.id == request->path.origin.id &&
+          path_node->path.origin.adv_router == request->path.origin.adv_router)
+        return path_node;
+    }
+
+#if 0
+  zlog_info ("req path : area: %#x origin: type: %d, id: %d, adv_router: %#x",
+             request->path.area_id, request->path.origin.type,
+             request->path.origin.id, request->path.origin.adv_router);
+  for (linklist_head (rn->path_list, &node); ! linklist_end (&node);
+       linklist_next (&node))
+    {
+      struct ospf6_path_node *path_node = node.data;
+      zlog_info ("  path : area: %#x origin: type: %d, id: %d, adv_router: %#x",
+                 path_node->path.area_id, path_node->path.origin.type,
+                 path_node->path.origin.id, path_node->path.origin.adv_router);
+    }
+#endif
+
+  return NULL;
+}
+
+struct ospf6_nexthop_node *
+ospf6_route_find_nexthop_node (struct ospf6_route_req *request,
+                               struct ospf6_path_node *pn)
+{
+  struct linklist_node node;
+  for (linklist_head (pn->nexthop_list, &node); ! linklist_end (&node);
+       linklist_next (&node))
+    {
+      struct ospf6_nexthop_node *nexthop_node = node.data;
+
+      if (! memcmp (&nexthop_node->nexthop, &request->nexthop,
+          sizeof (struct ospf6_nexthop)))
+        return nexthop_node;
+    }
+  return NULL;
+}
+
+void
+ospf6_route_add (struct ospf6_route_req *request,
+                 struct ospf6_route_table *table)
+{
+  struct ospf6_route_node   *rn;
+  struct ospf6_path_node    *pn;
+  struct ospf6_nexthop_node *nn;
+  struct route_node *route_node;
+
+  struct ospf6_route_req route;
+
+  int route_change   = 0;
+  int path_change    = 0;
+  int nexthop_change = 0;
+
+  /* find the requested route */
+  route_node = route_node_get (table->table, &request->route.prefix);
+  rn = (struct ospf6_route_node *) route_node->info;
+
+  if (rn)
+    {
+      if (memcmp (&rn->route, &request->route, sizeof (struct ospf6_route)))
+        {
+          memcpy (&rn->route, &request->route, sizeof (struct ospf6_route));
+          route_change++;
+        }
+    }
+  else
+    {
+      rn = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_route_node));
+      rn->table = table;
+      rn->route_node = route_node;
+      rn->route_id = table->route_id++;
+      rn->path_list = linklist_create ();
+      rn->path_list->cmp = ospf6_path_cmp;
+      memcpy (&rn->route, &request->route, sizeof (struct ospf6_route));
+      route_node->info = rn;
+    }
+
+  /* find the same path */
+  pn = ospf6_route_find_path_node (request, rn);
+
+  if (pn)
+    {
+      if (memcmp (&pn->path, &request->path, sizeof (struct ospf6_path)))
+        {
+          memcpy (&pn->path, &request->path, sizeof (struct ospf6_path));
+          path_change++;
+        }
+    }
+  else
+    {
+      pn = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_path_node));
+      pn->route_node = rn;
+      pn->nexthop_list = linklist_create ();
+      pn->nexthop_list->cmp = ospf6_nexthop_cmp;
+      memcpy (&pn->path, &request->path, sizeof (struct ospf6_path));
+      linklist_add (pn, rn->path_list);
+    }
+
+  /* find the same nexthop */
+  nn = ospf6_route_find_nexthop_node (request, pn);
+
+  if (nn)
+    {
+      if (memcmp (&nn->nexthop, &request->nexthop,
+                  sizeof (struct ospf6_nexthop)))
+        {
+          memcpy (&nn->nexthop, &request->nexthop,
+                  sizeof (struct ospf6_nexthop));
+          nexthop_change++;
+          gettimeofday (&nn->installed, (struct timezone *) NULL);
+        }
+    }
+  else
+    {
+      nn = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_nexthop_node));
+      nn->path_node = pn;
+      memcpy (&nn->nexthop, &request->nexthop, sizeof (struct ospf6_nexthop));
+      linklist_add (nn, pn->nexthop_list);
+      rn->count++;
+      gettimeofday (&nn->installed, (struct timezone *) NULL);
+    }
+
+  SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ADD);
+  if (route_change)
+    SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ROUTE_CHANGE);
+  if (path_change)
+    SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_PATH_CHANGE);
+  if (nexthop_change)
+    SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE);
+
+  if (table->freeze)
+    return;
+
+  if (IS_OSPF6_DUMP_ROUTE)
+    {
+      ospf6_route_log_request ("Add", table->name, request);
+
+      if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ROUTE_CHANGE))
+        zlog_info ("ROUTE:   route attribute change");
+      if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_PATH_CHANGE))
+        zlog_info ("ROUTE:   path attribute change");
+      if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE))
+        zlog_info ("ROUTE:   nexthop attribute change");
+    }
+
+  if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ROUTE_CHANGE) ||
+      CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_PATH_CHANGE))
+    SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE);
+
+  /* Call hooks */
+  ospf6_route_request (&route, rn, pn, nn);
+  if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ADD))
+    ospf6_route_hook_call (ADD, &route, table);
+  else if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE))
+    ospf6_route_hook_call (CHANGE, &route, table);
+
+  if (table->hook_add &&
+      CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ADD))
+    (*table->hook_add) (&route);
+  else if (table->hook_change &&
+           CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE))
+    (*table->hook_change) (&route);
+
+  /* clear flag */
+  nn->flag = 0;
+}
+
+void
+ospf6_route_remove (struct ospf6_route_req *request,
+                    struct ospf6_route_table *table)
+{
+  struct ospf6_route_node   *rn;
+  struct ospf6_path_node    *pn;
+  struct ospf6_nexthop_node *nn;
+  struct route_node *route_node;
+  struct ospf6_route_req route;
+
+  /* find the requested route */
+  route_node = route_node_get (table->table, &request->route.prefix);
+  rn = (struct ospf6_route_node *) route_node->info;
+
+  if (! rn)
+    {
+      if (IS_OSPF6_DUMP_ROUTE)
+        {
+          ospf6_route_log_request ("Remove", table->name, request);
+          zlog_info ("ROUTE:   Can't remove: No such route");
+        }
+      return;
+    }
+
+  pn = ospf6_route_find_path_node (request, rn);
+  if (! pn)
+    {
+      if (IS_OSPF6_DUMP_ROUTE)
+        {
+          ospf6_route_log_request ("Remove", table->name, request);
+          zlog_info ("ROUTE:   Can't remove: No such path");
+        }
+      return;
+    }
+
+  if (pn->path.area_id != request->path.area_id ||
+      pn->path.origin.type != request->path.origin.type ||
+      pn->path.origin.id != request->path.origin.id ||
+      pn->path.origin.adv_router != request->path.origin.adv_router)
+    {
+      if (IS_OSPF6_DUMP_ROUTE)
+        {
+          ospf6_route_log_request ("Remove", table->name, request);
+          zlog_info ("ROUTE:   Can't remove: Path differ");
+          {
+            char *s, *e, *c;
+            char line[512], *p;
+
+            p = line;
+            s = (char *) &pn->path;
+            e = s + sizeof (struct ospf6_path);
+            for (c = s; c < e; c++)
+              {
+                if ((c - s) % 4 == 0)
+                  snprintf (p++, line + sizeof (line) - p, " ");
+                snprintf (p, line + sizeof (line) - p, "%02x", *c);
+                p += 2;
+              }
+            zlog_info ("ROUTE:     path: %s", line);
+
+            p = line;
+            s = (char *) &request->path;
+            e = s + sizeof (struct ospf6_path);
+            for (c = s; c < e; c++)
+              {
+                if ((c - s) % 4 == 0)
+                  snprintf (p++, line + sizeof (line) - p, " ");
+                snprintf (p, line + sizeof (line) - p, "%02x", *c);
+                p += 2;
+              }
+            zlog_info ("ROUTE:     req : %s", line);
+
+          }
+        }
+      return;
+    }
+
+  nn = ospf6_route_find_nexthop_node (request, pn);
+  if (! nn)
+    {
+      if (IS_OSPF6_DUMP_ROUTE)
+        {
+          ospf6_route_log_request ("Remove", table->name, request);
+          zlog_info ("ROUTE:   Can't remove: No such nexthop");
+        }
+      return;
+    }
+
+  if (memcmp (&nn->nexthop, &request->nexthop, sizeof (struct ospf6_nexthop)))
+    {
+      if (IS_OSPF6_DUMP_ROUTE)
+        {
+          ospf6_route_log_request ("Remove", table->name, request);
+          zlog_info ("ROUTE:   Can't remove: Nexthop differ");
+        }
+      return;
+    }
+
+  SET_FLAG (nn->flag, OSPF6_ROUTE_FLAG_REMOVE);
+
+  if (table->freeze)
+    return;
+
+  if (IS_OSPF6_DUMP_ROUTE)
+    ospf6_route_log_request ("Remove", table->name, request);
+
+  ospf6_route_request (&route, rn, pn, nn);
+  ospf6_route_hook_call (REMOVE, &route, table);
+  if (table->hook_remove)
+    (*table->hook_remove) (&route);
+
+  /* clear flag */
+  nn->flag = 0;
+
+  /* remove nexthop */
+  linklist_remove (nn, pn->nexthop_list);
+  rn->count--;
+  XFREE (MTYPE_OSPF6_ROUTE, nn);
+
+  /* remove path if there's no nexthop for the path */
+  if (pn->nexthop_list->count != 0)
+    return;
+  linklist_remove (pn, rn->path_list);
+  linklist_delete (pn->nexthop_list);
+  XFREE (MTYPE_OSPF6_ROUTE, pn);
+
+  /* remove route if there's no path for the route */
+  if (rn->path_list->count != 0)
+    return;
+  route_node->info = NULL;
+  linklist_delete (rn->path_list);
+  XFREE (MTYPE_OSPF6_ROUTE, rn);
+}
+
+void
+ospf6_route_remove_all (struct ospf6_route_table *table)
+{
+  struct ospf6_route_req request;
+
+  for (ospf6_route_head (&request, table); ! ospf6_route_end (&request);
+       ospf6_route_next (&request))
+    ospf6_route_remove (&request, table);
+}
+
+
+struct ospf6_route_table *
+ospf6_route_table_create (char *name)
+{
+  int i;
+  struct ospf6_route_table *new;
+
+  new = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_route_table));
+  snprintf (new->name, sizeof (new->name), "%s", name);
+
+  new->table = route_table_init ();
+  for (i = 0; i < 3; i++)
+    new->hook_list[i] = linklist_create ();
+
+  return new;
+}
+
+void
+ospf6_route_table_delete (struct ospf6_route_table *table)
+{
+  int i;
+
+  ospf6_route_remove_all (table);
+  route_table_finish (table->table);
+  for (i = 0; i < 3; i++)
+    linklist_delete (table->hook_list[i]);
+  XFREE (MTYPE_OSPF6_ROUTE, table);
+}
+
+void
+ospf6_route_table_freeze (struct ospf6_route_table *route_table)
+{
+  if (IS_OSPF6_DUMP_ROUTE)
+    zlog_info ("ROUTE: Table freeze: %s", route_table->name);
+  assert (route_table->freeze == 0);
+  route_table->freeze = 1;
+}
+
+void
+ospf6_route_table_thaw (struct ospf6_route_table *route_table)
+{
+  struct route_node *node;
+  struct linklist_node pnode;
+  struct linklist_node nnode;
+
+  struct ospf6_route_node   *rn;
+  struct ospf6_path_node    *pn;
+  struct ospf6_nexthop_node *nn;
+
+  struct ospf6_route_req request;
+
+  if (IS_OSPF6_DUMP_ROUTE)
+    zlog_info ("ROUTE: Table thaw: %s", route_table->name);
+
+  assert (route_table->freeze == 1);
+  route_table->freeze = 0;
+
+  for (node = route_top (route_table->table); node;
+       node = route_next (node))
+    {
+      rn = node->info;
+      if (! rn)
+        continue;
+
+      for (linklist_head (rn->path_list, &pnode);
+           ! linklist_end (&pnode);
+           linklist_next (&pnode))
+        {
+          pn = pnode.data;
+
+          for (linklist_head (pn->nexthop_list, &nnode);
+               ! linklist_end (&nnode);
+               linklist_next (&nnode))
+            {
+              nn = nnode.data;
+
+              /* if the add and remove flag set without change flag,
+                 do nothing with this route */
+              if (! CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE) &&
+                  CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ADD) &&
+                  CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_REMOVE))
+                {
+                  nn->flag = 0;
+                  continue;
+                }
+
+              memset (&request, 0, sizeof (request));
+              memcpy (&request.route, &rn->route, sizeof (rn->route));
+              memcpy (&request.path, &pn->path, sizeof (pn->path));
+              memcpy (&request.nexthop, &nn->nexthop, sizeof (nn->nexthop));
+
+              if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_ADD) ||
+                  CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_CHANGE))
+                ospf6_route_add (&request, route_table);
+              else if (CHECK_FLAG (nn->flag, OSPF6_ROUTE_FLAG_REMOVE))
+                ospf6_route_remove (&request, route_table);
+            }
+        }
+    }
+}
+
+
+/* VTY commands */
+
+void
+ospf6_route_show (struct vty *vty, struct ospf6_route_node *rn)
+{
+  struct linklist_node pnode;
+  struct linklist_node nnode;
+  struct ospf6_path_node    *pn;
+  struct ospf6_nexthop_node *nn;
+
+  struct timeval now, res;
+  char duration[16];
+
+  u_int pc = 0;
+  u_int nc = 0;
+#define HEAD (pc == 0 && nc == 0)
+
+  char prefix[64], nexthop[64], ifname[IFNAMSIZ];
+
+  gettimeofday (&now, (struct timezone *) NULL);
+
+  /* destination */
+  if (rn->route.prefix.family == AF_INET ||
+      rn->route.prefix.family == AF_INET6)
+    prefix2str (&rn->route.prefix, prefix, sizeof (prefix));
+  else
+    prefix_ls2str (&rn->route.prefix, prefix, sizeof (prefix));
+
+  for (linklist_head (rn->path_list, &pnode); ! linklist_end (&pnode);
+       linklist_next (&pnode))
+    {
+      pn = pnode.data;
+
+      for (linklist_head (pn->nexthop_list, &nnode); ! linklist_end (&nnode);
+           linklist_next (&nnode))
+        {
+          nn = nnode.data;
+
+          inet_ntop (AF_INET6, &nn->nexthop.address, nexthop,
+                     sizeof (nexthop));
+          if (! if_indextoname (nn->nexthop.ifindex, ifname))
+            snprintf (ifname, sizeof (ifname), "%d", nn->nexthop.ifindex);
+
+          ospf6_timeval_sub (&now, &nn->installed, &res);
+          ospf6_timeval_string_summary (&res, duration, sizeof (duration));
+
+          vty_out (vty, "%c%1s %2s %-30s %-25s %6s %s%s",
+                   (HEAD ? '*' : ' '),
+                   DTYPE_ABNAME (rn->route.type),
+                   PTYPE_ABNAME (pn->path.type),
+                   prefix, nexthop, ifname, duration, VTY_NEWLINE);
+
+          nc++;
+        }
+      pc++;
+    }
+}
+
+void
+ospf6_route_show_detail (struct vty *vty, struct ospf6_route_node *rn)
+{
+  struct linklist_node pnode;
+  struct linklist_node nnode;
+  struct ospf6_path_node    *pn;
+  struct ospf6_nexthop_node *nn;
+
+  u_int pc = 0;
+  u_int nc = 0;
+
+  char prefix[64], nexthop[64], ifname[IFNAMSIZ];
+  char area_id[16], type[16], id[16], adv[16];
+  char capa[64];
+
+  /* destination */
+  if (rn->route.prefix.family == AF_INET ||
+      rn->route.prefix.family == AF_INET6)
+    prefix2str (&rn->route.prefix, prefix, sizeof (prefix));
+  else
+    prefix_ls2str (&rn->route.prefix, prefix, sizeof (prefix));
+
+  vty_out (vty, "%s%s%s", VTY_NEWLINE, prefix, VTY_NEWLINE);
+  vty_out (vty, "    Destination Type: %s%s",
+           DTYPE_NAME (rn->route.type), VTY_NEWLINE);
+
+  for (linklist_head (rn->path_list, &pnode); ! linklist_end (&pnode);
+       linklist_next (&pnode))
+    {
+      pn = pnode.data;
+
+      inet_ntop (AF_INET, &pn->path.area_id, area_id, sizeof (area_id));
+      ospf6_lsa_type_string (pn->path.origin.type, type, sizeof (type));
+      inet_ntop (AF_INET, &pn->path.origin.id, id, sizeof (id));
+      inet_ntop (AF_INET, &pn->path.origin.adv_router, adv, sizeof (adv));
+      ospf6_options_string (pn->path.capability, capa, sizeof (capa));
+
+      vty_out (vty, "  Path:%s", VTY_NEWLINE);
+      vty_out (vty, "    Associated Area: %s%s", area_id, VTY_NEWLINE);
+      vty_out (vty, "    LS Origin: %s ID: %s Adv: %s%s",
+               type, id, adv, VTY_NEWLINE);
+      vty_out (vty, "    Path Type: %s%s",
+               PTYPE_NAME (pn->path.type), VTY_NEWLINE);
+      vty_out (vty, "    Metric Type: %d%s",
+               pn->path.metric_type, VTY_NEWLINE);
+      vty_out (vty, "    Cost: Type-1: %lu Type-2: %lu%s",
+               (u_long) pn->path.cost, (u_long) pn->path.cost_e2,
+               VTY_NEWLINE);
+      vty_out (vty, "    Router Bits: %s|%s|%s|%s%s",
+               (CHECK_FLAG (pn->path.router_bits, OSPF6_ROUTER_LSA_BIT_W) ?
+                "W" : "-"),
+               (CHECK_FLAG (pn->path.router_bits, OSPF6_ROUTER_LSA_BIT_V) ?
+                "V" : "-"),
+               (CHECK_FLAG (pn->path.router_bits, OSPF6_ROUTER_LSA_BIT_E) ?
+                "E" : "-"),
+               (CHECK_FLAG (pn->path.router_bits, OSPF6_ROUTER_LSA_BIT_B) ?
+                "B" : "-"), VTY_NEWLINE);
+      vty_out (vty, "    Optional Capabilities: %s%s", capa, VTY_NEWLINE);
+      vty_out (vty, "    Prefix Options: %s%s", "xxx", VTY_NEWLINE);
+      vty_out (vty, "    Next Hops:%s", VTY_NEWLINE);
+
+      for (linklist_head (pn->nexthop_list, &nnode); ! linklist_end (&nnode);
+           linklist_next (&nnode))
+        {
+          nn = nnode.data;
+
+          inet_ntop (AF_INET6, &nn->nexthop.address, nexthop,
+                     sizeof (nexthop));
+          if (! if_indextoname (nn->nexthop.ifindex, ifname))
+            snprintf (ifname, sizeof (ifname), "%d", nn->nexthop.ifindex);
+
+          vty_out (vty, "       %c%s%%%s%s",
+                   (HEAD ? '*' : ' '), nexthop, ifname, VTY_NEWLINE);
+
+          nc++;
+        }
+      pc++;
+    }
+  vty_out (vty, "%s", VTY_NEWLINE);
+}
+
+int
+ospf6_route_table_show (struct vty *vty, int argc, char **argv,
+                        struct ospf6_route_table *table)
+{
+  int i, ret;
+  unsigned long ret_ul;
+  char *endptr;
+  struct prefix prefix;
+  int detail = 0;
+  int arg_ipv6  = 0;
+  int arg_ipv4  = 0;
+  int arg_digit = 0;
+  struct prefix_ipv6 *p6 = (struct prefix_ipv6 *) &prefix;
+  struct prefix_ls   *pl = (struct prefix_ls *) &prefix;
+  struct route_node *node;
+
+  u_int route_count = 0;
+  u_int path_count = 0;
+  u_int route_redundant = 0;
+
+  memset (&prefix, 0, sizeof (struct prefix));
+
+  for (i = 0; i < argc; i++)
+    {
+      if (! strcmp (argv[i], "detail"))
+        {
+          detail++;
+          break;
+        }
+
+      if (! arg_ipv6 && ! arg_ipv4 && ! arg_digit)
+        {
+
+          if ((ret = inet_pton (AF_INET6, argv[i], &p6->prefix)) == 1)
+            {
+              p6->family = AF_INET6;
+              p6->prefixlen = 128;
+              arg_ipv6++;
+              continue;
+            }
+          else if ((ret = inet_pton (AF_INET, argv[i], &pl->adv_router)) == 1)
+            {
+              pl->family = AF_UNSPEC;
+              pl->prefixlen = 64; /* xxx */
+              arg_ipv4++;
+              continue;
+            }
+          else
+            {
+              ret_ul = strtoul (argv[i], &endptr, 10);
+              if (*endptr == '\0')
+                {
+                  pl->adv_router.s_addr = htonl (ret_ul);
+                  pl->family = AF_UNSPEC;
+                  pl->prefixlen = 64; /* xxx */
+                  arg_digit++;
+                  continue;
+                }
+              else
+                {
+                  vty_out (vty, "Malformed argument: %s%s",
+                           argv[i], VTY_NEWLINE);
+                  return CMD_SUCCESS;
+                }
+            }
+        }
+
+      if (arg_ipv4 || arg_digit)
+        {
+          if ((ret = inet_pton (AF_INET, argv[i], &pl->id)) == 1)
+            {
+              arg_ipv4++;
+            }
+          else
+            {
+              ret_ul = strtoul (argv[i], &endptr, 10);
+              if (*endptr == '\0')
+                {
+                  pl->id.s_addr = htonl (ret_ul);
+                  arg_digit++;
+                }
+              else
+                {
+                  vty_out (vty, "Malformed argument: %s%s",
+                           argv[i], VTY_NEWLINE);
+                  return CMD_SUCCESS;
+                }
+            }
+        }
+    }
+
+  if (arg_ipv4 || arg_ipv6 || arg_digit)
+    {
+      node = route_node_match (table->table, &prefix);
+      if (node && node->info)
+        ospf6_route_show_detail (vty, node->info);
+      return CMD_SUCCESS;
+    }
+
+  if (! detail)
+    {
+      vty_out (vty, "%s%c%1s %2s %-30s %-25s %6s%s", VTY_NEWLINE,
+               ' ', " ", " ", "Destination", "Gateway", "I/F", VTY_NEWLINE);
+      vty_out (vty, "---------------------------%s", VTY_NEWLINE);
+    }
+
+  for (node = route_top (table->table); node; node = route_next (node))
+    {
+      struct ospf6_route_node *route = node->info;
+
+      if (! route)
+        continue;
+
+      if (detail)
+        ospf6_route_show_detail (vty, route);
+      else
+        ospf6_route_show (vty, route);
+
+      route_count++;
+      path_count += route->path_list->count;
+      if (route->path_list->count > 1)
+        route_redundant++;
+    }
+
+  vty_out (vty, "===========%s", VTY_NEWLINE);
+  vty_out (vty, "Route: %d Path: %d Redundant: %d%s",
+           route_count, path_count, route_redundant, VTY_NEWLINE);
+
+  return CMD_SUCCESS;
+}
+