vinyl-cache/lib/libvcc/vcc_acl.c
0
/*-
1
 * Copyright (c) 2006 Verdens Gang AS
2
 * Copyright (c) 2006-2010 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
6
 *
7
 * SPDX-License-Identifier: BSD-2-Clause
8
 *
9
 * Redistribution and use in source and binary forms, with or without
10
 * modification, are permitted provided that the following conditions
11
 * are met:
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 * 2. Redistributions in binary form must reproduce the above copyright
15
 *    notice, this list of conditions and the following disclaimer in the
16
 *    documentation and/or other materials provided with the distribution.
17
 *
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
22
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28
 * SUCH DAMAGE.
29
 */
30
31
#include "config.h"
32
33
#include <sys/socket.h>
34
35
#include <netinet/in.h>
36
37
#include <netdb.h>
38
#include <stdlib.h>
39
#include <string.h>
40
41
#include "vcc_compile.h"
42
#include <vtcp.h>
43
#include <vtree.h>
44
#include <vsa.h>
45
46
#define ACL_MAXADDR     (sizeof(struct in6_addr) + 1)
47
48
VRBT_HEAD(acl_tree, acl_e);
49
50
struct acl {
51
        unsigned                magic;
52
#define VCC_ACL_MAGIC           0xb9fb3cd0
53
54
        int                     flag_log;
55
        int                     flag_fold;
56
        int                     flag_fold_report;
57
        int                     flag_pedantic;
58
        int                     flag_table;
59
60
        struct acl_tree         acl_tree;
61
};
62
63
struct acl_e {
64
        unsigned                magic;
65
#define VCC_ACL_E_MAGIC 0xcac81e23
66
        VRBT_ENTRY(acl_e)       branch;
67
        unsigned char           data[ACL_MAXADDR];
68
        unsigned                mask;
69
        unsigned                not;
70
        unsigned                para;
71
        unsigned                overlapped;
72
        char                    *addr;
73
        const char              *fixed;
74
        struct token            *t_addr;
75
        struct token            *t_mask;
76
};
77
78
enum acl_cmp_e {
79
        ACL_EQ = 0,
80
        ACL_LT = -1,            // a < b
81
        ACL_GT = 1,             // b > a
82
        ACL_CONTAINED = -2,     // b contains a
83
        ACL_CONTAINS = 2,       // a contains b
84
        ACL_LEFT = -3,          // a + 1 == b
85
        ACL_RIGHT = 3           // a == b + 1
86
};
87
88
static void vcc_acl_insert_entry(struct vcc *, struct acl_e **);
89
90
/*
91
 * Compare two acl rules for relation
92
 */
93
94
#define CMP(n, a, b)                                                    \
95
        do {                                                            \
96
                if ((a) < (b))                                          \
97
                        return (enum acl_cmp_e)(-n);                    \
98
                else if ((b) < (a))                                     \
99
                        return (n);                                     \
100
        } while (0)
101
102
#define CMPA(a, b)                                                      \
103
        do {                                                            \
104
                if (((a) | 1) == (b))                                   \
105
                        return (ACL_LEFT);                              \
106
                else if (((b) | 1) == (a))                              \
107
                        return (ACL_RIGHT);                             \
108
        } while (0)
