1254562Scy/* 2254562Scy * Copyright (C) 2012 by Darren Reed. 3254562Scy * 4254562Scy * See the IPFILTER.LICENCE file for details on licencing. 5254562Scy */ 6254562Scy#include <sys/types.h> 7254562Scy#include <sys/time.h> 8254562Scy#include <sys/socket.h> 9254562Scy#include <sys/param.h> 10254562Scy#include <netinet/in.h> 11254562Scy#include <net/if.h> 12254562Scy#if !defined(_KERNEL) 13254562Scy# include <stddef.h> 14254562Scy# include <stdlib.h> 15254562Scy# include <strings.h> 16254562Scy# include <string.h> 17254562Scy#endif 18254562Scy#include "netinet/ip_compat.h" 19254562Scy#include "netinet/ip_fil.h" 20254562Scy#ifdef RDX_DEBUG 21254562Scy# include <arpa/inet.h> 22254562Scy# include <stdlib.h> 23254562Scy# include <stdio.h> 24254562Scy#endif 25254562Scy#include "netinet/radix_ipf.h" 26254562Scy 27254562Scy#define ADF_OFF offsetof(addrfamily_t, adf_addr) 28254562Scy#define ADF_OFF_BITS (ADF_OFF << 3) 29254562Scy 30254562Scystatic ipf_rdx_node_t *ipf_rx_insert __P((ipf_rdx_head_t *, 31254562Scy ipf_rdx_node_t nodes[2], int *)); 32254562Scystatic void ipf_rx_attach_mask __P((ipf_rdx_node_t *, ipf_rdx_mask_t *)); 33254562Scystatic int count_mask_bits __P((addrfamily_t *, u_32_t **)); 34254562Scystatic void buildnodes __P((addrfamily_t *, addrfamily_t *, 35254562Scy ipf_rdx_node_t n[2])); 36254562Scystatic ipf_rdx_node_t *ipf_rx_find_addr __P((ipf_rdx_node_t *, u_32_t *)); 37254562Scystatic ipf_rdx_node_t *ipf_rx_lookup __P((ipf_rdx_head_t *, addrfamily_t *, 38254562Scy addrfamily_t *)); 39317243Scystatic ipf_rdx_node_t *ipf_rx_match __P((ipf_rdx_head_t *, addrfamily_t *)); 40254562Scy 41254562Scy/* 42254562Scy * Foreword. 43254562Scy * --------- 44254562Scy * The code in this file has been written to target using the addrfamily_t 45254562Scy * data structure to house the address information and no other. Thus there 46254562Scy * are certain aspects of thise code (such as offsets to the address itself) 47254562Scy * that are hard coded here whilst they might be more variable elsewhere. 48254562Scy * Similarly, this code enforces no maximum key length as that's implied by 49254562Scy * all keys needing to be stored in addrfamily_t. 50254562Scy */ 51254562Scy 52254562Scy/* ------------------------------------------------------------------------ */ 53254562Scy/* Function: count_mask_bits */ 54254562Scy/* Returns: number of consecutive bits starting at "mask". */ 55254562Scy/* */ 56254562Scy/* Count the number of bits set in the address section of addrfamily_t and */ 57254562Scy/* return both that number and a pointer to the last word with a bit set if */ 58254562Scy/* lastp is not NULL. The bit count is performed using network byte order */ 59254562Scy/* as the guide for which bit is the most significant bit. */ 60254562Scy/* ------------------------------------------------------------------------ */ 61254562Scystatic int 62254562Scycount_mask_bits(mask, lastp) 63254562Scy addrfamily_t *mask; 64254562Scy u_32_t **lastp; 65254562Scy{ 66254562Scy u_32_t *mp = (u_32_t *)&mask->adf_addr; 67254562Scy u_32_t m; 68254562Scy int count = 0; 69254562Scy int mlen; 70254562Scy 71254562Scy mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr); 72254562Scy for (; mlen > 0; mlen -= 4, mp++) { 73254562Scy if ((m = ntohl(*mp)) == 0) 74254562Scy break; 75254562Scy if (lastp != NULL) 76254562Scy *lastp = mp; 77254562Scy for (; m & 0x80000000; m <<= 1) 78254562Scy count++; 79254562Scy } 80254562Scy 81254562Scy return count; 82254562Scy} 83254562Scy 84254562Scy 85254562Scy/* ------------------------------------------------------------------------ */ 86254562Scy/* Function: buildnodes */ 87254562Scy/* Returns: Nil */ 88254562Scy/* Parameters: addr(I) - network address for this radix node */ 89254562Scy/* mask(I) - netmask associated with the above address */ 90254562Scy/* nodes(O) - pair of ipf_rdx_node_t's to initialise with data */ 91254562Scy/* associated with addr and mask. */ 92254562Scy/* */ 93254562Scy/* Initialise the fields in a pair of radix tree nodes according to the */ 94254562Scy/* data supplied in the paramters "addr" and "mask". It is expected that */ 95254562Scy/* "mask" will contain a consecutive string of bits set. Masks with gaps in */ 96254562Scy/* the middle are not handled by this implementation. */ 97254562Scy/* ------------------------------------------------------------------------ */ 98254562Scystatic void 99254562Scybuildnodes(addr, mask, nodes) 100254562Scy addrfamily_t *addr, *mask; 101254562Scy ipf_rdx_node_t nodes[2]; 102254562Scy{ 103254562Scy u_32_t maskbits; 104254562Scy u_32_t lastmask; 105254562Scy u_32_t *last; 106254562Scy int masklen; 107254562Scy 108254562Scy last = NULL; 109254562Scy maskbits = count_mask_bits(mask, &last); 110254562Scy if (last == NULL) { 111254562Scy masklen = 0; 112254562Scy lastmask = 0; 113254562Scy } else { 114254562Scy masklen = last - (u_32_t *)mask; 115254562Scy lastmask = *last; 116254562Scy } 117254562Scy 118254562Scy bzero(&nodes[0], sizeof(ipf_rdx_node_t) * 2); 119254562Scy nodes[0].maskbitcount = maskbits; 120254562Scy nodes[0].index = -1 - (ADF_OFF_BITS + maskbits); 121254562Scy nodes[0].addrkey = (u_32_t *)addr; 122254562Scy nodes[0].maskkey = (u_32_t *)mask; 123254562Scy nodes[0].addroff = nodes[0].addrkey + masklen; 124254562Scy nodes[0].maskoff = nodes[0].maskkey + masklen; 125254562Scy nodes[0].parent = &nodes[1]; 126254562Scy nodes[0].offset = masklen; 127254562Scy nodes[0].lastmask = lastmask; 128254562Scy nodes[1].offset = masklen; 129254562Scy nodes[1].left = &nodes[0]; 130254562Scy nodes[1].maskbitcount = maskbits; 131254562Scy#ifdef RDX_DEBUG 132254562Scy (void) strcpy(nodes[0].name, "_BUILD.0"); 133254562Scy (void) strcpy(nodes[1].name, "_BUILD.1"); 134254562Scy#endif 135254562Scy} 136254562Scy 137254562Scy 138254562Scy/* ------------------------------------------------------------------------ */ 139254562Scy/* Function: ipf_rx_find_addr */ 140254562Scy/* Returns: ipf_rdx_node_t * - pointer to a node in the radix tree. */ 141254562Scy/* Parameters: tree(I) - pointer to first right node in tree to search */ 142254562Scy/* addr(I) - pointer to address to match */ 143254562Scy/* */ 144254562Scy/* Walk the radix tree given by "tree", looking for a leaf node that is a */ 145254562Scy/* match for the address given by "addr". */ 146254562Scy/* ------------------------------------------------------------------------ */ 147254562Scystatic ipf_rdx_node_t * 148254562Scyipf_rx_find_addr(tree, addr) 149254562Scy ipf_rdx_node_t *tree; 150254562Scy u_32_t *addr; 151254562Scy{ 152254562Scy ipf_rdx_node_t *cur; 153254562Scy 154254562Scy for (cur = tree; cur->index >= 0;) { 155254562Scy if (cur->bitmask & addr[cur->offset]) { 156254562Scy cur = cur->right; 157254562Scy } else { 158254562Scy cur = cur->left; 159254562Scy } 160254562Scy } 161254562Scy 162254562Scy return (cur); 163254562Scy} 164254562Scy 165254562Scy 166254562Scy/* ------------------------------------------------------------------------ */ 167254562Scy/* Function: ipf_rx_match */ 168254562Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 169254562Scy/* added to the tree. */ 170254562Scy/* Paramters: head(I) - pointer to tree head to search */ 171254562Scy/* addr(I) - pointer to address to find */ 172254562Scy/* */ 173254562Scy/* Search the radix tree for the best match to the address pointed to by */ 174254562Scy/* "addr" and return a pointer to that node. This search will not match the */ 175254562Scy/* address information stored in either of the root leaves as neither of */ 176254562Scy/* them are considered to be part of the tree of data being stored. */ 177254562Scy/* ------------------------------------------------------------------------ */ 178254562Scystatic ipf_rdx_node_t * 179254562Scyipf_rx_match(head, addr) 180254562Scy ipf_rdx_head_t *head; 181254562Scy addrfamily_t *addr; 182254562Scy{ 183254562Scy ipf_rdx_mask_t *masknode; 184254562Scy ipf_rdx_node_t *prev; 185254562Scy ipf_rdx_node_t *node; 186254562Scy ipf_rdx_node_t *cur; 187254562Scy u_32_t *data; 188254562Scy u_32_t *mask; 189254562Scy u_32_t *key; 190254562Scy u_32_t *end; 191254562Scy int len; 192254562Scy int i; 193254562Scy 194254562Scy len = addr->adf_len; 195254562Scy end = (u_32_t *)((u_char *)addr + len); 196254562Scy node = ipf_rx_find_addr(head->root, (u_32_t *)addr); 197254562Scy 198254562Scy /* 199254562Scy * Search the dupkey list for a potential match. 200254562Scy */ 201254562Scy for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) { 202254562Scy i = cur[0].addroff - cur[0].addrkey; 203254562Scy data = cur[0].addrkey + i; 204254562Scy mask = cur[0].maskkey + i; 205254562Scy key = (u_32_t *)addr + i; 206254562Scy for (; key < end; data++, key++, mask++) 207254562Scy if ((*key & *mask) != *data) 208254562Scy break; 209254562Scy if ((end == key) && (cur->root == 0)) 210254562Scy return (cur); /* Equal keys */ 211254562Scy } 212254562Scy prev = node->parent; 213254562Scy key = (u_32_t *)addr; 214254562Scy 215254562Scy for (node = prev; node->root == 0; node = node->parent) { 216254562Scy /* 217254562Scy * We know that the node hasn't matched so therefore only 218254562Scy * the entries in the mask list are searched, not the top 219254562Scy * node nor the dupkey list. 220254562Scy */ 221254562Scy masknode = node->masks; 222254562Scy for (; masknode != NULL; masknode = masknode->next) { 223254562Scy if (masknode->maskbitcount > node->maskbitcount) 224254562Scy continue; 225254562Scy cur = masknode->node; 226254562Scy for (i = ADF_OFF >> 2; i <= node->offset; i++) { 227254562Scy if ((key[i] & masknode->mask[i]) == 228254562Scy cur->addrkey[i]) 229254562Scy return (cur); 230254562Scy } 231254562Scy } 232254562Scy } 233254562Scy 234254562Scy return NULL; 235254562Scy} 236254562Scy 237254562Scy 238254562Scy/* ------------------------------------------------------------------------ */ 239254562Scy/* Function: ipf_rx_lookup */ 240254562Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 241254562Scy/* added to the tree. */ 242254562Scy/* Paramters: head(I) - pointer to tree head to search */ 243254562Scy/* addr(I) - address part of the key to match */ 244254562Scy/* mask(I) - netmask part of the key to match */ 245254562Scy/* */ 246254562Scy/* ipf_rx_lookup searches for an exact match on (addr,mask). The intention */ 247254562Scy/* is to see if a given key is in the tree, not to see if a route exists. */ 248254562Scy/* ------------------------------------------------------------------------ */ 249254562Scyipf_rdx_node_t * 250254562Scyipf_rx_lookup(head, addr, mask) 251254562Scy ipf_rdx_head_t *head; 252254562Scy addrfamily_t *addr, *mask; 253254562Scy{ 254254562Scy ipf_rdx_node_t *found; 255254562Scy ipf_rdx_node_t *node; 256254562Scy u_32_t *akey; 257254562Scy int count; 258254562Scy 259254562Scy found = ipf_rx_find_addr(head->root, (u_32_t *)addr); 260254562Scy if (found->root == 1) 261254562Scy return NULL; 262254562Scy 263254562Scy /* 264254562Scy * It is possible to find a matching address in the tree but for the 265254562Scy * netmask to not match. If the netmask does not match and there is 266254562Scy * no list of alternatives present at dupkey, return a failure. 267254562Scy */ 268254562Scy count = count_mask_bits(mask, NULL); 269254562Scy if (count != found->maskbitcount && found->dupkey == NULL) 270254562Scy return (NULL); 271254562Scy 272254562Scy akey = (u_32_t *)addr; 273254562Scy if ((found->addrkey[found->offset] & found->maskkey[found->offset]) != 274254562Scy akey[found->offset]) 275254562Scy return NULL; 276254562Scy 277254562Scy if (found->dupkey != NULL) { 278254562Scy node = found; 279254562Scy while (node != NULL && node->maskbitcount != count) 280254562Scy node = node->dupkey; 281254562Scy if (node == NULL) 282254562Scy return (NULL); 283254562Scy found = node; 284254562Scy } 285254562Scy return found; 286254562Scy} 287254562Scy 288254562Scy 289254562Scy/* ------------------------------------------------------------------------ */ 290254562Scy/* Function: ipf_rx_attach_mask */ 291254562Scy/* Returns: Nil */ 292254562Scy/* Parameters: node(I) - pointer to a radix tree node */ 293254562Scy/* mask(I) - pointer to mask structure to add */ 294254562Scy/* */ 295254562Scy/* Add the netmask to the given node in an ordering where the most specific */ 296254562Scy/* netmask is at the top of the list. */ 297254562Scy/* ------------------------------------------------------------------------ */ 298254562Scystatic void 299254562Scyipf_rx_attach_mask(node, mask) 300254562Scy ipf_rdx_node_t *node; 301254562Scy ipf_rdx_mask_t *mask; 302254562Scy{ 303254562Scy ipf_rdx_mask_t **pm; 304254562Scy ipf_rdx_mask_t *m; 305254562Scy 306254562Scy for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next) 307254562Scy if (m->maskbitcount < mask->maskbitcount) 308254562Scy break; 309254562Scy mask->next = *pm; 310254562Scy *pm = mask; 311254562Scy} 312254562Scy 313254562Scy 314254562Scy/* ------------------------------------------------------------------------ */ 315254562Scy/* Function: ipf_rx_insert */ 316254562Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 317254562Scy/* added to the tree. */ 318254562Scy/* Paramters: head(I) - pointer to tree head to add nodes to */ 319254562Scy/* nodes(I) - pointer to radix nodes to be added */ 320254562Scy/* dup(O) - set to 1 if node is a duplicate, else 0. */ 321254562Scy/* */ 322254562Scy/* Add the new radix tree entry that owns nodes[] to the tree given by head.*/ 323254562Scy/* If there is already a matching key in the table, "dup" will be set to 1 */ 324254562Scy/* and the existing node pointer returned if there is a complete key match. */ 325254562Scy/* A complete key match is a matching of all key data that is presented by */ 326254562Scy/* by the netmask. */ 327254562Scy/* ------------------------------------------------------------------------ */ 328254562Scystatic ipf_rdx_node_t * 329254562Scyipf_rx_insert(head, nodes, dup) 330254562Scy ipf_rdx_head_t *head; 331254562Scy ipf_rdx_node_t nodes[2]; 332254562Scy int *dup; 333254562Scy{ 334254562Scy ipf_rdx_mask_t **pmask; 335254562Scy ipf_rdx_node_t *node; 336254562Scy ipf_rdx_node_t *prev; 337254562Scy ipf_rdx_mask_t *mask; 338254562Scy ipf_rdx_node_t *cur; 339254562Scy u_32_t nodemask; 340254562Scy u_32_t *addr; 341254562Scy u_32_t *data; 342254562Scy int nodebits; 343254562Scy u_32_t *key; 344254562Scy u_32_t *end; 345254562Scy u_32_t bits; 346254562Scy int nodekey; 347254562Scy int nodeoff; 348254562Scy int nlen; 349254562Scy int len; 350254562Scy 351254562Scy addr = nodes[0].addrkey; 352254562Scy 353254562Scy node = ipf_rx_find_addr(head->root, addr); 354254562Scy len = ((addrfamily_t *)addr)->adf_len; 355254562Scy key = (u_32_t *)&((addrfamily_t *)addr)->adf_addr; 356254562Scy data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr; 357254562Scy end = (u_32_t *)((u_char *)addr + len); 358254562Scy for (nlen = 0; key < end; data++, key++, nlen += 32) 359254562Scy if (*key != *data) 360254562Scy break; 361254562Scy if (end == data) { 362254562Scy *dup = 1; 363254562Scy return (node); /* Equal keys */ 364254562Scy } 365254562Scy *dup = 0; 366254562Scy 367254562Scy bits = (ntohl(*data) ^ ntohl(*key)); 368254562Scy for (; bits != 0; nlen++) { 369254562Scy if ((bits & 0x80000000) != 0) 370254562Scy break; 371254562Scy bits <<= 1; 372254562Scy } 373254562Scy nlen += ADF_OFF_BITS; 374254562Scy nodes[1].index = nlen; 375254562Scy nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f)); 376254562Scy nodes[0].offset = nlen / 32; 377254562Scy nodes[1].offset = nlen / 32; 378254562Scy 379254562Scy /* 380254562Scy * Walk through the tree and look for the correct place to attach 381254562Scy * this node. ipf_rx_fin_addr is not used here because the place 382254562Scy * to attach this node may be an internal node (same key, different 383254562Scy * netmask.) Additionally, the depth of the search is forcibly limited 384254562Scy * here to not exceed the netmask, so that a short netmask will be 385254562Scy * added higher up the tree even if there are lower branches. 386254562Scy */ 387254562Scy cur = head->root; 388254562Scy key = nodes[0].addrkey; 389254562Scy do { 390254562Scy prev = cur; 391254562Scy if (key[cur->offset] & cur->bitmask) { 392254562Scy cur = cur->right; 393254562Scy } else { 394254562Scy cur = cur->left; 395254562Scy } 396254562Scy } while (nlen > (unsigned)cur->index); 397254562Scy 398254562Scy if ((key[prev->offset] & prev->bitmask) == 0) { 399254562Scy prev->left = &nodes[1]; 400254562Scy } else { 401254562Scy prev->right = &nodes[1]; 402254562Scy } 403254562Scy cur->parent = &nodes[1]; 404254562Scy nodes[1].parent = prev; 405254562Scy if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) { 406254562Scy nodes[1].right = cur; 407254562Scy } else { 408254562Scy nodes[1].right = &nodes[0]; 409254562Scy nodes[1].left = cur; 410254562Scy } 411254562Scy 412254562Scy nodeoff = nodes[0].offset; 413254562Scy nodekey = nodes[0].addrkey[nodeoff]; 414254562Scy nodemask = nodes[0].lastmask; 415254562Scy nodebits = nodes[0].maskbitcount; 416254562Scy prev = NULL; 417254562Scy /* 418254562Scy * Find the node up the tree with the largest pattern that still 419254562Scy * matches the node being inserted to see if this mask can be 420254562Scy * moved there. 421254562Scy */ 422254562Scy for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) { 423254562Scy if (cur->maskbitcount <= nodebits) 424254562Scy break; 425254562Scy if (((cur - 1)->addrkey[nodeoff] & nodemask) != nodekey) 426254562Scy break; 427254562Scy prev = cur; 428254562Scy } 429254562Scy 430254562Scy KMALLOC(mask, ipf_rdx_mask_t *); 431254562Scy if (mask == NULL) 432254562Scy return NULL; 433254562Scy bzero(mask, sizeof(*mask)); 434254562Scy mask->next = NULL; 435254562Scy mask->node = &nodes[0]; 436254562Scy mask->maskbitcount = nodebits; 437254562Scy mask->mask = nodes[0].maskkey; 438254562Scy nodes[0].mymask = mask; 439254562Scy 440254562Scy if (prev != NULL) { 441254562Scy ipf_rdx_mask_t *m; 442254562Scy 443254562Scy for (pmask = &prev->masks; (m = *pmask) != NULL; 444254562Scy pmask = &m->next) { 445254562Scy if (m->maskbitcount < nodebits) 446254562Scy break; 447254562Scy } 448254562Scy } else { 449254562Scy /* 450254562Scy * No higher up nodes qualify, so attach mask locally. 451254562Scy */ 452254562Scy pmask = &nodes[0].masks; 453254562Scy } 454254562Scy mask->next = *pmask; 455254562Scy *pmask = mask; 456254562Scy 457254562Scy /* 458254562Scy * Search the mask list on each child to see if there are any masks 459254562Scy * there that can be moved up to this newly inserted node. 460254562Scy */ 461254562Scy cur = nodes[1].right; 462254562Scy if (cur->root == 0) { 463254562Scy for (pmask = &cur->masks; (mask = *pmask) != NULL; ) { 464254562Scy if (mask->maskbitcount < nodebits) { 465254562Scy *pmask = mask->next; 466254562Scy ipf_rx_attach_mask(&nodes[0], mask); 467254562Scy } else { 468254562Scy pmask = &mask->next; 469254562Scy } 470254562Scy } 471254562Scy } 472254562Scy cur = nodes[1].left; 473254562Scy if (cur->root == 0 && cur != &nodes[0]) { 474254562Scy for (pmask = &cur->masks; (mask = *pmask) != NULL; ) { 475254562Scy if (mask->maskbitcount < nodebits) { 476254562Scy *pmask = mask->next; 477254562Scy ipf_rx_attach_mask(&nodes[0], mask); 478254562Scy } else { 479254562Scy pmask = &mask->next; 480254562Scy } 481254562Scy } 482254562Scy } 483254562Scy return (&nodes[0]); 484254562Scy} 485254562Scy 486254562Scy/* ------------------------------------------------------------------------ */ 487254562Scy/* Function: ipf_rx_addroute */ 488254562Scy/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */ 489254562Scy/* added to the tree. */ 490254562Scy/* Paramters: head(I) - pointer to tree head to search */ 491254562Scy/* addr(I) - address portion of "route" to add */ 492254562Scy/* mask(I) - netmask portion of "route" to add */ 493254562Scy/* nodes(I) - radix tree data nodes inside allocate structure */ 494254562Scy/* */ 495254562Scy/* Attempt to add a node to the radix tree. The key for the node is the */ 496254562Scy/* (addr,mask). No memory allocation for the radix nodes themselves is */ 497254562Scy/* performed here, the data structure that this radix node is being used to */ 498254562Scy/* find is expected to house the node data itself however the call to */ 499254562Scy/* ipf_rx_insert() will attempt to allocate memory in order for netmask to */ 500254562Scy/* be promoted further up the tree. */ 501254562Scy/* In this case, the ip_pool_node_t structure from ip_pool.h contains both */ 502254562Scy/* the key material (addr,mask) and the radix tree nodes[]. */ 503254562Scy/* */ 504254562Scy/* The mechanics of inserting the node into the tree is handled by the */ 505254562Scy/* function ipf_rx_insert() above. Here, the code deals with the case */ 506254562Scy/* where the data to be inserted is a duplicate. */ 507254562Scy/* ------------------------------------------------------------------------ */ 508254562Scyipf_rdx_node_t * 509254562Scyipf_rx_addroute(head, addr, mask, nodes) 510254562Scy ipf_rdx_head_t *head; 511254562Scy addrfamily_t *addr, *mask; 512254562Scy ipf_rdx_node_t *nodes; 513254562Scy{ 514254562Scy ipf_rdx_node_t *node; 515254562Scy ipf_rdx_node_t *prev; 516254562Scy ipf_rdx_node_t *x; 517254562Scy int dup; 518254562Scy 519254562Scy buildnodes(addr, mask, nodes); 520254562Scy x = ipf_rx_insert(head, nodes, &dup); 521254562Scy if (x == NULL) 522254562Scy return NULL; 523254562Scy 524254562Scy if (dup == 1) { 525254562Scy node = &nodes[0]; 526254562Scy prev = NULL; 527254562Scy /* 528254562Scy * The duplicate list is kept sorted with the longest 529254562Scy * mask at the top, meaning that the most specific entry 530254562Scy * in the listis found first. This list thus allows for 531254562Scy * duplicates such as 128.128.0.0/32 and 128.128.0.0/16. 532254562Scy */ 533254562Scy while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) { 534254562Scy prev = x; 535254562Scy x = x->dupkey; 536254562Scy } 537254562Scy 538254562Scy /* 539254562Scy * Is it a complete duplicate? If so, return NULL and 540254562Scy * fail the insert. Otherwise, insert it into the list 541254562Scy * of netmasks active for this key. 542254562Scy */ 543254562Scy if ((x != NULL) && (x->maskbitcount == node->maskbitcount)) 544254562Scy return (NULL); 545254562Scy 546254562Scy if (prev != NULL) { 547254562Scy nodes[0].dupkey = x; 548254562Scy prev->dupkey = &nodes[0]; 549254562Scy nodes[0].parent = prev; 550254562Scy if (x != NULL) 551254562Scy x->parent = &nodes[0]; 552254562Scy } else { 553254562Scy nodes[0].dupkey = x->dupkey; 554254562Scy prev = x->parent; 555254562Scy nodes[0].parent = prev; 556254562Scy x->parent = &nodes[0]; 557254562Scy if (prev->left == x) 558254562Scy prev->left = &nodes[0]; 559254562Scy else 560254562Scy prev->right = &nodes[0]; 561254562Scy } 562254562Scy } 563254562Scy 564254562Scy return &nodes[0]; 565254562Scy} 566254562Scy 567254562Scy 568254562Scy/* ------------------------------------------------------------------------ */ 569254562Scy/* Function: ipf_rx_delete */ 570254562Scy/* Returns: ipf_rdx_node_t * - NULL on error, else node removed from */ 571254562Scy/* the tree. */ 572254562Scy/* Paramters: head(I) - pointer to tree head to search */ 573254562Scy/* addr(I) - pointer to the address part of the key */ 574254562Scy/* mask(I) - pointer to the netmask part of the key */ 575254562Scy/* */ 576254562Scy/* Search for an entry in the radix tree that is an exact match for (addr, */ 577254562Scy/* mask) and remove it if it exists. In the case where (addr,mask) is a not */ 578254562Scy/* a unique key, the tree structure itself is not changed - only the list */ 579254562Scy/* of duplicate keys. */ 580254562Scy/* ------------------------------------------------------------------------ */ 581254562Scyipf_rdx_node_t * 582254562Scyipf_rx_delete(head, addr, mask) 583254562Scy ipf_rdx_head_t *head; 584254562Scy addrfamily_t *addr, *mask; 585254562Scy{ 586254562Scy ipf_rdx_mask_t **pmask; 587254562Scy ipf_rdx_node_t *parent; 588254562Scy ipf_rdx_node_t *found; 589254562Scy ipf_rdx_node_t *prev; 590254562Scy ipf_rdx_node_t *node; 591254562Scy ipf_rdx_node_t *cur; 592254562Scy ipf_rdx_mask_t *m; 593254562Scy int count; 594254562Scy 595254562Scy found = ipf_rx_find_addr(head->root, (u_32_t *)addr); 596254562Scy if (found == NULL) 597254562Scy return NULL; 598254562Scy if (found->root == 1) 599254562Scy return NULL; 600254562Scy count = count_mask_bits(mask, NULL); 601254562Scy parent = found->parent; 602254562Scy if (found->dupkey != NULL) { 603254562Scy node = found; 604254562Scy while (node != NULL && node->maskbitcount != count) 605254562Scy node = node->dupkey; 606254562Scy if (node == NULL) 607254562Scy return (NULL); 608254562Scy if (node != found) { 609254562Scy /* 610254562Scy * Remove from the dupkey list. Here, "parent" is 611254562Scy * the previous node on the list (rather than tree) 612254562Scy * and "dupkey" is the next node on the list. 613254562Scy */ 614254562Scy parent = node->parent; 615254562Scy parent->dupkey = node->dupkey; 616254562Scy node->dupkey->parent = parent; 617254562Scy } else { 618254562Scy /* 619254562Scy * 620254562Scy * When removing the top node of the dupkey list, 621254562Scy * the pointers at the top of the list that point 622254562Scy * to other tree nodes need to be preserved and 623254562Scy * any children must have their parent updated. 624254562Scy */ 625254562Scy node = node->dupkey; 626254562Scy node->parent = found->parent; 627254562Scy node->right = found->right; 628254562Scy node->left = found->left; 629254562Scy found->right->parent = node; 630254562Scy found->left->parent = node; 631254562Scy if (parent->left == found) 632254562Scy parent->left = node; 633254562Scy else 634254562Scy parent->right= node; 635254562Scy } 636254562Scy } else { 637254562Scy if (count != found->maskbitcount) 638254562Scy return (NULL); 639254562Scy /* 640254562Scy * Remove the node from the tree and reconnect the subtree 641254562Scy * below. 642254562Scy */ 643254562Scy /* 644254562Scy * If there is a tree to the left, look for something to 645254562Scy * attach in place of "found". 646254562Scy */ 647254562Scy prev = found + 1; 648254562Scy cur = parent->parent; 649254562Scy if (parent != found + 1) { 650254562Scy if ((found + 1)->parent->right == found + 1) 651254562Scy (found + 1)->parent->right = parent; 652254562Scy else 653254562Scy (found + 1)->parent->left = parent; 654254562Scy if (cur->right == parent) { 655254562Scy if (parent->left == found) { 656254562Scy cur->right = parent->right; 657254562Scy } else if (parent->left != parent - 1) { 658254562Scy cur->right = parent->left; 659254562Scy } else { 660254562Scy cur->right = parent - 1; 661254562Scy } 662254562Scy cur->right->parent = cur; 663254562Scy } else { 664254562Scy if (parent->right == found) { 665254562Scy cur->left = parent->left; 666254562Scy } else if (parent->right != parent - 1) { 667254562Scy cur->left = parent->right; 668254562Scy } else { 669254562Scy cur->left = parent - 1; 670254562Scy } 671254562Scy cur->left->parent = cur; 672254562Scy } 673254562Scy parent->left = (found + 1)->left; 674254562Scy if ((found + 1)->right != parent) 675254562Scy parent->right = (found + 1)->right; 676254562Scy parent->left->parent = parent; 677254562Scy parent->right->parent = parent; 678254562Scy parent->parent = (found + 1)->parent; 679254562Scy 680254562Scy parent->bitmask = prev->bitmask; 681254562Scy parent->offset = prev->offset; 682254562Scy parent->index = prev->index; 683254562Scy } else { 684254562Scy /* 685254562Scy * We found an edge node. 686254562Scy */ 687254562Scy cur = parent->parent; 688254562Scy if (cur->left == parent) { 689254562Scy if (parent->left == found) { 690254562Scy cur->left = parent->right; 691254562Scy parent->right->parent = cur; 692254562Scy } else { 693254562Scy cur->left = parent->left; 694254562Scy parent->left->parent = cur; 695254562Scy } 696254562Scy } else { 697254562Scy if (parent->right != found) { 698254562Scy cur->right = parent->right; 699254562Scy parent->right->parent = cur; 700254562Scy } else { 701254562Scy cur->right = parent->left; 702254562Scy prev->left->parent = cur; 703254562Scy } 704254562Scy } 705254562Scy } 706254562Scy } 707254562Scy 708254562Scy /* 709254562Scy * Remove mask associated with this node. 710254562Scy */ 711254562Scy for (cur = parent; cur->root == 0; cur = cur->parent) { 712254562Scy ipf_rdx_mask_t **pm; 713254562Scy 714254562Scy if (cur->maskbitcount <= found->maskbitcount) 715254562Scy break; 716254562Scy if (((cur - 1)->addrkey[found->offset] & found->bitmask) != 717254562Scy found->addrkey[found->offset]) 718254562Scy break; 719254562Scy for (pm = &cur->masks; (m = *pm) != NULL; ) 720254562Scy if (m->node == cur) { 721254562Scy *pm = m->next; 722254562Scy break; 723254562Scy } else { 724254562Scy pm = &m->next; 725254562Scy } 726254562Scy } 727254562Scy KFREE(found->mymask); 728254562Scy 729254562Scy /* 730254562Scy * Masks that have been brought up to this node from below need to 731254562Scy * be sent back down. 732254562Scy */ 733254562Scy for (pmask = &parent->masks; (m = *pmask) != NULL; ) { 734254562Scy *pmask = m->next; 735254562Scy cur = m->node; 736254562Scy if (cur == found) 737254562Scy continue; 738254562Scy if (found->addrkey[cur->offset] & cur->lastmask) { 739254562Scy ipf_rx_attach_mask(parent->right, m); 740254562Scy } else if (parent->left != found) { 741254562Scy ipf_rx_attach_mask(parent->left, m); 742254562Scy } 743254562Scy } 744254562Scy 745254562Scy return (found); 746254562Scy} 747254562Scy 748254562Scy 749254562Scy/* ------------------------------------------------------------------------ */ 750254562Scy/* Function: ipf_rx_walktree */ 751254562Scy/* Returns: Nil */ 752254562Scy/* Paramters: head(I) - pointer to tree head to search */ 753254562Scy/* walker(I) - function to call for each node in the tree */ 754254562Scy/* arg(I) - parameter to pass to walker, in addition to the */ 755254562Scy/* node pointer */ 756254562Scy/* */ 757254562Scy/* A standard tree walking function except that it is iterative, rather */ 758254562Scy/* than recursive and tracks the next node in case the "walker" function */ 759254562Scy/* should happen to delete and free the current node. It thus goes without */ 760254562Scy/* saying that the "walker" function is not permitted to cause any change */ 761254562Scy/* in the validity of the data found at either the left or right child. */ 762254562Scy/* ------------------------------------------------------------------------ */ 763254562Scyvoid 764254562Scyipf_rx_walktree(head, walker, arg) 765254562Scy ipf_rdx_head_t *head; 766254562Scy radix_walk_func_t walker; 767254562Scy void *arg; 768254562Scy{ 769254562Scy ipf_rdx_node_t *next; 770254562Scy ipf_rdx_node_t *node = head->root; 771254562Scy ipf_rdx_node_t *base; 772254562Scy 773254562Scy while (node->index >= 0) 774254562Scy node = node->left; 775254562Scy 776254562Scy for (;;) { 777254562Scy base = node; 778254562Scy while ((node->parent->right == node) && (node->root == 0)) 779254562Scy node = node->parent; 780254562Scy 781254562Scy for (node = node->parent->right; node->index >= 0; ) 782254562Scy node = node->left; 783254562Scy next = node; 784254562Scy 785254562Scy for (node = base; node != NULL; node = base) { 786254562Scy base = node->dupkey; 787254562Scy if (node->root == 0) 788254562Scy walker(node, arg); 789254562Scy } 790254562Scy node = next; 791254562Scy if (node->root) 792254562Scy return; 793254562Scy } 794254562Scy} 795254562Scy 796254562Scy 797254562Scy/* ------------------------------------------------------------------------ */ 798254562Scy/* Function: ipf_rx_inithead */ 799254562Scy/* Returns: int - 0 = success, else failure */ 800254562Scy/* Paramters: softr(I) - pointer to radix context */ 801254562Scy/* headp(O) - location for where to store allocated tree head */ 802254562Scy/* */ 803254562Scy/* This function allocates and initialises a radix tree head structure. */ 804254562Scy/* As a traditional radix tree, node 0 is used as the "0" sentinel and node */ 805254562Scy/* "2" is used as the all ones sentinel, leaving node "1" as the root from */ 806254562Scy/* which the tree is hung with node "0" on its left and node "2" to the */ 807254562Scy/* right. The context, "softr", is used here to provide a common source of */ 808254562Scy/* the zeroes and ones data rather than have one per head. */ 809254562Scy/* ------------------------------------------------------------------------ */ 810254562Scyint 811254562Scyipf_rx_inithead(softr, headp) 812254562Scy radix_softc_t *softr; 813254562Scy ipf_rdx_head_t **headp; 814254562Scy{ 815254562Scy ipf_rdx_head_t *ptr; 816254562Scy ipf_rdx_node_t *node; 817254562Scy 818254562Scy KMALLOC(ptr, ipf_rdx_head_t *); 819254562Scy *headp = ptr; 820254562Scy if (ptr == NULL) 821254562Scy return -1; 822254562Scy bzero(ptr, sizeof(*ptr)); 823254562Scy node = ptr->nodes; 824254562Scy ptr->root = node + 1; 825254562Scy node[0].index = ADF_OFF_BITS; 826254562Scy node[0].index = -1 - node[0].index; 827254562Scy node[1].index = ADF_OFF_BITS; 828254562Scy node[2].index = node[0].index; 829254562Scy node[0].parent = node + 1; 830254562Scy node[1].parent = node + 1; 831254562Scy node[2].parent = node + 1; 832254562Scy node[1].bitmask = htonl(0x80000000); 833254562Scy node[0].root = 1; 834254562Scy node[1].root = 1; 835254562Scy node[2].root = 1; 836254562Scy node[0].offset = ADF_OFF_BITS >> 5; 837254562Scy node[1].offset = ADF_OFF_BITS >> 5; 838254562Scy node[2].offset = ADF_OFF_BITS >> 5; 839254562Scy node[1].left = &node[0]; 840254562Scy node[1].right = &node[2]; 841254562Scy node[0].addrkey = (u_32_t *)softr->zeros; 842254562Scy node[2].addrkey = (u_32_t *)softr->ones; 843254562Scy#ifdef RDX_DEBUG 844254562Scy (void) strcpy(node[0].name, "0_ROOT"); 845254562Scy (void) strcpy(node[1].name, "1_ROOT"); 846254562Scy (void) strcpy(node[2].name, "2_ROOT"); 847254562Scy#endif 848254562Scy 849254562Scy ptr->addaddr = ipf_rx_addroute; 850254562Scy ptr->deladdr = ipf_rx_delete; 851254562Scy ptr->lookup = ipf_rx_lookup; 852254562Scy ptr->matchaddr = ipf_rx_match; 853254562Scy ptr->walktree = ipf_rx_walktree; 854254562Scy return 0; 855254562Scy} 856254562Scy 857254562Scy 858254562Scy/* ------------------------------------------------------------------------ */ 859254562Scy/* Function: ipf_rx_freehead */ 860254562Scy/* Returns: Nil */ 861254562Scy/* Paramters: head(I) - pointer to tree head to free */ 862254562Scy/* */ 863254562Scy/* This function simply free's up the radix tree head. Prior to calling */ 864254562Scy/* this function, it is expected that the tree will have been emptied. */ 865254562Scy/* ------------------------------------------------------------------------ */ 866254562Scyvoid 867254562Scyipf_rx_freehead(head) 868254562Scy ipf_rdx_head_t *head; 869254562Scy{ 870254562Scy KFREE(head); 871254562Scy} 872254562Scy 873254562Scy 874254562Scy/* ------------------------------------------------------------------------ */ 875254562Scy/* Function: ipf_rx_create */ 876254562Scy/* Parameters: Nil */ 877254562Scy/* */ 878254562Scy/* ------------------------------------------------------------------------ */ 879254562Scyvoid * 880254562Scyipf_rx_create() 881254562Scy{ 882254562Scy radix_softc_t *softr; 883254562Scy 884254562Scy KMALLOC(softr, radix_softc_t *); 885254562Scy if (softr == NULL) 886254562Scy return NULL; 887254562Scy bzero((char *)softr, sizeof(*softr)); 888254562Scy 889254562Scy KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t)); 890254562Scy if (softr->zeros == NULL) { 891254562Scy KFREE(softr); 892254562Scy return (NULL); 893254562Scy } 894254562Scy softr->ones = softr->zeros + sizeof(addrfamily_t); 895254562Scy 896254562Scy return softr; 897254562Scy} 898254562Scy 899254562Scy 900254562Scy/* ------------------------------------------------------------------------ */ 901254562Scy/* Function: ipf_rx_init */ 902254562Scy/* Returns: int - 0 = success (always) */ 903254562Scy/* */ 904254562Scy/* ------------------------------------------------------------------------ */ 905254562Scyint 906254562Scyipf_rx_init(ctx) 907254562Scy void *ctx; 908254562Scy{ 909254562Scy radix_softc_t *softr = ctx; 910254562Scy 911254562Scy memset(softr->zeros, 0, 3 * sizeof(addrfamily_t)); 912254562Scy memset(softr->ones, 0xff, sizeof(addrfamily_t)); 913254562Scy 914254562Scy return (0); 915254562Scy} 916254562Scy 917254562Scy 918254562Scy/* ------------------------------------------------------------------------ */ 919254562Scy/* Function: ipf_rx_destroy */ 920254562Scy/* Returns: Nil */ 921254562Scy/* */ 922254562Scy/* ------------------------------------------------------------------------ */ 923254562Scyvoid 924254562Scyipf_rx_destroy(ctx) 925254562Scy void *ctx; 926254562Scy{ 927254562Scy radix_softc_t *softr = ctx; 928254562Scy 929254562Scy if (softr->zeros != NULL) 930254562Scy KFREES(softr->zeros, 3 * sizeof(addrfamily_t)); 931254562Scy KFREE(softr); 932254562Scy} 933254562Scy 934254562Scy/* ====================================================================== */ 935254562Scy 936254562Scy#ifdef RDX_DEBUG 937254562Scy/* 938254562Scy * To compile this file as a standalone test unit, use -DRDX_DEBUG=1 939254562Scy */ 940254562Scy#define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name) 941254562Scy#define GNAME(y) ((y) == NULL ? "NULL" : NAME(y)) 942254562Scy 943254562Scytypedef struct myst { 944254562Scy struct ipf_rdx_node nodes[2]; 945254562Scy addrfamily_t dst; 946254562Scy addrfamily_t mask; 947254562Scy struct myst *next; 948254562Scy int printed; 949254562Scy} myst_t; 950254562Scy 951254562Scytypedef struct tabe_s { 952254562Scy char *host; 953254562Scy char *mask; 954254562Scy char *what; 955254562Scy} tabe_t; 956254562Scy 957254562Scytabe_t builtin[] = { 958254562Scy#if 1 959254562Scy { "192:168:100::0", "48", "d" }, 960254562Scy { "192:168:100::2", "128", "d" }, 961254562Scy#else 962254562Scy { "127.192.0.0", "255.255.255.0", "d" }, 963254562Scy { "127.128.0.0", "255.255.255.0", "d" }, 964254562Scy { "127.96.0.0", "255.255.255.0", "d" }, 965254562Scy { "127.80.0.0", "255.255.255.0", "d" }, 966254562Scy { "127.72.0.0", "255.255.255.0", "d" }, 967254562Scy { "127.64.0.0", "255.255.255.0", "d" }, 968254562Scy { "127.56.0.0", "255.255.255.0", "d" }, 969254562Scy { "127.48.0.0", "255.255.255.0", "d" }, 970254562Scy { "127.40.0.0", "255.255.255.0", "d" }, 971254562Scy { "127.32.0.0", "255.255.255.0", "d" }, 972254562Scy { "127.24.0.0", "255.255.255.0", "d" }, 973254562Scy { "127.16.0.0", "255.255.255.0", "d" }, 974254562Scy { "127.8.0.0", "255.255.255.0", "d" }, 975254562Scy { "124.0.0.0", "255.0.0.0", "d" }, 976254562Scy { "125.0.0.0", "255.0.0.0", "d" }, 977254562Scy { "126.0.0.0", "255.0.0.0", "d" }, 978254562Scy { "127.0.0.0", "255.0.0.0", "d" }, 979254562Scy { "10.0.0.0", "255.0.0.0", "d" }, 980254562Scy { "128.250.0.0", "255.255.0.0", "d" }, 981254562Scy { "192.168.0.0", "255.255.0.0", "d" }, 982254562Scy { "192.168.1.0", "255.255.255.0", "d" }, 983254562Scy#endif 984254562Scy { NULL, NULL, NULL } 985254562Scy}; 986254562Scy 987254562Scychar *mtable[][1] = { 988254562Scy#if 1 989254562Scy { "192:168:100::2" }, 990254562Scy { "192:168:101::2" }, 991254562Scy#else 992254562Scy { "9.0.0.0" }, 993254562Scy { "9.0.0.1" }, 994254562Scy { "11.0.0.0" }, 995254562Scy { "11.0.0.1" }, 996254562Scy { "127.0.0.1" }, 997254562Scy { "127.0.1.0" }, 998254562Scy { "255.255.255.0" }, 999254562Scy { "126.0.0.1" }, 1000254562Scy { "128.251.0.0" }, 1001254562Scy { "128.251.0.1" }, 1002254562Scy { "128.251.255.255" }, 1003254562Scy { "129.250.0.0" }, 1004254562Scy { "129.250.0.1" }, 1005254562Scy { "192.168.255.255" }, 1006254562Scy#endif 1007254562Scy { NULL } 1008254562Scy}; 1009254562Scy 1010254562Scy 1011254562Scyint forder[22] = { 1012254562Scy 14, 13, 12, 5, 10, 3, 19, 7, 4, 20, 8, 1013254562Scy 2, 17, 9, 16, 11, 15, 1, 6, 18, 0, 21 1014254562Scy}; 1015254562Scy 1016254562Scystatic int nodecount = 0; 1017254562Scymyst_t *myst_top = NULL; 1018254562Scytabe_t *ttable = NULL; 1019254562Scy 1020254562Scyvoid add_addr(ipf_rdx_head_t *, int , int); 1021254562Scyvoid checktree(ipf_rdx_head_t *); 1022254562Scyvoid delete_addr(ipf_rdx_head_t *rnh, int item); 1023254562Scyvoid dumptree(ipf_rdx_head_t *rnh); 1024254562Scyvoid nodeprinter(ipf_rdx_node_t *, void *); 1025254562Scyvoid printroots(ipf_rdx_head_t *); 1026254562Scyvoid random_add(ipf_rdx_head_t *); 1027254562Scyvoid random_delete(ipf_rdx_head_t *); 1028254562Scyvoid test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int); 1029254562Scy 1030254562Scy 1031254562Scystatic void 1032254562Scyipf_rx_freenode(node, arg) 1033254562Scy ipf_rdx_node_t *node; 1034254562Scy void *arg; 1035254562Scy{ 1036254562Scy ipf_rdx_head_t *head = arg; 1037254562Scy ipf_rdx_node_t *rv; 1038254562Scy myst_t *stp; 1039254562Scy 1040254562Scy stp = (myst_t *)node; 1041254562Scy rv = ipf_rx_delete(head, &stp->dst, &stp->mask); 1042254562Scy if (rv != NULL) { 1043254562Scy free(rv); 1044254562Scy } 1045254562Scy} 1046254562Scy 1047254562Scy 1048254562Scyconst char * 1049254562Scyaddrname(ap) 1050254562Scy addrfamily_t *ap; 1051254562Scy{ 1052254562Scy static char name[80]; 1053254562Scy const char *txt; 1054254562Scy 1055254562Scy bzero((char *)name, sizeof(name)); 1056254562Scy txt = inet_ntop(ap->adf_family, &ap->adf_addr, name, 1057254562Scy sizeof(name)); 1058254562Scy return txt; 1059254562Scy} 1060254562Scy 1061254562Scy 1062254562Scyvoid 1063254562Scyfill6bits(bits, msk) 1064254562Scy int bits; 1065254562Scy u_int *msk; 1066254562Scy{ 1067254562Scy if (bits == 0) { 1068254562Scy msk[0] = 0; 1069254562Scy msk[1] = 0; 1070254562Scy msk[2] = 0; 1071254562Scy msk[3] = 0; 1072254562Scy return; 1073254562Scy } 1074254562Scy 1075254562Scy msk[0] = 0xffffffff; 1076254562Scy msk[1] = 0xffffffff; 1077254562Scy msk[2] = 0xffffffff; 1078254562Scy msk[3] = 0xffffffff; 1079254562Scy 1080254562Scy if (bits == 128) 1081254562Scy return; 1082254562Scy if (bits > 96) { 1083254562Scy msk[3] = htonl(msk[3] << (128 - bits)); 1084254562Scy } else if (bits > 64) { 1085254562Scy msk[3] = 0; 1086254562Scy msk[2] = htonl(msk[2] << (96 - bits)); 1087254562Scy } else if (bits > 32) { 1088254562Scy msk[3] = 0; 1089254562Scy msk[2] = 0; 1090254562Scy msk[1] = htonl(msk[1] << (64 - bits)); 1091254562Scy } else { 1092254562Scy msk[3] = 0; 1093254562Scy msk[2] = 0; 1094254562Scy msk[1] = 0; 1095254562Scy msk[0] = htonl(msk[0] << (32 - bits)); 1096254562Scy } 1097254562Scy} 1098254562Scy 1099254562Scy 1100254562Scyvoid 1101254562Scysetaddr(afp, str) 1102254562Scy addrfamily_t *afp; 1103254562Scy char *str; 1104254562Scy{ 1105254562Scy 1106254562Scy bzero((char *)afp, sizeof(*afp)); 1107254562Scy 1108254562Scy if (strchr(str, ':') == NULL) { 1109254562Scy afp->adf_family = AF_INET; 1110254562Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1111254562Scy } else { 1112254562Scy afp->adf_family = AF_INET6; 1113254562Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16; 1114254562Scy } 1115254562Scy inet_pton(afp->adf_family, str, &afp->adf_addr); 1116254562Scy} 1117254562Scy 1118254562Scy 1119254562Scyvoid 1120254562Scysetmask(afp, str) 1121254562Scy addrfamily_t *afp; 1122254562Scy char *str; 1123254562Scy{ 1124254562Scy if (strchr(str, '.') != NULL) { 1125254562Scy afp->adf_addr.in4.s_addr = inet_addr(str); 1126254562Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1127254562Scy } else if (afp->adf_family == AF_INET) { 1128254562Scy afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str))); 1129254562Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4; 1130254562Scy } else if (afp->adf_family == AF_INET6) { 1131254562Scy fill6bits(atoi(str), afp->adf_addr.i6); 1132254562Scy afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16; 1133254562Scy } 1134254562Scy} 1135254562Scy 1136254562Scy 1137254562Scyvoid 1138254562Scynodeprinter(node, arg) 1139254562Scy ipf_rdx_node_t *node; 1140254562Scy void *arg; 1141254562Scy{ 1142254562Scy myst_t *stp = (myst_t *)node; 1143254562Scy 1144254562Scy printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n", 1145254562Scy node[0].name, 1146254562Scy GNAME(node[1].left), GNAME(node[1].right), 1147254562Scy GNAME(node[0].parent), GNAME(node[1].parent), 1148254562Scy addrname(&stp->dst), node[0].maskbitcount); 1149254562Scy if (stp->printed == -1) 1150254562Scy printf("!!! %d\n", stp->printed); 1151254562Scy else 1152254562Scy stp->printed = 1; 1153254562Scy} 1154254562Scy 1155254562Scy 1156254562Scyvoid 1157254562Scyprintnode(stp) 1158254562Scy myst_t *stp; 1159254562Scy{ 1160254562Scy ipf_rdx_node_t *node = &stp->nodes[0]; 1161254562Scy 1162254562Scy if (stp->nodes[0].index > 0) 1163254562Scy stp = (myst_t *)&stp->nodes[-1]; 1164254562Scy 1165254562Scy printf("Node %-9.9s ", node[0].name); 1166254562Scy printf("L %-9.9s ", GNAME(node[1].left)); 1167254562Scy printf("R %-9.9s ", GNAME(node[1].right)); 1168254562Scy printf("P %9.9s", GNAME(node[0].parent)); 1169254562Scy printf("/%-9.9s ", GNAME(node[1].parent)); 1170254562Scy printf("%s P%d\n", addrname(&stp->dst), stp->printed); 1171254562Scy} 1172254562Scy 1173254562Scy 1174254562Scyvoid 1175254562Scybuildtab(void) 1176254562Scy{ 1177254562Scy char line[80], *s; 1178254562Scy tabe_t *tab; 1179254562Scy int lines; 1180254562Scy FILE *fp; 1181254562Scy 1182254562Scy lines = 0; 1183254562Scy fp = fopen("hosts", "r"); 1184254562Scy 1185254562Scy while (fgets(line, sizeof(line), fp) != NULL) { 1186254562Scy s = strchr(line, '\n'); 1187254562Scy if (s != NULL) 1188254562Scy *s = '\0'; 1189254562Scy lines++; 1190254562Scy if (lines == 1) 1191254562Scy tab = malloc(sizeof(*tab) * 2); 1192254562Scy else 1193254562Scy tab = realloc(tab, (lines + 1) * sizeof(*tab)); 1194254562Scy tab[lines - 1].host = strdup(line); 1195254562Scy s = strchr(tab[lines - 1].host, '/'); 1196254562Scy *s++ = '\0'; 1197254562Scy tab[lines - 1].mask = s; 1198254562Scy tab[lines - 1].what = "d"; 1199254562Scy } 1200254562Scy fclose(fp); 1201254562Scy 1202254562Scy tab[lines].host = NULL; 1203254562Scy tab[lines].mask = NULL; 1204254562Scy tab[lines].what = NULL; 1205254562Scy ttable = tab; 1206254562Scy} 1207254562Scy 1208254562Scy 1209254562Scyvoid 1210254562Scyprintroots(rnh) 1211254562Scy ipf_rdx_head_t *rnh; 1212254562Scy{ 1213254562Scy printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1214254562Scy GNAME(&rnh->nodes[0]), 1215254562Scy rnh->nodes[0].index, GNAME(rnh->nodes[0].parent), 1216254562Scy GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right)); 1217254562Scy printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1218254562Scy GNAME(&rnh->nodes[1]), 1219254562Scy rnh->nodes[1].index, GNAME(rnh->nodes[1].parent), 1220254562Scy GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right)); 1221254562Scy printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n", 1222254562Scy GNAME(&rnh->nodes[2]), 1223254562Scy rnh->nodes[2].index, GNAME(rnh->nodes[2].parent), 1224254562Scy GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right)); 1225254562Scy} 1226254562Scy 1227254562Scy 1228254562Scyint 1229254562Scymain(int argc, char *argv[]) 1230254562Scy{ 1231254562Scy addrfamily_t af; 1232254562Scy ipf_rdx_head_t *rnh; 1233254562Scy radix_softc_t *ctx; 1234254562Scy int j; 1235254562Scy int i; 1236254562Scy 1237254562Scy rnh = NULL; 1238254562Scy 1239254562Scy buildtab(); 1240254562Scy ctx = ipf_rx_create(); 1241254562Scy ipf_rx_init(ctx); 1242254562Scy ipf_rx_inithead(ctx, &rnh); 1243254562Scy 1244254562Scy printf("=== ADD-0 ===\n"); 1245254562Scy for (i = 0; ttable[i].host != NULL; i++) { 1246254562Scy add_addr(rnh, i, i); 1247254562Scy checktree(rnh); 1248254562Scy } 1249254562Scy printroots(rnh); 1250254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1251254562Scy printf("=== DELETE-0 ===\n"); 1252254562Scy for (i = 0; ttable[i].host != NULL; i++) { 1253254562Scy delete_addr(rnh, i); 1254254562Scy printroots(rnh); 1255254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1256254562Scy } 1257254562Scy printf("=== ADD-1 ===\n"); 1258254562Scy for (i = 0; ttable[i].host != NULL; i++) { 1259254562Scy setaddr(&af, ttable[i].host); 1260254562Scy add_addr(rnh, i, i); /*forder[i]); */ 1261254562Scy checktree(rnh); 1262254562Scy } 1263254562Scy dumptree(rnh); 1264254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1265254562Scy printf("=== TEST-1 ===\n"); 1266254562Scy for (i = 0; ttable[i].host != NULL; i++) { 1267254562Scy setaddr(&af, ttable[i].host); 1268254562Scy test_addr(rnh, i, &af, -1); 1269254562Scy } 1270254562Scy 1271254562Scy printf("=== TEST-2 ===\n"); 1272254562Scy for (i = 0; mtable[i][0] != NULL; i++) { 1273254562Scy setaddr(&af, mtable[i][0]); 1274254562Scy test_addr(rnh, i, &af, -1); 1275254562Scy } 1276254562Scy printf("=== DELETE-1 ===\n"); 1277254562Scy for (i = 0; ttable[i].host != NULL; i++) { 1278254562Scy if (ttable[i].what[0] != 'd') 1279254562Scy continue; 1280254562Scy delete_addr(rnh, i); 1281254562Scy for (j = 0; ttable[j].host != NULL; j++) { 1282254562Scy setaddr(&af, ttable[j].host); 1283254562Scy test_addr(rnh, i, &af, 3); 1284254562Scy } 1285254562Scy printroots(rnh); 1286254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1287254562Scy } 1288254562Scy 1289254562Scy dumptree(rnh); 1290254562Scy 1291254562Scy printf("=== ADD-2 ===\n"); 1292254562Scy random_add(rnh); 1293254562Scy checktree(rnh); 1294254562Scy dumptree(rnh); 1295254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1296254562Scy printf("=== DELETE-2 ===\n"); 1297254562Scy random_delete(rnh); 1298254562Scy checktree(rnh); 1299254562Scy dumptree(rnh); 1300254562Scy 1301254562Scy ipf_rx_walktree(rnh, ipf_rx_freenode, rnh); 1302254562Scy 1303254562Scy return 0; 1304254562Scy} 1305254562Scy 1306254562Scy 1307254562Scyvoid 1308254562Scydumptree(rnh) 1309254562Scy ipf_rdx_head_t *rnh; 1310254562Scy{ 1311254562Scy myst_t *stp; 1312254562Scy 1313254562Scy printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n"); 1314254562Scy printroots(rnh); 1315254562Scy for (stp = myst_top; stp; stp = stp->next) 1316254562Scy printnode(stp); 1317254562Scy printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); 1318254562Scy} 1319254562Scy 1320254562Scy 1321254562Scyvoid 1322254562Scytest_addr(rnh, pref, addr, limit) 1323254562Scy ipf_rdx_head_t *rnh; 1324353164Scy int pref, limit; 1325254562Scy addrfamily_t *addr; 1326254562Scy{ 1327254562Scy static int extras[14] = { 0, -1, 1, 3, 5, 8, 9, 1328254562Scy 15, 16, 19, 255, 256, 65535, 65536 1329254562Scy }; 1330254562Scy ipf_rdx_node_t *rn; 1331254562Scy addrfamily_t af; 1332254562Scy char name[80]; 1333254562Scy myst_t *stp; 1334254562Scy int i; 1335254562Scy 1336254562Scy memset(&af, 0, sizeof(af)); 1337254562Scy#if 0 1338254562Scy if (limit < 0 || limit > 14) 1339254562Scy limit = 14; 1340254562Scy 1341254562Scy for (i = 0; i < limit; i++) { 1342254562Scy if (ttable[i].host == NULL) 1343254562Scy break; 1344254562Scy setaddr(&af, ttable[i].host); 1345254562Scy printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af)); 1346254562Scy rn = ipf_rx_match(rnh, &af); 1347254562Scy stp = (myst_t *)rn; 1348254562Scy printf(" = %s (%s/%d)\n", GNAME(rn), 1349254562Scy rn ? addrname(&stp->dst) : "NULL", 1350254562Scy rn ? rn->maskbitcount : 0); 1351254562Scy } 1352254562Scy#else 1353254562Scy printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr)); 1354254562Scy rn = ipf_rx_match(rnh, addr); 1355254562Scy stp = (myst_t *)rn; 1356254562Scy printf(" = %s (%s/%d)\n", GNAME(rn), 1357254562Scy rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0); 1358254562Scy#endif 1359254562Scy} 1360254562Scy 1361254562Scy 1362254562Scyvoid 1363254562Scydelete_addr(rnh, item) 1364254562Scy ipf_rdx_head_t *rnh; 1365254562Scy int item; 1366254562Scy{ 1367254562Scy ipf_rdx_node_t *rn; 1368254562Scy addrfamily_t mask; 1369254562Scy addrfamily_t af; 1370254562Scy myst_t **pstp; 1371254562Scy myst_t *stp; 1372254562Scy 1373254562Scy memset(&af, 0, sizeof(af)); 1374254562Scy memset(&mask, 0, sizeof(mask)); 1375254562Scy setaddr(&af, ttable[item].host); 1376254562Scy mask.adf_family = af.adf_family; 1377254562Scy setmask(&mask, ttable[item].mask); 1378254562Scy 1379254562Scy printf("DELETE(%s)\n", addrname(&af)); 1380254562Scy rn = ipf_rx_delete(rnh, &af, &mask); 1381254562Scy if (rn == NULL) { 1382254562Scy printf("FAIL LOOKUP DELETE\n"); 1383254562Scy checktree(rnh); 1384254562Scy for (stp = myst_top; stp != NULL; stp = stp->next) 1385254562Scy if (stp->printed != -1) 1386254562Scy stp->printed = -2; 1387254562Scy ipf_rx_walktree(rnh, nodeprinter, NULL); 1388254562Scy dumptree(rnh); 1389254562Scy abort(); 1390254562Scy } 1391254562Scy printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn)); 1392254562Scy 1393254562Scy for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next) 1394254562Scy if (stp == (myst_t *)rn) 1395254562Scy break; 1396254562Scy stp->printed = -1; 1397254562Scy stp->nodes[0].parent = &stp->nodes[0]; 1398254562Scy stp->nodes[1].parent = &stp->nodes[1]; 1399254562Scy *pstp = stp->next; 1400254562Scy free(stp); 1401254562Scy nodecount--; 1402254562Scy checktree(rnh); 1403254562Scy} 1404254562Scy 1405254562Scy 1406254562Scyvoid 1407254562Scyadd_addr(rnh, n, item) 1408254562Scy ipf_rdx_head_t *rnh; 1409254562Scy int n, item; 1410254562Scy{ 1411254562Scy ipf_rdx_node_t *rn; 1412254562Scy myst_t *stp; 1413254562Scy 1414254562Scy stp = calloc(1, sizeof(*stp)); 1415254562Scy rn = (ipf_rdx_node_t *)stp; 1416254562Scy setaddr(&stp->dst, ttable[item].host); 1417254562Scy stp->mask.adf_family = stp->dst.adf_family; 1418254562Scy setmask(&stp->mask, ttable[item].mask); 1419254562Scy stp->next = myst_top; 1420254562Scy myst_top = stp; 1421254562Scy (void) sprintf(rn[0].name, "_BORN.0"); 1422254562Scy (void) sprintf(rn[1].name, "_BORN.1"); 1423254562Scy rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes); 1424254562Scy (void) sprintf(rn[0].name, "%d_NODE.0", item); 1425254562Scy (void) sprintf(rn[1].name, "%d_NODE.1", item); 1426254562Scy printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name); 1427254562Scy nodecount++; 1428254562Scy checktree(rnh); 1429254562Scy} 1430254562Scy 1431254562Scy 1432254562Scyvoid 1433254562Scychecktree(ipf_rdx_head_t *head) 1434254562Scy{ 1435254562Scy myst_t *s1; 1436254562Scy ipf_rdx_node_t *rn; 1437254562Scy 1438254562Scy if (nodecount <= 1) 1439254562Scy return; 1440254562Scy 1441254562Scy for (s1 = myst_top; s1 != NULL; s1 = s1->next) { 1442254562Scy int fault = 0; 1443254562Scy if (s1->printed == -1) 1444254562Scy continue; 1445254562Scy rn = &s1->nodes[1]; 1446254562Scy if (rn->right->parent != rn) 1447254562Scy fault |= 1; 1448254562Scy if (rn->left->parent != rn) 1449254562Scy fault |= 2; 1450254562Scy if (rn->parent->left != rn && rn->parent->right != rn) 1451254562Scy fault |= 4; 1452254562Scy if (fault != 0) { 1453254562Scy printf("FAULT %#x %s\n", fault, rn->name); 1454254562Scy dumptree(head); 1455254562Scy ipf_rx_walktree(head, nodeprinter, NULL); 1456254562Scy fflush(stdout); 1457254562Scy fflush(stderr); 1458254562Scy printf("--\n"); 1459254562Scy abort(); 1460254562Scy } 1461254562Scy } 1462254562Scy} 1463254562Scy 1464254562Scy 1465254562Scyint * 1466254562Scyrandomize(int *pnitems) 1467254562Scy{ 1468254562Scy int *order; 1469254562Scy int nitems; 1470254562Scy int choice; 1471254562Scy int j; 1472254562Scy int i; 1473254562Scy 1474254562Scy nitems = sizeof(ttable) / sizeof(ttable[0]); 1475254562Scy *pnitems = nitems; 1476254562Scy order = calloc(nitems, sizeof(*order)); 1477254562Scy srandom(getpid() * time(NULL)); 1478254562Scy memset(order, 0xff, nitems * sizeof(*order)); 1479254562Scy order[21] = 21; 1480254562Scy for (i = 0; i < nitems - 1; i++) { 1481254562Scy do { 1482254562Scy choice = rand() % (nitems - 1); 1483254562Scy for (j = 0; j < nitems; j++) 1484254562Scy if (order[j] == choice) 1485254562Scy break; 1486254562Scy } while (j != nitems); 1487254562Scy order[i] = choice; 1488254562Scy } 1489254562Scy 1490254562Scy return order; 1491254562Scy} 1492254562Scy 1493254562Scy 1494254562Scyvoid 1495254562Scyrandom_add(rnh) 1496254562Scy ipf_rdx_head_t *rnh; 1497254562Scy{ 1498254562Scy int *order; 1499254562Scy int nitems; 1500254562Scy int i; 1501254562Scy 1502254562Scy order = randomize(&nitems); 1503254562Scy 1504254562Scy for (i = 0; i < nitems - 1; i++) { 1505254562Scy add_addr(rnh, i, order[i]); 1506254562Scy checktree(rnh); 1507254562Scy } 1508317242Scy 1509317242Scy free(order); 1510254562Scy} 1511254562Scy 1512254562Scy 1513254562Scyvoid 1514254562Scyrandom_delete(rnh) 1515254562Scy ipf_rdx_head_t *rnh; 1516254562Scy{ 1517254562Scy int *order; 1518254562Scy int nitems; 1519254562Scy int i; 1520254562Scy 1521254562Scy order = randomize(&nitems); 1522254562Scy 1523254562Scy for (i = 0; i < nitems - 1; i++) { 1524254562Scy delete_addr(rnh, i); 1525254562Scy checktree(rnh); 1526254562Scy } 1527317242Scy 1528317242Scy free(order); 1529254562Scy} 1530254562Scy#endif /* RDX_DEBUG */ 1531