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_type; 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_type)(void*, void*); 128 129 /** type of function that compares two keys. return 0 if equal. */ 130 typedef int (*lruhash_compfunc_type)(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_type)(void*, void*); 136 137 /** old data is deleted. This function is called: func(data, userarg). */ 138 typedef void (*lruhash_deldatafunc_type)(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_type)(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_type lock; 150 /** the size function for entries in this table */ 151 lruhash_sizefunc_type sizefunc; 152 /** the compare function for entries in this table. */ 153 lruhash_compfunc_type compfunc; 154 /** how to delete keys. */ 155 lruhash_delkeyfunc_type delkeyfunc; 156 /** how to delete data. */ 157 lruhash_deldatafunc_type deldatafunc; 158 /** how to mark a key pending deletion */ 159 lruhash_markdelfunc_type 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 /** the maximum collisions were detected during the lruhash_insert operations. */ 182 size_t max_collisions; 183 }; 184 185 /** 186 * A single bin with a linked list of entries in it. 187 */ 188 struct lruhash_bin { 189 /** 190 * Lock for exclusive access to the linked list 191 * This lock makes deletion of items safe in this overflow list. 192 */ 193 lock_quick_type lock; 194 /** linked list of overflow entries */ 195 struct lruhash_entry* overflow_list; 196 }; 197 198 /** 199 * An entry into the hash table. 200 * To change overflow_next you need to hold the bin lock. 201 * To change the lru items you need to hold the hashtable lock. 202 * This structure is designed as part of key struct. And key pointer helps 203 * to get the surrounding structure. Data should be allocated on its own. 204 */ 205 struct lruhash_entry { 206 /** 207 * rwlock for access to the contents of the entry 208 * Note that it does _not_ cover the lru_ and overflow_ ptrs. 209 * Even with a writelock, you cannot change hash and key. 210 * You need to delete it to change hash or key. 211 */ 212 lock_rw_type lock; 213 /** next entry in overflow chain. Covered by hashlock and binlock. */ 214 struct lruhash_entry* overflow_next; 215 /** next entry in lru chain. covered by hashlock. */ 216 struct lruhash_entry* lru_next; 217 /** prev entry in lru chain. covered by hashlock. */ 218 struct lruhash_entry* lru_prev; 219 /** hash value of the key. It may not change, until entry deleted. */ 220 hashvalue_type hash; 221 /** key */ 222 void* key; 223 /** data */ 224 void* data; 225 }; 226 227 /** 228 * Create new hash table. 229 * @param start_size: size of hashtable array at start, must be power of 2. 230 * @param maxmem: maximum amount of memory this table is allowed to use. 231 * @param sizefunc: calculates memory usage of entries. 232 * @param compfunc: compares entries, 0 on equality. 233 * @param delkeyfunc: deletes key. 234 * Calling both delkey and deldata will also free the struct lruhash_entry. 235 * Make it part of the key structure and delete it in delkeyfunc. 236 * @param deldatafunc: deletes data. 237 * @param arg: user argument that is passed to user function calls. 238 * @return: new hash table or NULL on malloc failure. 239 */ 240 struct lruhash* lruhash_create(size_t start_size, size_t maxmem, 241 lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc, 242 lruhash_delkeyfunc_type delkeyfunc, 243 lruhash_deldatafunc_type deldatafunc, void* arg); 244 245 /** 246 * Delete hash table. Entries are all deleted. 247 * @param table: to delete. 248 */ 249 void lruhash_delete(struct lruhash* table); 250 251 /** 252 * Clear hash table. Entries are all deleted, while locking them before 253 * doing so. At end the table is empty. 254 * @param table: to make empty. 255 */ 256 void lruhash_clear(struct lruhash* table); 257 258 /** 259 * Insert a new element into the hashtable. 260 * If key is already present data pointer in that entry is updated. 261 * The space calculation function is called with the key, data. 262 * If necessary the least recently used entries are deleted to make space. 263 * If necessary the hash array is grown up. 264 * 265 * @param table: hash table. 266 * @param hash: hash value. User calculates the hash. 267 * @param entry: identifies the entry. 268 * If key already present, this entry->key is deleted immediately. 269 * But entry->data is set to NULL before deletion, and put into 270 * the existing entry. The data is then freed. 271 * @param data: the data. 272 * @param cb_override: if not null overrides the cb_arg for the deletefunc. 273 */ 274 void lruhash_insert(struct lruhash* table, hashvalue_type hash, 275 struct lruhash_entry* entry, void* data, void* cb_override); 276 277 /** 278 * Lookup an entry in the hashtable. 279 * At the end of the function you hold a (read/write)lock on the entry. 280 * The LRU is updated for the entry (if found). 281 * @param table: hash table. 282 * @param hash: hash of key. 283 * @param key: what to look for, compared against entries in overflow chain. 284 * the hash value must be set, and must work with compare function. 285 * @param wr: set to true if you desire a writelock on the entry. 286 * with a writelock you can update the data part. 287 * @return: pointer to the entry or NULL. The entry is locked. 288 * The user must unlock the entry when done. 289 */ 290 struct lruhash_entry* lruhash_lookup(struct lruhash* table, 291 hashvalue_type hash, void* key, int wr); 292 293 /** 294 * Touch entry, so it becomes the most recently used in the LRU list. 295 * Caller must hold hash table lock. The entry must be inserted already. 296 * @param table: hash table. 297 * @param entry: entry to make first in LRU. 298 */ 299 void lru_touch(struct lruhash* table, struct lruhash_entry* entry); 300 301 /** 302 * Set the markdelfunction (or NULL) 303 */ 304 void lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md); 305 306 /** 307 * Update the size of an element in the hashtable. 308 * 309 * @param table: hash table. 310 * @param cb_override: if not NULL overrides the cb_arg for deletefunc. 311 * @param diff_size: difference in size to the hash table storage. 312 * This is newsize - oldsize, a positive number uses more space. 313 */ 314 void lruhash_update_space_used(struct lruhash* table, void* cb_override, 315 int diff_size); 316 317 /************************* getdns functions ************************/ 318 /*** these are used by getdns only and not by unbound. ***/ 319 320 /** 321 * Demote entry, so it becomes the least recently used in the LRU list. 322 * Caller must hold hash table lock. The entry must be inserted already. 323 * @param table: hash table. 324 * @param entry: entry to make last in LRU. 325 */ 326 void lru_demote(struct lruhash* table, struct lruhash_entry* entry); 327 328 /** 329 * Insert a new element into the hashtable, or retrieve the corresponding 330 * element of it exits. 331 * 332 * If key is already present data pointer in that entry is kept. 333 * If it is not present, a new entry is created. In that case, 334 * the space calculation function is called with the key, data. 335 * If necessary the least recently used entries are deleted to make space. 336 * If necessary the hash array is grown up. 337 * 338 * @param table: hash table. 339 * @param hash: hash value. User calculates the hash. 340 * @param entry: identifies the entry. 341 * @param data: the data. 342 * @param cb_arg: if not null overrides the cb_arg for the deletefunc. 343 * @return: pointer to the existing entry if the key was already present, 344 * or to the entry argument if it was not. 345 */ 346 struct lruhash_entry* lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash, 347 struct lruhash_entry* entry, void* data, void* cb_arg); 348 349 /************************* Internal functions ************************/ 350 /*** these are only exposed for unit tests. ***/ 351 352 /** 353 * Remove entry from hashtable. Does nothing if not found in hashtable. 354 * Delfunc is called for the entry. 355 * @param table: hash table. 356 * @param hash: hash of key. 357 * @param key: what to look for. 358 */ 359 void lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key); 360 361 /** init the hash bins for the table */ 362 void bin_init(struct lruhash_bin* array, size_t size); 363 364 /** delete the hash bin and entries inside it */ 365 void bin_delete(struct lruhash* table, struct lruhash_bin* bin); 366 367 /** 368 * Find entry in hash bin. You must have locked the bin. 369 * @param table: hash table with function pointers. 370 * @param bin: hash bin to look into. 371 * @param hash: hash value to look for. 372 * @param key: key to look for. 373 * @param collisions: how many collisions were found during the search. 374 * @return: the entry or NULL if not found. 375 */ 376 struct lruhash_entry* bin_find_entry(struct lruhash* table, 377 struct lruhash_bin* bin, hashvalue_type hash, void* key, size_t* collisions); 378 379 /** 380 * Remove entry from bin overflow chain. 381 * You must have locked the bin. 382 * @param bin: hash bin to look into. 383 * @param entry: entry ptr that needs removal. 384 */ 385 void bin_overflow_remove(struct lruhash_bin* bin, 386 struct lruhash_entry* entry); 387 388 /** 389 * Split hash bin into two new ones. Based on increased size_mask. 390 * Caller must hold hash table lock. 391 * At the end the routine acquires all hashbin locks (in the old array). 392 * This makes it wait for other threads to finish with the bins. 393 * So the bins are ready to be deleted after this function. 394 * @param table: hash table with function pointers. 395 * @param newa: new increased array. 396 * @param newmask: new lookup mask. 397 */ 398 void bin_split(struct lruhash* table, struct lruhash_bin* newa, 399 int newmask); 400 401 /** 402 * Try to make space available by deleting old entries. 403 * Assumes that the lock on the hashtable is being held by caller. 404 * Caller must not hold bin locks. 405 * @param table: hash table. 406 * @param list: list of entries that are to be deleted later. 407 * Entries have been removed from the hash table and writelock is held. 408 */ 409 void reclaim_space(struct lruhash* table, struct lruhash_entry** list); 410 411 /** 412 * Grow the table lookup array. Becomes twice as large. 413 * Caller must hold the hash table lock. Must not hold any bin locks. 414 * Tries to grow, on malloc failure, nothing happened. 415 * @param table: hash table. 416 */ 417 void table_grow(struct lruhash* table); 418 419 /** 420 * Put entry at front of lru. entry must be unlinked from lru. 421 * Caller must hold hash table lock. 422 * @param table: hash table with lru head and tail. 423 * @param entry: entry to make most recently used. 424 */ 425 void lru_front(struct lruhash* table, struct lruhash_entry* entry); 426 427 /** 428 * Remove entry from lru list. 429 * Caller must hold hash table lock. 430 * @param table: hash table with lru head and tail. 431 * @param entry: entry to remove from lru. 432 */ 433 void lru_remove(struct lruhash* table, struct lruhash_entry* entry); 434 435 /** 436 * Output debug info to the log as to state of the hash table. 437 * @param table: hash table. 438 * @param id: string printed with table to identify the hash table. 439 * @param extended: set to true to print statistics on overflow bin lengths. 440 */ 441 void lruhash_status(struct lruhash* table, const char* id, int extended); 442 443 /** 444 * Get memory in use now by the lruhash table. 445 * @param table: hash table. Will be locked before use. And unlocked after. 446 * @return size in bytes. 447 */ 448 size_t lruhash_get_mem(struct lruhash* table); 449 450 /** 451 * Traverse a lruhash. Call back for every element in the table. 452 * @param h: hash table. Locked before use. 453 * @param wr: if true writelock is obtained on element, otherwise readlock. 454 * @param func: function for every element. Do not lock or unlock elements. 455 * @param arg: user argument to func. 456 */ 457 void lruhash_traverse(struct lruhash* h, int wr, 458 void (*func)(struct lruhash_entry*, void*), void* arg); 459 460 #endif /* UTIL_STORAGE_LRUHASH_H */ 461