Virtual Compound Page Support

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

Quoted 9 lines · Christoph Lameter

Index: linux-2.6/include/linux/mm.h
===================================================================
--- linux-2.6.orig/include/linux/mm.h 2007-09-17
21:46:06.000000000 -0700
+++ linux-2.6/include/linux/mm.h 2007-09-17 23:56:54.000000000 -0700

include/linux/mm.h +0 -0

@@ -1158,6 +1158,14 @@ static inline unsigned long vma_pages(st
 	return (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
 }
 

include/linux/mm.h static inline unsigned long vma_pages(st · line 1167

Quoted 7 lines

include/linux/mm.h +7 -0

+/* Determine if an address is within the vmalloc range */
+static inline int is_vmalloc_addr(const void *x)
+{
+	unsigned long addr = (unsigned long)x;
+
+	return addr >= VMALLOC_START && addr < VMALLOC_END;
+}

This breaks on i386 because VMALLOC_END is defined in terms of PKMAP_BASE in the CONFIG_HIGHMEM case.

Currently there is a strong tendency to avoid larger page allocations in the kernel because of past fragmentation issues and the current defragmentation methods are still evolving. It is not clear to what extend they can provide reliable allocations for higher order pages (plus the definition of "reliable" seems to be in the eye of the beholder).

Currently we use vmalloc allocations in many locations to provide a safe way to allocate larger arrays. That is due to the danger of higher order allocations failing. Virtual Compound pages allow the use of regular page allocator allocations that will fall back only if there is an actual problem with acquiring a higher order page.

This patch set provides a way for a higher page allocation to fall back. Instead of a physically contiguous page a virtually contiguous page is provided. The functionality of the vmalloc layer is used to provide the necessary page tables and control structures to establish a virtually contiguous area.

Advantages:

- If higher order allocations are failing then virtual compound pages consisting of a series of order-0 pages can stand in for those allocations.

- "Reliability" as long as the vmalloc layer can provide virtual mappings.

- Ability to reduce the use of vmalloc layer significantly by using physically contiguous memory instead of virtual contiguous memory. Most uses of vmalloc() can be converted to page allocator calls.

- The use of physically contiguous memory instead of vmalloc may allow the
use larger TLB entries thus reducing TLB pressure. Also reduces
the need
for page table walks.

Disadvantages:

- In order to use fall back the logic accessing the memory must be aware that the memory could be backed by a virtual mapping and take precautions. virt_to_page() and page_address() may not work and vmalloc_to_page() and vmalloc_address() (introduced through this patch set) may have to be called.

- Virtual mappings are less efficient than physical mappings. Performance will drop once virtual fall back occurs.

- Virtual mappings have more memory overhead. vm_area control structures
page tables, page arrays etc need to be allocated and managed to
provide
virtual mappings.

The patchset provides this functionality in stages. Stage 1 introduces the basic fall back mechanism necessary to replace vmalloc allocations with

	alloc_page(GFP_VFALLBACK, order, ....)

which signifies to the page allocator that a higher order is to be found but a virtual mapping may stand in if there is an issue with fragmentation.

Stage 1 functionality does not allow allocation and freeing of virtual mappings from interrupt contexts.

The stage 1 series ends with the conversion of a few key uses of vmalloc in the VM to alloc_pages() for the allocation of sparsemems memmap table and the wait table in each zone. Other uses of vmalloc could be converted in the same way.

Stage 2 functionality enhances the fallback even more allowing allocation and frees in interrupt context.

SLUB is then modified to use the virtual mappings for slab caches that are marked with SLAB_VFALLBACK. If a slab cache is marked this way then we drop all the restraints regarding page order and allocate good large memory areas that fit lots of objects so that we rarely have to use the slow paths.

Two slab caches--the dentry cache and the buffer_heads--are then flagged that way. Others could be converted in the same way.

The patch set also provides a debugging aid through setting

CONFIG_VFALLBACK_ALWAYS

If set then all GFP_VFALLBACK allocations fall back to the virtual mappings. This is useful for verification tests. The test of this patch set was done by enabling that options and compiling a kernel.

Stage 3 functionality could be the adding of support for the large buffer size patchset. Not done yet and not sure if it would be useful to do.

Much of this patchset may only be needed for special cases in which the existing defragmentation methods fail for some reason. It may be better to have the system operate without such a safety net and make sure that the page allocator can return large orders in a reliable way.

The initial idea for this patchset came from Nick Piggin's fsblock and from his arguments about reliability and guarantees. Since his fsblock uses the virtual mappings I think it is legitimate to generalize the use of virtual mappings to support higher order allocations in this way. The application of these ideas to the large block size patchset etc are straightforward. If wanted I can base the next rev of the largebuffer patchset on this one and implement fallback.

Contrary to Nick, I still doubt that any of this provides a "guarantee". Have said that I have to deal with various failure scenarios in the VM daily and I'd certainly like to see it work in a more reliable manner.

IMHO getting rid of the various workarounds to deal with the small 4k pages and avoiding additional layers that group these pages in subsystem specific ways is something that can simplify the kernel and make the kernel more reliable overall.

If people feel that a virtual fall back is needed then so be it. Maybe we can shed our security blanket later when the approaches to deal with fragmentation have matured.

The patch set is also available via git from the largeblock git tree via

git pull
git://git.kernel.org/pub/scm/linux/kernel/git/christoph/
largeblocksize.git
vcompound

Signature · 5 lines

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

Make vunmap return the page array that was used at vmap. This is useful if one has no structures to track the page array but simply stores the virtual address somewhere. The disposition of the page array can be decided upon after vunmap. vfree() may now also be used instead of vunmap which will release the page array after vunmap'ping it.

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

Quoted 9 lines

Quoted 9 lines

Index: linux-2.6/include/linux/mm.h
===================================================================
--- linux-2.6.orig/include/linux/mm.h 2007-09-17 21:46:06.000000000
-0700
+++ linux-2.6/include/linux/mm.h 2007-09-17 23:56:54.000000000 -0700

include/linux/mm.h +0 -0

@@ -1158,6 +1158,14 @@ static inline unsigned long vma_pages(st
 	return (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
 }
 

Quoted 10 lines

include/linux/mm.h static inline unsigned long vma_pages(st · line 1167

Quoted 7 lines

include/linux/mm.h +7 -0

+/* Determine if an address is within the vmalloc range */
+static inline int is_vmalloc_addr(const void *x)
+{
+	unsigned long addr = (unsigned long)x;
+
+	return addr >= VMALLOC_START && addr < VMALLOC_END;
+}

This breaks on i386 because VMALLOC_END is defined in terms of PKMAP_BASE in the CONFIG_HIGHMEM case.

That is incorrect. This works perfectly on i386 and on ALL architectures supported by Linux. A lot of places in the kernel already do this today (mostly hand coded though, eg XFS and NTFS)...

The patchset provides this functionality in stages. Stage 1 introduces the basic fall back mechanism necessary to replace vmalloc allocations with

	alloc_page(GFP_VFALLBACK, order, ....)

which signifies to the page allocator that a higher order is to be found but a virtual mapping may stand in if there is an issue with fragmentation.

Stage 1 functionality does not allow allocation and freeing of virtual mappings from interrupt contexts.

The stage 1 series ends with the conversion of a few key uses of vmalloc in the VM to alloc_pages() for the allocation of sparsemems memmap table and the wait table in each zone. Other uses of vmalloc could be converted in the same way.

Stage 2 functionality enhances the fallback even more allowing allocation and frees in interrupt context.

SLUB is then modified to use the virtual mappings for slab caches that are marked with SLAB_VFALLBACK. If a slab cache is marked this way then we drop all the restraints regarding page order and allocate good large memory areas that fit lots of objects so that we rarely have to use the slow paths.

Two slab caches--the dentry cache and the buffer_heads--are then flagged that way. Others could be converted in the same way.

The patch set also provides a debugging aid through setting

CONFIG_VFALLBACK_ALWAYS

If set then all GFP_VFALLBACK allocations fall back to the virtual mappings. This is useful for verification tests. The test of this patch set was done by enabling that options and compiling a kernel.

Stage 3 functionality could be the adding of support for the large buffer size patchset. Not done yet and not sure if it would be useful to do.

Much of this patchset may only be needed for special cases in which the existing defragmentation methods fail for some reason. It may be better to have the system operate without such a safety net and make sure that the page allocator can return large orders in a reliable way.

The initial idea for this patchset came from Nick Piggin's fsblock and from his arguments about reliability and guarantees. Since his fsblock uses the virtual mappings I think it is legitimate to generalize the use of virtual mappings to support higher order allocations in this way. The application of these ideas to the large block size patchset etc are straightforward. If wanted I can base the next rev of the largebuffer patchset on this one and implement fallback.

Contrary to Nick, I still doubt that any of this provides a "guarantee". Have said that I have to deal with various failure scenarios in the VM daily and I'd certainly like to see it work in a more reliable manner.

IMHO getting rid of the various workarounds to deal with the small 4k pages and avoiding additional layers that group these pages in subsystem specific ways is something that can simplify the kernel and make the kernel more reliable overall.

If people feel that a virtual fall back is needed then so be it. Maybe we can shed our security blanket later when the approaches to deal with fragmentation have matured.

The patch set is also available via git from the largeblock git tree via

git pull
git://git.kernel.org/pub/scm/linux/kernel/git/christoph/largeblocksize.git
vcompound

Signature · 4 lines

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Hi Christoph,

Quoted 17 lines · Christoph Lameter

Currently there is a strong tendency to avoid larger page allocations in
the kernel because of past fragmentation issues and the current defragmentation methods are still evolving. It is not clear to what extend
they can provide reliable allocations for higher order pages (plus the definition of "reliable" seems to be in the eye of the beholder).

Currently we use vmalloc allocations in many locations to provide a safe
way to allocate larger arrays. That is due to the danger of higher order
allocations failing. Virtual Compound pages allow the use of regular page allocator allocations that will fall back only if there is an actual
problem with acquiring a higher order page.

Quoted 7 lines

This patch set provides a way for a higher page allocation to fall back.
Instead of a physically contiguous page a virtually contiguous page is provided. The functionality of the vmalloc layer is used to provide the necessary page tables and control structures to establish a virtually
contiguous area.

I like this a lot. It will get rid of all the silly games we have to play when needing both large allocations and efficient allocations where possible. In NTFS I can then just allocated higher order pages instead of having to mess about with the allocation size and allocating a single page if the requested size is <= PAGE_SIZE or using vmalloc() if the size is bigger. And it will make it faster because a lot of the time a higher order page allocation will succeed with your patchset without resorting to vmalloc() so that will be a lot faster.

So where I currently have fs/ntfs/malloc.h the below mess I could get rid of it completely and just use the normal page allocator/ deallocator instead...

static inline void *__ntfs_malloc(unsigned long size, gfp_t gfp_mask)

{
         if (likely(size <= PAGE_SIZE)) {
                 BUG_ON(!size);
                 /* kmalloc() has per-CPU caches so is faster for  
now. */
                 return kmalloc(PAGE_SIZE, gfp_mask & ~__GFP_HIGHMEM);
                 /* return (void *)__get_free_page(gfp_mask); */
         }
         if (likely(size >> PAGE_SHIFT < num_physpages))
                 return __vmalloc(size, gfp_mask, PAGE_KERNEL);
         return NULL;
}

And other places in the kernel can make use of the same. I think XFS does very similar things to NTFS in terms of larger allocations at least and there are probably more places I don't know about off the top of my head...

I am looking forward to your patchset going into mainline. (-:

Quoted 21 lines · Anton Altaparmakov

Quoted 10 lines

Quoted 10 lines

Index: linux-2.6/include/linux/mm.h
===================================================================
--- linux-2.6.orig/include/linux/mm.h 2007-09-17 21:46:06.000000000
-0700
+++ linux-2.6/include/linux/mm.h 2007-09-17 23:56:54.000000000
-0700

include/linux/mm.h +0 -0

@@ -1158,6 +1158,14 @@ static inline unsigned long vma_pages(st
 	return (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
 }
 

Quoted 10 lines

include/linux/mm.h static inline unsigned long vma_pages(st · line 1167

Quoted 7 lines

include/linux/mm.h +7 -0

+/* Determine if an address is within the vmalloc range */
+static inline int is_vmalloc_addr(const void *x)
+{
+	unsigned long addr = (unsigned long)x;
+
+	return addr >= VMALLOC_START && addr < VMALLOC_END;
+}

This breaks on i386 because VMALLOC_END is defined in terms of PKMAP_BASE in the CONFIG_HIGHMEM case.

Quoted 3 lines

That is incorrect. This works perfectly on i386 and on ALL architectures supported by Linux. A lot of places in the kernel already do this today (mostly hand coded though, eg XFS and NTFS)...

Hmm, really?

After applying patches 1-3 in this series and compiling on my i386 with defconfig, I get this:

In file included from include/linux/suspend.h:11,

                 from arch/i386/kernel/asm-offsets.c:11:

include/linux/mm.h: In function 'is_vmalloc_addr':
include/linux/mm.h:1166: error: 'PKMAP_BASE' undeclared (first use in this function) include/linux/mm.h:1166: error: (Each undeclared identifier is reported only once include/linux/mm.h:1166: error: for each function it appears in.)

so I don't know what you're talking about.

Although it may cause a problem as highmem.h also includes mm.h so a bit of trickery may be needed to get it to compile...

I suspect that is_vmalloc_addr() should not be in linux/mm.h at all and should be in linux/vmalloc.h instead and vmalloc.h should include linux/highmem.h. That would be more sensible than sticking a vmalloc related function into linux/mm.h where it does not belong...

Quoted 3 lines · Anton Altaparmakov

Although it may cause a problem as highmem.h also includes mm.h so a bit of trickery may be needed to get it to compile...

Quoted 4 lines

I suspect that is_vmalloc_addr() should not be in linux/mm.h at all and should be in linux/vmalloc.h instead and vmalloc.h should include linux/highmem.h. That would be more sensible than sticking a vmalloc related function into linux/mm.h where it does not belong...

That is why I suggested include/linux/vmalloc.h as its home in the first place. And no, adding an include for linux/highmem.h (and asm/pgtable.h) to linux/vmalloc.h does not work.

There even is such a function already in mm/sparse.c::vaddr_in_vmalloc_area() with pretty identical content. I would suggest either this new inline should go away completely and use the existing one and export it or the existing one should go away and the inline should be used. It seems silly to have two functions with different names doing exactly the same thing!

I suspect that is_vmalloc_addr() should not be in linux/mm.h at all and should be in linux/vmalloc.h instead and vmalloc.h should include linux/highmem.h. That would be more sensible than sticking a vmalloc related function into linux/mm.h where it does not belong...

1) Only power of two allocations are good candidates, or we waste RAM

2) On i386 machines, we have a small vmalloc window. (128 MB default value)
Many servers with >4GB memory (PAE) like to boot with vmalloc=32M option to get 992MB of LOWMEM. If we allow some slub caches to fallback to vmalloc land, we'll have problems to tune this.

4) vmalloc() currently uses a linked list of vm_struct. Might need something more scalable.

Quoted 1 line

	alloc_page(GFP_VFALLBACK, order, ....)

Is there a reason this needs to be a GFP flag versus a wrapper around alloc_page/free_page ? page_alloc.c is already too complicated and it's better to keep new features separated. The only drawback would be that free_pages would need a different call, but that doesn't seem like a big problem.

I'm also a little dubious about your attempts to do vmalloc in interrupt context. Is that really needed? GFP_ATOMIC allocations of large areas seem to be extremly unreliable to me and not design. Even if it works sometimes free probably wouldn't work there due to the flushes, which is very nasty. It would be better to drop that.

kernel/wait.c EXPORT_SYMBOL(wake_up_bit); · line 254

Quoted 3 lines · Christoph Lameter

kernel/wait.c +2 -0

+	if (is_vmalloc_addr(word))
+		page = vmalloc_to_page(word)

					^^^^^^

Missing ' ; '

Quoted 5 lines · Anton Altaparmakov

There even is such a function already in mm/sparse.c::vaddr_in_vmalloc_area() with pretty identical content. I would suggest either this new inline should go away completely and use the existing one and export it or the existing one should go away and the inline should be used. It seems silly to have two functions with different names doing exactly the same thing!

Just in case you have not noticed: This patchset removes the vaddr_in_vmalloc_area() in sparse.c

Quoted 4 lines · Anton Altaparmakov

I suspect that is_vmalloc_addr() should not be in linux/mm.h at all and should be in linux/vmalloc.h instead and vmalloc.h should include linux/highmem.h. That would be more sensible than sticking a vmalloc related function into linux/mm.h where it does not belong...

Tried it and that leads to all sort of other failures.

Hmm, I don't like returning array which someone allocated in past and forgot.

And, area->page[] array under vmalloc() is allocated as following (in -rc6-mm1) ==

       if (array_size > PAGE_SIZE) {
                pages = __vmalloc_node(array_size, gfp_mask | __GFP_ZERO,
                                        PAGE_KERNEL, node);
                area->flags |= VM_VPAGES;
        } else {
                pages = kmalloc_node(array_size,
                                (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO,
                                node);
        }

==
A bit complicating.

At least, please add comments "How to free page-array returned by vummap"

Quoted 1 line · KAMEZAWA Hiroyuki

Hmm, I don't like returning array which someone allocated in past and forgot.

But that is exactly the point. There is no need to keep track of the information that is of no interest until the disposition of the mapping.

Quoted 11 lines

And, area->page[] array under vmalloc() is allocated as following (in -rc6-mm1) ==

       if (array_size > PAGE_SIZE) {
                pages = __vmalloc_node(array_size, gfp_mask | __GFP_ZERO,
                                        PAGE_KERNEL, node);
                area->flags |= VM_VPAGES;
        } else {
                pages = kmalloc_node(array_size,
                                (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO,
                                node);
        }

Quoted 2 lines

==
A bit complicating.

Not at all. You can pass a __vmalloc'ed entity to vmap if you add VM_VPAGES to the flags passed to it.

Quoted 1 line

At least, please add comments "How to free page-array returned by vummap"

But that depends on how the vmap was called. The caller knows what he has done to acquire the memory and therefore also knows how to get rid of it.

If we are in an interrupt context then simply defer the free via a workqueue.

In an interrupt context it is not possible to use vmalloc_addr() to determine the vmalloc address. So add a variant that does that too.

Removing a virtual mappping *must* be done with interrupts enabled since tlb_xx functions are called that rely on interrupts for processor to processor communications.

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

---
 mm/page_alloc.c |   23 ++++++++++++++++++++++-
 1 file changed, 22 insertions(+), 1 deletion(-)

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

mm/page_alloc.c +22 -1

@@ -1297,7 +1297,12 @@ abort:
 	return NULL;
 }
 
-static void vcompound_free(void *addr)
+/*
+ * Virtual Compound freeing functions. This is complicated by the vmalloc
+ * layer not being able to free virtual allocations when interrupts are
+ * disabled. So we defer the frees via a workqueue if necessary.
+ */
+static void __vcompound_free(void *addr)
 {
 	struct page **pages = vunmap(addr);
 	int i;

@@ -1320,6 +1325,22 @@ static void vcompound_free(void *addr)
 	kfree(pages);
 }
 
+static void vcompound_free_work(struct work_struct *w)
+{
+	__vcompound_free((void *)w);
+}
+
+static void vcompound_free(void *addr)
+{
+	if (in_interrupt()) {
+		struct work_struct *w = addr;
+
+		INIT_WORK(w, vcompound_free_work);
+		schedule_work(w);
+	} else
+		__vcompound_free(addr);
+}
+
 /*
  * This is the 'heart' of the zoned buddy allocator.
  */

Quoted 3 lines

Removing a virtual mappping *must* be done with interrupts enabled since tlb_xx functions are called that rely on interrupts for processor to processor communications.

These things will clash drastically with my lazy TLB flushing and scalability work. Actually the lazy TLB flushing will provide a natural way to defer unmapping at interrupt time, and the scalability work should make it easier to vmap from interrupt context too, if you really need that.

SLAB_VFALLBACK can be specified for selected slab caches. If fallback is available then the conservative settings for higher order allocations are overridden. We then request an order that can accomodate at mininum 100 objects. The size of an individual slab allocation is allowed to reach up to 256k (order 6 on i386, order 4 on IA64).

Quoted 5 lines · Christoph Lameter

SLAB_VFALLBACK can be specified for selected slab caches. If fallback is available then the conservative settings for higher order allocations are overridden. We then request an order that can accomodate at mininum 100 objects. The size of an individual slab allocation is allowed to reach up to 256k (order 6 on i386, order 4 on IA64).

How come SLUB wants such a big amount of objects? I thought the unqueued nature of it made it better than slab because it minimised the amount of cache hot memory lying around in slabs...

vmalloc is incredibly slow and unscalable at the moment. I'm still working on making it more scalable and faster -- hopefully to a point where it would actually be usable for this... but you still get moved off large TLBs, and also have to inevitably do tlb flushing.

Or do you have SLUB at a point where performance is comparable to SLAB, and this is just a possible idea for more performance?

Again I have not seen any fallbacks to vmalloc in my testing. What we are doing here is mainly to address your theoretical cases that we so far have never seen to be a problem and increase the reliability of allocations of page orders larger than 3 to a usable level. So far I have so far not dared to enable orders larger than 3 by default.

Quoted 5 lines · Christoph Lameter

Again I have not seen any fallbacks to vmalloc in my testing. What we are doing here is mainly to address your theoretical cases that we so far have never seen to be a problem and increase the reliability of allocations of page orders larger than 3 to a usable level. So far I have so far not dared to enable orders larger than 3 by default.

take a recent -mm kernel, boot with mem=128M.

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Quoted 5 lines

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Really? That means we can no longer even allocate stacks for forking.

Its surprising that neither lumpy reclaim nor the mobility patches can deal with it? Lumpy reclaim should be able to free neighboring pages to avoid the order 1 failure unless there are lots of pinned pages.

I guess then that lots of pages are pinned through I/O?

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

Quoted 9 lines

Quoted 6 lines

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Really? That means we can no longer even allocate stacks for forking.

Quoted 5 lines

Its surprising that neither lumpy reclaim nor the mobility patches can deal with it? Lumpy reclaim should be able to free neighboring pages to avoid the order 1 failure unless there are lots of pinned pages.

I guess then that lots of pages are pinned through I/O?

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max

order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

its still on my todo list to look at it further..

Quoted 11 lines · Christoph Lameter

Quoted 5 lines

SLAB_VFALLBACK can be specified for selected slab caches. If fallback is available then the conservative settings for higher order allocations are overridden. We then request an order that can accomodate at mininum 100 objects. The size of an individual slab allocation is allowed to reach up to 256k (order 6 on i386, order 4 on IA64).

How come SLUB wants such a big amount of objects? I thought the unqueued nature of it made it better than slab because it minimised the amount of cache hot memory lying around in slabs...

The more objects in a page the more the fast path runs. The more the fast path runs the lower the cache footprint and the faster the overall allocations etc.

SLAB can be configured for large queues holdings lots of objects. SLUB can only reach the same through large pages because it does not have queues.

One could add the ability to manage pools of cpu slabs but that would be adding yet another layer to compensate for the problem of the small pages.

Reliable large page allocations means that we can get rid
of these layers and the many workarounds that we have in place right now.

The unqueued nature of SLUB reduces memory requirements and in general the more efficient code paths of SLUB offset the advantage that SLAB can reach by being able to put more objects onto its queues. SLAB necessarily introduces complexity and cache line use through the need to manage those queues.

Quoted 4 lines

vmalloc is incredibly slow and unscalable at the moment. I'm still working on making it more scalable and faster -- hopefully to a point where it would actually be usable for this... but you still get moved off large TLBs, and also have to inevitably do tlb flushing.

Again I have not seen any fallbacks to vmalloc in my testing. What we are doing here is mainly to address your theoretical cases that we so far have never seen to be a problem and increase the reliability of allocations of page orders larger than 3 to a usable level. So far I have so far not dared to enable orders larger than 3 by default.

AFAICT The performance of vmalloc is not really relevant. If this would become an issue then it would be possible to reduce the orders used to avoid fallbacks.

Quoted 2 lines

Or do you have SLUB at a point where performance is comparable to SLAB, and this is just a possible idea for more performance?

AFAICT SLUBs performance is superior to SLAB in most cases and it was like that from the beginning. I am still concerned about several corner cases though (I think most of them are going to be addressed by the per cpu patches in mm). Having a comparable or larger amount of per cpu objects as SLAB is something that also could address some of these concerns and could increase performance much further.

Quoted 5 lines

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

Yes, strict ordering would be much better. On NUMA it may be possible to completely forbid merging.

We can fall back to other nodes if necessary.
12M is not much on a NUMA system.

But this shows that (unsurprisingly) we may have issues on systems with a small amounts of memory and we may not want to use higher orders on such systems.

The case you got may be good to use as a testcase for the virtual fallback. Hmmmm...

Maybe it is possible to allocate the stack as a virtual compound page. Got some script/code to produce that problem?

Quoted 11 lines · Nick Piggin

Quoted 6 lines · Christoph Lameter

SLAB_VFALLBACK can be specified for selected slab caches. If fallback is available then the conservative settings for higher order allocations are overridden. We then request an order that can accomodate at mininum 100 objects. The size of an individual slab allocation is allowed to reach up to 256k (order 6 on i386, order 4 on IA64).

How come SLUB wants such a big amount of objects? I thought the unqueued nature of it made it better than slab because it minimised the amount of cache hot memory lying around in slabs...

The more objects in a page the more the fast path runs. The more the fast path runs the lower the cache footprint and the faster the overall allocations etc.

SLAB can be configured for large queues holdings lots of objects. SLUB can only reach the same through large pages because it does not have queues. One could add the ability to manage pools of cpu slabs but that would be adding yet another layer to compensate for the problem of the small pages. Reliable large page allocations means that we can get rid of these layers and the many workarounds that we have in place right now.

The unqueued nature of SLUB reduces memory requirements and in general the more efficient code paths of SLUB offset the advantage that SLAB can reach by being able to put more objects onto its queues.
introduces complexity and cache line use through the need to manage those queues.

Quoted 4 lines

vmalloc is incredibly slow and unscalable at the moment. I'm still working on making it more scalable and faster -- hopefully to a point where it would actually be usable for this... but you still get moved off large TLBs, and also have to inevitably do tlb flushing.

Again I have not seen any fallbacks to vmalloc in my testing. What we are doing here is mainly to address your theoretical cases that we so far have never seen to be a problem and increase the reliability of allocations of page orders larger than 3 to a usable level. So far I have so far not dared to enable orders larger than 3 by default.

Quoted 2 lines

Or do you have SLUB at a point where performance is comparable to SLAB, and this is just a possible idea for more performance?

AFAICT SLUBs performance is superior to SLAB in most cases and it was like that from the beginning. I am still concerned about several corner cases though (I think most of them are going to be addressed by the per cpu patches in mm). Having a comparable or larger amount of per cpu objects as SLAB is something that also could address some of these concerns and could increase performance much further.

Quoted 12 lines · Christoph Lameter

Quoted 5 lines

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Really? That means we can no longer even allocate stacks for forking.

Its surprising that neither lumpy reclaim nor the mobility patches can deal with it? Lumpy reclaim should be able to free neighboring pages to avoid the order 1 failure unless there are lots of pinned pages.

Quoted 1 line

I guess then that lots of pages are pinned through I/O?

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

its still on my todo list to look at it further..

Really? That means we can no longer even allocate stacks for forking.

Quoted 22 lines · On Fri, 28 Sep 2007 20:25:50 +0200 Peter Zijlstra <[email protected]>…

Quoted 6 lines · Christoph Lameter

Quoted 5 lines

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Quoted 7 lines

Really? That means we can no longer even allocate stacks for forking.

Its surprising that neither lumpy reclaim nor the mobility patches can deal with it? Lumpy reclaim should be able to free neighboring pages to avoid the order 1 failure unless there are lots of pinned pages.

I guess then that lots of pages are pinned through I/O?

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

Quoted 2 lines

its still on my todo list to look at it further..

That would be really really bad (as in: patch-dropping time) if those order-1 allocations are not atomic.

What's the callsite?

Ah, right, that was the detail... all this lumpy reclaim is useless for atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

One I can remember was:

add_to_page_cache()
radix_tree_insert()
radix_tree_node_alloc()
kmem_cache_alloc()

which is an atomic callsite.

Which leaves us in a situation where we can load pages, because there is free memory, but can't manage to allocate memory to track them..

Quoted 27 lines · Andrew Morton

Quoted 24 lines · On Fri, 28 Sep 2007 20:25:50 +0200 Peter Zijlstra <[email protected]>…

Quoted 6 lines · Christoph Lameter

Quoted 5 lines

start 2 processes that each mmap a separate 64M file, and which does sequential writes on them. start a 3th process that does the same with 64M anonymous.

wait for a while, and you'll see order=1 failures.

Quoted 7 lines

Really? That means we can no longer even allocate stacks for forking.

Its surprising that neither lumpy reclaim nor the mobility patches can deal with it? Lumpy reclaim should be able to free neighboring pages to avoid the order 1 failure unless there are lots of pinned pages.

I guess then that lots of pages are pinned through I/O?

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

its still on my todo list to look at it further..

Quoted 4 lines

That would be really really bad (as in: patch-dropping time) if those order-1 allocations are not atomic.

What's the callsite?

Ah, right, that was the detail... all this lumpy reclaim is useless for atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

One I can remember was:

add_to_page_cache()
radix_tree_insert()
radix_tree_node_alloc()
kmem_cache_alloc()

which is an atomic callsite.

Which leaves us in a situation where we can load pages, because there is free memory, but can't manage to allocate memory to track them..

Quoted 11 lines · Peter Zijlstra

Ah, right, that was the detail... all this lumpy reclaim is useless for atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

One I can remember was:

add_to_page_cache()
radix_tree_insert()
radix_tree_node_alloc()
kmem_cache_alloc()

Quoted 4 lines

which is an atomic callsite.

Which leaves us in a situation where we can load pages, because there is free memory, but can't manage to allocate memory to track them..

Ah, I found a boot log of one of these sessions, its also full of order-2 OOMs.. :-/

Quoted 16 lines · On Sat, 29 Sep 2007 10:53:41 +0200 Peter Zijlstra <[email protected]>…

Quoted 13 lines · Peter Zijlstra

Ah, right, that was the detail... all this lumpy reclaim is useless for atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

One I can remember was:

add_to_page_cache()
radix_tree_insert()
radix_tree_node_alloc()
kmem_cache_alloc()

which is an atomic callsite.

Quoted 5 lines

Quoted 2 lines

Which leaves us in a situation where we can load pages, because there is free memory, but can't manage to allocate memory to track them..

Ah, I found a boot log of one of these sessions, its also full of order-2 OOMs.. :-/

oom-killings, or page allocation failures? The latter, one hopes.

Quoted 1 line

oom-killings, or page allocation failures? The latter, one hopes.

Linux version 2.6.23-rc4-mm1-dirty (root@dyad) (gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4)) #27 Tue Sep 18 15:40:35 CEST 2007

...

mm_tester invoked oom-killer: gfp_mask=0x40d0, order=2, oomkilladj=0

Call Trace:
611b3878:  [<6002dd28>] printk_ratelimit+0x15/0x17
611b3888:  [<60052ed4>] out_of_memory+0x80/0x100
611b38c8:  [<60054b0c>] __alloc_pages+0x1ed/0x280
611b3948:  [<6006c608>] allocate_slab+0x5b/0xb0
611b3968:  [<6006c705>] new_slab+0x7e/0x183
611b39a8:  [<6006cbae>] __slab_alloc+0xc9/0x14b
611b39b0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39b8:  [<600980f2>] do_mpage_readpage+0x3b3/0x472
611b39e0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39f8:  [<6006cc81>] kmem_cache_alloc+0x51/0x98
611b3a38:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b3a58:  [<6004f8e2>] add_to_page_cache+0x22/0xf7
611b3a98:  [<6004f9c6>] add_to_page_cache_lru+0xf/0x24
611b3ab8:  [<6009821e>] mpage_readpages+0x6d/0x109
611b3ac0:  [<600d59f0>] ext3_get_block+0x0/0xf2
611b3b08:  [<6005483d>] get_page_from_freelist+0x8d/0xc1
611b3b88:  [<600d6937>] ext3_readpages+0x18/0x1a
611b3b98:  [<60056f00>] read_pages+0x37/0x9b
611b3bd8:  [<60057064>] __do_page_cache_readahead+0x100/0x157
611b3c48:  [<60057196>] do_page_cache_readahead+0x52/0x5f
611b3c78:  [<60050ab4>] filemap_fault+0x145/0x278
611b3ca8:  [<60022b61>] run_syscall_stub+0xd1/0xdd
611b3ce8:  [<6005eae3>] __do_fault+0x7e/0x3ca
611b3d68:  [<6005ee60>] do_linear_fault+0x31/0x33

611b3d88:  [<6005f149>] handle_mm_fault+0x14e/0x246
611b3da8:  [<60120a7b>] __up_read+0x73/0x7b
611b3de8:  [<60013177>] handle_page_fault+0x11f/0x23b
611b3e48:  [<60013419>] segv+0xac/0x297
611b3f28:  [<60013367>] segv_handler+0x68/0x6e
611b3f48:  [<600232ad>] get_skas_faultinfo+0x9c/0xa1
611b3f68:  [<60023853>] userspace+0x13a/0x19d
611b3fc8:  [<60010d58>] fork_handler+0x86/0x8d

On Sat, 29 Sep 2007 11:14:02 +0200 Peter Zijlstra <[email protected]>

Quoted 34 lines

Quoted 1 line

oom-killings, or page allocation failures? The latter, one hopes.

Linux version 2.6.23-rc4-mm1-dirty (root@dyad) (gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4)) #27 Tue Sep 18 15:40:35 CEST 2007

...

mm_tester invoked oom-killer: gfp_mask=0x40d0, order=2, oomkilladj=0

Call Trace:
611b3878:  [<6002dd28>] printk_ratelimit+0x15/0x17
611b3888:  [<60052ed4>] out_of_memory+0x80/0x100
611b38c8:  [<60054b0c>] __alloc_pages+0x1ed/0x280
611b3948:  [<6006c608>] allocate_slab+0x5b/0xb0
611b3968:  [<6006c705>] new_slab+0x7e/0x183
611b39a8:  [<6006cbae>] __slab_alloc+0xc9/0x14b
611b39b0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39b8:  [<600980f2>] do_mpage_readpage+0x3b3/0x472
611b39e0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39f8:  [<6006cc81>] kmem_cache_alloc+0x51/0x98
611b3a38:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b3a58:  [<6004f8e2>] add_to_page_cache+0x22/0xf7
611b3a98:  [<6004f9c6>] add_to_page_cache_lru+0xf/0x24
611b3ab8:  [<6009821e>] mpage_readpages+0x6d/0x109
611b3ac0:  [<600d59f0>] ext3_get_block+0x0/0xf2
611b3b08:  [<6005483d>] get_page_from_freelist+0x8d/0xc1
611b3b88:  [<600d6937>] ext3_readpages+0x18/0x1a
611b3b98:  [<60056f00>] read_pages+0x37/0x9b
611b3bd8:  [<60057064>] __do_page_cache_readahead+0x100/0x157
611b3c48:  [<60057196>] do_page_cache_readahead+0x52/0x5f
611b3c78:  [<60050ab4>] filemap_fault+0x145/0x278
611b3ca8:  [<60022b61>] run_syscall_stub+0xd1/0xdd
611b3ce8:  [<6005eae3>] __do_fault+0x7e/0x3ca
611b3d68:  [<6005ee60>] do_linear_fault+0x31/0x33

Quoted 8 lines

611b3d88:  [<6005f149>] handle_mm_fault+0x14e/0x246
611b3da8:  [<60120a7b>] __up_read+0x73/0x7b
611b3de8:  [<60013177>] handle_page_fault+0x11f/0x23b
611b3e48:  [<60013419>] segv+0xac/0x297
611b3f28:  [<60013367>] segv_handler+0x68/0x6e
611b3f48:  [<600232ad>] get_skas_faultinfo+0x9c/0xa1
611b3f68:  [<60023853>] userspace+0x13a/0x19d
611b3fc8:  [<60010d58>] fork_handler+0x86/0x8d

OK, that's different. Someone broke the vm - order-2 GFP_KERNEL allocations aren't supposed to fail.

I'm suspecting that did_some_progress thing.

Quoted 4 lines · Peter Zijlstra

memory got massively fragemented, as anti-frag gets easily defeated. setting min_free_kbytes to 12M does seem to solve it - it forces 2 max order blocks to stay available, so we don't mix types. however 12M on 128M is rather a lot.

Yes, strict ordering would be much better. On NUMA it may be possible to completely forbid merging. We can fall back to other nodes if necessary. 12M is not much on a NUMA system.

But this shows that (unsurprisingly) we may have issues on systems with a small amounts of memory and we may not want to use higher orders on such systems.

The case you got may be good to use as a testcase for the virtual fallback. Hmmmm... Maybe it is possible to allocate the stack as a virtual compound page. Got some script/code to produce that problem?

Quoted 1 line · Andrew Morton

On Sat, 29 Sep 2007 11:14:02 +0200 Peter Zijlstra <[email protected]>

Quoted 43 lines · wrote:

Quoted 42 lines

Quoted 1 line

oom-killings, or page allocation failures? The latter, one hopes.

Linux version 2.6.23-rc4-mm1-dirty (root@dyad) (gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4)) #27 Tue Sep 18 15:40:35 CEST 2007

...

mm_tester invoked oom-killer: gfp_mask=0x40d0, order=2, oomkilladj=0

Call Trace:
611b3878:  [<6002dd28>] printk_ratelimit+0x15/0x17
611b3888:  [<60052ed4>] out_of_memory+0x80/0x100
611b38c8:  [<60054b0c>] __alloc_pages+0x1ed/0x280
611b3948:  [<6006c608>] allocate_slab+0x5b/0xb0
611b3968:  [<6006c705>] new_slab+0x7e/0x183
611b39a8:  [<6006cbae>] __slab_alloc+0xc9/0x14b
611b39b0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39b8:  [<600980f2>] do_mpage_readpage+0x3b3/0x472
611b39e0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39f8:  [<6006cc81>] kmem_cache_alloc+0x51/0x98
611b3a38:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b3a58:  [<6004f8e2>] add_to_page_cache+0x22/0xf7
611b3a98:  [<6004f9c6>] add_to_page_cache_lru+0xf/0x24
611b3ab8:  [<6009821e>] mpage_readpages+0x6d/0x109
611b3ac0:  [<600d59f0>] ext3_get_block+0x0/0xf2
611b3b08:  [<6005483d>] get_page_from_freelist+0x8d/0xc1
611b3b88:  [<600d6937>] ext3_readpages+0x18/0x1a
611b3b98:  [<60056f00>] read_pages+0x37/0x9b
611b3bd8:  [<60057064>] __do_page_cache_readahead+0x100/0x157
611b3c48:  [<60057196>] do_page_cache_readahead+0x52/0x5f
611b3c78:  [<60050ab4>] filemap_fault+0x145/0x278
611b3ca8:  [<60022b61>] run_syscall_stub+0xd1/0xdd
611b3ce8:  [<6005eae3>] __do_fault+0x7e/0x3ca
611b3d68:  [<6005ee60>] do_linear_fault+0x31/0x33
611b3d88:  [<6005f149>] handle_mm_fault+0x14e/0x246
611b3da8:  [<60120a7b>] __up_read+0x73/0x7b
611b3de8:  [<60013177>] handle_page_fault+0x11f/0x23b
611b3e48:  [<60013419>] segv+0xac/0x297
611b3f28:  [<60013367>] segv_handler+0x68/0x6e
611b3f48:  [<600232ad>] get_skas_faultinfo+0x9c/0xa1
611b3f68:  [<60023853>] userspace+0x13a/0x19d
611b3fc8:  [<60010d58>] fork_handler+0x86/0x8d

Quoted 4 lines

OK, that's different. Someone broke the vm - order-2 GFP_KERNEL allocations aren't supposed to fail.

I'm suspecting that did_some_progress thing.

The allocation didn't fail -- it invoked the OOM killer because the kernel ran out of unfragmented memory.

Probably because higher order
allocations are the new vogue in -mm at the moment ;)

On Sat, 29 Sep 2007 06:19:33 +1000 Nick Piggin <[email protected]>

Quoted 53 lines · Andrew Morton

Quoted 2 lines

On Sat, 29 Sep 2007 11:14:02 +0200 Peter Zijlstra
<[email protected]>

Quoted 47 lines · wrote:

Quoted 34 lines

Quoted 1 line

oom-killings, or page allocation failures? The latter, one hopes.

Linux version 2.6.23-rc4-mm1-dirty (root@dyad) (gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4)) #27 Tue Sep 18 15:40:35 CEST 2007

