GCOV - Varnish Cache


/*-
 * Copyright (c) 2016 Varnish Software AS
 * All rights reserved.
 *
 * Author: Martin Blix Grydeland <martin@varnish-software.com>
 *
 * 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.
 *
 * Layout:
 *
 * buf [
 *    <x bytes name index n - 1> <x bytes value index n - 1>
 *    <x bytes name index n - 2> <x bytes value index n - 2>
 *    ...
 *    <x bytes name index 0> <x bytes value index 0>
 *
 *    (padding bytes for pointer alignment)
 *
 *    <struct vht_entry index 0>
 *    <struct vht_entry index 1>
 *    ...
 *    <struct vht_entry index n - 1>
 * ]
 *
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>

#include "vdef.h"
#include "miniobj.h"
#include "vas.h"

#include "hpack/vhp.h"

#define VHT_STATIC_MAX 61

struct vht_static {
        const char *name;
        unsigned namelen;
        const char *value;
        unsigned valuelen;
};

static const struct vht_static static_table[] = {
#define HPS(NUM, NAME, VAL)                     \
        { NAME, sizeof NAME - 1, VAL, sizeof VAL - 1 },
#include "tbl/vhp_static.h"
};

#define TBLSIZE(tbl) ((tbl)->size + (tbl)->n * VHT_ENTRY_SIZE)
#define ENTRIES(buf, bufsize, n)                                        \
        (((struct vht_entry *)((uintptr_t)(buf) + bufsize)) - (n))
#define TBLENTRIES(tbl) ENTRIES((tbl)->buf, (tbl)->bufsize, (tbl)->n)
#define TBLENTRY(tbl, i) (&TBLENTRIES(tbl)[(i)])
#define ENTRYLEN(e) ((e)->namelen + (e)->valuelen)
#define ENTRYSIZE(e) (ENTRYLEN(e) + VHT_ENTRY_SIZE)

/****************************************************************************/
/* Internal interface */

static void
vht_newentry(struct vht_table *tbl)
{
        struct vht_entry *e;

        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE);
        tbl->n++;
        e = TBLENTRY(tbl, 0);
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
        e->offset = tbl->size;
}

/* Trim elements from the end until the table size is less than max. */
static void
vht_trim(struct vht_table *tbl, ssize_t max)
{
        unsigned u, v;
        int i;
        struct vht_entry *e;

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);

        if (max < 0)
                max = 0;
        if (TBLSIZE(tbl) <= max)
                return;

        u = v = 0;
        for (i = tbl->n - 1; i >= 0; i--) {
                e = TBLENTRY(tbl, i);
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
                if (TBLSIZE(tbl) - (u + v * VHT_ENTRY_SIZE) > max) {
                        /* Trim entry */
                        assert(e->offset == u);
                        u += ENTRYLEN(e);
                        v++;
                        FINI_OBJ(e);
                } else {
                        /* Fixup offset */
                        assert(e->offset >= u);
                        e->offset -= u;
                }
        }
        assert(v <= tbl->n);

        vmemmove(tbl->buf, tbl->buf + u, tbl->size - u);
        vmemmove(TBLENTRY(tbl, v), TBLENTRY(tbl, 0), (tbl->n - v) * sizeof *e);
        tbl->n -= v;
        tbl->size -= u;
}

/* Append len bytes from buf to entry 0 name. Asserts if no space. */
static void
vht_appendname(struct vht_table *tbl, const char *buf, size_t len)
{
        struct vht_entry *e;

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        e = TBLENTRY(tbl, 0);
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
        AZ(e->valuelen);        /* Name needs to be set before value */
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
        assert(e->offset + e->namelen == tbl->size);
        vmemcpy(tbl->buf + tbl->size, buf, len);
        e->namelen += len;
        tbl->size += len;
}

/* Append len bytes from buf to entry 0 value. Asserts if no space. */
static void
vht_appendvalue(struct vht_table *tbl, const char *buf, size_t len)
{
        struct vht_entry *e;

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        e = TBLENTRY(tbl, 0);
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
        assert(e->offset + e->namelen + e->valuelen == tbl->size);
        vmemcpy(tbl->buf + tbl->size, buf, len);
        e->valuelen += len;
        tbl->size += len;
}

/****************************************************************************/
/* Public interface */

void
VHT_NewEntry(struct vht_table *tbl)
{

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(tbl->maxsize <= tbl->protomax);
        vht_trim(tbl, tbl->maxsize - VHT_ENTRY_SIZE);
        if (tbl->maxsize - TBLSIZE(tbl) < VHT_ENTRY_SIZE) {
                /* Maxsize less than one entry */
                assert(tbl->maxsize < VHT_ENTRY_SIZE);
                return;
        }
        vht_newentry(tbl);
}

