1238106Sdes/* 2238106Sdes * util/storage/lruhash.h - hashtable, hash function, LRU keeping. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24238106Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25238106Sdes * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26238106Sdes * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27238106Sdes * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28238106Sdes * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29238106Sdes * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30238106Sdes * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31238106Sdes * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32238106Sdes * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33238106Sdes * POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains a hashtable with LRU keeping of entries. 40238106Sdes * 41238106Sdes * The hash table keeps a maximum memory size. Old entries are removed 42238106Sdes * to make space for new entries. 43238106Sdes * 44238106Sdes * The locking strategy is as follows: 45238106Sdes * o since (almost) every read also implies a LRU update, the 46238106Sdes * hashtable lock is a spinlock, not rwlock. 47238106Sdes * o the idea is to move every thread through the hash lock quickly, 48238106Sdes * so that the next thread can access the lookup table. 49238106Sdes * o User performs hash function. 50238106Sdes * 51238106Sdes * For read: 52238106Sdes * o lock hashtable. 53238106Sdes * o lookup hash bin. 54238106Sdes * o lock hash bin. 55238106Sdes * o find entry (if failed, unlock hash, unl bin, exit). 56238106Sdes * o swizzle pointers for LRU update. 57238106Sdes * o unlock hashtable. 58238106Sdes * o lock entry (rwlock). 59238106Sdes * o unlock hash bin. 60238106Sdes * o work on entry. 61238106Sdes * o unlock entry. 62238106Sdes * 63238106Sdes * To update an entry, gain writelock and change the entry. 64238106Sdes * (the entry must keep the same hashvalue, so a data update.) 65238106Sdes * (you cannot upgrade a readlock to a writelock, because the item may 66238106Sdes * be deleted, it would cause race conditions. So instead, unlock and 67238106Sdes * relookup it in the hashtable.) 68238106Sdes * 69238106Sdes * To delete an entry: 70238106Sdes * o unlock the entry if you hold the lock already. 71238106Sdes * o lock hashtable. 72238106Sdes * o lookup hash bin. 73238106Sdes * o lock hash bin. 74238106Sdes * o find entry (if failed, unlock hash, unl bin, exit). 75238106Sdes * o remove entry from hashtable bin overflow chain. 76238106Sdes * o unlock hashtable. 77238106Sdes * o lock entry (writelock). 78238106Sdes * o unlock hash bin. 79238106Sdes * o unlock entry (nobody else should be waiting for this lock, 80238106Sdes * since you removed it from hashtable, and you got writelock while 81238106Sdes * holding the hashbinlock so you are the only one.) 82238106Sdes * Note you are only allowed to obtain a lock while holding hashbinlock. 83238106Sdes * o delete entry. 84238106Sdes * 85238106Sdes * The above sequence is: 86238106Sdes * o race free, works with read, write and delete. 87238106Sdes * o but has a queue, imagine someone needing a writelock on an item. 88238106Sdes * but there are still readlocks. The writelocker waits, but holds 89238106Sdes * the hashbinlock. The next thread that comes in and needs the same 90238106Sdes * hashbin will wait for the lock while holding the hashtable lock. 91238106Sdes * thus halting the entire system on hashtable. 92238106Sdes * This is because of the delete protection. 93238106Sdes * Readlocks will be easier on the rwlock on entries. 94238106Sdes * While the writer is holding writelock, similar problems happen with 95238106Sdes * a reader or writer needing the same item. 96238106Sdes * the scenario requires more than three threads. 97238106Sdes * o so the queue length is 3 threads in a bad situation. The fourth is 98238106Sdes * unable to use the hashtable. 99238106Sdes * 100238106Sdes * If you need to acquire locks on multiple items from the hashtable. 101238106Sdes * o you MUST release all locks on items from the hashtable before 102238106Sdes * doing the next lookup/insert/delete/whatever. 103238106Sdes * o To acquire multiple items you should use a special routine that 104238106Sdes * obtains the locks on those multiple items in one go. 105238106Sdes */ 106238106Sdes 107238106Sdes#ifndef UTIL_STORAGE_LRUHASH_H 108238106Sdes#define UTIL_STORAGE_LRUHASH_H 109238106Sdes#include "util/locks.h" 110238106Sdesstruct lruhash_bin; 111238106Sdesstruct lruhash_entry; 112238106Sdes 113238106Sdes/** default start size for hash arrays */ 114238106Sdes#define HASH_DEFAULT_STARTARRAY 1024 /* entries in array */ 115238106Sdes/** default max memory for hash arrays */ 116238106Sdes#define HASH_DEFAULT_MAXMEM 4*1024*1024 /* bytes */ 117238106Sdes 118238106Sdes/** the type of a hash value */ 119238106Sdestypedef uint32_t hashvalue_t; 120238106Sdes 121238106Sdes/** 122238106Sdes * Type of function that calculates the size of an entry. 123238106Sdes * Result must include the size of struct lruhash_entry. 124238106Sdes * Keys that are identical must also calculate to the same size. 125238106Sdes * size = func(key, data). 126238106Sdes */ 127238106Sdestypedef size_t (*lruhash_sizefunc_t)(void*, void*); 128238106Sdes 129238106Sdes/** type of function that compares two keys. return 0 if equal. */ 130238106Sdestypedef int (*lruhash_compfunc_t)(void*, void*); 131238106Sdes 132238106Sdes/** old keys are deleted. 133238106Sdes * The RRset type has to revoke its ID number, markdel() is used first. 134238106Sdes * This function is called: func(key, userarg) */ 135238106Sdestypedef void (*lruhash_delkeyfunc_t)(void*, void*); 136238106Sdes 137238106Sdes/** old data is deleted. This function is called: func(data, userarg). */ 138238106Sdestypedef void (*lruhash_deldatafunc_t)(void*, void*); 139238106Sdes 140238106Sdes/** mark a key as pending to be deleted (and not to be used by anyone). 141238106Sdes * called: func(key) */ 142238106Sdestypedef void (*lruhash_markdelfunc_t)(void*); 143238106Sdes 144238106Sdes/** 145238106Sdes * Hash table that keeps LRU list of entries. 146238106Sdes */ 147238106Sdesstruct lruhash { 148238106Sdes /** lock for exclusive access, to the lookup array */ 149238106Sdes lock_quick_t lock; 150238106Sdes /** the size function for entries in this table */ 151238106Sdes lruhash_sizefunc_t sizefunc; 152238106Sdes /** the compare function for entries in this table. */ 153238106Sdes lruhash_compfunc_t compfunc; 154238106Sdes /** how to delete keys. */ 155238106Sdes lruhash_delkeyfunc_t delkeyfunc; 156238106Sdes /** how to delete data. */ 157238106Sdes lruhash_deldatafunc_t deldatafunc; 158238106Sdes /** how to mark a key pending deletion */ 159238106Sdes lruhash_markdelfunc_t markdelfunc; 160238106Sdes /** user argument for user functions */ 161238106Sdes void* cb_arg; 162238106Sdes 163238106Sdes /** the size of the lookup array */ 164238106Sdes size_t size; 165238106Sdes /** size bitmask - since size is a power of 2 */ 166238106Sdes int size_mask; 167238106Sdes /** lookup array of bins */ 168238106Sdes struct lruhash_bin* array; 169238106Sdes 170238106Sdes /** the lru list, start and end, noncyclical double linked list. */ 171238106Sdes struct lruhash_entry* lru_start; 172238106Sdes /** lru list end item (least recently used) */ 173238106Sdes struct lruhash_entry* lru_end; 174238106Sdes 175238106Sdes /** the number of entries in the hash table. */ 176238106Sdes size_t num; 177238106Sdes /** the amount of space used, roughly the number of bytes in use. */ 178238106Sdes size_t space_used; 179238106Sdes /** the amount of space the hash table is maximally allowed to use. */ 180238106Sdes size_t space_max; 181238106Sdes}; 182238106Sdes 183238106Sdes/** 184238106Sdes * A single bin with a linked list of entries in it. 185238106Sdes */ 186238106Sdesstruct lruhash_bin { 187238106Sdes /** 188238106Sdes * Lock for exclusive access to the linked list 189238106Sdes * This lock makes deletion of items safe in this overflow list. 190238106Sdes */ 191238106Sdes lock_quick_t lock; 192238106Sdes /** linked list of overflow entries */ 193238106Sdes struct lruhash_entry* overflow_list; 194238106Sdes}; 195238106Sdes 196238106Sdes/** 197238106Sdes * An entry into the hash table. 198238106Sdes * To change overflow_next you need to hold the bin lock. 199238106Sdes * To change the lru items you need to hold the hashtable lock. 200238106Sdes * This structure is designed as part of key struct. And key pointer helps 201238106Sdes * to get the surrounding structure. Data should be allocated on its own. 202238106Sdes */ 203238106Sdesstruct lruhash_entry { 204238106Sdes /** 205238106Sdes * rwlock for access to the contents of the entry 206238106Sdes * Note that it does _not_ cover the lru_ and overflow_ ptrs. 207238106Sdes * Even with a writelock, you cannot change hash and key. 208238106Sdes * You need to delete it to change hash or key. 209238106Sdes */ 210238106Sdes lock_rw_t lock; 211238106Sdes /** next entry in overflow chain. Covered by hashlock and binlock. */ 212238106Sdes struct lruhash_entry* overflow_next; 213238106Sdes /** next entry in lru chain. covered by hashlock. */ 214238106Sdes struct lruhash_entry* lru_next; 215238106Sdes /** prev entry in lru chain. covered by hashlock. */ 216238106Sdes struct lruhash_entry* lru_prev; 217238106Sdes /** hash value of the key. It may not change, until entry deleted. */ 218238106Sdes hashvalue_t hash; 219238106Sdes /** key */ 220238106Sdes void* key; 221238106Sdes /** data */ 222238106Sdes void* data; 223238106Sdes}; 224238106Sdes 225238106Sdes/** 226238106Sdes * Create new hash table. 227238106Sdes * @param start_size: size of hashtable array at start, must be power of 2. 228238106Sdes * @param maxmem: maximum amount of memory this table is allowed to use. 229238106Sdes * @param sizefunc: calculates memory usage of entries. 230238106Sdes * @param compfunc: compares entries, 0 on equality. 231238106Sdes * @param delkeyfunc: deletes key. 232238106Sdes * Calling both delkey and deldata will also free the struct lruhash_entry. 233238106Sdes * Make it part of the key structure and delete it in delkeyfunc. 234238106Sdes * @param deldatafunc: deletes data. 235238106Sdes * @param arg: user argument that is passed to user function calls. 236238106Sdes * @return: new hash table or NULL on malloc failure. 237238106Sdes */ 238238106Sdesstruct lruhash* lruhash_create(size_t start_size, size_t maxmem, 239238106Sdes lruhash_sizefunc_t sizefunc, lruhash_compfunc_t compfunc, 240238106Sdes lruhash_delkeyfunc_t delkeyfunc, lruhash_deldatafunc_t deldatafunc, 241238106Sdes void* arg); 242238106Sdes 243238106Sdes/** 244238106Sdes * Delete hash table. Entries are all deleted. 245238106Sdes * @param table: to delete. 246238106Sdes */ 247238106Sdesvoid lruhash_delete(struct lruhash* table); 248238106Sdes 249238106Sdes/** 250238106Sdes * Clear hash table. Entries are all deleted, while locking them before 251238106Sdes * doing so. At end the table is empty. 252238106Sdes * @param table: to make empty. 253238106Sdes */ 254238106Sdesvoid lruhash_clear(struct lruhash* table); 255238106Sdes 256238106Sdes/** 257238106Sdes * Insert a new element into the hashtable. 258238106Sdes * If key is already present data pointer in that entry is updated. 259238106Sdes * The space calculation function is called with the key, data. 260238106Sdes * If necessary the least recently used entries are deleted to make space. 261238106Sdes * If necessary the hash array is grown up. 262238106Sdes * 263238106Sdes * @param table: hash table. 264238106Sdes * @param hash: hash value. User calculates the hash. 265238106Sdes * @param entry: identifies the entry. 266238106Sdes * If key already present, this entry->key is deleted immediately. 267238106Sdes * But entry->data is set to NULL before deletion, and put into 268238106Sdes * the existing entry. The data is then freed. 269238106Sdes * @param data: the data. 270238106Sdes * @param cb_override: if not null overrides the cb_arg for the deletefunc. 271238106Sdes */ 272238106Sdesvoid lruhash_insert(struct lruhash* table, hashvalue_t hash, 273238106Sdes struct lruhash_entry* entry, void* data, void* cb_override); 274238106Sdes 275238106Sdes/** 276238106Sdes * Lookup an entry in the hashtable. 277238106Sdes * At the end of the function you hold a (read/write)lock on the entry. 278238106Sdes * The LRU is updated for the entry (if found). 279238106Sdes * @param table: hash table. 280238106Sdes * @param hash: hash of key. 281238106Sdes * @param key: what to look for, compared against entries in overflow chain. 282238106Sdes * the hash value must be set, and must work with compare function. 283238106Sdes * @param wr: set to true if you desire a writelock on the entry. 284238106Sdes * with a writelock you can update the data part. 285238106Sdes * @return: pointer to the entry or NULL. The entry is locked. 286238106Sdes * The user must unlock the entry when done. 287238106Sdes */ 288238106Sdesstruct lruhash_entry* lruhash_lookup(struct lruhash* table, hashvalue_t hash, 289238106Sdes void* key, int wr); 290238106Sdes 291238106Sdes/** 292238106Sdes * Touch entry, so it becomes the most recently used in the LRU list. 293238106Sdes * Caller must hold hash table lock. The entry must be inserted already. 294238106Sdes * @param table: hash table. 295238106Sdes * @param entry: entry to make first in LRU. 296238106Sdes */ 297238106Sdesvoid lru_touch(struct lruhash* table, struct lruhash_entry* entry); 298238106Sdes 299238106Sdes/** 300238106Sdes * Set the markdelfunction (or NULL) 301238106Sdes */ 302238106Sdesvoid lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_t md); 303238106Sdes 304238106Sdes/************************* Internal functions ************************/ 305238106Sdes/*** these are only exposed for unit tests. ***/ 306238106Sdes 307238106Sdes/** 308238106Sdes * Remove entry from hashtable. Does nothing if not found in hashtable. 309238106Sdes * Delfunc is called for the entry. 310238106Sdes * @param table: hash table. 311238106Sdes * @param hash: hash of key. 312238106Sdes * @param key: what to look for. 313238106Sdes */ 314238106Sdesvoid lruhash_remove(struct lruhash* table, hashvalue_t hash, void* key); 315238106Sdes 316238106Sdes/** init the hash bins for the table */ 317238106Sdesvoid bin_init(struct lruhash_bin* array, size_t size); 318238106Sdes 319238106Sdes/** delete the hash bin and entries inside it */ 320238106Sdesvoid bin_delete(struct lruhash* table, struct lruhash_bin* bin); 321238106Sdes 322238106Sdes/** 323238106Sdes * Find entry in hash bin. You must have locked the bin. 324238106Sdes * @param table: hash table with function pointers. 325238106Sdes * @param bin: hash bin to look into. 326238106Sdes * @param hash: hash value to look for. 327238106Sdes * @param key: key to look for. 328238106Sdes * @return: the entry or NULL if not found. 329238106Sdes */ 330238106Sdesstruct lruhash_entry* bin_find_entry(struct lruhash* table, 331238106Sdes struct lruhash_bin* bin, hashvalue_t hash, void* key); 332238106Sdes 333238106Sdes/** 334238106Sdes * Remove entry from bin overflow chain. 335238106Sdes * You must have locked the bin. 336238106Sdes * @param bin: hash bin to look into. 337238106Sdes * @param entry: entry ptr that needs removal. 338238106Sdes */ 339238106Sdesvoid bin_overflow_remove(struct lruhash_bin* bin, 340238106Sdes struct lruhash_entry* entry); 341238106Sdes 342238106Sdes/** 343238106Sdes * Split hash bin into two new ones. Based on increased size_mask. 344238106Sdes * Caller must hold hash table lock. 345238106Sdes * At the end the routine acquires all hashbin locks (in the old array). 346238106Sdes * This makes it wait for other threads to finish with the bins. 347238106Sdes * So the bins are ready to be deleted after this function. 348238106Sdes * @param table: hash table with function pointers. 349238106Sdes * @param newa: new increased array. 350238106Sdes * @param newmask: new lookup mask. 351238106Sdes */ 352238106Sdesvoid bin_split(struct lruhash* table, struct lruhash_bin* newa, 353238106Sdes int newmask); 354238106Sdes 355238106Sdes/** 356238106Sdes * Try to make space available by deleting old entries. 357238106Sdes * Assumes that the lock on the hashtable is being held by caller. 358238106Sdes * Caller must not hold bin locks. 359238106Sdes * @param table: hash table. 360238106Sdes * @param list: list of entries that are to be deleted later. 361238106Sdes * Entries have been removed from the hash table and writelock is held. 362238106Sdes */ 363238106Sdesvoid reclaim_space(struct lruhash* table, struct lruhash_entry** list); 364238106Sdes 365238106Sdes/** 366238106Sdes * Grow the table lookup array. Becomes twice as large. 367238106Sdes * Caller must hold the hash table lock. Must not hold any bin locks. 368238106Sdes * Tries to grow, on malloc failure, nothing happened. 369238106Sdes * @param table: hash table. 370238106Sdes */ 371238106Sdesvoid table_grow(struct lruhash* table); 372238106Sdes 373238106Sdes/** 374238106Sdes * Put entry at front of lru. entry must be unlinked from lru. 375238106Sdes * Caller must hold hash table lock. 376238106Sdes * @param table: hash table with lru head and tail. 377238106Sdes * @param entry: entry to make most recently used. 378238106Sdes */ 379238106Sdesvoid lru_front(struct lruhash* table, struct lruhash_entry* entry); 380238106Sdes 381238106Sdes/** 382238106Sdes * Remove entry from lru list. 383238106Sdes * Caller must hold hash table lock. 384238106Sdes * @param table: hash table with lru head and tail. 385238106Sdes * @param entry: entry to remove from lru. 386238106Sdes */ 387238106Sdesvoid lru_remove(struct lruhash* table, struct lruhash_entry* entry); 388238106Sdes 389238106Sdes/** 390238106Sdes * Output debug info to the log as to state of the hash table. 391238106Sdes * @param table: hash table. 392238106Sdes * @param id: string printed with table to identify the hash table. 393238106Sdes * @param extended: set to true to print statistics on overflow bin lengths. 394238106Sdes */ 395238106Sdesvoid lruhash_status(struct lruhash* table, const char* id, int extended); 396238106Sdes 397238106Sdes/** 398238106Sdes * Get memory in use now by the lruhash table. 399238106Sdes * @param table: hash table. Will be locked before use. And unlocked after. 400238106Sdes * @return size in bytes. 401238106Sdes */ 402238106Sdessize_t lruhash_get_mem(struct lruhash* table); 403238106Sdes 404238106Sdes/** 405238106Sdes * Traverse a lruhash. Call back for every element in the table. 406238106Sdes * @param h: hash table. Locked before use. 407238106Sdes * @param wr: if true writelock is obtained on element, otherwise readlock. 408238106Sdes * @param func: function for every element. Do not lock or unlock elements. 409238106Sdes * @param arg: user argument to func. 410238106Sdes */ 411238106Sdesvoid lruhash_traverse(struct lruhash* h, int wr, 412238106Sdes void (*func)(struct lruhash_entry*, void*), void* arg); 413238106Sdes 414238106Sdes#endif /* UTIL_STORAGE_LRUHASH_H */ 415