[apparmor] [Patch] parser - reduce number of dynamic casts patch v2
Seth Arnold
seth.arnold at canonical.com
Wed Nov 27 23:39:12 UTC 2013
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 <seth.arnold at canonical.com>
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
> <sbeattie at ubuntu.com>
> http://NxNW.org/~steve/
> --
> AppArmor mailing list
> AppArmor at lists.ubuntu.com
> Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <https://lists.ubuntu.com/archives/apparmor/attachments/20131127/6de4d411/attachment.pgp>
More information about the AppArmor
mailing list