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