On 09/06/2013 03:59 AM, Steve Beattie wrote:
[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.
Alright I've gone over it in detail and am happy with it
thanks
Acked-by: John Johansen <[email protected]>
---
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. */
--
AppArmor mailing list
[email protected]
Modify settings or unsubscribe at:
https://lists.ubuntu.com/mailman/listinfo/apparmor
