GCOV - Varnish Cache


/*-
 * Copyright (c) 2006 Verdens Gang AS
 * Copyright (c) 2006-2015 Varnish Software AS
 * All rights reserved.
 *
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * This is the central hash-table code, it relies on a chosen hash
 * implementation only for the actual hashing, all the housekeeping
 * happens here.
 *
 * We have two kinds of structures, objecthead and object.  An objecthead
 * corresponds to a given (Host:, URL) tuple, and the objects hung from
 * the objecthead may represent various variations (ie: Vary: header,
 * different TTL etc) instances of that web-entity.
 *
 * Each objecthead has a mutex which locks both its own fields, the
 * list of objects and fields in the objects.
 *
 * The hash implementation must supply a reference count facility on
 * the objecthead, and return with a reference held after a lookup.
 *
 * Lookups in the hash implementation returns with a ref held and each
 * object hung from the objhead holds a ref as well.
 *
 * Objects have refcounts which are locked by the objecthead mutex.
 *
 * New objects are always marked busy, and they can go from busy to
 * not busy only once.
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>

#include "cache_varnishd.h"

#include "cache/cache_objhead.h"
#include "cache/cache_transport.h"

#include "hash/hash_slinger.h"

#include "vsha256.h"

struct rush {
        unsigned                magic;
#define RUSH_MAGIC              0xa1af5f01
        VTAILQ_HEAD(,req)       reqs;
};

static const struct hash_slinger *hash;
#define PRIVATE_OH_EXP 7
static struct objhead private_ohs[1 << PRIVATE_OH_EXP];

static void hsh_rush1(const struct worker *, struct objcore *,
    struct rush *);
static void hsh_rush2(struct worker *, struct rush *);
static int hsh_deref_objhead(struct worker *wrk, struct objhead **poh);
static int hsh_deref_objhead_unlock(struct worker *wrk, struct objhead **poh,
    struct objcore *oc);
static int hsh_deref_objcore_unlock(struct worker *, struct objcore **);

/*---------------------------------------------------------------------*/

#define VCF_RETURN(x) const struct vcf_return VCF_##x[1] = { \
        { .name = #x, } \
};

VCF_RETURNS()
#undef VCF_RETURN

/*---------------------------------------------------------------------*/

static void
hsh_initobjhead(struct objhead *oh)
{

        XXXAN(oh);
        INIT_OBJ(oh, OBJHEAD_MAGIC);
        oh->refcnt = 1;
        oh->waitinglist_gen = 1;
        VTAILQ_INIT(&oh->objcs);
        VTAILQ_INIT(&oh->waitinglist);
        Lck_New(&oh->mtx, lck_objhdr);
}

static struct objhead *
hsh_newobjhead(void)
{
        struct objhead *oh = malloc(sizeof *oh);
        hsh_initobjhead(oh);
        return (oh);
}

/*---------------------------------------------------------------------*/
/* Precreate an objhead and object for later use */
static void
hsh_prealloc(struct worker *wrk)
{

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);

        if (wrk->wpriv->nobjcore == NULL)
                wrk->wpriv->nobjcore = ObjNew(wrk);
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);

        if (wrk->wpriv->nobjhead == NULL) {
                wrk->wpriv->nobjhead = hsh_newobjhead();
                wrk->stats->n_objecthead++;
        }
        CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);

        if (hash->prep != NULL)
                hash->prep(wrk);
}

/*---------------------------------------------------------------------*/

// https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
static inline size_t
fib(uint64_t n, uint8_t bits)
{
        const uint64_t gr = 11400714819323198485LLU;
        uint64_t r;

        r = n * gr;
        r >>= (sizeof(gr) * 8) - bits;
        assert(r < (size_t)1 << bits);
        return ((size_t)r);
}

struct objcore *
HSH_Private(const struct worker *wrk)
{
        struct objcore *oc;
        struct objhead *oh;

        oh = &private_ohs[fib((uintptr_t)wrk, PRIVATE_OH_EXP)];
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        oc = ObjNew(wrk);
        AN(oc);
        oc->refcnt = 1;
        oc->objhead = oh;
        oc->flags |= OC_F_PRIVATE;
        Lck_Lock(&oh->mtx);
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
        oh->refcnt++;
        Lck_Unlock(&oh->mtx);
        return (oc);
}

/*---------------------------------------------------------------------*/

void
HSH_Cleanup(const struct worker *wrk)
{

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
        if (wrk->wpriv->nobjcore != NULL)
                ObjDestroy(wrk, &wrk->wpriv->nobjcore);

        if (wrk->wpriv->nobjhead != NULL) {
                CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
                Lck_Delete(&wrk->wpriv->nobjhead->mtx);
                FREE_OBJ(wrk->wpriv->nobjhead);
                wrk->stats->n_objecthead--;
        }
        if (wrk->wpriv->nhashpriv != NULL) {
                /* XXX: If needed, add slinger method for this */
                free(wrk->wpriv->nhashpriv);
                wrk->wpriv->nhashpriv = NULL;
        }
}

void
HSH_DeleteObjHead(const struct worker *wrk, struct objhead *oh)
{
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        AZ(oh->refcnt);
        assert(VTAILQ_EMPTY(&oh->objcs));
        assert(VTAILQ_EMPTY(&oh->waitinglist));
        Lck_Delete(&oh->mtx);
        wrk->stats->n_objecthead--;
        FREE_OBJ(oh);
}

void
HSH_AddString(struct req *req, void *ctx, const char *str)
{

        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
        AN(ctx);
        if (str != NULL) {
                VSHA256_Update(ctx, str, strlen(str));
                VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
        } else
                VSHA256_Update(ctx, &str, 1);
}

/*---------------------------------------------------------------------
 * This is a debugging hack to enable testing of boundary conditions
 * in the hash algorithm.
 * We trap the first 9 different digests and translate them to different
 * digests with edge bit conditions
 */