109
110
static void
111 8
vcl_acl_free(struct acl_e **aep)
112
{
113
        struct acl_e *a;
114
115 8
        TAKE_OBJ_NOTNULL(a, aep, VCC_ACL_E_MAGIC);
116 8
        free(a->addr);
117 8
        FREE_OBJ(a);
118 8
}
119
120
static enum acl_cmp_e
121 2220
vcl_acl_cmp(const struct acl_e *ae1, const struct acl_e *ae2)
122
{
123
        const unsigned char *p1, *p2;
124
        unsigned m;
125
        unsigned char a1, a2;
126
127 2220
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
128 2220
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
129
130 2220
        p1 = ae1->data;
131 2220
        p2 = ae2->data;
132 2220
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
133 11520
        for (; m >= 8; m -= 8) {
134 10540
                if (m == 8 && ae1->mask == ae2->mask)
135 228
                        CMPA(*p1, *p2);
136 19756
                CMP(ACL_GT, *p1, *p2);
137 9300
                p1++;
138 9300
                p2++;
139 9300
        }
140 980
        if (m) {
141 956
                assert (m < 8);
142 956
                a1 = *p1 >> (8 - m);
143 956
                a2 = *p2 >> (8 - m);
144 956
                if (ae1->mask == ae2->mask)
145 292
                        CMPA(a1, a2);
146 1292
                CMP(ACL_GT, a1, a2);
147 436
        } else if (ae1->mask == ae2->mask) {
148 8
                CMPA(*p1, *p2);
149 4
        }
150
        /* Long mask is less than short mask */
151 444
        CMP(ACL_CONTAINS, ae2->mask, ae1->mask);
152
153 8
        return (ACL_EQ);
154 2220
}
155
156
static int
157 444
vcl_acl_disjoint(const struct acl_e *ae1, const struct acl_e *ae2)
158
{
159
        const unsigned char *p1, *p2;
160
        unsigned m;
161
162 444
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
163 444
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
164
165 444
        p1 = ae1->data;
166 444
        p2 = ae2->data;
167 444
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
168 3224
        for (; m >= 8; m -= 8) {
169 5684
                CMP(ACL_GT, *p1, *p2);
170 2780
                p1++;
171 2780
                p2++;
172 2780
        }
173 320
        if (m) {
174 288
                m = 0xff00 >> m;
175 288
                m &= 0xff;
176 536
                CMP(ACL_GT, *p1 & m, *p2 & m);
177 248
        }
178 280
        return (0);
179 444
}
180
181 1496
VRBT_GENERATE_INSERT_COLOR(acl_tree, acl_e, branch, static)
182 784
VRBT_GENERATE_INSERT_FINISH(acl_tree, acl_e, branch, static)
183 2572
VRBT_GENERATE_INSERT(acl_tree, acl_e, branch, vcl_acl_cmp, static)
184 188
VRBT_GENERATE_REMOVE_COLOR(acl_tree, acl_e, branch, static)
185 348
VRBT_GENERATE_REMOVE(acl_tree, acl_e, branch, static)
186 800
VRBT_GENERATE_MINMAX(acl_tree, acl_e, branch, static)
187 2484
VRBT_GENERATE_NEXT(acl_tree, acl_e, branch, static)
188 1952
VRBT_GENERATE_PREV(acl_tree, acl_e, branch, static)
189
190
static char *
191 740
vcc_acl_chk(struct vcc *tl, const struct acl_e *ae, const int l,
192
    unsigned char *p, int fam)
193
{
194
        const unsigned char *u;
195
        char h[VTCP_ADDRBUFSIZE];
196
        char t[VTCP_ADDRBUFSIZE + 10];
197 740
        char s[vsa_suckaddr_len];
198 740
        char *r = NULL;
199
        const struct suckaddr *sa;
200
        unsigned m;
201 740
        int ll, ret = 0;
202
203 740
        u = p;
204 740
        ll = l;
205 740
        m = ae->mask;
206
207 740
        p += m / 8;
208 740
        ll -= m / 8;
209 740
        assert (ll >= 0);
210 740
        m %= 8;
211
212 740
        if (m && ((unsigned)*p << m & 0xff) != 0) {
213 16
                ret = 1;
214 16
                m = 0xff00 >> m;
215 16
                *p &= m;
216 16
        }
217 740
        if (m) {
218 400
                p++;
219 400
                ll--;
220 400
        }
221
222 1384
        for ( ; ll > 0; p++, ll--) {
223 644
                if (*p == 0)
224 624
                        continue;
225 20
                ret = 1;
226 20
                *p = 0;
227 20
        }
228 740
        if (ret == 0)
229 704
                return (NULL);
230
231 36
        sa = VSA_BuildFAP(s, fam, u, l, NULL, 0);
232 36
        AN(sa);
233 36
        VTCP_name(sa, h, sizeof h, NULL, 0);
234 36
        bprintf(t, "%s/%d", h, ae->mask);
235 36
        if (tl->acl->flag_pedantic != 0) {
236 8
                VSB_cat(tl->sb, "Non-zero bits in masked part, ");
237 8
                VSB_printf(tl->sb, "(maybe use %s ?)\n", t);
238 8
                vcc_ErrWhere(tl, ae->t_addr);
239 8
        }
240 36
        REPLACE(r, t);
241 36
        return (r);
242 740
}
243
244
static void
245 808
vcl_acl_fold(struct vcc *tl, struct acl_e **l, struct acl_e **r)
246
{
247
        enum acl_cmp_e cmp;
248
249 808
        AN(l);
250 808
        AN(r);
251 808
        CHECK_OBJ_NOTNULL(*l, VCC_ACL_E_MAGIC);
252 808
        CHECK_OBJ_NOTNULL(*r, VCC_ACL_E_MAGIC);
253
254 808
        if ((*l)->not || (*r)->not)
255 408
                return;
256
257 400
        cmp = vcl_acl_cmp(*l, *r);
258
259 400
        assert(cmp < 0);
260 400
        if (cmp == ACL_LT)
261 264
                return;
262
263 136
        do {
264 140
                switch (cmp) {
265
                case ACL_CONTAINED:
266 88
                        if (tl->acl->flag_fold_report) {
267 88
                                VSB_cat(tl->sb, "ACL entry:\n");
268 88
                                vcc_ErrWhere(tl, (*r)->t_addr);
269 88
                                VSB_cat(tl->sb, "supersedes / removes:\n");
270 88
                                vcc_ErrWhere(tl, (*l)->t_addr);
271 88
                                vcc_Warn(tl);
272 88
                        }
273 88
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
274 88
                        FREE_OBJ(*l);
275 88
                        *l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, *r);
276 88
                        break;
277
                case ACL_LEFT:
278 52
                        (*l)->mask--;
279 52
                        (*l)->fixed = "folded";
280 52
                        if (tl->acl->flag_fold_report) {
281 44
                                VSB_cat(tl->sb, "ACL entry:\n");
282 44
                                vcc_ErrWhere(tl, (*l)->t_addr);
283 44
                                VSB_cat(tl->sb, "left of:\n");
284 44
                                vcc_ErrWhere(tl, (*r)->t_addr);
285 88
                                VSB_printf(tl->sb, "removing the latter and "
286
                                    "expanding mask of the former by one to "
287 44
                                    "/%u\n", (*l)->mask - 8);
288 44
                                vcc_Warn(tl);
289 44
                        }
290 52
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *r);
291 52
                        FREE_OBJ(*r);
292 52
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
293 52
                        vcc_acl_insert_entry(tl, l);
294 52
                        return;
295
                default:
296 0
                        INCOMPL();
297 0
                }
