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 246111
hsh_initobjhead(struct objhead *oh)
99
{
100
101 246111
        XXXAN(oh);
102 246111
        INIT_OBJ(oh, OBJHEAD_MAGIC);
103 246111
        oh->refcnt = 1;
104 246111
        oh->waitinglist_gen = 1;
105 246111
        VTAILQ_INIT(&oh->objcs);
106 246111
        VTAILQ_INIT(&oh->waitinglist);
107 246111
        Lck_New(&oh->mtx, lck_objhdr);
108 246111
}
109
110
static struct objhead *
111 3167
hsh_newobjhead(void)
112
{
113 3167
        struct objhead *oh = malloc(sizeof *oh);
114 3167
        hsh_initobjhead(oh);
115 3167
        return (oh);
116
}
117
118
/*---------------------------------------------------------------------*/
119
/* Precreate an objhead and object for later use */
120
static void
121 5364
hsh_prealloc(struct worker *wrk)
122
{
123
124 5364
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
125
126 5364
        if (wrk->wpriv->nobjcore == NULL)
127 3626
                wrk->wpriv->nobjcore = ObjNew(wrk);
128 5364
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);
129
130 5364
        if (wrk->wpriv->nobjhead == NULL) {
131 3167
                wrk->wpriv->nobjhead = hsh_newobjhead();
132 3167
                wrk->stats->n_objecthead++;
133 3167
        }
134 5364
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
135
136 5364
        if (hash->prep != NULL)
137 5352
                hash->prep(wrk);
138 5364
}
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 2832
fib(uint64_t n, uint8_t bits)
145
{
146 2832
        const uint64_t gr = 11400714819323198485LLU;
147
        uint64_t r;
148
149 2832
        r = n * gr;
150 2832
        r >>= (sizeof(gr) * 8) - bits;
151 2832
        assert(r < (size_t)1 << bits);
152 2832
        return ((size_t)r);
153
}
154
155
struct objcore *
156 2832
HSH_Private(const struct worker *wrk)
157
{
158
        struct objcore *oc;
159
        struct objhead *oh;
160
161 2832
        oh = &private_ohs[fib((uintptr_t)wrk, PRIVATE_OH_EXP)];
162 2832
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
163
164 2832
        oc = ObjNew(wrk);
165 2832
        AN(oc);
166 2832
        oc->refcnt = 1;
167 2832
        oc->objhead = oh;
168 2832
        oc->flags |= OC_F_PRIVATE;
169 2832
        Lck_Lock(&oh->mtx);
170 2832
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
171 2832
        oh->refcnt++;
172 2832
        Lck_Unlock(&oh->mtx);
173 2832
        return (oc);
174
}
175
176
/*---------------------------------------------------------------------*/
177
178
void
179 1914
HSH_Cleanup(const struct worker *wrk)
180
{
181
182 1914
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
183 1914
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
184 1914
        if (wrk->wpriv->nobjcore != NULL)
185 4
                ObjDestroy(wrk, &wrk->wpriv->nobjcore);
186
187 1914
        if (wrk->wpriv->nobjhead != NULL) {
188 4
                CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
189 4
                Lck_Delete(&wrk->wpriv->nobjhead->mtx);
190 4
                FREE_OBJ(wrk->wpriv->nobjhead);
191 4
                wrk->stats->n_objecthead--;
192 4
        }
193 1914
        if (wrk->wpriv->nhashpriv != NULL) {
194
                /* XXX: If needed, add slinger method for this */
195 4
                free(wrk->wpriv->nhashpriv);
196 4
                wrk->wpriv->nhashpriv = NULL;
197 4
        }
198 1914
}
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 29626
HSH_AddString(struct req *req, void *ctx, const char *str)
216
{
217
218 29626
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
219 29626
        AN(ctx);
220 29626
        if (str != NULL) {
221 14812
                VSHA256_Update(ctx, str, strlen(str));
222 14812
                VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
223 14812
        } else
224 14814
                VSHA256_Update(ctx, &str, 1);
225 29626
}
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 36
hsh_testmagic(void *result)
280
{
281
        size_t i, j;
282
        static size_t nused = 0;
283
284 180
        for (i = 0; i < nused; i++)
285 162
                if (!memcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
286 18
                        break;
287 36
        if (i == nused && i < HSH_NMAGIC)
288 18
                memcpy(hsh_magiclist[nused++].was, result, VSHA256_LEN);
289 36
        if (i == nused)
290 0
                return;
291 36
        assert(i < HSH_NMAGIC);
292 36
        fprintf(stderr, "HASHMAGIC: <");
293 1188
        for (j = 0; j < VSHA256_LEN; j++)
294 1152
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
295 36
        fprintf(stderr, "> -> <");
296 36
        memcpy(result, hsh_magiclist[i].now, VSHA256_LEN);
297 1188
        for (j = 0; j < VSHA256_LEN; j++)
298 1152
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
299 36
        fprintf(stderr, ">\n");
300 36
}
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 34
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 34
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
316 34
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
317 34
        AN(digest);
318 34
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
319 34
        AN(ban);
320 34
        AZ(oc->flags & OC_F_BUSY);
321 34
        AZ(oc->flags & OC_F_PRIVATE);
322 34
        assert(oc->refcnt == 1);
323 34
        INIT_OBJ(&rush, RUSH_MAGIC);
324
325 34
        hsh_prealloc(wrk);
326
327 34
        AN(wrk->wpriv->nobjhead);
328 34
        oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
329 34
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
330 34
        Lck_AssertHeld(&oh->mtx);
331 34
        assert(oh->refcnt > 0);
332
333
        /* Mark object busy and insert (precreated) objcore in
334
           objecthead. The new object inherits our objhead reference. */
335 34
        oc->objhead = oh;
336 34
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
337 34
        EXP_RefNewObjcore(oc);
338 34
        Lck_Unlock(&oh->mtx);
339
340 34
        BAN_RefBan(oc, ban);
341 34
        AN(oc->ban);
342
343
        /* Move the object first in the oh list, unbusy it and run the
344
           waitinglist if necessary */
345 34
        Lck_Lock(&oh->mtx);
346 34
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
347 34
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
348 34
        if (!VTAILQ_EMPTY(&oh->waitinglist))
349 0
                hsh_rush1(wrk, oc, &rush);
350 34
        Lck_Unlock(&oh->mtx);
351 34
        hsh_rush2(wrk, &rush);
352
353 34
        EXP_Insert(wrk, oc);
354 34
}
355
356
/*---------------------------------------------------------------------
357
 */
