Skip to contentSkip to conversation

RFC mm: Introducing the Maple Tree

PATCH In review Liam R. Howlett 2 participants 76 messages Jan 12, 2021 – Jan 13, 2021

Subsystems (38)
lore
Share & tools
lore
#0 lore raw

v2 cover RFC mm: Introducing the Maple Tree

***NOTE: the majority of this patch is the tests (35855 lines).***

Thanks to Vlastimil Babka for helping with perf on the full kernel build and looking at the cache numbers.

Changes since last RFC:
- rebased against 5.10 and updated benchmarks
- Transitioned more internal mm operations to using maple states
- Removed the mm_struct linked list as well as the maximum address
- Replaced external linked list operations by maple tree iterators or searches

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct rbtree in the mm_struct with the long term goal of reducing the contention of the mmap_sem.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly short than the rbtree so it has fewer cache misses. As you can see below, the performance is getting very close even without the vmacache. I am looking for ways to optimize the vma code to make this even faster and would like input. As this tree requires allocations to provide RCU functionality, it is worth avoiding expanding the tree only to contract it in the next step.

This patch set is based on 5.10.

It is important to note that this is an RFC and there are limitations around what is currently supported.

The current status of this release is:
- **No support for 32 bit or nommu builds** There will be test robot emails
- Removal of the vmacache
- Removal of the mm_struct linked list and highest VMA end.

- Increase in performance in the following micro-benchmarks in Hmean:
- will-it-scale signal1-processes -5 to +10%
- will-it-scale page_fault1-threads increase upper limit by 20%
- will-it-scale page_fault2-threads -5 to +45% (disregarding dip in rbtree at

    30-48 threads)

- will-it-scale malloc1-threads 24.5 to 1168%, tests with 30, 48, 79, 110, and 141 are all over 100% better.
- will-it-scale brk1-threads **This test doesn't make sense, disregard**
- will-it-scale pthread_mutex1-threads -4.6 to +17%
- will-it-scale signal1-processes -6 to +10.7%
- will-it-scale signal1-threads -0.7 to +11%

- Decrease in performance in the following micro-benchmarks:
- will-it-scale page_fault3-processes -3.5 to -7%
- will-it-scale brk1 which tests insert speed of a vma as it is written of

    -40 to -48%.

- will-it-scale malloc1-processes -0.7 to -13%

- page_fault3-threads is worth noting as a bumpy graph with a higher base value but a lower upper value.

- kernbench elapse time is relatively flat. Please see performance details for more information.

- Converted the following to use the advanced maple tree interface:
mm/mmap.c
- brk()
- mmap_region()
- do_munmap()
- dup_mmap()
- do_munmap()
mm/memory.c
- free_pgtables()
- unmap_vmas()

- Currently operating in non-RCU mode. Once turned on, RCU mode will automatically enable when more than one thread is active on a task.

The long term goal of the maple tree is to reduce mmap_sem contention by removing users that cause contention one by one. This may lead to the lock being completely removed at some point.

The secondary goals is to add a fast RCU tree with a simple interface to the kernel and to clean up the mm code by removing the integration of the tree within the code and structures themselves.

============================================================================
Implementation details:

Each node is 256 Bytes and has multiple node types. The current implementation uses two node types and has a branching factor of 16 for leaf/non-alloc nodes and 10 for internal alloc nodes. The advantage of the internal alloc nodes is the ability to track the largest sub-tree gap for each entry.

With the removal of the vmacache and the linked list, most benchmarks are close to achieving parity and some are now above what the rbtree achieves. I'd still like some help with figuring out how to make building kernels faster.

The tree is at a disadvantage of needing to allocate storage space for internal use where as the rbtree stored the data within the vm_area_struct. This is a necessary trade off to move to RCU mode in the future.

performance details and raw data:

kernbench system time is up by ~4%, but elapsed time is pretty much the same.

Perf analysis of a 140 thread kernel build cache shows the follow:

With v2 RFC of the maple tree:

     14,692,670.92 msec task-clock                #   68.720 CPUs utilized
43,983,754,174,774      cycles                    #    2.994 GHz
35,221,280,320,157      instructions              #    0.80  insn per cycle
   548,066,089,628      cache-references          #   37.302 M/sec
    39,632,749,650      cache-misses              #    7.231 % of all cache refs
     213.804939614 seconds time elapsed

12822.727778000 seconds user

    1768.516799000 seconds sys

Vanilla 5.10:

     14,535,940.58 msec task-clock                #   67.025 CPUs utilized
43,541,026,636,749      cycles                    #    2.995 GHz
35,025,757,470,518      instructions              #    0.80  insn per cycle
   535,675,044,717      cache-references          #   36.852 M/sec
    38,837,910,214      cache-misses              #    7.250 % of all cache refs
     216.872446418 seconds time elapsed

12785.056085000 seconds user

    1653.652012000 seconds sys

0.555% more instructions were executed (195522849639 more) 0.019% more cache hits occurred

I *think* the system is able to keep the CPUs busy more often due to the increased cache hit rate. However, the added instructions reduce or remove the advantage at this point.

I had thought that there is more CPU used in-kernel but the bottleneck of the mmap_sem lock is still the runtime speed limiting factor. This doesn't make sense as pointed out by Vlastimil 'because kernel build should be lots of separate single-threaded processes (gcc) so where would that contention come from'.

I would appreciate any insightful comments on the results.

Benchmark numbers from mmtests on a 144 core system:

wis-signal 5.10 maple tree

Hmean     signal1-processes-2        1786040.86 (   0.00%)      1810613.96 *   1.38%*
Hmean     signal1-processes-5        4495852.24 (   0.00%)      4456978.23 *  -0.86%*
Hmean     signal1-processes-8        6962785.32 (   0.00%)      6928809.21 *  -0.49%*
Hmean     signal1-processes-12       9996679.72 (   0.00%)      9960859.26 *  -0.36%*
Hmean     signal1-processes-21       5800266.56 (   0.00%)      6424291.55 *  10.76%*
Hmean     signal1-processes-30       5461129.81 (   0.00%)      5965843.00 *   9.24%*
Hmean     signal1-processes-48       5402662.10 (   0.00%)      5373518.13 *  -0.54%*
Hmean     signal1-processes-79       6324458.64 (   0.00%)      6373855.01 *   0.78%*
Hmean     signal1-processes-110      7888582.74 (   0.00%)      7715943.65 *  -2.19%*
Hmean     signal1-processes-141      9708237.79 (   0.00%)      9144247.40 *  -5.81%*

wis-pf 5.10 maple tree

Hmean     page_fault3-processes-2        1528339.53 (   0.00%)      1418181.17 *  -7.21%*
Hmean     page_fault3-processes-5        3844682.44 (   0.00%)      3568964.13 *  -7.17%*
Hmean     page_fault3-processes-8        5962218.35 (   0.00%)      5582064.77 *  -6.38%*
Hmean     page_fault3-processes-12       8627107.79 (   0.00%)      8161496.35 *  -5.40%*
Hmean     page_fault3-processes-21      13714558.07 (   0.00%)     13137400.10 *  -4.21%*
Hmean     page_fault3-processes-30      19982269.52 (   0.00%)     18935995.56 *  -5.24%*
Hmean     page_fault3-processes-48      31128230.35 (   0.00%)     29117987.37 *  -6.46%*
Hmean     page_fault3-processes-79      46534013.37 (   0.00%)     43858063.38 *  -5.75%*
Hmean     page_fault3-processes-110     51560408.08 (   0.00%)     49113317.22 *  -4.75%*
Hmean     page_fault3-processes-141     56715596.66 (   0.00%)     54704417.46 *  -3.55%*
Hmean     page_fault1-threads-2          1845141.09 (   0.00%)      1845041.57 *  -0.01%*
Hmean     page_fault1-threads-5          4170927.21 (   0.00%)      4174427.49 *   0.08%*
Hmean     page_fault1-threads-8          5808980.21 (   0.00%)      5887126.65 *   1.35%*
Hmean     page_fault1-threads-12         5925792.38 (   0.00%)      5905272.94 *  -0.35%*
Hmean     page_fault1-threads-21         5871532.58 (   0.00%)      6440880.05 *   9.70%*
Hmean     page_fault1-threads-30         6832271.78 (   0.00%)      6861522.91 *   0.43%*
Hmean     page_fault1-threads-48         8614245.56 (   0.00%)      8922534.13 *   3.58%*
Hmean     page_fault1-threads-79        11609583.54 (   0.00%)     11257758.66 *  -3.03%*
Hmean     page_fault1-threads-110       11594428.36 (   0.00%)     12005585.11 *   3.55%*
Hmean     page_fault1-threads-141       11314690.18 (   0.00%)     13623989.67 *  20.41%*
Hmean     page_fault2-threads-2           806638.35 (   0.00%)       790103.29 *  -2.05%*
Hmean     page_fault2-threads-5          1689522.43 (   0.00%)      1705998.81 *   0.98%*
Hmean     page_fault2-threads-8          2117462.47 (   0.00%)      2002244.16 *  -5.44%*
Hmean     page_fault2-threads-12         2130151.22 (   0.00%)      2181799.70 *   2.42%*
Hmean     page_fault2-threads-21         1428004.62 (   0.00%)      2076765.86 *  45.43%*
Hmean     page_fault2-threads-30         1163606.91 (   0.00%)      2090400.49 *  79.65%*
Hmean     page_fault2-threads-48          605893.29 (   0.00%)      1712174.51 * 182.59%*
Hmean     page_fault2-threads-79         1401105.11 (   0.00%)      1948016.56 *  39.03%*
Hmean     page_fault2-threads-110        2107269.70 (   0.00%)      2063247.07 *  -2.09%*
Hmean     page_fault2-threads-141        1148808.86 (   0.00%)      1643422.67 *  43.05%*
Hmean     page_fault3-threads-2          1370710.48 (   0.00%)      1359083.92 *  -0.85%*
Hmean     page_fault3-threads-5          3010390.55 (   0.00%)      2488127.21 * -17.35%*
Hmean     page_fault3-threads-8          3214674.74 (   0.00%)      2502612.56 * -22.15%*
Hmean     page_fault3-threads-12         3443935.69 (   0.00%)      2788050.49 * -19.04%*
Hmean     page_fault3-threads-21         1500648.03 (   0.00%)      1748934.69 *  16.55%*
Hmean     page_fault3-threads-30         1633922.78 (   0.00%)      1644905.78 *   0.67%*
Hmean     page_fault3-threads-48         1357568.84 (   0.00%)      1501556.63 *  10.61%*
Hmean     page_fault3-threads-79         1731774.85 (   0.00%)      1527178.31 * -11.81%*
Hmean     page_fault3-threads-110        1867416.16 (   0.00%)      1918662.69 *   2.74%*
Hmean     page_fault3-threads-141        1901439.58 (   0.00%)      1960142.22 *   3.09%*

wis-malloc 5.10 maple tree

Hmean     brk1-processes-2           4547264.11 (   0.00%)      2711590.85 * -40.37%*
Hmean     brk1-processes-5          11396047.63 (   0.00%)      6723760.18 * -41.00%*
Hmean     brk1-processes-8          17684347.79 (   0.00%)      9850073.01 * -44.30%*
Hmean     brk1-processes-12         25803477.74 (   0.00%)     13551301.45 * -47.48%*
Hmean     brk1-processes-21         42083608.45 (   0.00%)     22484839.92 * -46.57%*
Hmean     brk1-processes-30         61095769.10 (   0.00%)     31853867.49 * -47.86%*
Hmean     brk1-processes-48         95924485.69 (   0.00%)     50239694.48 * -47.63%*
Hmean     brk1-processes-79        144415437.49 (   0.00%)     75287655.57 * -47.87%*
Hmean     brk1-processes-110       161729976.95 (   0.00%)     83624072.84 * -48.29%*
Hmean     brk1-processes-141       178985545.93 (   0.00%)     92036828.36 * -48.58%*

*Note: This isn't testing brk, it's testing insert of a VMA

Hmean     malloc1-processes-2         513481.82 (   0.00%)       447458.20 * -12.86%*
Hmean     malloc1-processes-5        1192865.83 (   0.00%)      1052137.79 * -11.80%*
Hmean     malloc1-processes-8        1290698.38 (   0.00%)      1202802.10 *  -6.81%*
Hmean     malloc1-processes-12       1357323.31 (   0.00%)      1300602.17 *  -4.18%*
Hmean     malloc1-processes-21       2052572.96 (   0.00%)      1975328.24 *  -3.76%*
Hmean     malloc1-processes-30       2793186.04 (   0.00%)      2700345.64 *  -3.32%*
Hmean     malloc1-processes-48       4087424.14 (   0.00%)      4059035.58 *  -0.69%*
Hmean     malloc1-processes-79       5185320.24 (   0.00%)      5120912.56 *  -1.24%*
Hmean     malloc1-processes-110      5231498.33 (   0.00%)      4991315.64 *  -4.59%*
Hmean     malloc1-processes-141      5096423.47 (   0.00%)      4847749.27 *  -4.88%*
Hmean     malloc1-threads-2            14119.77 (   0.00%)       179149.22 *1168.78%*
Hmean     malloc1-threads-5           120466.20 (   0.00%)       158994.30 *  31.98%*
Hmean     malloc1-threads-8           103323.01 (   0.00%)       128684.83 *  24.55%*
Hmean     malloc1-threads-12          102365.88 (   0.00%)       127458.10 *  24.51%*
Hmean     malloc1-threads-21           55230.52 (   0.00%)        97276.98 *  76.13%*
Hmean     malloc1-threads-30           40144.81 (   0.00%)        87899.80 * 118.96%*
Hmean     malloc1-threads-48           18651.63 (   0.00%)        57501.70 * 208.29%*
Hmean     malloc1-threads-79            5987.82 (   0.00%)        36411.66 * 508.10%*
Hmean     malloc1-threads-110           9425.14 (   0.00%)        19021.17 * 101.81%*
Hmean     malloc1-threads-141           6176.71 (   0.00%)        22104.21 * 257.86%*

wis-pthreadmutex 5.10 maple tree

Hmean     pthread_mutex1-threads-2         18757795.65 (   0.00%)     18234843.22 *  -2.79%*
Hmean     pthread_mutex1-threads-5         10875114.75 (   0.00%)     12748240.14 *  17.22%*
Hmean     pthread_mutex1-threads-8         13474657.37 (   0.00%)     14906619.63 *  10.63%*
Hmean     pthread_mutex1-threads-12        14686773.11 (   0.00%)     14096530.35 *  -4.02%*
Hmean     pthread_mutex1-threads-21        14253992.75 (   0.00%)     13893250.09 *  -2.53%*
Hmean     pthread_mutex1-threads-30        15327949.47 (   0.00%)     14613516.32 *  -4.66%*
Hmean     pthread_mutex1-threads-48        14892473.83 (   0.00%)     15177204.93 *   1.91%*
Hmean     pthread_mutex1-threads-79        14333125.23 (   0.00%)     14254569.45 *  -0.55%*
Hmean     pthread_mutex1-threads-110       13623757.15 (   0.00%)     14067267.02 *   3.26%*
Hmean     pthread_mutex1-threads-141       13097069.36 (   0.00%)     13320433.23 *   1.71%*

wis-signal 5.10 maple tree

Hmean     signal1-processes-2        1786040.86 (   0.00%)      1810613.96 *   1.38%*
Hmean     signal1-processes-5        4495852.24 (   0.00%)      4456978.23 *  -0.86%*
Hmean     signal1-processes-8        6962785.32 (   0.00%)      6928809.21 *  -0.49%*
Hmean     signal1-processes-12       9996679.72 (   0.00%)      9960859.26 *  -0.36%*
Hmean     signal1-processes-21       5800266.56 (   0.00%)      6424291.55 *  10.76%*
Hmean     signal1-processes-30       5461129.81 (   0.00%)      5965843.00 *   9.24%*
Hmean     signal1-processes-48       5402662.10 (   0.00%)      5373518.13 *  -0.54%*
Hmean     signal1-processes-79       6324458.64 (   0.00%)      6373855.01 *   0.78%*
Hmean     signal1-processes-110      7888582.74 (   0.00%)      7715943.65 *  -2.19%*
Hmean     signal1-processes-141      9708237.79 (   0.00%)      9144247.40 *  -5.81%*
Hmean     signal1-threads-2          1253290.69 (   0.00%)      1304356.96 *   4.07%*
Hmean     signal1-threads-5          1105142.15 (   0.00%)      1219370.11 *  10.34%*
Hmean     signal1-threads-8          1085584.56 (   0.00%)      1206909.95 *  11.18%*
Hmean     signal1-threads-12         1113346.88 (   0.00%)      1218394.23 *   9.44%*
Hmean     signal1-threads-21          817087.31 (   0.00%)       852237.46 *   4.30%*
Hmean     signal1-threads-30          657827.07 (   0.00%)       695077.88 *   5.66%*
Hmean     signal1-threads-48          523114.49 (   0.00%)       562605.91 *   7.55%*
Hmean     signal1-threads-79          500027.91 (   0.00%)       527026.99 *   5.40%*
Hmean     signal1-threads-110         480231.16 (   0.00%)       498458.54 *   3.80%*
Hmean     signal1-threads-141         468149.75 (   0.00%)       464573.98 *  -0.76%*
kernbench               5.10-rc1                maple tree
Amean     user-2        887.32 (   0.00%)      882.62 *   0.53%*
Amean     syst-2        145.77 (   0.00%)      152.04 *  -4.30%*
Amean     elsp-2        522.10 (   0.00%)      522.97 *  -0.17%*
Amean     user-4        902.24 (   0.00%)      898.12 *   0.46%*
Amean     syst-4        149.70 (   0.00%)      156.35 *  -4.44%*
Amean     elsp-4        269.58 (   0.00%)      271.99 *  -0.90%*
Amean     user-8        920.12 (   0.00%)      913.07 *   0.77%*
Amean     syst-8        149.97 (   0.00%)      155.61 *  -3.76%*
Amean     elsp-8        141.55 (   0.00%)      141.58 *  -0.03%*
Amean     user-16       935.31 (   0.00%)      926.23 *   0.97%*
Amean     syst-16       151.97 (   0.00%)      157.41 *  -3.58%*
Amean     elsp-16        77.37 (   0.00%)       77.35 *   0.04%*
Amean     user-32       982.76 (   0.00%)      977.36 *   0.55%*
Amean     syst-32       162.56 (   0.00%)      167.90 *  -3.29%*
Amean     elsp-32        46.17 (   0.00%)       46.08 *   0.19%*
Amean     user-64      1093.08 (   0.00%)     1081.16 *   1.09%*
Amean     syst-64       177.43 (   0.00%)      183.63 *  -3.49%*
Amean     elsp-64        30.80 (   0.00%)       30.28 *   1.68%*
Amean     user-128     1611.20 (   0.00%)     1610.98 *   0.01%*
Amean     syst-128      234.32 (   0.00%)      244.25 *  -4.24%*
Amean     elsp-128       25.76 (   0.00%)       25.73 *   0.12%*
Amean     user-256     1733.42 (   0.00%)     1739.23 *  -0.34%*
Amean     syst-256      248.58 (   0.00%)      259.16 *  -4.26%*
Amean     elsp-256       25.17 (   0.00%)       25.44 *  -1.07%*
Amean     user-288     1734.83 (   0.00%)     1737.28 *  -0.14%*
Amean     syst-288      249.63 (   0.00%)      259.55 *  -3.97%*
Amean     elsp-288       25.43 (   0.00%)       25.45 *  -0.09%*

gitcheckout

Amean     User           0.00 (   0.00%)        0.00 *   0.00%*
Amean     System         8.07 (   0.00%)        7.92 *   1.83%*
Amean     Elapsed       23.46 (   0.00%)       22.91 *   2.35%*
Amean     CPU           91.87 (   0.00%)       92.33 *  -0.51%*

Liam R. Howlett (70):
radix tree test suite: Enhancements for Maple Tree
radix tree test suite: Add support for fallthrough attribute radix tree test suite: Add support for kmem_cache_free_bulk radix tree test suite: Add keme_cache_alloc_bulk() support Maple Tree: Add new data structure
mm: Start tracking VMAs with maple tree
mm/mmap: Introduce unlock_range() for code cleanup mm/mmap: Change find_vma() to use the maple tree
mm/mmap: Change find_vma_prev() to use maple tree mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple
tree
kernel/fork: Convert dup_mmap to use maple tree
mm: Remove rb tree.
mm/gup: Add mm_populate_vma() for use when the vma is known mm/mmap: Change do_brk_flags() to expand existing VMA and add

    do_brk_munmap()

mm/mmap: Change vm_brk_flags() to use mm_populate_vma()
mm: Move find_vma_intersection to mmap.c and change implementation to
maple tree.
mm/mmap: Change mmap_region to use maple tree state mm/mmap: Drop munmap_vma_range()
mm: Remove vmacache
mm/mmap: Change __do_munmap() to avoid unnecessary lookups. mm/mmap: Move mmap_region() below do_munmap()
mm/mmap: Add do_mas_munmap() and wraper for __do_munmap()
mmap: Use find_vma_intersection in do_mmap() for overlap
mmap: Remove __do_munmap() in favour of do_mas_munmap() mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()
mmap: make remove_vma_list() inline
mm: Introduce vma_next() and vma_prev()
arch/arm64: Remove mmap linked list from vdso. arch/parsic: Remove mmap linked list from kernel/cache arch/powerpc: Remove mmap linked list from mm/book2s32/tlb arch/powerpc: Remove mmap linked list from mm/book2s32/subpage_prot arch/powerpc: Optimize cell spu task sync.
arch/s390: Use maple tree iterators instead of linked list. arch/um: Use maple tree iterators instead of linked list arch/x86: Use maple tree iterators for vdso/vma arch/xtensa: Use maple tree iterators for unmapped area drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma() drivers/oprofile: Lookup address in tree instead of linked list. drivers/tee/optee: Use maple tree iterators for __check_mem_type() fs/binfmt_elf: Use maple tree iterators for fill_files_note() fs/coredump: Use maple tree iterators in place of linked list fs/exec: Use vma_next() instead of linked list fs/proc/base: Use maple tree iterators in place of linked list fs/proc/task_mmu: Stop using linked list and highest_vm_end fs/userfaultfd: Stop using vma linked list.
ipc/shm: Stop using the vma linked list
kernel/acct: Use maple tree iterators instead of linked list kernel/events/core: Use maple tree iterators instead of linked list kernel/events/uprobes: Use maple tree iterators instead of linked list kernel/sched/fair: Use maple tree iterators instead of linked list kernel/sys: Use maple tree iterators instead of linked list mm/gup: Use maple tree navigation instead of linked list mm/huge_memory: Use vma_next() instead of vma linked list mm/khugepaged: Use maple tree iterators instead of vma linked list mm/ksm: Use maple tree iterators instead of vma linked list mm/madvise: Use vma_next instead of vma linked list mm/memcontrol: Stop using mm->highest_vm_end
mm/mempolicy: Use maple tree iterators instead of vma linked list mm/mlock: Use maple tree iterators instead of vma linked list mm/mprotect: Use maple tree navigation instead of vma linked list mm/mremap: Use vma_next() instead of vma linked list mm/msync: Use vma_next() instead of vma linked list mm/nommu: Use maple tree iterators instead of vma linked list mm/oom_kill: Use maple tree iterators instead of vma linked list mm/pagewalk: Use vma_next() instead of vma linked list mm/swapfile: Use maple tree iterator instead of vma linked list mm/nommu: Stop inserting into the vma linked list
mm/util: Remove __vma_link_list() and __vma_unlink_list()
mm: Remove vma linked list.
mm/mmap: Convert __insert_vm_struct to use mas, convert vma_link to
use vma_mas_link()

 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple-tree.rst         |    36 +
 MAINTAINERS                                   |    12 +
 arch/arm64/kernel/vdso.c                      |     5 +-
 arch/parisc/kernel/cache.c                    |     8 +-
 arch/powerpc/mm/book3s32/tlb.c                |     3 +-
 arch/powerpc/mm/book3s64/subpage_prot.c       |    13 +-
 arch/powerpc/oprofile/cell/spu_task_sync.c    |    22 +-
 arch/s390/mm/gmap.c                           |     6 +-
 arch/um/kernel/tlb.c                          |    14 +-
 arch/x86/entry/vdso/vma.c                     |     7 +-
 arch/x86/kernel/tboot.c                       |     2 +-
 arch/xtensa/kernel/syscall.c                  |     3 +-
 drivers/firmware/efi/efi.c                    |     2 +-
 drivers/misc/cxl/fault.c                      |     3 +-
 drivers/oprofile/buffer_sync.c                |    14 +-
 drivers/tee/optee/call.c                      |    13 +-
 fs/binfmt_elf.c                               |     3 +-
 fs/coredump.c                                 |    13 +-
 fs/exec.c                                     |     7 +-
 fs/proc/base.c                                |     5 +-
 fs/proc/task_mmu.c                            |    43 +-
 fs/userfaultfd.c                              |    24 +-
 include/linux/maple_tree.h                    |   439 +
 include/linux/mm.h                            |    49 +-
 include/linux/mm_types.h                      |    34 +-
 include/linux/mm_types_task.h                 |     5 -
 include/linux/sched.h                         |     1 -
 include/linux/sched/mm.h                      |     3 +
 include/linux/vmacache.h                      |    28 -
 include/trace/events/maple_tree.h             |   227 +
 include/trace/events/mmap.h                   |    71 +
 init/main.c                                   |     2 +
 ipc/shm.c                                     |    13 +-
 kernel/acct.c                                 |     6 +-
 kernel/debug/debug_core.c                     |    12 -
 kernel/events/core.c                          |     3 +-
 kernel/events/uprobes.c                       |     9 +-
 kernel/fork.c                                 |    48 +-
 kernel/sched/fair.c                           |    10 +-
 kernel/sys.c                                  |     3 +-
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  5700 +++
 lib/test_maple_tree.c                         | 35855 ++++++++++++++++
 mm/Makefile                                   |     2 +-
 mm/debug.c                                    |    12 +-
 mm/gup.c                                      |    27 +-
 mm/huge_memory.c                              |     6 +-
 mm/init-mm.c                                  |     4 +-
 mm/internal.h                                 |     4 +-
 mm/khugepaged.c                               |     7 +-
 mm/ksm.c                                      |    18 +-
 mm/madvise.c                                  |     2 +-
 mm/memcontrol.c                               |     6 +-
 mm/memory.c                                   |    39 +-
 mm/mempolicy.c                                |    33 +-
 mm/mlock.c                                    |    20 +-
 mm/mmap.c                                     |  2022 +-
 mm/mprotect.c                                 |     8 +-
 mm/mremap.c                                   |    13 +-
 mm/msync.c                                    |     2 +-
 mm/nommu.c                                    |    14 +-
 mm/oom_kill.c                                 |     3 +-
 mm/pagewalk.c                                 |     2 +-
 mm/swapfile.c                                 |     3 +-
 mm/util.c                                     |    32 -
 mm/vmacache.c                                 |   117 -
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |    13 +-
 tools/testing/radix-tree/generated/autoconf.h |     1 +
 tools/testing/radix-tree/linux.c              |    78 +-
 tools/testing/radix-tree/linux/kernel.h       |     8 +
 tools/testing/radix-tree/linux/maple_tree.h   |     3 +
 tools/testing/radix-tree/linux/slab.h         |     2 +
 tools/testing/radix-tree/maple.c              |    59 +
 tools/testing/radix-tree/test.h               |     1 +
 .../radix-tree/trace/events/maple_tree.h      |     8 +
 77 files changed, 43844 insertions(+), 1507 deletions(-)
 create mode 100644 Documentation/core-api/maple-tree.rst
 create mode 100644 include/linux/maple_tree.h
 delete mode 100644 include/linux/vmacache.h
 create mode 100644 include/trace/events/maple_tree.h
 create mode 100644 lib/maple_tree.c
 create mode 100644 lib/test_maple_tree.c
 delete mode 100644 mm/vmacache.c
 create mode 100644 tools/testing/radix-tree/linux/maple_tree.h
 create mode 100644 tools/testing/radix-tree/maple.c
 create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h
