source: bin/varnishd/cache_hash.c @ 93a770e

Revision 93a770e, 7.4 KB checked in by Poul-Henning Kamp <phk@…>, 7 years ago (diff)

Rewrite the req.hash implmentation:

Instead of assembling the entire hash-string in the workspace, use
a scatter gather approach, hinted by the VCL compiler.

This eliminates the workspace reservation which prevented regsub() from
working in vcl_hash, and reduces the size of the necessary workspace a
fair bit as well, at the cost of a little bit of complexity in the
hash implmentations.

Closes ticket 137 and possibly 141

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

  • Property mode set to 100644
Line 
1/*-
2 * Copyright (c) 2006 Verdens Gang AS
3 * Copyright (c) 2006-2007 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
74        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
75        w = sp->wrk;
76
77        if (w->nobjhead == NULL) {
78                w->nobjhead = calloc(sizeof *w->nobjhead, 1);
79                XXXAN(w->nobjhead);
80                w->nobjhead->magic = OBJHEAD_MAGIC;
81                TAILQ_INIT(&w->nobjhead->objects);
82                MTX_INIT(&w->nobjhead->mtx);
83                VSL_stats->n_objecthead++;
84        } else
85                CHECK_OBJ_NOTNULL(w->nobjhead, OBJHEAD_MAGIC);
86        if (w->nobj == NULL) {
87                w->nobj = calloc(sizeof *w->nobj, 1);
88                XXXAN(w->nobj);
89                w->nobj->magic = OBJECT_MAGIC;
90                w->nobj->http.magic = HTTP_MAGIC;
91                w->nobj->busy = 1;
92                w->nobj->refcnt = 1;
93                TAILQ_INIT(&w->nobj->store);
94                TAILQ_INIT(&w->nobj->waitinglist);
95                VSL_stats->n_object++;
96        } else
97                CHECK_OBJ_NOTNULL(w->nobj, OBJECT_MAGIC);
98}
99
100static void
101HSH_Freestore(struct object *o)
102{
103        struct storage *st, *stn;
104
105        TAILQ_FOREACH_SAFE(st, &o->store, list, stn) {
106                CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
107                TAILQ_REMOVE(&o->store, st, list);
108                STV_free(st);
109        }
110}
111
112int
113HSH_Compare(struct sess *sp, const char *b, const char *e)
114{
115        int i;
116        unsigned u, v;
117
118        i = sp->lhashptr - (e - b);
119        if (i)
120                return (i);
121        for (u = 0; u < sp->ihashptr; u += 2) {
122                v = sp->hashptr[u + 1] - sp->hashptr[u];
123                i = memcmp(sp->hashptr[u], b, v);
124                if (i)
125                        return (i);
126                b += v;
127                i = '#' - *b++;
128                if (i)
129                        return (i);
130        }
131        assert(*b == '\0');
132        b++;
133        assert(b == e);
134        return (0);
135}
136
137void
138HSH_Copy(struct sess *sp, char *b, const char *e)
139{
140        unsigned u, v;
141
142        assert((e - b) >= sp->lhashptr);
143        for (u = 0; u < sp->ihashptr; u += 2) {
144                v = sp->hashptr[u + 1] - sp->hashptr[u];
145                memcpy(b, sp->hashptr[u], v);
146                b += v;
147                *b++ = '#';
148        }
149        *b++ = '\0';
150        assert(b <= e);
151}
152
153struct object *
154HSH_Lookup(struct sess *sp)
155{
156        struct worker *w;
157        struct http *h;
158        struct objhead *oh;
159        struct object *o;
160
161        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
162        CHECK_OBJ_NOTNULL(sp->wrk, WORKER_MAGIC);
163        CHECK_OBJ_NOTNULL(sp->http, HTTP_MAGIC);
164        AN(hash);
165        w = sp->wrk;
166        h = sp->http;
167
168        HSH_Prealloc(sp);
169        if (sp->obj != NULL) {
170                CHECK_OBJ_NOTNULL(sp->obj, OBJECT_MAGIC);
171                o = sp->obj;
172                oh = o->objhead;
173                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
174                LOCK(&oh->mtx);
175                goto were_back;
176        }
177
178        oh = hash->lookup(sp, w->nobjhead);
179        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
180        if (oh == w->nobjhead)
181                w->nobjhead = NULL;
182        LOCK(&oh->mtx);
183        TAILQ_FOREACH(o, &oh->objects, list) {
184                o->refcnt++;
185                if (o->busy) {
186                        TAILQ_INSERT_TAIL(&o->waitinglist, sp, list);
187                        sp->obj = o;
188                        UNLOCK(&oh->mtx);
189                        return (NULL);
190                }
191        were_back:
192                if (!o->cacheable) {
193                        /* ignore */
194                } else if (o->ttl == 0) {
195                        /* Object banned but not reaped yet */
196                } else if (o->ttl <= sp->t_req) {
197                        /* Object expired */
198                } else if (BAN_CheckObject(o, h->hd[HTTP_HDR_URL].b)) {
199                        o->ttl = 0;
200                        VSL(SLT_ExpBan, 0, "%u was banned", o->xid);
201                        if (o->heap_idx != 0)
202                                EXP_TTLchange(o);
203                } else if (o->vary == NULL || VRY_Match(sp, o->vary))
204                        break;
205                o->refcnt--;
206        }
207        if (o != NULL) {
208                UNLOCK(&oh->mtx);
209                (void)hash->deref(oh);
210                LRU_Enter(o, sp->t_req);
211                return (o);
212        }
213
214        /* Insert (precreated) object in objecthead */
215        o = w->nobj;
216        w->nobj = NULL;
217        o->objhead = oh;
218        TAILQ_INSERT_TAIL(&oh->objects, o, list);
219        /* NB: do not deref objhead the new object inherits our reference */
220        UNLOCK(&oh->mtx);
221        BAN_NewObj(o);
222        LRU_Enter(o, sp->t_req);
223        return (o);
224}
225
226void
227HSH_Unbusy(struct object *o)
228{
229        struct objhead *oh;
230        struct sess *sp;
231
232        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
233        assert(o->busy);
234        assert(o->refcnt > 0);
235        if (o->cacheable)
236                EXP_Insert(o);
237        oh = o->objhead;
238        if (oh != NULL) {
239                CHECK_OBJ(oh, OBJHEAD_MAGIC);
240                LOCK(&oh->mtx);
241        }
242        o->busy = 0;
243        if (oh != NULL)
244                UNLOCK(&oh->mtx);
245        while (1) {
246                sp = TAILQ_FIRST(&o->waitinglist);
247                if (sp == NULL)
248                        break;
249                TAILQ_REMOVE(&o->waitinglist, sp, list);
250                WRK_QueueSession(sp);
251        }
252}
253
254void
255HSH_Ref(struct object *o)
256{
257        struct objhead *oh;
258
259        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
260        oh = o->objhead;
261        if (oh != NULL) {
262                CHECK_OBJ(oh, OBJHEAD_MAGIC);
263                LOCK(&oh->mtx);
264        }
265        assert(o->refcnt > 0);
266        o->refcnt++;
267        if (oh != NULL)
268                UNLOCK(&oh->mtx);
269}
270
271void
272HSH_Deref(struct object *o)
273{
274        struct objhead *oh;
275        unsigned r;
276
277        CHECK_OBJ_NOTNULL(o, OBJECT_MAGIC);
278        oh = o->objhead;
279        if (oh != NULL) {
280                CHECK_OBJ(oh, OBJHEAD_MAGIC);
281
282                /* drop ref on object */
283                LOCK(&oh->mtx);
284        }
285        assert(o->refcnt > 0);
286        r = --o->refcnt;
287        if (oh != NULL) {
288                if (!r)
289                        TAILQ_REMOVE(&oh->objects, o, list);
290                UNLOCK(&oh->mtx);
291        }
292
293        /* If still referenced, done */
294        if (r != 0)
295                return;
296
297        if (o->http.ws->s != NULL)
298                free(o->http.ws->s);
299
300        if (o->vary != NULL)
301                free(o->vary);
302
303        LRU_Remove(o);
304        HSH_Freestore(o);
305        FREE_OBJ(o);
306        VSL_stats->n_object--;
307
308        if (oh == NULL)
309                return;
310        /* Drop our ref on the objhead */
311        if (hash->deref(oh))
312                return;
313        assert(TAILQ_EMPTY(&oh->objects));
314        MTX_DESTROY(&oh->mtx);
315        VSL_stats->n_objecthead--;
316        FREE_OBJ(oh);
317}
318
319void
320HSH_Init(void)
321{
322
323        hash = heritage.hash;
324        if (hash->start != NULL)
325                hash->start();
326}
Note: See TracBrowser for help on using the repository browser.