Code Coverage: vinyl-cache/bin/vinyld/cache/cache_hash.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
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_int.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 5353
#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
hsh_initobjhead(struct objhead *oh)
99 132982
{
100
101 132982
        XXXAN(oh);
102 132982
        INIT_OBJ(oh, OBJHEAD_MAGIC);
103 132982
        oh->refcnt = 1;
104 132982
        oh->waitinglist_gen = 1;
105 132982
        VTAILQ_INIT(&oh->objcs);
106 132982
        VTAILQ_INIT(&oh->waitinglist);
107 132982
        Lck_New(&oh->mtx, lck_objhdr);
108 132982
}
109
110
static struct objhead *
111
hsh_newobjhead(void)
112 1654
{
113 1654
        struct objhead *oh = malloc(sizeof *oh);
114 1654
        hsh_initobjhead(oh);
115 1654
        return (oh);
116 1654
}
117
118
/*---------------------------------------------------------------------*/
119
/* Precreate an objhead and object for later use */
120
static void
121
hsh_prealloc(struct worker *wrk)
122 3726
{
123
124 3726
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
125
126 3726
        if (wrk->wpriv->nobjcore == NULL)
127 1881
                wrk->wpriv->nobjcore = ObjNew(wrk);
128 3726
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);
129
130 3726
        if (wrk->wpriv->nobjhead == NULL) {
131 1654
                wrk->wpriv->nobjhead = hsh_newobjhead();
132 1654
                wrk->stats->n_objecthead++;
133 1654
        }
134 3726
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
135
136 3726
        if (hash->prep != NULL)
137 3719
                hash->prep(wrk);