int
VHT_NewEntry_Indexed(struct vht_table *tbl, unsigned idx)
{
        struct vht_entry *e, *e2;
        unsigned l, l2, lentry, lname, u;
        uint8_t tmp[48];

        /* Referenced name insertion. This has to be done carefully
           because the referenced name may be evicted as the result of the
           insertion (RFC 7541 section 4.4). */

        assert(sizeof tmp >= VHT_ENTRY_SIZE);

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(tbl->maxsize <= tbl->protomax);

        if (idx == 0)
                return (-1);

        if (idx <= VHT_STATIC_MAX) {
                /* Static table reference */
                VHT_NewEntry(tbl);
                VHT_AppendName(tbl, static_table[idx - 1].name,
                    static_table[idx - 1].namelen);
                return (0);
        }
        idx -= VHT_STATIC_MAX + 1;

        if (idx >= tbl->n)
                return (-1);    /* No such index */
        assert(tbl->maxsize >= VHT_ENTRY_SIZE);

        e = TBLENTRY(tbl, idx);
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);

        /* Count how many elements we can safely evict to make space
           without evicting the referenced entry. */
        l = 0;
        u = 0;
        while (tbl->n - 1 - u > idx &&
            tbl->maxsize - TBLSIZE(tbl) + l < VHT_ENTRY_SIZE + e->namelen) {
                e2 = TBLENTRY(tbl, tbl->n - 1 - u);
                CHECK_OBJ_NOTNULL(e2, VHT_ENTRY_MAGIC);
                l += ENTRYSIZE(e2);
                u++;
        }
        vht_trim(tbl, TBLSIZE(tbl) - l);
        e += u;
        assert(e == TBLENTRY(tbl, idx));

        if (tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + e->namelen) {
                /* New entry with name fits */
                vht_newentry(tbl);
                idx++;
                assert(e == TBLENTRY(tbl, idx));
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
                vht_appendname(tbl, tbl->buf + e->offset, e->namelen);
                return (0);
        }

        /* The tricky case: The referenced name will be evicted as a
           result of the insertion. Move the referenced element data to
           the end of the buffer through a local buffer. */

        /* Remove the referenced element from the entry list */
        assert(idx == tbl->n - 1);
        assert(e->offset == 0);
        lname = e->namelen;
        lentry = ENTRYLEN(e);
        FINI_OBJ(e);
        vmemmove(TBLENTRY(tbl, 1), TBLENTRY(tbl, 0), (tbl->n - 1) * sizeof *e);
        tbl->n--;

        /* Shift the referenced element last using a temporary buffer. */
        l = 0;
        while (l < lentry) {
                l2 = lentry - l;
                if (l2 > sizeof tmp)
                        l2 = sizeof tmp;
                vmemcpy(tmp, tbl->buf, l2);
                vmemmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
                vmemcpy(tbl->buf + tbl->size - l2, tmp, l2);
                l += l2;
        }
        assert(l == lentry);
        tbl->size -= lentry;

        /* Fix up the existing element offsets */
        for (u = 0; u < tbl->n; u++) {
                e = TBLENTRY(tbl, u);
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
                assert(e->offset >= lentry);
                e->offset -= lentry;
                assert(e->offset + ENTRYLEN(e) <= tbl->size);
        }

        /* Insert the new entry with the name now present at the end of
           the buffer. */
        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + lname);
        tbl->n++;
        e = TBLENTRY(tbl, 0);
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
        e->offset = tbl->size;
        e->namelen = lname;
        tbl->size += lname;

        return (0);
}

void
VHT_AppendName(struct vht_table *tbl, const char *buf, ssize_t len)
{

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(tbl->maxsize <= tbl->protomax);
        if (len == 0)
                return;
        AN(buf);
        if (len < 0)
                len = vstrlen(buf);
        vht_trim(tbl, tbl->maxsize - len);
        if (tbl->n == 0)
                /* Max size exceeded */
                return;
        vht_appendname(tbl, buf, len);
}

void
VHT_AppendValue(struct vht_table *tbl, const char *buf, ssize_t len)
{

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(tbl->maxsize <= tbl->protomax);
        if (len == 0)
                return;
        AN(buf);
        if (len < 0)
                len = vstrlen(buf);
        vht_trim(tbl, tbl->maxsize - len);
        if (tbl->n == 0)
                /* Max size exceeded */
                return;
        vht_appendvalue(tbl, buf, len);
}

int
VHT_SetMaxTableSize(struct vht_table *tbl, size_t maxsize)
{

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(tbl->maxsize <= tbl->protomax);
        if (maxsize > tbl->protomax)
                return (-1);
        vht_trim(tbl, maxsize);
        assert(TBLSIZE(tbl) <= maxsize);
        tbl->maxsize = maxsize;
        return (0);
}

