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 42
vcl_acl_free(struct acl_e **aep)
112
{
113
        struct acl_e *a;
114
115 42
        TAKE_OBJ_NOTNULL(a, aep, VCC_ACL_E_MAGIC);
116 42
        free(a->addr);
117 42
        FREE_OBJ(a);
118 42
}
119
120
static enum acl_cmp_e
121 11697
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 11697
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
128 11697
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
129
130 11697
        p1 = ae1->data;
131 11697
        p2 = ae2->data;
132 11697
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
133 60522
        for (; m >= 8; m -= 8) {
134 55377
                if (m == 8 && ae1->mask == ae2->mask)
135 1197
                        CMPA(*p1, *p2);
136 103761
                CMP(ACL_GT, *p1, *p2);
137 48825
                p1++;
138 48825
                p2++;
139 48825
        }
140 5145
        if (m) {
141 5019
                assert (m < 8);
142 5019
                a1 = *p1 >> (8 - m);
143 5019
                a2 = *p2 >> (8 - m);
144 5019
                if (ae1->mask == ae2->mask)
145 1533
                        CMPA(a1, a2);
146 6783
                CMP(ACL_GT, a1, a2);
147 2289
        } else if (ae1->mask == ae2->mask) {
148 42
                CMPA(*p1, *p2);
149 21
        }
150
        /* Long mask is less than short mask */
151 2331
        CMP(ACL_CONTAINS, ae2->mask, ae1->mask);
152
153 42
        return (ACL_EQ);
154 11697
}
155
156
static int
157 2352
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 2352
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
163 2352
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
164
165 2352
        p1 = ae1->data;
166 2352
        p2 = ae2->data;
167 2352
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
168 16947
        for (; m >= 8; m -= 8) {
169 29862
                CMP(ACL_GT, *p1, *p2);
170 14595
                p1++;
171 14595
                p2++;
172 14595
        }
173 1680
        if (m) {
174 1512
                m = 0xff00 >> m;
175 1512
                m &= 0xff;
176 2814
                CMP(ACL_GT, *p1 & m, *p2 & m);
177 1302
        }
178 1470
        return (0);
179 2352
}
180
181 7875
VRBT_GENERATE_INSERT_COLOR(acl_tree, acl_e, branch, static)
182 4158
VRBT_GENERATE_INSERT_FINISH(acl_tree, acl_e, branch, static)
183 13566
VRBT_GENERATE_INSERT(acl_tree, acl_e, branch, vcl_acl_cmp, static)
184 987
VRBT_GENERATE_REMOVE_COLOR(acl_tree, acl_e, branch, static)
185 1827
VRBT_GENERATE_REMOVE(acl_tree, acl_e, branch, static)
186 4347
VRBT_GENERATE_MINMAX(acl_tree, acl_e, branch, static)
187 13230
VRBT_GENERATE_NEXT(acl_tree, acl_e, branch, static)
188 10332
VRBT_GENERATE_PREV(acl_tree, acl_e, branch, static)
189
190
static char *
191 3927
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 3927
        char s[vsa_suckaddr_len];
198 3927
        char *r = NULL;
199
        const struct suckaddr *sa;
200
        unsigned m;
201 3927
        int ll, ret = 0;
202
203 3927
        u = p;
204 3927
        ll = l;
205 3927
        m = ae->mask;
206
207 3927
        p += m / 8;
208 3927
        ll -= m / 8;
209 3927
        assert (ll >= 0);
210 3927
        m %= 8;
211
212 3927
        if (m && ((unsigned)*p << m & 0xff) != 0) {
213 84
                ret = 1;
214 84
                m = 0xff00 >> m;
215 84
                *p &= m;
216 84
        }
217 3927
        if (m) {
218 2100
                p++;
219 2100
                ll--;
220 2100
        }
221
222 7308
        for ( ; ll > 0; p++, ll--) {
223 3381
                if (*p == 0)
224 3276
                        continue;
225 105
                ret = 1;
226 105
                *p = 0;
227 105
        }
228 3927
        if (ret == 0)
