varnish-cache/bin/varnishd/hpack/vhp_table.c
1
/*-
2
 * Copyright (c) 2016 Varnish Software
3
 * All rights reserved.
4
 *
5
 * Author: Martin Blix Grydeland <martin@varnish-software.com>
6
 *
7
 * Redistribution and use in source and binary forms, with or without
8
 * modification, are permitted provided that the following conditions
9
 * are met:
10
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in the
14
 *    documentation and/or other materials provided with the distribution.
15
 *
16
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
20
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26
 * SUCH DAMAGE.
27
 *
28
 * Layout:
29
 *
30
 * buf [
31
 *    <x bytes name index n - 1> <x bytes value index n - 1>
32
 *    <x bytes name index n - 2> <x bytes value index n - 2>
33
 *    ...
34
 *    <x bytes name index 0> <x bytes value index 0>
35
 *
36
 *    (padding bytes for pointer alignment)
37
 *
38
 *    <struct vht_entry index 0>
39
 *    <struct vht_entry index 1>
40
 *    ...
41
 *    <struct vht_entry index n - 1>
42
 * ]
43
 *
44
 */
45
46
#include "config.h"
47
48
#include <stdio.h>
49
#include <stdlib.h>
50
#include <stdarg.h>
51
#include <string.h>
52
#include <stdint.h>
53
#include <limits.h>
54
55
#include "vdef.h"
56
#include "miniobj.h"
57
#include "vas.h"
58
59
#include "hpack/vhp.h"
60
61
#define VHT_STATIC_MAX 61
62
63
struct vht_static {
64
        const char *name;
65
        unsigned namelen;
66
        const char *value;
67
        unsigned valuelen;
68
};
69
70
static const struct vht_static static_table[] = {
71
#define HPS(NUM, NAME, VAL)                     \
72
        { NAME, sizeof NAME - 1, VAL, sizeof VAL - 1 },
73
#include "tbl/vhp_static.h"
74
};
75
76
#define TBLSIZE(tbl) ((tbl)->size + (tbl)->n * VHT_ENTRY_SIZE)
77
#define ENTRIES(buf, bufsize, n)                                        \
78
        (((struct vht_entry *)((uintptr_t)(buf) + bufsize)) - (n))
79
#define TBLENTRIES(tbl) ENTRIES((tbl)->buf, (tbl)->bufsize, (tbl)->n)
80
#define TBLENTRY(tbl, i) (&TBLENTRIES(tbl)[(i)])
81
#define ENTRYLEN(e) ((e)->namelen + (e)->valuelen)
82
#define ENTRYSIZE(e) (ENTRYLEN(e) + VHT_ENTRY_SIZE)
83
84
/****************************************************************************/
85
/* Internal interface */
86
87
static void
88 210
vht_newentry(struct vht_table *tbl)
89
{
90
        struct vht_entry *e;
91
92 210
        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE);
93 210
        tbl->n++;
94 210
        e = TBLENTRY(tbl, 0);
95 210
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
96 210
        e->offset = tbl->size;