static struct hsh_magiclist {
        unsigned char was[VSHA256_LEN];
        unsigned char now[VSHA256_LEN];
} hsh_magiclist[] = {
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 } },
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02 } },
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40 } },
        { .now = {      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80 } },
        { .now = {      0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
        { .now = {      0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
        { .now = {      0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
        { .now = {      0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
};

#define HSH_NMAGIC vcountof(hsh_magiclist)

static void
hsh_testmagic(void *result)
{
        size_t i, j;
        static size_t nused = 0;

        for (i = 0; i < nused; i++)
                if (!memcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
                        break;
        if (i == nused && i < HSH_NMAGIC)
                memcpy(hsh_magiclist[nused++].was, result, VSHA256_LEN);
        if (i == nused)
                return;
        assert(i < HSH_NMAGIC);
        fprintf(stderr, "HASHMAGIC: <");
        for (j = 0; j < VSHA256_LEN; j++)
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
        fprintf(stderr, "> -> <");
        memcpy(result, hsh_magiclist[i].now, VSHA256_LEN);
        for (j = 0; j < VSHA256_LEN; j++)
                fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
        fprintf(stderr, ">\n");
}

/*---------------------------------------------------------------------
 * Insert an object which magically appears out of nowhere or, more likely,
 * comes off some persistent storage device.
 * Insert it with a reference held.
 */

void
HSH_Insert(struct worker *wrk, const void *digest, struct objcore *oc,
    struct ban *ban)
{
        struct objhead *oh;
        struct rush rush;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
        AN(digest);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        AN(ban);
        AZ(oc->flags & OC_F_BUSY);
        AZ(oc->flags & OC_F_PRIVATE);
        assert(oc->refcnt == 1);
        INIT_OBJ(&rush, RUSH_MAGIC);

        hsh_prealloc(wrk);

        AN(wrk->wpriv->nobjhead);
        oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_AssertHeld(&oh->mtx);
        assert(oh->refcnt > 0);

        /* Mark object busy and insert (precreated) objcore in
           objecthead. The new object inherits our objhead reference. */
        oc->objhead = oh;
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
        EXP_RefNewObjcore(oc);
        Lck_Unlock(&oh->mtx);

        BAN_RefBan(oc, ban);
        AN(oc->ban);

        /* Move the object first in the oh list, unbusy it and run the
           waitinglist if necessary */
        Lck_Lock(&oh->mtx);
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
        if (!VTAILQ_EMPTY(&oh->waitinglist))
                hsh_rush1(wrk, oc, &rush);
        Lck_Unlock(&oh->mtx);
        hsh_rush2(wrk, &rush);

        EXP_Insert(wrk, oc);
}

/*---------------------------------------------------------------------
 */

static struct objcore *
hsh_insert_busyobj(const struct worker *wrk, struct objhead *oh)
{
        struct objcore *oc;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_AssertHeld(&oh->mtx);

        oc = wrk->wpriv->nobjcore;
        wrk->wpriv->nobjcore = NULL;
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);

        AZ(oc->flags & OC_F_BUSY);
        oc->flags |= OC_F_BUSY;
        oc->refcnt = 1;         /* Owned by busyobj */
        oc->objhead = oh;
        VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
        return (oc);
}

/*---------------------------------------------------------------------
 */

static int
hsh_vry_match(const struct req *req, struct objcore *oc, const uint8_t *vary)
{

        if (req->hash_ignore_vary)
                return (1);
        if (vary == NULL) {
                if (! ObjHasAttr(req->wrk, oc, OA_VARY))
                        return (1);
                vary = ObjGetAttr(req->wrk, oc, OA_VARY, NULL);
                AN(vary);
        }
        return (VRY_Match(req, vary));
}

static unsigned
hsh_rush_match(const struct req *req)
{
        struct objhead *oh;
        struct objcore *oc;

        oc = req->objcore;
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        assert(oc->refcnt > 0);

        AZ(oc->flags & OC_F_BUSY);
        AZ(oc->flags & OC_F_PRIVATE);
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_HFM|OC_F_HFP|OC_F_CANCEL|
            OC_F_FAILED))
                return (0);

        if (req->vcf != NULL) /* NB: must operate under oh lock. */
                return (0);

        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        return (hsh_vry_match(req, oc, NULL));
}

/*---------------------------------------------------------------------
 */

enum lookup_e
HSH_Lookup(struct req *req, struct objcore **ocp, struct objcore **bocp)
{
        struct worker *wrk;
        struct objhead *oh;
        struct objcore *oc;
        struct objcore *exp_oc;
        const struct vcf_return *vr;
        vtim_real exp_t_origin;
        int busy_found;
        intmax_t boc_progress;
        unsigned xid = 0;
        unsigned ban_checks;
        unsigned ban_any_variant;
        float dttl = 0.0;

        AN(ocp);
        *ocp = NULL;
        AN(bocp);
        *bocp = NULL;

        CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
        wrk = req->wrk;
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
        CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
        CHECK_OBJ_ORNULL(req->objcore, OBJCORE_MAGIC);
        CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
        AN(hash);

        hsh_prealloc(wrk);
        if (DO_DEBUG(DBG_HASHEDGE))
                hsh_testmagic(req->digest);

        /*
         * When a req rushes off the waiting list, it brings an implicit
         * oh refcnt acquired at disembark time and an oc ref (with its
         * own distinct oh ref) acquired during rush hour.
         */

        if (req->objcore != NULL && hsh_rush_match(req)) {
                TAKE_OBJ_NOTNULL(oc, &req->objcore, OBJCORE_MAGIC);
                *ocp = oc;
                oh = oc->objhead;
                Lck_Lock(&oh->mtx);
                oc->hits++;
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
                Req_LogHit(wrk, req, oc, boc_progress);
                /* NB: since this hit comes from the waiting list instead of
                 * a regular lookup, grace is not considered. The object is
                 * fresh in the context of the waiting list, even expired: it
                 * was successfully just [re]validated by a fetch task.
                 */
                return (HSH_HIT);
        }

        if (req->objcore != NULL) {
                oh = req->objcore->objhead;
                (void)HSH_DerefObjCore(wrk, &req->objcore);
                Lck_Lock(&oh->mtx);
        } else {
                AN(wrk->wpriv->nobjhead);
                oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
        }

        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_AssertHeld(&oh->mtx);

        if (req->hash_always_miss) {
                /* XXX: should we do predictive Vary in this case ? */
                /* Insert new objcore in objecthead and release mutex */
                *bocp = hsh_insert_busyobj(wrk, oh);
                /* NB: no deref of objhead, new object inherits reference */
                Lck_Unlock(&oh->mtx);
                return (HSH_MISS);
        }

        assert(oh->refcnt > 0);
        busy_found = 0;
        exp_oc = NULL;
        exp_t_origin = 0.0;
        ban_checks = 0;
        ban_any_variant = cache_param->ban_any_variant;
        VTAILQ_FOREACH(oc, &oh->objcs, hsh_list) {
                /* Must be at least our own ref + the objcore we examine */
                assert(oh->refcnt > 1);
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
                assert(oc->objhead == oh);
                assert(oc->refcnt > 0);

                if (oc->flags & OC_F_DYING)
                        continue;
                if (oc->flags & OC_F_FAILED)
                        continue;

                CHECK_OBJ_ORNULL(oc->boc, BOC_MAGIC);
                if (oc->flags & OC_F_BUSY) {
                        if (req->hash_ignore_busy)
                                continue;

                        if (oc->boc && oc->boc->vary != NULL &&
                            !hsh_vry_match(req, oc, oc->boc->vary)) {
                                wrk->strangelove++;
                                continue;
                        }

                        busy_found = 1;
                        continue;
                }

                if (oc->ttl <= 0.)
                        continue;

                if (ban_checks++ < ban_any_variant
                    && BAN_CheckObject(wrk, oc, req)) {
                        oc->flags |= OC_F_DYING;
                        EXP_Remove(oc, NULL);
                        continue;
                }

                if (!hsh_vry_match(req, oc, NULL)) {
                        wrk->strangelove++;
                        continue;
                }

                if (ban_checks >= ban_any_variant
                    && BAN_CheckObject(wrk, oc, req)) {
                        oc->flags |= OC_F_DYING;
                        EXP_Remove(oc, NULL);
                        continue;
                }

                if (req->vcf != NULL) {
                        vr = req->vcf->func(req, &oc, &exp_oc, 0);
                        if (vr == VCF_CONTINUE)
                                continue;
                        if (vr == VCF_MISS) {
                                oc = NULL;
                                break;
                        }
                        if (vr == VCF_HIT)
                                break;
                        assert(vr == VCF_DEFAULT);
                }

                if (EXP_Ttl(req, oc) > req->t_req) {
                        assert(oh->refcnt > 1);
                        assert(oc->objhead == oh);
                        break;
                }

                if (EXP_Ttl(NULL, oc) <= req->t_req && /* ignore req.max_age */
                    oc->t_origin > exp_t_origin) {
                        /* record the newest object */
                        exp_oc = oc;
                        exp_t_origin = oc->t_origin;
                        assert(oh->refcnt > 1);
                        assert(exp_oc->objhead == oh);
                }
        }

        if (req->vcf != NULL)
                (void)req->vcf->func(req, &oc, &exp_oc, 1);

        if (oc != NULL && oc->flags & OC_F_HFP) {
                xid = VXID(ObjGetXID(wrk, oc));
                dttl = EXP_Dttl(req, oc);
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
                wrk->stats->cache_hitpass++;
                VSLb(req->vsl, SLT_HitPass, "%u %.6f", xid, dttl);
                return (HSH_HITPASS);
        }

        if (oc != NULL) {
                *ocp = oc;
                oc->refcnt++;
                if (oc->flags & OC_F_HFM) {
                        xid = VXID(ObjGetXID(wrk, oc));
                        dttl = EXP_Dttl(req, oc);
                        *bocp = hsh_insert_busyobj(wrk, oh);
                        Lck_Unlock(&oh->mtx);
                        wrk->stats->cache_hitmiss++;
                        VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
                        return (HSH_HITMISS);
                }
                oc->hits++;
                boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
                AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
                Req_LogHit(wrk, req, oc, boc_progress);
                return (HSH_HIT);
        }

        if (exp_oc != NULL && exp_oc->flags & OC_F_HFM) {
                /*
                 * expired HFM ("grace/keep HFM")
                 *
                 * XXX should HFM objects actually have grace/keep ?
                 * XXX also:  why isn't *ocp = exp_oc ?
                 */
                xid = VXID(ObjGetXID(wrk, exp_oc));
                dttl = EXP_Dttl(req, exp_oc);
                *bocp = hsh_insert_busyobj(wrk, oh);
                Lck_Unlock(&oh->mtx);
                wrk->stats->cache_hitmiss++;
                VSLb(req->vsl, SLT_HitMiss, "%u %.6f", xid, dttl);
                return (HSH_HITMISS);
        }

        if (exp_oc != NULL && exp_oc->boc != NULL)
                boc_progress = exp_oc->boc->fetched_so_far;
        else
                boc_progress = -1;

        if (!busy_found) {
                *bocp = hsh_insert_busyobj(wrk, oh);

                if (exp_oc != NULL) {
                        exp_oc->refcnt++;
                        *ocp = exp_oc;
                        if (EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
                                exp_oc->hits++;
                                Lck_Unlock(&oh->mtx);
                                Req_LogHit(wrk, req, exp_oc, boc_progress);
                                return (HSH_GRACE);
                        }
                }
                Lck_Unlock(&oh->mtx);
                return (HSH_MISS);
        }

        AN(busy_found);
        if (exp_oc != NULL && EXP_Ttl_grace(req, exp_oc) >= req->t_req) {
                /* we do not wait on the busy object if in grace */
                exp_oc->refcnt++;
                *ocp = exp_oc;
                exp_oc->hits++;
                AN(hsh_deref_objhead_unlock(wrk, &oh, NULL));
                Req_LogHit(wrk, req, exp_oc, boc_progress);
                return (HSH_GRACE);
        }

        /* There are one or more busy objects, wait for them */
        VTAILQ_INSERT_TAIL(&oh->waitinglist, req, w_list);

        AZ(req->hash_ignore_busy);

        /*
         * The objhead reference is held by req while it is parked on the
         * waiting list. The oh pointer is taken back from the objcore that
         * triggers a rush of req off the waiting list.
         */
        assert(oh->refcnt > 1);

        req->wrk = NULL;
        req->waitinglist_gen = oh->waitinglist_gen;

        if (DO_DEBUG(DBG_WAITINGLIST))
                VSLb(req->vsl, SLT_Debug, "on waiting list <%p>", oh);

        Lck_Unlock(&oh->mtx);

        wrk->stats->busy_sleep++;
        return (HSH_BUSY);
}

/*---------------------------------------------------------------------
 * Pick the req's we are going to rush from the waiting list
 */

static void
hsh_rush1(const struct worker *wrk, struct objcore *oc, struct rush *r)
{
        struct objhead *oh;
        struct req *req;
        int i, max;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
        VTAILQ_INIT(&r->reqs);

        if (oc == NULL)
                return;

        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_AssertHeld(&oh->mtx);

        AZ(oc->flags & OC_F_BUSY);
        AZ(oc->flags & OC_F_PRIVATE);
        max = cache_param->rush_exponent;
        if (oc->flags & (OC_F_WITHDRAWN|OC_F_FAILED))
                max = 1;
        assert(max > 0);

        if (oc->waitinglist_gen == 0) {
                oc->waitinglist_gen = oh->waitinglist_gen;
                oh->waitinglist_gen++;
        }

        for (i = 0; i < max; i++) {
                req = VTAILQ_FIRST(&oh->waitinglist);
                if (req == NULL)
                        break;

                CHECK_OBJ(req, REQ_MAGIC);

                /* NB: The waiting list is naturally sorted by generation.
                 *
                 * Because of the exponential nature of the rush, it is
                 * possible that new requests enter the waiting list before
                 * the rush for this oc completes. Because the OC_F_BUSY flag
                 * was cleared before the beginning of the rush, requests
                 * from a newer generation already got a chance to evaluate
                 * oc during a lookup and it didn't match their criteria.
                 *
                 * Therefore there's no point propagating the exponential
                 * rush of this oc when we see a newer generation.
                 */
                if (req->waitinglist_gen > oc->waitinglist_gen)
                        break;

                AZ(req->wrk);
                VTAILQ_REMOVE(&oh->waitinglist, req, w_list);
                VTAILQ_INSERT_TAIL(&r->reqs, req, w_list);
                req->objcore = oc;
                oc->refcnt++;
                wrk->stats->busy_wakeup++;
        }
}

/*---------------------------------------------------------------------
 * Rush req's that came from waiting list.
 */

static void
hsh_rush2(struct worker *wrk, struct rush *r)
{
        struct req *req;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);

        while (!VTAILQ_EMPTY(&r->reqs)) {
                req = VTAILQ_FIRST(&r->reqs);
                CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
                VTAILQ_REMOVE(&r->reqs, req, w_list);
                DSL(DBG_WAITINGLIST, req->vsl->wid, "off waiting list");
                if (req->transport->reembark != NULL) {
                        // For ESI includes
                        req->transport->reembark(wrk, req);
                } else {
                        /*
                         * We ignore the queue limits which apply to new
                         * requests because if we fail to reschedule there
                         * may be vmod_privs to cleanup and we need a proper
                         * workerthread for that.
                         */
                        AZ(Pool_Task(req->sp->pool, req->task, TASK_QUEUE_RUSH));
                }
        }
}

/*---------------------------------------------------------------------
 * Purge an entire objhead
 */

unsigned
HSH_Purge(struct worker *wrk, struct objhead *oh, vtim_real ttl_now,
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
{
        struct objcore *oc, *oc_nows[2], **ocp;
        unsigned i, j, n, n_max, total = 0;
        int is_purge;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        is_purge = (ttl == 0 && grace == 0 && keep == 0);
        n_max = WS_ReserveLumps(wrk->aws, sizeof *ocp);
        if (n_max < 2) {
                /* No space on the workspace. Give it a stack buffer of 2
                 * elements, which is the minimum for the algorithm
                 * below. */
                ocp = oc_nows;
                n_max = 2;
        } else
                ocp = WS_Reservation(wrk->aws);
        AN(ocp);

        /* Note: This algorithm uses OC references in the list as
         * bookmarks, in order to know how far into the list we were when
         * releasing the mutex partway through and want to resume
         * again. This relies on the list not being reordered while we are
         * not holding the mutex. The only place where that happens is in
         * HSH_Unbusy(), where an OC_F_BUSY OC is moved first in the
         * list. This does not cause problems because we skip OC_F_BUSY
         * OCs. */

        Lck_Lock(&oh->mtx);
        oc = VTAILQ_FIRST(&oh->objcs);
        n = 0;
        while (1) {
                for (; n < n_max && oc != NULL; oc = VTAILQ_NEXT(oc, hsh_list))
                {
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
                        assert(oc->objhead == oh);
                        if (oc->flags & OC_F_BUSY) {
                                /* We cannot purge busy objects here, because
                                 * their owners have special rights to them,
                                 * and may nuke them without concern for the
                                 * refcount, which by definition always must
                                 * be one, so they don't check. */
                                continue;
                        }
                        if (oc->flags & OC_F_DYING)
                                continue;
                        if (is_purge)
                                oc->flags |= OC_F_DYING;
                        oc->refcnt++;
                        ocp[n++] = oc;
                }

                Lck_Unlock(&oh->mtx);

                if (n == 0) {
                        /* No eligible objcores found. We are finished. */
                        break;
                }

                j = n;
                if (oc != NULL) {
                        /* There are more objects on the objhead that we
                         * have not yet looked at, but no more space on
                         * the objcore reference list. Do not process the
                         * last one, it will be used as the bookmark into
                         * the objcore list for the next iteration of the
                         * outer loop. */
                        j--;
                        assert(j >= 1); /* True because n_max >= 2 */
                }
                for (i = 0; i < j; i++) {
                        CHECK_OBJ_NOTNULL(ocp[i], OBJCORE_MAGIC);
                        if (is_purge)
                                EXP_Remove(ocp[i], NULL);
                        else
                                EXP_Reduce(ocp[i], ttl_now, ttl, grace, keep);
                        (void)HSH_DerefObjCore(wrk, &ocp[i]);
                        AZ(ocp[i]);
                        total++;
                }

                if (j == n) {
                        /* No bookmark set, that means we got to the end
                         * of the objcore list in the previous run and are
                         * finished. */
                        break;
                }

                Lck_Lock(&oh->mtx);

                /* Move the bookmark first and continue scanning the
                 * objcores */
                CHECK_OBJ_NOTNULL(ocp[j], OBJCORE_MAGIC);
                ocp[0] = ocp[j];
                n = 1;
                oc = VTAILQ_NEXT(ocp[0], hsh_list);
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
        }

        WS_Release(wrk->aws, 0);
        if (is_purge)
                Pool_PurgeStat(total);
        return (total);
}

/*---------------------------------------------------------------------
 * Fail an objcore
 */

void
HSH_Fail(struct worker *wrk, struct objcore *oc)
{
        struct objhead *oh;
        struct rush rush;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);
        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        INIT_OBJ(&rush, RUSH_MAGIC);

        /*
         * We either failed before the end of vcl_backend_response
         * and a cache miss has the busy bit, so that HSH_Lookup()
         * will not consider this oc, or an object hung off the oc
         * so that it can consider it.
         *
         * We can only fail an ongoing fetch in a backend context
         * so we can safely check the BOC state as it won't change
         * under our feet.
         */
        if (oc->boc->state < BOS_STREAM)
                assert(oc->flags & (OC_F_BUSY|OC_F_PRIVATE));
        else
                assert(oc->stobj->stevedore != NULL);

        Lck_Lock(&oh->mtx);
        oc->flags |= OC_F_FAILED;
        if (oc->flags & OC_F_BUSY) {
                oc->flags &= ~OC_F_BUSY;
                hsh_rush1(wrk, oc, &rush);
        }
        Lck_Unlock(&oh->mtx);
        hsh_rush2(wrk, &rush);
}

/*---------------------------------------------------------------------
 * Mark a fetch we will not need as cancelled
 */

static void
hsh_cancel(struct objcore *oc)
{
        struct objhead *oh;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        oh = oc->objhead;
        CHECK_OBJ(oh, OBJHEAD_MAGIC);

        Lck_Lock(&oh->mtx);
        oc->flags |= OC_F_CANCEL;
        Lck_Unlock(&oh->mtx);
}

/*---------------------------------------------------------------------
 * Cancel a fetch when the client does not need it any more
 */

void
HSH_Cancel(struct worker *wrk, struct objcore *oc, struct boc *boc)
{
        struct boc *bocref = NULL;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);

        if ((oc->flags & OC_F_TRANSIENT) == 0)
                return;

        /*
         * NB: we use two distinct variables to only release the reference if
         * we had to acquire one. The caller-provided boc is optional.
         */
        if (boc == NULL)
                bocref = boc = HSH_RefBoc(oc);

        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);

        if (oc->flags & OC_F_HFP)
                AN(oc->flags & OC_F_HFM);

        if (boc != NULL) {
                hsh_cancel(oc);
                ObjWaitState(oc, BOS_FINISHED);
        }

        if (bocref != NULL)
                HSH_DerefBoc(wrk, oc);

        ObjSlim(wrk, oc);
}

/*---------------------------------------------------------------------
 * Withdraw an objcore that will not proceed with a fetch.
 */

void
HSH_Withdraw(struct worker *wrk, struct objcore **ocp)
{
        struct objhead *oh;
        struct objcore *oc;
        struct rush rush;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
        INIT_OBJ(&rush, RUSH_MAGIC);

        oh = oc->objhead;
        CHECK_OBJ(oh, OBJHEAD_MAGIC);

        Lck_Lock(&oh->mtx);
        AZ(oc->stobj->stevedore);
        AN(oc->flags & OC_F_BUSY);
        assert(oc->refcnt == 1);
        assert(oh->refcnt > 0);
        oc->flags &= ~OC_F_BUSY;
        oc->flags |= OC_F_WITHDRAWN;
        hsh_rush1(wrk, oc, &rush); /* grabs up to 1 oc ref */
        assert(hsh_deref_objcore_unlock(wrk, &oc) <= 1);

        hsh_rush2(wrk, &rush);
}

/*---------------------------------------------------------------------
 * Unbusy an objcore when the object is completely fetched.
 */

void
HSH_Unbusy(struct worker *wrk, struct objcore *oc)
{
        struct objhead *oh;
        struct rush rush;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->boc, BOC_MAGIC);

        oh = oc->objhead;
        CHECK_OBJ(oh, OBJHEAD_MAGIC);

        AN(oc->stobj->stevedore);
        assert(oh->refcnt > 0);
        assert(oc->refcnt > 0);

        if (oc->flags & OC_F_PRIVATE) {
                AZ(oc->flags & OC_F_BUSY);
                return;
        }

        AN(oc->flags & OC_F_BUSY);
        INIT_OBJ(&rush, RUSH_MAGIC);

        BAN_NewObjCore(oc);
        AN(oc->ban);

        /* XXX: pretouch neighbors on oh->objcs to prevent page-on under mtx */
        Lck_Lock(&oh->mtx);
        assert(oh->refcnt > 0);
        assert(oc->refcnt > 0);
        EXP_RefNewObjcore(oc); /* Takes a ref for expiry */
        /* XXX: strictly speaking, we should sort in Date: order. */
        VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
        VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
        oc->flags &= ~OC_F_BUSY;
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
                assert(oh->refcnt > 1);
                hsh_rush1(wrk, oc, &rush);
        }
        Lck_Unlock(&oh->mtx);
        EXP_Insert(wrk, oc);
        hsh_rush2(wrk, &rush);
}

