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