ospf_route.c

router source code for the ospdf.

	    zlog_info ("ospf_intra_add_stub(): old route is better, exit");
	  return;
	}

      /* (2) If this step is reached, the stub network's routing table
	 entry must be updated.  Calculate the set of next hops that
	 would result from using the stub network link.  This
	 calculation is shown in Section 16.1.1; input to this
	 calculation is the destination (the stub network) and the
	 parent vertex (the router vertex). If the distance D is the
	 same as the current routing table cost, simply add this set
	 of next hops to the routing table entry's list of next hops.
	 In this case, the routing table already has a Link State
	 Origin.  If this Link State Origin is a router-LSA whose Link
	 State ID is smaller than V's Router ID, reset the Link State
	 Origin to V's router-LSA. */

      if (cost == cur_or->cost)
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_intra_add_stub(): routes are equal, merge");

	  ospf_route_copy_nexthops_from_vertex (cur_or, v);

	  if (IPV4_ADDR_CMP (&cur_or->u.std.origin->id, &lsa->header.id) < 0)
	    cur_or->u.std.origin = (struct lsa_header *) lsa;
	  return;
	}

      /* Otherwise D is smaller than the routing table cost.
	 Overwrite the current routing table entry by setting the
	 routing table entry's cost to D, and by setting the entry's
	 list of next hops to the newly calculated set.  Set the
	 routing table entry's Link State Origin to V's router-LSA.
	 Then go on to examine the next stub network link. */

      if (cost < cur_or->cost)
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_intra_add_stub(): new route is better, set it");

	  cur_or->cost = cost;

	  list_delete (cur_or->path);
	  cur_or->path = NULL;

	  ospf_route_copy_nexthops_from_vertex (cur_or, v);

	  cur_or->u.std.origin = (struct lsa_header *) lsa;
	  return;
	}
    }

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_intra_add_stub(): installing new route");

  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 = cost;
  or->type = OSPF_DESTINATION_NETWORK;
  or->u.std.origin = (struct lsa_header *) lsa;
  or->path = list_new ();

  /* Nexthop is depend on connection type. */
  if (v != area->spf)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_intra_add_stub(): this network is on remote router");
      ospf_route_copy_nexthops_from_vertex (or, v);
    }
  else
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_intra_add_stub(): this network is on this router");

      if ((oi = ospf_if_lookup_by_prefix (area->ospf, &p)))
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_intra_add_stub(): the interface is %s",
		       IF_NAME (oi));

	  path = ospf_path_new ();
	  path->nexthop.s_addr = 0;
	  path->oi = oi;
	  listnode_add (or->path, path);
	}
      else
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_intra_add_stub(): where's the interface ?");
	}
    }

  rn->info = or;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info("ospf_intra_add_stub(): Stop");
}

char *ospf_path_type_str[] =
{
  "unknown-type",
  "intra-area",
  "inter-area",
  "type1-external",
  "type2-external"
};

void
ospf_route_table_dump (struct route_table *rt)
{
  struct route_node *rn;
  struct ospf_route *or;
  char buf1[BUFSIZ];
  char buf2[BUFSIZ];
  listnode pnode;
  struct ospf_path *path;

#if 0
  zlog_info ("Type   Dest   Area   Path	 Type	 Cost	Next	 Adv.");
  zlog_info ("					Hop(s)	 Router(s)");
#endif /* 0 */

  zlog_info ("========== OSPF routing table ==========");
  for (rn = route_top (rt); rn; rn = route_next (rn))
    if ((or = rn->info) != NULL)
      {
        if (or->type == OSPF_DESTINATION_NETWORK)
	  {
	    zlog_info ("N %s/%d\t%s\t%s\t%d", 
		       inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
		       rn->p.prefixlen,
		       inet_ntop (AF_INET, &or->u.std.area_id, buf2,
				  BUFSIZ),
		       ospf_path_type_str[or->path_type],
		       or->cost);
	    for (pnode = listhead (or->path); pnode; nextnode (pnode))
	      {
		path = getdata (pnode);
		zlog_info ("  -> %s", inet_ntoa (path->nexthop));
	      }
	  }
        else
	  zlog_info ("R %s\t%s\t%s\t%d", 
		     inet_ntop (AF_INET, &rn->p.u.prefix4, buf1, BUFSIZ),
		     inet_ntop (AF_INET, &or->u.std.area_id, buf2,
				BUFSIZ),
		     ospf_path_type_str[or->path_type],
		     or->cost);
      }
  zlog_info ("========================================");
}