298 88
                if (*l == NULL || *r == NULL || (*l)->not || (*r)->not)
299 56
                        break;
300 32
                cmp = vcl_acl_cmp(*l, *r);
301 32
        } while (cmp != ACL_LT);
302 808
}
303
304
static void
305 792
vcc_acl_insert_entry(struct vcc *tl, struct acl_e **aenp)
306
{
307
        struct acl_e *ae2, *l, *r;
308
309 792
        CHECK_OBJ_NOTNULL(*aenp, VCC_ACL_E_MAGIC);
310 792
        ae2 = VRBT_INSERT(acl_tree, &tl->acl->acl_tree, *aenp);
311 792
        if (ae2 != NULL) {
312 8
                if (ae2->not != (*aenp)->not) {
313 4
                        VSB_cat(tl->sb, "Conflicting ACL entries:\n");
314 4
                        vcc_ErrWhere(tl, ae2->t_addr);
315 4
                        VSB_cat(tl->sb, "vs:\n");
316 4
                        vcc_ErrWhere(tl, (*aenp)->t_addr);
317 4
                }
318 8
                return;
319
        }
320
321 784
        r = *aenp;
322 784
        *aenp = NULL;
323
324 784
        if (tl->acl->flag_fold == 0)
325 84
                return;
326
327 700
        l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, r);
328 700
        if (l != NULL) {
329 496
                vcl_acl_fold(tl, &l, &r);
330 496
        }
331 700
        if (r == NULL)
332 40
                return;
333 660
        l = r;
334 660
        r = VRBT_NEXT(acl_tree, &tl->acl->acl_tree, l);
335 660
        if (r == NULL)
336 348
                return;
337 312
        vcl_acl_fold(tl, &l, &r);
338 792
}
339
340
static void
341 748
vcc_acl_add_entry(struct vcc *tl, const struct acl_e *ae, int l,
342
    unsigned char *u, int fam)
