Changes in .gitignore

74579d8d - tools: separate out shared radix-tree components

Mon, 29 Jul 2024 11:50:40 +0000

tools: separate out shared radix-tree componentsThe core components contained within the radix-tree tests which provideshims for kernel headers and access to the maple tree are useful fortesting other things, so separate them out and make the radix tree testsdependent on the shared components.This lays the groundwork for us to add VMA tests of the newly introducedvma.c file.Link: https://lkml.kernel.org/r/1ee720c265808168e0d75608e687607d77c36719.1722251717.git.lorenzo.stoakes@oracle.comSigned-off-by: Lorenzo Stoakes Acked-by: Vlastimil Babka Reviewed-by: Liam R. Howlett Cc: Alexander Viro Cc: Brendan Higgins Cc: Christian Brauner Cc: David Gow Cc: Eric W. Biederman Cc: Jan Kara Cc: Kees Cook Cc: Matthew Wilcox (Oracle) Cc: Rae Moar Cc: SeongJae Park Cc: Shuah Khan Cc: Suren Baghdasaryan Cc: Pengfei Xu Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

120b1162 - maple_tree: reorganize testing to restore module testing

Fri, 28 Oct 2022 18:04:30 +0000

maple_tree: reorganize testing to restore module testingAlong the development cycle, the testing code support for module/in-kernelcompiles was removed. Restore this functionality by moving any internalAPI tests to the userspace side, as well as threading tests. Fix thelockdep issues and add a way to reduce memory usage so the tests cancomplete with KASAN + memleak detection. Make the tests work on 32 bithosts where possible and detect 32 bit hosts in the radix test suite.[akpm@linux-foundation.org: fix module export][akpm@linux-foundation.org: fix it some more][liam.howlett@oracle.com: fix compile warnings on 32bit build in check_find()] Link: https://lkml.kernel.org/r/20221107203816.1260327-1-Liam.Howlett@oracle.comLink: https://lkml.kernel.org/r/20221028180415.3074673-1-Liam.Howlett@oracle.comSigned-off-by: Liam R. Howlett Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

54a611b6 - Maple Tree: add new data structure

Tue, 06 Sep 2022 19:48:39 +0000

Maple Tree: add new data structurePatch series "Introducing the Maple Tree"The maple tree is an RCU-safe range based B-tree designed to use modernprocessor cache efficiently. There are a number of places in the kernelthat a non-overlapping range-based tree would be beneficial, especiallyone with a simple interface. If you use an rbtree with other datastructures to improve performance or an interval tree to tracknon-overlapping ranges, then this is for you.The tree has a branching factor of 10 for non-leaf nodes and 16 for leafnodes. With the increased branching factor, it is significantly shorterthan the rbtree so it has fewer cache misses. The removal of the linkedlist between subsequent entries also reduces the cache misses and the needto pull in the previous and next VMA during many tree alterations.The first user that is covered in this patch set is the vm_area_struct,where three data structures are replaced by the maple tree: the augmentedrbtree, the vma cache, and the linked list of VMAs in the mm_struct. Thelong term goal is to reduce or remove the mmap_lock contention.The plan is to get to the point where we use the maple tree in RCU mode.Readers will not block for writers. A single write operation will beallowed at a time. A reader re-walks if stale data is encountered. VMAswould be RCU enabled and this mode would be entered once multiple tasksare using the mm_struct.Davidlor said: Yes I like the maple tree, and at this stage I don't think we can ask for: more from this series wrt the MM - albeit there seems to still be some: folks reporting breakage. Fundamentally I see Liam's work to (re)move: complexity out of the MM (not to say that the actual maple tree is not: complex) by consolidating the three complimentary data structures very: much worth it considering performance does not take a hit. This was very: much a turn off with the range locking approach, which worst case scenario: incurred in prohibitive overhead. Also as Liam and Matthew have: mentioned, RCU opens up a lot of nice performance opportunities, and in: addition academia[1] has shown outstanding scalability of address spaces: with the foundation of replacing the locked rbtree with RCU aware trees.A similar work has been discovered in the academic press https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdfSheer coincidence. We designed our tree with the intention of solving thehardest problem first. Upon settling on a b-tree variant and a roughoutline, we researched ranged based b-trees and RCU b-trees and did findthat article. So it was nice to find reassurances that we were on theright path, but our design choice of using ranges made that paper unusablefor us.This patch (of 70):The maple tree is an RCU-safe range based B-tree designed to use modernprocessor cache efficiently. There are a number of places in the kernelthat a non-overlapping range-based tree would be beneficial, especiallyone with a simple interface. If you use an rbtree with other datastructures to improve performance or an interval tree to tracknon-overlapping ranges, then this is for you.The tree has a branching factor of 10 for non-leaf nodes and 16 for leafnodes. With the increased branching factor, it is significantly shorterthan the rbtree so it has fewer cache misses. The removal of the linkedlist between subsequent entries also reduces the cache misses and the needto pull in the previous and next VMA during many tree alterations.The first user that is covered in this patch set is the vm_area_struct,where three data structures are replaced by the maple tree: the augmentedrbtree, the vma cache, and the linked list of VMAs in the mm_struct. Thelong term goal is to reduce or remove the mmap_lock contention.The plan is to get to the point where we use the maple tree in RCU mode.Readers will not block for writers. A single write operation will beallowed at a time. A reader re-walks if stale data is encountered. VMAswould be RCU enabled and this mode would be entered once multiple tasksare using the mm_struct.There is additional BUG_ON() calls added within the tree, most of whichare in debug code. These will be replaced with a WARN_ON() call in thefuture. There is also additional BUG_ON() calls within the code whichwill also be reduced in number at a later date. These exist to catchthings such as out-of-range accesses which would crash anyways.Link: https://lkml.kernel.org/r/20220906194824.2110408-1-Liam.Howlett@oracle.comLink: https://lkml.kernel.org/r/20220906194824.2110408-2-Liam.Howlett@oracle.comSigned-off-by: Liam R. Howlett Signed-off-by: Matthew Wilcox (Oracle) Tested-by: David Howells Tested-by: Sven Schnelle Tested-by: Yu Zhao Cc: Vlastimil Babka Cc: David Hildenbrand Cc: Davidlohr Bueso Cc: Catalin Marinas Cc: SeongJae Park Cc: Will Deacon Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

