db: perform sub-tree "pruning" correctly

The existing sub-tree pruning was bad, so very bad.  It was obviously
broken on 32-bit platforms (our own tests were failing), and somewhat
less obviously broken on 64-bit platforms.

Reported-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Paul Moore <pmoore@redhat.com>

2 files changed, 182 insertions, 97 deletions

diff --git a/src/db.c b/src/db.c
index 29d94c8..ff73741 100644
--- a/src/db.c
+++ b/src/db.c
@@ -42,6 +42,13 @@
 #define _DB_PRI_MASK_USER		0x00FF0000
 #define _DB_PRI_USER(x)			(((x) << 16) & _DB_PRI_MASK_USER)
 
+/* private structure for tracking the state of the sub-tree "pruning" */
+struct db_prune_state {
+	bool prefix_exist;
+	bool prefix_new;
+	bool matched;
+};
+
 static unsigned int _db_tree_free(struct db_arg_chain_tree *tree);
 
 /**
@@ -91,8 +98,7 @@ static unsigned int _db_tree_free(struct db_arg_chain_tree *tree)
  * @param node the node to remove
  *
  * 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
- * as a result of removing the given node.  Returns the number of nodes freed.
+ * found.  Returns the number of nodes freed.
  *
  */
 static unsigned int _db_tree_remove(struct db_arg_chain_tree **tree,
@@ -109,7 +115,7 @@ static unsigned int _db_tree_remove(struct db_arg_chain_tree **tree,
 		c_iter = c_iter->lvl_prv;
 
 	do {
-		if (c_iter == node) {
+		if (c_iter == node || db_chain_zombie(c_iter)) {
 			/* remove from the tree */
 			if (c_iter == *tree) {
 				if (c_iter->lvl_prv != NULL)
@@ -181,71 +187,162 @@ static int _db_tree_act_check(struct db_arg_chain_tree *tree, uint32_t action)
 }
 
 /**
- * Checks for a sub-tree match in an existing tree and prunes the leaves
- * @param tree_head the head of the existing tree
- * @param tree_start the starting point into the existing tree
- * @param new_p pointer to the new tree
- * @param remove_flg removal flag, only valid on return if return >= 0
+ * Checks for a sub-tree match in an existing tree and prunes the tree
+ * @param prev the head of the existing tree or sub-tree
+ * @param existing the starting point into the existing tree
+ * @param new pointer to the new tree
+ * @param state pointer to the pruning state
  *
- * This function searches the existing tree for an occurance of the new tree
- * and removes as much of it as possible.  Returns the number of nodes removed
- * from the tree on success, and negative values on failure.
+ * This function searches the existing and new trees trying to prune each to
+ * eliminate redundancy.  Returns the number of nodes removed from the tree on
+ * success, zero if no changes were made, and negative values if the new tree
+ * should be discarded.
  *
  */
-static int _db_tree_sub_prune(struct db_arg_chain_tree **tree_head,
-			      struct db_arg_chain_tree *tree_start,
-			      struct db_arg_chain_tree *new,
-			      bool *remove_flg)
+static int _db_tree_sub_prune(struct db_arg_chain_tree **prev,
+			       struct db_arg_chain_tree *existing,
+			       struct db_arg_chain_tree *new,
+			       struct db_prune_state *state)
 {
 	int rc = 0;
-	struct db_arg_chain_tree *c_iter = tree_start;
-
-	*remove_flg = false;
+	int rc_tmp;
+	struct db_arg_chain_tree *ec_iter;
+	struct db_arg_chain_tree *ec_iter_tmp;
+	struct db_arg_chain_tree *c_iter;
+	struct db_prune_state state_new;
 
-	if (new == NULL || c_iter == NULL)
+	if (!state || !existing || !new)
 		return 0;
 
-	while (c_iter->lvl_prv != NULL)
-		c_iter = c_iter->lvl_prv;
+	ec_iter = existing;
+	c_iter = new;
 	do {
-		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 = true;
-			} 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 = true;
-			} 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;
+		if (db_chain_eq(ec_iter, c_iter)) {
+			/* equal */
+
+			if (db_chain_leaf(c_iter)) {
+				/* leaf */
+				if (db_chain_eq_result(ec_iter, c_iter)) {
+					/* identical results */
+					if (prev != NULL)
+						return _db_tree_remove(prev,
+								       ec_iter);
+					else
+						return -1;
+				}
+				if (c_iter->act_t_flg && ec_iter->nxt_t) {
+					/* new is shorter (true) */
+					if (prev == NULL)
+						return -1;
+					rc += _db_tree_remove(&(ec_iter->nxt_t),
+							      ec_iter->nxt_t);
+					ec_iter->act_t = c_iter->act_t;
+					ec_iter->act_t_flg = true;
+				}
+				if (c_iter->act_f_flg && ec_iter->nxt_f) {
+					/* new is shorter (false) */
+					if (prev == NULL)
+						return -1;
+					rc += _db_tree_remove(&(ec_iter->nxt_f),
+							      ec_iter->nxt_f);
+					ec_iter->act_f = c_iter->act_f;
+					ec_iter->act_f_flg = true;
+				}
 
-		c_iter = c_iter->lvl_nxt;
-	} while (c_iter != NULL);
+				return rc;
+			}
+
+			if (c_iter->nxt_t && ec_iter->act_t_flg)
+				/* existing is shorter (true) */
+				return -1;
+			if (c_iter->nxt_f && ec_iter->act_f_flg)
+				/* existing is shorter (false) */
+				return -1;
+
+			if (c_iter->nxt_t) {
+				state_new = *state;
+				state_new.matched = true;
+				rc_tmp = _db_tree_sub_prune((prev ?
+							     &ec_iter : NULL),
+							    ec_iter->nxt_t,
+							    c_iter->nxt_t,
+							    &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+				if (state->prefix_new && rc_tmp < 0)
+					return (rc > 0 ? rc : rc_tmp);
+			}
+			if (c_iter->nxt_f) {
+				state_new = *state;
+				state_new.matched = true;
+				rc_tmp = _db_tree_sub_prune((prev ?
+							     &ec_iter : NULL),
+							    ec_iter->nxt_f,
+							    c_iter->nxt_f,
+							    &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+				if (state->prefix_new && rc_tmp < 0)
+					return (rc > 0 ? rc : rc_tmp);
+			}
+		} else if (db_chain_lt(ec_iter, c_iter)) {
+			/* less than */
+			if (state->matched || state->prefix_new)
+				goto next;
+			state_new = *state;
+			state_new.prefix_exist = true;
+
+			if (ec_iter->nxt_t) {
+				rc_tmp = _db_tree_sub_prune((prev ?
+							      &ec_iter : NULL),
+							     ec_iter->nxt_t,
+							     c_iter,
+							     &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+			}
+			if (ec_iter->nxt_f) {
+				rc_tmp = _db_tree_sub_prune((prev ?
+							     &ec_iter : NULL),
+							    ec_iter->nxt_f,
+							    c_iter,
+							    &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+			}
+		} else if (db_chain_gt(ec_iter, c_iter)) {
+			/* greater than */
+			if (state->matched || state->prefix_exist)
+				goto next;
+			state_new = *state;
+			state_new.prefix_new = true;
+
+			if (c_iter->nxt_t) {
+				rc_tmp = _db_tree_sub_prune(NULL,
+							    ec_iter,
+							    c_iter->nxt_t,
+							    &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+				if (rc_tmp < 0)
+					return (rc > 0 ? rc : rc_tmp);
+			}
+			if (c_iter->nxt_f) {
+				rc_tmp = _db_tree_sub_prune(NULL,
+							    ec_iter,
+							    c_iter->nxt_f,
+							    &state_new);
+				rc += (rc_tmp > 0 ? rc_tmp : 0);
+				if (rc_tmp < 0)
+					return (rc > 0 ? rc : rc_tmp);
+			}
+		}
+
+next:
+		/* re-check current node and advance to the next node */
+		if (db_chain_zombie(ec_iter)) {
+			ec_iter_tmp = ec_iter->lvl_nxt;
+			rc += _db_tree_remove(prev, ec_iter);
+			ec_iter = ec_iter_tmp;
+		} else
+			ec_iter = ec_iter->lvl_nxt;
+	} while (ec_iter);
 
-sub_prune_return:
-	if (rc > 0)
-		*remove_flg = true;
 	return rc;
 }
 
@@ -960,7 +1057,8 @@ int db_rule_add(struct db_filter *db, uint32_t action, unsigned int syscall,
 	int rc = -ENOMEM;
 	struct db_sys_list *s_new, *s_iter, *s_prev = NULL;
 	struct db_arg_chain_tree *c_iter = NULL, *c_prev = NULL;
-	struct db_arg_chain_tree *ec_iter, *ec_iter_b;
+	struct db_arg_chain_tree *ec_iter;
+	struct db_prune_state state;
 	bool rm_flag = false;
 	unsigned int new_chain_cnt = 0;
 	unsigned int n_cnt;
@@ -1037,41 +1135,26 @@ add_reset:
 		s_iter->action = action;
 		goto add_free_ok;
 	}
+
+	/* check for sub-tree matches */
+	memset(&state, 0, sizeof(state));
+	rc = _db_tree_sub_prune(&(s_iter->chains), ec_iter, c_iter, &state);
+	if (rc > 0) {
+		rm_flag = true;
+		s_iter->node_cnt -= rc;
+		goto add_reset;
+	} else if (rc < 0)
+		goto add_free_ok;
+
 	/* syscall exists and has at least one existing chain - start at the
 	 * top and walk the two chains */
 	do {
-		/* 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) {
-			s_iter->node_cnt -= rc;
-			goto add_reset;
-		} else if (rc < 0)
-			goto add_free;
-
-		/* check for sub-tree matches in the new tree */
-		ec_iter_b = ec_iter;
-		while (ec_iter_b->lvl_prv != NULL)
-			ec_iter_b = ec_iter_b->lvl_prv;
-		do {
-			rc = _db_tree_sub_prune(&(s_new->chains),
-						c_iter, ec_iter_b, &rm_flag);
-			ec_iter_b = ec_iter_b->lvl_nxt;
-		} while (rc == 0 && ec_iter_b != NULL);
-		if (rc > 0) {
-			s_new->node_cnt -= rc;
-			if (s_new->node_cnt > 0)
-				goto add_reset;
-			rc = 0;
-			goto add_free;
-		} else if (rc < 0)
-			goto add_free;
-
 		/* insert the new rule into the existing tree */
 		if (db_chain_eq(c_iter, ec_iter)) {
 			/* found a matching node on this chain level */
-			if (db_chain_leaf(c_iter) && db_chain_leaf(ec_iter)) {
-				/* both are leaf nodes */
+			if (db_chain_action(c_iter) &&
+			    db_chain_action(ec_iter)) {
+				/* both are "action" nodes */
 				if (c_iter->act_t_flg && ec_iter->act_t_flg) {
 					if (ec_iter->act_t != action)
 						goto add_free_exist;
@@ -1092,9 +1175,9 @@ add_reset:
 							     &(s_iter->chains),
 							     ec_iter);
 					s_iter->node_cnt -= n_cnt;
+					goto add_free_ok;
 				}
-				goto add_free_ok;
-			} else if (db_chain_leaf(c_iter)) {
+			} else if (db_chain_action(c_iter)) {
 				/* new is shorter */
 				if (c_iter->act_t_flg) {
 					rc = _db_tree_act_check(ec_iter->nxt_t,
@@ -1116,8 +1199,8 @@ add_reset:
 					ec_iter->act_f = action;
 				}
 				s_iter->node_cnt -= n_cnt;
-				goto add_free_ok;
-			} else if (c_iter->nxt_t != NULL) {
+			}
+			if (c_iter->nxt_t != NULL) {
 				if (ec_iter->nxt_t != NULL) {
 					/* jump to the next level */
 					c_prev = c_iter;
@@ -1155,11 +1238,8 @@ add_reset:
 					s_iter->node_cnt += (s_new->node_cnt-1);
 					goto add_free_match;
 				}
-			} else {
-				/* we should never be here! */
-				rc = -EFAULT;
-				goto add_free;
-			}
+			} else
+				goto add_free_ok;
 		} else {
 			/* need to check other nodes on this level */
 			if (db_chain_lt(c_iter, ec_iter)) {
diff --git a/src/db.h b/src/db.h
index d686e03..d0d9ff1 100644
--- a/src/db.h
+++ b/src/db.h
@@ -80,8 +80,13 @@ struct db_arg_chain_tree {
 	(((x)->arg > (y)->arg) || \
 	 (((x)->arg == (y)->arg) && (((x)->op > (y)->op) || \
 	   (((x)->mask & (y)->mask) != (y)->mask))))
-#define db_chain_leaf(x) \
+#define db_chain_action(x) \
 	(((x)->act_t_flg) || ((x)->act_f_flg))
+#define db_chain_zombie(x) \
+	((x)->nxt_t == NULL && !((x)->act_t_flg) && \
+	 (x)->nxt_f == NULL && !((x)->act_f_flg))
+#define db_chain_leaf(x) \
+	((x)->nxt_t == NULL && (x)->nxt_f == NULL)
 #define db_chain_eq_result(x,y) \
 	((((x)->nxt_t != NULL && (y)->nxt_t != NULL) || \
 	  ((x)->nxt_t == NULL && (y)->nxt_t == NULL)) && \