343
{
344
        struct acl_e *aen;
345
346 748
        if (fam == PF_INET && ae->mask > 32) {
347 8
                VSB_printf(tl->sb,
348 4
                    "Too wide mask (/%u) for IPv4 address\n", ae->mask);
349 4
                if (ae->t_mask != NULL)
350 4
                        vcc_ErrWhere(tl, ae->t_mask);
351
                else
352 0
                        vcc_ErrWhere(tl, ae->t_addr);
353 4
                return;
354
        }
355 744
        if (fam == PF_INET6 && ae->mask > 128) {
356 8
                VSB_printf(tl->sb,
357 4
                    "Too wide mask (/%u) for IPv6 address\n", ae->mask);
358 4
                vcc_ErrWhere(tl, ae->t_mask);
359 4
                return;
360
        }
361
362
        /* Make a copy from the template */
363 740
        ALLOC_OBJ(aen, VCC_ACL_E_MAGIC);
364 740
        AN(aen);
365 740
        *aen = *ae;
366 740
        aen->addr = strdup(ae->addr);
367 740
        AN(aen->addr);
368
369 740
        aen->fixed = vcc_acl_chk(tl, ae, l, u, fam);
370
371
        /* We treat family as part of address, it saves code */
372 740
        assert(fam <= 0xff);
373 740
        aen->data[0] = fam & 0xff;
374 740
        aen->mask += 8;
375
376 740
        assert(l + 1UL <= sizeof aen->data);
377 740
        memcpy(aen->data + 1L, u, l);
378
379 740
        vcc_acl_insert_entry(tl, &aen);
380 740
        if (aen != NULL)
381 8
                vcl_acl_free(&aen);
382 748
}
383
384
static void
385 236
vcc_acl_try_getaddrinfo(struct vcc *tl, struct acl_e *ae)
386
{
387
        struct addrinfo *res0, *res, hint;
388
        struct sockaddr_in *sin4;
389
        struct sockaddr_in6 *sin6;
390
        unsigned char *u, i4, i6;
391
        int error;
392
393 236
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
394 236
        memset(&hint, 0, sizeof hint);
395 236
        hint.ai_family = PF_UNSPEC;
396 236
        hint.ai_socktype = SOCK_STREAM;
397 236
        error = getaddrinfo(ae->addr, "0", &hint, &res0);
398 236
        if (error) {
399 16
                if (ae->para) {
400 16
                        VSB_printf(tl->sb,
401
                            "Warning: %s ignored\n  -- %s\n",
402 8
                            ae->addr, gai_strerror(error));
403 16
                        Fh(tl, 1, "/* Ignored ACL entry: %s%s",
404 8
                            ae->para ? "\"(\" " : "", ae->not ? "\"!\" " : "");
405 8
                        EncToken(tl->fh, ae->t_addr);
406 8
                        if (ae->t_mask)
407 4
                                Fh(tl, 0, "/%u", ae->mask);
408 8
                        Fh(tl, 0, "%s\n", ae->para ? " \")\"" : "");
409 16
                        Fh(tl, 1, " * getaddrinfo:  %s */\n",
410 8
                             gai_strerror(error));
411 8
                } else {
412 16
                        VSB_printf(tl->sb,
413
                            "DNS lookup(%s): %s\n",
414 8
                            ae->addr, gai_strerror(error));
415 8
                        vcc_ErrWhere(tl, ae->t_addr);
416
                }
417 16
                return;
418
        }
419
420 220
        i4 = i6 = 0;
421 456
        for (res = res0; res != NULL; res = res->ai_next) {
422 236
                switch (res->ai_family) {
423
                case PF_INET:
424 16
                        i4++;
425 16
                        break;
426
                case PF_INET6:
427 220
                        i6++;
428 220
                        break;
429
                default:
430 0
                        VSB_printf(tl->sb,
431
                            "Ignoring unknown protocol family (%d) for %.*s\n",
432 0
                                res->ai_family, PF(ae->t_addr));
433 0
                        continue;
434
                }
435 236
        }
436
437 220
        if (ae->t_mask != NULL && i4 > 0 && i6 > 0) {
438 0
                VSB_printf(tl->sb,
439
                    "Mask (/%u) specified, but string resolves to"
440 0
                    " both IPv4 and IPv6 addresses.\n", ae->mask);
441 0
                vcc_ErrWhere(tl, ae->t_mask);
442 0
                freeaddrinfo(res0);
443 0
                return;
444
        }
445
446 448
        for (res = res0; res != NULL; res = res->ai_next) {
447 236
                switch (res->ai_family) {
448
                case PF_INET:
449 16
                        assert(PF_INET < 256);
450 16
                        sin4 = (void*)res->ai_addr;
451 16
                        assert(sizeof(sin4->sin_addr) == 4);
452 16
                        u = (void*)&sin4->sin_addr;
453 16
                        if (ae->t_mask == NULL)
454 16
                                ae->mask = 32;
455 16
                        vcc_acl_add_entry(tl, ae, 4, u, res->ai_family);
456 16
                        break;
457
                case PF_INET6:
458 220
                        assert(PF_INET6 < 256);
459 220
                        sin6 = (void*)res->ai_addr;
460 220
                        assert(sizeof(sin6->sin6_addr) == 16);
461 220
                        u = (void*)&sin6->sin6_addr;
462 220
                        if (ae->t_mask == NULL)
463 40
                                ae->mask = 128;
464 220
                        vcc_acl_add_entry(tl, ae, 16, u, res->ai_family);
465 220
                        break;
466
                default:
467 0
                        continue;
468
                }
469 236
                if (tl->err)
470 8
                        freeaddrinfo(res0);
471 236
                ERRCHK(tl);
472 228
        }
473 212
        freeaddrinfo(res0);
474
475 236
}
476
477
/*--------------------------------------------------------------------
478
 * Ancient stupidity on the part of X/Open and other standards orgs
479
 * dictate that "192.168" be translated to 192.0.0.168.  Ever since
480
 * CIDR happened, "192.168/16" notation has been used, but apparently
481
 * no API supports parsing this, so roll our own.
482
 */
