24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
| 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
48struct slabhash* slabhash_create(size_t numtables, size_t start_size,
49 size_t maxmem, lruhash_sizefunc_t sizefunc,
50 lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc,
51 lruhash_deldatafunc_t 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
87void 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
100void 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 */
110static unsigned int
111slab_idx(struct slabhash* sl, hashvalue_t hash)
112{
113 return ((hash & sl->mask) >> sl->shift);
114}
115
116void slabhash_insert(struct slabhash* sl, hashvalue_t 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
122struct lruhash_entry* slabhash_lookup(struct slabhash* sl,
123 hashvalue_t hash, void* key, int wr)
124{
125 return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
126}
127
128void slabhash_remove(struct slabhash* sl, hashvalue_t hash, void* key)
129{
130 lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
131}
132
133void 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
145size_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
156size_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
166struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_t 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 */
173static void delkey(struct slabhash_testkey* k) {
174 lock_rw_destroy(&k->entry.lock); free(k);}
175/** delete data */
176static void deldata(struct slabhash_testdata* d) {free(d);}
177
178size_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
184int 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
195void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
196{
197 delkey((struct slabhash_testkey*)key);
198}
199
200void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
201{
202 deldata((struct slabhash_testdata*)data);
203}
204
205void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_t md)
206{
207 size_t i;
208 for(i=0; i<sl->size; i++) {
209 lruhash_setmarkdel(sl->array[i], md);
210 }
211}
212
213void 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}
| 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
48struct slabhash* slabhash_create(size_t numtables, size_t start_size,
49 size_t maxmem, lruhash_sizefunc_t sizefunc,
50 lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc,
51 lruhash_deldatafunc_t 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
87void 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
100void 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 */
110static unsigned int
111slab_idx(struct slabhash* sl, hashvalue_t hash)
112{
113 return ((hash & sl->mask) >> sl->shift);
114}
115
116void slabhash_insert(struct slabhash* sl, hashvalue_t 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
122struct lruhash_entry* slabhash_lookup(struct slabhash* sl,
123 hashvalue_t hash, void* key, int wr)
124{
125 return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
126}
127
128void slabhash_remove(struct slabhash* sl, hashvalue_t hash, void* key)
129{
130 lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
131}
132
133void 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
145size_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
156size_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
166struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_t 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 */
173static void delkey(struct slabhash_testkey* k) {
174 lock_rw_destroy(&k->entry.lock); free(k);}
175/** delete data */
176static void deldata(struct slabhash_testdata* d) {free(d);}
177
178size_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
184int 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
195void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
196{
197 delkey((struct slabhash_testkey*)key);
198}
199
200void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
201{
202 deldata((struct slabhash_testdata*)data);
203}
204
205void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_t md)
206{
207 size_t i;
208 for(i=0; i<sl->size; i++) {
209 lruhash_setmarkdel(sl->array[i], md);
210 }
211}
212
213void 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}
|