2 * util/storage/slabhash.c - hashtable consisting of several smaller tables.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
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.
46 #include "util/storage/slabhash.h"
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)
54 struct slabhash* sl = (struct slabhash*)calloc(1,
55 sizeof(struct slabhash));
58 log_assert(sl->size > 0);
59 sl->array = (struct lruhash**)calloc(sl->size, sizeof(struct lruhash*));
64 sl->mask = (uint32_t)(sl->size - 1);
68 log_assert( (sl->size & sl->mask) == 0
69 /* size must be power of 2 */ );
71 while(!(sl->mask & 0x80000000)) {
76 for(i=0; i<sl->size; i++) {
77 sl->array[i] = lruhash_create(start_size, maxmem / sl->size,
78 sizefunc, compfunc, delkeyfunc, deldatafunc, arg);
87 void slabhash_delete(struct slabhash* sl)
93 for(i=0; i<sl->size; i++)
94 lruhash_delete(sl->array[i]);
100 void slabhash_clear(struct slabhash* sl)
105 for(i=0; i<sl->size; i++)
106 lruhash_clear(sl->array[i]);
109 /** helper routine to calculate the slabhash index */
111 slab_idx(struct slabhash* sl, hashvalue_type hash)
113 return ((hash & sl->mask) >> sl->shift);
116 void slabhash_insert(struct slabhash* sl, hashvalue_type hash,
117 struct lruhash_entry* entry, void* data, void* arg)
119 lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg);
122 struct lruhash_entry* slabhash_lookup(struct slabhash* sl,
123 hashvalue_type hash, void* key, int wr)
125 return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
128 void slabhash_remove(struct slabhash* sl, hashvalue_type hash, void* key)
130 lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
133 void slabhash_status(struct slabhash* sl, const char* id, int extended)
137 log_info("Slabhash %s: %u tables mask=%x shift=%d",
138 id, (unsigned)sl->size, (unsigned)sl->mask, sl->shift);
139 for(i=0; i<sl->size; i++) {
140 snprintf(num, sizeof(num), "table %u", (unsigned)i);
141 lruhash_status(sl->array[i], num, extended);
145 size_t slabhash_get_size(struct slabhash* sl)
148 for(i=0; i<sl->size; i++) {
149 lock_quick_lock(&sl->array[i]->lock);
150 total += sl->array[i]->space_max;
151 lock_quick_unlock(&sl->array[i]->lock);
156 int slabhash_is_size(struct slabhash* sl, size_t size, size_t slabs)
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 */
162 if(sl->size != slabs) return 0;
163 if(slabs == 0) return 0;
164 if( (size/slabs)*slabs == slabhash_get_size(sl))
169 size_t slabhash_get_mem(struct slabhash* sl)
171 size_t i, total = sizeof(*sl);
172 total += sizeof(struct lruhash*)*sl->size;
173 for(i=0; i<sl->size; i++) {
174 total += lruhash_get_mem(sl->array[i]);
179 struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash)
181 return sl->array[slab_idx(sl, hash)];
184 /* test code, here to avoid linking problems with fptr_wlist */
186 static void delkey(struct slabhash_testkey* k) {
187 lock_rw_destroy(&k->entry.lock); free(k);}
189 static void deldata(struct slabhash_testdata* d) {free(d);}
191 size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data))
193 return sizeof(struct slabhash_testkey) +
194 sizeof(struct slabhash_testdata);
197 int test_slabhash_compfunc(void* key1, void* key2)
199 struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1;
200 struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2;
208 void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
210 delkey((struct slabhash_testkey*)key);
213 void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
215 deldata((struct slabhash_testdata*)data);
218 void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md)
221 for(i=0; i<sl->size; i++) {
222 lruhash_setmarkdel(sl->array[i], md);
226 void slabhash_traverse(struct slabhash* sh, int wr,
227 void (*func)(struct lruhash_entry*, void*), void* arg)
230 for(i=0; i<sh->size; i++)
231 lruhash_traverse(sh->array[i], wr, func, arg);
234 size_t count_slabhash_entries(struct slabhash* sh)
236 size_t slab, cnt = 0;
238 for(slab=0; slab<sh->size; slab++) {
239 lock_quick_lock(&sh->array[slab]->lock);
240 cnt += sh->array[slab]->num;
241 lock_quick_unlock(&sh->array[slab]->lock);