Skip to content

Cleanup and optimise the page allocator V3

Mel Gorman linux-mm lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest35 patches 58 repliesIn review

Changes since V2 from the cover letter · 16 lines

o Remove brances by treating watermark flags as array indices
o Remove branch by assuming __GFP_HIGH == ALLOC_HIGH
o Do not check for compound on every page free
o Remove branch by always ensuring the migratetype is known on free
o Simplify buffered_rmqueue further
o Reintroduce improved version of batched bulk free of pcp pages
o Use allocation flags as an index to zone watermarks
o Work out __GFP_COLD only once
o Reduce the number of times zone stats are updated
o Do not dump reserve pages back into the allocator. Instead treat them as MOVABLE so that MIGRATE_RESERVE gets used on the max-order-overlapped boundaries without causing trouble
o Allow pages up to PAGE_ALLOC_COSTLY_ORDER to use the per-cpu allocator. order-1 allocations are frequently enough in particular to justify this
o Rearrange inlining such that the hot-path is inlined but not in a way that increases the text size of the page allocator
o Make the check for needing additional zonelist filtering due to NUMA or cpusets as light as possible
o Do not destroy compound pages going to the PCP lists
o Delay the merging of buddies until a high-order allocation needs them or anti-fragmentation is being forced to fallback
o Count high-order pages as 1

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/35Replace __alloc_pages_internal() with __alloc_pages_nodemask()include/linux/gfp.h mm/page_alloc.c+4 -121 reply
2/35Do not sanity check order in the fast pathinclude/linux/gfp.h mm/page_alloc.c+2 -61 reply
3/35Do not check NUMA node ID when the caller knows the node is validarch/ia64/hp/common/sba_iommu.c arch/ia64/kernel/mca.c arch/ia64/kernel/uncached.c +14 more+32 -230 replies
4/35Check only once if the zonelist is suitable for the allocationmm/page_alloc.c+3 -30 replies
5/35Break up the allocator entry point into fast and slow pathsmm/page_alloc.c+218 -1300 replies
6/35Move check for disabled anti-fragmentation out of fastpathinclude/linux/mmzone.h mm/page_alloc.c+4 -31 reply
7/35Check in advance if the zonelist needs additional filteringinclude/linux/cpuset.h mm/page_alloc.c+28 -110 replies
8/35Calculate the preferred zone for allocation only oncemm/page_alloc.c+32 -210 replies
9/35Calculate the migratetype for allocation only oncemm/page_alloc.c+26 -170 replies
10/35Calculate the alloc_flags for allocation only oncemm/page_alloc.c+50 -380 replies
11/35Calculate the cold parameter for allocation only oncemm/page_alloc.c+18 -170 replies
12/35Remove a branch by assuming __GFP_HIGH == ALLOC_HIGHmm/page_alloc.c+2 -20 replies
13/35Inline __rmqueue_smallest()mm/page_alloc.c+18 -50 replies
14/35Inline buffered_rmqueue()mm/page_alloc.c+2 -10 replies
15/35Inline __rmqueue_fallback()mm/page_alloc.c+2 -22 replies
16/35Save text by reducing call sites of __rmqueue()mm/page_alloc.c+7 -40 replies
17/35Do not call get_pageblock_migratetype() more than necessarymm/page_alloc.c+10 -61 reply
18/35Do not disable interrupts in free_page_mlock()mm/internal.h mm/page_alloc.c+10 -92 replies
19/35Do not setup zonelist cache when there is only one nodemm/page_alloc.c+8 -21 reply
20/35Use a pre-calculated value for num_online_nodes()include/linux/nodemask.h mm/page_alloc.c+18 -420 replies
21/35Do not check for compound pages during the page allocator sanity checksmm/page_alloc.c+3 -31 reply
22/35Use allocation flags as an index to the zone watermarkinclude/linux/mmzone.h mm/page_alloc.c+15 -111 reply
23/35Update NR_FREE_PAGES only as necessarymm/page_alloc.c+6 -64 replies
24/35Convert gfp_zone() to use a table of precalculated valuesinclude/linux/gfp.h init/main.c mm/page_alloc.c+47 -182 replies
25/35Re-sort GFP flags and fix whitespace alignment for easier reading.include/linux/gfp.h+5 -40 replies
26/35Use the per-cpu allocator for orders up to PAGE_ALLOC_COSTLY_ORDERmm/page_alloc.c+80 -382 replies
27/35Split per-cpu list into one-list-per-migrate-typeinclude/linux/mmzone.h mm/page_alloc.c+61 -260 replies
28/35Batch free pages from migratetype per-cpu listsmm/page_alloc.c+23 -130 replies
29/35Do not store the PCP high and batch watermarks in the per-cpu structureinclude/linux/mmzone.h mm/page_alloc.c mm/vmstat.c+31 -241 reply
30/35Skip the PCP list search by counting the order and type of pages on listinclude/linux/mmzone.h mm/page_alloc.c+30 -222 replies
31/35Optimistically check the first page on the PCP free list is suitablemm/page_alloc.c+6 -02 replies
32/35Inline next_zones_zonelist() of the zonelist scan in the fastpathinclude/linux/mmzone.h mm/mmzone.c mm/page_alloc.c+45 -320 replies
33/35Do not merge buddies until they are needed by a high-order allocation or anti-fragmentationinclude/linux/mmzone.h mm/page_alloc.c+86 -120 replies
34/35Allow compound pages to be stored on the PCP listsinclude/linux/page-flags.h mm/page_alloc.c+36 -181 reply
35/35Allow up to 4MB PCP lists due to compound pagesmm/page_alloc.c+9 -140 replies

