varnish-cache/bin/varnishd/cache/cache_hash.c
0
/*-
1
 * Copyright (c) 2006 Verdens Gang AS
2
 * Copyright (c) 2006-2015 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
6
 *
7
 * SPDX-License-Identifier: BSD-2-Clause
8
 *
9
 * Redistribution and use in source and binary forms, with or without
10
 * modification, are permitted provided that the following conditions
11
 * are met:
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 * 2. Redistributions in binary form must reproduce the above copyright
15
 *    notice, this list of conditions and the following disclaimer in the
16
 *    documentation and/or other materials provided with the distribution.
17
 *
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
22
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28
 * SUCH DAMAGE.
29
 *
30
 * This is the central hash-table code, it relies on a chosen hash
31
 * implementation only for the actual hashing, all the housekeeping
32
 * happens here.
33
 *
34
 * We have two kinds of structures, objecthead and object.  An objecthead
35
 * corresponds to a given (Host:, URL) tuple, and the objects hung from
36
 * the objecthead may represent various variations (ie: Vary: header,
37
 * different TTL etc) instances of that web-entity.
38
 *
39
 * Each objecthead has a mutex which locks both its own fields, the
40
 * list of objects and fields in the objects.
41
 *
42
 * The hash implementation must supply a reference count facility on
43
 * the objecthead, and return with a reference held after a lookup.
44
 *
45
 * Lookups in the hash implementation returns with a ref held and each
46
 * object hung from the objhead holds a ref as well.
47
 *
48
 * Objects have refcounts which are locked by the objecthead mutex.
49
 *
50
 * New objects are always marked busy, and they can go from busy to
51
 * not busy only once.
52
 */
53
54
#include "config.h"
55
56
#include <stdio.h>
57
#include <stdlib.h>
58
59
#include "cache_varnishd.h"
60
61
#include "cache/cache_objhead.h"
62
#include "cache/cache_transport.h"
63
64
#include "hash/hash_slinger.h"
65
66
#include "vsha256.h"
67
68
struct rush {
69
        unsigned                magic;
70
#define RUSH_MAGIC              0xa1af5f01
71
        VTAILQ_HEAD(,req)       reqs;
72
};
73
74
static const struct hash_slinger *hash;
75
#define PRIVATE_OH_EXP 7
76
static struct objhead private_ohs[1 << PRIVATE_OH_EXP];
77
78
static void hsh_rush1(const struct worker *, struct objcore *,
79
    struct rush *);
80
static void hsh_rush2(struct worker *, struct rush *);
81
static int hsh_deref_objhead(struct worker *wrk, struct objhead **poh);
82
static int hsh_deref_objhead_unlock(struct worker *wrk, struct objhead **poh,
83
    struct objcore *oc);
84
static int hsh_deref_objcore_unlock(struct worker *, struct objcore **);
85
86
/*---------------------------------------------------------------------*/
87
88
#define VCF_RETURN(x) const struct vcf_return VCF_##x[1] = { \
89
        { .name = #x, } \
90
};
91
92
VCF_RETURNS()
93
#undef VCF_RETURN
94
95
/*---------------------------------------------------------------------*/
96
97
static void
98 123055
hsh_initobjhead(struct objhead *oh)
99
{
100
101 123055
        XXXAN(oh);
102 123055
        INIT_OBJ(oh, OBJHEAD_MAGIC);
103 123055
        oh->refcnt = 1;
104 123055
        oh->waitinglist_gen = 1;
105 123055
        VTAILQ_INIT(&oh->objcs);
106 123055
        VTAILQ_INIT(&oh->waitinglist);
107 123055
        Lck_New(&oh->mtx, lck_objhdr);
108 123055
}
109
110
static struct objhead *
111 1583
hsh_newobjhead(void)
112
{
113 1583
        struct objhead *oh = malloc(sizeof *oh);
114 1583
        hsh_initobjhead(oh);
115 1583
        return (oh);
116
}
117
118
/*---------------------------------------------------------------------*/
119
/* Precreate an objhead and object for later use */
120
static void
121 2680
hsh_prealloc(struct worker *wrk)
122
{
123
124 2680
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
125
126 2680
        if (wrk->wpriv->nobjcore == NULL)
127 1811
                wrk->wpriv->nobjcore = ObjNew(wrk);
128 2680
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);
129
130 2680
        if (wrk->wpriv->nobjhead == NULL) {
131 1583
                wrk->wpriv->nobjhead = hsh_newobjhead();
132 1583
                wrk->stats->n_objecthead++;
133 1583
        }
134 2680
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
135
136 2680
        if (hash->prep != NULL)
137 2674
                hash->prep(wrk);
