[apparmor] [PATCH 9/9] Use unordered containers for caches etc. if they are available
John Johansen
john.johansen at canonical.com
Tue Sep 15 03:11:21 UTC 2015
This was an experiment to see if unordered containers would improve
the performance of the current dfa construction code, they do not and
will not and this patch will ever be committed to the project. However
it still serves as a proof of concept showing how the code can make
use of unordered containers when available and fall back to the older
stl containers when they are not.
I have a wip patchset that reworks the expr-tree -> dfa construction
that makes much heavier use of caching and lookups, and the use of
unordered containers provides a small performance boost. The code is
not done so it is unclear how signifcant an improvement they will
provide, but I would appreciate feedback on the basics of what is
being done here.
cummulative user time for 5 runs
2.10 unordered
dhclient 0m0.784s 0m0.868s
klogd 0m0.156s 0m0.140s
ubuntu-core-default 0m0.344s 0m0.344s
ubuntu-personal-qml-app 0m1.800s 0m1.784s
ubuntu-personal-webapp 0m2.528s 0m2.560s
chromium-browser 0m5.304s 0m5.208s
evince 0m11.416s 0m11.832s
firefox 0m5.304s 0m4.924s
usr.sbin.cupsd 0m1.060s 0m0.992s
dnsmasq 0m0.408s 0m0.436s
Signed-off-by: John Johansen <john.johansen at canonical.com>
---
parser/libapparmor_re/expr-tree.h | 76 +++++++++++++++++++++++++++++++++++----
parser/libapparmor_re/hfa.h | 40 +++++++++++++++++++--
2 files changed, 107 insertions(+), 9 deletions(-)
diff --git a/parser/libapparmor_re/expr-tree.h b/parser/libapparmor_re/expr-tree.h
index afd426f..e770873 100644
--- a/parser/libapparmor_re/expr-tree.h
+++ b/parser/libapparmor_re/expr-tree.h
@@ -39,6 +39,11 @@
#include <stack>
#include <ostream>
+#ifdef CXX11_UNORDERED_CONTAINERS
+#include <tr1/unordered_set>
+using std::tr1::unordered_set;
+#endif
+
#include <stdint.h>
#include "apparmor_re.h"
@@ -635,6 +640,15 @@ public:
return hash < rhs.hash;
}
}
+ bool operator==(hashedNodeSet const &rhs)const
+ {
+ if (hash == rhs.hash) {
+ if (nodes->size() == rhs.nodes->size())
+ return *nodes == *(rhs.nodes);
+ return false;
+ }
+ return false;
+ }
};
@@ -691,6 +705,20 @@ public:
}
return hash < rhs.hash;
}
+ 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 false;
+ }
+ return true;
+ }
+ return false;
+ }
+ return false;
+ }
};
class CacheStats {
@@ -703,9 +731,22 @@ public:
virtual unsigned long size(void) const = 0;
};
+#ifdef CXX11_UNORDERED_CONTAINERS
+struct hashedNodeSet_hash {
+ size_t operator()(hashedNodeSet const & x) const noexcept
+ {
+ return x.hash;
+ }
+};
+
+typedef unordered_set<hashedNodeSet, hashedNodeSet_hash> NodeSetType;
+#else
+typedef set<hashedNodeSet> NodeSetType;
+#endif
+
class NodeCache: public CacheStats {
public:
- set<hashedNodeSet> cache;
+ NodeSetType cache;
NodeCache(void): cache() { };
~NodeCache() { clear(); };
@@ -714,7 +755,7 @@ public:
void clear()
{
- for (set<hashedNodeSet>::iterator i = cache.begin();
+ for (NodeSetType::iterator i = cache.begin();
i != cache.end(); i++) {
delete i->nodes;
}
@@ -726,7 +767,7 @@ public:
{
if (!nodes)
return NULL;
- pair<set<hashedNodeSet>::iterator,bool> uniq;
+ pair<NodeSetType::iterator,bool> uniq;
uniq = cache.insert(hashedNodeSet(nodes));
if (uniq.second == false) {
delete(nodes);
@@ -740,16 +781,37 @@ public:
}
};
-struct deref_less_than {
+
+struct hashedNodeVec_eq {
+ bool operator()(hashedNodeVec * const &lhs, hashedNodeVec * const &rhs)const
+ {
+ return *lhs == *rhs;
+ }
+};
+
+struct hashedNodeVec_hash {
+ size_t operator()(hashedNodeVec * const & x) const noexcept
+ {
+ return x->hash;
+ }
+};
+
+struct hashedNodeVec_lt {
bool operator()(hashedNodeVec * const &lhs, hashedNodeVec * const &rhs)const
{
return *lhs < *rhs;
}
};
+#ifdef CXX11_UNORDERED_CONTAINERS
+typedef unordered_set<hashedNodeVec *, hashedNodeVec_hash, hashedNodeVec_eq> NodeVecType;
+#else
+typedef set<hashedNodeVec *, hashedNodeVec_lt> NodeVecType;
+#endif
+
class NodeVecCache: public CacheStats {
public:
- set<hashedNodeVec *, deref_less_than> cache;
+ NodeVecType cache;
NodeVecCache(void): cache() { };
~NodeVecCache() { clear(); };
@@ -758,7 +820,7 @@ public:
void clear()
{
- for (set<hashedNodeVec *>::iterator i = cache.begin();
+ for (NodeVecType::iterator i = cache.begin();
i != cache.end(); i++) {
delete *i;
}
@@ -770,7 +832,7 @@ public:
{
if (!nodes)
return NULL;
- pair<set<hashedNodeVec *>::iterator,bool> uniq;
+ pair<NodeVecType::iterator,bool> uniq;
hashedNodeVec *nv = new hashedNodeVec(nodes);
uniq = cache.insert(nv);
if (uniq.second == false) {
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
index f8fe3d3..3e151d8 100644
--- a/parser/libapparmor_re/hfa.h
+++ b/parser/libapparmor_re/hfa.h
@@ -28,6 +28,11 @@
#include <map>
#include <vector>
+#ifdef CXX11_UNORDERED_CONTAINERS
+#include <tr1/unordered_map>
+using std::tr1::unordered_map;
+#endif
+
#include <assert.h>
#include <stdint.h>
@@ -153,6 +158,12 @@ public:
return anodes < rhs.anodes;
return nnodes < rhs.nnodes;
}
+ bool operator==(ProtoState const &rhs)const
+ {
+ if (nnodes == rhs.nnodes)
+ return true;
+ return false;
+ }
unsigned long size(void)
{
@@ -251,14 +262,39 @@ public:
ostream &operator<<(ostream &os, const State &state);
+#ifdef CXX11_UNORDERED_CONTAINERS
+struct NodeMap_eq {
+ bool operator()(ProtoState const &lhs, ProtoState const &rhs)const
+ {
+ return lhs == rhs;
+ }
+};
+
+struct NodeMap_hash {
+ size_t operator()(ProtoState const & x) const noexcept
+ {
+ size_t hash = 5381;
+ if (x.nnodes)
+ hash = ((hash << 5) + hash) ^ x.nnodes->hash;
+ if (x.anodes)
+ hash = ((hash << 5) + hash) ^ (size_t) x.anodes;
+ return hash;
+ }
+};
+
+typedef unordered_map<ProtoState, State *, NodeMap_hash> NodeMapType;
+#else
+typedef map<ProtoState, State *> NodeMapType;
+#endif
+
class NodeMap: public CacheStats
{
public:
- typedef map<ProtoState, State *>::iterator iterator;
+ typedef NodeMapType::iterator iterator;
iterator begin() { return cache.begin(); }
iterator end() { return cache.end(); }
- map<ProtoState, State *> cache;
+ NodeMapType cache;
NodeMap(void): cache() { };
~NodeMap() { clear(); };
--
2.1.4
More information about the AppArmor
mailing list