d198b34f - .gitignore: add SPDX License Identifier

Tue, 03 Mar 2020 13:35:59 +0000

.gitignore: add SPDX License IdentifierAdd SPDX License Identifier to all .gitignore files.Signed-off-by: Masahiro Yamada Signed-off-by: Greg Kroah-Hartman List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

ad3d6c72 - xarray: Add XArray load operation

Tue, 07 Nov 2017 19:57:46 +0000

xarray: Add XArray load operationThe xa_load function brings with it a lot of infrastructure; xa_empty(),xa_is_err(), and large chunks of the XArray advanced API that are usedto implement xa_load.As the test-suite demonstrates, it is possible to use the XArray functionson a radix tree. The radix tree functions depend on the GFP flags beingstored in the root of the tree, so it's not possible to use the radixtree functions on an XArray.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

c6ce3e2f - radix tree test suite: Add config option for map shift

Mon, 13 Feb 2017 21:16:03 +0000

radix tree test suite: Add config option for map shiftAdd config option "SHIFT=" to Makefile for building test suitewith any value of RADIX_TREE_MAP_SHIFT between 3 and 7 inclusive.Signed-off-by: Rehas Sachdeva [mawilcox@microsoft.com: .gitignore, quieten grep, remove on clean]Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

8ac04868 - radix tree test suite: Build separate binaries for some tests

Mon, 19 Dec 2016 03:56:05 +0000

radix tree test suite: Build separate binaries for some testsTo allow developers to run a subset of tests, build separate multiorderand idr-test binaries which will run just the tests in those files.Signed-off-by: Matthew Wilcox Reviewed-by: Rehas Sachdeva List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

0a835c4f - Reimplement IDR and IDA using the radix tree

Tue, 20 Dec 2016 15:27:56 +0000

Reimplement IDR and IDA using the radix treeThe IDR is very similar to the radix tree. It has some functionality thatthe radix tree did not have (alloc next free, cyclic allocation, acallback-based for_each, destroy tree), which is readily implementable ontop of the radix tree. A few small changes were needed in order to use atag to represent nodes with free space below them. More extensivechanges were needed to support storing NULL as a valid entry in an IDR.Plain radix trees still interpret NULL as a not-present entry.The IDA is reimplemented as a client of the newly enhanced radix tree. Asin the current implementation, it uses a bitmap at the last level of thetree.Signed-off-by: Matthew Wilcox Signed-off-by: Matthew Wilcox Tested-by: Kirill A. Shutemov Cc: Konstantin Khlebnikov Cc: Ross Zwisler Cc: Tejun Heo Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/.gitignore

1366c37e - radix tree test harness

Thu, 17 Mar 2016 21:21:45 +0000

radix tree test harnessThis code is mostly from Andrew Morton and Nick Piggin; tarball downloadedfrom http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bdSome small modifications were necessary to the test harness to fix thebuild with the current Linux source code.I also made minor modifications to automatically test the radix-tree.cand radix-tree.h files that are in the current source tree, as opposedto a copied and slightly modified version. I am sure more could be doneto tidy up the harness, as well as adding more tests.[koct9i@gmail.com: fix compilation]Signed-off-by: Matthew Wilcox Cc: Shuah Khan Cc: Johannes Weiner Cc: Matthew Wilcox Cc: "Kirill A. Shutemov" Cc: Ross Zwisler Cc: Hugh Dickins Signed-off-by: Konstantin Khlebnikov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds List of files: /linux-6.15/tools/testing/radix-tree/.gitignore