483
484
static int
485 748
vcc_acl_try_netnotation(struct vcc *tl, struct acl_e *ae)
486
{
487
        unsigned char b[4];
488
        int i, j, k;
489
        unsigned u;
490
        const char *p;
491
492 748
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
493 748
        memset(b, 0, sizeof b);
494 748
        p = ae->addr;
495 2192
        for (i = 0; i < 4; i++) {
496 2192
                j = sscanf(p, "%u%n", &u, &k);
497 2192
                if (j != 1)
498 216
                        return (0);
499 1976
                if (u & ~0xff)
500 8
                        return (0);
501 1968
                b[i] = (unsigned char)u;
502 1968
                if (p[k] == '\0')
503 512
                        break;
504 1456
                if (p[k] != '.')
505 12
                        return (0);
506 1444
                p += k + 1;
507 1444
        }
508 512
        if (ae->t_mask == NULL)
509 112
                ae->mask = 8 + 8 * i;
510 512
        vcc_acl_add_entry(tl, ae, 4, b, AF_INET);
511 512
        return (1);
512 748
}
513
514
static void
515 764
vcc_acl_entry(struct vcc *tl)
516
{
517
        struct acl_e ae[1];
518
        char *sl, *e;
519
520 764
        INIT_OBJ(ae, VCC_ACL_E_MAGIC);
521
522 764
        if (tl->t->tok == '!') {
523 168
                ae->not = 1;
524 168
                vcc_NextToken(tl);
525 168
        }
526
527 764
        if (tl->t->tok == '(') {
528 12
                ae->para = 1;
529 12
                vcc_NextToken(tl);
530 12
        }
531
532 764
        if (!ae->not && tl->t->tok == '!') {
533 4
                ae->not = 1;
534 4
                vcc_NextToken(tl);
535 4
        }
536
537 764
        ExpectErr(tl, CSTR);
538 764
        ae->t_addr = tl->t;
539 764
        ae->addr = ae->t_addr->dec;
540 764
        vcc_NextToken(tl);
541
542 764
        if (strchr(ae->t_addr->dec, '/') != NULL) {
543 20
                sl = strchr(ae->addr, '/');
544 20
                AN(sl);
545 20
                *sl++ = '\0';
546 20
                e = NULL;
547 20
                ae->mask = strtoul(sl, &e, 10);
548 20
                if (*e != '\0') {
549 8
                        VSB_cat(tl->sb, ".../mask is not numeric.\n");
550 8
                        vcc_ErrWhere(tl, ae->t_addr);
551 8
                        return;
552
                }
553 12
                ae->t_mask = ae->t_addr;
554 12
                if (tl->t->tok == '/') {
555 4
                        VSB_cat(tl->sb, "/mask only allowed once.\n");
556 4
                        vcc_ErrWhere(tl, tl->t);
557 4
                        return;
558
                }
559 752
        } else if (tl->t->tok == '/') {
560 576
                vcc_NextToken(tl);
561 576
                ae->t_mask = tl->t;
562 576
                ExpectErr(tl, CNUM);
563 576
                ae->mask = vcc_UintVal(tl);
564 576
        }
565
566 752
        if (ae->para)
567 12
                SkipToken(tl, ')');
568
569 748
        if (!vcc_acl_try_netnotation(tl, ae)) {
570 236
                ERRCHK(tl);
571 236
                vcc_acl_try_getaddrinfo(tl, ae);
572 236
        }
573 748
        ERRCHK(tl);
574 764
}
575
576
/*********************************************************************
577
 * Emit the tokens making up an entry as C-strings
578
 */
579
580
static void
581 216
vcc_acl_emit_tokens(const struct vcc *tl, const struct acl_e *ae)
582
{
583
        struct token *t;
584 216
        const char *sep = "";
585
586 216
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
587 216
        t = ae->t_addr;
588 216
        do {
589 632
                if (t->tok == CSTR) {
590 216
                        Fh(tl, 0, "%s\"\\\"\" ", sep);
591 216
                        EncToken(tl->fh, t);
592 216
                        Fh(tl, 0, " \"\\\"\"");
593 632
                } else if (t == ae->t_mask) {
594 208
                        Fh(tl, 0, " \"%u\"", ae->mask - 8);
595 208
                } else {
596 208
                        Fh(tl, 0, "%s\"%.*s\"", sep, PF(t));
597
                }
598 632
                if (t == ae->t_mask)
599 208
                        break;
600 424
                t = vcc_PeekTokenFrom(tl, t);
601 424
                AN(t);
602 424
                sep = " ";
603 424
        } while (ae->t_mask != NULL);
604 216
        if (ae->fixed)
605 44
                Fh(tl, 0, "\" fixed: %s\"", ae->fixed);
606 216
}
607
608
/*********************************************************************
609
 * Emit ACL on table format
610
 */
