/*	$OpenBSD: pfctl_optimize.c,v 1.35 2015/01/21 21:50:33 deraadt Exp $ */

/*

 * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org>

 *

 * Permission to use, copy, modify, and distribute this software for any

 * purpose with or without fee is hereby granted, provided that the above

 * copyright notice and this permission notice appear in all copies.

 *

 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 */

#include <sys/types.h>

#include <sys/ioctl.h>

#include <sys/socket.h>

#include <netinet/in.h>

#include <arpa/inet.h>

#include <net/if.h>

#include <net/pfvar.h>

#include <assert.h>

#include <ctype.h>

#include <err.h>

#include <errno.h>

#include <stddef.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "pfctl_parser.h"

#include "pfctl.h"

/* The size at which a table becomes faster than individual rules */

#define TABLE_THRESHOLD		6

/* #define OPT_DEBUG	1 */

#ifdef OPT_DEBUG

# define DEBUG(str, v...) \

	printf("%s: " str "\n", __FUNCTION__ , ## v)

#else

# define DEBUG(str, v...) ((void)0)

#endif

/*

 * A container that lets us sort a superblock to optimize the skip step jumps

 */

struct pf_skip_step {

	int				ps_count;	/* number of items */

	TAILQ_HEAD( , pf_opt_rule)	ps_rules;

	TAILQ_ENTRY(pf_skip_step)	ps_entry;

};

/*

 * A superblock is a block of adjacent rules of similar action.  If there

 * are five PASS rules in a row, they all become members of a superblock.

 * Once we have a superblock, we are free to re-order any rules within it

 * in order to improve performance; if a packet is passed, it doesn't matter

 * who passed it.

 */

struct superblock {

	TAILQ_HEAD( , pf_opt_rule)		 sb_rules;

	TAILQ_ENTRY(superblock)			 sb_entry;

	struct superblock			*sb_profiled_block;

	TAILQ_HEAD(skiplist, pf_skip_step)	 sb_skipsteps[PF_SKIP_COUNT];

};

TAILQ_HEAD(superblocks, superblock);

/*

 * Description of the PF rule structure.

 */

enum {

    BARRIER,	/* the presence of the field puts the rule in it's own block */

    BREAK,	/* the field may not differ between rules in a superblock */

    NOMERGE,	/* the field may not differ between rules when combined */

    COMBINED,	/* the field may itself be combined with other rules */

    DC,		/* we just don't care about the field */

    NEVER};	/* we should never see this field set?!? */

struct pf_rule_field {

	const char	*prf_name;

	int		 prf_type;

	size_t		 prf_offset;

	size_t		 prf_size;

} pf_rule_desc[] = {

#define PF_RULE_FIELD(field, ty)	\

    {#field,				\

    ty,					\

    offsetof(struct pf_rule, field),	\

    sizeof(((struct pf_rule *)0)->field)}

    /*

     * The presence of these fields in a rule put the rule in it's own

     * superblock.  Thus it will not be optimized.  It also prevents the

     * rule from being re-ordered at all.

     */

    PF_RULE_FIELD(label,		BARRIER),

    PF_RULE_FIELD(prob,			BARRIER),

    PF_RULE_FIELD(max_states,		BARRIER),

    PF_RULE_FIELD(max_src_nodes,	BARRIER),

    PF_RULE_FIELD(max_src_states,	BARRIER),

    PF_RULE_FIELD(max_src_conn,		BARRIER),

    PF_RULE_FIELD(max_src_conn_rate,	BARRIER),

    PF_RULE_FIELD(anchor,		BARRIER),	/* for now */

    /*

     * These fields must be the same between all rules in the same superblock.

     * These rules are allowed to be re-ordered but only among like rules.

     * For instance we can re-order all 'tag "foo"' rules because they have the

     * same tag.  But we can not re-order between a 'tag "foo"' and a

     * 'tag "bar"' since that would change the meaning of the ruleset.

     */

    PF_RULE_FIELD(tagname,		BREAK),

    PF_RULE_FIELD(keep_state,		BREAK),

    PF_RULE_FIELD(qname,		BREAK),

    PF_RULE_FIELD(pqname,		BREAK),

    PF_RULE_FIELD(rt,			BREAK),

    PF_RULE_FIELD(allow_opts,		BREAK),

    PF_RULE_FIELD(rule_flag,		BREAK),

    PF_RULE_FIELD(action,		BREAK),

    PF_RULE_FIELD(log,			BREAK),

    PF_RULE_FIELD(quick,		BREAK),

    PF_RULE_FIELD(return_ttl,		BREAK),

    PF_RULE_FIELD(overload_tblname,	BREAK),

    PF_RULE_FIELD(flush,		BREAK),

    PF_RULE_FIELD(rdr,			BREAK),

    PF_RULE_FIELD(nat,			BREAK),

    PF_RULE_FIELD(logif,		BREAK),

    PF_RULE_FIELD(route,		BREAK),

    PF_RULE_FIELD(rtableid,		BREAK),

    /*

     * Any fields not listed in this structure act as BREAK fields

     */

    /*

     * These fields must not differ when we merge two rules together but

     * their difference isn't enough to put the rules in different superblocks.

     * There are no problems re-ordering any rules with these fields.

     */

    PF_RULE_FIELD(af,			NOMERGE),

    PF_RULE_FIELD(ifnot,		NOMERGE),

    PF_RULE_FIELD(ifname,		NOMERGE),	/* hack for IF groups */

    PF_RULE_FIELD(match_tag_not,	NOMERGE),

    PF_RULE_FIELD(match_tagname,	NOMERGE),

    PF_RULE_FIELD(os_fingerprint,	NOMERGE),

    PF_RULE_FIELD(timeout,		NOMERGE),

    PF_RULE_FIELD(return_icmp,		NOMERGE),

    PF_RULE_FIELD(return_icmp6,		NOMERGE),

    PF_RULE_FIELD(uid,			NOMERGE),

    PF_RULE_FIELD(gid,			NOMERGE),

    PF_RULE_FIELD(direction,		NOMERGE),

    PF_RULE_FIELD(proto,		NOMERGE),

    PF_RULE_FIELD(type,			NOMERGE),

    PF_RULE_FIELD(code,			NOMERGE),

    PF_RULE_FIELD(flags,		NOMERGE),

    PF_RULE_FIELD(flagset,		NOMERGE),

    PF_RULE_FIELD(tos,			NOMERGE),

    PF_RULE_FIELD(src.port,		NOMERGE),

    PF_RULE_FIELD(dst.port,		NOMERGE),

    PF_RULE_FIELD(src.port_op,		NOMERGE),

    PF_RULE_FIELD(dst.port_op,		NOMERGE),

    PF_RULE_FIELD(src.neg,		NOMERGE),

    PF_RULE_FIELD(dst.neg,		NOMERGE),

    PF_RULE_FIELD(onrdomain,		NOMERGE),

    PF_RULE_FIELD(naf,			NOMERGE),

    /* These fields can be merged */

    PF_RULE_FIELD(src.addr,		COMBINED),

    PF_RULE_FIELD(dst.addr,		COMBINED),

    /* We just don't care about these fields.  They're set by the kernel */

    PF_RULE_FIELD(skip,			DC),

    PF_RULE_FIELD(evaluations,		DC),

    PF_RULE_FIELD(packets,		DC),

    PF_RULE_FIELD(bytes,		DC),

    PF_RULE_FIELD(kif,			DC),

    PF_RULE_FIELD(states_cur,		DC),

    PF_RULE_FIELD(states_tot,		DC),

    PF_RULE_FIELD(src_nodes,		DC),

    PF_RULE_FIELD(nr,			DC),

    PF_RULE_FIELD(entries,		DC),

    PF_RULE_FIELD(qid,			DC),

    PF_RULE_FIELD(pqid,			DC),

    PF_RULE_FIELD(anchor_relative,	DC),

    PF_RULE_FIELD(anchor_wildcard,	DC),

    PF_RULE_FIELD(tag,			DC),

    PF_RULE_FIELD(match_tag,		DC),

    PF_RULE_FIELD(overload_tbl,		DC),

    /* These fields should never be set in a PASS/BLOCK rule XXX fix*/

    PF_RULE_FIELD(max_mss,		NEVER),

    PF_RULE_FIELD(min_ttl,		NEVER),

    PF_RULE_FIELD(set_tos,		NEVER),

};

int	addrs_combineable(struct pf_rule_addr *, struct pf_rule_addr *);

int	addrs_equal(struct pf_rule_addr *, struct pf_rule_addr *);

int	block_feedback(struct pfctl *, struct superblock *);

int	combine_rules(struct pfctl *, struct superblock *);

void	comparable_rule(struct pf_rule *, const struct pf_rule *, int);

int	construct_superblocks(struct pfctl *, struct pf_opt_queue *,

	    struct superblocks *);

void	exclude_supersets(struct pf_rule *, struct pf_rule *);

int	interface_group(const char *);

int	load_feedback_profile(struct pfctl *, struct superblocks *);

int	optimize_superblock(struct pfctl *, struct superblock *);

void	remove_from_skipsteps(struct skiplist *, struct superblock *,

	    struct pf_opt_rule *, struct pf_skip_step *);

int	remove_identical_rules(struct pfctl *, struct superblock *);

int	reorder_rules(struct pfctl *, struct superblock *, int);

int	rules_combineable(struct pf_rule *, struct pf_rule *);

void	skip_append(struct superblock *, int, struct pf_skip_step *,

	    struct pf_opt_rule *);

int	skip_compare(int, struct pf_skip_step *, struct pf_opt_rule *);

void	skip_init(void);

int	skip_cmp_af(struct pf_rule *, struct pf_rule *);

int	skip_cmp_dir(struct pf_rule *, struct pf_rule *);

int	skip_cmp_rdom(struct pf_rule *, struct pf_rule *);

int	skip_cmp_dst_addr(struct pf_rule *, struct pf_rule *);

int	skip_cmp_dst_port(struct pf_rule *, struct pf_rule *);

int	skip_cmp_ifp(struct pf_rule *, struct pf_rule *);

int	skip_cmp_proto(struct pf_rule *, struct pf_rule *);

int	skip_cmp_src_addr(struct pf_rule *, struct pf_rule *);

int	skip_cmp_src_port(struct pf_rule *, struct pf_rule *);

int	superblock_inclusive(struct superblock *, struct pf_opt_rule *);

void	superblock_free(struct pfctl *, struct superblock *);

int (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, struct pf_rule *);

const char *skip_comparitors_names[PF_SKIP_COUNT];

#define PF_SKIP_COMPARITORS {				\

    { "ifp", PF_SKIP_IFP, skip_cmp_ifp },		\

    { "dir", PF_SKIP_DIR, skip_cmp_dir },		\

    { "rdomain", PF_SKIP_RDOM, skip_cmp_rdom },		\

    { "af", PF_SKIP_AF, skip_cmp_af },			\

    { "proto", PF_SKIP_PROTO, skip_cmp_proto },		\

    { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr },	\

    { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr },	\

    { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port },	\

    { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port }	\

}

