How would RMAP be implemented without RMAP metadata?#

So the question arises: how do we know which virtual memory maps this page? Without any auxiliary data structure, the only option is to scan all tasks’ mappings to find the PTE access state (Accessed bit) corresponding to the target page/folio, and reclaim the page/folio to swap when no task maps it.

This brings two problems:

• The cost is proportional to the “total number of PTEs in the system,” not to the “number of pages that need to be reclaimed.” Scanning large numbers of page tables that map hot pages is pure waste.
• A page shared by multiple processes can only truly be reclaimed after all of its mappings have been torn down in their respective scans. The kernel cannot proactively pick a page and tear down all of its mappings at once, and the Accessed bit (page hotness) is scattered across various page tables and cannot be aggregated for a single page.

Take reclaim before Linux v2.4 as an example. swap_out() would start walking from init_mm, linearly scanning its page tables to see which PTE points to a page whose mapping can be torn down.

per-page RMAP (pte_chain)#

Since the problem is “there is no way to find all the PTEs mapped to a page from the page itself,” the simplest approach is to record all the corresponding PTEs directly on the page. With this in mind, Rik van Riel proposed RMAP in 2.4.17-rmap-12e. The concrete implementation adds a pte_chain field to the struct page data structure, pointing to a linked list that chains together the addresses of all corresponding PTEs. During reclaim, one only needs to walk this linked list and check the Accessed bit, instead of walking every PTE in the entire system as before. The patch was merged into mainline in 2.5.27.

1
#define NRPTE ((L1_CACHE_BYTES - sizeof(unsigned long))/sizeof(pte_addr_t))
2

3
// NRPTE = 7 when L1_CACHE_BYTES = 64
4
// 3 when L1_CACHE_BYTES = 32
5

6
struct page {
7
 ...
8
 struct pte_chain *pte_chain; /* points to all PTEs mapping this page */
9
 ...
10
};
11

12
struct pte_chain {
13
 unsigned long next_and_idx;
14
 pte_addr_t ptes[NRPTE];
15
} ____cacheline_aligned;
16

17
pte_chain_encode(pte_chain, idx): return (unsigned long)pte_chain | idx;
18
pte_chain_next(pc): return (struct pte_chain *)(pc->next_and_idx & ~NRPTE);
19
pte_chain_idx(pc): return pc->next_and_idx & NRPTE;
20

21
page_add_rmap(page, ptep);
22
page_remove_rmap(page, ptep);

In the pte_chain era there was no VMA-level insertion or removal at all. The unit of record was the PTE.

1
page_add_rmap(page, ptep); /* on page fault, link the pte address onto the page */
2
page_remove_rmap(page, ptep); /* on unmap, linearly scan to find and remove it */

fork(): copy_page_range() walks the PTEs one by one, calling page_add_rmap() once for each mapped page. Cost is O(number of pages), and memory is O(number of mappings). munmap() / exit(): zap_pte_range() calls page_remove_rmap() one by one, and removal requires a linear scan of the pte_chain to find the matching entry.

From per-page to per-object RMAP (anon_vma)#

However, this design still had problems. As the number of sharing tasks grows, the length of the pte_chain linked list grows too, and the time complexity of the whole walk is O(N)\text{, where N is the length of the pte_chain linked list}. In addition, the memory overhead brought by pte_chain is proportional to the system’s own memory size. Since pte_chain requires at least 12 extra bytes, even on a 32-bit system with just 128MB of RAM, the memory overhead of pte_chain amounts to 400KB.

Given the memory overhead of pte_chain, community acceptance was low, and the community began discussing how to eliminate the pte_chain memory overhead. For file-backed pages, the PTEs in use can be found in reverse via address->i_mmap; anon pages, however, had no similar data structure — hence anon_vma was born.

In 2.6.7, RMAP changed from the original per-page pte_chain chaining to having anon and file-backed pages share the mapping field, where file-backed pages store an address_space and anon pages store an anon_vma, using the LSB of the pointer to determine which is actually stored.