138 2680
}
139
140
/*---------------------------------------------------------------------*/
141
142
// https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
143
static inline size_t
144 1416
fib(uint64_t n, uint8_t bits)
145
{
146 1416
        const uint64_t gr = 11400714819323198485LLU;
147
        uint64_t r;
148
149 1416
        r = n * gr;
150 1416
        r >>= (sizeof(gr) * 8) - bits;
151 1416
        assert(r < (size_t)1 << bits);
152 1416
        return ((size_t)r);
153
}
154
155
struct objcore *
156 1416
HSH_Private(const struct worker *wrk)
157
{
158
        struct objcore *oc;
159
        struct objhead *oh;
160
161 1416
        oh = &private_ohs[fib((uintptr_t)wrk, PRIVATE_OH_EXP)];
162 1416
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
163
164 1416
        oc = ObjNew(wrk);
165 1416
        AN(oc);
166 1416
        oc->refcnt = 1;
167 1416
        oc->objhead = oh;
168 1416
        oc->flags |= OC_F_PRIVATE;
169 1416
        Lck_Lock(&oh->mtx);
170 1416
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
171 1416
        oh->refcnt++;
172 1416
        Lck_Unlock(&oh->mtx);
173 1416
        return (oc);
174
}
175
176
/*---------------------------------------------------------------------*/
177
178
void
179 967
HSH_Cleanup(const struct worker *wrk)
180
{
181
182 967
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
183 967
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
184 967
        if (wrk->wpriv->nobjcore != NULL)
185 1
                ObjDestroy(wrk, &wrk->wpriv->nobjcore);
186
187 967
        if (wrk->wpriv->nobjhead != NULL) {
188 1
                CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
189 1
                Lck_Delete(&wrk->wpriv->nobjhead->mtx);
190 1
                FREE_OBJ(wrk->wpriv->nobjhead);
191 1
                wrk->stats->n_objecthead--;
192 1
        }
193 967
        if (wrk->wpriv->nhashpriv != NULL) {
194
                /* XXX: If needed, add slinger method for this */
195 2
                free(wrk->wpriv->nhashpriv);
196 2
                wrk->wpriv->nhashpriv = NULL;
197 2
        }
198 967
}
199
200
void
201 0
HSH_DeleteObjHead(const struct worker *wrk, struct objhead *oh)
202
{
203 0
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
204 0
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
205
206 0
        AZ(oh->refcnt);
207 0
        assert(VTAILQ_EMPTY(&oh->objcs));
208 0
        assert(VTAILQ_EMPTY(&oh->waitinglist));
209 0
        Lck_Delete(&oh->mtx);
210 0
        wrk->stats->n_objecthead--;
211 0
        FREE_OBJ(oh);
212 0
}
213
214
void
215 14811
HSH_AddString(struct req *req, void *ctx, const char *str)
216
{
217
218 14811
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
219 14811
        AN(ctx);
220 14811
        if (str != NULL) {
221 7405
                VSHA256_Update(ctx, str, strlen(str));
222 7405
                VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
223 7405
        } else
224 7406
                VSHA256_Update(ctx, &str, 1);
225 14811
}
226
227
/*---------------------------------------------------------------------
228
 * This is a debugging hack to enable testing of boundary conditions
229
 * in the hash algorithm.
230
 * We trap the first 9 different digests and translate them to different
231
 * digests with edge bit conditions
232
 */
