[apparmor] [PATCH 03/10] Split out compressed dfa "transition table" compression

John Johansen john.johansen at canonical.com
Sat Mar 12 01:10:43 UTC 2011


On 03/11/2011 04:55 PM, Steve Beattie wrote:
> On Thu, Mar 10, 2011 at 12:35:53PM -0800, John Johansen wrote:
>> Split hfa into hfa and compressed_hfa files.  The hfa portion focuses on
>> creating an manipulating hfas, while compressed_hfa is used for creating
>> compressed hfas that can be used/reused at run time with much less memory
>> usage than the full blown hfa.
>>
>> Signed-off-by: John Johansen <john.johansen at canonical.com>
> 
> Acked-By: Steve Beattie <sbeattie at ubuntu.com>
> 
> ... though hfa.cc and compressed_hfa.cc imply (to me) a c++ class
> inheritance relationship that I don't think is accurate.
> 
> 

I am open to alternate naming, and there is a relationship just not an
inheritance based one.  Basically the hfa is the full deal that you
can manipulate, the compressed version is created from the hfa and
specialized, to be small and only used for match lookups (so basically
create, match, load, save).

Both of them are going to have more renaming and cleanup, and pickup
more functions.  Eg. they both will pick up match the missing match
routines.

I went with hfa*, over dfa as that is where we are headed, even though
we are very much just straight up dfa at the moment, and probably
for the next year or so, as the hfa creation routines are going to
require a lot of thought about how to best set up boundaries etc.


*for the curious hfa (hybrid finite automata) - its basically an nfa
that has under gone partial dfa conversion.

The design we are shooting for is a set of interconnected dfas, that
have boundary states connecting them.  The nfa part comes from being
in multiple dfas at once, that is when you cross a boundry instead of
entry just one next state (dfa) you may enter multiple next states
(multiple sub dfas).  This can be used to reduce state explosion in
dfas if the boundary points are chosen carefully, and because the
whole thing is smaller, hences uses less memory and fits in caches
it can be faster than using a plain dfa.



More information about the AppArmor mailing list