*: add git-reindent-branch.py

[mirror_frr.git] / ospfd / ospf_ia.c

/*
 * OSPF inter-area routing.
 * Copyright (C) 1999, 2000 Alex Zinin, 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 this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */


#include <zebra.h>

#include "thread.h"
#include "memory.h"
#include "hash.h"
#include "linklist.h"
#include "prefix.h"
#include "table.h"
#include "log.h"

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

static struct ospf_route *ospf_find_abr_route(struct route_table *rtrs,
					      struct prefix_ipv4 *abr,
					      struct ospf_area *area)
{
	struct route_node *rn;
	struct ospf_route * or ;
	struct listnode *node;

	if ((rn = route_node_lookup(rtrs, (struct prefix *)abr)) == NULL)
		return NULL;

	route_unlock_node(rn);

	for (ALL_LIST_ELEMENTS_RO((struct list *)rn->info, node, or))
		if (IPV4_ADDR_SAME(& or->u.std.area_id, &area->area_id)
		    && (or->u.std.flags & ROUTER_LSA_BORDER))
			return or ;

	return NULL;
}

static void ospf_ia_network_route(struct ospf *ospf, struct route_table *rt,
				  struct prefix_ipv4 *p,
				  struct ospf_route *new_or,
				  struct ospf_route *abr_or)
{
	struct route_node *rn1;
	struct ospf_route * or ;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug(
			"ospf_ia_network_route(): processing summary route to %s/%d",
			inet_ntoa(p->prefix), p->prefixlen);

	/* Find a route to the same dest */
	if ((rn1 = route_node_lookup(rt, (struct prefix *)p))) {
		int res;

		route_unlock_node(rn1);

		if ((or = rn1->info)) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_network_route(): "
					"Found a route to the same network");
			/* Check the existing route. */
			if ((res = ospf_route_cmp(ospf, new_or, or)) < 0) {
				/* New route is better, so replace old one. */
				ospf_route_subst(rn1, new_or, abr_or);
			} else if (res == 0) {
				/* New and old route are equal, so next hops can
				 * be added. */
				route_lock_node(rn1);
				ospf_route_copy_nexthops(or, abr_or->paths);
				route_unlock_node(rn1);

				/* new route can be deleted, because existing
				 * route has been updated. */
				ospf_route_free(new_or);
			} else {
				/* New route is worse, so free it. */
				ospf_route_free(new_or);
				return;
			}
		} /* if (or)*/
	}	 /*if (rn1)*/
	else {    /* no route */
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_ia_network_route(): add new route to %s/%d",
				inet_ntoa(p->prefix), p->prefixlen);
		ospf_route_add(rt, p, new_or, abr_or);
	}
}

static void ospf_ia_router_route(struct ospf *ospf, struct route_table *rtrs,
				 struct prefix_ipv4 *p,
				 struct ospf_route *new_or,
				 struct ospf_route *abr_or)
{
	struct ospf_route * or = NULL;
	struct route_node *rn;
	int ret;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("ospf_ia_router_route(): considering %s/%d",
			   inet_ntoa(p->prefix), p->prefixlen);
	/* Find a route to the same dest */
	rn = route_node_get(rtrs, (struct prefix *)p);

	if (rn->info == NULL)
		/* This is a new route */
		rn->info = list_new();
	else {
		struct ospf_area *or_area;
		or_area = ospf_area_lookup_by_area_id(ospf,
						      new_or->u.std.area_id);
		assert(or_area);
		/* This is an additional route */
		route_unlock_node(rn);
		or = ospf_find_asbr_route_through_area(rtrs, p, or_area);
	}

