From: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
This change improves performance of hashing functions used in AVC and
AVTab to hash 3x 32-bit values. As compared to original shift-xor function
used in AVC, substantial improvement in quality of hashing is gained by:
1. replacing shifts with rolls, thus preserving all of the incoming
entropy
2. adjusting shift/roll constants to reduce overlap between the input
values
3. use of arithmetic addition instead of XOR, as a way to spread out
collisions
4. use of hash_32() to level out the distribution of hash output values
throughout the range
Within the scope of particular application, these changes bring hash
quality to that of much more complex MurmurHash3 (which is currently used
in AVTab), while maintaining trivial simplicity of the original code.
The only price paid for the improvements is introduction of a single
32-bit multiplication instruction upon which hash_32() is built, which is
not a problem on almost any modern platform where fast multiplication is
available. For example, 32-bit MULs have had latency of 4 on pretty much
all Intel x86 CPUs for at least a decade or so (while ADD/XOR/SHL/ROL have
latency of 1). Platforms without fast multiplication provide their own
alternative mechanism for hash_32().
New hash function hash3() had been applied to two key parts of SELinux:
Access Vector Cache (AVC) and Access Vector Table (AVTab) with results
that follow.
AVC:
Below is the content of hash_stats, as observed on Fedora 32 in its
default configuration with targeted policy, averaged over 100 samples. The
stats show that new hash function not only cuts the longest chain almost
in half, but also provides a much better distribution throughout the table:
about 39% more buckets are being used, with at least half of all non-zero
buckets consistently staying at length 1, with 75% at 2 or below.
/sys/fs/selinux/avc/hash_stats:
Old New
Samples: 100 100
Entries: 504.43 503.67
Buckets: 219.73 304.61
1st Qu.: 1.00 1.00
Median : 1.39 1.00
3rd Qu.: 3.00 2.00
Maximum: 9.32 5.37
Next, performance of avc_lookup() is analyzed by timing it with ftrace on
a system with same configuration as above:
acv_lookup(), latency in us:
Old New
Samples: 261534 244168
Min. : 0.1320 0.1310
1st Qu.: 0.2410 0.2360
Median : 0.4220 0.4240
3rd Qu.: 0.5580 0.5600
Max. : 9.9300 9.9890
Considering small size of AVC in default configuration, the change does
not show any latency improvements. In fact, median and 75th percentile
timings appear to be in line with addition of extra 4 clock cycles for MUL
(roughly 2ns on a 2.2Ghz CPU), or 0.47%. This appears to be a small price
to pay for substantially better distribution of hash values, reducing a
probability and/or severity of potential pathological behavior on some
larger configurations.
Note that absolute max latency is likely not indicative, as it is
susceptible to one-off events such as interrupts, cache misses, etc.
AVTab:
Unlike AVC, AVTab hash table is much larger and much more densely
populated. In the past, need for better hashing in AVTab was demonstrated,
resulting in transition to a local copy of custom implementation of much
more complicated (and better) MurmurHash3, adapted for hashing of 3x u32s.
This change replaces MurmurHash3 with a much simpler, faster, yet just as
effective (at least, in this particular use case) hash3() function
described above.
As evidenced by debug output produced during the boot process, despite
being much simpler, hash3() yields quite similar (if not just a tiny bit
better) hash distribution quality within AVTab:
Old:
rules: 81014 entries and 29600/32768 buckets used, longest chain length
11 non-zero Q1/Med/Q3 2/2/4 sum of chain length^2 290030
New:
rules: 81014 entries and 29645/32768 buckets used, longest chain length
11 non-zero Q1/Med/Q3 2/2/4 sum of chain length^2 288810
Performance, though, is a different matter: a clear savings of 8ns to
10ns (75th and 50th percentiles respectively) had been measured with
ftrace for the most frequent AVTab lookup method:
avtab_search_node(), latency in us:
Old New
Samples: 5953243 5458099
Min. : 0.136 0.129
1st Qu.: 0.199 0.189
Median : 0.219 0.209
3rd Qu.: 0.294 0.286
Max. :10.000 9.990
The results are not as clear for much less frequently (that is 1500x call
frequency difference) used avtab_search(), though they appear to lean
towards a positive side:
avtab_search(), latency in us:
Old New
Samples: 3863 3638
Min. : 0.165 0.157
1st Qu.: 0.297 0.293
Median : 0.510 0.517
3rd Qu.: 0.803 0.774
Max. : 9.343 7.701
Signed-off-by: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
---
Please CC me directly on all replies.
security/selinux/avc.c | 8 +++--
security/selinux/include/hash3.h | 44 ++++++++++++++++++++++++
security/selinux/ss/avtab.c | 57 ++++++++++----------------------
security/selinux/ss/avtab.h | 1 +
4 files changed, 67 insertions(+), 43 deletions(-)
create mode 100644 security/selinux/include/hash3.h
diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index c3bbdb083371..ed092324bef1 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -30,12 +30,14 @@
#include "avc.h"
#include "avc_ss.h"
#include "classmap.h"
+#include "hash3.h"
#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
#include "median.h"
#endif
-#define AVC_CACHE_SLOTS 512
+#define AVC_CACHE_BITS (9)
+#define AVC_CACHE_SLOTS (1 << AVC_CACHE_BITS)
#define AVC_DEF_CACHE_THRESHOLD 512
#define AVC_CACHE_RECLAIM 16
@@ -125,9 +127,9 @@ static struct kmem_cache *avc_xperms_data_cachep;
static struct kmem_cache *avc_xperms_decision_cachep;
static struct kmem_cache *avc_xperms_cachep;
-static inline int avc_hash(u32 ssid, u32 tsid, u16 tclass)
+static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
{
- return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
+ return hash3(ssid, tsid, tclass, AVC_CACHE_BITS);
}
/**
diff --git a/security/selinux/include/hash3.h b/security/selinux/include/hash3.h
new file mode 100644
index 000000000000..21e2408f5227
--- /dev/null
+++ b/security/selinux/include/hash3.h
@@ -0,0 +1,44 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/* (C) Siarhei Liakh <Siarhei.Liakh@xxxxxxxxxxxxxxxxx>, 2020, GPL 2.0+ */
+
+#ifndef _SELINUX_HASH3_H
+#define _SELINUX_HASH3_H
+
+#include <linux/hash.h>
+#include <linux/bitops.h>
+
+/*
+ * hash3(): Mix and hash 3 x u32's with minimal overhead,
+ * truncate result to requested number of bits.
+ *
+ * This hash function produces very good results for inputs where most of
+ * input entropy is contained within the lower 11 bits of each of the words.
+ *
+ * For example, AVC hash table (in avc.c) is indexed by a 3-tuple (u32 ssid,
+ * u32 tsid, u16 tclass), where (on Fedora 32 Beta, as of March 2020) ssid and
+ * tsid appear to be sequential indexes between 0x0 and 0xA00, while tclass
+ * appears to be confined to the lower 8 bits, resulting in almost perfect
+ * packing of the indexes into a single 32-bit value.
+ *
+ * The function still produces reasonable hash values even when input value
+ * ranges span beyond 11 bits, as long as the placement of entropy within the
+ * input values is roughly the same for each of the componets (a, b, c), and
+ * the address space (a, b, c) is sparsely populated. Such behaviour is the
+ * result of two conscious choices: (1) use of rol32() to preserve all of the
+ * incoming entropy (as opposed to simple shifts which discard some input bits)
+ * and (2) use of arithmetic addition which carries over colliding bits (as
+ * opposed to binary XOR, which does not carry).
+ *
+ * The function will produce horrible collisions if input entropy is distrubuted
+ * within (a, b, c) such that it ends up within the same bit ranges after
+ * rotations, and the address space is densly populated. If that is the case,
+ * then two options are available:
+ * 1. Try switching around some of the inputs. EX: (a, b, c) => (b, c, a)
+ * 2. Use a real hash, such as jhash_3words() from linux/jhash.h
+ */
+static inline u32 hash3(u32 a, u32 b, u32 c, int bits)
+{
+ return hash_32(a + rol32(b, 11) + rol32(c, 22), bits);
+}
+
+#endif /* #ifndef _SELINUX_HASH3_H */
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 8baaddb01a95..d24f18ab9e4d 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -22,6 +22,7 @@
#include <linux/errno.h>
#include "avtab.h"
#include "policydb.h"
+#include "hash3.h"
#ifdef CONFIG_SECURITY_SELINUX_DEBUG_HASHES
#include "median.h"
@@ -30,43 +31,10 @@
static struct kmem_cache *avtab_node_cachep;
static struct kmem_cache *avtab_xperms_cachep;
-/* Based on MurmurHash3, written by Austin Appleby and placed in the
- * public domain.
- */
-static inline int avtab_hash(struct avtab_key *keyp, u32 mask)
+static inline u32 avtab_hash(struct avtab_key *keyp, u32 bits)
{
- static const u32 c1 = 0xcc9e2d51;
- static const u32 c2 = 0x1b873593;
- static const u32 r1 = 15;
- static const u32 r2 = 13;
- static const u32 m = 5;
- static const u32 n = 0xe6546b64;
-
- u32 hash = 0;
-
-#define mix(input) { \
- u32 v = input; \
- v *= c1; \
- v = (v << r1) | (v >> (32 - r1)); \
- v *= c2; \
- hash ^= v; \
- hash = (hash << r2) | (hash >> (32 - r2)); \
- hash = hash * m + n; \
-}
-
- mix(keyp->target_class);
- mix(keyp->target_type);
- mix(keyp->source_type);
-
-#undef mix
-
- hash ^= hash >> 16;
- hash *= 0x85ebca6b;
- hash ^= hash >> 13;
- hash *= 0xc2b2ae35;
- hash ^= hash >> 16;
-
- return hash & mask;
+ return hash3(keyp->target_class, keyp->target_type,
+ keyp->source_type, bits);
}
static struct avtab_node*
@@ -116,7 +84,7 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
if (!h)
return -EINVAL;
- hvalue = avtab_hash(key, h->mask);
+ hvalue = avtab_hash(key, h->bits);
for (prev = NULL, cur = h->htable[hvalue];
cur;
prev = cur, cur = cur->next) {
@@ -160,7 +128,7 @@ avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datu
if (!h)
return NULL;
- hvalue = avtab_hash(key, h->mask);
+ hvalue = avtab_hash(key, h->bits);
for (prev = NULL, cur = h->htable[hvalue];
cur;
prev = cur, cur = cur->next) {
@@ -191,7 +159,7 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
if (!h)
return NULL;
- hvalue = avtab_hash(key, h->mask);
+ hvalue = avtab_hash(key, h->bits);
for (cur = h->htable[hvalue]; cur;
cur = cur->next) {
if (key->source_type == cur->key.source_type &&
@@ -227,7 +195,7 @@ avtab_search_node(struct avtab *h, struct avtab_key *key)
if (!h)
return NULL;
- hvalue = avtab_hash(key, h->mask);
+ hvalue = avtab_hash(key, h->bits);
for (cur = h->htable[hvalue]; cur;
cur = cur->next) {
if (key->source_type == cur->key.source_type &&
@@ -301,6 +269,7 @@ void avtab_destroy(struct avtab *h)
h->htable = NULL;
h->nslot = 0;
h->mask = 0;
+ h->bits = 0;
}
void avtab_init(struct avtab *h)
@@ -313,6 +282,7 @@ void avtab_init(struct avtab *h)
int avtab_alloc(struct avtab *h, u32 nrules)
{
u32 mask = 0;
+ u32 bits = 0;
u32 shift = 0;
u32 work = nrules;
u32 nslot = 0;
@@ -339,6 +309,13 @@ int avtab_alloc(struct avtab *h, u32 nrules)
h->nel = 0;
h->nslot = nslot;
h->mask = mask;
+
+ while (mask) {
+ mask = mask >> 1;
+ bits++;
+ }
+
+ h->bits = bits;
pr_debug("SELinux: %d avtab hash slots, %d rules.\n",
h->nslot, nrules);
return 0;
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 5fdcb6696bcc..bf24d8094019 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -85,6 +85,7 @@ struct avtab {
u32 nel; /* number of elements */
u32 nslot; /* number of hash slots */
u32 mask; /* mask to compute hash func */
+ u32 bits; /* number of bits in mask */
};
void avtab_init(struct avtab *h);
--
2.17.1
