Skip to content

RFC Per-cpu page allocator replacement prototype

Mel Gorman linux-mm lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest22 patches 10 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/22mm: page allocator: Lookup pageblock migratetype with IRQs enabled during freemm/page_alloc.c+2 -10 replies
2/22mm: page allocator: Push down where IRQs are disabled during page freemm/page_alloc.c+10 -110 replies
3/22mm: page allocator: Use unsigned int for order in more placesinclude/linux/mmzone.h mm/page_alloc.c+23 -200 replies
4/22mm: page allocator: Only check migratetype of pages being drained while CMA activeinclude/linux/mmzone.h include/linux/page-isolation.h mm/page_alloc.c +1 more+34 -100 replies
5/22oom: Use number of online nodes when deciding whether to suppress messagesmm/page_alloc.c+9 -160 replies
6/22mm: page allocator: Convert hot/cold parameter and immediate callers to boolarch/sparc/mm/init_64.c arch/sparc/mm/tsb.c arch/tile/mm/homecache.c +8 more+18 -180 replies
7/22mm: page allocator: Do not lookup the pageblock migratetype during allocationmm/page_alloc.c+1 -10 replies
8/22mm: page allocator: Remove the per-cpu page allocatorinclude/linux/gfp.h include/linux/mm.h include/linux/mmzone.h +9 more+29 -6470 replies
9/22mm: page allocator: Allocate/free order-0 pages from a per-zone magazineinclude/linux/mmzone.h mm/page_alloc.c mm/vmstat.c+114 -215 replies
10/22mm: page allocator: Allocate and free pages from magazine in batchesmm/page_alloc.c+127 -450 replies
11/22mm: page allocator: Shrink the magazine to the migratetypes in useinclude/linux/mmzone.h mm/page_alloc.c+26 -60 replies
12/22mm: page allocator: Remove knowledge of hot/cold from page allocatorarch/sparc/mm/init_64.c arch/sparc/mm/tsb.c arch/tile/mm/homecache.c +6 more+25 -360 replies
13/22mm: page allocator: Use list_splice to refill the magazinemm/page_alloc.c+7 -80 replies
14/22mm: page allocator: Do not disable IRQs just to update statsmm/page_alloc.c+10 -70 replies
15/22mm: page allocator: Check if interrupts are enabled only once per allocation attemptmm/page_alloc.c+44 -230 replies
16/22mm: page allocator: Remove coalescing improvement heuristic during page freemm/page_alloc.c+0 -220 replies
17/22mm: page allocator: Move magazine access behind accessorsinclude/linux/mmzone.h mm/page_alloc.c mm/vmstat.c+41 -250 replies
18/22mm: page allocator: Split magazine lock in two to reduce contentioninclude/linux/mmzone.h mm/page_alloc.c mm/vmstat.c+95 -392 replies
19/22mm: page allocator: Watch for magazine and zone lock contentionmm/page_alloc.c+30 -80 replies
20/22mm: page allocator: Hold magazine lock for a batch of pagesmm/page_alloc.c+61 -140 replies
21/22mm: compaction: Release free page list under a batched magazine lockinclude/linux/gfp.h mm/compaction.c mm/page_alloc.c+22 -180 replies
22/22mm: page allocator: Drain magazines for direct compact failuresinclude/linux/gfp.h mm/memory-failure.c mm/memory_hotplug.c +2 more+60 -90 replies

Reviews trailers per patch

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

Read the v1 thread

Cover letter [RFC PATCH 00/22] Per-cpu page allocator replacement prototype

Two LSF/MM's ago there was discussion on the per-cpu page allocator and whether it could be replaced due to it's complexity, frequent drains/refills and IPI overhead for global drains. The main obstacle to removal is that without those lists the zone->lock becomes very heavily contended and alternatives are inevitably going to share cache lines. I prototyped a potential replacement on the flight home and then left it on a TODO list for another year.

Last LSF/MM this was talked about in the hallway again although the meat of the discussion was different and took into account Andi Kleen's talk about lock batching. On this flight home, I rebased the old prototype, added some additional bits and pieces and tidied it up a bit since. This TODO item is about 3 years old so apparently sometimes the only way to get someone to do something is to lock them in a metal box for a few hours.

This is a prototype replacement starts with some minor optimisations that have nothing to do with anything really other than they were floating around from another flights worth of work. It then replaces the per-cpu page allocator with an IRQ-unsafe (no interrupts, no calls with local_irq_save) magazine that is protected by a spinlock. This effectively has the allocator use two locks. magazine_lock for non-IRQ users (e.g. page faults) and the zone->lock for magazine drains/refills and users who have IRQs disabled (interrupts, slab). It then splits the magazine into two where the preferred magazine depends on the CPU id of the executing thread. Non-preferred magazines may also be used and are searched round-robin as they are only protected by spinlocks. The last part of the series does some mucking around with lock contention and batching multiple frees due to exit or compaction under the lock.

