Skip to content

mm: Page Replacement Policy Framework

Peter Zijlstra linux-mm lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest34 patches 16 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/34mm: kill-page-activate.patchinclude/linux/swap.h mm/swapfile.c+2 -30 replies
2/34mm: page-replace-kconfig-makefile.patchmm/Kconfig mm/Makefile mm/useonce.c+16 -01 reply
3/34mm: page-replace-insert.patchfs/cifs/file.c fs/exec.c fs/mpage.c +16 more+229 -1800 replies
4/34mm: page-replace-use_once.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/filemap.c+17 -10 replies
5/34mm: page-replace-generic-pagevec.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/swap.c +1 more+53 -640 replies
6/34mm: page-replace-activate.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/vmscan.c+72 -290 replies
7/34mm: page-replace-move-macros.patchinclude/linux/mm_page_replace.h mm/vmscan.c+30 -300 replies
8/34mm: page-replace-move-scan_control.patchinclude/linux/mm_page_replace.h mm/vmscan.c+30 -300 replies
9/34mm: page-replace-move-isolate_lru_pages.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h include/linux/swap.h +3 more+92 -810 replies
10/34mm: page-replace-reinsert.patchinclude/linux/mm_page_replace.h mm/mempolicy.c mm/useonce.c +1 more+15 -300 replies
11/34mm: page-replace-should_reclaim_mapped.patchmm/vmscan.c+46 -400 replies
12/34mm: page-replace-shrink.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h include/linux/swap.h +2 more+241 -2390 replies
13/34mm: page-replace-mark-accessed.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/swap.c+28 -270 replies
14/34mm: page-replace-remove-mm_inline.patchinclude/linux/mm_inline.h include/linux/mm_page_replace.h include/linux/mm_use_once_policy.h +3 more+35 -450 replies
15/34mm: page-replace-rotate.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/swap.c+10 -70 replies
16/34mm: page-replace-init.patchinclude/linux/mm_page_replace.h init/main.c mm/page_alloc.c +1 more+21 -60 replies
17/34mm: page-replace-info.patchinclude/linux/mm_page_replace.h mm/page_alloc.c mm/useonce.c+57 -420 replies
18/34mm: page-replace-counts.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/page_alloc.c +2 more+28 -140 replies
19/34mm: page-replace-data.patchinclude/linux/mm_page_replace_data.h include/linux/mm_use_once_data.h include/linux/mm_use_once_policy.h +2 more+68 -430 replies
20/34mm: page-replace-pg_flags.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h include/linux/page-flags.h +4 more+38 -150 replies
21/34mm: page-replace-nonresident.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/memory.c +2 more+46 -20 replies
22/34mm: page-replace-shrink-new.patchinclude/linux/mm_page_replace.h include/linux/mm_use_once_policy.h mm/vmscan.c+51 -00 replies
23/34mm: page-replace-documentation.patchDocumentation/vm/page_replacement_api.txt+216 -00 replies
24/34mm: sum_cpu_var.patchinclude/linux/percpu.h+5 -00 replies
25/34mm: kswapd-writeout-wait.patchinclude/linux/mm_page_replace.h mm/vmscan.c+9 -20 replies
26/34mm: clockpro-nonresident.patchinclude/linux/nonresident.h mm/nonresident.c+179 -00 replies
27/34mm: clockpro-ignore_token.patchinclude/linux/mm_use_once_policy.h include/linux/rmap.h mm/rmap.c +1 more+20 -140 replies
28/34mm: clockpro-PG_reclaim2.patchinclude/linux/page-flags.h mm/hugetlb.c mm/page_alloc.c+7 -20 replies
29/34mm: clockpro-clockpro.patchinclude/linux/mm_clockpro_data.h include/linux/mm_clockpro_policy.h include/linux/mm_page_replace.h +4 more+1029 -00 replies
30/34mm: cart-nonresident.patchinclude/linux/nonresident-cart.h mm/nonresident-cart.c+396 -00 replies
31/34mm: cart-PG_reclaim3.patchinclude/linux/page-flags.h mm/hugetlb.c mm/page_alloc.c+6 -10 replies
32/34mm: cart-cart.patchinclude/linux/mm_cart_data.h include/linux/mm_cart_policy.h include/linux/mm_page_replace.h +4 more+857 -40 replies
33/34mm: cart-r.patchinclude/linux/mm_cart_data.h include/linux/mm_cart_policy.h include/linux/mm_page_replace.h +4 more+78 -110 replies
34/34mm: random.patchinclude/linux/mm_page_replace.h include/linux/mm_page_replace_data.h include/linux/mm_random_data.h +4 more+358 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 00/34] mm: Page Replacement Policy Framework

This patch-set introduces a page replacement policy framework and 4 new experimental policies.

The page replacement algorithm determines which pages to swap out. The current algorithm has some problems that are increasingly noticable, even on desktop workloads. As said, this patch-set introduces 4 new algorithms.