...

mm_tester invoked oom-killer: gfp_mask=0x40d0, order=2, oomkilladj=0

Call Trace:
611b3878:  [<6002dd28>] printk_ratelimit+0x15/0x17
611b3888:  [<60052ed4>] out_of_memory+0x80/0x100
611b38c8:  [<60054b0c>] __alloc_pages+0x1ed/0x280
611b3948:  [<6006c608>] allocate_slab+0x5b/0xb0
611b3968:  [<6006c705>] new_slab+0x7e/0x183
611b39a8:  [<6006cbae>] __slab_alloc+0xc9/0x14b
611b39b0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39b8:  [<600980f2>] do_mpage_readpage+0x3b3/0x472
611b39e0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39f8:  [<6006cc81>] kmem_cache_alloc+0x51/0x98
611b3a38:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b3a58:  [<6004f8e2>] add_to_page_cache+0x22/0xf7
611b3a98:  [<6004f9c6>] add_to_page_cache_lru+0xf/0x24
611b3ab8:  [<6009821e>] mpage_readpages+0x6d/0x109
611b3ac0:  [<600d59f0>] ext3_get_block+0x0/0xf2
611b3b08:  [<6005483d>] get_page_from_freelist+0x8d/0xc1
611b3b88:  [<600d6937>] ext3_readpages+0x18/0x1a
611b3b98:  [<60056f00>] read_pages+0x37/0x9b
611b3bd8:  [<60057064>] __do_page_cache_readahead+0x100/0x157
611b3c48:  [<60057196>] do_page_cache_readahead+0x52/0x5f
611b3c78:  [<60050ab4>] filemap_fault+0x145/0x278
611b3ca8:  [<60022b61>] run_syscall_stub+0xd1/0xdd
611b3ce8:  [<6005eae3>] __do_fault+0x7e/0x3ca
611b3d68:  [<6005ee60>] do_linear_fault+0x31/0x33

