On Fri, Sep 06, 2013 at 03:59:22AM -0700, 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.
Wow, those are some impressive performance improvements. My mind goes in circles a little bit untangling the normalize() vs normalize_eps() methods, but it all feels like it hangs together as it should. Acked-by: Seth Arnold <[email protected]> Thanks > --- > 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/ > -- > AppArmor mailing list > [email protected] > Modify settings or unsubscribe at: > https://lists.ubuntu.com/mailman/listinfo/apparmor
signature.asc
Description: Digital signature
-- AppArmor mailing list [email protected] Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
