[apparmor] [Patch] parser - reduce number of dynamic casts patch v2

Steve Beattie steve at nxnw.org
Fri Sep 6 10:59:22 UTC 2013


[I was asked by John to resurrect and resubmit this parser patch.]

This is a prototype patch tries to reduce the number of
dynamic_cast<>s needed during normalization by pushing the operations
of normalize_tree() into the expr-tree classes themselves rather
than perform it as an external function. This reduces the need for
dynamic_cast<> checks on the current object under inspection and
reduces the number of checks needing to be performed on child Nodes
as well.

In non-strict benchmarking, doing the dynamic_cast<> reduction
for just the tree normalization operation resulted in a ~10-15%
improvement in overall time on a couple of different hosts (amd64,
armel), as measured against apparmor_parser -Q. Valgrind's callgrind
tool indicated a reduction in the number of calls to dynamic_cast<>
on the tst/simple_tests/vars/dbus_vars_9.sd test profile from ~19
million calls to ~12 million.

In comparisons with dumped expr trees over both the entire
tst/simple_tests/ tree and from 1000 randomly generated profiles via
stress.rb, the generated trees were identical.

Patch history:
  v1: initial version of patch
  v2: update patch to take into account the infinite loop fix in
      trunk rev 1975 and refresh against current code.

---
 parser/libapparmor_re/expr-tree.cc |   96 ++++++++++++++++++++++---------------
 parser/libapparmor_re/expr-tree.h  |   13 +++++
 2 files changed, 71 insertions(+), 38 deletions(-)

Index: b/parser/libapparmor_re/expr-tree.cc
===================================================================
--- a/parser/libapparmor_re/expr-tree.cc
+++ b/parser/libapparmor_re/expr-tree.cc
@@ -181,52 +181,72 @@ static void rotate_node(Node *t, int dir
 	t->child[!dir] = left;
 }
 
