Code Coverage: vinyl-cache/bin/vinyld/hash/hash_critbit.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
0
/*-
1
 * Copyright (c) 2008-2011 Varnish Software AS
2
 * All rights reserved.
3
 *
4
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
5
 *
6
 * SPDX-License-Identifier: BSD-2-Clause
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
 * 1. Redistributions of source code must retain the above copyright
12
 *    notice, this list of conditions and the following disclaimer.
13
 * 2. Redistributions in binary form must reproduce the above copyright
14
 *    notice, this list of conditions and the following disclaimer in the
15
 *    documentation and/or other materials provided with the distribution.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 *
29
 * A Crit Bit tree based hash
30
 */
31
32
// #define PHK
33
34
#include "config.h"
35
36
#include <stdlib.h>
37
38
#include "cache/cache_int.h"
39
#include "cache/cache_objhead.h"
40
41
#include "hash/hash_slinger.h"
42
#include "vmb.h"
43
#include "vtim.h"
44
45
static struct lock hcb_mtx;
46
47
/*---------------------------------------------------------------------
48
 * Table for finding out how many bits two bytes have in common,
49
 * counting from the MSB towards the LSB.
50
 * ie:
51
 *      hcb_bittbl[0x01 ^ 0x22] == 2
52
 *      hcb_bittbl[0x10 ^ 0x0b] == 3
53
 *
54
 */
55
56
static unsigned char hcb_bittbl[256];
57
58
static unsigned char
59
hcb_bits(unsigned char x, unsigned char y)
60 4568
{
61 4568
        return (hcb_bittbl[x ^ y]);
62 4568
}
63
64
static void
65
hcb_build_bittbl(void)
66 1024
{
67 1024
        unsigned char x;
68 1024
        unsigned y;
69
70 1024
        y = 0;
71 9216
        for (x = 0; x < 8; x++)
72 139264
                for (; y < (1U << x); y++)
73 131072
                        hcb_bittbl[y] = 8 - x;
74
75
        /* Quick asserts for sanity check */
76 1024
        assert(hcb_bits(0x34, 0x34) == 8);
77 1024
        AZ(hcb_bits(0xaa, 0x55));
78 1024
        assert(hcb_bits(0x01, 0x22) == 2);
79 1024
        assert(hcb_bits(0x10, 0x0b) == 3);
80 1024
}
81
82
/*---------------------------------------------------------------------
83
 * For space reasons we overload the two pointers with two different
84
 * kinds of of pointers.  We cast them to uintptr_t's and abuse the
85
 * low two bits to tell them apart, assuming that Vinyl will never
86
 * run on machines with less than 32bit alignment.
87
 *
88
 * Asserts will explode if these assumptions are not met.
89
 */
90
91
struct hcb_y {
92
        unsigned                magic;
93
#define HCB_Y_MAGIC             0x125c4bd2
94
        unsigned short          critbit;
95
        unsigned char           ptr;
96
        unsigned char           bitmask;
97
        volatile uintptr_t      leaf[2];
98
        VSTAILQ_ENTRY(hcb_y)    list;
99
};
100
101 8308
#define HCB_BIT_NODE            (1<<0)
102 12421
#define HCB_BIT_Y               (1<<1)
103
104
struct hcb_root {
105
        volatile uintptr_t      origo;
106
};
107
108
static struct hcb_root  hcb_root;
109
110
static VSTAILQ_HEAD(, hcb_y)    cool_y = VSTAILQ_HEAD_INITIALIZER(cool_y);
111
static VSTAILQ_HEAD(, hcb_y)    dead_y = VSTAILQ_HEAD_INITIALIZER(dead_y);
112
static VTAILQ_HEAD(, objhead)   cool_h = VTAILQ_HEAD_INITIALIZER(cool_h);
113
static VTAILQ_HEAD(, objhead)   dead_h = VTAILQ_HEAD_INITIALIZER(dead_h);
114
115
/*---------------------------------------------------------------------
116
 * Pointer accessor functions
117
 */
