/* ** 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@ */ #ifndef _IPTREE_H #define _IPTREE_H #include "silk.h" RCSIDENTVAR(rcsID_IPTREE_H, "$SiLK: iptree.h 7156 2007-05-11 21:59:24Z mthomas $"); /* * iptree.h * * Michael Collins * May 6th, 2003 * * This is a tree structure for ip addresses containing a bitmap of ip * addresses. * */ #include "utils.h" #include "skstream.h" /* * Now we define our basic tree types. */ #define SKIP_BBLOCK_COUNT 65536 #define SKIP_BBLOCK_SIZE 2048 /* * Error return values */ typedef enum _IPTreeErrors { SKIP_OK = 0, SKIP_ERR_ALLOC, SKIP_ERR_BADINPUT, SKIP_ERR_FILEIO, SKIP_ERR_FILETYPE, SKIP_ERR_NONEMPTY, SKIP_ERR_OPEN, } skIPTreeErrors_t; /* * Formats for textual output. See skIPTreePrintAddr() below. */ typedef enum _IPTreeFormats { SKIP_IPF_DOT = 0, /* Dotted quad: 10.0.0.1 */ SKIP_IPF_DEC = 1, /* Base-10 integer: 167772161 */ SKIP_IPF_HEX = 2, /* Base-16 integer: 0a000000 */ SKIP_IPF_ZERO = 4, /* Zero-padded dotted-quad: 010.000.000.001 */ /* Next value can be OR'ed with other values */ SKIP_IPF_CIDR = 16 } skIPTreeFormats_t; /* * IPSet * * An IPSet (aka IP-Tree) consists of a 64k pointers, each of which * is either NULL or a pointer to a node; a node contains 64k bits * for marking addresses. Dividing 64k by 32 means there are 2k * addressBlocks, each of which represents a /27. */ typedef struct _skIPNode_t skIPNode_t; /* THE TREE */ typedef struct skIPTree_t { uint32_t totalAddrs; skIPNode_t *nodes[SKIP_BBLOCK_COUNT]; } skIPTree_t; /* A NODE */ struct _skIPNode_t { uint16_t parentAddr; uint32_t addressBlock[SKIP_BBLOCK_SIZE]; }; #define skIPTreeNodeHasMark(lower16, node) \ ((node)->addressBlock[(lower16) >> 5] & (1 << ((lower16) & 0x1F))) /* * INTERNAL. Check for bit 'lower16' in 'node'. The value in * 'lower16' should be the 16 least significant bits of an address; * 'node' is the skIPNode_t for the 16 most significant bits of the * address. */ #define skIPTreeNodeMarkSpot(addr, node) \ ((node)->addressBlock[(((addr) & 0xFFFF)>>5)] |= (1 << ((addr)&0x1F))) /* * INTERNAL. Set bit 'addr' in 'node'. 'addr' can be the complete * IP address; 'node' is the skIPNode_t for the 16 most significant * bits of the address. */ #define skIPTreeCheckAddress(addr, ipset) \ ((ipset)->nodes[((addr) >> 16)] \ && skIPTreeNodeHasMark(((addr) & 0xFFFF),(ipset)->nodes[((addr) >> 16)])) /* * Return TRUE if 'ipAddr' is set on tree 'ipset'; FALSE otherwise */ /* * On disk format: the header is simply the usual SiLK generic * header. */ typedef struct skIPTreeHeader_t{ genericHeader gHdr; } skIPTreeHeader_t; /* * An iterator structure for looping over the elements in an IPset. */ typedef struct _IPTreeIterator { const skIPTree_t *tree; uint32_t top_16; uint16_t mid_11; uint16_t bot_5; } skIPTreeIterator_t; /* * The skIPTreeCIDRBlockIterator_t iterates over CIDR blocks and * fills an skIPTreeCIDRBlock_t. */ typedef struct _IPTreeCIDRBlockIterator { /* the underlying iterator over the IPs */ skIPTreeIterator_t tree_iter; /* the start of the current list of continuous addresses. when * this is > high, all addresses have been seen */ uint32_t low; /* the end of the current list of continuous addresses */ uint32_t high; /* the start of the next list of continuous addresses */ uint32_t newlist; } skIPTreeCIDRBlockIterator_t; typedef struct _IPTreeCIDRBlock { uint32_t addr; uint32_t mask; } skIPTreeCIDRBlock_t; /* * IP Address printing Macro */ #define skIPTreePrintAddrInt(outF, addr) \ (fprintf((outF), "%10lu\n", (unsigned long)(addr))) #define skIPTreePrintAddrHex(outF, addr) \ (fprintf((outF), "%08x\n", (addr))) #define skIPTreePrintAddrDot(outF, addr) \ (fprintf((outF), "%s\n", num2dot(addr))) #define skIPTreePrintAddrZero(outF, addr) \ (fprintf((outF), "%s\n", num2dot0(addr))) #define skIPTreePrintAddr(outF, addr, mode) \ switch (mode) { \ case SKIP_IPF_DEC: \ skIPTreePrintAddrInt((outF), (addr)); \ break; \ case SKIP_IPF_HEX: \ skIPTreePrintAddrHex((outF), (addr)); \ break; \ case SKIP_IPF_ZERO: \ skIPTreePrintAddrZero((outF), (addr)); \ break; \ case SKIP_IPF_DOT: \ default: \ skIPTreePrintAddrDot((outF), (addr)); \ break; \ } /* FUNCTION PROTOTYPES */ int skIPTreeAddAddress(uint32_t addr, skIPTree_t *ipset); /* * Add the IP Address 'addr' to the binary IPSet 'ipset'. Returns * SKIP_OK for success, or SKIP_ERR_ALLOC if there is not enough * memory to allocate space for the new IP address. */ uint64_t skIPTreeCountIPs(const skIPTree_t *ipset); /* * Returns a count of the number of IP addresses marked in the * 'ipset'. */ int skIPTreeCreate(skIPTree_t **ipset); /* * Allocation and creation function; initializes a new ipset at the * space specified by '*ipset' and sets the contents to empty. * * Returns SKIP_OK if everything went well, else SKIP_ERR_ALLOC * on a malloc failure, or SKIP_ERR_BADINPUT if ipset was NULL. * * skIPTreeDelete() is the corresponding free function. */ void skIPTreeDelete(skIPTree_t **ipset); /* * Frees the space associated with *ipset. On completion * *ipset == NULL */ void skIPTreeIntersect( skIPTree_t *result_ipset, const skIPTree_t *ipset); /* * Perform an intersection of 'result_ipset' and 'ipset', with the * result in the 'result_ipset'; i.e., turn off all addresses in * 'result_ipset' that are off in 'ipset'. */ int skIPTreeLoad(const char *filename, skIPTree_t **ipset); /* * Creates(allocates) a new IPset at the location pointed at by * 'ipset' and fills it with the data that the function reads from * the file 'filename'. * * This function is similar to skIPTreeRead(), except that this * function will create the skstream_t from the specified filename. * * In addition to the possible return values listed for * skIPTreeRead(), this function may return: * SKIP_ERR_OPEN - error in opening the file */ void skIPTreePrint(skstream_t *stream, const skIPTree_t *ipset, int ipFormat); /* * Prints, to the stream 'outFile', a textual representation of the * IPset given by 'ipset'. The parameter 'ipFormat' decribes how * to print the ipset, it can be one of the values described in the * "enum skIPTreeFormats". If 'ipFormat' has been OR'ed with the * SKIP_IPF_CIDR value, the output will be in CIDR notation. */ int skIPTreeRead(skstream_t *stream, skIPTree_t **ipset); /* * Allocates a new IPset at the location pointed at by 'ipset' and * fills it with the data that the function reads from the stream * 'stream'. 'stream' should be bound to a file and open. * * Returns one of the following: * SKIP_OK on success * SKIP_ERR_BADINPUT - one of the input values is NULL * SKIP_ERR_ALLOC - failure to allocate memory. * SKIP_ERR_NONEMPTY - the '*ipset' is not empty * SKIP_ERR_FILETYPE - the file is not of the correct type * SKIP_ERR_FILEIO - error during a read call * * On failure, 'ipset' is set back to null and deleted. */ int skIPTreeRemoveAll(skIPTree_t *ipset); /* * Remove all IPs from an IPset. */ int skIPTreeSave(const char *filename, const skIPTree_t *ipset); /* * Writes the IPset at 'ipset' to the disk file 'filename'; the * disk format is specified in iptree.api. * * This function is similar to skIPTreeWrite(), except this * function writes directly to a file using the default compression * method. * * In addition to the possible return values listed for * skIPTreeWrite(), this function may return: * SKIP_ERR_OPEN - error in opening the file */ const char *skIPTreeStrError(int err_code); /* * Return a text string describing 'err_code'. */ void skIPTreeSubtract( skIPTree_t *result_ipset, const skIPTree_t *ipset); /* * Subtract 'ipset' from 'result_ipset' with the result in the * 'result_ipset'; i.e., if an address is off in 'ipset', do not * modify the value in 'result_ipset', otherwise, turn off that * address in 'result_ipset'. */ int skIPTreeUnion( skIPTree_t *result_ipset, const skIPTree_t *ipset); /* * Perform the union of 'result_ipset' and 'ipset', with the result * in 'result_ipset'; i.e., merge 'ipset' into 'result_ipset'. * Returns 0 on success, or 1 on memory allocation error. */ int skIPTreeWrite(skstream_t *stream, const skIPTree_t *ipset); /* * Write the IPset at 'ipset' the output stream 'stream'. 'stream' * should be bound to a file and open. The caller may set the * compression method of the stream before calling this function. * If not set, the default compression method is used. * * Returns one of the following values: * SKIP_OK on success. * SKIP_ERR_OPEN if the file already exists. * SKIP_ERR_FILEIO if there's an error writing the data to disk. * SKIP_ERR_ALLOC on a memory allocatin problem for the ipset. */ /* * Iteration over the members of an IPset */ int skIPTreeIteratorBind( skIPTreeIterator_t *iter, const skIPTree_t *ipset); /* * Binds the IPset iterator 'iter' to iterate over all the entries * in the IPSet 'ipset'. Returns 0 on success, non-zero otherwise. */ int skIPTreeIteratorCreate( skIPTreeIterator_t **out_iter, const skIPTree_t *ipset); /* * Creates a new iterator at the address pointed to by 'out_iter' * and binds it to iterate over all the entries in the IPSet * 'ipset'. Returns 0 on success, non-zero otherwise. */ void skIPTreeIteratorDestroy(skIPTreeIterator_t **out_iter); /* * Destroys the iterator pointed to by 'out_iter'. */ skIteratorStatus_t skIPTreeIteratorNext( uint32_t *out_addr, skIPTreeIterator_t *iter); /* * If there are more entries in the IPSet, this function puts the * next IP Address into the location referenced by 'out_addr' and * returns SK_ITERATOR_OK. Otherwise, 'out_addr' is not touched * and SK_ITERATOR_NO_MORE_ENTRIES is returned. */ void skIPTreeIteratorReset(skIPTreeIterator_t *iter); /* * Resets the iterator 'iter' to begin looping through the entries * in the IPSet again. */ /* * Iteration over the CIDR Blocks of an IPset */ int skIPTreeCIDRBlockIteratorBind( skIPTreeCIDRBlockIterator_t *iter, const skIPTree_t *ipset); /* * Binds the IPset CIDR Block iterator 'iter' to iterate over all * the CIDR blocks in the IPSet 'ipset'. Returns 0 on success, * non-zero otherwise. */ int skIPTreeCIDRBlockIteratorCreate( skIPTreeCIDRBlockIterator_t **out_iter, const skIPTree_t *ipset); /* * Creates a new CIDR Block iterator at the address pointed to by * 'out_iter' and binds it to iterate over all the CIDR Blocks in * the IPSet 'ipset'. Returns 0 on success, non-zero otherwise. */ void skIPTreeCIDRBlockIteratorDestroy(skIPTreeCIDRBlockIterator_t **out_iter); /* * Destroys the iterator pointed to by 'out_iter'. */ skIteratorStatus_t skIPTreeCIDRBlockIteratorNext( skIPTreeCIDRBlock_t *out_cidr, skIPTreeCIDRBlockIterator_t *iter); /* * If there are more CIDR Blocks in the IPSet, this function fills * next CIDR Block pointer 'out_cidr' with that CIDR Block and * returns SK_ITERATOR_OK. Otherwise, 'out_cidr' is not touched * and SK_ITERATOR_NO_MORE_ENTRIES is returned. */ void skIPTreeCIDRBlockIteratorReset(skIPTreeCIDRBlockIterator_t *iter); /* * Resets the iterator 'iter' to begin looping through the entries * in the IPSet again. */ #endif /* _IPTREE_H */ /* ** Local Variables: ** mode:c ** indent-tabs-mode:nil ** c-basic-offset:4 ** End: */