1238106Sdes/* 2238106Sdes * util/storage/slabhash.c - hashtable consisting of several smaller tables. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24266114Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25266114Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26266114Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27266114Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28266114Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29266114Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30266114Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31266114Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32266114Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33266114Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * Implementation of hash table that consists of smaller hash tables. 40238106Sdes * This results in a partitioned lruhash table. 41238106Sdes * It cannot grow, but that gives it the ability to have multiple 42238106Sdes * locks. Also this means there are multiple LRU lists. 43238106Sdes */ 44238106Sdes 45238106Sdes#include "config.h" 46238106Sdes#include "util/storage/slabhash.h" 47238106Sdes 48238106Sdesstruct slabhash* slabhash_create(size_t numtables, size_t start_size, 49356345Scy size_t maxmem, lruhash_sizefunc_type sizefunc, 50356345Scy lruhash_compfunc_type compfunc, lruhash_delkeyfunc_type delkeyfunc, 51356345Scy lruhash_deldatafunc_type deldatafunc, void* arg) 52238106Sdes{ 53238106Sdes size_t i; 54238106Sdes struct slabhash* sl = (struct slabhash*)calloc(1, 55238106Sdes sizeof(struct slabhash)); 56238106Sdes if(!sl) return NULL; 57238106Sdes sl->size = numtables; 58238106Sdes log_assert(sl->size > 0); 59238106Sdes sl->array = (struct lruhash**)calloc(sl->size, sizeof(struct lruhash*)); 60238106Sdes if(!sl->array) { 61238106Sdes free(sl); 62238106Sdes return NULL; 63238106Sdes } 64238106Sdes sl->mask = (uint32_t)(sl->size - 1); 65238106Sdes if(sl->mask == 0) { 66238106Sdes sl->shift = 0; 67238106Sdes } else { 68238106Sdes log_assert( (sl->size & sl->mask) == 0 69238106Sdes /* size must be power of 2 */ ); 70238106Sdes sl->shift = 0; 71238106Sdes while(!(sl->mask & 0x80000000)) { 72238106Sdes sl->mask <<= 1; 73238106Sdes sl->shift ++; 74238106Sdes } 75238106Sdes } 76238106Sdes for(i=0; i<sl->size; i++) { 77238106Sdes sl->array[i] = lruhash_create(start_size, maxmem / sl->size, 78238106Sdes sizefunc, compfunc, delkeyfunc, deldatafunc, arg); 79238106Sdes if(!sl->array[i]) { 80238106Sdes slabhash_delete(sl); 81238106Sdes return NULL; 82238106Sdes } 83238106Sdes } 84238106Sdes return sl; 85238106Sdes} 86238106Sdes 87238106Sdesvoid slabhash_delete(struct slabhash* sl) 88238106Sdes{ 89238106Sdes if(!sl) 90238106Sdes return; 91238106Sdes if(sl->array) { 92238106Sdes size_t i; 93238106Sdes for(i=0; i<sl->size; i++) 94238106Sdes lruhash_delete(sl->array[i]); 95238106Sdes free(sl->array); 96238106Sdes } 97238106Sdes free(sl); 98238106Sdes} 99238106Sdes 100238106Sdesvoid slabhash_clear(struct slabhash* sl) 101238106Sdes{ 102238106Sdes size_t i; 103238106Sdes if(!sl) 104238106Sdes return; 105238106Sdes for(i=0; i<sl->size; i++) 106238106Sdes lruhash_clear(sl->array[i]); 107238106Sdes} 108238106Sdes 109238106Sdes/** helper routine to calculate the slabhash index */ 110238106Sdesstatic unsigned int 111356345Scyslab_idx(struct slabhash* sl, hashvalue_type hash) 112238106Sdes{ 113238106Sdes return ((hash & sl->mask) >> sl->shift); 114238106Sdes} 115238106Sdes 116356345Scyvoid slabhash_insert(struct slabhash* sl, hashvalue_type hash, 117238106Sdes struct lruhash_entry* entry, void* data, void* arg) 118238106Sdes{ 119238106Sdes lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg); 120238106Sdes} 121238106Sdes 122238106Sdesstruct lruhash_entry* slabhash_lookup(struct slabhash* sl, 123356345Scy hashvalue_type hash, void* key, int wr) 124238106Sdes{ 125238106Sdes return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr); 126238106Sdes} 127238106Sdes 128356345Scyvoid slabhash_remove(struct slabhash* sl, hashvalue_type hash, void* key) 129238106Sdes{ 130238106Sdes lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key); 131238106Sdes} 132238106Sdes 133238106Sdesvoid slabhash_status(struct slabhash* sl, const char* id, int extended) 134238106Sdes{ 135238106Sdes size_t i; 136238106Sdes char num[17]; 137238106Sdes log_info("Slabhash %s: %u tables mask=%x shift=%d", 138238106Sdes id, (unsigned)sl->size, (unsigned)sl->mask, sl->shift); 139238106Sdes for(i=0; i<sl->size; i++) { 140238106Sdes snprintf(num, sizeof(num), "table %u", (unsigned)i); 141238106Sdes lruhash_status(sl->array[i], num, extended); 142238106Sdes } 143238106Sdes} 144238106Sdes 145238106Sdessize_t slabhash_get_size(struct slabhash* sl) 146238106Sdes{ 147238106Sdes size_t i, total = 0; 148238106Sdes for(i=0; i<sl->size; i++) { 149238106Sdes lock_quick_lock(&sl->array[i]->lock); 150238106Sdes total += sl->array[i]->space_max; 151238106Sdes lock_quick_unlock(&sl->array[i]->lock); 152238106Sdes } 153238106Sdes return total; 154238106Sdes} 155238106Sdes 156356345Scyint slabhash_is_size(struct slabhash* sl, size_t size, size_t slabs) 157356345Scy{ 158356345Scy /* divide by slabs and then multiply by the number of slabs, 159356345Scy * because if the size is not an even multiple of slabs, the 160356345Scy * uneven amount needs to be removed for comparison */ 161356345Scy if(!sl) return 0; 162356345Scy if(sl->size != slabs) return 0; 163356345Scy if(slabs == 0) return 0; 164356345Scy if( (size/slabs)*slabs == slabhash_get_size(sl)) 165356345Scy return 1; 166356345Scy return 0; 167356345Scy} 168356345Scy 169238106Sdessize_t slabhash_get_mem(struct slabhash* sl) 170238106Sdes{ 171238106Sdes size_t i, total = sizeof(*sl); 172238106Sdes total += sizeof(struct lruhash*)*sl->size; 173238106Sdes for(i=0; i<sl->size; i++) { 174238106Sdes total += lruhash_get_mem(sl->array[i]); 175238106Sdes } 176238106Sdes return total; 177238106Sdes} 178238106Sdes 179356345Scystruct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash) 180238106Sdes{ 181238106Sdes return sl->array[slab_idx(sl, hash)]; 182238106Sdes} 183238106Sdes 184238106Sdes/* test code, here to avoid linking problems with fptr_wlist */ 185238106Sdes/** delete key */ 186238106Sdesstatic void delkey(struct slabhash_testkey* k) { 187238106Sdes lock_rw_destroy(&k->entry.lock); free(k);} 188238106Sdes/** delete data */ 189238106Sdesstatic void deldata(struct slabhash_testdata* d) {free(d);} 190238106Sdes 191238106Sdessize_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data)) 192238106Sdes{ 193238106Sdes return sizeof(struct slabhash_testkey) + 194238106Sdes sizeof(struct slabhash_testdata); 195238106Sdes} 196238106Sdes 197238106Sdesint test_slabhash_compfunc(void* key1, void* key2) 198238106Sdes{ 199238106Sdes struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1; 200238106Sdes struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2; 201238106Sdes if(k1->id == k2->id) 202238106Sdes return 0; 203238106Sdes if(k1->id > k2->id) 204238106Sdes return 1; 205238106Sdes return -1; 206238106Sdes} 207238106Sdes 208238106Sdesvoid test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg)) 209238106Sdes{ 210238106Sdes delkey((struct slabhash_testkey*)key); 211238106Sdes} 212238106Sdes 213238106Sdesvoid test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg)) 214238106Sdes{ 215238106Sdes deldata((struct slabhash_testdata*)data); 216238106Sdes} 217238106Sdes 218356345Scyvoid slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md) 219238106Sdes{ 220238106Sdes size_t i; 221238106Sdes for(i=0; i<sl->size; i++) { 222238106Sdes lruhash_setmarkdel(sl->array[i], md); 223238106Sdes } 224238106Sdes} 225238106Sdes 226238106Sdesvoid slabhash_traverse(struct slabhash* sh, int wr, 227276605Sdes void (*func)(struct lruhash_entry*, void*), void* arg) 228238106Sdes{ 229238106Sdes size_t i; 230238106Sdes for(i=0; i<sh->size; i++) 231238106Sdes lruhash_traverse(sh->array[i], wr, func, arg); 232238106Sdes} 233276605Sdes 234276605Sdessize_t count_slabhash_entries(struct slabhash* sh) 235276605Sdes{ 236276605Sdes size_t slab, cnt = 0; 237276605Sdes 238276605Sdes for(slab=0; slab<sh->size; slab++) { 239276605Sdes lock_quick_lock(&sh->array[slab]->lock); 240276605Sdes cnt += sh->array[slab]->num; 241276605Sdes lock_quick_unlock(&sh->array[slab]->lock); 242276605Sdes } 243276605Sdes return cnt; 244276605Sdes} 245