ospf6_spf.c

zebra测试源代码用于 SOCKET 通信

          if (stat_candidate_max < ospf6_spf_candidate_count ())
            stat_candidate_max = ospf6_spf_candidate_count ();

          listnode_add (candidate_list, W);
          ospf6_spf_candidate_enqueue (W);
        }
    }

  assert (listcount (candidate_list) == 0);
  list_free (candidate_list);
  assert (ospf6_spf_candidate_count () == 0);

  /* Clear thread timer */
  o6a->spf_tree->t_spf_calculation = (struct thread *) NULL;

  if (IS_OSPF6_DUMP_SPF)
    {
      zlog_info ("SPF: Calculation for area %s done", o6a->str);
      zlog_info ("SPF:   Statistics: %luth", (u_long)stat_spf);
      zlog_info ("SPF:   Node Number: %lu", (u_long)stat_node);
      zlog_info ("SPF:   Candidate Number: %lu Max: %lu",
                 (u_long) stat_candidate, (u_long) stat_candidate_max);
    }

  ospf6_route_table_thaw (o6a->table_topology);
  return 0;
}

int
ospf6_spf_calculation_thread (struct thread *t)
{
  struct ospf6_area *o6a;
  struct timeval start, end, runtime, interval;

  o6a = (struct ospf6_area *) THREAD_ARG (t);
  if (! o6a)
    {
      zlog_err ("SPF: Thread error");
      return -1;
    }

  if (! o6a->spf_tree)
    {
      zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str);
      return -1;
    }

  /* execute SPF calculation */
  gettimeofday (&start, (struct timezone *) NULL);
  ospf6_spf_calculation (o6a);
  gettimeofday (&end, (struct timezone *) NULL);

  /* update statistics */
  o6a->spf_tree->timerun ++;
  ospf6_timeval_sub (&end, &start, &runtime);
  ospf6_timeval_add_equal (&runtime, &o6a->spf_tree->runtime_total);

  if (o6a->spf_tree->timerun == 1)
    {
      o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec;
      o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec;
      o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec;
      o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec;
    }
  if (ospf6_timeval_cmp (o6a->spf_tree->runtime_min, runtime) > 0)
    {
      o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec;
      o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec;
    }
  if (ospf6_timeval_cmp (runtime, o6a->spf_tree->runtime_max) > 0)
    {
      o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec;
      o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec;
    }

  if (o6a->spf_tree->timerun == 1)
    {
      ospf6_timeval_sub (&start, &ospf6->starttime, &interval);
      ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total);
      o6a->spf_tree->interval_min.tv_sec = interval.tv_sec;
      o6a->spf_tree->interval_min.tv_usec = interval.tv_usec;
      o6a->spf_tree->interval_max.tv_sec = interval.tv_sec;
      o6a->spf_tree->interval_max.tv_usec = interval.tv_usec;
    }
  else
    {
      ospf6_timeval_sub (&start, &o6a->spf_tree->updated_time, &interval);
      ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total);
      if (ospf6_timeval_cmp (o6a->spf_tree->interval_min, interval) > 0)
        {
          o6a->spf_tree->interval_min.tv_sec = interval.tv_sec;
          o6a->spf_tree->interval_min.tv_usec = interval.tv_usec;
        }
      if (ospf6_timeval_cmp (interval, o6a->spf_tree->interval_max) > 0)
        {
          o6a->spf_tree->interval_max.tv_sec = interval.tv_sec;
          o6a->spf_tree->interval_max.tv_usec = interval.tv_usec;
        }
    }
  o6a->spf_tree->updated_time.tv_sec = end.tv_sec;
  o6a->spf_tree->updated_time.tv_usec = end.tv_usec;

  /* clear thread */
  o6a->spf_tree->t_spf_calculation = (struct thread *) NULL;

  return 0;
}

void
ospf6_spf_database_hook (struct ospf6_lsa *old, struct ospf6_lsa *new)
{
  struct ospf6_area *o6a = NULL;
  struct ospf6_interface *o6i = NULL;

  if (new->header->type == htons (OSPF6_LSA_TYPE_ROUTER) ||
      new->header->type == htons (OSPF6_LSA_TYPE_NETWORK))
    o6a = new->scope;
  else if (new->header->type == htons (OSPF6_LSA_TYPE_LINK))
    {
      o6i = new->scope;
      o6a = o6i->area;
    }

  if (o6a)
    ospf6_spf_calculation_schedule (o6a->area_id);
}