struct pfr_buffer table_buffer;

int table_identifier;

int

pfctl_optimize_ruleset(struct pfctl *pf, struct pf_ruleset *rs)

{

	struct superblocks superblocks;

	struct pf_opt_queue opt_queue;

	struct superblock *block;

	struct pf_opt_rule *por;

	struct pf_rule *r;

	struct pf_rulequeue *old_rules;

	DEBUG("optimizing ruleset");

	/*

	 * XXX expanding the pf_opt_rule format throughout pfctl might allow

	 * us to avoid all this copying.

	 */

	}

	}

	}

		}

	}

error:

		}

		}

	}

	}

}

/*

 * Go ahead and optimize a superblock

 */

int

optimize_superblock(struct pfctl *pf, struct superblock *block)

{

#ifdef OPT_DEBUG

	struct pf_opt_rule *por;

#endif /* OPT_DEBUG */

	/* We have a few optimization passes:

	 *   1) remove duplicate rules or rules that are a subset of other

	 *      rules

	 *   2) combine otherwise identical rules with different IP addresses

	 *      into a single rule and put the addresses in a table.

	 *   3) re-order the rules to improve kernel skip steps

	 *   4) re-order the 'quick' rules based on feedback from the

	 *      active ruleset statistics

	 *

	 * XXX combine_rules() doesn't combine v4 and v6 rules.  would just

	 *     have to keep af in the table container, make af 'COMBINE' and

	 *     twiddle the af on the merged rule

	 * XXX maybe add a weighting to the metric on skipsteps when doing

	 *     reordering.  sometimes two sequential tables will be better

	 *     that four consecutive interfaces.

	 * XXX need to adjust the skipstep count of everything after PROTO,

	 *     since they aren't actually checked on a proto mismatch in

	 *     pf_test_{tcp, udp, icmp}()

	 * XXX should i treat proto=0, af=0 or dir=0 special in skepstep

	 *     calculation since they are a DC?

	 * XXX keep last skiplist of last superblock to influence this

	 *     superblock.  '5 inet6 log' should make '3 inet6' come before '4

	 *     inet' in the next superblock.

	 * XXX would be useful to add tables for ports

	 * XXX we can also re-order some mutually exclusive superblocks to

	 *     try merging superblocks before any of these optimization passes.

	 *     for instance a single 'log in' rule in the middle of non-logging

	 *     out rules.

	 */

	/* shortcut.  there will be a lot of 1-rule superblocks */

#ifdef OPT_DEBUG

	printf("--- Superblock ---\n");

	TAILQ_FOREACH(por, &block->sb_rules, por_entry) {

		printf("  ");

		print_rule(&por->por_rule, por->por_rule.anchor ?

		    por->por_rule.anchor->name : "", PF_OPT_DEBUG);

	}

#endif /* OPT_DEBUG */

	    TAILQ_FIRST(&block->sb_rules)->por_rule.quick &&

	    block->sb_profiled_block) {

	}

	/*

	 * Don't add any optimization passes below reorder_rules().  It will

	 * have divided superblocks into smaller blocks for further refinement

	 * and doesn't put them back together again.  What once was a true

	 * superblock might have been split into multiple superblocks.

	 */

