rripfwd.c

用于嵌入式系统的TCP/IP协议栈及若干服务

/*
*            Copyright (c) 1998-2001 by NETsilicon Inc.
*
*  This software is copyrighted by and is the sole property of
*  NETsilicon.  All rights, title, ownership, or other interests
*  in the software remain the property of NETsilicon.  This
*  software may only be used in accordance with the corresponding
*  license agreement.  Any unauthorized use, duplication, transmission,
*  distribution, or disclosure of this software is expressly forbidden.
*
*  This Copyright notice may not be removed or modified without prior
*  written consent of NETsilicon.
*
*  NETsilicon, reserves the right to modify this software
*  without notice.
*
*  NETsilicon
*  411 Waverley Oaks Road                  USA 781.647.1234
*  Suite 227                               http://www.netsilicon.com
*  Waltham, MA 02452                       [e-mail]
*
*************************************************************************
*  $Name: Fusion 6.52 Fusion 6.51 $
*  $Date: 2001/09/20 10:30:32 $
*  $Source: M:/psisrc/routing/rrfdb/rcs/rripfwd.c $
*  $Revision: 1.10 $
*
***************************************************************************
*  File Description: Find the next hop for forwarding of IP packets  
***************************************************************************/
#include "riproute.h"
#include "rrfwd.h"
#include "nerrno.h"


/****************************
map tos to which fwd part of route
to use. if non default tos not
supported, everything maps to
use default. Note that tos values
are, per rfc1349, considered an
enumerated int, not a bit map.
Values with more than one bit
set are therefore distinct TOS.
If a particular routing protocol
does not support a tos, it uses
default. Note that we only support
the main 4 tos. Packets with more
than one bit set therefore use
default tos.

TOS indices in route entries:
0 default
1 monetary cost
2 reliability
3 throughput
4 delay
****************************/
#ifdef ALL_IP_METRICS
static int tos_map[32] = {
	0, 0, 1, 0, 2, 0, 0, 0,
	3, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0,
	4, 0, 0, 0, 0, 0, 0, 0
};
#else
static int tos_map[32] = {
	0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0
};
#endif