229 3738
                return (NULL);
230
231 189
        sa = VSA_BuildFAP(s, fam, u, l, NULL, 0);
232 189
        AN(sa);
233 189
        VTCP_name(sa, h, sizeof h, NULL, 0);
234 189
        bprintf(t, "%s/%d", h, ae->mask);
235 189
        if (tl->acl->flag_pedantic != 0) {
236 42
                VSB_cat(tl->sb, "Non-zero bits in masked part, ");
237 42
                VSB_printf(tl->sb, "(maybe use %s ?)\n", t);
238 42
                vcc_ErrWhere(tl, ae->t_addr);
239 42
        }
240 189
        REPLACE(r, t);
241 189
        return (r);
242 3927
}
243
244
static void
245 4263
vcl_acl_fold(struct vcc *tl, struct acl_e **l, struct acl_e **r)
246
{
247
        enum acl_cmp_e cmp;
248
249 4263
        AN(l);
250 4263
        AN(r);
251 4263
        CHECK_OBJ_NOTNULL(*l, VCC_ACL_E_MAGIC);
252 4263
        CHECK_OBJ_NOTNULL(*r, VCC_ACL_E_MAGIC);
253
254 4263
        if ((*l)->not || (*r)->not)
255 2142
                return;
256
257 2121
        cmp = vcl_acl_cmp(*l, *r);
258
259 2121
        assert(cmp < 0);
260 2121
        if (cmp == ACL_LT)
261 1407
                return;
262
263 714
        do {
264 735
                switch (cmp) {
265
                case ACL_CONTAINED:
266 462
                        if (tl->acl->flag_fold_report) {
267 462
                                VSB_cat(tl->sb, "ACL entry:\n");
268 462
                                vcc_ErrWhere(tl, (*r)->t_addr);
269 462
                                VSB_cat(tl->sb, "supersedes / removes:\n");
270 462
                                vcc_ErrWhere(tl, (*l)->t_addr);
271 462
                                vcc_Warn(tl);
272 462
                        }
273 462
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
274 462
                        FREE_OBJ(*l);
275 462
                        *l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, *r);
276 462
                        break;
277
                case ACL_LEFT:
278 273
                        (*l)->mask--;
279 273
                        (*l)->fixed = "folded";
280 273
                        if (tl->acl->flag_fold_report) {
281 231
                                VSB_cat(tl->sb, "ACL entry:\n");
282 231
                                vcc_ErrWhere(tl, (*l)->t_addr);
283 231
                                VSB_cat(tl->sb, "left of:\n");
284 231
                                vcc_ErrWhere(tl, (*r)->t_addr);
285 462
                                VSB_printf(tl->sb, "removing the latter and "
286
                                    "expanding mask of the former by one to "
287 231
                                    "/%u\n", (*l)->mask - 8);
288 231
                                vcc_Warn(tl);
289 231
                        }
290 273
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *r);
291 273
                        FREE_OBJ(*r);
292 273
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
293 273
                        vcc_acl_insert_entry(tl, l);
294 273
                        return;
295
                default:
296 0
                        INCOMPL();
297 0
                }
298 462
                if (*l == NULL || *r == NULL || (*l)->not || (*r)->not)
299 294
                        break;
300 168
                cmp = vcl_acl_cmp(*l, *r);
301 168
        } while (cmp != ACL_LT);
302 4263
}
303
304
static void
305 4200
vcc_acl_insert_entry(struct vcc *tl, struct acl_e **aenp)
306
{
307
        struct acl_e *ae2, *l, *r;
308
309 4200
        CHECK_OBJ_NOTNULL(*aenp, VCC_ACL_E_MAGIC);
310 4200
        ae2 = VRBT_INSERT(acl_tree, &tl->acl->acl_tree, *aenp);
311 4200
        if (ae2 != NULL) {
312 42
                if (ae2->not != (*aenp)->not) {
313 21
                        VSB_cat(tl->sb, "Conflicting ACL entries:\n");
314 21
                        vcc_ErrWhere(tl, ae2->t_addr);
315 21
                        VSB_cat(tl->sb, "vs:\n");
316 21
                        vcc_ErrWhere(tl, (*aenp)->t_addr);
317 21
                }
318 42
                return;
319
        }
320
321 4158
        r = *aenp;
322 4158
        *aenp = NULL;
323
324 4158
        if (tl->acl->flag_fold == 0)
325 441
                return;
326
327 3717
        l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, r);