97 210
}
98
99
/* Trim elements from the end until the table size is less than max. */
100
static void
101 2954
vht_trim(struct vht_table *tbl, ssize_t max)
102
{
103
        unsigned u, v;
104
        int i;
105
        struct vht_entry *e;
106
107 2954
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
108
109 2954
        if (max < 0)
110 0
                max = 0;
111 2954
        if (TBLSIZE(tbl) <= max)
112 5814
                return;
113
114 94
        u = v = 0;
115 490
        for (i = tbl->n - 1; i >= 0; i--) {
116 396
                e = TBLENTRY(tbl, i);
117 396
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
118 396
                if (TBLSIZE(tbl) - (u + v * VHT_ENTRY_SIZE) > max) {
119
                        /* Trim entry */
120 96
                        assert(e->offset == u);
121 96
                        u += ENTRYLEN(e);
122 96
                        v++;
123 96
                        e->magic = 0;
124
                } else {
125
                        /* Fixup offset */
126 300
                        assert(e->offset >= u);
127 300
                        e->offset -= u;
128
                }
129
        }
130 94
        assert(v <= tbl->n);
131
132 94
        memmove(tbl->buf, tbl->buf + u, tbl->size - u);
133 94
        memmove(TBLENTRY(tbl, v), TBLENTRY(tbl, 0), (tbl->n - v) * sizeof *e);
134 94
        tbl->n -= v;
135 94
        tbl->size -= u;
136
}
137
138
/* Append len bytes from buf to entry 0 name. Asserts if no space. */
139
static void
140 312
vht_appendname(struct vht_table *tbl, const char *buf, size_t len)
141
{
142
        struct vht_entry *e;
143
144 312
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
145 312
        e = TBLENTRY(tbl, 0);
146 312
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
147 312
        AZ(e->valuelen);        /* Name needs to be set before value */
148 312
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
149 312
        assert(e->offset + e->namelen == tbl->size);
150 312
        memcpy(tbl->buf + tbl->size, buf, len);
151 312
        e->namelen += len;
152 312
        tbl->size += len;
153 312
}
154
155
/* Append len bytes from buf to entry 0 value. Asserts if no space. */
156
static void
157 2260
vht_appendvalue(struct vht_table *tbl, const char *buf, size_t len)
158
{
159
        struct vht_entry *e;
160
161 2260
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
162 2260
        e = TBLENTRY(tbl, 0);
163 2260
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
164 2260
        assert(TBLSIZE(tbl) + len <= tbl->maxsize);
165 2260
        assert(e->offset + e->namelen + e->valuelen == tbl->size);
166 2260
        memcpy(tbl->buf + tbl->size, buf, len);
167 2260
        e->valuelen += len;
168 2260
        tbl->size += len;
169 2260
}
170
171
/****************************************************************************/
172
/* Public interface */
173
174
void
175 210
VHT_NewEntry(struct vht_table *tbl)
176
{
177
178 210
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
179 210
        assert(tbl->maxsize <= tbl->protomax);
180 210
        vht_trim(tbl, tbl->maxsize - VHT_ENTRY_SIZE);
181 210
        if (tbl->maxsize - TBLSIZE(tbl) < VHT_ENTRY_SIZE) {
182
                /* Maxsize less than one entry */
183 4
                assert(tbl->maxsize < VHT_ENTRY_SIZE);
184 214
                return;
185
        }
186 206
        vht_newentry(tbl);
187
}
188
189
int
190 178
VHT_NewEntry_Indexed(struct vht_table *tbl, unsigned idx)
191
{
192
        struct vht_entry *e, *e2;
193
        unsigned l, l2, lentry, lname, u;
194
        uint8_t tmp[48];
195
196
        /* Referenced name insertion. This has to be done carefully
197
           because the referenced name may be evicted as the result of the
198
           insertion (RFC 7541 section 4.4). */
199
200
        assert(sizeof tmp >= VHT_ENTRY_SIZE);
201
202 178
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
203 178
        assert(tbl->maxsize <= tbl->protomax);
204
205 178
        if (idx == 0)
206 0
                return (-1);
207
208 178
        if (idx <= VHT_STATIC_MAX) {
209
                /* Static table reference */
210 168
                VHT_NewEntry(tbl);
211 168
                VHT_AppendName(tbl, static_table[idx - 1].name,
212 168
                    static_table[idx - 1].namelen);
213 168
                return (0);
214
        }
215 10
        idx -= VHT_STATIC_MAX + 1;
216
217 10
        if (idx >= tbl->n)
218 0
                return (-1);    /* No such index */
219 10
        assert(tbl->maxsize >= VHT_ENTRY_SIZE);
220
221 10
        e = TBLENTRY(tbl, idx);
222 10
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
223
224
        /* Count how many elements we can safely evict to make space
225
           without evicting the referenced entry. */
226 10
        l = 0;
227 10
        u = 0;
228 24
        while (tbl->n - 1 - u > idx &&
229 2
            tbl->maxsize - TBLSIZE(tbl) + l < VHT_ENTRY_SIZE + e->namelen) {
230 2
                e2 = TBLENTRY(tbl, tbl->n - 1 - u);
231 2
                CHECK_OBJ_NOTNULL(e2, VHT_ENTRY_MAGIC);
232 2
                l += ENTRYSIZE(e2);
233 2
                u++;
234
        }
235 10
        vht_trim(tbl, TBLSIZE(tbl) - l);
236 10
        e += u;
237 10
        assert(e == TBLENTRY(tbl, idx));
238
239 10
        if (tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + e->namelen) {
240
                /* New entry with name fits */
241 4
                vht_newentry(tbl);
242 4
                idx++;
243 4
                assert(e == TBLENTRY(tbl, idx));
244 4
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
245 4
                vht_appendname(tbl, tbl->buf + e->offset, e->namelen);
246 4
                return (0);
247
        }
248
249
        /* The tricky case: The referenced name will be evicted as a
250
           result of the insertion. Move the referenced element data to
251
           the end of the buffer through a local buffer. */
252
253
        /* Remove the referenced element from the entry list */
254 6
        assert(idx == tbl->n - 1);
255 6
        assert(e->offset == 0);
256 6
        lname = e->namelen;
257 6
        lentry = ENTRYLEN(e);
258 6
        e->magic = 0;
259 6
        memmove(TBLENTRY(tbl, 1), TBLENTRY(tbl, 0), (tbl->n - 1) * sizeof *e);
260 6
        tbl->n--;
261
262
        /* Shift the referenced element last using a temporary buffer. */
263 6
        l = 0;
264 20
        while (l < lentry) {
265 8
                l2 = lentry - l;
266 8
                if (l2 > sizeof tmp)
267 2
                        l2 = sizeof tmp;
268 8
                memcpy(tmp, tbl->buf, l2);
269 8
                memmove(tbl->buf, tbl->buf + l2, tbl->size - l2);
270 8
                memcpy(tbl->buf + tbl->size - l2, tmp, l2);
271 8
                l += l2;
272
        }
273 6
        assert(l == lentry);
274 6
        tbl->size -= lentry;
275
276
        /* Fix up the existing element offsets */
277 12
        for (u = 0; u < tbl->n; u++) {
278 6
                e = TBLENTRY(tbl, u);
279 6
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
280 6
                assert(e->offset >= lentry);
281 6
                e->offset -= lentry;
282 6
                assert(e->offset + ENTRYLEN(e) <= tbl->size);
283
        }
284
285
        /* Insert the new entry with the name now present at the end of
286
           the buffer. */
287 6
        assert(tbl->maxsize - TBLSIZE(tbl) >= VHT_ENTRY_SIZE + lname);
288 6
        tbl->n++;
289 6
        e = TBLENTRY(tbl, 0);
290 6
        INIT_OBJ(e, VHT_ENTRY_MAGIC);
291 6
        e->offset = tbl->size;
292 6
        e->namelen = lname;
293 6
        tbl->size += lname;
294
295 6
        return (0);
296
}
297
298
void
299 308
VHT_AppendName(struct vht_table *tbl, const char *buf, ssize_t len)
300
{
301
302 308
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
303 308
        assert(tbl->maxsize <= tbl->protomax);
304 308
        if (len == 0)
305 0
                return;
306 308
        AN(buf);
307 308
        if (len < 0)
308 10
                len = strlen(buf);
309 308
        vht_trim(tbl, tbl->maxsize - len);
310 308
        if (tbl->n == 0)
311
                /* Max size exceeded */
312 0
                return;
313 308
        vht_appendname(tbl, buf, len);
314
}
315
316
void
317 2262
VHT_AppendValue(struct vht_table *tbl, const char *buf, ssize_t len)
318
{
319
320 2262
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
321 2262
        assert(tbl->maxsize <= tbl->protomax);
322 2262
        if (len == 0)
323 0
                return;
324 2262
        AN(buf);
325 2262
        if (len < 0)
326 20
                len = strlen(buf);
327 2262
        vht_trim(tbl, tbl->maxsize - len);
328 2262
        if (tbl->n == 0)
329
                /* Max size exceeded */
330 2
                return;
331 2260
        vht_appendvalue(tbl, buf, len);
332
}
333
334
int
335 8
VHT_SetMaxTableSize(struct vht_table *tbl, size_t maxsize)
336
{
337
338 8
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
339 8
        assert(tbl->maxsize <= tbl->protomax);
340 8
        if (maxsize > tbl->protomax)
341 2
                return (-1);
342 6
        vht_trim(tbl, maxsize);
343 6
        assert(TBLSIZE(tbl) <= maxsize);
344 6
        tbl->maxsize = maxsize;
345 6
        return (0);
346
}
347
348
int
349 158
VHT_SetProtoMax(struct vht_table *tbl, size_t protomax)
350
{
351
        size_t bufsize;
352
        char *buf;
353
354 158
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
355 158
        assert(protomax <= UINT_MAX);
356 158
        assert(tbl->maxsize <= tbl->protomax);
357
358 158
        if (protomax == tbl->protomax)
359 0
                return (0);
360
361 158
        if (tbl->maxsize > protomax)
362 2
                tbl->maxsize = protomax;
363 158
        vht_trim(tbl, tbl->maxsize);
364 158
        assert(TBLSIZE(tbl) <= tbl->maxsize);
365
366 158
        bufsize = PRNDUP(protomax);
367 158
        if (bufsize == tbl->bufsize) {
368 0
                tbl->protomax = protomax;
369 0
                return (0);
370
        }
371
372 158
        buf = malloc(bufsize);
373 158
        if (buf == NULL)
374 0
                return (-1);
375
376 158
        if (tbl->buf != NULL) {
377 4
                memcpy(buf, tbl->buf, tbl->size);
378 4
                memcpy(ENTRIES(buf, bufsize, tbl->n), TBLENTRIES(tbl),
379 4
                    sizeof (struct vht_entry) * tbl->n);
380 4
                free(tbl->buf);
381
        }
382 158
        tbl->buf = buf;
383 158
        tbl->bufsize = bufsize;
384 158
        tbl->protomax = protomax;
385 158
        return (0);
386
}
387
388
const char *
389 2078
VHT_LookupName(const struct vht_table *tbl, unsigned idx, size_t *plen)
390
{
391
        struct vht_entry *e;
392
393 2078
        AN(plen);
394 2078
        *plen = 0;
395
396 2078
        if (idx == 0) {
397 2
                return (NULL);
398
        }
399 2076
        if (idx <= VHT_STATIC_MAX) {
400 1488
                *plen = static_table[idx - 1].namelen;
401 1488
                return (static_table[idx - 1].name);
402
        }
403
404 588
        if (tbl == NULL)
405 0
                return (NULL);
406 588
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
407
408 588
        idx -= VHT_STATIC_MAX + 1;
409 588
        if (idx >= tbl->n)
410 0
                return (NULL);
411
412 588
        e = TBLENTRY(tbl, idx);
413 588
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
414 588
        assert(e->offset + e->namelen <= tbl->size);
415 588
        *plen = e->namelen;
416 588
        return (tbl->buf + e->offset);
417
}
418
419
const char *
420 1432
VHT_LookupValue(const struct vht_table *tbl, unsigned idx, size_t *plen)
421
{
422
        struct vht_entry *e;
423
424 1432
        AN(plen);
425 1432
        *plen = 0;
426
427 1432
        if (idx == 0) {
428 2
                return (NULL);
429
        }
430 1430
        if (idx <= VHT_STATIC_MAX) {
431 420
                *plen = static_table[idx - 1].valuelen;
432 420
                return (static_table[idx - 1].value);
433
        }
434
435 1010
        if (tbl == NULL)
436 0
                return (NULL);
437 1010
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
438
439 1010
        idx -= VHT_STATIC_MAX + 1;
440 1010
        if (idx >= tbl->n)
441 0
                return (NULL);
442
443 1010
        e = TBLENTRY(tbl, idx);
444 1010
        CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
445 1010
        assert(e->offset + e->namelen + e->valuelen <= tbl->size);
446 1010
        *plen = e->valuelen;
447 1010
        return (tbl->buf + e->offset + e->namelen);
448
}
449
450
int
451 154
VHT_Init(struct vht_table *tbl, size_t protomax)
452
{
453
        int r;
454
455
        assert(sizeof (struct vht_entry) <= VHT_ENTRY_SIZE);
456
457 154
        AN(tbl);
458 154
        if (protomax > UINT_MAX)
459 0
                return (-1);
460 154
        INIT_OBJ(tbl, VHT_TABLE_MAGIC);
461 154
        r = VHT_SetProtoMax(tbl, protomax);
462 154
        if (r) {
463 0
                tbl->magic = 0;
464 0
                return (r);
465
        }
466 154
        tbl->maxsize = tbl->protomax;
467 154
        return (0);
468
}
469
470
void
471 152
VHT_Fini(struct vht_table *tbl)
472
{
473
474 152
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
475 152
        free(tbl->buf);
476 152
        memset(tbl, 0, sizeof *tbl);
477 152
}
478
479
/****************************************************************************/
480
/* Internal interface */
481
482
#ifdef TABLE_TEST_DRIVER
483
484
#define VHT_DYNAMIC (VHT_STATIC_MAX + 1)
485
486
static int verbose = 0;
487
488
static int
489 44
vht_matchtable(struct vht_table *tbl, ...)
490
{
491
        va_list ap;
492
        unsigned u;
493
        int r;
494
        const char *a, *b;
495
        const struct vht_entry *e;
496
497 44
        CHECK_OBJ_NOTNULL(tbl, VHT_TABLE_MAGIC);
498
499 44
        va_start(ap, tbl);
500 44
        r = 0;
501 102
        for (u = 0; u < tbl->n; u++) {
502 58
                a = NULL;
503 58
                b = NULL;
504 58
                if (!r) {
505 58
                        a = va_arg(ap, const char *);
506 58
                        if (a == NULL) {
507 0
                                printf("Too many elements in table\n");
508 0
                                r = -1;
509
                        } else {
510 58
                                b = va_arg(ap, const char *);
511 58
                                AN(b);
512
                        }
513
                }
514
515 58
                e = TBLENTRY(tbl, u);
516 58
                CHECK_OBJ_NOTNULL(e, VHT_ENTRY_MAGIC);
517
518 58
                if (a) {
519 58
                        AN(b);
520 116
                        if (e->namelen != strlen(a) ||
521 58
                            strncmp(a, tbl->buf + e->offset, e->namelen))
522 0
                                r = -1;
523 116
                        if (e->valuelen != strlen(b) ||
524 58
                            strncmp(b, tbl->buf + e->offset + e->namelen,
525 58
                             e->valuelen))
526 0
                                r = -1;
527
                }
528
529 58
                if (verbose || r)
530 0
                        printf("%2u: @%03u (\"%.*s\", \"%.*s\")",
531 0
                            u, e->offset, (int)e->namelen, tbl->buf + e->offset,
532 0
                            (int)e->valuelen, tbl->buf + e->offset +e->namelen);
533
534 58
                if (a && (verbose || r)) {
535 0
                        AN(b);
536 0
                        printf(" %s (\"%s\", \"%s\")", (r ? "!=" : "=="), a, b);
537
                }
538
539 58
                if (verbose || r)
540 0
                        printf("\n");
541
        }
542 44
        if (!r) {
543 44
                a = va_arg(ap, const char *);
544 44
                if (a != NULL) {
545 0
                        printf("Missing elements in table\n");
546 0
                        r = -1;
547
                }
548
        }
549 44
        va_end(ap);
550
551 44
        if (verbose || r)
552 0
                printf("n=%d, size=%u, tblsz=%u, max=%u, pmax=%u, bufsz=%u\n",
553 0
                    tbl->n, tbl->size, TBLSIZE(tbl), tbl->maxsize,
554
                    tbl->protomax, tbl->bufsize);
555
556 44
        return (r);
557
}
558
559
static void
560 2
test_1(void)
561
{
562
        /* Static table */
563
564
        const char *p;
565
        size_t l;
566
567 2
        if (verbose)
568 0
                printf("Test 1:\n");
569
570
        /* 1: ':authority' -> '' */
571 2
        p = VHT_LookupName(NULL, 1, &l);
572 2
        assert(l == strlen(":authority"));
573 2
        AZ(strncmp(p, ":authority", strlen(":authority")));
574 2
        p = VHT_LookupValue(NULL, 1, &l);
575 2
        AN(p);
576 2
        AZ(l);
577
578
        /* 5: ':path' -> '/index.html' */
579 2
        p = VHT_LookupValue(NULL, 5, &l);
580 2
        assert(l == strlen("/index.html"));
581 2
        AZ(strncmp(p, "/index.html", strlen("/index.html")));
582
583
        /* 61: 'www-authenticate' -> '' */
584 2
        p = VHT_LookupName(NULL, 61, &l);
585 2
        assert(l == strlen("www-authenticate"));
586 2
        AZ(strncmp(p, "www-authenticate", strlen("www-authenticate")));
587 2
        p = VHT_LookupValue(NULL, 61, &l);
588 2
        AN(p);
589 2
        AZ(l);
590
591
        /* Test zero index */
592 2
        AZ(VHT_LookupName(NULL, 0, &l));
593 2
        AZ(l);
594 2
        AZ(VHT_LookupValue(NULL, 0, &l));
595 2
        AZ(l);
596
597 2
        printf("Test 1 finished successfully\n");
598 2
        if (verbose)
599 0
                printf("\n");
600 2
}
601
602
static void
603 2
test_2(void)
604
{
605
        /* Test filling and overflow */
606
607
        struct vht_table tbl[1];
608
609 2
        if (verbose)
610 0
                printf("Test 2:\n");
611
612 2
        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE + 10));
