ospf_lsa.c

router source code for the ospdf.

/*
 * OSPF Link State Advertisement
 * Copyright (C) 1999, 2000 Toshiaki Takada
 *
 * 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 "linklist.h"
#include "prefix.h"
#include "if.h"
#include "table.h"
#include "memory.h"
#include "stream.h"
#include "log.h"
#include "thread.h"
#include "hash.h"
#include "sockunion.h"		/* for inet_aton() */

#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
#include "ospfd/ospf_ism.h"
#include "ospfd/ospf_asbr.h"
#include "ospfd/ospf_lsa.h"
#include "ospfd/ospf_lsdb.h"
#include "ospfd/ospf_neighbor.h"
#include "ospfd/ospf_nsm.h"
#include "ospfd/ospf_flood.h"
#include "ospfd/ospf_packet.h"
#include "ospfd/ospf_spf.h"
#include "ospfd/ospf_dump.h"
#include "ospfd/ospf_route.h"
#include "ospfd/ospf_ase.h"
#include "ospfd/ospf_zebra.h"


u_int32_t
get_metric (u_char *metric)
{
  u_int32_t m;
  m = metric[0];
  m = (m << 8) + metric[1];
  m = (m << 8) + metric[2];
  return m;
}


struct timeval
tv_adjust (struct timeval a)
{
  while (a.tv_usec >= 1000000)
    {
      a.tv_usec -= 1000000;
      a.tv_sec++;
    }

  while (a.tv_usec < 0)
    {
      a.tv_usec += 1000000;
      a.tv_sec--;
    }

  return a;
}

int
tv_ceil (struct timeval a)
{
  a = tv_adjust (a);

  return (a.tv_usec ? a.tv_sec + 1 : a.tv_sec);
}

int
tv_floor (struct timeval a)
{
  a = tv_adjust (a);

  return a.tv_sec;
}

struct timeval
int2tv (int a)
{
  struct timeval ret;

  ret.tv_sec = a;
  ret.tv_usec = 0;

  return ret;
}

struct timeval
tv_add (struct timeval a, struct timeval b)
{
  struct timeval ret;

  ret.tv_sec = a.tv_sec + b.tv_sec;
  ret.tv_usec = a.tv_usec + b.tv_usec;

  return tv_adjust (ret);
}

struct timeval
tv_sub (struct timeval a, struct timeval b)
{
  struct timeval ret;

  ret.tv_sec = a.tv_sec - b.tv_sec;
  ret.tv_usec = a.tv_usec - b.tv_usec;

  return tv_adjust (ret);
}

int
tv_cmp (struct timeval a, struct timeval b)
{
  return (a.tv_sec == b.tv_sec ?
	  a.tv_usec - b.tv_usec : a.tv_sec - b.tv_sec);
}

int
ospf_lsa_refresh_delay (struct ospf_lsa *lsa)
{
  struct timeval delta, now;
  int delay = 0;

  gettimeofday (&now, NULL);
  delta = tv_sub (now, lsa->tv_orig);

  if (tv_cmp (delta, int2tv (OSPF_MIN_LS_INTERVAL)) < 0)
    {
      delay = tv_ceil (tv_sub (int2tv (OSPF_MIN_LS_INTERVAL), delta));

      if (IS_DEBUG_OSPF (lsa, LSA_GENERATE))
        zlog_info ("LSA[Type%d:%s]: Refresh timer delay %d seconds",
	           lsa->data->type, inet_ntoa (lsa->data->id), delay);

      assert (delay > 0);
    }

  return delay;
}


int
get_age (struct ospf_lsa *lsa)
{
  int age;
  struct timeval now;

  gettimeofday (&now, NULL);
  age = ntohs (lsa->data->ls_age) + tv_floor (tv_sub (now, lsa->tv_recv));

  return age;
}


/* Fletcher Checksum -- Refer to RFC1008. */
#define MODX                 4102
#define LSA_CHECKSUM_OFFSET    15

u_int16_t
ospf_lsa_checksum (struct lsa_header *lsa)
{
  u_char *sp, *ep, *p, *q;
  int c0 = 0, c1 = 0;
  int x, y;
  u_int16_t length;

  lsa->checksum = 0;
  length = ntohs (lsa->length) - 2;
  sp = (char *) &lsa->options;

  for (ep = sp + length; sp < ep; sp = q)
    {
      q = sp + MODX;
      if (q > ep)
        q = ep;
      for (p = sp; p < q; p++)
        {
          c0 += *p;
          c1 += c0;
        }
      c0 %= 255;
      c1 %= 255;
    }

  x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255;
  if (x <= 0)
    x += 255;
  y = 510 - c0 - x;
  if (y > 255)
    y -= 255;

  /* take care endian issue. */
  lsa->checksum = htons ((x << 8) + y);

  return (lsa->checksum);
}



