Re: [RFC NO CODE] [DISCUSSION] Anti-fragmenting ordered buddy allocator

[Dev Jain <dev.jain@arm.com>]

On 12/10/26 4:34 am, Zi Yan wrote:
> On Sun Oct 11, 2026 at 5:54 PM EDT, Dev Jain wrote:
>> (I am not posting code yet since it is in experimental stage.)
> 
> Thank you for posting the idea.

Thanks for replying Zi.


>>
>> TL;DR
>> -------
>>
>> I am proposing "ordered/bucketed buddy allocator": we divide the buddy
>> freelists into buckets, and prefer lower buckets for allocation.
>> This reduces external fragmentation (and, further reduces it when we
>> reverse the ordering for unmovable and reclaimable allocations) at the
>> cost of regressing the alloc and free paths, which depends on how many
>> buckets you partition into. I think we can partition into 4 buckets and
>> do some tricks to remove any regression.
>>
>> Design 1 is the simplest and the most upstream-friendly method in terms of
>> allocator speed. Design 2 tries to scale better with the number of buckets.
>>
>> INTRODUCTION
>> -------------
>>
>> Apart from dividing the freelists between migratetypes, little attempt
>> has been made to change the algorithm of the buddy itself to reduce
>> external fragmentation proactively (termed as "anti-fragmentation" in
>> academia). Linux has defragmentation (compaction). The analysis below
> 
> Like Rik suggested, it is better to focus on one thing at a time. I
> think improving anti-fragmentation at pageblock level is high priority
> at the moment.

The premise I started with was to improve chance of mTHP allocations; I would
like to point out the benefit of ordering.

I was first looking at the problem from the perspective of finding already
populated blocks to allocate, within the same migratetype (an implication
of trying to do that was, reverse the order for non-movable, which is not
the premise I started with).

If we bias allocations towards the left, we give more chance for pages at
the right to get freed and make contiguous free blocks. So maintaining an
ordering is a good approximation for biasing w.r.t fragmentation score.
This delays compaction triggers, and even if compaction is triggered it may
exploit some sort of ordering - it knows that sparse blocks are to the right
with good probability.

Essentially we are trying to do a bucket-sort here.

Think of the allocation stream as a *probability distribution* -
I am trying to skew that to one direction.


> 
>> is *not* to claim that compaction does a bad job; I just took up the
>> challenge of anti-fragmentation (because I like to torture myself) and
>> kept digging the rabbit hole.
>>
>> There have been academic papers about replacing the buddy with bitmaps -
>> I did not want a hard NAK from upstream at any attempt to do that, so
>> I preserved the buddy freelists.
>>
>> IDEA
>> ----
>>
>> There is a correlation between allocating from one side of memory, and
>> reducing external fragmentation. Biasing on one side implies the
>> probability we fragment already fragmented sections is high. This may also
>> enable smarter compaction by directing the free-page scanner toward
>> higher-address regions. This also circumvents the discussion around
>> a "fragmentation score" which is dependent on the size of the
>> block we are considering.
>>
>> The idea itself quite obviously improves clustering of allocations: I
>> observe reductions in 'compact_stall' and 'anon_fault_fallback', and some
>> large improvements when the number of buckets is high (like, compact_stall
>> going down from 4000 to 5 with almost no hit in execution time for a kernel
>> compilation). The obvious downside being slowing down the allocator (which
>> needs to be tested more widely). The content below is mainly on how
>> to minimize that.
> 
> I am not sure how your bucket idea is better than the existing pageblock
> design, because the biggest issue in anti-fragmentation is unmovable
> pages spreading across the entire physical memory space to prevent high
> order page allocation and I do not see how your idea could contaminate
> unmovable pages.

To make it clearer, I have observed improvement even without clustering
movable and non-movable to opposite ends, and simply clustering *all* allocations
to the left.

Note that all of the pageblock claim/steal algorithm of the buddy
remains the same - an unmovable allocation will still try to take the
largest order block free in movable buddy lists and try to claim it
instead of stealing, so the existing algorithm works. So we first
cluster by migratetype, then cluster by pfn bucket.




> 
> Unmovable pages can sometimes take majority of the memory of a system,
> leaving the entire memory space fragmented, for example a burst of
> dentry allocation. Roman wrote a small userspace app to do this [1], and
> you can give it a try. Afterwards, some of these unmovable pages might
> be freed after their use, but there is no guarantee that the freed
> unmovable pages can create contiguous free pages. Unless we do unmovable
> page lifetime prediction and group unmovable pages with similar lifetime
> like Yu Zhao proposed[2].

Thanks for mentioning [1] and [2].

You are right regarding [2]: I had also concluded that the most correct
way of looking at external fragmentation is lifetime prediction. I had
written a reply to Johannes' PCPbuddy patchset (my intuition says it
will also improve on fragmentation):

So basically we need to give contiguous pages to an "allocator context". The
allocator context examples are a file filling its pagecache, a slab filling
slab pages, a VMA faulting in memory, etc.

Currently a file does readahead to ask for contiguous memory which is good,
but it would have been great if we could reserve a pageblock worth of memory
and keep fragmenting it for the same file, tying allocations together.

Perhaps we can think for the file case specifically since pagecache has
been observed as a huge bottleneck for fragmentation: after reclaim,
the pages freed are scattered. And, they may immediately be taken again
by pagecache allocations.

(One way is, at least for filesystems not supporting large folios, we
can still do high-order (non-compound) allocations, the order
dictated by the write()/read() syscall, or the readahead ra->order.)

Then, the next programmatic approximation (losing accuracy) of
the "allocator context" is a task_struct. A task_struct reserves
a pageblock and allocates from it.

If you think about it, there is a correlation between allocator-context
and task_struct, since at a time the task is doing similar things in
a time frame, be it userspace allocation or even kernel allocations
triggered from userspace.

Then the next and more natural approximation (losing more accuracy)
is of a cpu. The cpu reserves a pageblock, and we hope that the
cpu is continuously used by the same allocator context for enough
time before migration.


> 
> IMHO, pageblock is already acting like bucket, limiting allocation
> range. I see each pageblock a small bucket for allocations and it is
> better than growing allocation from one end to the other end, because
> the latter means unmovable allocation can keep pushing the boundary and
> the boundary might be able to move back if there is a long live
> unmovable page sitting at the boundary.

I think what you are trying to say is that a long-term unmovable allocation
at the boundary will pin the boundary. But that is fine. That boundary is
not a hard limit (I am not claiming a bucket for a certain type of allocation),
the point of bucketing is to skew the probability distribution
(allocation distribution) to one side.

Codewise, the loop looks like

migratetype = gfp_migratetype(gfp);
choose zone->free_area[migratetype]

In that, choose the least bucket:
zone->free_area[migratetype][bucket]

Which has list_head[NR_PAGE_ORDERS].
> 
> At the moment, anti-fragmentation is only preventing mixing
> movable and unmovable pages in a pageblock. Rik's series[3] is doing
> additional work to keep unmovable page allocation within a unmovable
> pageblock, further reducing fragmentation. That is probably what we want
> to get in first.

Indeed, agreed that the bigger problem is pageblock mixing.


> 
> Maybe you can compare your idea with Rik's series and tell us the pros
> and cons of both. :)
> 
> 
> [1] https://github.com/rgushchin/fragm
> [2] https://lpc.events/event/18/contributions/1779/
> [3] https://lore.kernel.org/all/20261007021250.1665929-1-riel@surriel.com/
> 
>