613
614 2
        VHT_NewEntry(tbl);
615 2
        VHT_AppendName(tbl, "12345", -1);
616 2
        VHT_AppendValue(tbl, "abcde", -1);
617 2
        assert(TBLSIZE(tbl) == VHT_ENTRY_SIZE + 10);
618
        /* 0: '12345' -> 'abcde' */
619 2
        AZ(vht_matchtable(tbl, "12345", "abcde", NULL));
620
621 2
        VHT_AppendValue(tbl, "f", -1);
622 2
        AZ(vht_matchtable(tbl, NULL));
623
624 2
        VHT_NewEntry(tbl);
625 2
        AZ(vht_matchtable(tbl, "", "", NULL));
626
627 2
        VHT_Fini(tbl);
628 2
        AZ(tbl->buf);
629
630 2
        printf("Test 2 finished successfully\n");
631 2
        if (verbose)
632 0
                printf("\n");
633 2
}
634
635
static void
636 2
test_3(void)
637
{
638
        /* Test change in proto max size and dynamic max size */
639
640
        struct vht_table tbl[1];
641
642 2
        if (verbose)
643 0
                printf("Test 3:\n");
644
645 2
        AZ(VHT_Init(tbl, 4096));
646
647 2
        VHT_NewEntry(tbl);
648 2
        VHT_AppendName(tbl, "a", -1);
649 2
        VHT_AppendValue(tbl, "12345", -1);
650 2
        VHT_NewEntry(tbl);
651 2
        VHT_AppendName(tbl, "b", -1);
652 2
        VHT_AppendValue(tbl, "67890", -1);
653 2
        VHT_NewEntry(tbl);
654 2
        VHT_AppendName(tbl, "c", -1);
655 2
        VHT_AppendValue(tbl, "abcde", -1);
656 2
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", "a", "12345", NULL));
657
658
        /* Buffer reallocation */
659 2
        AZ(VHT_SetProtoMax(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
660 2
        AZ(vht_matchtable(tbl, "c", "abcde", "b", "67890", NULL));
661
662
        /* Increase table size beyond protomax */
663 2
        assert(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 + 1) == -1);
664
665
        /* Decrease by one */
666 2
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2 - 1));
667 2
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));
668
669
        /* Increase by one back to protomax */
