The Maple Tree + Lock Scalability

### Overview This presentation and technical discussion explore memory management (mm) scalability in the Linux kernel, focusing on the bottleneck of `mmap_lock` (formerly `mmap_sem`) and how the Maple Tree data structure combined with lockless techniques can address these challenges. The discussion examines several performance dimensions: CPU cache-line bouncing during concurrent read faults, thread serialization (false conflicts) across large address spaces in multi-threaded processes, and external processes (e.g., monitoring utilities like `ps` via `/proc`) stalling critical server threads.

### Key Topics - **mmap_lock Bottlenecks**: Analysis of cache-line contention, coarse-grained serialization across independent threads, and priority-inversion-like delays caused by external readers. - **The Maple Tree**: Replacement for red-black trees (`rb_tree`), linked lists, and the VMA cache for tracking Virtual Memory Areas (VMAs). Maple Tree simplifies kernel code and provides a top-down B-tree variant designed to support RCU-based lookups. - **Speculative Page Faults (SPF) vs. Maple Tree RCU**: Comparing sequence-count-based whole-`mm_struct` validation (SPF) against VMA-specific RCU lookups and invalidation flags. - **Lockless Read Fault Path**: Challenges of executing `__handle_mm_fault` under an RCU read lock without blocking on sleepable allocations (`gfp_t` flags) or page table reclaim. - **Per-VMA Locking as an Intermediate Step**: Evaluating read/write semaphores per VMA (`vma->vm_lock`) versus full rightless/lockless speculative fault handling.

### Technical Details - **Maple Tree Mechanics**: Maple tree eliminates the doubly linked list and VMA cache. It supports interval ranges and allows top-down splitting and multi-slot insertions or overwrites. - **RCU Page Fault Complications**: A critical hurdle in running page faults under pure RCU is that functions like `p4d_alloc`, `pud_alloc`, and `pmd_alloc` typically allocate memory using `GFP_KERNEL`, which can sleep or invoke direct reclaim. Proposed solutions include falling back to the slow path (re-acquiring `mmap_read_lock`) when intermediate page table levels are absent, or using `GFP_NOWAIT` on the fast path. - **Sleeping and SRCU**: Attendees debated whether Sleepable RCU (SRCU) could enclose the fault handler, noting that current SRCU read-side barriers add overhead, though a fast-reader variant with deferred update costs was proposed. - **VMA Invalidation**: In the proposed Maple Tree RCU model, instead of in-place modifications during resize/split, VMAs would be freed via RCU (`call_rcu`). An `inactive` flag validated under the page table lock (PTL) prevents committing faults to stale VMAs. - **RCU Page Table Freeing**: Ensuring that intermediate page tables and auxiliary structures (such as split page table locks on RT-preempt kernels) are freed asynchronously under RCU protection.

### Takeaways While the first step involves merging the Maple Tree without RCU to clean up mm complexity, moving toward lockless page faults requires careful handling of allocation fallbacks, page table freeing lifetimes, and slab preallocations. The community reached general consensus on considering per-VMA semaphores as a practical stepping stone before pursuing fully lockless fault handlers across giant VMAs.