[apparmor] [PATCH 2/9] Embedded the temporary computed nodes as part of the state

[John Johansen]

On 11/10/2010 04:24 PM, Steve Beattie wrote:
> On Wed, Nov 10, 2010 at 02:02:23PM -0800, John Johansen wrote:
>> Embedding the nodes are part of the state gives fast back reference from
>> the state to the nodes that created it.  This is useful for the state to
>> nodes mapping dump as it lets us output the states in order.  It will also
>> let us avoid certain nodemap lookup in the future.
>>
>> Overlay the nodes field (used only in dfa construction) with the partition
>> field which is only used during dfa minimization to avoid making the state
>> any larger.
>>
>> Signed-off-by: John Johansen <john.johansen at canonical.com>
>> ---
>>  parser/libapparmor_re/regexp.y |   21 +++++++++++++++------
>>  1 files changed, 15 insertions(+), 6 deletions(-)
>>
>> diff --git a/parser/libapparmor_re/regexp.y b/parser/libapparmor_re/regexp.y
>> index 82e9bb5..f866b78 100644
>> --- a/parser/libapparmor_re/regexp.y
>> +++ b/parser/libapparmor_re/regexp.y
>> @@ -1403,7 +1403,10 @@ class State {
>>  public:
>>  State() : label (0), audit(0), accept(0), cases() { }
>>  	int label;
>> -	Partition *partition;
>> +	union {
>> +		Partition *partition;
>> +		NodeSet *nodes;
>> +	};
> 
> Should the union have an initializer? Can you document the field in the
> comment header for the State class?
yes we can set it to an initial value of null

And yeah documenting is a good idea

> 
>> @@ -1421,6 +1424,7 @@ typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
>>  /* Transitions in the DFA. */
>>  
>>  class DFA {
>> +    void dump_node_to_dfa(void);
>>  public:
>>      DFA(Node *root, dfaflags_t flags);
>>      virtual ~DFA();
>> @@ -1454,6 +1458,7 @@ do { \
>>  		 */ \
>>  		TARGET = new State(); \
>>  		(TARGET)->label = nodemap.size();	\
>> +		(TARGET)->nodes = (NODES); \
>>  		states.push_back(TARGET); \
>>  		nodemap.insert(make_pair(index, TARGET)); \
>>  		work_queue.push_back(NODES);	  \
>> @@ -1468,14 +1473,16 @@ do { \
>>  	} \
>>  } while (0)
>>  
>> -static void dump_node_to_dfa(NodeMap &nodemap)
>> +/* WARNING: This routine can only be called from within DFA creation as
>> + * the nodes value is only valid during dfa construction.
>> + */
>> +void DFA::dump_node_to_dfa(void)
>>  {
>>  	cerr << "Mapping of States to expr nodes\n"
>>  		"  State  <=   Nodes\n"
>>  		"-------------------\n";
>> -	for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
>> -		cerr << "  " << i->second->label << " <= " << *i->first.second << "\n";
>> -
>> +	for (Partition::iterator i = states.begin(); i != states.end(); i++)
>> +		cerr << "  " << (*i)->label << " <= " << *(*i)->nodes << "\n";
>>  }
>>  
>>  /**
>> @@ -1505,6 +1512,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
>>  	nonmatching = new State;
>>  	states.push_back(nonmatching);
>>  	NodeSet *emptynode = new NodeSet;
>> +	nonmatching->nodes = emptynode;
>>  	nodemap.insert(make_pair(make_pair(hash_NodeSet(emptynode), emptynode), nonmatching));
>>  	/* there is no nodemapping for the nonmatching state */
>>  
>> @@ -1515,6 +1523,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
>>  	start->label = 1;
>>  	states.push_back(start);
>>  	NodeSet *first = new NodeSet(root->firstpos);
>> +	start->nodes = first;
>>  	nodemap.insert(make_pair(make_pair(hash_NodeSet(first), first), start));
>>  
>>  	/* the work_queue contains the proto-states (set of nodes that is
>> @@ -1594,7 +1603,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
>>  	}
>>  
>>  	if (flags & DFA_DUMP_NODE_TO_DFA)
>> -		dump_node_to_dfa(nodemap);
>> +		dump_node_to_dfa();
>>  
>>  	for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
>>  		delete i->first.second;
> 
> Otherwise, ACK.
> 
>