From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id E28C1E77188 for ; Sun, 12 Jan 2025 16:41:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 276E26B0092; Sun, 12 Jan 2025 11:41:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 1FFA36B0098; Sun, 12 Jan 2025 11:41:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0A0AC6B0099; Sun, 12 Jan 2025 11:41:32 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id DD6816B0092 for ; Sun, 12 Jan 2025 11:41:31 -0500 (EST) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 8839316189F for ; Sun, 12 Jan 2025 16:41:31 +0000 (UTC) X-FDA: 82999365582.25.EDF6FD5 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by imf19.hostedemail.com (Postfix) with ESMTP id 80F771A0004 for ; Sun, 12 Jan 2025 16:41:29 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=none; dmarc=pass (policy=none) header.from=arm.com; spf=pass (imf19.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@arm.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1736700089; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=OuPjA79nHQDtZQsQ6Ns+N1e+HFmNOlF1jDpL2aU0DFA=; b=ot9lmgAD/hYhS0QX9gZ9tW7vi0l+rxoVZk6b9sG6zexTpurd9G7JP1BprdxsxcJIgbOlh6 lyeFlayGBAKCoa6rEEG2lhEkl3wVhettCe+iwxFKcrj6/SPKUOFfsR9ZhN21Mjh8S2aMTh Wwj8UV2+fDdbdJsPz/I5kIE4qovV1iU= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1736700089; a=rsa-sha256; cv=none; b=raw9VuRUO7IwUkkbLgZFhfKGxCIDrnHu1e9bmRqFpyQFz/AyAp/CP1zWwlgsTbVvlFjwrg q5z5oVrUTdy3b4/rdkSZwdaFq0Wg54SxeYQschSyOtM/4wVw/4NaAkCqjv+F2uX8iX34E9 BmQh5Bm2cRyiGV0rN+I1AeobNElZbGA= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=none; dmarc=pass (policy=none) header.from=arm.com; spf=pass (imf19.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@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 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 X-Stat-Signature: ktn5rghun8ryfupy7txujf6qi3o3z9jt X-Rspamd-Queue-Id: 80F771A0004 X-Rspam-User: X-Rspamd-Server: rspam01 X-HE-Tag: 1736700089-929076 X-HE-Meta: U2FsdGVkX18YEsyOhPj2FkcYcNTrMXxswzy65nAFmuoTT+yzp9PysZrUeiWfx4Nm3wRZOJt7UP8UQo+9mhIPTNXXXwpuL8zzHpQ1Ce+4CJXpl+gDUHQ9yz6k6J0vLPOM6z0h4ra+yPnOpAodlya/eSjy3ZSczlqeFRi+FfN14uSMVYBl6tHqnJDxCeX4RJsjA/ISynGTUCFnLY8b2sXwYYoglo+fS06cA08j/C3vtoJD5LZQjuPLQ2g8C8sprzQg+xUOabAFNLBJncDME6uvGMYdWbIQKtuNO76wD81m1RBoFQL3lS6VsVniCJZ/m9PkbuVODPtB2gZMLuoJL4GsRxXCQoOJ+Obnf1onq705c8FZMjl/caVdubCyiim/D7RFO/FRZDP7Wrd8R0WuwJRXAfQIgRAl7SANz2H0FelC5La3W1BnOemLAys+dbpCjgk3qoCIqbhNnjPtcHAuqc5soAlj106xP9rRoQYBykUWG52eyY+ve2tJsOP+ki4IYTibQob2+nQUDVhszVcuiRJkjFHNc4c1fEMBWKTTbNmp9b4jV7V0/hr0zTHWPqG5KYhwJ+kNqram+w2l+IhxSrembQVKX5mPHrmvRRCYRbm9DCtqZHkqNMfv/S7qzBBYuokbMsUa+ZD4GSPCiAG//CwPw7nS8NPk8jMV0eRGHZb6KNXBCC2LElJbpMyhGs8JTp1hTVH3dAHwrLZl1Lpp8N7hpDzoZ1PvngDJqflKeh/EuMRNbZYgzF5jZF0AUq4BbTypmT/Qs3VyA4vGpYWrT5l10G+OY14PZUHI8HDxoXBrhtPk2xbRwPHmUOGK25bO8fl4n/tGUsxIQk5dRRY97PIAhrmR9cm5am467VMALp84BQ3sBUpvUXCEalNLbLZtvTJx4MfPWZox1ud4vwTdIyMK/RcOmkFkoMbrj8r40RCE/4MSCl6GQN4NZxDQ5I5ErZ5AqpkHcKVuhLC4hp9L8zD P61Kyxuv qH+GFXm221mNDtA1EZOet1bOHp0b4GhwZUHBt88Zs5MvEkXVjCxtNL4gvjV85Zi+DPYEEPBS7r5K11FWbrn6ldng2wHs52Nb1kuW66GxiN0AdosibvsJyLNBnTqgZiP/jfOQmqw2xaXK/DQOWnheER+qcneoULpCs5GSvFUdIEBH4E6fxBewZCa9xEQqMKiNXbnfy/oF+cIkZnKGw13BNpLxufO+O0AiHfi/e9S4PlMHMgdD45XxsR4oTE/6mPc4dNVxy+XfncPJB0uQdVsEkYeDqSVKYnD5wp1Hw0XhIr61+Go5iK53/xaocxBeZMdopOvbg+mJe7LuE46k75hZwM88aqJ+ofN7JQDowWmrnbQok2/hY5zjK+NLwfPvqh5duwrRD0XsICXf4gHPKLsWHGUsgMKbrx9VaddiGhfmCmWtoPdo= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000201, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 :) > >