[apparmor] [patch 0/5] [RFC] parser: use alternations for variable expansions

[John Johansen]

On 12/09/2013 12:37 PM, Steve Beattie wrote:
> This patch series converts the parser front end from expanding variables
> by adding additional rule entries into expanding variables by using
> alternations (e.g "@{VAR}=value1 value2" gets expanded in rules in to
> "{value1,value2}").
> 
> The intent behind this patch series was to improve the performance
> of the parser by reducing the amount of memory used by the front end
> and the amount of structure walking that would need to occur when
> converting from the front end structures into the backend DFA. A
> secondary effect is to eliminate a limitation on the size of rule
> that contains regular expressions.
> 
> I am somewhat ambivalent about whether this patch set should be
> applied; on the one hand, it does what it intends to do, reducing the
> front end memory usage and eliminating the limitation on rule size. In
> testing with real world profiles, I see up to 10% performance gains
> when compiling profiles (e.g. the evince profile as shipped in Ubuntu),
> and in certain synthetic situations, the difference can be dramatic
> (the parser/tst/simple_tests/vars/vars_dbus_9.sd time dropping from
> ~1sec to ~0.01sec).
> 
yes it should!

> On the other hand, because the back end is very sensitive
> to front end inputs, it can result in the parser taking
> longer, and for some synthetic cases, significantly longer
> (parser/tst/simple_tests/vars/vars_stress_03.sd is particularly
> egregious). And even where the performance is a win, it tends not
> to be drastically significant (again, between 0 and 10% less time to
> compile policy).
> 
that is because the front of the backend needs to be fixed. Once we
do that this should always be a win.

> As an aside, it really does demonstrate how sensitive the back end
> processing is to its inputs. For example, the Ubuntu evince profile
> gets drastically worse policy compilation times when additional
> HOMEDIRS are added (as the likewise-open package does), taking
> over 23 seconds to compile on my laptop without this patch set
> applied. I was very excited because initial versions of this patch
> were compiling the same policy in under 4 seconds. However, I realized
> that the generated policy wasn't the same due to the handling of
> '/' in variable values that in expansion would result in rules with
> '//' that we would filter out. Once I added code to take that into
> account, the reduction in policy compilation time was around 0.5s
> (using profiling showed that it was not the additional code to filter
> '/'s that was adding the extra time, but that the tree simplification
> in the backend would take longer).
>
yes, the tree simplification is dumb and something that was done under
pressure and as an experiment to improve compile times ages ago. At
the time I started it I didn't understand the relationships well and
I was just experimenting with which types of tree simplifications
would have a benefit.

The algorithm that is in place is iterative, it normalizes the tree
and then steps through some basic factoring and simplifications. Then
it normalizes in the other direction and repeats. It keeps doing this
until the tree stablizes and no more simplifications or factoring can
be applied. There are no firm time bounds to this algorithm and there
are cases where it actually significantly can slow down compiles but
overall it has been a win (it tends to hurt small DFAs and be a large
win for big DFAs).

you can fiddle/see with the differences using 
apparmor_parser --no-expr-simplify

and use -D stats for more indepth stats

eg.
> time apparmor_parser -QTD stats -O no-expr-simplify /etc/apparmor.d/usr.bin.evince 
takes
real	0m7.113s
user	0m7.062s
sys	0m0.056s

> time apparmor_parser -QTD stats /etc/apparmor.d/usr.bin.evince 
real	0m4.211s
user	0m4.190s
sys	0m0.020s

Digging into the stats for one of the larger DFAs that get produced I can see
For the no expr simplification (hence no expr stats):
  Created dfa: states 43679 proto { cache: size=43679 dups=252056 longest=769 avg=61 }, nnodes { cache: size=43083 dups=252652 longest=767 avg=54 }, anodes { cache: size=59 dups=242481 longest=20 avg=7 }

For the expr simplification:
  expr tree: c 14101, [] 66, [^] 1210, | 2820, + 0, * 753, . 89, cat 15420
  simplified expr tree: c 7160, [] 51, [^] 408, | 880, + 0, * 244, . 4, cat 6988
  Created dfa: states 13145 proto { cache: size=13145 dups=77228 longest=387 avg=28 }, nnodes { cache: size=12794 dups=77579 longest=385 avg=23 }, anodes { cache: size=59 dups=68866 longest=20 avg=7 }

we can see that without expr simplification the dfa had to create 43679
states vs with simplification 13145, and that the set of expr nnodes
making up those states where much longer 54 vs 23.  This means a lot
more work is going on dfa creation, but also in minimization as the dfa
gets cut down to about 9000 states.

I do have plans to fix the tree simplification. Its has two steps to
it, with one of them happening as part of the broader permissions work.

1. is to break the expr tree up into separate trees based on permission.
   This lets us do a coarse grouping and factoring of these expressions
   at the perm level as we add them.

   This is already happening because of how the factoring is setup but
   its much less efficient about it, nor is it guaranteed to result in
   the same sets for the same permission groups which means that the
   simplification/factoring is not as complete as it could be.

2. Rework tree simplification so that we flatten the tree at alt and
   cat nodes into vectors of alt and cat nodes in a group.
   This group can then be efficiently sorted and worked on for factoring
   and simplification.

   The current routine uses an inefficient O^2 walk/sort of these groups
   for factoring/simplification and it has other issues


> Therefore, I'm offering up this patch set for comments.
> 
/me will endeavor to give it a proper review soonish