/*====================================================================
 * HSH_Kill()
 *
 * It's dead Jim, kick it...
 */

void
HSH_Kill(struct objcore *oc)
{

        HSH_Replace(oc, NULL);
}

void
HSH_Replace(struct objcore *oc, const struct objcore *new_oc)
{

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
        if (new_oc != NULL) {
                CHECK_OBJ(new_oc, OBJCORE_MAGIC);
                assert(oc->objhead == new_oc->objhead);
        }

        Lck_Lock(&oc->objhead->mtx);
        oc->flags |= OC_F_DYING;
        Lck_Unlock(&oc->objhead->mtx);
        EXP_Remove(oc, new_oc);
}

/*====================================================================
 * HSH_Snipe()
 *
 * If objcore is idle, gain a ref and mark it dead.
 */

int
HSH_Snipe(const struct worker *wrk, struct objcore *oc)
{
        int retval = 0;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);

        if (oc->refcnt == 1 && !Lck_Trylock(&oc->objhead->mtx)) {
                if (oc->refcnt == 1 && !(oc->flags & OC_F_DYING)) {
                        oc->flags |= OC_F_DYING;
                        oc->refcnt++;
                        retval = 1;
                }
                Lck_Unlock(&oc->objhead->mtx);
        }
        if (retval)
                EXP_Remove(oc, NULL);
        return (retval);
}


