[apparmor] policy size

[John Johansen]

So this is just an update on what is being done to address policy size, in
the same vein as the "Slow apparmor policy compilation" mail.

compiled policy size is a big concern and we already use a compressed dfa
format, to reduce dfa size.  With that said we are working on several
improvements, though I can't give a time frame for when they will hit.

So what are we working on/planned for

full minimization
  this is part of the permissions rework, and it will allow use to remove
  all redundant states.

accept indexing
  Again part of the permission rework, this changes how permissions are
  stored in the dfa.  Instead of having a wide accept perm per state
  we will have an index per state, into a shared permission table.  Since
  the vast majority of permissions are shared this can result in
  significant savings.

  It is also needed to make dfa sharing possible as it separates separate
  a profiles permissions from the dfa.

state differential compression
  Currently we are just using a comb compression on the states next/check
  table.  With state differently compression we can reduce the number of
  transitions in the next/check table, we will continue to use comb
  compression on top of this.

equivalence classes
  Currently we don't use equivalence classes which would can help improve
  the packing achieved by the comb compression.

DFA/HFA sharing
  Currently every profile/hat has its own dfa.  We are working towards
  allowing the dfa to be shared.  As policy share a lot of common patterns
  this will result in a reduced total policy size.

kernel vars, counting constraints, and back references
  Natively supporting these can actual reduce the size of the dfa

hfa
  moving to a hybrid nfa/dfa with boundry/gateway states will help to
  control the exponential explosion that can occur in pure dfas.
  Basically this is aiming for something that is near nfa size with
  dfa speed.  If done right it can actually be faster as it has
  better caching properties.


Some of these improvements will hit next cycle, as they are part of
the permission rework (full minimization, accept indexing), while
others are a little further out.

cheers
john