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