Logo Search packages:      
Sourcecode: unbound version File versions  Download package

lruhash.h

Go to the documentation of this file.
/*
 * util/storage/lruhash.h - hashtable, hash function, LRU keeping.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file contains a hashtable with LRU keeping of entries.
 *
 * The hash table keeps a maximum memory size. Old entries are removed
 * to make space for new entries.
 *
 * The locking strategy is as follows:
 *    o since (almost) every read also implies a LRU update, the
 *      hashtable lock is a spinlock, not rwlock.
 *    o the idea is to move every thread through the hash lock quickly,
 *      so that the next thread can access the lookup table.
 *    o User performs hash function.
 *
 * For read:
 *    o lock hashtable.
 *          o lookup hash bin.
 *          o lock hash bin.
 *                o find entry (if failed, unlock hash, unl bin, exit).
 *                o swizzle pointers for LRU update.
 *          o unlock hashtable.
 *          o lock entry (rwlock).
 *          o unlock hash bin.
 *          o work on entry.
 *    o unlock entry.
 *
 * To update an entry, gain writelock and change the entry.
 * (the entry must keep the same hashvalue, so a data update.)
 * (you cannot upgrade a readlock to a writelock, because the item may
 *  be deleted, it would cause race conditions. So instead, unlock and
 *  relookup it in the hashtable.)
 *
 * To delete an entry:
 *    o unlock the entry if you hold the lock already.
 *    o lock hashtable.
 *          o lookup hash bin.
 *          o lock hash bin.
 *                o find entry (if failed, unlock hash, unl bin, exit).
 *                o remove entry from hashtable bin overflow chain.
 *          o unlock hashtable.
 *          o lock entry (writelock).
 *          o unlock hash bin.
 *    o unlock entry (nobody else should be waiting for this lock,
 *      since you removed it from hashtable, and you got writelock while
 *      holding the hashbinlock so you are the only one.)
 *      Note you are only allowed to obtain a lock while holding hashbinlock.
 *    o delete entry.
 *
 * The above sequence is:
 *    o race free, works with read, write and delete.
 *    o but has a queue, imagine someone needing a writelock on an item.
 *      but there are still readlocks. The writelocker waits, but holds
 *      the hashbinlock. The next thread that comes in and needs the same
 *      hashbin will wait for the lock while holding the hashtable lock.
 *      thus halting the entire system on hashtable.
 *      This is because of the delete protection. 
 *      Readlocks will be easier on the rwlock on entries.
 *      While the writer is holding writelock, similar problems happen with
 *      a reader or writer needing the same item.
 *      the scenario requires more than three threads.
 *    o so the queue length is 3 threads in a bad situation. The fourth is
 *      unable to use the hashtable.
 *
 * If you need to acquire locks on multiple items from the hashtable.
 *    o you MUST release all locks on items from the hashtable before
 *      doing the next lookup/insert/delete/whatever.
 *    o To acquire multiple items you should use a special routine that
 *      obtains the locks on those multiple items in one go.
 */

#ifndef UTIL_STORAGE_LRUHASH_H
#define UTIL_STORAGE_LRUHASH_H
#include "util/locks.h"
struct lruhash_bin;
struct lruhash_entry;

/** default start size for hash arrays */
00114 #define HASH_DEFAULT_STARTARRAY           1024 /* entries in array */
/** default max memory for hash arrays */
00116 #define HASH_DEFAULT_MAXMEM         4*1024*1024 /* bytes */

/** the type of a hash value */
00119 typedef uint32_t hashvalue_t;

/** 
 * Type of function that calculates the size of an entry.
 * Result must include the size of struct lruhash_entry. 
 * Keys that are identical must also calculate to the same size.
 * size = func(key, data).
 */
00127 typedef size_t (*lruhash_sizefunc_t)(void*, void*);

/** type of function that compares two keys. return 0 if equal. */
00130 typedef int (*lruhash_compfunc_t)(void*, void*);

/** old keys are deleted. 
 * The RRset type has to revoke its ID number, markdel() is used first.
 * This function is called: func(key, userarg) */
00135 typedef void (*lruhash_delkeyfunc_t)(void*, void*);

/** old data is deleted. This function is called: func(data, userarg). */
00138 typedef void (*lruhash_deldatafunc_t)(void*, void*);

/** mark a key as pending to be deleted (and not to be used by anyone). 
 * called: func(key) */
00142 typedef void (*lruhash_markdelfunc_t)(void*);

/**
 * Hash table that keeps LRU list of entries.
 */
