]> www.infradead.org Git - users/jedix/linux-maple.git/commit
lib/test_maple_tree: add testing for maple tree
authorLiam R. Howlett <Liam.Howlett@Oracle.com>
Wed, 20 Jul 2022 02:17:45 +0000 (02:17 +0000)
committerLiam R. Howlett <Liam.Howlett@oracle.com>
Tue, 6 Sep 2022 19:44:21 +0000 (15:44 -0400)
commitf556af4842767952eef0272c5dcf9421154d9452
tree86df30c247ebd37abb3597ecebcbe3a7f44fe499
parentade903cbe7199044899cd513c8ae11e78bf7a2ad
lib/test_maple_tree: add testing for maple tree

This is a test suite that uses the radix test infrastructure.  It has been
split into its own commit to allow for easier review of the maple tree
code.

The testing includes:
- Allocation of nodes
- gfp flag allocation checks
- Expansion & contraction of tree
- preallocation checks
- tree navigation by next/prev
- tree navigation by iterators (mas_for_each, etc)
- Number of nodes for a given number of entries
- Generic tree construction tests
- Addition and removal of entries in forward and reverse numerical indexes
- gap searching both forward and reverse
- Combining gaps by overwriting entries in different ways
- splitting right-most node
- splitting left-most node
- overwriting multiple slots
- overwriting across different levels of the tree
- overwriting the middle of a tree
- causing a 3-way split up to the root by overwriting the last slot and
  first slot of different nodes and spanning different levels
- RCU stress testing of the tree with threads
- Duplication of the tree by entry count
- Tests which were generated by fuzzers have been added.
- A large number of tests which come from recording crashing in a VM and
  reconstructing the tree (see check_erase2_set())

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
lib/test_maple_tree.c [new file with mode: 0644]
tools/testing/radix-tree/Makefile