	if (or) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_ia_router_route(): "
				"a route to the same ABR through the same area exists");
		/* New route is better */
		if ((ret = ospf_route_cmp(ospf, new_or, or)) < 0) {
			listnode_delete(rn->info, or);
			ospf_route_free(or);
			/* proceed down */
		}
		/* Routes are the same */
		else if (ret == 0) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_router_route(): merging the new route");

			ospf_route_copy_nexthops(or, abr_or->paths);
			ospf_route_free(new_or);
			return;
		}
		/* New route is worse */
		else {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_router_route(): skipping the new route");
			ospf_route_free(new_or);
			return;
		}
	}

	ospf_route_copy_nexthops(new_or, abr_or->paths);

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("ospf_ia_router_route(): adding the new route");

	listnode_add(rn->info, new_or);
}


static int process_summary_lsa(struct ospf_area *area, struct route_table *rt,
			       struct route_table *rtrs, struct ospf_lsa *lsa)
{
	struct ospf *ospf = area->ospf;
	struct ospf_area_range *range;
	struct ospf_route *abr_or, *new_or;
	struct summary_lsa *sl;
	struct prefix_ipv4 p, abr;
	u_int32_t metric;

	if (lsa == NULL)
		return 0;

	sl = (struct summary_lsa *)lsa->data;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("process_summary_lsa(): LS ID: %s",
			   inet_ntoa(sl->header.id));

	metric = GET_METRIC(sl->metric);

	if (metric == OSPF_LS_INFINITY)
		return 0;

	if (IS_LSA_MAXAGE(lsa))
		return 0;

	if (ospf_lsa_is_self_originated(area->ospf, lsa))
		return 0;

	p.family = AF_INET;
	p.prefix = sl->header.id;

	if (sl->header.type == OSPF_SUMMARY_LSA)
		p.prefixlen = ip_masklen(sl->mask);
	else
		p.prefixlen = IPV4_MAX_BITLEN;

	apply_mask_ipv4(&p);

	if (sl->header.type == OSPF_SUMMARY_LSA
	    && (range = ospf_area_range_match_any(ospf, &p))
	    && ospf_area_range_active(range))
		return 0;

	/* XXX: This check seems dubious to me. If an ABR has already decided
	 * to consider summaries received in this area, then why would one wish
	 * to exclude default?
	 */
	if (IS_OSPF_ABR(ospf) && ospf->abr_type != OSPF_ABR_STAND
	    && area->external_routing != OSPF_AREA_DEFAULT
	    && p.prefix.s_addr == OSPF_DEFAULT_DESTINATION && p.prefixlen == 0)
		return 0; /* Ignore summary default from a stub area */

	abr.family = AF_INET;
	abr.prefix = sl->header.adv_router;
	abr.prefixlen = IPV4_MAX_BITLEN;
	apply_mask_ipv4(&abr);

	abr_or = ospf_find_abr_route(rtrs, &abr, area);

	if (abr_or == NULL)
		return 0;

	new_or = ospf_route_new();
	new_or->type = OSPF_DESTINATION_NETWORK;
	new_or->id = sl->header.id;
	new_or->mask = sl->mask;
	new_or->u.std.options = sl->header.options;
	new_or->u.std.origin = (struct lsa_header *)sl;
	new_or->cost = abr_or->cost + metric;
	new_or->u.std.area_id = area->area_id;
	new_or->u.std.external_routing = area->external_routing;
	new_or->path_type = OSPF_PATH_INTER_AREA;

	if (sl->header.type == OSPF_SUMMARY_LSA)
		ospf_ia_network_route(ospf, rt, &p, new_or, abr_or);
	else {
		new_or->type = OSPF_DESTINATION_ROUTER;
		new_or->u.std.flags = ROUTER_LSA_EXTERNAL;
		ospf_ia_router_route(ospf, rtrs, &p, new_or, abr_or);
	}

	return 0;
}

static void ospf_examine_summaries(struct ospf_area *area,
				   struct route_table *lsdb_rt,
				   struct route_table *rt,
				   struct route_table *rtrs)
{
	struct ospf_lsa *lsa;
	struct route_node *rn;

	LSDB_LOOP(lsdb_rt, rn, lsa)
	process_summary_lsa(area, rt, rtrs, lsa);
}

int ospf_area_is_transit(struct ospf_area *area)
{
	return (area->transit == OSPF_TRANSIT_TRUE)
	       || ospf_full_virtual_nbrs(
			  area); /* Cisco forgets to set the V-bit :( */
}