Signature · 1 line
2.28.0
#1 lore raw

PATCH v2 1/70 radix tree test suite: Enhancements for Maple Tree

---
 tools/testing/radix-tree/linux.c        | 16 +++++++++++++++-
 tools/testing/radix-tree/linux/kernel.h |  1 +
 2 files changed, 16 insertions(+), 1 deletion(-)
tools/testing/radix-tree/linux.c +15 -1
index 2d9c59df60de0..93f7de81fbe87 100644
@@ -24,15 +24,28 @@ struct kmem_cache {
 	int nr_objs;
 	void *objs;
 	void (*ctor)(void *);
+	unsigned int non_kernel;
 };
 
+void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
+{
+	cachep->non_kernel = val;
+}
+
+unsigned long kmem_cache_get_alloc(struct kmem_cache *cachep)
+{
+	return cachep->size * nr_allocated;
+}
 void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp)
 {
 	void *p;
 
-	if (!(gfp & __GFP_DIRECT_RECLAIM))
+	if (!(gfp & __GFP_DIRECT_RECLAIM) && !cachep->non_kernel)
 		return NULL;
 
+	if (!(gfp & __GFP_DIRECT_RECLAIM))
+		cachep->non_kernel--;
+
 	pthread_mutex_lock(&cachep->lock);
 	if (cachep->nr_objs) {
 		struct radix_tree_node *node = cachep->objs;
@@ -116,5 +129,6 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	ret->nr_objs = 0;
 	ret->objs = NULL;
 	ret->ctor = ctor;
+	ret->non_kernel = 0;
 	return ret;
 }
tools/testing/radix-tree/linux/kernel.h +1 -0
index 39867fd80c8fa..c5c9d05f29da9 100644
@@ -14,6 +14,7 @@
 #include "../../../include/linux/kconfig.h"
 
 #define printk printf
+#define pr_err printk
 #define pr_info printk
 #define pr_debug printk
 #define pr_cont printk
Signature · 1 line
2.28.0
#2 lore raw

PATCH v2 2/70 radix tree test suite: Add support for fallthrough attribute

In reply to Liam R. Howlett

Add support for fallthrough on case statements. Note this does *NOT* check for missing fallthrough, but does allow compiling of code with fallthrough in case statements.

---
 tools/testing/radix-tree/linux/kernel.h | 7 +++++++
 1 file changed, 7 insertions(+)
tools/testing/radix-tree/linux/kernel.h +7 -0
index c5c9d05f29da9..99979aeaa3796 100644
@@ -24,4 +24,11 @@
 #define __must_hold(x)
 
 #define EXPORT_PER_CPU_SYMBOL_GPL(x)
+
+#if __has_attribute(__fallthrough__)
+# define fallthrough                    __attribute__((__fallthrough__))
+#else
+# define fallthrough                    do {} while (0)  /* fallthrough */
+#endif /* __has_attribute */
+
 #endif /* _KERNEL_H */
Signature · 1 line
2.28.0
#3 lore raw

PATCH v2 3/70 radix tree test suite: Add support for kmem_cache_free_bulk

In reply to Liam R. Howlett
---
 tools/testing/radix-tree/linux.c      | 9 +++++++++
 tools/testing/radix-tree/linux/slab.h | 1 +
 2 files changed, 10 insertions(+)
tools/testing/radix-tree/linux.c +9 -0
index 93f7de81fbe87..380bbc0a48d6f 100644
@@ -91,6 +91,15 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp)
 	pthread_mutex_unlock(&cachep->lock);
 }
 
+void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list)
+{
+	if (kmalloc_verbose)
+		printk("Bulk free %p[0-%lu]\n", list, size - 1);
+
+	for (int i = 0; i < size; i++)
+		kmem_cache_free(cachep, list[i]);
+}
+
 void *kmalloc(size_t size, gfp_t gfp)
 {
 	void *ret;
tools/testing/radix-tree/linux/slab.h +1 -0
index 2958830ce4d76..53b79c15b3a22 100644
@@ -24,4 +24,5 @@ struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
 			unsigned int align, unsigned int flags,
 			void (*ctor)(void *));
 
+void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t, void **);
 #endif		/* SLAB_H */
Signature · 1 line
2.28.0
#4 lore raw

PATCH v2 4/70 radix tree test suite: Add keme_cache_alloc_bulk() support

In reply to Liam R. Howlett
---
 tools/testing/radix-tree/linux.c      | 51 +++++++++++++++++++++++++++
 tools/testing/radix-tree/linux/slab.h |  1 +
 2 files changed, 52 insertions(+)
tools/testing/radix-tree/linux.c +51 -0
index 380bbc0a48d6f..fb19a40ebb465 100644
@@ -99,6 +99,57 @@ void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list)
 	for (int i = 0; i < size; i++)
 		kmem_cache_free(cachep, list[i]);
 }
+int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
+			  void **p)
+{
+	size_t i;
+
+	if (kmalloc_verbose)
+		printk("Bulk alloc %lu\n", size);
+
+	if (!(gfp & __GFP_DIRECT_RECLAIM) && cachep->non_kernel < size)
+		return 0;
+
+	if (!(gfp & __GFP_DIRECT_RECLAIM))
+		cachep->non_kernel -= size;
+
+	pthread_mutex_lock(&cachep->lock);
+	if (cachep->nr_objs >= size) {
+		struct radix_tree_node *node = cachep->objs;
+
+		for (i = 0; i < size; i++) {
+			cachep->nr_objs--;
+			cachep->objs = node->parent;
+			p[i] = cachep->objs;
+		}
+		pthread_mutex_unlock(&cachep->lock);
+		node->parent = NULL;
+	} else {
+		pthread_mutex_unlock(&cachep->lock);
+		for (i = 0; i < size; i++) {
+			if (cachep->align) {
+				posix_memalign(&p[i], cachep->align,
+					       cachep->size * size);
+			} else {
+				p[i] = malloc(cachep->size * size);
+			}
+			if (cachep->ctor)
+				cachep->ctor(p[i]);
+			else if (gfp & __GFP_ZERO)
+				memset(p[i], 0, cachep->size);
+		}
+	}
+
+	for (i = 0; i < size; i++) {
+		uatomic_inc(&nr_allocated);
+		uatomic_inc(&nr_tallocated);
+		if (kmalloc_verbose)
+			printf("Allocating %p from slab\n", p[i]);
+	}
+
+	return size;
+}
+
 
 void *kmalloc(size_t size, gfp_t gfp)
 {
tools/testing/radix-tree/linux/slab.h +1 -0
index 53b79c15b3a22..ba42b8cc11d09 100644
@@ -25,4 +25,5 @@ struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
 			void (*ctor)(void *));
 
 void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t, void **);
+int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t, size_t, void **);
 #endif		/* SLAB_H */
Signature · 1 line
2.28.0
#5 lore raw

PATCH v2 5/70 Maple Tree: Add new data structure

In reply to Liam R. Howlett

The Maple Tree is a new data structure optimised for storing ranges.

---
 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple-tree.rst         |    36 +
 MAINTAINERS                                   |    12 +
 include/linux/maple_tree.h                    |   439 +
 include/trace/events/maple_tree.h             |   227 +
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  5699 +++
 lib/test_maple_tree.c                         | 35855 ++++++++++++++++
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |    13 +-
 tools/testing/radix-tree/generated/autoconf.h |     1 +
 tools/testing/radix-tree/linux.c              |     2 +
 tools/testing/radix-tree/linux/maple_tree.h   |     3 +
 tools/testing/radix-tree/maple.c              |    59 +
 tools/testing/radix-tree/test.h               |     1 +
 .../radix-tree/trace/events/maple_tree.h      |     8 +
 16 files changed, 42358 insertions(+), 3 deletions(-)
 create mode 100644 Documentation/core-api/maple-tree.rst
 create mode 100644 include/linux/maple_tree.h
 create mode 100644 include/trace/events/maple_tree.h
 create mode 100644 lib/maple_tree.c
 create mode 100644 lib/test_maple_tree.c
 create mode 100644 tools/testing/radix-tree/linux/maple_tree.h
 create mode 100644 tools/testing/radix-tree/maple.c
 create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h
Documentation/core-api/index.rst +1 -0
index 69171b1799f21..5b2d3b269d5c7 100644
@@ -43,6 +43,7 @@ Library functionality that is used throughout the kernel.
    this_cpu_ops
    timekeeping
    errseq
+   maple-tree
 
 Concurrency primitives
 ======================
Documentation/core-api/maple-tree.rst new file +36 -0
new file mode 100644
index 0000000000000..6d71d4b1f1456
@@ -0,0 +1,36 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+
+==========
+Maple Tree
+==========
+
+:Author: Liam R. Howlett
+
+Overview
+========
+
+The Maple Tree is an RCU safe Range tree based on the B-Tree.
+
+Normal API
+==========
+
+Allocating Nodes
+----------------
+
+Locking
+-------
+
+Advanced API
+============
+
+
+Internal Entries
+----------------
+
+Functions and structures
+========================
+
+.. kernel-doc:: include/linux/maple_tree.c
+.. kernel-doc:: lib/maple_tree.c
+
MAINTAINERS +12 -0
index 281de213ef478..8773355330359 100644
@@ -10440,6 +10440,18 @@ L:	[email protected]
 S:	Maintained
 W:	http://www.kernel.org/doc/man-pages
 
+MAPLE TREE
+M:	Liam R. Howlett <[email protected]>
+L:	[email protected]
+S:	Supported
+F:	Documentation/core-api/maple_tree.rst
+F:	include/linux/maple_tree.h
+F:	include/trace/events/maple_tree.h
+F:	lib/maple_tree.c
+F:	lib/test_maple_tree.c
+F:	tools/testing/radix-tree/linux/maple_tree.h
+F:	tools/testing/radix-tree/maple.c
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <[email protected]>
 L:	[email protected]
include/linux/maple_tree.h new file +439 -0

439 lines not on this page · raw message

include/trace/events/maple_tree.h new file +227 -0

227 lines not on this page · raw message

lib/Makefile +2 -1
index d415fc7067c5b..7a0f855f90d45 100644
@@ -32,7 +32,8 @@ KCSAN_SANITIZE_random32.o := n
 
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o timerqueue.o xarray.o \
-	 idr.o extable.o sha1.o irq_regs.o argv_split.o \
+	 maple_tree.o idr.o extable.o \
+	 sha1.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
lib/maple_tree.c new file +5699 -0

2,264 lines not on this page · raw message

lib/test_maple_tree.c new file +35855 -0

35,855 lines not on this page · raw message

tools/testing/radix-tree/.gitignore +2 -0
index d971516401e68..c901d96dd013e 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/Makefile +11 -2
index aa6abfe0749c1..551937ba66495 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/generated/autoconf.h +1 -0
index 2218b3cc184e4..e7da803502362 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/linux.c +2 -0
index fb19a40ebb465..ab8ea12f00d63 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/linux/maple_tree.h new file +3 -0
new file mode 100644
index 0000000000000..993ac3c3026f7

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/maple.c new file +59 -0

59 lines not on this page · raw message

tools/testing/radix-tree/test.h +1 -0
index 7ef7067e942c2..22153004077bb 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/trace/events/maple_tree.h new file +8 -0
new file mode 100644
index 0000000000000..70c7f8d49aa1e

Lines of this file are not shown. View the raw message.

The rest of this diff is not shown. View the raw message.

Signature · 1 line
2.28.0

Part of the diff is not shown here. View the raw message.

#6 lore raw

PATCH v2 6/70 mm: Start tracking VMAs with maple tree

In reply to Liam R. Howlett

Start tracking the VMAs with the new maple tree structure in parallel with the rb_tree. Add debug and trace events for maple tree operations and duplicate the rb_tree that is created on forks into the maple tree.

---
 arch/x86/kernel/tboot.c     |   1 +
 drivers/firmware/efi/efi.c  |   1 +
 include/linux/mm.h          |   2 +
 include/linux/mm_types.h    |   2 +
 include/trace/events/mmap.h |  71 ++++++++++++
 init/main.c                 |   2 +
 kernel/fork.c               |   4 +
 mm/init-mm.c                |   2 +
 mm/mmap.c                   | 218 +++++++++++++++++++++++++++++++++++-
 9 files changed, 301 insertions(+), 2 deletions(-)
arch/x86/kernel/tboot.c +1 -0
index ae64f98ec2ab6..d9b1cc30976c4 100644
@@ -90,6 +90,7 @@ void __init tboot_probe(void)
 static pgd_t *tboot_pg_dir;
 static struct mm_struct tboot_mm = {
 	.mm_rb          = RB_ROOT,
+	.mm_mt          = MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd            = swapper_pg_dir,
 	.mm_users       = ATOMIC_INIT(2),
 	.mm_count       = ATOMIC_INIT(1),
drivers/firmware/efi/efi.c +1 -0
index 6c6eec044a978..e40effbf028a6 100644
@@ -55,6 +55,7 @@ static unsigned long __initdata rt_prop = EFI_INVALID_TABLE_ADDR;
 
 struct mm_struct efi_mm = {
 	.mm_rb			= RB_ROOT,
+	.mm_mt			= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.mm_users		= ATOMIC_INIT(2),
 	.mm_count		= ATOMIC_INIT(1),
 	MMAP_LOCK_INITIALIZER(efi_mm)
include/linux/mm.h +2 -0
index db6ae4d3fb4ed..9cbbbbc3043a9 100644
@@ -2467,6 +2467,8 @@ extern bool arch_has_descending_max_zone_pfns(void);
 /* nommu.c */
 extern atomic_long_t mmap_pages_allocated;
 extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
+/* maple_tree */
+void vma_store(struct mm_struct *mm, struct vm_area_struct *vma);
 
 /* interval_tree.c */
 void vma_interval_tree_insert(struct vm_area_struct *node,
include/linux/mm_types.h +2 -0
index 5a9238f6caad9..f2c725e1052f8 100644
@@ -8,6 +8,7 @@
 #include <linux/list.h>
 #include <linux/spinlock.h>
 #include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/completion.h>
 #include <linux/cpumask.h>
@@ -388,6 +389,7 @@ struct kioctx_table;
 struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
+		struct maple_tree mm_mt;
 		struct rb_root mm_rb;
 		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
include/trace/events/mmap.h +71 -0

77 lines not on this page · raw message

init/main.c +2 -0
index 32b2a8affafd1..506bcdbeb02d8 100644
@@ -114,6 +114,7 @@ static int kernel_init(void *);
 
 extern void init_IRQ(void);
 extern void radix_tree_init(void);
+extern void maple_tree_init(void);
 
 /*
  * Debug helper: via this flag we know that we are in 'early bootup code'
@@ -923,6 +924,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
 		 "Interrupts were enabled *very* early, fixing it\n"))
 		local_irq_disable();
 	radix_tree_init();
+	maple_tree_init();
 
 	/*
 	 * Set up housekeeping before setting up workqueues to allow the unbound
kernel/fork.c +4 -0
index 6d266388d3804..8c7273b0d4b77 100644
@@ -588,6 +588,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		rb_link = &tmp->vm_rb.rb_right;
 		rb_parent = &tmp->vm_rb;
 
+		/* Link the vma into the MT */
+		vma_store(mm, tmp);
+
 		mm->map_count++;
 		if (!(tmp->vm_flags & VM_WIPEONFORK))
 			retval = copy_page_range(tmp, mpnt);
@@ -1004,6 +1007,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 {
 	mm->mmap = NULL;
 	mm->mm_rb = RB_ROOT;
+	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
mm/init-mm.c +2 -0
index 3a613c85f9ede..27229044a0702 100644
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/mm_types.h>
 #include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/spinlock.h>
 #include <linux/list.h>
@@ -28,6 +29,7 @@
  */
 struct mm_struct init_mm = {
 	.mm_rb		= RB_ROOT,
+	.mm_mt		= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd		= swapper_pg_dir,
 	.mm_users	= ATOMIC_INIT(2),
 	.mm_count	= ATOMIC_INIT(1),
mm/mmap.c +216 -2

473 lines not on this page · raw message

Signature · 1 line
2.28.0
#7 lore raw

PATCH v2 7/70 mm/mmap: Introduce unlock_range() for code cleanup

In reply to Liam R. Howlett
---
 mm/mmap.c | 37 ++++++++++++++++++-------------------
 1 file changed, 18 insertions(+), 19 deletions(-)
mm/mmap.c +18 -19
index bf0de273161e1..65789b188c380 100644
@@ -2983,6 +2983,20 @@ int split_vma(struct mm_struct *mm, struct vm_area_struct *vma,
 	return __split_vma(mm, vma, addr, new_below);
 }
 
+static inline void unlock_range(struct vm_area_struct *start, unsigned long limit)
+{
+	struct mm_struct *mm = start->vm_mm;
+	struct vm_area_struct *tmp = start;
+
+	while (tmp && tmp->vm_start < limit) {
+		if (tmp->vm_flags & VM_LOCKED) {
+			mm->locked_vm -= vma_pages(tmp);
+			munlock_vma_pages_all(tmp);
+		}
+
+		tmp = tmp->vm_next;
+	}
+}
 /* Munmap is split into 2 main parts -- this part which finds
  * what needs doing, and the areas themselves, which do the
  * work.  This now handles partial unmappings.
@@ -3071,17 +3085,8 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	/*
 	 * unlock any mlock()ed ranges before detaching vmas
 	 */
-	if (mm->locked_vm) {
-		struct vm_area_struct *tmp = vma;
-		while (tmp && tmp->vm_start < end) {
-			if (tmp->vm_flags & VM_LOCKED) {
-				mm->locked_vm -= vma_pages(tmp);
-				munlock_vma_pages_all(tmp);
-			}
-
-			tmp = tmp->vm_next;
-		}
-	}
+	if (mm->locked_vm)
+		unlock_range(vma, end);
 
 	/* Detach vmas from rbtree */
 	if (!detach_vmas_to_be_unmapped(mm, vma, prev, end))
@@ -3384,14 +3389,8 @@ void exit_mmap(struct mm_struct *mm)
 		mmap_write_unlock(mm);
 	}
 
-	if (mm->locked_vm) {
-		vma = mm->mmap;
-		while (vma) {
-			if (vma->vm_flags & VM_LOCKED)
-				munlock_vma_pages_all(vma);
-			vma = vma->vm_next;
-		}
-	}
+	if (mm->locked_vm)
+		unlock_range(mm->mmap, ULONG_MAX);
 
 	arch_exit_mmap(mm);
 
Signature · 1 line
2.28.0
#8 lore raw

PATCH v2 8/70 mm/mmap: Change find_vma() to use the maple tree

In reply to Liam R. Howlett

Start using the maple tree to find VMA entries in an mm_struct.

---
 mm/mmap.c | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
mm/mmap.c +11 -18
index 65789b188c380..ab1cb0efc4c65 100644
@@ -2474,10 +2474,17 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 
 EXPORT_SYMBOL(get_unmapped_area);
 
-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
+/**
+ * find_vma() - Find the VMA for a given address, or the next vma.  May return
+ * NULL in the case of no vma at addr or above
+ * @mm The mm_struct to check
+ * @addr: The address
+ *
+ * Returns: The VMA assoicated with addr, or the next vma.
+ * May return NULL in the case of no vma at addr or above.
+ */
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
-	struct rb_node *rb_node;
 	struct vm_area_struct *vma;
 
 	/* Check the cache first. */
@@ -2485,24 +2492,10 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 	if (likely(vma))
 		return vma;
 
-	rb_node = mm->mm_rb.rb_node;
-
-	while (rb_node) {
-		struct vm_area_struct *tmp;
-
-		tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
-
-		if (tmp->vm_end > addr) {
-			vma = tmp;
-			if (tmp->vm_start <= addr)
-				break;
-			rb_node = rb_node->rb_left;
-		} else
-			rb_node = rb_node->rb_right;
-	}
-
+	vma = mt_find(&mm->mm_mt, &addr, ULONG_MAX);
 	if (vma)
 		vmacache_update(addr, vma);
+
 	return vma;
 }
 EXPORT_SYMBOL(find_vma);
Signature · 1 line
2.28.0
reviewer
#9 lore raw

Re: [PATCH v2 08/70] mm/mmap: Change find_vma() to use the maple tree

Hi,
Please adjust the kernel-doc to be correct :)

Quoted 12 lines · Liam R. Howlett

Start using the maple tree to find VMA entries in an mm_struct.

---
 mm/mmap.c | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
mm/mmap.c +0 -0
index 65789b188c380..ab1cb0efc4c65 100644

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2479

Quoted 7 lines
mm/mmap.c +3 -1
@@ -2474,10 +2474,17 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 
 EXPORT_SYMBOL(get_unmapped_area);
 
-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
+/**
+ * find_vma() - Find the VMA for a given address, or the next vma.  May return
+ * NULL in the case of no vma at addr or above

%NULL

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2480

Quoted 1 line
mm/mmap.c +1 -0
+ * @mm The mm_struct to check

* @mm: ...

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2483

Quoted 3 lines
mm/mmap.c +3 -0
+ * @addr: The address
+ *
+ * Returns: The VMA assoicated with addr, or the next vma.

associated

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2484

Quoted 1 line
mm/mmap.c +1 -0
+ * May return NULL in the case of no vma at addr or above.

%NULL

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2487

Quoted 3 lines
mm/mmap.c +1 -0
+ */
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {

thanks.

Signature · 1 line
~Randy
#10 lore raw

PATCH v2 9/70 mm/mmap: Change find_vma_prev() to use maple tree

In reply to Liam R. Howlett

Change the implementation of find_vma_prev to use the new maple tree data structure.

---
 mm/mmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
mm/mmap.c +17 -10
index ab1cb0efc4c65..f123f9c97dfe8 100644
@@ -2500,23 +2500,30 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
 
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * sets %pprev to the previous VMA, if any.
+ * @mm The mm_struct to check
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * Returns: The VMA associated with @addr, or the next vma.
+ * May return NULL in the case of no vma at addr or above.
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,
-			struct vm_area_struct **pprev)
+	      struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	vma = find_vma(mm, addr);
-	if (vma) {
-		*pprev = vma->vm_prev;
-	} else {
-		struct rb_node *rb_node = rb_last(&mm->mm_rb);
+	rcu_read_lock();
+	vma = mas_find(&mas, ULONG_MAX);
+	if (!vma)
+		mas_reset(&mas);
 
-		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
-	}
+	*pprev = mas_prev(&mas, 0);
+	rcu_read_unlock();
 	return vma;
 }
 
Signature · 1 line
2.28.0
reviewer
#11 lore raw

Re: [PATCH v2 09/70] mm/mmap: Change find_vma_prev() to use maple tree

Please see kernel-doc fixes below:

Quoted 13 lines · Liam R. Howlett

Change the implementation of find_vma_prev to use the new maple tree data structure.

---
 mm/mmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
mm/mmap.c +0 -0
index ab1cb0efc4c65..f123f9c97dfe8 100644

mm/mmap.c struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) · line 2505

Quoted 8 lines
mm/mmap.c +3 -2
@@ -2500,23 +2500,30 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
 
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * sets %pprev to the previous VMA, if any.

* set @pprev

mm/mmap.c struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) · line 2506

Quoted 1 line
mm/mmap.c +1 -0
+ * @mm The mm_struct to check

* @mm: ...

mm/mmap.c struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) · line 2511

Quoted 5 lines
mm/mmap.c +5 -0
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * Returns: The VMA associated with @addr, or the next vma.
+ * May return NULL in the case of no vma at addr or above.

%NULL

mm/mmap.c struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) · line 2514

Quoted 3 lines
mm/mmap.c +0 -0
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,

thanks.

Signature · 1 line
~Randy
#12 lore raw

PATCH v2 10/70 mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple tree

In reply to Liam R. Howlett

Use the new maple tree data structure to find an unmapped area.

---
 mm/mmap.c | 249 ++++++------------------------------------------------
 1 file changed, 27 insertions(+), 222 deletions(-)
mm/mmap.c +27 -222
index f123f9c97dfe8..3b3084ee309b7 100644
@@ -2040,260 +2040,65 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 	return error;
 }
 
+/* unmapped_area() Find an area between the low_limit and the high_limit with
+ * the correct alignment and offset, all from @info. Note: current->mm is used
+ * for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
 static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 {
-	/*
-	 * We implement the search by looking for an rbtree node that
-	 * immediately follows a suitable gap. That is,
-	 * - gap_start = vma->vm_prev->vm_end <= info->high_limit - length;
-	 * - gap_end   = vma->vm_start        >= info->low_limit  + length;
-	 * - gap_end - gap_start >= length
-	 */
+	unsigned long length, gap;
 
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma;
-	unsigned long length, low_limit, high_limit, gap_start, gap_end;
-	unsigned long gap;
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
+	validate_mm(current->mm);
 
-	MA_STATE(mas, &mm->mm_mt, 0, 0);
 	/* Adjust search length to account for worst case alignment overhead */
 	length = info->length + info->align_mask;
 	if (length < info->length)
 		return -ENOMEM;
 
-
-	/* Maple tree is self contained. */
-	rcu_read_lock();
 	if (mas_get_empty_area(&mas, info->low_limit, info->high_limit - 1,
 				  length)) {
 		rcu_read_unlock();
 		return -ENOMEM;
 	}
-	rcu_read_unlock();
 	gap = mas.index;
 	gap += (info->align_offset - gap) & info->align_mask;
-
-	/* Adjust search limits by the desired length */
-	if (info->high_limit < length)
-		return -ENOMEM;
-	high_limit = info->high_limit - length;
-
-	if (info->low_limit > high_limit)
-		return -ENOMEM;
-	low_limit = info->low_limit + length;
-
-	/* Check if rbtree root looks promising */
-	if (RB_EMPTY_ROOT(&mm->mm_rb))
-		goto check_highest;
-	vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
-	if (vma->rb_subtree_gap < length)
-		goto check_highest;
-
-	while (true) {
-		/* Visit left subtree if it looks promising */
-		gap_end = vm_start_gap(vma);
-		if (gap_end >= low_limit && vma->vm_rb.rb_left) {
-			struct vm_area_struct *left =
-				rb_entry(vma->vm_rb.rb_left,
-					 struct vm_area_struct, vm_rb);
-			if (left->rb_subtree_gap >= length) {
-				vma = left;
-				continue;
-			}
-		}
-
-		gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
-check_current:
-		/* Check if current node has a suitable gap */
-		if (gap_start > high_limit)
-			return -ENOMEM;
-		if (gap_end >= low_limit &&
-		    gap_end > gap_start && gap_end - gap_start >= length)
-			goto found;
-
-		/* Visit right subtree if it looks promising */
-		if (vma->vm_rb.rb_right) {
-			struct vm_area_struct *right =
-				rb_entry(vma->vm_rb.rb_right,
-					 struct vm_area_struct, vm_rb);
-			if (right->rb_subtree_gap >= length) {
-				vma = right;
-				continue;
-			}
-		}
-
-		/* Go back up the rbtree to find next candidate node */
-		while (true) {
-			struct rb_node *prev = &vma->vm_rb;
-			if (!rb_parent(prev))
-				goto check_highest;
-			vma = rb_entry(rb_parent(prev),
-				       struct vm_area_struct, vm_rb);
-			if (prev == vma->vm_rb.rb_left) {
-				gap_start = vm_end_gap(vma->vm_prev);
-				gap_end = vm_start_gap(vma);
-				goto check_current;
-			}
-		}
-	}
-
-check_highest:
-	/* Check highest gap, which does not precede any rbtree node */
-	gap_start = mm->highest_vm_end;
-	gap_end = ULONG_MAX;  /* Only for VM_BUG_ON below */
-	if (gap_start > high_limit)
-		return -ENOMEM;
-
-found:
-	/* We found a suitable gap. Clip it with the original low_limit. */
-	if (gap_start < info->low_limit)
-		gap_start = info->low_limit;
-
-	/* Adjust gap address to the desired alignment */
-	gap_start += (info->align_offset - gap_start) & info->align_mask;
-
-	VM_BUG_ON(gap_start + info->length > info->high_limit);
-	VM_BUG_ON(gap_start + info->length > gap_end);
-
-	VM_BUG_ON(gap != gap_start);
-	return gap_start;
+	return gap;
 }
 