611
612
static unsigned
613 8
vcc_acl_emit_tables(const struct vcc *tl, unsigned n, const char *name)
614
{
615
        struct acl_e *ae;
616 8
        unsigned rv = sizeof(ae->data) + 3;
617 8
        unsigned nn = 0;
618
        size_t sz;
619
620 16
        Fh(tl, 0, "\nstatic unsigned char acl_tbl_%s[%u*%u] = {\n",
621 8
            name, n, rv);
622 184
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
623 176
                if (ae->overlapped)
624 144
                        continue;
625 32
                Fh(tl, 0, "\t0x%02x,", ae->not ? 0 : 1);
626 32
                Fh(tl, 0, "0x%02x,", (ae->mask >> 3) - 1);
627 32
                Fh(tl, 0, "0x%02x,", (0xff00 >> (ae->mask & 7)) & 0xff);
628 576
                for (sz = 0; sz < sizeof(ae->data); sz++)
629 544
                        Fh(tl, 0, "0x%02x,", ae->data[sz]);
630 32
                for (; sz < rv - 3; sz++)
631 0
                        Fh(tl, 0, "0,");
632 32
                Fh(tl, 0, "\n");
633 32
                nn++;
634 32
        }
635 8
        assert(n == nn);
636 8
        Fh(tl, 0, "};\n");
637 8
        if (tl->acl->flag_log) {
638 8
                Fh(tl, 0, "\nstatic const char *acl_str_%s[%d] = {\n",
639 4
                    name, n);
640 92
                VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
641 88
                        if (ae->overlapped)
642 72
                                continue;
643 16
                        Fh(tl, 0, "\t");
644 32
                        Fh(tl, 0, "\"%sMATCH %s \" ",
645 16
                            ae->not ? "NEG_" : "", name);
646 16
                        vcc_acl_emit_tokens(tl, ae);
647 16
                        Fh(tl, 0, ",\n");
648 16
                }
649 4
                Fh(tl, 0, "};\n");
650 4
        }
651 8
        return (rv);
652
}
653
654
/*********************************************************************
655
 * Emit a function to match the ACL we have collected
656
 */
