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 2625
vht_newentry(struct vht_table *tbl)
90
{
91
        struct vht_entry *e;
92
93 2625
        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE);
94 2625
        tbl->n++;
95 2625
        e = TBLENTRY(tbl, 0);
96 2625
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
97 2625
        e->offset = tbl->size;
98 2625
}
99
100
/* Trim elements from the end until the table size is less than max. */
101
static void
102 38925
vht_trim(struct vht_table *tbl, ssize_t max)
103
{
104
        unsigned u, v;
105
        int i;
106
        struct vht_entry *e;
107
108 38925
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
109
110 38925
        if (max < 0)
111 0
                max = 0;
112 38925
        if (TBLSIZE(tbl) <= max)
113 37750
                return;
114
115 1175
        u = v = 0;
116 6125
        for (i = tbl->n - 1; i >= 0; i--) {
117 4950
                e = TBLENTRY(tbl, i);
118 4950
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
119 4950
                if (TBLSIZE(tbl) - (u + v * VHT_ENTRY_SIZE) > max) {
120
                        /* Trim entry */
121 1200
                        assert(e->offset == u);
122 1200
                        u += ENTRYLEN(e);
123 1200
                        v++;
124 1200
                        FINI_OBJ(e);
125 1200
                } else {
126
                        /* Fixup offset */
127 3750
                        assert(e->offset >= u);
128 3750
                        e->offset -= u;
129
                }
130 4950
        }
131 1175
        assert(v <= tbl->n);
132
133 1175
        memmove(tbl->buf, tbl->buf + u, tbl->size - u);
134 1175
        memmove(TBLENTRY(tbl, v), TBLENTRY(tbl, 0), (tbl->n - v) * sizeof *e);
135 1175
        tbl->n -= v;
136 1175
        tbl->size -= u;
137 38925
}
138
139
/* Append len bytes from buf to entry 0 name. Asserts if no space. */
140
static void
141 3900
vht_appendname(struct vht_table *tbl, const char *buf, size_t len)
142
{
143
        struct vht_entry *e;
144
145 3900
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
146 3900
        e = TBLENTRY(tbl, 0);
147 3900
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
148 3900
        AZ(e->valuelen);        /* Name needs to be set before value */
149 3900
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
150 3900
        assert(e->offset + e->namelen == tbl->size);
151 3900
        memcpy(tbl->buf + tbl->size, buf, len);
152 3900
        e->namelen += len;
153 3900
        tbl->size += len;
154 3900
}
155
156
/* Append len bytes from buf to entry 0 value. Asserts if no space. */
157
static void
158 28250
vht_appendvalue(struct vht_table *tbl, const char *buf, size_t len)
159
{
160
        struct vht_entry *e;
161
162 28250
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
163 28250
        e = TBLENTRY(tbl, 0);
164 28250
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
165 28250
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
166 28250
        assert(e->offset + e->namelen + e->valuelen == tbl->size);
167 28250
        memcpy(tbl->buf + tbl->size, buf, len);
168 28250
        e->valuelen += len;
169 28250
        tbl->size += len;
170 28250
}
171
172
/****************************************************************************/
173
/* Public interface */
174
175
void
176 2625
VHT_NewEntry(struct vht_table *tbl)
177
{
178
179 2625
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
180 2625
        assert(tbl->maxsize <= tbl->protomax);
181 2625
        vht_trim(tbl, tbl->maxsize - VHT_ENTRY_SIZE);
182 2625
        if (tbl->maxsize - TBLSIZE(tbl) < VHT_ENTRY_SIZE) {
183
                /* Maxsize less than one entry */
184 50
                assert(tbl->maxsize < VHT_ENTRY_SIZE);
185 50
                return;
186
        }
187 2575
        vht_newentry(tbl);
188 2625
}
189
190
int
191 2225
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 2225
        assert(sizeof tmp >= VHT_ENTRY_SIZE);
202
203 2225
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
204 2225
        assert(tbl->maxsize <= tbl->protomax);
205
206 2225
        if (idx == 0)
207 0
                return (-1);
208
209 2225
        if (idx <= VHT_STATIC_MAX) {
210
                /* Static table reference */
211 2100
                VHT_NewEntry(tbl);
212 4200
                VHT_AppendName(tbl, static_table[idx - 1].name,
213 2100
                    static_table[idx - 1].namelen);
214 2100
                return (0);
215
        }
