Re: [RFC 08/11] khugepaged: introduce khugepaged_scan_bitmap for mTHP support

Dev Jain
2025-01-12T16:41:32Z

On 12/01/25 8:43 pm, Dev Jain wrote:
>
>
> On 09/01/25 5:01 am, Nico Pache wrote:
>> khugepaged scans PMD ranges for potential collapse to a hugepage. To add
>> mTHP support we use this scan to instead record chunks of fully utilized
>> sections of the PMD.
>>
>> create a bitmap to represent a PMD in order MTHP_MIN_ORDER chunks.
>> by default we will set this to order 3. The reasoning is that for 4K 512
>> PMD size this results in a 64 bit bitmap which has some optimizations.
>> For other arches like ARM64 64K, we can set a larger order if needed.
>>
>> khugepaged_scan_bitmap uses a stack struct to recursively scan a bitmap
>> that represents chunks of fully utilized regions. We can then determine
>> what mTHP size fits best and in the following patch, we set this bitmap
>> while scanning the PMD.
>>
>> max_ptes_none is used as a scale to determine how "full" an order must
>> be before being considered for collapse.
>>
>> Signed-off-by: Nico Pache <npache@redhat.com>
>
> Here is my objective and subjective analysis.
>
> --------------------- Mathematical Analysis ----------------------------
>
> First off, in my series, I am missing one thing: When I fail to collapse
> a range as a result of exhausting all orders, I should jump to the next
> range starting with the alignment of order at which I just failed (i.e,
> the minimum allowable order). Currently I am exiting which is wasteful.
> This should be easy to extend.
>
> Let's call Nico Pache's method NP, and Dev Jain's method DJ.
>
> The only difference between NP and DJ is the remembrance of the state of
> the PTEs (I have already reverted to using write lock for my v2, see
> this reply: https://lore.kernel.org/all/71a2f471-3082-4ca2-
> ac48-2f664977282f@arm.com/). NP saves empty and filled PTEs in a bitmap,
> and then uses the optimized (let us assume them to be constant time
> operations, hopefully?) bitmap APIs, like bitmap_shift_right(), and
> bitmap_weight(). The latter is what determines whether for a particular
> order, the range has enough filled PTEs to justify calling
> collapse_huge_page(). DJ does this naively with a brute force iteration.
> Now, the edge NP has over DJ is just before calling
> collapse_huge_page(). Post calling that, everything remains the same;
> assuming that both DJ and NP derive the same collapsed ranges, then,
> collapse_huge_page() succeeds in NP if and only if it succeeds in DJ. NP
> knows quickly, when and when not to call collapse_huge_page().
>
> So the question is, how many iterations of PTE scans does NP save over
> DJ? We prove a stronger result:
>
> Let the PTE table consist of 2^x pte entries, where x >= 2 belongs to
> the set of natural numbers (x >= 2 because anon collapse is not
> supported for x < 2). Let f(x) = #iterations performed by DJ in the
> worst case. The worst case is, all orders are enabled, and we have some
> distribution of the PTEs.
>
> Lemma: f(x) <= 2^x * (x-1).
>
> Proof: We perform weak mathematical induction on x. Assume zero-
> indexing, and assume the worst case that all orders are enabled.
>
> Base case: Let x = 4. We have 16 entries. NP does 16 iterations. In the
> worst case, this what DJ may do: it will iterate all 16, and not
> collapse. Then it will iterate from 0-7 pte entries, and not collapse.
> Then, it will iterate from 0-3, and may or may not collapse. Here is the
> worst case (When I write l-r below, I mean the range l-r, both inclusive):
>
> 0-15 fail -> 0-7 fail -> 0-3 fail/success -> 4-7 fail/success -> 8-15
> fail -> 8-11 fail/success -> 12-15 fail/success
>
> #iterations = 16+8+4+4+8+4+4 = 48 = 2^4 * (4-1).
> Convince yourself that f(2) == 4 and f(3) <= 16.
>
> Inductive hypothesis: Assume the lemma is true for some x > 4.
>
> We need to prove for x+1. Let X = 2^(x+1) - 1, and Y = 2^x - 1.
> Let DJ start scanning from 0. If 0-X is success, we are done. So, assume
> 0-X fails. Now, DJ looks at 0-Y. Note that, for any x s.t 0 <= x <= X,
> if DJ starts scanning from x, there is no way it will cross the scan
> into the next half, i.e Y+1-X, since the scan length from x will be
> atmost the highest power-of-two alignment of x. Given this, we scan 0-Y
> completely, and then start from Y+1. Having established the above
> argument, we can use the inductive hypothesis on 0-Y and Y+1-X to derive
> that f(x) <= 2^(x+1) + 2f(x) <= 2^(x+1) + 2(2^x * (x-1)) = 2^(x+1) +

