db: correctly compare syscall arguments on 64-bit systems

This patch corrects a number of problems on 64-bit systems that were
preventing us from correctly comparing the high 32-bit word of a
syscall argument in some cases.

Reported-by: Thiago Marcos P. Santos <tmpsantos@gmail.com>
Signed-off-by: Paul Moore <pmoore@redhat.com>

8 files changed, 194 insertions, 95 deletions

diff --git a/src/db.c b/src/db.c
index 3a82e1c..7346a57 100644
--- a/src/db.c
+++ b/src/db.c
@@ -89,8 +89,6 @@ static unsigned int _db_tree_free(struct db_arg_chain_tree *tree)
  * Remove a node from an argument chain tree
  * @param tree the pointer to the tree
  * @param node the node to remove
- * @param action_flg the replacement action flag
- * @param action the replacement action
  *
  * This function searches the tree looking for the node and removes it once
  * found.  The function also removes any other nodes that are no longer needed
@@ -98,9 +96,7 @@ static unsigned int _db_tree_free(struct db_arg_chain_tree *tree)
  *
  */
 static unsigned int _db_tree_remove(struct db_arg_chain_tree **tree,
-				    struct db_arg_chain_tree *node,
-				    unsigned int action_flg,
-				    uint32_t action)
+				    struct db_arg_chain_tree *node)
 {
 	int cnt = 0;
 	struct db_arg_chain_tree *c_iter;
@@ -134,10 +130,8 @@ static unsigned int _db_tree_remove(struct db_arg_chain_tree **tree,
 		}
 
 		/* check the true/false sub-trees */
-		cnt += _db_tree_remove(&(c_iter->nxt_t), node,
-				       action_flg, action);
-		cnt += _db_tree_remove(&(c_iter->nxt_f), node,
-				       action_flg, action);
+		cnt += _db_tree_remove(&(c_iter->nxt_t), node);
+		cnt += _db_tree_remove(&(c_iter->nxt_f), node);
 
 		c_iter = c_iter->lvl_nxt;
 	} while (c_iter != NULL);