358
359
static struct objcore *
360 3047
hsh_insert_busyobj(const struct worker *wrk, struct objhead *oh)
361
{
362
        struct objcore *oc;
363
364 3047
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
365 3047
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
366 3047
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
367 3047
        Lck_AssertHeld(&oh->mtx);
368
369 3047
        oc = wrk->wpriv->nobjcore;
370 3047
        wrk->wpriv->nobjcore = NULL;
371 3047
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
372
373 3047
        AZ(oc->flags & OC_F_BUSY);
374 3047
        oc->flags |= OC_F_BUSY;
375 3047
        oc->refcnt = 1;         /* Owned by busyobj */
376 3047
        oc->objhead = oh;
377 3047
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
378 3047
        return (oc);
379
}
380
381
/*---------------------------------------------------------------------
382
 */
383
384
static int
385 7858
hsh_vry_match(const struct req *req, struct objcore *oc, const uint8_t *vary)
386
{
387
388 7858
        if (req->hash_ignore_vary)
389 2
                return (1);
390 7856
        if (vary == NULL) {
391 7852
                if (! ObjHasAttr(req->wrk, oc, OA_VARY))
392 2208
                        return (1);
393 5644
                vary = ObjGetAttr(req->wrk, oc, OA_VARY, NULL);
394 5644
                AN(vary);
395 5644
        }
396 5648
        return (VRY_Match(req, vary));
397 7858
}
398
399
static unsigned
400 113
hsh_rush_match(const struct req *req)
401
{
402
        struct objhead *oh;
403
        struct objcore *oc;
404
405 113
        oc = req->objcore;
406 113
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
407 113
        assert(oc->refcnt > 0);
408
409 113
        AZ(oc->flags & OC_F_BUSY);
410 113
        AZ(oc->flags & OC_F_PRIVATE);
411 113
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_HFM|OC_F_HFP|OC_F_CANCEL|
412
            OC_F_FAILED))
413 24
                return (0);
414
415 89
        if (req->vcf != NULL) /* NB: must operate under oh lock. */
416 0
                return (0);
417
418 89
        oh = oc->objhead;
419 89
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420
421 89
        return (hsh_vry_match(req, oc, NULL));
422 113
}
423
424
/*---------------------------------------------------------------------
425
 */
426
427
enum lookup_e
428 5330
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 5330
        unsigned xid = 0;
439
        unsigned ban_checks;
440
        unsigned ban_any_variant;
441 5330
        float dttl = 0.0;
442
443 5330
        AN(ocp);
444 5330
        *ocp = NULL;
445 5330
        AN(bocp);
446 5330
        *bocp = NULL;
447
448 5330
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
449 5330
        wrk = req->wrk;
450 5330
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
451 5330
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
452 5330
        CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
453 5330
        CHECK_OBJ_ORNULL(req->objcore, OBJCORE_MAGIC);
454 5330
        CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
