1254219Scy/* 2254219Scy * Copyright (C) 2012 by Darren Reed. 3254219Scy * 4254219Scy * See the IPFILTER.LICENCE file for details on licencing. 5254219Scy */ 6254219Scy#include <sys/types.h> 7254219Scy#include <sys/time.h> 8254219Scy#include <sys/socket.h> 9254219Scy#include <sys/param.h> 10254219Scy#include <netinet/in.h> 11254219Scy#include <net/if.h> 12254219Scy#if !defined(_KERNEL) 13254219Scy# include <stddef.h> 14254219Scy# include <stdlib.h> 15254219Scy# include <strings.h> 16254219Scy# include <string.h> 17254219Scy#endif 18254219Scy#include "netinet/ip_compat.h" 19254219Scy#include "netinet/ip_fil.h" 20254219Scy#ifdef RDX_DEBUG 21254219Scy# include <arpa/inet.h> 22254219Scy# include <stdlib.h> 23254219Scy# include <stdio.h> 24254219Scy#endif 25254219Scy#include "netinet/radix_ipf.h" 26254219Scy 27254219Scy#define ADF_OFF offsetof(addrfamily_t, adf_addr) 28254219Scy#define ADF_OFF_BITS (ADF_OFF << 3) 29254219Scy 30254219Scystatic ipf_rdx_node_t *ipf_rx_insert __P((ipf_rdx_head_t *, 31254219Scy ipf_rdx_node_t nodes[2], int *)); 32254219Scystatic void ipf_rx_attach_mask __P((ipf_rdx_node_t *, ipf_rdx_mask_t *)); 33254219Scystatic int count_mask_bits __P((addrfamily_t *, u_32_t **)); 34254219Scystatic void buildnodes __P((addrfamily_t *, addrfamily_t *, 35254219Scy ipf_rdx_node_t n[2])); 36254219Scystatic ipf_rdx_node_t *ipf_rx_find_addr __P((ipf_rdx_node_t *, u_32_t *)); 37254219Scystatic ipf_rdx_node_t *ipf_rx_lookup __P((ipf_rdx_head_t *, addrfamily_t *, 38254219Scy addrfamily_t *)); 39254219Scystatic ipf_rdx_node_t *ipf_rx_match __P((ipf_rdx_head_t *, addrfamily_t *)); 40254219Scy 41254219Scy/* 42254219Scy * Foreword. 43254219Scy * --------- 44254219Scy * The code in this file has been written to target using the addrfamily_t 45254219Scy * data structure to house the address information and no other. Thus there 46254219Scy * are certain aspects of thise code (such as offsets to the address itself) 47254219Scy * that are hard coded here whilst they might be more variable elsewhere. 48254219Scy * Similarly, this code enforces no maximum key length as that's implied by 49254219Scy * all keys needing to be stored in addrfamily_t. 50254219Scy */ 51254219Scy 52254219Scy/* ------------------------------------------------------------------------ */ 53254219Scy/* Function: count_mask_bits */ 54254219Scy/* Returns: number of consecutive bits starting at "mask". */ 55254219Scy/* */ 56254219Scy/* Count the number of bits set in the address section of addrfamily_t and */ 57254219Scy/* return both that number and a pointer to the last word with a bit set if */ 58254219Scy/* lastp is not NULL. The bit count is performed using network byte order */ 59254219Scy/* as the guide for which bit is the most significant bit. */ 60254219Scy/* ------------------------------------------------------------------------ */ 61254219Scystatic int 62254219Scycount_mask_bits(mask, lastp) 63254219Scy addrfamily_t *mask; 64254219Scy u_32_t **lastp; 65254219Scy{ 66254219Scy u_32_t *mp = (u_32_t *)&mask->adf_addr; 67254219Scy u_32_t m; 68254219Scy int count = 0; 69254219Scy int mlen; 70254219Scy 71254219Scy mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr); 72254219Scy for (; mlen > 0; mlen -= 4, mp++) { 73254219Scy if ((m = ntohl(*mp)) == 0) 74254219Scy break; 75254219Scy if (lastp != NULL) 76254219Scy *lastp = mp; 77254219Scy for (; m & 0x80000000; m <<= 1) 78254219Scy count++; 79254219Scy } 80254219Scy 81254219Scy return count; 82254219Scy} 83254219Scy 84254219Scy 85254219Scy/* ------------------------------------------------------------------------ */ 86254219Scy/* Function: buildnodes */ 87254219Scy/* Returns: Nil */ 88254219Scy/* Parameters: addr(I) - network address for this radix node */ 89254219Scy/* mask(I) - netmask associated with the above address */ 90254219Scy/* nodes(O) - pair of ipf_rdx_node_t's to initialise with data */ 91254219Scy/* associated with addr and mask. */ 92254219Scy/* */ 93254219Scy/* Initialise the fields in a pair of radix tree nodes according to the */ 94254219Scy/* data supplied in the paramters "addr" and "mask". It is expected that */ 95254219Scy/* "mask" will contain a consecutive string of bits set. Masks with gaps in */ 96254219Scy/* the middle are not handled by this implementation. */ 97254219Scy/* ------------------------------------------------------------------------ */ 98254219Scystatic void 99254219Scybuildnodes(addr, mask, nodes) 100254219Scy addrfamily_t *addr, *mask; 101254219Scy ipf_rdx_node_t nodes[2]; 102254219Scy{ 103254219Scy u_32_t maskbits; 104254219Scy u_32_t lastbits; 105254219Scy u_32_t lastmask; 106254219Scy u_32_t *last; 107254219Scy int masklen; 108254219Scy 109254219Scy last = NULL; 110254219Scy maskbits = count_mask_bits(mask, &last); 111254219Scy if (last == NULL) { 112254219Scy masklen = 0; 113254219Scy lastmask = 0; 114254219Scy } else { 115254219Scy masklen = last - (u_32_t *)mask; 116254219Scy lastmask = *last; 117254219Scy } 118254219Scy lastbits = maskbits & 0x1f; 119254219Scy 120254219Scy bzero(&nodes[0], sizeof(ipf_rdx_node_t) * 2); 121254219Scy nodes[0].maskbitcount = maskbits; 122254219Scy nodes[0].index = -1 - (ADF_OFF_BITS + maskbits); 123254219Scy nodes[0].addrkey = (u_32_t *)addr; 124254219Scy nodes[0].maskkey = (u_32_t *)mask; 125254219Scy nodes[0].addroff = nodes[0].addrkey + masklen; 126254219Scy nodes[0].maskoff = nodes[0].maskkey + masklen; 127254219Scy nodes[0].parent = &nodes[1]; 128254219Scy nodes[0].offset = masklen; 129254219Scy nodes[0].lastmask = lastmask; 130254219Scy nodes[1].offset = masklen; 131254219Scy nodes[1].left = &nodes[0]; 132254219Scy nodes[1].maskbitcount = maskbits; 133254219Scy#ifdef RDX_DEBUG 134254219Scy (void) strcpy(nodes[0].name, "_BUILD.0"); 135254219Scy (void) strcpy(nodes[1].name, "_BUILD.1"); 136254219Scy#endif 137254219Scy} 138254219Scy 139254219Scy 140254219Scy/* ------------------------------------------------------------------------ */ 141254219Scy/* Function: ipf_rx_find_addr */ 142254219Scy/* Returns: ipf_rdx_node_t * - pointer to a node in the radix tree. */ 143254219Scy/* Parameters: tree(I) - pointer to first right node in tree to search */ 144254219Scy/* addr(I) - pointer to address to match */ 145254219Scy/* */ 146254219Scy/* Walk the radix tree given by "tree", looking for a leaf node that is a */ 147254219Scy/* match for the address given by "addr". */ 148254219Scy/* ------------------------------------------------------------------------ */ 149254219Scystatic ipf_rdx_node_t * 150254219Scyipf_rx_find_addr(tree, addr) 151254219Scy ipf_rdx_node_t *tree; 152254219Scy u_32_t *addr; 153254219Scy{ 154254219Scy ipf_rdx_node_t *cur; 155254219Scy 156254219Scy for (cur = tree; cur->index >= 0;) { 157254219Scy if (cur->bitmask & addr[cur->offset]) { 158254219Scy cur = cur->right; 159254219Scy } else { 160254219Scy cur = cur->left; 161254219Scy } 162254219Scy } 163254219Scy 164254219Scy return (cur); 165254219Scy} 166254219Scy 167254219Scy 168254219Scy/* ------------------------------------------------------------------------ */ 169254219Scy/* Function: ipf_rx_match */ 170254219Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 171254219Scy/* added to the tree. */ 172254219Scy/* Paramters: head(I) - pointer to tree head to search */ 173254219Scy/* addr(I) - pointer to address to find */ 174254219Scy/* */ 175254219Scy/* Search the radix tree for the best match to the address pointed to by */ 176254219Scy/* "addr" and return a pointer to that node. This search will not match the */ 177254219Scy/* address information stored in either of the root leaves as neither of */ 178254219Scy/* them are considered to be part of the tree of data being stored. */ 179254219Scy/* ------------------------------------------------------------------------ */ 180254219Scystatic ipf_rdx_node_t * 181254219Scyipf_rx_match(head, addr) 182254219Scy ipf_rdx_head_t *head; 183254219Scy addrfamily_t *addr; 184254219Scy{ 185254219Scy ipf_rdx_mask_t *masknode; 186254219Scy ipf_rdx_node_t *prev; 187254219Scy ipf_rdx_node_t *node; 188254219Scy ipf_rdx_node_t *cur; 189254219Scy u_32_t *data; 190254219Scy u_32_t *mask; 191254219Scy u_32_t *key; 192254219Scy u_32_t *end; 193254219Scy int len; 194254219Scy int i; 195254219Scy 196254219Scy len = addr->adf_len; 197254219Scy end = (u_32_t *)((u_char *)addr + len); 198254219Scy node = ipf_rx_find_addr(head->root, (u_32_t *)addr); 199254219Scy 200254219Scy /* 201254219Scy * Search the dupkey list for a potential match. 202254219Scy */ 203254219Scy for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) { 204254219Scy i = cur[0].addroff - cur[0].addrkey; 205254219Scy data = cur[0].addrkey + i; 206254219Scy mask = cur[0].maskkey + i; 207254219Scy key = (u_32_t *)addr + i; 208254219Scy for (; key < end; data++, key++, mask++) 209254219Scy if ((*key & *mask) != *data) 210254219Scy break; 211254219Scy if ((end == key) && (cur->root == 0)) 212254219Scy return (cur); /* Equal keys */ 213254219Scy } 214254219Scy prev = node->parent; 215254219Scy key = (u_32_t *)addr; 216254219Scy 217254219Scy for (node = prev; node->root == 0; node = node->parent) { 218254219Scy /* 219254219Scy * We know that the node hasn't matched so therefore only 220254219Scy * the entries in the mask list are searched, not the top 221254219Scy * node nor the dupkey list. 222254219Scy */ 223254219Scy masknode = node->masks; 224254219Scy for (; masknode != NULL; masknode = masknode->next) { 225254219Scy if (masknode->maskbitcount > node->maskbitcount) 226254219Scy continue; 227254219Scy cur = masknode->node; 228254219Scy for (i = ADF_OFF >> 2; i <= node->offset; i++) { 229254219Scy if ((key[i] & masknode->mask[i]) == 230254219Scy cur->addrkey[i]) 231254219Scy return (cur); 232254219Scy } 233254219Scy } 234254219Scy } 235254219Scy 236254219Scy return NULL; 237254219Scy} 238254219Scy 239254219Scy 240254219Scy/* ------------------------------------------------------------------------ */ 241254219Scy/* Function: ipf_rx_lookup */ 242254219Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 243254219Scy/* added to the tree. */ 244254219Scy/* Paramters: head(I) - pointer to tree head to search */ 245254219Scy/* addr(I) - address part of the key to match */ 246254219Scy/* mask(I) - netmask part of the key to match */ 247254219Scy/* */ 248254219Scy/* ipf_rx_lookup searches for an exact match on (addr,mask). The intention */ 249254219Scy/* is to see if a given key is in the tree, not to see if a route exists. */ 250254219Scy/* ------------------------------------------------------------------------ */ 251254219Scyipf_rdx_node_t * 252254219Scyipf_rx_lookup(head, addr, mask) 253254219Scy ipf_rdx_head_t *head; 254254219Scy addrfamily_t *addr, *mask; 255254219Scy{ 256254219Scy ipf_rdx_node_t *found; 257254219Scy ipf_rdx_node_t *node; 258254219Scy u_32_t *akey; 259254219Scy int count; 260254219Scy 261254219Scy found = ipf_rx_find_addr(head->root, (u_32_t *)addr); 262254219Scy if (found->root == 1) 263254219Scy return NULL; 264254219Scy 265254219Scy /* 266254219Scy * It is possible to find a matching address in the tree but for the 267254219Scy * netmask to not match. If the netmask does not match and there is 268254219Scy * no list of alternatives present at dupkey, return a failure. 269254219Scy */ 270254219Scy count = count_mask_bits(mask, NULL); 271254219Scy if (count != found->maskbitcount && found->dupkey == NULL) 272254219Scy return (NULL); 273254219Scy 274254219Scy akey = (u_32_t *)addr; 275254219Scy if ((found->addrkey[found->offset] & found->maskkey[found->offset]) != 276254219Scy akey[found->offset]) 277254219Scy return NULL; 278254219Scy 279254219Scy if (found->dupkey != NULL) { 280254219Scy node = found; 281254219Scy while (node != NULL && node->maskbitcount != count) 282254219Scy node = node->dupkey; 283254219Scy if (node == NULL) 284254219Scy return (NULL); 285254219Scy found = node; 286254219Scy } 287254219Scy return found; 288254219Scy} 289254219Scy 290254219Scy 291254219Scy/* ------------------------------------------------------------------------ */ 292254219Scy/* Function: ipf_rx_attach_mask */ 293254219Scy/* Returns: Nil */ 294254219Scy/* Parameters: node(I) - pointer to a radix tree node */ 295254219Scy/* mask(I) - pointer to mask structure to add */ 296254219Scy/* */ 297254219Scy/* Add the netmask to the given node in an ordering where the most specific */ 298254219Scy/* netmask is at the top of the list. */ 299254219Scy/* ------------------------------------------------------------------------ */ 300254219Scystatic void 301254219Scyipf_rx_attach_mask(node, mask) 302254219Scy ipf_rdx_node_t *node; 303254219Scy ipf_rdx_mask_t *mask; 304254219Scy{ 305254219Scy ipf_rdx_mask_t **pm; 306254219Scy ipf_rdx_mask_t *m; 307254219Scy 308254219Scy for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next) 309254219Scy if (m->maskbitcount < mask->maskbitcount) 310254219Scy break; 311254219Scy mask->next = *pm; 312254219Scy *pm = mask; 313254219Scy} 314254219Scy 315254219Scy 316254219Scy/* ------------------------------------------------------------------------ */ 317254219Scy/* Function: ipf_rx_insert */ 318254219Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 319254219Scy/* added to the tree. */ 320254219Scy/* Paramters: head(I) - pointer to tree head to add nodes to */ 321254219Scy/* nodes(I) - pointer to radix nodes to be added */ 322254219Scy/* dup(O) - set to 1 if node is a duplicate, else 0. */ 323254219Scy/* */ 324254219Scy/* Add the new radix tree entry that owns nodes[] to the tree given by head.*/ 325254219Scy/* If there is already a matching key in the table, "dup" will be set to 1 */ 326254219Scy/* and the existing node pointer returned if there is a complete key match. */ 327254219Scy/* A complete key match is a matching of all key data that is presented by */ 328254219Scy/* by the netmask. */ 329254219Scy/* ------------------------------------------------------------------------ */ 330254219Scystatic ipf_rdx_node_t * 331254219Scyipf_rx_insert(head, nodes, dup) 332254219Scy ipf_rdx_head_t *head; 333254219Scy ipf_rdx_node_t nodes[2]; 334254219Scy int *dup; 335254219Scy{ 336254219Scy ipf_rdx_mask_t **pmask; 337254219Scy ipf_rdx_node_t *node; 338254219Scy ipf_rdx_node_t *prev; 339254219Scy ipf_rdx_mask_t *mask; 340254219Scy ipf_rdx_node_t *cur; 341254219Scy u_32_t nodemask; 342254219Scy u_32_t *addr; 343254219Scy u_32_t *data; 344254219Scy int nodebits; 345254219Scy u_32_t *key; 346254219Scy u_32_t *end; 347254219Scy u_32_t bits; 348254219Scy int nodekey; 349254219Scy int nodeoff; 350254219Scy int nlen; 351254219Scy int len; 352254219Scy 353254219Scy addr = nodes[0].addrkey; 354254219Scy 355254219Scy node = ipf_rx_find_addr(head->root, addr); 356254219Scy len = ((addrfamily_t *)addr)->adf_len; 357254219Scy key = (u_32_t *)&((addrfamily_t *)addr)->adf_addr; 358254219Scy data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr; 359254219Scy end = (u_32_t *)((u_char *)addr + len); 360254219Scy for (nlen = 0; key < end; data++, key++, nlen += 32) 361254219Scy if (*key != *data) 362254219Scy break; 363254219Scy if (end == data) { 364254219Scy *dup = 1; 365254219Scy return (node); /* Equal keys */ 366254219Scy } 367254219Scy *dup = 0; 368254219Scy 369254219Scy bits = (ntohl(*data) ^ ntohl(*key)); 370254219Scy for (; bits != 0; nlen++) { 371254219Scy if ((bits & 0x80000000) != 0) 372254219Scy break; 373254219Scy bits <<= 1; 374254219Scy } 375254219Scy nlen += ADF_OFF_BITS; 376254219Scy nodes[1].index = nlen; 377254219Scy nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f)); 378254219Scy nodes[0].offset = nlen / 32; 379254219Scy nodes[1].offset = nlen / 32; 380254219Scy 381254219Scy /* 382254219Scy * Walk through the tree and look for the correct place to attach 383254219Scy * this node. ipf_rx_fin_addr is not used here because the place 384254219Scy * to attach this node may be an internal node (same key, different 385254219Scy * netmask.) Additionally, the depth of the search is forcibly limited 386254219Scy * here to not exceed the netmask, so that a short netmask will be 387254219Scy * added higher up the tree even if there are lower branches. 388254219Scy */ 389254219Scy cur = head->root; 390254219Scy key = nodes[0].addrkey; 391254219Scy do { 392254219Scy prev = cur; 393254219Scy if (key[cur->offset] & cur->bitmask) { 394254219Scy cur = cur->right; 395254219Scy } else { 396254219Scy cur = cur->left; 397254219Scy } 398254219Scy } while (nlen > (unsigned)cur->index); 399254219Scy 400254219Scy if ((key[prev->offset] & prev->bitmask) == 0) { 401254219Scy prev->left = &nodes[1]; 402254219Scy } else { 403254219Scy prev->right = &nodes[1]; 404254219Scy } 405254219Scy cur->parent = &nodes[1]; 406254219Scy nodes[1].parent = prev; 407254219Scy if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) { 408254219Scy nodes[1].right = cur; 409254219Scy } else { 410254219Scy nodes[1].right = &nodes[0]; 411254219Scy nodes[1].left = cur; 412254219Scy } 413254219Scy 414254219Scy nodeoff = nodes[0].offset; 415254219Scy nodekey = nodes[0].addrkey[nodeoff]; 416254219Scy nodemask = nodes[0].lastmask; 417254219Scy nodebits = nodes[0].maskbitcount; 418254219Scy prev = NULL; 419254219Scy /* 420254219Scy * Find the node up the tree with the largest pattern that still 421254219Scy * matches the node being inserted to see if this mask can be 422254219Scy * moved there. 423254219Scy */ 424254219Scy for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) { 425254219Scy if (cur->maskbitcount <= nodebits) 426254219Scy break; 427254219Scy if (((cur - 1)->addrkey[nodeoff] & nodemask) != nodekey) 428254219Scy break; 429254219Scy prev = cur; 430254219Scy } 431254219Scy 432254219Scy KMALLOC(mask, ipf_rdx_mask_t *); 433254219Scy if (mask == NULL) 434254219Scy return NULL; 435254219Scy bzero(mask, sizeof(*mask)); 436254219Scy mask->next = NULL; 437254219Scy mask->node = &nodes[0]; 438254219Scy mask->maskbitcount = nodebits; 439254219Scy mask->mask = nodes[0].maskkey; 440254219Scy nodes[0].mymask = mask; 441254219Scy 442254219Scy if (prev != NULL) { 443254219Scy ipf_rdx_mask_t *m; 444254219Scy 445254219Scy for (pmask = &prev->masks; (m = *pmask) != NULL; 446254219Scy pmask = &m->next) { 447254219Scy if (m->maskbitcount < nodebits) 448254219Scy break; 449254219Scy } 450254219Scy } else { 451254219Scy /* 452254219Scy * No higher up nodes qualify, so attach mask locally. 453254219Scy */ 454254219Scy pmask = &nodes[0].masks; 455254219Scy } 456254219Scy mask->next = *pmask; 457254219Scy *pmask = mask; 458254219Scy 459254219Scy /* 460254219Scy * Search the mask list on each child to see if there are any masks 461254219Scy * there that can be moved up to this newly inserted node. 462254219Scy */ 463254219Scy cur = nodes[1].right; 464254219Scy if (cur->root == 0) { 465254219Scy for (pmask = &cur->masks; (mask = *pmask) != NULL; ) { 466254219Scy if (mask->maskbitcount < nodebits) { 467254219Scy *pmask = mask->next; 468254219Scy ipf_rx_attach_mask(&nodes[0], mask); 469254219Scy } else { 470254219Scy pmask = &mask->next; 471254219Scy } 472254219Scy } 473254219Scy } 474254219Scy cur = nodes[1].left; 475254219Scy if (cur->root == 0 && cur != &nodes[0]) { 476254219Scy for (pmask = &cur->masks; (mask = *pmask) != NULL; ) { 477254219Scy if (mask->maskbitcount < nodebits) { 478254219Scy *pmask = mask->next; 479254219Scy ipf_rx_attach_mask(&nodes[0], mask); 480254219Scy } else { 481254219Scy pmask = &mask->next; 482254219Scy } 483254219Scy } 484254219Scy } 485254219Scy return (&nodes[0]); 486254219Scy} 487254219Scy 488254219Scy/* ------------------------------------------------------------------------ */ 489254219Scy/* Function: ipf_rx_addroute */ 490254219Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 491254219Scy/* added to the tree. */ 492254219Scy/* Paramters: head(I) - pointer to tree head to search */ 493254219Scy/* addr(I) - address portion of "route" to add */ 494254219Scy/* mask(I) - netmask portion of "route" to add */ 495254219Scy/* nodes(I) - radix tree data nodes inside allocate structure */ 496254219Scy/* */ 497254219Scy/* Attempt to add a node to the radix tree. The key for the node is the */ 498254219Scy/* (addr,mask). No memory allocation for the radix nodes themselves is */ 499254219Scy/* performed here, the data structure that this radix node is being used to */ 500254219Scy/* find is expected to house the node data itself however the call to */ 501254219Scy/* ipf_rx_insert() will attempt to allocate memory in order for netmask to */ 502254219Scy/* be promoted further up the tree. */ 503254219Scy/* In this case, the ip_pool_node_t structure from ip_pool.h contains both */ 504254219Scy/* the key material (addr,mask) and the radix tree nodes[]. */ 505254219Scy/* */ 506254219Scy/* The mechanics of inserting the node into the tree is handled by the */ 507254219Scy/* function ipf_rx_insert() above. Here, the code deals with the case */ 508254219Scy/* where the data to be inserted is a duplicate. */ 509254219Scy/* ------------------------------------------------------------------------ */ 510254219Scyipf_rdx_node_t * 511254219Scyipf_rx_addroute(head, addr, mask, nodes) 512254219Scy ipf_rdx_head_t *head; 513254219Scy addrfamily_t *addr, *mask; 514254219Scy ipf_rdx_node_t *nodes; 515254219Scy{ 516254219Scy ipf_rdx_node_t *node; 517254219Scy ipf_rdx_node_t *prev; 518254219Scy ipf_rdx_node_t *x; 519254219Scy int dup; 520254219Scy 521254219Scy buildnodes(addr, mask, nodes); 522254219Scy x = ipf_rx_insert(head, nodes, &dup); 523254219Scy if (x == NULL) 524254219Scy return NULL; 525254219Scy 526254219Scy if (dup == 1) { 527254219Scy node = &nodes[0]; 528254219Scy prev = NULL; 529254219Scy /* 530254219Scy * The duplicate list is kept sorted with the longest 531254219Scy * mask at the top, meaning that the most specific entry 532254219Scy * in the listis found first. This list thus allows for 533254219Scy * duplicates such as 128.128.0.0/32 and 128.128.0.0/16. 534254219Scy */ 535254219Scy while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) { 536254219Scy prev = x; 537254219Scy x = x->dupkey; 538254219Scy } 539254219Scy 540254219Scy /* 541254219Scy * Is it a complete duplicate? If so, return NULL and 542254219Scy * fail the insert. Otherwise, insert it into the list 543254219Scy * of netmasks active for this key. 544254219Scy */ 545254219Scy if ((x != NULL) && (x->maskbitcount == node->maskbitcount)) 546254219Scy return (NULL); 547254219Scy 548254219Scy if (prev != NULL) { 549254219Scy nodes[0].dupkey = x; 550254219Scy prev->dupkey = &nodes[0]; 551254219Scy nodes[0].parent = prev; 552254219Scy if (x != NULL) 553254219Scy x->parent = &nodes[0]; 554254219Scy } else { 555254219Scy nodes[0].dupkey = x->dupkey; 556254219Scy prev = x->parent; 557254219Scy nodes[0].parent = prev; 558254219Scy x->parent = &nodes[0]; 559254219Scy if (prev->left == x) 560254219Scy prev->left = &nodes[0]; 561254219Scy else 562254219Scy prev->right = &nodes[0]; 563254219Scy } 564254219Scy } 565254219Scy 566254219Scy return &nodes[0]; 567254219Scy} 568254219Scy 569254219Scy 570254219Scy/* ------------------------------------------------------------------------ */ 571254219Scy/* Function: ipf_rx_delete */ 572254219Scy/* Returns: ipf_rdx_node_t * - NULL on error, else node removed from */ 573254219Scy/* the tree. */ 574254219Scy/* Paramters: head(I) - pointer to tree head to search */ 575254219Scy/* addr(I) - pointer to the address part of the key */ 576254219Scy/* mask(I) - pointer to the netmask part of the key */ 577254219Scy/* */ 578254219Scy/* Search for an entry in the radix tree that is an exact match for (addr, */ 579254219Scy/* mask) and remove it if it exists. In the case where (addr,mask) is a not */ 580254219Scy/* a unique key, the tree structure itself is not changed - only the list */ 581254219Scy/* of duplicate keys. */ 582254219Scy/* ------------------------------------------------------------------------ */ 583254219Scyipf_rdx_node_t * 584254219Scyipf_rx_delete(head, addr, mask) 585254219Scy ipf_rdx_head_t *head; 586254219Scy addrfamily_t *addr, *mask; 587254219Scy{ 588254219Scy ipf_rdx_mask_t **pmask; 589254219Scy ipf_rdx_node_t *parent; 590254219Scy ipf_rdx_node_t *found; 591254219Scy ipf_rdx_node_t *prev; 592254219Scy ipf_rdx_node_t *node; 593254219Scy ipf_rdx_node_t *cur; 594254219Scy ipf_rdx_mask_t *m; 595254219Scy int count; 596254219Scy 597254219Scy found = ipf_rx_find_addr(head->root, (u_32_t *)addr); 598254219Scy if (found == NULL) 599254219Scy return NULL; 600254219Scy if (found->root == 1) 601254219Scy return NULL; 602254219Scy count = count_mask_bits(mask, NULL); 603254219Scy parent = found->parent; 604254219Scy if (found->dupkey != NULL) { 605254219Scy node = found; 606254219Scy while (node != NULL && node->maskbitcount != count) 607254219Scy node = node->dupkey; 608254219Scy if (node == NULL) 609254219Scy return (NULL); 610254219Scy if (node != found) { 611254219Scy /* 612254219Scy * Remove from the dupkey list. Here, "parent" is 613254219Scy * the previous node on the list (rather than tree) 614254219Scy * and "dupkey" is the next node on the list. 615254219Scy */ 616254219Scy parent = node->parent; 617254219Scy parent->dupkey = node->dupkey; 618254219Scy node->dupkey->parent = parent; 619254219Scy } else { 620254219Scy /* 621254219Scy * 622254219Scy * When removing the top node of the dupkey list, 623254219Scy * the pointers at the top of the list that point 624254219Scy * to other tree nodes need to be preserved and 625254219Scy * any children must have their parent updated. 626254219Scy */ 627254219Scy node = node->dupkey; 628254219Scy node->parent = found->parent; 629254219Scy node->right = found->right; 630254219Scy node->left = found->left; 631254219Scy found->right->parent = node; 632254219Scy found->left->parent = node; 633254219Scy if (parent->left == found) 634254219Scy parent->left = node; 635254219Scy else 636254219Scy parent->right= node; 637254219Scy } 638254219Scy } else { 639254219Scy if (count != found->maskbitcount) 640254219Scy return (NULL); 641254219Scy /* 642254219Scy * Remove the node from the tree and reconnect the subtree 643254219Scy * below. 644254219Scy */ 645254219Scy /* 646254219Scy * If there is a tree to the left, look for something to 647254219Scy * attach in place of "found". 648254219Scy */ 649254219Scy prev = found + 1; 650254219Scy cur = parent->parent; 651254219Scy if (parent != found + 1) { 652254219Scy if ((found + 1)->parent->right == found + 1) 653254219Scy (found + 1)->parent->right = parent; 654254219Scy else 655254219Scy (found + 1)->parent->left = parent; 656254219Scy if (cur->right == parent) { 657254219Scy if (parent->left == found) { 658254219Scy cur->right = parent->right; 659254219Scy } else if (parent->left != parent - 1) { 660254219Scy cur->right = parent->left; 661254219Scy } else { 662254219Scy cur->right = parent - 1; 663254219Scy } 664254219Scy cur->right->parent = cur; 665254219Scy } else { 666254219Scy if (parent->right == found) { 667254219Scy cur->left = parent->left; 668254219Scy } else if (parent->right != parent - 1) { 669254219Scy cur->left = parent->right; 670254219Scy } else { 671254219Scy cur->left = parent - 1; 672254219Scy } 673254219Scy cur->left->parent = cur; 674254219Scy } 675254219Scy parent->left = (found + 1)->left; 676254219Scy if ((found + 1)->right != parent) 677254219Scy parent->right = (found + 1)->right; 678254219Scy parent->left->parent = parent; 679254219Scy parent->right->parent = parent; 680254219Scy parent->parent = (found + 1)->parent; 681254219Scy 682254219Scy parent->bitmask = prev->bitmask; 683254219Scy parent->offset = prev->offset; 684254219Scy parent->index = prev->index; 685254219Scy } else { 686254219Scy /* 687254219Scy * We found an edge node. 688254219Scy */ 689254219Scy cur = parent->parent; 690254219Scy if (cur->left == parent) { 691254219Scy if (parent->left == found) { 692254219Scy cur->left = parent->right; 693254219Scy parent->right->parent = cur; 694254219Scy } else { 695254219Scy cur->left = parent->left; 696254219Scy parent->left->parent = cur; 697254219Scy } 698254219Scy } else { 699254219Scy if (parent->right != found) { 700254219Scy cur->right = parent->right; 701254219Scy parent->right->parent = cur; 702254219Scy } else { 703254219Scy cur->right = parent->left; 704254219Scy prev->left->parent = cur; 705254219Scy } 706254219Scy } 707254219Scy } 708254219Scy } 709254219Scy 710254219Scy /* 711254219Scy * Remove mask associated with this node. 712254219Scy */ 713254219Scy for (cur = parent; cur->root == 0; cur = cur->parent) { 714254219Scy ipf_rdx_mask_t **pm; 715254219Scy 716254219Scy if (cur->maskbitcount <= found->maskbitcount) 717254219Scy break; 718254219Scy if (((cur - 1)->addrkey[found->offset] & found->bitmask) != 719254219Scy found->addrkey[found->offset]) 720254219Scy break; 721254219Scy for (pm = &cur->masks; (m = *pm) != NULL; ) 722254219Scy if (m->node == cur) { 723254219Scy *pm = m->next; 724254219Scy break; 725254219Scy } else { 726254219Scy pm = &m->next; 727254219Scy } 728254219Scy } 729254219Scy KFREE(found->mymask); 730254219Scy 731254219Scy /* 732254219Scy * Masks that have been brought up to this node from below need to 733254219Scy * be sent back down. 734254219Scy */ 735254219Scy for (pmask = &parent->masks; (m = *pmask) != NULL; ) { 736254219Scy *pmask = m->next; 737254219Scy cur = m->node; 738254219Scy if (cur == found) 739254219Scy continue; 740254219Scy if (found->addrkey[cur->offset] & cur->lastmask) { 741254219Scy ipf_rx_attach_mask(parent->right, m); 742254219Scy } else if (parent->left != found) { 743254219Scy ipf_rx_attach_mask(parent->left, m); 744254219Scy } 745254219Scy } 746254219Scy 747254219Scy return (found); 748254219Scy} 749254219Scy 750254219Scy 751254219Scy/* ------------------------------------------------------------------------ */ 752254219Scy/* Function: ipf_rx_walktree */ 753254219Scy/* Returns: Nil */ 754254219Scy/* Paramters: head(I) - pointer to tree head to search */ 755254219Scy/* walker(I) - function to call for each node in the tree */ 756254219Scy/* arg(I) - parameter to pass to walker, in addition to the */ 757254219Scy/* node pointer */ 758254219Scy/* */ 759254219Scy/* A standard tree walking function except that it is iterative, rather */ 760254219Scy/* than recursive and tracks the next node in case the "walker" function */ 761254219Scy/* should happen to delete and free the current node. It thus goes without */ 762254219Scy/* saying that the "walker" function is not permitted to cause any change */ 763254219Scy/* in the validity of the data found at either the left or right child. */ 764254219Scy/* ------------------------------------------------------------------------ */ 765254219Scyvoid 766254219Scyipf_rx_walktree(head, walker, arg) 767254219Scy ipf_rdx_head_t *head; 768254219Scy radix_walk_func_t walker; 769254219Scy void *arg; 770254219Scy{ 771254219Scy ipf_rdx_node_t *next; 772254219Scy ipf_rdx_node_t *node = head->root; 773254219Scy ipf_rdx_node_t *base; 774254219Scy 775254219Scy while (node->index >= 0) 776254219Scy node = node->left; 777254219Scy 778254219Scy for (;;) { 779254219Scy base = node; 780254219Scy while ((node->parent->right == node) && (node->root == 0)) 781254219Scy node = node->parent; 782254219Scy 783254219Scy for (node = node->parent->right; node->index >= 0; ) 784254219Scy node = node->left; 785254219Scy next = node; 786254219Scy 787254219Scy for (node = base; node != NULL; node = base) { 788254219Scy base = node->dupkey; 789254219Scy if (node->root == 0) 790254219Scy walker(node, arg); 791254219Scy } 792254219Scy node = next; 793254219Scy if (node->root) 794254219Scy return; 795254219Scy } 796254219Scy} 797254219Scy 798254219Scy 799254219Scy/* ------------------------------------------------------------------------ */ 800254219Scy/* Function: ipf_rx_inithead */ 801254219Scy/* Returns: int - 0 = success, else failure */ 802254219Scy/* Paramters: softr(I) - pointer to radix context */ 803254219Scy/* headp(O) - location for where to store allocated tree head */ 804254219Scy/* */ 805254219Scy/* This function allocates and initialises a radix tree head structure. */ 806254219Scy/* As a traditional radix tree, node 0 is used as the "0" sentinel and node */ 807254219Scy/* "2" is used as the all ones sentinel, leaving node "1" as the root from */ 808254219Scy/* which the tree is hung with node "0" on its left and node "2" to the */ 809254219Scy/* right. The context, "softr", is used here to provide a common source of */ 810254219Scy/* the zeroes and ones data rather than have one per head. */ 811254219Scy/* ------------------------------------------------------------------------ */ 812254219Scyint 813254219Scyipf_rx_inithead(softr, headp) 814254219Scy radix_softc_t *softr; 815254219Scy ipf_rdx_head_t **headp; 816254219Scy{ 817254219Scy ipf_rdx_head_t *ptr; 818254219Scy ipf_rdx_node_t *node; 819254219Scy 820254219Scy KMALLOC(ptr, ipf_rdx_head_t *); 821254219Scy *headp = ptr; 822254219Scy if (ptr == NULL) 823254219Scy return -1; 824254219Scy bzero(ptr, sizeof(*ptr)); 825254219Scy node = ptr->nodes; 826254219Scy ptr->root = node + 1; 827254219Scy node[0].index = ADF_OFF_BITS; 828254219Scy node[0].index = -1 - node[0].index; 829254219Scy node[1].index = ADF_OFF_BITS; 830254219Scy node[2].index = node[0].index; 831254219Scy node[0].parent = node + 1; 832254219Scy node[1].parent = node + 1; 833254219Scy node[2].parent = node + 1; 834254219Scy node[1].bitmask = htonl(0x80000000); 835254219Scy node[0].root = 1; 836254219Scy node[1].root = 1; 837254219Scy node[2].root = 1; 838254219Scy node[0].offset = ADF_OFF_BITS >> 5; 839254219Scy node[1].offset = ADF_OFF_BITS >> 5; 840254219Scy node[2].offset = ADF_OFF_BITS >> 5; 841254219Scy node[1].left = &node[0]; 842254219Scy node[1].right = &node[2]; 843254219Scy node[0].addrkey = (u_32_t *)softr->zeros; 844254219Scy node[2].addrkey = (u_32_t *)softr->ones; 845254219Scy#ifdef RDX_DEBUG 846254219Scy (void) strcpy(node[0].name, "0_ROOT"); 847254219Scy (void) strcpy(node[1].name, "1_ROOT"); 848254219Scy (void) strcpy(node[2].name, "2_ROOT"); 849254219Scy#endif 850254219Scy 851254219Scy ptr->addaddr = ipf_rx_addroute; 852254219Scy ptr->deladdr = ipf_rx_delete; 853254219Scy ptr->lookup = ipf_rx_lookup; 854254219Scy ptr->matchaddr = ipf_rx_match; 855254219Scy ptr->walktree = ipf_rx_walktree; 856254219Scy return 0; 857254219Scy} 858254219Scy 859254219Scy 860254219Scy/* ------------------------------------------------------------------------ */ 861254219Scy/* Function: ipf_rx_freehead */ 862254219Scy/* Returns: Nil */ 863254219Scy/* Paramters: head(I) - pointer to tree head to free */ 864254219Scy/* */ 865254219Scy/* This function simply free's up the radix tree head. Prior to calling */ 866254219Scy/* this function, it is expected that the tree will have been emptied. */ 867254219Scy/* ------------------------------------------------------------------------ */ 868254219Scyvoid 869254219Scyipf_rx_freehead(head) 870254219Scy ipf_rdx_head_t *head; 871254219Scy{ 872254219Scy KFREE(head); 873254219Scy} 874254219Scy 875254219Scy 876254219Scy/* ------------------------------------------------------------------------ */ 877254219Scy/* Function: ipf_rx_create */ 878254219Scy/* Parameters: Nil */ 879254219Scy/* */ 880254219Scy/* ------------------------------------------------------------------------ */ 881254219Scyvoid * 882254219Scyipf_rx_create() 883254219Scy{ 884254219Scy radix_softc_t *softr; 885254219Scy 886254219Scy KMALLOC(softr, radix_softc_t *); 887254219Scy if (softr == NULL) 888254219Scy return NULL; 889254219Scy bzero((char *)softr, sizeof(*softr)); 890254219Scy 891254219Scy KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t)); 892254219Scy if (softr->zeros == NULL) { 893254219Scy KFREE(softr); 894254219Scy return (NULL); 895254219Scy } 896254219Scy softr->ones = softr->zeros + sizeof(addrfamily_t); 897254219Scy 898254219Scy return softr; 899254219Scy} 900254219Scy 901254219Scy 902254219Scy/* ------------------------------------------------------------------------ */ 903254219Scy/* Function: ipf_rx_init */ 904254219Scy/* Returns: int - 0 = success (always) */ 905254219Scy/* */ 906254219Scy/* ------------------------------------------------------------------------ */ 907254219Scyint 908254219Scyipf_rx_init(ctx) 909254219Scy void *ctx; 910254219Scy{ 911254219Scy radix_softc_t *softr = ctx; 912254219Scy 913254219Scy memset(softr->zeros, 0, 3 * sizeof(addrfamily_t)); 914254219Scy memset(softr->ones, 0xff, sizeof(addrfamily_t)); 915254219Scy 916254219Scy return (0); 917254219Scy} 918254219Scy 919254219Scy 920254219Scy/* ------------------------------------------------------------------------ */ 921254219Scy/* Function: ipf_rx_destroy */ 922254219Scy/* Returns: Nil */ 923254219Scy/* */ 924254219Scy/* ------------------------------------------------------------------------ */ 925254219Scyvoid 926254219Scyipf_rx_destroy(ctx) 927254219Scy void *ctx; 928254219Scy{ 929254219Scy radix_softc_t *softr = ctx; 930254219Scy 931254219Scy if (softr->zeros != NULL) 932254219Scy KFREES(softr->zeros, 3 * sizeof(addrfamily_t)); 933254219Scy KFREE(softr); 934254219Scy} 935254219Scy 936254219Scy/* ====================================================================== */ 937254219Scy 938254219Scy#ifdef RDX_DEBUG 939254219Scy/* 940254219Scy * To compile this file as a standalone test unit, use -DRDX_DEBUG=1 941254219Scy */ 942254219Scy#define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name) 943254219Scy#define GNAME(y) ((y) == NULL ? "NULL" : NAME(y)) 944254219Scy 945254219Scytypedef struct myst { 946254219Scy struct ipf_rdx_node nodes[2]; 947254219Scy addrfamily_t dst; 948254219Scy addrfamily_t mask; 949254219Scy struct myst *next; 950254219Scy int printed; 951254219Scy} myst_t; 952254219Scy 953254219Scytypedef struct tabe_s { 954254219Scy char *host; 955254219Scy char *mask; 956254219Scy char *what; 957254219Scy} tabe_t; 958254219Scy 959254219Scytabe_t builtin[] = { 960254219Scy#if 1 961254219Scy { "192:168:100::0", "48", "d" }, 962254219Scy { "192:168:100::2", "128", "d" }, 963254219Scy#else 964254219Scy { "127.192.0.0", "255.255.255.0", "d" }, 965254219Scy { "127.128.0.0", "255.255.255.0", "d" }, 966254219Scy { "127.96.0.0", "255.255.255.0", "d" }, 967254219Scy { "127.80.0.0", "255.255.255.0", "d" }, 968254219Scy { "127.72.0.0", "255.255.255.0", "d" }, 969254219Scy { "127.64.0.0", "255.255.255.0", "d" }, 970254219Scy { "127.56.0.0", "255.255.255.0", "d" }, 971254219Scy { "127.48.0.0", "255.255.255.0", "d" }, 972254219Scy { "127.40.0.0", "255.255.255.0", "d" }, 973254219Scy { "127.32.0.0", "255.255.255.0", "d" }, 974254219Scy { "127.24.0.0", "255.255.255.0", "d" }, 975254219Scy { "127.16.0.0", "255.255.255.0", "d" }, 976254219Scy { "127.8.0.0", "255.255.255.0", "d" }, 977254219Scy { "124.0.0.0", "255.0.0.0", "d" }, 978254219Scy { "125.0.0.0", "255.0.0.0", "d" }, 979254219Scy { "126.0.0.0", "255.0.0.0", "d" }, 980254219Scy { "127.0.0.0", "255.0.0.0", "d" }, 981254219Scy { "10.0.0.0", "255.0.0.0", "d" }, 982254219Scy { "128.250.0.0", "255.255.0.0", "d" }, 983254219Scy { "192.168.0.0", "255.255.0.0", "d" }, 984254219Scy { "192.168.1.0", "255.255.255.0", "d" }, 985254219Scy#endif 986254219Scy { NULL, NULL, NULL } 987254219Scy}; 988254219Scy 989254219Scychar *mtable[][1] = { 990254219Scy#if 1 991254219Scy { "192:168:100::2" }, 992254219Scy { "192:168:101::2" }, 993254219Scy#else 994254219Scy { "9.0.0.0" }, 995254219Scy { "9.0.0.1" }, 996254219Scy { "11.0.0.0" }, 997254219Scy { "11.0.0.1" }, 998254219Scy { "127.0.0.1" }, 999254219Scy { "127.0.1.0" }, 1000254219Scy { "255.255.255.0" }, 1001254219Scy { "126.0.0.1" }, 1002254219Scy { "128.251.0.0" }, 1003254219Scy { "128.251.0.1" }, 1004254219Scy { "128.251.255.255" }, 1005254219Scy { "129.250.0.0" }, 1006254219Scy { "129.250.0.1" }, 1007254219Scy { "192.168.255.255" }, 1008254219Scy#endif 1009254219Scy { NULL } 1010254219Scy}; 1011254219Scy 1012254219Scy 1013254219Scyint forder[22] = { 1014254219Scy 14, 13, 12, 5, 10, 3, 19, 7, 4, 20, 8, 1015254219Scy 2, 17, 9, 16, 11, 15, 1, 6, 18, 0, 21 1016254219Scy}; 1017254219Scy 1018254219Scystatic int nodecount = 0; 1019254219Scymyst_t *myst_top = NULL; 1020254219Scytabe_t *ttable = NULL; 1021254219Scy 1022254219Scyvoid add_addr(ipf_rdx_head_t *, int , int); 1023254219Scyvoid checktree(ipf_rdx_head_t *); 1024254219Scyvoid delete_addr(ipf_rdx_head_t *rnh, int item); 1025254219Scyvoid dumptree(ipf_rdx_head_t *rnh); 1026254219Scyvoid nodeprinter(ipf_rdx_node_t *, void *); 1027254219Scyvoid printroots(ipf_rdx_head_t *); 1028254219Scyvoid random_add(ipf_rdx_head_t *); 1029254219Scyvoid random_delete(ipf_rdx_head_t *); 1030254219Scyvoid test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int); 1031254219Scy 1032254219Scy 1033254219Scystatic void 1034254219Scyipf_rx_freenode(node, arg) 1035254219Scy ipf_rdx_node_t *node; 1036254219Scy void *arg; 1037254219Scy{ 1038254219Scy ipf_rdx_head_t *head = arg; 1039254219Scy ipf_rdx_node_t *rv; 1040254219Scy myst_t *stp; 1041254219Scy 1042254219Scy stp = (myst_t *)node; 1043254219Scy rv = ipf_rx_delete(head, &stp->dst, &stp->mask); 1044254219Scy if (rv != NULL) { 1045254219Scy free(rv); 1046254219Scy } 1047254219Scy} 1048254219Scy 1049254219Scy 1050254219Scyconst char * 1051254219Scyaddrname(ap) 1052254219Scy addrfamily_t *ap; 1053254219Scy{ 1054254219Scy static char name[80]; 1055254219Scy const char *txt; 1056254219Scy 1057254219Scy bzero((char *)name, sizeof(name)); 1058254219Scy txt = inet_ntop(ap->adf_family, &ap->adf_addr, name, 1059254219Scy sizeof(name)); 1060254219Scy return txt; 1061254219Scy} 1062254219Scy 1063254219Scy 1064254219Scyvoid 1065254219Scyfill6bits(bits, msk) 1066254219Scy int bits; 1067254219Scy u_int *msk; 1068254219Scy{ 1069254219Scy if (bits == 0) { 1070254219Scy msk[0] = 0; 1071254219Scy msk[1] = 0; 1072254219Scy msk[2] = 0; 1073254219Scy msk[3] = 0; 1074254219Scy return; 1075254219Scy } 1076254219Scy 1077254219Scy msk[0] = 0xffffffff; 1078254219Scy msk[1] = 0xffffffff; 1079254219Scy msk[2] = 0xffffffff; 1080254219Scy msk[3] = 0xffffffff; 1081254219Scy 1082254219Scy if (bits == 128) 1083254219Scy return; 1084254219Scy if (bits > 96) { 1085254219Scy msk[3] = htonl(msk[3] << (128 - bits)); 1086254219Scy } else if (bits > 64) { 1087254219Scy msk[3] = 0; 1088254219Scy msk[2] = htonl(msk[2] << (96 - bits)); 1089254219Scy } else if (bits > 32) { 1090254219Scy msk[3] = 0; 1091254219Scy msk[2] = 0; 1092254219Scy msk[1] = htonl(msk[1] << (64 - bits)); 1093254219Scy } else { 1094254219Scy msk[3] = 0; 1095254219Scy msk[2] = 0; 1096254219Scy msk[1] = 0; 1097254219Scy msk[0] = htonl(msk[0] << (32 - bits)); 1098254219Scy } 1099254219Scy} 1100254219Scy 1101254219Scy 1102254219Scyvoid 1103254219Scysetaddr(afp, str) 1104254219Scy addrfamily_t *afp; 1105254219Scy char *str; 1106254219Scy{ 1107254219Scy 1108254219Scy bzero((char *)afp, sizeof(*afp)); 1109254219Scy 1110254219Scy if (strchr(str, ':') == NULL) { 1111254219Scy afp->adf_family = AF_INET; 1112254219Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1113254219Scy } else { 1114254219Scy afp->adf_family = AF_INET6; 1115254219Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16; 1116254219Scy } 1117254219Scy inet_pton(afp->adf_family, str, &afp->adf_addr); 1118254219Scy} 1119254219Scy 1120254219Scy 1121254219Scyvoid 1122254219Scysetmask(afp, str) 1123254219Scy addrfamily_t *afp; 1124254219Scy char *str; 1125254219Scy{ 1126254219Scy if (strchr(str, '.') != NULL) { 1127254219Scy afp->adf_addr.in4.s_addr = inet_addr(str); 1128254219Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1129254219Scy } else if (afp->adf_family == AF_INET) { 1130254219Scy afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str))); 1131254219Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1132254219Scy } else if (afp->adf_family == AF_INET6) { 1133254219Scy fill6bits(atoi(str), afp->adf_addr.i6); 1134254219Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16; 1135254219Scy } 1136254219Scy} 1137254219Scy 1138254219Scy 1139254219Scyvoid 1140254219Scynodeprinter(node, arg) 1141254219Scy ipf_rdx_node_t *node; 1142254219Scy void *arg; 1143254219Scy{ 1144254219Scy myst_t *stp = (myst_t *)node; 1145254219Scy 1146254219Scy printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n", 1147254219Scy node[0].name, 1148254219Scy GNAME(node[1].left), GNAME(node[1].right), 1149254219Scy GNAME(node[0].parent), GNAME(node[1].parent), 1150254219Scy addrname(&stp->dst), node[0].maskbitcount); 1151254219Scy if (stp->printed == -1) 1152254219Scy printf("!!! %d\n", stp->printed); 1153254219Scy else 1154254219Scy stp->printed = 1; 1155254219Scy} 1156254219Scy 1157254219Scy 1158254219Scyvoid 1159254219Scyprintnode(stp) 1160254219Scy myst_t *stp; 1161254219Scy{ 1162254219Scy ipf_rdx_node_t *node = &stp->nodes[0]; 1163254219Scy 1164254219Scy if (stp->nodes[0].index > 0) 1165254219Scy stp = (myst_t *)&stp->nodes[-1]; 1166254219Scy 1167254219Scy printf("Node %-9.9s ", node[0].name); 1168254219Scy printf("L %-9.9s ", GNAME(node[1].left)); 1169254219Scy printf("R %-9.9s ", GNAME(node[1].right)); 1170254219Scy printf("P %9.9s", GNAME(node[0].parent)); 1171254219Scy printf("/%-9.9s ", GNAME(node[1].parent)); 1172254219Scy printf("%s P%d\n", addrname(&stp->dst), stp->printed); 1173254219Scy} 1174254219Scy 1175254219Scy 1176254219Scyvoid 1177254219Scybuildtab(void) 1178254219Scy{ 1179254219Scy char line[80], *s; 1180254219Scy tabe_t *tab; 1181254219Scy int lines; 1182254219Scy FILE *fp; 1183254219Scy 1184254219Scy lines = 0; 1185254219Scy fp = fopen("hosts", "r"); 1186254219Scy 1187254219Scy while (fgets(line, sizeof(line), fp) != NULL) { 1188254219Scy s = strchr(line, '\n'); 1189254219Scy if (s != NULL) 1190254219Scy *s = '\0'; 1191254219Scy lines++; 1192254219Scy if (lines == 1) 1193254219Scy tab = malloc(sizeof(*tab) * 2); 1194254219Scy else 1195254219Scy tab = realloc(tab, (lines + 1) * sizeof(*tab)); 1196254219Scy tab[lines - 1].host = strdup(line); 1197254219Scy s = strchr(tab[lines - 1].host, '/'); 1198254219Scy *s++ = '\0'; 1199254219Scy tab[lines - 1].mask = s; 1200254219Scy tab[lines - 1].what = "d"; 1201254219Scy } 1202254219Scy fclose(fp); 1203254219Scy 1204254219Scy tab[lines].host = NULL; 1205254219Scy tab[lines].mask = NULL; 1206254219Scy tab[lines].what = NULL; 1207254219Scy ttable = tab; 1208254219Scy} 1209254219Scy 1210254219Scy 1211254219Scyvoid 1212254219Scyprintroots(rnh) 1213254219Scy ipf_rdx_head_t *rnh; 1214254219Scy{ 1215254219Scy printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1216254219Scy GNAME(&rnh->nodes[0]), 1217254219Scy rnh->nodes[0].index, GNAME(rnh->nodes[0].parent), 1218254219Scy GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right)); 1219254219Scy printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1220254219Scy GNAME(&rnh->nodes[1]), 1221254219Scy rnh->nodes[1].index, GNAME(rnh->nodes[1].parent), 1222254219Scy GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right)); 1223254219Scy printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1224254219Scy GNAME(&rnh->nodes[2]), 1225254219Scy rnh->nodes[2].index, GNAME(rnh->nodes[2].parent), 1226254219Scy GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right)); 1227254219Scy} 1228254219Scy 1229254219Scy 1230254219Scyint 1231254219Scymain(int argc, char *argv[]) 1232254219Scy{ 1233254219Scy addrfamily_t af; 1234254219Scy ipf_rdx_head_t *rnh; 1235254219Scy radix_softc_t *ctx; 1236254219Scy int j; 1237254219Scy int i; 1238254219Scy 1239254219Scy rnh = NULL; 1240254219Scy 1241254219Scy buildtab(); 1242254219Scy ctx = ipf_rx_create(); 1243254219Scy ipf_rx_init(ctx); 1244254219Scy ipf_rx_inithead(ctx, &rnh); 1245254219Scy 1246254219Scy printf("=== ADD-0 ===\n"); 1247254219Scy for (i = 0; ttable[i].host != NULL; i++) { 1248254219Scy add_addr(rnh, i, i); 1249254219Scy checktree(rnh); 1250254219Scy } 1251254219Scy printroots(rnh); 1252254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1253254219Scy printf("=== DELETE-0 ===\n"); 1254254219Scy for (i = 0; ttable[i].host != NULL; i++) { 1255254219Scy delete_addr(rnh, i); 1256254219Scy printroots(rnh); 1257254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1258254219Scy } 1259254219Scy printf("=== ADD-1 ===\n"); 1260254219Scy for (i = 0; ttable[i].host != NULL; i++) { 1261254219Scy setaddr(&af, ttable[i].host); 1262254219Scy add_addr(rnh, i, i); /*forder[i]); */ 1263254219Scy checktree(rnh); 1264254219Scy } 1265254219Scy dumptree(rnh); 1266254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1267254219Scy printf("=== TEST-1 ===\n"); 1268254219Scy for (i = 0; ttable[i].host != NULL; i++) { 1269254219Scy setaddr(&af, ttable[i].host); 1270254219Scy test_addr(rnh, i, &af, -1); 1271254219Scy } 1272254219Scy 1273254219Scy printf("=== TEST-2 ===\n"); 1274254219Scy for (i = 0; mtable[i][0] != NULL; i++) { 1275254219Scy setaddr(&af, mtable[i][0]); 1276254219Scy test_addr(rnh, i, &af, -1); 1277254219Scy } 1278254219Scy printf("=== DELETE-1 ===\n"); 1279254219Scy for (i = 0; ttable[i].host != NULL; i++) { 1280254219Scy if (ttable[i].what[0] != 'd') 1281254219Scy continue; 1282254219Scy delete_addr(rnh, i); 1283254219Scy for (j = 0; ttable[j].host != NULL; j++) { 1284254219Scy setaddr(&af, ttable[j].host); 1285254219Scy test_addr(rnh, i, &af, 3); 1286254219Scy } 1287254219Scy printroots(rnh); 1288254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1289254219Scy } 1290254219Scy 1291254219Scy dumptree(rnh); 1292254219Scy 1293254219Scy printf("=== ADD-2 ===\n"); 1294254219Scy random_add(rnh); 1295254219Scy checktree(rnh); 1296254219Scy dumptree(rnh); 1297254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1298254219Scy printf("=== DELETE-2 ===\n"); 1299254219Scy random_delete(rnh); 1300254219Scy checktree(rnh); 1301254219Scy dumptree(rnh); 1302254219Scy 1303254219Scy ipf_rx_walktree(rnh, ipf_rx_freenode, rnh); 1304254219Scy 1305254219Scy return 0; 1306254219Scy} 1307254219Scy 1308254219Scy 1309254219Scyvoid 1310254219Scydumptree(rnh) 1311254219Scy ipf_rdx_head_t *rnh; 1312254219Scy{ 1313254219Scy myst_t *stp; 1314254219Scy 1315254219Scy printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n"); 1316254219Scy printroots(rnh); 1317254219Scy for (stp = myst_top; stp; stp = stp->next) 1318254219Scy printnode(stp); 1319254219Scy printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); 1320254219Scy} 1321254219Scy 1322254219Scy 1323254219Scyvoid 1324254219Scytest_addr(rnh, pref, addr, limit) 1325254219Scy ipf_rdx_head_t *rnh; 1326254219Scy int pref; 1327254219Scy addrfamily_t *addr; 1328254219Scy{ 1329254219Scy static int extras[14] = { 0, -1, 1, 3, 5, 8, 9, 1330254219Scy 15, 16, 19, 255, 256, 65535, 65536 1331254219Scy }; 1332254219Scy ipf_rdx_node_t *rn; 1333254219Scy addrfamily_t af; 1334254219Scy char name[80]; 1335254219Scy myst_t *stp; 1336254219Scy int i; 1337254219Scy 1338254219Scy memset(&af, 0, sizeof(af)); 1339254219Scy#if 0 1340254219Scy if (limit < 0 || limit > 14) 1341254219Scy limit = 14; 1342254219Scy 1343254219Scy for (i = 0; i < limit; i++) { 1344254219Scy if (ttable[i].host == NULL) 1345254219Scy break; 1346254219Scy setaddr(&af, ttable[i].host); 1347254219Scy printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af)); 1348254219Scy rn = ipf_rx_match(rnh, &af); 1349254219Scy stp = (myst_t *)rn; 1350254219Scy printf(" = %s (%s/%d)\n", GNAME(rn), 1351254219Scy rn ? addrname(&stp->dst) : "NULL", 1352254219Scy rn ? rn->maskbitcount : 0); 1353254219Scy } 1354254219Scy#else 1355254219Scy printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr)); 1356254219Scy rn = ipf_rx_match(rnh, addr); 1357254219Scy stp = (myst_t *)rn; 1358254219Scy printf(" = %s (%s/%d)\n", GNAME(rn), 1359254219Scy rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0); 1360254219Scy#endif 1361254219Scy} 1362254219Scy 1363254219Scy 1364254219Scyvoid 1365254219Scydelete_addr(rnh, item) 1366254219Scy ipf_rdx_head_t *rnh; 1367254219Scy int item; 1368254219Scy{ 1369254219Scy ipf_rdx_node_t *rn; 1370254219Scy addrfamily_t mask; 1371254219Scy addrfamily_t af; 1372254219Scy myst_t **pstp; 1373254219Scy myst_t *stp; 1374254219Scy 1375254219Scy memset(&af, 0, sizeof(af)); 1376254219Scy memset(&mask, 0, sizeof(mask)); 1377254219Scy setaddr(&af, ttable[item].host); 1378254219Scy mask.adf_family = af.adf_family; 1379254219Scy setmask(&mask, ttable[item].mask); 1380254219Scy 1381254219Scy printf("DELETE(%s)\n", addrname(&af)); 1382254219Scy rn = ipf_rx_delete(rnh, &af, &mask); 1383254219Scy if (rn == NULL) { 1384254219Scy printf("FAIL LOOKUP DELETE\n"); 1385254219Scy checktree(rnh); 1386254219Scy for (stp = myst_top; stp != NULL; stp = stp->next) 1387254219Scy if (stp->printed != -1) 1388254219Scy stp->printed = -2; 1389254219Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1390254219Scy dumptree(rnh); 1391254219Scy abort(); 1392254219Scy } 1393254219Scy printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn)); 1394254219Scy 1395254219Scy for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next) 1396254219Scy if (stp == (myst_t *)rn) 1397254219Scy break; 1398254219Scy stp->printed = -1; 1399254219Scy stp->nodes[0].parent = &stp->nodes[0]; 1400254219Scy stp->nodes[1].parent = &stp->nodes[1]; 1401254219Scy *pstp = stp->next; 1402254219Scy free(stp); 1403254219Scy nodecount--; 1404254219Scy checktree(rnh); 1405254219Scy} 1406254219Scy 1407254219Scy 1408254219Scyvoid 1409254219Scyadd_addr(rnh, n, item) 1410254219Scy ipf_rdx_head_t *rnh; 1411254219Scy int n, item; 1412254219Scy{ 1413254219Scy ipf_rdx_node_t *rn; 1414254219Scy myst_t *stp; 1415254219Scy 1416254219Scy stp = calloc(1, sizeof(*stp)); 1417254219Scy rn = (ipf_rdx_node_t *)stp; 1418254219Scy setaddr(&stp->dst, ttable[item].host); 1419254219Scy stp->mask.adf_family = stp->dst.adf_family; 1420254219Scy setmask(&stp->mask, ttable[item].mask); 1421254219Scy stp->next = myst_top; 1422254219Scy myst_top = stp; 1423254219Scy (void) sprintf(rn[0].name, "_BORN.0"); 1424254219Scy (void) sprintf(rn[1].name, "_BORN.1"); 1425254219Scy rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes); 1426254219Scy (void) sprintf(rn[0].name, "%d_NODE.0", item); 1427254219Scy (void) sprintf(rn[1].name, "%d_NODE.1", item); 1428254219Scy printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name); 1429254219Scy nodecount++; 1430254219Scy checktree(rnh); 1431254219Scy} 1432254219Scy 1433254219Scy 1434254219Scyvoid 1435254219Scychecktree(ipf_rdx_head_t *head) 1436254219Scy{ 1437254219Scy myst_t *s1; 1438254219Scy ipf_rdx_node_t *rn; 1439254219Scy 1440254219Scy if (nodecount <= 1) 1441254219Scy return; 1442254219Scy 1443254219Scy for (s1 = myst_top; s1 != NULL; s1 = s1->next) { 1444254219Scy int fault = 0; 1445254219Scy if (s1->printed == -1) 1446254219Scy continue; 1447254219Scy rn = &s1->nodes[1]; 1448254219Scy if (rn->right->parent != rn) 1449254219Scy fault |= 1; 1450254219Scy if (rn->left->parent != rn) 1451254219Scy fault |= 2; 1452254219Scy if (rn->parent->left != rn && rn->parent->right != rn) 1453254219Scy fault |= 4; 1454254219Scy if (fault != 0) { 1455254219Scy printf("FAULT %#x %s\n", fault, rn->name); 1456254219Scy dumptree(head); 1457254219Scy ipf_rx_walktree(head, nodeprinter, NULL); 1458254219Scy fflush(stdout); 1459254219Scy fflush(stderr); 1460254219Scy printf("--\n"); 1461254219Scy abort(); 1462254219Scy } 1463254219Scy } 1464254219Scy} 1465254219Scy 1466254219Scy 1467254219Scyint * 1468254219Scyrandomize(int *pnitems) 1469254219Scy{ 1470254219Scy int *order; 1471254219Scy int nitems; 1472254219Scy int choice; 1473254219Scy int j; 1474254219Scy int i; 1475254219Scy 1476254219Scy nitems = sizeof(ttable) / sizeof(ttable[0]); 1477254219Scy *pnitems = nitems; 1478254219Scy order = calloc(nitems, sizeof(*order)); 1479254219Scy srandom(getpid() * time(NULL)); 1480254219Scy memset(order, 0xff, nitems * sizeof(*order)); 1481254219Scy order[21] = 21; 1482254219Scy for (i = 0; i < nitems - 1; i++) { 1483254219Scy do { 1484254219Scy choice = rand() % (nitems - 1); 1485254219Scy for (j = 0; j < nitems; j++) 1486254219Scy if (order[j] == choice) 1487254219Scy break; 1488254219Scy } while (j != nitems); 1489254219Scy order[i] = choice; 1490254219Scy } 1491254219Scy 1492254219Scy return order; 1493254219Scy} 1494254219Scy 1495254219Scy 1496254219Scyvoid 1497254219Scyrandom_add(rnh) 1498254219Scy ipf_rdx_head_t *rnh; 1499254219Scy{ 1500254219Scy int *order; 1501254219Scy int nitems; 1502254219Scy int i; 1503254219Scy 1504254219Scy order = randomize(&nitems); 1505254219Scy 1506254219Scy for (i = 0; i < nitems - 1; i++) { 1507254219Scy add_addr(rnh, i, order[i]); 1508254219Scy checktree(rnh); 1509254219Scy } 1510254219Scy} 1511254219Scy 1512254219Scy 1513254219Scyvoid 1514254219Scyrandom_delete(rnh) 1515254219Scy ipf_rdx_head_t *rnh; 1516254219Scy{ 1517254219Scy int *order; 1518254219Scy int nitems; 1519254219Scy int i; 1520254219Scy 1521254219Scy order = randomize(&nitems); 1522254219Scy 1523254219Scy for (i = 0; i < nitems - 1; i++) { 1524254219Scy delete_addr(rnh, i); 1525254219Scy checktree(rnh); 1526254219Scy } 1527254219Scy} 1528254219Scy#endif /* RDX_DEBUG */ 1529