[apparmor] [patch] rework dfa structure

[Steve Beattie]

On Tue, Oct 12, 2010 at 03:33:50AM -0700, John Johansen wrote:
>  This patch reworks the internal structures used to compute the dfa. It is on
> the large side, and I experimented with different ways to split this up but in
> the end, anything I could do would result in a series of dependent patches
> that would require all of them to be applied to get meaningful functional
> changes.
> 
> The patch structural reworks the dfa so that
> - there is a new State class, it takes the place of sets of nodes in the
>   dfa, and allows storing state information within the state
> - removes the dfa transition table, which mapped sets of nodes to a
>   transition table, by moving the transition into the new state class
> - computes dfa state permissions once (stored in the state)
> - expression tree nodes are independent from a created dfa.  This allows
>   computed expression trees, and sets of Nodes (used as protostates when
>   computing the dfa).  To be managed independent of the dfa life time.
>   This will allow reducing the amount of memory used, in the future,
>   and will also allow separating the expression tree logic out into
>   its own file.
> 
> 
> The patch has some effect on reducing peak memory usage, and computation
> time.  The actual amount of reduction is dependent on the number of states
> in the dfa with larger saving being achieved on larger dfas.  Eg. for
> the test evince profile I was using it makes the parser about 7% faster with a
> peak memory usage about 12% less.
> 
> The patch is a little rough at the moment, and I actually don't have any
> intention of fixing anything beyond functional problems.  As the follow
> on set of patches, are aimed at cleaning up the dfa code.  Splitting it
> into separate files, fixing formating etc.  So it doesn't make a lot of
> sense to do partial formating fixes here.

I've reviewed this patch as best I can as well as run some tests with
it applied and it looks okay to me. ACK.

[Sorry for the delay.]

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
Url : https://lists.ubuntu.com/archives/apparmor/attachments/20101020/7a12372d/attachment.pgp