5 files changed, 468 insertions, 324 deletions

diff --git a/security/selinux/ss/mls.c b/security/selinux/ss/mls.c
index 2fe459df3c85..18ba0c2328fb 100644
--- a/security/selinux/ss/mls.c
+++ b/security/selinux/ss/mls.c
@@ -436,16 +436,17 @@ int mls_setup_user_range(struct policydb *p,
 
 /*
  * Convert the MLS fields in the security context
- * structure `c' from the values specified in the
- * policy `oldp' to the values specified in the policy `newp'.
+ * structure `oldc' from the values specified in the
+ * policy `oldp' to the values specified in the policy `newp',
+ * storing the resulting context in `newc'.
  */
 int mls_convert_context(struct policydb *oldp,
                         struct policydb *newp,
-                        struct context *c)
+                        struct context *oldc,
+                        struct context *newc)
 {
         struct level_datum *levdatum;
         struct cat_datum *catdatum;
-        struct ebitmap bitmap;
         struct ebitmap_node *node;
         int l, i;
 
@@ -455,28 +456,25 @@ int mls_convert_context(struct policydb *oldp,
         for (l = 0; l < 2; l++) {
                 levdatum = hashtab_search(newp->p_levels.table,
                                           sym_name(oldp, SYM_LEVELS,
-                                                   c->range.level[l].sens - 1));
+                                                   oldc->range.level[l].sens - 1));
 
                 if (!levdatum)
                         return -EINVAL;
-                c->range.level[l].sens = levdatum->level->sens;
+                newc->range.level[l].sens = levdatum->level->sens;
 
-                ebitmap_init(&bitmap);
-                ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i) {
+                ebitmap_for_each_positive_bit(&oldc->range.level[l].cat,
+                                              node, i) {
                         int rc;
 
                         catdatum = hashtab_search(newp->p_cats.table,
                                                   sym_name(oldp, SYM_CATS, i));
                         if (!catdatum)
                                 return -EINVAL;
-                        rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
+                        rc = ebitmap_set_bit(&newc->range.level[l].cat,
+                                             catdatum->value - 1, 1);
                         if (rc)
                                 return rc;
-
-                        cond_resched();
                 }
-                ebitmap_destroy(&c->range.level[l].cat);
-                c->range.level[l].cat = bitmap;
         }
 
         return 0;
