Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
From:   Liam Howlett <liam.howlett@oracle.com>
To:     "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Yu Zhao <yuzhao@google.com>
Subject: [PATCH v8 00/70] Introducing the Maple Tree
Thread-Topic: [PATCH v8 00/70] Introducing the Maple Tree
Thread-Index: AQHYWX8vSnmCSFccn0+psIQVsVvpYQ==
Date:   Tue, 26 Apr 2022 15:06:19 +0000
Message-ID: <20220426150616.3937571-1-Liam.Howlett@oracle.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?xm4ZkU+3bUhvGgWNaRjuZy7lYak9LY6odDTxbPzfuHTA+OChs5ENrwatH0?=
 =?iso-8859-1?Q?CgJhFMa64k8mFGbb6+Wlln3nQaWsNZQxYAqmBqfdL0ytJsXAV7KsOiZ2bg?=
 =?iso-8859-1?Q?ca/7aN16gcrpsD4XB7dj4spMaUVgvdtr7ylLaot4XErrE42HxYEpVRWYoL?=
 =?iso-8859-1?Q?+E+Eghud/NGie7b+d6PgEqU2aDHv9wOXbfwqCTN597F1GMUKO09vYn2D+E?=
 =?iso-8859-1?Q?jZAnDDAkLI8GXsJTMFFCMa2pPnJSwQ3vW6rRima2ocTdfC+0ZCaSOVsYLu?=
 =?iso-8859-1?Q?sgIqKqZnvCZCHFYhdc1FSbN/j6SFbMasB2NxGp78IREG5z1809F5OvXJS3?=
 =?iso-8859-1?Q?qKPk/rqMDv+4xmm81SUfTeDadZns3S9hbzI+B0nIZ8XnduZwELkGZe/MAK?=
 =?iso-8859-1?Q?tOVo72m13O9rZjnIgxL9BX1TWLYO4+1btPa6YDymzX7aXgkX8QbOzN1/K9?=
 =?iso-8859-1?Q?mnm9I7Pnv7dy1Yh0mVTU7anFyCEQ7UBP/w1Q13Z76RlYNfp0AtfbV5zphW?=
 =?iso-8859-1?Q?Eq6hKLyRk4Ee0D2Nn75lgqIyJq28yBF0ILGh1hfMVRIOAvc6xaJQ5A3hut?=
 =?iso-8859-1?Q?4LQcN1HryhtGySBoHIEypH98uG+l+wcNvtIT8lUt9568fML1/auIZ3bWP2?=
 =?iso-8859-1?Q?ViGlWa/bvTazPx0y+LGvlsXc4fTig2Dirmb9kQ/GwuHw1ATask2DgkK56i?=
 =?iso-8859-1?Q?Mt+JoKWNTxpAdoOGPKPGV2tBpIkXkpzO8TiM7yzrYNmXfu6wi7LSnCIMJy?=
 =?iso-8859-1?Q?x+y8Ks7+TO4DHFiHCRm5NR2Rg3RKc2WrB63yR16H597aJLoC9NjJV30Tls?=
 =?iso-8859-1?Q?mZKFsxWEBPvbCars6US3k+IHEi+OdNNqsoCfE/9QKxBQWw8T/YDrORHwPj?=
 =?iso-8859-1?Q?y8k2/0kUcTJWzgVOzRnk6STLSbnUZejqY592NiM7e7AOuJruTOdhRwl8ky?=
 =?iso-8859-1?Q?qGDRk/BFgWSydOvNPx2xSe5x4qJUSCeR2ubPZmFjRMUpI29QZO0H0a8h61?=
 =?iso-8859-1?Q?HilbbaHcbeYSLvQ24RampoJw+E/cJ5DQgXXrf90o1Pfvbe+MRHI0q3G74X?=
 =?iso-8859-1?Q?8//67N/AbWZ6VYtIRV5tjXqdI1VrucaDBOylF1s8A7YIXekFjnf4AgEDon?=
 =?iso-8859-1?Q?zujeW/vqGNvH6+IMBy0Y1HpQmwrFVcL8dlcGibtNTgEF5MFCqBv0wUeX1c?=
 =?iso-8859-1?Q?HT+J7XR/09B2uJzCj1po1WBwAFZty9QmqVuM3metq0tQFTYLSK03wpDhb1?=
 =?iso-8859-1?Q?JfsdB7XyPn3PeX7Fab80U/CMUadgl+MZ1YUWu161cxWsFq9/Mfe7VHJWsX?=
 =?iso-8859-1?Q?HhEzBkN7Wg2X2gU5PZxRxt8Fow6F4AJCz4se09z459SaWPt3uSaeYFU2cR?=
 =?iso-8859-1?Q?LfyMbLN8+yQi301QUkKIWn6ocj8y8GUGF1R2Ddlr2V062qhnO2/cKjn+yN?=
 =?iso-8859-1?Q?PuYEEf7iopmMe3P8SUI1tg5qUJcLR7ECtEvyfx3ZJ4Sxiv+ACnfSDQZmcW?=
 =?iso-8859-1?Q?jOyIiZYT0bcGghuxXFTOo3ysLxCtACowqiVc9SO6/ygTYXom6rTm/O0DhH?=
 =?iso-8859-1?Q?PgqBxTPgawjsHcsToHpBpzMBVBUFGfm+07luXvZ+JHIEZkBkMxrVFUw2+o?=
 =?iso-8859-1?Q?G+X3N+YJVuqBgisO9xEP8ugtMv8mKyz+J0ALFkkI/dbOf2e/QWERFWAYrP?=
 =?iso-8859-1?Q?rO/pjfWSOzzGDvhCIkjQf73AO8YtTucJsOTVl6bTzuHNifH7ea33zgbjDC?=
 =?iso-8859-1?Q?muaIiugBkKjFgXcv0F2utIhNFnWG0H/jC1zZ/cHol15hJuXOl+SsVT8i9G?=
 =?iso-8859-1?Q?q+lSaRhPXTMWpHS2QtFn0bO2izZiPUo=3D?=
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 70677ae3-090e-4d66-e15d-08da279651ef
X-MS-Exchange-CrossTenant-originalarrivaltime: 26 Apr 2022 15:06:19.8974
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: mDbWfmqGqW3BiltMZl2ZN88L6+U7uWLp25Hur/tTxtaHFhVHJ0FczaBKYHWHfJpM66YZ/8ANOm8aSZAp7AEkTg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR10MB4659
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.486,18.0.858
 definitions=2022-04-26_04:2022-04-26,2022-04-26 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 mlxlogscore=999
 malwarescore=0 mlxscore=0 phishscore=0 bulkscore=0 adultscore=0
 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2202240000 definitions=main-2204260096