#ifdef OPT_DEBUG

	printf("--- END Superblock ---\n");

#endif /* OPT_DEBUG */

}

/*

 * Optimization pass #1: remove identical rules

 */

int

remove_identical_rules(struct pfctl *pf, struct superblock *block)

{

	struct pf_opt_rule *por1, *por2, *por_next, *por2_next;

	struct pf_rule a, a2, b, b2;

				DEBUG("removing identical rule  nr%d = *nr%d*",

				    por1->por_rule.nr, por2->por_rule.nr);

				DEBUG("removing identical rule  *nr%d* = nr%d",

				    por1->por_rule.nr, por2->por_rule.nr);

			}

		}

	}

}

/*

 * Optimization pass #2: combine similar rules with different addresses

 * into a single rule and a table

 */

int

combine_rules(struct pfctl *pf, struct superblock *block)

{

	struct pf_opt_rule *p1, *p2, *por_next;

	int src_eq, dst_eq;

	/* First we make a pass to combine the rules.  O(n log n) */

			    &p2->por_rule.src);

			    &p2->por_rule.dst);

			    p2->por_dst_tbl == NULL &&

			    p2->por_src_tbl == NULL &&

			    rules_combineable(&p1->por_rule, &p2->por_rule) &&

			    addrs_combineable(&p1->por_rule.dst,

			    &p2->por_rule.dst)) {

				DEBUG("can combine rules  nr%d = nr%d",

				    p1->por_rule.nr, p2->por_rule.nr);

				    add_opt_table(pf, &p1->por_dst_tbl,

				    p1->por_rule.af, &p1->por_rule.dst, NULL))

				    p1->por_rule.af, &p2->por_rule.dst, NULL))

				    TABLE_THRESHOLD) {

					    por_entry);

				}

			    && p2->por_src_tbl == NULL &&

			    p2->por_dst_tbl == NULL &&

			    rules_combineable(&p1->por_rule, &p2->por_rule) &&

			    addrs_combineable(&p1->por_rule.src,

			    &p2->por_rule.src)) {

				DEBUG("can combine rules  nr%d = nr%d",

				    p1->por_rule.nr, p2->por_rule.nr);

				    add_opt_table(pf, &p1->por_src_tbl,

				    p1->por_rule.af, &p1->por_rule.src, NULL))

				    p1->por_rule.af, &p2->por_rule.src, NULL))

				    TABLE_THRESHOLD) {

					    por_entry);

				}

			}

		}

	}

	/*

	 * Then we make a final pass to create a valid table name and

	 * insert the name into the rules.

	 * Convert translation/routing mapping pools to tables as well.

	 */

		    TABLE_THRESHOLD) {

				/* This rule is included in a table */

			}

			    pf_opt_create_table(pf, p1->por_src_tbl))

				    PFR_TFLAG_CONST, 1,

				    &p1->por_src_tbl->pt_nodes);

			    sizeof(p1->por_rule.src.addr));

			    p1->por_src_tbl->pt_name,

			    sizeof(p1->por_rule.src.addr.v.tblname));

		}

		    TABLE_THRESHOLD) {

				/* This rule is included in a table */

			}

			    pf_opt_create_table(pf, p1->por_dst_tbl))

				    PFR_TFLAG_CONST, 1,

				    &p1->por_dst_tbl->pt_nodes);

			    sizeof(p1->por_rule.dst.addr));

			    p1->por_dst_tbl->pt_name,

			    sizeof(p1->por_rule.dst.addr.v.tblname));

		}

	}

}

