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) tupple, 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;
static struct objhead *private_oh;

static void hsh_rush1(const struct worker *, struct objhead *,
    struct rush *, int);
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,
    int);

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

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

VCF_RETURNS()
#undef VCF_RETURN

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

static struct objhead *
hsh_newobjhead(void)
{
        struct objhead *oh;

        ALLOC_OBJ(oh, OBJHEAD_MAGIC);
        XXXAN(oh);
        oh->refcnt = 1;
        VTAILQ_INIT(&oh->objcs);
        VTAILQ_INIT(&oh->waitinglist);
        Lck_New(&oh->mtx, lck_objhdr);
        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);
}

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

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

        CHECK_OBJ_NOTNULL(private_oh, OBJHEAD_MAGIC);

        oc = ObjNew(wrk);
        AN(oc);
        oc->refcnt = 1;
        oc->objhead = private_oh;
        oc->flags |= OC_F_PRIVATE;
        Lck_Lock(&private_oh->mtx);
        VTAILQ_INSERT_TAIL(&private_oh->objcs, oc, hsh_list);
        private_oh->refcnt++;
        Lck_Unlock(&private_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 (sizeof hsh_magiclist / sizeof hsh_magiclist[0])

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);
        AN(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);
        oc->flags &= ~OC_F_BUSY;
        if (!VTAILQ_EMPTY(&oh->waitinglist))
                hsh_rush1(wrk, oh, &rush, HSH_RUSH_POLICY);
        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);

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

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

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;
        const uint8_t *vary;
        intmax_t boc_progress;
        unsigned xid = 0;
        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->vcf, VCF_MAGIC);
        AN(hash);

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

        if (req->hash_objhead != NULL) {
                /*
                 * This req came off the waiting list, and brings an
                 * oh refcnt with it.
                 */
                CHECK_OBJ_NOTNULL(req->hash_objhead, OBJHEAD_MAGIC);
                oh = req->hash_objhead;
                Lck_Lock(&oh->mtx);
                req->hash_objhead = NULL;
        } 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;
        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 &&
                            !req->hash_ignore_vary &&
                            !VRY_Match(req, oc->boc->vary)) {
                                wrk->strangelove++;
                                continue;
                        }

                        busy_found = 1;
                        continue;
                }

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

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

                if (!req->hash_ignore_vary && ObjHasAttr(wrk, oc, OA_VARY)) {
                        vary = ObjGetAttr(wrk, oc, OA_VARY, NULL);
                        AN(vary);
                        if (!VRY_Match(req, vary)) {
                                wrk->strangelove++;
                                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.ttl */
                    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, HSH_RUSH_POLICY));
                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, HSH_RUSH_POLICY));
                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, 0));
                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 transfers to the sess, we get it
         * back when the sess comes off the waiting list and
         * calls us again
         */
        req->hash_objhead = oh;
        req->wrk = NULL;
        req->waitinglist = 1;

        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 objhead *oh, struct rush *r, int max)
{
        int i;
        struct req *req;

        if (max == 0)
                return;
        if (max == HSH_RUSH_POLICY)
                max = cache_param->rush_exponent;
        assert(max > 0);

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
        CHECK_OBJ_NOTNULL(r, RUSH_MAGIC);
        VTAILQ_INIT(&r->reqs);
        Lck_AssertHeld(&oh->mtx);
        for (i = 0; i < max; i++) {
                req = VTAILQ_FIRST(&oh->waitinglist);
                if (req == NULL)
                        break;
                CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
                wrk->stats->busy_wakeup++;
                AZ(req->wrk);
                VTAILQ_REMOVE(&oh->waitinglist, req, w_list);
                VTAILQ_INSERT_TAIL(&r->reqs, req, w_list);
                req->waitinglist = 0;
        }
}

/*---------------------------------------------------------------------
 * 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;
                        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]);
                        else
                                EXP_Rearm(ocp[i], ttl_now, ttl, grace, keep);
                        (void)HSH_DerefObjCore(wrk, &ocp[i], 0);
                        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 objcore *oc)
{
        struct objhead *oh;

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

        /*
         * We have to have either a busy bit, so that HSH_Lookup
         * will not consider this oc, or an object hung of the oc
         * so that it can consider it.
         */
        assert((oc->flags & OC_F_BUSY) || (oc->stobj->stevedore != NULL));

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