/* Create OSPF LSA. */
struct ospf_lsa *
ospf_lsa_new ()
{
  struct ospf_lsa *new;

  new = XCALLOC (MTYPE_OSPF_LSA, sizeof (struct ospf_lsa));
  memset (new, 0, sizeof (struct ospf_lsa));

  new->flags = 0;
  new->lock = 1;
  new->retransmit_counter = 0;
  gettimeofday (&new->tv_recv, NULL);
  new->tv_orig = new->tv_recv;
  new->refresh_list = -1;
  
  return new;
}

/* Duplicate OSPF LSA. */
struct ospf_lsa *
ospf_lsa_dup (struct ospf_lsa *lsa)
{
  struct ospf_lsa *new;

  if (lsa == NULL)
    return NULL;

  new = XCALLOC (MTYPE_OSPF_LSA, sizeof (struct ospf_lsa));

  memcpy (new, lsa, sizeof (struct ospf_lsa));
  UNSET_FLAG (new->flags, OSPF_LSA_DISCARD);
  new->lock = 1;
  new->retransmit_counter = 0;
  new->data = ospf_lsa_data_dup (lsa->data);

  /* kevinm: Clear the refresh_list, otherwise there are going
     to be problems when we try to remove the LSA from the
     queue (which it's not a member of.)
     XXX: Should we add the LSA to the refresh_list queue? */
  new->refresh_list = -1;

  if (IS_DEBUG_OSPF (lsa, LSA))
    zlog_info ("LSA: duplicated %p (new: %p)", lsa, new);

  return new;
}

/* Free OSPF LSA. */
void
ospf_lsa_free (struct ospf_lsa *lsa)
{
  assert (lsa->lock == 0);
  
  if (IS_DEBUG_OSPF (lsa, LSA))
    zlog_info ("LSA: freed %p", lsa);

  /* Delete LSA data. */
  if (lsa->data != NULL)
    ospf_lsa_data_free (lsa->data);

  assert (lsa->refresh_list < 0);

  memset (lsa, 0, sizeof (struct ospf_lsa)); 
  XFREE (MTYPE_OSPF_LSA, lsa);
}

/* Lock LSA. */
struct ospf_lsa *
ospf_lsa_lock (struct ospf_lsa *lsa)
{
  lsa->lock++;
  return lsa;
}

/* Unlock LSA. */
void
ospf_lsa_unlock (struct ospf_lsa *lsa)
{
  /* This is sanity check. */
  if (!lsa)
    return;
  
  lsa->lock--;

  assert (lsa->lock >= 0);

  if (lsa->lock == 0)
    {
      assert (CHECK_FLAG (lsa->flags, OSPF_LSA_DISCARD));
      ospf_lsa_free (lsa);
    }
}

/* Check discard flag. */
void
ospf_lsa_discard (struct ospf_lsa *lsa)
{
  if (!CHECK_FLAG (lsa->flags, OSPF_LSA_DISCARD))
    {
      SET_FLAG (lsa->flags, OSPF_LSA_DISCARD);
      ospf_lsa_unlock (lsa);
    }
}

/* Create LSA data. */
struct lsa_header *
ospf_lsa_data_new (size_t size)
{
  struct lsa_header *new;

  new = (struct lsa_header *) XMALLOC (MTYPE_OSPF_LSA_DATA, size);
  memset (new, 0, size);

  return new;
}

/* Duplicate LSA data. */
struct lsa_header *
ospf_lsa_data_dup (struct lsa_header *lsah)
{
  struct lsa_header *new;

  new = ospf_lsa_data_new (ntohs (lsah->length));
  memcpy (new, lsah, ntohs (lsah->length));

  return new;
}

/* Free LSA data. */
void
ospf_lsa_data_free (struct lsa_header *lsah)
{
  if (IS_DEBUG_OSPF (lsa, LSA))
    zlog_info ("LSA[Type%d:%s]: data freed %p",
	       lsah->type, inet_ntoa (lsah->id), lsah);

  XFREE (MTYPE_OSPF_LSA_DATA, lsah);
}


/* LSA general functions. */

const char *
dump_lsa_key (struct ospf_lsa *lsa)
{
  static char buf[] = {
    "Type255,id(255.255.255.255),ar(255.255.255.255)",
  };
  struct lsa_header *lsah;

  if (lsa != NULL && (lsah = lsa->data) != NULL)
    {
      char id[INET_ADDRSTRLEN], ar[INET_ADDRSTRLEN];
      strcpy (id, inet_ntoa (lsah->id));
      strcpy (ar, inet_ntoa (lsah->adv_router));

      sprintf (buf, "Type%d,id(%s),ar(%s)", lsah->type, id, ar);
    }
  else
    strcpy (buf, "NULL");

  return buf;
}

