1 /* 2 * util/storage/lruhash.h - hashtable, hash function, LRU keeping. 3 * 4 * Copyright (c) 2007, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 /** 37 * \file 38 * 39 * This file contains a hashtable with LRU keeping of entries. 40 * 41 * The hash table keeps a maximum memory size. Old entries are removed 42 * to make space for new entries. 43 * 44 * The locking strategy is as follows: 45 * o since (almost) every read also implies a LRU update, the 46 * hashtable lock is a spinlock, not rwlock. 47 * o the idea is to move every thread through the hash lock quickly, 48 * so that the next thread can access the lookup table. 49 * o User performs hash function. 50 * 51 * For read: 52 * o lock hashtable. 53 * o lookup hash bin. 54 * o lock hash bin. 55 * o find entry (if failed, unlock hash, unl bin, exit). 56 * o swizzle pointers for LRU update. 57 * o unlock hashtable. 58 * o lock entry (rwlock). 59 * o unlock hash bin. 60 * o work on entry. 61 * o unlock entry. 62 * 63 * To update an entry, gain writelock and change the entry. 64 * (the entry must keep the same hashvalue, so a data update.) 65 * (you cannot upgrade a readlock to a writelock, because the item may 66 * be deleted, it would cause race conditions. So instead, unlock and 67 * relookup it in the hashtable.) 68 * 69 * To delete an entry: 70 * o unlock the entry if you hold the lock already. 71 * o lock hashtable. 72 * o lookup hash bin. 73 * o lock hash bin. 74 * o find entry (if failed, unlock hash, unl bin, exit). 75 * o remove entry from hashtable bin overflow chain. 76 * o unlock hashtable. 77 * o lock entry (writelock). 78 * o unlock hash bin. 79 * o unlock entry (nobody else should be waiting for this lock, 80 * since you removed it from hashtable, and you got writelock while 81 * holding the hashbinlock so you are the only one.) 82 * Note you are only allowed to obtain a lock while holding hashbinlock. 83 * o delete entry. 84 * 85 * The above sequence is: 86 * o race free, works with read, write and delete. 87 * o but has a queue, imagine someone needing a writelock on an item. 88 * but there are still readlocks. The writelocker waits, but holds 89 * the hashbinlock. The next thread that comes in and needs the same 90 * hashbin will wait for the lock while holding the hashtable lock. 91 * thus halting the entire system on hashtable. 92 * This is because of the delete protection. 93 * Readlocks will be easier on the rwlock on entries. 94 * While the writer is holding writelock, similar problems happen with 95 * a reader or writer needing the same item. 96 * the scenario requires more than three threads. 97 * o so the queue length is 3 threads in a bad situation. The fourth is 98 * unable to use the hashtable. 99 * 100 * If you need to acquire locks on multiple items from the hashtable. 101 * o you MUST release all locks on items from the hashtable before 102 * doing the next lookup/insert/delete/whatever. 103 * o To acquire multiple items you should use a special routine that 104 * obtains the locks on those multiple items in one go. 105 */ 106 107 #ifndef UTIL_STORAGE_LRUHASH_H 108 #define UTIL_STORAGE_LRUHASH_H 109 #include "util/locks.h" 110 struct lruhash_bin; 111 struct lruhash_entry; 112 113 /** default start size for hash arrays */ 114 #define HASH_DEFAULT_STARTARRAY 1024 /* entries in array */ 115 /** default max memory for hash arrays */ 116 #define HASH_DEFAULT_MAXMEM 4*1024*1024 /* bytes */ 117 118 /** the type of a hash value */ 119 typedef uint32_t hashvalue_t; 120 121 /** 122 * Type of function that calculates the size of an entry. 123 * Result must include the size of struct lruhash_entry. 124 * Keys that are identical must also calculate to the same size. 125 * size = func(key, data). 126 */ 127 typedef size_t (*lruhash_sizefunc_t)(void*, void*); 128 129 /** type of function that compares two keys. return 0 if equal. */ 130 typedef int (*lruhash_compfunc_t)(void*, void*); 131 132 /** old keys are deleted. 133 * The RRset type has to revoke its ID number, markdel() is used first. 134 * This function is called: func(key, userarg) */ 135 typedef void (*lruhash_delkeyfunc_t)(void*, void*); 136 137 /** old data is deleted. This function is called: func(data, userarg). */ 138 typedef void (*lruhash_deldatafunc_t)(void*, void*); 139 140 /** mark a key as pending to be deleted (and not to be used by anyone). 141 * called: func(key) */ 142 typedef void (*lruhash_markdelfunc_t)(void*); 143 144 /** 145 * Hash table that keeps LRU list of entries. 146 */ 147 struct lruhash { 148 /** lock for exclusive access, to the lookup array */ 149 lock_quick_t lock; 150 /** the size function for entries in this table */ 151 lruhash_sizefunc_t sizefunc; 152 /** the compare function for entries in this table. */ 153 lruhash_compfunc_t compfunc; 154 /** how to delete keys. */ 155 lruhash_delkeyfunc_t delkeyfunc; 156 /** how to delete data. */ 157 lruhash_deldatafunc_t deldatafunc; 158 /** how to mark a key pending deletion */ 159 lruhash_markdelfunc_t markdelfunc; 160 /** user argument for user functions */ 161 void* cb_arg; 162 163 /** the size of the lookup array */ 164 size_t size; 165 /** size bitmask - since size is a power of 2 */ 166 int size_mask; 167 /** lookup array of bins */ 168 struct lruhash_bin* array; 169 170 /** the lru list, start and end, noncyclical double linked list. */ 171 struct lruhash_entry* lru_start; 172 /** lru list end item (least recently used) */ 173 struct lruhash_entry* lru_end; 174 175 /** the number of entries in the hash table. */ 176 size_t num; 177 /** the amount of space used, roughly the number of bytes in use. */ 178 size_t space_used; 179 /** the amount of space the hash table is maximally allowed to use. */ 180 size_t space_max; 181 }; 182 183 /** 184 * A single bin with a linked list of entries in it. 185 */ 186 struct lruhash_bin { 187 /** 188 * Lock for exclusive access to the linked list 189 * This lock makes deletion of items safe in this overflow list. 190 */ 191 lock_quick_t lock; 192 /** linked list of overflow entries */ 193 struct lruhash_entry* overflow_list; 194 }; 195 196 /** 197 * An entry into the hash table. 198 * To change overflow_next you need to hold the bin lock. 199 * To change the lru items you need to hold the hashtable lock. 200 * This structure is designed as part of key struct. And key pointer helps 201 * to get the surrounding structure. Data should be allocated on its own. 202 */ 203 struct lruhash_entry { 204 /** 205 * rwlock for access to the contents of the entry 206 * Note that it does _not_ cover the lru_ and overflow_ ptrs. 207 * Even with a writelock, you cannot change hash and key. 208 * You need to delete it to change hash or key. 209 */ 210 lock_rw_t lock; 211 /** next entry in overflow chain. Covered by hashlock and binlock. */ 212 struct lruhash_entry* overflow_next; 213 /** next entry in lru chain. covered by hashlock. */ 214 struct lruhash_entry* lru_next; 215 /** prev entry in lru chain. covered by hashlock. */ 216 struct lruhash_entry* lru_prev; 217 /** hash value of the key. It may not change, until entry deleted. */ 218 hashvalue_t hash; 219 /** key */ 220 void* key; 221 /** data */ 222 void* data; 223 }; 224 225 /** 226 * Create new hash table. 227 * @param start_size: size of hashtable array at start, must be power of 2. 228 * @param maxmem: maximum amount of memory this table is allowed to use. 229 * @param sizefunc: calculates memory usage of entries. 230 * @param compfunc: compares entries, 0 on equality. 231 * @param delkeyfunc: deletes key. 232 * Calling both delkey and deldata will also free the struct lruhash_entry. 233 * Make it part of the key structure and delete it in delkeyfunc. 234 * @param deldatafunc: deletes data. 235 * @param arg: user argument that is passed to user function calls. 236 * @return: new hash table or NULL on malloc failure. 237 */ 238 struct lruhash* lruhash_create(size_t start_size, size_t maxmem, 239 lruhash_sizefunc_t sizefunc, lruhash_compfunc_t compfunc, 240 lruhash_delkeyfunc_t delkeyfunc, lruhash_deldatafunc_t deldatafunc, 241 void* arg); 242 243 /** 244 * Delete hash table. Entries are all deleted. 245 * @param table: to delete. 246 */ 247 void lruhash_delete(struct lruhash* table); 248 249 /** 250 * Clear hash table. Entries are all deleted, while locking them before 251 * doing so. At end the table is empty. 252 * @param table: to make empty. 253 */ 254 void lruhash_clear(struct lruhash* table); 255 256 /** 257 * Insert a new element into the hashtable. 258 * If key is already present data pointer in that entry is updated. 259 * The space calculation function is called with the key, data. 260 * If necessary the least recently used entries are deleted to make space. 261 * If necessary the hash array is grown up. 262 * 263 * @param table: hash table. 264 * @param hash: hash value. User calculates the hash. 265 * @param entry: identifies the entry. 266 * If key already present, this entry->key is deleted immediately. 267 * But entry->data is set to NULL before deletion, and put into 268 * the existing entry. The data is then freed. 269 * @param data: the data. 270 * @param cb_override: if not null overrides the cb_arg for the deletefunc. 271 */ 272 void lruhash_insert(struct lruhash* table, hashvalue_t hash, 273 struct lruhash_entry* entry, void* data, void* cb_override); 274 275 /** 276 * Lookup an entry in the hashtable. 277 * At the end of the function you hold a (read/write)lock on the entry. 278 * The LRU is updated for the entry (if found). 279 * @param table: hash table. 280 * @param hash: hash of key. 281 * @param key: what to look for, compared against entries in overflow chain. 282 * the hash value must be set, and must work with compare function. 283 * @param wr: set to true if you desire a writelock on the entry. 284 * with a writelock you can update the data part. 285 * @return: pointer to the entry or NULL. The entry is locked. 286 * The user must unlock the entry when done. 287 */ 288 struct lruhash_entry* lruhash_lookup(struct lruhash* table, hashvalue_t hash, 289 void* key, int wr); 290 291 /** 292 * Touch entry, so it becomes the most recently used in the LRU list. 293 * Caller must hold hash table lock. The entry must be inserted already. 294 * @param table: hash table. 295 * @param entry: entry to make first in LRU. 296 */ 297 void lru_touch(struct lruhash* table, struct lruhash_entry* entry); 298 299 /** 300 * Set the markdelfunction (or NULL) 301 */ 302 void lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_t md); 303 304 /************************* Internal functions ************************/ 305 /*** these are only exposed for unit tests. ***/ 306 307 /** 308 * Remove entry from hashtable. Does nothing if not found in hashtable. 309 * Delfunc is called for the entry. 310 * @param table: hash table. 311 * @param hash: hash of key. 312 * @param key: what to look for. 313 */ 314 void lruhash_remove(struct lruhash* table, hashvalue_t hash, void* key); 315 316 /** init the hash bins for the table */ 317 void bin_init(struct lruhash_bin* array, size_t size); 318 319 /** delete the hash bin and entries inside it */ 320 void bin_delete(struct lruhash* table, struct lruhash_bin* bin); 321 322 /** 323 * Find entry in hash bin. You must have locked the bin. 324 * @param table: hash table with function pointers. 325 * @param bin: hash bin to look into. 326 * @param hash: hash value to look for. 327 * @param key: key to look for. 328 * @return: the entry or NULL if not found. 329 */ 330 struct lruhash_entry* bin_find_entry(struct lruhash* table, 331 struct lruhash_bin* bin, hashvalue_t hash, void* key); 332 333 /** 334 * Remove entry from bin overflow chain. 335 * You must have locked the bin. 336 * @param bin: hash bin to look into. 337 * @param entry: entry ptr that needs removal. 338 */ 339 void bin_overflow_remove(struct lruhash_bin* bin, 340 struct lruhash_entry* entry); 341 342 /** 343 * Split hash bin into two new ones. Based on increased size_mask. 344 * Caller must hold hash table lock. 345 * At the end the routine acquires all hashbin locks (in the old array). 346 * This makes it wait for other threads to finish with the bins. 347 * So the bins are ready to be deleted after this function. 348 * @param table: hash table with function pointers. 349 * @param newa: new increased array. 350 * @param newmask: new lookup mask. 351 */ 352 void bin_split(struct lruhash* table, struct lruhash_bin* newa, 353 int newmask); 354 355 /** 356 * Try to make space available by deleting old entries. 357 * Assumes that the lock on the hashtable is being held by caller. 358 * Caller must not hold bin locks. 359 * @param table: hash table. 360 * @param list: list of entries that are to be deleted later. 361 * Entries have been removed from the hash table and writelock is held. 362 */ 363 void reclaim_space(struct lruhash* table, struct lruhash_entry** list); 364 365 /** 366 * Grow the table lookup array. Becomes twice as large. 367 * Caller must hold the hash table lock. Must not hold any bin locks. 368 * Tries to grow, on malloc failure, nothing happened. 369 * @param table: hash table. 370 */ 371 void table_grow(struct lruhash* table); 372 373 /** 374 * Put entry at front of lru. entry must be unlinked from lru. 375 * Caller must hold hash table lock. 376 * @param table: hash table with lru head and tail. 377 * @param entry: entry to make most recently used. 378 */ 379 void lru_front(struct lruhash* table, struct lruhash_entry* entry); 380 381 /** 382 * Remove entry from lru list. 383 * Caller must hold hash table lock. 384 * @param table: hash table with lru head and tail. 385 * @param entry: entry to remove from lru. 386 */ 387 void lru_remove(struct lruhash* table, struct lruhash_entry* entry); 388 389 /** 390 * Output debug info to the log as to state of the hash table. 391 * @param table: hash table. 392 * @param id: string printed with table to identify the hash table. 393 * @param extended: set to true to print statistics on overflow bin lengths. 394 */ 395 void lruhash_status(struct lruhash* table, const char* id, int extended); 396 397 /** 398 * Get memory in use now by the lruhash table. 399 * @param table: hash table. Will be locked before use. And unlocked after. 400 * @return size in bytes. 401 */ 402 size_t lruhash_get_mem(struct lruhash* table); 403 404 /** 405 * Traverse a lruhash. Call back for every element in the table. 406 * @param h: hash table. Locked before use. 407 * @param wr: if true writelock is obtained on element, otherwise readlock. 408 * @param func: function for every element. Do not lock or unlock elements. 409 * @param arg: user argument to func. 410 */ 411 void lruhash_traverse(struct lruhash* h, int wr, 412 void (*func)(struct lruhash_entry*, void*), void* arg); 413 414 #endif /* UTIL_STORAGE_LRUHASH_H */ 415