328 3717
        if (l != NULL) {
329 2625
                vcl_acl_fold(tl, &l, &r);
330 2625
        }
331 3717
        if (r == NULL)
332 210
                return;
333 3507
        l = r;
334 3507
        r = VRBT_NEXT(acl_tree, &tl->acl->acl_tree, l);
335 3507
        if (r == NULL)
336 1869
                return;
337 1638
        vcl_acl_fold(tl, &l, &r);
338 4200
}
339
340
static void
341 3969
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 3969
        if (fam == PF_INET && ae->mask > 32) {
347 42
                VSB_printf(tl->sb,
348 21
                    "Too wide mask (/%u) for IPv4 address\n", ae->mask);
349 21
                if (ae->t_mask != NULL)
350 21
                        vcc_ErrWhere(tl, ae->t_mask);
351
                else
352 0
                        vcc_ErrWhere(tl, ae->t_addr);
353 21
                return;
354
        }
355 3948
        if (fam == PF_INET6 && ae->mask > 128) {
356 42
                VSB_printf(tl->sb,
357 21
                    "Too wide mask (/%u) for IPv6 address\n", ae->mask);
358 21
                vcc_ErrWhere(tl, ae->t_mask);
359 21
                return;
360
        }
361
362
        /* Make a copy from the template */
363 3927
        ALLOC_OBJ(aen, VCC_ACL_E_MAGIC);
364 3927
        AN(aen);
365 3927
        *aen = *ae;
366 3927
        aen->addr = strdup(ae->addr);
367 3927
        AN(aen->addr);
368
369 3927
        aen->fixed = vcc_acl_chk(tl, ae, l, u, fam);
370
371
        /* We treat family as part of address, it saves code */
372 3927
        assert(fam <= 0xff);
373 3927
        aen->data[0] = fam & 0xff;
374 3927
        aen->mask += 8;
375
376 3927
        assert(l + 1UL <= sizeof aen->data);
377 3927
        vmemcpy(aen->data + 1L, u, l);
378
379 3927
        vcc_acl_insert_entry(tl, &aen);
380 3927
        if (aen != NULL)
381 42
                vcl_acl_free(&aen);
382 3969
}
383
384
static void
385 1260
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 1260
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
394 1260
        memset(&hint, 0, sizeof hint);
395 1260
        hint.ai_family = PF_UNSPEC;
396 1260
        hint.ai_socktype = SOCK_STREAM;
397 1260
        error = getaddrinfo(ae->addr, "0", &hint, &res0);
398 1260
        if (error) {
399 84
                if (ae->para) {
400 84
                        VSB_printf(tl->sb,
401
                            "Warning: %s ignored\n  -- %s\n",
402 42
                            ae->addr, gai_strerror(error));
403 84
                        Fh(tl, 1, "/* Ignored ACL entry: %s%s",
404 42
                            ae->para ? "\"(\" " : "", ae->not ? "\"!\" " : "");
405 42
                        EncToken(tl->fh, ae->t_addr);
406 42
                        if (ae->t_mask)
407 21
                                Fh(tl, 0, "/%u", ae->mask);
408 42
                        Fh(tl, 0, "%s\n", ae->para ? " \")\"" : "");
409 84
                        Fh(tl, 1, " * getaddrinfo:  %s */\n",
410 42
                             gai_strerror(error));
411 42
                } else {
412 84
                        VSB_printf(tl->sb,
413
                            "DNS lookup(%s): %s\n",
414 42
                            ae->addr, gai_strerror(error));
415 42
                        vcc_ErrWhere(tl, ae->t_addr);
416
                }
417 84
                return;
418
        }
419
420 1176
        i4 = i6 = 0;
