mm: Implement Slab Movable Objects (SMO)

Create an ops field in /sys/slab/*/ops to contain all the callback operations defined for a slab cache. This will be used to display the additional callbacks that will be defined soon to enable movable objects.

Display the existing ctor callback in the ops fields contents.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slub.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

mm/slub.c +0 -0

index dc777761b6b7..69164aa7cbbf 100644

Quoted 9 lines · Tobin C. Harding

Create an ops field in /sys/slab/*/ops to contain all the callback operations defined for a slab cache. This will be used to display the additional callbacks that will be defined soon to enable movable objects.

Display the existing ctor callback in the ops fields contents.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

Hi Tobin!

Quoted 9 lines

---
 mm/slub.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

mm/slub.c +0 -0

index dc777761b6b7..69164aa7cbbf 100644

mm/slub.c static ssize_t cpu_partial_store(struct kmem_cache *s, const char *buf, · line 5017

Quoted 10 lines

mm/slub.c +3 -1

@@ -5009,13 +5009,18 @@ static ssize_t cpu_partial_store(struct kmem_cache *s, const char *buf,
 }
 SLAB_ATTR(cpu_partial);
 
-static ssize_t ctor_show(struct kmem_cache *s, char *buf)
+static ssize_t ops_show(struct kmem_cache *s, char *buf)
 {
+	int x = 0;
+
 	if (!s->ctor)
 		return 0;

        ^^^^^^^^^^^^^^^^^

You can drop this part, can't you?

Also, it's not clear (without looking into following patches) why do you make this refactoring. So, please, add a note, or move this change into the patch 3.

Quoted 8 lines · Tobin C. Harding

mm/slab_common.c +0 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 

mm/slab_common.c int slab_unmergeable(struct kmem_cache *s) · line 304

Quoted 4 lines

mm/slab_common.c +4 -0

+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */

Shouldn't this implication go the other way, i.e.

    s->ctor => s->isolate & s->migrate

Quoted 9 lines · Tycho Andersen

Quoted 8 lines · Tobin C. Harding

mm/slab_common.c +0 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 

Quoted 7 lines

mm/slab_common.c int slab_unmergeable(struct kmem_cache *s) · line 304

Quoted 4 lines

mm/slab_common.c +4 -0

+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */

Shouldn't this implication go the other way, i.e.

    s->ctor => s->isolate & s->migrate

A cache can have a constructor but the object may not be movable (I.e. currently dentries and inodes).

Quoted 19 lines · Christopher Lameter

Quoted 16 lines · Tycho Andersen

mm/slab_common.c int slab_unmergeable(struct kmem_cache *s) · line 304

Quoted 12 lines · Tobin C. Harding

mm/slab_common.c +4 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 
+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */

Shouldn't this implication go the other way, i.e.

    s->ctor => s->isolate & s->migrate

Quoted 2 lines

A cache can have a constructor but the object may not be movable (I.e. currently dentries and inodes).

Yep, thanks. Somehow I got confused by the comment.

Quoted 20 lines · Tycho Andersen

Quoted 19 lines · Christopher Lameter

Quoted 16 lines · Tycho Andersen

mm/slab_common.c int slab_unmergeable(struct kmem_cache *s) · line 304

Quoted 12 lines · Tobin C. Harding

mm/slab_common.c +4 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 
+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */

Shouldn't this implication go the other way, i.e.

    s->ctor => s->isolate & s->migrate

Quoted 4 lines

Quoted 2 lines

A cache can have a constructor but the object may not be movable (I.e. currently dentries and inodes).

Yep, thanks. Somehow I got confused by the comment.

I removed code here from the original RFC-v2, if this comment is confusing perhaps we are better off without it.

Add the two methods needed for moving objects and enable the display of the callbacks via the /sys/kernel/slab interface.

Add documentation explaining the use of these methods and the prototypes for slab.h. Add functions to setup the callbacks method for a slab cache.

Add empty functions for SLAB/SLOB. The API is generic so it could be theoretically implemented for these allocators as well.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 include/linux/slab.h     | 69 ++++++++++++++++++++++++++++++++++++++++
 include/linux/slub_def.h |  3 ++
 mm/slab_common.c         |  4 +++
 mm/slub.c                | 42 ++++++++++++++++++++++++
 4 files changed, 118 insertions(+)

include/linux/slab.h +69 -0

index 11b45f7ae405..22e87c41b8a4 100644
@@ -152,6 +152,75 @@ void memcg_create_kmem_cache(struct mem_cgroup *, struct kmem_cache *);
 void memcg_deactivate_kmem_caches(struct mem_cgroup *);
 void memcg_destroy_kmem_caches(struct mem_cgroup *);
 
+/*
+ * Function prototypes passed to kmem_cache_setup_mobility() to enable
+ * mobile objects and targeted reclaim in slab caches.
+ */
+
+/**
+ * typedef kmem_cache_isolate_func - Object migration callback function.
+ * @s: The cache we are working on.
+ * @ptr: Pointer to an array of pointers to the objects to migrate.
+ * @nr: Number of objects in array.
+ *
+ * The purpose of kmem_cache_isolate_func() is to pin each object so that
+ * they cannot be freed until kmem_cache_migrate_func() has processed
+ * them. This may be accomplished by increasing the refcount or setting
+ * a flag.
+ *
+ * The object pointer array passed is also passed to
+ * kmem_cache_migrate_func().  The function may remove objects from the
+ * array by setting pointers to NULL. This is useful if we can determine
+ * that an object is being freed because kmem_cache_isolate_func() was
+ * called when the subsystem was calling kmem_cache_free().  In that
+ * case it is not necessary to increase the refcount or specially mark
+ * the object because the release of the slab lock will lead to the
+ * immediate freeing of the object.
+ *
+ * Context: Called with locks held so that the slab objects cannot be
+ *          freed.  We are in an atomic context and no slab operations
+ *          may be performed.
+ * Return: A pointer that is passed to the migrate function. If any
+ *         objects cannot be touched at this point then the pointer may
+ *         indicate a failure and then the migration function can simply
+ *         remove the references that were already obtained. The private
+ *         data could be used to track the objects that were already pinned.
+ */
+typedef void *kmem_cache_isolate_func(struct kmem_cache *s, void **ptr, int nr);
+
+/**
+ * typedef kmem_cache_migrate_func - Object migration callback function.
+ * @s: The cache we are working on.
+ * @ptr: Pointer to an array of pointers to the objects to migrate.
+ * @nr: Number of objects in array.
+ * @node: The NUMA node where the object should be allocated.
+ * @private: The pointer returned by kmem_cache_isolate_func().
+ *
+ * This function is responsible for migrating objects.  Typically, for
+ * each object in the input array you will want to allocate an new
+ * object, copy the original object, update any pointers, and free the
+ * old object.
+ *
+ * After this function returns all pointers to the old object should now
+ * point to the new object.
+ *
+ * Context: Called with no locks held and interrupts enabled.  Sleeping
+ *          is possible.  Any operation may be performed.
+ */
+typedef void kmem_cache_migrate_func(struct kmem_cache *s, void **ptr,
+				     int nr, int node, void *private);
+
+/*
+ * kmem_cache_setup_mobility() is used to setup callbacks for a slab cache.
+ */
+#ifdef CONFIG_SLUB
+void kmem_cache_setup_mobility(struct kmem_cache *, kmem_cache_isolate_func,
+			       kmem_cache_migrate_func);
+#else
+static inline void kmem_cache_setup_mobility(struct kmem_cache *s,
+	kmem_cache_isolate_func isolate, kmem_cache_migrate_func migrate) {}
+#endif
+
 /*
  * Please use this macro to create slab caches. Simply specify the
  * name of the structure and maybe some flags that are listed above.

include/linux/slub_def.h +3 -0

index 3a1a1dbc6f49..a7340a1ed5dc 100644
@@ -99,6 +99,9 @@ struct kmem_cache {
 	gfp_t allocflags;	/* gfp flags to use on each alloc */
 	int refcount;		/* Refcount for slab cache destroy */
 	void (*ctor)(void *);
+	kmem_cache_isolate_func *isolate;
+	kmem_cache_migrate_func *migrate;
+
 	unsigned int inuse;		/* Offset to metadata */
 	unsigned int align;		/* Alignment */
 	unsigned int red_left_pad;	/* Left redzone padding size */

mm/slab_common.c +4 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 
+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */
 	if (s->ctor)
 		return 1;
 

mm/slub.c +0 -0

index 69164aa7cbbf..0133168d1089 100644

mm/slub.c +10 -0

+	/*
+	 * Mobile objects must have a ctor otherwise the object may be
+	 * in an undefined state on allocation.  Since the object may
+	 * need to be inspected by the migration function at any time
+	 * after allocation we must ensure that the object always has a
+	 * defined state.
+	 */
+	if (!s->ctor) {
+		pr_err("%s: cannot setup mobility without a constructor\n",
+		       s->name);

mm/slub.c +4 -0

+	s->flags &= ~__CMPXCHG_DOUBLE;
+}
+EXPORT_SYMBOL(kmem_cache_setup_mobility);
+
 void *__kmalloc_track_caller(size_t size, gfp_t gfpflags, unsigned long caller)
 {
 	struct kmem_cache *s;

mm/slub.c +7 -0

+
+	if (s->migrate) {
+		x += sprintf(buf + x, "migrate : ");
+		x += sprint_symbol(buf + x,
+				(unsigned long)s->migrate);
+		x += sprintf(buf + x, "\n");
+	}
 	return x;
 }
 SLAB_ATTR_RO(ops);

Signature · 1 line

2.21.0

Quoted 136 lines · Tobin C. Harding

Add the two methods needed for moving objects and enable the display of the callbacks via the /sys/kernel/slab interface.

Add documentation explaining the use of these methods and the prototypes for slab.h. Add functions to setup the callbacks method for a slab cache.

Add empty functions for SLAB/SLOB. The API is generic so it could be theoretically implemented for these allocators as well.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 include/linux/slab.h     | 69 ++++++++++++++++++++++++++++++++++++++++
 include/linux/slub_def.h |  3 ++
 mm/slab_common.c         |  4 +++
 mm/slub.c                | 42 ++++++++++++++++++++++++
 4 files changed, 118 insertions(+)

include/linux/slab.h +69 -0

index 11b45f7ae405..22e87c41b8a4 100644
@@ -152,6 +152,75 @@ void memcg_create_kmem_cache(struct mem_cgroup *, struct kmem_cache *);
 void memcg_deactivate_kmem_caches(struct mem_cgroup *);
 void memcg_destroy_kmem_caches(struct mem_cgroup *);
 
+/*
+ * Function prototypes passed to kmem_cache_setup_mobility() to enable
+ * mobile objects and targeted reclaim in slab caches.
+ */
+
+/**
+ * typedef kmem_cache_isolate_func - Object migration callback function.
+ * @s: The cache we are working on.
+ * @ptr: Pointer to an array of pointers to the objects to migrate.
+ * @nr: Number of objects in array.
+ *
+ * The purpose of kmem_cache_isolate_func() is to pin each object so that
+ * they cannot be freed until kmem_cache_migrate_func() has processed
+ * them. This may be accomplished by increasing the refcount or setting
+ * a flag.
+ *
+ * The object pointer array passed is also passed to
+ * kmem_cache_migrate_func().  The function may remove objects from the
+ * array by setting pointers to NULL. This is useful if we can determine
+ * that an object is being freed because kmem_cache_isolate_func() was
+ * called when the subsystem was calling kmem_cache_free().  In that
+ * case it is not necessary to increase the refcount or specially mark
+ * the object because the release of the slab lock will lead to the
+ * immediate freeing of the object.
+ *
+ * Context: Called with locks held so that the slab objects cannot be
+ *          freed.  We are in an atomic context and no slab operations
+ *          may be performed.
+ * Return: A pointer that is passed to the migrate function. If any
+ *         objects cannot be touched at this point then the pointer may
+ *         indicate a failure and then the migration function can simply
+ *         remove the references that were already obtained. The private
+ *         data could be used to track the objects that were already pinned.
+ */
+typedef void *kmem_cache_isolate_func(struct kmem_cache *s, void **ptr, int nr);
+
+/**
+ * typedef kmem_cache_migrate_func - Object migration callback function.
+ * @s: The cache we are working on.
+ * @ptr: Pointer to an array of pointers to the objects to migrate.
+ * @nr: Number of objects in array.
+ * @node: The NUMA node where the object should be allocated.
+ * @private: The pointer returned by kmem_cache_isolate_func().
+ *
+ * This function is responsible for migrating objects.  Typically, for
+ * each object in the input array you will want to allocate an new
+ * object, copy the original object, update any pointers, and free the
+ * old object.
+ *
+ * After this function returns all pointers to the old object should now
+ * point to the new object.
+ *
+ * Context: Called with no locks held and interrupts enabled.  Sleeping
+ *          is possible.  Any operation may be performed.
+ */
+typedef void kmem_cache_migrate_func(struct kmem_cache *s, void **ptr,
+				     int nr, int node, void *private);
+
+/*
+ * kmem_cache_setup_mobility() is used to setup callbacks for a slab cache.
+ */
+#ifdef CONFIG_SLUB
+void kmem_cache_setup_mobility(struct kmem_cache *, kmem_cache_isolate_func,
+			       kmem_cache_migrate_func);
+#else
+static inline void kmem_cache_setup_mobility(struct kmem_cache *s,
+	kmem_cache_isolate_func isolate, kmem_cache_migrate_func migrate) {}
+#endif
+
 /*
  * Please use this macro to create slab caches. Simply specify the
  * name of the structure and maybe some flags that are listed above.

include/linux/slub_def.h +3 -0

index 3a1a1dbc6f49..a7340a1ed5dc 100644
@@ -99,6 +99,9 @@ struct kmem_cache {
 	gfp_t allocflags;	/* gfp flags to use on each alloc */
 	int refcount;		/* Refcount for slab cache destroy */
 	void (*ctor)(void *);
+	kmem_cache_isolate_func *isolate;
+	kmem_cache_migrate_func *migrate;
+
 	unsigned int inuse;		/* Offset to metadata */
 	unsigned int align;		/* Alignment */
 	unsigned int red_left_pad;	/* Left redzone padding size */

mm/slab_common.c +4 -0

index f9d89c1b5977..754acdb292e4 100644
@@ -298,6 +298,10 @@ int slab_unmergeable(struct kmem_cache *s)
 	if (!is_root_cache(s))
 		return 1;
 
+	/*
+	 * s->isolate and s->migrate imply s->ctor so no need to
+	 * check them explicitly.
+	 */
 	if (s->ctor)
 		return 1;
 

mm/slub.c +0 -0

index 69164aa7cbbf..0133168d1089 100644
@@ -4325,6 +4325,34 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4331

Quoted 4 lines

mm/slub.c +4 -0

+void kmem_cache_setup_mobility(struct kmem_cache *s,
+			       kmem_cache_isolate_func isolate,
+			       kmem_cache_migrate_func migrate)
+{

I wonder if it's better to adapt kmem_cache_create() to take two additional argument? I suspect mobility is not a dynamic option, so it can be set on kmem_cache creation.

Quoted 6 lines

mm/slub.c +0 -0

@@ -4325,6 +4325,34 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4331

Quoted 4 lines

mm/slub.c +4 -0

+void kmem_cache_setup_mobility(struct kmem_cache *s,
+			       kmem_cache_isolate_func isolate,
+			       kmem_cache_migrate_func migrate)
+{

I wonder if it's better to adapt kmem_cache_create() to take two additional argument? I suspect mobility is not a dynamic option, so it can be set on kmem_cache creation.

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4351

Quoted 4 lines

mm/slub.c +4 -0

+	/*
+	 * Sadly serialization requirements currently mean that we have
+	 * to disable fast cmpxchg based processing.
+	 */

Can you, please, elaborate a bit more here?

Quoted 6 lines · Roman Gushchin

Quoted 6 lines

mm/slub.c +0 -0

@@ -4325,6 +4325,34 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 

Quoted 8 lines

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4331

Quoted 4 lines

mm/slub.c +4 -0

+void kmem_cache_setup_mobility(struct kmem_cache *s,
+			       kmem_cache_isolate_func isolate,
+			       kmem_cache_migrate_func migrate)
+{

I wonder if it's better to adapt kmem_cache_create() to take two additional argument? I suspect mobility is not a dynamic option, so it can be set on kmem_cache creation.

One other idea that prior versions of this patchset used was to change kmem_cache_create() so that the ctor parameter becomes an ops vector.

However, in order to reduce the size of the patchset I dropped that. It could be easily moved back to the way it was before.

Quoted 7 lines

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4351

Quoted 5 lines

mm/slub.c +4 -0

+	/*
+	 * Sadly serialization requirements currently mean that we have
+	 * to disable fast cmpxchg based processing.
+	 */

Can you, please, elaborate a bit more here?

cmpxchg based processing does not lock the struct page. SMO requires to ensure that all changes on a slab page can be stopped. The page->lock will accomplish that. I think we could avoid dealing with actually locking the page with some more work.

-F lists caches that support object migration.

-C lists caches that use a ctor.

Add command line options to show caches with a constructor and caches with that are migratable (i.e. have isolate and migrate functions).

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 tools/vm/slabinfo.c | 40 ++++++++++++++++++++++++++++++++++++----
 1 file changed, 36 insertions(+), 4 deletions(-)

Quoted 1 line · Tobin C. Harding

-F lists caches that support object migration.

Maybe -M?

We have now in place a mechanism for adding callbacks to a cache in order to be able to implement object migration.

Add a function __move() that implements SMO by moving all objects in a slab page using the isolate/migrate callback methods.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slub.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)

mm/slub.c +2 -0

index 0133168d1089..6ce866b420f1 100644
@@ -4325,6 +4325,91 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 
+/*
+ * Allocate a slab scratch space that is sufficient to keep pointers to

mm/slub.c +5 -0

+}
+
+/*
+ * __move() - Move all objects in the given slab.
+ * @page: The slab we are working on.

mm/slub.c +58 -0

+	unsigned long objects;
+	struct kmem_cache *s;
+	unsigned long flags;
+	unsigned long *map;
+	void *private;
+	int count;
+	void *p;
+	void **vector = scratch;
+	void *addr = page_address(page);
+
+	local_irq_save(flags);
+	slab_lock(page);
+
+	BUG_ON(!PageSlab(page)); /* Must be s slab page */
+	BUG_ON(!page->frozen);	 /* Slab must have been frozen earlier */
+
+	s = page->slab_cache;
+	objects = page->objects;
+	map = scratch + objects * sizeof(void **);
+
+	/* Determine used objects */
+	bitmap_fill(map, objects);
+	for (p = page->freelist; p; p = get_freepointer(s, p))
+		__clear_bit(slab_index(p, s, addr), map);
+
+	/* Build vector of pointers to objects */
+	count = 0;
+	memset(vector, 0, objects * sizeof(void **));
+	for_each_object(p, s, addr, objects)
+		if (test_bit(slab_index(p, s, addr), map))
+			vector[count++] = p;
+
+	if (s->isolate)
+		private = s->isolate(s, vector, count);
+	else
+		/* Objects do not need to be isolated */
+		private = NULL;
+
+	/*
+	 * Pinned the objects. Now we can drop the slab lock. The slab
+	 * is frozen so it cannot vanish from under us nor will
+	 * allocations be performed on the slab. However, unlocking the
+	 * slab will allow concurrent slab_frees to proceed. So the
+	 * subsystem must have a way to tell from the content of the
+	 * object that it was freed.
+	 *
+	 * If neither RCU nor ctor is being used then the object may be
+	 * modified by the allocator after being freed which may disrupt
+	 * the ability of the migrate function to tell if the object is
+	 * free or not.
+	 */
+	slab_unlock(page);
+	local_irq_restore(flags);
+
+	/* Perform callback to move the objects */
+	s->migrate(s, vector, count, node, private);
+}
+
 void kmem_cache_setup_mobility(struct kmem_cache *s,
 			       kmem_cache_isolate_func isolate,
 			       kmem_cache_migrate_func migrate)

Signature · 1 line

2.21.0

Quoted 22 lines · Tobin C. Harding

We have now in place a mechanism for adding callbacks to a cache in order to be able to implement object migration.

Add a function __move() that implements SMO by moving all objects in a slab page using the isolate/migrate callback methods.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slub.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)

mm/slub.c +2 -0

index 0133168d1089..6ce866b420f1 100644
@@ -4325,6 +4325,91 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 
+/*
+ * Allocate a slab scratch space that is sufficient to keep pointers to

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4339

Quoted 10 lines

mm/slub.c +10 -0

+ * individual objects for all objects in cache and also a bitmap for the
+ * objects (used to mark which objects are active).
+ */
+static inline void *alloc_scratch(struct kmem_cache *s)
+{
+	unsigned int size = oo_objects(s->max);
+
+	return kmalloc(size * sizeof(void *) +
+		       BITS_TO_LONGS(size) * sizeof(unsigned long),
+		       GFP_KERNEL);

I wonder how big this allocation can be?
Given that the reason for migration is probably highly fragmented memory, we probably don't want to have a high-order allocation here. So maybe kvmalloc()?

Quoted 10 lines

mm/slub.c +10 -0

+}
+
+/*
+ * __move() - Move all objects in the given slab.
+ * @page: The slab we are working on.
+ * @scratch: Pointer to scratch space.
+ * @node: The target node to move objects to.
+ *
+ * If the target node is not the current node then the object is moved
+ * to the target node.  If the target node is the current node then this

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4354

Quoted 5 lines

mm/slub.c +5 -0

+ * is an effective way of defragmentation since the current slab page
+ * with its object is exempt from allocation.
+ */
+static void __move(struct page *page, void *scratch, int node)
+{

__move() isn't a very explanatory name. kmem_cache_move() (as in Christopher's version) is much better, IMO. Or maybe move_slab_objects()?

Also, it's usually better to avoid adding new functions without calling them. Maybe it's possible to merge this patch with (9)?

Quoted 49 lines · Roman Gushchin

Quoted 22 lines · Tobin C. Harding

We have now in place a mechanism for adding callbacks to a cache in order to be able to implement object migration.

Add a function __move() that implements SMO by moving all objects in a slab page using the isolate/migrate callback methods.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slub.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)

mm/slub.c +2 -0

index 0133168d1089..6ce866b420f1 100644
@@ -4325,6 +4325,91 @@ int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags)
 	return err;
 }
 
