[apparmor] [patch] rework dfa structure

John Johansen john at jjmx.net
Tue Oct 12 11:33:50 BST 2010

 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

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: rework-state-to-node.patch
Type: text/x-patch
Size: 34403 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/apparmor/attachments/20101012/c8a300e1/attachment-0001.bin 

More information about the AppArmor mailing list