/src/unbound/util/storage/slabhash.c

Source
/*
 * util/storage/slabhash.c - hashtable consisting of several smaller tables.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * 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.
 */

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

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)
{
  size_t i;
  struct slabhash* sl = (struct slabhash*)calloc(1, 
    sizeof(struct slabhash));
  if(!sl) return NULL;
  sl->size = numtables;
  log_assert(sl->size > 0);
  sl->array = (struct lruhash**)calloc(sl->size, sizeof(struct lruhash*));
  if(!sl->array) {
    free(sl);
    return NULL;
  }
  sl->mask = (uint32_t)(sl->size - 1);
  if(sl->mask == 0) {
    sl->shift = 0;
  } else {
    log_assert( (sl->size & sl->mask) == 0 
      /* size must be power of 2 */ );
    sl->shift = 0;
    while(!(sl->mask & 0x80000000)) {
      sl->mask <<= 1;
      sl->shift ++;
    }
  }
  for(i=0; i<sl->size; i++) {
    sl->array[i] = lruhash_create(start_size, maxmem / sl->size,
      sizefunc, compfunc, delkeyfunc, deldatafunc, arg);
    if(!sl->array[i]) {
      slabhash_delete(sl);
      return NULL;
    }
  }
  return sl;
}

void slabhash_delete(struct slabhash* sl)
{
  if(!sl)
    return;
  if(sl->array) {
    size_t i;
    for(i=0; i<sl->size; i++)
      lruhash_delete(sl->array[i]);
    free(sl->array);
  }
  free(sl);
}

void slabhash_clear(struct slabhash* sl)
{
  size_t i;
  if(!sl)
    return;
  for(i=0; i<sl->size; i++)
    lruhash_clear(sl->array[i]);
}

/** helper routine to calculate the slabhash index */
static unsigned int
slab_idx(struct slabhash* sl, hashvalue_type hash)
{
  return ((hash & sl->mask) >> sl->shift);
}

void slabhash_insert(struct slabhash* sl, hashvalue_type hash, 
  struct lruhash_entry* entry, void* data, void* arg)
{
  lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg);
}

struct lruhash_entry* slabhash_lookup(struct slabhash* sl, 
  hashvalue_type hash, void* key, int wr)
{
  return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
}

void slabhash_remove(struct slabhash* sl, hashvalue_type hash, void* key)
{
  lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
}

void slabhash_status(struct slabhash* sl, const char* id, int extended)
{
  size_t i;
  char num[17];
  log_info("Slabhash %s: %u tables mask=%x shift=%d", 
    id, (unsigned)sl->size, (unsigned)sl->mask, sl->shift);
  for(i=0; i<sl->size; i++) {
    snprintf(num, sizeof(num), "table %u", (unsigned)i);
    lruhash_status(sl->array[i], num, extended);
  }
}

size_t slabhash_get_size(struct slabhash* sl)
{
  size_t i, total = 0;
  for(i=0; i<sl->size; i++) {
    lock_quick_lock(&sl->array[i]->lock);
    total += sl->array[i]->space_max;
    lock_quick_unlock(&sl->array[i]->lock);
  }
  return total;
}

int slabhash_is_size(struct slabhash* sl, size_t size, size_t slabs)
{
  /* divide by slabs and then multiply by the number of slabs,
   * because if the size is not an even multiple of slabs, the
   * uneven amount needs to be removed for comparison */
  if(!sl) return 0;
  if(sl->size != slabs) return 0;
  if(slabs == 0) return 0;
  if( (size/slabs)*slabs == slabhash_get_size(sl))
    return 1;
  return 0;
}

void slabhash_update_space_used(struct slabhash* sl, hashvalue_type hash,
  void* cb_arg, int diff_size)
{
  lruhash_update_space_used(sl->array[slab_idx(sl, hash)], cb_arg,
    diff_size);
}