138 3726
}
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
fib(uint64_t n, uint8_t bits)
145 5353
{
146 5353
        const uint64_t gr = 11400714819323198485LLU;
147 5353
        uint64_t r;
148
149 5353
        r = n * gr;
150 5353
        r >>= (sizeof(gr) * 8) - bits;
151 5353
        assert(r < (size_t)1 << bits);
152 5353
        return ((size_t)r);
153 5353
}
154
155
struct objcore *
156
HSH_Private(const struct worker *wrk)
157 5353
{
158 5353
        struct objcore *oc;
159 5353
        struct objhead *oh;
160
161 5353
        oh = &private_ohs[fib((uintptr_t)wrk, PRIVATE_OH_EXP)];
162 5353
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
163
164 5353
        oc = ObjNew(wrk);
165 5353
        AN(oc);
166 5353
        oc->refcnt = 1;
167 5353
        oc->objhead = oh;
168 5353
        oc->flags |= OC_F_PRIVATE;
169 5353
        Lck_Lock(&oh->mtx);
170 5353
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
171 5353
        oh->refcnt++;
172 5353
        Lck_Unlock(&oh->mtx);
173 5353
        return (oc);
174 5353
}
175
176
/*---------------------------------------------------------------------*/
177
178
void
179
HSH_Cleanup(const struct worker *wrk)
180 23786
{
181
182 23786
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
183 23786
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
184 23786
        if (wrk->wpriv->nobjcore != NULL)
185 306
                ObjDestroy(wrk, &wrk->wpriv->nobjcore);
186
187 23786
        if (wrk->wpriv->nobjhead != NULL) {
188 412
                CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
189 412
                Lck_Delete(&wrk->wpriv->nobjhead->mtx);
190 412
                FREE_OBJ(wrk->wpriv->nobjhead);
191 412
                wrk->stats->n_objecthead--;
192 412
        }
193 23786
        if (wrk->wpriv->nhashpriv != NULL) {
194
                /* XXX: If needed, add slinger method for this */
195 812
                free(wrk->wpriv->nhashpriv);
196 812
                wrk->wpriv->nhashpriv = NULL;
197 812
        }
198 23786
}
199
200
void
201
HSH_DeleteObjHead(const struct worker *wrk, struct objhead *oh)
202 0
{
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
HSH_AddString(struct req *req, void *ctx, const char *str)
216 25468
{
217
218 25468
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
219 25468
        AN(ctx);
220 25468
        if (str != NULL) {
221 12735
                VSHA256_Update(ctx, str, vstrlen(str));
222 12735
                VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
223 12735
        } else
224 12733
                VSHA256_Update(ctx, &str, 1);
225 25468
}
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 9
#define HSH_NMAGIC vcountof(hsh_magiclist)
277
278
static void
279
hsh_testmagic(void *result)
280 18
{
281 18
        size_t i, j;
282 18
        static size_t nused = 0;
283
284 90
        for (i = 0; i < nused; i++)
285 81
                if (!vmemcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
286 9
                        break;
287 18
        if (i == nused && i < HSH_NMAGIC)
288 9
                vmemcpy(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
        vmemcpy(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
HSH_Insert(struct worker *wrk, const void *digest, struct objcore *oc,
310
    struct ban *ban)
311 16
{
312 16
        struct objhead *oh;
313 16
        struct rush rush;
314
315 16
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
316 16
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
317 16
        AN(digest);
318 16
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
319 16
        AN(ban);
320 16
        AZ(oc->flags & (OC_F_BUSY | OC_F_PRIVATE));
321 16
        assert(oc->refcnt == 1);
322 16
        INIT_OBJ(&rush, RUSH_MAGIC);
323
324 16
        hsh_prealloc(wrk);
325
326 16
        AN(wrk->wpriv->nobjhead);
327 16
        oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
328 16
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
329 16
        Lck_AssertHeld(&oh->mtx);
330 16
        assert(oh->refcnt > 0);
331
332
        /* Mark object busy and insert (precreated) objcore in
333
           objecthead. The new object inherits our objhead reference. */
334 16
        oc->objhead = oh;
335 16
        oc->flags |= OC_F_BUSY;
336 16
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
337 16
        EXP_RefNewObjcore(oc);
338 16
        Lck_Unlock(&oh->mtx);
339
340 16
        BAN_RefBan(oc, ban);
341 16
        AN(oc->ban);
342
343
        /* Move the object first in the oh list, unbusy it and run the
344
           waitinglist if necessary */
345 16
        Lck_Lock(&oh->mtx);
346 16
        oc->flags &= ~OC_F_BUSY;
347 16
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
348 16
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
349 16
        if (!VTAILQ_EMPTY(&oh->waitinglist))
350 0
                hsh_rush1(wrk, oc, &rush);
351 16
        Lck_Unlock(&oh->mtx);
352 16
        hsh_rush2(wrk, &rush);
353
354 16
        EXP_Insert(wrk, oc);
355 16
}
356
357
/*---------------------------------------------------------------------
358
 */
359
360
static struct objcore *
361
hsh_insert_busyobj(const struct worker *wrk, struct objhead *oh)
362 1561
{
363 1561
        struct objcore *oc;
364
365 1561
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
366 1561
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
367 1561
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
368 1561
        Lck_AssertHeld(&oh->mtx);
369
370 1561
        oc = wrk->wpriv->nobjcore;
371 1561
        wrk->wpriv->nobjcore = NULL;
372 1561
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
373
374 1561
        AZ(oc->flags & OC_F_BUSY);
375 1561
        oc->flags |= OC_F_BUSY;
376 1561
        oc->refcnt = 1;         /* Owned by busyobj */
377 1561
        oc->objhead = oh;
378 1561
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
379 1561
        return (oc);
380 1561
}
381
382
/*---------------------------------------------------------------------
383
 */
384
385
static int
386
hsh_vry_match(const struct req *req, struct objcore *oc, const uint8_t *vary)
387 4941
{
388
389 4941
        if (req->hash_ignore_vary)
390 1
                return (1);
391 4940
        if (vary == NULL) {
392 4937
                if (! ObjHasAttr(req->wrk, oc, OA_VARY))
393 1626
                        return (1);
394 3311
                vary = ObjGetAttr(req->wrk, oc, OA_VARY, NULL);
395 3311
                AN(vary);
396 3311
        }
397 3314
        return (VRY_Match(req, vary));
398 4940
}
399
400
static unsigned
401
hsh_rush_match(const struct req *req)
402 59
{
403 59
        struct objcore *oc;
404
405 59
        oc = req->objcore;
406 59
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
407 59
        assert(oc->refcnt > 0);
408
409 59
        AZ(oc->flags & (OC_F_BUSY | OC_F_PRIVATE));
410 59
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_HFM|OC_F_HFP|OC_F_CANCEL|
411 59
            OC_F_FAILED))
412 12
                return (0);
413
414 47
        if (req->vcf != NULL) /* NB: must operate under oh lock. */
415 0
                return (0);
416
417 47
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
418
419 47
        return (hsh_vry_match(req, oc, NULL));
420 47
}
421
422
/*---------------------------------------------------------------------
423
 */
424
425
enum lookup_e
426
HSH_Lookup(struct req *req, struct objcore **ocp, struct objcore **bocp)
427 3712
{
428 3712
        struct worker *wrk;
429 3712
        struct objhead *oh;
430 3712
        struct objcore *oc;
431 3712
        struct objcore *exp_oc;
432 3712
        const struct vcf_return *vr;
433 3712
        vtim_real exp_t_origin;
434 3712
        int busy_found;
435 3712
        intmax_t boc_progress;
436 3712
        unsigned xid = 0;
437 3712
        unsigned ban_checks;
438 3712
        unsigned ban_any_variant;
439 3712
        float dttl = 0.0;
440
441 3712
        AN(ocp);
442 3712
        *ocp = NULL;
443 3712
        AN(bocp);
444 3712
        *bocp = NULL;
445
446 3712
        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
447 3712
        wrk = req->wrk;
448 3712
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
449 3712
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
450 3712
        CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
451 3712
        CHECK_OBJ_ORNULL(req->objcore, OBJCORE_MAGIC);
452 3712
        CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
453 3712
        AN(hash);
454
455 3712
        hsh_prealloc(wrk);
456 3712
        if (DO_DEBUG(DBG_HASHEDGE))
457 18
                hsh_testmagic(req->digest);
458
459
        /*
460
         * When a req rushes off the waiting list, it brings an implicit
461
         * oh refcnt acquired at disembark time and an oc ref (with its
462
         * own distinct oh ref) acquired during rush hour.
463
         */
464
465 3712
        if (req->objcore != NULL && hsh_rush_match(req)) {
466 45
                TAKE_OBJ_NOTNULL(oc, &req->objcore, OBJCORE_MAGIC);
467 45
                *ocp = oc;
468 45
                oh = oc->objhead;
469 45
                Lck_Lock(&oh->mtx);
470 45
                oc->hits++;
471 45
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
472 45
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
473 45
                Req_LogHit(wrk, req, oc, boc_progress);
474
                /* NB: since this hit comes from the waiting list instead of
475
                 * a regular lookup, grace is not considered. The object is
476
                 * fresh in the context of the waiting list, even expired: it
477
                 * was successfully just [re]validated by a fetch task.
478
                 */
479 45
                return (HSH_HIT);
480 45
        }
481
482 3667
        if (req->objcore != NULL) {
483 14
                oh = req->objcore->objhead;
484 14
                (void)HSH_DerefObjCore(wrk, &req->objcore);
485 14
                Lck_Lock(&oh->mtx);
486 3653
        } else {
487 3653
                AN(wrk->wpriv->nobjhead);
488 3653
                oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
489 3653
        }
490
491 3667
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
492 3667
        Lck_AssertHeld(&oh->mtx);
493
494 3667
        if (req->hash_always_miss) {
495
                /* XXX: should we do predictive Vary in this case ? */
496
                /* Insert new objcore in objecthead and release mutex */
497 17
                *bocp = hsh_insert_busyobj(wrk, oh);
498
                /* NB: no deref of objhead, new object inherits reference */
499 17
                Lck_Unlock(&oh->mtx);
500 17
                return (HSH_MISS);
501 17
        }
502
503 3650
        assert(oh->refcnt > 0);
504 3650
        busy_found = 0;
505 3650
        exp_oc = NULL;
506 3650
        exp_t_origin = 0.0;
507 3650
        ban_checks = 0;
508 3650
        ban_any_variant = cache_param->ban_any_variant;
509 5002
        VTAILQ_FOREACH(oc, &oh->objcs, hsh_list) {
510
                /* Must be at least our own ref + the objcore we examine */
511 5002
                assert(oh->refcnt > 1);
512 5002
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
513 5002
                assert(oc->objhead == oh);
514 5002
                assert(oc->refcnt > 0);
515
516 5002
                if (oc->flags & OC_F_DYING)
517 0
                        continue;
518 5002
                if (oc->flags & OC_F_FAILED)
519 0
                        continue;
520
521 5002
                CHECK_OBJ_ORNULL(oc->boc, BOC_MAGIC);
522 5002
                if (oc->flags & OC_F_BUSY) {
523 65
                        if (req->hash_ignore_busy)
524 1
                                continue;
525
526 64
                        if (oc->boc && oc->boc->vary != NULL &&
527 64
                            !hsh_vry_match(req, oc, oc->boc->vary)) {
528 1
                                wrk->strangelove++;
529 1
                                continue;
530 1
                        }
531
532 63
                        busy_found = 1;
533 63
                        continue;
534 64
                }
535
536 4937
                if (oc->ttl <= 0.)
537 47
                        continue;
538
539 4890
                if (ban_checks++ < ban_any_variant
540 4890
                    && BAN_CheckObject(wrk, oc, req)) {
541 0
                        oc->flags |= OC_F_DYING;
542 0
                        EXP_Remove(oc, NULL);
543 0
                        continue;
544 0
                }
545
546 4890
                if (!hsh_vry_match(req, oc, NULL)) {
547 2626
                        wrk->strangelove++;
548 2626
                        continue;
549 2626
                }
550
551 2264
                if (ban_checks >= ban_any_variant
552 2264
                    && BAN_CheckObject(wrk, oc, req)) {
553 34
                        oc->flags |= OC_F_DYING;
554 34
                        EXP_Remove(oc, NULL);
555 34
                        continue;
556 34
                }
557
558 2230
                if (req->vcf != NULL) {
559 8
                        vr = req->vcf->func(req, &oc, &exp_oc, 0);
560 8
                        if (vr == VCF_CONTINUE)
561 4
                                continue;
562 4
                        if (vr == VCF_MISS) {
563 3
                                oc = NULL;
564 3
                                break;
565 3
                        }
566 1
                        if (vr == VCF_HIT)
567 1
                                break;
568 0
                        assert(vr == VCF_DEFAULT);
569 0
                }
570
571 2222
                if (EXP_Ttl(req, oc) > req->t_req) {
572 2072
                        assert(oh->refcnt > 1);
573 2072
                        assert(oc->objhead == oh);
574 2072
                        break;
575 2072
                }
576
577 150
                if (EXP_Ttl(NULL, oc) <= req->t_req && /* ignore req.max_age */
578 150
                    oc->t_origin > exp_t_origin) {
579
                        /* record the newest object */
580 145
                        exp_oc = oc;
581 145
                        exp_t_origin = oc->t_origin;
582 145
                        assert(oh->refcnt > 1);
583 145
                        assert(exp_oc->objhead == oh);
584 145
                }
585 150
        }
586
587 3650
        if (req->vcf != NULL)
588 6
                (void)req->vcf->func(req, &oc, &exp_oc, 1);
589
590 3650
        if (oc != NULL && oc->flags & OC_F_HFP) {
591 13
                xid = VXID(ObjGetXID(wrk, oc));
592 13
                dttl = EXP_Dttl(req, oc);
593 13
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
594 13
                wrk->stats->cache_hitpass++;
595 13
                VSLb(req->vsl, SLT_HitPass, "%u %.6f", xid, dttl);
596 13
                return (HSH_HITPASS);
597 13
        }
598
599 3637
        if (oc != NULL) {
600 2061
                *ocp = oc;
601 2061
                oc->refcnt++;
602 2061
                if (oc->flags & OC_F_HFM) {
603 32
                        xid = VXID(ObjGetXID(wrk, oc));
604 32
                        dttl = EXP_Dttl(req, oc);
605 32
                        *bocp = hsh_insert_busyobj(wrk, oh);
606 32
                        Lck_Unlock(&oh->mtx);
607 32
                        wrk->stats->cache_hitmiss++;
608 32
                        VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
609 32
                        return (HSH_HITMISS);
610 32
                }
611 2029
                oc->hits++;
612 2029
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
613 2029
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
614 2029
                Req_LogHit(wrk, req, oc, boc_progress);
615 2029
                return (HSH_HIT);
616 2029
        }
617
618 1576
        if (exp_oc != NULL && exp_oc->flags & OC_F_HFM) {
619
                /*
620
                 * expired HFM ("grace/keep HFM")
621
                 *
622
                 * XXX should HFM objects actually have grace/keep ?
623
                 * XXX also:  why isn't *ocp = exp_oc ?
624
                 */
625 4
                xid = VXID(ObjGetXID(wrk, exp_oc));
626 4
                dttl = EXP_Dttl(req, exp_oc);
627 4
                *bocp = hsh_insert_busyobj(wrk, oh);
628 4
                Lck_Unlock(&oh->mtx);
629 4
                wrk->stats->cache_hitmiss++;
630 4
                VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
631 4
                return (HSH_HITMISS);
632 4
        }
633
634 1572
        if (exp_oc != NULL && exp_oc->boc != NULL)
635 5
                boc_progress = exp_oc->boc->fetched_so_far;
636 1567
        else
637 1567
                boc_progress = -1;
638
639 1572
        if (!busy_found) {
640 1508
                *bocp = hsh_insert_busyobj(wrk, oh);
641
642 1508
                if (exp_oc != NULL) {
643 136
                        exp_oc->refcnt++;
644 136
                        *ocp = exp_oc;
645 136
                        if (EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
646 96
                                exp_oc->hits++;
647 96
                                Lck_Unlock(&oh->mtx);
648 96
                                Req_LogHit(wrk, req, exp_oc, boc_progress);
649 96
                                return (HSH_GRACE);
650 96
                        }
651 136
                }
652 1412
                Lck_Unlock(&oh->mtx);
653 1412
                return (HSH_MISS);
654 1508
        }
655
656 64
        AN(busy_found);
657 64
        if (exp_oc != NULL && EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
658
                /* we do not wait on the busy object if in grace */
659 3
                exp_oc->refcnt++;
660 3
                *ocp = exp_oc;
661 3
                exp_oc->hits++;
662 3
                AN(hsh_deref_objhead_unlock(wrk, &oh, NULL));
663 3
                Req_LogHit(wrk, req, exp_oc, boc_progress);
664 3
                return (HSH_GRACE);
665 3
        }
666
667
        /* There are one or more busy objects, wait for them */
668 61
        VTAILQ_INSERT_TAIL(&oh->waitinglist, req, w_list);
669
670 61
        AZ(req->hash_ignore_busy);
671
672
        /*
673
         * The objhead reference is held by req while it is parked on the
674
         * waiting list. The oh pointer is taken back from the objcore that
675
         * triggers a rush of req off the waiting list.
676
         */
677 61
        assert(oh->refcnt > 1);
678
679 61
        req->wrk = NULL;
680 61
        req->waitinglist_gen = oh->waitinglist_gen;
681
682 61
        if (DO_DEBUG(DBG_WAITINGLIST))
683 22
                VSLb(req->vsl, SLT_Debug, "on waiting list <%p>", oh);
684
685 61
        Lck_Unlock(&oh->mtx);
686
687 61
        wrk->stats->busy_sleep++;
688 61
        return (HSH_BUSY);
689 61
}
690
691
/*---------------------------------------------------------------------
692
 * Pick the req's we are going to rush from the waiting list
693
 */
694
695
static void
696
hsh_rush1(const struct worker *wrk, struct objcore *oc, struct rush *r)
697 121
{
698 121
        struct objhead *oh;
699 121
        struct req *req;
700 121
        int i, max;
701
702 121
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
703 121
        CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
704 121
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
705 121
        VTAILQ_INIT(&r->reqs);
706
707 121
        if (oc == NULL)
708 1
                return;
709
710 120
        oh = oc->objhead;
711 120
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
712 120
        Lck_AssertHeld(&oh->mtx);
713
714 120
        AZ(oc->flags & (OC_F_BUSY | OC_F_PRIVATE));
715 120
        max = cache_param->rush_exponent;
716 120
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_FAILED))
717 78
                max = 1;
718 120
        assert(max > 0);
719
720 120
        if (oc->waitinglist_gen == 0) {
721 113
                oc->waitinglist_gen = oh->waitinglist_gen;
722 113
                oh->waitinglist_gen++;
723 113
        }
724
725 179
        for (i = 0; i < max; i++) {
726 167
                req = VTAILQ_FIRST(&oh->waitinglist);
727 167
                if (req == NULL)
728 108
                        break;
729
730 59
                CHECK_OBJ(req, REQ_MAGIC);
731
732
                /* NB: The waiting list is naturally sorted by generation.
733
                 *
734
                 * Because of the exponential nature of the rush, it is
735
                 * possible that new requests enter the waiting list before
736
                 * the rush for this oc completes. Because the OC_F_BUSY flag
737
                 * was cleared before the beginning of the rush, requests
738
                 * from a newer generation already got a chance to evaluate
739
                 * oc during a lookup and it didn't match their criteria.
740
                 *
741
                 * Therefore there's no point propagating the exponential
742
                 * rush of this oc when we see a newer generation.
743
                 */
744 59
                if (req->waitinglist_gen > oc->waitinglist_gen)
745 0
                        break;
746
747 59
                AZ(req->wrk);
748 59
                VTAILQ_REMOVE(&oh->waitinglist, req, w_list);
749 59
                VTAILQ_INSERT_TAIL(&r->reqs, req, w_list);
750 59
                req->objcore = oc;
751 59
                oc->refcnt++;
752 59
                wrk->stats->busy_wakeup++;
753 59
        }
754 120
}
755
756
/*---------------------------------------------------------------------
757
 * Rush req's that came from waiting list.
758
 */
759
760
static void
761
hsh_rush2(struct worker *wrk, struct rush *r)
762 4194
{
763 4194
        struct req *req;
764
765 4194
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
766 4194
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
767
768 4253
        while (!VTAILQ_EMPTY(&r->reqs)) {
769 59
                req = VTAILQ_FIRST(&r->reqs);
770 59
                CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
771 59
                VTAILQ_REMOVE(&r->reqs, req, w_list);
772 59
                DSL(DBG_WAITINGLIST, req->vsl->wid, "off waiting list");
773 59
                if (req->transport->reembark != NULL) {
774
                        // For ESI includes
775 1
                        req->transport->reembark(wrk, req);
776 58
                } else {
777
                        /*
778
                         * We ignore the queue limits which apply to new
779
                         * requests because if we fail to reschedule there
780
                         * may be vmod_privs to cleanup and we need a proper
781
                         * workerthread for that.
782
                         */
783 58
                        AZ(Pool_Task(req->sp->pool, req->task, TASK_QUEUE_RUSH));
784 58
                }
785 59
        }
786 4194
}
787
788
/*---------------------------------------------------------------------
789
 * Purge an entire objhead
790
 */
791
792
unsigned
793
HSH_Purge(struct worker *wrk, struct objhead *oh, vtim_real ttl_now,
794
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
795 24
{
796 24
        struct objcore *oc, *oc_nows[2], **ocp;
797 24
        unsigned i, j, n, n_max, total = 0;
798 24
        int is_purge;
799
800 24
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
801 24
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
802
803 24
        is_purge = (ttl == 0 && grace == 0 && keep == 0);
804 24
        n_max = WS_ReserveLumps(wrk->aws, sizeof *ocp);
805 24
        if (n_max < 2) {
806
                /* No space on the workspace. Give it a stack buffer of 2
807
                 * elements, which is the minimum for the algorithm
808
                 * below. */
809 0
                ocp = oc_nows;
810 0
                n_max = 2;
811 0
        } else
812 24
                ocp = WS_Reservation(wrk->aws);
813 24
        AN(ocp);
814
815
        /* Note: This algorithm uses OC references in the list as
816
         * bookmarks, in order to know how far into the list we were when
817
         * releasing the mutex partway through and want to resume
818
         * again. This relies on the list not being reordered while we are
819
         * not holding the mutex. The only place where that happens is in
820
         * HSH_Unbusy(), where an OC_F_BUSY OC is moved first in the
821
         * list. This does not cause problems because we skip OC_F_BUSY
822
         * OCs. */
823
824 24
        Lck_Lock(&oh->mtx);
825 24
        oc = VTAILQ_FIRST(&oh->objcs);
826 24
        n = 0;
827 25
        while (1) {
828 142
                for (; n < n_max && oc != NULL; oc = VTAILQ_NEXT(oc, hsh_list))
829 117
                {
830 117
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
831 117
                        assert(oc->objhead == oh);
832 117
                        if (oc->flags & OC_F_BUSY) {
833
                                /* We cannot purge busy objects here, because
834
                                 * their owners have special rights to them,
835
                                 * and may nuke them without concern for the
836
                                 * refcount, which by definition always must
837
                                 * be one, so they don't check. */
838 23
                                continue;
839 23
                        }
840 94
                        if (oc->flags & OC_F_DYING)
841 0
                                continue;
842 94
                        if (is_purge)
843 84
                                oc->flags |= OC_F_DYING;
844 94
                        oc->refcnt++;
845 94
                        ocp[n++] = oc;
846 94
                }
847
848 25
                Lck_Unlock(&oh->mtx);
849
850 25
                if (n == 0) {
851
                        /* No eligible objcores found. We are finished. */
852 4
                        break;
853 4
                }
854
855 21
                j = n;
856 21
                if (oc != NULL) {
857
                        /* There are more objects on the objhead that we
858
                         * have not yet looked at, but no more space on
859
                         * the objcore reference list. Do not process the
860
                         * last one, it will be used as the bookmark into
861
                         * the objcore list for the next iteration of the
862
                         * outer loop. */
863 1
                        j--;
864 1
                        assert(j >= 1); /* True because n_max >= 2 */
865 1
                }
866 115
                for (i = 0; i < j; i++) {
867 94
                        CHECK_OBJ_NOTNULL(ocp[i], OBJCORE_MAGIC);
868 94
                        if (is_purge)
869 84
                                EXP_Remove(ocp[i], NULL);
870 10
                        else
871 10
                                EXP_Reduce(ocp[i], ttl_now, ttl, grace, keep);
872 94
                        (void)HSH_DerefObjCore(wrk, &ocp[i]);
873 94
                        AZ(ocp[i]);
874 94
                        total++;
875 94
                }
876
877 21
                if (j == n) {
878
                        /* No bookmark set, that means we got to the end
879
                         * of the objcore list in the previous run and are
880
                         * finished. */
881 20
                        break;
882 20
                }
883
884 1
                Lck_Lock(&oh->mtx);
885
886
                /* Move the bookmark first and continue scanning the
887
                 * objcores */
888 1
                CHECK_OBJ_NOTNULL(ocp[j], OBJCORE_MAGIC);
889 1
                ocp[0] = ocp[j];
890 1
                n = 1;
891 1
                oc = VTAILQ_NEXT(ocp[0], hsh_list);
892 1
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
893 1
        }
894
895 24
        WS_Release(wrk->aws, 0);
896 24
        if (is_purge)
897 14
                Pool_PurgeStat(total);
898 24
        return (total);
899 24
}
900
901
/*---------------------------------------------------------------------
902
 * Fail an objcore
903
 */
904
905
void
906
HSH_Fail(struct worker *wrk, struct objcore *oc)
907 74
{
908 74
        struct objhead *oh;
909 74
        struct rush rush;
910
911 74
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
912 74
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
913 74
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
914 74
        oh = oc->objhead;
915 74
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
916 74
        INIT_OBJ(&rush, RUSH_MAGIC);
917
918
        /*
919
         * We either failed before the end of vcl_backend_response
920
         * and a cache miss has the busy bit, so that HSH_Lookup()
921
         * will not consider this oc, or an object hung off the oc
922
         * so that it can consider it.
923
         *
924
         * We can only fail an ongoing fetch in a backend context
925
         * so we can safely check the BOC state as it won't change
926
         * under our feet.
927
         */
928 74
        if (oc->boc->state < BOS_STREAM)
929 52
                assert(oc->flags & (OC_F_BUSY|OC_F_PRIVATE));
930 22
        else
931 22
                assert(oc->stobj->stevedore != NULL);
932
933 74
        Lck_Lock(&oh->mtx);
934 74
        oc->flags |= OC_F_FAILED;
935 74
        if (oc->flags & OC_F_BUSY) {
936 46
                oc->flags &= ~OC_F_BUSY;
937 46
                hsh_rush1(wrk, oc, &rush);
938 46
        }
939 74
        Lck_Unlock(&oh->mtx);
940 74
        hsh_rush2(wrk, &rush);
941 74
}
942
943
/*---------------------------------------------------------------------
944
 * Mark a fetch we will not need as cancelled
945
 */
946
947
static void
948
hsh_cancel(struct objcore *oc)
949 539
{
950 539
        struct objhead *oh;
951
952 539
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
953 539
        oh = oc->objhead;
954 539
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
955
956 539
        Lck_Lock(&oh->mtx);
957 539
        oc->flags |= OC_F_CANCEL;
958 539
        Lck_Unlock(&oh->mtx);
959 539
}
960
961
/*---------------------------------------------------------------------
962
 * Cancel a fetch when the client does not need it any more
963
 */
964
965
void
966
HSH_Cancel(struct worker *wrk, struct objcore *oc, struct boc *boc)
967 8669
{
968 8669
        struct boc *bocref = NULL;
969
970 8669
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
971
972 8669
        if ((oc->flags & OC_F_TRANSIENT) == 0)
973 3475
                return;
974
975
        /*
976
         * NB: we use two distinct variables to only release the reference if
977
         * we had to acquire one. The caller-provided boc is optional.
978
         */
979 5194
        if (boc == NULL)
980 4658
                bocref = boc = HSH_RefBoc(oc);
981
982 5194
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
983
984 5194
        if (oc->flags & OC_F_HFP)
985 30
                AN(oc->flags & OC_F_HFM);
986
987 5194
        if (boc != NULL) {
988 539
                hsh_cancel(oc);
989 539
                (void)ObjWaitState(oc, BOS_FINISHED);
990 539
        }
991
992 5194
        if (bocref != NULL)
993 3
                HSH_DerefBoc(wrk, oc);
994
995 5194
        ObjSlim(wrk, oc);
996 5194
}
997
998
/*---------------------------------------------------------------------
999
 * Withdraw an objcore that will not proceed with a fetch.
1000
 */
1001
1002
void
1003
HSH_Withdraw(struct worker *wrk, struct objcore **ocp)
1004 32
{
1005 32
        struct objhead *oh;
1006 32
        struct objcore *oc;
1007 32
        struct rush rush;
1008
1009 32
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1010 32
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1011 32
        INIT_OBJ(&rush, RUSH_MAGIC);
1012
1013 32
        oh = oc->objhead;
1014 32
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1015
1016 32
        Lck_Lock(&oh->mtx);
1017 32
        AZ(oc->stobj->stevedore);
1018 32
        AN(oc->flags & OC_F_BUSY);
1019 32
        assert(oc->refcnt == 1);
1020 32
        assert(oh->refcnt > 0);
1021 32
        oc->flags &= ~OC_F_BUSY;
1022 32
        oc->flags |= OC_F_WITHDRAWN;
1023 32
        hsh_rush1(wrk, oc, &rush); /* grabs up to 1 oc ref */
1024 32
        assert(hsh_deref_objcore_unlock(wrk, &oc) <= 1);
1025
1026 32
        hsh_rush2(wrk, &rush);
1027 32
}
1028
1029
/*---------------------------------------------------------------------
1030
 * Unbusy an objcore when the object is completely fetched.
1031
 */
1032
1033
void
1034
HSH_Unbusy(struct worker *wrk, struct objcore *oc)
1035 2917
{
1036 2917
        struct objhead *oh;
1037 2917
        struct rush rush;
1038
1039 2917
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1040 2917
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1041 2917
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
1042
1043 2917
        oh = oc->objhead;
1044 2917
        CHECK_OBJ(oh, OBJHEAD_MAGIC);
1045
1046 2917
        AN(oc->stobj->stevedore);
1047 2917
        assert(oh->refcnt > 0);
1048 2917
        assert(oc->refcnt > 0);
1049
1050 2917
        if (oc->flags & OC_F_PRIVATE) {
1051 1435
                AZ(oc->flags & OC_F_BUSY);
1052 1435
                return;
1053 1435
        }
1054
1055 1482
        AN(oc->flags & OC_F_BUSY);
1056 1482
        INIT_OBJ(&rush, RUSH_MAGIC);
1057
1058 1482
        BAN_NewObjCore(oc);
1059 1482
        AN(oc->ban);
1060
1061
        /* XXX: pretouch neighbors on oh->objcs to prevent page-on under mtx */
1062 1482
        Lck_Lock(&oh->mtx);
1063 1482
        assert(oh->refcnt > 0);
1064 1482
        assert(oc->refcnt > 0);
1065 1482
        EXP_RefNewObjcore(oc); /* Takes a ref for expiry */
1066
        /* XXX: strictly speaking, we should sort in Date: order. */
1067 1482
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1068 1482
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
1069 1482
        oc->flags &= ~OC_F_BUSY;
1070 1482
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1071 35
                assert(oh->refcnt > 1);
1072 35
                hsh_rush1(wrk, oc, &rush);
1073 35
        }
1074 1482
        Lck_Unlock(&oh->mtx);
1075 1482
        EXP_Insert(wrk, oc);
1076 1482
        hsh_rush2(wrk, &rush);
1077 1482
}
1078
1079
/*====================================================================
1080
 * HSH_Kill()
1081
 *
1082
 * It's dead Jim, kick it...
1083
 */
1084
1085
void
1086
HSH_Kill(struct objcore *oc)
1087 272
{
1088
1089 272
        HSH_Replace(oc, NULL);
1090 272
}
1091
1092
void
1093
HSH_Replace(struct objcore *oc, const struct objcore *new_oc)
1094 353
{
1095
1096 353
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1097 353
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1098 353
        if (new_oc != NULL) {
1099 81
                CHECK_OBJ(new_oc, OBJCORE_MAGIC);
1100 81
                assert(oc->objhead == new_oc->objhead);
1101 81
        }
1102
1103 353
        Lck_Lock(&oc->objhead->mtx);
1104 353
        oc->flags |= OC_F_DYING;
1105 353
        Lck_Unlock(&oc->objhead->mtx);
1106 353
        EXP_Remove(oc, new_oc);
1107 353
}
1108
1109
/*====================================================================
1110
 * HSH_Snipe()
1111
 *
1112
 * If objcore is idle, gain a ref and mark it dead.
1113
 */
1114
1115
int
1116
HSH_Snipe(const struct worker *wrk, struct objcore *oc)
1117 11
{
1118 11
        int retval = 0;
1119
1120 11
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1121 11
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1122 11
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
1123
1124 11
        if (oc->refcnt == 1 && !Lck_Trylock(&oc->objhead->mtx)) {
1125 11
                if (oc->refcnt == 1 && !(oc->flags & OC_F_DYING)) {
1126 11
                        oc->flags |= OC_F_DYING;
1127 11
                        oc->refcnt++;
1128 11
                        retval = 1;
1129 11
                }
1130 11
                Lck_Unlock(&oc->objhead->mtx);
1131 11
        }
1132 11
        if (retval)
1133 11
                EXP_Remove(oc, NULL);
1134 11
        return (retval);
1135 11
}
1136
1137
1138
/*---------------------------------------------------------------------
1139
 * Gain a reference on an objcore
1140
 *
1141
 * Holding it is required while
1142
 * - keeping referenecs to any object data as returned by ObjGetAttr()
1143
 * - Iterating over object body data: ObjVAIinit() until ObjVAIfini()
1144
 *   (which implies holding onto unreturned leases)
1145
 */
1146
1147
void
1148
HSH_Ref(struct objcore *oc)
1149 3159
{
1150 3159
        struct objhead *oh;
1151
1152 3159
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1153 3159
        oh = oc->objhead;
1154 3159
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1155 3159
        Lck_Lock(&oh->mtx);
1156 3159
        assert(oc->refcnt > 0);
1157 3159
        oc->refcnt++;
1158 3159
        Lck_Unlock(&oh->mtx);
1159 3159
}
1160
1161
/*---------------------------------------------------------------------
1162
 * Gain a reference on the busyobj, if the objcore has one
1163
 */
1164
1165
struct boc *
1166
HSH_RefBoc(const struct objcore *oc)
1167 21715
{
1168 21715
        struct objhead *oh;
1169 21715
        struct boc *boc;
1170
1171 21715
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1172 21715
        oh = oc->objhead;
1173 21715
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1174 21715
        if (oc->boc == NULL)
1175 16611
                return (NULL);
1176 5104
        Lck_Lock(&oh->mtx);
1177 5104
        assert(oc->refcnt > 0);
1178 5104
        boc = oc->boc;
1179 5104
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
1180 5104
        if (boc != NULL) {
1181 5101
                assert(boc->refcount > 0);
1182 5101
                if (boc->state < BOS_FINISHED)
1183 5043
                        boc->refcount++;
1184 58
                else
1185 58
                        boc = NULL;
1186 5101
        }
1187 5104
        Lck_Unlock(&oh->mtx);
1188 5104
        return (boc);
1189 5104
}
1190
1191
void
1192
HSH_DerefBoc(struct worker *wrk, struct objcore *oc)
1193 11937
{
1194 11937
        struct boc *boc;
1195 11937
        unsigned r;
1196
1197 11937
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1198 11937
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
1199 11937
        boc = oc->boc;
1200 11937
        CHECK_OBJ_NOTNULL(boc, BOC_MAGIC);
1201 11937
        Lck_Lock(&oc->objhead->mtx);
1202 11937
        assert(oc->refcnt > 0);
1203 11937
        assert(boc->refcount > 0);
1204 11937
        r = --boc->refcount;
1205 11937
        if (r == 0)
1206 6896
                oc->boc = NULL;
1207 11937
        Lck_Unlock(&oc->objhead->mtx);
1208 11937
        if (r == 0)
1209 6896
                ObjBocDone(wrk, oc, &boc);
1210 11937
}
1211
1212
/*--------------------------------------------------------------------
1213
 * Dereference objcore
1214
 *
1215
 * Returns zero if target was destroyed.
1216
 */
1217
1218
int
1219
HSH_DerefObjCore(struct worker *wrk, struct objcore **ocp)
1220 12896
{
1221 12896
        struct objcore *oc;
1222 12896
        struct objhead *oh;
1223
1224 12896
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1225 12896
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1226 12896
        assert(oc->refcnt > 0);
1227
1228 12896
        oh = oc->objhead;
1229 12896
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1230
1231 12896
        Lck_Lock(&oh->mtx);
1232 12896
        return (hsh_deref_objcore_unlock(wrk, &oc));
1233 12896
}
1234
1235
static int
1236
hsh_deref_objcore_unlock(struct worker *wrk, struct objcore **ocp)
1237 12928
{
1238 12928
        struct objcore *oc;
1239 12928
        struct objhead *oh;
1240 12928
        int r;
1241
1242 12928
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1243 12928
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
1244 12928
        assert(oc->refcnt > 0);
1245
1246 12928
        oh = oc->objhead;
1247 12928
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
1248
1249 12928
        Lck_AssertHeld(&oh->mtx);
1250 12928
        assert(oh->refcnt > 0);
1251 12928
        r = --oc->refcnt;
1252 12928
        if (!r)
1253 5852
                VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
1254 12928
        Lck_Unlock(&oh->mtx);
1255 12928
        if (r != 0)
1256 7075
                return (r);
1257
1258 5853
        AZ(oc->flags & OC_F_BUSY);
1259 5853
        AZ(oc->exp_flags);
1260
1261 5853
        BAN_DestroyObj(oc);
1262 5853
        AZ(oc->ban);
1263
1264 5853
        if (oc->stobj->stevedore != NULL)
1265 5765
                ObjFreeObj(wrk, oc);
1266 5853
        ObjDestroy(wrk, &oc);
1267
1268
        /* Drop our ref on the objhead */
1269 5853
        assert(oh->refcnt > 0);
1270 5853
        (void)hsh_deref_objhead(wrk, &oh);
1271 5853
        return (0);
1272 5853
}
1273
1274
static int
1275
hsh_deref_objhead_unlock(struct worker *wrk, struct objhead **poh,
1276
    struct objcore *oc)
1277 7941
{
1278 7941
        struct objhead *oh;
1279 7941
        struct rush rush;
1280 7941
        int r;
1281
1282 7941
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1283 7941
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1284
1285 7941
        Lck_AssertHeld(&oh->mtx);
1286
1287 7941
        if (oh >= private_ohs && oh < private_ohs + vcountof(private_ohs)) {
1288 5353
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1289 5353
                assert(oh->refcnt > 1);
1290 5353
                oh->refcnt--;
1291 5353
                Lck_Unlock(&oh->mtx);
1292 5353
                return (1);
1293 5353
        }
1294
1295
        //lint --e{661}
1296
        //lint -specific(-e661)
1297
        //
1298
        // because of the static array, flexelint thinks that all ohs were from
1299
        // the static array :( the above suppression applies to the remainder of
1300
        // this function body and specific walks involving this function
1301
1302 2588
        INIT_OBJ(&rush, RUSH_MAGIC);
1303 2588
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
1304 8
                assert(oh->refcnt > 1);
1305 8
                hsh_rush1(wrk, oc, &rush);
1306 8
        }
1307
1308 2588
        if (oh->refcnt == 1)
1309 214
                assert(VTAILQ_EMPTY(&oh->waitinglist));
1310
1311 2588
        assert(oh->refcnt > 0);
1312 2588
        r = hash->deref(wrk, oh); /* Unlocks oh->mtx */
1313 2588
        hsh_rush2(wrk, &rush);
1314 2588
        return (r);
1315 2588
}
1316
1317
static int
1318
hsh_deref_objhead(struct worker *wrk, struct objhead **poh)
1319 5852
{
1320 5852
        struct objhead *oh;
1321
1322 5852
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
1323 5852
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);
1324
1325 5852
        Lck_Lock(&oh->mtx);
1326 5852
        return (hsh_deref_objhead_unlock(wrk, &oh, NULL));
1327 5852
}
1328
1329
void
1330
HSH_Init(const struct hash_slinger *slinger)
1331 1026
{
1332
1333 1026
        assert(DIGEST_LEN == VSHA256_LEN);      /* avoid #include pollution */
1334 1026
        hash = slinger;
1335 1026
        if (hash->start != NULL)
1336 1026
                hash->start();
1337 1026
        for (struct objhead *oh = private_ohs;
1338 132354
            oh < private_ohs + vcountof(private_ohs);
1339 131328
            oh++) {
1340 131328
                hsh_initobjhead(oh);
1341 131328
                assert(oh->refcnt == 1);
1342 131328
        }
1343 1026
}