int
VHT_SetProtoMax(struct vht_table *tbl, size_t protomax)
{
        size_t bufsize;
        char *buf;

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        assert(protomax <= UINT_MAX);
        assert(tbl->maxsize <= tbl->protomax);

        if (protomax == tbl->protomax)
                return (0);

        if (tbl->maxsize > protomax)
                tbl->maxsize = protomax;
        vht_trim(tbl, tbl->maxsize);
        assert(TBLSIZE(tbl) <= tbl->maxsize);

        bufsize = PRNDUP(protomax);
        if (bufsize == tbl->bufsize) {
                tbl->protomax = protomax;
                return (0);
        }

        buf = malloc(bufsize);
        if (buf == NULL)
                return (-1);

        if (tbl->buf != NULL) {
                vmemcpy(buf, tbl->buf, tbl->size);
                vmemcpy(ENTRIES(buf, bufsize, tbl->n), TBLENTRIES(tbl),
                        sizeof(struct vht_entry) * tbl->n);
                free(tbl->buf);
        }
        tbl->buf = buf;
        tbl->bufsize = bufsize;
        tbl->protomax = protomax;
        return (0);
}

const char *
VHT_LookupName(const struct vht_table *tbl, unsigned idx, size_t *plen)
{
        struct vht_entry *e;

        AN(plen);
        *plen = 0;

        if (idx == 0) {
                return (NULL);
        }
        if (idx <= VHT_STATIC_MAX) {
                *plen = static_table[idx - 1].namelen;
                return (static_table[idx - 1].name);
        }

        if (tbl == NULL)
                return (NULL);
        CHECK_OBJ(tbl, VHT_TABLE_MAGIC);

        idx -= VHT_STATIC_MAX + 1;
        if (idx >= tbl->n)
                return (NULL);

        e = TBLENTRY(tbl, idx);
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
        assert(e->offset + e->namelen <= tbl->size);
        *plen = e->namelen;
        return (tbl->buf + e->offset);
}

const char *
VHT_LookupValue(const struct vht_table *tbl, unsigned idx, size_t *plen)
{
        struct vht_entry *e;

        AN(plen);
        *plen = 0;

        if (idx == 0) {
                return (NULL);
        }
        if (idx <= VHT_STATIC_MAX) {
                *plen = static_table[idx - 1].valuelen;
                return (static_table[idx - 1].value);
        }

        if (tbl == NULL)
                return (NULL);
        CHECK_OBJ(tbl, VHT_TABLE_MAGIC);

        idx -= VHT_STATIC_MAX + 1;
        if (idx >= tbl->n)
                return (NULL);

        e = TBLENTRY(tbl, idx);
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
        assert(e->offset + e->namelen + e->valuelen <= tbl->size);
        *plen = e->valuelen;
        return (tbl->buf + e->offset + e->namelen);
}

int
VHT_Init(struct vht_table *tbl, size_t protomax)
{
        int r;

        assert(sizeof (struct vht_entry) <= VHT_ENTRY_SIZE);

        AN(tbl);
        if (protomax > UINT_MAX)
                return (-1);
        INIT_OBJ(tbl, VHT_TABLE_MAGIC);
        r = VHT_SetProtoMax(tbl, protomax);
        if (r) {
                FINI_OBJ(tbl);
                return (r);
        }
        tbl->maxsize = tbl->protomax;
        return (0);
}

void
VHT_Fini(struct vht_table *tbl)
{

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
        free(tbl->buf);
        memset(tbl, 0, sizeof *tbl);
}

/****************************************************************************/
/* Internal interface */

#ifdef TABLE_TEST_DRIVER

#define VHT_DYNAMIC (VHT_STATIC_MAX + 1)

static int verbose = 0;

static int
vht_matchtable(struct vht_table *tbl, ...)
{
        va_list ap;
        unsigned u;
        int r;
        const char *a, *b;
        const struct vht_entry *e;

        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);

        va_start(ap, tbl);
        r = 0;
        for (u = 0; u < tbl->n; u++) {
                a = NULL;
                b = NULL;
                if (!r) {
                        a = va_arg(ap, const char *);
                        if (a == NULL) {
                                printf("Too many elements in table\n");
                                r = -1;
                        } else {
                                b = va_arg(ap, const char *);
                                AN(b);
                        }
                }

                e = TBLENTRY(tbl, u);
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);

                if (a) {
                        AN(b);
                        if (e->namelen != vstrlen(a) ||
                            vstrncmp(a, tbl->buf + e->offset, e->namelen))
                                r = -1;
                        if (e->valuelen != vstrlen(b) ||
                            vstrncmp(b, tbl->buf + e->offset + e->namelen,
                             e->valuelen))
                                r = -1;
                }

                if (verbose || r)
                        printf("%2u: @%03u (\"%.*s\", \"%.*s\")",
                            u, e->offset, (int)e->namelen, tbl->buf + e->offset,
                            (int)e->valuelen, tbl->buf + e->offset +e->namelen);

                if (a && (verbose || r)) {
                        AN(b);
                        printf(" %s (\"%s\", \"%s\")", (r ? "!=" : "=="), a, b);
                }

                if (verbose || r)
                        printf("\n");
        }
        if (!r) {
                a = va_arg(ap, const char *);
                if (a != NULL) {
                        printf("Missing elements in table\n");
                        r = -1;
                }
        }
        va_end(ap);

        if (verbose || r)
                printf("n=%d, size=%u, tblsz=%u, max=%u, pmax=%u, bufsz=%u\n",
                    tbl->n, tbl->size, TBLSIZE(tbl), tbl->maxsize,
                    tbl->protomax, tbl->bufsize);

        return (r);
}