455 5330
        AN(hash);
456
457 5330
        hsh_prealloc(wrk);
458 5330
        if (DO_DEBUG(DBG_HASHEDGE))
459 36
                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 5330
        if (req->objcore != NULL && hsh_rush_match(req)) {
468 85
                TAKE_OBJ_NOTNULL(oc, &req->objcore, OBJCORE_MAGIC);
469 85
                *ocp = oc;
470 85
                oh = oc->objhead;
471 85
                Lck_Lock(&oh->mtx);
472 85
                oc->hits++;
473 85
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
474 85
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
475 85
                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 85
                return (HSH_HIT);
482
        }
483
484 5245
        if (req->objcore != NULL) {
485 28
                oh = req->objcore->objhead;
486 28
                (void)HSH_DerefObjCore(wrk, &req->objcore);
487 28
                Lck_Lock(&oh->mtx);
488 28
        } else {
489 5217
                AN(wrk->wpriv->nobjhead);
490 5217
                oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
491
        }
492
493 5245
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
494 5245
        Lck_AssertHeld(&oh->mtx);
495
496 5245
        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 30
                *bocp = hsh_insert_busyobj(wrk, oh);
500
                /* NB: no deref of objhead, new object inherits reference */
501 30
                Lck_Unlock(&oh->mtx);
502 30
                return (HSH_MISS);
503
        }
504
505 5215
        assert(oh->refcnt > 0);
506 5215
        busy_found = 0;
507 5215
        exp_oc = NULL;
508 5215
        exp_t_origin = 0.0;
509 5215
        ban_checks = 0;
510 5215
        ban_any_variant = cache_param->ban_any_variant;
511 11052
        VTAILQ_FOREACH(oc, &oh->objcs, hsh_list) {
512
                /* Must be at least our own ref + the objcore we examine */
513 7984
                assert(oh->refcnt > 1);
514 7984
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
515 7984
                assert(oc->objhead == oh);
516 7984
                assert(oc->refcnt > 0);
517
518 7984
                if (oc->flags & OC_F_DYING)
519 0
                        continue;
520 7984
                if (oc->flags & OC_F_FAILED)
521 0
                        continue;
522
523 7984
                CHECK_OBJ_ORNULL(oc->boc, BOC_MAGIC);
524 7984
                if (oc->flags & OC_F_BUSY) {
525 125
                        if (req->hash_ignore_busy)
526 2
                                continue;
527
528 123
                        if (oc->boc && oc->boc->vary != NULL &&
529 4
                            !hsh_vry_match(req, oc, oc->boc->vary)) {
530 2
                                wrk->strangelove++;
531 2
                                continue;
532
                        }
533
534 121
                        busy_found = 1;
535 121
                        continue;
536
                }
537
538 7859
                if (oc->ttl <= 0.)
539 94
                        continue;
540
541 7765
                if (ban_checks++ < ban_any_variant
542 7765
                    && BAN_CheckObject(wrk, oc, req)) {
543 0
                        oc->flags |= OC_F_DYING;
544 0
                        EXP_Remove(oc, NULL);
545 0
                        continue;
546
                }
547
548 7765
                if (!hsh_vry_match(req, oc, NULL)) {
549 5252
                        wrk->strangelove++;
550 5252
                        continue;
551
                }
552
553 2513
                if (ban_checks >= ban_any_variant
554 2513
                    && BAN_CheckObject(wrk, oc, req)) {
555 68
                        oc->flags |= OC_F_DYING;
556 68
                        EXP_Remove(oc, NULL);
557 68
                        continue;
558
                }
559
560 2445
                if (req->vcf != NULL) {
561 16
                        vr = req->vcf->func(req, &oc, &exp_oc, 0);
562 16
                        if (vr == VCF_CONTINUE)
563 8
                                continue;
564 8
                        if (vr == VCF_MISS) {
565 6
                                oc = NULL;
566 6
                                break;
567
                        }
568 2
                        if (vr == VCF_HIT)
569 2
                                break;
570 0
                        assert(vr == VCF_DEFAULT);
571 0
                }
572
573 2429
                if (EXP_Ttl(req, oc) > req->t_req) {
574 2139
                        assert(oh->refcnt > 1);
575 2139
                        assert(oc->objhead == oh);
576 2139
                        break;
577
                }
578
579 290
                if (EXP_Ttl(NULL, oc) <= req->t_req && /* ignore req.ttl */
580 282
                    oc->t_origin > exp_t_origin) {
581
                        /* record the newest object */
582 280
                        exp_oc = oc;
583 280
                        exp_t_origin = oc->t_origin;
584 280
                        assert(oh->refcnt > 1);
585 280
                        assert(exp_oc->objhead == oh);
586 280
                }
587 290
        }
