[Apparmor-dev] Gentoo AppArmor

[John Johansen]

Steve Beattie wrote:
> On Sat, Nov 15, 2008 at 05:25:41PM +0100, Mario Fetka wrote:
>> i am a gentoo user and creating some ebuilds for gentoo 
>> ( svn: http://mars.arge.at/svn/linamh/trunk/apparmor/
>> layman: http://ftp.mars.arge.at/pub/Foverlay/geos_one-overlay.xml )
> 
> Cool, thanks for doing this!
> 
>> Submitted By: Mario Fetka (mario dot fetka at gmail dot com)
>> Date: 2008-11-10
>> Initial Package Version: 2.3.1
>> Origin: me
>> Upstream Status: unkonown
>> Description: fix compile and remove test on build
>>  
>> diff -Naur apparmor-parser-2.3.1.orig/Makefile apparmor-parser-2.3.1/Makefile
>> --- apparmor-parser-2.3.1.orig/Makefile	2008-05-26 11:22:56.000000000 +0000
>> +++ apparmor-parser-2.3.1/Makefile	2008-11-09 18:34:02.820003875 +0000
>> @@ -127,7 +127,7 @@
>>  
>>  all: 	$(TOOLS) $(MANPAGES) ${HTMLMANPAGES} techdoc.pdf techdoc/index.html
>>  	$(Q)make -C po all
>> -	$(Q)make -s tests
>> +#	$(Q)make -s tests
> 
> Ideally the tests would be light-weight enough that they can be enabled
> on every build. Unfortunately, a very recent commit that was intended
> to help reduce memory usage by the parser causes two of the regression
> stress tests to take a long time (5 min each here), but they do complete.
> I'm hoping to look into it, but in the mean time, you can disable the
> specific tests by adding
> 
Well yes that particular patch is somewhat unfortunate and can cause a
slow down on some policies.  On most policies the slow down is minimal
but on some it is currently roughly quadratic to the number of nodes in
the regex tree.  Overall it is a win, not only does it reduce user side
memory consumption of the parser, it also reduces the size of the
generated dfa reducing kernel memory consumption and results in an
exponential speed up on the computation of some policies.

The var tests that you are referring to, do hight light some
deficiencies both in that it is not optimal in the tree refactoring nor
in the time to do the optimization.

Those particular tests are bad for the tree factoring in that they have
a lot of redundant alternations, and the tree factoring spends a fair
amount of time removing them.  I have looked into it a little, and have
a few ideas for improving it but I haven't had time yet.

If you beat me to it, some of what needs fixed is
- tree normalization is called more than it needs to be
- tree normalization revisits the entire tree, when often it could be
  applied to only part of the tree.
- large tree comparison is slow, a hash of subtrees might speed this up
- there are some missing optimizations that could reduce the number of
  nodes earlier on.
  eg. altnodes of two characters could be converted to a charset
      (a | b) -> [ab]
  and the matching rule of
      (c | [ab] -> [abc]
- there are some factoring rules missing
- in many cases factoring is doing the worst case, where one branch of
  the subtree gradually factors all other branches of the subtree.  This
  is opposed to the best case where the work gets divided between
  subtrees.  This is similar to a quick sort breaking down to its worst
  case.

For those who are interested in why the patch was added in its less than
optimal state, it allows some users to compile/load policy where they
couldn't before under AppArmor 2.1/2.3 (since the move to the dfa).

In one particular case, I have seen a profile which could not be
computed on a machine with more than 8 gigs of ram (before hitting
swap), and after tree factoring, that profile can be compiled in about
20 seconds and less than 50 megs.  Still not great but ...

> Bah, I thought these typos had been stamped out.
> 
> Otherwise, the patch to the parser was fine. I've committed it to
> subversion.
> 
thanks steve