#ifdef IP_USE_PTREE
fnc_prot(int, ipRtMatchLen,(rripa,iproute_ent_pt))
fnc_prot(iproute_ent_pt, ipRtFindPart2,(rripa))
/****************************************************
IpGetNextHop:

	Finds next hop subnet address and circuit to
	forward PDU to. 

	returns:	Route found via router:
			 snad and c filled in.
			Destination is direct net or us:
			 c= dest circ, snad ptr = 0.
			Couldn't find route:
			 c = INVALID_CIRC.
			

*****************************************************/
arpent_pt IpGetNextHop(register byte *ap,int *cid,
                             int tos)
{
	int             jlen, mlen;
	iproute_ent_pt         srec, nrec;
	rripa          ta,mmask;
	byte            b;
	int             tbit = 0;
	int             tag;
	rripa ipadd;
	arpent_pt rp;
	int nextmp;
	int tm = tos_map[tos];
	TOSFWD *tp;

	/* 0 illegal */
	ipadd = cXIPA(ap);
	if(!ipadd){
		*cid = INVALID_CIRC;
		return( (arpent_pt)0 );
	}

	/* first match ? */
	srec = i_node->rn_pthead;
	if(srec) while (1) {
		tbit += srec->iprt_skip;

		/* if we go any further, we wont get any
	 	   more match bits anyway
		*/
		b = i_node->rn_rtl2m[tbit-1];
		if((ipadd & b) != (srec->iprt_ipa.ip_add &b)){
			break;
		}

		IPV4BIT(ipadd, tbit - 1, b);
		if (b) {

			/* take right link */
			tag = srec->iprt_rtag;
			srec = srec->iprt_rlink;
		} else {

			/* take left link */
			tag = srec->iprt_ltag;
			srec = srec->iprt_llink;
		}

		/*
		 * we know that if there is a match, tbits 
		   match those in
		 * srec. however, we dont know if bits 
		   between skips match.
		*/

		if (tag) {
			break;
		}
	}
	/* weve got some bits match, but dont know it
	   address does up to route mask. traverse routes
	   with equal ipadd, but different mask.
	*/
	nrec = srec;
	while (nrec) {
		if ( (ipadd & nrec->iprt_ipa.ip_mask) ==
		             nrec->iprt_ipa.ip_add) {

			/* we have a matching nrec, increment use
				count and return first adj */

			/* if local dest or direct net, return c=0 */
			if(!nrec->t[0].iprt_fent[0]){

				*cid = nrec->iprt_cid;
				return( (arpent_pt)0 );
			}
			if(nrec->t[tm].iprt_cost == -1){
				/* use default tos */
				tp = &nrec->t[0];
			}
			else{ /* use requested tos */ 
				tp = &nrec->t[tm];
			}
#ifdef IP_LOAD_SHARE
			nextmp = tp->iprt_next_adj;
	
			*cid= tp->iprt_fent[nextmp]->ae_cid;
			rp= tp->iprt_fent[nextmp];

			if(tp->iprt_numadj > tp->iprt_next_adj +1){
				tp->iprt_next_adj ++;
			}
			else{
				tp->iprt_next_adj= 0;
			}
#else

			*cid= tp->iprt_fent[0]->ae_cid;
			rp= tp->iprt_fent[0];

#endif
			return(rp);
		}
		nrec = nrec->iprt_dup;
	}

	if (!srec){
		*cid = INVALID_CIRC;
		return( (arpent_pt)0 );
	}

	/* determine how many bits match, +1 because
	   we want to look again at matchlen
	*/
	jlen = ipRtMatchLen(ipadd, srec) +1;

	/* look for routes with shorter masks, try
	   each mask len we have in table
	*/
	ta = ipadd;
	while ((mlen = i_node->rn_rtmasks[jlen]) >= 0) {
		mmask = i_node->rn_rtl2m[mlen];
		ta &= mmask;
		/* should be exact match */
		nrec = ipRtFindPart2(ta);
		if (nrec && (ta == nrec->iprt_ipa.ip_add)) {
			/* verify route has short enough mask */
			while (nrec) {
				if (mmask >= nrec->iprt_ipa.ip_mask) {
					/* we have a matching rent, increment use
						count and return first adj */

					/* if local dest or direct net, return c=0 */
					if(!nrec->t[0].iprt_fent[0]){

						*cid = nrec->iprt_cid;
						return( (arpent_pt)0 );
					}
					if(nrec->t[tm].iprt_cost == -1){
						/* use default tos */
						tp = &nrec->t[0];
					}
					else{ /* use requested tos */ 
						tp = &nrec->t[tm];
					}
#ifdef IP_LOAD_SHARE
					nextmp = tp->iprt_next_adj;
	
					*cid= tp->iprt_fent[nextmp]->ae_cid;
					rp= tp->iprt_fent[nextmp];

					if(tp->iprt_numadj > tp->iprt_next_adj +1){
						tp->iprt_next_adj ++;
					}
					else{
						tp->iprt_next_adj= 0;
					}
#else

					*cid= tp->iprt_fent[0]->ae_cid;
					rp= tp->iprt_fent[0];

#endif
					return(rp);

				}
				nrec = nrec->iprt_dup;
			}
		}
		jlen = mlen;
	}
	*cid = INVALID_CIRC;
	return( (arpent_pt)0 );
}

#else