421 2436
        for (res = res0; res != NULL; res = res->ai_next) {
422 1260
                switch (res->ai_family) {
423
                case PF_INET:
424 84
                        i4++;
425 84
                        break;
426
                case PF_INET6:
427 1176
                        i6++;
428 1176
                        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 1260
        }
436
437 1176
        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 2394
        for (res = res0; res != NULL; res = res->ai_next) {
447 1260
                switch (res->ai_family) {
448
                case PF_INET:
449 84
                        assert(PF_INET < 256);
450 84
                        sin4 = (void*)res->ai_addr;
451 84
                        assert(sizeof(sin4->sin_addr) == 4);
452 84
                        u = (void*)&sin4->sin_addr;
453 84
                        if (ae->t_mask == NULL)
454 84
                                ae->mask = 32;
455 84
                        vcc_acl_add_entry(tl, ae, 4, u, res->ai_family);
456 84
                        break;
457
                case PF_INET6:
458 1176
                        assert(PF_INET6 < 256);
459 1176
                        sin6 = (void*)res->ai_addr;
460 1176
                        assert(sizeof(sin6->sin6_addr) == 16);
461 1176
                        u = (void*)&sin6->sin6_addr;
462 1176
                        if (ae->t_mask == NULL)
463 231
                                ae->mask = 128;
464 1176
                        vcc_acl_add_entry(tl, ae, 16, u, res->ai_family);
465 1176
                        break;
466
                default:
467 0
                        continue;
468
                }
469 1260
                if (tl->err)
470 42
                        freeaddrinfo(res0);
471 1260
                ERRCHK(tl);
472 1218
        }
473 1134
        freeaddrinfo(res0);
474
475 1260
}
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 3969
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 3969
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
493 3969
        memset(b, 0, sizeof b);
494 3969
        p = ae->addr;
495 11613
        for (i = 0; i < 4; i++) {
496 11613
                j = sscanf(p, "%u%n", &u, &k);
497 11613
                if (j != 1)
498 1155
                        return (0);
499 10458
                if (u & ~0xff)
500 42
                        return (0);
501 10416
                b[i] = (unsigned char)u;
502 10416
                if (p[k] == '\0')
503 2709
                        break;
504 7707
                if (p[k] != '.')
505 63
                        return (0);
506 7644
                p += k + 1;
507 7644
        }
508 2709
        if (ae->t_mask == NULL)
509 609
                ae->mask = 8 + 8 * i;
510 2709
        vcc_acl_add_entry(tl, ae, 4, b, AF_INET);
511 2709
        return (1);
512 3969
}
513
514
static void
515 4053
vcc_acl_entry(struct vcc *tl)
516
{
517
        struct acl_e ae[1];
518
        char *sl, *e;
519
520 4053
        INIT_OBJ(ae, VCC_ACL_E_MAGIC);
521
522 4053
        if (tl->t->tok == '!') {
523 882
                ae->not = 1;
524 882
                vcc_NextToken(tl);
525 882
        }
526
527 4053
        if (tl->t->tok == '(') {
528 63
                ae->para = 1;
529 63
                vcc_NextToken(tl);
530 63
        }
531
532 4053
        if (!ae->not && tl->t->tok == '!') {
533 21
                ae->not = 1;
534 21
                vcc_NextToken(tl);
535 21
        }
536
537 4053
        ExpectErr(tl, CSTR);
538 4053
        ae->t_addr = tl->t;
539 4053
        ae->addr = ae->t_addr->dec;
540 4053
        vcc_NextToken(tl);
541
542 4053
        if (strchr(ae->t_addr->dec, '/') != NULL) {
543 105
                sl = strchr(ae->addr, '/');
544 105
                AN(sl);
545 105
                *sl++ = '\0';
546 105
                e = NULL;
547 105
                ae->mask = strtoul(sl, &e, 10);
548 105
                if (*e != '\0') {
549 42
                        VSB_cat(tl->sb, ".../mask is not numeric.\n");
550 42
                        vcc_ErrWhere(tl, ae->t_addr);
551 42
                        return;
552
                }
553 63
                ae->t_mask = ae->t_addr;
554 63
                if (tl->t->tok == '/') {
555 21
                        VSB_cat(tl->sb, "/mask only allowed once.\n");
556 21
                        vcc_ErrWhere(tl, tl->t);
557 21
                        return;
558
                }
559 3990
        } else if (tl->t->tok == '/') {
560 3024
                vcc_NextToken(tl);
561 3024
                ae->t_mask = tl->t;
562 3024
                ExpectErr(tl, CNUM);
563 3024
                ae->mask = vcc_UintVal(tl);
564 3024
        }
565
566 3990
        if (ae->para)
567 63
                SkipToken(tl, ')');
568
569 3969
        if (!vcc_acl_try_netnotation(tl, ae)) {
570 1260
                ERRCHK(tl);
571 1260
                vcc_acl_try_getaddrinfo(tl, ae);
572 1260
        }
573 3969
        ERRCHK(tl);
574 4053
}
575
576
/*********************************************************************
577
 * Emit the tokens making up an entry as C-strings
578
 */
