ospf6_spf.c

zebra测试源代码用于 SOCKET 通信

        {
          if (type == htons (OSPF6_LSA_TYPE_ROUTER))
            zlog_info ("SPF: Can't find LSA for W (%s *): not found",
                      buf_router);
          else
            zlog_info ("SPF: Can't find LSA for W (%s %s): not found",
                      buf_router, buf_id);
        }
      return (struct ospf6_vertex *) NULL;
    }

  if (IS_LSA_MAXAGE (lsa))
    {
      if (IS_OSPF6_DUMP_SPF)
        zlog_info ("SPF: Associated LSA for W is MaxAge: %s", lsa->str);
      return (struct ospf6_vertex *) NULL;
    }

  /* Check back reference from W's lsa to V's lsa */
  backreference = 0;
  lsdnum = ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header);
  for (i = 0; i < lsdnum; i++)
    {
      if (ospf6_lsa_lsd_is_refer_ok (i, (struct ospf6_lsa_header *) lsa->header,
                                     index, (struct ospf6_lsa_header *) V->lsa->header))
        backreference++;
    }
  if (! backreference)
    {
      if (IS_OSPF6_DUMP_SPF)
        zlog_info ("SPF: Back reference failed: V: %s, W: %s",
                   V->lsa->str, lsa->str);
      return (struct ospf6_vertex *) NULL;
    }

  /* Allocate new ospf6_vertex for W */
  W = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX,
                                       sizeof (struct ospf6_vertex));
  if (! W)
    {
      zlog_err ("SPF: Can't allocate memory for Vertex");
      return (struct ospf6_vertex *) NULL;
    }
  memset (W, 0, sizeof (struct ospf6_vertex));

  /* Initialize */
  W->vertex_id.family = AF_UNSPEC;
  W->vertex_id.prefixlen = 64; /* xxx */
  W->lsa = lsa;
  if (type == htons (OSPF6_LSA_TYPE_ROUTER))
    W->vertex_id.id.s_addr = htonl (0); /* XXX */
  else
    W->vertex_id.id.s_addr = W->lsa->header->id;
  W->vertex_id.adv_router.s_addr = W->lsa->header->adv_router;
  W->nexthop_list = linklist_create ();
  W->path_list = list_new ();
  W->parent_list = list_new ();
  W->distance = V->distance + distance;
  W->depth = V->depth + 1;

  inet_ntop (AF_INET, &W->vertex_id.adv_router.s_addr,
             buf_router, sizeof (buf_router));
  inet_ntop (AF_INET, &W->vertex_id.id.s_addr, buf_id, sizeof (buf_id));
  snprintf (W->string, sizeof (W->string), "[%s-%s (%d)]",
            buf_router, buf_id, W->distance);

  /* capability bits and optional capabilities */
  if (W->vertex_id.id.s_addr == 0)
    {
      router_lsa = (struct ospf6_router_lsa *) (W->lsa->header + 1);
      W->capability_bits = router_lsa->bits;
      memcpy (W->opt_capability, router_lsa->options,
              sizeof (W->opt_capability));
    }
  else
    {
      network_lsa = (struct ospf6_network_lsa *) (W->lsa->header + 1);
      W->capability_bits = network_lsa->reserved;
      memcpy (W->opt_capability, network_lsa->options,
              sizeof (W->opt_capability));
    }

  /* Link to Parent node */
  listnode_add (W->parent_list, V);

  /* Nexthop Calculation */
  if (ospf6_spf_nexthop_calculation (W, ifindex, V, o6a->spf_tree) < 0)
    return NULL;

  return W;
}

static void
ospf6_spf_vertex_delete (struct ospf6_vertex *v)
{
  linklist_delete (v->nexthop_list);
  list_delete (v->path_list);
  list_delete (v->parent_list);
  XFREE (MTYPE_OSPF6_VERTEX, v);
}