/****************************************************
IpGetNextHop:

	Finds next hop subnet address and circuit to
	forward PDU to. 

	returns:	Route found via router:
			 snad and c filled in.
			Destination is direct net or us:
			 c= dest circ, snad ptr = 0.
			Couldn't find route:
			 c = INVALID_CIRC.
			

*****************************************************/
arpent_pt IpGetNextHop(byte *ap, int *cid, int tos)
{
	rripa ipadd;
	byte key;
	iproute_ent_pt rent;
	arpent_pt rp;
#ifdef IP_LOAD_SHARE
	int nextmp;
#endif
#ifdef USE_BTREE
	iproute_ent_pt bfwd;
	int get_bfwd = 1;
#endif
	iproute_ent_pt fwd;
	rripa tmp;
	int tm = tos_map[tos];
	TOSFWD *tp;


	/* Routes are stored in the following manner:
	   - if the subnet mask is at least as long as
	     the mask for the corresponding address class,
	     use a hash key of the address anded with 
	     the  class mask.
	   - if the subnet mask is shorter, use a hash
	     key of 0.

	=> This means we only need to look in two hash
	   bins to find a possible route: a non-zero bin
	   and a zero bin. Further, since we store with
	   longest mask first in each bin, the first
	   route we find is the best one.

	if USE_BTREE is DEFINED, all entries with the same mask
	are stored in a balanced binary tree.
	*/

	/* 0 illegal */
	ipadd = XIPA(ap);
	if(!ipadd){
		*cid = INVALID_CIRC;
		return( (arpent_pt)0 );
	}

	/* find the non-zero bin */
	if( *ap <= IP_CLASS_A_MAX ){

		key = *ap;
	}
	else if( *ap <= IP_CLASS_B_MAX ){

		key = *ap ^ *(ap+1);
	}
	else{

		key = *ap ^ *(ap+1) ^ *(ap+2);
	}

	key &= (IP_ROUTE_HASHES-1);


	/* cycle through the non-zero bin looking for first match */
	for( rent= *(i_node->rn_rt_def+(2*key)); rent; rent = fwd){

#ifdef USE_BTREE
		if(get_bfwd){
			bfwd = rent->iprt_fwd;
			get_bfwd = 0;
		}
#endif
		/* see if this route matches */
		tmp = ipadd & rent->iprt_ipa.ip_mask;
		if((tmp == rent->iprt_ipa.ip_add) &&
		   !RT_UNREACHABLE(rent)){
	

			/* we have a matching rent, increment use
				count and return first adj */

			/* if local dest or direct net, return c=0 */
			if(!rent->t[0].iprt_fent[0]){

				*cid = rent->iprt_cid;
				return( (arpent_pt)0 );
			}
			if(rent->t[tm].iprt_cost == -1){
				/* use default tos */
				tp = &rent->t[0];
			}
			else{ /* use requested tos */ 
				tp = &rent->t[tm];
			}
#ifdef IP_LOAD_SHARE
			nextmp = tp->iprt_next_adj;
	
			*cid= tp->iprt_fent[nextmp]->ae_cid;
			rp= tp->iprt_fent[nextmp];

			if(tp->iprt_numadj > tp->iprt_next_adj +1){
				tp->iprt_next_adj ++;
			}
			else{
				tp->iprt_next_adj= 0;
			}
#else /* IP_LOAD_SHARE */

			*cid= tp->iprt_fent[0]->ae_cid;
			rp= tp->iprt_fent[0];

#endif /* IP_LOAD_SHARE */
			return(rp);
		}
		/* compute next to look at */
#ifdef USE_BTREE
		else if(tmp < rent->iprt_ipa.ip_add){
			if(rent->iprt_left)
				fwd = rent->iprt_left;
			else{
				fwd = bfwd;
				get_bfwd = 1;
			}
		}
		else{
			if(rent->iprt_right)
				fwd = rent->iprt_right;
			else{
				fwd = bfwd;
				get_bfwd = 1;
			}
		}
#else
		fwd = rent->iprt_fwd;
#endif /* USE BTREE */
		/* no match, next route */
	}

	/* cycle through the zero bin looking for first match */
	for( rent= *i_node->rn_rt_def; rent; rent = fwd){

#ifdef USE_BTREE
		if(get_bfwd){
			bfwd = rent->iprt_fwd;
			get_bfwd = 0;
		}
#endif

		/* see if this route matches */
		tmp = ipadd & rent->iprt_ipa.ip_mask;
		if((tmp == rent->iprt_ipa.ip_add) &&
		   !RT_UNREACHABLE(rent) ){


			/* we have a matching rent, increment use
				count and return first adj */

			/* if local dest or direct net, return c=0 */
			if(!rent->t[0].iprt_fent[0]){

				*cid = rent->iprt_cid;
				return( (arpent_pt)0 );
			}
			if(rent->t[tm].iprt_cost == -1){
				/* use default tos */
				tp = &rent->t[0];
			}
			else{ /* use requested tos */
				tp = &rent->t[tm];
			}
#ifdef IP_LOAD_SHARE
			nextmp = tp->iprt_next_adj;
			*cid= tp->iprt_fent[nextmp]->ae_cid;
			rp= tp->iprt_fent[nextmp];

			if(tp->iprt_numadj > tp->iprt_next_adj +1){
				tp->iprt_next_adj ++;
			}
			else{
				tp->iprt_next_adj= 0;
			}
#else /*  IP_LOAD_SHARE */

			*cid= tp->iprt_fent[0]->ae_cid;
			rp= tp->iprt_fent[0];

#endif /* IP_LOAD_SHARE */
			return(rp);
		}
		/* compute next to look at */
#ifdef USE_BTREE
		else if(tmp < rent->iprt_ipa.ip_add){
			if(rent->iprt_left)
				fwd = rent->iprt_left;
			else{
				fwd = bfwd;
				get_bfwd = 1;
			}
		}
		else{
			if(rent->iprt_right)
				fwd = rent->iprt_right;
			else{
				fwd = bfwd;
				get_bfwd = 1;
			}
		}
#else
		fwd = rent->iprt_fwd;
#endif /* USE BTREE */

		/* no match, next route */
	}
	
	*cid = INVALID_CIRC;
	return( (arpent_pt)0 );
}