118
static int
119
hcb_is_node(uintptr_t u)
120 3368
{
121
122 3368
        return (u & HCB_BIT_NODE);
123 3368
}
124
125
static int
126
hcb_is_y(uintptr_t u)
127 7888
{
128
129 7888
        return (u & HCB_BIT_Y);
130 7888
}
131
132
static uintptr_t
133
hcb_r_node(const struct objhead *n)
134 1572
{
135
136 1572
        AZ((uintptr_t)n & (HCB_BIT_NODE | HCB_BIT_Y));
137 1572
        return (HCB_BIT_NODE | (uintptr_t)n);
138 1572
}
139
140
static struct objhead *
141
hcb_l_node(uintptr_t u)
142 3368
{
143
144 3368
        assert(u & HCB_BIT_NODE);
145 3368
        AZ(u & HCB_BIT_Y);
146 3368
        return ((struct objhead *)(u & ~HCB_BIT_NODE));
147 3368
}
148
149
static uintptr_t
150
hcb_r_y(const struct hcb_y *y)
151 472
{
152
153 472
        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
154 472
        AZ((uintptr_t)y & (HCB_BIT_NODE | HCB_BIT_Y));
155 472
        return (HCB_BIT_Y | (uintptr_t)y);
156 472
}
157
158
static struct hcb_y *
159
hcb_l_y(uintptr_t u)
160 4061
{
161
162 4061
        AZ(u & HCB_BIT_NODE);
163 4061
        assert(u & HCB_BIT_Y);
164 4061
        return ((struct hcb_y *)(u & ~HCB_BIT_Y));
165 4061
}
166
167
/*---------------------------------------------------------------------
168
 * Find the "critical" bit that separates these two digests
169
 */
170
171
static unsigned
172
hcb_crit_bit(const uint8_t *digest, const struct objhead *oh2, struct hcb_y *y)
173 472
{
174 472
        unsigned char u, r;
175
176 472
        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
177 599
        for (u = 0; u < DIGEST_LEN && digest[u] == oh2->digest[u]; u++)
178 127
                ;
179 472
        assert(u < DIGEST_LEN);
180 472
        r = hcb_bits(digest[u], oh2->digest[u]);
181 472
        y->ptr = u;
182 472
        y->bitmask = 0x80 >> r;
183 472
        y->critbit = u * 8 + r;
184 472
        return (y->critbit);
185 472
}
186
187
/*---------------------------------------------------------------------
188
 * Unless we have the lock, we need to be very careful about pointer
189
 * references into the tree, we cannot trust things to be the same
190
 * in two consecutive memory accesses.
191
 */
192
193
static struct objhead *
194
hcb_insert(const struct worker *wrk, struct hcb_root *root,
195
    const uint8_t *digest, struct objhead **noh)
