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