GCOV - Varnish Cache


/*-
 * Copyright (c) 2008-2011 Varnish Software AS
 * All rights reserved.
 *
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * A Crit Bit tree based hash
 */

// #define PHK

#include "config.h"

#include <stdlib.h>

#include "cache/cache_varnishd.h"
#include "cache/cache_objhead.h"

#include "hash/hash_slinger.h"
#include "vmb.h"
#include "vtim.h"

static struct lock hcb_mtx;

/*---------------------------------------------------------------------
 * Table for finding out how many bits two bytes have in common,
 * counting from the MSB towards the LSB.
 * ie:
 *      hcb_bittbl[0x01 ^ 0x22] == 2
 *      hcb_bittbl[0x10 ^ 0x0b] == 3
 *
 */

static unsigned char hcb_bittbl[256];

static unsigned char
hcb_bits(unsigned char x, unsigned char y)
{
        return (hcb_bittbl[x ^ y]);
}

static void
hcb_build_bittbl(void)
{
        unsigned char x;
        unsigned y;

        y = 0;
        for (x = 0; x < 8; x++)
                for (; y < (1U << x); y++)
                        hcb_bittbl[y] = 8 - x;

        /* Quick asserts for sanity check */
        assert(hcb_bits(0x34, 0x34) == 8);
        AZ(hcb_bits(0xaa, 0x55));
        assert(hcb_bits(0x01, 0x22) == 2);
        assert(hcb_bits(0x10, 0x0b) == 3);
}

/*---------------------------------------------------------------------
 * For space reasons we overload the two pointers with two different
 * kinds of of pointers.  We cast them to uintptr_t's and abuse the
 * low two bits to tell them apart, assuming that Varnish will never
 * run on machines with less than 32bit alignment.
 *
 * Asserts will explode if these assumptions are not met.
 */

struct hcb_y {
        unsigned                magic;
#define HCB_Y_MAGIC             0x125c4bd2
        unsigned short          critbit;
        unsigned char           ptr;
        unsigned char           bitmask;
        volatile uintptr_t      leaf[2];
        VSTAILQ_ENTRY(hcb_y)    list;
};

#define HCB_BIT_NODE            (1<<0)
#define HCB_BIT_Y               (1<<1)

struct hcb_root {
        volatile uintptr_t      origo;
};

static struct hcb_root  hcb_root;

static VSTAILQ_HEAD(, hcb_y)    cool_y = VSTAILQ_HEAD_INITIALIZER(cool_y);
static VSTAILQ_HEAD(, hcb_y)    dead_y = VSTAILQ_HEAD_INITIALIZER(dead_y);
static VTAILQ_HEAD(, objhead)   cool_h = VTAILQ_HEAD_INITIALIZER(cool_h);
static VTAILQ_HEAD(, objhead)   dead_h = VTAILQ_HEAD_INITIALIZER(dead_h);

/*---------------------------------------------------------------------
 * Pointer accessor functions
 */
static int
hcb_is_node(uintptr_t u)
{

        return (u & HCB_BIT_NODE);
}

static int
hcb_is_y(uintptr_t u)
{

        return (u & HCB_BIT_Y);
}

static uintptr_t
hcb_r_node(const struct objhead *n)
{

        AZ((uintptr_t)n & (HCB_BIT_NODE | HCB_BIT_Y));
        return (HCB_BIT_NODE | (uintptr_t)n);
}

static struct objhead *
hcb_l_node(uintptr_t u)
{

        assert(u & HCB_BIT_NODE);
        AZ(u & HCB_BIT_Y);
        return ((struct objhead *)(u & ~HCB_BIT_NODE));
}

static uintptr_t
hcb_r_y(const struct hcb_y *y)
{

        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
        AZ((uintptr_t)y & (HCB_BIT_NODE | HCB_BIT_Y));
        return (HCB_BIT_Y | (uintptr_t)y);
}

static struct hcb_y *
hcb_l_y(uintptr_t u)
{

        AZ(u & HCB_BIT_NODE);
        assert(u & HCB_BIT_Y);
        return ((struct hcb_y *)(u & ~HCB_BIT_Y));
}