static void ospf_update_network_route(struct ospf *ospf, struct route_table *rt,
				      struct route_table *rtrs,
				      struct summary_lsa *lsa,
				      struct prefix_ipv4 *p,
				      struct ospf_area *area)
{
	struct route_node *rn;
	struct ospf_route * or, *abr_or, *new_or;
	struct prefix_ipv4 abr;
	u_int32_t cost;

	abr.family = AF_INET;
	abr.prefix = lsa->header.adv_router;
	abr.prefixlen = IPV4_MAX_BITLEN;
	apply_mask_ipv4(&abr);

	abr_or = ospf_find_abr_route(rtrs, &abr, area);

	if (abr_or == NULL) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): can't find a route to the ABR");
		return;
	}

	cost = abr_or->cost + GET_METRIC(lsa->metric);

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

	if (!rn) {
		if (ospf->abr_type != OSPF_ABR_SHORTCUT)
			return; /* Standard ABR can update only already
				   installed
				   backbone paths */
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): "
				"Allowing Shortcut ABR to add new route");
		new_or = ospf_route_new();
		new_or->type = OSPF_DESTINATION_NETWORK;
		new_or->id = lsa->header.id;
		new_or->mask = lsa->mask;
		new_or->u.std.options = lsa->header.options;
		new_or->u.std.origin = (struct lsa_header *)lsa;
		new_or->cost = cost;
		new_or->u.std.area_id = area->area_id;
		new_or->u.std.external_routing = area->external_routing;
		new_or->path_type = OSPF_PATH_INTER_AREA;
		ospf_route_add(rt, p, new_or, abr_or);

		return;
	} else {
		route_unlock_node(rn);
		if (rn->info == NULL)
			return;
	}

	or = rn->info;

	if (or->path_type != OSPF_PATH_INTRA_AREA &&
	    or->path_type != OSPF_PATH_INTER_AREA) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): ERR: path type is wrong");
		return;
	}

	if (ospf->abr_type == OSPF_ABR_SHORTCUT) {
		if (or->path_type == OSPF_PATH_INTRA_AREA
			      && !OSPF_IS_AREA_ID_BACKBONE(or->u.std.area_id)) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_update_network_route(): Shortcut: "
					"this intra-area path is not backbone");
			return;
		}
	} else /* Not Shortcut ABR */
	{
		if (!OSPF_IS_AREA_ID_BACKBONE(or->u.std.area_id)) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_update_network_route(): "
					"route is not BB-associated");
			return; /* We can update only BB routes */
		}
	}

	if (or->cost < cost) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): new route is worse");
		return;
	}

	if (or->cost == cost) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): "
				"new route is same distance, adding nexthops");
		ospf_route_copy_nexthops(or, abr_or->paths);
	}

	if (or->cost > cost) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_network_route(): "
				"new route is better, overriding nexthops");
		ospf_route_subst_nexthops(or, abr_or->paths);
		or->cost = cost;

		if ((ospf->abr_type == OSPF_ABR_SHORTCUT)
		    && !OSPF_IS_AREA_ID_BACKBONE(or->u.std.area_id)) {
			or->path_type = OSPF_PATH_INTER_AREA;
			or->u.std.area_id = area->area_id;
			or->u.std.external_routing = area->external_routing;
			/* Note that we can do this only in Shortcut ABR mode,
			   because standard ABR must leave the route type and
			   area
			   unchanged
			*/
		}
	}
}

static void ospf_update_router_route(struct ospf *ospf,
				     struct route_table *rtrs,
				     struct summary_lsa *lsa,
				     struct prefix_ipv4 *p,
				     struct ospf_area *area)
{
	struct ospf_route * or, *abr_or, *new_or;
	struct prefix_ipv4 abr;
	u_int32_t cost;

	abr.family = AF_INET;
	abr.prefix = lsa->header.adv_router;
	abr.prefixlen = IPV4_MAX_BITLEN;
	apply_mask_ipv4(&abr);

