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 { 53 size_t i; 54 struct slabhash* sl = (struct slabhash*)calloc(1, 55 sizeof(struct slabhash)); 56 if(!sl) return NULL; 57 sl->size = numtables; 58 log_assert(sl->size > 0); 59 sl->array = (struct lruhash**)calloc(sl->size, sizeof(struct lruhash*)); 60 if(!sl->array) { 61 free(sl); 62 return NULL; 63 } 64 sl->mask = (uint32_t)(sl->size - 1); 65 if(sl->mask == 0) { 66 sl->shift = 0; 67 } else { 68 log_assert( (sl->size & sl->mask) == 0 69 /* size must be power of 2 */ ); 70 sl->shift = 0; 71 while(!(sl->mask & 0x80000000)) { 72 sl->mask <<= 1; 73 sl->shift ++; 74 } 75 } 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); 79 if(!sl->array[i]) { 80 slabhash_delete(sl); 81 return NULL; 82 } 83 } 84 return sl; 85 } 86 87 void slabhash_delete(struct slabhash* sl) 88 { 89 if(!sl) 90 return; 91 if(sl->array) { 92 size_t i; 93 for(i=0; i<sl->size; i++) 94 lruhash_delete(sl->array[i]); 95 free(sl->array); 96 } 97 free(sl); 98 } 99 100 void slabhash_clear(struct slabhash* sl) 101 { 102 size_t i; 103 if(!sl) 104 return; 105 for(i=0; i<sl->size; i++) 106 lruhash_clear(sl->array[i]); 107 } 108 109 /** helper routine to calculate the slabhash index */ 110 static unsigned int 111 slab_idx(struct slabhash* sl, hashvalue_type hash) 112 { 113 return ((hash & sl->mask) >> sl->shift); 114 } 115 116 void slabhash_insert(struct slabhash* sl, hashvalue_type hash, 117 struct lruhash_entry* entry, void* data, void* arg) 118 { 119 lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg); 120 } 121 122 struct lruhash_entry* slabhash_lookup(struct slabhash* sl, 123 hashvalue_type hash, void* key, int wr) 124 { 125 return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr); 126 } 127 128 void slabhash_remove(struct slabhash* sl, hashvalue_type hash, void* key) 129 { 130 lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key); 131 } 132 133 void slabhash_status(struct slabhash* sl, const char* id, int extended) 134 { 135 size_t i; 136 char num[17]; 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); 142 } 143 } 144 145 size_t slabhash_get_size(struct slabhash* sl) 146 { 147 size_t i, total = 0; 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); 152 } 153 return total; 154 } 155 156 size_t slabhash_get_mem(struct slabhash* sl) 157 { 158 size_t i, total = sizeof(*sl); 159 total += sizeof(struct lruhash*)*sl->size; 160 for(i=0; i<sl->size; i++) { 161 total += lruhash_get_mem(sl->array[i]); 162 } 163 return total; 164 } 165 166 struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash) 167 { 168 return sl->array[slab_idx(sl, hash)]; 169 } 170 171 /* test code, here to avoid linking problems with fptr_wlist */ 172 /** delete key */ 173 static void delkey(struct slabhash_testkey* k) { 174 lock_rw_destroy(&k->entry.lock); free(k);} 175 /** delete data */ 176 static void deldata(struct slabhash_testdata* d) {free(d);} 177 178 size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data)) 179 { 180 return sizeof(struct slabhash_testkey) + 181 sizeof(struct slabhash_testdata); 182 } 183 184 int test_slabhash_compfunc(void* key1, void* key2) 185 { 186 struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1; 187 struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2; 188 if(k1->id == k2->id) 189 return 0; 190 if(k1->id > k2->id) 191 return 1; 192 return -1; 193 } 194 195 void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg)) 196 { 197 delkey((struct slabhash_testkey*)key); 198 } 199 200 void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg)) 201 { 202 deldata((struct slabhash_testdata*)data); 203 } 204 205 void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md) 206 { 207 size_t i; 208 for(i=0; i<sl->size; i++) { 209 lruhash_setmarkdel(sl->array[i], md); 210 } 211 } 212 213 void slabhash_traverse(struct slabhash* sh, int wr, 214 void (*func)(struct lruhash_entry*, void*), void* arg) 215 { 216 size_t i; 217 for(i=0; i<sh->size; i++) 218 lruhash_traverse(sh->array[i], wr, func, arg); 219 } 220 221 size_t count_slabhash_entries(struct slabhash* sh) 222 { 223 size_t slab, cnt = 0; 224 225 for(slab=0; slab<sh->size; slab++) { 226 lock_quick_lock(&sh->array[slab]->lock); 227 cnt += sh->array[slab]->num; 228 lock_quick_unlock(&sh->array[slab]->lock); 229 } 230 return cnt; 231 } 232