sfxhash.c

Linux snort-2.4.4源代码

/*!
 *
 *  \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_malloc/memcap_alloc.
 *
 *  Copyright (C) 2001 Marc A Norton.
 *  Copyright (C) 2003 Sourcefire,Inc.
 *
 *  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.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "sfxhash.h"

/*
 * Private Malloc - abstract the memory system
 */
static 
void * s_malloc( SFXHASH * t, int n )
{
    return sfmemcap_alloc( &t->mc, n );
}
static 
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_malloc( t, nbytes );
}
void   sfxhash_free( SFXHASH * t, void * p )
{
    s_free( t, p );
}

#ifdef XXXX
/*
 *  A classic hash routine using prime numbers 
 *
 *  Constants for the Prime No. based hash routines  
 */
#define PRIME_INIT   9791
#define PRIME_SCALE  31
static unsigned sfxhash_data( unsigned char *d, int n )
{
    int i;
    register unsigned hash = PRIME_INIT;
    for(i=0;i<n;i++)
    {
        hash = hash * PRIME_SCALE + d[i];
    }  
    return hash;
}

#endif /* XXXX */

/*
 *   Primiitive Prime number test, not very fast nor efficient, but should be ok for 
 *   hash table sizes of typical size.  NOT for real-time usage!
 */
static int isPrime(int num )
{
    int i;
    for(i=2;i<num;i++)
    {
        if( (num % i) == 0 ) break;//oops not prime, should have a remainder
    }
    if( i == num ) return 1;
    return 0;
}
/*
 *  Iterate number till we find a prime.
 */
static int calcNextPrime(int num )
{
    while( !isPrime( num ) ) num++;

    return num;
}

/*!
 *
 * 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 = calcNextPrime( nrows );
    }
    else   /* use the magnitude or nrows as is */
    { 
        nrows = -nrows;
    }

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

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

    sfmemcap_init( &h->mc, maxmem );

    /* Allocate the array of node ptrs */
    h->table = (SFXHASH_NODE**) s_malloc( h, sizeof(SFXHASH_NODE*) * nrows );
    if( !h->table ) 
    {
        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->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 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;
}


/*!
 *  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;
    }

    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;
        t->fhead    = hnode;
        t->ftail    = hnode;
    }
}
static
SFXHASH_NODE * sfxhash_get_free_node( SFXHASH *t )
{
    SFXHASH_NODE * node = t->fhead;

    /* Remove A Node from the Free Node List - remove the head node */
    if( t->fhead  ) 
    {
        t->fhead = t->fhead->gnext;
        if( t->fhead ) 
            t->fhead->gprev = 0;

        if( t->ftail  == node ) /* no more nodes - clear the tail */
            t->ftail  =  0;
    }

    return node;
}

static
void sfxhash_glink_node( SFXHASH *t, SFXHASH_NODE * hnode )
{
    /* Add The Node */
    if( t->ghead ) /* add the node to head of the the existing list */
    {
        hnode->gprev    = 0;  
        hnode->gnext    = t->ghead;
        t->ghead->gprev = hnode;
        t->ghead        = hnode;
        /* tail is not affected */
    }
    else /* 1st node in this list */
    {
        hnode->gprev = 0;
        hnode->gnext = 0;
        t->ghead    = hnode;
        t->gtail    = hnode;
    }
}

static
void sfxhash_gunlink_node( SFXHASH *t, SFXHASH_NODE * hnode )
{
    /* Remove the Head Node */
    if( t->ghead == hnode ) /* add the node to head of the the existing list */
    {
        t->ghead = t->ghead->gnext;
        if( t->ghead ) 
            t->ghead->gprev = 0;
    }

    if( hnode->gprev ) hnode->gprev->gnext = hnode->gnext;
    if( hnode->gnext ) hnode->gnext->gprev = hnode->gprev;

    if( t->gtail  == hnode )
        t->gtail  =  hnode->gprev;             
}

void sfxhash_gmovetofront( SFXHASH *t, SFXHASH_NODE * hnode )
{
    if( hnode != t->ghead )
    {
        sfxhash_gunlink_node( t, hnode );
        sfxhash_glink_node( t, hnode );
    }
}

/*
 *
 */
static
void sfxhash_link_node( SFXHASH * t, SFXHASH_NODE * hnode )
{
    /* Add The Node to the Hash Table Row List */
    if( t->table[hnode->rindex] ) /* add the node to the existing list */
    {
        hnode->prev = 0;  // insert node as head node
        hnode->next=t->table[hnode->rindex];
        t->table[hnode->rindex]->prev = hnode;
        t->table[hnode->rindex] = hnode;
    }
    else /* 1st node in this list */
    {
        hnode->prev=0;
        hnode->next=0;
        t->table[hnode->rindex] = hnode;
    }
}

