Slab objects identifiers

The idea of how to generate and ID for an arbitrary slab object is simple:

- The ID is 128 bits
- The upper 64 bits are slab ID
- The lower 64 bits are object index withing a slab (yes, it's too many, but is done for simplicity - not to deal with 96-bit numbers)
- The slab ID is the 48-bit per-cpu monotonic counter mixed with 16-bit cpuid. Even if being incremented 1M times per second the first part will stay uniqe for 200+ years. The cpuid is required to make values picked on two cpus differ.

Signed-off-by Pavel Emelyanov<[email protected]>

---
  include/linux/slab.h |   17 +++++++++++++++++
  init/Kconfig         |    9 +++++++++
  mm/Makefile          |    1 +
  mm/slab_obj_ids.c    |   25 +++++++++++++++++++++++++
  4 files changed, 52 insertions(+), 0 deletions(-)

create mode 100644 mm/slab_obj_ids.c

include/linux/slab.h +17 -0

index 573c809..ae9c735 100644
@@ -23,6 +23,7 @@
  #define SLAB_CACHE_DMA		0x00004000UL	/* Use GFP_DMA memory */
  #define SLAB_STORE_USER		0x00010000UL	/* DEBUG: Store the last owner for bug hunting */
  #define SLAB_PANIC		0x00040000UL	/* Panic if kmem_cache_create() fails */
+#define SLAB_WANT_OBJIDS	0x00080000UL	/* Want GENERIC_OBJECT_IDS-friendly slabs */
  /*
   * SLAB_DESTROY_BY_RCU - **WARNING** READ THIS!
   *

@@ -162,6 +163,22 @@ void kfree(const void *);
  void kzfree(const void *);
  size_t ksize(const void *);
 
+#ifdef CONFIG_SLAB_OBJECT_IDS
+void __slab_pick_id(u64 *s_id);
+static inline void __slab_get_id(u64 *id, u64 s_id, u64 o_id)
+{
+	id[0] = o_id;
+	id[1] = s_id;
+}
+
+void k_object_id(const void *, u64 *id);
+#else
+static inline void k_object_id(const void *x, u64 *id)
+{
+	id[0] = id[1] = 0;
+}
+#endif
+
  /*
   * Allocator specific definitions. These are mainly used to establish optimized
   * ways to convert kmalloc() calls to kmem_cache_alloc() invocations by

init/Kconfig +9 -0

index d627783..4c1c0e6 100644
@@ -1200,6 +1200,15 @@ config SLUB_DEBUG
  	  SLUB sysfs support. /sys/slab will not exist and there will be
  	  no support for cache validation etc.
 
+config SLAB_OBJECT_IDS
+	default y
+	bool "Enable slab kernel object ID infrastructure"
+	depends on !SLOB
+	help
+	  This option provides an infrastructure for calculating ID-s of
+	  slab/slub objects. These ID-s are not based on the object location
+	  in memory and thus can be shown to the userspace.
+
  config COMPAT_BRK
  	bool "Disable heap randomization"
  	default y

mm/Makefile +1 -0

index 836e416..fb65080 100644
@@ -50,3 +50,4 @@ obj-$(CONFIG_HWPOISON_INJECT) += hwpoison-inject.o
  obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o
  obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o
  obj-$(CONFIG_CLEANCACHE) += cleancache.o
+obj-$(CONFIG_SLAB_OBJECT_IDS) += slab_obj_ids.o

mm/slab_obj_ids.c new file +15 -0

new file mode 100644
index 0000000..87d1693
@@ -0,0 +1,25 @@
+#include<linux/percpu.h>
+
+#define SLUB_ID_CPU_SHIFT	16
+static DEFINE_PER_CPU(u64, slub_ids);
+
+void __slab_pick_id(u64 *s_id)
+{
+	int cpu;
+	u64 id;
+
+	/*
+	 * The idea behind this all is very simple:
+	 *
+	 * The ID is the 48-bit per-cpu monotonic counter mixed with 16-bit cpuid.
+	 * Even if being incremented 1M times per second the first part will stay

Hi Pavel,

Quoted 10 lines · Pavel Emelyanov

The idea of how to generate and ID for an arbitrary slab object is simple:

- The ID is 128 bits
- The upper 64 bits are slab ID
- The lower 64 bits are object index withing a slab (yes, it's too many, but is done for simplicity - not to deal with 96-bit numbers)
- The slab ID is the 48-bit per-cpu monotonic counter mixed with 16-bit cpuid. Even if being incremented 1M times per second the first part will stay uniqe for 200+ years. The cpuid is required to make values picked on two cpus differ.

So why can't we just use tighter numbers, and leave some reserved fields instead ?

Having ids in the objects of the slab may prove useful in the future for other uses as well.

For instance, concurrent to that, we're trying to figure out ways to have per-cgroup pages/objects accounted in the memory controller.

The most up2date proposals create an entire kmem cache for each cgroup, thus trivially guaranteeing uniqueness. It however, leads to fragmentation. Having the objects to be IDed and being cgroup part of this id, could help us achieve the same goal with less fragmentation.

While doing the checkpoint-restore in the userspace we need to determine whether various kernel objects (like mm_struct-s of file_struct-s) are shared between tasks and restore this state.

The 2nd step can for now be solved by using respective CLONE_XXX flags and the unshare syscall, while there's currently no ways for solving the 1st one.

One of the ways for checking whether two tasks share e.g. an mm_struct is to provide some mm_struct ID of a task to its proc file. The best from the performance point of view ID is the object address in the kernel, but showing them to the userspace is not good for performance reasons. Thus the ID should not be calculated based on the object address.

Quoted 4 lines · Pavel Emelyanov

While doing the checkpoint-restore in the userspace we need to determine whether various kernel objects (like mm_struct-s of file_struct-s) are shared between tasks and restore this state.

Quoted 8 lines

The 2nd step can for now be solved by using respective CLONE_XXX flags and the unshare syscall, while there's currently no ways for solving the 1st one.

One of the ways for checking whether two tasks share e.g. an mm_struct is to provide some mm_struct ID of a task to its proc file. The best from the performance point of view ID is the object address in the kernel, but showing them to the userspace is not good for performance reasons. Thus the ID should not be calculated based on the object address.

If two tasks share an mm_struct then the mm_struct pointer (task->mm) will point to the same address. Objects are already uniquely identified by their address.

If you store the physical address with the object content when transferring then you can verify that they share the mm_struct.

Quoted 2 lines

If you store the physical address with the object content when transferring then you can verify that they share the mm_struct.

... are we all OK with showing kernel addresses to the userspace? I thought the %pK format was invented specially to handle such leaks.

If we are, then (as I said in the first letter) we should just show them and forget this set. If we're not - we should invent smth more straightforward and this set is an attempt for doing this.

Quoted 5 lines · Pavel Emelyanov

Quoted 2 lines

If you store the physical address with the object content when transferring then you can verify that they share the mm_struct.

... are we all OK with showing kernel addresses to the userspace? I thought the %pK format was invented specially to handle such leaks.

Not in general but I think for process migration we are fine with the handling of the addresses. Doesnt process migration require rooot anyways?

Adding additional metadata to each slab or object is certainly not acceptable because it slows down operations for everyone.

Quoted 3 lines

If we are, then (as I said in the first letter) we should just show them and forget this set. If we're not - we should invent smth more straightforward and this set is an attempt for doing this.

Well one solution is to show the addresses only to members of a specific group or only to root.

Quoted 3 lines

If two tasks share an mm_struct then the mm_struct pointer (task->mm) will point to the same address. Objects are already uniquely identified by their address.

Yes of course, but ...

Quoted 2 lines

If you store the physical address with the object content when transferring then you can verify that they share the mm_struct.

... are we all OK with showing kernel addresses to the userspace? I thought the %pK format was invented specially to handle such leaks.

If we are, then (as I said in the first letter) we should just show them and forget this set. If we're not - we should invent smth more straightforward and this set is an attempt for doing this.

Quoted 6 lines · Pavel Emelyanov

Quoted 3 lines

If two tasks share an mm_struct then the mm_struct pointer (task->mm) will point to the same address. Objects are already uniquely identified by their address.

Yes of course, but ...

Quoted 5 lines

Quoted 2 lines

If you store the physical address with the object content when transferring then you can verify that they share the mm_struct.

... are we all OK with showing kernel addresses to the userspace? I thought the %pK format was invented specially to handle such leaks.

I don't think it's worth it to try to hide kernel addresses for checkpoint/restart.

Quoted 3 lines

If we are, then (as I said in the first letter) we should just show them and forget this set. If we're not - we should invent smth more straightforward and this set is an attempt for doing this.

Does this ID thing need to happen in the slab layer?

Pekka
.

Quoted 5 lines

Quoted 2 lines

... are we all OK with showing kernel addresses to the userspace? I thought the %pK format was invented specially to handle such leaks.

I don't think it's worth it to try to hide kernel addresses for checkpoint/restart.

We don't need to know anything about kernel internals for checkpoint-restart, that's why I said, that abstract identifiers are just fine.

Quoted 5 lines

Quoted 3 lines

If we are, then (as I said in the first letter) we should just show them and forget this set. If we're not - we should invent smth more straightforward and this set is an attempt for doing this.

Does this ID thing need to happen in the slab layer?

Not necessarily, of course, but if we're going to show some identifier of an object we have 2 choices - either we generate this ID independently (with e.g. IDA), but this is slow, or we use some knowledge of an object as a bunch of bytes in memory. These slab IDs thing is an attempt to implement the 2nd approach.

The question I'm trying to answer with this is - do task A and task B have their mm shared or not? Showing an ID answers one. Maybe there exists another way, but I haven't invented it yet and decided to send this set out for discussion (the "release early" idiom). If slab maintainers say "no, we don't accept this at all ever", then of course I'll have to think further, but if the concept is suitable, but needs some refinement - let's do it.

Quoted 6 lines

Quoted 1 line

Does this ID thing need to happen in the slab layer?

Not necessarily, of course, but if we're going to show some identifier of an object we have 2 choices - either we generate this ID independently (with e.g. IDA), but this is slow, or we use some knowledge of an object as a bunch of bytes in memory. These slab IDs thing is an attempt to implement the 2nd approach.

Why is the first approach slow? I fully agree that unique IDs are probably the way to go here but why don't you just add a new member to struct mm_struct and initialize it in mm_alloc() and mm_dup()?

Quoted 6 lines

The question I'm trying to answer with this is - do task A and task B have their mm shared or not? Showing an ID answers one. Maybe there exists another way, but I haven't invented it yet and decided to send this set out for discussion (the "release early" idiom). If slab maintainers say "no, we don't accept this at all ever", then of course I'll have to think further, but if the concept is suitable, but needs some refinement - let's do it.

Oh, I much appreciate that you sent this early. I'm not completely against doing this in the slab layer but I need much more convincing. I expect most distros to enable checkpoint/restart so this ID mechanism is going to be default on for slab.

Pekka
.

Hi.

While doing the checkpoint-restore in the userspace we need to determine whether various kernel objects (like mm_struct-s of file_struct-s) are shared between tasks and restore this state.
The 2nd step can for now be solved by using respective CLONE_XXX flags and the unshare syscall, while there's currently no ways for solving the 1st one.

One of the ways for checking whether two tasks share e.g. an mm_struct is to provide some mm_struct ID of a task to its proc file. The best from the performance point of view ID is the object address in the kernel, but showing them to the userspace is not good for performance reasons. Thus the ID should not be calculated based on the object address.

The proposal is to have the ID for slab objects as the mixture of two things - the number of an object on the slub and the ID of a slab, which is calculated simply by getting a monotonic 64 bit number at the slab allocation time which gives us 200+ years of stable work (see comment in the patch #2) :)

On Thu, Oct 06, 2011 at 08:22:17PM +0400, Pavel Emelyanov wrote:

Quoted 15 lines

Hi.

While doing the checkpoint-restore in the userspace we need to determine whether various kernel objects (like mm_struct-s of file_struct-s) are shared between tasks and restore this state.
The 2nd step can for now be solved by using respective CLONE_XXX flags and the unshare syscall, while there's currently no ways for solving the 1st one.

One of the ways for checking whether two tasks share e.g. an mm_struct is to provide some mm_struct ID of a task to its proc file. The best from the performance point of view ID is the object address in the kernel, but showing them to the userspace is not good for performance reasons. Thus the ID should not be calculated based on the object address.

Quoted 4 lines

The proposal is to have the ID for slab objects as the mixture of two things - the number of an object on the slub and the ID of a slab, which is calculated simply by getting a monotonic 64 bit number at the slab allocation time which gives us 200+ years of stable work (see comment in the patch #2) :)

This just strikes me as the wrong approach. Userspace should not need to know the structures the kernel is using to implement the sharing that's possible with the clone flags. The userspace interface should be framed such that the kernel is not exporting the relationship between these structures so much as the relationship between the tasks which those structures reflect. Perhaps you could write the interface so that it shows the clone flags one would use to re-create the child task from the parent instead of trying to output these ids.

Also, putting this in slab seems like a poor choice -- isn't instrumenting the allocator rather invasive?

Especialy when we're talking about a handful of structs in comparison to everything else the allocators handle?

Cheers,
-Matt Helsley
.