varnish-cache/bin/varnishd/hash/hash_classic.c
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2011 Varnish Software AS
4
 * All rights reserved.
5
 *
6
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
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 classic bucketed hash
30
 */
31
32
#include "config.h"
33
34
#include <stdio.h>
35
#include <stdlib.h>
36
37
#include "cache/cache_varnishd.h"
38
#include "cache/cache_objhead.h"
39
#include "common/heritage.h"
40
41
#include "hash/hash_slinger.h"
42
43
static struct VSC_lck *lck_hcl;
44
45
/*--------------------------------------------------------------------*/
46
47
struct hcl_hd {
48
        unsigned                magic;
49
#define HCL_HEAD_MAGIC          0x0f327016
50
        VTAILQ_HEAD(, objhead)  head;
51
        struct lock             mtx;
52
};
53
54
static unsigned                 hcl_nhash = 16383;
55
static struct hcl_hd            *hcl_head;
56
57
/*--------------------------------------------------------------------
58
 * The ->init method allows the management process to pass arguments
59
 */
60
61
static void v_matchproto_(hash_init_f)
62 1
hcl_init(int ac, char * const *av)
63
{
64
        int i;
65
        unsigned u;
66
67 1
        if (ac == 0)
68 0
                return;
69 1
        if (ac > 1)
70 0
                ARGV_ERR("(-hclassic) too many arguments\n");
71 1
        i = sscanf(av[0], "%u", &u);
72 1
        if (i <= 0 || u == 0)
73 0
                return;
74 1
        if (u > 2 && !(u & (u - 1))) {
75 0
                fprintf(stderr,
76
                    "NOTE:\n"
77
                    "\tA power of two number of hash buckets is "
78
                    "marginally less efficient\n"
79
                    "\twith systematic URLs.  Reducing by one"
80
                    " hash bucket.\n");
81 0
                u--;
82
        }
83 1
        hcl_nhash = u;
84 1
        fprintf(stderr, "Classic hash: %u buckets\n", hcl_nhash);
85
}
86
87
/*--------------------------------------------------------------------
88
 * The ->start method is called during cache process start and allows
89
 * initialization to happen before the first lookup.
90
 */
91
92
static void v_matchproto_(hash_start_f)
93 1
hcl_start(void)
94
{
95
        unsigned u;
96
97 1
        lck_hcl = Lck_CreateClass("hcl");
98 1
        hcl_head = calloc(hcl_nhash, sizeof *hcl_head);
99 1
        XXXAN(hcl_head);
100
101 12
        for (u = 0; u < hcl_nhash; u++) {
102 11
                VTAILQ_INIT(&hcl_head[u].head);
103 11
                Lck_New(&hcl_head[u].mtx, lck_hcl);
104 11
                hcl_head[u].magic = HCL_HEAD_MAGIC;
105
        }
106 1
}
107
108
/*--------------------------------------------------------------------
109
 * Lookup and possibly insert element.
110
 * If nobj != NULL and the lookup does not find key, nobj is inserted.
111
 * If nobj == NULL and the lookup does not find key, NULL is returned.
112
 * A reference to the returned object is held.
113
 * We use a two-pass algorithm to handle inserts as they are quite
114
 * rare and collisions even rarer.
115
 */
116
117
static struct objhead * v_matchproto_(hash_lookup_f)
118 4
hcl_lookup(struct worker *wrk, const void *digest, struct objhead **noh)
119
{
120
        struct objhead *oh;
121
        struct hcl_hd *hp;
122
        unsigned u1, hdigest;
123
        int i;
124
125 4
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
126 4
        AN(digest);
127 4
        if (noh != NULL)
128 4
                CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
129
130
        assert(sizeof oh->digest >= sizeof hdigest);
131 4
        memcpy(&hdigest, digest, sizeof hdigest);
132 4
        u1 = hdigest % hcl_nhash;
133 4
        hp = &hcl_head[u1];
134
135 4
        Lck_Lock(&hp->mtx);
136 8
        VTAILQ_FOREACH(oh, &hp->head, hoh_list) {
137 2
                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
138 2
                i = memcmp(oh->digest, digest, sizeof oh->digest);
139 2
                if (i < 0)
140 0
                        continue;
141 2
                if (i > 0)
142 0
                        break;
143 2
                oh->refcnt++;
144 2
                Lck_Unlock(&hp->mtx);
145 2
                Lck_Lock(&oh->mtx);
146 2
                return (oh);
147
        }
148
149 2
        if (noh == NULL) {
150 0
                Lck_Unlock(&hp->mtx);
151 0
                return (NULL);
152
        }
153
154 2
        if (oh != NULL)
155 0
                VTAILQ_INSERT_BEFORE(oh, *noh, hoh_list);
156
        else
157 2
                VTAILQ_INSERT_TAIL(&hp->head, *noh, hoh_list);
158
159 2
        oh = *noh;
160 2
        *noh = NULL;
161 2
        memcpy(oh->digest, digest, sizeof oh->digest);
162
163 2
        oh->hoh_head = hp;
164
165 2
        Lck_Unlock(&hp->mtx);
166 2
        Lck_Lock(&oh->mtx);
167 2
        return (oh);
168
}
169
170
/*--------------------------------------------------------------------
171
 * Dereference and if no references are left, free.
172
 */
173
174
static int v_matchproto_(hash_deref_f)
175 2
hcl_deref(struct objhead *oh)
176
{
177
        struct hcl_hd *hp;
178
        int ret;
179
180 2
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
181 2
        CAST_OBJ_NOTNULL(hp, oh->hoh_head, HCL_HEAD_MAGIC);
182 2
        assert(oh->refcnt > 0);
183 2
        Lck_Lock(&hp->mtx);
184 2
        if (--oh->refcnt == 0) {
185 0
                VTAILQ_REMOVE(&hp->head, oh, hoh_list);
186 0
                ret = 0;
187
        } else
188 2
                ret = 1;
189 2
        Lck_Unlock(&hp->mtx);
190 2
        return (ret);
191
}
192
193
/*--------------------------------------------------------------------*/
194
195
const struct hash_slinger hcl_slinger = {
196
        .magic  =       SLINGER_MAGIC,
197
        .name   =       "classic",
198
        .init   =       hcl_init,
199
        .start  =       hcl_start,
200
        .lookup =       hcl_lookup,
201
        .deref  =       hcl_deref,
202
};