Quoted 8 lines

611b3d88:  [<6005f149>] handle_mm_fault+0x14e/0x246
611b3da8:  [<60120a7b>] __up_read+0x73/0x7b
611b3de8:  [<60013177>] handle_page_fault+0x11f/0x23b
611b3e48:  [<60013419>] segv+0xac/0x297
611b3f28:  [<60013367>] segv_handler+0x68/0x6e
611b3f48:  [<600232ad>] get_skas_faultinfo+0x9c/0xa1
611b3f68:  [<60023853>] userspace+0x13a/0x19d
611b3fc8:  [<60010d58>] fork_handler+0x86/0x8d

OK, that's different. Someone broke the vm - order-2 GFP_KERNEL allocations aren't supposed to fail.

I'm suspecting that did_some_progress thing.

Quoted 2 lines

The allocation didn't fail -- it invoked the OOM killer because the kernel ran out of unfragmented memory.

We can't "run out of unfragmented memory" for an order-2 GFP_KERNEL allocation in this workload. We go and synchronously free stuff up to make it work.

How did this get broken?

Quoted 2 lines

Probably because higher order
allocations are the new vogue in -mm at the moment ;)

That's a different bug.

bug 1: We shouldn't be doing higher-order allocations in slub because of the considerable damage this does to atomic allocations.