static void
ospf6_spf_vertex_merge (struct ospf6_vertex *w, struct ospf6_vertex *x)
{
  listnode node;
  struct linklist_node lnode;

  /* merge should be done on two nodes which are
     almost the same */

  /* these w and x should be both candidate.
     candidate should not have any children */
  assert (list_isempty (w->path_list));
  assert (list_isempty (x->path_list));

  /* merge parent list */
  for (node = listhead (w->parent_list); node; nextnode (node))
    {
      if (listnode_lookup (x->parent_list, getdata (node)))
        continue;
      listnode_add (x->parent_list, getdata (node));
    }

  /* merge nexthop list */
  for (linklist_head (w->nexthop_list, &lnode); ! linklist_end (&lnode);
       linklist_next (&lnode))
    linklist_add (lnode.data, x->nexthop_list);
}

static void
ospf6_spf_initialize (list candidate_list, struct ospf6_area *o6a)
{
  listnode node;
  struct ospf6_vertex *v;
  struct ospf6_lsa *lsa;
  u_int16_t type;
  u_int32_t id, adv_router;
  struct linklist_node lnode;

  struct ospf6_nexthop *nexthop;
  struct interface *ifp;
  char buf_router[64], buf_id[64];

  /* delete topology routing table for this area */
  ospf6_route_remove_all (o6a->table_topology);

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

  for (linklist_head (nexthop_list, &lnode); ! linklist_end (&lnode);
       linklist_next (&lnode))
    XFREE (MTYPE_OSPF6_VERTEX, lnode.data);
  linklist_remove_all (nexthop_list);

  /* Find self originated Router-LSA */
  type = htons (OSPF6_LSA_TYPE_ROUTER);
  id = htonl (0);
  adv_router = ospf6->router_id;

  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);

  if (! lsa)
    {
      if (IS_OSPF6_DUMP_SPF)
        zlog_info ("SPF: Can't find self originated Router-LSA");
      return;
    }
  if (IS_LSA_MAXAGE (lsa))
    {
      zlog_err ("SPF: MaxAge self originated Router-LSA");
      return;
    }

  /* Create root vertex */
  v = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX,
                                       sizeof (struct ospf6_vertex));
  if (! v)
    {
      zlog_err ("SPF: Can't allocate memory for root vertex");
      return;
    }
  memset (v, 0, sizeof (struct ospf6_vertex));

  v->vertex_id.family = AF_UNSPEC; /* XXX */
  v->vertex_id.prefixlen = 64; /* XXX */
  v->vertex_id.id.s_addr = htonl (0);
  v->vertex_id.adv_router.s_addr = ospf6->router_id;
  if (ospf6_is_asbr (ospf6))
    OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_E);
  OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_V6);
  OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_R);
  v->nexthop_list = linklist_create ();
  v->path_list = list_new ();
  v->parent_list = list_new ();
  v->distance = 0;
  v->depth = 0;
  v->lsa = lsa;

  inet_ntop (AF_INET, &v->vertex_id.adv_router.s_addr,
             buf_router, sizeof (buf_router));
  inet_ntop (AF_INET, &v->vertex_id.id.s_addr, buf_id, sizeof (buf_id));
  snprintf (v->string, sizeof (v->string), "[%s-%s (%d)]",
            buf_router, buf_id, v->distance);

  nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop));
  ifp = if_lookup_by_name ("lo0");
  if (ifp)
    nexthop->ifindex = ifp->ifindex;
  inet_pton (AF_INET6, "::1", &nexthop->address);
  linklist_add (nexthop, v->nexthop_list);
  linklist_add (nexthop, nexthop_list);

  o6a->spf_tree->root = v;
  listnode_add (candidate_list, v);

  ospf6_spf_candidate_enqueue (v);
}