216 125
        idx -= VHT_STATIC_MAX + 1;
217
218 125
        if (idx >= tbl->n)
219 0
                return (-1);    /* No such index */
220 125
        assert(tbl->maxsize >= VHT_ENTRY_SIZE);
221
222 125
        e = TBLENTRY(tbl, idx);
223 125
        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 125
        l = 0;
228 125
        u = 0;
229 175
        while (tbl->n - 1 - u > idx &&
230 25
            tbl->maxsize - TBLSIZE(tbl) + l < VHT_ENTRY_SIZE + e->namelen) {
231 25
                e2 = TBLENTRY(tbl, tbl->n - 1 - u);
232 25
                CHECK_OBJ_NOTNULL(e2, VHT_ENTRY_MAGIC);
233 25
                l += ENTRYSIZE(e2);
234 25
                u++;
235
        }
236 125
        vht_trim(tbl, TBLSIZE(tbl) - l);
237 125
        e += u;
238 125
        assert(e == TBLENTRY(tbl, idx));
239
240 125
        if (tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + e->namelen) {
241
                /* New entry with name fits */
242 50
                vht_newentry(tbl);
243 50
                idx++;
244 50
                assert(e == TBLENTRY(tbl, idx));
245 50
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
246 50
                vht_appendname(tbl, tbl->buf + e->offset, e->namelen);
247 50
                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 75
        assert(idx == tbl->n - 1);
256 75
        assert(e->offset == 0);
257 75
        lname = e->namelen;
258 75
        lentry = ENTRYLEN(e);
259 75
        FINI_OBJ(e);
260 75
        memmove(TBLENTRY(tbl, 1), TBLENTRY(tbl, 0), (tbl->n - 1) * sizeof *e);
261 75
        tbl->n--;
262
263
        /* Shift the referenced element last using a temporary buffer. */
264 75
        l = 0;
265 175
        while (l < lentry) {
266 100
                l2 = lentry - l;
267 100
                if (l2 > sizeof tmp)
268 25
                        l2 = sizeof tmp;
269 100
                memcpy(tmp, tbl->buf, l2);
270 100
                memmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
271 100
                memcpy(tbl->buf + tbl->size - l2, tmp, l2);
272 100
                l += l2;
273
        }
274 75
        assert(l == lentry);
275 75
        tbl->size -= lentry;
276
277
        /* Fix up the existing element offsets */
278 150
        for (u = 0; u < tbl->n; u++) {
279 75
                e = TBLENTRY(tbl, u);
280 75
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
281 75
                assert(e->offset >= lentry);
282 75
                e->offset -= lentry;
283 75
                assert(e->offset + ENTRYLEN(e) <= tbl->size);
284 75
        }
285
286
        /* Insert the new entry with the name now present at the end of
287
           the buffer. */
288 75
        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + lname);
289 75
        tbl->n++;
290 75
        e = TBLENTRY(tbl, 0);
291 75
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
292 75
        e->offset = tbl->size;
293 75
        e->namelen = lname;
294 75
        tbl->size += lname;
295
296 75
        return (0);
