/**************************************************************************** * * Copyright (C) 2006-2007 Sourcefire, Inc. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License Version 2 as * published by the Free Software Foundation.  You may not use, modify or * distribute this program under any other version of the GNU General * Public License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ****************************************************************************//* * @file    sfrt.h * @author  Adam Keeton <akeeton@sourcefire.com> * @date    Thu July 20 10:16:26 EDT 2006 * * SFRT implements two different routing table lookup methods that have been  * adapted to return a void pointers. Any generic information may be  * associated with a given IP or CIDR block. * * As of this writing, the two methods used are Stefan Nilsson and Gunnar  * Karlsson's LC-trie, and a multibit-trie method similar to Gupta et-al.'s  * DIR-n-m.  Presently, the LC-trie is used for testing purposes as the * current implementation does not allow for fast, dynamic inserts. * * The intended use is to associate large IP blocks with specific information; * such as what may be written into the table by RNA.   * * NOTE: information should only move from less specific to more specific, ie: *   *      First insert:  1.1.0.0/16  ->  some data *      Second insert: 1.1.2.3     ->  some other data * * As opposed to: * *      First insert:  1.1.2.3     ->  some other data *      Second insert: 1.1.0.0/16  ->  some data * * If more general information is to overwrite existing entries, the table  * should be free'ed and rebuilt.  This is due to the difficulty of cleaning  * out stale entries with the current implementation.  At runtime, this won't * be a significant issue since inserts should apply to specific IP addresses * and not entire blocks of IPs. *  * * Implementation: * * The routing tables associate an index into a "data" table with each CIDR.   * Each entry in the data table stores a pointer to actual data.  This  * implementation was chosen so each routing entry only needs one word to  * either index the data array, or point to another table.   *  * Inserts are performed by specifying a CIDR and a pointer to its associated * data.  Since a new routing table entry may overwrite previous entries,  * a flag selects whether the insert favors the most recent or favors the most * specific.  Favoring most specific should be the default behvior.  If  * the user wishes to overwrite routing entries with more general data, the  * table should be flushed, rather than using favor-most-recent. *  * Before modifying the routing or data tables, the insert function performs a * lookup on the CIDR-to-be-insertted.  If no entry or an entry *of differing  * bit length* is found, the data is insertted into the data table, and its * index is used for the new routing table entry.  If an entry is found that  * is as specific as the new CIDR, the index stored points to where the new  * data is written into the data table. *  * If more specific CIDR blocks overwrote the data table, then the more  * general routing table entries that were not overwritten will be referencing * the wrong data.  Alternatively, less specific entries can only overwrite * existing routing table entries if favor-most-recent inserts are used. * * Because there is no quick way to clean the data-table if a user wishes to * use a favor-most-recent insert for more general data, the user should flush * the table with sfrt_free and create one anew.  Alternatively, a small  * memory leak occurs with the data table, as it will be storing pointers that * no routing table entry cares about. * * * The API calls that should be used are:  *  sfrt_new    - create new table *  sfrt_insert - insert entry  *  sfrt_lookup - lookup entry *  sfrt_free   - free table*/#ifndef ROUTE_H#define ROUTE_H#ifdef HAVE_CONFIG_H#include "config.h"#endif#include "decode.h"#include <stdlib.h>#include <sys/types.h>#include "sfrt_trie.h"#include "debug.h"typedef u_int32_t IP;typedef void* GENERIC;   /* To be replaced with a pointer to a policy */typedef struct {    word index;    word length;} tuple_t;#include "sfrt_dir.h"//#define SUPPORT_LCTRIE#ifdef SUPPORT_LCTRIE#include "sfrt_lctrie.h"#endifenum types {#ifdef SUPPORT_LCTRIE   LCT,#endif   DIR_24_8,   DIR_16x2,   DIR_16_8x2,   DIR_16_4x4,   DIR_8x4,   DIR_4x8,   DIR_2x16,   IPv4,   IPv6};enum return_codes {   RT_SUCCESS=0,   RT_INSERT_FAILURE,   RT_POLICY_TABLE_EXCEEDED,   DIR_INSERT_FAILURE,   DIR_LOOKUP_FAILURE,   MEM_ALLOC_FAILURE #ifdef SUPPORT_LCTRIE   ,   LCT_COMPILE_FAILURE,   LCT_INSERT_FAILURE,   LCT_LOOKUP_FAILURE#endif};/* Defined in sfrt.c */extern char *rt_error_messages[];enum {    RT_FAVOR_TIME,   RT_FAVOR_SPECIFIC};/*******************************************************************//* Master table struct.  Abstracts DIR and LC-trie methods         */typedef struct {    GENERIC *data;      /* data table. Each IP points to an entry here */    u_int32_t num_ent;  /* Number of entries in the policy table */    u_int32_t max_size; /* Max size of policies array */    char ip_type;       /* Only IPs of this family will be used */    char table_type;        u_int32_t allocated;    void *rt;            /* Actual "routing" table */    tuple_t (*lookup)(IP ip, GENERIC);     int (*insert)(IP ip, int len, word index, int behavior, GENERIC);     void (*free)(void *);    u_int32_t (*usage)(void *);} table_t;/*******************************************************************//* Abstracted routing table API */table_t * sfrt_new(char type, char ip_type, long data_size, u_int32_t mem_cap);void      sfrt_free(table_t *table);GENERIC sfrt_lookup(void *adr, table_t* table);typedef void (*sfrt_iterator_callback)(void *);void    sfrt_iterate(table_t* table, sfrt_iterator_callback userfunc);void    sfrt_cleanup(table_t* table, sfrt_iterator_callback userfunc);int     sfrt_insert(void *adr, unsigned char len, GENERIC ptr,                         int behavior, table_t *table);u_int32_t     sfrt_usage(table_t *table);u_int32_t     sfrt_num_entries(table_t *table);#endif