588
589 5215
        if (req->vcf != NULL)
590 12
                (void)req->vcf->func(req, &oc, &exp_oc, 1);
591
592 5215
        if (oc != NULL && oc->flags & OC_F_HFP) {
593 22
                xid = VXID(ObjGetXID(wrk, oc));
594 22
                dttl = EXP_Dttl(req, oc);
595 22
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
596 22
                wrk->stats->cache_hitpass++;
597 22
                VSLb(req->vsl, SLT_HitPass, "%u %.6f", xid, dttl);
598 22
                return (HSH_HITPASS);
599
        }
600
601 5193
        if (oc != NULL) {
602 2121
                *ocp = oc;
603 2121
                oc->refcnt++;
604 2121
                if (oc->flags & OC_F_HFM) {
605 64
                        xid = VXID(ObjGetXID(wrk, oc));
606 64
                        dttl = EXP_Dttl(req, oc);
607 64
                        *bocp = hsh_insert_busyobj(wrk, oh);
608 64
                        Lck_Unlock(&oh->mtx);
609 64
                        wrk->stats->cache_hitmiss++;
610 64
                        VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
611 64
                        return (HSH_HITMISS);
612
                }
613 2057
                oc->hits++;
614 2057
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
615 2057
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
616 2057
                Req_LogHit(wrk, req, oc, boc_progress);
617 2057
                return (HSH_HIT);
618
        }
619
620 3072
        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 8
                xid = VXID(ObjGetXID(wrk, exp_oc));
628 8
                dttl = EXP_Dttl(req, exp_oc);
629 8
                *bocp = hsh_insert_busyobj(wrk, oh);
630 8
                Lck_Unlock(&oh->mtx);
631 8
                wrk->stats->cache_hitmiss++;
632 8
                VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
633 8
                return (HSH_HITMISS);
634
        }
635
636 3064
        if (exp_oc != NULL && exp_oc->boc != NULL)
637 10
                boc_progress = exp_oc->boc->fetched_so_far;
638
        else
639 3054
                boc_progress = -1;
640
641 3064
        if (!busy_found) {
642 2945
                *bocp = hsh_insert_busyobj(wrk, oh);
643
644 2945
                if (exp_oc != NULL) {
645 262
                        exp_oc->refcnt++;
646 262
                        *ocp = exp_oc;
647 262
                        if (EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
648 188
                                exp_oc->hits++;
649 188
                                Lck_Unlock(&oh->mtx);
650 188
                                Req_LogHit(wrk, req, exp_oc, boc_progress);
651 188
                                return (HSH_GRACE);
652
                        }
653 74
                }
654 2757
                Lck_Unlock(&oh->mtx);
655 2757
                return (HSH_MISS);
656
        }
657
658 119
        AN(busy_found);
659 119
        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 6
                exp_oc->refcnt++;
662 6
                *ocp = exp_oc;
663 6
                exp_oc->hits++;
664 6
                AN(hsh_deref_objhead_unlock(wrk, &oh, NULL));
665 6
                Req_LogHit(wrk, req, exp_oc, boc_progress);
666 6
                return (HSH_GRACE);
667
        }
668
669
        /* There are one or more busy objects, wait for them */
670 113
        VTAILQ_INSERT_TAIL(&oh->waitinglist, req, w_list);
671
672 113
        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 113
        assert(oh->refcnt > 1);
680
681 113
        req->wrk = NULL;
682 113
        req->waitinglist_gen = oh->waitinglist_gen;
683
684 113
        if (DO_DEBUG(DBG_WAITINGLIST))
685 44
                VSLb(req->vsl, SLT_Debug, "on waiting list <%p>", oh);
686
687 113
        Lck_Unlock(&oh->mtx);
688
689 113
        wrk->stats->busy_sleep++;
690 113
        return (HSH_BUSY);
691 5330
}
692
693
/*---------------------------------------------------------------------
694
 * Pick the req's we are going to rush from the waiting list
695
 */
696
697
static void
698 242
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 242
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
705 242
        CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
706 242
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
707 242
        VTAILQ_INIT(&r->reqs);
708
709 242
        if (oc == NULL)
710 2
                return;
711
712 240
        oh = oc->objhead;
713 240
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
714 240
        Lck_AssertHeld(&oh->mtx);
715
716 240
        AZ(oc->flags & OC_F_BUSY);
717 240
        AZ(oc->flags & OC_F_PRIVATE);
718 240
        max = cache_param->rush_exponent;
719 240
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_FAILED))
720 157
                max = 1;
721 240
        assert(max > 0);
722
723 240
        if (oc->waitinglist_gen == 0) {
724 228
                oc->waitinglist_gen = oh->waitinglist_gen;
725 228
                oh->waitinglist_gen++;
726 228
        }
