A guarded page table (GPT) for Linux
This project is dealing with developing a GPT (a specific instance of the more general multi-level page table (MLPT) for Linux. The aim of the work is to provide an alternative page table implementation for Linux systems using the related PageTableInterface project for Linux.
If you have any queries regarding the work please contact AdamWiggins
What is a GPT?
A guarded page table can be thought of as a standard multi-level or hierarchical page table with an additional technique known as /PathCompression applied to it. More specifically a GPT is a page table structure based on a path-compressed Trie. Other compression techniques can also be applied to tries and in this work we will also explore the use of /LevelCompression. For more information regarding the mechanisms the GPT provides and how these compare to the standard Linux page table see /MechanismsAndTradeoffs.
Design issues
A collection of notes regarding the design issues facing the GPT in Linux:
Supported architectures
The GPTs main target is 64-bit systems where standard MLPTs can lead to excessive page table memory usage and potentially deeper page table structures (more expensive lookup). For architectures where the page table is software walked the GPT can be a drop in replacement, for hardware walked architectures the GPT can either be the primary Linux page table, with the hardware walked format used as a cache or software TLB or an alternative page table implementation used, such as the default MLPT of the PageTableInterface.
Target architectures
/IA64 - This is the primary target architecture. The GPT is either software walked with the hardware walker disabled, or the hardware walker is used as a software TLB.
- In general we couldn't use the short VHTP format as it requires the bottom levels to be mapped into a virtual linear array with the pte payload only (no guard, etc).
- We could use the short format VHPT iff it was simply a cache of the GPT, though it isn't clear if this would actually gain anything over the long format VHPT.
PowerPC - Another arch that uses the hardware walked page table format as a software TLB and the GPT is suitable for.
SPARCv9 - 64Bit SPARC is software walked so a GPT should work fine.
i386 - GPT doesn't really make sense in these architectures as the GPTs aim is to reduce memory and cache footprint which would would be lost to the hardware imposed MLPT. Might be an option as a software TLB particularly if Linux VM sub-system could detect sharing of page tables and this was exploited by both the GPT and the hardware format.
ARM - Similar deal to i386. Though using the hardware page table as a cache in combination with FASS could reduce memory usage as a large page directory would no longer be needed per address-space.
Alpha - PALCode enforces the page table format, similar to a hardware walked page table so the default MLPT is probably more suitable then the GPT.
- x86-64 - Not sure what the details are here, probably similar to i386, just more levels.
- Others?
Encoding entries
NOTE: This is a brain dump which needs to be cleaned up and organised - AdamWiggins.
- For synchronisation we need get/set functions to load and store entries to/from the page table and functions to manipulate copies of the entry.
There are four GPT entry types (Add a diagram - AdamWiggins):
- Invalid - No mapping for this region, terminal.
- Leaf - Mapping for this region, terminal.
Shared - Intermediate node, points to another level, which may be shared. NOTE: Shared sub-trees are future work.
- Internal - Intermediate node, points to another level.
- Invalid nodes only have a type, the rest of the entry is unused.
- All nodes are the same size, allowing mixed node types in the same level of the GPT.
- Leaf nodes contain a guard, coverage (superpage size), and payload (physical addr, access rights, attributes, etc).
- Internal nodes contain a guard, pointer to the next level and the next level's size.
To improve the performance of determining when to restructure, valid and full counts for levels should be stored in their internal nodes, see my thesis notes - AdamWiggins.
- Shared nodes require all the fields of internal nodes, plus a reference count and access rights.
Related work
The work has grown out of the earlier work towards VariableRadixPageTables for Linux.
