Skip to content

Introduce a store type enum for the Maple tree

Sidhartha Kumar linux-mm lkml 4 versions – Applied

Status from this message: [merged mm-stable] maple_tree-make-write-helper-functions-void.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest17 patches 9 repliesApplied 17/17
  2. v316 patches 2 repliesSuperseded
  3. v216 patches 6 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v118 patches10 repliesSuperseded

Patches in v4 All 17 applied

#Subject and filesSizeRepliesApplied
1/17maple_tree: introduce store_type enuminclude/linux/maple_tree.h+14 -00 repliesApplied
2/17maple_tree: introduce mas_wr_prealloc_setup()lib/maple_tree.c+8 -20 repliesApplied
3/17maple_tree: move up mas_wr_store_setup() and mas_wr_prealloc_setup()lib/maple_tree.c+48 -480 repliesApplied
4/17maple_tree: introduce mas_wr_store_type()lib/maple_tree.c tools/testing/radix-tree/maple.c+193 -604 repliesApplied
5/17maple_tree: remove mas_destroy() from mas_nomem()lib/maple_tree.c tools/testing/radix-tree/maple.c+30 -170 repliesApplied
6/17maple_tree: preallocate nodes in mas_erase()lib/maple_tree.c+6 -20 repliesApplied
7/17maple_tree: use mas_store_gfp() in mtree_store_range()lib/maple_tree.c+1 -100 repliesApplied
8/17maple_tree: print store type in mas_dump()lib/maple_tree.c+34 -00 repliesApplied
9/17maple_tree: use store type in mas_wr_store_entry()lib/maple_tree.c+52 -380 repliesApplied
10/17maple_tree: convert mas_insert() to preallocate nodeslib/maple_tree.c+10 -120 repliesApplied
11/17maple_tree: simplify mas_commit_b_node()lib/maple_tree.c+7 -570 repliesApplied
12/17maple_tree: remove mas_wr_modify()lib/maple_tree.c+0 -380 repliesApplied
13/17maple_tree: have mas_store() allocate nodes if neededlib/maple_tree.c+17 -20 repliesApplied
14/17maple_tree: remove node allocations from various write helper functionslib/maple_tree.c+0 -270 repliesApplied
15/17maple_tree: remove repeated sanity checks from write helper functionslib/maple_tree.c+2 -150 repliesApplied
16/17maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()lib/maple_tree.c+13 -55 repliesApplied
17/17maple_tree: make write helper functions voidlib/maple_tree.c+16 -310 repliesApplied

Reviews trailers per patch

10 of 17 patches have a Reviewed-by or Acked-by.

PatchLiam R. Howlett
1/17
2/17
3/17R-b
4/17
5/17R-b
6/17
7/17R-b
8/17R-b
9/17R-b
10/17R-b
11/17
12/17R-b
13/17R-b
14/17R-b
15/17
16/17R-b
17/17

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 00/17] Introduce a store type enum for the Maple tree

v3[1] -> v4:
- move up mas->node = null in mas_start() so mas->node is cleared in all cases.
- don't pass gfp into mas_wr_preallocate().This fixes the libfs error reported in v3[2].
- change condition of node store so more writes can be eligible node stores.
- more cleanup of mas_commit_b_node() as most of the function becomes dead code.
- remove wr_bnode as a store type as it is no longer needed.
- add a patch to change many write helper functions to be void.

================================ OVERVIEW ================================

This series implements two work items[3]: "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,
};

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.

Patches 1-16 implement this store type feature.
Patch 17 is a cleanup patch to change functions that have unused return types to be void.

================================ RESULTS =================================

Phoronix t-test-1 (Seconds < Lower Is Better)

    v6.10-rc6
        Threads: 1
            33.15

        Threads: 2
            10.81

    v6.10-rc6 + this series
            Threads: 1
            32.69

        Threads: 2
            10.45

Stress-ng mmap

                    6.10_base  store_type_v4

Duration User 2744.65 2769.40
Duration System 10862.69 10817.59
Duration Elapsed 1477.58 1478.35

================================ 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/[email protected]/T/#m81044feb66765265f8ca7f21e4b4b3725b18780a
[2]: https://lore.kernel.org/linux-mm/[email protected]/T/#mb36c6526486638e82518c0f37a428fb279c84d8a
[3]: https://lists.infradead.org/pipermail/maple-tree/2023-December/003098.html

Sidhartha Kumar (17):
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: preallocate nodes 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 write helper functions
maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()
maple_tree: make write helper functions void

 include/linux/maple_tree.h       |  14 +
 lib/maple_tree.c                 | 653 ++++++++++++++++---------------
 tools/testing/radix-tree/maple.c |  46 ++-
 3 files changed, 400 insertions(+), 313 deletions(-)
Signature · 1 line
2.46.0