[patch 0/4] kernel generic object IDs series

[patch 0/4] kernel generic object IDs series

[Cyrill Gorcunov]

Hi,

when we do the checkpoint-restore we need to find out if various kernel objects
(like mm_struct-s of file_struct-s) are shared between tasks (and restore them
after).

While at restore time we can use CLONE_XXX flags and unshare syscall there is
no way to find out sharing structures at checkpoint time. Thus, to chop the
knit, we introduce generic-object-ids helpers which do basically encode
kernel pointers into some form (at moment is's simple XOR operation over
a random cookie value) and provide them back to userspace. So one can test
if two resource are shared between different task.

Since such information is pretty valuable -- it's allowed for CAP_SYS_ADMIN
only since xor encoded values has nothing to do with security but used only
to break an impression that ID means something other than random "number"
which should be used for "sameness" test only and nothing else.

The following objects are shown at the moment

 - all namespaces living in /proc/pid/ns/
 - open files (shown in /proc/pid/fdinfo/)
 - objects, that can be shared with CLONE_XXX flags (except for namespaces)

Any kind of comments and especially complains (!) are very appreciated!

Cyrill

[patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

[-- Attachment #1: 1-introduce-gen_obj_id --]
[-- Type: text/plain, Size: 4078 bytes --]

The routine XORs the given pointer with a random value
producing an ID (32 or 64 bit, depending on the arch).

Since it's a valuable information -- only CAP_SYS_ADMIN
is allowed to obtain it.

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 include/linux/mm.h |   10 ++++++++++
 mm/Kconfig         |   16 ++++++++++++++++
 mm/util.c          |   49 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 75 insertions(+)

Index: linux-2.6.git/include/linux/mm.h
===================================================================
--- linux-2.6.git.orig/include/linux/mm.h
+++ linux-2.6.git/include/linux/mm.h
@@ -1640,5 +1640,15 @@ extern void copy_user_huge_page(struct p
 				unsigned int pages_per_huge_page);
 #endif /* CONFIG_TRANSPARENT_HUGEPAGE || CONFIG_HUGETLBFS */
 
+enum {
+	GEN_OBJ_ID_TYPES,
+};
+
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+unsigned long gen_obj_id(void *ptr, int type);
+#else
+static inline unsigned long gen_obj_id(void *ptr, int type) { return 0; }
+#endif
+
 #endif /* __KERNEL__ */
 #endif /* _LINUX_MM_H */
Index: linux-2.6.git/mm/Kconfig
===================================================================
--- linux-2.6.git.orig/mm/Kconfig
+++ linux-2.6.git/mm/Kconfig
@@ -373,3 +373,19 @@ config CLEANCACHE
 	  in a negligible performance hit.
 
 	  If unsure, say Y to enable cleancache
+
+config GENERIC_OBJECT_IDS
+	bool "Enable generic object ids infrastructure"
+	depends on CHECKPOINT_RESTORE
+	default n
+	help
+	  Turn on the functionality that can generate IDs for kernel
+	  objects, which are exported to userspace via /proc filesystem.
+
+	  It is useful if you need to examinate kernel objects and test
+	  if they are shared between several tasks. These IDs should never
+	  be used for anything but the "sameness" test. Besides, the IDs are
+	  dynamic and valid only while object is alive, once it get freed or
+	  kernel is rebooted -- the IDs will be changed.
+
+	  If unsure, say N here.
Index: linux-2.6.git/mm/util.c
===================================================================
--- linux-2.6.git.orig/mm/util.c
+++ linux-2.6.git/mm/util.c
@@ -4,6 +4,8 @@
 #include <linux/export.h>
 #include <linux/err.h>
 #include <linux/sched.h>
+#include <linux/random.h>
+#include <linux/capability.h>
 #include <asm/uaccess.h>
 
 #include "internal.h"
@@ -307,3 +309,50 @@ EXPORT_TRACEPOINT_SYMBOL(kmalloc_node);
 EXPORT_TRACEPOINT_SYMBOL(kmem_cache_alloc_node);
 EXPORT_TRACEPOINT_SYMBOL(kfree);
 EXPORT_TRACEPOINT_SYMBOL(kmem_cache_free);
+
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+static unsigned long gen_obj_cookie[GEN_OBJ_ID_TYPES] __read_mostly;
+
+unsigned long gen_obj_id(void *ptr, int type)
+{
+	if (!capable(CAP_SYS_ADMIN) || !ptr)
+		return 0;
+
+	BUG_ON(type >= GEN_OBJ_ID_TYPES);
+
+	/*
+	 * Note the simple XOR is used here not in a sake
+	 * of security by any means, but rather to break
+	 * an "impression" that such IDs means something
+	 * other than a number which can be used for comparison
+	 * with another number generated by this helper only.
+	 */
+	return ((unsigned long)ptr) ^ gen_obj_cookie[type];
+}
+
+static __init int gen_obj_cookie_init(void)
+{
+#if BITS_PER_LONG == 64
+	const unsigned long emergency_cookie = 0xefcdab8967452301;
+#else
+	const unsigned long emergency_cookie = 0x98badcf9;
+#endif
+	int i;
+
+	for (i = 0; i < GEN_OBJ_ID_TYPES; i++) {
+		get_random_bytes(&gen_obj_cookie[i],
+				 sizeof(unsigned long));
+		/*
+		 * In 'impossible' case of random-bytes = 0
+		 * we still would have non-zero value.
+		 */
+		gen_obj_cookie[i] =
+			(gen_obj_cookie[i] & __PAGE_OFFSET) +
+			(emergency_cookie & ~__PAGE_OFFSET);
+	}
+
+	return 0;
+}
+
+late_initcall(gen_obj_cookie_init);
+#endif

[patch 2/4] proc: Show namespaces IDs in /proc/pid/ns/* files

[Cyrill Gorcunov]

[-- Attachment #1: 2-objids-namespaces --]
[-- Type: text/plain, Size: 3835 bytes --]

This patch adds proc_ns_read method which provides
IDs for /proc/pid/ns/* files.

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 Documentation/filesystems/proc.txt |   24 ++++++++++++++++++++++++
 fs/proc/namespaces.c               |   21 +++++++++++++++++++++
 include/linux/mm.h                 |    1 +
 3 files changed, 46 insertions(+)

Index: linux-2.6.git/Documentation/filesystems/proc.txt
===================================================================
--- linux-2.6.git.orig/Documentation/filesystems/proc.txt
+++ linux-2.6.git/Documentation/filesystems/proc.txt
@@ -40,6 +40,7 @@ Table of Contents
   3.4	/proc/<pid>/coredump_filter - Core dump filtering settings
   3.5	/proc/<pid>/mountinfo - Information about mounts
   3.6	/proc/<pid>/comm  & /proc/<pid>/task/<tid>/comm
+  3.7	/proc/<pid>/ns - Information about namespaces
 
 
 ------------------------------------------------------------------------------
@@ -1545,3 +1546,26 @@ a task to set its own or one of its thre
 is limited in size compared to the cmdline value, so writing anything longer
 then the kernel's TASK_COMM_LEN (currently 16 chars) will result in a truncated
 comm value.
+
+3.7	/proc/<pid>/ns - Information about namespaces
+-----------------------------------------------------
+
+This directory consists of the following files "net", "uts", "ipc",
+and depend if appropriate CONFIG_ entry is set, i.e. it's possible
+to have only one, two or all three files here.
+
+Currently file contents provides that named "object id" number, which
+is a number useful for the one purpose only -- to test if two differen
+<pid> share the namespace.
+
+A typical format is
+
+id:	445332486300860161
+
+i.e. "id" followed by a number. One should never assume the number
+means something, it is only useful for "sameness" test with another number
+obtained from another <pid>.
+
+Moreover, a safe approach is to remember it as a string, since format may
+change in future and id would be not a long integer value, but something
+else, say SHA1/2 or even uuid encoded stream.
Index: linux-2.6.git/fs/proc/namespaces.c
===================================================================
--- linux-2.6.git.orig/fs/proc/namespaces.c
+++ linux-2.6.git/fs/proc/namespaces.c
@@ -27,10 +27,31 @@ static const struct proc_ns_operations *
 #endif
 };
 
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+static ssize_t proc_ns_read(struct file *file, char __user *buf,
+				      size_t len, loff_t *ppos)
+{
+	struct proc_inode *ei = PROC_I(file->f_dentry->d_inode);
+	char tmp[32];
+
+	snprintf(tmp, sizeof(tmp), "id:\t%lu\n",
+		gen_obj_id(ei->ns, GEN_OBJ_ID_NS));
+	return simple_read_from_buffer(buf, len, ppos, tmp, strlen(tmp));
+}
+
+static const struct file_operations ns_file_operations = {
+	.llseek		= no_llseek,
+	.read		= proc_ns_read,
+};
+
+#else
+
 static const struct file_operations ns_file_operations = {
 	.llseek		= no_llseek,
 };
 
+#endif /* CONFIG_GENERIC_OBJECT_IDS */
+
 static struct dentry *proc_ns_instantiate(struct inode *dir,
 	struct dentry *dentry, struct task_struct *task, const void *ptr)
 {
Index: linux-2.6.git/include/linux/mm.h
===================================================================
--- linux-2.6.git.orig/include/linux/mm.h
+++ linux-2.6.git/include/linux/mm.h
@@ -1641,6 +1641,7 @@ extern void copy_user_huge_page(struct p
 #endif /* CONFIG_TRANSPARENT_HUGEPAGE || CONFIG_HUGETLBFS */
 
 enum {
+	GEN_OBJ_ID_NS,
 	GEN_OBJ_ID_TYPES,
 };
 

[patch 3/4] proc: Show open file ID in /proc/pid/fdinfo/*

[Cyrill Gorcunov]

[-- Attachment #1: 3-objid-fdinfo-2 --]
[-- Type: text/plain, Size: 2360 bytes --]

This patch adds "id" field in /proc/pid/fdinfo/<file>
output which represent generic ID for 'struct file'
being used by a task.

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 fs/proc/base.c     |   34 +++++++++++++++++++++++++++++-----
 include/linux/mm.h |    1 +
 2 files changed, 30 insertions(+), 5 deletions(-)

Index: linux-2.6.git/fs/proc/base.c
===================================================================
--- linux-2.6.git.orig/fs/proc/base.c
+++ linux-2.6.git/fs/proc/base.c
@@ -1888,8 +1888,36 @@ out:
 	return ~0U;
 }
 
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+
+#define PROC_FDINFO_MAX 128
+
+static void proc_fd_info_fill(char *info, struct file *file, unsigned int f_flags)
+{
+	snprintf(info, PROC_FDINFO_MAX,
+		"pos:\t%lli\n"
+		"flags:\t0%o\n"
+		"id:\t%lu\n",
+		(long long)file->f_pos,
+		f_flags,
+		gen_obj_id(file, GEN_OBJ_ID_FILE));
+}
+
+#else /* CONFIG_GENERIC_OBJECT_IDS */
+
 #define PROC_FDINFO_MAX 64
 
+static void proc_fd_info_fill(char *info, struct file *file, unsigned int f_flags)
+{
+	snprintf(info, PROC_FDINFO_MAX,
+		"pos:\t%lli\n"
+		"flags:\t0%o\n",
+		(long long)file->f_pos,
+		f_flags);
+}
+
+#endif
+
 static int proc_fd_info(struct inode *inode, struct path *path, char *info)
 {
 	struct task_struct *task = get_proc_task(inode);
@@ -1922,11 +1950,7 @@ static int proc_fd_info(struct inode *in
 				path_get(&file->f_path);
 			}
 			if (info)
-				snprintf(info, PROC_FDINFO_MAX,
-					 "pos:\t%lli\n"
-					 "flags:\t0%o\n",
-					 (long long) file->f_pos,
-					 f_flags);
+				proc_fd_info_fill(info, file, f_flags);
 			spin_unlock(&files->file_lock);
 			put_files_struct(files);
 			return 0;
Index: linux-2.6.git/include/linux/mm.h
===================================================================
--- linux-2.6.git.orig/include/linux/mm.h
+++ linux-2.6.git/include/linux/mm.h
@@ -1642,6 +1642,7 @@ extern void copy_user_huge_page(struct p
 
 enum {
 	GEN_OBJ_ID_NS,
+	GEN_OBJ_ID_FILE,
 	GEN_OBJ_ID_TYPES,
 };
 

Re: [patch 0/4] kernel generic object IDs series

[Cyrill Gorcunov]

On Thu, Dec 22, 2011 at 04:56:39PM +0400, Cyrill Gorcunov wrote:
...
> 
> Any kind of comments and especially complains (!) are very appreciated!
> 
> Cyrill
> 

Because of "CLONE_XXX" in subject, LKML dropped the fourth patch, so I
renamed it and put it here. Sorry for inconvenince.

	Cyrill
---
proc: Show IDs of objects cloned with CLONE_ in proc

An example of output is

	# cat /proc/2332/objects 
	VM        :445332486314238977
	FILES     :16574420397857109505
	FS        :7421276367695228033
	SIGHAND   :9517130248188834433
	IO        :9605099974489260945
	SYSVSEM   :0

each one represents an ID of appropriate resource used
by a task -- memory, signals, fs and etc.

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 Documentation/filesystems/proc.txt |   18 ++++++++++++++++++
 fs/proc/base.c                     |   29 +++++++++++++++++++++++++++++
 include/linux/mm.h                 |    6 ++++++
 3 files changed, 53 insertions(+)

Index: linux-2.6.git/Documentation/filesystems/proc.txt
===================================================================
--- linux-2.6.git.orig/Documentation/filesystems/proc.txt
+++ linux-2.6.git/Documentation/filesystems/proc.txt
@@ -41,6 +41,7 @@ Table of Contents
   3.5	/proc/<pid>/mountinfo - Information about mounts
   3.6	/proc/<pid>/comm  & /proc/<pid>/task/<tid>/comm
   3.7	/proc/<pid>/ns - Information about namespaces
+  3.8	/proc/<pid>/objects - Information about generic objects
 
 
 ------------------------------------------------------------------------------
@@ -1569,3 +1570,20 @@ obtained from another <pid>.
 Moreover, a safe approach is to remember it as a string, since format may
 change in future and id would be not a long integer value, but something
 else, say SHA1/2 or even uuid encoded stream.
+
+3.8	/proc/<pid>/objects - Information about generic objects
+---------------------------------------------------------------
+
+Similar to /proc/<pid>/ns this file provide generic object ids by
+the following format (better to illustrate with example)
+
+VM        :445332486300860161
+FILES     :16574420397866995457
+FS        :7421276367693613825
+SIGHAND   :9517130248196786369
+IO        :0
+SYSVSEM   :0
+
+The first column is an object name, the second -- object ID number.
+As being mentioned in 3.7 one should carry them as a string to be
+on a safe side.
Index: linux-2.6.git/fs/proc/base.c
===================================================================
--- linux-2.6.git.orig/fs/proc/base.c
+++ linux-2.6.git/fs/proc/base.c
@@ -312,6 +312,32 @@ out:
 	return res;
 }
 
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+static int proc_pid_objs(struct task_struct *task, char * buffer)
+{
+	int ret = 0;
+
+#define SHOW_PID_OBJ(__type, __field)					\
+	do {								\
+		ret += sprintf(buffer + ret, "%-10s:%lu\n",		\
+				#__type,				\
+				gen_obj_id(task->__field,		\
+					GEN_OBJ_ID_##__type));		\
+	} while (0)
+
+	SHOW_PID_OBJ(VM, mm);
+	SHOW_PID_OBJ(FILES, files);
+	SHOW_PID_OBJ(FS, fs);
+	SHOW_PID_OBJ(SIGHAND, sighand);
+	SHOW_PID_OBJ(IO, io_context);
+	SHOW_PID_OBJ(SYSVSEM, sysvsem.undo_list);
+
+#undef SHOW_PID_OBJ
+
+	return ret;
+}
+#endif
+
 static int proc_pid_auxv(struct task_struct *task, char *buffer)
 {
 	struct mm_struct *mm = mm_for_maps(task);
@@ -3172,6 +3198,9 @@ static const struct pid_entry tgid_base_
 	INF("syscall",    S_IRUGO, proc_pid_syscall),
 #endif
 	INF("cmdline",    S_IRUGO, proc_pid_cmdline),
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+	INF("objects",    S_IRUGO, proc_pid_objs),
+#endif
 	ONE("stat",       S_IRUGO, proc_tgid_stat),
 	ONE("statm",      S_IRUGO, proc_pid_statm),
 	REG("maps",       S_IRUGO, proc_maps_operations),
Index: linux-2.6.git/include/linux/mm.h
===================================================================
--- linux-2.6.git.orig/include/linux/mm.h
+++ linux-2.6.git/include/linux/mm.h
@@ -1643,6 +1643,12 @@ extern void copy_user_huge_page(struct p
 enum {
 	GEN_OBJ_ID_NS,
 	GEN_OBJ_ID_FILE,
+	GEN_OBJ_ID_VM,
+	GEN_OBJ_ID_FILES,
+	GEN_OBJ_ID_FS,
+	GEN_OBJ_ID_SIGHAND,
+	GEN_OBJ_ID_IO,
+	GEN_OBJ_ID_SYSVSEM,
 	GEN_OBJ_ID_TYPES,
 };
 

[patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

[-- Attachment #1: 1-introduce-gen_obj_id --]
[-- Type: text/plain, Size: 4618 bytes --]

The routine XORs the given pointer with a random value
producing an ID (32 or 64 bit, depending on the arch).

Since it's a valuable information -- only CAP_SYS_ADMIN
is allowed to obtain it.

 - Tejun worried about the single poison value was a weak side -
   leaking one makes all the IDs vulnerable. To address this
   several poison values - one per object type - are introduced.
   They are stored in a plain array.
 - Pekka proposed to initialized poison values in the late_initcall callback
 - ... and move the code to mm/util.c

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
---
 include/linux/gen_obj_id.h |   20 +++++++++++++++++
 mm/Kconfig                 |   16 ++++++++++++++
 mm/Makefile                |    1 
 mm/gen_obj_id.c            |   51 +++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 88 insertions(+)

Index: linux-2.6.git/include/linux/gen_obj_id.h
===================================================================
--- /dev/null
+++ linux-2.6.git/include/linux/gen_obj_id.h
@@ -0,0 +1,20 @@
+#ifndef _LINUX_GEN_OBJ_ID_H
+#define _LINUX_GEN_OBJ_ID_H
+
+#ifdef __KERNEL__
+
+enum {
+	GEN_OBJ_ID_TYPES,
+};
+
+#ifdef CONFIG_GENERIC_OBJECT_ID
+extern unsigned long gen_obj_id(void *ptr, int type);
+#else
+static inline unsigned long gen_obj_id(void *ptr, int type)
+{
+	return 0;
+}
+#endif
+
+#endif /* __KERNEL__ */
+#endif /* _LINUX_GEN_OBJ_ID_H */
Index: linux-2.6.git/mm/Kconfig
===================================================================
--- linux-2.6.git.orig/mm/Kconfig
+++ linux-2.6.git/mm/Kconfig
@@ -373,3 +373,19 @@ config CLEANCACHE
 	  in a negligible performance hit.
 
 	  If unsure, say Y to enable cleancache
+
+config GENERIC_OBJECT_ID
+	bool "Enable generic object ID infrastructure"
+	depends on CHECKPOINT_RESTORE
+	default n
+	help
+	  Turn on the functionality that can generate IDs for kernel
+	  objects, which are exported to userspace via /proc filesystem.
+
+	  It is useful if you need to examinate kernel objects and test
+	  if they are shared between several tasks. These IDs should never
+	  be used for anything but the "sameness" test. Besides, the IDs are
+	  dynamic and valid only while object is alive, once it get freed or
+	  kernel is rebooted -- the IDs will be changed.
+
+	  If unsure, say N here.
Index: linux-2.6.git/mm/Makefile
===================================================================
--- linux-2.6.git.orig/mm/Makefile
+++ linux-2.6.git/mm/Makefile
@@ -51,3 +51,4 @@ obj-$(CONFIG_HWPOISON_INJECT) += hwpoiso
 obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o
 obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o
 obj-$(CONFIG_CLEANCACHE) += cleancache.o
+obj-$(CONFIG_GENERIC_OBJECT_ID) += gen_obj_id.o
Index: linux-2.6.git/mm/gen_obj_id.c
===================================================================
--- /dev/null
+++ linux-2.6.git/mm/gen_obj_id.c
@@ -0,0 +1,51 @@
+#include <linux/kernel.h>
+#include <linux/capability.h>
+#include <linux/random.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/gen_obj_id.h>
+
+static unsigned long gen_obj_cookie[GEN_OBJ_ID_TYPES] __read_mostly;
+
+unsigned long gen_obj_id(void *ptr, int type)
+{
+	if (!capable(CAP_SYS_ADMIN) || !ptr)
+		return 0;
+
+	BUG_ON(type >= GEN_OBJ_ID_TYPES);
+
+	/*
+	 * Note the simple XOR is used here not in a sake
+	 * of security by any means, but rather to break
+	 * an "impression" that such IDs means something
+	 * other than a number which can be used for comparison
+	 * with another number generated by this helper only.
+	 */
+	return ((unsigned long)ptr) ^ gen_obj_cookie[type];
+}
+
+static __init int gen_obj_cookie_init(void)
+{
+#if BITS_PER_LONG == 64
+	const unsigned long emergency_cookie = 0xefcdab8967452301;
+#else
+	const unsigned long emergency_cookie = 0x98badcf9;
+#endif
+	int i;
+
+	for (i = 0; i < GEN_OBJ_ID_TYPES; i++) {
+		get_random_bytes(&gen_obj_cookie[i],
+				 sizeof(unsigned long));
+		/*
+		 * In 'impossible' case of random-bytes = 0
+		 * we still would have non-zero value.
+		 */
+		gen_obj_cookie[i] =
+			(gen_obj_cookie[i] & __PAGE_OFFSET) +
+			(emergency_cookie & ~__PAGE_OFFSET);
+	}
+
+	return 0;
+}
+
+late_initcall(gen_obj_cookie_init);

Re: [patch 0/4] kernel generic object IDs series

[Cyrill Gorcunov]

On Thu, Dec 22, 2011 at 4:56 PM, Cyrill Gorcunov <gorcunov@openvz.org> wrote:
> Hi,
>
> when we do the checkpoint-restore we need to find out if various kernel objects
> (like mm_struct-s of file_struct-s) are shared between tasks (and restore them
> after).
>
...

Ping, any opinions on the series?

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Andrew Morton]

On Fri, 23 Dec 2011 16:47:42 +0400
Cyrill Gorcunov <gorcunov@openvz.org> wrote:

> The routine XORs the given pointer with a random value
> producing an ID (32 or 64 bit, depending on the arch).
> 
> Since it's a valuable information -- only CAP_SYS_ADMIN
> is allowed to obtain it.
> 
>  - Tejun worried about the single poison value was a weak side -
>    leaking one makes all the IDs vulnerable. To address this
>    several poison values - one per object type - are introduced.
>    They are stored in a plain array.
>  - Pekka proposed to initialized poison values in the late_initcall callback
>  - ... and move the code to mm/util.c

I'm trying to remember what this is all about, and I don't want to have
to remember all the discussion from last time this came up!

Please, do cover all this in the changelogs: tell us what the code is
all for and try to capture the design decisions thus far.  It's a
useful reminder for current reviewers and is very valuable for new
reviewers.

The root-only restriction sounds like a pretty bad one.  I suspect it
really isn't that bad but again, the changelog should discuss the pros
and cons here.


A thought: if all we're trying to do here is to check for the sameness
of objects, can we push the comparison into the kernel so we don't have
this exporting-sensitive-info problem at all?  Just return a boolean to
userspace?

Something like

int sys_pid_fields_equal(pid_t pid1, pid_t pid2, enum pid_field field_id);

?

For /proc/pid/fdinfo/* userspace can open /proc/pid1/fdinfo/0 and
/proc/pid2/fdinfo/0 and call sys_are_these_files_the_same(fd1, fd2, ...).

Perhaps sys_pid_fields_equal() can use sys_are_these_files_the_same()
as well, if we can think up a way of passing it two fds to represent
the two pids.

Have a think about it ;)

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Andrew Morton]

On Fri, 23 Dec 2011 16:47:42 +0400
Cyrill Gorcunov <gorcunov@openvz.org> wrote:

> The routine XORs the given pointer with a random value
> producing an ID (32 or 64 bit, depending on the arch).
> 
> Since it's a valuable information -- only CAP_SYS_ADMIN
> is allowed to obtain it.
> 
>  - Tejun worried about the single poison value was a weak side -
>    leaking one makes all the IDs vulnerable. To address this
>    several poison values - one per object type - are introduced.
>    They are stored in a plain array.
>  - Pekka proposed to initialized poison values in the late_initcall callback
>  - ... and move the code to mm/util.c
>
> ...
>

The code in general looks simple and reasonable to me.  I'm too much of
a security weenie to pass judgement on the security aspects.

>
> ...
>
> --- linux-2.6.git.orig/mm/Kconfig
> +++ linux-2.6.git/mm/Kconfig
> @@ -373,3 +373,19 @@ config CLEANCACHE
>  	  in a negligible performance hit.
>  
>  	  If unsure, say Y to enable cleancache
> +
> +config GENERIC_OBJECT_ID
> +	bool "Enable generic object ID infrastructure"
> +	depends on CHECKPOINT_RESTORE

Is c/r useless without GENERIC_OBJECT_ID?  If so, perhaps a `select'
would be good here.

> +	default n
> +	help
> +	  Turn on the functionality that can generate IDs for kernel
> +	  objects, which are exported to userspace via /proc filesystem.
> +
> +	  It is useful if you need to examinate kernel objects and test
> +	  if they are shared between several tasks. These IDs should never
> +	  be used for anything but the "sameness" test. Besides, the IDs are
> +	  dynamic and valid only while object is alive, once it get freed or
> +	  kernel is rebooted -- the IDs will be changed.
> +
> +	  If unsure, say N here.
> Index: linux-2.6.git/mm/Makefile
> ===================================================================
> --- linux-2.6.git.orig/mm/Makefile
> +++ linux-2.6.git/mm/Makefile
> @@ -51,3 +51,4 @@ obj-$(CONFIG_HWPOISON_INJECT) += hwpoiso
>  obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o
>  obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o
>  obj-$(CONFIG_CLEANCACHE) += cleancache.o
> +obj-$(CONFIG_GENERIC_OBJECT_ID) += gen_obj_id.o
> Index: linux-2.6.git/mm/gen_obj_id.c
> ===================================================================
> --- /dev/null
> +++ linux-2.6.git/mm/gen_obj_id.c
> @@ -0,0 +1,51 @@
> +#include <linux/kernel.h>
> +#include <linux/capability.h>
> +#include <linux/random.h>
> +#include <linux/module.h>
> +#include <linux/init.h>
> +#include <linux/gen_obj_id.h>

Formally, we need more includes than this.  cache.h for __read_mostly,
bug.h for BUG(), maybe others.  Forgetting bug.h used to be (and maybe
still is) a popular way of breaking the build for alpha.

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 1009 bytes --]

On Fri, 23 Dec 2011 16:47:42 +0400, Cyrill Gorcunov said:
> The routine XORs the given pointer with a random value
> producing an ID (32 or 64 bit, depending on the arch).

> Index: linux-2.6.git/mm/Kconfig

> +config GENERIC_OBJECT_ID
> +	bool "Enable generic object ID infrastructure"
> +	depends on CHECKPOINT_RESTORE
> +	default n
> +	help
> +	  Turn on the functionality that can generate IDs for kernel

"Turn on functionality"

> +	  objects, which are exported to userspace via /proc filesystem.

Lose the ,

> +
> +	  It is useful if you need to examinate kernel objects and test

examine

> +	  if they are shared between several tasks. These IDs should never
> +	  be used for anything but the "sameness" test. Besides, the IDs are

s/Besides, the/The/

> +	  dynamic and valid only while object is alive, once it get freed or

s/alive, once/alive. Once/

> +	  kernel is rebooted -- the IDs will be changed.

s/ --/,/

Also, see Andrew's comments regarding a generic foo_fields_equal() in-kernel.

[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Andrew Morton]

On Tue, 27 Dec 2011 18:54:29 -0500
Valdis.Kletnieks@vt.edu wrote:

> > +config GENERIC_OBJECT_ID
> > +	bool "Enable generic object ID infrastructure"
> > +	depends on CHECKPOINT_RESTORE
> > +	default n
> > +	help
> > +	  Turn on the functionality that can generate IDs for kernel
> 
> "Turn on functionality"
> 
> > +	  objects, which are exported to userspace via /proc filesystem.
> 
> Lose the ,
> 
> > +
> > +	  It is useful if you need to examinate kernel objects and test
> 
> examine
> 
> > +	  if they are shared between several tasks. These IDs should never
> > +	  be used for anything but the "sameness" test. Besides, the IDs are
> 
> s/Besides, the/The/
> 
> > +	  dynamic and valid only while object is alive, once it get freed or
> 
> s/alive, once/alive. Once/
> 
> > +	  kernel is rebooted -- the IDs will be changed.
> 
> s/ --/,/

heh, I avoided mentioning these things because I usually rewrite the
user-facing text when merging patches from non-native English speakers.

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Randy Dunlap]

On 12/27/2011 03:33 PM, Andrew Morton wrote:
> On Fri, 23 Dec 2011 16:47:42 +0400
> Cyrill Gorcunov <gorcunov@openvz.org> wrote:
> 
>> The routine XORs the given pointer with a random value
>> producing an ID (32 or 64 bit, depending on the arch).
>>
>> Since it's a valuable information -- only CAP_SYS_ADMIN
>> is allowed to obtain it.
>>
>>  - Tejun worried about the single poison value was a weak side -
>>    leaking one makes all the IDs vulnerable. To address this
>>    several poison values - one per object type - are introduced.
>>    They are stored in a plain array.
>>  - Pekka proposed to initialized poison values in the late_initcall callback
>>  - ... and move the code to mm/util.c
>>
>> ...
>>
> 
> The code in general looks simple and reasonable to me.  I'm too much of
> a security weenie to pass judgement on the security aspects.
> 
>>
>> ...
>>
>> --- linux-2.6.git.orig/mm/Kconfig
>> +++ linux-2.6.git/mm/Kconfig
>> @@ -373,3 +373,19 @@ config CLEANCACHE
>>  	  in a negligible performance hit.
>>  
>>  	  If unsure, say Y to enable cleancache
>> +
>> +config GENERIC_OBJECT_ID
>> +	bool "Enable generic object ID infrastructure"
>> +	depends on CHECKPOINT_RESTORE
> 
> Is c/r useless without GENERIC_OBJECT_ID?  If so, perhaps a `select'
> would be good here.

Is GENERIC_OBJECT_ID useful elsewhere?  If so, then it shouldn't depend
on CHECKPOINT_RESTORE -- it should just live in lib/ instead of in mm/
and CHECKPOINT_RESTORE should select it.

>> +	default n
>> +	help
>> +	  Turn on the functionality that can generate IDs for kernel
>> +	  objects, which are exported to userspace via /proc filesystem.
>> +
>> +	  It is useful if you need to examinate kernel objects and test
>> +	  if they are shared between several tasks. These IDs should never
>> +	  be used for anything but the "sameness" test. Besides, the IDs are
>> +	  dynamic and valid only while object is alive, once it get freed or
>> +	  kernel is rebooted -- the IDs will be changed.
>> +
>> +	  If unsure, say N here.


-- 
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Tue, Dec 27, 2011 at 04:02:24PM -0800, Andrew Morton wrote:
...
> > 
> > > +	  kernel is rebooted -- the IDs will be changed.
> > 
> > s/ --/,/
> 
> heh, I avoided mentioning these things because I usually rewrite the
> user-facing text when merging patches from non-native English speakers.
> 

:) Thanks!

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Tue, Dec 27, 2011 at 04:48:17PM -0800, Randy Dunlap wrote:
...
> > 
> > Is c/r useless without GENERIC_OBJECT_ID?  If so, perhaps a `select'
> > would be good here.
> 
> Is GENERIC_OBJECT_ID useful elsewhere?  If so, then it shouldn't depend
> on CHECKPOINT_RESTORE -- it should just live in lib/ instead of in mm/
> and CHECKPOINT_RESTORE should select it.
> 

Well, at moment I simply don't know who else might need it. So I though
that if someone would need it we simply drop CHECKPOINT_RESTORE dep then.

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Tue, Dec 27, 2011 at 03:23:44PM -0800, Andrew Morton wrote:
> On Fri, 23 Dec 2011 16:47:42 +0400
> Cyrill Gorcunov <gorcunov@openvz.org> wrote:
> 
> > The routine XORs the given pointer with a random value
> > producing an ID (32 or 64 bit, depending on the arch).
> > 
> > Since it's a valuable information -- only CAP_SYS_ADMIN
> > is allowed to obtain it.
> > 
> >  - Tejun worried about the single poison value was a weak side -
> >    leaking one makes all the IDs vulnerable. To address this
> >    several poison values - one per object type - are introduced.
> >    They are stored in a plain array.
> >  - Pekka proposed to initialized poison values in the late_initcall callback
> >  - ... and move the code to mm/util.c
> 
> I'm trying to remember what this is all about, and I don't want to have
> to remember all the discussion from last time this came up!
> 
> Please, do cover all this in the changelogs: tell us what the code is
> all for and try to capture the design decisions thus far.  It's a
> useful reminder for current reviewers and is very valuable for new
> reviewers.
> 

Actually, not much was changed here, but indeed I've missed some changelong
snippets, sorry, will update next time. In short -- if to export these values
to unprivilege users we're to use strong encryption with some expansion of
the former pointers, and even more -- since kernel pointers do cover not
that big space (espec in case of x86-32) one could prehash all possible values
and if (for some reason) the cookie vector become known to an attacker, the
plain encryption would not work, but require some additional security
protection. Ie, none of scheme such as sha1(pointer ^ cookie) will be
enough.

So as a first step I thought root-only access should be better until more
clever scheme would be developed. Actually there is an option to simply
inject counters into kernel structures which we compare (ie vm, files and etc),
but it increase kernel memory consumption too much.

> The root-only restriction sounds like a pretty bad one.  I suspect it
> really isn't that bad but again, the changelog should discuss the pros
> and cons here.
> 
> A thought: if all we're trying to do here is to check for the sameness
> of objects, can we push the comparison into the kernel so we don't have
> this exporting-sensitive-info problem at all?  Just return a boolean to
> userspace?
> 
> Something like
> 
> int sys_pid_fields_equal(pid_t pid1, pid_t pid2, enum pid_field field_id);
> 
> ?
> 
> For /proc/pid/fdinfo/* userspace can open /proc/pid1/fdinfo/0 and
> /proc/pid2/fdinfo/0 and call sys_are_these_files_the_same(fd1, fd2, ...).
> 
> Perhaps sys_pid_fields_equal() can use sys_are_these_files_the_same()
> as well, if we can think up a way of passing it two fds to represent
> the two pids.
> 
> Have a think about it ;)
> 

Good idea! Maybe we could simply extend prctl then?
And thanks a lot for feedback, Andrew!

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Andrew Morton]

On Wed, 28 Dec 2011 11:42:14 +0400 Cyrill Gorcunov <gorcunov@gmail.com> wrote:

> Maybe we could simply extend prctl then?

I'd suggest a syscall.  prctl is a big crap bucket and this thing has
simple, well defined semantics.  syscalls are cheap.

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 01:42:50AM -0800, Andrew Morton wrote:
> On Wed, 28 Dec 2011 11:42:14 +0400 Cyrill Gorcunov <gorcunov@gmail.com> wrote:
> 
> > Maybe we could simply extend prctl then?
> 
> I'd suggest a syscall.  prctl is a big crap bucket and this thing has
> simple, well defined semantics.  syscalls are cheap.
> 

OK. I'll think about it. Thanks!

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Pavel Emelyanov]

> A thought: if all we're trying to do here is to check for the sameness
> of objects, can we push the comparison into the kernel so we don't have
> this exporting-sensitive-info problem at all?  Just return a boolean to
> userspace?
> 
> Something like
> 
> int sys_pid_fields_equal(pid_t pid1, pid_t pid2, enum pid_field field_id);
> 
> ?
> 
> For /proc/pid/fdinfo/* userspace can open /proc/pid1/fdinfo/0 and
> /proc/pid2/fdinfo/0 and call sys_are_these_files_the_same(fd1, fd2, ...).
> 
> Perhaps sys_pid_fields_equal() can use sys_are_these_files_the_same()
> as well, if we can think up a way of passing it two fds to represent
> the two pids.
> 
> Have a think about it ;)

With this the complexity of determining sharing for N files scattered across
several tasks would be N^2, since we'll have to compare each file to each file.

On the other hand having just N IDs at hands would allow us to use more efficient
algorithms resulting in e.g. N*log(N) complexity.

That said I'd really appreciate if we work out a solution with IDs.

Thanks,
Pavel

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 01:47:37PM +0400, Pavel Emelyanov wrote:
> > A thought: if all we're trying to do here is to check for the sameness
> > of objects, can we push the comparison into the kernel so we don't have
> > this exporting-sensitive-info problem at all?  Just return a boolean to
> > userspace?
> > 
> > Something like
> > 
> > int sys_pid_fields_equal(pid_t pid1, pid_t pid2, enum pid_field field_id);
> > 
> > ?
> > 
> > For /proc/pid/fdinfo/* userspace can open /proc/pid1/fdinfo/0 and
> > /proc/pid2/fdinfo/0 and call sys_are_these_files_the_same(fd1, fd2, ...).
> > 
> > Perhaps sys_pid_fields_equal() can use sys_are_these_files_the_same()
> > as well, if we can think up a way of passing it two fds to represent
> > the two pids.
> > 
> > Have a think about it ;)
> 
> With this the complexity of determining sharing for N files scattered across
> several tasks would be N^2, since we'll have to compare each file to each file.
> 

Sigh. Indeed, I somehow missed that we have to compare a bunch of descriptors.

> On the other hand having just N IDs at hands would allow us to use more efficient
> algorithms resulting in e.g. N*log(N) complexity.
> 
> That said I'd really appreciate if we work out a solution with IDs.
> 

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Tejun Heo]

Hello, Cyrill.

Just my 2 cents.

On Fri, Dec 23, 2011 at 04:47:42PM +0400, Cyrill Gorcunov wrote:
> +unsigned long gen_obj_id(void *ptr, int type)
> +{
> +	if (!capable(CAP_SYS_ADMIN) || !ptr)
> +		return 0;
> +
> +	BUG_ON(type >= GEN_OBJ_ID_TYPES);
> +
> +	/*
> +	 * Note the simple XOR is used here not in a sake
> +	 * of security by any means, but rather to break
> +	 * an "impression" that such IDs means something
> +	 * other than a number which can be used for comparison
> +	 * with another number generated by this helper only.
> +	 */
> +	return ((unsigned long)ptr) ^ gen_obj_cookie[type];
> +}

To me, XOR & CAP_SYS_ADMIN combination doesn't make much sense.  With
CAP_SYS_ADMIN, there's no reason for XOR - we can just export
pointers.  If we plan on removing CAP_SYS_ADMIN restriction down the
road, XOR doesn't help much.  It's too weak.  The XOR is unnecessary
with CAP_SYS_ADMIN and useless without it.  It seems pointless to me.
If we're going down this route, I think doing cryptographically safe
hash would be much better.

Thanks.

-- 
tejun

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 08:06:55AM -0800, Tejun Heo wrote:
> Hello, Cyrill.
> 
> Just my 2 cents.
> 
> On Fri, Dec 23, 2011 at 04:47:42PM +0400, Cyrill Gorcunov wrote:
> > +unsigned long gen_obj_id(void *ptr, int type)
> > +{
> > +	if (!capable(CAP_SYS_ADMIN) || !ptr)
> > +		return 0;
> > +
> > +	BUG_ON(type >= GEN_OBJ_ID_TYPES);
> > +
> > +	/*
> > +	 * Note the simple XOR is used here not in a sake
> > +	 * of security by any means, but rather to break
> > +	 * an "impression" that such IDs means something
> > +	 * other than a number which can be used for comparison
> > +	 * with another number generated by this helper only.
> > +	 */
> > +	return ((unsigned long)ptr) ^ gen_obj_cookie[type];
> > +}
> 
> To me, XOR & CAP_SYS_ADMIN combination doesn't make much sense.  With
> CAP_SYS_ADMIN, there's no reason for XOR - we can just export
> pointers.  If we plan on removing CAP_SYS_ADMIN restriction down the
> road, XOR doesn't help much.  It's too weak.  The XOR is unnecessary
> with CAP_SYS_ADMIN and useless without it.  It seems pointless to me.
> If we're going down this route, I think doing cryptographically safe
> hash would be much better.
> 

Hi Tejun, thanks for comment! Yes, XOR is useless here in security meaning,
but it simply breaks impression that these generating numbers "mean" somthing
(I remained them as Vasily asked).

I personally fine to simply leave plain pointers here and root-only access
since that is enough for us (and our tool will require root privileges
anyway :)

OTOH, we could add some sha2 here with pointer+cookie as an initial value but I fear
this will bring more code comlexity and computing sha2 hash is not that
fast operation, which should be taken into account (note on x86-32 since
pointers are 32bit values one could compute prehash for all space covered
and if an attacker will know somehow cookie value the hash will be easily
broken, not sure if it's really usefull for someone, since if you have root
access to the machine such IDs will be the last thing attacker should be
interested in :)

And it seems noone except us need this interface yet, so maybe sticking with
"pointer exported under root-only" would be enough?

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Tejun Heo]

Hello,

On Wed, Dec 28, 2011 at 08:18:09PM +0400, Cyrill Gorcunov wrote:
> Hi Tejun, thanks for comment! Yes, XOR is useless here in security meaning,
> but it simply breaks impression that these generating numbers "mean" somthing
> (I remained them as Vasily asked).

But that comes at the cost of creating the impression that the XOR
does something, which doesn't seem like a good situation.  e.g. Why do
we need per-domain XOR random keys for then?  That code now doesn't
mean anything.

> I personally fine to simply leave plain pointers here and root-only access
> since that is enough for us (and our tool will require root privileges
> anyway :)
> 
> OTOH, we could add some sha2 here with pointer+cookie as an initial value but I fear
> this will bring more code comlexity and computing sha2 hash is not that
> fast operation, which should be taken into account (note on x86-32 since
> pointers are 32bit values one could compute prehash for all space covered
> and if an attacker will know somehow cookie value the hash will be easily
> broken, not sure if it's really usefull for someone, since if you have root
> access to the machine such IDs will be the last thing attacker should be
> interested in :)

We have the whole crypto subsystem dealing with this.  It sure would
be more complex than ^ operator but it's not like you have to open
code the whole thing.  Is it really that complex to use?

> And it seems noone except us need this interface yet, so maybe sticking with
> "pointer exported under root-only" would be enough?

Maybe, dunno.  But even if it's gonna be raw pointer or XOR'd value
for now, I would suggest exporting it in the form which can be
replaced by proper hash in the future.  ie. Don't let userland assume
it's 32bit or 64bit value.

Thanks.

-- 
tejun

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 08:26:53AM -0800, Tejun Heo wrote:
> Hello,
> 
> On Wed, Dec 28, 2011 at 08:18:09PM +0400, Cyrill Gorcunov wrote:
> > Hi Tejun, thanks for comment! Yes, XOR is useless here in security meaning,
> > but it simply breaks impression that these generating numbers "mean" somthing
> > (I remained them as Vasily asked).
> 
> But that comes at the cost of creating the impression that the XOR
> does something, which doesn't seem like a good situation.  e.g. Why do
> we need per-domain XOR random keys for then?  That code now doesn't
> mean anything.
> 

Strictly speaking, yes, we don't need per-domain keys, one would be enough,
I left them here just to add some more entropy in IDs. And comment in code
and in proc.txt mention pretty clearly (I hope) that one should interpret
the IDs as a string of bytes rather than a number to be on a safe side since
one day the generating algorithm might be changed (I dont think there will be
a need, but still better to warn users and give them a safe way).

> > I personally fine to simply leave plain pointers here and root-only access
> > since that is enough for us (and our tool will require root privileges
> > anyway :)
> > 
> > OTOH, we could add some sha2 here with pointer+cookie as an initial value but I fear
> > this will bring more code comlexity and computing sha2 hash is not that
> > fast operation, which should be taken into account (note on x86-32 since
> > pointers are 32bit values one could compute prehash for all space covered
> > and if an attacker will know somehow cookie value the hash will be easily
> > broken, not sure if it's really usefull for someone, since if you have root
> > access to the machine such IDs will be the last thing attacker should be
> > interested in :)
> 
> We have the whole crypto subsystem dealing with this.  It sure would
> be more complex than ^ operator but it's not like you have to open
> code the whole thing.  Is it really that complex to use?

No, Tejun, the use of crypto engine is not hard but it means more memory
consumption (one need to carry resulting hashes and print them out into
/proc) and more cpu consuption while we really need some fast and cheap
solution. Unlike other usage of crypto engine (such as encoding for net
layer, iirc ipsec uses it) I'm not really convinced we should use that
heavy artillery here ;)

> 
> > And it seems noone except us need this interface yet, so maybe sticking with
> > "pointer exported under root-only" would be enough?
> 
> Maybe, dunno.  But even if it's gonna be raw pointer or XOR'd value
> for now, I would suggest exporting it in the form which can be
> replaced by proper hash in the future.  ie. Don't let userland assume
> it's 32bit or 64bit value.
> 

I see, I could use some other form of output, it's not a problem. The main
problem which interface community prefer, should I really switch to crypto
usage or we can leave with root-only+plain-pointer approach?

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Tejun Heo]

Hello,

On Wed, Dec 28, 2011 at 08:40:55PM +0400, Cyrill Gorcunov wrote:
> > We have the whole crypto subsystem dealing with this.  It sure would
> > be more complex than ^ operator but it's not like you have to open
> > code the whole thing.  Is it really that complex to use?
> 
> No, Tejun, the use of crypto engine is not hard but it means more memory
> consumption (one need to carry resulting hashes and print them out into
> /proc) and more cpu consuption while we really need some fast and cheap
> solution. Unlike other usage of crypto engine (such as encoding for net
> layer, iirc ipsec uses it) I'm not really convinced we should use that
> heavy artillery here ;)

But the cost would be attributed to the user requesting that specific
data and given the amount of data to be hashed, I don't think the
computational or memory overhead should be the deciding design factor
here.  There are far more grave issues here.  Userland visible API and
security.

> I see, I could use some other form of output, it's not a problem. The main
> problem which interface community prefer, should I really switch to crypto
> usage or we can leave with root-only+plain-pointer approach?

I don't know either but if proper hashing (crypto or not) is simple
enough, this really isn't a tradeoff we need to make, no?

Thanks.

-- 
tejun

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Alan Cox]

> +	  be used for anything but the "sameness" test. Besides, the IDs are
> +	  dynamic and valid only while object is alive, once it get freed or

Please explain your locking model which ensures a false sameness cannot
occur due to object reuse as you do the comparison and scan.

Alan

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 08:45:22AM -0800, Tejun Heo wrote:
> Hello,
> 
> On Wed, Dec 28, 2011 at 08:40:55PM +0400, Cyrill Gorcunov wrote:
> > > We have the whole crypto subsystem dealing with this.  It sure would
> > > be more complex than ^ operator but it's not like you have to open
> > > code the whole thing.  Is it really that complex to use?
> > 
> > No, Tejun, the use of crypto engine is not hard but it means more memory
> > consumption (one need to carry resulting hashes and print them out into
> > /proc) and more cpu consuption while we really need some fast and cheap
> > solution. Unlike other usage of crypto engine (such as encoding for net
> > layer, iirc ipsec uses it) I'm not really convinced we should use that
> > heavy artillery here ;)
> 
> But the cost would be attributed to the user requesting that specific
> data and given the amount of data to be hashed, I don't think the
> computational or memory overhead should be the deciding design factor
> here.  There are far more grave issues here.  Userland visible API and
> security.
>

Well, it is not deciding but it should be taken into account. One could
be reading this IDs again and again and again affecting performance of
the whole system, which means I really would prefer to limit access to such
features (ie root-only). If (as I said) for other cases there is simply no way to
_not_ use crypto, our case might be the one where using crypto is redundant.

> > I see, I could use some other form of output, it's not a problem. The main
> > problem which interface community prefer, should I really switch to crypto
> > usage or we can leave with root-only+plain-pointer approach?
> 
> I don't know either but if proper hashing (crypto or not) is simple
> enough, this really isn't a tradeoff we need to make, no?
> 

Hell knows, I would prefer to escape strong-crypto usage, but if there is
no other way, of course I'll change the approach ;)

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Tejun Heo]

Hello,

On Wed, Dec 28, 2011 at 08:53:36PM +0400, Cyrill Gorcunov wrote:
> Well, it is not deciding but it should be taken into account. One could
> be reading this IDs again and again and again affecting performance of
> the whole system,

I can't see how it would affect performance of the whole system.
Calculating hash doesn't involve any further locking or use of scarce
global resource.  It would add small amount memory and processing
overhead for the task reading the hash.  It sure is something to be
considered but I really don't think this should be a major factor
here.

> which means I really would prefer to limit access to such
> features (ie root-only). If (as I said) for other cases there is simply no way to
> _not_ use crypto, our case might be the one where using crypto is redundant.

Limiting it to root and just exporting printer (or maybe XOR with a
randomish value) may be good enough.  I don't know.  However, we no
longer consider exporting pointers to unpriviliedged userland safe and
this can be useful in many circumstances, so if it's not too
difficult, I think trying to use proper hash would be nide.

Thanks.

-- 
tejun

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 04:51:14PM +0000, Alan Cox wrote:
> > +	  be used for anything but the "sameness" test. Besides, the IDs are
> > +	  dynamic and valid only while object is alive, once it get freed or
> 
> Please explain your locking model which ensures a false sameness cannot
> occur due to object reuse as you do the comparison and scan.
> 

It can happen in case of object re-allocated from slab. But in case
of two living pids it's impossible to get same pointers for different
objects. Or I misunderstood the question, Alan? It's up to application
to not compare objects from dead tasks.

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 09:01:16AM -0800, Tejun Heo wrote:
> Hello,
> 
> On Wed, Dec 28, 2011 at 08:53:36PM +0400, Cyrill Gorcunov wrote:
> > Well, it is not deciding but it should be taken into account. One could
> > be reading this IDs again and again and again affecting performance of
> > the whole system,
> 
> I can't see how it would affect performance of the whole system.
> Calculating hash doesn't involve any further locking or use of scarce
> global resource.  It would add small amount memory and processing
> overhead for the task reading the hash.  It sure is something to be
> considered but I really don't think this should be a major factor
> here.
> 

Yeah, indeed.

> > which means I really would prefer to limit access to such
> > features (ie root-only). If (as I said) for other cases there is simply no way to
> > _not_ use crypto, our case might be the one where using crypto is redundant.
> 
> Limiting it to root and just exporting printer (or maybe XOR with a
> randomish value) may be good enough.  I don't know.  However, we no
> longer consider exporting pointers to unpriviliedged userland safe and
> this can be useful in many circumstances, so if it's not too
> difficult, I think trying to use proper hash would be nide.

OK, Tejun, I'll try, but no promises :) Thanks!

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Alan Cox]

> It can happen in case of object re-allocated from slab. But in case
> of two living pids it's impossible to get same pointers for different
> objects. Or I misunderstood the question, Alan? It's up to application
> to not compare objects from dead tasks.

How will it know the task has not died and been reallocated, or its
resources not been freed and reallocated during the comparison ?

Your comparison appears to have a zero time validity - you can ask "is A
the same as B" but by the time you get an answer your answer may no
longer be true. It also externalises a current implementation
detail in a very ugly way.

Would it also not be better to do the job right and simply have an
interface to ask "who shares with A" or even something a bit more high
level, it seems you are creating something nastier by trying to push all
this in userspace than if you did the job or part of it kernel side where
you had access to the right locking infrastructure and where the public
API doesn't need to expose innards of the kernel ?

Alan

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 05:21:51PM +0000, Alan Cox wrote:
> > It can happen in case of object re-allocated from slab. But in case
> > of two living pids it's impossible to get same pointers for different
> > objects. Or I misunderstood the question, Alan? It's up to application
> > to not compare objects from dead tasks.
> 
> How will it know the task has not died and been reallocated, or its
> resources not been freed and reallocated during the comparison ?
> 
> Your comparison appears to have a zero time validity - you can ask "is A
> the same as B" but by the time you get an answer your answer may no
> longer be true. It also externalises a current implementation
> detail in a very ugly way.
>

It's not differ from reading other data from /proc. How make you be sure
the PPid read from a task status is the same once you've finished reading
it? The same applies to say ps output, it's valid for almost zero time,
then one need to restart ps again to get new process tree snapshot. The
same here -- if I need a precise results I have to either stop tasks or
froze them and compare IDs. That's what I've had in mind.

> Would it also not be better to do the job right and simply have an
> interface to ask "who shares with A" or even something a bit more high
> level, it seems you are creating something nastier by trying to push all
> this in userspace than if you did the job or part of it kernel side where
> you had access to the right locking infrastructure and where the public
> API doesn't need to expose innards of the kernel ?
> 

Need to think, thanks a lot for idea, Alan!

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 09:35:02PM +0400, Cyrill Gorcunov wrote:
> On Wed, Dec 28, 2011 at 05:21:51PM +0000, Alan Cox wrote:
> > > It can happen in case of object re-allocated from slab. But in case
> > > of two living pids it's impossible to get same pointers for different
> > > objects. Or I misunderstood the question, Alan? It's up to application
> > > to not compare objects from dead tasks.
> > 
> > How will it know the task has not died and been reallocated, or its
> > resources not been freed and reallocated during the comparison ?
> > 
> > Your comparison appears to have a zero time validity - you can ask "is A
> > the same as B" but by the time you get an answer your answer may no
> > longer be true. It also externalises a current implementation
> > detail in a very ugly way.
> >
> 
> It's not differ from reading other data from /proc. How make you be sure
> the PPid read from a task status is the same once you've finished reading
> it? The same applies to say ps output, it's valid for almost zero time,
> then one need to restart ps again to get new process tree snapshot. The
> same here -- if I need a precise results I have to either stop tasks or
> froze them and compare IDs. That's what I've had in mind.
> 
> > Would it also not be better to do the job right and simply have an
> > interface to ask "who shares with A" or even something a bit more high
> > level, it seems you are creating something nastier by trying to push all
> > this in userspace than if you did the job or part of it kernel side where
> > you had access to the right locking infrastructure and where the public
> > API doesn't need to expose innards of the kernel ?
> > 
> 
> Need to think, thanks a lot for idea, Alan!
> 

You know, Alan, I thought about different ways... but eventually I think
having _this_ interface is better than anything else (of course along with
addressing problems Tejun mentioned). "Who shares with A" doesn't make
situation better, once I obtain the result it's not valid anymore and
I have to either do the same requests again and again, or stop/freeze
tasks before asking which resources they do share. The interface provided
now gives the *minimun* information user-space needed to draw the shared
resources affinity scheme, and I would like to escape putting more work
on kernel side if possible. Sounds reasonable?

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Wed, Dec 28, 2011 at 09:14:19PM +0400, Cyrill Gorcunov wrote:
> 
> Yeah, indeed.
> 
> > > which means I really would prefer to limit access to such
> > > features (ie root-only). If (as I said) for other cases there is simply no way to
> > > _not_ use crypto, our case might be the one where using crypto is redundant.
> > 
> > Limiting it to root and just exporting printer (or maybe XOR with a
> > randomish value) may be good enough.  I don't know.  However, we no
> > longer consider exporting pointers to unpriviliedged userland safe and
> > this can be useful in many circumstances, so if it's not too
> > difficult, I think trying to use proper hash would be nide.
> 
> OK, Tejun, I'll try, but no promises :) Thanks!
> 

Tejun, I've tried to use crypto engine here but it produced a warning
about being used in non-sleepable context (which takes place when we
read /proc/<pid>/fdinfo/* files). So I used lib/sha1.c instead. The
final result is below, please review.

The output as expected is sha1 hash but note I still placed root-only
access here since I prefer security guys to confirm if such production
is indeed safe to be exported for regular users.

| [root@localhost ~]# cat /proc/2/ns/net 
| id:	ebfc829fc16a466c9c02b031ceab65c277040c02

	Cyrill
---
From: Cyrill Gorcunov <gorcunov@openvz.org>
Subject: Add routine for generating an ID for kernel pointer v2

The routine XORs the given pointer with a random value,
expands the production to sha1 message block and compute
the sha1 hash producing an ID.

Util confirmed that the production is a safe one to be
exported for the unprivileged users CAP_SYS_ADMIN guird
is used.

Because the routine might be used in non-sleepable context
built-in realization of sha1 is chosen instead of crypto
manager and its helpers.

v1:
 - Tejun worried about the single poison value was a weak side -
   leaking one makes all the IDs vulnerable. To address this
   several poison values - one per object type - are introduced.
   They are stored in a plain array.
 - Pekka proposed to initialized poison values in the late_initcall callback
 - ... and move the code to mm/util.c, but eventually it's moved
   to an own file.

v2:
 - Tejun suggested to use crypto engine instead of plain XOR and
   provide hashes to unprivilege users as well.
 - A number of fixes for Kconfig prompt from Valdis
 - Andrew pointed more #incclude's are needed

Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
CC: Glauber Costa <glommer@parallels.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: Tejun Heo <tj@kernel.org>
CC: Matt Helsley <matthltc@us.ibm.com>
CC: Pekka Enberg <penberg@kernel.org>
CC: Eric Dumazet <eric.dumazet@gmail.com>
CC: Vasiliy Kulikov <segoon@openwall.com>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
CC: Valdis.Kletnieks@vt.edu
---
 include/linux/gen_obj_id.h |   26 ++++++++++++++
 mm/Kconfig                 |   18 ++++++++++
 mm/Makefile                |    1 
 mm/gen_obj_id.c            |   81 +++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 126 insertions(+)

Index: linux-2.6.git/include/linux/gen_obj_id.h
===================================================================
--- /dev/null
+++ linux-2.6.git/include/linux/gen_obj_id.h
@@ -0,0 +1,26 @@
+#ifndef _LINUX_GEN_OBJ_ID_H
+#define _LINUX_GEN_OBJ_ID_H
+
+#include <linux/cryptohash.h>
+#include <linux/err.h>
+
+#ifdef __KERNEL__
+
+enum {
+	GEN_OBJ_ID_TYPES,
+};
+
+#define GEN_OBJ_ID_DIGEST_SIZE	(SHA_DIGEST_WORDS * sizeof(__u32))
+#define GEN_OBJ_ID_BUF_SIZE	(GEN_OBJ_ID_DIGEST_SIZE * 2)
+
+#ifdef CONFIG_GENERIC_OBJECT_ID
+extern int gen_obj_id(void *ptr, int type, char *dst, unsigned long size);
+#else
+static inline int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
+{
+	return -EINVAL;
+}
+#endif
+
+#endif /* __KERNEL__ */
+#endif /* _LINUX_GEN_OBJ_ID_H */
Index: linux-2.6.git/mm/Kconfig
===================================================================
--- linux-2.6.git.orig/mm/Kconfig
+++ linux-2.6.git/mm/Kconfig
@@ -373,3 +373,21 @@ config CLEANCACHE
 	  in a negligible performance hit.
 
 	  If unsure, say Y to enable cleancache
+
+config GENERIC_OBJECT_ID
+	bool "Enable generic object ID infrastructure"
+	depends on CHECKPOINT_RESTORE
+	depends on CRYPTO_SHA1
+	default n
+	help
+	  Turn on functionality that can generate IDs for kernel
+	  objects, which are exported to the userspace via /proc
+	  filesystem.
+
+	  It is useful if you need to examine kernel objects and test
+	  if they are shared between several tasks. These IDs should never
+	  be used for anything but the "sameness" test. The IDs are dynamic
+	  and valid only while object is alive. Once it get freed or kernel
+	  is rebooted, the IDs will be changed.
+
+	  If unsure, say N here.
Index: linux-2.6.git/mm/Makefile
===================================================================
--- linux-2.6.git.orig/mm/Makefile
+++ linux-2.6.git/mm/Makefile
@@ -51,3 +51,4 @@ obj-$(CONFIG_HWPOISON_INJECT) += hwpoiso
 obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o
 obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o
 obj-$(CONFIG_CLEANCACHE) += cleancache.o
+obj-$(CONFIG_GENERIC_OBJECT_ID) += gen_obj_id.o
Index: linux-2.6.git/mm/gen_obj_id.c
===================================================================
--- /dev/null
+++ linux-2.6.git/mm/gen_obj_id.c
@@ -0,0 +1,81 @@
+#include <linux/kernel.h>
+#include <linux/capability.h>
+#include <linux/cryptohash.h>
+#include <linux/string.h>
+#include <linux/random.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/cache.h>
+#include <linux/bug.h>
+#include <linux/err.h>
+
+#include <linux/gen_obj_id.h>
+
+static unsigned long gen_obj_cookie[GEN_OBJ_ID_TYPES] __read_mostly;
+
+int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
+{
+	__u32 hash[SHA_DIGEST_WORDS];
+	__u32 workspace[SHA_WORKSPACE_WORDS];
+	__u8 extract[SHA_MESSAGE_BYTES];
+	__u8 *t = (__u8 *)hash;
+	unsigned long id;
+	int i;
+
+	BUG_ON(type >= GEN_OBJ_ID_TYPES);
+
+	if (!capable(CAP_SYS_ADMIN) ||
+	    size < GEN_OBJ_ID_BUF_SIZE) {
+		memset(dst, '0', size);
+		return -EINVAL;
+	}
+
+	id = ((unsigned long)ptr) ^ gen_obj_cookie[type];
+
+	BUILD_BUG_ON(SHA_MESSAGE_BYTES % sizeof(long));
+
+	/*
+	 * Expand the ID to the whole message block.
+	 */
+	for (i = 0; i < (SHA_MESSAGE_BYTES / sizeof(long)); i++)
+		((long *)extract)[i] = id;
+
+	sha_init(hash);
+	sha_transform(hash, extract, workspace);
+
+	snprintf(dst, size,
+		 "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x"
+		 "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
+		 t[ 0], t[ 1], t[ 2], t[ 3], t[ 4],
+		 t[ 5], t[ 6], t[ 7], t[ 8], t[ 9],
+		 t[10], t[11], t[12], t[13], t[14],
+		 t[15], t[16], t[17], t[18], t[19]);
+
+	return 0;
+}
+
+static __init int gen_obj_cookie_init(void)
+{
+#if BITS_PER_LONG == 64
+	const unsigned long emergency_cookie = 0xefcdab8967452301;
+#else
+	const unsigned long emergency_cookie = 0x98badcf9;
+#endif
+	int i;
+
+	for (i = 0; i < GEN_OBJ_ID_TYPES; i++) {
+		get_random_bytes(&gen_obj_cookie[i],
+				 sizeof(unsigned long));
+		/*
+		 * In 'impossible' case of random-bytes = 0
+		 * we still would have non-zero value.
+		 */
+		gen_obj_cookie[i] =
+			(gen_obj_cookie[i] & __PAGE_OFFSET) +
+			(emergency_cookie & ~__PAGE_OFFSET);
+	}
+
+	return 0;
+}
+
+late_initcall(gen_obj_cookie_init);

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Tejun Heo]

Hello,

On Thu, Dec 29, 2011 at 06:24:38PM +0400, Cyrill Gorcunov wrote:
> Tejun, I've tried to use crypto engine here but it produced a warning
> about being used in non-sleepable context (which takes place when we
> read /proc/<pid>/fdinfo/* files). So I used lib/sha1.c instead. The
> final result is below, please review.

I don't know anything about cryptography and have no idea whether sha1
is good enough, so I can't really say much. :)

Which part triggered the context warning?  IIRC, crypto context
preparation and actual calculation can be done in separate steps.
Can't the calculation part be done from non-sleepable context?

cc'ing Herbert & David and quoting the whole message.

Thanks.

> The output as expected is sha1 hash but note I still placed root-only
> access here since I prefer security guys to confirm if such production
> is indeed safe to be exported for regular users.
> 
> | [root@localhost ~]# cat /proc/2/ns/net 
> | id:	ebfc829fc16a466c9c02b031ceab65c277040c02
> 
> 	Cyrill
> ---
> From: Cyrill Gorcunov <gorcunov@openvz.org>
> Subject: Add routine for generating an ID for kernel pointer v2
> 
> The routine XORs the given pointer with a random value,
> expands the production to sha1 message block and compute
> the sha1 hash producing an ID.
> 
> Util confirmed that the production is a safe one to be
> exported for the unprivileged users CAP_SYS_ADMIN guird
> is used.
> 
> Because the routine might be used in non-sleepable context
> built-in realization of sha1 is chosen instead of crypto
> manager and its helpers.
> 
> v1:
>  - Tejun worried about the single poison value was a weak side -
>    leaking one makes all the IDs vulnerable. To address this
>    several poison values - one per object type - are introduced.
>    They are stored in a plain array.
>  - Pekka proposed to initialized poison values in the late_initcall callback
>  - ... and move the code to mm/util.c, but eventually it's moved
>    to an own file.
> 
> v2:
>  - Tejun suggested to use crypto engine instead of plain XOR and
>    provide hashes to unprivilege users as well.
>  - A number of fixes for Kconfig prompt from Valdis
>  - Andrew pointed more #incclude's are needed
> 
> Based-on-patch-from: Pavel Emelyanov <xemul@parallels.com>
> Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
> CC: Glauber Costa <glommer@parallels.com>
> CC: Andi Kleen <andi@firstfloor.org>
> CC: Tejun Heo <tj@kernel.org>
> CC: Matt Helsley <matthltc@us.ibm.com>
> CC: Pekka Enberg <penberg@kernel.org>
> CC: Eric Dumazet <eric.dumazet@gmail.com>
> CC: Vasiliy Kulikov <segoon@openwall.com>
> CC: Andrew Morton <akpm@linux-foundation.org>
> CC: Alexey Dobriyan <adobriyan@gmail.com>
> CC: Valdis.Kletnieks@vt.edu
> ---
>  include/linux/gen_obj_id.h |   26 ++++++++++++++
>  mm/Kconfig                 |   18 ++++++++++
>  mm/Makefile                |    1 
>  mm/gen_obj_id.c            |   81 +++++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 126 insertions(+)
> 
> Index: linux-2.6.git/include/linux/gen_obj_id.h
> ===================================================================
> --- /dev/null
> +++ linux-2.6.git/include/linux/gen_obj_id.h
> @@ -0,0 +1,26 @@
> +#ifndef _LINUX_GEN_OBJ_ID_H
> +#define _LINUX_GEN_OBJ_ID_H
> +
> +#include <linux/cryptohash.h>
> +#include <linux/err.h>
> +
> +#ifdef __KERNEL__
> +
> +enum {
> +	GEN_OBJ_ID_TYPES,
> +};
> +#define GEN_OBJ_ID_DIGEST_SIZE	(SHA_DIGEST_WORDS * sizeof(__u32))
> +#define GEN_OBJ_ID_BUF_SIZE	(GEN_OBJ_ID_DIGEST_SIZE * 2)
> +
> +#ifdef CONFIG_GENERIC_OBJECT_ID
> +extern int gen_obj_id(void *ptr, int type, char *dst, unsigned long size);
> +#else
> +static inline int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
> +{
> +	return -EINVAL;
> +}
> +#endif
> +
> +#endif /* __KERNEL__ */
> +#endif /* _LINUX_GEN_OBJ_ID_H */
> Index: linux-2.6.git/mm/Kconfig
> ===================================================================
> --- linux-2.6.git.orig/mm/Kconfig
> +++ linux-2.6.git/mm/Kconfig
> @@ -373,3 +373,21 @@ config CLEANCACHE
>  	  in a negligible performance hit.
>  
>  	  If unsure, say Y to enable cleancache
> +
> +config GENERIC_OBJECT_ID
> +	bool "Enable generic object ID infrastructure"
> +	depends on CHECKPOINT_RESTORE
> +	depends on CRYPTO_SHA1
> +	default n
> +	help
> +	  Turn on functionality that can generate IDs for kernel
> +	  objects, which are exported to the userspace via /proc
> +	  filesystem.
> +
> +	  It is useful if you need to examine kernel objects and test
> +	  if they are shared between several tasks. These IDs should never
> +	  be used for anything but the "sameness" test. The IDs are dynamic
> +	  and valid only while object is alive. Once it get freed or kernel
> +	  is rebooted, the IDs will be changed.
> +
> +	  If unsure, say N here.
> Index: linux-2.6.git/mm/Makefile
> ===================================================================
> --- linux-2.6.git.orig/mm/Makefile
> +++ linux-2.6.git/mm/Makefile
> @@ -51,3 +51,4 @@ obj-$(CONFIG_HWPOISON_INJECT) += hwpoiso
>  obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o
>  obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o
>  obj-$(CONFIG_CLEANCACHE) += cleancache.o
> +obj-$(CONFIG_GENERIC_OBJECT_ID) += gen_obj_id.o
> Index: linux-2.6.git/mm/gen_obj_id.c
> ===================================================================
> --- /dev/null
> +++ linux-2.6.git/mm/gen_obj_id.c
> @@ -0,0 +1,81 @@
> +#include <linux/kernel.h>
> +#include <linux/capability.h>
> +#include <linux/cryptohash.h>
> +#include <linux/string.h>
> +#include <linux/random.h>
> +#include <linux/module.h>
> +#include <linux/init.h>
> +#include <linux/cache.h>
> +#include <linux/bug.h>
> +#include <linux/err.h>
> +
> +#include <linux/gen_obj_id.h>
> +
> +static unsigned long gen_obj_cookie[GEN_OBJ_ID_TYPES] __read_mostly;
> +
> +int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
> +{
> +	__u32 hash[SHA_DIGEST_WORDS];
> +	__u32 workspace[SHA_WORKSPACE_WORDS];
> +	__u8 extract[SHA_MESSAGE_BYTES];
> +	__u8 *t = (__u8 *)hash;
> +	unsigned long id;
> +	int i;
> +
> +	BUG_ON(type >= GEN_OBJ_ID_TYPES);
> +
> +	if (!capable(CAP_SYS_ADMIN) ||
> +	    size < GEN_OBJ_ID_BUF_SIZE) {
> +		memset(dst, '0', size);
> +		return -EINVAL;
> +	}
> +
> +	id = ((unsigned long)ptr) ^ gen_obj_cookie[type];
> +
> +	BUILD_BUG_ON(SHA_MESSAGE_BYTES % sizeof(long));
> +
> +	/*
> +	 * Expand the ID to the whole message block.
> +	 */
> +	for (i = 0; i < (SHA_MESSAGE_BYTES / sizeof(long)); i++)
> +		((long *)extract)[i] = id;
> +
> +	sha_init(hash);
> +	sha_transform(hash, extract, workspace);
> +
> +	snprintf(dst, size,
> +		 "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x"
> +		 "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
> +		 t[ 0], t[ 1], t[ 2], t[ 3], t[ 4],
> +		 t[ 5], t[ 6], t[ 7], t[ 8], t[ 9],
> +		 t[10], t[11], t[12], t[13], t[14],
> +		 t[15], t[16], t[17], t[18], t[19]);
> +
> +	return 0;
> +}
> +
> +static __init int gen_obj_cookie_init(void)
> +{
> +#if BITS_PER_LONG == 64
> +	const unsigned long emergency_cookie = 0xefcdab8967452301;
> +#else
> +	const unsigned long emergency_cookie = 0x98badcf9;
> +#endif
> +	int i;
> +
> +	for (i = 0; i < GEN_OBJ_ID_TYPES; i++) {
> +		get_random_bytes(&gen_obj_cookie[i],
> +				 sizeof(unsigned long));
> +		/*
> +		 * In 'impossible' case of random-bytes = 0
> +		 * we still would have non-zero value.
> +		 */
> +		gen_obj_cookie[i] =
> +			(gen_obj_cookie[i] & __PAGE_OFFSET) +
> +			(emergency_cookie & ~__PAGE_OFFSET);
> +	}
> +
> +	return 0;
> +}
> +
> +late_initcall(gen_obj_cookie_init);

-- 
tejun

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Thu, Dec 29, 2011 at 08:14:14AM -0800, Tejun Heo wrote:
> Hello,
> 
> On Thu, Dec 29, 2011 at 06:24:38PM +0400, Cyrill Gorcunov wrote:
> > Tejun, I've tried to use crypto engine here but it produced a warning
> > about being used in non-sleepable context (which takes place when we
> > read /proc/<pid>/fdinfo/* files). So I used lib/sha1.c instead. The
> > final result is below, please review.
> 
> I don't know anything about cryptography and have no idea whether sha1
> is good enough, so I can't really say much. :)
> 
> Which part triggered the context warning?  IIRC, crypto context
> preparation and actual calculation can be done in separate steps.
> Can't the calculation part be done from non-sleepable context?
> 
> cc'ing Herbert & David and quoting the whole message.
> 

I've got the following warning when being calculated sha hash
for "cat /proc/self/fdinfo/0" as following

[root@localhost ~]# cat /proc/self/fdinfo/0
[   89.120366] BUG: sleeping function called from invalid context at kernel/rwsem.c:21
[   89.123316] in_atomic(): 1, irqs_disabled(): 0, pid: 2395, name: cat
[   89.125324] 1 lock held by cat/2395:
[   89.125935]  #0:  (&(&newf->file_lock)->rlock){+.+...}, at: [<ffffffff8127a57a>] proc_fd_info+0x98/0x1f8
[   89.127647] Pid: 2395, comm: cat Not tainted 3.2.0-rc6+ #281
[   89.128615] Call Trace:
[   89.129056]  [<ffffffff810b824e>] __might_sleep+0x17c/0x188
[   89.129995]  [<ffffffff82058ba2>] down_read+0x2d/0xcc
[   89.130874]  [<ffffffff810859fd>] ? kvm_clock_read+0x54/0x9f
[   89.131856]  [<ffffffff814079ef>] crypto_alg_lookup+0x2a/0x68
[   89.132867]  [<ffffffff81407b51>] crypto_larval_lookup+0x4f/0x1c4
[   89.133951]  [<ffffffff81407cf7>] crypto_alg_mod_lookup+0x31/0xba
[   89.135020]  [<ffffffff81407fc6>] crypto_alloc_base+0x3d/0xd9
[   89.135994]  [<ffffffff81117eac>] ? __lock_acquire+0x7c1/0x1486
[   89.137025]  [<ffffffff81201a88>] gen_obj_id+0x7c/0x288
[   89.137912]  [<ffffffff8105ce40>] ? sched_clock+0x10/0x1b
[   89.138844]  [<ffffffff811031f8>] ? sched_clock_local+0x15/0xb9
[   89.139854]  [<ffffffff810f3b5d>] ? get_pid_task+0x5f/0x70
[   89.140798]  [<ffffffff8110345f>] ? sched_clock_cpu+0x137/0x154
[   89.141820]  [<ffffffff8127a57a>] ? proc_fd_info+0x98/0x1f8
[   89.142788]  [<ffffffff811160f3>] ? lock_acquired+0x2ed/0x30e
[   89.143773]  [<ffffffff8127a62d>] proc_fd_info+0x14b/0x1f8
[   89.144716]  [<ffffffff8127a729>] proc_fdinfo_read+0x4f/0xaf
[   89.145687]  [<ffffffff81204c8a>] vfs_read+0xe6/0x163
[   89.146549]  [<ffffffff81206981>] ? fget_light+0x41/0xf9
[   89.147465]  [<ffffffff81204d69>] sys_read+0x62/0x97
[   89.148342]  [<ffffffff82063b02>] system_call_fastpath+0x16/0x1b
pos:    0
flags:  0100002
id:     8db6cbf5ffede35133f633dc492e71fae28f3b8c

the helper routine was like (note it was a draft version)

+int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
+{
+	__u8 tmp[GEN_OBJ_ID_DIGEST_SIZE];
+	struct crypto_hash *tfm;
+	struct scatterlist sg[1];
+	struct hash_desc desc;
+	unsigned long key;
+	int err = 0;
+
+	BUG_ON(type >= GEN_OBJ_ID_TYPES);
+
+	if (unlikely(size < GEN_OBJ_ID_BUF_SIZE))
+               return -EINVAL;
+
+	tfm = crypto_alloc_hash("sha1", 0, CRYPTO_ALG_ASYNC);
+	if (IS_ERR(tfm))
+               return PTR_ERR(tfm);
+
+	WARN_ON_ONCE(crypto_hash_digestsize(tfm) != GEN_OBJ_ID_DIGEST_SIZE);
+
+	desc.tfm = tfm;
+	desc.flags = 0;
+
+	key = ((unsigned long)ptr) ^ gen_obj_cookie[type];
+	sg_init_one(sg, &key, sizeof(key));
+
+	err = crypto_hash_init(&desc);
+	if (!err)
+               err = crypto_hash_update(&desc, sg, sizeof(key));
+	if (!err)
+               err = crypto_hash_final(&desc, tmp);
+	crypto_free_hash(tfm);
+	if (!err)
+               snprintf(dst, size,
+                        "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x"
+                        "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
+                        tmp[ 0], tmp[ 1], tmp[ 2], tmp[ 3], tmp[ 4],
+                        tmp[ 5], tmp[ 6], tmp[ 7], tmp[ 8], tmp[ 9],
+                        tmp[10], tmp[11], tmp[12], tmp[13], tmp[14],
+                        tmp[15], tmp[16], tmp[17], tmp[18], tmp[19]);
+
+	return err;
+}

Probably I've had to crypto_alloc_hash earlier and simply keep a reference
to algo but since I'm not sure if looking for modules in late-init-call
is good idea.

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Herbert Xu]

On Thu, Dec 29, 2011 at 08:24:53PM +0400, Cyrill Gorcunov wrote:
>
> Probably I've had to crypto_alloc_hash earlier and simply keep a reference
> to algo but since I'm not sure if looking for modules in late-init-call
> is good idea.

Right, the allocation needs to occur in a sleepable context.

If you're just hashing something small and have no need for
hardware acceleration then lib/sha1.c is fine.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Fri, Dec 30, 2011 at 11:23:09AM +1100, Herbert Xu wrote:
> On Thu, Dec 29, 2011 at 08:24:53PM +0400, Cyrill Gorcunov wrote:
> >
> > Probably I've had to crypto_alloc_hash earlier and simply keep a reference
> > to algo but since I'm not sure if looking for modules in late-init-call
> > is good idea.
> 
> Right, the allocation needs to occur in a sleepable context.
> 
> If you're just hashing something small and have no need for
> hardware acceleration then lib/sha1.c is fine.
> 

Hi, yeah, it's just one message block hashing so I've switched
to lib/sha1.c. Herbert, I'm more interested in security analysis
-- would the sha1(msg), where the 'msg' is the kernel pointer
XOR'ed with random value and expanded to the 512 bits would be
safe enough for export to unprivilege users?

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[KOSAKI Motohiro]

(12/30/11 2:36 AM), Cyrill Gorcunov wrote:
> On Fri, Dec 30, 2011 at 11:23:09AM +1100, Herbert Xu wrote:
>> On Thu, Dec 29, 2011 at 08:24:53PM +0400, Cyrill Gorcunov wrote:
>>>
>>> Probably I've had to crypto_alloc_hash earlier and simply keep a reference
>>> to algo but since I'm not sure if looking for modules in late-init-call
>>> is good idea.
>>
>> Right, the allocation needs to occur in a sleepable context.
>>
>> If you're just hashing something small and have no need for
>> hardware acceleration then lib/sha1.c is fine.
>>
>
> Hi, yeah, it's just one message block hashing so I've switched
> to lib/sha1.c. Herbert, I'm more interested in security analysis
> -- would the sha1(msg), where the 'msg' is the kernel pointer
> XOR'ed with random value and expanded to the 512 bits would be
> safe enough for export to unprivilege users?

Even if now we don't know an attacking way of sha1 reverse hashing,
we may discover within 10 years. Many secure messages lost from hardware 
speedup and new algorithm attack. so, nobody can say it's abi safe.

And, if you don't use perfect hash, you may have a hash collision risk. 
What's happen if different pointer makes same ID?

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Fri, Dec 30, 2011 at 03:31:32PM -0500, KOSAKI Motohiro wrote:
> (12/30/11 2:36 AM), Cyrill Gorcunov wrote:
> >On Fri, Dec 30, 2011 at 11:23:09AM +1100, Herbert Xu wrote:
> >>On Thu, Dec 29, 2011 at 08:24:53PM +0400, Cyrill Gorcunov wrote:
> >>>
> >>>Probably I've had to crypto_alloc_hash earlier and simply keep a reference
> >>>to algo but since I'm not sure if looking for modules in late-init-call
> >>>is good idea.
> >>
> >>Right, the allocation needs to occur in a sleepable context.
> >>
> >>If you're just hashing something small and have no need for
> >>hardware acceleration then lib/sha1.c is fine.
> >>
> >
> >Hi, yeah, it's just one message block hashing so I've switched
> >to lib/sha1.c. Herbert, I'm more interested in security analysis
> >-- would the sha1(msg), where the 'msg' is the kernel pointer
> >XOR'ed with random value and expanded to the 512 bits would be
> >safe enough for export to unprivilege users?
> 
> Even if now we don't know an attacking way of sha1 reverse hashing,
> we may discover within 10 years. Many secure messages lost from
> hardware speedup and new algorithm attack. so, nobody can say it's
> abi safe.
>

Yes, I know. But there is a big difference between direct hash crack and
indirect crack caused by limited space of data used for such hash. That's
the reason why random cookie was used and xor production was expanded to
the whole message block.

> And, if you don't use perfect hash, you may have a hash collision
> risk. What's happen if different pointer makes same ID?

Well, strictly speaking this is pretty bad case for me. Of course this
wont lead to catastrophic results for user-space application I think
but definitely I would prefer to not have collisions here.

Guys, this become more and more complex, finally I fear someone
propose to do ideal hashing run-time ;) Maybe we can step back and
live with root-only and plain pointers here? I'm not sure who else
might need such facility except us, and if once there will be a candidate
-- we could take a look on hashing again and provide safe hashes there. No?

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[KOSAKI Motohiro]

(12/30/11 3:48 PM), Cyrill Gorcunov wrote:
> On Fri, Dec 30, 2011 at 03:31:32PM -0500, KOSAKI Motohiro wrote:
>> (12/30/11 2:36 AM), Cyrill Gorcunov wrote:
>>> On Fri, Dec 30, 2011 at 11:23:09AM +1100, Herbert Xu wrote:
>>>> On Thu, Dec 29, 2011 at 08:24:53PM +0400, Cyrill Gorcunov wrote:
>>>>>
>>>>> Probably I've had to crypto_alloc_hash earlier and simply keep a reference
>>>>> to algo but since I'm not sure if looking for modules in late-init-call
>>>>> is good idea.
>>>>
>>>> Right, the allocation needs to occur in a sleepable context.
>>>>
>>>> If you're just hashing something small and have no need for
>>>> hardware acceleration then lib/sha1.c is fine.
>>>>
>>>
>>> Hi, yeah, it's just one message block hashing so I've switched
>>> to lib/sha1.c. Herbert, I'm more interested in security analysis
>>> -- would the sha1(msg), where the 'msg' is the kernel pointer
>>> XOR'ed with random value and expanded to the 512 bits would be
>>> safe enough for export to unprivilege users?
>>
>> Even if now we don't know an attacking way of sha1 reverse hashing,
>> we may discover within 10 years. Many secure messages lost from
>> hardware speedup and new algorithm attack. so, nobody can say it's
>> abi safe.
>>
>
> Yes, I know. But there is a big difference between direct hash crack and
> indirect crack caused by limited space of data used for such hash. That's
> the reason why random cookie was used and xor production was expanded to
> the whole message block.
>
>> And, if you don't use perfect hash, you may have a hash collision
>> risk. What's happen if different pointer makes same ID?
>
> Well, strictly speaking this is pretty bad case for me. Of course this
> wont lead to catastrophic results for user-space application I think
> but definitely I would prefer to not have collisions here.
>
> Guys, this become more and more complex, finally I fear someone
> propose to do ideal hashing run-time ;) Maybe we can step back and
> live with root-only and plain pointers here? I'm not sure who else
> might need such facility except us, and if once there will be a candidate
> -- we could take a look on hashing again and provide safe hashes there. No?

But recently kernel security fashion are, we don't expose a kernel 
pointer at all even though the file is root only. I'm not sure how
much effective such fashion. but you seems run opposite way.

I doubt user land can implement good comparison way. Why you gave up 
Andrew's sys_are_these_files_the_same() idea?

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Kyle Moffett]

On Thu, Dec 29, 2011 at 11:24, Cyrill Gorcunov <gorcunov@gmail.com> wrote:
> +int gen_obj_id(void *ptr, int type, char *dst, unsigned long size)
> +{
> [...]
> +       unsigned long key;
> [...]
> +       BUG_ON(type >= GEN_OBJ_ID_TYPES);
> +
> +       if (unlikely(size < GEN_OBJ_ID_BUF_SIZE))
> +               return -EINVAL;
> +
> +       tfm = crypto_alloc_hash("sha1", 0, CRYPTO_ALG_ASYNC);
> +       if (IS_ERR(tfm))
> +               return PTR_ERR(tfm);
> +
> +       WARN_ON_ONCE(crypto_hash_digestsize(tfm) != GEN_OBJ_ID_DIGEST_SIZE);

The issue here is "crypto_alloc_hash()" from atomic context.  Do that
during initialization when you compute the gen_obj_cookie[] array.

For the syscall prototype, something like this:

        ssize_t object_id(int obj_type, int id_type, long id, void
*buffer, size_t buffer_len);

The function would populate as many bytes of "buffer" as it needs to
store the object ID, up to "buffer_len", and it would return the total
number of bytes needed for that particular object ID (even if more
than fit in the buffer), or a negative number for an error.  That
would allow different object types to have different numbers of bytes
depending on the hash algorithm in use.  In practice, it would even
work fine if somebody implemented a program which always passed a
128-byte buffer and a constant 128, as the first 128 bytes of SHA-2
512 is at least as unique as SHA-1.

The "obj_type" would be something like "OBJECT_TYPE_FILE",
"OBJECT_TYPE_PROCESS", etc, while the "id_type" would be
"OBJECT_FROM_FD", "OBJECT_FROM_PID", "OBJECT_FROM_TID", etc.  That
would be very easy to extend in the future with new ways of looking up
object information (IE: add "OBJECT_FROM_MMAP" that takes a cast
pointer to a mapped area as "id" and looks up the file associated with
it).

A quick optimization for users is something like this:
if (!buffer_len)
        return crypto_hash_digestsize(tfm);

> [...]
> +       key = ((unsigned long)ptr) ^ gen_obj_cookie[type];
> +       sg_init_one(sg, &key, sizeof(key));

Don't XOR the key and the object cookie, you are reducing your
possible hash states.  Instead feed both together into the hash, and
make "gen_obj_cookie" an array of 8 or 16 bytes, EG:

u8 key[sizeof(void *) + sizeof(gen_obj_cookie[type])];
*(void **)key = ptr;
memcpy(key + sizeof(void *), &gen_obj_cookie[type],
sizeof(gen_obj_cookie[type]));

Even SHA-1 benefits from the massive number of additional possible
hash states that this provides over SHA1(ptr ^ cookie).  Ideally, you
should actually dynamically allocate the gen_obj_cookie data so that
the cookcie value is the same size as the hash output.  That ensures
that even if a "ptr" is always the same (IE: known-plaintext attack)
you still have to break the whole hash algorithm to compute
"gen_obj_cookie".  This makes even a partially-broken hash much
stronger against the same attacks.

> +               snprintf(dst, size,
> +                        "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x"
> +                        "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
> +                        tmp[ 0], tmp[ 1], tmp[ 2], tmp[ 3], tmp[ 4],
> +                        tmp[ 5], tmp[ 6], tmp[ 7], tmp[ 8], tmp[ 9],
> +                        tmp[10], tmp[11], tmp[12], tmp[13], tmp[14],
> +                        tmp[15], tmp[16], tmp[17], tmp[18], tmp[19]);

Don't hexdump the key, just return pure binary and allow the user to
encode it if they care (EG: files in "proc" would hexdump, but a
syscall would not).  Also, I somehow suspect there is a preexisting
function to do this for a byte array.

Cheers,
Kyle Moffett

-- 
Curious about my work on the Debian powerpcspe port?
I'm keeping a blog here: http://pureperl.blogspot.com/

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Fri, Dec 30, 2011 at 06:51:37PM -0500, KOSAKI Motohiro wrote:
...
> >
> >Guys, this become more and more complex, finally I fear someone
> >propose to do ideal hashing run-time ;) Maybe we can step back and
> >live with root-only and plain pointers here? I'm not sure who else
> >might need such facility except us, and if once there will be a candidate
> >-- we could take a look on hashing again and provide safe hashes there. No?
> 
> But recently kernel security fashion are, we don't expose a kernel
> pointer at all even though the file is root only. I'm not sure how
> much effective such fashion. but you seems run opposite way.
> 
> I doubt user land can implement good comparison way. Why you gave up
> Andrew's sys_are_these_files_the_same() idea?
> 

Because of speed, as Pavel mentioned
 |
 | With this the complexity of determining sharing for N files scattered across
 | several tasks would be N^2, since we'll have to compare each file to each file.
 |
 | On the other hand having just N IDs at hands would allow us to use more
 | efficient algorithms resulting in e.g. N*log(N) complexity.
 |

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Fri, Dec 30, 2011 at 11:55:29PM -0500, Kyle Moffett wrote:
...
> 
> Don't hexdump the key, just return pure binary and allow the user to
> encode it if they care (EG: files in "proc" would hexdump, but a
> syscall would not).  Also, I somehow suspect there is a preexisting
> function to do this for a byte array.
> 

Thanks a *lot* for comments, Kyle! I'll think about it and try to make
some draft prototype.

	Cyrill

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[bastien ROUCARIES]

Le Saturday 31 December 2011 08:51:02, Cyrill Gorcunov a écrit :
> On Fri, Dec 30, 2011 at 06:51:37PM -0500, KOSAKI Motohiro wrote:
> ...
> 
> > >Guys, this become more and more complex, finally I fear someone
> > >propose to do ideal hashing run-time ;) Maybe we can step back and
> > >live with root-only and plain pointers here? I'm not sure who else
> > >might need such facility except us, and if once there will be a
> > >candidate -- we could take a look on hashing again and provide safe
> > >hashes there. No?
> > 
> > But recently kernel security fashion are, we don't expose a kernel
> > pointer at all even though the file is root only. I'm not sure how
> > much effective such fashion. but you seems run opposite way.
> > 
> > I doubt user land can implement good comparison way. Why you gave up
> > Andrew's sys_are_these_files_the_same() idea?

By memory, it seems that fuse expose kernel pointer encrypting it with tea. Tea is simple and quick you should get a glimpse at 
it.

> Because of speed, as Pavel mentioned
> 
>  | With this the complexity of determining sharing for N files scattered
>  | across several tasks would be N^2, since we'll have to compare each
>  | file to each file.
>  | 
>  | On the other hand having just N IDs at hands would allow us to use more
>  | efficient algorithms resulting in e.g. N*log(N) complexity.



> 	Cyrill
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [patch 1/4] Add routine for generating an ID for kernel pointer

[Cyrill Gorcunov]

On Mon, Jan 02, 2012 at 01:18:13PM +0100, bastien ROUCARIES wrote:
> Le Saturday 31 December 2011 08:51:02, Cyrill Gorcunov a écrit :
> > On Fri, Dec 30, 2011 at 06:51:37PM -0500, KOSAKI Motohiro wrote:
> > ...
> > 
> > > >Guys, this become more and more complex, finally I fear someone
> > > >propose to do ideal hashing run-time ;) Maybe we can step back and
> > > >live with root-only and plain pointers here? I'm not sure who else
> > > >might need such facility except us, and if once there will be a
> > > >candidate -- we could take a look on hashing again and provide safe
> > > >hashes there. No?
> > > 
> > > But recently kernel security fashion are, we don't expose a kernel
> > > pointer at all even though the file is root only. I'm not sure how
> > > much effective such fashion. but you seems run opposite way.
> > > 
> > > I doubt user land can implement good comparison way. Why you gave up
> > > Andrew's sys_are_these_files_the_same() idea?
> 
> By memory, it seems that fuse expose kernel pointer encrypting it with tea.
> Tea is simple and quick you should get a glimpse at it.
> 

I've been advised to try aes as well with random cookie as a key.
I'll take a look once I've time to. Thanks!

	Cyrill