static void
test_1(void)
{
        /* Static table */

        const char *p;
        size_t l;

        if (verbose)
                printf("Test 1:\n");

        /* 1: ':authority' -> '' */
        p = VHT_LookupName(NULL, 1, &l);
        assert(l == vstrlen(":authority"));
        AZ(vstrncmp(p, ":authority", vstrlen(":authority")));
        p = VHT_LookupValue(NULL, 1, &l);
        AN(p);
        AZ(l);

        /* 5: ':path' -> '/index.html' */
        p = VHT_LookupValue(NULL, 5, &l);
        assert(l == vstrlen("/index.html"));
        AZ(vstrncmp(p, "/index.html", vstrlen("/index.html")));

        /* 61: 'www-authenticate' -> '' */
        p = VHT_LookupName(NULL, 61, &l);
        assert(l == vstrlen("www-authenticate"));
        AZ(vstrncmp(p, "www-authenticate", vstrlen("www-authenticate")));
        p = VHT_LookupValue(NULL, 61, &l);
        AN(p);
        AZ(l);

        /* Test zero index */
        AZ(VHT_LookupName(NULL, 0, &l));
        AZ(l);
        AZ(VHT_LookupValue(NULL, 0, &l));
        AZ(l);

        printf("Test 1 finished successfully\n");
        if (verbose)
                printf("\n");
}

static void
test_2(void)
{
        /* Test filling and overflow */

        struct vht_table tbl[1];

        if (verbose)
                printf("Test 2:\n");

        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE + 10));

        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, "12345", -1);
        VHT_AppendValue(tbl, "abcde", -1);
        assert(TBLSIZE(tbl) == VHT_ENTRY_SIZE + 10);
        /* 0: '12345' -> 'abcde' */
        AZ(vht_matchtable(tbl, "12345", "abcde", NULL));

        VHT_AppendValue(tbl, "f", -1);
        AZ(vht_matchtable(tbl, NULL));

        VHT_NewEntry(tbl);
        AZ(vht_matchtable(tbl, "", "", NULL));

        VHT_Fini(tbl);
        AZ(tbl->buf);

        printf("Test 2 finished successfully\n");
        if (verbose)
                printf("\n");
}

static void
test_3(void)
{
        /* Test change in proto max size and dynamic max size */

        struct vht_table tbl[1];

        if (verbose)
                printf("Test 3:\n");

        AZ(VHT_Init(tbl, 4096));

        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, "a", -1);
        VHT_AppendValue(tbl, "12345", -1);
        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, "b", -1);
        VHT_AppendValue(tbl, "67890", -1);
        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, "c", -1);
        VHT_AppendValue(tbl, "abcde", -1);
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", "a", "12345", NULL));

        /* Buffer reallocation */
        AZ(VHT_SetProtoMax(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", NULL));

        /* Increase table size beyond protomax */
        assert(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 + 1) == -1);

        /* Decrease by one */
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 - 1));
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));

        /* Increase by one back to protomax */
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));

        /* Add entry */
        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, "d", -1);
        VHT_AppendValue(tbl, "ABCDE", -1);
        AZ(vht_matchtable(tbl, "d", "ABCDE", "c", "abcde", NULL));

        /* Set to zero */
        AZ(VHT_SetMaxTableSize(tbl, 0));
        AZ(vht_matchtable(tbl, NULL));
        VHT_NewEntry(tbl);
        AZ(vht_matchtable(tbl, NULL));

        /* Set protomax to zero */
        AZ(VHT_SetProtoMax(tbl, 0));
        AZ(vht_matchtable(tbl, NULL));
        VHT_NewEntry(tbl);
        AZ(vht_matchtable(tbl, NULL));

        VHT_Fini(tbl);

        printf("Test 3 finished successfully\n");
        if (verbose)
                printf("\n");
}

static void
test_4(void)
{
        /* Referenced name new entry */

        struct vht_table tbl[1];
        static const char longname[] =
            "1234567890"
            "1234567890"
            "1234567890"
            "1234567890"
            "1234567890"
            "1";        /* 51 bytes + VHT_ENTRY_SIZE == 83 */

        if (verbose)
                printf("Test 4:\n");

        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE * 2 + 10 * 2)); /* 84 bytes */

        /* New entry indexed from static table */
        AZ(VHT_NewEntry_Indexed(tbl, 4));
        VHT_AppendValue(tbl, "12345", -1);
        AZ(vht_matchtable(tbl, ":path", "12345", NULL));

        /* New entry indexed from dynamic table */
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
        VHT_AppendValue(tbl, "abcde", -1);
        AZ(vht_matchtable(tbl, ":path", "abcde", ":path", "12345", NULL));
        AZ(tbl->maxsize - TBLSIZE(tbl)); /* No space left */

        /* New entry indexed from dynamic table, no overlap eviction */
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
        VHT_AppendValue(tbl, "ABCDE", -1);
        AZ(vht_matchtable(tbl, ":path", "ABCDE", ":path", "abcde", NULL));

        /* New entry indexed from dynamic table, overlap eviction */
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 1));
        AZ(vht_matchtable(tbl, ":path", "", ":path", "ABCDE", NULL));

        /* New entry indexed from dynamic table, overlap eviction with
           overlap larger than the copy buffer size */
        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, longname, vstrlen(longname));
        AZ(vht_matchtable(tbl, longname, "", NULL));
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
        VHT_AppendValue(tbl, "2", -1);
        AZ(vht_matchtable(tbl, longname, "2", NULL));

        VHT_Fini(tbl);
        printf("Test 4 finished successfully\n");
        if (verbose)
                printf("\n");
}