579
580
static void
581 1134
vcc_acl_emit_tokens(const struct vcc *tl, const struct acl_e *ae)
582
{
583
        struct token *t;
584 1134
        const char *sep = "";
585
586 1134
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
587 1134
        t = ae->t_addr;
588 1134
        do {
589 3318
                if (t->tok == CSTR) {
590 1134
                        Fh(tl, 0, "%s\"\\\"\" ", sep);
591 1134
                        EncToken(tl->fh, t);
592 1134
                        Fh(tl, 0, " \"\\\"\"");
593 3318
                } else if (t == ae->t_mask) {
594 1092
                        Fh(tl, 0, " \"%u\"", ae->mask - 8);
595 1092
                } else {
596 1092
                        Fh(tl, 0, "%s\"%.*s\"", sep, PF(t));
597
                }
598 3318
                if (t == ae->t_mask)
599 1092
                        break;
600 2226
                t = vcc_PeekTokenFrom(tl, t);
601 2226
                AN(t);
602 2226
                sep = " ";
603 2226
        } while (ae->t_mask != NULL);
604 1134
        if (ae->fixed)
605 231
                Fh(tl, 0, "\" fixed: %s\"", ae->fixed);
606 1134
}
607
608
/*********************************************************************
609
 * Emit ACL on table format
610
 */
611
612
static unsigned
613 63
vcc_acl_emit_tables(const struct vcc *tl, unsigned n, const char *name)
614
{
615
        struct acl_e *ae;
616 63
        unsigned rv = sizeof(ae->data) + 3;
617 63
        unsigned nn = 0;
618
        size_t sz;
619
620 126
        Fh(tl, 0, "\nstatic unsigned char acl_tbl_%s[%u*%u] = {\n",
621 63
            name, n, rv);
622 1029
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
623 966
                if (ae->overlapped)
624 756
                        continue;
625 210
                Fh(tl, 0, "\t0x%02x,", ae->not ? 0 : 1);
626 210
                Fh(tl, 0, "0x%02x,", (ae->mask >> 3) - 1);
627 210
                Fh(tl, 0, "0x%02x,", (0xff00 >> (ae->mask & 7)) & 0xff);
628 3780
                for (sz = 0; sz < sizeof(ae->data); sz++)
629 3570
                        Fh(tl, 0, "0x%02x,", ae->data[sz]);
630 210
                for (; sz < rv - 3; sz++)
631 0
                        Fh(tl, 0, "0,");
632 210
                Fh(tl, 0, "\n");
633 210
                nn++;
634 210
        }
635 63
        assert(n == nn);
636 63
        Fh(tl, 0, "};\n");
637 63
        if (tl->acl->flag_log) {
638 42
                Fh(tl, 0, "\nstatic const char *acl_str_%s[%d] = {\n",
639 21
                    name, n);
640 483
                VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
641 462
                        if (ae->overlapped)
642 378
                                continue;
643 84
                        Fh(tl, 0, "\t");
644 168
                        Fh(tl, 0, "\"%sMATCH %s \" ",
645 84
                            ae->not ? "NEG_" : "", name);
646 84
                        vcc_acl_emit_tokens(tl, ae);
647 84
                        Fh(tl, 0, ",\n");
648 84
                }
