ospf_route.c

router source code for the ospdf.

/*
 * OSPF routing table.
 * 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 "prefix.h"
#include "table.h"
#include "memory.h"
#include "linklist.h"
#include "log.h"
#include "if.h"
#include "command.h"
#include "sockunion.h"

#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
#include "ospfd/ospf_asbr.h"
#include "ospfd/ospf_lsa.h"
#include "ospfd/ospf_route.h"
#include "ospfd/ospf_spf.h"
#include "ospfd/ospf_zebra.h"
#include "ospfd/ospf_dump.h"

struct ospf_route *
ospf_route_new ()
{
  struct ospf_route *new;

  new = XCALLOC (MTYPE_OSPF_ROUTE, sizeof (struct ospf_route));

  new->ctime = time (NULL);
  new->mtime = new->ctime;

  return new;
}

void
ospf_route_free (struct ospf_route *or)
{
  listnode node;

  if (or->path)
    {
      for (node = listhead (or->path); node; nextnode (node))
	ospf_path_free (node->data);

      list_delete (or->path);
    }

  XFREE (MTYPE_OSPF_ROUTE, or);
}

struct ospf_path *
ospf_path_new ()
{
  struct ospf_path *new;

  new = XCALLOC (MTYPE_OSPF_PATH, sizeof (struct ospf_path));

  return new;
}

struct ospf_path *
ospf_path_dup (struct ospf_path *path)
{
  struct ospf_path *new;

  new = ospf_path_new ();
  memcpy (new, path, sizeof (struct ospf_path));

  return new;
}

void
ospf_path_free (struct ospf_path *op)
{
  XFREE (MTYPE_OSPF_PATH, op);
}

void
ospf_route_delete (struct route_table *rt)
{
  struct route_node *rn;
  struct ospf_route *or;

  for (rn = route_top (rt); rn; rn = route_next (rn))
    if ((or = rn->info) != NULL)
      {
	if (or->type == OSPF_DESTINATION_NETWORK)
	  ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p,
				       or);
	else if (or->type == OSPF_DESTINATION_DISCARD)
	  ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
      }
}

void
ospf_route_table_free (struct route_table *rt)
{
  struct route_node *rn;
  struct ospf_route *or;

  for (rn = route_top (rt); rn; rn = route_next (rn))
    if ((or = rn->info) != NULL)
      {
	ospf_route_free (or);

	rn->info = NULL;
	route_unlock_node (rn);
      }

   route_table_finish (rt);
}

/* If a prefix and a nexthop match any route in the routing table,
   then return 1, otherwise return 0. */
int
ospf_route_match_same (struct route_table *rt, struct prefix_ipv4 *prefix,
		       struct ospf_route *newor)
{
  struct route_node *rn;
  struct ospf_route *or;
  struct ospf_path *op;
  struct ospf_path *newop;
  listnode n1;
  listnode n2;

  if (! rt || ! prefix)
    return 0;

   rn = route_node_lookup (rt, (struct prefix *) prefix);
   if (! rn || ! rn->info)
     return 0;
 
   route_unlock_node (rn);

   or = rn->info;
   if (or->type == newor->type && or->cost == newor->cost)
     {
       if (or->type == OSPF_DESTINATION_NETWORK)
	 {
	   if (or->path->count != newor->path->count)
	     return 0;

	   /* Check each path. */
	   for (n1 = listhead (or->path), n2 = listhead (newor->path);
		n1 && n2; nextnode (n1), nextnode (n2))
	     { 
	       op = getdata (n1);
	       newop = getdata (n2);

	       if (! IPV4_ADDR_SAME (&op->nexthop, &newop->nexthop))
		 return 0;
	     }
	   return 1;
	 }
       else if (prefix_same (&rn->p, (struct prefix *) prefix))
	 return 1;
     }
  return 0;
}

/* rt: Old, cmprt: New */
void
ospf_route_delete_uniq (struct route_table *rt, struct route_table *cmprt)
{
  struct route_node *rn;
  struct ospf_route *or;

  for (rn = route_top (rt); rn; rn = route_next (rn))
    if ((or = rn->info) != NULL) 
      if (or->path_type == OSPF_PATH_INTRA_AREA ||
	  or->path_type == OSPF_PATH_INTER_AREA)
	{
	  if (or->type == OSPF_DESTINATION_NETWORK)
	    {
	      if (! ospf_route_match_same (cmprt, 
					   (struct prefix_ipv4 *) &rn->p, or))
		ospf_zebra_delete ((struct prefix_ipv4 *) &rn->p, or);
	    }
	  else if (or->type == OSPF_DESTINATION_DISCARD)
	    if (! ospf_route_match_same (cmprt,
					 (struct prefix_ipv4 *) &rn->p, or))
	      ospf_zebra_delete_discard ((struct prefix_ipv4 *) &rn->p);
	}
}

