xref: /dragonfly/sys/net/radix.h (revision c92088d5)
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  * 3. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  *	@(#)radix.h	8.2 (Berkeley) 10/31/94
30  * $FreeBSD: src/sys/net/radix.h,v 1.16.2.1 2000/05/03 19:17:11 wollman Exp $
31  */
32 
33 #ifndef _NET_RADIX_H_
34 #define	_NET_RADIX_H_
35 
36 #include <sys/types.h>
37 
38 /*
39  * Radix search tree node layout.
40  */
41 
42 struct radix_node {
43 	struct	radix_mask *rn_mklist;	/* masks contained in subtree */
44 	struct	radix_node *rn_parent;	/* parent */
45 	int	rn_bit;		/* node: bit offset; leaf: -1-index(netmask) */
46 	u_char	rn_flags;	/* enumerated next */
47 #define RNF_NORMAL	1	/* leaf contains normal route */
48 #define RNF_ROOT	2	/* leaf is root node (embedded in the tree) */
49 #define RNF_ACTIVE	4	/* node is alive (for rtfree) */
50 	union {
51 		/* leaf-only data: */
52 		struct {
53 			/* object of search; point to the key passed by the
54 			 * caller */
55 			const u_char *rn_Key;
56 			/* optional netmask; if present, point to the rn_key
57 			 * of a node in the mask tree */
58 			const u_char *rn_Mask;
59 			/* chain of routes with the same key but differnt
60 			 * netmasks. */
61 			struct	radix_node *rn_Dupedkey;
62 		} rn_leaf;
63 		/* node-only data: */
64 		struct {
65 			int	rn_Offset;	/* where to start compare */
66 			u_char	rn_Bmask;	/* byte mask for bit test */
67 			struct	radix_node *rn_Left; /* progeny */
68 			struct	radix_node *rn_Right; /* progeny */
69 		} rn_node;
70 	}	rn_u;
71 #ifdef RN_DEBUG
72 	int rn_info;
73 	struct radix_node *rn_twin;
74 	struct radix_node *rn_ybro;
75 #endif
76 };
77 
78 #define	rn_dupedkey	rn_u.rn_leaf.rn_Dupedkey
79 #define	rn_key		rn_u.rn_leaf.rn_Key
80 #define	rn_mask		rn_u.rn_leaf.rn_Mask
81 #define	rn_offset	rn_u.rn_node.rn_Offset
82 #define	rn_bmask	rn_u.rn_node.rn_Bmask
83 #define	rn_left		rn_u.rn_node.rn_Left
84 #define	rn_right	rn_u.rn_node.rn_Right
85 
86 /*
87  * We do this statically now because the dynamic initialization
88  * occurs too late and has an ordering problem w/ pf preloads
89  * vs protocol domains.
90  */
91 #define RN_MAXKEYLEN	32
92 #define RN_MAXKEYONES	{ -1, -1, -1, -1, -1, -1, -1, -1,	\
93 			  -1, -1, -1, -1, -1, -1, -1, -1,	\
94 			  -1, -1, -1, -1, -1, -1, -1, -1,	\
95 			  -1, -1, -1, -1, -1, -1, -1, -1 }
96 
97 /*
98  * Annotations to tree concerning potential routes applying to subtrees.
99  */
100 
101 struct radix_mask {
102 	int	rm_bit;			/* bit offset; -1-index(netmask) */
103 	char	rm_unused;
104 	u_char	rm_flags;		/* cf. rn_flags */
105 	struct	radix_mask *rm_next;	/* list of more masks to try */
106 	union	{
107 		const u_char *rmu_mask;		/* the mask */
108 		struct	radix_node *rmu_leaf;	/* for normal routes */
109 	}	rm_rmu;
110 	int	rm_refs;		/* # of references to this struct */
111 };
112 
113 #define	rm_mask rm_rmu.rmu_mask
114 #define	rm_leaf rm_rmu.rmu_leaf
115 
116 typedef int walktree_f_t (struct radix_node *, void *);
117 typedef void freenode_f_t (struct radix_node *);
118 
119 struct radix_node_head {
120 	struct	radix_node *rnh_treetop;
121 
122 	/* add based on sockaddr */
123 	struct	radix_node *(*rnh_addaddr)
124 		    (const void *key, const void *mask,
125 		     struct radix_node_head *head, struct radix_node nodes[]);
126 
127 	/* remove based on sockaddr */
128 	struct	radix_node *(*rnh_deladdr)
129 		    (const void *key, const void *mask,
130 		     struct radix_node_head *head);
131 
132 	/* locate based on sockaddr */
133 	struct	radix_node *(*rnh_matchaddr)
134 		    (const void *key, struct radix_node_head *head);
135 
136 	/* locate based on sockaddr */
137 	struct	radix_node *(*rnh_lookup)
138 		    (const void *key, const void *mask,
139 		     struct radix_node_head *head);
140 
141 	/* traverse tree */
142 	int	(*rnh_walktree)
143 		    (struct radix_node_head *head, walktree_f_t *f, void *w);
144 
145 	/* traverse tree below a */
146 	int	(*rnh_walktree_from)
147 		    (struct radix_node_head *head, const void *addr,
148 		     const void *mask, walktree_f_t *f, void *w);
149 
150 	/*
151 	 * Do something when the last ref drops.
152 	 * A (*rnh_close)() routine
153 	 *	can clear RTF_UP
154 	 *	can remove a route from the radix tree
155 	 *	cannot change the reference count
156 	 *	cannot deallocate the route
157 	 */
158 	void	(*rnh_close)
159 		    (struct radix_node *rn, struct radix_node_head *head);
160 
161 	/*
162 	 * Embedded nodes (flagged with RNF_ROOT) for an empty tree:
163 	 * - left node
164 	 * - top/root node (pointed by rnh_treetop)
165 	 * - right node
166 	 */
167 	struct	radix_node rnh_nodes[3];
168 
169 	/* unused entries */
170 	int	rnh_addrsize;		/* permit, but not require fixed keys */
171 	int	rnh_pktsize;		/* permit, but not require fixed keys */
172 	struct	radix_node *(*rnh_addpkt)	/* add based on packet hdr */
173 		    (const void *v, const void *mask,
174 		     struct radix_node_head *head, struct radix_node nodes[]);
175 	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */
176 		    (const void *v, const void *mask,
177 		     struct radix_node_head *head);
178 
179 	/* traverse tree starting from a */
180 	int	(*rnh_walktree_at)
181 		    (struct radix_node_head *head, const void *addr,
182 		     const void *mask, walktree_f_t *f, void *w);
183 
184 	struct radix_node_head *rnh_maskhead;
185 };
186 
187 #ifdef _KERNEL
188 
189 #ifdef MALLOC_DECLARE
190 MALLOC_DECLARE(M_RTABLE);
191 #endif
192 
193 #define R_Malloc(p, t, n) \
194 	(p = (t) kmalloc((n), M_RTABLE, M_INTWAIT | M_NULLOK))
195 #define R_Free(p)	kfree(p, M_RTABLE)
196 
197 #else /* !_KERNEL */
198 
199 #include <stdbool.h>
200 
201 #define R_Malloc(p, t, n)	(p = (t) malloc((n)))
202 #define R_Free(p)		free(p)
203 
204 #endif /* _KERNEL */
205 
206 void			 rn_init(void);
207 int			 rn_inithead(struct radix_node_head **head,
208 				     struct radix_node_head *maskhead,
209 				     int off_bytes);
210 void			 rn_freehead(struct radix_node_head *head);
211 void			 rn_flush(struct radix_node_head *head,
212 				  freenode_f_t *f);
213 void			 rn_freemask(struct radix_node *rn);
214 struct radix_node_head	*rn_cpumaskhead(int cpu);
215 bool			 rn_refines(const void *m, const void *n);
216 struct radix_node	*rn_addmask(const void *mask, bool search, int skip,
217 				    struct radix_node_head *maskhead);
218 struct radix_node	*rn_addroute(const void *key, const void *mask,
219 				     struct radix_node_head *head,
220 				     struct radix_node nodes[2]);
221 struct radix_node	*rn_delete(const void *key, const void *mask,
222 				   struct radix_node_head *head);
223 struct radix_node	*rn_lookup(const void *key, const void *mask,
224 				   struct radix_node_head *head);
225 struct radix_node	*rn_match(const void *key,
226 				  struct radix_node_head *head);
227 
228 #endif /* _NET_RADIX_H_ */
229