size_t slabhash_get_mem(struct slabhash* sl)
{ 
  size_t i, total = sizeof(*sl);
  total += sizeof(struct lruhash*)*sl->size;
  for(i=0; i<sl->size; i++) {
    total += lruhash_get_mem(sl->array[i]);
  }
  return total;
}

struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash)
{
  return sl->array[slab_idx(sl, hash)];
}

/* test code, here to avoid linking problems with fptr_wlist */
/** delete key */
static void delkey(struct slabhash_testkey* k) {
  lock_rw_destroy(&k->entry.lock); free(k);}
/** delete data */
static void deldata(struct slabhash_testdata* d) {free(d);}

size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data))
{
  return sizeof(struct slabhash_testkey) + 
    sizeof(struct slabhash_testdata);
}

int test_slabhash_compfunc(void* key1, void* key2)
{
  struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1;
  struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2;
  if(k1->id == k2->id)
    return 0;
  if(k1->id > k2->id)
    return 1;
  return -1;
}

void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
{
  delkey((struct slabhash_testkey*)key);
}

void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
{
  deldata((struct slabhash_testdata*)data);
}

void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md)
{
  size_t i;
  for(i=0; i<sl->size; i++) {
    lruhash_setmarkdel(sl->array[i], md);
  }
}

void slabhash_traverse(struct slabhash* sh, int wr,
  void (*func)(struct lruhash_entry*, void*), void* arg)
{
  size_t i;
  for(i=0; i<sh->size; i++)
    lruhash_traverse(sh->array[i], wr, func, arg);
}

size_t count_slabhash_entries(struct slabhash* sh)
{
  size_t slab, cnt = 0;

  for(slab=0; slab<sh->size; slab++) {
    lock_quick_lock(&sh->array[slab]->lock);
    cnt += sh->array[slab]->num;
    lock_quick_unlock(&sh->array[slab]->lock);
  }
  return cnt;
}

void get_slabhash_stats(struct slabhash* sh, long long* num, long long* collisions)
{
  size_t slab, cnt = 0, max_collisions = 0;

  for(slab=0; slab<sh->size; slab++) {
    lock_quick_lock(&sh->array[slab]->lock);
    cnt += sh->array[slab]->num;
    if (max_collisions < sh->array[slab]->max_collisions) {
      max_collisions = sh->array[slab]->max_collisions;
    }
    lock_quick_unlock(&sh->array[slab]->lock);
  }
  if (num != NULL)
    *num = cnt;
  if (collisions != NULL)
    *collisions = max_collisions;
}

void slabhash_adjust_size(struct slabhash* sl, size_t max)
{
  size_t space_max = max / sl->size;
  size_t i;
  for(i=0; i<sl->size; i++) {
    lruhash_update_space_max(sl->array[i], NULL, space_max);
  }
}

Coverage Report

Created: 2025-12-14 06:45