X-Proofpoint-GUID: w3Ssqv1aIvwIu0iyVM3apk2tFzB14yho
X-Proofpoint-ORIG-GUID: w3Ssqv1aIvwIu0iyVM3apk2tFzB14yho
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,
	MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE autolearn=no
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Andrew,

Please replace the patches in your mglru-maple branch with this set.  It sh=
ould
be a drop in replacement for my patch range with the fixes into these
patches.  Adding the preallocation to work around the fs-reclaim LOCKDEP
issue caused enough changes to the patches to warrant a respin.

The last patch on the branch is still needed to fix vmscan after mglru
is applied.  ee4b1fc24f30 "mm/vmscan: Use VMA_ITERATOR in
get_next_vma()"


Here is the pretty cover letter you requested last time.

------------------------------------

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, where three data structures are
replaced by the maple tree: the augmented rbtree, the vma cache, and the
linked list of VMAs in the mm_struct.  The long term goal is to reduce
or remove the mmap_sem contention.

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 shorter th=
an
the rbtree so it has fewer cache misses.  The removal of the linked list
between subsequent entries also reduces the cache misses and the need to pu=
ll
in the previous and next VMA during many tree alterations.

This patch set is based on v5.18-rc2

git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220426

v8 changes:
 - Added preallocations before any potential edits to the tree when holding=
 the
i_mmap_lock to avoid fs-reclaim issues on extreme memory pressure.
 - Fixed issue in mempolicy mas_for_each() loop.
 - Moved static definitions inside ifdef for DEBUG_MAPLE
 - Fixed compile warnings reported by build bots
 - Moved mas_dfs_preorder() to testing code
 - Changed __vma_adjust() to record the highest vma in case 6 instead of
finding it twice.
 - Fixed locking issue in exit_mmap()
 - Fixed up from/s-o-b ordering

