userns: improve uid/gid map collision detection

Initial implementation of the uid/gid maps will enforce that the maps should be in order and would prevent a use case like this from being used:

	0	1000	1
	48	500	1

since the second entry both values should be bigger than the previous. This patch implements a more elaborate collision detection allowing any order to be used.

Cc "Eric W. Biederman" <[email protected]>

Cc "Serge E. Hallyn" <[email protected]>

Signed-off-by Aristeu Rozanski <[email protected]>

kernel/user_namespace.c +23 -4

index 2b042c4..fb0e492 100644
@@ -521,6 +521,28 @@ struct seq_operations proc_projid_seq_operations = {
 
 static DEFINE_MUTEX(id_map_mutex);
 
+#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static inline int extent_collision(struct uid_gid_map *new_map,
+				   struct uid_gid_extent *extent)
+{
+	int i;
+	struct uid_gid_extent *cur;
+
+	for (i = 0; i < new_map->nr_extents; i++) {
+		cur = &new_map->extent[i];
+		if (in_range(extent->first, cur->first, cur->count) ||
+		    in_range(extent->first + extent->count, cur->first,
+			     cur->count))
+			return 1;
+		if (in_range(extent->lower_first, cur->lower_first,
+			     cur->count) ||
+		    in_range(extent->lower_first + extent->count,
+			     cur->lower_first, cur->count))
+			return 1;
+	}
+	return 0;
+}
+
 static ssize_t map_write(struct file *file, const char __user *buf,
 			 size_t count, loff_t *ppos,
 			 int cap_setid,

@@ -634,10 +656,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
 		if ((extent->lower_first + extent->count) <= extent->lower_first)
 			goto out;
 
-		/* For now only accept extents that are strictly in order */
-		if (last &&
-		    (((last->first + last->count) > extent->first) ||
-		     ((last->lower_first + last->count) > extent->lower_first)))
+		if (extent_collision(&new_map, extent))
 			goto out;
 
 		new_map.nr_extents++;

userns: improve uid/gid map collision detection

Initial implementation of the uid/gid maps (/proc/<pid>/{u,g}id_map) will enforce that the UID and GID maps be written in strict order as a simple way to check for range collision:

	local id	mapped to	count/range
	0		1000		50
	(ids 0-50 get mapped to 1000-1050)
	100		2120		10
	500		5000		200

so for each new entry, local id must be bigger than last local id (plus count) and the ids it maps to also needs to be bigger than the last entry (plus count).

This makes impossible to have a use case like this:

	local id	mapped to	count/range
	0		1000		1
	48		500		20

because while 48+20 > 0+1, 500+20 < 1000+1.

This patch implements a more elaborate collision detection allowing any order to be used.

v2: improved the patch description as requested by Andrew

btw, what the heck is up with CONFIG_UIDGID_CONVERTED? That thing prevents userns from being compiled in an allmodconfig build, which is rather undesirable. Isn't there a better, more user-friendly way of doing this?

eek, a macro! Macros are always bad.

This one is bad because

a) it's a macro

b) it evaluates its args multiple times and hence will cause nasty bugs if called with expressions-with-side-effects.

c) it evaluates its args multiple times and if called with non-trivial expressions the compiler might not be able to CSE those expressions, leading to code bloat.

Add lo, this patch:

kernel/user_namespace.c renamed from kernel/user_namespace.c~userns-improve-uid-gid-map-collision-detection-fix +5 -1

@@ -521,7 +521,11 @@ struct seq_operations proc_projid_seq_op
 
 static DEFINE_MUTEX(id_map_mutex);
 
-#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static bool in_range(u32 b, u32 first, u32 len)
+{
+	return b >= first && b < first + len;
+}
+
 static inline int extent_collision(struct uid_gid_map *new_map,
 				   struct uid_gid_extent *extent)
 {

reduces the user_namespace.o text from 4822 bytes to 4727 with gcc-4.4.4. This is a remarkably large difference.

Quoted 31 lines · Andrew Morton

eek, a macro! Macros are always bad.

This one is bad because

a) it's a macro

b) it evaluates its args multiple times and hence will cause nasty bugs if called with expressions-with-side-effects.

c) it evaluates its args multiple times and if called with non-trivial expressions the compiler might not be able to CSE those expressions, leading to code bloat.

Add lo, this patch:

kernel/user_namespace.c renamed from kernel/user_namespace.c~userns-improve-uid-gid-map-collision-detection-fix +5 -1

@@ -521,7 +521,11 @@ struct seq_operations proc_projid_seq_op
 
 static DEFINE_MUTEX(id_map_mutex);
 
-#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static bool in_range(u32 b, u32 first, u32 len)
+{
+	return b >= first && b < first + len;
+}
+
 static inline int extent_collision(struct uid_gid_map *new_map,
 				   struct uid_gid_extent *extent)
 {

Quoted 2 lines

reduces the user_namespace.o text from 4822 bytes to 4727 with gcc-4.4.4. This is a remarkably large difference.

thanks Andrew

(I see Eric already answered about the config option)

Aritsteu after looking at both my version and yours I am going with

mine. While my code is a little wordier I have half the number of comparisons your code does, and I took the time to kill the variable introducing a function to test for range collisions makes unnecessary. On Andrews size metric my version seems noticably smaller as well.

size $PWD-build/kernel/user_namespace.o
text data bss dec hex filename
4376 144 0 4520 11a8 /home/eric/projects/linux/linux-userns-devel-build/kernel/user_namespace.o

Short of something unexpected I plan to push all my code to linux-next sometime tomorrow.