xref: /illumos-gate/usr/src/common/net/patricia/radix.c (revision 2679e103)
1c793af95Ssangeeta /*
2c793af95Ssangeeta  * Copyright 2006 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 #pragma ident	"%Z%%M%	%I%	%E% SMI"
38c793af95Ssangeeta 
39c793af95Ssangeeta /*
40c793af95Ssangeeta  * Routines to build and maintain radix trees for routing lookups.
41c793af95Ssangeeta  */
42c793af95Ssangeeta #include <sys/types.h>
43c793af95Ssangeeta 
44c793af95Ssangeeta #ifndef _RADIX_H_
45c793af95Ssangeeta #include <sys/param.h>
46c793af95Ssangeeta #ifdef	_KERNEL
47c793af95Ssangeeta #include <sys/lock.h>
48c793af95Ssangeeta #include <sys/mutex.h>
49c793af95Ssangeeta #include <sys/systm.h>
50c793af95Ssangeeta #include <sys/cmn_err.h>
51c793af95Ssangeeta #else
52c793af95Ssangeeta #include <assert.h>
53c793af95Ssangeeta #define	ASSERT assert
54c793af95Ssangeeta #include <stdio.h>
55c793af95Ssangeeta #include <stdlib.h>
56c793af95Ssangeeta #include <syslog.h>
57c793af95Ssangeeta #include <strings.h>
58c793af95Ssangeeta #endif	/* _KERNEL */
59c793af95Ssangeeta #include <net/radix.h>
60c793af95Ssangeeta #endif
61c793af95Ssangeeta 
62c793af95Ssangeeta #ifndef	_KERNEL
63c793af95Ssangeeta void
64c793af95Ssangeeta panic(const char *str)
65c793af95Ssangeeta {
66c793af95Ssangeeta 	fprintf(stderr, "Panic - %s\n", str);
67c793af95Ssangeeta 	abort();
68c793af95Ssangeeta }
69c793af95Ssangeeta #endif	/* _KERNEL */
70c793af95Ssangeeta 
71c793af95Ssangeeta static int	rn_walktree(struct radix_node_head *, walktree_f_t *, void *);
72*2679e103Ssowmini static int	rn_walktree_mt(struct radix_node_head *, walktree_f_t *,
73*2679e103Ssowmini     void *, lockf_t, lockf_t);
74c793af95Ssangeeta static struct radix_node
75c793af95Ssangeeta 	*rn_insert(void *, struct radix_node_head *, int *,
76c793af95Ssangeeta 	    struct radix_node [2]),
77c793af95Ssangeeta 	*rn_newpair(void *, int, struct radix_node[2]),
78c793af95Ssangeeta 	*rn_search(void *, struct radix_node *),
79c793af95Ssangeeta 	*rn_search_m(void *, struct radix_node *, void *),
80c793af95Ssangeeta 	*rn_lookup(void *, void *, struct radix_node_head *),
81c793af95Ssangeeta 	*rn_match(void *, struct radix_node_head *),
82c793af95Ssangeeta 	*rn_match_args(void *, struct radix_node_head *, match_leaf_t *,
83c793af95Ssangeeta 	    void *),
84c793af95Ssangeeta 	*rn_addmask(void *, int, int),
85c793af95Ssangeeta 	*rn_addroute(void *, void *, struct radix_node_head *,
86c793af95Ssangeeta 	    struct radix_node [2]),
87c793af95Ssangeeta 	*rn_delete(void *, void *, struct radix_node_head *);
88c793af95Ssangeeta static	boolean_t rn_refines(void *, void *);
89c793af95Ssangeeta 
90c793af95Ssangeeta #define	MAX_KEYLEN	16
91c793af95Ssangeeta static int	max_keylen = MAX_KEYLEN;
92c793af95Ssangeeta 
93c793af95Ssangeeta #ifdef	_KERNEL
94c793af95Ssangeeta static struct kmem_cache *radix_mask_cache; /* for rn_mkfreelist */
95c793af95Ssangeeta static struct kmem_cache *radix_node_cache;
96c793af95Ssangeeta #else
97c793af95Ssangeeta static char *radix_mask_cache, *radix_node_cache; /* dummy vars. never inited */
98c793af95Ssangeeta #endif	/* _KERNEL */
99c793af95Ssangeeta 
100c793af95Ssangeeta static struct radix_mask *rn_mkfreelist;
101c793af95Ssangeeta static struct radix_node_head *mask_rnhead;
102c793af95Ssangeeta /*
103c793af95Ssangeeta  * Work area -- the following point to 2 buffers of size max_keylen,
104c793af95Ssangeeta  * allocated in this order in a block of memory malloc'ed by rn_init.
105c793af95Ssangeeta  * A third buffer of size MAX_KEYLEN is allocated from the stack.
106c793af95Ssangeeta  */
107c793af95Ssangeeta static char *rn_zeros, *rn_ones;
108c793af95Ssangeeta 
109c793af95Ssangeeta #define	MKGet(m)  R_Malloc(m, radix_mask_cache, sizeof (struct radix_mask))
110c793af95Ssangeeta #define	MKFree(m) Free(m, radix_mask_cache)
111c793af95Ssangeeta #define	rn_masktop (mask_rnhead->rnh_treetop)
112c793af95Ssangeeta 
113c793af95Ssangeeta static boolean_t	rn_lexobetter(void *m_arg, void *n_arg);
114c793af95Ssangeeta static struct radix_mask *
115c793af95Ssangeeta 		rn_new_radix_mask(struct radix_node *tt,
116c793af95Ssangeeta 		    struct radix_mask *next);
117c793af95Ssangeeta static boolean_t
118c793af95Ssangeeta 		rn_satisfies_leaf(char *trial, struct radix_node *leaf,
119c793af95Ssangeeta 		    int skip, match_leaf_t *rn_leaf_fn, void *rn_leaf_arg);
120c793af95Ssangeeta 
121c793af95Ssangeeta #define	RN_MATCHF(rn, f, arg)	(f == NULL || (*f)((rn), arg))
122c793af95Ssangeeta 
123c793af95Ssangeeta /*
124c793af95Ssangeeta  * The data structure for the keys is a radix tree with one way
125c793af95Ssangeeta  * branching removed.  The index rn_bit at an internal node n represents a bit
126c793af95Ssangeeta  * position to be tested.  The tree is arranged so that all descendants
127c793af95Ssangeeta  * of a node n have keys whose bits all agree up to position rn_bit - 1.
128c793af95Ssangeeta  * (We say the index of n is rn_bit.)
129c793af95Ssangeeta  *
130c793af95Ssangeeta  * There is at least one descendant which has a one bit at position rn_bit,
131c793af95Ssangeeta  * and at least one with a zero there.
132c793af95Ssangeeta  *
133c793af95Ssangeeta  * A route is determined by a pair of key and mask.  We require that the
134c793af95Ssangeeta  * bit-wise logical and of the key and mask to be the key.
135c793af95Ssangeeta  * We define the index of a route associated with the mask to be
136c793af95Ssangeeta  * the first bit number in the mask where 0 occurs (with bit number 0
137c793af95Ssangeeta  * representing the highest order bit).
138c793af95Ssangeeta  *
139c793af95Ssangeeta  * We say a mask is normal if every bit is 0, past the index of the mask.
140c793af95Ssangeeta  * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
141c793af95Ssangeeta  * and m is a normal mask, then the route applies to every descendant of n.
142c793af95Ssangeeta  * If the index(m) < rn_bit, this implies the trailing last few bits of k
143c793af95Ssangeeta  * before bit b are all 0, (and hence consequently true of every descendant
144c793af95Ssangeeta  * of n), so the route applies to all descendants of the node as well.
145c793af95Ssangeeta  *
146c793af95Ssangeeta  * Similar logic shows that a non-normal mask m such that
147c793af95Ssangeeta  * index(m) <= index(n) could potentially apply to many children of n.
148c793af95Ssangeeta  * Thus, for each non-host route, we attach its mask to a list at an internal
149c793af95Ssangeeta  * node as high in the tree as we can go.
150c793af95Ssangeeta  *
151c793af95Ssangeeta  * The present version of the code makes use of normal routes in short-
152c793af95Ssangeeta  * circuiting an explict mask and compare operation when testing whether
153c793af95Ssangeeta  * a key satisfies a normal route, and also in remembering the unique leaf
154c793af95Ssangeeta  * that governs a subtree.
155c793af95Ssangeeta  */
156c793af95Ssangeeta 
157c793af95Ssangeeta /*
158c793af95Ssangeeta  * Most of the functions in this code assume that the key/mask arguments
159c793af95Ssangeeta  * are sockaddr-like structures, where the first byte is an uchar_t
160c793af95Ssangeeta  * indicating the size of the entire structure.
161c793af95Ssangeeta  *
162c793af95Ssangeeta  * To make the assumption more explicit, we use the LEN() macro to access
163c793af95Ssangeeta  * this field. It is safe to pass an expression with side effects
164c793af95Ssangeeta  * to LEN() as the argument is evaluated only once.
165c793af95Ssangeeta  */
166c793af95Ssangeeta #define	LEN(x) (*(const uchar_t *)(x))
167c793af95Ssangeeta 
168c793af95Ssangeeta 
169c793af95Ssangeeta /*
170c793af95Ssangeeta  * Search a node in the tree matching the key.
171c793af95Ssangeeta  */
172c793af95Ssangeeta static struct radix_node *
173c793af95Ssangeeta rn_search(v_arg, head)
174c793af95Ssangeeta 	void *v_arg;
175c793af95Ssangeeta 	struct radix_node *head;
176c793af95Ssangeeta {
177c793af95Ssangeeta 	struct radix_node *x;
178c793af95Ssangeeta 	caddr_t v;
179c793af95Ssangeeta 
180c793af95Ssangeeta 	for (x = head, v = v_arg; x->rn_bit >= 0; ) {
181c793af95Ssangeeta 		if (x->rn_bmask & v[x->rn_offset])
182c793af95Ssangeeta 			x = x->rn_right;
183c793af95Ssangeeta 		else
184c793af95Ssangeeta 			x = x->rn_left;
185c793af95Ssangeeta 	}
186c793af95Ssangeeta 	return (x);
187c793af95Ssangeeta }
188c793af95Ssangeeta 
189c793af95Ssangeeta /*
190c793af95Ssangeeta  * Same as above, but with an additional mask.
191c793af95Ssangeeta  */
192c793af95Ssangeeta static struct radix_node *
193c793af95Ssangeeta rn_search_m(v_arg, head, m_arg)
194c793af95Ssangeeta 	struct radix_node *head;
195c793af95Ssangeeta 	void *v_arg, *m_arg;
196c793af95Ssangeeta {
197c793af95Ssangeeta 	struct radix_node *x;
198c793af95Ssangeeta 	caddr_t v = v_arg, m = m_arg;
199c793af95Ssangeeta 
200c793af95Ssangeeta 	for (x = head; x->rn_bit >= 0; ) {
201c793af95Ssangeeta 		if ((x->rn_bmask & m[x->rn_offset]) &&
202c793af95Ssangeeta 		    (x->rn_bmask & v[x->rn_offset]))
203c793af95Ssangeeta 			x = x->rn_right;
204c793af95Ssangeeta 		else
205c793af95Ssangeeta 			x = x->rn_left;
206c793af95Ssangeeta 	}
207c793af95Ssangeeta 	return (x);
208c793af95Ssangeeta }
209c793af95Ssangeeta 
210c793af95Ssangeeta /*
211c793af95Ssangeeta  * Returns true if there are no bits set in n_arg that are zero in
212c793af95Ssangeeta  * m_arg and the masks aren't equal.  In other words, it returns true
213c793af95Ssangeeta  * when m_arg is a finer-granularity netmask -- it represents a subset
214c793af95Ssangeeta  * of the destinations implied by n_arg.
215c793af95Ssangeeta  */
216c793af95Ssangeeta static boolean_t
217c793af95Ssangeeta rn_refines(m_arg, n_arg)
218c793af95Ssangeeta 	void *m_arg, *n_arg;
219c793af95Ssangeeta {
220c793af95Ssangeeta 	caddr_t m = m_arg, n = n_arg;
221c793af95Ssangeeta 	caddr_t lim = n + LEN(n), lim2 = lim;
222c793af95Ssangeeta 	int longer = LEN(n++) - (int)LEN(m++);
223c793af95Ssangeeta 	boolean_t masks_are_equal = B_TRUE;
224c793af95Ssangeeta 
225c793af95Ssangeeta 	if (longer > 0)
226c793af95Ssangeeta 		lim -= longer;
227c793af95Ssangeeta 	while (n < lim) {
228c793af95Ssangeeta 		if (*n & ~(*m))
229c793af95Ssangeeta 			return (0);
230c793af95Ssangeeta 		if (*n++ != *m++)
231c793af95Ssangeeta 			masks_are_equal = B_FALSE;
232c793af95Ssangeeta 	}
233c793af95Ssangeeta 	while (n < lim2)
234c793af95Ssangeeta 		if (*n++)
235c793af95Ssangeeta 			return (B_FALSE);
236c793af95Ssangeeta 	if (masks_are_equal && (longer < 0))
237c793af95Ssangeeta 		for (lim2 = m - longer; m < lim2; )
238c793af95Ssangeeta 			if (*m++)
239c793af95Ssangeeta 				return (B_TRUE);
240c793af95Ssangeeta 	return (!masks_are_equal);
241c793af95Ssangeeta }
242c793af95Ssangeeta 
243c793af95Ssangeeta static struct radix_node *
244c793af95Ssangeeta rn_lookup(v_arg, m_arg, head)
245c793af95Ssangeeta 	void *v_arg, *m_arg;
246c793af95Ssangeeta 	struct radix_node_head *head;
247c793af95Ssangeeta {
248c793af95Ssangeeta 	struct radix_node *x;
249c793af95Ssangeeta 	caddr_t netmask = NULL;
250c793af95Ssangeeta 
251c793af95Ssangeeta 	if (m_arg) {
252c793af95Ssangeeta 		x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
253c793af95Ssangeeta 		if (x == NULL)
254c793af95Ssangeeta 			return (NULL);
255c793af95Ssangeeta 		netmask = x->rn_key;
256c793af95Ssangeeta 	}
257c793af95Ssangeeta 	x = rn_match(v_arg, head);
258c793af95Ssangeeta 	if (x && netmask) {
259c793af95Ssangeeta 		while (x && x->rn_mask != netmask)
260c793af95Ssangeeta 			x = x->rn_dupedkey;
261c793af95Ssangeeta 	}
262c793af95Ssangeeta 	return (x);
263c793af95Ssangeeta }
264c793af95Ssangeeta 
265c793af95Ssangeeta /*
266c793af95Ssangeeta  * Returns true if address 'trial' has no bits differing from the
267c793af95Ssangeeta  * leaf's key when compared under the leaf's mask.  In other words,
268c793af95Ssangeeta  * returns true when 'trial' matches leaf.
269c793af95Ssangeeta  * In addition, if a rn_leaf_fn is passed in, that is used to find
270c793af95Ssangeeta  * a match on conditions defined by the caller of rn_match.  This is
271c793af95Ssangeeta  * used by the kernel ftable to match on IRE_MATCH_* conditions.
272c793af95Ssangeeta  */
273c793af95Ssangeeta static boolean_t
274c793af95Ssangeeta rn_satisfies_leaf(trial, leaf, skip, rn_leaf_fn, rn_leaf_arg)
275c793af95Ssangeeta 	caddr_t trial;
276c793af95Ssangeeta 	struct radix_node *leaf;
277c793af95Ssangeeta 	int skip;
278c793af95Ssangeeta 	match_leaf_t *rn_leaf_fn;
279c793af95Ssangeeta 	void *rn_leaf_arg;
280c793af95Ssangeeta {
281c793af95Ssangeeta 	char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
282c793af95Ssangeeta 	char *cplim;
283c793af95Ssangeeta 	int length = min(LEN(cp), LEN(cp2));
284c793af95Ssangeeta 
285c793af95Ssangeeta 	if (cp3 == 0)
286c793af95Ssangeeta 		cp3 = rn_ones;
287c793af95Ssangeeta 	else
288c793af95Ssangeeta 		length = min(length, LEN(cp3));
289c793af95Ssangeeta 	cplim = cp + length;
290c793af95Ssangeeta 	cp3 += skip;
291c793af95Ssangeeta 	cp2 += skip;
292c793af95Ssangeeta 
293c793af95Ssangeeta 	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
294c793af95Ssangeeta 		if ((*cp ^ *cp2) & *cp3)
295c793af95Ssangeeta 			return (B_FALSE);
296c793af95Ssangeeta 
297c793af95Ssangeeta 	return (RN_MATCHF(leaf, rn_leaf_fn, rn_leaf_arg));
298c793af95Ssangeeta }
299c793af95Ssangeeta 
300c793af95Ssangeeta static struct radix_node *
301c793af95Ssangeeta rn_match(v_arg, head)
302c793af95Ssangeeta 	void *v_arg;
303c793af95Ssangeeta 	struct radix_node_head *head;
304c793af95Ssangeeta {
305c793af95Ssangeeta 	return (rn_match_args(v_arg, head, NULL, NULL));
306c793af95Ssangeeta }
307c793af95Ssangeeta 
308c793af95Ssangeeta static struct radix_node *
309c793af95Ssangeeta rn_match_args(v_arg, head, rn_leaf_fn, rn_leaf_arg)
310c793af95Ssangeeta 	void *v_arg;
311c793af95Ssangeeta 	struct radix_node_head *head;
312c793af95Ssangeeta 	match_leaf_t *rn_leaf_fn;
313c793af95Ssangeeta 	void *rn_leaf_arg;
314c793af95Ssangeeta {
315c793af95Ssangeeta 	caddr_t v = v_arg;
316c793af95Ssangeeta 	struct radix_node *t = head->rnh_treetop, *x;
317c793af95Ssangeeta 	caddr_t cp = v, cp2;
318c793af95Ssangeeta 	caddr_t cplim;
319c793af95Ssangeeta 	struct radix_node *saved_t, *top = t;
320c793af95Ssangeeta 	int off = t->rn_offset, vlen = LEN(cp), matched_off;
321c793af95Ssangeeta 	int test, b, rn_bit;
322c793af95Ssangeeta 
323c793af95Ssangeeta 	/*
324c793af95Ssangeeta 	 * Open code rn_search(v, top) to avoid overhead of extra
325c793af95Ssangeeta 	 * subroutine call.
326c793af95Ssangeeta 	 */
327c793af95Ssangeeta 	for (; t->rn_bit >= 0; ) {
328c793af95Ssangeeta 		if (t->rn_bmask & cp[t->rn_offset])
329c793af95Ssangeeta 			t = t->rn_right;
330c793af95Ssangeeta 		else
331c793af95Ssangeeta 			t = t->rn_left;
332c793af95Ssangeeta 	}
333c793af95Ssangeeta 	/*
334c793af95Ssangeeta 	 * See if we match exactly as a host destination
335c793af95Ssangeeta 	 * or at least learn how many bits match, for normal mask finesse.
336c793af95Ssangeeta 	 *
337c793af95Ssangeeta 	 * It doesn't hurt us to limit how many bytes to check
338c793af95Ssangeeta 	 * to the length of the mask, since if it matches we had a genuine
339c793af95Ssangeeta 	 * match and the leaf we have is the most specific one anyway;
340c793af95Ssangeeta 	 * if it didn't match with a shorter length it would fail
341c793af95Ssangeeta 	 * with a long one.  This wins big for class B&C netmasks which
342c793af95Ssangeeta 	 * are probably the most common case...
343c793af95Ssangeeta 	 */
344c793af95Ssangeeta 	if (t->rn_mask)
345c793af95Ssangeeta 		vlen = LEN(t->rn_mask);
346c793af95Ssangeeta 	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
347c793af95Ssangeeta 	for (; cp < cplim; cp++, cp2++)
348c793af95Ssangeeta 		if (*cp != *cp2)
349c793af95Ssangeeta 			goto keydiff;
350c793af95Ssangeeta 	/*
351c793af95Ssangeeta 	 * This extra grot is in case we are explicitly asked
352c793af95Ssangeeta 	 * to look up the default.  Ugh!
353c793af95Ssangeeta 	 *
354c793af95Ssangeeta 	 * Never return the root node itself, it seems to cause a
355c793af95Ssangeeta 	 * lot of confusion.
356c793af95Ssangeeta 	 */
357c793af95Ssangeeta 	if (t->rn_flags & RNF_ROOT)
358c793af95Ssangeeta 		t = t->rn_dupedkey;
359c793af95Ssangeeta 	if (t == NULL || RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) {
360c793af95Ssangeeta 		return (t);
361c793af95Ssangeeta 	} else {
362c793af95Ssangeeta 		/*
363c793af95Ssangeeta 		 * Although we found an exact match on the key, rn_leaf_fn
364c793af95Ssangeeta 		 * is looking for some other criteria as well. Continue
365c793af95Ssangeeta 		 * looking as if the exact match failed.
366c793af95Ssangeeta 		 */
367c793af95Ssangeeta 		if (t->rn_parent->rn_flags & RNF_ROOT) {
368c793af95Ssangeeta 			/* hit the top. have to give up */
369c793af95Ssangeeta 			return (NULL);
370c793af95Ssangeeta 		}
371c793af95Ssangeeta 		b = 0;
372c793af95Ssangeeta 		goto keeplooking;
373c793af95Ssangeeta 
374c793af95Ssangeeta 	}
375c793af95Ssangeeta keydiff:
376c793af95Ssangeeta 	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
377c793af95Ssangeeta 	for (b = 7; (test >>= 1) > 0; )
378c793af95Ssangeeta 		b--;
379c793af95Ssangeeta keeplooking:
380c793af95Ssangeeta 	matched_off = cp - v;
381c793af95Ssangeeta 	b += matched_off << 3;
382c793af95Ssangeeta 	rn_bit = -1 - b;
383c793af95Ssangeeta 
384c793af95Ssangeeta 	/*
385c793af95Ssangeeta 	 * If there is a host route in a duped-key chain, it will be first.
386c793af95Ssangeeta 	 */
387c793af95Ssangeeta 	if ((saved_t = t)->rn_mask == 0)
388c793af95Ssangeeta 		t = t->rn_dupedkey;
389c793af95Ssangeeta 	for (; t != NULL; t = t->rn_dupedkey) {
390c793af95Ssangeeta 		/*
391c793af95Ssangeeta 		 * Even if we don't match exactly as a host,
392c793af95Ssangeeta 		 * we may match if the leaf we wound up at is
393c793af95Ssangeeta 		 * a route to a net.
394c793af95Ssangeeta 		 */
395c793af95Ssangeeta 
396c793af95Ssangeeta 		if (t->rn_flags & RNF_NORMAL) {
397c793af95Ssangeeta 			if ((rn_bit <= t->rn_bit) &&
398c793af95Ssangeeta 			    RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) {
399c793af95Ssangeeta 				return (t);
400c793af95Ssangeeta 			}
401c793af95Ssangeeta 		} else if (rn_satisfies_leaf(v, t, matched_off, rn_leaf_fn,
402c793af95Ssangeeta 		    rn_leaf_arg)) {
403c793af95Ssangeeta 			return (t);
404c793af95Ssangeeta 		}
405c793af95Ssangeeta 	}
406c793af95Ssangeeta 	t = saved_t;
407c793af95Ssangeeta 	/* start searching up the tree */
408c793af95Ssangeeta 	do {
409c793af95Ssangeeta 		struct radix_mask *m;
410c793af95Ssangeeta 
411c793af95Ssangeeta 		t = t->rn_parent;
412c793af95Ssangeeta 		m = t->rn_mklist;
413c793af95Ssangeeta 		/*
414c793af95Ssangeeta 		 * If non-contiguous masks ever become important
415c793af95Ssangeeta 		 * we can restore the masking and open coding of
416c793af95Ssangeeta 		 * the search and satisfaction test and put the
417c793af95Ssangeeta 		 * calculation of "off" back before the "do".
418c793af95Ssangeeta 		 */
419c793af95Ssangeeta 		while (m) {
420c793af95Ssangeeta 			if (m->rm_flags & RNF_NORMAL) {
421c793af95Ssangeeta 				if ((rn_bit <= m->rm_bit) &&
422c793af95Ssangeeta 				    RN_MATCHF(m->rm_leaf, rn_leaf_fn,
423c793af95Ssangeeta 				    rn_leaf_arg)) {
424c793af95Ssangeeta 					return (m->rm_leaf);
425c793af95Ssangeeta 				}
426c793af95Ssangeeta 			} else {
427c793af95Ssangeeta 				off = min(t->rn_offset, matched_off);
428c793af95Ssangeeta 				x = rn_search_m(v, t, m->rm_mask);
429c793af95Ssangeeta 				while (x != NULL && x->rn_mask != m->rm_mask)
430c793af95Ssangeeta 					x = x->rn_dupedkey;
431c793af95Ssangeeta 				if (x && rn_satisfies_leaf(v, x, off,
432c793af95Ssangeeta 				    rn_leaf_fn, rn_leaf_arg)) {
433c793af95Ssangeeta 					return (x);
434c793af95Ssangeeta 				}
435c793af95Ssangeeta 			}
436c793af95Ssangeeta 			m = m->rm_mklist;
437c793af95Ssangeeta 		}
438c793af95Ssangeeta 	} while (t != top);
439c793af95Ssangeeta 	return (0);
440c793af95Ssangeeta }
441c793af95Ssangeeta 
442c793af95Ssangeeta /*
443c793af95Ssangeeta  * Whenever we add a new leaf to the tree, we also add a parent node,
444c793af95Ssangeeta  * so we allocate them as an array of two elements: the first one must be
445c793af95Ssangeeta  * the leaf (see RNTORT() in route.c), the second one is the parent.
446c793af95Ssangeeta  * This routine initializes the relevant fields of the nodes, so that
447c793af95Ssangeeta  * the leaf is the left child of the parent node, and both nodes have
448c793af95Ssangeeta  * (almost) all all fields filled as appropriate.
449c793af95Ssangeeta  * The function returns a pointer to the parent node.
450c793af95Ssangeeta  */
451c793af95Ssangeeta 
452c793af95Ssangeeta static struct radix_node *
453c793af95Ssangeeta rn_newpair(v, b, nodes)
454c793af95Ssangeeta 	void *v;
455c793af95Ssangeeta 	int b;
456c793af95Ssangeeta 	struct radix_node nodes[2];
457c793af95Ssangeeta {
458c793af95Ssangeeta 	struct radix_node *tt = nodes, *t = tt + 1;
459c793af95Ssangeeta 
460c793af95Ssangeeta 	t->rn_bit = b;
461c793af95Ssangeeta 	t->rn_bmask = 0x80 >> (b & 7);
462c793af95Ssangeeta 	t->rn_left = tt;
463c793af95Ssangeeta 	t->rn_offset = b >> 3;
464c793af95Ssangeeta 
465c793af95Ssangeeta 	/*
466c793af95Ssangeeta 	 * t->rn_parent, r->rn_right, tt->rn_mask, tt->rn_dupedkey
467c793af95Ssangeeta 	 * and tt->rn_bmask must have been zeroed by caller.
468c793af95Ssangeeta 	 */
469c793af95Ssangeeta 	tt->rn_bit = -1;
470c793af95Ssangeeta 	tt->rn_key = v;
471c793af95Ssangeeta 	tt->rn_parent = t;
472c793af95Ssangeeta 	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
473c793af95Ssangeeta 	tt->rn_mklist = t->rn_mklist = 0;
474c793af95Ssangeeta 	return (t);
475c793af95Ssangeeta }
476c793af95Ssangeeta 
477c793af95Ssangeeta static struct radix_node *
478c793af95Ssangeeta rn_insert(v_arg, head, dupentry, nodes)
479c793af95Ssangeeta 	void *v_arg;
480c793af95Ssangeeta 	struct radix_node_head *head;
481c793af95Ssangeeta 	int *dupentry;
482c793af95Ssangeeta 	struct radix_node nodes[2];
483c793af95Ssangeeta {
484c793af95Ssangeeta 	caddr_t v = v_arg;
485c793af95Ssangeeta 	struct radix_node *top = head->rnh_treetop;
486c793af95Ssangeeta 	int head_off = top->rn_offset, vlen = (int)LEN(v);
487c793af95Ssangeeta 	struct radix_node *t = rn_search(v_arg, top);
488c793af95Ssangeeta 	caddr_t cp = v + head_off;
489c793af95Ssangeeta 	int b;
490c793af95Ssangeeta 	struct radix_node *tt;
491c793af95Ssangeeta 
492c793af95Ssangeeta 	/*
493c793af95Ssangeeta 	 * Find first bit at which v and t->rn_key differ
494c793af95Ssangeeta 	 */
495c793af95Ssangeeta 	{
496c793af95Ssangeeta 		caddr_t cp2 = t->rn_key + head_off;
497c793af95Ssangeeta 		int cmp_res;
498c793af95Ssangeeta 		caddr_t cplim = v + vlen;
499c793af95Ssangeeta 
500c793af95Ssangeeta 		while (cp < cplim)
501c793af95Ssangeeta 			if (*cp2++ != *cp++)
502c793af95Ssangeeta 				goto on1;
503c793af95Ssangeeta 		*dupentry = 1;
504c793af95Ssangeeta 		return (t);
505c793af95Ssangeeta on1:
506c793af95Ssangeeta 		*dupentry = 0;
507c793af95Ssangeeta 		cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
508c793af95Ssangeeta 		for (b = (cp - v) << 3; cmp_res; b--)
509c793af95Ssangeeta 			cmp_res >>= 1;
510c793af95Ssangeeta 	}
511c793af95Ssangeeta 	{
512c793af95Ssangeeta 		struct radix_node *p, *x = top;
513c793af95Ssangeeta 		cp = v;
514c793af95Ssangeeta 		do {
515c793af95Ssangeeta 			p = x;
516c793af95Ssangeeta 			if (cp[x->rn_offset] & x->rn_bmask)
517c793af95Ssangeeta 				x = x->rn_right;
518c793af95Ssangeeta 			else
519c793af95Ssangeeta 				x = x->rn_left;
520c793af95Ssangeeta 		} while (b > (unsigned)x->rn_bit);
521c793af95Ssangeeta 				/* x->rn_bit < b && x->rn_bit >= 0 */
522c793af95Ssangeeta 		t = rn_newpair(v_arg, b, nodes);
523c793af95Ssangeeta 		tt = t->rn_left;
524c793af95Ssangeeta 		if ((cp[p->rn_offset] & p->rn_bmask) == 0)
525c793af95Ssangeeta 			p->rn_left = t;
526c793af95Ssangeeta 		else
527c793af95Ssangeeta 			p->rn_right = t;
528c793af95Ssangeeta 		x->rn_parent = t;
529c793af95Ssangeeta 		t->rn_parent = p;
530c793af95Ssangeeta 		if ((cp[t->rn_offset] & t->rn_bmask) == 0) {
531c793af95Ssangeeta 			t->rn_right = x;
532c793af95Ssangeeta 		} else {
533c793af95Ssangeeta 			t->rn_right = tt;
534c793af95Ssangeeta 			t->rn_left = x;
535c793af95Ssangeeta 		}
536c793af95Ssangeeta 	}
537c793af95Ssangeeta 	return (tt);
538c793af95Ssangeeta }
539c793af95Ssangeeta 
540c793af95Ssangeeta static struct radix_node *
541c793af95Ssangeeta rn_addmask(n_arg, search, skip)
542c793af95Ssangeeta 	int search, skip;
543c793af95Ssangeeta 	void *n_arg;
544c793af95Ssangeeta {
545c793af95Ssangeeta 	caddr_t netmask = (caddr_t)n_arg;
546c793af95Ssangeeta 	struct radix_node *x;
547c793af95Ssangeeta 	caddr_t cp, cplim;
548c793af95Ssangeeta 	int b = 0, mlen, j;
549c793af95Ssangeeta 	int maskduplicated, m0, isnormal;
550c793af95Ssangeeta 	struct radix_node *saved_x;
551c793af95Ssangeeta 	int last_zeroed = 0;
552c793af95Ssangeeta 	char addmask_key[MAX_KEYLEN];
553c793af95Ssangeeta 
554c793af95Ssangeeta 	if ((mlen = LEN(netmask)) > max_keylen)
555c793af95Ssangeeta 		mlen = max_keylen;
556c793af95Ssangeeta 	if (skip == 0)
557c793af95Ssangeeta 		skip = 1;
558c793af95Ssangeeta 	if (mlen <= skip)
559c793af95Ssangeeta 		return (mask_rnhead->rnh_nodes);
560c793af95Ssangeeta 	if (skip > 1)
561c793af95Ssangeeta 		bcopy(rn_ones + 1, addmask_key + 1, skip - 1);
562c793af95Ssangeeta 	if ((m0 = mlen) > skip)
563c793af95Ssangeeta 		bcopy(netmask + skip, addmask_key + skip, mlen - skip);
564c793af95Ssangeeta 	/*
565c793af95Ssangeeta 	 * Trim trailing zeroes.
566c793af95Ssangeeta 	 */
567c793af95Ssangeeta 	for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0; )
568c793af95Ssangeeta 		cp--;
569c793af95Ssangeeta 	mlen = cp - addmask_key;
570c793af95Ssangeeta 	if (mlen <= skip) {
571c793af95Ssangeeta 		if (m0 >= last_zeroed)
572c793af95Ssangeeta 			last_zeroed = mlen;
573c793af95Ssangeeta 		return (mask_rnhead->rnh_nodes);
574c793af95Ssangeeta 	}
575c793af95Ssangeeta 	if (m0 < last_zeroed)
576c793af95Ssangeeta 		bzero(addmask_key + m0, last_zeroed - m0);
577c793af95Ssangeeta 	*addmask_key = last_zeroed = mlen;
578c793af95Ssangeeta 	x = rn_search(addmask_key, rn_masktop);
579c793af95Ssangeeta 	if (bcmp(addmask_key, x->rn_key, mlen) != 0)
580c793af95Ssangeeta 		x = 0;
581c793af95Ssangeeta 	if (x || search)
582c793af95Ssangeeta 		return (x);
583c793af95Ssangeeta 	R_Zalloc(x, radix_node_cache, max_keylen + 2 * sizeof (*x));
584c793af95Ssangeeta 
585c793af95Ssangeeta 	if ((saved_x = x) == 0)
586c793af95Ssangeeta 		return (0);
587c793af95Ssangeeta 	netmask = cp = (caddr_t)(x + 2);
588c793af95Ssangeeta 	bcopy(addmask_key, cp, mlen);
589c793af95Ssangeeta 	x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
590c793af95Ssangeeta 	if (maskduplicated) {
591c793af95Ssangeeta #ifdef	_KERNEL
592c793af95Ssangeeta 		cmn_err(CE_WARN, "rn_addmask: mask impossibly already in tree");
593c793af95Ssangeeta #else
594c793af95Ssangeeta 		syslog(LOG_ERR, "rn_addmask: mask impossibly already in tree");
595c793af95Ssangeeta #endif	/* _KERNEL */
596c793af95Ssangeeta 		Free(saved_x, radix_node_cache);
597c793af95Ssangeeta 		return (x);
598c793af95Ssangeeta 	}
599c793af95Ssangeeta 	/*
600c793af95Ssangeeta 	 * Calculate index of mask, and check for normalcy.
601c793af95Ssangeeta 	 * First find the first byte with a 0 bit, then if there are
602c793af95Ssangeeta 	 * more bits left (remember we already trimmed the trailing 0's),
603c793af95Ssangeeta 	 * the pattern must be one of those in normal_chars[], or we have
604c793af95Ssangeeta 	 * a non-contiguous mask.
605c793af95Ssangeeta 	 */
606c793af95Ssangeeta 	cplim = netmask + mlen;
607c793af95Ssangeeta 	isnormal = 1;
608c793af95Ssangeeta 	for (cp = netmask + skip; (cp < cplim) && *(uchar_t *)cp == 0xff; )
609c793af95Ssangeeta 		cp++;
610c793af95Ssangeeta 	if (cp != cplim) {
611c793af95Ssangeeta 		static uint8_t normal_chars[] = {
612c793af95Ssangeeta 			0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};
613c793af95Ssangeeta 
614c793af95Ssangeeta 		for (j = 0x80; (j & *cp) != 0; j >>= 1)
615c793af95Ssangeeta 			b++;
616c793af95Ssangeeta 		if (*cp != normal_chars[b] || cp != (cplim - 1))
617c793af95Ssangeeta 			isnormal = 0;
618c793af95Ssangeeta 	}
619c793af95Ssangeeta 	b += (cp - netmask) << 3;
620c793af95Ssangeeta 	x->rn_bit = -1 - b;
621c793af95Ssangeeta 	if (isnormal)
622c793af95Ssangeeta 		x->rn_flags |= RNF_NORMAL;
623c793af95Ssangeeta 	return (x);
624c793af95Ssangeeta }
625c793af95Ssangeeta 
626c793af95Ssangeeta /* arbitrary ordering for non-contiguous masks */
627c793af95Ssangeeta static boolean_t
628c793af95Ssangeeta rn_lexobetter(m_arg, n_arg)
629c793af95Ssangeeta 	void *m_arg, *n_arg;
630c793af95Ssangeeta {
631c793af95Ssangeeta 	uchar_t *mp = m_arg, *np = n_arg, *lim;
632c793af95Ssangeeta 
633c793af95Ssangeeta 	if (LEN(mp) > LEN(np))
634c793af95Ssangeeta 		/* not really, but need to check longer one first */
635c793af95Ssangeeta 		return (B_TRUE);
636c793af95Ssangeeta 	if (LEN(mp) == LEN(np))
637c793af95Ssangeeta 		for (lim = mp + LEN(mp); mp < lim; )
638c793af95Ssangeeta 			if (*mp++ > *np++)
639c793af95Ssangeeta 				return (B_TRUE);
640c793af95Ssangeeta 	return (B_FALSE);
641c793af95Ssangeeta }
642c793af95Ssangeeta 
643c793af95Ssangeeta static struct radix_mask *
644c793af95Ssangeeta rn_new_radix_mask(tt, next)
645c793af95Ssangeeta 	struct radix_node *tt;
646c793af95Ssangeeta 	struct radix_mask *next;
647c793af95Ssangeeta {
648c793af95Ssangeeta 	struct radix_mask *m;
649c793af95Ssangeeta 
650c793af95Ssangeeta 	MKGet(m);
651c793af95Ssangeeta 	if (m == 0) {
652c793af95Ssangeeta #ifndef	_KERNEL
653c793af95Ssangeeta 		syslog(LOG_ERR, "Mask for route not entered\n");
654c793af95Ssangeeta #endif	/* _KERNEL */
655c793af95Ssangeeta 		return (0);
656c793af95Ssangeeta 	}
657c793af95Ssangeeta 	bzero(m, sizeof (*m));
658c793af95Ssangeeta 	m->rm_bit = tt->rn_bit;
659c793af95Ssangeeta 	m->rm_flags = tt->rn_flags;
660c793af95Ssangeeta 	if (tt->rn_flags & RNF_NORMAL)
661c793af95Ssangeeta 		m->rm_leaf = tt;
662c793af95Ssangeeta 	else
663c793af95Ssangeeta 		m->rm_mask = tt->rn_mask;
664c793af95Ssangeeta 	m->rm_mklist = next;
665c793af95Ssangeeta 	tt->rn_mklist = m;
666c793af95Ssangeeta 	return (m);
667c793af95Ssangeeta }
668c793af95Ssangeeta 
669c793af95Ssangeeta static struct radix_node *
670c793af95Ssangeeta rn_addroute(v_arg, n_arg, head, treenodes)
671c793af95Ssangeeta 	void *v_arg, *n_arg;
672c793af95Ssangeeta 	struct radix_node_head *head;
673c793af95Ssangeeta 	struct radix_node treenodes[2];
674c793af95Ssangeeta {
675c793af95Ssangeeta 	caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
676c793af95Ssangeeta 	struct radix_node *t, *x = 0, *tt;
677c793af95Ssangeeta 	struct radix_node *saved_tt, *top = head->rnh_treetop;
678c793af95Ssangeeta 	short b = 0, b_leaf = 0;
679c793af95Ssangeeta 	int keyduplicated;
680c793af95Ssangeeta 	caddr_t mmask;
681c793af95Ssangeeta 	struct radix_mask *m, **mp;
682c793af95Ssangeeta 
683c793af95Ssangeeta 	/*
684c793af95Ssangeeta 	 * In dealing with non-contiguous masks, there may be
685c793af95Ssangeeta 	 * many different routes which have the same mask.
686c793af95Ssangeeta 	 * We will find it useful to have a unique pointer to
687c793af95Ssangeeta 	 * the mask to speed avoiding duplicate references at
688c793af95Ssangeeta 	 * nodes and possibly save time in calculating indices.
689c793af95Ssangeeta 	 */
690c793af95Ssangeeta 	if (netmask)  {
691c793af95Ssangeeta 		if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)
692c793af95Ssangeeta 			return (0);
693c793af95Ssangeeta 		b_leaf = x->rn_bit;
694c793af95Ssangeeta 		b = -1 - x->rn_bit;
695c793af95Ssangeeta 		netmask = x->rn_key;
696c793af95Ssangeeta 	}
697c793af95Ssangeeta 	/*
698c793af95Ssangeeta 	 * Deal with duplicated keys: attach node to previous instance
699c793af95Ssangeeta 	 */
700c793af95Ssangeeta 	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
701c793af95Ssangeeta 	if (keyduplicated) {
702c793af95Ssangeeta 		for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
703c793af95Ssangeeta 			if (tt->rn_mask == netmask)
704c793af95Ssangeeta 				return (0);
705c793af95Ssangeeta 			if (netmask == 0 ||
706c793af95Ssangeeta 			    (tt->rn_mask &&
707c793af95Ssangeeta 			    /* index (netmask) > node */
708c793af95Ssangeeta 			    ((b_leaf < tt->rn_bit) ||
709c793af95Ssangeeta 			    rn_refines(netmask, tt->rn_mask) ||
710c793af95Ssangeeta 			    rn_lexobetter(netmask, tt->rn_mask))))
711c793af95Ssangeeta 				break;
712c793af95Ssangeeta 		}
713c793af95Ssangeeta 		/*
714c793af95Ssangeeta 		 * If the mask is not duplicated, we wouldn't
715c793af95Ssangeeta 		 * find it among possible duplicate key entries
716c793af95Ssangeeta 		 * anyway, so the above test doesn't hurt.
717c793af95Ssangeeta 		 *
718c793af95Ssangeeta 		 * We sort the masks for a duplicated key the same way as
719c793af95Ssangeeta 		 * in a masklist -- most specific to least specific.
720c793af95Ssangeeta 		 * This may require the unfortunate nuisance of relocating
721c793af95Ssangeeta 		 * the head of the list.
722c793af95Ssangeeta 		 *
723c793af95Ssangeeta 		 * We also reverse, or doubly link the list through the
724c793af95Ssangeeta 		 * parent pointer.
725c793af95Ssangeeta 		 */
726c793af95Ssangeeta 		if (tt == saved_tt) {
727c793af95Ssangeeta 			struct	radix_node *xx = x;
728c793af95Ssangeeta 			/* link in at head of list */
729c793af95Ssangeeta 			(tt = treenodes)->rn_dupedkey = t;
730c793af95Ssangeeta 			tt->rn_flags = t->rn_flags;
731c793af95Ssangeeta 			tt->rn_parent = x = t->rn_parent;
732c793af95Ssangeeta 			t->rn_parent = tt; /* parent */
733c793af95Ssangeeta 			if (x->rn_left == t)
734c793af95Ssangeeta 				x->rn_left = tt;
735c793af95Ssangeeta 			else
736c793af95Ssangeeta 				x->rn_right = tt;
737c793af95Ssangeeta 			saved_tt = tt; x = xx;
738c793af95Ssangeeta 		} else {
739c793af95Ssangeeta 			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
740c793af95Ssangeeta 			t->rn_dupedkey = tt;
741c793af95Ssangeeta 			/* Set rn_parent value for tt and tt->rn_dupedkey */
742c793af95Ssangeeta 			tt->rn_parent = t;
743c793af95Ssangeeta 			if (tt->rn_dupedkey)
744c793af95Ssangeeta 				tt->rn_dupedkey->rn_parent = tt;
745c793af95Ssangeeta 		}
746c793af95Ssangeeta 		tt->rn_key = v;
747c793af95Ssangeeta 		tt->rn_bit = -1;
748c793af95Ssangeeta 		tt->rn_flags = RNF_ACTIVE;
749c793af95Ssangeeta 	}
750c793af95Ssangeeta 	/*
751c793af95Ssangeeta 	 * Put mask in tree.
752c793af95Ssangeeta 	 */
753c793af95Ssangeeta 	if (netmask) {
754c793af95Ssangeeta 		tt->rn_mask = netmask;
755c793af95Ssangeeta 		tt->rn_bit = x->rn_bit;
756c793af95Ssangeeta 		tt->rn_flags |= x->rn_flags & RNF_NORMAL;
757c793af95Ssangeeta 	}
758c793af95Ssangeeta 	t = saved_tt->rn_parent;
759c793af95Ssangeeta 	if (keyduplicated)
760c793af95Ssangeeta 		goto key_exists;
761c793af95Ssangeeta 	b_leaf = -1 - t->rn_bit;
762c793af95Ssangeeta 	if (t->rn_right == saved_tt)
763c793af95Ssangeeta 		x = t->rn_left;
764c793af95Ssangeeta 	else
765c793af95Ssangeeta 		x = t->rn_right;
766c793af95Ssangeeta 	/* Promote general routes from below */
767c793af95Ssangeeta 	if (x->rn_bit < 0) {
768c793af95Ssangeeta 	    for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
769c793af95Ssangeeta 		if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
770c793af95Ssangeeta 			*mp = m = rn_new_radix_mask(x, 0);
771c793af95Ssangeeta 			if (m)
772c793af95Ssangeeta 				mp = &m->rm_mklist;
773c793af95Ssangeeta 		}
774c793af95Ssangeeta 	} else if (x->rn_mklist) {
775c793af95Ssangeeta 		/*
776c793af95Ssangeeta 		 * Skip over masks whose index is > that of new node
777c793af95Ssangeeta 		 */
778c793af95Ssangeeta 		for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
779c793af95Ssangeeta 			if (m->rm_bit >= b_leaf)
780c793af95Ssangeeta 				break;
781c793af95Ssangeeta 		t->rn_mklist = m; *mp = 0;
782c793af95Ssangeeta 	}
783c793af95Ssangeeta key_exists:
784c793af95Ssangeeta 	/* Add new route to highest possible ancestor's list */
785c793af95Ssangeeta 	if ((netmask == 0) || (b > t->rn_bit))
786c793af95Ssangeeta 		return (tt); /* can't lift at all */
787c793af95Ssangeeta 	b_leaf = tt->rn_bit;
788c793af95Ssangeeta 	do {
789c793af95Ssangeeta 		x = t;
790c793af95Ssangeeta 		t = t->rn_parent;
791c793af95Ssangeeta 	} while (b <= t->rn_bit && x != top);
792c793af95Ssangeeta 	/*
793c793af95Ssangeeta 	 * Search through routes associated with node to
794c793af95Ssangeeta 	 * insert new route according to index.
795c793af95Ssangeeta 	 * Need same criteria as when sorting dupedkeys to avoid
796c793af95Ssangeeta 	 * double loop on deletion.
797c793af95Ssangeeta 	 */
798c793af95Ssangeeta 	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) {
799c793af95Ssangeeta 		if (m->rm_bit < b_leaf)
800c793af95Ssangeeta 			continue;
801c793af95Ssangeeta 		if (m->rm_bit > b_leaf)
802c793af95Ssangeeta 			break;
803c793af95Ssangeeta 		if (m->rm_flags & RNF_NORMAL) {
804c793af95Ssangeeta 			mmask = m->rm_leaf->rn_mask;
805c793af95Ssangeeta 			if (tt->rn_flags & RNF_NORMAL) {
806c793af95Ssangeeta #ifdef	_KERNEL
807c793af95Ssangeeta 				cmn_err(CE_WARN, "Non-unique normal route, "
808c793af95Ssangeeta 				    "mask not entered\n");
809c793af95Ssangeeta #else
810c793af95Ssangeeta 				syslog(LOG_ERR, "Non-unique normal route, "
811c793af95Ssangeeta 				    "mask not entered\n");
812c793af95Ssangeeta #endif	/* _KERNEL */
813c793af95Ssangeeta 				return (tt);
814c793af95Ssangeeta 			}
815c793af95Ssangeeta 		} else
816c793af95Ssangeeta 			mmask = m->rm_mask;
817c793af95Ssangeeta 		if (mmask == netmask) {
818c793af95Ssangeeta 			m->rm_refs++;
819c793af95Ssangeeta 			tt->rn_mklist = m;
820c793af95Ssangeeta 			return (tt);
821c793af95Ssangeeta 		}
822c793af95Ssangeeta 		if (rn_refines(netmask, mmask) ||
823c793af95Ssangeeta 		    rn_lexobetter(netmask, mmask))
824c793af95Ssangeeta 			break;
825c793af95Ssangeeta 	}
826c793af95Ssangeeta 	*mp = rn_new_radix_mask(tt, *mp);
827c793af95Ssangeeta 	return (tt);
828c793af95Ssangeeta }
829c793af95Ssangeeta 
830c793af95Ssangeeta static struct radix_node *
831c793af95Ssangeeta rn_delete(v_arg, netmask_arg, head)
832c793af95Ssangeeta 	void *v_arg, *netmask_arg;
833c793af95Ssangeeta 	struct radix_node_head *head;
834c793af95Ssangeeta {
835c793af95Ssangeeta 	struct radix_node *t, *p, *x, *tt;
836c793af95Ssangeeta 	struct radix_mask *m, *saved_m, **mp;
837c793af95Ssangeeta 	struct radix_node *dupedkey, *saved_tt, *top;
838c793af95Ssangeeta 	caddr_t v, netmask;
839c793af95Ssangeeta 	int b, head_off, vlen;
840c793af95Ssangeeta 
841c793af95Ssangeeta 	v = v_arg;
842c793af95Ssangeeta 	netmask = netmask_arg;
843c793af95Ssangeeta 	x = head->rnh_treetop;
844c793af95Ssangeeta 	tt = rn_search(v, x);
845c793af95Ssangeeta 	head_off = x->rn_offset;
846c793af95Ssangeeta 	vlen =  LEN(v);
847c793af95Ssangeeta 	saved_tt = tt;
848c793af95Ssangeeta 	top = x;
849c793af95Ssangeeta 	if (tt == 0 ||
850c793af95Ssangeeta 	    bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
851c793af95Ssangeeta 		return (0);
852c793af95Ssangeeta 	/*
853c793af95Ssangeeta 	 * Delete our route from mask lists.
854c793af95Ssangeeta 	 */
855c793af95Ssangeeta 	if (netmask) {
856c793af95Ssangeeta 		if ((x = rn_addmask(netmask, 1, head_off)) == 0)
857c793af95Ssangeeta 			return (0);
858c793af95Ssangeeta 		netmask = x->rn_key;
859c793af95Ssangeeta 		while (tt->rn_mask != netmask)
860c793af95Ssangeeta 			if ((tt = tt->rn_dupedkey) == 0)
861c793af95Ssangeeta 				return (0);
862c793af95Ssangeeta 	}
863c793af95Ssangeeta 	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
864c793af95Ssangeeta 		goto on1;
865c793af95Ssangeeta 	if (tt->rn_flags & RNF_NORMAL) {
866c793af95Ssangeeta 		if (m->rm_leaf != tt || m->rm_refs > 0) {
867c793af95Ssangeeta #ifdef	_KERNEL
868c793af95Ssangeeta 			cmn_err(CE_WARN,
869c793af95Ssangeeta 			    "rn_delete: inconsistent annotation\n");
870c793af95Ssangeeta #else
871c793af95Ssangeeta 			syslog(LOG_ERR, "rn_delete: inconsistent annotation\n");
872c793af95Ssangeeta #endif	/* _KERNEL */
873c793af95Ssangeeta 			return (0);  /* dangling ref could cause disaster */
874c793af95Ssangeeta 		}
875c793af95Ssangeeta 	} else {
876c793af95Ssangeeta 		if (m->rm_mask != tt->rn_mask) {
877c793af95Ssangeeta #ifdef	_KERNEL
878c793af95Ssangeeta 			cmn_err(CE_WARN,
879c793af95Ssangeeta 			    "rn_delete: inconsistent annotation 2\n");
880c793af95Ssangeeta #else
881c793af95Ssangeeta 			syslog(LOG_ERR,
882c793af95Ssangeeta 			    "rn_delete: inconsistent annotation 2\n");
883c793af95Ssangeeta #endif	/* _KERNEL */
884c793af95Ssangeeta 			goto on1;
885c793af95Ssangeeta 		}
886c793af95Ssangeeta 		if (--m->rm_refs >= 0)
887c793af95Ssangeeta 			goto on1;
888c793af95Ssangeeta 	}
889c793af95Ssangeeta 	b = -1 - tt->rn_bit;
890c793af95Ssangeeta 	t = saved_tt->rn_parent;
891c793af95Ssangeeta 	if (b > t->rn_bit)
892c793af95Ssangeeta 		goto on1; /* Wasn't lifted at all */
893c793af95Ssangeeta 	do {
894c793af95Ssangeeta 		x = t;
895c793af95Ssangeeta 		t = t->rn_parent;
896c793af95Ssangeeta 	} while (b <= t->rn_bit && x != top);
897c793af95Ssangeeta 	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
898c793af95Ssangeeta 		if (m == saved_m) {
899c793af95Ssangeeta 			*mp = m->rm_mklist;
900c793af95Ssangeeta 			MKFree(m);
901c793af95Ssangeeta 			break;
902c793af95Ssangeeta 		}
903c793af95Ssangeeta 	if (m == 0) {
904c793af95Ssangeeta #ifdef	_KERNEL
905c793af95Ssangeeta 		cmn_err(CE_WARN, "rn_delete: couldn't find our annotation\n");
906c793af95Ssangeeta #else
907c793af95Ssangeeta 		syslog(LOG_ERR, "rn_delete: couldn't find our annotation\n");
908c793af95Ssangeeta #endif	/* _KERNEL */
909c793af95Ssangeeta 		if (tt->rn_flags & RNF_NORMAL)
910c793af95Ssangeeta 			return (0); /* Dangling ref to us */
911c793af95Ssangeeta 	}
912c793af95Ssangeeta on1:
913c793af95Ssangeeta 	/*
914c793af95Ssangeeta 	 * Eliminate us from tree
915c793af95Ssangeeta 	 */
916c793af95Ssangeeta 	if (tt->rn_flags & RNF_ROOT)
917c793af95Ssangeeta 		return (0);
918c793af95Ssangeeta 	t = tt->rn_parent;
919c793af95Ssangeeta 	dupedkey = saved_tt->rn_dupedkey;
920c793af95Ssangeeta 	if (dupedkey) {
921c793af95Ssangeeta 		/*
922c793af95Ssangeeta 		 * Here, tt is the deletion target and
923c793af95Ssangeeta 		 * saved_tt is the head of the dupekey chain.
924c793af95Ssangeeta 		 */
925c793af95Ssangeeta 		if (tt == saved_tt) {
926c793af95Ssangeeta 			/* remove from head of chain */
927c793af95Ssangeeta 			x = dupedkey; x->rn_parent = t;
928c793af95Ssangeeta 			if (t->rn_left == tt)
929c793af95Ssangeeta 				t->rn_left = x;
930c793af95Ssangeeta 			else
931c793af95Ssangeeta 				t->rn_right = x;
932c793af95Ssangeeta 		} else {
933c793af95Ssangeeta 			/* find node in front of tt on the chain */
934c793af95Ssangeeta 			for (x = p = saved_tt; p && p->rn_dupedkey != tt; )
935c793af95Ssangeeta 				p = p->rn_dupedkey;
936c793af95Ssangeeta 			if (p) {
937c793af95Ssangeeta 				p->rn_dupedkey = tt->rn_dupedkey;
938c793af95Ssangeeta 				if (tt->rn_dupedkey)		/* parent */
939c793af95Ssangeeta 					tt->rn_dupedkey->rn_parent = p;
940c793af95Ssangeeta 								/* parent */
941c793af95Ssangeeta 			} else
942c793af95Ssangeeta #ifdef	_KERNEL
943c793af95Ssangeeta 				cmn_err(CE_WARN,
944c793af95Ssangeeta 				    "rn_delete: couldn't find us\n");
945c793af95Ssangeeta #else
946c793af95Ssangeeta 				syslog(LOG_ERR,
947c793af95Ssangeeta 				    "rn_delete: couldn't find us\n");
948c793af95Ssangeeta #endif	/* _KERNEL */
949c793af95Ssangeeta 		}
950c793af95Ssangeeta 		t = tt + 1;
951c793af95Ssangeeta 		if (t->rn_flags & RNF_ACTIVE) {
952c793af95Ssangeeta 			*++x = *t;
953c793af95Ssangeeta 			p = t->rn_parent;
954c793af95Ssangeeta 			if (p->rn_left == t)
955c793af95Ssangeeta 				p->rn_left = x;
956c793af95Ssangeeta 			else
957c793af95Ssangeeta 				p->rn_right = x;
958c793af95Ssangeeta 			x->rn_left->rn_parent = x;
959c793af95Ssangeeta 			x->rn_right->rn_parent = x;
960c793af95Ssangeeta 		}
961c793af95Ssangeeta 		goto out;
962c793af95Ssangeeta 	}
963c793af95Ssangeeta 	if (t->rn_left == tt)
964c793af95Ssangeeta 		x = t->rn_right;
965c793af95Ssangeeta 	else
966c793af95Ssangeeta 		x = t->rn_left;
967c793af95Ssangeeta 	p = t->rn_parent;
968c793af95Ssangeeta 	if (p->rn_right == t)
969c793af95Ssangeeta 		p->rn_right = x;
970c793af95Ssangeeta 	else
971c793af95Ssangeeta 		p->rn_left = x;
972c793af95Ssangeeta 	x->rn_parent = p;
973c793af95Ssangeeta 	/*
974c793af95Ssangeeta 	 * Demote routes attached to us.
975c793af95Ssangeeta 	 */
976c793af95Ssangeeta 	if (t->rn_mklist) {
977c793af95Ssangeeta 		if (x->rn_bit >= 0) {
978c793af95Ssangeeta 			for (mp = &x->rn_mklist; (m = *mp) != NULL; )
979c793af95Ssangeeta 				mp = &m->rm_mklist;
980c793af95Ssangeeta 			*mp = t->rn_mklist;
981c793af95Ssangeeta 		} else {
982c793af95Ssangeeta 			/*
983c793af95Ssangeeta 			 * If there are any key,mask pairs in a sibling
984c793af95Ssangeeta 			 * duped-key chain, some subset will appear sorted
985c793af95Ssangeeta 			 * in the same order attached to our mklist
986c793af95Ssangeeta 			 */
987c793af95Ssangeeta 			for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
988c793af95Ssangeeta 				if (m == x->rn_mklist) {
989c793af95Ssangeeta 					struct radix_mask *mm = m->rm_mklist;
990c793af95Ssangeeta 					x->rn_mklist = 0;
991c793af95Ssangeeta 					if (--(m->rm_refs) < 0)
992c793af95Ssangeeta 						MKFree(m);
993c793af95Ssangeeta 					m = mm;
994c793af95Ssangeeta 				}
995c793af95Ssangeeta 			if (m)
996c793af95Ssangeeta #ifdef	_KERNEL
997c793af95Ssangeeta 				cmn_err(CE_WARN,
998c793af95Ssangeeta 				    "rn_delete: Orphaned Mask %p at %p\n",
999c793af95Ssangeeta 				    (void *)m, (void *)x);
1000c793af95Ssangeeta #else
1001c793af95Ssangeeta 				syslog(LOG_ERR,
1002c793af95Ssangeeta 				    "rn_delete: Orphaned Mask %p at %p\n",
1003c793af95Ssangeeta 				    (void *)m, (void *)x);
1004c793af95Ssangeeta #endif	/* _KERNEL */
1005c793af95Ssangeeta 		}
1006c793af95Ssangeeta 	}
1007c793af95Ssangeeta 	/*
1008c793af95Ssangeeta 	 * We may be holding an active internal node in the tree.
1009c793af95Ssangeeta 	 */
1010c793af95Ssangeeta 	x = tt + 1;
1011c793af95Ssangeeta 	if (t != x) {
1012c793af95Ssangeeta 		*t = *x;
1013c793af95Ssangeeta 		t->rn_left->rn_parent = t;
1014c793af95Ssangeeta 		t->rn_right->rn_parent = t;
1015c793af95Ssangeeta 		p = x->rn_parent;
1016c793af95Ssangeeta 		if (p->rn_left == x)
1017c793af95Ssangeeta 			p->rn_left = t;
1018c793af95Ssangeeta 		else
1019c793af95Ssangeeta 			p->rn_right = t;
1020c793af95Ssangeeta 	}
1021c793af95Ssangeeta out:
1022c793af95Ssangeeta 	tt->rn_flags &= ~RNF_ACTIVE;
1023c793af95Ssangeeta 	tt[1].rn_flags &= ~RNF_ACTIVE;
1024c793af95Ssangeeta 	return (tt);
1025c793af95Ssangeeta }
1026c793af95Ssangeeta 
1027c793af95Ssangeeta /*
1028c793af95Ssangeeta  * Walk the radix tree; For the kernel routing table, we hold additional
1029c793af95Ssangeeta  * refs on the ire_bucket to ensure that the walk function f() does not
1030c793af95Ssangeeta  * run into trashed memory. The kernel routing table is identified by
1031c793af95Ssangeeta  * a rnh_treetop that has RNF_SUNW_FT set in the rn_flags.
1032c793af95Ssangeeta  * Note that all refs takein in rn_walktree are released before it returns,
1033c793af95Ssangeeta  * so that f() will need to take any additional references on memory
1034c793af95Ssangeeta  * to be passed back to the caller of rn_walktree.
1035c793af95Ssangeeta  */
1036c793af95Ssangeeta static int
1037c793af95Ssangeeta rn_walktree(h, f, w)
1038c793af95Ssangeeta 	struct radix_node_head *h;
1039c793af95Ssangeeta 	walktree_f_t *f;
1040c793af95Ssangeeta 	void *w;
1041*2679e103Ssowmini {
1042*2679e103Ssowmini 	return (rn_walktree_mt(h, f, w, NULL, NULL));
1043*2679e103Ssowmini }
1044*2679e103Ssowmini static int
1045*2679e103Ssowmini rn_walktree_mt(h, f, w, lockf, unlockf)
1046*2679e103Ssowmini 	struct radix_node_head *h;
1047*2679e103Ssowmini 	walktree_f_t *f;
1048*2679e103Ssowmini 	void *w;
1049*2679e103Ssowmini 	lockf_t lockf, unlockf;
1050c793af95Ssangeeta {
1051c793af95Ssangeeta 	int error;
1052c793af95Ssangeeta 	struct radix_node *base, *next;
1053c793af95Ssangeeta 	struct radix_node *rn = h->rnh_treetop;
1054*2679e103Ssowmini 	boolean_t is_mt = B_FALSE;
1055c793af95Ssangeeta 
1056*2679e103Ssowmini 	if (lockf != NULL) {
1057*2679e103Ssowmini 		ASSERT(unlockf != NULL);
1058*2679e103Ssowmini 		is_mt = B_TRUE;
1059c793af95Ssangeeta 	}
1060c793af95Ssangeeta 	/*
1061c793af95Ssangeeta 	 * This gets complicated because we may delete the node
1062c793af95Ssangeeta 	 * while applying the function f to it, so we need to calculate
1063c793af95Ssangeeta 	 * the successor node in advance.
1064c793af95Ssangeeta 	 */
1065c793af95Ssangeeta 	RADIX_NODE_HEAD_RLOCK(h);
1066c793af95Ssangeeta 	/* First time through node, go left */
1067c793af95Ssangeeta 	while (rn->rn_bit >= 0) {
1068c793af95Ssangeeta 		rn = rn->rn_left;
1069c793af95Ssangeeta 	}
1070c793af95Ssangeeta 
1071*2679e103Ssowmini 	if (is_mt)
1072*2679e103Ssowmini 		(*lockf)(rn);
1073c793af95Ssangeeta 
1074c793af95Ssangeeta 	for (;;) {
1075c793af95Ssangeeta 		base = rn;
1076c793af95Ssangeeta 		/* If at right child go back up, otherwise, go right */
1077c793af95Ssangeeta 		while (rn->rn_parent->rn_right == rn &&
1078c793af95Ssangeeta 		    (rn->rn_flags & RNF_ROOT) == 0) {
1079c793af95Ssangeeta 			rn = rn->rn_parent;
1080c793af95Ssangeeta 		}
1081c793af95Ssangeeta 		/* Find the next *leaf* since next node might vanish, too */
1082c793af95Ssangeeta 		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0; ) {
1083c793af95Ssangeeta 			rn = rn->rn_left;
1084c793af95Ssangeeta 		}
1085c793af95Ssangeeta 		next = rn;
1086c793af95Ssangeeta 
1087*2679e103Ssowmini 		if (is_mt && next != NULL)
1088*2679e103Ssowmini 			(*lockf)(next);
1089c793af95Ssangeeta 
1090c793af95Ssangeeta 		/* Process leaves */
1091c793af95Ssangeeta 		while ((rn = base) != NULL) {
1092c793af95Ssangeeta 			base = rn->rn_dupedkey;
1093c793af95Ssangeeta 
1094*2679e103Ssowmini 			if (is_mt && base != NULL)
1095*2679e103Ssowmini 				(*lockf)(base);
1096c793af95Ssangeeta 
1097c793af95Ssangeeta 			RADIX_NODE_HEAD_UNLOCK(h);
1098c793af95Ssangeeta 			if (!(rn->rn_flags & RNF_ROOT) &&
1099c793af95Ssangeeta 			    (error = (*f)(rn, w))) {
1100*2679e103Ssowmini 				if (is_mt) {
1101*2679e103Ssowmini 					(*unlockf)(rn);
1102c793af95Ssangeeta 					if (base != NULL)
1103*2679e103Ssowmini 						(*unlockf)(base);
1104c793af95Ssangeeta 					if (next != NULL)
1105*2679e103Ssowmini 						(*unlockf)(next);
1106c793af95Ssangeeta 				}
1107c793af95Ssangeeta 				return (error);
1108c793af95Ssangeeta 			}
1109*2679e103Ssowmini 			if (is_mt)
1110*2679e103Ssowmini 				(*unlockf)(rn);
1111c793af95Ssangeeta 			RADIX_NODE_HEAD_RLOCK(h);
1112c793af95Ssangeeta 		}
1113c793af95Ssangeeta 		rn = next;
1114c793af95Ssangeeta 		if (rn->rn_flags & RNF_ROOT) {
1115c793af95Ssangeeta 			RADIX_NODE_HEAD_UNLOCK(h);
1116*2679e103Ssowmini 			/*
1117*2679e103Ssowmini 			 * no ref to release, since we never take a ref
1118*2679e103Ssowmini 			 * on the root node- it can't be deleted.
1119*2679e103Ssowmini 			 */
1120c793af95Ssangeeta 			return (0);
1121c793af95Ssangeeta 		}
1122c793af95Ssangeeta 	}
1123c793af95Ssangeeta 	/* NOTREACHED */
1124c793af95Ssangeeta }
1125c793af95Ssangeeta 
1126c793af95Ssangeeta /*
1127c793af95Ssangeeta  * Allocate and initialize an empty tree. This has 3 nodes, which are
1128c793af95Ssangeeta  * part of the radix_node_head (in the order <left,root,right>) and are
1129c793af95Ssangeeta  * marked RNF_ROOT so they cannot be freed.
1130c793af95Ssangeeta  * The leaves have all-zero and all-one keys, with significant
1131c793af95Ssangeeta  * bits starting at 'off'.
1132c793af95Ssangeeta  * Return 1 on success, 0 on error.
1133c793af95Ssangeeta  */
1134c793af95Ssangeeta int
1135c793af95Ssangeeta rn_inithead(head, off)
1136c793af95Ssangeeta 	void **head;
1137c793af95Ssangeeta 	int off;
1138c793af95Ssangeeta {
1139c793af95Ssangeeta 	struct radix_node_head *rnh;
1140c793af95Ssangeeta 	struct radix_node *t, *tt, *ttt;
1141c793af95Ssangeeta 	if (*head)
1142c793af95Ssangeeta 		return (1);
1143c793af95Ssangeeta 	R_ZallocSleep(rnh, struct radix_node_head *, sizeof (*rnh));
1144c793af95Ssangeeta 	if (rnh == 0)
1145c793af95Ssangeeta 		return (0);
1146c793af95Ssangeeta #ifdef _KERNEL
1147c793af95Ssangeeta 	RADIX_NODE_HEAD_LOCK_INIT(rnh);
1148c793af95Ssangeeta #endif
1149c793af95Ssangeeta 	*head = rnh;
1150c793af95Ssangeeta 	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
1151c793af95Ssangeeta 	ttt = rnh->rnh_nodes + 2;
1152c793af95Ssangeeta 	t->rn_right = ttt;
1153c793af95Ssangeeta 	t->rn_parent = t;
1154c793af95Ssangeeta 	tt = t->rn_left;	/* ... which in turn is rnh->rnh_nodes */
1155c793af95Ssangeeta 	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
1156c793af95Ssangeeta 	tt->rn_bit = -1 - off;
1157c793af95Ssangeeta 	*ttt = *tt;
1158c793af95Ssangeeta 	ttt->rn_key = rn_ones;
1159c793af95Ssangeeta 	rnh->rnh_addaddr = rn_addroute;
1160c793af95Ssangeeta 	rnh->rnh_deladdr = rn_delete;
1161c793af95Ssangeeta 	rnh->rnh_matchaddr = rn_match;
1162c793af95Ssangeeta 	rnh->rnh_matchaddr_args = rn_match_args;
1163c793af95Ssangeeta 	rnh->rnh_lookup = rn_lookup;
1164c793af95Ssangeeta 	rnh->rnh_walktree = rn_walktree;
1165*2679e103Ssowmini 	rnh->rnh_walktree_mt = rn_walktree_mt;
1166c793af95Ssangeeta 	rnh->rnh_walktree_from = NULL;  /* not implemented */
1167c793af95Ssangeeta 	rnh->rnh_treetop = t;
1168c793af95Ssangeeta 	return (1);
1169c793af95Ssangeeta }
1170c793af95Ssangeeta 
1171c793af95Ssangeeta void
1172c793af95Ssangeeta rn_init()
1173c793af95Ssangeeta {
1174c793af95Ssangeeta 	char *cp, *cplim;
1175c793af95Ssangeeta 
1176c793af95Ssangeeta #ifdef	_KERNEL
1177c793af95Ssangeeta 	radix_mask_cache = kmem_cache_create("radix_mask",
1178c793af95Ssangeeta 	    sizeof (struct radix_mask), 0, NULL, NULL, NULL, NULL, NULL, 0);
1179c793af95Ssangeeta 	radix_node_cache = kmem_cache_create("radix_node",
1180c793af95Ssangeeta 	    max_keylen + 2 * sizeof (struct radix_node),
1181c793af95Ssangeeta 	    0, NULL, NULL, NULL, NULL, NULL, 0);
1182c793af95Ssangeeta #endif /* _KERNEL */
1183c793af95Ssangeeta 	R_ZallocSleep(rn_zeros, char *, 2 * max_keylen);
1184c793af95Ssangeeta 
1185c793af95Ssangeeta 	ASSERT(rn_zeros != NULL);
1186c793af95Ssangeeta 	bzero(rn_zeros, 2 * max_keylen);
1187c793af95Ssangeeta 	rn_ones = cp = rn_zeros + max_keylen;
1188c793af95Ssangeeta 	cplim = rn_ones + max_keylen;
1189c793af95Ssangeeta 	while (cp < cplim)
1190c793af95Ssangeeta 		*cp++ = -1;
1191c793af95Ssangeeta 	if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0)
1192c793af95Ssangeeta 		panic("rn_init: could not init mask_rnhead ");
1193c793af95Ssangeeta }
1194c793af95Ssangeeta 
1195c793af95Ssangeeta int
1196c793af95Ssangeeta rn_freenode(n, p)
1197c793af95Ssangeeta 	struct radix_node *n;
1198c793af95Ssangeeta 	void *p;
1199c793af95Ssangeeta {
1200c793af95Ssangeeta 	struct	radix_node_head *rnh = p;
1201c793af95Ssangeeta 	struct	radix_node *d;
1202c793af95Ssangeeta 
1203c793af95Ssangeeta 	d = rnh->rnh_deladdr(n->rn_key, NULL, rnh);
1204c793af95Ssangeeta 	if (d != NULL) {
1205c793af95Ssangeeta 		Free(d, radix_node_cache);
1206c793af95Ssangeeta 	}
1207c793af95Ssangeeta 	return (0);
1208c793af95Ssangeeta }
1209c793af95Ssangeeta 
1210c793af95Ssangeeta 
1211c793af95Ssangeeta void
1212c793af95Ssangeeta rn_freehead(rnh)
1213c793af95Ssangeeta 	struct radix_node_head *rnh;
1214c793af95Ssangeeta {
1215c793af95Ssangeeta 	(void) rn_walktree(rnh, rn_freenode, rnh);
1216c793af95Ssangeeta 
1217c793af95Ssangeeta 	rnh->rnh_addaddr = NULL;
1218c793af95Ssangeeta 	rnh->rnh_deladdr = NULL;
1219c793af95Ssangeeta 	rnh->rnh_matchaddr = NULL;
1220c793af95Ssangeeta 	rnh->rnh_lookup = NULL;
1221c793af95Ssangeeta 	rnh->rnh_walktree = NULL;
1222c793af95Ssangeeta 
1223c793af95Ssangeeta #ifdef	_KERNEL
1224c793af95Ssangeeta 	FreeHead(rnh, sizeof (*rnh));
1225c793af95Ssangeeta #else
1226c793af95Ssangeeta 	Free(rnh, NULL);
1227c793af95Ssangeeta #endif	/* _KERNEL */
1228c793af95Ssangeeta }
1229c793af95Ssangeeta 
1230c793af95Ssangeeta void
1231c793af95Ssangeeta rn_fini()
1232c793af95Ssangeeta {
1233c793af95Ssangeeta 	struct radix_mask *m;
1234c793af95Ssangeeta 
1235c793af95Ssangeeta 	if (rn_zeros != NULL) {
1236c793af95Ssangeeta #ifdef _KERNEL
1237c793af95Ssangeeta 		FreeHead(rn_zeros, 2 * max_keylen);
1238c793af95Ssangeeta #else
1239c793af95Ssangeeta 		Free(rn_zeros, NULL);
1240c793af95Ssangeeta #endif
1241c793af95Ssangeeta 		rn_zeros = NULL;
1242c793af95Ssangeeta 	}
1243c793af95Ssangeeta 
1244c793af95Ssangeeta 
1245c793af95Ssangeeta 	if (mask_rnhead != NULL) {
1246c793af95Ssangeeta 		rn_freehead(mask_rnhead);
1247c793af95Ssangeeta 		mask_rnhead = NULL;
1248c793af95Ssangeeta 	}
1249c793af95Ssangeeta 
1250c793af95Ssangeeta 	while ((m = rn_mkfreelist) != NULL) {
1251c793af95Ssangeeta 		rn_mkfreelist = m->rm_mklist;
1252c793af95Ssangeeta 		Free(m, NULL);
1253c793af95Ssangeeta 	}
1254c793af95Ssangeeta }
1255