bug 2: order-2 GFP_KERNEL allocations shouldn't fail like this.

Quoted 1 line · Andrew Morton

On Sat, 29 Sep 2007 06:19:33 +1000 Nick Piggin <[email protected]>

Quoted 56 lines · wrote:

Quoted 55 lines · Andrew Morton

Quoted 2 lines

On Sat, 29 Sep 2007 11:14:02 +0200 Peter Zijlstra
<[email protected]>

Quoted 43 lines · wrote:

Quoted 34 lines

Quoted 1 line

oom-killings, or page allocation failures? The latter, one hopes.

Linux version 2.6.23-rc4-mm1-dirty (root@dyad) (gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4)) #27 Tue Sep 18 15:40:35 CEST 2007

...

mm_tester invoked oom-killer: gfp_mask=0x40d0, order=2, oomkilladj=0

Call Trace:
611b3878:  [<6002dd28>] printk_ratelimit+0x15/0x17
611b3888:  [<60052ed4>] out_of_memory+0x80/0x100
611b38c8:  [<60054b0c>] __alloc_pages+0x1ed/0x280
611b3948:  [<6006c608>] allocate_slab+0x5b/0xb0
611b3968:  [<6006c705>] new_slab+0x7e/0x183
611b39a8:  [<6006cbae>] __slab_alloc+0xc9/0x14b
611b39b0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39b8:  [<600980f2>] do_mpage_readpage+0x3b3/0x472
611b39e0:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b39f8:  [<6006cc81>] kmem_cache_alloc+0x51/0x98
611b3a38:  [<6011f89f>] radix_tree_preload+0x70/0xbf
611b3a58:  [<6004f8e2>] add_to_page_cache+0x22/0xf7
611b3a98:  [<6004f9c6>] add_to_page_cache_lru+0xf/0x24
611b3ab8:  [<6009821e>] mpage_readpages+0x6d/0x109
611b3ac0:  [<600d59f0>] ext3_get_block+0x0/0xf2
611b3b08:  [<6005483d>] get_page_from_freelist+0x8d/0xc1
611b3b88:  [<600d6937>] ext3_readpages+0x18/0x1a
611b3b98:  [<60056f00>] read_pages+0x37/0x9b
611b3bd8:  [<60057064>] __do_page_cache_readahead+0x100/0x157
611b3c48:  [<60057196>] do_page_cache_readahead+0x52/0x5f
611b3c78:  [<60050ab4>] filemap_fault+0x145/0x278
611b3ca8:  [<60022b61>] run_syscall_stub+0xd1/0xdd
611b3ce8:  [<6005eae3>] __do_fault+0x7e/0x3ca
611b3d68:  [<6005ee60>] do_linear_fault+0x31/0x33