void
ospf6_spf_calculation_schedule (u_int32_t area_id)
{
  struct ospf6_area *o6a;
  char buf[64];

  o6a = ospf6_area_lookup (area_id, ospf6);
  if (! o6a)
    {
      inet_ntop (AF_INET, &area_id, buf, sizeof (buf));
      zlog_err ("SPF: Can't find area: %s", buf);
      return;
    }

  if (! o6a->spf_tree)
    {
      zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str);
      return;
    }

  if (o6a->spf_tree->t_spf_calculation)
    return;

  o6a->spf_tree->t_spf_calculation =
    thread_add_event (master, ospf6_spf_calculation_thread, o6a, 0);
}

struct ospf6_spftree *
ospf6_spftree_create ()
{
  struct ospf6_spftree *spf_tree;
  spf_tree = (struct ospf6_spftree *) XMALLOC (MTYPE_OSPF6_SPFTREE,
                                               sizeof (struct ospf6_spftree));
  if (! spf_tree)
    {
      zlog_err ("SPF: Can't allocate memory for SPF tree");
      return (struct ospf6_spftree *) NULL;
    }
  memset (spf_tree, 0, sizeof (spf_tree));

  spf_tree->list = list_new ();

  return spf_tree;
}

void
ospf6_spftree_delete (struct ospf6_spftree *spf_tree)
{
  listnode node;
  struct ospf6_vertex *v;

  /* Delete spf tree */
  for (node = listhead (spf_tree->list); node; nextnode (node))
    {
      v = (struct ospf6_vertex *) getdata (node);
      ospf6_spf_vertex_delete (v);
    }
  list_delete_all_node (spf_tree->list);

  XFREE (MTYPE_OSPF6_SPFTREE, spf_tree);
}

void
ospf6_nexthop_show (struct vty *vty, struct ospf6_nexthop *nexthop)
{
  char buf[128], *ifname;
  struct ospf6_interface *o6i;

  ifname = NULL;

  o6i = ospf6_interface_lookup_by_index (nexthop->ifindex);
  if (! o6i)
    {
      zlog_err ("Spf: invalid ifindex %d in nexthop", nexthop->ifindex);
    }
  else
    ifname = o6i->interface->name;

  inet_ntop (AF_INET6, &nexthop->address, buf, sizeof (buf));
  vty_out (vty, "    %s%%%s(%d)%s", buf, ifname,
           nexthop->ifindex, VTY_NEWLINE);
}

void
ospf6_vertex_show (struct vty *vty, struct ospf6_vertex *vertex)
{
  listnode node;
  struct ospf6_vertex *v;
  struct linklist_node lnode;

  vty_out (vty, "SPF node %s%s", vertex->string, VTY_NEWLINE);
  vty_out (vty, "  cost to this node: %d%s", vertex->distance, VTY_NEWLINE);
  vty_out (vty, "  hops to this node: %d%s", vertex->depth, VTY_NEWLINE);

  vty_out (vty, "  nexthops reachable to this node:%s", VTY_NEWLINE);
  for (linklist_head (vertex->nexthop_list, &lnode);
       ! linklist_end (&lnode);
       linklist_next (&lnode))
    ospf6_nexthop_show (vty, (struct ospf6_nexthop *) lnode.data);

  vty_out (vty, "  parent nodes to this node:%s", VTY_NEWLINE);
  if (! list_isempty (vertex->parent_list))
    vty_out (vty, "    ");
  for (node = listhead (vertex->parent_list); node; nextnode (node))
    {
      v = (struct ospf6_vertex *) getdata (node);
      vty_out (vty, "%s ", v->string);
    }
  if (! list_isempty (vertex->parent_list))
    vty_out (vty, "%s", VTY_NEWLINE);

  vty_out (vty, "  child nodes to this node:%s", VTY_NEWLINE);
  if (! list_isempty (vertex->path_list))
    vty_out (vty, "    ");
  for (node = listhead (vertex->path_list); node; nextnode (node))
    {
      v = (struct ospf6_vertex *) getdata (node);
      vty_out (vty, "%s ", v->string);
    }
  if (! list_isempty (vertex->path_list))
    vty_out (vty, "%s", VTY_NEWLINE);

  vty_out (vty, "%s", VTY_NEWLINE);
}

