Earlier this year, Rik proposed using augmented rbtrees to optimize our search for a suitable unmapped area during mmap(). This prompted my work on improving the augmented rbtree code. Rik doesn't seem to have time to follow up on his idea at this time, so I'm sending this series to revive the idea. These changes are against v3.7-rc3. I have only converted the generic and x86_64 search implementations so far, as I'm really looking for comments on the general approach; however it shouldn't be too difficult to convert other architectures in the same way (and eventually the drivers that define their own f_op->get_unmapped_area method as well). Patch 1 augments the VMA rbtree with a new rb_subtree_gap field, indicating the length of the largest gap immediately preceding any VMAs in a subtree. Patch 2 adds new checks to CONFIG_DEBUG_VM_RB to verify the above information is correctly maintained. Patch 3 rearranges the vm_area_struct layout so that rbtree searches only need data that is contained in the first cacheline (this one is from Rik's original patch series) Patch 4 adds a generic vm_unmapped_area() search function, which allows for searching for an address space of any desired length, within [low; high[ address constraints, with any desired alignment. The generic arch_get_unmapped_area[_topdown] functions are also converted to use this. Patch 5 converts the x86_64 arch_get_unmapped_area[_topdown] functions to use vm_unmapped_area() as well. Patch 6 fixes cache coloring on x86_64, as suggested by Rik in his previous series. My own feel for this series is that I'm fairly confident in the robustness of my vm_unmapped_area() implementation; however I would like to confirm that people are happy with this new interface. Also the code that figures out what constraints to pass to vm_unmapped_area() is a bit odd; I have tried to make the constraints match the behavior of the current code but it's not clear to me if that behavior makes sense in the first place. There is also the question of performance. I remember from IRC conversations that someone (I think it was Mel ?) had found some regressions with Rik's prior proposal. My current proposal is significantly faster at updating the rbtrees; however there is still the fact that vm_unmapped_area() does not use a free area cache as the old brute-force implementation did. I don't expect that to be a problem, but I have not confirmed yet if the prior regressions are gone (and if they are still present, one would want to find out if they are introduced by rbtree maintainance in Patch 1, or by removing the free area cache as part of patches 4/5). Michel Lespinasse (5): mm: augment vma rbtree with rb_subtree_gap mm: check rb_subtree_gap correctness mm: vm_unmapped_area() lookup function mm: use vm_unmapped_area() on x86_64 architecture mm: fix cache coloring on x86_64 Rik van Riel (1): mm: rearrange vm_area_struct for fewer cache misses arch/x86/include/asm/elf.h | 6 +- arch/x86/kernel/sys_x86_64.c | 151 +++----------- arch/x86/vdso/vma.c | 2 +- include/linux/mm.h | 31 +++ include/linux/mm_types.h | 19 ++- mm/mmap.c | 450 ++++++++++++++++++++++++++++++++---------- 6 files changed, 423 insertions(+), 236 deletions(-) -- 1.7.7.3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>