ipr.c

minux操作系统源代码

/*
ipr.c

Copyright 1995 Philip Homburg
*/

#include "inet.h"
#include "clock.h"

#include "type.h"
#include "assert.h"
#include "buf.h"
#include "event.h"
#include "io.h"
#include "ip_int.h"
#include "ipr.h"

THIS_FILE

#define OROUTE_NR		128
#define OROUTE_STATIC_NR	16
#define OROUTE_HASH_ASS_NR	 4
#define OROUTE_HASH_NR		32
#define OROUTE_HASH_MASK	(OROUTE_HASH_NR-1)

#define hash_oroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
	hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
	hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
	hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
	(hash_tmp + (port_nr)) & OROUTE_HASH_MASK)

typedef struct oroute_hash
{
	ipaddr_t orh_addr;
	oroute_t *orh_route;
} oroute_hash_t;

PRIVATE oroute_t oroute_table[OROUTE_NR];
PRIVATE oroute_t *oroute_head;
PRIVATE int static_oroute_nr;
PRIVATE oroute_hash_t oroute_hash_table[OROUTE_HASH_NR][OROUTE_HASH_ASS_NR];

#define IROUTE_NR		512
#define IROUTE_HASH_ASS_NR	 4
#define IROUTE_HASH_NR		32
#define IROUTE_HASH_MASK	(IROUTE_HASH_NR-1)

#define hash_iroute(port_nr, ipaddr, hash_tmp) (hash_tmp= (ipaddr), \
	hash_tmp= (hash_tmp >> 20) ^ hash_tmp, \
	hash_tmp= (hash_tmp >> 10) ^ hash_tmp, \
	hash_tmp= (hash_tmp >> 5) ^ hash_tmp, \
	(hash_tmp + (port_nr)) & IROUTE_HASH_MASK)

typedef struct iroute_hash
{
	ipaddr_t irh_addr;
	iroute_t *irh_route;
} iroute_hash_t;

PRIVATE iroute_t iroute_table[IROUTE_NR];
PRIVATE iroute_hash_t iroute_hash_table[IROUTE_HASH_NR][IROUTE_HASH_ASS_NR];

FORWARD oroute_t *oroute_find_ent ARGS(( int port_nr, ipaddr_t dest ));
FORWARD void oroute_del ARGS(( oroute_t *oroute ));
FORWARD oroute_t *sort_dists ARGS(( oroute_t *oroute ));
FORWARD oroute_t *sort_gws ARGS(( oroute_t *oroute ));
FORWARD	void oroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));
FORWARD	void iroute_uncache_nw ARGS(( ipaddr_t dest, ipaddr_t netmask ));

PUBLIC void ipr_init()
{
	int i;
	oroute_t *oroute;
	iroute_t *iroute;

	for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
		oroute->ort_flags= ORTF_EMPTY;
	static_oroute_nr= 0;
	assert(OROUTE_HASH_ASS_NR == 4);

	for (i= 0, iroute= iroute_table; i<IROUTE_NR; i++, iroute++)
		iroute->irt_flags= IRTF_EMPTY;
	assert(IROUTE_HASH_ASS_NR == 4);
}


