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