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