	abr_or = ospf_find_abr_route(rtrs, &abr, area);

	if (abr_or == NULL) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_update_router_route(): can't find a route to the ABR");
		return;
	}

	cost = abr_or->cost + GET_METRIC(lsa->metric);

	/* First try to find a backbone path,
	   because standard ABR can update only BB-associated paths */

	if ((ospf->backbone == NULL) && (ospf->abr_type != OSPF_ABR_SHORTCUT))
		return; /* no BB area, not Shortcut ABR, exiting */

	/* find the backbone route, if possible */
	if ((ospf->backbone == NULL)
	    || !(or = ospf_find_asbr_route_through_area(rtrs, p,
							ospf->backbone))) {
		if (ospf->abr_type != OSPF_ABR_SHORTCUT)

			/* route to ASBR through the BB not found
			   the router is not Shortcut ABR, exiting */

			return;
		else
		/* We're a Shortcut ABR*/
		{
			/* Let it either add a new router or update the route
			   through the same (non-BB) area. */

			new_or = ospf_route_new();
			new_or->type = OSPF_DESTINATION_ROUTER;
			new_or->id = lsa->header.id;
			new_or->mask = lsa->mask;
			new_or->u.std.options = lsa->header.options;
			new_or->u.std.origin = (struct lsa_header *)lsa;
			new_or->cost = cost;
			new_or->u.std.area_id = area->area_id;
			new_or->u.std.external_routing = area->external_routing;
			new_or->path_type = OSPF_PATH_INTER_AREA;
			new_or->u.std.flags = ROUTER_LSA_EXTERNAL;
			ospf_ia_router_route(ospf, rtrs, p, new_or, abr_or);

			return;
		}
	}

	/* At this point the "or" is always bb-associated */

	if (!(or->u.std.flags & ROUTER_LSA_EXTERNAL)) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_upd_router_route(): the remote router is not an ASBR");
		return;
	}

	if (or->path_type != OSPF_PATH_INTRA_AREA &&
	    or->path_type != OSPF_PATH_INTER_AREA)
		return;

	if (or->cost < cost)
		return;

	else if (or->cost == cost)
		ospf_route_copy_nexthops(or, abr_or->paths);

	else if (or->cost > cost) {
		ospf_route_subst_nexthops(or, abr_or->paths);
		or->cost = cost;

		/* Even if the ABR runs in Shortcut mode, we can't change
		   the path type and area, because the "or" is always
		   bb-associated
		   at this point and even Shortcut ABR can't change these
		   attributes */
	}
}

static int process_transit_summary_lsa(struct ospf_area *area,
				       struct route_table *rt,
				       struct route_table *rtrs,
				       struct ospf_lsa *lsa)
{
	struct ospf *ospf = area->ospf;
	struct summary_lsa *sl;
	struct prefix_ipv4 p;
	u_int32_t metric;

	if (lsa == NULL)
		return 0;

	sl = (struct summary_lsa *)lsa->data;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("process_transit_summaries(): LS ID: %s",
			   inet_ntoa(lsa->data->id));
	metric = GET_METRIC(sl->metric);

	if (metric == OSPF_LS_INFINITY) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"process_transit_summaries(): metric is infinity, skip");
		return 0;
	}

	if (IS_LSA_MAXAGE(lsa)) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"process_transit_summaries(): This LSA is too old");
		return 0;
	}

	if (ospf_lsa_is_self_originated(area->ospf, lsa)) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"process_transit_summaries(): This LSA is mine, skip");
		return 0;
	}

	p.family = AF_INET;
	p.prefix = sl->header.id;

	if (sl->header.type == OSPF_SUMMARY_LSA)
		p.prefixlen = ip_masklen(sl->mask);
	else
		p.prefixlen = IPV4_MAX_BITLEN;

	apply_mask_ipv4(&p);

	if (sl->header.type == OSPF_SUMMARY_LSA)
		ospf_update_network_route(ospf, rt, rtrs, sl, &p, area);
	else
		ospf_update_router_route(ospf, rtrs, sl, &p, area);

	return 0;
}