+/* unmapped_area() Find an area between the low_limit and the high_limit with
+ * the correct alignment and offset at the highest available address, all from
+ * @info. Note: current->mm is used for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
 static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 {
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = NULL;
-	unsigned long length, low_limit, high_limit, gap_start, gap_end;
-	unsigned long gap;
+	unsigned long length, gap;
 
-	MA_STATE(mas, &mm->mm_mt, 0, 0);
-	validate_mm_mt(mm);
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
+	validate_mm_mt(current->mm);
 	/* Adjust search length to account for worst case alignment overhead */
 	length = info->length + info->align_mask;
 	if (length < info->length)
 		return -ENOMEM;
 
-	rcu_read_lock();
-	if (mas_get_empty_area_rev(&mas, info->low_limit, info->high_limit,
+	if (mas_get_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
 				length)) {
 		rcu_read_unlock();
 		return -ENOMEM;
 	}
-	rcu_read_unlock();
 	gap = (mas.index + info->align_mask) & ~info->align_mask;
 	gap -= info->align_offset & info->align_mask;
-	/*
-	 * Adjust search limits by the desired length.
-	 * See implementation comment at top of unmapped_area().
-	 */
-	gap_end = info->high_limit;
-	if (gap_end < length)
-		return -ENOMEM;
-	high_limit = gap_end - length;
-
-	if (info->low_limit > high_limit)
-		return -ENOMEM;
-	low_limit = info->low_limit + length;
-
-	/* Check highest gap, which does not precede any rbtree node */
-	gap_start = mm->highest_vm_end;
-	if (gap_start <= high_limit)
-		goto found_highest;
-
-	/* Check if rbtree root looks promising */
-	if (RB_EMPTY_ROOT(&mm->mm_rb))
-		return -ENOMEM;
-	vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
-	if (vma->rb_subtree_gap < length)
-		return -ENOMEM;
-
-	while (true) {
-		/* Visit right subtree if it looks promising */
-		gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
-		if (gap_start <= high_limit && vma->vm_rb.rb_right) {
-			struct vm_area_struct *right =
-				rb_entry(vma->vm_rb.rb_right,
-					 struct vm_area_struct, vm_rb);
-			if (right->rb_subtree_gap >= length) {
-				vma = right;
-				continue;
-			}
-		}
-
-check_current:
-		/* Check if current node has a suitable gap */
-		gap_end = vm_start_gap(vma);
-		if (gap_end < low_limit)
-			return -ENOMEM;
-		if (gap_start <= high_limit &&
-		    gap_end > gap_start && gap_end - gap_start >= length)
-			goto found;
-
-		/* Visit left subtree if it looks promising */
-		if (vma->vm_rb.rb_left) {
-			struct vm_area_struct *left =
-				rb_entry(vma->vm_rb.rb_left,
-					 struct vm_area_struct, vm_rb);
-			if (left->rb_subtree_gap >= length) {
-				vma = left;
-				continue;
-			}
-		}
-
-		/* Go back up the rbtree to find next candidate node */
-		while (true) {
-			struct rb_node *prev = &vma->vm_rb;
-			if (!rb_parent(prev))
-				return -ENOMEM;
-			vma = rb_entry(rb_parent(prev),
-				       struct vm_area_struct, vm_rb);
-			if (prev == vma->vm_rb.rb_right) {
-				gap_start = vma->vm_prev ?
-					vm_end_gap(vma->vm_prev) : 0;
-				goto check_current;
-			}
-		}
-	}
-
-found:
-	/* We found a suitable gap. Clip it with the original high_limit. */
-	if (gap_end > info->high_limit)
-		gap_end = info->high_limit;
-
-found_highest:
-	/* Compute highest gap address at the desired alignment */
-	gap_end -= info->length;
-	gap_end -= (gap_end - info->align_offset) & info->align_mask;
-
-	VM_BUG_ON(gap_end < info->low_limit);
-	VM_BUG_ON(gap_end < gap_start);
-
-	if (gap != gap_end) {
-		pr_err("%s: %px Gap was found: mt %lu gap_end %lu\n", __func__,
-				mm, gap, gap_end);
-		pr_err("window was %lu - %lu size %lu\n", info->high_limit,
-				info->low_limit, length);
-		pr_err("mas.min %lu max %lu mas.last %lu\n", mas.min, mas.max,
-				mas.last);
-		pr_err("mas.index %lu align mask %lu offset %lu\n", mas.index,
-				info->align_mask, info->align_offset);
-		pr_err("rb_find_vma find on %lu => %px (%px)\n", mas.index,
-				find_vma(mm, mas.index), vma);
-#if defined(CONFIG_DEBUG_MAPLE_TREE)
-		mt_dump(&mm->mm_mt);
-#endif
-		{
-			struct vm_area_struct *dv = mm->mmap;
-
-			while (dv) {
-				printk("vma %px %lu-%lu\n", dv, dv->vm_start, dv->vm_end);
-				dv = dv->vm_next;
-			}
-		}
-		VM_BUG_ON(gap != gap_end);
-	}
-
-	return gap_end;
+	return gap;
 }
 
 /*
Signature · 1 line
2.28.0
reviewer
#13 lore raw

Re: [PATCH v2 10/70] mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple tree

one copy-pasta error below:

Quoted 26 lines · Liam R. Howlett

Use the new maple tree data structure to find an unmapped area.

---
 mm/mmap.c | 249 ++++++------------------------------------------------
 1 file changed, 27 insertions(+), 222 deletions(-)
mm/mmap.c +9 -0
index f123f9c97dfe8..3b3084ee309b7 100644
@@ -2040,260 +2040,65 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 	return error;
 }
 
+/* unmapped_area() Find an area between the low_limit and the high_limit with
+ * the correct alignment and offset, all from @info. Note: current->mm is used
+ * for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
 static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 {

...

Quoted 3 lines

}

+/* unmapped_area() Find an area between the low_limit and the high_limit with

s/unmapped_area/unmapped_area_topdown/

Quoted 10 lines

+ * the correct alignment and offset at the highest available address, all from
+ * @info. Note: current->mm is used for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info) {

thanks.

Signature · 1 line
~Randy
#14 lore raw

PATCH v2 11/70 kernel/fork: Convert dup_mmap to use maple tree

In reply to Liam R. Howlett

Use the maple tree iterator to duplicate the mm_struct trees.

---
 include/linux/sched/mm.h |  3 +++
 kernel/fork.c            | 22 +++++++++++++++++-----
 2 files changed, 20 insertions(+), 5 deletions(-)
include/linux/sched/mm.h +3 -0
index d5ece7a9a403f..919e2e44b764e 100644
@@ -8,6 +8,7 @@
 #include <linux/mm_types.h>
 #include <linux/gfp.h>
 #include <linux/sync_core.h>
+#include <linux/maple_tree.h>
 
 /*
  * Routines for handling mm_structs
@@ -67,11 +68,13 @@ static inline void mmdrop(struct mm_struct *mm)
  */
 static inline void mmget(struct mm_struct *mm)
 {
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)
 {
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }
 
kernel/fork.c +17 -5
index 8c7273b0d4b77..8fcbd970666c3 100644
@@ -472,7 +472,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
 	struct rb_node **rb_link, *rb_parent;
 	int retval;
-	unsigned long charge;
+	unsigned long charge = 0;
+	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 	LIST_HEAD(uf);
 
 	uprobe_start_dup_mmap();
@@ -506,7 +508,12 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		goto out;
 
 	prev = NULL;
-	for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
+
+	retval = mas_entry_count(&mas, oldmm->map_count);
+	if (retval)
+		goto fail_nomem;
+
+	mas_for_each(&old_mas, mpnt, ULONG_MAX) {
 		struct file *file;
 
 		if (mpnt->vm_flags & VM_DONTCOPY) {
@@ -520,7 +527,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		 */
 		if (fatal_signal_pending(current)) {
 			retval = -EINTR;
-			goto out;
+			goto loop_out;
 		}
 		if (mpnt->vm_flags & VM_ACCOUNT) {
 			unsigned long len = vma_pages(mpnt);
@@ -589,7 +596,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		rb_parent = &tmp->vm_rb;
 
 		/* Link the vma into the MT */
-		vma_store(mm, tmp);
+		mas.index = tmp->vm_start;
+		mas.last = tmp->vm_end - 1;
+		mas_store(&mas, tmp);
 
 		mm->map_count++;
 		if (!(tmp->vm_flags & VM_WIPEONFORK))
@@ -599,14 +608,16 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 			tmp->vm_ops->open(tmp);
 
 		if (retval)
-			goto out;
+			goto loop_out;
 	}
 	/* a new mm has just been created */
 	retval = arch_dup_mmap(oldmm, mm);
+loop_out:
 out:
 	mmap_write_unlock(mm);
 	flush_tlb_mm(oldmm);
 	mmap_write_unlock(oldmm);
+	mas_destroy(&mas);
 	dup_userfaultfd_complete(&uf);
 fail_uprobe_end:
 	uprobe_end_dup_mmap();
@@ -1076,6 +1087,7 @@ static inline void __mmput(struct mm_struct *mm)
 {
 	VM_BUG_ON(atomic_read(&mm->mm_users));
 
+	mt_clear_in_rcu(&mm->mm_mt);
 	uprobe_clear_state(mm);
 	exit_aio(mm);
 	ksm_exit(mm);
Signature · 1 line
2.28.0
#15 lore raw

PATCH v2 12/70 mm: Remove rb tree.

In reply to Liam R. Howlett

Remove the RB tree and start using the maple tree for vm_area_struct tracking.

---
 arch/x86/kernel/tboot.c    |   1 -
 drivers/firmware/efi/efi.c |   1 -
 include/linux/mm.h         |   4 -
 include/linux/mm_types.h   |  27 +-
 kernel/fork.c              |   8 -
 mm/init-mm.c               |   2 -
 mm/mmap.c                  | 527 ++++++++-----------------------------
 mm/util.c                  |   8 +
 8 files changed, 132 insertions(+), 446 deletions(-)
arch/x86/kernel/tboot.c +0 -1
index d9b1cc30976c4..9b97ffa23e0b0 100644
@@ -89,7 +89,6 @@ void __init tboot_probe(void)
 
 static pgd_t *tboot_pg_dir;
 static struct mm_struct tboot_mm = {
-	.mm_rb          = RB_ROOT,
 	.mm_mt          = MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd            = swapper_pg_dir,
 	.mm_users       = ATOMIC_INIT(2),
drivers/firmware/efi/efi.c +0 -1
index e40effbf028a6..665796649c23d 100644
@@ -54,7 +54,6 @@ static unsigned long __initdata mem_reserve = EFI_INVALID_TABLE_ADDR;
 static unsigned long __initdata rt_prop = EFI_INVALID_TABLE_ADDR;
 
 struct mm_struct efi_mm = {
-	.mm_rb			= RB_ROOT,
 	.mm_mt			= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.mm_users		= ATOMIC_INIT(2),
 	.mm_count		= ATOMIC_INIT(1),
include/linux/mm.h +0 -4
index 9cbbbbc3043a9..dbb83118eba09 100644
@@ -2467,8 +2467,6 @@ extern bool arch_has_descending_max_zone_pfns(void);
 /* nommu.c */
 extern atomic_long_t mmap_pages_allocated;
 extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
-/* maple_tree */
-void vma_store(struct mm_struct *mm, struct vm_area_struct *vma);
 
 /* interval_tree.c */
 void vma_interval_tree_insert(struct vm_area_struct *node,
@@ -2524,8 +2522,6 @@ extern int __split_vma(struct mm_struct *, struct vm_area_struct *,
 extern int split_vma(struct mm_struct *, struct vm_area_struct *,
 	unsigned long addr, int new_below);
 extern int insert_vm_struct(struct mm_struct *, struct vm_area_struct *);
-extern void __vma_link_rb(struct mm_struct *, struct vm_area_struct *,
-	struct rb_node **, struct rb_node *);
 extern void unlink_file_vma(struct vm_area_struct *);
 extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
 	unsigned long addr, unsigned long len, pgoff_t pgoff,
include/linux/mm_types.h +8 -19
index f2c725e1052f8..fa3cf29f01f21 100644
@@ -274,7 +274,6 @@ typedef unsigned long vm_flags_t;
  * map parts of them.
  */
 struct vm_region {
-	struct rb_node	vm_rb;		/* link in global region tree */
 	vm_flags_t	vm_flags;	/* VMA vm_flags */
 	unsigned long	vm_start;	/* start address of region */
 	unsigned long	vm_end;		/* region initialised to here */
@@ -312,19 +311,6 @@ struct vm_area_struct {
 
 	/* linked list of VM areas per task, sorted by address */
 	struct vm_area_struct *vm_next, *vm_prev;
-
-	struct rb_node vm_rb;
-
-	/*
-	 * Largest free memory gap in bytes to the left of this VMA.
-	 * Either between this VMA and vma->vm_prev, or between one of the
-	 * VMAs below us in the VMA rbtree and its ->vm_prev. This helps
-	 * get_unmapped_area find a free area of the right size.
-	 */
-	unsigned long rb_subtree_gap;
-
-	/* Second cache line starts here. */
-
 	struct mm_struct *vm_mm;	/* The address space we belong to. */
 
 	/*
@@ -334,6 +320,12 @@ struct vm_area_struct {
 	pgprot_t vm_page_prot;
 	unsigned long vm_flags;		/* Flags, see mm.h. */
 
+	/* Information about our backing store: */
+	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
+					 * units
+					 */
+	/* Second cache line starts here. */
+	struct file *vm_file;		/* File we map to (can be NULL). */
 	/*
 	 * For areas with an address space and backing store,
 	 * linkage into the address_space->i_mmap interval tree.
@@ -352,16 +344,14 @@ struct vm_area_struct {
 	struct list_head anon_vma_chain; /* Serialized by mmap_lock &
 					  * page_table_lock */
 	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */
+	/* Third cache line starts here. */
 
 	/* Function pointers to deal with this struct. */
 	const struct vm_operations_struct *vm_ops;
 
-	/* Information about our backing store: */
-	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
-					   units */
-	struct file * vm_file;		/* File we map to (can be NULL). */
 	void * vm_private_data;		/* was vm_pte (shared mem) */
 
+
 #ifdef CONFIG_SWAP
 	atomic_long_t swap_readahead_info;
 #endif
@@ -390,7 +380,6 @@ struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
-		struct rb_root mm_rb;
 		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
kernel/fork.c +0 -8
index 8fcbd970666c3..0ef4c4fa66c1b 100644
@@ -470,7 +470,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 					struct mm_struct *oldmm)
 {
 	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
-	struct rb_node **rb_link, *rb_parent;
 	int retval;
 	unsigned long charge = 0;
 	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
@@ -497,8 +496,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	mm->exec_vm = oldmm->exec_vm;
 	mm->stack_vm = oldmm->stack_vm;
 
-	rb_link = &mm->mm_rb.rb_node;
-	rb_parent = NULL;
 	pprev = &mm->mmap;
 	retval = ksm_fork(mm, oldmm);
 	if (retval)
@@ -591,10 +588,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		tmp->vm_prev = prev;
 		prev = tmp;
 
-		__vma_link_rb(mm, tmp, rb_link, rb_parent);
-		rb_link = &tmp->vm_rb.rb_right;
-		rb_parent = &tmp->vm_rb;
-
 		/* Link the vma into the MT */
 		mas.index = tmp->vm_start;
 		mas.last = tmp->vm_end - 1;
@@ -1017,7 +1010,6 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 	struct user_namespace *user_ns)
 {
 	mm->mmap = NULL;
-	mm->mm_rb = RB_ROOT;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
mm/init-mm.c +0 -2
index 27229044a0702..49d803fc4cdea 100644
@@ -1,6 +1,5 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/mm_types.h>
-#include <linux/rbtree.h>
 #include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/spinlock.h>
@@ -28,7 +27,6 @@
  * and size this cpu_bitmask to NR_CPUS.
  */
 struct mm_struct init_mm = {
-	.mm_rb		= RB_ROOT,
 	.mm_mt		= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd		= swapper_pg_dir,
 	.mm_users	= ATOMIC_INIT(2),
mm/mmap.c +116 -411

891 lines not on this page · raw message

mm/util.c +8 -0
index 4ddb6e186dd5c..48c79f2784eca 100644
@@ -287,6 +287,8 @@ void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
 	vma->vm_next = next;
 	if (next)
 		next->vm_prev = vma;
+	else
+		mm->highest_vm_end = vm_end_gap(vma);
 }
 
 void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
@@ -301,6 +303,12 @@ void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
 		mm->mmap = next;
 	if (next)
 		next->vm_prev = prev;
+	else {
+		if (prev)
+			mm->highest_vm_end = vm_end_gap(prev);
+		else
+			mm->highest_vm_end = 0;
+	}
 }
 
 /* Check if the vma is being used as a stack by this task */
Signature · 1 line
2.28.0
#16 lore raw

PATCH v2 13/70 mm/gup: Add mm_populate_vma() for use when the vma is known

In reply to Liam R. Howlett

When a vma is known, avoid calling mm_populate to search for the vma to populate.

---
 include/linux/mm.h |  4 ++++
 mm/gup.c           | 20 ++++++++++++++++++++
 2 files changed, 24 insertions(+)
include/linux/mm.h +4 -0
index dbb83118eba09..baaad07c43c99 100644
@@ -2587,8 +2587,12 @@ static inline void mm_populate(unsigned long addr, unsigned long len)
 	/* Ignore errors */
 	(void) __mm_populate(addr, len, 1);
 }
+extern void mm_populate_vma(struct vm_area_struct *vma, unsigned long start,
+			    unsigned long end);
 #else
 static inline void mm_populate(unsigned long addr, unsigned long len) {}
+void mm_populate_vma(struct vm_area_struct *vma, unsigned long start,
+		     unsigned long end) {}
 #endif
 
 /* These take the mm semaphore themselves */
mm/gup.c +20 -0
index 98eb8e6d2609c..b06e2a6d90187 100644
@@ -1431,6 +1431,26 @@ long populate_vma_page_range(struct vm_area_struct *vma,
 				NULL, NULL, locked);
 }
 
+/*
+ * mm_populate_vma() - Populate a single range in a single vma.
+ * @vma: The vma to populate.
+ * @start: The start address to populate
+ * @end: The end address to stop populating
+ *
+ * Note: Ignores errors.
+ */
+void mm_populate_vma(struct vm_area_struct *vma, unsigned long start,
+		unsigned long end)
+{
+	struct mm_struct *mm = current->mm;
+	int locked = 1;
+
+	mmap_read_lock(mm);
+	populate_vma_page_range(vma, start, end, &locked);
+	if (locked)
+		mmap_read_unlock(mm);
+}
+
 /*
  * __mm_populate - populate and/or mlock pages within a range of address space.
  *
Signature · 1 line
2.28.0
#17 lore raw

PATCH v2 14/70 mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap()

In reply to Liam R. Howlett

Avoid allocating a new VMA when it is not necessary. Expand or contract the existing VMA instead. This avoids unnecessary tree manipulations and allocations.

Once the VMA is known, use it directly when populating to avoid unnecessary lookup work.

---
 mm/mmap.c | 299 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 237 insertions(+), 62 deletions(-)
mm/mmap.c +237 -62
index a2b32202191d6..f500d5e490f1c 100644
@@ -51,7 +51,6 @@
 #include <asm/cacheflush.h>
 #include <asm/tlb.h>
 #include <asm/mmu_context.h>
-
 #define CREATE_TRACE_POINTS
 #include <trace/events/mmap.h>
 
@@ -184,18 +183,22 @@ static struct vm_area_struct *remove_vma(struct vm_area_struct *vma)
 	return next;
 }
 
-static int do_brk_flags(unsigned long addr, unsigned long request, unsigned long flags,
-		struct list_head *uf);
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf);
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,
+			unsigned long addr, unsigned long request,
+			unsigned long flags);
 SYSCALL_DEFINE1(brk, unsigned long, brk)
 {
-	unsigned long retval;
 	unsigned long newbrk, oldbrk, origbrk;
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *next;
+	struct vm_area_struct *brkvma, *next = NULL;
 	unsigned long min_brk;
 	bool populate;
 	bool downgraded = false;
 	LIST_HEAD(uf);
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	if (mmap_write_lock_killable(mm))
 		return -EINTR;
@@ -235,37 +238,49 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 		goto success;
 	}
 
-	/*
-	 * Always allow shrinking brk.
-	 * __do_munmap() may downgrade mmap_lock to read.
-	 */
-	if (brk <= mm->brk) {
+	mas_set(&mas, newbrk);
+	brkvma = mas_walk(&mas);
+	if (brkvma) { // munmap necessary, there is something at newbrk.
+		/*
+		 * Always allow shrinking brk.
+		 * do_brk_munmap() may downgrade mmap_lock to read.
+		 */
 		int ret;
 
+		if (brkvma->vm_start >= oldbrk)
+			goto out; // mapping intersects with an existing non-brk vma.
 		/*
-		 * mm->brk must to be protected by write mmap_lock so update it
-		 * before downgrading mmap_lock. When __do_munmap() fails,
-		 * mm->brk will be restored from origbrk.
+		 * mm->brk must to be protected by write mmap_lock.
+		 * do_brk_munmap() may downgrade the lock,  so update it
+		 * before calling do_brk_munmap().
 		 */
 		mm->brk = brk;
-		ret = __do_munmap(mm, newbrk, oldbrk-newbrk, &uf, true);
-		if (ret < 0) {
-			mm->brk = origbrk;
-			goto out;
-		} else if (ret == 1) {
+		mas.last = oldbrk - 1;
+		ret = do_brk_munmap(&mas, brkvma, newbrk, oldbrk, &uf);
+		if (ret == 1)  {
 			downgraded = true;
-		}
-		goto success;
-	}
+			goto success;
+		} else if (!ret)
+			goto success;
 
+		mm->brk = origbrk;
+		goto out;
+	}
+	/* Only check if the next VMA is within the stack_guard_gap of the
+	 * expansion area */
+	next = mas_next(&mas, newbrk + PAGE_SIZE + stack_guard_gap);
 	/* Check against existing mmap mappings. */
-	next = find_vma(mm, oldbrk);
 	if (next && newbrk + PAGE_SIZE > vm_start_gap(next))
 		goto out;
 
+	brkvma = mas_prev(&mas, mm->start_brk);
+	if (brkvma && (brkvma->vm_start >= oldbrk))
+		goto out; // Trying to map over another vma.
+
 	/* Ok, looks good - let it rip. */
-	if (do_brk_flags(oldbrk, newbrk-oldbrk, 0, &uf) < 0)
+	if (do_brk_flags(&mas, &brkvma, oldbrk, newbrk - oldbrk, 0) < 0)
 		goto out;
+
 	mm->brk = brk;
 
 success:
@@ -276,13 +291,12 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 		mmap_write_unlock(mm);
 	userfaultfd_unmap_complete(mm, &uf);
 	if (populate)
-		mm_populate(oldbrk, newbrk - oldbrk);
+		mm_populate_vma(brkvma, oldbrk, newbrk);
 	return brk;
 
 out:
-	retval = origbrk;
 	mmap_write_unlock(mm);
-	return retval;
+	return origbrk;
 }
 
 #if defined(CONFIG_DEBUG_MAPLE_TREE)
@@ -367,16 +381,16 @@ static void validate_mm(struct mm_struct *mm)
 	validate_mm_mt(mm);
 
 	while (vma) {
+#ifdef CONFIG_DEBUG_VM_RB
 		struct anon_vma *anon_vma = vma->anon_vma;
 		struct anon_vma_chain *avc;
-
 		if (anon_vma) {
 			anon_vma_lock_read(anon_vma);
 			list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
 				anon_vma_interval_tree_verify(avc);
 			anon_vma_unlock_read(anon_vma);
 		}
-
+#endif
 		highest_address = vm_end_gap(vma);
 		vma = vma->vm_next;
 		i++;
@@ -537,6 +551,39 @@ static void __vma_link_file(struct vm_area_struct *vma)
 	}
 }
 
+/*
+ * vma_mas_store() - Store a VMA in the maple tree.
+ * @vma: The vm_area_struct
+ * @mas: The maple state
+ *
+ * Efficient way to store a VMA in the maple tree when the @mas has already
+ * walked to the correct location.
+ *
+ * Note: the end address is inclusive in the maple tree.
+ */
+static inline int vma_mas_store(struct vm_area_struct *vma, struct ma_state *mas)
+{
+	mas->index = vma->vm_start;
+	mas->last = vma->vm_end - 1;
+	return mas_store_gfp(mas, vma, GFP_KERNEL);
+}
+
+/*
+ * vma_mas_remove() - Remove a VMA from the maple tree.
+ * @vma: The vm_area_struct
+ * @mas: The maple state
+ *
+ * Efficient way to remove a VMA from the maple tree when the @mas has already
+ * been established and points to the correct location.
+ * Note: the end address is inclusive in the maple tree.
+ */
+static inline int vma_mas_remove(struct vm_area_struct *vma, struct ma_state *mas)
+{
+	mas->index = vma->vm_start;
+	mas->last = vma->vm_end - 1;
+	return mas_store_gfp(mas, NULL, GFP_KERNEL);
+}
+
 /*
  * vma_mt_szero() - Set a given range to zero.  Used when modifying a
  * vm_area_struct start or end.
@@ -565,6 +612,7 @@ static inline void vma_mt_store(struct mm_struct *mm, struct vm_area_struct *vma
 		GFP_KERNEL);
 }
 
+
 static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 			struct vm_area_struct *prev)
 {
@@ -1806,7 +1854,6 @@ static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 
 	if (mas_get_empty_area(&mas, info->low_limit, info->high_limit - 1,
 				  length)) {
-		rcu_read_unlock();
 		return -ENOMEM;
 	}
 	gap = mas.index;
@@ -1835,7 +1882,6 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 
 	if (mas_get_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
 				length)) {
-		rcu_read_unlock();
 		return -ENOMEM;
 	}
 	gap = (mas.index + info->align_mask) & ~info->align_mask;
@@ -2022,8 +2068,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 EXPORT_SYMBOL(get_unmapped_area);
 
 /**
- * find_vma() - Find the VMA for a given address, or the next vma.  May return
- * NULL in the case of no vma at addr or above
+ * find_vma() - Find the VMA for a given address, or the next vma.
  * @mm The mm_struct to check
  * @addr: The address
  *
@@ -2033,13 +2078,16 @@ EXPORT_SYMBOL(get_unmapped_area);
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, start_addr, start_addr);
 
 	/* Check the cache first. */
 	vma = vmacache_find(mm, addr);
 	if (likely(vma))
 		return vma;
 
-	vma = mt_find(&mm->mm_mt, &addr, ULONG_MAX);
+	rcu_read_lock();
+	vma = mas_find(&mas, end_addr - 1);
+	rcu_read_unlock();
 	if (vma)
 		vmacache_update(addr, vma);
 
@@ -2777,16 +2825,102 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
 }
 
 /*
- *  this is really a simplified "do_mmap".  it only handles
- *  anonymous maps.  eventually we may be able to do some
- *  brk-specific accounting here.
+ * bkr_munmap() - Unmap a parital vma.
+ * @mas: The maple tree state.
+ * @vma: The vma to be modified
+ * @newbrk: the start of the address to unmap
+ * @oldbrk: The end of the address to unmap
+ *
+ * Returns: 0 on success.
+ * unmaps a partial VMA mapping.  Does not handle alignment, downgrades lock if
+ * possible.
  */
-static int do_brk_flags(unsigned long addr, unsigned long len,
-			unsigned long flags, struct list_head *uf)
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf)
+{
+	struct mm_struct *mm = vma->vm_mm;
+	struct vm_area_struct unmap;
+	unsigned long unmap_pages;
+	int ret = 1;
+
+	arch_unmap(mm, newbrk, oldbrk);
+
+	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
+		mas_set(mas, newbrk);
+		if (vma->vm_start != newbrk)
+			mas_reset(mas); // cause a re-walk for the first overlap.
+		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
+		goto munmap_full_vma;
+	}
+
+	vma_init(&unmap, mm);
+	unmap.vm_start = newbrk;
+	unmap.vm_end = oldbrk;
+	ret = userfaultfd_unmap_prep(&unmap, newbrk, oldbrk, uf);
+	if (ret)
+		return ret;
+	ret = 1;
+
+	// Change the oldbrk of vma to the newbrk of the munmap area
+	vma_adjust_trans_huge(vma, vma->vm_start, newbrk, 0);
+	if (vma->anon_vma) {
+		anon_vma_lock_write(vma->anon_vma);
+		anon_vma_interval_tree_pre_update_vma(vma);
+	}
+
+	vma->vm_end = newbrk;
+	if (vma_mas_remove(&unmap, mas))
+		goto mas_store_fail;
+
+	vmacache_invalidate(vma->vm_mm);
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+
+	unmap_pages = vma_pages(&unmap);
+	if (unmap.vm_flags & VM_LOCKED) {
+		mm->locked_vm -= unmap_pages;
+		munlock_vma_pages_range(&unmap, newbrk, oldbrk);
+	}
+
+	mmap_write_downgrade(mm);
+	unmap_region(mm, &unmap, vma, newbrk, oldbrk);
+	/* Statistics */
+	vm_stat_account(mm, unmap.vm_flags, -unmap_pages);
+	if (unmap.vm_flags & VM_ACCOUNT)
+		vm_unacct_memory(unmap_pages);
+
+munmap_full_vma:
+	validate_mm_mt(mm);
+	return ret;
+
+mas_store_fail:
+	vma->vm_end = oldbrk;
+	anon_vma_interval_tree_post_update_vma(vma);
+	anon_vma_unlock_write(vma->anon_vma);
+	return -ENOMEM;
+}
+
+/*
+ * do_brk_flags() - Increase the brk vma if the flags match.
+ * @mas: The maple tree state.
+ * @addr: The start address
+ * @len: The length of the increase
+ * @vma: The vma,
+ * @flags: The VMA Flags
+ *
+ * Extend the brk VMA from addr to addr + len.  If the VMA is NULL or the flags
+ * do not match then create a new anonymous VMA.  Eventually we may be able to
+ * do some brk-specific accounting here.
+ */
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,
+			unsigned long addr, unsigned long len,
+			unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma, *prev;
-	pgoff_t pgoff = addr >> PAGE_SHIFT;
+	struct vm_area_struct *prev = NULL, *vma;
 	int error;
 	unsigned long mapped_addr;
 	validate_mm_mt(mm);
@@ -2804,11 +2938,7 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	if (error)
 		return error;
 
-	/* Clear old maps, set up prev and uf */
-	if (munmap_vma_range(mm, addr, len, &prev, uf))
-		return -ENOMEM;
-
-	/* Check against address space limits *after* clearing old maps... */
+	/* Check against address space limits by the changed size */
 	if (!may_expand_vm(mm, flags, len >> PAGE_SHIFT))
 		return -ENOMEM;
 
@@ -2818,28 +2948,58 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	if (security_vm_enough_memory_mm(mm, len >> PAGE_SHIFT))
 		return -ENOMEM;
 
-	/* Can we just expand an old private anonymous mapping? */
-	vma = vma_merge(mm, prev, addr, addr + len, flags,
-			NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
-	if (vma)
-		goto out;
+	mas->last = addr + len - 1;
+	if (*brkvma) {
+		vma = *brkvma;
+		/* Expand the existing vma if possible; almost never a singular
+		 * list, so this will almost always fail. */
 
-	/*
-	 * create a vma struct for an anonymous mapping
-	 */
-	vma = vm_area_alloc(mm);
-	if (!vma) {
-		vm_unacct_memory(len >> PAGE_SHIFT);
-		return -ENOMEM;
+		if ((!vma->anon_vma ||
+		     list_is_singular(&vma->anon_vma_chain)) &&
+		     ((vma->vm_flags & ~VM_SOFTDIRTY) == flags)){
+			mas->index = vma->vm_start;
+
+			vma_adjust_trans_huge(vma, addr, addr + len, 0);
+			if (vma->anon_vma) {
+				anon_vma_lock_write(vma->anon_vma);
+				anon_vma_interval_tree_pre_update_vma(vma);
+			}
+			vma->vm_end = addr + len;
+			vma->vm_flags |= VM_SOFTDIRTY;
+			if (mas_store_gfp(mas, vma, GFP_KERNEL))
+				goto mas_mod_fail;
+			if (vma->anon_vma) {
+				anon_vma_interval_tree_post_update_vma(vma);
+				anon_vma_unlock_write(vma->anon_vma);
+			}
+			khugepaged_enter_vma_merge(vma, flags);
+			goto out;
+		}
+		prev = vma;
 	}
+	mas->index = addr;
+	mas_walk(mas);
+
+	/* create a vma struct for an anonymous mapping */
+	vma = vm_area_alloc(mm);
+	if (!vma)
+		goto vma_alloc_fail;
 
 	vma_set_anonymous(vma);
 	vma->vm_start = addr;
 	vma->vm_end = addr + len;
-	vma->vm_pgoff = pgoff;
+	vma->vm_pgoff = addr >> PAGE_SHIFT;
 	vma->vm_flags = flags;
 	vma->vm_page_prot = vm_get_page_prot(flags);
-	vma_link(mm, vma, prev);
+	if (vma_mas_store(vma, mas))
+		goto mas_store_fail;
+
+	if (!prev)
+		prev = mas_prev(mas, 0);
+
+	__vma_link_list(mm, vma, prev);
+	mm->map_count++;
+	*brkvma = vma;
 out:
 	perf_event_mmap(vma);
 	mm->total_vm += len >> PAGE_SHIFT;
@@ -2849,15 +3009,29 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	vma->vm_flags |= VM_SOFTDIRTY;
 	validate_mm_mt(mm);
 	return 0;
+
+mas_store_fail:
+	vm_area_free(vma);
+vma_alloc_fail:
+	vm_unacct_memory(len >> PAGE_SHIFT);
+	return -ENOMEM;
+
+mas_mod_fail:
+	vma->vm_end = addr;
+	anon_vma_interval_tree_post_update_vma(vma);
+	anon_vma_unlock_write(vma->anon_vma);
+	return -ENOMEM;
+
 }
 
 int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
+	struct vm_area_struct *vma = NULL;
 	unsigned long len;
 	int ret;
 	bool populate;
-	LIST_HEAD(uf);
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	len = PAGE_ALIGN(request);
 	if (len < request)
@@ -2868,10 +3042,11 @@ int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
 	if (mmap_write_lock_killable(mm))
 		return -EINTR;
 
-	ret = do_brk_flags(addr, len, flags, &uf);
+	// This vma left intentionally blank.
+	mas_walk(&mas);
+	ret = do_brk_flags(&mas, &vma, addr, len, flags);
 	populate = ((mm->def_flags & VM_LOCKED) != 0);
 	mmap_write_unlock(mm);
-	userfaultfd_unmap_complete(mm, &uf);
 	if (populate && !ret)
 		mm_populate(addr, len);
 	return ret;
Signature · 1 line
2.28.0
reviewer
#18 lore raw

Re: [PATCH v2 14/70] mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap()

Hi--

Quoted 20 lines · Liam R. Howlett

Avoid allocating a new VMA when it is not necessary. Expand or contract the existing VMA instead. This avoids unnecessary tree manipulations and allocations.

Once the VMA is known, use it directly when populating to avoid unnecessary lookup work.

---
 mm/mmap.c | 299 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 237 insertions(+), 62 deletions(-)
mm/mmap.c +0 -0
index a2b32202191d6..f500d5e490f1c 100644

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2072

Quoted 7 lines
mm/mmap.c +1 -2
@@ -2022,8 +2068,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 EXPORT_SYMBOL(get_unmapped_area);
 
 /**
- * find_vma() - Find the VMA for a given address, or the next vma.  May return
- * NULL in the case of no vma at addr or above
+ * find_vma() - Find the VMA for a given address, or the next vma.
  * @mm The mm_struct to check

* @mm: ...

Quoted 4 lines
mm/mmap.c +0 -0
  * @addr: The address
  *
@@ -2777,16 +2825,102 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
 }

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2832

Quoted 10 lines
mm/mmap.c +5 -3
 
 /*
- *  this is really a simplified "do_mmap".  it only handles
- *  anonymous maps.  eventually we may be able to do some
- *  brk-specific accounting here.
+ * bkr_munmap() - Unmap a parital vma.
+ * @mas: The maple tree state.
+ * @vma: The vma to be modified
+ * @newbrk: the start of the address to unmap
+ * @oldbrk: The end of the address to unmap

missing:
* @uf: ...

Quoted 71 lines
mm/mmap.c +68 -2
+ *
+ * Returns: 0 on success.
+ * unmaps a partial VMA mapping.  Does not handle alignment, downgrades lock if
+ * possible.
  */
-static int do_brk_flags(unsigned long addr, unsigned long len,
-			unsigned long flags, struct list_head *uf)
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf)
+{
+	struct mm_struct *mm = vma->vm_mm;
+	struct vm_area_struct unmap;
+	unsigned long unmap_pages;
+	int ret = 1;
+
+	arch_unmap(mm, newbrk, oldbrk);
+
+	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
+		mas_set(mas, newbrk);
+		if (vma->vm_start != newbrk)
+			mas_reset(mas); // cause a re-walk for the first overlap.
+		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
+		goto munmap_full_vma;
+	}
+
+	vma_init(&unmap, mm);
+	unmap.vm_start = newbrk;
+	unmap.vm_end = oldbrk;
+	ret = userfaultfd_unmap_prep(&unmap, newbrk, oldbrk, uf);
+	if (ret)
+		return ret;
+	ret = 1;
+
+	// Change the oldbrk of vma to the newbrk of the munmap area
+	vma_adjust_trans_huge(vma, vma->vm_start, newbrk, 0);
+	if (vma->anon_vma) {
+		anon_vma_lock_write(vma->anon_vma);
+		anon_vma_interval_tree_pre_update_vma(vma);
+	}
+
+	vma->vm_end = newbrk;
+	if (vma_mas_remove(&unmap, mas))
+		goto mas_store_fail;
+
+	vmacache_invalidate(vma->vm_mm);
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+
+	unmap_pages = vma_pages(&unmap);
+	if (unmap.vm_flags & VM_LOCKED) {
+		mm->locked_vm -= unmap_pages;
+		munlock_vma_pages_range(&unmap, newbrk, oldbrk);
+	}
+
+	mmap_write_downgrade(mm);
+	unmap_region(mm, &unmap, vma, newbrk, oldbrk);
+	/* Statistics */
+	vm_stat_account(mm, unmap.vm_flags, -unmap_pages);
+	if (unmap.vm_flags & VM_ACCOUNT)
+		vm_unacct_memory(unmap_pages);
+
+munmap_full_vma:
+	validate_mm_mt(mm);
+	return ret;
+
+mas_store_fail:
+	vma->vm_end = oldbrk;
+	anon_vma_interval_tree_post_update_vma(vma);

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2911

Quoted 10 lines
mm/mmap.c +10 -0
+	anon_vma_unlock_write(vma->anon_vma);
+	return -ENOMEM;
+}
+
+/*
+ * do_brk_flags() - Increase the brk vma if the flags match.
+ * @mas: The maple tree state.
+ * @addr: The start address
+ * @len: The length of the increase
+ * @vma: The vma,

s/@vma/@brkvma/ ??

Quoted 7 lines
mm/mmap.c +7 -0
+ * @flags: The VMA Flags
+ *
+ * Extend the brk VMA from addr to addr + len.  If the VMA is NULL or the flags
+ * do not match then create a new anonymous VMA.  Eventually we may be able to
+ * do some brk-specific accounting here.
+ */
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2926