/*

 * Optimization pass #3: re-order rules to improve skip steps

 */

int

reorder_rules(struct pfctl *pf, struct superblock *block, int depth)

{

	struct superblock *newblock;

	struct pf_skip_step *skiplist;

	struct pf_opt_rule *por;

	TAILQ_HEAD( , pf_opt_rule) head;

	/*

	 * Calculate the best-case skip steps.  We put each rule in a list

	 * of other rules with common fields

	 */

			    ps_entry) {

			}

				    NULL)

				    skiplist, ps_entry);

			}

		}

	}

	/*

	 * Now we're going to ignore any fields that are identical between

	 * all of the rules in the superblock and those fields which differ

	 * between every rule in the superblock.

	 */

			DEBUG("(%d) original skipstep '%s' is all rules",

			    depth, skip_comparitors_names[i]);

		} else {

			DEBUG("(%d) original skipstep '%s' largest jump is %d",

			    depth, skip_comparitors_names[i],

			    skiplist->ps_count);

		}

	}

		/* Ugh.  There is NO commonality in the superblock on which

		 * optimize the skipsteps optimization.

		 */

	}

	/*

	 * Now we're going to empty the superblock rule list and re-create

	 * it based on a more optimal skipstep order.

	 */

	}

		/*

		 * Find the most useful skip steps remaining

		 */

			}

		}

			/*

			 * Nothing useful left.  Leave remaining rules in order.

			 */

			DEBUG("(%d) no more commonality for skip steps", depth);

				    por_entry);

			}

		} else {

			/*

			 * There is commonality.  Extract those common rules

			 * and place them in the ruleset adjacent to each

			 * other.

			 */

			    largest_list]);

			DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d",

			    depth, skip_comparitors_names[largest_list],

			    largest, TAILQ_FIRST(&TAILQ_FIRST(&block->

			    sb_skipsteps [largest_list])->ps_rules)->

			    por_rule.nr);

			    skiplist, ps_entry);

			/*

			 * There may be further commonality inside these

			 * rules.  So we'll split them off into they're own

			 * superblock and pass it back into the optimizer.

			 */

				    == NULL) {

				}

				DEBUG("(%d) splitting off %d rules from superblock @ #%d",

				    depth, skiplist->ps_count,

				    TAILQ_FIRST(&skiplist->ps_rules)->

				    por_rule.nr);

			} else {

			}

				    por_skip_entry[largest_list]);

				    por_entry);

				/* Remove this rule from all other skiplists */

				    largest_list], block, por, skiplist);

			}

		}

	}

			    ps_entry);

		}

	}

}