+/*
+ * Allocate a slab scratch space that is sufficient to keep pointers to

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4339

Quoted 10 lines

mm/slub.c +10 -0

+ * individual objects for all objects in cache and also a bitmap for the
+ * objects (used to mark which objects are active).
+ */
+static inline void *alloc_scratch(struct kmem_cache *s)
+{
+	unsigned int size = oo_objects(s->max);
+
+	return kmalloc(size * sizeof(void *) +
+		       BITS_TO_LONGS(size) * sizeof(unsigned long),
+		       GFP_KERNEL);

I wonder how big this allocation can be?
Given that the reason for migration is probably highly fragmented memory, we probably don't want to have a high-order allocation here. So maybe kvmalloc()?

Quoted 10 lines

mm/slub.c +10 -0

+}
+
+/*
+ * __move() - Move all objects in the given slab.
+ * @page: The slab we are working on.
+ * @scratch: Pointer to scratch space.
+ * @node: The target node to move objects to.
+ *
+ * If the target node is not the current node then the object is moved
+ * to the target node.  If the target node is the current node then this

Quoted 8 lines

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4354

Quoted 5 lines

mm/slub.c +5 -0

+ * is an effective way of defragmentation since the current slab page
+ * with its object is exempt from allocation.
+ */
+static void __move(struct page *page, void *scratch, int node)
+{

__move() isn't a very explanatory name. kmem_cache_move() (as in Christopher's version) is much better, IMO. Or maybe move_slab_objects()?

