source: bin/varnishd/cache_hash.c @ aae429

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

Split the http_workspace into sess_workspace and obj_workspace, so they
can be tuned separately.

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