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