/* Install routes to table. */
void
ospf_route_install (struct ospf *ospf, struct route_table *rt)
{
  struct route_node *rn;
  struct ospf_route *or;

  /* rt contains new routing table, new_table contains an old one.
     updating pointers */
  if (ospf->old_table)
    ospf_route_table_free (ospf->old_table);

  ospf->old_table = ospf->new_table;
  ospf->new_table = rt;

  /* Delete old routes. */
  if (ospf->old_table)
    ospf_route_delete_uniq (ospf->old_table, rt);

  /* Install new routes. */
  for (rn = route_top (rt); rn; rn = route_next (rn))
    if ((or = rn->info) != NULL)
      {
	if (or->type == OSPF_DESTINATION_NETWORK)
	  {
	    if (! ospf_route_match_same (ospf->old_table,
					 (struct prefix_ipv4 *)&rn->p, or))
	      ospf_zebra_add ((struct prefix_ipv4 *) &rn->p, or);
	  }
	else if (or->type == OSPF_DESTINATION_DISCARD)
	  if (! ospf_route_match_same (ospf->old_table,
				       (struct prefix_ipv4 *) &rn->p, or))
	    ospf_zebra_add_discard ((struct prefix_ipv4 *) &rn->p);
      }
}

void
ospf_intra_route_add (struct route_table *rt, struct vertex *v,
		      struct ospf_area *area)
{
  struct route_node *rn;
  struct ospf_route *or;
  struct prefix_ipv4 p;
  struct ospf_path *path;
  struct vertex_nexthop *nexthop;
  listnode nnode;

  p.family = AF_INET;
  p.prefix = v->id;
  if (v->type == OSPF_VERTEX_ROUTER)
    p.prefixlen = IPV4_MAX_BITLEN;
  else
    {
      struct network_lsa *lsa = (struct network_lsa *) v->lsa;
      p.prefixlen = ip_masklen (lsa->mask);
    }
  apply_mask_ipv4 (&p);

  rn = route_node_get (rt, (struct prefix *) &p);
  if (rn->info)
    {
      zlog_warn ("Same routing information exists for %s", inet_ntoa (v->id));
      route_unlock_node (rn);
      return;
    }

  or = ospf_route_new ();

  if (v->type == OSPF_VERTEX_NETWORK)
    {
      or->type = OSPF_DESTINATION_NETWORK;
      or->path = list_new ();

      for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
	{
	  nexthop = getdata (nnode);
	  path = ospf_path_new ();
	  path->nexthop = nexthop->router;
	  listnode_add (or->path, path);
	}
    }
  else
    or->type = OSPF_DESTINATION_ROUTER;

  or->id = v->id;
  or->u.std.area_id = area->area_id;
#ifdef HAVE_NSSA
  or->u.std.external_routing= area->external_routing;
#endif /* HAVE_NSSA */
  or->path_type = OSPF_PATH_INTRA_AREA;
  or->cost = v->distance;

  rn->info = or;
}

/* RFC2328 16.1. (4). For "router". */
void
ospf_intra_add_router (struct route_table *rt, struct vertex *v,
		       struct ospf_area *area)
{
  struct route_node *rn;
  struct ospf_route *or;
  struct prefix_ipv4 p;
  struct router_lsa *lsa;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_router: Start");

  lsa = (struct router_lsa *) v->lsa;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_router: LS ID: %s",
	       inet_ntoa (lsa->header.id));

  ospf_vl_up_check (area, lsa->header.id, v);

  if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT))
    area->shortcut_capability = 0;

  /* If the newly added vertex is an area border router or AS boundary
     router, a routing table entry is added whose destination type is
     "router". */
  if (! IS_ROUTER_LSA_BORDER (lsa) && ! IS_ROUTER_LSA_EXTERNAL (lsa))
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_intra_add_router: "
		   "this router is neither ASBR nor ABR, skipping it");
      return;
    }

  /* Update ABR and ASBR count in this area. */
  if (IS_ROUTER_LSA_BORDER (lsa))
    area->abr_count++;
  if (IS_ROUTER_LSA_EXTERNAL (lsa))
    area->asbr_count++;

  /* The Options field found in the associated router-LSA is copied
     into the routing table entry's Optional capabilities field. Call
     the newly added vertex Router X. */
  or = ospf_route_new ();

  or->id = v->id;
  or->u.std.area_id = area->area_id;
#ifdef HAVE_NSSA
  or->u.std.external_routing = area->external_routing;