297 2225
}
298
299
void
300 3850
VHT_AppendName(struct vht_table *tbl, const char *buf, ssize_t len)
301
{
302
303 3850
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
304 3850
        assert(tbl->maxsize <= tbl->protomax);
305 3850
        if (len == 0)
306 0
                return;
307 3850
        AN(buf);
308 3850
        if (len < 0)
309 125
                len = strlen(buf);
310 3850
        vht_trim(tbl, tbl->maxsize - len);
311 3850
        if (tbl->n == 0)
312
                /* Max size exceeded */
313 0
                return;
314 3850
        vht_appendname(tbl, buf, len);
315 3850
}
316
317
void
318 28275
VHT_AppendValue(struct vht_table *tbl, const char *buf, ssize_t len)
319
{
320
321 28275
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
322 28275
        assert(tbl->maxsize <= tbl->protomax);
323 28275
        if (len == 0)
324 0
                return;
325 28275
        AN(buf);
326 28275
        if (len < 0)
327 250
                len = strlen(buf);
328 28275
        vht_trim(tbl, tbl->maxsize - len);
329 28275
        if (tbl->n == 0)
330
                /* Max size exceeded */
331 25
                return;
332 28250
        vht_appendvalue(tbl, buf, len);
333 28275
}
334
335
int
336 100
VHT_SetMaxTableSize(struct vht_table *tbl, size_t maxsize)
337
{
338
339 100
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
340 100
        assert(tbl->maxsize <= tbl->protomax);
341 100
        if (maxsize > tbl->protomax)
342 25
                return (-1);
343 75
        vht_trim(tbl, maxsize);
344 75
        assert(TBLSIZE(tbl) <= maxsize);
345 75
        tbl->maxsize = maxsize;
346 75
        return (0);
347 100
}
348
349
int
350 3975
VHT_SetProtoMax(struct vht_table *tbl, size_t protomax)
351
{
352
        size_t bufsize;
353
        char *buf;
354
355 3975
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
356 3975
        assert(protomax <= UINT_MAX);
357 3975
        assert(tbl->maxsize <= tbl->protomax);
358
359 3975
        if (protomax == tbl->protomax)
360 0
                return (0);
361
362 3975
        if (tbl->maxsize > protomax)
363 25
                tbl->maxsize = protomax;
364 3975
        vht_trim(tbl, tbl->maxsize);
365 3975
        assert(TBLSIZE(tbl) <= tbl->maxsize);
366
367 3975
        bufsize = PRNDUP(protomax);
368 3975
        if (bufsize == tbl->bufsize) {
369 0
                tbl->protomax = protomax;
370 0
                return (0);
371
        }
372
373 3975
        buf = malloc(bufsize);
374 3975
        if (buf == NULL)
375 0
                return (-1);
376
377 3975
        if (tbl->buf != NULL) {
378 50
                memcpy(buf, tbl->buf, tbl->size);
379 100
                memcpy(ENTRIES(buf, bufsize, tbl->n), TBLENTRIES(tbl),
380 50
                    sizeof (struct vht_entry) * tbl->n);
381 50
                free(tbl->buf);
382 50
        }
383 3975
        tbl->buf = buf;
384 3975
        tbl->bufsize = bufsize;
385 3975
        tbl->protomax = protomax;
386 3975
        return (0);
387 3975
}
388
389
const char *
390 25975
VHT_LookupName(const struct vht_table *tbl, unsigned idx, size_t *plen)
391
{
392
        struct vht_entry *e;
393
394 25975
        AN(plen);
395 25975
        *plen = 0;
396
397 25975
        if (idx == 0) {
398 25
                return (NULL);
399
        }
400 25950
        if (idx <= VHT_STATIC_MAX) {
401 18600
                *plen = static_table[idx - 1].namelen;
402 18600
                return (static_table[idx - 1].name);
403
        }
404
405 7350
        if (tbl == NULL)
406 0
                return (NULL);
407 7350
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
408
409 7350
        idx -= VHT_STATIC_MAX + 1;
410 7350
        if (idx >= tbl->n)
411 0
                return (NULL);
412
413 7350
        e = TBLENTRY(tbl, idx);
414 7350
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
415 7350
        assert(e->offset + e->namelen <= tbl->size);
416 7350
        *plen = e->namelen;
417 7350
        return (tbl->buf + e->offset);
418 25975
}
419
420
const char *
421 17900
VHT_LookupValue(const struct vht_table *tbl, unsigned idx, size_t *plen)
422
{
423
        struct vht_entry *e;
424
425 17900
        AN(plen);
426 17900
        *plen = 0;
427
428 17900
        if (idx == 0) {
429 25
                return (NULL);
430
        }
431 17875
        if (idx <= VHT_STATIC_MAX) {
432 5250
                *plen = static_table[idx - 1].valuelen;
433 5250
                return (static_table[idx - 1].value);
434
        }
435
436 12625
        if (tbl == NULL)
437 0
                return (NULL);
438 12625
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
439
440 12625
        idx -= VHT_STATIC_MAX + 1;
441 12625
        if (idx >= tbl->n)
442 0
                return (NULL);
443
444 12625
        e = TBLENTRY(tbl, idx);
445 12625
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
446 12625
        assert(e->offset + e->namelen + e->valuelen <= tbl->size);
447 12625
        *plen = e->valuelen;
448 12625
        return (tbl->buf + e->offset + e->namelen);
449 17900
}
450
451
int
452 3925
VHT_Init(struct vht_table *tbl, size_t protomax)
453
{
454
        int r;
455
456 3925
        assert(sizeof (struct vht_entry) <= VHT_ENTRY_SIZE);
457
458 3925
        AN(tbl);
459 3925
        if (protomax > UINT_MAX)
460 0
                return (-1);
461 3925
        INIT_OBJ(tbl, VHT_TABLE_MAGIC);
462 3925
        r = VHT_SetProtoMax(tbl, protomax);
463 3925
        if (r) {
464 0
                FINI_OBJ(tbl);
465 0
                return (r);
466
        }
467 3925
        tbl->maxsize = tbl->protomax;
468 3925
        return (0);
469 3925
}
470
471
void
472 3714
VHT_Fini(struct vht_table *tbl)
473
{
474
475 3714
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
476 3714
        free(tbl->buf);
477 3714
        memset(tbl, 0, sizeof *tbl);
478 3714
}
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 550
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 550
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
499
500 550
        va_start(ap, tbl);
