1223637Sbz/* $OpenBSD: pfctl_optimize.c,v 1.17 2008/05/06 03:45:21 mpf Exp $ */ 2145837Smlaier 3145837Smlaier/* 4145837Smlaier * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org> 5145837Smlaier * 6145837Smlaier * Permission to use, copy, modify, and distribute this software for any 7145837Smlaier * purpose with or without fee is hereby granted, provided that the above 8145837Smlaier * copyright notice and this permission notice appear in all copies. 9145837Smlaier * 10145837Smlaier * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11145837Smlaier * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12145837Smlaier * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13145837Smlaier * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14145837Smlaier * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15145837Smlaier * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16145837Smlaier * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17145837Smlaier */ 18145837Smlaier 19145840Smlaier#include <sys/cdefs.h> 20145840Smlaier__FBSDID("$FreeBSD: stable/10/sbin/pfctl/pfctl_optimize.c 328649 2018-02-01 02:00:36Z pfg $"); 21145840Smlaier 22145837Smlaier#include <sys/types.h> 23145837Smlaier#include <sys/ioctl.h> 24145837Smlaier#include <sys/socket.h> 25145837Smlaier 26145837Smlaier#include <net/if.h> 27145837Smlaier#include <net/pfvar.h> 28145837Smlaier 29145837Smlaier#include <netinet/in.h> 30145837Smlaier#include <arpa/inet.h> 31145837Smlaier 32145837Smlaier#include <assert.h> 33145837Smlaier#include <ctype.h> 34145837Smlaier#include <err.h> 35145837Smlaier#include <errno.h> 36145837Smlaier#include <stddef.h> 37145837Smlaier#include <stdio.h> 38145837Smlaier#include <stdlib.h> 39145837Smlaier#include <string.h> 40145837Smlaier 41145837Smlaier#include "pfctl_parser.h" 42145837Smlaier#include "pfctl.h" 43145837Smlaier 44145837Smlaier/* The size at which a table becomes faster than individual rules */ 45145837Smlaier#define TABLE_THRESHOLD 6 46145837Smlaier 47145837Smlaier 48145837Smlaier/* #define OPT_DEBUG 1 */ 49145837Smlaier#ifdef OPT_DEBUG 50145837Smlaier# define DEBUG(str, v...) \ 51145837Smlaier printf("%s: " str "\n", __FUNCTION__ , ## v) 52145837Smlaier#else 53145837Smlaier# define DEBUG(str, v...) ((void)0) 54145837Smlaier#endif 55145837Smlaier 56145837Smlaier 57145837Smlaier/* 58145837Smlaier * A container that lets us sort a superblock to optimize the skip step jumps 59145837Smlaier */ 60145837Smlaierstruct pf_skip_step { 61145837Smlaier int ps_count; /* number of items */ 62145837Smlaier TAILQ_HEAD( , pf_opt_rule) ps_rules; 63145837Smlaier TAILQ_ENTRY(pf_skip_step) ps_entry; 64145837Smlaier}; 65145837Smlaier 66145837Smlaier 67145837Smlaier/* 68145837Smlaier * A superblock is a block of adjacent rules of similar action. If there 69145837Smlaier * are five PASS rules in a row, they all become members of a superblock. 70145837Smlaier * Once we have a superblock, we are free to re-order any rules within it 71145837Smlaier * in order to improve performance; if a packet is passed, it doesn't matter 72145837Smlaier * who passed it. 73145837Smlaier */ 74145837Smlaierstruct superblock { 75145837Smlaier TAILQ_HEAD( , pf_opt_rule) sb_rules; 76145837Smlaier TAILQ_ENTRY(superblock) sb_entry; 77145837Smlaier struct superblock *sb_profiled_block; 78145837Smlaier TAILQ_HEAD(skiplist, pf_skip_step) sb_skipsteps[PF_SKIP_COUNT]; 79145837Smlaier}; 80145837SmlaierTAILQ_HEAD(superblocks, superblock); 81145837Smlaier 82145837Smlaier 83145837Smlaier/* 84145837Smlaier * Description of the PF rule structure. 85145837Smlaier */ 86145837Smlaierenum { 87145837Smlaier BARRIER, /* the presence of the field puts the rule in it's own block */ 88145837Smlaier BREAK, /* the field may not differ between rules in a superblock */ 89145837Smlaier NOMERGE, /* the field may not differ between rules when combined */ 90145837Smlaier COMBINED, /* the field may itself be combined with other rules */ 91145837Smlaier DC, /* we just don't care about the field */ 92145837Smlaier NEVER}; /* we should never see this field set?!? */ 93145837Smlaierstruct pf_rule_field { 94145837Smlaier const char *prf_name; 95145837Smlaier int prf_type; 96145837Smlaier size_t prf_offset; 97145837Smlaier size_t prf_size; 98145837Smlaier} pf_rule_desc[] = { 99145837Smlaier#define PF_RULE_FIELD(field, ty) \ 100145837Smlaier {#field, \ 101145837Smlaier ty, \ 102145837Smlaier offsetof(struct pf_rule, field), \ 103145837Smlaier sizeof(((struct pf_rule *)0)->field)} 104145837Smlaier 105145837Smlaier 106145837Smlaier /* 107145837Smlaier * The presence of these fields in a rule put the rule in it's own 108145837Smlaier * superblock. Thus it will not be optimized. It also prevents the 109145837Smlaier * rule from being re-ordered at all. 110145837Smlaier */ 111145837Smlaier PF_RULE_FIELD(label, BARRIER), 112145837Smlaier PF_RULE_FIELD(prob, BARRIER), 113145837Smlaier PF_RULE_FIELD(max_states, BARRIER), 114145837Smlaier PF_RULE_FIELD(max_src_nodes, BARRIER), 115171172Smlaier PF_RULE_FIELD(max_src_states, BARRIER), 116171172Smlaier PF_RULE_FIELD(max_src_conn, BARRIER), 117171172Smlaier PF_RULE_FIELD(max_src_conn_rate, BARRIER), 118171172Smlaier PF_RULE_FIELD(anchor, BARRIER), /* for now */ 119145837Smlaier 120145837Smlaier /* 121145837Smlaier * These fields must be the same between all rules in the same superblock. 122145837Smlaier * These rules are allowed to be re-ordered but only among like rules. 123145837Smlaier * For instance we can re-order all 'tag "foo"' rules because they have the 124145837Smlaier * same tag. But we can not re-order between a 'tag "foo"' and a 125145837Smlaier * 'tag "bar"' since that would change the meaning of the ruleset. 126145837Smlaier */ 127145837Smlaier PF_RULE_FIELD(tagname, BREAK), 128145837Smlaier PF_RULE_FIELD(keep_state, BREAK), 129145837Smlaier PF_RULE_FIELD(qname, BREAK), 130171172Smlaier PF_RULE_FIELD(pqname, BREAK), 131145837Smlaier PF_RULE_FIELD(rt, BREAK), 132145837Smlaier PF_RULE_FIELD(allow_opts, BREAK), 133145837Smlaier PF_RULE_FIELD(rule_flag, BREAK), 134145837Smlaier PF_RULE_FIELD(action, BREAK), 135171172Smlaier PF_RULE_FIELD(log, BREAK), 136171172Smlaier PF_RULE_FIELD(quick, BREAK), 137171172Smlaier PF_RULE_FIELD(return_ttl, BREAK), 138171172Smlaier PF_RULE_FIELD(overload_tblname, BREAK), 139171172Smlaier PF_RULE_FIELD(flush, BREAK), 140171172Smlaier PF_RULE_FIELD(rpool, BREAK), 141171172Smlaier PF_RULE_FIELD(logif, BREAK), 142145837Smlaier 143145837Smlaier /* 144145837Smlaier * Any fields not listed in this structure act as BREAK fields 145145837Smlaier */ 146145837Smlaier 147145837Smlaier 148145837Smlaier /* 149145837Smlaier * These fields must not differ when we merge two rules together but 150145837Smlaier * their difference isn't enough to put the rules in different superblocks. 151145837Smlaier * There are no problems re-ordering any rules with these fields. 152145837Smlaier */ 153145837Smlaier PF_RULE_FIELD(af, NOMERGE), 154145837Smlaier PF_RULE_FIELD(ifnot, NOMERGE), 155171172Smlaier PF_RULE_FIELD(ifname, NOMERGE), /* hack for IF groups */ 156145837Smlaier PF_RULE_FIELD(match_tag_not, NOMERGE), 157145837Smlaier PF_RULE_FIELD(match_tagname, NOMERGE), 158145837Smlaier PF_RULE_FIELD(os_fingerprint, NOMERGE), 159145837Smlaier PF_RULE_FIELD(timeout, NOMERGE), 160145837Smlaier PF_RULE_FIELD(return_icmp, NOMERGE), 161145837Smlaier PF_RULE_FIELD(return_icmp6, NOMERGE), 162145837Smlaier PF_RULE_FIELD(uid, NOMERGE), 163145837Smlaier PF_RULE_FIELD(gid, NOMERGE), 164145837Smlaier PF_RULE_FIELD(direction, NOMERGE), 165145837Smlaier PF_RULE_FIELD(proto, NOMERGE), 166145837Smlaier PF_RULE_FIELD(type, NOMERGE), 167145837Smlaier PF_RULE_FIELD(code, NOMERGE), 168145837Smlaier PF_RULE_FIELD(flags, NOMERGE), 169145837Smlaier PF_RULE_FIELD(flagset, NOMERGE), 170145837Smlaier PF_RULE_FIELD(tos, NOMERGE), 171145837Smlaier PF_RULE_FIELD(src.port, NOMERGE), 172145837Smlaier PF_RULE_FIELD(dst.port, NOMERGE), 173145837Smlaier PF_RULE_FIELD(src.port_op, NOMERGE), 174145837Smlaier PF_RULE_FIELD(dst.port_op, NOMERGE), 175145837Smlaier PF_RULE_FIELD(src.neg, NOMERGE), 176145837Smlaier PF_RULE_FIELD(dst.neg, NOMERGE), 177145837Smlaier 178145837Smlaier /* These fields can be merged */ 179145837Smlaier PF_RULE_FIELD(src.addr, COMBINED), 180145837Smlaier PF_RULE_FIELD(dst.addr, COMBINED), 181145837Smlaier 182145837Smlaier /* We just don't care about these fields. They're set by the kernel */ 183145837Smlaier PF_RULE_FIELD(skip, DC), 184145837Smlaier PF_RULE_FIELD(evaluations, DC), 185145837Smlaier PF_RULE_FIELD(packets, DC), 186145837Smlaier PF_RULE_FIELD(bytes, DC), 187145837Smlaier PF_RULE_FIELD(kif, DC), 188223637Sbz PF_RULE_FIELD(states_cur, DC), 189223637Sbz PF_RULE_FIELD(states_tot, DC), 190145837Smlaier PF_RULE_FIELD(src_nodes, DC), 191145837Smlaier PF_RULE_FIELD(nr, DC), 192145837Smlaier PF_RULE_FIELD(entries, DC), 193145837Smlaier PF_RULE_FIELD(qid, DC), 194145837Smlaier PF_RULE_FIELD(pqid, DC), 195145837Smlaier PF_RULE_FIELD(anchor_relative, DC), 196145837Smlaier PF_RULE_FIELD(anchor_wildcard, DC), 197171172Smlaier PF_RULE_FIELD(tag, DC), 198171172Smlaier PF_RULE_FIELD(match_tag, DC), 199171172Smlaier PF_RULE_FIELD(overload_tbl, DC), 200145837Smlaier 201145837Smlaier /* These fields should never be set in a PASS/BLOCK rule */ 202145837Smlaier PF_RULE_FIELD(natpass, NEVER), 203145837Smlaier PF_RULE_FIELD(max_mss, NEVER), 204145837Smlaier PF_RULE_FIELD(min_ttl, NEVER), 205223637Sbz PF_RULE_FIELD(set_tos, NEVER), 206145837Smlaier}; 207145837Smlaier 208145837Smlaier 209145837Smlaier 210145837Smlaierint add_opt_table(struct pfctl *, struct pf_opt_tbl **, sa_family_t, 211145837Smlaier struct pf_rule_addr *); 212145837Smlaierint addrs_combineable(struct pf_rule_addr *, struct pf_rule_addr *); 213145837Smlaierint addrs_equal(struct pf_rule_addr *, struct pf_rule_addr *); 214145837Smlaierint block_feedback(struct pfctl *, struct superblock *); 215145837Smlaierint combine_rules(struct pfctl *, struct superblock *); 216145837Smlaiervoid comparable_rule(struct pf_rule *, const struct pf_rule *, int); 217145837Smlaierint construct_superblocks(struct pfctl *, struct pf_opt_queue *, 218145837Smlaier struct superblocks *); 219145837Smlaiervoid exclude_supersets(struct pf_rule *, struct pf_rule *); 220171172Smlaierint interface_group(const char *); 221145837Smlaierint load_feedback_profile(struct pfctl *, struct superblocks *); 222145837Smlaierint optimize_superblock(struct pfctl *, struct superblock *); 223145837Smlaierint pf_opt_create_table(struct pfctl *, struct pf_opt_tbl *); 224145837Smlaiervoid remove_from_skipsteps(struct skiplist *, struct superblock *, 225145837Smlaier struct pf_opt_rule *, struct pf_skip_step *); 226145837Smlaierint remove_identical_rules(struct pfctl *, struct superblock *); 227145837Smlaierint reorder_rules(struct pfctl *, struct superblock *, int); 228145837Smlaierint rules_combineable(struct pf_rule *, struct pf_rule *); 229145837Smlaiervoid skip_append(struct superblock *, int, struct pf_skip_step *, 230145837Smlaier struct pf_opt_rule *); 231145837Smlaierint skip_compare(int, struct pf_skip_step *, struct pf_opt_rule *); 232145837Smlaiervoid skip_init(void); 233145837Smlaierint skip_cmp_af(struct pf_rule *, struct pf_rule *); 234145837Smlaierint skip_cmp_dir(struct pf_rule *, struct pf_rule *); 235145837Smlaierint skip_cmp_dst_addr(struct pf_rule *, struct pf_rule *); 236145837Smlaierint skip_cmp_dst_port(struct pf_rule *, struct pf_rule *); 237145837Smlaierint skip_cmp_ifp(struct pf_rule *, struct pf_rule *); 238145837Smlaierint skip_cmp_proto(struct pf_rule *, struct pf_rule *); 239145837Smlaierint skip_cmp_src_addr(struct pf_rule *, struct pf_rule *); 240145837Smlaierint skip_cmp_src_port(struct pf_rule *, struct pf_rule *); 241145837Smlaierint superblock_inclusive(struct superblock *, struct pf_opt_rule *); 242145837Smlaiervoid superblock_free(struct pfctl *, struct superblock *); 243145837Smlaier 244145837Smlaier 245145837Smlaierint (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, struct pf_rule *); 246145837Smlaierconst char *skip_comparitors_names[PF_SKIP_COUNT]; 247145837Smlaier#define PF_SKIP_COMPARITORS { \ 248145837Smlaier { "ifp", PF_SKIP_IFP, skip_cmp_ifp }, \ 249145837Smlaier { "dir", PF_SKIP_DIR, skip_cmp_dir }, \ 250145837Smlaier { "af", PF_SKIP_AF, skip_cmp_af }, \ 251145837Smlaier { "proto", PF_SKIP_PROTO, skip_cmp_proto }, \ 252145837Smlaier { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr }, \ 253145837Smlaier { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port }, \ 254145837Smlaier { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr }, \ 255145837Smlaier { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port } \ 256145837Smlaier} 257145837Smlaier 258145837Smlaierstruct pfr_buffer table_buffer; 259145837Smlaierint table_identifier; 260145837Smlaier 261145837Smlaier 262145837Smlaierint 263171172Smlaierpfctl_optimize_ruleset(struct pfctl *pf, struct pf_ruleset *rs) 264145837Smlaier{ 265145837Smlaier struct superblocks superblocks; 266171172Smlaier struct pf_opt_queue opt_queue; 267145837Smlaier struct superblock *block; 268145837Smlaier struct pf_opt_rule *por; 269171172Smlaier struct pf_rule *r; 270171172Smlaier struct pf_rulequeue *old_rules; 271145837Smlaier 272145837Smlaier DEBUG("optimizing ruleset"); 273145837Smlaier memset(&table_buffer, 0, sizeof(table_buffer)); 274145837Smlaier skip_init(); 275171172Smlaier TAILQ_INIT(&opt_queue); 276145837Smlaier 277171172Smlaier old_rules = rs->rules[PF_RULESET_FILTER].active.ptr; 278171172Smlaier rs->rules[PF_RULESET_FILTER].active.ptr = 279171172Smlaier rs->rules[PF_RULESET_FILTER].inactive.ptr; 280171172Smlaier rs->rules[PF_RULESET_FILTER].inactive.ptr = old_rules; 281145837Smlaier 282171172Smlaier /* 283171172Smlaier * XXX expanding the pf_opt_rule format throughout pfctl might allow 284171172Smlaier * us to avoid all this copying. 285171172Smlaier */ 286171172Smlaier while ((r = TAILQ_FIRST(rs->rules[PF_RULESET_FILTER].inactive.ptr)) 287171172Smlaier != NULL) { 288171172Smlaier TAILQ_REMOVE(rs->rules[PF_RULESET_FILTER].inactive.ptr, r, 289171172Smlaier entries); 290171172Smlaier if ((por = calloc(1, sizeof(*por))) == NULL) 291171172Smlaier err(1, "calloc"); 292171172Smlaier memcpy(&por->por_rule, r, sizeof(*r)); 293171172Smlaier if (TAILQ_FIRST(&r->rpool.list) != NULL) { 294171172Smlaier TAILQ_INIT(&por->por_rule.rpool.list); 295171172Smlaier pfctl_move_pool(&r->rpool, &por->por_rule.rpool); 296171172Smlaier } else 297171172Smlaier bzero(&por->por_rule.rpool, 298171172Smlaier sizeof(por->por_rule.rpool)); 299171172Smlaier 300171172Smlaier 301171172Smlaier TAILQ_INSERT_TAIL(&opt_queue, por, por_entry); 302171172Smlaier } 303171172Smlaier 304145837Smlaier TAILQ_INIT(&superblocks); 305171172Smlaier if (construct_superblocks(pf, &opt_queue, &superblocks)) 306145837Smlaier goto error; 307145837Smlaier 308171172Smlaier if (pf->optimize & PF_OPTIMIZE_PROFILE) { 309145837Smlaier if (load_feedback_profile(pf, &superblocks)) 310145837Smlaier goto error; 311145837Smlaier } 312145837Smlaier 313145837Smlaier TAILQ_FOREACH(block, &superblocks, sb_entry) { 314145837Smlaier if (optimize_superblock(pf, block)) 315145837Smlaier goto error; 316145837Smlaier } 317145837Smlaier 318171172Smlaier rs->anchor->refcnt = 0; 319145837Smlaier while ((block = TAILQ_FIRST(&superblocks))) { 320145837Smlaier TAILQ_REMOVE(&superblocks, block, sb_entry); 321145837Smlaier 322145837Smlaier while ((por = TAILQ_FIRST(&block->sb_rules))) { 323145837Smlaier TAILQ_REMOVE(&block->sb_rules, por, por_entry); 324171172Smlaier por->por_rule.nr = rs->anchor->refcnt++; 325171172Smlaier if ((r = calloc(1, sizeof(*r))) == NULL) 326171172Smlaier err(1, "calloc"); 327171172Smlaier memcpy(r, &por->por_rule, sizeof(*r)); 328171172Smlaier TAILQ_INIT(&r->rpool.list); 329171172Smlaier pfctl_move_pool(&por->por_rule.rpool, &r->rpool); 330171172Smlaier TAILQ_INSERT_TAIL( 331171172Smlaier rs->rules[PF_RULESET_FILTER].active.ptr, 332171172Smlaier r, entries); 333145837Smlaier free(por); 334145837Smlaier } 335145837Smlaier free(block); 336145837Smlaier } 337145837Smlaier 338145837Smlaier return (0); 339145837Smlaier 340145837Smlaiererror: 341171172Smlaier while ((por = TAILQ_FIRST(&opt_queue))) { 342171172Smlaier TAILQ_REMOVE(&opt_queue, por, por_entry); 343145837Smlaier if (por->por_src_tbl) { 344145837Smlaier pfr_buf_clear(por->por_src_tbl->pt_buf); 345145837Smlaier free(por->por_src_tbl->pt_buf); 346145837Smlaier free(por->por_src_tbl); 347145837Smlaier } 348145837Smlaier if (por->por_dst_tbl) { 349145837Smlaier pfr_buf_clear(por->por_dst_tbl->pt_buf); 350145837Smlaier free(por->por_dst_tbl->pt_buf); 351145837Smlaier free(por->por_dst_tbl); 352145837Smlaier } 353145837Smlaier free(por); 354145837Smlaier } 355145837Smlaier while ((block = TAILQ_FIRST(&superblocks))) { 356145837Smlaier TAILQ_REMOVE(&superblocks, block, sb_entry); 357145837Smlaier superblock_free(pf, block); 358145837Smlaier } 359145837Smlaier return (1); 360145837Smlaier} 361145837Smlaier 362145837Smlaier 363145837Smlaier/* 364145837Smlaier * Go ahead and optimize a superblock 365145837Smlaier */ 366145837Smlaierint 367145837Smlaieroptimize_superblock(struct pfctl *pf, struct superblock *block) 368145837Smlaier{ 369145837Smlaier#ifdef OPT_DEBUG 370145837Smlaier struct pf_opt_rule *por; 371145837Smlaier#endif /* OPT_DEBUG */ 372145837Smlaier 373145837Smlaier /* We have a few optimization passes: 374145837Smlaier * 1) remove duplicate rules or rules that are a subset of other 375145837Smlaier * rules 376145837Smlaier * 2) combine otherwise identical rules with different IP addresses 377145837Smlaier * into a single rule and put the addresses in a table. 378145837Smlaier * 3) re-order the rules to improve kernel skip steps 379145837Smlaier * 4) re-order the 'quick' rules based on feedback from the 380145837Smlaier * active ruleset statistics 381145837Smlaier * 382145837Smlaier * XXX combine_rules() doesn't combine v4 and v6 rules. would just 383145837Smlaier * have to keep af in the table container, make af 'COMBINE' and 384145837Smlaier * twiddle the af on the merged rule 385145837Smlaier * XXX maybe add a weighting to the metric on skipsteps when doing 386145837Smlaier * reordering. sometimes two sequential tables will be better 387145837Smlaier * that four consecutive interfaces. 388145837Smlaier * XXX need to adjust the skipstep count of everything after PROTO, 389145837Smlaier * since they aren't actually checked on a proto mismatch in 390145837Smlaier * pf_test_{tcp, udp, icmp}() 391145837Smlaier * XXX should i treat proto=0, af=0 or dir=0 special in skepstep 392145837Smlaier * calculation since they are a DC? 393145837Smlaier * XXX keep last skiplist of last superblock to influence this 394145837Smlaier * superblock. '5 inet6 log' should make '3 inet6' come before '4 395145837Smlaier * inet' in the next superblock. 396145837Smlaier * XXX would be useful to add tables for ports 397145837Smlaier * XXX we can also re-order some mutually exclusive superblocks to 398145837Smlaier * try merging superblocks before any of these optimization passes. 399145837Smlaier * for instance a single 'log in' rule in the middle of non-logging 400145837Smlaier * out rules. 401145837Smlaier */ 402145837Smlaier 403223637Sbz /* shortcut. there will be a lot of 1-rule superblocks */ 404145837Smlaier if (!TAILQ_NEXT(TAILQ_FIRST(&block->sb_rules), por_entry)) 405145837Smlaier return (0); 406145837Smlaier 407145837Smlaier#ifdef OPT_DEBUG 408145837Smlaier printf("--- Superblock ---\n"); 409145837Smlaier TAILQ_FOREACH(por, &block->sb_rules, por_entry) { 410145837Smlaier printf(" "); 411171172Smlaier print_rule(&por->por_rule, por->por_rule.anchor ? 412223057Sbz por->por_rule.anchor->name : "", 1, 0); 413145837Smlaier } 414145837Smlaier#endif /* OPT_DEBUG */ 415145837Smlaier 416145837Smlaier 417145837Smlaier if (remove_identical_rules(pf, block)) 418145837Smlaier return (1); 419145837Smlaier if (combine_rules(pf, block)) 420145837Smlaier return (1); 421171172Smlaier if ((pf->optimize & PF_OPTIMIZE_PROFILE) && 422145837Smlaier TAILQ_FIRST(&block->sb_rules)->por_rule.quick && 423145837Smlaier block->sb_profiled_block) { 424145837Smlaier if (block_feedback(pf, block)) 425145837Smlaier return (1); 426145837Smlaier } else if (reorder_rules(pf, block, 0)) { 427145837Smlaier return (1); 428145837Smlaier } 429145837Smlaier 430145837Smlaier /* 431145837Smlaier * Don't add any optimization passes below reorder_rules(). It will 432145837Smlaier * have divided superblocks into smaller blocks for further refinement 433145837Smlaier * and doesn't put them back together again. What once was a true 434145837Smlaier * superblock might have been split into multiple superblocks. 435145837Smlaier */ 436145837Smlaier 437145837Smlaier#ifdef OPT_DEBUG 438145837Smlaier printf("--- END Superblock ---\n"); 439145837Smlaier#endif /* OPT_DEBUG */ 440145837Smlaier return (0); 441145837Smlaier} 442145837Smlaier 443145837Smlaier 444145837Smlaier/* 445145837Smlaier * Optimization pass #1: remove identical rules 446145837Smlaier */ 447145837Smlaierint 448145837Smlaierremove_identical_rules(struct pfctl *pf, struct superblock *block) 449145837Smlaier{ 450145837Smlaier struct pf_opt_rule *por1, *por2, *por_next, *por2_next; 451145837Smlaier struct pf_rule a, a2, b, b2; 452145837Smlaier 453145837Smlaier for (por1 = TAILQ_FIRST(&block->sb_rules); por1; por1 = por_next) { 454145837Smlaier por_next = TAILQ_NEXT(por1, por_entry); 455145837Smlaier for (por2 = por_next; por2; por2 = por2_next) { 456145837Smlaier por2_next = TAILQ_NEXT(por2, por_entry); 457145837Smlaier comparable_rule(&a, &por1->por_rule, DC); 458145837Smlaier comparable_rule(&b, &por2->por_rule, DC); 459145837Smlaier memcpy(&a2, &a, sizeof(a2)); 460145837Smlaier memcpy(&b2, &b, sizeof(b2)); 461145837Smlaier 462145837Smlaier exclude_supersets(&a, &b); 463145837Smlaier exclude_supersets(&b2, &a2); 464145837Smlaier if (memcmp(&a, &b, sizeof(a)) == 0) { 465145837Smlaier DEBUG("removing identical rule nr%d = *nr%d*", 466145837Smlaier por1->por_rule.nr, por2->por_rule.nr); 467145837Smlaier TAILQ_REMOVE(&block->sb_rules, por2, por_entry); 468145837Smlaier if (por_next == por2) 469145837Smlaier por_next = TAILQ_NEXT(por1, por_entry); 470145837Smlaier free(por2); 471145837Smlaier } else if (memcmp(&a2, &b2, sizeof(a2)) == 0) { 472145837Smlaier DEBUG("removing identical rule *nr%d* = nr%d", 473145837Smlaier por1->por_rule.nr, por2->por_rule.nr); 474145837Smlaier TAILQ_REMOVE(&block->sb_rules, por1, por_entry); 475145837Smlaier free(por1); 476145837Smlaier break; 477145837Smlaier } 478145837Smlaier } 479145837Smlaier } 480145837Smlaier 481145837Smlaier return (0); 482145837Smlaier} 483145837Smlaier 484145837Smlaier 485145837Smlaier/* 486145837Smlaier * Optimization pass #2: combine similar rules with different addresses 487145837Smlaier * into a single rule and a table 488145837Smlaier */ 489145837Smlaierint 490145837Smlaiercombine_rules(struct pfctl *pf, struct superblock *block) 491145837Smlaier{ 492145837Smlaier struct pf_opt_rule *p1, *p2, *por_next; 493145837Smlaier int src_eq, dst_eq; 494145837Smlaier 495145837Smlaier if ((pf->loadopt & PFCTL_FLAG_TABLE) == 0) { 496145837Smlaier warnx("Must enable table loading for optimizations"); 497145837Smlaier return (1); 498145837Smlaier } 499145837Smlaier 500145837Smlaier /* First we make a pass to combine the rules. O(n log n) */ 501145837Smlaier TAILQ_FOREACH(p1, &block->sb_rules, por_entry) { 502145837Smlaier for (p2 = TAILQ_NEXT(p1, por_entry); p2; p2 = por_next) { 503145837Smlaier por_next = TAILQ_NEXT(p2, por_entry); 504145837Smlaier 505145837Smlaier src_eq = addrs_equal(&p1->por_rule.src, 506145837Smlaier &p2->por_rule.src); 507145837Smlaier dst_eq = addrs_equal(&p1->por_rule.dst, 508145837Smlaier &p2->por_rule.dst); 509145837Smlaier 510145837Smlaier if (src_eq && !dst_eq && p1->por_src_tbl == NULL && 511145837Smlaier p2->por_dst_tbl == NULL && 512145837Smlaier p2->por_src_tbl == NULL && 513145837Smlaier rules_combineable(&p1->por_rule, &p2->por_rule) && 514145837Smlaier addrs_combineable(&p1->por_rule.dst, 515145837Smlaier &p2->por_rule.dst)) { 516145837Smlaier DEBUG("can combine rules nr%d = nr%d", 517145837Smlaier p1->por_rule.nr, p2->por_rule.nr); 518145837Smlaier if (p1->por_dst_tbl == NULL && 519145837Smlaier add_opt_table(pf, &p1->por_dst_tbl, 520145837Smlaier p1->por_rule.af, &p1->por_rule.dst)) 521145837Smlaier return (1); 522145837Smlaier if (add_opt_table(pf, &p1->por_dst_tbl, 523145837Smlaier p1->por_rule.af, &p2->por_rule.dst)) 524145837Smlaier return (1); 525145837Smlaier p2->por_dst_tbl = p1->por_dst_tbl; 526145837Smlaier if (p1->por_dst_tbl->pt_rulecount >= 527145837Smlaier TABLE_THRESHOLD) { 528145837Smlaier TAILQ_REMOVE(&block->sb_rules, p2, 529145837Smlaier por_entry); 530145837Smlaier free(p2); 531145837Smlaier } 532145837Smlaier } else if (!src_eq && dst_eq && p1->por_dst_tbl == NULL 533145837Smlaier && p2->por_src_tbl == NULL && 534145837Smlaier p2->por_dst_tbl == NULL && 535145837Smlaier rules_combineable(&p1->por_rule, &p2->por_rule) && 536145837Smlaier addrs_combineable(&p1->por_rule.src, 537145837Smlaier &p2->por_rule.src)) { 538145837Smlaier DEBUG("can combine rules nr%d = nr%d", 539145837Smlaier p1->por_rule.nr, p2->por_rule.nr); 540145837Smlaier if (p1->por_src_tbl == NULL && 541145837Smlaier add_opt_table(pf, &p1->por_src_tbl, 542145837Smlaier p1->por_rule.af, &p1->por_rule.src)) 543145837Smlaier return (1); 544145837Smlaier if (add_opt_table(pf, &p1->por_src_tbl, 545145837Smlaier p1->por_rule.af, &p2->por_rule.src)) 546145837Smlaier return (1); 547145837Smlaier p2->por_src_tbl = p1->por_src_tbl; 548145837Smlaier if (p1->por_src_tbl->pt_rulecount >= 549145837Smlaier TABLE_THRESHOLD) { 550145837Smlaier TAILQ_REMOVE(&block->sb_rules, p2, 551145837Smlaier por_entry); 552145837Smlaier free(p2); 553145837Smlaier } 554145837Smlaier } 555145837Smlaier } 556145837Smlaier } 557145837Smlaier 558145837Smlaier 559145837Smlaier /* 560145837Smlaier * Then we make a final pass to create a valid table name and 561145837Smlaier * insert the name into the rules. 562145837Smlaier */ 563145837Smlaier for (p1 = TAILQ_FIRST(&block->sb_rules); p1; p1 = por_next) { 564145837Smlaier por_next = TAILQ_NEXT(p1, por_entry); 565145837Smlaier assert(p1->por_src_tbl == NULL || p1->por_dst_tbl == NULL); 566145837Smlaier 567145837Smlaier if (p1->por_src_tbl && p1->por_src_tbl->pt_rulecount >= 568145837Smlaier TABLE_THRESHOLD) { 569145837Smlaier if (p1->por_src_tbl->pt_generated) { 570145837Smlaier /* This rule is included in a table */ 571145837Smlaier TAILQ_REMOVE(&block->sb_rules, p1, por_entry); 572145837Smlaier free(p1); 573145837Smlaier continue; 574145837Smlaier } 575145837Smlaier p1->por_src_tbl->pt_generated = 1; 576145837Smlaier 577145837Smlaier if ((pf->opts & PF_OPT_NOACTION) == 0 && 578145837Smlaier pf_opt_create_table(pf, p1->por_src_tbl)) 579145837Smlaier return (1); 580145837Smlaier 581145837Smlaier pf->tdirty = 1; 582145837Smlaier 583145837Smlaier if (pf->opts & PF_OPT_VERBOSE) 584145837Smlaier print_tabledef(p1->por_src_tbl->pt_name, 585145837Smlaier PFR_TFLAG_CONST, 1, 586145837Smlaier &p1->por_src_tbl->pt_nodes); 587145837Smlaier 588145837Smlaier memset(&p1->por_rule.src.addr, 0, 589145837Smlaier sizeof(p1->por_rule.src.addr)); 590145837Smlaier p1->por_rule.src.addr.type = PF_ADDR_TABLE; 591145837Smlaier strlcpy(p1->por_rule.src.addr.v.tblname, 592145837Smlaier p1->por_src_tbl->pt_name, 593145837Smlaier sizeof(p1->por_rule.src.addr.v.tblname)); 594145837Smlaier 595145837Smlaier pfr_buf_clear(p1->por_src_tbl->pt_buf); 596145837Smlaier free(p1->por_src_tbl->pt_buf); 597145837Smlaier p1->por_src_tbl->pt_buf = NULL; 598145837Smlaier } 599145837Smlaier if (p1->por_dst_tbl && p1->por_dst_tbl->pt_rulecount >= 600145837Smlaier TABLE_THRESHOLD) { 601145837Smlaier if (p1->por_dst_tbl->pt_generated) { 602145837Smlaier /* This rule is included in a table */ 603145837Smlaier TAILQ_REMOVE(&block->sb_rules, p1, por_entry); 604145837Smlaier free(p1); 605145837Smlaier continue; 606145837Smlaier } 607145837Smlaier p1->por_dst_tbl->pt_generated = 1; 608145837Smlaier 609145837Smlaier if ((pf->opts & PF_OPT_NOACTION) == 0 && 610145837Smlaier pf_opt_create_table(pf, p1->por_dst_tbl)) 611145837Smlaier return (1); 612145837Smlaier pf->tdirty = 1; 613145837Smlaier 614145837Smlaier if (pf->opts & PF_OPT_VERBOSE) 615145837Smlaier print_tabledef(p1->por_dst_tbl->pt_name, 616145837Smlaier PFR_TFLAG_CONST, 1, 617145837Smlaier &p1->por_dst_tbl->pt_nodes); 618145837Smlaier 619145837Smlaier memset(&p1->por_rule.dst.addr, 0, 620145837Smlaier sizeof(p1->por_rule.dst.addr)); 621145837Smlaier p1->por_rule.dst.addr.type = PF_ADDR_TABLE; 622145837Smlaier strlcpy(p1->por_rule.dst.addr.v.tblname, 623145837Smlaier p1->por_dst_tbl->pt_name, 624145837Smlaier sizeof(p1->por_rule.dst.addr.v.tblname)); 625145837Smlaier 626145837Smlaier pfr_buf_clear(p1->por_dst_tbl->pt_buf); 627145837Smlaier free(p1->por_dst_tbl->pt_buf); 628145837Smlaier p1->por_dst_tbl->pt_buf = NULL; 629145837Smlaier } 630145837Smlaier } 631145837Smlaier 632145837Smlaier return (0); 633145837Smlaier} 634145837Smlaier 635145837Smlaier 636145837Smlaier/* 637145837Smlaier * Optimization pass #3: re-order rules to improve skip steps 638145837Smlaier */ 639145837Smlaierint 640145837Smlaierreorder_rules(struct pfctl *pf, struct superblock *block, int depth) 641145837Smlaier{ 642145837Smlaier struct superblock *newblock; 643145837Smlaier struct pf_skip_step *skiplist; 644145837Smlaier struct pf_opt_rule *por; 645145837Smlaier int i, largest, largest_list, rule_count = 0; 646145837Smlaier TAILQ_HEAD( , pf_opt_rule) head; 647145837Smlaier 648145837Smlaier /* 649145837Smlaier * Calculate the best-case skip steps. We put each rule in a list 650145837Smlaier * of other rules with common fields 651145837Smlaier */ 652145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) { 653145837Smlaier TAILQ_FOREACH(por, &block->sb_rules, por_entry) { 654145837Smlaier TAILQ_FOREACH(skiplist, &block->sb_skipsteps[i], 655145837Smlaier ps_entry) { 656145837Smlaier if (skip_compare(i, skiplist, por) == 0) 657145837Smlaier break; 658145837Smlaier } 659145837Smlaier if (skiplist == NULL) { 660145837Smlaier if ((skiplist = calloc(1, sizeof(*skiplist))) == 661145837Smlaier NULL) 662145837Smlaier err(1, "calloc"); 663145837Smlaier TAILQ_INIT(&skiplist->ps_rules); 664145837Smlaier TAILQ_INSERT_TAIL(&block->sb_skipsteps[i], 665145837Smlaier skiplist, ps_entry); 666145837Smlaier } 667145837Smlaier skip_append(block, i, skiplist, por); 668145837Smlaier } 669145837Smlaier } 670145837Smlaier 671145837Smlaier TAILQ_FOREACH(por, &block->sb_rules, por_entry) 672145837Smlaier rule_count++; 673145837Smlaier 674145837Smlaier /* 675145837Smlaier * Now we're going to ignore any fields that are identical between 676145837Smlaier * all of the rules in the superblock and those fields which differ 677145837Smlaier * between every rule in the superblock. 678145837Smlaier */ 679145837Smlaier largest = 0; 680145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) { 681145837Smlaier skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); 682145837Smlaier if (skiplist->ps_count == rule_count) { 683145837Smlaier DEBUG("(%d) original skipstep '%s' is all rules", 684145837Smlaier depth, skip_comparitors_names[i]); 685145837Smlaier skiplist->ps_count = 0; 686145837Smlaier } else if (skiplist->ps_count == 1) { 687145837Smlaier skiplist->ps_count = 0; 688145837Smlaier } else { 689145837Smlaier DEBUG("(%d) original skipstep '%s' largest jump is %d", 690145837Smlaier depth, skip_comparitors_names[i], 691145837Smlaier skiplist->ps_count); 692145837Smlaier if (skiplist->ps_count > largest) 693145837Smlaier largest = skiplist->ps_count; 694145837Smlaier } 695145837Smlaier } 696145837Smlaier if (largest == 0) { 697145837Smlaier /* Ugh. There is NO commonality in the superblock on which 698145837Smlaier * optimize the skipsteps optimization. 699145837Smlaier */ 700145837Smlaier goto done; 701145837Smlaier } 702145837Smlaier 703145837Smlaier /* 704145837Smlaier * Now we're going to empty the superblock rule list and re-create 705145837Smlaier * it based on a more optimal skipstep order. 706145837Smlaier */ 707145837Smlaier TAILQ_INIT(&head); 708145837Smlaier while ((por = TAILQ_FIRST(&block->sb_rules))) { 709145837Smlaier TAILQ_REMOVE(&block->sb_rules, por, por_entry); 710145837Smlaier TAILQ_INSERT_TAIL(&head, por, por_entry); 711145837Smlaier } 712145837Smlaier 713145837Smlaier 714145837Smlaier while (!TAILQ_EMPTY(&head)) { 715145837Smlaier largest = 1; 716145837Smlaier 717145837Smlaier /* 718145837Smlaier * Find the most useful skip steps remaining 719145837Smlaier */ 720145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) { 721145837Smlaier skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); 722145837Smlaier if (skiplist->ps_count > largest) { 723145837Smlaier largest = skiplist->ps_count; 724145837Smlaier largest_list = i; 725145837Smlaier } 726145837Smlaier } 727145837Smlaier 728145837Smlaier if (largest <= 1) { 729145837Smlaier /* 730145837Smlaier * Nothing useful left. Leave remaining rules in order. 731145837Smlaier */ 732145837Smlaier DEBUG("(%d) no more commonality for skip steps", depth); 733145837Smlaier while ((por = TAILQ_FIRST(&head))) { 734145837Smlaier TAILQ_REMOVE(&head, por, por_entry); 735145837Smlaier TAILQ_INSERT_TAIL(&block->sb_rules, por, 736145837Smlaier por_entry); 737145837Smlaier } 738145837Smlaier } else { 739145837Smlaier /* 740145837Smlaier * There is commonality. Extract those common rules 741145837Smlaier * and place them in the ruleset adjacent to each 742145837Smlaier * other. 743145837Smlaier */ 744145837Smlaier skiplist = TAILQ_FIRST(&block->sb_skipsteps[ 745145837Smlaier largest_list]); 746145837Smlaier DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d", 747145837Smlaier depth, skip_comparitors_names[largest_list], 748145837Smlaier largest, TAILQ_FIRST(&TAILQ_FIRST(&block-> 749145837Smlaier sb_skipsteps [largest_list])->ps_rules)-> 750145837Smlaier por_rule.nr); 751145837Smlaier TAILQ_REMOVE(&block->sb_skipsteps[largest_list], 752145837Smlaier skiplist, ps_entry); 753145837Smlaier 754145837Smlaier 755145837Smlaier /* 756145837Smlaier * There may be further commonality inside these 757145837Smlaier * rules. So we'll split them off into they're own 758145837Smlaier * superblock and pass it back into the optimizer. 759145837Smlaier */ 760145837Smlaier if (skiplist->ps_count > 2) { 761145837Smlaier if ((newblock = calloc(1, sizeof(*newblock))) 762145837Smlaier == NULL) { 763145837Smlaier warn("calloc"); 764145837Smlaier return (1); 765145837Smlaier } 766145837Smlaier TAILQ_INIT(&newblock->sb_rules); 767145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) 768145837Smlaier TAILQ_INIT(&newblock->sb_skipsteps[i]); 769145837Smlaier TAILQ_INSERT_BEFORE(block, newblock, sb_entry); 770145837Smlaier DEBUG("(%d) splitting off %d rules from superblock @ #%d", 771145837Smlaier depth, skiplist->ps_count, 772145837Smlaier TAILQ_FIRST(&skiplist->ps_rules)-> 773145837Smlaier por_rule.nr); 774145837Smlaier } else { 775145837Smlaier newblock = block; 776145837Smlaier } 777145837Smlaier 778145837Smlaier while ((por = TAILQ_FIRST(&skiplist->ps_rules))) { 779145837Smlaier TAILQ_REMOVE(&head, por, por_entry); 780145837Smlaier TAILQ_REMOVE(&skiplist->ps_rules, por, 781145837Smlaier por_skip_entry[largest_list]); 782145837Smlaier TAILQ_INSERT_TAIL(&newblock->sb_rules, por, 783145837Smlaier por_entry); 784145837Smlaier 785145837Smlaier /* Remove this rule from all other skiplists */ 786145837Smlaier remove_from_skipsteps(&block->sb_skipsteps[ 787145837Smlaier largest_list], block, por, skiplist); 788145837Smlaier } 789145837Smlaier free(skiplist); 790145837Smlaier if (newblock != block) 791145837Smlaier if (reorder_rules(pf, newblock, depth + 1)) 792145837Smlaier return (1); 793145837Smlaier } 794145837Smlaier } 795145837Smlaier 796145837Smlaierdone: 797145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) { 798145837Smlaier while ((skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]))) { 799145837Smlaier TAILQ_REMOVE(&block->sb_skipsteps[i], skiplist, 800145837Smlaier ps_entry); 801145837Smlaier free(skiplist); 802145837Smlaier } 803145837Smlaier } 804145837Smlaier 805145837Smlaier return (0); 806145837Smlaier} 807145837Smlaier 808145837Smlaier 809145837Smlaier/* 810145837Smlaier * Optimization pass #4: re-order 'quick' rules based on feedback from the 811145837Smlaier * currently running ruleset 812145837Smlaier */ 813145837Smlaierint 814145837Smlaierblock_feedback(struct pfctl *pf, struct superblock *block) 815145837Smlaier{ 816145837Smlaier TAILQ_HEAD( , pf_opt_rule) queue; 817145837Smlaier struct pf_opt_rule *por1, *por2; 818145837Smlaier u_int64_t total_count = 0; 819145837Smlaier struct pf_rule a, b; 820145837Smlaier 821145837Smlaier 822145837Smlaier /* 823145837Smlaier * Walk through all of the profiled superblock's rules and copy 824145837Smlaier * the counters onto our rules. 825145837Smlaier */ 826145837Smlaier TAILQ_FOREACH(por1, &block->sb_profiled_block->sb_rules, por_entry) { 827145837Smlaier comparable_rule(&a, &por1->por_rule, DC); 828171172Smlaier total_count += por1->por_rule.packets[0] + 829171172Smlaier por1->por_rule.packets[1]; 830145837Smlaier TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { 831145837Smlaier if (por2->por_profile_count) 832145837Smlaier continue; 833145837Smlaier comparable_rule(&b, &por2->por_rule, DC); 834145837Smlaier if (memcmp(&a, &b, sizeof(a)) == 0) { 835145837Smlaier por2->por_profile_count = 836171172Smlaier por1->por_rule.packets[0] + 837171172Smlaier por1->por_rule.packets[1]; 838145837Smlaier break; 839145837Smlaier } 840145837Smlaier } 841145837Smlaier } 842145837Smlaier superblock_free(pf, block->sb_profiled_block); 843145837Smlaier block->sb_profiled_block = NULL; 844145837Smlaier 845145837Smlaier /* 846145837Smlaier * Now we pull all of the rules off the superblock and re-insert them 847145837Smlaier * in sorted order. 848145837Smlaier */ 849145837Smlaier 850145837Smlaier TAILQ_INIT(&queue); 851145837Smlaier while ((por1 = TAILQ_FIRST(&block->sb_rules)) != NULL) { 852145837Smlaier TAILQ_REMOVE(&block->sb_rules, por1, por_entry); 853145837Smlaier TAILQ_INSERT_TAIL(&queue, por1, por_entry); 854145837Smlaier } 855145837Smlaier 856145837Smlaier while ((por1 = TAILQ_FIRST(&queue)) != NULL) { 857145837Smlaier TAILQ_REMOVE(&queue, por1, por_entry); 858145837Smlaier/* XXX I should sort all of the unused rules based on skip steps */ 859145837Smlaier TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { 860145837Smlaier if (por1->por_profile_count > por2->por_profile_count) { 861145837Smlaier TAILQ_INSERT_BEFORE(por2, por1, por_entry); 862145837Smlaier break; 863145837Smlaier } 864145837Smlaier } 865145840Smlaier#ifdef __FreeBSD__ 866145840Smlaier if (por2 == NULL) 867145840Smlaier#else 868145837Smlaier if (por2 == TAILQ_END(&block->sb_rules)) 869145840Smlaier#endif 870145837Smlaier TAILQ_INSERT_TAIL(&block->sb_rules, por1, por_entry); 871145837Smlaier } 872145837Smlaier 873145837Smlaier return (0); 874145837Smlaier} 875145837Smlaier 876145837Smlaier 877145837Smlaier/* 878145837Smlaier * Load the current ruleset from the kernel and try to associate them with 879145837Smlaier * the ruleset we're optimizing. 880145837Smlaier */ 881145837Smlaierint 882145837Smlaierload_feedback_profile(struct pfctl *pf, struct superblocks *superblocks) 883145837Smlaier{ 884145837Smlaier struct superblock *block, *blockcur; 885145837Smlaier struct superblocks prof_superblocks; 886145837Smlaier struct pf_opt_rule *por; 887145837Smlaier struct pf_opt_queue queue; 888145837Smlaier struct pfioc_rule pr; 889145837Smlaier struct pf_rule a, b; 890145837Smlaier int nr, mnr; 891145837Smlaier 892145837Smlaier TAILQ_INIT(&queue); 893145837Smlaier TAILQ_INIT(&prof_superblocks); 894145837Smlaier 895145837Smlaier memset(&pr, 0, sizeof(pr)); 896145837Smlaier pr.rule.action = PF_PASS; 897145837Smlaier if (ioctl(pf->dev, DIOCGETRULES, &pr)) { 898145837Smlaier warn("DIOCGETRULES"); 899145837Smlaier return (1); 900145837Smlaier } 901145837Smlaier mnr = pr.nr; 902145837Smlaier 903145837Smlaier DEBUG("Loading %d active rules for a feedback profile", mnr); 904145837Smlaier for (nr = 0; nr < mnr; ++nr) { 905171172Smlaier struct pf_ruleset *rs; 906145837Smlaier if ((por = calloc(1, sizeof(*por))) == NULL) { 907145837Smlaier warn("calloc"); 908145837Smlaier return (1); 909145837Smlaier } 910145837Smlaier pr.nr = nr; 911145837Smlaier if (ioctl(pf->dev, DIOCGETRULE, &pr)) { 912145837Smlaier warn("DIOCGETRULES"); 913145837Smlaier return (1); 914145837Smlaier } 915145837Smlaier memcpy(&por->por_rule, &pr.rule, sizeof(por->por_rule)); 916171172Smlaier rs = pf_find_or_create_ruleset(pr.anchor_call); 917171172Smlaier por->por_rule.anchor = rs->anchor; 918145837Smlaier if (TAILQ_EMPTY(&por->por_rule.rpool.list)) 919145837Smlaier memset(&por->por_rule.rpool, 0, 920145837Smlaier sizeof(por->por_rule.rpool)); 921145837Smlaier TAILQ_INSERT_TAIL(&queue, por, por_entry); 922145837Smlaier 923145837Smlaier /* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket, 924145837Smlaier * PF_PASS, pf->anchor) ??? 925145837Smlaier * ... pfctl_clear_pool(&pr.rule.rpool) 926145837Smlaier */ 927145837Smlaier } 928145837Smlaier 929145837Smlaier if (construct_superblocks(pf, &queue, &prof_superblocks)) 930145837Smlaier return (1); 931145837Smlaier 932145837Smlaier 933145837Smlaier /* 934145837Smlaier * Now we try to associate the active ruleset's superblocks with 935145837Smlaier * the superblocks we're compiling. 936145837Smlaier */ 937145837Smlaier block = TAILQ_FIRST(superblocks); 938145837Smlaier blockcur = TAILQ_FIRST(&prof_superblocks); 939145837Smlaier while (block && blockcur) { 940145837Smlaier comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, 941145837Smlaier BREAK); 942145837Smlaier comparable_rule(&b, &TAILQ_FIRST(&blockcur->sb_rules)->por_rule, 943145837Smlaier BREAK); 944145837Smlaier if (memcmp(&a, &b, sizeof(a)) == 0) { 945145837Smlaier /* The two superblocks lined up */ 946145837Smlaier block->sb_profiled_block = blockcur; 947145837Smlaier } else { 948145837Smlaier DEBUG("superblocks don't line up between #%d and #%d", 949145837Smlaier TAILQ_FIRST(&block->sb_rules)->por_rule.nr, 950145837Smlaier TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr); 951145837Smlaier break; 952145837Smlaier } 953145837Smlaier block = TAILQ_NEXT(block, sb_entry); 954145837Smlaier blockcur = TAILQ_NEXT(blockcur, sb_entry); 955145837Smlaier } 956145837Smlaier 957145837Smlaier 958145837Smlaier 959145837Smlaier /* Free any superblocks we couldn't link */ 960145837Smlaier while (blockcur) { 961145837Smlaier block = TAILQ_NEXT(blockcur, sb_entry); 962145837Smlaier superblock_free(pf, blockcur); 963145837Smlaier blockcur = block; 964145837Smlaier } 965145837Smlaier return (0); 966145837Smlaier} 967145837Smlaier 968145837Smlaier 969145837Smlaier/* 970145837Smlaier * Compare a rule to a skiplist to see if the rule is a member 971145837Smlaier */ 972145837Smlaierint 973145837Smlaierskip_compare(int skipnum, struct pf_skip_step *skiplist, 974145837Smlaier struct pf_opt_rule *por) 975145837Smlaier{ 976145837Smlaier struct pf_rule *a, *b; 977145837Smlaier if (skipnum >= PF_SKIP_COUNT || skipnum < 0) 978145837Smlaier errx(1, "skip_compare() out of bounds"); 979145837Smlaier a = &por->por_rule; 980145837Smlaier b = &TAILQ_FIRST(&skiplist->ps_rules)->por_rule; 981145837Smlaier 982145837Smlaier return ((skip_comparitors[skipnum])(a, b)); 983145837Smlaier} 984145837Smlaier 985145837Smlaier 986145837Smlaier/* 987145837Smlaier * Add a rule to a skiplist 988145837Smlaier */ 989145837Smlaiervoid 990145837Smlaierskip_append(struct superblock *superblock, int skipnum, 991145837Smlaier struct pf_skip_step *skiplist, struct pf_opt_rule *por) 992145837Smlaier{ 993145837Smlaier struct pf_skip_step *prev; 994145837Smlaier 995145837Smlaier skiplist->ps_count++; 996145837Smlaier TAILQ_INSERT_TAIL(&skiplist->ps_rules, por, por_skip_entry[skipnum]); 997145837Smlaier 998145837Smlaier /* Keep the list of skiplists sorted by whichever is larger */ 999145837Smlaier while ((prev = TAILQ_PREV(skiplist, skiplist, ps_entry)) && 1000145837Smlaier prev->ps_count < skiplist->ps_count) { 1001145837Smlaier TAILQ_REMOVE(&superblock->sb_skipsteps[skipnum], 1002145837Smlaier skiplist, ps_entry); 1003145837Smlaier TAILQ_INSERT_BEFORE(prev, skiplist, ps_entry); 1004145837Smlaier } 1005145837Smlaier} 1006145837Smlaier 1007145837Smlaier 1008145837Smlaier/* 1009145837Smlaier * Remove a rule from the other skiplist calculations. 1010145837Smlaier */ 1011145837Smlaiervoid 1012145837Smlaierremove_from_skipsteps(struct skiplist *head, struct superblock *block, 1013145837Smlaier struct pf_opt_rule *por, struct pf_skip_step *active_list) 1014145837Smlaier{ 1015145837Smlaier struct pf_skip_step *sk, *next; 1016145837Smlaier struct pf_opt_rule *p2; 1017145837Smlaier int i, found; 1018145837Smlaier 1019145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) { 1020145837Smlaier sk = TAILQ_FIRST(&block->sb_skipsteps[i]); 1021145837Smlaier if (sk == NULL || sk == active_list || sk->ps_count <= 1) 1022145837Smlaier continue; 1023145837Smlaier found = 0; 1024145837Smlaier do { 1025145837Smlaier TAILQ_FOREACH(p2, &sk->ps_rules, por_skip_entry[i]) 1026145837Smlaier if (p2 == por) { 1027145837Smlaier TAILQ_REMOVE(&sk->ps_rules, p2, 1028145837Smlaier por_skip_entry[i]); 1029145837Smlaier found = 1; 1030145837Smlaier sk->ps_count--; 1031145837Smlaier break; 1032145837Smlaier } 1033145837Smlaier } while (!found && (sk = TAILQ_NEXT(sk, ps_entry))); 1034145837Smlaier if (found && sk) { 1035145837Smlaier /* Does this change the sorting order? */ 1036145837Smlaier while ((next = TAILQ_NEXT(sk, ps_entry)) && 1037145837Smlaier next->ps_count > sk->ps_count) { 1038145837Smlaier TAILQ_REMOVE(head, sk, ps_entry); 1039145837Smlaier TAILQ_INSERT_AFTER(head, next, sk, ps_entry); 1040145837Smlaier } 1041145837Smlaier#ifdef OPT_DEBUG 1042145837Smlaier next = TAILQ_NEXT(sk, ps_entry); 1043145837Smlaier assert(next == NULL || next->ps_count <= sk->ps_count); 1044145837Smlaier#endif /* OPT_DEBUG */ 1045145837Smlaier } 1046145837Smlaier } 1047145837Smlaier} 1048145837Smlaier 1049145837Smlaier 1050145837Smlaier/* Compare two rules AF field for skiplist construction */ 1051145837Smlaierint 1052145837Smlaierskip_cmp_af(struct pf_rule *a, struct pf_rule *b) 1053145837Smlaier{ 1054145837Smlaier if (a->af != b->af || a->af == 0) 1055145837Smlaier return (1); 1056145837Smlaier return (0); 1057145837Smlaier} 1058145837Smlaier 1059145837Smlaier/* Compare two rules DIRECTION field for skiplist construction */ 1060145837Smlaierint 1061145837Smlaierskip_cmp_dir(struct pf_rule *a, struct pf_rule *b) 1062145837Smlaier{ 1063145837Smlaier if (a->direction == 0 || a->direction != b->direction) 1064145837Smlaier return (1); 1065145837Smlaier return (0); 1066145837Smlaier} 1067145837Smlaier 1068145837Smlaier/* Compare two rules DST Address field for skiplist construction */ 1069145837Smlaierint 1070145837Smlaierskip_cmp_dst_addr(struct pf_rule *a, struct pf_rule *b) 1071145837Smlaier{ 1072145837Smlaier if (a->dst.neg != b->dst.neg || 1073145837Smlaier a->dst.addr.type != b->dst.addr.type) 1074145837Smlaier return (1); 1075145837Smlaier /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 1076145837Smlaier * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || 1077145837Smlaier * a->proto == IPPROTO_ICMP 1078145837Smlaier * return (1); 1079145837Smlaier */ 1080145837Smlaier switch (a->dst.addr.type) { 1081145837Smlaier case PF_ADDR_ADDRMASK: 1082145837Smlaier if (memcmp(&a->dst.addr.v.a.addr, &b->dst.addr.v.a.addr, 1083145837Smlaier sizeof(a->dst.addr.v.a.addr)) || 1084145837Smlaier memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, 1085145837Smlaier sizeof(a->dst.addr.v.a.mask)) || 1086145837Smlaier (a->dst.addr.v.a.addr.addr32[0] == 0 && 1087145837Smlaier a->dst.addr.v.a.addr.addr32[1] == 0 && 1088145837Smlaier a->dst.addr.v.a.addr.addr32[2] == 0 && 1089145837Smlaier a->dst.addr.v.a.addr.addr32[3] == 0)) 1090145837Smlaier return (1); 1091145837Smlaier return (0); 1092145837Smlaier case PF_ADDR_DYNIFTL: 1093145837Smlaier if (strcmp(a->dst.addr.v.ifname, b->dst.addr.v.ifname) != 0 || 1094328649Spfg a->dst.addr.iflags != b->dst.addr.iflags || 1095145837Smlaier memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, 1096145837Smlaier sizeof(a->dst.addr.v.a.mask))) 1097145837Smlaier return (1); 1098145837Smlaier return (0); 1099145837Smlaier case PF_ADDR_NOROUTE: 1100171172Smlaier case PF_ADDR_URPFFAILED: 1101145837Smlaier return (0); 1102145837Smlaier case PF_ADDR_TABLE: 1103145837Smlaier return (strcmp(a->dst.addr.v.tblname, b->dst.addr.v.tblname)); 1104145837Smlaier } 1105145837Smlaier return (1); 1106145837Smlaier} 1107145837Smlaier 1108145837Smlaier/* Compare two rules DST port field for skiplist construction */ 1109145837Smlaierint 1110145837Smlaierskip_cmp_dst_port(struct pf_rule *a, struct pf_rule *b) 1111145837Smlaier{ 1112145837Smlaier /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 1113145837Smlaier * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || 1114145837Smlaier * a->proto == IPPROTO_ICMP 1115145837Smlaier * return (1); 1116145837Smlaier */ 1117145837Smlaier if (a->dst.port_op == PF_OP_NONE || a->dst.port_op != b->dst.port_op || 1118145837Smlaier a->dst.port[0] != b->dst.port[0] || 1119145837Smlaier a->dst.port[1] != b->dst.port[1]) 1120145837Smlaier return (1); 1121145837Smlaier return (0); 1122145837Smlaier} 1123145837Smlaier 1124145837Smlaier/* Compare two rules IFP field for skiplist construction */ 1125145837Smlaierint 1126145837Smlaierskip_cmp_ifp(struct pf_rule *a, struct pf_rule *b) 1127145837Smlaier{ 1128145837Smlaier if (strcmp(a->ifname, b->ifname) || a->ifname[0] == '\0') 1129145837Smlaier return (1); 1130145837Smlaier return (a->ifnot != b->ifnot); 1131145837Smlaier} 1132145837Smlaier 1133145837Smlaier/* Compare two rules PROTO field for skiplist construction */ 1134145837Smlaierint 1135145837Smlaierskip_cmp_proto(struct pf_rule *a, struct pf_rule *b) 1136145837Smlaier{ 1137145837Smlaier return (a->proto != b->proto || a->proto == 0); 1138145837Smlaier} 1139145837Smlaier 1140145837Smlaier/* Compare two rules SRC addr field for skiplist construction */ 1141145837Smlaierint 1142145837Smlaierskip_cmp_src_addr(struct pf_rule *a, struct pf_rule *b) 1143145837Smlaier{ 1144145837Smlaier if (a->src.neg != b->src.neg || 1145145837Smlaier a->src.addr.type != b->src.addr.type) 1146145837Smlaier return (1); 1147145837Smlaier /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 1148145837Smlaier * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || 1149145837Smlaier * a->proto == IPPROTO_ICMP 1150145837Smlaier * return (1); 1151145837Smlaier */ 1152145837Smlaier switch (a->src.addr.type) { 1153145837Smlaier case PF_ADDR_ADDRMASK: 1154145837Smlaier if (memcmp(&a->src.addr.v.a.addr, &b->src.addr.v.a.addr, 1155145837Smlaier sizeof(a->src.addr.v.a.addr)) || 1156145837Smlaier memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, 1157145837Smlaier sizeof(a->src.addr.v.a.mask)) || 1158145837Smlaier (a->src.addr.v.a.addr.addr32[0] == 0 && 1159145837Smlaier a->src.addr.v.a.addr.addr32[1] == 0 && 1160145837Smlaier a->src.addr.v.a.addr.addr32[2] == 0 && 1161145837Smlaier a->src.addr.v.a.addr.addr32[3] == 0)) 1162145837Smlaier return (1); 1163145837Smlaier return (0); 1164145837Smlaier case PF_ADDR_DYNIFTL: 1165145837Smlaier if (strcmp(a->src.addr.v.ifname, b->src.addr.v.ifname) != 0 || 1166328649Spfg a->src.addr.iflags != b->src.addr.iflags || 1167145837Smlaier memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, 1168145837Smlaier sizeof(a->src.addr.v.a.mask))) 1169145837Smlaier return (1); 1170145837Smlaier return (0); 1171145837Smlaier case PF_ADDR_NOROUTE: 1172171172Smlaier case PF_ADDR_URPFFAILED: 1173145837Smlaier return (0); 1174145837Smlaier case PF_ADDR_TABLE: 1175145837Smlaier return (strcmp(a->src.addr.v.tblname, b->src.addr.v.tblname)); 1176145837Smlaier } 1177145837Smlaier return (1); 1178145837Smlaier} 1179145837Smlaier 1180145837Smlaier/* Compare two rules SRC port field for skiplist construction */ 1181145837Smlaierint 1182145837Smlaierskip_cmp_src_port(struct pf_rule *a, struct pf_rule *b) 1183145837Smlaier{ 1184145837Smlaier if (a->src.port_op == PF_OP_NONE || a->src.port_op != b->src.port_op || 1185145837Smlaier a->src.port[0] != b->src.port[0] || 1186145837Smlaier a->src.port[1] != b->src.port[1]) 1187145837Smlaier return (1); 1188145837Smlaier /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 1189145837Smlaier * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || 1190145837Smlaier * a->proto == IPPROTO_ICMP 1191145837Smlaier * return (1); 1192145837Smlaier */ 1193145837Smlaier return (0); 1194145837Smlaier} 1195145837Smlaier 1196145837Smlaier 1197145837Smlaiervoid 1198145837Smlaierskip_init(void) 1199145837Smlaier{ 1200145837Smlaier struct { 1201145837Smlaier char *name; 1202145837Smlaier int skipnum; 1203145837Smlaier int (*func)(struct pf_rule *, struct pf_rule *); 1204145837Smlaier } comps[] = PF_SKIP_COMPARITORS; 1205145837Smlaier int skipnum, i; 1206145837Smlaier 1207145837Smlaier for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) { 1208145837Smlaier for (i = 0; i < sizeof(comps)/sizeof(*comps); i++) 1209145837Smlaier if (comps[i].skipnum == skipnum) { 1210145837Smlaier skip_comparitors[skipnum] = comps[i].func; 1211145837Smlaier skip_comparitors_names[skipnum] = comps[i].name; 1212145837Smlaier } 1213145837Smlaier } 1214145837Smlaier for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) 1215145837Smlaier if (skip_comparitors[skipnum] == NULL) 1216145837Smlaier errx(1, "Need to add skip step comparitor to pfctl?!"); 1217145837Smlaier} 1218145837Smlaier 1219145837Smlaier/* 1220145837Smlaier * Add a host/netmask to a table 1221145837Smlaier */ 1222145837Smlaierint 1223145837Smlaieradd_opt_table(struct pfctl *pf, struct pf_opt_tbl **tbl, sa_family_t af, 1224145837Smlaier struct pf_rule_addr *addr) 1225145837Smlaier{ 1226145837Smlaier#ifdef OPT_DEBUG 1227145837Smlaier char buf[128]; 1228145837Smlaier#endif /* OPT_DEBUG */ 1229145837Smlaier static int tablenum = 0; 1230145837Smlaier struct node_host node_host; 1231145837Smlaier 1232145837Smlaier if (*tbl == NULL) { 1233145837Smlaier if ((*tbl = calloc(1, sizeof(**tbl))) == NULL || 1234145837Smlaier ((*tbl)->pt_buf = calloc(1, sizeof(*(*tbl)->pt_buf))) == 1235145837Smlaier NULL) 1236145837Smlaier err(1, "calloc"); 1237145837Smlaier (*tbl)->pt_buf->pfrb_type = PFRB_ADDRS; 1238145837Smlaier SIMPLEQ_INIT(&(*tbl)->pt_nodes); 1239145837Smlaier 1240145837Smlaier /* This is just a temporary table name */ 1241145837Smlaier snprintf((*tbl)->pt_name, sizeof((*tbl)->pt_name), "%s%d", 1242145837Smlaier PF_OPT_TABLE_PREFIX, tablenum++); 1243145837Smlaier DEBUG("creating table <%s>", (*tbl)->pt_name); 1244145837Smlaier } 1245145837Smlaier 1246145837Smlaier memset(&node_host, 0, sizeof(node_host)); 1247145837Smlaier node_host.af = af; 1248145837Smlaier node_host.addr = addr->addr; 1249145837Smlaier 1250145837Smlaier#ifdef OPT_DEBUG 1251145837Smlaier DEBUG("<%s> adding %s/%d", (*tbl)->pt_name, inet_ntop(af, 1252145837Smlaier &node_host.addr.v.a.addr, buf, sizeof(buf)), 1253145837Smlaier unmask(&node_host.addr.v.a.mask, af)); 1254145837Smlaier#endif /* OPT_DEBUG */ 1255145837Smlaier 1256145837Smlaier if (append_addr_host((*tbl)->pt_buf, &node_host, 0, 0)) { 1257145837Smlaier warn("failed to add host"); 1258145837Smlaier return (1); 1259145837Smlaier } 1260145837Smlaier if (pf->opts & PF_OPT_VERBOSE) { 1261145837Smlaier struct node_tinit *ti; 1262145837Smlaier 1263145837Smlaier if ((ti = calloc(1, sizeof(*ti))) == NULL) 1264145837Smlaier err(1, "malloc"); 1265145837Smlaier if ((ti->host = malloc(sizeof(*ti->host))) == NULL) 1266145837Smlaier err(1, "malloc"); 1267145837Smlaier memcpy(ti->host, &node_host, sizeof(*ti->host)); 1268145837Smlaier SIMPLEQ_INSERT_TAIL(&(*tbl)->pt_nodes, ti, entries); 1269145837Smlaier } 1270145837Smlaier 1271145837Smlaier (*tbl)->pt_rulecount++; 1272145837Smlaier if ((*tbl)->pt_rulecount == TABLE_THRESHOLD) 1273145837Smlaier DEBUG("table <%s> now faster than skip steps", (*tbl)->pt_name); 1274145837Smlaier 1275145837Smlaier return (0); 1276145837Smlaier} 1277145837Smlaier 1278145837Smlaier 1279145837Smlaier/* 1280145837Smlaier * Do the dirty work of choosing an unused table name and creating it. 1281145837Smlaier * (be careful with the table name, it might already be used in another anchor) 1282145837Smlaier */ 1283145837Smlaierint 1284145837Smlaierpf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl) 1285145837Smlaier{ 1286145837Smlaier static int tablenum; 1287145837Smlaier struct pfr_table *t; 1288145837Smlaier 1289145837Smlaier if (table_buffer.pfrb_type == 0) { 1290145837Smlaier /* Initialize the list of tables */ 1291145837Smlaier table_buffer.pfrb_type = PFRB_TABLES; 1292145837Smlaier for (;;) { 1293145837Smlaier pfr_buf_grow(&table_buffer, table_buffer.pfrb_size); 1294145837Smlaier table_buffer.pfrb_size = table_buffer.pfrb_msize; 1295145837Smlaier if (pfr_get_tables(NULL, table_buffer.pfrb_caddr, 1296145837Smlaier &table_buffer.pfrb_size, PFR_FLAG_ALLRSETS)) 1297145837Smlaier err(1, "pfr_get_tables"); 1298145837Smlaier if (table_buffer.pfrb_size <= table_buffer.pfrb_msize) 1299145837Smlaier break; 1300145837Smlaier } 1301145837Smlaier table_identifier = arc4random(); 1302145837Smlaier } 1303145837Smlaier 1304145837Smlaier /* XXX would be *really* nice to avoid duplicating identical tables */ 1305145837Smlaier 1306145837Smlaier /* Now we have to pick a table name that isn't used */ 1307145837Smlaieragain: 1308145837Smlaier DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl->pt_name, 1309145837Smlaier PF_OPT_TABLE_PREFIX, table_identifier, tablenum); 1310145837Smlaier snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d", 1311145837Smlaier PF_OPT_TABLE_PREFIX, table_identifier, tablenum); 1312145837Smlaier PFRB_FOREACH(t, &table_buffer) { 1313145837Smlaier if (strcasecmp(t->pfrt_name, tbl->pt_name) == 0) { 1314145837Smlaier /* Collision. Try again */ 1315145837Smlaier DEBUG("wow, table <%s> in use. trying again", 1316145837Smlaier tbl->pt_name); 1317145837Smlaier table_identifier = arc4random(); 1318145837Smlaier goto again; 1319145837Smlaier } 1320145837Smlaier } 1321145837Smlaier tablenum++; 1322145837Smlaier 1323145837Smlaier 1324171172Smlaier if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1, 1325223637Sbz pf->astack[0]->name, tbl->pt_buf, pf->astack[0]->ruleset.tticket)) { 1326223637Sbz warn("failed to create table %s in %s", 1327223637Sbz tbl->pt_name, pf->astack[0]->name); 1328145837Smlaier return (1); 1329145837Smlaier } 1330145837Smlaier return (0); 1331145837Smlaier} 1332145837Smlaier 1333145837Smlaier/* 1334145837Smlaier * Partition the flat ruleset into a list of distinct superblocks 1335145837Smlaier */ 1336145837Smlaierint 1337145837Smlaierconstruct_superblocks(struct pfctl *pf, struct pf_opt_queue *opt_queue, 1338145837Smlaier struct superblocks *superblocks) 1339145837Smlaier{ 1340145837Smlaier struct superblock *block = NULL; 1341145837Smlaier struct pf_opt_rule *por; 1342145837Smlaier int i; 1343145837Smlaier 1344145837Smlaier while (!TAILQ_EMPTY(opt_queue)) { 1345145837Smlaier por = TAILQ_FIRST(opt_queue); 1346145837Smlaier TAILQ_REMOVE(opt_queue, por, por_entry); 1347145837Smlaier if (block == NULL || !superblock_inclusive(block, por)) { 1348145837Smlaier if ((block = calloc(1, sizeof(*block))) == NULL) { 1349145837Smlaier warn("calloc"); 1350145837Smlaier return (1); 1351145837Smlaier } 1352145837Smlaier TAILQ_INIT(&block->sb_rules); 1353145837Smlaier for (i = 0; i < PF_SKIP_COUNT; i++) 1354145837Smlaier TAILQ_INIT(&block->sb_skipsteps[i]); 1355145837Smlaier TAILQ_INSERT_TAIL(superblocks, block, sb_entry); 1356145837Smlaier } 1357145837Smlaier TAILQ_INSERT_TAIL(&block->sb_rules, por, por_entry); 1358145837Smlaier } 1359145837Smlaier 1360145837Smlaier return (0); 1361145837Smlaier} 1362145837Smlaier 1363145837Smlaier 1364145837Smlaier/* 1365145837Smlaier * Compare two rule addresses 1366145837Smlaier */ 1367145837Smlaierint 1368145837Smlaieraddrs_equal(struct pf_rule_addr *a, struct pf_rule_addr *b) 1369145837Smlaier{ 1370145837Smlaier if (a->neg != b->neg) 1371145837Smlaier return (0); 1372145837Smlaier return (memcmp(&a->addr, &b->addr, sizeof(a->addr)) == 0); 1373145837Smlaier} 1374145837Smlaier 1375145837Smlaier 1376145837Smlaier/* 1377145837Smlaier * The addresses are not equal, but can we combine them into one table? 1378145837Smlaier */ 1379145837Smlaierint 1380145837Smlaieraddrs_combineable(struct pf_rule_addr *a, struct pf_rule_addr *b) 1381145837Smlaier{ 1382145837Smlaier if (a->addr.type != PF_ADDR_ADDRMASK || 1383145837Smlaier b->addr.type != PF_ADDR_ADDRMASK) 1384145837Smlaier return (0); 1385145837Smlaier if (a->neg != b->neg || a->port_op != b->port_op || 1386145837Smlaier a->port[0] != b->port[0] || a->port[1] != b->port[1]) 1387145837Smlaier return (0); 1388145837Smlaier return (1); 1389145837Smlaier} 1390145837Smlaier 1391145837Smlaier 1392145837Smlaier/* 1393145837Smlaier * Are we allowed to combine these two rules 1394145837Smlaier */ 1395145837Smlaierint 1396145837Smlaierrules_combineable(struct pf_rule *p1, struct pf_rule *p2) 1397145837Smlaier{ 1398145837Smlaier struct pf_rule a, b; 1399145837Smlaier 1400145837Smlaier comparable_rule(&a, p1, COMBINED); 1401145837Smlaier comparable_rule(&b, p2, COMBINED); 1402145837Smlaier return (memcmp(&a, &b, sizeof(a)) == 0); 1403145837Smlaier} 1404145837Smlaier 1405145837Smlaier 1406145837Smlaier/* 1407145837Smlaier * Can a rule be included inside a superblock 1408145837Smlaier */ 1409145837Smlaierint 1410145837Smlaiersuperblock_inclusive(struct superblock *block, struct pf_opt_rule *por) 1411145837Smlaier{ 1412145837Smlaier struct pf_rule a, b; 1413145837Smlaier int i, j; 1414145837Smlaier 1415145837Smlaier /* First check for hard breaks */ 1416145837Smlaier for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) { 1417145837Smlaier if (pf_rule_desc[i].prf_type == BARRIER) { 1418145837Smlaier for (j = 0; j < pf_rule_desc[i].prf_size; j++) 1419145837Smlaier if (((char *)&por->por_rule)[j + 1420145837Smlaier pf_rule_desc[i].prf_offset] != 0) 1421145837Smlaier return (0); 1422145837Smlaier } 1423145837Smlaier } 1424145837Smlaier 1425171172Smlaier /* per-rule src-track is also a hard break */ 1426171172Smlaier if (por->por_rule.rule_flag & PFRULE_RULESRCTRACK) 1427145837Smlaier return (0); 1428145837Smlaier 1429171172Smlaier /* 1430223637Sbz * Have to handle interface groups separately. Consider the following 1431171172Smlaier * rules: 1432171172Smlaier * block on EXTIFS to any port 22 1433171172Smlaier * pass on em0 to any port 22 1434171172Smlaier * (where EXTIFS is an arbitrary interface group) 1435171172Smlaier * The optimizer may decide to re-order the pass rule in front of the 1436171172Smlaier * block rule. But what if EXTIFS includes em0??? Such a reordering 1437171172Smlaier * would change the meaning of the ruleset. 1438171172Smlaier * We can't just lookup the EXTIFS group and check if em0 is a member 1439171172Smlaier * because the user is allowed to add interfaces to a group during 1440171172Smlaier * runtime. 1441171172Smlaier * Ergo interface groups become a defacto superblock break :-( 1442171172Smlaier */ 1443171172Smlaier if (interface_group(por->por_rule.ifname) || 1444171172Smlaier interface_group(TAILQ_FIRST(&block->sb_rules)->por_rule.ifname)) { 1445171172Smlaier if (strcasecmp(por->por_rule.ifname, 1446171172Smlaier TAILQ_FIRST(&block->sb_rules)->por_rule.ifname) != 0) 1447171172Smlaier return (0); 1448171172Smlaier } 1449171172Smlaier 1450145837Smlaier comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE); 1451145837Smlaier comparable_rule(&b, &por->por_rule, NOMERGE); 1452171172Smlaier if (memcmp(&a, &b, sizeof(a)) == 0) 1453145837Smlaier return (1); 1454145837Smlaier 1455145837Smlaier#ifdef OPT_DEBUG 1456145837Smlaier for (i = 0; i < sizeof(por->por_rule); i++) { 1457145837Smlaier int closest = -1; 1458145837Smlaier if (((u_int8_t *)&a)[i] != ((u_int8_t *)&b)[i]) { 1459145837Smlaier for (j = 0; j < sizeof(pf_rule_desc) / 1460145837Smlaier sizeof(*pf_rule_desc); j++) { 1461145837Smlaier if (i >= pf_rule_desc[j].prf_offset && 1462145837Smlaier i < pf_rule_desc[j].prf_offset + 1463145837Smlaier pf_rule_desc[j].prf_size) { 1464145837Smlaier DEBUG("superblock break @ %d due to %s", 1465145837Smlaier por->por_rule.nr, 1466145837Smlaier pf_rule_desc[j].prf_name); 1467145837Smlaier return (0); 1468145837Smlaier } 1469145837Smlaier if (i > pf_rule_desc[j].prf_offset) { 1470145837Smlaier if (closest == -1 || 1471145837Smlaier i-pf_rule_desc[j].prf_offset < 1472145837Smlaier i-pf_rule_desc[closest].prf_offset) 1473145837Smlaier closest = j; 1474145837Smlaier } 1475145837Smlaier } 1476145837Smlaier 1477145837Smlaier if (closest >= 0) 1478145837Smlaier DEBUG("superblock break @ %d on %s+%xh", 1479145837Smlaier por->por_rule.nr, 1480145837Smlaier pf_rule_desc[closest].prf_name, 1481145837Smlaier i - pf_rule_desc[closest].prf_offset - 1482145837Smlaier pf_rule_desc[closest].prf_size); 1483145837Smlaier else 1484145837Smlaier DEBUG("superblock break @ %d on field @ %d", 1485145837Smlaier por->por_rule.nr, i); 1486145837Smlaier return (0); 1487145837Smlaier } 1488145837Smlaier } 1489145837Smlaier#endif /* OPT_DEBUG */ 1490145837Smlaier 1491145837Smlaier return (0); 1492145837Smlaier} 1493145837Smlaier 1494145837Smlaier 1495145837Smlaier/* 1496171172Smlaier * Figure out if an interface name is an actual interface or actually a 1497171172Smlaier * group of interfaces. 1498171172Smlaier */ 1499171172Smlaierint 1500171172Smlaierinterface_group(const char *ifname) 1501171172Smlaier{ 1502171172Smlaier if (ifname == NULL || !ifname[0]) 1503171172Smlaier return (0); 1504171172Smlaier 1505171172Smlaier /* Real interfaces must end in a number, interface groups do not */ 1506171172Smlaier if (isdigit(ifname[strlen(ifname) - 1])) 1507171172Smlaier return (0); 1508171172Smlaier else 1509171172Smlaier return (1); 1510171172Smlaier} 1511171172Smlaier 1512171172Smlaier 1513171172Smlaier/* 1514145837Smlaier * Make a rule that can directly compared by memcmp() 1515145837Smlaier */ 1516145837Smlaiervoid 1517145837Smlaiercomparable_rule(struct pf_rule *dst, const struct pf_rule *src, int type) 1518145837Smlaier{ 1519145837Smlaier int i; 1520145837Smlaier /* 1521145837Smlaier * To simplify the comparison, we just zero out the fields that are 1522145837Smlaier * allowed to be different and then do a simple memcmp() 1523145837Smlaier */ 1524145837Smlaier memcpy(dst, src, sizeof(*dst)); 1525145837Smlaier for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) 1526145837Smlaier if (pf_rule_desc[i].prf_type >= type) { 1527145837Smlaier#ifdef OPT_DEBUG 1528145837Smlaier assert(pf_rule_desc[i].prf_type != NEVER || 1529145837Smlaier *(((char *)dst) + pf_rule_desc[i].prf_offset) == 0); 1530145837Smlaier#endif /* OPT_DEBUG */ 1531145837Smlaier memset(((char *)dst) + pf_rule_desc[i].prf_offset, 0, 1532145837Smlaier pf_rule_desc[i].prf_size); 1533145837Smlaier } 1534145837Smlaier} 1535145837Smlaier 1536145837Smlaier 1537145837Smlaier/* 1538145837Smlaier * Remove superset information from two rules so we can directly compare them 1539145837Smlaier * with memcmp() 1540145837Smlaier */ 1541145837Smlaiervoid 1542145837Smlaierexclude_supersets(struct pf_rule *super, struct pf_rule *sub) 1543145837Smlaier{ 1544145837Smlaier if (super->ifname[0] == '\0') 1545145837Smlaier memset(sub->ifname, 0, sizeof(sub->ifname)); 1546145837Smlaier if (super->direction == PF_INOUT) 1547145837Smlaier sub->direction = PF_INOUT; 1548145837Smlaier if ((super->proto == 0 || super->proto == sub->proto) && 1549145837Smlaier super->flags == 0 && super->flagset == 0 && (sub->flags || 1550145837Smlaier sub->flagset)) { 1551145837Smlaier sub->flags = super->flags; 1552145837Smlaier sub->flagset = super->flagset; 1553145837Smlaier } 1554145837Smlaier if (super->proto == 0) 1555145837Smlaier sub->proto = 0; 1556145837Smlaier 1557145837Smlaier if (super->src.port_op == 0) { 1558145837Smlaier sub->src.port_op = 0; 1559145837Smlaier sub->src.port[0] = 0; 1560145837Smlaier sub->src.port[1] = 0; 1561145837Smlaier } 1562145837Smlaier if (super->dst.port_op == 0) { 1563145837Smlaier sub->dst.port_op = 0; 1564145837Smlaier sub->dst.port[0] = 0; 1565145837Smlaier sub->dst.port[1] = 0; 1566145837Smlaier } 1567145837Smlaier 1568145837Smlaier if (super->src.addr.type == PF_ADDR_ADDRMASK && !super->src.neg && 1569145837Smlaier !sub->src.neg && super->src.addr.v.a.mask.addr32[0] == 0 && 1570145837Smlaier super->src.addr.v.a.mask.addr32[1] == 0 && 1571145837Smlaier super->src.addr.v.a.mask.addr32[2] == 0 && 1572145837Smlaier super->src.addr.v.a.mask.addr32[3] == 0) 1573145837Smlaier memset(&sub->src.addr, 0, sizeof(sub->src.addr)); 1574145837Smlaier else if (super->src.addr.type == PF_ADDR_ADDRMASK && 1575145837Smlaier sub->src.addr.type == PF_ADDR_ADDRMASK && 1576145837Smlaier super->src.neg == sub->src.neg && 1577145837Smlaier super->af == sub->af && 1578145837Smlaier unmask(&super->src.addr.v.a.mask, super->af) < 1579145837Smlaier unmask(&sub->src.addr.v.a.mask, sub->af) && 1580145837Smlaier super->src.addr.v.a.addr.addr32[0] == 1581145837Smlaier (sub->src.addr.v.a.addr.addr32[0] & 1582145837Smlaier super->src.addr.v.a.mask.addr32[0]) && 1583145837Smlaier super->src.addr.v.a.addr.addr32[1] == 1584145837Smlaier (sub->src.addr.v.a.addr.addr32[1] & 1585145837Smlaier super->src.addr.v.a.mask.addr32[1]) && 1586145837Smlaier super->src.addr.v.a.addr.addr32[2] == 1587145837Smlaier (sub->src.addr.v.a.addr.addr32[2] & 1588145837Smlaier super->src.addr.v.a.mask.addr32[2]) && 1589145837Smlaier super->src.addr.v.a.addr.addr32[3] == 1590145837Smlaier (sub->src.addr.v.a.addr.addr32[3] & 1591145837Smlaier super->src.addr.v.a.mask.addr32[3])) { 1592145837Smlaier /* sub->src.addr is a subset of super->src.addr/mask */ 1593145837Smlaier memcpy(&sub->src.addr, &super->src.addr, sizeof(sub->src.addr)); 1594145837Smlaier } 1595145837Smlaier 1596145837Smlaier if (super->dst.addr.type == PF_ADDR_ADDRMASK && !super->dst.neg && 1597145837Smlaier !sub->dst.neg && super->dst.addr.v.a.mask.addr32[0] == 0 && 1598145837Smlaier super->dst.addr.v.a.mask.addr32[1] == 0 && 1599145837Smlaier super->dst.addr.v.a.mask.addr32[2] == 0 && 1600145837Smlaier super->dst.addr.v.a.mask.addr32[3] == 0) 1601145837Smlaier memset(&sub->dst.addr, 0, sizeof(sub->dst.addr)); 1602145837Smlaier else if (super->dst.addr.type == PF_ADDR_ADDRMASK && 1603145837Smlaier sub->dst.addr.type == PF_ADDR_ADDRMASK && 1604145837Smlaier super->dst.neg == sub->dst.neg && 1605145837Smlaier super->af == sub->af && 1606145837Smlaier unmask(&super->dst.addr.v.a.mask, super->af) < 1607145837Smlaier unmask(&sub->dst.addr.v.a.mask, sub->af) && 1608145837Smlaier super->dst.addr.v.a.addr.addr32[0] == 1609145837Smlaier (sub->dst.addr.v.a.addr.addr32[0] & 1610145837Smlaier super->dst.addr.v.a.mask.addr32[0]) && 1611145837Smlaier super->dst.addr.v.a.addr.addr32[1] == 1612145837Smlaier (sub->dst.addr.v.a.addr.addr32[1] & 1613145837Smlaier super->dst.addr.v.a.mask.addr32[1]) && 1614145837Smlaier super->dst.addr.v.a.addr.addr32[2] == 1615145837Smlaier (sub->dst.addr.v.a.addr.addr32[2] & 1616145837Smlaier super->dst.addr.v.a.mask.addr32[2]) && 1617145837Smlaier super->dst.addr.v.a.addr.addr32[3] == 1618145837Smlaier (sub->dst.addr.v.a.addr.addr32[3] & 1619145837Smlaier super->dst.addr.v.a.mask.addr32[3])) { 1620145837Smlaier /* sub->dst.addr is a subset of super->dst.addr/mask */ 1621145837Smlaier memcpy(&sub->dst.addr, &super->dst.addr, sizeof(sub->dst.addr)); 1622145837Smlaier } 1623145837Smlaier 1624145837Smlaier if (super->af == 0) 1625145837Smlaier sub->af = 0; 1626145837Smlaier} 1627145837Smlaier 1628145837Smlaier 1629145837Smlaiervoid 1630145837Smlaiersuperblock_free(struct pfctl *pf, struct superblock *block) 1631145837Smlaier{ 1632145837Smlaier struct pf_opt_rule *por; 1633145837Smlaier while ((por = TAILQ_FIRST(&block->sb_rules))) { 1634145837Smlaier TAILQ_REMOVE(&block->sb_rules, por, por_entry); 1635145837Smlaier if (por->por_src_tbl) { 1636145837Smlaier if (por->por_src_tbl->pt_buf) { 1637145837Smlaier pfr_buf_clear(por->por_src_tbl->pt_buf); 1638145837Smlaier free(por->por_src_tbl->pt_buf); 1639145837Smlaier } 1640145837Smlaier free(por->por_src_tbl); 1641145837Smlaier } 1642145837Smlaier if (por->por_dst_tbl) { 1643145837Smlaier if (por->por_dst_tbl->pt_buf) { 1644145837Smlaier pfr_buf_clear(por->por_dst_tbl->pt_buf); 1645145837Smlaier free(por->por_dst_tbl->pt_buf); 1646145837Smlaier } 1647145837Smlaier free(por->por_dst_tbl); 1648145837Smlaier } 1649145837Smlaier free(por); 1650145837Smlaier } 1651145837Smlaier if (block->sb_profiled_block) 1652145837Smlaier superblock_free(pf, block->sb_profiled_block); 1653145837Smlaier free(block); 1654145837Smlaier} 1655145837Smlaier 1656