[084d4db] | 1 | #include <machine/rtems-bsd-user-space.h> |
---|
| 2 | |
---|
| 3 | /* $OpenBSD: pfctl_optimize.c,v 1.17 2008/05/06 03:45:21 mpf Exp $ */ |
---|
| 4 | |
---|
| 5 | /* |
---|
| 6 | * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org> |
---|
| 7 | * |
---|
| 8 | * Permission to use, copy, modify, and distribute this software for any |
---|
| 9 | * purpose with or without fee is hereby granted, provided that the above |
---|
| 10 | * copyright notice and this permission notice appear in all copies. |
---|
| 11 | * |
---|
| 12 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
---|
| 13 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
---|
| 14 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
---|
| 15 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
---|
| 16 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
---|
| 17 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
---|
| 18 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
---|
| 19 | */ |
---|
| 20 | |
---|
| 21 | #include <sys/cdefs.h> |
---|
| 22 | __FBSDID("$FreeBSD$"); |
---|
| 23 | |
---|
| 24 | #include <rtems/bsd/sys/types.h> |
---|
| 25 | #include <sys/ioctl.h> |
---|
| 26 | #include <sys/socket.h> |
---|
| 27 | |
---|
| 28 | #include <net/if.h> |
---|
| 29 | #include <net/pfvar.h> |
---|
| 30 | |
---|
| 31 | #include <netinet/in.h> |
---|
| 32 | #include <arpa/inet.h> |
---|
| 33 | |
---|
| 34 | #include <assert.h> |
---|
| 35 | #include <ctype.h> |
---|
| 36 | #include <err.h> |
---|
| 37 | #include <errno.h> |
---|
| 38 | #include <stddef.h> |
---|
| 39 | #include <stdio.h> |
---|
| 40 | #include <stdlib.h> |
---|
| 41 | #include <string.h> |
---|
| 42 | |
---|
| 43 | #include "pfctl_parser.h" |
---|
| 44 | #include "pfctl.h" |
---|
| 45 | |
---|
| 46 | /* The size at which a table becomes faster than individual rules */ |
---|
| 47 | #define TABLE_THRESHOLD 6 |
---|
| 48 | |
---|
| 49 | |
---|
| 50 | /* #define OPT_DEBUG 1 */ |
---|
| 51 | #ifdef OPT_DEBUG |
---|
| 52 | # define DEBUG(str, v...) \ |
---|
| 53 | printf("%s: " str "\n", __FUNCTION__ , ## v) |
---|
| 54 | #else |
---|
| 55 | # define DEBUG(str, v...) ((void)0) |
---|
| 56 | #endif |
---|
| 57 | |
---|
| 58 | |
---|
| 59 | /* |
---|
| 60 | * A container that lets us sort a superblock to optimize the skip step jumps |
---|
| 61 | */ |
---|
| 62 | struct pf_skip_step { |
---|
| 63 | int ps_count; /* number of items */ |
---|
| 64 | TAILQ_HEAD( , pf_opt_rule) ps_rules; |
---|
| 65 | TAILQ_ENTRY(pf_skip_step) ps_entry; |
---|
| 66 | }; |
---|
| 67 | |
---|
| 68 | |
---|
| 69 | /* |
---|
| 70 | * A superblock is a block of adjacent rules of similar action. If there |
---|
| 71 | * are five PASS rules in a row, they all become members of a superblock. |
---|
| 72 | * Once we have a superblock, we are free to re-order any rules within it |
---|
| 73 | * in order to improve performance; if a packet is passed, it doesn't matter |
---|
| 74 | * who passed it. |
---|
| 75 | */ |
---|
| 76 | struct superblock { |
---|
| 77 | TAILQ_HEAD( , pf_opt_rule) sb_rules; |
---|
| 78 | TAILQ_ENTRY(superblock) sb_entry; |
---|
| 79 | struct superblock *sb_profiled_block; |
---|
| 80 | TAILQ_HEAD(skiplist, pf_skip_step) sb_skipsteps[PF_SKIP_COUNT]; |
---|
| 81 | }; |
---|
| 82 | TAILQ_HEAD(superblocks, superblock); |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | /* |
---|
| 86 | * Description of the PF rule structure. |
---|
| 87 | */ |
---|
| 88 | enum { |
---|
| 89 | BARRIER, /* the presence of the field puts the rule in it's own block */ |
---|
| 90 | BREAK, /* the field may not differ between rules in a superblock */ |
---|
| 91 | NOMERGE, /* the field may not differ between rules when combined */ |
---|
| 92 | COMBINED, /* the field may itself be combined with other rules */ |
---|
| 93 | DC, /* we just don't care about the field */ |
---|
| 94 | NEVER}; /* we should never see this field set?!? */ |
---|
| 95 | struct pf_rule_field { |
---|
| 96 | const char *prf_name; |
---|
| 97 | int prf_type; |
---|
| 98 | size_t prf_offset; |
---|
| 99 | size_t prf_size; |
---|
| 100 | } pf_rule_desc[] = { |
---|
| 101 | #define PF_RULE_FIELD(field, ty) \ |
---|
| 102 | {#field, \ |
---|
| 103 | ty, \ |
---|
| 104 | offsetof(struct pf_rule, field), \ |
---|
| 105 | sizeof(((struct pf_rule *)0)->field)} |
---|
| 106 | |
---|
| 107 | |
---|
| 108 | /* |
---|
| 109 | * The presence of these fields in a rule put the rule in it's own |
---|
| 110 | * superblock. Thus it will not be optimized. It also prevents the |
---|
| 111 | * rule from being re-ordered at all. |
---|
| 112 | */ |
---|
| 113 | PF_RULE_FIELD(label, BARRIER), |
---|
| 114 | PF_RULE_FIELD(prob, BARRIER), |
---|
| 115 | PF_RULE_FIELD(max_states, BARRIER), |
---|
| 116 | PF_RULE_FIELD(max_src_nodes, BARRIER), |
---|
| 117 | PF_RULE_FIELD(max_src_states, BARRIER), |
---|
| 118 | PF_RULE_FIELD(max_src_conn, BARRIER), |
---|
| 119 | PF_RULE_FIELD(max_src_conn_rate, BARRIER), |
---|
| 120 | PF_RULE_FIELD(anchor, BARRIER), /* for now */ |
---|
| 121 | |
---|
| 122 | /* |
---|
| 123 | * These fields must be the same between all rules in the same superblock. |
---|
| 124 | * These rules are allowed to be re-ordered but only among like rules. |
---|
| 125 | * For instance we can re-order all 'tag "foo"' rules because they have the |
---|
| 126 | * same tag. But we can not re-order between a 'tag "foo"' and a |
---|
| 127 | * 'tag "bar"' since that would change the meaning of the ruleset. |
---|
| 128 | */ |
---|
| 129 | PF_RULE_FIELD(tagname, BREAK), |
---|
| 130 | PF_RULE_FIELD(keep_state, BREAK), |
---|
| 131 | PF_RULE_FIELD(qname, BREAK), |
---|
| 132 | PF_RULE_FIELD(pqname, BREAK), |
---|
| 133 | PF_RULE_FIELD(rt, BREAK), |
---|
| 134 | PF_RULE_FIELD(allow_opts, BREAK), |
---|
| 135 | PF_RULE_FIELD(rule_flag, BREAK), |
---|
| 136 | PF_RULE_FIELD(action, BREAK), |
---|
| 137 | PF_RULE_FIELD(log, BREAK), |
---|
| 138 | PF_RULE_FIELD(quick, BREAK), |
---|
| 139 | PF_RULE_FIELD(return_ttl, BREAK), |
---|
| 140 | PF_RULE_FIELD(overload_tblname, BREAK), |
---|
| 141 | PF_RULE_FIELD(flush, BREAK), |
---|
| 142 | PF_RULE_FIELD(rpool, BREAK), |
---|
| 143 | PF_RULE_FIELD(logif, BREAK), |
---|
| 144 | |
---|
| 145 | /* |
---|
| 146 | * Any fields not listed in this structure act as BREAK fields |
---|
| 147 | */ |
---|
| 148 | |
---|
| 149 | |
---|
| 150 | /* |
---|
| 151 | * These fields must not differ when we merge two rules together but |
---|
| 152 | * their difference isn't enough to put the rules in different superblocks. |
---|
| 153 | * There are no problems re-ordering any rules with these fields. |
---|
| 154 | */ |
---|
| 155 | PF_RULE_FIELD(af, NOMERGE), |
---|
| 156 | PF_RULE_FIELD(ifnot, NOMERGE), |
---|
| 157 | PF_RULE_FIELD(ifname, NOMERGE), /* hack for IF groups */ |
---|
| 158 | PF_RULE_FIELD(match_tag_not, NOMERGE), |
---|
| 159 | PF_RULE_FIELD(match_tagname, NOMERGE), |
---|
| 160 | PF_RULE_FIELD(os_fingerprint, NOMERGE), |
---|
| 161 | PF_RULE_FIELD(timeout, NOMERGE), |
---|
| 162 | PF_RULE_FIELD(return_icmp, NOMERGE), |
---|
| 163 | PF_RULE_FIELD(return_icmp6, NOMERGE), |
---|
| 164 | PF_RULE_FIELD(uid, NOMERGE), |
---|
| 165 | PF_RULE_FIELD(gid, NOMERGE), |
---|
| 166 | PF_RULE_FIELD(direction, NOMERGE), |
---|
| 167 | PF_RULE_FIELD(proto, NOMERGE), |
---|
| 168 | PF_RULE_FIELD(type, NOMERGE), |
---|
| 169 | PF_RULE_FIELD(code, NOMERGE), |
---|
| 170 | PF_RULE_FIELD(flags, NOMERGE), |
---|
| 171 | PF_RULE_FIELD(flagset, NOMERGE), |
---|
| 172 | PF_RULE_FIELD(tos, NOMERGE), |
---|
| 173 | PF_RULE_FIELD(src.port, NOMERGE), |
---|
| 174 | PF_RULE_FIELD(dst.port, NOMERGE), |
---|
| 175 | PF_RULE_FIELD(src.port_op, NOMERGE), |
---|
| 176 | PF_RULE_FIELD(dst.port_op, NOMERGE), |
---|
| 177 | PF_RULE_FIELD(src.neg, NOMERGE), |
---|
| 178 | PF_RULE_FIELD(dst.neg, NOMERGE), |
---|
| 179 | |
---|
| 180 | /* These fields can be merged */ |
---|
| 181 | PF_RULE_FIELD(src.addr, COMBINED), |
---|
| 182 | PF_RULE_FIELD(dst.addr, COMBINED), |
---|
| 183 | |
---|
| 184 | /* We just don't care about these fields. They're set by the kernel */ |
---|
| 185 | PF_RULE_FIELD(skip, DC), |
---|
| 186 | PF_RULE_FIELD(evaluations, DC), |
---|
| 187 | PF_RULE_FIELD(packets, DC), |
---|
| 188 | PF_RULE_FIELD(bytes, DC), |
---|
| 189 | PF_RULE_FIELD(kif, DC), |
---|
| 190 | PF_RULE_FIELD(states_cur, DC), |
---|
| 191 | PF_RULE_FIELD(states_tot, DC), |
---|
| 192 | PF_RULE_FIELD(src_nodes, DC), |
---|
| 193 | PF_RULE_FIELD(nr, DC), |
---|
| 194 | PF_RULE_FIELD(entries, DC), |
---|
| 195 | PF_RULE_FIELD(qid, DC), |
---|
| 196 | PF_RULE_FIELD(pqid, DC), |
---|
| 197 | PF_RULE_FIELD(anchor_relative, DC), |
---|
| 198 | PF_RULE_FIELD(anchor_wildcard, DC), |
---|
| 199 | PF_RULE_FIELD(tag, DC), |
---|
| 200 | PF_RULE_FIELD(match_tag, DC), |
---|
| 201 | PF_RULE_FIELD(overload_tbl, DC), |
---|
| 202 | |
---|
| 203 | /* These fields should never be set in a PASS/BLOCK rule */ |
---|
| 204 | PF_RULE_FIELD(natpass, NEVER), |
---|
| 205 | PF_RULE_FIELD(max_mss, NEVER), |
---|
| 206 | PF_RULE_FIELD(min_ttl, NEVER), |
---|
| 207 | PF_RULE_FIELD(set_tos, NEVER), |
---|
| 208 | }; |
---|
| 209 | |
---|
| 210 | |
---|
| 211 | |
---|
| 212 | int add_opt_table(struct pfctl *, struct pf_opt_tbl **, sa_family_t, |
---|
| 213 | struct pf_rule_addr *); |
---|
| 214 | int addrs_combineable(struct pf_rule_addr *, struct pf_rule_addr *); |
---|
| 215 | int addrs_equal(struct pf_rule_addr *, struct pf_rule_addr *); |
---|
| 216 | int block_feedback(struct pfctl *, struct superblock *); |
---|
| 217 | int combine_rules(struct pfctl *, struct superblock *); |
---|
| 218 | void comparable_rule(struct pf_rule *, const struct pf_rule *, int); |
---|
| 219 | int construct_superblocks(struct pfctl *, struct pf_opt_queue *, |
---|
| 220 | struct superblocks *); |
---|
| 221 | void exclude_supersets(struct pf_rule *, struct pf_rule *); |
---|
| 222 | int interface_group(const char *); |
---|
| 223 | int load_feedback_profile(struct pfctl *, struct superblocks *); |
---|
| 224 | int optimize_superblock(struct pfctl *, struct superblock *); |
---|
| 225 | int pf_opt_create_table(struct pfctl *, struct pf_opt_tbl *); |
---|
| 226 | void remove_from_skipsteps(struct skiplist *, struct superblock *, |
---|
| 227 | struct pf_opt_rule *, struct pf_skip_step *); |
---|
| 228 | int remove_identical_rules(struct pfctl *, struct superblock *); |
---|
| 229 | int reorder_rules(struct pfctl *, struct superblock *, int); |
---|
| 230 | int rules_combineable(struct pf_rule *, struct pf_rule *); |
---|
| 231 | void skip_append(struct superblock *, int, struct pf_skip_step *, |
---|
| 232 | struct pf_opt_rule *); |
---|
| 233 | int skip_compare(int, struct pf_skip_step *, struct pf_opt_rule *); |
---|
| 234 | void skip_init(void); |
---|
| 235 | int skip_cmp_af(struct pf_rule *, struct pf_rule *); |
---|
| 236 | int skip_cmp_dir(struct pf_rule *, struct pf_rule *); |
---|
| 237 | int skip_cmp_dst_addr(struct pf_rule *, struct pf_rule *); |
---|
| 238 | int skip_cmp_dst_port(struct pf_rule *, struct pf_rule *); |
---|
| 239 | int skip_cmp_ifp(struct pf_rule *, struct pf_rule *); |
---|
| 240 | int skip_cmp_proto(struct pf_rule *, struct pf_rule *); |
---|
| 241 | int skip_cmp_src_addr(struct pf_rule *, struct pf_rule *); |
---|
| 242 | int skip_cmp_src_port(struct pf_rule *, struct pf_rule *); |
---|
| 243 | int superblock_inclusive(struct superblock *, struct pf_opt_rule *); |
---|
| 244 | void superblock_free(struct pfctl *, struct superblock *); |
---|
| 245 | |
---|
| 246 | |
---|
| 247 | int (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, struct pf_rule *); |
---|
| 248 | const char *skip_comparitors_names[PF_SKIP_COUNT]; |
---|
| 249 | #define PF_SKIP_COMPARITORS { \ |
---|
| 250 | { "ifp", PF_SKIP_IFP, skip_cmp_ifp }, \ |
---|
| 251 | { "dir", PF_SKIP_DIR, skip_cmp_dir }, \ |
---|
| 252 | { "af", PF_SKIP_AF, skip_cmp_af }, \ |
---|
| 253 | { "proto", PF_SKIP_PROTO, skip_cmp_proto }, \ |
---|
| 254 | { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr }, \ |
---|
| 255 | { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port }, \ |
---|
| 256 | { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr }, \ |
---|
| 257 | { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port } \ |
---|
| 258 | } |
---|
| 259 | |
---|
| 260 | struct pfr_buffer table_buffer; |
---|
| 261 | int table_identifier; |
---|
| 262 | |
---|
| 263 | |
---|
| 264 | int |
---|
| 265 | pfctl_optimize_ruleset(struct pfctl *pf, struct pf_ruleset *rs) |
---|
| 266 | { |
---|
| 267 | struct superblocks superblocks; |
---|
| 268 | struct pf_opt_queue opt_queue; |
---|
| 269 | struct superblock *block; |
---|
| 270 | struct pf_opt_rule *por; |
---|
| 271 | struct pf_rule *r; |
---|
| 272 | struct pf_rulequeue *old_rules; |
---|
| 273 | |
---|
| 274 | DEBUG("optimizing ruleset"); |
---|
| 275 | memset(&table_buffer, 0, sizeof(table_buffer)); |
---|
| 276 | skip_init(); |
---|
| 277 | TAILQ_INIT(&opt_queue); |
---|
| 278 | |
---|
| 279 | old_rules = rs->rules[PF_RULESET_FILTER].active.ptr; |
---|
| 280 | rs->rules[PF_RULESET_FILTER].active.ptr = |
---|
| 281 | rs->rules[PF_RULESET_FILTER].inactive.ptr; |
---|
| 282 | rs->rules[PF_RULESET_FILTER].inactive.ptr = old_rules; |
---|
| 283 | |
---|
| 284 | /* |
---|
| 285 | * XXX expanding the pf_opt_rule format throughout pfctl might allow |
---|
| 286 | * us to avoid all this copying. |
---|
| 287 | */ |
---|
| 288 | while ((r = TAILQ_FIRST(rs->rules[PF_RULESET_FILTER].inactive.ptr)) |
---|
| 289 | != NULL) { |
---|
| 290 | TAILQ_REMOVE(rs->rules[PF_RULESET_FILTER].inactive.ptr, r, |
---|
| 291 | entries); |
---|
| 292 | if ((por = calloc(1, sizeof(*por))) == NULL) |
---|
| 293 | err(1, "calloc"); |
---|
| 294 | memcpy(&por->por_rule, r, sizeof(*r)); |
---|
| 295 | if (TAILQ_FIRST(&r->rpool.list) != NULL) { |
---|
| 296 | TAILQ_INIT(&por->por_rule.rpool.list); |
---|
| 297 | pfctl_move_pool(&r->rpool, &por->por_rule.rpool); |
---|
| 298 | } else |
---|
| 299 | bzero(&por->por_rule.rpool, |
---|
| 300 | sizeof(por->por_rule.rpool)); |
---|
| 301 | |
---|
| 302 | |
---|
| 303 | TAILQ_INSERT_TAIL(&opt_queue, por, por_entry); |
---|
| 304 | } |
---|
| 305 | |
---|
| 306 | TAILQ_INIT(&superblocks); |
---|
| 307 | if (construct_superblocks(pf, &opt_queue, &superblocks)) |
---|
| 308 | goto error; |
---|
| 309 | |
---|
| 310 | if (pf->optimize & PF_OPTIMIZE_PROFILE) { |
---|
| 311 | if (load_feedback_profile(pf, &superblocks)) |
---|
| 312 | goto error; |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | TAILQ_FOREACH(block, &superblocks, sb_entry) { |
---|
| 316 | if (optimize_superblock(pf, block)) |
---|
| 317 | goto error; |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | rs->anchor->refcnt = 0; |
---|
| 321 | while ((block = TAILQ_FIRST(&superblocks))) { |
---|
| 322 | TAILQ_REMOVE(&superblocks, block, sb_entry); |
---|
| 323 | |
---|
| 324 | while ((por = TAILQ_FIRST(&block->sb_rules))) { |
---|
| 325 | TAILQ_REMOVE(&block->sb_rules, por, por_entry); |
---|
| 326 | por->por_rule.nr = rs->anchor->refcnt++; |
---|
| 327 | if ((r = calloc(1, sizeof(*r))) == NULL) |
---|
| 328 | err(1, "calloc"); |
---|
| 329 | memcpy(r, &por->por_rule, sizeof(*r)); |
---|
| 330 | TAILQ_INIT(&r->rpool.list); |
---|
| 331 | pfctl_move_pool(&por->por_rule.rpool, &r->rpool); |
---|
| 332 | TAILQ_INSERT_TAIL( |
---|
| 333 | rs->rules[PF_RULESET_FILTER].active.ptr, |
---|
| 334 | r, entries); |
---|
| 335 | free(por); |
---|
| 336 | } |
---|
| 337 | free(block); |
---|
| 338 | } |
---|
| 339 | |
---|
| 340 | return (0); |
---|
| 341 | |
---|
| 342 | error: |
---|
| 343 | while ((por = TAILQ_FIRST(&opt_queue))) { |
---|
| 344 | TAILQ_REMOVE(&opt_queue, por, por_entry); |
---|
| 345 | if (por->por_src_tbl) { |
---|
| 346 | pfr_buf_clear(por->por_src_tbl->pt_buf); |
---|
| 347 | free(por->por_src_tbl->pt_buf); |
---|
| 348 | free(por->por_src_tbl); |
---|
| 349 | } |
---|
| 350 | if (por->por_dst_tbl) { |
---|
| 351 | pfr_buf_clear(por->por_dst_tbl->pt_buf); |
---|
| 352 | free(por->por_dst_tbl->pt_buf); |
---|
| 353 | free(por->por_dst_tbl); |
---|
| 354 | } |
---|
| 355 | free(por); |
---|
| 356 | } |
---|
| 357 | while ((block = TAILQ_FIRST(&superblocks))) { |
---|
| 358 | TAILQ_REMOVE(&superblocks, block, sb_entry); |
---|
| 359 | superblock_free(pf, block); |
---|
| 360 | } |
---|
| 361 | return (1); |
---|
| 362 | } |
---|
| 363 | |
---|
| 364 | |
---|
| 365 | /* |
---|
| 366 | * Go ahead and optimize a superblock |
---|
| 367 | */ |
---|
| 368 | int |
---|
| 369 | optimize_superblock(struct pfctl *pf, struct superblock *block) |
---|
| 370 | { |
---|
| 371 | #ifdef OPT_DEBUG |
---|
| 372 | struct pf_opt_rule *por; |
---|
| 373 | #endif /* OPT_DEBUG */ |
---|
| 374 | |
---|
| 375 | /* We have a few optimization passes: |
---|
| 376 | * 1) remove duplicate rules or rules that are a subset of other |
---|
| 377 | * rules |
---|
| 378 | * 2) combine otherwise identical rules with different IP addresses |
---|
| 379 | * into a single rule and put the addresses in a table. |
---|
| 380 | * 3) re-order the rules to improve kernel skip steps |
---|
| 381 | * 4) re-order the 'quick' rules based on feedback from the |
---|
| 382 | * active ruleset statistics |
---|
| 383 | * |
---|
| 384 | * XXX combine_rules() doesn't combine v4 and v6 rules. would just |
---|
| 385 | * have to keep af in the table container, make af 'COMBINE' and |
---|
| 386 | * twiddle the af on the merged rule |
---|
| 387 | * XXX maybe add a weighting to the metric on skipsteps when doing |
---|
| 388 | * reordering. sometimes two sequential tables will be better |
---|
| 389 | * that four consecutive interfaces. |
---|
| 390 | * XXX need to adjust the skipstep count of everything after PROTO, |
---|
| 391 | * since they aren't actually checked on a proto mismatch in |
---|
| 392 | * pf_test_{tcp, udp, icmp}() |
---|
| 393 | * XXX should i treat proto=0, af=0 or dir=0 special in skepstep |
---|
| 394 | * calculation since they are a DC? |
---|
| 395 | * XXX keep last skiplist of last superblock to influence this |
---|
| 396 | * superblock. '5 inet6 log' should make '3 inet6' come before '4 |
---|
| 397 | * inet' in the next superblock. |
---|
| 398 | * XXX would be useful to add tables for ports |
---|
| 399 | * XXX we can also re-order some mutually exclusive superblocks to |
---|
| 400 | * try merging superblocks before any of these optimization passes. |
---|
| 401 | * for instance a single 'log in' rule in the middle of non-logging |
---|
| 402 | * out rules. |
---|
| 403 | */ |
---|
| 404 | |
---|
| 405 | /* shortcut. there will be a lot of 1-rule superblocks */ |
---|
| 406 | if (!TAILQ_NEXT(TAILQ_FIRST(&block->sb_rules), por_entry)) |
---|
| 407 | return (0); |
---|
| 408 | |
---|
| 409 | #ifdef OPT_DEBUG |
---|
| 410 | printf("--- Superblock ---\n"); |
---|
| 411 | TAILQ_FOREACH(por, &block->sb_rules, por_entry) { |
---|
| 412 | printf(" "); |
---|
| 413 | print_rule(&por->por_rule, por->por_rule.anchor ? |
---|
| 414 | por->por_rule.anchor->name : "", 1, 0); |
---|
| 415 | } |
---|
| 416 | #endif /* OPT_DEBUG */ |
---|
| 417 | |
---|
| 418 | |
---|
| 419 | if (remove_identical_rules(pf, block)) |
---|
| 420 | return (1); |
---|
| 421 | if (combine_rules(pf, block)) |
---|
| 422 | return (1); |
---|
| 423 | if ((pf->optimize & PF_OPTIMIZE_PROFILE) && |
---|
| 424 | TAILQ_FIRST(&block->sb_rules)->por_rule.quick && |
---|
| 425 | block->sb_profiled_block) { |
---|
| 426 | if (block_feedback(pf, block)) |
---|
| 427 | return (1); |
---|
| 428 | } else if (reorder_rules(pf, block, 0)) { |
---|
| 429 | return (1); |
---|
| 430 | } |
---|
| 431 | |
---|
| 432 | /* |
---|
| 433 | * Don't add any optimization passes below reorder_rules(). It will |
---|
| 434 | * have divided superblocks into smaller blocks for further refinement |
---|
| 435 | * and doesn't put them back together again. What once was a true |
---|
| 436 | * superblock might have been split into multiple superblocks. |
---|
| 437 | */ |
---|
| 438 | |
---|
| 439 | #ifdef OPT_DEBUG |
---|
| 440 | printf("--- END Superblock ---\n"); |
---|
| 441 | #endif /* OPT_DEBUG */ |
---|
| 442 | return (0); |
---|
| 443 | } |
---|
| 444 | |
---|
| 445 | |
---|
| 446 | /* |
---|
| 447 | * Optimization pass #1: remove identical rules |
---|
| 448 | */ |
---|
| 449 | int |
---|
| 450 | remove_identical_rules(struct pfctl *pf, struct superblock *block) |
---|
| 451 | { |
---|
| 452 | struct pf_opt_rule *por1, *por2, *por_next, *por2_next; |
---|
| 453 | struct pf_rule a, a2, b, b2; |
---|
| 454 | |
---|
| 455 | for (por1 = TAILQ_FIRST(&block->sb_rules); por1; por1 = por_next) { |
---|
| 456 | por_next = TAILQ_NEXT(por1, por_entry); |
---|
| 457 | for (por2 = por_next; por2; por2 = por2_next) { |
---|
| 458 | por2_next = TAILQ_NEXT(por2, por_entry); |
---|
| 459 | comparable_rule(&a, &por1->por_rule, DC); |
---|
| 460 | comparable_rule(&b, &por2->por_rule, DC); |
---|
| 461 | memcpy(&a2, &a, sizeof(a2)); |
---|
| 462 | memcpy(&b2, &b, sizeof(b2)); |
---|
| 463 | |
---|
| 464 | exclude_supersets(&a, &b); |
---|
| 465 | exclude_supersets(&b2, &a2); |
---|
| 466 | if (memcmp(&a, &b, sizeof(a)) == 0) { |
---|
| 467 | DEBUG("removing identical rule nr%d = *nr%d*", |
---|
| 468 | por1->por_rule.nr, por2->por_rule.nr); |
---|
| 469 | TAILQ_REMOVE(&block->sb_rules, por2, por_entry); |
---|
| 470 | if (por_next == por2) |
---|
| 471 | por_next = TAILQ_NEXT(por1, por_entry); |
---|
| 472 | free(por2); |
---|
| 473 | } else if (memcmp(&a2, &b2, sizeof(a2)) == 0) { |
---|
| 474 | DEBUG("removing identical rule *nr%d* = nr%d", |
---|
| 475 | por1->por_rule.nr, por2->por_rule.nr); |
---|
| 476 | TAILQ_REMOVE(&block->sb_rules, por1, por_entry); |
---|
| 477 | free(por1); |
---|
| 478 | break; |
---|
| 479 | } |
---|
| 480 | } |
---|
| 481 | } |
---|
| 482 | |
---|
| 483 | return (0); |
---|
| 484 | } |
---|
| 485 | |
---|
| 486 | |
---|
| 487 | /* |
---|
| 488 | * Optimization pass #2: combine similar rules with different addresses |
---|
| 489 | * into a single rule and a table |
---|
| 490 | */ |
---|
| 491 | int |
---|
| 492 | combine_rules(struct pfctl *pf, struct superblock *block) |
---|
| 493 | { |
---|
| 494 | struct pf_opt_rule *p1, *p2, *por_next; |
---|
| 495 | int src_eq, dst_eq; |
---|
| 496 | |
---|
| 497 | if ((pf->loadopt & PFCTL_FLAG_TABLE) == 0) { |
---|
| 498 | warnx("Must enable table loading for optimizations"); |
---|
| 499 | return (1); |
---|
| 500 | } |
---|
| 501 | |
---|
| 502 | /* First we make a pass to combine the rules. O(n log n) */ |
---|
| 503 | TAILQ_FOREACH(p1, &block->sb_rules, por_entry) { |
---|
| 504 | for (p2 = TAILQ_NEXT(p1, por_entry); p2; p2 = por_next) { |
---|
| 505 | por_next = TAILQ_NEXT(p2, por_entry); |
---|
| 506 | |
---|
| 507 | src_eq = addrs_equal(&p1->por_rule.src, |
---|
| 508 | &p2->por_rule.src); |
---|
| 509 | dst_eq = addrs_equal(&p1->por_rule.dst, |
---|
| 510 | &p2->por_rule.dst); |
---|
| 511 | |
---|
| 512 | if (src_eq && !dst_eq && p1->por_src_tbl == NULL && |
---|
| 513 | p2->por_dst_tbl == NULL && |
---|
| 514 | p2->por_src_tbl == NULL && |
---|
| 515 | rules_combineable(&p1->por_rule, &p2->por_rule) && |
---|
| 516 | addrs_combineable(&p1->por_rule.dst, |
---|
| 517 | &p2->por_rule.dst)) { |
---|
| 518 | DEBUG("can combine rules nr%d = nr%d", |
---|
| 519 | p1->por_rule.nr, p2->por_rule.nr); |
---|
| 520 | if (p1->por_dst_tbl == NULL && |
---|
| 521 | add_opt_table(pf, &p1->por_dst_tbl, |
---|
| 522 | p1->por_rule.af, &p1->por_rule.dst)) |
---|
| 523 | return (1); |
---|
| 524 | if (add_opt_table(pf, &p1->por_dst_tbl, |
---|
| 525 | p1->por_rule.af, &p2->por_rule.dst)) |
---|
| 526 | return (1); |
---|
| 527 | p2->por_dst_tbl = p1->por_dst_tbl; |
---|
| 528 | if (p1->por_dst_tbl->pt_rulecount >= |
---|
| 529 | TABLE_THRESHOLD) { |
---|
| 530 | TAILQ_REMOVE(&block->sb_rules, p2, |
---|
| 531 | por_entry); |
---|
| 532 | free(p2); |
---|
| 533 | } |
---|
| 534 | } else if (!src_eq && dst_eq && p1->por_dst_tbl == NULL |
---|
| 535 | && p2->por_src_tbl == NULL && |
---|
| 536 | p2->por_dst_tbl == NULL && |
---|
| 537 | rules_combineable(&p1->por_rule, &p2->por_rule) && |
---|
| 538 | addrs_combineable(&p1->por_rule.src, |
---|
| 539 | &p2->por_rule.src)) { |
---|
| 540 | DEBUG("can combine rules nr%d = nr%d", |
---|
| 541 | p1->por_rule.nr, p2->por_rule.nr); |
---|
| 542 | if (p1->por_src_tbl == NULL && |
---|
| 543 | add_opt_table(pf, &p1->por_src_tbl, |
---|
| 544 | p1->por_rule.af, &p1->por_rule.src)) |
---|
| 545 | return (1); |
---|
| 546 | if (add_opt_table(pf, &p1->por_src_tbl, |
---|
| 547 | p1->por_rule.af, &p2->por_rule.src)) |
---|
| 548 | return (1); |
---|
| 549 | p2->por_src_tbl = p1->por_src_tbl; |
---|
| 550 | if (p1->por_src_tbl->pt_rulecount >= |
---|
| 551 | TABLE_THRESHOLD) { |
---|
| 552 | TAILQ_REMOVE(&block->sb_rules, p2, |
---|
| 553 | por_entry); |
---|
| 554 | free(p2); |
---|
| 555 | } |
---|
| 556 | } |
---|
| 557 | } |
---|
| 558 | } |
---|
| 559 | |
---|
| 560 | |
---|
| 561 | /* |
---|
| 562 | * Then we make a final pass to create a valid table name and |
---|
| 563 | * insert the name into the rules. |
---|
| 564 | */ |
---|
| 565 | for (p1 = TAILQ_FIRST(&block->sb_rules); p1; p1 = por_next) { |
---|
| 566 | por_next = TAILQ_NEXT(p1, por_entry); |
---|
| 567 | assert(p1->por_src_tbl == NULL || p1->por_dst_tbl == NULL); |
---|
| 568 | |
---|
| 569 | if (p1->por_src_tbl && p1->por_src_tbl->pt_rulecount >= |
---|
| 570 | TABLE_THRESHOLD) { |
---|
| 571 | if (p1->por_src_tbl->pt_generated) { |
---|
| 572 | /* This rule is included in a table */ |
---|
| 573 | TAILQ_REMOVE(&block->sb_rules, p1, por_entry); |
---|
| 574 | free(p1); |
---|
| 575 | continue; |
---|
| 576 | } |
---|
| 577 | p1->por_src_tbl->pt_generated = 1; |
---|
| 578 | |
---|
| 579 | if ((pf->opts & PF_OPT_NOACTION) == 0 && |
---|
| 580 | pf_opt_create_table(pf, p1->por_src_tbl)) |
---|
| 581 | return (1); |
---|
| 582 | |
---|
| 583 | pf->tdirty = 1; |
---|
| 584 | |
---|
| 585 | if (pf->opts & PF_OPT_VERBOSE) |
---|
| 586 | print_tabledef(p1->por_src_tbl->pt_name, |
---|
| 587 | PFR_TFLAG_CONST, 1, |
---|
| 588 | &p1->por_src_tbl->pt_nodes); |
---|
| 589 | |
---|
| 590 | memset(&p1->por_rule.src.addr, 0, |
---|
| 591 | sizeof(p1->por_rule.src.addr)); |
---|
| 592 | p1->por_rule.src.addr.type = PF_ADDR_TABLE; |
---|
| 593 | strlcpy(p1->por_rule.src.addr.v.tblname, |
---|
| 594 | p1->por_src_tbl->pt_name, |
---|
| 595 | sizeof(p1->por_rule.src.addr.v.tblname)); |
---|
| 596 | |
---|
| 597 | pfr_buf_clear(p1->por_src_tbl->pt_buf); |
---|
| 598 | free(p1->por_src_tbl->pt_buf); |
---|
| 599 | p1->por_src_tbl->pt_buf = NULL; |
---|
| 600 | } |
---|
| 601 | if (p1->por_dst_tbl && p1->por_dst_tbl->pt_rulecount >= |
---|
| 602 | TABLE_THRESHOLD) { |
---|
| 603 | if (p1->por_dst_tbl->pt_generated) { |
---|
| 604 | /* This rule is included in a table */ |
---|
| 605 | TAILQ_REMOVE(&block->sb_rules, p1, por_entry); |
---|
| 606 | free(p1); |
---|
| 607 | continue; |
---|
| 608 | } |
---|
| 609 | p1->por_dst_tbl->pt_generated = 1; |
---|
| 610 | |
---|
| 611 | if ((pf->opts & PF_OPT_NOACTION) == 0 && |
---|
| 612 | pf_opt_create_table(pf, p1->por_dst_tbl)) |
---|
| 613 | return (1); |
---|
| 614 | pf->tdirty = 1; |
---|
| 615 | |
---|
| 616 | if (pf->opts & PF_OPT_VERBOSE) |
---|
| 617 | print_tabledef(p1->por_dst_tbl->pt_name, |
---|
| 618 | PFR_TFLAG_CONST, 1, |
---|
| 619 | &p1->por_dst_tbl->pt_nodes); |
---|
| 620 | |
---|
| 621 | memset(&p1->por_rule.dst.addr, 0, |
---|
| 622 | sizeof(p1->por_rule.dst.addr)); |
---|
| 623 | p1->por_rule.dst.addr.type = PF_ADDR_TABLE; |
---|
| 624 | strlcpy(p1->por_rule.dst.addr.v.tblname, |
---|
| 625 | p1->por_dst_tbl->pt_name, |
---|
| 626 | sizeof(p1->por_rule.dst.addr.v.tblname)); |
---|
| 627 | |
---|
| 628 | pfr_buf_clear(p1->por_dst_tbl->pt_buf); |
---|
| 629 | free(p1->por_dst_tbl->pt_buf); |
---|
| 630 | p1->por_dst_tbl->pt_buf = NULL; |
---|
| 631 | } |
---|
| 632 | } |
---|
| 633 | |
---|
| 634 | return (0); |
---|
| 635 | } |
---|
| 636 | |
---|
| 637 | |
---|
| 638 | /* |
---|
| 639 | * Optimization pass #3: re-order rules to improve skip steps |
---|
| 640 | */ |
---|
| 641 | int |
---|
| 642 | reorder_rules(struct pfctl *pf, struct superblock *block, int depth) |
---|
| 643 | { |
---|
| 644 | struct superblock *newblock; |
---|
| 645 | struct pf_skip_step *skiplist; |
---|
| 646 | struct pf_opt_rule *por; |
---|
| 647 | int i, largest, largest_list, rule_count = 0; |
---|
| 648 | TAILQ_HEAD( , pf_opt_rule) head; |
---|
| 649 | |
---|
| 650 | /* |
---|
| 651 | * Calculate the best-case skip steps. We put each rule in a list |
---|
| 652 | * of other rules with common fields |
---|
| 653 | */ |
---|
| 654 | for (i = 0; i < PF_SKIP_COUNT; i++) { |
---|
| 655 | TAILQ_FOREACH(por, &block->sb_rules, por_entry) { |
---|
| 656 | TAILQ_FOREACH(skiplist, &block->sb_skipsteps[i], |
---|
| 657 | ps_entry) { |
---|
| 658 | if (skip_compare(i, skiplist, por) == 0) |
---|
| 659 | break; |
---|
| 660 | } |
---|
| 661 | if (skiplist == NULL) { |
---|
| 662 | if ((skiplist = calloc(1, sizeof(*skiplist))) == |
---|
| 663 | NULL) |
---|
| 664 | err(1, "calloc"); |
---|
| 665 | TAILQ_INIT(&skiplist->ps_rules); |
---|
| 666 | TAILQ_INSERT_TAIL(&block->sb_skipsteps[i], |
---|
| 667 | skiplist, ps_entry); |
---|
| 668 | } |
---|
| 669 | skip_append(block, i, skiplist, por); |
---|
| 670 | } |
---|
| 671 | } |
---|
| 672 | |
---|
| 673 | TAILQ_FOREACH(por, &block->sb_rules, por_entry) |
---|
| 674 | rule_count++; |
---|
| 675 | |
---|
| 676 | /* |
---|
| 677 | * Now we're going to ignore any fields that are identical between |
---|
| 678 | * all of the rules in the superblock and those fields which differ |
---|
| 679 | * between every rule in the superblock. |
---|
| 680 | */ |
---|
| 681 | largest = 0; |
---|
| 682 | for (i = 0; i < PF_SKIP_COUNT; i++) { |
---|
| 683 | skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); |
---|
| 684 | if (skiplist->ps_count == rule_count) { |
---|
| 685 | DEBUG("(%d) original skipstep '%s' is all rules", |
---|
| 686 | depth, skip_comparitors_names[i]); |
---|
| 687 | skiplist->ps_count = 0; |
---|
| 688 | } else if (skiplist->ps_count == 1) { |
---|
| 689 | skiplist->ps_count = 0; |
---|
| 690 | } else { |
---|
| 691 | DEBUG("(%d) original skipstep '%s' largest jump is %d", |
---|
| 692 | depth, skip_comparitors_names[i], |
---|
| 693 | skiplist->ps_count); |
---|
| 694 | if (skiplist->ps_count > largest) |
---|
| 695 | largest = skiplist->ps_count; |
---|
| 696 | } |
---|
| 697 | } |
---|
| 698 | if (largest == 0) { |
---|
| 699 | /* Ugh. There is NO commonality in the superblock on which |
---|
| 700 | * optimize the skipsteps optimization. |
---|
| 701 | */ |
---|
| 702 | goto done; |
---|
| 703 | } |
---|
| 704 | |
---|
| 705 | /* |
---|
| 706 | * Now we're going to empty the superblock rule list and re-create |
---|
| 707 | * it based on a more optimal skipstep order. |
---|
| 708 | */ |
---|
| 709 | TAILQ_INIT(&head); |
---|
| 710 | while ((por = TAILQ_FIRST(&block->sb_rules))) { |
---|
| 711 | TAILQ_REMOVE(&block->sb_rules, por, por_entry); |
---|
| 712 | TAILQ_INSERT_TAIL(&head, por, por_entry); |
---|
| 713 | } |
---|
| 714 | |
---|
| 715 | |
---|
| 716 | while (!TAILQ_EMPTY(&head)) { |
---|
| 717 | largest = 1; |
---|
| 718 | |
---|
| 719 | /* |
---|
| 720 | * Find the most useful skip steps remaining |
---|
| 721 | */ |
---|
| 722 | for (i = 0; i < PF_SKIP_COUNT; i++) { |
---|
| 723 | skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]); |
---|
| 724 | if (skiplist->ps_count > largest) { |
---|
| 725 | largest = skiplist->ps_count; |
---|
| 726 | largest_list = i; |
---|
| 727 | } |
---|
| 728 | } |
---|
| 729 | |
---|
| 730 | if (largest <= 1) { |
---|
| 731 | /* |
---|
| 732 | * Nothing useful left. Leave remaining rules in order. |
---|
| 733 | */ |
---|
| 734 | DEBUG("(%d) no more commonality for skip steps", depth); |
---|
| 735 | while ((por = TAILQ_FIRST(&head))) { |
---|
| 736 | TAILQ_REMOVE(&head, por, por_entry); |
---|
| 737 | TAILQ_INSERT_TAIL(&block->sb_rules, por, |
---|
| 738 | por_entry); |
---|
| 739 | } |
---|
| 740 | } else { |
---|
| 741 | /* |
---|
| 742 | * There is commonality. Extract those common rules |
---|
| 743 | * and place them in the ruleset adjacent to each |
---|
| 744 | * other. |
---|
| 745 | */ |
---|
| 746 | skiplist = TAILQ_FIRST(&block->sb_skipsteps[ |
---|
| 747 | largest_list]); |
---|
| 748 | DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d", |
---|
| 749 | depth, skip_comparitors_names[largest_list], |
---|
| 750 | largest, TAILQ_FIRST(&TAILQ_FIRST(&block-> |
---|
| 751 | sb_skipsteps [largest_list])->ps_rules)-> |
---|
| 752 | por_rule.nr); |
---|
| 753 | TAILQ_REMOVE(&block->sb_skipsteps[largest_list], |
---|
| 754 | skiplist, ps_entry); |
---|
| 755 | |
---|
| 756 | |
---|
| 757 | /* |
---|
| 758 | * There may be further commonality inside these |
---|
| 759 | * rules. So we'll split them off into they're own |
---|
| 760 | * superblock and pass it back into the optimizer. |
---|
| 761 | */ |
---|
| 762 | if (skiplist->ps_count > 2) { |
---|
| 763 | if ((newblock = calloc(1, sizeof(*newblock))) |
---|
| 764 | == NULL) { |
---|
| 765 | warn("calloc"); |
---|
| 766 | return (1); |
---|
| 767 | } |
---|
| 768 | TAILQ_INIT(&newblock->sb_rules); |
---|
| 769 | for (i = 0; i < PF_SKIP_COUNT; i++) |
---|
| 770 | TAILQ_INIT(&newblock->sb_skipsteps[i]); |
---|
| 771 | TAILQ_INSERT_BEFORE(block, newblock, sb_entry); |
---|
| 772 | DEBUG("(%d) splitting off %d rules from superblock @ #%d", |
---|
| 773 | depth, skiplist->ps_count, |
---|
| 774 | TAILQ_FIRST(&skiplist->ps_rules)-> |
---|
| 775 | por_rule.nr); |
---|
| 776 | } else { |
---|
| 777 | newblock = block; |
---|
| 778 | } |
---|
| 779 | |
---|
| 780 | while ((por = TAILQ_FIRST(&skiplist->ps_rules))) { |
---|
| 781 | TAILQ_REMOVE(&head, por, por_entry); |
---|
| 782 | TAILQ_REMOVE(&skiplist->ps_rules, por, |
---|
| 783 | por_skip_entry[largest_list]); |
---|
| 784 | TAILQ_INSERT_TAIL(&newblock->sb_rules, por, |
---|
| 785 | por_entry); |
---|
| 786 | |
---|
| 787 | /* Remove this rule from all other skiplists */ |
---|
| 788 | remove_from_skipsteps(&block->sb_skipsteps[ |
---|
| 789 | largest_list], block, por, skiplist); |
---|
| 790 | } |
---|
| 791 | free(skiplist); |
---|
| 792 | if (newblock != block) |
---|
| 793 | if (reorder_rules(pf, newblock, depth + 1)) |
---|
| 794 | return (1); |
---|
| 795 | } |
---|
| 796 | } |
---|
| 797 | |
---|
| 798 | done: |
---|
| 799 | for (i = 0; i < PF_SKIP_COUNT; i++) { |
---|
| 800 | while ((skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]))) { |
---|
| 801 | TAILQ_REMOVE(&block->sb_skipsteps[i], skiplist, |
---|
| 802 | ps_entry); |
---|
| 803 | free(skiplist); |
---|
| 804 | } |
---|
| 805 | } |
---|
| 806 | |
---|
| 807 | return (0); |
---|
| 808 | } |
---|
| 809 | |
---|
| 810 | |
---|
| 811 | /* |
---|
| 812 | * Optimization pass #4: re-order 'quick' rules based on feedback from the |
---|
| 813 | * currently running ruleset |
---|
| 814 | */ |
---|
| 815 | int |
---|
| 816 | block_feedback(struct pfctl *pf, struct superblock *block) |
---|
| 817 | { |
---|
| 818 | TAILQ_HEAD( , pf_opt_rule) queue; |
---|
| 819 | struct pf_opt_rule *por1, *por2; |
---|
| 820 | u_int64_t total_count = 0; |
---|
| 821 | struct pf_rule a, b; |
---|
| 822 | |
---|
| 823 | |
---|
| 824 | /* |
---|
| 825 | * Walk through all of the profiled superblock's rules and copy |
---|
| 826 | * the counters onto our rules. |
---|
| 827 | */ |
---|
| 828 | TAILQ_FOREACH(por1, &block->sb_profiled_block->sb_rules, por_entry) { |
---|
| 829 | comparable_rule(&a, &por1->por_rule, DC); |
---|
| 830 | total_count += por1->por_rule.packets[0] + |
---|
| 831 | por1->por_rule.packets[1]; |
---|
| 832 | TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { |
---|
| 833 | if (por2->por_profile_count) |
---|
| 834 | continue; |
---|
| 835 | comparable_rule(&b, &por2->por_rule, DC); |
---|
| 836 | if (memcmp(&a, &b, sizeof(a)) == 0) { |
---|
| 837 | por2->por_profile_count = |
---|
| 838 | por1->por_rule.packets[0] + |
---|
| 839 | por1->por_rule.packets[1]; |
---|
| 840 | break; |
---|
| 841 | } |
---|
| 842 | } |
---|
| 843 | } |
---|
| 844 | superblock_free(pf, block->sb_profiled_block); |
---|
| 845 | block->sb_profiled_block = NULL; |
---|
| 846 | |
---|
| 847 | /* |
---|
| 848 | * Now we pull all of the rules off the superblock and re-insert them |
---|
| 849 | * in sorted order. |
---|
| 850 | */ |
---|
| 851 | |
---|
| 852 | TAILQ_INIT(&queue); |
---|
| 853 | while ((por1 = TAILQ_FIRST(&block->sb_rules)) != NULL) { |
---|
| 854 | TAILQ_REMOVE(&block->sb_rules, por1, por_entry); |
---|
| 855 | TAILQ_INSERT_TAIL(&queue, por1, por_entry); |
---|
| 856 | } |
---|
| 857 | |
---|
| 858 | while ((por1 = TAILQ_FIRST(&queue)) != NULL) { |
---|
| 859 | TAILQ_REMOVE(&queue, por1, por_entry); |
---|
| 860 | /* XXX I should sort all of the unused rules based on skip steps */ |
---|
| 861 | TAILQ_FOREACH(por2, &block->sb_rules, por_entry) { |
---|
| 862 | if (por1->por_profile_count > por2->por_profile_count) { |
---|
| 863 | TAILQ_INSERT_BEFORE(por2, por1, por_entry); |
---|
| 864 | break; |
---|
| 865 | } |
---|
| 866 | } |
---|
| 867 | #ifdef __FreeBSD__ |
---|
| 868 | if (por2 == NULL) |
---|
| 869 | #else |
---|
| 870 | if (por2 == TAILQ_END(&block->sb_rules)) |
---|
| 871 | #endif |
---|
| 872 | TAILQ_INSERT_TAIL(&block->sb_rules, por1, por_entry); |
---|
| 873 | } |
---|
| 874 | |
---|
| 875 | return (0); |
---|
| 876 | } |
---|
| 877 | |
---|
| 878 | |
---|
| 879 | /* |
---|
| 880 | * Load the current ruleset from the kernel and try to associate them with |
---|
| 881 | * the ruleset we're optimizing. |
---|
| 882 | */ |
---|
| 883 | int |
---|
| 884 | load_feedback_profile(struct pfctl *pf, struct superblocks *superblocks) |
---|
| 885 | { |
---|
| 886 | struct superblock *block, *blockcur; |
---|
| 887 | struct superblocks prof_superblocks; |
---|
| 888 | struct pf_opt_rule *por; |
---|
| 889 | struct pf_opt_queue queue; |
---|
| 890 | struct pfioc_rule pr; |
---|
| 891 | struct pf_rule a, b; |
---|
| 892 | int nr, mnr; |
---|
| 893 | |
---|
| 894 | TAILQ_INIT(&queue); |
---|
| 895 | TAILQ_INIT(&prof_superblocks); |
---|
| 896 | |
---|
| 897 | memset(&pr, 0, sizeof(pr)); |
---|
| 898 | pr.rule.action = PF_PASS; |
---|
| 899 | if (ioctl(pf->dev, DIOCGETRULES, &pr)) { |
---|
| 900 | warn("DIOCGETRULES"); |
---|
| 901 | return (1); |
---|
| 902 | } |
---|
| 903 | mnr = pr.nr; |
---|
| 904 | |
---|
| 905 | DEBUG("Loading %d active rules for a feedback profile", mnr); |
---|
| 906 | for (nr = 0; nr < mnr; ++nr) { |
---|
| 907 | struct pf_ruleset *rs; |
---|
| 908 | if ((por = calloc(1, sizeof(*por))) == NULL) { |
---|
| 909 | warn("calloc"); |
---|
| 910 | return (1); |
---|
| 911 | } |
---|
| 912 | pr.nr = nr; |
---|
| 913 | if (ioctl(pf->dev, DIOCGETRULE, &pr)) { |
---|
| 914 | warn("DIOCGETRULES"); |
---|
| 915 | return (1); |
---|
| 916 | } |
---|
| 917 | memcpy(&por->por_rule, &pr.rule, sizeof(por->por_rule)); |
---|
| 918 | rs = pf_find_or_create_ruleset(pr.anchor_call); |
---|
| 919 | por->por_rule.anchor = rs->anchor; |
---|
| 920 | if (TAILQ_EMPTY(&por->por_rule.rpool.list)) |
---|
| 921 | memset(&por->por_rule.rpool, 0, |
---|
| 922 | sizeof(por->por_rule.rpool)); |
---|
| 923 | TAILQ_INSERT_TAIL(&queue, por, por_entry); |
---|
| 924 | |
---|
| 925 | /* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket, |
---|
| 926 | * PF_PASS, pf->anchor) ??? |
---|
| 927 | * ... pfctl_clear_pool(&pr.rule.rpool) |
---|
| 928 | */ |
---|
| 929 | } |
---|
| 930 | |
---|
| 931 | if (construct_superblocks(pf, &queue, &prof_superblocks)) |
---|
| 932 | return (1); |
---|
| 933 | |
---|
| 934 | |
---|
| 935 | /* |
---|
| 936 | * Now we try to associate the active ruleset's superblocks with |
---|
| 937 | * the superblocks we're compiling. |
---|
| 938 | */ |
---|
| 939 | block = TAILQ_FIRST(superblocks); |
---|
| 940 | blockcur = TAILQ_FIRST(&prof_superblocks); |
---|
| 941 | while (block && blockcur) { |
---|
| 942 | comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, |
---|
| 943 | BREAK); |
---|
| 944 | comparable_rule(&b, &TAILQ_FIRST(&blockcur->sb_rules)->por_rule, |
---|
| 945 | BREAK); |
---|
| 946 | if (memcmp(&a, &b, sizeof(a)) == 0) { |
---|
| 947 | /* The two superblocks lined up */ |
---|
| 948 | block->sb_profiled_block = blockcur; |
---|
| 949 | } else { |
---|
| 950 | DEBUG("superblocks don't line up between #%d and #%d", |
---|
| 951 | TAILQ_FIRST(&block->sb_rules)->por_rule.nr, |
---|
| 952 | TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr); |
---|
| 953 | break; |
---|
| 954 | } |
---|
| 955 | block = TAILQ_NEXT(block, sb_entry); |
---|
| 956 | blockcur = TAILQ_NEXT(blockcur, sb_entry); |
---|
| 957 | } |
---|
| 958 | |
---|
| 959 | |
---|
| 960 | |
---|
| 961 | /* Free any superblocks we couldn't link */ |
---|
| 962 | while (blockcur) { |
---|
| 963 | block = TAILQ_NEXT(blockcur, sb_entry); |
---|
| 964 | superblock_free(pf, blockcur); |
---|
| 965 | blockcur = block; |
---|
| 966 | } |
---|
| 967 | return (0); |
---|
| 968 | } |
---|
| 969 | |
---|
| 970 | |
---|
| 971 | /* |
---|
| 972 | * Compare a rule to a skiplist to see if the rule is a member |
---|
| 973 | */ |
---|
| 974 | int |
---|
| 975 | skip_compare(int skipnum, struct pf_skip_step *skiplist, |
---|
| 976 | struct pf_opt_rule *por) |
---|
| 977 | { |
---|
| 978 | struct pf_rule *a, *b; |
---|
| 979 | if (skipnum >= PF_SKIP_COUNT || skipnum < 0) |
---|
| 980 | errx(1, "skip_compare() out of bounds"); |
---|
| 981 | a = &por->por_rule; |
---|
| 982 | b = &TAILQ_FIRST(&skiplist->ps_rules)->por_rule; |
---|
| 983 | |
---|
| 984 | return ((skip_comparitors[skipnum])(a, b)); |
---|
| 985 | } |
---|
| 986 | |
---|
| 987 | |
---|
| 988 | /* |
---|
| 989 | * Add a rule to a skiplist |
---|
| 990 | */ |
---|
| 991 | void |
---|
| 992 | skip_append(struct superblock *superblock, int skipnum, |
---|
| 993 | struct pf_skip_step *skiplist, struct pf_opt_rule *por) |
---|
| 994 | { |
---|
| 995 | struct pf_skip_step *prev; |
---|
| 996 | |
---|
| 997 | skiplist->ps_count++; |
---|
| 998 | TAILQ_INSERT_TAIL(&skiplist->ps_rules, por, por_skip_entry[skipnum]); |
---|
| 999 | |
---|
| 1000 | /* Keep the list of skiplists sorted by whichever is larger */ |
---|
| 1001 | while ((prev = TAILQ_PREV(skiplist, skiplist, ps_entry)) && |
---|
| 1002 | prev->ps_count < skiplist->ps_count) { |
---|
| 1003 | TAILQ_REMOVE(&superblock->sb_skipsteps[skipnum], |
---|
| 1004 | skiplist, ps_entry); |
---|
| 1005 | TAILQ_INSERT_BEFORE(prev, skiplist, ps_entry); |
---|
| 1006 | } |
---|
| 1007 | } |
---|
| 1008 | |
---|
| 1009 | |
---|
| 1010 | /* |
---|
| 1011 | * Remove a rule from the other skiplist calculations. |
---|
| 1012 | */ |
---|
| 1013 | void |
---|
| 1014 | remove_from_skipsteps(struct skiplist *head, struct superblock *block, |
---|
| 1015 | struct pf_opt_rule *por, struct pf_skip_step *active_list) |
---|
| 1016 | { |
---|
| 1017 | struct pf_skip_step *sk, *next; |
---|
| 1018 | struct pf_opt_rule *p2; |
---|
| 1019 | int i, found; |
---|
| 1020 | |
---|
| 1021 | for (i = 0; i < PF_SKIP_COUNT; i++) { |
---|
| 1022 | sk = TAILQ_FIRST(&block->sb_skipsteps[i]); |
---|
| 1023 | if (sk == NULL || sk == active_list || sk->ps_count <= 1) |
---|
| 1024 | continue; |
---|
| 1025 | found = 0; |
---|
| 1026 | do { |
---|
| 1027 | TAILQ_FOREACH(p2, &sk->ps_rules, por_skip_entry[i]) |
---|
| 1028 | if (p2 == por) { |
---|
| 1029 | TAILQ_REMOVE(&sk->ps_rules, p2, |
---|
| 1030 | por_skip_entry[i]); |
---|
| 1031 | found = 1; |
---|
| 1032 | sk->ps_count--; |
---|
| 1033 | break; |
---|
| 1034 | } |
---|
| 1035 | } while (!found && (sk = TAILQ_NEXT(sk, ps_entry))); |
---|
| 1036 | if (found && sk) { |
---|
| 1037 | /* Does this change the sorting order? */ |
---|
| 1038 | while ((next = TAILQ_NEXT(sk, ps_entry)) && |
---|
| 1039 | next->ps_count > sk->ps_count) { |
---|
| 1040 | TAILQ_REMOVE(head, sk, ps_entry); |
---|
| 1041 | TAILQ_INSERT_AFTER(head, next, sk, ps_entry); |
---|
| 1042 | } |
---|
| 1043 | #ifdef OPT_DEBUG |
---|
| 1044 | next = TAILQ_NEXT(sk, ps_entry); |
---|
| 1045 | assert(next == NULL || next->ps_count <= sk->ps_count); |
---|
| 1046 | #endif /* OPT_DEBUG */ |
---|
| 1047 | } |
---|
| 1048 | } |
---|
| 1049 | } |
---|
| 1050 | |
---|
| 1051 | |
---|
| 1052 | /* Compare two rules AF field for skiplist construction */ |
---|
| 1053 | int |
---|
| 1054 | skip_cmp_af(struct pf_rule *a, struct pf_rule *b) |
---|
| 1055 | { |
---|
| 1056 | if (a->af != b->af || a->af == 0) |
---|
| 1057 | return (1); |
---|
| 1058 | return (0); |
---|
| 1059 | } |
---|
| 1060 | |
---|
| 1061 | /* Compare two rules DIRECTION field for skiplist construction */ |
---|
| 1062 | int |
---|
| 1063 | skip_cmp_dir(struct pf_rule *a, struct pf_rule *b) |
---|
| 1064 | { |
---|
| 1065 | if (a->direction == 0 || a->direction != b->direction) |
---|
| 1066 | return (1); |
---|
| 1067 | return (0); |
---|
| 1068 | } |
---|
| 1069 | |
---|
| 1070 | /* Compare two rules DST Address field for skiplist construction */ |
---|
| 1071 | int |
---|
| 1072 | skip_cmp_dst_addr(struct pf_rule *a, struct pf_rule *b) |
---|
| 1073 | { |
---|
| 1074 | if (a->dst.neg != b->dst.neg || |
---|
| 1075 | a->dst.addr.type != b->dst.addr.type) |
---|
| 1076 | return (1); |
---|
| 1077 | /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 |
---|
| 1078 | * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || |
---|
| 1079 | * a->proto == IPPROTO_ICMP |
---|
| 1080 | * return (1); |
---|
| 1081 | */ |
---|
| 1082 | switch (a->dst.addr.type) { |
---|
| 1083 | case PF_ADDR_ADDRMASK: |
---|
| 1084 | if (memcmp(&a->dst.addr.v.a.addr, &b->dst.addr.v.a.addr, |
---|
| 1085 | sizeof(a->dst.addr.v.a.addr)) || |
---|
| 1086 | memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, |
---|
| 1087 | sizeof(a->dst.addr.v.a.mask)) || |
---|
| 1088 | (a->dst.addr.v.a.addr.addr32[0] == 0 && |
---|
| 1089 | a->dst.addr.v.a.addr.addr32[1] == 0 && |
---|
| 1090 | a->dst.addr.v.a.addr.addr32[2] == 0 && |
---|
| 1091 | a->dst.addr.v.a.addr.addr32[3] == 0)) |
---|
| 1092 | return (1); |
---|
| 1093 | return (0); |
---|
| 1094 | case PF_ADDR_DYNIFTL: |
---|
| 1095 | if (strcmp(a->dst.addr.v.ifname, b->dst.addr.v.ifname) != 0 || |
---|
| 1096 | a->dst.addr.iflags != a->dst.addr.iflags || |
---|
| 1097 | memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask, |
---|
| 1098 | sizeof(a->dst.addr.v.a.mask))) |
---|
| 1099 | return (1); |
---|
| 1100 | return (0); |
---|
| 1101 | case PF_ADDR_NOROUTE: |
---|
| 1102 | case PF_ADDR_URPFFAILED: |
---|
| 1103 | return (0); |
---|
| 1104 | case PF_ADDR_TABLE: |
---|
| 1105 | return (strcmp(a->dst.addr.v.tblname, b->dst.addr.v.tblname)); |
---|
| 1106 | } |
---|
| 1107 | return (1); |
---|
| 1108 | } |
---|
| 1109 | |
---|
| 1110 | /* Compare two rules DST port field for skiplist construction */ |
---|
| 1111 | int |
---|
| 1112 | skip_cmp_dst_port(struct pf_rule *a, struct pf_rule *b) |
---|
| 1113 | { |
---|
| 1114 | /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 |
---|
| 1115 | * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || |
---|
| 1116 | * a->proto == IPPROTO_ICMP |
---|
| 1117 | * return (1); |
---|
| 1118 | */ |
---|
| 1119 | if (a->dst.port_op == PF_OP_NONE || a->dst.port_op != b->dst.port_op || |
---|
| 1120 | a->dst.port[0] != b->dst.port[0] || |
---|
| 1121 | a->dst.port[1] != b->dst.port[1]) |
---|
| 1122 | return (1); |
---|
| 1123 | return (0); |
---|
| 1124 | } |
---|
| 1125 | |
---|
| 1126 | /* Compare two rules IFP field for skiplist construction */ |
---|
| 1127 | int |
---|
| 1128 | skip_cmp_ifp(struct pf_rule *a, struct pf_rule *b) |
---|
| 1129 | { |
---|
| 1130 | if (strcmp(a->ifname, b->ifname) || a->ifname[0] == '\0') |
---|
| 1131 | return (1); |
---|
| 1132 | return (a->ifnot != b->ifnot); |
---|
| 1133 | } |
---|
| 1134 | |
---|
| 1135 | /* Compare two rules PROTO field for skiplist construction */ |
---|
| 1136 | int |
---|
| 1137 | skip_cmp_proto(struct pf_rule *a, struct pf_rule *b) |
---|
| 1138 | { |
---|
| 1139 | return (a->proto != b->proto || a->proto == 0); |
---|
| 1140 | } |
---|
| 1141 | |
---|
| 1142 | /* Compare two rules SRC addr field for skiplist construction */ |
---|
| 1143 | int |
---|
| 1144 | skip_cmp_src_addr(struct pf_rule *a, struct pf_rule *b) |
---|
| 1145 | { |
---|
| 1146 | if (a->src.neg != b->src.neg || |
---|
| 1147 | a->src.addr.type != b->src.addr.type) |
---|
| 1148 | return (1); |
---|
| 1149 | /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 |
---|
| 1150 | * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || |
---|
| 1151 | * a->proto == IPPROTO_ICMP |
---|
| 1152 | * return (1); |
---|
| 1153 | */ |
---|
| 1154 | switch (a->src.addr.type) { |
---|
| 1155 | case PF_ADDR_ADDRMASK: |
---|
| 1156 | if (memcmp(&a->src.addr.v.a.addr, &b->src.addr.v.a.addr, |
---|
| 1157 | sizeof(a->src.addr.v.a.addr)) || |
---|
| 1158 | memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, |
---|
| 1159 | sizeof(a->src.addr.v.a.mask)) || |
---|
| 1160 | (a->src.addr.v.a.addr.addr32[0] == 0 && |
---|
| 1161 | a->src.addr.v.a.addr.addr32[1] == 0 && |
---|
| 1162 | a->src.addr.v.a.addr.addr32[2] == 0 && |
---|
| 1163 | a->src.addr.v.a.addr.addr32[3] == 0)) |
---|
| 1164 | return (1); |
---|
| 1165 | return (0); |
---|
| 1166 | case PF_ADDR_DYNIFTL: |
---|
| 1167 | if (strcmp(a->src.addr.v.ifname, b->src.addr.v.ifname) != 0 || |
---|
| 1168 | a->src.addr.iflags != a->src.addr.iflags || |
---|
| 1169 | memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask, |
---|
| 1170 | sizeof(a->src.addr.v.a.mask))) |
---|
| 1171 | return (1); |
---|
| 1172 | return (0); |
---|
| 1173 | case PF_ADDR_NOROUTE: |
---|
| 1174 | case PF_ADDR_URPFFAILED: |
---|
| 1175 | return (0); |
---|
| 1176 | case PF_ADDR_TABLE: |
---|
| 1177 | return (strcmp(a->src.addr.v.tblname, b->src.addr.v.tblname)); |
---|
| 1178 | } |
---|
| 1179 | return (1); |
---|
| 1180 | } |
---|
| 1181 | |
---|
| 1182 | /* Compare two rules SRC port field for skiplist construction */ |
---|
| 1183 | int |
---|
| 1184 | skip_cmp_src_port(struct pf_rule *a, struct pf_rule *b) |
---|
| 1185 | { |
---|
| 1186 | if (a->src.port_op == PF_OP_NONE || a->src.port_op != b->src.port_op || |
---|
| 1187 | a->src.port[0] != b->src.port[0] || |
---|
| 1188 | a->src.port[1] != b->src.port[1]) |
---|
| 1189 | return (1); |
---|
| 1190 | /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0 |
---|
| 1191 | * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP || |
---|
| 1192 | * a->proto == IPPROTO_ICMP |
---|
| 1193 | * return (1); |
---|
| 1194 | */ |
---|
| 1195 | return (0); |
---|
| 1196 | } |
---|
| 1197 | |
---|
| 1198 | |
---|
| 1199 | void |
---|
| 1200 | skip_init(void) |
---|
| 1201 | { |
---|
| 1202 | struct { |
---|
| 1203 | char *name; |
---|
| 1204 | int skipnum; |
---|
| 1205 | int (*func)(struct pf_rule *, struct pf_rule *); |
---|
| 1206 | } comps[] = PF_SKIP_COMPARITORS; |
---|
| 1207 | int skipnum, i; |
---|
| 1208 | |
---|
| 1209 | for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) { |
---|
| 1210 | for (i = 0; i < sizeof(comps)/sizeof(*comps); i++) |
---|
| 1211 | if (comps[i].skipnum == skipnum) { |
---|
| 1212 | skip_comparitors[skipnum] = comps[i].func; |
---|
| 1213 | skip_comparitors_names[skipnum] = comps[i].name; |
---|
| 1214 | } |
---|
| 1215 | } |
---|
| 1216 | for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) |
---|
| 1217 | if (skip_comparitors[skipnum] == NULL) |
---|
| 1218 | errx(1, "Need to add skip step comparitor to pfctl?!"); |
---|
| 1219 | } |
---|
| 1220 | |
---|
| 1221 | /* |
---|
| 1222 | * Add a host/netmask to a table |
---|
| 1223 | */ |
---|
| 1224 | int |
---|
| 1225 | add_opt_table(struct pfctl *pf, struct pf_opt_tbl **tbl, sa_family_t af, |
---|
| 1226 | struct pf_rule_addr *addr) |
---|
| 1227 | { |
---|
| 1228 | #ifdef OPT_DEBUG |
---|
| 1229 | char buf[128]; |
---|
| 1230 | #endif /* OPT_DEBUG */ |
---|
| 1231 | static int tablenum = 0; |
---|
| 1232 | struct node_host node_host; |
---|
| 1233 | |
---|
| 1234 | if (*tbl == NULL) { |
---|
| 1235 | if ((*tbl = calloc(1, sizeof(**tbl))) == NULL || |
---|
| 1236 | ((*tbl)->pt_buf = calloc(1, sizeof(*(*tbl)->pt_buf))) == |
---|
| 1237 | NULL) |
---|
| 1238 | err(1, "calloc"); |
---|
| 1239 | (*tbl)->pt_buf->pfrb_type = PFRB_ADDRS; |
---|
| 1240 | SIMPLEQ_INIT(&(*tbl)->pt_nodes); |
---|
| 1241 | |
---|
| 1242 | /* This is just a temporary table name */ |
---|
| 1243 | snprintf((*tbl)->pt_name, sizeof((*tbl)->pt_name), "%s%d", |
---|
| 1244 | PF_OPT_TABLE_PREFIX, tablenum++); |
---|
| 1245 | DEBUG("creating table <%s>", (*tbl)->pt_name); |
---|
| 1246 | } |
---|
| 1247 | |
---|
| 1248 | memset(&node_host, 0, sizeof(node_host)); |
---|
| 1249 | node_host.af = af; |
---|
| 1250 | node_host.addr = addr->addr; |
---|
| 1251 | |
---|
| 1252 | #ifdef OPT_DEBUG |
---|
| 1253 | DEBUG("<%s> adding %s/%d", (*tbl)->pt_name, inet_ntop(af, |
---|
| 1254 | &node_host.addr.v.a.addr, buf, sizeof(buf)), |
---|
| 1255 | unmask(&node_host.addr.v.a.mask, af)); |
---|
| 1256 | #endif /* OPT_DEBUG */ |
---|
| 1257 | |
---|
| 1258 | if (append_addr_host((*tbl)->pt_buf, &node_host, 0, 0)) { |
---|
| 1259 | warn("failed to add host"); |
---|
| 1260 | return (1); |
---|
| 1261 | } |
---|
| 1262 | if (pf->opts & PF_OPT_VERBOSE) { |
---|
| 1263 | struct node_tinit *ti; |
---|
| 1264 | |
---|
| 1265 | if ((ti = calloc(1, sizeof(*ti))) == NULL) |
---|
| 1266 | err(1, "malloc"); |
---|
| 1267 | if ((ti->host = malloc(sizeof(*ti->host))) == NULL) |
---|
| 1268 | err(1, "malloc"); |
---|
| 1269 | memcpy(ti->host, &node_host, sizeof(*ti->host)); |
---|
| 1270 | SIMPLEQ_INSERT_TAIL(&(*tbl)->pt_nodes, ti, entries); |
---|
| 1271 | } |
---|
| 1272 | |
---|
| 1273 | (*tbl)->pt_rulecount++; |
---|
| 1274 | if ((*tbl)->pt_rulecount == TABLE_THRESHOLD) |
---|
| 1275 | DEBUG("table <%s> now faster than skip steps", (*tbl)->pt_name); |
---|
| 1276 | |
---|
| 1277 | return (0); |
---|
| 1278 | } |
---|
| 1279 | |
---|
| 1280 | |
---|
| 1281 | /* |
---|
| 1282 | * Do the dirty work of choosing an unused table name and creating it. |
---|
| 1283 | * (be careful with the table name, it might already be used in another anchor) |
---|
| 1284 | */ |
---|
| 1285 | int |
---|
| 1286 | pf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl) |
---|
| 1287 | { |
---|
| 1288 | static int tablenum; |
---|
| 1289 | struct pfr_table *t; |
---|
| 1290 | |
---|
| 1291 | if (table_buffer.pfrb_type == 0) { |
---|
| 1292 | /* Initialize the list of tables */ |
---|
| 1293 | table_buffer.pfrb_type = PFRB_TABLES; |
---|
| 1294 | for (;;) { |
---|
| 1295 | pfr_buf_grow(&table_buffer, table_buffer.pfrb_size); |
---|
| 1296 | table_buffer.pfrb_size = table_buffer.pfrb_msize; |
---|
| 1297 | if (pfr_get_tables(NULL, table_buffer.pfrb_caddr, |
---|
| 1298 | &table_buffer.pfrb_size, PFR_FLAG_ALLRSETS)) |
---|
| 1299 | err(1, "pfr_get_tables"); |
---|
| 1300 | if (table_buffer.pfrb_size <= table_buffer.pfrb_msize) |
---|
| 1301 | break; |
---|
| 1302 | } |
---|
| 1303 | table_identifier = arc4random(); |
---|
| 1304 | } |
---|
| 1305 | |
---|
| 1306 | /* XXX would be *really* nice to avoid duplicating identical tables */ |
---|
| 1307 | |
---|
| 1308 | /* Now we have to pick a table name that isn't used */ |
---|
| 1309 | again: |
---|
| 1310 | DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl->pt_name, |
---|
| 1311 | PF_OPT_TABLE_PREFIX, table_identifier, tablenum); |
---|
| 1312 | snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d", |
---|
| 1313 | PF_OPT_TABLE_PREFIX, table_identifier, tablenum); |
---|
| 1314 | PFRB_FOREACH(t, &table_buffer) { |
---|
| 1315 | if (strcasecmp(t->pfrt_name, tbl->pt_name) == 0) { |
---|
| 1316 | /* Collision. Try again */ |
---|
| 1317 | DEBUG("wow, table <%s> in use. trying again", |
---|
| 1318 | tbl->pt_name); |
---|
| 1319 | table_identifier = arc4random(); |
---|
| 1320 | goto again; |
---|
| 1321 | } |
---|
| 1322 | } |
---|
| 1323 | tablenum++; |
---|
| 1324 | |
---|
| 1325 | |
---|
| 1326 | if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1, |
---|
| 1327 | pf->astack[0]->name, tbl->pt_buf, pf->astack[0]->ruleset.tticket)) { |
---|
| 1328 | warn("failed to create table %s in %s", |
---|
| 1329 | tbl->pt_name, pf->astack[0]->name); |
---|
| 1330 | return (1); |
---|
| 1331 | } |
---|
| 1332 | return (0); |
---|
| 1333 | } |
---|
| 1334 | |
---|
| 1335 | /* |
---|
| 1336 | * Partition the flat ruleset into a list of distinct superblocks |
---|
| 1337 | */ |
---|
| 1338 | int |
---|
| 1339 | construct_superblocks(struct pfctl *pf, struct pf_opt_queue *opt_queue, |
---|
| 1340 | struct superblocks *superblocks) |
---|
| 1341 | { |
---|
| 1342 | struct superblock *block = NULL; |
---|
| 1343 | struct pf_opt_rule *por; |
---|
| 1344 | int i; |
---|
| 1345 | |
---|
| 1346 | while (!TAILQ_EMPTY(opt_queue)) { |
---|
| 1347 | por = TAILQ_FIRST(opt_queue); |
---|
| 1348 | TAILQ_REMOVE(opt_queue, por, por_entry); |
---|
| 1349 | if (block == NULL || !superblock_inclusive(block, por)) { |
---|
| 1350 | if ((block = calloc(1, sizeof(*block))) == NULL) { |
---|
| 1351 | warn("calloc"); |
---|
| 1352 | return (1); |
---|
| 1353 | } |
---|
| 1354 | TAILQ_INIT(&block->sb_rules); |
---|
| 1355 | for (i = 0; i < PF_SKIP_COUNT; i++) |
---|
| 1356 | TAILQ_INIT(&block->sb_skipsteps[i]); |
---|
| 1357 | TAILQ_INSERT_TAIL(superblocks, block, sb_entry); |
---|
| 1358 | } |
---|
| 1359 | TAILQ_INSERT_TAIL(&block->sb_rules, por, por_entry); |
---|
| 1360 | } |
---|
| 1361 | |
---|
| 1362 | return (0); |
---|
| 1363 | } |
---|
| 1364 | |
---|
| 1365 | |
---|
| 1366 | /* |
---|
| 1367 | * Compare two rule addresses |
---|
| 1368 | */ |
---|
| 1369 | int |
---|
| 1370 | addrs_equal(struct pf_rule_addr *a, struct pf_rule_addr *b) |
---|
| 1371 | { |
---|
| 1372 | if (a->neg != b->neg) |
---|
| 1373 | return (0); |
---|
| 1374 | return (memcmp(&a->addr, &b->addr, sizeof(a->addr)) == 0); |
---|
| 1375 | } |
---|
| 1376 | |
---|
| 1377 | |
---|
| 1378 | /* |
---|
| 1379 | * The addresses are not equal, but can we combine them into one table? |
---|
| 1380 | */ |
---|
| 1381 | int |
---|
| 1382 | addrs_combineable(struct pf_rule_addr *a, struct pf_rule_addr *b) |
---|
| 1383 | { |
---|
| 1384 | if (a->addr.type != PF_ADDR_ADDRMASK || |
---|
| 1385 | b->addr.type != PF_ADDR_ADDRMASK) |
---|
| 1386 | return (0); |
---|
| 1387 | if (a->neg != b->neg || a->port_op != b->port_op || |
---|
| 1388 | a->port[0] != b->port[0] || a->port[1] != b->port[1]) |
---|
| 1389 | return (0); |
---|
| 1390 | return (1); |
---|
| 1391 | } |
---|
| 1392 | |
---|
| 1393 | |
---|
| 1394 | /* |
---|
| 1395 | * Are we allowed to combine these two rules |
---|
| 1396 | */ |
---|
| 1397 | int |
---|
| 1398 | rules_combineable(struct pf_rule *p1, struct pf_rule *p2) |
---|
| 1399 | { |
---|
| 1400 | struct pf_rule a, b; |
---|
| 1401 | |
---|
| 1402 | comparable_rule(&a, p1, COMBINED); |
---|
| 1403 | comparable_rule(&b, p2, COMBINED); |
---|
| 1404 | return (memcmp(&a, &b, sizeof(a)) == 0); |
---|
| 1405 | } |
---|
| 1406 | |
---|
| 1407 | |
---|
| 1408 | /* |
---|
| 1409 | * Can a rule be included inside a superblock |
---|
| 1410 | */ |
---|
| 1411 | int |
---|
| 1412 | superblock_inclusive(struct superblock *block, struct pf_opt_rule *por) |
---|
| 1413 | { |
---|
| 1414 | struct pf_rule a, b; |
---|
| 1415 | int i, j; |
---|
| 1416 | |
---|
| 1417 | /* First check for hard breaks */ |
---|
| 1418 | for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) { |
---|
| 1419 | if (pf_rule_desc[i].prf_type == BARRIER) { |
---|
| 1420 | for (j = 0; j < pf_rule_desc[i].prf_size; j++) |
---|
| 1421 | if (((char *)&por->por_rule)[j + |
---|
| 1422 | pf_rule_desc[i].prf_offset] != 0) |
---|
| 1423 | return (0); |
---|
| 1424 | } |
---|
| 1425 | } |
---|
| 1426 | |
---|
| 1427 | /* per-rule src-track is also a hard break */ |
---|
| 1428 | if (por->por_rule.rule_flag & PFRULE_RULESRCTRACK) |
---|
| 1429 | return (0); |
---|
| 1430 | |
---|
| 1431 | /* |
---|
| 1432 | * Have to handle interface groups separately. Consider the following |
---|
| 1433 | * rules: |
---|
| 1434 | * block on EXTIFS to any port 22 |
---|
| 1435 | * pass on em0 to any port 22 |
---|
| 1436 | * (where EXTIFS is an arbitrary interface group) |
---|
| 1437 | * The optimizer may decide to re-order the pass rule in front of the |
---|
| 1438 | * block rule. But what if EXTIFS includes em0??? Such a reordering |
---|
| 1439 | * would change the meaning of the ruleset. |
---|
| 1440 | * We can't just lookup the EXTIFS group and check if em0 is a member |
---|
| 1441 | * because the user is allowed to add interfaces to a group during |
---|
| 1442 | * runtime. |
---|
| 1443 | * Ergo interface groups become a defacto superblock break :-( |
---|
| 1444 | */ |
---|
| 1445 | if (interface_group(por->por_rule.ifname) || |
---|
| 1446 | interface_group(TAILQ_FIRST(&block->sb_rules)->por_rule.ifname)) { |
---|
| 1447 | if (strcasecmp(por->por_rule.ifname, |
---|
| 1448 | TAILQ_FIRST(&block->sb_rules)->por_rule.ifname) != 0) |
---|
| 1449 | return (0); |
---|
| 1450 | } |
---|
| 1451 | |
---|
| 1452 | comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE); |
---|
| 1453 | comparable_rule(&b, &por->por_rule, NOMERGE); |
---|
| 1454 | if (memcmp(&a, &b, sizeof(a)) == 0) |
---|
| 1455 | return (1); |
---|
| 1456 | |
---|
| 1457 | #ifdef OPT_DEBUG |
---|
| 1458 | for (i = 0; i < sizeof(por->por_rule); i++) { |
---|
| 1459 | int closest = -1; |
---|
| 1460 | if (((u_int8_t *)&a)[i] != ((u_int8_t *)&b)[i]) { |
---|
| 1461 | for (j = 0; j < sizeof(pf_rule_desc) / |
---|
| 1462 | sizeof(*pf_rule_desc); j++) { |
---|
| 1463 | if (i >= pf_rule_desc[j].prf_offset && |
---|
| 1464 | i < pf_rule_desc[j].prf_offset + |
---|
| 1465 | pf_rule_desc[j].prf_size) { |
---|
| 1466 | DEBUG("superblock break @ %d due to %s", |
---|
| 1467 | por->por_rule.nr, |
---|
| 1468 | pf_rule_desc[j].prf_name); |
---|
| 1469 | return (0); |
---|
| 1470 | } |
---|
| 1471 | if (i > pf_rule_desc[j].prf_offset) { |
---|
| 1472 | if (closest == -1 || |
---|
| 1473 | i-pf_rule_desc[j].prf_offset < |
---|
| 1474 | i-pf_rule_desc[closest].prf_offset) |
---|
| 1475 | closest = j; |
---|
| 1476 | } |
---|
| 1477 | } |
---|
| 1478 | |
---|
| 1479 | if (closest >= 0) |
---|
| 1480 | DEBUG("superblock break @ %d on %s+%xh", |
---|
| 1481 | por->por_rule.nr, |
---|
| 1482 | pf_rule_desc[closest].prf_name, |
---|
| 1483 | i - pf_rule_desc[closest].prf_offset - |
---|
| 1484 | pf_rule_desc[closest].prf_size); |
---|
| 1485 | else |
---|
| 1486 | DEBUG("superblock break @ %d on field @ %d", |
---|
| 1487 | por->por_rule.nr, i); |
---|
| 1488 | return (0); |
---|
| 1489 | } |
---|
| 1490 | } |
---|
| 1491 | #endif /* OPT_DEBUG */ |
---|
| 1492 | |
---|
| 1493 | return (0); |
---|
| 1494 | } |
---|
| 1495 | |
---|
| 1496 | |
---|
| 1497 | /* |
---|
| 1498 | * Figure out if an interface name is an actual interface or actually a |
---|
| 1499 | * group of interfaces. |
---|
| 1500 | */ |
---|
| 1501 | int |
---|
| 1502 | interface_group(const char *ifname) |
---|
| 1503 | { |
---|
| 1504 | if (ifname == NULL || !ifname[0]) |
---|
| 1505 | return (0); |
---|
| 1506 | |
---|
| 1507 | /* Real interfaces must end in a number, interface groups do not */ |
---|
| 1508 | if (isdigit(ifname[strlen(ifname) - 1])) |
---|
| 1509 | return (0); |
---|
| 1510 | else |
---|
| 1511 | return (1); |
---|
| 1512 | } |
---|
| 1513 | |
---|
| 1514 | |
---|
| 1515 | /* |
---|
| 1516 | * Make a rule that can directly compared by memcmp() |
---|
| 1517 | */ |
---|
| 1518 | void |
---|
| 1519 | comparable_rule(struct pf_rule *dst, const struct pf_rule *src, int type) |
---|
| 1520 | { |
---|
| 1521 | int i; |
---|
| 1522 | /* |
---|
| 1523 | * To simplify the comparison, we just zero out the fields that are |
---|
| 1524 | * allowed to be different and then do a simple memcmp() |
---|
| 1525 | */ |
---|
| 1526 | memcpy(dst, src, sizeof(*dst)); |
---|
| 1527 | for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) |
---|
| 1528 | if (pf_rule_desc[i].prf_type >= type) { |
---|
| 1529 | #ifdef OPT_DEBUG |
---|
| 1530 | assert(pf_rule_desc[i].prf_type != NEVER || |
---|
| 1531 | *(((char *)dst) + pf_rule_desc[i].prf_offset) == 0); |
---|
| 1532 | #endif /* OPT_DEBUG */ |
---|
| 1533 | memset(((char *)dst) + pf_rule_desc[i].prf_offset, 0, |
---|
| 1534 | pf_rule_desc[i].prf_size); |
---|
| 1535 | } |
---|
| 1536 | } |
---|
| 1537 | |
---|
| 1538 | |
---|
| 1539 | /* |
---|
| 1540 | * Remove superset information from two rules so we can directly compare them |
---|
| 1541 | * with memcmp() |
---|
| 1542 | */ |
---|
| 1543 | void |
---|
| 1544 | exclude_supersets(struct pf_rule *super, struct pf_rule *sub) |
---|
| 1545 | { |
---|
| 1546 | if (super->ifname[0] == '\0') |
---|
| 1547 | memset(sub->ifname, 0, sizeof(sub->ifname)); |
---|
| 1548 | if (super->direction == PF_INOUT) |
---|
| 1549 | sub->direction = PF_INOUT; |
---|
| 1550 | if ((super->proto == 0 || super->proto == sub->proto) && |
---|
| 1551 | super->flags == 0 && super->flagset == 0 && (sub->flags || |
---|
| 1552 | sub->flagset)) { |
---|
| 1553 | sub->flags = super->flags; |
---|
| 1554 | sub->flagset = super->flagset; |
---|
| 1555 | } |
---|
| 1556 | if (super->proto == 0) |
---|
| 1557 | sub->proto = 0; |
---|
| 1558 | |
---|
| 1559 | if (super->src.port_op == 0) { |
---|
| 1560 | sub->src.port_op = 0; |
---|
| 1561 | sub->src.port[0] = 0; |
---|
| 1562 | sub->src.port[1] = 0; |
---|
| 1563 | } |
---|
| 1564 | if (super->dst.port_op == 0) { |
---|
| 1565 | sub->dst.port_op = 0; |
---|
| 1566 | sub->dst.port[0] = 0; |
---|
| 1567 | sub->dst.port[1] = 0; |
---|
| 1568 | } |
---|
| 1569 | |
---|
| 1570 | if (super->src.addr.type == PF_ADDR_ADDRMASK && !super->src.neg && |
---|
| 1571 | !sub->src.neg && super->src.addr.v.a.mask.addr32[0] == 0 && |
---|
| 1572 | super->src.addr.v.a.mask.addr32[1] == 0 && |
---|
| 1573 | super->src.addr.v.a.mask.addr32[2] == 0 && |
---|
| 1574 | super->src.addr.v.a.mask.addr32[3] == 0) |
---|
| 1575 | memset(&sub->src.addr, 0, sizeof(sub->src.addr)); |
---|
| 1576 | else if (super->src.addr.type == PF_ADDR_ADDRMASK && |
---|
| 1577 | sub->src.addr.type == PF_ADDR_ADDRMASK && |
---|
| 1578 | super->src.neg == sub->src.neg && |
---|
| 1579 | super->af == sub->af && |
---|
| 1580 | unmask(&super->src.addr.v.a.mask, super->af) < |
---|
| 1581 | unmask(&sub->src.addr.v.a.mask, sub->af) && |
---|
| 1582 | super->src.addr.v.a.addr.addr32[0] == |
---|
| 1583 | (sub->src.addr.v.a.addr.addr32[0] & |
---|
| 1584 | super->src.addr.v.a.mask.addr32[0]) && |
---|
| 1585 | super->src.addr.v.a.addr.addr32[1] == |
---|
| 1586 | (sub->src.addr.v.a.addr.addr32[1] & |
---|
| 1587 | super->src.addr.v.a.mask.addr32[1]) && |
---|
| 1588 | super->src.addr.v.a.addr.addr32[2] == |
---|
| 1589 | (sub->src.addr.v.a.addr.addr32[2] & |
---|
| 1590 | super->src.addr.v.a.mask.addr32[2]) && |
---|
| 1591 | super->src.addr.v.a.addr.addr32[3] == |
---|
| 1592 | (sub->src.addr.v.a.addr.addr32[3] & |
---|
| 1593 | super->src.addr.v.a.mask.addr32[3])) { |
---|
| 1594 | /* sub->src.addr is a subset of super->src.addr/mask */ |
---|
| 1595 | memcpy(&sub->src.addr, &super->src.addr, sizeof(sub->src.addr)); |
---|
| 1596 | } |
---|
| 1597 | |
---|
| 1598 | if (super->dst.addr.type == PF_ADDR_ADDRMASK && !super->dst.neg && |
---|
| 1599 | !sub->dst.neg && super->dst.addr.v.a.mask.addr32[0] == 0 && |
---|
| 1600 | super->dst.addr.v.a.mask.addr32[1] == 0 && |
---|
| 1601 | super->dst.addr.v.a.mask.addr32[2] == 0 && |
---|
| 1602 | super->dst.addr.v.a.mask.addr32[3] == 0) |
---|
| 1603 | memset(&sub->dst.addr, 0, sizeof(sub->dst.addr)); |
---|
| 1604 | else if (super->dst.addr.type == PF_ADDR_ADDRMASK && |
---|
| 1605 | sub->dst.addr.type == PF_ADDR_ADDRMASK && |
---|
| 1606 | super->dst.neg == sub->dst.neg && |
---|
| 1607 | super->af == sub->af && |
---|
| 1608 | unmask(&super->dst.addr.v.a.mask, super->af) < |
---|
| 1609 | unmask(&sub->dst.addr.v.a.mask, sub->af) && |
---|
| 1610 | super->dst.addr.v.a.addr.addr32[0] == |
---|
| 1611 | (sub->dst.addr.v.a.addr.addr32[0] & |
---|
| 1612 | super->dst.addr.v.a.mask.addr32[0]) && |
---|
| 1613 | super->dst.addr.v.a.addr.addr32[1] == |
---|
| 1614 | (sub->dst.addr.v.a.addr.addr32[1] & |
---|
| 1615 | super->dst.addr.v.a.mask.addr32[1]) && |
---|
| 1616 | super->dst.addr.v.a.addr.addr32[2] == |
---|
| 1617 | (sub->dst.addr.v.a.addr.addr32[2] & |
---|
| 1618 | super->dst.addr.v.a.mask.addr32[2]) && |
---|
| 1619 | super->dst.addr.v.a.addr.addr32[3] == |
---|
| 1620 | (sub->dst.addr.v.a.addr.addr32[3] & |
---|
| 1621 | super->dst.addr.v.a.mask.addr32[3])) { |
---|
| 1622 | /* sub->dst.addr is a subset of super->dst.addr/mask */ |
---|
| 1623 | memcpy(&sub->dst.addr, &super->dst.addr, sizeof(sub->dst.addr)); |
---|
| 1624 | } |
---|
| 1625 | |
---|
| 1626 | if (super->af == 0) |
---|
| 1627 | sub->af = 0; |
---|
| 1628 | } |
---|
| 1629 | |
---|
| 1630 | |
---|
| 1631 | void |
---|
| 1632 | superblock_free(struct pfctl *pf, struct superblock *block) |
---|
| 1633 | { |
---|
| 1634 | struct pf_opt_rule *por; |
---|
| 1635 | while ((por = TAILQ_FIRST(&block->sb_rules))) { |
---|
| 1636 | TAILQ_REMOVE(&block->sb_rules, por, por_entry); |
---|
| 1637 | if (por->por_src_tbl) { |
---|
| 1638 | if (por->por_src_tbl->pt_buf) { |
---|
| 1639 | pfr_buf_clear(por->por_src_tbl->pt_buf); |
---|
| 1640 | free(por->por_src_tbl->pt_buf); |
---|
| 1641 | } |
---|
| 1642 | free(por->por_src_tbl); |
---|
| 1643 | } |
---|
| 1644 | if (por->por_dst_tbl) { |
---|
| 1645 | if (por->por_dst_tbl->pt_buf) { |
---|
| 1646 | pfr_buf_clear(por->por_dst_tbl->pt_buf); |
---|
| 1647 | free(por->por_dst_tbl->pt_buf); |
---|
| 1648 | } |
---|
| 1649 | free(por->por_dst_tbl); |
---|
| 1650 | } |
---|
| 1651 | free(por); |
---|
| 1652 | } |
---|
| 1653 | if (block->sb_profiled_block) |
---|
| 1654 | superblock_free(pf, block->sb_profiled_block); |
---|
| 1655 | free(block); |
---|
| 1656 | } |
---|
| 1657 | |
---|