670 2
        AZ(VHT_SetMaxTableSize(tbl, VHT_ENTRY_SIZE * 2 + 6 * 2));
671 2
        AZ(vht_matchtable(tbl, "c", "abcde", NULL));
672
673
        /* Add entry */
674 2
        VHT_NewEntry(tbl);
675 2
        VHT_AppendName(tbl, "d", -1);
676 2
        VHT_AppendValue(tbl, "ABCDE", -1);
677 2
        AZ(vht_matchtable(tbl, "d", "ABCDE", "c", "abcde", NULL));
678
679
        /* Set to zero */
680 2
        AZ(VHT_SetMaxTableSize(tbl, 0));
681 2
        AZ(vht_matchtable(tbl, NULL));
682 2
        VHT_NewEntry(tbl);
683 2
        AZ(vht_matchtable(tbl, NULL));
684
685
        /* Set protomax to zero */
686 2
        AZ(VHT_SetProtoMax(tbl, 0));
687 2
        AZ(vht_matchtable(tbl, NULL));
688 2
        VHT_NewEntry(tbl);
689 2
        AZ(vht_matchtable(tbl, NULL));
690
691 2
        VHT_Fini(tbl);
692
693 2
        printf("Test 3 finished successfully\n");
694 2
        if (verbose)
695 0
                printf("\n");
