source: bin/varnishd/cache_hash.c @ fe7a68

Revision fe7a68, 9.1 KB checked in by Dag Erling Smørgrav <des@…>, 6 years ago (diff)

Update copyright; also convert a couple of files from ISO-8859-1 to UTF-8.

git-svn-id:  http://www.varnish-cache.org/svn/trunk/varnish-cache@2415 d4fa192b-c00b-0410-8231-f00ffab90ce4

  • Property mode set to 100644
Line 
1/*-
2 * Copyright (c) 2006 Verdens Gang AS
3 * Copyright (c) 2006-2008 Linpro 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 * $Id$
30 *
31 * This is the central hash-table code, it relies on a chosen hash
32 * implementation only for the actual hashing, all the housekeeping
33 * happens here.
34 *
35 * We have two kinds of structures, objecthead and object.  An objecthead
36 * corresponds to a given (Host:, URL) tupple, and the objects hung from
37 * the objecthead may represent various variations (ie: Vary: header,
38 * different TTL etc) instances of that web-entity.
39 *
40 * Each objecthead has a mutex which locks both its own fields, the
41 * list of objects and fields in the objects.
42 *
43 * The hash implementation must supply a reference count facility on
44 * the objecthead, and return with a reference held after a lookup.
45 *
46 * Lookups in the hash implementation returns with a ref held and each
47 * object hung from the objhead holds a ref as well.
48 *
49 * Objects have refcounts which are locked by the objecthead mutex.
50 *
51 * New objects are always marked busy, and they can go from busy to
52 * not busy only once.
53 */
54
55#include <stdio.h>
56#include <stdlib.h>
57#include <string.h>
58#include <sys/types.h>
59#include <fcntl.h>
60
61#include "shmlog.h"
62#include "cache.h"
63#include "heritage.h"
64#include "stevedore.h"
65
66static struct hash_slinger      *hash;
67
68/* Precreate an objhead and object for later use */
69void
70HSH_Prealloc(struct sess *sp)
71{
72        struct worker *w;
73        struct storage *st;
74
75        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
76        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
77        w = sp->wrk;
78
79        if (w->nobjhead == NULL) {
80                w->nobjhead = calloc(sizeof *w->nobjhead, 1);
81                XXXAN(w->nobjhead);
82                w->nobjhead->magic = OBJHEAD_MAGIC;
83                VTAILQ_INIT(&w->nobjhead->objects);
84                VTAILQ_INIT(&w->nobjhead->waitinglist);
85                MTX_INIT(&w->nobjhead->mtx);
86                VSL_stats->n_objecthead++;
87        } else
88                CHECK_OBJ_NOTNULL(w->nobjhead, OBJHEAD_MAGIC);
89        if (w->nobj == NULL) {
90                st = STV_alloc(sp, params->mem_workspace);
91                XXXAN(st);
92                assert(st->space > sizeof *w->nobj);
93                w->nobj = (void *)st->ptr; /* XXX: align ? */
94                st->len = sizeof *w->nobj;
95                memset(w->nobj, 0, sizeof *w->nobj);
96                w->nobj->objstore = st;
97                w->nobj->magic = OBJECT_MAGIC;
98                w->nobj->http->magic = HTTP_MAGIC;
99                w->nobj->busy = 1;
100                w->nobj->refcnt = 1;
101                VTAILQ_INIT(&w->nobj->store);
102                VTAILQ_INIT(&w->nobj->esibits);
103                VSL_stats->n_object++;
104        } else
105                CHECK_OBJ_NOTNULL(w->nobj, OBJECT_MAGIC);
106}
107
108static void
109HSH_Freestore(struct object *o)
110{
111        struct storage *st, *stn;
112
113        VTAILQ_FOREACH_SAFE(st, &o->store, list, stn) {
114                CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
115                VTAILQ_REMOVE(&o->store, st, list);
116                STV_free(st);
117        }
118}
119
120int
121HSH_Compare(const struct sess *sp, const struct objhead *obj)
122{
123        int i;
124        unsigned u, v;
125        const char *b;
126
127        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
128        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
129        CHECK_OBJ_NOTNULL(obj, OBJHEAD_MAGIC);
130        i = sp->lhashptr - obj->hashlen;
131        if (i)
132                return (i);
133        b = obj->hash;
134        for (u = 0; u < sp->ihashptr; u += 2) {
135                v = pdiff(sp->hashptr[u], sp->hashptr[u + 1]);
136                i = memcmp(sp->hashptr[u], b, v);
137                if (i)
138                        return (i);
139                b += v;
140                i = '#' - *b++;
141                if (i)
142                        return (i);
143        }
144        assert(*b == '\0');
145        b++;
146        assert(b == obj->hash + obj->hashlen);
147        WSP(sp, SLT_Debug, "Hash Match: %s", obj->hash);
148        return (0);
149}
150
151void
152HSH_Copy(const struct sess *sp, const struct objhead *obj)
153{
154        unsigned u, v;
155        char *b;
156
157        assert(obj->hashlen >= sp->lhashptr);
158        b = obj->hash;
159        for (u = 0; u < sp->ihashptr; u += 2) {
160                v = pdiff(sp->hashptr[u], sp->hashptr[u + 1]);
161                memcpy(b, sp->hashptr[u], v);
162                b += v;
163                *b++ = '#';
164        }
165        *b++ = '\0';
166        WSP(sp, SLT_Debug, "Hash: %s", obj->hash);
167        assert(b <= obj->hash + obj->hashlen);
168}
169
170struct object *
171HSH_Lookup(struct sess *sp)
172{
173        struct worker *w;
174        struct http *h;
175        struct objhead *oh;
176        struct object *o, *busy_o, *grace_o;
177
178        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
179        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
180        CHECK_OBJ_NOTNULL(sp->http, HTTP_MAGIC);
181        AN(hash);
182        w = sp->wrk;
183        h = sp->http;
184
185        HSH_Prealloc(sp);
186        if (sp->objhead != NULL) {
187                CHECK_OBJ_NOTNULL(sp->objhead, OBJHEAD_MAGIC);
188                oh = sp->objhead;
189                sp->objhead = NULL;
190                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
191                LOCK(&oh->mtx);
192        } else {
193                oh = hash->lookup(sp, w->nobjhead);
194                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
195                if (oh == w->nobjhead)
196                        w->nobjhead = NULL;
197                LOCK(&oh->mtx);
198        }
199
200        busy_o = NULL;
201        grace_o = NULL;
202        VTAILQ_FOREACH(o, &oh->objects, list) {
203                if (o->busy) {
204                        busy_o = o;
205                        continue;
206                }
207                if (!o->cacheable)
208                        continue;
209                if (o->ttl == 0) 
210                        continue;
211                if (BAN_CheckObject(o, h->hd[HTTP_HDR_URL].b, oh->hash)) {
212                        o->ttl = 0;
213                        WSP(sp, SLT_ExpBan, "%u was banned", o->xid);
214                        if (o->timer_idx != 0)
215                                EXP_TTLchange(o);
216                        continue;
217                }
218                if (o->vary != NULL && !VRY_Match(sp, o->vary))
219                        continue;
220
221                /* If still valid, use it */
222                if (o->ttl >= sp->t_req)
223                        break;
224
225                /* Remember any matching objects inside their grace period */
226                if (o->ttl + o->grace >= sp->t_req)
227                        grace_o = o;
228        }
229
230        /*
231         * If we have a object in grace and being fetched,
232         * use it, if req.grace is also satisified.
233         */
234        if (o == NULL && grace_o != NULL &&
235            grace_o->child != NULL &&
236            grace_o->ttl + sp->grace >= sp->t_req)
237                o = grace_o;
238
239        if (o != NULL) {
240                /* We found an object we like */
241                o->refcnt++;
242                UNLOCK(&oh->mtx);
243                (void)hash->deref(oh);
244                return (o);
245        }
246
247        if (busy_o != NULL) {
248                /* There are one or more busy objects, wait for them */
249                VTAILQ_INSERT_TAIL(&oh->waitinglist, sp, list);
250                sp->objhead = oh;
251                UNLOCK(&oh->mtx);
252                return (NULL);
253        }
254
255        /* Insert (precreated) object in objecthead */
256        o = w->nobj;
257        w->nobj = NULL;
258        o->objhead = oh;
259        /* XXX: Should this not be ..._HEAD now ? */
260        VTAILQ_INSERT_TAIL(&oh->objects, o, list);
261        /* NB: do not deref objhead the new object inherits our reference */
262        if (grace_o != NULL) {
263                grace_o->child = o;
264                o->parent = grace_o;
265                grace_o->refcnt++;
266        }
267        UNLOCK(&oh->mtx);
268        BAN_NewObj(o);
269        /*
270         * It's cheaper to copy the timestamp here, than to get a new one
271         * in EXP_Insert().
272         */
273        o->lru_stamp = w->used;
274        return (o);
275}
276
277static void
278hsh_rush(struct objhead *oh)
279{
280        unsigned u;
281        struct sess *sp;
282
283        for (u = 0; u < params->rush_exponent; u++) {
284                sp = VTAILQ_FIRST(&oh->waitinglist);
285                if (sp == NULL)
286                        return;
287                VTAILQ_REMOVE(&oh->waitinglist, sp, list);
288                VSL(SLT_Debug, sp->id, "of waiting list");
289                WRK_QueueSession(sp);
290        }
291}
292
293void
294HSH_Unbusy(struct object *o)
295{
296        struct objhead *oh;
297        struct object *parent;
298
299        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
300        assert(o->busy);
301        assert(o->refcnt > 0);
302        if (o->cacheable)
303                EXP_Insert(o);
304        oh = o->objhead;
305        if (oh != NULL) {
306                CHECK_OBJ(oh, OBJHEAD_MAGIC);
307                LOCK(&oh->mtx);
308        }
309        o->busy = 0;
310        if (oh != NULL)
311                hsh_rush(oh);
312        parent = o->parent;
313        o->parent = NULL;
314        if (parent != NULL)
315                parent->child = NULL;
316        if (oh != NULL)
317                UNLOCK(&oh->mtx);
318        if (parent != NULL)
319                HSH_Deref(parent);
320}
321
322void
323HSH_Ref(struct object *o)
324{
325        struct objhead *oh;
326
327        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
328        oh = o->objhead;
329        if (oh != NULL) {
330                CHECK_OBJ(oh, OBJHEAD_MAGIC);
331                LOCK(&oh->mtx);
332        }
333        assert(o->refcnt > 0);
334        o->refcnt++;
335        if (oh != NULL)
336                UNLOCK(&oh->mtx);
337}
338
339void
340HSH_Deref(struct object *o)
341{
342        struct objhead *oh;
343        unsigned r;
344
345        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
346        oh = o->objhead;
347        if (oh != NULL) {
348                CHECK_OBJ(oh, OBJHEAD_MAGIC);
349
350                /* drop ref on object */
351                LOCK(&oh->mtx);
352        }
353        assert(o->refcnt > 0);
354        r = --o->refcnt;
355        if (oh != NULL)
356                hsh_rush(oh);
357        if (oh != NULL) {
358                if (!r)
359                        VTAILQ_REMOVE(&oh->objects, o, list);
360                UNLOCK(&oh->mtx);
361        }
362
363        /* If still referenced, done */
364        if (r != 0)
365                return;
366
367        if (o->vary != NULL)
368                free(o->vary);
369
370        ESI_Destroy(o);
371        HSH_Freestore(o);
372        STV_free(o->objstore);
373        VSL_stats->n_object--;
374
375        if (oh == NULL)
376                return;
377        /* Drop our ref on the objhead */
378        if (hash->deref(oh))
379                return;
380        assert(VTAILQ_EMPTY(&oh->objects));
381        MTX_DESTROY(&oh->mtx);
382        VSL_stats->n_objecthead--;
383        FREE_OBJ(oh);
384}
385
386void
387HSH_Init(void)
388{
389
390        hash = heritage.hash;
391        if (hash->start != NULL)
392                hash->start();
393}
Note: See TracBrowser for help on using the repository browser.