649 21
                Fh(tl, 0, "};\n");
650 21
        }
651 63
        return (rv);
652
}
653
654
/*********************************************************************
655
 * Emit a function to match the ACL we have collected
656
 */
657
658
static void
659 735
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 735
        struct inifin *ifp = NULL;
665
        struct vsb *func;
666 735
        unsigned n, no, nw = 0;
667
668 735
        func = VSB_new_auto();
669 735
        AN(func);
670 735
        VSB_cat(func, "match_acl_");
671 735
        VCC_PrintCName(func, sym->name, NULL);
672 735
        AZ(VSB_finish(func));
673
674 735
        depth = -1;
675 735
        at[0] = 256;
676 735
        ae2 = NULL;
677 735
        n = no = 0;
678 3801
        VRBT_FOREACH_REVERSE(ae, acl_tree, &tl->acl->acl_tree) {
679 3066
                n++;
680 3066
                if (ae2 == NULL) {
681 714
                        ae2 = ae;
682 3066
                } else if (vcl_acl_disjoint(ae, ae2)) {
683 882
                        ae2 = ae;
684 882
                } else {
685 1470
                        no++;
686 1470
                        ae->overlapped = 1;
687
                }
688 3066
        }
689
690 735
        Fh(tl, 0, "/* acl_n_%s n %u no %u */\n", sym->name, n, no);
691 735
        if (n - no < (1<<1))
692 378
                no = n;
693 357
        else if (!tl->acl->flag_table)
694 294
                no = n;
695
696 735
        if (no < n)
697 63
                nw = vcc_acl_emit_tables(tl, n - no, sym->rname);
698
699
700 735
        Fh(tl, 0, "\nstatic int v_matchproto_(acl_match_f)\n");
701 735
        Fh(tl, 0, "%s(VRT_CTX, const VCL_IP p)\n", VSB_data(func));
702 735
        Fh(tl, 0, "{\n");
703 735
        Fh(tl, 0, "\tconst unsigned char *a;\n");
704 735
        Fh(tl, 0, "\tint fam;\n");
705 735
        Fh(tl, 0, "\n");
706 735
        Fh(tl, 0, "\tfam = VRT_VSA_GetPtr(ctx, p, &a);\n");
707 735
        Fh(tl, 0, "\tif (fam < 0) {\n");
708 735
        Fh(tl, 0, "\t\tVRT_fail(ctx,");
709 735
        Fh(tl, 0, " \"ACL %s: no protocol family\");\n", sym->name);
710 735
        Fh(tl, 0, "\t\treturn(0);\n");
711 735
        Fh(tl, 0, "\t}\n\n");
712 735
        if (!tl->err_unref) {
713 42
                ifp = New_IniFin(tl);
714 84
                VSB_printf(ifp->ini,
715 42
                        "\t(void)%s;\n", VSB_data(func));
716 42
        }
717
718 3801
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
719
720 3066
                if (no < n && !ae->overlapped)
721 210
                        continue;
722
723
                /* Find how much common prefix we have */
724 15876
                for (l = 0; l <= depth && l * 8 < (int)ae->mask - 7; l++) {
725 14049
                        assert(l >= 0);
726 14049
                        if (ae->data[l] != at[l])
727 1029
                                break;
728 13020
                }
729
730
                /* Back down, if necessary */
731 6468
                while (l <= depth) {
732 3612
                        Fh(tl, 0, "\t%*s}\n", -depth, "");
733 3612
                        depth--;
734
                }
735
736 2856
                m = (int)ae->mask;
737 2856
                assert(m >= l*8);
738 2856
                m -= l * 8;
739
740
                /* Do whole byte compares */
