sys/contrib/ipfilter/netinet/radix_ipf.c

   1 /*
   2  * Copyright (C) 2012 by Darren Reed.
   3  *
   4  * See the IPFILTER.LICENCE file for details on licencing.
   5  */
   6 #include <sys/types.h>
   7 #include <sys/time.h>
   8 #include <sys/socket.h>
   9 #include <sys/param.h>
  10 #include <netinet/in.h>
  11 #include <net/if.h>
  12 #ifdef _KERNEL
  13 #include <sys/systm.h>
  14 #else
  15 # include <stddef.h>
  16 # include <stdlib.h>
  17 # include <strings.h>
  18 # include <string.h>
  19 #endif /* !_KERNEL */
  20 #include "netinet/ip_compat.h"
  21 #include "netinet/ip_fil.h"
  22 #ifdef RDX_DEBUG
  23 # include <arpa/inet.h>
  24 # include <stdlib.h>
  25 # include <stdio.h>
  26 #endif
  27 #include "netinet/radix_ipf.h"
  28
  29 #define ADF_OFF offsetof(addrfamily_t, adf_addr)
  30 #define ADF_OFF_BITS    (ADF_OFF << 3)
  31
  32 static ipf_rdx_node_t *ipf_rx_insert __P((ipf_rdx_head_t *,
  33                                           ipf_rdx_node_t nodes[2], int *));
  34 static void ipf_rx_attach_mask __P((ipf_rdx_node_t *, ipf_rdx_mask_t *));
  35 static int count_mask_bits __P((addrfamily_t *, u_32_t **));
  36 static void buildnodes __P((addrfamily_t *, addrfamily_t *,
  37                             ipf_rdx_node_t n[2]));
  38 static ipf_rdx_node_t *ipf_rx_find_addr __P((ipf_rdx_node_t *, u_32_t *));
  39 static ipf_rdx_node_t *ipf_rx_lookup __P((ipf_rdx_head_t *, addrfamily_t *,
  40                                           addrfamily_t *));
  41 /*      $NetBSD: radix_ipf.c,v 1.6 2015/12/15 12:30:34 christos Exp $   */
  42
  43 /*
  44  * Foreword.
  45  * ---------
  46  * The code in this file has been written to target using the addrfamily_t
  47  * data structure to house the address information and no other. Thus there
  48  * are certain aspects of thise code (such as offsets to the address itself)
  49  * that are hard coded here whilst they might be more variable elsewhere.
  50  * Similarly, this code enforces no maximum key length as that's implied by
  51  * all keys needing to be stored in addrfamily_t.
  52  */
  53
  54 /* ------------------------------------------------------------------------ */
  55 /* Function:    count_mask_bits                                             */
  56 /* Returns:     number of consecutive bits starting at "mask".              */
  57 /*                                                                          */
  58 /* Count the number of bits set in the address section of addrfamily_t and  */
  59 /* return both that number and a pointer to the last word with a bit set if */
  60 /* lastp is not NULL. The bit count is performed using network byte order   */
  61 /* as the guide for which bit is the most significant bit.                  */
  62 /* ------------------------------------------------------------------------ */
  63 static int
  64 count_mask_bits(mask, lastp)
  65         addrfamily_t *mask;
  66         u_32_t **lastp;
  67 {
  68         u_32_t *mp = (u_32_t *)&mask->adf_addr;
  69         u_32_t m;
  70         int count = 0;
  71         int mlen;
  72
  73         mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr);
  74         for (; mlen > 0; mlen -= 4, mp++) {
  75                 if ((m = ntohl(*mp)) == 0)
  76                         break;
  77                 if (lastp != NULL)
  78                         *lastp = mp;
  79                 for (; m & 0x80000000; m <<= 1)
  80                         count++;
  81         }
  82
  83         return count;
  84 }
  85
  86
  87 /* ------------------------------------------------------------------------ */
  88 /* Function:    buildnodes                                                  */
  89 /* Returns:     Nil                                                         */
  90 /* Parameters:  addr(I)  - network address for this radix node              */
  91 /*              mask(I)  - netmask associated with the above address        */
  92 /*              nodes(O) - pair of ipf_rdx_node_t's to initialise with data */
  93 /*                         associated with addr and mask.                   */
  94 /*                                                                          */
  95 /* Initialise the fields in a pair of radix tree nodes according to the     */
  96 /* data supplied in the paramters "addr" and "mask". It is expected that    */
  97 /* "mask" will contain a consecutive string of bits set. Masks with gaps in */
  98 /* the middle are not handled by this implementation.                       */
  99 /* ------------------------------------------------------------------------ */
 100 static void
 101 buildnodes(addr, mask, nodes)
 102         addrfamily_t *addr, *mask;
 103         ipf_rdx_node_t nodes[2];
 104 {
 105         u_32_t maskbits;
 106         u_32_t lastbits;
 107         u_32_t lastmask;
 108         u_32_t *last;
 109         int masklen;
 110
 111         last = NULL;
 112         maskbits = count_mask_bits(mask, &last);
 113         if (last == NULL) {
 114                 masklen = 0;
 115                 lastmask = 0;
 116         } else {
 117                 masklen = last - (u_32_t *)mask;
 118                 lastmask = *last;
 119         }
 120         lastbits = maskbits & 0x1f;
 121
 122         bzero(&nodes[0], sizeof(ipf_rdx_node_t) * 2);
 123         nodes[0].maskbitcount = maskbits;
 124         nodes[0].index = -1 - (ADF_OFF_BITS + maskbits);
 125         nodes[0].addrkey = (u_32_t *)addr;
 126         nodes[0].maskkey = (u_32_t *)mask;
 127         nodes[0].addroff = nodes[0].addrkey + masklen;
 128         nodes[0].maskoff = nodes[0].maskkey + masklen;
 129         nodes[0].parent = &nodes[1];
 130         nodes[0].offset = masklen;
 131         nodes[0].lastmask = lastmask;
 132         nodes[1].offset = masklen;
 133         nodes[1].left = &nodes[0];
 134         nodes[1].maskbitcount = maskbits;
 135 #ifdef RDX_DEBUG
 136         (void) strcpy(nodes[0].name, "_BUILD.0");
 137         (void) strcpy(nodes[1].name, "_BUILD.1");
 138 #endif
 139 }
 140
 141
 142 /* ------------------------------------------------------------------------ */
 143 /* Function:    ipf_rx_find_addr                                            */
 144 /* Returns:     ipf_rdx_node_t * - pointer to a node in the radix tree.     */
 145 /* Parameters:  tree(I)  - pointer to first right node in tree to search    */
 146 /*              addr(I)  - pointer to address to match                      */
 147 /*                                                                          */
 148 /* Walk the radix tree given by "tree", looking for a leaf node that is a   */
 149 /* match for the address given by "addr".                                   */
 150 /* ------------------------------------------------------------------------ */
 151 static ipf_rdx_node_t *
 152 ipf_rx_find_addr(tree, addr)
 153         ipf_rdx_node_t *tree;
 154         u_32_t *addr;
 155 {
 156         ipf_rdx_node_t *cur;
 157
 158         for (cur = tree; cur->index >= 0;) {
 159                 if (cur->bitmask & addr[cur->offset]) {
 160                         cur = cur->right;
 161                 } else {
 162                         cur = cur->left;
 163                 }
 164         }
 165
 166         return (cur);
 167 }
 168
 169
 170 /* ------------------------------------------------------------------------ */
 171 /* Function:    ipf_rx_match                                                */
 172 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
 173 /*                                 added to the tree.                       */
 174 /* Paramters:   head(I)  - pointer to tree head to search                   */
 175 /*              addr(I)  - pointer to address to find                       */
 176 /*                                                                          */
 177 /* Search the radix tree for the best match to the address pointed to by    */
 178 /* "addr" and return a pointer to that node. This search will not match the */
 179 /* address information stored in either of the root leaves as neither of    */
 180 /* them are considered to be part of the tree of data being stored.         */
 181 /* ------------------------------------------------------------------------ */
 182 static ipf_rdx_node_t *
 183 ipf_rx_match(head, addr)
 184         ipf_rdx_head_t *head;
 185         addrfamily_t *addr;
 186 {
 187         ipf_rdx_mask_t *masknode;
 188         ipf_rdx_node_t *prev;
 189         ipf_rdx_node_t *node;
 190         ipf_rdx_node_t *cur;
 191         u_32_t *data;
 192         u_32_t *mask;
 193         u_32_t *key;
 194         u_32_t *end;
 195         int len;
 196         int i;
 197
 198         len = addr->adf_len;
 199         end = (u_32_t *)((u_char *)addr + len);
 200         node = ipf_rx_find_addr(head->root, (u_32_t *)addr);
 201
 202         /*
 203          * Search the dupkey list for a potential match.
 204          */
 205         for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) {
 206                 i = cur[0].addroff - cur[0].addrkey;
 207                 data = cur[0].addrkey + i;
 208                 mask = cur[0].maskkey + i;
 209                 key = (u_32_t *)addr + i;
 210                 for (; key < end; data++, key++, mask++)
 211                         if ((*key & *mask) != *data)
 212                                 break;
 213                 if ((end == key) && (cur->root == 0))
 214                         return (cur);   /* Equal keys */
 215         }
 216         prev = node->parent;
 217         key = (u_32_t *)addr;
 218
 219         for (node = prev; node->root == 0; node = node->parent) {
 220                 /*
 221                  * We know that the node hasn't matched so therefore only
 222                  * the entries in the mask list are searched, not the top
 223                  * node nor the dupkey list.
 224                  */
 225                 masknode = node->masks;
 226                 for (; masknode != NULL; masknode = masknode->next) {
 227                         if (masknode->maskbitcount > node->maskbitcount)
 228                                 continue;
 229                         cur = masknode->node;
 230                         for (i = ADF_OFF >> 2; i <= node->offset; i++) {
 231                                 if ((key[i] & masknode->mask[i]) ==
 232                                     cur->addrkey[i])
 233                                         return (cur);
 234                         }
 235                 }
 236         }
 237
 238         return NULL;
 239 }
 240
 241
 242 /* ------------------------------------------------------------------------ */
 243 /* Function:    ipf_rx_lookup                                               */
 244 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
 245 /*                                 added to the tree.                       */
 246 /* Paramters:   head(I)  - pointer to tree head to search                   */
 247 /*              addr(I)  - address part of the key to match                 */
 248 /*              mask(I)  - netmask part of the key to match                 */
 249 /*                                                                          */
 250 /* ipf_rx_lookup searches for an exact match on (addr,mask). The intention  */
 251 /* is to see if a given key is in the tree, not to see if a route exists.   */
 252 /* ------------------------------------------------------------------------ */
 253 ipf_rdx_node_t *
 254 ipf_rx_lookup(head, addr, mask)
 255         ipf_rdx_head_t *head;
 256         addrfamily_t *addr, *mask;
 257 {
 258         ipf_rdx_node_t *found;
 259         ipf_rdx_node_t *node;
 260         u_32_t *akey;
 261         int count;
 262
 263         found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
 264         if (found->root == 1)
 265                 return NULL;
 266
 267         /*
 268          * It is possible to find a matching address in the tree but for the
 269          * netmask to not match. If the netmask does not match and there is
 270          * no list of alternatives present at dupkey, return a failure.
 271          */
 272         count = count_mask_bits(mask, NULL);
 273         if (count != found->maskbitcount && found->dupkey == NULL)
 274                 return (NULL);
 275
 276         akey = (u_32_t *)addr;
 277         if ((found->addrkey[found->offset] & found->maskkey[found->offset]) !=
 278             akey[found->offset])
 279                 return NULL;
 280
 281         if (found->dupkey != NULL) {
 282                 node = found;
 283                 while (node != NULL && node->maskbitcount != count)
 284                         node = node->dupkey;
 285                 if (node == NULL)
 286                         return (NULL);
 287                 found = node;
 288         }
 289         return found;
 290 }
 291
 292
 293 /* ------------------------------------------------------------------------ */
 294 /* Function:    ipf_rx_attach_mask                                          */
 295 /* Returns:     Nil                                                         */
 296 /* Parameters:  node(I)  - pointer to a radix tree node                     */
 297 /*              mask(I)  - pointer to mask structure to add                 */
 298 /*                                                                          */
 299 /* Add the netmask to the given node in an ordering where the most specific */
 300 /* netmask is at the top of the list.                                       */
 301 /* ------------------------------------------------------------------------ */
 302 static void
 303 ipf_rx_attach_mask(node, mask)
 304         ipf_rdx_node_t *node;
 305         ipf_rdx_mask_t *mask;
 306 {
 307         ipf_rdx_mask_t **pm;
 308         ipf_rdx_mask_t *m;
 309
 310         for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next)
 311                 if (m->maskbitcount < mask->maskbitcount)
 312                         break;
 313         mask->next = *pm;
 314         *pm = mask;
 315 }
 316
 317
 318 /* ------------------------------------------------------------------------ */
 319 /* Function:    ipf_rx_insert                                               */
 320 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
 321 /*                                 added to the tree.                       */
 322 /* Paramters:   head(I)  - pointer to tree head to add nodes to             */
 323 /*              nodes(I) - pointer to radix nodes to be added               */
 324 /*              dup(O)   - set to 1 if node is a duplicate, else 0.         */
 325 /*                                                                          */
 326 /* Add the new radix tree entry that owns nodes[] to the tree given by head.*/
 327 /* If there is already a matching key in the table, "dup" will be set to 1  */
 328 /* and the existing node pointer returned if there is a complete key match. */
 329 /* A complete key match is a matching of all key data that is presented by  */
 330 /* by the netmask.                                                          */
 331 /* ------------------------------------------------------------------------ */
 332 static ipf_rdx_node_t *
 333 ipf_rx_insert(head, nodes, dup)
 334         ipf_rdx_head_t *head;
 335         ipf_rdx_node_t nodes[2];
 336         int *dup;
 337 {
 338         ipf_rdx_mask_t **pmask;
 339         ipf_rdx_node_t *node;
 340         ipf_rdx_node_t *prev;
 341         ipf_rdx_mask_t *mask;
 342         ipf_rdx_node_t *cur;
 343         u_32_t nodemask;
 344         u_32_t *addr;
 345         u_32_t *data;
 346         int nodebits;
 347         u_32_t *key;
 348         u_32_t *end;
 349         u_32_t bits;
 350         int nodekey;
 351         int nodeoff;
 352         int nlen;
 353         int len;
 354
 355         addr = nodes[0].addrkey;
 356
 357         node = ipf_rx_find_addr(head->root, addr);
 358         len = ((addrfamily_t *)addr)->adf_len;
 359         key = (u_32_t *)&((addrfamily_t *)addr)->adf_addr;
 360         data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr;
 361         end = (u_32_t *)((u_char *)addr + len);
 362         for (nlen = 0; key < end; data++, key++, nlen += 32)
 363                 if (*key != *data)
 364                         break;
 365         if (end == data) {
 366                 *dup = 1;
 367                 return (node);  /* Equal keys */
 368         }
 369         *dup = 0;
 370
 371         bits = (ntohl(*data) ^ ntohl(*key));
 372         for (; bits != 0; nlen++) {
 373                 if ((bits & 0x80000000) != 0)
 374                         break;
 375                 bits <<= 1;
 376         }
 377         nlen += ADF_OFF_BITS;
 378         nodes[1].index = nlen;
 379         nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f));
 380         nodes[0].offset = nlen / 32;
 381         nodes[1].offset = nlen / 32;
 382
 383         /*
 384          * Walk through the tree and look for the correct place to attach
 385          * this node. ipf_rx_fin_addr is not used here because the place
 386          * to attach this node may be an internal node (same key, different
 387          * netmask.) Additionally, the depth of the search is forcibly limited
 388          * here to not exceed the netmask, so that a short netmask will be
 389          * added higher up the tree even if there are lower branches.
 390          */
 391         cur = head->root;
 392         key = nodes[0].addrkey;
 393         do {
 394                 prev = cur;
 395                 if (key[cur->offset] & cur->bitmask) {
 396                         cur = cur->right;
 397                 } else {
 398                         cur = cur->left;
 399                 }
 400         } while (nlen > (unsigned)cur->index);
 401
 402         if ((key[prev->offset] & prev->bitmask) == 0) {
 403                 prev->left = &nodes[1];
 404         } else {
 405                 prev->right = &nodes[1];
 406         }
 407         cur->parent = &nodes[1];
 408         nodes[1].parent = prev;
 409         if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) {
 410                 nodes[1].right = cur;
 411         } else {
 412                 nodes[1].right = &nodes[0];
 413                 nodes[1].left = cur;
 414         }
 415
 416         nodeoff = nodes[0].offset;
 417         nodekey = nodes[0].addrkey[nodeoff];
 418         nodemask = nodes[0].lastmask;
 419         nodebits = nodes[0].maskbitcount;
 420         prev = NULL;
 421         /*
 422          * Find the node up the tree with the largest pattern that still
 423          * matches the node being inserted to see if this mask can be
 424          * moved there.
 425          */
 426         for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) {
 427                 if (cur->maskbitcount <= nodebits)
 428                         break;
 429                 if (((cur - 1)->addrkey[nodeoff] & nodemask) != nodekey)
 430                         break;
 431                 prev = cur;
 432         }
 433
 434         KMALLOC(mask, ipf_rdx_mask_t *);
 435         if (mask == NULL)
 436                 return NULL;
 437         bzero(mask, sizeof(*mask));
 438         mask->next = NULL;
 439         mask->node = &nodes[0];
 440         mask->maskbitcount = nodebits;
 441         mask->mask = nodes[0].maskkey;
 442         nodes[0].mymask = mask;
 443
 444         if (prev != NULL) {
 445                 ipf_rdx_mask_t *m;
 446
 447                 for (pmask = &prev->masks; (m = *pmask) != NULL;
 448                      pmask = &m->next) {
 449                         if (m->maskbitcount < nodebits)
 450                                 break;
 451                 }
 452         } else {
 453                 /*
 454                  * No higher up nodes qualify, so attach mask locally.
 455                  */
 456                 pmask = &nodes[0].masks;
 457         }
 458         mask->next = *pmask;
 459         *pmask = mask;
 460
 461         /*
 462          * Search the mask list on each child to see if there are any masks
 463          * there that can be moved up to this newly inserted node.
 464          */
 465         cur = nodes[1].right;
 466         if (cur->root == 0) {
 467                 for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
 468                         if (mask->maskbitcount < nodebits) {
 469                                 *pmask = mask->next;
 470                                 ipf_rx_attach_mask(&nodes[0], mask);
 471                         } else {
 472                                 pmask = &mask->next;
 473                         }
 474                 }
 475         }
 476         cur = nodes[1].left;
 477         if (cur->root == 0 && cur != &nodes[0]) {
 478                 for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
 479                         if (mask->maskbitcount < nodebits) {
 480                                 *pmask = mask->next;
 481                                 ipf_rx_attach_mask(&nodes[0], mask);
 482                         } else {
 483                                 pmask = &mask->next;
 484                         }
 485                 }
 486         }
 487         return (&nodes[0]);
 488 }
 489
 490 /* ------------------------------------------------------------------------ */
 491 /* Function:    ipf_rx_addroute                                             */
 492 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
 493 /*                                 added to the tree.                       */
 494 /* Paramters:   head(I)  - pointer to tree head to search                   */
 495 /*              addr(I)  - address portion of "route" to add                */
 496 /*              mask(I)  - netmask portion of "route" to add                */
 497 /*              nodes(I) - radix tree data nodes inside allocate structure  */
 498 /*                                                                          */
 499 /* Attempt to add a node to the radix tree. The key for the node is the     */
 500 /* (addr,mask). No memory allocation for the radix nodes themselves is      */
 501 /* performed here, the data structure that this radix node is being used to */
 502 /* find is expected to house the node data itself however the call to       */
 503 /* ipf_rx_insert() will attempt to allocate memory in order for netmask to  */
 504 /* be promoted further up the tree.                                         */
 505 /* In this case, the ip_pool_node_t structure from ip_pool.h contains both  */
 506 /* the key material (addr,mask) and the radix tree nodes[].                 */
 507 /*                                                                          */
 508 /* The mechanics of inserting the node into the tree is handled by the      */
 509 /* function ipf_rx_insert() above. Here, the code deals with the case       */
 510 /* where the data to be inserted is a duplicate.                            */
 511 /* ------------------------------------------------------------------------ */
 512 ipf_rdx_node_t *
 513 ipf_rx_addroute(head, addr, mask, nodes)
 514         ipf_rdx_head_t *head;
 515         addrfamily_t *addr, *mask;
 516         ipf_rdx_node_t *nodes;
 517 {
 518         ipf_rdx_node_t *node;
 519         ipf_rdx_node_t *prev;
 520         ipf_rdx_node_t *x;
 521         int dup;
 522
 523         buildnodes(addr, mask, nodes);
 524         x = ipf_rx_insert(head, nodes, &dup);
 525         if (x == NULL)
 526                 return NULL;
 527
 528         if (dup == 1) {
 529                 node = &nodes[0];
 530                 prev = NULL;
 531                 /*
 532                  * The duplicate list is kept sorted with the longest
 533                  * mask at the top, meaning that the most specific entry
 534                  * in the listis found first. This list thus allows for
 535                  * duplicates such as 128.128.0.0/32 and 128.128.0.0/16.
 536                  */
 537                 while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) {
 538                         prev = x;
 539                         x = x->dupkey;
 540                 }
 541
 542                 /*
 543                  * Is it a complete duplicate? If so, return NULL and
 544                  * fail the insert. Otherwise, insert it into the list
 545                  * of netmasks active for this key.
 546                  */
 547                 if ((x != NULL) && (x->maskbitcount == node->maskbitcount))
 548                         return (NULL);
 549
 550                 if (prev != NULL) {
 551                         nodes[0].dupkey = x;
 552                         prev->dupkey = &nodes[0];
 553                         nodes[0].parent = prev;
 554                         if (x != NULL)
 555                                 x->parent = &nodes[0];
 556                 } else {
 557                         nodes[0].dupkey = x->dupkey;
 558                         prev = x->parent;
 559                         nodes[0].parent = prev;
 560                         x->parent = &nodes[0];
 561                         if (prev->left == x)
 562                                 prev->left = &nodes[0];
 563                         else
 564                                 prev->right = &nodes[0];
 565                 }
 566         }
 567
 568         return &nodes[0];
 569 }
 570
 571
 572 /* ------------------------------------------------------------------------ */
 573 /* Function:    ipf_rx_delete                                               */
 574 /* Returns:     ipf_rdx_node_t * - NULL on error, else node removed from    */
 575 /*                                 the tree.                                */
 576 /* Paramters:   head(I)  - pointer to tree head to search                   */
 577 /*              addr(I)  - pointer to the address part of the key           */
 578 /*              mask(I)  - pointer to the netmask part of the key           */
 579 /*                                                                          */
 580 /* Search for an entry in the radix tree that is an exact match for (addr,  */
 581 /* mask) and remove it if it exists. In the case where (addr,mask) is a not */
 582 /* a unique key, the tree structure itself is not changed - only the list   */
 583 /* of duplicate keys.                                                       */
 584 /* ------------------------------------------------------------------------ */
 585 ipf_rdx_node_t *
 586 ipf_rx_delete(head, addr, mask)
 587         ipf_rdx_head_t *head;
 588         addrfamily_t *addr, *mask;
 589 {
 590         ipf_rdx_mask_t **pmask;
 591         ipf_rdx_node_t *parent;
 592         ipf_rdx_node_t *found;
 593         ipf_rdx_node_t *prev;
 594         ipf_rdx_node_t *node;
 595         ipf_rdx_node_t *cur;
 596         ipf_rdx_mask_t *m;
 597         int count;
 598
 599         found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
 600         if (found == NULL)
 601                 return NULL;
 602         if (found->root == 1)
 603                 return NULL;
 604         count = count_mask_bits(mask, NULL);
 605         parent = found->parent;
 606         if (found->dupkey != NULL) {
 607                 node = found;
 608                 while (node != NULL && node->maskbitcount != count)
 609                         node = node->dupkey;
 610                 if (node == NULL)
 611                         return (NULL);
 612                 if (node != found) {
 613                         /*
 614                          * Remove from the dupkey list. Here, "parent" is
 615                          * the previous node on the list (rather than tree)
 616                          * and "dupkey" is the next node on the list.
 617                          */
 618                         parent = node->parent;
 619                         parent->dupkey = node->dupkey;
 620                         node->dupkey->parent = parent;
 621                 } else {
 622                         /*
 623                          *
 624                          * When removing the top node of the dupkey list,
 625                          * the pointers at the top of the list that point
 626                          * to other tree nodes need to be preserved and
 627                          * any children must have their parent updated.
 628                          */
 629                         node = node->dupkey;
 630                         node->parent = found->parent;
 631                         node->right = found->right;
 632                         node->left = found->left;
 633                         found->right->parent = node;
 634                         found->left->parent = node;
 635                         if (parent->left == found)
 636                                 parent->left = node;
 637                         else
 638                                 parent->right= node;
 639                 }
 640         } else {
 641                 if (count != found->maskbitcount)
 642                         return (NULL);
 643                 /*
 644                  * Remove the node from the tree and reconnect the subtree
 645                  * below.
 646                  */
 647                 /*
 648                  * If there is a tree to the left, look for something to
 649                  * attach in place of "found".
 650                  */
 651                 prev = found + 1;
 652                 cur = parent->parent;
 653                 if (parent != found + 1) {
 654                         if ((found + 1)->parent->right == found + 1)
 655                                 (found + 1)->parent->right = parent;
 656                         else
 657                                 (found + 1)->parent->left = parent;
 658                         if (cur->right == parent) {
 659                                 if (parent->left == found) {
 660                                         cur->right = parent->right;
 661                                 } else if (parent->left != parent - 1) {
 662                                         cur->right = parent->left;
 663                                 } else {
 664                                         cur->right = parent - 1;
 665                                 }
 666                                 cur->right->parent = cur;
 667                         } else {
 668                                 if (parent->right == found) {
 669                                         cur->left = parent->left;
 670                                 } else if (parent->right != parent - 1) {
 671                                         cur->left = parent->right;
 672                                 } else {
 673                                         cur->left = parent - 1;
 674                                 }
 675                                 cur->left->parent = cur;
 676                         }
 677                         parent->left = (found + 1)->left;
 678                         if ((found + 1)->right != parent)
 679                                 parent->right = (found + 1)->right;
 680                         parent->left->parent = parent;
 681                         parent->right->parent = parent;
 682                         parent->parent = (found + 1)->parent;
 683
 684                         parent->bitmask = prev->bitmask;
 685                         parent->offset = prev->offset;
 686                         parent->index = prev->index;
 687                 } else {
 688                         /*
 689                          * We found an edge node.
 690                          */
 691                         cur = parent->parent;
 692                         if (cur->left == parent) {
 693                                 if (parent->left == found) {
 694                                         cur->left = parent->right;
 695                                         parent->right->parent = cur;
 696                                 } else {
 697                                         cur->left = parent->left;
 698                                         parent->left->parent = cur;
 699                                 }
 700                         } else {
 701                                 if (parent->right != found) {
 702                                         cur->right = parent->right;
 703                                         parent->right->parent = cur;
 704                                 } else {
 705                                         cur->right = parent->left;
 706                                         prev->left->parent = cur;
 707                                 }
 708                         }
 709                 }
 710         }
 711
 712         /*
 713          * Remove mask associated with this node.
 714          */
 715         for (cur = parent; cur->root == 0; cur = cur->parent) {
 716                 ipf_rdx_mask_t **pm;
 717
 718                 if (cur->maskbitcount <= found->maskbitcount)
 719                         break;
 720                 if (((cur - 1)->addrkey[found->offset] & found->bitmask) !=
 721                     found->addrkey[found->offset])
 722                         break;
 723                 for (pm = &cur->masks; (m = *pm) != NULL; )
 724                         if (m->node == cur) {
 725                                 *pm = m->next;
 726                                 break;
 727                         } else {
 728                                 pm = &m->next;
 729                         }
 730         }
 731         KFREE(found->mymask);
 732
 733         /*
 734          * Masks that have been brought up to this node from below need to
 735          * be sent back down.
 736          */
 737         for (pmask = &parent->masks; (m = *pmask) != NULL; ) {
 738                 *pmask = m->next;
 739                 cur = m->node;
 740                 if (cur == found)
 741                         continue;
 742                 if (found->addrkey[cur->offset] & cur->lastmask) {
 743                         ipf_rx_attach_mask(parent->right, m);
 744                 } else if (parent->left != found) {
 745                         ipf_rx_attach_mask(parent->left, m);
 746                 }
 747         }
 748
 749         return (found);
 750 }
 751
 752
 753 /* ------------------------------------------------------------------------ */
 754 /* Function:    ipf_rx_walktree                                             */
 755 /* Returns:     Nil                                                         */
 756 /* Paramters:   head(I)   - pointer to tree head to search                  */
 757 /*              walker(I) - function to call for each node in the tree      */
 758 /*              arg(I)    - parameter to pass to walker, in addition to the */
 759 /*                          node pointer                                    */
 760 /*                                                                          */
 761 /* A standard tree walking function except that it is iterative, rather     */
 762 /* than recursive and tracks the next node in case the "walker" function    */
 763 /* should happen to delete and free the current node. It thus goes without  */
 764 /* saying that the "walker" function is not permitted to cause any change   */
 765 /* in the validity of the data found at either the left or right child.     */
 766 /* ------------------------------------------------------------------------ */
 767 void
 768 ipf_rx_walktree(head, walker, arg)
 769         ipf_rdx_head_t *head;
 770         radix_walk_func_t walker;
 771         void *arg;
 772 {
 773         ipf_rdx_node_t *next;
 774         ipf_rdx_node_t *node = head->root;
 775         ipf_rdx_node_t *base;
 776
 777         while (node->index >= 0)
 778                 node = node->left;
 779
 780         for (;;) {
 781                 base = node;
 782                 while ((node->parent->right == node) && (node->root == 0))
 783                         node = node->parent;
 784
 785                 for (node = node->parent->right; node->index >= 0; )
 786                         node = node->left;
 787                 next = node;
 788
 789                 for (node = base; node != NULL; node = base) {
 790                         base = node->dupkey;
 791                         if (node->root == 0)
 792                                 walker(node, arg);
 793                 }
 794                 node = next;
 795                 if (node->root)
 796                         return;
 797         }
 798 }
 799
 800
 801 /* ------------------------------------------------------------------------ */
 802 /* Function:    ipf_rx_inithead                                             */
 803 /* Returns:     int       - 0 = success, else failure                       */
 804 /* Paramters:   softr(I)  - pointer to radix context                        */
 805 /*              headp(O)  - location for where to store allocated tree head */
 806 /*                                                                          */
 807 /* This function allocates and initialises a radix tree head structure.     */
 808 /* As a traditional radix tree, node 0 is used as the "0" sentinel and node */
 809 /* "2" is used as the all ones sentinel, leaving node "1" as the root from  */
 810 /* which the tree is hung with node "0" on its left and node "2" to the     */
 811 /* right. The context, "softr", is used here to provide a common source of  */
 812 /* the zeroes and ones data rather than have one per head.                  */
 813 /* ------------------------------------------------------------------------ */
 814 int
 815 ipf_rx_inithead(softr, headp)
 816         radix_softc_t *softr;
 817         ipf_rdx_head_t **headp;
 818 {
 819         ipf_rdx_head_t *ptr;
 820         ipf_rdx_node_t *node;
 821
 822         KMALLOC(ptr, ipf_rdx_head_t *);
 823         *headp = ptr;
 824         if (ptr == NULL)
 825                 return -1;
 826         bzero(ptr, sizeof(*ptr));
 827         node = ptr->nodes;
 828         ptr->root = node + 1;
 829         node[0].index = ADF_OFF_BITS;
 830         node[0].index = -1 - node[0].index;
 831         node[1].index = ADF_OFF_BITS;
 832         node[2].index = node[0].index;
 833         node[0].parent = node + 1;
 834         node[1].parent = node + 1;
 835         node[2].parent = node + 1;
 836         node[1].bitmask = htonl(0x80000000);
 837         node[0].root = 1;
 838         node[1].root = 1;
 839         node[2].root = 1;
 840         node[0].offset = ADF_OFF_BITS >> 5;
 841         node[1].offset = ADF_OFF_BITS >> 5;
 842         node[2].offset = ADF_OFF_BITS >> 5;
 843         node[1].left = &node[0];
 844         node[1].right = &node[2];
 845         node[0].addrkey = (u_32_t *)softr->zeros;
 846         node[2].addrkey = (u_32_t *)softr->ones;
 847 #ifdef RDX_DEBUG
 848         (void) strcpy(node[0].name, "0_ROOT");
 849         (void) strcpy(node[1].name, "1_ROOT");
 850         (void) strcpy(node[2].name, "2_ROOT");
 851 #endif
 852
 853         ptr->addaddr = ipf_rx_addroute;
 854         ptr->deladdr = ipf_rx_delete;
 855         ptr->lookup = ipf_rx_lookup;
 856         ptr->matchaddr = ipf_rx_match;
 857         ptr->walktree = ipf_rx_walktree;
 858         return 0;
 859 }
 860
 861
 862 /* ------------------------------------------------------------------------ */
 863 /* Function:    ipf_rx_freehead                                             */
 864 /* Returns:     Nil                                                         */
 865 /* Paramters:   head(I)  - pointer to tree head to free                     */
 866 /*                                                                          */
 867 /* This function simply free's up the radix tree head. Prior to calling     */
 868 /* this function, it is expected that the tree will have been emptied.      */
 869 /* ------------------------------------------------------------------------ */
 870 void
 871 ipf_rx_freehead(head)
 872         ipf_rdx_head_t *head;
 873 {
 874         KFREE(head);
 875 }
 876
 877
 878 /* ------------------------------------------------------------------------ */
 879 /* Function:    ipf_rx_create                                               */
 880 /* Parameters:  Nil                                                         */
 881 /*                                                                          */
 882 /* ------------------------------------------------------------------------ */
 883 void *
 884 ipf_rx_create()
 885 {
 886         radix_softc_t *softr;
 887
 888         KMALLOC(softr, radix_softc_t *);
 889         if (softr == NULL)
 890                 return NULL;
 891         bzero((char *)softr, sizeof(*softr));
 892
 893         KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t));
 894         if (softr->zeros == NULL) {
 895                 KFREE(softr);
 896                 return (NULL);
 897         }
 898         softr->ones = softr->zeros + sizeof(addrfamily_t);
 899
 900         return softr;
 901 }
 902
 903
 904 /* ------------------------------------------------------------------------ */
 905 /* Function:    ipf_rx_init                                                 */
 906 /* Returns:     int       - 0 = success (always)                            */
 907 /*                                                                          */
 908 /* ------------------------------------------------------------------------ */
 909 int
 910 ipf_rx_init(ctx)
 911         void *ctx;
 912 {
 913         radix_softc_t *softr = ctx;
 914
 915         memset(softr->zeros, 0, 3 * sizeof(addrfamily_t));
 916         memset(softr->ones, 0xff, sizeof(addrfamily_t));
 917
 918         return (0);
 919 }
 920
 921
 922 /* ------------------------------------------------------------------------ */
 923 /* Function:    ipf_rx_destroy                                              */
 924 /* Returns:     Nil                                                         */
 925 /*                                                                          */
 926 /* ------------------------------------------------------------------------ */
 927 void
 928 ipf_rx_destroy(ctx)
 929         void *ctx;
 930 {
 931         radix_softc_t *softr = ctx;
 932
 933         if (softr->zeros != NULL)
 934                 KFREES(softr->zeros, 3 * sizeof(addrfamily_t));
 935         KFREE(softr);
 936 }
 937
 938 /* ====================================================================== */
 939
 940 #ifdef RDX_DEBUG
 941 /*
 942  * To compile this file as a standalone test unit, use -DRDX_DEBUG=1
 943  */
 944 #define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name)
 945 #define GNAME(y)        ((y) == NULL ? "NULL" : NAME(y))
 946
 947 typedef struct myst {
 948         struct ipf_rdx_node nodes[2];
 949         addrfamily_t    dst;
 950         addrfamily_t    mask;
 951         struct myst     *next;
 952         int             printed;
 953 } myst_t;
 954
 955 typedef struct tabe_s {
 956         char    *host;
 957         char    *mask;
 958         char    *what;
 959 } tabe_t;
 960
 961 tabe_t builtin[] = {
 962 #if 1
 963         { "192:168:100::0",     "48",                   "d" },
 964         { "192:168:100::2",     "128",                  "d" },
 965 #else
 966         { "127.192.0.0",        "255.255.255.0",        "d" },
 967         { "127.128.0.0",        "255.255.255.0",        "d" },
 968         { "127.96.0.0",         "255.255.255.0",        "d" },
 969         { "127.80.0.0",         "255.255.255.0",        "d" },
 970         { "127.72.0.0",         "255.255.255.0",        "d" },
 971         { "127.64.0.0",         "255.255.255.0",        "d" },
 972         { "127.56.0.0",         "255.255.255.0",        "d" },
 973         { "127.48.0.0",         "255.255.255.0",        "d" },
 974         { "127.40.0.0",         "255.255.255.0",        "d" },
 975         { "127.32.0.0",         "255.255.255.0",        "d" },
 976         { "127.24.0.0",         "255.255.255.0",        "d" },
 977         { "127.16.0.0",         "255.255.255.0",        "d" },
 978         { "127.8.0.0",          "255.255.255.0",        "d" },
 979         { "124.0.0.0",          "255.0.0.0",            "d" },
 980         { "125.0.0.0",          "255.0.0.0",            "d" },
 981         { "126.0.0.0",          "255.0.0.0",            "d" },
 982         { "127.0.0.0",          "255.0.0.0",            "d" },
 983         { "10.0.0.0",           "255.0.0.0",            "d" },
 984         { "128.250.0.0",        "255.255.0.0",          "d" },
 985         { "192.168.0.0",        "255.255.0.0",          "d" },
 986         { "192.168.1.0",        "255.255.255.0",        "d" },
 987 #endif
 988         { NULL, NULL, NULL }
 989 };
 990
 991 char *mtable[][1] = {
 992 #if 1
 993         { "192:168:100::2" },
 994         { "192:168:101::2" },
 995 #else
 996         { "9.0.0.0" },
 997         { "9.0.0.1" },
 998         { "11.0.0.0" },
 999         { "11.0.0.1" },
1000         { "127.0.0.1" },
1001         { "127.0.1.0" },
1002         { "255.255.255.0" },
1003         { "126.0.0.1" },
1004         { "128.251.0.0" },
1005         { "128.251.0.1" },
1006         { "128.251.255.255" },
1007         { "129.250.0.0" },
1008         { "129.250.0.1" },
1009         { "192.168.255.255" },
1010 #endif
1011         { NULL }
1012 };
1013
1014
1015 int forder[22] = {
1016         14, 13, 12,  5, 10,  3, 19,  7,  4, 20,  8,
1017          2, 17,  9, 16, 11, 15,  1,  6, 18,  0, 21
1018 };
1019
1020 static int nodecount = 0;
1021 myst_t *myst_top = NULL;
1022 tabe_t *ttable = NULL;
1023
1024 void add_addr(ipf_rdx_head_t *, int , int);
1025 void checktree(ipf_rdx_head_t *);
1026 void delete_addr(ipf_rdx_head_t *rnh, int item);
1027 void dumptree(ipf_rdx_head_t *rnh);
1028 void nodeprinter(ipf_rdx_node_t *, void *);
1029 void printroots(ipf_rdx_head_t *);
1030 void random_add(ipf_rdx_head_t *);
1031 void random_delete(ipf_rdx_head_t *);
1032 void test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int);
1033
1034
1035 static void
1036 ipf_rx_freenode(node, arg)
1037         ipf_rdx_node_t *node;
1038         void *arg;
1039 {
1040         ipf_rdx_head_t *head = arg;
1041         ipf_rdx_node_t *rv;
1042         myst_t *stp;
1043
1044         stp = (myst_t *)node;
1045         rv = ipf_rx_delete(head, &stp->dst, &stp->mask);
1046         if (rv != NULL) {
1047                 free(rv);
1048         }
1049 }
1050
1051
1052 const char *
1053 addrname(ap)
1054         addrfamily_t *ap;
1055 {
1056         static char name[80];
1057         const char *txt;
1058
1059         bzero((char *)name, sizeof(name));
1060         txt =  inet_ntop(ap->adf_family, &ap->adf_addr, name,
1061                          sizeof(name));
1062         return txt;
1063 }
1064
1065
1066 void
1067 fill6bits(bits, msk)
1068         int bits;
1069         u_int *msk;
1070 {
1071         if (bits == 0) {
1072                 msk[0] = 0;
1073                 msk[1] = 0;
1074                 msk[2] = 0;
1075                 msk[3] = 0;
1076                 return;
1077         }
1078
1079         msk[0] = 0xffffffff;
1080         msk[1] = 0xffffffff;
1081         msk[2] = 0xffffffff;
1082         msk[3] = 0xffffffff;
1083
1084         if (bits == 128)
1085                 return;
1086         if (bits > 96) {
1087                 msk[3] = htonl(msk[3] << (128 - bits));
1088         } else if (bits > 64) {
1089                 msk[3] = 0;
1090                 msk[2] = htonl(msk[2] << (96 - bits));
1091         } else if (bits > 32) {
1092                 msk[3] = 0;
1093                 msk[2] = 0;
1094                 msk[1] = htonl(msk[1] << (64 - bits));
1095         } else {
1096                 msk[3] = 0;
1097                 msk[2] = 0;
1098                 msk[1] = 0;
1099                 msk[0] = htonl(msk[0] << (32 - bits));
1100         }
1101 }
1102
1103
1104 void
1105 setaddr(afp, str)
1106         addrfamily_t *afp;
1107         char *str;
1108 {
1109
1110         bzero((char *)afp, sizeof(*afp));
1111
1112         if (strchr(str, ':') == NULL) {
1113                 afp->adf_family = AF_INET;
1114                 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1115         } else {
1116                 afp->adf_family = AF_INET6;
1117                 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1118         }
1119         inet_pton(afp->adf_family, str, &afp->adf_addr);
1120 }
1121
1122
1123 void
1124 setmask(afp, str)
1125         addrfamily_t *afp;
1126         char *str;
1127 {
1128         if (strchr(str, '.') != NULL) {
1129                 afp->adf_addr.in4.s_addr = inet_addr(str);
1130                 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1131         } else if (afp->adf_family == AF_INET) {
1132                 afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str)));
1133                 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1134         } else if (afp->adf_family == AF_INET6) {
1135                 fill6bits(atoi(str), afp->adf_addr.i6);
1136                 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1137         }
1138 }
1139
1140
1141 void
1142 nodeprinter(node, arg)
1143         ipf_rdx_node_t *node;
1144         void *arg;
1145 {
1146         myst_t *stp = (myst_t *)node;
1147
1148         printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n",
1149                 node[0].name,
1150                 GNAME(node[1].left), GNAME(node[1].right),
1151                 GNAME(node[0].parent), GNAME(node[1].parent),
1152                 addrname(&stp->dst), node[0].maskbitcount);
1153         if (stp->printed == -1)
1154                 printf("!!! %d\n", stp->printed);
1155         else
1156                 stp->printed = 1;
1157 }
1158
1159
1160 void
1161 printnode(stp)
1162         myst_t *stp;
1163 {
1164         ipf_rdx_node_t *node = &stp->nodes[0];
1165
1166         if (stp->nodes[0].index > 0)
1167                 stp = (myst_t *)&stp->nodes[-1];
1168
1169         printf("Node %-9.9s ", node[0].name);
1170         printf("L %-9.9s ", GNAME(node[1].left));
1171         printf("R %-9.9s ", GNAME(node[1].right));
1172         printf("P %9.9s", GNAME(node[0].parent));
1173         printf("/%-9.9s ", GNAME(node[1].parent));
1174         printf("%s P%d\n", addrname(&stp->dst), stp->printed);
1175 }
1176
1177
1178 void
1179 buildtab(void)
1180 {
1181         char line[80], *s;
1182         tabe_t *tab;
1183         int lines;
1184         FILE *fp;
1185
1186         lines = 0;
1187         fp = fopen("hosts", "r");
1188
1189         while (fgets(line, sizeof(line), fp) != NULL) {
1190                 s = strchr(line, '\n');
1191                 if (s != NULL)
1192                         *s = '\0';
1193                 lines++;
1194                 if (lines == 1)
1195                         tab = malloc(sizeof(*tab) * 2);
1196                 else
1197                         tab = realloc(tab, (lines + 1) * sizeof(*tab));
1198                 tab[lines - 1].host = strdup(line);
1199                 s = strchr(tab[lines - 1].host, '/');
1200                 *s++ = '\0';
1201                 tab[lines - 1].mask = s;
1202                 tab[lines - 1].what = "d";
1203         }
1204         fclose(fp);
1205
1206         tab[lines].host = NULL;
1207         tab[lines].mask = NULL;
1208         tab[lines].what = NULL;
1209         ttable = tab;
1210 }
1211
1212
1213 void
1214 printroots(rnh)
1215         ipf_rdx_head_t *rnh;
1216 {
1217         printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1218                 GNAME(&rnh->nodes[0]),
1219                 rnh->nodes[0].index, GNAME(rnh->nodes[0].parent),
1220                 GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right));
1221         printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1222                 GNAME(&rnh->nodes[1]),
1223                 rnh->nodes[1].index, GNAME(rnh->nodes[1].parent),
1224                 GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right));
1225         printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1226                 GNAME(&rnh->nodes[2]),
1227                 rnh->nodes[2].index, GNAME(rnh->nodes[2].parent),
1228                 GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right));
1229 }
1230
1231
1232 int
1233 main(int argc, char *argv[])
1234 {
1235         addrfamily_t af;
1236         ipf_rdx_head_t *rnh;
1237         radix_softc_t *ctx;
1238         int j;
1239         int i;
1240
1241         rnh = NULL;
1242
1243         buildtab();
1244         ctx = ipf_rx_create();
1245         ipf_rx_init(ctx);
1246         ipf_rx_inithead(ctx, &rnh);
1247
1248         printf("=== ADD-0 ===\n");
1249         for (i = 0; ttable[i].host != NULL; i++) {
1250                 add_addr(rnh, i, i);
1251                 checktree(rnh);
1252         }
1253         printroots(rnh);
1254         ipf_rx_walktree(rnh, nodeprinter, NULL);
1255         printf("=== DELETE-0 ===\n");
1256         for (i = 0; ttable[i].host != NULL; i++) {
1257                 delete_addr(rnh, i);
1258                 printroots(rnh);
1259                 ipf_rx_walktree(rnh, nodeprinter, NULL);
1260         }
1261         printf("=== ADD-1 ===\n");
1262         for (i = 0; ttable[i].host != NULL; i++) {
1263                 setaddr(&af, ttable[i].host);
1264                 add_addr(rnh, i, i); /*forder[i]); */
1265                 checktree(rnh);
1266         }
1267         dumptree(rnh);
1268         ipf_rx_walktree(rnh, nodeprinter, NULL);
1269         printf("=== TEST-1 ===\n");
1270         for (i = 0; ttable[i].host != NULL; i++) {
1271                 setaddr(&af, ttable[i].host);
1272                 test_addr(rnh, i, &af, -1);
1273         }
1274
1275         printf("=== TEST-2 ===\n");
1276         for (i = 0; mtable[i][0] != NULL; i++) {
1277                 setaddr(&af, mtable[i][0]);
1278                 test_addr(rnh, i, &af, -1);
1279         }
1280         printf("=== DELETE-1 ===\n");
1281         for (i = 0; ttable[i].host != NULL; i++) {
1282                 if (ttable[i].what[0] != 'd')
1283                         continue;
1284                 delete_addr(rnh, i);
1285                 for (j = 0; ttable[j].host != NULL; j++) {
1286                         setaddr(&af, ttable[j].host);
1287                         test_addr(rnh, i, &af, 3);
1288                 }
1289                 printroots(rnh);
1290                 ipf_rx_walktree(rnh, nodeprinter, NULL);
1291         }
1292
1293         dumptree(rnh);
1294
1295         printf("=== ADD-2 ===\n");
1296         random_add(rnh);
1297         checktree(rnh);
1298         dumptree(rnh);
1299         ipf_rx_walktree(rnh, nodeprinter, NULL);
1300         printf("=== DELETE-2 ===\n");
1301         random_delete(rnh);
1302         checktree(rnh);
1303         dumptree(rnh);
1304
1305         ipf_rx_walktree(rnh, ipf_rx_freenode, rnh);
1306
1307         return 0;
1308 }
1309
1310
1311 void
1312 dumptree(rnh)
1313         ipf_rdx_head_t *rnh;
1314 {
1315         myst_t *stp;
1316
1317         printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n");
1318         printroots(rnh);
1319         for (stp = myst_top; stp; stp = stp->next)
1320                 printnode(stp);
1321         printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
1322 }
1323
1324
1325 void
1326 test_addr(rnh, pref, addr, limit)
1327         ipf_rdx_head_t *rnh;
1328         int pref;
1329         addrfamily_t *addr;
1330 {
1331         static int extras[14] = { 0, -1, 1, 3, 5, 8, 9,
1332                                   15, 16, 19, 255, 256, 65535, 65536
1333         };
1334         ipf_rdx_node_t *rn;
1335         addrfamily_t af;
1336         char name[80];
1337         myst_t *stp;
1338         int i;
1339
1340         memset(&af, 0, sizeof(af));
1341 #if 0
1342         if (limit < 0 || limit > 14)
1343                 limit = 14;
1344
1345         for (i = 0; i < limit; i++) {
1346                 if (ttable[i].host == NULL)
1347                         break;
1348                 setaddr(&af, ttable[i].host);
1349                 printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af));
1350                 rn = ipf_rx_match(rnh, &af);
1351                 stp = (myst_t *)rn;
1352                 printf(" = %s (%s/%d)\n", GNAME(rn),
1353                         rn ? addrname(&stp->dst) : "NULL",
1354                         rn ? rn->maskbitcount : 0);
1355         }
1356 #else
1357         printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr));
1358         rn = ipf_rx_match(rnh, addr);
1359         stp = (myst_t *)rn;
1360         printf(" = %s (%s/%d)\n", GNAME(rn),
1361                 rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0);
1362 #endif
1363 }
1364
1365
1366 void
1367 delete_addr(rnh, item)
1368         ipf_rdx_head_t *rnh;
1369         int item;
1370 {
1371         ipf_rdx_node_t *rn;
1372         addrfamily_t mask;
1373         addrfamily_t af;
1374         myst_t **pstp;
1375         myst_t *stp;
1376
1377         memset(&af, 0, sizeof(af));
1378         memset(&mask, 0, sizeof(mask));
1379         setaddr(&af, ttable[item].host);
1380         mask.adf_family = af.adf_family;
1381         setmask(&mask, ttable[item].mask);
1382
1383         printf("DELETE(%s)\n", addrname(&af));
1384         rn = ipf_rx_delete(rnh, &af, &mask);
1385         if (rn == NULL) {
1386                 printf("FAIL LOOKUP DELETE\n");
1387                 checktree(rnh);
1388                 for (stp = myst_top; stp != NULL; stp = stp->next)
1389                         if (stp->printed != -1)
1390                                 stp->printed = -2;
1391                 ipf_rx_walktree(rnh, nodeprinter, NULL);
1392                 dumptree(rnh);
1393                 abort();
1394         }
1395         printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn));
1396
1397         for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next)
1398                 if (stp == (myst_t *)rn)
1399                         break;
1400         stp->printed = -1;
1401         stp->nodes[0].parent = &stp->nodes[0];
1402         stp->nodes[1].parent = &stp->nodes[1];
1403         *pstp = stp->next;
1404         free(stp);
1405         nodecount--;
1406         checktree(rnh);
1407 }
1408
1409
1410 void
1411 add_addr(rnh, n, item)
1412         ipf_rdx_head_t *rnh;
1413         int n, item;
1414 {
1415         ipf_rdx_node_t *rn;
1416         myst_t *stp;
1417
1418         stp = calloc(1, sizeof(*stp));
1419         rn = (ipf_rdx_node_t *)stp;
1420         setaddr(&stp->dst, ttable[item].host);
1421         stp->mask.adf_family = stp->dst.adf_family;
1422         setmask(&stp->mask, ttable[item].mask);
1423         stp->next = myst_top;
1424         myst_top = stp;
1425         (void) sprintf(rn[0].name, "_BORN.0");
1426         (void) sprintf(rn[1].name, "_BORN.1");
1427         rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes);
1428         (void) sprintf(rn[0].name, "%d_NODE.0", item);
1429         (void) sprintf(rn[1].name, "%d_NODE.1", item);
1430         printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name);
1431         nodecount++;
1432         checktree(rnh);
1433 }
1434
1435
1436 void
1437 checktree(ipf_rdx_head_t *head)
1438 {
1439         myst_t *s1;
1440         ipf_rdx_node_t *rn;
1441
1442         if (nodecount <= 1)
1443                 return;
1444
1445         for (s1 = myst_top; s1 != NULL; s1 = s1->next) {
1446                 int fault = 0;
1447                 if (s1->printed == -1)
1448                         continue;
1449                 rn = &s1->nodes[1];
1450                 if (rn->right->parent != rn)
1451                         fault |= 1;
1452                 if (rn->left->parent != rn)
1453                         fault |= 2;
1454                 if (rn->parent->left != rn && rn->parent->right != rn)
1455                         fault |= 4;
1456                 if (fault != 0) {
1457                         printf("FAULT %#x %s\n", fault, rn->name);
1458                         dumptree(head);
1459                         ipf_rx_walktree(head, nodeprinter, NULL);
1460                         fflush(stdout);
1461                         fflush(stderr);
1462                         printf("--\n");
1463                         abort();
1464                 }
1465         }
1466 }
1467
1468
1469 int *
1470 randomize(int *pnitems)
1471 {
1472         int *order;
1473         int nitems;
1474         int choice;
1475         int j;
1476         int i;
1477
1478         nitems = sizeof(ttable) / sizeof(ttable[0]);
1479         *pnitems = nitems;
1480         order = calloc(nitems, sizeof(*order));
1481         srandom(getpid() * time(NULL));
1482         memset(order, 0xff, nitems * sizeof(*order));
1483         order[21] = 21;
1484         for (i = 0; i < nitems - 1; i++) {
1485                 do {
1486                         choice = rand() % (nitems - 1);
1487                         for (j = 0; j < nitems; j++)
1488                                 if (order[j] == choice)
1489                                         break;
1490                 } while (j != nitems);
1491                 order[i] = choice;
1492         }
1493
1494         return order;
1495 }
1496
1497
1498 void
1499 random_add(rnh)
1500         ipf_rdx_head_t *rnh;
1501 {
1502         int *order;
1503         int nitems;
1504         int i;
1505
1506         order = randomize(&nitems);
1507
1508         for (i = 0; i < nitems - 1; i++) {
1509                 add_addr(rnh, i, order[i]);
1510                 checktree(rnh);
1511         }
1512
1513         free(order);
1514 }
1515
1516
1517 void
1518 random_delete(rnh)
1519         ipf_rdx_head_t *rnh;
1520 {
1521         int *order;
1522         int nitems;
1523         int i;
1524
1525         order = randomize(&nitems);
1526
1527         for (i = 0; i < nitems - 1; i++) {
1528                 delete_addr(rnh, i);
1529                 checktree(rnh);
1530         }
1531
1532         free(order);
1533 }
1534 #endif /* RDX_DEBUG */