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>

1 files changed, 5 insertions, 0 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,
 };