657
658
static void
659 136
vcc_acl_emit(struct vcc *tl, const struct symbol *sym)
660
{
661
        struct acl_e *ae, *ae2;
662
        int depth, l, m, i;
663
        unsigned at[ACL_MAXADDR];
664 136
        struct inifin *ifp = NULL;
665
        struct vsb *func;
666 136
        unsigned n, no, nw = 0;
667
668 136
        func = VSB_new_auto();
669 136
        AN(func);
670 136
        VSB_cat(func, "match_acl_");
671 136
        VCC_PrintCName(func, sym->name, NULL);
672 136
        AZ(VSB_finish(func));
673
674 136
        depth = -1;
675 136
        at[0] = 256;
676 136
        ae2 = NULL;
677 136
        n = no = 0;
678 712
        VRBT_FOREACH_REVERSE(ae, acl_tree, &tl->acl->acl_tree) {
679 576
                n++;
680 576
                if (ae2 == NULL) {
681 132
                        ae2 = ae;
682 576
                } else if (vcl_acl_disjoint(ae, ae2)) {
683 164
                        ae2 = ae;
684 164
                } else {
685 280
                        no++;
686 280
                        ae->overlapped = 1;
687
                }
688 576
        }
689
690 136
        Fh(tl, 0, "/* acl_n_%s n %u no %u */\n", sym->name, n, no);
691 136
        if (n - no < (1<<1))
692 72
                no = n;
693 64
        else if (!tl->acl->flag_table)
694 56
                no = n;
695
696 136
        if (no < n)
697 8
                nw = vcc_acl_emit_tables(tl, n - no, sym->name);
698
699
700 136
        Fh(tl, 0, "\nstatic int v_matchproto_(acl_match_f)\n");
701 136
        Fh(tl, 0, "%s(VRT_CTX, const VCL_IP p)\n", VSB_data(func));
702 136
        Fh(tl, 0, "{\n");
703 136
        Fh(tl, 0, "\tconst unsigned char *a;\n");
704 136
        Fh(tl, 0, "\tint fam;\n");
705 136
        Fh(tl, 0, "\n");
706 136
        Fh(tl, 0, "\tfam = VRT_VSA_GetPtr(ctx, p, &a);\n");
707 136
        Fh(tl, 0, "\tif (fam < 0) {\n");
708 136
        Fh(tl, 0, "\t\tVRT_fail(ctx,");
709 136
        Fh(tl, 0, " \"ACL %s: no protocol family\");\n", sym->name);
710 136
        Fh(tl, 0, "\t\treturn(0);\n");
711 136
        Fh(tl, 0, "\t}\n\n");
712 136
        if (!tl->err_unref) {
713 8
                ifp = New_IniFin(tl);
714 16
                VSB_printf(ifp->ini,
715 8
                        "\t(void)%s;\n", VSB_data(func));
716 8
        }
717
718 712
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
719
720 576
                if (no < n && !ae->overlapped)
721 32
                        continue;
722
723
                /* Find how much common prefix we have */
724 3024
                for (l = 0; l <= depth && l * 8 < (int)ae->mask - 7; l++) {
725 2676
                        assert(l >= 0);
726 2676
                        if (ae->data[l] != at[l])
727 196
                                break;
728 2480
                }
729
730
                /* Back down, if necessary */
731 1232
                while (l <= depth) {
732 688
                        Fh(tl, 0, "\t%*s}\n", -depth, "");
733 688
                        depth--;
734
                }
735
736 544
                m = (int)ae->mask;
737 544
                assert(m >= l*8);
738 544
                m -= l * 8;
739
740
                /* Do whole byte compares */
741 2100
                for (i = l; m >= 8; m -= 8, i++) {
742 1556
                        if (i == 0)
743 376
                                Fh(tl, 0, "\t%*s%sif (fam == %d) {\n",
744 188
                                    -i, "", "", ae->data[i]);
745
                        else
746 2736
                                Fh(tl, 0, "\t%*s%sif (a[%d] == %d) {\n",
747 1368
                                    -i, "", "", i - 1, ae->data[i]);
748 1556
                        at[i] = ae->data[i];
749 1556
                        depth = i;
750 1556
                }
751
752 544
                if (m > 0) {
753
                        // XXX can remove masking due to fixup
754
                        /* Do fractional byte compares */
755 600
                        Fh(tl, 0, "\t%*s%sif ((a[%d] & 0x%x) == %d) {\n",
756 300
                            -i, "", "", i - 1, (0xff00 >> m) & 0xff,
757 300
                            ae->data[i] & ((0xff00 >> m) & 0xff));
758 300
                        at[i] = 256;
759 300
                        depth = i;
760 300
                }
761
762 544
                i = ((int)ae->mask + 7) / 8;
763
764 544
                if (tl->acl->flag_log) {
765 400
                        Fh(tl, 0, "\t%*sVPI_acl_log(ctx, \"%sMATCH %s \" ",
766 200
                            -i, "", ae->not ? "NEG_" : "", sym->name);
767 200
                        vcc_acl_emit_tokens(tl, ae);
768 200
                        Fh(tl, 0, ");\n");
769 200
                }
770
771 544
                Fh(tl, 0, "\t%*sreturn (%d);\n", -i, "", ae->not ? 0 : 1);
772 544
        }
773
774
        /* Unwind */
775 1304
        for (; 0 <= depth; depth--)
776 1168
                Fh(tl, 0, "\t%*.*s}\n", depth, depth, "");
777
778 136
        if (no < n) {
779 8
                Fh(tl, 0, "\treturn(\n\t    VPI_acl_table(ctx,\n");
780 8
                Fh(tl, 0, "\t\tp,\n");
781 8
                Fh(tl, 0, "\t\t%u, %u,\n", n - no, nw);
782 8
                Fh(tl, 0, "\t\tacl_tbl_%s,\n", sym->name);
783 8
                if (tl->acl->flag_log)
784 4
                        Fh(tl, 0, "\t\tacl_str_%s,\n", sym->name);
785
                else
786 4
                        Fh(tl, 0, "\t\tNULL,\n");
787 8
                Fh(tl, 0, "\t\t\"NO MATCH %s\"\n\t    )\n\t);\n", sym->name);
788 8
        } else {
789
                /* Deny by default */
790 128
                if (tl->acl->flag_log)
791 40
                        Fh(tl, 0, "\tVPI_acl_log(ctx, \"NO_MATCH %s\");\n",
792 20
                            sym->name);
793 128
                Fh(tl, 0, "\treturn(0);\n");
794
        }
795 136
        Fh(tl, 0, "}\n");
796
797
        /* Emit the struct that will be referenced */
798 136
        Fh(tl, 0, "\nstatic const struct vrt_acl %s[] = {{\n", sym->rname);
799 136
        Fh(tl, 0, "\t.magic = VRT_ACL_MAGIC,\n");
800 136
        Fh(tl, 0, "\t.match = &%s,\n", VSB_data(func));