/*---------------------------------------------------------------------
 * Gain a reference on an objcore
 */

void
HSH_Ref(struct objcore *oc)
{
        struct objhead *oh;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        Lck_Lock(&oh->mtx);
        assert(oc->refcnt > 0);
        oc->refcnt++;
        Lck_Unlock(&oh->mtx);
}

/*---------------------------------------------------------------------
 * Gain a reference on the busyobj, if the objcore has one
 */

struct boc *
HSH_RefBoc(const struct objcore *oc)
{
        struct objhead *oh;
        struct boc *boc;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        if (oc->boc == NULL)
                return (NULL);
        Lck_Lock(&oh->mtx);
        assert(oc->refcnt > 0);
        boc = oc->boc;
        CHECK_OBJ_ORNULL(boc, BOC_MAGIC);
        if (boc != NULL) {
                assert(boc->refcount > 0);
                if (boc->state < BOS_FINISHED)
                        boc->refcount++;
                else
                        boc = NULL;
        }
        Lck_Unlock(&oh->mtx);
        return (boc);
}

void
HSH_DerefBoc(struct worker *wrk, struct objcore *oc)
{
        struct boc *boc;
        unsigned r;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        boc = oc->boc;
        CHECK_OBJ_NOTNULL(boc, BOC_MAGIC);
        Lck_Lock(&oc->objhead->mtx);
        assert(oc->refcnt > 0);
        assert(boc->refcount > 0);
        r = --boc->refcount;
        if (r == 0)
                oc->boc = NULL;
        Lck_Unlock(&oc->objhead->mtx);
        if (r == 0)
                ObjBocDone(wrk, oc, &boc);
}

