unbound  0.1
Functions
slabhash.c File Reference

Implementation of hash table that consists of smaller hash tables. More...

#include "config.h"
#include "util/storage/slabhash.h"

Functions

struct slabhashslabhash_create (size_t numtables, size_t start_size, size_t maxmem, lruhash_sizefunc_t sizefunc, lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, lruhash_deldatafunc_t deldatafunc, void *arg)
 Create new slabbed hash table.
void slabhash_delete (struct slabhash *sl)
 Delete hash table.
void slabhash_clear (struct slabhash *sl)
 Clear hash table.
static unsigned int slab_idx (struct slabhash *sl, hashvalue_t hash)
 helper routine to calculate the slabhash index
void slabhash_insert (struct slabhash *sl, hashvalue_t hash, struct lruhash_entry *entry, void *data, void *arg)
 Insert a new element into the hashtable, uses lruhash_insert.
struct lruhash_entryslabhash_lookup (struct slabhash *sl, hashvalue_t hash, void *key, int wr)
 Lookup an entry in the hashtable.
void slabhash_remove (struct slabhash *sl, hashvalue_t hash, void *key)
 Remove entry from hashtable.
void slabhash_status (struct slabhash *sl, const char *id, int extended)
 Output debug info to the log as to state of the hash table.
size_t slabhash_get_size (struct slabhash *sl)
 Retrieve slab hash total size.
size_t slabhash_get_mem (struct slabhash *sl)
 Retrieve slab hash current memory use.
struct lruhashslabhash_gettable (struct slabhash *sl, hashvalue_t hash)
 Get lruhash table for a given hash value.
static void delkey (struct slabhash_testkey *k)
 delete key
static void deldata (struct slabhash_testdata *d)
 delete data
size_t test_slabhash_sizefunc (void *ATTR_UNUSED(key), void *ATTR_UNUSED(data))
int test_slabhash_compfunc (void *key1, void *key2)
 test comparefunc for lruhash
void test_slabhash_delkey (void *key, void *ATTR_UNUSED(arg))
void test_slabhash_deldata (void *data, void *ATTR_UNUSED(arg))
void slabhash_setmarkdel (struct slabhash *sl, lruhash_markdelfunc_t md)
 Set markdel function.
void slabhash_traverse (struct slabhash *sh, int wr, void(*func)(struct lruhash_entry *, void *), void *arg)
 Traverse a slabhash.

Detailed Description

Implementation of hash table that consists of smaller hash tables.

This results in a partitioned lruhash table. It cannot grow, but that gives it the ability to have multiple locks. Also this means there are multiple LRU lists.

Function Documentation

struct slabhash* slabhash_create ( size_t  numtables,
size_t  start_size,
size_t  maxmem,
lruhash_sizefunc_t  sizefunc,
lruhash_compfunc_t  compfunc,
lruhash_delkeyfunc_t  delkeyfunc,
lruhash_deldatafunc_t  deldatafunc,
void *  arg 
)
read

Create new slabbed hash table.

Parameters
numtables,:number of hash tables to use, other parameters used to initialize these smaller hashtables.
start_size,:size of hashtable array at start, must be power of 2.
maxmem,:maximum amount of memory this table is allowed to use. so every table gets maxmem/numtables to use for itself.
sizefunc,:calculates memory usage of entries.
compfunc,:compares entries, 0 on equality.
delkeyfunc,:deletes key.
deldatafunc,:deletes data.
arg,:user argument that is passed to user function calls.
Returns
: new hash table or NULL on malloc failure.

References slabhash::array, log_assert, lruhash_create(), slabhash::mask, slabhash::shift, slabhash::size, and slabhash_delete().

Referenced by context_finalize(), daemon_apply_cfg(), infra_create(), key_cache_create(), rrset_cache_create(), and slabhash_test().

void slabhash_delete ( struct slabhash table)

Delete hash table.

Entries are all deleted.

Parameters
table,:to delete.

References slabhash::array, lruhash_delete(), and slabhash::size.

Referenced by context_finalize(), daemon_apply_cfg(), daemon_delete(), infra_delete(), key_cache_delete(), rrset_cache_delete(), slabhash_create(), slabhash_test(), and ub_ctx_delete().

void slabhash_clear ( struct slabhash table)

Clear hash table.

Entries are all deleted.

Parameters
table,:to make empty.

References slabhash::array, lruhash_clear(), and slabhash::size.

Referenced by daemon_cleanup(), do_flush_infra(), libworker_alloc_cleanup(), test_long_table(), and worker_alloc_cleanup().

