From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 863CD20DF4 for ; Sun, 12 Jan 2025 16:41:29 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=217.140.110.172 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736700092; cv=none; b=igEcJoEoZe2ZoTJOE8MCD3sS0fq0DT2+JAXRpmrYnORabFAqWUrO7FGFjzr+HXZig1NXXZdzIelViZnRmDInUpXtDmGdSPmYREGbWJ55D0PSyvq9NDhHCtto7grpqT9IrJq6FuOxLyjgj125JU4CGtnDGt5g50PVRBxulkM9xtM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736700092; c=relaxed/simple; bh=iEb/846Vju/sX7f0zim+w+X53GnusgH44mdc4TWK9QE=; h=Message-ID:Date:MIME-Version:Subject:From:To:Cc:References: In-Reply-To:Content-Type; b=vAUx9asoDSv49rpnfONzF+67kac8CAVstdAcntiN7pfUFe/BwSrew52XL9kYauo/t5U1+TiplsIi1FPX3820fQ5LFLcX3FZt1QJt/WxF/TrSHKmuwFZ82npAbqnM30Xo1Idj+3xsmwfJ6ncb81RpZaUxyLNomoZHR1CXr8cHFUY= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com; spf=pass smtp.mailfrom=arm.com; arc=none smtp.client-ip=217.140.110.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=arm.com Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id CC0D5106F; Sun, 12 Jan 2025 08:41:56 -0800 (PST) Received: from [10.163.85.40] (unknown [10.163.85.40]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 52F113F71E; Sun, 12 Jan 2025 08:41:16 -0800 (PST) Message-ID: <5cc41116-d5e7-4130-bb71-611f61fd8092@arm.com> Date: Sun, 12 Jan 2025 22:11:13 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [RFC 08/11] khugepaged: introduce khugepaged_scan_bitmap for mTHP support From: Dev Jain To: Nico Pache , linux-kernel@vger.kernel.org, linux-mm@kvack.org Cc: ryan.roberts@arm.com, anshuman.khandual@arm.com, catalin.marinas@arm.com, cl@gentwo.org, vbabka@suse.cz, mhocko@suse.com, apopple@nvidia.com, dave.hansen@linux.intel.com, will@kernel.org, baohua@kernel.org, jack@suse.cz, srivatsa@csail.mit.edu, haowenchao22@gmail.com, hughd@google.com, aneesh.kumar@kernel.org, yang@os.amperecomputing.com, peterx@redhat.com, ioworker0@gmail.com, wangkefeng.wang@huawei.com, ziy@nvidia.com, jglisse@google.com, surenb@google.com, vishal.moola@gmail.com, zokeefe@google.com, zhengqi.arch@bytedance.com, jhubbard@nvidia.com, 21cnbao@gmail.com, willy@infradead.org, kirill.shutemov@linux.intel.com, david@redhat.com, aarcange@redhat.com, raquini@redhat.com, sunnanyong@huawei.com, usamaarif642@gmail.com, audra@redhat.com, akpm@linux-foundation.org References: <20250108233128.14484-1-npache@redhat.com> <20250108233128.14484-9-npache@redhat.com> <23023f48-95c6-4a24-ac8b-aba4b1a441b4@arm.com> Content-Language: en-US In-Reply-To: <23023f48-95c6-4a24-ac8b-aba4b1a441b4@arm.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit 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 > > 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 :) > >