iprt.h

用于嵌入式系统的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: 2002/01/22 14:11:04 $
*  $Source: M:/psisrc/routing/incl/rcs/iprt.h $
*  $Revision: 1.10 $
*************************************************************************
*  File Description: Definitions for IP forwarding database
*************************************************************************
route resource locking:

routing table can be accessed by multiple threads
if bgp, ospf etc are run as separate tasks/threads.
If enviroment is non-preemptive, this is not a problem.
But if it is, some table locking is required. We use
os_critical/normal to control this. The assumptions
are:
- only the owner of a route can modify or delete it.
- non-owners only have access to route via utilities
  in ipfdb.c. Pointers are never returned, so non-ipfdb.c
  code is not responsible for locking.
- owners can modify a route outside ipfdb.c (and therefore
  in unlocked state), but only members that are private
  to the owner.
*************************************************************************/

/*****************************************************
#ifdef IP_USE_PTREE
routes are stored in patricia tree (also called radix 
tree) format.
under this format, define an index for node n as the 
sum of the iprt_skip values of all routes traversed to get to node n.  (including the iprt_skip value of n itself).

each entry has the following characteristic:

- all children of node n contain the same leading
  index -1 bits of iprt_addr as node n.


note that patricia trees work only if the no key 
(iprt_addr in this case) is a leading substring of 
another key. To meet this requirement, we pad all 
addresses with 0 and consider all keys to be 32 bits 
long. if two entries end up with the same key under 
this approach, they are stored by linking using 
iprt_dup.  therefore, as far as the basic tree 
algorithms are concerned, there are no duplicates.

routes in tree have no relationship to mask lengths. 
if there are no routes that are supersets of another 
route, there is no problem. to handle the case where 
one route is superset of another, we need to mask off 
some bits and search again. to keep from trying all 
possible masks, we keep an array of active mask lens.
*********************************************/
/* stored ARP entries */
typedef struct arp_entry{

	struct arp_entry	*ae_fwd;		/* links */
	struct arp_entry	*ae_bwd;
	rripa				ae_ipa;		    /* ip address */
	SNAD				ae_snad;		/* subnet address */
	int					ae_cid;		    /* circuit */
	dword				ae_actstamp;		/*activity timestamp */
	int					ae_type;		/* entry type */
	int					ae_rtref;		/* route refcnt */
}ARPENT, *arpent_pt;

/* entry types */
#define ARP_SRC		0x0f
#define ARP_STAT		1
#define ARP_DYN		    2
#define ARP_LOC		    4
#define ARP_UNKNOWN		0
#define ARP_ATTRIB		0xf0
#define ARP_BCAST		0x10
#define ARP_PTPT		0x20
#define ARPRQ_NON802	0x80
#define ARP_TIC         10


/* one per supported TOS */
typedef struct tos_fwd{
	int						iprt_cost;
                   /* possbile nexthop ip/arp */
	struct arp_entry 	   *iprt_fent[MAX_IP_MSPLIT];
#ifdef IP_LOAD_SHARE
	byte					iprt_next_adj;
	byte					iprt_numadj;
#endif /* IP_LOAD_SHARE */
}TOSFWD;

#ifdef ALL_IP_METRICS
/* in order: default, monetary,reliability, tput, delay */
#define NUM_TOSFWD	5
#else
#define NUM_TOSFWD	1
#endif

typedef struct iproute_entry{
#ifdef IP_USE_PTREE
	struct iproute_entry *iprt_bwd;
	struct iproute_entry *iprt_llink;
	struct iproute_entry *iprt_rlink;
	struct iproute_entry *iprt_dup;
	byte                  iprt_skip;	/* bits to skip */
	byte                  iprt_ltag;
	byte                  iprt_rtag;
#else
	struct iproute_entry 	*iprt_fwd;		/* links */
	struct iproute_entry 	*iprt_bwd;		/* links */
#ifdef USE_BTREE
	struct iproute_entry	*iprt_left;
	struct iproute_entry	*iprt_right;
	signed char				iprt_bal;
#endif /* USE_BTREE */
#endif /* !IP_USE_PTREE */

	/* all following independent of tree type */

	struct iproute_entry	*iprt_other;	 /* other owners */
	struct ipnetaddr		iprt_ipa;		 /* dest */
	int						iprt_cost2;
	int						iprt_mtype;		/* int/ext */
	int						iprt_level;		/* L1 or L2 */
	void					*iprt_prptr;	/* mospf/bgp */
	int						iprt_trig;
	int						iprt_owner;		/* protocol src */
	struct routing_timer	*iprt_ttl;		/* time-out */
    dword                   iprt_tcreate;   /* System time in msecs since bootup
                                               when route was created.
                                            */
	rripa					iprt_tag;		/* learned tag */
	int						iprt_cid;       /* direct only */
	union{
	rripa					u_area;  /* ospf src area */
	rripa					u_src;   /* rip src rtr */
	}u;
	TOSFWD				t[NUM_TOSFWD];	  /* fwd per tos */

}iproute_ent, *iproute_ent_pt;

