bpf:pfc: Add optimization option to use a binary tree

This patch adds a filter attribute, SCMP_FLTATR_CTL_OPTIMIZE,
to specify the optimization level of the seccomp filter:
	0 - currently unused
	1 - rules weighted by priority and complexity (default)
	2 - binary tree sorted by syscall number

Several in-house customers have identified that their large
seccomp filters are slowing down their applications.  Their
filters largely consist of simple allow/deny logic for many
syscalls (306 in one case) and for the most part don't utilize
argument filtering.

I modified gen_bpf.c and gen_pfc.c to utilize a cBPF binary tree
if the user has requested optimize level 2.  I then timed
calling getppid() in a loop using one of my customer's seccomp
filters.  I ran this loop one million times and recorded the min,
max, and mean times (in TSC ticks) to call getppid().  (I didn't
disable interrupts, so the max time was often large.)  I chose
to report the minimum time because I feel it best represents the
actual time to traverse the syscall.

Test Case                      minimum TSC ticks to make syscall
----------------------------------------------------------------
seccomp disabled                                             138
getppid() at the front of 306-syscall seccomp filter         256
getppid() in middle of 306-syscall seccomp filter            516
getppid() at the end of the 306-syscall filter              1942
getppid() in a binary tree                                   312

As shown in the table above, a binary tree can signficantly improve
syscall performance in the average and worst case scenario for these
customers.

Signed-off-by: Tom Hromatka <tom.hromatka@oracle.com>
Signed-off-by: Paul Moore <paul@paul-moore.com>

7 files changed, 457 insertions, 44 deletions

diff --git a/include/seccomp.h.in b/include/seccomp.h.in
index 208b366..8115b50 100644
--- a/include/seccomp.h.in
+++ b/include/seccomp.h.in
@@ -69,6 +69,11 @@ enum scmp_filter_attr {
 	SCMP_FLTATR_API_TSKIP = 5,	/**< allow rules with a -1 syscall */
 	SCMP_FLTATR_CTL_LOG = 6,	/**< log not-allowed actions */
 	SCMP_FLTATR_CTL_SSB = 7,	/**< disable SSB mitigation */
+	SCMP_FLTATR_CTL_OPTIMIZE = 8,	/**< filter optimization level: (DEFAULT = 1)
+					 * 0 - currently unused
+					 * 1 - rules weighted by priority and complexity
+					 * 2 - binary tree sorted by syscall number
+					 */
 	_SCMP_FLTATR_MAX,
 };
 
diff --git a/src/db.c b/src/db.c
index a40cb2b..bd362a6 100644
--- a/src/db.c
+++ b/src/db.c
@@ -841,6 +841,7 @@ static void _db_reset(struct db_filter *db)
 		}
 		db->syscalls = NULL;
 	}