static
void sfxhash_unlink_node( SFXHASH * t, SFXHASH_NODE * hnode )
{
    if( hnode->prev )  // definitely not the 1st node in the list
    {
        hnode->prev->next = hnode->next;
        if( hnode->next ) 
            hnode->next->prev = hnode->prev;
    }
    else if( t->table[hnode->rindex] )  // must be the 1st node in the list
    {
        t->table[hnode->rindex] = t->table[hnode->rindex]->next;
        if( t->table[hnode->rindex] )
            t->table[hnode->rindex]->prev = 0;
    }
}

/*
 *  move a node to the front of the row list at row = 'index'
 */
static void movetofront( SFXHASH *t, SFXHASH_NODE * n )
{
    /* Modify Hash Node Row List */
    if( t->table[n->rindex] != n ) // if not at front of list already...
    {
        /* Unlink the node */
        sfxhash_unlink_node( t, n );
     
        /* Link at front of list */
        sfxhash_link_node( t, n );
    }

    /* Move node in the global hash node list to the front */
    sfxhash_gmovetofront( t, n );
}

/*
 * Allocat a new hash node, uses Auto Node Recovery if needed and enabled.
 * 
 * The oldest node is the one with the longest time since it was last touched, 
 * and does not have any direct indication of how long the node has been around.
 * We don't monitor the actual time since last being touched, instead we use a
 * splayed global list of node pointers. As nodes are accessed they are splayed
 * to the front of the list. The oldest node is just the tail node.
 *
 */
static 
SFXHASH_NODE * sfxhash_newnode( SFXHASH * t )
{
    SFXHASH_NODE * hnode;

    /* Recycle Old Nodes - if any */
    hnode = sfxhash_get_free_node( t );

    /* Allocate memory for a node */
    if( ! hnode )
    {
        hnode = (SFXHASH_NODE*)s_malloc( t, sizeof(SFXHASH_NODE) +
                                         t->keysize + t->datasize );
    }
        
    /*  If we still haven't found hnode, we're at our memory limit.
     *
     *  Uses Automatic Node Recovery, to recycle the oldest node-based on access
     *  (Unlink and reuse the tail node)
     */ 
    if( !hnode && t->anr_flag && t->gtail )
    {
        /* Find the oldes node the users willing to let go. */
        for(hnode = t->gtail; hnode; hnode = hnode->gprev )
        {
            if( t->anrfree ) /* User has provided a permission+release callback function */
            {
                t->anr_tries++;/* Count # ANR requests */
                
                /* Ask the user for permission to release this node, but let them say no! */
                if( t->anrfree( hnode->key, hnode->data ) )
                {
                    /* NO, don't recycle this node, user's not ready to let it go. */                            
                    continue;
                }
                
                /* YES, user said we can recycle this node */
            }

            sfxhash_gunlink_node( t, hnode ); /* unlink from the global list */
            sfxhash_unlink_node( t, hnode ); /* unlink from the row list */
            t->count--;
            t->anr_count++; /* count # of ANR operations */
            break;
        }
    }

    /* either we are returning a node or we're all full and the user
     * won't let us allocate anymore and we return NULL */
    return hnode;
}

/*
 *
 *  Find a Node based on the key, return the node and the index.
 *  The index is valid even if the return value is NULL, in which
 *  case the index is the corect row in which the node should be 
 *  created.
 *
 */
static 
SFXHASH_NODE * sfxhash_find_node_row( SFXHASH * t, void * key, int * rindex )
{
    unsigned       hashkey;
    int            index;
    SFXHASH_NODE  *hnode;

    hashkey = t->sfhashfcn->hash_fcn( t->sfhashfcn,
                                      (unsigned char*)key,
                                      t->keysize );
    
/*     printf("hashkey: %u t->keysize: %d\n", hashkey, t->keysize); */
/*     flowkey_fprint(stdout, key);  */
/*     printf("****\n"); */

    index   = hashkey % t->nrows;

    *rindex = index;
   
    for( hnode=t->table[index]; hnode; hnode=hnode->next )
    {
        if( !t->sfhashfcn->keycmp_fcn(hnode->key,key,t->keysize) )
        {
            if( t->splay > 0 )
                movetofront(t,hnode);

            t->find_success++;            
            return hnode;
        }
    }

    t->find_fail++;            
    return NULL;
}



/*!
 * Add a key + data pair to the hash table
 *
 * 2003-06-06:
 *  - unique_tracker.c assumes that this splays
 *    nodes to the top when they are added.
 *
 *    This is done because of the successful find.
 *
 * @param t SFXHASH table pointer