It has not been heavily tested in low memory, heavy interrupt situations or extensively with all the debugging options enabled so it's likely there are bugs hiding in there. However I'm interested in hearing if the per-cpu page allocator is something we really want to replace or if there is a better potential alternative than this prototype. There are some interesting possibilities with this sort of design. For example, it would be possible to allocate magazines to allocator-intensive processes that are chained together for global drains where they are necessary. For these processes there would be much less contention (only on drains/refills) without having to use IPIs to drain their pages.

In the follow tests, no debugging was enabled but profiling was running so the tests are heavily disrupted. Take the results with a grain of salt. Machine was a single socket i7 with 16G RAM.

kernbench

                               3.9.0                 3.9.0
                             vanilla    magazine
User    min         883.59 (  0.00%)      700.16 ( 20.76%)
User    mean        891.11 (  0.00%)      741.02 ( 16.84%)
User    stddev       12.14 (  0.00%)       50.04 (-312.18%)
User    max         915.30 (  0.00%)      817.50 ( 10.69%)
User    range        31.71 (  0.00%)      117.34 (-270.04%)
System  min          58.85 (  0.00%)       43.65 ( 25.83%)
System  mean         59.65 (  0.00%)       47.65 ( 20.12%)
System  stddev        1.35 (  0.00%)        4.79 (-254.39%)
System  max          62.35 (  0.00%)       55.35 ( 11.23%)
System  range         3.50 (  0.00%)       11.70 (-234.29%)
Elapsed min         127.75 (  0.00%)       99.37 ( 22.22%)
Elapsed mean        129.19 (  0.00%)      105.73 ( 18.16%)
Elapsed stddev        2.07 (  0.00%)        7.56 (-265.78%)
Elapsed max         133.25 (  0.00%)      117.53 ( 11.80%)
Elapsed range         5.50 (  0.00%)       18.16 (-230.18%)
CPU     min         731.00 (  0.00%)      742.00 ( -1.50%)
CPU     mean        735.20 (  0.00%)      745.60 ( -1.41%)
CPU     stddev        2.99 (  0.00%)        3.38 (-12.99%)
CPU     max         739.00 (  0.00%)      751.00 ( -1.62%)
CPU     range         8.00 (  0.00%)        9.00 (-12.50%)

Kernel build benchmark seemed fairly successful, if anything they seem too good and I suspect this might have been a particularly "lucky" run. A non-profiling run might reveal more.

pagealloc

                                               3.9.0                      3.9.0
                                             vanilla         magazine
order-0 alloc-1                     671.11 (  0.00%)           734.11 ( -9.39%)
order-0 alloc-2                     520.33 (  0.00%)           517.56 (  0.53%)
order-0 alloc-4                     426.56 (  0.00%)           461.78 ( -8.26%)
order-0 alloc-8                     666.33 (  0.00%)           381.67 ( 42.72%)
order-0 alloc-16                    341.78 (  0.00%)           354.44 ( -3.71%)
order-0 alloc-32                    336.89 (  0.00%)           345.33 ( -2.51%)
order-0 alloc-64                    331.33 (  0.00%)           324.56 (  2.05%)
order-0 alloc-128                   324.56 (  0.00%)           325.89 ( -0.41%)
order-0 alloc-256                   350.44 (  0.00%)           326.22 (  6.91%)
order-0 alloc-512                   369.33 (  0.00%)           345.67 (  6.41%)
order-0 alloc-1024                  381.44 (  0.00%)           352.67 (  7.54%)
order-0 alloc-2048                  387.50 (  0.00%)           348.00 ( 10.19%)
order-0 alloc-4096                  403.00 (  0.00%)           384.50 (  4.59%)
order-0 alloc-8192                  413.00 (  0.00%)           383.00 (  7.26%)
order-0 alloc-16384                 411.00 (  0.00%)           396.80 (  3.45%)
order-0 free-1                      357.22 (  0.00%)           458.89 (-28.46%)
order-0 free-2                      285.11 (  0.00%)           349.89 (-22.72%)
order-0 free-4                      231.33 (  0.00%)           296.00 (-27.95%)
order-0 free-8                      371.56 (  0.00%)           229.33 ( 38.28%)
order-0 free-16                     189.78 (  0.00%)           212.89 (-12.18%)
order-0 free-32                     185.67 (  0.00%)           206.11 (-11.01%)
order-0 free-64                     178.44 (  0.00%)           197.78 (-10.83%)
order-0 free-128                    178.11 (  0.00%)           197.00 (-10.61%)
order-0 free-256                    227.89 (  0.00%)           196.56 ( 13.75%)
order-0 free-512                    280.11 (  0.00%)           194.67 ( 30.50%)
order-0 free-1024                   301.67 (  0.00%)           227.50 ( 24.59%)
order-0 free-2048                   325.50 (  0.00%)           238.00 ( 26.88%)
order-0 free-4096                   328.00 (  0.00%)           278.25 ( 15.17%)
order-0 free-8192                   337.50 (  0.00%)           277.00 ( 17.93%)
order-0 free-16384                  338.00 (  0.00%)           285.20 ( 15.62%)
order-0 total-1                    1031.89 (  0.00%)          1197.22 (-16.02%)
order-0 total-2                     805.44 (  0.00%)           867.44 ( -7.70%)
order-0 total-4                     657.89 (  0.00%)           768.67 (-16.84%)
order-0 total-8                    1039.56 (  0.00%)           611.00 ( 41.22%)
order-0 total-16                    531.56 (  0.00%)           569.33 ( -7.11%)
order-0 total-32                    523.44 (  0.00%)           551.44 ( -5.35%)
order-0 total-64                    509.78 (  0.00%)           522.89 ( -2.57%)
order-0 total-128                   502.67 (  0.00%)           522.89 ( -4.02%)
order-0 total-256                   579.56 (  0.00%)           522.78 (  9.80%)
order-0 total-512                   649.44 (  0.00%)           540.33 ( 16.80%)
order-0 total-1024                  686.44 (  0.00%)           580.17 ( 15.48%)
order-0 total-2048                  713.00 (  0.00%)           586.00 ( 17.81%)
order-0 total-4096                  731.00 (  0.00%)           663.75 (  9.20%)
order-0 total-8192                  750.50 (  0.00%)           660.00 ( 12.06%)
order-0 total-16384                 749.00 (  0.00%)           683.00 (  8.81%)

