Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33;
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 00/12] maple_tree: iterator state changes
Date:   Wed,  1 Nov 2023 13:16:17 -0400
Message-Id: <20231101171629.3612299-1-Liam.Howlett@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?1HO99oly4l82y25/MhpWKkyrExbu8bvdbpOx2n7Vw5BoMemZQFyPJud9zNoV?=
 =?us-ascii?Q?w4rCTt0eABjO5CnxEMdYFirOx8ZuAtgUAxdOMN+Cn2tWXR208cCvCYgNjfUN?=
 =?us-ascii?Q?aattmd/nwtqTzQ20U1vxg1+WU0hPsT/JT1Wq+OjQ5/bO8s4Sg4VZNYkUVfr6?=
 =?us-ascii?Q?iqmp3JAUqqeM9I7kVOFGnxqulnujZILOvXZaybvleuOB6ANUWf20Km2vOzWR?=
 =?us-ascii?Q?LUfS7+pSe6flQndasRFvMlt9qYbYPKnKDMblGfWicmDgeCWVve2szXADfRHz?=
 =?us-ascii?Q?WoR74zdnrw+QiACuSfExsga/SVyXRAani9QE7PSC4hyC2deN92qrUc/7S2fe?=
 =?us-ascii?Q?9XCBENkWvXQjsg4EjslKVfEO89rNDqi+wqqQljq+XuwSlPKrC8DM9nSQmSMI?=
 =?us-ascii?Q?uhiQDUgmB5oatYA1NhNkmUz1m3VFfYxfmmEy0NVzAMTz+r3DWsexMxRBqeC/?=
 =?us-ascii?Q?SlRbywJQ7ROfUFy+Xj5ccpuRUYn9Kubv62sxsdvsSdnBr/hQoesnZsPvW+5W?=
 =?us-ascii?Q?g/n9177Bu7VF+LOkcokL7/OFHPb3OFP1qYG587Okfx2jx9bVTy4a4WC03k3Q?=
 =?us-ascii?Q?+t1UdzHgJx8kygfuuYqCtyAqHATaHHV7MsW5okhwN1iNtVosO8EZQ4Xr4XQ2?=
 =?us-ascii?Q?/rGn2Qa9wkvQQulivYo3gI5sz1hHMA+9ofIb0K4/8ZRbqsfA+OYJTCDmUKwX?=
 =?us-ascii?Q?f5Bqya+hTb/fOB3THuaYR2GoYuqK4q/x0rLmarMF/WZPfdxoh1zEMfUFpgjK?=
 =?us-ascii?Q?uD6iB0vaFNEydJAmImCD7EWq3GUdunKJCYUz1khnqMiDj1+/jHwp7o+fkaAE?=
 =?us-ascii?Q?4vkhDyiRWjjkCX1/MYa493z4ZN8zV/L4+BpxgneHqamBjJYfzcfdeEUOK/7U?=
 =?us-ascii?Q?UUklPHhHDpjlGKUd59O1/zO5K8mVuDZBrzVcROpDLuBWfgk3FVN08abGVAI7?=
 =?us-ascii?Q?gh5nXA6Uj3YXvhiXhvl6U61OcFOv1SOmWtHWVlsdG1PqP1UiliRRUBbprpZW?=
 =?us-ascii?Q?2W8xdbkvEZtdSU7jekWUhyFz6x4AxssXvRoRfEm9NpNRoc5nAZKoJbf/gn9v?=
 =?us-ascii?Q?FobDpx/ri7Yj6wogsbo6Nf/PyPwdSiUq7XkujCA9h2umLl05Tj9x3LiuXDg2?=
 =?us-ascii?Q?z6CZjLIoYSowLSjIqhV9k0AQNJMYVaMo9NhmfOXTmPiUt7jh4rTgr759VDUB?=
 =?us-ascii?Q?jQbQfmmgkICd/itnnpa8zYF0LiUCbBJcyig3odbk7xpAI4C9NXd5Am5dn9ly?=
 =?us-ascii?Q?X6nQQlZbboR3fxdVYMEJY33GAhz+iRLntWD/RNGB2zwnBrK9POXk7IinSSXw?=
 =?us-ascii?Q?Vxh4Nf2sly9Ly+tVTJK6NO5nyBIMdHUVcjytnVlJqheinJMeKJ4OCWZbIoqr?=
 =?us-ascii?Q?ibjt5xLhs/uNolIw5Sr+0WtO4uwt2X78KDjBeP5rUu8E/mIY+ckeV4NHiD/z?=
 =?us-ascii?Q?ZN8ZaLGbYt3ka/Q1yxbRy7/UR1YZj9hpFkmnYcCviUKfqQYfarOH2uDBQG1J?=
 =?us-ascii?Q?rWvvElQgonzQD2rFkqYyYHBuuUP4LenrEjWZSfm5QjMrfRCsT0gfEjCJnQJP?=
 =?us-ascii?Q?oTcky+5lezrLpNPdcZu/OzXPqNg/dYn0iCRvI5nk?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: LfmijDtZPcnCrcRv6qnp9MLPHvNzxdwl+vm6TppI4z36wcw+qFo0TD4Pq14wnzSw/VgW4pE8wqQ0VvNbnquKXR2FTmqsazOF1sjBHZ2pa5KKHrYf/YchD7aZ4YoLaZkPnlZGotL2+u2wv1666nIRHGr5aFpcGtgMOyArepfnEPJbAWdXihlW0hD8BOmrds5pwFr2WbTD+xn7SH/ZFzMr25Q3kql7RXOkcV9A1k22X+B+i0A9DqIrVd3oaugD1Ocn68K6mgrk7ye2ARqHoUzTwlUw+oUO3f8NSNUFQa98dRSrb5cMGgk2GOpRwrOsYxcROIPQPU8KLaAvufZyxwE16gCXpGimbyO5B/qlOfMh6H/qiYjT0fcIVG4TQsiVh0u7B9INzSlIlK2fRzPZKWfA0zkzxT9uKgI4BT926T8e0u6B78wKxJVnH/13SLpIVV4WJT1Yuijk2VRMBqaWaTNtP7cnn855QU5OOBCUw1pou7IZjwAnxqgk5rSQ0/xnUSwCIAMLiOETFhWckPbZ9O9e+Jj7wHcI9H/OxLD3u1CkGzNzWd2aU1qdBI8F/PWyUSQHYezlU9r6Z6VApRD9wSl8twfnQQcX+puQitMuOiFfsDIrIzJYALjf0LUpDVqQGrXAeiHI9jkKb2VZJ3QMd+v69OrrCBxXIsTxRzD6iSx7Pig1789ybPynoZ4S7jSj6yg2516Yh4gcq8SkTMcjaby0eoZHJrtQWPf3x3H2kMbhgZ81MR6S91Cc7CE/708oR/RcSVb21DabRpENvv3zkksOg3hzHGkHyzb0rEkdrb1vjFFv/5jcubfOKHamhaN7hH1eZD9RuqhYWPIA/Gfy95lWxtRio8ySOcTUZ0bAesHp0ZCoxRh2IrAYPhzZ2pRRLCCtlgO35neW+afBbnNYUehMVQ==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 687f5c30-173f-47ee-4fdd-08dbdafe4db1
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Nov 2023 17:16:36.4021
 (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: 10fjAsWBJPInZhL0ju1jYDOqYfP8Y7H04Z1jGfNiuC67txBMgNG/p1EwozL0KhsoeRgaNbiSVUa5xgCI2KDDuA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA1PR10MB7684
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.987,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-11-01_15,2023-11-01_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 malwarescore=0 bulkscore=0
 mlxscore=0 adultscore=0 mlxlogscore=635 phishscore=0 suspectscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2310240000
 definitions=main-2311010134
X-Proofpoint-ORIG-GUID: FsvbHEjE-2mil-uds7CBbcMblgvbtHIb
X-Proofpoint-GUID: FsvbHEjE-2mil-uds7CBbcMblgvbtHIb
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Wed, 01 Nov 2023 10:17:05 -0700 (PDT)

Andrew,

These patches have some general cleanup and a change to separate the
maple state status tracking from the maple state node.

The maple state status change allows for walks to continue from previous
places when the status needs to be recorded to make logical sense for
the next call to the maple state.  For instance, it allows for prev/next
to function in a way that better resembles the linked list.  It also
allows switch statements to be used to detect missed states during
compile, and the addition of fast-path "active" state is cleaner as an
enum.

While making the status change, perf showed some very small (one line)
functions that were not inlined even with the inline key word.  Making
these small functions __always_inline is less expensive according to
perf.  As part of that change, some inlines have been dropped from
larger functions.

Perf also showed that the commonly used mas_for_each() iterator was
spending a lot of time finding the end of the node.  This series
introduces caching of the end of the node in the maple state (and
updating it during writes). This caching along with the inline changes
yielded at 23.25% improvement on the BENCH_MAS_FOR_EACH maple tree test
framework benchmark.

I've also included a change to mtree_range_walk and mtree_lookup_walk to
take advantage of Peng's change [1] to the initial pivot setup.

mmtests did not produce any significant gains.

[1] https://lore.kernel.org/all/20230711035444.526-1-zhangpeng.00@bytedance.com/T/#u

Liam R. Howlett (12):
  maple_tree: Remove unnecessary default labels from switch statements
  maple_tree: Make mas_erase() more robust
  maple_tree: Move debug check to __mas_set_range()
  maple_tree: Add end of node tracking to the maple state
  maple_tree: Use cached node end in mas_next()
  maple_tree: Use cached node end in mas_destroy()
  maple_tree: Clean up inlines for some functions
  maple_tree: Separate ma_state node from status.
  maple_tree: Remove mas_searchable()
  maple_tree: Use maple state end for write operations
  maple_tree: Don't find node end in mtree_lookup_walk()
  maple_tree: mtree_range_walk() clean up

 include/linux/maple_tree.h                  | 342 +++++-----
 include/linux/mm_types.h                    |   3 +-
 lib/maple_tree.c                            | 680 +++++++++++---------
 lib/test_maple_tree.c                       | 201 +++---
 mm/internal.h                               |  10 +-
 tools/testing/radix-tree/linux/maple_tree.h |   2 +-
 tools/testing/radix-tree/maple.c            |  27 +-
 7 files changed, 679 insertions(+), 586 deletions(-)

-- 
2.40.1