801 136
        Fh(tl, 0, "\t.name = \"%s\",\n", sym->name);
802 136
        Fh(tl, 0, "}};\n\n");
803 136
        if (!tl->err_unref) {
804 8
                AN(ifp);
805 8
                VSB_printf(ifp->ini, "\t(void)%s;", sym->rname);
806 8
        }
807 136
        VSB_destroy(&func);
808 136
}
809
810
static void
811 24
vcc_parseAclFold(struct vcc *tl, int sign)
812
{
813
        struct acl *acl;
814
815 24
        CHECK_OBJ_NOTNULL(tl, VCC_MAGIC);
816 24
        assert(vcc_IdIs(tl->t, "fold"));
817 24
        acl = tl->acl;
818 24
        CHECK_OBJ_NOTNULL(acl, VCC_ACL_MAGIC);
819
820 24
        acl->flag_fold = sign;
821 24
        acl->flag_fold_report = 1;
822 24
        vcc_NextToken(tl);
823 24
        if (tl->t->tok != '(')
824 12
                return;
825
826 12
        if (! acl->flag_fold) {
827 4
                VSB_cat(tl->sb, "-fold(...) is invalid, use -fold:\n");
828 4
                vcc_ErrWhere(tl, tl->t);
829 4
                return;
830
        }
831
832 8
        SkipToken(tl, '(');
833
834
#define FOLD_SUBFLAGS_MSG "The only ACL fold sub-flag is `report`:\n"
835
836 8
        sign = vcc_IsFlag(tl);
837 8
        if (tl->err) {
838 0
                VSB_cat(tl->sb, FOLD_SUBFLAGS_MSG);
839 0
                return;
840
        }
841 8
        if (sign < 0)
842 0
                return;
843
844 8
        if (! vcc_IdIs(tl->t, "report")) {
845 4
                VSB_cat(tl->sb, FOLD_SUBFLAGS_MSG);
846 4
                vcc_ErrWhere(tl, tl->t);
847 4
                return;
848
        }
849
850 4
        acl->flag_fold_report = sign;
851
852 4
        vcc_NextToken(tl);
853 4
        SkipToken(tl, ')');
854 24
}
855
856
void
857 204
vcc_ParseAcl(struct vcc *tl)
858
{
859
        struct symbol *sym;
860
        int sign;
861
        struct acl acl[1];
862
863 204
        INIT_OBJ(acl, VCC_ACL_MAGIC);
864 204
        tl->acl = acl;
865 204
        acl->flag_pedantic = 1;
866 204
        acl->flag_fold = 1;
867 204
        acl->flag_fold_report = 1;
868 204
        vcc_NextToken(tl);
869 204
        VRBT_INIT(&acl->acl_tree);
870
871 204
        vcc_ExpectVid(tl, "ACL");
872 204
        ERRCHK(tl);
873 200
        sym = VCC_HandleSymbol(tl, ACL);
874 200
        ERRCHK(tl);
875 200
        AN(sym);
876
877
#define FLAGS_MSG "Valid ACL flags are `log`, `fold`, `pedantic` and `table`:\n"
878
879 300
        while (1) {
880 300
                sign = vcc_IsFlag(tl);
881 300
                if (tl->err) {
882 4
                        VSB_cat(tl->sb, FLAGS_MSG);
883 4
                        return;
884
                }
885 296
                if (sign < 0)
886 184
                        break;
887 112
                if (vcc_IdIs(tl->t, "log")) {
888 32
                        acl->flag_log = sign;
889 32
                        vcc_NextToken(tl);
890 112
                } else if (vcc_IdIs(tl->t, "fold")) {
891 24
                        vcc_parseAclFold(tl, sign);
892 24
                        if (tl->err)
893 8
                                return;
894 72
                } else if (vcc_IdIs(tl->t, "pedantic")) {
895 44
                        acl->flag_pedantic = sign;
896 44
                        vcc_NextToken(tl);
897 56
                } else if (vcc_IdIs(tl->t, "table")) {
898 8
                        acl->flag_table = sign;
899 8
                        vcc_NextToken(tl);
900 8
                } else {
901 4
                        VSB_cat(tl->sb, "Unknown ACL flag. " FLAGS_MSG);
902 4
                        vcc_ErrWhere(tl, tl->t);
903 4
                        return;
904
                }
905
        }
906
907
#undef FLAGS_MSG
908
909 184
        SkipToken(tl, '{');
910
911 900
        while (tl->t->tok != '}') {
912 764
                vcc_acl_entry(tl);
913 764
                ERRCHK(tl);
914 720
                SkipToken(tl, ';');
915
        }
916 136
        SkipToken(tl, '}');
917
918 136
        vcc_acl_emit(tl, sym);
919 204
}