xref: /titanic_41/usr/src/uts/common/inet/ipf/radix_ipf.h (revision c793af95640863cd29868fc7c419c5d2496b207b)
1 /*
2  * Copyright (c) 1988, 1989, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  *	@(#)radix.h	8.2 (Berkeley) 10/31/94
27  */
28 
29 #ifndef RADIX_IPF_H
30 #define RADIX_IPF_H
31 
32 #pragma ident	"%Z%%M%	%I%	%E% SMI"
33 
34 #if SOLARIS2 > 10
35 #include <net/radix.h>
36 #else
37 #if !defined(_NET_RADIX_H_) && !defined(_RADIX_H_)
38 #define	_NET_RADIX_H_
39 #ifndef _RADIX_H_
40 #define	_RADIX_H_
41 #endif /* _RADIX_H_ */
42 
43 #ifndef __P
44 # ifdef __STDC__
45 #  define	__P(x)  x
46 # else
47 #  define	__P(x)  ()
48 # endif
49 #endif
50 
51 #if defined(__sgi)
52 # define	radix_mask	ipf_radix_mask
53 # define	radix_node	ipf_radix_node
54 # define	radix_node_head	ipf_radix_node_head
55 #endif
56 
57 /*
58  * Radix search tree node layout.
59  */
60 
61 struct radix_node {
62 	struct	radix_mask *rn_mklist;	/* list of masks contained in subtree */
63 	struct	radix_node *rn_p;	/* parent */
64 	short	rn_b;			/* bit offset; -1-index(netmask) */
65 	char	rn_bmask;		/* node: mask for bit test*/
66 	u_char	rn_flags;		/* enumerated next */
67 #define RNF_NORMAL	1		/* leaf contains normal route */
68 #define RNF_ROOT	2		/* leaf is root leaf for tree */
69 #define RNF_ACTIVE	4		/* This node is alive (for rtfree) */
70 	union {
71 		struct {			/* leaf only data: */
72 			caddr_t rn_Key;		/* object of search */
73 			caddr_t rn_Mask;	/* netmask, if present */
74 			struct	radix_node *rn_Dupedkey;
75 		} rn_leaf;
76 		struct {			/* node only data: */
77 			int	rn_Off;		/* where to start compare */
78 			struct	radix_node *rn_L;/* progeny */
79 			struct	radix_node *rn_R;/* progeny */
80 		} rn_node;
81 	} rn_u;
82 #ifdef RN_DEBUG
83 	int rn_info;
84 	struct radix_node *rn_twin;
85 	struct radix_node *rn_ybro;
86 #endif
87 };
88 
89 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
90 #define rn_key rn_u.rn_leaf.rn_Key
91 #define rn_mask rn_u.rn_leaf.rn_Mask
92 #define rn_off rn_u.rn_node.rn_Off
93 #define rn_l rn_u.rn_node.rn_L
94 #define rn_r rn_u.rn_node.rn_R
95 
96 /*
97  * Annotations to tree concerning potential routes applying to subtrees.
98  */
99 
100 struct radix_mask {
101 	short	rm_b;			/* bit offset; -1-index(netmask) */
102 	char	rm_unused;		/* cf. rn_bmask */
103 	u_char	rm_flags;		/* cf. rn_flags */
104 	struct	radix_mask *rm_mklist;	/* more masks to try */
105 	union	{
106 		caddr_t	rmu_mask;		/* the mask */
107 		struct	radix_node *rmu_leaf;	/* for normal routes */
108 	}	rm_rmu;
109 	int	rm_refs;		/* # of references to this struct */
110 };
111 
112 #define rm_mask rm_rmu.rmu_mask
113 #define rm_leaf rm_rmu.rmu_leaf		/* extra field would make 32 bytes */
114 
115 #define MKGet(m) {\
116 	if (rn_mkfreelist) {\
117 		m = rn_mkfreelist; \
118 		rn_mkfreelist = (m)->rm_mklist; \
119 	} else \
120 		R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
121 
122 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
123 
124 struct radix_node_head {
125 	struct	radix_node *rnh_treetop;
126 	struct	radix_node *rnh_leaflist;
127 	u_long	rnh_hits;
128 	u_int	rnh_number;
129 	u_int	rnh_ref;
130 	int	rnh_addrsize;		/* permit, but not require fixed keys */
131 	int	rnh_pktsize;		/* permit, but not require fixed keys */
132 	struct	radix_node *(*rnh_addaddr)	/* add based on sockaddr */
133 		__P((void *v, void *mask,
134 		     struct radix_node_head *head, struct radix_node nodes[]));
135 	struct	radix_node *(*rnh_addpkt)	/* add based on packet hdr */
136 		__P((void *v, void *mask,
137 		     struct radix_node_head *head, struct radix_node nodes[]));
138 	struct	radix_node *(*rnh_deladdr)	/* remove based on sockaddr */
139 		__P((void *v, void *mask, struct radix_node_head *head));
140 	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */
141 		__P((void *v, void *mask, struct radix_node_head *head));
142 	struct	radix_node *(*rnh_matchaddr)	/* locate based on sockaddr */
143 		__P((void *v, struct radix_node_head *head));
144 	struct	radix_node *(*rnh_lookup)	/* locate based on sockaddr */
145 		__P((void *v, void *mask, struct radix_node_head *head));
146 	struct	radix_node *(*rnh_matchpkt)	/* locate based on packet hdr */
147 		__P((void *v, struct radix_node_head *head));
148 	int	(*rnh_walktree)			/* traverse tree */
149 		__P((struct radix_node_head *,
150 		     int (*)(struct radix_node *, void *), void *));
151 	struct	radix_node rnh_nodes[3];	/* empty tree for common case */
152 };
153 
154 
155 #if defined(AIX)
156 # undef Bcmp
157 # undef Bzero
158 # undef R_Malloc
159 # undef Free
160 #endif
161 #define Bcmp(a, b, n)	bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
162 #if defined(linux) && defined(_KERNEL)
163 # define Bcopy(a, b, n)	memmove(((caddr_t)(b)), ((caddr_t)(a)), (unsigned)(n))
164 #else
165 # define Bcopy(a, b, n)	bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
166 #endif
167 #define Bzero(p, n)		bzero((caddr_t)(p), (unsigned)(n));
168 #define R_Malloc(p, t, n)	KMALLOCS(p, t, n)
169 #define FreeS(p, z)		KFREES(p, z)
170 #define Free(p)			KFREE(p)
171 
172 #if (defined(__osf__) || defined(AIX) || (IRIX >= 60516)) && defined(_KERNEL)
173 # define	rn_init		ipf_rn_init
174 # define	rn_fini		ipf_rn_fini
175 # define	rn_inithead	ipf_rn_inithead
176 # define	rn_freehead	ipf_rn_freehead
177 # define	rn_inithead0	ipf_rn_inithead0
178 # define	rn_refines	ipf_rn_refines
179 # define	rn_walktree	ipf_rn_walktree
180 # define	rn_addmask	ipf_rn_addmask
181 # define	rn_addroute	ipf_rn_addroute
182 # define	rn_delete	ipf_rn_delete
183 # define	rn_insert	ipf_rn_insert
184 # define	rn_lookup	ipf_rn_lookup
185 # define	rn_match	ipf_rn_match
186 # define	rn_newpair	ipf_rn_newpair
187 # define	rn_search	ipf_rn_search
188 # define	rn_search_m	ipf_rn_search_m
189 # define	max_keylen	ipf_maxkeylen
190 # define	rn_mkfreelist	ipf_rn_mkfreelist
191 # define	rn_zeros	ipf_rn_zeros
192 # define	rn_ones		ipf_rn_ones
193 # define	rn_satisfies_leaf	ipf_rn_satisfies_leaf
194 # define	rn_lexobetter	ipf_rn_lexobetter
195 # define	rn_new_radix_mask	ipf_rn_new_radix_mask
196 # define	rn_freenode	ipf_rn_freenode
197 #endif
198 
199 void	 rn_init __P((void));
200 void	 rn_fini __P((void));
201 int	 rn_inithead __P((void **, int));
202 void	 rn_freehead __P((struct radix_node_head *));
203 int	 rn_inithead0 __P((struct radix_node_head *, int));
204 int	 rn_refines __P((void *, void *));
205 int	 rn_walktree __P((struct radix_node_head *,
206 			  int (*)(struct radix_node *, void *), void *));
207 struct radix_node
208 	 *rn_addmask __P((void *, int, int)),
209 	 *rn_addroute __P((void *, void *, struct radix_node_head *,
210 			struct radix_node [2])),
211 	 *rn_delete __P((void *, void *, struct radix_node_head *)),
212 	 *rn_insert __P((void *, struct radix_node_head *, int *,
213 			struct radix_node [2])),
214 	 *rn_lookup __P((void *, void *, struct radix_node_head *)),
215 	 *rn_match __P((void *, struct radix_node_head *)),
216 	 *rn_newpair __P((void *, int, struct radix_node[2])),
217 	 *rn_search __P((void *, struct radix_node *)),
218 	 *rn_search_m __P((void *, struct radix_node *, void *));
219 
220 #endif /* _NET_RADIX_H_ */
221 #endif /* SOLARIS2 */
222 #endif /* RADIX_IPF_H */
223