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