196 4902
{
197 4902
        volatile uintptr_t *p;
198 4902
        uintptr_t pp;
199 4902
        struct hcb_y *y, *y2;
200 4902
        struct objhead *oh2;
201 4902
        unsigned s, s2;
202
203 4902
        p = &root->origo;
204 4902
        pp = *p;
205 4902
        if (pp == 0) {
206 1534
                if (noh == NULL)
207 768
                        return (NULL);
208 766
                oh2 = *noh;
209 766
                *noh = NULL;
210 766
                vmemcpy(oh2->digest, digest, sizeof oh2->digest);
211 766
                *p = hcb_r_node(oh2);
212 766
                return (oh2);
213 1534
        }
214
215 6911
        while (hcb_is_y(pp)) {
216 3543
                y = hcb_l_y(pp);
217 3543
                CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
218 3543
                assert(y->ptr < DIGEST_LEN);
219 3543
                s = (digest[y->ptr] & y->bitmask) != 0;
220 3543
                assert(s < 2);
221 3543
                p = &y->leaf[s];
222 3543
                pp = *p;
223 3543
        }
224
225 3368
        if (pp == 0) {
226
                /* We raced hcb_delete and got a NULL pointer */
227 0
                assert(noh == NULL);
228 0
                return (NULL);
229 0
        }
230
231 3368
        assert(hcb_is_node(pp));
232
233
        /* We found a node, does it match ? */
234 3368
        oh2 = hcb_l_node(pp);
235 3368
        CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
236 3368
        if (!vmemcmp(oh2->digest, digest, DIGEST_LEN))
237 2425
                return (oh2);
238
239 943
        if (noh == NULL)
240 472
                return (NULL);
241
242
        /* Insert */
243
244 471
        TAKE_OBJ_NOTNULL(y2, &wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
245 471
        (void)hcb_crit_bit(digest, oh2, y2);
246 471
        s2 = (digest[y2->ptr] & y2->bitmask) != 0;
247 471
        assert(s2 < 2);
248 471
        oh2 = *noh;
249 471
        *noh = NULL;
250 471
        vmemcpy(oh2->digest, digest, sizeof oh2->digest);
251 471
        y2->leaf[s2] = hcb_r_node(oh2);
252 471
        s2 = 1-s2;
253
254 471
        p = &root->origo;
255 471
        AN(*p);
256
257 781
        while (hcb_is_y(*p)) {
258 398
                y = hcb_l_y(*p);
259 398
                CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
260 398
                assert(y->critbit != y2->critbit);
261 398
                if (y->critbit > y2->critbit)
262 88
                        break;
263 310
                assert(y->ptr < DIGEST_LEN);
264 310
                s = (digest[y->ptr] & y->bitmask) != 0;
265 310
                assert(s < 2);
266 310
                p = &y->leaf[s];
267 310
        }
268 471
        y2->leaf[s2] = *p;
269 471
        VWMB();
270 471
        *p = hcb_r_y(y2);
271 471
        return (oh2);
272 471
}
273
274
/*--------------------------------------------------------------------*/
275
276
static void
277
hcb_delete(struct hcb_root *r, const struct objhead *oh)
278 214
{
279 214
        struct hcb_y *y;
280 214
        volatile uintptr_t *p;
281 214
        unsigned s;
282
283 214
        if (r->origo == hcb_r_node(oh)) {
284 140
                r->origo = 0;
285 140
                return;
286 140
        }
287 74
        p = &r->origo;
288 74
        assert(hcb_is_y(*p));
289
290 74
        y = NULL;
291 120
        while (1) {
292 120
                assert(hcb_is_y(*p));
293 120
                y = hcb_l_y(*p);
294 120
                assert(y->ptr < DIGEST_LEN);
295 120
                s = (oh->digest[y->ptr] & y->bitmask) != 0;
296 120
                assert(s < 2);
297 120
                if (y->leaf[s] == hcb_r_node(oh)) {
298 74
                        *p = y->leaf[1 - s];
299 74
                        VSTAILQ_INSERT_TAIL(&cool_y, y, list);
300 74
                        return;
301 74
                }
302 46
                p = &y->leaf[s];
303 46
        }
304 74
}
305
306
/*--------------------------------------------------------------------*/
307
308
static void * v_matchproto_(bgthread_t)
309
hcb_cleaner(struct worker *wrk, void *priv)
310 1024
{
311 1024
        struct hcb_y *y, *y2;
312 1024
        struct objhead *oh, *oh2;
313
314 1024
        (void)priv;
315 2048
        while (1) {
316 1024
                VSTAILQ_FOREACH_SAFE(y, &dead_y, list, y2) {
317 0
                        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
318 0
                        VSTAILQ_REMOVE_HEAD(&dead_y, list);
319 0
                        FREE_OBJ(y);
320 0
                }
321 1024
                VTAILQ_FOREACH_SAFE(oh, &dead_h, hoh_list, oh2) {
322 0
                        CHECK_OBJ(oh, OBJHEAD_MAGIC);
323 0
                        VTAILQ_REMOVE(&dead_h, oh, hoh_list);
324 0
                        HSH_DeleteObjHead(wrk, oh);
325 0
                }
326 1024
                Lck_Lock(&hcb_mtx);
327 1024
                VSTAILQ_CONCAT(&dead_y, &cool_y);
328 1024
                VTAILQ_CONCAT(&dead_h, &cool_h, hoh_list);
329 1024
                Lck_Unlock(&hcb_mtx);
330 1024
                Pool_Sumstat(wrk);
331 1024
                VTIM_sleep(cache_param->critbit_cooloff);
332 1024
        }
333 1024
        NEEDLESS(return (NULL));
334 1024
}
335
336
/*--------------------------------------------------------------------*/
337
338
static void v_matchproto_(hash_start_f)
339
hcb_start(void)
340 1024
{
341 1024
        struct objhead *oh = NULL;
342 1024
        pthread_t tp;
343
344 1024
        (void)oh;
345 1024
        Lck_New(&hcb_mtx, lck_hcb);
346 1024
        WRK_BgThread(&tp, "hcb-cleaner", hcb_cleaner, NULL);
347 1024
        memset(&hcb_root, 0, sizeof hcb_root);
348 1024
        hcb_build_bittbl();
349 1024
}
350
351
static int v_matchproto_(hash_deref_f)
352
hcb_deref(struct worker *wrk, struct objhead *oh)
353 2585
{
354 2585
        int r;
355
356 2585
        (void)wrk;
357 2585
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
358 2585
        Lck_AssertHeld(&oh->mtx);
359 2585
        assert(oh->refcnt > 0);
360 2585
        r = --oh->refcnt;
361 2585
        if (oh->refcnt == 0) {
362 214
                Lck_Lock(&hcb_mtx);
363 214
                hcb_delete(&hcb_root, oh);
364 214
                VTAILQ_INSERT_TAIL(&cool_h, oh, hoh_list);
365 214
                Lck_Unlock(&hcb_mtx);
366 214
        }
367 2585
        Lck_Unlock(&oh->mtx);
368
#ifdef PHK
369
        fprintf(stderr, "hcb_defef %d %d <%s>\n", __LINE__, r, oh->hash);
370
#endif
371 2585
        return (r);
372 2585
}
373
374
static struct objhead * v_matchproto_(hash_lookup_f)
375
hcb_lookup(struct worker *wrk, const void *digest, struct objhead **noh)
376 3661
{
377 3661
        struct objhead *oh;
378 3661
        struct hcb_y *y;
379 3661
        unsigned u;
380
381 3661
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
382 3661
        AN(digest);
383 3662
        if (noh != NULL) {
384 3662
                CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
385 3662
                assert((*noh)->refcnt == 1);
386 3662
        }
387
388
        /* First try in read-only mode without holding a lock */
389
390 3661
        wrk->stats->hcb_nolock++;
391 3661
        oh = hcb_insert(wrk, &hcb_root, digest, NULL);
392 3661
        if (oh != NULL) {
393 2422
                Lck_Lock(&oh->mtx);
394
                /*
395
                 * A refcount of zero indicates that the tree changed
396
                 * under us, so fall through and try with the lock held.
397
                 */
398 2422
                u = oh->refcnt;
399 2422
                if (u > 0) {
400 2420
                        oh->refcnt++;
401 2420
                        return (oh);
402 2420
                }
403 2
                Lck_Unlock(&oh->mtx);
404 2
        }
405
406 1241
        while (1) {
407
                /* No luck, try with lock held, so we can modify tree */
408 1241
                CAST_OBJ_NOTNULL(y, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
409 1241
                Lck_Lock(&hcb_mtx);
410 1241
                VSC_C_main->hcb_lock++;
411 1241
                oh = hcb_insert(wrk, &hcb_root, digest, noh);
412 1241
                Lck_Unlock(&hcb_mtx);
413
414 1241
                if (oh == NULL)
415 0
                        return (NULL);
416
417 1241
                Lck_Lock(&oh->mtx);
418
419 1241
                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420 1241
                if (noh != NULL && *noh == NULL) {
421 1238
                        assert(oh->refcnt > 0);
422 1238
                        VSC_C_main->hcb_insert++;
423 1238
                        return (oh);
424 1238
                }
425
                /*
426
                 * A refcount of zero indicates that the tree changed
427
                 * under us, so fall through and try with the lock held.
428
                 */
429 3
                u = oh->refcnt;
430 3
                if (u > 0) {
431 3
                        oh->refcnt++;
432 3
                        return (oh);
433 3
                }
434 0
                Lck_Unlock(&oh->mtx);
435 0
        }
436 1241
}
437
438
static void v_matchproto_(hash_prep_f)
439
hcb_prep(struct worker *wrk)
440 3721
{
441 3721
        struct hcb_y *y;
442
443 3721
        if (wrk->wpriv->nhashpriv == NULL) {
444 1296
                ALLOC_OBJ(y, HCB_Y_MAGIC);
445 1296
                AN(y);
446 1296
                wrk->wpriv->nhashpriv = y;
447 1296
        }
448 3721
}
449
450
const struct hash_slinger hcb_slinger = {
451
        .magic  =       SLINGER_MAGIC,
452
        .name   =       "critbit",
453
        .start  =       hcb_start,
454
        .lookup =       hcb_lookup,
455
        .prep =         hcb_prep,
456
        .deref  =       hcb_deref,
457
};