How about move_slab_page()? We use kmem_cache_move() later in the series. __move() moves all objects in the given page but not all objects in this cache (which kmem_cache_move() later does). Open to further suggestions though, naming things is hard :)

Christopher's original patch uses kmem_cache_move() for a function that only moves objects from within partial slabs, I changed it because I did not think this name suitably describes the behaviour. So from the original I rename:

	__move() -> __defrag()
	kmem_cache_move() -> __move()

And reuse kmem_cache_move() for move _all_ objects (includes full list).

With this set applied we have the call chains

kmem_cache_shrink() # Defined in slab_common.c, exported to kernel.
-> __kmem_cache_shrink() # Defined in slub.c
-> __defrag() # Unconditionally (i.e 100%)

     -> __move()

kmem_cache_defrag() # Exported to kernel
-> __defrag()
-> __move()

move_store() # sysfs
-> kmem_cache_move()
-> __move()
or
-> __move_all_objects_to()
-> kmem_cache_move()

     -> __move()

Suggested improvements?

Quoted 3 lines

Also, it's usually better to avoid adding new functions without calling them. Maybe it's possible to merge this patch with (9)?

Understood. The reason behind this is that I attempted to break this set up separating the implementation of SMO with the addition of each feature. This function is only called when features are implemented to use SMO, I did not want to elevate any feature above any other by including it in this patch. I'm open to suggestions on how to order though, also I'm happy to order it differently if/when we do PATCH version. Is that acceptable for the RFC versions?

