rripfdb.c

来自「用于嵌入式系统的TCP/IP协议栈及若干服务」· C语言 代码 · 共 2,850 行 · 第 1/5 页

/*
*            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: 2002/01/22 14:09:57 $
*  $Source: M:/psisrc/routing/rrfdb/rcs/rripfdb.c $
*  $Revision: 1.33 $
*************************************************************************
***************************************************************************
*  File Description: IP forwarding database. 

Overall architecture used:

1 hash table for all routing tables of a given metric.
The contents of hash table are pointers to a routing
entry (iproute_entry). 

***********************************************/
#include "riproute.h"
#include "ipport.h"
#include "ipaccess.h"
#include "icirc.h"
#include "rrfwd.h"
#ifdef OSPF_PROTOCOL
#include "fnsospf.h"
#endif
#include "fns_str.h"

#define IPRT_CONTAIN(d1,m1,d2,m2) ((m1>m2)?0:(d1==(d2&m1))?1:0)
fnc_prot(int, ipRedistCheck,(iproute_ent_pt,REDIST_TMPL *,IPRT_REDIST *,int))
fnc_prot(void, bgpAddExtRt,(ipna_pt,IPRT_REDIST *))
fnc_prot(void, bgpModExtRt,(ipna_pt))
fnc_prot(void, bgpDelExtRt,(ipna_pt))
fnc_prot(void, bgpRouteModified,(ipna_pt,int))
fnc_prot(void, ospfAddExtRt,(ipna_pt,rripa,int,int,int,int,rripa))
fnc_prot(void, ospfDelExtRt,(ipna_pt,int,int,int))
fnc_prot(void, IrIpAddExtRt,(ipna_pt,int,int,int,int,int))
fnc_prot(void, IrIpDelExtRt,(ipna_pt,int,int,int,int))
fnc_prot(static iproute_ent_pt, ipFindBestRt,(rripa))
fnc_prot(void, ipRtArpDeref,(iproute_ent_pt))
fnc_prot(iproute_ent_pt, ipFindRoute,(ipna_pt,int))
fnc_prot(icirc_pt,ipCircFromId,(int))
fnc_prot(iproute_ent_pt, ipAddRoute, (ipna_pt,rripa,int,int,int,rripa))
fnc_prot(void, ipDelRoute,(iproute_ent_pt iprt))
fnc_prot(void, ipStaticRtOn,(int))
fnc_prot(void, ipStaticRtOff,(int))
fnc_prot(iproute_ent_pt, ipAddRouteM, (ipna_pt,int,rripa *,int *,int,int,rripa,int))
fnc_prot(void, ipReplaceRouteM,(iproute_ent_pt,int,rripa *,int *,int,rripa,int,int))
fnc_prot(static iproute_ent_pt, ipFindRt, (ipna_pt))\
fnc_prot(int , ip_rtKey, (ipna_pt))
fnc_prot(arpent_pt, IpGetNextHop, (byte *,int *, int ))
fnc_prot(icirc_pt, ipGetMatchAddr, (icirc_pt c, rripa next))

INODE *i_node = (INODE *)0;
int addrsIndex = 0;
int totalAddrs = 0;
rripa rteTbl_Addrs[2*IP_ROUTE_HASHES];	/* filled in when a route is
											inserted into the table.
											used by SNMP
										 */

/**************************************************
IrIpRtInit:

Initialize IP routing tables.
**************************************************/
void IrIpRtInit()
{
	int i,max;
	iproute_ent_pt rblk,srt;
 
    /* hashing tables */

	/* alloc main node */
	if( (i_node = (inode_pt)RR_MALLOC(sizeof(INODE))) == 0){
		ASSERT(0,"ip: cant alloc main node");
		return;
	}
	rrFillMem((char *)i_node,0,sizeof(INODE));


#ifdef IP_USE_PTREE
	/* mask lens we have routes for */
	for(i = 0; i < 33;i++){
		i_node->rn_rtmasks[i] = -1;
		i_node->rn_rtl2m[i] = ipRtLen2Mask(i);
	}
#else
	/* hashing tables */
	if( (i_node->rn_rt_def= (iproute_ent_pt *)
	  ipRouteAlloc(2*sizeof(iproute_ent_pt)*IP_ROUTE_HASHES))== 0){
		ASSERT(0,"IPINIT");
	}
	rrFillMem(i_node->rn_rt_def,0,2*sizeof(iproute_ent_pt)*IP_ROUTE_HASHES);
#endif

	/* only alloc structs for other metrics if we will
	   use them */

	/* blocks of path entry structs,
	   to allow decision to run
	   without stopping forwarding */


	/* may alloc smaller table size for non-default */
	max = IP_DEF_ROUTE_BSZ;

	if((rblk= (iproute_ent_pt)
  		ipRouteAlloc(sizeof(iproute_ent)* max))== 0){
		ASSERT(0,"IPINIT");
	}
	/* link each struct in free list */
	for(i = 0, srt = rblk ;i < max; srt++, i++){

		rrLink((dll_pt)srt,(dll_pt)&i_node->rn_rtfwd_def);
	}
	i_node->rn_def_blks = 1;

	/*  For SNMP code. */
	addrsIndex = 0;
	totalAddrs = 0;
	rrFillMem(rteTbl_Addrs,0,2*IP_ROUTE_HASHES*sizeof(rripa));





}