Quoted 8 lines

611b3d88:  [<6005f149>] handle_mm_fault+0x14e/0x246
611b3da8:  [<60120a7b>] __up_read+0x73/0x7b
611b3de8:  [<60013177>] handle_page_fault+0x11f/0x23b
611b3e48:  [<60013419>] segv+0xac/0x297
611b3f28:  [<60013367>] segv_handler+0x68/0x6e
611b3f48:  [<600232ad>] get_skas_faultinfo+0x9c/0xa1
611b3f68:  [<60023853>] userspace+0x13a/0x19d
611b3fc8:  [<60010d58>] fork_handler+0x86/0x8d

Quoted 4 lines

OK, that's different. Someone broke the vm - order-2 GFP_KERNEL allocations aren't supposed to fail.

I'm suspecting that did_some_progress thing.

The allocation didn't fail -- it invoked the OOM killer because the kernel ran out of unfragmented memory.

Quoted 5 lines

We can't "run out of unfragmented memory" for an order-2 GFP_KERNEL allocation in this workload. We go and synchronously free stuff up to make it work.

How did this get broken?

Either no more order-2 pages could be freed, or the ones that were being freed were being used by something else (eg. other order-2 slab allocations).

Quoted 6 lines

Quoted 3 lines

Probably because higher order
allocations are the new vogue in -mm at the moment ;)