static struct ospf6_vertex *
ospf6_spf_get_closest_candidate (list candidate_list)
{
  listnode node;
  struct ospf6_vertex *candidate, *closest;

  closest = (struct ospf6_vertex *) NULL;
  for (node = listhead (candidate_list); node; nextnode (node))
    {
      candidate = (struct ospf6_vertex *) getdata (node);

      if (closest && candidate->distance > closest->distance)
        continue;

      /* always choose network vertices if those're the same cost */
      if (closest && candidate->distance == closest->distance
          && closest->vertex_id.id.s_addr != 0)
        continue;

      closest = candidate;
    }

  return closest;
}

static struct ospf6_vertex *
ospf6_spf_get_same_candidate (struct ospf6_vertex *w, list candidate_list)
{
  listnode node;
  struct ospf6_vertex *c, *same;

  same = (struct ospf6_vertex *) NULL;
  for (node = listhead (candidate_list); node; nextnode (node))
    {
      c = (struct ospf6_vertex *) getdata (node);
      if (w->vertex_id.adv_router.s_addr != c->vertex_id.adv_router.s_addr)
        continue;
      if (w->vertex_id.id.s_addr != c->vertex_id.id.s_addr)
        continue;

      if (same)
        zlog_warn ("SPF: duplicate candidates in candidate_list");

      same = c;
    }

  return same;
}

static void
ospf6_spf_install (struct ospf6_vertex *vertex, struct ospf6_area *o6a)
{
  listnode node;
  struct ospf6_vertex *parent;
  struct ospf6_nexthop *nexthop;
  struct ospf6_route_req request;
  struct linklist_node lnode;

  struct ospf6_router_lsa *router_lsa;
  struct ospf6_network_lsa *network_lsa;

  router_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header);
  network_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header);

  if (IS_OSPF6_DUMP_SPF)
    {
      zlog_info ("SPF: Install: %s", vertex->string);
    }

  listnode_add (o6a->spf_tree->list, vertex);

  for (node = listhead (vertex->parent_list); node; nextnode (node))
    {
      parent = (struct ospf6_vertex *) getdata (node);
      listnode_add (parent->path_list, vertex);
      vertex->depth = parent->depth + 1;
    }

#if 0
  if (vertex == o6a->spf_tree->root)
    return;
#endif /*0*/

  /* install route to topology table */
  memset (&request, 0, sizeof (request));
  if (vertex->vertex_id.id.s_addr) /* xxx */
    request.route.type = OSPF6_DEST_TYPE_NETWORK;
  else
    request.route.type = OSPF6_DEST_TYPE_ROUTER;
  memcpy (&request.route.prefix, &vertex->vertex_id,
          sizeof (struct prefix));

  request.path.area_id = o6a->area_id;
  request.path.type = OSPF6_PATH_TYPE_INTRA;
  request.path.cost = vertex->distance;
  request.path.cost_e2 = 0;
  request.path.origin.type = vertex->lsa->header->type;
  request.path.origin.id = vertex->lsa->header->id;
  request.path.origin.adv_router = vertex->lsa->header->adv_router;
  if (vertex->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER))
    request.path.router_bits = router_lsa->bits;
  memcpy (&request.path.capability, vertex->opt_capability,
          sizeof (request.path.capability));

#if 0
  if (IS_OSPF6_DUMP_SPF)
    zlog_info ("SPF:   install %d nexthops for %s",
               listcount (vertex->nexthop_list), vertex->string);
#endif

  for (linklist_head (vertex->nexthop_list, &lnode); ! linklist_end (&lnode);
       linklist_next (&lnode))
    {
      nexthop = lnode.data;

      request.nexthop.ifindex = nexthop->ifindex;
      memcpy (&request.nexthop.address, &nexthop->address,
              sizeof (request.nexthop.address));

      ospf6_route_add (&request, o6a->table_topology);
    }
}

struct ospf6_vertex *
ospf6_spf_lookup (struct ospf6_vertex *w, struct ospf6_area *o6a)
{
  listnode node;
  struct ospf6_vertex *v;

  for (node = listhead (o6a->spf_tree->list); node; nextnode (node))
    {
      v = (struct ospf6_vertex *) getdata (node);

      if (w->vertex_id.adv_router.s_addr != v->vertex_id.adv_router.s_addr)
        continue;
      if (w->vertex_id.id.s_addr != v->vertex_id.id.s_addr)
        continue;

      return v;
    }

  return (struct ospf6_vertex *) NULL;
}

