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_pedantic;
57
        int                     flag_table;
58
59
        struct acl_tree         acl_tree;
60
};
61
62
struct acl_e {
63
        unsigned                magic;
64
#define VCC_ACL_E_MAGIC 0xcac81e23
65
        VRBT_ENTRY(acl_e)       branch;
66
        unsigned char           data[ACL_MAXADDR];
67
        unsigned                mask;
68
        unsigned                not;
69
        unsigned                para;
70
        unsigned                overlapped;
71
        char                    *addr;
72
        const char              *fixed;
73
        struct token            *t_addr;
74
        struct token            *t_mask;
75
};
76
77
enum acl_cmp_e {
78
        ACL_EQ = 0,
79
        ACL_LT = -1,            // a < b
80
        ACL_GT = 1,             // b > a
81
        ACL_CONTAINED = -2,     // b contains a
82
        ACL_CONTAINS = 2,       // a contains b
83
        ACL_LEFT = -3,          // a + 1 == b
84
        ACL_RIGHT = 3           // a == b + 1
85
};
86
87
static void vcc_acl_insert_entry(struct vcc *, struct acl_e **);
88
89
/*
90
 * Compare two acl rules for relation
91
 */
92
93
#define CMP(n, a, b)                                                    \
94
        do {                                                            \
95
                if ((a) < (b))                                          \
96
                        return (enum acl_cmp_e)(-n);                    \
97
                else if ((b) < (a))                                     \
98
                        return (n);                                     \
99
        } while (0)
100
101
#define CMPA(a, b)                                                      \
102
        do {                                                            \
103
                if (((a) | 1) == (b))                                   \
104
                        return (ACL_LEFT);                              \
105
                else if (((b) | 1) == (a))                              \
106
                        return (ACL_RIGHT);                             \
107
        } while (0)
108
109
static void
110 240
vcl_acl_free(struct acl_e **aep)
111
{
112
        struct acl_e *a;
113
114 240
        TAKE_OBJ_NOTNULL(a, aep, VCC_ACL_E_MAGIC);
115 240
        free(a->addr);
116 240
        FREE_OBJ(a);
117 240
}
118
119
static enum acl_cmp_e
120 22000
vcl_acl_cmp(const struct acl_e *ae1, const struct acl_e *ae2)
121
{
122
        const unsigned char *p1, *p2;
123
        unsigned m;
124
        unsigned char a1, a2;
125
126 22000
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
127 22000
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
128
129 22000
        p1 = ae1->data;
130 22000
        p2 = ae2->data;
131 22000
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
132 113680
        for (; m >= 8; m -= 8) {
133 104160
                if (m == 8 && ae1->mask == ae2->mask)
134 2280
                        CMPA(*p1, *p2);
135 195320
                CMP(ACL_GT, *p1, *p2);
136 91680
                p1++;
137 91680
                p2++;
138 91680
        }
139 9520
        if (m) {
140 9120
                assert (m < 8);
141 9120
                a1 = *p1 >> (8 - m);
142 9120
                a2 = *p2 >> (8 - m);
143 9120
                if (ae1->mask == ae2->mask)
144 2840
                        CMPA(a1, a2);
145 12320
                CMP(ACL_GT, a1, a2);
146 4280
        } else if (ae1->mask == ae2->mask) {
147 400
                CMPA(*p1, *p2);
148 200
        }
149
        /* Long mask is less than short mask */
150 4520
        CMP(ACL_CONTAINS, ae2->mask, ae1->mask);
151
152 240
        return (ACL_EQ);
153 22000
}
154
155
static int
156 4240
vcl_acl_disjoint(const struct acl_e *ae1, const struct acl_e *ae2)
157
{
158
        const unsigned char *p1, *p2;
159
        unsigned m;
160
161 4240
        CHECK_OBJ_NOTNULL(ae1, VCC_ACL_E_MAGIC);
162 4240
        CHECK_OBJ_NOTNULL(ae2, VCC_ACL_E_MAGIC);
163
164 4240
        p1 = ae1->data;
165 4240
        p2 = ae2->data;
166 4240
        m = vmin_t(unsigned, ae1->mask, ae2->mask);
167 30640
        for (; m >= 8; m -= 8) {
168 54040
                CMP(ACL_GT, *p1, *p2);
169 26400
                p1++;
170 26400
                p2++;
171 26400
        }
172 3000
        if (m) {
173 2880
                m = 0xff00 >> m;
174 2880
                m &= 0xff;
175 5360
                CMP(ACL_GT, *p1 & m, *p2 & m);
176 2480
        }
177 2600
        return (0);
178 4240
}
179
180 14520
VRBT_GENERATE_INSERT_COLOR(acl_tree, acl_e, branch, static)
181 7320
VRBT_GENERATE_INSERT_FINISH(acl_tree, acl_e, branch, static)
182 24920
VRBT_GENERATE_INSERT(acl_tree, acl_e, branch, vcl_acl_cmp, static)
183 1800
VRBT_GENERATE_REMOVE_COLOR(acl_tree, acl_e, branch, static)
184 3240
VRBT_GENERATE_REMOVE(acl_tree, acl_e, branch, static)
185 7080
VRBT_GENERATE_MINMAX(acl_tree, acl_e, branch, static)
186 24080
VRBT_GENERATE_NEXT(acl_tree, acl_e, branch, static)
187 18600
VRBT_GENERATE_PREV(acl_tree, acl_e, branch, static)
188
189
static char *
190 7040
vcc_acl_chk(struct vcc *tl, const struct acl_e *ae, const int l,
191
    unsigned char *p, int fam)
