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