Quoted 4 lines

mm/slub.c +4 -0

+static inline void *alloc_scratch(struct kmem_cache *s)
+{
+	unsigned int size = oo_objects(s->max);
+

mm/slub.c int __kmem_cache_create(struct kmem_cache *s, slab_flags_t flags) · line 4339

Quoted 3 lines

mm/slub.c +3 -0

+	return kmalloc(size * sizeof(void *) +
+		       BITS_TO_LONGS(size) * sizeof(unsigned long),
+		       GFP_KERNEL);

I wonder how big this allocation can be?
Given that the reason for migration is probably highly fragmented memory, we probably don't want to have a high-order allocation here. So maybe kvmalloc()?

mm/slub.c +8 -0

@@ -3642,6 +3642,7 @@ static int kmem_cache_open(struct kmem_cache *s, slab_flags_t flags)
 
 	set_cpu_partial(s);
 
+	s->defrag_used_ratio = 30;
 #ifdef CONFIG_NUMA
 	s->remote_node_defrag_ratio = 1000;
 #endif

@@ -5261,6 +5262,28 @@ static ssize_t destroy_by_rcu_show(struct kmem_cache *s, char *buf)
 }
 SLAB_ATTR_RO(destroy_by_rcu);
 
+static ssize_t defrag_used_ratio_show(struct kmem_cache *s, char *buf)
+{
+	return sprintf(buf, "%d\n", s->defrag_used_ratio);
+}
+
+static ssize_t defrag_used_ratio_store(struct kmem_cache *s,
+				       const char *buf, size_t length)

Quoted 25 lines · Tobin C. Harding

mm/slub.c +12 -0

@@ -3642,6 +3642,7 @@ static int kmem_cache_open(struct kmem_cache *s, slab_flags_t flags)
 
 	set_cpu_partial(s);
 
+	s->defrag_used_ratio = 30;
 #ifdef CONFIG_NUMA
 	s->remote_node_defrag_ratio = 1000;
 #endif

@@ -5261,6 +5262,28 @@ static ssize_t destroy_by_rcu_show(struct kmem_cache *s, char *buf)
 }
 SLAB_ATTR_RO(destroy_by_rcu);
 
