[RFC PATCH v2 4/4] [squash] add back reverse lookup cache to sidtab

[Ondrej Mosnacek <omosnace@redhat.com>]

This patch adds a simple cache for reverse lookup to the new sidtab
implementation. The cache works in a very similar way as the old
implementation's cache. The only difference is that instead of storing
pointers to the hash table nodes it stores just the indices of the
'cached' entries.

The new cache ensures that the indices are loaded/stored atomically, but
it still has the drawback that concurrent cache updates may mess up the
contents of the cache. Such situation however only reduces its
effectivity, not the correctness of lookups.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 security/selinux/ss/sidtab.c | 49 ++++++++++++++++++++++++++++++++++--
 security/selinux/ss/sidtab.h |  5 ++++
 2 files changed, 52 insertions(+), 2 deletions(-)

diff --git a/security/selinux/ss/sidtab.c b/security/selinux/ss/sidtab.c
index a82deecfac09..abd2beb6dafc 100644
--- a/security/selinux/ss/sidtab.c
+++ b/security/selinux/ss/sidtab.c
@@ -23,6 +23,9 @@ int sidtab_init(struct sidtab *s)
 
 	memset(s->roots, 0, sizeof(s->roots));
 
+	for (i = 0; i < SIDTAB_RCACHE_SIZE; i++)
+		atomic_set(&s->rcache[i], -1);
+
 	for (i = 0; i < SECINITSID_NUM; i++)
 		s->isids[i].set = 0;
 
@@ -204,6 +207,40 @@ static int sidtab_find_context(union sidtab_entry_inner entry,
 	return -ENOENT;
 }
 
+static void sidtab_rcache_update(struct sidtab *s, u32 index, u32 pos)
+{
+	while (pos > 0) {
+		atomic_set(&s->rcache[pos], atomic_read(&s->rcache[pos - 1]));
+		--pos;
+	}
+	atomic_set(&s->rcache[0], (int)index);
+}
+
+static void sidtab_rcache_push(struct sidtab *s, u32 index)
+{
+	sidtab_rcache_update(s, index, SIDTAB_RCACHE_SIZE - 1);
+}
+
+static int sidtab_rcache_search(struct sidtab *s, struct context *context,
+				u32 *index)
+{
+	u32 i;
+
+	for (i = 0; i < SIDTAB_RCACHE_SIZE; i++) {
+		int v = atomic_read(&s->rcache[i]);
+
+		if (v < 0)
+			continue;
+
+		if (context_cmp(sidtab_do_lookup(s, (u32)v, 0), context)) {
+			sidtab_rcache_update(s, (u32)v, i);
+			*index = (u32)v;
+			return 0;
+		}
+	}
+	return -ENOENT;
+}
+
 static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 				 u32 *index)
 {
@@ -214,6 +251,10 @@ static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 	struct context *dst, *dst_convert;
 	int rc;
 
+	rc = sidtab_rcache_search(s, context, index);
+	if (rc == 0)
+		return 0;
+
 	level = sidtab_level_from_count(count);
 
 	/* read entries after reading count */
@@ -222,8 +263,10 @@ static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 	pos = 0;
 	rc = sidtab_find_context(s->roots[level], &pos, count, level,
 				 context, index);
-	if (rc == 0)
+	if (rc == 0) {
+		sidtab_rcache_push(s, *index);
 		return 0;
+	}
 
 	/* lock-free search failed: lock, re-search, and insert if not found */
 	spin_lock_irqsave(&s->lock, flags);
@@ -235,8 +278,9 @@ static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 	/* if count has changed before we acquired the lock, then catch up */
 	while (count < count_locked) {
 		if (context_cmp(sidtab_do_lookup(s, count, 0), context)) {
-			rc = 0;
+			sidtab_rcache_push(s, count);
 			*index = count;
+			rc = 0;
 			goto out_unlock;
 		}
 		++count;
@@ -278,6 +322,7 @@ static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 		pr_info("SELinux:  Context %s is not valid (left unmapped).\n",
 			context->str);
 
+	sidtab_rcache_push(s, count);
 	*index = count;
 
 	/* write entries before writing new count */
diff --git a/security/selinux/ss/sidtab.h b/security/selinux/ss/sidtab.h
index 292512792a70..2bf50bf12751 100644
--- a/security/selinux/ss/sidtab.h
+++ b/security/selinux/ss/sidtab.h
@@ -66,12 +66,17 @@ struct sidtab_convert_params {
 	struct sidtab *target;
 };
 
+#define SIDTAB_RCACHE_SIZE 4
+
 struct sidtab {
 	union sidtab_entry_inner roots[SIDTAB_MAX_LEVEL + 1];
 	atomic_t count;
 	struct sidtab_convert_params *convert;
 	spinlock_t lock;
 
+	/* reverse lookup cache */
+	atomic_t rcache[SIDTAB_RCACHE_SIZE];
+
 	/* index == SID - 1 (no entry for SECSID_NULL) */
 	struct sidtab_isid_entry isids[SECINITSID_NUM];
 };
-- 
2.19.1