727
728 353
        for (i = 0; i < max; i++) {
729 331
                req = VTAILQ_FIRST(&oh->waitinglist);
730 331
                if (req == NULL)
731 218
                        break;
732
733 113
                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 113
                if (req->waitinglist_gen > oc->waitinglist_gen)
748 0
                        break;
749
750 113
                AZ(req->wrk);
751 113
                VTAILQ_REMOVE(&oh->waitinglist, req, w_list);
752 113
                VTAILQ_INSERT_TAIL(&r->reqs, req, w_list);
753 113
                req->objcore = oc;
754 113
                oc->refcnt++;
755 113
                wrk->stats->busy_wakeup++;
756 113
        }
757 242
}
758
759
/*---------------------------------------------------------------------
760
 * Rush req's that came from waiting list.
761
 */
762
763
static void
764 6215
hsh_rush2(struct worker *wrk, struct rush *r)
765
{
766
        struct req *req;
767
768 6215
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
769 6215
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
770
771 6328
        while (!VTAILQ_EMPTY(&r->reqs)) {
772 113
                req = VTAILQ_FIRST(&r->reqs);
773 113
                CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
774 113
                VTAILQ_REMOVE(&r->reqs, req, w_list);
775 113
                DSL(DBG_WAITINGLIST, req->vsl->wid, "off waiting list");
776 113
                if (req->transport->reembark != NULL) {
777
                        // For ESI includes
778 3
                        req->transport->reembark(wrk, req);
779 3
                } 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 110
                        AZ(Pool_Task(req->sp->pool, req->task, TASK_QUEUE_RUSH));
787
                }
788
        }
789 6215
}
790
791
/*---------------------------------------------------------------------
792
 * Purge an entire objhead
793
 */
794
795
unsigned
796 44
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 44
        unsigned i, j, n, n_max, total = 0;
801
        int is_purge;
802
803 44
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
804 44
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
805
806 44
        is_purge = (ttl == 0 && grace == 0 && keep == 0);
807 44
        n_max = WS_ReserveLumps(wrk->aws, sizeof *ocp);
808 44
        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 44
                ocp = WS_Reservation(wrk->aws);
816 44
        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 44
        Lck_Lock(&oh->mtx);
828 44
        oc = VTAILQ_FIRST(&oh->objcs);
829 44
        n = 0;
830 46
        while (1) {
831 268
                for (; n < n_max && oc != NULL; oc = VTAILQ_NEXT(oc, hsh_list))
832
                {
833 222
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
834 222
                        assert(oc->objhead == oh);
835 222
                        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 38
                                continue;
842
                        }
843 184
                        if (oc->flags & OC_F_DYING)
844 0
                                continue;
845 184
                        if (is_purge)
846 164
                                oc->flags |= OC_F_DYING;
847 184
                        oc->refcnt++;
848 184
                        ocp[n++] = oc;
849 184
                }
850
851 46
                Lck_Unlock(&oh->mtx);
852
853 46
                if (n == 0) {
854
                        /* No eligible objcores found. We are finished. */
855 8
                        break;
856
                }
857
858 38
                j = n;
859 38
                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 2
                        j--;
867 2
                        assert(j >= 1); /* True because n_max >= 2 */
868 2
                }
869 222
                for (i = 0; i < j; i++) {
870 184
                        CHECK_OBJ_NOTNULL(ocp[i], OBJCORE_MAGIC);
871 184
                        if (is_purge)
872 164
                                EXP_Remove(ocp[i], NULL);
873
                        else
874 20
                                EXP_Reduce(ocp[i], ttl_now, ttl, grace, keep);
875 184
                        (void)HSH_DerefObjCore(wrk, &ocp[i]);
876 184
                        AZ(ocp[i]);
877 184
                        total++;
878 184
                }
879
880 38
                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 36
                        break;
885
                }
886
887 2
                Lck_Lock(&oh->mtx);
888
889
                /* Move the bookmark first and continue scanning the
890
                 * objcores */
891 2
                CHECK_OBJ_NOTNULL(ocp[j], OBJCORE_MAGIC);
892 2
                ocp[0] = ocp[j];
893 2
                n = 1;
894 2
                oc = VTAILQ_NEXT(ocp[0], hsh_list);
895 2
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
896
        }
897
898 44
        WS_Release(wrk->aws, 0);
899 44
        if (is_purge)
900 24
                Pool_PurgeStat(total);
901 44
        return (total);
902
}
903
904
/*---------------------------------------------------------------------
905
 * Fail an objcore
906
 */