void
ospf6_spf_statistics_show (struct vty *vty, struct ospf6_spftree *spf_tree)
{
  listnode node;
  struct ospf6_vertex *vertex;
  u_int router_count, network_count, maxdepth;
  struct timeval runtime_avg, interval_avg, last_updated, now;
  char rmin[64], rmax[64], ravg[64];
  char imin[64], imax[64], iavg[64];
  char last_updated_string[64];

  maxdepth = router_count = network_count = 0;
  for (node = listhead (spf_tree->list); node; nextnode (node))
    {
      vertex = (struct ospf6_vertex *) getdata (node);
      if (vertex->vertex_id.id.s_addr)
        network_count++;
      else
        router_count++;
      if (maxdepth < vertex->depth)
        maxdepth = vertex->depth;
    }

  ospf6_timeval_div (&spf_tree->runtime_total, spf_tree->timerun,
                     &runtime_avg);
  ospf6_timeval_string (&spf_tree->runtime_min, rmin, sizeof (rmin));
  ospf6_timeval_string (&spf_tree->runtime_max, rmax, sizeof (rmax));
  ospf6_timeval_string (&runtime_avg, ravg, sizeof (ravg));

  ospf6_timeval_div (&spf_tree->interval_total, spf_tree->timerun,
                     &interval_avg);
  ospf6_timeval_string (&spf_tree->interval_min, imin, sizeof (imin));
  ospf6_timeval_string (&spf_tree->interval_max, imax, sizeof (imax));
  ospf6_timeval_string (&interval_avg, iavg, sizeof (iavg));

  gettimeofday (&now, (struct timezone *) NULL);
  ospf6_timeval_sub (&now, &spf_tree->updated_time, &last_updated);
  ospf6_timeval_string (&last_updated, last_updated_string,
                        sizeof (last_updated_string));

  vty_out (vty, "     SPF algorithm executed %d times%s", 
           spf_tree->timerun, VTY_NEWLINE);
  vty_out (vty, "     Average time to run SPF: %s%s",
           ravg, VTY_NEWLINE);
  vty_out (vty, "     Maximum time to run SPF: %s%s",
           rmax, VTY_NEWLINE);
  vty_out (vty, "     Average interval of SPF: %s%s",
           iavg, VTY_NEWLINE);
  vty_out (vty, "     SPF last updated: %s ago%s",
           last_updated_string, VTY_NEWLINE);
  vty_out (vty, "     Current SPF node count: %d%s",
           listcount (spf_tree->list), VTY_NEWLINE);
  vty_out (vty, "       Router: %d Network: %d%s",
           router_count, network_count, VTY_NEWLINE);
  vty_out (vty, "       Maximum of Hop count to nodes: %d%s",
           maxdepth, VTY_NEWLINE);
}

DEFUN (show_ipv6_ospf6_area_spf_node,
       show_ipv6_ospf6_area_spf_node_cmd,
       "show ipv6 ospf6 area A.B.C.D spf node",
       SHOW_STR
       IP6_STR
       OSPF6_STR
       OSPF6_AREA_STR
       OSPF6_AREA_ID_STR
       "Shortest Path First caculation\n"
       "vertex infomation\n"
       )
{
  listnode i;
  u_int32_t area_id;
  struct ospf6_area *o6a;
  struct ospf6_vertex *vertex;

  OSPF6_CMD_CHECK_RUNNING ();

  inet_pton (AF_INET, argv[0], &area_id);
  o6a = ospf6_area_lookup (area_id, ospf6);
  if (! o6a)
    return CMD_SUCCESS;

  for (i = listhead (o6a->spf_tree->list); i; nextnode (i))
    {
      vertex = (struct ospf6_vertex *) getdata (i);
      ospf6_vertex_show (vty, vertex);
    }

  return CMD_SUCCESS;
}