u_int32_t
lsa_seqnum_increment (struct ospf_lsa *lsa)
{
  u_int32_t seqnum;

  seqnum = ntohl (lsa->data->ls_seqnum) + 1;

  return htonl (seqnum);
}

void
lsa_header_set (struct stream *s, u_char options,
		u_char type, struct in_addr id, struct in_addr router_id)
{
  struct lsa_header *lsah;

  lsah = (struct lsa_header *) STREAM_DATA (s);

  lsah->ls_age = htons (0);
  lsah->options = options;
  lsah->type = type;
  lsah->id = id;
  lsah->adv_router = router_id;
  lsah->ls_seqnum = htonl (OSPF_INITIAL_SEQUENCE_NUMBER);

  ospf_output_forward (s, OSPF_LSA_HEADER_SIZE);
}


/* router-LSA related functions. */
/* Get router-LSA flags. */
u_char
router_lsa_flags (struct ospf_area *area)
{
  u_char flags;

  flags = area->ospf->flags;

  /* Set virtual link flag. */
  if (ospf_full_virtual_nbrs (area))
    SET_FLAG (flags, ROUTER_LSA_VIRTUAL);
  else
    /* Just sanity check */
    UNSET_FLAG (flags, ROUTER_LSA_VIRTUAL);

  /* Set Shortcut ABR behabiour flag. */
  UNSET_FLAG (flags, ROUTER_LSA_SHORTCUT);
  if (area->ospf->abr_type == OSPF_ABR_SHORTCUT)
    if (!OSPF_IS_AREA_BACKBONE (area))
      if ((area->shortcut_configured == OSPF_SHORTCUT_DEFAULT &&
	   area->ospf->backbone == NULL) ||
	  area->shortcut_configured == OSPF_SHORTCUT_ENABLE)
	SET_FLAG (flags, ROUTER_LSA_SHORTCUT);

  /* ASBR can't exit in stub area. */
  if (area->external_routing == OSPF_AREA_STUB)
    UNSET_FLAG (flags, OSPF_FLAG_ASBR);

  return flags;
}

/* Lookup neighbor other than myself.
   And check neighbor count,
   Point-to-Point link must have only 1 neighbor. */
struct ospf_neighbor *
ospf_nbr_lookup_ptop (struct ospf_interface *oi)
{
  struct ospf_neighbor *nbr = NULL;
  struct route_node *rn;

  /* Search neighbor, there must be one of two nbrs. */
  for (rn = route_top (oi->nbrs); rn; rn = route_next (rn))
    if ((nbr = rn->info))
      if (!IPV4_ADDR_SAME (&nbr->router_id, &oi->ospf->router_id))
	if (nbr->state == NSM_Full)
	  {
	    route_unlock_node (rn);
	    break;
	  }

  /* PtoP link must have only 1 neighbor. */
  if (ospf_nbr_count (oi, 0) > 1)
    zlog_warn ("Point-to-Point link has more than 1 neighobrs.");

  return nbr;
}

/* Set a link information. */
void
link_info_set (struct stream *s, struct in_addr id,
	       struct in_addr data, u_char type, u_char tos, u_int16_t cost)
{
  /* TOS based routing is not supported. */
  stream_put_ipv4 (s, id.s_addr);		/* Link ID. */
  stream_put_ipv4 (s, data.s_addr);		/* Link Data. */
  stream_putc (s, type);			/* Link Type. */
  stream_putc (s, tos);				/* TOS = 0. */
  stream_putw (s, cost);			/* Link Cost. */
}

/* Describe Point-to-Point link. */
int
lsa_link_ptop_set (struct stream *s, struct ospf_interface *oi)
{
  int links = 0;
  struct ospf_neighbor *nbr;
  struct in_addr id, mask;

  if (IS_DEBUG_OSPF (lsa, LSA_GENERATE))
    zlog_info ("LSA[Type1]: Set link Point-to-Point");

  if ((nbr = ospf_nbr_lookup_ptop (oi)))
    if (nbr->state == NSM_Full)
      {
	/* For unnumbered point-to-point networks, the Link Data field
	   should specify the interface's MIB-II ifIndex value. */
	link_info_set (s, nbr->router_id, oi->address->u.prefix4,
		       LSA_LINK_TYPE_POINTOPOINT, 0, oi->output_cost);
	links++;
      }

  if (oi->connected->destination != NULL)
    {
      /* Option 1:
	 link_type = LSA_LINK_TYPE_STUB;
	 link_id = nbr->address.u.prefix4;
	 link_data.s_addr = 0xffffffff;
	 link_cost = o->output_cost; */
      
      id.s_addr = oi->connected->destination->u.prefix4.s_addr;
      mask.s_addr = 0xffffffff;