Re: 4level page tables for Linux II

Re: 4level page tables for Linux II

[Albert Cahalan]

Hmmm...

pml4, pgd, pmd, pte  (kernel names)
PML4E, PDPE, PDE, PTE   (AMD hardware names)

It's kind of a mess, isn't it? It was bad enough
with the "pmd" (page middle directory, ugh) being
some random invention and everything being generally
in conflict with real hardware naming. Now you've
come up with a fourth name.

Notice that you've resorted to using a number.
Why not do that for the others too? It would
bring some order to this ever-growing collection
of arbitrary names. Like this:

pd4, pd3, pd2, pd1

Re: 4level page tables for Linux II

[Andi Kleen]

On 12 Oct 2004 23:36:40 -0400
Albert Cahalan <albert@users.sf.net> wrote:

> Hmmm...
> 
> pml4, pgd, pmd, pte  (kernel names)
> PML4E, PDPE, PDE, PTE   (AMD hardware names)

No actually a PML4E is a PML4 _E_ntry in the AMD/Intel docs.
PML4 is the official name for the fourth level page.

> It's kind of a mess, isn't it? It was bad enough
> with the "pmd" (page middle directory, ugh) being
> some random invention and everything being generally
> in conflict with real hardware naming. Now you've
> come up with a fourth name.
> 
> Notice that you've resorted to using a number.

I just followed AMD.

> Why not do that for the others too? It would
> bring some order to this ever-growing collection
> of arbitrary names. Like this:

I don't think it makes sense to break code unnecessarily.

And when you cannot remember the few names for the level you 
better shouldn't touch VM at all.

-Andi

Re: 4level page tables for Linux II

[Albert Cahalan]

On Wed, 2004-10-13 at 03:22, Andi Kleen wrote:
> On 12 Oct 2004 23:36:40 -0400
> Albert Cahalan <albert@users.sf.net> wrote:
> 
> > Hmmm...
> > 
> > pml4, pgd, pmd, pte  (kernel names)
> > PML4E, PDPE, PDE, PTE   (AMD hardware names)
> 
> No actually a PML4E is a PML4 _E_ntry in the AMD/Intel docs.
> PML4 is the official name for the fourth level page.
> 
> > It's kind of a mess, isn't it? It was bad enough
> > with the "pmd" (page middle directory, ugh) being
> > some random invention and everything being generally
> > in conflict with real hardware naming. Now you've
> > come up with a fourth name.
> > 
> > Notice that you've resorted to using a number.
> 
> I just followed AMD.
> 
> > Why not do that for the others too? It would
> > bring some order to this ever-growing collection
> > of arbitrary names. Like this:
> 
> I don't think it makes sense to break code unnecessarily.
> 
> And when you cannot remember the few names for the level you 
> better shouldn't touch VM at all.

One of the reasons that Linux is so hackable is that
crummy names get changed. Here too, the old names are bad.

An old example: we use copy_from_user now, not copy_fromfs.
Don't you agree that this is an improvement? It broke code
unnecessarily, but Linus did it anyway. Linux would be a
lot less readable if it had screwy names everywhere.

Perhaps you shouldn't touch kernel code if you can't
remember that copy_fromfs is unrelated to fs code.
Still, why make things difficult? The less effort you
waste remembering stupid names, the more you can spare
for writing great code.

Re: 4level page tables for Linux II

[Matthias Urlichs]

Hi, Andi Kleen wrote:

> And when you cannot remember the few names for the level you 
> better shouldn't touch VM at all.

Disagree. Rather strongly in fact.

It's probably OK if you already know the stuff and have been hacking
Linux' mm for years already, but if you try to learn how things work by
actually looking at the code..?

Just number them. Let pd1 point to pages, pd2 to pd1 entries, and so on.
(Level zero is the actual pages.)

-- 
Matthias Urlichs

Re: 4level page tables for Linux II

[Andrew Grover]

