contrib/ipfilter/radix.c

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