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