Quoted 10 lines
mm/mmap.c +3 -2
+			unsigned long addr, unsigned long len,
+			unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma, *prev;
-	pgoff_t pgoff = addr >> PAGE_SHIFT;
+	struct vm_area_struct *prev = NULL, *vma;
 	int error;
 	unsigned long mapped_addr;
 	validate_mm_mt(mm);

thanks.

Signature · 1 line
~Randy
#19 lore raw

Re: [PATCH v2 14/70] mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap()

Quoted 25 lines · Randy Dunlap

Hi--

Quoted 22 lines · Liam R. Howlett

Avoid allocating a new VMA when it is not necessary. Expand or contract the existing VMA instead. This avoids unnecessary tree manipulations and allocations.

Once the VMA is known, use it directly when populating to avoid unnecessary lookup work.

---
 mm/mmap.c | 299 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 237 insertions(+), 62 deletions(-)
mm/mmap.c +0 -0
index a2b32202191d6..f500d5e490f1c 100644
@@ -2022,8 +2068,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 EXPORT_SYMBOL(get_unmapped_area);
 
Quoted 7 lines

mm/mmap.c get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, · line 2072

Quoted 5 lines
mm/mmap.c +1 -2
 /**
- * find_vma() - Find the VMA for a given address, or the next vma.  May return
- * NULL in the case of no vma at addr or above
+ * find_vma() - Find the VMA for a given address, or the next vma.
  * @mm The mm_struct to check

* @mm: ...

Ack

Quoted 6 lines
Quoted 6 lines
mm/mmap.c +0 -0
  * @addr: The address
  *
@@ -2777,16 +2825,102 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
 }
 
Quoted 12 lines

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2832

Quoted 9 lines
mm/mmap.c +5 -3
 /*
- *  this is really a simplified "do_mmap".  it only handles
- *  anonymous maps.  eventually we may be able to do some
- *  brk-specific accounting here.
+ * bkr_munmap() - Unmap a parital vma.
+ * @mas: The maple tree state.
+ * @vma: The vma to be modified
+ * @newbrk: the start of the address to unmap
+ * @oldbrk: The end of the address to unmap

missing:
* @uf: ...

Thanks, yes. I will add the user fault.

Quoted 76 lines
Quoted 76 lines
mm/mmap.c +72 -2
+ *
+ * Returns: 0 on success.
+ * unmaps a partial VMA mapping.  Does not handle alignment, downgrades lock if
+ * possible.
  */
-static int do_brk_flags(unsigned long addr, unsigned long len,
-			unsigned long flags, struct list_head *uf)
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf)
+{
+	struct mm_struct *mm = vma->vm_mm;
+	struct vm_area_struct unmap;
+	unsigned long unmap_pages;
+	int ret = 1;
+
+	arch_unmap(mm, newbrk, oldbrk);
+
+	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
+		mas_set(mas, newbrk);
+		if (vma->vm_start != newbrk)
+			mas_reset(mas); // cause a re-walk for the first overlap.
+		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
+		goto munmap_full_vma;
+	}
+
+	vma_init(&unmap, mm);
+	unmap.vm_start = newbrk;
+	unmap.vm_end = oldbrk;
+	ret = userfaultfd_unmap_prep(&unmap, newbrk, oldbrk, uf);
+	if (ret)
+		return ret;
+	ret = 1;
+
+	// Change the oldbrk of vma to the newbrk of the munmap area
+	vma_adjust_trans_huge(vma, vma->vm_start, newbrk, 0);
+	if (vma->anon_vma) {
+		anon_vma_lock_write(vma->anon_vma);
+		anon_vma_interval_tree_pre_update_vma(vma);
+	}
+
+	vma->vm_end = newbrk;
+	if (vma_mas_remove(&unmap, mas))
+		goto mas_store_fail;
+
+	vmacache_invalidate(vma->vm_mm);
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+
+	unmap_pages = vma_pages(&unmap);
+	if (unmap.vm_flags & VM_LOCKED) {
+		mm->locked_vm -= unmap_pages;
+		munlock_vma_pages_range(&unmap, newbrk, oldbrk);
+	}
+
+	mmap_write_downgrade(mm);
+	unmap_region(mm, &unmap, vma, newbrk, oldbrk);
+	/* Statistics */
+	vm_stat_account(mm, unmap.vm_flags, -unmap_pages);
+	if (unmap.vm_flags & VM_ACCOUNT)
+		vm_unacct_memory(unmap_pages);
+
+munmap_full_vma:
+	validate_mm_mt(mm);
+	return ret;
+
+mas_store_fail:
+	vma->vm_end = oldbrk;
+	anon_vma_interval_tree_post_update_vma(vma);
+	anon_vma_unlock_write(vma->anon_vma);
+	return -ENOMEM;
+}
+
Quoted 8 lines

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2911

Quoted 6 lines
mm/mmap.c +6 -0
+/*
+ * do_brk_flags() - Increase the brk vma if the flags match.
+ * @mas: The maple tree state.
+ * @addr: The start address
+ * @len: The length of the increase
+ * @vma: The vma,

s/@vma/@brkvma/ ??

yes, sorry. I tried to clarify the name in a later revision.

Quoted 10 lines
Quoted 10 lines
mm/mmap.c +9 -0
+ * @flags: The VMA Flags
+ *
+ * Extend the brk VMA from addr to addr + len.  If the VMA is NULL or the flags
+ * do not match then create a new anonymous VMA.  Eventually we may be able to
+ * do some brk-specific accounting here.
+ */
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,
+			unsigned long addr, unsigned long len,
+			unsigned long flags)
Quoted 12 lines

mm/mmap.c SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size, · line 2926

Quoted 8 lines
mm/mmap.c +1 -2
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma, *prev;
-	pgoff_t pgoff = addr >> PAGE_SHIFT;
+	struct vm_area_struct *prev = NULL, *vma;
 	int error;
 	unsigned long mapped_addr;
 	validate_mm_mt(mm);

Thank you for looking at this. I will fix all the issues you have pointed out across the three emails.

Thanks,
Liam

#20 lore raw

PATCH v2 15/70 mm/mmap: Change vm_brk_flags() to use mm_populate_vma()

In reply to Liam R. Howlett

Skip searching for the vma to populate after creating it by passing in a pointer.

---
 mm/mmap.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
mm/mmap.c +2 -2
index f500d5e490f1c..cab665a6daa05 100644
@@ -3045,10 +3045,10 @@ int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
 	// This vma left intentionally blank.
 	mas_walk(&mas);
 	ret = do_brk_flags(&mas, &vma, addr, len, flags);
-	populate = ((mm->def_flags & VM_LOCKED) != 0);
 	mmap_write_unlock(mm);
+	populate = ((mm->def_flags & VM_LOCKED) != 0);
 	if (populate && !ret)
-		mm_populate(addr, len);
+		mm_populate_vma(vma, addr, addr + len);
 	return ret;
 }
 EXPORT_SYMBOL(vm_brk_flags);
Signature · 1 line
2.28.0
#21 lore raw

PATCH v2 16/70 mm: Move find_vma_intersection to mmap.c and change implementation to maple tree.

In reply to Liam R. Howlett

When searching for a vma within a range, it is easier to use the maple tree interface. This means the find_vma() call changes to a special case of the find_vma_intersection(). Exported for kvm module.

---
 include/linux/mm.h | 10 ++--------
 mm/mmap.c          | 41 ++++++++++++++++++++++++++++-------------
 2 files changed, 30 insertions(+), 21 deletions(-)
include/linux/mm.h +2 -8
index baaad07c43c99..996353a057500 100644
@@ -2651,14 +2651,8 @@ extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned lon
 
 /* Look up the first VMA which intersects the interval start_addr..end_addr-1,
    NULL if none.  Assume start_addr < end_addr. */
-static inline struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
-{
-	struct vm_area_struct * vma = find_vma(mm,start_addr);
-
-	if (vma && end_addr <= vma->vm_start)
-		vma = NULL;
-	return vma;
-}
+extern struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
+		     unsigned long start_addr, unsigned long end_addr);
 
 static inline unsigned long vm_start_gap(struct vm_area_struct *vma)
 {
mm/mmap.c +28 -13

60 lines not on this page · raw message

Signature · 1 line
2.28.0
#22 lore raw

PATCH v2 17/70 mm/mmap: Change mmap_region to use maple tree state

In reply to Liam R. Howlett
---
 lib/maple_tree.c |   1 +
 mm/mmap.c        | 227 ++++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 195 insertions(+), 33 deletions(-)
lib/maple_tree.c +1 -0
index c24c6f154c857..522f5fdfe5078 100644
@@ -3566,6 +3566,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite
 	if (ret > 2)
 		return NULL;
 spanning_store:
+
 	return content;
 }
 
mm/mmap.c +194 -33

344 lines not on this page · raw message

Signature · 1 line
2.28.0
#23 lore raw

PATCH v2 18/70 mm/mmap: Drop munmap_vma_range()

In reply to Liam R. Howlett
---
 mm/mmap.c | 23 -----------------------
 1 file changed, 23 deletions(-)
mm/mmap.c +0 -23
index d3dfea031c0d5..1cef158c31909 100644
@@ -483,29 +483,6 @@ static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
 	return vma->vm_next;
 }
 