Line	Count	Source
1		/*
2		* util/storage/slabhash.c - hashtable consisting of several smaller tables.
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		* Implementation of hash table that consists of smaller hash tables.
40		* This results in a partitioned lruhash table.
41		* It cannot grow, but that gives it the ability to have multiple
42		* locks. Also this means there are multiple LRU lists.
43		*/
44
45		#include "config.h"
46		#include "util/storage/slabhash.h"
47
48		struct slabhash* slabhash_create(size_t numtables, size_t start_size,
49		size_t maxmem, lruhash_sizefunc_type sizefunc,
50		lruhash_compfunc_type compfunc, lruhash_delkeyfunc_type delkeyfunc,
51		lruhash_deldatafunc_type deldatafunc, void* arg)
52	4.00k	{
53	4.00k	size_t i;
54	4.00k	struct slabhash* sl = (struct slabhash*)calloc(1,
55	4.00k	sizeof(struct slabhash));
56	4.00k	if(!sl) return NULL;
57	4.00k	sl->size = numtables;
58	4.00k	log_assert(sl->size > 0);
59	4.00k	sl->array = (struct lruhash*)calloc(sl->size, sizeof(struct lruhash));
60	4.00k	if(!sl->array) {
61	0	free(sl);
62	0	return NULL;
63	0	}
64	4.00k	sl->mask = (uint32_t)(sl->size - 1);
65	4.00k	if(sl->mask == 0) {
66	0	sl->shift = 0;
67	4.00k	} else {
68	4.00k	log_assert( (sl->size & sl->mask) == 0
69	4.00k	/* size must be power of 2 */ );
70	4.00k	sl->shift = 0;
71	124k	while(!(sl->mask & 0x80000000)) {
72	120k	sl->mask <<= 1;
73	120k	sl->shift ++;
74	120k	}
75	4.00k	}
76	20.0k	for(i=0; i<sl->size; i++) {
77	16.0k	sl->array[i] = lruhash_create(start_size, maxmem / sl->size,
78	16.0k	sizefunc, compfunc, delkeyfunc, deldatafunc, arg);
79	16.0k	if(!sl->array[i]) {
80	0	slabhash_delete(sl);
81	0	return NULL;
82	0	}
83	16.0k	}
84	4.00k	return sl;
85	4.00k	}
86
87		void slabhash_delete(struct slabhash* sl)
88	4.00k	{
89	4.00k	if(!sl)
90	0	return;
91	4.00k	if(sl->array) {
92	4.00k	size_t i;
93	20.0k	for(i=0; i<sl->size; i++)
94	16.0k	lruhash_delete(sl->array[i]);
95	4.00k	free(sl->array);
96	4.00k	}
97	4.00k	free(sl);
98	4.00k	}
99
100		void slabhash_clear(struct slabhash* sl)
101	0	{
102	0	size_t i;
103	0	if(!sl)
104	0	return;
105	0	for(i=0; i<sl->size; i++)
106	0	lruhash_clear(sl->array[i]);
107	0	}
108
109		/** helper routine to calculate the slabhash index */
110		static unsigned int
111		slab_idx(struct slabhash* sl, hashvalue_type hash)
112	18.2k	{
113	18.2k	return ((hash & sl->mask) >> sl->shift);
114	18.2k	}
115
116		void slabhash_insert(struct slabhash* sl, hashvalue_type hash,
117		struct lruhash_entry* entry, void* data, void* arg)
118	9.12k	{
119	9.12k	lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg);
120	9.12k	}
121
122		struct lruhash_entry* slabhash_lookup(struct slabhash* sl,
123		hashvalue_type hash, void* key, int wr)
124	9.12k	{
125	9.12k	return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
126	9.12k	}
127
128		void slabhash_remove(struct slabhash* sl, hashvalue_type hash, void* key)
129	0	{
130	0	lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
131	0	}
132
133		void slabhash_status(struct slabhash* sl, const char* id, int extended)
134	0	{
135	0	size_t i;
136	0	char num[17];
137	0	log_info("Slabhash %s: %u tables mask=%x shift=%d",
138	0	id, (unsigned)sl->size, (unsigned)sl->mask, sl->shift);
139	0	for(i=0; i<sl->size; i++) {
140	0	snprintf(num, sizeof(num), "table %u", (unsigned)i);
141	0	lruhash_status(sl->array[i], num, extended);
142	0	}
143	0	}
144
145		size_t slabhash_get_size(struct slabhash* sl)
146	0	{
147	0	size_t i, total = 0;
148	0	for(i=0; i<sl->size; i++) {
149	0	lock_quick_lock(&sl->array[i]->lock);
150	0	total += sl->array[i]->space_max;
151	0	lock_quick_unlock(&sl->array[i]->lock);
152	0	}
153	0	return total;
154	0	}
155
156		int slabhash_is_size(struct slabhash* sl, size_t size, size_t slabs)
157	0	{
158		/* divide by slabs and then multiply by the number of slabs,
159		* because if the size is not an even multiple of slabs, the
160		* uneven amount needs to be removed for comparison */
161	0	if(!sl) return 0;
162	0	if(sl->size != slabs) return 0;
163	0	if(slabs == 0) return 0;
164	0	if( (size/slabs)*slabs == slabhash_get_size(sl))
165	0	return 1;
166	0	return 0;
167	0	}
168
169		void slabhash_update_space_used(struct slabhash* sl, hashvalue_type hash,
170		void* cb_arg, int diff_size)
171	0	{
172	0	lruhash_update_space_used(sl->array[slab_idx(sl, hash)], cb_arg,
173	0	diff_size);
174	0	}
175
176		size_t slabhash_get_mem(struct slabhash* sl)
177	0	{
178	0	size_t i, total = sizeof(*sl);
179	0	total += sizeof(struct lruhash)sl->size;
180	0	for(i=0; i<sl->size; i++) {
181	0	total += lruhash_get_mem(sl->array[i]);
182	0	}
183	0	return total;
184	0	}
185
186		struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash)
187	0	{
188	0	return sl->array[slab_idx(sl, hash)];
189	0	}
190
191		/* test code, here to avoid linking problems with fptr_wlist */
192		/** delete key */
193	0	static void delkey(struct slabhash_testkey* k) {
194	0	lock_rw_destroy(&k->entry.lock); free(k);}
195		/** delete data */
196	0	static void deldata(struct slabhash_testdata* d) {free(d);}
197
198		size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data))
199	0	{
200	0	return sizeof(struct slabhash_testkey) +
201	0	sizeof(struct slabhash_testdata);
202	0	}
203
204		int test_slabhash_compfunc(void* key1, void* key2)
205	0	{
206	0	struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1;
207	0	struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2;
208	0	if(k1->id == k2->id)
209	0	return 0;
210	0	if(k1->id > k2->id)
211	0	return 1;
212	0	return -1;
213	0	}
214
215		void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
216	0	{
217	0	delkey((struct slabhash_testkey*)key);
218	0	}
219
220		void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
221	0	{
222	0	deldata((struct slabhash_testdata*)data);
223	0	}
224
225		void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md)
226	4.00k	{
227	4.00k	size_t i;
228	20.0k	for(i=0; i<sl->size; i++) {
229	16.0k	lruhash_setmarkdel(sl->array[i], md);
230	16.0k	}
231	4.00k	}
232
233		void slabhash_traverse(struct slabhash* sh, int wr,
234		void (func)(struct lruhash_entry, void), void arg)
235	0	{
236	0	size_t i;
237	0	for(i=0; i<sh->size; i++)
238	0	lruhash_traverse(sh->array[i], wr, func, arg);
239	0	}
240
241		size_t count_slabhash_entries(struct slabhash* sh)
242	0	{
243	0	size_t slab, cnt = 0;
244
245	0	for(slab=0; slab<sh->size; slab++) {
246	0	lock_quick_lock(&sh->array[slab]->lock);
247	0	cnt += sh->array[slab]->num;
248	0	lock_quick_unlock(&sh->array[slab]->lock);
249	0	}
250	0	return cnt;
251	0	}
252
253		void get_slabhash_stats(struct slabhash* sh, long long* num, long long* collisions)
254	0	{
255	0	size_t slab, cnt = 0, max_collisions = 0;
256
257	0	for(slab=0; slab<sh->size; slab++) {
258	0	lock_quick_lock(&sh->array[slab]->lock);
259	0	cnt += sh->array[slab]->num;
260	0	if (max_collisions < sh->array[slab]->max_collisions) {
261	0	max_collisions = sh->array[slab]->max_collisions;
262	0	}
263	0	lock_quick_unlock(&sh->array[slab]->lock);
264	0	}
265	0	if (num != NULL)
266	0	*num = cnt;
267	0	if (collisions != NULL)
268	0	*collisions = max_collisions;
269	0	}
270
271		void slabhash_adjust_size(struct slabhash* sl, size_t max)
272	0	{
273	0	size_t space_max = max / sl->size;
274	0	size_t i;
275	0	for(i=0; i<sl->size; i++) {
276		lruhash_update_space_max(sl->array[i], NULL, space_max);
277	0	}
278	0	}