1 | /* $NetBSD: radix.c,v 1.46 2016/11/15 01:50:06 ozaki-r Exp $ */ |
2 | |
3 | /* |
4 | * Copyright (c) 1988, 1989, 1993 |
5 | * The Regents of the University of California. All rights reserved. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following conditions |
9 | * are met: |
10 | * 1. Redistributions of source code must retain the above copyright |
11 | * notice, this list of conditions and the following disclaimer. |
12 | * 2. Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in the |
14 | * documentation and/or other materials provided with the distribution. |
15 | * 3. Neither the name of the University nor the names of its contributors |
16 | * may be used to endorse or promote products derived from this software |
17 | * without specific prior written permission. |
18 | * |
19 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
20 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
22 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
23 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
24 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
25 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
26 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
27 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
28 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
29 | * SUCH DAMAGE. |
30 | * |
31 | * @(#)radix.c 8.6 (Berkeley) 10/17/95 |
32 | */ |
33 | |
34 | /* |
35 | * Routines to build and maintain radix trees for routing lookups. |
36 | */ |
37 | |
38 | #include <sys/cdefs.h> |
39 | __KERNEL_RCSID(0, "$NetBSD: radix.c,v 1.46 2016/11/15 01:50:06 ozaki-r Exp $" ); |
40 | |
41 | #ifndef _NET_RADIX_H_ |
42 | #include <sys/param.h> |
43 | #include <sys/queue.h> |
44 | #include <sys/kmem.h> |
45 | #ifdef _KERNEL |
46 | #ifdef _KERNEL_OPT |
47 | #include "opt_inet.h" |
48 | #endif |
49 | |
50 | #include <sys/systm.h> |
51 | #include <sys/malloc.h> |
52 | #define M_DONTWAIT M_NOWAIT |
53 | #include <sys/domain.h> |
54 | #else |
55 | #include <stdlib.h> |
56 | #endif |
57 | #include <sys/syslog.h> |
58 | #include <net/radix.h> |
59 | #endif |
60 | |
61 | typedef void (*rn_printer_t)(void *, const char *fmt, ...); |
62 | |
63 | int max_keylen; |
64 | struct radix_mask *rn_mkfreelist; |
65 | struct radix_node_head *mask_rnhead; |
66 | static char *addmask_key; |
67 | static const char normal_chars[] = |
68 | {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1}; |
69 | static char *rn_zeros, *rn_ones; |
70 | |
71 | #define rn_masktop (mask_rnhead->rnh_treetop) |
72 | |
73 | static int rn_satisfies_leaf(const char *, struct radix_node *, int); |
74 | static int rn_lexobetter(const void *, const void *); |
75 | static struct radix_mask *rn_new_radix_mask(struct radix_node *, |
76 | struct radix_mask *); |
77 | static struct radix_node *rn_walknext(struct radix_node *, rn_printer_t, |
78 | void *); |
79 | static struct radix_node *rn_walkfirst(struct radix_node *, rn_printer_t, |
80 | void *); |
81 | static void rn_nodeprint(struct radix_node *, rn_printer_t, void *, |
82 | const char *); |
83 | |
84 | #define SUBTREE_OPEN "[ " |
85 | #define SUBTREE_CLOSE " ]" |
86 | |
87 | #ifdef RN_DEBUG |
88 | static void rn_treeprint(struct radix_node_head *, rn_printer_t, void *); |
89 | #endif /* RN_DEBUG */ |
90 | |
91 | /* |
92 | * The data structure for the keys is a radix tree with one way |
93 | * branching removed. The index rn_b at an internal node n represents a bit |
94 | * position to be tested. The tree is arranged so that all descendants |
95 | * of a node n have keys whose bits all agree up to position rn_b - 1. |
96 | * (We say the index of n is rn_b.) |
97 | * |
98 | * There is at least one descendant which has a one bit at position rn_b, |
99 | * and at least one with a zero there. |
100 | * |
101 | * A route is determined by a pair of key and mask. We require that the |
102 | * bit-wise logical and of the key and mask to be the key. |
103 | * We define the index of a route to associated with the mask to be |
104 | * the first bit number in the mask where 0 occurs (with bit number 0 |
105 | * representing the highest order bit). |
106 | * |
107 | * We say a mask is normal if every bit is 0, past the index of the mask. |
108 | * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, |
109 | * and m is a normal mask, then the route applies to every descendant of n. |
110 | * If the index(m) < rn_b, this implies the trailing last few bits of k |
111 | * before bit b are all 0, (and hence consequently true of every descendant |
112 | * of n), so the route applies to all descendants of the node as well. |
113 | * |
114 | * Similar logic shows that a non-normal mask m such that |
115 | * index(m) <= index(n) could potentially apply to many children of n. |
116 | * Thus, for each non-host route, we attach its mask to a list at an internal |
117 | * node as high in the tree as we can go. |
118 | * |
119 | * The present version of the code makes use of normal routes in short- |
120 | * circuiting an explicit mask and compare operation when testing whether |
121 | * a key satisfies a normal route, and also in remembering the unique leaf |
122 | * that governs a subtree. |
123 | */ |
124 | |
125 | struct radix_node * |
126 | rn_search( |
127 | const void *v_arg, |
128 | struct radix_node *head) |
129 | { |
130 | const u_char * const v = v_arg; |
131 | struct radix_node *x; |
132 | |
133 | for (x = head; x->rn_b >= 0;) { |
134 | if (x->rn_bmask & v[x->rn_off]) |
135 | x = x->rn_r; |
136 | else |
137 | x = x->rn_l; |
138 | } |
139 | return x; |
140 | } |
141 | |
142 | struct radix_node * |
143 | rn_search_m( |
144 | const void *v_arg, |
145 | struct radix_node *head, |
146 | const void *m_arg) |
147 | { |
148 | struct radix_node *x; |
149 | const u_char * const v = v_arg; |
150 | const u_char * const m = m_arg; |
151 | |
152 | for (x = head; x->rn_b >= 0;) { |
153 | if ((x->rn_bmask & m[x->rn_off]) && |
154 | (x->rn_bmask & v[x->rn_off])) |
155 | x = x->rn_r; |
156 | else |
157 | x = x->rn_l; |
158 | } |
159 | return x; |
160 | } |
161 | |
162 | int |
163 | rn_refines( |
164 | const void *m_arg, |
165 | const void *n_arg) |
166 | { |
167 | const char *m = m_arg; |
168 | const char *n = n_arg; |
169 | const char *lim = n + *(const u_char *)n; |
170 | const char *lim2 = lim; |
171 | int longer = (*(const u_char *)n++) - (int)(*(const u_char *)m++); |
172 | int masks_are_equal = 1; |
173 | |
174 | if (longer > 0) |
175 | lim -= longer; |
176 | while (n < lim) { |
177 | if (*n & ~(*m)) |
178 | return 0; |
179 | if (*n++ != *m++) |
180 | masks_are_equal = 0; |
181 | } |
182 | while (n < lim2) |
183 | if (*n++) |
184 | return 0; |
185 | if (masks_are_equal && (longer < 0)) |
186 | for (lim2 = m - longer; m < lim2; ) |
187 | if (*m++) |
188 | return 1; |
189 | return !masks_are_equal; |
190 | } |
191 | |
192 | struct radix_node * |
193 | rn_lookup( |
194 | const void *v_arg, |
195 | const void *m_arg, |
196 | struct radix_node_head *head) |
197 | { |
198 | struct radix_node *x; |
199 | const char *netmask = NULL; |
200 | |
201 | if (m_arg) { |
202 | if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) |
203 | return NULL; |
204 | netmask = x->rn_key; |
205 | } |
206 | x = rn_match(v_arg, head); |
207 | if (x != NULL && netmask != NULL) { |
208 | while (x != NULL && x->rn_mask != netmask) |
209 | x = x->rn_dupedkey; |
210 | } |
211 | return x; |
212 | } |
213 | |
214 | static int |
215 | rn_satisfies_leaf( |
216 | const char *trial, |
217 | struct radix_node *leaf, |
218 | int skip) |
219 | { |
220 | const char *cp = trial; |
221 | const char *cp2 = leaf->rn_key; |
222 | const char *cp3 = leaf->rn_mask; |
223 | const char *cplim; |
224 | int length = min(*(const u_char *)cp, *(const u_char *)cp2); |
225 | |
226 | if (cp3 == 0) |
227 | cp3 = rn_ones; |
228 | else |
229 | length = min(length, *(const u_char *)cp3); |
230 | cplim = cp + length; cp3 += skip; cp2 += skip; |
231 | for (cp += skip; cp < cplim; cp++, cp2++, cp3++) |
232 | if ((*cp ^ *cp2) & *cp3) |
233 | return 0; |
234 | return 1; |
235 | } |
236 | |
237 | struct radix_node * |
238 | rn_match( |
239 | const void *v_arg, |
240 | struct radix_node_head *head) |
241 | { |
242 | const char * const v = v_arg; |
243 | struct radix_node *t = head->rnh_treetop; |
244 | struct radix_node *top = t; |
245 | struct radix_node *x; |
246 | struct radix_node *saved_t; |
247 | const char *cp = v; |
248 | const char *cp2; |
249 | const char *cplim; |
250 | int off = t->rn_off; |
251 | int vlen = *(const u_char *)cp; |
252 | int matched_off; |
253 | int test, b, rn_b; |
254 | |
255 | /* |
256 | * Open code rn_search(v, top) to avoid overhead of extra |
257 | * subroutine call. |
258 | */ |
259 | for (; t->rn_b >= 0; ) { |
260 | if (t->rn_bmask & cp[t->rn_off]) |
261 | t = t->rn_r; |
262 | else |
263 | t = t->rn_l; |
264 | } |
265 | /* |
266 | * See if we match exactly as a host destination |
267 | * or at least learn how many bits match, for normal mask finesse. |
268 | * |
269 | * It doesn't hurt us to limit how many bytes to check |
270 | * to the length of the mask, since if it matches we had a genuine |
271 | * match and the leaf we have is the most specific one anyway; |
272 | * if it didn't match with a shorter length it would fail |
273 | * with a long one. This wins big for class B&C netmasks which |
274 | * are probably the most common case... |
275 | */ |
276 | if (t->rn_mask) |
277 | vlen = *(const u_char *)t->rn_mask; |
278 | cp += off; cp2 = t->rn_key + off; cplim = v + vlen; |
279 | for (; cp < cplim; cp++, cp2++) |
280 | if (*cp != *cp2) |
281 | goto on1; |
282 | /* |
283 | * This extra grot is in case we are explicitly asked |
284 | * to look up the default. Ugh! |
285 | */ |
286 | if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) |
287 | t = t->rn_dupedkey; |
288 | return t; |
289 | on1: |
290 | test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ |
291 | for (b = 7; (test >>= 1) > 0;) |
292 | b--; |
293 | matched_off = cp - v; |
294 | b += matched_off << 3; |
295 | rn_b = -1 - b; |
296 | /* |
297 | * If there is a host route in a duped-key chain, it will be first. |
298 | */ |
299 | if ((saved_t = t)->rn_mask == 0) |
300 | t = t->rn_dupedkey; |
301 | for (; t; t = t->rn_dupedkey) |
302 | /* |
303 | * Even if we don't match exactly as a host, |
304 | * we may match if the leaf we wound up at is |
305 | * a route to a net. |
306 | */ |
307 | if (t->rn_flags & RNF_NORMAL) { |
308 | if (rn_b <= t->rn_b) |
309 | return t; |
310 | } else if (rn_satisfies_leaf(v, t, matched_off)) |
311 | return t; |
312 | t = saved_t; |
313 | /* start searching up the tree */ |
314 | do { |
315 | struct radix_mask *m; |
316 | t = t->rn_p; |
317 | m = t->rn_mklist; |
318 | if (m) { |
319 | /* |
320 | * If non-contiguous masks ever become important |
321 | * we can restore the masking and open coding of |
322 | * the search and satisfaction test and put the |
323 | * calculation of "off" back before the "do". |
324 | */ |
325 | do { |
326 | if (m->rm_flags & RNF_NORMAL) { |
327 | if (rn_b <= m->rm_b) |
328 | return m->rm_leaf; |
329 | } else { |
330 | off = min(t->rn_off, matched_off); |
331 | x = rn_search_m(v, t, m->rm_mask); |
332 | while (x && x->rn_mask != m->rm_mask) |
333 | x = x->rn_dupedkey; |
334 | if (x && rn_satisfies_leaf(v, x, off)) |
335 | return x; |
336 | } |
337 | m = m->rm_mklist; |
338 | } while (m); |
339 | } |
340 | } while (t != top); |
341 | return NULL; |
342 | } |
343 | |
344 | static void |
345 | rn_nodeprint(struct radix_node *rn, rn_printer_t printer, void *arg, |
346 | const char *delim) |
347 | { |
348 | (*printer)(arg, "%s(%s%p: p<%p> l<%p> r<%p>)" , |
349 | delim, ((void *)rn == arg) ? "*" : "" , rn, rn->rn_p, |
350 | rn->rn_l, rn->rn_r); |
351 | } |
352 | |
353 | #ifdef RN_DEBUG |
354 | int rn_debug = 1; |
355 | |
356 | static void |
357 | rn_dbg_print(void *arg, const char *fmt, ...) |
358 | { |
359 | va_list ap; |
360 | |
361 | va_start(ap, fmt); |
362 | vlog(LOG_DEBUG, fmt, ap); |
363 | va_end(ap); |
364 | } |
365 | |
366 | static void |
367 | rn_treeprint(struct radix_node_head *h, rn_printer_t printer, void *arg) |
368 | { |
369 | struct radix_node *dup, *rn; |
370 | const char *delim; |
371 | |
372 | if (printer == NULL) |
373 | return; |
374 | |
375 | rn = rn_walkfirst(h->rnh_treetop, printer, arg); |
376 | for (;;) { |
377 | /* Process leaves */ |
378 | delim = "" ; |
379 | for (dup = rn; dup != NULL; dup = dup->rn_dupedkey) { |
380 | if ((dup->rn_flags & RNF_ROOT) != 0) |
381 | continue; |
382 | rn_nodeprint(dup, printer, arg, delim); |
383 | delim = ", " ; |
384 | } |
385 | rn = rn_walknext(rn, printer, arg); |
386 | if (rn->rn_flags & RNF_ROOT) |
387 | return; |
388 | } |
389 | /* NOTREACHED */ |
390 | } |
391 | |
392 | #define traverse(__head, __rn) rn_treeprint((__head), rn_dbg_print, (__rn)) |
393 | #endif /* RN_DEBUG */ |
394 | |
395 | struct radix_node * |
396 | rn_newpair( |
397 | const void *v, |
398 | int b, |
399 | struct radix_node nodes[2]) |
400 | { |
401 | struct radix_node *tt = nodes; |
402 | struct radix_node *t = tt + 1; |
403 | t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); |
404 | t->rn_l = tt; t->rn_off = b >> 3; |
405 | tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t; |
406 | tt->rn_flags = t->rn_flags = RNF_ACTIVE; |
407 | return t; |
408 | } |
409 | |
410 | struct radix_node * |
411 | rn_insert( |
412 | const void *v_arg, |
413 | struct radix_node_head *head, |
414 | int *dupentry, |
415 | struct radix_node nodes[2]) |
416 | { |
417 | struct radix_node *top = head->rnh_treetop; |
418 | struct radix_node *t = rn_search(v_arg, top); |
419 | struct radix_node *tt; |
420 | const char *v = v_arg; |
421 | int head_off = top->rn_off; |
422 | int vlen = *((const u_char *)v); |
423 | const char *cp = v + head_off; |
424 | int b; |
425 | /* |
426 | * Find first bit at which v and t->rn_key differ |
427 | */ |
428 | { |
429 | const char *cp2 = t->rn_key + head_off; |
430 | const char *cplim = v + vlen; |
431 | int cmp_res; |
432 | |
433 | while (cp < cplim) |
434 | if (*cp2++ != *cp++) |
435 | goto on1; |
436 | *dupentry = 1; |
437 | return t; |
438 | on1: |
439 | *dupentry = 0; |
440 | cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; |
441 | for (b = (cp - v) << 3; cmp_res; b--) |
442 | cmp_res >>= 1; |
443 | } |
444 | { |
445 | struct radix_node *p, *x = top; |
446 | cp = v; |
447 | do { |
448 | p = x; |
449 | if (cp[x->rn_off] & x->rn_bmask) |
450 | x = x->rn_r; |
451 | else x = x->rn_l; |
452 | } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ |
453 | #ifdef RN_DEBUG |
454 | if (rn_debug) |
455 | log(LOG_DEBUG, "%s: Going In:\n" , __func__), traverse(head, p); |
456 | #endif |
457 | t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; |
458 | if ((cp[p->rn_off] & p->rn_bmask) == 0) |
459 | p->rn_l = t; |
460 | else |
461 | p->rn_r = t; |
462 | x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ |
463 | if ((cp[t->rn_off] & t->rn_bmask) == 0) { |
464 | t->rn_r = x; |
465 | } else { |
466 | t->rn_r = tt; t->rn_l = x; |
467 | } |
468 | #ifdef RN_DEBUG |
469 | if (rn_debug) { |
470 | log(LOG_DEBUG, "%s: Coming Out:\n" , __func__), |
471 | traverse(head, p); |
472 | } |
473 | #endif /* RN_DEBUG */ |
474 | } |
475 | return tt; |
476 | } |
477 | |
478 | struct radix_node * |
479 | rn_addmask( |
480 | const void *n_arg, |
481 | int search, |
482 | int skip) |
483 | { |
484 | const char *netmask = n_arg; |
485 | const char *cp; |
486 | const char *cplim; |
487 | struct radix_node *x; |
488 | struct radix_node *saved_x; |
489 | int b = 0, mlen, j; |
490 | int maskduplicated, m0, isnormal; |
491 | static int last_zeroed = 0; |
492 | |
493 | if ((mlen = *(const u_char *)netmask) > max_keylen) |
494 | mlen = max_keylen; |
495 | if (skip == 0) |
496 | skip = 1; |
497 | if (mlen <= skip) |
498 | return mask_rnhead->rnh_nodes; |
499 | if (skip > 1) |
500 | memmove(addmask_key + 1, rn_ones + 1, skip - 1); |
501 | if ((m0 = mlen) > skip) |
502 | memmove(addmask_key + skip, netmask + skip, mlen - skip); |
503 | /* |
504 | * Trim trailing zeroes. |
505 | */ |
506 | for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) |
507 | cp--; |
508 | mlen = cp - addmask_key; |
509 | if (mlen <= skip) { |
510 | if (m0 >= last_zeroed) |
511 | last_zeroed = mlen; |
512 | return mask_rnhead->rnh_nodes; |
513 | } |
514 | if (m0 < last_zeroed) |
515 | memset(addmask_key + m0, 0, last_zeroed - m0); |
516 | *addmask_key = last_zeroed = mlen; |
517 | x = rn_search(addmask_key, rn_masktop); |
518 | if (memcmp(addmask_key, x->rn_key, mlen) != 0) |
519 | x = 0; |
520 | if (x || search) |
521 | return x; |
522 | R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); |
523 | if ((saved_x = x) == NULL) |
524 | return NULL; |
525 | memset(x, 0, max_keylen + 2 * sizeof (*x)); |
526 | cp = netmask = (void *)(x + 2); |
527 | memmove(x + 2, addmask_key, mlen); |
528 | x = rn_insert(cp, mask_rnhead, &maskduplicated, x); |
529 | if (maskduplicated) { |
530 | log(LOG_ERR, "rn_addmask: mask impossibly already in tree\n" ); |
531 | Free(saved_x); |
532 | return x; |
533 | } |
534 | /* |
535 | * Calculate index of mask, and check for normalcy. |
536 | */ |
537 | cplim = netmask + mlen; isnormal = 1; |
538 | for (cp = netmask + skip; (cp < cplim) && *(const u_char *)cp == 0xff;) |
539 | cp++; |
540 | if (cp != cplim) { |
541 | for (j = 0x80; (j & *cp) != 0; j >>= 1) |
542 | b++; |
543 | if (*cp != normal_chars[b] || cp != (cplim - 1)) |
544 | isnormal = 0; |
545 | } |
546 | b += (cp - netmask) << 3; |
547 | x->rn_b = -1 - b; |
548 | if (isnormal) |
549 | x->rn_flags |= RNF_NORMAL; |
550 | return x; |
551 | } |
552 | |
553 | static int /* XXX: arbitrary ordering for non-contiguous masks */ |
554 | rn_lexobetter( |
555 | const void *m_arg, |
556 | const void *n_arg) |
557 | { |
558 | const u_char *mp = m_arg; |
559 | const u_char *np = n_arg; |
560 | const u_char *lim; |
561 | |
562 | if (*mp > *np) |
563 | return 1; /* not really, but need to check longer one first */ |
564 | if (*mp == *np) |
565 | for (lim = mp + *mp; mp < lim;) |
566 | if (*mp++ > *np++) |
567 | return 1; |
568 | return 0; |
569 | } |
570 | |
571 | static struct radix_mask * |
572 | rn_new_radix_mask( |
573 | struct radix_node *tt, |
574 | struct radix_mask *next) |
575 | { |
576 | struct radix_mask *m; |
577 | |
578 | MKGet(m); |
579 | if (m == NULL) { |
580 | log(LOG_ERR, "Mask for route not entered\n" ); |
581 | return NULL; |
582 | } |
583 | memset(m, 0, sizeof(*m)); |
584 | m->rm_b = tt->rn_b; |
585 | m->rm_flags = tt->rn_flags; |
586 | if (tt->rn_flags & RNF_NORMAL) |
587 | m->rm_leaf = tt; |
588 | else |
589 | m->rm_mask = tt->rn_mask; |
590 | m->rm_mklist = next; |
591 | tt->rn_mklist = m; |
592 | return m; |
593 | } |
594 | |
595 | struct radix_node * |
596 | rn_addroute( |
597 | const void *v_arg, |
598 | const void *n_arg, |
599 | struct radix_node_head *head, |
600 | struct radix_node treenodes[2]) |
601 | { |
602 | const char *v = v_arg, *netmask = n_arg; |
603 | struct radix_node *t, *x = NULL, *tt; |
604 | struct radix_node *saved_tt, *top = head->rnh_treetop; |
605 | short b = 0, b_leaf = 0; |
606 | int keyduplicated; |
607 | const char *mmask; |
608 | struct radix_mask *m, **mp; |
609 | |
610 | /* |
611 | * In dealing with non-contiguous masks, there may be |
612 | * many different routes which have the same mask. |
613 | * We will find it useful to have a unique pointer to |
614 | * the mask to speed avoiding duplicate references at |
615 | * nodes and possibly save time in calculating indices. |
616 | */ |
617 | if (netmask != NULL) { |
618 | if ((x = rn_addmask(netmask, 0, top->rn_off)) == NULL) |
619 | return NULL; |
620 | b_leaf = x->rn_b; |
621 | b = -1 - x->rn_b; |
622 | netmask = x->rn_key; |
623 | } |
624 | /* |
625 | * Deal with duplicated keys: attach node to previous instance |
626 | */ |
627 | saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); |
628 | if (keyduplicated) { |
629 | for (t = tt; tt != NULL; t = tt, tt = tt->rn_dupedkey) { |
630 | if (tt->rn_mask == netmask) |
631 | return NULL; |
632 | if (netmask == NULL || |
633 | (tt->rn_mask != NULL && |
634 | (b_leaf < tt->rn_b || /* index(netmask) > node */ |
635 | rn_refines(netmask, tt->rn_mask) || |
636 | rn_lexobetter(netmask, tt->rn_mask)))) |
637 | break; |
638 | } |
639 | /* |
640 | * If the mask is not duplicated, we wouldn't |
641 | * find it among possible duplicate key entries |
642 | * anyway, so the above test doesn't hurt. |
643 | * |
644 | * We sort the masks for a duplicated key the same way as |
645 | * in a masklist -- most specific to least specific. |
646 | * This may require the unfortunate nuisance of relocating |
647 | * the head of the list. |
648 | * |
649 | * We also reverse, or doubly link the list through the |
650 | * parent pointer. |
651 | */ |
652 | if (tt == saved_tt) { |
653 | struct radix_node *xx = x; |
654 | /* link in at head of list */ |
655 | (tt = treenodes)->rn_dupedkey = t; |
656 | tt->rn_flags = t->rn_flags; |
657 | tt->rn_p = x = t->rn_p; |
658 | t->rn_p = tt; |
659 | if (x->rn_l == t) |
660 | x->rn_l = tt; |
661 | else |
662 | x->rn_r = tt; |
663 | saved_tt = tt; |
664 | x = xx; |
665 | } else { |
666 | (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; |
667 | t->rn_dupedkey = tt; |
668 | tt->rn_p = t; |
669 | if (tt->rn_dupedkey) |
670 | tt->rn_dupedkey->rn_p = tt; |
671 | } |
672 | tt->rn_key = v; |
673 | tt->rn_b = -1; |
674 | tt->rn_flags = RNF_ACTIVE; |
675 | } |
676 | /* |
677 | * Put mask in tree. |
678 | */ |
679 | if (netmask != NULL) { |
680 | tt->rn_mask = netmask; |
681 | tt->rn_b = x->rn_b; |
682 | tt->rn_flags |= x->rn_flags & RNF_NORMAL; |
683 | } |
684 | t = saved_tt->rn_p; |
685 | if (keyduplicated) |
686 | goto on2; |
687 | b_leaf = -1 - t->rn_b; |
688 | if (t->rn_r == saved_tt) |
689 | x = t->rn_l; |
690 | else |
691 | x = t->rn_r; |
692 | /* Promote general routes from below */ |
693 | if (x->rn_b < 0) { |
694 | for (mp = &t->rn_mklist; x != NULL; x = x->rn_dupedkey) { |
695 | if (x->rn_mask != NULL && x->rn_b >= b_leaf && |
696 | x->rn_mklist == NULL) { |
697 | *mp = m = rn_new_radix_mask(x, NULL); |
698 | if (m != NULL) |
699 | mp = &m->rm_mklist; |
700 | } |
701 | } |
702 | } else if (x->rn_mklist != NULL) { |
703 | /* |
704 | * Skip over masks whose index is > that of new node |
705 | */ |
706 | for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) |
707 | if (m->rm_b >= b_leaf) |
708 | break; |
709 | t->rn_mklist = m; |
710 | *mp = NULL; |
711 | } |
712 | on2: |
713 | /* Add new route to highest possible ancestor's list */ |
714 | if (netmask == NULL || b > t->rn_b) |
715 | return tt; /* can't lift at all */ |
716 | b_leaf = tt->rn_b; |
717 | do { |
718 | x = t; |
719 | t = t->rn_p; |
720 | } while (b <= t->rn_b && x != top); |
721 | /* |
722 | * Search through routes associated with node to |
723 | * insert new route according to index. |
724 | * Need same criteria as when sorting dupedkeys to avoid |
725 | * double loop on deletion. |
726 | */ |
727 | for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) { |
728 | if (m->rm_b < b_leaf) |
729 | continue; |
730 | if (m->rm_b > b_leaf) |
731 | break; |
732 | if (m->rm_flags & RNF_NORMAL) { |
733 | mmask = m->rm_leaf->rn_mask; |
734 | if (tt->rn_flags & RNF_NORMAL) { |
735 | log(LOG_ERR, "Non-unique normal route," |
736 | " mask not entered\n" ); |
737 | return tt; |
738 | } |
739 | } else |
740 | mmask = m->rm_mask; |
741 | if (mmask == netmask) { |
742 | m->rm_refs++; |
743 | tt->rn_mklist = m; |
744 | return tt; |
745 | } |
746 | if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) |
747 | break; |
748 | } |
749 | *mp = rn_new_radix_mask(tt, *mp); |
750 | return tt; |
751 | } |
752 | |
753 | struct radix_node * |
754 | rn_delete1( |
755 | const void *v_arg, |
756 | const void *netmask_arg, |
757 | struct radix_node_head *head, |
758 | struct radix_node *rn) |
759 | { |
760 | struct radix_node *t, *p, *x, *tt; |
761 | struct radix_mask *m, *saved_m, **mp; |
762 | struct radix_node *dupedkey, *saved_tt, *top; |
763 | const char *v, *netmask; |
764 | int b, head_off, vlen; |
765 | |
766 | v = v_arg; |
767 | netmask = netmask_arg; |
768 | x = head->rnh_treetop; |
769 | tt = rn_search(v, x); |
770 | head_off = x->rn_off; |
771 | vlen = *(const u_char *)v; |
772 | saved_tt = tt; |
773 | top = x; |
774 | if (tt == NULL || |
775 | memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off) != 0) |
776 | return NULL; |
777 | /* |
778 | * Delete our route from mask lists. |
779 | */ |
780 | if (netmask != NULL) { |
781 | if ((x = rn_addmask(netmask, 1, head_off)) == NULL) |
782 | return NULL; |
783 | netmask = x->rn_key; |
784 | while (tt->rn_mask != netmask) |
785 | if ((tt = tt->rn_dupedkey) == NULL) |
786 | return NULL; |
787 | } |
788 | if (tt->rn_mask == NULL || (saved_m = m = tt->rn_mklist) == NULL) |
789 | goto on1; |
790 | if (tt->rn_flags & RNF_NORMAL) { |
791 | if (m->rm_leaf != tt || m->rm_refs > 0) { |
792 | log(LOG_ERR, "rn_delete: inconsistent annotation\n" ); |
793 | return NULL; /* dangling ref could cause disaster */ |
794 | } |
795 | } else { |
796 | if (m->rm_mask != tt->rn_mask) { |
797 | log(LOG_ERR, "rn_delete: inconsistent annotation\n" ); |
798 | goto on1; |
799 | } |
800 | if (--m->rm_refs >= 0) |
801 | goto on1; |
802 | } |
803 | b = -1 - tt->rn_b; |
804 | t = saved_tt->rn_p; |
805 | if (b > t->rn_b) |
806 | goto on1; /* Wasn't lifted at all */ |
807 | do { |
808 | x = t; |
809 | t = t->rn_p; |
810 | } while (b <= t->rn_b && x != top); |
811 | for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) { |
812 | if (m == saved_m) { |
813 | *mp = m->rm_mklist; |
814 | MKFree(m); |
815 | break; |
816 | } |
817 | } |
818 | if (m == NULL) { |
819 | log(LOG_ERR, "rn_delete: couldn't find our annotation\n" ); |
820 | if (tt->rn_flags & RNF_NORMAL) |
821 | return NULL; /* Dangling ref to us */ |
822 | } |
823 | on1: |
824 | /* |
825 | * Eliminate us from tree |
826 | */ |
827 | if (tt->rn_flags & RNF_ROOT) |
828 | return NULL; |
829 | #ifdef RN_DEBUG |
830 | if (rn_debug) |
831 | log(LOG_DEBUG, "%s: Going In:\n" , __func__), traverse(head, tt); |
832 | #endif |
833 | t = tt->rn_p; |
834 | dupedkey = saved_tt->rn_dupedkey; |
835 | if (dupedkey != NULL) { |
836 | /* |
837 | * Here, tt is the deletion target, and |
838 | * saved_tt is the head of the dupedkey chain. |
839 | */ |
840 | if (tt == saved_tt) { |
841 | x = dupedkey; |
842 | x->rn_p = t; |
843 | if (t->rn_l == tt) |
844 | t->rn_l = x; |
845 | else |
846 | t->rn_r = x; |
847 | } else { |
848 | /* find node in front of tt on the chain */ |
849 | for (x = p = saved_tt; |
850 | p != NULL && p->rn_dupedkey != tt;) |
851 | p = p->rn_dupedkey; |
852 | if (p != NULL) { |
853 | p->rn_dupedkey = tt->rn_dupedkey; |
854 | if (tt->rn_dupedkey != NULL) |
855 | tt->rn_dupedkey->rn_p = p; |
856 | } else |
857 | log(LOG_ERR, "rn_delete: couldn't find us\n" ); |
858 | } |
859 | t = tt + 1; |
860 | if (t->rn_flags & RNF_ACTIVE) { |
861 | *++x = *t; |
862 | p = t->rn_p; |
863 | if (p->rn_l == t) |
864 | p->rn_l = x; |
865 | else |
866 | p->rn_r = x; |
867 | x->rn_l->rn_p = x; |
868 | x->rn_r->rn_p = x; |
869 | } |
870 | goto out; |
871 | } |
872 | if (t->rn_l == tt) |
873 | x = t->rn_r; |
874 | else |
875 | x = t->rn_l; |
876 | p = t->rn_p; |
877 | if (p->rn_r == t) |
878 | p->rn_r = x; |
879 | else |
880 | p->rn_l = x; |
881 | x->rn_p = p; |
882 | /* |
883 | * Demote routes attached to us. |
884 | */ |
885 | if (t->rn_mklist == NULL) |
886 | ; |
887 | else if (x->rn_b >= 0) { |
888 | for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) |
889 | ; |
890 | *mp = t->rn_mklist; |
891 | } else { |
892 | /* If there are any key,mask pairs in a sibling |
893 | duped-key chain, some subset will appear sorted |
894 | in the same order attached to our mklist */ |
895 | for (m = t->rn_mklist; |
896 | m != NULL && x != NULL; |
897 | x = x->rn_dupedkey) { |
898 | if (m == x->rn_mklist) { |
899 | struct radix_mask *mm = m->rm_mklist; |
900 | x->rn_mklist = NULL; |
901 | if (--(m->rm_refs) < 0) |
902 | MKFree(m); |
903 | m = mm; |
904 | } |
905 | } |
906 | if (m != NULL) { |
907 | log(LOG_ERR, "rn_delete: Orphaned Mask %p at %p\n" , |
908 | m, x); |
909 | } |
910 | } |
911 | /* |
912 | * We may be holding an active internal node in the tree. |
913 | */ |
914 | x = tt + 1; |
915 | if (t != x) { |
916 | *t = *x; |
917 | t->rn_l->rn_p = t; |
918 | t->rn_r->rn_p = t; |
919 | p = x->rn_p; |
920 | if (p->rn_l == x) |
921 | p->rn_l = t; |
922 | else |
923 | p->rn_r = t; |
924 | } |
925 | out: |
926 | #ifdef RN_DEBUG |
927 | if (rn_debug) { |
928 | log(LOG_DEBUG, "%s: Coming Out:\n" , __func__), |
929 | traverse(head, tt); |
930 | } |
931 | #endif /* RN_DEBUG */ |
932 | tt->rn_flags &= ~RNF_ACTIVE; |
933 | tt[1].rn_flags &= ~RNF_ACTIVE; |
934 | return tt; |
935 | } |
936 | |
937 | struct radix_node * |
938 | rn_delete( |
939 | const void *v_arg, |
940 | const void *netmask_arg, |
941 | struct radix_node_head *head) |
942 | { |
943 | return rn_delete1(v_arg, netmask_arg, head, NULL); |
944 | } |
945 | |
946 | static struct radix_node * |
947 | rn_walknext(struct radix_node *rn, rn_printer_t printer, void *arg) |
948 | { |
949 | /* If at right child go back up, otherwise, go right */ |
950 | while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) { |
951 | if (printer != NULL) |
952 | (*printer)(arg, SUBTREE_CLOSE); |
953 | rn = rn->rn_p; |
954 | } |
955 | if (printer) |
956 | rn_nodeprint(rn->rn_p, printer, arg, "" ); |
957 | /* Find the next *leaf* since next node might vanish, too */ |
958 | for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) { |
959 | if (printer != NULL) |
960 | (*printer)(arg, SUBTREE_OPEN); |
961 | rn = rn->rn_l; |
962 | } |
963 | return rn; |
964 | } |
965 | |
966 | static struct radix_node * |
967 | rn_walkfirst(struct radix_node *rn, rn_printer_t printer, void *arg) |
968 | { |
969 | /* First time through node, go left */ |
970 | while (rn->rn_b >= 0) { |
971 | if (printer != NULL) |
972 | (*printer)(arg, SUBTREE_OPEN); |
973 | rn = rn->rn_l; |
974 | } |
975 | return rn; |
976 | } |
977 | |
978 | int |
979 | rn_walktree( |
980 | struct radix_node_head *h, |
981 | int (*f)(struct radix_node *, void *), |
982 | void *w) |
983 | { |
984 | int error; |
985 | struct radix_node *base, *next, *rn; |
986 | /* |
987 | * This gets complicated because we may delete the node |
988 | * while applying the function f to it, so we need to calculate |
989 | * the successor node in advance. |
990 | */ |
991 | rn = rn_walkfirst(h->rnh_treetop, NULL, NULL); |
992 | for (;;) { |
993 | base = rn; |
994 | next = rn_walknext(rn, NULL, NULL); |
995 | /* Process leaves */ |
996 | while ((rn = base) != NULL) { |
997 | base = rn->rn_dupedkey; |
998 | if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) |
999 | return error; |
1000 | } |
1001 | rn = next; |
1002 | if (rn->rn_flags & RNF_ROOT) |
1003 | return 0; |
1004 | } |
1005 | /* NOTREACHED */ |
1006 | } |
1007 | |
1008 | struct radix_node * |
1009 | rn_search_matched(struct radix_node_head *h, |
1010 | int (*matcher)(struct radix_node *, void *), void *w) |
1011 | { |
1012 | bool matched; |
1013 | struct radix_node *base, *next, *rn; |
1014 | /* |
1015 | * This gets complicated because we may delete the node |
1016 | * while applying the function f to it, so we need to calculate |
1017 | * the successor node in advance. |
1018 | */ |
1019 | rn = rn_walkfirst(h->rnh_treetop, NULL, NULL); |
1020 | for (;;) { |
1021 | base = rn; |
1022 | next = rn_walknext(rn, NULL, NULL); |
1023 | /* Process leaves */ |
1024 | while ((rn = base) != NULL) { |
1025 | base = rn->rn_dupedkey; |
1026 | if (!(rn->rn_flags & RNF_ROOT)) { |
1027 | matched = (*matcher)(rn, w); |
1028 | if (matched) |
1029 | return rn; |
1030 | } |
1031 | } |
1032 | rn = next; |
1033 | if (rn->rn_flags & RNF_ROOT) |
1034 | return NULL; |
1035 | } |
1036 | /* NOTREACHED */ |
1037 | } |
1038 | |
1039 | struct delayinit { |
1040 | void **head; |
1041 | int off; |
1042 | SLIST_ENTRY(delayinit) entries; |
1043 | }; |
1044 | static SLIST_HEAD(, delayinit) delayinits = SLIST_HEAD_INITIALIZER(delayheads); |
1045 | static int radix_initialized; |
1046 | |
1047 | /* |
1048 | * Initialize a radix tree once radix is initialized. Only for bootstrap. |
1049 | * Assume that no concurrency protection is necessary at this stage. |
1050 | */ |
1051 | void |
1052 | rn_delayedinit(void **head, int off) |
1053 | { |
1054 | struct delayinit *di; |
1055 | |
1056 | KASSERT(radix_initialized == 0); |
1057 | |
1058 | di = kmem_alloc(sizeof(*di), KM_SLEEP); |
1059 | di->head = head; |
1060 | di->off = off; |
1061 | SLIST_INSERT_HEAD(&delayinits, di, entries); |
1062 | } |
1063 | |
1064 | int |
1065 | rn_inithead(void **head, int off) |
1066 | { |
1067 | struct radix_node_head *rnh; |
1068 | |
1069 | if (*head != NULL) |
1070 | return 1; |
1071 | R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); |
1072 | if (rnh == NULL) |
1073 | return 0; |
1074 | *head = rnh; |
1075 | return rn_inithead0(rnh, off); |
1076 | } |
1077 | |
1078 | int |
1079 | rn_inithead0(struct radix_node_head *rnh, int off) |
1080 | { |
1081 | struct radix_node *t; |
1082 | struct radix_node *tt; |
1083 | struct radix_node *ttt; |
1084 | |
1085 | memset(rnh, 0, sizeof(*rnh)); |
1086 | t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); |
1087 | ttt = rnh->rnh_nodes + 2; |
1088 | t->rn_r = ttt; |
1089 | t->rn_p = t; |
1090 | tt = t->rn_l; |
1091 | tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; |
1092 | tt->rn_b = -1 - off; |
1093 | *ttt = *tt; |
1094 | ttt->rn_key = rn_ones; |
1095 | rnh->rnh_addaddr = rn_addroute; |
1096 | rnh->rnh_deladdr = rn_delete; |
1097 | rnh->rnh_matchaddr = rn_match; |
1098 | rnh->rnh_lookup = rn_lookup; |
1099 | rnh->rnh_treetop = t; |
1100 | return 1; |
1101 | } |
1102 | |
1103 | void |
1104 | rn_init(void) |
1105 | { |
1106 | char *cp, *cplim; |
1107 | struct delayinit *di; |
1108 | #ifdef _KERNEL |
1109 | struct domain *dp; |
1110 | |
1111 | if (radix_initialized) |
1112 | panic("radix already initialized" ); |
1113 | radix_initialized = 1; |
1114 | |
1115 | DOMAIN_FOREACH(dp) { |
1116 | if (dp->dom_maxrtkey > max_keylen) |
1117 | max_keylen = dp->dom_maxrtkey; |
1118 | } |
1119 | #endif |
1120 | if (max_keylen == 0) { |
1121 | log(LOG_ERR, |
1122 | "rn_init: radix functions require max_keylen be set\n" ); |
1123 | return; |
1124 | } |
1125 | |
1126 | R_Malloc(rn_zeros, char *, 3 * max_keylen); |
1127 | if (rn_zeros == NULL) |
1128 | panic("rn_init" ); |
1129 | memset(rn_zeros, 0, 3 * max_keylen); |
1130 | rn_ones = cp = rn_zeros + max_keylen; |
1131 | addmask_key = cplim = rn_ones + max_keylen; |
1132 | while (cp < cplim) |
1133 | *cp++ = -1; |
1134 | if (rn_inithead((void *)&mask_rnhead, 0) == 0) |
1135 | panic("rn_init 2" ); |
1136 | |
1137 | while ((di = SLIST_FIRST(&delayinits)) != NULL) { |
1138 | if (!rn_inithead(di->head, di->off)) |
1139 | panic("delayed rn_inithead failed" ); |
1140 | SLIST_REMOVE_HEAD(&delayinits, entries); |
1141 | kmem_free(di, sizeof(*di)); |
1142 | } |
1143 | } |
1144 | |