sfxhash.c

著名的入侵检测系统snort的最新版本的源码

/****************************************************************************
 *
 * Copyright (C) 2003-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.
 *
 ****************************************************************************/

/*!
 *
 *  \f sfxhash.c
 *
 *  A Customized hash table library for storing and accessing key + data pairs.
 *
 *  This table incorporates a memory manager (memcap.c) to provide a memory cap,  
 *  and an automatic node recovery system for out of memory management. Keys and
 *  Data are copied into the hash table during the add operation. The data may
 *  be allocated and free'd by the user (by setting the datasize to zero ). A 
 *  user callback is provided to allow the user to do cleanup whenever a node
 *  is released, by either the ANR system or the relase() function.
 *
 *  Users can and should delete nodes when they know they are not needed anymore,
 *  but this custom table is designed for the case where nodes are allocated 
 *  permanently, we have to limit memory, and we wish to recycle old nodes.  
 *  Many problems have a natural node ageing paradigm working in our favor, 
 *  so automated node aging makes sense. i.e. thresholding, tcp state.
 *
 *  This hash table maps keys to data.  All keys must be unique.
 *  Uniqueness is enforcedby the code.
 *
 *  Features:
 *
 *    1) Keys must be fixed length (per table) binary byte sequences.
 *         keys are copied during the add function
 *    2) Data must be fixed length (per table) binary byte sequences.
 *         data is copied during the add function - if datasize > 0
 *       Data may be managed by the user as well.
 *    3) Table row sizes can be automatically adjusted to
 *       the nearest prime number size during table initialization/creation.
 *    4) Memory management includes tracking the size of each allocation, 
 *       number of allocations, enforcing a memory cap, and automatic node 
 *       recovery - when  memory is low the oldest untouched node
 *       is unlinked and recycled for use as a new node.
 *
 *  Per Node Memory Usage:
 *  ----------------------
 *     SFXHASH_NODE bytes
 *     KEYSIZE bytes
 *     [DATASIZE bytes] if datasize > 0 during call to sfxhash_new.
 *
 *  The hash node memory (sfxhash_node,key,and data) is allocated with 
 *  one call to s_alloc/memcap_alloc.
 *
 *  Author: Marc Norton
 *
 *  2003-06-03: cmg - added sfxhash_{l,m}ru to return {least,most}
 *              recently used node from the global list
 *
 *              - added _anrcount function
 *              - changed count function to return unsigned to match structure
 *
 *  2003-06-11: cmg added
 *              overhead_bytes + blocks to separate out the
 *              memcap constraints from the hash table itself
 *              find success v fail
 *
 *  2003-06-19: cmg added
 *
 *              ability to set own hash function
 *              ability to set own key cmp function
 *
 *  2003-06-30: rdempster
 *              fixed bug in that would anr from the freelist
 *              
 *  2005-11-15: modified sfxhash_add to check if 'data' is zero before memcpy'ing.
 *              this allows user to pass null for data, and set up the data area
 *              themselves after the call - this is much more flexible.
 *  8/31/2006: man - changed to use prime table lookup.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "sfxhash.h"
#include "sfprimetable.h"
#include "util.h"
#include "debug.h"

/*
 * Private Malloc - abstract the memory system
 */
static INLINE
void * s_alloc( SFXHASH * t, int n )
{
    return sfmemcap_alloc( &t->mc, n );
}
static INLINE
void s_free( SFXHASH * t, void * p )
{
    sfmemcap_free( &t->mc, p );
}

/*
 *   User access to the memory management, do they need it ? WaitAndSee
 */
void * sfxhash_alloc( SFXHASH * t, unsigned nbytes )
{
    return s_alloc( t, nbytes );
}
void   sfxhash_free( SFXHASH * t, void * p )
{
    s_free( t, p );
}

int sfxhash_nearest_powerof2(int nrows) 
{
    int i;

    nrows -= 1;
    for(i=1; i<sizeof(nrows) * 8; i <<= 1)          
        nrows = nrows | (nrows >> i);
    nrows += 1;

    return nrows;
}

int sfxhash_calcrows(int num)
{
    return sfxhash_nearest_powerof2(num);
//  return sf_nearest_prime( nrows );
}
        

/*!
 *
 * Create a new hash table
 *
 * By default, this will "splay" nodes to the top of a free list. 
 *
 * @param nrows    number of rows in hash table
 * @param keysize  key size in bytes, same for all keys
 * @param datasize datasize in bytes, zero indicates user manages data
 * @param maxmem   maximum memory to use in bytes
 * @param anr_flag Automatic Node Recovery boolean flag
 * @param anrfree  users Automatic Node Recovery memory release function
 * @param usrfree  users standard memory release function
 *
 * @return SFXHASH*
 * @retval  0 out of memory
 * @retval !0 Valid SFXHASH pointer  
 *
 */