501 550
        r = 0;
502 1275
        for (u = 0; u < tbl->n; u++) {
503 725
                a = NULL;
504 725
                b = NULL;
505 725
                if (!r) {
506 725
                        a = va_arg(ap, const char *);
507 725
                        if (a == NULL) {
508 0
                                printf("Too many elements in table\n");
509 0
                                r = -1;
510 0
                        } else {
511 725
                                b = va_arg(ap, const char *);
512 725
                                AN(b);
513
                        }
514 725
                }
515
516 725
                e = TBLENTRY(tbl, u);
517 725
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
518
519 725
                if (a) {
520 725
                        AN(b);
521 725
                        if (e->namelen != strlen(a) ||
522 725
                            strncmp(a, tbl->buf + e->offset, e->namelen))
523 0
                                r = -1;
524 725
                        if (e->valuelen != strlen(b) ||
525 1450
                            strncmp(b, tbl->buf + e->offset + e->namelen,
526 725
                             e->valuelen))
527 0
                                r = -1;
528 725
                }
529
530 725
                if (verbose || r)
531 0
                        printf("%2u: @%03u (\"%.*s\", \"%.*s\")",
532 0
                            u, e->offset, (int)e->namelen, tbl->buf + e->offset,
533 0
                            (int)e->valuelen, tbl->buf + e->offset +e->namelen);
534
535 725
                if (a && (verbose || r)) {
536 0
                        AN(b);
537 0
                        printf(" %s (\"%s\", \"%s\")", (r ? "!=" : "=="), a, b);
538 0
                }
539
540 725
                if (verbose || r)
541 0
                        printf("\n");
542 725
        }
543 550
        if (!r) {
544 550
                a = va_arg(ap, const char *);
545 550
                if (a != NULL) {
546 0
                        printf("Missing elements in table\n");
547 0
                        r = -1;
548 0
                }
549 550
        }
550 550
        va_end(ap);
551
552 550
        if (verbose || r)
553 0
                printf("n=%d, size=%u, tblsz=%u, max=%u, pmax=%u, bufsz=%u\n",
554 0
                    tbl->n, tbl->size, TBLSIZE(tbl), tbl->maxsize,
555 0
                    tbl->protomax, tbl->bufsize);
556
557 550
        return (r);
558
}
559
560
static void
561 25
test_1(void)
562
{
563
        /* Static table */
564
565
        const char *p;
566
        size_t l;
567
568 25
        if (verbose)
569 0
                printf("Test 1:\n");
570
571
        /* 1: ':authority' -> '' */
572 25
        p = VHT_LookupName(NULL, 1, &l);
573 25
        assert(l == strlen(":authority"));
574 25
        AZ(strncmp(p, ":authority", strlen(":authority")));
575 25
        p = VHT_LookupValue(NULL, 1, &l);
576 25
        AN(p);
577 25
        AZ(l);
578
579
        /* 5: ':path' -> '/index.html' */
580 25
        p = VHT_LookupValue(NULL, 5, &l);
581 25
        assert(l == strlen("/index.html"));
582 25
        AZ(strncmp(p, "/index.html", strlen("/index.html")));
583
584
        /* 61: 'www-authenticate' -> '' */
585 25
        p = VHT_LookupName(NULL, 61, &l);
586 25
        assert(l == strlen("www-authenticate"));
587 25
        AZ(strncmp(p, "www-authenticate", strlen("www-authenticate")));
588 25
        p = VHT_LookupValue(NULL, 61, &l);
589 25
        AN(p);
590 25
        AZ(l);
591
592
        /* Test zero index */
593 25
        AZ(VHT_LookupName(NULL, 0, &l));
594 25
        AZ(l);
595 25
        AZ(VHT_LookupValue(NULL, 0, &l));
596 25
        AZ(l);
597
598 25
        printf("Test 1 finished successfully\n");
599 25
        if (verbose)
600 0
                printf("\n");
601 25
}
602
603
static void
604 25
test_2(void)
605
{
606
        /* Test filling and overflow */
607
608
        struct vht_table tbl[1];
609
610 25
        if (verbose)
611 0
                printf("Test 2:\n");
612
613 25
        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE + 10));
