#
175542f5 |
| 14-Dec-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: add radix_tree_join
This new function allows for the replacement of many smaller entries in the radix tree with one larger multiorder entry. From the point of view of an RCU walker, the
radix-tree: add radix_tree_join
This new function allows for the replacement of many smaller entries in the radix tree with one larger multiorder entry. From the point of view of an RCU walker, they may see a mixture of the smaller entries and the large entry during the same walk, but they will never see NULL for an index which was populated before the join.
Link: http://lkml.kernel.org/r/1480369871-5271-58-git-send-email-mawilcox@linuxonhyperv.com Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
268f42de |
| 14-Dec-2016 |
Matthew Wilcox <mawilcox@microsoft.com> |
radix-tree: delete radix_tree_range_tag_if_tagged()
This is an exceptionally complicated function with just one caller (tag_pages_for_writeback). We devote a large portion of the runtime of the tes
radix-tree: delete radix_tree_range_tag_if_tagged()
This is an exceptionally complicated function with just one caller (tag_pages_for_writeback). We devote a large portion of the runtime of the test suite to testing this one function which has one caller. By introducing the new function radix_tree_iter_tag_set(), we can eliminate all of the complexity while keeping the performance. The caller can now use a fairly standard radix_tree_for_each() loop, and it doesn't need to worry about tricksy things like 'start' wrapping.
The test suite continues to spend a large amount of time investigating this function, but now it's testing the underlying primitives such as radix_tree_iter_resume() and the radix_tree_for_each_tagged() iterator which are also used by other parts of the kernel.
Link: http://lkml.kernel.org/r/1480369871-5271-57-git-send-email-mawilcox@linuxonhyperv.com Signed-off-by: Matthew Wilcox <willy@infradead.org> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
148deab2 |
| 14-Dec-2016 |
Matthew Wilcox <mawilcox@microsoft.com> |
radix-tree: improve multiorder iterators
This fixes several interlinked problems with the iterators in the presence of multiorder entries.
1. radix_tree_iter_next() would only advance by one slot,
radix-tree: improve multiorder iterators
This fixes several interlinked problems with the iterators in the presence of multiorder entries.
1. radix_tree_iter_next() would only advance by one slot, which would result in the iterators returning the same entry more than once if there were sibling entries.
2. radix_tree_next_slot() could return an internal pointer instead of a user pointer if a tagged multiorder entry was immediately followed by an entry of lower order.
3. radix_tree_next_slot() expanded to a lot more code than it used to when multiorder support was compiled in. And I wasn't comfortable with entry_to_node() being in a header file.
Fixing radix_tree_iter_next() for the presence of sibling entries necessarily involves examining the contents of the radix tree, so we now need to pass 'slot' to radix_tree_iter_next(), and we need to change the calling convention so it is called *before* dropping the lock which protects the tree. Also rename it to radix_tree_iter_resume(), as some people thought it was necessary to call radix_tree_iter_next() each time around the loop.
radix_tree_next_slot() becomes closer to how it looked before multiorder support was introduced. It only checks to see if the next entry in the chunk is a sibling entry or a pointer to a node; this should be rare enough that handling this case out of line is not a performance impact (and such impact is amortised by the fact that the entry we just processed was a multiorder entry). Also, radix_tree_next_slot() used to force a new chunk lookup for untagged entries, which is more expensive than the out of line sibling entry skipping.
Link: http://lkml.kernel.org/r/1480369871-5271-55-git-send-email-mawilcox@linuxonhyperv.com Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
101d9607 |
| 14-Dec-2016 |
Matthew Wilcox <mawilcox@microsoft.com> |
radix tree test suite: record order in each item
This probably doubles the size of each item allocated by the test suite but it lets us check a few more things, and may be needed for upcoming API ch
radix tree test suite: record order in each item
This probably doubles the size of each item allocated by the test suite but it lets us check a few more things, and may be needed for upcoming API changes that require the caller pass in the order of the entry.
Link: http://lkml.kernel.org/r/1480369871-5271-46-git-send-email-mawilcox@linuxonhyperv.com Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
6d75f366 |
| 12-Dec-2016 |
Johannes Weiner <hannes@cmpxchg.org> |
lib: radix-tree: check accounting of existing slot replacement users
The bug in khugepaged fixed earlier in this series shows that radix tree slot replacement is fragile; and it will become more so
lib: radix-tree: check accounting of existing slot replacement users
The bug in khugepaged fixed earlier in this series shows that radix tree slot replacement is fragile; and it will become more so when not only NULL<->!NULL transitions need to be caught but transitions from and to exceptional entries as well. We need checks.
Re-implement radix_tree_replace_slot() on top of the sanity-checked __radix_tree_replace(). This requires existing callers to also pass the radix tree root, but it'll warn us when somebody replaces slots with contents that need proper accounting (transitions between NULL entries, real entries, exceptional entries) and where a replacement through the slot pointer would corrupt the radix tree node counts.
Link: http://lkml.kernel.org/r/20161117193021.GB23430@cmpxchg.org Signed-off-by: Johannes Weiner <hannes@cmpxchg.org> Suggested-by: Jan Kara <jack@suse.cz> Reviewed-by: Jan Kara <jack@suse.cz> Cc: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Hugh Dickins <hughd@google.com> Cc: Matthew Wilcox <mawilcox@linuxonhyperv.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
Revision tags: v4.9, openbmc-4.4-20161121-1, v4.4.33, v4.4.32, v4.4.31, v4.4.30, v4.4.29, v4.4.28, v4.4.27, v4.7.10, openbmc-4.4-20161021-1, v4.7.9, v4.4.26, v4.7.8, v4.4.25, v4.4.24, v4.7.7, v4.8, v4.4.23, v4.7.6, v4.7.5, v4.4.22 |
|
#
62fd5258 |
| 22-Sep-2016 |
Matthew Wilcox <mawilcox@microsoft.com> |
radix tree test suite: Test radix_tree_replace_slot() for multiorder entries
When we replace a multiorder entry, check that all indices reflect the new value.
Also, compile the test suite with -O2,
radix tree test suite: Test radix_tree_replace_slot() for multiorder entries
When we replace a multiorder entry, check that all indices reflect the new value.
Also, compile the test suite with -O2, which shows other problems with the code due to some dodgy pointer operations in the radix tree code.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
Revision tags: v4.4.21, v4.7.4, v4.7.3, v4.4.20, v4.7.2, v4.4.19, openbmc-4.4-20160819-1, v4.7.1, v4.4.18, v4.4.17, openbmc-4.4-20160804-1, v4.4.16, v4.7, openbmc-4.4-20160722-1, openbmc-20160722-1, openbmc-20160713-1, v4.4.15, v4.6.4, v4.6.3, v4.4.14, v4.6.2, v4.4.13, openbmc-20160606-1, v4.6.1, v4.4.12 |
|
#
8c1244de |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: tidy up next_chunk
Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name of the child node. Also use node_maxindex() where it makes sense.
The 'rnode' variable was
radix-tree: tidy up next_chunk
Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name of the child node. Also use node_maxindex() where it makes sense.
The 'rnode' variable was unnecessary; it doesn't overlap in usage with 'node', so we can just use 'node' the whole way through the function.
Improve the testcase to start the walk from every index in the carefully constructed tree, and to accept any index within the range covered by the entry.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
070c5ac2 |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries
I had previously decided that tagging a single multiorder entry would count as tagging 2^order entries for the purposes of 'nr
radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries
I had previously decided that tagging a single multiorder entry would count as tagging 2^order entries for the purposes of 'nr_to_tag'. I now believe that decision to be a mistake, and it should count as a single entry. That's more likely to be what callers expect.
When walking back up the tree from a newly-tagged entry, the current code assumed we were starting from the lowest level of the tree; if we have a multiorder entry with an order at least RADIX_TREE_MAP_SHIFT in size then we need to shift the index by 'shift' before we start walking back up the tree, or we will end up not setting tags on higher entries, and then mistakenly thinking that entries below a certain point in the tree are not tagged.
If the first index we examine is a sibling entry of a tagged multiorder entry, we were not tagging it. We need to examine the canonical entry, and the easiest way to do that is to use radix_tree_descend(). We then have to skip over sibling slots when looking for the next entry in the tree or we will end up walking back to the canonical entry.
Add several tests for radix_tree_range_tag_if_tagged().
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
8a14f4d8 |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: fix radix_tree_create for sibling entries
If the radix tree user attempted to insert a colliding entry with an existing multiorder entry, then radix_tree_create() could encounter a sibli
radix-tree: fix radix_tree_create for sibling entries
If the radix tree user attempted to insert a colliding entry with an existing multiorder entry, then radix_tree_create() could encounter a sibling entry when walking down the tree to look for a slot. Use radix_tree_descend() to fix the problem, and add a test-case to make sure the problem doesn't come back in future.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
0fc9b8ca |
| 20-May-2016 |
Ross Zwisler <ross.zwisler@linux.intel.com> |
radix-tree test suite: add multi-order tag test
Add a generic test for multi-order tag verification, and call it using several different configurations.
This test creates a multi-order radix tree u
radix-tree test suite: add multi-order tag test
Add a generic test for multi-order tag verification, and call it using several different configurations.
This test creates a multi-order radix tree using the given index and order, and then sets, checks and clears tags using the indices covered by the single multi-order radix tree entry.
With the various calls done by this test we verify root multi-order entries without siblings, multi-order entries without siblings in a radix tree node, as well as multi-order entries with siblings of various sizes.
Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
643b57d0 |
| 20-May-2016 |
Ross Zwisler <ross.zwisler@linux.intel.com> |
radix tree test suite: multi-order iteration test
Add a unit test to verify that we can iterate over multi-order entries properly via a radix_tree_for_each_slot() loop.
This was done with a single,
radix tree test suite: multi-order iteration test
Add a unit test to verify that we can iterate over multi-order entries properly via a radix_tree_for_each_slot() loop.
This was done with a single, somewhat complicated configuration that was meant to test many of the various corner cases having to do with multi-order entries:
- An iteration could begin at a sibling entry, and we need to return the canonical entry. - We could have entries of various orders in the same slots[] array. - We could have multi-order entries at a nonzero height, followed by indirect pointers to more radix tree nodes later in that same slots[] array.
Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
7b60e9ad |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: fix multiorder BUG_ON in radix_tree_insert
These BUG_ON tests are to ensure that all the tags are clear when inserting a new entry. If we insert a multiorder entry, we'll end up looking
radix-tree: fix multiorder BUG_ON in radix_tree_insert
These BUG_ON tests are to ensure that all the tags are clear when inserting a new entry. If we insert a multiorder entry, we'll end up looking at the tags for a different node, and so the BUG_ON can end up triggering spuriously.
Also, we now have three tags, not two, so check all three are clear, and check all the root tags with a single call to BUG_ON since the bits are stored contiguously.
Include a test-case to ensure this problem does not reoccur.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
afe0e395 |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix-tree: fix several shrinking bugs with multiorder entries
Setting the indirect bit on the user data entry used to be unambiguous because the tree walking code knew not to expect internal nodes
radix-tree: fix several shrinking bugs with multiorder entries
Setting the indirect bit on the user data entry used to be unambiguous because the tree walking code knew not to expect internal nodes in the last level of the tree. Multiorder entries can appear at any level of the tree, and a leaf with the indirect bit set is indistinguishable from a pointer to a node.
Introduce a special entry (RADIX_TREE_RETRY) which is neither a valid user entry, nor a valid pointer to a node. The radix_tree_deref_retry() function continues to work the same way, but tree walking code can distinguish it from a pointer to a node.
Also fix the condition for setting slot->parent to NULL; it does not matter what height the tree is, it only matters whether slot is an indirect pointer. Move this code above the comment which is referring to the assignment to root->rnode.
Also fix the condition for preventing the tree from shrinking to a single entry if it's a multiorder entry.
Add a test-case to the test suite that checks that the tree goes back down to its original height after an item is inserted & deleted from a higher index in the tree.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
4f3755d1 |
| 20-May-2016 |
Matthew Wilcox <willy@linux.intel.com> |
radix tree test suite: start adding multiorder tests
Test suite infrastructure for working with multiorder entries.
The test itself is pretty basic: Add an entry, check that all expected indices re
radix tree test suite: start adding multiorder tests
Test suite infrastructure for working with multiorder entries.
The test itself is pretty basic: Add an entry, check that all expected indices return that entry and that indices around that entry don't return an entry. Then delete the entry and check no index returns that entry. Tests a few edge conditions including the multiorder entry at index 0 and at a higher index. Also tests deleting through an alias as well as through the canonical index.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
edd822b6 |
| 31-Mar-2021 |
Matthew Wilcox (Oracle) <willy@infradead.org> |
radix tree test suite: Register the main thread with the RCU library [ Upstream commit 1bb4bd266cf39fd2fa711f2d265c558b92df1119 ] Several test runners register individual worker thr
radix tree test suite: Register the main thread with the RCU library [ Upstream commit 1bb4bd266cf39fd2fa711f2d265c558b92df1119 ] Several test runners register individual worker threads with the RCU library, but neglect to register the main thread, which can lead to objects being freed while the main thread is in what appears to be an RCU critical section. Reported-by: Chris von Recklinghausen <crecklin@redhat.com> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org> Signed-off-by: Sasha Levin <sashal@kernel.org>
show more ...
|
Revision tags: v5.10.27, v5.10.26, v5.10.25, v5.10.24, v5.10.23, v5.10.22, v5.10.21, v5.10.20, v5.10.19, v5.4.101, v5.10.18, v5.10.17, v5.11, v5.10.16, v5.10.15, v5.10.14, v5.10, v5.8.17, v5.8.16, v5.8.15, v5.9, v5.8.14, v5.8.13, v5.8.12, v5.8.11, v5.8.10, v5.8.9, v5.8.8, v5.8.7, v5.8.6, v5.4.62, v5.8.5, v5.8.4, v5.4.61, v5.8.3, v5.4.60, v5.8.2, v5.4.59, v5.8.1, v5.4.58, v5.4.57, v5.4.56, v5.8, v5.7.12, v5.4.55, v5.7.11, v5.4.54, v5.7.10, v5.4.53, v5.4.52, v5.7.9, v5.7.8, v5.4.51, v5.4.50, v5.7.7, v5.4.49, v5.7.6, v5.7.5, v5.4.48, v5.7.4, v5.7.3, v5.4.47, v5.4.46, v5.7.2, v5.4.45, v5.7.1, v5.4.44, v5.7, v5.4.43, v5.4.42, v5.4.41, v5.4.40, v5.4.39, v5.4.38, v5.4.37, v5.4.36, v5.4.35, v5.4.34, v5.4.33, v5.4.32, v5.4.31, v5.4.30, v5.4.29, v5.6, v5.4.28, v5.4.27, v5.4.26, v5.4.25, v5.4.24, v5.4.23, v5.4.22, v5.4.21, v5.4.20, v5.4.19, v5.4.18, v5.4.17, v5.4.16, v5.5, v5.4.15, v5.4.14, v5.4.13, v5.4.12, v5.4.11, v5.4.10, v5.4.9, v5.4.8, v5.4.7, v5.4.6, v5.4.5, v5.4.4, v5.4.3, v5.3.15, v5.4.2, v5.4.1, v5.3.14, v5.4, v5.3.13, v5.3.12, v5.3.11, v5.3.10, v5.3.9, v5.3.8, v5.3.7, v5.3.6, v5.3.5, v5.3.4, v5.3.3, v5.3.2, v5.3.1, v5.3, v5.2.14, v5.3-rc8, v5.2.13, v5.2.12, v5.2.11, v5.2.10, v5.2.9, v5.2.8, v5.2.7, v5.2.6, v5.2.5, v5.2.4, v5.2.3, v5.2.2, v5.2.1, v5.2, v5.1.16, v5.1.15, v5.1.14, v5.1.13, v5.1.12, v5.1.11, v5.1.10, v5.1.9, v5.1.8, v5.1.7, v5.1.6 |
|
#
2025cf9e |
| 29-May-2019 |
Thomas Gleixner <tglx@linutronix.de> |
treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 288 Based on 1 normalized pattern(s): this program is free software you can redistribute it and or modify it u
treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 288 Based on 1 normalized pattern(s): this program is free software you can redistribute it and or modify it under the terms and conditions of the gnu general public license version 2 as published by the free software foundation this program is distributed in the hope it will be useful but without any warranty without even the implied warranty of merchantability or fitness for a particular purpose see the gnu general public license for more details extracted by the scancode license scanner the SPDX license identifier GPL-2.0-only has been chosen to replace the boilerplate/reference in 263 file(s). Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Reviewed-by: Allison Randal <allison@lohutok.net> Reviewed-by: Alexios Zavras <alexios.zavras@intel.com> Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190529141901.208660670@linutronix.de Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
show more ...
|
Revision tags: v5.1.5, v5.1.4, v5.1.3, v5.1.2, v5.1.1, v5.0.14, v5.1, v5.0.13, v5.0.12, v5.0.11, v5.0.10, v5.0.9, v5.0.8, v5.0.7, v5.0.6, v5.0.5, v5.0.4, v5.0.3, v4.19.29, v5.0.2, v4.19.28, v5.0.1, v4.19.27, v5.0, v4.19.26, v4.19.25, v4.19.24, v4.19.23, v4.19.22, v4.19.21, v4.19.20, v4.19.19, v4.19.18, v4.19.17, v4.19.16, v4.19.15, v4.19.14, v4.19.13, v4.19.12, v4.19.11, v4.19.10, v4.19.9, v4.19.8, v4.19.7, v4.19.6, v4.19.5, v4.19.4, v4.18.20, v4.19.3, v4.18.19, v4.19.2, v4.18.18, v4.18.17, v4.19.1, v4.19, v4.18.16, v4.18.15, v4.18.14, v4.18.13, v4.18.12, v4.18.11, v4.18.10 |
|
#
542980aa |
| 22-Sep-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree test: Convert multiorder tests to XArray This is the last remaining user of the multiorder functionality of the radix tree. Test the XArray instead. Signed-off-by: M
radix tree test: Convert multiorder tests to XArray This is the last remaining user of the multiorder functionality of the radix tree. Test the XArray instead. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.18.9 |
|
#
4bb53bdd |
| 12-Sep-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree tests: Move item_insert_order The remaining tests are not suitable for moving in-kernel, so move item_insert_order() into multiorder.c, make it static and make it use the
radix tree tests: Move item_insert_order The remaining tests are not suitable for moving in-kernel, so move item_insert_order() into multiorder.c, make it static and make it use the XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.18.7 |
|
#
4f06d630 |
| 09-Sep-2018 |
Matthew Wilcox <willy@infradead.org> |
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorde
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
93eb07f7 |
| 08-Sep-2018 |
Matthew Wilcox <willy@infradead.org> |
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in t
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.18.6 |
|
#
d6427f81 |
| 28-Aug-2018 |
Matthew Wilcox <willy@infradead.org> |
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.18.5, v4.17.18, v4.18.4 |
|
#
372266ba |
| 18-Aug-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree test suite: Convert tag_tagged_items to XArray The tag_tagged_items() function is supposed to test the page-writeback tagging code. Since that has been converted to the XArra
radix tree test suite: Convert tag_tagged_items to XArray The tag_tagged_items() function is supposed to test the page-writeback tagging code. Since that has been converted to the XArray, there's not much point in testing the radix tree's tagging code. This requires using the pthread mutex embedded in the xarray instead of an external lock, so remove the pthread mutexes which protect xarrays/radix trees. Also remove radix_tree_iter_tag_set() as this was the last user. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.18.3, v4.17.17, v4.18.2, v4.17.16, v4.17.15, v4.18.1, v4.18, v4.17.14, v4.17.13, v4.17.12, v4.17.11, v4.17.10, v4.17.9, v4.17.8, v4.17.7, v4.17.6, v4.17.5, v4.17.4, v4.17.3, v4.17.2, v4.17.1, v4.17 |
|
#
2956c664 |
| 19-May-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree: Remove split/join code radix_tree_split and radix_tree_join were never used upstream. Remove them; if they're needed in future they will be replaced by XArray equivalent
radix tree: Remove split/join code radix_tree_split and radix_tree_join were never used upstream. Remove them; if they're needed in future they will be replaced by XArray equivalents. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
1cf56f9d |
| 09-Apr-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree: Remove radix_tree_update_node_t The only user of this functionality was the workingset code, and it's now been converted to the XArray. Remove __radix_tree_delete_node()
radix tree: Remove radix_tree_update_node_t The only user of this functionality was the workingset code, and it's now been converted to the XArray. Remove __radix_tree_delete_node() entirely as it was also only used by the workingset code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
Revision tags: v4.16, v4.15, v4.13.16, v4.14 |
|
#
01959dfe |
| 09-Nov-2017 |
Matthew Wilcox <willy@infradead.org> |
xarray: Define struct xa_node This is a direct replacement for struct radix_tree_node. A couple of struct members have changed name, so convert those. Use a #define so that radix t
xarray: Define struct xa_node This is a direct replacement for struct radix_tree_node. A couple of struct members have changed name, so convert those. Use a #define so that radix tree users continue to work without change. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
show more ...
|