1 /*
2 * Copyright (C) 2012 by Darren Reed.
3 *
4 * See the IPFILTER.LICENCE file for details on licencing.
5 */
6 #include <sys/types.h>
7 #include <sys/time.h>
8 #include <sys/socket.h>
9 #include <sys/param.h>
10 #include <netinet/in.h>
11 #include <net/if.h>
12 #ifdef _KERNEL
13 #include <sys/systm.h>
14 #else
15 # include <stddef.h>
16 # include <stdlib.h>
17 # include <strings.h>
18 # include <string.h>
19 #endif /* !_KERNEL */
20 #include "netinet/ip_compat.h"
21 #include "netinet/ip_fil.h"
22 #ifdef RDX_DEBUG
23 # include <arpa/inet.h>
24 # include <stdlib.h>
25 # include <stdio.h>
26 #endif
27 #include "netinet/radix_ipf.h"
28
29 #define ADF_OFF offsetof(addrfamily_t, adf_addr)
30 #define ADF_OFF_BITS (ADF_OFF << 3)
31
32 static ipf_rdx_node_t *ipf_rx_insert(ipf_rdx_head_t *,
33 ipf_rdx_node_t nodes[2], int *);
34 static void ipf_rx_attach_mask(ipf_rdx_node_t *, ipf_rdx_mask_t *);
35 static int count_mask_bits(addrfamily_t *, u_32_t **);
36 static void buildnodes(addrfamily_t *, addrfamily_t *,
37 ipf_rdx_node_t n[2]);
38 static ipf_rdx_node_t *ipf_rx_find_addr(ipf_rdx_node_t *, u_32_t *);
39 static ipf_rdx_node_t *ipf_rx_lookup(ipf_rdx_head_t *, addrfamily_t *,
40 addrfamily_t *);
41 static ipf_rdx_node_t *ipf_rx_match(ipf_rdx_head_t *, addrfamily_t *);
42
43 /*
44 * Foreword.
45 * ---------
46 * The code in this file has been written to target using the addrfamily_t
47 * data structure to house the address information and no other. Thus there
48 * are certain aspects of thise code (such as offsets to the address itself)
49 * that are hard coded here whilst they might be more variable elsewhere.
50 * Similarly, this code enforces no maximum key length as that's implied by
51 * all keys needing to be stored in addrfamily_t.
52 */
53
54 /* ------------------------------------------------------------------------ */
55 /* Function: count_mask_bits */
56 /* Returns: number of consecutive bits starting at "mask". */
57 /* */
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,int * dup)319 ipf_rx_insert(ipf_rdx_head_t *head, ipf_rdx_node_t *nodes, 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 * When removing the top node of the dupkey list,
603 * the pointers at the top of the list that point
604 * to other tree nodes need to be preserved and
605 * any children must have their parent updated.
606 */
607 node = node->dupkey;
608 node->parent = found->parent;
609 node->right = found->right;
610 node->left = found->left;
611 found->right->parent = node;
612 found->left->parent = node;
613 if (parent->left == found)
614 parent->left = node;
615 else
616 parent->right= node;
617 }
618 } else {
619 if (count != found->maskbitcount)
620 return (NULL);
621 /*
622 * Remove the node from the tree and reconnect the subtree
623 * below.
624 */
625 /*
626 * If there is a tree to the left, look for something to
627 * attach in place of "found".
628 */
629 prev = found + 1;
630 cur = parent->parent;
631 if (parent != found + 1) {
632 if ((found + 1)->parent->right == found + 1)
633 (found + 1)->parent->right = parent;
634 else
635 (found + 1)->parent->left = parent;
636 if (cur->right == parent) {
637 if (parent->left == found) {
638 cur->right = parent->right;
639 } else if (parent->left != parent - 1) {
640 cur->right = parent->left;
641 } else {
642 cur->right = parent - 1;
643 }
644 cur->right->parent = cur;
645 } else {
646 if (parent->right == found) {
647 cur->left = parent->left;
648 } else if (parent->right != parent - 1) {
649 cur->left = parent->right;
650 } else {
651 cur->left = parent - 1;
652 }
653 cur->left->parent = cur;
654 }
655 parent->left = (found + 1)->left;
656 if ((found + 1)->right != parent)
657 parent->right = (found + 1)->right;
658 parent->left->parent = parent;
659 parent->right->parent = parent;
660 parent->parent = (found + 1)->parent;
661
662 parent->bitmask = prev->bitmask;
663 parent->offset = prev->offset;
664 parent->index = prev->index;
665 } else {
666 /*
667 * We found an edge node.
668 */
669 cur = parent->parent;
670 if (cur->left == parent) {
671 if (parent->left == found) {
672 cur->left = parent->right;
673 parent->right->parent = cur;
674 } else {
675 cur->left = parent->left;
676 parent->left->parent = cur;
677 }
678 } else {
679 if (parent->right != found) {
680 cur->right = parent->right;
681 parent->right->parent = cur;
682 } else {
683 cur->right = parent->left;
684 prev->left->parent = cur;
685 }
686 }
687 }
688 }
689
690 /*
691 * Remove mask associated with this node.
692 */
693 for (cur = parent; cur->root == 0; cur = cur->parent) {
694 ipf_rdx_mask_t **pm;
695
696 if (cur->maskbitcount <= found->maskbitcount)
697 break;
698 if (((cur - 1)->addrkey[found->offset] & found->bitmask) !=
699 found->addrkey[found->offset])
700 break;
701 for (pm = &cur->masks; (m = *pm) != NULL; )
702 if (m->node == cur) {
703 *pm = m->next;
704 break;
705 } else {
706 pm = &m->next;
707 }
708 }
709 KFREE(found->mymask);
710
711 /*
712 * Masks that have been brought up to this node from below need to
713 * be sent back down.
714 */
715 for (pmask = &parent->masks; (m = *pmask) != NULL; ) {
716 *pmask = m->next;
717 cur = m->node;
718 if (cur == found)
719 continue;
720 if (found->addrkey[cur->offset] & cur->lastmask) {
721 ipf_rx_attach_mask(parent->right, m);
722 } else if (parent->left != found) {
723 ipf_rx_attach_mask(parent->left, m);
724 }
725 }
726
727 return (found);
728 }
729
730
731 /* ------------------------------------------------------------------------ */
732 /* Function: ipf_rx_walktree */
733 /* Returns: Nil */
734 /* Paramters: head(I) - pointer to tree head to search */
735 /* walker(I) - function to call for each node in the tree */
736 /* arg(I) - parameter to pass to walker, in addition to the */
737 /* node pointer */
738 /* */
739 /* A standard tree walking function except that it is iterative, rather */
740 /* than recursive and tracks the next node in case the "walker" function */
741 /* should happen to delete and free the current node. It thus goes without */
742 /* saying that the "walker" function is not permitted to cause any change */
743 /* in the validity of the data found at either the left or right child. */
744 /* ------------------------------------------------------------------------ */
745 void
ipf_rx_walktree(ipf_rdx_head_t * head,radix_walk_func_t walker,void * arg)746 ipf_rx_walktree(ipf_rdx_head_t *head, radix_walk_func_t walker, void *arg)
747 {
748 ipf_rdx_node_t *next;
749 ipf_rdx_node_t *node = head->root;
750 ipf_rdx_node_t *base;
751
752 while (node->index >= 0)
753 node = node->left;
754
755 for (;;) {
756 base = node;
757 while ((node->parent->right == node) && (node->root == 0))
758 node = node->parent;
759
760 for (node = node->parent->right; node->index >= 0; )
761 node = node->left;
762 next = node;
763
764 for (node = base; node != NULL; node = base) {
765 base = node->dupkey;
766 if (node->root == 0)
767 walker(node, arg);
768 }
769 node = next;
770 if (node->root)
771 return;
772 }
773 }
774
775
776 /* ------------------------------------------------------------------------ */
777 /* Function: ipf_rx_inithead */
778 /* Returns: int - 0 = success, else failure */
779 /* Paramters: softr(I) - pointer to radix context */
780 /* headp(O) - location for where to store allocated tree head */
781 /* */
782 /* This function allocates and initialises a radix tree head structure. */
783 /* As a traditional radix tree, node 0 is used as the "0" sentinel and node */
784 /* "2" is used as the all ones sentinel, leaving node "1" as the root from */
785 /* which the tree is hung with node "0" on its left and node "2" to the */
786 /* right. The context, "softr", is used here to provide a common source of */
787 /* the zeroes and ones data rather than have one per head. */
788 /* ------------------------------------------------------------------------ */
789 int
ipf_rx_inithead(radix_softc_t * softr,ipf_rdx_head_t ** headp)790 ipf_rx_inithead(radix_softc_t *softr, ipf_rdx_head_t **headp)
791 {
792 ipf_rdx_head_t *ptr;
793 ipf_rdx_node_t *node;
794
795 KMALLOC(ptr, ipf_rdx_head_t *);
796 *headp = ptr;
797 if (ptr == NULL)
798 return (-1);
799 bzero(ptr, sizeof(*ptr));
800 node = ptr->nodes;
801 ptr->root = node + 1;
802 node[0].index = ADF_OFF_BITS;
803 node[0].index = -1 - node[0].index;
804 node[1].index = ADF_OFF_BITS;
805 node[2].index = node[0].index;
806 node[0].parent = node + 1;
807 node[1].parent = node + 1;
808 node[2].parent = node + 1;
809 node[1].bitmask = htonl(0x80000000);
810 node[0].root = 1;
811 node[1].root = 1;
812 node[2].root = 1;
813 node[0].offset = ADF_OFF_BITS >> 5;
814 node[1].offset = ADF_OFF_BITS >> 5;
815 node[2].offset = ADF_OFF_BITS >> 5;
816 node[1].left = &node[0];
817 node[1].right = &node[2];
818 node[0].addrkey = (u_32_t *)softr->zeros;
819 node[2].addrkey = (u_32_t *)softr->ones;
820 #ifdef RDX_DEBUG
821 (void) strcpy(node[0].name, "0_ROOT");
822 (void) strcpy(node[1].name, "1_ROOT");
823 (void) strcpy(node[2].name, "2_ROOT");
824 #endif
825
826 ptr->addaddr = ipf_rx_addroute;
827 ptr->deladdr = ipf_rx_delete;
828 ptr->lookup = ipf_rx_lookup;
829 ptr->matchaddr = ipf_rx_match;
830 ptr->walktree = ipf_rx_walktree;
831 return (0);
832 }
833
834
835 /* ------------------------------------------------------------------------ */
836 /* Function: ipf_rx_freehead */
837 /* Returns: Nil */
838 /* Paramters: head(I) - pointer to tree head to free */
839 /* */
840 /* This function simply free's up the radix tree head. Prior to calling */
841 /* this function, it is expected that the tree will have been emptied. */
842 /* ------------------------------------------------------------------------ */
843 void
ipf_rx_freehead(ipf_rdx_head_t * head)844 ipf_rx_freehead(ipf_rdx_head_t *head)
845 {
846 KFREE(head);
847 }
848
849
850 /* ------------------------------------------------------------------------ */
851 /* Function: ipf_rx_create */
852 /* Parameters: Nil */
853 /* */
854 /* ------------------------------------------------------------------------ */
855 void *
ipf_rx_create(void)856 ipf_rx_create(void)
857 {
858 radix_softc_t *softr;
859
860 KMALLOC(softr, radix_softc_t *);
861 if (softr == NULL)
862 return (NULL);
863 bzero((char *)softr, sizeof(*softr));
864
865 KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t));
866 if (softr->zeros == NULL) {
867 KFREE(softr);
868 return (NULL);
869 }
870 softr->ones = softr->zeros + sizeof(addrfamily_t);
871
872 return (softr);
873 }
874
875
876 /* ------------------------------------------------------------------------ */
877 /* Function: ipf_rx_init */
878 /* Returns: int - 0 = success (always) */
879 /* */
880 /* ------------------------------------------------------------------------ */
881 int
ipf_rx_init(void * ctx)882 ipf_rx_init(void *ctx)
883 {
884 radix_softc_t *softr = ctx;
885
886 memset(softr->zeros, 0, 3 * sizeof(addrfamily_t));
887 memset(softr->ones, 0xff, sizeof(addrfamily_t));
888
889 return (0);
890 }
891
892
893 /* ------------------------------------------------------------------------ */
894 /* Function: ipf_rx_destroy */
895 /* Returns: Nil */
896 /* */
897 /* ------------------------------------------------------------------------ */
898 void
ipf_rx_destroy(void * ctx)899 ipf_rx_destroy(void *ctx)
900 {
901 radix_softc_t *softr = ctx;
902
903 if (softr->zeros != NULL)
904 KFREES(softr->zeros, 3 * sizeof(addrfamily_t));
905 KFREE(softr);
906 }
907
908 /* ====================================================================== */
909
910 #ifdef RDX_DEBUG
911 /*
912 * To compile this file as a standalone test unit, use -DRDX_DEBUG=1
913 */
914 #define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name)
915 #define GNAME(y) ((y) == NULL ? "NULL" : NAME(y))
916
917 typedef struct myst {
918 struct ipf_rdx_node nodes[2];
919 addrfamily_t dst;
920 addrfamily_t mask;
921 struct myst *next;
922 int printed;
923 } myst_t;
924
925 typedef struct tabe_s {
926 char *host;
927 char *mask;
928 char *what;
929 } tabe_t;
930
931 tabe_t builtin[] = {
932 #if 1
933 { "192:168:100::0", "48", "d" },
934 { "192:168:100::2", "128", "d" },
935 #else
936 { "127.192.0.0", "255.255.255.0", "d" },
937 { "127.128.0.0", "255.255.255.0", "d" },
938 { "127.96.0.0", "255.255.255.0", "d" },
939 { "127.80.0.0", "255.255.255.0", "d" },
940 { "127.72.0.0", "255.255.255.0", "d" },
941 { "127.64.0.0", "255.255.255.0", "d" },
942 { "127.56.0.0", "255.255.255.0", "d" },
943 { "127.48.0.0", "255.255.255.0", "d" },
944 { "127.40.0.0", "255.255.255.0", "d" },
945 { "127.32.0.0", "255.255.255.0", "d" },
946 { "127.24.0.0", "255.255.255.0", "d" },
947 { "127.16.0.0", "255.255.255.0", "d" },
948 { "127.8.0.0", "255.255.255.0", "d" },
949 { "124.0.0.0", "255.0.0.0", "d" },
950 { "125.0.0.0", "255.0.0.0", "d" },
951 { "126.0.0.0", "255.0.0.0", "d" },
952 { "127.0.0.0", "255.0.0.0", "d" },
953 { "10.0.0.0", "255.0.0.0", "d" },
954 { "128.250.0.0", "255.255.0.0", "d" },
955 { "192.168.0.0", "255.255.0.0", "d" },
956 { "192.168.1.0", "255.255.255.0", "d" },
957 #endif
958 { NULL, NULL, NULL }
959 };
960
961 char *mtable[][1] = {
962 #if 1
963 { "192:168:100::2" },
964 { "192:168:101::2" },
965 #else
966 { "9.0.0.0" },
967 { "9.0.0.1" },
968 { "11.0.0.0" },
969 { "11.0.0.1" },
970 { "127.0.0.1" },
971 { "127.0.1.0" },
972 { "255.255.255.0" },
973 { "126.0.0.1" },
974 { "128.251.0.0" },
975 { "128.251.0.1" },
976 { "128.251.255.255" },
977 { "129.250.0.0" },
978 { "129.250.0.1" },
979 { "192.168.255.255" },
980 #endif
981 { NULL }
982 };
983
984
985 int forder[22] = {
986 14, 13, 12, 5, 10, 3, 19, 7, 4, 20, 8,
987 2, 17, 9, 16, 11, 15, 1, 6, 18, 0, 21
988 };
989
990 static int nodecount = 0;
991 myst_t *myst_top = NULL;
992 tabe_t *ttable = NULL;
993
994 void add_addr(ipf_rdx_head_t *, int , int);
995 void checktree(ipf_rdx_head_t *);
996 void delete_addr(ipf_rdx_head_t *rnh, int item);
997 void dumptree(ipf_rdx_head_t *rnh);
998 void nodeprinter(ipf_rdx_node_t *, void *);
999 void printroots(ipf_rdx_head_t *);
1000 void random_add(ipf_rdx_head_t *);
1001 void random_delete(ipf_rdx_head_t *);
1002 void test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int);
1003
1004
1005 static void
ipf_rx_freenode(ipf_rdx_node_t * node,void * arg)1006 ipf_rx_freenode(ipf_rdx_node_t *node, void *arg)
1007 {
1008 ipf_rdx_head_t *head = arg;
1009 ipf_rdx_node_t *rv;
1010 myst_t *stp;
1011
1012 stp = (myst_t *)node;
1013 rv = ipf_rx_delete(head, &stp->dst, &stp->mask);
1014 if (rv != NULL) {
1015 free(rv);
1016 }
1017 }
1018
1019
1020 const char *
addrname(addrfamily_t * ap)1021 addrname(addrfamily_t *ap)
1022 {
1023 static char name[80];
1024 const char *txt;
1025
1026 bzero((char *)name, sizeof(name));
1027 txt = inet_ntop(ap->adf_family, &ap->adf_addr, name,
1028 sizeof(name));
1029 return (txt);
1030 }
1031
1032
1033 void
fill6bits(int bits,u_int * msk)1034 fill6bits(int bits, u_int *msk)
1035 {
1036 if (bits == 0) {
1037 msk[0] = 0;
1038 msk[1] = 0;
1039 msk[2] = 0;
1040 msk[3] = 0;
1041 return;
1042 }
1043
1044 msk[0] = 0xffffffff;
1045 msk[1] = 0xffffffff;
1046 msk[2] = 0xffffffff;
1047 msk[3] = 0xffffffff;
1048
1049 if (bits == 128)
1050 return;
1051 if (bits > 96) {
1052 msk[3] = htonl(msk[3] << (128 - bits));
1053 } else if (bits > 64) {
1054 msk[3] = 0;
1055 msk[2] = htonl(msk[2] << (96 - bits));
1056 } else if (bits > 32) {
1057 msk[3] = 0;
1058 msk[2] = 0;
1059 msk[1] = htonl(msk[1] << (64 - bits));
1060 } else {
1061 msk[3] = 0;
1062 msk[2] = 0;
1063 msk[1] = 0;
1064 msk[0] = htonl(msk[0] << (32 - bits));
1065 }
1066 }
1067
1068
1069 void
setaddr(addrfamily_t * afp,char * str)1070 setaddr(addrfamily_t *afp, char *str)
1071 {
1072
1073 bzero((char *)afp, sizeof(*afp));
1074
1075 if (strchr(str, ':') == NULL) {
1076 afp->adf_family = AF_INET;
1077 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1078 } else {
1079 afp->adf_family = AF_INET6;
1080 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1081 }
1082 inet_pton(afp->adf_family, str, &afp->adf_addr);
1083 }
1084
1085
1086 void
setmask(addrfamily_t * afp,char * str)1087 setmask(addrfamily_t *afp, char *str)
1088 {
1089 if (strchr(str, '.') != NULL) {
1090 afp->adf_addr.in4.s_addr = inet_addr(str);
1091 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1092 } else if (afp->adf_family == AF_INET) {
1093 afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str)));
1094 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
1095 } else if (afp->adf_family == AF_INET6) {
1096 fill6bits(atoi(str), afp->adf_addr.i6);
1097 afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
1098 }
1099 }
1100
1101
1102 void
nodeprinter(ipf_rdx_node_t * node,void * arg)1103 nodeprinter(ipf_rdx_node_t *node, void *arg)
1104 {
1105 myst_t *stp = (myst_t *)node;
1106
1107 printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n",
1108 node[0].name,
1109 GNAME(node[1].left), GNAME(node[1].right),
1110 GNAME(node[0].parent), GNAME(node[1].parent),
1111 addrname(&stp->dst), node[0].maskbitcount);
1112 if (stp->printed == -1)
1113 printf("!!! %d\n", stp->printed);
1114 else
1115 stp->printed = 1;
1116 }
1117
1118
1119 void
printnode(myst_t * stp)1120 printnode(myst_t *stp)
1121 {
1122 ipf_rdx_node_t *node = &stp->nodes[0];
1123
1124 if (stp->nodes[0].index > 0)
1125 stp = (myst_t *)&stp->nodes[-1];
1126
1127 printf("Node %-9.9s ", node[0].name);
1128 printf("L %-9.9s ", GNAME(node[1].left));
1129 printf("R %-9.9s ", GNAME(node[1].right));
1130 printf("P %9.9s", GNAME(node[0].parent));
1131 printf("/%-9.9s ", GNAME(node[1].parent));
1132 printf("%s P%d\n", addrname(&stp->dst), stp->printed);
1133 }
1134
1135
1136 void
buildtab(void)1137 buildtab(void)
1138 {
1139 char line[80], *s;
1140 tabe_t *tab;
1141 int lines;
1142 FILE *fp;
1143
1144 lines = 0;
1145 fp = fopen("hosts", "r");
1146
1147 while (fgets(line, sizeof(line), fp) != NULL) {
1148 s = strchr(line, '\n');
1149 if (s != NULL)
1150 *s = '\0';
1151 lines++;
1152 if (lines == 1)
1153 tab = malloc(sizeof(*tab) * 2);
1154 else
1155 tab = realloc(tab, (lines + 1) * sizeof(*tab));
1156 tab[lines - 1].host = strdup(line);
1157 s = strchr(tab[lines - 1].host, '/');
1158 *s++ = '\0';
1159 tab[lines - 1].mask = s;
1160 tab[lines - 1].what = "d";
1161 }
1162 fclose(fp);
1163
1164 tab[lines].host = NULL;
1165 tab[lines].mask = NULL;
1166 tab[lines].what = NULL;
1167 ttable = tab;
1168 }
1169
1170
1171 void
printroots(ipf_rdx_head_t * rnh)1172 printroots(ipf_rdx_head_t *rnh)
1173 {
1174 printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1175 GNAME(&rnh->nodes[0]),
1176 rnh->nodes[0].index, GNAME(rnh->nodes[0].parent),
1177 GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right));
1178 printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1179 GNAME(&rnh->nodes[1]),
1180 rnh->nodes[1].index, GNAME(rnh->nodes[1].parent),
1181 GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right));
1182 printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
1183 GNAME(&rnh->nodes[2]),
1184 rnh->nodes[2].index, GNAME(rnh->nodes[2].parent),
1185 GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right));
1186 }
1187
1188
1189 int
main(int argc,char * argv[])1190 main(int argc, char *argv[])
1191 {
1192 addrfamily_t af;
1193 ipf_rdx_head_t *rnh;
1194 radix_softc_t *ctx;
1195 int j;
1196 int i;
1197
1198 rnh = NULL;
1199
1200 buildtab();
1201 ctx = ipf_rx_create();
1202 ipf_rx_init(ctx);
1203 ipf_rx_inithead(ctx, &rnh);
1204
1205 printf("=== ADD-0 ===\n");
1206 for (i = 0; ttable[i].host != NULL; i++) {
1207 add_addr(rnh, i, i);
1208 checktree(rnh);
1209 }
1210 printroots(rnh);
1211 ipf_rx_walktree(rnh, nodeprinter, NULL);
1212 printf("=== DELETE-0 ===\n");
1213 for (i = 0; ttable[i].host != NULL; i++) {
1214 delete_addr(rnh, i);
1215 printroots(rnh);
1216 ipf_rx_walktree(rnh, nodeprinter, NULL);
1217 }
1218 printf("=== ADD-1 ===\n");
1219 for (i = 0; ttable[i].host != NULL; i++) {
1220 setaddr(&af, ttable[i].host);
1221 add_addr(rnh, i, i); /*forder[i]); */
1222 checktree(rnh);
1223 }
1224 dumptree(rnh);
1225 ipf_rx_walktree(rnh, nodeprinter, NULL);
1226 printf("=== TEST-1 ===\n");
1227 for (i = 0; ttable[i].host != NULL; i++) {
1228 setaddr(&af, ttable[i].host);
1229 test_addr(rnh, i, &af, -1);
1230 }
1231
1232 printf("=== TEST-2 ===\n");
1233 for (i = 0; mtable[i][0] != NULL; i++) {
1234 setaddr(&af, mtable[i][0]);
1235 test_addr(rnh, i, &af, -1);
1236 }
1237 printf("=== DELETE-1 ===\n");
1238 for (i = 0; ttable[i].host != NULL; i++) {
1239 if (ttable[i].what[0] != 'd')
1240 continue;
1241 delete_addr(rnh, i);
1242 for (j = 0; ttable[j].host != NULL; j++) {
1243 setaddr(&af, ttable[j].host);
1244 test_addr(rnh, i, &af, 3);
1245 }
1246 printroots(rnh);
1247 ipf_rx_walktree(rnh, nodeprinter, NULL);
1248 }
1249
1250 dumptree(rnh);
1251
1252 printf("=== ADD-2 ===\n");
1253 random_add(rnh);
1254 checktree(rnh);
1255 dumptree(rnh);
1256 ipf_rx_walktree(rnh, nodeprinter, NULL);
1257 printf("=== DELETE-2 ===\n");
1258 random_delete(rnh);
1259 checktree(rnh);
1260 dumptree(rnh);
1261
1262 ipf_rx_walktree(rnh, ipf_rx_freenode, rnh);
1263
1264 return (0);
1265 }
1266
1267
1268 void
dumptree(ipf_rdx_head_t * rnh)1269 dumptree(ipf_rdx_head_t *rnh)
1270 {
1271 myst_t *stp;
1272
1273 printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n");
1274 printroots(rnh);
1275 for (stp = myst_top; stp; stp = stp->next)
1276 printnode(stp);
1277 printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
1278 }
1279
1280
1281 void
test_addr(ipf_rdx_head_t * rnh,int pref,addrfamily_t * addr,int limit)1282 test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *addr, int limit)
1283 {
1284 static int extras[14] = { 0, -1, 1, 3, 5, 8, 9,
1285 15, 16, 19, 255, 256, 65535, 65536
1286 };
1287 ipf_rdx_node_t *rn;
1288 addrfamily_t af;
1289 char name[80];
1290 myst_t *stp;
1291 int i;
1292
1293 memset(&af, 0, sizeof(af));
1294 #if 0
1295 if (limit < 0 || limit > 14)
1296 limit = 14;
1297
1298 for (i = 0; i < limit; i++) {
1299 if (ttable[i].host == NULL)
1300 break;
1301 setaddr(&af, ttable[i].host);
1302 printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af));
1303 rn = ipf_rx_match(rnh, &af);
1304 stp = (myst_t *)rn;
1305 printf(" = %s (%s/%d)\n", GNAME(rn),
1306 rn ? addrname(&stp->dst) : "NULL",
1307 rn ? rn->maskbitcount : 0);
1308 }
1309 #else
1310 printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr));
1311 rn = ipf_rx_match(rnh, addr);
1312 stp = (myst_t *)rn;
1313 printf(" = %s (%s/%d)\n", GNAME(rn),
1314 rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0);
1315 #endif
1316 }
1317
1318
1319 void
delete_addr(ipf_rdx_head_t * rnh,int item)1320 delete_addr(ipf_rdx_head_t *rnh, int item)
1321 {
1322 ipf_rdx_node_t *rn;
1323 addrfamily_t mask;
1324 addrfamily_t af;
1325 myst_t **pstp;
1326 myst_t *stp;
1327
1328 memset(&af, 0, sizeof(af));
1329 memset(&mask, 0, sizeof(mask));
1330 setaddr(&af, ttable[item].host);
1331 mask.adf_family = af.adf_family;
1332 setmask(&mask, ttable[item].mask);
1333
1334 printf("DELETE(%s)\n", addrname(&af));
1335 rn = ipf_rx_delete(rnh, &af, &mask);
1336 if (rn == NULL) {
1337 printf("FAIL LOOKUP DELETE\n");
1338 checktree(rnh);
1339 for (stp = myst_top; stp != NULL; stp = stp->next)
1340 if (stp->printed != -1)
1341 stp->printed = -2;
1342 ipf_rx_walktree(rnh, nodeprinter, NULL);
1343 dumptree(rnh);
1344 abort();
1345 }
1346 printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn));
1347
1348 for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next)
1349 if (stp == (myst_t *)rn)
1350 break;
1351 stp->printed = -1;
1352 stp->nodes[0].parent = &stp->nodes[0];
1353 stp->nodes[1].parent = &stp->nodes[1];
1354 *pstp = stp->next;
1355 free(stp);
1356 nodecount--;
1357 checktree(rnh);
1358 }
1359
1360
1361 void
add_addr(ipf_rdx_head_t * rnh,int n,int item)1362 add_addr(ipf_rdx_head_t *rnh, int n, int item)
1363 {
1364 ipf_rdx_node_t *rn;
1365 myst_t *stp;
1366
1367 stp = calloc(1, sizeof(*stp));
1368 rn = (ipf_rdx_node_t *)stp;
1369 setaddr(&stp->dst, ttable[item].host);
1370 stp->mask.adf_family = stp->dst.adf_family;
1371 setmask(&stp->mask, ttable[item].mask);
1372 stp->next = myst_top;
1373 myst_top = stp;
1374 #ifdef RDX_DEBUG
1375 (void) snprintf(rn[0].name, sizeof(ipf_rdx_node.name), "_BORN.0");
1376 (void) snprintf(rn[1].name, sizeof(ipf_rdx_node.name), "_BORN.1");
1377 rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes);
1378 (void) snprintf(rn[0].name, sizeof(ipf_rdx_node.name), "%d_NODE.0", item);
1379 (void) snprintf(rn[1].name, sizeof(ipf_rdx_node.name), "%d_NODE.1", item);
1380 printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name);
1381 #endif
1382 nodecount++;
1383 checktree(rnh);
1384 }
1385
1386
1387 void
checktree(ipf_rdx_head_t * head)1388 checktree(ipf_rdx_head_t *head)
1389 {
1390 myst_t *s1;
1391 ipf_rdx_node_t *rn;
1392
1393 if (nodecount <= 1)
1394 return;
1395
1396 for (s1 = myst_top; s1 != NULL; s1 = s1->next) {
1397 int fault = 0;
1398 if (s1->printed == -1)
1399 continue;
1400 rn = &s1->nodes[1];
1401 if (rn->right->parent != rn)
1402 fault |= 1;
1403 if (rn->left->parent != rn)
1404 fault |= 2;
1405 if (rn->parent->left != rn && rn->parent->right != rn)
1406 fault |= 4;
1407 if (fault != 0) {
1408 printf("FAULT %#x %s\n", fault, rn->name);
1409 dumptree(head);
1410 ipf_rx_walktree(head, nodeprinter, NULL);
1411 fflush(stdout);
1412 fflush(stderr);
1413 printf("--\n");
1414 abort();
1415 }
1416 }
1417 }
1418
1419
1420 int *
randomize(int * pnitems)1421 randomize(int *pnitems)
1422 {
1423 int *order;
1424 int nitems;
1425 int choice;
1426 int j;
1427 int i;
1428
1429 nitems = sizeof(ttable) / sizeof(ttable[0]);
1430 *pnitems = nitems;
1431 order = calloc(nitems, sizeof(*order));
1432 srandom(getpid() * time(NULL));
1433 memset(order, 0xff, nitems * sizeof(*order));
1434 order[21] = 21;
1435 for (i = 0; i < nitems - 1; i++) {
1436 do {
1437 choice = rand() % (nitems - 1);
1438 for (j = 0; j < nitems; j++)
1439 if (order[j] == choice)
1440 break;
1441 } while (j != nitems);
1442 order[i] = choice;
1443 }
1444
1445 return (order);
1446 }
1447
1448
1449 void
random_add(ipf_rdx_head_t * rnh)1450 random_add(ipf_rdx_head_t *rnh)
1451 {
1452 int *order;
1453 int nitems;
1454 int i;
1455
1456 order = randomize(&nitems);
1457
1458 for (i = 0; i < nitems - 1; i++) {
1459 add_addr(rnh, i, order[i]);
1460 checktree(rnh);
1461 }
1462
1463 free(order);
1464 }
1465
1466
1467 void
random_delete(ipf_rdx_head_t * rnh)1468 random_delete(ipf_rdx_head_t *rnh)
1469 {
1470 int *order;
1471 int nitems;
1472 int i;
1473
1474 order = randomize(&nitems);
1475
1476 for (i = 0; i < nitems - 1; i++) {
1477 delete_addr(rnh, i);
1478 checktree(rnh);
1479 }
1480
1481 free(order);
1482 }
1483 #endif /* RDX_DEBUG */
1484