[apparmor] [PATCH 4/4] Move rule simplification into the tree construction phase

[Steve Beattie]

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 at canonical.com>

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

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL: <https://lists.ubuntu.com/archives/apparmor/attachments/20150624/e63cac6e/attachment.pgp>