696 2
}
697
698
static void
699 2
test_4(void)
700
{
701
        /* Referenced name new entry */
702
703
        struct vht_table tbl[1];
704
        static const char longname[] =
705
            "1234567890"
706
            "1234567890"
707
            "1234567890"
708
            "1234567890"
709
            "1234567890"
710
            "1";        /* 51 bytes + VHT_ENTRY_SIZE == 83 */
711
712 2
        if (verbose)
713 0
                printf("Test 4:\n");
714
715 2
        AZ(VHT_Init(tbl, VHT_ENTRY_SIZE * 2 + 10 * 2)); /* 84 bytes */
716
717
        /* New entry indexed from static table */
718 2
        AZ(VHT_NewEntry_Indexed(tbl, 4));
719 2
        VHT_AppendValue(tbl, "12345", -1);
720 2
        AZ(vht_matchtable(tbl, ":path", "12345", NULL));
721
722
        /* New entry indexed from dynamic table */
723 2
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
724 2
        VHT_AppendValue(tbl, "abcde", -1);
725 2
        AZ(vht_matchtable(tbl, ":path", "abcde", ":path", "12345", NULL));
726 2
        AZ(tbl->maxsize - TBLSIZE(tbl)); /* No space left */
727
728
        /* New entry indexed from dynamic table, no overlap eviction */
729 2
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
730 2
        VHT_AppendValue(tbl, "ABCDE", -1);
731 2
        AZ(vht_matchtable(tbl, ":path", "ABCDE", ":path", "abcde", NULL));
732
733
        /* New entry indexed from dynamic table, overlap eviction */
734 2
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 1));
735 2
        AZ(vht_matchtable(tbl, ":path", "", ":path", "ABCDE", NULL));