diff --git a/security/selinux/ss/mls.h b/security/selinux/ss/mls.h
index 67093647576d..7954b1e60b64 100644
--- a/security/selinux/ss/mls.h
+++ b/security/selinux/ss/mls.h
@@ -46,7 +46,8 @@ int mls_range_set(struct context *context, struct mls_range *range);
 
 int mls_convert_context(struct policydb *oldp,
                         struct policydb *newp,
-                        struct context *context);
+                        struct context *oldc,
+                        struct context *newc);
 
 int mls_compute_sid(struct policydb *p,
                     struct context *scontext,
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 4ff4b0edbf6b..dd44126c8d14 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1907,19 +1907,16 @@ struct convert_context_args {
 
 /*
  * Convert the values in the security context
- * structure `c' from the values specified
+ * structure `oldc' from the values specified
  * in the policy `p->oldp' to the values specified
- * in the policy `p->newp'.  Verify that the
- * context is valid under the new policy.
+ * in the policy `p->newp', storing the new context
+ * in `newc'.  Verify that the context is valid
+ * under the new policy.
  */
-static int convert_context(u32 key,
-                           struct context *c,
-                           void *p)
+static int convert_context(struct context *oldc, struct context *newc, void *p)
 {
         struct convert_context_args *args;
-        struct context oldc;
         struct ocontext *oc;
-        struct mls_range *range;
         struct role_datum *role;
         struct type_datum *typdatum;
         struct user_datum *usrdatum;
@@ -1929,76 +1926,65 @@ static int convert_context(u32 key,
 
         args = p;
 
-        if (c->str) {
-                struct context ctx;
-
-                rc = -ENOMEM;
-                s = kstrdup(c->str, GFP_KERNEL);
+        if (oldc->str) {
+                s = kstrdup(oldc->str, GFP_KERNEL);
                 if (!s)
-                        goto out;
+                        return -ENOMEM;
 
                 rc = string_to_context_struct(args->newp, NULL, s,
-                                              &ctx, SECSID_NULL);
-                kfree(s);
-                if (!rc) {
-                        pr_info("SELinux:  Context %s became valid (mapped).\n",
-                               c->str);
-                        /* Replace string with mapped representation. */
-                        kfree(c->str);
-                        memcpy(c, &ctx, sizeof(*c));
-                        goto out;
-                } else if (rc == -EINVAL) {
+                                              newc, SECSID_NULL);
+                if (rc == -EINVAL) {
                         /* Retain string representation for later mapping. */
-                        rc = 0;
-                        goto out;
-                } else {
+                        context_init(newc);
+                        newc->str = s;
+                        newc->len = oldc->len;
+                        return 0;
+                }
+                kfree(s);
+                if (rc) {
                         /* Other error condition, e.g. ENOMEM. */
                         pr_err("SELinux:   Unable to map context %s, rc = %d.\n",
-                               c->str, -rc);
-                        goto out;
+                               oldc->str, -rc);
+                        return rc;
                 }
+                pr_info("SELinux:  Context %s became valid (mapped).\n",
+                        oldc->str);
+                return 0;
         }
 
-        rc = context_cpy(&oldc, c);
-        if (rc)
-                goto out;
+        context_init(newc);
 
         /* Convert the user. */
         rc = -EINVAL;
         usrdatum = hashtab_search(args->newp->p_users.table,
-                                  sym_name(args->oldp, SYM_USERS, c->user - 1));
+                                  sym_name(args->oldp,
+                                           SYM_USERS, oldc->user - 1));
         if (!usrdatum)
                 goto bad;
-        c->user = usrdatum->value;
+        newc->user = usrdatum->value;
 
         /* Convert the role. */
         rc = -EINVAL;
         role = hashtab_search(args->newp->p_roles.table,
-                              sym_name(args->oldp, SYM_ROLES, c->role - 1));
+                              sym_name(args->oldp, SYM_ROLES, oldc->role - 1));
         if (!role)
                 goto bad;
-        c->role = role->value;
+        newc->role = role->value;
 
         /* Convert the type. */
         rc = -EINVAL;
         typdatum = hashtab_search(args->newp->p_types.table,
-                                  sym_name(args->oldp, SYM_TYPES, c->type - 1));
+                                  sym_name(args->oldp,
+                                           SYM_TYPES, oldc->type - 1));
         if (!typdatum)
                 goto bad;
-        c->type = typdatum->value;
+        newc->type = typdatum->value;
 
         /* Convert the MLS fields if dealing with MLS policies */
         if (args->oldp->mls_enabled && args->newp->mls_enabled) {
-                rc = mls_convert_context(args->oldp, args->newp, c);
+                rc = mls_convert_context(args->oldp, args->newp, oldc, newc);
                 if (rc)
                         goto bad;
-        } else if (args->oldp->mls_enabled && !args->newp->mls_enabled) {
-                /*
-                 * Switching between MLS and non-MLS policy:
-                 * free any storage used by the MLS fields in the
-                 * context for all existing entries in the sidtab.
-                 */
-                mls_context_destroy(c);
         } else if (!args->oldp->mls_enabled && args->newp->mls_enabled) {
                 /*
                  * Switching between non-MLS and MLS policy:
@@ -2016,38 +2002,30 @@ static int convert_context(u32 key,
                                 " the initial SIDs list\n");
                         goto bad;
                 }
-                range = &oc->context[0].range;
-                rc = mls_range_set(c, range);
+                rc = mls_range_set(newc, &oc->context[0].range);
                 if (rc)
                         goto bad;
         }
 
         /* Check the validity of the new context. */
-        if (!policydb_context_isvalid(args->newp, c)) {
-                rc = convert_context_handle_invalid_context(args->state,
-                                                            &oldc);
+        if (!policydb_context_isvalid(args->newp, newc)) {
+                rc = convert_context_handle_invalid_context(args->state, oldc);
                 if (rc)
                         goto bad;
         }
 
-        context_destroy(&oldc);
-
-        rc = 0;
-out:
-        return rc;
+        return 0;
 bad:
         /* Map old representation to string and save it. */
-        rc = context_struct_to_string(args->oldp, &oldc, &s, &len);
+        rc = context_struct_to_string(args->oldp, oldc, &s, &len);
         if (rc)
                 return rc;
-        context_destroy(&oldc);
-        context_destroy(c);
-        c->str = s;
-        c->len = len;
+        context_destroy(newc);
+        newc->str = s;
+        newc->len = len;
         pr_info("SELinux:  Context %s became invalid (unmapped).\n",
-               c->str);
-        rc = 0;
-        goto out;
+                newc->str);
+        return 0;
 }
 
 static void security_load_policycaps(struct selinux_state *state)
@@ -2091,6 +2069,7 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len)
         struct policydb *oldpolicydb, *newpolicydb;
         struct selinux_mapping *oldmapping;
         struct selinux_map newmap;