+static ssize_t defrag_used_ratio_show(struct kmem_cache *s, char *buf)
+{
+	return sprintf(buf, "%d\n", s->defrag_used_ratio);
+}
+
+static ssize_t defrag_used_ratio_store(struct kmem_cache *s,
+				       const char *buf, size_t length)
+{
+	unsigned long ratio;
+	int err;
+

mm/slub.c static ssize_t destroy_by_rcu_show(struct kmem_cache *s, char *buf) · line 5281

Quoted 6 lines

mm/slub.c +6 -0

+	err = kstrtoul(buf, 10, &ratio);
+	if (err)
+		return err;
+
+	if (ratio <= 100)
+		s->defrag_used_ratio = ratio;

    else
        return -EINVAL;

If many objects are allocated with the slab allocator and freed in an arbitrary order then the slab caches can become internally fragmented. Now that the slab allocator supports movable objects we can defragment any cache that has this feature enabled.

Slab defragmentation may occur:

1. Unconditionally when __kmem_cache_shrink() is called on a slab cache by the kernel calling kmem_cache_shrink().

2. Unconditionally through the use of the slabinfo command.

slabinfo <cache> -s

3. Conditionally via the use of kmem_cache_defrag()

Use SMO when shrinking cache. Currently when the kernel calls kmem_cache_shrink() we curate the partial slabs list. If object migration is not enabled for the cache we still do this, if however SMO is enabled, we attempt to move objects in partially full slabs in order to defragment the cache. Shrink attempts to move all objects in order to reduce the cache to a single partial slab for each node.

kmem_cache_defrag() differs from shrink in that it operates dependent on the defrag_used_ratio and only attempts to move objects if the number of partial slabs exceeds MAX_PARTIAL (for each node).

Add function kmem_cache_defrag(int node).

kmem_cache_defrag() only performs defragmentation if the usage ratio of the slab is lower than the configured percentage (sysfs file added in previous patch). Fragmentation ratios are measured by calculating the percentage of objects in use compared to the total number of objects that the slab page can accommodate.

The scanning of slab caches is optimized because the defragmentable slabs come first on the list. Thus we can terminate scans on the first slab encountered that does not support defragmentation.

kmem_cache_defrag() takes a node parameter. This can either be -1 if defragmentation should be performed on all nodes, or a node number.

Defragmentation may be disabled by setting defrag ratio to 0

echo 0 > /sys/kernel/slab/<cache>/defrag_used_ratio

In order for a cache to be defragmentable the cache must support object migration (SMO). Enabling SMO for a cache is done via a call to the recently added function:

	void kmem_cache_setup_mobility(struct kmem_cache *,
				       kmem_cache_isolate_func,
			               kmem_cache_migrate_func);

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 include/linux/slab.h |   1 +
 mm/slub.c            | 266 +++++++++++++++++++++++++++++++------------
 2 files changed, 194 insertions(+), 73 deletions(-)

include/linux/slab.h +1 -0

index 22e87c41b8a4..b9b46bc9937e 100644
@@ -147,6 +147,7 @@ struct kmem_cache *kmem_cache_create_usercopy(const char *name,
 			void (*ctor)(void *));
 void kmem_cache_destroy(struct kmem_cache *);
 int kmem_cache_shrink(struct kmem_cache *);
+int kmem_cache_defrag(int node);
 
 void memcg_create_kmem_cache(struct mem_cgroup *, struct kmem_cache *);
 void memcg_deactivate_kmem_caches(struct mem_cgroup *);

mm/slub.c +12 -73

index 515db0f36c55..53dd4cb5b5a4 100644
@@ -354,6 +354,12 @@ static __always_inline void slab_lock(struct page *page)
 	bit_spin_lock(PG_locked, &page->flags);
 }
 
+static __always_inline int slab_trylock(struct page *page)
+{
+	VM_BUG_ON_PAGE(PageTail(page), page);
+	return bit_spin_trylock(PG_locked, &page->flags);
+}
+
 static __always_inline void slab_unlock(struct page *page)
 {
 	VM_BUG_ON_PAGE(PageTail(page), page);

@@ -3959,79 +3965,6 @@ void kfree(const void *x)
 }
 EXPORT_SYMBOL(kfree);
 
-#define SHRINK_PROMOTE_MAX 32
-
-/*
- * kmem_cache_shrink discards empty slabs and promotes the slabs filled
- * up most to the head of the partial lists. New allocations will then
- * fill those up and thus they can be removed from the partial lists.
- *
- * The slabs with the least items are placed last. This results in them
- * being allocated from last increasing the chance that the last objects
- * are freed in them.
- */
-int __kmem_cache_shrink(struct kmem_cache *s)
-{
-	int node;
-	int i;
-	struct kmem_cache_node *n;
-	struct page *page;
-	struct page *t;
-	struct list_head discard;
-	struct list_head promote[SHRINK_PROMOTE_MAX];
-	unsigned long flags;
-	int ret = 0;
-
-	flush_all(s);
-	for_each_kmem_cache_node(s, node, n) {
-		INIT_LIST_HEAD(&discard);
-		for (i = 0; i < SHRINK_PROMOTE_MAX; i++)
-			INIT_LIST_HEAD(promote + i);
-
-		spin_lock_irqsave(&n->list_lock, flags);
-
-		/*
-		 * Build lists of slabs to discard or promote.
-		 *
-		 * Note that concurrent frees may occur while we hold the
-		 * list_lock. page->inuse here is the upper limit.
-		 */
-		list_for_each_entry_safe(page, t, &n->partial, lru) {
-			int free = page->objects - page->inuse;
-
-			/* Do not reread page->inuse */
-			barrier();
-
-			/* We do not keep full slabs on the list */
-			BUG_ON(free <= 0);
-
-			if (free == page->objects) {
-				list_move(&page->lru, &discard);
-				n->nr_partial--;
-			} else if (free <= SHRINK_PROMOTE_MAX)
-				list_move(&page->lru, promote + free - 1);
-		}
-
-		/*
-		 * Promote the slabs filled up most to the head of the
-		 * partial list.
-		 */
-		for (i = SHRINK_PROMOTE_MAX - 1; i >= 0; i--)
-			list_splice(promote + i, &n->partial);
-
-		spin_unlock_irqrestore(&n->list_lock, flags);
-
-		/* Release empty slabs */
-		list_for_each_entry_safe(page, t, &discard, lru)
-			discard_slab(s, page);
-
-		if (slabs_node(s, node))
-			ret = 1;
-	}
-
-	return ret;
-}
-
 #ifdef CONFIG_MEMCG
 static void kmemcg_cache_deact_after_rcu(struct kmem_cache *s)
 {

@@ -4411,6 +4344,193 @@ static void __move(struct page *page, void *scratch, int node)
 	s->migrate(s, vector, count, node, private);
 }
 