741 11025
                for (i = l; m >= 8; m -= 8, i++) {
742 8169
                        if (i == 0)
743 1974
                                Fh(tl, 0, "\t%*s%sif (fam == %d) {\n",
744 987
                                    -i, "", "", ae->data[i]);
745
                        else
746 14364
                                Fh(tl, 0, "\t%*s%sif (a[%d] == %d) {\n",
747 7182
                                    -i, "", "", i - 1, ae->data[i]);
748 8169
                        at[i] = ae->data[i];
749 8169
                        depth = i;
750 8169
                }
751
752 2856
                if (m > 0) {
753
                        // XXX can remove masking due to fixup
754
                        /* Do fractional byte compares */
755 3150
                        Fh(tl, 0, "\t%*s%sif ((a[%d] & 0x%x) == %d) {\n",
756 1575
                            -i, "", "", i - 1, (0xff00 >> m) & 0xff,
757 1575
                            ae->data[i] & ((0xff00 >> m) & 0xff));
758 1575
                        at[i] = 256;
759 1575
                        depth = i;
760 1575
                }
761
762 2856
                i = ((int)ae->mask + 7) / 8;
763
764 2856
                if (tl->acl->flag_log) {
765 2100
                        Fh(tl, 0, "\t%*sVPI_acl_log(ctx, \"%sMATCH %s \" ",
766 1050
                            -i, "", ae->not ? "NEG_" : "", sym->name);
767 1050
                        vcc_acl_emit_tokens(tl, ae);
768 1050
                        Fh(tl, 0, ");\n");
769 1050
                }
770
771 2856
                Fh(tl, 0, "\t%*sreturn (%d);\n", -i, "", ae->not ? 0 : 1);
772 2856
        }
773
774
        /* Unwind */
775 6867
        for (; 0 <= depth; depth--)
776 6132
                Fh(tl, 0, "\t%*.*s}\n", depth, depth, "");
777
778 735
        if (no < n) {
779 63
                Fh(tl, 0, "\treturn(\n\t    VPI_acl_table(ctx,\n");
780 63
                Fh(tl, 0, "\t\tp,\n");
781 63
                Fh(tl, 0, "\t\t%u, %u,\n", n - no, nw);
782 63
                Fh(tl, 0, "\t\tacl_tbl_%s,\n", sym->rname);
783 63
                if (tl->acl->flag_log)
784 21
                        Fh(tl, 0, "\t\tacl_str_%s,\n", sym->rname);
785
                else
786 42
                        Fh(tl, 0, "\t\tNULL,\n");
787 63
                Fh(tl, 0, "\t\t\"NO MATCH %s\"\n\t    )\n\t);\n", sym->name);
788 63
        } else {
789
                /* Deny by default */
790 672
                if (tl->acl->flag_log)
791 210
                        Fh(tl, 0, "\tVPI_acl_log(ctx, \"NO_MATCH %s\");\n",
792 105
                            sym->name);
793 672
                Fh(tl, 0, "\treturn(0);\n");
794
        }
795 735
        Fh(tl, 0, "}\n");
796
797
        /* Emit the struct that will be referenced */
798 735
        Fh(tl, 0, "\nstatic const struct vrt_acl %s[] = {{\n", sym->rname);
799 735
        Fh(tl, 0, "\t.magic = VRT_ACL_MAGIC,\n");
800 735
        Fh(tl, 0, "\t.match = &%s,\n", VSB_data(func));
801 735
        Fh(tl, 0, "\t.name = \"%s\",\n", sym->name);
802 735
        Fh(tl, 0, "}};\n\n");
803 735
        if (!tl->err_unref) {
804 42
                AN(ifp);
805 42
                VSB_printf(ifp->ini, "\t(void)%s;", sym->rname);
806 42
        }
807 735
        VSB_destroy(&func);
