slub: Fallback to kmalloc_large for failing higher order allocs

We can use that handoff to avoid failing if a higher order kmalloc slab allocation cannot be satisfied by the page allocator. If we reach the out of memory path then simply try a kmalloc_large(). kfree() can already handle the case of an object that was allocated via the page allocator and so this will work just fine (apart from object accounting...).

Slub already has two ways of allocating an object. One is via its own
logic and the other is via the call to kmalloc_large to hand of object allocation to the page allocator. kmalloc_large is typically used for objects >= PAGE_SIZE.

We can use that handoff to avoid failing if a higher order kmalloc slab allocation cannot be satisfied by the page allocator. If we reach the out of memory path then simply try a kmalloc_large(). kfree() can already handle the case of an object that was allocated via the page allocator and so this will work just fine (apart from object accounting...).

Quoted 6 lines

We can use that handoff to avoid failing if a higher order kmalloc slab allocation cannot be satisfied by the page allocator. If we reach the out of memory path then simply try a kmalloc_large(). kfree() can already handle the case of an object that was allocated via the page allocator and so this will work just fine (apart from object accounting...).

Sorry, I didn't follow the discussion close enough. Why are we doing this? Is it fixing some real bug I am not aware of?

Slub already has two ways of allocating an object. One is via its own logic and the other is via the call to kmalloc_large to hand of object allocation to the page allocator. kmalloc_large is typically used for objects >= PAGE_SIZE.

We can use that handoff to avoid failing if a higher order kmalloc slab allocation cannot be satisfied by the page allocator. If we reach the out of memory path then simply try a kmalloc_large(). kfree() can already handle the case of an object that was allocated via the page allocator and so this will work just fine (apart from object accounting...).

For any kmalloc slab that already requires higher order allocs (which makes it impossible to use the page allocator fastpath!) we just use PAGE_ALLOC_COSTLY_ORDER to get the largest number of objects in one go from the page allocator slowpath.

On a 4k platform this patch will lead to the following use of higher order pages for the following kmalloc slabs:

8 ... 1024 order 0
2048 .. 4096 order 3 (4k slab only after the next patch)

We may waste some space if fallback occurs on a 2k slab but we are always able to fallback to an order 0 alloc. I hope that satisfies Nick's concerns?

Signed-off-by Christoph Lameter <[email protected]>

---
 mm/slub.c |   43 ++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 38 insertions(+), 5 deletions(-)

Index: linux-2.6/mm/slub.c
===================================================================

mm/slub.c +21 -4

@@ -211,6 +211,8 @@ static inline void ClearSlabDebug(struct
 /* Internal SLUB flags */
 #define __OBJECT_POISON		0x80000000 /* Poison object */
 #define __SYSFS_ADD_DEFERRED	0x40000000 /* Not yet visible via sysfs */
+#define __KMALLOC_CACHE		0x20000000 /* objects freed using kfree */
+#define __PAGE_ALLOC_FALLBACK	0x10000000 /* Allow fallback to page alloc */
 
 /* Not all arches define cache_line_size */
 #ifndef cache_line_size

@@ -1539,7 +1541,6 @@ load_freelist:
 unlock_out:
 	slab_unlock(c->page);
 	stat(c, ALLOC_SLOWPATH);
-out:
 #ifdef SLUB_FASTPATH
 	local_irq_restore(flags);
 #endif

@@ -1574,8 +1575,24 @@ new_slab:
 		c->page = new;
 		goto load_freelist;
 	}
-	object = NULL;
-	goto out;
+#ifdef SLUB_FASTPATH
+	local_irq_restore(flags);
+#endif
+	/*
+	 * No memory available.
+	 *
+	 * If the slab uses higher order allocs but the object is
+	 * smaller than a page size then we can fallback in emergencies
+	 * to the page allocator via kmalloc_large. The page allocator may
+	 * have failed to obtain a higher order page and we can try to
+	 * allocate a single page if the object fits into a single page.
+	 * That is only possible if certain conditions are met that are being
+	 * checked when a slab is created.
+	 */
+	if (!(gfpflags & __GFP_THISNODE) && (s->flags & __PAGE_ALLOC_FALLBACK))
+		return kmalloc_large(s->objsize, gfpflags);
+
+	return NULL;
 debug:
 	object = c->page->freelist;
 	if (!alloc_debug_processing(s, c->page, object, addr))

