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 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * 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, 49238106Sdes size_t maxmem, lruhash_sizefunc_t sizefunc, 50238106Sdes lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, 51238106Sdes lruhash_deldatafunc_t 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 111238106Sdesslab_idx(struct slabhash* sl, hashvalue_t hash) 112238106Sdes{ 113238106Sdes return ((hash & sl->mask) >> sl->shift); 114238106Sdes} 115238106Sdes 116238106Sdesvoid slabhash_insert(struct slabhash* sl, hashvalue_t 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, 123238106Sdes hashvalue_t hash, void* key, int wr) 124238106Sdes{ 125238106Sdes return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr); 126238106Sdes} 127238106Sdes 128238106Sdesvoid slabhash_remove(struct slabhash* sl, hashvalue_t 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 156238106Sdessize_t slabhash_get_mem(struct slabhash* sl) 157238106Sdes{ 158238106Sdes size_t i, total = sizeof(*sl); 159238106Sdes total += sizeof(struct lruhash*)*sl->size; 160238106Sdes for(i=0; i<sl->size; i++) { 161238106Sdes total += lruhash_get_mem(sl->array[i]); 162238106Sdes } 163238106Sdes return total; 164238106Sdes} 165238106Sdes 166238106Sdesstruct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_t hash) 167238106Sdes{ 168238106Sdes return sl->array[slab_idx(sl, hash)]; 169238106Sdes} 170238106Sdes 171238106Sdes/* test code, here to avoid linking problems with fptr_wlist */ 172238106Sdes/** delete key */ 173238106Sdesstatic void delkey(struct slabhash_testkey* k) { 174238106Sdes lock_rw_destroy(&k->entry.lock); free(k);} 175238106Sdes/** delete data */ 176238106Sdesstatic void deldata(struct slabhash_testdata* d) {free(d);} 177238106Sdes 178238106Sdessize_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data)) 179238106Sdes{ 180238106Sdes return sizeof(struct slabhash_testkey) + 181238106Sdes sizeof(struct slabhash_testdata); 182238106Sdes} 183238106Sdes 184238106Sdesint test_slabhash_compfunc(void* key1, void* key2) 185238106Sdes{ 186238106Sdes struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1; 187238106Sdes struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2; 188238106Sdes if(k1->id == k2->id) 189238106Sdes return 0; 190238106Sdes if(k1->id > k2->id) 191238106Sdes return 1; 192238106Sdes return -1; 193238106Sdes} 194238106Sdes 195238106Sdesvoid test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg)) 196238106Sdes{ 197238106Sdes delkey((struct slabhash_testkey*)key); 198238106Sdes} 199238106Sdes 200238106Sdesvoid test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg)) 201238106Sdes{ 202238106Sdes deldata((struct slabhash_testdata*)data); 203238106Sdes} 204238106Sdes 205238106Sdesvoid slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_t md) 206238106Sdes{ 207238106Sdes size_t i; 208238106Sdes for(i=0; i<sl->size; i++) { 209238106Sdes lruhash_setmarkdel(sl->array[i], md); 210238106Sdes } 211238106Sdes} 212238106Sdes 213238106Sdesvoid slabhash_traverse(struct slabhash* sh, int wr, 214285206Sdes void (*func)(struct lruhash_entry*, void*), void* arg) 215238106Sdes{ 216238106Sdes size_t i; 217238106Sdes for(i=0; i<sh->size; i++) 218238106Sdes lruhash_traverse(sh->array[i], wr, func, arg); 219238106Sdes} 220285206Sdes 221285206Sdessize_t count_slabhash_entries(struct slabhash* sh) 222285206Sdes{ 223285206Sdes size_t slab, cnt = 0; 224285206Sdes 225285206Sdes for(slab=0; slab<sh->size; slab++) { 226285206Sdes lock_quick_lock(&sh->array[slab]->lock); 227285206Sdes cnt += sh->array[slab]->num; 228285206Sdes lock_quick_unlock(&sh->array[slab]->lock); 229285206Sdes } 230285206Sdes return cnt; 231285206Sdes} 232