#ifndef IP_USE_PTREE
/*****************************************************

table structure:

table is organized as a dual linked list where each
link is a pointer to the first member of a balanced
binary tree. links are iprt_fwd and iprt_bwd. Each
tree consists of routes with the same ip mask. Longest mask
trees are linked ahead of those with shorter masks.
trees are linked using iprt_left, iprt_right and iprt_bwd.
When a search comes to the end of a tree, (left/right = 0),
it continues with the iprt_fwd member stored when entering
the tree. If all entries have different masks,
or USE_BTREE is false, this degenerates to a normal
linked list. 
******************************************************/
fnc_prot(static iproute_ent *,findNode,(rripa,iproute_ent *))
fnc_prot(static int,getTreeHeight,(iproute_ent *))
fnc_prot(static int,ip_btinsert,(iproute_ent *,iproute_ent *,iproute_ent **,int))
fnc_prot(static void,ip_btdelete,(iproute_ent *,iproute_ent *,iproute_ent **,int))

/******************************************
route insertion/deletion:
use radix or binary tree function.
returns 0 success, -1 failure
******************************************/
int ip_rtinsert(iproute_ent *iprt)
{
	ipna_pt ipna = &iprt->iprt_ipa;
	iproute_ent_pt tmp,*tbl;
	int bin,rc;
    use_critical;

	/* Put address in SNMP table of addresses in routing table. */
	if (addrsIndex != (2*IP_ROUTE_HASHES-1))
	{
		rteTbl_Addrs[addrsIndex++] = ipna->ip_add;
		totalAddrs++;
	}
	else
		addrsIndex = 0;


	/* link it according to length of mask */
	/* link according to subnet mask len, longest first */
	/* anything with the same mask goes into a balanced
	   binary tree.
	*/

	/* note: this is going into an active routing table, so
	   we need to be careful and guarantee atomic pointer
	   write
	*/

	bin = ip_rtKey(ipna);
	tbl = i_node->rn_rt_def;
	tmp= tbl[2*bin];
	if(!tmp){
		/* first in chain */
		iprt->iprt_fwd = 0;
		iprt->iprt_bwd = 0;
		critical;
		tbl[2*bin] = iprt;
		tbl[2*bin +1] = iprt;
		normal;
#ifdef USE_BTREE
		iprt->iprt_left = iprt->iprt_right = 0;
		iprt->iprt_bal = 0;
#endif
		return(0);
	}

	/* find same mask or shorter */
	else for(; tmp; tmp = tmp->iprt_fwd){
	
		if(iprt->iprt_ipa.ip_mask > 
			tmp->iprt_ipa.ip_mask){

			/* new has longer mask than tmp, insert
			   in front of tmp.
			*/
			iprt->iprt_fwd = tmp;
			iprt->iprt_bwd = tmp->iprt_bwd;
			if(iprt->iprt_bwd){
				critical;
				iprt->iprt_bwd->iprt_fwd = iprt;
				tmp->iprt_bwd = iprt;
				normal;
			}
			else{
				critical;
				tbl[2*bin] = iprt;
				tmp->iprt_bwd = iprt;
				normal;
			}
#ifdef USE_BTREE
			iprt->iprt_left = iprt->iprt_right = 0;
			iprt->iprt_bal = 0;
#endif
			return(0);
		}
		else if(iprt->iprt_ipa.ip_mask == 
			tmp->iprt_ipa.ip_mask){
			/* it has same mask, insert in tree */
#ifdef USE_BTREE
			critical;
			rc = ip_btinsert(iprt,tmp,tbl,bin);
			normal;
#else
			iprt->iprt_fwd = tmp;
			iprt->iprt_bwd = tmp->iprt_bwd;
			if(iprt->iprt_bwd){
				critical;
				iprt->iprt_bwd->iprt_fwd = iprt;
				tmp->iprt_bwd = iprt;
				normal;
			}
			else{
				critical;
				tbl[2*bin] = iprt;
				tmp->iprt_bwd = iprt;
				normal;
			}
			rc = 0;
#endif
			return(rc);
		}
	}
	/* got to end of list, new has shortest mask */
	iprt->iprt_fwd = 0;
	iprt->iprt_bwd = tbl[2*bin+1];
#ifdef USE_BTREE
	iprt->iprt_left = iprt->iprt_right = 0;
	iprt->iprt_bal = 0;
#endif
	critical;
	iprt->iprt_bwd->iprt_fwd = iprt;
	tbl[2*bin+1] = iprt;
	normal;
	return(0);
}

