2 * Copyright (C) 2012 by Darren Reed.
4 * See the IPFILTER.LICENCE file for details on licencing.
8 #include <sys/socket.h>
10 #include <netinet/in.h>
18 #include "netinet/ip_compat.h"
19 #include "netinet/ip_fil.h"
21 # include <arpa/inet.h>
25 #include "netinet/radix_ipf.h"
27 #define ADF_OFF offsetof(addrfamily_t, adf_addr)
28 #define ADF_OFF_BITS (ADF_OFF << 3)
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 *,
39 static ipf_rdx_node_t *ipf_rx_match __P((ipf_rdx_head_t *, addrfamily_t *));
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.
52 /* ------------------------------------------------------------------------ */
53 /* Function: count_mask_bits */
54 /* Returns: number of consecutive bits starting at "mask". */
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 /* ------------------------------------------------------------------------ */
62 count_mask_bits(mask, lastp)
66 u_32_t *mp = (u_32_t *)&mask->adf_addr;
71 mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr);
72 for (; mlen > 0; mlen -= 4, mp++) {
73 if ((m = ntohl(*mp)) == 0)
77 for (; m & 0x80000000; m <<= 1)
85 /* ------------------------------------------------------------------------ */
86 /* Function: buildnodes */
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. */
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 /* ------------------------------------------------------------------------ */
99 buildnodes(addr, mask, nodes)
100 addrfamily_t *addr, *mask;
101 ipf_rdx_node_t nodes[2];
109 maskbits = count_mask_bits(mask, &last);
114 masklen = last - (u_32_t *)mask;
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;
132 (void) strcpy(nodes[0].name, "_BUILD.0");
133 (void) strcpy(nodes[1].name, "_BUILD.1");
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 */
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(tree, addr)
149 ipf_rdx_node_t *tree;
154 for (cur = tree; cur->index >= 0;) {
155 if (cur->bitmask & addr[cur->offset]) {
166 /* ------------------------------------------------------------------------ */
167 /* Function: ipf_rx_match */
168 /* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
169 /* added to the tree. */
170 /* Paramters: head(I) - pointer to tree head to search */
171 /* addr(I) - pointer to address to find */
173 /* Search the radix tree for the best match to the address pointed to by */
174 /* "addr" and return a pointer to that node. This search will not match the */
175 /* address information stored in either of the root leaves as neither of */
176 /* them are considered to be part of the tree of data being stored. */
177 /* ------------------------------------------------------------------------ */
178 static ipf_rdx_node_t *
179 ipf_rx_match(head, addr)
180 ipf_rdx_head_t *head;
183 ipf_rdx_mask_t *masknode;
184 ipf_rdx_node_t *prev;
185 ipf_rdx_node_t *node;
195 end = (u_32_t *)((u_char *)addr + len);
196 node = ipf_rx_find_addr(head->root, (u_32_t *)addr);
199 * Search the dupkey list for a potential match.
201 for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) {
202 i = cur[0].addroff - cur[0].addrkey;
203 data = cur[0].addrkey + i;
204 mask = cur[0].maskkey + i;
205 key = (u_32_t *)addr + i;
206 for (; key < end; data++, key++, mask++)
207 if ((*key & *mask) != *data)
209 if ((end == key) && (cur->root == 0))
210 return (cur); /* Equal keys */
213 key = (u_32_t *)addr;
215 for (node = prev; node->root == 0; node = node->parent) {
217 * We know that the node hasn't matched so therefore only
218 * the entries in the mask list are searched, not the top
219 * node nor the dupkey list.
221 masknode = node->masks;
222 for (; masknode != NULL; masknode = masknode->next) {
223 if (masknode->maskbitcount > node->maskbitcount)
225 cur = masknode->node;
226 for (i = ADF_OFF >> 2; i <= node->offset; i++) {
227 if ((key[i] & masknode->mask[i]) ==
238 /* ------------------------------------------------------------------------ */
239 /* Function: ipf_rx_lookup */
240 /* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
241 /* added to the tree. */
242 /* Paramters: head(I) - pointer to tree head to search */
243 /* addr(I) - address part of the key to match */
244 /* mask(I) - netmask part of the key to match */
246 /* ipf_rx_lookup searches for an exact match on (addr,mask). The intention */
247 /* is to see if a given key is in the tree, not to see if a route exists. */
248 /* ------------------------------------------------------------------------ */
250 ipf_rx_lookup(head, addr, mask)
251 ipf_rdx_head_t *head;
252 addrfamily_t *addr, *mask;
254 ipf_rdx_node_t *found;
255 ipf_rdx_node_t *node;
259 found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
260 if (found->root == 1)
264 * It is possible to find a matching address in the tree but for the
265 * netmask to not match. If the netmask does not match and there is
266 * no list of alternatives present at dupkey, return a failure.
268 count = count_mask_bits(mask, NULL);
269 if (count != found->maskbitcount && found->dupkey == NULL)
272 akey = (u_32_t *)addr;
273 if ((found->addrkey[found->offset] & found->maskkey[found->offset]) !=
277 if (found->dupkey != NULL) {
279 while (node != NULL && node->maskbitcount != count)
289 /* ------------------------------------------------------------------------ */
290 /* Function: ipf_rx_attach_mask */
292 /* Parameters: node(I) - pointer to a radix tree node */
293 /* mask(I) - pointer to mask structure to add */
295 /* Add the netmask to the given node in an ordering where the most specific */
296 /* netmask is at the top of the list. */
297 /* ------------------------------------------------------------------------ */
299 ipf_rx_attach_mask(node, mask)
300 ipf_rdx_node_t *node;
301 ipf_rdx_mask_t *mask;
306 for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next)
307 if (m->maskbitcount < mask->maskbitcount)
314 /* ------------------------------------------------------------------------ */
315 /* Function: ipf_rx_insert */
316 /* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
317 /* added to the tree. */
318 /* Paramters: head(I) - pointer to tree head to add nodes to */
319 /* nodes(I) - pointer to radix nodes to be added */
320 /* dup(O) - set to 1 if node is a duplicate, else 0. */
322 /* Add the new radix tree entry that owns nodes[] to the tree given by head.*/
323 /* If there is already a matching key in the table, "dup" will be set to 1 */
324 /* and the existing node pointer returned if there is a complete key match. */
325 /* A complete key match is a matching of all key data that is presented by */
326 /* by the netmask. */
327 /* ------------------------------------------------------------------------ */
328 static ipf_rdx_node_t *
329 ipf_rx_insert(head, nodes, dup)
330 ipf_rdx_head_t *head;
331 ipf_rdx_node_t nodes[2];
334 ipf_rdx_mask_t **pmask;
335 ipf_rdx_node_t *node;
336 ipf_rdx_node_t *prev;
337 ipf_rdx_mask_t *mask;
351 addr = nodes[0].addrkey;
353 node = ipf_rx_find_addr(head->root, addr);
354 len = ((addrfamily_t *)addr)->adf_len;
355 key = (u_32_t *)&((addrfamily_t *)addr)->adf_addr;
356 data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr;
357 end = (u_32_t *)((u_char *)addr + len);
358 for (nlen = 0; key < end; data++, key++, nlen += 32)
363 return (node); /* Equal keys */
367 bits = (ntohl(*data) ^ ntohl(*key));
368 for (; bits != 0; nlen++) {
369 if ((bits & 0x80000000) != 0)
373 nlen += ADF_OFF_BITS;
374 nodes[1].index = nlen;
375 nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f));
376 nodes[0].offset = nlen / 32;
377 nodes[1].offset = nlen / 32;
380 * Walk through the tree and look for the correct place to attach
381 * this node. ipf_rx_fin_addr is not used here because the place
382 * to attach this node may be an internal node (same key, different
383 * netmask.) Additionally, the depth of the search is forcibly limited
384 * here to not exceed the netmask, so that a short netmask will be
385 * added higher up the tree even if there are lower branches.
388 key = nodes[0].addrkey;
391 if (key[cur->offset] & cur->bitmask) {
396 } while (nlen > (unsigned)cur->index);
398 if ((key[prev->offset] & prev->bitmask) == 0) {
399 prev->left = &nodes[1];
401 prev->right = &nodes[1];
403 cur->parent = &nodes[1];
404 nodes[1].parent = prev;
405 if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) {
406 nodes[1].right = cur;
408 nodes[1].right = &nodes[0];
412 nodeoff = nodes[0].offset;
413 nodekey = nodes[0].addrkey[nodeoff];
414 nodemask = nodes[0].lastmask;
415 nodebits = nodes[0].maskbitcount;
418 * Find the node up the tree with the largest pattern that still
419 * matches the node being inserted to see if this mask can be
422 for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) {
423 if (cur->maskbitcount <= nodebits)
425 if (((cur - 1)->addrkey[nodeoff] & nodemask) != nodekey)
430 KMALLOC(mask, ipf_rdx_mask_t *);
433 bzero(mask, sizeof(*mask));
435 mask->node = &nodes[0];
436 mask->maskbitcount = nodebits;
437 mask->mask = nodes[0].maskkey;
438 nodes[0].mymask = mask;
443 for (pmask = &prev->masks; (m = *pmask) != NULL;
445 if (m->maskbitcount < nodebits)
450 * No higher up nodes qualify, so attach mask locally.
452 pmask = &nodes[0].masks;
458 * Search the mask list on each child to see if there are any masks
459 * there that can be moved up to this newly inserted node.
461 cur = nodes[1].right;
462 if (cur->root == 0) {
463 for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
464 if (mask->maskbitcount < nodebits) {
466 ipf_rx_attach_mask(&nodes[0], mask);
473 if (cur->root == 0 && cur != &nodes[0]) {
474 for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
475 if (mask->maskbitcount < nodebits) {
477 ipf_rx_attach_mask(&nodes[0], mask);
486 /* ------------------------------------------------------------------------ */
487 /* Function: ipf_rx_addroute */
488 /* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
489 /* added to the tree. */
490 /* Paramters: head(I) - pointer to tree head to search */
491 /* addr(I) - address portion of "route" to add */
492 /* mask(I) - netmask portion of "route" to add */
493 /* nodes(I) - radix tree data nodes inside allocate structure */
495 /* Attempt to add a node to the radix tree. The key for the node is the */
496 /* (addr,mask). No memory allocation for the radix nodes themselves is */
497 /* performed here, the data structure that this radix node is being used to */
498 /* find is expected to house the node data itself however the call to */
499 /* ipf_rx_insert() will attempt to allocate memory in order for netmask to */
500 /* be promoted further up the tree. */
501 /* In this case, the ip_pool_node_t structure from ip_pool.h contains both */
502 /* the key material (addr,mask) and the radix tree nodes[]. */
504 /* The mechanics of inserting the node into the tree is handled by the */
505 /* function ipf_rx_insert() above. Here, the code deals with the case */
506 /* where the data to be inserted is a duplicate. */
507 /* ------------------------------------------------------------------------ */
509 ipf_rx_addroute(head, addr, mask, nodes)
510 ipf_rdx_head_t *head;
511 addrfamily_t *addr, *mask;
512 ipf_rdx_node_t *nodes;
514 ipf_rdx_node_t *node;
515 ipf_rdx_node_t *prev;
519 buildnodes(addr, mask, nodes);
520 x = ipf_rx_insert(head, nodes, &dup);
528 * The duplicate list is kept sorted with the longest
529 * mask at the top, meaning that the most specific entry
530 * in the listis found first. This list thus allows for
531 * duplicates such as 128.128.0.0/32 and 128.128.0.0/16.
533 while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) {
539 * Is it a complete duplicate? If so, return NULL and
540 * fail the insert. Otherwise, insert it into the list
541 * of netmasks active for this key.
543 if ((x != NULL) && (x->maskbitcount == node->maskbitcount))
548 prev->dupkey = &nodes[0];
549 nodes[0].parent = prev;
551 x->parent = &nodes[0];
553 nodes[0].dupkey = x->dupkey;
555 nodes[0].parent = prev;
556 x->parent = &nodes[0];
558 prev->left = &nodes[0];
560 prev->right = &nodes[0];
568 /* ------------------------------------------------------------------------ */
569 /* Function: ipf_rx_delete */
570 /* Returns: ipf_rdx_node_t * - NULL on error, else node removed from */
572 /* Paramters: head(I) - pointer to tree head to search */
573 /* addr(I) - pointer to the address part of the key */
574 /* mask(I) - pointer to the netmask part of the key */
576 /* Search for an entry in the radix tree that is an exact match for (addr, */
577 /* mask) and remove it if it exists. In the case where (addr,mask) is a not */
578 /* a unique key, the tree structure itself is not changed - only the list */
579 /* of duplicate keys. */
580 /* ------------------------------------------------------------------------ */
582 ipf_rx_delete(head, addr, mask)
583 ipf_rdx_head_t *head;
584 addrfamily_t *addr, *mask;
586 ipf_rdx_mask_t **pmask;
587 ipf_rdx_node_t *parent;
588 ipf_rdx_node_t *found;
589 ipf_rdx_node_t *prev;
590 ipf_rdx_node_t *node;
595 found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
598 if (found->root == 1)
600 count = count_mask_bits(mask, NULL);
601 parent = found->parent;
602 if (found->dupkey != NULL) {
604 while (node != NULL && node->maskbitcount != count)
610 * Remove from the dupkey list. Here, "parent" is
611 * the previous node on the list (rather than tree)
612 * and "dupkey" is the next node on the list.
614 parent = node->parent;
615 parent->dupkey = node->dupkey;
616 node->dupkey->parent = parent;
620 * When removing the top node of the dupkey list,
621 * the pointers at the top of the list that point
622 * to other tree nodes need to be preserved and
623 * any children must have their parent updated.
626 node->parent = found->parent;
627 node->right = found->right;
628 node->left = found->left;
629 found->right->parent = node;
630 found->left->parent = node;
631 if (parent->left == found)
637 if (count != found->maskbitcount)
640 * Remove the node from the tree and reconnect the subtree
644 * If there is a tree to the left, look for something to
645 * attach in place of "found".
648 cur = parent->parent;
649 if (parent != found + 1) {
650 if ((found + 1)->parent->right == found + 1)
651 (found + 1)->parent->right = parent;
653 (found + 1)->parent->left = parent;
654 if (cur->right == parent) {
655 if (parent->left == found) {
656 cur->right = parent->right;
657 } else if (parent->left != parent - 1) {
658 cur->right = parent->left;
660 cur->right = parent - 1;
662 cur->right->parent = cur;
664 if (parent->right == found) {
665 cur->left = parent->left;
666 } else if (parent->right != parent - 1) {
667 cur->left = parent->right;
669 cur->left = parent - 1;
671 cur->left->parent = cur;
673 parent->left = (found + 1)->left;
674 if ((found + 1)->right != parent)
675 parent->right = (found + 1)->right;
676 parent->left->parent = parent;
677 parent->right->parent = parent;
678 parent->parent = (found + 1)->parent;
680 parent->bitmask = prev->bitmask;
681 parent->offset = prev->offset;
682 parent->index = prev->index;
685 * We found an edge node.
687 cur = parent->parent;
688 if (cur->left == parent) {
689 if (parent->left == found) {
690 cur->left = parent->right;
691 parent->right->parent = cur;
693 cur->left = parent->left;
694 parent->left->parent = cur;
697 if (parent->right != found) {
698 cur->right = parent->right;
699 parent->right->parent = cur;
701 cur->right = parent->left;
702 prev->left->parent = cur;
709 * Remove mask associated with this node.
711 for (cur = parent; cur->root == 0; cur = cur->parent) {
714 if (cur->maskbitcount <= found->maskbitcount)
716 if (((cur - 1)->addrkey[found->offset] & found->bitmask) !=
717 found->addrkey[found->offset])
719 for (pm = &cur->masks; (m = *pm) != NULL; )
720 if (m->node == cur) {
727 KFREE(found->mymask);
730 * Masks that have been brought up to this node from below need to
733 for (pmask = &parent->masks; (m = *pmask) != NULL; ) {
738 if (found->addrkey[cur->offset] & cur->lastmask) {
739 ipf_rx_attach_mask(parent->right, m);
740 } else if (parent->left != found) {
741 ipf_rx_attach_mask(parent->left, m);
749 /* ------------------------------------------------------------------------ */
750 /* Function: ipf_rx_walktree */
752 /* Paramters: head(I) - pointer to tree head to search */
753 /* walker(I) - function to call for each node in the tree */
754 /* arg(I) - parameter to pass to walker, in addition to the */
757 /* A standard tree walking function except that it is iterative, rather */
758 /* than recursive and tracks the next node in case the "walker" function */
759 /* should happen to delete and free the current node. It thus goes without */
760 /* saying that the "walker" function is not permitted to cause any change */
761 /* in the validity of the data found at either the left or right child. */
762 /* ------------------------------------------------------------------------ */
764 ipf_rx_walktree(head, walker, arg)
765 ipf_rdx_head_t *head;
766 radix_walk_func_t walker;
769 ipf_rdx_node_t *next;
770 ipf_rdx_node_t *node = head->root;
771 ipf_rdx_node_t *base;
773 while (node->index >= 0)
778 while ((node->parent->right == node) && (node->root == 0))
781 for (node = node->parent->right; node->index >= 0; )
785 for (node = base; node != NULL; node = base) {
797 /* ------------------------------------------------------------------------ */
798 /* Function: ipf_rx_inithead */
799 /* Returns: int - 0 = success, else failure */
800 /* Paramters: softr(I) - pointer to radix context */
801 /* headp(O) - location for where to store allocated tree head */
803 /* This function allocates and initialises a radix tree head structure. */
804 /* As a traditional radix tree, node 0 is used as the "0" sentinel and node */
805 /* "2" is used as the all ones sentinel, leaving node "1" as the root from */
806 /* which the tree is hung with node "0" on its left and node "2" to the */
807 /* right. The context, "softr", is used here to provide a common source of */
808 /* the zeroes and ones data rather than have one per head. */
809 /* ------------------------------------------------------------------------ */
811 ipf_rx_inithead(softr, headp)
812 radix_softc_t *softr;
813 ipf_rdx_head_t **headp;
816 ipf_rdx_node_t *node;
818 KMALLOC(ptr, ipf_rdx_head_t *);
822 bzero(ptr, sizeof(*ptr));
824 ptr->root = node + 1;
825 node[0].index = ADF_OFF_BITS;
826 node[0].index = -1 - node[0].index;
827 node[1].index = ADF_OFF_BITS;
828 node[2].index = node[0].index;
829 node[0].parent = node + 1;
830 node[1].parent = node + 1;
831 node[2].parent = node + 1;
832 node[1].bitmask = htonl(0x80000000);
836 node[0].offset = ADF_OFF_BITS >> 5;
837 node[1].offset = ADF_OFF_BITS >> 5;
838 node[2].offset = ADF_OFF_BITS >> 5;
839 node[1].left = &node[0];
840 node[1].right = &node[2];
841 node[0].addrkey = (u_32_t *)softr->zeros;
842 node[2].addrkey = (u_32_t *)softr->ones;
844 (void) strcpy(node[0].name, "0_ROOT");
845 (void) strcpy(node[1].name, "1_ROOT");
846 (void) strcpy(node[2].name, "2_ROOT");
849 ptr->addaddr = ipf_rx_addroute;
850 ptr->deladdr = ipf_rx_delete;
851 ptr->lookup = ipf_rx_lookup;
852 ptr->matchaddr = ipf_rx_match;
853 ptr->walktree = ipf_rx_walktree;
858 /* ------------------------------------------------------------------------ */
859 /* Function: ipf_rx_freehead */
861 /* Paramters: head(I) - pointer to tree head to free */
863 /* This function simply free's up the radix tree head. Prior to calling */
864 /* this function, it is expected that the tree will have been emptied. */
865 /* ------------------------------------------------------------------------ */
867 ipf_rx_freehead(head)
868 ipf_rdx_head_t *head;
874 /* ------------------------------------------------------------------------ */
875 /* Function: ipf_rx_create */
876 /* Parameters: Nil */
878 /* ------------------------------------------------------------------------ */
882 radix_softc_t *softr;
884 KMALLOC(softr, radix_softc_t *);
887 bzero((char *)softr, sizeof(*softr));
889 KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t));
890 if (softr->zeros == NULL) {
894 softr->ones = softr->zeros + sizeof(addrfamily_t);
900 /* ------------------------------------------------------------------------ */
901 /* Function: ipf_rx_init */
902 /* Returns: int - 0 = success (always) */
904 /* ------------------------------------------------------------------------ */
909 radix_softc_t *softr = ctx;
911 memset(softr->zeros, 0, 3 * sizeof(addrfamily_t));
912 memset(softr->ones, 0xff, sizeof(addrfamily_t));
918 /* ------------------------------------------------------------------------ */
919 /* Function: ipf_rx_destroy */
922 /* ------------------------------------------------------------------------ */
927 radix_softc_t *softr = ctx;
929 if (softr->zeros != NULL)
930 KFREES(softr->zeros, 3 * sizeof(addrfamily_t));
934 /* ====================================================================== */
938 * To compile this file as a standalone test unit, use -DRDX_DEBUG=1
940 #define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name)
941 #define GNAME(y) ((y) == NULL ? "NULL" : NAME(y))
943 typedef struct myst {
944 struct ipf_rdx_node nodes[2];
951 typedef struct tabe_s {
959 { "192:168:100::0", "48", "d" },
960 { "192:168:100::2", "128", "d" },
962 { "127.192.0.0", "255.255.255.0", "d" },
963 { "127.128.0.0", "255.255.255.0", "d" },
964 { "127.96.0.0", "255.255.255.0", "d" },
965 { "127.80.0.0", "255.255.255.0", "d" },
966 { "127.72.0.0", "255.255.255.0", "d" },
967 { "127.64.0.0", "255.255.255.0", "d" },
968 { "127.56.0.0", "255.255.255.0", "d" },
969 { "127.48.0.0", "255.255.255.0", "d" },
970 { "127.40.0.0", "255.255.255.0", "d" },
971 { "127.32.0.0", "255.255.255.0", "d" },
972 { "127.24.0.0", "255.255.255.0", "d" },
973 { "127.16.0.0", "255.255.255.0", "d" },
974 { "127.8.0.0", "255.255.255.0", "d" },
975 { "124.0.0.0", "255.0.0.0", "d" },
976 { "125.0.0.0", "255.0.0.0", "d" },
977 { "126.0.0.0", "255.0.0.0", "d" },
978 { "127.0.0.0", "255.0.0.0", "d" },
979 { "10.0.0.0", "255.0.0.0", "d" },
980 { "128.250.0.0", "255.255.0.0", "d" },
981 { "192.168.0.0", "255.255.0.0", "d" },
982 { "192.168.1.0", "255.255.255.0", "d" },
987 char *mtable[][1] = {
989 { "192:168:100::2" },
990 { "192:168:101::2" },
1002 { "128.251.255.255" },
1005 { "192.168.255.255" },
1012 14, 13, 12, 5, 10, 3, 19, 7, 4, 20, 8,
1013 2, 17, 9, 16, 11, 15, 1, 6, 18, 0, 21
1016 static int nodecount = 0;
1017 myst_t *myst_top = NULL;
1018 tabe_t *ttable = NULL;
1020 void add_addr(ipf_rdx_head_t *, int , int);
1021 void checktree(ipf_rdx_head_t *);
1022 void delete_addr(ipf_rdx_head_t *rnh, int item);
1023 void dumptree(ipf_rdx_head_t *rnh);
1024 void nodeprinter(ipf_rdx_node_t *, void *);
1025 void printroots(ipf_rdx_head_t *);
1026 void random_add(ipf_rdx_head_t *);
1027 void random_delete(ipf_rdx_head_t *);
1028 void test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int);
1032 ipf_rx_freenode(node, arg)
1033 ipf_rdx_node_t *node;
1036 ipf_rdx_head_t *head = arg;
1040 stp = (myst_t *)node;
1041 rv = ipf_rx_delete(head, &stp->dst, &stp->mask);
1052 static char name[80];
1055 bzero((char *)name, sizeof(name));
1056 txt = inet_ntop(ap->adf_family, &ap->adf_addr, name,
1063 fill6bits(bits, msk)
1075 msk[0] = 0xffffffff;
1076 msk[1] = 0xffffffff;
1077 msk[2] = 0xffffffff;
1078 msk[3] = 0xffffffff;
1083 msk[3] = htonl(msk[3] << (128 - bits));
1084 } else if (bits > 64) {
1086 msk[2] = htonl(msk[2] << (96 - bits));
1087 } else if (bits > 32) {
1090 msk[1] = htonl(msk[1] << (64 - bits));
1095 msk[0] = htonl(msk[0] << (32 - bits));
1106 bzero((char *)afp, sizeof(*afp));
1108 if (strchr(str, ':') == NULL) {
1109 afp->adf_family = AF_INET;
1110 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1112 afp->adf_family = AF_INET6;
1113 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1115 inet_pton(afp->adf_family, str, &afp->adf_addr);
1124 if (strchr(str, '.') != NULL) {
1125 afp->adf_addr.in4.s_addr = inet_addr(str);
1126 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1127 } else if (afp->adf_family == AF_INET) {
1128 afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str)));
1129 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1130 } else if (afp->adf_family == AF_INET6) {
1131 fill6bits(atoi(str), afp->adf_addr.i6);
1132 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1138 nodeprinter(node, arg)
1139 ipf_rdx_node_t *node;
1142 myst_t *stp = (myst_t *)node;
1144 printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n",
1146 GNAME(node[1].left), GNAME(node[1].right),
1147 GNAME(node[0].parent), GNAME(node[1].parent),
1148 addrname(&stp->dst), node[0].maskbitcount);
1149 if (stp->printed == -1)
1150 printf("!!! %d\n", stp->printed);
1160 ipf_rdx_node_t *node = &stp->nodes[0];
1162 if (stp->nodes[0].index > 0)
1163 stp = (myst_t *)&stp->nodes[-1];
1165 printf("Node %-9.9s ", node[0].name);
1166 printf("L %-9.9s ", GNAME(node[1].left));
1167 printf("R %-9.9s ", GNAME(node[1].right));
1168 printf("P %9.9s", GNAME(node[0].parent));
1169 printf("/%-9.9s ", GNAME(node[1].parent));
1170 printf("%s P%d\n", addrname(&stp->dst), stp->printed);
1183 fp = fopen("hosts", "r");
1185 while (fgets(line, sizeof(line), fp) != NULL) {
1186 s = strchr(line, '\n');
1191 tab = malloc(sizeof(*tab) * 2);
1193 tab = realloc(tab, (lines + 1) * sizeof(*tab));
1194 tab[lines - 1].host = strdup(line);
1195 s = strchr(tab[lines - 1].host, '/');
1197 tab[lines - 1].mask = s;
1198 tab[lines - 1].what = "d";
1202 tab[lines].host = NULL;
1203 tab[lines].mask = NULL;
1204 tab[lines].what = NULL;
1211 ipf_rdx_head_t *rnh;
1213 printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1214 GNAME(&rnh->nodes[0]),
1215 rnh->nodes[0].index, GNAME(rnh->nodes[0].parent),
1216 GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right));
1217 printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1218 GNAME(&rnh->nodes[1]),
1219 rnh->nodes[1].index, GNAME(rnh->nodes[1].parent),
1220 GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right));
1221 printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1222 GNAME(&rnh->nodes[2]),
1223 rnh->nodes[2].index, GNAME(rnh->nodes[2].parent),
1224 GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right));
1229 main(int argc, char *argv[])
1232 ipf_rdx_head_t *rnh;
1240 ctx = ipf_rx_create();
1242 ipf_rx_inithead(ctx, &rnh);
1244 printf("=== ADD-0 ===\n");
1245 for (i = 0; ttable[i].host != NULL; i++) {
1246 add_addr(rnh, i, i);
1250 ipf_rx_walktree(rnh, nodeprinter, NULL);
1251 printf("=== DELETE-0 ===\n");
1252 for (i = 0; ttable[i].host != NULL; i++) {
1253 delete_addr(rnh, i);
1255 ipf_rx_walktree(rnh, nodeprinter, NULL);
1257 printf("=== ADD-1 ===\n");
1258 for (i = 0; ttable[i].host != NULL; i++) {
1259 setaddr(&af, ttable[i].host);
1260 add_addr(rnh, i, i); /*forder[i]); */
1264 ipf_rx_walktree(rnh, nodeprinter, NULL);
1265 printf("=== TEST-1 ===\n");
1266 for (i = 0; ttable[i].host != NULL; i++) {
1267 setaddr(&af, ttable[i].host);
1268 test_addr(rnh, i, &af, -1);
1271 printf("=== TEST-2 ===\n");
1272 for (i = 0; mtable[i][0] != NULL; i++) {
1273 setaddr(&af, mtable[i][0]);
1274 test_addr(rnh, i, &af, -1);
1276 printf("=== DELETE-1 ===\n");
1277 for (i = 0; ttable[i].host != NULL; i++) {
1278 if (ttable[i].what[0] != 'd')
1280 delete_addr(rnh, i);
1281 for (j = 0; ttable[j].host != NULL; j++) {
1282 setaddr(&af, ttable[j].host);
1283 test_addr(rnh, i, &af, 3);
1286 ipf_rx_walktree(rnh, nodeprinter, NULL);
1291 printf("=== ADD-2 ===\n");
1295 ipf_rx_walktree(rnh, nodeprinter, NULL);
1296 printf("=== DELETE-2 ===\n");
1301 ipf_rx_walktree(rnh, ipf_rx_freenode, rnh);
1309 ipf_rdx_head_t *rnh;
1313 printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n");
1315 for (stp = myst_top; stp; stp = stp->next)
1317 printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
1322 test_addr(rnh, pref, addr, limit)
1323 ipf_rdx_head_t *rnh;
1327 static int extras[14] = { 0, -1, 1, 3, 5, 8, 9,
1328 15, 16, 19, 255, 256, 65535, 65536
1336 memset(&af, 0, sizeof(af));
1338 if (limit < 0 || limit > 14)
1341 for (i = 0; i < limit; i++) {
1342 if (ttable[i].host == NULL)
1344 setaddr(&af, ttable[i].host);
1345 printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af));
1346 rn = ipf_rx_match(rnh, &af);
1348 printf(" = %s (%s/%d)\n", GNAME(rn),
1349 rn ? addrname(&stp->dst) : "NULL",
1350 rn ? rn->maskbitcount : 0);
1353 printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr));
1354 rn = ipf_rx_match(rnh, addr);
1356 printf(" = %s (%s/%d)\n", GNAME(rn),
1357 rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0);
1363 delete_addr(rnh, item)
1364 ipf_rdx_head_t *rnh;
1373 memset(&af, 0, sizeof(af));
1374 memset(&mask, 0, sizeof(mask));
1375 setaddr(&af, ttable[item].host);
1376 mask.adf_family = af.adf_family;
1377 setmask(&mask, ttable[item].mask);
1379 printf("DELETE(%s)\n", addrname(&af));
1380 rn = ipf_rx_delete(rnh, &af, &mask);
1382 printf("FAIL LOOKUP DELETE\n");
1384 for (stp = myst_top; stp != NULL; stp = stp->next)
1385 if (stp->printed != -1)
1387 ipf_rx_walktree(rnh, nodeprinter, NULL);
1391 printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn));
1393 for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next)
1394 if (stp == (myst_t *)rn)
1397 stp->nodes[0].parent = &stp->nodes[0];
1398 stp->nodes[1].parent = &stp->nodes[1];
1407 add_addr(rnh, n, item)
1408 ipf_rdx_head_t *rnh;
1414 stp = calloc(1, sizeof(*stp));
1415 rn = (ipf_rdx_node_t *)stp;
1416 setaddr(&stp->dst, ttable[item].host);
1417 stp->mask.adf_family = stp->dst.adf_family;
1418 setmask(&stp->mask, ttable[item].mask);
1419 stp->next = myst_top;
1421 (void) sprintf(rn[0].name, "_BORN.0");
1422 (void) sprintf(rn[1].name, "_BORN.1");
1423 rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes);
1424 (void) sprintf(rn[0].name, "%d_NODE.0", item);
1425 (void) sprintf(rn[1].name, "%d_NODE.1", item);
1426 printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name);
1433 checktree(ipf_rdx_head_t *head)
1441 for (s1 = myst_top; s1 != NULL; s1 = s1->next) {
1443 if (s1->printed == -1)
1446 if (rn->right->parent != rn)
1448 if (rn->left->parent != rn)
1450 if (rn->parent->left != rn && rn->parent->right != rn)
1453 printf("FAULT %#x %s\n", fault, rn->name);
1455 ipf_rx_walktree(head, nodeprinter, NULL);
1466 randomize(int *pnitems)
1474 nitems = sizeof(ttable) / sizeof(ttable[0]);
1476 order = calloc(nitems, sizeof(*order));
1477 srandom(getpid() * time(NULL));
1478 memset(order, 0xff, nitems * sizeof(*order));
1480 for (i = 0; i < nitems - 1; i++) {
1482 choice = rand() % (nitems - 1);
1483 for (j = 0; j < nitems; j++)
1484 if (order[j] == choice)
1486 } while (j != nitems);
1496 ipf_rdx_head_t *rnh;
1502 order = randomize(&nitems);
1504 for (i = 0; i < nitems - 1; i++) {
1505 add_addr(rnh, i, order[i]);
1515 ipf_rdx_head_t *rnh;
1521 order = randomize(&nitems);
1523 for (i = 0; i < nitems - 1; i++) {
1524 delete_addr(rnh, i);
1530 #endif /* RDX_DEBUG */