192
{
193
        const unsigned char *u;
194
        char h[VTCP_ADDRBUFSIZE];
195
        char t[VTCP_ADDRBUFSIZE + 10];
196 7040
        char s[vsa_suckaddr_len];
197 7040
        char *r = NULL;
198
        const struct suckaddr *sa;
199
        unsigned m;
200 7040
        int ll, ret = 0;
201
202 7040
        u = p;
203 7040
        ll = l;
204 7040
        m = ae->mask;
205
206 7040
        p += m / 8;
207 7040
        ll -= m / 8;
208 7040
        assert (ll >= 0);
209 7040
        m %= 8;
210
211 7040
        if (m && ((unsigned)*p << m & 0xff) != 0) {
212 160
                ret = 1;
213 160
                m = 0xff00 >> m;
214 160
                *p &= m;
215 160
        }
216 7040
        if (m) {
217 3960
                p++;
218 3960
                ll--;
219 3960
        }
220
221 13200
        for ( ; ll > 0; p++, ll--) {
222 6160
                if (*p == 0)
223 5960
                        continue;
224 200
                ret = 1;
225 200
                *p = 0;
226 200
        }
227 7040
        if (ret == 0)
228 6680
                return (NULL);
229
230 360
        sa = VSA_BuildFAP(s, fam, u, l, NULL, 0);
231 360
        AN(sa);
232 360
        VTCP_name(sa, h, sizeof h, NULL, 0);
233 360
        bprintf(t, "%s/%d", h, ae->mask);
234 360
        if (tl->acl->flag_pedantic != 0) {
235 80
                VSB_cat(tl->sb, "Non-zero bits in masked part, ");
236 80
                VSB_printf(tl->sb, "(maybe use %s ?)\n", t);
237 80
                vcc_ErrWhere(tl, ae->t_addr);
238 80
        }
239 360
        REPLACE(r, t);
240 360
        return (r);
241 7040
}
242
243
static void
244 8160
vcl_acl_fold(struct vcc *tl, struct acl_e **l, struct acl_e **r)
245
{
246
        enum acl_cmp_e cmp;
247
248 8160
        AN(l);
249 8160
        AN(r);
250 8160
        CHECK_OBJ_NOTNULL(*l, VCC_ACL_E_MAGIC);
251 8160
        CHECK_OBJ_NOTNULL(*r, VCC_ACL_E_MAGIC);
252
253 8160
        if ((*l)->not || (*r)->not)
254 4080
                return;
255
256 4080
        cmp = vcl_acl_cmp(*l, *r);
257
258 4080
        assert(cmp < 0);
259 4080
        if (cmp == ACL_LT)
260 2840
                return;
261
262 1240
        do {
263 1280
                switch (cmp) {
264
                case ACL_CONTAINED:
265 760
                        VSB_cat(tl->sb, "ACL entry:\n");
266 760
                        vcc_ErrWhere(tl, (*r)->t_addr);
267 760
                        VSB_cat(tl->sb, "supersedes / removes:\n");
268 760
                        vcc_ErrWhere(tl, (*l)->t_addr);
269 760
                        vcc_Warn(tl);
270 760
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
271 760
                        FREE_OBJ(*l);
272 760
                        *l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, *r);
273 760
                        break;
274
                case ACL_LEFT:
275 520
                        (*l)->mask--;
276 520
                        (*l)->fixed = "folded";
277 520
                        VSB_cat(tl->sb, "ACL entry:\n");
278 520
                        vcc_ErrWhere(tl, (*l)->t_addr);
279 520
                        VSB_cat(tl->sb, "left of:\n");
280 520
                        vcc_ErrWhere(tl, (*r)->t_addr);
281 1040
                        VSB_printf(tl->sb, "removing the latter and expanding "
282
                            "mask of the former by one to /%u\n",
283 520
                            (*l)->mask - 8);
284 520
                        vcc_Warn(tl);
285 520
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *r);
286 520
                        FREE_OBJ(*r);
287 520
                        VRBT_REMOVE(acl_tree, &tl->acl->acl_tree, *l);
288 520
                        vcc_acl_insert_entry(tl, l);
289 520
                        return;
290
                default:
291 0
                        INCOMPL();
292 0
                }
