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