This is a systemtap-drive page allocator microbenchmark that allocates order-0 pages in increasingly large "batches" and times the length of time it takes to allocate and free. The results are a bit all over the map. Frees are slower because they always wait for the preferred magazine to be free and freeing single pages in a loop is a worst-case scenario. For larger patches it tends to perform reasonably well though.

pft

                             3.9.0                 3.9.0
                           vanilla               magazine
Faults/cpu 1  953441.5530 (  0.00%)  954011.8576 (  0.06%)
Faults/cpu 2  923793.1533 (  0.00%)  889436.7293 ( -3.72%)
Faults/cpu 3  876829.2292 (  0.00%)  868230.6471 ( -0.98%)
Faults/cpu 4  819914.9333 (  0.00%)  735264.4793 (-10.32%)
Faults/cpu 5  689049.0107 (  0.00%)  663481.5446 ( -3.71%)
Faults/cpu 6  579924.4065 (  0.00%)  571889.3687 ( -1.39%)
Faults/cpu 7  552024.1040 (  0.00%)  494345.8698 (-10.45%)
Faults/cpu 8  461452.7560 (  0.00%)  457877.1810 ( -0.77%)
Faults/sec 1  938245.7112 (  0.00%)  939198.4047 (  0.10%)
Faults/sec 2 1814498.4087 (  0.00%) 1748800.3800 ( -3.62%)
Faults/sec 3 2544466.6368 (  0.00%) 2359068.2163 ( -7.29%)
Faults/sec 4 3032778.8584 (  0.00%) 2831753.6553 ( -6.63%)
Faults/sec 5 3025180.2736 (  0.00%) 2952758.4589 ( -2.39%)
Faults/sec 6 3131131.0106 (  0.00%) 3058954.4941 ( -2.31%)
Faults/sec 7 3286271.0631 (  0.00%) 3183931.7940 ( -3.11%)
Faults/sec 8 3135331.0027 (  0.00%) 3106746.5908 ( -0.91%)

This is a page faulting microbenchmark that is forced to use base pages only. Here the new design suffers a bit because the allocation path is likely to contend on the magazine lock.

So preliminary testing indicates the results are mixed bag. As long as locks are not contended, it performs fine but parallel fault testing hits into spinlock contention on the magazine locks. A greater problem is that because CPUs share magazines it means that the struct pages are frequently dirtied cache lines. If CPU A frees a page to a magazine and CPU B immediately allocates it then the cache line for the page and the magazine bounces and this costs. It's on the TODO list to research if the available literature has anything useful to say that does not depend on per-cpu lists and the associated problems with them.

Comments?

 arch/sparc/mm/init_64.c        |    4 +-
 arch/sparc/mm/tsb.c            |    2 +-
 arch/tile/mm/homecache.c       |    2 +-
 fs/fuse/dev.c                  |    2 +-
 include/linux/gfp.h            |   12 +-
 include/linux/mm.h             |    3 -
 include/linux/mmzone.h         |   46 +-
 include/linux/page-isolation.h |    7 +-
 include/linux/pagemap.h        |    2 +-
 include/linux/swap.h           |    2 +-
 include/trace/events/kmem.h    |   22 +-
 init/main.c                    |    1 -
 kernel/power/snapshot.c        |    2 -
 kernel/sysctl.c                |   10 -
 mm/compaction.c                |   18 +-
 mm/memory-failure.c            |    2 +-
 mm/memory_hotplug.c            |   13 +-
 mm/page_alloc.c                | 1109 +++++++++++++++++-----------------------
 mm/page_isolation.c            |   30 +-
 mm/rmap.c                      |    2 +-
 mm/swap.c                      |    6 +-
 mm/swap_state.c                |    2 +-
 mm/vmscan.c                    |    6 +-
 mm/vmstat.c                    |   54 +-
 24 files changed, 571 insertions(+), 788 deletions(-)
Signature · 7 lines
1.8.1.4

--
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>