907
908
void
909 136
HSH_Fail(struct worker *wrk, struct objcore *oc)
910
{
911
        struct objhead *oh;
912
        struct rush rush;
913
914 136
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
915 136
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
916 136
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
917 136
        oh = oc->objhead;
918 136
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
919 136
        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 136
        if (oc->boc->state < BOS_STREAM)
932 102
                assert(oc->flags & (OC_F_BUSY|OC_F_PRIVATE));
933
        else
934 34
                assert(oc->stobj->stevedore != NULL);
935
936 136
        Lck_Lock(&oh->mtx);
937 136
        oc->flags |= OC_F_FAILED;
938 136
        if (oc->flags & OC_F_BUSY) {
939 90
                oc->flags &= ~OC_F_BUSY;
940 90
                hsh_rush1(wrk, oc, &rush);
941 90
        }
942 136
        Lck_Unlock(&oh->mtx);
943 136
        hsh_rush2(wrk, &rush);
944 136
}
945
946
/*---------------------------------------------------------------------
947
 * Mark a fetch we will not need as cancelled
948
 */
949
950
static void
951 708
hsh_cancel(struct objcore *oc)
952
{
953
        struct objhead *oh;
954
955 708
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
956 708
        oh = oc->objhead;
957 708
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
958
959 708
        Lck_Lock(&oh->mtx);
960 708
        oc->flags |= OC_F_CANCEL;
961 708
        Lck_Unlock(&oh->mtx);
962 708
}
963
964
/*---------------------------------------------------------------------
965
 * Cancel a fetch when the client does not need it any more
966
 */
967
968
void
969 7686
HSH_Cancel(struct worker *wrk, struct objcore *oc, struct boc *boc)
970
{
971 7686
        struct boc *bocref = NULL;
972
973 7686
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
974
975 7686
        if ((oc->flags & OC_F_TRANSIENT) == 0)
976 4888
                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 2798
        if (boc == NULL)
983 2098
                bocref = boc = HSH_RefBoc(oc);
984
985 2798
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
986
987 2798
        if (oc->flags & OC_F_HFP)
988 44
                AN(oc->flags & OC_F_HFM);
989
990 2798
        if (boc != NULL) {
991 708
                hsh_cancel(oc);
992 708
                ObjWaitState(oc, BOS_FINISHED);
993 708
        }
994
995 2798
        if (bocref != NULL)
996 8
                HSH_DerefBoc(wrk, oc);
997
998 2798
        ObjSlim(wrk, oc);
999 7686
}
1000
1001
/*---------------------------------------------------------------------
1002
 * Withdraw an objcore that will not proceed with a fetch.
1003
 */
1004
1005
void
1006 67
HSH_Withdraw(struct worker *wrk, struct objcore **ocp)
1007
{
1008
        struct objhead *oh;
1009
        struct objcore *oc;
1010
        struct rush rush;
1011
1012 67
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1013 67
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1014 67
        INIT_OBJ(&rush, RUSH_MAGIC);
1015
1016 67
        oh = oc->objhead;
1017 67
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1018
1019 67
        Lck_Lock(&oh->mtx);
1020 67
        AZ(oc->stobj->stevedore);
1021 67
        AN(oc->flags & OC_F_BUSY);
1022 67
        assert(oc->refcnt == 1);
1023 67
        assert(oh->refcnt > 0);
1024 67
        oc->flags &= ~OC_F_BUSY;
1025 67
        oc->flags |= OC_F_WITHDRAWN;
1026 67
        hsh_rush1(wrk, oc, &rush); /* grabs up to 1 oc ref */
1027 67
        assert(hsh_deref_objcore_unlock(wrk, &oc) <= 1);
1028
1029 67
        hsh_rush2(wrk, &rush);
1030 67
}
1031
1032
/*---------------------------------------------------------------------
1033
 * Unbusy an objcore when the object is completely fetched.
1034
 */
1035
1036
void
1037 4444
HSH_Unbusy(struct worker *wrk, struct objcore *oc)
1038
{
1039
        struct objhead *oh;
1040
        struct rush rush;
1041
1042 4444
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1043 4444
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1044 4444
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
1045
1046 4444
        oh = oc->objhead;
1047 4444
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1048
1049 4444
        AN(oc->stobj->stevedore);
1050 4444
        assert(oh->refcnt > 0);
1051 4444
        assert(oc->refcnt > 0);
1052
1053 4444
        if (oc->flags & OC_F_PRIVATE) {
1054 1556
                AZ(oc->flags & OC_F_BUSY);
1055 1556
                return;
1056
        }
1057
1058 2888
        AN(oc->flags & OC_F_BUSY);
1059 2888
        INIT_OBJ(&rush, RUSH_MAGIC);
1060
1061 2888
        BAN_NewObjCore(oc);
1062 2888
        AN(oc->ban);
1063
1064
        /* XXX: pretouch neighbors on oh->objcs to prevent page-on under mtx */
1065 2888
        Lck_Lock(&oh->mtx);
1066 2888
        assert(oh->refcnt > 0);
1067 2888
        assert(oc->refcnt > 0);
1068 2888
        EXP_RefNewObjcore(oc); /* Takes a ref for expiry */
1069
        /* XXX: strictly speaking, we should sort in Date: order. */
1070 2888
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1071 2888
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
1072 2888
        oc->flags &= ~OC_F_BUSY;
1073 2888
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1074 69
                assert(oh->refcnt > 1);
1075 69
                hsh_rush1(wrk, oc, &rush);
1076 69
        }