1
struct page {
2
 ...
3
 struct address_space *mapping;
4
 ...
5
};

anon_vma uses a linked list to chain together the VMAs that belong to it, and multiple pages map to the same anon_vma. On unmap, the page offset is computed from page->index, then each VMA in the anon_vma is walked; the page offset is added to the VMA’s start address to determine whether the VMA is related to the page, and to find the corresponding PTE.

1
struct anon_vma {
2
 spinlock_t lock;
3
 struct list_head head; /* chains vma->anon_vma_node */
4
};

• Insertion (page fault): anon_vma_prepare(vma). First, find_mergeable_anon_vma() attempts to reuse the anon_vma of an adjacent mergeable VMA; only if none is found is a new one allocated, and finally list_add(&vma->anon_vma_node, &anon_vma->head).
• Insertion (fork): anon_vma_link(vma). The child process directly reuses the parent’s anon_vma, hanging its own node onto the same list.
• Insertion (VMA split): the new VMA produced by split_vma() shares the same anon_vma, likewise via anon_vma_link().
• Removal: anon_vma_unlink(vma) — after list_del(), check whether the list is empty; if so, free the anon_vma.

From anon_vma to anon_vma_chain#

The anon_vma introduced in 2004 solved the memory overhead of pte_chain, but its handling of fork() was too crude: a child process’s VMA was hung directly onto the parent’s anon_vma, so the entire process family shared a single anon_vma.

Before object rmap was merged in 2003, Andrew Morton raised concerns about this mechanism. The object rmap design walks all VMAs associated with an entire object (such as an anon_vma or address_space), which inevitably visits VMAs completely unrelated to the page being reclaimed, spending a large amount of time on the walk. In contrast, pte_chain only needs to walk the PTEs relevant to the page. He also illustrated the problem with an extreme case: with 1000 tasks using the same file, where each task has 1000 VMAs on that file, there are 1 million VMAs in total, and on unmap all 1 million VMAs must be walked no matter what. Although he only mentioned file-backed pages, since this is a problem of the design itself, anon pages could suffer the same problem.

Notably, Andrew himself at the time leaned toward this being merely “theoretically possible” and not a big deal — after all, the 2.4 virtual scan design had the same problem and nobody had hit it. Seven years later, however, what Andrew Morton worried about did happen.

Without the anon_vma changes, when AIM7 hits around 9.7k users (on a test box with 16GB RAM and not quite enough IO), the system ends up running >99% in system time, with every CPU on the same anon_vma lock in the pageout code.

Rik van Riel found that the AIM7 benchmark seized up when the user count reached 9.7k, with most of the time spent contending for the anon_vma lock — confirming the walking-time problem described above.

In response, Rik van Riel proposed a patch addressing this. The concrete idea is to create an anon_vma per process and use the anon_vma_chain data structure to link anon_vmas and VMAs, then use same_vma and same_anon_vma to chain together the AVCs that map to the same “vma or anon_vma,” forming a many-to-many association.

After applying this patch, AIM7 only began to seize up at 29.7k users, and the bottleneck shifted to I/O wait.

1
struct anon_vma_chain {
2
 struct vm_area_struct *vma;
3
 struct anon_vma *anon_vma;
4
 struct list_head same_vma; // all avcs that linked by same vma
5
 struct list_head same_anon_vma; // all avcs that linked by same anon_vma
6
};

Corresponding kernel commit/patch:

• 5beb49305251 (mm: change anon_vma linking to fix multi-process server scalability issue).

anon_vma_chain interval tree#

The same_anon_vma linked list was replaced with an interval tree (implemented as an augmented rbtree), keyed by the interval [\text{vm_pgoff}, \text{vm_pgoff} + \text{vma_pages}) covered by each VMA. The RMAP walk becomes a stabbing query on the target pgoff, returning only the VMAs whose interval actually covers that pgoff, with complexity O(log n + number of hits). In the same merge window, the long-standing prio_tree on the file-backed side was also replaced by the same interval tree (6b2dbba8b6ac); anon and file reverse walks have shared the same index structure ever since — which is where today’s anon_vma_interval_tree_foreach() and vma_interval_tree_foreach() macros come from.

