ospf6_spf.c

zebra测试源代码用于 SOCKET 通信

/*
 * 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.  
 */
/* Shortest Path First calculation for OSPFv3 */

#include "ospf6d.h"

#include "linklist.h"
#include "prefix.h"
#include "table.h"

#include "ospf6_proto.h"
#include "ospf6_lsa.h"
#include "ospf6_lsdb.h"
#include "ospf6_route.h"
#include "ospf6_spf.h"
#include "ospf6_neighbor.h"
#include "ospf6_interface.h"
#include "ospf6_area.h"

#include "ospf6_bintree.h"
#include "ospf6_linklist.h"

struct bintree *_candidate_list;
struct linklist *nexthop_list;

struct ospf6_spf_candidate_node
{
  u_int32_t cost;
  struct linklist *list;
};

int
ospf6_spf_candidate_node_cmp (void *a, void *b)
{
  struct ospf6_spf_candidate_node *ca = a;
  struct ospf6_spf_candidate_node *cb = b;
  return ca->cost - cb->cost;
}

int
ospf6_spf_vertex_cmp (void *a, void *b)
{
  return 1;
}

void
ospf6_spf_candidate_node_print (int indent_num, void *node)
{
  struct ospf6_spf_candidate_node *cn = node;
  char format[256];

  snprintf (format, sizeof (format), "%%%ds %%d (num: %%d)",
            indent_num * 2 + 1);
  zlog_info (format, " ", cn->cost, cn->list->count);
}

void
ospf6_spf_candidate_init ()
{
  _candidate_list = bintree_create ();
  _candidate_list->cmp = ospf6_spf_candidate_node_cmp;
}

u_int32_t
ospf6_spf_candidate_count ()
{
  u_int32_t count = 0;
  struct bintree_node node;
  struct ospf6_spf_candidate_node *cnode;

  for (bintree_head (_candidate_list, &node); ! bintree_end (&node);
       bintree_next (&node))
    {
      cnode = node.data;
      count += cnode->list->count;
    }

  return count;
}

void
ospf6_spf_candidate_print ()
{
  zlog_info ("---------------------------");
  bintree_print (ospf6_spf_candidate_node_print, _candidate_list);
  zlog_info ("---------------------------");
}

void
ospf6_spf_candidate_enqueue (struct ospf6_vertex *v)
{
  struct ospf6_spf_candidate_node req, *node;

  memset (&req, 0, sizeof (req));
  req.cost = v->distance;
  node = bintree_lookup (&req, _candidate_list);

  if (node == NULL)
    {
      node = malloc (sizeof (struct ospf6_spf_candidate_node));
      node->cost = v->distance;
      node->list = linklist_create ();
      node->list->cmp = ospf6_spf_vertex_cmp;
      bintree_add (node, _candidate_list);
    }

  linklist_add (v, node->list);

#if 0
  if (IS_OSPF6_DUMP_SPF)
    ospf6_spf_candidate_print ();
#endif
}

struct ospf6_vertex *
ospf6_spf_candidate_dequeue ()
{
  struct ospf6_spf_candidate_node *node;
  struct linklist_node lnode;
  struct ospf6_vertex *ret;

  node = bintree_lookup_min (_candidate_list);
  if (node == NULL)
    return NULL;

  linklist_head (node->list, &lnode);
  ret = lnode.data;

  linklist_remove (ret, node->list);
  if (node->list->count == 0)
    {
      linklist_delete (node->list);
      bintree_remove (node, _candidate_list);
    }

#if 0
  if (IS_OSPF6_DUMP_SPF)
    ospf6_spf_candidate_print ();
#endif

  return ret;
}

void
ospf6_spf_candidate_remove (struct ospf6_vertex *v)
{
  struct bintree_node node;
  struct ospf6_spf_candidate_node *cnode = NULL;

  for (bintree_head (_candidate_list, &node); ! bintree_end (&node);
       bintree_next (&node))
    {
      cnode = node.data;
      if (linklist_lookup (v, cnode->list))
        {
          linklist_remove (v, cnode->list);
          break;
        }
    }

  if (cnode->list->count == 0)
    {
      linklist_delete (cnode->list);
      bintree_remove (cnode, _candidate_list);
    }
}


#define TIMER_SEC_MICRO 1000000

/* timeval calculation */
static void
ospf6_timeval_add (const struct timeval *t1, const struct timeval *t2,
                   struct timeval *result)
{
  long moveup = 0;

  result->tv_usec = t1->tv_usec + t2->tv_usec;
  while (result->tv_usec > TIMER_SEC_MICRO)
    {
      result->tv_usec -= TIMER_SEC_MICRO;
      moveup ++;
    }

