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

[Pedro Falcato]

Hi,

On Sun, Oct 11, 2026 at 09:54:11PM +0000, Dev Jain wrote:
> (I am not posting code yet since it is in experimental stage.)
> 
> 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
> 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.

So, I've been looking at LLFree (one of those novel page allocators with
no buddy and just a bitmap) lately. A few thoughts:

LLFree basically divides memory into 2MB pageblocks (with a free pages
counter), and then later organizes these pageblocks into 64MB "tree roots".
These tree roots are then borrowed by each CPU and made local (pretty much
like old SLUB used to do). This localizes most of your allocations and
pretty much avoids conflicts/cross-talk across CPUs.

Yes, there is a bitmap. I don't think it's required, and it might actually
be misguided. The paper itself has other side-goals. One of them is easy
persistence in persistent DRAM; we don't need that. Another one is minimizing
the cache footprint of the page allocator; this is misguided (IMO) because
allocating pages has the side effect of you actually needing to initialize
the struct pages after the fact; whether the allocator core hangs state off
the struct page or not is not important, and in fact using struct page there
might provide cache benefits.

The bitmap does not work well for random order allocations.
The paper itself was written on Linux 6.0, which (probably) relied quite a
lot less on things like mTHP (and random-order file pages) than we do now.

In any case, this paper doesn't necessarily address your fragmentation
problems, but it does attempt to address fragmentation (and SMP performance)
through borrowing these pageblocks. I would not be surprised if it had
a sizeable (positive) impact in fragmentation. I firmly believe that a
direction similar to the buddy allocator, but with more buddy work pushed
to the pcpu side (like Johannes's pcp buddy allocator series) is there right
approach and could have a meaningful effect.

Of course, it doesn't solve other problems like lifetime mixing in allocations,
and things like slab migration are insanely complicated to pull off.
 

-- 
Pedro