How to design a general and transparent superpage management system to achieve high and sustained performance for real workloads and negligible degradation in pathological situations?
Superpage definition and benefits
- Memory pages of larger sizes (e.g., 8KB, 64KB, 512KB, 4MB)
The rest is the same as the normal pages:
- power of 2 size
- use only one TLB entry
- aligned (physically and virtually)
- uniform protection attributes
- one reference bit, one dirty bit
Superpage improves TLB coverage (i.e., the amount of memory accessible through cached mappings. In other words, without incurrin misses in the TLB)
- Allocation: how/when/what size to allocate?
Promotion (create a superpage out of a set of smaller pages)
- Wait for app to touch pages (the gray ones) may lose opportunities to increase TLB coverage
- Create small superpage (the first four blue ones) may waste overhead
- Forcibly populate pages (i.e., group all eight base pages into one superpage) may lead to internal fragmentation
Demotion (convert a superpage into smaller pages). Happens when:
- page attributes of base pages of a superpage become non-uniform (e.g., some of the base pages protection attributes changed and different from the rest within the superpage)
- during partial pageouts
Memory becomes fragmentated due to:
- use of multiple page sizes
- persistence of file cache pages
- scattered wired (non-pageable) pages
Continuity: contended resource
- OS must trade off impact of contiguity restoration against superpage benefits
- Determines a preferred superpage size for the region encompassing the base page whose access caused the page fault
- The entire set of frames (gray ones above) is tentatively reserved for potential future use as a superpage, and added to a reservation list.
memory objects fixed in size (e.g., code, file): largest, aligned superpage (contains the faulting page) + doesn't overlap with existing reservations or allocated pages + no larger than object
memory objects with dynamic size (e.g., heap): everything same as above except not restricting no larger than object
- If size is not available, preempt existing reservation or resign to a smaller size
preemption policy: the reservation is preempted whose most recent page allocation occured least recently, among all candidate reservations.
Use reservation list:
- keep track of reserved page frame extents that are not fully-populated
- One reservation list for each page size supported by the hardware except for the largest superpage size
- Reservation in each list are kept sorted by the time of their most recent page frame allocations. When the system decides to preempt a reservation of a given size, it chooses the reservation at the head of the list for that size.
Promote only regions that are fully populated by the application
Promotion occurs to the smallest superpage size as soon as the population count corresponds to that size. Then, when the population count reaches the enxt larger superpage size, another promotion occurs to the next size, and so on.
- One reference bit per superpage: how do we detect portions of a superpage not referenced anymore?
- Solution: On memory pressure, demote superpages when resetting reference bit; Re-promote (incrementally) as pages are referenced
Low contiguity: modified page daemon
- restore contiguity: move clean, inactive pages to the free list
- minimize impact: prefer pages that contribute the most to contiguity; keep contents for as long as possible (even when part of a reservation: if reactivated, break reservation)
Cluster wired pages
Auxiliary data structure: population map
Population maps keep track of allocated base pages within each memory object.
- Reserved frame lookup
- Overlap avoidance
- Promotion decisions
- Preemption assitance
Implemented as a radix tree. Details see paper
- Another well-written paper. I think it is a good candidate for a self-learning project (i.e., implementing superpage management system on JOS)