[Patch 0/17] PTI: Explation of Clean Page Table Interface

[Patch 0/17] PTI: Explation of Clean Page Table Interface

[Paul Cameron Davies]

Linux currently uses the same page table format regardless of
architecture.  Access to the page table is open-coded in a variety of
places.  Architectures that walk a different page table format in
hardware set up a hardware-walkable cache in their native format, that
then has to be kept in step with Linux's page table.

The first step to allowing different page table formats is to split
the page table implementation into separate files from its use.
This patch series abstracts the page table implementation, and cleans
it up, so that:
    1.  All page table operations are in one place, making future
        maintenance easier
    2.  Generic code no longer knows what format the page table is,
        opening the way to experimentation with different
        page table formats.

The interface is separated into two parts.  The first part is
architecture independent. All architectures must run through
this interface regardless of whether or not that architecture
can or will ever want to change page tables.

This patch series provides the architectural independent interface.
It has been tested and benchmarked for IA64 using lmbench.  It also passes
all relevant tests in the Linux Test Project (LTP) on IA64.  This patch
should 5~also compile and run for i386.  To run on other architectures add
CONFIG_DEFAULT_PT to the architectures config.  Turn off HugeTLB.

Summary of performance degradation using lmbench on IA64:
~3.5% deterioration in fork latency on IA64.
~1.0% deterioration in mmap latency on IA64

The interface has been designed in such a way so as to avoid changing
kernel functionality, and causing minimal deterioration in performance.
As a result there are a large number of iterators.  With feedback
from the community it should be possible to patch the kernel to produce a 
general
set of iterators with a few specialised iterators.  (We actually have
a guarded page table running under an interface with general iterators
on an older kernel).

                           BASIC FUNCTIONALITY

This in contained in include/linux/default-pt.h and mm/default-pt.c

/*
  * This is the structure representing the path of the pte in
  * the page table.  For efficiency reasons we store the partial
  * path only
  */
typedef struct pt_struct { pmd_t *pmd; } pt_path_t;

/* Create user page table */
static inline int create_user_page_table(struct mm_struct *mm);

/* Destroy user page table */
static inline void destroy_user_page_table(struct mm_struct *mm);

/* Look up user or kernel page table - saving the path */
static inline pte_t *lookup_page_table(struct mm_struct *mm,
                 unsigned long address, pt_path_t *pt_path);

/* Lookup gate are of page table for fast system calls */
static inline pte_t *lookup_gate_area(struct mm_struct *mm,
                         unsigned long pg);
/* Free page table range */
void free_page_table_range(struct mmu_gather **tlb, unsigned long addr,
         unsigned long end, unsigned long floor, unsigned long ceiling);

/* Provided to keep free_pgtables implementation independent */
static inline void coallesce_vmas(struct vm_area_struct **vma_p,
                 struct vm_area_struct **next_p);

                          PTI WORKER FUNCTIONS
/*
  * Locks the ptes notionally pointed to by the page table path.
  */
#define lock_pte(mm, pt_path)

/*
  * Unlocks the ptes notionally pointed to by the
  * page table path.
  */
#define unlock_pte(mm, pt_path)

/*
  * Looks up a page table from a saved path.  It also
  * locks the page table.
  */
#define lookup_page_table_fast(mm, pt_path, address)

/*
  * Check that the original pte hasn't change.
  */
#define atomic_pte_same(mm, pte, orig_pte, pt_path)

                          THE ITERATORS

Each iterator is passed a function and arguments to operate on
the pte being iterated over.  There are three classes of iterator
for slightly different purposes.

1) Dual iterators - Build a page table while it reads a page table.

Contained in default-pt-dual-iterators.h (included in default-pt.h)

/* For duplicating page table regions for fork and mmap */
static inline int copy_dual_iterator(struct mm_struct *dst_mm,
         struct mm_struct *src_mm, unsigned long addr, unsigned long end,
         struct vm_area_struct *vma, pte_rw_iterator_callback_t func);

/* For mremap sys call - source and destination page table is the same
    for this dual iterator */
static inline unsigned long move_page_tables(struct vm_area_struct *vma,
         unsigned long old_addr, struct vm_area_struct *new_vma,
         unsigned long new_addr, unsigned long len, mremap_callback_t 
func);

2) Build iterators - build a page table between a range of addresses.

Contained in default-pt-build-iterators.h (included in default-pt.h)

static inline int vmap_pte_range(pmd_t *pmd, unsigned long addr,
         unsigned long end, pgprot_t prot, struct page ***pages,
         vmap_callback_t func)