+        struct sidtab_convert_params convert_params;
         struct convert_context_args args;
         u32 seqno;
         int rc = 0;
@@ -2147,12 +2126,6 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len)
                 goto out;
         }
 
-        oldsidtab = state->ss->sidtab;
-
-#if 0
-        sidtab_hash_eval(oldsidtab, "sids");
-#endif
-
         rc = policydb_read(newpolicydb, fp);
         if (rc) {
                 kfree(newsidtab);
@@ -2184,6 +2157,8 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len)
                 goto err;
         }
 
+        oldsidtab = state->ss->sidtab;
+
         /*
          * Convert the internal representations of contexts
          * in the new SID table.
@@ -2191,7 +2166,12 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len)
         args.state = state;
         args.oldp = policydb;
         args.newp = newpolicydb;
-        rc = sidtab_convert(oldsidtab, newsidtab, convert_context, &args);
+
+        convert_params.func = convert_context;
+        convert_params.args = &args;
+        convert_params.target = newsidtab;
+
+        rc = sidtab_convert(oldsidtab, &convert_params);
         if (rc) {
                 pr_err("SELinux:  unable to convert the internal"
                         " representation of contexts in the new SID"
diff --git a/security/selinux/ss/sidtab.c b/security/selinux/ss/sidtab.c
index e44e7cec630c..e63a90ff2728 100644
--- a/security/selinux/ss/sidtab.c
+++ b/security/selinux/ss/sidtab.c
@@ -2,88 +2,41 @@
 /*
  * Implementation of the SID table type.
  *
- * Author : Stephen Smalley, <sds@tycho.nsa.gov>
+ * Original author: Stephen Smalley, <sds@tycho.nsa.gov>
+ * Author: Ondrej Mosnacek, <omosnacek@gmail.com>
+ *
+ * Copyright (C) 2018 Red Hat, Inc.
  */
+#include <linux/errno.h>
 #include <linux/kernel.h>
 #include <linux/slab.h>
+#include <linux/sched.h>
 #include <linux/spinlock.h>
-#include <linux/errno.h>
+#include <linux/atomic.h>
 #include "flask.h"
 #include "security.h"
 #include "sidtab.h"
 
-#define SIDTAB_HASH(sid) \
-(sid & SIDTAB_HASH_MASK)
-
 int sidtab_init(struct sidtab *s)
 {
-        int i;
+        u32 i;
 
-        s->htable = kmalloc_array(SIDTAB_SIZE, sizeof(*s->htable), GFP_ATOMIC);
-        if (!s->htable)
-                return -ENOMEM;
+        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;
 
-        for (i = 0; i < SIDTAB_SIZE; i++)
-                s->htable[i] = NULL;
+        atomic_set(&s->count, 0);
 
-        for (i = 0; i < SIDTAB_CACHE_LEN; i++)
-                s->cache[i] = NULL;
+        s->convert = NULL;
 
-        s->nel = 0;
-        s->next_sid = 0;
-        s->shutdown = 0;
         spin_lock_init(&s->lock);
         return 0;
 }
 
-static int sidtab_insert(struct sidtab *s, u32 sid, struct context *context)
-{
-        int hvalue;
-        struct sidtab_node *prev, *cur, *newnode;
-
-        if (!s)
-                return -ENOMEM;
-
-        hvalue = SIDTAB_HASH(sid);
-        prev = NULL;
-        cur = s->htable[hvalue];
-        while (cur && sid > cur->sid) {
-                prev = cur;
-                cur = cur->next;
-        }
-
-        if (cur && sid == cur->sid)
-                return -EEXIST;
-
-        newnode = kmalloc(sizeof(*newnode), GFP_ATOMIC);
-        if (!newnode)
-                return -ENOMEM;
-
-        newnode->sid = sid;
-        if (context_cpy(&newnode->context, context)) {
-                kfree(newnode);
-                return -ENOMEM;
-        }
-
-        if (prev) {
-                newnode->next = prev->next;
-                wmb();
-                prev->next = newnode;
-        } else {
-                newnode->next = s->htable[hvalue];
-                wmb();
-                s->htable[hvalue] = newnode;
-        }
-
-        s->nel++;
-        if (sid >= s->next_sid)
-                s->next_sid = sid + 1;
-        return 0;
-}
-
 int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
 {
         struct sidtab_isid_entry *entry;
@@ -102,20 +55,90 @@ int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
         return 0;
 }
 
