xref: /illumos-gate/usr/src/uts/common/inet/ipf/radix_ipf.h (revision 2d6eb4a5e0a47d30189497241345dc5466bb68ab)
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 #if SOLARIS2 > 10
33 #include <net/radix.h>
34 #else
35 #if !defined(_NET_RADIX_H_) && !defined(_RADIX_H_)
36 #define	_NET_RADIX_H_
37 #ifndef _RADIX_H_
38 #define	_RADIX_H_
39 #endif /* _RADIX_H_ */
40 
41 #ifndef __P
42 # ifdef __STDC__
43 #  define	__P(x)  x
44 # else
45 #  define	__P(x)  ()
46 # endif
47 #endif
48 
49 #if defined(__sgi)
50 # define	radix_mask	ipf_radix_mask
51 # define	radix_node	ipf_radix_node
52 # define	radix_node_head	ipf_radix_node_head
53 #endif
54 
55 /*
56  * Radix search tree node layout.
57  */
58 
59 struct radix_node {
60 	struct	radix_mask *rn_mklist;	/* list of masks contained in subtree */
61 	struct	radix_node *rn_p;	/* parent */
62 	short	rn_b;			/* bit offset; -1-index(netmask) */
63 	char	rn_bmask;		/* node: mask for bit test*/
64 	u_char	rn_flags;		/* enumerated next */
65 #define RNF_NORMAL	1		/* leaf contains normal route */
66 #define RNF_ROOT	2		/* leaf is root leaf for tree */
67 #define RNF_ACTIVE	4		/* This node is alive (for rtfree) */
68 	union {
69 		struct {			/* leaf only data: */
70 			caddr_t rn_Key;		/* object of search */
71 			caddr_t rn_Mask;	/* netmask, if present */
72 			struct	radix_node *rn_Dupedkey;
73 		} rn_leaf;
74 		struct {			/* node only data: */
75 			int	rn_Off;		/* where to start compare */
76 			struct	radix_node *rn_L;/* progeny */
77 			struct	radix_node *rn_R;/* progeny */
78 		} rn_node;
79 	} rn_u;
80 #ifdef RN_DEBUG
81 	int rn_info;
82 	struct radix_node *rn_twin;
83 	struct radix_node *rn_ybro;
84 #endif
85 };
86 
87 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
88 #define rn_key rn_u.rn_leaf.rn_Key
89 #define rn_mask rn_u.rn_leaf.rn_Mask
90 #define rn_off rn_u.rn_node.rn_Off
91 #define rn_l rn_u.rn_node.rn_L
92 #define rn_r rn_u.rn_node.rn_R
93 
94 /*
95  * Annotations to tree concerning potential routes applying to subtrees.
96  */
97 
98 struct radix_mask {
99 	short	rm_b;			/* bit offset; -1-index(netmask) */
100 	char	rm_unused;		/* cf. rn_bmask */
101 	u_char	rm_flags;		/* cf. rn_flags */
102 	struct	radix_mask *rm_mklist;	/* more masks to try */
103 	union	{
104 		caddr_t	rmu_mask;		/* the mask */
105 		struct	radix_node *rmu_leaf;	/* for normal routes */
106 	}	rm_rmu;
107 	int	rm_refs;		/* # of references to this struct */
108 };
109 
110 #define rm_mask rm_rmu.rmu_mask
111 #define rm_leaf rm_rmu.rmu_leaf		/* extra field would make 32 bytes */
112 
113 #define MKGet(m) {\
114 	if (rn_mkfreelist) {\
115 		m = rn_mkfreelist; \
116 		rn_mkfreelist = (m)->rm_mklist; \
117 	} else \
118 		R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
119 
120 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
121 
122 struct radix_node_head {
123 	struct	radix_node *rnh_treetop;
124 	struct	radix_node *rnh_leaflist;
125 	u_long	rnh_hits;
126 	u_int	rnh_number;
127 	u_int	rnh_ref;
128 	int	rnh_addrsize;		/* permit, but not require fixed keys */
129 	int	rnh_pktsize;		/* permit, but not require fixed keys */
130 	struct	radix_node *(*rnh_addaddr)	/* add based on sockaddr */
131 		__P((void *v, void *mask,
132 		     struct radix_node_head *head, struct radix_node nodes[]));
133 	struct	radix_node *(*rnh_addpkt)	/* add based on packet hdr */
134 		__P((void *v, void *mask,
135 		     struct radix_node_head *head, struct radix_node nodes[]));
136 	struct	radix_node *(*rnh_deladdr)	/* remove based on sockaddr */
137 		__P((void *v, void *mask, struct radix_node_head *head));
138 	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */
139 		__P((void *v, void *mask, struct radix_node_head *head));
140 	struct	radix_node *(*rnh_matchaddr)	/* locate based on sockaddr */
141 		__P((void *v, struct radix_node_head *head));
142 	struct	radix_node *(*rnh_lookup)	/* locate based on sockaddr */
143 		__P((void *v, void *mask, struct radix_node_head *head));
144 	struct	radix_node *(*rnh_matchpkt)	/* locate based on packet hdr */
145 		__P((void *v, struct radix_node_head *head));
146 	int	(*rnh_walktree)			/* traverse tree */
147 		__P((struct radix_node_head *,
148 		     int (*)(struct radix_node *, void *), void *));
149 	struct	radix_node rnh_nodes[3];	/* empty tree for common case */
150 };
151 
152 
153 #if defined(AIX)
154 # undef Bcmp
155 # undef Bzero
156 # undef R_Malloc
157 # undef Free
158 #endif
159 #define Bcmp(a, b, n)	bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
160 #if defined(linux) && defined(_KERNEL)
161 # define Bcopy(a, b, n)	memmove(((caddr_t)(b)), ((caddr_t)(a)), (unsigned)(n))
162 #else
163 # define Bcopy(a, b, n)	bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
164 #endif
165 #define Bzero(p, n)		bzero((caddr_t)(p), (unsigned)(n));
166 #define R_Malloc(p, t, n)	KMALLOCS(p, t, n)
167 #define FreeS(p, z)		KFREES(p, z)
168 #define Free(p)			KFREE(p)
169 
170 #if (defined(__osf__) || defined(AIX) || (IRIX >= 60516)) && defined(_KERNEL)
171 # define	rn_init		ipf_rn_init
172 # define	rn_fini		ipf_rn_fini
173 # define	rn_inithead	ipf_rn_inithead
174 # define	rn_freehead	ipf_rn_freehead
175 # define	rn_inithead0	ipf_rn_inithead0
176 # define	rn_refines	ipf_rn_refines
177 # define	rn_walktree	ipf_rn_walktree
178 # define	rn_addmask	ipf_rn_addmask
179 # define	rn_addroute	ipf_rn_addroute
180 # define	rn_delete	ipf_rn_delete
181 # define	rn_insert	ipf_rn_insert
182 # define	rn_lookup	ipf_rn_lookup
183 # define	rn_match	ipf_rn_match
184 # define	rn_newpair	ipf_rn_newpair
185 # define	rn_search	ipf_rn_search
186 # define	rn_search_m	ipf_rn_search_m
187 # define	max_keylen	ipf_maxkeylen
188 # define	rn_mkfreelist	ipf_rn_mkfreelist
189 # define	rn_zeros	ipf_rn_zeros
190 # define	rn_ones		ipf_rn_ones
191 # define	rn_satisfies_leaf	ipf_rn_satisfies_leaf
192 # define	rn_lexobetter	ipf_rn_lexobetter
193 # define	rn_new_radix_mask	ipf_rn_new_radix_mask
194 # define	rn_freenode	ipf_rn_freenode
195 #endif
196 
197 void	 rn_init __P((void));
198 void	 rn_fini __P((void));
199 int	 rn_inithead __P((void **, int));
200 void	 rn_freehead __P((struct radix_node_head *));
201 int	 rn_inithead0 __P((struct radix_node_head *, int));
202 int	 rn_refines __P((void *, void *));
203 int	 rn_walktree __P((struct radix_node_head *,
204 			  int (*)(struct radix_node *, void *), void *));
205 struct radix_node
206 	 *rn_addmask __P((void *, int, int)),
207 	 *rn_addroute __P((void *, void *, struct radix_node_head *,
208 			struct radix_node [2])),
209 	 *rn_delete __P((void *, void *, struct radix_node_head *)),
210 	 *rn_insert __P((void *, struct radix_node_head *, int *,
211 			struct radix_node [2])),
212 	 *rn_lookup __P((void *, void *, struct radix_node_head *)),
213 	 *rn_match __P((void *, struct radix_node_head *)),
214 	 *rn_newpair __P((void *, int, struct radix_node[2])),
215 	 *rn_search __P((void *, struct radix_node *)),
216 	 *rn_search_m __P((void *, struct radix_node *, void *));
217 
218 #endif /* _NET_RADIX_H_ */
219 #endif /* SOLARIS2 */
220 #endif /* RADIX_IPF_H */
221