static inline int zeromap_build_iterator(struct mm_struct *mm,
         unsigned long addr, unsigned long end,
         pgprot_t prot, zeromap_callback_t func);

static inline int remap_build_iterator(struct mm_struct *mm,
         unsigned long addr, unsigned long end, unsigned long pfn,
         pgprot_t prot, remap_pfn_callback_t func);

3) Read iterators - read a page table between a range of addresses.

Contained in default-pt-read-iterators.h (included in default-pt.h).

static inline unsigned long unmap_page_range_iterator(struct mmu_gather 
*tlb,
         struct vm_area_struct *vma, unsigned long addr, unsigned long end,
         long *zap_work, struct zap_details *details, zap_pte_callback_t 
func);

static inline void vunmap_read_iterator(unsigned long addr,
         unsigned long end, vunmap_callback_t func);

static inline unsigned long msync_read_iterator(struct vm_area_struct 
*vma,
         unsigned long addr, unsigned long end, msync_callback_t func);

static inline void change_protection_read_iterator(struct vm_area_struct 
*vma,
         unsigned long addr, unsigned long end, pgprot_t newprot,
         change_prot_callback_t func);

static inline int unuse_vma_read_iterator(struct vm_area_struct *vma,
         unsigned long addr, unsigned long end, swp_entry_t entry,
         struct page *page, unuse_pte_callback_t func);

static inline int check_policy_read_iterator(struct vm_area_struct *vma,
         unsigned long addr, unsigned long end, const nodemask_t *nodes,
         unsigned long flags, void *private, mempolicy_check_pte_t func);

static inline void smaps_read_iterator(struct vm_area_struct *vma,
         unsigned long addr, unsigned long end,
         struct mem_size_stats *mss, smaps_pte_callback_t func);

I am keen to hear from anyone planning to put a
new page table implementation into the kernel. Is there
anything in my patch that could be changed to better
accommodate you?

Results and progress will be documented on the Gelato@UNSW wiki in the 
very near future.

http://www.gelato.unsw.edu.au/IA64wiki/PageTableInterface

Paul Davies on behalf of Gelato@UNSW.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Jes Sorensen]

>>>>> "Paul" == Paul Cameron Davies <pauld@cse.unsw.EDU.AU> writes:

Paul> This patch series provides the architectural independent
Paul> interface.  It has been tested and benchmarked for IA64 using
Paul> lmbench.  It also passes all relevant tests in the Linux Test
Paul> Project (LTP) on IA64.  This patch should 5~also compile and run
Paul> for i386.  To run on other architectures add CONFIG_DEFAULT_PT
Paul> to the architectures config.  Turn off HugeTLB.

Paul> Summary of performance degradation using lmbench on IA64: ~3.5%
Paul> deterioration in fork latency on IA64.  ~1.0% deterioration in
Paul> mmap latency on IA64

Paul,

Let me just get it right as I am not sure I am reading it correctly.
Are you saying that this patch causes a 3.5% fork performance
degradation on ia64 or are you saying it is improving 3.5%?

Thanks,
Jes

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Peter Chubb]

>>>>> "Jes" == Jes Sorensen <jes@sgi.com> writes:

>>>>> "Paul" == Paul Cameron Davies <pauld@cse.unsw.EDU.AU> writes:
Paul> This patch series provides the architectural independent
Paul> interface.  It has been tested and benchmarked for IA64 using
Paul> lmbench.  It also passes all relevant tests in the Linux Test
Paul> Project (LTP) on IA64.  This patch should 5~also compile and run
Paul> for i386.  To run on other architectures add CONFIG_DEFAULT_PT
Paul> to the architectures config.  Turn off HugeTLB.

Paul> Summary of performance degradation using lmbench on IA64: ~3.5%
Paul> deterioration in fork latency on IA64.  ~1.0% deterioration in
Paul> mmap latency on IA64

Jes> Paul,

Jes> Let me just get it right as I am not sure I am reading it
Jes> correctly.  Are you saying that this patch causes a 3.5% fork
Jes> performance degradation on ia64 or are you saying it is improving
Jes> 3.5%?

I believe that yes, there is currently a small performance degradation
on IA64.  I think we'll get that back when we put a more appropriate
page table under the interface.  And this is the first cut, and can be
made more efficient anyway.

I'm not sure whether Paul's benchmarked yet on x86, but that's the
critical place where performance matters for this interface, because
x86 will use the same page table (under the interface) as at
present.