/*

 * Optimization pass #4: re-order 'quick' rules based on feedback from the

 * currently running ruleset

 */

int

block_feedback(struct pfctl *pf, struct superblock *block)

{

	TAILQ_HEAD( , pf_opt_rule) queue;

	struct pf_opt_rule *por1, *por2;

	struct pf_rule a, b;

	/*

	 * Walk through all of the profiled superblock's rules and copy

	 * the counters onto our rules.

	 */

		    por1->por_rule.packets[1];

				    por1->por_rule.packets[0] +

				    por1->por_rule.packets[1];

			}

		}

	}

	/*

	 * Now we pull all of the rules off the superblock and re-insert them

	 * in sorted order.

	 */

	}

/* XXX I should sort all of the unused rules based on skip steps */

			}

		}

	}

}

/*

 * Load the current ruleset from the kernel and try to associate them with

 * the ruleset we're optimizing.

 */

int

load_feedback_profile(struct pfctl *pf, struct superblocks *superblocks)

{

	struct superblock *block, *blockcur;

	struct superblocks prof_superblocks;

	struct pf_opt_rule *por;

	struct pf_opt_queue queue;

	struct pfioc_rule pr;

	struct pf_rule a, b;

	int nr, mnr;

	}

	DEBUG("Loading %d active rules for a feedback profile", mnr);

		struct pf_ruleset *rs;

		}

		}

		/* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket,

		 *         PF_PASS, pf->anchor) ???

		 * ... pfctl_clear_pool(&pr.rule.rpool)

		 */

	}

	/*

	 * Now we try to associate the active ruleset's superblocks with

	 * the superblocks we're compiling.

	 */

		    BREAK);

		    BREAK);

			/* The two superblocks lined up */

		} else {

			DEBUG("superblocks don't line up between #%d and #%d",

			    TAILQ_FIRST(&block->sb_rules)->por_rule.nr,

			    TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr);

		}

	}

	/* Free any superblocks we couldn't link */

	}

}

/*

 * Compare a rule to a skiplist to see if the rule is a member

 */

int

skip_compare(int skipnum, struct pf_skip_step *skiplist,

    struct pf_opt_rule *por)

{

	struct pf_rule *a, *b;

}

/*

 * Add a rule to a skiplist

 */

void

skip_append(struct superblock *superblock, int skipnum,

    struct pf_skip_step *skiplist, struct pf_opt_rule *por)

{

	struct pf_skip_step *prev;

	/* Keep the list of skiplists sorted by whichever is larger */

	    prev->ps_count < skiplist->ps_count) {

		    skiplist, ps_entry);

	}

}

/*

 * Remove a rule from the other skiplist calculations.

 */

void

remove_from_skipsteps(struct skiplist *head, struct superblock *block,

    struct pf_opt_rule *por, struct pf_skip_step *active_list)

{

	struct pf_skip_step *sk, *next;

	struct pf_opt_rule *p2;

	int i, found;