+/*
+ * __defrag() - Defragment node.
+ * @s: cache we are working on.
+ * @node: The node to move objects from.
+ * @target_node: The node to move objects to.
+ * @ratio: The defrag ratio (percentage, between 0 and 100).

mm/slub.c +152 -0

+{
+	struct kmem_cache_node *n = get_node(s, node);
+	struct page *page, *page2;
+	LIST_HEAD(move_list);
+	unsigned long flags;
+
+	if (node == target_node && n->nr_partial <= 1) {
+		/*
+		 * Trying to reduce fragmentation on a node but there is
+		 * only a single or no partial slab page. This is already
+		 * the optimal object density that we can reach.
+		 */
+		return n->nr_partial;
+	}
+
+	spin_lock_irqsave(&n->list_lock, flags);
+	list_for_each_entry_safe(page, page2, &n->partial, lru) {
+		if (!slab_trylock(page))
+			/* Busy slab. Get out of the way */
+			continue;
+
+		if (page->inuse) {
+			if (page->inuse > ratio * page->objects / 100) {
+				slab_unlock(page);
+				/*
+				 * Skip slab because the object density
+				 * in the slab page is high enough.
+				 */
+				continue;
+			}
+
+			list_move(&page->lru, &move_list);
+			if (s->migrate) {
+				/* Stop page being considered for allocations */
+				n->nr_partial--;
+				page->frozen = 1;
+			}
+			slab_unlock(page);
+		} else {	/* Empty slab page */
+			list_del(&page->lru);
+			n->nr_partial--;
+			slab_unlock(page);
+			discard_slab(s, page);
+		}
+	}
+
+	if (!s->migrate) {
+		/*
+		 * No defrag method. By simply putting the zaplist at the
+		 * end of the partial list we can let them simmer longer
+		 * and thus increase the chance of all objects being
+		 * reclaimed.
+		 *
+		 */
+		list_splice(&move_list, n->partial.prev);
+	}
+
+	spin_unlock_irqrestore(&n->list_lock, flags);
+
+	if (s->migrate && !list_empty(&move_list)) {
+		void **scratch = alloc_scratch(s);
+		struct page *page, *page2;
+
+		if (scratch) {
+			/* Try to remove / move the objects left */
+			list_for_each_entry(page, &move_list, lru) {
+				if (page->inuse)
+					__move(page, scratch, target_node);
+			}
+			kfree(scratch);
+		}
+
+		/* Inspect results and dispose of pages */
+		spin_lock_irqsave(&n->list_lock, flags);
+		list_for_each_entry_safe(page, page2, &move_list, lru) {
+			list_del(&page->lru);
+			slab_lock(page);
+			page->frozen = 0;
+
+			if (page->inuse) {
+				/*
+				 * Objects left in slab page, move it to the
+				 * tail of the partial list to increase the
+				 * chance that the freeing of the remaining
+				 * objects will free the slab page.
+				 */
+				n->nr_partial++;
+				list_add_tail(&page->lru, &n->partial);
+				slab_unlock(page);
+			} else {
+				slab_unlock(page);
+				discard_slab(s, page);
+			}
+		}
+		spin_unlock_irqrestore(&n->list_lock, flags);
+	}
+
+	return n->nr_partial;
+}
+
+/**
+ * kmem_cache_defrag() - Defrag slab caches.
+ * @node: The node to defrag or -1 for all nodes.
+ *
+ * Defrag slabs conditional on the amount of fragmentation in a page.
+ */
+int kmem_cache_defrag(int node)
+{
+	struct kmem_cache *s;
+	unsigned long left = 0;
+
+	/*
+	 * kmem_cache_defrag may be called from the reclaim path which may be
+	 * called for any page allocator alloc. So there is the danger that we
+	 * get called in a situation where slub already acquired the slub_lock
+	 * for other purposes.
+	 */
+	if (!mutex_trylock(&slab_mutex))
+		return 0;
+
+	list_for_each_entry(s, &slab_caches, list) {
+		/*
+		 * Defragmentable caches come first. If the slab cache is not
+		 * defragmentable then we can stop traversing the list.
+		 */
+		if (!s->migrate)
+			break;
+
+		if (node == -1) {
+			int nid;
+
+			for_each_node_state(nid, N_NORMAL_MEMORY)
+				if (s->node[nid]->nr_partial > MAX_PARTIAL)
+					left += __defrag(s, nid, nid, s->defrag_used_ratio);
+		} else {
+			if (s->node[node]->nr_partial > MAX_PARTIAL)
+				left += __defrag(s, node, node, s->defrag_used_ratio);
+		}
+	}
+	mutex_unlock(&slab_mutex);
+	return left;
+}
+EXPORT_SYMBOL(kmem_cache_defrag);
+
+/**
+ * __kmem_cache_shrink() - Shrink a cache.
+ * @s: The cache to shrink.
+ *
+ * Reduces the memory footprint of a slab cache by as much as possible.
+ *
+ * This works by:
+ *  1. Removing empty slabs from the partial list.

Quoted 180 lines · Tobin C. Harding

If many objects are allocated with the slab allocator and freed in an arbitrary order then the slab caches can become internally fragmented. Now that the slab allocator supports movable objects we can defragment any cache that has this feature enabled.

Slab defragmentation may occur:

1. Unconditionally when __kmem_cache_shrink() is called on a slab cache by the kernel calling kmem_cache_shrink().

2. Unconditionally through the use of the slabinfo command.

slabinfo <cache> -s

3. Conditionally via the use of kmem_cache_defrag()

Use SMO when shrinking cache. Currently when the kernel calls kmem_cache_shrink() we curate the partial slabs list. If object migration is not enabled for the cache we still do this, if however SMO is enabled, we attempt to move objects in partially full slabs in order to defragment the cache. Shrink attempts to move all objects in order to reduce the cache to a single partial slab for each node.

kmem_cache_defrag() differs from shrink in that it operates dependent on the defrag_used_ratio and only attempts to move objects if the number of partial slabs exceeds MAX_PARTIAL (for each node).

Add function kmem_cache_defrag(int node).

kmem_cache_defrag() only performs defragmentation if the usage ratio of the slab is lower than the configured percentage (sysfs file added in previous patch). Fragmentation ratios are measured by calculating the percentage of objects in use compared to the total number of objects that the slab page can accommodate.

The scanning of slab caches is optimized because the defragmentable slabs come first on the list. Thus we can terminate scans on the first slab encountered that does not support defragmentation.

kmem_cache_defrag() takes a node parameter. This can either be -1 if defragmentation should be performed on all nodes, or a node number.

Defragmentation may be disabled by setting defrag ratio to 0

echo 0 > /sys/kernel/slab/<cache>/defrag_used_ratio

In order for a cache to be defragmentable the cache must support object migration (SMO). Enabling SMO for a cache is done via a call to the recently added function:

	void kmem_cache_setup_mobility(struct kmem_cache *,
				       kmem_cache_isolate_func,
			               kmem_cache_migrate_func);

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 include/linux/slab.h |   1 +
 mm/slub.c            | 266 +++++++++++++++++++++++++++++++------------
 2 files changed, 194 insertions(+), 73 deletions(-)

include/linux/slab.h +1 -0

index 22e87c41b8a4..b9b46bc9937e 100644
@@ -147,6 +147,7 @@ struct kmem_cache *kmem_cache_create_usercopy(const char *name,
 			void (*ctor)(void *));
 void kmem_cache_destroy(struct kmem_cache *);
 int kmem_cache_shrink(struct kmem_cache *);
+int kmem_cache_defrag(int node);
 
 void memcg_create_kmem_cache(struct mem_cgroup *, struct kmem_cache *);
 void memcg_deactivate_kmem_caches(struct mem_cgroup *);

mm/slub.c +12 -73

index 515db0f36c55..53dd4cb5b5a4 100644
@@ -354,6 +354,12 @@ static __always_inline void slab_lock(struct page *page)
 	bit_spin_lock(PG_locked, &page->flags);
 }
 
+static __always_inline int slab_trylock(struct page *page)
+{
+	VM_BUG_ON_PAGE(PageTail(page), page);
+	return bit_spin_trylock(PG_locked, &page->flags);
+}
+
 static __always_inline void slab_unlock(struct page *page)
 {
 	VM_BUG_ON_PAGE(PageTail(page), page);

@@ -3959,79 +3965,6 @@ void kfree(const void *x)
 }
 EXPORT_SYMBOL(kfree);
 
-#define SHRINK_PROMOTE_MAX 32
-
-/*
- * kmem_cache_shrink discards empty slabs and promotes the slabs filled
- * up most to the head of the partial lists. New allocations will then
- * fill those up and thus they can be removed from the partial lists.
- *
- * The slabs with the least items are placed last. This results in them
- * being allocated from last increasing the chance that the last objects
- * are freed in them.
- */
-int __kmem_cache_shrink(struct kmem_cache *s)
-{
-	int node;
-	int i;
-	struct kmem_cache_node *n;
-	struct page *page;
-	struct page *t;
-	struct list_head discard;
-	struct list_head promote[SHRINK_PROMOTE_MAX];
-	unsigned long flags;
-	int ret = 0;
-
-	flush_all(s);
-	for_each_kmem_cache_node(s, node, n) {
-		INIT_LIST_HEAD(&discard);
-		for (i = 0; i < SHRINK_PROMOTE_MAX; i++)
-			INIT_LIST_HEAD(promote + i);
-
-		spin_lock_irqsave(&n->list_lock, flags);
-
-		/*
-		 * Build lists of slabs to discard or promote.
-		 *
-		 * Note that concurrent frees may occur while we hold the
-		 * list_lock. page->inuse here is the upper limit.
-		 */
-		list_for_each_entry_safe(page, t, &n->partial, lru) {
-			int free = page->objects - page->inuse;
-
-			/* Do not reread page->inuse */
-			barrier();
-
-			/* We do not keep full slabs on the list */
-			BUG_ON(free <= 0);
-
-			if (free == page->objects) {
-				list_move(&page->lru, &discard);
-				n->nr_partial--;
-			} else if (free <= SHRINK_PROMOTE_MAX)
-				list_move(&page->lru, promote + free - 1);
-		}
-
-		/*
-		 * Promote the slabs filled up most to the head of the
-		 * partial list.
-		 */
-		for (i = SHRINK_PROMOTE_MAX - 1; i >= 0; i--)
-			list_splice(promote + i, &n->partial);
-
-		spin_unlock_irqrestore(&n->list_lock, flags);
-
-		/* Release empty slabs */
-		list_for_each_entry_safe(page, t, &discard, lru)
-			discard_slab(s, page);
-
-		if (slabs_node(s, node))
-			ret = 1;
-	}
-
-	return ret;
-}
-
 #ifdef CONFIG_MEMCG
 static void kmemcg_cache_deact_after_rcu(struct kmem_cache *s)
 {

@@ -4411,6 +4344,193 @@ static void __move(struct page *page, void *scratch, int node)
 	s->migrate(s, vector, count, node, private);
 }
 
