[apparmor] [PATCH 3/4] Change expr tree construction so that rules are grouped by perms

[John Johansen]

Currently rules are added to the expression tree in order, and then
tree simplification and factoring is done. This forces simplification
to "search" through the tree to find rules with the same permissions
during right factoring, which dependent on ordering of factoring may
not be able to group all rules of the same permissions.

Instead of having tree factoring do the work to regroup rules with the
same permissions, pregroup them as part of the expr tree construction.
And only build the full tree when the dfa is constructed.

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/aare_rules.cc | 18 +++++++++++++++---
 parser/libapparmor_re/aare_rules.h  |  7 +++++--
 2 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/parser/libapparmor_re/aare_rules.cc b/parser/libapparmor_re/aare_rules.cc
index 0f265c7..578471e 100644
--- a/parser/libapparmor_re/aare_rules.cc
+++ b/parser/libapparmor_re/aare_rules.cc
@@ -41,6 +41,7 @@ aare_rules::~aare_rules(void)
 		root->release();
 
 	unique_perms.clear();
+	expr_map.clear();
 }
 
 bool aare_rules::add_rule(const char *rule, int deny, uint32_t perms,
@@ -53,10 +54,11 @@ void aare_rules::add_to_rules(Node *tree, Node *perms)
 {
 	if (reverse)
 		flip_tree(tree);
-	if (root)
-		root = new AltNode(root, new CatNode(tree, perms));
+	Node *base = expr_map[perms];
+	if (base)
+		expr_map[perms] = new AltNode(base, tree);
 	else
-		root = new CatNode(tree, perms);
+		expr_map[perms] = tree;
 }
 
 static Node *cat_with_null_seperator(Node *l, Node *r)
@@ -130,6 +132,16 @@ void *aare_rules::create_dfa(size_t *size, dfaflags_t flags)
 {
 	char *buffer = NULL;
 
+	/* finish constructing the expr tree from the different permission
+	 * set nodes */
+	PermExprMap::iterator i = expr_map.begin();
+	if (i != expr_map.end()) {
+		root = new CatNode(i->second, i->first);
+		for (i++; i != expr_map.end(); i++) {
+			root = new AltNode(root, new CatNode(i->second, i->first));
+		}
+	}
+
 	label_nodes(root);
 	if (flags & DFA_DUMP_TREE) {
 		cerr << "\nDFA: Expression Tree\n";
diff --git a/parser/libapparmor_re/aare_rules.h b/parser/libapparmor_re/aare_rules.h
index 30ae27c..c30bfd9 100644
--- a/parser/libapparmor_re/aare_rules.h
+++ b/parser/libapparmor_re/aare_rules.h
@@ -86,16 +86,19 @@ public:
 	}
 };
 
+typedef std::map<Node *, Node *> PermExprMap;
+
 class aare_rules {
 	Node *root;
 	void add_to_rules(Node *tree, Node *perms);
 	UniquePermsCache unique_perms;
+	PermExprMap expr_map;
 	
 public:
 	int reverse;
 	int rule_count;
-	aare_rules(): root(NULL), unique_perms(), reverse(0), rule_count(0) { };
-	aare_rules(int reverse): root(NULL), unique_perms(), reverse(reverse), rule_count(0) { };
+	aare_rules(void): root(NULL), unique_perms(), expr_map(), reverse(0), rule_count(0) { };
+	aare_rules(int reverse): root(NULL), unique_perms(), expr_map(), reverse(reverse), rule_count(0) { };
 	~aare_rules();
 
 	bool add_rule(const char *rule, int deny, uint32_t perms,
-- 
2.1.4