[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
<[email protected]>
http://NxNW.org/~steve/
signature.asc
Description: Digital signature
-- AppArmor mailing list [email protected] Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