  result->tv_sec = t1->tv_sec + t2->tv_sec + moveup;
}

static void
ospf6_timeval_add_equal (const struct timeval *t, struct timeval *result)
{
  struct timeval tmp;
  ospf6_timeval_add (t, result, &tmp);
  result->tv_sec = tmp.tv_sec;
  result->tv_usec = tmp.tv_usec;
}

/* Compare timeval a and b.  It returns an integer less than, equal
   to, or great than zero if a is found, respectively, to be less
   than, to match, or be greater than b.  */
static int
ospf6_timeval_cmp (const struct timeval t1, const struct timeval t2)
{
  return (t1.tv_sec == t2.tv_sec
	  ? t1.tv_usec - t2.tv_usec : t1.tv_sec - t2.tv_sec);
}


static int
ospf6_spf_lsd_num (struct ospf6_vertex *V, struct ospf6_area *o6a)
{
  u_int16_t type;
  u_int32_t id, adv_router;
  struct ospf6_lsa *lsa;

  if (V->vertex_id.id.s_addr)
    type = htons (OSPF6_LSA_TYPE_NETWORK);
  else
    type = htons (OSPF6_LSA_TYPE_ROUTER);
  id = V->vertex_id.id.s_addr;
  adv_router = V->vertex_id.adv_router.s_addr;

  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);
  if (! lsa)
    {
      zlog_err ("SPF: Can't find associated LSA for %s", V->string);
      return 0;
    }

  return ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header);
}

/* RFC2328 section 16.1.1:
   Check if there is at least one router in the path
   from the root to this vertex. */
static int
ospf6_spf_is_router_to_root (struct ospf6_vertex *c,
                             struct ospf6_spftree *spf_tree)
{
  listnode node;
  struct ospf6_vertex *p;

  if (spf_tree->root == c)
    return 0;

  for (node = listhead (c->parent_list); node; nextnode (node))
    {
      p = (struct ospf6_vertex *) getdata (node);

      if (p == spf_tree->root)
        return 0;

      if (p->vertex_id.id.s_addr == 0) /* this is router */
        continue;
      else if (ospf6_spf_is_router_to_root (p, spf_tree))
        continue;

      return 0;
    }

  return 1;
}

static struct in6_addr *
ospf6_spf_get_ipaddr (u_int32_t id, u_int32_t adv_router, u_int32_t ifindex)
{
  char buf[64], nhbuf[64];
  struct ospf6_interface *o6i;
  struct ospf6_neighbor *o6n;
  struct ospf6_lsa *lsa;
  struct ospf6_lsdb_node node;

  o6i = ospf6_interface_lookup_by_index (ifindex);
  if (! o6i)
    {
      zlog_err ("SPF: Can't find interface: index %d", ifindex);
      return (struct in6_addr *) NULL;
    }

  /* Find Link-LSA of the vertex in question */
  lsa = NULL;
  for (ospf6_lsdb_type_router (&node, htons (OSPF6_LSA_TYPE_LINK),
                               adv_router, o6i->lsdb);
       ! ospf6_lsdb_is_end (&node);
       ospf6_lsdb_next (&node))
    lsa = node.lsa;

  /* return Linklocal Address field if the Link-LSA exists */
  if (lsa && lsa->header->adv_router == adv_router)
    {
      struct ospf6_link_lsa *link_lsa;
      link_lsa = (struct ospf6_link_lsa *) (lsa->header + 1);
      return &link_lsa->llsa_linklocal;
    }

  zlog_warn ("SPF: Can't find Link-LSA for %s",
             inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)));

  o6n = ospf6_neighbor_lookup (adv_router, o6i);
  if (! o6n)
    {
      inet_ntop (AF_INET, &adv_router, buf, sizeof (buf));
      zlog_err ("SPF: Can't find neighbor %s in %s, "
                "unable to find his linklocal address",
                buf, o6i->interface->name);
      return (struct in6_addr *) NULL;
    }

  zlog_warn ("SPF: use packet's source address for %s's nexthop: %s",
             inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)),
             inet_ntop (AF_INET6, &o6n->hisaddr, nhbuf, sizeof (nhbuf)));

  return &o6n->hisaddr;
}

static int
ospf6_spf_nexthop_calculation (struct ospf6_vertex *W,
                               u_int32_t ifindex,
                               struct ospf6_vertex *V,
                               struct ospf6_spftree *spf_tree)
{
  struct ospf6_nexthop *nexthop, *n;
  u_int32_t adv_router, id;
  struct in6_addr nexthop_ipaddr, *ipaddr;
  unsigned int nexthop_ifindex;
  struct linklist_node node;