v7: https://lore.kernel.org/linux-mm/20220404143501.2016403-8-Liam.Howlett@=
oracle.com/
v6: https://lore.kernel.org/linux-mm/20220215143728.3810954-1-Liam.Howlett@=
oracle.com/
v5: https://lore.kernel.org/linux-mm/20220202024137.2516438-1-Liam.Howlett@=
oracle.com/
v4: https://lore.kernel.org/linux-mm/20211201142918.921493-1-Liam.Howlett@o=
racle.com/
v3: https://lore.kernel.org/linux-mm/20211005012959.1110504-1-Liam.Howlett@=
oracle.com/
v2: https://lore.kernel.org/linux-mm/20210817154651.1570984-1-Liam.Howlett@=
oracle.com/
v1: https://lore.kernel.org/linux-mm/20210428153542.2814175-1-Liam.Howlett@=
Oracle.com/


Liam R. Howlett (45):
  radix tree test suite: add pr_err define
  radix tree test suite: add kmem_cache_set_non_kernel()
  radix tree test suite: add allocation counts and size to kmem_cache
  radix tree test suite: add support for slab bulk APIs
  radix tree test suite: add lockdep_is_held to header
  mips: rename mt_init to mips_mt_init
  Maple Tree: add new data structure
  lib/test_maple_tree: add testing for maple tree
  mm: start tracking VMAs with maple tree
  mm/mmap: use the maple tree in find_vma() instead of the rbtree.
  mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree
  mm/mmap: use maple tree for unmapped_area{_topdown}
  kernel/fork: use maple tree for dup_mmap() during forking
  damon: Convert __damon_va_three_regions to use the VMA iterator
  mm: remove rb tree.
  mmap: change zeroing of maple tree in __vma_adjust()
  xen: use vma_lookup() in privcmd_ioctl_mmap()
  mm: optimize find_exact_vma() to use vma_lookup()
  mm/khugepaged: optimize collapse_pte_mapped_thp() by using
    vma_lookup()
  mm/mmap: change do_brk_flags() to expand existing VMA and add
    do_brk_munmap()
  mm: use maple tree operations for find_vma_intersection()
  mm/mmap: use advanced maple tree API for mmap_region()
  mm: remove vmacache
  mm: convert vma_lookup() to use mtree_load()
  mm/mmap: move mmap_region() below do_munmap()
  mm/mmap: reorganize munmap to use maple states
  mm/mmap: change do_brk_munmap() to use do_mas_align_munmap()
  arm64: Change elfcore for_each_mte_vma() to use VMA iterator
  fs/proc/base: use maple tree iterators in place of linked list
  userfaultfd: use maple tree iterator to iterate VMAs
  ipc/shm: use VMA iterator instead of linked list
  bpf: remove VMA linked list
  mm/gup: use maple tree navigation instead of linked list
  mm/madvise: use vma_find() instead of vma linked list
  mm/memcontrol: stop using mm->highest_vm_end
  mm/mempolicy: use vma iterator & maple state instead of vma linked
    list
  mm/mprotect: use maple tree navigation instead of vma linked list
  mm/mremap: use vma_find_intersection() instead of vma linked list
  mm/msync: use vma_find() instead of vma linked list
  mm/oom_kill: use maple tree iterators instead of vma linked list
  mm/swapfile: use vma iterator instead of vma linked list
  riscv: use vma iterator for vdso
  mm: remove the vma linked list
  mm/mmap: drop range_has_overlap() function
  mm/mmap.c: pass in mapping to __vma_link_file()

