diff options
-rw-r--r-- | sbin/pfctl/Makefile | 3 | ||||
-rw-r--r-- | sbin/pfctl/pfctl.8 | 37 | ||||
-rw-r--r-- | sbin/pfctl/pfctl.c | 49 | ||||
-rw-r--r-- | sbin/pfctl/pfctl_optimize.c | 1558 | ||||
-rw-r--r-- | sbin/pfctl/pfctl_parser.c | 6 | ||||
-rw-r--r-- | sbin/pfctl/pfctl_parser.h | 35 |
6 files changed, 1677 insertions, 11 deletions
diff --git a/sbin/pfctl/Makefile b/sbin/pfctl/Makefile index 6ff9790605b..52763fde678 100644 --- a/sbin/pfctl/Makefile +++ b/sbin/pfctl/Makefile @@ -1,8 +1,9 @@ -# $OpenBSD: Makefile,v 1.16 2004/06/10 19:02:16 miod Exp $ +# $OpenBSD: Makefile,v 1.17 2004/07/16 23:44:24 frantzen Exp $ PROG= pfctl SRCS= pfctl.c parse.y pfctl_parser.c pf_print_state.c pfctl_altq.c SRCS+= pfctl_osfp.c pfctl_radix.c pfctl_table.c pfctl_qstats.c +SRCS+= pfctl_optimize.c CFLAGS+= -Wall -Wmissing-prototypes -Wno-uninitialized CFLAGS+= -Wstrict-prototypes -I${.CURDIR} YFLAGS= diff --git a/sbin/pfctl/pfctl.8 b/sbin/pfctl/pfctl.8 index ca87f39d384..45c0bbf80e5 100644 --- a/sbin/pfctl/pfctl.8 +++ b/sbin/pfctl/pfctl.8 @@ -1,4 +1,4 @@ -.\" $OpenBSD: pfctl.8,v 1.112 2004/06/21 20:47:11 msf Exp $ +.\" $OpenBSD: pfctl.8,v 1.113 2004/07/16 23:44:24 frantzen Exp $ .\" .\" Copyright (c) 2001 Kjell Wooding. All rights reserved. .\" @@ -33,7 +33,7 @@ .Sh SYNOPSIS .Nm pfctl .Bk -words -.Op Fl AdeghNnOqRrvz +.Op Fl AdeghNnOoqRrvz .Xo .Oo Fl a Ar anchor .Op Ns / Ns Ar ruleset Oc @@ -238,6 +238,39 @@ Do not actually load rules, just parse them. .It Fl O Load only the options present in the rule file. Other rules and options are ignored. +.It Fl o +Enable the ruleset optimizer. +The ruleset optimizer attempts to improve rulesets by removing rule +duplication and making better use of rule ordering. +Specifically, it does four things: +.Pp +.Bl -enum -compact +.It +remove duplicate rules +.It +remove rules that are a subset of another rule +.It +combine multiple rules into a table when advantageous +.It +re-order the rules to improve evaluation performance +.El +.Pp +A second +.Fl o +may be specified to use the currently loaded ruleset as a feedback profile +to tailor the optimization of the +.Ar quick +rules to the actual network behavior. +.Pp +It is important to note that the ruleset optimizer will modify the ruleset +to improve performance. +A side effect of the ruleset modification is that per-rule accounting +statistics will have different meanings than before. +If per-rule accounting is important for billing purposes or whatnot, either +the ruleset optimizer should not be used or a +.Ar label +field should be added to all of the accounting rules to act as optimization +barriers. .It Fl p Ar device Use the device file .Ar device diff --git a/sbin/pfctl/pfctl.c b/sbin/pfctl/pfctl.c index 3de4fecf3b0..61927181590 100644 --- a/sbin/pfctl/pfctl.c +++ b/sbin/pfctl/pfctl.c @@ -1,4 +1,4 @@ -/* $OpenBSD: pfctl.c,v 1.217 2004/05/21 23:10:48 dhartmei Exp $ */ +/* $OpenBSD: pfctl.c,v 1.218 2004/07/16 23:44:24 frantzen Exp $ */ /* * Copyright (c) 2001 Daniel Hartmeier @@ -871,6 +871,39 @@ pfctl_add_rule(struct pfctl *pf, struct pf_rule *r, const char *anchor_call) break; } + + if ((pf->opts & PF_OPT_OPTIMIZE) && rs_num == PF_RULESET_FILTER) { + /* + * We'll do an optimization post-pass before finally adding the + * rules. Then we'll disable the optimization flag and feed + * the rules right back into this function. + */ + struct pf_opt_rule *pfr; + struct pf_pooladdr *pa; + + if ((pfr = calloc(1, sizeof(*pfr))) == NULL) + err(1, "calloc"); + memcpy(&pfr->por_rule, r, sizeof(*r)); + if (strlcpy(pfr->por_anchor, anchor_call, + sizeof(pfr->por_anchor)) >= sizeof(pfr->por_anchor)) + errx(1, "pfctl_add_rule: strlcpy"); + TAILQ_INSERT_TAIL(&pf->opt_queue, pfr, por_entry); + + if (TAILQ_FIRST(&r->rpool.list) != NULL) { + TAILQ_INIT(&pfr->por_rule.rpool.list); + while ((pa = TAILQ_FIRST(&r->rpool.list)) != NULL) { + TAILQ_REMOVE(&r->rpool.list, pa, entries); + TAILQ_INSERT_TAIL(&pfr->por_rule.rpool.list, pa, + entries); + } + } else { + memset(&pfr->por_rule.rpool, 0, + sizeof(pfr->por_rule.rpool)); + + } + return (0); + } + if ((pf->opts & PF_OPT_NOACTION) == 0) { bzero(&pr, sizeof(pr)); if (strlcpy(pr.anchor, pf->anchor, sizeof(pr.anchor)) >= @@ -962,6 +995,7 @@ pfctl_rules(int dev, char *filename, int opts, char *anchorname, pf.trans = t; pf.rule_nr = 0; pf.anchor = anchorname; + TAILQ_INIT(&pf.opt_queue); if ((opts & PF_OPT_NOACTION) == 0) { if ((pf.loadopt & PFCTL_FLAG_NAT) != 0) { @@ -999,6 +1033,11 @@ pfctl_rules(int dev, char *filename, int opts, char *anchorname, else goto _error; } + if (pf.opts & PF_OPT_OPTIMIZE) { + if (pfctl_optimize_rules(&pf)) + ERRX("Failed to optimize ruleset: pf rules not loaded"); + } + if ((altqsupport && (pf.loadopt & PFCTL_FLAG_ALTQ) != 0)) if (check_commit_altq(dev, opts) != 0) ERRX("errors in altq config"); @@ -1345,7 +1384,7 @@ main(int argc, char *argv[]) usage(); while ((ch = getopt(argc, argv, - "a:AdD:eqf:F:ghi:k:nNOp:rRs:t:T:vx:z")) != -1) { + "a:AdD:eqf:F:ghi:k:nNOop:rRs:t:T:vx:z")) != -1) { switch (ch) { case 'a': anchoropt = optarg; @@ -1408,6 +1447,12 @@ main(int argc, char *argv[]) case 'R': loadopt |= PFCTL_FLAG_FILTER; break; + case 'o': + if (opts & PF_OPT_OPTIMIZE) + opts |= PF_OPT_OPTIMIZE_PROFILE; + else + opts |= PF_OPT_OPTIMIZE; + break; case 'O': loadopt |= PFCTL_FLAG_OPTION; break; diff --git a/sbin/pfctl/pfctl_optimize.c b/sbin/pfctl/pfctl_optimize.c new file mode 100644 index 00000000000..c61155b1171 --- /dev/null +++ b/sbin/pfctl/pfctl_optimize.c @@ -0,0 +1,1558 @@ +/* $OpenBSD: pfctl_optimize.c,v 1.1 2004/07/16 23:44:24 frantzen Exp $ */ + +/* + * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <sys/types.h> +#include <sys/ioctl.h> +#include <sys/socket.h> + +#include <net/if.h> +#include <net/pfvar.h> + +#include <netinet/in.h> +#include <arpa/inet.h> + +#include <assert.h> +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "pfctl_parser.h" +#include "pfctl.h" + +/* The size at which a table becomes faster than individual rules */ +#define TABLE_THRESHOLD 6 + + +/* #define OPT_DEBUG 1 */ +#ifdef OPT_DEBUG +# define DEBUG(str, v...) \ + printf("%s: " str "\n", __FUNCTION__ , ## v) +#else +# define DEBUG(str, v...) ((void)0) +#endif + + +/* + * A container that lets us sort a superblock to optimize the skip step jumps + */ +struct pf_skip_step { + int ps_count; /* number of items */ + TAILQ_HEAD( , pf_opt_rule) ps_rules; + TAILQ_ENTRY(pf_skip_step) ps_entry; +}; + + +/* + * A superblock is a block of adjacent rules of similar action. If there + * are five PASS rules in a row, they all become members of a superblock. + * Once we have a superblock, we are free to re-order any rules within it + * in order to improve performance; if a packet is passed, it doesn't matter + * who passed it. + */ +struct superblock { + TAILQ_HEAD( , pf_opt_rule) sb_rules; + TAILQ_ENTRY(superblock) sb_entry; + struct superblock *sb_profiled_block; + TAILQ_HEAD(skiplist, pf_skip_step) sb_skipsteps[PF_SKIP_COUNT]; +}; +TAILQ_HEAD(superblocks, superblock); + + +/* + * Description of the PF rule structure. + */ +enum { + BARRIER, /* the presence of the field puts the rule in it's own block */ + BREAK, /* the field may not differ between rules in a superblock */ + NOMERGE, /* the field may not differ between rules when combined */ + COMBINED, /* the field may itself be combined with other rules */ + DC, /* we just don't care about the field */ + NEVER}; /* we should never see this field set?!? */ +struct pf_rule_field { + const char *prf_name; + int prf_type; + size_t prf_offset; + size_t prf_size; +} pf_rule_desc[] = { +#define PF_RULE_FIELD(field, ty) \ + {#field, \ + ty, \ + offsetof(struct pf_rule, field), \ + sizeof(((struct pf_rule *)0)->field)} + + + /* + * The presence of these fields in a rule put the rule in it's own + * superblock. Thus it will not be optimized. It also prevents the + * rule from being re-ordered at all. + */ + PF_RULE_FIELD(label, BARRIER), + PF_RULE_FIELD(prob, BARRIER), + PF_RULE_FIELD(max_states, BARRIER), + PF_RULE_FIELD(max_src_nodes, BARRIER), + + /* + * These fields must be the same between all rules in the same superblock. + * These rules are allowed to be re-ordered but only among like rules. + * For instance we can re-order all 'tag "foo"' rules because they have the + * same tag. But we can not re-order between a 'tag "foo"' and a + * 'tag "bar"' since that would change the meaning of the ruleset. + */ + PF_RULE_FIELD(tagname, BREAK), + PF_RULE_FIELD(keep_state, BREAK), + PF_RULE_FIELD(qname, BREAK), + PF_RULE_FIELD(rt, BREAK), + PF_RULE_FIELD(allow_opts, BREAK), + PF_RULE_FIELD(rule_flag, BREAK), + PF_RULE_FIELD(action, BREAK), + + /* + * Any fields not listed in this structure act as BREAK fields + */ + + + /* + * These fields must not differ when we merge two rules together but + * their difference isn't enough to put the rules in different superblocks. + * There are no problems re-ordering any rules with these fields. + */ + PF_RULE_FIELD(af, NOMERGE), + PF_RULE_FIELD(ifnot, NOMERGE), + PF_RULE_FIELD(ifname, NOMERGE), + PF_RULE_FIELD(match_tag_not, NOMERGE), + PF_RULE_FIELD(match_tagname, NOMERGE), + PF_RULE_FIELD(os_fingerprint, NOMERGE), + PF_RULE_FIELD(timeout, NOMERGE), + PF_RULE_FIELD(return_icmp, NOMERGE), + PF_RULE_FIELD(return_icmp6, NOMERGE), + PF_RULE_FIELD(uid, NOMERGE), + PF_RULE_FIELD(gid, NOMERGE), + PF_RULE_FIELD(direction, NOMERGE), + PF_RULE_FIELD(proto, NOMERGE), + PF_RULE_FIELD(type, NOMERGE), + PF_RULE_FIELD(code, NOMERGE), + PF_RULE_FIELD(flags, NOMERGE), + PF_RULE_FIELD(flagset, NOMERGE), + PF_RULE_FIELD(tos, NOMERGE), + PF_RULE_FIELD(src.port, NOMERGE), + PF_RULE_FIELD(dst.port, NOMERGE), + PF_RULE_FIELD(src.port_op, NOMERGE), + PF_RULE_FIELD(dst.port_op, NOMERGE), + PF_RULE_FIELD(src.neg, NOMERGE), + PF_RULE_FIELD(dst.neg, NOMERGE), + + /* These fields can be merged */ + PF_RULE_FIELD(src.addr, COMBINED), + PF_RULE_FIELD(dst.addr, COMBINED), + + /* We just don't care about these fields. They're set by the kernel */ + PF_RULE_FIELD(skip, DC), + PF_RULE_FIELD(evaluations, DC), + PF_RULE_FIELD(packets, DC), + PF_RULE_FIELD(bytes, DC), + PF_RULE_FIELD(kif, DC), + PF_RULE_FIELD(anchor, DC), + PF_RULE_FIELD(states, DC), + PF_RULE_FIELD(src_nodes, DC), + PF_RULE_FIELD(nr, DC), + PF_RULE_FIELD(entries, DC), + PF_RULE_FIELD(qid, DC), + PF_RULE_FIELD(pqid, DC), + PF_RULE_FIELD(anchor_relative, DC), + PF_RULE_FIELD(anchor_wildcard, DC), + + /* These fields should never be set in a PASS/BLOCK rule */ + PF_RULE_FIELD(natpass, NEVER), + PF_RULE_FIELD(max_mss, NEVER), + PF_RULE_FIELD(min_ttl, NEVER), +}; + + + +int add_opt_table(struct pfctl *, struct pf_opt_tbl **, sa_family_t, + struct pf_rule_addr *); +int addrs_combineable(struct pf_rule_addr *, struct pf_rule_addr *); +int addrs_equal(struct pf_rule_addr *, struct pf_rule_addr *); +int block_feedback(struct pfctl *, struct superblock *); +int combine_rules(struct pfctl *, struct superblock *); +void comparable_rule(struct pf_rule *, const struct pf_rule *, int); +int construct_superblocks(struct pfctl *, struct pf_opt_queue *, + struct superblocks *); +void exclude_supersets(struct pf_rule *, struct pf_rule *); +int load_feedback_profile(struct pfctl *, struct superblocks *); +int optimize_superblock(struct pfctl *, struct superblock *); +int pf_opt_create_table(struct pfctl *, struct pf_opt_tbl *); +void remove_from_skipsteps(struct skiplist *, struct superblock *, + struct pf_opt_rule *, struct pf_skip_step *); +int remove_identical_rules(struct pfctl *, struct superblock *); +int reorder_rules(struct pfctl *, struct superblock *, int); +int rules_combineable(struct pf_rule *, struct pf_rule *); +void skip_append(struct superblock *, int, struct pf_skip_step *, + struct pf_opt_rule *); +int skip_compare(int, struct pf_skip_step *, struct pf_opt_rule *); +void skip_init(void); +int skip_cmp_af(struct pf_rule *, struct pf_rule *); +int skip_cmp_dir(struct pf_rule *, struct pf_rule *); +int skip_cmp_dst_addr(struct pf_rule *, struct pf_rule *); +int skip_cmp_dst_port(struct pf_rule *, struct pf_rule *); +int skip_cmp_ifp(struct pf_rule *, struct pf_rule *); +int skip_cmp_proto(struct pf_rule *, struct pf_rule *); +int skip_cmp_src_addr(struct pf_rule *, struct pf_rule *); +int skip_cmp_src_port(struct pf_rule *, struct pf_rule *); +int superblock_inclusive(struct superblock *, struct pf_opt_rule *); +void superblock_free(struct pfctl *, struct superblock *); + + +int (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, struct pf_rule *); +const char *skip_comparitors_names[PF_SKIP_COUNT]; +#define PF_SKIP_COMPARITORS { \ + { "ifp", PF_SKIP_IFP, skip_cmp_ifp }, \ + { "dir", PF_SKIP_DIR, skip_cmp_dir }, \ + { "af", PF_SKIP_AF, skip_cmp_af }, \ + { "proto", PF_SKIP_PROTO, skip_cmp_proto }, \ + { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr }, \ + { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port }, \ + { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr }, \ + { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port } \ +} + +struct pfr_buffer table_buffer; +int table_identifier; + + +int +pfctl_optimize_rules(struct pfctl *pf) +{ + struct superblocks superblocks; + struct superblock *block; + struct pf_opt_rule *por; + int nr; + + DEBUG("optimizing ruleset"); + memset(&table_buffer, 0, sizeof(table_buffer)); + skip_init(); + + if (TAILQ_FIRST(&pf->opt_queue)) + nr = TAILQ_FIRST(&pf->opt_queue)->por_rule.nr; + + TAILQ_INIT(&superblocks); + if (construct_superblocks(pf, &pf->opt_queue, &superblocks)) + goto error; + + if (pf->opts & PF_OPT_OPTIMIZE_PROFILE) { + if (load_feedback_profile(pf, &superblocks)) + goto error; + } + + TAILQ_FOREACH(block, &superblocks, sb_entry) { + if (optimize_superblock(pf, block)) + goto error; + } + + + /* + * Optimizations are done so we turn off the optimization flag and + * put the rules right back into the regular codepath. + */ + pf->opts &= ~PF_OPT_OPTIMIZE; + + while ((block = TAILQ_FIRST(&superblocks))) { + TAILQ_REMOVE(&superblocks, block, sb_entry); + + while ((por = TAILQ_FIRST(&block->sb_rules))) { + TAILQ_REMOVE(&block->sb_rules, por, por_entry); + por->por_rule.nr = nr++; + if (pfctl_add_rule(pf, &por->por_rule, + por->por_anchor)) { + free(por); + goto error; + } + free(por); + } + free(block); + } + + return (0); + +error: + while ((por = TAILQ_FIRST(&pf->opt_queue))) { + TAILQ_REMOVE(&pf->opt_queue, por, por_entry); + if (por->por_src_tbl) { + pfr_buf_clear(por->por_src_tbl->pt_buf); + free(por->por_src_tbl->pt_buf); + free(por->por_src_tbl); + } + if (por->por_dst_tbl) { + pfr_buf_clear(por->por_dst_tbl->pt_buf); + free(por->por_dst_tbl->pt_buf); + free(por->por_dst_tbl); + } + free(por); + } + while ((block = TAILQ_FIRST(&superblocks))) { + TAILQ_REMOVE(&superblocks, block, sb_entry); + superblock_free(pf, block); + } + return (1); +} + + +/* + * Go ahead and optimize a superblock + */ +int +optimize_superblock(struct pfctl *pf, struct superblock *block) +{ +#ifdef OPT_DEBUG + struct pf_opt_rule *por; +#endif /* OPT_DEBUG */ + + /* We have a few optimization passes: + * 1) remove duplicate rules or rules that are a subset of other + * rules + * 2) combine otherwise identical rules with different IP addresses + * into a single rule and put the addresses in a table. + * 3) re-order the rules to improve kernel skip steps + * 4) re-order the 'quick' rules based on feedback from the + * active ruleset statistics + * + * XXX combine_rules() doesn't combine v4 and v6 rules. would just + * have to keep af in the table container, make af 'COMBINE' and + * twiddle the af on the merged rule + * XXX maybe add a weighting to the metric on skipsteps when doing + * reordering. sometimes two sequential tables will be better + * that four consecutive interfaces. + * XXX need to adjust the skipstep count of everything after PROTO, + * since they aren't actually checked on a proto mismatch in + * pf_test_{tcp, udp, icmp}() + * XXX should i treat proto=0, af=0 or dir=0 special in skepstep + * calculation since they are a DC? + * XXX keep last skiplist of last superblock to influence this + * superblock. '5 inet6 log' should make '3 inet6' come before '4 + * inet' in the next superblock. + * XXX would be useful to add tables for ports + * XXX we can also re-order some mutually exclusive superblocks to + * try merging superblocks before any of these optimization passes. + * for instance a single 'log in' rule in the middle of non-logging + * out rules. + */ + + /* shortcut. there will be alot of 1-rule superblocks */ + if (!TAILQ_NEXT(TAILQ_FIRST(&block->sb_rules), por_entry)) + return (0); + +#ifdef OPT_DEBUG + printf("--- Superblock ---\n"); + TAILQ_FOREACH(por, &block->sb_rules, por_entry) { + printf(" "); + print_rule(&por->por_rule, por->por_anchor, 1); + } +#endif /* OPT_DEBUG */ + + + if (remove_identical_rules(pf, block)) + return (1); + if (combine_rules(pf, block)) + return (1); + if ((pf->opts & PF_OPT_OPTIMIZE_PROFILE) && + TAILQ_FIRST(&block->sb_rules)->por_rule.quick && + block->sb_profiled_block) { + if (block_feedback(pf, block)) + return (1); + } else if (reorder_rules(pf, block, 0)) { + return (1); + } + + /* + * Don't add any optimization passes below reorder_rules(). It will + * have divided superblocks into smaller blocks for further refinement + * and doesn't put them back together again. What once was a true + * superblock might have been split into multiple superblocks. + */ + +#ifdef OPT_DEBUG + printf("--- END Superblock ---\n"); +#endif /* OPT_DEBUG */ + return (0); +} + + +/* + * Optimization pass #1: remove identical rules + */ +int +remove_identical_rules(struct pfctl *pf, struct superblock *block) +{ + struct pf_opt_rule *por1, *por2, *por_next, *por2_next; + struct pf_rule a, a2, b, b2; + + for (por1 = TAILQ_FIRST(&block->sb_rules); por1; por1 = por_next) { + por_next = TAILQ_NEXT(por1, por_entry); + for (por2 = por_next; por2; por2 = por2_next) { + por2_next = TAILQ_NEXT(por2, por_entry); + comparable_rule(&a, &por1->por_rule, DC); + comparable_rule(&b, &por2->por_rule, DC); + memcpy(&a2, &a, sizeof(a2)); + memcpy(&b2, &b, sizeof(b2)); + + exclude_supersets(&a, &b); + exclude_supersets(&b2, &a2); + if (memcmp(&a, &b, sizeof(a)) == 0) { + DEBUG("removing identical rule nr%d = *nr%d*", + por1->por_rule.nr, por2->por_rule.nr); + TAILQ_REMOVE(&block->sb_rules, por2, por_entry); + if (por_next == por2) + por_next = TAILQ_NEXT(por1, por_entry); + free(por2); + } else if (memcmp(&a2, &b2, sizeof(a2)) == 0) { + DEBUG("removing identical rule *nr%d* = nr%d", + por1->por_rule.nr, por2->por_rule.nr); + TAILQ_REMOVE(&block->sb_rules, por1, por_entry); + free(por1); + break; + } + } + } + + return (0); +} + + +/* + * Optimization pass #2: combine similar rules with different addresses + * into a single rule and a table + */ +int +combine_rules(struct pfctl *pf, struct superblock *block) +{ + struct pf_opt_rule *p1, *p2, *por_next; + int src_eq, dst_eq; + + if ((pf->loadopt & PFCTL_FLAG_TABLE) == 0) { + warnx("Must enable table loading for optimizations"); + return (1); + } + + /* First we make a pass to combine the rules. O(n log n) */ + TAILQ_FOREACH(p1, &block->sb_rules, por_entry) { + for (p2 = TAILQ_NEXT(p1, por_entry); p2; p2 = por_next) { + por_next = TAILQ_NEXT(p2, por_entry); + + src_eq = addrs_equal(&p1->por_rule.src, + &p2->por_rule.src); + dst_eq = addrs_equal(&p1->por_rule.dst, + &p2->por_rule.dst); + + if (src_eq && !dst_eq && p1->por_src_tbl == NULL && + p2->por_dst_tbl == NULL && + rules_combineable(&p1->por_rule, &p2->por_rule) && + addrs_combineable(&p1->por_rule.dst, + &p2->por_rule.dst)) { + DEBUG("can combine rules nr%d = nr%d", + p1->por_rule.nr, p2->por_rule.nr); + if (p1->por_dst_tbl == NULL && + add_opt_table(pf, &p1->por_dst_tbl, + p1->por_rule.af, &p1->por_rule.dst)) + return (1); + if (add_opt_table(pf, &p1->por_dst_tbl, + p1->por_rule.af, &p2->por_rule.dst)) + return (1); + p2->por_dst_tbl = p1->por_dst_tbl; + if (p1->por_dst_tbl->pt_rulecount >= + TABLE_THRESHOLD) { + TAILQ_REMOVE(&block->sb_rules, p2, + por_entry); + free(p2); + } + } else if (!src_eq && dst_eq && p1->por_dst_tbl == NULL + && p2->por_src_tbl == NULL && + rules_combineable(&p1->por_rule, &p2->por_rule) && + addrs_combineable(&p1->por_rule.src, + &p2->por_rule.src)) { + DEBUG("can combine rules nr%d = nr%d", + p1->por_rule.nr, p2->por_rule.nr); + if (p1->por_src_tbl == NULL && + add_opt_table(pf, &p1->por_src_tbl, + p1->por_rule.af, &p1->por_rule.src)) + return (1); + if (add_opt_table(pf, &p1->por_src_tbl, + p1->por_rule.af, &p2->por_rule.src)) + return (1); + p2->por_src_tbl = p1->por_src_tbl; + if (p1->por_src_tbl->pt_rulecount >= + TABLE_THRESHOLD) { + TAILQ_REMOVE(&block->sb_rules, p2, + por_entry); + free(p2); + } + } + } + } + + + /* + * Then we make a final pass to create a valid table name and + * insert the name into the rules. + */ + for (p1 = TAILQ_FIRST(&block->sb_rules); p1; p1 = por_next) { + por_next = TAILQ_NEXT(p1, por_entry); + assert(p1->por_src_tbl == NULL || p1->por_dst_tbl == NULL); + + if (p1->por_src_tbl && p1->por_src_tbl->pt_rulecount >= + TABLE_THRESHOLD) { + if (p1->por_src_tbl->pt_generated) { + /* This rule is included in a table */ + TAILQ_REMOVE(&block->sb_rules, p1, por_entry); + free(p1); + continue; + } + p1->por_src_tbl->pt_generated = 1; + + if ((pf->opts & PF_OPT_NOACTION) == 0 && + pf_opt_create_table(pf, p1->por_src_tbl)) + return (1); + + pf->tdirty = 1; + + if (pf->opts & PF_OPT_VERBOSE) + print_tabledef(p1->por_src_tbl->pt_name, + PFR_TFLAG_CONST, 1, + &p1->por_src_tbl->pt_nodes); + + memset(&p1->por_rule.src.addr, 0, + sizeof(p1->por_rule.src.addr)); + p1->por_rule.src.addr.type = PF_ADDR_TABLE; + strlcpy(p1->por_rule.src.addr.v.tblname, + p1->por_src_tbl->pt_name, + sizeof(p1->por_rule.src.addr.v.tblname)); + + pfr_buf_clear(p1->por_src_tbl->pt_buf); + free(p1->por_src_tbl->pt_buf); + p1->por_src_tbl->pt_buf = NULL; + } + if (p1->por_dst_tbl && p1->por_dst_tbl->pt_rulecount >= + TABLE_THRESHOLD) { + if (p1->por_dst_tbl->pt_generated) { + /* This rule is included in a table */ + TAILQ_REMOVE(&block->sb_rules, p1, por_entry); + free(p1); + continue; + } + p1->por_dst_tbl->pt_generated = 1; + + if ((pf->opts & PF_OPT_NOACTION) == 0 && + pf_opt_create_table(pf, p1->por_dst_tbl)) + return (1); + pf->tdirty = 1; + + if (pf->opts & PF_OPT_VERBOSE) + print_tabledef(p1->por_dst_tbl->pt_name, + PFR_TFLAG_CONST, 1, + &p1->por_dst_tbl->pt_nodes); + + memset(&p1->por_rule.dst.addr, 0, + sizeof(p1->por_rule.dst.addr)); + p1->por_rule.dst.addr.type = PF_ADDR_TABLE; + strlcpy(p1->por_rule.dst.addr.v.tblname, + p1->por_dst_tbl->pt_name, + sizeof(p1->por_rule.dst.addr.v.tblname)); + + pfr_buf_clear(p1->por_dst_tbl->pt_buf); + free(p1->por_dst_tbl->pt_buf); + p1->por_dst_tbl->pt_buf = NULL; + } + } + + return (0); +} + + +/* + * Optimization pass #3: re-order rules to improve skip steps + */ +int +reorder_rules(struct pfctl *pf, struct superblock *block, int depth) +{ + struct superblock *newblock; + struct pf_skip_step *skiplist; + struct pf_opt_rule *por; + int i, largest, largest_list, rule_count = 0; + TAILQ_HEAD( , pf_opt_rule) head; + + /* + * Calculate the best-case skip steps. We put each rule in a list + * of other rules with common fields + */ + for (i = 0; i < PF_SKIP_COUNT; i++) { + TAILQ_FOREACH(por, &block->sb_rules, por_entry) { + TAILQ_FOREACH(skiplist, &block->sb_skipsteps[i], + ps_entry) { + if (skip_compare(i, skiplist, por) == 0) + break; + } + if (skiplist == NULL) { + if ((skiplist = calloc(1, sizeof(*skiplist))) == + NULL) + err(1, "calloc"); + TAILQ_INIT(&skiplist->ps_rules); + TAILQ_INSERT_TAIL(&block->sb_skipsteps[i], + skiplist, ps_entry); + } + skip_append(block, i, skiplist, por); + } + } + + TAILQ_FOREACH(por, &block->sb_rules, por_entry) + rule_count++; + + /* + * Now we're going to ignore any fields that are identical between + * all of the rules in the superblock and those fields which differ + * between every rule in the superblock. + */ + largest = 0; + for (i = 0; i < PF_SKIP_COUNT; i++) { + skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); + if (skiplist->ps_count == rule_count) { + DEBUG("(%d) original skipstep '%s' is all rules", + depth, skip_comparitors_names[i]); + skiplist->ps_count = 0; + } else if (skiplist->ps_count == 1) { + skiplist->ps_count = 0; + } else { + DEBUG("(%d) original skipstep '%s' largest jump is %d", + depth, skip_comparitors_names[i], + skiplist->ps_count); + if (skiplist->ps_count > largest) + largest = skiplist->ps_count; + } + } + if (largest == 0) { + /* Ugh. There is NO commonality in the superblock on which + * optimize the skipsteps optimization. + */ + goto done; + } + + /* + * Now we're going to empty the superblock rule list and re-create + * it based on a more optimal skipstep order. + */ + TAILQ_INIT(&head); + while ((por = TAILQ_FIRST(&block->sb_rules))) { + TAILQ_REMOVE(&block->sb_rules, por, por_entry); + TAILQ_INSERT_TAIL(&head, por, por_entry); + } + + + while (!TAILQ_EMPTY(&head)) { + largest = 1; + + /* + * Find the most useful skip steps remaining + */ + for (i = 0; i < PF_SKIP_COUNT; i++) { + skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); + if (skiplist->ps_count > largest) { + largest = skiplist->ps_count; + largest_list = i; + } + } + + if (largest <= 1) { + /* + * Nothing useful left. Leave remaining rules in order. + */ + DEBUG("(%d) no more commonality for skip steps", depth); + while ((por = TAILQ_FIRST(&head))) { + TAILQ_REMOVE(&head, por, por_entry); + TAILQ_INSERT_TAIL(&block->sb_rules, por, + por_entry); + } + } else { + /* + * There is commonality. Extract those common rules + * and place them in the ruleset adjacent to each + * other. + */ + skiplist = TAILQ_FIRST(&block->sb_skipsteps[ + largest_list]); + DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d", + depth, skip_comparitors_names[largest_list], + largest, TAILQ_FIRST(&TAILQ_FIRST(&block-> + sb_skipsteps [largest_list])->ps_rules)-> + por_rule.nr); + TAILQ_REMOVE(&block->sb_skipsteps[largest_list], + skiplist, ps_entry); + + + /* + * There may be further commonality inside these + * rules. So we'll split them off into they're own + * superblock and pass it back into the optimizer. + */ + if (skiplist->ps_count > 2) { + if ((newblock = calloc(1, sizeof(*newblock))) + == NULL) { + warn("calloc"); + return (1); + } + TAILQ_INIT(&newblock->sb_rules); + for (i = 0; i < PF_SKIP_COUNT; i++) + TAILQ_INIT(&newblock->sb_skipsteps[i]); + TAILQ_INSERT_BEFORE(block, newblock, sb_entry); + DEBUG("(%d) splitting off %d rules from superblock @ #%d", + depth, skiplist->ps_count, + TAILQ_FIRST(&skiplist->ps_rules)-> + por_rule.nr); + } else { + newblock = block; + } + + while ((por = TAILQ_FIRST(&skiplist->ps_rules))) { + TAILQ_REMOVE(&head, por, por_entry); + TAILQ_REMOVE(&skiplist->ps_rules, por, + por_skip_entry[largest_list]); + TAILQ_INSERT_TAIL(&newblock->sb_rules, por, + por_entry); + + /* Remove this rule from all other skiplists */ + remove_from_skipsteps(&block->sb_skipsteps[ + largest_list], block, por, skiplist); + } + free(skiplist); + if (newblock != block) + if (reorder_rules(pf, newblock, depth + 1)) + return (1); + } + } + +done: + for (i = 0; i < PF_SKIP_COUNT; i++) { + while ((skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]))) { + TAILQ_REMOVE(&block->sb_skipsteps[i], skiplist, + ps_entry); + free(skiplist); + } + } + + return (0); +} + + +/* + * Optimization pass #4: re-order 'quick' rules based on feedback from the + * currently running ruleset + */ +int +block_feedback(struct pfctl *pf, struct superblock *block) +{ + TAILQ_HEAD( , pf_opt_rule) queue; + struct pf_opt_rule *por1, *por2; + u_int64_t total_count = 0; + struct pf_rule a, b; + + + /* + * Walk through all of the profiled superblock's rules and copy + * the counters onto our rules. + */ + TAILQ_FOREACH(por1, &block->sb_profiled_block->sb_rules, por_entry) { + comparable_rule(&a, &por1->por_rule, DC); + total_count += por1->por_rule.packets; + TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { + if (por2->por_profile_count) + continue; + comparable_rule(&b, &por2->por_rule, DC); + if (memcmp(&a, &b, sizeof(a)) == 0) { + por2->por_profile_count = + por1->por_rule.packets; + break; + } + } + } + superblock_free(pf, block->sb_profiled_block); + block->sb_profiled_block = NULL; + + /* + * Now we pull all of the rules off the superblock and re-insert them + * in sorted order. + */ + + TAILQ_INIT(&queue); + while ((por1 = TAILQ_FIRST(&block->sb_rules)) != NULL) { + TAILQ_REMOVE(&block->sb_rules, por1, por_entry); + TAILQ_INSERT_TAIL(&queue, por1, por_entry); + } + + while ((por1 = TAILQ_FIRST(&queue)) != NULL) { + TAILQ_REMOVE(&queue, por1, por_entry); +/* XXX I should sort all of the unused rules based on skip steps */ + TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { + if (por1->por_profile_count > por2->por_profile_count) { + TAILQ_INSERT_BEFORE(por2, por1, por_entry); + break; + } + } + if (por2 == TAILQ_END(&block->sb_rules)) + TAILQ_INSERT_TAIL(&block->sb_rules, por1, por_entry); + } + + return (0); +} + + +/* + * Load the current ruleset from the kernel and try to associate them with + * the ruleset we're optimizing. + */ +int +load_feedback_profile(struct pfctl *pf, struct superblocks *superblocks) +{ + struct superblock *block, *blockcur; + struct superblocks prof_superblocks; + struct pf_opt_rule *por; + struct pf_opt_queue queue; + struct pfioc_rule pr; + struct pf_rule a, b; + int nr, mnr; + + TAILQ_INIT(&queue); + TAILQ_INIT(&prof_superblocks); + + memset(&pr, 0, sizeof(pr)); + pr.rule.action = PF_PASS; + if (ioctl(pf->dev, DIOCGETRULES, &pr)) { + warn("DIOCGETRULES"); + return (1); + } + mnr = pr.nr; + + DEBUG("Loading %d active rules for a feedback profile", mnr); + for (nr = 0; nr < mnr; ++nr) { + if ((por = calloc(1, sizeof(*por))) == NULL) { + warn("calloc"); + return (1); + } + pr.nr = nr; + if (ioctl(pf->dev, DIOCGETRULE, &pr)) { + warn("DIOCGETRULES"); + return (1); + } + memcpy(&por->por_rule, &pr.rule, sizeof(por->por_rule)); + strlcpy(por->por_anchor, pr.anchor_call, + sizeof(por->por_anchor)); + if (TAILQ_EMPTY(&por->por_rule.rpool.list)) + memset(&por->por_rule.rpool, 0, + sizeof(por->por_rule.rpool)); + TAILQ_INSERT_TAIL(&queue, por, por_entry); + + /* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket, + * PF_PASS, pf->anchor) ??? + * ... pfctl_clear_pool(&pr.rule.rpool) + */ + } + + if (construct_superblocks(pf, &queue, &prof_superblocks)) + return (1); + + + /* + * Now we try to associate the active ruleset's superblocks with + * the superblocks we're compiling. + */ + block = TAILQ_FIRST(superblocks); + blockcur = TAILQ_FIRST(&prof_superblocks); + while (block && blockcur) { + comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, + BREAK); + comparable_rule(&b, &TAILQ_FIRST(&blockcur->sb_rules)->por_rule, + BREAK); + if (memcmp(&a, &b, sizeof(a)) == 0) { + /* The two superblocks lined up */ + block->sb_profiled_block = blockcur; + } else { + DEBUG("superblocks don't line up between #%d and #%d", + TAILQ_FIRST(&block->sb_rules)->por_rule.nr, + TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr); + break; + } + block = TAILQ_NEXT(block, sb_entry); + blockcur = TAILQ_NEXT(blockcur, sb_entry); + } + + + + /* Free any superblocks we couldn't link */ + while (blockcur) { + block = TAILQ_NEXT(blockcur, sb_entry); + superblock_free(pf, blockcur); + blockcur = block; + } + return (0); +} + + +/* + * Compare a rule to a skiplist to see if the rule is a member + */ +int +skip_compare(int skipnum, struct pf_skip_step *skiplist, + struct pf_opt_rule *por) +{ + struct pf_rule *a, *b; + if (skipnum >= PF_SKIP_COUNT || skipnum < 0) + errx(1, "skip_compare() out of bounds"); + a = &por->por_rule; + b = &TAILQ_FIRST(&skiplist->ps_rules)->por_rule; + + return ((skip_comparitors[skipnum])(a, b)); +} + + +/* + * Add a rule to a skiplist + */ +void +skip_append(struct superblock *superblock, int skipnum, + struct pf_skip_step *skiplist, struct pf_opt_rule *por) +{ + struct pf_skip_step *prev; + + skiplist->ps_count++; + TAILQ_INSERT_TAIL(&skiplist->ps_rules, por, por_skip_entry[skipnum]); + + /* Keep the list of skiplists sorted by whichever is larger */ + while ((prev = TAILQ_PREV(skiplist, skiplist, ps_entry)) && + prev->ps_count < skiplist->ps_count) { + TAILQ_REMOVE(&superblock->sb_skipsteps[skipnum], + skiplist, ps_entry); + TAILQ_INSERT_BEFORE(prev, skiplist, ps_entry); + } +} + + +/* + * Remove a rule from the other skiplist calculations. + */ +void +remove_from_skipsteps(struct skiplist *head, struct superblock *block, + struct pf_opt_rule *por, struct pf_skip_step *active_list) +{ + struct pf_skip_step *sk, *next; + struct pf_opt_rule *p2; + int i, found; + + for (i = 0; i < PF_SKIP_COUNT; i++) { + sk = TAILQ_FIRST(&block->sb_skipsteps[i]); + if (sk == NULL || sk == active_list || sk->ps_count <= 1) + continue; + found = 0; + do { + TAILQ_FOREACH(p2, &sk->ps_rules, por_skip_entry[i]) + if (p2 == por) { + TAILQ_REMOVE(&sk->ps_rules, p2, + por_skip_entry[i]); + found = 1; + sk->ps_count--; + break; + } + } while (!found && (sk = TAILQ_NEXT(sk, ps_entry))); + if (found && sk) { + /* Does this change the sorting order? */ + while ((next = TAILQ_NEXT(sk, ps_entry)) && + next->ps_count > sk->ps_count) { + TAILQ_REMOVE(head, sk, ps_entry); + TAILQ_INSERT_AFTER(head, next, sk, ps_entry); + } +#ifdef OPT_DEBUG + next = TAILQ_NEXT(sk, ps_entry); + assert(next == NULL || next->ps_count <= sk->ps_count); +#endif /* OPT_DEBUG */ + + } + } +} + + +/* Compare two rules AF field for skiplist construction */ +int +skip_cmp_af(struct pf_rule *a, struct pf_rule *b) +{ + if (a->af != b->af || a->af == 0) + return (1); + return (0); +} + +/* Compare two rules DIRECTION field for skiplist construction */ +int +skip_cmp_dir(struct pf_rule *a, struct pf_rule *b) +{ + if (a->direction == 0 || a->direction != b->direction) + return (1); + return (0); +} + +/* Compare two rules DST Address field for skiplist construction */ +int +skip_cmp_dst_addr(struct pf_rule *a, struct pf_rule *b) +{ + if (a->dst.neg != b->dst.neg || + a->dst.addr.type != b->dst.addr.type) + return (1); + /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 + * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || + * a->proto == IPPROTO_ICMP + * return (1); + */ + switch (a->dst.addr.type) { + case PF_ADDR_ADDRMASK: + if (memcmp(&a->dst.addr.v.a.addr, &b->dst.addr.v.a.addr, + sizeof(a->dst.addr.v.a.addr)) || + memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, + sizeof(a->dst.addr.v.a.mask)) || + (a->dst.addr.v.a.addr.addr32[0] == 0 && + a->dst.addr.v.a.addr.addr32[1] == 0 && + a->dst.addr.v.a.addr.addr32[2] == 0 && + a->dst.addr.v.a.addr.addr32[3] == 0)) + return (1); + return (0); + case PF_ADDR_DYNIFTL: + if (strcmp(a->dst.addr.v.ifname, b->dst.addr.v.ifname) != 0 || + a->dst.addr.iflags != a->dst.addr.iflags || + memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, + sizeof(a->dst.addr.v.a.mask))) + return (1); + return (0); + case PF_ADDR_NOROUTE: + return (0); + case PF_ADDR_TABLE: + return (strcmp(a->dst.addr.v.tblname, b->dst.addr.v.tblname)); + } + return (1); +} + +/* Compare two rules DST port field for skiplist construction */ +int +skip_cmp_dst_port(struct pf_rule *a, struct pf_rule *b) +{ + /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 + * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || + * a->proto == IPPROTO_ICMP + * return (1); + */ + if (a->dst.port_op == PF_OP_NONE || a->dst.port_op != b->dst.port_op || + a->dst.port[0] != b->dst.port[0] || + a->dst.port[1] != b->dst.port[1]) + return (1); + return (0); +} + +/* Compare two rules IFP field for skiplist construction */ +int +skip_cmp_ifp(struct pf_rule *a, struct pf_rule *b) +{ + if (strcmp(a->ifname, b->ifname) || a->ifname[0] == '\0') + return (1); + return (a->ifnot != b->ifnot); +} + +/* Compare two rules PROTO field for skiplist construction */ +int +skip_cmp_proto(struct pf_rule *a, struct pf_rule *b) +{ + return (a->proto != b->proto || a->proto == 0); +} + +/* Compare two rules SRC addr field for skiplist construction */ +int +skip_cmp_src_addr(struct pf_rule *a, struct pf_rule *b) +{ + if (a->src.neg != b->src.neg || + a->src.addr.type != b->src.addr.type) + return (1); + /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 + * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || + * a->proto == IPPROTO_ICMP + * return (1); + */ + switch (a->src.addr.type) { + case PF_ADDR_ADDRMASK: + if (memcmp(&a->src.addr.v.a.addr, &b->src.addr.v.a.addr, + sizeof(a->src.addr.v.a.addr)) || + memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, + sizeof(a->src.addr.v.a.mask)) || + (a->src.addr.v.a.addr.addr32[0] == 0 && + a->src.addr.v.a.addr.addr32[1] == 0 && + a->src.addr.v.a.addr.addr32[2] == 0 && + a->src.addr.v.a.addr.addr32[3] == 0)) + return (1); + return (0); + case PF_ADDR_DYNIFTL: + if (strcmp(a->src.addr.v.ifname, b->src.addr.v.ifname) != 0 || + a->src.addr.iflags != a->src.addr.iflags || + memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, + sizeof(a->src.addr.v.a.mask))) + return (1); + return (0); + case PF_ADDR_NOROUTE: + return (0); + case PF_ADDR_TABLE: + return (strcmp(a->src.addr.v.tblname, b->src.addr.v.tblname)); + } + return (1); +} + +/* Compare two rules SRC port field for skiplist construction */ +int +skip_cmp_src_port(struct pf_rule *a, struct pf_rule *b) +{ + if (a->src.port_op == PF_OP_NONE || a->src.port_op != b->src.port_op || + a->src.port[0] != b->src.port[0] || + a->src.port[1] != b->src.port[1]) + return (1); + /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 + * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || + * a->proto == IPPROTO_ICMP + * return (1); + */ + return (0); +} + + +void +skip_init(void) +{ + struct { + char *name; + int skipnum; + int (*func)(struct pf_rule *, struct pf_rule *); + } comps[] = PF_SKIP_COMPARITORS; + int skipnum, i; + + for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) { + for (i = 0; i < sizeof(comps)/sizeof(*comps); i++) + if (comps[i].skipnum == skipnum) { + skip_comparitors[skipnum] = comps[i].func; + skip_comparitors_names[skipnum] = comps[i].name; + } + } + for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) + if (skip_comparitors[skipnum] == NULL) + errx(1, "Need to add skip step comparitor to pfctl?!"); +} + +/* + * Add a host/netmask to a table + */ +int +add_opt_table(struct pfctl *pf, struct pf_opt_tbl **tbl, sa_family_t af, + struct pf_rule_addr *addr) +{ +#ifdef OPT_DEBUG + char buf[128]; +#endif /* OPT_DEBUG */ + static int tablenum = 0; + struct node_host node_host; + + if (*tbl == NULL) { + if ((*tbl = calloc(1, sizeof(**tbl))) == NULL || + ((*tbl)->pt_buf = calloc(1, sizeof(*(*tbl)->pt_buf))) == + NULL) + err(1, "calloc"); + (*tbl)->pt_buf->pfrb_type = PFRB_ADDRS; + SIMPLEQ_INIT(&(*tbl)->pt_nodes); + + /* This is just a temporary table name */ + snprintf((*tbl)->pt_name, sizeof((*tbl)->pt_name), "%s%d", + PF_OPT_TABLE_PREFIX, tablenum++); + DEBUG("creating table <%s>", (*tbl)->pt_name); + } + + memset(&node_host, 0, sizeof(node_host)); + node_host.af = af; + node_host.addr = addr->addr; + +#ifdef OPT_DEBUG + DEBUG("<%s> adding %s/%d", (*tbl)->pt_name, inet_ntop(af, + &node_host.addr.v.a.addr, buf, sizeof(buf)), + unmask(&node_host.addr.v.a.mask, af)); +#endif /* OPT_DEBUG */ + + if (append_addr_host((*tbl)->pt_buf, &node_host, 0, 0)) + return (1); + if (pf->opts & PF_OPT_VERBOSE) { + struct node_tinit *ti; + + if ((ti = calloc(1, sizeof(*ti))) == NULL) + err(1, "malloc"); + if ((ti->host = malloc(sizeof(*ti->host))) == NULL) + err(1, "malloc"); + memcpy(ti->host, &node_host, sizeof(*ti->host)); + SIMPLEQ_INSERT_TAIL(&(*tbl)->pt_nodes, ti, entries); + } + + (*tbl)->pt_rulecount++; + if ((*tbl)->pt_rulecount == TABLE_THRESHOLD) + DEBUG("table <%s> now faster than skip steps", (*tbl)->pt_name); + + return (0); +} + + +/* + * Do the dirty work of choosing an unused table name and creating it. + * (be careful with the table name, it might already be used in another anchor) + */ +int +pf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl) +{ + static int tablenum; + struct pfr_table *t; + + if (table_buffer.pfrb_type == 0) { + /* Initialize the list of tables */ + table_buffer.pfrb_type = PFRB_TABLES; + for (;;) { + pfr_buf_grow(&table_buffer, table_buffer.pfrb_size); + table_buffer.pfrb_size = table_buffer.pfrb_msize; + if (pfr_get_tables(NULL, table_buffer.pfrb_caddr, + &table_buffer.pfrb_size, PFR_FLAG_ALLRSETS)) + err(1, "pfr_get_tables"); + if (table_buffer.pfrb_size <= table_buffer.pfrb_msize) + break; + } + table_identifier = arc4random(); + } + + /* XXX would be *really* nice to avoid duplicating identical tables */ + + /* Now we have to pick a table name that isn't used */ +again: + DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl->pt_name, + PF_OPT_TABLE_PREFIX, table_identifier, tablenum); + snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d", + PF_OPT_TABLE_PREFIX, table_identifier, tablenum); + PFRB_FOREACH(t, &table_buffer) { + if (strcasecmp(t->pfrt_name, tbl->pt_name) == 0) { + /* Collision. Try again */ + DEBUG("wow, table <%s> in use. trying again", + tbl->pt_name); + table_identifier = arc4random(); + goto again; + } + } + tablenum++; + + + if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1, pf->anchor, + tbl->pt_buf, pf->tticket)) + return (1); + return (0); +} + +/* + * Partition the flat ruleset into a list of distinct superblocks + */ +int +construct_superblocks(struct pfctl *pf, struct pf_opt_queue *opt_queue, + struct superblocks *superblocks) +{ + struct superblock *block = NULL; + struct pf_opt_rule *por; + int i; + + while (!TAILQ_EMPTY(opt_queue)) { + por = TAILQ_FIRST(opt_queue); + TAILQ_REMOVE(opt_queue, por, por_entry); + if (block == NULL || !superblock_inclusive(block, por)) { + if ((block = calloc(1, sizeof(*block))) == NULL) { + warn("calloc"); + return (1); + } + TAILQ_INIT(&block->sb_rules); + for (i = 0; i < PF_SKIP_COUNT; i++) + TAILQ_INIT(&block->sb_skipsteps[i]); + TAILQ_INSERT_TAIL(superblocks, block, sb_entry); + } + TAILQ_INSERT_TAIL(&block->sb_rules, por, por_entry); + } + + return (0); +} + + +/* + * Compare two rule addresses + */ +int +addrs_equal(struct pf_rule_addr *a, struct pf_rule_addr *b) +{ + if (a->neg != b->neg) + return (0); + return (memcmp(&a->addr, &b->addr, sizeof(a->addr)) == 0); +} + + +/* + * The addresses are not equal, but can we combine them into one table? + */ +int +addrs_combineable(struct pf_rule_addr *a, struct pf_rule_addr *b) +{ + if (a->addr.type != PF_ADDR_ADDRMASK && + b->addr.type != PF_ADDR_ADDRMASK) + return (0); + if (a->neg != b->neg || a->port_op != b->port_op || + a->port[0] != b->port[0] || a->port[1] != b->port[1]) + return (0); + return (1); +} + + +/* + * Are we allowed to combine these two rules + */ +int +rules_combineable(struct pf_rule *p1, struct pf_rule *p2) +{ + struct pf_rule a, b; + + comparable_rule(&a, p1, COMBINED); + comparable_rule(&b, p2, COMBINED); + return (memcmp(&a, &b, sizeof(a)) == 0); +} + + +/* + * Can a rule be included inside a superblock + */ +int +superblock_inclusive(struct superblock *block, struct pf_opt_rule *por) +{ + struct pf_rule a, b; + int i, j; + + /* First check for hard breaks */ + for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) { + if (pf_rule_desc[i].prf_type == BARRIER) { + for (j = 0; j < pf_rule_desc[i].prf_size; j++) + if (((char *)&por->por_rule)[j + + pf_rule_desc[i].prf_offset] != 0) + return (0); + } + } + + /* 'anchor' heads and per-rule src-track are also hard breaks */ + if (por->por_anchor[0] != '\0' || + (por->por_rule.rule_flag & PFRULE_RULESRCTRACK)) + return (0); + + comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE); + comparable_rule(&b, &por->por_rule, NOMERGE); + if (strcmp(TAILQ_FIRST(&block->sb_rules)->por_anchor, + por->por_anchor) == 0 && memcmp(&a, &b, sizeof(a)) == 0) + return (1); + +#ifdef OPT_DEBUG + for (i = 0; i < sizeof(por->por_rule); i++) { + int closest = -1; + if (((u_int8_t *)&a)[i] != ((u_int8_t *)&b)[i]) { + for (j = 0; j < sizeof(pf_rule_desc) / + sizeof(*pf_rule_desc); j++) { + if (i >= pf_rule_desc[j].prf_offset && + i < pf_rule_desc[j].prf_offset + + pf_rule_desc[j].prf_size) { + DEBUG("superblock break @ %d due to %s", + por->por_rule.nr, + pf_rule_desc[j].prf_name); + return (0); + } + if (i > pf_rule_desc[j].prf_offset) { + if (closest == -1 || + i-pf_rule_desc[j].prf_offset < + i-pf_rule_desc[closest].prf_offset) + closest = j; + } + } + + if (closest >= 0) + DEBUG("superblock break @ %d on %s+%xh", + por->por_rule.nr, + pf_rule_desc[closest].prf_name, + i - pf_rule_desc[closest].prf_offset - + pf_rule_desc[closest].prf_size); + else + DEBUG("superblock break @ %d on field @ %d", + por->por_rule.nr, i); + return (0); + } + } +#endif /* OPT_DEBUG */ + + return (0); +} + + +/* + * Make a rule that can directly compared by memcmp() + */ +void +comparable_rule(struct pf_rule *dst, const struct pf_rule *src, int type) +{ + int i; + /* + * To simplify the comparison, we just zero out the fields that are + * allowed to be different and then do a simple memcmp() + */ + memcpy(dst, src, sizeof(*dst)); + for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) + if (pf_rule_desc[i].prf_type >= type) { +#ifdef OPT_DEBUG + assert(pf_rule_desc[i].prf_type != NEVER || + *(((char *)dst) + pf_rule_desc[i].prf_offset) == 0); +#endif /* OPT_DEBUG */ + memset(((char *)dst) + pf_rule_desc[i].prf_offset, 0, + pf_rule_desc[i].prf_size); + } +} + + +/* + * Remove superset information from two rules so we can directly compare them + * with memcmp() + */ +void +exclude_supersets(struct pf_rule *super, struct pf_rule *sub) +{ + if (super->ifname[0] == '\0') + memset(sub->ifname, 0, sizeof(sub->ifname)); + if (super->direction == PF_INOUT) + sub->direction = PF_INOUT; + if ((super->proto == 0 || super->proto == sub->proto) && + super->flags == 0 && super->flagset == 0 && (sub->flags || + sub->flagset)) { + sub->flags = super->flags; + sub->flagset = super->flagset; + } + if (super->proto == 0) + sub->proto = 0; + + if (super->src.port_op == 0) { + sub->src.port_op = 0; + sub->src.port[0] = 0; + sub->src.port[1] = 0; + } + if (super->dst.port_op == 0) { + sub->dst.port_op = 0; + sub->dst.port[0] = 0; + sub->dst.port[1] = 0; + } + + if (super->src.addr.type == PF_ADDR_ADDRMASK && !super->src.neg && + !sub->src.neg && super->src.addr.v.a.mask.addr32[0] == 0 && + super->src.addr.v.a.mask.addr32[1] == 0 && + super->src.addr.v.a.mask.addr32[2] == 0 && + super->src.addr.v.a.mask.addr32[3] == 0) + memset(&sub->src.addr, 0, sizeof(sub->src.addr)); + else if (super->src.addr.type == PF_ADDR_ADDRMASK && + sub->src.addr.type == PF_ADDR_ADDRMASK && + super->src.neg == sub->src.neg && + super->af == sub->af && + unmask(&super->src.addr.v.a.mask, super->af) < + unmask(&sub->src.addr.v.a.mask, sub->af) && + super->src.addr.v.a.addr.addr32[0] == + (sub->src.addr.v.a.addr.addr32[0] & + super->src.addr.v.a.mask.addr32[0]) && + super->src.addr.v.a.addr.addr32[1] == + (sub->src.addr.v.a.addr.addr32[1] & + super->src.addr.v.a.mask.addr32[1]) && + super->src.addr.v.a.addr.addr32[2] == + (sub->src.addr.v.a.addr.addr32[2] & + super->src.addr.v.a.mask.addr32[2]) && + super->src.addr.v.a.addr.addr32[3] == + (sub->src.addr.v.a.addr.addr32[3] & + super->src.addr.v.a.mask.addr32[3])) { + /* sub->src.addr is a subset of super->src.addr/mask */ + memcpy(&sub->src.addr, &super->src.addr, sizeof(sub->src.addr)); + } + + if (super->dst.addr.type == PF_ADDR_ADDRMASK && !super->dst.neg && + !sub->dst.neg && super->dst.addr.v.a.mask.addr32[0] == 0 && + super->dst.addr.v.a.mask.addr32[1] == 0 && + super->dst.addr.v.a.mask.addr32[2] == 0 && + super->dst.addr.v.a.mask.addr32[3] == 0) + memset(&sub->dst.addr, 0, sizeof(sub->dst.addr)); + else if (super->dst.addr.type == PF_ADDR_ADDRMASK && + sub->dst.addr.type == PF_ADDR_ADDRMASK && + super->dst.neg == sub->dst.neg && + super->af == sub->af && + unmask(&super->dst.addr.v.a.mask, super->af) < + unmask(&sub->dst.addr.v.a.mask, sub->af) && + super->dst.addr.v.a.addr.addr32[0] == + (sub->dst.addr.v.a.addr.addr32[0] & + super->dst.addr.v.a.mask.addr32[0]) && + super->dst.addr.v.a.addr.addr32[1] == + (sub->dst.addr.v.a.addr.addr32[1] & + super->dst.addr.v.a.mask.addr32[1]) && + super->dst.addr.v.a.addr.addr32[2] == + (sub->dst.addr.v.a.addr.addr32[2] & + super->dst.addr.v.a.mask.addr32[2]) && + super->dst.addr.v.a.addr.addr32[3] == + (sub->dst.addr.v.a.addr.addr32[3] & + super->dst.addr.v.a.mask.addr32[3])) { + /* sub->dst.addr is a subset of super->dst.addr/mask */ + memcpy(&sub->dst.addr, &super->dst.addr, sizeof(sub->dst.addr)); + } + + if (super->af == 0) + sub->af = 0; +} + + +void +superblock_free(struct pfctl *pf, struct superblock *block) +{ + struct pf_opt_rule *por; + while ((por = TAILQ_FIRST(&block->sb_rules))) { + TAILQ_REMOVE(&block->sb_rules, por, por_entry); + if (por->por_src_tbl) { + if (por->por_src_tbl->pt_buf) { + pfr_buf_clear(por->por_src_tbl->pt_buf); + free(por->por_src_tbl->pt_buf); + } + free(por->por_src_tbl); + } + if (por->por_dst_tbl) { + if (por->por_dst_tbl->pt_buf) { + pfr_buf_clear(por->por_dst_tbl->pt_buf); + free(por->por_dst_tbl->pt_buf); + } + free(por->por_dst_tbl); + } + free(por); + } + if (block->sb_profiled_block) + superblock_free(pf, block->sb_profiled_block); + free(block); +} + diff --git a/sbin/pfctl/pfctl_parser.c b/sbin/pfctl/pfctl_parser.c index 0d0aaf54278..e83ae9eab95 100644 --- a/sbin/pfctl/pfctl_parser.c +++ b/sbin/pfctl/pfctl_parser.c @@ -1,4 +1,4 @@ -/* $OpenBSD: pfctl_parser.c,v 1.202 2004/06/29 22:14:13 henning Exp $ */ +/* $OpenBSD: pfctl_parser.c,v 1.203 2004/07/16 23:44:25 frantzen Exp $ */ /* * Copyright (c) 2001 Daniel Hartmeier @@ -966,9 +966,7 @@ set_ipmask(struct node_host *h, u_int8_t b) int i, j = 0; m = &h->addr.v.a.mask; - - for (i = 0; i < 4; i++) - m->addr32[i] = 0; + memset(m, 0, sizeof(*m)); while (b >= 32) { m->addr32[j++] = 0xffffffff; diff --git a/sbin/pfctl/pfctl_parser.h b/sbin/pfctl/pfctl_parser.h index d16abc4d599..b069b8236d4 100644 --- a/sbin/pfctl/pfctl_parser.h +++ b/sbin/pfctl/pfctl_parser.h @@ -1,4 +1,4 @@ -/* $OpenBSD: pfctl_parser.h,v 1.76 2004/05/19 17:50:51 dhartmei Exp $ */ +/* $OpenBSD: pfctl_parser.h,v 1.77 2004/07/16 23:44:25 frantzen Exp $ */ /* * Copyright (c) 2001 Daniel Hartmeier @@ -46,6 +46,8 @@ #define PF_OPT_DUMMYACTION 0x0100 #define PF_OPT_DEBUG 0x0200 #define PF_OPT_SHOWALL 0x0400 +#define PF_OPT_OPTIMIZE 0x0800 +#define PF_OPT_OPTIMIZE_PROFILE 0x1000 #define PF_TH_ALL 0xFF @@ -59,6 +61,11 @@ NULL \ } +struct pfr_buffer; /* forward definition */ +struct pf_opt_rule; +TAILQ_HEAD(pf_opt_queue, pf_opt_rule); + + struct pfctl { int dev; int opts; @@ -72,6 +79,7 @@ struct pfctl { struct pfr_buffer *trans; const char *anchor; const char *ruleset; + struct pf_opt_queue opt_queue; }; struct node_if { @@ -142,9 +150,31 @@ struct node_tinit { /* table initializer */ char *file; }; -struct pfr_buffer; /* forward definition */ + +/* optimizer created tables */ +struct pf_opt_tbl { + char pt_name[PF_TABLE_NAME_SIZE]; + int pt_rulecount; + int pt_generated; + struct node_tinithead pt_nodes; + struct pfr_buffer *pt_buf; +}; +#define PF_OPT_TABLE_PREFIX "__automatic_" + +/* optimizer pf_rule container */ +struct pf_opt_rule { + struct pf_rule por_rule; + struct pf_opt_tbl *por_src_tbl; + struct pf_opt_tbl *por_dst_tbl; + char por_anchor[MAXPATHLEN]; + u_int64_t por_profile_count; + TAILQ_ENTRY(pf_opt_rule) por_entry; + TAILQ_ENTRY(pf_opt_rule) por_skip_entry[PF_SKIP_COUNT]; +}; + int pfctl_rules(int, char *, int, char *, struct pfr_buffer *); +int pfctl_optimize_rules(struct pfctl *); int pfctl_add_rule(struct pfctl *, struct pf_rule *, const char *); int pfctl_add_altq(struct pfctl *, struct pf_altq *); @@ -220,6 +250,7 @@ extern const struct pf_timeout pf_timeouts[]; void set_ipmask(struct node_host *, u_int8_t); int check_netmask(struct node_host *, sa_family_t); +int unmask(struct pf_addr *, sa_family_t); void ifa_load(void); struct node_host *ifa_exists(const char *, int); struct node_host *ifa_lookup(const char *, int); |