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 TAILQ_CONCAT(&head, &block->sb_rules, por_entry);
727
728 while (!TAILQ_EMPTY(&head)) {
729 largest = 1;
730
731 /*
732 * Find the most useful skip steps remaining
733 */
734 for (i = 0; i < PF_SKIP_COUNT; i++) {
735 skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]);
736 if (skiplist->ps_count > largest) {
737 largest = skiplist->ps_count;
738 largest_list = i;
739 }
740 }
741
742 if (largest <= 1) {
743 /*
744 * Nothing useful left. Leave remaining rules in order.
745 */
746 DEBUG("(%d) no more commonality for skip steps", depth);
747 TAILQ_CONCAT(&block->sb_rules, &head, por_entry);
748 } else {
749 /*
750 * There is commonality. Extract those common rules
751 * and place them in the ruleset adjacent to each
752 * other.
753 */
754 skiplist = TAILQ_FIRST(&block->sb_skipsteps[
755 largest_list]);
756 DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d",
757 depth, skip_comparitors_names[largest_list],
758 largest, TAILQ_FIRST(&TAILQ_FIRST(&block->
759 sb_skipsteps [largest_list])->ps_rules)->
760 por_rule.nr);
761 TAILQ_REMOVE(&block->sb_skipsteps[largest_list],
762 skiplist, ps_entry);
763
764
765 /*
766 * There may be further commonality inside these
767 * rules. So we'll split them off into they're own
768 * superblock and pass it back into the optimizer.
769 */
770 if (skiplist->ps_count > 2) {
771 if ((newblock = calloc(1, sizeof(*newblock)))
772 == NULL) {
773 warn("calloc");
774 return (1);
775 }
776 TAILQ_INIT(&newblock->sb_rules);
777 for (i = 0; i < PF_SKIP_COUNT; i++)
778 TAILQ_INIT(&newblock->sb_skipsteps[i]);
779 TAILQ_INSERT_BEFORE(block, newblock, sb_entry);
780 DEBUG("(%d) splitting off %d rules from superblock @ #%d",
781 depth, skiplist->ps_count,
782 TAILQ_FIRST(&skiplist->ps_rules)->
783 por_rule.nr);
784 } else {
785 newblock = block;
786 }
787
788 while ((por = TAILQ_FIRST(&skiplist->ps_rules))) {
789 TAILQ_REMOVE(&head, por, por_entry);
790 TAILQ_REMOVE(&skiplist->ps_rules, por,
791 por_skip_entry[largest_list]);
792 TAILQ_INSERT_TAIL(&newblock->sb_rules, por,
793 por_entry);
794
795 /* Remove this rule from all other skiplists */
796 remove_from_skipsteps(&block->sb_skipsteps[
797 largest_list], block, por, skiplist);
798 }
799 free(skiplist);
800 if (newblock != block)
801 if (reorder_rules(pf, newblock, depth + 1))
802 return (1);
803 }
804 }
805
806 done:
807 for (i = 0; i < PF_SKIP_COUNT; i++) {
808 while ((skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]))) {
809 TAILQ_REMOVE(&block->sb_skipsteps[i], skiplist,
810 ps_entry);
811 free(skiplist);
812 }
813 }
814
815 return (0);
816 }
817
818
819 /*
820 * Optimization pass #4: re-order 'quick' rules based on feedback from the
821 * currently running ruleset
822 */
823 int
block_feedback(struct pfctl * pf,struct superblock * block)824 block_feedback(struct pfctl *pf, struct superblock *block)
825 {
826 TAILQ_HEAD( , pf_opt_rule) queue;
827 struct pf_opt_rule *por1, *por2;
828 struct pfctl_rule a, b;
829
830
831 /*
832 * Walk through all of the profiled superblock's rules and copy
833 * the counters onto our rules.
834 */
835 TAILQ_FOREACH(por1, &block->sb_profiled_block->sb_rules, por_entry) {
836 comparable_rule(&a, &por1->por_rule, DC);
837 TAILQ_FOREACH(por2, &block->sb_rules, por_entry) {
838 if (por2->por_profile_count)
839 continue;
840 comparable_rule(&b, &por2->por_rule, DC);
841 if (memcmp(&a, &b, sizeof(a)) == 0) {
842 por2->por_profile_count =
843 por1->por_rule.packets[0] +
844 por1->por_rule.packets[1];
845 break;
846 }
847 }
848 }
849 superblock_free(pf, block->sb_profiled_block);
850 block->sb_profiled_block = NULL;
851
852 /*
853 * Now we pull all of the rules off the superblock and re-insert them
854 * in sorted order.
855 */
856
857 TAILQ_INIT(&queue);
858 TAILQ_CONCAT(&queue, &block->sb_rules, por_entry);
859
860 while ((por1 = TAILQ_FIRST(&queue)) != NULL) {
861 TAILQ_REMOVE(&queue, por1, por_entry);
862 /* XXX I should sort all of the unused rules based on skip steps */
863 TAILQ_FOREACH(por2, &block->sb_rules, por_entry) {
864 if (por1->por_profile_count > por2->por_profile_count) {
865 TAILQ_INSERT_BEFORE(por2, por1, por_entry);
866 break;
867 }
868 }
869 #ifdef __FreeBSD__
870 if (por2 == NULL)
871 #else
872 if (por2 == TAILQ_END(&block->sb_rules))
873 #endif
874 TAILQ_INSERT_TAIL(&block->sb_rules, por1, por_entry);
875 }
876
877 return (0);
878 }
879
880
881 /*
882 * Load the current ruleset from the kernel and try to associate them with
883 * the ruleset we're optimizing.
884 */
885 int
load_feedback_profile(struct pfctl * pf,struct superblocks * superblocks)886 load_feedback_profile(struct pfctl *pf, struct superblocks *superblocks)
887 {
888 char anchor_call[MAXPATHLEN] = "";
889 struct superblock *block, *blockcur;
890 struct superblocks prof_superblocks;
891 struct pf_opt_rule *por;
892 struct pf_opt_queue queue;
893 struct pfctl_rules_info rules;
894 struct pfctl_rule a, b, rule;
895 int nr, mnr, ret;
896
897 TAILQ_INIT(&queue);
898 TAILQ_INIT(&prof_superblocks);
899
900 if ((ret = pfctl_get_rules_info_h(pf->h, &rules, PF_PASS, "")) != 0) {
901 warnx("%s", pf_strerror(ret));
902 return (1);
903 }
904 mnr = rules.nr;
905
906 DEBUG("Loading %d active rules for a feedback profile", mnr);
907 for (nr = 0; nr < mnr; ++nr) {
908 struct pfctl_ruleset *rs;
909 if ((por = calloc(1, sizeof(*por))) == NULL) {
910 warn("calloc");
911 return (1);
912 }
913
914 if (pfctl_get_rule_h(pf->h, nr, rules.ticket, "", PF_PASS,
915 &rule, anchor_call)) {
916 warnx("%s", pf_strerror(ret));
917 free(por);
918 return (1);
919 }
920 memcpy(&por->por_rule, &rule, sizeof(por->por_rule));
921 rs = pf_find_or_create_ruleset(anchor_call);
922 por->por_rule.anchor = rs->anchor;
923 if (TAILQ_EMPTY(&por->por_rule.rdr.list))
924 memset(&por->por_rule.rdr, 0,
925 sizeof(por->por_rule.rdr));
926 if (TAILQ_EMPTY(&por->por_rule.nat.list))
927 memset(&por->por_rule.nat, 0,
928 sizeof(por->por_rule.nat));
929 TAILQ_INSERT_TAIL(&queue, por, por_entry);
930
931 /* XXX pfctl_get_pool(pf->dev, &rule.rdr, nr, pr.ticket,
932 * PF_PASS, pf->anchor) ???
933 * ... pfctl_clear_pool(&rule.rdr)
934 */
935 }
936
937 if (construct_superblocks(pf, &queue, &prof_superblocks))
938 return (1);
939
940
941 /*
942 * Now we try to associate the active ruleset's superblocks with
943 * the superblocks we're compiling.
944 */
945 block = TAILQ_FIRST(superblocks);
946 blockcur = TAILQ_FIRST(&prof_superblocks);
947 while (block && blockcur) {
948 comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule,
949 BREAK);
950 comparable_rule(&b, &TAILQ_FIRST(&blockcur->sb_rules)->por_rule,
951 BREAK);
952 if (memcmp(&a, &b, sizeof(a)) == 0) {
953 /* The two superblocks lined up */
954 block->sb_profiled_block = blockcur;
955 } else {
956 DEBUG("superblocks don't line up between #%d and #%d",
957 TAILQ_FIRST(&block->sb_rules)->por_rule.nr,
958 TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr);
959 break;
960 }
961 block = TAILQ_NEXT(block, sb_entry);
962 blockcur = TAILQ_NEXT(blockcur, sb_entry);
963 }
964
965
966
967 /* Free any superblocks we couldn't link */
968 while (blockcur) {
969 block = TAILQ_NEXT(blockcur, sb_entry);
970 superblock_free(pf, blockcur);
971 blockcur = block;
972 }
973 return (0);
974 }
975
976
977 /*
978 * Compare a rule to a skiplist to see if the rule is a member
979 */
980 int
skip_compare(int skipnum,struct pf_skip_step * skiplist,struct pf_opt_rule * por)981 skip_compare(int skipnum, struct pf_skip_step *skiplist,
982 struct pf_opt_rule *por)
983 {
984 struct pfctl_rule *a, *b;
985 if (skipnum >= PF_SKIP_COUNT || skipnum < 0)
986 errx(1, "skip_compare() out of bounds");
987 a = &por->por_rule;
988 b = &TAILQ_FIRST(&skiplist->ps_rules)->por_rule;
989
990 return ((skip_comparitors[skipnum])(a, b));
991 }
992
993
994 /*
995 * Add a rule to a skiplist
996 */
997 void
skip_append(struct superblock * superblock,int skipnum,struct pf_skip_step * skiplist,struct pf_opt_rule * por)998 skip_append(struct superblock *superblock, int skipnum,
999 struct pf_skip_step *skiplist, struct pf_opt_rule *por)
1000 {
1001 struct pf_skip_step *prev;
1002
1003 skiplist->ps_count++;
1004 TAILQ_INSERT_TAIL(&skiplist->ps_rules, por, por_skip_entry[skipnum]);
1005
1006 /* Keep the list of skiplists sorted by whichever is larger */
1007 while ((prev = TAILQ_PREV(skiplist, skiplist, ps_entry)) &&
1008 prev->ps_count < skiplist->ps_count) {
1009 TAILQ_REMOVE(&superblock->sb_skipsteps[skipnum],
1010 skiplist, ps_entry);
1011 TAILQ_INSERT_BEFORE(prev, skiplist, ps_entry);
1012 }
1013 }
1014
1015
1016 /*
1017 * Remove a rule from the other skiplist calculations.
1018 */
1019 void
remove_from_skipsteps(struct skiplist * head,struct superblock * block,struct pf_opt_rule * por,struct pf_skip_step * active_list)1020 remove_from_skipsteps(struct skiplist *head, struct superblock *block,
1021 struct pf_opt_rule *por, struct pf_skip_step *active_list)
1022 {
1023 struct pf_skip_step *sk, *next;
1024 struct pf_opt_rule *p2;
1025 int i, found;
1026
1027 for (i = 0; i < PF_SKIP_COUNT; i++) {
1028 sk = TAILQ_FIRST(&block->sb_skipsteps[i]);
1029 if (sk == NULL || sk == active_list || sk->ps_count <= 1)
1030 continue;
1031 found = 0;
1032 do {
1033 TAILQ_FOREACH(p2, &sk->ps_rules, por_skip_entry[i])
1034 if (p2 == por) {
1035 TAILQ_REMOVE(&sk->ps_rules, p2,
1036 por_skip_entry[i]);
1037 found = 1;
1038 sk->ps_count--;
1039 break;
1040 }
1041 } while (!found && (sk = TAILQ_NEXT(sk, ps_entry)));
1042 if (found && sk) {
1043 /* Does this change the sorting order? */
1044 while ((next = TAILQ_NEXT(sk, ps_entry)) &&
1045 next->ps_count > sk->ps_count) {
1046 TAILQ_REMOVE(head, sk, ps_entry);
1047 TAILQ_INSERT_AFTER(head, next, sk, ps_entry);
1048 }
1049 #ifdef OPT_DEBUG
1050 next = TAILQ_NEXT(sk, ps_entry);
1051 assert(next == NULL || next->ps_count <= sk->ps_count);
1052 #endif /* OPT_DEBUG */
1053 }
1054 }
1055 }
1056
1057
1058 /* Compare two rules AF field for skiplist construction */
1059 int
skip_cmp_af(struct pfctl_rule * a,struct pfctl_rule * b)1060 skip_cmp_af(struct pfctl_rule *a, struct pfctl_rule *b)
1061 {
1062 if (a->af != b->af || a->af == 0)
1063 return (1);
1064 return (0);
1065 }
1066
1067 /* Compare two rules DIRECTION field for skiplist construction */
1068 int
skip_cmp_dir(struct pfctl_rule * a,struct pfctl_rule * b)1069 skip_cmp_dir(struct pfctl_rule *a, struct pfctl_rule *b)
1070 {
1071 if (a->direction == 0 || a->direction != b->direction)
1072 return (1);
1073 return (0);
1074 }
1075
1076 /* Compare two rules DST Address field for skiplist construction */
1077 int
skip_cmp_dst_addr(struct pfctl_rule * a,struct pfctl_rule * b)1078 skip_cmp_dst_addr(struct pfctl_rule *a, struct pfctl_rule *b)
1079 {
1080 if (a->dst.neg != b->dst.neg ||
1081 a->dst.addr.type != b->dst.addr.type)
1082 return (1);
1083 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1084 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1085 * a->proto == IPPROTO_ICMP
1086 * return (1);
1087 */
1088 switch (a->dst.addr.type) {
1089 case PF_ADDR_ADDRMASK:
1090 if (memcmp(&a->dst.addr.v.a.addr, &b->dst.addr.v.a.addr,
1091 sizeof(a->dst.addr.v.a.addr)) ||
1092 memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask,
1093 sizeof(a->dst.addr.v.a.mask)) ||
1094 (a->dst.addr.v.a.addr.addr32[0] == 0 &&
1095 a->dst.addr.v.a.addr.addr32[1] == 0 &&
1096 a->dst.addr.v.a.addr.addr32[2] == 0 &&
1097 a->dst.addr.v.a.addr.addr32[3] == 0))
1098 return (1);
1099 return (0);
1100 case PF_ADDR_DYNIFTL:
1101 if (strcmp(a->dst.addr.v.ifname, b->dst.addr.v.ifname) != 0 ||
1102 a->dst.addr.iflags != b->dst.addr.iflags ||
1103 memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask,
1104 sizeof(a->dst.addr.v.a.mask)))
1105 return (1);
1106 return (0);
1107 case PF_ADDR_NOROUTE:
1108 case PF_ADDR_URPFFAILED:
1109 return (0);
1110 case PF_ADDR_TABLE:
1111 return (strcmp(a->dst.addr.v.tblname, b->dst.addr.v.tblname));
1112 }
1113 return (1);
1114 }
1115
1116 /* Compare two rules DST port field for skiplist construction */
1117 int
skip_cmp_dst_port(struct pfctl_rule * a,struct pfctl_rule * b)1118 skip_cmp_dst_port(struct pfctl_rule *a, struct pfctl_rule *b)
1119 {
1120 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1121 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1122 * a->proto == IPPROTO_ICMP
1123 * return (1);
1124 */
1125 if (a->dst.port_op == PF_OP_NONE || a->dst.port_op != b->dst.port_op ||
1126 a->dst.port[0] != b->dst.port[0] ||
1127 a->dst.port[1] != b->dst.port[1])
1128 return (1);
1129 return (0);
1130 }
1131
1132 /* Compare two rules IFP field for skiplist construction */
1133 int
skip_cmp_ifp(struct pfctl_rule * a,struct pfctl_rule * b)1134 skip_cmp_ifp(struct pfctl_rule *a, struct pfctl_rule *b)
1135 {
1136 if (strcmp(a->ifname, b->ifname) || a->ifname[0] == '\0')
1137 return (1);
1138 return (a->ifnot != b->ifnot);
1139 }
1140
1141 /* Compare two rules PROTO field for skiplist construction */
1142 int
skip_cmp_proto(struct pfctl_rule * a,struct pfctl_rule * b)1143 skip_cmp_proto(struct pfctl_rule *a, struct pfctl_rule *b)
1144 {
1145 return (a->proto != b->proto || a->proto == 0);
1146 }
1147
1148 /* Compare two rules SRC addr field for skiplist construction */
1149 int
skip_cmp_src_addr(struct pfctl_rule * a,struct pfctl_rule * b)1150 skip_cmp_src_addr(struct pfctl_rule *a, struct pfctl_rule *b)
1151 {
1152 if (a->src.neg != b->src.neg ||
1153 a->src.addr.type != b->src.addr.type)
1154 return (1);
1155 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1156 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1157 * a->proto == IPPROTO_ICMP
1158 * return (1);
1159 */
1160 switch (a->src.addr.type) {
1161 case PF_ADDR_ADDRMASK:
1162 if (memcmp(&a->src.addr.v.a.addr, &b->src.addr.v.a.addr,
1163 sizeof(a->src.addr.v.a.addr)) ||
1164 memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask,
1165 sizeof(a->src.addr.v.a.mask)) ||
1166 (a->src.addr.v.a.addr.addr32[0] == 0 &&
1167 a->src.addr.v.a.addr.addr32[1] == 0 &&
1168 a->src.addr.v.a.addr.addr32[2] == 0 &&
1169 a->src.addr.v.a.addr.addr32[3] == 0))
1170 return (1);
1171 return (0);
1172 case PF_ADDR_DYNIFTL:
1173 if (strcmp(a->src.addr.v.ifname, b->src.addr.v.ifname) != 0 ||
1174 a->src.addr.iflags != b->src.addr.iflags ||
1175 memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask,
1176 sizeof(a->src.addr.v.a.mask)))
1177 return (1);
1178 return (0);
1179 case PF_ADDR_NOROUTE:
1180 case PF_ADDR_URPFFAILED:
1181 return (0);
1182 case PF_ADDR_TABLE:
1183 return (strcmp(a->src.addr.v.tblname, b->src.addr.v.tblname));
1184 }
1185 return (1);
1186 }
1187
1188 /* Compare two rules SRC port field for skiplist construction */
1189 int
skip_cmp_src_port(struct pfctl_rule * a,struct pfctl_rule * b)1190 skip_cmp_src_port(struct pfctl_rule *a, struct pfctl_rule *b)
1191 {
1192 if (a->src.port_op == PF_OP_NONE || a->src.port_op != b->src.port_op ||
1193 a->src.port[0] != b->src.port[0] ||
1194 a->src.port[1] != b->src.port[1])
1195 return (1);
1196 /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1197 * && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1198 * a->proto == IPPROTO_ICMP
1199 * return (1);
1200 */
1201 return (0);
1202 }
1203
1204
1205 void
skip_init(void)1206 skip_init(void)
1207 {
1208 struct {
1209 char *name;
1210 int skipnum;
1211 int (*func)(struct pfctl_rule *, struct pfctl_rule *);
1212 } comps[] = PF_SKIP_COMPARITORS;
1213 int skipnum, i;
1214
1215 for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) {
1216 for (i = 0; i < sizeof(comps)/sizeof(*comps); i++)
1217 if (comps[i].skipnum == skipnum) {
1218 skip_comparitors[skipnum] = comps[i].func;
1219 skip_comparitors_names[skipnum] = comps[i].name;
1220 }
1221 }
1222 for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++)
1223 if (skip_comparitors[skipnum] == NULL)
1224 errx(1, "Need to add skip step comparitor to pfctl?!");
1225 }
1226
1227 /*
1228 * Add a host/netmask to a table
1229 */
1230 int
add_opt_table(struct pfctl * pf,struct pf_opt_tbl ** tbl,sa_family_t af,struct pf_rule_addr * addr)1231 add_opt_table(struct pfctl *pf, struct pf_opt_tbl **tbl, sa_family_t af,
1232 struct pf_rule_addr *addr)
1233 {
1234 #ifdef OPT_DEBUG
1235 char buf[128];
1236 #endif /* OPT_DEBUG */
1237 static int tablenum = 0;
1238 struct node_host node_host;
1239
1240 if (*tbl == NULL) {
1241 if ((*tbl = calloc(1, sizeof(**tbl))) == NULL ||
1242 ((*tbl)->pt_buf = calloc(1, sizeof(*(*tbl)->pt_buf))) ==
1243 NULL)
1244 err(1, "calloc");
1245 (*tbl)->pt_refcnt = 1;
1246 (*tbl)->pt_buf->pfrb_type = PFRB_ADDRS;
1247 SIMPLEQ_INIT(&(*tbl)->pt_nodes);
1248
1249 /* This is just a temporary table name */
1250 snprintf((*tbl)->pt_name, sizeof((*tbl)->pt_name), "%s%d",
1251 PF_OPTIMIZER_TABLE_PFX, tablenum++);
1252 DEBUG("creating table <%s>", (*tbl)->pt_name);
1253 }
1254
1255 memset(&node_host, 0, sizeof(node_host));
1256 node_host.af = af;
1257 node_host.addr = addr->addr;
1258
1259 #ifdef OPT_DEBUG
1260 DEBUG("<%s> adding %s/%d", (*tbl)->pt_name, inet_ntop(af,
1261 &node_host.addr.v.a.addr, buf, sizeof(buf)),
1262 unmask(&node_host.addr.v.a.mask));
1263 #endif /* OPT_DEBUG */
1264
1265 if (append_addr_host((*tbl)->pt_buf, &node_host, 0, 0)) {
1266 warn("failed to add host");
1267 return (1);
1268 }
1269 if (pf->opts & PF_OPT_VERBOSE) {
1270 struct node_tinit *ti;
1271
1272 if ((ti = calloc(1, sizeof(*ti))) == NULL)
1273 err(1, "malloc");
1274 if ((ti->host = malloc(sizeof(*ti->host))) == NULL)
1275 err(1, "malloc");
1276 memcpy(ti->host, &node_host, sizeof(*ti->host));
1277 SIMPLEQ_INSERT_TAIL(&(*tbl)->pt_nodes, ti, entries);
1278 }
1279
1280 (*tbl)->pt_rulecount++;
1281 if ((*tbl)->pt_rulecount == TABLE_THRESHOLD)
1282 DEBUG("table <%s> now faster than skip steps", (*tbl)->pt_name);
1283
1284 return (0);
1285 }
1286
1287
1288 /*
1289 * Do the dirty work of choosing an unused table name and creating it.
1290 * (be careful with the table name, it might already be used in another anchor)
1291 */
1292 int
pf_opt_create_table(struct pfctl * pf,struct pf_opt_tbl * tbl)1293 pf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl)
1294 {
1295 static int tablenum;
1296 struct pfr_table *t;
1297
1298 if (table_buffer.pfrb_type == 0) {
1299 /* Initialize the list of tables */
1300 table_buffer.pfrb_type = PFRB_TABLES;
1301 for (;;) {
1302 pfr_buf_grow(&table_buffer, table_buffer.pfrb_size);
1303 table_buffer.pfrb_size = table_buffer.pfrb_msize;
1304 if (pfr_get_tables(NULL, table_buffer.pfrb_caddr,
1305 &table_buffer.pfrb_size, PFR_FLAG_ALLRSETS))
1306 err(1, "pfr_get_tables");
1307 if (table_buffer.pfrb_size <= table_buffer.pfrb_msize)
1308 break;
1309 }
1310 table_identifier = arc4random();
1311 }
1312
1313 /* XXX would be *really* nice to avoid duplicating identical tables */
1314
1315 /* Now we have to pick a table name that isn't used */
1316 again:
1317 DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl->pt_name,
1318 PF_OPTIMIZER_TABLE_PFX, table_identifier, tablenum);
1319 snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d",
1320 PF_OPTIMIZER_TABLE_PFX, table_identifier, tablenum);
1321 PFRB_FOREACH(t, &table_buffer) {
1322 if (strcasecmp(t->pfrt_name, tbl->pt_name) == 0) {
1323 /* Collision. Try again */
1324 DEBUG("wow, table <%s> in use. trying again",
1325 tbl->pt_name);
1326 table_identifier = arc4random();
1327 goto again;
1328 }
1329 }
1330 tablenum++;
1331
1332
1333 if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1,
1334 pf->astack[0]->path, tbl->pt_buf, pf->astack[0]->ruleset.tticket)) {
1335 warn("failed to create table %s in %s",
1336 tbl->pt_name, pf->astack[0]->name);
1337 return (1);
1338 }
1339 return (0);
1340 }
1341
1342 /*
1343 * Partition the flat ruleset into a list of distinct superblocks
1344 */
1345 int
construct_superblocks(struct pfctl * pf,struct pf_opt_queue * opt_queue,struct superblocks * superblocks)1346 construct_superblocks(struct pfctl *pf, struct pf_opt_queue *opt_queue,
1347 struct superblocks *superblocks)
1348 {
1349 struct superblock *block = NULL;
1350 struct pf_opt_rule *por;
1351 int i;
1352
1353 while (!TAILQ_EMPTY(opt_queue)) {
1354 por = TAILQ_FIRST(opt_queue);
1355 TAILQ_REMOVE(opt_queue, por, por_entry);
1356 if (block == NULL || !superblock_inclusive(block, por)) {
1357 if ((block = calloc(1, sizeof(*block))) == NULL) {
1358 warn("calloc");
1359 return (1);
1360 }
1361 TAILQ_INIT(&block->sb_rules);
1362 for (i = 0; i < PF_SKIP_COUNT; i++)
1363 TAILQ_INIT(&block->sb_skipsteps[i]);
1364 TAILQ_INSERT_TAIL(superblocks, block, sb_entry);
1365 }
1366 TAILQ_INSERT_TAIL(&block->sb_rules, por, por_entry);
1367 }
1368
1369 return (0);
1370 }
1371
1372
1373 /*
1374 * Compare two rule addresses
1375 */
1376 int
addrs_equal(struct pf_rule_addr * a,struct pf_rule_addr * b)1377 addrs_equal(struct pf_rule_addr *a, struct pf_rule_addr *b)
1378 {
1379 if (a->neg != b->neg)
1380 return (0);
1381 return (memcmp(&a->addr, &b->addr, sizeof(a->addr)) == 0);
1382 }
1383
1384
1385 /*
1386 * The addresses are not equal, but can we combine them into one table?
1387 */
1388 int
addrs_combineable(struct pf_rule_addr * a,struct pf_rule_addr * b)1389 addrs_combineable(struct pf_rule_addr *a, struct pf_rule_addr *b)
1390 {
1391 if (a->addr.type != PF_ADDR_ADDRMASK ||
1392 b->addr.type != PF_ADDR_ADDRMASK)
1393 return (0);
1394 if (a->neg != b->neg || a->port_op != b->port_op ||
1395 a->port[0] != b->port[0] || a->port[1] != b->port[1])
1396 return (0);
1397 return (1);
1398 }
1399
1400
1401 /*
1402 * Are we allowed to combine these two rules
1403 */
1404 int
rules_combineable(struct pfctl_rule * p1,struct pfctl_rule * p2)1405 rules_combineable(struct pfctl_rule *p1, struct pfctl_rule *p2)
1406 {
1407 struct pfctl_rule a, b;
1408
1409 comparable_rule(&a, p1, COMBINED);
1410 comparable_rule(&b, p2, COMBINED);
1411 return (memcmp(&a, &b, sizeof(a)) == 0);
1412 }
1413
1414
1415 /*
1416 * Can a rule be included inside a superblock
1417 */
1418 int
superblock_inclusive(struct superblock * block,struct pf_opt_rule * por)1419 superblock_inclusive(struct superblock *block, struct pf_opt_rule *por)
1420 {
1421 struct pfctl_rule a, b;
1422 int i, j;
1423
1424 /* First check for hard breaks */
1425 for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) {
1426 if (pf_rule_desc[i].prf_type == BARRIER) {
1427 for (j = 0; j < pf_rule_desc[i].prf_size; j++)
1428 if (((char *)&por->por_rule)[j +
1429 pf_rule_desc[i].prf_offset] != 0)
1430 return (0);
1431 }
1432 }
1433
1434 /* per-rule src-track is also a hard break */
1435 if (por->por_rule.rule_flag & PFRULE_RULESRCTRACK)
1436 return (0);
1437
1438 /*
1439 * Have to handle interface groups separately. Consider the following
1440 * rules:
1441 * block on EXTIFS to any port 22
1442 * pass on em0 to any port 22
1443 * (where EXTIFS is an arbitrary interface group)
1444 * The optimizer may decide to re-order the pass rule in front of the
1445 * block rule. But what if EXTIFS includes em0??? Such a reordering
1446 * would change the meaning of the ruleset.
1447 * We can't just lookup the EXTIFS group and check if em0 is a member
1448 * because the user is allowed to add interfaces to a group during
1449 * runtime.
1450 * Ergo interface groups become a defacto superblock break :-(
1451 */
1452 if (interface_group(por->por_rule.ifname) ||
1453 interface_group(TAILQ_FIRST(&block->sb_rules)->por_rule.ifname)) {
1454 if (strcasecmp(por->por_rule.ifname,
1455 TAILQ_FIRST(&block->sb_rules)->por_rule.ifname) != 0)
1456 return (0);
1457 }
1458
1459 comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE);
1460 comparable_rule(&b, &por->por_rule, NOMERGE);
1461 if (memcmp(&a, &b, sizeof(a)) == 0)
1462 return (1);
1463
1464 #ifdef OPT_DEBUG
1465 for (i = 0; i < sizeof(por->por_rule); i++) {
1466 int closest = -1;
1467 if (((u_int8_t *)&a)[i] != ((u_int8_t *)&b)[i]) {
1468 for (j = 0; j < sizeof(pf_rule_desc) /
1469 sizeof(*pf_rule_desc); j++) {
1470 if (i >= pf_rule_desc[j].prf_offset &&
1471 i < pf_rule_desc[j].prf_offset +
1472 pf_rule_desc[j].prf_size) {
1473 DEBUG("superblock break @ %d due to %s",
1474 por->por_rule.nr,
1475 pf_rule_desc[j].prf_name);
1476 return (0);
1477 }
1478 if (i > pf_rule_desc[j].prf_offset) {
1479 if (closest == -1 ||
1480 i-pf_rule_desc[j].prf_offset <
1481 i-pf_rule_desc[closest].prf_offset)
1482 closest = j;
1483 }
1484 }
1485
1486 if (closest >= 0)
1487 DEBUG("superblock break @ %d on %s+%zxh",
1488 por->por_rule.nr,
1489 pf_rule_desc[closest].prf_name,
1490 i - pf_rule_desc[closest].prf_offset -
1491 pf_rule_desc[closest].prf_size);
1492 else
1493 DEBUG("superblock break @ %d on field @ %d",
1494 por->por_rule.nr, i);
1495 return (0);
1496 }
1497 }
1498 #endif /* OPT_DEBUG */
1499
1500 return (0);
1501 }
1502
1503
1504 /*
1505 * Figure out if an interface name is an actual interface or actually a
1506 * group of interfaces.
1507 */
1508 int
interface_group(const char * ifname)1509 interface_group(const char *ifname)
1510 {
1511 int s;
1512 struct ifgroupreq ifgr;
1513
1514 if (ifname == NULL || !ifname[0])
1515 return (0);
1516
1517 s = get_query_socket();
1518
1519 memset(&ifgr, 0, sizeof(ifgr));
1520 strlcpy(ifgr.ifgr_name, ifname, IFNAMSIZ);
1521 if (ioctl(s, SIOCGIFGMEMB, (caddr_t)&ifgr) == -1) {
1522 if (errno == ENOENT)
1523 return (0);
1524 else
1525 err(1, "SIOCGIFGMEMB");
1526 }
1527
1528 return (1);
1529 }
1530
1531
1532 /*
1533 * Make a rule that can directly compared by memcmp()
1534 */
1535 void
comparable_rule(struct pfctl_rule * dst,const struct pfctl_rule * src,int type)1536 comparable_rule(struct pfctl_rule *dst, const struct pfctl_rule *src, int type)
1537 {
1538 int i;
1539 /*
1540 * To simplify the comparison, we just zero out the fields that are
1541 * allowed to be different and then do a simple memcmp()
1542 */
1543 memcpy(dst, src, sizeof(*dst));
1544 for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++)
1545 if (pf_rule_desc[i].prf_type >= type) {
1546 #ifdef OPT_DEBUG
1547 assert(pf_rule_desc[i].prf_type != NEVER ||
1548 *(((char *)dst) + pf_rule_desc[i].prf_offset) == 0);
1549 #endif /* OPT_DEBUG */
1550 memset(((char *)dst) + pf_rule_desc[i].prf_offset, 0,
1551 pf_rule_desc[i].prf_size);
1552 }
1553 }
1554
1555
1556 /*
1557 * Remove superset information from two rules so we can directly compare them
1558 * with memcmp()
1559 */
1560 void
exclude_supersets(struct pfctl_rule * super,struct pfctl_rule * sub)1561 exclude_supersets(struct pfctl_rule *super, struct pfctl_rule *sub)
1562 {
1563 if (super->ifname[0] == '\0')
1564 memset(sub->ifname, 0, sizeof(sub->ifname));
1565 if (super->direction == PF_INOUT)
1566 sub->direction = PF_INOUT;
1567 if ((super->proto == 0 || super->proto == sub->proto) &&
1568 super->flags == 0 && super->flagset == 0 && (sub->flags ||
1569 sub->flagset)) {
1570 sub->flags = super->flags;
1571 sub->flagset = super->flagset;
1572 }
1573 if (super->proto == 0)
1574 sub->proto = 0;
1575
1576 if (super->src.port_op == 0) {
1577 sub->src.port_op = 0;
1578 sub->src.port[0] = 0;
1579 sub->src.port[1] = 0;
1580 }
1581 if (super->dst.port_op == 0) {
1582 sub->dst.port_op = 0;
1583 sub->dst.port[0] = 0;
1584 sub->dst.port[1] = 0;
1585 }
1586
1587 if (super->src.addr.type == PF_ADDR_ADDRMASK && !super->src.neg &&
1588 !sub->src.neg && super->src.addr.v.a.mask.addr32[0] == 0 &&
1589 super->src.addr.v.a.mask.addr32[1] == 0 &&
1590 super->src.addr.v.a.mask.addr32[2] == 0 &&
1591 super->src.addr.v.a.mask.addr32[3] == 0)
1592 memset(&sub->src.addr, 0, sizeof(sub->src.addr));
1593 else if (super->src.addr.type == PF_ADDR_ADDRMASK &&
1594 sub->src.addr.type == PF_ADDR_ADDRMASK &&
1595 super->src.neg == sub->src.neg &&
1596 super->af == sub->af &&
1597 unmask(&super->src.addr.v.a.mask) <
1598 unmask(&sub->src.addr.v.a.mask) &&
1599 super->src.addr.v.a.addr.addr32[0] ==
1600 (sub->src.addr.v.a.addr.addr32[0] &
1601 super->src.addr.v.a.mask.addr32[0]) &&
1602 super->src.addr.v.a.addr.addr32[1] ==
1603 (sub->src.addr.v.a.addr.addr32[1] &
1604 super->src.addr.v.a.mask.addr32[1]) &&
1605 super->src.addr.v.a.addr.addr32[2] ==
1606 (sub->src.addr.v.a.addr.addr32[2] &
1607 super->src.addr.v.a.mask.addr32[2]) &&
1608 super->src.addr.v.a.addr.addr32[3] ==
1609 (sub->src.addr.v.a.addr.addr32[3] &
1610 super->src.addr.v.a.mask.addr32[3])) {
1611 /* sub->src.addr is a subset of super->src.addr/mask */
1612 memcpy(&sub->src.addr, &super->src.addr, sizeof(sub->src.addr));
1613 }
1614
1615 if (super->dst.addr.type == PF_ADDR_ADDRMASK && !super->dst.neg &&
1616 !sub->dst.neg && super->dst.addr.v.a.mask.addr32[0] == 0 &&
1617 super->dst.addr.v.a.mask.addr32[1] == 0 &&
1618 super->dst.addr.v.a.mask.addr32[2] == 0 &&
1619 super->dst.addr.v.a.mask.addr32[3] == 0)
1620 memset(&sub->dst.addr, 0, sizeof(sub->dst.addr));
1621 else if (super->dst.addr.type == PF_ADDR_ADDRMASK &&
1622 sub->dst.addr.type == PF_ADDR_ADDRMASK &&
1623 super->dst.neg == sub->dst.neg &&
1624 super->af == sub->af &&
1625 unmask(&super->dst.addr.v.a.mask) <
1626 unmask(&sub->dst.addr.v.a.mask) &&
1627 super->dst.addr.v.a.addr.addr32[0] ==
1628 (sub->dst.addr.v.a.addr.addr32[0] &
1629 super->dst.addr.v.a.mask.addr32[0]) &&
1630 super->dst.addr.v.a.addr.addr32[1] ==
1631 (sub->dst.addr.v.a.addr.addr32[1] &
1632 super->dst.addr.v.a.mask.addr32[1]) &&
1633 super->dst.addr.v.a.addr.addr32[2] ==
1634 (sub->dst.addr.v.a.addr.addr32[2] &
1635 super->dst.addr.v.a.mask.addr32[2]) &&
1636 super->dst.addr.v.a.addr.addr32[3] ==
1637 (sub->dst.addr.v.a.addr.addr32[3] &
1638 super->dst.addr.v.a.mask.addr32[3])) {
1639 /* sub->dst.addr is a subset of super->dst.addr/mask */
1640 memcpy(&sub->dst.addr, &super->dst.addr, sizeof(sub->dst.addr));
1641 }
1642
1643 if (super->af == 0)
1644 sub->af = 0;
1645 }
1646
1647
1648 void
superblock_free(struct pfctl * pf,struct superblock * block)1649 superblock_free(struct pfctl *pf, struct superblock *block)
1650 {
1651 struct pf_opt_rule *por;
1652 while ((por = TAILQ_FIRST(&block->sb_rules))) {
1653 TAILQ_REMOVE(&block->sb_rules, por, por_entry);
1654 pf_opt_table_unref(por->por_src_tbl);
1655 pf_opt_table_unref(por->por_dst_tbl);
1656 free(por);
1657 }
1658 if (block->sb_profiled_block)
1659 superblock_free(pf, block->sb_profiled_block);
1660 free(block);
1661 }
1662
1663 struct pf_opt_tbl *
pf_opt_table_ref(struct pf_opt_tbl * pt)1664 pf_opt_table_ref(struct pf_opt_tbl *pt)
1665 {
1666 /* parser does not run concurrently, we don't need atomic ops. */
1667 if (pt != NULL)
1668 pt->pt_refcnt++;
1669
1670 return (pt);
1671 }
1672
1673 void
pf_opt_table_unref(struct pf_opt_tbl * pt)1674 pf_opt_table_unref(struct pf_opt_tbl *pt)
1675 {
1676 if ((pt != NULL) && ((--pt->pt_refcnt) == 0)) {
1677 if (pt->pt_buf != NULL) {
1678 pfr_buf_clear(pt->pt_buf);
1679 free(pt->pt_buf);
1680 }
1681 free(pt);
1682 }
1683 }
1684