All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH -mm v2 00/11] mm: scalable and unified arch_get_unmapped_area
@ 2012-06-21 21:57 ` Rik van Riel
  0 siblings, 0 replies; 90+ messages in thread
From: Rik van Riel @ 2012-06-21 21:57 UTC (permalink / raw)
  To: linux-mm
  Cc: akpm, aarcange, peterz, minchan, kosaki.motohiro, andi, hannes,
	mel, linux-kernel

A long time ago, we decided to limit the number of VMAs per
process to 64k. As it turns out, there actually are programs
using tens of thousands of VMAs.

The linear search in arch_get_unmapped_area and
arch_get_unmapped_area_topdown can be a real issue for
those programs. 

This patch series aims to fix the scalability issue by
tracking the size of each free hole in the VMA rbtree,
propagating the free hole info up the tree. 

Another major goal is to put the bulk of the necessary
arch_get_unmapped_area(_topdown) functionality into one
set of functions, so we can eliminate the custom large
functions per architecture, sticking to a few much smaller
architecture specific functions instead.

In this version I have only gotten rid of the x86, ARM, SH
and MIPS arch-specific code, and am already showing a
fairly promising diffstat:

 arch/arm/include/asm/pgtable.h    |    6 
 arch/arm/mm/init.c                |    4 
 arch/arm/mm/mmap.c                |  217 ------------------
 arch/mips/include/asm/page.h      |    2 
 arch/mips/include/asm/pgtable.h   |    7 
 arch/mips/mm/mmap.c               |  177 --------------
 arch/sh/include/asm/pgtable.h     |    4 
 arch/sh/mm/mmap.c                 |  219 ------------------
 arch/x86/include/asm/elf.h        |    3 
 arch/x86/include/asm/pgtable_64.h |    4 
 arch/x86/kernel/sys_x86_64.c      |  200 ++--------------
 arch/x86/vdso/vma.c               |    2 
 include/linux/mm_types.h          |   19 +
 include/linux/rbtree.h            |   12 +
 include/linux/sched.h             |   13 +
 lib/rbtree.c                      |   46 +++
 mm/internal.h                     |    5 
 mm/mmap.c                         |  449 +++++++++++++++++++++++++++++---------
 18 files changed, 478 insertions(+), 911 deletions(-)

v2: address reviewers' comments
    optimize propagating info up the VMA tree (30% faster at frag test)
    add SH architecture

TODO:
- eliminate arch-specific functions for more architectures
- integrate hugetlbfs alignment (with Andi Kleen's patch?)

Performance

Testing performance with a benchmark that allocates tens
of thousands of VMAs, unmaps them and mmaps them some more
in a loop, shows promising results.

Vanilla 3.4 kernel:
$ ./agua_frag_test_64
..........

Min Time (ms): 6
Avg. Time (ms): 294.0000
Max Time (ms): 609
Std Dev (ms): 113.1664
Standard deviation exceeds 10

With -v2 patches:
$ ./agua_frag_test_64
..........

Min Time (ms): 12
Avg. Time (ms): 31.0000
Max Time (ms): 42
Std Dev (ms): 3.3648
All checks pass

The total run time of the test goes down by about a
factor 5.  More importantly, the worst case performance
of the loop (which is what really hurt some applications)
has gone down by about a factor 14.


^ permalink raw reply	[flat|nested] 90+ messages in thread

end of thread, other threads:[~2012-07-04 10:13 UTC | newest]

Thread overview: 90+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-06-21 21:57 [PATCH -mm v2 00/11] mm: scalable and unified arch_get_unmapped_area Rik van Riel
2012-06-21 21:57 ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA rbtree Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-22  9:57   ` Peter Zijlstra
2012-06-22  9:57     ` Peter Zijlstra
2012-06-22  9:58   ` Peter Zijlstra
2012-06-22  9:58     ` Peter Zijlstra
2012-06-22 14:11     ` Rik van Riel
2012-06-22 14:11       ` Rik van Riel
2012-06-22 14:13       ` Peter Zijlstra
2012-06-22 14:13         ` Peter Zijlstra
2012-06-22 14:25         ` Rik van Riel
2012-06-22 14:25           ` Rik van Riel
2012-06-22 14:37           ` Peter Zijlstra
2012-06-22 14:37             ` Peter Zijlstra
2012-06-22 15:41             ` Rik van Riel
2012-06-22 15:41               ` Rik van Riel
2012-06-25 19:29               ` Peter Zijlstra
2012-06-25 19:29                 ` Peter Zijlstra
2012-06-25 21:52                 ` Rik van Riel
2012-06-25 21:52                   ` Rik van Riel
2012-06-26  8:31                   ` Peter Zijlstra
2012-06-26  8:31                     ` Peter Zijlstra
2012-06-26 13:05                     ` Rik van Riel
2012-06-26 13:05                       ` Rik van Riel
2012-06-26 13:45                       ` Peter Zijlstra
2012-06-26 13:45                         ` Peter Zijlstra
2012-06-26 15:49                         ` Rik van Riel
2012-06-26 15:49                           ` Rik van Riel
2012-06-27 12:27                           ` Peter Zijlstra
2012-06-27 12:27                             ` Peter Zijlstra
2012-06-26  8:37                   ` Peter Zijlstra
2012-06-26  8:37                     ` Peter Zijlstra
2012-06-22 10:02   ` Peter Zijlstra
2012-06-22 10:02     ` Peter Zijlstra
2012-06-29 23:46   ` Michel Lespinasse
2012-06-29 23:46     ` Michel Lespinasse
2012-07-03 21:37     ` Rik van Riel
2012-07-03 21:37       ` Rik van Riel
2012-07-03 23:16       ` Michel Lespinasse
2012-07-03 23:16         ` Michel Lespinasse
2012-07-04 10:12         ` Peter Zijlstra
2012-07-04 10:12           ` Peter Zijlstra
2012-06-21 21:57 ` [PATCH -mm v2 02/11] mm: rearrange vm_area_struct for fewer cache misses Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 03/11] mm: vma_adjust: only call adjust_free_gap when needed Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 04/11] rbtree: add helpers to find nearest uncle node Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-22  9:49   ` Peter Zijlstra
2012-06-22  9:49     ` Peter Zijlstra
2012-06-21 21:57 ` [PATCH -mm v2 05/11] mm: get unmapped area from VMA tree Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-30  1:33   ` Michel Lespinasse
2012-06-30  1:33     ` Michel Lespinasse
2012-07-03  0:23     ` Michel Lespinasse
2012-07-03  0:23       ` Michel Lespinasse
2012-06-30  2:42   ` Michel Lespinasse
2012-06-30  2:42     ` Michel Lespinasse
2012-06-21 21:57 ` [PATCH -mm v2 06/11] mm: arbitrary address ranges for arch_get_unmapped_area Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 07/11] mm: make cache alignment code generic Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-30  2:22   ` Michel Lespinasse
2012-06-30  2:22     ` Michel Lespinasse
2012-06-21 21:57 ` [PATCH -mm v2 08/11] mm: remove x86 arch_get_unmapped_area(_topdown) Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 09/11] mm: remove MIPS arch_get_unmapped_area code Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57 ` [PATCH -mm v2 10/11] mm: remove ARM arch_get_unmapped_area functions Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-22 22:27   ` Russell King - ARM Linux
2012-06-22 22:27     ` Russell King - ARM Linux
2012-06-23 17:50     ` Johannes Weiner
2012-06-23 17:50       ` Johannes Weiner
2012-06-21 21:57 ` [PATCH -mm v2 11/11] mm: remove SH " Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-21 21:57   ` Rik van Riel
2012-06-25  2:11   ` Paul Mundt
2012-06-25  2:11     ` Paul Mundt
2012-06-25  2:11     ` Paul Mundt
2012-06-22 14:24 ` [PATCH -mm v2 00/11] mm: scalable and unified arch_get_unmapped_area John Stoffel
2012-06-22 14:24   ` John Stoffel
2012-06-22 21:47   ` Andrew Morton
2012-06-22 21:47     ` Andrew Morton
2012-06-23 16:03     ` John Stoffel
2012-06-23 16:03       ` John Stoffel
2012-06-22 15:01 ` Johannes Weiner
2012-06-22 15:01   ` Johannes Weiner

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.