source: bin/varnishd/cache_hash.c @ a7ed1d7

Revision a7ed1d7, 9.8 KB checked in by Poul-Henning Kamp <phk@…>, 6 years ago (diff)

Add obj.hits VRT variable which counts how many *previous* hits
this object has seen.

Idea for prefetching being used as workaround for #310

git-svn-id:  http://www.varnish-cache.org/svn/trunk/varnish-cache@3166 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 "config.h"
56
57#include <stdio.h>
58#include <stdlib.h>
59#include <math.h>
60#include <string.h>
61#include <limits.h>
62#include <sys/types.h>
63#include <fcntl.h>
64
65#include "shmlog.h"
66#include "cache.h"
67#include "stevedore.h"
68
69static struct hash_slinger      *hash;
70
71double
72HSH_Grace(double g)
73{
74        if (isnan(g))
75                return (double)(params->default_grace);
76        return (g);
77}
78
79/* Precreate an objhead and object for later use */
80void
81HSH_Prealloc(struct sess *sp)
82{
83        struct worker *w;
84        struct storage *st;
85
86        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
87        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
88        w = sp->wrk;
89
90        if (w->nobjhead == NULL) {
91                w->nobjhead = calloc(sizeof *w->nobjhead, 1);
92                XXXAN(w->nobjhead);
93                w->nobjhead->magic = OBJHEAD_MAGIC;
94                VTAILQ_INIT(&w->nobjhead->objects);
95                VTAILQ_INIT(&w->nobjhead->waitinglist);
96                MTX_INIT(&w->nobjhead->mtx);
97                VSL_stats->n_objecthead++;
98        } else
99                CHECK_OBJ_NOTNULL(w->nobjhead, OBJHEAD_MAGIC);
100        if (w->nobj == NULL) {
101                st = STV_alloc(sp, params->obj_workspace);
102                XXXAN(st);
103                assert(st->space > sizeof *w->nobj);
104                w->nobj = (void *)st->ptr; /* XXX: align ? */
105                st->len = sizeof *w->nobj;
106                memset(w->nobj, 0, sizeof *w->nobj);
107                w->nobj->objstore = st;
108                WS_Init(w->nobj->ws_o, "obj",
109                    st->ptr + st->len, st->space - st->len);
110                st->len = st->space;
111                WS_Assert(w->nobj->ws_o);
112                http_Setup(w->nobj->http, w->nobj->ws_o);
113                w->nobj->magic = OBJECT_MAGIC;
114                w->nobj->http->magic = HTTP_MAGIC;
115                w->nobj->busy = 1;
116                w->nobj->refcnt = 1;
117                w->nobj->grace = NAN;
118                VTAILQ_INIT(&w->nobj->store);
119                VTAILQ_INIT(&w->nobj->esibits);
120                VSL_stats->n_object++;
121               
122        } else
123                CHECK_OBJ_NOTNULL(w->nobj, OBJECT_MAGIC);
124}
125
126void
127HSH_Freestore(struct object *o)
128{
129        struct storage *st, *stn;
130
131        VTAILQ_FOREACH_SAFE(st, &o->store, list, stn) {
132                CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
133                VTAILQ_REMOVE(&o->store, st, list);
134                STV_free(st);
135        }
136}
137
138int
139HSH_Compare(const struct sess *sp, const struct objhead *obj)
140{
141        int i;
142        unsigned u, v;
143        const char *b;
144
145        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
146        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
147        CHECK_OBJ_NOTNULL(obj, OBJHEAD_MAGIC);
148        i = sp->lhashptr - obj->hashlen;
149        if (i)
150                return (i);
151        b = obj->hash;
152        for (u = 0; u < sp->ihashptr; u += 2) {
153                v = pdiff(sp->hashptr[u], sp->hashptr[u + 1]);
154                i = memcmp(sp->hashptr[u], b, v);
155                if (i)
156                        return (i);
157                b += v;
158                i = '#' - *b++;
159                if (i)
160                        return (i);
161        }
162        assert(*b == '\0');
163        b++;
164        assert(b == obj->hash + obj->hashlen);
165        return (0);
166}
167
168void
169HSH_Copy(const struct sess *sp, const struct objhead *obj)
170{
171        unsigned u, v;
172        char *b;
173
174        assert(obj->hashlen >= sp->lhashptr);
175        b = obj->hash;
176        for (u = 0; u < sp->ihashptr; u += 2) {
177                v = pdiff(sp->hashptr[u], sp->hashptr[u + 1]);
178                memcpy(b, sp->hashptr[u], v);
179                b += v;
180                *b++ = '#';
181        }
182        *b++ = '\0';
183        assert(b <= obj->hash + obj->hashlen);
184}
185
186struct object *
187HSH_Lookup(struct sess *sp)
188{
189        struct worker *w;
190        struct http *h;
191        struct objhead *oh;
192        struct object *o, *busy_o, *grace_o;
193
194        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
195        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
196        CHECK_OBJ_NOTNULL(sp->http, HTTP_MAGIC);
197        AN(hash);
198        w = sp->wrk;
199        h = sp->http;
200
201        HSH_Prealloc(sp);
202        if (sp->objhead != NULL) {
203                CHECK_OBJ_NOTNULL(sp->objhead, OBJHEAD_MAGIC);
204                oh = sp->objhead;
205                sp->objhead = NULL;
206                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
207                LOCK(&oh->mtx);
208        } else {
209                oh = hash->lookup(sp, w->nobjhead);
210                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
211                if (oh == w->nobjhead)
212                        w->nobjhead = NULL;
213                LOCK(&oh->mtx);
214        }
215
216        busy_o = NULL;
217        grace_o = NULL;
218        VTAILQ_FOREACH(o, &oh->objects, list) {
219                if (o->busy) {
220                        busy_o = o;
221                        continue;
222                }
223                if (!o->cacheable)
224                        continue;
225                if (o->ttl == 0) 
226                        continue;
227                if (BAN_CheckObject(o, h->hd[HTTP_HDR_URL].b, oh->hash)) {
228                        o->ttl = 0;
229                        WSP(sp, SLT_ExpBan, "%u was banned", o->xid);
230                        EXP_Rearm(o);
231                        continue;
232                }
233                if (o->vary != NULL && !VRY_Match(sp, o->vary))
234                        continue;
235
236                /* If still valid, use it */
237                if (o->ttl >= sp->t_req)
238                        break;
239
240                /* Remember any matching objects inside their grace period */
241                if (o->ttl + HSH_Grace(o->grace) >= sp->t_req)
242                        grace_o = o;
243        }
244
245        /*
246         * If we have a object in grace and being fetched,
247         * use it, if req.grace is also satisified.
248         */
249        if (o == NULL && grace_o != NULL &&
250            grace_o->child != NULL &&
251            grace_o->ttl + HSH_Grace(sp->grace) >= sp->t_req)
252                o = grace_o;
253
254        if (o != NULL) {
255                /* We found an object we like */
256                o->refcnt++;
257                if (o->hits < INT_MAX)
258                        o->hits++;
259                UNLOCK(&oh->mtx);
260                if (params->log_hash)
261                        WSP(sp, SLT_Hash, "%s", oh->hash);
262                (void)hash->deref(oh);
263                return (o);
264        }
265
266        if (busy_o != NULL) {
267                /* There are one or more busy objects, wait for them */
268                VTAILQ_INSERT_TAIL(&oh->waitinglist, sp, list);
269                sp->objhead = oh;
270                UNLOCK(&oh->mtx);
271                return (NULL);
272        }
273
274        /* Insert (precreated) object in objecthead */
275        o = w->nobj;
276        w->nobj = NULL;
277        o->objhead = oh;
278        /* XXX: Should this not be ..._HEAD now ? */
279        VTAILQ_INSERT_TAIL(&oh->objects, o, list);
280        /* NB: do not deref objhead the new object inherits our reference */
281        if (grace_o != NULL) {
282                grace_o->child = o;
283                o->parent = grace_o;
284                grace_o->refcnt++;
285        }
286        UNLOCK(&oh->mtx);
287        if (params->log_hash)
288                WSP(sp, SLT_Hash, "%s", oh->hash);
289        /*
290         * XXX: This may be too early, relative to pass objects.
291         * XXX: possibly move to when we commit to have it in the cache.
292         */
293        BAN_NewObj(o);
294        return (o);
295}
296
297static void
298hsh_rush(struct objhead *oh)
299{
300        unsigned u;
301        struct sess *sp;
302
303        for (u = 0; u < params->rush_exponent; u++) {
304                sp = VTAILQ_FIRST(&oh->waitinglist);
305                if (sp == NULL)
306                        return;
307                VTAILQ_REMOVE(&oh->waitinglist, sp, list);
308                DSL(0x20, SLT_Debug, sp->id, "off waiting list");
309                WRK_QueueSession(sp);
310        }
311}
312
313void
314HSH_Unbusy(const struct sess *sp)
315{
316        struct object *o;
317        struct objhead *oh;
318        struct object *parent;
319
320        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
321        o = sp->obj;
322        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
323        assert(o->busy);
324        assert(o->refcnt > 0);
325        if (o->ws_o->overflow)
326                VSL_stats->n_objoverflow++;
327        if (params->diag_bitmap & 0x40)
328                WSP(sp, SLT_Debug, 
329                    "Object %u workspace free %u", o->xid, WS_Free(o->ws_o));
330       
331        oh = o->objhead;
332        if (oh != NULL) {
333                CHECK_OBJ(oh, OBJHEAD_MAGIC);
334                LOCK(&oh->mtx);
335        }
336        o->busy = 0;
337        if (oh != NULL)
338                hsh_rush(oh);
339        parent = o->parent;
340        o->parent = NULL;
341        if (parent != NULL)
342                parent->child = NULL;
343        if (oh != NULL)
344                UNLOCK(&oh->mtx);
345        if (parent != NULL)
346                HSH_Deref(parent);
347}
348
349void
350HSH_Ref(struct object *o)
351{
352        struct objhead *oh;
353
354        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
355        oh = o->objhead;
356        if (oh != NULL) {
357                CHECK_OBJ(oh, OBJHEAD_MAGIC);
358                LOCK(&oh->mtx);
359        }
360        assert(o->refcnt > 0);
361        o->refcnt++;
362        if (oh != NULL)
363                UNLOCK(&oh->mtx);
364}
365
366void
367HSH_Deref(struct object *o)
368{
369        struct objhead *oh;
370        unsigned r;
371
372        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
373        oh = o->objhead;
374        if (oh != NULL) {
375                CHECK_OBJ(oh, OBJHEAD_MAGIC);
376
377                /* drop ref on object */
378                LOCK(&oh->mtx);
379        }
380        assert(o->refcnt > 0);
381        r = --o->refcnt;
382        if (oh != NULL)
383                hsh_rush(oh);
384        if (oh != NULL) {
385                if (!r)
386                        VTAILQ_REMOVE(&oh->objects, o, list);
387                UNLOCK(&oh->mtx);
388        }
389
390        /* If still referenced, done */
391        if (r != 0)
392                return;
393
394        BAN_DestroyObj(o);
395        DSL(0x40, SLT_Debug, 0, "Object %u workspace min free %u",
396            o->xid, WS_Free(o->ws_o));
397
398        if (o->vary != NULL)
399                free(o->vary);
400
401        ESI_Destroy(o);
402        HSH_Freestore(o);
403        STV_free(o->objstore);
404        VSL_stats->n_object--;
405
406        if (oh == NULL)
407                return;
408        /* Drop our ref on the objhead */
409        if (hash->deref(oh))
410                return;
411        assert(VTAILQ_EMPTY(&oh->objects));
412        MTX_DESTROY(&oh->mtx);
413        VSL_stats->n_objecthead--;
414        free(oh->hash);
415        FREE_OBJ(oh);
416}
417
418void
419HSH_Init(void)
420{
421
422        hash = heritage.hash;
423        if (hash->start != NULL)
424                hash->start();
425}
Note: See TracBrowser for help on using the repository browser.