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_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 */