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);

        memmove(tbl->buf, tbl->buf + u, tbl->size - u);
        memmove(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);
        memcpy(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);
        memcpy(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);
        memmove(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;
                memcpy(tmp, tbl->buf, l2);
                memmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
                memcpy(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 = strlen(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 = strlen(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) {
                memcpy(buf, tbl->buf, tbl->size);
                memcpy(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_NOTNULL(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_NOTNULL(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 != strlen(a) ||
                            strncmp(a, tbl->buf + e->offset, e->namelen))
                                r = -1;
                        if (e->valuelen != strlen(b) ||
                            strncmp(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 == strlen(":authority"));
        AZ(strncmp(p, ":authority", strlen(":authority")));
        p = VHT_LookupValue(NULL, 1, &l);
        AN(p);
        AZ(l);

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

        /* 61: 'www-authenticate' -> '' */
        p = VHT_LookupName(NULL, 61, &l);
        assert(l == strlen("www-authenticate"));
        AZ(strncmp(p, "www-authenticate", strlen("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, strlen(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 && !strcmp(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 */

		varnish-cache/bin/varnishd/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	105	vht_newentry(struct vht_table *tbl)
90		{
91		struct vht_entry *e;
92
93	105	assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE);
94	105	tbl->n++;
95	105	e = TBLENTRY(tbl, 0);
96	105	INIT_OBJ(e, VHT_ENTRY_MAGIC);
97	105	e->offset = tbl->size;
98	105	}
99
100		/* Trim elements from the end until the table size is less than max. */
101		static void
102	1573	vht_trim(struct vht_table *tbl, ssize_t max)
103		{
104		unsigned u, v;
105		int i;
106		struct vht_entry *e;
107
108	1573	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
109
110	1573	if (max < 0)
111	0	max = 0;
112	1573	if (TBLSIZE(tbl) <= max)
113	1526	return;
114
115	47	u = v = 0;
116	245	for (i = tbl->n - 1; i >= 0; i--) {
117	198	e = TBLENTRY(tbl, i);
118	198	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
119	198	if (TBLSIZE(tbl) - (u + v * VHT_ENTRY_SIZE) > max) {
120		/* Trim entry */
121	48	assert(e->offset == u);
122	48	u += ENTRYLEN(e);
123	48	v++;
124	48	FINI_OBJ(e);
125	48	} else {
126		/* Fixup offset */
127	150	assert(e->offset >= u);
128	150	e->offset -= u;
129		}
130	198	}
131	47	assert(v <= tbl->n);
132
133	47	memmove(tbl->buf, tbl->buf + u, tbl->size - u);
134	47	memmove(TBLENTRY(tbl, v), TBLENTRY(tbl, 0), (tbl->n - v) * sizeof *e);
135	47	tbl->n -= v;
136	47	tbl->size -= u;
137	1573	}
138
139		/* Append len bytes from buf to entry 0 name. Asserts if no space. */
140		static void
141	156	vht_appendname(struct vht_table tbl, const char buf, size_t len)
142		{
143		struct vht_entry *e;
144
145	156	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
146	156	e = TBLENTRY(tbl, 0);
147	156	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
148	156	AZ(e->valuelen); /* Name needs to be set before value */
149	156	assert(TBLSIZE(tbl) + len <= tbl->maxsize);
150	156	assert(e->offset + e->namelen == tbl->size);
151	156	memcpy(tbl->buf + tbl->size, buf, len);
152	156	e->namelen += len;
153	156	tbl->size += len;
154	156	}
155
156		/* Append len bytes from buf to entry 0 value. Asserts if no space. */
157		static void
158	1130	vht_appendvalue(struct vht_table tbl, const char buf, size_t len)
159		{
160		struct vht_entry *e;
161
162	1130	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
163	1130	e = TBLENTRY(tbl, 0);
164	1130	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
165	1130	assert(TBLSIZE(tbl) + len <= tbl->maxsize);
166	1130	assert(e->offset + e->namelen + e->valuelen == tbl->size);
167	1130	memcpy(tbl->buf + tbl->size, buf, len);
168	1130	e->valuelen += len;
169	1130	tbl->size += len;
170	1130	}
171
172		/****************************************************************************/
173		/* Public interface */
174
175		void
176	105	VHT_NewEntry(struct vht_table *tbl)
177		{
178
179	105	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
180	105	assert(tbl->maxsize <= tbl->protomax);
181	105	vht_trim(tbl, tbl->maxsize - VHT_ENTRY_SIZE);
182	105	if (tbl->maxsize - TBLSIZE(tbl) < VHT_ENTRY_SIZE) {
183		/* Maxsize less than one entry */
184	2	assert(tbl->maxsize < VHT_ENTRY_SIZE);
185	2	return;
186		}
187	103	vht_newentry(tbl);
188	105	}
189
190		int
191	89	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	89	assert(sizeof tmp >= VHT_ENTRY_SIZE);
202
203	89	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
204	89	assert(tbl->maxsize <= tbl->protomax);
205
206	89	if (idx == 0)
207	0	return (-1);
208
209	89	if (idx <= VHT_STATIC_MAX) {
210		/* Static table reference */
211	84	VHT_NewEntry(tbl);
212	168	VHT_AppendName(tbl, static_table[idx - 1].name,
213	84	static_table[idx - 1].namelen);
214	84	return (0);
215		}
216	5	idx -= VHT_STATIC_MAX + 1;
217
218	5	if (idx >= tbl->n)
219	0	return (-1); /* No such index */
220	5	assert(tbl->maxsize >= VHT_ENTRY_SIZE);
221
222	5	e = TBLENTRY(tbl, idx);
223	5	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	5	l = 0;
228	5	u = 0;
229	7	while (tbl->n - 1 - u > idx &&
230	1	tbl->maxsize - TBLSIZE(tbl) + l < VHT_ENTRY_SIZE + e->namelen) {
231	1	e2 = TBLENTRY(tbl, tbl->n - 1 - u);
232	1	CHECK_OBJ_NOTNULL(e2, VHT_ENTRY_MAGIC);
233	1	l += ENTRYSIZE(e2);
234	1	u++;
235		}
236	5	vht_trim(tbl, TBLSIZE(tbl) - l);
237	5	e += u;
238	5	assert(e == TBLENTRY(tbl, idx));
239
240	5	if (tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + e->namelen) {
241		/* New entry with name fits */
242	2	vht_newentry(tbl);
243	2	idx++;
244	2	assert(e == TBLENTRY(tbl, idx));
245	2	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
246	2	vht_appendname(tbl, tbl->buf + e->offset, e->namelen);
247	2	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	3	assert(idx == tbl->n - 1);
256	3	assert(e->offset == 0);
257	3	lname = e->namelen;
258	3	lentry = ENTRYLEN(e);
259	3	FINI_OBJ(e);
260	3	memmove(TBLENTRY(tbl, 1), TBLENTRY(tbl, 0), (tbl->n - 1) * sizeof *e);
261	3	tbl->n--;
262
263		/* Shift the referenced element last using a temporary buffer. */
264	3	l = 0;
265	7	while (l < lentry) {
266	4	l2 = lentry - l;
267	4	if (l2 > sizeof tmp)
268	1	l2 = sizeof tmp;
269	4	memcpy(tmp, tbl->buf, l2);
270	4	memmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
271	4	memcpy(tbl->buf + tbl->size - l2, tmp, l2);
272	4	l += l2;
273		}
274	3	assert(l == lentry);
275	3	tbl->size -= lentry;
276
277		/* Fix up the existing element offsets */
278	6	for (u = 0; u < tbl->n; u++) {
279	3	e = TBLENTRY(tbl, u);
280	3	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
281	3	assert(e->offset >= lentry);
282	3	e->offset -= lentry;
283	3	assert(e->offset + ENTRYLEN(e) <= tbl->size);
284	3	}
285
286		/* Insert the new entry with the name now present at the end of
287		the buffer. */
288	3	assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + lname);
289	3	tbl->n++;
290	3	e = TBLENTRY(tbl, 0);
291	3	INIT_OBJ(e, VHT_ENTRY_MAGIC);
292	3	e->offset = tbl->size;
293	3	e->namelen = lname;
294	3	tbl->size += lname;
295
296	3	return (0);
297	89	}
298
299		void
300	154	VHT_AppendName(struct vht_table tbl, const char buf, ssize_t len)
301		{
302
303	154	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
304	154	assert(tbl->maxsize <= tbl->protomax);
305	154	if (len == 0)
306	0	return;
307	154	AN(buf);
308	154	if (len < 0)
309	5	len = strlen(buf);
310	154	vht_trim(tbl, tbl->maxsize - len);
311	154	if (tbl->n == 0)
312		/* Max size exceeded */
313	0	return;
314	154	vht_appendname(tbl, buf, len);
315	154	}
316
317		void
318	1131	VHT_AppendValue(struct vht_table tbl, const char buf, ssize_t len)
319		{
320
321	1131	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
322	1131	assert(tbl->maxsize <= tbl->protomax);
323	1131	if (len == 0)
324	0	return;
325	1131	AN(buf);
326	1131	if (len < 0)
327	10	len = strlen(buf);
328	1131	vht_trim(tbl, tbl->maxsize - len);
329	1131	if (tbl->n == 0)
330		/* Max size exceeded */
331	1	return;
332	1130	vht_appendvalue(tbl, buf, len);
333	1131	}
334
335		int
336	4	VHT_SetMaxTableSize(struct vht_table *tbl, size_t maxsize)
337		{
338
339	4	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
340	4	assert(tbl->maxsize <= tbl->protomax);
341	4	if (maxsize > tbl->protomax)
342	1	return (-1);
343	3	vht_trim(tbl, maxsize);
344	3	assert(TBLSIZE(tbl) <= maxsize);
345	3	tbl->maxsize = maxsize;
346	3	return (0);
347	4	}
348
349		int
350	175	VHT_SetProtoMax(struct vht_table *tbl, size_t protomax)
351		{
352		size_t bufsize;
353		char *buf;
354
355	175	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
356	175	assert(protomax <= UINT_MAX);
357	175	assert(tbl->maxsize <= tbl->protomax);
358
359	175	if (protomax == tbl->protomax)
360	0	return (0);
361
362	175	if (tbl->maxsize > protomax)
363	1	tbl->maxsize = protomax;
364	175	vht_trim(tbl, tbl->maxsize);
365	175	assert(TBLSIZE(tbl) <= tbl->maxsize);
366
367	175	bufsize = PRNDUP(protomax);
368	175	if (bufsize == tbl->bufsize) {
369	0	tbl->protomax = protomax;
370	0	return (0);
371		}
372
373	175	buf = malloc(bufsize);
374	175	if (buf == NULL)
375	0	return (-1);
376
377	175	if (tbl->buf != NULL) {
378	2	memcpy(buf, tbl->buf, tbl->size);
379	4	memcpy(ENTRIES(buf, bufsize, tbl->n), TBLENTRIES(tbl),
380	2	sizeof (struct vht_entry) * tbl->n);
381	2	free(tbl->buf);
382	2	}
383	175	tbl->buf = buf;
384	175	tbl->bufsize = bufsize;
385	175	tbl->protomax = protomax;
386	175	return (0);
387	175	}
388
389		const char *
390	1039	VHT_LookupName(const struct vht_table tbl, unsigned idx, size_t plen)
391		{
392		struct vht_entry *e;
393
394	1039	AN(plen);
395	1039	*plen = 0;
396
397	1039	if (idx == 0) {
398	1	return (NULL);
399		}
400	1038	if (idx <= VHT_STATIC_MAX) {
401	744	*plen = static_table[idx - 1].namelen;
402	744	return (static_table[idx - 1].name);
403		}
404
405	294	if (tbl == NULL)
406	0	return (NULL);
407	294	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
408
409	294	idx -= VHT_STATIC_MAX + 1;
410	294	if (idx >= tbl->n)
411	0	return (NULL);
412
413	294	e = TBLENTRY(tbl, idx);
414	294	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
415	294	assert(e->offset + e->namelen <= tbl->size);
416	294	*plen = e->namelen;
417	294	return (tbl->buf + e->offset);
418	1039	}
419
420		const char *
421	716	VHT_LookupValue(const struct vht_table tbl, unsigned idx, size_t plen)
422		{
423		struct vht_entry *e;
424
425	716	AN(plen);
426	716	*plen = 0;
427
428	716	if (idx == 0) {
429	1	return (NULL);
430		}
431	715	if (idx <= VHT_STATIC_MAX) {
432	210	*plen = static_table[idx - 1].valuelen;
433	210	return (static_table[idx - 1].value);
434		}
435
436	505	if (tbl == NULL)
437	0	return (NULL);
438	505	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
439
440	505	idx -= VHT_STATIC_MAX + 1;
441	505	if (idx >= tbl->n)
442	0	return (NULL);
443
444	505	e = TBLENTRY(tbl, idx);
445	505	CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
446	505	assert(e->offset + e->namelen + e->valuelen <= tbl->size);
447	505	*plen = e->valuelen;
448	505	return (tbl->buf + e->offset + e->namelen);
449	716	}
450
451		int
452	173	VHT_Init(struct vht_table *tbl, size_t protomax)
453		{
454		int r;
455
456	173	assert(sizeof (struct vht_entry) <= VHT_ENTRY_SIZE);
457
458	173	AN(tbl);
459	173	if (protomax > UINT_MAX)
460	0	return (-1);
461	173	INIT_OBJ(tbl, VHT_TABLE_MAGIC);
462	173	r = VHT_SetProtoMax(tbl, protomax);
463	173	if (r) {
464	0	FINI_OBJ(tbl);
465	0	return (r);
466		}
467	173	tbl->maxsize = tbl->protomax;
468	173	return (0);
469	173	}
470
471		void
472	168	VHT_Fini(struct vht_table *tbl)
473		{
474
475	168	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
476	168	free(tbl->buf);
477	168	memset(tbl, 0, sizeof *tbl);
478	168	}
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	22	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	22	CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
499