static void
test_5(void)
{
        struct vht_table tbl[1];
        char buf_a[3];
        char buf_b[2];
        int i;

        if (verbose)
                printf("Test 5:\n");

        assert(sizeof buf_a > 0);
        for (i = 0; i < sizeof buf_a - 1; i++)
                buf_a[i] = 'a';
        buf_a[i++] = '\0';

        assert(sizeof buf_b > 0);
        for (i = 0; i < sizeof buf_b - 1; i++)
                buf_b[i] = 'b';
        buf_b[i++] = '\0';

        AZ(VHT_Init(tbl,
                3 * ((sizeof buf_a - 1)+(sizeof buf_b - 1)+VHT_ENTRY_SIZE)));

        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
        AZ(vht_matchtable(tbl, buf_a, buf_b, NULL));

        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, NULL));

        VHT_NewEntry(tbl);
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));

        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 2));
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));

        VHT_Fini(tbl);
        printf("Test 5 finished successfully\n");
        if (verbose)
                printf("\n");
}

int
main(int argc, char **argv)
{

        if (argc == 2 && !vstrcmp(argv[1], "-v"))
                verbose = 1;
        else if (argc != 1) {
                fprintf(stderr, "Usage: %s [-v]\n", argv[0]);
                return (1);
        }

        if (verbose) {
                printf("sizeof (struct vht_table) == %zu\n",
                    sizeof (struct vht_table));
                printf("sizeof (struct vht_entry) == %zu\n",
                    sizeof (struct vht_entry));
                printf("\n");
        }

        test_1();
        test_2();
        test_3();
        test_4();
        test_5();

        return (0);
}

#endif  /* TABLE_TEST_DRIVER */

		vinyl-cache/bin/vinyld/hpack/vhp_table.c
