diff options
Diffstat (limited to 'freebsd/sbin/pfctl/pfctl_optimize.c')
| -rw-r--r-- | freebsd/sbin/pfctl/pfctl_optimize.c | 1705 |
1 files changed, 1705 insertions, 0 deletions
diff --git a/freebsd/sbin/pfctl/pfctl_optimize.c b/freebsd/sbin/pfctl/pfctl_optimize.c new file mode 100644 index 00000000..b8f44e8b --- /dev/null +++ b/freebsd/sbin/pfctl/pfctl_optimize.c @@ -0,0 +1,1705 @@ +#include <machine/rtems-bsd-user-space.h> + +#ifdef __rtems__ +#include "rtems-bsd-pfctl-namespace.h" +#endif /* __rtems__ */ + +/* $OpenBSD: pfctl_optimize.c,v 1.17 2008/05/06 03:45:21 mpf 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/cdefs.h> +__FBSDID("$FreeBSD$"); + +#ifdef __rtems__ +#include <machine/rtems-bsd-program.h> +#define pf_find_or_create_ruleset _bsd_pf_find_or_create_ruleset +#endif /* __rtems__ */ +#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" +#ifdef __rtems__ +struct pf_rule_field { + const char *prf_name; + int prf_type; + size_t prf_offset; + size_t prf_size; +}; +#include "rtems-bsd-pfctl-pfctl_optimize-data.h" +#endif /* __rtems__ */ + +/* 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?!? */ +#ifndef __rtems__ +static struct pf_rule_field { + const char *prf_name; + int prf_type; + size_t prf_offset; + size_t prf_size; +} pf_rule_desc[] = { +#else /* __rtems__ */ +static struct pf_rule_field pf_rule_desc[] = { +#endif /* __rtems__ */ +#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), + PF_RULE_FIELD(max_src_states, BARRIER), + PF_RULE_FIELD(max_src_conn, BARRIER), + PF_RULE_FIELD(max_src_conn_rate, BARRIER), + PF_RULE_FIELD(anchor, BARRIER), /* for now */ + + /* + * 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(pqname, BREAK), + PF_RULE_FIELD(rt, BREAK), + PF_RULE_FIELD(allow_opts, BREAK), + PF_RULE_FIELD(rule_flag, BREAK), + PF_RULE_FIELD(action, BREAK), + PF_RULE_FIELD(log, BREAK), + PF_RULE_FIELD(quick, BREAK), + PF_RULE_FIELD(return_ttl, BREAK), + PF_RULE_FIELD(overload_tblname, BREAK), + PF_RULE_FIELD(flush, BREAK), + PF_RULE_FIELD(rpool, BREAK), + PF_RULE_FIELD(logif, 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), /* hack for IF groups */ + 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(states_cur, DC), + PF_RULE_FIELD(states_tot, 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), + PF_RULE_FIELD(tag, DC), + PF_RULE_FIELD(match_tag, DC), + PF_RULE_FIELD(overload_tbl, 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), + PF_RULE_FIELD(set_tos, 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 interface_group(const char *); +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 *); + + +static int (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, + struct pf_rule *); +static 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 } \ +} + +static struct pfr_buffer table_buffer; +static int table_identifier; + + +int +pfctl_optimize_ruleset(struct pfctl *pf, struct pf_ruleset *rs) +{ + struct superblocks superblocks; + struct pf_opt_queue opt_queue; + struct superblock *block; + struct pf_opt_rule *por; + struct pf_rule *r; + struct pf_rulequeue *old_rules; + + DEBUG("optimizing ruleset"); + memset(&table_buffer, 0, sizeof(table_buffer)); + skip_init(); + TAILQ_INIT(&opt_queue); + + old_rules = rs->rules[PF_RULESET_FILTER].active.ptr; + rs->rules[PF_RULESET_FILTER].active.ptr = + rs->rules[PF_RULESET_FILTER].inactive.ptr; + rs->rules[PF_RULESET_FILTER].inactive.ptr = old_rules; + + /* + * XXX expanding the pf_opt_rule format throughout pfctl might allow + * us to avoid all this copying. + */ + while ((r = TAILQ_FIRST(rs->rules[PF_RULESET_FILTER].inactive.ptr)) + != NULL) { + TAILQ_REMOVE(rs->rules[PF_RULESET_FILTER].inactive.ptr, r, + entries); + if ((por = calloc(1, sizeof(*por))) == NULL) + err(1, "calloc"); + memcpy(&por->por_rule, r, sizeof(*r)); + if (TAILQ_FIRST(&r->rpool.list) != NULL) { + TAILQ_INIT(&por->por_rule.rpool.list); + pfctl_move_pool(&r->rpool, &por->por_rule.rpool); + } else + bzero(&por->por_rule.rpool, + sizeof(por->por_rule.rpool)); + + + TAILQ_INSERT_TAIL(&opt_queue, por, por_entry); + } + + TAILQ_INIT(&superblocks); + if (construct_superblocks(pf, &opt_queue, &superblocks)) + goto error; + + if (pf->optimize & PF_OPTIMIZE_PROFILE) { + if (load_feedback_profile(pf, &superblocks)) + goto error; + } + + TAILQ_FOREACH(block, &superblocks, sb_entry) { + if (optimize_superblock(pf, block)) + goto error; + } + + rs->anchor->refcnt = 0; + 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 = rs->anchor->refcnt++; + if ((r = calloc(1, sizeof(*r))) == NULL) + err(1, "calloc"); + memcpy(r, &por->por_rule, sizeof(*r)); + TAILQ_INIT(&r->rpool.list); + pfctl_move_pool(&por->por_rule.rpool, &r->rpool); + TAILQ_INSERT_TAIL( + rs->rules[PF_RULESET_FILTER].active.ptr, + r, entries); + free(por); + } + free(block); + } + + return (0); + +error: + while ((por = TAILQ_FIRST(&opt_queue))) { + TAILQ_REMOVE(&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 a lot 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_rule.anchor ? + por->por_rule.anchor->name : "", 1, 0); + } +#endif /* OPT_DEBUG */ + + + if (remove_identical_rules(pf, block)) + return (1); + if (combine_rules(pf, block)) + return (1); + if ((pf->optimize & PF_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 && + p2->por_src_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 && + p2->por_dst_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[0] + + por1->por_rule.packets[1]; + 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[0] + + por1->por_rule.packets[1]; + 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; + } + } +#ifdef __FreeBSD__ + if (por2 == NULL) +#else + if (por2 == TAILQ_END(&block->sb_rules)) +#endif + 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) { + struct pf_ruleset *rs; + 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)); + rs = pf_find_or_create_ruleset(pr.anchor_call); + por->por_rule.anchor = rs->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: + case PF_ADDR_URPFFAILED: + 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: + case PF_ADDR_URPFFAILED: + 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 + */ +#ifdef __rtems__ +static int add_opt_tablenum = 0; +#endif /* __rtems__ */ +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 */ +#ifndef __rtems__ + static int tablenum = 0; +#endif /* __rtems__ */ + 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", +#ifndef __rtems__ + PF_OPT_TABLE_PREFIX, tablenum++); +#else /* __rtems__ */ + PF_OPT_TABLE_PREFIX, add_opt_tablenum++); +#endif /* __rtems__ */ + 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)) { + warn("failed to add host"); + 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) + */ +#ifdef __rtems__ +static int pf_opt_create_tablenum; +#endif /* __rtems__ */ +int +pf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl) +{ +#ifndef __rtems__ + static int tablenum; +#endif /* __rtems__ */ + 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, +#ifndef __rtems__ + PF_OPT_TABLE_PREFIX, table_identifier, tablenum); +#else /* __rtems__ */ + PF_OPT_TABLE_PREFIX, table_identifier, pf_opt_create_tablenum); +#endif /* __rtems__ */ + snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d", +#ifndef __rtems__ + PF_OPT_TABLE_PREFIX, table_identifier, tablenum); +#else /* __rtems__ */ + PF_OPT_TABLE_PREFIX, table_identifier, pf_opt_create_tablenum); +#endif /* __rtems__ */ + 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; + } + } +#ifndef __rtems__ + tablenum++; +#else /* __rtems__ */ + pf_opt_create_tablenum++; +#endif /* __rtems__ */ + + + if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1, + pf->astack[0]->name, tbl->pt_buf, pf->astack[0]->ruleset.tticket)) { + warn("failed to create table %s in %s", + tbl->pt_name, pf->astack[0]->name); + 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); + } + } + + /* per-rule src-track is also a hard break */ + if (por->por_rule.rule_flag & PFRULE_RULESRCTRACK) + return (0); + + /* + * Have to handle interface groups separately. Consider the following + * rules: + * block on EXTIFS to any port 22 + * pass on em0 to any port 22 + * (where EXTIFS is an arbitrary interface group) + * The optimizer may decide to re-order the pass rule in front of the + * block rule. But what if EXTIFS includes em0??? Such a reordering + * would change the meaning of the ruleset. + * We can't just lookup the EXTIFS group and check if em0 is a member + * because the user is allowed to add interfaces to a group during + * runtime. + * Ergo interface groups become a defacto superblock break :-( + */ + if (interface_group(por->por_rule.ifname) || + interface_group(TAILQ_FIRST(&block->sb_rules)->por_rule.ifname)) { + if (strcasecmp(por->por_rule.ifname, + TAILQ_FIRST(&block->sb_rules)->por_rule.ifname) != 0) + return (0); + } + + comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE); + comparable_rule(&b, &por->por_rule, NOMERGE); + if (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); +} + + +/* + * Figure out if an interface name is an actual interface or actually a + * group of interfaces. + */ +int +interface_group(const char *ifname) +{ + if (ifname == NULL || !ifname[0]) + return (0); + + /* Real interfaces must end in a number, interface groups do not */ + if (isdigit(ifname[strlen(ifname) - 1])) + return (0); + else + return (1); +} + + +/* + * 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); +} + |