736
737
        /* New entry indexed from dynamic table, overlap eviction with
738
           overlap larger than the copy buffer size */
739 2
        VHT_NewEntry(tbl);
740 2
        VHT_AppendName(tbl, longname, strlen(longname));
741 2
        AZ(vht_matchtable(tbl, longname, "", NULL));
742 2
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 0));
743 2
        VHT_AppendValue(tbl, "2", -1);
744 2
        AZ(vht_matchtable(tbl, longname, "2", NULL));
745
746 2
        VHT_Fini(tbl);
747 2
        printf("Test 4 finished successfully\n");
748 2
        if (verbose)
749 0
                printf("\n");
750 2
}
751
752
static void
753 2
test_5(void)
754
{
755
        struct vht_table tbl[1];
756
        char buf_a[3];
757
        char buf_b[2];
758
        int i;
759
760 2
        if (verbose)
761 0
                printf("Test 5:\n");
762
763
        assert(sizeof buf_a > 0);
764 6
        for (i = 0; i < sizeof buf_a - 1; i++)
765 4
                buf_a[i] = 'a';
766 2
        buf_a[i++] = '\0';
767
768
        assert(sizeof buf_b > 0);
769 4
        for (i = 0; i < sizeof buf_b - 1; i++)
770 2
                buf_b[i] = 'b';
771 2
        buf_b[i++] = '\0';
772
773 2
        AZ(VHT_Init(tbl,
774
                3 * ((sizeof buf_a - 1)+(sizeof buf_b - 1)+VHT_ENTRY_SIZE)));
775
776 2
        VHT_NewEntry(tbl);
777 2
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
778 2
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
779 2
        AZ(vht_matchtable(tbl, buf_a, buf_b, NULL));
780
781 2
        VHT_NewEntry(tbl);
782 2
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
783 2
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
784 2
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, NULL));
785
786 2
        VHT_NewEntry(tbl);
