Commit | Line | Data |
---|---|---|
984263bc MD |
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. | |
2c64e990 | 13 | * 3. Neither the name of the University nor the names of its contributors |
984263bc MD |
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 | ||
1bd40720 MD |
33 | #ifndef _NET_RADIX_H_ |
34 | #define _NET_RADIX_H_ | |
35 | ||
1bd40720 | 36 | #include <sys/types.h> |
984263bc | 37 | |
984263bc MD |
38 | /* |
39 | * Radix search tree node layout. | |
40 | */ | |
41 | ||
42 | struct radix_node { | |
2e9572df | 43 | struct radix_mask *rn_mklist; /* masks contained in subtree */ |
984263bc | 44 | struct radix_node *rn_parent; /* parent */ |
c92088d5 | 45 | int rn_bit; /* node: bit offset; leaf: -1-index(netmask) */ |
7e65cd3b AL |
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) */ | |
984263bc | 50 | union { |
7e65cd3b AL |
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. */ | |
984263bc MD |
61 | struct radix_node *rn_Dupedkey; |
62 | } rn_leaf; | |
7e65cd3b AL |
63 | /* node-only data: */ |
64 | struct { | |
90f10db5 | 65 | int rn_Offset; /* where to start compare */ |
a3643718 | 66 | u_char rn_Bmask; /* byte mask for bit test */ |
d7a94067 AL |
67 | struct radix_node *rn_Left; /* progeny */ |
68 | struct radix_node *rn_Right; /* progeny */ | |
984263bc | 69 | } rn_node; |
d7a94067 | 70 | } rn_u; |
984263bc MD |
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 | |
90f10db5 | 81 | #define rn_offset rn_u.rn_node.rn_Offset |
d7a94067 AL |
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 | |
984263bc | 85 | |
70cef922 MD |
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 | ||
984263bc MD |
97 | /* |
98 | * Annotations to tree concerning potential routes applying to subtrees. | |
99 | */ | |
100 | ||
101 | struct radix_mask { | |
c92088d5 | 102 | int rm_bit; /* bit offset; -1-index(netmask) */ |
7e65cd3b | 103 | char rm_unused; |
984263bc | 104 | u_char rm_flags; /* cf. rn_flags */ |
2e9572df | 105 | struct radix_mask *rm_next; /* list of more masks to try */ |
984263bc | 106 | union { |
a3643718 | 107 | const u_char *rmu_mask; /* the mask */ |
984263bc MD |
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 | |
7e65cd3b | 114 | #define rm_leaf rm_rmu.rmu_leaf |
984263bc | 115 | |
158abb01 | 116 | typedef int walktree_f_t (struct radix_node *, void *); |
101038a2 | 117 | typedef void freenode_f_t (struct radix_node *); |
984263bc MD |
118 | |
119 | struct radix_node_head { | |
120 | struct radix_node *rnh_treetop; | |
2e9572df JH |
121 | |
122 | /* add based on sockaddr */ | |
123 | struct radix_node *(*rnh_addaddr) | |
a3643718 | 124 | (const void *key, const void *mask, |
2e9572df JH |
125 | struct radix_node_head *head, struct radix_node nodes[]); |
126 | ||
127 | /* remove based on sockaddr */ | |
128 | struct radix_node *(*rnh_deladdr) | |
a3643718 | 129 | (const void *key, const void *mask, |
22dac581 | 130 | struct radix_node_head *head); |
2e9572df JH |
131 | |
132 | /* locate based on sockaddr */ | |
133 | struct radix_node *(*rnh_matchaddr) | |
a3643718 | 134 | (const void *key, struct radix_node_head *head); |
2e9572df JH |
135 | |
136 | /* locate based on sockaddr */ | |
137 | struct radix_node *(*rnh_lookup) | |
a3643718 | 138 | (const void *key, const void *mask, |
22dac581 | 139 | struct radix_node_head *head); |
2e9572df JH |
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) | |
a3643718 AL |
147 | (struct radix_node_head *head, const void *addr, |
148 | const void *mask, walktree_f_t *f, void *w); | |
2e9572df | 149 | |
0bf6c14c JH |
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 | */ | |
2e9572df JH |
158 | void (*rnh_close) |
159 | (struct radix_node *rn, struct radix_node_head *head); | |
160 | ||
7e65cd3b AL |
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]; | |
2e9572df JH |
168 | |
169 | /* unused entries */ | |
725ff871 | 170 | int rnh_addrsize; /* permit, but not require fixed keys */ |
984263bc | 171 | int rnh_pktsize; /* permit, but not require fixed keys */ |
984263bc | 172 | struct radix_node *(*rnh_addpkt) /* add based on packet hdr */ |
a3643718 | 173 | (const void *v, const void *mask, |
158abb01 | 174 | struct radix_node_head *head, struct radix_node nodes[]); |
984263bc | 175 | struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */ |
a3643718 | 176 | (const void *v, const void *mask, |
22dac581 | 177 | struct radix_node_head *head); |
291dd55b SZ |
178 | |
179 | /* traverse tree starting from a */ | |
180 | int (*rnh_walktree_at) | |
a3643718 AL |
181 | (struct radix_node_head *head, const void *addr, |
182 | const void *mask, walktree_f_t *f, void *w); | |
b4628cf9 SZ |
183 | |
184 | struct radix_node_head *rnh_maskhead; | |
984263bc MD |
185 | }; |
186 | ||
757c5b14 AL |
187 | #ifdef _KERNEL |
188 | ||
189 | #ifdef MALLOC_DECLARE | |
d3afab17 | 190 | MALLOC_DECLARE(M_RTABLE); |
2e9572df | 191 | #endif |
984263bc | 192 | |
757c5b14 AL |
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 | ||
3b5e1b0a AL |
199 | #include <stdbool.h> |
200 | ||
757c5b14 AL |
201 | #define R_Malloc(p, t, n) (p = (t) malloc((n))) |
202 | #define R_Free(p) free(p) | |
203 | ||
204 | #endif /* _KERNEL */ | |
205 | ||
305cf933 | 206 | void rn_init(void); |
6823c302 | 207 | int rn_inithead(struct radix_node_head **head, |
51203098 AL |
208 | struct radix_node_head *maskhead, |
209 | int off_bytes); | |
101038a2 AL |
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); | |
b4628cf9 | 214 | struct radix_node_head *rn_cpumaskhead(int cpu); |
a3643718 AL |
215 | bool rn_refines(const void *m, const void *n); |
216 | struct radix_node *rn_addmask(const void *mask, bool search, int skip, | |
305cf933 | 217 | struct radix_node_head *maskhead); |
a3643718 | 218 | struct radix_node *rn_addroute(const void *key, const void *mask, |
305cf933 AL |
219 | struct radix_node_head *head, |
220 | struct radix_node nodes[2]); | |
a3643718 | 221 | struct radix_node *rn_delete(const void *key, const void *mask, |
305cf933 | 222 | struct radix_node_head *head); |
a3643718 | 223 | struct radix_node *rn_lookup(const void *key, const void *mask, |
305cf933 | 224 | struct radix_node_head *head); |
a3643718 | 225 | struct radix_node *rn_match(const void *key, |
22dac581 | 226 | struct radix_node_head *head); |
984263bc | 227 | |
1bd40720 | 228 | #endif /* _NET_RADIX_H_ */ |