00147 struct lruhash {
      /** lock for exclusive access, to the lookup array */
00149       lock_quick_t lock;
      /** the size function for entries in this table */
00151       lruhash_sizefunc_t sizefunc;
      /** the compare function for entries in this table. */
00153       lruhash_compfunc_t compfunc;
      /** how to delete keys. */
00155       lruhash_delkeyfunc_t delkeyfunc;
      /** how to delete data. */
00157       lruhash_deldatafunc_t deldatafunc;
      /** how to mark a key pending deletion */
00159       lruhash_markdelfunc_t markdelfunc;
      /** user argument for user functions */
00161       void* cb_arg;

      /** the size of the lookup array */
00164       size_t size;
      /** size bitmask - since size is a power of 2 */
00166       int size_mask;
      /** lookup array of bins */
00168       struct lruhash_bin* array;

      /** the lru list, start and end, noncyclical double linked list. */
00171       struct lruhash_entry* lru_start;
      /** lru list end item (least recently used) */
00173       struct lruhash_entry* lru_end;

      /** the number of entries in the hash table. */
00176       size_t num;
      /** the amount of space used, roughly the number of bytes in use. */
00178       size_t space_used;
      /** the amount of space the hash table is maximally allowed to use. */
00180       size_t space_max;
};

/**
 * A single bin with a linked list of entries in it.
 */
00186 struct lruhash_bin {
      /** 
       * Lock for exclusive access to the linked list
       * This lock makes deletion of items safe in this overflow list.
       */
00191       lock_quick_t lock;
      /** linked list of overflow entries */
00193       struct lruhash_entry* overflow_list;
};

/**
 * An entry into the hash table.
 * To change overflow_next you need to hold the bin lock.
 * To change the lru items you need to hold the hashtable lock.
 * This structure is designed as part of key struct. And key pointer helps
 * to get the surrounding structure. Data should be allocated on its own.
 */
00203 struct lruhash_entry {
      /** 
       * rwlock for access to the contents of the entry
       * Note that it does _not_ cover the lru_ and overflow_ ptrs.
       * Even with a writelock, you cannot change hash and key.
       * You need to delete it to change hash or key.
       */
00210       lock_rw_t lock;
      /** next entry in overflow chain. Covered by hashlock and binlock. */
00212       struct lruhash_entry* overflow_next;
      /** next entry in lru chain. covered by hashlock. */
00214       struct lruhash_entry* lru_next;
      /** prev entry in lru chain. covered by hashlock. */
00216       struct lruhash_entry* lru_prev;
      /** hash value of the key. It may not change, until entry deleted. */
00218       hashvalue_t hash;
      /** key */
00220       void* key;
      /** data */
00222       void* data;
};

/**
 * Create new hash table.
 * @param start_size: size of hashtable array at start, must be power of 2.
 * @param maxmem: maximum amount of memory this table is allowed to use.
 * @param sizefunc: calculates memory usage of entries.
 * @param compfunc: compares entries, 0 on equality.
 * @param delkeyfunc: deletes key.
 *   Calling both delkey and deldata will also free the struct lruhash_entry.
 *   Make it part of the key structure and delete it in delkeyfunc.
 * @param deldatafunc: deletes data. 
 * @param arg: user argument that is passed to user function calls.
 * @return: new hash table or NULL on malloc failure.
 */
struct lruhash* lruhash_create(size_t start_size, size_t maxmem,
      lruhash_sizefunc_t sizefunc, lruhash_compfunc_t compfunc,
      lruhash_delkeyfunc_t delkeyfunc, lruhash_deldatafunc_t deldatafunc, 
      void* arg);

/**
 * Delete hash table. Entries are all deleted.
 * @param table: to delete.
 */
void lruhash_delete(struct lruhash* table);

/**
 * Clear hash table. Entries are all deleted, while locking them before 
 * doing so. At end the table is empty.
 * @param table: to make empty.
 */
void lruhash_clear(struct lruhash* table);

/**
 * Insert a new element into the hashtable. 
 * If key is already present data pointer in that entry is updated.
 * The space calculation function is called with the key, data.
 * If necessary the least recently used entries are deleted to make space.
 * If necessary the hash array is grown up.
 *
 * @param table: hash table.
 * @param hash: hash value. User calculates the hash.
 * @param entry: identifies the entry.
 *    If key already present, this entry->key is deleted immediately.
 *    But entry->data is set to NULL before deletion, and put into
 *    the existing entry. The data is then freed.
 * @param data: the data.
 * @param cb_override: if not null overrides the cb_arg for the deletefunc.
 */
void lruhash_insert(struct lruhash* table, hashvalue_t hash, 
      struct lruhash_entry* entry, void* data, void* cb_override);