void slabhash_insert ( struct slabhash table,
hashvalue_t  hash,
struct lruhash_entry entry,
void *  data,
void *  cb_override 
)

Insert a new element into the hashtable, uses lruhash_insert.

If key is already present data pointer in that entry is updated.

Parameters
table,:hash table.
hash,:hash value. User calculates the hash.
entry,:identifies the entry. If key already present, this entry->key is deleted immediately. But entry->data is set to NULL before deletion, and put into the existing entry. The data is then freed.
data,:the data.
cb_override,:if not NULL overrides the cb_arg for deletfunc.

References slabhash::array, lruhash_insert(), and slab_idx().

Referenced by dns_cache_store_msg(), infra_edns_update(), infra_host(), infra_rtt_update(), infra_set_lame(), key_cache_insert(), rrset_cache_update(), test_short_table(), testadd(), and testadd_unlim().

struct lruhash_entry* slabhash_lookup ( struct slabhash table,
hashvalue_t  hash,
void *  key,
int  wr 
)
read

Lookup an entry in the hashtable.

Uses lruhash_lookup. At the end of the function you hold a (read/write)lock on the entry. The LRU is updated for the entry (if found).

Parameters
table,:hash table.
hash,:hash of key.
key,:what to look for, compared against entries in overflow chain. the hash value must be set, and must work with compare function.
wr,:set to true if you desire a writelock on the entry. with a writelock you can update the data part.
Returns
: pointer to the entry or NULL. The entry is locked. The user must unlock the entry when done.

References slabhash::array, lruhash_lookup(), and slab_idx().

Referenced by dns_cache_lookup(), infra_lookup_nottl(), invalidateQueryInCache(), key_cache_search(), msg_cache_lookup(), rrset_cache_lookup(), rrset_cache_update(), rrset_check_sec_status(), rrset_update_sec_status(), test_short_table(), testlookup(), testlookup_unlim(), and worker_handle_request().

void slabhash_remove ( struct slabhash table,
hashvalue_t  hash,
void *  key 
)

Remove entry from hashtable.

Does nothing if not found in hashtable. Delfunc is called for the entry. Uses lruhash_remove.

Parameters
table,:hash table.
hash,:hash of key.
key,:what to look for.

References slabhash::array, lruhash_remove(), and slab_idx().

Referenced by do_cache_remove(), key_cache_remove(), rrset_cache_remove(), test_short_table(), testremove(), and testremove_unlim().

void slabhash_status ( struct slabhash table,
const char *  id,
int  extended 
)

Output debug info to the log as to state of the hash table.

Parameters
table,:hash table.
id,:string printed with table to identify the hash table.
extended,:set to true to print statistics on overflow bin lengths.

References slabhash::array, log_info(), lruhash_status(), slabhash::mask, slabhash::shift, and slabhash::size.

Referenced by test_long_table(), test_thr_main(), and test_threaded_table().

size_t slabhash_get_size ( struct slabhash table)

Retrieve slab hash total size.

Parameters
table,:hash table.
Returns
size configured as max.

References slabhash::array, lruhash::lock, slabhash::size, and lruhash::space_max.

Referenced by context_finalize(), daemon_apply_cfg(), infra_adjust(), and rrset_cache_adjust().

size_t slabhash_get_mem ( struct slabhash table)

Retrieve slab hash current memory use.

Parameters
table,:hash table.
Returns
memory in use.

References slabhash::array, lruhash_get_mem(), slabhash::size, and lruhash::size.

Referenced by infra_get_mem(), key_cache_get_mem(), print_mem(), and worker_mem_report().

struct lruhash* slabhash_gettable ( struct slabhash table,
hashvalue_t  hash 
)
read

Get lruhash table for a given hash value.

Parameters
table,:slabbed hash table.
hash,:hash value.
Returns
the lru hash table.

References slabhash::array, and slab_idx().

Referenced by rrset_cache_touch().

void slabhash_setmarkdel ( struct slabhash table,
lruhash_markdelfunc_t  md 
)

Set markdel function.

Parameters
table,:slabbed hash table.
md,:markdel function ptr.

References slabhash::array, lruhash_setmarkdel(), and slabhash::size.

Referenced by rrset_cache_create().

void slabhash_traverse ( struct slabhash table,
int  wr,
void(*)(struct lruhash_entry *, void *)  func,
void *  arg 
)

Traverse a slabhash.

Parameters
table,:slabbed hash table.
wr,:if true, writelock is obtained, otherwise readlock.
func,:function to call for every element.
arg,:user argument to function.

References slabhash::array, lruhash_traverse(), and slabhash::size.

Referenced by do_dump_infra(), do_flush_infra(), and do_flush_zone().