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 int slabhash_is_size(struct slabhash* sl, size_t size, size_t slabs) 157 { 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 if(!sl) return 0; 162 if(sl->size != slabs) return 0; 163 if(slabs == 0) return 0; 164 if( (size/slabs)*slabs == slabhash_get_size(sl)) 165 return 1; 166 return 0; 167 } 168 169 size_t slabhash_get_mem(struct slabhash* sl) 170 { 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]); 175 } 176 return total; 177 } 178 179 struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_type hash) 180 { 181 return sl->array[slab_idx(sl, hash)]; 182 } 183 184 /* test code, here to avoid linking problems with fptr_wlist */ 185 /** delete key */ 186 static void delkey(struct slabhash_testkey* k) { 187 lock_rw_destroy(&k->entry.lock); free(k);} 188 /** delete data */ 189 static void deldata(struct slabhash_testdata* d) {free(d);} 190 191 size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data)) 192 { 193 return sizeof(struct slabhash_testkey) + 194 sizeof(struct slabhash_testdata); 195 } 196 197 int test_slabhash_compfunc(void* key1, void* key2) 198 { 199 struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1; 200 struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2; 201 if(k1->id == k2->id) 202 return 0; 203 if(k1->id > k2->id) 204 return 1; 205 return -1; 206 } 207 208 void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg)) 209 { 210 delkey((struct slabhash_testkey*)key); 211 } 212 213 void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg)) 214 { 215 deldata((struct slabhash_testdata*)data); 216 } 217 218 void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_type md) 219 { 220 size_t i; 221 for(i=0; i<sl->size; i++) { 222 lruhash_setmarkdel(sl->array[i], md); 223 } 224 } 225 226 void slabhash_traverse(struct slabhash* sh, int wr, 227 void (*func)(struct lruhash_entry*, void*), void* arg) 228 { 229 size_t i; 230 for(i=0; i<sh->size; i++) 231 lruhash_traverse(sh->array[i], wr, func, arg); 232 } 233 234 size_t count_slabhash_entries(struct slabhash* sh) 235 { 236 size_t slab, cnt = 0; 237 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); 242 } 243 return cnt; 244 } 245 246 void get_slabhash_stats(struct slabhash* sh, long long* num, long long* collisions) 247 { 248 size_t slab, cnt = 0, max_collisions = 0; 249 250 for(slab=0; slab<sh->size; slab++) { 251 lock_quick_lock(&sh->array[slab]->lock); 252 cnt += sh->array[slab]->num; 253 if (max_collisions < sh->array[slab]->max_collisions) { 254 max_collisions = sh->array[slab]->max_collisions; 255 } 256 lock_quick_unlock(&sh->array[slab]->lock); 257 } 258 if (num != NULL) 259 *num = cnt; 260 if (collisions != NULL) 261 *collisions = max_collisions; 262 } 263