static void ospf_examine_transit_summaries(struct ospf_area *area,
					   struct route_table *lsdb_rt,
					   struct route_table *rt,
					   struct route_table *rtrs)
{
	struct ospf_lsa *lsa;
	struct route_node *rn;

	LSDB_LOOP(lsdb_rt, rn, lsa)
	process_transit_summary_lsa(area, rt, rtrs, lsa);
}

void ospf_ia_routing(struct ospf *ospf, struct route_table *rt,
		     struct route_table *rtrs)
{
	struct ospf_area *area;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("ospf_ia_routing():start");

	if (IS_OSPF_ABR(ospf)) {
		struct listnode *node;
		struct ospf_area *area;

		switch (ospf->abr_type) {
		case OSPF_ABR_STAND:
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug("ospf_ia_routing():Standard ABR");

			if ((area = ospf->backbone)) {
				struct listnode *node;

				if (IS_DEBUG_OSPF_EVENT) {
					zlog_debug(
						"ospf_ia_routing():backbone area found");
					zlog_debug(
						"ospf_ia_routing():examining summaries");
				}

				OSPF_EXAMINE_SUMMARIES_ALL(area, rt, rtrs);

				for (ALL_LIST_ELEMENTS_RO(ospf->areas, node,
							  area))
					if (area != ospf->backbone)
						if (ospf_area_is_transit(area))
							OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
								area, rt, rtrs);
			} else if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_routing():backbone area NOT found");
			break;
		case OSPF_ABR_IBM:
		case OSPF_ABR_CISCO:
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_routing():Alternative Cisco/IBM ABR");
			area = ospf->backbone; /* Find the BB */

			/* If we have an active BB connection */
			if (area && ospf_act_bb_connection(ospf)) {
				if (IS_DEBUG_OSPF_EVENT) {
					zlog_debug(
						"ospf_ia_routing(): backbone area found");
					zlog_debug(
						"ospf_ia_routing(): examining BB summaries");
				}

				OSPF_EXAMINE_SUMMARIES_ALL(area, rt, rtrs);

				for (ALL_LIST_ELEMENTS_RO(ospf->areas, node,
							  area))
					if (area != ospf->backbone)
						if (ospf_area_is_transit(area))
							OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
								area, rt, rtrs);
			} else { /* No active BB connection--consider all areas
				  */
				if (IS_DEBUG_OSPF_EVENT)
					zlog_debug(
						"ospf_ia_routing(): "
						"Active BB connection not found");
				for (ALL_LIST_ELEMENTS_RO(ospf->areas, node,
							  area))
					OSPF_EXAMINE_SUMMARIES_ALL(area, rt,
								   rtrs);
			}
			break;
		case OSPF_ABR_SHORTCUT:
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"ospf_ia_routing():Alternative Shortcut");
			area = ospf->backbone; /* Find the BB */

			/* If we have an active BB connection */
			if (area && ospf_act_bb_connection(ospf)) {
				if (IS_DEBUG_OSPF_EVENT) {
					zlog_debug(
						"ospf_ia_routing(): backbone area found");
					zlog_debug(
						"ospf_ia_routing(): examining BB summaries");
				}
				OSPF_EXAMINE_SUMMARIES_ALL(area, rt, rtrs);
			}

			for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area))
				if (area != ospf->backbone)
					if (ospf_area_is_transit(area)
					    || ((area->shortcut_configured
						 != OSPF_SHORTCUT_DISABLE)
						&& ((ospf->backbone == NULL)
						    || ((area->shortcut_configured
							 == OSPF_SHORTCUT_ENABLE)
							&& area->shortcut_capability))))
						OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
							area, rt, rtrs);
			break;
		default:
			break;
		}
	} else {
		struct listnode *node;

		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_ia_routing():not ABR, considering all areas");

		for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area))
			OSPF_EXAMINE_SUMMARIES_ALL(area, rt, rtrs);
	}
}