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