293 760
                if (*l == NULL || *r == NULL || (*l)->not || (*r)->not)
294 440
                        break;
295 320
                cmp = vcl_acl_cmp(*l, *r);
296 320
        } while (cmp != ACL_LT);
297 8160
}
298
299
static void
300 7560
vcc_acl_insert_entry(struct vcc *tl, struct acl_e **aenp)
301
{
302
        struct acl_e *ae2, *l, *r;
303
304 7560
        CHECK_OBJ_NOTNULL(*aenp, VCC_ACL_E_MAGIC);
305 7560
        ae2 = VRBT_INSERT(acl_tree, &tl->acl->acl_tree, *aenp);
306 7560
        if (ae2 != NULL) {
307 240
                if (ae2->not != (*aenp)->not) {
308 40
                        VSB_cat(tl->sb, "Conflicting ACL entries:\n");
309 40
                        vcc_ErrWhere(tl, ae2->t_addr);
310 40
                        VSB_cat(tl->sb, "vs:\n");
311 40
                        vcc_ErrWhere(tl, (*aenp)->t_addr);
312 40
                }
313 240
                return;
314
        }
315
316 7320
        r = *aenp;
317 7320
        *aenp = NULL;
318
319 7320
        if (tl->acl->flag_fold == 0)
320 560
                return;
321
322 6760
        l = VRBT_PREV(acl_tree, &tl->acl->acl_tree, r);
323 6760
        if (l != NULL) {
324 4960
                vcl_acl_fold(tl, &l, &r);
325 4960
        }
326 6760
        if (r == NULL)
327 320
                return;
328 6440
        l = r;
329 6440
        r = VRBT_NEXT(acl_tree, &tl->acl->acl_tree, l);
330 6440
        if (r == NULL)
331 3240
                return;
332 3200
        vcl_acl_fold(tl, &l, &r);
333 7560
}
334
335
static void
336 7120
vcc_acl_add_entry(struct vcc *tl, const struct acl_e *ae, int l,
337
    unsigned char *u, int fam)
