slabhash.c File Reference

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

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


struct slabhashslabhash_create (size_t numtables, size_t start_size, size_t maxmem, lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc, lruhash_delkeyfunc_type delkeyfunc, lruhash_deldatafunc_type deldatafunc, void *arg)
 Create new slabbed hash table. More...
void slabhash_delete (struct slabhash *sl)
 Delete hash table. More...
void slabhash_clear (struct slabhash *sl)
 Clear hash table. More...
static unsigned int slab_idx (struct slabhash *sl, hashvalue_type hash)
 helper routine to calculate the slabhash index
void slabhash_insert (struct slabhash *sl, hashvalue_type hash, struct lruhash_entry *entry, void *data, void *arg)
 Insert a new element into the hashtable, uses lruhash_insert. More...
struct lruhash_entryslabhash_lookup (struct slabhash *sl, hashvalue_type hash, void *key, int wr)
 Lookup an entry in the hashtable. More...
void slabhash_remove (struct slabhash *sl, hashvalue_type hash, void *key)
 Remove entry from hashtable. More...
void slabhash_status (struct slabhash *sl, const char *id, int extended)
 Output debug info to the log as to state of the hash table. More...
size_t slabhash_get_size (struct slabhash *sl)
 Retrieve slab hash total size. More...
int slabhash_is_size (struct slabhash *sl, size_t size, size_t slabs)
 See if slabhash is of given (size, slabs) configuration. More...
size_t slabhash_get_mem (struct slabhash *sl)
 Retrieve slab hash current memory use. More...
struct lruhashslabhash_gettable (struct slabhash *sl, hashvalue_type hash)
 Get lruhash table for a given hash value. More...
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_type md)
 Set markdel function. More...
void slabhash_traverse (struct slabhash *sh, int wr, void(*func)(struct lruhash_entry *, void *), void *arg)
 Traverse a slabhash. More...
size_t count_slabhash_entries (struct slabhash *sh)
void get_slabhash_stats (struct slabhash *sh, long long *num, long long *collisions)
 Retrieves number of items in slabhash and the current max collision level. More...

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

◆ slabhash_create()

struct slabhash* slabhash_create ( size_t  numtables,
size_t  start_size,
size_t  maxmem,
lruhash_sizefunc_type  sizefunc,
lruhash_compfunc_type  compfunc,
lruhash_delkeyfunc_type  delkeyfunc,
lruhash_deldatafunc_type  deldatafunc,
void *  arg 

Create new slabbed hash table.

numtablesnumber of hash tables to use, other parameters used to initialize these smaller hashtables.
start_sizesize of hashtable array at start, must be power of 2.
maxmemmaximum amount of memory this table is allowed to use. so every table gets maxmem/numtables to use for itself.
sizefunccalculates memory usage of entries.
compfunccompares entries, 0 on equality.
delkeyfuncdeletes key.
deldatafuncdeletes data.
arguser argument that is passed to user function calls.
: new hash table or NULL on malloc failure.

References slabhash::array, lruhash::compfunc, lruhash::deldatafunc, lruhash::delkeyfunc, log_assert, lruhash_create(), slabhash::mask, slabhash::shift, slabhash::size, lruhash::sizefunc, and slabhash_delete().

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

◆ slabhash_delete()

void slabhash_delete ( struct slabhash table)

Delete hash table.

Entries are all deleted.

tableto 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(), and slabhash_test().

◆ slabhash_clear()

void slabhash_clear ( struct slabhash table)

Clear hash table.

Entries are all deleted.

tableto make empty.

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

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

◆ slabhash_insert()

void slabhash_insert ( struct slabhash table,
hashvalue_type  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.

tablehash table.
hashhash value. User calculates the hash.
entryidentifies 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.
datathe data.
cb_overrideif not NULL overrides the cb_arg for deletefunc.

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

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

◆ slabhash_lookup()

struct lruhash_entry* slabhash_lookup ( struct slabhash table,
hashvalue_type  hash,
void *  key,
int  wr 

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).

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

References slabhash::array, lruhash_entry::hash, lruhash_entry::key, lruhash_lookup(), and slab_idx().

Referenced by dns_cache_lookup(), dnsc_nonces_lookup(), dnsc_shared_secrets_lookup(), infra_find_ip_ratedata(), infra_find_ratedata(), infra_lookup_nottl(), invalidateQueryInCache(), key_cache_search(), mesh_serve_expired_lookup(), msg_cache_lookup(), rrset_cache_lookup(), rrset_cache_update(), rrset_check_sec_status(), rrset_update_sec_status(), test_short_table(), testlookup(), and testlookup_unlim().

◆ slabhash_remove()

void slabhash_remove ( struct slabhash table,
hashvalue_type  hash,
void *  key 

Remove entry from hashtable.

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

tablehash table.
hashhash of key.
keywhat to look for.

References slabhash::array, lruhash_entry::hash, lruhash_entry::key, lruhash_remove(), and slab_idx().

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

◆ slabhash_status()

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

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

tablehash table.
idstring printed with table to identify the hash table.
extendedset 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().

◆ slabhash_get_size()

size_t slabhash_get_size ( struct slabhash table)

Retrieve slab hash total size.

tablehash table.
size configured as max.

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

Referenced by slabhash_is_size().

◆ slabhash_is_size()

int slabhash_is_size ( struct slabhash table,
size_t  size,
size_t  slabs 

See if slabhash is of given (size, slabs) configuration.

tablehash table
sizemax size to test for
slabsslab count to test for.
true if equal

References slabhash::size, and slabhash_get_size().

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

◆ slabhash_get_mem()

size_t slabhash_get_mem ( struct slabhash table)

Retrieve slab hash current memory use.

tablehash table.
memory in use.

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

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

◆ slabhash_gettable()

struct lruhash* slabhash_gettable ( struct slabhash table,
hashvalue_type  hash 

Get lruhash table for a given hash value.

tableslabbed hash table.
hashhash value.
the lru hash table.

References slabhash::array, and slab_idx().

Referenced by rrset_cache_touch().

◆ slabhash_setmarkdel()

void slabhash_setmarkdel ( struct slabhash table,
lruhash_markdelfunc_type  md 

Set markdel function.

tableslabbed hash table.
mdmarkdel function ptr.

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

Referenced by rrset_cache_create().

◆ slabhash_traverse()

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

Traverse a slabhash.

tableslabbed hash table.
wrif true, writelock is obtained, otherwise readlock.
funcfunction to call for every element.
arguser argument to function.

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

Referenced by do_dump_infra(), do_flush_bogus(), do_flush_infra(), do_flush_negative(), do_flush_zone(), and do_ratelimit_list().

◆ get_slabhash_stats()

void get_slabhash_stats ( struct slabhash table,
long long *  entries_count,
long long *  max_collisions 

Retrieves number of items in slabhash and the current max collision level.

tableslabbed hash table.
entries_countwhere to save the current number of elements.
max_collisionswhere to save the current max collisions level.

References slabhash::array, lruhash::lock, lruhash::max_collisions, lruhash::num, and slabhash::size.

Referenced by server_stats_compile().