808 735
}
809
810
static void
811 126
vcc_parseAclFold(struct vcc *tl, int sign)
812
{
813
        struct acl *acl;
814
815 126
        CHECK_OBJ_NOTNULL(tl, VCC_MAGIC);
816 126
        assert(vcc_IdIs(tl->t, "fold"));
817 126
        acl = tl->acl;
818 126
        CHECK_OBJ_NOTNULL(acl, VCC_ACL_MAGIC);
819
820 126
        acl->flag_fold = sign;
821 126
        acl->flag_fold_report = 1;
822 126
        vcc_NextToken(tl);
823 126
        if (tl->t->tok != '(')
824 63
                return;
825
826 63
        if (! acl->flag_fold) {
827 21
                VSB_cat(tl->sb, "-fold(...) is invalid, use -fold:\n");
828 21
                vcc_ErrWhere(tl, tl->t);
829 21
                return;
830
        }
831
832 42
        SkipToken(tl, '(');
833
834
#define FOLD_SUBFLAGS_MSG "The only ACL fold sub-flag is `report`:\n"
835
836 42
        sign = vcc_IsFlag(tl);
837 42
        if (tl->err) {
838 0
                VSB_cat(tl->sb, FOLD_SUBFLAGS_MSG);
839 0
                return;
840
        }
841 42
        if (sign < 0)
842 0
                return;
843
844 42
        if (! vcc_IdIs(tl->t, "report")) {
845 21
                VSB_cat(tl->sb, FOLD_SUBFLAGS_MSG);
846 21
                vcc_ErrWhere(tl, tl->t);
847 21
                return;
848
        }
849
850 21
        acl->flag_fold_report = sign;
851
852 21
        vcc_NextToken(tl);
853 21
        SkipToken(tl, ')');
854 126
}
855
856
void
857 1092
vcc_ParseAcl(struct vcc *tl)
858
{
859
        struct symbol *sym;
860
        int sign;
861
        struct acl acl[1];
862
863 1092
        INIT_OBJ(acl, VCC_ACL_MAGIC);
864 1092
        tl->acl = acl;
865 1092
        acl->flag_pedantic = 1;
866 1092
        acl->flag_fold = 1;
867 1092
        acl->flag_fold_report = 1;
868 1092
        vcc_NextToken(tl);
869 1092
        VRBT_INIT(&acl->acl_tree);
870
871 1092
        vcc_ExpectVid(tl, "ACL");
872 1092
        ERRCHK(tl);
873 1071
        sym = VCC_HandleSymbol(tl, ACL);
874 1071
        ERRCHK(tl);
875 1071
        AN(sym);
876
877
#define FLAGS_MSG "Valid ACL flags are `log`, `fold`, `pedantic` and `table`:\n"
878
879 1617
        while (1) {
880 1617
                sign = vcc_IsFlag(tl);
881 1617
                if (tl->err) {
882 21
                        VSB_cat(tl->sb, FLAGS_MSG);
883 21
                        return;
884
                }
885 1596
                if (sign < 0)
886 987
                        break;
887 609
                if (vcc_IdIs(tl->t, "log")) {
888 168
                        acl->flag_log = sign;
889 168
                        vcc_NextToken(tl);
890 609
                } else if (vcc_IdIs(tl->t, "fold")) {
891 126
                        vcc_parseAclFold(tl, sign);
892 126
                        if (tl->err)
893 42
                                return;
894 399
                } else if (vcc_IdIs(tl->t, "pedantic")) {
895 231
                        acl->flag_pedantic = sign;
896 231
                        vcc_NextToken(tl);
897 315
                } else if (vcc_IdIs(tl->t, "table")) {
898 63
                        acl->flag_table = sign;
899 63
                        vcc_NextToken(tl);
900 63
                } else {
901 21
                        VSB_cat(tl->sb, "Unknown ACL flag. " FLAGS_MSG);
902 21
                        vcc_ErrWhere(tl, tl->t);
903 21
                        return;
904
                }
905
        }
906
907
#undef FLAGS_MSG
908
909 987
        SkipToken(tl, '{');
910
911 4788
        while (tl->t->tok != '}') {
912 4053
                vcc_acl_entry(tl);
913 4053
                ERRCHK(tl);
914 3822
                SkipToken(tl, ';');
915
        }
916 735
        SkipToken(tl, '}');
917
918 735
        vcc_acl_emit(tl, sym);
919 1092
}