+	db->syscall_cnt = 0;
 
 	/* free any rules */
 	if (db->rules != NULL) {
@@ -1069,6 +1070,7 @@ int db_col_reset(struct db_filter_col *col, uint32_t def_action)
 	col->attr.api_tskip = 0;
 	col->attr.log_enable = 0;
 	col->attr.spec_allow = 0;
+	col->attr.optimize = 1;
 
 	/* set the state */
 	col->state = _DB_STA_VALID;
@@ -1311,6 +1313,9 @@ int db_col_attr_get(const struct db_filter_col *col,
 	case SCMP_FLTATR_CTL_SSB:
 		*value = col->attr.spec_allow;
 		break;
+	case SCMP_FLTATR_CTL_OPTIMIZE:
+		*value = col->attr.optimize;
+		break;
 	default:
 		rc = -EEXIST;
 		break;
@@ -1386,6 +1391,17 @@ int db_col_attr_set(struct db_filter_col *col,
 			rc = -EOPNOTSUPP;
 		}
 		break;
+	case SCMP_FLTATR_CTL_OPTIMIZE:
+		switch (value) {
+		case 1:
+		case 2:
+			col->attr.optimize = value;
+			break;
+		default:
+			rc = -EOPNOTSUPP;
+			break;
+		}
+		break;
 	default:
 		rc = -EEXIST;
 		break;
@@ -2052,6 +2068,7 @@ add_reset:
 			s_new->next = db->syscalls;
 			db->syscalls = s_new;
 		}
+		db->syscall_cnt++;
 		return 0;
 	} else if (s_iter->chains == NULL) {
 		if (rm_flag || !s_iter->valid) {
diff --git a/src/db.h b/src/db.h
index 9dce65a..ae485ee 100644
--- a/src/db.h
+++ b/src/db.h
@@ -118,6 +118,8 @@ struct db_filter_attr {
 	uint32_t log_enable;
 	/* SPEC_ALLOW related attributes */
 	uint32_t spec_allow;
+	/* SCMP_FLTATR_CTL_OPTIMIZE related attributes */
+	uint32_t optimize;
 };
 
 struct db_filter {
@@ -126,6 +128,7 @@ struct db_filter {
 
 	/* syscall filters, kept as a sorted single-linked list */
 	struct db_sys_list *syscalls;
+	unsigned int syscall_cnt;
 
 	/* list of rules used to build the filters, kept in order */
 	struct db_api_rule_list *rules;
diff --git a/src/gen_bpf.c b/src/gen_bpf.c
index cebfaaa..55a7958 100644
--- a/src/gen_bpf.c
+++ b/src/gen_bpf.c
@@ -21,6 +21,7 @@
 
 #include <errno.h>
 #include <inttypes.h>
+#include <limits.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -45,6 +46,11 @@
 #define AINC_BLK			2
 #define AINC_PROG			64
 
+/* binary tree definitions */
+#define SYSCALLS_PER_NODE		(4)
+#define BTREE_HSH_INVALID		(UINT64_MAX)
+#define BTREE_SYSCALL_INVALID		(UINT_MAX)
+
 struct acc_state {
 	int32_t offset;
 	uint32_t mask;
@@ -1147,6 +1153,50 @@ chain_failure:
 }
 
 /**
+ * Sort the syscalls by syscall number
+ * @param syscalls the linked list of syscalls to be sorted
+ * @param s_head the head of the linked list to be returned to the caller
+ * @param s_tail the tail of the linked list to be returned to the caller
+ */
+static void _sys_num_sort(struct db_sys_list *syscalls,
+			  struct db_sys_list **s_head,
+			  struct db_sys_list **s_tail)
+{
+	struct db_sys_list *s_iter, *s_iter_b;
+
+	db_list_foreach(s_iter, syscalls) {
+		if (*s_head != NULL) {
+			s_iter_b = *s_head;
+			while ((s_iter_b->pri_nxt != NULL) &&
+			       (s_iter->num <= s_iter_b->num))
+				s_iter_b = s_iter_b->pri_nxt;
+
+			if (s_iter->num > s_iter_b->num) {
+				s_iter->pri_prv = s_iter_b->pri_prv;
+				s_iter->pri_nxt = s_iter_b;
+				if (s_iter_b == *s_head) {
+					(*s_head)->pri_prv = s_iter;
+					*s_head = s_iter;
+				} else {
+					s_iter->pri_prv->pri_nxt = s_iter;
+					s_iter->pri_nxt->pri_prv = s_iter;
+				}
+			} else {
+				s_iter->pri_prv = *s_tail;
+				s_iter->pri_nxt = NULL;
+				s_iter->pri_prv->pri_nxt = s_iter;
+				*s_tail = s_iter;
+			}
+		} else {
+			*s_head = s_iter;
+			*s_tail = s_iter;
+			(*s_head)->pri_prv = NULL;
+			(*s_head)->pri_nxt = NULL;
+		}
+	}
+}
+
+/**
  * Sort the syscalls by priority
  * @param syscalls the linked list of syscalls to be sorted
  * @param s_head the head of the linked list to be returned to the caller
@@ -1191,6 +1241,27 @@ static void _sys_priority_sort(struct db_sys_list *syscalls,
 }
 
 /**
+ * Sort the syscalls
+ * @param syscalls the linked list of syscalls to be sorted
+ * @param s_head the head of the linked list to be returned to the caller
+ * @param s_tail the tail of the linked list to be returned to the caller
+ *
+ * Wrapper function for sorting syscalls
+ *
+ */
+static void _sys_sort(struct db_sys_list *syscalls,
+		      struct db_sys_list **s_head,
+		      struct db_sys_list **s_tail,
+		      uint32_t optimize)
+{
+	if (optimize != 2)
+		_sys_priority_sort(syscalls, s_head, s_tail);
+	else
+		/* sort by number for the binary tree */
+		_sys_num_sort(syscalls, s_head, s_tail);
+}
+
+/**
  * Insert an instruction into the BPF state and connect the linked list
  * @param state the BPF state
  * @param instr the instruction to insert
@@ -1221,6 +1292,136 @@ static int _gen_bpf_insert(struct bpf_state *state, struct bpf_instr *instr,
 }
 
 /**
+ * Calculate the number of levels in the binary tree
+ * @param syscall_cnt the number of syscalls in this seccomp filter
+ */
+static int _get_bintree_levels(unsigned int syscall_cnt)
+{
+	unsigned int i = 2, max_level = SYSCALLS_PER_NODE * 2;
+
+	while (max_level < syscall_cnt) {
+		max_level <<= 1;
+		i++;
+	}
+
+	return i;
+}
+
+/**
+ * Initialize the binary tree
+ * @param bintree_hashes Array of hashes that store binary tree jump dests
+ * @param bintree_syscalls Array of syscalls for the binary tree "if > " logic
+ * @param bintree_levels Number of levels in the binary tree
+ * @param syscall_cnt Number of syscalls in this filter
+ * @param empty_cnt Number of empty slots needed to balance the tree
+ *
+ */
+static int _gen_bpf_init_bintree(uint64_t **bintree_hashes,
+				 unsigned int **bintree_syscalls,
+				 unsigned int *bintree_levels,
+				 unsigned int syscall_cnt,
+				 unsigned int *empty_cnt)
+{
+	int i;
+
+	*bintree_levels = _get_bintree_levels(syscall_cnt);
+
+	if (*bintree_levels > 0) {
+		*empty_cnt = ((unsigned int)(SYSCALLS_PER_NODE * 2) <<
+			      ((*bintree_levels) - 1)) - syscall_cnt;
+		*bintree_hashes = zmalloc(sizeof(uint64_t) *
+					  (*bintree_levels));
+		if (bintree_hashes == NULL)
+			return -ENOMEM;
+
+		*bintree_syscalls = zmalloc(sizeof(unsigned int) *
+					    (*bintree_levels));
+		if (bintree_syscalls == NULL)
+			return -ENOMEM;
+
+		for (i = 0; i < *bintree_levels; i++) {
+			(*bintree_syscalls)[i] = BTREE_SYSCALL_INVALID;
+			(*bintree_hashes)[i] = BTREE_HSH_INVALID;
+		}
+	}
+
+	return 0;
+}
+
+/**
+ * Generate the binary tree
+ * @param state the BPF state
+ * @param bintree_hashes Array of hashes that store binary tree jump dests
+ * @param bintree_syscalls Array of syscalls for the binary tree "if > " logic
+ * @param bintree_levels Number of levels in the binary tree
+ * @param total_cnt Total number of syscalls and empty slots in the bintree
+ * @param cur_syscall Current syscall being processed
+ * @param blks_added Number of BPF blocks added by this function
+ *
+ * Generate the BPF instruction blocks for the binary tree for cur_syscall.
+ * If this syscall is at the end of the node, then this function will
+ * create the requisite ifs and elses for the tree.
+ */
+static int _gen_bpf_bintree(struct bpf_state *state, uint64_t *bintree_hashes,
+			    unsigned int *bintree_syscalls,
+			    unsigned int bintree_levels,
+			    unsigned int total_cnt, unsigned int cur_syscall,
+			    unsigned int *blks_added)
+{
+	struct bpf_blk *b_bintree = NULL;
+	struct bpf_instr instr;
+	unsigned int level;
+	int rc = 0, i, j;
+
+	for (i = bintree_levels - 1; i >= 0; i--) {
+		level = SYSCALLS_PER_NODE << i;
+
+		if ((total_cnt % level) == 0) {
+			/* save the "if greater than" syscall num */
+			bintree_syscalls[i] = cur_syscall;
+			/* save the hash for the jf case */
+			bintree_hashes[i] = state->b_new->hash;
+
+			for (j = 0; j < i; j++) {
+				if (bintree_syscalls[j] == BTREE_SYSCALL_INVALID ||
+				    bintree_hashes[j] == BTREE_HSH_INVALID)
+					/* we are near the end of the binary
+					 * tree and the jump-to location is
+					 * not valid.  skip this if-else
+					 */
+					continue;
+
+				_BPF_INSTR(instr,
+					   _BPF_OP(state->arch, BPF_JMP + BPF_JGT),
+					   _BPF_JMP_NO,
+					   _BPF_JMP_NO,
+					   _BPF_K(state->arch, bintree_syscalls[j]));
+				instr.jt = _BPF_JMP_HSH(b_bintree == NULL ?
+							state->b_new->hash : b_bintree->hash);
+				instr.jf = _BPF_JMP_HSH(bintree_hashes[j]);
+				(*blks_added)++;
+
+				rc = _gen_bpf_insert(state, &instr,
+						     &b_bintree, &state->b_head, NULL);
+				if (rc < 0)
+					goto out;
+			}
+
+			if (b_bintree != NULL)
+				/* this is the last if in this "block".
+				 * save it off so the next binary tree
+				 * if can "else" to it.
+				 */
+				bintree_hashes[j] = b_bintree->hash;
+			break;
+		}
+	}
+
+out:
+	return rc;
+}
+
+/**
  * Generate the BPF instruction blocks for a given syscall
  * @param state the BPF state
  * @param sys the syscall filter DB entry
@@ -1308,9 +1509,13 @@ static struct bpf_blk *_gen_bpf_syscall(struct bpf_state *state,
 static int _gen_bpf_syscalls(struct bpf_state *state,
 			     const struct db_filter *db,
 			     const struct db_filter *db_secondary,
-			     unsigned int *blks_added)
+			     unsigned int *blks_added, uint32_t optimize,
+			     unsigned int *bintree_levels)
 {
 	struct db_sys_list *s_head = NULL, *s_tail = NULL, *s_iter;
+	unsigned int syscall_cnt = 0, empty_cnt = 0;
+	uint64_t *bintree_hashes = NULL, nxt_hsh;
+	unsigned int *bintree_syscalls = NULL;
 	bool acc_reset;
 	int rc = 0;
 
@@ -1322,9 +1527,17 @@ static int _gen_bpf_syscalls(struct bpf_state *state,
 	*blks_added = 0;
 
 	/* sort the syscall list */
-	_sys_priority_sort(db->syscalls, &s_head, &s_tail);
+	_sys_sort(db->syscalls, &s_head, &s_tail, optimize);
 	if (db_secondary != NULL)
-		_sys_priority_sort(db_secondary->syscalls, &s_head, &s_tail);
+		_sys_sort(db_secondary->syscalls, &s_head, &s_tail, optimize);
+
+	if (optimize == 2) {
+		rc = _gen_bpf_init_bintree(&bintree_hashes, &bintree_syscalls,
+					   bintree_levels, db->syscall_cnt,
+					   &empty_cnt);
+		if (rc < 0)
+			goto out;
+	}
 
 	if ((state->arch->token == SCMP_ARCH_X86_64 ||
 	     state->arch->token == SCMP_ARCH_X32) && (db_secondary == NULL))
@@ -1332,16 +1545,28 @@ static int _gen_bpf_syscalls(struct bpf_state *state,
 	else
 		acc_reset = true;
 
+	if (*bintree_levels > 0)
+		/* The accumulator is reset when the first bintree "if" is
+		 * generated.
+		 */
+		acc_reset = false;
+
 	/* create the syscall filters and add them to block list group */
 	for (s_iter = s_tail; s_iter != NULL; s_iter = s_iter->pri_prv) {
 		if (!s_iter->valid)
 			continue;
 
+		if (*bintree_levels > 0 &&
+		    ((syscall_cnt + empty_cnt) % SYSCALLS_PER_NODE) == 0)
+			/* This is the last syscall in the node.  go to the
+			 * default hash */
+			nxt_hsh = state->def_hsh;
+		else
+			nxt_hsh = state->b_head == NULL ?
+				  state->def_hsh : state->b_head->hash;
+
 		/* build the syscall filter */
-		state->b_new = _gen_bpf_syscall(state, s_iter,
-						(state->b_head == NULL ?
-						 state->def_hsh :
-						 state->b_head->hash),
+		state->b_new = _gen_bpf_syscall(state, s_iter, nxt_hsh,
 						(s_iter == s_head ?
 						 acc_reset : false));
 		if (state->b_new == NULL)
@@ -1361,9 +1586,26 @@ static int _gen_bpf_syscalls(struct bpf_state *state,
 		if (state->b_tail->next != NULL)
 			state->b_tail = state->b_tail->next;
 		(*blks_added)++;
+		syscall_cnt++;
+
+		/* build the binary tree if and else logic */
+		if (*bintree_levels > 0) {
+			rc = _gen_bpf_bintree(state, bintree_hashes,
+					      bintree_syscalls,
+					      *bintree_levels,
+					      syscall_cnt + empty_cnt,
+					      s_iter->num, blks_added);
+			if (rc < 0)
+				goto out;
+		}
 	}
 
 out:
+	if (bintree_hashes != NULL)
+		free(bintree_hashes);
+	if (bintree_syscalls != NULL)
+		free(bintree_syscalls);
+
 	return rc;
 }
 
@@ -1381,21 +1623,37 @@ out:
  */
 static struct bpf_blk *_gen_bpf_arch(struct bpf_state *state,
 				     const struct db_filter *db,
-				     const struct db_filter *db_secondary)
+				     const struct db_filter *db_secondary,
+				     uint32_t optimize)
 {
 	int rc;
-	unsigned int blk_cnt = 0, blks_added = 0;
+	unsigned int blk_cnt = 0, blks_added = 0, bintree_levels = 0;
 	struct bpf_instr instr;
-	struct bpf_blk *b_iter;
+	struct bpf_blk *b_iter, *b_bintree;
 
 	state->arch = db->arch;
 
 	/* create the syscall filters and add them to block list group */
-	rc = _gen_bpf_syscalls(state, db, db_secondary, &blks_added);
+	rc = _gen_bpf_syscalls(state, db, db_secondary, &blks_added, optimize,
+			       &bintree_levels);
 	if (rc < 0)
 		goto arch_failure;
 	blk_cnt += blks_added;
 
+	if (bintree_levels > 0) {
+		_BPF_INSTR(instr, _BPF_OP(state->arch, BPF_LD + BPF_ABS),
+			   _BPF_JMP_NO, _BPF_JMP_NO,
+			   _BPF_SYSCALL(state->arch));
+		blk_cnt++;
+
+		rc = _gen_bpf_insert(state, &instr, &b_bintree,
+				     &state->b_head, NULL);
+		if (rc < 0)
+			goto arch_failure;
+		b_bintree->acc_start = _ACC_STATE_UNDEF;
+		b_bintree->acc_end = _ACC_STATE_OFFSET(_BPF_OFFSET_SYSCALL);
+	}
+
 	/* additional ABI filtering */
 	if ((state->arch->token == SCMP_ARCH_X86_64 ||
 	     state->arch->token == SCMP_ARCH_X32) && (db_secondary == NULL)) {
@@ -1752,7 +2010,8 @@ static int _gen_bpf_build_bpf(struct bpf_state *state,
 			db_secondary = NULL;
 
 		/* create the filter for the architecture(s) */
-		b_new = _gen_bpf_arch(state, col->filters[iter], db_secondary);
+		b_new = _gen_bpf_arch(state, col->filters[iter], db_secondary,
+				      col->attr.optimize);
 		if (b_new == NULL)
 			return -ENOMEM;
 		b_new->prev = b_tail;
diff --git a/src/gen_pfc.c b/src/gen_pfc.c
index 8186f0d..767845f 100644
--- a/src/gen_pfc.c
+++ b/src/gen_pfc.c
@@ -243,68 +243,163 @@ static void _gen_pfc_chain(const struct arch_def *arch,
  *
  */
 static void _gen_pfc_syscall(const struct arch_def *arch,
-			     const struct db_sys_list *sys, FILE *fds)
+			     const struct db_sys_list *sys, FILE *fds,
+			     int lvl)
 {
 	unsigned int sys_num = sys->num;
 	const char *sys_name = arch_syscall_resolve_num(arch, sys_num);
 
-	_indent(fds, 1);
+	_indent(fds, lvl);
 	fprintf(fds, "# filter for syscall \"%s\" (%u) [priority: %d]\n",
 		(sys_name ? sys_name : "UNKNOWN"), sys_num, sys->priority);
-	_indent(fds, 1);
+	_indent(fds, lvl);
 	fprintf(fds, "if ($syscall == %u)\n", sys_num);
 	if (sys->chains == NULL) {
-		_indent(fds, 2);
+		_indent(fds, lvl + 1);
 		_pfc_action(fds, sys->action);
 	} else
-		_gen_pfc_chain(arch, sys->chains, 2, fds);
+		_gen_pfc_chain(arch, sys->chains, lvl + 1, fds);
 }
 
-/**
- * Generate pseudo filter code for an architecture
- * @param col the seccomp filter collection
- * @param db the single seccomp filter
- * @param fds the file stream to send the output
- *
- * This function generates a pseudo filter code representation of the given
- * filter DB and writes it to the given output stream.  Returns zero on
- * success, negative values on failure.
- *
- */
-static int _gen_pfc_arch(const struct db_filter_col *col,
-			 const struct db_filter *db, FILE *fds)
+#define SYSCALLS_PER_NODE		(4)
+static int _get_bintree_levels(unsigned int syscall_cnt,
+			       uint32_t optimize)
 {
-	int rc = 0;
+	unsigned int i = 0, max_level;
+
+	if (optimize != 2)
+		/* Only use a binary tree if requested */
+		return 0;
+
+	do {
+		max_level = SYSCALLS_PER_NODE << i;
+		i++;
+	} while(max_level < syscall_cnt);
+
+	return i;
+}
+
+static int _get_bintree_syscall_num(const struct pfc_sys_list *cur,
+				    int lookahead_cnt,
+				    int *const num)
+{
+	while (lookahead_cnt > 0 && cur != NULL) {
+		cur = cur->next;
+		lookahead_cnt--;
+	}
+
+	if (cur == NULL)
+		return -EINVAL;
+
+	*num = cur->sys->num;
+	return 0;
+}
+
+static int _sys_num_sort(struct db_sys_list *syscalls,
+			 struct pfc_sys_list **p_head)
+{
+	struct pfc_sys_list *p_iter = NULL, *p_new, *p_prev;
 	struct db_sys_list *s_iter;
-	struct pfc_sys_list *p_iter = NULL, *p_new, *p_head = NULL, *p_prev;
 
-	/* sort the syscall list */
-	db_list_foreach(s_iter, db->syscalls) {
+	db_list_foreach(s_iter, syscalls) {
 		p_new = zmalloc(sizeof(*p_new));
 		if (p_new == NULL) {
-			rc = -ENOMEM;
-			goto arch_return;
+			return -ENOMEM;
 		}
 		p_new->sys = s_iter;
 
 		p_prev = NULL;
-		p_iter = p_head;
+		p_iter = *p_head;
+		while (p_iter != NULL &&
+		       s_iter->num < p_iter->sys->num) {
+			p_prev = p_iter;
+			p_iter = p_iter->next;
+		}
+		if (*p_head == NULL)
+			*p_head = p_new;
+		else if (p_prev == NULL) {
+			p_new->next = *p_head;
+			*p_head = p_new;
+		} else {
+			p_new->next = p_iter;
+			p_prev->next = p_new;
+		}
+	}
+
+	return 0;
+}
+
+static int _sys_priority_sort(struct db_sys_list *syscalls,
+			      struct pfc_sys_list **p_head)
+{
+	struct pfc_sys_list *p_iter = NULL, *p_new, *p_prev;
+	struct db_sys_list *s_iter;
+
+	db_list_foreach(s_iter, syscalls) {
+		p_new = zmalloc(sizeof(*p_new));
+		if (p_new == NULL) {
+			return -ENOMEM;
+		}
+		p_new->sys = s_iter;
+
+		p_prev = NULL;
+		p_iter = *p_head;
 		while (p_iter != NULL &&
 		       s_iter->priority < p_iter->sys->priority) {
 			p_prev = p_iter;
 			p_iter = p_iter->next;
 		}
-		if (p_head == NULL)
-			p_head = p_new;
+		if (*p_head == NULL)
+			*p_head = p_new;
 		else if (p_prev == NULL) {
-			p_new->next = p_head;
-			p_head = p_new;
+			p_new->next = *p_head;
+			*p_head = p_new;
 		} else {
 			p_new->next = p_iter;
 			p_prev->next = p_new;
 		}
 	}
 
+	return 0;
+}
+
+static int _sys_sort(struct db_sys_list *syscalls,
+		     struct pfc_sys_list **p_head,
+		     uint32_t optimize)
+{
+	if (optimize != 2)
+		return _sys_priority_sort(syscalls, p_head);
+	else
+		/* sort by number for the binary tree */
+		return _sys_num_sort(syscalls, p_head);
+}
+
+/**
+ * Generate pseudo filter code for an architecture
+ * @param col the seccomp filter collection
+ * @param db the single seccomp filter
+ * @param fds the file stream to send the output
+ *
+ * This function generates a pseudo filter code representation of the given
+ * filter DB and writes it to the given output stream.  Returns zero on
+ * success, negative values on failure.
+ *
+ */
+static int _gen_pfc_arch(const struct db_filter_col *col,
+			 const struct db_filter *db, FILE *fds,
+			 uint32_t optimize)
+{
+	int rc = 0, i = 0, lookahead_num;
+	unsigned int syscall_cnt = 0, bintree_levels, level, indent = 1;
+	struct pfc_sys_list *p_iter = NULL, *p_head = NULL;
+
+	/* sort the syscall list */
+	rc = _sys_sort(db->syscalls, &p_head, optimize);
+	if (rc < 0)
+		goto arch_return;
+
+	bintree_levels = _get_bintree_levels(db->syscall_cnt, optimize);
+
 	fprintf(fds, "# filter for arch %s (%u)\n",
 		_pfc_arch(db->arch), db->arch->token_bpf);
 	fprintf(fds, "if ($arch == %u)\n", db->arch->token_bpf);
@@ -314,8 +409,40 @@ static int _gen_pfc_arch(const struct db_filter_col *col,
 			p_iter = p_iter->next;
 			continue;
 		}
-		_gen_pfc_syscall(db->arch, p_iter->sys, fds);
+
+		for (i = bintree_levels - 1; i > 0; i--) {
+			level = SYSCALLS_PER_NODE << i;
+
+			if (syscall_cnt == 0 || (syscall_cnt % level) == 0) {
+				rc = _get_bintree_syscall_num(p_iter, level / 2,
+							      &lookahead_num);
+				if (rc < 0)
+					/* We have reached the end of the bintree.
+					 * There aren't enough syscalls to construct
+					 * any more if-elses.
+					 */
+					continue;
+				_indent(fds, indent);
+				fprintf(fds, "if ($syscall > %u)\n", lookahead_num);
+				indent++;
+			} else if ((syscall_cnt % (level / 2)) == 0) {
+				lookahead_num = p_iter->sys->num;
+				_indent(fds, indent - 1);
+				fprintf(fds, "else # ($syscall <= %u)\n",
+					p_iter->sys->num);
+			}
+
+		}
+
+		_gen_pfc_syscall(db->arch, p_iter->sys, fds, indent);
+		syscall_cnt++;
 		p_iter = p_iter->next;
+
+		/* undo the indentations as the else statements complete */
+		for (i = 0; i < bintree_levels; i++) {
+			if (syscall_cnt % ((SYSCALLS_PER_NODE * 2) << i) == 0)
+				indent--;
+		}
 	}
 	_indent(fds, 1);
 	fprintf(fds, "# default action\n");
@@ -330,7 +457,6 @@ arch_return:
 	}
 	return rc;
 }
-
 /**
  * Generate a pseudo filter code string representation
  * @param col the seccomp filter collection
@@ -363,7 +489,8 @@ int gen_pfc_generate(const struct db_filter_col *col, int fd)
 	fprintf(fds, "#\n");
 
 	for (iter = 0; iter < col->filter_cnt; iter++)
-		_gen_pfc_arch(col, col->filters[iter], fds);
+		_gen_pfc_arch(col, col->filters[iter], fds,
+			      col->attr.optimize);
 
 	fprintf(fds, "# invalid architecture action\n");
 	_pfc_action(fds, col->attr.act_badarch);
diff --git a/src/python/libseccomp.pxd b/src/python/libseccomp.pxd
index f1194b6..b970318 100644
--- a/src/python/libseccomp.pxd
+++ b/src/python/libseccomp.pxd
@@ -61,6 +61,7 @@ cdef extern from "seccomp.h":
         SCMP_FLTATR_API_TSKIP
         SCMP_FLTATR_CTL_LOG
         SCMP_FLTATR_CTL_SSB
+        SCMP_FLTATR_CTL_OPTIMIZE
 
     cdef enum scmp_compare:
         SCMP_CMP_NE
diff --git a/src/python/seccomp.pyx b/src/python/seccomp.pyx
index 113fbf4..d7c1bb1 100644
--- a/src/python/seccomp.pyx
+++ b/src/python/seccomp.pyx
@@ -326,6 +326,7 @@ cdef class Attr:
     API_TSKIP = libseccomp.SCMP_FLTATR_API_TSKIP
     CTL_LOG = libseccomp.SCMP_FLTATR_CTL_LOG
     CTL_SSB = libseccomp.SCMP_FLTATR_CTL_SSB
+    CTL_OPTIMIZE = libseccomp.SCMP_FLTATR_CTL_OPTIMIZE
 
 cdef class Arg:
     """ Python object representing a SyscallFilter syscall argument.