diff options
Diffstat (limited to 'external/unbound/util/storage/lruhash.h')
| -rw-r--r-- | external/unbound/util/storage/lruhash.h | 414 |
1 files changed, 414 insertions, 0 deletions
diff --git a/external/unbound/util/storage/lruhash.h b/external/unbound/util/storage/lruhash.h new file mode 100644 index 000000000..30377d8e7 --- /dev/null +++ b/external/unbound/util/storage/lruhash.h @@ -0,0 +1,414 @@ +/* + * 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 COPYRIGHT + * HOLDER 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 */ +#define HASH_DEFAULT_STARTARRAY 1024 /* entries in array */ +/** default max memory for hash arrays */ +#define HASH_DEFAULT_MAXMEM 4*1024*1024 /* bytes */ + +/** the type of a hash value */ +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). + */ +typedef size_t (*lruhash_sizefunc_t)(void*, void*); + +/** type of function that compares two keys. return 0 if equal. */ +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) */ +typedef void (*lruhash_delkeyfunc_t)(void*, void*); + +/** old data is deleted. This function is called: func(data, userarg). */ +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) */ +typedef void (*lruhash_markdelfunc_t)(void*); + +/** + * Hash table that keeps LRU list of entries. + */ +struct lruhash { + /** lock for exclusive access, to the lookup array */ + lock_quick_t lock; + /** the size function for entries in this table */ + lruhash_sizefunc_t sizefunc; + /** the compare function for entries in this table. */ + lruhash_compfunc_t compfunc; + /** how to delete keys. */ + lruhash_delkeyfunc_t delkeyfunc; + /** how to delete data. */ + lruhash_deldatafunc_t deldatafunc; + /** how to mark a key pending deletion */ + lruhash_markdelfunc_t markdelfunc; + /** user argument for user functions */ + void* cb_arg; + + /** the size of the lookup array */ + size_t size; + /** size bitmask - since size is a power of 2 */ + int size_mask; + /** lookup array of bins */ + struct lruhash_bin* array; + + /** the lru list, start and end, noncyclical double linked list. */ + struct lruhash_entry* lru_start; + /** lru list end item (least recently used) */ + struct lruhash_entry* lru_end; + + /** the number of entries in the hash table. */ + size_t num; + /** the amount of space used, roughly the number of bytes in use. */ + size_t space_used; + /** the amount of space the hash table is maximally allowed to use. */ + size_t space_max; +}; + +/** + * A single bin with a linked list of entries in it. + */ +struct lruhash_bin { + /** + * Lock for exclusive access to the linked list + * This lock makes deletion of items safe in this overflow list. + */ + lock_quick_t lock; + /** linked list of overflow entries */ + 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. + */ +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. + */ + lock_rw_t lock; + /** next entry in overflow chain. Covered by hashlock and binlock. */ + struct lruhash_entry* overflow_next; + /** next entry in lru chain. covered by hashlock. */ + struct lruhash_entry* lru_next; + /** prev entry in lru chain. covered by hashlock. */ + struct lruhash_entry* lru_prev; + /** hash value of the key. It may not change, until entry deleted. */ + hashvalue_t hash; + /** key */ + void* key; + /** data */ + 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); + +/** + * Traverse a lruhash. Call back for every element in the table. + * @param h: hash table. Locked before use. + * @param wr: if true writelock is obtained on element, otherwise readlock. + * @param func: function for every element. Do not lock or unlock elements. + * @param arg: user argument to func. + */ +void lruhash_traverse(struct lruhash* h, int wr, + void (*func)(struct lruhash_entry*, void*), void* arg); + +#endif /* UTIL_STORAGE_LRUHASH_H */ |