PUBLIC iroute_t *iroute_frag(port_nr, dest)
int port_nr;
ipaddr_t dest;
{
	int hash, i;
	iroute_hash_t *iroute_hash;
	iroute_hash_t tmp_hash;
	iroute_t *iroute, *bestroute;
	unsigned long hash_tmp;
	u32_t tmp_mask;

	hash= hash_iroute(port_nr, dest, hash_tmp);
	iroute_hash= &iroute_hash_table[hash][0];
	if (iroute_hash[0].irh_addr == dest)
		iroute= iroute_hash[0].irh_route;
	else if (iroute_hash[1].irh_addr == dest)
	{
		tmp_hash= iroute_hash[1];
		iroute_hash[1]= iroute_hash[0];
		iroute_hash[0]= tmp_hash;
		iroute= tmp_hash.irh_route;
	}
	else if (iroute_hash[2].irh_addr == dest)
	{
		tmp_hash= iroute_hash[2];
		iroute_hash[2]= iroute_hash[1];
		iroute_hash[1]= iroute_hash[0];
		iroute_hash[0]= tmp_hash;
		iroute= tmp_hash.irh_route;
	}
	else if (iroute_hash[3].irh_addr == dest)
	{
		tmp_hash= iroute_hash[3];
		iroute_hash[3]= iroute_hash[2];
		iroute_hash[2]= iroute_hash[1];
		iroute_hash[1]= iroute_hash[0];
		iroute_hash[0]= tmp_hash;
		iroute= tmp_hash.irh_route;
	}
	else
		iroute= NULL;
	if (iroute)
		return iroute;

	bestroute= NULL;
	for (i= 0, iroute= iroute_table; i < IROUTE_NR; i++, iroute++)
	{
		if (!(iroute->irt_flags & IRTF_INUSE))
			continue;
		if (((dest ^ iroute->irt_dest) & iroute->irt_subnetmask) != 0)
			continue;
		if (!bestroute)
		{
			bestroute= iroute;
			continue;
		}

		/* More specific netmasks are better */
		if (iroute->irt_subnetmask != bestroute->irt_subnetmask)
		{
			/* Using two ntohl macros in one expression
			 * is not allowed (tmp_l is modified twice)
			 */
			tmp_mask= ntohl(iroute->irt_subnetmask);
			if (tmp_mask > ntohl(bestroute->irt_subnetmask))
				bestroute= iroute;
			continue;
		}
			
		/* Dynamic routes override static routes */
		if ((iroute->irt_flags & IRTF_STATIC) != 
			(bestroute->irt_flags & IRTF_STATIC))
		{
			if (bestroute->irt_flags & IRTF_STATIC)
				bestroute= iroute;
			continue;
		}

		/* A route to the local interface give an opportunity
		 * to send redirects.
		 */
		if (iroute->irt_port != bestroute->irt_port)
		{
			if (iroute->irt_port == port_nr)
				bestroute= iroute;
			continue;
		}
	}
	if (bestroute == NULL)
		return NULL;

	iroute_hash[3]= iroute_hash[2];
	iroute_hash[2]= iroute_hash[1];
	iroute_hash[1]= iroute_hash[0];
	iroute_hash[0].irh_addr= dest;
	iroute_hash[0].irh_route= bestroute;

	return bestroute;
}

PUBLIC int oroute_frag(port_nr, dest, ttl, msgsize, nexthop)
int port_nr;
ipaddr_t dest;
int ttl;
size_t msgsize;
ipaddr_t *nexthop;
{
	oroute_t *oroute;

	oroute= oroute_find_ent(port_nr, dest);
	if (!oroute || oroute->ort_dist > ttl)
		return EDSTNOTRCH;
	if (msgsize && oroute->ort_mtu && 
		oroute->ort_mtu < msgsize)
	{
		return EPACKSIZE;
	}

	*nexthop= oroute->ort_gateway;
	return NW_OK;
}


PUBLIC int ipr_add_oroute(port_nr, dest, subnetmask, gateway, 
	timeout, dist, mtu, static_route, preference, oroute_p)
