Replacing the dfa

[John Johansen]

On 06/16/2010 06:17 AM, Jamie Strandboge wrote:
> On Wed, 2010-06-16 at 00:59 -0700, John Johansen wrote:
>> Over the last few weeks I have been looking into improving loaded policy
>> size, and creation time.  This has lead me to believe that we need to
>> replace how AA does its pattern matching.
> ...
>> The hybrid should allow us to improve both compile time and memory use,
>> by reducing state explosion.  If done properly this should reduce the
>> compiled size of all but the simplest profiles.
> 
> I think the hybrid approach sounds fine, but my feeling is that this
> should happen after AA is accepted upstream (unless our current dfa is
> blocking acceptance). Our current dfa may have a few problems, but in
> general it works for a lot of people. Updating it later should be easy
> enough since it should be wholly contained within AA.
> 

Right, I guess I didn't make this clear.  This is a long term move, there
is a lot of work and cleanup that needs to happen before we can move away
from the dfa, nor will we move away from the dfa entirely.

We will actually still need the dfa code for the subgraphs between nfa
choke points (it will just need to be extended) and it will also be needed
for global policy analysis.

In the short term we will have to live with cleanups to the dfa, which
should reduce its memory use amd compile time some by reducing the number
of maps used, separating the dfa from the regex tree so its nodes can be
freed after the dfa is created instead of holding on to it until after
all dfas have been created, and tweaking and cleaning up heuristics more.
But none of these changes are going to result in dramatic cleanups in
compilation memory use nor speed, and they will have even less effect
on loaded policy size.