1
struct anon_vma_chain {
2
 struct vm_area_struct *vma;
3
 struct anon_vma *anon_vma;
4
 struct list_head same_vma; /* locked by mmap_lock & page_table_lock */
5
 struct rb_node rb; /* locked by anon_vma->rwsem */
6
 unsigned long rb_subtree_last;
7
#ifdef CONFIG_DEBUG_VM_RB
8
 unsigned long cached_vma_start, cached_vma_last;
9
#endif
10
};

During an RMAP walk, the anon_vma is first obtained from page->mapping, then the anon_vma_chain interval tree is walked continuously from anon_vma->rb_root, checking each corresponding VMA’s vm_start and vm_end to determine whether the PTE corresponding to that VMA maps this page.

Corresponding kernel commit:

• bf181b9f9d8d (mm anon rmap: replace same_anon_vma linked list with an interval tree)

Observing How the Active/Inactive Lists Use RMAP#

Access detection in the traditional Active/Inactive lists is built entirely on RMAP. The kernel cannot be notified at the moment the hardware sets the Accessed bit; it can only poll after the fact: folio_referenced() performs one RMAP walk over the folio, checking and clearing the Accessed bit of every mapping PTE one by one, returning “how many VMAs have accessed it since the last check.”

Concretely, two paths perform RMAP walks:

1. Demotion: check whether the folio at the tail of the Active LRU list has been accessed; if not, move it to the inactive list.
2. Eviction: check whether the folio at the tail of the Inactive LRU list has been accessed; if not, drop the folio; otherwise move it back to the Inactive list.

Taking kswapd as an example, its call path into RMAP is:

1
kswapd -> balance_pgdat -> shrink_node -> shrink_lruvec
2
 ├── shrink_active_list
3
 │ └── folio_referenced -> __rmap_walk_file
4
 │ ├── folio_referenced_one -> page_vma_mapped_walk
5
 │ └── vma_interval_tree_iter_first
6
 └── shrink_folio_list
7
 ├── folio_referenced -> __rmap_walk_file -> folio_referenced_one
8
 │ └── page_vma_mapped_walk
9
 └── try_to_unmap -> __rmap_walk_file -> try_to_unmap_one
10
 └── set_tlb_ubc_flush_pending

How MGLRU Reduces RMAP Overhead#

Architectural Improvements#

First, at the architectural level, the Active/Inactive lists must operate on both the active and inactive LRU lists during eviction, whereas MGLRU — thanks to the natural aging property of its generations — only needs to operate on the oldest generation (min_seq) during eviction.

1
kswapd -> balance_pgdat -> kswapd_shrink_node -> shrink_node
2
└── lru_gen_shrink_node
3
 └── shrink_one (global) / shrink_many -> shrink_one (memcg)
4
 └── try_to_shrink_lruvec -> evict_folios
5
 └── shrink_folio_list
6
 ├── folio_check_references -> folio_referenced
7
 │ └── rmap_walk -> rmap_walk_anon / rmap_walk_file
8
 │ └── folio_referenced_one
9
 │ └── page_vma_mapped_walk # all fixed costs are paid in full before this point
10
 │ └── lru_gen_look_around # a 64-PTE window with near-zero marginal cost
11
 │ ├── get_pte_pfn / get_pfn_folio
12
 │ ├── walk_update_folio # promote neighbors in place
13
 │ └── update_bloom_filter # feed back to aging
14
 └── try_to_unmap -> rmap_walk -> try_to_unmap_one

Next, consider the cost structure of an RMAP walk. To check the Accessed bit of a single PTE, folio_referenced() must always pay: acquiring the VMA object lock, walking the interval tree, page_vma_mapped_walk() descending the page table level by level to locate the PTE, and acquiring the page table lock (PTL). Meanwhile, the LRU is organized by physical pages, and adjacent folios on the list come from different VMAs of different processes. Thus every walk is a set of lock and tree operations with zero cache reuse. High fixed cost, and none of it amortized — this is why page_vma_mapped_walk eats 18.47% of kswapd’s CPU.

