4level page tables for Linux

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

Re: 4level page tables for Linux

[Andrea Arcangeli]

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

btw, locking isn't needed even for the pgd.

fremap.c is the only one that gets it right:

	pgd = pgd_offset(mm, addr);
	spin_lock(&mm->page_table_lock);
	pmd = pmd_alloc(mm, pgd, addr);

the rest is just overkill but it doesn't hurt in practice.

after you add the 4level, locking will become necessary for the pgd, but
it's still not needed for the pml4.

I'm not very excited about changing the naming, of the pgd/pmd/pte so I
like to keep it like it is now.

peraphs we could consider pgd4 instead of pml4. What does "pml" stands
for?

Re: 4level page tables for Linux

[Andi Kleen]

On Wed, 13 Oct 2004 20:41:53 +0200
Andrea Arcangeli <andrea@novell.com> wrote:


> 
> after you add the 4level, locking will become necessary for the pgd, but
> it's still not needed for the pml4.

Yes, agreed. I did an audit of the generic code and it seems to be ok
regarding the pgd use.


> peraphs we could consider pgd4 instead of pml4. What does "pml" stands
> for?

page mapping level 4 (?) just guessing here.

PML4 is the name AMD and Intel use in their documentation. I don't see 
a particular reason to be different from them.

-Andi

Re: 4level page tables for Linux

[Andrea Arcangeli]

On Wed, Oct 13, 2004 at 09:35:58PM +0200, Andi Kleen wrote:
> page mapping level 4 (?) just guessing here.

make sense.

> PML4 is the name AMD and Intel use in their documentation. I don't see 
> a particular reason to be different from them.

just because we never say 'page mapping level 4', we think 'page table
level 4' or 'page directory level 4'.

pte4 doesn't sound nice since we don't use pte3/2/1, but pgd4 could make
some more sense than pml4.

But I'm fine if you prefer to stick with pml4. Those are names we tend
to memorize anyways, I don't actually know what pmd means exactly either
(page middle directory)?

Re: 4level page tables for Linux

[Christoph Lameter]

On Wed, 13 Oct 2004, Andrea Arcangeli wrote:

> On Wed, Oct 13, 2004 at 09:35:58PM +0200, Andi Kleen wrote:
> > page mapping level 4 (?) just guessing here.
>
> make sense.
>
> > PML4 is the name AMD and Intel use in their documentation. I don't see
> > a particular reason to be different from them.
>
> just because we never say 'page mapping level 4', we think 'page table
> level 4' or 'page directory level 4'.

Would it not be best to give up hardcoding these page mapping levels into
the kernel? Linux should support N levels. pml4,pgd,pmd,pte needs to
disappear and be replaced by

pte_path[N]

We are duplicating code for pgd, pmd, pte and now pml again and again. The
code could be much simpler if this would be generalized. Various
architectures would support different levels without some strange
feature like f.e. pmd's being "optimized away".

Certainly the way that pml4 is proposed to be done is less invasive but we
are creating something more and more difficult to maintain.

Re: 4level page tables for Linux

[Andi Kleen]

On Mon, Oct 18, 2004 at 10:02:20AM -0700, Christoph Lameter wrote:
> On Wed, 13 Oct 2004, Andrea Arcangeli wrote:
> 
> > On Wed, Oct 13, 2004 at 09:35:58PM +0200, Andi Kleen wrote:
> > > page mapping level 4 (?) just guessing here.
> >
> > make sense.
> >
> > > PML4 is the name AMD and Intel use in their documentation. I don't see
> > > a particular reason to be different from them.
> >
> > just because we never say 'page mapping level 4', we think 'page table
> > level 4' or 'page directory level 4'.
> 
> Would it not be best to give up hardcoding these page mapping levels into
> the kernel? Linux should support N levels. pml4,pgd,pmd,pte needs to

It already does. Currently it supports 2-3 levels, with my patch
it supports 2-4 levels.

> disappear and be replaced by
> 
> pte_path[N]
> 
> We are duplicating code for pgd, pmd, pte and now pml again and again. The
> code could be much simpler if this would be generalized. Various

For most people it is already generalized (get_user_pages).
The only exception is the core VM and the low level architecture code.
The later will need to deal always with the details.


> architectures would support different levels without some strange
> feature like f.e. pmd's being "optimized away".

Nobody came up with a nice automatic iterator so far.

If you look at the different functions in mm/* who handle all level 
they all do slightly different things so it's not that easy to 
generalize. Also it is not that many, perhaps seven in mm/* plus 
another in the arch code.

> Certainly the way that pml4 is proposed to be done is less invasive but we
> are creating something more and more difficult to maintain.

I don't see us switching to more levels any time soon ...

Also I don't think it's that bad as you're claiming it is. It's a clear
abstraction which has served us well so far.

-Andi

Re: 4level page tables for Linux

[Andrea Arcangeli]

On Mon, Oct 18, 2004 at 10:02:20AM -0700, Christoph Lameter wrote:
> Would it not be best to give up hardcoding these page mapping levels into
> the kernel? Linux should support N levels. pml4,pgd,pmd,pte needs to
> disappear and be replaced by
> 
> pte_path[N]

those aren't the same thing. they may have different
format and different size, plus as Ingo pointed out we use type checking
even when they're the same size. Plus they're already an array. It's not
that simple to remove those duplicate loops, and pte[N] wouldn't mean
the level but the entry offset in the pagetable. Peraphs it's possible
to remove the loops but you'd need at least more runtime branches to
execute in each loop to understand which methods you need to execute
depending on the level you're running on. I certainly don't like the
loops myself so I see your point ;).

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

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

[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 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

[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

[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

[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

[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]

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