/*---------------------------------------------------------------------
 * Find the "critical" bit that separates these two digests
 */

static unsigned
hcb_crit_bit(const uint8_t *digest, const struct objhead *oh2, struct hcb_y *y)
{
        unsigned char u, r;

        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
        for (u = 0; u < DIGEST_LEN && digest[u] == oh2->digest[u]; u++)
                ;
        assert(u < DIGEST_LEN);
        r = hcb_bits(digest[u], oh2->digest[u]);
        y->ptr = u;
        y->bitmask = 0x80 >> r;
        y->critbit = u * 8 + r;
        return (y->critbit);
}

/*---------------------------------------------------------------------
 * Unless we have the lock, we need to be very careful about pointer
 * references into the tree, we cannot trust things to be the same
 * in two consecutive memory accesses.
 */

static struct objhead *
hcb_insert(const struct worker *wrk, struct hcb_root *root,
    const uint8_t *digest, struct objhead **noh)
{
        volatile uintptr_t *p;
        uintptr_t pp;
        struct hcb_y *y, *y2;
        struct objhead *oh2;
        unsigned s, s2;

        p = &root->origo;
        pp = *p;
        if (pp == 0) {
                if (noh == NULL)
                        return (NULL);
                oh2 = *noh;
                *noh = NULL;
                memcpy(oh2->digest, digest, sizeof oh2->digest);
                *p = hcb_r_node(oh2);
                return (oh2);
        }

        while (hcb_is_y(pp)) {
                y = hcb_l_y(pp);
                CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
                assert(y->ptr < DIGEST_LEN);
                s = (digest[y->ptr] & y->bitmask) != 0;
                assert(s < 2);
                p = &y->leaf[s];
                pp = *p;
        }

        if (pp == 0) {
                /* We raced hcb_delete and got a NULL pointer */
                assert(noh == NULL);
                return (NULL);
        }

        assert(hcb_is_node(pp));

        /* We found a node, does it match ? */
        oh2 = hcb_l_node(pp);
        CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
        if (!memcmp(oh2->digest, digest, DIGEST_LEN))
                return (oh2);

        if (noh == NULL)
                return (NULL);

        /* Insert */

        TAKE_OBJ_NOTNULL(y2, &wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
        (void)hcb_crit_bit(digest, oh2, y2);
        s2 = (digest[y2->ptr] & y2->bitmask) != 0;
        assert(s2 < 2);
        oh2 = *noh;
        *noh = NULL;
        memcpy(oh2->digest, digest, sizeof oh2->digest);
        y2->leaf[s2] = hcb_r_node(oh2);
        s2 = 1-s2;

        p = &root->origo;
        AN(*p);

        while (hcb_is_y(*p)) {
                y = hcb_l_y(*p);
                CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
                assert(y->critbit != y2->critbit);
                if (y->critbit > y2->critbit)
                        break;
                assert(y->ptr < DIGEST_LEN);
                s = (digest[y->ptr] & y->bitmask) != 0;
                assert(s < 2);
                p = &y->leaf[s];
        }
        y2->leaf[s2] = *p;
        VWMB();
        *p = hcb_r_y(y2);
        return (oh2);
}

/*--------------------------------------------------------------------*/

static void
hcb_delete(struct hcb_root *r, const struct objhead *oh)
{
        struct hcb_y *y;
        volatile uintptr_t *p;
        unsigned s;

        if (r->origo == hcb_r_node(oh)) {
                r->origo = 0;
                return;
        }
        p = &r->origo;
        assert(hcb_is_y(*p));

        y = NULL;
        while (1) {
                assert(hcb_is_y(*p));
                y = hcb_l_y(*p);
                assert(y->ptr < DIGEST_LEN);
                s = (oh->digest[y->ptr] & y->bitmask) != 0;
                assert(s < 2);
                if (y->leaf[s] == hcb_r_node(oh)) {
                        *p = y->leaf[1 - s];
                        VSTAILQ_INSERT_TAIL(&cool_y, y, list);
                        return;
                }
                p = &y->leaf[s];
        }
}

/*--------------------------------------------------------------------*/

static void * v_matchproto_(bgthread_t)
hcb_cleaner(struct worker *wrk, void *priv)
{
        struct hcb_y *y, *y2;
        struct objhead *oh, *oh2;

        (void)priv;
        while (1) {
                VSTAILQ_FOREACH_SAFE(y, &dead_y, list, y2) {
                        CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
                        VSTAILQ_REMOVE_HEAD(&dead_y, list);
                        FREE_OBJ(y);
                }
                VTAILQ_FOREACH_SAFE(oh, &dead_h, hoh_list, oh2) {
                        CHECK_OBJ(oh, OBJHEAD_MAGIC);
                        VTAILQ_REMOVE(&dead_h, oh, hoh_list);
                        HSH_DeleteObjHead(wrk, oh);
                }
                Lck_Lock(&hcb_mtx);
                VSTAILQ_CONCAT(&dead_y, &cool_y);
                VTAILQ_CONCAT(&dead_h, &cool_h, hoh_list);
                Lck_Unlock(&hcb_mtx);
                Pool_Sumstat(wrk);
                VTIM_sleep(cache_param->critbit_cooloff);
        }
        NEEDLESS(return (NULL));
}

/*--------------------------------------------------------------------*/

static void v_matchproto_(hash_start_f)
hcb_start(void)
{
        struct objhead *oh = NULL;
        pthread_t tp;

        (void)oh;
        Lck_New(&hcb_mtx, lck_hcb);
        WRK_BgThread(&tp, "hcb-cleaner", hcb_cleaner, NULL);
        memset(&hcb_root, 0, sizeof hcb_root);
        hcb_build_bittbl();
}

static int v_matchproto_(hash_deref_f)
hcb_deref(struct worker *wrk, struct objhead *oh)
{
        int r;

        (void)wrk;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_AssertHeld(&oh->mtx);
        assert(oh->refcnt > 0);
        r = --oh->refcnt;
        if (oh->refcnt == 0) {
                Lck_Lock(&hcb_mtx);
                hcb_delete(&hcb_root, oh);
                VTAILQ_INSERT_TAIL(&cool_h, oh, hoh_list);
                Lck_Unlock(&hcb_mtx);
        }
        Lck_Unlock(&oh->mtx);
#ifdef PHK
        fprintf(stderr, "hcb_defef %d %d <%s>\n", __LINE__, r, oh->hash);
#endif
        return (r);
}

static struct objhead * v_matchproto_(hash_lookup_f)
hcb_lookup(struct worker *wrk, const void *digest, struct objhead **noh)
{
        struct objhead *oh;
        struct hcb_y *y;
        unsigned u;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        AN(digest);
        if (noh != NULL) {
                CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
                assert((*noh)->refcnt == 1);
        }

        /* First try in read-only mode without holding a lock */

        wrk->stats->hcb_nolock++;
        oh = hcb_insert(wrk, &hcb_root, digest, NULL);
        if (oh != NULL) {
                Lck_Lock(&oh->mtx);
                /*
                 * A refcount of zero indicates that the tree changed
                 * under us, so fall through and try with the lock held.
                 */
                u = oh->refcnt;
                if (u > 0) {
                        oh->refcnt++;
                        return (oh);
                }
                Lck_Unlock(&oh->mtx);
        }

        while (1) {
                /* No luck, try with lock held, so we can modify tree */
                CAST_OBJ_NOTNULL(y, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
                Lck_Lock(&hcb_mtx);
                VSC_C_main->hcb_lock++;
                oh = hcb_insert(wrk, &hcb_root, digest, noh);
                Lck_Unlock(&hcb_mtx);

                if (oh == NULL)
                        return (NULL);

                Lck_Lock(&oh->mtx);

                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
                if (noh != NULL && *noh == NULL) {
                        assert(oh->refcnt > 0);
                        VSC_C_main->hcb_insert++;
                        return (oh);
                }
                /*
                 * A refcount of zero indicates that the tree changed
                 * under us, so fall through and try with the lock held.
                 */
                u = oh->refcnt;
                if (u > 0) {
                        oh->refcnt++;
                        return (oh);
                }
                Lck_Unlock(&oh->mtx);
        }
}

static void v_matchproto_(hash_prep_f)
hcb_prep(struct worker *wrk)
{
        struct hcb_y *y;

        if (wrk->wpriv->nhashpriv == NULL) {
                ALLOC_OBJ(y, HCB_Y_MAGIC);
                AN(y);
                wrk->wpriv->nhashpriv = y;
        }
}

const struct hash_slinger hcb_slinger = {
        .magic  =       SLINGER_MAGIC,
        .name   =       "critbit",
        .start  =       hcb_start,
        .lookup =       hcb_lookup,
        .prep =         hcb_prep,
        .deref  =       hcb_deref,
};

		varnish-cache/bin/varnishd/hash/hash_critbit.c
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_varnishd.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	167652	hcb_bits(unsigned char x, unsigned char y)
60		{
61	167652	return (hcb_bittbl[x ^ y]);
62		}
63
64		static void
65	37064	hcb_build_bittbl(void)
66		{
67		unsigned char x;
68		unsigned y;
69
70	37064	y = 0;
71	333576	for (x = 0; x < 8; x++)
72	5040704	for (; y < (1U << x); y++)
73	5040704	hcb_bittbl[y] = 8 - x;
74
75		/* Quick asserts for sanity check */
76	37064	assert(hcb_bits(0x34, 0x34) == 8);
77	37064	AZ(hcb_bits(0xaa, 0x55));
78	37064	assert(hcb_bits(0x01, 0x22) == 2);
79	37064	assert(hcb_bits(0x10, 0x0b) == 3);
80	37064	}
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 Varnish 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		#define HCB_BIT_NODE (1<<0)
102		#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	92674	hcb_is_node(uintptr_t u)
120		{
121
122	92674	return (u & HCB_BIT_NODE);
123		}
124
125		static int
126	194713	hcb_is_y(uintptr_t u)
127		{
128
129	194713	return (u & HCB_BIT_Y);
130		}
131
132		static uintptr_t
133	58416	hcb_r_node(const struct objhead *n)
134		{
135
136	58416	AZ((uintptr_t)n & (HCB_BIT_NODE \| HCB_BIT_Y));
137	58416	return (HCB_BIT_NODE \| (uintptr_t)n);
138		}
139
140		static struct objhead *
141	92668	hcb_l_node(uintptr_t u)
142		{
143
144	92668	assert(u & HCB_BIT_NODE);
145	92668	AZ(u & HCB_BIT_Y);
146	92668	return ((struct objhead *)(u & ~HCB_BIT_NODE));
147		}
148
149		static uintptr_t
150	19396	hcb_r_y(const struct hcb_y *y)
151		{
152
153	19396	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
154	19396	AZ((uintptr_t)y & (HCB_BIT_NODE \| HCB_BIT_Y));
155	19396	return (HCB_BIT_Y \| (uintptr_t)y);
156		}
157
158		static struct hcb_y *
159	83888	hcb_l_y(uintptr_t u)
160		{
161
162	83888	AZ(u & HCB_BIT_NODE);
163	83888	assert(u & HCB_BIT_Y);
164	83888	return ((struct hcb_y *)(u & ~HCB_BIT_Y));
165		}
166
167		/*---------------------------------------------------------------------
168		* Find the "critical" bit that separates these two digests
169		*/
170
171		static unsigned
172	19396	hcb_crit_bit(const uint8_t digest, const struct objhead oh2, struct hcb_y *y)
173		{
174		unsigned char u, r;
175
176	19396	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
177	24996	for (u = 0; u < DIGEST_LEN && digest[u] == oh2->digest[u]; u++)
178		;
179	19396	assert(u < DIGEST_LEN);
180	19396	r = hcb_bits(digest[u], oh2->digest[u]);
181	19396	y->ptr = u;
182	19396	y->bitmask = 0x80 >> r;
183	19396	y->critbit = u * 8 + r;
184	19396	return (y->critbit);
185		}
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	149201	hcb_insert(const struct worker wrk, struct hcb_root root,
195		const uint8_t digest, struct objhead *noh)
196		{
197		volatile uintptr_t *p;
198		uintptr_t pp;
199		struct hcb_y y, y2;
200		struct objhead *oh2;
201		unsigned s, s2;
202
203	149201	p = &root->origo;
204	149201	pp = *p;
205	149201	if (pp == 0) {
206	56526	if (noh == NULL)
207	28288	return (NULL);
208	28238	oh2 = *noh;
209	28238	*noh = NULL;
210	28238	memcpy(oh2->digest, digest, sizeof oh2->digest);
211	28238	*p = hcb_r_node(oh2);
212	28238	return (oh2);
213		}
214
215	154651	while (hcb_is_y(pp)) {
216	61976	y = hcb_l_y(pp);
217	61976	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
218	61976	assert(y->ptr < DIGEST_LEN);
219	61976	s = (digest[y->ptr] & y->bitmask) != 0;
220	61976	assert(s < 2);
221	61976	p = &y->leaf[s];
222	61976	pp = *p;
223		}
224
225	92675	if (pp == 0) {
226		/* We raced hcb_delete and got a NULL pointer */
227	0	assert(noh == NULL);
228	0	return (NULL);
229		}
230
231	92675	assert(hcb_is_node(pp));
232
233		/* We found a node, does it match ? */
234	92675	oh2 = hcb_l_node(pp);
235	92675	CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
236	92675	if (!memcmp(oh2->digest, digest, DIGEST_LEN))
237	53898	return (oh2);
238
239	38777	if (noh == NULL)
240	19381	return (NULL);
241
242		/* Insert */
243
244	19396	TAKE_OBJ_NOTNULL(y2, &wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
245	19396	(void)hcb_crit_bit(digest, oh2, y2);
246	19396	s2 = (digest[y2->ptr] & y2->bitmask) != 0;
247	19396	assert(s2 < 2);
248	19396	oh2 = *noh;
249	19396	*noh = NULL;
250	19396	memcpy(oh2->digest, digest, sizeof oh2->digest);
251	19396	y2->leaf[s2] = hcb_r_node(oh2);
252	19396	s2 = 1-s2;
253
254	19396	p = &root->origo;
255	19396	AN(*p);
256
257	33921	while (hcb_is_y(*p)) {
258	18187	y = hcb_l_y(*p);
259	18187	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
260	18187	assert(y->critbit != y2->critbit);
261	18187	if (y->critbit > y2->critbit)
262	3662	break;
263	14525	assert(y->ptr < DIGEST_LEN);
264	14525	s = (digest[y->ptr] & y->bitmask) != 0;
265	14525	assert(s < 2);
266	14525	p = &y->leaf[s];
267		}
268	19396	y2->leaf[s2] = *p;
269	19396	VWMB();
270	19396	*p = hcb_r_y(y2);
271	19396	return (oh2);
272	149201	}
273
274		/--------------------------------------------------------------------/
275
276		static void
277	7060	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	7060	if (r->origo == hcb_r_node(oh)) {
284	4638	r->origo = 0;
285	4638	return;
286		}
287	2422	p = &r->origo;
288	2422	assert(hcb_is_y(*p));
289
290	2422	y = NULL;
291	3722	while (1) {
292	3722	assert(hcb_is_y(*p));
293	3722	y = hcb_l_y(*p);
294	3722	assert(y->ptr < DIGEST_LEN);
295	3722	s = (oh->digest[y->ptr] & y->bitmask) != 0;
296	3722	assert(s < 2);
297	3722	if (y->leaf[s] == hcb_r_node(oh)) {
298	2422	*p = y->leaf[1 - s];
299	2422	VSTAILQ_INSERT_TAIL(&cool_y, y, list);
300	2422	return;
301		}
302	1300	p = &y->leaf[s];
303		}
304	7060	}
305
306		/--------------------------------------------------------------------/
307
308		static void * v_matchproto_(bgthread_t)
309	0	hcb_cleaner(struct worker wrk, void priv)
310		{
311		struct hcb_y y, y2;
312		struct objhead oh, oh2;
313
314	0	(void)priv;
315	37064	while (1) {
316	37064	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	37064	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	37064	Lck_Lock(&hcb_mtx);
327	37064	VSTAILQ_CONCAT(&dead_y, &cool_y);
328	37064	VTAILQ_CONCAT(&dead_h, &cool_h, hoh_list);
329	37064	Lck_Unlock(&hcb_mtx);
330	37064	Pool_Sumstat(wrk);
331	37064	VTIM_sleep(cache_param->critbit_cooloff);
332		}
333		NEEDLESS(return (NULL));
334		}
335
336		/--------------------------------------------------------------------/
337
338		static void v_matchproto_(hash_start_f)
339	37064	hcb_start(void)
340		{
341	37064	struct objhead *oh = NULL;
342		pthread_t tp;
343
344	37064	(void)oh;
345	37064	Lck_New(&hcb_mtx, lck_hcb);
346	37064	WRK_BgThread(&tp, "hcb-cleaner", hcb_cleaner, NULL);
347	37064	memset(&hcb_root, 0, sizeof hcb_root);
348	37064	hcb_build_bittbl();
349	37064	}
350
351		static int v_matchproto_(hash_deref_f)
352	59061	hcb_deref(struct worker wrk, struct objhead oh)
353		{
354		int r;
355
356	59061	(void)wrk;
357	59061	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
358	59061	Lck_AssertHeld(&oh->mtx);
359	59061	assert(oh->refcnt > 0);
360	59061	r = --oh->refcnt;
361	59061	if (oh->refcnt == 0) {
362	7060	Lck_Lock(&hcb_mtx);
363	7060	hcb_delete(&hcb_root, oh);
364	7060	VTAILQ_INSERT_TAIL(&cool_h, oh, hoh_list);
365	7060	Lck_Unlock(&hcb_mtx);
366	7060	}
367	59061	Lck_Unlock(&oh->mtx);
368		#ifdef PHK
369		fprintf(stderr, "hcb_defef %d %d <%s>\n", __LINE__, r, oh->hash);
370		#endif
371	59061	return (r);
372		}
373
374		static struct objhead * v_matchproto_(hash_lookup_f)
375	101537	hcb_lookup(struct worker wrk, const void digest, struct objhead **noh)
376		{
377		struct objhead *oh;
378		struct hcb_y *y;
379		unsigned u;
380
381	101537	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
382	101537	AN(digest);
383	101537	if (noh != NULL) {
384	101533	CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
385	101533	assert((*noh)->refcnt == 1);
386	101533	}
387
388		/* First try in read-only mode without holding a lock */
389
390	101537	wrk->stats->hcb_nolock++;
391	101537	oh = hcb_insert(wrk, &hcb_root, digest, NULL);
392	101537	if (oh != NULL) {
393	53861	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	53861	u = oh->refcnt;
399	53861	if (u > 0) {
400	53860	oh->refcnt++;
401	53860	return (oh);
402		}
403	1	Lck_Unlock(&oh->mtx);
404	1	}
405
406	47671	while (1) {
407		/* No luck, try with lock held, so we can modify tree */
408	47671	CAST_OBJ_NOTNULL(y, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
409	47671	Lck_Lock(&hcb_mtx);
410	47671	VSC_C_main->hcb_lock++;
411	47671	oh = hcb_insert(wrk, &hcb_root, digest, noh);
412	47671	Lck_Unlock(&hcb_mtx);
413
414	47671	if (oh == NULL)
415	0	return (NULL);
416
417	47671	Lck_Lock(&oh->mtx);
418
419	47671	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420	47671	if (noh != NULL && *noh == NULL) {
421	47634	assert(oh->refcnt > 0);
422	47634	VSC_C_main->hcb_insert++;
423	47634	return (oh);
424		}
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	37	u = oh->refcnt;
430	37	if (u > 0) {
431	37	oh->refcnt++;
432	37	return (oh);
433		}
434	0	Lck_Unlock(&oh->mtx);
435		}
436	101531	}
437
438		static void v_matchproto_(hash_prep_f)
439	103416	hcb_prep(struct worker *wrk)
440		{
441		struct hcb_y *y;
442
443	103416	if (wrk->wpriv->nhashpriv == NULL) {
444	48485	ALLOC_OBJ(y, HCB_Y_MAGIC);
445	48485	AN(y);
446	48485	wrk->wpriv->nhashpriv = y;
447	48485	}
448	103416	}
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		};