[RFC PATCH v2 00/13] mm: rework anon_vma and remove anon_vma_chain

[tao]

Hi all,

Since v1 was relatively complex and difficult to extend, this version
adopts a simpler anon_vma implementation approach.


Replace the original anon_vma + anon_vma_chain multiple rbtree
structures with a depth-aware doubly linked list, and remove anon_vma_chain.


During rmap walks, vma_rmap_base(vma) is used to compute the page
address and look up the corresponding VMA from mm_mt:

  vma_rmap_base(vma) = vma->vm_start - vma->vm_pgoff * PAGE_SIZE

  page_address(vma, pgoff)
    = vma->vm_start + (pgoff - vma->vm_pgoff) * PAGE_SIZE
    = vma->vm_start - vma->vm_pgoff * PAGE_SIZE + pgoff * PAGE_SIZE
    = vma_rmap_base(vma) + pgoff * PAGE_SIZE

Since vma_rmap_base(vma) remains invariant across VMA merge and split
operations, VMA updates only need to adjust the VMA count of the
corresponding anon_vma. The anon_vma no longer directly tracks VMAs,
which eliminates the need for anon_vma_chain.

Process fork behaves like a fractal expansion of both tasks and
anon_vmas. A dedicated fractal_list records forked anon_vmas, while
descendant anon_vmas are derived from fork depth during rmap walks.
For this reason, the new design is named ANON_VMA_FRACTAL.

The depth is initialized to 0.
When a child is added, the root depth is set to 1.
A remap child has a depth of parent->depth + 1,
while a fork child has a depth of parent->depth + 2.
For example:
 1) A forks B and C:

	                   (1A)
	                  /    \
	                (3B)---(3C)

 2) B remaps D:

	                   (1A)
	                  /    \
	                (3B)   (3C)
	                /       /
	              (4D)-----o

 3) B forks E and F:

	                   (1A)--o
	                  /       \
	                (3B)      (3C)
	                /         /
	              (4D)       /
	              /         /
	            (5E)------(5F)

 4) C forks G:

	                   (1A)------------o
	                  /                 \
	                (3B)      (3C)       o
	                /         /  \      /
	              (4D)       /    \    /
	              /         /      \  /
	            (5E)------(5F)     (5G)

Only the root node A needs to traverse all descendants; non-root nodes
only traverse their own descendant nodes. For example:
- When rmap-ing A: first process A, then traverse all descendants
  B/D/E/F/C/G. A does not need to be traversed again.
- When rmap-ing B: first process B, then traverse its descendants
  D/E/F. Since C->depth <= B->depth, the rmap walk terminates at C.

The fractal_list remains stable across VMA merge and split operations.
It is updated only when anon_vmas are forked, remapped, or unlinked, and
is traversed during rmap walks.

On an Android device after boot, memory usage of vm_area_struct,
anon_vma, and anon_vma_chain is reduced by about 35 MB.

  struct              base(KB)  patch(KB)  patch_struct      saved(KB)
  --------------------------------------------------------------------
  vm_area_struct        110760     103837  vm_area_struct         6887
  anon_vma               19152       8576  anon_node             10576
  anon_vma_chain         17560          0  NA                    17560
  NA                         0        346  anon_semaphore         -346

lat_proc shows fork performance improves by about 15% at P=10.

Changes since v1:
- anon_vma now stores mm and rmap_base for VMA lookup, and only tracks
  the number of associated VMAs instead of directly tracking VMAs
- Use fractal_list + depth to maintain anon_vma topology and remove
  anon_vma_chain completely
- Keep folio->mapping storing anon_vma
- Preserve existing APIs and external callers unchanged while
  introducing ANON_RMAP_FOREACH_VMA() to unify anonymous rmap traversal
- Use vm_refcnt on leaf VMAs for rmap protection
- Optimize rwsem memory usage with shared semaphores

Patch layout:
  1-2: add CONFIG_ANON_VMA_FRACTAL and basic helpers
  3-7: implement anon_vma fractal infrastructure
  8: implement anonymous folio rmap
  9-10: replace anon_vma with anon_node
  11: use vm_refcnt on leaf VMAs for rmap protection
  12: optimize anon_vma memory usage with shared semaphores

v1:
https://lore.kernel.org/all/20260527110147.17815-1-tao.wangtao@xxxxxxxxx/

tao (13):
  mm: add CONFIG_ANON_VMA_FRACTAL
  mm: implement helpers for ANON_VMA_FRACTAL
  mm: implement __anon_node_prepare for ANON_VMA_FRACTAL
  mm: implement anon_node_clone for ANON_VMA_FRACTAL
  mm: implement anon_node_fork_with_prev for ANON_VMA_FRACTAL
  mm: implement unlink_anon_nodes for ANON_VMA_FRACTAL
  mm: handle rmap_base changes for ANON_VMA_FRACTAL
  mm: implement anonymous folio rmap for ANON_VMA_FRACTAL
  mm: prepare anon_node replacement for ANON_VMA_FRACTAL
  mm: replace anon_vma with anon_node for ANON_VMA_FRACTAL
  mm: optimize rmap for ANON_VMA_FRACTAL with PVL
  mm: shared semaphores for ANON_VMA_FRACTAL
  mm: Enable CONFIG_ANON_VMA_FRACTAL by default

 include/linux/mm.h       |   2 +
 include/linux/mm_types.h |   2 +
 include/linux/rmap.h     |  56 ++++
 include/linux/rwsem.h    |  10 +
 mm/Kconfig               |  37 +++
 mm/internal.h            | 205 ++++++++++++
 mm/ksm.c                 |  19 +-
 mm/memory-failure.c      |   8 +-
 mm/mmap.c                |   7 +-
 mm/rmap.c                | 686 +++++++++++++++++++++++++++++++++++++--
 mm/vma.c                 |  76 ++++-
 mm/vma_init.c            |   2 +
 12 files changed, 1056 insertions(+), 54 deletions(-)

-- 
2.17.1