Patches 01 - 25:

Introduction of the general framework. Piece by piece the current
use-once LRU-2Q policy is isolated. With each patch a piece of the framework API is introduced.

Patches 26 - 29:

Adds a policy based on CLOCKPro. (http://linux-mm.org/PeterZClockPro2)

Patches 30 - 32:

Adds a policy based on CART. (http://linux-mm.org/PeterZCart)

Patch 33:

Adds a variation of the CART policy that tries to incorporate
cyclic access patterns.

Patch 34:

Adds a random page replacement policy, simple policy that uses a simple
PRNG to take the decision. More of a toy example than a real alternative.

Individual patches and a rollup can be found here:
http://programming.kicks-ass.net/kernel-patches/page-replace/

Measurements:

(Walltime, so lower is better)

cyclic-anon ; Cyclic access pattern with anonymous memory.
(http://programming.kicks-ass.net/benchmarks/cyclic-anon.c)

2.6.16-rc6              14:28
2.6.16-rc6-useonce      15:11
2.6.16-rc6-clockpro     10:51

2.6.16-rc6-cart 8:55
2.6.16-rc6-random 1:09:50

cyclic-file ; Cyclic access pattern with file backed memory.
(http://programming.kicks-ass.net/benchmarks/cyclic-file.c)

2.6.16-rc6 11:24
2.6.16-rc6-clockpro 8:14
2.6.16-rc6-cart 8:09

webtrace ; Replay of an IO trace from the Umass trace repository
(http://programming.kicks-ass.net/benchmarks/spc/)

2.6.16-rc6 8:27
2.6.16-rc6-useonce 8:24

2.6.16-rc6-clockpro     10:23
2.6.16-rc6-cart         15:30
2.6.16-rc6-random       15:52

mdb-bench ; Low frequency benchmark.
(http://linux-mm.org/PageReplacementTesting)

2.6.16-rc6            4:20:44
2.6.16-rc6 (mlock)    3:52:15
2.6.16-rc6-useonce    4:20:59
2.6.16-rc6-clockpro   3:56:17
2.6.16-rc6-cart       4:11:54
2.6.16-rc6-random     5:21:30

(I should do more runs to get error bounds on these values,
this is the avg of 3)

Aside from tweaking the policies, the big thing left is NUMA-ify the nonresident page trackers.

The results merit further attention, please consider for 2.6.18.

Peter

---

 Documentation/vm/page_replacement_api.txt |  216 +++++++
 fs/cifs/file.c                            |    4 
 fs/exec.c                                 |    4 
 fs/mpage.c                                |    5 
 fs/ntfs/file.c                            |    4 
 fs/ramfs/file-nommu.c                     |    2 
 include/linux/mm_cart_data.h              |   39 +
 include/linux/mm_cart_policy.h            |  141 ++++
 include/linux/mm_clockpro_data.h          |   21 
 include/linux/mm_clockpro_policy.h        |  143 +++++
 include/linux/mm_inline.h                 |   39 -
 include/linux/mm_page_replace.h           |  146 +++++
 include/linux/mm_page_replace_data.h      |   19 
 include/linux/mm_random_data.h            |    9 
 include/linux/mm_random_policy.h          |   47 +
 include/linux/mm_use_once_data.h          |   16 
 include/linux/mm_use_once_policy.h        |  175 ++++++
 include/linux/mmzone.h                    |    8 
 include/linux/nonresident-cart.h          |   34 +
 include/linux/nonresident.h               |   12 
 include/linux/page-flags.h                |   11 
 include/linux/pagevec.h                   |    8 
 include/linux/percpu.h                    |    5 
 include/linux/rmap.h                      |    4 
 include/linux/swap.h                      |   10 
 init/main.c                               |    2 
 mm/Kconfig                                |   32 +
 mm/Makefile                               |    6 
 mm/cart.c                                 |  723 +++++++++++++++++++++++++
 mm/clockpro.c                             |  855 ++++++++++++++++++++++++++++++
 mm/filemap.c                              |   20 
 mm/hugetlb.c                              |    5 
 mm/memory.c                               |   42 +
 mm/mempolicy.c                            |   13 
 mm/mmap.c                                 |    5 
 mm/nonresident-cart.c                     |  362 ++++++++++++
 mm/nonresident.c                          |  167 +++++
 mm/page_alloc.c                           |   76 --
 mm/random_policy.c                        |  292 ++++++++++
 mm/readahead.c                            |    9 
 mm/rmap.c                                 |   26 
 mm/shmem.c                                |    2 
 mm/swap.c                                 |  206 +------
 mm/swap_state.c                           |    6 
 mm/swapfile.c                             |   17 
 mm/useonce.c                              |  489 +++++++++++++++++
 mm/vmscan.c                               |  552 +++----------------
 47 files changed, 4226 insertions(+), 803 deletions(-)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>