linux-kernel - Re: [PATCH v3 00/16] Introduce a store type enum for the Maple tree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <oaimbp2onjag4u5dida73hu62aqcajf2siqtvdc4mxq6y2dylz@g6ik3a5gquu4>
Date: Mon, 24 Jun 2024 11:43:41 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Sidhartha Kumar <sidhartha.kumar@...cle.com>
Cc: linux-kernel@...r.kernel.org, maple-tree@...ts.infradead.org,
        linux-mm@...ck.org, akpm@...ux-foundation.org, willy@...radead.org
Subject: Re: [PATCH v3 00/16] Introduce a store type enum for the Maple tree


Thanks!

Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>

* Sidhartha Kumar <sidhartha.kumar@...cle.com> [240618 16:48]:
> This series is rebased on top of mm-unstable + the patch:
> maple_tree: modified return type of mas_wr_store_entry()[1]. Andrew could
> you add that patch to mm-unstable before merging this series.
> 
> 
> v2[2] -> v3:
>   - fix new line issues throughout the series
> 
>   - remove use of helper function in patch 13 
> 
> 
> v1[3] -> v2:
>   - previous results were noisy, replaced with stress-ng-mmap config of
>     mmtests
>   
>   - document function parameter 'entry'in 'mas_prealloc_calc per Intel
>     Test Robot
>   
>   - explain why mas_reset() was dropeed in patch 4
> 
>   - add locking and mas_destroy() to testcase in patch 4
>   
>   - squash "set write store type" vs "set store type" into the
>     mas_wr_store_entry() modification
> 
>   - only set ret to xa_err() in the err case in mas_store_gfp()
> 
>   - move MT_BUG_ON() inside lock in patch 7
> 
>   - noinline mas_wr_spanning store to reduce stack usage in
>     mas_wr_store_type() in patch 11 per Intel Test Robot
> 
>   - document function parameter gfp in mas_insert() per Intel
>     test robot.
> 
>   - further simplify the local variables in patch 11
> 
> ================================ OVERVIEW ================================
> 
> This series implements two work items[4]: "aligning mas_store_gfp() with
> mas_preallocate()" and "enum for store type". 
> 
> mas_store_gfp() is modified to preallocate nodes. This simplies many of
> the write helper functions by allowing them to use mas_store_gfp() rather
> than open coding node allocation and error handling.
> 
> The enum defines the following store types:
> 
> enum store_type {
> 	wr_invalid,
> 	wr_new_root,
> 	wr_store_root,
> 	wr_exact_fit,
> 	wr_spanning_store,
> 	wr_split_store,
> 	wr_rebalance,
> 	wr_append,
> 	wr_node_store,
> 	wr_slot_store,
> 	wr_bnode
> };
> 
> In the current maple tree code, a walk down the tree is done in
> mas_preallocate() to determine the number of nodes needed for this write.
> After node allocation, mas_wr_store_entry() will perform another walk to
> determine which write helper function to use to complete the write.
> 
> Rather than performing the second walk, we can store the type of write
> in the maple write state during node allocation and read this field to
> complete the write.
> 
> ================================ RESULTS =================================
> 
>                   v6.10_mmap     v6.10_mmap_store_type
> Duration User           9.80        8.69
> Duration System      2295.94     2243.85
> Duration Elapsed     1010.50     1009.44
> 
> ================================ TESTING =================================
> 
> Testing was done with the maple tree test suite. A new test case is also
> added to validate the order in which we test for and assign the store type.
> 
> [1]: https://lore.kernel.org/linux-mm/20240614092428.29491-1-rgbi3307@gmail.com/T/
> [2]: https://lore.kernel.org/linux-mm/20240607185257.963768-1-sidhartha.kumar@oracle.com/T/#ma3795b93f9d5c9c9286291e12f089bff45b87fed
> [3]: https://lore.kernel.org/linux-mm/20240604174145.563900-1-sidhartha.kumar@oracle.com/
> [4]: https://lists.infradead.org/pipermail/maple-tree/2023-December/003098.html
> 
> 
> Sidhartha Kumar (16):
>   maple_tree: introduce store_type enum
>   maple_tree: introduce mas_wr_prealloc_setup()
>   maple_tree: move up mas_wr_store_setup() and mas_wr_prealloc_setup()
>   maple_tree: introduce mas_wr_store_type()
>   maple_tree: remove mas_destroy() from mas_nomem()
>   maple_tree: use mas_store_gfp() in mas_erase()
>   maple_tree: use mas_store_gfp() in mtree_store_range()
>   maple_tree: print store type in mas_dump()
>   maple_tree: use store type in mas_wr_store_entry()
>   maple_tree: convert mas_insert() to preallocate nodes
>   maple_tree: simplify mas_commit_b_node()
>   maple_tree: remove mas_wr_modify()
>   maple_tree: have mas_store() allocate nodes if needed
>   maple_tree: remove node allocations from various write helper
>     functions
>   maple_tree: remove repeated sanity checks from mas_wr_append()
>   maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()
> 
>  include/linux/maple_tree.h       |  15 +
>  lib/maple_tree.c                 | 580 ++++++++++++++++++-------------
>  tools/testing/radix-tree/maple.c |  46 ++-
>  3 files changed, 396 insertions(+), 245 deletions(-)
> 
> -- 
> 2.45.2
>