Support for Multiple Page Sizes

[Neal H. Walfield]

I'm curious how a memory manager should expose and handle multiple
page sizes.  In particular, I am curious what motivates large pages
and whether the resulting complexity of supporting them is thereby
justified.


Requirements
------------

The system must be reasonable reasonable efficiency, deal with
disruptive interference.  The first requirement precludes static
partitioning.  The second does not allow self-paging for reasons
explained in my last note.  It also requires that all resource be
accounted.  This includes, e.g., PTEs.  Thus, after the various
resource managers start, no further allocations are required on their
part: a principal always pays for all shared resources used on its
behalf.

Based on these requirements, I have tentatively concluded that memory
must be managed centrally and that this resource manager must do its
own paging.


Scenario
--------

Let's imagine that a task allocates a large page, the resource manager
admits this allocation and at some point decides to evict the page.
When the application next requires the page, there are a number of
possibilities:

 - There is sufficient, properly-aligned contiguous memory and
   resource manager is willing to allocate it to the principal

   In this case, the resource manager can just page the data back in
   and continue.

 - There is sufficient memory, however, it is not properly-aligned or
   not contiguous; the resource manager is willing to allocate all of
   it to the principal

   In this case, there are two strategies: defragmentation and
   splitting.

   Defragmentation:

   When the resource manager decides to defragment memory, who should
   pay for it?  The thread that caused the fault could in theory pay,
   however, the fragmentation may be the result of another task's
   usage pattern.  Is it right to penalize the faulting task?

   This approach also introduces two types of quality of service
   cross-talk.  Tasks that use large pages can induce the relocation
   of other tasks' memory.  During the copy, this suspends access to
   the page.  It also induces a page-fault on next access, which must
   be handled by the RM.  Second, tasks that cause physical memory
   fragmentation impact tasks that use large pages as the latter may
   have to defragment memory.

   Splitting:

   It is also possible to simply split the large page into smaller
   pages.  Again, the question is who should pay.  In this case, the
   required resource is primarily memory, e.g., PTEs.  In the case of
   breaking a 4MB page into 4KB pages, an extra 4kb is required.  This
   could be solved by simply including this in the fixed price of
   allocating a single large page.  This would still be cheaper than
   allocating an array of base-page sized pages.

 - And, the resource manager is willing to allocate the task less
   physical memory than is required to hold the entire page

   In this case, the only option to still permit the task to progress
   is splitting.  The same problems apply as above.


Guarded Page Tables
-------------------

To support multiple page sizes ala L4 while correctly accounting all
memory, seL4 has choosen to use a variation of guarded page tables
[1].  Looking up pages in a GPT is relatively straightforward.  I've
thought a bit about modifying a GPT and it appears that it can be
fairly complex and require some shuffling on insert if you don't know
beforehand how the address space will look.


Why Multiple Page Sizes
-----------------------

In Jochen's paper in which he describes guarded page tables he
discusses fitting objects into the minimum number of pages possible.
But is the common usage pattern to really access all bits of an
object?  Today we don't swap tasks; we page them.  The justification
is that only bits and pieces are used and the cost of the additional
faults, memory and TLBs is generally less than the cost of paging the
object as a whole.

An exception to this observation is a rendered image.  In this case,
the image is often either completely or wholly displayed on the screen
(think web browser); the entirety of the object is used at once.

Tentative Conclusion
--------------------

This analysis has led me to the tentative conclusion that for paged
data, the complexity of supporting multiple page-sizes may not be
justified.


Comments?

Thanks,
Neal



[1] Page Table Structures For Fine-Grain Virtual Memory by Jochen
    Liedtke (1994).

    http://citeseer.ist.psu.edu/liedtke94page.html



--