614
615 25
        VHT_NewEntry(tbl);
616 25
        VHT_AppendName(tbl, "12345", -1);
617 25
        VHT_AppendValue(tbl, "abcde", -1);
618 25
        assert(TBLSIZE(tbl) == VHT_ENTRY_SIZE + 10);
619
        /* 0: '12345' -> 'abcde' */
620 25
        AZ(vht_matchtable(tbl, "12345", "abcde", NULL));
621
622 25
        VHT_AppendValue(tbl, "f", -1);
623 25
        AZ(vht_matchtable(tbl, NULL));
624
625 25
        VHT_NewEntry(tbl);
626 25
        AZ(vht_matchtable(tbl, "", "", NULL));
627
628 25
        VHT_Fini(tbl);
629 25
        AZ(tbl->buf);
630
631 25
        printf("Test 2 finished successfully\n");
632 25
        if (verbose)
633 0
                printf("\n");
634 25
}
635
636
static void
637 25
test_3(void)
638
{
639
        /* Test change in proto max size and dynamic max size */
640
641
        struct vht_table tbl[1];
642
643 25
        if (verbose)
644 0
                printf("Test 3:\n");
645
646 25
        AZ(VHT_Init(tbl, 4096));
647
648 25
        VHT_NewEntry(tbl);
649 25
        VHT_AppendName(tbl, "a", -1);
650 25
        VHT_AppendValue(tbl, "12345", -1);
651 25
        VHT_NewEntry(tbl);
652 25
        VHT_AppendName(tbl, "b", -1);
653 25
        VHT_AppendValue(tbl, "67890", -1);
654 25
        VHT_NewEntry(tbl);
655 25
        VHT_AppendName(tbl, "c", -1);
656 25
        VHT_AppendValue(tbl, "abcde", -1);
657 25
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", "a", "12345", NULL));
658
659
        /* Buffer reallocation */
660 25
        AZ(VHT_SetProtoMax(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
661 25
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", NULL));
662
663
        /* Increase table size beyond protomax */
664 25
        assert(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 + 1) == -1);
665
666
        /* Decrease by one */
667 25
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 - 1));
668 25
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));
669
670
        /* Increase by one back to protomax */
671 25
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
672 25
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));
673
674
        /* Add entry */
675 25
        VHT_NewEntry(tbl);
676 25
        VHT_AppendName(tbl, "d", -1);
677 25
        VHT_AppendValue(tbl, "ABCDE", -1);
678 25
        AZ(vht_matchtable(tbl, "d", "ABCDE", "c", "abcde", NULL));
679
680
        /* Set to zero */
681 25
        AZ(VHT_SetMaxTableSize(tbl, 0));
682 25
        AZ(vht_matchtable(tbl, NULL));
683 25
        VHT_NewEntry(tbl);
684 25
        AZ(vht_matchtable(tbl, NULL));
685
686
        /* Set protomax to zero */
687 25
        AZ(VHT_SetProtoMax(tbl, 0));
688 25
        AZ(vht_matchtable(tbl, NULL));
689 25
        VHT_NewEntry(tbl);
690 25
        AZ(vht_matchtable(tbl, NULL));
691
692 25
        VHT_Fini(tbl);
693
694 25
        printf("Test 3 finished successfully\n");
695 25
        if (verbose)
696 0
                printf("\n");
697 25
}
698
699
static void
700 25
test_4(void)
701
{
702
        /* Referenced name new entry */
703
704
        struct vht_table tbl[1];
705
        static const char longname[] =
706
            "1234567890"
707
            "1234567890"
708
            "1234567890"
709
            "1234567890"
710
            "1234567890"
711
            "1";        /* 51 bytes + VHT_ENTRY_SIZE == 83 */
712
713 25
        if (verbose)
714 0
                printf("Test 4:\n");
715
716 25
        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE * 2 + 10 * 2)); /* 84 bytes */