That's a different bug.

Quoted 4 lines

bug 1: We shouldn't be doing higher-order allocations in slub because of the considerable damage this does to atomic allocations.

bug 2: order-2 GFP_KERNEL allocations shouldn't fail like this.

I think one causes 2 as well -- it isn't just considerable damage to atomic allocations but to GFP_KERNEL allocations too.

On Sun, 30 Sep 2007 05:09:28 +1000 Nick Piggin <[email protected]>

Quoted 11 lines · Andrew Morton

Quoted 6 lines

We can't "run out of unfragmented memory" for an order-2 GFP_KERNEL allocation in this workload. We go and synchronously free stuff up to make it work.

How did this get broken?

Either no more order-2 pages could be freed, or the ones that were being freed were being used by something else (eg. other order-2 slab allocations).

No. The current design of reclaim (for better or for worse) is that for order 0,1,2 and 3 allocations we just keep on trying until it works. That got broken and I think it got broken at a design level when that did_some_progress logic went in. Perhaps something else we did later worsened things.

I thought it was slower. Have you fixed the performance regression? (OK, I read further down that you are still working on it but not confirmed yet...)

OK, so long as it isn't going to depend on using higher order pages, that's fine. (if they help even further as an optional thing, that's fine too. You can turn them on your huge systems and not even bother about adding this vmap fallback -- you won't have me to nag you about these purely theoretical issues).

Quoted 2 lines

atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

Oh OK.

I thought we'd already fixed slub so that it didn't do that. Maybe that fix is in -mm but I don't think so.

Trying to do atomic order-1 allocations on behalf of arbitray slab caches just won't fly - this is a significant degradation in kernel reliability, as you've very easily demonstrated.

Quoted 1 line · Christoph Lameter

Really? That means we can no longer even allocate stacks for forking.

I think I'm running with 4k stacks...

Minimally, SLUB by default should continue to use order-0 pages. Peter has managed to bust order-1 pages with mem=128MB. Admittedly, it was a really hostile workload but the point remains. It was artifically worked around with min_free_kbytes (value set based on pageblock_order, could also have been artifically worked around by dropping pageblock_order) and he eventually caused order-0 failures so the workload is pretty damn hostile to everything.

Quoted 11 lines · Andrew Morton

Quoted 2 lines

atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

Oh OK.

I thought we'd already fixed slub so that it didn't do that. Maybe that fix is in -mm but I don't think so.

Trying to do atomic order-1 allocations on behalf of arbitray slab caches just won't fly - this is a significant degradation in kernel reliability, as you've very easily demonstrated.

Ummm... SLAB also does order 1 allocations. We have always done them.

See mm/slab.c

/*
* Do not go above this order unless 0 objects fit into the slab. */
#define BREAK_GFP_ORDER_HI 1
#define BREAK_GFP_ORDER_LO 0
static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;

Do slab and slub use the same underlying page size for each slab?

Single data point: the CONFIG_SLAB boxes which I have access to here are using order-0 for radix_tree_node, so they won't be failing in the way in which Peter's machine is.

Quoted 1 line · Andrew Morton

Do slab and slub use the same underlying page size for each slab?

SLAB cannot pack objects as dense as SLUB and they have different algorithm to make the choice of order. Thus the number of objects per slab may vary between SLAB and SLUB and therefore also the choice of order to store these objects.

Quoted 3 lines

Single data point: the CONFIG_SLAB boxes which I have access to here are using order-0 for radix_tree_node, so they won't be failing in the way in which Peter's machine is.

Upstream SLUB uses order 0 allocations for the radix tree.

