ospf_spf.c

router source code for the ospdf.

/* OSPF SPF calculation.
   Copyright (C) 1999, 2000 Kunihiro Ishiguro, 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 "thread.h"
#include "memory.h"
#include "hash.h"
#include "linklist.h"
#include "prefix.h"
#include "if.h"
#include "table.h"
#include "log.h"
#include "sockunion.h"          /* for inet_ntop () */

#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_spf.h"
#include "ospfd/ospf_route.h"
#include "ospfd/ospf_ia.h"
#include "ospfd/ospf_ase.h"
#include "ospfd/ospf_abr.h"
#include "ospfd/ospf_dump.h"

#define DEBUG

struct vertex_nexthop *
vertex_nexthop_new (struct vertex *parent)
{
  struct vertex_nexthop *new;

  new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
  new->parent = parent;

  return new;
}

void
vertex_nexthop_free (struct vertex_nexthop *nh)
{
  XFREE (MTYPE_OSPF_NEXTHOP, nh);
}

struct vertex_nexthop *
vertex_nexthop_dup (struct vertex_nexthop *nh)
{
  struct vertex_nexthop *new;

  new = vertex_nexthop_new (nh->parent);

  new->oi = nh->oi;
  new->router = nh->router;

  return new;
}


struct vertex *
ospf_vertex_new (struct ospf_lsa *lsa)
{
  struct vertex *new;

  new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
  memset (new, 0, sizeof (struct vertex));

  new->flags = 0;
  new->type = lsa->data->type;
  new->id = lsa->data->id;
  new->lsa = lsa->data;
  new->distance = 0;
  new->child = list_new ();
  new->nexthop = list_new ();

  return new;
}

void
ospf_vertex_free (struct vertex *v)
{
  listnode node;

  list_delete (v->child);

  if (listcount (v->nexthop) > 0)
    for (node = listhead (v->nexthop); node; nextnode (node))
      vertex_nexthop_free (node->data);

  list_delete (v->nexthop);

  XFREE (MTYPE_OSPF_VERTEX, v);
}

void
ospf_vertex_add_parent (struct vertex *v)
{
  struct vertex_nexthop *nh;
  listnode node;

  for (node = listhead (v->nexthop); node; nextnode (node))
    {
      nh = (struct vertex_nexthop *) getdata (node);

      /* No need to add two links from the same parent. */
      if (listnode_lookup (nh->parent->child, v) == NULL)
	listnode_add (nh->parent->child, v);
    }
}

void
ospf_spf_init (struct ospf_area *area)
{
  struct vertex *v;

  /* Create root node. */
  v = ospf_vertex_new (area->router_lsa_self);

  area->spf = v;

  /* Reset ABR and ASBR router counts. */
  area->abr_count = 0;
  area->asbr_count = 0;
}

int
ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
                     struct lsa_header *lsa)
{
  struct prefix p;
  struct route_node *rn;

  p.family = AF_INET;
  p.prefixlen = IPV4_MAX_BITLEN;
  p.u.prefix4 = lsa->id;

  if (lsa->type == OSPF_ROUTER_LSA)
    rn = route_node_get (rv, &p);
  else
    rn = route_node_get (nv, &p);

  if (rn->info != NULL)
    {
      route_unlock_node (rn);
      return 1;
    }
  return 0;
}

listnode
ospf_vertex_lookup (list vlist, struct in_addr id, int type)
{
  listnode node;
  struct vertex *v;

  for (node = listhead (vlist); node; nextnode (node))
    {
      v = (struct vertex *) getdata (node);
      if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type)
        return node;
    }

  return NULL;
}

