mm: page_alloc: pcp buddy allocator
Subsystems (5)
Johannes Weiner
reviewercover mm: page_alloc: pcp buddy allocator
Hi,
this is an RFC for making the page allocator scale better with higher thread counts and larger memory quantities.
In Meta production, we're seeing increasing zone->lock contention that was traced back to a few different paths. A prominent one is the userspace allocator, jemalloc. Allocations happen from page faults on all CPUs running the workload. Frees are cached for reuse, but the caches are periodically purged back to the kernel from a handful of purger threads. This breaks affinity between allocations and frees:
Both sides use their own PCPs - one side depletes them, the other one overfills them. Both sides routinely hit the zone->locked slowpath.
My understanding is that tcmalloc has a similar architecture.
Another contributor to contention is process exits, where large numbers of pages are freed at once. The current PCP can only reduce lock time when pages are reused. Reuse is unlikely because it's an avalanche of free pages on a CPU busy walking page tables. Every time the PCP overflows, the drain acquires the zone->lock and frees pages one by one, trying to merge buddies together.
The idea proposed here is this: instead of single pages, make the PCP grab entire pageblocks, split them outside the zone->lock. That CPU then takes ownership of the block, and all frees route back to that PCP instead of the freeing CPU's local one.
This has several benefits:
1. It's right away coarser/fewer allocations transactions under the zone->lock.
1a. Even if no full free blocks are available (memory pressure or
small zone), with splitting available at the PCP level means the PCP can still grab chunks larger than the requested order from the zone->lock freelists, and dole them out on its own time.
2. The pages free back to where the allocations happen, increasing the odds of reuse and reducing the chances of zone->lock slowpaths.
3. The page buddies come back into one place, allowing upfront merging under the local pcp->lock. This makes coarser/fewer freeing transactions under the zone->lock.
The big concern is fragmentation. Movable allocations tend to be a mix of short-lived anon and long-lived file cache pages. By the time the PCP needs to drain due to thresholds or pressure, the blocks might not be fully re-assembled yet. To prevent gobbling up and fragmenting ever more blocks, partial blocks are remembered on drain and their pages queued last on the zone freelist. When a PCP refills, it first tries to recover any such fragment blocks.
On small or pressured machines, the PCP degrades to its previous behavior. If a whole block doesn't fit the pcp->high limit, or a whole block isn't available, the refill grabs smaller chunks that aren't marked for ownership. The free side will use the local PCP as before.
I still need to run broader benchmarks, but I've been consistently seeing a 3-4% reduction in %sys time for simple kernel builds on my 32-way, 32G RAM test machine.
A synthetic test on the same machine that allocates on many CPUs and frees on just a few sees a consistent 1% increase in throughput.
I would expect those numbers to increase with higher concurrency and larger memory volumes, but verifying that is TBD.
Sending an RFC to get an early gauge on direction.
Based on 0257f64bdac7fdca30fa3cae0df8b9ecbec7733a.
include/linux/mmzone.h | 38 ++- include/linux/page-flags.h | 9 + mm/debug.c | 1 + mm/internal.h | 17 + mm/mm_init.c | 25 +- mm/page_alloc.c | 784 +++++++++++++++++++++++++++++++------------ mm/sparse.c | 3 +- 7 files changed, 622 insertions(+), 255 deletions(-)
Johannes Weiner
reviewerRFC 1/2 mm: page_alloc: replace pageblock_flags bitmap with struct pageblock_data
From: Johannes Weiner <[email protected]>
Replace the packed pageblock_flags bitmap with a per-pageblock struct containing its own flags word. This changes the storage from NR_PAGEBLOCK_BITS bits per pageblock packed into shared unsigned longs, to a dedicated unsigned long per pageblock.
The free path looks up migratetype (from pageblock flags) immediately followed by looking up pageblock ownership. Colocating them in a struct means this hot path touches one cache line instead of two.
The per-pageblock struct also eliminates all the bit-packing indexing (pfn_to_bitidx, word selection, intra-word shifts), simplifying the accessor code.
Memory overhead: 8 bytes per pageblock (one unsigned long). With 2MB pageblocks on x86_64, that's 4KB per GB -- up from ~0.5-1 bytes per pageblock with the packed bitmap, but still negligible in absolute terms.
No functional change.
--- include/linux/mmzone.h | 15 ++++---- mm/internal.h | 17 +++++++++ mm/mm_init.c | 25 ++++++------- mm/page_alloc.c | 81 ++++++------------------------------------ mm/sparse.c | 3 +- 5 files changed, 48 insertions(+), 93 deletions(-)
include/linux/mmzone.h +8 -7
@@ -916,7 +916,7 @@ struct zone {* Flags for a pageblock_nr_pages block. See pageblock-flags.h. * In SPARSEMEM, this map is stored in struct mem_section */ -unsigned long *pageblock_flags; +struct pageblock_data *pageblock_data;#endif /* CONFIG_SPARSEMEM */ /* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
@@ -1866,9 +1866,6 @@ static inline bool movable_only_nodes(nodemask_t *nodes)#define PAGES_PER_SECTION (1UL << PFN_SECTION_SHIFT)#define PAGE_SECTION_MASK (~(PAGES_PER_SECTION-1)) -#define SECTION_BLOCKFLAGS_BITS \ - ((1UL << (PFN_SECTION_SHIFT - pageblock_order)) * NR_PAGEBLOCK_BITS) -#if (MAX_PAGE_ORDER +PAGE_SHIFT ) >SECTION_SIZE_BITS #error Allocator MAX_PAGE_ORDER exceeds SECTION_SIZE#endif
@@ -1901,13 +1898,17 @@ static inline unsigned long section_nr_to_pfn(unsigned long sec)#define SUBSECTION_ALIGN_UP (pfn) ALIGN((pfn), PAGES_PER_SUBSECTION)#define SUBSECTION_ALIGN_DOWN (pfn) ((pfn) & PAGE_SUBSECTION_MASK) +struct pageblock_data { +unsigned long flags; +}; +struct mem_section_usage {struct rcu_head rcu;#ifdef CONFIG_SPARSEMEM_VMEMMAP DECLARE_BITMAP(subsection_map, SUBSECTIONS_PER_SECTION);#endif /* See declaration of similar field in struct zone */ -unsigned long pageblock_flags[0 ]; +struct pageblock_data pageblock_data[]; };void subsection_map_init (unsigned long pfn,unsigned long nr_pages);
@@ -1960,9 +1961,9 @@ extern struct mem_section **mem_section;extern struct mem_section mem_section[NR_SECTION_ROOTS ][SECTIONS_PER_ROOT ];#endif -static inline unsigned long *section_to_usemap (struct mem_section *ms) +static inline struct pageblock_data *section_to_usemap (struct mem_section *ms) { -return ms->usage->pageblock_flags; +return ms->usage->pageblock_data; }static inline struct mem_section *__nr_to_section (unsigned long nr)
mm/internal.h +17 -0
@@ -787,6 +787,23 @@ static inline struct page *find_buddy_page_pfn(struct page *page,return NULL ; } +static inline struct pageblock_data *pfn_to_pageblock (const struct page *page, +unsigned long pfn) +{ +#ifdef CONFIG_SPARSEMEM +struct mem_section *ms =__pfn_to_section (pfn); +unsigned long idx = (pfn & (PAGES_PER_SECTION -1 )) >> pageblock_order; + +return §ion_to_usemap (ms)[idx]; +#else +struct zone *zone =page_zone (page); +unsigned long idx; + + idx = (pfn -pageblock_start_pfn (zone->zone_start_pfn)) >> pageblock_order; +return &zone->pageblock_data[idx]; +#endif +} +extern struct page *__pageblock_pfn_to_page (unsigned long start_pfn,unsigned long end_pfn,struct zone *zone);
mm/mm_init.c +10 -15
@@ -1467,36 +1467,31 @@ void __meminit init_currently_empty_zone(struct zone *zone,#ifndef CONFIG_SPARSEMEM /* -* Calculate the size of the zone->pageblock_flags rounded to an unsigned long -* Start by making sure zonesize is a multiple of pageblock_order by rounding -* up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally -* round what is now in bits to nearest long in bits, then return it in -* bytes. +* Calculate the size of the zone->pageblock_data array. +* Round up the zone size to a pageblock boundary to get the +* number of pageblocks, then multiply by the struct size. */ static unsigned long __init usemap_size (unsigned long zone_start_pfn,unsigned long zonesize) { -unsigned long usemapsize; +unsigned long nr_pageblocks; zonesize += zone_start_pfn & (pageblock_nr_pages-1 ); - usemapsize =round_up (zonesize, pageblock_nr_pages); - usemapsize = usemapsize >> pageblock_order; - usemapsize *=NR_PAGEBLOCK_BITS ; - usemapsize =round_up (usemapsize,BITS_PER_LONG ); + nr_pageblocks =round_up (zonesize, pageblock_nr_pages) >> pageblock_order; -return usemapsize /BITS_PER_BYTE ; +return nr_pageblocks *sizeof (struct pageblock_data ); }static void __ref setup_usemap (struct zone *zone) {unsigned long usemapsize =usemap_size (zone->zone_start_pfn, zone->spanned_pages); - zone->pageblock_flags =NULL ; + zone->pageblock_data =NULL ;if (usemapsize) { - zone->pageblock_flags = + zone->pageblock_data =memblock_alloc_node (usemapsize,SMP_CACHE_BYTES ,zone_to_nid (zone)); -if (!zone->pageblock_flags) -panic ("Failed to allocate %ld bytes for zone %s pageblock flags on node %d\n" , +if (!zone->pageblock_data) +panic ("Failed to allocate %ld bytes for zone %s pageblock data on node %d\n" , usemapsize, zone->name,zone_to_nid (zone)); } }
mm/page_alloc.c +11 -70
144 lines not on this page · raw message
mm/sparse.c +2 -1
@@ -298,7 +298,8 @@ static void __meminit sparse_init_one_section(struct mem_section *ms,static unsigned long usemap_size (void ) { -return BITS_TO_LONGS (SECTION_BLOCKFLAGS_BITS ) *sizeof (unsigned long ); +return (1UL << (PFN_SECTION_SHIFT - pageblock_order)) * +sizeof (struct pageblock_data ); }size_t mem_section_usage_size (void )
Signature · 1 line
2.53.0
Re: [RFC 1/2] mm: page_alloc: replace pageblock_flags bitmap with struct pageblock_data
Quoted 10 lines · Johannes Weiner
From: Johannes Weiner <[email protected]>
Replace the packed
pageblock_flagsbitmap with a per-pageblock struct containing its own flags word. This changes the storage fromNR_PAGEBLOCK_BITSbits per pageblock packed into shared unsigned longs,
to a dedicated unsigned long per pageblock.Signed-off-by Johannes Weiner <[email protected]>
Signature · 1 line
All Rights Reversed.
Zi Yan
reviewerRe: [RFC 1/2] mm: page_alloc: replace pageblock_flags bitmap with struct pageblock_data
In reply to Johannes WeinerQuoted 54 lines · Johannes Weiner
From: Johannes Weiner <[email protected]>
Replace the packed
pageblock_flagsbitmap with a per-pageblock struct containing its own flags word. This changes the storage fromNR_PAGEBLOCK_BITSbits per pageblock packed into shared unsigned longs, to a dedicated unsigned long per pageblock.The free path looks up migratetype (from pageblock flags) immediately followed by looking up pageblock ownership. Colocating them in a struct means this hot path touches one cache line instead of two.
The per-pageblock struct also eliminates all the bit-packing indexing (
pfn_to_bitidx, word selection, intra-word shifts), simplifying the accessor code.Memory overhead: 8 bytes per pageblock (one unsigned long). With 2MB pageblocks on
x86_64, that's 4KB per GB -- up from ~0.5-1 bytes per pageblock with the packed bitmap, but still negligible in absolute terms.No functional change.
Signed-off-by Johannes Weiner <[email protected]>--- include/linux/mmzone.h | 15 ++++---- mm/internal.h | 17 +++++++++ mm/mm_init.c | 25 ++++++------- mm/page_alloc.c | 81 ++++++------------------------------------ mm/sparse.c | 3 +- 5 files changed, 48 insertions(+), 93 deletions(-)include/linux/mmzone.h +1
-4@@ -916,7 +916,7 @@ struct zone {* Flags for a pageblock_nr_pages block. See pageblock-flags.h. * In SPARSEMEM, this map is stored in struct mem_section */ -unsigned long *pageblock_flags; +struct pageblock_data *pageblock_data;#endif /* CONFIG_SPARSEMEM */ /* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */ @@ -1866,9 +1866,6 @@ static inline bool movable_only_nodes(nodemask_t *nodes)#define PAGES_PER_SECTION (1UL << PFN_SECTION_SHIFT)#define PAGE_SECTION_MASK (~(PAGES_PER_SECTION-1)) -#define SECTION_BLOCKFLAGS_BITS \ - ((1UL << (PFN_SECTION_SHIFT - pageblock_order)) * NR_PAGEBLOCK_BITS) -#if (MAX_PAGE_ORDER +PAGE_SHIFT ) >SECTION_SIZE_BITS #error Allocator MAX_PAGE_ORDER exceeds SECTION_SIZE#endif
include/linux/mmzone.h static inline unsigned long section_nr_to_pfn(unsigned long sec) · line 1902
Quoted 5 lines
include/linux/mmzone.h +2
-0@@ -1901,13 +1898,17 @@ static inline unsigned long section_nr_to_pfn(unsigned long sec)#define SUBSECTION_ALIGN_UP (pfn) ALIGN((pfn), PAGES_PER_SUBSECTION)#define SUBSECTION_ALIGN_DOWN (pfn) ((pfn) & PAGE_SUBSECTION_MASK) +struct pageblock_data { +unsigned long flags;
Would it be better to make this uint32_t if !CONFIG_MEMORY_ISOLATION and uint64_t otherwise? MIGRATE_ISOLATE is the only reason to have 8 byte pageblock flag.
<snip>
include/linux/mmzone.h static inline unsigned long section_nr_to_pfn(unsigned long sec) · line 1908
Quoted 5 lines
include/linux/mmzone.h +0
-5-#ifdef CONFIG_MEMORY_ISOLATION -BUILD_BUG_ON (NR_PAGEBLOCK_BITS !=8 ); -#else -BUILD_BUG_ON (NR_PAGEBLOCK_BITS !=4 ); -#endif
We probably still need
BUILD_BUG_ON(NR_PAGEBLOCK_BITS > sizeof(struct pageblock_data));
just in case in the future we add too many pageblock bits.
Otherwise, this patch can be sent and merged separately.
--
Best Regards,
Yan, Zi
Johannes Weiner
reviewerRFC 2/2 mm: page_alloc: per-cpu pageblock buddy allocator
In reply to Johannes WeinerOn large machines, zone->lock is a scaling bottleneck for page allocation. Two common patterns drive contention:
1. Affinity violations: pages are allocated on one CPU but freed on another (jemalloc, exit, reclaim). The freeing CPU's PCP drains to zone buddy, and the allocating CPU refills from zone buddy -- both under zone->lock, defeating PCP batching entirely.
2. Concurrent exits: processes tearing down large address spaces simultaneously overwhelm per-CPU PCP capacity, serializing on zone->lock for overflow.
Solution
Extend the PCP to operate on whole pageblocks with ownership tracking.
Each CPU claims pageblocks from the zone buddy and splits them locally. Pages are tagged with their owning CPU, so frees route back to the owner's PCP regardless of which CPU frees. This eliminates affinity violations: the owner CPU's PCP absorbs both allocations and frees for its blocks without touching zone->lock.
It also shortens zone->lock hold time during drain and refill cycles. Whole blocks are acquired under zone->lock and then split outside of it. Affinity routing to the owning PCP on free enables buddy merging outside the zone->lock as well; a bottom-up merge pass runs under pcp->lock on drain, freeing larger chunks under zone->lock.
PCP refill uses a four-phase approach:
Phase 0: recover owned fragments previously drained to zone buddy. Phase 1: claim whole pageblocks from zone buddy.
Phase 2: grab sub-pageblock chunks without migratetype stealing. Phase 3: traditional __rmqueue() with migratetype fallback.
Phase 0/1 pages are owned and marked PagePCPBuddy, making them eligible for PCP-level merging. Phase 2/3 pages are cached on PCP for batching only -- no ownership, no merging. However, Phase 2 still benefits from chunky zone transactions: it pulls higher-order entries from zone free lists under zone->lock and splits them on the PCP outside of it, rather than acquiring zone->lock per page.
When PCP batch sizes are small (small machines with few CPUs) or the zone is fragmented and no whole pageblocks are available, refill falls through to Phase 2/3 naturally. The allocator degrades gracefully to the original page-at-a-time behavior.
When owned blocks accumulate long-lived allocations (e.g. a mix of anonymous and file cache pages), partial block drains send the free fragments to zone buddy and remember the block, so Phase 0 can recover them on the next refill. This allows the allocator to pack new allocations next to existing ones in already-committed blocks rather than consuming fresh pageblocks, keeping fragmentation contained.
Data structures:
- per_cpu_pages: +owned_blocks list head, +PCPF_CPU_DEAD flag to gate enqueuing on offline CPUs.
- pageblock_data: +cpu (owner), +block_pfn, +cpu_node (recovery list linkage). 32 bytes per pageblock, ~16KB per GB with 2MB pageblocks.
- PagePCPBuddy page type marks pages eligible for PCP-level merging.
--- include/linux/mmzone.h | 23 +- include/linux/page-flags.h | 9 + mm/debug.c | 1 + mm/page_alloc.c | 705 +++++++++++++++++++++++++++++-------- 4 files changed, 575 insertions(+), 163 deletions(-)
include/linux/mmzone.h +13 -10
@@ -714,17 +714,10 @@ enum zone_watermarks { };/* -* One per migratetype for each PAGE_ALLOC_COSTLY_ORDER. Two additional lists -* are added for THP. One PCP list is used by GPF_MOVABLE, and the other PCP list -* is used by GFP_UNMOVABLE and GFP_RECLAIMABLE. +* One per migratetype for page orders up to and including PAGE_BLOCK_MAX_ORDER. */ -#ifdef CONFIG_TRANSPARENT_HUGEPAGE -#define NR_PCP_THP 2 -#else -#define NR_PCP_THP 0 -#endif -#define NR_LOWORDER_PCP_LISTS (MIGRATE_PCPTYPES * (PAGE_ALLOC_COSTLY_ORDER + 1)) -#define NR_PCP_LISTS (NR_LOWORDER_PCP_LISTS + NR_PCP_THP) +#define NR_PCP_ORDERS (PAGE_BLOCK_MAX_ORDER + 1) +#define NR_PCP_LISTS (MIGRATE_PCPTYPES * NR_PCP_ORDERS)/* * Flags used in pcp->flags field.
@@ -737,9 +730,13 @@ enum zone_watermarks {* draining PCP for consecutive high-order pages freeing without * allocation if data cache slice of CPU is large enough. To reduce * zone lock contention and keep cache-hot pages reusing. +* +* PCPF_CPU_DEAD: CPU is offline. Don't enqueue freed pages; fall +* back to zone buddy instead. */ #define PCPF_PREV_FREE_HIGH_ORDER BIT(0)#define PCPF_FREE_HIGH_BATCH BIT(1) +#define PCPF_CPU_DEAD BIT(2)struct per_cpu_pages {spinlock_t lock;/* Protects lists field */
@@ -755,6 +752,9 @@ struct per_cpu_pages {#endif short free_count;/* consecutive free count */ +/* Pageblocks owned by this CPU, for fragment recovery */ +struct list_head owned_blocks; +/* Lists of pages, one per migrate type stored on the pcp-lists */ struct list_head lists[NR_PCP_LISTS ]; }____cacheline_aligned_in_smp ;
@@ -1900,6 +1900,9 @@ static inline unsigned long section_nr_to_pfn(unsigned long sec)struct pageblock_data {unsigned long flags; +int cpu;/* PCP ownership: owning cpu + 1, or 0 for zone-owned */ +unsigned long block_pfn;/* first PFN of pageblock */ +struct list_head cpu_node;/* per-CPU owned-blocks list */ };struct mem_section_usage {
include/linux/page-flags.h +9 -0
@@ -934,6 +934,7 @@ enum pagetype { PGTY_zsmalloc =0xf6 , PGTY_unaccepted =0xf7 , PGTY_large_kmalloc =0xf8 , + PGTY_pcp_buddy =0xf9 , PGTY_mapcount_underflow = 0xff };
@@ -1002,6 +1003,14 @@ static __always_inline void __ClearPage##uname(struct page *page) \*/ PAGE_TYPE_OPS (Buddy, buddy, buddy) +/* +* PagePCPBuddy() indicates that the page is free and in a per-cpu +* buddy allocator (see mm/page_alloc.c). Unlike PageBuddy() pages, +* these are not on zone free lists and must not be isolated by +* compaction or other zone-level code. + */ +PAGE_TYPE_OPS (PCPBuddy, pcp_buddy, pcp_buddy) +/* * PageOffline() indicates that the page is logically offline although the * containing section is online. (e.g. inflated in a balloon driver or
mm/debug.c +1 -0
@@ -56,6 +56,7 @@ static const char *page_type_names[] = {DEF_PAGETYPE_NAME (table),DEF_PAGETYPE_NAME (buddy),DEF_PAGETYPE_NAME (unaccepted), + DEF_PAGETYPE_NAME(pcp_buddy), };static const char *page_type_name (unsigned int page_type)
mm/page_alloc.c +552 -153
1,016 lines not on this page · raw message
Signature · 1 line
2.53.0
Re: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Quoted 26 lines · Johannes Weiner
(quoted diff) +0
-0@@ -755,6 +752,9 @@ struct per_cpu_pages { #endifshort
free_count; /* consecutive free count */
+ /* Pageblocks owned by this CPU, for fragment recovery */
+ structlist_headowned_blocks;
+
/* Lists of pages, one per migrate type stored on the pcp-lists */ structlist_headlists[NR_PCP_LISTS];
}____cacheline_aligned_in_smp;+ /*
+ * Phase 0: Recover fragments from owned blocks.
+ *
+ * Theowned_blockslist tracks blocks that have fragments
+ * sitting in zone buddy (put there by drains). Pull matching
+ * fragments back to PCP with PagePCPBuddy so they participate
+ * in merging, instead of claiming fresh blocks and spreading
+ * fragmentation further.
+ *
+ * Only recover blocks matching the requested migratetype.
+ * After recovery, remove the block from the list -- the drain
+ * path re-adds it if new fragments arrive.
+ */
Quoted 8 lines
+
list_for_each_entry_safe(pbd, tmp, &pcp->owned_blocks, cpu_node){
+ unsigned longbase_pfn, pfn;
+ intblock_mt;
+
+base_pfn=pbd->block_pfn;
+block_mt=pbd_migratetype(pbd);
+ if (block_mt!= migratetype)
+ continue;
GIven that you just skip over blocks of the wrong migratetype, I wonder if it makes sense to have a different list head for each migratetype in the per_cpu_pages struct.
Not that I should be saying anything that would slow down the merging of these patches, since making the buddy allocator more of a slow path is pretty much a prerequisite for the 1GB allocation stuff I'm working on :)
Signature · 1 line
All Rights Reversed.
Johannes Weiner
reviewerRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Quoted 36 lines · Rik van Riel
Quoted 26 lines · Johannes Weiner
(quoted diff) +0
-0@@ -755,6 +752,9 @@ struct per_cpu_pages { #endifshort
free_count; /* consecutive free count */
+ /* Pageblocks owned by this CPU, for fragment recovery */
+ structlist_headowned_blocks;
+
/* Lists of pages, one per migrate type stored on the pcp-lists */ structlist_headlists[NR_PCP_LISTS];
}____cacheline_aligned_in_smp;+ /*
+ * Phase 0: Recover fragments from owned blocks.
+ *
+ * Theowned_blockslist tracks blocks that have fragments
+ * sitting in zone buddy (put there by drains). Pull matching
+ * fragments back to PCP with PagePCPBuddy so they participate
+ * in merging, instead of claiming fresh blocks and spreading
+ * fragmentation further.
+ *
+ * Only recover blocks matching the requested migratetype.
+ * After recovery, remove the block from the list -- the drain
+ * path re-adds it if new fragments arrive.
+ */Quoted 8 lines
+
list_for_each_entry_safe(pbd, tmp, &pcp->owned_blocks, cpu_node){
+ unsigned longbase_pfn, pfn;
+ intblock_mt;
+
+base_pfn=pbd->block_pfn;
+block_mt=pbd_migratetype(pbd);
+ if (block_mt!= migratetype)
+ continue;
Quoted 3 lines
GIven that you just skip over blocks of the wrong migratetype, I wonder if it makes sense to have a different list head for each migratetype in the
per_cpu_pagesstruct.
The list is fairly small in practice (pcp->high / average_free_pages_per_block). I haven't run into any issues with it so far (although like I said, my tests have been limited).
That said, I also don't think it would be an issue to do that split if necessary. Additional list heads are 16 bytes per cpu per zone.
Let me keep an eye on this during larger scale tests.
Re: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
In reply to Johannes WeinerQuoted 29 lines · Johannes Weiner
On large machines,
zone->lockis a scaling bottleneck for page allocation. Two common patterns drive contention:1. Affinity violations: pages are allocated on one CPU but freed on another (jemalloc, exit, reclaim). The freeing CPU's PCP drains to zone buddy, and the allocating CPU refills from zone buddy -- both under
zone->lock, defeating PCP batching entirely.2. Concurrent exits: processes tearing down large address spaces simultaneously overwhelm per-CPU PCP capacity, serializing on
zone->lockfor overflow.Solution
Extend the PCP to operate on whole pageblocks with ownership tracking.
Each CPU claims pageblocks from the zone buddy and splits them locally. Pages are tagged with their owning CPU, so frees route back to the owner's PCP regardless of which CPU frees. This eliminates affinity violations: the owner CPU's PCP absorbs both allocations and frees for its blocks without touching
zone->lock.It also shortens
zone->lockhold time during drain and refill cycles. Whole blocks are acquired underzone->lockand then split outside of it. Affinity routing to the owning PCP on free enables buddy merging outside thezone->lockas well; a bottom-up merge pass runs underpcp->lockon drain, freeing larger chunks underzone->lock.
Quoted 7 lines
PCP refill uses a four-phase approach:
Phase 0: recover owned fragments previously drained to zone buddy. Phase 1: claim whole pageblocks from zone buddy.
Phase 2: grab sub-pageblock chunks without migratetype stealing. Phase 3: traditional__rmqueue()with migratetype fallback.
Since the migrate type passed to rmqueue_bulk, where these changes are, is the PCP migratetype, this will prefer MIGRATE_MOVABLE more than before in the presence of MIGRATE_CMA pageblocks, right?
Currently, the CMA fallback is done when > 50% of free zone memory is MIGRATE_CMA. For a PCP list, this isn't strictly true of course, since grabbing a page of the PCP list doesn't do this check, and MIGRATE_CMA doesn't have its own PCP list. But since rmqueue_bulk does do it, I'm guessing the fallback still mostly adheres to that 50%.
With this change to rmqueue_bulk, it feels like it would prefer MIGRATE_MOVABLE more, since that is the mt passed to it (never MIGRATE_CMA), and the fallback is only done if the final phase is needed.
Have you tested this with a zone that has a large amount of CMA in it and checked the percentages?
- Frank
Johannes Weiner
reviewerRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Quoted 48 lines · Frank van der Linden
Quoted 29 lines · Johannes Weiner
On large machines,
zone->lockis a scaling bottleneck for page allocation. Two common patterns drive contention:1. Affinity violations: pages are allocated on one CPU but freed on another (jemalloc, exit, reclaim). The freeing CPU's PCP drains to zone buddy, and the allocating CPU refills from zone buddy -- both under
zone->lock, defeating PCP batching entirely.2. Concurrent exits: processes tearing down large address spaces simultaneously overwhelm per-CPU PCP capacity, serializing on
zone->lockfor overflow.Solution
Extend the PCP to operate on whole pageblocks with ownership tracking.
Each CPU claims pageblocks from the zone buddy and splits them locally. Pages are tagged with their owning CPU, so frees route back to the owner's PCP regardless of which CPU frees. This eliminates affinity violations: the owner CPU's PCP absorbs both allocations and frees for its blocks without touching
zone->lock.It also shortens
zone->lockhold time during drain and refill cycles. Whole blocks are acquired underzone->lockand then split outside of it. Affinity routing to the owning PCP on free enables buddy merging outside thezone->lockas well; a bottom-up merge pass runs underpcp->lockon drain, freeing larger chunks underzone->lock.Quoted 7 lines
PCP refill uses a four-phase approach:
Phase 0: recover owned fragments previously drained to zone buddy. Phase 1: claim whole pageblocks from zone buddy.
Phase 2: grab sub-pageblock chunks without migratetype stealing. Phase 3: traditional__rmqueue()with migratetype fallback.Since the migrate type passed to
rmqueue_bulk, where these changes are, is the PCP migratetype, this will preferMIGRATE_MOVABLEmore than before in the presence ofMIGRATE_CMApageblocks, right?Currently, the CMA fallback is done when > 50% of free zone memory is
MIGRATE_CMA. For a PCP list, this isn't strictly true of course, since grabbing a page of the PCP list doesn't do this check, andMIGRATE_CMAdoesn't have its own PCP list. But sincermqueue_bulkdoes do it, I'm guessing the fallback still mostly adheres to that 50%.
Quoted 7 lines
With this change to
rmqueue_bulk, it feels like it would preferMIGRATE_MOVABLEmore, since that is the mt passed to it (neverMIGRATE_CMA), and the fallback is only done if the final phase is needed.Have you tested this with a zone that has a large amount of CMA in it and checked the percentages?
Good catch. Yes, I think there are problems here wrt CMA:
Phase 0 does not recover CMA blocks when movable is requested. That looks buggy. It should restore both block types.
Phase 1 grabbing whole new blocks actually does use __rmqueue(), so it gets the CMA fallback.
Phase 2 scans freelists based on requested type. This looks buggy as well. It should use the logic from the to of __rmqueue() to decide whether to grab CMA chunks instead.
Phase 3 is the regular __rmqueue() path again, which honors it.
It doesn't look hard to fix, but I'll be sure to test that.
kernel test robot
build botRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
In reply to Johannes Weinerkernel test robot noticed the following build errors:
Hi Johannes,
[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:
[auto build test ERROR on rppt-memblock/for-next]
[also build test ERROR on rppt-memblock/fixes linus/master v7.0-rc7 next-20260407] [cannot apply to akpm-mm/mm-everything]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Johannes-Weiner/mm-page_alloc-replace-pageblock_flags-bitmap-with-struct-pageblock_data/20260407-193348 base: https://git.kernel.org/pub/scm/linux/kernel/git/rppt/memblock.git for-next patch link: https://lore.kernel.org/r/20260403194526.477775-3-hannes%40cmpxchg.org patch subject: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator config: i386-allnoconfig-bpf (https://download.01.org/0day-ci/archive/20260408/[email protected]/config) compiler: gcc-14 (Debian 14.2.0-19) 14.2.0 reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260408/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/r/[email protected]/
All error/warnings (new ones prefixed by >>):
In file included from kernel/fork.c:118:
kernel/../mm/internal.h: In function 'pfn_to_pageblock':
>> kernel/../mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^
--
In file included from mm/filemap.c:54:
mm/internal.h: In function 'pfn_to_pageblock':
>> mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^
--
In file included from mm/mm_init.c:35:
mm/internal.h: In function 'pfn_to_pageblock':
>> mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^
mm/mm_init.c: In function 'usemap_size':
>> mm/mm_init.c:1456:39: error: invalid application of 'sizeof' to incomplete type 'struct pageblock_data'
1456 | return nr_pageblocks * sizeof(struct pageblock_data);
| ^~~~~~
>> mm/mm_init.c:1457:1: warning: control reaches end of non-void function [-Wreturn-type]
1457 | }
| ^
--
In file included from mm/page_alloc.c:58:
mm/internal.h: In function 'pfn_to_pageblock':
>> mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^
mm/page_alloc.c: In function 'get_pfnblock_flags_word':
>> mm/page_alloc.c:363:44: error: invalid use of undefined type 'struct pageblock_data'
363 | return &pfn_to_pageblock(page, pfn)->flags;
| ^~
>> mm/page_alloc.c:364:1: warning: control reaches end of non-void function [-Wreturn-type]
364 | }
| ^
--
In file included from fs/exec.c:82:
fs/../mm/internal.h: In function 'pfn_to_pageblock':
>> fs/../mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^
--
In file included from lib/vsprintf.c:51:
lib/../mm/internal.h: In function 'pfn_to_pageblock':
>> lib/../mm/internal.h:803:37: error: invalid use of undefined type 'struct pageblock_data'
803 | return &zone->pageblock_data[idx];
| ^vim +803 kernel/../mm/internal.h
8170ac4700d26f Zi Yan 2022-04-28 789
d88d3563065850 Johannes Weiner 2026-04-03 790 static inline struct pageblock_data *pfn_to_pageblock(const struct page *page,
d88d3563065850 Johannes Weiner 2026-04-03 791 unsigned long pfn)
d88d3563065850 Johannes Weiner 2026-04-03 792 {
d88d3563065850 Johannes Weiner 2026-04-03 793 #ifdef CONFIG_SPARSEMEM
d88d3563065850 Johannes Weiner 2026-04-03 794 struct mem_section *ms = __pfn_to_section(pfn);
d88d3563065850 Johannes Weiner 2026-04-03 795 unsigned long idx = (pfn & (PAGES_PER_SECTION - 1)) >> pageblock_order;
d88d3563065850 Johannes Weiner 2026-04-03 796
d88d3563065850 Johannes Weiner 2026-04-03 797 return §ion_to_usemap(ms)[idx];
d88d3563065850 Johannes Weiner 2026-04-03 798 #else
d88d3563065850 Johannes Weiner 2026-04-03 799 struct zone *zone = page_zone(page);
d88d3563065850 Johannes Weiner 2026-04-03 800 unsigned long idx;
d88d3563065850 Johannes Weiner 2026-04-03 801
d88d3563065850 Johannes Weiner 2026-04-03 802 idx = (pfn - pageblock_start_pfn(zone->zone_start_pfn)) >> pageblock_order;
d88d3563065850 Johannes Weiner 2026-04-03 @803 return &zone->pageblock_data[idx];
d88d3563065850 Johannes Weiner 2026-04-03 804 #endif
d88d3563065850 Johannes Weiner 2026-04-03 805 }d88d3563065850 Johannes Weiner 2026-04-03 806
Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki
Vlastimil Babka (SUSE)
maintainerRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
In reply to Johannes WeinerQuoted 8 lines · Johannes Weiner
On large machines,
zone->lockis a scaling bottleneck for page allocation. Two common patterns drive contention:1. Affinity violations: pages are allocated on one CPU but freed on another (jemalloc, exit, reclaim). The freeing CPU's PCP drains to zone buddy, and the allocating CPU refills from zone buddy -- both under
zone->lock, defeating PCP batching entirely.
Quoted 7 lines
2. Concurrent exits: processes tearing down large address spaces simultaneously overwhelm per-CPU PCP capacity, serializing on
zone->lockfor overflow.Solution
Extend the PCP to operate on whole pageblocks with ownership tracking.
Hi Johannes,
interesting ideas, as usual from you :) I'll try to point out some things that immediately came to mind, although it's not a thorough review.
Quoted 5 lines
Each CPU claims pageblocks from the zone buddy and splits them locally. Pages are tagged with their owning CPU, so frees route back to the owner's PCP regardless of which CPU frees. This eliminates affinity violations: the owner CPU's PCP absorbs both allocations and frees for its blocks without touching
zone->lock.
Details differ a lot of course (i.e. slab has no buddy merging) but I can see some parallel with SLUB's cpu slabs and these "cpu owned pageblocks". However SLUB moved into the direction of today's pcplists with replacing that with sheaves, and this is moving in the opposite direction :)
Quoted 9 lines
It also shortens
zone->lockhold time during drain and refill cycles. Whole blocks are acquired underzone->lockand then split outside of it. Affinity routing to the owning PCP on free enables buddy merging outside thezone->lockas well; a bottom-up merge pass runs underpcp->lockon drain, freeing larger chunks underzone->lock.PCP refill uses a four-phase approach:
Phase 0: recover owned fragments previously drained to zone buddy.
Note this is done using pfn scanning under zone lock. Is there a risk of defeating the short lock hold time goal?
Quoted 4 lines
Phase 1: claim whole pageblocks from zone buddy.
Phase 2: grab sub-pageblock chunks without migratetype stealing. Phase 3: traditional__rmqueue()with migratetype fallback.
Quoted 8 lines
Phase 0/1 pages are owned and marked PagePCPBuddy, making them eligible for PCP-level merging. Phase 2/3 pages are cached on PCP for batching only -- no ownership, no merging.
However, Phase 2 still
benefits from chunky zone transactions: it pulls higher-order entries from zone free lists underzone->lockand splits them on the PCP outside of it, rather than acquiringzone->lockper page.
I think this particular benefit could be possible to do even today without the other changes. Should we try it first?
Quoted 11 lines
When PCP batch sizes are small (small machines with few CPUs) or the zone is fragmented and no whole pageblocks are available, refill falls through to Phase 2/3 naturally. The allocator degrades gracefully to the original page-at-a-time behavior.
When owned blocks accumulate long-lived allocations (e.g. a mix of anonymous and file cache pages), partial block drains send the free fragments to zone buddy and remember the block, so Phase 0 can recover them on the next refill. This allows the allocator to pack new allocations next to existing ones in already-committed blocks rather than consuming fresh pageblocks, keeping fragmentation contained.
So this reads like there could be multiple owned blocks (is there any limit?) with only a bunch of free pages each, increasing my concern about pfn scanning under zone lock.
Quoted 60 lines
Data structures:
-
per_cpu_pages: +owned_blocks list head, +PCPF_CPU_DEAD flag to gate enqueuing on offline CPUs.
-pageblock_data: +cpu (owner), +block_pfn, +cpu_node (recovery list linkage). 32 bytes per pageblock, ~16KB per GB with 2MB pageblocks.
- PagePCPBuddy page type marks pages eligible for PCP-level merging.[[email protected]: fix ownership clearing on direct block frees]Signed-off-by Johannes Weiner <[email protected]>/*
mm/page_alloc.c +21
-5@@ -2907,9 +3205,11 @@ static void __free_frozen_pages(struct page *page, unsigned int order, {unsigned long UP_flags;struct per_cpu_pages *pcp; +struct pageblock_data *pbd;struct zone *zone;unsigned long pfn =page_to_pfn (page);int migratetype; +int owner_cpu, cache_cpu;if (!pcp_allowed_order (order)) {__free_pages_ok (page, order, fpi_flags);@@ -2927,7 +3227,8 @@ static void __free_frozen_pages(struct page *page, unsigned int order,* excessively into the page allocator */ zone =page_zone (page); - migratetype =get_pfnblock_migratetype (page, pfn); + pbd =pfn_to_pageblock (page, pfn); + migratetype =pbd_migratetype (pbd);if (unlikely (migratetype >=MIGRATE_PCPTYPES )) {if (unlikely (is_migrate_isolate (migratetype))) {free_one_page (zone, page, pfn, order, fpi_flags);@@ -2941,15 +3242,45 @@ static void __free_frozen_pages(struct page *page, unsigned int order,add_page_to_zone_llist (zone, page, order);return ; } - pcp =pcp_spin_trylock (zone->per_cpu_pageset, UP_flags); -if (pcp) { -if (!free_frozen_page_commit (zone, pcp, page, migratetype, - order, fpi_flags, &UP_flags)) + +/* +* Route page to the owning CPU's PCP for merging, or to +* the local PCP for batching (zone-owned pages). Zone-owned +* pages are cached without PagePCPBuddy -- the merge pass +* skips them, so they're inert on any PCP list and drain +* individually to zone buddy. +* +* Ownership is stable here: it can only change when the +* pageblock is complete -- either fully free in zone buddy +* (Phase 1 claims) or fully merged on PCP (drain disowns). +* Since we hold this page, neither can happen. +*/ + owner_cpu = pbd->cpu -1 ; + cache_cpu = owner_cpu; +if (cache_cpu <0 ) + cache_cpu =raw_smp_processor_id ();
mm/page_alloc.c static void __free_frozen_pages(struct page *page, unsigned int order, · line 3270
Quoted 10 lines
mm/page_alloc.c +7
-1+ + pcp =per_cpu_ptr (zone->per_cpu_pageset, cache_cpu); +if (unlikely (fpi_flags &FPI_TRYLOCK ) || !in_task ()) { +if (!spin_trylock_irqsave (&pcp->lock, UP_flags)) { +free_one_page (zone, page, pfn, order, fpi_flags);return ; -pcp_spin_unlock (pcp, UP_flags); + } }else { +spin_lock_irqsave (&pcp->lock, UP_flags);
Hm was it necessary to replace the pcp trylock scheme with spin_lock_irqsave() here?
Quoted 16 lines
mm/page_alloc.c +11
-0+ } + +if (unlikely (pcp->flags &PCPF_CPU_DEAD )) { +spin_unlock_irqrestore (&pcp->lock, UP_flags);free_one_page (zone, page, pfn, order, fpi_flags); +return ; } + +free_frozen_page_commit (zone, pcp, page, + migratetype, order, fpi_flags, + cache_cpu == owner_cpu); + +spin_unlock_irqrestore (&pcp->lock, UP_flags); }void free_frozen_pages (struct page *page,unsigned int order)
Johannes Weiner
reviewerRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Hey Vlastimil,
Quoted 13 lines · Vlastimil Babka (SUSE)
Quoted 12 lines · Johannes Weiner
On large machines,
zone->lockis a scaling bottleneck for page allocation. Two common patterns drive contention:1. Affinity violations: pages are allocated on one CPU but freed on another (jemalloc, exit, reclaim). The freeing CPU's PCP drains to zone buddy, and the allocating CPU refills from zone buddy -- both under
zone->lock, defeating PCP batching entirely.2. Concurrent exits: processes tearing down large address spaces simultaneously overwhelm per-CPU PCP capacity, serializing on
zone->lockfor overflow.
Quoted 8 lines
Quoted 3 lines
Solution
Extend the PCP to operate on whole pageblocks with ownership tracking.
Hi Johannes,
interesting ideas, as usual from you :) I'll try to point out some things that immediately came to mind, although it's not a thorough review.
Thanks for taking a look!
Quoted 10 lines
Quoted 5 lines
Each CPU claims pageblocks from the zone buddy and splits them locally. Pages are tagged with their owning CPU, so frees route back to the owner's PCP regardless of which CPU frees. This eliminates affinity violations: the owner CPU's PCP absorbs both allocations and frees for its blocks without touching
zone->lock.Details differ a lot of course (i.e. slab has no buddy merging) but I can see some parallel with SLUB's cpu slabs and these "cpu owned pageblocks". However SLUB moved into the direction of today's pcplists with replacing that with sheaves, and this is moving in the opposite direction :)
Let me think about this more. I've not attempted a deeper comparison with slub, but rather followed the data on painpoints in the current buddy / pcp allocator dynamics.
Quoted 6 lines
Quoted 6 lines
It also shortens
zone->lockhold time during drain and refill cycles. Whole blocks are acquired underzone->lockand then split outside of it. Affinity routing to the owning PCP on free enables buddy merging outside thezone->lockas well; a bottom-up merge pass runs underpcp->lockon drain, freeing larger chunks underzone->lock.
Quoted 6 lines
Quoted 3 lines
PCP refill uses a four-phase approach:
Phase 0: recover owned fragments previously drained to zone buddy.
Note this is done using pfn scanning under zone lock. Is there a risk of defeating the short lock hold time goal?
This is part of a larger question, let me take a stab below.
Quoted 8 lines
Quoted 7 lines
Phase 1: claim whole pageblocks from zone buddy.
Phase 2: grab sub-pageblock chunks without migratetype stealing. Phase 3: traditional__rmqueue()with migratetype fallback.Phase 0/1 pages are owned and marked PagePCPBuddy, making them eligible for PCP-level merging. Phase 2/3 pages are cached on PCP for batching only -- no ownership, no merging.
Quoted 7 lines
Quoted 4 lines
However, Phase 2 still
benefits from chunky zone transactions: it pulls higher-order entries from zone free lists underzone->lockand splits them on the PCP outside of it, rather than acquiringzone->lockper page.I think this particular benefit could be possible to do even today without the other changes. Should we try it first?
I'll experiment with that in isolation. I would expect it to help in the allocation paths.
That said, the worst congestion we've seen were all triggered by the freeing paths. Faults and allocations tend to be more spread out over time. It's the frees that happen in CPU-bound avalanches of order-0.
Quoted 12 lines
Quoted 11 lines
When PCP batch sizes are small (small machines with few CPUs) or the zone is fragmented and no whole pageblocks are available, refill falls through to Phase 2/3 naturally. The allocator degrades gracefully to the original page-at-a-time behavior.
When owned blocks accumulate long-lived allocations (e.g. a mix of anonymous and file cache pages), partial block drains send the free fragments to zone buddy and remember the block, so Phase 0 can recover them on the next refill. This allows the allocator to pack new allocations next to existing ones in already-committed blocks rather than consuming fresh pageblocks, keeping fragmentation contained.
Quoted 3 lines
So this reads like there could be multiple owned blocks (is there any limit?) with only a bunch of free pages each, increasing my concern about pfn scanning under zone lock.
Yes, it's a concern right now, and needs more work.
The list is built from PCP fragments on drain, and fully consumed on refill (migratetype mismatch aside, need to fix). That caps the list at pcp->high_max - pcp->batch blocks in the worst case (when there is only one free page in each block).
Those last free pages can get stolen by another CPU before the next refill, resulting in a PFN walk worst-case of (pcp->high_max - pcp->batch) * pageblock_nr_pages.
Some ideas I need to try out:
- First I think we can bound the zone->lock hold period easily by cycling the lock after each block.
- We could maintain a free counter in pageblock_data to terminate the scan early if no buddies remain.
- We might be able to hard limit the PFN scans to 2x or 4x pages_needed, then fall through to grabbing individual pages. We shouldn't get new blocks while there are unrecovered partial blocks, or it would defeat the point of recovery (runaway consumption of new blocks pinned by a couple of long-lived allocations). The dynamics this would add are a bit harder to reason about.
Quoted 30 lines
Quoted 30 lines
mm/page_alloc.c +22
-4@@ -2941,15 +3242,45 @@ static void __free_frozen_pages(struct page *page, unsigned int order,add_page_to_zone_llist (zone, page, order);return ; } - pcp =pcp_spin_trylock (zone->per_cpu_pageset, UP_flags); -if (pcp) { -if (!free_frozen_page_commit (zone, pcp, page, migratetype, - order, fpi_flags, &UP_flags)) + +/* +* Route page to the owning CPU's PCP for merging, or to +* the local PCP for batching (zone-owned pages). Zone-owned +* pages are cached without PagePCPBuddy -- the merge pass +* skips them, so they're inert on any PCP list and drain +* individually to zone buddy. +* +* Ownership is stable here: it can only change when the +* pageblock is complete -- either fully free in zone buddy +* (Phase 1 claims) or fully merged on PCP (drain disowns). +* Since we hold this page, neither can happen. +*/ + owner_cpu = pbd->cpu -1 ; + cache_cpu = owner_cpu; +if (cache_cpu <0 ) + cache_cpu =raw_smp_processor_id (); + + pcp =per_cpu_ptr (zone->per_cpu_pageset, cache_cpu); +if (unlikely (fpi_flags &FPI_TRYLOCK ) || !in_task ()) { +if (!spin_trylock_irqsave (&pcp->lock, UP_flags)) { +free_one_page (zone, page, pfn, order, fpi_flags);
Quoted 8 lines
mm/page_alloc.c static void __free_frozen_pages(struct page *page, unsigned int order, · line 3270
Quoted 5 lines
mm/page_alloc.c +2
-1return ; -pcp_spin_unlock (pcp, UP_flags); + } }else { +spin_lock_irqsave (&pcp->lock, UP_flags);Hm was it necessary to replace the pcp trylock scheme with
spin_lock_irqsave()here?
It's beneficial.
Before, this would only be contended with preemption; the trylock was needed to avoid a deadlock.
After, we can have contention when freeing to a remote PCP that's busy. But giving the page back to that owning PCP is still the best destination for it. A trylock with a zone buddy fallback means a zone->lock cycle now AND for a single page AND increases the odds of a zone->locked refill later (since that page leaves the PCP economy).
What *might* work is an llist on that PCP, leaving it to the next successful PCP holder to drain. But that means more work under the pcp->lock on the allocation and drain side, so it could be a wash.
Re: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
In reply to Johannes WeinerOn Fri, 3 Apr 2026 at 15:40 PM Johannes Weiner <[email protected]> wrote:
[...]
Quoted 1 line
(quoted diff) +0
-0@@ -2941,15 +3242,45 @@ static void __free_frozen_pages(struct page *page, unsigned int order,
[...]
Quoted 10 lines
(quoted diff) +7
-1+ pcp = per_cpu_ptr(zone->per_cpu_pageset, cache_cpu); + if (unlikely(fpi_flags & FPI_TRYLOCK) || !in_task()) { + if (!spin_trylock_irqsave(&pcp->lock, UP_flags)) { + free_one_page(zone, page, pfn, order, fpi_flags); return; - pcp_spin_unlock(pcp, UP_flags); + } } else { + spin_lock_irqsave(&pcp->lock, UP_flags); + }
[...]
Quoted 1 line
(quoted diff) +0
-0@@ -3025,17 +3369,35 @@ void free_unref_folios(struct folio_batch *folios)
[...]
Review
Quoted 11 lines
(quoted diff) +11
-0+ if (!in_task()) { + if (unlikely(!spin_trylock_irqsave( + &pcp->lock, UP_flags))) { + pcp = NULL; + free_one_page(zone, &folio->page, pfn, + order, FPI_NONE); + continue; + } + } else { + spin_lock_irqsave(&pcp->lock, UP_flags); + }
Hello Johannes,
Thank you for the great work on this series -- I hope it is still being actively worked on.
We are suffering from heavy zone->lock contention on our production servers as well, so I backported this series to our internal 6.18.y kernel. However, since deploying it to a few dozen production servers running workloads with heavy memory and I/O pressure, we have been hitting hard lockups at a rate of roughly one every day or two. The hard lockups look as follows:
[149519.005207] watchdog: CPU22: Watchdog detected hard LOCKUP on cpu 22 [149519.005211] Modules linked in: af_packet_diag netlink_diag squashfs loop zram xt_owner xt_DSCP cls_bpf sch_ingress xt_CT nft_compat bpf_preload mptcp_diag raw_diag unix_diag binfmt_misc udp_diag tcp_diag inet_diag nf_tables xt_conntrack nf_nat nf_conntrack_netlink nfnetlink nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 af_packet bonding overlay ipmi_ssif amd_atl intel_rapl_msr intel_rapl_common amd64_edac kvm_amd dax_hmem cxl_acpi cxl_port mlx5_ib cxl_pmem kvm acpi_ipmi ib_uverbs irqbypass vfat ipmi_si cxl_core i2c_piix4 ipmi_devintf fat rapl einj acpi_cpufreq ib_core pcspkr i2c_smbus xfs ipmi_msghandler k10temp i2c_designware_platform i2c_designware_core input_leds sch_fq_codel drm fuse backlight ext4 crc16 mbcache jbd2 polyval_clmulni ghash_clmulni_intel mlx5_core mlxfw tls nvme psample ptp nvme_core ccp pps_core sd_mod sg ahci libahci libata aesni_intel [149519.005260] CPU: 22 UID: 10305 PID: 3050692 Comm: java Kdump: loaded Not tainted 6.18.44-3 #3.infra PREEMPT(voluntary) [149519.005263] Hardware name: ZTE R5350 G5/MB53A05A, BIOS 24.25.02.02 04/30/2025 [149519.005264] RIP: 0010:queued_spin_lock_slowpath+0x299/0x2d0 [149519.005270] Code: 83 e0 03 83 e9 01 48 c1 e0 04 48 63 c9 48 05 80 48 61 9f 48 03 04 cd c0 5c 6b 9e 48 89 10 8b 42 08 85 c0 75 09 f3 90 8b 42 08 <85> c0 74 f7 48 8b 0a 48 85 c9 0f 84 6a ff ff ff 0f 0d 09 e9 62 ff [149519.005271] RSP: 0018:ff7d3f62682ef678 EFLAGS: 00000046 [149519.005272] RAX: 0000000000000000 RBX: ff483cf409daf880 RCX: 00000000000000bc [149519.005273] RDX: ff483cf409daf880 RSI: 0000000002f40100 RDI: ff483cf40ad75540 [149519.005273] RBP: ff7d3f62682ef698 R08: 0000000000000055 R09: 0000000000000000 [149519.005274] R10: ffb3caab519aee00 R11: 0000000000000001 R12: ff483cf40ad75540 [149519.005274] R13: 00000000005c0000 R14: 00000000005c0000 R15: 000000000000000e [149519.005275] FS: 0000000000000000(0000) GS:ff483cf46a79b000(0000) knlGS:0000000000000000 [149519.005276] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [149519.005276] CR2: 00007fd14532b000 CR3: 000000061d798798 CR4: 0000000000771ef0 [149519.005277] PKRU: 55555554 [149519.005277] Call Trace: [149519.005278] <TASK> [149519.005282] _raw_spin_lock_irqsave+0x51/0x60 [149519.005284] free_unref_folios+0x60c/0xaa0 [149519.005289] folios_put_refs+0x182/0x210 [149519.005292] free_pages_and_swap_cache+0xc7/0x170 [149519.005294] ? __entry_text_start+0xf/0x30 [149519.005297] __tlb_batch_free_encoded_pages+0x47/0xb0 [149519.005300] tlb_flush_mmu+0x4f/0x140 [149519.005301] zap_pte_range+0x300/0x490 [149519.005303] zap_pmd_range.isra.0+0xc4/0x220 [149519.005305] unmap_page_range+0x270/0x3d0 [149519.005306] unmap_single_vma.constprop.0+0x7d/0xc0 [149519.005309] unmap_vmas+0x92/0x160 [149519.005311] exit_mmap+0xf2/0x400 [149519.005313] ? mutex_lock+0x13/0x50 [149519.005315] __mmput+0x52/0x120 [149519.005318] mmput+0x30/0x40 [149519.005320] exit_mm+0xe7/0x150 [149519.005321] do_exit+0x1c7/0x490 [149519.005322] do_group_exit+0x34/0x90 [149519.005324] get_signal+0x919/0x960 [149519.005326] arch_do_signal_or_restart+0x29/0x100 [149519.005327] ? __x64_sys_futex+0x77/0x1e0 [149519.005330] exit_to_user_mode_loop+0xa0/0x120 [149519.005333] do_syscall_64+0x1ea/0xe10 [149519.005335] entry_SYSCALL_64_after_hwframe+0x76/0x7e [149519.005336] RIP: 0033:0x7f9ed929c39a [149519.005342] Code: Unable to access opcode bytes at 0x7f9ed929c370. [149519.005343] RSP: 002b:00007f9e8d2fe300 EFLAGS: 00000246 ORIG_RAX: 00000000000000ca [149519.005343] RAX: fffffffffffffe00 RBX: 0000000000000000 RCX: 00007f9ed929c39a [149519.005344] RDX: 0000000000000000 RSI: 0000000000000189 RDI: 00007f9ed6074b3c [149519.005344] RBP: 0000000000000000 R08: 0000000000000000 R09: 00000000ffffffff [149519.005345] R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000 [149519.005345] R13: 00007f9ed6074b3c R14: 0000000000000001 R15: 0000000000000000 [149519.005347] </TASK> [149519.005348] Kernel panic - not syncing: Hard LOCKUP [149519.005349] CPU: 22 UID: 10305 PID: 3050692 Comm: java Kdump: loaded Not tainted 6.18.44-3 #3.infra PREEMPT(voluntary) [149519.005350] Hardware name: ZTE R5350 G5/MB53A05A, BIOS 24.25.02.02 04/30/2025 [149519.005350] Call Trace: [149519.005351] <NMI> [149519.005351] dump_stack_lvl+0x26/0xb0 [149519.005353] dump_stack+0x10/0x20 [149519.005354] vpanic+0x34d/0x3a0 [149519.005355] panic+0x57/0x60 [149519.005357] nmi_panic+0x2b/0x60 [149519.005358] watchdog_hardlockup_check+0x1b4/0x200 [149519.005360] watchdog_overflow_callback+0x7c/0x90 [149519.005362] __perf_event_overflow+0x11c/0x3b0 [149519.005365] perf_event_overflow+0x19/0x20 [149519.005366] amd_pmu_v2_handle_irq+0x1f5/0x3e0 [149519.005369] ? flush_tlb_one_kernel+0xe/0x30 [149519.005371] ? set_pte_vaddr_p4d+0x4f/0x60 [149519.005373] ? set_pte_vaddr+0x7b/0xb0 [149519.005373] ? native_set_fixmap+0x59/0x90 [149519.005375] ? ghes_copy_tofrom_phys+0x75/0x120 [149519.005378] ? __ghes_peek_estatus.isra.0+0x4e/0xc0 [149519.005380] ? ghes_in_nmi_queue_one_entry.constprop.0+0x3c/0x2a0 [149519.005382] perf_event_nmi_handler+0x2d/0x50 [149519.005384] nmi_handle.part.0+0x5a/0x160 [149519.005386] default_do_nmi+0x11c/0x160 [149519.005387] exc_nmi+0x10b/0x1a0 [149519.005388] end_repeat_nmi+0xf/0x53 [149519.005389] RIP: 0010:queued_spin_lock_slowpath+0x299/0x2d0 [149519.005391] Code: 83 e0 03 83 e9 01 48 c1 e0 04 48 63 c9 48 05 80 48 61 9f 48 03 04 cd c0 5c 6b 9e 48 89 10 8b 42 08 85 c0 75 09 f3 90 8b 42 08 <85> c0 74 f7 48 8b 0a 48 85 c9 0f 84 6a ff ff ff 0f 0d 09 e9 62 ff [149519.005391] RSP: 0018:ff7d3f62682ef678 EFLAGS: 00000046 [149519.005392] RAX: 0000000000000000 RBX: ff483cf409daf880 RCX: 00000000000000bc [149519.005392] RDX: ff483cf409daf880 RSI: 0000000002f40100 RDI: ff483cf40ad75540 [149519.005393] RBP: ff7d3f62682ef698 R08: 0000000000000055 R09: 0000000000000000 [149519.005393] R10: ffb3caab519aee00 R11: 0000000000000001 R12: ff483cf40ad75540 [149519.005394] R13: 00000000005c0000 R14: 00000000005c0000 R15: 000000000000000e [149519.005395] ? queued_spin_lock_slowpath+0x299/0x2d0 [149519.005396] ? queued_spin_lock_slowpath+0x299/0x2d0 [149519.005398] </NMI> [149519.005398] <TASK> [149519.005398] _raw_spin_lock_irqsave+0x51/0x60 [149519.005400] free_unref_folios+0x60c/0xaa0 [149519.005402] folios_put_refs+0x182/0x210 [149519.005404] free_pages_and_swap_cache+0xc7/0x170 [149519.005405] ? __entry_text_start+0xf/0x30 [149519.005407] __tlb_batch_free_encoded_pages+0x47/0xb0 [149519.005409] tlb_flush_mmu+0x4f/0x140 [149519.005410] zap_pte_range+0x300/0x490 [149519.005412] zap_pmd_range.isra.0+0xc4/0x220 [149519.005413] unmap_page_range+0x270/0x3d0 [149519.005414] unmap_single_vma.constprop.0+0x7d/0xc0 [149519.005415] unmap_vmas+0x92/0x160 [149519.005417] exit_mmap+0xf2/0x400 [149519.005419] ? mutex_lock+0x13/0x50 [149519.005421] __mmput+0x52/0x120 [149519.005422] mmput+0x30/0x40 [149519.005424] exit_mm+0xe7/0x150 [149519.005425] do_exit+0x1c7/0x490 [149519.005426] do_group_exit+0x34/0x90 [149519.005427] get_signal+0x919/0x960 [149519.005428] arch_do_signal_or_restart+0x29/0x100 [149519.005429] ? __x64_sys_futex+0x77/0x1e0 [149519.005430] exit_to_user_mode_loop+0xa0/0x120 [149519.005432] do_syscall_64+0x1ea/0xe10 [149519.005433] entry_SYSCALL_64_after_hwframe+0x76/0x7e [149519.005434] RIP: 0033:0x7f9ed929c39a [149519.005435] Code: Unable to access opcode bytes at 0x7f9ed929c370. [149519.005435] RSP: 002b:00007f9e8d2fe300 EFLAGS: 00000246 ORIG_RAX: 00000000000000ca [149519.005436] RAX: fffffffffffffe00 RBX: 0000000000000000 RCX: 00007f9ed929c39a [149519.005436] RDX: 0000000000000000 RSI: 0000000000000189 RDI: 00007f9ed6074b3c [149519.005436] RBP: 0000000000000000 R08: 0000000000000000 R09: 00000000ffffffff [149519.005437] R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000 [149519.005437] R13: 00007f9ed6074b3c R14: 0000000000000001 R15: 0000000000000000 [149519.005438] </TASK>
This hard lockup can be fixed by the following changes on top of your series:
mm/page_alloc.c +9 -17
@@ -3266,13 +3266,9 @@ static void __free_frozen_pages(struct page *page, unsigned int order, cache_cpu =raw_smp_processor_id (); pcp =per_cpu_ptr (zone->per_cpu_pageset, cache_cpu); -if (unlikely (fpi_flags &FPI_TRYLOCK ) || !in_task ()) { -if (!spin_trylock_irqsave (&pcp->lock, UP_flags)) { -free_one_page (zone, page, pfn, order, fpi_flags); -return ; - } - }else { -spin_lock_irqsave (&pcp->lock, UP_flags); +if (!spin_trylock_irqsave (&pcp->lock, UP_flags)) { +free_one_page (zone, page, pfn, order, fpi_flags); +return ; }if (unlikely (pcp->flags &PCPF_CPU_DEAD )) {
@@ -3378,16 +3374,12 @@ void free_unref_folios(struct folio_batch *folios)* contention on a per-CPU lock beats the * unbatched zone->lock fallback. */ -if (!in_task ()) { -if (unlikely (!spin_trylock_irqsave ( - &pcp->lock, UP_flags))) { - pcp =NULL ; -free_one_page (zone, &folio->page, pfn, - order,FPI_NONE ); -continue ; - } - }else { -spin_lock_irqsave (&pcp->lock, UP_flags); +if (unlikely (!spin_trylock_irqsave ( + &pcp->lock, UP_flags))) { + pcp =NULL ; +free_one_page (zone, &folio->page, pfn, + order,FPI_NONE ); +continue ; }if (unlikely (pcp->flags &PCPF_CPU_DEAD )) {spin_unlock_irqrestore (&pcp->lock, UP_flags);
With these changes applied, the affected servers have been running lockup-free for more than two weeks so far.
If you have any updates on this series, we would be happy to test them on our production servers and report back.
Thanks
Johannes Weiner
reviewerRe: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Hello Yafang,
Quoted 35 lines · Yafang Shao
On Fri, 3 Apr 2026 at 15:40 PM Johannes Weiner <[email protected]> wrote:
[...]
Quoted 1 line
(quoted diff) +0
-0@@ -2941,15 +3242,45 @@ static void __free_frozen_pages(struct page *page, unsigned int order,[...]
Quoted 10 lines
(quoted diff) +7
-1+ pcp = per_cpu_ptr(zone->per_cpu_pageset, cache_cpu); + if (unlikely(fpi_flags & FPI_TRYLOCK) || !in_task()) { + if (!spin_trylock_irqsave(&pcp->lock, UP_flags)) { + free_one_page(zone, page, pfn, order, fpi_flags); return; - pcp_spin_unlock(pcp, UP_flags); + } } else { + spin_lock_irqsave(&pcp->lock, UP_flags); + }[...]
Quoted 1 line
(quoted diff) +0
-0@@ -3025,17 +3369,35 @@ void free_unref_folios(struct folio_batch *folios)[...]
mm/page_alloc.c void free_unref_folios(struct folio_batch *folios)
Quoted 11 lines
mm/page_alloc.c +11
-0+if (!in_task ()) { +if (unlikely (!spin_trylock_irqsave ( + &pcp->lock, UP_flags))) { + pcp =NULL ; +free_one_page (zone, &folio->page, pfn, + order,FPI_NONE ); +continue ; + } + }else { +spin_lock_irqsave (&pcp->lock, UP_flags); + }Hello Johannes,
Quoted 2 lines
Thank you for the great work on this series -- I hope it is still being actively worked on.
Thanks for the kind words.
I am still actively working on it. Since the last iteration I have addressed a few things:
1. The locking bug you are seeing. Rik had also run into this during stress testing. The fallback to the zone buddy on PCP contention brought back some of the original zone->lock contention. So instead I'm using the zone llist introduced for lockless allocations.
2. The PFN search for block recovery that Vlastimil pointed out. I've tried various solutions (counters, bitmaps) but the thing that worked best was having the zone buddy itself maintain free pages of owned blocks on a per-block loaner list (in addition to the regular zone freelists). This eliminates the sparse search altogether. Recovery is
then: pcp->owned_blocks -> pbd->buddy_loans -> page. Every page visited gets recovered. For the loaner list_head, I'm reusing mapping/index space that's unused in a freed page.
3. Removed the unowned buddy splitting on the PCP. Vlastimil had actually asked to try that separately, as an incremental step, since it's self contained. I tried this but realized that part was actually bad altogether. It violates the rmqueue_smallest policy and causes runaway fragmentation - just like the new block claiming did before I added the block recovery step beforehand.
So now refilling is just block recovery -> new blocks -> unowned singles of the requested order.
Incidentally, this also eliminated the CMA problem that Frank pointed out, since the other refill paths respect ALLOC_CMA.
4. I realized I'm also violating the smallest-first policy in how I was mixing owned and unowned chunks on the same freelists. For example, an order-3 refill from singles sits next to order-3 fragments from owned blocks. Only owned fragments, which route back to and reassemble on that PCP, must be split. Unowned singles must be consumed at their native order to preserve smallest-first policy.
pcp_rmqueue_smallest() could check the PagePCPBuddy() flag to tell which ones can be split, but that introduces another sparse search problem, where we might walk higher order lists in the hope to find a splittable owned buddy.
To avoid this, I retained the legacy/unowned pcp freelists (up to costly order and THP), and added a second set of buddy freelists up to pageblock order to the PCP. This way the rule can be maintained with O(1) list checks instead of O(pcp size) scans.
5. The on-demand merging at drain time proved problematic. Draining isn't exhaustive, so it can attempt to merge the same unmergeable fragments repeatedly. I moved merging into the pcp free path instead, so every page is tried for merging exactly once, which seems to perform a lot better in performance testing.
Overall, it's gotten a bit bigger than I had hoped for. But it also looks much more robust. And the additions described above seem well offset by performance improvements in tests so far, even on smaller machines.
I'm still testing and polishing right now, and hoping to send a new version soon.
Quoted 6 lines
We are suffering from heavy
zone->lockcontention on our production servers as well, so I backported this series to our internal 6.18.y kernel. However, since deploying it to a few dozen production servers running workloads with heavy memory and I/O pressure, we have been hitting hard lockups at a rate of roughly one every day or two. The hard lockups look as follows:
[...]
Quoted 2 lines
With these changes applied, the affected servers have been running lockup-free for more than two weeks so far.
I'm assuming you saw an improvement of zone->lock contention. Would you be able to share some numbers or observations?
Thanks again!
Re: [RFC 2/2] mm: page_alloc: per-cpu pageblock buddy allocator
Quoted 4 lines · Johannes Weiner
Hello Yafang,
On Fri, Sep 18, 2026 at 10:22:22AM +0800, Yafang Shao wrote:
[...]
Quoted 6 lines
Quoted 5 lines
Hello Johannes,
Thank you for the great work on this series -- I hope it is still being actively worked on.
Quoted 8 lines
Thanks for the kind words.
I am still actively working on it. Since the last iteration I have addressed a few things:
1. The locking bug you are seeing. Rik had also run into this during stress testing. The fallback to the zone buddy on PCP contention brought back some of the original
zone->lockcontention.
Right, I noticed that the zone::lock contention increased slightly after I applied the livepatch above.
Quoted 2 lines
So instead
I'm using the zone llist introduced for lockless allocations.
That is good news!
Quoted 46 lines
2. The PFN search for block recovery that Vlastimil pointed out. I've tried various solutions (counters, bitmaps) but the thing that worked best was having the zone buddy itself maintain free pages of owned blocks on a per-block loaner list (in addition to the regular zone freelists). This eliminates the sparse search altogether. Recovery is
then:pcp->owned_blocks->pbd->buddy_loans-> page. Every page visited gets recovered. For the loanerlist_head, I'm reusing mapping/index space that's unused in a freed page.3. Removed the unowned buddy splitting on the PCP. Vlastimil had actually asked to try that separately, as an incremental step, since it's self contained. I tried this but realized that part was actually bad altogether. It violates the
rmqueue_smallestpolicy and causes runaway fragmentation - just like the new block claiming did before I added the block recovery step beforehand.So now refilling is just block recovery -> new blocks -> unowned singles of the requested order.
Incidentally, this also eliminated the CMA problem that Frank pointed out, since the other refill paths respect
ALLOC_CMA.4. I realized I'm also violating the smallest-first policy in how I was mixing owned and unowned chunks on the same freelists. For example, an order-3 refill from singles sits next to order-3 fragments from owned blocks. Only owned fragments, which route back to and reassemble on that PCP, must be split. Unowned singles must be consumed at their native order to preserve smallest-first policy.
pcp_rmqueue_smallest()could check thePagePCPBuddy()flag to tell which ones can be split, but that introduces another sparse search problem, where we might walk higher order lists in the hope to find a splittable owned buddy.To avoid this, I retained the legacy/unowned pcp freelists (up to costly order and THP), and added a second set of buddy freelists up to pageblock order to the PCP. This way the rule can be maintained with O(1) list checks instead of O(pcp size) scans.
5. The on-demand merging at drain time proved problematic. Draining isn't exhaustive, so it can attempt to merge the same unmergeable fragments repeatedly. I moved merging into the pcp free path instead, so every page is tried for merging exactly once, which seems to perform a lot better in performance testing.
Quoted 4 lines
Overall, it's gotten a bit bigger than I had hoped for. But it also looks much more robust. And the additions described above seem well offset by performance improvements in tests so far, even on smaller machines.
It will take me some time to fully understand your work, but thank you so much for your great effort in resolving this long-standing zone::lock contention issue.
Quoted 3 lines
I'm still testing and polishing right now, and hoping to send a new version soon.
Great
Quoted 8 lines
Quoted 7 lines
We are suffering from heavy
zone->lockcontention on our production servers as well, so I backported this series to our internal 6.18.y kernel. However, since deploying it to a few dozen production servers running workloads with heavy memory and I/O pressure, we have been hitting hard lockups at a rate of roughly one every day or two. The hard lockups look as follows:
Quoted 7 lines
[...]
Quoted 2 lines
With these changes applied, the affected servers have been running lockup-free for more than two weeks so far.
I'm assuming you saw an improvement of
zone->lockcontention. Would you be able to share some numbers or observations?
The result is great. Below are the observations from our real production workloads.
On our Kubernetes servers, many different applications (Pods) are deployed on a single host, and redis is very latency-sensitive. Whenever other Pods exit simultaneously, or any Pod allocates or frees a large amount of memory, redis easily hits latency spikes, and its P99 can quickly reach a level the application can't tolerate.
This issue is clearly reflected by the TCPTimeouts metric in /proc/net/netstat, since the network receive path also needs to hold the zone::lock. Before your improvement, Redis's TCPTimeouts could reach tens or even hundreds whenever other Pods exited simultaneously or allocated/freed large amounts of memory. With your improvement applied, TCPTimeouts has stayed below 10 and Redis's P99 has remained acceptable. After I deployed the hotfix to work around the hard lockup issue, TCPTimeouts rose slightly, but it is still far lower than before your improvement.
Signature · 2 lines
Regards Yafang
Zi Yan
reviewerQuoted 14 lines · Johannes Weiner
Hi,
this is an RFC for making the page allocator scale better with higher thread counts and larger memory quantities.
In Meta production, we're seeing increasing
zone->lockcontention that was traced back to a few different paths. A prominent one is the userspace allocator, jemalloc. Allocations happen from page faults on all CPUs running the workload. Frees are cached for reuse, but the caches are periodically purged back to the kernel from a handful of purger threads. This breaks affinity between allocations and frees:
Both sides use their own PCPs - one side depletes them, the other one overfills them. Both sides routinely hit thezone->lockedslowpath.
Quoted 8 lines
My understanding is that tcmalloc has a similar architecture.
Another contributor to contention is process exits, where large numbers of pages are freed at once. The current PCP can only reduce lock time when pages are reused. Reuse is unlikely because it's an avalanche of free pages on a CPU busy walking page tables. Every time the PCP overflows, the drain acquires the
zone->lockand frees pages one by one, trying to merge buddies together.
IIUC, zone->lock held time is mostly spent on free page merging. Have you tried to let PCP do the free page merging before holding zone->lock and returning free pages to buddy? That is a much smaller change than what you proposed. This method might not work if physically contiguous free pages are allocated by separate CPUs, so that PCP merging cannot be done. But this might be rare?
Quoted 5 lines
The idea proposed here is this: instead of single pages, make the PCP grab entire pageblocks, split them outside the
zone->lock. That CPU then takes ownership of the block, and all frees route back to that PCP instead of the freeing CPU's local one.
This is basically distributed buddy allocators, right? Instead of relying on a single zone->lock, PCP locks are used. The worst case it can face is that physically contiguous free pages are allocated across all CPUs, so that all CPUs are competing a single PCP lock. It seems that you have not hit this. So I wonder if what I proposed above might work as a simpler approach. Let me know if I miss anything.
I wonder how this distributed buddy allocators would work if anyone wants to allocate >pageblock free pages, like alloc_contig_range(). Multiple PCP locks need to be taken one by one. Maybe it is better than taking and dropping zone->lock repeatedly. Have you benchmarked alloc_contig_range(), like hugetlb allocation?
Quoted 11 lines
This has several benefits:
1. It's right away coarser/fewer allocations transactions under the
zone->lock.1a. Even if no full free blocks are available (memory pressure or
small zone), with splitting available at the PCP level means the PCP can still grab chunks larger than the requested order from thezone->lockfreelists, and dole them out on its own time.
Quoted 6 lines
2. The pages free back to where the allocations happen, increasing the odds of reuse and reducing the chances of
zone->lockslowpaths.3. The page buddies come back into one place, allowing upfront merging under the local
pcp->lock. This makes coarser/fewer freeing transactions under thezone->lock.
I wonder if we could go more radical by moving buddy allocator out of zone->lock completely to PCP lock. If one PCP runs out of free pages, it can steal another PCP's whole pageblock. I probably should do some literature investigation on this. Some research must have been done on this.
Quoted 18 lines
The big concern is fragmentation. Movable allocations tend to be a mix of short-lived anon and long-lived file cache pages. By the time the PCP needs to drain due to thresholds or pressure, the blocks might not be fully re-assembled yet. To prevent gobbling up and fragmenting ever more blocks, partial blocks are remembered on drain and their pages queued last on the zone freelist. When a PCP refills, it first tries to recover any such fragment blocks.
On small or pressured machines, the PCP degrades to its previous behavior. If a whole block doesn't fit the
pcp->highlimit, or a whole block isn't available, the refill grabs smaller chunks that aren't marked for ownership. The free side will use the local PCP as before.I still need to run broader benchmarks, but I've been consistently seeing a 3-4% reduction in %sys time for simple kernel builds on my 32-way, 32G RAM test machine.
Quoted 7 lines
A synthetic test on the same machine that allocates on many CPUs and frees on just a few sees a consistent 1% increase in throughput.
I would expect those numbers to increase with higher concurrency and larger memory volumes, but verifying that is TBD.
Sending an RFC to get an early gauge on direction.
Thank you for sending this out. :)
Quoted 11 lines
Based on
0257f64bdac7fdca30fa3cae0df8b9ecbec7733a.include/linux/mmzone.h | 38 ++- include/linux/page-flags.h | 9 + mm/debug.c | 1 + mm/internal.h | 17 + mm/mm_init.c | 25 +- mm/page_alloc.c | 784 +++++++++++++++++++++++++++++++------------ mm/sparse.c | 3 +- 7 files changed, 622 insertions(+), 255 deletions(-)
--
Best Regards,
Yan, Zi
Johannes Weiner
reviewerQuoted 22 lines · Zi Yan
Quoted 12 lines · Johannes Weiner
this is an RFC for making the page allocator scale better with higher thread counts and larger memory quantities.
In Meta production, we're seeing increasing
zone->lockcontention that was traced back to a few different paths. A prominent one is the userspace allocator, jemalloc. Allocations happen from page faults on all CPUs running the workload. Frees are cached for reuse, but the caches are periodically purged back to the kernel from a handful of purger threads. This breaks affinity between allocations and frees:
Both sides use their own PCPs - one side depletes them, the other one overfills them. Both sides routinely hit thezone->lockedslowpath.Quoted 8 lines
My understanding is that tcmalloc has a similar architecture.
Another contributor to contention is process exits, where large numbers of pages are freed at once. The current PCP can only reduce lock time when pages are reused. Reuse is unlikely because it's an avalanche of free pages on a CPU busy walking page tables. Every time the PCP overflows, the drain acquires the
zone->lockand frees pages one by one, trying to merge buddies together.
Quoted 6 lines
IIUC,
zone->lockheld time is mostly spent on free page merging. Have you tried to let PCP do the free page merging before holdingzone->lockand returning free pages to buddy? That is a much smaller change than what you proposed. This method might not work if physically contiguous free pages are allocated by separate CPUs, so that PCP merging cannot be done. But this might be rare?
On my 32G system, pcp->high_min for zone Normal is 988. That's one block and a half. The rmqueue_smallest policy means the next CPU will prefer the remainder of that partial block. So if there is concurrency, every other block is shared. Not exactly uncommon. The effect lessens the larger the machine is, of course.
But let's assume it's not an issue. How do you know you can safely merge with a buddy pfn? You need to establish that it's on that same PCP's list. Short of *scanning* the list, it seems something like PagePCPBuddy() and page->pcp_cpu is inevitably needed. But of course a per-page cpu field is tough to come by.
So the block ownership is more natural, and then you might as well use that for affinity routing to increase the odds of merges.
IOW, I'm having a hard time seeing what could be taken away and still have it work.
Quoted 9 lines
Quoted 4 lines
The idea proposed here is this: instead of single pages, make the PCP grab entire pageblocks, split them outside the
zone->lock. That CPU then takes ownership of the block, and all frees route back to that PCP instead of the freeing CPU's local one.This is basically distributed buddy allocators, right? Instead of relying on a single
zone->lock, PCP locks are used. The worst case it can face is that physically contiguous free pages are allocated across all CPUs, so that all CPUs are competing a single PCP lock.
The worst case is one CPU allocating for everybody else in the system, so that all freers route to that PCP.
I've played with microbenchmarks to provoke this, but it looks mostly neutral over baseline, at least at the scale of this machine.
In this scenario, baseline will have the affinity mismatch problem:
the allocating CPU routinely hits zone->lock to refill, and the freeing CPUs routinely hit zone->lock to drain and merge.
In the new scheme, they would hit the pcp->lock instead of the zone->lock. So not necessarily an improvement in lock breaking. BUT because freers refill the allocator's cache, merging is deferred; that's a net reduction of work performed under the contended lock.
Quoted 8 lines
It seems that you have not hit this. So I wonder if what I proposed above might work as a simpler approach. Let me know if I miss anything.
I wonder how this distributed buddy allocators would work if anyone wants to allocate >pageblock free pages, like
alloc_contig_range(). Multiple PCP locks need to be taken one by one. Maybe it is better than taking and droppingzone->lockrepeatedly. Have you benchmarkedalloc_contig_range(), like hugetlb allocation?
I didn't change that aspect.
The PCPs are still the same size, and PCP pages are still skipped by the isolation code.
IOW it's not a purely distributed buddy allocator. It's still just a per-cpu cache of limited size. The only thing I'm doing is provide a mechanism for splitting and pre-merging at the cache level, and setting up affinity/routing rules to increase the chances of success. But the impact on alloc_contig should be the same.
Quoted 17 lines
Quoted 10 lines
This has several benefits:
1. It's right away coarser/fewer allocations transactions under the
zone->lock.1a. Even if no full free blocks are available (memory pressure or
small zone), with splitting available at the PCP level means the PCP can still grab chunks larger than the requested order from thezone->lockfreelists, and dole them out on its own time.Quoted 6 lines
2. The pages free back to where the allocations happen, increasing the odds of reuse and reducing the chances of
zone->lockslowpaths.3. The page buddies come back into one place, allowing upfront merging under the local
pcp->lock. This makes coarser/fewer freeing transactions under thezone->lock.
Quoted 5 lines
I wonder if we could go more radical by moving buddy allocator out of
zone->lockcompletely to PCP lock. If one PCP runs out of free pages, it can steal another PCP's whole pageblock. I probably should do some literature investigation on this. Some research must have been done on this.
This is an interesting idea. Make the zone buddy a pure block economy and remove all buddy code from it. Slowpath allocs and frees would always be in whole blocks.
You'd have to come up with a natural stealing order. If one CPU needs something it doesn't have, which CPUs, and which order, do you look at for stealing.
I think you'd still have to route back frees to the nominal owner of the block, or stealing could scatter pages all over the place and we'd never be able to merge them back up.
I think you'd also need to pull accounting (NR_FREE_PAGES) to the per-cpu level, and inform compaction/isolation to deal with these pages, since the majority default is now distributed.
But the scenario where one CPU needs what another one has is an interesting one. I didn't invent anything new for this for now, but rather rely on how we have been handling this through the zone freelists. But I do think it's a little silly: right now, if a CPU needs something another CPU might have, we ask EVERY CPU in the system to drain their cache into the shared pool - simultaneously - running the full buddy merge algorithm on everything that comes in. The CPU grabs a small handful of these pages, most likely having to split again. All other CPUs are now cache cold on the next request.
Zi Yan
reviewerQuoted 42 lines · Johannes Weiner
Quoted 22 lines · Zi Yan
Quoted 12 lines · Johannes Weiner
this is an RFC for making the page allocator scale better with higher thread counts and larger memory quantities.
In Meta production, we're seeing increasing
zone->lockcontention that was traced back to a few different paths. A prominent one is the userspace allocator, jemalloc. Allocations happen from page faults on all CPUs running the workload. Frees are cached for reuse, but the caches are periodically purged back to the kernel from a handful of purger threads. This breaks affinity between allocations and frees:
Both sides use their own PCPs - one side depletes them, the other one overfills them. Both sides routinely hit thezone->lockedslowpath.Quoted 8 lines
My understanding is that tcmalloc has a similar architecture.
Another contributor to contention is process exits, where large numbers of pages are freed at once. The current PCP can only reduce lock time when pages are reused. Reuse is unlikely because it's an avalanche of free pages on a CPU busy walking page tables. Every time the PCP overflows, the drain acquires the
zone->lockand frees pages one by one, trying to merge buddies together.Quoted 6 lines
IIUC,
zone->lockheld time is mostly spent on free page merging. Have you tried to let PCP do the free page merging before holdingzone->lockand returning free pages to buddy? That is a much smaller change than what you proposed. This method might not work if physically contiguous free pages are allocated by separate CPUs, so that PCP merging cannot be done. But this might be rare?On my 32G system,
pcp->high_minfor zone Normal is 988. That's one block and a half. Thermqueue_smallestpolicy means the next CPU will prefer the remainder of that partial block. So if there is concurrency, every other block is shared. Not exactly uncommon. The effect lessens the larger the machine is, of course.But let's assume it's not an issue. How do you know you can safely merge with a buddy pfn? You need to establish that it's on that same PCP's list. Short of *scanning* the list, it seems something like
PagePCPBuddy()andpage->pcp_cpuis inevitably needed. But of course a per-page cpu field is tough to come by.
Quoted 5 lines
So the block ownership is more natural, and then you might as well use that for affinity routing to increase the odds of merges.
IOW, I'm having a hard time seeing what could be taken away and still have it work.
You are right. I was assuming that pages that can be merged are freed via the same CPU. That rarely happens.
Quoted 17 lines
Quoted 10 lines
Quoted 5 lines
The idea proposed here is this: instead of single pages, make the PCP grab entire pageblocks, split them outside the
zone->lock. That CPU then takes ownership of the block, and all frees route back to that PCP instead of the freeing CPU's local one.This is basically distributed buddy allocators, right? Instead of relying on a single
zone->lock, PCP locks are used. The worst case it can face is that physically contiguous free pages are allocated across all CPUs, so that all CPUs are competing a single PCP lock.The worst case is one CPU allocating for everybody else in the system, so that all freers route to that PCP.
I've played with microbenchmarks to provoke this, but it looks mostly neutral over baseline, at least at the scale of this machine.
Quoted 8 lines
In this scenario, baseline will have the affinity mismatch problem:
the allocating CPU routinely hitszone->lockto refill, and the freeing CPUs routinely hitzone->lockto drain and merge.In the new scheme, they would hit the
pcp->lockinstead of thezone->lock. So not necessarily an improvement in lock breaking. BUT because freers refill the allocator's cache, merging is deferred; that's a net reduction of work performed under the contended lock.
This makes sense to me.
Quoted 12 lines
Quoted 9 lines
It seems that you have not hit this. So I wonder if what I proposed above might work as a simpler approach. Let me know if I miss anything.
I wonder how this distributed buddy allocators would work if anyone wants to allocate >pageblock free pages, like
alloc_contig_range(). Multiple PCP locks need to be taken one by one. Maybe it is better than taking and droppingzone->lockrepeatedly. Have you benchmarkedalloc_contig_range(), like hugetlb allocation?I didn't change that aspect.
Quoted 8 lines
The PCPs are still the same size, and PCP pages are still skipped by the isolation code.
IOW it's not a purely distributed buddy allocator. It's still just a per-cpu cache of limited size. The only thing I'm doing is provide a mechanism for splitting and pre-merging at the cache level, and setting up affinity/routing rules to increase the chances of success. But the impact on
alloc_contigshould be the same.
Got it. Thanks for the explanation.
Quoted 24 lines
Quoted 18 lines
Quoted 11 lines
This has several benefits:
1. It's right away coarser/fewer allocations transactions under the
zone->lock.1a. Even if no full free blocks are available (memory pressure or
small zone), with splitting available at the PCP level means the PCP can still grab chunks larger than the requested order from thezone->lockfreelists, and dole them out on its own time.Quoted 6 lines
2. The pages free back to where the allocations happen, increasing the odds of reuse and reducing the chances of
zone->lockslowpaths.3. The page buddies come back into one place, allowing upfront merging under the local
pcp->lock. This makes coarser/fewer freeing transactions under thezone->lock.Quoted 5 lines
I wonder if we could go more radical by moving buddy allocator out of
zone->lockcompletely to PCP lock. If one PCP runs out of free pages, it can steal another PCP's whole pageblock. I probably should do some literature investigation on this. Some research must have been done on this.
Quoted 7 lines
This is an interesting idea. Make the zone buddy a pure block economy and remove all buddy code from it. Slowpath allocs and frees would always be in whole blocks.
You'd have to come up with a natural stealing order. If one CPU needs something it doesn't have, which CPUs, and which order, do you look at for stealing.
One naive idea is to make zone buddy keep track of PCP free lists for stealing.
Quoted 4 lines
I think you'd still have to route back frees to the nominal owner of the block, or stealing could scatter pages all over the place and we'd never be able to merge them back up.
Basically, we want to keep free pages to be merged as much as possible. Something like free page compaction across all PCPs.
Quoted 5 lines
I think you'd also need to pull accounting (
NR_FREE_PAGES) to the per-cpu level, and inform compaction/isolation to deal with these pages, since the majority default is now distributed.
Quoted 9 lines
But the scenario where one CPU needs what another one has is an interesting one. I didn't invent anything new for this for now, but rather rely on how we have been handling this through the zone freelists. But I do think it's a little silly: right now, if a CPU needs something another CPU might have, we ask EVERY CPU in the system to drain their cache into the shared pool - simultaneously - running the full buddy merge algorithm on everything that comes in. The CPU grabs a small handful of these pages, most likely having to split again. All other CPUs are now cache cold on the next request.
Yes, a better way might be that when a CPU wants something, it should be able to ask the other CPUs to drain the minimal amount of free pages. But I do not have a good idea on how to do that yet.
It sounds to me that your current approach is a good first step towards distributed buddy allocator. I will check the code and think about it more and ask questions later.
Thank you for the explanation.
Best Regards,
Yan, Zi
Quoted 45 lines · Johannes Weiner
Hi,
this is an RFC for making the page allocator scale better with higher thread counts and larger memory quantities.
In Meta production, we're seeing increasing
zone->lockcontention that was traced back to a few different paths. A prominent one is the userspace allocator, jemalloc. Allocations happen from page faults on all CPUs running the workload. Frees are cached for reuse, but the caches are periodically purged back to the kernel from a handful of purger threads. This breaks affinity between allocations and frees:
Both sides use their own PCPs - one side depletes them, the other one overfills them. Both sides routinely hit thezone->lockedslowpath.My understanding is that tcmalloc has a similar architecture.
Another contributor to contention is process exits, where large numbers of pages are freed at once. The current PCP can only reduce lock time when pages are reused. Reuse is unlikely because it's an avalanche of free pages on a CPU busy walking page tables. Every time the PCP overflows, the drain acquires the
zone->lockand frees pages one by one, trying to merge buddies together.The idea proposed here is this: instead of single pages, make the PCP grab entire pageblocks, split them outside the
zone->lock. That CPU then takes ownership of the block, and all frees route back to that PCP instead of the freeing CPU's local one.This has several benefits:
1. It's right away coarser/fewer allocations transactions under the
zone->lock.1a. Even if no full free blocks are available (memory pressure or
small zone), with splitting available at the PCP level means the PCP can still grab chunks larger than the requested order from thezone->lockfreelists, and dole them out on its own time.2. The pages free back to where the allocations happen, increasing the odds of reuse and reducing the chances of
zone->lockslowpaths.3. The page buddies come back into one place, allowing upfront merging under the local
pcp->lock. This makes coarser/fewer freeing transactions under thezone->lock.
Quoted 7 lines
The big concern is fragmentation. Movable allocations tend to be a mix of short-lived anon and long-lived file cache pages. By the time the PCP needs to drain due to thresholds or pressure, the blocks might not be fully re-assembled yet. To prevent gobbling up and fragmenting ever more blocks, partial blocks are remembered on drain and their pages queued last on the zone freelist. When a PCP refills, it first tries to recover any such fragment blocks.
Hi Johannes,
I have been working on anti-fragmentation algorithms in the buddy. After thinking a lot I converged onto a "per-cpu, per-pageblock" buddy allocator of sorts. Overall I think we can kill two birds with one stone - performance and external fragmentation.
I will list my ideations here (perhaps something clicks to anyone) in no particular order, and then show how I eventually reach a design similar to yours:
Suppose we are trying for order-2 allocs. An order-0 alloc request comes on a cpu, the pcpu list is empty, the zone freelist for order-0 is empty. We end up breaking an order-1 or higher block, even when other cpus may have order-0 free pages.
I figured that just by disabling pcp lists, we can delay triggering compaction (got 2% more order-2 THP allocations without triggering compaction/reclaim) by not hiding order-0 free pages from order-0 alloc requests. So, a "PCP stealing" algorithm may be needed.
I then thought of a "sorting" algorithm on the freelists: either sort by PFN (causing allocations to cluster on the lower half of memory space) or by fragmentation score (per pageblock). Any such sorting algorithm requires two things:
1. When to trigger the algorithm - can't be wasting time doing sorting on every alloc and free
2. What portion of the list to sort: sorting should not push a block recently freed to the back of the list because it is cache hot, so let us take a major portion of the list from the tail and sort it
3. The sorting algorithm should be cheap: bucket sort by sqrt(RAM) number of buckets or some other number if sorting by PFN, or bucket sort by frag score, buckets being [0, 511]).
All of this helps, but the more fundamental problem is that for a block of contiguous memory, their lifetimes are *not* tied together.
Consider VMA1 of Process P1 and VMA2 of Process P2, being the only allocators (by the process faulting in) and contending on the zone lock. Usually a process will start faulting into the VMA contiguously. So, if we have four pages:
0 0 0 0
and both processes are faulting in, then the configuration most probably would look like
1 2 1 2
meaning that VMA1 will have pages 0 and 2, VMA2 will have pages 1 and 3, because dropping the zone lock will cause the other one to enter, and so on. Had this not been the case, we could have got "1 1 2 2" which is clearly better.
(Although we have pcp lists which consume from zone lists in batches, the logic above quickly starts holding true because the lifetime of each order list on the pcp is not tied together, so eventually the pcp is filled with non contiguous memory).
I then researched around and found that reclaim is one of the biggest factors of fragmentation, but again the fundamental problem is lifetime. I found out an attempt to do reclaim in blocks:
https://lore.kernel.org/all/exportbomb.1164300519@pinky/
which got reverted: active and inactive pages are clustered together.
So then I thought, how do I tie the lifetime together? Probably have a task_struct steal a block of memory? That sounds like something very complex to get right. Instead, I can use a CPU being an analogue to the process.
So now the zone just becomes a provider of blocks.
A process when faulting in, assuming doesn't get bounced around cpus like anything, can now get allocations physically close to each other.
The crux is that doing allocations from a global state like the zone means that just as you drop the lock you let the other guy enter, which breaks contiguity. Having contiguity per cpu means the same process can use it up.
I would assume implementing a pure per-cpu based allocator could get you blazing fast performance, with all of the above extfrag benefits, at the cost of figuring out an algorithm for cpus to steal from other cpus.
I assume some bitmask tricks could work wherein each cpu advertises free blocks to the other.
I think there are existing cpu-stealing concepts in scheduler etc which we can borrow, and perhaps I should also take a look at slab once again for per-cpu ideas (although they had a radical sheaves change which I am not familiar with).
I will play around with your patchset and see if I can improve it!
Quoted 28 lines
On small or pressured machines, the PCP degrades to its previous behavior. If a whole block doesn't fit the
pcp->highlimit, or a whole block isn't available, the refill grabs smaller chunks that aren't marked for ownership. The free side will use the local PCP as before.I still need to run broader benchmarks, but I've been consistently seeing a 3-4% reduction in %sys time for simple kernel builds on my 32-way, 32G RAM test machine.
A synthetic test on the same machine that allocates on many CPUs and frees on just a few sees a consistent 1% increase in throughput.
I would expect those numbers to increase with higher concurrency and larger memory volumes, but verifying that is TBD.
Sending an RFC to get an early gauge on direction.
Based on
0257f64bdac7fdca30fa3cae0df8b9ecbec7733a.include/linux/mmzone.h | 38 ++- include/linux/page-flags.h | 9 + mm/debug.c | 1 + mm/internal.h | 17 + mm/mm_init.c | 25 +- mm/page_alloc.c | 784 +++++++++++++++++++++++++++++++------------ mm/sparse.c | 3 +- 7 files changed, 622 insertions(+), 255 deletions(-)