338
{
339
        struct acl_e *aen;
340
341 7120
        if (fam == PF_INET && ae->mask > 32) {
342 80
                VSB_printf(tl->sb,
343 40
                    "Too wide mask (/%u) for IPv4 address\n", ae->mask);
344 40
                if (ae->t_mask != NULL)
345 40
                        vcc_ErrWhere(tl, ae->t_mask);
346
                else
347 0
                        vcc_ErrWhere(tl, ae->t_addr);
348 40
                return;
349
        }
350 7080
        if (fam == PF_INET6 && ae->mask > 128) {
351 80
                VSB_printf(tl->sb,
352 40
                    "Too wide mask (/%u) for IPv6 address\n", ae->mask);
353 40
                vcc_ErrWhere(tl, ae->t_mask);
354 40
                return;
355
        }
356
357
        /* Make a copy from the template */
358 7040
        ALLOC_OBJ(aen, VCC_ACL_E_MAGIC);
359 7040
        AN(aen);
360 7040
        *aen = *ae;
361 7040
        aen->addr = strdup(ae->addr);
362 7040
        AN(aen->addr);
363
364 7040
        aen->fixed = vcc_acl_chk(tl, ae, l, u, fam);
365
366
        /* We treat family as part of address, it saves code */
367 7040
        assert(fam <= 0xff);
368 7040
        aen->data[0] = fam & 0xff;
369 7040
        aen->mask += 8;
370
371 7040
        assert(l + 1UL <= sizeof aen->data);
372 7040
        memcpy(aen->data + 1L, u, l);
373
374 7040
        vcc_acl_insert_entry(tl, &aen);
375 7040
        if (aen != NULL)
376 240
                vcl_acl_free(&aen);
377 7120
}
378
379
static void
380 2280
vcc_acl_try_getaddrinfo(struct vcc *tl, struct acl_e *ae)
381
{
382
        struct addrinfo *res0, *res, hint;
383
        struct sockaddr_in *sin4;
384
        struct sockaddr_in6 *sin6;
385
        unsigned char *u, i4, i6;
386
        int error;
387
388 2280
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
389 2280
        memset(&hint, 0, sizeof hint);
390 2280
        hint.ai_family = PF_UNSPEC;
391 2280
        hint.ai_socktype = SOCK_STREAM;
392 2280
        error = getaddrinfo(ae->addr, "0", &hint, &res0);
393 2280
        if (error) {
394 160
                if (ae->para) {
395 160
                        VSB_printf(tl->sb,
396
                            "Warning: %s ignored\n  -- %s\n",
397 80
                            ae->addr, gai_strerror(error));
398 160
                        Fh(tl, 1, "/* Ignored ACL entry: %s%s",
399 80
                            ae->para ? "\"(\" " : "", ae->not ? "\"!\" " : "");
400 80
                        EncToken(tl->fh, ae->t_addr);
401 80
                        if (ae->t_mask)
402 40
                                Fh(tl, 0, "/%u", ae->mask);
403 80
                        Fh(tl, 0, "%s\n", ae->para ? " \")\"" : "");
404 160
                        Fh(tl, 1, " * getaddrinfo:  %s */\n",
405 80
                             gai_strerror(error));
406 80
                } else {
407 160
                        VSB_printf(tl->sb,
408
                            "DNS lookup(%s): %s\n",
409 80
                            ae->addr, gai_strerror(error));
410 80
                        vcc_ErrWhere(tl, ae->t_addr);
411
                }
412 160
                return;
413
        }
414
415 2120
        i4 = i6 = 0;
416 4320
        for (res = res0; res != NULL; res = res->ai_next) {
417 2200
                switch (res->ai_family) {
418
                case PF_INET:
419 80
                        i4++;
420 80
                        break;
421
                case PF_INET6:
422 2120
                        i6++;
423 2120
                        break;
424
                default:
425 0
                        VSB_printf(tl->sb,
426
                            "Ignoring unknown protocol family (%d) for %.*s\n",
427 0
                                res->ai_family, PF(ae->t_addr));
428 0
                        continue;
429
                }
430 2200
        }
431
432 2120
        if (ae->t_mask != NULL && i4 > 0 && i6 > 0) {
433 0
                VSB_printf(tl->sb,
434
                    "Mask (/%u) specified, but string resolves to"
435 0
                    " both IPv4 and IPv6 addresses.\n", ae->mask);
436 0
                vcc_ErrWhere(tl, ae->t_mask);
437 0
                freeaddrinfo(res0);
438 0
                return;
439
        }
440
441 4240
        for (res = res0; res != NULL; res = res->ai_next) {
442 2200
                switch (res->ai_family) {
443
                case PF_INET:
444 80
                        assert(PF_INET < 256);
445 80
                        sin4 = (void*)res->ai_addr;
446 80
                        assert(sizeof(sin4->sin_addr) == 4);
447 80
                        u = (void*)&sin4->sin_addr;
448 80
                        if (ae->t_mask == NULL)
449 80
                                ae->mask = 32;
450 80
                        vcc_acl_add_entry(tl, ae, 4, u, res->ai_family);
451 80
                        break;
452
                case PF_INET6:
453 2120
                        assert(PF_INET6 < 256);
454 2120
                        sin6 = (void*)res->ai_addr;
455 2120
                        assert(sizeof(sin6->sin6_addr) == 16);
456 2120
                        u = (void*)&sin6->sin6_addr;
457 2120
                        if (ae->t_mask == NULL)
458 320
                                ae->mask = 128;
459 2120
                        vcc_acl_add_entry(tl, ae, 16, u, res->ai_family);
460 2120
                        break;
461
                default:
462 0
                        continue;
463
                }
464 2200
                if (tl->err)
465 80
                        freeaddrinfo(res0);
466 2200
                ERRCHK(tl);
467 2120
        }
468 2040
        freeaddrinfo(res0);
469
470 2280
}
471
472
/*--------------------------------------------------------------------
473
 * Ancient stupidity on the part of X/Open and other standards orgs
474
 * dictate that "192.168" be translated to 192.0.0.168.  Ever since
475
 * CIDR happened, "192.168/16" notation has been used, but apparently
476
 * no API supports parsing this, so roll our own.
477
 */
