/* ** Copyright (C) 2001-2007 by Carnegie Mellon University. ** ** @OPENSOURCE_HEADER_START@ ** ** Use of the SILK system and related source code is subject to the terms ** of the following licenses: ** ** GNU Public License (GPL) Rights pursuant to Version 2, June 1991 ** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013 ** ** NO WARRANTY ** ** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER ** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY ** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN ** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY ** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT ** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE, ** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE ** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT, ** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY ** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF ** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES. ** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF ** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON ** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE ** DELIVERABLES UNDER THIS LICENSE. ** ** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie ** Mellon University, its trustees, officers, employees, and agents from ** all claims or demands made against them (and any related losses, ** expenses, or attorney's fees) arising out of, or relating to Licensee's ** and/or its sub licensees' negligent use or willful misuse of or ** negligent conduct or willful misconduct regarding the Software, ** facilities, or other rights or assistance granted by Carnegie Mellon ** University under this License, including, but not limited to, any ** claims of product liability, personal injury, death, damage to ** property, or violation of any laws or regulations. ** ** Carnegie Mellon University Software Engineering Institute authored ** documents are sponsored by the U.S. Department of Defense under ** Contract F19628-00-C-0003. Carnegie Mellon University retains ** copyrights in all material produced under this contract. The U.S. ** Government retains a non-exclusive, royalty-free license to publish or ** reproduce these documents, or allow others to do so, for U.S. ** Government purposes only pursuant to the copyright license under the ** contract clause at 252.227.7013. ** ** @OPENSOURCE_HEADER_END@ */ /* * iptree.c * * This is a data structure for providing marked sets of ip addresses * in a tree format. * * This revision of the iptree module now moves it off into a cleaner * separate space and has replaced the read and write statements with * atomic operations. */ #include "silk.h" RCSIDENT("$SiLK: iptree.c 7356 2007-05-31 18:37:21Z mthomas $"); #include "iptree.h" /* DEFINES AND TYPEDEFS */ /* Version to write into the file's header */ #define IPSET_FILE_VERSION 2 /* macro to print an IP */ #define PRINT_IP(s, ip, fmt) \ switch ((fmt) & ~SKIP_IPF_CIDR) { \ case SKIP_IPF_HEX: \ skStreamPrint((s), "0x%08lx", (unsigned long)(ip)); \ break; \ case SKIP_IPF_DEC: \ skStreamPrint((s), "%lu", (unsigned long)(ip)); \ break; \ case SKIP_IPF_ZERO: \ skStreamPrint((s), "%s", num2dot0(ip)); \ break; \ case SKIP_IPF_DOT: \ default: \ skStreamPrint((s), "%s", num2dot(ip)); \ break; \ } /* LOCAL FUNCTIONS */ /* Add addr to ipset */ int skIPTreeAddAddress(uint32_t addr, skIPTree_t *ipset) { assert(ipset); if (NULL == ipset->nodes[addr>>16]) { ipset->nodes[addr>>16] = calloc(1, sizeof(skIPNode_t)); if (NULL == ipset->nodes[addr>>16]) { return SKIP_ERR_ALLOC; } ipset->nodes[addr>>16]->parentAddr = (uint16_t)(addr>>16); } skIPTreeNodeMarkSpot(addr,ipset->nodes[addr>>16]); return SKIP_OK; } /* Return a count of the number of IPs in tree. */ uint64_t skIPTreeCountIPs(const skIPTree_t *ipset) { int i, j, k; uint64_t count = 0; for (i = 0; i < SKIP_BBLOCK_COUNT; i++) { if (ipset->nodes[i] != NULL) { /* Break the abstraction to speed up the counting */ for (j = 0; j < SKIP_BBLOCK_SIZE; ++j) { if (ipset->nodes[i]->addressBlock[j]) { for (k = 0; k < 32; ++k) { if (ipset->nodes[i]->addressBlock[j] & (1 << k)) { ++count; } } } } } } return count; } /* Allocate an IPset and set contents to empty */ int skIPTreeCreate(skIPTree_t **ipset) { if (ipset == NULL) { return SKIP_ERR_BADINPUT; } *ipset = calloc(1, sizeof(skIPTree_t)); if (*ipset == NULL) { return SKIP_ERR_ALLOC; } return SKIP_OK; } /* Frees space associated with *ipset. */ void skIPTreeDelete(skIPTree_t **ipset) { int i; if (ipset == NULL || *ipset == NULL) { return; } for (i = 0; i < SKIP_BBLOCK_COUNT; i++) { if ((*ipset)->nodes[i] != NULL) { free((*ipset)->nodes[i]); (*ipset)->nodes[i] = NULL; } } free(*ipset); *ipset = NULL; } /* Turn off bits of 'result_ipset' that are off in 'ipset'. */ void skIPTreeIntersect( skIPTree_t *result_ipset, const skIPTree_t *ipset) { int i, j; for (i = 0; i < SKIP_BBLOCK_COUNT; ++i) { if (result_ipset->nodes[i] != NULL) { if (ipset->nodes[i] == NULL) { /* This /16 is off in 'ipset', turn off in 'result_ipset' */ free(result_ipset->nodes[i]); result_ipset->nodes[i] = NULL; } else { /* Need to intersect the bits in the /16 */ for (j = 0; j < SKIP_BBLOCK_SIZE; ++j) { result_ipset->nodes[i]->addressBlock[j] &= ipset->nodes[i]->addressBlock[j]; } } } /* ELSE this /16 is off in the 'result_ipset'. Leave it alone. */ } } /* Read IPset from filename---a wrapper around skIPTreeRead(). */ int skIPTreeLoad(const char *filename, skIPTree_t **ipset) { skstream_t *stream = NULL; int rv; if (filename == NULL || ipset == NULL) { return SKIP_ERR_BADINPUT; } if ((rv = skStreamCreate(&stream, SK_IO_READ, SK_CONTENT_SILK)) || (rv = skStreamBind(stream, filename)) || (rv = skStreamOpen(stream))) { skStreamPrintLastErr(stream, rv, &skAppPrintErr); rv = SKIP_ERR_OPEN; goto END; } rv = skIPTreeRead(stream, ipset); if (rv) { goto END; } END: skStreamDestroy(&stream); return rv; } /* Print a textual prepresenation of the IP Tree. */ void skIPTreePrint(skstream_t *stream, const skIPTree_t *ipset, int ipFormat) { if (ipFormat & SKIP_IPF_CIDR) { skIPTreeCIDRBlockIterator_t cidr_iter; skIPTreeCIDRBlock_t cidr; /* memset to eliminate gcc warning */ memset(&cidr_iter, 0, sizeof(skIPTreeCIDRBlockIterator_t)); skIPTreeCIDRBlockIteratorBind(&cidr_iter, ipset); while (skIPTreeCIDRBlockIteratorNext(&cidr, &cidr_iter) == SK_ITERATOR_OK) { PRINT_IP(stream, cidr.addr, ipFormat); if (cidr.mask == 32) { skStreamPrint(stream, "\n"); } else { skStreamPrint(stream, "/%d\n", cidr.mask); } } } else { skIPTreeIterator_t iter; uint32_t addr; /* memset to eliminate gcc warning */ memset(&iter, 0, sizeof(skIPTreeIterator_t)); skIPTreeIteratorBind(&iter, ipset); while (skIPTreeIteratorNext(&addr, &iter) == SK_ITERATOR_OK) { PRINT_IP(stream, addr, ipFormat); skStreamPrint(stream, "\n"); } } } /* Allocate 'ipset' and read it from the data stream 'stream'. */ int skIPTreeRead(skstream_t *stream, skIPTree_t **ipset) { skIPTreeHeader_t th; fileVersion_t vers; int swapFlag; uint32_t tBuffer[9]; uint32_t blockStart, rootAddr; ssize_t b; int i; int rv; if (stream == NULL || ipset == NULL) { return SKIP_ERR_BADINPUT; } if ((*ipset) != NULL) { return SKIP_ERR_NONEMPTY; } rv = skStreamReadSilkHeader(stream, &th, sizeof(th)); if (rv) { skStreamPrintLastErr(stream, rv, &skAppPrintErr); rv = SKIP_ERR_FILEIO; goto END; } if (FT_IPSET != skStreamGetSilkFormat(stream)) { rv = SKIP_ERR_FILETYPE; goto END; } /* * There has only been one IPset file format, but it may have * version 0, 1, or 2. Files of v2 support compression on write; * for compatibility with SiLK-0.10.0 through 0.10.4, compression * on read is supported regardless of version. * * When first released, the version of the IPset was never * initialized. To work with those files, the version check was * never implemented. */ vers = skStreamGetSilkVersion(stream); if (vers > IPSET_FILE_VERSION) { skAppPrintErr("IPset file version %d not supported", vers); return SKIP_ERR_FILETYPE; } swapFlag = !skStreamIsNativeByteOrder(stream); rv = skIPTreeCreate(ipset); if (rv != SKIP_OK) { goto END; } /* * IPs are stored on disk in blocks of nine 32-bit words which * represent a /24. The first uint32_t is the base IP of the /24 * (a.b.c.0); the remaining eight uint32_t's have a bit for each * address in the /24. */ while ((b = skStreamRead(stream, tBuffer, sizeof(tBuffer))) == sizeof(tBuffer)) { if (swapFlag) { for (i = 0; i < 9; ++i) { tBuffer[i] = BSWAP32(tBuffer[i]); } } /* Put the first two octets into rootAddr, and allocate the * space for the /16 if we need to */ rootAddr = (tBuffer[0] & 0xFFFF0000) >> 16; if ((*ipset)->nodes[rootAddr] == NULL) { (*ipset)->nodes[rootAddr] = calloc(1, sizeof(skIPNode_t)); if ((*ipset)->nodes[rootAddr] == NULL) { rv = SKIP_ERR_ALLOC; goto END; } (*ipset)->nodes[rootAddr]->parentAddr = rootAddr; } /* Locate where this /24 occurs inside the larger /16, then * copy it into place. */ blockStart = ((tBuffer[0] >> 8) & 0xFF) * 8; memcpy(((*ipset)->nodes[rootAddr]->addressBlock + blockStart), tBuffer + 1, 8 * sizeof(uint32_t)); } if (b == -1) { /* read error */ rv = SKIP_ERR_FILEIO; goto END; } rv = SKIP_OK; END: if (rv != SKIP_OK) { /* Do cleanup (Delete tree) and return */ if ((*ipset) != NULL) { skIPTreeDelete(ipset); } } return rv; } /* Remove all addresses from an IPset */ int skIPTreeRemoveAll(skIPTree_t *ipset) { int i; if (ipset == NULL) { return SKIP_ERR_BADINPUT; } /* delete all the nodes */ for (i = 0; i < SKIP_BBLOCK_COUNT; i++) { if (ipset->nodes[i] != NULL) { free(ipset->nodes[i]); } } memset(ipset, 0, sizeof(skIPTree_t)); return SKIP_OK; } /* Write 'ipset' to 'filename'--a wrapper around skIPTreeWrite(). */ int skIPTreeSave(const char *filename, const skIPTree_t *ipset) { skstream_t *stream = NULL; int rv; if (filename == NULL || ipset == NULL) { return SKIP_ERR_BADINPUT; } if ((rv = skStreamCreate(&stream, SK_IO_WRITE, SK_CONTENT_SILK)) || (rv = skStreamBind(stream, filename)) || (rv = skStreamOpen(stream))) { skStreamPrintLastErr(stream, rv, &skAppPrintErr); rv = SKIP_ERR_OPEN; goto END; } rv = skIPTreeWrite(stream, ipset); END: skStreamDestroy(&stream); return rv; } /* Convert 'error_code' to a string. */ const char *skIPTreeStrError(int error_code) { switch ((skIPTreeErrors_t)error_code) { case SKIP_OK: return "Success"; case SKIP_ERR_ALLOC: return "Unable to allocate memory"; case SKIP_ERR_BADINPUT: return "Empty input value"; case SKIP_ERR_FILEIO: return "Error in read/write"; case SKIP_ERR_FILETYPE: return "Input is not an IPset"; case SKIP_ERR_NONEMPTY: return "Input IPset is not empty"; case SKIP_ERR_OPEN: return "Error opening file"; } return "Unrecognized error code"; } /* Subtract 'ipset' from 'result_ipset' */ void skIPTreeSubtract( skIPTree_t *result_ipset, const skIPTree_t *ipset) { int i, j; for (i = 0; i < SKIP_BBLOCK_COUNT; ++i) { if ((result_ipset->nodes[i] != NULL) && (ipset->nodes[i] != NULL)) { /* Need to intersect with the complement in the /16 */ for (j = 0; j < SKIP_BBLOCK_SIZE; ++j) { result_ipset->nodes[i]->addressBlock[j] &= ~(ipset->nodes[i]->addressBlock[j]); } } /* ELSE This /16 is off in at least one ipset. Leave it alone. */ } } /* Merge 'ipset' into 'result_ipset' */ int skIPTreeUnion( skIPTree_t *result_ipset, const skIPTree_t *ipset) { int i, j; for (i = 0; i < SKIP_BBLOCK_COUNT; ++i) { if (NULL != ipset->nodes[i]) { if (NULL != result_ipset->nodes[i]) { /* need to merge */ for (j = 0; j < SKIP_BBLOCK_SIZE; ++j) { result_ipset->nodes[i]->addressBlock[j] |= ipset->nodes[i]->addressBlock[j]; } } else { /* copy block from ipset to result_ipset */ result_ipset->nodes[i] = malloc(sizeof(skIPNode_t)); if (result_ipset->nodes[i] == NULL) { return SKIP_ERR_ALLOC; } memcpy(result_ipset->nodes[i], ipset->nodes[i], sizeof(skIPNode_t)); } } } return SKIP_OK; } /* Write 'ipset' to 'stream'. */ int skIPTreeWrite(skstream_t *stream, const skIPTree_t *ipset) { uint32_t i; uint32_t j; uint32_t jOffset; uint32_t class_c; skIPTreeHeader_t treeHdr; skIPNode_t *workNode; int rv; if (stream == NULL || ipset == NULL) { return SKIP_ERR_BADINPUT; } /* * Prep and write the IPTree's header information. */ if ((rv = skStreamSetSilkFormat(stream, FT_IPSET)) || (rv = skStreamSetSilkVersion(stream, IPSET_FILE_VERSION)) || (rv = skStreamWriteSilkHeader(stream, &treeHdr, sizeof(treeHdr)))) { skStreamPrintLastErr(stream, rv, &skAppPrintErr); rv = SKIP_ERR_FILETYPE; goto END; } /* * IPs are stored on disk in blocks of nine 32-bit words which * represent a /24. The first uint32_t is the base IP of the /24 * (a.b.c.0); the remaining eight uint32_t's have a bit for each * address in the /24. */ for (i = 0; i < SKIP_BBLOCK_COUNT; i++) { /* workNode represents a /16 */ workNode = ipset->nodes[i]; if (workNode == NULL) { continue; } /* * There is data in this /16, now walk over the addressBlocks, * which are /27s, and for any which have IP bits set, write * the entire /24 to disk. */ j = 0; while (j < SKIP_BBLOCK_SIZE) { if (workNode->addressBlock[j] == 0) { /* nothing in this /27 */ j = j + 1; continue; } /* there is data in this /27; get the /24 that it is part * of, and write that base address. */ class_c = ((i << 16) | (j << 5)) & 0xFFFFFF00; if (skStreamWrite(stream, &class_c, sizeof(uint32_t)) == -1) { rv = SKIP_ERR_FILEIO; goto END; } /* compute the first /27 that has data for the /24, then * write the complete /24: 8 uint32_t's */ jOffset = (j & (0xff << 3)); if (skStreamWrite(stream, (workNode->addressBlock+jOffset), 8 * sizeof(uint32_t)) == -1) { rv = SKIP_ERR_FILEIO; goto END; } /* move the start of the next /24 */ j = ((j & (0xff << 3)) + 8); } } rv = skStreamFlush(stream); if (rv) { skStreamPrintLastErr(stream, rv, &skAppPrintErr); rv = SKIP_ERR_FILEIO; goto END; } rv = SKIP_OK; END: return rv; } /* ITERATOR CODE */ /* Bind iterator to ipset */ int skIPTreeIteratorBind( skIPTreeIterator_t *iter, const skIPTree_t *ipset) { if (iter == NULL || ipset == NULL) { return SKIP_ERR_BADINPUT; } iter->tree = ipset; skIPTreeIteratorReset(iter); return SKIP_OK; } /* Create iterator */ int skIPTreeIteratorCreate( skIPTreeIterator_t **out_iter, const skIPTree_t *ipset) { assert(out_iter); *out_iter = malloc(sizeof(skIPTreeIterator_t)); if (*out_iter == NULL) { return SKIP_ERR_ALLOC; } if (skIPTreeIteratorBind(*out_iter, ipset)) { skIPTreeIteratorDestroy(out_iter); return SKIP_ERR_BADINPUT; } return SKIP_OK; } /* Destroy iterator */ void skIPTreeIteratorDestroy(skIPTreeIterator_t **out_iter) { if (*out_iter) { (*out_iter)->tree = NULL; free(*out_iter); *out_iter = NULL; } } #define FIND_NEXT_ITER_TOP(iter) \ for ( ; (iter)->top_16 < SKIP_BBLOCK_COUNT; ++(iter)->top_16) { \ if ((iter)->tree->nodes[(iter)->top_16] != NULL) { \ /* found a /16 with data */ \ break; \ } \ } /* Get next entry in tree */ skIteratorStatus_t skIPTreeIteratorNext( uint32_t *out_addr, skIPTreeIterator_t *iter) { assert(out_addr); while (iter->top_16 < SKIP_BBLOCK_COUNT) { for ( ; iter->mid_11 < SKIP_BBLOCK_SIZE ; ++iter->mid_11) { if ((iter->tree->nodes[iter->top_16]->addressBlock[iter->mid_11]) == 0) { continue; } for ( ; iter->bot_5 < 32; ++iter->bot_5) { if (skIPTreeNodeHasMark(((iter->mid_11 << 5) + iter->bot_5), (iter->tree->nodes[iter->top_16]))) { /* Generate the IP address */ *out_addr = (((iter->top_16) << 16) | (iter->mid_11 << 5) | iter->bot_5); /* Prepare to search from next IP address */ ++iter->bot_5; return SK_ITERATOR_OK; } } /* reset bottom counter */ iter->bot_5 = 0; } /* reset middle counter; move top counter to next valid block */ iter->mid_11 = 0; ++iter->top_16; FIND_NEXT_ITER_TOP(iter); } return SK_ITERATOR_NO_MORE_ENTRIES; } /* Reset iterator */ void skIPTreeIteratorReset(skIPTreeIterator_t *iter) { /* Set everything to zero, then find the first IP address */ iter->top_16 = iter->mid_11 = iter->bot_5 = 0; FIND_NEXT_ITER_TOP(iter); } /* Bind a CIDR iterator to an IPset */ int skIPTreeCIDRBlockIteratorBind( skIPTreeCIDRBlockIterator_t *iter, const skIPTree_t *ipset) { if (skIPTreeIteratorBind(&iter->tree_iter, ipset)) { return SKIP_ERR_BADINPUT; } skIPTreeCIDRBlockIteratorReset(iter); return SKIP_OK; } /* Create CIDR iterator */ int skIPTreeCIDRBlockIteratorCreate( skIPTreeCIDRBlockIterator_t **out_iter, const skIPTree_t *ipset) { assert(out_iter); *out_iter = malloc(sizeof(skIPTreeCIDRBlockIterator_t)); if (*out_iter == NULL) { return SKIP_ERR_ALLOC; } if (skIPTreeCIDRBlockIteratorBind(*out_iter, ipset)) { skIPTreeCIDRBlockIteratorDestroy(out_iter); return SKIP_ERR_BADINPUT; } return SKIP_OK; } /* Destroy CIDR iterator */ void skIPTreeCIDRBlockIteratorDestroy(skIPTreeCIDRBlockIterator_t **out_iter) { if (*out_iter) { free(*out_iter); *out_iter = NULL; } } skIteratorStatus_t skIPTreeCIDRBlockIteratorNext( skIPTreeCIDRBlock_t *out_cidr, skIPTreeCIDRBlockIterator_t *iter) { assert(out_cidr); /* check for the stoping condition */ if (iter->low > iter->high) { return SK_ITERATOR_NO_MORE_ENTRIES; } /* If 'iter' is at the start of a new block, add IPs to the * current continuous list until we get a non-contiguous IP or * there is no more data */ while (iter->high == iter->newlist) { if (skIPTreeIteratorNext(&iter->newlist, &iter->tree_iter) != SK_ITERATOR_OK) { /* no more data */ iter->newlist = 0; break; } if (iter->newlist == (iter->high + 1)) { /* Current range is contiguous, expand it. */ iter->high = iter->newlist; } } out_cidr->addr = iter->low; out_cidr->mask = skComputeCIDR(out_cidr->addr, iter->high, &iter->low); if (iter->low == 0) { /* finished with this contiguous list of IPs, move to start of * next list of IPS */ if (iter->newlist == 0) { /* no more IPs */ iter->high = 0; iter->low = 1; } else { iter->low = iter->high = iter->newlist; } } return SK_ITERATOR_OK; } /* Reset CIDR iterator */ void skIPTreeCIDRBlockIteratorReset(skIPTreeCIDRBlockIterator_t *iter) { assert(iter); /* reset the IP iterator */ skIPTreeIteratorReset(&iter->tree_iter); /* find the first IP address */ if (skIPTreeIteratorNext(&iter->newlist, &iter->tree_iter) == SK_ITERATOR_OK) { iter->low = iter->high = iter->newlist; } else { /* No IPs. Set to our stopping condition */ iter->high = iter->newlist = 0; iter->low = 1; } } /* ** Local Variables: ** mode:c ** indent-tabs-mode:nil ** c-basic-offset:4 ** End: */