Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v2 00/36] Maple tree mas_{next,prev}_range() and cleanup
Date:   Fri,  5 May 2023 13:41:28 -0400
Message-Id: <20230505174204.2665599-1-Liam.Howlett@oracle.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?L1RuV3RzempRM2l1WGdRNUNZaEJkazZ1bzBTSlFEQTJCQk1hZlJNU1kydGlj?=
 =?utf-8?B?dTd2ci9xTjRmeWRIZjQwWGNWbkc2QlBuUlNVbmszQUwxK1RjZmt2NTY5eVJX?=
 =?utf-8?B?a2FRdmV0QWFpUVlFZ0pqUXNuL1YxRk9nWVNZWERTanlDRGFrWDdscnQ2TVlZ?=
 =?utf-8?B?a2ZPZTAwdzJGbklqbityUVZFQmhZd0ROSFhuZGtjdG5QOVVCNXpOcmI3NTYx?=
 =?utf-8?B?VCsxV2Y5SWFmK2V3MHIxdmlhMzBJNHB0a1FzOVhUMEU2N21oYnBKZm5QNlNX?=
 =?utf-8?B?TjBSbmZ0b0dvMmNDOGYwYllWMmFHSm02NHJMYloyTFBqb28wL2pDQ2pKbFhX?=
 =?utf-8?B?ZXpSRHN4RVRyOGtTMUR0d0RScHo3dnlXSHdrYmNyamxRbnBUaHlXL1RVYVFS?=
 =?utf-8?B?eGJZOHdScmErNTN2di9wUUl2RWNPcnNpYWdaT002em1zdGlQSXA2N1E3a3ZZ?=
 =?utf-8?B?YmptbFFzbnhtUWQ1MDFMa2xiQ2lONUtlalovWTFROHlQdm1OM3UzRzh6ODhZ?=
 =?utf-8?B?WHZreFFEdm53SERHajltNUQxWnRKOW10Tm1EdW9BR2Y0V0EzZnQ1cTlwblVz?=
 =?utf-8?B?a2srYStMNU1DVzBrdHNoZCtTd3djVUNvSmdaYWVMTXdrcmdLaVBPMGNVRHV3?=
 =?utf-8?B?dzc1Q0VPT0ZsYStIUDMzVHgyZ1Ywb3hQR3JUaXdLWFBhU0pPa3Bmem1odk40?=
 =?utf-8?B?M0RJWkI0dG4vaFRwVTh3UURqYkJEbFpUU1hBSUxUWm5LWTNFa2IrNTNseFk2?=
 =?utf-8?B?WlhFL1ZFZjF5a212a1hqM0N2bnFvbURxUytFN01TZGw1eVVSVzR1R3pCVjRM?=
 =?utf-8?B?T1Z4S1pnSUJNZXRLTU0vL1FrV3RFNFZJdlFSSUgzVXpsNHJDb3doWHJzRFdk?=
 =?utf-8?B?ZUpKK0NPUWxZUEExOUVsenZGTjM4MXhCR2V3Wk1keU16VDdsR01ETktMZSty?=
 =?utf-8?B?ZVBBcG5SdjNTalNNOG5WQmhoTEdSZVkwRGxpT0toblJFcjNVRzJNOXZTUS9P?=
 =?utf-8?B?VlBleVlrb2UyQzhmazlaaGVLZHRXYkw0WHVLRTBMZTlzYVJTOHJhS3YrMlNY?=
 =?utf-8?B?dlJoOE9xWUZydnhPZGhseXNBalVIc1VhZmFvOG5Sc1RkN1o1SVpmYWYrOWk1?=
 =?utf-8?B?czA4NkRRaEhsazZlTEFBQ3F0NnZNR3krc3pLRTBNZHBhRzdya2xyRS91Nk1u?=
 =?utf-8?B?UFkvdWF1UkkyNlhVd3RWQkJ2RDlrUlB6VGdnNHJTUndtVFJlMHNuR2J3c0dM?=
 =?utf-8?B?elcwVzVYd3oxYXc2V2x0aGpyNW5IdkV1VWovSkVuZzdCYjRESWZmclhUdzFV?=
 =?utf-8?B?OTZ3MW9NdU5ZR2p0UzN3SlFGME8xMlFmN0FlN0NWVTNWT0xMWkRDc05hckk4?=
 =?utf-8?B?cjV3M0dQNXRyKzk4MklxbFVwbnVXaml5cmV0L2xnakM3MFU3TjNrZG9FSGNE?=
 =?utf-8?B?RnlIS1R2T1VYWlJTTTdySnNJaGRVT0hKSURaODlpdlQ4dDNlQzZKcUx6K1Ay?=
 =?utf-8?B?bEp4dmpxd2pTTjBsL0xxWXY5a1d4empTOWNyMGpqS1hwUXp0QS8ycktZbDJ6?=
 =?utf-8?B?TERwampzTEpXSi9zZzlhdVFRZDNJSERZaExDK3VaZW5NWE9DQWhnWENzcG1Y?=
 =?utf-8?B?c0lvMno0MnNLZWVyVVRKM3c2Y1FZanpnOXhJV2xqQWFHM245cGJERFpNR2FJ?=
 =?utf-8?B?ZzFJb0xOQkJCemdTYitkcUpzYWQyWmdzZTlnRFI2NWF5clFFaFE3MmhOQnNq?=
 =?utf-8?B?NGhYTjVhSE1FNHVwRTI3R2NCbkw3OEhBK3RJQzNBd2ZnN3M1LzY3ckJlci9W?=
 =?utf-8?B?ZWxXbHh6QkU0clpTMnNscWloMkdvbkZHc1hKbE12S2ZoUW5OT3gvMkwxdlFP?=
 =?utf-8?B?RzlpK2tlMWwwRVRaakZHUWJhSE1jblk3OEdsK3k0TDU1a1pMU2w0VnBlOW94?=
 =?utf-8?B?N2dBaWh4RkpkYk5DZ2VmTGhIcWxaYi94ZGZaVmY5aVBISDV2dDhTOXBIOEFp?=
 =?utf-8?B?bmNpVVlXMDBiOGZrb0tZK1Z0UkxZYWlUVWF2UThTWmtnNTFmbm0rWjZqK1Nh?=
 =?utf-8?B?MGZkdEpGM1E2L0dDMTZ1RFJMZkp2eUhQS251RGN1UUpMcUhHYWQxSURXdkVV?=
 =?utf-8?B?NTc1K3FqTHh2YStyZEdKUFhJdjNFSFQwOHNUWnI3eEoydloveFBYTXJET0Fo?=
 =?utf-8?B?UkE9PQ==?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: p9adw264bAxYTVDmvDSHzeIZQYh5KpyCOgNrHh1jSPRVlZKLedSZTh5sTBTo1zAt8OSXJ24cLDI/AV1YR+hLP3Qb2pbOE/bdJkeDfO31kbwYsXzZCIOEvcl2t9m1bJYgTaiHdPn7e+N1Lq5QIuobvNHQbn5J6meRgSzgP7y+SVPiJ207oGCs8dl9cvXp8W8vyTZBJpinedMHzCWfpHxVbUOQxZzqyNzbZwp6plFRF5eCH25LCTxXQQNyVhbWrb6fTWjeBwHRCSg6IjkxbjIGkPO2t3vwZCM3C6ppuUpYXzVx0WNLE6YfQ1PLdMxKUqcq17fM1L+fUdwtxiRCFZe/Isg+BmnbbT+QQxojy5IDjaYwWjJeGmslRRmjlTIFCUEk8/wEpIZmDFfUSnDdf0Z+E8aqKHh54oh3K0FbQCnFYTQhMOp4DRIm7hdsMRm/dPz+cHV+TvrY90yPbNWQLQpC1qq7NmiHIIe0nQAGhOabjzqDKc8JGZrNPwcNc73+KFqG5eSYuZBf9+oljprrbQqZ5SrBKtSETGEhWwrSmqn0m/h3MtXmGqtmoHYJf8S29KgYmeiditj0IGeIa7+ZYNL5YE4yLN/tKkcYzb4FmPajZchNNF1uzqQ5kVmzDtQM51teCNygw1e046TSDVEv+hSNe9vRBBiAvlJ/5jnqAdXbys0Q4M+eh5MU0CkP+jFR+XJF5qgTCPb2SliiskKM1Xevi/BNxLAjmrG+ZkBIDhucTW8KjhExQwv6+kgfdVSy+wnycRESH/ZM1AdqJsnKZz+qb0wMXtIb83XmbvlV9c2h9nCRB/hZgro20QGkGfsayxpJAIdyVtZ+2/lXcdlucYy1PXmCvCbfsXAPT7c72YVPcf79DEYk56BaDDlGayKLONpaxzq9hvXm/7nZFKs7a4W+5Q==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: f54932a6-b5b0-4bf7-9216-08db4d9043b4
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2023 17:43:41.0704
 (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: uu7bIAXmfZoaMoXKgkQ2Y0rN2FElZlTcmnUIK8t60+Sdo6cNT/rPeUkz19dL4J2pS+A/bxO44yNfv7uTESoS5g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR10MB7199
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-05-05_24,2023-05-05_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0
 mlxlogscore=999 spamscore=0 phishscore=0 adultscore=0 mlxscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2303200000 definitions=main-2305050146
X-Proofpoint-GUID: Fhv_hKC60JoK_A29NPVKZBHAEpL45_Ma
X-Proofpoint-ORIG-GUID: Fhv_hKC60JoK_A29NPVKZBHAEpL45_Ma
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE
        autolearn=ham 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

This patch set contains a number of clean ups to the code to make it
more usable (next/prev range), the addition of debug output formatting,
the addition of printing the maple state information in the
WARN_ON/BUG_ON code.

There is also work done here to keep nodes active during iterations to
reduce the necessity of re-walking the tree.

Finally, there is a new interface added to move to the next or previous
range in the tree, even if it is empty.

The organisation of the patches is as follows:

0001-0004 - Small clean ups
0005-0018 - Additional debug options and WARN_ON/BUG_ON changes
0019      - Test module __init and __exit addition
0020-0021 - More functional clean ups
0022-0026 - Changes to keep nodes active
0027-0034 - Add new mas_{prev,next}_range()
0035      - Use new mas_{prev,next}_range() in mmap_region()
0036      - Fix testing code of alloc_rev_range() testcase.

Changes since v1:
 - Changed mas_parent_enum() to mas_parent_type() - Thanks Peng Zhang
 - Fix the test code working without debug. - Thanks kernel test robot
   <lkp@intel.com> 
 - Change vma_iter_store() debug log to one line - Thanks Sergey
   Senozhatsky 
 - Change mas_walk() to return entry instead of mas_root() to avoid
   potential RCU issue. - Thanks Peng Zhang
 - Added fix for testing of mas_empty_area.
 - Added check for underflow to mas_prev_slot() - Thanks Peng Zhang
 - Fixed compile issue in mas_next_slot() interface patch - Thanks
   kernel test robot <lkp@intel.com>
 - Removed extra check in mas_next_node() - Thanks Peng Zhang
 - Added missing T's to commit message in two patchs - Thanks Petr
   Tesařík
 - Fix the change to the do_vmi_align_munmap() function to work with the
   new iterator - Thanks kernel test robot <yujie.liu@intel.com>
 - Fix the testing of mas_{prev,next}_range() undeclared function names
   - Thanks kernel test robot <lkp@intel.com>
 - Fix typo in testing code of mas_{prev,next,walk} - Thanks Peng Zhang


v1: https://lore.kernel.org/linux-mm/20230425140955.3834476-1-Liam.Howlett@oracle.com/ 

Liam R. Howlett (36):
  maple_tree: Fix static analyser cppcheck issue
  maple_tree: Clean up mas_parent_enum() and rename to mas_parent_type()
  maple_tree: Avoid unnecessary ascending
  maple_tree: Clean up mas_dfs_postorder()
  maple_tree: Add format option to mt_dump()
  maple_tree: Add debug BUG_ON and WARN_ON variants
  maple_tree: Convert BUG_ON() to MT_BUG_ON()
  maple_tree: Change RCU checks to WARN_ON() instead of BUG_ON()
  maple_tree: Convert debug code to use MT_WARN_ON() and MAS_WARN_ON()
  maple_tree: Use MAS_BUG_ON() when setting a leaf node as a parent
  maple_tree: Use MAS_BUG_ON() in mas_set_height()
  maple_tree: Use MAS_BUG_ON() from mas_topiary_range()
  maple_tree: Use MAS_WR_BUG_ON() in mas_store_prealloc()
  maple_tree: Use MAS_BUG_ON() prior to calling mas_meta_gap()
  maple_tree: Return error on mte_pivots() out of range
  maple_tree: Make test code work without debug enabled
  mm: Update validate_mm() to use vma iterator
  mm: Update vma_iter_store() to use MAS_WARN_ON()
  maple_tree: Add __init and __exit to test module
  maple_tree: Remove unnecessary check from mas_destroy()
  maple_tree: mas_start() reset depth on dead node
  mm/mmap: Change do_vmi_align_munmap() for maple tree iterator changes
  maple_tree: Try harder to keep active node after mas_next()
  maple_tree: Try harder to keep active node with mas_prev()
  maple_tree: Revise limit checks in mas_empty_area{_rev}()
  maple_tree: Fix testing mas_empty_area()
  maple_tree: Introduce mas_next_slot() interface
  maple_tree: Add mas_next_range() and mas_find_range() interfaces
  maple_tree: Relocate mas_rewalk() and mas_rewalk_if_dead()
  maple_tree: Introduce mas_prev_slot() interface
  maple_tree: Add mas_prev_range() and mas_find_range_rev interface
  maple_tree: Clear up index and last setting in single entry tree
  maple_tree: Update testing code for mas_{next,prev,walk}
  mm: Add vma_iter_{next,prev}_range() to vma iterator
  mm: Avoid rewalk in mmap_region
  maple_tree: Add gap to check_alloc_rev_range() testcase

 include/linux/maple_tree.h            |  129 ++-
 include/linux/mm.h                    |   13 +
 include/linux/mmdebug.h               |   14 +
 lib/Kconfig.debug                     |   10 +-
 lib/maple_tree.c                      | 1175 ++++++++++++++-----------
 lib/test_maple_tree.c                 |  863 +++++++++++++++---
 mm/debug.c                            |    9 +
 mm/internal.h                         |   26 +-
 mm/mmap.c                             |  111 ++-
 tools/testing/radix-tree/linux/init.h |    1 +
 tools/testing/radix-tree/maple.c      |  164 ++--
 11 files changed, 1760 insertions(+), 755 deletions(-)

-- 
2.39.2