787 2
        VHT_AppendName(tbl, buf_a, sizeof buf_a - 1);
788 2
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
789 2
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));
790
791 2
        AZ(VHT_NewEntry_Indexed(tbl, VHT_DYNAMIC + 2));
792 2
        VHT_AppendValue(tbl, buf_b, sizeof buf_b - 1);
793 2
        AZ(vht_matchtable(tbl, buf_a, buf_b, buf_a, buf_b, buf_a, buf_b, NULL));
794
795 2
        VHT_Fini(tbl);
796 2
        printf("Test 5 finished successfully\n");
797 2
        if (verbose)
798 0
                printf("\n");
799 2
}
800
801
int
802 2
main(int argc, char **argv)
803
{
804
805 2
        if (argc == 2 && !strcmp(argv[1], "-v"))
806 0
                verbose = 1;
807 2
        else if (argc != 1) {
808 0
                fprintf(stderr, "Usage: %s [-v]\n", argv[0]);
809 0
                return (1);
810
        }
811
812 2
        if (verbose) {
813 0
                printf("sizeof (struct vht_table) == %zu\n",
814
                    sizeof (struct vht_table));
815 0
                printf("sizeof (struct vht_entry) == %zu\n",
816
                    sizeof (struct vht_entry));
817 0
                printf("\n");
818
        }
819
820 2
        test_1();
821 2
        test_2();
822 2
        test_3();
823 2
        test_4();
824 2
        test_5();
825
826 2
        return (0);
827
}
828
829
#endif  /* TABLE_TEST_DRIVER */