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

[Steve Beattie]

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?

> @@ -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.

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
Url : https://lists.ubuntu.com/archives/apparmor/attachments/20101110/e6e2ff40/attachment-0001.pgp