(Checking the algorithm here)
On Mon, Jun 01, 2026 at 10:11:24AM +0200, David Hildenbrand (Arm) wrote:
> On 5/22/26 17:00, Nico Pache wrote:
>
> Finally time for the core piece :)
>
> > Enable khugepaged to collapse to mTHP orders. This patch implements the
> > main scanning logic using a bitmap to track occupied pages and a stack
> > structure that allows us to find optimal collapse sizes.
> >
> > Previous to this patch, PMD collapse had 3 main phases, a light weight
> > scanning phase (mmap_read_lock) that determines a potential PMD
> > collapse, an alloc phase (mmap unlocked), then finally heavier collapse
> > phase (mmap_write_lock).
> >
> > To enabled mTHP collapse we make the following changes:
> >
> > During PMD scan phase, track occupied pages in a bitmap. When mTHP
> > orders are enabled, we remove the restriction of max_ptes_none during the
> > scan phase to avoid missing potential mTHP collapse candidates. Once we
> > have scanned the full PMD range and updated the bitmap to track occupied
> > pages, we use the bitmap to find the optimal mTHP size.
> >
> > Implement collapse_scan_bitmap() to perform binary recursion on the bitmap
> > and determine the best eligible order for the collapse. A stack structure
> > is used instead of traditional recursion to manage the search. This also
> > prevents a traditional recursive approach when the kernel stack struct is
> > limited. The algorithm recursively splits the bitmap into smaller chunks to
> > find the highest order mTHPs that satisfy the collapse criteria. We start
> > by attempting the PMD order, then moved on the consecutively lower orders
> > (mTHP collapse). The stack maintains a pair of variables (offset, order),
This is inaccurate, it's only consecutively smaller until you hit smallest then
it starts bumping around 2 -> 3 -> 2 -> 3 -> 2 -> .. -> 4 -> 3 -> 2 -> 3 -> 2
-> 4 -> etc.
More like consecutively smaller, then always trying for the smallest possible
fit?
Would be good to describe why we do this, presumably to get a best _fit_?
> > indicating the number of PTEs from the start of the PMD, and the order of
> > the potential collapse candidate.
> >
> > The algorithm for consuming the bitmap works as such:
> > 1) push (0, HPAGE_PMD_ORDER) onto the stack
> > 2) pop the stack
> > 3) check if the number of set bits in that (offset,order) pair
> > statisfy the max_ptes_none threshold for that order
> > 4) if yes, attempt collapse
> > 5) if no (or collapse fails), push two new stack items representing
> > the left and right halves of the current bitmap range, at the
> > next lower order
I notice the ordering is wrong here, you actualy push the mid_offset first then
the offset (e.g. 'right', then 'left'):
collapse_mthp_stack_push(cc, &stack_size, mid_offset,
next_order);
collapse_mthp_stack_push(cc, &stack_size, offset,
next_order);
So that way you are popping the 'left' first then the 'right'.
So seems you'll get:
stack={0, 9}
Pop (0, order=9):
|----------------------------------------|
|########################################|
|----------------------------------------|
stack={256, 8}, {0, 8}
Pop (0, order=8):
|--------------------|-------------------|
|####################| |
|--------------------|-------------------|
stack={256, 8}, {128, 7}, {0, 7}
Pop (0, order=7):
|----------|-----------------------------|
|##########| |
|----------|-----------------------------|
stack={256, 8}, {128, 7}, {64, 6}, {0, 6}
Pop (0, order=6):
|----|-----------------------------------|
|####| |
|----|-----------------------------------|
...
stack={256, 8}, ..., { 8, 3 }, {0, 2}
Pop (0, order=2):
|-|--------------------------------------|
|#| |
|-|--------------------------------------|
Then finally :) we get the offsets :)
stack={256, 8}, ..., {8, 3}, {4, 2}
Pop (4, order=2):
|-|-|------------------------------------|
| |#| |
|-|-|------------------------------------|
stack={256, 8}, ..., { 12, 2 }, {8, 3}
Pop (8, order=3):
|---|--|---------------------------------|
| |##| |
|---|--|---------------------------------|
stack={256, 8}, ..., { 12, 2 }, {12, 2}, {8, 2}
Pop (8, order=2):
|---|-|----------------------------------|
| |#| |
|---|-|----------------------------------|
etc.
It seems to me that you're going to keep iterating down until you match an mTHP
when a larger mTHP could have been had?
So we're going:
order 9 -> 8 -> 7 -> 6 -> ... -> 2 -> 3 -> 2 -> 4 -> 3 -> 2
I guess the point is to avoid only getting the largest possible
I guess if we did try to get the largest then we'd only get 2 of the largest
possible then exhaust the whole PMD, should a PMD-sized entry not be possble.
> > 6) repeat at step (2) until stack is empty.
> >
> > Below is a diagram representing the algorithm and stack items:
> >
> > offset mid_offset
> > | |
> > | |
> > v v
> > ____________________________________
> > | PTE Page Table |
> > --------------------------------------
> > <-------><------->
> > order-1 order-1
>
>
> Reading this, it is unclear why exactly do we need the stack.
>
> Why can't you work with offset + cur_order?
>
> Initially,
>
> offset = 0;
> cur_order = HPAGE_PMD_ORDER;
>
> If collapse succeeded, advance to next range.
> If collapse failed, try next smaller order, keeping offset unchanged.
>
> if (failed && cur_order > KHUGEPAGED_MIN_MTHP_ORDER) {
> /* Try next smaller order. */
> cur_order = cur_order - 1;
OK this matches the stack for the 0 offset entries...
> } else {
> /* Skip to next chunk. */
> offset += 1 << cur_order;
> cur_order = max_order_from_offset(offset);
Then 1 << 2 -> 4 so go to offset=4.
max_order_from_offset(4) = 2. so (4, offset=2) same as above.
Then we'd loop back here and go to offset = 8, and max_order_from_offset(8) = 3
And, yeah this seems equivalent.
> }
>
> Of course, handling disabled orders. max_order_from_offset() is rather trivial
> (natural buddy order, capped at HPAGE_PMD_ORDER).
Something like?
static unsigned long max_order_from_offset(unsigned long offset)
{
if (!offset)
return HPAGE_PMD_ORDER;
return ilog2(offset);
}
>
> What's the benefit of the stack?
Yeah it seems equivalent. Good idea!
Thanks, Lorenzo