@@ -2322,7 +2339,20 @@ static int calculate_sizes(struct kmem_c
 	size = ALIGN(size, align);
 	s->size = size;
 
-	s->order = calculate_order(size);
+	if ((flags & __KMALLOC_CACHE) &&

mm/slub.c +7 -1

+	} else
+		s->order = calculate_order(size);
+
 	if (s->order < 0)
 		return 0;
 

@@ -2539,7 +2569,7 @@ static struct kmem_cache *create_kmalloc
 
 	down_write(&slub_lock);
 	if (!kmem_cache_open(s, gfp_flags, name, size, ARCH_KMALLOC_MINALIGN,
-			flags, NULL))
+			flags | __KMALLOC_CACHE, NULL))
 		goto panic;
 
 	list_add(&s->list, &slab_caches);

@@ -3058,6 +3088,9 @@ static int slab_unmergeable(struct kmem_
 	if (slub_nomerge || (s->flags & SLUB_NEVER_MERGE))
 		return 1;
 
+	if ((s->flags & __PAGE_ALLOC_FALLBACK)
+		return 1;
+
 	if (s->ctor)
 		return 1;
 

Signature · 1 line

-- 

comments with a grain of salt. But, if a kmalloc slab allocation fails and it ultimately uses the page allocator, I do not see how calling the page allocator directly makes a difference.

The kmalloc slab allocation will use order 3. The allocation for an individual object via the page allocator only uses order 0. The order 0 alloc will succeed even if memory is extremely fragmented. Its a safety valve that Nick probably finds important.

Quoted 4 lines · Christoph Lameter

The kmalloc slab allocation will use order 3. The allocation for an individual object via the page allocator only uses order 0. The order 0 alloc will succeed even if memory is extremely fragmented. Its a safety valve that Nick probably finds important.

Hmm, shouldn't we then fix just fix calculate_order() to not try so hard to find better fitting higher orders?

That would mean reducing the number of objects that can be allocated from the fastpath before we have to go to the page allocator again. Increasing the number of fastpath uses vs slowpath increases the overall performance of a slab.

If we would use order 0 slab allocs for 4k slabs then every call to slab_alloc would lead to a corresponding call to the page allocator. The regression would not be fixed. We just add slab_alloc overhead to an already bad page allocator call.

Aah, I see. I wonder if we can fix up allocate_slab() to try with a smaller order as long as the size allows that? The only problem I can see is s->objects but I think we can just move that to be a per-slab variable. So sort of variable-order slabs kind of a thing.

Quoted 4 lines

Aah, I see. I wonder if we can fix up allocate_slab() to try with a smaller order as long as the size allows that? The only problem I can see is s->objects but I think we can just move that to be a per-slab variable. So sort of variable-order slabs kind of a thing.

Urgh. This is going to require a count of the maximum number of objects per individual slab page. Adds more overhead to the fast path and means that not all the slabs may have the same order. Which may in turn result in a mix of order 3 2 1 pages. Not good for fragmentation. I think the do order 3 always and then order 0 if we are in a bad fragmentation state the best compromise. In particular because these bad fragmented memory scenarios seems to be very difficult to produce and occur only in specialized situations (f.e. minimal ram with lots of page pinned by I/O, stuff like that).

Reviewed-by Pekka Enberg <[email protected]>

to this patch and the kmem_cache_alloc equivalent (which you might as well fold into one patch).

I would like to merge this patch into 2.6.25 and keep the other for mm to maybe merge in 2.6.26. Not sure how safe the general use of the fallback is. Definitely no problem for the kmalloc array.

This is the same trick as done by the hugetlb support in the kernel. If we allocate a huge page use __GFP_MOVABLE because an allocation of a HUGE_PAGE size is the large allocation unit that cannot cause fragmentation.

This will make a system that was booted with

slub_min_order = 9

not have any reclaimable slab allocations anymore. All slab allocations will be of type MOVABLE (although they are not movable like huge pages are also not movable). This means that we only have MOVABLE and UNMOVABLE sections of memory which reduces the types of sections and therefore the danger of fragmenting memory.

Quoted 4 lines

This will make a system that was booted with

slub_min_order = 9

Quoted 5 lines

not have any reclaimable slab allocations anymore. All slab allocations will be of type MOVABLE (although they are not movable like huge pages are also not movable). This means that we only have MOVABLE and UNMOVABLE sections of memory which reduces the types of sections and therefore the danger of fragmenting memory.

Why does slub_min_order=9 matter? I suppose this is fixing some other real bug?

This is the same trick as done by the hugetlb support in the kernel.
If we allocate a huge page use __GFP_MOVABLE because an allocation of a HUGE_PAGE size is the large allocation unit that cannot cause fragmentation.

This will make a system that was booted with

slub_min_order = 9

not have any reclaimable slab allocations anymore. All slab allocations will be of type MOVABLE (although they are not movable like huge pages are also not movable). This means that we only have MOVABLE and UNMOVABLE sections of memory which reduces the types of sections and therefore the danger of fragmenting memory.

Why does slub_min_order=9 matter? I suppose this is fixing some other real bug?

This is the same trick as done by the hugetlb support in the kernel. If we allocate a huge page use __GFP_MOVABLE because an allocation of a HUGE_PAGE size is the large allocation unit that cannot cause fragmentation.

This will make a system that was booted with

slub_min_order = 9

not have any reclaimable slab allocations anymore. All slab allocations will be of type MOVABLE (although they are not movable like huge pages are also not movable). This means that we only have MOVABLE and UNMOVABLE sections of memory which reduces the types of sections and therefore the danger of fragmenting memory.

Signed-off-by Christoph Lameter <[email protected]>

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

Index: linux-2.6/mm/slub.c
===================================================================

mm/slub.c +4 -0

@@ -2363,6 +2363,10 @@ static int calculate_sizes(struct kmem_c
 	if (s->flags & SLAB_CACHE_DMA)
 		s->allocflags |= SLUB_DMA;
 
+	if (s->order && s->order == get_order(HPAGE_SIZE))
+		/* Huge pages are always allocated as movable */
+		s->allocflags |= __GFP_MOVABLE;
+	else
 	if (s->flags & SLAB_RECLAIM_ACCOUNT)
 		s->allocflags |= __GFP_RECLAIMABLE;
 

Signature · 1 line

-- 

The only reason to have an allocation like this set as MOVABLE is so it can make use of the partition created by movablecore= which has a few specific purposes. One of them is that on a shared system, a partition can be created that is of the same size as the largest hugepage pool required for any job. As jobs run, they can grow or shrink the pool as desired. When the jobs complete, the hugepages are no longer in use and the partition becomes essentially free.

SLAB pages do not have the same property. Even with all processes exited, there will be slab allocations lying around, probably in this partition preventing the hugepage pool being resized (or memory hot-remove for that matter which can work on a section-boundary on POWER).

If the administrator has created a partition for memory hot-remove or for having a known quantity when resizing the hugepage pool, it is unlikely they want SLAB pages to be allocated from the same place putting a spanner in the works. Without the partition and slub_min_order==hugepage_size, this patch does nothing so;

NACK.

Quoted 7 lines

The only reason to have an allocation like this set as MOVABLE is so it can make use of the partition created by movablecore= which has a few specific purposes. One of them is that on a shared system, a partition can be created that is of the same size as the largest hugepage pool required for any job. As jobs run, they can grow or shrink the pool as desired. When the jobs complete, the hugepages are no longer in use and the partition becomes essentially free.

Doesnt it mean that the allocations can occur in MAX_ORDER blocks marked MOVABLE?

I thought movablecore= is no longer necessary after the rest of the antifrag stuff was merged?

Quoted 4 lines

SLAB pages do not have the same property. Even with all processes exited, there will be slab allocations lying around, probably in this partition preventing the hugepage pool being resized (or memory hot-remove for that matter which can work on a section-boundary on POWER).

echo 2 >/proc/sys/vm/drop_cache will usually allow a significant shrinkage of the slab caches. In many ways it is the same.

Quoted 7 lines

If the administrator has created a partition for memory hot-remove or for having a known quantity when resizing the hugepage pool, it is unlikely they want SLAB pages to be allocated from the same place putting a spanner in the works. Without the partition and slub_min_order==hugepage_size, this patch does nothing so;

NACK.

This is a feature enabled by a special command line boot option. So its something that the admin did *intentionally*.

Slab allocation will *not*
take away from the huge page pool but will take pages from the page allocator.

A system with huge amounts of memory has a large amount of huge pages. It is typically at this point to have 4G per cpu in a system and we may go higher. 4G means up to 2048 huge pages per cpu! Huge page allocation will be quite common and its good to reduce page allocator overhead.

Quoted 2 lines

Doesnt it mean that the allocations can occur in MAX_ORDER blocks marked MOVABLE?

Blocks aren't MAX_ORDER in size, they are pageblock_order in size and that value can be thought of as HUGETLB_PAGE_ORDER. No matter what you mark them as, it is still one pageblock. If you leave them as RECLAIMABLE or UNMOVABLE, a MOVABLE block may still get reclaimed and given to slab instead without this patch. Marking them movable when no partition exists gains nothing at all.

Quoted 3 lines

echo 2 >/proc/sys/vm/drop_cache will usually allow a significant shrinkage of the slab caches. In many ways it is the same.

Except it doesn't work for all slabs. As part of the highorder allocation stress tests I run, a final part is allocating pages when no other process is running and /proc/sys/vm/drop_cache has been used. There are still remaining pages left in odd places.

Quoted 2 lines

This is a feature enabled by a special command line boot option. So its something that the admin did *intentionally*.

Not quite. What he asked for is that slub_min_order=HUGE_PAGESIZE, not slub_use_zone_movable. In a situation where they wanted to have a hugepage pool that reliably resized and slub_min_order == HUGE_PAGESIZE, he would find that they collide for no obvious reason.

Quoted 5 lines

A system with huge amounts of memory has a large amount of huge pages. It is typically at this point to have 4G per cpu in a system and we may go higher. 4G means up to 2048 huge pages per cpu! Huge page allocation will be quite common and its good to reduce page allocator overhead.

Marking them movable makes no difference to that assertion.

Quoted 9 lines

Quoted 3 lines

Doesnt it mean that the allocations can occur in MAX_ORDER blocks marked MOVABLE?

Blocks aren't MAX_ORDER in size, they are pageblock_order in size and that value can be thought of as HUGETLB_PAGE_ORDER. No matter what you mark them as, it is still one pageblock. If you leave them as RECLAIMABLE or UNMOVABLE, a MOVABLE block may still get reclaimed and given to slab instead without this patch. Marking them movable when no partition exists gains nothing at all.

Ok so order 9 allocs of slub could occur in pageblock_order blocks like what happens for huge pages today. AFAICT this makes the handling of slab pages consistent with huge pages?

Quoted 4 lines

Quoted 3 lines

echo 2 >/proc/sys/vm/drop_cache will usually allow a significant shrinkage of the slab caches. In many ways it is the same.

Quoted 4 lines

Except it doesn't work for all slabs. As part of the highorder allocation stress tests I run, a final part is allocating pages when no other process is running and /proc/sys/vm/drop_cache has been used. There are still remaining pages left in odd places.

Nor does it work for huge pages which cannot be moved but they are marked __GFP_MOVABLE anyways.

Quoted 7 lines

Quoted 2 lines

This is a feature enabled by a special command line boot option. So its something that the admin did *intentionally*.

Not quite. What he asked for is that slub_min_order=HUGE_PAGESIZE, not slub_use_zone_movable. In a situation where they wanted to have a hugepage pool that reliably resized and slub_min_order == HUGE_PAGESIZE, he would find that they collide for no obvious reason.

Hmm.... So they would use the size of the movable area to size the hugetlb area?

Quoted 6 lines

Quoted 5 lines

A system with huge amounts of memory has a large amount of huge pages. It is typically at this point to have 4G per cpu in a system and we may go higher. 4G means up to 2048 huge pages per cpu! Huge page allocation will be quite common and its good to reduce page allocator overhead.

Marking them movable makes no difference to that assertion.

Hmmmm... Okay if pages are managed in pageblock_size chunks that are of HUGE_PAGE_SIZE then this patch makes no difference whatsoever.

Quoted 3 lines

Hmmmm... Okay if pages are managed in pageblock_size chunks that are of HUGE_PAGE_SIZE then this patch makes no difference whatsoever.

Yes it does - it means that slub pages can be allocated from the movablecore= partition if slub_min_order is set to a magic value. What it does not do at all is help SLUB in a meaningful fashion.

Still NACK.

Expand the scheme used for kmalloc-2048 and kmalloc-4096 to all slab caches. That means that kmem_cache_free() must now be able to handle a fallback object that was allocated from the page allocator. This is touching the fastpath costing us 1/2 % of performance (pretty small so within variance). Kind of hacky though.

Quoted 5 lines · Christoph Lameter

Expand the scheme used for kmalloc-2048 and kmalloc-4096 to all slab caches. That means that kmem_cache_free() must now be able to handle a fallback object that was allocated from the page allocator. This is touching the fastpath costing us 1/2 % of performance (pretty small so within variance). Kind of hacky though.

Looks good but are there any numbers that indicate this is an overall win?

Expand the scheme used for kmalloc-2048 and kmalloc-4096 to all slab
caches. That means that kmem_cache_free() must now be able to handle a fallback object that was allocated from the page allocator. This is touching the fastpath costing us 1/2 % of performance (pretty small so within variance). Kind of hacky though.

Currently we determine the gfp flags to pass to the page allocator each time a slab is being allocated.

Determine the bits to be set at the time the slab is created. Store in a new allocflags field and add the flags in allocate_slab().

Currently we determine the gfp flags to pass to the page allocator each time a slab is being allocated.

Determine the bits to be set at the time the slab is created. Store in a new allocflags field and add the flags in allocate_slab().

Signed-off-by Christoph Lameter <[email protected]>

---
 include/linux/slub_def.h |    1 +
 mm/slub.c                |   19 +++++++++++--------
 2 files changed, 12 insertions(+), 8 deletions(-)

Index: linux-2.6/include/linux/slub_def.h
===================================================================

include/linux/slub_def.h +1 -0

@@ -71,6 +71,7 @@ struct kmem_cache {
 
 	/* Allocation and freeing of slabs */
 	int objects;		/* Number of objects in slab */
+	gfp_t allocflags;	/* gfp flags to use on each alloc */
 	int refcount;		/* Refcount for slab cache destroy */
 	void (*ctor)(struct kmem_cache *, void *);
 	int inuse;		/* Offset to metadata */

Index: linux-2.6/mm/slub.c
===================================================================

mm/slub.c +4 -8

@@ -1078,14 +1078,7 @@ static struct page *allocate_slab(struct
 	struct page *page;
 	int pages = 1 << s->order;
 
-	if (s->order)
-		flags |= __GFP_COMP;
-
-	if (s->flags & SLAB_CACHE_DMA)
-		flags |= SLUB_DMA;
-
-	if (s->flags & SLAB_RECLAIM_ACCOUNT)
-		flags |= __GFP_RECLAIMABLE;
+	flags |= s->allocflags;
 
 	if (node == -1)
 		page = alloc_pages(flags, s->order);

@@ -2333,6 +2326,16 @@ static int calculate_sizes(struct kmem_c
 	if (s->order < 0)
 		return 0;
 
+	s->allocflags = 0;
+	if (s->order)
+		s->allocflags |= __GFP_COMP;