/*--------------------------------------------------------------------
 * Dereference objcore
 *
 * Returns zero if target was destroyed.
 */

int
HSH_DerefObjCore(struct worker *wrk, struct objcore **ocp)
{
        struct objcore *oc;
        struct objhead *oh;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
        assert(oc->refcnt > 0);

        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        Lck_Lock(&oh->mtx);
        return (hsh_deref_objcore_unlock(wrk, &oc));
}

static int
hsh_deref_objcore_unlock(struct worker *wrk, struct objcore **ocp)
{
        struct objcore *oc;
        struct objhead *oh;
        int r;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        TAKE_OBJ_NOTNULL(oc, ocp, OBJCORE_MAGIC);
        assert(oc->refcnt > 0);

        oh = oc->objhead;
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);

        Lck_AssertHeld(&oh->mtx);
        assert(oh->refcnt > 0);
        r = --oc->refcnt;
        if (!r)
                VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
        Lck_Unlock(&oh->mtx);
        if (r != 0)
                return (r);

        AZ(oc->flags & OC_F_BUSY);
        AZ(oc->exp_flags);

        BAN_DestroyObj(oc);
        AZ(oc->ban);

        if (oc->stobj->stevedore != NULL)
                ObjFreeObj(wrk, oc);
        ObjDestroy(wrk, &oc);

        /* Drop our ref on the objhead */
        assert(oh->refcnt > 0);
        (void)hsh_deref_objhead(wrk, &oh);
        return (0);
}