Typo: f(x+1) <= 2^(x+1) + 2f(x).

> 2^(x+1) * (x-1) = 2^(x+1) * (x). Q.E.D
> (You can simulate the proof for x=9; what I mean to say is, we can
> divide 0-511 into 0-255 and 256-511).
>
> So, for our case, NP performs 512 iterations, and DJ performs in the
> worst case, 512 * 8 = 4096 iterations. Hmm...
>
> ----------------------- Subjective Analysis --------------------------
>
> [1] The worst case is, well, the worst case; the practical case on arm64
> machines is, only 2048k and 64k is enabled. So, NP performs 512
> iterations, and DJ performs 512 + 16 * (number of 64K chunks) = 512 +
> 512 = 1024 iterations. That is not much difference.
>
> [2] Both implementations have the creep problem described here:
> https://lore.kernel.org/all/20241216165105.56185-13-dev.jain@arm.com/
>
> [3] The bitmaps are being created only for pte_none case, whereas we
> also have the shared and the swap case. In fact, for the none case, if
> we have PMD-order enabled, we will almost surely collapse to PMD size,
> given that the common case is khugepaged_max_ptes_none = 511: if we have
> one PTE filled, we will call collapse_huge_page(), and both DJ and NP
> will perform 512 iterations. Therefore, the bitmaps also need to be
> extended to the shared and the swap case so as to get any potential
> benefit from the idea in a practical scenario.
>
> [4] NP does not handle scanning VMAs of size less than PMD. Since NP
> introduces a single entry point of khugepaged_collapse_single_pmd(), I
> am not sure how difficult it will be to extend the implementation, and
> given that, MTHP_BITMAP_SIZE is a compile time constant. I have extended
> this in my v2 and it works.
>
> [5] In NP, for a bit to be set, the chunk completely needs to be filled/
> shared/swapped out. This completely changes the meaning of the sysfs
> parameters max_ptes_*. It also makes it very hard to debug since it may
> happen that, distribution D1 has more PTEs filled but less bits in the
> bitmap set than distribution D2. DJ also changes the meaning of the
> parameters due to scaling errors, but that is only an off-by-one error,
> therefore, the behaviour is easier to predict.
>
> [6] In NP, we have: remember the state of the PTEs ->
> alloc_charge_folio() -> read_lock(), unlock() -> mmap_write_lock() ->
> anon_vma_lock_write() -> TLB flush for PMD. There is a significant time
> difference here, and the remembered PTEs may be vastly different from
> what we have now. Obviously I cannot pinpoint an exact number as to how
> bad this is or not for the accuracy of khugepaged. For DJ, since a
> particular PTE may come into the scan range multiple times, DJ gives the
> range a chance if the distribution changed recently.
>
> [7] The last time I tried to save on #iterations of PTE entries, this
> happened:
>
> https://lore.kernel.org/all/ZugxqJ-CjEi5lEW_@casper.infradead.org/
>
> Matthew Wilcox pointed out a potential regression in a patch which was
> an "obvious optimization" to me on paper; I tested and it turned out he
> was correct:
>
> https://lore.kernel.org/all/8700274f-b521-444e-8d17-c06039a1376c@arm.com/
>
> We could argue whether it is worth to have the bitmap memory
> initialization, copying, weight checking, and recursion overhead.
>
> This is the most I can come up with by analyzing from a third person
> perspective :)
>
>