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