contrib/unbound/util/storage/slabhash.c

   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 }