MM varies
because the use of higher order allocs is more loose if the mobility algorithms are found to be active:

2.6.23-rc8:

Name Objects Objsize Space Slabs/Part/Cpu O/S O %Fr %Ef Flg\
radix_tree_node 14281 552 9.9M 2432/948/1 7 0 38 79

Ah. So the already-dropped slub-exploit-page-mobility-to-increase-allocation-order.patch was the culprit?

Quoted 16 lines · On Mon, 1 Oct 2007 13:55:29 -0700 (PDT) Christoph Lameter <[email protected]>…

Quoted 11 lines · Andrew Morton

Quoted 2 lines

atomic allocations. And with SLUB using higher order pages, atomic !0 order allocations will be very very common.

Oh OK.

I thought we'd already fixed slub so that it didn't do that. Maybe that fix is in -mm but I don't think so.

Trying to do atomic order-1 allocations on behalf of arbitray slab caches just won't fly - this is a significant degradation in kernel reliability, as you've very easily demonstrated.

Ummm... SLAB also does order 1 allocations. We have always done them.

Quoted 8 lines

See mm/slab.c

/*
* Do not go above this order unless 0 objects fit into the slab. */
#define BREAK_GFP_ORDER_HI 1
#define BREAK_GFP_ORDER_LO 0
static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;

Do slab and slub use the same underlying page size for each slab?

Single data point: the CONFIG_SLAB boxes which I have access to here are using order-0 for radix_tree_node, so they won't be failing in the way in which Peter's machine is.

I've never ever before seen reports of page allocation failures in the radix-tree node allocation code, and that's the bottom line. This is just a drop-dead must-fix show-stopping bug. We cannot rely upon atomic order-1 allocations succeeding so we cannot use them for radix-tree nodes. Nor for lots of other things which we have no chance of identifying.

Peter, is this bug -mm only, or is 2.6.23 similarly failing?

Quoted 4 lines · Peter Zijlstra

Quoted 1 line · Christoph Lameter

Really? That means we can no longer even allocate stacks for forking.

I think I'm running with 4k stacks...

4k stacks will never fly on an SGI x86_64 NUMA configuration given the additional data that may be kept on the stack. We are currently considering to go from 8k to 16k (or even 32k) to make things work. So having the ability to put the stacks in vmalloc space may be something to look at.

Quoted 3 lines · Nick Piggin

I thought it was slower. Have you fixed the performance regression? (OK, I read further down that you are still working on it but not confirmed yet...)

The problem is with the weird way of Intel testing and communication. Every 3-6 month or so they will tell you the system is X% up or down on arch Y (and they wont give you details because its somehow secret). And then there are conflicting statements by the two or so performance test departments. One of them repeatedly assured me that they do not see any regressions.

Quoted 5 lines

OK, so long as it isn't going to depend on using higher order pages, that's fine. (if they help even further as an optional thing, that's fine too. You can turn them on your huge systems and not even bother about adding this vmap fallback -- you won't have me to nag you about these purely theoretical issues).

Well the vmap fallback is generally useful AFAICT. Higher order allocations are common on some of our platforms. Order 1 failures even affect essential things like stacks that have nothing to do with SLUB and the LBS patchset.

The problem is with the weird way of Intel testing and communication. Every 3-6 month or so they will tell you the system is X% up or down on arch Y (and they wont give you details because its somehow secret). And then there are conflicting statements by the two or so performance test departments. One of them repeatedly assured me that they do not see any regressions.

