varnish-cache/bin/varnishd/hash/hash_simple_list.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
 * This is the reference hash(/lookup) implementation
30
 */
31
32
#include "config.h"
33
34
#include "cache/cache_varnishd.h"
35
#include "cache/cache_objhead.h"
36
37
#include "hash/hash_slinger.h"
38
39
static struct VSC_lck *lck_hsl;
40
41
/*--------------------------------------------------------------------*/
42
43
static VTAILQ_HEAD(, objhead)   hsl_head = VTAILQ_HEAD_INITIALIZER(hsl_head);
44
static struct lock hsl_mtx;
45
46
/*--------------------------------------------------------------------
47
 * The ->init method is called during process start and allows
48
 * initialization to happen before the first lookup.
49
 */
50
51
static void v_matchproto_(hash_start_f)
52 1
hsl_start(void)
53
{
54
55 1
        lck_hsl = Lck_CreateClass("hsl");
56 1
        Lck_New(&hsl_mtx, lck_hsl);
57 1
}
58
59
/*--------------------------------------------------------------------
60
 * Lookup and possibly insert element.
61
 * If nobj != NULL and the lookup does not find key, nobj is inserted.
62
 * If nobj == NULL and the lookup does not find key, NULL is returned.
63
 * A reference to the returned object is held.
64
 */
65
66
static struct objhead * v_matchproto_(hash_lookup_f)
67 2
hsl_lookup(struct worker *wrk, const void *digest, struct objhead **noh)
68
{
69
        struct objhead *oh;
70
        int i;
71
72 2
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
73 2
        AN(digest);
74 2
        if (noh != NULL)
75 2
                CHECK_OBJ_NOTNULL(*noh, OBJHEAD_MAGIC);
76
77 2
        Lck_Lock(&hsl_mtx);
78 4
        VTAILQ_FOREACH(oh, &hsl_head, hoh_list) {
79 1
                i = memcmp(oh->digest, digest, sizeof oh->digest);
80 1
                if (i < 0)
81 0
                        continue;
82 1
                if (i > 0)
83 0
                        break;
84 1
                oh->refcnt++;
85 1
                Lck_Unlock(&hsl_mtx);
86 1
                Lck_Lock(&oh->mtx);
87 1
                return (oh);
88
        }
89
90 1
        if (noh == NULL)
91 0
                return (NULL);
92
93 1
        if (oh != NULL)
94 0
                VTAILQ_INSERT_BEFORE(oh, *noh, hoh_list);
95
        else
96 1
                VTAILQ_INSERT_TAIL(&hsl_head, *noh, hoh_list);
97
98 1
        oh = *noh;
99 1
        *noh = NULL;
100 1
        memcpy(oh->digest, digest, sizeof oh->digest);
101 1
        Lck_Unlock(&hsl_mtx);
102 1
        Lck_Lock(&oh->mtx);
103 1
        return (oh);
104
}
105
106
/*--------------------------------------------------------------------
107
 * Dereference and if no references are left, free.
108
 */
109
110
static int v_matchproto_(hash_deref_f)
111 1
hsl_deref(struct objhead *oh)
112
{
113
        int ret;
114
115 1
        Lck_Lock(&hsl_mtx);
116 1
        if (--oh->refcnt == 0) {
117 0
                VTAILQ_REMOVE(&hsl_head, oh, hoh_list);
118 0
                ret = 0;
119
        } else
120 1
                ret = 1;
121 1
        Lck_Unlock(&hsl_mtx);
122 1
        return (ret);
123
}
124
125
/*--------------------------------------------------------------------*/
126
127
const struct hash_slinger hsl_slinger = {
128
        .magic  =       SLINGER_MAGIC,
129
        .name   =       "simple",
130
        .start  =       hsl_start,
131
        .lookup =       hsl_lookup,
132
        .deref  =       hsl_deref,
133
};