Matthew Wilcox (Oracle) (25):
  mm: add VMA iterator
  mmap: use the VMA iterator in count_vma_pages_range()
  proc: remove VMA rbtree use from nommu
  arm64: remove mmap linked list from vdso
  parisc: remove mmap linked list from cache handling
  powerpc: remove mmap linked list walks
  s390: remove vma linked list walks
  x86: remove vma linked list walks
  xtensa: remove vma linked list walks
  cxl: remove vma linked list walk
  optee: remove vma linked list walk
  um: remove vma linked list walk
  coredump: remove vma linked list walk
  exec: use VMA iterator instead of linked list
  fs/proc/task_mmu: stop using linked list and highest_vm_end
  acct: use VMA iterator instead of linked list
  perf: use VMA iterator
  sched: use maple tree iterator to walk VMAs
  fork: use VMA iterator
  mm/khugepaged: stop using vma linked list
  mm/ksm: use vma iterators instead of vma linked list
  mm/mlock: use vma iterator and instead of vma linked list
  mm/pagewalk: use vma_find() instead of vma linked list
  i915: use the VMA iterator
  nommu: remove uses of VMA linked list

 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple_tree.rst         |   218 +
 MAINTAINERS                                   |    12 +
 arch/arm64/kernel/elfcore.c                   |    16 +-
 arch/arm64/kernel/vdso.c                      |     3 +-
 arch/mips/kernel/mips-mt.c                    |     4 +-
 arch/parisc/kernel/cache.c                    |     7 +-
 arch/powerpc/kernel/vdso.c                    |     6 +-
 arch/powerpc/mm/book3s32/tlb.c                |    11 +-
 arch/powerpc/mm/book3s64/subpage_prot.c       |    13 +-
 arch/riscv/kernel/vdso.c                      |     3 +-
 arch/s390/kernel/vdso.c                       |     3 +-
 arch/s390/mm/gmap.c                           |     6 +-
 arch/um/kernel/tlb.c                          |    14 +-
 arch/x86/entry/vdso/vma.c                     |     9 +-
 arch/x86/kernel/tboot.c                       |     2 +-
 arch/xtensa/kernel/syscall.c                  |    18 +-
 drivers/firmware/efi/efi.c                    |     2 +-
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c   |    14 +-
 drivers/misc/cxl/fault.c                      |    45 +-
 drivers/tee/optee/call.c                      |    18 +-
 drivers/xen/privcmd.c                         |     2 +-
 fs/coredump.c                                 |    34 +-
 fs/exec.c                                     |    12 +-
 fs/proc/base.c                                |     5 +-
 fs/proc/internal.h                            |     2 +-
 fs/proc/task_mmu.c                            |    74 +-
 fs/proc/task_nommu.c                          |    45 +-
 fs/userfaultfd.c                              |    49 +-
 include/linux/maple_tree.h                    |   685 +
 include/linux/mm.h                            |    74 +-
 include/linux/mm_types.h                      |    43 +-
 include/linux/mm_types_task.h                 |    12 -
 include/linux/sched.h                         |     1 -
 include/linux/userfaultfd_k.h                 |     7 +-
 include/linux/vm_event_item.h                 |     4 -
 include/linux/vmacache.h                      |    28 -
 include/linux/vmstat.h                        |     6 -
 include/trace/events/maple_tree.h             |   123 +
 include/trace/events/mmap.h                   |    71 +
 init/main.c                                   |     2 +
 ipc/shm.c                                     |    21 +-
 kernel/acct.c                                 |    11 +-
 kernel/bpf/task_iter.c                        |    10 +-
 kernel/debug/debug_core.c                     |    12 -
 kernel/events/core.c                          |     3 +-
 kernel/events/uprobes.c                       |     9 +-
 kernel/fork.c                                 |    58 +-
 kernel/sched/fair.c                           |    10 +-
 lib/Kconfig.debug                             |    17 +-
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  6964 +++
 lib/test_maple_tree.c                         | 37854 ++++++++++++++++
 mm/Makefile                                   |     2 +-
 mm/damon/vaddr-test.h                         |    37 +-
 mm/damon/vaddr.c                              |    53 +-
 mm/debug.c                                    |    14 +-
 mm/gup.c                                      |     7 +-
 mm/huge_memory.c                              |     4 +-
 mm/init-mm.c                                  |     4 +-
 mm/internal.h                                 |    42 +-
 mm/khugepaged.c                               |    13 +-
 mm/ksm.c                                      |    18 +-
 mm/madvise.c                                  |     2 +-
 mm/memcontrol.c                               |     6 +-
 mm/memory.c                                   |    33 +-
 mm/mempolicy.c                                |    56 +-
 mm/mlock.c                                    |    34 +-
 mm/mmap.c                                     |  2079 +-
 mm/mprotect.c                                 |     7 +-
 mm/mremap.c                                   |    22 +-
 mm/msync.c                                    |     2 +-
 mm/nommu.c                                    |   135 +-
 mm/oom_kill.c                                 |     3 +-
 mm/pagewalk.c                                 |     2 +-
 mm/swapfile.c                                 |     4 +-
 mm/util.c                                     |    32 -
 mm/vmacache.c                                 |   117 -
 mm/vmstat.c                                   |     4 -
 tools/include/linux/slab.h                    |     4 +
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |     9 +-
 tools/testing/radix-tree/generated/autoconf.h |     1 +
 tools/testing/radix-tree/linux.c              |   160 +-
 tools/testing/radix-tree/linux/kernel.h       |     1 +
 tools/testing/radix-tree/linux/lockdep.h      |     2 +
 tools/testing/radix-tree/linux/maple_tree.h   |     7 +
 tools/testing/radix-tree/maple.c              |    59 +
 .../radix-tree/trace/events/maple_tree.h      |     3 +
 89 files changed, 47833 insertions(+), 1823 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

--=20
2.35.1