int port_nr;
ipaddr_t dest;
ipaddr_t subnetmask;
ipaddr_t gateway;
time_t timeout;
int dist;
int mtu;
int static_route;
i32_t preference;
oroute_t **oroute_p;
{
	int i;
	ip_port_t *ip_port;
	oroute_t *oroute, *oldest_route, *prev, *nw_route, *gw_route, 
		*prev_route;
	time_t currtim, exp_tim, exp_tim_orig;

	oldest_route= 0;
	currtim= get_time();
	if (timeout)
		exp_tim= timeout+currtim;
	else
		exp_tim= 0;

	DBLOCK(0x10, 
		printf("ip[%d]: adding oroute to ", port_nr);
		writeIpAddr(dest);
		printf("["); writeIpAddr(subnetmask); printf("] through ");
		writeIpAddr(gateway);
		printf(" timeout: %lds, distance %d, pref %ld, mtu %d\n",
			(long)timeout/HZ, dist, (long)preference, mtu));

	ip_port= &ip_port_table[port_nr];

	/* Validate gateway */
	if (((gateway ^ ip_port->ip_ipaddr) & ip_port->ip_subnetmask) != 0)
	{
		DBLOCK(1, printf("ip[%d]: (ipr_add_oroute) invalid gateway: ",
			port_nr); writeIpAddr(gateway); printf("\n"));
		return EINVAL;
	}

	if (static_route)
	{
		if (static_oroute_nr >= OROUTE_STATIC_NR)
			return ENOMEM;
		static_oroute_nr++;
	}
	else
	{
		/* Try to track down any old routes. */
		for(oroute= oroute_head; oroute; oroute= oroute->ort_nextnw)
		{
			if (oroute->ort_port != port_nr)
				continue;
			if (oroute->ort_dest == dest &&
				oroute->ort_subnetmask == subnetmask)
			{
				break;
			}
		}
		for(; oroute; oroute= oroute->ort_nextgw)
		{
			if (oroute->ort_gateway == gateway)
				break;
		}
		for(; oroute; oroute= oroute->ort_nextdist)
		{
			if ((oroute->ort_flags & ORTF_STATIC) != 0)
				continue;
			if (oroute->ort_dist > dist)
				continue;
			break;
		}
		if (oroute)
		{
			assert(oroute->ort_port == port_nr);
			if (dest != 0)
			{
				/* The new expire should not be later
				 * than the old expire time. Except for
				 * default routes, where the expire time
				 * is simple set to the new value.
				 */
				exp_tim_orig= oroute->ort_exp_tim;
				if (!exp_tim)
					exp_tim= exp_tim_orig;
				else if (exp_tim_orig &&
					exp_tim > exp_tim_orig)
				{
					exp_tim= exp_tim_orig;
				}
			}
			oroute_del(oroute);
			oroute->ort_flags= 0;
			oldest_route= oroute;
		}
	}

	if (oldest_route == NULL)
	{
		/* Look for an unused entry, or remove an existing one */
		for (i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
		{
			if ((oroute->ort_flags & ORTF_INUSE) == 0)
				break;
			if (oroute->ort_exp_tim && oroute->ort_exp_tim < 
				currtim)
			{
				oroute_del(oroute);
				oroute->ort_flags= 0;
				break;
			}
			if (oroute->ort_flags & ORTF_STATIC)
				continue;
			if (oroute->ort_dest == 0)
			{
				/* Never remove default routes. */
				continue;
			}
			if (oldest_route == NULL)
			{
				oldest_route= oroute;
				continue;
			}
			if (oroute->ort_timestamp < oldest_route->ort_timestamp)
			{
				oldest_route= oroute;
			}
		}
		if (i < OROUTE_NR)
			oldest_route= oroute;
		else
		{
			assert(oldest_route);
			oroute_del(oldest_route);
			oldest_route->ort_flags= 0;
		}
	}

	oldest_route->ort_dest= dest;
	oldest_route->ort_gateway= gateway;
	oldest_route->ort_subnetmask= subnetmask;
	oldest_route->ort_exp_tim= exp_tim;
	oldest_route->ort_timestamp= currtim;
	oldest_route->ort_dist= dist;
	oldest_route->ort_mtu= mtu;
	oldest_route->ort_port= port_nr;
	oldest_route->ort_flags= ORTF_INUSE;
	oldest_route->ort_pref= preference;
	if (static_route)
		oldest_route->ort_flags |= ORTF_STATIC;
	
	/* Insert the route by tearing apart the routing table, 
	 * and insert the entry during the reconstruction.
	 */
	for (prev= 0, nw_route= oroute_head; nw_route; 
		prev= nw_route, nw_route= nw_route->ort_nextnw)
	{
		if (nw_route->ort_port != port_nr)
			continue;
		if (nw_route->ort_dest == dest &&
			nw_route->ort_subnetmask == subnetmask)
		{
			if (prev)
				prev->ort_nextnw= nw_route->ort_nextnw;
			else
				oroute_head= nw_route->ort_nextnw;
			break;
		}
	}
	prev_route= nw_route;
	for(prev= NULL, gw_route= nw_route; gw_route; 
		prev= gw_route, gw_route= gw_route->ort_nextgw)
	{
		if (gw_route->ort_gateway == gateway)
		{
			if (prev)
				prev->ort_nextgw= gw_route->ort_nextgw;
			else
				nw_route= gw_route->ort_nextgw;
			break;
		}
	}
	oldest_route->ort_nextdist= gw_route;
	gw_route= oldest_route;
	gw_route= sort_dists(gw_route);
	gw_route->ort_nextgw= nw_route;
	nw_route= gw_route;
	nw_route= sort_gws(nw_route);
	nw_route->ort_nextnw= oroute_head;
	oroute_head= nw_route;
	if (nw_route != prev_route)
		oroute_uncache_nw(nw_route->ort_dest, nw_route->ort_subnetmask);
	if (oroute_p != NULL)
		*oroute_p= oldest_route;
	return NW_OK;
}

PUBLIC int ipr_del_oroute(port_nr, dest, subnetmask, gateway, static_route)
int port_nr;
ipaddr_t dest;
ipaddr_t subnetmask;
ipaddr_t gateway;
int static_route;
{
	int i;
	oroute_t *oroute;

	for(i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
	{
		if ((oroute->ort_flags & ORTF_INUSE) == 0)
			continue;
		if (oroute->ort_port != port_nr ||
			oroute->ort_dest != dest ||
			oroute->ort_subnetmask != subnetmask ||
			oroute->ort_gateway != gateway)
		{
			continue;
		}
		if (!!(oroute->ort_flags & ORTF_STATIC) != static_route)
			continue;
		break;
	}

	if (i == OROUTE_NR)
		return ESRCH;

	if (static_route)
		static_oroute_nr--;

	oroute_del(oroute);
	oroute->ort_flags &= ~ORTF_INUSE;
	return NW_OK;
}



PUBLIC void ipr_chk_otab(port_nr, addr, mask)
int port_nr;
ipaddr_t addr;
ipaddr_t mask;
{
	int i;
	oroute_t *oroute;

	DBLOCK(1,
		printf("ip[%d] (ipr_chk_otab): addr ", port_nr);
		writeIpAddr(addr);
		printf(" mask ");
		writeIpAddr(mask);
		printf("\n");
	);

	if (addr == 0)
	{
		/* Special hack to flush entries for an interface that
		 * goes down.
		 */
		addr= mask= HTONL(0xffffffff);
	}

	for(i= 0, oroute= oroute_table; i<OROUTE_NR; i++, oroute++)
	{
		if ((oroute->ort_flags & ORTF_INUSE) == 0)
			continue;
		if (oroute->ort_port != port_nr ||
			((oroute->ort_gateway ^ addr) & mask) == 0)
		{
			continue;
		}
		DBLOCK(1, printf("ip[%d] (ipr_chk_otab): deleting route to ",
				port_nr);
			writeIpAddr(oroute->ort_dest);
			printf(" gw ");
			writeIpAddr(oroute->ort_gateway);
			printf("\n"));

		if (oroute->ort_flags & ORTF_STATIC)
			static_oroute_nr--;
		oroute_del(oroute);
		oroute->ort_flags &= ~ORTF_INUSE;
	}
}


PUBLIC void ipr_gateway_down(port_nr, gateway, timeout)
int port_nr;
ipaddr_t gateway;
time_t timeout;
{
	oroute_t *route_ind;
	time_t currtim;
	int i;
	int result;

	currtim= get_time();
	for (i= 0, route_ind= oroute_table; i<OROUTE_NR; i++, route_ind++)
	{
		if (!(route_ind->ort_flags & ORTF_INUSE))
			continue;
		if (route_ind->ort_gateway != gateway)
			continue;
		if (route_ind->ort_exp_tim && route_ind->ort_exp_tim < currtim)
			continue;
		result= ipr_add_oroute(port_nr, route_ind->ort_dest, 
			route_ind->ort_subnetmask, gateway, 
			timeout, ORTD_UNREACHABLE, route_ind->ort_mtu,
			FALSE, 0, NULL);
		assert(result == NW_OK);
	}
}


PUBLIC void ipr_destunrch(port_nr, dest, netmask, timeout)
int port_nr;
ipaddr_t dest;
ipaddr_t netmask;
time_t timeout;
{
	oroute_t *oroute;
	int result;

	oroute= oroute_find_ent(port_nr, dest);

	if (!oroute)
	{
		DBLOCK(1, printf("ip[%d]: got a dest unreachable for ",
			port_nr);
			writeIpAddr(dest); printf("but no route present\n"));

		return;
	}
	result= ipr_add_oroute(port_nr, dest, netmask, oroute->ort_gateway, 
		timeout, ORTD_UNREACHABLE, oroute->ort_mtu, FALSE, 0, NULL);
	assert(result == NW_OK);
}


PUBLIC void ipr_redirect(port_nr, dest, netmask, old_gateway, new_gateway, 
	timeout)
int port_nr;
ipaddr_t dest;
ipaddr_t netmask;
ipaddr_t old_gateway;
ipaddr_t new_gateway;
time_t timeout;
{
	oroute_t *oroute;
	ip_port_t *ip_port;
	int result;

	ip_port= &ip_port_table[port_nr];
	oroute= oroute_find_ent(port_nr, dest);

	if (!oroute)
	{
		DBLOCK(1, printf("ip[%d]: got a redirect for ", port_nr);
			writeIpAddr(dest); printf("but no route present\n"));
		return;
	}
	if (oroute->ort_gateway != old_gateway)
	{
		DBLOCK(1, printf("ip[%d]: got a redirect from ", port_nr);
			writeIpAddr(old_gateway); printf(" for ");
			writeIpAddr(dest); printf(" but curr gateway is ");
			writeIpAddr(oroute->ort_gateway); printf("\n"));
		return;
	}
	if ((new_gateway ^ ip_port->ip_ipaddr) & ip_port->ip_subnetmask)
	{
		DBLOCK(1, printf("ip[%d]: redirect from ", port_nr);
			writeIpAddr(old_gateway); printf(" for ");
			writeIpAddr(dest); printf(" but new gateway ");
			writeIpAddr(new_gateway);
			printf(" is not on local subnet\n"));
		return;
	}
	if (oroute->ort_flags & ORTF_STATIC)
	{
		if (oroute->ort_dest == dest)
		{
			DBLOCK(1, printf("ip[%d]: got a redirect for ",
				port_nr);
				writeIpAddr(dest);
				printf("but route is fixed\n"));
			return;
		}
	}
	else
	{
		result= ipr_add_oroute(port_nr, dest, netmask, 
			oroute->ort_gateway, HZ, ORTD_UNREACHABLE, 
			oroute->ort_mtu, FALSE, 0, NULL);
		assert(result == NW_OK);
	}
	result= ipr_add_oroute(port_nr, dest, netmask, new_gateway,
		timeout, 1, oroute->ort_mtu, FALSE, 0, NULL);
	assert(result == NW_OK);
}


PUBLIC void ipr_ttl_exc(port_nr, dest, netmask, timeout)
int port_nr;
ipaddr_t dest;
ipaddr_t netmask;
time_t timeout;
{
	oroute_t *oroute;
	int new_dist;
	int result;

	oroute= oroute_find_ent(port_nr, dest);