/*
  Notes:
  if nrows < 0 don't cal the nearest prime.
  datasize must be the same for all entries, unless datasize is zero.
  maxmem of 0 indicates no memory limits.

*/
SFXHASH * sfxhash_new( int nrows, int keysize, int datasize, int maxmem, 
                       int anr_flag, 
                       int (*anrfree)(void * key, void * data),
                       int (*usrfree)(void * key, void * data),
                       int recycle_flag )
{
    int       i;
    SFXHASH * h;

    if( nrows > 0 ) /* make sure we have a prime number */
    {
//        nrows = sf_nearest_prime( nrows );
        /* If nrows is not a power of two, need to find the 
         * next highest power of two */
        nrows = sfxhash_nearest_powerof2(nrows);
    }
    else   /* use the magnitude of nrows as is */
    { 
        nrows = -nrows;
    }

    /* Allocate the table structure from general memory */
    //h = (SFXHASH*) calloc( 1, sizeof(SFXHASH) );
    h = (SFXHASH*)SnortAlloc(sizeof(SFXHASH));
    if( !h ) 
    {
        return 0;
    }

    /* this has a default hashing function */
    h->sfhashfcn = sfhashfcn_new( nrows );
    
    if( !h->sfhashfcn ) 
    {
        free(h);
        return 0;
    }

    sfmemcap_init( &h->mc, maxmem );

    /* Allocate the array of node ptrs */
    h->table = (SFXHASH_NODE**) s_alloc( h, sizeof(SFXHASH_NODE*) * nrows );
    if( !h->table ) 
    {
        free(h->sfhashfcn);
        free(h);
        return 0;
    }

    for( i=0; i<nrows; i++ )
    {
        h->table[i] = 0;
    }

    h->anrfree  = anrfree;
    h->usrfree  = usrfree;
    h->keysize  = keysize;
    h->datasize = datasize;
    h->nrows    = nrows;
    h->max_nodes = 0;
    h->crow     = 0; 
    h->cnode    = 0; 
    h->count    = 0;
    h->ghead    = 0;
    h->gtail    = 0;
    h->anr_count= 0;    
    h->anr_tries= 0;
    h->anr_flag = anr_flag; 
    h->splay    = 1; 
    h->recycle_nodes = recycle_flag;

    h->find_success = 0;
    h->find_fail    = 0;
    
    /* save off how much we've already allocated from our memcap */    
    h->overhead_bytes = h->mc.memused;
    h->overhead_blocks = h->mc.nblocks;

    return h;
}

/*!
 *  Set the maximum nodes used in this hash table.
 *  Specifying 0 is unlimited (or otherwise limited by memcap).
 * 
 * @param h SFXHASH table pointer
 * @param max_nodes maximum nodes to allow.
 *
 */
void sfxhash_set_max_nodes( SFXHASH *h, int max_nodes )
{
    if (h)
    {
        h->max_nodes = max_nodes;
    }
}

/*!
 *  Set Splay mode : Splays nodes to front of list on each access
 * 
 * @param t SFXHASH table pointer
 * @param n boolean flag toggles splaying of hash nodes
 *
 */
void sfxhash_splaymode( SFXHASH * t, int n )
{
    t->splay = n;
}


/*!
 *  Free all nodes in the free list
 *
 *  Removes and frees all of the nodes in the free list
 *  No need to call the user free, since that should've been
 *  done when those nodes were put back in the free list.
 *
 * @param h SFXHASH table pointer
 */
static
void sfxhash_delete_free_list(SFXHASH *t)
{
    SFXHASH_NODE *cur = NULL;
    SFXHASH_NODE *next = NULL;

    if (t == NULL || t->fhead == NULL)
        return;

    cur = t->fhead;

    while (cur != NULL)
    {
        next = cur->gnext;
        s_free(t, (void *)cur);
        cur = next;
    }

    t->fhead = NULL;
    t->ftail = NULL;
}

/*!
 *  Delete the hash Table 
 *
 *  free key's, free node's, and free the users data.
 *
 * @param h SFXHASH table pointer
 *
 */
void sfxhash_delete( SFXHASH * h )
{
    unsigned    i;
    SFXHASH_NODE * node, * onode;

    if( !h ) return;

    if( h->sfhashfcn ) sfhashfcn_free( h->sfhashfcn );
 
    if( h->table )
    {  
        for(i=0;i<h->nrows;i++)
        {
            for( node=h->table[i]; node;  )
            {
                onode = node;
                node  = node->next;
                
                /* Notify user that we are about to free this node function */
                if( h->usrfree )
                    h->usrfree( onode->key, onode->data );
        
                s_free( h,onode );
            }
        }
        s_free( h, h->table );
        h->table = 0;
    }

    sfxhash_delete_free_list( h );

    free( h ); /* free the table from general memory */
}

/*!
 *  Get the # of Nodes in HASH the table
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_count( SFXHASH * t )
{
    return t->count;
}

/*!
 *  Get the # auto recovery 
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_anr_count( SFXHASH * t )
{
    return t->anr_count;
}

/*!
 *  Get the # finds
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_find_total( SFXHASH * t )
{
    return t->find_success + t->find_fail;
}

/*!
 *  Get the # unsucessful finds
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_find_fail( SFXHASH * t )
{
    return t->find_fail;
}

/*!
 *  Get the # sucessful finds
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_find_success( SFXHASH * t )
{
    return t->find_success;
}




/*!
 *  Get the # of overhead bytes
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_overhead_bytes( SFXHASH * t )
{
    return t->overhead_bytes;
}

/*!
 *  Get the # of overhead blocks
 *
 * @param t SFXHASH table pointer
 *
 */
unsigned sfxhash_overhead_blocks( SFXHASH * t )
{
    return t->overhead_blocks;
}

/*
 *  Free List - uses the NODE gnext/gprev fields
 */
static
void sfxhash_save_free_node( SFXHASH *t, SFXHASH_NODE * hnode )
{
    /* Add A Node to the Free Node List */
    if( t->fhead ) /* add the node to head of the the existing list */
    {
        hnode->gprev    = 0;  
        hnode->gnext    = t->fhead;
        t->fhead->gprev = hnode;
        t->fhead        = hnode;
        /* tail is not affected */
    }
    else /* 1st node in this list */
    {
        hnode->gprev = 0;
        hnode->gnext = 0;