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

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

On 12/10/26 1:55 pm, Pedro Falcato wrote:
> 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:

Hi Pedro,

Right, David H. had sent me that paper : )


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

Yeah I had skimmed over it and did not understand the cache benefit claim; the
main benefit seems to be the lockless design.

The critical section under zone->lock is extremely cache efficient right now
as, when it pops a page from the head, it touches 1) the list_head sentinel
of the list which is hot, 2) the page to be alloced whose fields are going
to get touched anyway, 3) the next page's prev pointer, so warming up this
page for the next allocation.


Right now we bounce on different cachelines once the lower order freelists get
empty. The current design is to first index by order, and then by migratetype.

I vibe coded to do the reverse and it does improve cache hits in general. But,
it has a collision with the free_area->nr_free which maintains total free blocks
per order (hence, summed across migratetypes). I'll see if I can send this
patch separately.

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

Indeed.

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

Exactly which I wrote in the other email : ) A cpu is the natural approximation
of tying lifetime together.


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