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	168617	hcb_bits(unsigned char x, unsigned char y)
60		{
61	168617	return (hcb_bittbl[x ^ y]);
62		}
63
64		static void
65	37306	hcb_build_bittbl(void)
66		{
67		unsigned char x;
68		unsigned y;
69
70	37306	y = 0;
71	335754	for (x = 0; x < 8; x++)
72	5073616	for (; y < (1U << x); y++)
73	5073616	hcb_bittbl[y] = 8 - x;
74
75		/* Quick asserts for sanity check */
76	37306	assert(hcb_bits(0x34, 0x34) == 8);
77	37306	AZ(hcb_bits(0xaa, 0x55));
78	37306	assert(hcb_bits(0x01, 0x22) == 2);
79	37306	assert(hcb_bits(0x10, 0x0b) == 3);
80	37306	}
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	92756	hcb_is_node(uintptr_t u)
120		{
121
122	92756	return (u & HCB_BIT_NODE);
123		}
124
125		static int
126	194817	hcb_is_y(uintptr_t u)
127		{
128
129	194817	return (u & HCB_BIT_Y);
130		}
131
132		static uintptr_t
133	58693	hcb_r_node(const struct objhead *n)
134		{
135
136	58693	AZ((uintptr_t)n & (HCB_BIT_NODE \| HCB_BIT_Y));
137	58693	return (HCB_BIT_NODE \| (uintptr_t)n);
138		}
139
140		static struct objhead *
141	92757	hcb_l_node(uintptr_t u)
142		{
143
144	92757	assert(u & HCB_BIT_NODE);
145	92757	AZ(u & HCB_BIT_Y);
146	92757	return ((struct objhead *)(u & ~HCB_BIT_NODE));
147		}
148
149		static uintptr_t
150	19393	hcb_r_y(const struct hcb_y *y)
151		{
152
153	19393	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
154	19393	AZ((uintptr_t)y & (HCB_BIT_NODE \| HCB_BIT_Y));
155	19393	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	19393	hcb_crit_bit(const uint8_t digest, const struct objhead oh2, struct hcb_y *y)
173		{
174		unsigned char u, r;
175
176	19393	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
177	24993	for (u = 0; u < DIGEST_LEN && digest[u] == oh2->digest[u]; u++)
178		;
179	19393	assert(u < DIGEST_LEN);
180	19393	r = hcb_bits(digest[u], oh2->digest[u]);
181	19393	y->ptr = u;
182	19393	y->bitmask = 0x80 >> r;
183	19393	y->critbit = u * 8 + r;
184	19393	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	149641	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	149641	p = &root->origo;
204	149641	pp = *p;
205	149641	if (pp == 0) {
206	56882	if (noh == NULL)
207	28472	return (NULL);
208	28410	oh2 = *noh;
209	28410	*noh = NULL;
210	28410	memcpy(oh2->digest, digest, sizeof oh2->digest);
211	28410	*p = hcb_r_node(oh2);
212	28410	return (oh2);
213		}
214
215	154730	while (hcb_is_y(pp)) {
216	61971	y = hcb_l_y(pp);
217	61971	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
218	61971	assert(y->ptr < DIGEST_LEN);
219	61971	s = (digest[y->ptr] & y->bitmask) != 0;
220	61971	assert(s < 2);
221	61971	p = &y->leaf[s];
222	61971	pp = *p;
223		}
224
225	92759	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	92759	assert(hcb_is_node(pp));
232
233		/* We found a node, does it match ? */
234	92759	oh2 = hcb_l_node(pp);
235	92759	CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
236	92759	if (!memcmp(oh2->digest, digest, DIGEST_LEN))
237	53980	return (oh2);
238
239	38779	if (noh == NULL)
240	19386	return (NULL);
241
242		/* Insert */
243
244	19393	TAKE_OBJ_NOTNULL(y2, &wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
245	19393	(void)hcb_crit_bit(digest, oh2, y2);
246	19393	s2 = (digest[y2->ptr] & y2->bitmask) != 0;
247	19393	assert(s2 < 2);
248	19393	oh2 = *noh;
249	19393	*noh = NULL;
250	19393	memcpy(oh2->digest, digest, sizeof oh2->digest);
251	19393	y2->leaf[s2] = hcb_r_node(oh2);
252	19393	s2 = 1-s2;
253
254	19393	p = &root->origo;
255	19393	AN(*p);
256
257	33930	while (hcb_is_y(*p)) {
258	18185	y = hcb_l_y(*p);
259	18185	CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
260	18185	assert(y->critbit != y2->critbit);
261	18185	if (y->critbit > y2->critbit)
262	3648	break;
263	14537	assert(y->ptr < DIGEST_LEN);
264	14537	s = (digest[y->ptr] & y->bitmask) != 0;
265	14537	assert(s < 2);
266	14537	p = &y->leaf[s];
267		}
268	19393	y2->leaf[s2] = *p;
269	19393	VWMB();
270	19393	*p = hcb_r_y(y2);
271	19393	return (oh2);
272	149641	}
273
274		/--------------------------------------------------------------------/
275
276		static void
277	7159	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	7159	if (r->origo == hcb_r_node(oh)) {
284	4730	r->origo = 0;
285	4730	return;
286		}
287	2429	p = &r->origo;
288	2429	assert(hcb_is_y(*p));
289
290	2429	y = NULL;
291	3731	while (1) {
292	3731	assert(hcb_is_y(*p));
293	3731	y = hcb_l_y(*p);
294	3731	assert(y->ptr < DIGEST_LEN);
295	3731	s = (oh->digest[y->ptr] & y->bitmask) != 0;
296	3731	assert(s < 2);
297	3731	if (y->leaf[s] == hcb_r_node(oh)) {
298	2429	*p = y->leaf[1 - s];
299	2429	VSTAILQ_INSERT_TAIL(&cool_y, y, list);
300	2429	return;
301		}
302	1302	p = &y->leaf[s];
303		}
304	7159	}
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	37306	while (1) {
316	37306	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	37306	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	37306	Lck_Lock(&hcb_mtx);
327	37306	VSTAILQ_CONCAT(&dead_y, &cool_y);
328	37306	VTAILQ_CONCAT(&dead_h, &cool_h, hoh_list);
329	37306	Lck_Unlock(&hcb_mtx);
330	37306	Pool_Sumstat(wrk);
331	37306	VTIM_sleep(cache_param->critbit_cooloff);
332		}
333		NEEDLESS(return (NULL));
334		}
335
336		/--------------------------------------------------------------------/
337
338		static void v_matchproto_(hash_start_f)
339	37306	hcb_start(void)
340		{
341	37306	struct objhead *oh = NULL;
342		pthread_t tp;
343
344	37306	(void)oh;
345	37306	Lck_New(&hcb_mtx, lck_hcb);
346	37306	WRK_BgThread(&tp, "hcb-cleaner", hcb_cleaner, NULL);
347	37306	memset(&hcb_root, 0, sizeof hcb_root);
348	37306	hcb_build_bittbl();
349	37306	}
350
351		static int v_matchproto_(hash_deref_f)
352	59236	hcb_deref(struct worker wrk, struct objhead oh)
353		{
354		int r;
355
356	59236	(void)wrk;
357	59236	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
358	59236	Lck_AssertHeld(&oh->mtx);
359	59236	assert(oh->refcnt > 0);
360	59236	r = --oh->refcnt;
361	59236	if (oh->refcnt == 0) {
362	7159	Lck_Lock(&hcb_mtx);
363	7159	hcb_delete(&hcb_root, oh);
364	7159	VTAILQ_INSERT_TAIL(&cool_h, oh, hoh_list);
365	7159	Lck_Unlock(&hcb_mtx);
366	7159	}
367	59236	Lck_Unlock(&oh->mtx);
368		#ifdef PHK
369		fprintf(stderr, "hcb_defef %d %d <%s>\n", __LINE__, r, oh->hash);
370		#endif
371	59236	return (r);
372		}
373
374		static struct objhead * v_matchproto_(hash_lookup_f)
375	101785	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	101785	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
382	101785	AN(digest);
383	101785	if (noh != NULL) {
384	101779	CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
385	101779	assert((*noh)->refcnt == 1);
386	101779	}
387
388		/* First try in read-only mode without holding a lock */
389
390	101785	wrk->stats->hcb_nolock++;
391	101785	oh = hcb_insert(wrk, &hcb_root, digest, NULL);
392	101785	if (oh != NULL) {
393	53919	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	53919	u = oh->refcnt;
399	53919	if (u > 0) {
400	53917	oh->refcnt++;
401	53917	return (oh);
402		}
403	2	Lck_Unlock(&oh->mtx);
404	2	}
405
406	47864	while (1) {
407		/* No luck, try with lock held, so we can modify tree */
408	47864	CAST_OBJ_NOTNULL(y, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
409	47864	Lck_Lock(&hcb_mtx);
410	47864	VSC_C_main->hcb_lock++;
411	47864	oh = hcb_insert(wrk, &hcb_root, digest, noh);
412	47864	Lck_Unlock(&hcb_mtx);
413
414	47864	if (oh == NULL)
415	0	return (NULL);
416
417	47864	Lck_Lock(&oh->mtx);
418
419	47864	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420	47864	if (noh != NULL && *noh == NULL) {
421	47803	assert(oh->refcnt > 0);
422	47803	VSC_C_main->hcb_insert++;
423	47803	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	61	u = oh->refcnt;
430	61	if (u > 0) {
431	61	oh->refcnt++;
432	61	return (oh);
433		}
434	0	Lck_Unlock(&oh->mtx);
435		}
436	101781	}
437
438		static void v_matchproto_(hash_prep_f)
439	103673	hcb_prep(struct worker *wrk)
440		{
441		struct hcb_y *y;
442
443	103673	if (wrk->wpriv->nhashpriv == NULL) {
444	48594	ALLOC_OBJ(y, HCB_Y_MAGIC);
445	48594	AN(y);
446	48594	wrk->wpriv->nhashpriv = y;
447	48594	}
448	103673	}
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		};