u_int32_t stat_node = 0;
u_int32_t stat_candidate = 0;
u_int32_t stat_candidate_max = 0;
u_int32_t stat_spf = 0;


/* RFC2328 section 16.1 , RFC2740 section 3.8.1 */
static int
ospf6_spf_calculation (struct ospf6_area *o6a)
{
  list candidate_list;
  struct ospf6_vertex *V, *W, *X;
  int ldnum, i;

  if (! o6a || ! o6a->spf_tree)
    {
      zlog_err ("SPF: Can't calculate SPF tree: malformed area");
      return -1;
    }

  stat_spf ++;
  stat_node = 0;
  stat_candidate = 0;
  stat_candidate_max = 0;

  if (IS_OSPF6_DUMP_SPF)
    zlog_info ("SPF: Calculation for area %s", o6a->str);

  ospf6_route_table_freeze (o6a->table_topology);
  ospf6_route_remove_all (o6a->table_topology);

  /* (1): Initialize the algorithm's data structures */
  candidate_list = list_new ();
  ospf6_spf_initialize (candidate_list, o6a);
  stat_candidate ++;

  /* (3): Install closest from candidate list; if empty, break */
  while (listcount (candidate_list))
    {
      V = ospf6_spf_get_closest_candidate (candidate_list);
      listnode_delete (candidate_list, V);

      {
        struct ospf6_vertex *V_;

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

        V_ = ospf6_spf_candidate_dequeue ();

#if 0
        if (IS_OSPF6_DUMP_SPF)
          {
            zlog_info ("Candidate list count: %lu",
                       (u_long)ospf6_spf_candidate_count ());
            zlog_info ("*** Candidate %s: %p <-> %p",
                       (V == V_ ? "same" : "*** differ ***"), V, V_);
            zlog_info ("  %p: %s", V, V->string);
            zlog_info ("  %p: %s", V_, V_->string);
          }
#endif

      }

      stat_node++;
      ospf6_spf_install (V, o6a);

      /* (2): Examin LSA of just added vertex */
      ldnum = ospf6_spf_lsd_num (V, o6a);
      for (i = 0; i < ldnum; i++)
        {
          /* (b): If no LSA, or MaxAge, or LinkBack fail, examin next */
          W = ospf6_spf_vertex_create (i, V, o6a);
          if (! W)
            continue;

          stat_candidate ++;

          /* (c) */
          if (ospf6_spf_lookup (W, o6a))
            {
              if (IS_OSPF6_DUMP_SPF)
                zlog_info ("SPF:   %s: Already in SPF tree", W->string);
              ospf6_spf_vertex_delete (W);
              continue;
            }

          /* (d) */
          X = ospf6_spf_get_same_candidate (W, candidate_list);
          if (X && X->distance < W->distance)
            {
              if (IS_OSPF6_DUMP_SPF)
                zlog_info ("SPF:   %s: More closer found", W->string);
              ospf6_spf_vertex_delete (W);
              continue;
            }
          if (X && X->distance == W->distance)
            {
              if (IS_OSPF6_DUMP_SPF)
                zlog_info ("SPF:   %s: new ECMP candidate", W->string);
              ospf6_spf_vertex_merge (W, X);
              ospf6_spf_vertex_delete (W);
              continue;
            }

          if (X)
            {
              if (IS_OSPF6_DUMP_SPF)
                zlog_info ("SPF:   %s: Swap with old candidate", W->string);
              listnode_delete (candidate_list, X);
              ospf6_spf_candidate_remove (X);
              ospf6_spf_vertex_delete (X);
            }
          else
            {
              if (IS_OSPF6_DUMP_SPF)
                zlog_info ("SPF:   %s: New Candidate", W->string);
            }