1
 patch1-6
2
 39.03% lzo1x_1_do_compress (real work)
3
 18.47% page_vma_mapped_walk (overhead)
4
 6.74% _raw_spin_unlock_irq
5
 3.97% do_raw_spin_lock
6
 2.49% ptep_clear_flush
7
 2.48% anon_vma_interval_tree_iter_first
8
 1.92% folio_referenced_one
9
 1.88% __zram_bvec_write
10
 1.48% memmove
11
 1.31% vma_interval_tree_iter_next
12

13
 patch1-7
14
 48.16% lzo1x_1_do_compress (real work)
15
 8.20% page_vma_mapped_walk (overhead)
16
 7.06% _raw_spin_unlock_irq
17
 2.92% ptep_clear_flush
18
 2.53% __zram_bvec_write
19
 2.11% do_raw_spin_lock
20
 2.02% memmove
21
 1.93% lru_gen_look_around
22
 1.56% free_unref_page_list
23
 1.40% memset

Hence lru_gen_look_around() exploits the spatial locality of memory to improve page reclaim and hot page identification. When shrink_folio_list finds a hot PTE (Accessed bit = 1), it draws a PMD scan window centered on that PTE address, searching a total of BITS_PER_LONG PTEs within it, checking whether the Accessed bits of these neighboring PTEs are also 1 (young), and when there are enough hot pages, adds the PMD to a Bloom filter to serve as auxiliary information during aging.

$f(young, total) = young \times n \ge total$ $n=clamp(cacheline\div sizeof(pte),2,8)$

Finally, the aging part. As mentioned above, when a PMD contains enough hot pages, it is added to the Bloom filter. When aging performs its page table walk, it first queries the Bloom filter for each PMD entry. If the PMD exists in the Bloom filter, it means the PMD’s hot-page density is high enough that it is worth continuing to walk the PTEs inside and performing promote/protect.

Reclaim Behavior#


• cgroup memory.reclaim
  • Proactive, manually triggered
  • echo <size> > /sys/fs/cgroup/<cg-name>/memory.reclaim
• direct reclaim
  • Reactive, triggered when available memory is extremely scarce (watermark below WMARK_MIN)
  • Executes synchronously; the memory watermark is checked on page fault
  • Stops once the watermark rises to WMARK_LOW
• kswapd
  • Triggered when the available memory watermark falls below WMARK_LOW
  • Runs in the background, stops at WMARK_HIGH

Google: kstaled / kreclaimd (ASPLOS 2019)#

• kstaled: periodically walks page tables reading the pages’ Accessed bits to track page age
• kreclaimd: compresses pages whose age exceeds a threshold into zswap
• Architectural evolution:
  1. sysfs + bitmap
  2. kstaled / kreclaimd
• Overhead grows linearly with memory size and scan frequency
  • kstaled scanning changed to a PMD linked-list walk (3.5x lower CPU usage)
  • kreclaimd changed to consume kstaled’s data

sjp38: DAMON/S (Data Access MONitoring[-based operation Schemes])#

• By SeongJae Park (sjp38), a former Amazon employee
• Region-based sampling
  • Changes the monitoring granularity from pages (as in Google’s architecture above) to regions (region size is configurable)
  • Uses sampling to observe region hotness
  • Each sampling round randomly picks one page per region, waits one interval, then checks whether it was accessed; on a hit, the region’s nr_accesses is incremented by 1.
• Adaptive Regions Adjustment
  • The premise is that pages within the same region have similar hotness, and access patterns change over time, so DAMON automatically merges and splits regions based on access frequency to continuously maintain this premise.
• Reclaim policies can be designed based on the observed information (DAMOS)
  • Example: DAMON_RECLAIM