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

[Steve Beattie]

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).

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).

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).

Therefore, I'm offering up this patch set for comments.

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