Swap abstraction

This talk addresses critical issues in Linux kernel swap memory management, focusing on data structure design and fragmentation problems introduced by Multi-Order Thrift Pages (MTP). The speaker reviews current swap internals—offset-keyed data structures that are heavily space-optimized but difficult to maintain—and questions whether a major rewrite should prioritize cleaner code or measurable performance gains. A key insight emerges: on systems with minimal swap usage, pre-allocation of swap structures is wasteful, while at massive scale (Google fleet), small per-entry memory overhead accumulates significantly.

The core technical problem centers on MTP fragmentation. When MTP are merged into the memory management system, measurements show a 19% compression improvement and 2.7x CPU time savings for decompression with 64k MTP using Z-swap. However, this introduces severe fragmentation: allocation failure rates jump from 14% initially to 90% within 5 hours during normal workload switching, despite less than 50% of swap space being consumed. The root cause is that small MTP allocations create partially-used clusters that pollute the swap space but aren't considered candidates for further large MTP allocation, rendering swap unusable despite available space.

The speaker proposes a multi-phase solution. Short-term: implement cluster allocation ordering to prevent mixing different-sized MTP within the same cluster, maintaining separate tracking for empty and half-full clusters. This is relatively simple to implement if, as one questioner suggests, the ratio between MTP sizes remains stable. Long-term: develop a buddy allocator for swap entries using a sliding-window approach to scan and maintain allocation lists without pre-allocating metadata for the entire swap space.

Most ambitiously, the proposal introduces compound swap entries—allowing one swap entry to represent multiple consecutive or non-contiguous slots without duplicating metadata (counters, cgroups, etc.). This reduces memory overhead while enabling flexible granularity: the allocator can make swap-out decisions independently of swap-in decisions, splitting large folios on write if necessary and reassembling during reads. The design costs 4 extra bytes per entry upfront but saves memory through reduced duplication when using compound entries.

The design is contentious. Audience members, particularly Matthew, argue the speaker is reinventing filesystems without filesystem expertise and should consult filesystem developers. The speaker counters that concrete memory overhead calculations (4 bytes per entry) and simpler implementation make this approach viable compared to full filesystem solutions. Disagreement exists on whether non-contiguous folio support is necessary; one questioner suggests splitting folios on allocation failure rather than maintaining complex non-contiguous metadata, which the speaker acknowledges but argues his design decouples swapping strategy from granularity—a desired capability.

Emergent hardware constraints receive attention: future storage devices may mandate 16k minimum write alignment, implying a 4k folio would necessarily batch with three additional pages. Discussion suggests this could be addressed by batching pages from the LRU list, simplifying some complexity if properly ordered. The speaker notes this reinforces the case for decoupling memory management from swap cache details.

Final tension: the speaker proposes compound entries with potentially non-contiguous backing, while acknowledging this is invasive to swap backend code. Audience feedback emphasizes the need for a complete filesystem-oriented reference design for comparison. The speaker defends the incremental proposal as measurable and implementable while remaining open to exploring formal filesystem approaches once fully specified. No decision is reached; the session ends with agreement that future work should account for hardware alignment requirements and that gathering concrete fragmentation statistics under realistic workloads (rather than theoretical worst-cases) is essential before committing to complex solutions.