[apparmor] [PATCH 09/10] Split the nodeset used in computing the dfa into two sets, accepting and non-accepting, and have the proto-state use them.

[John Johansen]

On 10/28/2011 03:08 PM, Seth Arnold wrote:
> Can you explain the complicated condition at the end of the split operation?
> 
> static void split_node_types(NodeSet *nodes, NodeSet **anodes, NodeSet **nnodes)
>  {
>     *anodes = *nnodes = NULL;
>     for (NodeSet::iterator i = nodes->begin(); i != nodes->end(); ) {
>         If ((*i)->is_accept()) {
>             if (!*anodes)
>                 *anodes = new NodeSet;
>             (*anodes)->insert(*i);
>             NodeSet::iterator k = i++;
>             nodes->erase(k);
>         } else
>              i++;
>     }
>  
>     if (nodes->size() > 0 || !*anodes) {
>         *nnodes = nodes;
>     } else {
>         delete nodes;
>     }
> }
> 
> (Please forgive the formatting, blackberry is surely not vim.)
> 
> I'm going around in circles trying to understand why || was used and how these conditions make sense in the end. I think I'd feel better if all the non-accept nodes were appended to nnodes in the body of the loop instead, but I'm not convinced that would be the same behavior.
> 
> What am I missing?
> 
Forgive the lengthy, and meandering of the reply.  Hopefully it will fully
explain what is going on, and why certain choices where made :)

DFA states are formed from a set of ImportantNodes from the expression tree, some
accepting some non-accepting.  We use a set container during computing follows
as it turns out to be the best for the job.  The same node may be inserted multiple
times, during the the process calculating the follow states.  And the set efficiently
catches the redundancy and orders the nodes as well, which is useful for later
comparisons.

This builtup proto-state (*nodes) is the set of NFA states the DFA will represent.
We split it for two reasons, the first being that we need to track permissions
more precisely (more patches yet to come), and simply storing the set of accept
permissions off of the DFA state results in a fair balloning of memory if the
duplication isn't removed.  Hence we split of the accept perms, and get a
single version of each and reference it.

We do the same thing for the non-accepting states (nnodes), its doesn't gain us
as much as with the accept nodes, but there is some gain.  The protostate then
glues these two pieces back together to get the same set we originally builtup.

The split_node_types routine is a bit of a hack, and I do need to go back into
this at some point and see if we can't clean this up more.  Ideally we shouldn't
be splitting the types post construction, but as part of the process of the
initial build in follow(),

So split nodes is dividing the accept nodes (anodes), from the non-accept nodes
(nnodes) in the nodes set.  For efficiency purposes, we move the accept nodes into
their own set because there are far fewer of them than nnodes.  And nodes just
becomes nnodes.

eg.  Output of a stats dump.
Created dfa: states 12160 proto { cache: size=12160 dups=71797 longest=324 avg=28 }, nnodes { cache: size=11841 dups=72116 longest=322 avg=22 }, anodes { cache: size=55 dups=64655 longest=20 avg=7 }

This shows we created 12160 states
The proto cache (accept + non-accept nodes combined back together) has
  size of 12160 entries (this should allows equal the number of states
                         as this is the basis of the state)
  there where 71797 entries generated as part of the construction that
  ended up as duplicates of an entry already in the cache, so they
  could be discarded.

  The longest entry is 324 Important nodes long, with the average entry
  being 28.

  We can see the same pattern for the nnodes cache and the accept nodes
  cache.  The nnodes cache is fairly close to the proto cache in that
  most of the entries that result in dups there actually result in
  dups in the proto cache.  I need to do some experimenting here on how
  we can exploit this better but its pretty low priority atm.

  The accept nodes cache is different it only has 55 entries and 64655
  dup insertions recorded.  And we retain this information beyond
  the dfa construction phase.

The confusing logic at the end actually can actually be thrown out now
(so thanks for questioning) but was important at one point the life of
this patches development.

What it is doing is making an exception for the empty, non-accepting/
trap state, which gets inserted into the caches, and matched like other
states.

So if there are any elements left in nodes, they will becomes nnodes
or if there are no nnodes and there are no accept nodes we have the
empty nodeset case.  Otherwise we just have an empty set that we can
discard.

We can now replace it by just returning the empty set, and discarding it
when it matches against the nnodes cache lookup.

The reason we don't append nodes to nnodes, is as I stated above
efficiency.  With the stl that would meant we where creating new set
nodes copying data over and inserting into a new set.  Where if
we just remove the accept nodes and insert them in their own set
there is far less work (compare chain length average 28 vs. 7).

I actually experimented with this and the difference was significant.