int ip_rtdelete(iproute_ent *iprt)
{
	iproute_ent *tmp;
	iproute_ent_pt *tbl;
	int bin, i;
    use_critical;

	bin = ip_rtKey(&iprt->iprt_ipa);
	tbl = i_node->rn_rt_def;

	/* Remove from SNMP table of routes. */
	for (i=0; i<2*IP_ROUTE_HASHES; i++)
	{
		if (rteTbl_Addrs[i] == iprt->iprt_ipa.ip_add)
		{
			rteTbl_Addrs[i] = (u32)0;
			totalAddrs--;
			break;
		}
	}

#ifdef USE_BTREE
	/* find out if we are in a tree, or standalone
	   link element */
	if( iprt->iprt_left || iprt->iprt_right ||
		/* could be a tree leaf node */
	   (iprt->iprt_bwd &&
	    iprt->iprt_bwd->iprt_ipa.ip_mask == iprt->iprt_ipa.ip_mask)){

		/* in tree, find tree head */
		for(tmp = iprt; tmp; tmp = tmp->iprt_bwd){
			if(!tmp->iprt_bwd ||
			   tmp->iprt_bwd->iprt_ipa.ip_mask !=
			   iprt->iprt_ipa.ip_mask ){

				critical;
				ip_btdelete(iprt,tmp,tbl,bin);
				normal;
				return(0);
			}
		}
		ASSERT(0,"ip_rtdelete");
	}
#endif /* USE_BTREE */
	/* standalone, just unlink */
	critical;
	if(iprt->iprt_fwd){
		iprt->iprt_fwd->iprt_bwd = iprt->iprt_bwd;
	}
	else{
		tbl[2*bin+1] = iprt->iprt_bwd;
	}		
	if(iprt->iprt_bwd){
		iprt->iprt_bwd->iprt_fwd = iprt->iprt_fwd;
	}
	else{
		tbl[2*bin] = iprt->iprt_fwd;
	}		
	normal;
	return(0);
}

#ifdef USE_BTREE


/* look at the back link from XN1 and set its left or
   right fwd link to XN2
*/
#define ADJ_BLINK(XN1,XN2) {\
if(XN1->iprt_bwd->iprt_left == XN1)            \
	XN1->iprt_bwd->iprt_left = XN2;           \
else                                           \
	XN1->iprt_bwd->iprt_right = XN2;          \
}

