source: bin/varnishd/cache_hash.c @ 7b8b18f

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

Add diagnostic features to keep track of object workspace usage.

git-svn-id:  http://www.varnish-cache.org/svn/trunk@2560 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 sess *sp)
289{
290        struct object *o;
291        struct objhead *oh;
292        struct object *parent;
293
294        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
295        o = sp->obj;
296        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
297        assert(o->busy);
298        assert(o->refcnt > 0);
299        if (o->ws_o->overflow)
300                VSL_stats->n_objoverflow++;
301        if (params->diag_bitmap & 0x40)
302                WSP(sp, SLT_Debug, 
303                    "Object workspace used %u", WS_Used(o->ws_o));
304       
305        oh = o->objhead;
306        if (oh != NULL) {
307                CHECK_OBJ(oh, OBJHEAD_MAGIC);
308                LOCK(&oh->mtx);
309        }
310        o->busy = 0;
311        if (oh != NULL)
312                hsh_rush(oh);
313        parent = o->parent;
314        o->parent = NULL;
315        if (parent != NULL)
316                parent->child = NULL;
317        if (oh != NULL)
318                UNLOCK(&oh->mtx);
319        if (parent != NULL)
320                HSH_Deref(parent);
321}
322
323void
324HSH_Ref(struct object *o)
325{
326        struct objhead *oh;
327
328        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
329        oh = o->objhead;
330        if (oh != NULL) {
331                CHECK_OBJ(oh, OBJHEAD_MAGIC);
332                LOCK(&oh->mtx);
333        }
334        assert(o->refcnt > 0);
335        o->refcnt++;
336        if (oh != NULL)
337                UNLOCK(&oh->mtx);
338}
339
340void
341HSH_Deref(struct object *o)
342{
343        struct objhead *oh;
344        unsigned r;
345
346        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
347        oh = o->objhead;
348        if (oh != NULL) {
349                CHECK_OBJ(oh, OBJHEAD_MAGIC);
350
351                /* drop ref on object */
352                LOCK(&oh->mtx);
353        }
354        assert(o->refcnt > 0);
355        r = --o->refcnt;
356        if (oh != NULL)
357                hsh_rush(oh);
358        if (oh != NULL) {
359                if (!r)
360                        VTAILQ_REMOVE(&oh->objects, o, list);
361                UNLOCK(&oh->mtx);
362        }
363
364        /* If still referenced, done */
365        if (r != 0)
366                return;
367
368        if (params->diag_bitmap & 0x40)
369                VSL(SLT_Debug, 0, 
370                    "Object workspace max used %u", WS_Used(o->ws_o));
371
372        if (o->vary != NULL)
373                free(o->vary);
374
375        ESI_Destroy(o);
376        HSH_Freestore(o);
377        STV_free(o->objstore);
378        VSL_stats->n_object--;
379
380        if (oh == NULL)
381                return;
382        /* Drop our ref on the objhead */
383        if (hash->deref(oh))
384                return;
385        assert(VTAILQ_EMPTY(&oh->objects));
386        MTX_DESTROY(&oh->mtx);
387        VSL_stats->n_objecthead--;
388        FREE_OBJ(oh);
389}
390
391void
392HSH_Init(void)
393{
394
395        hash = heritage.hash;
396        if (hash->start != NULL)
397                hash->start();
398}
Note: See TracBrowser for help on using the repository browser.