  /* until this, nexthop_list should be untouched */
  assert (list_isempty (W->nexthop_list));

  /* If ther is at least one intervening router from root to W */
  if (ospf6_spf_is_router_to_root (W, spf_tree))
    {
      /* Create no new nexthop, Inherit from the intervening router */
      for (linklist_head (V->nexthop_list, &node); ! linklist_end (&node);
           linklist_next (&node))
        linklist_add (node.data, W->nexthop_list);
      return 0;
    }

  /* Create new nexthop */

  adv_router = W->vertex_id.adv_router.s_addr;
  id = W->vertex_id.id.s_addr;

  nexthop_ifindex = 0;
  memset (&nexthop_ipaddr, 0, sizeof (struct in6_addr));
  if (spf_tree->root && V == spf_tree->root)
    {
      nexthop_ifindex = ifindex;
      if (! id) /* xxx, if V is router */
        {
          ipaddr = ospf6_spf_get_ipaddr (id, adv_router, ifindex);
          if (! ipaddr)
            {
              /* xxx, should trigger error and quit SPF calculation... */
              memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr));
              return -1;
            }
          else
            memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr));
        }
    }
  else
    {
      /* V is broadcast network, W is router */
      assert (V->vertex_id.id.s_addr != 0);
      assert (W->vertex_id.id.s_addr == 0);
 
      linklist_head (V->nexthop_list, &node);
      n = (struct ospf6_nexthop *) node.data;
      nexthop_ifindex = n->ifindex;
      ipaddr = ospf6_spf_get_ipaddr (id, adv_router, n->ifindex);
      if (! ipaddr)
        {
          /* xxx, should trigger error and quit SPF calculation... */
          memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr));
          return -1;
        }
      else
        memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr));
    }

  nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop));
  nexthop->ifindex = nexthop_ifindex;
  memcpy (&nexthop->address, &nexthop_ipaddr, sizeof (nexthop->address));

  linklist_add (nexthop, W->nexthop_list);

  /* to hold malloced memory */
  linklist_add (nexthop, nexthop_list);

  return 0;
}

static struct ospf6_vertex *
ospf6_spf_vertex_create (int index, struct ospf6_vertex *V,
                         struct ospf6_area *o6a)
{
  struct ospf6_lsa *lsa;
  struct ospf6_router_lsa *router_lsa;
  struct ospf6_router_lsd *router_lsd;
  struct ospf6_network_lsa *network_lsa;
  struct ospf6_network_lsd *network_lsd;
  u_int32_t id, adv_router;
  u_int16_t type;
  void *lsd;
  struct ospf6_vertex *W;
  u_int16_t distance;
  u_int32_t ifindex;
  int backreference, lsdnum, i;
  char buf_router[16], buf_id[16];

  type = id = adv_router = 0;

  /* Get Linkstate description */
  lsd = ospf6_lsa_lsd_get (index, (struct ospf6_lsa_header *) V->lsa->header);
  if (! lsd)
    {
      zlog_err ("SPF: Can't find %dth Link description from %s",
                index, V->lsa->str);
      return (struct ospf6_vertex *) NULL;
    }

  /* Check Link state description */
  distance = 0;
  ifindex = 0;
  if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER))
    {
      router_lsd = lsd;
      if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_POINTTOPOINT)
        {
          type = htons (OSPF6_LSA_TYPE_ROUTER);
          id = htonl (0);
        }
      else if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_TRANSIT_NETWORK)
        {
          type = htons (OSPF6_LSA_TYPE_NETWORK);
          id = router_lsd->neighbor_interface_id;
        }
      adv_router = router_lsd->neighbor_router_id;
      distance = ntohs (router_lsd->metric);
      ifindex = ntohl (router_lsd->interface_id);
    }
  else if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_NETWORK))
    {
      network_lsd = lsd;
      type = htons (OSPF6_LSA_TYPE_ROUTER);
      id = htonl (0);
      adv_router = network_lsd->adv_router;
    }

  /* Avoid creating candidate of myself */
  if (adv_router == o6a->ospf6->router_id &&
      type == htons (OSPF6_LSA_TYPE_ROUTER))
    {
      return (struct ospf6_vertex *) NULL;
    }

  /* Find Associated LSA for W */
  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);

  if (! lsa)
    {
      inet_ntop (AF_INET, &adv_router, buf_router, sizeof (buf_router));
      inet_ntop (AF_INET, &id, buf_id, sizeof (buf_id));

      if (IS_OSPF6_DUMP_SPF)