#endif /* HAVE_NSSA */
  or->path_type = OSPF_PATH_INTRA_AREA;
  or->cost = v->distance;
  or->type = OSPF_DESTINATION_ROUTER;
  or->u.std.origin = (struct lsa_header *) lsa;
  or->u.std.options = lsa->header.options;
  or->u.std.flags = lsa->flags;

  /* If Router X is the endpoint of one of the calculating router's
     virtual links, and the virtual link uses Area A as Transit area:
     the virtual link is declared up, the IP address of the virtual
     interface is set to the IP address of the outgoing interface
     calculated above for Router X, and the virtual neighbor's IP
     address is set to Router X's interface address (contained in
     Router X's router-LSA) that points back to the root of the
     shortest- path tree; equivalently, this is the interface that
     points back to Router X's parent vertex on the shortest-path tree
     (similar to the calculation in Section 16.1.1). */

  p.family = AF_INET;
  p.prefix = v->id;
  p.prefixlen = IPV4_MAX_BITLEN;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_router: talking about %s/%d",
	       inet_ntoa (p.prefix), p.prefixlen);

  rn = route_node_get (rt, (struct prefix *) &p);

  /* Note that we keep all routes to ABRs and ASBRs, not only the best */
  if (rn->info == NULL)
    rn->info = list_new ();
  else
    route_unlock_node (rn);

  ospf_route_copy_nexthops_from_vertex (or, v);

  listnode_add (rn->info, or);

  zlog_info ("ospf_intra_add_router: Start");
}

/* RFC2328 16.1. (4).  For transit network. */
void
ospf_intra_add_transit (struct route_table *rt, struct vertex *v,
			struct ospf_area *area)
{
  struct route_node *rn;
  struct ospf_route *or;
  struct prefix_ipv4 p;
  struct network_lsa *lsa;

  lsa = (struct network_lsa*) v->lsa;

  /* If the newly added vertex is a transit network, the routing table
     entry for the network is located.  The entry's Destination ID is
     the IP network number, which can be obtained by masking the
     Vertex ID (Link State ID) with its associated subnet mask (found
     in the body of the associated network-LSA). */
  p.family = AF_INET;
  p.prefix = v->id;
  p.prefixlen = ip_masklen (lsa->mask);
  apply_mask_ipv4 (&p);

  rn = route_node_get (rt, (struct prefix *) &p);

  /* If the routing table entry already exists (i.e., there is already
     an intra-area route to the destination installed in the routing
     table), multiple vertices have mapped to the same IP network.
     For example, this can occur when a new Designated Router is being
     established.  In this case, the current routing table entry
     should be overwritten if and only if the newly found path is just
     as short and the current routing table entry's Link State Origin
     has a smaller Link State ID than the newly added vertex' LSA. */
  if (rn->info)
    {
      struct ospf_route *cur_or;

      route_unlock_node (rn);
      cur_or = rn->info;

      if (v->distance > cur_or->cost ||
          IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) > 0)
	return;
      
      ospf_route_free (rn->info);
    }

  or = ospf_route_new ();

  or->id = v->id;
  or->u.std.area_id = area->area_id;
#ifdef HAVE_NSSA
  or->u.std.external_routing = area->external_routing;
#endif /* HAVE_NSSA */
  or->path_type = OSPF_PATH_INTRA_AREA;
  or->cost = v->distance;
  or->type = OSPF_DESTINATION_NETWORK;
  or->u.std.origin = (struct lsa_header *) lsa;

  ospf_route_copy_nexthops_from_vertex (or, v);
  
  rn->info = or;
}

/* RFC2328 16.1. second stage. */
void
ospf_intra_add_stub (struct route_table *rt, struct router_lsa_link *link,
		     struct vertex *v, struct ospf_area *area)
{
  u_int32_t cost;
  struct route_node *rn;
  struct ospf_route *or;
  struct prefix_ipv4 p;
  struct router_lsa *lsa;
  struct ospf_interface *oi;
  struct ospf_path *path;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_stub(): Start");

  lsa = (struct router_lsa *) v->lsa;

  p.family = AF_INET;
  p.prefix = link->link_id;
  p.prefixlen = ip_masklen (link->link_data);
  apply_mask_ipv4 (&p);

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_stub(): processing route to %s/%d",  
	       inet_ntoa (p.prefix), p.prefixlen);

  /* (1) Calculate the distance D of stub network from the root.  D is
     equal to the distance from the root to the router vertex
     (calculated in stage 1), plus the stub network link's advertised
     cost. */
  cost = v->distance + ntohs (link->m[0].metric);

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_stub(): calculated cost is %d + %d = %d", 
	       v->distance, ntohs(link->m[0].metric), cost);

  rn = route_node_get (rt, (struct prefix *) &p);

  /* Lookup current routing table. */
  if (rn->info)
    {
      struct ospf_route *cur_or;

      route_unlock_node (rn);

      cur_or = rn->info;

      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_intra_add_stub(): "
		   "another route to the same prefix found");

      /* Compare this distance to the current best cost to the stub
	 network.  This is done by looking up the stub network's
	 current routing table entry.  If the calculated distance D is
	 larger, go on to examine the next stub network link in the
	 LSA. */
      if (cost > cur_or->cost)
	{
	  if (IS_DEBUG_OSPF_EVENT)