Skip to contentSkip to conversation

Anti-fragmenting ordered buddy allocator

RFC Dev Jain 4 participants 7 messages Oct 11 – Oct 12 Memory management

lore
Share & tools
lore

Dev Jain

author
#0 lore raw

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

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.

PROBLEM
-------

The number of buckets is inversely proportional to allocator performance. The critical section under the zone->lock is extremely fast.

The overheads are the following:

1) Alloc: What is the first free bucket which has the required order? We don't want to naively scan across the buckets.

Then, the more surprising one, which becomes more visible as the number of buckets increase:

2) Free: When we do pfn->bucket lookup (which needs to happen in a cache-effective manner) and free into that bucket, if this is not the "active" bucket we were allocating from, then we are going to miss the cache. The inactive bucket list_head is cold, and the page at its head is also cold. We are going to perform some cold operations to insert it into its (bucket, order) freelist.

At least on my system, increasing the size of struct zone did not contribute to overhead (for free areas <= 64). I may not have increased it enough.

DESIGN COMMONALITY
------------------

All designs aim to prefer low addresses for movable allocations, and high addresses for reclaimable/unmovable allocations. The "SOLUTION COMMONALITY" is: keep things tight in cache. We pay cycles when the bucket we were allocing from starts becoming empty, and we need to find the next bucket. The crux is to amortize that cost somehow.

DESIGN 1
--------
We divide the zone into 4 buckets of equal length. Then, allocation first chooses the migratetype, iterates the available buckets from left to right for movable allocations, and right to left for unmovable/reclaimable. When freeing, we do a pfn->bucket index lookup, and free into that (migratetype, bucket, order) freelist.
Note that we change the indexing to the above: currently the index is (order, migratetype), making order list heads for the same migratetype distant. This is problematic if we want to scan order lists for the same buddy unit.

We may be needlessly scanning the lists when the bucket is empty. So, we can make a bucket "active" and allocate from the active bucket, till we cannot. Then we iterate from the start and make a bucket active.

This algorithm does not scale well with the number of buckets, but is the simplest.

DESIGN 2
--------

The aim now is to increase the number of buckets. Suppose the active bucket is F, wherein active means, this is the bucket we will keep allocing from until we cannot.

ALLOC TIME: We request an order-x block, search the order freelists on this bucket, and can't find anything. Now, we need to find the first bucket with an order-y freelist nonempty, y >= x.

We can use a "bucket-local" bitmap: for the active bucket, maintain a local bitmap, kept on the cacheline of the order-0 list_head. On every pop and free from the active bucket, we will update this bitmap to indicate whether order-x list is nonempty.

Once this bucket becomes nonactive, publish this local bitmap into the zone-scoped bitmap, and use that bitmap to quickly find the first bucket which has a block >= order-x.

FREE TIME: if we are freeing a PFN belonging to a non-active bucket ... we DO NOT need to free to its bucket yet! Free this into a lockless linked list kept in the zone->lock cacheline (just like trylock_free_pages). The crux is that we do not need to make these blocks visible to the buddy yet either for allocation or buddy coalescing, since allocation from those buckets is not going to happen until the active bucket is in use.

Once the active bucket can no longer satisfy the request, we drain this list (or, when a threshold is crossed, to prevent unbounded work under spinlock).

So we have amortized cache misses across non-active frees.

The problem starts when this bucket jumping becomes very frequent. It is a sign we are under memory pressure. We should then call into the slowpath and free enough pages. But, we really shouldn't be using huge number of buckets under memory pressure, since there is no point of "anti fragmentation" now. The bucketed allocator helps us to delay compaction and reclaim. So we need a way to switch.

#1 lore raw
Quoted 5 lines · Dev Jain

Apart from dividing the freelists between migratetypes, little attempt
has been made to change the algorithm

Could I convince you to take a look at these patches?

https://lore.kernel.org/all/[email protected]/

My current plan is to first improve the fragmentation at pageblock level, and then add some slow path code on top of that which can steer the allocations by physical address range, to preserve the potential for gigablock page lalocation.

Signature · 1 line
All Rights Reversed.
author
#2 lore raw
Quoted 9 lines · Rik van Riel
Quoted 5 lines · Dev Jain

Apart from dividing the freelists between migratetypes, little attempt
has been made to change the algorithm

Could I convince you to take a look at these patches?

Thanks for replying Rik.

Quoted 2 lines

https://lore.kernel.org/all/[email protected]/

Indeed, I had seen these patches and from a cursory look I liked them. I will eventually try to get into page-alloc review.

Quoted 8 lines

My current plan is to first improve the fragmentation at pageblock level, and then add some slow path code on top of that which can steer the allocations by physical address range, to preserve the potential for gigablock page lalocation.

#3 lore raw
In reply to Dev Jain
Quoted 1 line · Dev Jain

(I am not posting code yet since it is in experimental stage.)

Thank you for posting the idea.

Quoted 15 lines

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.

Quoted 7 lines

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.

Quoted 19 lines

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.

Quoted 7 lines

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/[email protected]/

Signature · 2 lines
Best Regards,
Yan, Zi
author
#4 lore raw
Quoted 4 lines · Zi Yan
Quoted 1 line · Dev Jain

(I am not posting code yet since it is in experimental stage.)

Thank you for posting the idea.

Thanks for replying Zi.

Quoted 18 lines
Quoted 18 lines

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

Quoted 8 lines
Quoted 4 lines

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.

Quoted 28 lines
Quoted 20 lines

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.

Quoted 7 lines

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.

Quoted 5 lines

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.

Quoted 9 lines

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.

Quoted 7 lines

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

Quoted 6 lines

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.

Quoted 10 lines

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/[email protected]/

#5 lore raw
In reply to Dev Jain

Hi,

Quoted 27 lines · Dev Jain

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

Quoted 3 lines

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.

Signature · 1 line
Pedro
author
#6 lore raw
Quoted 30 lines · Pedro Falcato

Hi,

Quoted 27 lines · Dev Jain

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

Quoted 6 lines
Quoted 3 lines

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 : )

Quoted 7 lines

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.

Quoted 8 lines

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.

Quoted 4 lines

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.

Quoted 8 lines

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.

Quoted 5 lines

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