[apparmor] [patch 08/13] parser - push normalize_tree() ops into expr-tree classes
John Johansen
john.johansen at canonical.com
Thu Oct 10 22:34:53 UTC 2013
On 10/10/2013 01:46 PM, Steve Beattie wrote:
> This is 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 eliminates 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.
> v3: no change
>
> Signed-off-by: Steve Beattie <steve at nxnw.org>
I know I asked you to push this, but please hold off on committing it
I thought I saw an error last time I you sent it, but I haven't had
a chance to give it a proper look yet
> ---
> parser/libapparmor_re/expr-tree.cc | 98 ++++++++++++++++++++++---------------
> parser/libapparmor_re/expr-tree.h | 15 +++++
> 2 files changed, 73 insertions(+), 40 deletions(-)
>
> Index: b/parser/libapparmor_re/expr-tree.cc
> ===================================================================
> --- a/parser/libapparmor_re/expr-tree.cc
> +++ b/parser/libapparmor_re/expr-tree.cc
> @@ -1,7 +1,7 @@
> /*
> * (C) 2006, 2007 Andreas Gruenbacher <agruen at suse.de>
> * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
> - * Copyright 2009-2012 Canonical Ltd.
> + * Copyright 2009-2013 Canonical Ltd.
> *
> * The libapparmor library is licensed under the terms of the GNU
> * Lesser General Public License, version 2.1. Please see the file
> @@ -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
> @@ -1,7 +1,7 @@
> /*
> * (C) 2006, 2007 Andreas Gruenbacher <agruen at suse.de>
> * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
> - * Copyright 2009-2012 Canonical Ltd.
> + * Copyright 2009-2013 Canonical Ltd.
> *
> * The libapparmor library is licensed under the terms of the GNU
> * Lesser General Public License, version 2.1. Please see the file
> @@ -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 AppArmor at lists.ubuntu.com Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
>
More information about the AppArmor
mailing list