Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/ebiederm/user-namespace

Pull user namespace update from Eric Biederman:
 "The only change that is production ready this round is the work to
  increase the number of uid and gid mappings a user namespace can
  support from 5 to 340.

  This code was carefully benchmarked and it was confirmed that in the
  existing cases the performance remains the same. In the worst case
  with 340 mappings an cache cold stat times go from 158ns to 248ns.
  That is noticable but still quite small, and only the people who are
  doing crazy things pay the cost.

  This work uncovered some documentation and cleanup opportunities in
  the mapping code, and patches to make those cleanups and improve the
  documentation will be coming in the next merge window"

* 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/ebiederm/user-namespace:
  userns: Simplify insert_extent
  userns: Make map_id_down a wrapper for map_id_range_down
  userns: Don't read extents twice in m_start
  userns: Simplify the user and group mapping functions
  userns: Don't special case a count of 0
  userns: bump idmap limits to 340
  userns: use union in {g,u}idmap struct

3 files changed, 325 insertions, 77 deletions

diff --git a/include/linux/user_namespace.h b/include/linux/user_namespace.h
index 3fe714da7f5a..d6b74b91096b 100644
--- a/include/linux/user_namespace.h
+++ b/include/linux/user_namespace.h
@@ -11,15 +11,24 @@
 #include <linux/sysctl.h>
 #include <linux/err.h>
 
-#define UID_GID_MAP_MAX_EXTENTS 5
+#define UID_GID_MAP_MAX_BASE_EXTENTS 5
+#define UID_GID_MAP_MAX_EXTENTS 340
 