int
ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
{
  int i;
  int length;
  struct router_lsa *rl;
  struct network_lsa *nl;

  /* In case of W is Network LSA. */
  if (w->type == OSPF_NETWORK_LSA)
    {
      if (v->type == OSPF_NETWORK_LSA)
        return 0;

      nl = (struct network_lsa *) w;
      length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
      
      for (i = 0; i < length; i++)
        if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
          return 1;
      return 0;
    }

  /* In case of W is Router LSA. */
  if (w->type == OSPF_ROUTER_LSA)
    {
      rl = (struct router_lsa *) w;

      length = ntohs (w->length);

      for (i = 0;
	   i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
	   i++, length -= 12)
        {
          switch (rl->link[i].type)
            {
            case LSA_LINK_TYPE_POINTOPOINT:
            case LSA_LINK_TYPE_VIRTUALLINK:
              /* Router LSA ID. */
              if (v->type == OSPF_ROUTER_LSA &&
                  IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
                {
                  return 1;
                }
              break;
            case LSA_LINK_TYPE_TRANSIT:
              /* Network LSA ID. */
              if (v->type == OSPF_NETWORK_LSA &&
                  IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
                {
                  return 1;
		}
              break;
            case LSA_LINK_TYPE_STUB:
              /* Not take into count? */
              continue;
            default:
              break;
            }
        }
    }
  return 0;
}

/* Add the nexthop to the list, only if it is unique.
 * If it's not unique, free the nexthop entry.
 */
void
ospf_nexthop_add_unique (struct vertex_nexthop *new, list nexthop)
{
  struct vertex_nexthop *nh;
  listnode node;
  int match;

  match = 0;
  for (node = listhead (nexthop); node; nextnode (node))
    {
      nh = node->data;

      /* Compare the two entries. */
      /* XXX
       * Comparing the parent preserves the shortest path tree
       * structure even when the nexthops are identical.
       */
      if (nh->oi == new->oi &&
	  IPV4_ADDR_SAME (&nh->router, &new->router) &&
	  nh->parent == new->parent)
	{
	  match = 1;
	  break;
	}
    }

  if (!match)
    listnode_add (nexthop, new);
  else
    vertex_nexthop_free (new);
}

/* Merge entries in list b into list a. */
void
ospf_nexthop_merge (list a, list b)
{
  struct listnode *n;

  for (n = listhead (b); n; nextnode (n))
    {
      ospf_nexthop_add_unique (n->data, a);
    }
}

#define ROUTER_LSA_MIN_SIZE 12
#define ROUTER_LSA_TOS_SIZE 4

struct router_lsa_link *
ospf_get_next_link (struct vertex *v, struct vertex *w,
		    struct router_lsa_link *prev_link)
{
  u_char *p;
  u_char *lim;
  struct router_lsa_link *l;

  if (prev_link == NULL)
    p = ((u_char *) v->lsa) + 24;
  else
    {
      p = (u_char *)prev_link;
      p += (ROUTER_LSA_MIN_SIZE +
            (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
    }
  
  lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);

  while (p < lim)
    {
      l = (struct router_lsa_link *) p;

      p += (ROUTER_LSA_MIN_SIZE +
            (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));

      if (l->m[0].type == LSA_LINK_TYPE_STUB)
        continue;

      /* Defer NH calculation via VLs until summaries from
         transit areas area confidered             */

      if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
        continue; 

      if (IPV4_ADDR_SAME (&l->link_id, &w->id))
          return l;
    }

  return NULL;
}

/* Calculate nexthop from root to vertex W. */
void
ospf_nexthop_calculation (struct ospf_area *area,
                          struct vertex *v, struct vertex *w)
{
  listnode node;
  struct vertex_nexthop *nh, *x;
  struct ospf_interface *oi = NULL;
  struct router_lsa_link *l = NULL;
	  
    
  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_nexthop_calculation(): Start");

  /* W's parent is root. */
  if (v == area->spf)
    {
      if (w->type == OSPF_VERTEX_ROUTER)
	{
	  while ((l = ospf_get_next_link (v, w, l)))
	    {
	      struct router_lsa_link *l2 = NULL;
	      
	      if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
		{
		  /* Check for PtMP, signified by PtP link V->W
		     with link_data our PtMP interface. */
                  oi = ospf_if_is_configured (area->ospf, &l->link_data);
                  if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
		    {
		      struct prefix_ipv4 la;
		      la.prefixlen = oi->address->prefixlen;
		      
		      /* We link to them on PtMP interface
			 - find the interface on w */
		      while ((l2 = ospf_get_next_link (w, v, l2)))
			{
			  la.prefix = l2->link_data;
			  
			  if (prefix_cmp ((struct prefix *)&la,
					  oi->address) == 0)
			    /* link_data is on our PtMP network */
			    break;
			}
		    }
		  else
		    {                                
		      while ((l2 = ospf_get_next_link (w, v, l2)))
			{
			  oi = ospf_if_is_configured (area->ospf,
						      &(l2->link_data));
			  
			  if (oi == NULL)
			    continue;
			  
			  if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
					       &l->link_data))
			    continue;
			  
			  break;
			}
		    }
		  
		  if (oi && l2)
		    {
		      nh = vertex_nexthop_new (v);
		      nh->oi = oi;
		      nh->router = l2->link_data;
		      listnode_add (w->nexthop, nh);
		    }
		}
	    }
	}
      else
	{
	  while ((l = ospf_get_next_link (v, w, l)))
	    {
	      oi = ospf_if_is_configured (area->ospf, &(l->link_data));
	      if (oi)
		{
		  nh = vertex_nexthop_new (v);
		  nh->oi = oi;
		  nh->router.s_addr = 0;
		  listnode_add (w->nexthop, nh);
		}
	    }
	}
      return;
    }
  /* In case of W's parent is network connected to root. */
  else if (v->type == OSPF_VERTEX_NETWORK)
    {
      for (node = listhead (v->nexthop); node; nextnode (node))
        {
          x = (struct vertex_nexthop *) getdata (node);
          if (x->parent == area->spf)
            {
	      while ((l = ospf_get_next_link (w, v, l)))
		{
		  nh = vertex_nexthop_new (v);
		  nh->oi = x->oi;
		  nh->router = l->link_data;
		  listnode_add (w->nexthop, nh);
		}
	      return;
	    }
        }
    }

  /* Inherit V's nexthop. */
  for (node = listhead (v->nexthop); node; nextnode (node))
    {
      nh = vertex_nexthop_dup (node->data);
      nh->parent = v;
      ospf_nexthop_add_unique (nh, w->nexthop);
    }
}

void
ospf_install_candidate (list candidate, struct vertex *w)
{
  listnode node;
  struct vertex *cw;

  if (list_isempty (candidate))
    {
      listnode_add (candidate, w);
      return;
    }

  /* Install vertex with sorting by distance. */
  for (node = listhead (candidate); node; nextnode (node))
    {
      cw = (struct vertex *) getdata (node);
      if (cw->distance > w->distance)
        {
          list_add_node_prev (candidate, node, w);
          break;
        }
      else if (node->next == NULL)
        {
          list_add_node_next (candidate, node, w);
          break;
        }
    }
}

/* RFC2328 Section 16.1 (2). */
void
ospf_spf_next (struct vertex *v, struct ospf_area *area,
               list candidate, struct route_table *rv,
               struct route_table *nv)
{
  struct ospf_lsa *w_lsa = NULL;
  struct vertex *w, *cw;
  u_char *p;
  u_char *lim;
  struct router_lsa_link *l = NULL;
  struct in_addr *r;
  listnode node;
  int type = 0;

  /* If this is a router-LSA, and bit V of the router-LSA (see Section
     A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE.  */
  if (v->type == OSPF_VERTEX_ROUTER)
    {
      if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
        area->transit = OSPF_TRANSIT_TRUE;
    }

  p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
  lim =  ((u_char *) v->lsa) + ntohs (v->lsa->length);
    
  while (p < lim)
    {
      /* In case of V is Router-LSA. */
      if (v->lsa->type == OSPF_ROUTER_LSA)
        {
          l = (struct router_lsa_link *) p;

          p += (ROUTER_LSA_MIN_SIZE + 
                (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));

          /* (a) If this is a link to a stub network, examine the next
             link in V's LSA.  Links to stub networks will be
             considered in the second stage of the shortest path
             calculation. */
          if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
            continue;

          /* (b) Otherwise, W is a transit vertex (router or transit
             network).  Look up the vertex W's LSA (router-LSA or
             network-LSA) in Area A's link state database. */
          switch (type)
            {
            case LSA_LINK_TYPE_POINTOPOINT:
            case LSA_LINK_TYPE_VIRTUALLINK:
              if (type == LSA_LINK_TYPE_VIRTUALLINK)
		{
		  if (IS_DEBUG_OSPF_EVENT)
		    zlog_info ("looking up LSA through VL: %s",
			       inet_ntoa (l->link_id));
		}

              w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
                                       l->link_id);
              if (w_lsa)
		{
		  if (IS_DEBUG_OSPF_EVENT)
		  zlog_info("found the LSA");
		}
              break;
            case LSA_LINK_TYPE_TRANSIT:
		  if (IS_DEBUG_OSPF_EVENT)