/* rip trigger flags */
#define IPRT_RIP_CHANGED		1

/* best route to dest*/
#define IPRT_IS_BEST		2

/* rip import external */
#define IPRT_RIP_IMPORT		4

/*************************************
TABLE WALK MACROS:

definitions depend on whether routing
table is stored as hash/btrees or as
patricia(radix) tree.
*************************************/
#ifdef IP_USE_PTREE

#define RT_TABLEWALK           		               \
{                                                      \
iproute_ent *xxxrt;                                    \
for(iprt = ip_ptfirst();iprt; iprt = xxxrt){           \
    xxxrt = ip_ptnext(iprt);                     

#define RT_TABLEWALKEND	}}            \


#define RT_TABLEWALK_BY_OWNER(xo) 	     \
{                                                      \
iproute_ent *yrt,*yyrt,*xxxrt;                         \
for(yrt = ip_ptfirst();yrt; yrt = xxxrt){           \
	xxxrt = ip_ptnext(yrt);                            \
    /* look for route onwed by xo */                   \
    for(iprt = yrt; iprt; iprt = yyrt){                \
      yyrt = iprt->iprt_other;                          \
      if(iprt->iprt_owner == xo) break;                 \
    }                                                  \
    if(!iprt)continue;  /* no such owner this route */  \

#else /* IP_USE_PTREE */
/**************************************
what started out as a linked list walk now
must be supplemented to include the fact that
each node in the linked list could be a
binary tree. for cases that need to look at
every element in the list, we need to traverse
the tree as well as the list.

tree traverse is as follows:
- is !left && !right, its not a tree go to next link
- else its a tree traverse as follows
- find first element by following left links
- until done, if there is right link follow it then all
  the way left
  else go up one,repeat

NOTE: this also works if a route is deleted in the
loop.
***************************************/
#ifdef USE_BTREE
#define RT_BINWALK(xrt,xbinstart) 		               \
{                                                      \
iproute_ent *xxrt,*xxxrt,*xxxxrt,*xxxyrt;              \
for(xxrt = (xbinstart); xxrt; xxrt = xxxxrt){          \
  xxxxrt = xxrt->iprt_fwd;                             \
  xxxyrt = xxrt->iprt_bwd;                             \
  for(xrt = ip_btfirst(xxrt);xrt; xrt = xxxrt){        \
    xxxrt = ip_btnext(xrt,xxxyrt);                     \

#else
#define RT_BINWALK(xrt,xbinstart) 		               \
{                                                              \
iproute_ent *xxrt;                                             \
for(xrt = (xbinstart); xrt; xrt = xxrt){                       \
  xxrt = xrt->iprt_fwd;                                        \

#endif

#ifdef USE_BTREE
#define RT_BINWALKEND 	}}}
#else
#define RT_BINWALKEND 	}}
#endif

/* table walk macros to allow third party to use
   rip with non-phase2 routing tables */

#define RT_TABLEWALK							\
{											\
int xxbin;									\
for(xxbin= 0; xxbin < IP_ROUTE_HASHES; xxbin++){		\
	/* go through existing  routes in this bin  */	\
	RT_BINWALK(iprt,*(i_node->rn_rt_def +(2*xxbin)))

#define RT_TABLEWALKEND	RT_BINWALKEND }}            \



/***************************************************
each route in the tree can have non-best routes
attached to it (using iprt_other). for example,
if an ospf route is the best route to dest X, there
may also be a static route linked to the ospf root
so that the static route will get used if the ospf
route goes away. this macros traverses the table,
locating only those routes owned by xo.
***************************************************/
#ifdef USE_BTREE
#define RT_BINWALK_BY_OWNER(xrt,xbinstart,xo) 	     \
{                                                      \
iproute_ent *xxrt,*xxxrt,*xxxxrt,*xxxyrt;              \
iproute_ent *yrt,*yyrt;                                \
for(xxrt = (xbinstart); xxrt; xxrt = xxxxrt){          \
  xxxxrt = xxrt->iprt_fwd;                             \
  xxxyrt = xxrt->iprt_bwd;                             \
  for(yrt = ip_btfirst(xxrt);yrt; yrt = xxxrt){        \
    xxxrt = ip_btnext(yrt,xxxyrt);                     \
    /* look for route onwed by xo */                   \
    for(xrt = yrt; xrt; xrt = yyrt){                   \
      yyrt = xrt->iprt_other;                          \
      if(xrt->iprt_owner == xo) break;                 \
    }                                                  \
    if(!xrt)continue;  /* no such owner this route */  \

#else
#define RT_BINWALK_BY_OWNER(xrt,xbinstart,xo) 		\
{                                                      \
iproute_ent *yyrt,*yrt,*xxrt;                          \
for(yrt = (xbinstart); yrt; yrt = yyrt){               \
  yyrt = yrt->iprt_fwd;                                \
  /* look for route onwed by xo */                     \
  for(xrt = yrt; xrt; xrt = xxrt){                     \
    xxrt = xrt->iprt_other;                            \
    if(xrt->iprt_owner == xo) break;                   \
  }                                                    \
  if(!xrt)continue;  /* no such owner this route */    \

#endif

#define RT_TABLEWALK_BY_OWNER(xo) 					\
{											\
int xxbin;									\
for(xxbin= 0; xxbin < IP_ROUTE_HASHES; xxbin++){		\
	/* go through existing  routes in this bin  */	\
	RT_BINWALK_BY_OWNER(iprt,*(i_node->rn_rt_def +(2*xxbin)),xo)


#endif /* !IP_USE_PTREE */

/* route access macros for situations where an external
   FDB is used */
#define RT_OWNER(iprt) iprt->iprt_owner
#define RT_IS_BCAST(iprt) (!iprt->iprt_cid)
#define RT_IS_TRIG(iprt,val)  (iprt->iprt_trig & val)
#define RT_TRIG_SET(iprt,val)  iprt->iprt_trig |= val
#define RT_TRIG_CLR(iprt,val)  iprt->iprt_trig &= ~val
#define RT_DEST(iprt)	iprt->iprt_ipa.ip_add
#define RT_MASK(iprt)	iprt->iprt_ipa.ip_mask
#define RT_TOS0_NHCID(iprt) (iprt->t[0].iprt_fent[0] ? iprt->t[0].iprt_fent[0]->ae_cid : 0)
#define RT_TOS0_NHIPA(iprt) (iprt->t[0].iprt_fent[0]? iprt->t[0].iprt_fent[0]->ae_ipa : 0 )
#define RT_TAG(iprt)	iprt->iprt_tag
#define RT_TOS0_COST(iprt)  iprt->t[0].iprt_cost
#define RT_IS_INTERNAL(iprt) (iprt->iprt_mtype == IPRT_INT)
#define RT_COST2(iprt)	iprt->iprt_cost2
#define RT_TTL(iprt)	iprt->iprt_ttl
#define RT_TTL_SET(iprt,timer)  iprt->iprt_ttl = timer
#define RT_PRPTR(iprt)	iprt->iprt_prptr
#define RT_PRPTR_SET(iprt,val)  iprt->iprt_prptr = (void *)val 
#define RT_UNREACHABLE(iprt)	(iprt->iprt_cid == INVALID_CIRC)
#define RT_DIRECT_CID(iprt)	iprt->iprt_cid
#define RT_LEVEL(iprt)		iprt->iprt_level
#define RT_GARBAGE_ALLOC()	ip_rtAlloc()
#define RT_GARBAGE_FREE(iprt)	ip_rtFree(iprt)
#define RT_IS_BEST(iprt)      (iprt->iprt_trig & IPRT_IS_BEST)
#define iprt_area u.u_area
#define iprt_src  u.u_src
#define RT_SRC(iprt)  		iprt->iprt_src
#define RT_SRC_SET(iprt,xsrc)  (iprt->iprt_src = xsrc)

#define IPV4ADDR_BITS 32

/* gets value of bit position zbit in ip address */
#define IPV4BIT(zaddr,zbit,zres) {\
        byte ztmp; \
        ztmp = *((byte *)(&zaddr) +((zbit) >> 3)); \
        zres = ztmp & (0x80 >> ((zbit) & 7)); \
}

/* true if "hole" in mask; true because x&-x always has 
   exactly one bit set, which should be equal -x */
#define IP_MASK_HOLE(ipadd) ((ipadd&(~ipadd+1)) != (~ipadd+1))

/* 
static routes that point to a disabled circuit
are stored in these structures held in i_node.
when a circuit comes up, they are removed and
put in the real routing table. when a circuit 
goes down, they are moved back here
*/
typedef struct ip_temp_static{
	struct dll		s_dll;
	rripa				s_ipaddr;
	rripa				s_ipmask;
	rripa			     s_next;
	int                 s_cid;
	int                 s_cost;
	int                 s_owner;
	iproute_ent_pt		s_rt;
}IP_TMPSTAT;