contrib/unbound/util/storage/lruhash.h

   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 /************************* getdns functions ************************/
 307 /*** these are used by getdns only and not by unbound. ***/
 308
 309 /**
 310  * Demote entry, so it becomes the least recently used in the LRU list.
 311  * Caller must hold hash table lock. The entry must be inserted already.
 312  * @param table: hash table.
 313  * @param entry: entry to make last in LRU.
 314  */
 315 void lru_demote(struct lruhash* table, struct lruhash_entry* entry);
 316
 317 /**
 318  * Insert a new element into the hashtable, or retrieve the corresponding
 319  * element of it exits.
 320  *
 321  * If key is already present data pointer in that entry is kept.
 322  * If it is not present, a new entry is created. In that case,
 323  * the space calculation function is called with the key, data.
 324  * If necessary the least recently used entries are deleted to make space.
 325  * If necessary the hash array is grown up.
 326  *
 327  * @param table: hash table.
 328  * @param hash: hash value. User calculates the hash.
 329  * @param entry: identifies the entry.
 330  * @param data: the data.
 331  * @param cb_arg: if not null overrides the cb_arg for the deletefunc.
 332  * @return: pointer to the existing entry if the key was already present,
 333  *     or to the entry argument if it was not.
 334  */
 335 struct lruhash_entry* lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
 336         struct lruhash_entry* entry, void* data, void* cb_arg);
 337
 338 /************************* Internal functions ************************/
 339 /*** these are only exposed for unit tests. ***/
 340
 341 /**
 342  * Remove entry from hashtable. Does nothing if not found in hashtable.
 343  * Delfunc is called for the entry.
 344  * @param table: hash table.
 345  * @param hash: hash of key.
 346  * @param key: what to look for.
 347  */
 348 void lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key);
 349
 350 /** init the hash bins for the table */
 351 void bin_init(struct lruhash_bin* array, size_t size);
 352
 353 /** delete the hash bin and entries inside it */
 354 void bin_delete(struct lruhash* table, struct lruhash_bin* bin);
 355
 356 /**
 357  * Find entry in hash bin. You must have locked the bin.
 358  * @param table: hash table with function pointers.
 359  * @param bin: hash bin to look into.
 360  * @param hash: hash value to look for.
 361  * @param key: key to look for.
 362  * @param collisions: how many collisions were found during the search.
 363  * @return: the entry or NULL if not found.
 364  */
 365 struct lruhash_entry* bin_find_entry(struct lruhash* table,
 366         struct lruhash_bin* bin, hashvalue_type hash, void* key, size_t* collisions);
 367
 368 /**
 369  * Remove entry from bin overflow chain.
 370  * You must have locked the bin.
 371  * @param bin: hash bin to look into.
 372  * @param entry: entry ptr that needs removal.
 373  */
 374 void bin_overflow_remove(struct lruhash_bin* bin,
 375         struct lruhash_entry* entry);
 376
 377 /**
 378  * Split hash bin into two new ones. Based on increased size_mask.
 379  * Caller must hold hash table lock.
 380  * At the end the routine acquires all hashbin locks (in the old array).
 381  * This makes it wait for other threads to finish with the bins.
 382  * So the bins are ready to be deleted after this function.
 383  * @param table: hash table with function pointers.
 384  * @param newa: new increased array.
 385  * @param newmask: new lookup mask.
 386  */
 387 void bin_split(struct lruhash* table, struct lruhash_bin* newa,
 388         int newmask);
 389
 390 /**
 391  * Try to make space available by deleting old entries.
 392  * Assumes that the lock on the hashtable is being held by caller.
 393  * Caller must not hold bin locks.
 394  * @param table: hash table.
 395  * @param list: list of entries that are to be deleted later.
 396  *      Entries have been removed from the hash table and writelock is held.
 397  */
 398 void reclaim_space(struct lruhash* table, struct lruhash_entry** list);
 399
 400 /**
 401  * Grow the table lookup array. Becomes twice as large.
 402  * Caller must hold the hash table lock. Must not hold any bin locks.
 403  * Tries to grow, on malloc failure, nothing happened.
 404  * @param table: hash table.
 405  */
 406 void table_grow(struct lruhash* table);
 407
 408 /**
 409  * Put entry at front of lru. entry must be unlinked from lru.
 410  * Caller must hold hash table lock.
 411  * @param table: hash table with lru head and tail.
 412  * @param entry: entry to make most recently used.
 413  */
 414 void lru_front(struct lruhash* table, struct lruhash_entry* entry);
 415
 416 /**
 417  * Remove entry from lru list.
 418  * Caller must hold hash table lock.
 419  * @param table: hash table with lru head and tail.
 420  * @param entry: entry to remove from lru.
 421  */
 422 void lru_remove(struct lruhash* table, struct lruhash_entry* entry);
 423
 424 /**
 425  * Output debug info to the log as to state of the hash table.
 426  * @param table: hash table.
 427  * @param id: string printed with table to identify the hash table.
 428  * @param extended: set to true to print statistics on overflow bin lengths.
 429  */
 430 void lruhash_status(struct lruhash* table, const char* id, int extended);
 431
 432 /**
 433  * Get memory in use now by the lruhash table.
 434  * @param table: hash table. Will be locked before use. And unlocked after.
 435  * @return size in bytes.
 436  */
 437 size_t lruhash_get_mem(struct lruhash* table);
 438
 439 /**
 440  * Traverse a lruhash. Call back for every element in the table.
 441  * @param h: hash table.  Locked before use.
 442  * @param wr: if true writelock is obtained on element, otherwise readlock.
 443  * @param func: function for every element. Do not lock or unlock elements.
 444  * @param arg: user argument to func.
 445  */
 446 void lruhash_traverse(struct lruhash* h, int wr,
 447         void (*func)(struct lruhash_entry*, void*), void* arg);
 448
 449 #endif /* UTIL_STORAGE_LRUHASH_H */