478
479
static int
480 7200
vcc_acl_try_netnotation(struct vcc *tl, struct acl_e *ae)
481
{
482
        unsigned char b[4];
483
        int i, j, k;
484
        unsigned u;
485
        const char *p;
486
487 7200
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
488 7200
        memset(b, 0, sizeof b);
489 7200
        p = ae->addr;
490 21200
        for (i = 0; i < 4; i++) {
491 21200
                j = sscanf(p, "%u%n", &u, &k);
492 21200
                if (j != 1)
493 2080
                        return (0);
494 19120
                if (u & ~0xff)
495 80
                        return (0);
496 19040
                b[i] = (unsigned char)u;
497 19040
                if (p[k] == '\0')
498 4920
                        break;
499 14120
                if (p[k] != '.')
500 120
                        return (0);
501 14000
                p += k + 1;
502 14000
        }
503 4920
        if (ae->t_mask == NULL)
504 1120
                ae->mask = 8 + 8 * i;
505 4920
        vcc_acl_add_entry(tl, ae, 4, b, AF_INET);
506 4920
        return (1);
507 7200
}
508
509
static void
510 7360
vcc_acl_entry(struct vcc *tl)
511
{
512
        struct acl_e ae[1];
513
        char *sl, *e;
514
515 7360
        INIT_OBJ(ae, VCC_ACL_E_MAGIC);
516
517 7360
        if (tl->t->tok == '!') {
518 1680
                ae->not = 1;
519 1680
                vcc_NextToken(tl);
520 1680
        }
521
522 7360
        if (tl->t->tok == '(') {
523 120
                ae->para = 1;
524 120
                vcc_NextToken(tl);
525 120
        }
526
527 7360
        if (!ae->not && tl->t->tok == '!') {
528 40
                ae->not = 1;
529 40
                vcc_NextToken(tl);
530 40
        }
531
532 7360
        ExpectErr(tl, CSTR);
533 7360
        ae->t_addr = tl->t;
534 7360
        ae->addr = ae->t_addr->dec;
535 7360
        vcc_NextToken(tl);
536
537 7360
        if (strchr(ae->t_addr->dec, '/') != NULL) {
538 120
                sl = strchr(ae->addr, '/');
539 120
                AN(sl);
540 120
                *sl++ = '\0';
541 120
                e = NULL;
542 120
                ae->mask = strtoul(sl, &e, 10);
543 120
                if (*e != '\0') {
544 80
                        VSB_cat(tl->sb, ".../mask is not numeric.\n");
545 80
                        vcc_ErrWhere(tl, ae->t_addr);
546 80
                        return;
547
                }
548 40
                ae->t_mask = ae->t_addr;
549 40
                if (tl->t->tok == '/') {
550 40
                        VSB_cat(tl->sb, "/mask only allowed once.\n");
551 40
                        vcc_ErrWhere(tl, tl->t);
552 40
                        return;
553
                }
554 7240
        } else if (tl->t->tok == '/') {
555 5640
                vcc_NextToken(tl);
556 5640
                ae->t_mask = tl->t;
557 5640
                ExpectErr(tl, CNUM);
558 5640
                ae->mask = vcc_UintVal(tl);
559 5640
        }
560
561 7240
        if (ae->para)
562 120
                SkipToken(tl, ')');
563
564 7200
        if (!vcc_acl_try_netnotation(tl, ae)) {
565 2280
                ERRCHK(tl);
566 2280
                vcc_acl_try_getaddrinfo(tl, ae);
567 2280
        }
568 7200
        ERRCHK(tl);
569 7360
}
570
571
/*********************************************************************
572
 * Emit the tokens making up an entry as C-strings
573
 */