static int
hsh_deref_objhead_unlock(struct worker *wrk, struct objhead **poh,
    struct objcore *oc)
{
        struct objhead *oh;
        struct rush rush;
        int r;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);

        Lck_AssertHeld(&oh->mtx);

        if (oh >= private_ohs && oh < private_ohs + vcountof(private_ohs)) {
                assert(VTAILQ_EMPTY(&oh->waitinglist));
                assert(oh->refcnt > 1);
                oh->refcnt--;
                Lck_Unlock(&oh->mtx);
                return (1);
        }

        //lint --e{661}
        //lint -specific(-e661)
        //
        // because of the static array, flexelint thinks that all ohs were from
        // the static array :( the above suppression applies to the remainder of
        // this function body and specific walks involving this function

        INIT_OBJ(&rush, RUSH_MAGIC);
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
                assert(oh->refcnt > 1);
                hsh_rush1(wrk, oc, &rush);
        }

        if (oh->refcnt == 1)
                assert(VTAILQ_EMPTY(&oh->waitinglist));

        assert(oh->refcnt > 0);
        r = hash->deref(wrk, oh); /* Unlocks oh->mtx */
        hsh_rush2(wrk, &rush);
        return (r);
}

static int
hsh_deref_objhead(struct worker *wrk, struct objhead **poh)
{
        struct objhead *oh;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        TAKE_OBJ_NOTNULL(oh, poh, OBJHEAD_MAGIC);

        Lck_Lock(&oh->mtx);
        return (hsh_deref_objhead_unlock(wrk, &oh, NULL));
}

