RFC mm: Introducing the Maple Tree
Subsystems (38)
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 refs213.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 refs216.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
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
@@ -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
@@ -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
PATCH v2 2/70 radix tree test suite: Add support for fallthrough attribute
In reply to Liam R. HowlettAdd 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
@@ -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
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
@@ -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
@@ -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
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
@@ -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
@@ -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
PATCH v2 5/70 Maple Tree: Add new data structure
In reply to Liam R. HowlettThe 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
@@ -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
@@ -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
@@ -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
@@ -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/generated/autoconf.h +1 -0
Lines of this file are not shown. View the raw message.
tools/testing/radix-tree/linux/maple_tree.h new file +3 -0
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/trace/events/maple_tree.h new file +8 -0
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.
PATCH v2 6/70 mm: Start tracking VMAs with maple tree
In reply to Liam R. HowlettStart 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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
@@ -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
PATCH v2 8/70 mm/mmap: Change find_vma() to use the maple tree
In reply to Liam R. HowlettStart 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
@@ -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
Randy Dunlap
reviewerRe: [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.Signed-off-by Liam R. Howlett <[email protected]>--- mm/mmap.c | 29 +++++++++++------------------ 1 file changed, 11 insertions(+), 18 deletions(-)mm/mmap.c +0
-0
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
PATCH v2 9/70 mm/mmap: Change find_vma_prev() to use maple tree
In reply to Liam R. HowlettChange 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
@@ -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
Randy Dunlap
reviewerRe: [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_prevto use the new maple tree data structure.Signed-off-by Liam R. Howlett <[email protected]>--- mm/mmap.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-)mm/mmap.c +0
-0
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
PATCH v2 10/70 mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple tree
In reply to Liam R. HowlettUse 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
@@ -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, ¤t->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, ¤t->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
Randy Dunlap
reviewerRe: [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.
Signed-off-by Liam R. Howlett <[email protected]>--- mm/mmap.c | 249 ++++++------------------------------------------------ 1 file changed, 27 insertions(+), 222 deletions(-)mm/mmap.c +9
-0@@ -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 thelow_limitand thehigh_limitwith
s/unmapped_area/unmapped_area_topdown/
Quoted 10 lines
+ * the correct alignment and offset at the highest available address, all from
+ * @info. Note:current->mmis 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 longunmapped_area_topdown(struct vm_unmapped_area_info *info){
thanks.
Signature · 1 line
~Randy
PATCH v2 11/70 kernel/fork: Convert dup_mmap to use maple tree
In reply to Liam R. HowlettUse 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
@@ -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
@@ -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
PATCH v2 12/70 mm: Remove rb tree.
In reply to Liam R. HowlettRemove 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
PATCH v2 13/70 mm/gup: Add mm_populate_vma() for use when the vma is known
In reply to Liam R. HowlettWhen 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
@@ -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
@@ -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
PATCH v2 14/70 mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap()
In reply to Liam R. HowlettAvoid 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
@@ -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
Randy Dunlap
reviewerRe: [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.
Signed-off-by Liam R. Howlett <[email protected]>--- mm/mmap.c | 299 +++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 237 insertions(+), 62 deletions(-)mm/mmap.c +0
-0
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
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.
Signed-off-by Liam R. Howlett <[email protected]>--- mm/mmap.c | 299 +++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 237 insertions(+), 62 deletions(-)mm/mmap.c +0
-0@@ -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
PATCH v2 15/70 mm/mmap: Change vm_brk_flags() to use mm_populate_vma()
In reply to Liam R. HowlettSkip 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
@@ -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
PATCH v2 16/70 mm: Move find_vma_intersection to mmap.c and change implementation to maple tree.
In reply to Liam R. HowlettWhen 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
@@ -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
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
@@ -3566,6 +3566,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwriteif (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
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
@@ -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
PATCH v2 19/70 mm: Remove vmacache
In reply to Liam R. HowlettThe 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
PATCH v2 20/70 mm/mmap: Change __do_munmap() to avoid unnecessary lookups.
In reply to Liam R. HowlettAs 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
@@ -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
PATCH v2 21/70 mm/mmap: Move mmap_region() below do_munmap()
In reply to Liam R. HowlettRelocation 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
@@ -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
PATCH v2 22/70 mm/mmap: Add do_mas_munmap() and wraper for __do_munmap()
In reply to Liam R. HowlettTo 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
@@ -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
PATCH v2 23/70 mmap: Use find_vma_intersection in do_mmap() for overlap
In reply to Liam R. HowlettWhen 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
@@ -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
PATCH v2 24/70 mmap: Remove __do_munmap() in favour of do_mas_munmap()
In reply to Liam R. HowlettExport 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
@@ -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
@@ -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
@@ -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
PATCH v2 25/70 mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()
In reply to Liam R. Howlettdo_brk_munmap() already has aligned addresses.
--- mm/mmap.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
mm/mmap.c +3 -2
@@ -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
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
@@ -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
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
@@ -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 lonextern 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
PATCH v2 28/70 arch/arm64: Remove mmap linked list from vdso.
In reply to Liam R. HowlettStart using the maple tree
--- arch/arm64/kernel/vdso.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)
arch/arm64/kernel/vdso.c +4 -1
@@ -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
PATCH v2 29/70 arch/parsic: Remove mmap linked list from kernel/cache
In reply to Liam R. HowlettStart using the maple tree
--- arch/parisc/kernel/cache.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
arch/parisc/kernel/cache.c +5 -3
@@ -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
PATCH v2 30/70 arch/powerpc: Remove mmap linked list from mm/book2s32/tlb
In reply to Liam R. HowlettStart 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
@@ -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
PATCH v2 31/70 arch/powerpc: Remove mmap linked list from mm/book2s32/subpage_prot
In reply to Liam R. HowlettStart 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
@@ -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
PATCH v2 32/70 arch/powerpc: Optimize cell spu task sync.
In reply to Liam R. HowlettUse 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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
PATCH v2 38/70 drivers/oprofile: Lookup address in tree instead of linked list.
In reply to Liam R. HowlettUse 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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
PATCH v2 44/70 fs/proc/task_mmu: Stop using linked list and highest_vm_end
In reply to Liam R. HowlettRemove 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
@@ -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
PATCH v2 45/70 fs/userfaultfd: Stop using vma linked list.
In reply to Liam R. HowlettDon'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
@@ -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
PATCH v2 46/70 ipc/shm: Stop using the vma linked list
In reply to Liam R. HowlettWhen 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
@@ -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
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
@@ -537,16 +537,14 @@ void acct_collect(long exitcode, int group_dead)struct pacct_struct *pacct = ¤t->signal->pacct;u64 utime, stime;unsigned long vsize =0 ; +MA_STATE (mas, ¤t->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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -1151,7 +1151,7 @@ int do_madvise(struct mm_struct *mm, unsigned long start, size_t len_in, int behif (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
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
@@ -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
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
@@ -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, ¤t->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
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
@@ -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, ¤t->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, ¤t->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
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
@@ -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, ¤t->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
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
@@ -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
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
@@ -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
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
@@ -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 listreturn -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
PATCH v2 69/70 mm: Remove vma linked list.
In reply to Liam R. HowlettThe 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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. HowlettDrop unused vma_store()
--- mm/mmap.c | 24 ++++++++---------------- 1 file changed, 8 insertions(+), 16 deletions(-)
mm/mmap.c +8 -16
@@ -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