717
718
        /* New entry indexed from static table */
719 25
        AZ(VHT_NewEntry_Indexed(tbl, 4));
720 25
        VHT_AppendValue(tbl, "12345", -1);
721 25
        AZ(vht_matchtable(tbl, ":path", "12345", NULL));
722
723
        /* New entry indexed from dynamic table */
724 25
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
725 25
        VHT_AppendValue(tbl, "abcde", -1);
726 25
        AZ(vht_matchtable(tbl, ":path", "abcde", ":path", "12345", NULL));
727 25
        AZ(tbl->maxsize - TBLSIZE(tbl)); /* No space left */
728
729
        /* New entry indexed from dynamic table, no overlap eviction */
730 25
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
731 25
        VHT_AppendValue(tbl, "ABCDE", -1);
732 25
        AZ(vht_matchtable(tbl, ":path", "ABCDE", ":path", "abcde", NULL));
733
734
        /* New entry indexed from dynamic table, overlap eviction */
735 25
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 1));
736 25
        AZ(vht_matchtable(tbl, ":path", "", ":path", "ABCDE", NULL));
737
738
        /* New entry indexed from dynamic table, overlap eviction with
739
           overlap larger than the copy buffer size */
740 25
        VHT_NewEntry(tbl);
741 25
        VHT_AppendName(tbl, longname, strlen(longname));
742 25
        AZ(vht_matchtable(tbl, longname, "", NULL));
743 25
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
744 25
        VHT_AppendValue(tbl, "2", -1);
745 25
        AZ(vht_matchtable(tbl, longname, "2", NULL));
746
747 25
        VHT_Fini(tbl);
748 25
        printf("Test 4 finished successfully\n");
749 25
        if (verbose)
750 0
                printf("\n");
751 25
}
752
753
static void
754 25
test_5(void)
755
{
756
        struct vht_table tbl[1];
757
        char buf_a[3];
758
        char buf_b[2];
759
        int i;
760
761 25
        if (verbose)
762 0
                printf("Test 5:\n");
763
764 25
        assert(sizeof buf_a > 0);
765 75
        for (i = 0; i < sizeof buf_a - 1; i++)
766 50
                buf_a[i] = 'a';
767 25
        buf_a[i++] = '\0';
768
769 25
        assert(sizeof buf_b > 0);
770 50
        for (i = 0; i < sizeof buf_b - 1; i++)
771 25
                buf_b[i] = 'b';
772 25
        buf_b[i++] = '\0';
773
774 25
        AZ(VHT_Init(tbl,
775
                3 * ((sizeof buf_a - 1)+(sizeof buf_b - 1)+VHT_ENTRY_SIZE)));
776
777 25
        VHT_NewEntry(tbl);
778 25
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
779 25
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
780 25
        AZ(vht_matchtable(tbl, buf_a, buf_b, NULL));
781
782 25
        VHT_NewEntry(tbl);
783 25
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
784 25
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
785 25
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, NULL));
786
787 25
        VHT_NewEntry(tbl);
788 25
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
789 25
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
790 25
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));
791
792 25
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 2));
793 25
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
794 25
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));
795
796 25
        VHT_Fini(tbl);
797 25
        printf("Test 5 finished successfully\n");
798 25
        if (verbose)
799 0
                printf("\n");
800 25
}
801
802
int
803 25
main(int argc, char **argv)
804
{
805
806 25
        if (argc == 2 && !strcmp(argv[1], "-v"))
807 0
                verbose = 1;
808 25
        else if (argc != 1) {
809 0
                fprintf(stderr, "Usage: %s [-v]\n", argv[0]);
810 0
                return (1);
811
        }
812
813 25
        if (verbose) {
814 0
                printf("sizeof (struct vht_table) == %zu\n",
815
                    sizeof (struct vht_table));
816 0
                printf("sizeof (struct vht_entry) == %zu\n",
817
                    sizeof (struct vht_entry));
818 0
                printf("\n");
819 0
        }
820
821 25
        test_1();
822 25
        test_2();
823 25
        test_3();
824 25
        test_4();
825 25
        test_5();
826
827 25
        return (0);
828 25
}
829
830
#endif  /* TABLE_TEST_DRIVER */