ospf6_route.c

linux 路由软件 可支持RIP OSPF BGP等

/*
 * Copyright (C) 2003 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 <zebra.h>

#include "log.h"
#include "memory.h"
#include "prefix.h"
#include "table.h"
#include "vty.h"
#include "command.h"

#include "ospf6_proto.h"
#include "ospf6_lsa.h"
#include "ospf6_lsdb.h"
#include "ospf6_route.h"
#include "ospf6d.h"

unsigned char conf_debug_ospf6_route = 0;

void
ospf6_linkstate_prefix (u_int32_t adv_router, u_int32_t id,
                        struct prefix *prefix)
{
  memset (prefix, 0, sizeof (struct prefix));
  prefix->family = AF_INET6;
  prefix->prefixlen = 64;
  memcpy (&prefix->u.prefix6.s6_addr[0], &adv_router, 4);
  memcpy (&prefix->u.prefix6.s6_addr[4], &id, 4);
}

void
ospf6_linkstate_prefix2str (struct prefix *prefix, char *buf, int size)
{
  u_int32_t adv_router, id;
  char adv_router_str[16], id_str[16];
  memcpy (&adv_router, &prefix->u.prefix6.s6_addr[0], 4);
  memcpy (&id, &prefix->u.prefix6.s6_addr[4], 4);
  inet_ntop (AF_INET, &adv_router, adv_router_str, sizeof (adv_router_str));
  inet_ntop (AF_INET, &id, id_str, sizeof (id_str));
  if (ntohl (id))
    snprintf (buf, size, "%s Net-ID: %s", adv_router_str, id_str);
  else
    snprintf (buf, size, "%s", adv_router_str);
}

/* Global strings for logging */
char *ospf6_dest_type_str[OSPF6_DEST_TYPE_MAX] =
{ "Unknown", "Router", "Network", "Discard", "Linkstate", "AddressRange", };

char *ospf6_dest_type_substr[OSPF6_DEST_TYPE_MAX] =
{ "?", "R", "N", "D", "L", "A", };

char *ospf6_path_type_str[OSPF6_PATH_TYPE_MAX] =
{ "Unknown", "Intra-Area", "Inter-Area", "External-1", "External-2", };

char *ospf6_path_type_substr[OSPF6_PATH_TYPE_MAX] =
{ "??", "IA", "IE", "E1", "E2", };


struct ospf6_route *
ospf6_route_create ()
{
  struct ospf6_route *route;
  route = XCALLOC (MTYPE_OSPF6_ROUTE, sizeof (struct ospf6_route));
  return route;
}

void
ospf6_route_delete (struct ospf6_route *route)
{
  XFREE (MTYPE_OSPF6_ROUTE, route);
}

struct ospf6_route *
ospf6_route_copy (struct ospf6_route *route)
{
  struct ospf6_route *new;

  new = ospf6_route_create ();
  memcpy (new, route, sizeof (struct ospf6_route));
  new->rnode = NULL;
  new->prev = NULL;
  new->next = NULL;
  new->lock = 0;
  return new;
}

void
ospf6_route_lock (struct ospf6_route *route)
{
  route->lock++;
}

void
ospf6_route_unlock (struct ospf6_route *route)
{
  assert (route->lock > 0);
  route->lock--;
  if (route->lock == 0)
    ospf6_route_delete (route);
}

/* Route compare function. If ra is more preferred, it returns
   less than 0. If rb is more preferred returns greater than 0.
   Otherwise (neither one is preferred), returns 0 */
static int
ospf6_route_cmp (struct ospf6_route *ra, struct ospf6_route *rb)
{
  assert (ospf6_route_is_same (ra, rb));
  assert (OSPF6_PATH_TYPE_NONE < ra->path.type &&
          ra->path.type < OSPF6_PATH_TYPE_MAX);
  assert (OSPF6_PATH_TYPE_NONE < rb->path.type &&
          rb->path.type < OSPF6_PATH_TYPE_MAX);

  if (ra->type != rb->type)
    return (ra->type - rb->type);

  if (ra->path.area_id != rb->path.area_id)
    return (ntohl (ra->path.area_id) - ntohl (rb->path.area_id));

  if (ra->path.type != rb->path.type)
    return (ra->path.type - rb->path.type);

  if (ra->path.type == OSPF6_PATH_TYPE_EXTERNAL2)
    {
      if (ra->path.cost_e2 != rb->path.cost_e2)
        return (ra->path.cost_e2 - rb->path.cost_e2);
    }
  else
    {
      if (ra->path.cost != rb->path.cost)
        return (ra->path.cost - rb->path.cost);
    }

  return 0;
}

struct ospf6_route *
ospf6_route_lookup (struct prefix *prefix,
                    struct ospf6_route_table *table)
{
  struct route_node *node;
  struct ospf6_route *route;

  node = route_node_lookup (table->table, prefix);
  if (node == NULL)
    return NULL;

  route = (struct ospf6_route *) node->info;
  return route;
}

struct ospf6_route *
ospf6_route_lookup_identical (struct ospf6_route *route,
                              struct ospf6_route_table *table)
{
  struct ospf6_route *target;

  for (target = ospf6_route_lookup (&route->prefix, table);
       target; target = target->next)
    {
      if (ospf6_route_is_identical (target, route))
        return target;
    }
  return NULL;
}

struct ospf6_route *
ospf6_route_lookup_bestmatch (struct prefix *prefix,
                              struct ospf6_route_table *table)
{
  struct route_node *node;
  struct ospf6_route *route;

  node = route_node_match (table->table, prefix);
  if (node == NULL)
    return NULL;
  route_unlock_node (node);

  route = (struct ospf6_route *) node->info;
  return route;
}

