[prev in list] [next in list] [prev in thread] [next in thread] 

List:       apparmor-dev
Subject:    Re: [apparmor] [PATCH 4/4] Move rule simplification into the tree construction phase
From:       Steve Beattie <steve () nxnw ! org>
Date:       2015-06-25 6:00:31
Message-ID: 20150625060031.GQ16138 () nxnw ! org
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


On Mon, Jun 22, 2015 at 11:00:02AM -0700, John Johansen wrote:
> The current rule simplification algorithm has issues that need to be
> addressed in a rewrite, but it is still often a win, especially for
> larger profiles.
> 
> However doing rule simplification as a single pass limits what it can
> do. We default to right simplification first because this has historically
> shown the most benefits. For two reasons
>   1. It allowed better grouping of the split out accept nodes that we
>      used to do (changed in previous patches)
>   2. because trailing regexes like
>        /foo/**,
>        /foo/**.txt,
>      can be combined and they are the largest source of node set
>      explosion.
> 
> However the move to unique node sets, eliminates 1, and forces 2 to
> work within only the single unique permission set on the right side
> factoring pass, but it still incures the penalty of walking the whole
> tree looking for potential nodes to factor.
> 
> Moving tree simplification into the construction phases gets rid of
> the need for the right side factoring pass to walk other node sets
> that will never combine, and since we are doing simplification we can
> do it before the cat and permission nodes are added reducing the
> set of nodes to look at by another two.
> 
> We do loose the ability to combine nodes from different sets during
> the left factoring pass, but experimentation shows that doing
> simplification only within the unique permission sets achieve most of
> the factoring that a single global pass would achieve.
> 
> Signed-off-by: John Johansen <john.johansen@canonical.com>

Acked-by: Steve Beattie <steve@nxnw.org>. I did a bunch of testing on it
as well. The performance win is pretty nice.

-- 
Steve Beattie
<sbeattie@ubuntu.com>
http://NxNW.org/~steve/

["signature.asc" (application/pgp-signature)]

-- 
AppArmor mailing list
AppArmor@lists.ubuntu.com
Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor


[prev in list] [next in list] [prev in thread] [next in thread]