void
ospf_terminate ()
{
  struct ospf *ospf;
  listnode node;

  LIST_LOOP (om->ospf, ospf, node)
    {
      if (ospf->new_table)
	ospf_route_delete (ospf->new_table);
      if (ospf->old_external_route)
	ospf_route_delete (ospf->old_external_route);
    }
}

/* This is 16.4.1 implementation.
   o Intra-area paths using non-backbone areas are always the most preferred.
   o The other paths, intra-area backbone paths and inter-area paths,
     are of equal preference. */
int
ospf_asbr_route_cmp (struct ospf *ospf, struct ospf_route *r1,
		     struct ospf_route *r2)
{
  u_char r1_type, r2_type;

  r1_type = r1->path_type;
  r2_type = r2->path_type;

  /* If RFC1583Compat flag is on -- all paths are equal. */
  if (CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
    return 0;

  /* r1/r2 itself is backbone, and it's Inter-area path. */
  if (OSPF_IS_AREA_ID_BACKBONE (r1->u.std.area_id))
    r1_type = OSPF_PATH_INTER_AREA;
  if (OSPF_IS_AREA_ID_BACKBONE (r2->u.std.area_id))
    r2_type = OSPF_PATH_INTER_AREA;

  return (r1_type - r2_type);
}

/* Compare two routes.
 ret <  0 -- r1 is better.
 ret == 0 -- r1 and r2 are the same.
 ret >  0 -- r2 is better. */
int
ospf_route_cmp (struct ospf *ospf, struct ospf_route *r1,
		struct ospf_route *r2)
{
  int ret = 0;

  /* Path types of r1 and r2 are not the same. */
  if ((ret = (r1->path_type - r2->path_type)))
    return ret;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("Route[Compare]: Path types are the same.");
  /* Path types are the same, compare any cost. */
  switch (r1->path_type)
    {
    case OSPF_PATH_INTRA_AREA:
    case OSPF_PATH_INTER_AREA:
      break;
    case OSPF_PATH_TYPE1_EXTERNAL:
      if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
	{
	  ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
	  if (ret != 0)
	    return ret;
	}
      break;
    case OSPF_PATH_TYPE2_EXTERNAL:
      if ((ret = (r1->u.ext.type2_cost - r2->u.ext.type2_cost)))
	return ret;

      if (!CHECK_FLAG (ospf->config, OSPF_RFC1583_COMPATIBLE))
	{
	  ret = ospf_asbr_route_cmp (ospf, r1->u.ext.asbr, r2->u.ext.asbr);
	  if (ret != 0)
	    return ret;
	}
      break;
    }      

  /* Anyway, compare the costs. */
  return (r1->cost - r2->cost);
}

int
ospf_path_exist (struct list *plist, struct in_addr nexthop,
		 struct ospf_interface *oi)
{
  listnode node;
  struct ospf_path *path;

  for (node = listhead (plist); node; nextnode (node))
    {
      path = node->data;

      if (IPV4_ADDR_SAME (&path->nexthop, &nexthop) && path->oi == oi)
	return 1;
    }
  return 0;
}

void
ospf_route_copy_nexthops_from_vertex (struct ospf_route *to,
				      struct vertex *v)
{
  listnode nnode;
  struct ospf_path *path;
  struct vertex_nexthop *nexthop;

  if (to->path == NULL)
    to->path = list_new ();

  for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
    {
      nexthop = getdata (nnode);

      if (nexthop->oi != NULL) 
	{
	  if (! ospf_path_exist (to->path, nexthop->router, nexthop->oi))
	    {
	      path = ospf_path_new ();
	      path->nexthop = nexthop->router;
	      path->oi = nexthop->oi;
	      listnode_add (to->path, path);
	    }
	}
    }
}

struct ospf_path *
ospf_path_lookup (list plist, struct ospf_path *path)
{
  listnode node;

  for (node = listhead (plist); node; nextnode (node))
    {
      struct ospf_path *op = node->data;

      if (IPV4_ADDR_SAME (&op->nexthop, &path->nexthop) &&
	  IPV4_ADDR_SAME (&op->adv_router, &path->adv_router))
	return op;
    }

  return NULL;
}

void
ospf_route_copy_nexthops (struct ospf_route *to, list from)
{
  listnode node;

  if (to->path == NULL)
    to->path = list_new ();

  for (node = listhead (from); node; nextnode (node))
    /* The same routes are just discarded. */
    if (!ospf_path_lookup (to->path, node->data))
      listnode_add (to->path, ospf_path_dup (node->data));
}

void
ospf_route_subst_nexthops (struct ospf_route *to, list from)
{
  listnode node;
  struct ospf_path *op;

  for (node = listhead (to->path); node; nextnode (node))
    if ((op = getdata (node)) != NULL)
      {
	ospf_path_free (op);
	node->data = NULL;
      }

  list_delete_all_node (to->path);
  ospf_route_copy_nexthops (to, from);
}

void
ospf_route_subst (struct route_node *rn, struct ospf_route *new_or,
		  struct ospf_route *over)
{
  route_lock_node (rn);
  ospf_route_free (rn->info);