-- 
Dr Peter Chubb  http://www.gelato.unsw.edu.au  peterc AT gelato.unsw.edu.au
http://www.ertos.nicta.com.au           ERTOS within National ICT Australia

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Paul Cameron Davies]

Hi Jes

It is currently causing a degradation, but we are in the process
of performance tuning.

There is a small cost associated with the PTI at the moment.

Cheers

Paul

On Tue, 30 May 2006, Jes Sorensen wrote:

>>>>>> "Paul" == Paul Cameron Davies <pauld@cse.unsw.EDU.AU> writes:
>
> Paul> This patch series provides the architectural independent
> Paul> interface.  It has been tested and benchmarked for IA64 using
> Paul> lmbench.  It also passes all relevant tests in the Linux Test
> Paul> Project (LTP) on IA64.  This patch should 5~also compile and run
> Paul> for i386.  To run on other architectures add CONFIG_DEFAULT_PT
> Paul> to the architectures config.  Turn off HugeTLB.
>
> Paul> Summary of performance degradation using lmbench on IA64: ~3.5%
> Paul> deterioration in fork latency on IA64.  ~1.0% deterioration in
> Paul> mmap latency on IA64
>
> Paul,
>
> Let me just get it right as I am not sure I am reading it correctly.
> Are you saying that this patch causes a 3.5% fork performance
> degradation on ia64 or are you saying it is improving 3.5%?
>
> Thanks,
> Jes
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Jes Sorensen]

Paul Cameron Davies wrote:
> Hi Jes
> 
> It is currently causing a degradation, but we are in the process
> of performance tuning.
> 
> There is a small cost associated with the PTI at the moment.

Hi Paul,

Bugger! I was hoping it was the other way round :( 3.5% falls into the
bucket of pretty expensive in my book, so I'll cross my fingers that
you nail the source of it.

Cheers,
Jes

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Paul Cameron Davies]

Hi Jes

I concede that I am acutely aware that 3.5% is just too high,  but we know 
which abstractions are causing the problems.

We will hope to nail down some of these problems in the next few weeks
and then feed again.

What level of degradation in peformance in acceptable (if any)?


Cheers

Paul Davies

On Tue, 30 May 2006, Jes Sorensen wrote:

> Paul Cameron Davies wrote:
>> Hi Jes
>>
>> It is currently causing a degradation, but we are in the process
>> of performance tuning.
>>
>> There is a small cost associated with the PTI at the moment.
>
> Hi Paul,
>
> Bugger! I was hoping it was the other way round :( 3.5% falls into the
> bucket of pretty expensive in my book, so I'll cross my fingers that
> you nail the source of it.
>
> Cheers,
> Jes
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Nick Piggin]

Paul Cameron Davies wrote:

> Hi Jes
>
> I concede that I am acutely aware that 3.5% is just too high,  but we 
> know which abstractions are causing the problems.
>
> We will hope to nail down some of these problems in the next few weeks
> and then feed again.
>
> What level of degradation in peformance in acceptable (if any)?


For upstream inclusion? negative degradation, I'd assume: you're adding
significant complexity so there has to be some justification for it...

And unless it is something pretty significant, I'd almost bet that Linus,
if nobody else, will veto it. Our radix-tree v->p data structure is
fairly clean, performant, etc. It matches the logical->physical radix
tree data structure we use for pagecache as well.

BTW. I reckon your performance problems are due to indirect function
calls.

Nick

--

Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Hugh Dickins]

On Wed, 31 May 2006, Paul Cameron Davies wrote:
> 
> What level of degradation in peformance in acceptable (if any)?

None.  What is the point in slowing it down, even on the architecture
you are targeting, while making it all more complicated, moving
significant code around from the .cs where we expect it into .hs?

And please, next time, make sure the patches can actually be applied:
your mailer (pine) messed with the whitespace - quell-flowed-text is,
I think, the feature you need to add, but mail yourself the patches
first as a test to make sure they can be applied by recipients.

Hugh

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Paul Cameron Davies]

On Wed, 31 May 2006, Nick Piggin wrote:

> Paul Cameron Davies wrote:
>
>> Hi Jes
>> 
>> I concede that I am acutely aware that 3.5% is just too high,  but we know 
>> which abstractions are causing the problems.
>> 
>> We will hope to nail down some of these problems in the next few weeks
>> and then feed again.
>> 
>> What level of degradation in peformance in acceptable (if any)?
>
>
> For upstream inclusion? negative degradation, I'd assume: you're adding
> significant complexity so there has to be some justification for it...

