[apparmor] [PATCH 10/10] To reduce memory overhead of dfa creation convert to using a Node Vector instead of a NodeSet.

[John Johansen]

We need to store sets of Nodes, to compute the dfa but the C++ set is
not the most efficient way to do this as, it has a has a lot of overhead
just to store a single pointer.

Instead we can use an array of tightly packed pointers + a some header
information.  We can do this because once the Set is finalized it will
not change, we just need to be able to reference and compare to it.

We don't use C++ Vectors as they have more overhead than a plain array
and we don't need their additional functionality.

We only replace the use of hashedNodeSets for non-accepting states as
these sets are only used in the dfa construction, and dominate the memory
usage.  The accepting states still may need to be modified during
minimization and there are only a small number of entries (20-30), so
it does not make sense to convert them.

Also introduce a NodeVec cache that serves the same purpose as the NodeSet
cache that was introduced earlier.

This is not abstracted this out as nicely as might be desired but avoiding
the use of a custom iterator and directly iterating on the Node array
allows for a small performance gain, on larger sets.

This patch reduces the amount of heap memory used by dfa creation by about
4x - overhead.  So for small dfas the savings is only 2-3x but on larger
dfas the savings become more and more pronounced.

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/hfa.cc |    9 ++-
 parser/libapparmor_re/hfa.h  |  104 ++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 107 insertions(+), 6 deletions(-)

diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
index fe79aad..91cc3bd 100644
--- a/parser/libapparmor_re/hfa.cc
+++ b/parser/libapparmor_re/hfa.cc
@@ -100,12 +100,12 @@ State *DFA::add_new_state(NodeSet *nodes, State *other)
 	 * follow(), ie. put in separate lists from the start
 	 */
 	NodeSet *anodes, *nnodes;
+	hashedNodeVec *nnodev;
 	split_node_types(nodes, &anodes, &nnodes);
-
-	nnodes = nnodes_cache.insert(nnodes);
+	nnodev = nnodes_cache.insert(nnodes);
 	anodes = anodes_cache.insert(anodes);
 
-	ProtoState proto(nnodes, anodes);
+	ProtoState proto(nnodev, anodes);
 	State *state = new State(node_map.size(), proto, other);
 	pair<NodeMap::iterator,bool> x = node_map.insert(proto, state);
 	if (x.second == false) {
@@ -134,6 +134,9 @@ void DFA::update_state_transitions(State *state)
 	for (NodeSet::iterator i = state->nodes.nnodes->begin(); i != state->nodes.nnodes->end(); i++)
 		(*i)->follow(cases);
 
+	for (unsigned int i = 0; i < state->nodes.nnodes->size(); i++)
+		state->nodes.nnodes->nodes[i]->follow(cases);
+
 	/* Now for each set of nodes in the computed transitions, make
 	 * sure that there is a state that maps to it, and add the
 	 * matching case to the state.
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
index cc71e2d..b9037be 100644
--- a/parser/libapparmor_re/hfa.h
+++ b/parser/libapparmor_re/hfa.h
@@ -65,6 +65,58 @@ public:
 	}
 };
 
+
+class hashedNodeVec {
+public:
+	unsigned long hash;
+	unsigned long len;
+	ImportantNode **nodes;
+
+	hashedNodeVec(NodeSet *n)
+	{
+		hash = hash_NodeSet(n);
+		len = n->size();
+		nodes = new ImportantNode *[n->size()];
+
+		unsigned int j = 0;
+		for (NodeSet::iterator i = n->begin(); i != n->end(); i++, j++) {
+			nodes[j] = *i;
+		}
+	}
+
+	hashedNodeVec(NodeSet *n, unsigned long h): hash(h)
+	{
+		len = n->size();
+		nodes = new ImportantNode *[n->size()];
+		ImportantNode **j = nodes;
+		for (NodeSet::iterator i = n->begin(); i != n->end(); i++) {
+			*(j++) = *i;
+		}
+	}
+
+	~hashedNodeVec()
+	{
+		delete nodes;
+	}
+
+	unsigned long size()const { return len; }
+
+	bool operator<(hashedNodeVec const &rhs)const
+	{
+		if (hash == rhs.hash) {
+			if (len == rhs.size()) {
+				for (unsigned int i = 0; i < len; i++) {
+					if (nodes[i] != rhs.nodes[i])
+						return nodes[i] < rhs.nodes[i];
+				}
+				return false;
+			}
+			return len < rhs.size();
+		}
+		return hash < rhs.hash;
+	}
+};
+
 class CacheStats {
 public:
 	unsigned long dup, sum, max;
@@ -112,15 +164,61 @@ public:
 	}
 };
 
+struct deref_less_than {
+       bool operator()(hashedNodeVec * const &lhs, hashedNodeVec * const &rhs)const
+		{
+			return *lhs < *rhs;
+		}
+};
+
+class NodeVecCache: public CacheStats {
+public:
+	set<hashedNodeVec *, deref_less_than> cache;
+
+	NodeVecCache(void): cache() { };
+	~NodeVecCache() { clear(); };
+
+	virtual unsigned long size(void) const { return cache.size(); }
+
+	void clear()
+	{
+		for (set<hashedNodeVec *>::iterator i = cache.begin();
+		     i != cache.end(); i++) {
+			delete *i;
+		}
+		cache.clear();
+		CacheStats::clear();
+	}
+
+	hashedNodeVec *insert(NodeSet *nodes)
+	{
+		if (!nodes)
+			return NULL;
+		pair<set<hashedNodeVec *>::iterator,bool> uniq;
+		hashedNodeVec *nv = new hashedNodeVec(nodes);
+		uniq = cache.insert(nv);
+		if (uniq.second == false) {
+			delete nv;
+			dup++;
+		} else {
+			sum += nodes->size();
+			if (nodes->size() > max)
+				max = nodes->size();
+		}
+		delete(nodes);
+		return (*uniq.first);
+	}
+};
+
 /*
  * ProtoState - NodeSet and ancillery information used to create a state
  */
 class ProtoState {
 public:
-	NodeSet *nnodes;
+	hashedNodeVec *nnodes;
 	NodeSet *anodes;
 
-	ProtoState(NodeSet *n, NodeSet *a = NULL): nnodes(n), anodes(a) { };
+	ProtoState(hashedNodeVec *n, NodeSet *a = NULL): nnodes(n), anodes(a) { };
 	bool operator<(ProtoState const &rhs)const
 	{
 		if (nnodes == rhs.nnodes)
@@ -231,7 +329,7 @@ class DFA {
 
 	/* temporary values used during computations */
 	NodeCache anodes_cache;
-	NodeCache nnodes_cache;
+	NodeVecCache nnodes_cache;
 	NodeMap node_map;
 	list<State *> work_queue;
 
-- 
1.7.5.4