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