Re: [PATCH mm-unstable v18 11/14] mm/khugepaged: Introduce mTHP collapse support

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

quoted

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

quoted

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.

quoted

    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