#endif

/****************************************************
IpGetNextHop:

	Finds next hop subnet address and circuit to
	forward PDU to.

	returns:	Route found via router:
				snad and c filled in.
				Destination is direct net or us:
				c= dest circ, snad ptr = 0.
				Couldn't find route:
				c = INVALID_CIRC.


*****************************************************/
int  ipGetNextHop(	byte *ap,int *cid,rripa *nexthop, rripa *mask
					,unsigned long * costp)
{

	arpent_pt ae = IpGetNextHop(ap, cid, 0);
	
	if( !ae ) {
		if( *cid == INVALID_CIRC ) {
			return FNS_ENETUNREACH; /* dubious but for now */
		}
		/* Local route */
		*nexthop = 0;
		return FNS_ENOERR;
	}
	/* There is a next hop */
	*nexthop = ae->ae_ipa;
	*cid = ae->ae_cid;
	return FNS_ENOERR;
}



/****************************************************
IpGetRouteEntry:

	Finds next Route entry and circuit to
	forward PDU to. 

	returns:	Route entry :
			Couldn't find route:
			 c = INVALID_CIRC.
			

*****************************************************/
int  ipGetRouteEntry(byte *ap, iproute_ent_pt *retPtr)
{
	rripa ipadd;
	byte key;
	iproute_ent_pt rent;
#ifdef USE_BTREE
	iproute_ent_pt bfwd = 0;
#endif
	iproute_ent_pt fwd;
	rripa tmp;

	/* Routes are stored in the following manner:
	   - if the subnet mask is at least as long as
	     the mask for the corresponding address class,
	     use a hash key of the address anded with 
	     the  class mask.
	   - if the subnet mask is shorter, use a hash
	     key of 0.

	=> This means we only need to look in two hash
	   bins to find a possible route: a non-zero bin
	   and a zero bin. Further, since we store with
	   longest mask first in each bin, the first
	   route we find is the best one.

	if USE_BTREE is true, all entries with the same mask
	are stored in a balanced binary tree.
	*/

	/* 0 illegal */
	ipadd = XIPA(ap);
	if(!ipadd){
		return( -1 );
	}

	/* find the non-zero bin */
	if( *ap <= IP_CLASS_A_MAX ){

		key = *ap;
	}
	else if( *ap <= IP_CLASS_B_MAX ){

		key = *ap ^ *(ap+1);
	}
	else{

		key = *ap ^ *(ap+1) ^ *(ap+2);
	}

	key &= (IP_ROUTE_HASHES-1);


	/* cycle through the non-zero bin looking for first match */
	for( rent= *(i_node->rn_rt_def+(2*key)); rent; rent = fwd){

#ifdef USE_BTREE
		if(!bfwd) bfwd = rent->iprt_fwd;
#endif
		/* see if this route matches */
		tmp = ipadd & rent->iprt_ipa.ip_mask;
		if(tmp == rent->iprt_ipa.ip_add){
			*retPtr = rent;
			return(0);
		}
		/* compute next to look at */
#ifdef USE_BTREE
		else if(tmp < rent->iprt_ipa.ip_add){
			if(rent->iprt_left)
				fwd = rent->iprt_left;
			else{
				fwd = bfwd;
				bfwd = 0;
			}
		}
		else{
			if(rent->iprt_right)
				fwd = rent->iprt_right;
			else{
				fwd = bfwd;
				bfwd = 0;
			}
		}
#else
		fwd = rent->iprt_fwd;
#endif /* USE BTREE */
		/* no match, next route */
	}

	/* cycle through the zero bin looking for first match */
	for( rent= *i_node->rn_rt_def; rent; rent = fwd){

#ifdef USE_BTREE
		if(!bfwd) bfwd = rent->iprt_fwd;
#endif

		/* see if this route matches */
		tmp = ipadd & rent->iprt_ipa.ip_mask;
		if(tmp == rent->iprt_ipa.ip_add){
			*retPtr  = rent;
			return(0);
		}
		/* compute next to look at */
#ifdef USE_BTREE
		else if(tmp < rent->iprt_ipa.ip_add){
			if(rent->iprt_left)
				fwd = rent->iprt_left;
			else{
				fwd = bfwd;
				bfwd = 0;
			}
		}
		else{
			if(rent->iprt_right)
				fwd = rent->iprt_right;
			else{
				fwd = bfwd;
				bfwd = 0;
			}
		}
#else
		fwd = rent->iprt_fwd;
#endif /* USE BTREE */

		/* no match, next route */
	}
	
	return( -1 );
}