-struct uid_gid_map {    /* 64 bytes -- 1 cache line */
+struct uid_gid_extent {
+        u32 first;
+        u32 lower_first;
+        u32 count;
+};
+
+struct uid_gid_map { /* 64 bytes -- 1 cache line */
         u32 nr_extents;
-        struct uid_gid_extent {
-                u32 first;
-                u32 lower_first;
-                u32 count;
-        } extent[UID_GID_MAP_MAX_EXTENTS];
+        union {
+                struct uid_gid_extent extent[UID_GID_MAP_MAX_BASE_EXTENTS];
+                struct {
+                        struct uid_gid_extent *forward;
+                        struct uid_gid_extent *reverse;
+                };
+        };
 };
 
 #define USERNS_SETGROUPS_ALLOWED 1UL
diff --git a/kernel/user.c b/kernel/user.c
index 00281add65b2..9a20acce460d 100644
--- a/kernel/user.c
+++ b/kernel/user.c
@@ -26,26 +26,32 @@
 struct user_namespace init_user_ns = {
         .uid_map = {
                 .nr_extents = 1,
-                .extent[0] = {
-                        .first = 0,
-                        .lower_first = 0,
-                        .count = 4294967295U,
+                {
+                        .extent[0] = {
+                                .first = 0,
+                                .lower_first = 0,
+                                .count = 4294967295U,
+                        },
                 },
         },
         .gid_map = {
                 .nr_extents = 1,
-                .extent[0] = {
-                        .first = 0,
-                        .lower_first = 0,
-                        .count = 4294967295U,
+                {
+                        .extent[0] = {
+                                .first = 0,
+                                .lower_first = 0,
+                                .count = 4294967295U,
+                        },
                 },
         },
         .projid_map = {
                 .nr_extents = 1,
-                .extent[0] = {
-                        .first = 0,
-                        .lower_first = 0,
-                        .count = 4294967295U,
+                {
+                        .extent[0] = {
+                                .first = 0,
+                                .lower_first = 0,
+                                .count = 4294967295U,
+                        },
                 },
         },
         .count = ATOMIC_INIT(3),
diff --git a/kernel/user_namespace.c b/kernel/user_namespace.c
index d32b45662fb6..246d4d4ce5c7 100644
--- a/kernel/user_namespace.c
+++ b/kernel/user_namespace.c
@@ -23,6 +23,8 @@
 #include <linux/ctype.h>
 #include <linux/projid.h>
 #include <linux/fs_struct.h>
+#include <linux/bsearch.h>
+#include <linux/sort.h>
 
 static struct kmem_cache *user_ns_cachep __read_mostly;
 static DEFINE_MUTEX(userns_state_mutex);
@@ -181,6 +183,18 @@ static void free_user_ns(struct work_struct *work)
         do {
                 struct ucounts *ucounts = ns->ucounts;
                 parent = ns->parent;
+                if (ns->gid_map.nr_extents > UID_GID_MAP_MAX_BASE_EXTENTS) {
+                        kfree(ns->gid_map.forward);
+                        kfree(ns->gid_map.reverse);
+                }
+                if (ns->uid_map.nr_extents > UID_GID_MAP_MAX_BASE_EXTENTS) {
+                        kfree(ns->uid_map.forward);
+                        kfree(ns->uid_map.reverse);
+                }
+                if (ns->projid_map.nr_extents > UID_GID_MAP_MAX_BASE_EXTENTS) {
+                        kfree(ns->projid_map.forward);
+                        kfree(ns->projid_map.reverse);
+                }
                 retire_userns_sysctls(ns);
 #ifdef CONFIG_PERSISTENT_KEYRINGS
                 key_put(ns->persistent_keyring_register);
@@ -198,26 +212,101 @@ void __put_user_ns(struct user_namespace *ns)
 }
 EXPORT_SYMBOL(__put_user_ns);
 
-static u32 map_id_range_down(struct uid_gid_map *map, u32 id, u32 count)
+/**
+ * idmap_key struct holds the information necessary to find an idmapping in a
+ * sorted idmap array. It is passed to cmp_map_id() as first argument.
+ */
+struct idmap_key {
+        bool map_up; /* true  -> id from kid; false -> kid from id */
+        u32 id; /* id to find */
+        u32 count; /* == 0 unless used with map_id_range_down() */
+};
+
+/**
+ * cmp_map_id - Function to be passed to bsearch() to find the requested
+ * idmapping. Expects struct idmap_key to be passed via @k.
+ */
+static int cmp_map_id(const void *k, const void *e)
 {
-        unsigned idx, extents;
+        u32 first, last, id2;
+        const struct idmap_key *key = k;
+        const struct uid_gid_extent *el = e;
+
+        id2 = key->id + key->count - 1;
+
+        /* handle map_id_{down,up}() */
+        if (key->map_up)
+                first = el->lower_first;
+        else
+                first = el->first;
+
+        last = first + el->count - 1;
+
+        if (key->id >= first && key->id <= last &&
+            (id2 >= first && id2 <= last))
+                return 0;
+
+        if (key->id < first || id2 < first)
+                return -1;
+
+        return 1;
+}
+
+/**
+ * map_id_range_down_max - Find idmap via binary search in ordered idmap array.
+ * Can only be called if number of mappings exceeds UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static struct uid_gid_extent *
+map_id_range_down_max(unsigned extents, struct uid_gid_map *map, u32 id, u32 count)
+{
+        struct idmap_key key;
+
+        key.map_up = false;
+        key.count = count;
+        key.id = id;
+
+        return bsearch(&key, map->forward, extents,
+                       sizeof(struct uid_gid_extent), cmp_map_id);
+}
+
+/**
+ * map_id_range_down_base - Find idmap via binary search in static extent array.
+ * Can only be called if number of mappings is equal or less than
+ * UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static struct uid_gid_extent *
+map_id_range_down_base(unsigned extents, struct uid_gid_map *map, u32 id, u32 count)
+{
+        unsigned idx;
         u32 first, last, id2;
 
         id2 = id + count - 1;
 
         /* Find the matching extent */
-        extents = map->nr_extents;
-        smp_rmb();
         for (idx = 0; idx < extents; idx++) {
                 first = map->extent[idx].first;
                 last = first + map->extent[idx].count - 1;
                 if (id >= first && id <= last &&
                     (id2 >= first && id2 <= last))
-                        break;
+                        return &map->extent[idx];
         }
+        return NULL;
+}
+
+static u32 map_id_range_down(struct uid_gid_map *map, u32 id, u32 count)
+{
+        struct uid_gid_extent *extent;
+        unsigned extents = map->nr_extents;
+        smp_rmb();
+
+        if (extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                extent = map_id_range_down_base(extents, map, id, count);
+        else
+                extent = map_id_range_down_max(extents, map, id, count);
+
         /* Map the id or note failure */
-        if (idx < extents)
-                id = (id - first) + map->extent[idx].lower_first;
+        if (extent)
+                id = (id - extent->first) + extent->lower_first;
         else
                 id = (u32) -1;
 
@@ -226,44 +315,61 @@ static u32 map_id_range_down(struct uid_gid_map *map, u32 id, u32 count)
 
 static u32 map_id_down(struct uid_gid_map *map, u32 id)
 {
-        unsigned idx, extents;
+        return map_id_range_down(map, id, 1);
+}
+
+/**
+ * map_id_up_base - Find idmap via binary search in static extent array.
+ * Can only be called if number of mappings is equal or less than
+ * UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static struct uid_gid_extent *
+map_id_up_base(unsigned extents, struct uid_gid_map *map, u32 id)
+{
+        unsigned idx;
         u32 first, last;
 
         /* Find the matching extent */
-        extents = map->nr_extents;
-        smp_rmb();
         for (idx = 0; idx < extents; idx++) {
-                first = map->extent[idx].first;
+                first = map->extent[idx].lower_first;
                 last = first + map->extent[idx].count - 1;
                 if (id >= first && id <= last)
-                        break;
+                        return &map->extent[idx];
         }
-        /* Map the id or note failure */
-        if (idx < extents)
-                id = (id - first) + map->extent[idx].lower_first;
-        else
-                id = (u32) -1;
+        return NULL;
+}
 
-        return id;
+/**
+ * map_id_up_max - Find idmap via binary search in ordered idmap array.
+ * Can only be called if number of mappings exceeds UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static struct uid_gid_extent *
+map_id_up_max(unsigned extents, struct uid_gid_map *map, u32 id)
+{
+        struct idmap_key key;
+
+        key.map_up = true;
+        key.count = 1;
+        key.id = id;
+
+        return bsearch(&key, map->reverse, extents,
+                       sizeof(struct uid_gid_extent), cmp_map_id);
 }
 
 static u32 map_id_up(struct uid_gid_map *map, u32 id)
 {
-        unsigned idx, extents;
-        u32 first, last;
-
-        /* Find the matching extent */
-        extents = map->nr_extents;
+        struct uid_gid_extent *extent;
+        unsigned extents = map->nr_extents;
         smp_rmb();
-        for (idx = 0; idx < extents; idx++) {
-                first = map->extent[idx].lower_first;
-                last = first + map->extent[idx].count - 1;
-                if (id >= first && id <= last)
-                        break;
-        }
+
+        if (extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                extent = map_id_up_base(extents, map, id);
+        else
+                extent = map_id_up_max(extents, map, id);
+
         /* Map the id or note failure */
-        if (idx < extents)
-                id = (id - first) + map->extent[idx].first;
+        if (extent)
+                id = (id - extent->lower_first) + extent->first;
         else
                 id = (u32) -1;
 
@@ -540,13 +646,17 @@ static int projid_m_show(struct seq_file *seq, void *v)
 static void *m_start(struct seq_file *seq, loff_t *ppos,
                      struct uid_gid_map *map)
 {
-        struct uid_gid_extent *extent = NULL;
         loff_t pos = *ppos;
+        unsigned extents = map->nr_extents;
+        smp_rmb();
 
-        if (pos < map->nr_extents)
-                extent = &map->extent[pos];
+        if (pos >= extents)
+                return NULL;
 
-        return extent;
+        if (extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                return &map->extent[pos];
+
+        return &map->forward[pos];
 }
 
 static void *uid_m_start(struct seq_file *seq, loff_t *ppos)
@@ -618,7 +728,10 @@ static bool mappings_overlap(struct uid_gid_map *new_map,
                 u32 prev_upper_last, prev_lower_last;
                 struct uid_gid_extent *prev;
 
-                prev = &new_map->extent[idx];
+                if (new_map->nr_extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                        prev = &new_map->extent[idx];
+                else
+                        prev = &new_map->forward[idx];
 
                 prev_upper_first = prev->first;
                 prev_lower_first = prev->lower_first;
@@ -638,6 +751,101 @@ static bool mappings_overlap(struct uid_gid_map *new_map,
         return false;
 }
 
+/**
+ * insert_extent - Safely insert a new idmap extent into struct uid_gid_map.
+ * Takes care to allocate a 4K block of memory if the number of mappings exceeds
+ * UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static int insert_extent(struct uid_gid_map *map, struct uid_gid_extent *extent)
+{
+        struct uid_gid_extent *dest;
+
+        if (map->nr_extents == UID_GID_MAP_MAX_BASE_EXTENTS) {
+                struct uid_gid_extent *forward;
+
+                /* Allocate memory for 340 mappings. */
+                forward = kmalloc(sizeof(struct uid_gid_extent) *
+                                 UID_GID_MAP_MAX_EXTENTS, GFP_KERNEL);
+                if (!forward)
+                        return -ENOMEM;
+
+                /* Copy over memory. Only set up memory for the forward pointer.
+                 * Defer the memory setup for the reverse pointer.
+                 */
+                memcpy(forward, map->extent,
+                       map->nr_extents * sizeof(map->extent[0]));
+
+                map->forward = forward;
+                map->reverse = NULL;
+        }
+
+        if (map->nr_extents < UID_GID_MAP_MAX_BASE_EXTENTS)
+                dest = &map->extent[map->nr_extents];
+        else
+                dest = &map->forward[map->nr_extents];
+
+        *dest = *extent;
+        map->nr_extents++;
+        return 0;
+}
+
+/* cmp function to sort() forward mappings */
+static int cmp_extents_forward(const void *a, const void *b)
+{
+        const struct uid_gid_extent *e1 = a;
+        const struct uid_gid_extent *e2 = b;
+
+        if (e1->first < e2->first)
+                return -1;
+
+        if (e1->first > e2->first)
+                return 1;
+
+        return 0;
+}
+
+/* cmp function to sort() reverse mappings */
+static int cmp_extents_reverse(const void *a, const void *b)
+{
+        const struct uid_gid_extent *e1 = a;
+        const struct uid_gid_extent *e2 = b;
+
+        if (e1->lower_first < e2->lower_first)
+                return -1;
+
+        if (e1->lower_first > e2->lower_first)
+                return 1;
+
+        return 0;
+}
+
+/**
+ * sort_idmaps - Sorts an array of idmap entries.
+ * Can only be called if number of mappings exceeds UID_GID_MAP_MAX_BASE_EXTENTS.
+ */
+static int sort_idmaps(struct uid_gid_map *map)
+{
+        if (map->nr_extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                return 0;
+
+        /* Sort forward array. */
+        sort(map->forward, map->nr_extents, sizeof(struct uid_gid_extent),
+             cmp_extents_forward, NULL);
+
+        /* Only copy the memory from forward we actually need. */
+        map->reverse = kmemdup(map->forward,
+                               map->nr_extents * sizeof(struct uid_gid_extent),
+                               GFP_KERNEL);
+        if (!map->reverse)
+                return -ENOMEM;
+
+        /* Sort reverse array. */
+        sort(map->reverse, map->nr_extents, sizeof(struct uid_gid_extent),
+             cmp_extents_reverse, NULL);
+
+        return 0;
+}
+
 static ssize_t map_write(struct file *file, const char __user *buf,
                          size_t count, loff_t *ppos,
                          int cap_setid,
@@ -648,7 +856,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
         struct user_namespace *ns = seq->private;
         struct uid_gid_map new_map;
         unsigned idx;
-        struct uid_gid_extent *extent = NULL;
+        struct uid_gid_extent extent;
         char *kbuf = NULL, *pos, *next_line;
         ssize_t ret = -EINVAL;
 
@@ -673,6 +881,8 @@ static ssize_t map_write(struct file *file, const char __user *buf,
          */
         mutex_lock(&userns_state_mutex);
 
+        memset(&new_map, 0, sizeof(struct uid_gid_map));
+
         ret = -EPERM;
         /* Only allow one successful write to the map */
         if (map->nr_extents != 0)
@@ -700,9 +910,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
         /* Parse the user data */
         ret = -EINVAL;
         pos = kbuf;
-        new_map.nr_extents = 0;
         for (; pos; pos = next_line) {
-                extent = &new_map.extent[new_map.nr_extents];
 
                 /* Find the end of line and ensure I don't look past it */
                 next_line = strchr(pos, '\n');
@@ -714,17 +922,17 @@ static ssize_t map_write(struct file *file, const char __user *buf,
                 }
 
                 pos = skip_spaces(pos);
-                extent->first = simple_strtoul(pos, &pos, 10);
+                extent.first = simple_strtoul(pos, &pos, 10);
                 if (!isspace(*pos))
                         goto out;
 
                 pos = skip_spaces(pos);
-                extent->lower_first = simple_strtoul(pos, &pos, 10);
+                extent.lower_first = simple_strtoul(pos, &pos, 10);
                 if (!isspace(*pos))
                         goto out;
 
                 pos = skip_spaces(pos);
-                extent->count = simple_strtoul(pos, &pos, 10);
+                extent.count = simple_strtoul(pos, &pos, 10);
                 if (*pos && !isspace(*pos))
                         goto out;
 
@@ -734,29 +942,31 @@ static ssize_t map_write(struct file *file, const char __user *buf,
                         goto out;
 
                 /* Verify we have been given valid starting values */
-                if ((extent->first == (u32) -1) ||
-                    (extent->lower_first == (u32) -1))
+                if ((extent.first == (u32) -1) ||
+                    (extent.lower_first == (u32) -1))
                         goto out;
 
                 /* Verify count is not zero and does not cause the
                  * extent to wrap
                  */
-                if ((extent->first + extent->count) <= extent->first)
+                if ((extent.first + extent.count) <= extent.first)
                         goto out;
-                if ((extent->lower_first + extent->count) <=
-                     extent->lower_first)
+                if ((extent.lower_first + extent.count) <=
+                     extent.lower_first)
                         goto out;
 
                 /* Do the ranges in extent overlap any previous extents? */
-                if (mappings_overlap(&new_map, extent))
+                if (mappings_overlap(&new_map, &extent))
                         goto out;
 
-                new_map.nr_extents++;
-
-                /* Fail if the file contains too many extents */
-                if ((new_map.nr_extents == UID_GID_MAP_MAX_EXTENTS) &&
+                if ((new_map.nr_extents + 1) == UID_GID_MAP_MAX_EXTENTS &&
                     (next_line != NULL))
                         goto out;
+
+                ret = insert_extent(&new_map, &extent);
+                if (ret < 0)
+                        goto out;
+                ret = -EINVAL;
         }
         /* Be very certaint the new map actually exists */
         if (new_map.nr_extents == 0)
@@ -767,16 +977,26 @@ static ssize_t map_write(struct file *file, const char __user *buf,
         if (!new_idmap_permitted(file, ns, cap_setid, &new_map))
                 goto out;
 
+        ret = sort_idmaps(&new_map);
+        if (ret < 0)
+                goto out;
+
+        ret = -EPERM;
         /* Map the lower ids from the parent user namespace to the
          * kernel global id space.
          */
         for (idx = 0; idx < new_map.nr_extents; idx++) {
+                struct uid_gid_extent *e;
                 u32 lower_first;
-                extent = &new_map.extent[idx];
+
+                if (new_map.nr_extents <= UID_GID_MAP_MAX_BASE_EXTENTS)
+                        e = &new_map.extent[idx];
+                else
+                        e = &new_map.forward[idx];
 
                 lower_first = map_id_range_down(parent_map,
-                                                extent->lower_first,
-                                                extent->count);
+                                                e->lower_first,
+                                                e->count);
 
                 /* Fail if we can not map the specified extent to
                  * the kernel global id space.
@@ -784,18 +1004,31 @@ static ssize_t map_write(struct file *file, const char __user *buf,
                 if (lower_first == (u32) -1)
                         goto out;
 
-                extent->lower_first = lower_first;
+                e->lower_first = lower_first;
         }
 
         /* Install the map */
-        memcpy(map->extent, new_map.extent,
-                new_map.nr_extents*sizeof(new_map.extent[0]));
+        if (new_map.nr_extents <= UID_GID_MAP_MAX_BASE_EXTENTS) {
+                memcpy(map->extent, new_map.extent,
+                       new_map.nr_extents * sizeof(new_map.extent[0]));
+        } else {
+                map->forward = new_map.forward;
+                map->reverse = new_map.reverse;
+        }
         smp_wmb();
         map->nr_extents = new_map.nr_extents;
 
         *ppos = count;
         ret = count;
 out:
+        if (ret < 0 && new_map.nr_extents > UID_GID_MAP_MAX_BASE_EXTENTS) {
+                kfree(new_map.forward);
+                kfree(new_map.reverse);
+                map->forward = NULL;
+                map->reverse = NULL;
+                map->nr_extents = 0;
+        }
+
         mutex_unlock(&userns_state_mutex);
         kfree(kbuf);
         return ret;