1077 2888
        Lck_Unlock(&oh->mtx);
1078 2888
        EXP_Insert(wrk, oc);
1079 2888
        hsh_rush2(wrk, &rush);
1080 4444
}
1081
1082
/*====================================================================
1083
 * HSH_Kill()
1084
 *
1085
 * It's dead Jim, kick it...
1086
 */
1087
1088
void
1089 472
HSH_Kill(struct objcore *oc)
1090
{
1091
1092 472
        HSH_Replace(oc, NULL);
1093 472
}
1094
1095
void
1096 623
HSH_Replace(struct objcore *oc, const struct objcore *new_oc)
1097
{
1098
1099 623
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1100 623
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1101 623
        if (new_oc != NULL) {
1102 151
                CHECK_OBJ(new_oc, OBJCORE_MAGIC);
1103 151
                assert(oc->objhead == new_oc->objhead);
1104 151
        }
1105
1106 623
        Lck_Lock(&oc->objhead->mtx);
1107 623
        oc->flags |= OC_F_DYING;
1108 623
        Lck_Unlock(&oc->objhead->mtx);
1109 623
        EXP_Remove(oc, new_oc);
1110 623
}
1111
1112
/*====================================================================
1113
 * HSH_Snipe()
1114
 *
1115
 * If objcore is idle, gain a ref and mark it dead.
1116
 */
1117
1118
int
1119 22
HSH_Snipe(const struct worker *wrk, struct objcore *oc)
1120
{
1121 22
        int retval = 0;
1122
1123 22
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1124 22
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1125 22
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1126
1127 22
        if (oc->refcnt == 1 && !Lck_Trylock(&oc->objhead->mtx)) {
1128 22
                if (oc->refcnt == 1 && !(oc->flags & OC_F_DYING)) {
1129 22
                        oc->flags |= OC_F_DYING;
1130 22
                        oc->refcnt++;
1131 22
                        retval = 1;
1132 22
                }
1133 22
                Lck_Unlock(&oc->objhead->mtx);
1134 22
        }
1135 22
        if (retval)
1136 22
                EXP_Remove(oc, NULL);
1137 22
        return (retval);
1138
}
1139
1140
1141
/*---------------------------------------------------------------------
1142
 * Gain a reference on an objcore
1143
 */
1144
1145
void
1146 4904
HSH_Ref(struct objcore *oc)
1147
{
1148
        struct objhead *oh;
1149
1150 4904
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1151 4904
        oh = oc->objhead;
1152 4904
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1153 4904
        Lck_Lock(&oh->mtx);
1154 4904
        assert(oc->refcnt > 0);
1155 4904
        oc->refcnt++;
1156 4904
        Lck_Unlock(&oh->mtx);
1157 4904
}
1158
1159
/*---------------------------------------------------------------------
1160
 * Gain a reference on the busyobj, if the objcore has one
1161
 */
1162
1163
struct boc *
1164 19195
HSH_RefBoc(const struct objcore *oc)
1165
{
1166
        struct objhead *oh;
1167
        struct boc *boc;
1168
1169 19195
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1170 19195
        oh = oc->objhead;
1171 19195
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1172 19195
        if (oc->boc == NULL)
1173 11288
                return (NULL);
1174 7907
        Lck_Lock(&oh->mtx);
1175 7907
        assert(oc->refcnt > 0);
1176 7907
        boc = oc->boc;
1177 7907
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
1178 7907
        if (boc != NULL) {
1179 7905
                assert(boc->refcount > 0);
1180 7905
                if (boc->state < BOS_FINISHED)
1181 7855
                        boc->refcount++;
1182
                else
1183 50
                        boc = NULL;
1184 7905
        }
1185 7907
        Lck_Unlock(&oh->mtx);
1186 7907
        return (boc);
1187 19193
}
1188
1189
void
1190 13694
HSH_DerefBoc(struct worker *wrk, struct objcore *oc)
1191
{
1192
        struct boc *boc;
1193
        unsigned r;
1194
1195 13694
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1196 13694
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1197 13694
        boc = oc->boc;
1198 13694
        CHECK_OBJ_NOTNULL(boc, BOC_MAGIC);
1199 13694
        Lck_Lock(&oc->objhead->mtx);
1200 13694
        assert(oc->refcnt > 0);
1201 13694
        assert(boc->refcount > 0);
1202 13694
        r = --boc->refcount;
1203 13694
        if (r == 0)
1204 5841
                oc->boc = NULL;
1205 13694
        Lck_Unlock(&oc->objhead->mtx);
1206 13694
        if (r == 0)
1207 5842
                ObjBocDone(wrk, oc, &boc);
1208 13694
}
1209
1210
/*--------------------------------------------------------------------
1211
 * Dereference objcore
1212
 *
1213
 * Returns zero if target was destroyed.
1214
 */