+/*
+ * __defrag() - Defragment node.
+ * @s: cache we are working on.
+ * @node: The node to move objects from.
+ * @target_node: The node to move objects to.
+ * @ratio: The defrag ratio (percentage, between 0 and 100).

mm/slub.c static void __move(struct page *page, void *scratch, int node) · line 4362

Quoted 10 lines

mm/slub.c +10 -0

+ *
+ * Release slabs with zero objects and try to call the migration function
+ * for slabs with less than the 'ratio' percentage of objects allocated.
+ *
+ * Moved objects are allocated on @target_node.
+ *
+ * Return: The number of partial slabs left on the node after the operation.
+ */
+static unsigned long __defrag(struct kmem_cache *s, int node, int target_node,
+			      int ratio)

Maybe kmem_cache_defrag_node()?

Quoted 156 lines

mm/slub.c +156 -0

+{
+	struct kmem_cache_node *n = get_node(s, node);
+	struct page *page, *page2;
+	LIST_HEAD(move_list);
+	unsigned long flags;
+
+	if (node == target_node && n->nr_partial <= 1) {
+		/*
+		 * Trying to reduce fragmentation on a node but there is
+		 * only a single or no partial slab page. This is already
+		 * the optimal object density that we can reach.
+		 */
+		return n->nr_partial;
+	}
+
+	spin_lock_irqsave(&n->list_lock, flags);
+	list_for_each_entry_safe(page, page2, &n->partial, lru) {
+		if (!slab_trylock(page))
+			/* Busy slab. Get out of the way */
+			continue;
+
+		if (page->inuse) {
+			if (page->inuse > ratio * page->objects / 100) {
+				slab_unlock(page);
+				/*
+				 * Skip slab because the object density
+				 * in the slab page is high enough.
+				 */
+				continue;
+			}
+
+			list_move(&page->lru, &move_list);
+			if (s->migrate) {
+				/* Stop page being considered for allocations */
+				n->nr_partial--;
+				page->frozen = 1;
+			}
+			slab_unlock(page);
+		} else {	/* Empty slab page */
+			list_del(&page->lru);
+			n->nr_partial--;
+			slab_unlock(page);
+			discard_slab(s, page);
+		}
+	}
+
+	if (!s->migrate) {
+		/*
+		 * No defrag method. By simply putting the zaplist at the
+		 * end of the partial list we can let them simmer longer
+		 * and thus increase the chance of all objects being
+		 * reclaimed.
+		 *
+		 */
+		list_splice(&move_list, n->partial.prev);
+	}
+
+	spin_unlock_irqrestore(&n->list_lock, flags);
+
+	if (s->migrate && !list_empty(&move_list)) {
+		void **scratch = alloc_scratch(s);
+		struct page *page, *page2;
+
+		if (scratch) {
+			/* Try to remove / move the objects left */
+			list_for_each_entry(page, &move_list, lru) {
+				if (page->inuse)
+					__move(page, scratch, target_node);
+			}
+			kfree(scratch);
+		}
+
+		/* Inspect results and dispose of pages */
+		spin_lock_irqsave(&n->list_lock, flags);
+		list_for_each_entry_safe(page, page2, &move_list, lru) {
+			list_del(&page->lru);
+			slab_lock(page);
+			page->frozen = 0;
+
+			if (page->inuse) {
+				/*
+				 * Objects left in slab page, move it to the
+				 * tail of the partial list to increase the
+				 * chance that the freeing of the remaining
+				 * objects will free the slab page.
+				 */
+				n->nr_partial++;
+				list_add_tail(&page->lru, &n->partial);
+				slab_unlock(page);
+			} else {
+				slab_unlock(page);
+				discard_slab(s, page);
+			}
+		}
+		spin_unlock_irqrestore(&n->list_lock, flags);
+	}
+
+	return n->nr_partial;
+}
+
+/**
+ * kmem_cache_defrag() - Defrag slab caches.
+ * @node: The node to defrag or -1 for all nodes.
+ *
+ * Defrag slabs conditional on the amount of fragmentation in a page.
+ */
+int kmem_cache_defrag(int node)
+{
+	struct kmem_cache *s;
+	unsigned long left = 0;
+
+	/*
+	 * kmem_cache_defrag may be called from the reclaim path which may be
+	 * called for any page allocator alloc. So there is the danger that we
+	 * get called in a situation where slub already acquired the slub_lock
+	 * for other purposes.
+	 */
+	if (!mutex_trylock(&slab_mutex))
+		return 0;
+
+	list_for_each_entry(s, &slab_caches, list) {
+		/*
+		 * Defragmentable caches come first. If the slab cache is not
+		 * defragmentable then we can stop traversing the list.
+		 */
+		if (!s->migrate)
+			break;
+
+		if (node == -1) {
+			int nid;
+
+			for_each_node_state(nid, N_NORMAL_MEMORY)
+				if (s->node[nid]->nr_partial > MAX_PARTIAL)
+					left += __defrag(s, nid, nid, s->defrag_used_ratio);
+		} else {
+			if (s->node[node]->nr_partial > MAX_PARTIAL)
+				left += __defrag(s, node, node, s->defrag_used_ratio);
+		}
+	}
+	mutex_unlock(&slab_mutex);
+	return left;
+}
+EXPORT_SYMBOL(kmem_cache_defrag);
+
+/**
+ * __kmem_cache_shrink() - Shrink a cache.
+ * @s: The cache to shrink.
+ *
+ * Reduces the memory footprint of a slab cache by as much as possible.
+ *
+ * This works by:
+ *  1. Removing empty slabs from the partial list.
+ *  2. Migrating slab objects to denser slab pages if the slab cache
+ *  supports migration.  If not, reorganizing the partial list so that
+ *  more densely allocated slab pages come first.
+ *

mm/slub.c static void __move(struct page *page, void *scratch, int node) · line 4524

Quoted 6 lines

mm/slub.c +6 -0

+ * Not called directly, called by kmem_cache_shrink().
+ */
+int __kmem_cache_shrink(struct kmem_cache *s)
+{
+	int node;
+	int left = 0;

s/int/unsigned long? Or s/unsigned long/int in __defrag()?

Implement functions to migrate objects. This is based on initial code by Matthew Wilcox and was modified to work with slab object migration.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 lib/radix-tree.c | 13 +++++++++++++
 lib/xarray.c     | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

lib/radix-tree.c +13 -0

index 14d51548bea6..9412c2853726 100644
@@ -1613,6 +1613,17 @@ static int radix_tree_cpu_dead(unsigned int cpu)
 	return 0;
 }
 
