diff options
| author |   Ross Zwisler <ross.zwisler@linux.intel.com> | 2016-05-20 17:02:26 -0700 |
|---|---|---|
| committer |   Linus Torvalds <torvalds@linux-foundation.org> | 2016-05-20 17:58:30 -0700 |
| commit | 21ef533931f73a8e963a6107aa5ec51b192f28be (patch) | |
| tree | bc5066db87ca565cbc35e3535e88b1e5ec1beb41 /tools/testing/radix-tree | |
| parent | radix-tree: fix multiorder BUG_ON in radix_tree_insert (diff) | |
| download | linux-dev-21ef533931f73a8e963a6107aa5ec51b192f28be.tar.xz linux-dev-21ef533931f73a8e963a6107aa5ec51b192f28be.zip | |
radix-tree: add support for multi-order iterating
This enables the macros radix_tree_for_each_slot() and friends to be
used with multi-order entries.
The way that this works is that we treat all entries in a given slots[]
array as a single chunk. If the index given to radix_tree_next_chunk()
happens to point us to a sibling entry, we will back up iter->index so
that it points to the canonical entry, and that will be the place where
we start our iteration.
As we're processing a chunk in radix_tree_next_slot(), we process
canonical entries, skip over sibling entries, and restart the chunk
lookup if we find a non-sibling indirect pointer. This drops back to
the radix_tree_next_chunk() code, which will re-walk the tree and look
for another chunk.
This allows us to properly handle multi-order entries mixed with other
entries that are at various heights in the radix tree.
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>
Diffstat (limited to 'tools/testing/radix-tree')
| -rw-r--r-- | tools/testing/radix-tree/generated/autoconf.h | 3 | ||||
| -rw-r--r-- | tools/testing/radix-tree/linux/kernel.h | 5 |
2 files changed, 4 insertions, 4 deletions
diff --git a/tools/testing/radix-tree/generated/autoconf.h b/tools/testing/radix-tree/generated/autoconf.h new file mode 100644 index 000000000000..ad18cf5a2a3a --- /dev/null +++ b/tools/testing/radix-tree/generated/autoconf.h @@ -0,0 +1,3 @@ +#define CONFIG_RADIX_TREE_MULTIORDER 1 +#define CONFIG_SHMEM 1 +#define CONFIG_SWAP 1 diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 8ea0ed450810..be98a47b4e1b 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -8,10 +8,7 @@ #include <limits.h> #include "../../include/linux/compiler.h" - -#define CONFIG_RADIX_TREE_MULTIORDER -#define CONFIG_SHMEM -#define CONFIG_SWAP +#include "../../../include/linux/kconfig.h" #define RADIX_TREE_MAP_SHIFT 3 |