static void
ospf6_spftree_show (struct vty *vty, char *prefix, int current_rest,
                    struct ospf6_vertex *v)
{
  char *p;
  int psize;
  int restnum;
  listnode node;

  vty_out (vty, "%s+-%s%s", prefix, v->string, VTY_NEWLINE);

  if (listcount (v->path_list) == 0)
    return;

  psize = strlen (prefix) + 3;
  p = malloc (psize);
  if (!p)
    {
      vty_out (vty, "depth too long ...%s", VTY_NEWLINE);
      return;
    }

  restnum = listcount (v->path_list);
  for (node = listhead (v->path_list); node; nextnode (node))
    {
      --restnum;
      snprintf (p, psize, "%s%s", prefix, (current_rest ? "| " : "  "));
      ospf6_spftree_show (vty, p, restnum,
                          (struct ospf6_vertex *) getdata (node));
    }

  free (p);
}

DEFUN (show_ipv6_ospf6_area_spf_tree,
       show_ipv6_ospf6_area_spf_tree_cmd,
       "show ipv6 ospf6 area A.B.C.D spf tree",
       SHOW_STR
       IP6_STR
       OSPF6_STR
       OSPF6_AREA_STR
       OSPF6_AREA_ID_STR
       "Shortest Path First caculation\n"
       "Displays spf tree\n")
{
  u_int32_t area_id;
  struct ospf6_area *o6a;

  OSPF6_CMD_CHECK_RUNNING ();

  inet_pton (AF_INET, argv[0], &area_id);
  o6a = ospf6_area_lookup (area_id, ospf6);
  if (! o6a)
    return CMD_SUCCESS;

  vty_out (vty, "%s        SPF tree for Area %s%s%s",
           VTY_NEWLINE, o6a->str, VTY_NEWLINE, VTY_NEWLINE);

  if (! o6a->spf_tree->root)
    return CMD_SUCCESS;

  ospf6_spftree_show (vty, "", 0, o6a->spf_tree->root);
  return CMD_SUCCESS;
}

DEFUN (show_ipv6_ospf6_area_topology,
       show_ipv6_ospf6_area_topology_cmd,
       "show ipv6 ospf6 area A.B.C.D topology",
       SHOW_STR
       IP6_STR
       OSPF6_STR
       OSPF6_AREA_STR
       OSPF6_AREA_ID_STR
       OSPF6_SPF_STR
       "Displays SPF topology table\n")
{
  struct ospf6_area *o6a;
  u_int32_t area_id;

  OSPF6_CMD_CHECK_RUNNING ();

  inet_pton (AF_INET, argv[0], &area_id);
  o6a = ospf6_area_lookup (area_id, ospf6);

  if (! o6a)
    return CMD_SUCCESS;

  argc -= 1;
  argv += 1;

  return ospf6_route_table_show (vty, argc, argv, o6a->table_topology);
}

ALIAS (show_ipv6_ospf6_area_topology,
       show_ipv6_ospf6_area_topology_router_cmd,
       "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>|detail)",
       SHOW_STR
       IP6_STR
       OSPF6_STR
       OSPF6_AREA_STR
       OSPF6_AREA_ID_STR
       OSPF6_SPF_STR
       "Displays SPF topology table\n"
       OSPF6_ROUTER_ID_STR
       OSPF6_ROUTER_ID_STR
       );

ALIAS (show_ipv6_ospf6_area_topology,
       show_ipv6_ospf6_area_topology_router_lsid_cmd,
       "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>) (A.B.C.D|<0-4294967295>)",
       SHOW_STR
       IP6_STR
       OSPF6_STR
       OSPF6_AREA_STR
       OSPF6_AREA_ID_STR
       OSPF6_SPF_STR
       "Displays SPF topology table\n"
       OSPF6_ROUTER_ID_STR
       OSPF6_ROUTER_ID_STR
       OSPF6_LS_ID_STR
       OSPF6_LS_ID_STR
       );

void
ospf6_spf_init ()
{
  nexthop_list = linklist_create ();
  ospf6_spf_candidate_init ();
  install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_node_cmd);
  install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_tree_cmd);
  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_cmd);
  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_cmd);
  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd);
  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_node_cmd);
  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_tree_cmd);
  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_cmd);
  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_cmd);
  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd);
}