-void normalize_tree(Node *t, int dir)
+/* return False if no work done */
+int TwoChildNode::normalize_eps(int dir)
 {
-	if (dynamic_cast<LeafNode *>(t))
-		return;
+	if ((&epsnode == child[dir]) &&
+	    (&epsnode != child[!dir])) {
+		// (E | a) -> (a | E)
+		// Ea -> aE
+		// Test for E | (E | E) and E . (E . E) which will
+		// result in an infinite loop
+		Node *c = child[!dir];
+		if (dynamic_cast<TwoChildNode *>(c) &&
+		    &epsnode == c->child[dir] &&
+		    &epsnode == c->child[!dir]) {
+			c->release();
+			c = &epsnode;
+		}
+		child[!dir] = child[dir];
+		child[dir] = c;
+		return 1;
+	}
 
+	return 0;
+}
+
+void CatNode::normalize(int dir)
+{
 	for (;;) {
-		if (dynamic_cast<TwoChildNode *>(t) &&
-		    (&epsnode == t->child[dir]) &&
-		    (&epsnode != t->child[!dir])) {
-			// (E | a) -> (a | E)
-			// Ea -> aE
-			// Test for E | (E | E) and E . (E . E) which will
-			// result in an infinite loop
-			Node *c = t->child[!dir];
-			if (dynamic_cast<TwoChildNode *>(c) &&
-			    &epsnode == c->child[dir] &&
-			    &epsnode == c->child[!dir]) {
-				c->release();
-				c = &epsnode;
-			}
-			t->child[dir] = c;
-			t->child[!dir] = &epsnode;
-			// Don't break here as 'a' may be a tree that
-			// can be pulled up.
-		} else if ((dynamic_cast<AltNode *>(t) &&
-			    dynamic_cast<AltNode *>(t->child[dir])) ||
-			   (dynamic_cast<CatNode *>(t) &&
-			    dynamic_cast<CatNode *>(t->child[dir]))) {
-			// (a | b) | c -> a | (b | c)
+		if (normalize_eps(dir)) {
+			continue;
+		} else if (dynamic_cast<CatNode *>(child[dir])) {
 			// (ab)c -> a(bc)
-			rotate_node(t, dir);
-		} else if (dynamic_cast<AltNode *>(t) &&
-			   dynamic_cast<CharSetNode *>(t->child[dir]) &&
-			   dynamic_cast<CharNode *>(t->child[!dir])) {
+			rotate_node(this, dir);
+		} else {
+			break;
+		}
+	}
+
+	if (child[dir])
+		child[dir]->normalize(dir);
+	if (child[!dir])
+		child[!dir]->normalize(dir);
+}
+
+void AltNode::normalize(int dir)
+{
+	for (;;) {
+		if (normalize_eps(dir)) {
+			continue;
+		} else if (dynamic_cast<AltNode *>(child[dir])) {
+			// (a | b) | c -> a | (b | c)
+			rotate_node(this, dir);
+		} else if (dynamic_cast<CharSetNode *>(child[dir]) &&
+			   dynamic_cast<CharNode *>(child[!dir])) {
 			// [a] | b  ->  b | [a]
-			Node *c = t->child[dir];
-			t->child[dir] = t->child[!dir];
-			t->child[!dir] = c;
+			Node *c = child[dir];
+			child[dir] = child[!dir];
+			child[!dir] = c;
 		} else {
 			break;
 		}
 	}
-	if (t->child[dir])
-		normalize_tree(t->child[dir], dir);
-	if (t->child[!dir])
-		normalize_tree(t->child[!dir], dir);
+
+	if (child[dir])
+		child[dir]->normalize(dir);
+	if (child[!dir])
+		child[!dir]->normalize(dir);
 }
 
 //charset conversion is disabled for now,
@@ -558,7 +578,7 @@ Node *simplify_tree(Node *t, dfaflags_t
 			do {
 				modified = false;
 				if (flags & DFA_CONTROL_TREE_NORMAL)
-					normalize_tree(t, dir);
+					t->normalize(dir);
 				t = simplify_tree_base(t, dir, modified);
 				if (modified)
 					update = true;
Index: b/parser/libapparmor_re/expr-tree.h
===================================================================
--- a/parser/libapparmor_re/expr-tree.h
+++ b/parser/libapparmor_re/expr-tree.h
@@ -126,6 +126,15 @@ public:
 	virtual int eq(Node *other) = 0;
 	virtual ostream &dump(ostream &os) = 0;
 	void dump_syntax_tree(ostream &os);
+	virtual void normalize(int dir)
+	{
+		if (child[dir])
+			child[dir]->normalize(dir);
+		if (child[!dir])
+			child[!dir]->normalize(dir);
+	}
+	/* return false if no work done */
+	virtual int normalize_eps(int dir __attribute__((unused))) { return 0; }
 
 	bool nullable;
 	NodeSet firstpos, lastpos, followpos;
@@ -157,11 +166,13 @@ public:
 class TwoChildNode: public InnerNode {
 public:
 	TwoChildNode(Node *left, Node *right): InnerNode(left, right) { };
+	virtual int normalize_eps(int dir);
 };
 
 class LeafNode: public Node {
 public:
 	LeafNode(): Node() { };
+	virtual void normalize(int dir __attribute__((unused))) { return; }
 };
 
 /* Match nothing (//). */
@@ -485,6 +496,7 @@ public:
 		child[1]->dump(os);
 		return os;
 	}
+	void normalize(int dir);
 };
 
 /* Match one of two alternative nodes. */
@@ -521,6 +533,7 @@ public:
 		os << ')';
 		return os;
 	}
+	void normalize(int dir);
 };
 
 /* Traverse the syntax tree depth-first in an iterator-like manner. */

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <https://lists.ubuntu.com/archives/apparmor/attachments/20130906/6ceaf8c3/attachment.pgp>


More information about the AppArmor mailing list