/*---------------------------------------------------------------------
 * 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_PRIVATE | OC_F_HFM | OC_F_HFP)) == 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);
}

/*---------------------------------------------------------------------
 * 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);
        INIT_OBJ(&rush, RUSH_MAGIC);

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

        if (!(oc->flags & OC_F_PRIVATE)) {
                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);
        if (!(oc->flags & OC_F_PRIVATE))
                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, oh, &rush, HSH_RUSH_POLICY);
        }
        Lck_Unlock(&oh->mtx);
        EXP_Insert(wrk, oc); /* Does nothing unless EXP_RefNewObjcore was
                              * called */
        hsh_rush2(wrk, &rush);
}

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

void
HSH_Kill(struct objcore *oc)
{

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

        Lck_Lock(&oc->objhead->mtx);
        oc->flags |= OC_F_DYING;
        Lck_Unlock(&oc->objhead->mtx);
        EXP_Remove(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);
        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, int rushmax)
{
        struct objcore *oc;
        struct objhead *oh;
        struct rush rush;
        int r;

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

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

        Lck_Lock(&oh->mtx);
        assert(oh->refcnt > 0);
        r = --oc->refcnt;
        if (!r)
                VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
        if (!VTAILQ_EMPTY(&oh->waitinglist)) {
                assert(oh->refcnt > 1);
                hsh_rush1(wrk, oh, &rush, rushmax);
        }
        Lck_Unlock(&oh->mtx);
        hsh_rush2(wrk, &rush);
        if (r != 0)
                return (r);

        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, int max)
{
        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_oh) {
                assert(VTAILQ_EMPTY(&oh->waitinglist));
                assert(oh->refcnt > 1);
                oh->refcnt--;
                Lck_Unlock(&oh->mtx);
                return (1);
        }

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

        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, 0));
}

void
HSH_Init(const struct hash_slinger *slinger)
{

        assert(DIGEST_LEN == VSHA256_LEN);      /* avoid #include pollution */
        hash = slinger;
        if (hash->start != NULL)
                hash->start();
        private_oh = hsh_newobjhead();
        private_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) tupple, 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		static struct objhead *private_oh;