-static struct context *sidtab_lookup(struct sidtab *s, u32 sid)
+static u32 sidtab_level_from_count(u32 count)
 {
-        int hvalue;
-        struct sidtab_node *cur;
+        u32 capacity = SIDTAB_LEAF_ENTRIES;
+        u32 level = 0;
+
+        while (count > capacity) {
+                capacity <<= SIDTAB_INNER_SHIFT;
+                ++level;
+        }
+        return level;
+}
+
+static int sidtab_alloc_roots(struct sidtab *s, u32 level)
+{
+        u32 l;
+
+        if (!s->roots[0].ptr_leaf) {
+                s->roots[0].ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                               GFP_ATOMIC);
+                if (!s->roots[0].ptr_leaf)
+                        return -ENOMEM;
+        }
+        for (l = 1; l <= level; ++l)
+                if (!s->roots[l].ptr_inner) {
+                        s->roots[l].ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                                        GFP_ATOMIC);
+                        if (!s->roots[l].ptr_inner)
+                                return -ENOMEM;
+                        s->roots[l].ptr_inner->entries[0] = s->roots[l - 1];
+                }
+        return 0;
+}
+
+static struct context *sidtab_do_lookup(struct sidtab *s, u32 index, int alloc)
+{
+        union sidtab_entry_inner *entry;
+        u32 level, capacity_shift, leaf_index = index / SIDTAB_LEAF_ENTRIES;
+
+        /* find the level of the subtree we need */
+        level = sidtab_level_from_count(index + 1);
+        capacity_shift = level * SIDTAB_INNER_SHIFT;
+
+        /* allocate roots if needed */
+        if (alloc && sidtab_alloc_roots(s, level) != 0)
+                return NULL;
+
+        /* lookup inside the subtree */
+        entry = &s->roots[level];
+        while (level != 0) {
+                capacity_shift -= SIDTAB_INNER_SHIFT;
+                --level;
+
+                entry = &entry->ptr_inner->entries[leaf_index >> capacity_shift];
+                leaf_index &= ((u32)1 << capacity_shift) - 1;
+
+                if (!entry->ptr_inner) {
+                        if (alloc)
+                                entry->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                                           GFP_ATOMIC);
+                        if (!entry->ptr_inner)
+                                return NULL;
+                }
+        }
+        if (!entry->ptr_leaf) {
+                if (alloc)
+                        entry->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                                  GFP_ATOMIC);
+                if (!entry->ptr_leaf)
+                        return NULL;
+        }
+        return &entry->ptr_leaf->entries[index % SIDTAB_LEAF_ENTRIES].context;
+}
 
-        hvalue = SIDTAB_HASH(sid);
-        cur = s->htable[hvalue];
-        while (cur && sid > cur->sid)
-                cur = cur->next;
+static struct context *sidtab_lookup(struct sidtab *s, u32 index)
+{
+        u32 count = (u32)atomic_read(&s->count);
 
-        if (!cur || sid != cur->sid)
+        if (index >= count)
                 return NULL;
 
-        return &cur->context;
+        /* read entries after reading count */
+        smp_rmb();
+
+        return sidtab_do_lookup(s, index, 0);
 }
 
 static struct context *sidtab_lookup_initial(struct sidtab *s, u32 sid)