/******************************************
find route with next highest val, given 
head and current route
********************************************/
iproute_ent  *ip_btnext(iproute_ent *nd,iproute_ent *prev)
{

	/* if there is right link, follow it then all left
	   links.
	*/
	if(nd->iprt_right){
		nd = nd->iprt_right;
		for(;nd;nd = nd->iprt_left){
			if(!nd->iprt_left)
				return(nd);
		}
	}
	/* go up tree till we find a link that is left
	   (ie. up is greater)
	*/
	while(1){
		if(nd->iprt_bwd == prev) return(0);
		if(nd->iprt_bwd->iprt_left == nd)
			return(nd->iprt_bwd);
		nd = nd->iprt_bwd;
	}

}
/******************************************
find route with next highest val, given
head and current route
********************************************/
iproute_ent  *ip_btfirst(iproute_ent *nd)
{
	/* find first */
	/* follow left links */
	for(; ; nd = nd->iprt_left){
		if(!nd->iprt_left)
			break;
	}
	return(nd);
}
int ip_rtver()
{

	iproute_ent *nd,**tbl,*head,*tail;
	int i,bl,br;
	int errnox;
	int saw_tail = 0;

	tbl = i_node->rn_rt_def;
	/* process each path entry */
	for(i= 0; i< IP_ROUTE_HASHES; i++){

		head = *(tbl +(2*i));
		if(head && head->iprt_bwd){
			errnox = 20;
			goto puke;
		}
		tail = *(tbl +(2*i)+1);
		if(tail && tail->iprt_fwd){
			errnox = 21;
			goto puke;
		}
		RT_BINWALK(nd,*(tbl+(2*i)))

		if(nd == tail)saw_tail = 1;
		/* ver fwd/back links */
		if(nd->iprt_left && nd->iprt_left->iprt_bwd != nd){
			errnox = 1;
			goto puke;
		}
		if(nd->iprt_right && nd->iprt_right->iprt_bwd != nd){
			errnox = 2;
			goto puke;
		}
		/* check links, differ if head, vs tree internal */
		if(nd->iprt_bwd && nd->iprt_bwd->iprt_ipa.ip_mask ==
		    nd->iprt_ipa.ip_mask){
			if(nd->iprt_bwd->iprt_left != nd &&
			   nd->iprt_bwd->iprt_right != nd){
				errnox = 3;
				goto puke;
			}
		}
		else{
		  if(nd->iprt_fwd && nd->iprt_fwd->iprt_bwd != nd){
			errnox = 4;
			goto puke;
		  }
		  if(nd->iprt_bwd && nd->iprt_bwd->iprt_fwd != nd){
			errnox = 5;
			goto puke;
		  }
		}

		/* ver add.ip_addues */
		if(nd->iprt_left && nd->iprt_left->iprt_ipa.ip_add >= nd->iprt_ipa.ip_add){
			errnox = 6;
			goto puke;
		}
		if(nd->iprt_right && nd->iprt_right->iprt_ipa.ip_add <= nd->iprt_ipa.ip_add){
			errnox = 7;
			goto puke;
		}

		/* ver balance */
		bl = getTreeHeight(nd->iprt_left);
		br = getTreeHeight(nd->iprt_right);
		if(bl -br >1 || br-bl > 1){
			errnox = 8;
			goto puke;
		}

		if(br -bl != nd->iprt_bal){
			errnox = 9;
			goto puke;
		}

		/* sanity (dont chk fwd)*/
		if(nd->iprt_left == nd ||
	 	   nd->iprt_right == nd ||
		   nd->iprt_bwd == nd){
			errnox = 10;
			goto puke;
		}
		RT_BINWALKEND
		if(tail && !saw_tail){
			errnox = 22;
			goto puke;
		}
	}
	return(0);
puke:
	return(errnox);
}

/******************************************
Given a route, return the next route.  Given a
null route returns the head of the table.
********************************************/

rripa* ip_getRteTableAddrs(int* count)
{
	int i;
	rripa* rteAddrs;

	*count = 0;
	rteAddrs = (rripa*)h_alloc(totalAddrs * sizeof(rripa), &i, 1);
	if (i)
		return(NULL);

	for (i=0; i < 2*IP_ROUTE_HASHES && *count < totalAddrs; i++)
	{
		if (rteTbl_Addrs[i])
			rteAddrs[(*count)++] = rteTbl_Addrs[i];
	}
	return(rteAddrs);
	
}  /* end ip_getRteTableAddrs */


static iproute_ent *findNode(rripa add,iproute_ent *head)
{
	iproute_ent *nd = head;
	while(nd){
		if(nd->iprt_ipa.ip_add == add) return(nd);
		else if(add > nd->iprt_ipa.ip_add) nd = nd->iprt_right;
		else nd = nd->iprt_left;
	}
	return((iproute_ent *)0);
}

static int getTreeHeight(iproute_ent *nd)
{
	int cnt = 0;
	while(nd){
		cnt++;
		if(nd->iprt_bal < 0)
			nd = nd->iprt_left;
		else
			nd = nd->iprt_right;
	}
	return(cnt);
}
static int ip_btinsert(iproute_ent *node,iproute_ent *head,iproute_ent **tbl,int bin)
{
	rripa add = node->iprt_ipa.ip_add;
	iproute_ent *tmp,*adjnd,*r;
	int  a;

	if(findNode(add,head))
		 return(-1);

	node->iprt_left = 0;
	node->iprt_right = 0;
	node->iprt_bwd = 0;
	node->iprt_fwd = 0;
	node->iprt_bal = 0;
	node->iprt_ipa.ip_add = add;

	/* find a home, will add at end of a chain */
	tmp = head;
	adjnd = head;