76
77		static void hsh_rush1(const struct worker , struct objhead ,
78		struct rush *, int);
79		static void hsh_rush2(struct worker , struct rush );
80		static int hsh_deref_objhead(struct worker wrk, struct objhead *poh);
81		static int hsh_deref_objhead_unlock(struct worker wrk, struct objhead *poh,
82		int);
83
84		/---------------------------------------------------------------------/
85
86		#define VCF_RETURN(x) const struct vcf_return VCF_##x[1] = { \
87		{ .name = #x, } \
88		};
89
90		VCF_RETURNS()
91		#undef VCF_RETURN
92
93		/---------------------------------------------------------------------/
94
95		static struct objhead *
96	59233	hsh_newobjhead(void)
97		{
98		struct objhead *oh;
99
100	59233	ALLOC_OBJ(oh, OBJHEAD_MAGIC);
101	59233	XXXAN(oh);
102	59233	oh->refcnt = 1;
103	59233	VTAILQ_INIT(&oh->objcs);
104	59233	VTAILQ_INIT(&oh->waitinglist);
105	59233	Lck_New(&oh->mtx, lck_objhdr);
106	59233	return (oh);
107		}
108
109		/---------------------------------------------------------------------/
110		/* Precreate an objhead and object for later use */
111		static void
112	61641	hsh_prealloc(struct worker *wrk)
113		{
114
115	61641	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
116
117	61641	if (wrk->wpriv->nobjcore == NULL)
118	42321	wrk->wpriv->nobjcore = ObjNew(wrk);
119	61641	CHECK_OBJ_NOTNULL(wrk->wpriv->nobjcore, OBJCORE_MAGIC);
120
121	61641	if (wrk->wpriv->nobjhead == NULL) {
122	37038	wrk->wpriv->nobjhead = hsh_newobjhead();
123	37038	wrk->stats->n_objecthead++;
124	37038	}
125	61641	CHECK_OBJ_NOTNULL(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
126
127	61641	if (hash->prep != NULL)
128	61490	hash->prep(wrk);
129	61641	}
130
131		/---------------------------------------------------------------------/
132
133		struct objcore *
134	31575	HSH_Private(const struct worker *wrk)
135		{
136		struct objcore *oc;
137
138	31575	CHECK_OBJ_NOTNULL(private_oh, OBJHEAD_MAGIC);
139
140	31575	oc = ObjNew(wrk);
141	31575	AN(oc);
142	31575	oc->refcnt = 1;
143	31575	oc->objhead = private_oh;
144	31575	oc->flags \|= OC_F_PRIVATE;
145	31575	Lck_Lock(&private_oh->mtx);
146	31575	VTAILQ_INSERT_TAIL(&private_oh->objcs, oc, hsh_list);
147	31575	private_oh->refcnt++;
148	31575	Lck_Unlock(&private_oh->mtx);
149	31575	return (oc);
150		}
151
152		/---------------------------------------------------------------------/
153
154		void
155	22571	HSH_Cleanup(const struct worker *wrk)
156		{
157
158	22571	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
159	22571	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
160	22571	if (wrk->wpriv->nobjcore != NULL)
161	34	ObjDestroy(wrk, &wrk->wpriv->nobjcore);
162
163	22571	if (wrk->wpriv->nobjhead != NULL) {
164	34	CHECK_OBJ(wrk->wpriv->nobjhead, OBJHEAD_MAGIC);
165	34	Lck_Delete(&wrk->wpriv->nobjhead->mtx);
166	34	FREE_OBJ(wrk->wpriv->nobjhead);
167	34	wrk->stats->n_objecthead--;
168	34	}
169	22571	if (wrk->wpriv->nhashpriv != NULL) {
170		/* XXX: If needed, add slinger method for this */
171	50	free(wrk->wpriv->nhashpriv);
172	50	wrk->wpriv->nhashpriv = NULL;
173	50	}
174	22571	}
175
176		void
177	0	HSH_DeleteObjHead(const struct worker wrk, struct objhead oh)
178		{
179	0	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
180	0	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
181
182	0	AZ(oh->refcnt);
183	0	assert(VTAILQ_EMPTY(&oh->objcs));
184	0	assert(VTAILQ_EMPTY(&oh->waitinglist));
185	0	Lck_Delete(&oh->mtx);
186	0	wrk->stats->n_objecthead--;
187	0	FREE_OBJ(oh);
188	0	}
189
190		void
191	341735	HSH_AddString(struct req req, void ctx, const char *str)
192		{
193
194	341735	CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
195	341735	AN(ctx);
196	341735	if (str != NULL) {
197	170934	VSHA256_Update(ctx, str, strlen(str));
198	170934	VSLbs(req->vsl, SLT_Hash, TOSTRAND(str));
199	170934	} else
200	170801	VSHA256_Update(ctx, &str, 1);
201	341735	}
202
203		/*---------------------------------------------------------------------
204		* This is a debugging hack to enable testing of boundary conditions
205		* in the hash algorithm.
206		* We trap the first 9 different digests and translate them to different
207		* digests with edge bit conditions
208		*/
209
210		static struct hsh_magiclist {
211		unsigned char was[VSHA256_LEN];
212		unsigned char now[VSHA256_LEN];
213		} hsh_magiclist[] = {
214		{ .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
215		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
216		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
217		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
218		{ .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
219		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
220		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
221		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 } },
222		{ .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
223		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
224		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
225		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02 } },
226		{ .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
227		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
228		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
229		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40 } },
230		{ .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
231		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
232		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
233		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80 } },
234		{ .now = { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
235		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
236		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
237		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } },
238		{ .now = { 0x02, 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 = { 0x80, 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, 0x00 } },
246		{ .now = { 0x40, 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, 0x00 } },
250		};
251
252		#define HSH_NMAGIC (sizeof hsh_magiclist / sizeof hsh_magiclist[0])
253
254		static void
255	450	hsh_testmagic(void *result)
256		{
257		size_t i, j;
258		static size_t nused = 0;
259
260	2250	for (i = 0; i < nused; i++)
261	2025	if (!memcmp(hsh_magiclist[i].was, result, VSHA256_LEN))
262	225	break;
263	450	if (i == nused && i < HSH_NMAGIC)
264	225	memcpy(hsh_magiclist[nused++].was, result, VSHA256_LEN);
265	450	if (i == nused)
266	0	return;
267	450	assert(i < HSH_NMAGIC);
268	450	fprintf(stderr, "HASHMAGIC: <");
269	14850	for (j = 0; j < VSHA256_LEN; j++)
270	14400	fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
271	450	fprintf(stderr, "> -> <");
272	450	memcpy(result, hsh_magiclist[i].now, VSHA256_LEN);
273	14850	for (j = 0; j < VSHA256_LEN; j++)
274	14400	fprintf(stderr, "%02x", ((unsigned char*)result)[j]);
275	450	fprintf(stderr, ">\n");
276	450	}
277
278		/*---------------------------------------------------------------------
279		* Insert an object which magically appears out of nowhere or, more likely,
280		* comes off some persistent storage device.
281		* Insert it with a reference held.
282		*/
283
284		void
285	425	HSH_Insert(struct worker wrk, const void digest, struct objcore *oc,
286		struct ban *ban)
287		{
288		struct objhead *oh;
289		struct rush rush;
290
291	425	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
292	425	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
293	425	AN(digest);
294	425	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
295	425	AN(ban);
296	425	AN(oc->flags & OC_F_BUSY);
297	425	AZ(oc->flags & OC_F_PRIVATE);
298	425	assert(oc->refcnt == 1);
299	425	INIT_OBJ(&rush, RUSH_MAGIC);
300
301	425	hsh_prealloc(wrk);
302
303	425	AN(wrk->wpriv->nobjhead);
304	425	oh = hash->lookup(wrk, digest, &wrk->wpriv->nobjhead);
305	425	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
306	425	Lck_AssertHeld(&oh->mtx);
307	425	assert(oh->refcnt > 0);
308
309		/* Mark object busy and insert (precreated) objcore in
310		objecthead. The new object inherits our objhead reference. */
311	425	oc->objhead = oh;
312	425	VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
313	425	EXP_RefNewObjcore(oc);
314	425	Lck_Unlock(&oh->mtx);
315
316	425	BAN_RefBan(oc, ban);
317	425	AN(oc->ban);
318
319		/* Move the object first in the oh list, unbusy it and run the
320		waitinglist if necessary */
321	425	Lck_Lock(&oh->mtx);
322	425	VTAILQ_REMOVE(&oh->objcs, oc, hsh_list);
323	425	VTAILQ_INSERT_HEAD(&oh->objcs, oc, hsh_list);
324	425	oc->flags &= ~OC_F_BUSY;
325	425	if (!VTAILQ_EMPTY(&oh->waitinglist))
326	0	hsh_rush1(wrk, oh, &rush, HSH_RUSH_POLICY);
327	425	Lck_Unlock(&oh->mtx);
328	425	hsh_rush2(wrk, &rush);
329
330	425	EXP_Insert(wrk, oc);
331	425	}
332
333		/*---------------------------------------------------------------------
334		*/
335
336		static struct objcore *
337	35913	hsh_insert_busyobj(const struct worker wrk, struct objhead oh)
338		{
339		struct objcore *oc;
340
341	35913	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
342	35913	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
343	35913	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
344	35913	Lck_AssertHeld(&oh->mtx);
345
346	35913	oc = wrk->wpriv->nobjcore;
347	35913	wrk->wpriv->nobjcore = NULL;
348	35913	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
349
350	35913	AN(oc->flags & OC_F_BUSY);
351	35913	oc->refcnt = 1; /* Owned by busyobj */
352	35913	oc->objhead = oh;
353	35913	VTAILQ_INSERT_TAIL(&oh->objcs, oc, hsh_list);
354	35913	return (oc);
355		}
356
357		/*---------------------------------------------------------------------
358		*/
359
360		enum lookup_e
361	61217	HSH_Lookup(struct req req, struct objcore ocp, struct objcore *bocp)
362		{
363		struct worker *wrk;
364		struct objhead *oh;
365		struct objcore *oc;
366		struct objcore *exp_oc;
367		const struct vcf_return *vr;
368		vtim_real exp_t_origin;
369		int busy_found;
370		const uint8_t *vary;
371		intmax_t boc_progress;
372	61217	unsigned xid = 0;
373	61217	float dttl = 0.0;
374
375	61217	AN(ocp);
376	61217	*ocp = NULL;
377	61217	AN(bocp);
378	61217	*bocp = NULL;
379
380	61217	CHECK_OBJ_NOTNULL(req, REQ_MAGIC);
381	61217	wrk = req->wrk;
382	61217	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
383	61217	CHECK_OBJ_NOTNULL(wrk->wpriv, WORKER_PRIV_MAGIC);
384	61217	CHECK_OBJ_NOTNULL(req->http, HTTP_MAGIC);
385	61217	CHECK_OBJ_ORNULL(req->vcf, VCF_MAGIC);
386	61217	AN(hash);
387
388	61217	hsh_prealloc(wrk);
389	61217	if (DO_DEBUG(DBG_HASHEDGE))
390	450	hsh_testmagic(req->digest);
391
392	61217	if (req->hash_objhead != NULL) {
393		/*
394		* This req came off the waiting list, and brings an
395		* oh refcnt with it.
396		*/
397	1162	CHECK_OBJ_NOTNULL(req->hash_objhead, OBJHEAD_MAGIC);
398	1162	oh = req->hash_objhead;
399	1162	Lck_Lock(&oh->mtx);
400	1162	req->hash_objhead = NULL;
401	1162	} else {
402	60055	AN(wrk->wpriv->nobjhead);
403	60055	oh = hash->lookup(wrk, req->digest, &wrk->wpriv->nobjhead);
404		}
405
406	61217	CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
407	61217	Lck_AssertHeld(&oh->mtx);
408
409	61217	if (req->hash_always_miss) {
410		/* XXX: should we do predictive Vary in this case ? */
411		/* Insert new objcore in objecthead and release mutex */
412	350	*bocp = hsh_insert_busyobj(wrk, oh);
413		/* NB: no deref of objhead, new object inherits reference */
414	350	Lck_Unlock(&oh->mtx);
415	350	return (HSH_MISS);
416		}
417
418	60867	assert(oh->refcnt > 0);
419	60867	busy_found = 0;
420	60867	exp_oc = NULL;
421	60867	exp_t_origin = 0.0;
422	132815	VTAILQ_FOREACH(oc, &oh->objcs, hsh_list) {
423		/* Must be at least our own ref + the objcore we examine */
424	96843	assert(oh->refcnt > 1);
425	96843	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
426	96843	assert(oc->objhead == oh);
427	96843	assert(oc->refcnt > 0);
428
429	96843	if (oc->flags & OC_F_DYING)
430	0	continue;
431	96843	if (oc->flags & OC_F_FAILED)
432	0	continue;
433
434	96843	CHECK_OBJ_ORNULL(oc->boc, BOC_MAGIC);
435	96843	if (oc->flags & OC_F_BUSY) {
436	1309	if (req->hash_ignore_busy)
437	25	continue;
438
439	1357	if (oc->boc && oc->boc->vary != NULL &&
440	73	!req->hash_ignore_vary &&
441	73	!VRY_Match(req, oc->boc->vary)) {
442	25	wrk->strangelove++;
443	25	continue;
444		}
445
446	1259	busy_found = 1;
447	1259	continue;
448		}
449
450	95534	if (oc->ttl <= 0.)
451	1150	continue;
452
453	94384	if (BAN_CheckObject(wrk, oc, req)) {
454	800	oc->flags \|= OC_F_DYING;
455	800	EXP_Remove(oc);
456	800	continue;
457		}
458
459	93584	if (!req->hash_ignore_vary && ObjHasAttr(wrk, oc, OA_VARY)) {
460	69175	vary = ObjGetAttr(wrk, oc, OA_VARY, NULL);
461	69175	AN(vary);
462	69175	if (!VRY_Match(req, vary)) {
463	65450	wrk->strangelove++;
464	65450	continue;
465		}
466	3725	}
467
468	28134	if (req->vcf != NULL) {
469	200	vr = req->vcf->func(req, &oc, &exp_oc, 0);
470	200	if (vr == VCF_CONTINUE)
471	100	continue;
472	100	if (vr == VCF_MISS) {
473	75	oc = NULL;
474	75	break;
475		}
476	25	if (vr == VCF_HIT)
477	25	break;
478	0	assert(vr == VCF_DEFAULT);
479	0	}
480
481	27934	if (EXP_Ttl(req, oc) > req->t_req) {
482	24795	assert(oh->refcnt > 1);
483	24795	assert(oc->objhead == oh);
484	24795	break;
485		}
486
487	3139	if (EXP_Ttl(NULL, oc) < req->t_req && /* ignore req.ttl */
488	3050	oc->t_origin > exp_t_origin) {
489		/* record the newest object */
490	3025	exp_oc = oc;
491	3025	exp_t_origin = oc->t_origin;
492	3025	assert(oh->refcnt > 1);
493	3025	assert(exp_oc->objhead == oh);
494	3025	}
495	3139	}
496
497	60867	if (req->vcf != NULL)
498	150	(void)req->vcf->func(req, &oc, &exp_oc, 1);
499