Reviews trailers per patch

12 of 35 patches have a Reviewed-by or Acked-by.

PatchChristoph LameterPekka Enberg
1/35R-b
2/35R-b
3/35R-b
4/35R-b
5/35
6/35R-b
7/35
8/35
9/35
10/35A-b
11/35
12/35
13/35
14/35
15/35
16/35
17/35R-b
18/35
19/35R-b
20/35
21/35R-b
22/35R-b
23/35R-b
24/35
25/35
26/35
27/35
28/35
29/35
30/35
31/35
32/35
33/35
34/35R-b
35/35

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [PATCH 00/35] Cleanup and optimise the page allocator V3

Here is V3 of an attempt to cleanup and optimise the page allocator and should be ready for general testing. The page allocator is now faster (16% reduced time overall for kernbench on one machine) and it has a smaller cache footprint (16.5% less L1 cache misses and 19.5% less L2 cache misses for kernbench on one machine). The text footprint has unfortunately increased, largely due to the introduction of a form of lazy buddy merging mechanism that avoids cache misses by postponing buddy merging until a high-order allocation needs it.

I tested the patchset with kernbench, hackbench, sysbench-postgres and netperf UDP and TCP with a variety of sizes. Many machines and loads showed improved performance *however* it was not universal. On some machines, one load would be faster and another slower (perversely, sometimes netperf-UDP would be faster with netperf-TCP slower). On an different machines, the workloads that gained or lost would differ. I haven't fully pinned down why this is yet but I have observed on at least one machine lock contention is higher and more time is spent in functions like rb_erase(), both which might imply some sort of scheduling artifact. I've also noted that while the allocator incurs fewer cache misses, sometimes cache misses overall are increased for the workload but the increased lock contention might account for this.

In some cases, more time is spent in copy_user_generic_string()[1] which might imply that strings are getting the same colour with the greater effort spent giving back hot pages but theories as to why this is not a universal effect are welcome. I've also noted that machines with many CPUs with different caches suffer because struct page is not cache-aligned but aligning it hurts other machines so I left it alone. Finally, the performance characteristics are vary depending on if you use SLAB, SLUB or SLQB.

So, while the page allocator is faster in most cases, making all workloads universally go faster needs to now look at other areas like the sl*b allocator and the scheduler.

Here is the patchset as it stands and I think it's ready for wider testing and to be considered for merging depending on the outcome of testing and reviews.

[1] copy_user_generic_unrolled on one machine was slowed down by an extreme amount. I did not check if there was a pattern of slowdowns versus which version of copy_user_generic() was used

Changes since V2
o Remove brances by treating watermark flags as array indices
o Remove branch by assuming __GFP_HIGH == ALLOC_HIGH
o Do not check for compound on every page free
o Remove branch by always ensuring the migratetype is known on free
o Simplify buffered_rmqueue further
o Reintroduce improved version of batched bulk free of pcp pages
o Use allocation flags as an index to zone watermarks
o Work out __GFP_COLD only once
o Reduce the number of times zone stats are updated
o Do not dump reserve pages back into the allocator. Instead treat them as MOVABLE so that MIGRATE_RESERVE gets used on the max-order-overlapped boundaries without causing trouble
o Allow pages up to PAGE_ALLOC_COSTLY_ORDER to use the per-cpu allocator. order-1 allocations are frequently enough in particular to justify this
o Rearrange inlining such that the hot-path is inlined but not in a way that increases the text size of the page allocator
o Make the check for needing additional zonelist filtering due to NUMA or cpusets as light as possible
o Do not destroy compound pages going to the PCP lists
o Delay the merging of buddies until a high-order allocation needs them or anti-fragmentation is being forced to fallback
o Count high-order pages as 1

Changes since V1
o Remove the ifdef CONFIG_CPUSETS from inside get_page_from_freelist()
o Use non-lock bit operations for clearing the mlock flag
o Factor out alloc_flags calculation so it is only done once (Peter)
o Make gfp.h a bit prettier and clear-cut (Peter)
o Instead of deleting a debugging check, replace page_count() in the free path with a version that does not check for compound pages (Nick)
o Drop the alteration for hot/cold page freeing until we know if it helps or not

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