@@ -210,80 +204,48 @@ static int _db_tree_sub_prune(struct db_arg_chain_tree **tree_head,
 
 	if (new == NULL || c_iter == NULL)
 		return 0;
-	if (!db_chain_one_result(new))
-		return 0;
 
 	while (c_iter->lvl_prv != NULL)
 		c_iter = c_iter->lvl_prv;
-
 	do {
-		if (c_iter->arg < new->arg) {
-			if (c_iter->nxt_t != NULL) {
-				rc = _db_tree_sub_prune(tree_head,
-							c_iter->nxt_t, new,
-							remove_flg);
-				if (rc > 0)
-					goto sub_prune_found_down;
-			}
-			if (c_iter->nxt_f != NULL) {
-				rc = _db_tree_sub_prune(tree_head,
-							c_iter->nxt_f, new,
-							remove_flg);
-				if (rc > 0)
-					goto sub_prune_found_down;
-			}
-		} else if (db_chain_eq(c_iter, new)) {
-			if (db_chain_leaf(new)) {
-				if (!db_chain_one_result(c_iter)) {
-					/* can't remove existing node */
-					if (new->act_t_flg && c_iter->act_t_flg
-					    && new->act_t == c_iter->act_t)
-						c_iter->act_t_flg = 0;
-					if (new->act_f_flg && c_iter->act_f_flg
-					    && new->act_f == c_iter->act_f)
-						c_iter->act_f_flg = 0;
-					goto sub_prune_return;
-				}
-				if ((db_chain_eq_result(c_iter, new)) ||
-				    ((new->act_t_flg && c_iter->nxt_t != NULL)||
-				     (new->act_f_flg && c_iter->nxt_f != NULL)))
-					/* exact or close match - remove node */
-					goto sub_prune_remove;
-				goto sub_prune_return;
-			}
-			if (new->nxt_t != NULL) {
-				rc = _db_tree_sub_prune(tree_head,
-							c_iter->nxt_t,
-							new->nxt_t,
-							remove_flg);
-				if (rc > 0)
-					goto sub_prune_found_down;
-			}
-			if (new->nxt_f != NULL) {
-				rc = _db_tree_sub_prune(tree_head,
-							c_iter->nxt_f,
-							new->nxt_f,
-							remove_flg);
-				if (rc > 0)
-					goto sub_prune_found_down;
-			}
+		if (db_chain_eq(c_iter, new)) {
+			if (new->act_t_flg) {
+				rc += _db_tree_remove(tree_head, c_iter->nxt_t);
+				c_iter->act_t = new->act_t;
+				c_iter->act_t_flg = 1;
+			} else if (new->nxt_t != NULL)
+				rc += _db_tree_sub_prune(tree_head,
+							 c_iter->nxt_t,
+							 new->nxt_t,
+							 remove_flg);
+			if (new->act_f_flg) {
+				rc += _db_tree_remove(tree_head, c_iter->nxt_f);
+				c_iter->act_f = new->act_f;
+				c_iter->act_f_flg = 1;
+			} else if (new->nxt_f != NULL)
+				rc += _db_tree_sub_prune(tree_head,
+							 c_iter->nxt_f,
+							 new->nxt_f,
+							 remove_flg);
+		} else if (db_chain_lt(c_iter, new)) {
+			if (c_iter->nxt_t != NULL)
+				rc += _db_tree_sub_prune(tree_head,
+							 c_iter->nxt_t, new,
+							 remove_flg);
+			if (c_iter->nxt_f != NULL)
+				rc += _db_tree_sub_prune(tree_head,
+							 c_iter->nxt_f, new,
+							 remove_flg);
+
 		} else if (db_chain_gt(c_iter, new))
 			goto sub_prune_return;
 
 		c_iter = c_iter->lvl_nxt;
 	} while (c_iter != NULL);
 
-	goto sub_prune_return;
-
-sub_prune_found_down:
-	if (db_chain_zombie(c_iter))
-		goto sub_prune_remove;
 sub_prune_return:
-	*remove_flg = 0;
-	return rc;
-sub_prune_remove:
-	rc += _db_tree_remove(tree_head, c_iter, 0, 0);
-	*remove_flg = 1;
+	if (rc > 0)
+		*remove_flg = 1;
 	return rc;
 }
 
@@ -768,7 +730,7 @@ static struct db_sys_list *_db_rule_gen_64(const struct arch_def *arch,
 	int chain_len_max;
 	struct db_sys_list *s_new;
 	struct db_arg_chain_tree *c_iter_hi = NULL, *c_iter_lo = NULL;
-	struct db_arg_chain_tree *c_prev_lo = NULL;
+	struct db_arg_chain_tree *c_prev_hi = NULL, *c_prev_lo = NULL;
 	unsigned int tf_flag;
 
 	s_new = malloc(sizeof(*s_new));
@@ -798,10 +760,12 @@ static struct db_sys_list *_db_rule_gen_64(const struct arch_def *arch,
 
 		/* link this level to the previous level */
 		if (c_prev_lo != NULL) {
-			if (tf_flag)
-				c_prev_lo->nxt_t = c_iter_hi;
-			else
+			if (!tf_flag) {
 				c_prev_lo->nxt_f = c_iter_hi;
+				c_prev_hi->nxt_f = c_iter_hi;
+				c_iter_hi->refcnt++;
+			} else
+				c_prev_lo->nxt_t = c_iter_hi;
 		} else
 			s_new->chains = c_iter_hi;
 		s_new->node_cnt += 2;
@@ -851,16 +815,19 @@ static struct db_sys_list *_db_rule_gen_64(const struct arch_def *arch,
 		/* link the hi and lo chain nodes */
 		c_iter_hi->nxt_t = c_iter_lo;
 
+		c_prev_hi = c_iter_hi;
 		c_prev_lo = c_iter_lo;
 	}
 	if (c_iter_lo != NULL) {
 		/* set the leaf node */
-		if (tf_flag) {
-			c_iter_lo->act_t_flg = 1;
-			c_iter_lo->act_t = action;
-		} else {
+		if (!tf_flag) {
 			c_iter_lo->act_f_flg = 1;
 			c_iter_lo->act_f = action;
+			c_iter_hi->act_f_flg = 1;
+			c_iter_hi->act_f = action;
+		} else {
+			c_iter_lo->act_t_flg = 1;
+			c_iter_lo->act_t = action;
 		}
 	} else
 		s_new->action = action;
@@ -1076,12 +1043,11 @@ add_reset:
 		/* check for sub-tree matches in the existing tree */
 		rc = _db_tree_sub_prune(&(s_iter->chains), ec_iter, c_iter,
 					&rm_flag);
-		if (rc > 0)
+		if (rc > 0) {
 			s_iter->node_cnt -= rc;
-		else if (rc < 0)
-			goto add_free;
-		if (rm_flag)
 			goto add_reset;
+		} else if (rc < 0)
+			goto add_free;
 
 		/* check for sub-tree matches in the new tree */
 		ec_iter_b = ec_iter;
@@ -1095,10 +1061,7 @@ add_reset:
 		if (rc > 0) {
 			s_new->node_cnt -= rc;
 			if (s_new->node_cnt > 0)
-				/* XXX - are we ever going to hit this is a
-				 *       normal use case?  pretty sure we can't
-				 *       "reset" in this case ... */
-				return -EFAULT;
+				goto add_reset;
 			rc = 0;
 			goto add_free;
 		} else if (rc < 0)
@@ -1127,9 +1090,7 @@ add_reset:
 				    ec_iter->act_t == ec_iter->act_f) {
 					n_cnt = _db_tree_remove(
 							     &(s_iter->chains),
-							     ec_iter,
-							     1,
-							     ec_iter->act_t);
+							     ec_iter);
 					s_iter->node_cnt -= n_cnt;
 				}
 				goto add_free_ok;
diff --git a/src/db.h b/src/db.h
index 2f1373c..203a0b4 100644
--- a/src/db.h
+++ b/src/db.h
@@ -89,8 +89,6 @@ struct db_arg_chain_tree {
 	 ((x)->nxt_t == NULL && (x)->nxt_f != NULL))
 #define db_chain_one_action(x) \
 	((x)->act_t_flg != (x)->act_f_flg)
-#define db_chain_one_result(x) \
-	(db_chain_one_nxt(x) != db_chain_one_action(x))
 #define db_chain_eq_result(x,y) \
 	((((x)->nxt_t != NULL && (y)->nxt_t != NULL) || \
 	  ((x)->nxt_t == NULL && (y)->nxt_t == NULL)) && \
diff --git a/src/gen_bpf.c b/src/gen_bpf.c
index 01c2709..164e87b 100644
--- a/src/gen_bpf.c
+++ b/src/gen_bpf.c
@@ -1005,9 +1005,13 @@ static struct bpf_blk *_gen_bpf_syscall(struct bpf_state *state,
 	int rc;
 	struct bpf_instr instr;
 	struct bpf_blk *blk_c, *blk_s = NULL;
-	struct bpf_jump def_jump = _BPF_JMP_HSH(state->def_hsh);
+	struct bpf_jump def_jump;
 	struct acc_state a_state;
 
+	/* we do the memset before the assignment to keep valgrind happy */
+	memset(&def_jump, 0, sizeof(def_jump));
+	def_jump = _BPF_JMP_HSH(state->def_hsh);
+
 	/* setup the accumulator state */
 	if (acc_reset) {
 		_BPF_INSTR(instr, BPF_LD+BPF_ABS, _BPF_JMP_NO, _BPF_JMP_NO,
diff --git a/tests/.gitignore b/tests/.gitignore
index 8080469..a9f7e2f 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -25,3 +25,4 @@ util.pyc
 22-sim-basic_chains_array
 23-sim-arch_all_basic
 24-live-arg_allow
+25-sim-multilevel_chains_adv
diff --git a/tests/25-sim-multilevel_chains_adv.c b/tests/25-sim-multilevel_chains_adv.c
new file mode 100644
index 0000000..68c24ac
--- /dev/null
+++ b/tests/25-sim-multilevel_chains_adv.c
@@ -0,0 +1,62 @@
+/**
+ * Seccomp Library test program
+ *
+ * Copyright (c) 2013 Red Hat <pmoore@redhat.com>
+ * Author: Paul Moore <pmoore@redhat.com>
+ */
+
+/*
+ * This library is free software; you can redistribute it and/or modify it
+ * under the terms of version 2.1 of the GNU Lesser General Public License as
+ * published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
+ * for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this library; if not, see <http://www.gnu.org/licenses>.
+ */
+
+#include <stdlib.h>
+
+#include <seccomp.h>
+
+#include "util.h"
+
+int main(int argc, char *argv[])
+{
+	int rc;
+	struct util_options opts;
+	scmp_filter_ctx ctx;
+
+	rc = util_getopt(argc, argv, &opts);
+	if (rc < 0)
+		goto out;
+
+	ctx = seccomp_init(SCMP_ACT_KILL);
+	if (ctx == NULL)
+		goto out;
+
+	rc = seccomp_rule_add_exact(ctx, SCMP_ACT_ALLOW, 10, 2,
+				    SCMP_A0(SCMP_CMP_EQ, 11),
+				    SCMP_A1(SCMP_CMP_NE, 12));
+	if (rc != 0)
+		goto out;
+
+	rc = seccomp_rule_add_exact(ctx, SCMP_ACT_ALLOW, 20, 3,
+				    SCMP_A0(SCMP_CMP_EQ, 21),
+				    SCMP_A1(SCMP_CMP_NE, 22),
+				    SCMP_A2(SCMP_CMP_EQ, 23));
+	if (rc != 0)
+		goto out;
+
+	rc = util_filter_output(&opts, ctx);
+	if (rc)
+		goto out;
+
+out:
+	seccomp_release(ctx);
+	return (rc < 0 ? -rc : rc);
+}
diff --git a/tests/25-sim-multilevel_chains_adv.py b/tests/25-sim-multilevel_chains_adv.py
new file mode 100755
index 0000000..95a673c
--- /dev/null
+++ b/tests/25-sim-multilevel_chains_adv.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python
+
+#
+# Seccomp Library test program
+#
+# Copyright (c) 2013 Red Hat <pmoore@redhat.com>
+# Author: Paul Moore <pmoore@redhat.com>
+#
+
+#
+# This library is free software; you can redistribute it and/or modify it
+# under the terms of version 2.1 of the GNU Lesser General Public License as
+# published by the Free Software Foundation.
+#
+# This library is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
+# for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with this library; if not, see <http://www.gnu.org/licenses>.
+#
+
+import argparse
+import sys
+
+import util
+
+from seccomp import *
+
+def test(args):
+    f = SyscallFilter(KILL)
+    f.add_rule_exactly(ALLOW, 10,
+                       Arg(0, EQ, 11),
+                       Arg(1, NE, 12));
+    f.add_rule_exactly(ALLOW, 20,
+                       Arg(0, EQ, 21),
+                       Arg(1, NE, 22),
+                       Arg(2, EQ, 23));
+    return f
+
+args = util.get_opt()
+ctx = test(args)
+util.filter_output(args, ctx)
+
+# kate: syntax python;
+# kate: indent-mode python; space-indent on; indent-width 4; mixedindent off;
diff --git a/tests/25-sim-multilevel_chains_adv.tests b/tests/25-sim-multilevel_chains_adv.tests
new file mode 100644
index 0000000..d47a23b
--- /dev/null
+++ b/tests/25-sim-multilevel_chains_adv.tests
@@ -0,0 +1,25 @@
+#
+# libseccomp regression test automation data
+#
+# Copyright (c) 2013 Red Hat <pmoore@redhat.com>
+# Author: Paul Moore <pmoore@redhat.com
+#
+
+test type: bpf-sim
+
+# Testname			Arch		Syscall		Arg0		Arg1		Arg2		Arg3	Arg4	Arg5	Result
+25-sim-multilevel_chains_adv	+x86_64		0-9		N		N		N		N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		10		0x0000000b	0x00000000	N		N	N	N	ALLOW
+25-sim-multilevel_chains_adv	+x86_64		10		0x10000000b	0x00000000	N		N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		10		0x0000000b	0x10000000c	N		N	N	N	ALLOW
+25-sim-multilevel_chains_adv	+x86_64		11-19		N		N		N		N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		20		0x00000015	0x00000000	0x00000017	N	N	N	ALLOW
+25-sim-multilevel_chains_adv	+x86_64		20		0x00000015	0x00000016	0x00000017	N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		20		0x100000015	0x00000000	0x00000017	N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		20		0x00000015	0x00000000	0x100000017	N	N	N	KILL
+25-sim-multilevel_chains_adv	+x86_64		21-30		N		N		N		N	N	N	KILL
+
+test type: bpf-sim-fuzz
+
+# Testname			StressCount
+25-sim-multilevel_chains_adv	50
diff --git a/tests/Makefile b/tests/Makefile
index 048e332..3d28827 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -59,7 +59,8 @@ TESTS = 01-sim-allow \
 	21-live-basic_allow \
 	22-sim-basic_chains_array \
 	23-sim-arch_all_basic \
-	24-live-arg_allow
+	24-live-arg_allow \
+	25-sim-multilevel_chains_adv
 
 DEPS_OBJS = $(OBJS:%.o=%.d)
 DEPS_TESTS = $(TESTS:%=%.d)