/**
 * Lookup an entry in the hashtable.
 * At the end of the function you hold a (read/write)lock on the entry.
 * The LRU is updated for the entry (if found).
 * @param table: hash table.
 * @param hash: hash of key.
 * @param key: what to look for, compared against entries in overflow chain.
 *    the hash value must be set, and must work with compare function.
 * @param wr: set to true if you desire a writelock on the entry.
 *    with a writelock you can update the data part.
 * @return: pointer to the entry or NULL. The entry is locked.
 *    The user must unlock the entry when done.
 */
struct lruhash_entry* lruhash_lookup(struct lruhash* table, hashvalue_t hash, 
      void* key, int wr);

/**
 * Touch entry, so it becomes the most recently used in the LRU list.
 * Caller must hold hash table lock. The entry must be inserted already.
 * @param table: hash table.
 * @param entry: entry to make first in LRU.
 */
void lru_touch(struct lruhash* table, struct lruhash_entry* entry);

/**
 * Set the markdelfunction (or NULL)
 */
void lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_t md);

/************************* Internal functions ************************/
/*** these are only exposed for unit tests. ***/

/**
 * Remove entry from hashtable. Does nothing if not found in hashtable.
 * Delfunc is called for the entry.
 * @param table: hash table.
 * @param hash: hash of key.
 * @param key: what to look for. 
 */
void lruhash_remove(struct lruhash* table, hashvalue_t hash, void* key);

/** init the hash bins for the table */
void bin_init(struct lruhash_bin* array, size_t size);

/** delete the hash bin and entries inside it */
void bin_delete(struct lruhash* table, struct lruhash_bin* bin);

/** 
 * Find entry in hash bin. You must have locked the bin.
 * @param table: hash table with function pointers.
 * @param bin: hash bin to look into.
 * @param hash: hash value to look for.
 * @param key: key to look for.
 * @return: the entry or NULL if not found.
 */
struct lruhash_entry* bin_find_entry(struct lruhash* table, 
      struct lruhash_bin* bin, hashvalue_t hash, void* key);

/**
 * Remove entry from bin overflow chain.
 * You must have locked the bin.
 * @param bin: hash bin to look into.
 * @param entry: entry ptr that needs removal.
 */
void bin_overflow_remove(struct lruhash_bin* bin, 
      struct lruhash_entry* entry);

/**
 * Split hash bin into two new ones. Based on increased size_mask.
 * Caller must hold hash table lock.
 * At the end the routine acquires all hashbin locks (in the old array).
 * This makes it wait for other threads to finish with the bins.
 * So the bins are ready to be deleted after this function.
 * @param table: hash table with function pointers.
 * @param newa: new increased array.
 * @param newmask: new lookup mask.
 */
void bin_split(struct lruhash* table, struct lruhash_bin* newa, 
      int newmask);

/** 
 * Try to make space available by deleting old entries.
 * Assumes that the lock on the hashtable is being held by caller.
 * Caller must not hold bin locks.
 * @param table: hash table.
 * @param list: list of entries that are to be deleted later.
 *    Entries have been removed from the hash table and writelock is held.
 */
void reclaim_space(struct lruhash* table, struct lruhash_entry** list);

/**
 * Grow the table lookup array. Becomes twice as large.
 * Caller must hold the hash table lock. Must not hold any bin locks.
 * Tries to grow, on malloc failure, nothing happened.
 * @param table: hash table.
 */
void table_grow(struct lruhash* table);

/**
 * Put entry at front of lru. entry must be unlinked from lru.
 * Caller must hold hash table lock.
 * @param table: hash table with lru head and tail.
 * @param entry: entry to make most recently used.
 */
void lru_front(struct lruhash* table, struct lruhash_entry* entry);

/**
 * Remove entry from lru list.
 * Caller must hold hash table lock.
 * @param table: hash table with lru head and tail.
 * @param entry: entry to remove from lru.
 */
void lru_remove(struct lruhash* table, struct lruhash_entry* entry);

/**
 * Output debug info to the log as to state of the hash table.
 * @param table: hash table.
 * @param id: string printed with table to identify the hash table.
 * @param extended: set to true to print statistics on overflow bin lengths.
 */
void lruhash_status(struct lruhash* table, const char* id, int extended);

/**
 * Get memory in use now by the lruhash table.
 * @param table: hash table. Will be locked before use. And unlocked after.
 * @return size in bytes.
 */
size_t lruhash_get_mem(struct lruhash* table);

#endif /* UTIL_STORAGE_LRUHASH_H */

Generated by  Doxygen 1.6.0   Back to index