233
234
static struct hsh_magiclist {
235
        unsigned char was[VSHA256_LEN];
236
        unsigned char now[VSHA256_LEN];
237
} hsh_magiclist[] = {
238
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
239
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
240
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
241
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
242
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
243
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
244
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
245
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 } },
246
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
247
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
248
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
249
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02 } },
250
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
251
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
252
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
253
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40 } },
254
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
255
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
256
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
257
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80 } },
258
        { .now = {      0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
259
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
260
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
261
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
262
        { .now = {      0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
263
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
264
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
265
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
266
        { .now = {      0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
267
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
268
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
269
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
270
        { .now = {      0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
271
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
272
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
273
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
274
};
275
276
#define HSH_NMAGIC vcountof(hsh_magiclist)
277
278
static void
279 18
hsh_testmagic(void *result)
280
{
281
        size_t i, j;
282
        static size_t nused = 0;
283
284 90
        for (i = 0; i < nused; i++)
285 81
                if (!memcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
286 9
                        break;
287 18
        if (i == nused && i < HSH_NMAGIC)
288 9
                memcpy(hsh_magiclist[nused++].was, result, VSHA256_LEN);
289 18
        if (i == nused)
290 0
                return;
291 18
        assert(i < HSH_NMAGIC);
292 18
        fprintf(stderr, "HASHMAGIC: <");
293 594
        for (j = 0; j < VSHA256_LEN; j++)
294 576
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
295 18
        fprintf(stderr, "> -> <");
296 18
        memcpy(result, hsh_magiclist[i].now, VSHA256_LEN);
297 594
        for (j = 0; j < VSHA256_LEN; j++)
298 576
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
299 18
        fprintf(stderr, ">\n");
300 18
}
301
302
/*---------------------------------------------------------------------
303
 * Insert an object which magically appears out of nowhere or, more likely,
304
 * comes off some persistent storage device.
305
 * Insert it with a reference held.
306
 */
307
308
void
309 17
HSH_Insert(struct worker *wrk, const void *digest, struct objcore *oc,
310
    struct ban *ban)
311
{
312
        struct objhead *oh;
313
        struct rush rush;
314
315 17
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
316 17
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
317 17
        AN(digest);
318 17
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
319 17
        AN(ban);
320 17
        AZ(oc->flags & OC_F_BUSY);
321 17
        AZ(oc->flags & OC_F_PRIVATE);
322 17
        assert(oc->refcnt == 1);
323 17
        INIT_OBJ(&rush, RUSH_MAGIC);
324
325 17
        hsh_prealloc(wrk);
326
327 17
        AN(wrk->wpriv->nobjhead);
328 17
        oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
329 17
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
330 17
        Lck_AssertHeld(&oh->mtx);
331 17
        assert(oh->refcnt > 0);
332
333
        /* Mark object busy and insert (precreated) objcore in
334
           objecthead. The new object inherits our objhead reference. */
335 17
        oc->objhead = oh;
336 17
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
337 17
        EXP_RefNewObjcore(oc);
338 17
        Lck_Unlock(&oh->mtx);
339
340 17
        BAN_RefBan(oc, ban);
341 17
        AN(oc->ban);
342
343
        /* Move the object first in the oh list, unbusy it and run the
344
           waitinglist if necessary */
345 17
        Lck_Lock(&oh->mtx);
346 17
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
347 17
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
348 17
        if (!VTAILQ_EMPTY(&oh->waitinglist))
349 0
                hsh_rush1(wrk, oc, &rush);
350 17
        Lck_Unlock(&oh->mtx);
351 17
        hsh_rush2(wrk, &rush);
352
353 17
        EXP_Insert(wrk, oc);
354 17
}
355
356
/*---------------------------------------------------------------------
357
 */
358
359
static struct objcore *
360 1524
hsh_insert_busyobj(const struct worker *wrk, struct objhead *oh)
361
{
362
        struct objcore *oc;
363
364 1524
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
365 1524
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
366 1524
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
367 1524
        Lck_AssertHeld(&oh->mtx);
368
369 1524
        oc = wrk->wpriv->nobjcore;
370 1524
        wrk->wpriv->nobjcore = NULL;
371 1524
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
372
373 1524
        AZ(oc->flags & OC_F_BUSY);
374 1524
        oc->flags |= OC_F_BUSY;
375 1524
        oc->refcnt = 1;         /* Owned by busyobj */
376 1524
        oc->objhead = oh;
377 1524
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
378 1524
        return (oc);
379
}
380
381
/*---------------------------------------------------------------------
382
 */
383
384
static int
385 3927
hsh_vry_match(const struct req *req, struct objcore *oc, const uint8_t *vary)
386
{
387
388 3927
        if (req->hash_ignore_vary)
389 1
                return (1);
390 3926
        if (vary == NULL) {
391 3924
                if (! ObjHasAttr(req->wrk, oc, OA_VARY))
392 1102
                        return (1);
393 2822
                vary = ObjGetAttr(req->wrk, oc, OA_VARY, NULL);
394 2822
                AN(vary);
395 2822
        }
396 2824
        return (VRY_Match(req, vary));
397 3927
}
398
399
static unsigned
400 55
hsh_rush_match(const struct req *req)
401
{
402
        struct objhead *oh;
403
        struct objcore *oc;
404
405 55
        oc = req->objcore;
406 55
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
407 55
        assert(oc->refcnt > 0);
408
409 55
        AZ(oc->flags & OC_F_BUSY);
410 55
        AZ(oc->flags & OC_F_PRIVATE);
411 55
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_HFM|OC_F_HFP|OC_F_CANCEL|
412
            OC_F_FAILED))
413 12
                return (0);
414
415 43
        if (req->vcf != NULL) /* NB: must operate under oh lock. */
416 0
                return (0);
417
418 43
        oh = oc->objhead;
419 43
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420
421 43
        return (hsh_vry_match(req, oc, NULL));
422 55
}
423
424
/*---------------------------------------------------------------------
425
 */
426
427
enum lookup_e
428 2663
HSH_Lookup(struct req *req, struct objcore **ocp, struct objcore **bocp)
429
{
430
        struct worker *wrk;
431
        struct objhead *oh;
432
        struct objcore *oc;
433
        struct objcore *exp_oc;
434
        const struct vcf_return *vr;
435
        vtim_real exp_t_origin;
436
        int busy_found;
437
        intmax_t boc_progress;
438 2663
        unsigned xid = 0;
439
        unsigned ban_checks;
440
        unsigned ban_any_variant;
441 2663
        float dttl = 0.0;
442
443 2663
        AN(ocp);
444 2663
        *ocp = NULL;
445 2663
        AN(bocp);
446 2663
        *bocp = NULL;
447
448 2663
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
449 2663
        wrk = req->wrk;
450 2663
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
451 2663
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
452 2663
        CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
453 2663
        CHECK_OBJ_ORNULL(req->objcore, OBJCORE_MAGIC);
454 2663
        CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
455 2663
        AN(hash);
456
457 2663
        hsh_prealloc(wrk);
458 2663
        if (DO_DEBUG(DBG_HASHEDGE))
459 18
                hsh_testmagic(req->digest);
460
461
        /*
462
         * When a req rushes off the waiting list, it brings an implicit
463
         * oh refcnt acquired at disembark time and an oc ref (with its
464
         * own distinct oh ref) acquired during rush hour.
465
         */
466
467 2663
        if (req->objcore != NULL && hsh_rush_match(req)) {
468 41
                TAKE_OBJ_NOTNULL(oc, &req->objcore, OBJCORE_MAGIC);
469 41
                *ocp = oc;
470 41
                oh = oc->objhead;
471 41
                Lck_Lock(&oh->mtx);
472 41
                oc->hits++;
473 41
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
474 41
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
475 41
                Req_LogHit(wrk, req, oc, boc_progress);
476
                /* NB: since this hit comes from the waiting list instead of
477
                 * a regular lookup, grace is not considered. The object is
478
                 * fresh in the context of the waiting list, even expired: it
479
                 * was successfully just [re]validated by a fetch task.
480
                 */
481 41
                return (HSH_HIT);
482
        }
483
484 2622
        if (req->objcore != NULL) {
485 14
                oh = req->objcore->objhead;
486 14
                (void)HSH_DerefObjCore(wrk, &req->objcore);
487 14
                Lck_Lock(&oh->mtx);
488 14
        } else {
489 2608
                AN(wrk->wpriv->nobjhead);
490 2608
                oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
491
        }
492
493 2622
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
494 2622
        Lck_AssertHeld(&oh->mtx);
495
496 2622
        if (req->hash_always_miss) {
497
                /* XXX: should we do predictive Vary in this case ? */
498
                /* Insert new objcore in objecthead and release mutex */
499 15
                *bocp = hsh_insert_busyobj(wrk, oh);
500
                /* NB: no deref of objhead, new object inherits reference */
501 15
                Lck_Unlock(&oh->mtx);
502 15
                return (HSH_MISS);
503
        }
504
505 2607
        assert(oh->refcnt > 0);
506 2607
        busy_found = 0;
507 2607
        exp_oc = NULL;
508 2607
        exp_t_origin = 0.0;
509 2607
        ban_checks = 0;
510 2607
        ban_any_variant = cache_param->ban_any_variant;
511 5523
        VTAILQ_FOREACH(oc, &oh->objcs, hsh_list) {
512
                /* Must be at least our own ref + the objcore we examine */
513 3990
                assert(oh->refcnt > 1);
514 3990
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
515 3990
                assert(oc->objhead == oh);
516 3990
                assert(oc->refcnt > 0);
517
518 3990
                if (oc->flags & OC_F_DYING)
519 0
                        continue;
520 3990
                if (oc->flags & OC_F_FAILED)
521 0
                        continue;
522
523 3990
                CHECK_OBJ_ORNULL(oc->boc, BOC_MAGIC);
524 3990
                if (oc->flags & OC_F_BUSY) {
525 61
                        if (req->hash_ignore_busy)
526 1
                                continue;
527
528 60
                        if (oc->boc && oc->boc->vary != NULL &&
529 2
                            !hsh_vry_match(req, oc, oc->boc->vary)) {
530 1
                                wrk->strangelove++;
531 1
                                continue;
532
                        }
533
534 59
                        busy_found = 1;
535 59
                        continue;
536
                }
537
538 3929
                if (oc->ttl <= 0.)
539 47
                        continue;
540
541 3882
                if (ban_checks++ < ban_any_variant
542 3882
                    && BAN_CheckObject(wrk, oc, req)) {
543 0
                        oc->flags |= OC_F_DYING;
544 0
                        EXP_Remove(oc, NULL);
545 0
                        continue;
546
                }
547
548 3882
                if (!hsh_vry_match(req, oc, NULL)) {
549 2626
                        wrk->strangelove++;
550 2626
                        continue;
551
                }
552
553 1256
                if (ban_checks >= ban_any_variant
554 1256
                    && BAN_CheckObject(wrk, oc, req)) {
555 34
                        oc->flags |= OC_F_DYING;
556 34
                        EXP_Remove(oc, NULL);
557 34
                        continue;
558
                }
559
560 1222
                if (req->vcf != NULL) {
561 8
                        vr = req->vcf->func(req, &oc, &exp_oc, 0);
562 8
                        if (vr == VCF_CONTINUE)
563 4
                                continue;
564 4
                        if (vr == VCF_MISS) {
565 3
                                oc = NULL;
566 3
                                break;
567
                        }
568 1
                        if (vr == VCF_HIT)
569 1
                                break;
570 0
                        assert(vr == VCF_DEFAULT);
571 0
                }
572
573 1214
                if (EXP_Ttl(req, oc) > req->t_req) {
574 1070
                        assert(oh->refcnt > 1);
575 1070
                        assert(oc->objhead == oh);
576 1070
                        break;
577
                }
578
579 144
                if (EXP_Ttl(NULL, oc) <= req->t_req && /* ignore req.ttl */
580 141
                    oc->t_origin > exp_t_origin) {
581
                        /* record the newest object */
582 140
                        exp_oc = oc;
583 140
                        exp_t_origin = oc->t_origin;
584 140
                        assert(oh->refcnt > 1);
585 140
                        assert(exp_oc->objhead == oh);
586 140
                }
587 144
        }
588
589 2607
        if (req->vcf != NULL)
590 6
                (void)req->vcf->func(req, &oc, &exp_oc, 1);
591
592 2607
        if (oc != NULL && oc->flags & OC_F_HFP) {
593 11
                xid = VXID(ObjGetXID(wrk, oc));
594 11
                dttl = EXP_Dttl(req, oc);
595 11
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
596 11
                wrk->stats->cache_hitpass++;
597 11
                VSLb(req->vsl, SLT_HitPass, "%u %.6f", xid, dttl);
598 11
                return (HSH_HITPASS);
599
        }
600
601 2596
        if (oc != NULL) {
602 1061
                *ocp = oc;
603 1061
                oc->refcnt++;
604 1061
                if (oc->flags & OC_F_HFM) {
605 32
                        xid = VXID(ObjGetXID(wrk, oc));
606 32
                        dttl = EXP_Dttl(req, oc);
607 32
                        *bocp = hsh_insert_busyobj(wrk, oh);
608 32
                        Lck_Unlock(&oh->mtx);
609 32
                        wrk->stats->cache_hitmiss++;
610 32
                        VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
611 32
                        return (HSH_HITMISS);
612
                }
613 1029
                oc->hits++;
614 1029
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
615 1029
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
616 1029
                Req_LogHit(wrk, req, oc, boc_progress);
617 1029
                return (HSH_HIT);
618
        }
619
620 1535
        if (exp_oc != NULL && exp_oc->flags & OC_F_HFM) {
621
                /*
622
                 * expired HFM ("grace/keep HFM")
623
                 *
624
                 * XXX should HFM objects actually have grace/keep ?
625
                 * XXX also:  why isn't *ocp = exp_oc ?
626
                 */
627 4
                xid = VXID(ObjGetXID(wrk, exp_oc));
628 4
                dttl = EXP_Dttl(req, exp_oc);
629 4
                *bocp = hsh_insert_busyobj(wrk, oh);
630 4
                Lck_Unlock(&oh->mtx);
631 4
                wrk->stats->cache_hitmiss++;
632 4
                VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
633 4
                return (HSH_HITMISS);
634
        }
635
636 1531
        if (exp_oc != NULL && exp_oc->boc != NULL)
637 5
                boc_progress = exp_oc->boc->fetched_so_far;
638
        else
639 1526
                boc_progress = -1;
640
641 1531
        if (!busy_found) {
642 1473
                *bocp = hsh_insert_busyobj(wrk, oh);
643
644 1473
                if (exp_oc != NULL) {
645 131
                        exp_oc->refcnt++;
646 131
                        *ocp = exp_oc;
647 131
                        if (EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
648 94
                                exp_oc->hits++;
649 94
                                Lck_Unlock(&oh->mtx);
650 94
                                Req_LogHit(wrk, req, exp_oc, boc_progress);
651 94
                                return (HSH_GRACE);
652
                        }
653 37
                }
654 1379
                Lck_Unlock(&oh->mtx);
655 1379
                return (HSH_MISS);
656
        }
657
658 58
        AN(busy_found);
659 58
        if (exp_oc != NULL && EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
660
                /* we do not wait on the busy object if in grace */
661 3
                exp_oc->refcnt++;
662 3
                *ocp = exp_oc;
663 3
                exp_oc->hits++;
664 3
                AN(hsh_deref_objhead_unlock(wrk, &oh, NULL));
665 3
                Req_LogHit(wrk, req, exp_oc, boc_progress);
666 3
                return (HSH_GRACE);
667
        }
668
669
        /* There are one or more busy objects, wait for them */
670 55
        VTAILQ_INSERT_TAIL(&oh->waitinglist, req, w_list);
671
672 55
        AZ(req->hash_ignore_busy);
673
674
        /*
675
         * The objhead reference is held by req while it is parked on the
676
         * waiting list. The oh pointer is taken back from the objcore that
677
         * triggers a rush of req off the waiting list.
678
         */
679 55
        assert(oh->refcnt > 1);
680
681 55
        req->wrk = NULL;
682 55
        req->waitinglist_gen = oh->waitinglist_gen;
683
684 55
        if (DO_DEBUG(DBG_WAITINGLIST))
685 22
                VSLb(req->vsl, SLT_Debug, "on waiting list <%p>", oh);
686
687 55
        Lck_Unlock(&oh->mtx);
688
689 55
        wrk->stats->busy_sleep++;
690 55
        return (HSH_BUSY);
691 2663
}
692
693
/*---------------------------------------------------------------------
694
 * Pick the req's we are going to rush from the waiting list
695
 */
696
697
static void
698 120
hsh_rush1(const struct worker *wrk, struct objcore *oc, struct rush *r)
699
{
700
        struct objhead *oh;
701
        struct req *req;
702
        int i, max;
703
704 120
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
705 120
        CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
706 120
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
707 120
        VTAILQ_INIT(&r->reqs);
708
709 120
        if (oc == NULL)
710 1
                return;
711
712 119
        oh = oc->objhead;
713 119
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
714 119
        Lck_AssertHeld(&oh->mtx);
715
716 119
        AZ(oc->flags & OC_F_BUSY);
717 119
        AZ(oc->flags & OC_F_PRIVATE);
718 119
        max = cache_param->rush_exponent;
719 119
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_FAILED))
720 79
                max = 1;
721 119
        assert(max > 0);
722
723 119
        if (oc->waitinglist_gen == 0) {
724 113
                oc->waitinglist_gen = oh->waitinglist_gen;
725 113
                oh->waitinglist_gen++;
726 113
        }
727
728 174
        for (i = 0; i < max; i++) {
729 163
                req = VTAILQ_FIRST(&oh->waitinglist);
730 163
                if (req == NULL)
731 108
                        break;
732
733 55
                CHECK_OBJ(req, REQ_MAGIC);
734
735
                /* NB: The waiting list is naturally sorted by generation.
736
                 *
737
                 * Because of the exponential nature of the rush, it is
738
                 * possible that new requests enter the waiting list before
739
                 * the rush for this oc completes. Because the OC_F_BUSY flag
740
                 * was cleared before the beginning of the rush, requests
741
                 * from a newer generation already got a chance to evaluate
742
                 * oc during a lookup and it didn't match their criteria.
743
                 *
744
                 * Therefore there's no point propagating the exponential
745
                 * rush of this oc when we see a newer generation.
746
                 */
747 55
                if (req->waitinglist_gen > oc->waitinglist_gen)
748 0
                        break;
749
750 55
                AZ(req->wrk);
751 55
                VTAILQ_REMOVE(&oh->waitinglist, req, w_list);
752 55
                VTAILQ_INSERT_TAIL(&r->reqs, req, w_list);
753 55
                req->objcore = oc;
754 55
                oc->refcnt++;
755 55
                wrk->stats->busy_wakeup++;
756 55
        }
757 120
}
758
759
/*---------------------------------------------------------------------
760
 * Rush req's that came from waiting list.
761
 */
762
763
static void
764 3108
hsh_rush2(struct worker *wrk, struct rush *r)
765
{
766
        struct req *req;
767
768 3108
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
769 3108
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
770
771 3163
        while (!VTAILQ_EMPTY(&r->reqs)) {
772 55
                req = VTAILQ_FIRST(&r->reqs);
773 55
                CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
774 55
                VTAILQ_REMOVE(&r->reqs, req, w_list);
775 55
                DSL(DBG_WAITINGLIST, req->vsl->wid, "off waiting list");
776 55
                if (req->transport->reembark != NULL) {
777
                        // For ESI includes
778 1
                        req->transport->reembark(wrk, req);
779 1
                } else {
780
                        /*
781
                         * We ignore the queue limits which apply to new
782
                         * requests because if we fail to reschedule there
783
                         * may be vmod_privs to cleanup and we need a proper
784
                         * workerthread for that.
785
                         */
786 54
                        AZ(Pool_Task(req->sp->pool, req->task, TASK_QUEUE_RUSH));
787
                }
788
        }
789 3108
}
790
791
/*---------------------------------------------------------------------
792
 * Purge an entire objhead
793
 */
794
795
unsigned
796 22
HSH_Purge(struct worker *wrk, struct objhead *oh, vtim_real ttl_now,
797
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
798
{
799
        struct objcore *oc, *oc_nows[2], **ocp;
800 22
        unsigned i, j, n, n_max, total = 0;
801
        int is_purge;
802
803 22
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
804 22
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
805
806 22
        is_purge = (ttl == 0 && grace == 0 && keep == 0);
807 22
        n_max = WS_ReserveLumps(wrk->aws, sizeof *ocp);
808 22
        if (n_max < 2) {
809
                /* No space on the workspace. Give it a stack buffer of 2
810
                 * elements, which is the minimum for the algorithm
811
                 * below. */
812 0
                ocp = oc_nows;
813 0
                n_max = 2;
814 0
        } else
815 22
                ocp = WS_Reservation(wrk->aws);
816 22
        AN(ocp);
817
818
        /* Note: This algorithm uses OC references in the list as
819
         * bookmarks, in order to know how far into the list we were when
820
         * releasing the mutex partway through and want to resume
821
         * again. This relies on the list not being reordered while we are
822
         * not holding the mutex. The only place where that happens is in
823
         * HSH_Unbusy(), where an OC_F_BUSY OC is moved first in the
824
         * list. This does not cause problems because we skip OC_F_BUSY
825
         * OCs. */
826
827 22
        Lck_Lock(&oh->mtx);
828 22
        oc = VTAILQ_FIRST(&oh->objcs);
829 22
        n = 0;
830 23
        while (1) {
831 134
                for (; n < n_max && oc != NULL; oc = VTAILQ_NEXT(oc, hsh_list))
832
                {
833 111
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
834 111
                        assert(oc->objhead == oh);
835 111
                        if (oc->flags & OC_F_BUSY) {
836
                                /* We cannot purge busy objects here, because
837
                                 * their owners have special rights to them,
838
                                 * and may nuke them without concern for the
839
                                 * refcount, which by definition always must
840
                                 * be one, so they don't check. */
841 19
                                continue;
842
                        }
843 92
                        if (oc->flags & OC_F_DYING)
844 0
                                continue;
845 92
                        if (is_purge)
846 82
                                oc->flags |= OC_F_DYING;
847 92
                        oc->refcnt++;
848 92
                        ocp[n++] = oc;
849 92
                }
850
851 23
                Lck_Unlock(&oh->mtx);
852
853 23
                if (n == 0) {
854
                        /* No eligible objcores found. We are finished. */
855 4
                        break;
856
                }
857
858 19
                j = n;
859 19
                if (oc != NULL) {
860
                        /* There are more objects on the objhead that we
861
                         * have not yet looked at, but no more space on
862
                         * the objcore reference list. Do not process the
863
                         * last one, it will be used as the bookmark into
864
                         * the objcore list for the next iteration of the
865
                         * outer loop. */
866 1
                        j--;
867 1
                        assert(j >= 1); /* True because n_max >= 2 */
868 1
                }
869 111
                for (i = 0; i < j; i++) {
870 92
                        CHECK_OBJ_NOTNULL(ocp[i], OBJCORE_MAGIC);
871 92
                        if (is_purge)
872 82
                                EXP_Remove(ocp[i], NULL);
873
                        else
874 10
                                EXP_Reduce(ocp[i], ttl_now, ttl, grace, keep);
875 92
                        (void)HSH_DerefObjCore(wrk, &ocp[i]);
876 92
                        AZ(ocp[i]);
877 92
                        total++;
878 92
                }
879
880 19
                if (j == n) {
881
                        /* No bookmark set, that means we got to the end
882
                         * of the objcore list in the previous run and are
883
                         * finished. */
884 18
                        break;
885
                }
886
887 1
                Lck_Lock(&oh->mtx);
888
889
                /* Move the bookmark first and continue scanning the
890
                 * objcores */
891 1
                CHECK_OBJ_NOTNULL(ocp[j], OBJCORE_MAGIC);
892 1
                ocp[0] = ocp[j];
893 1
                n = 1;
894 1
                oc = VTAILQ_NEXT(ocp[0], hsh_list);
895 1
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
896
        }
897
898 22
        WS_Release(wrk->aws, 0);
899 22
        if (is_purge)
900 12
                Pool_PurgeStat(total);
901 22
        return (total);
902
}
903
904
/*---------------------------------------------------------------------
905
 * Fail an objcore
906
 */
907
908
void
909 68
HSH_Fail(struct worker *wrk, struct objcore *oc)
910
{
911
        struct objhead *oh;
912
        struct rush rush;
913
914 68
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
915 68
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
916 68
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
917 68
        oh = oc->objhead;
918 68
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
919 68
        INIT_OBJ(&rush, RUSH_MAGIC);
920
921
        /*
922
         * We either failed before the end of vcl_backend_response
923
         * and a cache miss has the busy bit, so that HSH_Lookup()
924
         * will not consider this oc, or an object hung off the oc
925
         * so that it can consider it.
926
         *
927
         * We can only fail an ongoing fetch in a backend context
928
         * so we can safely check the BOC state as it won't change
929
         * under our feet.
930
         */
931 68
        if (oc->boc->state < BOS_STREAM)
932 51
                assert(oc->flags & (OC_F_BUSY|OC_F_PRIVATE));
933
        else
934 17
                assert(oc->stobj->stevedore != NULL);
935
936 68
        Lck_Lock(&oh->mtx);
937 68
        oc->flags |= OC_F_FAILED;
938 68
        if (oc->flags & OC_F_BUSY) {
939 45
                oc->flags &= ~OC_F_BUSY;
940 45
                hsh_rush1(wrk, oc, &rush);
941 45
        }
942 68
        Lck_Unlock(&oh->mtx);
943 68
        hsh_rush2(wrk, &rush);
944 68
}
945
946
/*---------------------------------------------------------------------
947
 * Mark a fetch we will not need as cancelled
948
 */
949
950
static void
951 354
hsh_cancel(struct objcore *oc)
952
{
953
        struct objhead *oh;
954
955 354
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
956 354
        oh = oc->objhead;
957 354
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
958
959 354
        Lck_Lock(&oh->mtx);
960 354
        oc->flags |= OC_F_CANCEL;
961 354
        Lck_Unlock(&oh->mtx);
962 354
}
963
964
/*---------------------------------------------------------------------
965
 * Cancel a fetch when the client does not need it any more
966
 */
967
968
void
969 3843
HSH_Cancel(struct worker *wrk, struct objcore *oc, struct boc *boc)
970
{
971 3843
        struct boc *bocref = NULL;
972
973 3843
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
974
975 3843
        if ((oc->flags & OC_F_TRANSIENT) == 0)
976 2444
                return;
977
978
        /*
979
         * NB: we use two distinct variables to only release the reference if
980
         * we had to acquire one. The caller-provided boc is optional.
981
         */
982 1399
        if (boc == NULL)
983 1048
                bocref = boc = HSH_RefBoc(oc);
984
985 1399
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
986
987 1399
        if (oc->flags & OC_F_HFP)
988 22
                AN(oc->flags & OC_F_HFM);
989
990 1399
        if (boc != NULL) {
991 354
                hsh_cancel(oc);
992 354
                ObjWaitState(oc, BOS_FINISHED);
993 354
        }
994
995 1399
        if (bocref != NULL)
996 3
                HSH_DerefBoc(wrk, oc);
997
998 1399
        ObjSlim(wrk, oc);
999 3843
}
1000
1001
/*---------------------------------------------------------------------
1002
 * Withdraw an objcore that will not proceed with a fetch.
1003
 */
1004
1005
void
1006 34
HSH_Withdraw(struct worker *wrk, struct objcore **ocp)
1007
{
1008
        struct objhead *oh;
1009
        struct objcore *oc;
1010
        struct rush rush;
1011
1012 34
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1013 34
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1014 34
        INIT_OBJ(&rush, RUSH_MAGIC);
1015
1016 34
        oh = oc->objhead;
1017 34
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1018
1019 34
        Lck_Lock(&oh->mtx);
1020 34
        AZ(oc->stobj->stevedore);
1021 34
        AN(oc->flags & OC_F_BUSY);
1022 34
        assert(oc->refcnt == 1);
1023 34
        assert(oh->refcnt > 0);
1024 34
        oc->flags &= ~OC_F_BUSY;
1025 34
        oc->flags |= OC_F_WITHDRAWN;
1026 34
        hsh_rush1(wrk, oc, &rush); /* grabs up to 1 oc ref */
1027 34
        assert(hsh_deref_objcore_unlock(wrk, &oc) <= 1);
1028
1029 34
        hsh_rush2(wrk, &rush);
1030 34
}
1031
1032
/*---------------------------------------------------------------------
1033
 * Unbusy an objcore when the object is completely fetched.
1034
 */
1035
1036
void
1037 2222
HSH_Unbusy(struct worker *wrk, struct objcore *oc)
1038
{
1039
        struct objhead *oh;
1040
        struct rush rush;
1041
1042 2222
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1043 2222
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1044 2222
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
1045
1046 2222
        oh = oc->objhead;
1047 2222
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1048
1049 2222
        AN(oc->stobj->stevedore);
1050 2222
        assert(oh->refcnt > 0);
1051 2222
        assert(oc->refcnt > 0);
1052
1053 2222
        if (oc->flags & OC_F_PRIVATE) {
1054 778
                AZ(oc->flags & OC_F_BUSY);
1055 778
                return;
1056
        }
1057
1058 1444
        AN(oc->flags & OC_F_BUSY);
1059 1444
        INIT_OBJ(&rush, RUSH_MAGIC);
1060
1061 1444
        BAN_NewObjCore(oc);
1062 1444
        AN(oc->ban);
1063
1064
        /* XXX: pretouch neighbors on oh->objcs to prevent page-on under mtx */
1065 1444
        Lck_Lock(&oh->mtx);
1066 1444
        assert(oh->refcnt > 0);
1067 1444
        assert(oc->refcnt > 0);
1068 1444
        EXP_RefNewObjcore(oc); /* Takes a ref for expiry */
1069
        /* XXX: strictly speaking, we should sort in Date: order. */
1070 1444
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1071 1444
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
1072 1444
        oc->flags &= ~OC_F_BUSY;
1073 1444
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1074 34
                assert(oh->refcnt > 1);
1075 34
                hsh_rush1(wrk, oc, &rush);
1076 34
        }
1077 1444
        Lck_Unlock(&oh->mtx);
1078 1444
        EXP_Insert(wrk, oc);
1079 1444
        hsh_rush2(wrk, &rush);
1080 2222
}
1081
1082
/*====================================================================
1083
 * HSH_Kill()
1084
 *
1085
 * It's dead Jim, kick it...
1086
 */
1087
1088
void
1089 236
HSH_Kill(struct objcore *oc)
1090
{
1091
1092 236
        HSH_Replace(oc, NULL);
1093 236
}
1094
1095
void
1096 312
HSH_Replace(struct objcore *oc, const struct objcore *new_oc)
1097
{
1098
1099 312
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1100 312
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1101 312
        if (new_oc != NULL) {
1102 76
                CHECK_OBJ(new_oc, OBJCORE_MAGIC);
1103 76
                assert(oc->objhead == new_oc->objhead);
1104 76
        }
1105
1106 312
        Lck_Lock(&oc->objhead->mtx);
1107 312
        oc->flags |= OC_F_DYING;
1108 312
        Lck_Unlock(&oc->objhead->mtx);
1109 312
        EXP_Remove(oc, new_oc);
1110 312
}
1111
1112
/*====================================================================
1113
 * HSH_Snipe()
1114
 *
1115
 * If objcore is idle, gain a ref and mark it dead.
1116
 */
1117
1118
int
1119 11
HSH_Snipe(const struct worker *wrk, struct objcore *oc)
1120
{
1121 11
        int retval = 0;
1122
1123 11
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1124 11
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1125 11
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1126
1127 11
        if (oc->refcnt == 1 && !Lck_Trylock(&oc->objhead->mtx)) {
1128 11
                if (oc->refcnt == 1 && !(oc->flags & OC_F_DYING)) {
1129 11
                        oc->flags |= OC_F_DYING;
1130 11
                        oc->refcnt++;
1131 11
                        retval = 1;
1132 11
                }
1133 11
                Lck_Unlock(&oc->objhead->mtx);
1134 11
        }
1135 11
        if (retval)
1136 11
                EXP_Remove(oc, NULL);
1137 11
        return (retval);
1138
}
1139
1140
1141
/*---------------------------------------------------------------------
1142
 * Gain a reference on an objcore
1143
 */
1144
1145
void
1146 2451
HSH_Ref(struct objcore *oc)
1147
{
1148
        struct objhead *oh;
1149
1150 2451
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1151 2451
        oh = oc->objhead;
1152 2451
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1153 2451
        Lck_Lock(&oh->mtx);
1154 2451
        assert(oc->refcnt > 0);
1155 2451
        oc->refcnt++;
1156 2451
        Lck_Unlock(&oh->mtx);
1157 2451
}
1158
1159
/*---------------------------------------------------------------------
1160
 * Gain a reference on the busyobj, if the objcore has one
1161
 */
1162
1163
struct boc *
1164 9596
HSH_RefBoc(const struct objcore *oc)
1165
{
1166
        struct objhead *oh;
1167
        struct boc *boc;
1168
1169 9596
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1170 9596
        oh = oc->objhead;
1171 9596
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1172 9596
        if (oc->boc == NULL)
1173 5647
                return (NULL);
1174 3949
        Lck_Lock(&oh->mtx);
1175 3949
        assert(oc->refcnt > 0);
1176 3949
        boc = oc->boc;
1177 3949
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
1178 3949
        if (boc != NULL) {
1179 3949
                assert(boc->refcount > 0);
1180 3949
                if (boc->state < BOS_FINISHED)
1181 3929
                        boc->refcount++;
1182
                else
1183 20
                        boc = NULL;
1184 3949
        }
1185 3949
        Lck_Unlock(&oh->mtx);
1186 3949
        return (boc);
1187 9596
}
1188
1189
void
1190 6850
HSH_DerefBoc(struct worker *wrk, struct objcore *oc)
1191
{
1192
        struct boc *boc;
1193
        unsigned r;
1194
1195 6850
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1196 6850
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1197 6850
        boc = oc->boc;
1198 6850
        CHECK_OBJ_NOTNULL(boc, BOC_MAGIC);
1199 6850
        Lck_Lock(&oc->objhead->mtx);
1200 6850
        assert(oc->refcnt > 0);
1201 6850
        assert(boc->refcount > 0);
1202 6850
        r = --boc->refcount;
1203 6850
        if (r == 0)
1204 2921
                oc->boc = NULL;
1205 6850
        Lck_Unlock(&oc->objhead->mtx);
1206 6850
        if (r == 0)
1207 2921
                ObjBocDone(wrk, oc, &boc);
1208 6850
}
1209
1210
/*--------------------------------------------------------------------
1211
 * Dereference objcore
1212
 *
1213
 * Returns zero if target was destroyed.
1214
 */
1215
1216
int
1217 7126
HSH_DerefObjCore(struct worker *wrk, struct objcore **ocp)
1218
{
1219
        struct objcore *oc;
1220
        struct objhead *oh;
1221
1222 7126
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1223 7126
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1224 7126
        assert(oc->refcnt > 0);
1225
1226 7126
        oh = oc->objhead;
1227 7126
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1228
1229 7126
        Lck_Lock(&oh->mtx);
1230 7126
        return (hsh_deref_objcore_unlock(wrk, &oc));
1231
}
1232
1233
static int
1234 7162
hsh_deref_objcore_unlock(struct worker *wrk, struct objcore **ocp)
1235
{
1236
        struct objcore *oc;
1237
        struct objhead *oh;
1238
        int r;
1239
1240 7162
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1241 7162
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1242 7162
        assert(oc->refcnt > 0);
1243
1244 7162
        oh = oc->objhead;
1245 7162
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1246
1247 7162
        Lck_AssertHeld(&oh->mtx);
1248 7162
        assert(oh->refcnt > 0);
1249 7162
        r = --oc->refcnt;
1250 7162
        if (!r)
1251 1877
                VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1252 7162
        Lck_Unlock(&oh->mtx);
1253 7162
        if (r != 0)
1254 5285
                return (r);
1255
1256 1877
        AZ(oc->flags & OC_F_BUSY);
1257 1877
        AZ(oc->exp_flags);
1258
1259 1877
        BAN_DestroyObj(oc);
1260 1877
        AZ(oc->ban);
1261
1262 1877
        if (oc->stobj->stevedore != NULL)
1263 1790
                ObjFreeObj(wrk, oc);
1264 1877
        ObjDestroy(wrk, &oc);
1265
1266
        /* Drop our ref on the objhead */
1267 1877
        assert(oh->refcnt > 0);
1268 1877
        (void)hsh_deref_objhead(wrk, &oh);
1269 1877
        return (0);
1270 7162
}
1271
1272
static int
1273 2961
hsh_deref_objhead_unlock(struct worker *wrk, struct objhead **poh,
1274
    struct objcore *oc)
1275
{
1276
        struct objhead *oh;
1277
        struct rush rush;
1278
        int r;
1279
1280 2961
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1281 2961
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1282
1283 2961
        Lck_AssertHeld(&oh->mtx);
1284
1285 2961
        if (oh >= private_ohs && oh < private_ohs + vcountof(private_ohs)) {
1286 1416
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1287 1416
                assert(oh->refcnt > 1);
1288 1416
                oh->refcnt--;
1289 1416
                Lck_Unlock(&oh->mtx);
1290 1416
                return (1);
1291
        }
1292
1293
        //lint --e{661}
1294
        //lint -specific(-e661)
1295
        //
1296
        // because of the static array, flexelint thinks that all ohs were from
1297
        // the static array :( the above suppression applies to the remainder of
1298
        // this function body and specific walks involving this function
1299
1300 1545
        INIT_OBJ(&rush, RUSH_MAGIC);
1301 1545
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1302 7
                assert(oh->refcnt > 1);
1303 7
                hsh_rush1(wrk, oc, &rush);
1304 7
        }
1305
1306 1545
        if (oh->refcnt == 1)
1307 181
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1308
1309 1545
        assert(oh->refcnt > 0);
1310 1545
        r = hash->deref(wrk, oh); /* Unlocks oh->mtx */
1311 1545
        hsh_rush2(wrk, &rush);
1312 1545
        return (r);
1313 2961
}
1314
1315
static int
1316 1877
hsh_deref_objhead(struct worker *wrk, struct objhead **poh)
1317
{
1318
        struct objhead *oh;
1319
1320 1877
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1321 1877
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1322
1323 1877
        Lck_Lock(&oh->mtx);
1324 1877
        return (hsh_deref_objhead_unlock(wrk, &oh, NULL));
1325
}
1326
1327
void
1328 949
HSH_Init(const struct hash_slinger *slinger)
1329
{
1330
1331 949
        assert(DIGEST_LEN == VSHA256_LEN);      /* avoid #include pollution */
1332 949
        hash = slinger;
1333 949
        if (hash->start != NULL)
1334 949
                hash->start();
1335 122421
        for (struct objhead *oh = private_ohs;
1336 122421
            oh < private_ohs + vcountof(private_ohs);
1337 121472
            oh++) {
1338 121472
                hsh_initobjhead(oh);
1339 121472
                assert(oh->refcnt == 1);
1340 121472
        }
1341 949
}