From mboxrd@z Thu Jan 1 00:00:00 1970 From: Suzuki K Poulose Subject: Re: [PATCH] KVM: arm64: Clarify explanation of STAGE2_PGTABLE_LEVELS Date: Tue, 6 Nov 2018 09:52:59 +0000 Message-ID: References: <20181102075352.20636-1-christoffer.dall@arm.com> <404f2d39-5dc5-602f-0594-0997b409ff84@arm.com> <20181102142543.GY12057@e113682-lin.lund.arm.com> <20181106084215.GJ12057@e113682-lin.lund.arm.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; Format="flowed" Content-Transfer-Encoding: 7bit Cc: Marc Zyngier , kvmarm@lists.cs.columbia.edu, linux-arm-kernel@lists.infradead.org, kvm@vger.kernel.org To: Christoffer Dall Return-path: In-Reply-To: <20181106084215.GJ12057@e113682-lin.lund.arm.com> Content-Language: en-US List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kvmarm-bounces@lists.cs.columbia.edu Sender: kvmarm-bounces@lists.cs.columbia.edu List-Id: kvm.vger.kernel.org On 06/11/2018 08:42, Christoffer Dall wrote: > On Mon, Nov 05, 2018 at 03:00:34PM +0000, Suzuki K Poulose wrote: >> >> >> On 02/11/18 14:25, Christoffer Dall wrote: >>> On Fri, Nov 02, 2018 at 11:02:38AM +0000, Suzuki K Poulose wrote: >>>> Hi >>>> >>>> On 02/11/18 07:53, Christoffer Dall wrote: >>>>> In attempting to re-construct the logic for our stage 2 page table >>>>> layout I found the reaoning in the comment explaining how we calculate >>>>> the number of levels used for stage 2 page tables a bit backwards. >>>>> >>>>> This commit attempts to clarify the comment, to make it slightly easier >>>>> to read without having the Arm ARM open on the right page. >>>>> >>>>> While we're at it, fixup a typo in a comment that was recently changed. >>>>> >>>>> Signed-off-by: Christoffer Dall >>>>> --- >>>>> arch/arm64/include/asm/stage2_pgtable.h | 17 ++++++++++------- >>>>> virt/kvm/arm/mmu.c | 2 +- >>>>> 2 files changed, 11 insertions(+), 8 deletions(-) >>>>> >>>>> diff --git a/arch/arm64/include/asm/stage2_pgtable.h b/arch/arm64/include/asm/stage2_pgtable.h >>>>> index d352f6df8d2c..9c387320b28c 100644 >>>>> --- a/arch/arm64/include/asm/stage2_pgtable.h >>>>> +++ b/arch/arm64/include/asm/stage2_pgtable.h >>>>> @@ -31,15 +31,18 @@ >>>>> /* >>>>> * The hardware supports concatenation of up to 16 tables at stage2 entry level >>>>> - * and we use the feature whenever possible. >>>>> + * and we use the feature whenever possible, which means we resolve 4 bits of >>>> >>>> s/we resolve 4 bits/we resolve 4 additional bits/ ? >>>> >>> >>> yes >>> >>>>> + * address at the entry level. >>>>> * >>>>> - * Now, the minimum number of bits resolved at any level is (PAGE_SHIFT - 3). >>>>> + * This implies, the total number of page table levels required for >>>>> + * IPA_SHIFT at stage2 expected by the hardware can be calculated using >>>>> + * the same logic used for the (non-collapsable) stage1 page tables but for >>>>> + * (IPA_SHIFT - 4). >>>>> + * >>>>> + * Note, the minimum number of bits resolved at any level is (PAGE_SHIFT - 3). >>>> >>>> May be we could improve it further by : >>>> >>>> s/resolved at any level/resolved at any *non-entry* level/ >>>> >>>> as, we could resolve as small as 1 bit at the entry level. >>>> >>>> >>> >>> yes >>> >>>>> * On arm64, the smallest PAGE_SIZE supported is 4k, which means >>>>> - * (PAGE_SHIFT - 3) > 4 holds for all page sizes. >>>>> - * This implies, the total number of page table levels at stage2 expected >>>>> - * by the hardware is actually the number of levels required for (IPA_SHIFT - 4) >>>>> - * in normal translations(e.g, stage1), since we cannot have another level in >>>>> - * the range (IPA_SHIFT, IPA_SHIFT - 4). >>>>> + * (PAGE_SHIFT - 3) > 4 holds for all page sizes >>>>> + * and therefore we will need a minimum of two levels for stage2 in all cases. >>>> >>>> I think the above statement is misleading. The minimum number of >>>> levels has nothing to do with the concatenation. >>> >>> Architecturally surely it does? (The point of concatenation is to >>> reduce the minimal number of levels required.) >>> >>> Maybe you mean the minimum number of levels imposed by KVM here? >>> >>>> For e.g, we could >>>> still create a stage2 with 1 level (32bit IPA on 64K, 29bit + 3bit >>>> concatenated), going by the same rules above. The only reason why >>>> we limit the number of levels to 2, is to prevent splitting stage1 PMD >>>> huge mappings (which are quite common) at stage2. >>>> >>> >>> So I wasn't entirely clear what the comment was trying to say with the >>> "(PAGE_SHIFT - 3) > 4 holds for all page size" statement, so I though >>> that was there to show that we'll need a minimum of two levels, but >>> maybe that was written under the assumption of the limitations of >>> IPA_SHIFT (was KVM_PHYS_SIZE). >> >> See below. >> >>> >>> Since you wrote the original comment, and I couldn't correctly parse >>> that, and I apparently still didn't fully understand, can you suggest an >>> alternative wording? >> >> I think trying to over explain the concept has created more confusion. >> The whole paragraph is trying to prove that we only need : >> >> ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) >> to map IPA_SHIFT bits at stage2 with maximum utilization of the >> concatenation at entry level. > > Yes, I think that comes across more clearly in my rewording up to the > "Note, ...". Yes it does and I prefer your version than mine. > >> >> Right now the comment tries to establish it via the hard route, by >> proving that there cannot be an intermediate level in the range >> [IPA_SHIFT, IPA_SHIFT - 4]. Or in other words : >> >> (ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) + 1) >= >> ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT) >> >> I don't know if it is worth the explanation and then causing further >> confusion. > > I think you're then actually trying to explain two things. > > First, we can get the number of levels by using the stage 1 calculation > and adjust for concatenation by subtracting 4 from the number of bits we > need to translate. > > Second, some further reasoning about *why* that is true. > > It remains unclear to me exactly what your point about > '(PAGE_SHIFT - 3) > 4' > is and how that supports the second point. Also I'm not entirely sure > why we need that. So, we have to prove that : x + 1 >= y, where : x = ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) y = ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT) We can prove it by contradiction. i.e let us assume y > x + 1, => There is an additional level between, (y) and (x + 1), which implies, there is an intermediate level covering the "bits" of the input address in the range [IPA_SHIFT, IPA_SHIFT - 4]. But since we must resolve exactly (PAGE_SHIFT - 3) bits (9bits minimum) in an intermediate level, that level can't exist. And thus our assumption can never be true. I guess we don't need to go to that level of craziness, just to prove it formally. > > I was trying to preserve all the information you had in the original > comment (assuming it was important), but I honestly think that we only > need to explain the first part (because the confusing part of the code > is the reuse of a stage 1 macro and subtracting 4). > >> >> May be I could replace the confusing text with something like : >> >> "A normal page table with ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) levels >> is guaranteed to resolve minimum of (IPA_SHIFT - 4)bits (when the entry >> level is fully used, and more bits otherwise.). For an input address of >> size IPA_SHIFT bits, we could cover the remaining 4 bits using the same >> number of levels or using the concatenation if needed." >> > > I prefer my version above to explain this particular aspect :) > > But this seems to exclude the stuff you originally had about > (PAGE_SHIFT - 3) > 4' ? Does the above make it clear ? Cheers Suzuki From mboxrd@z Thu Jan 1 00:00:00 1970 From: suzuki.poulose@arm.com (Suzuki K Poulose) Date: Tue, 6 Nov 2018 09:52:59 +0000 Subject: [PATCH] KVM: arm64: Clarify explanation of STAGE2_PGTABLE_LEVELS In-Reply-To: <20181106084215.GJ12057@e113682-lin.lund.arm.com> References: <20181102075352.20636-1-christoffer.dall@arm.com> <404f2d39-5dc5-602f-0594-0997b409ff84@arm.com> <20181102142543.GY12057@e113682-lin.lund.arm.com> <20181106084215.GJ12057@e113682-lin.lund.arm.com> Message-ID: To: linux-arm-kernel@lists.infradead.org List-Id: linux-arm-kernel.lists.infradead.org On 06/11/2018 08:42, Christoffer Dall wrote: > On Mon, Nov 05, 2018 at 03:00:34PM +0000, Suzuki K Poulose wrote: >> >> >> On 02/11/18 14:25, Christoffer Dall wrote: >>> On Fri, Nov 02, 2018 at 11:02:38AM +0000, Suzuki K Poulose wrote: >>>> Hi >>>> >>>> On 02/11/18 07:53, Christoffer Dall wrote: >>>>> In attempting to re-construct the logic for our stage 2 page table >>>>> layout I found the reaoning in the comment explaining how we calculate >>>>> the number of levels used for stage 2 page tables a bit backwards. >>>>> >>>>> This commit attempts to clarify the comment, to make it slightly easier >>>>> to read without having the Arm ARM open on the right page. >>>>> >>>>> While we're at it, fixup a typo in a comment that was recently changed. >>>>> >>>>> Signed-off-by: Christoffer Dall >>>>> --- >>>>> arch/arm64/include/asm/stage2_pgtable.h | 17 ++++++++++------- >>>>> virt/kvm/arm/mmu.c | 2 +- >>>>> 2 files changed, 11 insertions(+), 8 deletions(-) >>>>> >>>>> diff --git a/arch/arm64/include/asm/stage2_pgtable.h b/arch/arm64/include/asm/stage2_pgtable.h >>>>> index d352f6df8d2c..9c387320b28c 100644 >>>>> --- a/arch/arm64/include/asm/stage2_pgtable.h >>>>> +++ b/arch/arm64/include/asm/stage2_pgtable.h >>>>> @@ -31,15 +31,18 @@ >>>>> /* >>>>> * The hardware supports concatenation of up to 16 tables at stage2 entry level >>>>> - * and we use the feature whenever possible. >>>>> + * and we use the feature whenever possible, which means we resolve 4 bits of >>>> >>>> s/we resolve 4 bits/we resolve 4 additional bits/ ? >>>> >>> >>> yes >>> >>>>> + * address at the entry level. >>>>> * >>>>> - * Now, the minimum number of bits resolved at any level is (PAGE_SHIFT - 3). >>>>> + * This implies, the total number of page table levels required for >>>>> + * IPA_SHIFT at stage2 expected by the hardware can be calculated using >>>>> + * the same logic used for the (non-collapsable) stage1 page tables but for >>>>> + * (IPA_SHIFT - 4). >>>>> + * >>>>> + * Note, the minimum number of bits resolved at any level is (PAGE_SHIFT - 3). >>>> >>>> May be we could improve it further by : >>>> >>>> s/resolved at any level/resolved at any *non-entry* level/ >>>> >>>> as, we could resolve as small as 1 bit at the entry level. >>>> >>>> >>> >>> yes >>> >>>>> * On arm64, the smallest PAGE_SIZE supported is 4k, which means >>>>> - * (PAGE_SHIFT - 3) > 4 holds for all page sizes. >>>>> - * This implies, the total number of page table levels at stage2 expected >>>>> - * by the hardware is actually the number of levels required for (IPA_SHIFT - 4) >>>>> - * in normal translations(e.g, stage1), since we cannot have another level in >>>>> - * the range (IPA_SHIFT, IPA_SHIFT - 4). >>>>> + * (PAGE_SHIFT - 3) > 4 holds for all page sizes >>>>> + * and therefore we will need a minimum of two levels for stage2 in all cases. >>>> >>>> I think the above statement is misleading. The minimum number of >>>> levels has nothing to do with the concatenation. >>> >>> Architecturally surely it does? (The point of concatenation is to >>> reduce the minimal number of levels required.) >>> >>> Maybe you mean the minimum number of levels imposed by KVM here? >>> >>>> For e.g, we could >>>> still create a stage2 with 1 level (32bit IPA on 64K, 29bit + 3bit >>>> concatenated), going by the same rules above. The only reason why >>>> we limit the number of levels to 2, is to prevent splitting stage1 PMD >>>> huge mappings (which are quite common) at stage2. >>>> >>> >>> So I wasn't entirely clear what the comment was trying to say with the >>> "(PAGE_SHIFT - 3) > 4 holds for all page size" statement, so I though >>> that was there to show that we'll need a minimum of two levels, but >>> maybe that was written under the assumption of the limitations of >>> IPA_SHIFT (was KVM_PHYS_SIZE). >> >> See below. >> >>> >>> Since you wrote the original comment, and I couldn't correctly parse >>> that, and I apparently still didn't fully understand, can you suggest an >>> alternative wording? >> >> I think trying to over explain the concept has created more confusion. >> The whole paragraph is trying to prove that we only need : >> >> ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) >> to map IPA_SHIFT bits at stage2 with maximum utilization of the >> concatenation at entry level. > > Yes, I think that comes across more clearly in my rewording up to the > "Note, ...". Yes it does and I prefer your version than mine. > >> >> Right now the comment tries to establish it via the hard route, by >> proving that there cannot be an intermediate level in the range >> [IPA_SHIFT, IPA_SHIFT - 4]. Or in other words : >> >> (ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) + 1) >= >> ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT) >> >> I don't know if it is worth the explanation and then causing further >> confusion. > > I think you're then actually trying to explain two things. > > First, we can get the number of levels by using the stage 1 calculation > and adjust for concatenation by subtracting 4 from the number of bits we > need to translate. > > Second, some further reasoning about *why* that is true. > > It remains unclear to me exactly what your point about > '(PAGE_SHIFT - 3) > 4' > is and how that supports the second point. Also I'm not entirely sure > why we need that. So, we have to prove that : x + 1 >= y, where : x = ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) y = ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT) We can prove it by contradiction. i.e let us assume y > x + 1, => There is an additional level between, (y) and (x + 1), which implies, there is an intermediate level covering the "bits" of the input address in the range [IPA_SHIFT, IPA_SHIFT - 4]. But since we must resolve exactly (PAGE_SHIFT - 3) bits (9bits minimum) in an intermediate level, that level can't exist. And thus our assumption can never be true. I guess we don't need to go to that level of craziness, just to prove it formally. > > I was trying to preserve all the information you had in the original > comment (assuming it was important), but I honestly think that we only > need to explain the first part (because the confusing part of the code > is the reuse of a stage 1 macro and subtracting 4). > >> >> May be I could replace the confusing text with something like : >> >> "A normal page table with ARM64_HW_PGTABLE_LEVELS(IPA_SHIFT - 4) levels >> is guaranteed to resolve minimum of (IPA_SHIFT - 4)bits (when the entry >> level is fully used, and more bits otherwise.). For an input address of >> size IPA_SHIFT bits, we could cover the remaining 4 bits using the same >> number of levels or using the concatenation if needed." >> > > I prefer my version above to explain this particular aspect :) > > But this seems to exclude the stuff you originally had about > (PAGE_SHIFT - 3) > 4' ? Does the above make it clear ? Cheers Suzuki