On Thu, 14 Oct 2004 18:57:24 +0200, Matthias Urlichs
<smurf@smurf.noris.de> wrote:
> Hi, Andi Kleen wrote:
> 
> > And when you cannot remember the few names for the level you
> > better shouldn't touch VM at all.
> 
> Disagree. Rather strongly in fact.
> 
> It's probably OK if you already know the stuff and have been hacking
> Linux' mm for years already, but if you try to learn how things work by
> actually looking at the code..?
> 
> Just number them. Let pd1 point to pages, pd2 to pd1 entries, and so on.
> (Level zero is the actual pages.)

I happen to agree, but surely this can be addressed at our leisure,
after pml4 is in.

Maybe a good task for the kernel janitors, if we all agree more
sensible names are desirable.

Regards -- Andy

Re: 4level page tables for Linux II

[Jörn Engel]

On Thu, 14 October 2004 18:55:20 -0700, Andrew Grover wrote:
> On Thu, 14 Oct 2004 18:57:24 +0200, Matthias Urlichs
> > Disagree. Rather strongly in fact.
> > 
> > It's probably OK if you already know the stuff and have been hacking
> > Linux' mm for years already, but if you try to learn how things work by
> > actually looking at the code..?
> > 
> > Just number them. Let pd1 point to pages, pd2 to pd1 entries, and so on.
> > (Level zero is the actual pages.)
> 
> I happen to agree, but surely this can be addressed at our leisure,
> after pml4 is in.
> 
> Maybe a good task for the kernel janitors, if we all agree more
> sensible names are desirable.

Please don't.  Current names may be odd, but at least they are
sufficiently different from one another.  4 names that only differ in
a single number are an invitation for typos, thinkos and similar
confusion.

Whenever I notice a mess like that in any piece of software I change
it to make the difference bigger, not smaller.  Have you ever been
slightly distracted, kept typing anyway and it compiled just fine,
creating a subtle bug? ;)

Jörn

-- 
When I am working on a problem I never think about beauty.  I think
only how to solve the problem.  But when I have finished, if the
solution is not beautiful, I know it is wrong.
-- R. Buckminster Fuller

Re: 4level page tables for Linux II

[Matthias Urlichs]

[-- Attachment #1: Type: text/plain, Size: 660 bytes --]

Hi,

Jörn Engel:
> Please don't.  Current names may be odd, but at least they are
> sufficiently different from one another.  4 names that only differ in
> a single number are an invitation for typos, thinkos and similar
> confusion.
> 
Right now, so are the existing names: you have to remember which is which.

Levels numbered 1..4 are much simpler: you only have to remember that
the actual pages are level zero.

The solution of your typo problem is typechecking in the compiler;
presumably it'll warn me if I try to store a pgd3 pointer in a pgd2
entry.

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: 4level page tables for Linux II

[Jörn Engel]

On Fri, 15 October 2004 15:55:21 +0200, Matthias Urlichs wrote:
>
> Right now, so are the existing names: you have to remember which is which.

That appears to be the problem with any name.  Still, my confusion
about which is read(2) and which is write(2) is rare.

> Levels numbered 1..4 are much simpler: you only have to remember that
> the actual pages are level zero.

if and goto is much simpler, compared to while, for, do..while, else,
and whatever slipped my mind right now.  Maybe you should target the c
standard next. ;)

> The solution of your typo problem is typechecking in the compiler;
> presumably it'll warn me if I try to store a pgd3 pointer in a pgd2
> entry.

That should help somewhat, agreed.  Patches?

Jörn

-- 
Public Domain  - Free as in Beer
General Public - Free as in Speech
BSD License    - Free as in Enterprise
Shared Source  - Free as in "Work will make you..."

Re: 4level page tables for Linux II

[Ingo Molnar]

* Jörn Engel <joern@wohnheim.fh-wedel.de> wrote:

> > The solution of your typo problem is typechecking in the compiler;
> > presumably it'll warn me if I try to store a pgd3 pointer in a pgd2
> > entry.
> 
> That should help somewhat, agreed.  Patches?