574
575
static void
576 2120
vcc_acl_emit_tokens(const struct vcc *tl, const struct acl_e *ae)
577
{
578
        struct token *t;
579 2120
        const char *sep = "";
580
581 2120
        CHECK_OBJ_NOTNULL(ae, VCC_ACL_E_MAGIC);
582 2120
        t = ae->t_addr;
583 2120
        do {
584 6200
                if (t->tok == CSTR) {
585 2120
                        Fh(tl, 0, "%s\"\\\"\" ", sep);
586 2120
                        EncToken(tl->fh, t);
587 2120
                        Fh(tl, 0, " \"\\\"\"");
588 6200
                } else if (t == ae->t_mask) {
589 2040
                        Fh(tl, 0, " \"%u\"", ae->mask - 8);
590 2040
                } else {
591 2040
                        Fh(tl, 0, "%s\"%.*s\"", sep, PF(t));
592
                }
593 6200
                if (t == ae->t_mask)
594 2040
                        break;
595 4160
                t = vcc_PeekTokenFrom(tl, t);
596 4160
                AN(t);
597 4160
                sep = " ";
598 4160
        } while (ae->t_mask != NULL);
599 2120
        if (ae->fixed)
600 400
                Fh(tl, 0, "\" fixed: %s\"", ae->fixed);
601 2120
}
602
603
/*********************************************************************
604
 * Emit ACL on table format
605
 */
606
607
static unsigned
608 80
vcc_acl_emit_tables(const struct vcc *tl, unsigned n, const char *name)
609
{
610
        struct acl_e *ae;
611 80
        unsigned rv = sizeof(ae->data) + 3;
612 80
        unsigned nn = 0;
613
        size_t sz;
614
615 160
        Fh(tl, 0, "\nstatic unsigned char acl_tbl_%s[%u*%u] = {\n",
616 80
            name, n, rv);
617 1840
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
618 1760
                if (ae->overlapped)
619 1440
                        continue;
620 320
                Fh(tl, 0, "\t0x%02x,", ae->not ? 0 : 1);
621 320
                Fh(tl, 0, "0x%02x,", (ae->mask >> 3) - 1);
622 320
                Fh(tl, 0, "0x%02x,", (0xff00 >> (ae->mask & 7)) & 0xff);
623 5760
                for (sz = 0; sz < sizeof(ae->data); sz++)
624 5440
                        Fh(tl, 0, "0x%02x,", ae->data[sz]);
625 320
                for (; sz < rv - 3; sz++)
626 0
                        Fh(tl, 0, "0,");
627 320
                Fh(tl, 0, "\n");
628 320
                nn++;
629 320
        }
630 80
        assert(n == nn);
631 80
        Fh(tl, 0, "};\n");
632 80
        if (tl->acl->flag_log) {
633 80
                Fh(tl, 0, "\nstatic const char *acl_str_%s[%d] = {\n",
634 40
                    name, n);
635 920
                VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
636 880
                        if (ae->overlapped)
637 720
                                continue;
638 160
                        Fh(tl, 0, "\t");
639 320
                        Fh(tl, 0, "\"%sMATCH %s \" ",
640 160
                            ae->not ? "NEG_" : "", name);
641 160
                        vcc_acl_emit_tokens(tl, ae);
642 160
                        Fh(tl, 0, ",\n");
643 160
                }
644 40
                Fh(tl, 0, "};\n");
645 40
        }
646 80
        return (rv);
647
}
648
649
/*********************************************************************
650
 * Emit a function to match the ACL we have collected
651
 */
