xref: /illumos-gate/usr/src/common/net/patricia/radix.c (revision bd670b35)
1c793af95Ssangeeta /*
2*bd670b35SErik Nordmark  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
3c793af95Ssangeeta  * Use is subject to license terms.
4c793af95Ssangeeta  *
5c793af95Ssangeeta  * Copyright (c) 1988, 1989, 1993
6c793af95Ssangeeta  *	The Regents of the University of California.  All rights reserved.
7c793af95Ssangeeta  *
8c793af95Ssangeeta  * Redistribution and use in source and binary forms, with or without
9c793af95Ssangeeta  * modification, are permitted provided that the following conditions
10c793af95Ssangeeta  * are met:
11c793af95Ssangeeta  * 1. Redistributions of source code must retain the above copyright
12c793af95Ssangeeta  *    notice, this list of conditions and the following disclaimer.
13c793af95Ssangeeta  * 2. Redistributions in binary form must reproduce the above copyright
14c793af95Ssangeeta  *    notice, this list of conditions and the following disclaimer in the
15c793af95Ssangeeta  *    documentation and/or other materials provided with the distribution.
16c793af95Ssangeeta  * 4. Neither the name of the University nor the names of its contributors
17c793af95Ssangeeta  *    may be used to endorse or promote products derived from this software
18c793af95Ssangeeta  *    without specific prior written permission.
19c793af95Ssangeeta  *
20c793af95Ssangeeta  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21c793af95Ssangeeta  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22c793af95Ssangeeta  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23c793af95Ssangeeta  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24c793af95Ssangeeta  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25c793af95Ssangeeta  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26c793af95Ssangeeta  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27c793af95Ssangeeta  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28c793af95Ssangeeta  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29c793af95Ssangeeta  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30c793af95Ssangeeta  * SUCH DAMAGE.
31c793af95Ssangeeta  *
32c793af95Ssangeeta  *	@(#)radix.c	8.5 (Berkeley) 5/19/95
33c793af95Ssangeeta  * $FreeBSD: /repoman/r/ncvs/src/sys/net/radix.c,v 1.36.2.1 2005/01/31 23:26:23
34c793af95Ssangeeta  * imp Exp $
35c793af95Ssangeeta  */
36c793af95Ssangeeta 
37c793af95Ssangeeta 
38c793af95Ssangeeta /*
39c793af95Ssangeeta  * Routines to build and maintain radix trees for routing lookups.
40c793af95Ssangeeta  */
41c793af95Ssangeeta #include <sys/types.h>
42c793af95Ssangeeta 
43c793af95Ssangeeta #ifndef _RADIX_H_
44c793af95Ssangeeta #include <sys/param.h>
45c793af95Ssangeeta #ifdef	_KERNEL
46c793af95Ssangeeta #include <sys/lock.h>
47c793af95Ssangeeta #include <sys/mutex.h>
48c793af95Ssangeeta #include <sys/systm.h>
49c793af95Ssangeeta #include <sys/cmn_err.h>
50c793af95Ssangeeta #else
51c793af95Ssangeeta #include <assert.h>
52c793af95Ssangeeta #define	ASSERT assert
53c793af95Ssangeeta #include <stdio.h>
54c793af95Ssangeeta #include <stdlib.h>
55c793af95Ssangeeta #include <syslog.h>
56c793af95Ssangeeta #include <strings.h>
57c793af95Ssangeeta #endif	/* _KERNEL */
58c793af95Ssangeeta #include <net/radix.h>
59c793af95Ssangeeta #endif
60c793af95Ssangeeta 
61c793af95Ssangeeta #ifndef	_KERNEL
62c793af95Ssangeeta void
panic(const char * str)63c793af95Ssangeeta panic(const char *str)
64c793af95Ssangeeta {
65c793af95Ssangeeta 	fprintf(stderr, "Panic - %s\n", str);
66c793af95Ssangeeta 	abort();
67c793af95Ssangeeta }
68c793af95Ssangeeta #endif	/* _KERNEL */
69c793af95Ssangeeta 
70c793af95Ssangeeta static int	rn_walktree(struct radix_node_head *, walktree_f_t *, void *);
712679e103Ssowmini static int	rn_walktree_mt(struct radix_node_head *, walktree_f_t *,
722679e103Ssowmini     void *, lockf_t, lockf_t);
73c793af95Ssangeeta static struct radix_node
74c793af95Ssangeeta 	*rn_insert(void *, struct radix_node_head *, int *,
75c793af95Ssangeeta 	    struct radix_node [2]),
76c793af95Ssangeeta 	*rn_newpair(void *, int, struct radix_node[2]),
77c793af95Ssangeeta 	*rn_search(void *, struct radix_node *),
78c793af95Ssangeeta 	*rn_search_m(void *, struct radix_node *, void *),
79c793af95Ssangeeta 	*rn_lookup(void *, void *, struct radix_node_head *),
80c793af95Ssangeeta 	*rn_match(void *, struct radix_node_head *),
81c793af95Ssangeeta 	*rn_match_args(void *, struct radix_node_head *, match_leaf_t *,
82c793af95Ssangeeta 	    void *),
83c793af95Ssangeeta 	*rn_addmask(void *, int, int),
84c793af95Ssangeeta 	*rn_addroute(void *, void *, struct radix_node_head *,
85c793af95Ssangeeta 	    struct radix_node [2]),
86c793af95Ssangeeta 	*rn_delete(void *, void *, struct radix_node_head *);
87c793af95Ssangeeta static	boolean_t rn_refines(void *, void *);
88c793af95Ssangeeta 
8940cdc2e8SAlexandr Nedvedicky /*
9040cdc2e8SAlexandr Nedvedicky  * IPF also uses PATRICIA tree to manage ippools. IPF stores its own structure
9140cdc2e8SAlexandr Nedvedicky  * addrfamily_t. sizeof (addrfamily_t) == 24.
9240cdc2e8SAlexandr Nedvedicky  */
9340cdc2e8SAlexandr Nedvedicky #define	MAX_KEYLEN	24
94c793af95Ssangeeta static int	max_keylen = MAX_KEYLEN;
95c793af95Ssangeeta 
96c793af95Ssangeeta #ifdef	_KERNEL
97c793af95Ssangeeta static struct kmem_cache *radix_mask_cache; /* for rn_mkfreelist */
98c793af95Ssangeeta static struct kmem_cache *radix_node_cache;
99c793af95Ssangeeta #else
100c793af95Ssangeeta static char *radix_mask_cache, *radix_node_cache; /* dummy vars. never inited */
101c793af95Ssangeeta #endif	/* _KERNEL */
102c793af95Ssangeeta 
103c793af95Ssangeeta static struct radix_mask *rn_mkfreelist;
104c793af95Ssangeeta static struct radix_node_head *mask_rnhead;
105c793af95Ssangeeta /*
106c793af95Ssangeeta  * Work area -- the following point to 2 buffers of size max_keylen,
107c793af95Ssangeeta  * allocated in this order in a block of memory malloc'ed by rn_init.
108c793af95Ssangeeta  * A third buffer of size MAX_KEYLEN is allocated from the stack.
109c793af95Ssangeeta  */
110c793af95Ssangeeta static char *rn_zeros, *rn_ones;
111c793af95Ssangeeta 
112c793af95Ssangeeta #define	MKGet(m)  R_Malloc(m, radix_mask_cache, sizeof (struct radix_mask))
113c793af95Ssangeeta #define	MKFree(m) Free(m, radix_mask_cache)
114c793af95Ssangeeta #define	rn_masktop (mask_rnhead->rnh_treetop)
115c793af95Ssangeeta 
116c793af95Ssangeeta static boolean_t	rn_lexobetter(void *m_arg, void *n_arg);
117c793af95Ssangeeta static struct radix_mask *
118c793af95Ssangeeta 		rn_new_radix_mask(struct radix_node *tt,
119c793af95Ssangeeta 		    struct radix_mask *next);
120c793af95Ssangeeta static boolean_t
121c793af95Ssangeeta 		rn_satisfies_leaf(char *trial, struct radix_node *leaf,
122c793af95Ssangeeta 		    int skip, match_leaf_t *rn_leaf_fn, void *rn_leaf_arg);
123c793af95Ssangeeta 
124c793af95Ssangeeta #define	RN_MATCHF(rn, f, arg)	(f == NULL || (*f)((rn), arg))
125c793af95Ssangeeta 
126c793af95Ssangeeta /*
127c793af95Ssangeeta  * The data structure for the keys is a radix tree with one way
128c793af95Ssangeeta  * branching removed.  The index rn_bit at an internal node n represents a bit
129c793af95Ssangeeta  * position to be tested.  The tree is arranged so that all descendants
130c793af95Ssangeeta  * of a node n have keys whose bits all agree up to position rn_bit - 1.
131c793af95Ssangeeta  * (We say the index of n is rn_bit.)
132c793af95Ssangeeta  *
133c793af95Ssangeeta  * There is at least one descendant which has a one bit at position rn_bit,
134c793af95Ssangeeta  * and at least one with a zero there.
135c793af95Ssangeeta  *
136c793af95Ssangeeta  * A route is determined by a pair of key and mask.  We require that the
137c793af95Ssangeeta  * bit-wise logical and of the key and mask to be the key.
138c793af95Ssangeeta  * We define the index of a route associated with the mask to be
139c793af95Ssangeeta  * the first bit number in the mask where 0 occurs (with bit number 0
140c793af95Ssangeeta  * representing the highest order bit).
141c793af95Ssangeeta  *
142c793af95Ssangeeta  * We say a mask is normal if every bit is 0, past the index of the mask.
143c793af95Ssangeeta  * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
144c793af95Ssangeeta  * and m is a normal mask, then the route applies to every descendant of n.
145c793af95Ssangeeta  * If the index(m) < rn_bit, this implies the trailing last few bits of k
146c793af95Ssangeeta  * before bit b are all 0, (and hence consequently true of every descendant
147c793af95Ssangeeta  * of n), so the route applies to all descendants of the node as well.
148c793af95Ssangeeta  *
149c793af95Ssangeeta  * Similar logic shows that a non-normal mask m such that
150c793af95Ssangeeta  * index(m) <= index(n) could potentially apply to many children of n.
151c793af95Ssangeeta  * Thus, for each non-host route, we attach its mask to a list at an internal
152c793af95Ssangeeta  * node as high in the tree as we can go.
153c793af95Ssangeeta  *
154c793af95Ssangeeta  * The present version of the code makes use of normal routes in short-
155c793af95Ssangeeta  * circuiting an explict mask and compare operation when testing whether
156c793af95Ssangeeta  * a key satisfies a normal route, and also in remembering the unique leaf
157c793af95Ssangeeta  * that governs a subtree.
158c793af95Ssangeeta  */
159c793af95Ssangeeta 
160c793af95Ssangeeta /*
161c793af95Ssangeeta  * Most of the functions in this code assume that the key/mask arguments
162c793af95Ssangeeta  * are sockaddr-like structures, where the first byte is an uchar_t
163c793af95Ssangeeta  * indicating the size of the entire structure.
164c793af95Ssangeeta  *
165c793af95Ssangeeta  * To make the assumption more explicit, we use the LEN() macro to access
166c793af95Ssangeeta  * this field. It is safe to pass an expression with side effects
167c793af95Ssangeeta  * to LEN() as the argument is evaluated only once.
168c793af95Ssangeeta  */
169c793af95Ssangeeta #define	LEN(x) (*(const uchar_t *)(x))
170c793af95Ssangeeta 
171c793af95Ssangeeta 
172c793af95Ssangeeta /*
173c793af95Ssangeeta  * Search a node in the tree matching the key.
174c793af95Ssangeeta  */
175c793af95Ssangeeta static struct radix_node *
rn_search(v_arg,head)176c793af95Ssangeeta rn_search(v_arg, head)
177c793af95Ssangeeta 	void *v_arg;
178c793af95Ssangeeta 	struct radix_node *head;
179c793af95Ssangeeta {
180c793af95Ssangeeta 	struct radix_node *x;
181c793af95Ssangeeta 	caddr_t v;
182c793af95Ssangeeta 
183c793af95Ssangeeta 	for (x = head, v = v_arg; x->rn_bit >= 0; ) {
184c793af95Ssangeeta 		if (x->rn_bmask & v[x->rn_offset])
185c793af95Ssangeeta 			x = x->rn_right;
186c793af95Ssangeeta 		else
187c793af95Ssangeeta 			x = x->rn_left;
188c793af95Ssangeeta 	}
189c793af95Ssangeeta 	return (x);
190c793af95Ssangeeta }
191c793af95Ssangeeta 
192c793af95Ssangeeta /*
193c793af95Ssangeeta  * Same as above, but with an additional mask.
194c793af95Ssangeeta  */
195c793af95Ssangeeta static struct radix_node *
rn_search_m(v_arg,head,m_arg)196c793af95Ssangeeta rn_search_m(v_arg, head, m_arg)
197c793af95Ssangeeta 	struct radix_node *head;
198c793af95Ssangeeta 	void *v_arg, *m_arg;
199c793af95Ssangeeta {
200c793af95Ssangeeta 	struct radix_node *x;
201c793af95Ssangeeta 	caddr_t v = v_arg, m = m_arg;
202c793af95Ssangeeta 
203c793af95Ssangeeta 	for (x = head; x->rn_bit >= 0; ) {
204c793af95Ssangeeta 		if ((x->rn_bmask & m[x->rn_offset]) &&
205c793af95Ssangeeta 		    (x->rn_bmask & v[x->rn_offset]))
206c793af95Ssangeeta 			x = x->rn_right;
207c793af95Ssangeeta 		else
208c793af95Ssangeeta 			x = x->rn_left;
209c793af95Ssangeeta 	}
210c793af95Ssangeeta 	return (x);
211c793af95Ssangeeta }
212c793af95Ssangeeta 
213c793af95Ssangeeta /*
214c793af95Ssangeeta  * Returns true if there are no bits set in n_arg that are zero in
215c793af95Ssangeeta  * m_arg and the masks aren't equal.  In other words, it returns true
216c793af95Ssangeeta  * when m_arg is a finer-granularity netmask -- it represents a subset
217c793af95Ssangeeta  * of the destinations implied by n_arg.
218c793af95Ssangeeta  */
219c793af95Ssangeeta static boolean_t
rn_refines(m_arg,n_arg)220c793af95Ssangeeta rn_refines(m_arg, n_arg)
221c793af95Ssangeeta 	void *m_arg, *n_arg;
222c793af95Ssangeeta {
223c793af95Ssangeeta 	caddr_t m = m_arg, n = n_arg;
224c793af95Ssangeeta 	caddr_t lim = n + LEN(n), lim2 = lim;
225c793af95Ssangeeta 	int longer = LEN(n++) - (int)LEN(m++);
226c793af95Ssangeeta 	boolean_t masks_are_equal = B_TRUE;
227c793af95Ssangeeta 
228c793af95Ssangeeta 	if (longer > 0)
229c793af95Ssangeeta 		lim -= longer;
230c793af95Ssangeeta 	while (n < lim) {
231c793af95Ssangeeta 		if (*n & ~(*m))
232c793af95Ssangeeta 			return (0);
233c793af95Ssangeeta 		if (*n++ != *m++)
234c793af95Ssangeeta 			masks_are_equal = B_FALSE;
235c793af95Ssangeeta 	}
236c793af95Ssangeeta 	while (n < lim2)
237c793af95Ssangeeta 		if (*n++)
238c793af95Ssangeeta 			return (B_FALSE);
239c793af95Ssangeeta 	if (masks_are_equal && (longer < 0))
240c793af95Ssangeeta 		for (lim2 = m - longer; m < lim2; )
241c793af95Ssangeeta 			if (*m++)
242c793af95Ssangeeta 				return (B_TRUE);
243c793af95Ssangeeta 	return (!masks_are_equal);
244c793af95Ssangeeta }
245c793af95Ssangeeta 
246c793af95Ssangeeta static struct radix_node *
rn_lookup(v_arg,m_arg,head)247c793af95Ssangeeta rn_lookup(v_arg, m_arg, head)
248c793af95Ssangeeta 	void *v_arg, *m_arg;
249c793af95Ssangeeta 	struct radix_node_head *head;
250c793af95Ssangeeta {
251c793af95Ssangeeta 	struct radix_node *x;
252c793af95Ssangeeta 	caddr_t netmask = NULL;
253c793af95Ssangeeta 
254c793af95Ssangeeta 	if (m_arg) {
255c793af95Ssangeeta 		x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
256c793af95Ssangeeta 		if (x == NULL)
257c793af95Ssangeeta 			return (NULL);
258c793af95Ssangeeta 		netmask = x->rn_key;
259c793af95Ssangeeta 	}
260c793af95Ssangeeta 	x = rn_match(v_arg, head);
261c793af95Ssangeeta 	if (x && netmask) {
262c793af95Ssangeeta 		while (x && x->rn_mask != netmask)
263c793af95Ssangeeta 			x = x->rn_dupedkey;
264c793af95Ssangeeta 	}
265c793af95Ssangeeta 	return (x);
266c793af95Ssangeeta }
267c793af95Ssangeeta 
268c793af95Ssangeeta /*
269c793af95Ssangeeta  * Returns true if address 'trial' has no bits differing from the
270c793af95Ssangeeta  * leaf's key when compared under the leaf's mask.  In other words,
271c793af95Ssangeeta  * returns true when 'trial' matches leaf.
272c793af95Ssangeeta  * In addition, if a rn_leaf_fn is passed in, that is used to find
273c793af95Ssangeeta  * a match on conditions defined by the caller of rn_match.  This is
274c793af95Ssangeeta  * used by the kernel ftable to match on IRE_MATCH_* conditions.
275c793af95Ssangeeta  */
276c793af95Ssangeeta static boolean_t
rn_satisfies_leaf(trial,leaf,skip,rn_leaf_fn,rn_leaf_arg)277c793af95Ssangeeta rn_satisfies_leaf(trial, leaf, skip, rn_leaf_fn, rn_leaf_arg)
278c793af95Ssangeeta 	caddr_t trial;
279c793af95Ssangeeta 	struct radix_node *leaf;
280c793af95Ssangeeta 	int skip;
281c793af95Ssangeeta 	match_leaf_t *rn_leaf_fn;
282c793af95Ssangeeta 	void *rn_leaf_arg;
283c793af95Ssangeeta {
284c793af95Ssangeeta 	char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
285c793af95Ssangeeta 	char *cplim;
286c793af95Ssangeeta 	int length = min(LEN(cp), LEN(cp2));
287c793af95Ssangeeta 
288c793af95Ssangeeta 	if (cp3 == 0)
289c793af95Ssangeeta 		cp3 = rn_ones;
290c793af95Ssangeeta 	else
291c793af95Ssangeeta 		length = min(length, LEN(cp3));
292c793af95Ssangeeta 	cplim = cp + length;
293c793af95Ssangeeta 	cp3 += skip;
294c793af95Ssangeeta 	cp2 += skip;
295c793af95Ssangeeta 
296c793af95Ssangeeta 	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
297c793af95Ssangeeta 		if ((*cp ^ *cp2) & *cp3)
298c793af95Ssangeeta 			return (B_FALSE);
299c793af95Ssangeeta 
300c793af95Ssangeeta 	return (RN_MATCHF(leaf, rn_leaf_fn, rn_leaf_arg));
301c793af95Ssangeeta }
302c793af95Ssangeeta 
303c793af95Ssangeeta static struct radix_node *
rn_match(v_arg,head)304c793af95Ssangeeta rn_match(v_arg, head)
305c793af95Ssangeeta 	void *v_arg;
306c793af95Ssangeeta 	struct radix_node_head *head;
307c793af95Ssangeeta {
308c793af95Ssangeeta 	return (rn_match_args(v_arg, head, NULL, NULL));
309c793af95Ssangeeta }
310c793af95Ssangeeta 
311c793af95Ssangeeta static struct radix_node *
rn_match_args(v_arg,head,rn_leaf_fn,rn_leaf_arg)312c793af95Ssangeeta rn_match_args(v_arg, head, rn_leaf_fn, rn_leaf_arg)
313c793af95Ssangeeta 	void *v_arg;
314c793af95Ssangeeta 	struct radix_node_head *head;
315c793af95Ssangeeta 	match_leaf_t *rn_leaf_fn;
316c793af95Ssangeeta 	void *rn_leaf_arg;
317c793af95Ssangeeta {
318c793af95Ssangeeta 	caddr_t v = v_arg;
319c793af95Ssangeeta 	struct radix_node *t = head->rnh_treetop, *x;
320c793af95Ssangeeta 	caddr_t cp = v, cp2;
321c793af95Ssangeeta 	caddr_t cplim;
322c793af95Ssangeeta 	struct radix_node *saved_t, *top = t;
323c793af95Ssangeeta 	int off = t->rn_offset, vlen = LEN(cp), matched_off;
324c793af95Ssangeeta 	int test, b, rn_bit;
325c793af95Ssangeeta 
326c793af95Ssangeeta 	/*
327c793af95Ssangeeta 	 * Open code rn_search(v, top) to avoid overhead of extra
328c793af95Ssangeeta 	 * subroutine call.
329c793af95Ssangeeta 	 */
330c793af95Ssangeeta 	for (; t->rn_bit >= 0; ) {
331c793af95Ssangeeta 		if (t->rn_bmask & cp[t->rn_offset])
332c793af95Ssangeeta 			t = t->rn_right;
333c793af95Ssangeeta 		else
334c793af95Ssangeeta 			t = t->rn_left;
335c793af95Ssangeeta 	}
336c793af95Ssangeeta 	/*
337c793af95Ssangeeta 	 * See if we match exactly as a host destination
338c793af95Ssangeeta 	 * or at least learn how many bits match, for normal mask finesse.
339c793af95Ssangeeta 	 *
340c793af95Ssangeeta 	 * It doesn't hurt us to limit how many bytes to check
341c793af95Ssangeeta 	 * to the length of the mask, since if it matches we had a genuine
342c793af95Ssangeeta 	 * match and the leaf we have is the most specific one anyway;
343c793af95Ssangeeta 	 * if it didn't match with a shorter length it would fail
344c793af95Ssangeeta 	 * with a long one.  This wins big for class B&C netmasks which
345c793af95Ssangeeta 	 * are probably the most common case...
346c793af95Ssangeeta 	 */
347c793af95Ssangeeta 	if (t->rn_mask)
348c793af95Ssangeeta 		vlen = LEN(t->rn_mask);
349c793af95Ssangeeta 	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
350c793af95Ssangeeta 	for (; cp < cplim; cp++, cp2++)
351c793af95Ssangeeta 		if (*cp != *cp2)
352c793af95Ssangeeta 			goto keydiff;
353c793af95Ssangeeta 	/*
354c793af95Ssangeeta 	 * This extra grot is in case we are explicitly asked
355c793af95Ssangeeta 	 * to look up the default.  Ugh!
356c793af95Ssangeeta 	 *
357c793af95Ssangeeta 	 * Never return the root node itself, it seems to cause a
358c793af95Ssangeeta 	 * lot of confusion.
359c793af95Ssangeeta 	 */
360c793af95Ssangeeta 	if (t->rn_flags & RNF_ROOT)
361c793af95Ssangeeta 		t = t->rn_dupedkey;
362c793af95Ssangeeta 	if (t == NULL || RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) {
363c793af95Ssangeeta 		return (t);
364c793af95Ssangeeta 	} else {
365c793af95Ssangeeta 		/*
366c793af95Ssangeeta 		 * Although we found an exact match on the key, rn_leaf_fn
367c793af95Ssangeeta 		 * is looking for some other criteria as well. Continue
368c793af95Ssangeeta 		 * looking as if the exact match failed.
369c793af95Ssangeeta 		 */
370*bd670b35SErik Nordmark 		if (t->rn_dupedkey == NULL &&
371*bd670b35SErik Nordmark 		    (t->rn_parent->rn_flags & RNF_ROOT)) {
372*bd670b35SErik Nordmark 			/* no more dupedkeys and hit the top. have to give up */
373c793af95Ssangeeta 			return (NULL);
374c793af95Ssangeeta 		}
375c793af95Ssangeeta 		b = 0;
376c793af95Ssangeeta 		goto keeplooking;
377c793af95Ssangeeta 
378c793af95Ssangeeta 	}
379c793af95Ssangeeta keydiff:
380c793af95Ssangeeta 	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
381c793af95Ssangeeta 	for (b = 7; (test >>= 1) > 0; )
382c793af95Ssangeeta 		b--;
383c793af95Ssangeeta keeplooking:
384c793af95Ssangeeta 	matched_off = cp - v;
385c793af95Ssangeeta 	b += matched_off << 3;
386c793af95Ssangeeta 	rn_bit = -1 - b;
387c793af95Ssangeeta 
388c793af95Ssangeeta 	/*
389c793af95Ssangeeta 	 * If there is a host route in a duped-key chain, it will be first.
390c793af95Ssangeeta 	 */
391c793af95Ssangeeta 	if ((saved_t = t)->rn_mask == 0)
392c793af95Ssangeeta 		t = t->rn_dupedkey;
393c793af95Ssangeeta 	for (; t != NULL; t = t->rn_dupedkey) {
394c793af95Ssangeeta 		/*
395c793af95Ssangeeta 		 * Even if we don't match exactly as a host,
396c793af95Ssangeeta 		 * we may match if the leaf we wound up at is
397c793af95Ssangeeta 		 * a route to a net.
398c793af95Ssangeeta 		 */
399c793af95Ssangeeta 
400c793af95Ssangeeta 		if (t->rn_flags & RNF_NORMAL) {
401c793af95Ssangeeta 			if ((rn_bit <= t->rn_bit) &&
402c793af95Ssangeeta 			    RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) {
403c793af95Ssangeeta 				return (t);
404c793af95Ssangeeta 			}
405c793af95Ssangeeta 		} else if (rn_satisfies_leaf(v, t, matched_off, rn_leaf_fn,
406c793af95Ssangeeta 		    rn_leaf_arg)) {
407c793af95Ssangeeta 			return (t);
408c793af95Ssangeeta 		}
409c793af95Ssangeeta 	}
410c793af95Ssangeeta 	t = saved_t;
411c793af95Ssangeeta 	/* start searching up the tree */
412c793af95Ssangeeta 	do {
413c793af95Ssangeeta 		struct radix_mask *m;
414c793af95Ssangeeta 
415c793af95Ssangeeta 		t = t->rn_parent;
416c793af95Ssangeeta 		m = t->rn_mklist;
417c793af95Ssangeeta 		/*
418c793af95Ssangeeta 		 * If non-contiguous masks ever become important
419c793af95Ssangeeta 		 * we can restore the masking and open coding of
420c793af95Ssangeeta 		 * the search and satisfaction test and put the
421c793af95Ssangeeta 		 * calculation of "off" back before the "do".
422c793af95Ssangeeta 		 */
423c793af95Ssangeeta 		while (m) {
424c793af95Ssangeeta 			if (m->rm_flags & RNF_NORMAL) {
425c793af95Ssangeeta 				if ((rn_bit <= m->rm_bit) &&
426c793af95Ssangeeta 				    RN_MATCHF(m->rm_leaf, rn_leaf_fn,
427c793af95Ssangeeta 				    rn_leaf_arg)) {
428c793af95Ssangeeta 					return (m->rm_leaf);
429c793af95Ssangeeta 				}
430c793af95Ssangeeta 			} else {
431c793af95Ssangeeta 				off = min(t->rn_offset, matched_off);
432c793af95Ssangeeta 				x = rn_search_m(v, t, m->rm_mask);
433c793af95Ssangeeta 				while (x != NULL && x->rn_mask != m->rm_mask)
434c793af95Ssangeeta 					x = x->rn_dupedkey;
435c793af95Ssangeeta 				if (x && rn_satisfies_leaf(v, x, off,
436c793af95Ssangeeta 				    rn_leaf_fn, rn_leaf_arg)) {
437c793af95Ssangeeta 					return (x);
438c793af95Ssangeeta 				}
439c793af95Ssangeeta 			}
440c793af95Ssangeeta 			m = m->rm_mklist;
441c793af95Ssangeeta 		}
442c793af95Ssangeeta 	} while (t != top);
443c793af95Ssangeeta 	return (0);
444c793af95Ssangeeta }
445c793af95Ssangeeta 
446c793af95Ssangeeta /*
447c793af95Ssangeeta  * Whenever we add a new leaf to the tree, we also add a parent node,
448c793af95Ssangeeta  * so we allocate them as an array of two elements: the first one must be
449c793af95Ssangeeta  * the leaf (see RNTORT() in route.c), the second one is the parent.
450c793af95Ssangeeta  * This routine initializes the relevant fields of the nodes, so that
451c793af95Ssangeeta  * the leaf is the left child of the parent node, and both nodes have
452c793af95Ssangeeta  * (almost) all all fields filled as appropriate.
453c793af95Ssangeeta  * The function returns a pointer to the parent node.
454c793af95Ssangeeta  */
455c793af95Ssangeeta 
456c793af95Ssangeeta static struct radix_node *
rn_newpair(v,b,nodes)457c793af95Ssangeeta rn_newpair(v, b, nodes)
458c793af95Ssangeeta 	void *v;
459c793af95Ssangeeta 	int b;
460c793af95Ssangeeta 	struct radix_node nodes[2];
461c793af95Ssangeeta {
462c793af95Ssangeeta 	struct radix_node *tt = nodes, *t = tt + 1;
463c793af95Ssangeeta 
464c793af95Ssangeeta 	t->rn_bit = b;
465c793af95Ssangeeta 	t->rn_bmask = 0x80 >> (b & 7);
466c793af95Ssangeeta 	t->rn_left = tt;
467c793af95Ssangeeta 	t->rn_offset = b >> 3;
468c793af95Ssangeeta 
469c793af95Ssangeeta 	/*
470c793af95Ssangeeta 	 * t->rn_parent, r->rn_right, tt->rn_mask, tt->rn_dupedkey
471c793af95Ssangeeta 	 * and tt->rn_bmask must have been zeroed by caller.
472c793af95Ssangeeta 	 */
473c793af95Ssangeeta 	tt->rn_bit = -1;
474c793af95Ssangeeta 	tt->rn_key = v;
475c793af95Ssangeeta 	tt->rn_parent = t;
476c793af95Ssangeeta 	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
477c793af95Ssangeeta 	tt->rn_mklist = t->rn_mklist = 0;
478c793af95Ssangeeta 	return (t);
479c793af95Ssangeeta }
480c793af95Ssangeeta 
481c793af95Ssangeeta static struct radix_node *
rn_insert(v_arg,head,dupentry,nodes)482c793af95Ssangeeta rn_insert(v_arg, head, dupentry, nodes)
483c793af95Ssangeeta 	void *v_arg;
484c793af95Ssangeeta 	struct radix_node_head *head;
485c793af95Ssangeeta 	int *dupentry;
486c793af95Ssangeeta 	struct radix_node nodes[2];
487c793af95Ssangeeta {
488c793af95Ssangeeta 	caddr_t v = v_arg;
489c793af95Ssangeeta 	struct radix_node *top = head->rnh_treetop;
490*bd670b35SErik Nordmark 	struct radix_node *p, *x;
491c793af95Ssangeeta 	int head_off = top->rn_offset, vlen = (int)LEN(v);
492c793af95Ssangeeta 	struct radix_node *t = rn_search(v_arg, top);
493c793af95Ssangeeta 	caddr_t cp = v + head_off;
494c793af95Ssangeeta 	int b;
495c793af95Ssangeeta 	struct radix_node *tt;
496*bd670b35SErik Nordmark 	caddr_t cp2 = t->rn_key + head_off;
497*bd670b35SErik Nordmark 	int cmp_res;
498*bd670b35SErik Nordmark 	caddr_t cplim = v + vlen;
499c793af95Ssangeeta 
500c793af95Ssangeeta 	/*
501c793af95Ssangeeta 	 * Find first bit at which v and t->rn_key differ
502c793af95Ssangeeta 	 */
503*bd670b35SErik Nordmark 	while (cp < cplim)
504*bd670b35SErik Nordmark 		if (*cp2++ != *cp++)
505*bd670b35SErik Nordmark 			goto on1;
506*bd670b35SErik Nordmark 	*dupentry = 1;
507*bd670b35SErik Nordmark 	return (t);
508c793af95Ssangeeta on1:
509*bd670b35SErik Nordmark 	*dupentry = 0;
510*bd670b35SErik Nordmark 	cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
511*bd670b35SErik Nordmark 	/*
512*bd670b35SErik Nordmark 	 * (cp - v) is the number of bytes where the match is relevant.
513