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