void
HSH_Init(const struct hash_slinger *slinger)
{

        assert(DIGEST_LEN == VSHA256_LEN);      /* avoid #include pollution */
        hash = slinger;
        if (hash->start != NULL)
                hash->start();
        for (struct objhead *oh = private_ohs;
            oh < private_ohs + vcountof(private_ohs);
            oh++) {
                hsh_initobjhead(oh);
                assert(oh->refcnt == 1);
        }
}

		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	4918617	hsh_initobjhead(struct objhead *oh)
99		{
100
101	4918617	XXXAN(oh);
102	4918617	INIT_OBJ(oh, OBJHEAD_MAGIC);
103	4918617	oh->refcnt = 1;
104	4918617	oh->waitinglist_gen = 1;
105	4918617	VTAILQ_INIT(&oh->objcs);
106	4918617	VTAILQ_INIT(&oh->waitinglist);
107	4918617	Lck_New(&oh->mtx, lck_objhdr);
108	4918617	}
109
110		static struct objhead *
111	63319	hsh_newobjhead(void)
112		{
113	63319	struct objhead oh = malloc(sizeof oh);
114	63319	hsh_initobjhead(oh);
115	63319	return (oh);
116		}
117
118		/---------------------------------------------------------------------/
119		/* Precreate an objhead and object for later use */
120		static void
121	107240	hsh_prealloc(struct worker *wrk)
122		{
123
124	107240	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
125
126	107240	if (wrk->wpriv->nobjcore == NULL)
127	72418	wrk->wpriv->nobjcore = ObjNew(wrk);
128	107240	CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);
129
130	107240	if (wrk->wpriv->nobjhead == NULL) {
131	63321	wrk->wpriv->nobjhead = hsh_newobjhead();
132	63321	wrk->stats->n_objecthead++;
133	63321	}
134	107240	CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
135
136	107240	if (hash->prep != NULL)
137	107000	hash->prep(wrk);
138	107240	}
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	56720	fib(uint64_t n, uint8_t bits)
145		{
146	56720	const uint64_t gr = 11400714819323198485LLU;
147		uint64_t r;
148
149	56720	r = n * gr;
150	56720	r >>= (sizeof(gr) * 8) - bits;
151	56720	assert(r < (size_t)1 << bits);
152	56720	return ((size_t)r);
153		}
154
155		struct objcore *
156	56720	HSH_Private(const struct worker *wrk)
157		{
158		struct objcore *oc;
159		struct objhead *oh;
160
161	56720	oh = &private_ohs[fib((uintptr_t)wrk, PRIVATE_OH_EXP)];
162	56720	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
163
164	56720	oc = ObjNew(wrk);
165	56720	AN(oc);
166	56720	oc->refcnt = 1;
167	56720	oc->objhead = oh;
168	56720	oc->flags \|= OC_F_PRIVATE;
169	56720	Lck_Lock(&oh->mtx);
170	56720	VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
171	56720	oh->refcnt++;
172	56720	Lck_Unlock(&oh->mtx);
173	56720	return (oc);
174		}
175
176		/---------------------------------------------------------------------/
177
178		void
179	38353	HSH_Cleanup(const struct worker *wrk)
180		{
181
182	38353	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
183	38353	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
184	38353	if (wrk->wpriv->nobjcore != NULL)
185	72	ObjDestroy(wrk, &wrk->wpriv->nobjcore);
186
187	38353	if (wrk->wpriv->nobjhead != NULL) {
188	72	CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
189	72	Lck_Delete(&wrk->wpriv->nobjhead->mtx);
190	72	FREE_OBJ(wrk->wpriv->nobjhead);
191	72	wrk->stats->n_objecthead--;
192	72	}
193	38353	if (wrk->wpriv->nhashpriv != NULL) {
194		/* XXX: If needed, add slinger method for this */
195	80	free(wrk->wpriv->nhashpriv);
196	80	wrk->wpriv->nhashpriv = NULL;
197	80	}
198	38353	}
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	592634	HSH_AddString(struct req req, void ctx, const char *str)
216		{
217
218	592634	CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
219	592634	AN(ctx);
220	592634	if (str != NULL) {
221	296300	VSHA256_Update(ctx, str, strlen(str));
222	296300	VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
223	296300	} else
224	296334	VSHA256_Update(ctx, &str, 1);
225	592634	}
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	720	hsh_testmagic(void *result)
280		{
281		size_t i, j;
282		static size_t nused = 0;
283
284	3600	for (i = 0; i < nused; i++)
285	3240	if (!memcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
286	360	break;
287	720	if (i == nused && i < HSH_NMAGIC)
288	360	memcpy(hsh_magiclist[nused++].was, result, VSHA256_LEN);
289	720	if (i == nused)
290	0	return;
291	720	assert(i < HSH_NMAGIC);
292	720	fprintf(stderr, "HASHMAGIC: <");
293	23760	for (j = 0; j < VSHA256_LEN; j++)
294	23040	fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
295	720	fprintf(stderr, "> -> <");
296	720	memcpy(result, hsh_magiclist[i].now, VSHA256_LEN);
297	23760	for (j = 0; j < VSHA256_LEN; j++)
298	23040	fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
299	720	fprintf(stderr, ">\n");
300	720	}
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	680	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	680	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
316	680	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
317	680	AN(digest);
318	680	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
319	680	AN(ban);
320	680	AZ(oc->flags & OC_F_BUSY);
321	680	AZ(oc->flags & OC_F_PRIVATE);
322	680	assert(oc->refcnt == 1);
323	680	INIT_OBJ(&rush, RUSH_MAGIC);
324
325	680	hsh_prealloc(wrk);
326
327	680	AN(wrk->wpriv->nobjhead);
328	680	oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
329	680	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
330	680	Lck_AssertHeld(&oh->mtx);
331	680	assert(oh->refcnt > 0);
332
333		/* Mark object busy and insert (precreated) objcore in
334		objecthead. The new object inherits our objhead reference. */
335	680	oc->objhead = oh;
336	680	VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
337	680	EXP_RefNewObjcore(oc);
338	680	Lck_Unlock(&oh->mtx);
339
340	680	BAN_RefBan(oc, ban);
341	680	AN(oc->ban);
342
343		/* Move the object first in the oh list, unbusy it and run the
344		waitinglist if necessary */
345	680	Lck_Lock(&oh->mtx);
346	680	VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
347	680	VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
348	680	if (!VTAILQ_EMPTY(&oh->waitinglist))
349	0	hsh_rush1(wrk, oc, &rush);
350	680	Lck_Unlock(&oh->mtx);
351	680	hsh_rush2(wrk, &rush);
352
353	680	EXP_Insert(wrk, oc);
354	680	}
355
356		/*---------------------------------------------------------------------
357		*/
358
359		static struct objcore *
360	60946	hsh_insert_busyobj(const struct worker wrk, struct objhead oh)
361		{
362		struct objcore *oc;
363
364	60946	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
365	60946	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
366	60946	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
367	60946	Lck_AssertHeld(&oh->mtx);
368
369	60946	oc = wrk->wpriv->nobjcore;
370	60946	wrk->wpriv->nobjcore = NULL;
371	60946	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
372
373	60946	AZ(oc->flags & OC_F_BUSY);
374	60946	oc->flags \|= OC_F_BUSY;
375	60946	oc->refcnt = 1; /* Owned by busyobj */
376	60946	oc->objhead = oh;
377	60946	VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
378	60946	return (oc);
379		}
380
381		/*---------------------------------------------------------------------
382		*/
383
384		static int
385	157144	hsh_vry_match(const struct req req, struct objcore oc, const uint8_t *vary)
386		{
387
388	157144	if (req->hash_ignore_vary)
389	40	return (1);
390	157104	if (vary == NULL) {
391	157029	if (! ObjHasAttr(req->wrk, oc, OA_VARY))
392	44150	return (1);
393	112879	vary = ObjGetAttr(req->wrk, oc, OA_VARY, NULL);
394	112879	AN(vary);
395	112879	}
396	112954	return (VRY_Match(req, vary));
397	157144	}
398
399		static unsigned
400	2199	hsh_rush_match(const struct req *req)
401		{
402		struct objhead *oh;
403		struct objcore *oc;
404
405	2199	oc = req->objcore;
406	2199	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
407	2199	assert(oc->refcnt > 0);
408
409	2199	AZ(oc->flags & OC_F_BUSY);
410	2199	AZ(oc->flags & OC_F_PRIVATE);
411	2199	if (oc->flags & (OC_F_WITHDRAWN\|OC_F_HFM\|OC_F_HFP\|OC_F_CANCEL\|
412		OC_F_FAILED))
413	479	return (0);
414
415	1720	if (req->vcf != NULL) /* NB: must operate under oh lock. */
416	0	return (0);
417
418	1720	oh = oc->objhead;
419	1720	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
420
421	1720	return (hsh_vry_match(req, oc, NULL));
422	2199	}
423
424		/*---------------------------------------------------------------------
425		*/
426
427		enum lookup_e
428	106559	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	106559	unsigned xid = 0;
439		unsigned ban_checks;
440		unsigned ban_any_variant;
441	106559	float dttl = 0.0;
442
443	106559	AN(ocp);
444	106559	*ocp = NULL;
445	106559	AN(bocp);
446	106559	*bocp = NULL;
447
448	106559	CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
449	106559	wrk = req->wrk;
450	106559	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
451	106559	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
452	106559	CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
453	106559	CHECK_OBJ_ORNULL(req->objcore, OBJCORE_MAGIC);
454	106559	CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
455	106559	AN(hash);
456
457	106559	hsh_prealloc(wrk);
458	106559	if (DO_DEBUG(DBG_HASHEDGE))
459	720	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	106559	if (req->objcore != NULL && hsh_rush_match(req)) {
468	1640	TAKE_OBJ_NOTNULL(oc, &req->objcore, OBJCORE_MAGIC);
469	1640	*ocp = oc;
470	1640	oh = oc->objhead;
471	1640	Lck_Lock(&oh->mtx);
472	1640	oc->hits++;
473	1640	boc_progress = oc->boc == NULL ? -1 : oc->boc->fetched_so_far;
474	1640	AN(hsh_deref_objhead_unlock(wrk, &oh, oc));
475	1640	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	1640	return (HSH_HIT);
482		}
483
484	104919	if (req->objcore != NULL) {
485	577	oh = req->objcore->objhead;
486	577	(void)HSH_DerefObjCore(wrk, &req->objcore);
487	577	Lck_Lock(&oh->mtx);
488	577	} else {
489	104342	AN(wrk->wpriv->nobjhead);
490	104342	oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
491		}
492
493	104919	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
494	104919	Lck_AssertHeld(&oh->mtx);
495
496	104919	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	600	*bocp = hsh_insert_busyobj(wrk, oh);