So, on "a well-known OLTP benchmark which prohibits publishing absolute numbers" and on an x86-64 system (I don't think exactly which model is important), we're seeing *6.51%* performance loss on slub vs slab. This is with a 2.6.23-rc3 kernel. Tuning the boot parameters, as you've asked for before (slub_min_order=2, slub_max_order=4, slub_min_objects=8) gets back 0.38% of that. It's still down 6.13% over slab.

Now, where do we go next? I suspect that 2.6.23-rc9 has significant changes since -rc3, but I'd like to confirm that before kicking off another (expensive) run. Please, tell me what useful kernels are to test.

Quoted 6 lines · Matthew Wilcox

So, on "a well-known OLTP benchmark which prohibits publishing absolute numbers" and on an x86-64 system (I don't think exactly which model is important), we're seeing *6.51%* performance loss on slub vs slab. This is with a 2.6.23-rc3 kernel. Tuning the boot parameters, as you've asked for before (slub_min_order=2, slub_max_order=4, slub_min_objects=8) gets back 0.38% of that. It's still down 6.13% over slab.

Yeah the fastpath vs. slow path is not the issue as Siddha and I concluded earlier. Seems that we are mainly seeing cacheline bouncing due to two cpus accessing meta data in the same page struct. The patches in MM that are scheduled to be merged for .24 address that issue. I have repeatedly asked that these patches be tested. The patches were posted months ago.

Quoted 6 lines

Yeah the fastpath vs. slow path is not the issue as Siddha and I concluded earlier. Seems that we are mainly seeing cacheline bouncing due to two cpus accessing meta data in the same page struct. The patches in MM that are scheduled to be merged for .24 address that issue. I have repeatedly asked that these patches be tested. The patches were posted months ago.

I just checked with the guys who did the test. When I said -rc3, I mis-spoke; this is 2.6.23-rc3 *plus* the patches which Suresh agreed to test for you.

Yeah the fastpath vs. slow path is not the issue as Siddha and I concluded earlier. Seems that we are mainly seeing cacheline bouncing due to two cpus accessing meta data in the same page struct. The patches in MM that are scheduled to be merged for .24 address

Ok every time something says anything not 100% positive about SLUB you come back with "but it's fixed in the next patch set"... *every time*.

Quoted 4 lines · On Thu, 4 Oct 2007 10:38:15 -0700 (PDT) Christoph Lameter <[email protected]>…

Yeah the fastpath vs. slow path is not the issue as Siddha and I concluded earlier. Seems that we are mainly seeing cacheline bouncing due to two cpus accessing meta data in the same page struct. The patches in MM that are scheduled to be merged for .24 address

Ok every time something says anything not 100% positive about SLUB you come back with "but it's fixed in the next patch set"... *every time*.

To be honest, to me that sounds that SLUB isn't ready for prime time yet, or at least not ready to be the only one in town...

The day that the answer is "the kernel.org slub is fixing all the issues" is when it's ready..

I was not aware of that. Would it be possible for you to summarize all the test data that you have right now about SLUB vs. SLAB with the patches listed? Exactly what kernel version and what version of the per cpu patches were tested?

Was the page allocator pass through patchset
separately applied as I requested?

Finally: Is there some way that I can reproduce the tests on my machines?

We have three runs, all with 2.6.23-rc3 plus the patches that Suresh applied from 20070922. The first run is with slab. The second run is with SLUB and the third run is SLUB plus the tuning parameters you recommended.

I have a spreadsheet with Vtune data in it that was collected during each of these test runs, so we can see which functions are the hottest. I can grab that data and send it to you, if that's interesting.

Quoted 2 lines

Was the page allocator pass through patchset
separately applied as I requested?

I don't believe so. Suresh?

I think for future tests, it would be easiest if you send me a git reference. That way we will all know precisely what is being tested.

Quoted 1 line

Finally: Is there some way that I can reproduce the tests on my machines?

As usual for these kinds of setups ... take a two-CPU machine, 64GB of memory, half a dozen fibre channel adapters, about 3000 discs, a commercial database, a team of experts for three months worth of tuning ...

I don't know if anyone's tried to replicate a benchmark like this using Postgres. Would be nice if they have ...

Quoted 4 lines

Quoted 2 lines

Was the page allocator pass through patchset
separately applied as I requested?

I don't believe so. Suresh?

If it was a git pull then the pass through was included and never taken out.

Ok every time something says anything not 100% positive about SLUB you come back with "but it's fixed in the next patch set"... *every time*.

Quoted 1 line

Finally: Is there some way that I can reproduce the tests on my machines?

As usual for these kinds of setups ... take a two-CPU machine, 64GB of memory, half a dozen fibre channel adapters, about 3000 discs, a commercial database, a team of experts for three months worth of tuning ...

There comes a point where it is the reporter's responsibility to help the developer come up with a publishable test case the developer can use to work on fixing the problem and help ensure it stays fixed.

Using an unpublishable benchmark, whose results even cannot be published, really stretches the limits of "reasonable" don't you think?

Anything, I do mean anything, can be simulated using small test programs. Pointing at a big fancy machine with lots of storage and disk is a passive aggressive way to avoid the real issues, in that nobody is putting forth the effort to try and come up with an at least publishable test case that Christoph can use to help you guys.

If coming up with a reproducable and publishable test case is the difference between this getting fixed and it not getting fixed, are you going to invest the time to do that?

Quoted 3 lines

There comes a point where it is the reporter's responsibility to help the developer come up with a publishable test case the developer can use to work on fixing the problem and help ensure it stays fixed.

That's a lot of effort. Is it more effort than doing some remote debugging with Christoph? I don't know.

Anything, I do mean anything, can be simulated using small test programs.

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

Yet here we stand. Christoph is aggressively trying to get slab removed from the tree. There is a testcase which shows slub performing worse than slab. It's not my fault I can't publish it. And just because I can't publish it doesn't mean it doesn't exist.

Slab needs to not get removed until slub is as good a performer on this benchmark.

From: Chuck Ebbert <[email protected]>
Date: Thu, 04 Oct 2007 17:02:17 -0400

Quoted 3 lines

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

You repeatedly read zeros from a smaller disk into the same amount of memory, and sort that as if it were real data instead.

Quoted 7 lines

From: Chuck Ebbert <[email protected]>
Date: Thu, 04 Oct 2007 17:02:17 -0400

Quoted 3 lines

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

Quoted 2 lines

You repeatedly read zeros from a smaller disk into the same amount of memory, and sort that as if it were real data instead.

You've just replaced 3000 concurrent streams of data with a single stream. That won't test the memory allocator's ability to allocate memory to many concurrent users very well.

From: Chuck Ebbert <[email protected]> Date: Thu, 04 Oct 2007 17:47:48 -0400

Quoted 8 lines · David Miller

Quoted 7 lines

From: Chuck Ebbert <[email protected]> Date: Thu, 04 Oct 2007 17:02:17 -0400

Quoted 3 lines

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

Quoted 6 lines

Quoted 2 lines

You repeatedly read zeros from a smaller disk into the same amount of memory, and sort that as if it were real data instead.

You've just replaced 3000 concurrent streams of data with a single stream. That won't test the memory allocator's ability to allocate memory to many concurrent users very well.

You've kindly removed my "thinking outside of the box" comment.

The point is was not that my specific suggestion would be perfect, but that if you used your creativity and thought in similar directions you might find a way to do it.

People are too narrow minded when it comes to these things, and that's the problem I want to address.

Using an unpublishable benchmark, whose results even cannot be published, really stretches the limits of "reasonable" don't you think?

This "SLUB isn't ready yet" bullshit is just a shamans dance which distracts attention away from the real problem, which is that a reproducable, publishable test case, is not being provided to the developer so he can work on fixing the problem.

I can tell you this thing would be fixed overnight if a proper test case had been provided by now.

Yet here we stand. Christoph is aggressively trying to get slab removed from the tree. There is a testcase which shows slub performing worse than slab. It's not my fault I can't publish it. And just because I can't publish it doesn't mean it doesn't exist.

But this is just a preposterous position to put him in. If there's no reproduceable test case, then why should he care that one program he can't even see works badly? If you care, you fix it.

So there could still be page struct contention left if multiple processors frequently and simultaneously free to the same slab and that slab is not the per cpu slab of a cpu. That could be addressed by optimizing the object free handling further to not touch the page struct even if we miss the per cpu slab.

That get_partial* is far up indicates contention on the list lock that should be addressable by either increasing the slab size or by changing the object free handling to batch in some form.

This is an SMP system right? 2 cores with 4 cpus each? The main loop is always hitting on the same slabs? Which slabs would this be? Am I right in thinking that one process allocates objects and then lets multiple other processors do work and then the allocated object is freed from a cpu that did not allocate the object? If neighboring objects in one slab are allocated on one cpu and then are almost simultaneously freed from a set of different cpus then this may be explain the situation. -

Quoted 5 lines

But this is just a preposterous position to put him in. If there's no reproduceable test case, then why should he care that one program he can't
even see works badly? If you care, you fix it.

People have been trying for years to make reproducible test cases for huge and complex workloads. It doesn't work. The tests that do work take weeks to run and need to be carefully validated before they can be officially released. The open source community can and should be working on similar tests, but they will never be simple.

Quoted 18 lines · David Miller

From: Chuck Ebbert <[email protected]> Date: Thu, 04 Oct 2007 17:47:48 -0400

Quoted 8 lines · David Miller

Quoted 7 lines

From: Chuck Ebbert <[email protected]> Date: Thu, 04 Oct 2007 17:02:17 -0400

Quoted 3 lines

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

Quoted 6 lines

Quoted 2 lines

You repeatedly read zeros from a smaller disk into the same amount of memory, and sort that as if it were real data instead.

You've just replaced 3000 concurrent streams of data with a single stream. That won't test the memory allocator's ability to allocate memory to many concurrent users very well.

Quoted 8 lines

You've kindly removed my "thinking outside of the box" comment.

The point is was not that my specific suggestion would be perfect, but that if you used your creativity and thought in similar directions you might find a way to do it.

People are too narrow minded when it comes to these things, and that's the problem I want to address.

And it's a good point, too, because often problems to one person are a no-brainer to someone else.

Creating lots of "fake" disks is trivial to do, IMO. Use loopback on sparse files containing sparse filesxi, use ramdisks containing sparse files or write a sparse dm target for sparse block device mapping, etc. I'm sure there's more than the few I just threw out...

I'd like to second Davids emails here, this is a serious problem. Having a reproducible test case lowers the barrier for getting the problem fixed by orders of magnitude. It's the difference between the problem getting fixed in a day or two and it potentially lingering for months, because email ping-pong takes forever and "the test team has moved on to other tests, we'll let you know the results of test foo in 3 weeks time when we have a new slot on the box" just removing any developer motivation to work on the issue.

Hi,

Quoted 8 lines · Jens Axboe

I'd like to second Davids emails here, this is a serious problem. Having a reproducible test case lowers the barrier for getting the problem fixed by orders of magnitude. It's the difference between the problem getting fixed in a day or two and it potentially lingering for months, because email ping-pong takes forever and "the test team has moved on to other tests, we'll let you know the results of test foo in 3 weeks time when we have a new slot on the box" just removing any developer motivation to work on the issue.

What I don't understand is that why don't the people who _have_ access to the test case fix the problem? Unlike slab, slub is not a pile of crap that only Christoph can hack on...

Writing a small test module to exercise slub/slab in various ways (allocating from all cpus freeing from one, as described) should not be too hard. Perhaps that would be enough to find this performance discrepancy between slab and slub?

I'd like to second Davids emails here, this is a serious problem. Having a reproducible test case lowers the barrier for getting the problem fixed by orders of magnitude. It's the difference between the problem getting fixed in a day or two and it potentially lingering for months, because email ping-pong takes forever and "the test team has moved on to other tests, we'll let you know the results of test foo in 3 weeks time when we have a new slot on the box" just removing any developer motivation to work on the issue.

Quoted 8 lines · Jens Axboe

I'd like to second Davids emails here, this is a serious problem. Having a reproducible test case lowers the barrier for getting the problem fixed by orders of magnitude. It's the difference between the problem getting fixed in a day or two and it potentially lingering for months, because email ping-pong takes forever and "the test team has moved on to other tests, we'll let you know the results of test foo in 3 weeks time when we have a new slot on the box" just removing any developer motivation to work on the issue.

I vaguely remembered something called orasim, so I went looking for it. I found http://oss.oracle.com/~wcoekaer/orasim/ which is dated from 2004, and I found http://oss.oracle.com/projects/orasimjobfiles/ which seems to be a stillborn project. Is there anything else I should know about orasim? ;-)

Quoted 5 lines · Jens Axboe

Writing a small test module to exercise slub/slab in various ways (allocating from all cpus freeing from one, as described) should not be too hard. Perhaps that would be enough to find this performance discrepancy between slab and slub?

You could simulate that by just sending packets using unix sockets between threads bound to different CPUs. Sending a packet allocates; receiving deallocates.

But it's not clear that will really simulate the cache bounce environment of the database test. I don't think all passing of data between CPUs using slub objects is slow.

I vaguely remembered something called orasim, so I went looking for it. I found http://oss.oracle.com/~wcoekaer/orasim/ which is dated from 2004, and I found http://oss.oracle.com/projects/orasimjobfiles/ which seems to be a stillborn project. Is there anything else I should know about orasim? ;-)

It might not, it might. The point is trying to isolate the problem and making a simple test case that could be used to reproduce it, so that Christoph (or someone else) can easily fix it.

Quoted 3 lines · David Miller

Anything, I do mean anything, can be simulated using small test programs.

How do you simulate reading 100TB of data spread across 3000 disks, selecting 10% of it using some criterion, then sorting and summarizing the result?

Focus on the slab allocator usage, instrument it, record a trace, generate a statistical model that matches, and write a small programm/kernel module that has the same allocation pattern. Then verify this statistical workload still shows the same performance difference.

Easy: no
Doable: yes