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