Type-checking of pte/pmd/pgd has been part of the kernel for the past 7
years or so. Andi's patch implements it for pml4's too.

the pt1/pt2/pt3/pt4 distinction makes more sense stylistically, but the
current patch should be engineered for as minimal impact as possible. 
Drastic changes to the MM namespace can be done later (if ever).

	Ingo

4level page tables for Linux

[Andi Kleen]

I released a 4level page table patch for 2.6.9rc4.  It is available
from ftp://ftp.suse.com/pub/people/ak/4level/4level-2.6.9rc4-1.gz

It changes the Linux MM which currently only supports 3 levels of 
page tables to support a fourth level (PML4). This is needed to 
exceed more than 512GB of virtual address space per process on x86-64. 
People have been running into the 512GB limit when mmaping large files.

The patch extends all the code in the VM that walks the 3level
hierarchy to handle the fourth level too.

The patch changes x86-64 to now support 47bits (128TB) of virtual
address space per process. 

The changes are fortunately quite localized. Only mm/* had to change
(mostly in straight forward ways), drivers etc. already were well
isolated from the page tables with the get_user_pages() function.
The only exception was DRM, which needed a small patch.

Excluding the i386/x86-64 architecture specific parts the patch looks like:

 drivers/char/drm/drm_memory.h        |    3 
 fs/exec.c                            |    6 
 include/asm-generic/nopml4-page.h    |   11 
 include/asm-generic/nopml4-pgalloc.h |   21 +
 include/asm-generic/nopml4-pgtable.h |   39 ++
 include/asm-generic/pgtable.h        |    2 
 include/asm-generic/tlb.h            |    6 
 include/linux/init_task.h            |    2 
 include/linux/mm.h                   |   10 
 include/linux/sched.h                |    2 
 kernel/fork.c                        |    6 
 mm/fremap.c                          |   18 -
 mm/memory.c                          |  584 ++++++++++++++++++++++++-----------
 mm/mempolicy.c                       |   18 -
 mm/mmap.c                            |   36 +-
 mm/mprotect.c                        |   44 ++
 mm/mremap.c                          |   21 +
 mm/msync.c                           |   43 ++
 mm/rmap.c                            |   21 +
 mm/swapfile.c                        |   61 ++-
 mm/vmalloc.c                         |   85 ++++-

For architectures with less levels of page tables the code should be mostly a 
nop. 

The patch currently only supports x86-64 and i386. Other architectures
will need some changes to compile. The changes to convert an architecture
over are quite straight forward, please see the changes to i386 in
the patch. I renamed all functions that need changing so things
that are broken will not compile.

I will need some help to do this conversion because I can only test
i386 and x86-64 easily.  I can convert architectures over, but someone
will need to test the result.

Plan is to merge it into -mm* ASAP, when the major architectures

have been ported over.

-Andi

Re: 4level page tables for Linux

[Dave Hansen]

@@ -110,13 +115,18 @@ int install_file_pte(struct mm_struct *m
                unsigned long addr, unsigned long pgoff, pgprot_t prot)
 {
...
+       pml4 = pml4_offset(mm, addr);
+
+       spin_lock(&mm->page_table_lock);
+       pgd = pgd_alloc(mm, pml4, addr);
+       if (!pgd)
+               goto err_unlock;

Locking isn't needed for access to the pml4?  This is a wee bit
different from pgd's and I didn't see any documentation about it
anywhere.  Could be confusing.

+++ linux-2.6.9rc4-4level/mm/memory.c 
...
+#undef inline
+#define inline
+unsigned long caddr;

Is this just for debugging?

+static inline void free_one_pml4(struct mmu_gather *tlb, pml4_t *pml4,
+                                unsigned long addr, unsigned long end)
+{
...
+       do {
+               caddr = addr;
+               free_one_pgd(tlb, pgd);
+               free++;
+               addr = (addr + PGDIR_SIZE) & PGDIR_MASK;
+               pgd++;
+       } while (addr && addr < end);

If someone attempts to clear an address which is in the top PGDIR_SIZE
bytes of memory, this will overflow.  Is that an issue?

There also seems to be quite a bit of churn in the copy_*_range()
functions that isn't completely related to the pml4 changes.  Should
that get broken out?

-- Dave

Re: 4level page tables for Linux

[Andi Kleen]

On Tue, Oct 12, 2004 at 11:48:22AM -0700, Dave Hansen wrote:
> @@ -110,13 +115,18 @@ int install_file_pte(struct mm_struct *m
>                 unsigned long addr, unsigned long pgoff, pgprot_t prot)
>  {
> ...
> +       pml4 = pml4_offset(mm, addr);
> +
> +       spin_lock(&mm->page_table_lock);
> +       pgd = pgd_alloc(mm, pml4, addr);
> +       if (!pgd)
> +               goto err_unlock;
> 
> Locking isn't needed for access to the pml4?  This is a wee bit
> different from pgd's and I didn't see any documentation about it
> anywhere.  Could be confusing.

No, the lock is still needed. Thanks for catching this, that was indeed
wrong.

> 
> +++ linux-2.6.9rc4-4level/mm/memory.c 
> ...
> +#undef inline
> +#define inline
> +unsigned long caddr;
> 
> Is this just for debugging?

Yes, that's a leftover I forgot to remove.  Will go in the next 
version.

(btw t here is another leftover in there, I will remove it too) 

> 
> +static inline void free_one_pml4(struct mmu_gather *tlb, pml4_t *pml4,
> +                                unsigned long addr, unsigned long end)
> +{
> ...
> +       do {
> +               caddr = addr;
> +               free_one_pgd(tlb, pgd);
> +               free++;
> +               addr = (addr + PGDIR_SIZE) & PGDIR_MASK;
> +               pgd++;
> +       } while (addr && addr < end);
> 
> If someone attempts to clear an address which is in the top PGDIR_SIZE
> bytes of memory, this will overflow.  Is that an issue?

That is what the addr && is for. Yes, overflows happen and afaik they
are all handled.

> 
> There also seems to be quite a bit of churn in the copy_*_range()
> functions that isn't completely related to the pml4 changes.  Should
> that get broken out?

It's related. The old function just wasn't scalable to 4 level 
page tables at all (i really tried but it was too ugly) so I rewrote it 
completely. Splitting it would be difficult because the 3level version 
would be already very different from the 4level version.

Thanks for the review.

-Andi

Re: 4level page tables for Linux II

[Andi Kleen]

On Tue, Oct 12, 2004 at 09:03:46PM +0200, Andi Kleen wrote:
> On Tue, Oct 12, 2004 at 11:48:22AM -0700, Dave Hansen wrote:
> > @@ -110,13 +115,18 @@ int install_file_pte(struct mm_struct *m
> >                 unsigned long addr, unsigned long pgoff, pgprot_t prot)
> >  {
> > ...
> > +       pml4 = pml4_offset(mm, addr);
> > +
> > +       spin_lock(&mm->page_table_lock);
> > +       pgd = pgd_alloc(mm, pml4, addr);
> > +       if (!pgd)
> > +               goto err_unlock;
> > 
> > Locking isn't needed for access to the pml4?  This is a wee bit
> > different from pgd's and I didn't see any documentation about it
> > anywhere.  Could be confusing.
> 
> No, the lock is still needed. Thanks for catching this, that was indeed
> wrong.

Actually on second though - the code was actually ok. The reason is 
that the highest page table level never goes away while the process
exists, and holding a pointer into it is always valid. 

Only referencing it needs a lock, but pml4_offset doesn't reference
anything yet.

The same used to hold for pgds, but the 4level page tables change that. 
However there was at least one bug in the patchkit in this area 
which I now fixed.

-Andi