0		/*-
1		* Copyright (c) 2016 Varnish Software AS
2		* All rights reserved.
3		*
4		* Author: Martin Blix Grydeland <martin@varnish-software.com>
5		*
6		* SPDX-License-Identifier: BSD-2-Clause
7		*
8		* Redistribution and use in source and binary forms, with or without
9		* modification, are permitted provided that the following conditions
10		* are met:
11		* 1. Redistributions of source code must retain the above copyright
12		* notice, this list of conditions and the following disclaimer.
13		* 2. Redistributions in binary form must reproduce the above copyright
14		* notice, this list of conditions and the following disclaimer in the
15		* documentation and/or other materials provided with the distribution.
16		*
17		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20		* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27		* SUCH DAMAGE.
28		*
29		* Layout:
30		*
31		* buf [
32		* <x bytes name index n - 1> <x bytes value index n - 1>
33		* <x bytes name index n - 2> <x bytes value index n - 2>
34		* ...
35		* <x bytes name index 0> <x bytes value index 0>
36		*
37		* (padding bytes for pointer alignment)
38		*
39		* <struct vht_entry index 0>
40		* <struct vht_entry index 1>
41		* ...
42		* <struct vht_entry index n - 1>
43		* ]
44		*
45		*/
46
47		#include "config.h"
48
49		#include <stdio.h>
50		#include <stdlib.h>
51		#include <stdarg.h>
52		#include <string.h>
53		#include <stdint.h>
54		#include <limits.h>
55
56		#include "vdef.h"
57		#include "miniobj.h"
58		#include "vas.h"
59
60		#include "hpack/vhp.h"
61
62		#define VHT_STATIC_MAX 61
63
64		struct vht_static {
65		const char *name;
66		unsigned namelen;
67		const char *value;
68		unsigned valuelen;
69		};
70
71		static const struct vht_static static_table[] = {
72		#define HPS(NUM, NAME, VAL) \
73		{ NAME, sizeof NAME - 1, VAL, sizeof VAL - 1 },
74		#include "tbl/vhp_static.h"
75		};
76
77		#define TBLSIZE(tbl) ((tbl)->size + (tbl)->n * VHT_ENTRY_SIZE)
78		#define ENTRIES(buf, bufsize, n) \
79		(((struct vht_entry *)((uintptr_t)(buf) + bufsize)) - (n))
80		#define TBLENTRIES(tbl) ENTRIES((tbl)->buf, (tbl)->bufsize, (tbl)->n)
81		#define TBLENTRY(tbl, i) (&TBLENTRIES(tbl)[(i)])
82		#define ENTRYLEN(e) ((e)->namelen + (e)->valuelen)
83		#define ENTRYSIZE(e) (ENTRYLEN(e) + VHT_ENTRY_SIZE)
84
85		/****************************************************************************/
86		/* Internal interface */
87
88		static void
89	2205	vht_newentry(struct vht_table *tbl)
90		{
91		struct vht_entry *e;
92
93	2205	assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE);
94	2205	tbl->n++;
95	2205	e = TBLENTRY(tbl, 0);
96	2205	INIT_OBJ(e, VHT_ENTRY_MAGIC);
97	2205	e->offset = tbl->size;
98	2205	}
99
100		/* Trim elements from the end until the table size is less than max. */
101		static void
102	33075	vht_trim(struct vht_table *tbl, ssize_t max)
103		{
104		unsigned u, v;
105		int i;
106		struct vht_entry *e;
107
108	33075	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
109
110	33075	if (max < 0)
111	0	max = 0;
112	33075	if (TBLSIZE(tbl) <= max)
113	32088	return;
114
115	987	u = v = 0;
116	5145	for (i = tbl->n - 1; i >= 0; i--) {
117	4158	e = TBLENTRY(tbl, i);
118	4158	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
119	4158	if (TBLSIZE(tbl) - (u + v * VHT_ENTRY_SIZE) > max) {
120		/* Trim entry */
121	1008	assert(e->offset == u);
122	1008	u += ENTRYLEN(e);
123	1008	v++;
124	1008	FINI_OBJ(e);
125	1008	} else {
126		/* Fixup offset */
127	3150	assert(e->offset >= u);
128	3150	e->offset -= u;
129		}
130	4158	}
131	987	assert(v <= tbl->n);
132
133	987	vmemmove(tbl->buf, tbl->buf + u, tbl->size - u);
134	987	vmemmove(TBLENTRY(tbl, v), TBLENTRY(tbl, 0), (tbl->n - v) * sizeof *e);
135	987	tbl->n -= v;
136	987	tbl->size -= u;
137	33075	}
138
139		/* Append len bytes from buf to entry 0 name. Asserts if no space. */
140		static void
141	3276	vht_appendname(struct vht_table tbl, const char buf, size_t len)
142		{
143		struct vht_entry *e;
144
145	3276	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
146	3276	e = TBLENTRY(tbl, 0);
147	3276	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
148	3276	AZ(e->valuelen); /* Name needs to be set before value */
149	3276	assert(TBLSIZE(tbl) + len <= tbl->maxsize);
150	3276	assert(e->offset + e->namelen == tbl->size);
151	3276	vmemcpy(tbl->buf + tbl->size, buf, len);
152	3276	e->namelen += len;
153	3276	tbl->size += len;
154	3276	}
155
156		/* Append len bytes from buf to entry 0 value. Asserts if no space. */
157		static void
158	23730	vht_appendvalue(struct vht_table tbl, const char buf, size_t len)
159		{
160		struct vht_entry *e;
161
162	23730	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
163	23730	e = TBLENTRY(tbl, 0);
164	23730	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
165	23730	assert(TBLSIZE(tbl) + len <= tbl->maxsize);
166	23730	assert(e->offset + e->namelen + e->valuelen == tbl->size);
167	23730	vmemcpy(tbl->buf + tbl->size, buf, len);
168	23730	e->valuelen += len;
169	23730	tbl->size += len;
170	23730	}
171
172		/****************************************************************************/
173		/* Public interface */
174
175		void
176	2205	VHT_NewEntry(struct vht_table *tbl)
177		{
178
179	2205	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
180	2205	assert(tbl->maxsize <= tbl->protomax);
181	2205	vht_trim(tbl, tbl->maxsize - VHT_ENTRY_SIZE);
182	2205	if (tbl->maxsize - TBLSIZE(tbl) < VHT_ENTRY_SIZE) {
183		/* Maxsize less than one entry */
184	42	assert(tbl->maxsize < VHT_ENTRY_SIZE);
185	42	return;
186		}
187	2163	vht_newentry(tbl);
188	2205	}
189
190		int
191	1869	VHT_NewEntry_Indexed(struct vht_table *tbl, unsigned idx)
192		{
193		struct vht_entry e, e2;
194		unsigned l, l2, lentry, lname, u;
195		uint8_t tmp[48];
196
197		/* Referenced name insertion. This has to be done carefully
198		because the referenced name may be evicted as the result of the
199		insertion (RFC 7541 section 4.4). */
200
201	1869	assert(sizeof tmp >= VHT_ENTRY_SIZE);
202
203	1869	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
204	1869	assert(tbl->maxsize <= tbl->protomax);
205
206	1869	if (idx == 0)
207	0	return (-1);
208
209	1869	if (idx <= VHT_STATIC_MAX) {
210		/* Static table reference */
211	1764	VHT_NewEntry(tbl);
212	3528	VHT_AppendName(tbl, static_table[idx - 1].name,
213	1764	static_table[idx - 1].namelen);
214	1764	return (0);
215		}
216	105	idx -= VHT_STATIC_MAX + 1;
217
218	105	if (idx >= tbl->n)
219	0	return (-1); /* No such index */
220	105	assert(tbl->maxsize >= VHT_ENTRY_SIZE);
221
222	105	e = TBLENTRY(tbl, idx);
223	105	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
224
225		/* Count how many elements we can safely evict to make space
226		without evicting the referenced entry. */
227	105	l = 0;
228	105	u = 0;
229	147	while (tbl->n - 1 - u > idx &&
230	21	tbl->maxsize - TBLSIZE(tbl) + l < VHT_ENTRY_SIZE + e->namelen) {
231	21	e2 = TBLENTRY(tbl, tbl->n - 1 - u);
232	21	CHECK_OBJ_NOTNULL(e2, VHT_ENTRY_MAGIC);
233	21	l += ENTRYSIZE(e2);
234	21	u++;
235		}
236	105	vht_trim(tbl, TBLSIZE(tbl) - l);
237	105	e += u;
238	105	assert(e == TBLENTRY(tbl, idx));
239
240	105	if (tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + e->namelen) {
241		/* New entry with name fits */
242	42	vht_newentry(tbl);
243	42	idx++;
244	42	assert(e == TBLENTRY(tbl, idx));
245	42	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
246	42	vht_appendname(tbl, tbl->buf + e->offset, e->namelen);
247	42	return (0);
248		}
249
250		/* The tricky case: The referenced name will be evicted as a
251		result of the insertion. Move the referenced element data to
252		the end of the buffer through a local buffer. */
253
254		/* Remove the referenced element from the entry list */
255	63	assert(idx == tbl->n - 1);
256	63	assert(e->offset == 0);
257	63	lname = e->namelen;
258	63	lentry = ENTRYLEN(e);
259	63	FINI_OBJ(e);
260	63	vmemmove(TBLENTRY(tbl, 1), TBLENTRY(tbl, 0), (tbl->n - 1) * sizeof *e);
261	63	tbl->n--;
262
263		/* Shift the referenced element last using a temporary buffer. */
264	63	l = 0;
265	147	while (l < lentry) {
266	84	l2 = lentry - l;
267	84	if (l2 > sizeof tmp)
268	21	l2 = sizeof tmp;
269	84	vmemcpy(tmp, tbl->buf, l2);
270	84	vmemmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
271	84	vmemcpy(tbl->buf + tbl->size - l2, tmp, l2);
272	84	l += l2;
273		}
274	63	assert(l == lentry);
275	63	tbl->size -= lentry;
276
277		/* Fix up the existing element offsets */
278	126	for (u = 0; u < tbl->n; u++) {
279	63	e = TBLENTRY(tbl, u);
280	63	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
281	63	assert(e->offset >= lentry);
282	63	e->offset -= lentry;
283	63	assert(e->offset + ENTRYLEN(e) <= tbl->size);
284	63	}
285
286		/* Insert the new entry with the name now present at the end of
287		the buffer. */
288	63	assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + lname);
289	63	tbl->n++;
290	63	e = TBLENTRY(tbl, 0);
291	63	INIT_OBJ(e, VHT_ENTRY_MAGIC);
292	63	e->offset = tbl->size;
293	63	e->namelen = lname;
294	63	tbl->size += lname;
295
296	63	return (0);
297	1869	}
298
299		void
300	3234	VHT_AppendName(struct vht_table tbl, const char buf, ssize_t len)
301		{
302
303	3234	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
304	3234	assert(tbl->maxsize <= tbl->protomax);
305	3234	if (len == 0)
306	0	return;
307	3234	AN(buf);
308	3234	if (len < 0)
309	105	len = vstrlen(buf);
310	3234	vht_trim(tbl, tbl->maxsize - len);
311	3234	if (tbl->n == 0)
312		/* Max size exceeded */
313	0	return;
314	3234	vht_appendname(tbl, buf, len);
315	3234	}
316
317		void
318	23751	VHT_AppendValue(struct vht_table tbl, const char buf, ssize_t len)
319		{
320
321	23751	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
322	23751	assert(tbl->maxsize <= tbl->protomax);
323	23751	if (len == 0)
324	0	return;
325	23751	AN(buf);
326	23751	if (len < 0)
327	210	len = vstrlen(buf);
328	23751	vht_trim(tbl, tbl->maxsize - len);
329	23751	if (tbl->n == 0)
330		/* Max size exceeded */
331	21	return;
332	23730	vht_appendvalue(tbl, buf, len);
333	23751	}
334
335		int
336	84	VHT_SetMaxTableSize(struct vht_table *tbl, size_t maxsize)
337		{
338
339	84	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
340	84	assert(tbl->maxsize <= tbl->protomax);
341	84	if (maxsize > tbl->protomax)
342	21	return (-1);
343	63	vht_trim(tbl, maxsize);
344	63	assert(TBLSIZE(tbl) <= maxsize);
345	63	tbl->maxsize = maxsize;
346	63	return (0);
347	84	}
348
349		int
350	3717	VHT_SetProtoMax(struct vht_table *tbl, size_t protomax)
351		{
352		size_t bufsize;
353		char *buf;
354
355	3717	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
356	3717	assert(protomax <= UINT_MAX);
357	3717	assert(tbl->maxsize <= tbl->protomax);
358
359	3717	if (protomax == tbl->protomax)
360	0	return (0);
361
362	3717	if (tbl->maxsize > protomax)
363	21	tbl->maxsize = protomax;
364	3717	vht_trim(tbl, tbl->maxsize);
365	3717	assert(TBLSIZE(tbl) <= tbl->maxsize);
366
367	3717	bufsize = PRNDUP(protomax);
368	3717	if (bufsize == tbl->bufsize) {
369	0	tbl->protomax = protomax;
370	0	return (0);
371		}
372
373	3717	buf = malloc(bufsize);
374	3717	if (buf == NULL)
375	0	return (-1);
376
377	3717	if (tbl->buf != NULL) {
378	42	vmemcpy(buf, tbl->buf, tbl->size);
379	42	vmemcpy(ENTRIES(buf, bufsize, tbl->n), TBLENTRIES(tbl),
380		sizeof(struct vht_entry) * tbl->n);
381	42	free(tbl->buf);
382	42	}
383	3717	tbl->buf = buf;
384	3717	tbl->bufsize = bufsize;
385	3717	tbl->protomax = protomax;
386	3717	return (0);
387	3717	}
388
389		const char *
390	21819	VHT_LookupName(const struct vht_table tbl, unsigned idx, size_t plen)
391		{
392		struct vht_entry *e;
393
394	21819	AN(plen);
395	21819	*plen = 0;
396
397	21819	if (idx == 0) {
398	21	return (NULL);
399		}
400	21798	if (idx <= VHT_STATIC_MAX) {
401	15624	*plen = static_table[idx - 1].namelen;
402	15624	return (static_table[idx - 1].name);
403		}
404
405	6174	if (tbl == NULL)
406	0	return (NULL);
407	6174	CHECK_OBJ(tbl, VHT_TABLE_MAGIC);
408
409	6174	idx -= VHT_STATIC_MAX + 1;
410	6174	if (idx >= tbl->n)
411	0	return (NULL);
412
413	6174	e = TBLENTRY(tbl, idx);
414	6174	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
415	6174	assert(e->offset + e->namelen <= tbl->size);
416	6174	*plen = e->namelen;
417	6174	return (tbl->buf + e->offset);
418	21819	}
419
420		const char *
421	15036	VHT_LookupValue(const struct vht_table tbl, unsigned idx, size_t plen)
422		{
423		struct vht_entry *e;
424
425	15036	AN(plen);
426	15036	*plen = 0;
427
428	15036	if (idx == 0) {
429	21	return (NULL);
430		}
431	15015	if (idx <= VHT_STATIC_MAX) {
432	4410	*plen = static_table[idx - 1].valuelen;
433	4410	return (static_table[idx - 1].value);
434		}
435
436	10605	if (tbl == NULL)
437	0	return (NULL);
438	10605	CHECK_OBJ(tbl, VHT_TABLE_MAGIC);
439
440	10605	idx -= VHT_STATIC_MAX + 1;
441	10605	if (idx >= tbl->n)
442	0	return (NULL);
443
444	10605	e = TBLENTRY(tbl, idx);
445	10605	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
446	10605	assert(e->offset + e->namelen + e->valuelen <= tbl->size);
447	10605	*plen = e->valuelen;
448	10605	return (tbl->buf + e->offset + e->namelen);
449	15036	}
450
451		int
452	3675	VHT_Init(struct vht_table *tbl, size_t protomax)
453		{
454		int r;
455
456	3675	assert(sizeof (struct vht_entry) <= VHT_ENTRY_SIZE);
457
458	3675	AN(tbl);
459	3675	if (protomax > UINT_MAX)
460	0	return (-1);
461	3675	INIT_OBJ(tbl, VHT_TABLE_MAGIC);
462	3675	r = VHT_SetProtoMax(tbl, protomax);
463	3675	if (r) {
464	0	FINI_OBJ(tbl);
465	0	return (r);
466		}
467	3675	tbl->maxsize = tbl->protomax;
468	3675	return (0);
469	3675	}
470
471		void
472	3654	VHT_Fini(struct vht_table *tbl)
473		{
474
475	3654	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
476	3654	free(tbl->buf);
477	3654	memset(tbl, 0, sizeof *tbl);
478	3654	}
479
480		/****************************************************************************/
481		/* Internal interface */
482
483		#ifdef TABLE_TEST_DRIVER
484
485		#define VHT_DYNAMIC (VHT_STATIC_MAX + 1)
486
487		static int verbose = 0;
488
489		static int
490	462	vht_matchtable(struct vht_table *tbl, ...)
491		{
492		va_list ap;
493		unsigned u;
494		int r;
495		const char a, b;
496		const struct vht_entry *e;
497
498	462	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
499