652
653
static void
654 1160
vcc_acl_emit(struct vcc *tl, const struct symbol *sym)
655
{
656
        struct acl_e *ae, *ae2;
657
        int depth, l, m, i;
658
        unsigned at[ACL_MAXADDR];
659 1160
        struct inifin *ifp = NULL;
660
        struct vsb *func;
661 1160
        unsigned n, no, nw = 0;
662
663 1160
        func = VSB_new_auto();
664 1160
        AN(func);
665 1160
        VSB_cat(func, "match_acl_");
666 1160
        VCC_PrintCName(func, sym->name, NULL);
667 1160
        AZ(VSB_finish(func));
668
669 1160
        depth = -1;
670 1160
        at[0] = 256;
671 1160
        ae2 = NULL;
672 1160
        n = no = 0;
673 6520
        VRBT_FOREACH_REVERSE(ae, acl_tree, &tl->acl->acl_tree) {
674 5360
                n++;
675 5360
                if (ae2 == NULL) {
676 1120
                        ae2 = ae;
677 5360
                } else if (vcl_acl_disjoint(ae, ae2)) {
678 1640
                        ae2 = ae;
679 1640
                } else {
680 2600
                        no++;
681 2600
                        ae->overlapped = 1;
682
                }
683 5360
        }
684
685 1160
        Fh(tl, 0, "/* acl_n_%s n %u no %u */\n", sym->name, n, no);
686 1160
        if (n - no < (1<<1))
687 600
                no = n;
688 560
        else if (!tl->acl->flag_table)
689 480
                no = n;
690
691 1160
        if (no < n)
692 80
                nw = vcc_acl_emit_tables(tl, n - no, sym->name);
693
694
695 1160
        Fh(tl, 0, "\nstatic int v_matchproto_(acl_match_f)\n");
696 1160
        Fh(tl, 0, "%s(VRT_CTX, const VCL_IP p)\n", VSB_data(func));
697 1160
        Fh(tl, 0, "{\n");
698 1160
        Fh(tl, 0, "\tconst unsigned char *a;\n");
699 1160
        Fh(tl, 0, "\tint fam;\n");
700 1160
        Fh(tl, 0, "\n");
701 1160
        Fh(tl, 0, "\tfam = VRT_VSA_GetPtr(ctx, p, &a);\n");
702 1160
        Fh(tl, 0, "\tif (fam < 0) {\n");
703 1160
        Fh(tl, 0, "\t\tVRT_fail(ctx,");
704 1160
        Fh(tl, 0, " \"ACL %s: no protocol family\");\n", sym->name);
705 1160
        Fh(tl, 0, "\t\treturn(0);\n");
706 1160
        Fh(tl, 0, "\t}\n\n");
707 1160
        if (!tl->err_unref) {
708 80
                ifp = New_IniFin(tl);
709 160
                VSB_printf(ifp->ini,
710 80
                        "\t(void)%s;\n", VSB_data(func));
711 80
        }
712
713 6520
        VRBT_FOREACH(ae, acl_tree, &tl->acl->acl_tree) {
714
715 5360
                if (no < n && !ae->overlapped)
716 320
                        continue;
717
718
                /* Find how much common prefix we have */
719 28440
                for (l = 0; l <= depth && l * 8 < (int)ae->mask - 7; l++) {
720 25360
                        assert(l >= 0);
721 25360
                        if (ae->data[l] != at[l])
722 1960
                                break;
723 23400
                }
724
725
                /* Back down, if necessary */
726 11840
                while (l <= depth) {
727 6800
                        Fh(tl, 0, "\t%*s}\n", -depth, "");
728 6800
                        depth--;
729
                }
730
731 5040
                m = (int)ae->mask;
732 5040
                assert(m >= l*8);
733 5040
                m -= l * 8;
734
735
                /* Do whole byte compares */
736 18720
                for (i = l; m >= 8; m -= 8, i++) {
737 13680
                        if (i == 0)
738 3200
                                Fh(tl, 0, "\t%*s%sif (fam == %d) {\n",
739 1600
                                    -i, "", "", ae->data[i]);
740
                        else
741 24160
                                Fh(tl, 0, "\t%*s%sif (a[%d] == %d) {\n",
742 12080
                                    -i, "", "", i - 1, ae->data[i]);
743 13680
                        at[i] = ae->data[i];
744 13680
                        depth = i;
745 13680
                }
746
747 5040
                if (m > 0) {
748
                        // XXX can remove masking due to fixup
749
                        /* Do fractional byte compares */
750 6080
                        Fh(tl, 0, "\t%*s%sif ((a[%d] & 0x%x) == %d) {\n",
751 3040
                            -i, "", "", i - 1, (0xff00 >> m) & 0xff,
752 3040
                            ae->data[i] & ((0xff00 >> m) & 0xff));
753 3040
                        at[i] = 256;
754 3040
                        depth = i;
755 3040
                }
756
757 5040
                i = ((int)ae->mask + 7) / 8;
758
759 5040
                if (tl->acl->flag_log) {
760 3920
                        Fh(tl, 0, "\t%*sVPI_acl_log(ctx, \"%sMATCH %s \" ",
761 1960
                            -i, "", ae->not ? "NEG_" : "", sym->name);
762 1960
                        vcc_acl_emit_tokens(tl, ae);
763 1960
                        Fh(tl, 0, ");\n");
764 1960
                }
765
766 5040
                Fh(tl, 0, "\t%*sreturn (%d);\n", -i, "", ae->not ? 0 : 1);
767 5040
        }
768
769
        /* Unwind */
770 11080
        for (; 0 <= depth; depth--)
771 9920
                Fh(tl, 0, "\t%*.*s}\n", depth, depth, "");
772
773 1160
        if (no < n) {
774 80
                Fh(tl, 0, "\treturn(\n\t    VPI_acl_table(ctx,\n");
775 80
                Fh(tl, 0, "\t\tp,\n");
776 80
                Fh(tl, 0, "\t\t%u, %u,\n", n - no, nw);
777 80
                Fh(tl, 0, "\t\tacl_tbl_%s,\n", sym->name);
778 80
                if (tl->acl->flag_log)
779 40
                        Fh(tl, 0, "\t\tacl_str_%s,\n", sym->name);
780
                else
781 40
                        Fh(tl, 0, "\t\tNULL,\n");
782 80
                Fh(tl, 0, "\t\t\"NO MATCH %s\"\n\t    )\n\t);\n", sym->name);
783 80
        } else {
784
                /* Deny by default */
785 1080
                if (tl->acl->flag_log)
786 320
                        Fh(tl, 0, "\tVPI_acl_log(ctx, \"NO_MATCH %s\");\n",
787 160
                            sym->name);
788 1080
                Fh(tl, 0, "\treturn(0);\n");
789
        }
790 1160
        Fh(tl, 0, "}\n");
791
792
        /* Emit the struct that will be referenced */
793 1160
        Fh(tl, 0, "\nstatic const struct vrt_acl %s[] = {{\n", sym->rname);
794 1160
        Fh(tl, 0, "\t.magic = VRT_ACL_MAGIC,\n");
795 1160
        Fh(tl, 0, "\t.match = &%s,\n", VSB_data(func));
796 1160
        Fh(tl, 0, "\t.name = \"%s\",\n", sym->name);
797 1160
        Fh(tl, 0, "}};\n\n");
798 1160
        if (!tl->err_unref) {
799 80
                AN(ifp);
800 80
                VSB_printf(ifp->ini, "\t(void)%s;", sym->rname);
801 80
        }
802 1160
        VSB_destroy(&func);
803 1160
}
804
805
void
806 1760
vcc_ParseAcl(struct vcc *tl)
807
{
808
        struct symbol *sym;
809
        int sign;
810
        struct acl acl[1];
811
812 1760
        INIT_OBJ(acl, VCC_ACL_MAGIC);
813 1760
        tl->acl = acl;
814 1760
        acl->flag_pedantic = 1;
815 1760
        acl->flag_fold = 1;
816 1760
        vcc_NextToken(tl);
817 1760
        VRBT_INIT(&acl->acl_tree);
818
819 1760
        vcc_ExpectVid(tl, "ACL");
820 1760
        ERRCHK(tl);
821 1720
        sym = VCC_HandleSymbol(tl, ACL);
822 1720
        ERRCHK(tl);
823 1720
        AN(sym);
824
825
#define FLAGS_MSG "Valid ACL flags are `log`, `fold`, `pedantic` and `table`:\n"
826
827 2400
        while (1) {
828 2400
                sign = vcc_IsFlag(tl);
829 2400
                if (tl->err) {
830 40
                        VSB_cat(tl->sb, FLAGS_MSG);
831 40
                        return;
832
                }
833 2360
                if (sign < 0)
834 1640
                        break;
835 720
                if (vcc_IdIs(tl->t, "log")) {
836 200
                        acl->flag_log = sign;
837 200
                        vcc_NextToken(tl);
838 720
                } else if (vcc_IdIs(tl->t, "fold")) {
839 80
                        acl->flag_fold = sign;
840 80
                        vcc_NextToken(tl);
841 520
                } else if (vcc_IdIs(tl->t, "pedantic")) {
842 320
                        acl->flag_pedantic = sign;
843 320
                        vcc_NextToken(tl);
844 440
                } else if (vcc_IdIs(tl->t, "table")) {
845 80
                        acl->flag_table = sign;
846 80
                        vcc_NextToken(tl);
847 80
                } else {
848 40
                        VSB_cat(tl->sb, "Unknown ACL flag. " FLAGS_MSG);
849 40
                        vcc_ErrWhere(tl, tl->t);
850 40
                        return;
851
                }
852
        }
853
854
#undef FLAGS_MSG
855
856 1640
        SkipToken(tl, '{');
857
858 8520
        while (tl->t->tok != '}') {
859 7360
                vcc_acl_entry(tl);
860 7360
                ERRCHK(tl);
861 6920
                SkipToken(tl, ';');
862
        }
863 1160
        SkipToken(tl, '}');
864
865 1160
        vcc_acl_emit(tl, sym);
866 1760
}