+extern void xa_object_migrate(void *tree_node, int numa_node);
+
+static void radix_tree_migrate(struct kmem_cache *s, void **objects, int nr,
+			       int node, void *private)
+{
+	int i;
+
+	for (i = 0; i < nr; i++)
+		xa_object_migrate(objects[i], node);
+}
+
 void __init radix_tree_init(void)
 {
 	int ret;

@@ -1627,4 +1638,6 @@ void __init radix_tree_init(void)
 	ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
 					NULL, radix_tree_cpu_dead);
 	WARN_ON(ret < 0);
+	kmem_cache_setup_mobility(radix_tree_node_cachep, NULL,
+				  radix_tree_migrate);
 }

lib/xarray.c +0 -0

index 81c3171ddde9..4f6f17c87769 100644
@@ -1950,6 +1950,50 @@ void xa_destroy(struct xarray *xa)
 }
 EXPORT_SYMBOL(xa_destroy);
 

Quoted 48 lines · Tobin C. Harding

Implement functions to migrate objects. This is based on initial code by Matthew Wilcox and was modified to work with slab object migration.

Co-developed-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

---
 lib/radix-tree.c | 13 +++++++++++++
 lib/xarray.c     | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

lib/radix-tree.c +13 -0

index 14d51548bea6..9412c2853726 100644
@@ -1613,6 +1613,17 @@ static int radix_tree_cpu_dead(unsigned int cpu)
 	return 0;
 }
 
+extern void xa_object_migrate(void *tree_node, int numa_node);
+
+static void radix_tree_migrate(struct kmem_cache *s, void **objects, int nr,
+			       int node, void *private)
+{
+	int i;
+
+	for (i = 0; i < nr; i++)
+		xa_object_migrate(objects[i], node);
+}
+
 void __init radix_tree_init(void)
 {
 	int ret;

@@ -1627,4 +1638,6 @@ void __init radix_tree_init(void)
 	ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
 					NULL, radix_tree_cpu_dead);
 	WARN_ON(ret < 0);
+	kmem_cache_setup_mobility(radix_tree_node_cachep, NULL,
+				  radix_tree_migrate);
 }

lib/xarray.c +0 -0

index 81c3171ddde9..4f6f17c87769 100644
@@ -1950,6 +1950,50 @@ void xa_destroy(struct xarray *xa)
 }
 EXPORT_SYMBOL(xa_destroy);
 

lib/xarray.c void xa_destroy(struct xarray *xa) · line 1962

Quoted 10 lines

lib/xarray.c +10 -0

+void xa_object_migrate(struct xa_node *node, int numa_node)
+{
+	struct xarray *xa = READ_ONCE(node->array);
+	void __rcu **slot;
+	struct xa_node *new_node;
+	int i;
+
+	/* Freed or not yet in tree then skip */
+	if (!xa || xa == XA_FREE_MARK)
+		return;

XA_FREE_MARK is equal to 0, so the second check is redundant.

#define XA_MARK_0 ((__force xa_mark_t)0U)
#define XA_MARK_1 ((__force xa_mark_t)1U)
#define XA_MARK_2 ((__force xa_mark_t)2U)
#define XA_PRESENT ((__force xa_mark_t)8U)
#define XA_MARK_MAX XA_MARK_2
#define XA_FREE_MARK XA_MARK_0

xa_node_free() sets node->array to XA_RCU_FREE, so maybe it's what you need. I'm not sure however, Matthew should know better

lib/xarray.c void xa_destroy(struct xarray *xa) · line 1965

Quoted 3 lines

lib/xarray.c +3 -0

+
+	new_node = kmem_cache_alloc_node(radix_tree_node_cachep,
+					 GFP_KERNEL, numa_node);

We need to check here if the allocation was successful.

Hi,

Here is a patch set implementing movable objects within the SLUB allocator. This is work based on Christopher's patch set:

https://lore.kernel.org/patchwork/project/lkml/list/?series=377335

The original code logic is from that set and implemented by Christopher. Clean up, refactoring, documentation, and additional features by myself. Blame for any bugs remaining falls solely with myself. Patches using Christopher's code use the Co-developed-by tag.

After movable objects are implemented a number of useful features become possible. Some of these are implemented in this series, including:

- Cache defragmentation.

Currently the SLUB allocator is susceptible to internal fragmentation. This occurs when a large number of cached objects are allocated and then freed in an arbitrary order. As the cache fragments the number of pages used by the partial slabs list increases. This wastes memory.

Patch set implements the machinery to facilitate conditional cache defragmentation (via kmem_cache_defrag()) and unconditional defragmentation (via kmem_cache_shrink()). Various sysfs knobs are provided to interact with and configure this.

Patch set implements movable objects and cache defragmentation for the XArray.

- Moving objects to and from a specific NUMA node.

- Balancing objects across all NUMA nodes.

We add a test module to facilitate playing around with movable objects and a python test suite that uses the module.

Everything except the NUMA stuff was tested on bare metal, the NUMA stuff was tested with Qemu NUMA emulation.

Possible further work:

1. Implementing movable objects for the inode and dentry caches.

2. Tying into the page migration and page defragmentation logic so that so far unmovable pages that are in the way of creating a contiguous block of memory will become movable. This would mean checking for slab pages in the migration logic and calling slab to see if it can move the page by migrating all objects.

Quoted 43 lines · Tobin C. Harding

Hi,

Here is a patch set implementing movable objects within the SLUB allocator. This is work based on Christopher's patch set:

https://lore.kernel.org/patchwork/project/lkml/list/?series=377335

The original code logic is from that set and implemented by Christopher. Clean up, refactoring, documentation, and additional features by myself. Blame for any bugs remaining falls solely with myself. Patches using Christopher's code use the Co-developed-by tag.

After movable objects are implemented a number of useful features become possible. Some of these are implemented in this series, including:

- Cache defragmentation.

Currently the SLUB allocator is susceptible to internal fragmentation. This occurs when a large number of cached objects are allocated and then freed in an arbitrary order. As the cache fragments the number of pages used by the partial slabs list increases. This wastes memory.

Patch set implements the machinery to facilitate conditional cache defragmentation (via kmem_cache_defrag()) and unconditional defragmentation (via kmem_cache_shrink()). Various sysfs knobs are provided to interact with and configure this.

Patch set implements movable objects and cache defragmentation for the XArray.

- Moving objects to and from a specific NUMA node.

- Balancing objects across all NUMA nodes.

We add a test module to facilitate playing around with movable objects and a python test suite that uses the module.

Everything except the NUMA stuff was tested on bare metal, the NUMA stuff was tested with Qemu NUMA emulation.

Possible further work:

Quoted 7 lines

1. Implementing movable objects for the inode and dentry caches.

2. Tying into the page migration and page defragmentation logic so that so far unmovable pages that are in the way of creating a contiguous block of memory will become movable. This would mean checking for slab pages in the migration logic and calling slab to see if it can move the page by migrating all objects.

Hi Tobin!

Very interesting and promising patchset! Looking forward for inode/dentry moving support, might be a big deal for allocating huge pages dynamically.