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