1215
1216
int
1217 14250
HSH_DerefObjCore(struct worker *wrk, struct objcore **ocp)
1218
{
1219
        struct objcore *oc;
1220
        struct objhead *oh;
1221
1222 14250
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1223 14250
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1224 14250
        assert(oc->refcnt > 0);
1225
1226 14250
        oh = oc->objhead;
1227 14250
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1228
1229 14250
        Lck_Lock(&oh->mtx);
1230 14250
        return (hsh_deref_objcore_unlock(wrk, &oc));
1231
}
1232
1233
static int
1234 14323
hsh_deref_objcore_unlock(struct worker *wrk, struct objcore **ocp)
1235
{
1236
        struct objcore *oc;
1237
        struct objhead *oh;
1238
        int r;
1239
1240 14323
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1241 14323
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1242 14323
        assert(oc->refcnt > 0);
1243
1244 14323
        oh = oc->objhead;
1245 14323
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1246
1247 14323
        Lck_AssertHeld(&oh->mtx);
1248 14323
        assert(oh->refcnt > 0);
1249 14323
        r = --oc->refcnt;
1250 14323
        if (!r)
1251 3752
                VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1252 14323
        Lck_Unlock(&oh->mtx);
1253 14323
        if (r != 0)
1254 10571
                return (r);
1255
1256 3752
        AZ(oc->flags & OC_F_BUSY);
1257 3752
        AZ(oc->exp_flags);
1258
1259 3752
        BAN_DestroyObj(oc);
1260 3752
        AZ(oc->ban);
1261
1262 3752
        if (oc->stobj->stevedore != NULL)
1263 3578
                ObjFreeObj(wrk, oc);
1264 3752
        ObjDestroy(wrk, &oc);
1265
1266
        /* Drop our ref on the objhead */
1267 3752
        assert(oh->refcnt > 0);
1268 3752
        (void)hsh_deref_objhead(wrk, &oh);
1269 3752
        return (0);
1270 14323
}
1271
1272
static int
1273 5922
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 5922
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1281 5922
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1282
1283 5922
        Lck_AssertHeld(&oh->mtx);
1284
1285 5922
        if (oh >= private_ohs && oh < private_ohs + vcountof(private_ohs)) {
1286 2832
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1287 2832
                assert(oh->refcnt > 1);
1288 2832
                oh->refcnt--;
1289 2832
                Lck_Unlock(&oh->mtx);
1290 2832
                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 3090
        INIT_OBJ(&rush, RUSH_MAGIC);
1301 3090
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1302 16
                assert(oh->refcnt > 1);
1303 16
                hsh_rush1(wrk, oc, &rush);
1304 16
        }
1305
1306 3090
        if (oh->refcnt == 1)
1307 362
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1308
1309 3090
        assert(oh->refcnt > 0);
1310 3090
        r = hash->deref(wrk, oh); /* Unlocks oh->mtx */
1311 3090
        hsh_rush2(wrk, &rush);
1312 3090
        return (r);
1313 5922
}
1314
1315
static int
1316 3752
hsh_deref_objhead(struct worker *wrk, struct objhead **poh)
1317
{
1318
        struct objhead *oh;
1319
1320 3752
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1321 3752
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1322
1323 3752
        Lck_Lock(&oh->mtx);
1324 3752
        return (hsh_deref_objhead_unlock(wrk, &oh, NULL));
1325
}
1326
1327
void
1328 1898
HSH_Init(const struct hash_slinger *slinger)
1329
{
1330
1331 1898
        assert(DIGEST_LEN == VSHA256_LEN);      /* avoid #include pollution */
1332 1898
        hash = slinger;
1333 1898
        if (hash->start != NULL)
1334 1898
                hash->start();
1335 244842
        for (struct objhead *oh = private_ohs;
1336 244842
            oh < private_ohs + vcountof(private_ohs);
1337 242944
            oh++) {
1338 242944
                hsh_initobjhead(oh);
1339 242944
                assert(oh->refcnt == 1);
1340 242944
        }
1341 1898
}