@@ -127,9 +150,6 @@ static struct context *sidtab_search_core(struct sidtab *s, u32 sid, int force)
 {
         struct context *context;
 
-        if (!s)
-                return NULL;
-
         if (sid != 0) {
                 if (sid > SECINITSID_NUM)
                         context = sidtab_lookup(s, sid - (SECINITSID_NUM + 1));
@@ -152,102 +172,69 @@ struct context *sidtab_search_force(struct sidtab *s, u32 sid)
         return sidtab_search_core(s, sid, 1);
 }
 
-static int sidtab_map(struct sidtab *s,
-                      int (*apply)(u32 sid,
-                                   struct context *context,
-                                   void *args),
-                      void *args)
+static int sidtab_find_context(union sidtab_entry_inner entry,
+                               u32 *pos, u32 count, u32 level,
+                               struct context *context, u32 *index)
 {
-        int i, rc = 0;
-        struct sidtab_node *cur;
+        int rc;
+        u32 i;
 
-        if (!s)
-                goto out;
+        if (level != 0) {
+                struct sidtab_node_inner *node = entry.ptr_inner;
 
-        for (i = 0; i < SIDTAB_SIZE; i++) {
-                cur = s->htable[i];
-                while (cur) {
-                        rc = apply(cur->sid, &cur->context, args);
-                        if (rc)
-                                goto out;
-                        cur = cur->next;
+                i = 0;
+                while (i < SIDTAB_INNER_ENTRIES && *pos < count) {
+                        rc = sidtab_find_context(node->entries[i],
+                                                 pos, count, level - 1,
+                                                 context, index);
+                        if (rc == 0)
+                                return 0;
+                        i++;
+                }
+        } else {
+                struct sidtab_node_leaf *node = entry.ptr_leaf;
+
+                i = 0;
+                while (i < SIDTAB_LEAF_ENTRIES && *pos < count) {
+                        if (context_cmp(&node->entries[i].context, context)) {
+                                *index = *pos;
+                                return 0;
+                        }
+                        (*pos)++;
+                        i++;
                 }
         }
-out:
-        return rc;
+        return -ENOENT;
 }
 
-/* Clone the SID into the new SID table. */
-static int clone_sid(u32 sid, struct context *context, void *arg)
+static void sidtab_rcache_update(struct sidtab *s, u32 index, u32 pos)
 {
-        struct sidtab *s = arg;
-        return sidtab_insert(s, sid, context);
+        while (pos > 0) {
+                atomic_set(&s->rcache[pos], atomic_read(&s->rcache[pos - 1]));
+                --pos;
+        }
+        atomic_set(&s->rcache[0], (int)index);
 }
 
-int sidtab_convert(struct sidtab *s, struct sidtab *news,
-                   int (*convert)(u32 sid,
-                                  struct context *context,
-                                  void *args),
-                   void *args)
+static void sidtab_rcache_push(struct sidtab *s, u32 index)
 {
-        unsigned long flags;
-        int rc;
-
-        spin_lock_irqsave(&s->lock, flags);
-        s->shutdown = 1;
-        spin_unlock_irqrestore(&s->lock, flags);
-
-        rc = sidtab_map(s, clone_sid, news);
-        if (rc)
-                return rc;
-
-        return sidtab_map(news, convert, args);
+        sidtab_rcache_update(s, index, SIDTAB_RCACHE_SIZE - 1);
 }
 
-static void sidtab_update_cache(struct sidtab *s, struct sidtab_node *n, int loc)
+static int sidtab_rcache_search(struct sidtab *s, struct context *context,
+                                u32 *index)
 {
-        BUG_ON(loc >= SIDTAB_CACHE_LEN);
+        u32 i;
 
-        while (loc > 0) {
-                s->cache[loc] = s->cache[loc - 1];
-                loc--;
-        }
-        s->cache[0] = n;
-}
+        for (i = 0; i < SIDTAB_RCACHE_SIZE; i++) {
+                int v = atomic_read(&s->rcache[i]);
 
-static inline int sidtab_search_context(struct sidtab *s,
-                                        struct context *context, u32 *sid)
-{
-        int i;
-        struct sidtab_node *cur;
-
-        for (i = 0; i < SIDTAB_SIZE; i++) {
-                cur = s->htable[i];
-                while (cur) {
-                        if (context_cmp(&cur->context, context)) {
-                                sidtab_update_cache(s, cur, SIDTAB_CACHE_LEN - 1);
-                                *sid = cur->sid;
-                                return 0;
-                        }
-                        cur = cur->next;
-                }
-        }
-        return -ENOENT;
-}
+                if (v < 0)
+                        continue;
 
-static inline int sidtab_search_cache(struct sidtab *s, struct context *context,
-                                      u32 *sid)
-{
-        int i;
-        struct sidtab_node *node;
-
-        for (i = 0; i < SIDTAB_CACHE_LEN; i++) {
-                node = s->cache[i];
-                if (unlikely(!node))
-                        return -ENOENT;
-                if (context_cmp(&node->context, context)) {
-                        sidtab_update_cache(s, node, i);
-                        *sid = node->sid;
+                if (context_cmp(sidtab_do_lookup(s, (u32)v, 0), context)) {
+                        sidtab_rcache_update(s, (u32)v, i);
+                        *index = (u32)v;
                         return 0;
                 }
         }
@@ -255,38 +242,98 @@ static inline int sidtab_search_cache(struct sidtab *s, struct context *context,
 }
 
 static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
-                                 u32 *sid)
+                                 u32 *index)
 {
-        int ret;
         unsigned long flags;
+        u32 count = (u32)atomic_read(&s->count);
+        u32 count_locked, level, pos;
+        struct sidtab_convert_params *convert;
+        struct context *dst, *dst_convert;
+        int rc;
 
-        ret = sidtab_search_cache(s, context, sid);
-        if (ret)
-                ret = sidtab_search_context(s, context, sid);
-        if (ret) {
-                spin_lock_irqsave(&s->lock, flags);
-                /* Rescan now that we hold the lock. */
-                ret = sidtab_search_context(s, context, sid);
-                if (!ret)
-                        goto unlock_out;
-                /* No SID exists for the context.  Allocate a new one. */
-                if (s->next_sid == (UINT_MAX - SECINITSID_NUM - 1) ||
-                    s->shutdown) {
-                        ret = -ENOMEM;
-                        goto unlock_out;
+        rc = sidtab_rcache_search(s, context, index);
+        if (rc == 0)
+                return 0;
+
+        level = sidtab_level_from_count(count);
+
+        /* read entries after reading count */
+        smp_rmb();
+
+        pos = 0;
+        rc = sidtab_find_context(s->roots[level], &pos, count, level,
+                                 context, index);
+        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);
+
+        convert = s->convert;
+        count_locked = (u32)atomic_read(&s->count);
+        level = sidtab_level_from_count(count_locked);
+
+        /* 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)) {
+                        sidtab_rcache_push(s, count);
+                        *index = count;
+                        rc = 0;
+                        goto out_unlock;
                 }
-                *sid = s->next_sid++;
-                if (context->len)
-                        pr_info("SELinux:  Context %s is not valid (left unmapped).\n",
-                               context->str);
-                ret = sidtab_insert(s, *sid, context);
-                if (ret)
-                        s->next_sid--;
-unlock_out:
-                spin_unlock_irqrestore(&s->lock, flags);
+                ++count;
+        }
+
+        /* insert context into new entry */
+        rc = -ENOMEM;
+        dst = sidtab_do_lookup(s, count, 1);
+        if (!dst)
+                goto out_unlock;
+
+        rc = context_cpy(dst, context);
+        if (rc)
+                goto out_unlock;
+
+        /*
+         * if we are building a new sidtab, we need to convert the context
+         * and insert it there as well
+         */
+        if (convert) {
+                rc = -ENOMEM;
+                dst_convert = sidtab_do_lookup(convert->target, count, 1);
+                if (!dst_convert) {
+                        context_destroy(dst);
+                        goto out_unlock;
+                }
+
+                rc = convert->func(context, dst_convert, convert->args);
+                if (rc) {
+                        context_destroy(dst);
+                        goto out_unlock;
+                }
+
+                /* at this point we know the insert won't fail */
+                atomic_set(&convert->target->count, count + 1);
         }
 
-        return ret;
+        if (context->len)
+                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 */
+        smp_wmb();
+
+        atomic_set(&s->count, count + 1);
+
+        rc = 0;
+out_unlock:
+        spin_unlock_irqrestore(&s->lock, flags);
+        return rc;
 }
 
 int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid)
@@ -310,57 +357,139 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid)
         return 0;
 }
 
-void sidtab_hash_eval(struct sidtab *h, char *tag)
+static int sidtab_convert_tree(union sidtab_entry_inner *edst,
+                               union sidtab_entry_inner *esrc,
+                               u32 *pos, u32 count, u32 level,
+                               struct sidtab_convert_params *convert)
 {
-        int i, chain_len, slots_used, max_chain_len;
-        struct sidtab_node *cur;
-
-        slots_used = 0;
-        max_chain_len = 0;
-        for (i = 0; i < SIDTAB_SIZE; i++) {
-                cur = h->htable[i];
-                if (cur) {
-                        slots_used++;
-                        chain_len = 0;
-                        while (cur) {
-                                chain_len++;
-                                cur = cur->next;
-                        }
+        int rc;
+        u32 i;
 
-                        if (chain_len > max_chain_len)
-                                max_chain_len = chain_len;
+        if (level != 0) {
+                if (!edst->ptr_inner) {
+                        edst->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                                  GFP_KERNEL);
+                        if (!edst->ptr_inner)
+                                return -ENOMEM;
                 }
+                i = 0;
+                while (i < SIDTAB_INNER_ENTRIES && *pos < count) {
+                        rc = sidtab_convert_tree(&edst->ptr_inner->entries[i],
+                                                 &esrc->ptr_inner->entries[i],
+                                                 pos, count, level - 1,
+                                                 convert);
+                        if (rc)
+                                return rc;
+                        i++;
+                }
+        } else {
+                if (!edst->ptr_leaf) {
+                        edst->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
+                                                 GFP_KERNEL);
+                        if (!edst->ptr_leaf)
+                                return -ENOMEM;
+                }
+                i = 0;
+                while (i < SIDTAB_LEAF_ENTRIES && *pos < count) {
+                        rc = convert->func(&esrc->ptr_leaf->entries[i].context,
+                                           &edst->ptr_leaf->entries[i].context,
+                                           convert->args);
+                        if (rc)
+                                return rc;
+                        (*pos)++;
+                        i++;
+                }
+                cond_resched();
+        }
+        return 0;
+}
+
+int sidtab_convert(struct sidtab *s, struct sidtab_convert_params *params)
+{
+        unsigned long flags;
+        u32 count, level, pos;
+        int rc;
+
+        spin_lock_irqsave(&s->lock, flags);
+
+        /* concurrent policy loads are not allowed */
+        if (s->convert) {
+                spin_unlock_irqrestore(&s->lock, flags);
+                return -EBUSY;
         }
 
-        pr_debug("%s:  %d entries and %d/%d buckets used, longest "
-               "chain length %d\n", tag, h->nel, slots_used, SIDTAB_SIZE,
-               max_chain_len);
+        count = (u32)atomic_read(&s->count);
+        level = sidtab_level_from_count(count);
+
+        /* allocate last leaf in the new sidtab (to avoid race with
+         * live convert)
+         */
+        rc = sidtab_do_lookup(params->target, count - 1, 1) ? 0 : -ENOMEM;
+        if (rc) {
+                spin_unlock_irqrestore(&s->lock, flags);
+                return rc;
+        }
+
+        /* set count in case no new entries are added during conversion */
+        atomic_set(&params->target->count, count);
+
+        /* enable live convert of new entries */
+        s->convert = params;
+
+        /* we can safely do the rest of the conversion outside the lock */
+        spin_unlock_irqrestore(&s->lock, flags);
+
+        pr_info("SELinux:  Converting %u SID table entries...\n", count);
+
+        /* convert all entries not covered by live convert */
+        pos = 0;
+        rc = sidtab_convert_tree(&params->target->roots[level],
+                                 &s->roots[level], &pos, count, level, params);
+        if (rc) {
+                /* we need to keep the old table - disable live convert */
+                spin_lock_irqsave(&s->lock, flags);
+                s->convert = NULL;
+                spin_unlock_irqrestore(&s->lock, flags);
+        }
+        return rc;
 }
 
-void sidtab_destroy(struct sidtab *s)
+static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level)
 {
-        int i;
-        struct sidtab_node *cur, *temp;
+        u32 i;
+
+        if (level != 0) {
+                struct sidtab_node_inner *node = entry.ptr_inner;
+
+                if (!node)
+                        return;
+
+                for (i = 0; i < SIDTAB_INNER_ENTRIES; i++)
+                        sidtab_destroy_tree(node->entries[i], level - 1);
+                kfree(node);
+        } else {
+                struct sidtab_node_leaf *node = entry.ptr_leaf;
 
-        if (!s)
-                return;
+                if (!node)
+                        return;
+
+                for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++)
+                        context_destroy(&node->entries[i].context);
+                kfree(node);
+        }
+}
+
+void sidtab_destroy(struct sidtab *s)
+{
+        u32 i, level;
 
         for (i = 0; i < SECINITSID_NUM; i++)
                 if (s->isids[i].set)
                         context_destroy(&s->isids[i].context);
 
-        for (i = 0; i < SIDTAB_SIZE; i++) {
-                cur = s->htable[i];
-                while (cur) {
-                        temp = cur;
-                        cur = cur->next;
-                        context_destroy(&temp->context);
-                        kfree(temp);
-                }
-                s->htable[i] = NULL;
-        }
-        kfree(s->htable);
-        s->htable = NULL;
-        s->nel = 0;
-        s->next_sid = 1;
+        level = SIDTAB_MAX_LEVEL;
+        while (level && !s->roots[level].ptr_inner)
+                --level;
+
+        sidtab_destroy_tree(s->roots[level], level);
 }
