1 /*
2 * Copyright (C) 2012 by Darren Reed.
3 *
4 * See the IPFILTER.LICENCE file for details on licencing.
5 */
6 #include <sys/types.h>
7 #include <sys/time.h>
8 #include <sys/socket.h>
9 #include <sys/param.h>
10 #include <netinet/in.h>
11 #include <net/if.h>
12 #ifdef _KERNEL
13 #include <sys/systm.h>
14 #else
15 # include <stddef.h>
16 # include <stdlib.h>
17 # include <strings.h>
18 # include <string.h>
19 #endif /* !_KERNEL */
20 #include "netinet/ip_compat.h"
21 #include "netinet/ip_fil.h"
22 #ifdef RDX_DEBUG
23 # include <arpa/inet.h>
24 # include <stdlib.h>
25 # include <stdio.h>
26 #endif
27 #include "netinet/radix_ipf.h"
28
29 #define ADF_OFF offsetof(addrfamily_t, adf_addr)
30 #define ADF_OFF_BITS (ADF_OFF << 3)
31
32 static ipf_rdx_node_t *ipf_rx_insert __P((ipf_rdx_head_t *,
33 ipf_rdx_node_t nodes[2], int *));
34 static void ipf_rx_attach_mask __P((ipf_rdx_node_t *, ipf_rdx_mask_t *));
35 static int count_mask_bits __P((addrfamily_t *, u_32_t **));
36 static void buildnodes __P((addrfamily_t *, addrfamily_t *,
37 ipf_rdx_node_t n[2]));
38 static ipf_rdx_node_t *ipf_rx_find_addr __P((ipf_rdx_node_t *, u_32_t *));
39 static ipf_rdx_node_t *ipf_rx_lookup __P((ipf_rdx_head_t *, addrfamily_t *,
40 addrfamily_t *));
41 static ipf_rdx_node_t *ipf_rx_match __P((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 /* */
58 /* Count the number of bits set in the address section of addrfamily_t and */
59 /* return both that number and a pointer to the last word with a bit set if */
60 /* lastp is not NULL. The bit count is performed using network byte order */
61 /* as the guide for which bit is the most significant bit. */
62 /* ------------------------------------------------------------------------ */
63 static int
count_mask_bits(mask,lastp)64 count_mask_bits(mask, lastp)
65 addrfamily_t *mask;
66 u_32_t **lastp;
67 {
68 u_32_t *mp = (u_32_t *)&mask->adf_addr;
69 u_32_t m;
70 int count = 0;
71 int mlen;
72
73 mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr);
74 for (; mlen > 0; mlen -= 4, mp++) {
75 if ((m = ntohl(*mp)) == 0)
76 break;
77 if (lastp != NULL)
78 *lastp = mp;
79 for (; m & 0x80000000; m <<= 1)
80 count++;
81 }
82
83 return count;
84 }
85
86
87 /* ------------------------------------------------------------------------ */
88 /* Function: buildnodes */
89 /* Returns: Nil */
90 /* Parameters: addr(I) - network address for this radix node */
91 /* mask(I) - netmask associated with the above address */
92 /* nodes(O) - pair of ipf_rdx_node_t's to initialise with data */
93 /* associated with addr and mask. */
94 /* */
95 /* Initialise the fields in a pair of radix tree nodes according to the */
96 /* data supplied in the paramters "addr" and "mask". It is expected that */
97 /* "mask" will contain a consecutive string of bits set. Masks with gaps in */
98 /* the middle are not handled by this implementation. */
99 /* ------------------------------------------------------------------------ */
100 static void
buildnodes(addr,mask,nodes)101 buildnodes(addr, mask, nodes)
102 addrfamily_t *addr, *mask;
103 ipf_rdx_node_t nodes[2];
104 {
105 u_32_t maskbits;
106 u_32_t lastmask;
107 u_32_t *last;
108 int masklen;
109
110 last = NULL;
111 maskbits = count_mask_bits(mask, &last);
112 if (last == NULL) {
113 masklen = 0;
114 lastmask = 0;
115 } else {
116 masklen = last - (u_32_t *)mask;
117 lastmask = *last;
118 }
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 *
ipf_rx_find_addr(tree,addr)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 *
ipf_rx_match(head,addr)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 *
ipf_rx_lookup(head,addr,mask)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
ipf_rx_attach_mask(node,mask)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 *
ipf_rx_insert(head,nodes,dup)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 *
ipf_rx_addroute(head,addr,mask,nodes)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 *
ipf_rx_delete(head,addr,mask)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
ipf_rx_walktree(head,walker,arg)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
ipf_rx_inithead(softr,headp)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
ipf_rx_freehead(head)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 *
ipf_rx_create()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
ipf_rx_init(ctx)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
ipf_rx_destroy(ctx)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
ipf_rx_freenode(node,arg)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 *
addrname(ap)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
fill6bits(bits,msk)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
setaddr(afp,str)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
setmask(afp,str)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
nodeprinter(node,arg)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
printnode(stp)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
buildtab(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
printroots(rnh)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
main(int argc,char * argv[])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
dumptree(rnh)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
test_addr(rnh,pref,addr,limit)1324 test_addr(rnh, pref, addr, limit)
1325 ipf_rdx_head_t *rnh;
1326 int pref, limit;
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
delete_addr(rnh,item)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
add_addr(rnh,n,item)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
checktree(ipf_rdx_head_t * head)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 *
randomize(int * pnitems)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
random_add(rnh)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 free(order);
1512 }
1513
1514
1515 void
random_delete(rnh)1516 random_delete(rnh)
1517 ipf_rdx_head_t *rnh;
1518 {
1519 int *order;
1520 int nitems;
1521 int i;
1522
1523 order = randomize(&nitems);
1524
1525 for (i = 0; i < nitems - 1; i++) {
1526 delete_addr(rnh, i);
1527 checktree(rnh);
1528 }
1529
1530 free(order);
1531 }
1532 #endif /* RDX_DEBUG */
1533