Our long term goal is upstream inclusion.  We are planning to release
early and release often to get feedback and exposure.  We want to bring
around the people that don't have a vested interest in cleanly accessing
the page tables, and get early input into the direction the interface
should take.

> And unless it is something pretty significant, I'd almost bet that Linus,
> if nobody else, will veto it. Our radix-tree v->p data structure is
> fairly clean, performant, etc. It matches the logical->physical radix
> tree data structure we use for pagecache as well.

Being able to change the page table on a 64 bit machine will
be a huge advantage into the future when applications really start to
make use of the 64 bit address space.  The current trie (multi level
page table - MLPT) is not going to perform against more
sophisticated data structures in a sparsely occupied 64 bit address space
At UNSW we are experimenting with different page tables.  We have
replaced the MLPT in Linux with a GPT (guarded page table), running
on an older kernel. The GPT is essentially an unconstrained radix tree (a
specialed MLPT).

GPTs are naturally suited to page table sharing and the seamless
implementation of Superpages. (please refer to Liedtke's paper,
Address Space Sparsity and fine granularity, ACM Operating Systems
Review, vol 29, pp87-90, January 1995).

We are looking to provide alternate page table options in Linux
to enable Linux to continue to boast about its scalability
as an operating system.  The MLPT is not going to scale from the 32
bit address space to the 64 bit address space.  Unfortunately
some concession may need to be made by some architectures to support this.

> BTW. I reckon your performance problems are due to indirect function
> calls.
Thanks.  This is certainly a large part of the performance problem.
The problem is, thus far it is the most efficient solution I have come up
with.

Cheers

Paul

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Paul Cameron Davies]

On Wed, 31 May 2006, Hugh Dickins wrote:

> On Wed, 31 May 2006, Paul Cameron Davies wrote:
>>
>> What level of degradation in peformance in acceptable (if any)?
>
> None.  What is the point in slowing it down, even on the architecture
> you are targeting, while making it all more complicated, moving
> significant code around from the .cs where we expect it into .hs?

The PTI (page table interface) will give a small performance hit,
but we believe that when the MLPT is replaced with some other
implementation, for example the GPT (guarded page table), that
a better overall performance will be achieved.

In particular, this will be true for apps with large memory
requirements on 64-bit architectures.

We have access to some papers discussing the problems that will
occur when large memory spaces are more commonly used, but
unfortunately there is no URL to directly access them.
We do have a paper that discusses variable radix page tables
(which is a GPT by another name) found here:

www.ertos.nicta.com.au/publications/papers/Szmajda_Heiser_03.pdf

As a pragmatist, I agree that it is of real concern that the
page table interface would slow down commonly-used architectures.
However, current performance depends on the kernel being
organised to suit the MLPT implementation. That is likely to
prevent efficient use of large memory spaces in the future.

Directly accessing the VM data structure works well at the moment.
In the near future, it is likely that many systems will want to
work with large amounts of memory, and the optimisations that
work well now will not work well with those systems.

> And please, next time, make sure the patches can actually be applied:
> your mailer (pine) messed with the whitespace - quell-flowed-text is,
> I think, the feature you need to add, but mail yourself the patches
> first as a test to make sure they can be applied by recipients.
Sorry, thanks for the tip.

Cheers

Paul

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [Patch 0/17] PTI: Explation of Clean Page Table Interface

[Nick Piggin]

Paul Cameron Davies wrote:
> On Wed, 31 May 2006, Nick Piggin wrote:

>> And unless it is something pretty significant, I'd almost bet that Linus,
>> if nobody else, will veto it. Our radix-tree v->p data structure is
>> fairly clean, performant, etc. It matches the logical->physical radix
>> tree data structure we use for pagecache as well.
> 
> 
> Being able to change the page table on a 64 bit machine will
> be a huge advantage into the future when applications really start to
> make use of the 64 bit address space.  The current trie (multi level
> page table - MLPT) is not going to perform against more
> sophisticated data structures in a sparsely occupied 64 bit address space

OK, this is what I mean by better performing. It does not have to
have *zero* performance regressions across the board, but simply
something that tips the cost/benefit.

That does imply that the framework itself would never get included,
without something behind it that does perform better. Which I assume
is your plan.


The release early approach is a good one, so continue to post code
and/or results on linux-mm. I do happen to think you'll have a pretty
hard time getting this in at all, but good luck to you ;)

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>