diff --git a/security/selinux/ss/sidtab.h b/security/selinux/ss/sidtab.h
index e657ae6bf996..bbd5c0d1f3bd 100644
--- a/security/selinux/ss/sidtab.h
+++ b/security/selinux/ss/sidtab.h
@@ -1,41 +1,82 @@
 /* SPDX-License-Identifier: GPL-2.0 */
 /*
- * A security identifier table (sidtab) is a hash table
+ * A security identifier table (sidtab) is a lookup table
  * of security context structures indexed by SID value.
  *
- * Author : Stephen Smalley, <sds@tycho.nsa.gov>
+ * Original author: Stephen Smalley, <sds@tycho.nsa.gov>
+ * Author: Ondrej Mosnacek, <omosnacek@gmail.com>
+ *
+ * Copyright (C) 2018 Red Hat, Inc.
  */
 #ifndef _SS_SIDTAB_H_
 #define _SS_SIDTAB_H_
 
+#include <linux/spinlock_types.h>
+#include <linux/log2.h>
+
 #include "context.h"
 
-struct sidtab_node {
-        u32 sid;                /* security identifier */
-        struct context context; /* security context structure */
-        struct sidtab_node *next;
+struct sidtab_entry_leaf {
+        struct context context;
+};
+
+struct sidtab_node_inner;
+struct sidtab_node_leaf;
+
+union sidtab_entry_inner {
+        struct sidtab_node_inner *ptr_inner;
+        struct sidtab_node_leaf  *ptr_leaf;
 };
 
-#define SIDTAB_HASH_BITS 7
-#define SIDTAB_HASH_BUCKETS (1 << SIDTAB_HASH_BITS)
-#define SIDTAB_HASH_MASK (SIDTAB_HASH_BUCKETS-1)
+/* align node size to page boundary */
+#define SIDTAB_NODE_ALLOC_SHIFT PAGE_SHIFT
+#define SIDTAB_NODE_ALLOC_SIZE  PAGE_SIZE
+
+#define size_to_shift(size) ((size) == 1 ? 1 : (const_ilog2((size) - 1) + 1))
+
+#define SIDTAB_INNER_SHIFT \
+        (SIDTAB_NODE_ALLOC_SHIFT - size_to_shift(sizeof(union sidtab_entry_inner)))
+#define SIDTAB_INNER_ENTRIES ((size_t)1 << SIDTAB_INNER_SHIFT)
+#define SIDTAB_LEAF_ENTRIES \
+        (SIDTAB_NODE_ALLOC_SIZE / sizeof(struct sidtab_entry_leaf))
 
-#define SIDTAB_SIZE SIDTAB_HASH_BUCKETS
+#define SIDTAB_MAX_BITS 31 /* limited to INT_MAX due to atomic_t range */
+#define SIDTAB_MAX (((u32)1 << SIDTAB_MAX_BITS) - 1)
+/* ensure enough tree levels for SIDTAB_MAX entries */
+#define SIDTAB_MAX_LEVEL \
+        DIV_ROUND_UP(SIDTAB_MAX_BITS - size_to_shift(SIDTAB_LEAF_ENTRIES), \
+                     SIDTAB_INNER_SHIFT)
+
+struct sidtab_node_leaf {
+        struct sidtab_entry_leaf entries[SIDTAB_LEAF_ENTRIES];
+};
+
+struct sidtab_node_inner {
+        union sidtab_entry_inner entries[SIDTAB_INNER_ENTRIES];
+};
 
 struct sidtab_isid_entry {
         int set;
         struct context context;
 };
 
+struct sidtab_convert_params {
+        int (*func)(struct context *oldc, struct context *newc, void *args);
+        void *args;
+        struct sidtab *target;
+};
+
+#define SIDTAB_RCACHE_SIZE 3
+
 struct sidtab {
-        struct sidtab_node **htable;
-        unsigned int nel;       /* number of elements */
-        unsigned int next_sid;  /* next SID to allocate */
-        unsigned char shutdown;
-#define SIDTAB_CACHE_LEN        3
-        struct sidtab_node *cache[SIDTAB_CACHE_LEN];
+        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];
 };
@@ -45,15 +86,10 @@ int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context);
 struct context *sidtab_search(struct sidtab *s, u32 sid);
 struct context *sidtab_search_force(struct sidtab *s, u32 sid);
 
-int sidtab_convert(struct sidtab *s, struct sidtab *news,
-                   int (*apply)(u32 sid,
-                                struct context *context,
-                                void *args),
-                   void *args);
+int sidtab_convert(struct sidtab *s, struct sidtab_convert_params *params);
 
 int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid);
 
-void sidtab_hash_eval(struct sidtab *h, char *tag);
 void sidtab_destroy(struct sidtab *s);
 
 #endif  /* _SS_SIDTAB_H_ */