#ifndef NDEBUG
static void
_route_count_assert (struct ospf6_route_table *table)
{
  struct ospf6_route *debug;
  char buf[64];
  int num = 0;
  for (debug = ospf6_route_head (table); debug;
       debug = ospf6_route_next (debug))
    num++;

  if (num == table->count)
    return;

  zlog_info ("PANIC !! table[%p]->count = %d, real = %d",
             table, table->count, num);
  for (debug = ospf6_route_head (table); debug;
       debug = ospf6_route_next (debug))
    {
      prefix2str (&debug->prefix, buf, sizeof (buf));
      zlog_info ("%p %p %s", debug->prev, debug->next, buf);
    }
  zlog_info ("DUMP END");

  assert (num == table->count);
}
#define ospf6_route_count_assert(t) (_route_count_assert (t))
#else
#define ospf6_route_count_assert(t) ((void) 0)
#endif /*NDEBUG*/

struct ospf6_route *
ospf6_route_add (struct ospf6_route *route,
                 struct ospf6_route_table *table)
{
  struct route_node *node, *nextnode, *prevnode;
  struct ospf6_route *current = NULL;
  struct ospf6_route *prev = NULL, *old = NULL, *next = NULL;
  char buf[64];
  struct timeval now;

  assert (route->rnode == NULL);
  assert (route->lock == 0);
  assert (route->next == NULL);
  assert (route->prev == NULL);

  if (route->type == OSPF6_DEST_TYPE_LINKSTATE)
    ospf6_linkstate_prefix2str (&route->prefix, buf, sizeof (buf));
  else
    prefix2str (&route->prefix, buf, sizeof (buf));

  if (IS_OSPF6_DEBUG_ROUTE (TABLE))
    zlog_info ("route add %s", buf);

  gettimeofday (&now, NULL);

  node = route_node_get (table->table, &route->prefix);
  route->rnode = node;

  /* find place to insert */
  for (current = node->info; current; current = current->next)
    {
      if (! ospf6_route_is_same (current, route))
        next = current;
      else if (current->type != route->type)
        prev = current;
      else if (ospf6_route_is_same_origin (current, route))
        old = current;
      else if (ospf6_route_cmp (current, route) > 0)
        next = current;
      else
        prev = current;

      if (old || next)
        break;
    }

  if (old)
    {
      /* if route does not actually change, return unchanged */
      if (ospf6_route_is_identical (old, route))
        {
          if (IS_OSPF6_DEBUG_ROUTE (TABLE))
            zlog_info ("  identical route found, ignore");

          ospf6_route_delete (route);
          SET_FLAG (old->flag, OSPF6_ROUTE_ADD);
          ospf6_route_count_assert (table);

          return old;
        }

      if (IS_OSPF6_DEBUG_ROUTE (TABLE))
        zlog_info ("  old route found, replace");

      /* replace old one if exists */
      if (node->info == old)
        {
          node->info = route;
          SET_FLAG (route->flag, OSPF6_ROUTE_BEST);
        }

      if (old->prev)
        old->prev->next = route;
      route->prev = old->prev;
      if (old->next)
        old->next->prev = route;
      route->next = old->next;

      route->installed = old->installed;
      route->changed = now;

      ospf6_route_unlock (old); /* will be deleted later */
      ospf6_route_lock (route);

      SET_FLAG (route->flag, OSPF6_ROUTE_CHANGE);
      ospf6_route_count_assert (table);

      if (table->hook_add)
        (*table->hook_add) (route);

      return route;
    }

  /* insert if previous or next node found */
  if (prev || next)
    {
      if (IS_OSPF6_DEBUG_ROUTE (TABLE))
        zlog_info ("  another path found, insert");

      if (prev == NULL)
        prev = next->prev;
      if (next == NULL)
        next = prev->next;

      if (prev)
        prev->next = route;
      route->prev = prev;
      if (next)
        next->prev = route;
      route->next = next;

      if (node->info == next)
        {
          assert (next->rnode == node);
          node->info = route;
          UNSET_FLAG (next->flag, OSPF6_ROUTE_BEST);
          SET_FLAG (route->flag, OSPF6_ROUTE_BEST);
        }

      route->installed = now;
      route->changed = now;

      ospf6_route_lock (route);
      table->count++;
      ospf6_route_count_assert (table);

      SET_FLAG (route->flag, OSPF6_ROUTE_ADD);
      if (table->hook_add)
        (*table->hook_add) (route);

      return route;
    }

  /* Else, this is the brand new route regarding to the prefix */
  if (IS_OSPF6_DEBUG_ROUTE (TABLE))
    zlog_info ("  brand new route, add");

  assert (node->info == NULL);
  node->info = route;
  SET_FLAG (route->flag, OSPF6_ROUTE_BEST);
  ospf6_route_lock (route);
  route->installed = now;
  route->changed = now;

  /* lookup real existing next route */
  nextnode = node;
  route_lock_node (nextnode);
  do {
    nextnode = route_next (nextnode);
  } while (nextnode && nextnode->info == NULL);

  /* set next link */
  if (nextnode == NULL)
    route->next = NULL;
  else
    {
      route_unlock_node (nextnode);

      next = nextnode->info;
      route->next = next;
      next->prev = route;
    }

  /* lookup real existing prev route */
  prevnode = node;
  route_lock_node (prevnode);
  do {
    prevnode = route_prev (prevnode);
  } while (prevnode && prevnode->info == NULL);

  /* set prev link */
  if (prevnode == NULL)
    route->prev = NULL;
  else
    {
      route_unlock_node (prevnode);

      prev = prevnode->info;
      while (prev->next && ospf6_route_is_same (prev, prev->next))
        prev = prev->next;
      route->prev = prev;