[apparmor] [PATCH 4/4] Move rule simplification into the tree construction phase

[John Johansen]

The current rule simplification algorithm has issues that need to be
addressed in a rewrite, but it is still often a win, especially for
larger profiles.

However doing rule simplification as a single pass limits what it can
do. We default to right simplification first because this has historically
shown the most benefits. For two reasons
  1. It allowed better grouping of the split out accept nodes that we
     used to do (changed in previous patches)
  2. because trailing regexes like
       /foo/**,
       /foo/**.txt,
     can be combined and they are the largest source of node set
     explosion.

However the move to unique node sets, eliminates 1, and forces 2 to
work within only the single unique permission set on the right side
factoring pass, but it still incures the penalty of walking the whole
tree looking for potential nodes to factor.

Moving tree simplification into the construction phases gets rid of
the need for the right side factoring pass to walk other node sets
that will never combine, and since we are doing simplification we can
do it before the cat and permission nodes are added reducing the
set of nodes to look at by another two.

We do loose the ability to combine nodes from different sets during
the left factoring pass, but experimentation shows that doing
simplification only within the unique permission sets achieve most of
the factoring that a single global pass would achieve.

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/aare_rules.cc | 26 +++++++++++++++++++++++---
 1 file changed, 23 insertions(+), 3 deletions(-)

diff --git a/parser/libapparmor_re/aare_rules.cc b/parser/libapparmor_re/aare_rules.cc
index 578471e..02aa80f 100644
--- a/parser/libapparmor_re/aare_rules.cc
+++ b/parser/libapparmor_re/aare_rules.cc
@@ -136,12 +136,26 @@ void *aare_rules::create_dfa(size_t *size, dfaflags_t flags)
 	 * set nodes */
 	PermExprMap::iterator i = expr_map.begin();
 	if (i != expr_map.end()) {
-		root = new CatNode(i->second, i->first);
+		if (flags & DFA_CONTROL_TREE_SIMPLE) {
+			Node *tmp = simplify_tree(i->second, flags);
+			root = new CatNode(tmp, i->first);
+		} else
+			root = new CatNode(i->second, i->first);
 		for (i++; i != expr_map.end(); i++) {
-			root = new AltNode(root, new CatNode(i->second, i->first));
+			Node *tmp;
+			if (flags & DFA_CONTROL_TREE_SIMPLE) {
+				tmp = simplify_tree(i->second, flags);
+			} else
+				tmp = i->second;
+			root = new AltNode(root, new CatNode(tmp, i->first));
 		}
 	}
 
+	/* dumping of the none simplified tree without -O no-expr-simplify
+	 * is broken because we need to build the tree above first, and
+	 * simplification is woven into the build. Reevaluate how to fix
+	 * this debug dump.
+	 */
 	label_nodes(root);
 	if (flags & DFA_DUMP_TREE) {
 		cerr << "\nDFA: Expression Tree\n";
@@ -150,7 +164,13 @@ void *aare_rules::create_dfa(size_t *size, dfaflags_t flags)
 	}
 
 	if (flags & DFA_CONTROL_TREE_SIMPLE) {
-		root = simplify_tree(root, flags);
+		/* This is old total tree, simplification point
+		 * For now just do simplification up front. It gets most
+		 * of the benefit running on the smaller chains, and is
+		 * overall faster because there are less nodes. Reevaluate
+		 * once tree simplification is rewritten
+		 */
+		//root = simplify_tree(root, flags);
 
 		if (flags & DFA_DUMP_SIMPLE_TREE) {
 			cerr << "\nDFA: Simplified Expression Tree\n";
-- 
2.1.4