  ospf_route_copy_nexthops (new_or, over->path);
  rn->info = new_or;
  route_unlock_node (rn);
}

void
ospf_route_add (struct route_table *rt, struct prefix_ipv4 *p,
		struct ospf_route *new_or, struct ospf_route *over)
{
  struct route_node *rn;

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

  ospf_route_copy_nexthops (new_or, over->path);

  if (rn->info)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_route_add(): something's wrong !");
      route_unlock_node (rn);
      return;
    }

  rn->info = new_or;
}

void
ospf_prune_unreachable_networks (struct route_table *rt)
{
  struct route_node *rn, *next;
  struct ospf_route *or;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("Pruning unreachable networks");

  for (rn = route_top (rt); rn; rn = next)
    {
      next = route_next (rn);
      if (rn->info != NULL)
	{
	  or = rn->info;
	  if (listcount (or->path) == 0)
	    {
	      if (IS_DEBUG_OSPF_EVENT)
		zlog_info ("Pruning route to %s/%d",
			   inet_ntoa (rn->p.u.prefix4), rn->p.prefixlen);

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

void
ospf_prune_unreachable_routers (struct route_table *rtrs)
{
  struct route_node *rn, *next;
  struct ospf_route *or;
  listnode node, nnext;
  list paths;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("Pruning unreachable routers");

  for (rn = route_top (rtrs); rn; rn = next)
    {
      next = route_next (rn);
      if ((paths = rn->info) == NULL)
	continue;

      for (node = listhead (paths); node; node = nnext) 
	{
	  nnext = node->next;

	  or = getdata (node);

	  if (listcount (or->path) == 0)
	    {
	      if (IS_DEBUG_OSPF_EVENT)
		{
		  zlog_info ("Pruning route to rtr %s",
			     inet_ntoa (rn->p.u.prefix4));
		  zlog_info ("               via area %s",
			     inet_ntoa (or->u.std.area_id));
		}

	      listnode_delete (paths, or);
	      ospf_route_free (or);
	    }
	}

      if (listcount (paths) == 0)
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("Pruning router node %s", inet_ntoa (rn->p.u.prefix4));

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

int
ospf_add_discard_route (struct route_table *rt, struct ospf_area *area,
			struct prefix_ipv4 *p)
{
  struct route_node *rn;
  struct ospf_route *or, *new_or;

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

  if (rn == NULL)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_add_discard_route(): router installation error");
      return 0;
    }

  if (rn->info) /* If the route to the same destination is found */
    {
      route_unlock_node (rn);

      or = rn->info;

      if (or->path_type == OSPF_PATH_INTRA_AREA)
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_add_discard_route(): "
		       "an intra-area route exists");
	  return 0;
	}

      if (or->type == OSPF_DESTINATION_DISCARD)
	{
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("ospf_add_discard_route(): "
		       "discard entry already installed");
	  return 0;
	}

      ospf_route_free (rn->info);
  }

  new_or = ospf_route_new ();
  new_or->type = OSPF_DESTINATION_DISCARD;
  new_or->id.s_addr = 0;
  new_or->cost = 0;
  new_or->u.std.area_id = area->area_id;
#ifdef HAVE_NSSA
  new_or->u.std.external_routing = area->external_routing;
#endif /* HAVE_NSSA */
  new_or->path_type = OSPF_PATH_INTER_AREA;
  rn->info = new_or;

  ospf_zebra_add_discard (p);

  return 1;
}

void
ospf_delete_discard_route (struct prefix_ipv4 *p)
{
  ospf_zebra_delete_discard(p);
}