-/*
- * munmap_vma_range() - munmap VMAs that overlap a range.
- * @mm: The mm struct
- * @start: The start of the range.
- * @len: The length of the range.
- * @pprev: pointer to the pointer that will be set to previous vm_area_struct
- *
- * Find all the vm_area_struct that overlap from @start to
- * @end and munmap them.  Set @pprev to the previous vm_area_struct.
- *
- * Returns: -ENOMEM on munmap failure or 0 on success.
- */
-static inline int
-munmap_vma_range(struct mm_struct *mm, unsigned long start, unsigned long len,
-		 struct vm_area_struct **pprev, struct list_head *uf)
-{
-	// Needs optimization.
-	while (range_has_overlap(mm, start, start + len, pprev)) {
-		if (do_munmap(mm, start, len, uf))
-			return -ENOMEM;
-	}
-	return 0;
-}
 static unsigned long count_vma_pages_range(struct mm_struct *mm,
 		unsigned long addr, unsigned long end)
 {
Signature · 1 line
2.28.0
#24 lore raw

PATCH v2 19/70 mm: Remove vmacache

In reply to Liam R. Howlett

The maple tree is able to find a VMA quick enough to no longer need the vma cache. Remove the vmacache to reduce work in keeping it up to date and code complexity.

---
 fs/exec.c                     |   3 -
 fs/proc/task_mmu.c            |   1 -
 include/linux/mm_types.h      |   1 -
 include/linux/mm_types_task.h |   5 --
 include/linux/sched.h         |   1 -
 include/linux/vmacache.h      |  28 --------
 kernel/debug/debug_core.c     |  12 ----
 kernel/fork.c                 |   5 --
 mm/Makefile                   |   2 +-
 mm/debug.c                    |   4 +-
 mm/mmap.c                     |  20 ------
 mm/vmacache.c                 | 117 ----------------------------------
 12 files changed, 3 insertions(+), 196 deletions(-)
 delete mode 100644 include/linux/vmacache.h
 delete mode 100644 mm/vmacache.c
fs/exec.c +0 -3
index 547a2390baf54..aa466921d6a97 100644
@@ -28,7 +28,6 @@
 #include <linux/file.h>
 #include <linux/fdtable.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/stat.h>
 #include <linux/fcntl.h>
 #include <linux/swap.h>
@@ -1019,8 +1018,6 @@ static int exec_mmap(struct mm_struct *mm)
 	activate_mm(active_mm, mm);
 	if (IS_ENABLED(CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM))
 		local_irq_enable();
-	tsk->mm->vmacache_seqnum = 0;
-	vmacache_flush(tsk);
 	task_unlock(tsk);
 	if (old_mm) {
 		mmap_read_unlock(old_mm);
fs/proc/task_mmu.c +0 -1
index ee5a235b30562..1ec2dd34ebffd 100644
@@ -1,6 +1,5 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/pagewalk.h>
-#include <linux/vmacache.h>
 #include <linux/hugetlb.h>
 #include <linux/huge_mm.h>
 #include <linux/mount.h>
include/linux/mm_types.h +0 -1
index fa3cf29f01f21..5a85b76bb9b9a 100644
@@ -380,7 +380,6 @@ struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
-		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
 				unsigned long addr, unsigned long len,
include/linux/mm_types_task.h +0 -5
index c1bc6731125cb..33c9fa4d4f66a 100644
@@ -31,11 +31,6 @@
 #define VMACACHE_SIZE (1U << VMACACHE_BITS)
 #define VMACACHE_MASK (VMACACHE_SIZE - 1)
 
-struct vmacache {
-	u64 seqnum;
-	struct vm_area_struct *vmas[VMACACHE_SIZE];
-};
-
 /*
  * When updating this, please also update struct resident_page_types[] in
  * kernel/fork.c
include/linux/sched.h +0 -1
index 76cd21fa55016..418a44dabc37e 100644
@@ -758,7 +758,6 @@ struct task_struct {
 	struct mm_struct		*active_mm;
 
 	/* Per-thread vma caching: */
-	struct vmacache			vmacache;
 
 #ifdef SPLIT_RSS_COUNTING
 	struct task_rss_stat		rss_stat;
include/linux/vmacache.h deleted +0 -28
deleted file mode 100644
index 6fce268a4588e..0000000000000
@@ -1,28 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-#ifndef __LINUX_VMACACHE_H
-#define __LINUX_VMACACHE_H
-
-#include <linux/sched.h>
-#include <linux/mm.h>
-
-static inline void vmacache_flush(struct task_struct *tsk)
-{
-	memset(tsk->vmacache.vmas, 0, sizeof(tsk->vmacache.vmas));
-}
-
-extern void vmacache_update(unsigned long addr, struct vm_area_struct *newvma);
-extern struct vm_area_struct *vmacache_find(struct mm_struct *mm,
-						    unsigned long addr);
-
-#ifndef CONFIG_MMU
-extern struct vm_area_struct *vmacache_find_exact(struct mm_struct *mm,
-						  unsigned long start,
-						  unsigned long end);
-#endif
-
-static inline void vmacache_invalidate(struct mm_struct *mm)
-{
-	mm->vmacache_seqnum++;
-}
-
-#endif /* __LINUX_VMACACHE_H */
kernel/debug/debug_core.c +0 -12
index 1e75a8923a8d1..f6e7156088ea7 100644
@@ -53,7 +53,6 @@
 #include <linux/pid.h>
 #include <linux/smp.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/rcupdate.h>
 #include <linux/irq.h>
 
@@ -286,17 +285,6 @@ static void kgdb_flush_swbreak_addr(unsigned long addr)
 	if (!CACHE_FLUSH_IS_SAFE)
 		return;
 
-	if (current->mm) {
-		int i;
-
-		for (i = 0; i < VMACACHE_SIZE; i++) {
-			if (!current->vmacache.vmas[i])
-				continue;
-			flush_cache_range(current->vmacache.vmas[i],
-					  addr, addr + BREAK_INSTR_SIZE);
-		}
-	}
-
 	/* Force flush instruction cache if it was outside the mm */
 	flush_icache_range(addr, addr + BREAK_INSTR_SIZE);
 }
kernel/fork.c +0 -5
index 0ef4c4fa66c1b..b8c25c2e9587f 100644
@@ -42,7 +42,6 @@
 #include <linux/mmu_notifier.h>
 #include <linux/fs.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/nsproxy.h>
 #include <linux/capability.h>
 #include <linux/cpu.h>
@@ -1011,7 +1010,6 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 {
 	mm->mmap = NULL;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
-	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
 	mmap_init_lock(mm);
@@ -1408,9 +1406,6 @@ static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
 	if (!oldmm)
 		return 0;
 
-	/* initialize the new vmacache entries */
-	vmacache_flush(tsk);
-
 	if (clone_flags & CLONE_VM) {
 		mmget(oldmm);
 		mm = oldmm;
mm/Makefile +1 -1
index d73aed0fc99c1..ca05b84ac738b 100644
@@ -50,7 +50,7 @@ obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
 			   readahead.o swap.o truncate.o vmscan.o shmem.o \
 			   util.o mmzone.o vmstat.o backing-dev.o \
 			   mm_init.o percpu.o slab_common.o \
-			   compaction.o vmacache.o \
+			   compaction.o \
 			   interval_tree.o list_lru.o workingset.o \
 			   debug.o gup.o $(mmu-y)
 
mm/debug.c +2 -2
index ccca576b28990..d8ed9d7383267 100644
@@ -214,7 +214,7 @@ EXPORT_SYMBOL(dump_vma);
 
 void dump_mm(const struct mm_struct *mm)
 {
-	pr_emerg("mm %px mmap %px seqnum %llu task_size %lu\n"
+	pr_emerg("mm %px mmap %px task_size %lu\n"
 #ifdef CONFIG_MMU
 		"get_unmapped_area %px\n"
 #endif
@@ -242,7 +242,7 @@ void dump_mm(const struct mm_struct *mm)
 		"tlb_flush_pending %d\n"
 		"def_flags: %#lx(%pGv)\n",
 
-		mm, mm->mmap, (long long) mm->vmacache_seqnum, mm->task_size,
+		mm, mm->mmap, mm->task_size,
 #ifdef CONFIG_MMU
 		mm->get_unmapped_area,
 #endif
mm/mmap.c +0 -20
index 1cef158c31909..cc9d0c524d575 100644
@@ -13,7 +13,6 @@
 #include <linux/slab.h>
 #include <linux/backing-dev.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/shm.h>
 #include <linux/mman.h>
 #include <linux/pagemap.h>
@@ -705,9 +704,6 @@ inline int vma_expand(struct ma_state *mas, struct vm_area_struct *vma,
 		/* Remove from mm linked list - also updates highest_vm_end */
 		__vma_unlink_list(mm, next);
 
-		/* Kill the cache */
-		vmacache_invalidate(mm);
-
 		if (file)
 			__remove_shared_vm_struct(next, file, mapping);
 
@@ -921,8 +917,6 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
 
 	if (remove_next) {
 		__vma_unlink_list(mm, next);
-		/* Kill the cache */
-		vmacache_invalidate(mm);
 		if (file)
 			__remove_shared_vm_struct(next, file, mapping);
 	} else if (insert) {
@@ -2220,19 +2214,9 @@ struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
 {
 	struct vm_area_struct *vma;
 	MA_STATE(mas, &mm->mm_mt, start_addr, start_addr);
-
-	/* Check the cache first. */
-	vma = vmacache_find(mm, start_addr);
-	if (likely(vma))
-		return vma;
-
 	rcu_read_lock();
 	vma = mas_find(&mas, end_addr - 1);
 	rcu_read_unlock();
-
-	if (vma)
-		vmacache_update(start_addr, vma);
-
 	return vma;
 }
 EXPORT_SYMBOL(find_vma_intersection);
@@ -2627,9 +2611,6 @@ detach_vmas_to_be_unmapped(struct mm_struct *mm, struct vm_area_struct *vma,
 		mm->highest_vm_end = prev ? vm_end_gap(prev) : 0;
 	tail_vma->vm_next = NULL;
 
-	/* Kill the cache */
-	vmacache_invalidate(mm);
-
 	/*
 	 * Do not downgrade mmap_lock if we are next to VM_GROWSDOWN or
 	 * VM_GROWSUP VMA. Such VMAs can change their size under
@@ -3026,7 +3007,6 @@ static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	if (vma_mas_remove(&unmap, mas))
 		goto mas_store_fail;
 
-	vmacache_invalidate(vma->vm_mm);
 	if (vma->anon_vma) {
 		anon_vma_interval_tree_post_update_vma(vma);
 		anon_vma_unlock_write(vma->anon_vma);
mm/vmacache.c deleted +0 -117

117 lines not on this page · raw message

Signature · 1 line
2.28.0
#25 lore raw

PATCH v2 20/70 mm/mmap: Change __do_munmap() to avoid unnecessary lookups.

In reply to Liam R. Howlett

As there is no longer a vmacache, find_vma() is more expensive and so avoid doing them

---
 mm/mmap.c | 115 ++++++++++++++++++++++++++++--------------------------
 1 file changed, 59 insertions(+), 56 deletions(-)
mm/mmap.c +59 -56
index cc9d0c524d575..af426972c9dd2 100644
@@ -2585,44 +2585,6 @@ static void unmap_region(struct mm_struct *mm,
 	tlb_finish_mmu(&tlb, start, end);
 }
 
-/*
- * Create a list of vma's touched by the unmap, removing them from the mm's
- * vma list as we go..
- */
-static bool
-detach_vmas_to_be_unmapped(struct mm_struct *mm, struct vm_area_struct *vma,
-	struct vm_area_struct *prev, unsigned long end)
-{
-	struct vm_area_struct **insertion_point;
-	struct vm_area_struct *tail_vma = NULL;
-
-	insertion_point = (prev ? &prev->vm_next : &mm->mmap);
-	vma->vm_prev = NULL;
-	vma_mt_szero(mm, vma->vm_start, end);
-	do {
-		mm->map_count--;
-		tail_vma = vma;
-		vma = vma->vm_next;
-	} while (vma && vma->vm_start < end);
-	*insertion_point = vma;
-	if (vma)
-		vma->vm_prev = prev;
-	else
-		mm->highest_vm_end = prev ? vm_end_gap(prev) : 0;
-	tail_vma->vm_next = NULL;
-
-	/*
-	 * Do not downgrade mmap_lock if we are next to VM_GROWSDOWN or
-	 * VM_GROWSUP VMA. Such VMAs can change their size under
-	 * down_read(mmap_lock) and collide with the VMA we are about to unmap.
-	 */
-	if (vma && (vma->vm_flags & VM_GROWSDOWN))
-		return false;
-	if (prev && (prev->vm_flags & VM_GROWSUP))
-		return false;
-	return true;
-}
-
 /*
  * __split_vma() bypasses sysctl_max_map_count checking.  We use this where it
  * has already been checked or doesn't make sense to fail.
@@ -2702,12 +2664,16 @@ int split_vma(struct mm_struct *mm, struct vm_area_struct *vma,
 	return __split_vma(mm, vma, addr, new_below);
 }
 
-static inline void unlock_range(struct vm_area_struct *start, unsigned long limit)
+static inline int unlock_range(struct vm_area_struct *start,
+			       struct vm_area_struct **tail, unsigned long limit)
 {
 	struct mm_struct *mm = start->vm_mm;
 	struct vm_area_struct *tmp = start;
+	int count = 0;
 
 	while (tmp && tmp->vm_start < limit) {
+		*tail = tmp;
+		count++;
 		if (tmp->vm_flags & VM_LOCKED) {
 			mm->locked_vm -= vma_pages(tmp);
 			munlock_vma_pages_all(tmp);
@@ -2715,6 +2681,8 @@ static inline void unlock_range(struct vm_area_struct *start, unsigned long limi
 
 		tmp = tmp->vm_next;
 	}
+
+	return count;
 }
 /* Munmap is split into 2 main parts -- this part which finds
  * what needs doing, and the areas themselves, which do the
@@ -2726,24 +2694,24 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 {
 	unsigned long end;
 	struct vm_area_struct *vma, *prev, *last;
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
 	if ((offset_in_page(start)) || start > TASK_SIZE || len > TASK_SIZE-start)
 		return -EINVAL;
 
-	len = PAGE_ALIGN(len);
-	end = start + len;
-	if (len == 0)
+	end = start + PAGE_ALIGN(len);
+	if (end == start)
 		return -EINVAL;
 
 	 /* arch_unmap() might do unmaps itself.  */
 	arch_unmap(mm, start, end);
 
 	/* Find the first overlapping VMA */
-	vma = find_vma_intersection(mm, start, end);
+	vma = mas_find(&mas, end - 1);
 	if (!vma)
 		return 0;
 
-	prev = vma->vm_prev;
+	mas.last = end - 1;
 	/* we have start < vma->vm_end  */
 
 	/*
@@ -2767,16 +2735,27 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 		if (error)
 			return error;
 		prev = vma;
+		vma = vma_next(mm, prev);
+		mas.index = start;
+		mas_reset(&mas);
+	} else {
+		prev = vma->vm_prev;
 	}
 
+	if (vma->vm_end >= end)
+		last = vma;
+	else
+		last = find_vma_intersection(mm, end - 1, end);
+
 	/* Does it split the last one? */
-	last = find_vma(mm, end);
-	if (last && end > last->vm_start) {
+	if (last && end < last->vm_end) {
 		int error = __split_vma(mm, last, end, 1);
 		if (error)
 			return error;
+		vma = vma_next(mm, prev);
+		mas_reset(&mas);
 	}
-	vma = vma_next(mm, prev);
+
 
 	if (unlikely(uf)) {
 		/*
@@ -2789,22 +2768,46 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 		 * failure that it's not worth optimizing it for.
 		 */
 		int error = userfaultfd_unmap_prep(vma, start, end, uf);
+
 		if (error)
 			return error;
 	}
 
 	/*
-	 * unlock any mlock()ed ranges before detaching vmas
+	 * unlock any mlock()ed ranges before detaching vmas, count the number
+	 * of VMAs to be dropped, and return the tail entry of the affected
+	 * area.
 	 */
-	if (mm->locked_vm)
-		unlock_range(vma, end);
+	mm->map_count -= unlock_range(vma, &last, end);
+	/* Drop removed area from the tree */
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+
+	/* Detach vmas from the MM linked list */
+	vma->vm_prev = NULL;
+	if (prev)
+		prev->vm_next = last->vm_next;
+	else
+		mm->mmap = last->vm_next;
 
-	/* Detach vmas from the MM linked list and remove from the mm tree*/
-	if (!detach_vmas_to_be_unmapped(mm, vma, prev, end))
-		downgrade = false;
+	if (last->vm_next) {
+		last->vm_next->vm_prev = prev;
+		last->vm_next = NULL;
+	} else
+		mm->highest_vm_end = prev ? vm_end_gap(prev) : 0;
 
-	if (downgrade)
-		mmap_write_downgrade(mm);
+	/*
+	 * Do not downgrade mmap_lock if we are next to VM_GROWSDOWN or
+	 * VM_GROWSUP VMA. Such VMAs can change their size under
+	 * down_read(mmap_lock) and collide with the VMA we are about to unmap.
+	 */
+	if (downgrade) {
+		if (last && (last->vm_flags & VM_GROWSDOWN))
+			downgrade = false;
+		else if (prev && (prev->vm_flags & VM_GROWSUP))
+			downgrade = false;
+		else
+			mmap_write_downgrade(mm);
+	}
 
 	unmap_region(mm, vma, prev, start, end);
 
@@ -3227,7 +3230,7 @@ void exit_mmap(struct mm_struct *mm)
 	}
 
 	if (mm->locked_vm)
-		unlock_range(mm->mmap, ULONG_MAX);
+		unlock_range(mm->mmap, &vma, ULONG_MAX);
 
 	arch_exit_mmap(mm);
 
Signature · 1 line
2.28.0
#26 lore raw

PATCH v2 21/70 mm/mmap: Move mmap_region() below do_munmap()

In reply to Liam R. Howlett

Relocation of code for the next commit. There should be no changes here.

---
 mm/mmap.c | 490 ++++++++++++++++++++++++++----------------------------
 1 file changed, 240 insertions(+), 250 deletions(-)
mm/mmap.c +240 -250
index af426972c9dd2..07aec9e215de4 100644
@@ -1715,256 +1715,6 @@ static inline int accountable_mapping(struct file *file, vm_flags_t vm_flags)
 	return (vm_flags & (VM_NORESERVE | VM_SHARED | VM_WRITE)) == VM_WRITE;
 }
 
-unsigned long mmap_region(struct file *file, unsigned long addr,
-		unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
-		struct list_head *uf)
-{
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = NULL;
-	struct vm_area_struct *prev, *next;
-	pgoff_t pglen = len >> PAGE_SHIFT;
-	unsigned long charged = 0;
-	unsigned long end = addr + len;
-	unsigned long merge_start = addr, merge_end = end;
-	pgoff_t vm_pgoff;
-	int error;
-	MA_STATE(mas, &mm->mm_mt, addr, end - 1);
-
-	/* Check against address space limit. */
-	if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
-		unsigned long nr_pages;
-
-		/*
-		 * MAP_FIXED may remove pages of mappings that intersects with
-		 * requested mapping. Account for the pages it would unmap.
-		 */
-		nr_pages = count_vma_pages_range(mm, addr, end);
-
-		if (!may_expand_vm(mm, vm_flags,
-					(len >> PAGE_SHIFT) - nr_pages))
-			return -ENOMEM;
-	}
-
-	/* Unmap any existing mapping in the area */
-	if (do_munmap(mm, addr, len, uf))
-		return -ENOMEM;
-
-	/*
-	 * Private writable mapping: check memory availability
-	 */
-	if (accountable_mapping(file, vm_flags)) {
-		charged = len >> PAGE_SHIFT;
-		if (security_vm_enough_memory_mm(mm, charged))
-			return -ENOMEM;
-		vm_flags |= VM_ACCOUNT;
-	}
-
-
-	if (vm_flags & VM_SPECIAL) {
-		prev = mas_prev(&mas, 0);
-		goto cannot_expand;
-	}
-
-	/* Attempt to expand an old mapping */
-
-	/* Check next */
-	next = mas_next(&mas, ULONG_MAX);
-	if (next && next->vm_start == end && vma_policy(next) &&
-	    can_vma_merge_before(next, vm_flags, NULL, file, pgoff+pglen,
-				 NULL_VM_UFFD_CTX)) {
-		merge_end = next->vm_end;
-		vma = next;
-		vm_pgoff = next->vm_pgoff - pglen;
-	}
-
-	/* Check prev */
-	prev = mas_prev(&mas, 0);
-	if (prev && prev->vm_end == addr && !vma_policy(prev) &&
-	    can_vma_merge_after(prev, vm_flags, NULL, file, pgoff,
-				NULL_VM_UFFD_CTX)) {
-		merge_start = prev->vm_start;
-		vma = prev;
-		vm_pgoff = prev->vm_pgoff;
-	}
-
-
-	/* Actually expand, if possible */
-	if (vma &&
-	    !vma_expand(&mas, vma, merge_start, merge_end, vm_pgoff, next)) {
-		khugepaged_enter_vma_merge(prev, vm_flags);
-		goto expanded;
-	}
-
-	mas_reset(&mas);
-	mas_set(&mas, addr);
-	mas.last = end - 1;
-cannot_expand:
-	/*
-	 * Determine the object being mapped and call the appropriate
-	 * specific mapper. the address has already been validated, but
-	 * not unmapped, but the maps are removed from the list.
-	 */
-	vma = vm_area_alloc(mm);
-	if (!vma) {
-		error = -ENOMEM;
-		goto unacct_error;
-	}
-
-	vma->vm_start = addr;
-	vma->vm_end = end;
-	vma->vm_flags = vm_flags;
-	vma->vm_page_prot = vm_get_page_prot(vm_flags);
-	vma->vm_pgoff = pgoff;
-
-	if (file) {
-		if (vm_flags & VM_DENYWRITE) {
-			error = deny_write_access(file);
-			if (error)
-				goto free_vma;
-		}
-		if (vm_flags & VM_SHARED) {
-			error = mapping_map_writable(file->f_mapping);
-			if (error)
-				goto allow_write_and_free_vma;
-		}
-
-		/* ->mmap() can change vma->vm_file, but must guarantee that
-		 * vma_link() below can deny write-access if VM_DENYWRITE is set
-		 * and map writably if VM_SHARED is set. This usually means the
-		 * new file must not have been exposed to user-space, yet.
-		 */
-		vma->vm_file = get_file(file);
-		error = call_mmap(file, vma);
-		if (error)
-			goto unmap_and_free_vma;
-
-		/* Can addr have changed??
-		 *
-		 * Answer: Yes, several device drivers can do it in their
-		 *         f_op->mmap method. -DaveM
-		 * Bug: If addr is changed, prev, rb_link, rb_parent should
-		 *      be updated for vma_link()
-		 */
-		WARN_ON_ONCE(addr != vma->vm_start);
-
-		addr = vma->vm_start;
-
-		/* If vm_flags changed after call_mmap(), we should try merge vma again
-		 * as we may succeed this time.
-		 */
-		if (unlikely(vm_flags != vma->vm_flags && prev &&
-			     prev->vm_end == addr && !vma_policy(prev) &&
-			     can_vma_merge_after(prev, vm_flags, NULL, file,
-						 pgoff, NULL_VM_UFFD_CTX))) {
-			merge_start = prev->vm_start;
-			vm_pgoff = prev->vm_pgoff;
-			if (!vma_expand(&mas, prev, merge_start, merge_end,
-					vm_pgoff, next)) {
-				/* ->mmap() can change vma->vm_file and fput the original file. So
-				 * fput the vma->vm_file here or we would add an extra fput for file
-				 * and cause general protection fault ultimately.
-				 */
-				fput(vma->vm_file);
-				vm_area_free(vma);
-				vma = prev;
-				/* Update vm_flags and possible addr to pick up the change. We don't
-				 * warn here if addr changed as the vma is not linked by vma_link().
-				 */
-				addr = vma->vm_start;
-				vm_flags = vma->vm_flags;
-				goto unmap_writable;
-			}
-		}
-
-		/* Can addr have changed??
-		 *
-		 * Answer: Yes, several device drivers can do it in their
-		 *         f_op->mmap method. -DaveM
-		 * Bug: If addr is changed, prev and the maple tree data should
-		 * be updated for vma_link()
-		 */
-		WARN_ON_ONCE(addr != vma->vm_start);
-
-		addr = vma->vm_start;
-		vm_flags = vma->vm_flags;
-	} else if (vm_flags & VM_SHARED) {
-		error = shmem_zero_setup(vma);
-		if (error)
-			goto free_vma;
-	} else {
-		vma_set_anonymous(vma);
-	}
-
-	/* Allow architectures to sanity-check the vm_flags */
-	if (!arch_validate_flags(vma->vm_flags)) {
-		error = -EINVAL;
-		if (file)
-			goto unmap_and_free_vma;
-		else
-			goto free_vma;
-	}
-
-	mas.index = mas.last = addr;
-	mas_walk(&mas);
-	vma_mas_link(mm, vma, &mas, prev);
-	/* Once vma denies write, undo our temporary denial count */
-	if (file) {
-unmap_writable:
-		if (vm_flags & VM_SHARED)
-			mapping_unmap_writable(file->f_mapping);
-		if (vm_flags & VM_DENYWRITE)
-			allow_write_access(file);
-	}
-	file = vma->vm_file;
-expanded:
-	perf_event_mmap(vma);
-
-	vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
-	if (vm_flags & VM_LOCKED) {
-		if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
-		    is_vm_hugetlb_page(vma) ||
-		    vma == get_gate_vma(current->mm))
-			vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
-		else
-			mm->locked_vm += (len >> PAGE_SHIFT);
-	}
-
-	if (file)
-		uprobe_mmap(vma);
-
-	/*
-	 * New (or expanded) vma always get soft dirty status.
-	 * Otherwise user-space soft-dirty page tracker won't
-	 * be able to distinguish situation when vma area unmapped,
-	 * then new mapped in-place (which must be aimed as
-	 * a completely new data area).
-	 */
-	vma->vm_flags |= VM_SOFTDIRTY;
-
-	vma_set_page_prot(vma);
-
-	return addr;
-
-unmap_and_free_vma:
-	vma->vm_file = NULL;
-	fput(file);
-
-	/* Undo any partial mapping done by a device driver. */
-	unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
-	charged = 0;
-	if (vm_flags & VM_SHARED)
-		mapping_unmap_writable(file->f_mapping);
-allow_write_and_free_vma:
-	if (vm_flags & VM_DENYWRITE)
-		allow_write_access(file);
-free_vma:
-	vm_area_free(vma);
-unacct_error:
-	if (charged)
-		vm_unacct_memory(charged);
-	return error;
-}
-
 /* unmapped_area() Find an area between the low_limit and the high_limit with
  * the correct alignment and offset, all from @info. Note: current->mm is used
  * for the search.
@@ -2823,6 +2573,246 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	return __do_munmap(mm, start, len, uf, false);
 }
 
+unsigned long mmap_region(struct file *file, unsigned long addr,
+		unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
+		struct list_head *uf)
+{
+	struct mm_struct *mm = current->mm;
+	struct vm_area_struct *vma = NULL;
+	struct vm_area_struct *prev, *next;
+	pgoff_t pglen = len >> PAGE_SHIFT;
+	unsigned long charged = 0;
+	unsigned long end = addr + len;
+	unsigned long merge_start = addr, merge_end = end;
+	pgoff_t vm_pgoff;
+	int error;
+	MA_STATE(mas, &mm->mm_mt, addr, end - 1);
+
+	/* Check against address space limit. */
+	if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
+		unsigned long nr_pages;
+
+		/*
+		 * MAP_FIXED may remove pages of mappings that intersects with
+		 * requested mapping. Account for the pages it would unmap.
+		 */
+		nr_pages = count_vma_pages_range(mm, addr, end);
+
+		if (!may_expand_vm(mm, vm_flags,
+					(len >> PAGE_SHIFT) - nr_pages))
+			return -ENOMEM;
+	}
+
+	/* Unmap any existing mapping in the area */
+	if (do_mas_munmap(&mas, mm, addr, len, uf, false))
+		return -ENOMEM;
+
+	/*
+	 * Private writable mapping: check memory availability
+	 */
+	if (accountable_mapping(file, vm_flags)) {
+		charged = len >> PAGE_SHIFT;
+		if (security_vm_enough_memory_mm(mm, charged))
+			return -ENOMEM;
+		vm_flags |= VM_ACCOUNT;
+	}
+
+
+	if (vm_flags & VM_SPECIAL) {
+		prev = mas_prev(&mas, 0);
+		goto cannot_expand;
+	}
+
+	/* Attempt to expand an old mapping */
+
+	/* Check next */
+	next = mas_next(&mas, ULONG_MAX);
+	if (next && next->vm_start == end && vma_policy(next) &&
+	    can_vma_merge_before(next, vm_flags, NULL, file, pgoff + pglen,
+				 NULL_VM_UFFD_CTX)) {
+		merge_end = next->vm_end;
+		vma = next;
+		vm_pgoff = next->vm_pgoff - pglen;
+	}
+
+	/* Check prev */
+	prev = mas_prev(&mas, 0);
+	if (prev && prev->vm_end == addr && !vma_policy(prev) &&
+	    can_vma_merge_after(prev, vm_flags, NULL, file, pgoff,
+				NULL_VM_UFFD_CTX)) {
+		merge_start = prev->vm_start;
+		vma = prev;
+		vm_pgoff = prev->vm_pgoff;
+	}
+
+	/* Actually expand, if possible */
+	if (vma &&
+	    !vma_expand(&mas, vma, merge_start, merge_end, vm_pgoff, next)) {
+		khugepaged_enter_vma_merge(prev, vm_flags);
+		goto expanded;
+	}
+
+cannot_expand:
+	/*
+	 * Determine the object being mapped and call the appropriate
+	 * specific mapper. the address has already been validated, but
+	 * not unmapped, but the maps are removed from the list.
+	 */
+	vma = vm_area_alloc(mm);
+	if (!vma) {
+		error = -ENOMEM;
+		goto unacct_error;
+	}
+
+	vma->vm_start = addr;
+	vma->vm_end = end;
+	vma->vm_flags = vm_flags;
+	vma->vm_page_prot = vm_get_page_prot(vm_flags);
+	vma->vm_pgoff = pgoff;
+
+	if (file) {
+		if (vm_flags & VM_DENYWRITE) {
+			error = deny_write_access(file);
+			if (error)
+				goto free_vma;
+		}
+		if (vm_flags & VM_SHARED) {
+			error = mapping_map_writable(file->f_mapping);
+			if (error)
+				goto allow_write_and_free_vma;
+		}
+
+		/* ->mmap() can change vma->vm_file, but must guarantee that
+		 * vma_link() below can deny write-access if VM_DENYWRITE is set
+		 * and map writably if VM_SHARED is set. This usually means the
+		 * new file must not have been exposed to user-space, yet.
+		 */
+		vma->vm_file = get_file(file);
+		error = call_mmap(file, vma);
+		if (error)
+			goto unmap_and_free_vma;
+
+		/* If vm_flags changed after call_mmap(), we should try merge vma again
+		 * as we may succeed this time.
+		 */
+		if (unlikely(vm_flags != vma->vm_flags && prev &&
+			     prev->vm_end == addr && !vma_policy(prev) &&
+			     can_vma_merge_after(prev, vm_flags, NULL, file,
+						 pgoff, NULL_VM_UFFD_CTX))) {
+			merge_start = prev->vm_start;
+			vm_pgoff = prev->vm_pgoff;
+			if (!vma_expand(&mas, prev, merge_start, merge_end,
+					vm_pgoff, next)) {
+				/* ->mmap() can change vma->vm_file and fput the original file. So
+				 * fput the vma->vm_file here or we would add an extra fput for file
+				 * and cause general protection fault ultimately.
+				 */
+				fput(vma->vm_file);
+				vm_area_free(vma);
+				vma = prev;
+				/* Update vm_flags and possible addr to pick up the change. We don't
+				 * warn here if addr changed as the vma is not linked by vma_link().
+				 */
+				addr = vma->vm_start;
+				vm_flags = vma->vm_flags;
+				goto unmap_writable;
+			}
+		}
+
+		/* Can addr have changed??
+		 *
+		 * Answer: Yes, several device drivers can do it in their
+		 *         f_op->mmap method. -DaveM
+		 * Bug: If addr is changed, prev and the maple tree data should
+		 * be updated for vma_link()
+		 */
+		WARN_ON_ONCE(addr != vma->vm_start);
+
+		addr = vma->vm_start;
+		vm_flags = vma->vm_flags;
+	} else if (vm_flags & VM_SHARED) {
+		error = shmem_zero_setup(vma);
+		if (error)
+			goto free_vma;
+	} else {
+		vma_set_anonymous(vma);
+	}
+
+	/* Allow architectures to sanity-check the vm_flags */
+	if (!arch_validate_flags(vma->vm_flags)) {
+		error = -EINVAL;
+		if (file)
+			goto unmap_and_free_vma;
+		else
+			goto free_vma;
+	}
+
+	/*
+	 * mas was called for the prev vma, and that may not be the correct
+	 * location for the vma being inserted, but is is before that location
+	 * and so the call to vma_mas_link()->vma_mas_store()->mas_store_gfp()
+	 * will detect the write as a spanning store and reset mas if necessary.
+	 */
+	mas.index = mas.last = addr;
+	mas_walk(&mas);
+	vma_mas_link(mm, vma, &mas, prev);
+	/* Once vma denies write, undo our temporary denial count */
+	if (file) {
+unmap_writable:
+		if (vm_flags & VM_SHARED)
+			mapping_unmap_writable(file->f_mapping);
+		if (vm_flags & VM_DENYWRITE)
+			allow_write_access(file);
+	}
+	file = vma->vm_file;
+expanded:
+	perf_event_mmap(vma);
+
+	vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
+	if (vm_flags & VM_LOCKED) {
+		if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
+		    is_vm_hugetlb_page(vma) ||
+		    vma == get_gate_vma(current->mm))
+			vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
+		else
+			mm->locked_vm += (len >> PAGE_SHIFT);
+	}
+
+	if (file)
+		uprobe_mmap(vma);
+
+	/*
+	 * New (or expanded) vma always get soft dirty status.
+	 * Otherwise user-space soft-dirty page tracker won't
+	 * be able to distinguish situation when vma area unmapped,
+	 * then new mapped in-place (which must be aimed as
+	 * a completely new data area).
+	 */
+	vma->vm_flags |= VM_SOFTDIRTY;
+
+	vma_set_page_prot(vma);
+
+	return addr;
+
+unmap_and_free_vma:
+	vma->vm_file = NULL;
+	fput(file);
+
+	/* Undo any partial mapping done by a device driver. */
+	unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
+	charged = 0;
+	if (vm_flags & VM_SHARED)
+		mapping_unmap_writable(file->f_mapping);
+allow_write_and_free_vma:
+	if (vm_flags & VM_DENYWRITE)
+		allow_write_access(file);
+free_vma:
+	vm_area_free(vma);
+unacct_error:
+	if (charged)
+		vm_unacct_memory(charged);
+	return error;
+}
 static int __vm_munmap(unsigned long start, size_t len, bool downgrade)
 {
 	int ret;
Signature · 1 line
2.28.0
#27 lore raw

PATCH v2 22/70 mm/mmap: Add do_mas_munmap() and wraper for __do_munmap()

In reply to Liam R. Howlett

To avoid extra tree work, it is necessary to support passing in a maple state to key functions. Start this work with __do_munmap().

---
 mm/mmap.c | 102 ++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 72 insertions(+), 30 deletions(-)
mm/mmap.c +72 -30
index 07aec9e215de4..8bc4ee7cc2fff 100644
@@ -2434,34 +2434,24 @@ static inline int unlock_range(struct vm_area_struct *start,
 
 	return count;
 }
-/* Munmap is split into 2 main parts -- this part which finds
- * what needs doing, and the areas themselves, which do the
- * work.  This now handles partial unmappings.
- * Jeremy Fitzhardinge <[email protected]>
+
+/* do_mas_align_munmap() - munmap the aligned region from @start to @end.
+ *
+ * @mas: The maple_state, ideally set up to alter the correct tree location.
+ * @vma: The starting vm_area_struct
+ * @mm: The mm_struct
+ * @start: The aligned start address to munmap.
+ * @end: The aligned end address to munmap.
+ * @uf: The userfaultfd list_head
+ * @downgrade: Set to true to attempt a downwrite of the mmap_sem
+ *
+ *
  */
-int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
-		struct list_head *uf, bool downgrade)
+int do_mas_align_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			struct mm_struct *mm, unsigned long start,
+			unsigned long end, struct list_head *uf, bool downgrade)
 {
-	unsigned long end;
-	struct vm_area_struct *vma, *prev, *last;
-	MA_STATE(mas, &mm->mm_mt, start, start);
-
-	if ((offset_in_page(start)) || start > TASK_SIZE || len > TASK_SIZE-start)
-		return -EINVAL;
-
-	end = start + PAGE_ALIGN(len);
-	if (end == start)
-		return -EINVAL;
-
-	 /* arch_unmap() might do unmaps itself.  */
-	arch_unmap(mm, start, end);
-
-	/* Find the first overlapping VMA */
-	vma = mas_find(&mas, end - 1);
-	if (!vma)
-		return 0;
-
-	mas.last = end - 1;
+	struct vm_area_struct *prev, *last;
 	/* we have start < vma->vm_end  */
 
 	/*
@@ -2486,8 +2476,8 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 			return error;
 		prev = vma;
 		vma = vma_next(mm, prev);
-		mas.index = start;
-		mas_reset(&mas);
+		mas->index = start;
+		mas_reset(mas);
 	} else {
 		prev = vma->vm_prev;
 	}
@@ -2503,7 +2493,7 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 		if (error)
 			return error;
 		vma = vma_next(mm, prev);
-		mas_reset(&mas);
+		mas_reset(mas);
 	}
 
 
@@ -2530,7 +2520,7 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	 */
 	mm->map_count -= unlock_range(vma, &last, end);
 	/* Drop removed area from the tree */
-	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	mas_store_gfp(mas, NULL, GFP_KERNEL);
 
 	/* Detach vmas from the MM linked list */
 	vma->vm_prev = NULL;
@@ -2567,6 +2557,58 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	return downgrade ? 1 : 0;
 }
 
+int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
+		struct list_head *uf, bool downgrade)
+{
+	MA_STATE(mas, &mm->mm_mt, start, start);
+	return do_mas_munmap(&mas, mm, start, len, uf, downgrade);
+}
+
+/*
+ * do_mas_munmap() - munmap a given range.
+ * @mas: The maple state
+ * @mm: The mm_struct
+ * @start: The start address to munmap
+ * @len: The length of the range to munmap
+ * @uf: The userfaultfd list_head
+ * @downgrade: set to true if the user wants to attempt to write_downgrade the
+ * mmap_sem
+ *
+ * This function takes a @mas that is in the correct state to remove the
+ * mapping(s).  The @len will be aligned and any arch_unmap work will be
+ * preformed.
+ */
+int do_mas_munmap(struct ma_state *mas, struct mm_struct *mm,
+		  unsigned long start, size_t len, struct list_head *uf,
+		  bool downgrade)
+{
+	unsigned long end;
+	struct vm_area_struct *vma;
+
+	if ((offset_in_page(start)) || start > TASK_SIZE || len > TASK_SIZE-start)
+		return -EINVAL;
+
+	end = start + PAGE_ALIGN(len);
+	if (end == start)
+		return -EINVAL;
+
+	 /* arch_unmap() might do unmaps itself.  */
+	arch_unmap(mm, start, end);
+
+	/* Find the first overlapping VMA */
+	vma = mas_find(mas, end - 1);
+	if (!vma)
+		return 0;
+
+	mas->last = end - 1;
+	return do_mas_align_munmap(mas, vma, mm, start, end, uf, downgrade);
+}
+/* do_munmap() - Wrapper function for non-maple tree aware do_munmap() calls.
+ * @mm: The mm_struct
+ * @start: The start address to munmap
+ * @len: The length to be munmapped.
+ * @uf: The userfaultfd list_head
+ */
 int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	      struct list_head *uf)
 {
Signature · 1 line
2.28.0
#28 lore raw

PATCH v2 23/70 mmap: Use find_vma_intersection in do_mmap() for overlap

In reply to Liam R. Howlett

When detecting a conflict with MAP_FIXED_NOREPLACE, using the new interface avoids the need for a temp variable

---
 mm/mmap.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
mm/mmap.c +1 -3
index 8bc4ee7cc2fff..c0a64c4726b67 100644
@@ -1445,9 +1445,7 @@ unsigned long do_mmap(struct file *file, unsigned long addr,
 		return addr;
 
 	if (flags & MAP_FIXED_NOREPLACE) {
-		struct vm_area_struct *vma = find_vma(mm, addr);
-
-		if (vma && vma->vm_start < addr + len)
+		if (find_vma_intersection(mm, addr, addr + len))
 			return -EEXIST;
 	}
 
Signature · 1 line
2.28.0
#29 lore raw

PATCH v2 24/70 mmap: Remove __do_munmap() in favour of do_mas_munmap()

In reply to Liam R. Howlett

Export new interface and use it in place of old interface.

---
 include/linux/mm.h |  4 ++--
 mm/mmap.c          | 16 ++++------------
 mm/mremap.c        |  7 ++++---
 3 files changed, 10 insertions(+), 17 deletions(-)
include/linux/mm.h +2 -2
index 996353a057500..680dcfe07dbb6 100644
@@ -2573,8 +2573,8 @@ extern unsigned long mmap_region(struct file *file, unsigned long addr,
 extern unsigned long do_mmap(struct file *file, unsigned long addr,
 	unsigned long len, unsigned long prot, unsigned long flags,
 	unsigned long pgoff, unsigned long *populate, struct list_head *uf);
-extern int __do_munmap(struct mm_struct *, unsigned long, size_t,
-		       struct list_head *uf, bool downgrade);
+extern int do_mas_munmap(struct ma_state *mas, struct mm_struct *mm,
+	 unsigned long start, size_t len, struct list_head *uf, bool downgrade);
 extern int do_munmap(struct mm_struct *, unsigned long, size_t,
 		     struct list_head *uf);
 extern int do_madvise(struct mm_struct *mm, unsigned long start, size_t len_in, int behavior);
mm/mmap.c +4 -12
index c0a64c4726b67..9be91b47db6b4 100644
@@ -2555,13 +2555,6 @@ int do_mas_align_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	return downgrade ? 1 : 0;
 }
 
-int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
-		struct list_head *uf, bool downgrade)
-{
-	MA_STATE(mas, &mm->mm_mt, start, start);
-	return do_mas_munmap(&mas, mm, start, len, uf, downgrade);
-}
-
 /*
  * do_mas_munmap() - munmap a given range.
  * @mas: The maple state
@@ -2610,7 +2603,8 @@ int do_mas_munmap(struct ma_state *mas, struct mm_struct *mm,
 int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	      struct list_head *uf)
 {
-	return __do_munmap(mm, start, len, uf, false);
+	MA_STATE(mas, &mm->mm_mt, start, start);
+	return do_mas_munmap(&mas, mm, start, len, uf, false);
 }
 
 unsigned long mmap_region(struct file *file, unsigned long addr,
@@ -2858,11 +2852,12 @@ static int __vm_munmap(unsigned long start, size_t len, bool downgrade)
 	int ret;
 	struct mm_struct *mm = current->mm;
 	LIST_HEAD(uf);
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
 	if (mmap_write_lock_killable(mm))
 		return -EINTR;
 
-	ret = __do_munmap(mm, start, len, &uf, downgrade);
+	ret = do_mas_munmap(&mas, mm, start, len, &uf, downgrade);
 	/*
 	 * Returning 1 indicates mmap_lock is downgraded.
 	 * But 1 is not legal return value of vm_munmap() and munmap(), reset
@@ -3014,9 +3009,6 @@ static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	arch_unmap(mm, newbrk, oldbrk);
 
 	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
-		mas_set(mas, newbrk);
-		if (vma->vm_start != newbrk)
-			mas_reset(mas); // cause a re-walk for the first overlap.
 		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
 		goto munmap_full_vma;
 	}
mm/mremap.c +4 -3
index 138abbae4f758..a7526a8c1fe5a 100644
@@ -723,14 +723,15 @@ SYSCALL_DEFINE5(mremap, unsigned long, addr, unsigned long, old_len,
 	/*
 	 * Always allow a shrinking remap: that just unmaps
 	 * the unnecessary pages..
-	 * __do_munmap does all the needed commit accounting, and
+	 * do_mas_munmap does all the needed commit accounting, and
 	 * downgrades mmap_lock to read if so directed.
 	 */
 	if (old_len >= new_len) {
 		int retval;
+		MA_STATE(mas, &mm->mm_mt, addr + new_len, addr + new_len);
 
-		retval = __do_munmap(mm, addr+new_len, old_len - new_len,
-				  &uf_unmap, true);
+		retval = do_mas_munmap(&mas, mm, addr + new_len,
+				       old_len - new_len, &uf_unmap, true);
 		if (retval < 0 && old_len != new_len) {
 			ret = retval;
 			goto out;
Signature · 1 line
2.28.0
#30 lore raw

PATCH v2 25/70 mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()

In reply to Liam R. Howlett

do_brk_munmap() already has aligned addresses.

---
 mm/mmap.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
mm/mmap.c +3 -2
index 9be91b47db6b4..f750e85d4dc2c 100644
@@ -3004,12 +3004,13 @@ static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	struct mm_struct *mm = vma->vm_mm;
 	struct vm_area_struct unmap;
 	unsigned long unmap_pages;
-	int ret = 1;
+	int ret;
 
 	arch_unmap(mm, newbrk, oldbrk);
 
 	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
-		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
+		ret = do_mas_align_munmap(mas, vma, mm, newbrk, oldbrk, uf,
+					  true);
 		goto munmap_full_vma;
 	}
 
Signature · 1 line
2.28.0
#31 lore raw

PATCH v2 26/70 mmap: make remove_vma_list() inline

In reply to Liam R. Howlett
---
 mm/mmap.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
mm/mmap.c +2 -1
index f750e85d4dc2c..964582c0f16ee 100644
@@ -2294,7 +2294,8 @@ EXPORT_SYMBOL_GPL(find_extend_vma);
  *
  * Called with the mm semaphore held.
  */
-static void remove_vma_list(struct mm_struct *mm, struct vm_area_struct *vma)
+static inline void remove_vma_list(struct mm_struct *mm,
+				   struct vm_area_struct *vma)
 {
 	unsigned long nr_accounted = 0;
 
Signature · 1 line
2.28.0
#32 lore raw

PATCH v2 27/70 mm: Introduce vma_next() and vma_prev()

In reply to Liam R. Howlett
---
 include/linux/mm.h | 35 ++++++++++++++++++++++++++++++++++-
 1 file changed, 34 insertions(+), 1 deletion(-)
include/linux/mm.h +34 -1
index 680dcfe07dbb6..99b1dec97495a 100644
@@ -1647,7 +1647,7 @@ void zap_vma_ptes(struct vm_area_struct *vma, unsigned long address,
 void zap_page_range(struct vm_area_struct *vma, unsigned long address,
 		    unsigned long size);
 void unmap_vmas(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long start, unsigned long end);
+		struct ma_state *mas, unsigned long start, unsigned long end);
 
 struct mmu_notifier_range;
 
@@ -2654,6 +2654,24 @@ extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned lon
 extern struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
 		     unsigned long start_addr, unsigned long end_addr);
 
+static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
+			const struct vm_area_struct *vma)
+{
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
+
+	mas_set(&mas, vma->vm_end);
+	return mas_next(&mas, ULONG_MAX);
+}
+
+static inline struct vm_area_struct *vma_prev(struct mm_struct *mm,
+			const struct vm_area_struct *vma)
+{
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
+
+	mas_set(&mas, vma->vm_start);
+	return mas_prev(&mas, 0);
+}
+
 static inline unsigned long vm_start_gap(struct vm_area_struct *vma)
 {
 	unsigned long vm_start = vma->vm_start;
@@ -2695,6 +2713,21 @@ static inline struct vm_area_struct *find_exact_vma(struct mm_struct *mm,
 	return vma;
 }
 
+static inline struct vm_area_struct *vma_mas_next(struct ma_state *mas)
+{
+	struct ma_state tmp;
+
+	memcpy(&tmp, mas, sizeof(tmp));
+	return mas_next(&tmp, ULONG_MAX);
+}
+
+static inline struct vm_area_struct *vma_mas_prev(struct ma_state *mas)
+{
+	struct ma_state tmp;
+
+	memcpy(&tmp, mas, sizeof(tmp));
+	return mas_prev(&tmp, 0);
+}
 static inline bool range_in_vma(struct vm_area_struct *vma,
 				unsigned long start, unsigned long end)
 {
Signature · 1 line
2.28.0
#33 lore raw

PATCH v2 28/70 arch/arm64: Remove mmap linked list from vdso.

In reply to Liam R. Howlett

Start using the maple tree

---
 arch/arm64/kernel/vdso.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
arch/arm64/kernel/vdso.c +4 -1
index debb8995d57fb..caa7d8f6b99db 100644
@@ -144,10 +144,12 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 {
 	struct mm_struct *mm = task->mm;
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long size = vma->vm_end - vma->vm_start;
 
 		if (vma_is_special_mapping(vma, vdso_info[VDSO_ABI_AA64].dm))
@@ -157,6 +159,7 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 			zap_page_range(vma, vma->vm_start, size);
 #endif
 	}
+	rcu_read_unlock();
 
 	mmap_read_unlock(mm);
 	return 0;
Signature · 1 line
2.28.0
#34 lore raw

PATCH v2 29/70 arch/parsic: Remove mmap linked list from kernel/cache

In reply to Liam R. Howlett

Start using the maple tree

---
 arch/parisc/kernel/cache.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
arch/parisc/kernel/cache.c +5 -3
index 86a1a63563fd5..288a25e1b1c29 100644
@@ -520,8 +520,9 @@ static inline unsigned long mm_total_size(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	unsigned long usize = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next)
+	mas_for_each(&mas, vma, ULONG_MAX)
 		usize += vma->vm_end - vma->vm_start;
 	return usize;
 }
@@ -548,6 +549,7 @@ void flush_cache_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	pgd_t *pgd;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* Flushing the whole cache on each cpu takes forever on
 	   rp3440, etc.  So, avoid it if the mm isn't too big.  */
@@ -560,7 +562,7 @@ void flush_cache_mm(struct mm_struct *mm)
 	}
 
 	if (mm->context == mfsp(3)) {
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			flush_user_dcache_range_asm(vma->vm_start, vma->vm_end);
 			if (vma->vm_flags & VM_EXEC)
 				flush_user_icache_range_asm(vma->vm_start, vma->vm_end);
@@ -570,7 +572,7 @@ void flush_cache_mm(struct mm_struct *mm)
 	}
 
 	pgd = mm->pgd;
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long addr;
 
 		for (addr = vma->vm_start; addr < vma->vm_end;
Signature · 1 line
2.28.0
#35 lore raw

PATCH v2 30/70 arch/powerpc: Remove mmap linked list from mm/book2s32/tlb

In reply to Liam R. Howlett

Start using the maple tree

---
 arch/powerpc/mm/book3s32/tlb.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
arch/powerpc/mm/book3s32/tlb.c +2 -1
index b6c7427daa6fe..be595b36dc4cd 100644
@@ -121,6 +121,7 @@ EXPORT_SYMBOL(flush_tlb_kernel_range);
 void flush_tlb_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *mp;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	if (!Hash) {
 		_tlbia();
@@ -133,7 +134,7 @@ void flush_tlb_mm(struct mm_struct *mm)
 	 * unmap_region or exit_mmap, but not from vmtruncate on SMP -
 	 * but it seems dup_mmap is the only SMP case which gets here.
 	 */
-	for (mp = mm->mmap; mp != NULL; mp = mp->vm_next)
+	mas_for_each(&mas, mp, ULONG_MAX)
 		flush_range(mp->vm_mm, mp->vm_start, mp->vm_end);
 }
 EXPORT_SYMBOL(flush_tlb_mm);
Signature · 1 line
2.28.0
#36 lore raw

PATCH v2 31/70 arch/powerpc: Remove mmap linked list from mm/book2s32/subpage_prot

In reply to Liam R. Howlett

Start using the maple tree

---
 arch/powerpc/mm/book3s64/subpage_prot.c | 13 ++-----------
 1 file changed, 2 insertions(+), 11 deletions(-)
arch/powerpc/mm/book3s64/subpage_prot.c +2 -11
index 60c6ea16a972a..ada1531f81be9 100644
@@ -149,24 +149,15 @@ static void subpage_mark_vma_nohuge(struct mm_struct *mm, unsigned long addr,
 				    unsigned long len)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	/*
 	 * We don't try too hard, we just mark all the vma in that range
 	 * VM_NOHUGEPAGE and split them.
 	 */
-	vma = find_vma(mm, addr);
-	/*
-	 * If the range is in unmapped range, just return
-	 */
-	if (vma && ((addr + len) <= vma->vm_start))
-		return;
-
-	while (vma) {
-		if (vma->vm_start >= (addr + len))
-			break;
+	mas_for_each(&mas, vma, addr + len) {
 		vma->vm_flags |= VM_NOHUGEPAGE;
 		walk_page_vma(vma, &subpage_walk_ops, NULL);
-		vma = vma->vm_next;
 	}
 }
 #else
Signature · 1 line
2.28.0
#37 lore raw

PATCH v2 32/70 arch/powerpc: Optimize cell spu task sync.

In reply to Liam R. Howlett

Use the vma api to look up the spu reference instead of walking the linked list.

---
 arch/powerpc/oprofile/cell/spu_task_sync.c | 22 ++++++++++------------
 1 file changed, 10 insertions(+), 12 deletions(-)
arch/powerpc/oprofile/cell/spu_task_sync.c +10 -12
index 489f993100d56..47b4d4e9b628d 100644
@@ -333,19 +333,17 @@ get_exec_dcookie_and_offset(struct spu *spu, unsigned int *offsetp,
 	}
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
-		if (vma->vm_start > spu_ref || vma->vm_end <= spu_ref)
-			continue;
-		my_offset = spu_ref - vma->vm_start;
-		if (!vma->vm_file)
-			goto fail_no_image_cookie;
-
-		pr_debug("Found spu ELF at %X(object-id:%lx) for file %pD\n",
-			 my_offset, spu_ref, vma->vm_file);
-		*offsetp = my_offset;
-		break;
-	}
+	vma = find_vma_intersection(mm, spu_ref, spu_ref + 1);
+	if (!vma)
+		goto fail_no_image_cookie;
+
+	my_offset = spu_ref - vma->vm_start;
+	if (!vma->vm_file)
+		goto fail_no_image_cookie;
 
+	pr_debug("Found spu ELF at %X(object-id:%lx) for file %pD\n",
+		 my_offset, spu_ref, vma->vm_file);
+	*offsetp = my_offset;
 	*spu_bin_dcookie = fast_get_dcookie(&vma->vm_file->f_path);
 	pr_debug("got dcookie for %pD\n", vma->vm_file);
 
Signature · 1 line
2.28.0
#38 lore raw

PATCH v2 33/70 arch/s390: Use maple tree iterators instead of linked list.

In reply to Liam R. Howlett
---
 arch/s390/mm/gmap.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
arch/s390/mm/gmap.c +4 -2
index 64795d0349263..8f7ed79583b29 100644
@@ -2502,8 +2502,9 @@ static const struct mm_walk_ops thp_split_walk_ops = {
 static inline void thp_split_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		vma->vm_flags &= ~VM_HUGEPAGE;
 		vma->vm_flags |= VM_NOHUGEPAGE;
 		walk_page_vma(vma, &thp_split_walk_ops, NULL);
@@ -2571,8 +2572,9 @@ int gmap_mark_unmergeable(void)
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
 	int ret;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		ret = ksm_madvise(vma, vma->vm_start, vma->vm_end,
 				  MADV_UNMERGEABLE, &vma->vm_flags);
 		if (ret)
Signature · 1 line
2.28.0
#39 lore raw

PATCH v2 34/70 arch/um: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 arch/um/kernel/tlb.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)
arch/um/kernel/tlb.c +6 -8
index 61776790cd678..e40dd6deb1d21 100644
@@ -590,21 +590,19 @@ void flush_tlb_mm_range(struct mm_struct *mm, unsigned long start,
 
 void flush_tlb_mm(struct mm_struct *mm)
 {
-	struct vm_area_struct *vma = mm->mmap;
+	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	while (vma != NULL) {
+	mas_for_each(&mas, vma, ULONG_MAX)
 		fix_range(mm, vma->vm_start, vma->vm_end, 0);
-		vma = vma->vm_next;
-	}
 }
 
 void force_flush_all(void)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = mm->mmap;
+	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	while (vma != NULL) {
+	mas_for_each(&mas, vma, ULONG_MAX)
 		fix_range(mm, vma->vm_start, vma->vm_end, 1);
-		vma = vma->vm_next;
-	}
 }
Signature · 1 line
2.28.0
#40 lore raw

PATCH v2 35/70 arch/x86: Use maple tree iterators for vdso/vma

In reply to Liam R. Howlett
---
 arch/x86/entry/vdso/vma.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
arch/x86/entry/vdso/vma.c +5 -2
index 9185cb1d13b9b..f531efb00ba35 100644
@@ -144,9 +144,11 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 	struct mm_struct *mm = task->mm;
 	struct vm_area_struct *vma;
 
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
+
 	mmap_read_lock(mm);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long size = vma->vm_end - vma->vm_start;
 
 		if (vma_is_special_mapping(vma, &vvar_mapping))
@@ -371,6 +373,7 @@ int map_vdso_once(const struct vdso_image *image, unsigned long addr)
 {
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_write_lock(mm);
 	/*
@@ -380,7 +383,7 @@ int map_vdso_once(const struct vdso_image *image, unsigned long addr)
 	 * We could search vma near context.vdso, but it's a slowpath,
 	 * so let's explicitly check all VMAs to be completely sure.
 	 */
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma_is_special_mapping(vma, &vdso_mapping) ||
 				vma_is_special_mapping(vma, &vvar_mapping)) {
 			mmap_write_unlock(mm);
Signature · 1 line
2.28.0
#41 lore raw

PATCH v2 36/70 arch/xtensa: Use maple tree iterators for unmapped area

In reply to Liam R. Howlett
---
 arch/xtensa/kernel/syscall.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
arch/xtensa/kernel/syscall.c +2 -1
index 2c415fce6801a..26ec2e67879ad 100644
@@ -62,6 +62,7 @@ unsigned long arch_get_unmapped_area(struct file *filp, unsigned long addr,
 		unsigned long len, unsigned long pgoff, unsigned long flags)
 {
 	struct vm_area_struct *vmm;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	if (flags & MAP_FIXED) {
 		/* We do not accept a shared mapping if it would violate
@@ -83,7 +84,7 @@ unsigned long arch_get_unmapped_area(struct file *filp, unsigned long addr,
 	else
 		addr = PAGE_ALIGN(addr);
 
-	for (vmm = find_vma(current->mm, addr); ; vmm = vmm->vm_next) {
+	mas_for_each(&mas, vmm, ULONG_MAX) {
 		/* At this point:  (!vmm || addr < vmm->vm_end). */
 		if (TASK_SIZE - len < addr)
 			return -ENOMEM;
Signature · 1 line
2.28.0
#42 lore raw

PATCH v2 37/70 drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma()

In reply to Liam R. Howlett
---
 drivers/misc/cxl/fault.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
drivers/misc/cxl/fault.c +2 -1
index 01153b74334a1..47951b84f2cda 100644
@@ -313,6 +313,7 @@ static void cxl_prefault_vma(struct cxl_context *ctx)
 	struct vm_area_struct *vma;
 	int rc;
 	struct mm_struct *mm;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mm = get_mem_context(ctx);
 	if (mm == NULL) {
@@ -322,7 +323,7 @@ static void cxl_prefault_vma(struct cxl_context *ctx)
 	}
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		for (ea = vma->vm_start; ea < vma->vm_end;
 				ea = next_segment(ea, slb.vsid)) {
 			rc = copro_calculate_slb(mm, ea, &slb);
Signature · 1 line
2.28.0
#43 lore raw

PATCH v2 38/70 drivers/oprofile: Lookup address in tree instead of linked list.

In reply to Liam R. Howlett

Use the vma interface to find the vma if one exists instead of the linked list

---
 drivers/oprofile/buffer_sync.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)
drivers/oprofile/buffer_sync.c +4 -10
index cc917865f13ab..c63703b3bcebe 100644
@@ -253,15 +253,12 @@ static unsigned long get_exec_dcookie(struct mm_struct *mm)
 static unsigned long
 lookup_dcookie(struct mm_struct *mm, unsigned long addr, off_t *offset)
 {
-	unsigned long cookie = NO_COOKIE;
+	unsigned long cookie = INVALID_COOKIE;
 	struct vm_area_struct *vma;
 
 	mmap_read_lock(mm);
-	for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) {
-
-		if (addr < vma->vm_start || addr >= vma->vm_end)
-			continue;
-
+	vma = find_vma_intersection(mm, addr, addr + 1);
+	if (vma) {
 		if (vma->vm_file) {
 			cookie = fast_get_dcookie(&vma->vm_file->f_path);
 			*offset = (vma->vm_pgoff << PAGE_SHIFT) + addr -
@@ -269,13 +266,10 @@ lookup_dcookie(struct mm_struct *mm, unsigned long addr, off_t *offset)
 		} else {
 			/* must be an anonymous map */
 			*offset = addr;
+			cookie = NO_COOKIE;
 		}
-
-		break;
 	}
 
-	if (!vma)
-		cookie = INVALID_COOKIE;
 	mmap_read_unlock(mm);
 
 	return cookie;
Signature · 1 line
2.28.0
#44 lore raw

PATCH v2 39/70 drivers/tee/optee: Use maple tree iterators for __check_mem_type()

In reply to Liam R. Howlett
---
 drivers/tee/optee/call.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
drivers/tee/optee/call.c +9 -4
index c981757ba0d40..94acf379eaeeb 100644
@@ -545,12 +545,17 @@ static bool is_normal_memory(pgprot_t p)
 
 static int __check_mem_type(struct vm_area_struct *vma, unsigned long end)
 {
-	while (vma && is_normal_memory(vma->vm_page_prot)) {
-		if (vma->vm_end >= end)
-			return 0;
-		vma = vma->vm_next;
+	MA_STATE(mas, &vma->vm_mm->mm_mt, vma->vm_start, vma->vm_start);
+
+
+	mas_for_each(&mas, vma, end) {
+		if (!is_normal_memory(vma->vm_page_prot))
+		    break;
 	}
 
+	if (!vma)
+		return 0;
+
 	return -EINVAL;
 }
 
Signature · 1 line
2.28.0
#45 lore raw

PATCH v2 40/70 fs/binfmt_elf: Use maple tree iterators for fill_files_note()

In reply to Liam R. Howlett
---
 fs/binfmt_elf.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
fs/binfmt_elf.c +2 -1
index fa50e8936f5fc..92b67b914bf96 100644
@@ -1609,6 +1609,7 @@ static int fill_files_note(struct memelfnote *note)
 	user_long_t *data;
 	user_long_t *start_end_ofs;
 	char *name_base, *name_curpos;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* *Estimated* file count and total data size needed */
 	count = mm->map_count;
@@ -1633,7 +1634,7 @@ static int fill_files_note(struct memelfnote *note)
 	name_base = name_curpos = ((char *)data) + names_ofs;
 	remaining = size - names_ofs;
 	count = 0;
-	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		struct file *file;
 		const char *filename;
 
Signature · 1 line
2.28.0
#46 lore raw

PATCH v2 41/70 fs/coredump: Use maple tree iterators in place of linked list

In reply to Liam R. Howlett
---
 fs/coredump.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)
fs/coredump.c +7 -6
index c6acfc694f658..a69f281a08afb 100644
@@ -1040,10 +1040,10 @@ static unsigned long vma_dump_size(struct vm_area_struct *vma,
 	return vma->vm_end - vma->vm_start;
 }
 
-static struct vm_area_struct *first_vma(struct task_struct *tsk,
+static struct vm_area_struct *first_vma(struct mm_struct *mm,
 					struct vm_area_struct *gate_vma)
 {
-	struct vm_area_struct *ret = tsk->mm->mmap;
+	struct vm_area_struct *ret = find_vma(mm, 0);
 
 	if (ret)
 		return ret;
@@ -1054,12 +1054,13 @@ static struct vm_area_struct *first_vma(struct task_struct *tsk,
  * Helper function for iterating across a vma list.  It ensures that the caller
  * will visit `gate_vma' prior to terminating the search.
  */
-static struct vm_area_struct *next_vma(struct vm_area_struct *this_vma,
+static struct vm_area_struct *next_vma(struct mm_struct *mm,
+				       struct vm_area_struct *this_vma,
 				       struct vm_area_struct *gate_vma)
 {
 	struct vm_area_struct *ret;
 
-	ret = this_vma->vm_next;
+	ret = vma_next(mm, this_vma);
 	if (ret)
 		return ret;
 	if (this_vma == gate_vma)
@@ -1097,8 +1098,8 @@ int dump_vma_snapshot(struct coredump_params *cprm, int *vma_count,
 		return -ENOMEM;
 	}
 
-	for (i = 0, vma = first_vma(current, gate_vma); vma != NULL;
-			vma = next_vma(vma, gate_vma), i++) {
+	for (i = 0, vma = first_vma(mm, gate_vma); vma != NULL;
+			vma = next_vma(mm, vma, gate_vma), i++) {
 		struct core_vma_metadata *m = (*vma_meta) + i;
 
 		m->start = vma->vm_start;
Signature · 1 line
2.28.0
#47 lore raw

PATCH v2 42/70 fs/exec: Use vma_next() instead of linked list

In reply to Liam R. Howlett
---
 fs/exec.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
fs/exec.c +2 -2
index aa466921d6a97..6eb585ea1b841 100644
@@ -712,7 +712,7 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 		 * when the old and new regions overlap clear from new_end.
 		 */
 		free_pgd_range(&tlb, new_end, old_end, new_end,
-			vma->vm_next ? vma->vm_next->vm_start : USER_PGTABLES_CEILING);
+			vma_next(mm, vma) ? vma_next(mm, vma)->vm_start : USER_PGTABLES_CEILING);
 	} else {
 		/*
 		 * otherwise, clean from old_start; this is done to not touch
@@ -721,7 +721,7 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 		 * for the others its just a little faster.
 		 */
 		free_pgd_range(&tlb, old_start, old_end, new_end,
-			vma->vm_next ? vma->vm_next->vm_start : USER_PGTABLES_CEILING);
+			vma_next(mm, vma) ? vma_next(mm, vma)->vm_start : USER_PGTABLES_CEILING);
 	}
 	tlb_finish_mmu(&tlb, old_start, old_end);
 
Signature · 1 line
2.28.0
#48 lore raw

PATCH v2 43/70 fs/proc/base: Use maple tree iterators in place of linked list

In reply to Liam R. Howlett
---
 fs/proc/base.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
fs/proc/base.c +4 -1
index b362523a9829a..0a7d4d3d6ae9b 100644
@@ -2316,6 +2316,7 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 	GENRADIX(struct map_files_info) fa;
 	struct map_files_info *p;
 	int ret;
+	MA_STATE(mas, NULL, 0, 0);
 
 	genradix_init(&fa);
 
@@ -2343,6 +2344,7 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 	}
 
 	nr_files = 0;
+	mas.tree = &mm->mm_mt;
 
 	/*
 	 * We need two passes here:
@@ -2354,7 +2356,8 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 	 * routine might require mmap_lock taken in might_fault().
 	 */
 
-	for (vma = mm->mmap, pos = 2; vma; vma = vma->vm_next) {
+	pos = 2;
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma->vm_file)
 			continue;
 		if (++pos <= ctx->pos)
Signature · 1 line
2.28.0
#49 lore raw

PATCH v2 44/70 fs/proc/task_mmu: Stop using linked list and highest_vm_end

In reply to Liam R. Howlett

Remove references to mm_struct linked list and highest_vm_end for when they are removed

---
 fs/proc/task_mmu.c | 42 ++++++++++++++++++++++++------------------
 1 file changed, 24 insertions(+), 18 deletions(-)
fs/proc/task_mmu.c +24 -18
index 1ec2dd34ebffd..501d27ae2b772 100644
@@ -164,14 +164,13 @@ static void *m_start(struct seq_file *m, loff_t *ppos)
 static void *m_next(struct seq_file *m, void *v, loff_t *ppos)
 {
 	struct proc_maps_private *priv = m->private;
-	struct vm_area_struct *next, *vma = v;
+	struct vm_area_struct *next = NULL, *vma = v;
 
-	if (vma == priv->tail_vma)
-		next = NULL;
-	else if (vma->vm_next)
-		next = vma->vm_next;
-	else
-		next = priv->tail_vma;
+	if (vma != priv->tail_vma) {
+		next = vma_next(vma->vm_mm, vma);
+		if (!next)
+			next = priv->tail_vma;
+	}
 
 	*ppos = next ? next->vm_start : -1UL;
 
@@ -841,16 +840,16 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 {
 	struct proc_maps_private *priv = m->private;
 	struct mem_size_stats mss;
-	struct mm_struct *mm;
+	struct mm_struct *mm = priv->mm;
 	struct vm_area_struct *vma;
-	unsigned long last_vma_end = 0;
+	unsigned long vma_start, last_vma_end = 0;
 	int ret = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	priv->task = get_proc_task(priv->inode);
 	if (!priv->task)
 		return -ESRCH;
 
-	mm = priv->mm;
 	if (!mm || !mmget_not_zero(mm)) {
 		ret = -ESRCH;
 		goto out_put_task;
@@ -863,8 +862,13 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 		goto out_put_mm;
 
 	hold_task_mempolicy(priv);
+	vma = mas_find(&mas, 0);
+
+	if (vma)
+		vma_start = vma->vm_start;
 
-	for (vma = priv->mm->mmap; vma;) {
+	mas_set(&mas, 0);
+	mas_for_each(&mas, vma, -1) {
 		smap_gather_stats(vma, &mss, 0);
 		last_vma_end = vma->vm_end;
 
@@ -873,6 +877,7 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 		 * access it for write request.
 		 */
 		if (mmap_lock_is_contended(mm)) {
+			mas_pause(&mas);
 			mmap_read_unlock(mm);
 			ret = mmap_read_lock_killable(mm);
 			if (ret) {
@@ -916,7 +921,8 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 			 *    contains last_vma_end.
 			 *    Iterate VMA' from last_vma_end.
 			 */
-			vma = find_vma(mm, last_vma_end - 1);
+			mas.index = mas.last = last_vma_end - 1;
+			vma = mas_find(&mas, -1);
 			/* Case 3 above */
 			if (!vma)
 				break;
@@ -930,11 +936,9 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 				smap_gather_stats(vma, &mss, last_vma_end);
 		}
 		/* Case 2 above */
-		vma = vma->vm_next;
 	}
 
-	show_vma_header_prefix(m, priv->mm->mmap->vm_start,
-			       last_vma_end, 0, 0, 0, 0);
+	show_vma_header_prefix(m, vma_start, last_vma_end, 0, 0, 0, 0);
 	seq_pad(m, ' ');
 	seq_puts(m, "[rollup]\n");
 
@@ -1209,6 +1213,7 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 		return -ESRCH;
 	mm = get_task_mm(task);
 	if (mm) {
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 		struct mmu_notifier_range range;
 		struct clear_refs_private cp = {
 			.type = type,
@@ -1235,7 +1240,7 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 		}
 		tlb_gather_mmu(&tlb, mm, 0, -1);
 		if (type == CLEAR_REFS_SOFT_DIRTY) {
-			for (vma = mm->mmap; vma; vma = vma->vm_next) {
+			mas_for_each(&mas, vma, ULONG_MAX) {
 				if (!(vma->vm_flags & VM_SOFTDIRTY))
 					continue;
 				mmap_read_unlock(mm);
@@ -1243,7 +1248,8 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 					count = -EINTR;
 					goto out_mm;
 				}
-				for (vma = mm->mmap; vma; vma = vma->vm_next) {
+				mas_set(&mas, 0);
+				mas_for_each(&mas, vma, ULONG_MAX) {
 					vma->vm_flags &= ~VM_SOFTDIRTY;
 					vma_set_page_prot(vma);
 				}
@@ -1255,7 +1261,7 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 						0, NULL, mm, 0, -1UL);
 			mmu_notifier_invalidate_range_start(&range);
 		}
-		walk_page_range(mm, 0, mm->highest_vm_end, &clear_refs_walk_ops,
+		walk_page_range(mm, 0, -1, &clear_refs_walk_ops,
 				&cp);
 		if (type == CLEAR_REFS_SOFT_DIRTY)
 			mmu_notifier_invalidate_range_end(&range);
Signature · 1 line
2.28.0
#50 lore raw

PATCH v2 45/70 fs/userfaultfd: Stop using vma linked list.

In reply to Liam R. Howlett

Don't use the mm_struct linked list or the vma->vm_next in prep for removal

---
 fs/userfaultfd.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
fs/userfaultfd.c +17 -7
index 000b457ad0876..b0eac6fb3e8e2 100644
@@ -598,14 +598,16 @@ static void userfaultfd_event_wait_completion(struct userfaultfd_ctx *ctx,
 	if (release_new_ctx) {
 		struct vm_area_struct *vma;
 		struct mm_struct *mm = release_new_ctx->mm;
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 		/* the various vma->vm_userfaultfd_ctx still points to it */
 		mmap_write_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next)
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (vma->vm_userfaultfd_ctx.ctx == release_new_ctx) {
 				vma->vm_userfaultfd_ctx = NULL_VM_UFFD_CTX;
 				vma->vm_flags &= ~(VM_UFFD_WP | VM_UFFD_MISSING);
 			}
+		}
 		mmap_write_unlock(mm);
 
 		userfaultfd_ctx_put(release_new_ctx);
@@ -790,7 +792,9 @@ int userfaultfd_unmap_prep(struct vm_area_struct *vma,
 			   unsigned long start, unsigned long end,
 			   struct list_head *unmaps)
 {
-	for ( ; vma && vma->vm_start < end; vma = vma->vm_next) {
+	MA_STATE(mas, &vma->vm_mm->mm_mt, vma->vm_start, vma->vm_start);
+
+	mas_for_each(&mas, vma, end) {
 		struct userfaultfd_unmap_ctx *unmap_ctx;
 		struct userfaultfd_ctx *ctx = vma->vm_userfaultfd_ctx.ctx;
 
@@ -840,6 +844,7 @@ static int userfaultfd_release(struct inode *inode, struct file *file)
 	/* len == 0 means wake all */
 	struct userfaultfd_wake_range range = { .len = 0, };
 	unsigned long new_flags;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	WRITE_ONCE(ctx->released, true);
 
@@ -856,7 +861,7 @@ static int userfaultfd_release(struct inode *inode, struct file *file)
 	 */
 	mmap_write_lock(mm);
 	prev = NULL;
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		cond_resched();
 		BUG_ON(!!vma->vm_userfaultfd_ctx.ctx ^
 		       !!(vma->vm_flags & (VM_UFFD_MISSING | VM_UFFD_WP)));
@@ -1270,6 +1275,7 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	bool found;
 	bool basic_ioctls;
 	unsigned long start, end, vma_end;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	user_uffdio_register = (struct uffdio_register __user *) arg;
 
@@ -1328,7 +1334,8 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	 */
 	found = false;
 	basic_ioctls = false;
-	for (cur = vma; cur && cur->vm_start < end; cur = cur->vm_next) {
+	mas_set(&mas, vma->vm_start);
+	mas_for_each(&mas, cur, end) {
 		cond_resched();
 
 		BUG_ON(!!cur->vm_userfaultfd_ctx.ctx ^
@@ -1444,7 +1451,7 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	skip:
 		prev = vma;
 		start = vma->vm_end;
-		vma = vma->vm_next;
+		vma = vma_next(mm, vma);
 	} while (vma && vma->vm_start < end);
 out_unlock:
 	mmap_write_unlock(mm);
@@ -1485,6 +1492,7 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	bool found;
 	unsigned long start, end, vma_end;
 	const void __user *buf = (void __user *)arg;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	ret = -EFAULT;
 	if (copy_from_user(&uffdio_unregister, buf, sizeof(uffdio_unregister)))
@@ -1528,7 +1536,9 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	 */
 	found = false;
 	ret = -EINVAL;
-	for (cur = vma; cur && cur->vm_start < end; cur = cur->vm_next) {
+	mas_set(&mas, vma->vm_start);
+
+	mas_for_each(&mas, cur, end) {
 		cond_resched();
 
 		BUG_ON(!!cur->vm_userfaultfd_ctx.ctx ^
@@ -1614,7 +1624,7 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	skip:
 		prev = vma;
 		start = vma->vm_end;
-		vma = vma->vm_next;
+		vma = vma_next(mm, vma);
 	} while (vma && vma->vm_start < end);
 out_unlock:
 	mmap_write_unlock(mm);
Signature · 1 line
2.28.0
#51 lore raw

PATCH v2 46/70 ipc/shm: Stop using the vma linked list

In reply to Liam R. Howlett

When searching for a VMA, a maple state can be used instead of the linked list in the mm_struct

---
 ipc/shm.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)
ipc/shm.c +7 -6
index e25c7c6106bcf..4ad8788352099 100644
@@ -1631,6 +1631,7 @@ long ksys_shmdt(char __user *shmaddr)
 	loff_t size = 0;
 	struct file *file;
 	struct vm_area_struct *next;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 #endif
 
 	if (addr & ~PAGE_MASK)
@@ -1660,11 +1661,11 @@ long ksys_shmdt(char __user *shmaddr)
 	 * match the usual checks anyway. So assume all vma's are
 	 * above the starting address given.
 	 */
-	vma = find_vma(mm, addr);
 
 #ifdef CONFIG_MMU
+	vma = mas_find(&mas, ULONG_MAX);
 	while (vma) {
-		next = vma->vm_next;
+		next = mas_find(&mas, ULONG_MAX);
 
 		/*
 		 * Check if the starting address would match, i.e. it's
@@ -1703,21 +1704,21 @@ long ksys_shmdt(char __user *shmaddr)
 	 */
 	size = PAGE_ALIGN(size);
 	while (vma && (loff_t)(vma->vm_end - addr) <= size) {
-		next = vma->vm_next;
-
 		/* finding a matching vma now does not alter retval */
 		if ((vma->vm_ops == &shm_vm_ops) &&
 		    ((vma->vm_start - addr)/PAGE_SIZE == vma->vm_pgoff) &&
 		    (vma->vm_file == file))
 			do_munmap(mm, vma->vm_start, vma->vm_end - vma->vm_start, NULL);
-		vma = next;
+
+		vma = mas_find(&mas, addr + size - 1);
 	}
 
 #else	/* CONFIG_MMU */
+	vma = mas_walk(&mas);
 	/* under NOMMU conditions, the exact address to be destroyed must be
 	 * given
 	 */
-	if (vma && vma->vm_start == addr && vma->vm_ops == &shm_vm_ops) {
+	if (vma && vma->vm_ops == &shm_vm_ops) {
 		do_munmap(mm, vma->vm_start, vma->vm_end - vma->vm_start, NULL);
 		retval = 0;
 	}
Signature · 1 line
2.28.0
#52 lore raw

PATCH v2 47/70 kernel/acct: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 kernel/acct.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
kernel/acct.c +2 -4
index f175df8f6aa4a..bcfe2cf7c7c0f 100644
@@ -537,16 +537,14 @@ void acct_collect(long exitcode, int group_dead)
 	struct pacct_struct *pacct = &current->signal->pacct;
 	u64 utime, stime;
 	unsigned long vsize = 0;
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 
 	if (group_dead && current->mm) {
 		struct vm_area_struct *vma;
 
 		mmap_read_lock(current->mm);
-		vma = current->mm->mmap;
-		while (vma) {
+		mas_for_each(&mas, vma, -1)
 			vsize += vma->vm_end - vma->vm_start;
-			vma = vma->vm_next;
-		}
 		mmap_read_unlock(current->mm);
 	}
 
Signature · 1 line
2.28.0
#53 lore raw

PATCH v2 48/70 kernel/events/core: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 kernel/events/core.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/events/core.c +2 -1
index dc568ca295bdc..767bec30c395f 100644
@@ -9888,8 +9888,9 @@ static void perf_addr_filter_apply(struct perf_addr_filter *filter,
 				   struct perf_addr_filter_range *fr)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma->vm_file)
 			continue;
 
Signature · 1 line
2.28.0
#54 lore raw

PATCH v2 49/70 kernel/events/uprobes: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 kernel/events/uprobes.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
kernel/events/uprobes.c +6 -3
index 00b0358739ab3..b0aa05be2a61d 100644
@@ -356,8 +356,9 @@ static struct vm_area_struct *
 find_ref_ctr_vma(struct uprobe *uprobe, struct mm_struct *mm)
 {
 	struct vm_area_struct *tmp;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (tmp = mm->mmap; tmp; tmp = tmp->vm_next)
+	mas_for_each(&mas, tmp, ULONG_MAX)
 		if (valid_ref_ctr_vma(uprobe, tmp))
 			return tmp;
 
@@ -1239,9 +1240,10 @@ static int unapply_uprobe(struct uprobe *uprobe, struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	int err = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long vaddr;
 		loff_t offset;
 
@@ -1990,8 +1992,9 @@ bool uprobe_deny_signal(void)
 static void mmf_recalc_uprobes(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!valid_vma(vma, false))
 			continue;
 		/*
Signature · 1 line
2.28.0
#55 lore raw

PATCH v2 50/70 kernel/sched/fair: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 kernel/sched/fair.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
kernel/sched/fair.c +7 -3
index ae7ceba8fd4f2..1cb3a245ffd85 100644
@@ -2723,6 +2723,7 @@ static void task_numa_work(struct callback_head *work)
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
 	long pages, virtpages;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	SCHED_WARN_ON(p != container_of(work, struct task_struct, numa_work));
 
@@ -2775,13 +2776,16 @@ static void task_numa_work(struct callback_head *work)
 
 	if (!mmap_read_trylock(mm))
 		return;
-	vma = find_vma(mm, start);
+
+	mas_set(&mas, start);
+	vma = mas_walk(&mas);
 	if (!vma) {
 		reset_ptenuma_scan(p);
 		start = 0;
-		vma = mm->mmap;
+		mas_set(&mas, start);
 	}
-	for (; vma; vma = vma->vm_next) {
+
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma_migratable(vma) || !vma_policy_mof(vma) ||
 			is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
 			continue;
Signature · 1 line
2.28.0
#56 lore raw

PATCH v2 51/70 kernel/sys: Use maple tree iterators instead of linked list

In reply to Liam R. Howlett
---
 kernel/sys.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sys.c +2 -1
index a730c03ee607c..fe061c54a5a46 100644
@@ -1858,9 +1858,10 @@ static int prctl_set_mm_exe_file(struct mm_struct *mm, unsigned int fd)
 	err = -EBUSY;
 	if (exe_file) {
 		struct vm_area_struct *vma;
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 		mmap_read_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (!vma->vm_file)
 				continue;
 			if (path_equal(&vma->vm_file->f_path,
Signature · 1 line
2.28.0
#57 lore raw

PATCH v2 52/70 mm/gup: Use maple tree navigation instead of linked list

In reply to Liam R. Howlett
---
 mm/gup.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
mm/gup.c +4 -3
index b06e2a6d90187..20392efb2d9ba 100644
@@ -1465,6 +1465,7 @@ int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
 	struct vm_area_struct *vma = NULL;
 	int locked = 0;
 	long ret = 0;
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
 	end = start + len;
 
@@ -1476,10 +1477,10 @@ int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
 		if (!locked) {
 			locked = 1;
 			mmap_read_lock(mm);
-			vma = find_vma(mm, nstart);
+			vma = mas_find(&mas, end);
 		} else if (nstart >= vma->vm_end)
-			vma = vma->vm_next;
-		if (!vma || vma->vm_start >= end)
+			vma = mas_next(&mas, end);
+		if (!vma)
 			break;
 		/*
 		 * Set [nstart; nend) to intersection of desired address
Signature · 1 line
2.28.0
#58 lore raw

PATCH v2 53/70 mm/huge_memory: Use vma_next() instead of vma linked list

In reply to Liam R. Howlett
---
 mm/huge_memory.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
mm/huge_memory.c +3 -3
index ec2bb93f74314..4005beb23daf9 100644
@@ -2304,12 +2304,12 @@ void vma_adjust_trans_huge(struct vm_area_struct *vma,
 		split_huge_pmd_address(vma, end, false, NULL);
 
 	/*
-	 * If we're also updating the vma->vm_next->vm_start, if the new
-	 * vm_next->vm_start isn't hpage aligned and it could previously
+	 * If we're also updating the vma_next(vma)->vm_start, if the new
+	 * vma_next()->vm_start isn't hpage aligned and it could previously
 	 * contain an hugepage: check if we need to split an huge pmd.
 	 */
 	if (adjust_next > 0) {
-		struct vm_area_struct *next = vma->vm_next;
+		struct vm_area_struct *next = vma_next(vma->vm_mm, vma);
 		unsigned long nstart = next->vm_start;
 		nstart += adjust_next;
 		if (nstart & ~HPAGE_PMD_MASK &&
Signature · 1 line
2.28.0
#59 lore raw

PATCH v2 54/70 mm/khugepaged: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/khugepaged.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
mm/khugepaged.c +5 -2
index 4e3dff13eb70c..fbfcee552da6c 100644
@@ -2049,6 +2049,7 @@ static unsigned int khugepaged_scan_mm_slot(unsigned int pages,
 	struct mm_struct *mm;
 	struct vm_area_struct *vma;
 	int progress = 0;
+	MA_STATE(mas, NULL, 0, 0);
 
 	VM_BUG_ON(!pages);
 	lockdep_assert_held(&khugepaged_mm_lock);
@@ -2065,18 +2066,20 @@ static unsigned int khugepaged_scan_mm_slot(unsigned int pages,
 	khugepaged_collapse_pte_mapped_thps(mm_slot);
 
 	mm = mm_slot->mm;
+	mas.tree = &mm->mm_mt;
 	/*
 	 * Don't wait for semaphore (to avoid long wait times).  Just move to
 	 * the next mm on the list.
 	 */
 	vma = NULL;
+	mas_set(&mas, khugepaged_scan.address);
 	if (unlikely(!mmap_read_trylock(mm)))
 		goto breakouterloop_mmap_lock;
 	if (likely(!khugepaged_test_exit(mm)))
-		vma = find_vma(mm, khugepaged_scan.address);
+		vma = mas_find(&mas, ULONG_MAX);
 
 	progress++;
-	for (; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long hstart, hend;
 
 		cond_resched();
Signature · 1 line
2.28.0
#60 lore raw

PATCH v2 55/70 mm/ksm: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/ksm.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
mm/ksm.c +11 -7
index 0960750bb316d..9aa579cef7614 100644
@@ -975,10 +975,12 @@ static int unmerge_and_remove_all_rmap_items(void)
 	spin_unlock(&ksm_mmlist_lock);
 
 	for (mm_slot = ksm_scan.mm_slot;
-			mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
-		mm = mm_slot->mm;
+			mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot, mm = mm_slot->mm) {
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
+
 		mmap_read_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		mas_set(&mas, 0);
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (ksm_test_exit(mm))
 				break;
 			if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
@@ -2286,13 +2288,14 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	mm = slot->mm;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
+
 	mmap_read_lock(mm);
 	if (ksm_test_exit(mm))
-		vma = NULL;
-	else
-		vma = find_vma(mm, ksm_scan.address);
+		goto no_vmas;
 
-	for (; vma; vma = vma->vm_next) {
+	mas_set(&mas, ksm_scan.address);
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!(vma->vm_flags & VM_MERGEABLE))
 			continue;
 		if (ksm_scan.address < vma->vm_start)
@@ -2330,6 +2333,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	if (ksm_test_exit(mm)) {
+no_vmas:
 		ksm_scan.address = 0;
 		ksm_scan.rmap_list = &slot->rmap_list;
 	}
Signature · 1 line
2.28.0
#61 lore raw

PATCH v2 56/70 mm/madvise: Use vma_next instead of vma linked list

In reply to Liam R. Howlett
---
 mm/madvise.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/madvise.c +1 -1
index 13f5677b93222..0da3c9a5f5b82 100644
@@ -1151,7 +1151,7 @@ int do_madvise(struct mm_struct *mm, unsigned long start, size_t len_in, int beh
 		if (start >= end)
 			goto out;
 		if (prev)
-			vma = prev->vm_next;
+			vma = vma_next(mm, prev);
 		else	/* madvise_remove dropped mmap_lock */
 			vma = find_vma(mm, start);
 	}
Signature · 1 line
2.28.0
#62 lore raw

PATCH v2 57/70 mm/memcontrol: Stop using mm->highest_vm_end

In reply to Liam R. Howlett
---
 mm/memcontrol.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
mm/memcontrol.c +2 -4
index 29459a6ce1c7a..7fe753d6a81f1 100644
@@ -5892,7 +5892,7 @@ static unsigned long mem_cgroup_count_precharge(struct mm_struct *mm)
 	unsigned long precharge;
 
 	mmap_read_lock(mm);
-	walk_page_range(mm, 0, mm->highest_vm_end, &precharge_walk_ops, NULL);
+	walk_page_range(mm, 0, -1, &precharge_walk_ops, NULL);
 	mmap_read_unlock(mm);
 
 	precharge = mc.precharge;
@@ -6190,9 +6190,7 @@ static void mem_cgroup_move_charge(void)
 	 * When we have consumed all precharges and failed in doing
 	 * additional charge, the page walk just aborts.
 	 */
-	walk_page_range(mc.mm, 0, mc.mm->highest_vm_end, &charge_walk_ops,
-			NULL);
-
+	walk_page_range(mc.mm, 0, -1, &charge_walk_ops, NULL);
 	mmap_read_unlock(mc.mm);
 	atomic_dec(&mc.from->moving_account);
 }
Signature · 1 line
2.28.0
#63 lore raw

PATCH v2 58/70 mm/mempolicy: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/mempolicy.c | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)
mm/mempolicy.c +20 -13
index 3ca4898f3f249..e0b8e658f18eb 100644
@@ -404,9 +404,10 @@ void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new)
 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_write_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next)
+	mas_for_each(&mas, vma, ULONG_MAX)
 		mpol_rebind_policy(vma->vm_policy, new);
 	mmap_write_unlock(mm);
 }
@@ -671,7 +672,7 @@ static unsigned long change_prot_numa(struct vm_area_struct *vma,
 static int queue_pages_test_walk(unsigned long start, unsigned long end,
 				struct mm_walk *walk)
 {
-	struct vm_area_struct *vma = walk->vma;
+	struct vm_area_struct *next, *vma = walk->vma;
 	struct queue_pages *qp = walk->private;
 	unsigned long endvma = vma->vm_end;
 	unsigned long flags = qp->flags;
@@ -686,9 +687,10 @@ static int queue_pages_test_walk(unsigned long start, unsigned long end,
 			/* hole at head side of range */
 			return -EFAULT;
 	}
+	next = vma_next(vma->vm_mm, vma);
 	if (!(flags & MPOL_MF_DISCONTIG_OK) &&
 		((vma->vm_end < qp->end) &&
-		(!vma->vm_next || vma->vm_end < vma->vm_next->vm_start)))
+		(!next || vma->vm_end < next->vm_start)))
 		/* hole at middle or tail of range */
 		return -EFAULT;
 
@@ -809,21 +811,22 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 	pgoff_t pgoff;
 	unsigned long vmstart;
 	unsigned long vmend;
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
-	vma = find_vma(mm, start);
+	vma = mas_find(&mas, ULONG_MAX);
 	VM_BUG_ON(!vma);
 
-	prev = vma->vm_prev;
+	prev = vma_mas_prev(&mas);
 	if (start > vma->vm_start)
 		prev = vma;
 
-	for (; vma && vma->vm_start < end; prev = vma, vma = next) {
-		next = vma->vm_next;
+	mas_for_each(&mas, vma, end - 1) {
+		next = vma_next(mm, vma);
 		vmstart = max(start, vma->vm_start);
 		vmend   = min(end, vma->vm_end);
 
 		if (mpol_equal(vma_policy(vma), new_pol))
-			continue;
+			goto next;
 
 		pgoff = vma->vm_pgoff +
 			((vmstart - vma->vm_start) >> PAGE_SHIFT);
@@ -832,7 +835,7 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 				 new_pol, vma->vm_userfaultfd_ctx);
 		if (prev) {
 			vma = prev;
-			next = vma->vm_next;
+			next = vma_next(mm, vma);
 			if (mpol_equal(vma_policy(vma), new_pol))
 				continue;
 			/* vma_merge() joined vma && vma->next, case 8 */
@@ -847,11 +850,14 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 			err = split_vma(vma->vm_mm, vma, vmend, 0);
 			if (err)
 				goto out;
+			mas_pause(&mas);
 		}
  replace:
 		err = vma_replace_policy(vma, new_pol);
 		if (err)
 			goto out;
+next:
+		prev = vma;
 	}
 
  out:
@@ -1072,6 +1078,7 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 			   int flags)
 {
 	nodemask_t nmask;
+	struct vm_area_struct *vma;
 	LIST_HEAD(pagelist);
 	int err = 0;
 	struct migration_target_control mtc = {
@@ -1087,8 +1094,9 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 	 * need migration.  Between passing in the full user address
 	 * space range and MPOL_MF_DISCONTIG_OK, this call can not fail.
 	 */
+	vma = find_vma(mm, 0);
 	VM_BUG_ON(!(flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)));
-	queue_pages_range(mm, mm->mmap->vm_start, mm->task_size, &nmask,
+	queue_pages_range(mm, vma->vm_start, mm->task_size, &nmask,
 			flags | MPOL_MF_DISCONTIG_OK, &pagelist);
 
 	if (!list_empty(&pagelist)) {
@@ -1217,13 +1225,12 @@ static struct page *new_page(struct page *page, unsigned long start)
 {
 	struct vm_area_struct *vma;
 	unsigned long address;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
-	vma = find_vma(current->mm, start);
-	while (vma) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		address = page_address_in_vma(page, vma);
 		if (address != -EFAULT)
 			break;
-		vma = vma->vm_next;
 	}
 
 	if (PageHuge(page)) {
Signature · 1 line
2.28.0
#64 lore raw

PATCH v2 59/70 mm/mlock: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/mlock.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)
mm/mlock.c +10 -10
index 884b1216da6a6..2c27597ebcf6b 100644
@@ -591,6 +591,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 	unsigned long nstart, end, tmp;
 	struct vm_area_struct * vma, * prev;
 	int error;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	VM_BUG_ON(offset_in_page(start));
 	VM_BUG_ON(len != PAGE_ALIGN(len));
@@ -599,11 +600,11 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		return -EINVAL;
 	if (end == start)
 		return 0;
-	vma = find_vma(current->mm, start);
-	if (!vma || vma->vm_start > start)
+	vma = mas_walk(&mas);
+	if (!vma)
 		return -ENOMEM;
 
-	prev = vma->vm_prev;
+	prev = mas_prev(&mas, 0);
 	if (start > vma->vm_start)
 		prev = vma;
 
@@ -625,7 +626,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		if (nstart >= end)
 			break;
 
-		vma = prev->vm_next;
+		vma = vma_next(prev->vm_mm, prev);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			break;
@@ -646,15 +647,12 @@ static unsigned long count_mm_mlocked_page_nr(struct mm_struct *mm,
 {
 	struct vm_area_struct *vma;
 	unsigned long count = 0;
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
 	if (mm == NULL)
 		mm = current->mm;
 
-	vma = find_vma(mm, start);
-	if (vma == NULL)
-		vma = mm->mmap;
-
-	for (; vma ; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, start + len) {
 		if (start >= vma->vm_end)
 			continue;
 		if (start + len <=  vma->vm_start)
@@ -769,6 +767,7 @@ static int apply_mlockall_flags(int flags)
 {
 	struct vm_area_struct * vma, * prev = NULL;
 	vm_flags_t to_add = 0;
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 
 	current->mm->def_flags &= VM_LOCKED_CLEAR_MASK;
 	if (flags & MCL_FUTURE) {
@@ -787,7 +786,7 @@ static int apply_mlockall_flags(int flags)
 			to_add |= VM_LOCKONFAULT;
 	}
 
-	for (vma = current->mm->mmap; vma ; vma = prev->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		vm_flags_t newflags;
 
 		newflags = vma->vm_flags & VM_LOCKED_CLEAR_MASK;
@@ -795,6 +794,7 @@ static int apply_mlockall_flags(int flags)
 
 		/* Ignore errors */
 		mlock_fixup(vma, &prev, vma->vm_start, vma->vm_end, newflags);
+		mas_pause(&mas);
 		cond_resched();
 	}
 out:
Signature · 1 line
2.28.0
#65 lore raw

PATCH v2 60/70 mm/mprotect: Use maple tree navigation instead of vma linked list

In reply to Liam R. Howlett
---
 mm/mprotect.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
mm/mprotect.c +5 -3
index 56c02beb60414..a6208b872336e 100644
@@ -518,6 +518,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	const int grows = prot & (PROT_GROWSDOWN|PROT_GROWSUP);
 	const bool rier = (current->personality & READ_IMPLIES_EXEC) &&
 				(prot & PROT_READ);
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	start = untagged_addr(start);
 
@@ -549,11 +550,12 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	if ((pkey != -1) && !mm_pkey_is_allocated(current->mm, pkey))
 		goto out;
 
-	vma = find_vma(current->mm, start);
+	mas_set(&mas, start);
+	vma = mas_walk(&mas);
 	error = -ENOMEM;
 	if (!vma)
 		goto out;
-	prev = vma->vm_prev;
+	prev = mas_prev(&mas, 0);
 	if (unlikely(grows & PROT_GROWSDOWN)) {
 		if (vma->vm_start >= end)
 			goto out;
@@ -626,7 +628,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 		if (nstart >= end)
 			goto out;
 
-		vma = prev->vm_next;
+		vma = mas_next(&mas, ULONG_MAX);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			goto out;
Signature · 1 line
2.28.0
#66 lore raw

PATCH v2 61/70 mm/mremap: Use vma_next() instead of vma linked list

In reply to Liam R. Howlett
---
 mm/mremap.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
mm/mremap.c +4 -2
index a7526a8c1fe5a..3b6e7f0324635 100644
@@ -465,7 +465,7 @@ static unsigned long move_vma(struct vm_area_struct *vma,
 	if (excess) {
 		vma->vm_flags |= VM_ACCOUNT;
 		if (split)
-			vma->vm_next->vm_flags |= VM_ACCOUNT;
+			vma_next(mm, vma)->vm_flags |= VM_ACCOUNT;
 	}
 
 	return new_addr;
@@ -638,9 +638,11 @@ static unsigned long mremap_to(unsigned long addr, unsigned long old_len,
 static int vma_expandable(struct vm_area_struct *vma, unsigned long delta)
 {
 	unsigned long end = vma->vm_end + delta;
+	struct vm_area_struct *next;
 	if (end < vma->vm_end) /* overflow */
 		return 0;
-	if (vma->vm_next && vma->vm_next->vm_start < end) /* intersection */
+	next = vma_next(vma->vm_mm, vma);
+	if (next && next->vm_start < end) /* intersection */
 		return 0;
 	if (get_unmapped_area(NULL, vma->vm_start, end - vma->vm_start,
 			      0, MAP_FIXED) & ~PAGE_MASK)
Signature · 1 line
2.28.0
#67 lore raw

PATCH v2 62/70 mm/msync: Use vma_next() instead of vma linked list

In reply to Liam R. Howlett
---
 mm/msync.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/msync.c +1 -1
index 69c6d20295318..8100ad5b12eb8 100644
@@ -100,7 +100,7 @@ SYSCALL_DEFINE3(msync, unsigned long, start, size_t, len, int, flags)
 				error = 0;
 				goto out_unlock;
 			}
-			vma = vma->vm_next;
+			vma = vma_next(mm, vma);
 		}
 	}
 out_unlock:
Signature · 1 line
2.28.0
#68 lore raw

PATCH v2 63/70 mm/nommu: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/nommu.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)
mm/nommu.c +6 -4
index 0faf39b32cdb9..4e5cc63728b65 100644
@@ -677,6 +677,7 @@ static void delete_vma(struct mm_struct *mm, struct vm_area_struct *vma)
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* check the cache first */
 	vma = vmacache_find(mm, addr);
@@ -685,7 +686,7 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 
 	/* trawl the list (there may be multiple mappings in which addr
 	 * resides) */
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma->vm_start > addr)
 			return NULL;
 		if (vma->vm_end > addr) {
@@ -726,6 +727,7 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 {
 	struct vm_area_struct *vma;
 	unsigned long end = addr + len;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* check the cache first */
 	vma = vmacache_find_exact(mm, addr, end);
@@ -734,7 +736,7 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 
 	/* trawl the list (there may be multiple mappings in which addr
 	 * resides) */
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma->vm_start < addr)
 			continue;
 		if (vma->vm_start > addr)
@@ -1485,7 +1487,7 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len, struct list
 				return -EINVAL;
 			if (end == vma->vm_end)
 				goto erase_whole_vma;
-			vma = vma->vm_next;
+			vma = vma_next(vma);
 		} while (vma);
 		return -EINVAL;
 	} else {
@@ -1543,7 +1545,7 @@ void exit_mmap(struct mm_struct *mm)
 	mm->total_vm = 0;
 
 	while ((vma = mm->mmap)) {
-		mm->mmap = vma->vm_next;
+		mm->mmap = vma_next(vma);
 		delete_vma_from_mm(vma);
 		delete_vma(mm, vma);
 		cond_resched();
Signature · 1 line
2.28.0
#69 lore raw

PATCH v2 64/70 mm/oom_kill: Use maple tree iterators instead of vma linked list

In reply to Liam R. Howlett
---
 mm/oom_kill.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
mm/oom_kill.c +2 -1
index 8b84661a64109..a5e2045ec2763 100644
@@ -514,6 +514,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	bool ret = true;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/*
 	 * Tell all users of get_user/copy_from_user etc... that the content
@@ -523,7 +524,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 	 */
 	set_bit(MMF_UNSTABLE, &mm->flags);
 
-	for (vma = mm->mmap ; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!can_madv_lru_vma(vma))
 			continue;
 
Signature · 1 line
2.28.0
#70 lore raw

PATCH v2 65/70 mm/pagewalk: Use vma_next() instead of vma linked list

In reply to Liam R. Howlett
---
 mm/pagewalk.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/pagewalk.c +1 -1
index e81640d9f1770..20bd8d14d0425 100644
@@ -408,7 +408,7 @@ int walk_page_range(struct mm_struct *mm, unsigned long start,
 		} else { /* inside vma */
 			walk.vma = vma;
 			next = min(end, vma->vm_end);
-			vma = vma->vm_next;
+			vma = vma_next(mm, vma);;
 
 			err = walk_page_test(start, next, &walk);
 			if (err > 0) {
Signature · 1 line
2.28.0
#71 lore raw

PATCH v2 66/70 mm/swapfile: Use maple tree iterator instead of vma linked list

In reply to Liam R. Howlett
---
 mm/swapfile.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
mm/swapfile.c +2 -1
index d58361109066d..10e1d60ff6f89 100644
@@ -2104,9 +2104,10 @@ static int unuse_mm(struct mm_struct *mm, unsigned int type,
 {
 	struct vm_area_struct *vma;
 	int ret = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma->anon_vma) {
 			ret = unuse_vma(vma, type, frontswap,
 					fs_pages_to_unuse);
Signature · 1 line
2.28.0
#72 lore raw

PATCH v2 67/70 mm/nommu: Stop inserting into the vma linked list

In reply to Liam R. Howlett
---
 mm/nommu.c | 4 ----
 1 file changed, 4 deletions(-)
mm/nommu.c +0 -4
index 4e5cc63728b65..a3f97a612f16a 100644
@@ -617,8 +617,6 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 	prev = NULL;
 	if (rb_prev)
 		prev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
-
-	__vma_link_list(mm, vma, prev);
 }
 
 /*
@@ -653,8 +651,6 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
 	/* remove from the MM's tree and list */
 	rb_erase(&vma->vm_rb, &mm->mm_rb);
-
-	__vma_unlink_list(mm, vma);
 }
 
 /*
Signature · 1 line
2.28.0
#73 lore raw

PATCH v2 68/70 mm/util: Remove __vma_link_list() and __vma_unlink_list()

In reply to Liam R. Howlett
---
 mm/util.c | 40 ----------------------------------------
 1 file changed, 40 deletions(-)
mm/util.c +0 -40
index 48c79f2784eca..74888472a0848 100644
@@ -271,46 +271,6 @@ void *memdup_user_nul(const void __user *src, size_t len)
 }
 EXPORT_SYMBOL(memdup_user_nul);
 
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev)
-{
-	struct vm_area_struct *next;
-
-	vma->vm_prev = prev;
-	if (prev) {
-		next = prev->vm_next;
-		prev->vm_next = vma;
-	} else {
-		next = mm->mmap;
-		mm->mmap = vma;
-	}
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
-	else
-		mm->highest_vm_end = vm_end_gap(vma);
-}
-
-void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
-{
-	struct vm_area_struct *prev, *next;
-
-	next = vma->vm_next;
-	prev = vma->vm_prev;
-	if (prev)
-		prev->vm_next = next;
-	else
-		mm->mmap = next;
-	if (next)
-		next->vm_prev = prev;
-	else {
-		if (prev)
-			mm->highest_vm_end = vm_end_gap(prev);
-		else
-			mm->highest_vm_end = 0;
-	}
-}
-
 /* Check if the vma is being used as a stack by this task */
 int vma_is_stack_for_current(struct vm_area_struct *vma)
 {
Signature · 1 line
2.28.0
#74 lore raw

PATCH v2 69/70 mm: Remove vma linked list.

In reply to Liam R. Howlett

The vma linked list has been replaced by the maple tree iterators and vma_next() vma_prev() functions.

A part of this change is also the iterators free_pgd_range(), zap_page_range(), and unmap_single_vma()

---
 include/linux/mm_types.h |   8 +-
 kernel/fork.c            |  15 +-
 mm/debug.c               |  12 +-
 mm/internal.h            |   4 +-
 mm/memory.c              |  39 +--
 mm/mmap.c                | 522 +++++++++++++++------------------------
 6 files changed, 241 insertions(+), 359 deletions(-)
include/linux/mm_types.h +1 -7
index 5a85b76bb9b9a..630673866af94 100644
@@ -303,14 +303,11 @@ struct vm_userfaultfd_ctx {};
  * library, the executable area etc).
  */
 struct vm_area_struct {
-	/* The first cache line has the info for VMA tree walking. */
-
 	unsigned long vm_start;		/* Our start address within vm_mm. */
 	unsigned long vm_end;		/* The first byte after our end address
 					   within vm_mm. */
 
 	/* linked list of VM areas per task, sorted by address */
-	struct vm_area_struct *vm_next, *vm_prev;
 	struct mm_struct *vm_mm;	/* The address space we belong to. */
 
 	/*
@@ -324,8 +321,7 @@ struct vm_area_struct {
 	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
 					 * units
 					 */
-	/* Second cache line starts here. */
-	struct file *vm_file;		/* File we map to (can be NULL). */
+	struct file * vm_file;		/* File we map to (can be NULL). */
 	/*
 	 * For areas with an address space and backing store,
 	 * linkage into the address_space->i_mmap interval tree.
@@ -378,7 +374,6 @@ struct core_state {
 struct kioctx_table;
 struct mm_struct {
 	struct {
-		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
@@ -393,7 +388,6 @@ struct mm_struct {
 		unsigned long mmap_compat_legacy_base;
 #endif
 		unsigned long task_size;	/* size of task vm space */
-		unsigned long highest_vm_end;	/* highest vma end address */
 		pgd_t * pgd;
 
 #ifdef CONFIG_MEMBARRIER
kernel/fork.c +1 -14
index b8c25c2e9587f..d3c22604493f9 100644
@@ -363,7 +363,6 @@ struct vm_area_struct *vm_area_dup(struct vm_area_struct *orig)
 		 */
 		*new = data_race(*orig);
 		INIT_LIST_HEAD(&new->anon_vma_chain);
-		new->vm_next = new->vm_prev = NULL;
 	}
 	return new;
 }
@@ -468,7 +467,7 @@ EXPORT_SYMBOL(free_task);
 static __latent_entropy int dup_mmap(struct mm_struct *mm,
 					struct mm_struct *oldmm)
 {
-	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
+	struct vm_area_struct *mpnt, *tmp;
 	int retval;
 	unsigned long charge = 0;
 	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
@@ -495,7 +494,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	mm->exec_vm = oldmm->exec_vm;
 	mm->stack_vm = oldmm->stack_vm;
 
-	pprev = &mm->mmap;
 	retval = ksm_fork(mm, oldmm);
 	if (retval)
 		goto out;
@@ -503,8 +501,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	if (retval)
 		goto out;
 
-	prev = NULL;
-
 	retval = mas_entry_count(&mas, oldmm->map_count);
 	if (retval)
 		goto fail_nomem;
@@ -579,14 +575,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		if (is_vm_hugetlb_page(tmp))
 			reset_vma_resv_huge_pages(tmp);
 
-		/*
-		 * Link in the new vma and copy the page table entries.
-		 */
-		*pprev = tmp;
-		pprev = &tmp->vm_next;
-		tmp->vm_prev = prev;
-		prev = tmp;
-
 		/* Link the vma into the MT */
 		mas.index = tmp->vm_start;
 		mas.last = tmp->vm_end - 1;
@@ -1008,7 +996,6 @@ static void mm_init_uprobes_state(struct mm_struct *mm)
 static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 	struct user_namespace *user_ns)
 {
-	mm->mmap = NULL;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
mm/debug.c +6 -6
index d8ed9d7383267..8dd7a23782480 100644
@@ -203,8 +203,8 @@ void dump_vma(const struct vm_area_struct *vma)
 		"prot %lx anon_vma %px vm_ops %px\n"
 		"pgoff %lx file %px private_data %px\n"
 		"flags: %#lx(%pGv)\n",
-		vma, (void *)vma->vm_start, (void *)vma->vm_end, vma->vm_next,
-		vma->vm_prev, vma->vm_mm,
+		vma, (void *)vma->vm_start, (void *)vma->vm_end,
+		vma_next(vma->vm_mm, vma), vma_prev(vma->vm_mm, vma), vma->vm_mm,
 		(unsigned long)pgprot_val(vma->vm_page_prot),
 		vma->anon_vma, vma->vm_ops, vma->vm_pgoff,
 		vma->vm_file, vma->vm_private_data,
@@ -214,11 +214,11 @@ EXPORT_SYMBOL(dump_vma);
 
 void dump_mm(const struct mm_struct *mm)
 {
-	pr_emerg("mm %px mmap %px task_size %lu\n"
+	pr_emerg("mm %px task_size %lu\n"
 #ifdef CONFIG_MMU
 		"get_unmapped_area %px\n"
 #endif
-		"mmap_base %lu mmap_legacy_base %lu highest_vm_end %lu\n"
+		"mmap_base %lu mmap_legacy_base %lu\n"
 		"pgd %px mm_users %d mm_count %d pgtables_bytes %lu map_count %d\n"
 		"hiwater_rss %lx hiwater_vm %lx total_vm %lx locked_vm %lx\n"
 		"pinned_vm %llx data_vm %lx exec_vm %lx stack_vm %lx\n"
@@ -242,11 +242,11 @@ void dump_mm(const struct mm_struct *mm)
 		"tlb_flush_pending %d\n"
 		"def_flags: %#lx(%pGv)\n",
 
-		mm, mm->mmap, mm->task_size,
+		mm, mm->task_size,
 #ifdef CONFIG_MMU
 		mm->get_unmapped_area,
 #endif
-		mm->mmap_base, mm->mmap_legacy_base, mm->highest_vm_end,
+		mm->mmap_base, mm->mmap_legacy_base,
 		mm->pgd, atomic_read(&mm->mm_users),
 		atomic_read(&mm->mm_count),
 		mm_pgtables_bytes(mm),
mm/internal.h +2 -2
index c43ccdddb0f6e..aaf382dbee14e 100644
@@ -36,8 +36,8 @@ void page_writeback_init(void);
 
 vm_fault_t do_swap_page(struct vm_fault *vmf);
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long floor, unsigned long ceiling);
+void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
+	struct vm_area_struct *vma, unsigned long floor, unsigned long ceiling);
 
 static inline bool can_madv_lru_vma(struct vm_area_struct *vma)
 {
mm/memory.c +25 -14
index c48f8df6e5026..3217c46fa32b8 100644
@@ -387,13 +387,18 @@ void free_pgd_range(struct mmu_gather *tlb,
 	} while (pgd++, addr = next, addr != end);
 }
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
-		unsigned long floor, unsigned long ceiling)
+void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
+	struct vm_area_struct *vma, unsigned long floor, unsigned long ceiling)
 {
-	while (vma) {
-		struct vm_area_struct *next = vma->vm_next;
+	struct vm_area_struct *next;
+	struct ma_state ma_next = *mas;
+
+	do {
 		unsigned long addr = vma->vm_start;
 
+		next = mas_find(&ma_next, ceiling - 1);
+		BUG_ON(vma->vm_start < floor);
+		BUG_ON(vma->vm_end - 1 > ceiling - 1);
 		/*
 		 * Hide vma from rmap and truncate_pagecache before freeing
 		 * pgtables
@@ -410,16 +415,17 @@ void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
 			 */
 			while (next && next->vm_start <= vma->vm_end + PMD_SIZE
 			       && !is_vm_hugetlb_page(next)) {
-				vma = next;
-				next = vma->vm_next;
+				next = mas_find(&ma_next, ceiling - 1);
+				vma = mas_find(mas, ceiling - 1);
+				BUG_ON(vma->vm_start < floor);
+				BUG_ON(vma->vm_end -1 > ceiling - 1);
 				unlink_anon_vmas(vma);
 				unlink_file_vma(vma);
 			}
 			free_pgd_range(tlb, addr, vma->vm_end,
 				floor, next ? next->vm_start : ceiling);
 		}
-		vma = next;
-	}
+	} while ((vma = mas_find(mas, (ceiling - 1))) != NULL);
 }
 
 int __pte_alloc(struct mm_struct *mm, pmd_t *pmd)
@@ -1493,16 +1499,19 @@ static void unmap_single_vma(struct mmu_gather *tlb,
  * drops the lock and schedules.
  */
 void unmap_vmas(struct mmu_gather *tlb,
-		struct vm_area_struct *vma, unsigned long start_addr,
-		unsigned long end_addr)
+		struct vm_area_struct *vma, struct ma_state *mas,
+		unsigned long start_addr, unsigned long end_addr)
 {
 	struct mmu_notifier_range range;
 
 	mmu_notifier_range_init(&range, MMU_NOTIFY_UNMAP, 0, vma, vma->vm_mm,
 				start_addr, end_addr);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < end_addr; vma = vma->vm_next)
+	do {
+		BUG_ON(vma->vm_start < start_addr);
+		BUG_ON(vma->vm_end > end_addr);
 		unmap_single_vma(tlb, vma, start_addr, end_addr, NULL);
+	} while ((vma = mas_find(mas, end_addr - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 }
 
@@ -1519,6 +1528,7 @@ void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 {
 	struct mmu_notifier_range range;
 	struct mmu_gather tlb;
+	MA_STATE(mas, &vma->vm_mm->mm_mt, start, start);
 
 	lru_add_drain();
 	mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, vma, vma->vm_mm,
@@ -1526,8 +1536,9 @@ void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 	tlb_gather_mmu(&tlb, vma->vm_mm, start, range.end);
 	update_hiwater_rss(vma->vm_mm);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < range.end; vma = vma->vm_next)
+	do {
 		unmap_single_vma(&tlb, vma, start, range.end, NULL);
+	} while ((vma = mas_find(&mas, range.end - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 	tlb_finish_mmu(&tlb, start, range.end);
 }
@@ -4903,8 +4914,8 @@ int __access_remote_vm(struct task_struct *tsk, struct mm_struct *mm,
 			 * Check if this is a VM_IO | VM_PFNMAP VMA, which
 			 * we can access using slightly different code.
 			 */
-			vma = find_vma(mm, addr);
-			if (!vma || vma->vm_start > addr)
+			vma = find_vma_intersection(mm, addr, addr + 1);
+			if (!vma)
 				break;
 			if (vma->vm_ops && vma->vm_ops->access)
 				ret = vma->vm_ops->access(vma, addr, buf,
mm/mmap.c +206 -316

1,150 lines not on this page · raw message

Signature · 1 line
2.28.0
#75 lore raw

PATCH v2 70/70 mm/mmap: Convert __insert_vm_struct to use mas, convert vma_link to use vma_mas_link()

In reply to Liam R. Howlett

Drop unused vma_store()

---
 mm/mmap.c | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)
mm/mmap.c +8 -16
index ce8857b9abd89..b4ed8be4899b8 100644
@@ -514,21 +514,9 @@ static void vma_mas_link(struct mm_struct *mm, struct vm_area_struct *vma,
 
 static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma)
 {
-	struct address_space *mapping = NULL;
+	MA_STATE(mas, &mm->mm_mt, vma->vm_start, vma->vm_end - 1);
 
-	if (vma->vm_file) {
-		mapping = vma->vm_file->f_mapping;
-		i_mmap_lock_write(mapping);
-	}
-
-	vma_mt_store(mm, vma);
-	__vma_link_file(vma);
-
-	if (mapping)
-		i_mmap_unlock_write(mapping);
-
-	mm->map_count++;
-	validate_mm(mm);
+	vma_mas_link(mm, vma, &mas);
 }
 
 /*
@@ -538,9 +526,13 @@ static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma)
 static inline void __insert_vm_struct(struct mm_struct *mm,
 				      struct vm_area_struct *vma)
 {
-	if (find_vma_intersection(mm, vma->vm_start, vma->vm_end))
+	MA_STATE(mas, &mm->mm_mt, vma->vm_start, vma->vm_end - 1);
+
+	if (mas_find(&mas, vma->vm_end - 1))
 		BUG();
-	vma_mt_store(mm, vma);
+
+	mas_set_range(&mas, vma->vm_start, vma->vm_end - 1);
+	vma_mas_store(vma, &mas);
 	mm->map_count++;
 }
 
Signature · 1 line
2.28.0