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

["Zi Yan" <ziy@nvidia.com>]

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

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

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

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.

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.

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/


-- 
Best Regards,
Yan, Zi