Message ID | 1444821634-1689-4-git-send-email-suzuki.poulose@arm.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > Introduce helpers for finding the number of page table > levels required for a given VA width, shift for a particular > page table level. > > Convert the existing users to the new helpers. More users > to follow. > > Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org> > Cc: Mark Rutland <mark.rutland@arm.com> > Cc: Catalin Marinas <catalin.marinas@arm.com> > Cc: Will Deacon <will.deacon@arm.com> > Cc: Marc Zyngier <marc.zyngier@arm.com> > Signed-off-by: Suzuki K. Poulose <suzuki.poulose@arm.com> > > --- > Changes since V2: > - Add comments around the macros > - Change ARM64_HW_PGTABLE_LEVEL_SHIFT to accept pagetable level as > described by ARM ARM > --- > arch/arm64/include/asm/pgtable-hwdef.h | 25 ++++++++++++++++++++++--- > 1 file changed, 22 insertions(+), 3 deletions(-) > > diff --git a/arch/arm64/include/asm/pgtable-hwdef.h b/arch/arm64/include/asm/pgtable-hwdef.h > index 95c1ec0..c6194ab 100644 > --- a/arch/arm64/include/asm/pgtable-hwdef.h > +++ b/arch/arm64/include/asm/pgtable-hwdef.h > @@ -16,13 +16,31 @@ > #ifndef __ASM_PGTABLE_HWDEF_H > #define __ASM_PGTABLE_HWDEF_H > > +/* > + * Number of page-table levels required to address 'va_bits' wide > + * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > + * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > + * > + * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > + * > + * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > + * due to build issues. So we use the following magic formula. > + */ > +#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) I think I failed the interview question [1]. :( I read the comment to mean this was a brand-new piece of magic, as opposed to a constant-folded copy of DIV_ROUND_UP. So it seems there's still some scope for confusion, even if that only includes me. I think we should bite the bullet and have a full copy of DIV_ROUND_UP, e.g. /* * We cannot include linux/kernel.h for DIV_ROUND_UP due to build * issues. Instead, copy & paste its magic formula here for now. */ #define __DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) /* * Number of page-table levels required to address 'va_bits' wide * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) * bits with (PAGE_SHIFT - 3) bits at each page table level. */ #define ARM64_HW_PGTABLE_LEVELS(va_bits) \ __DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) It's a little verbose, but it keeps this legible and ensures I get the job. We can leave the constant-folding to the compiler. Other than that, this looks good to me. With the above applied: Acked-by: Mark Rutland <mark.rutland@arm.com> Thanks, Mark. [1] http://lists.infradead.org/pipermail/linux-arm-kernel/2015-October/375609.html
On 14/10/15 18:07, Mark Rutland wrote: > On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: >> + * Number of page-table levels required to address 'va_bits' wide >> + * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) >> + * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: >> + * >> + * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) >> + * >> + * We cannot include linux/kernel.h which defines DIV_ROUND_UP here >> + * due to build issues. So we use the following magic formula. >> + */ >> +#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) > > I think I failed the interview question [1]. :( > > I read the comment to mean this was a brand-new piece of magic, as > opposed to a constant-folded copy of DIV_ROUND_UP. So it seems there's > still some scope for confusion, even if that only includes me. > Wouldn't it be better to modify the comment to say, we open coded the DIV_ROUND_UP ? We could potentially end up in a conflict if somebody else does __DIV_ROUND_UP. I have seen similar issues with the CPU feature series, where if I include one particular header file in another, kernel build breaks without giving you a clue, what caused the error. Usually due to the multiple definitions (e.g NSEC_PER_SEC) and other conflicts. Given that this header file gets included with asm/page.h and hence would be used included for people outside arch/arm64, I would prefer, not to head there, instead update the comment, something like this : /* * Number of page-table levels required to address 'va_bits' wide * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: * * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) * * where DIV_ROUND_UP (n, d) = > ((n) + (d) - 1) / (d) * * We cannot include linux/kernel.h which defines DIV_ROUND_UP here * due to build issues. So we open code the DIV_ROUND_UP and hence * we get : * ((va_bits - PAGE_SHIFT) + (PAGE_SHIFT - 3) -1) / (PAGE_SHIFT - 3) * * which gets simplified as : * (((va_bits) - 4) / (PAGE_SHIFT - 3)) * */ Let me know if you are happy with that ? Thanks Suzuki
On Thu, Oct 15, 2015 at 10:35:38AM +0100, Suzuki K. Poulose wrote: > On 14/10/15 18:07, Mark Rutland wrote: > >On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > > >>+ * Number of page-table levels required to address 'va_bits' wide > >>+ * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > >>+ * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > >>+ * > >>+ * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > >>+ * > >>+ * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > >>+ * due to build issues. So we use the following magic formula. > >>+ */ > >>+#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) > > > >I think I failed the interview question [1]. :( > > > >I read the comment to mean this was a brand-new piece of magic, as > >opposed to a constant-folded copy of DIV_ROUND_UP. So it seems there's > >still some scope for confusion, even if that only includes me. > > > > Wouldn't it be better to modify the comment to say, we open coded the DIV_ROUND_UP ? > We could potentially end up in a conflict if somebody else does __DIV_ROUND_UP. > I have seen similar issues with the CPU feature series, where if I include one > particular header file in another, kernel build breaks without giving you a clue, > what caused the error. Usually due to the multiple definitions (e.g NSEC_PER_SEC) > and other conflicts. Given that this header file gets included with asm/page.h and > hence would be used included for people outside arch/arm64, I would prefer, not to > head there, instead update the comment, something like this : > > > /* > * Number of page-table levels required to address 'va_bits' wide > * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > * > * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > * > * where DIV_ROUND_UP (n, d) = > ((n) + (d) - 1) / (d) > * > * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > * due to build issues. So we open code the DIV_ROUND_UP and hence > * we get : > * ((va_bits - PAGE_SHIFT) + (PAGE_SHIFT - 3) -1) / (PAGE_SHIFT - 3) > * > * which gets simplified as : > * (((va_bits) - 4) / (PAGE_SHIFT - 3)) > * > */ > > Let me know if you are happy with that ? I am also happy with this. For the above, feel free to add: Acked-by: Mark Rutland <mark.rutland@arm.com> Thanks, Mark.
On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > Introduce helpers for finding the number of page table > levels required for a given VA width, shift for a particular > page table level. > > Convert the existing users to the new helpers. More users > to follow. > > Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org> > Cc: Mark Rutland <mark.rutland@arm.com> > Cc: Catalin Marinas <catalin.marinas@arm.com> > Cc: Will Deacon <will.deacon@arm.com> > Cc: Marc Zyngier <marc.zyngier@arm.com> > Signed-off-by: Suzuki K. Poulose <suzuki.poulose@arm.com> > > --- > Changes since V2: > - Add comments around the macros > - Change ARM64_HW_PGTABLE_LEVEL_SHIFT to accept pagetable level as > described by ARM ARM > --- > arch/arm64/include/asm/pgtable-hwdef.h | 25 ++++++++++++++++++++++--- > 1 file changed, 22 insertions(+), 3 deletions(-) > > diff --git a/arch/arm64/include/asm/pgtable-hwdef.h b/arch/arm64/include/asm/pgtable-hwdef.h > index 95c1ec0..c6194ab 100644 > --- a/arch/arm64/include/asm/pgtable-hwdef.h > +++ b/arch/arm64/include/asm/pgtable-hwdef.h > @@ -16,13 +16,31 @@ > #ifndef __ASM_PGTABLE_HWDEF_H > #define __ASM_PGTABLE_HWDEF_H > > +/* > + * Number of page-table levels required to address 'va_bits' wide > + * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > + * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > + * > + * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > + * > + * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > + * due to build issues. So we use the following magic formula. > + */ > +#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) > + > +/* > + * Size mapped by an entry at level n > + * We map PAGE_SHIFT - 3 at all levels, except the PAGE_SHIFT bits at the last level > + */ > +#define ARM64_HW_PGTABLE_LEVEL_SHIFT(n) ((PAGE_SHIFT - 3) * (4 - (n)) + 3) I feel like I'm partially failing the interview question again, in that I don't fully understand the '+ 3' in the end? Also the comment could be expanded to explain the (4 - (n)), but I couldn't easily come up with good language for explaining that you have a maximum of 4 levels and you subtract the 'n' levels that your are not accounting for... That said, this still looks functionally correct to me. -Christoffer > + > #define PTRS_PER_PTE (1 << (PAGE_SHIFT - 3)) > > /* > * PMD_SHIFT determines the size a level 2 page table entry can map. > */ > #if CONFIG_PGTABLE_LEVELS > 2 > -#define PMD_SHIFT ((PAGE_SHIFT - 3) * 2 + 3) > +#define PMD_SHIFT ARM64_HW_PGTABLE_LEVEL_SHIFT(2) > #define PMD_SIZE (_AC(1, UL) << PMD_SHIFT) > #define PMD_MASK (~(PMD_SIZE-1)) > #define PTRS_PER_PMD PTRS_PER_PTE > @@ -32,7 +50,7 @@ > * PUD_SHIFT determines the size a level 1 page table entry can map. > */ > #if CONFIG_PGTABLE_LEVELS > 3 > -#define PUD_SHIFT ((PAGE_SHIFT - 3) * 3 + 3) > +#define PUD_SHIFT ARM64_HW_PGTABLE_LEVEL_SHIFT(1) > #define PUD_SIZE (_AC(1, UL) << PUD_SHIFT) > #define PUD_MASK (~(PUD_SIZE-1)) > #define PTRS_PER_PUD PTRS_PER_PTE > @@ -42,7 +60,8 @@ > * PGDIR_SHIFT determines the size a top-level page table entry can map > * (depending on the configuration, this level can be 0, 1 or 2). > */ > -#define PGDIR_SHIFT ((PAGE_SHIFT - 3) * CONFIG_PGTABLE_LEVELS + 3) > +#define PGDIR_SHIFT \ > + ARM64_HW_PGTABLE_LEVEL_SHIFT(4 - CONFIG_PGTABLE_LEVELS) > #define PGDIR_SIZE (_AC(1, UL) << PGDIR_SHIFT) > #define PGDIR_MASK (~(PGDIR_SIZE-1)) > #define PTRS_PER_PGD (1 << (VA_BITS - PGDIR_SHIFT)) > -- > 1.7.9.5 >
On Thu, Oct 15, 2015 at 10:35:38AM +0100, Suzuki K. Poulose wrote: > On 14/10/15 18:07, Mark Rutland wrote: > >On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > > >>+ * Number of page-table levels required to address 'va_bits' wide > >>+ * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > >>+ * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > >>+ * > >>+ * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > >>+ * > >>+ * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > >>+ * due to build issues. So we use the following magic formula. > >>+ */ > >>+#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) > > > >I think I failed the interview question [1]. :( > > > >I read the comment to mean this was a brand-new piece of magic, as > >opposed to a constant-folded copy of DIV_ROUND_UP. So it seems there's > >still some scope for confusion, even if that only includes me. > > > > Wouldn't it be better to modify the comment to say, we open coded the DIV_ROUND_UP ? > We could potentially end up in a conflict if somebody else does __DIV_ROUND_UP. > I have seen similar issues with the CPU feature series, where if I include one > particular header file in another, kernel build breaks without giving you a clue, > what caused the error. Usually due to the multiple definitions (e.g NSEC_PER_SEC) > and other conflicts. Given that this header file gets included with asm/page.h and > hence would be used included for people outside arch/arm64, I would prefer, not to > head there, instead update the comment, something like this : > > > /* > * Number of page-table levels required to address 'va_bits' wide > * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > * > * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > * > * where DIV_ROUND_UP (n, d) = > ((n) + (d) - 1) / (d) > * > * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > * due to build issues. So we open code the DIV_ROUND_UP and hence > * we get : > * ((va_bits - PAGE_SHIFT) + (PAGE_SHIFT - 3) -1) / (PAGE_SHIFT - 3) > * > * which gets simplified as : > * (((va_bits) - 4) / (PAGE_SHIFT - 3)) > * > */ > > Let me know if you are happy with that ? > I preferred Mark's suggestion, but I don't have the experience with breaking builds with kernel header includes, so I guess we'll do with this. Thanks for adding the comments! -Christoffer
On Thu, Oct 15, 2015 at 01:37:35PM +0200, Christoffer Dall wrote: > On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > > Introduce helpers for finding the number of page table > > levels required for a given VA width, shift for a particular > > page table level. > > > > Convert the existing users to the new helpers. More users > > to follow. > > > > Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org> > > Cc: Mark Rutland <mark.rutland@arm.com> > > Cc: Catalin Marinas <catalin.marinas@arm.com> > > Cc: Will Deacon <will.deacon@arm.com> > > Cc: Marc Zyngier <marc.zyngier@arm.com> > > Signed-off-by: Suzuki K. Poulose <suzuki.poulose@arm.com> > > > > --- > > Changes since V2: > > - Add comments around the macros > > - Change ARM64_HW_PGTABLE_LEVEL_SHIFT to accept pagetable level as > > described by ARM ARM > > --- > > arch/arm64/include/asm/pgtable-hwdef.h | 25 ++++++++++++++++++++++--- > > 1 file changed, 22 insertions(+), 3 deletions(-) > > > > diff --git a/arch/arm64/include/asm/pgtable-hwdef.h b/arch/arm64/include/asm/pgtable-hwdef.h > > index 95c1ec0..c6194ab 100644 > > --- a/arch/arm64/include/asm/pgtable-hwdef.h > > +++ b/arch/arm64/include/asm/pgtable-hwdef.h > > @@ -16,13 +16,31 @@ > > #ifndef __ASM_PGTABLE_HWDEF_H > > #define __ASM_PGTABLE_HWDEF_H > > > > +/* > > + * Number of page-table levels required to address 'va_bits' wide > > + * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) > > + * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: > > + * > > + * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) > > + * > > + * We cannot include linux/kernel.h which defines DIV_ROUND_UP here > > + * due to build issues. So we use the following magic formula. > > + */ > > +#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) > > + > > +/* > > + * Size mapped by an entry at level n > > + * We map PAGE_SHIFT - 3 at all levels, except the PAGE_SHIFT bits at the last level > > + */ > > +#define ARM64_HW_PGTABLE_LEVEL_SHIFT(n) ((PAGE_SHIFT - 3) * (4 - (n)) + 3) > > I feel like I'm partially failing the interview question again, in that > I don't fully understand the '+ 3' in the end? The last level handles PAGE_SHIFT bits (the bits from the VA that are the same in the PA). We only accounted for (PAGE_SHIFT - 3) bits at each level when multiplying, so we add those 3 missing bits back at the end. Thanks, Mark.
On 15/10/15 13:44, Mark Rutland wrote: > On Thu, Oct 15, 2015 at 01:37:35PM +0200, Christoffer Dall wrote: >> On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: >>> Introduce helpers for finding the number of page table >>> levels required for a given VA width, shift for a particular >>> page table level. >>> +/* >>> + * Size mapped by an entry at level n >>> + * We map PAGE_SHIFT - 3 at all levels, except the PAGE_SHIFT bits at the last level >>> + */ >>> +#define ARM64_HW_PGTABLE_LEVEL_SHIFT(n) ((PAGE_SHIFT - 3) * (4 - (n)) + 3) >> >> I feel like I'm partially failing the interview question again, in that >> I don't fully understand the '+ 3' in the end? > > The last level handles PAGE_SHIFT bits (the bits from the VA that are > the same in the PA). We only accounted for (PAGE_SHIFT - 3) bits at each > level when multiplying, so we add those 3 missing bits back at the end. > Something like : /* * Size mapped by an entry at level n * We map PAGE_SHIFT - 3 at all levels, except the last, where we map PAGE_SHIFT bits. * The maximum number of levels supported by the architecture is 4. Hence at starting * at level n, we hanve (4 - n) levels of translation. So, the total number of bits * mapped by an entry at level n is : * * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT * * Rearranging it a bit we get : * (4 - n) * (PAGE_SHIFT - 3) + 3 */ Or we could use the formula without rearranging. Thanks Suzuki
On Thu, Oct 15, 2015 at 02:14:22PM +0100, Suzuki K. Poulose wrote: > On 15/10/15 13:44, Mark Rutland wrote: > >On Thu, Oct 15, 2015 at 01:37:35PM +0200, Christoffer Dall wrote: > >>On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > >>>Introduce helpers for finding the number of page table > >>>levels required for a given VA width, shift for a particular > >>>page table level. > > >>>+/* > >>>+ * Size mapped by an entry at level n > >>>+ * We map PAGE_SHIFT - 3 at all levels, except the PAGE_SHIFT bits at the last level > >>>+ */ > >>>+#define ARM64_HW_PGTABLE_LEVEL_SHIFT(n) ((PAGE_SHIFT - 3) * (4 - (n)) + 3) > >> > >>I feel like I'm partially failing the interview question again, in that > >>I don't fully understand the '+ 3' in the end? > > > >The last level handles PAGE_SHIFT bits (the bits from the VA that are > >the same in the PA). We only accounted for (PAGE_SHIFT - 3) bits at each > >level when multiplying, so we add those 3 missing bits back at the end. > > > > Something like : > > /* > * Size mapped by an entry at level n > * We map PAGE_SHIFT - 3 at all levels, except the last, where we map PAGE_SHIFT bits. > * The maximum number of levels supported by the architecture is 4. Hence at starting > * at level n, we hanve (4 - n) levels of translation. So, the total number of bits nit: s/hanve/have/ > * mapped by an entry at level n is : > * > * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT > * > * Rearranging it a bit we get : > * (4 - n) * (PAGE_SHIFT - 3) + 3 > */ > > Or we could use the formula without rearranging. > Either way, even I get it now. Thanks for the explanation!! Assuming some version of this goes in: Acked-by: Christoffer Dall <christoffer.dall@linaro.org>
On 15/10/15 14:30, Christoffer Dall wrote: > On Thu, Oct 15, 2015 at 02:14:22PM +0100, Suzuki K. Poulose wrote: >> On 15/10/15 13:44, Mark Rutland wrote: >>> On Thu, Oct 15, 2015 at 01:37:35PM +0200, Christoffer Dall wrote: >>>> On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: >> * The maximum number of levels supported by the architecture is 4. Hence at starting >> * at level n, we hanve (4 - n) levels of translation. So, the total number of bits > > nit: s/hanve/have/ Fixed. > >> * mapped by an entry at level n is : >> * >> * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT >> * >> * Rearranging it a bit we get : >> * (4 - n) * (PAGE_SHIFT - 3) + 3 >> */ >> >> Or we could use the formula without rearranging. >> > Either way, even I get it now. > > Thanks for the explanation!! :). I was involved too much in these calculations that, the formula looked obvious to me, when I wrote it. But yes, I did realise that it is indeed complicated, once I really started looking at explaining why I wrote it so. Thanks for being patient :) and complaining peacefully ! Btw, I have a revised (hopefully better) version here : /* * Size mapped by an entry at level n ( 0 <= n <= 3) * We map (PAGE_SHIFT - 3) at all translation levels and PAGE_SHIFT bits * in the final page. The maximum number of translation levels supported by * the architecture is 4. Hence, starting at at level n, we have further * ((4 - n) - 1) levels of translation excluding the offset within the page. * So, the total number of bits mapped by an entry at level n is : * * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT * * Rearranging it a bit we get : * (4 - n) * (PAGE_SHIFT - 3) + 3 */ > > Assuming some version of this goes in: > > Acked-by: Christoffer Dall <christoffer.dall@linaro.org> > Thanks. I lost two interview questions though ;) Suzuki
On Thu, Oct 15, 2015 at 02:48:47PM +0100, Suzuki K. Poulose wrote: > On 15/10/15 14:30, Christoffer Dall wrote: > >On Thu, Oct 15, 2015 at 02:14:22PM +0100, Suzuki K. Poulose wrote: > >>On 15/10/15 13:44, Mark Rutland wrote: > >>>On Thu, Oct 15, 2015 at 01:37:35PM +0200, Christoffer Dall wrote: > >>>>On Wed, Oct 14, 2015 at 12:20:26PM +0100, Suzuki K. Poulose wrote: > > > >> * The maximum number of levels supported by the architecture is 4. Hence at starting > >> * at level n, we hanve (4 - n) levels of translation. So, the total number of bits > > > >nit: s/hanve/have/ > > Fixed. > > > > >> * mapped by an entry at level n is : > >> * > >> * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT > >> * > >> * Rearranging it a bit we get : > >> * (4 - n) * (PAGE_SHIFT - 3) + 3 > >> */ > >> > >>Or we could use the formula without rearranging. > >> > >Either way, even I get it now. > > > >Thanks for the explanation!! > > :). I was involved too much in these calculations that, the formula looked > obvious to me, when I wrote it. But yes, I did realise that it is indeed > complicated, once I really started looking at explaining why I wrote it so. > Thanks for being patient :) and complaining peacefully ! > > Btw, I have a revised (hopefully better) version here : > > /* > * Size mapped by an entry at level n ( 0 <= n <= 3) > * We map (PAGE_SHIFT - 3) at all translation levels and PAGE_SHIFT bits > * in the final page. The maximum number of translation levels supported by > * the architecture is 4. Hence, starting at at level n, we have further > * ((4 - n) - 1) levels of translation excluding the offset within the page. > * So, the total number of bits mapped by an entry at level n is : > * > * ((4 - n) - 1) * (PAGE_SHIFT - 3) + PAGE_SHIFT > * > * Rearranging it a bit we get : > * (4 - n) * (PAGE_SHIFT - 3) + 3 > */ > Looks good. > > > > >Assuming some version of this goes in: > > > >Acked-by: Christoffer Dall <christoffer.dall@linaro.org> > > > > Thanks. I lost two interview questions though ;) > There are plenty of good sources for that in the KVM/ARM code. -Christoffer
diff --git a/arch/arm64/include/asm/pgtable-hwdef.h b/arch/arm64/include/asm/pgtable-hwdef.h index 95c1ec0..c6194ab 100644 --- a/arch/arm64/include/asm/pgtable-hwdef.h +++ b/arch/arm64/include/asm/pgtable-hwdef.h @@ -16,13 +16,31 @@ #ifndef __ASM_PGTABLE_HWDEF_H #define __ASM_PGTABLE_HWDEF_H +/* + * Number of page-table levels required to address 'va_bits' wide + * address, without section mapping. We resolve the top (va_bits - PAGE_SHIFT) + * bits with (PAGE_SHIFT - 3) bits at each page table level. Hence: + * + * levels = DIV_ROUND_UP((va_bits - PAGE_SHIFT), (PAGE_SHIFT - 3)) + * + * We cannot include linux/kernel.h which defines DIV_ROUND_UP here + * due to build issues. So we use the following magic formula. + */ +#define ARM64_HW_PGTABLE_LEVELS(va_bits) (((va_bits) - 4) / (PAGE_SHIFT - 3)) + +/* + * Size mapped by an entry at level n + * We map PAGE_SHIFT - 3 at all levels, except the PAGE_SHIFT bits at the last level + */ +#define ARM64_HW_PGTABLE_LEVEL_SHIFT(n) ((PAGE_SHIFT - 3) * (4 - (n)) + 3) + #define PTRS_PER_PTE (1 << (PAGE_SHIFT - 3)) /* * PMD_SHIFT determines the size a level 2 page table entry can map. */ #if CONFIG_PGTABLE_LEVELS > 2 -#define PMD_SHIFT ((PAGE_SHIFT - 3) * 2 + 3) +#define PMD_SHIFT ARM64_HW_PGTABLE_LEVEL_SHIFT(2) #define PMD_SIZE (_AC(1, UL) << PMD_SHIFT) #define PMD_MASK (~(PMD_SIZE-1)) #define PTRS_PER_PMD PTRS_PER_PTE @@ -32,7 +50,7 @@ * PUD_SHIFT determines the size a level 1 page table entry can map. */ #if CONFIG_PGTABLE_LEVELS > 3 -#define PUD_SHIFT ((PAGE_SHIFT - 3) * 3 + 3) +#define PUD_SHIFT ARM64_HW_PGTABLE_LEVEL_SHIFT(1) #define PUD_SIZE (_AC(1, UL) << PUD_SHIFT) #define PUD_MASK (~(PUD_SIZE-1)) #define PTRS_PER_PUD PTRS_PER_PTE @@ -42,7 +60,8 @@ * PGDIR_SHIFT determines the size a top-level page table entry can map * (depending on the configuration, this level can be 0, 1 or 2). */ -#define PGDIR_SHIFT ((PAGE_SHIFT - 3) * CONFIG_PGTABLE_LEVELS + 3) +#define PGDIR_SHIFT \ + ARM64_HW_PGTABLE_LEVEL_SHIFT(4 - CONFIG_PGTABLE_LEVELS) #define PGDIR_SIZE (_AC(1, UL) << PGDIR_SHIFT) #define PGDIR_MASK (~(PGDIR_SIZE-1)) #define PTRS_PER_PGD (1 << (VA_BITS - PGDIR_SHIFT))
Introduce helpers for finding the number of page table levels required for a given VA width, shift for a particular page table level. Convert the existing users to the new helpers. More users to follow. Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org> Cc: Mark Rutland <mark.rutland@arm.com> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Marc Zyngier <marc.zyngier@arm.com> Signed-off-by: Suzuki K. Poulose <suzuki.poulose@arm.com> --- Changes since V2: - Add comments around the macros - Change ARM64_HW_PGTABLE_LEVEL_SHIFT to accept pagetable level as described by ARM ARM --- arch/arm64/include/asm/pgtable-hwdef.h | 25 ++++++++++++++++++++++--- 1 file changed, 22 insertions(+), 3 deletions(-)