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