1 /* $OpenBSD: pfctl_optimize.c,v 1.18 2008/05/07 06:23:30 markus Exp $ */
4 * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org>
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 #include <sys/types.h>
20 #include <sys/ioctl.h>
21 #include <sys/socket.h>
24 #include <net/pf/pfvar.h>
26 #include <netinet/in.h>
27 #include <arpa/inet.h>
38 #include "pfctl_parser.h"
41 /* The size at which a table becomes faster than individual rules */
42 #define TABLE_THRESHOLD 6
45 /* #define OPT_DEBUG 1 */
47 # define DEBUG(str, v...) \
48 printf("%s: " str "\n", __func__ , ## v)
50 # define DEBUG(str, v...) ((void)0)
55 * A container that lets us sort a superblock to optimize the skip step jumps
58 int ps_count
; /* number of items */
59 TAILQ_HEAD( , pf_opt_rule
) ps_rules
;
60 TAILQ_ENTRY(pf_skip_step
) ps_entry
;
65 * A superblock is a block of adjacent rules of similar action. If there
66 * are five PASS rules in a row, they all become members of a superblock.
67 * Once we have a superblock, we are free to re-order any rules within it
68 * in order to improve performance; if a packet is passed, it doesn't matter
72 TAILQ_HEAD( , pf_opt_rule
) sb_rules
;
73 TAILQ_ENTRY(superblock
) sb_entry
;
74 struct superblock
*sb_profiled_block
;
75 TAILQ_HEAD(skiplist
, pf_skip_step
) sb_skipsteps
[PF_SKIP_COUNT
];
77 TAILQ_HEAD(superblocks
, superblock
);
81 * Description of the PF rule structure.
84 BARRIER
, /* the presence of the field puts the rule in it's own block */
85 BREAK
, /* the field may not differ between rules in a superblock */
86 NOMERGE
, /* the field may not differ between rules when combined */
87 COMBINED
, /* the field may itself be combined with other rules */
88 DC
, /* we just don't care about the field */
89 NEVER
}; /* we should never see this field set?!? */
90 struct pf_rule_field
{
96 #define PF_RULE_FIELD(field, ty) \
99 offsetof(struct pf_rule, field), \
100 sizeof(((struct pf_rule *)0)->field)}
104 * The presence of these fields in a rule put the rule in it's own
105 * superblock. Thus it will not be optimized. It also prevents the
106 * rule from being re-ordered at all.
108 PF_RULE_FIELD(label
, BARRIER
),
109 PF_RULE_FIELD(prob
, BARRIER
),
110 PF_RULE_FIELD(max_states
, BARRIER
),
111 PF_RULE_FIELD(max_src_nodes
, BARRIER
),
112 PF_RULE_FIELD(max_src_states
, BARRIER
),
113 PF_RULE_FIELD(max_src_conn
, BARRIER
),
114 PF_RULE_FIELD(max_src_conn_rate
, BARRIER
),
115 PF_RULE_FIELD(anchor
, BARRIER
), /* for now */
118 * These fields must be the same between all rules in the same superblock.
119 * These rules are allowed to be re-ordered but only among like rules.
120 * For instance we can re-order all 'tag "foo"' rules because they have the
121 * same tag. But we can not re-order between a 'tag "foo"' and a
122 * 'tag "bar"' since that would change the meaning of the ruleset.
124 PF_RULE_FIELD(tagname
, BREAK
),
125 PF_RULE_FIELD(keep_state
, BREAK
),
126 PF_RULE_FIELD(qname
, BREAK
),
127 PF_RULE_FIELD(pqname
, BREAK
),
128 PF_RULE_FIELD(rt
, BREAK
),
129 PF_RULE_FIELD(allow_opts
, BREAK
),
130 PF_RULE_FIELD(rule_flag
, BREAK
),
131 PF_RULE_FIELD(action
, BREAK
),
132 PF_RULE_FIELD(log
, BREAK
),
133 PF_RULE_FIELD(quick
, BREAK
),
134 PF_RULE_FIELD(return_ttl
, BREAK
),
135 PF_RULE_FIELD(overload_tblname
, BREAK
),
136 PF_RULE_FIELD(flush
, BREAK
),
137 PF_RULE_FIELD(rpool
, BREAK
),
138 PF_RULE_FIELD(logif
, BREAK
),
141 * Any fields not listed in this structure act as BREAK fields
146 * These fields must not differ when we merge two rules together but
147 * their difference isn't enough to put the rules in different superblocks.
148 * There are no problems re-ordering any rules with these fields.
150 PF_RULE_FIELD(af
, NOMERGE
),
151 PF_RULE_FIELD(ifnot
, NOMERGE
),
152 PF_RULE_FIELD(ifname
, NOMERGE
), /* hack for IF groups */
153 PF_RULE_FIELD(match_tag_not
, NOMERGE
),
154 PF_RULE_FIELD(match_tagname
, NOMERGE
),
155 PF_RULE_FIELD(os_fingerprint
, NOMERGE
),
156 PF_RULE_FIELD(timeout
, NOMERGE
),
157 PF_RULE_FIELD(return_icmp
, NOMERGE
),
158 PF_RULE_FIELD(return_icmp6
, NOMERGE
),
159 PF_RULE_FIELD(uid
, NOMERGE
),
160 PF_RULE_FIELD(gid
, NOMERGE
),
161 PF_RULE_FIELD(direction
, NOMERGE
),
162 PF_RULE_FIELD(proto
, NOMERGE
),
163 PF_RULE_FIELD(type
, NOMERGE
),
164 PF_RULE_FIELD(code
, NOMERGE
),
165 PF_RULE_FIELD(flags
, NOMERGE
),
166 PF_RULE_FIELD(flagset
, NOMERGE
),
167 PF_RULE_FIELD(tos
, NOMERGE
),
168 PF_RULE_FIELD(src
.port
, NOMERGE
),
169 PF_RULE_FIELD(dst
.port
, NOMERGE
),
170 PF_RULE_FIELD(src
.port_op
, NOMERGE
),
171 PF_RULE_FIELD(dst
.port_op
, NOMERGE
),
172 PF_RULE_FIELD(src
.neg
, NOMERGE
),
173 PF_RULE_FIELD(dst
.neg
, NOMERGE
),
175 /* These fields can be merged */
176 PF_RULE_FIELD(src
.addr
, COMBINED
),
177 PF_RULE_FIELD(dst
.addr
, COMBINED
),
179 /* We just don't care about these fields. They're set by the kernel */
180 PF_RULE_FIELD(skip
, DC
),
181 PF_RULE_FIELD(evaluations
, DC
),
182 PF_RULE_FIELD(packets
, DC
),
183 PF_RULE_FIELD(bytes
, DC
),
184 PF_RULE_FIELD(kif
, DC
),
185 PF_RULE_FIELD(states_cur
, DC
),
186 PF_RULE_FIELD(states_tot
, DC
),
187 PF_RULE_FIELD(src_nodes
, DC
),
188 PF_RULE_FIELD(nr
, DC
),
189 PF_RULE_FIELD(entries
, DC
),
190 PF_RULE_FIELD(qid
, DC
),
191 PF_RULE_FIELD(pqid
, DC
),
192 PF_RULE_FIELD(anchor_relative
, DC
),
193 PF_RULE_FIELD(anchor_wildcard
, DC
),
194 PF_RULE_FIELD(tag
, DC
),
195 PF_RULE_FIELD(match_tag
, DC
),
196 PF_RULE_FIELD(overload_tbl
, DC
),
198 /* These fields should never be set in a PASS/BLOCK rule */
199 PF_RULE_FIELD(natpass
, NEVER
),
200 PF_RULE_FIELD(max_mss
, NEVER
),
201 PF_RULE_FIELD(min_ttl
, NEVER
),
202 PF_RULE_FIELD(set_tos
, NEVER
),
207 int add_opt_table(struct pfctl
*, struct pf_opt_tbl
**, sa_family_t
,
208 struct pf_rule_addr
*);
209 int addrs_combineable(struct pf_rule_addr
*, struct pf_rule_addr
*);
210 int addrs_equal(struct pf_rule_addr
*, struct pf_rule_addr
*);
211 int block_feedback(struct pfctl
*, struct superblock
*);
212 int combine_rules(struct pfctl
*, struct superblock
*);
213 void comparable_rule(struct pf_rule
*, const struct pf_rule
*, int);
214 int construct_superblocks(struct pfctl
*, struct pf_opt_queue
*,
215 struct superblocks
*);
216 void exclude_supersets(struct pf_rule
*, struct pf_rule
*);
217 int interface_group(const char *);
218 int load_feedback_profile(struct pfctl
*, struct superblocks
*);
219 int optimize_superblock(struct pfctl
*, struct superblock
*);
220 int pf_opt_create_table(struct pfctl
*, struct pf_opt_tbl
*);
221 void remove_from_skipsteps(struct skiplist
*, struct superblock
*,
222 struct pf_opt_rule
*, struct pf_skip_step
*);
223 int remove_identical_rules(struct pfctl
*, struct superblock
*);
224 int reorder_rules(struct pfctl
*, struct superblock
*, int);
225 int rules_combineable(struct pf_rule
*, struct pf_rule
*);
226 void skip_append(struct superblock
*, int, struct pf_skip_step
*,
227 struct pf_opt_rule
*);
228 int skip_compare(int, struct pf_skip_step
*, struct pf_opt_rule
*);
229 void skip_init(void);
230 int skip_cmp_af(struct pf_rule
*, struct pf_rule
*);
231 int skip_cmp_dir(struct pf_rule
*, struct pf_rule
*);
232 int skip_cmp_dst_addr(struct pf_rule
*, struct pf_rule
*);
233 int skip_cmp_dst_port(struct pf_rule
*, struct pf_rule
*);
234 int skip_cmp_ifp(struct pf_rule
*, struct pf_rule
*);
235 int skip_cmp_proto(struct pf_rule
*, struct pf_rule
*);
236 int skip_cmp_src_addr(struct pf_rule
*, struct pf_rule
*);
237 int skip_cmp_src_port(struct pf_rule
*, struct pf_rule
*);
238 int superblock_inclusive(struct superblock
*, struct pf_opt_rule
*);
239 void superblock_free(struct pfctl
*, struct superblock
*);
242 int (*skip_comparitors
[PF_SKIP_COUNT
])(struct pf_rule
*, struct pf_rule
*);
243 const char *skip_comparitors_names
[PF_SKIP_COUNT
];
244 #define PF_SKIP_COMPARITORS { \
245 { "ifp", PF_SKIP_IFP, skip_cmp_ifp }, \
246 { "dir", PF_SKIP_DIR, skip_cmp_dir }, \
247 { "af", PF_SKIP_AF, skip_cmp_af }, \
248 { "proto", PF_SKIP_PROTO, skip_cmp_proto }, \
249 { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr }, \
250 { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port }, \
251 { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr }, \
252 { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port } \
255 struct pfr_buffer table_buffer
;
256 int table_identifier
;
260 pfctl_optimize_ruleset(struct pfctl
*pf
, struct pf_ruleset
*rs
)
262 struct superblocks superblocks
;
263 struct pf_opt_queue opt_queue
;
264 struct superblock
*block
;
265 struct pf_opt_rule
*por
;
267 struct pf_rulequeue
*old_rules
;
269 DEBUG("optimizing ruleset");
270 memset(&table_buffer
, 0, sizeof(table_buffer
));
272 TAILQ_INIT(&opt_queue
);
274 old_rules
= rs
->rules
[PF_RULESET_FILTER
].active
.ptr
;
275 rs
->rules
[PF_RULESET_FILTER
].active
.ptr
=
276 rs
->rules
[PF_RULESET_FILTER
].inactive
.ptr
;
277 rs
->rules
[PF_RULESET_FILTER
].inactive
.ptr
= old_rules
;
280 * XXX expanding the pf_opt_rule format throughout pfctl might allow
281 * us to avoid all this copying.
283 while ((r
= TAILQ_FIRST(rs
->rules
[PF_RULESET_FILTER
].inactive
.ptr
))
285 TAILQ_REMOVE(rs
->rules
[PF_RULESET_FILTER
].inactive
.ptr
, r
,
287 if ((por
= calloc(1, sizeof(*por
))) == NULL
)
289 memcpy(&por
->por_rule
, r
, sizeof(*r
));
290 if (TAILQ_FIRST(&r
->rpool
.list
) != NULL
) {
291 TAILQ_INIT(&por
->por_rule
.rpool
.list
);
292 pfctl_move_pool(&r
->rpool
, &por
->por_rule
.rpool
);
294 bzero(&por
->por_rule
.rpool
,
295 sizeof(por
->por_rule
.rpool
));
298 TAILQ_INSERT_TAIL(&opt_queue
, por
, por_entry
);
301 TAILQ_INIT(&superblocks
);
302 if (construct_superblocks(pf
, &opt_queue
, &superblocks
))
305 if (pf
->optimize
& PF_OPTIMIZE_PROFILE
) {
306 if (load_feedback_profile(pf
, &superblocks
))
310 TAILQ_FOREACH(block
, &superblocks
, sb_entry
) {
311 if (optimize_superblock(pf
, block
))
315 rs
->anchor
->refcnt
= 0;
316 while ((block
= TAILQ_FIRST(&superblocks
))) {
317 TAILQ_REMOVE(&superblocks
, block
, sb_entry
);
319 while ((por
= TAILQ_FIRST(&block
->sb_rules
))) {
320 TAILQ_REMOVE(&block
->sb_rules
, por
, por_entry
);
321 por
->por_rule
.nr
= rs
->anchor
->refcnt
++;
322 if ((r
= calloc(1, sizeof(*r
))) == NULL
)
324 memcpy(r
, &por
->por_rule
, sizeof(*r
));
325 TAILQ_INIT(&r
->rpool
.list
);
326 pfctl_move_pool(&por
->por_rule
.rpool
, &r
->rpool
);
328 rs
->rules
[PF_RULESET_FILTER
].active
.ptr
,
338 while ((por
= TAILQ_FIRST(&opt_queue
))) {
339 TAILQ_REMOVE(&opt_queue
, por
, por_entry
);
340 if (por
->por_src_tbl
) {
341 pfr_buf_clear(por
->por_src_tbl
->pt_buf
);
342 free(por
->por_src_tbl
->pt_buf
);
343 free(por
->por_src_tbl
);
345 if (por
->por_dst_tbl
) {
346 pfr_buf_clear(por
->por_dst_tbl
->pt_buf
);
347 free(por
->por_dst_tbl
->pt_buf
);
348 free(por
->por_dst_tbl
);
352 while ((block
= TAILQ_FIRST(&superblocks
))) {
353 TAILQ_REMOVE(&superblocks
, block
, sb_entry
);
354 superblock_free(pf
, block
);
361 * Go ahead and optimize a superblock
364 optimize_superblock(struct pfctl
*pf
, struct superblock
*block
)
367 struct pf_opt_rule
*por
;
368 #endif /* OPT_DEBUG */
370 /* We have a few optimization passes:
371 * 1) remove duplicate rules or rules that are a subset of other
373 * 2) combine otherwise identical rules with different IP addresses
374 * into a single rule and put the addresses in a table.
375 * 3) re-order the rules to improve kernel skip steps
376 * 4) re-order the 'quick' rules based on feedback from the
377 * active ruleset statistics
379 * XXX combine_rules() doesn't combine v4 and v6 rules. would just
380 * have to keep af in the table container, make af 'COMBINE' and
381 * twiddle the af on the merged rule
382 * XXX maybe add a weighting to the metric on skipsteps when doing
383 * reordering. sometimes two sequential tables will be better
384 * that four consecutive interfaces.
385 * XXX need to adjust the skipstep count of everything after PROTO,
386 * since they aren't actually checked on a proto mismatch in
387 * pf_test_{tcp, udp, icmp}()
388 * XXX should i treat proto=0, af=0 or dir=0 special in skepstep
389 * calculation since they are a DC?
390 * XXX keep last skiplist of last superblock to influence this
391 * superblock. '5 inet6 log' should make '3 inet6' come before '4
392 * inet' in the next superblock.
393 * XXX would be useful to add tables for ports
394 * XXX we can also re-order some mutually exclusive superblocks to
395 * try merging superblocks before any of these optimization passes.
396 * for instance a single 'log in' rule in the middle of non-logging
400 /* shortcut. there will be a lot of 1-rule superblocks */
401 if (!TAILQ_NEXT(TAILQ_FIRST(&block
->sb_rules
), por_entry
))
405 printf("--- Superblock ---\n");
406 TAILQ_FOREACH(por
, &block
->sb_rules
, por_entry
) {
408 print_rule(&por
->por_rule
, por
->por_rule
.anchor
?
409 por
->por_rule
.anchor
->name
: "", 1);
411 #endif /* OPT_DEBUG */
414 if (remove_identical_rules(pf
, block
))
416 if (combine_rules(pf
, block
))
418 if ((pf
->optimize
& PF_OPTIMIZE_PROFILE
) &&
419 TAILQ_FIRST(&block
->sb_rules
)->por_rule
.quick
&&
420 block
->sb_profiled_block
) {
421 if (block_feedback(pf
, block
))
423 } else if (reorder_rules(pf
, block
, 0)) {
428 * Don't add any optimization passes below reorder_rules(). It will
429 * have divided superblocks into smaller blocks for further refinement
430 * and doesn't put them back together again. What once was a true
431 * superblock might have been split into multiple superblocks.
435 printf("--- END Superblock ---\n");
436 #endif /* OPT_DEBUG */
442 * Optimization pass #1: remove identical rules
445 remove_identical_rules(struct pfctl
*pf
, struct superblock
*block
)
447 struct pf_opt_rule
*por1
, *por2
, *por_next
, *por2_next
;
448 struct pf_rule a
, a2
, b
, b2
;
450 for (por1
= TAILQ_FIRST(&block
->sb_rules
); por1
; por1
= por_next
) {
451 por_next
= TAILQ_NEXT(por1
, por_entry
);
452 for (por2
= por_next
; por2
; por2
= por2_next
) {
453 por2_next
= TAILQ_NEXT(por2
, por_entry
);
454 comparable_rule(&a
, &por1
->por_rule
, DC
);
455 comparable_rule(&b
, &por2
->por_rule
, DC
);
456 memcpy(&a2
, &a
, sizeof(a2
));
457 memcpy(&b2
, &b
, sizeof(b2
));
459 exclude_supersets(&a
, &b
);
460 exclude_supersets(&b2
, &a2
);
461 if (memcmp(&a
, &b
, sizeof(a
)) == 0) {
462 DEBUG("removing identical rule nr%d = *nr%d*",
463 por1
->por_rule
.nr
, por2
->por_rule
.nr
);
464 TAILQ_REMOVE(&block
->sb_rules
, por2
, por_entry
);
465 if (por_next
== por2
)
466 por_next
= TAILQ_NEXT(por1
, por_entry
);
468 } else if (memcmp(&a2
, &b2
, sizeof(a2
)) == 0) {
469 DEBUG("removing identical rule *nr%d* = nr%d",
470 por1
->por_rule
.nr
, por2
->por_rule
.nr
);
471 TAILQ_REMOVE(&block
->sb_rules
, por1
, por_entry
);
483 * Optimization pass #2: combine similar rules with different addresses
484 * into a single rule and a table
487 combine_rules(struct pfctl
*pf
, struct superblock
*block
)
489 struct pf_opt_rule
*p1
, *p2
, *por_next
;
492 if ((pf
->loadopt
& PFCTL_FLAG_TABLE
) == 0) {
493 warnx("Must enable table loading for optimizations");
497 /* First we make a pass to combine the rules. O(n log n) */
498 TAILQ_FOREACH(p1
, &block
->sb_rules
, por_entry
) {
499 for (p2
= TAILQ_NEXT(p1
, por_entry
); p2
; p2
= por_next
) {
500 por_next
= TAILQ_NEXT(p2
, por_entry
);
502 src_eq
= addrs_equal(&p1
->por_rule
.src
,
504 dst_eq
= addrs_equal(&p1
->por_rule
.dst
,
507 if (src_eq
&& !dst_eq
&& p1
->por_src_tbl
== NULL
&&
508 p2
->por_dst_tbl
== NULL
&&
509 p2
->por_src_tbl
== NULL
&&
510 rules_combineable(&p1
->por_rule
, &p2
->por_rule
) &&
511 addrs_combineable(&p1
->por_rule
.dst
,
512 &p2
->por_rule
.dst
)) {
513 DEBUG("can combine rules nr%d = nr%d",
514 p1
->por_rule
.nr
, p2
->por_rule
.nr
);
515 if (p1
->por_dst_tbl
== NULL
&&
516 add_opt_table(pf
, &p1
->por_dst_tbl
,
517 p1
->por_rule
.af
, &p1
->por_rule
.dst
))
519 if (add_opt_table(pf
, &p1
->por_dst_tbl
,
520 p1
->por_rule
.af
, &p2
->por_rule
.dst
))
522 p2
->por_dst_tbl
= p1
->por_dst_tbl
;
523 if (p1
->por_dst_tbl
->pt_rulecount
>=
525 TAILQ_REMOVE(&block
->sb_rules
, p2
,
529 } else if (!src_eq
&& dst_eq
&& p1
->por_dst_tbl
== NULL
530 && p2
->por_src_tbl
== NULL
&&
531 p2
->por_dst_tbl
== NULL
&&
532 rules_combineable(&p1
->por_rule
, &p2
->por_rule
) &&
533 addrs_combineable(&p1
->por_rule
.src
,
534 &p2
->por_rule
.src
)) {
535 DEBUG("can combine rules nr%d = nr%d",
536 p1
->por_rule
.nr
, p2
->por_rule
.nr
);
537 if (p1
->por_src_tbl
== NULL
&&
538 add_opt_table(pf
, &p1
->por_src_tbl
,
539 p1
->por_rule
.af
, &p1
->por_rule
.src
))
541 if (add_opt_table(pf
, &p1
->por_src_tbl
,
542 p1
->por_rule
.af
, &p2
->por_rule
.src
))
544 p2
->por_src_tbl
= p1
->por_src_tbl
;
545 if (p1
->por_src_tbl
->pt_rulecount
>=
547 TAILQ_REMOVE(&block
->sb_rules
, p2
,
557 * Then we make a final pass to create a valid table name and
558 * insert the name into the rules.
560 for (p1
= TAILQ_FIRST(&block
->sb_rules
); p1
; p1
= por_next
) {
561 por_next
= TAILQ_NEXT(p1
, por_entry
);
562 assert(p1
->por_src_tbl
== NULL
|| p1
->por_dst_tbl
== NULL
);
564 if (p1
->por_src_tbl
&& p1
->por_src_tbl
->pt_rulecount
>=
566 if (p1
->por_src_tbl
->pt_generated
) {
567 /* This rule is included in a table */
568 TAILQ_REMOVE(&block
->sb_rules
, p1
, por_entry
);
572 p1
->por_src_tbl
->pt_generated
= 1;
574 if ((pf
->opts
& PF_OPT_NOACTION
) == 0 &&
575 pf_opt_create_table(pf
, p1
->por_src_tbl
))
580 if (pf
->opts
& PF_OPT_VERBOSE
)
581 print_tabledef(p1
->por_src_tbl
->pt_name
,
583 &p1
->por_src_tbl
->pt_nodes
);
585 memset(&p1
->por_rule
.src
.addr
, 0,
586 sizeof(p1
->por_rule
.src
.addr
));
587 p1
->por_rule
.src
.addr
.type
= PF_ADDR_TABLE
;
588 strlcpy(p1
->por_rule
.src
.addr
.v
.tblname
,
589 p1
->por_src_tbl
->pt_name
,
590 sizeof(p1
->por_rule
.src
.addr
.v
.tblname
));
592 pfr_buf_clear(p1
->por_src_tbl
->pt_buf
);
593 free(p1
->por_src_tbl
->pt_buf
);
594 p1
->por_src_tbl
->pt_buf
= NULL
;
596 if (p1
->por_dst_tbl
&& p1
->por_dst_tbl
->pt_rulecount
>=
598 if (p1
->por_dst_tbl
->pt_generated
) {
599 /* This rule is included in a table */
600 TAILQ_REMOVE(&block
->sb_rules
, p1
, por_entry
);
604 p1
->por_dst_tbl
->pt_generated
= 1;
606 if ((pf
->opts
& PF_OPT_NOACTION
) == 0 &&
607 pf_opt_create_table(pf
, p1
->por_dst_tbl
))
611 if (pf
->opts
& PF_OPT_VERBOSE
)
612 print_tabledef(p1
->por_dst_tbl
->pt_name
,
614 &p1
->por_dst_tbl
->pt_nodes
);
616 memset(&p1
->por_rule
.dst
.addr
, 0,
617 sizeof(p1
->por_rule
.dst
.addr
));
618 p1
->por_rule
.dst
.addr
.type
= PF_ADDR_TABLE
;
619 strlcpy(p1
->por_rule
.dst
.addr
.v
.tblname
,
620 p1
->por_dst_tbl
->pt_name
,
621 sizeof(p1
->por_rule
.dst
.addr
.v
.tblname
));
623 pfr_buf_clear(p1
->por_dst_tbl
->pt_buf
);
624 free(p1
->por_dst_tbl
->pt_buf
);
625 p1
->por_dst_tbl
->pt_buf
= NULL
;
634 * Optimization pass #3: re-order rules to improve skip steps
637 reorder_rules(struct pfctl
*pf
, struct superblock
*block
, int depth
)
639 struct superblock
*newblock
;
640 struct pf_skip_step
*skiplist
;
641 struct pf_opt_rule
*por
;
642 int i
, largest
, largest_list
, rule_count
= 0;
643 TAILQ_HEAD( , pf_opt_rule
) head
;
646 * Calculate the best-case skip steps. We put each rule in a list
647 * of other rules with common fields
649 for (i
= 0; i
< PF_SKIP_COUNT
; i
++) {
650 TAILQ_FOREACH(por
, &block
->sb_rules
, por_entry
) {
651 TAILQ_FOREACH(skiplist
, &block
->sb_skipsteps
[i
],
653 if (skip_compare(i
, skiplist
, por
) == 0)
656 if (skiplist
== NULL
) {
657 if ((skiplist
= calloc(1, sizeof(*skiplist
))) ==
660 TAILQ_INIT(&skiplist
->ps_rules
);
661 TAILQ_INSERT_TAIL(&block
->sb_skipsteps
[i
],
664 skip_append(block
, i
, skiplist
, por
);
668 TAILQ_FOREACH(por
, &block
->sb_rules
, por_entry
)
672 * Now we're going to ignore any fields that are identical between
673 * all of the rules in the superblock and those fields which differ
674 * between every rule in the superblock.
677 for (i
= 0; i
< PF_SKIP_COUNT
; i
++) {
678 skiplist
= TAILQ_FIRST(&block
->sb_skipsteps
[i
]);
679 if (skiplist
->ps_count
== rule_count
) {
680 DEBUG("(%d) original skipstep '%s' is all rules",
681 depth
, skip_comparitors_names
[i
]);
682 skiplist
->ps_count
= 0;
683 } else if (skiplist
->ps_count
== 1) {
684 skiplist
->ps_count
= 0;
686 DEBUG("(%d) original skipstep '%s' largest jump is %d",
687 depth
, skip_comparitors_names
[i
],
689 if (skiplist
->ps_count
> largest
)
690 largest
= skiplist
->ps_count
;
694 /* Ugh. There is NO commonality in the superblock on which
695 * optimize the skipsteps optimization.
701 * Now we're going to empty the superblock rule list and re-create
702 * it based on a more optimal skipstep order.
705 while ((por
= TAILQ_FIRST(&block
->sb_rules
))) {
706 TAILQ_REMOVE(&block
->sb_rules
, por
, por_entry
);
707 TAILQ_INSERT_TAIL(&head
, por
, por_entry
);
711 while (!TAILQ_EMPTY(&head
)) {
715 * Find the most useful skip steps remaining
717 for (i
= 0; i
< PF_SKIP_COUNT
; i
++) {
718 skiplist
= TAILQ_FIRST(&block
->sb_skipsteps
[i
]);
719 if (skiplist
->ps_count
> largest
) {
720 largest
= skiplist
->ps_count
;
727 * Nothing useful left. Leave remaining rules in order.
729 DEBUG("(%d) no more commonality for skip steps", depth
);
730 while ((por
= TAILQ_FIRST(&head
))) {
731 TAILQ_REMOVE(&head
, por
, por_entry
);
732 TAILQ_INSERT_TAIL(&block
->sb_rules
, por
,
737 * There is commonality. Extract those common rules
738 * and place them in the ruleset adjacent to each
741 skiplist
= TAILQ_FIRST(&block
->sb_skipsteps
[
743 DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d",
744 depth
, skip_comparitors_names
[largest_list
],
745 largest
, TAILQ_FIRST(&TAILQ_FIRST(&block
->
746 sb_skipsteps
[largest_list
])->ps_rules
)->
748 TAILQ_REMOVE(&block
->sb_skipsteps
[largest_list
],
753 * There may be further commonality inside these
754 * rules. So we'll split them off into they're own
755 * superblock and pass it back into the optimizer.
757 if (skiplist
->ps_count
> 2) {
758 if ((newblock
= calloc(1, sizeof(*newblock
)))
763 TAILQ_INIT(&newblock
->sb_rules
);
764 for (i
= 0; i
< PF_SKIP_COUNT
; i
++)
765 TAILQ_INIT(&newblock
->sb_skipsteps
[i
]);
766 TAILQ_INSERT_BEFORE(block
, newblock
, sb_entry
);
767 DEBUG("(%d) splitting off %d rules from superblock @ #%d",
768 depth
, skiplist
->ps_count
,
769 TAILQ_FIRST(&skiplist
->ps_rules
)->
775 while ((por
= TAILQ_FIRST(&skiplist
->ps_rules
))) {
776 TAILQ_REMOVE(&head
, por
, por_entry
);
777 TAILQ_REMOVE(&skiplist
->ps_rules
, por
,
778 por_skip_entry
[largest_list
]);
779 TAILQ_INSERT_TAIL(&newblock
->sb_rules
, por
,
782 /* Remove this rule from all other skiplists */
783 remove_from_skipsteps(&block
->sb_skipsteps
[
784 largest_list
], block
, por
, skiplist
);
787 if (newblock
!= block
)
788 if (reorder_rules(pf
, newblock
, depth
+ 1))
794 for (i
= 0; i
< PF_SKIP_COUNT
; i
++) {
795 while ((skiplist
= TAILQ_FIRST(&block
->sb_skipsteps
[i
]))) {
796 TAILQ_REMOVE(&block
->sb_skipsteps
[i
], skiplist
,
807 * Optimization pass #4: re-order 'quick' rules based on feedback from the
808 * currently running ruleset
811 block_feedback(struct pfctl
*pf
, struct superblock
*block
)
813 TAILQ_HEAD( , pf_opt_rule
) queue
;
814 struct pf_opt_rule
*por1
, *por2
;
815 u_int64_t total_count
= 0;
820 * Walk through all of the profiled superblock's rules and copy
821 * the counters onto our rules.
823 TAILQ_FOREACH(por1
, &block
->sb_profiled_block
->sb_rules
, por_entry
) {
824 comparable_rule(&a
, &por1
->por_rule
, DC
);
825 total_count
+= por1
->por_rule
.packets
[0] +
826 por1
->por_rule
.packets
[1];
827 TAILQ_FOREACH(por2
, &block
->sb_rules
, por_entry
) {
828 if (por2
->por_profile_count
)
830 comparable_rule(&b
, &por2
->por_rule
, DC
);
831 if (memcmp(&a
, &b
, sizeof(a
)) == 0) {
832 por2
->por_profile_count
=
833 por1
->por_rule
.packets
[0] +
834 por1
->por_rule
.packets
[1];
839 superblock_free(pf
, block
->sb_profiled_block
);
840 block
->sb_profiled_block
= NULL
;
843 * Now we pull all of the rules off the superblock and re-insert them
848 while ((por1
= TAILQ_FIRST(&block
->sb_rules
)) != NULL
) {
849 TAILQ_REMOVE(&block
->sb_rules
, por1
, por_entry
);
850 TAILQ_INSERT_TAIL(&queue
, por1
, por_entry
);
853 while ((por1
= TAILQ_FIRST(&queue
)) != NULL
) {
854 TAILQ_REMOVE(&queue
, por1
, por_entry
);
855 /* XXX I should sort all of the unused rules based on skip steps */
856 TAILQ_FOREACH(por2
, &block
->sb_rules
, por_entry
) {
857 if (por1
->por_profile_count
> por2
->por_profile_count
) {
858 TAILQ_INSERT_BEFORE(por2
, por1
, por_entry
);
863 TAILQ_INSERT_TAIL(&block
->sb_rules
, por1
, por_entry
);
871 * Load the current ruleset from the kernel and try to associate them with
872 * the ruleset we're optimizing.
875 load_feedback_profile(struct pfctl
*pf
, struct superblocks
*superblocks
)
877 struct superblock
*block
, *blockcur
;
878 struct superblocks prof_superblocks
;
879 struct pf_opt_rule
*por
;
880 struct pf_opt_queue queue
;
881 struct pfioc_rule pr
;
886 TAILQ_INIT(&prof_superblocks
);
888 memset(&pr
, 0, sizeof(pr
));
889 pr
.rule
.action
= PF_PASS
;
890 if (ioctl(pf
->dev
, DIOCGETRULES
, &pr
)) {
891 warn("DIOCGETRULES");
896 DEBUG("Loading %d active rules for a feedback profile", mnr
);
897 for (nr
= 0; nr
< mnr
; ++nr
) {
898 struct pf_ruleset
*rs
;
899 if ((por
= calloc(1, sizeof(*por
))) == NULL
) {
904 if (ioctl(pf
->dev
, DIOCGETRULE
, &pr
)) {
905 warn("DIOCGETRULES");
908 memcpy(&por
->por_rule
, &pr
.rule
, sizeof(por
->por_rule
));
909 rs
= pf_find_or_create_ruleset(pr
.anchor_call
);
910 por
->por_rule
.anchor
= rs
->anchor
;
911 if (TAILQ_EMPTY(&por
->por_rule
.rpool
.list
))
912 memset(&por
->por_rule
.rpool
, 0,
913 sizeof(por
->por_rule
.rpool
));
914 TAILQ_INSERT_TAIL(&queue
, por
, por_entry
);
916 /* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket,
917 * PF_PASS, pf->anchor) ???
918 * ... pfctl_clear_pool(&pr.rule.rpool)
922 if (construct_superblocks(pf
, &queue
, &prof_superblocks
))
927 * Now we try to associate the active ruleset's superblocks with
928 * the superblocks we're compiling.
930 block
= TAILQ_FIRST(superblocks
);
931 blockcur
= TAILQ_FIRST(&prof_superblocks
);
932 while (block
&& blockcur
) {
933 comparable_rule(&a
, &TAILQ_FIRST(&block
->sb_rules
)->por_rule
,
935 comparable_rule(&b
, &TAILQ_FIRST(&blockcur
->sb_rules
)->por_rule
,
937 if (memcmp(&a
, &b
, sizeof(a
)) == 0) {
938 /* The two superblocks lined up */
939 block
->sb_profiled_block
= blockcur
;
941 DEBUG("superblocks don't line up between #%d and #%d",
942 TAILQ_FIRST(&block
->sb_rules
)->por_rule
.nr
,
943 TAILQ_FIRST(&blockcur
->sb_rules
)->por_rule
.nr
);
946 block
= TAILQ_NEXT(block
, sb_entry
);
947 blockcur
= TAILQ_NEXT(blockcur
, sb_entry
);
952 /* Free any superblocks we couldn't link */
954 block
= TAILQ_NEXT(blockcur
, sb_entry
);
955 superblock_free(pf
, blockcur
);
963 * Compare a rule to a skiplist to see if the rule is a member
966 skip_compare(int skipnum
, struct pf_skip_step
*skiplist
,
967 struct pf_opt_rule
*por
)
969 struct pf_rule
*a
, *b
;
970 if (skipnum
>= PF_SKIP_COUNT
|| skipnum
< 0)
971 errx(1, "skip_compare() out of bounds");
973 b
= &TAILQ_FIRST(&skiplist
->ps_rules
)->por_rule
;
975 return ((skip_comparitors
[skipnum
])(a
, b
));
980 * Add a rule to a skiplist
983 skip_append(struct superblock
*superblock
, int skipnum
,
984 struct pf_skip_step
*skiplist
, struct pf_opt_rule
*por
)
986 struct pf_skip_step
*prev
;
988 skiplist
->ps_count
++;
989 TAILQ_INSERT_TAIL(&skiplist
->ps_rules
, por
, por_skip_entry
[skipnum
]);
991 /* Keep the list of skiplists sorted by whichever is larger */
992 while ((prev
= TAILQ_PREV(skiplist
, skiplist
, ps_entry
)) &&
993 prev
->ps_count
< skiplist
->ps_count
) {
994 TAILQ_REMOVE(&superblock
->sb_skipsteps
[skipnum
],
996 TAILQ_INSERT_BEFORE(prev
, skiplist
, ps_entry
);
1002 * Remove a rule from the other skiplist calculations.
1005 remove_from_skipsteps(struct skiplist
*head
, struct superblock
*block
,
1006 struct pf_opt_rule
*por
, struct pf_skip_step
*active_list
)
1008 struct pf_skip_step
*sk
, *next
;
1009 struct pf_opt_rule
*p2
;
1012 for (i
= 0; i
< PF_SKIP_COUNT
; i
++) {
1013 sk
= TAILQ_FIRST(&block
->sb_skipsteps
[i
]);
1014 if (sk
== NULL
|| sk
== active_list
|| sk
->ps_count
<= 1)
1018 TAILQ_FOREACH(p2
, &sk
->ps_rules
, por_skip_entry
[i
])
1020 TAILQ_REMOVE(&sk
->ps_rules
, p2
,
1026 } while (!found
&& (sk
= TAILQ_NEXT(sk
, ps_entry
)));
1028 /* Does this change the sorting order? */
1029 while ((next
= TAILQ_NEXT(sk
, ps_entry
)) &&
1030 next
->ps_count
> sk
->ps_count
) {
1031 TAILQ_REMOVE(head
, sk
, ps_entry
);
1032 TAILQ_INSERT_AFTER(head
, next
, sk
, ps_entry
);
1035 next
= TAILQ_NEXT(sk
, ps_entry
);
1036 assert(next
== NULL
|| next
->ps_count
<= sk
->ps_count
);
1037 #endif /* OPT_DEBUG */
1043 /* Compare two rules AF field for skiplist construction */
1045 skip_cmp_af(struct pf_rule
*a
, struct pf_rule
*b
)
1047 if (a
->af
!= b
->af
|| a
->af
== 0)
1052 /* Compare two rules DIRECTION field for skiplist construction */
1054 skip_cmp_dir(struct pf_rule
*a
, struct pf_rule
*b
)
1056 if (a
->direction
== 0 || a
->direction
!= b
->direction
)
1061 /* Compare two rules DST Address field for skiplist construction */
1063 skip_cmp_dst_addr(struct pf_rule
*a
, struct pf_rule
*b
)
1065 if (a
->dst
.neg
!= b
->dst
.neg
||
1066 a
->dst
.addr
.type
!= b
->dst
.addr
.type
)
1068 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1069 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1070 * a->proto == IPPROTO_ICMP
1073 switch (a
->dst
.addr
.type
) {
1074 case PF_ADDR_ADDRMASK
:
1075 if (memcmp(&a
->dst
.addr
.v
.a
.addr
, &b
->dst
.addr
.v
.a
.addr
,
1076 sizeof(a
->dst
.addr
.v
.a
.addr
)) ||
1077 memcmp(&a
->dst
.addr
.v
.a
.mask
, &b
->dst
.addr
.v
.a
.mask
,
1078 sizeof(a
->dst
.addr
.v
.a
.mask
)) ||
1079 (a
->dst
.addr
.v
.a
.addr
.addr32
[0] == 0 &&
1080 a
->dst
.addr
.v
.a
.addr
.addr32
[1] == 0 &&
1081 a
->dst
.addr
.v
.a
.addr
.addr32
[2] == 0 &&
1082 a
->dst
.addr
.v
.a
.addr
.addr32
[3] == 0))
1085 case PF_ADDR_DYNIFTL
:
1086 if (strcmp(a
->dst
.addr
.v
.ifname
, b
->dst
.addr
.v
.ifname
) != 0 ||
1087 a
->dst
.addr
.iflags
!= b
->dst
.addr
.iflags
||
1088 memcmp(&a
->dst
.addr
.v
.a
.mask
, &b
->dst
.addr
.v
.a
.mask
,
1089 sizeof(a
->dst
.addr
.v
.a
.mask
)))
1092 case PF_ADDR_NOROUTE
:
1093 case PF_ADDR_URPFFAILED
:
1096 return (strcmp(a
->dst
.addr
.v
.tblname
, b
->dst
.addr
.v
.tblname
));
1101 /* Compare two rules DST port field for skiplist construction */
1103 skip_cmp_dst_port(struct pf_rule
*a
, struct pf_rule
*b
)
1105 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1106 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1107 * a->proto == IPPROTO_ICMP
1110 if (a
->dst
.port_op
== PF_OP_NONE
|| a
->dst
.port_op
!= b
->dst
.port_op
||
1111 a
->dst
.port
[0] != b
->dst
.port
[0] ||
1112 a
->dst
.port
[1] != b
->dst
.port
[1])
1117 /* Compare two rules IFP field for skiplist construction */
1119 skip_cmp_ifp(struct pf_rule
*a
, struct pf_rule
*b
)
1121 if (strcmp(a
->ifname
, b
->ifname
) || a
->ifname
[0] == '\0')
1123 return (a
->ifnot
!= b
->ifnot
);
1126 /* Compare two rules PROTO field for skiplist construction */
1128 skip_cmp_proto(struct pf_rule
*a
, struct pf_rule
*b
)
1130 return (a
->proto
!= b
->proto
|| a
->proto
== 0);
1133 /* Compare two rules SRC addr field for skiplist construction */
1135 skip_cmp_src_addr(struct pf_rule
*a
, struct pf_rule
*b
)
1137 if (a
->src
.neg
!= b
->src
.neg
||
1138 a
->src
.addr
.type
!= b
->src
.addr
.type
)
1140 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1141 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1142 * a->proto == IPPROTO_ICMP
1145 switch (a
->src
.addr
.type
) {
1146 case PF_ADDR_ADDRMASK
:
1147 if (memcmp(&a
->src
.addr
.v
.a
.addr
, &b
->src
.addr
.v
.a
.addr
,
1148 sizeof(a
->src
.addr
.v
.a
.addr
)) ||
1149 memcmp(&a
->src
.addr
.v
.a
.mask
, &b
->src
.addr
.v
.a
.mask
,
1150 sizeof(a
->src
.addr
.v
.a
.mask
)) ||
1151 (a
->src
.addr
.v
.a
.addr
.addr32
[0] == 0 &&
1152 a
->src
.addr
.v
.a
.addr
.addr32
[1] == 0 &&
1153 a
->src
.addr
.v
.a
.addr
.addr32
[2] == 0 &&
1154 a
->src
.addr
.v
.a
.addr
.addr32
[3] == 0))
1157 case PF_ADDR_DYNIFTL
:
1158 if (strcmp(a
->src
.addr
.v
.ifname
, b
->src
.addr
.v
.ifname
) != 0 ||
1159 a
->src
.addr
.iflags
!= b
->src
.addr
.iflags
||
1160 memcmp(&a
->src
.addr
.v
.a
.mask
, &b
->src
.addr
.v
.a
.mask
,
1161 sizeof(a
->src
.addr
.v
.a
.mask
)))
1164 case PF_ADDR_NOROUTE
:
1165 case PF_ADDR_URPFFAILED
:
1168 return (strcmp(a
->src
.addr
.v
.tblname
, b
->src
.addr
.v
.tblname
));
1173 /* Compare two rules SRC port field for skiplist construction */
1175 skip_cmp_src_port(struct pf_rule
*a
, struct pf_rule
*b
)
1177 if (a
->src
.port_op
== PF_OP_NONE
|| a
->src
.port_op
!= b
->src
.port_op
||
1178 a
->src
.port
[0] != b
->src
.port
[0] ||
1179 a
->src
.port
[1] != b
->src
.port
[1])
1181 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1182 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1183 * a->proto == IPPROTO_ICMP
1196 int (*func
)(struct pf_rule
*, struct pf_rule
*);
1197 } comps
[] = PF_SKIP_COMPARITORS
;
1200 for (skipnum
= 0; skipnum
< PF_SKIP_COUNT
; skipnum
++) {
1201 for (i
= 0; i
< sizeof(comps
)/sizeof(*comps
); i
++)
1202 if (comps
[i
].skipnum
== skipnum
) {
1203 skip_comparitors
[skipnum
] = comps
[i
].func
;
1204 skip_comparitors_names
[skipnum
] = comps
[i
].name
;
1207 for (skipnum
= 0; skipnum
< PF_SKIP_COUNT
; skipnum
++)
1208 if (skip_comparitors
[skipnum
] == NULL
)
1209 errx(1, "Need to add skip step comparitor to pfctl?!");
1213 * Add a host/netmask to a table
1216 add_opt_table(struct pfctl
*pf
, struct pf_opt_tbl
**tbl
, sa_family_t af
,
1217 struct pf_rule_addr
*addr
)
1221 #endif /* OPT_DEBUG */
1222 static int tablenum
= 0;
1223 struct node_host node_host
;
1226 if ((*tbl
= calloc(1, sizeof(**tbl
))) == NULL
||
1227 ((*tbl
)->pt_buf
= calloc(1, sizeof(*(*tbl
)->pt_buf
))) ==
1230 (*tbl
)->pt_buf
->pfrb_type
= PFRB_ADDRS
;
1231 SIMPLEQ_INIT(&(*tbl
)->pt_nodes
);
1233 /* This is just a temporary table name */
1234 snprintf((*tbl
)->pt_name
, sizeof((*tbl
)->pt_name
), "%s%d",
1235 PF_OPT_TABLE_PREFIX
, tablenum
++);
1236 DEBUG("creating table <%s>", (*tbl
)->pt_name
);
1239 memset(&node_host
, 0, sizeof(node_host
));
1241 node_host
.addr
= addr
->addr
;
1244 DEBUG("<%s> adding %s/%d", (*tbl
)->pt_name
, inet_ntop(af
,
1245 &node_host
.addr
.v
.a
.addr
, buf
, sizeof(buf
)),
1246 unmask(&node_host
.addr
.v
.a
.mask
, af
));
1247 #endif /* OPT_DEBUG */
1249 if (append_addr_host((*tbl
)->pt_buf
, &node_host
, 0, 0)) {
1250 warn("failed to add host");
1253 if (pf
->opts
& PF_OPT_VERBOSE
) {
1254 struct node_tinit
*ti
;
1256 if ((ti
= calloc(1, sizeof(*ti
))) == NULL
)
1258 if ((ti
->host
= malloc(sizeof(*ti
->host
))) == NULL
)
1260 memcpy(ti
->host
, &node_host
, sizeof(*ti
->host
));
1261 SIMPLEQ_INSERT_TAIL(&(*tbl
)->pt_nodes
, ti
, entries
);
1264 (*tbl
)->pt_rulecount
++;
1265 if ((*tbl
)->pt_rulecount
== TABLE_THRESHOLD
)
1266 DEBUG("table <%s> now faster than skip steps", (*tbl
)->pt_name
);
1273 * Do the dirty work of choosing an unused table name and creating it.
1274 * (be careful with the table name, it might already be used in another anchor)
1277 pf_opt_create_table(struct pfctl
*pf
, struct pf_opt_tbl
*tbl
)
1279 static int tablenum
;
1280 const struct pfr_table
*t
;
1282 if (table_buffer
.pfrb_type
== 0) {
1283 /* Initialize the list of tables */
1284 table_buffer
.pfrb_type
= PFRB_TABLES
;
1286 pfr_buf_grow(&table_buffer
, table_buffer
.pfrb_size
);
1287 table_buffer
.pfrb_size
= table_buffer
.pfrb_msize
;
1288 if (pfr_get_tables(NULL
, table_buffer
.pfrb_caddr
,
1289 &table_buffer
.pfrb_size
, PFR_FLAG_ALLRSETS
))
1290 err(1, "pfr_get_tables");
1291 if (table_buffer
.pfrb_size
<= table_buffer
.pfrb_msize
)
1294 table_identifier
= arc4random();
1297 /* XXX would be *really* nice to avoid duplicating identical tables */
1299 /* Now we have to pick a table name that isn't used */
1301 DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl
->pt_name
,
1302 PF_OPT_TABLE_PREFIX
, table_identifier
, tablenum
);
1303 snprintf(tbl
->pt_name
, sizeof(tbl
->pt_name
), "%s%x_%d",
1304 PF_OPT_TABLE_PREFIX
, table_identifier
, tablenum
);
1305 PFRB_FOREACH(t
, &table_buffer
) {
1306 if (strcasecmp(t
->pfrt_name
, tbl
->pt_name
) == 0) {
1307 /* Collision. Try again */
1308 DEBUG("wow, table <%s> in use. trying again",
1310 table_identifier
= arc4random();
1317 if (pfctl_define_table(tbl
->pt_name
, PFR_TFLAG_CONST
, 1,
1318 pf
->astack
[0]->name
, tbl
->pt_buf
, pf
->astack
[0]->ruleset
.tticket
)) {
1319 warn("failed to create table %s in %s",
1320 tbl
->pt_name
, pf
->astack
[0]->name
);
1327 * Partition the flat ruleset into a list of distinct superblocks
1330 construct_superblocks(struct pfctl
*pf
, struct pf_opt_queue
*opt_queue
,
1331 struct superblocks
*superblocks
)
1333 struct superblock
*block
= NULL
;
1334 struct pf_opt_rule
*por
;
1337 while (!TAILQ_EMPTY(opt_queue
)) {
1338 por
= TAILQ_FIRST(opt_queue
);
1339 TAILQ_REMOVE(opt_queue
, por
, por_entry
);
1340 if (block
== NULL
|| !superblock_inclusive(block
, por
)) {
1341 if ((block
= calloc(1, sizeof(*block
))) == NULL
) {
1345 TAILQ_INIT(&block
->sb_rules
);
1346 for (i
= 0; i
< PF_SKIP_COUNT
; i
++)
1347 TAILQ_INIT(&block
->sb_skipsteps
[i
]);
1348 TAILQ_INSERT_TAIL(superblocks
, block
, sb_entry
);
1350 TAILQ_INSERT_TAIL(&block
->sb_rules
, por
, por_entry
);
1358 * Compare two rule addresses
1361 addrs_equal(struct pf_rule_addr
*a
, struct pf_rule_addr
*b
)
1363 if (a
->neg
!= b
->neg
)
1365 return (memcmp(&a
->addr
, &b
->addr
, sizeof(a
->addr
)) == 0);
1370 * The addresses are not equal, but can we combine them into one table?
1373 addrs_combineable(struct pf_rule_addr
*a
, struct pf_rule_addr
*b
)
1375 if (a
->addr
.type
!= PF_ADDR_ADDRMASK
||
1376 b
->addr
.type
!= PF_ADDR_ADDRMASK
)
1378 if (a
->neg
!= b
->neg
|| a
->port_op
!= b
->port_op
||
1379 a
->port
[0] != b
->port
[0] || a
->port
[1] != b
->port
[1])
1386 * Are we allowed to combine these two rules
1389 rules_combineable(struct pf_rule
*p1
, struct pf_rule
*p2
)
1391 struct pf_rule a
, b
;
1393 comparable_rule(&a
, p1
, COMBINED
);
1394 comparable_rule(&b
, p2
, COMBINED
);
1395 return (memcmp(&a
, &b
, sizeof(a
)) == 0);
1400 * Can a rule be included inside a superblock
1403 superblock_inclusive(struct superblock
*block
, struct pf_opt_rule
*por
)
1405 struct pf_rule a
, b
;
1408 /* First check for hard breaks */
1409 for (i
= 0; i
< sizeof(pf_rule_desc
)/sizeof(*pf_rule_desc
); i
++) {
1410 if (pf_rule_desc
[i
].prf_type
== BARRIER
) {
1411 for (j
= 0; j
< pf_rule_desc
[i
].prf_size
; j
++)
1412 if (((char *)&por
->por_rule
)[j
+
1413 pf_rule_desc
[i
].prf_offset
] != 0)
1418 /* per-rule src-track is also a hard break */
1419 if (por
->por_rule
.rule_flag
& PFRULE_RULESRCTRACK
)
1423 * Have to handle interface groups separately. Consider the following
1425 * block on EXTIFS to any port 22
1426 * pass on em0 to any port 22
1427 * (where EXTIFS is an arbitrary interface group)
1428 * The optimizer may decide to re-order the pass rule in front of the
1429 * block rule. But what if EXTIFS includes em0??? Such a reordering
1430 * would change the meaning of the ruleset.
1431 * We can't just lookup the EXTIFS group and check if em0 is a member
1432 * because the user is allowed to add interfaces to a group during
1434 * Ergo interface groups become a defacto superblock break :-(
1436 if (interface_group(por
->por_rule
.ifname
) ||
1437 interface_group(TAILQ_FIRST(&block
->sb_rules
)->por_rule
.ifname
)) {
1438 if (strcasecmp(por
->por_rule
.ifname
,
1439 TAILQ_FIRST(&block
->sb_rules
)->por_rule
.ifname
) != 0)
1443 comparable_rule(&a
, &TAILQ_FIRST(&block
->sb_rules
)->por_rule
, NOMERGE
);
1444 comparable_rule(&b
, &por
->por_rule
, NOMERGE
);
1445 if (memcmp(&a
, &b
, sizeof(a
)) == 0)
1449 for (i
= 0; i
< sizeof(por
->por_rule
); i
++) {
1451 if (((u_int8_t
*)&a
)[i
] != ((u_int8_t
*)&b
)[i
]) {
1452 for (j
= 0; j
< sizeof(pf_rule_desc
) /
1453 sizeof(*pf_rule_desc
); j
++) {
1454 if (i
>= pf_rule_desc
[j
].prf_offset
&&
1455 i
< pf_rule_desc
[j
].prf_offset
+
1456 pf_rule_desc
[j
].prf_size
) {
1457 DEBUG("superblock break @ %d due to %s",
1459 pf_rule_desc
[j
].prf_name
);
1462 if (i
> pf_rule_desc
[j
].prf_offset
) {
1463 if (closest
== -1 ||
1464 i
-pf_rule_desc
[j
].prf_offset
<
1465 i
-pf_rule_desc
[closest
].prf_offset
)
1471 DEBUG("superblock break @ %d on %s+%lxh",
1473 pf_rule_desc
[closest
].prf_name
,
1474 i
- pf_rule_desc
[closest
].prf_offset
-
1475 pf_rule_desc
[closest
].prf_size
);
1477 DEBUG("superblock break @ %d on field @ %d",
1478 por
->por_rule
.nr
, i
);
1482 #endif /* OPT_DEBUG */
1489 * Figure out if an interface name is an actual interface or actually a
1490 * group of interfaces.
1493 interface_group(const char *ifname
)
1495 if (ifname
== NULL
|| !ifname
[0])
1498 /* Real interfaces must end in a number, interface groups do not */
1499 if (isdigit(ifname
[strlen(ifname
) - 1]))
1507 * Make a rule that can directly compared by memcmp()
1510 comparable_rule(struct pf_rule
*dst
, const struct pf_rule
*src
, int type
)
1514 * To simplify the comparison, we just zero out the fields that are
1515 * allowed to be different and then do a simple memcmp()
1517 memcpy(dst
, src
, sizeof(*dst
));
1518 for (i
= 0; i
< sizeof(pf_rule_desc
)/sizeof(*pf_rule_desc
); i
++)
1519 if (pf_rule_desc
[i
].prf_type
>= type
) {
1521 assert(pf_rule_desc
[i
].prf_type
!= NEVER
||
1522 *(((char *)dst
) + pf_rule_desc
[i
].prf_offset
) == 0);
1523 #endif /* OPT_DEBUG */
1524 memset(((char *)dst
) + pf_rule_desc
[i
].prf_offset
, 0,
1525 pf_rule_desc
[i
].prf_size
);
1531 * Remove superset information from two rules so we can directly compare them
1535 exclude_supersets(struct pf_rule
*super
, struct pf_rule
*sub
)
1537 if (super
->ifname
[0] == '\0')
1538 memset(sub
->ifname
, 0, sizeof(sub
->ifname
));
1539 if (super
->direction
== PF_INOUT
)
1540 sub
->direction
= PF_INOUT
;
1541 if ((super
->proto
== 0 || super
->proto
== sub
->proto
) &&
1542 super
->flags
== 0 && super
->flagset
== 0 && (sub
->flags
||
1544 sub
->flags
= super
->flags
;
1545 sub
->flagset
= super
->flagset
;
1547 if (super
->proto
== 0)
1550 if (super
->src
.port_op
== 0) {
1551 sub
->src
.port_op
= 0;
1552 sub
->src
.port
[0] = 0;
1553 sub
->src
.port
[1] = 0;
1555 if (super
->dst
.port_op
== 0) {
1556 sub
->dst
.port_op
= 0;
1557 sub
->dst
.port
[0] = 0;
1558 sub
->dst
.port
[1] = 0;
1561 if (super
->src
.addr
.type
== PF_ADDR_ADDRMASK
&& !super
->src
.neg
&&
1562 !sub
->src
.neg
&& super
->src
.addr
.v
.a
.mask
.addr32
[0] == 0 &&
1563 super
->src
.addr
.v
.a
.mask
.addr32
[1] == 0 &&
1564 super
->src
.addr
.v
.a
.mask
.addr32
[2] == 0 &&
1565 super
->src
.addr
.v
.a
.mask
.addr32
[3] == 0)
1566 memset(&sub
->src
.addr
, 0, sizeof(sub
->src
.addr
));
1567 else if (super
->src
.addr
.type
== PF_ADDR_ADDRMASK
&&
1568 sub
->src
.addr
.type
== PF_ADDR_ADDRMASK
&&
1569 super
->src
.neg
== sub
->src
.neg
&&
1570 super
->af
== sub
->af
&&
1571 unmask(&super
->src
.addr
.v
.a
.mask
, super
->af
) <
1572 unmask(&sub
->src
.addr
.v
.a
.mask
, sub
->af
) &&
1573 super
->src
.addr
.v
.a
.addr
.addr32
[0] ==
1574 (sub
->src
.addr
.v
.a
.addr
.addr32
[0] &
1575 super
->src
.addr
.v
.a
.mask
.addr32
[0]) &&
1576 super
->src
.addr
.v
.a
.addr
.addr32
[1] ==
1577 (sub
->src
.addr
.v
.a
.addr
.addr32
[1] &
1578 super
->src
.addr
.v
.a
.mask
.addr32
[1]) &&
1579 super
->src
.addr
.v
.a
.addr
.addr32
[2] ==
1580 (sub
->src
.addr
.v
.a
.addr
.addr32
[2] &
1581 super
->src
.addr
.v
.a
.mask
.addr32
[2]) &&
1582 super
->src
.addr
.v
.a
.addr
.addr32
[3] ==
1583 (sub
->src
.addr
.v
.a
.addr
.addr32
[3] &
1584 super
->src
.addr
.v
.a
.mask
.addr32
[3])) {
1585 /* sub->src.addr is a subset of super->src.addr/mask */
1586 memcpy(&sub
->src
.addr
, &super
->src
.addr
, sizeof(sub
->src
.addr
));
1589 if (super
->dst
.addr
.type
== PF_ADDR_ADDRMASK
&& !super
->dst
.neg
&&
1590 !sub
->dst
.neg
&& super
->dst
.addr
.v
.a
.mask
.addr32
[0] == 0 &&
1591 super
->dst
.addr
.v
.a
.mask
.addr32
[1] == 0 &&
1592 super
->dst
.addr
.v
.a
.mask
.addr32
[2] == 0 &&
1593 super
->dst
.addr
.v
.a
.mask
.addr32
[3] == 0)
1594 memset(&sub
->dst
.addr
, 0, sizeof(sub
->dst
.addr
));
1595 else if (super
->dst
.addr
.type
== PF_ADDR_ADDRMASK
&&
1596 sub
->dst
.addr
.type
== PF_ADDR_ADDRMASK
&&
1597 super
->dst
.neg
== sub
->dst
.neg
&&
1598 super
->af
== sub
->af
&&
1599 unmask(&super
->dst
.addr
.v
.a
.mask
, super
->af
) <
1600 unmask(&sub
->dst
.addr
.v
.a
.mask
, sub
->af
) &&
1601 super
->dst
.addr
.v
.a
.addr
.addr32
[0] ==
1602 (sub
->dst
.addr
.v
.a
.addr
.addr32
[0] &
1603 super
->dst
.addr
.v
.a
.mask
.addr32
[0]) &&
1604 super
->dst
.addr
.v
.a
.addr
.addr32
[1] ==
1605 (sub
->dst
.addr
.v
.a
.addr
.addr32
[1] &
1606 super
->dst
.addr
.v
.a
.mask
.addr32
[1]) &&
1607 super
->dst
.addr
.v
.a
.addr
.addr32
[2] ==
1608 (sub
->dst
.addr
.v
.a
.addr
.addr32
[2] &
1609 super
->dst
.addr
.v
.a
.mask
.addr32
[2]) &&
1610 super
->dst
.addr
.v
.a
.addr
.addr32
[3] ==
1611 (sub
->dst
.addr
.v
.a
.addr
.addr32
[3] &
1612 super
->dst
.addr
.v
.a
.mask
.addr32
[3])) {
1613 /* sub->dst.addr is a subset of super->dst.addr/mask */
1614 memcpy(&sub
->dst
.addr
, &super
->dst
.addr
, sizeof(sub
->dst
.addr
));
1623 superblock_free(struct pfctl
*pf
, struct superblock
*block
)
1625 struct pf_opt_rule
*por
;
1626 while ((por
= TAILQ_FIRST(&block
->sb_rules
))) {
1627 TAILQ_REMOVE(&block
->sb_rules
, por
, por_entry
);
1628 if (por
->por_src_tbl
) {
1629 if (por
->por_src_tbl
->pt_buf
) {
1630 pfr_buf_clear(por
->por_src_tbl
->pt_buf
);
1631 free(por
->por_src_tbl
->pt_buf
);
1633 free(por
->por_src_tbl
);
1635 if (por
->por_dst_tbl
) {
1636 if (por
->por_dst_tbl
->pt_buf
) {
1637 pfr_buf_clear(por
->por_dst_tbl
->pt_buf
);
1638 free(por
->por_dst_tbl
->pt_buf
);
1640 free(por
->por_dst_tbl
);
1644 if (block
->sb_profiled_block
)
1645 superblock_free(pf
, block
->sb_profiled_block
);