From: Matthew Wilcox <mawilcox@linuxonhyperv.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org>, Konstantin Khlebnikov <koct9i@gmail.com>, Ross Zwisler <ross.zwisler@linux.intel.com> Cc: linux-fsdevel@vger.kernel.org, Matthew Wilcox <willy@linux.intel.com>, linux-mm@kvack.org, "Kirill A . Shutemov" <kirill.shutemov@linux.intel.com> Subject: [PATCH 11/29] radix-tree: Add radix_tree_split Date: Wed, 16 Nov 2016 16:16:38 -0800 [thread overview] Message-ID: <1479341856-30320-14-git-send-email-mawilcox@linuxonhyperv.com> (raw) In-Reply-To: <1479341856-30320-1-git-send-email-mawilcox@linuxonhyperv.com> From: Matthew Wilcox <willy@linux.intel.com> This new function splits a larger multiorder entry into smaller entries (potentially multi-order entries). These entries are initialised to RADIX_TREE_RETRY to ensure that RCU walkers who see this state aren't confused. The caller should then call radix_tree_for_each_slot() and radix_tree_replace_slot() in order to turn these retry entries into the intended new entries. Tags are replicated from the original multiorder entry into each new entry. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- include/linux/radix-tree.h | 3 + lib/radix-tree.c | 109 ++++++++++++++++++++++++++++++++-- tools/testing/radix-tree/multiorder.c | 26 ++++++++ 3 files changed, 134 insertions(+), 4 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 1efd81f..f5518f1 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -319,8 +319,11 @@ static inline void radix_tree_preload_end(void) preempt_enable(); } +int radix_tree_split(struct radix_tree_root *, unsigned long index, + unsigned new_order); int radix_tree_join(struct radix_tree_root *, unsigned long index, unsigned new_order, void *); + /** * struct radix_tree_iter - radix tree iterator state * diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6a76252..eaf0f353 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -231,7 +231,10 @@ static void dump_node(struct radix_tree_node *node, unsigned long index) void *entry = node->slots[i]; if (!entry) continue; - if (is_sibling_entry(node, entry)) { + if (entry == RADIX_TREE_RETRY) { + pr_debug("radix retry offset %ld indices %ld-%ld\n", + i, first, last); + } else if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n", entry, i, *(void **)entry_to_node(entry), @@ -641,7 +644,10 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot, unsigned i, n, tag, offset, tags = 0; if (node) { - n = 1 << (order - node->shift); + if (order > node->shift) + n = 1 << (order - node->shift); + else + n = 1; offset = get_slot_offset(node, slot); } else { n = 1; @@ -680,7 +686,8 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot, tag_set(node, tag, offset); } if (radix_tree_is_internal_node(old) && - !is_sibling_entry(node, old)) + !is_sibling_entry(node, old) && + (old != RADIX_TREE_RETRY)) radix_tree_free_nodes(old); } if (node) @@ -843,6 +850,98 @@ int radix_tree_join(struct radix_tree_root *root, unsigned long index, return error; } + +int radix_tree_split(struct radix_tree_root *root, unsigned long index, + unsigned order) +{ + struct radix_tree_node *parent, *node, *child; + void **slot; + unsigned int offset, end; + unsigned n, tag, tags = 0; + + if (!__radix_tree_lookup(root, index, &parent, &slot)) + return -ENOENT; + if (!parent) + return -ENOENT; + + offset = get_slot_offset(parent, slot); + + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tag_get(parent, tag, offset)) + tags |= 1 << tag; + + for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) { + if (!is_sibling_entry(parent, parent->slots[end])) + break; + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(parent, tag, end); + /* rcu_assign_pointer ensures tags are set before RETRY */ + rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY); + } + + if (order == parent->shift) + return 0; + if (order > parent->shift) { + while (offset < end) + offset += insert_entries(parent, &parent->slots[offset], + RADIX_TREE_RETRY, order, true); + return 0; + } + + node = parent; + + for (;;) { + if (node->shift > order) { + child = radix_tree_node_alloc(root); + if (!child) + goto nomem; + child->shift = node->shift - RADIX_TREE_MAP_SHIFT; + child->offset = offset; + child->count = 0; + child->parent = node; + if (node != parent) { + node->count++; + node->slots[offset] = node_to_entry(child); + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(node, tag, offset); + } + + node = child; + offset = 0; + continue; + } + + n = insert_entries(node, &node->slots[offset], + RADIX_TREE_RETRY, order, false); + BUG_ON(n > RADIX_TREE_MAP_SIZE); + + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(node, tag, offset); + offset += n; + + while (offset == RADIX_TREE_MAP_SIZE) { + if (node == parent) + break; + offset = node->offset; + child = node; + node = node->parent; + rcu_assign_pointer(node->slots[offset], + node_to_entry(child)); + offset++; + } + if ((node == parent) && (offset == end)) + return 0; + } + + nomem: + /* Shouldn't happen; did user forget to preload? */ + /* TODO: free all the allocated nodes */ + WARN_ON(1); + return -ENOMEM; +} #endif /** @@ -1081,8 +1180,10 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, child = rcu_dereference_raw(node->slots[offset]); } - if ((child == NULL) || (child == RADIX_TREE_RETRY)) + if (!child) goto restart; + if (child == RADIX_TREE_RETRY) + break; } while (radix_tree_is_internal_node(child)); /* Update the iterator state */ diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index 4c66acc..d9e8155 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -356,6 +356,31 @@ static void multiorder_join(void) } } +static void __multiorder_split(int old_order, int new_order) +{ + RADIX_TREE(tree, GFP_KERNEL); + void **slot; + struct radix_tree_iter iter; + + item_insert_order(&tree, 0, old_order); + radix_tree_tag_set(&tree, 0, 2); + radix_tree_split(&tree, 0, new_order); + radix_tree_for_each_slot(slot, &tree, &iter, 0) { + radix_tree_replace_slot(slot, item_create(iter.index)); + } + + item_kill_tree(&tree); +} + +static void multiorder_split(void) +{ + int i, j; + + for (i = 9; i < 19; i++) + for (j = 0; j < i; j++) + __multiorder_split(i, j); +} + void multiorder_checks(void) { int i; @@ -374,4 +399,5 @@ void multiorder_checks(void) multiorder_iteration(); multiorder_tagged_iteration(); multiorder_join(); + multiorder_split(); } -- 2.10.2
WARNING: multiple messages have this Message-ID (diff)
From: Matthew Wilcox <mawilcox@linuxonhyperv.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org>, Konstantin Khlebnikov <koct9i@gmail.com>, Ross Zwisler <ross.zwisler@linux.intel.com> Cc: linux-fsdevel@vger.kernel.org, Matthew Wilcox <willy@linux.intel.com>, linux-mm@kvack.org, "Kirill A . Shutemov" <kirill.shutemov@linux.intel.com> Subject: [PATCH 11/29] radix-tree: Add radix_tree_split Date: Wed, 16 Nov 2016 16:16:38 -0800 [thread overview] Message-ID: <1479341856-30320-14-git-send-email-mawilcox@linuxonhyperv.com> (raw) In-Reply-To: <1479341856-30320-1-git-send-email-mawilcox@linuxonhyperv.com> From: Matthew Wilcox <willy@linux.intel.com> This new function splits a larger multiorder entry into smaller entries (potentially multi-order entries). These entries are initialised to RADIX_TREE_RETRY to ensure that RCU walkers who see this state aren't confused. The caller should then call radix_tree_for_each_slot() and radix_tree_replace_slot() in order to turn these retry entries into the intended new entries. Tags are replicated from the original multiorder entry into each new entry. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- include/linux/radix-tree.h | 3 + lib/radix-tree.c | 109 ++++++++++++++++++++++++++++++++-- tools/testing/radix-tree/multiorder.c | 26 ++++++++ 3 files changed, 134 insertions(+), 4 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 1efd81f..f5518f1 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -319,8 +319,11 @@ static inline void radix_tree_preload_end(void) preempt_enable(); } +int radix_tree_split(struct radix_tree_root *, unsigned long index, + unsigned new_order); int radix_tree_join(struct radix_tree_root *, unsigned long index, unsigned new_order, void *); + /** * struct radix_tree_iter - radix tree iterator state * diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6a76252..eaf0f353 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -231,7 +231,10 @@ static void dump_node(struct radix_tree_node *node, unsigned long index) void *entry = node->slots[i]; if (!entry) continue; - if (is_sibling_entry(node, entry)) { + if (entry == RADIX_TREE_RETRY) { + pr_debug("radix retry offset %ld indices %ld-%ld\n", + i, first, last); + } else if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n", entry, i, *(void **)entry_to_node(entry), @@ -641,7 +644,10 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot, unsigned i, n, tag, offset, tags = 0; if (node) { - n = 1 << (order - node->shift); + if (order > node->shift) + n = 1 << (order - node->shift); + else + n = 1; offset = get_slot_offset(node, slot); } else { n = 1; @@ -680,7 +686,8 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot, tag_set(node, tag, offset); } if (radix_tree_is_internal_node(old) && - !is_sibling_entry(node, old)) + !is_sibling_entry(node, old) && + (old != RADIX_TREE_RETRY)) radix_tree_free_nodes(old); } if (node) @@ -843,6 +850,98 @@ int radix_tree_join(struct radix_tree_root *root, unsigned long index, return error; } + +int radix_tree_split(struct radix_tree_root *root, unsigned long index, + unsigned order) +{ + struct radix_tree_node *parent, *node, *child; + void **slot; + unsigned int offset, end; + unsigned n, tag, tags = 0; + + if (!__radix_tree_lookup(root, index, &parent, &slot)) + return -ENOENT; + if (!parent) + return -ENOENT; + + offset = get_slot_offset(parent, slot); + + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tag_get(parent, tag, offset)) + tags |= 1 << tag; + + for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) { + if (!is_sibling_entry(parent, parent->slots[end])) + break; + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(parent, tag, end); + /* rcu_assign_pointer ensures tags are set before RETRY */ + rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY); + } + + if (order == parent->shift) + return 0; + if (order > parent->shift) { + while (offset < end) + offset += insert_entries(parent, &parent->slots[offset], + RADIX_TREE_RETRY, order, true); + return 0; + } + + node = parent; + + for (;;) { + if (node->shift > order) { + child = radix_tree_node_alloc(root); + if (!child) + goto nomem; + child->shift = node->shift - RADIX_TREE_MAP_SHIFT; + child->offset = offset; + child->count = 0; + child->parent = node; + if (node != parent) { + node->count++; + node->slots[offset] = node_to_entry(child); + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(node, tag, offset); + } + + node = child; + offset = 0; + continue; + } + + n = insert_entries(node, &node->slots[offset], + RADIX_TREE_RETRY, order, false); + BUG_ON(n > RADIX_TREE_MAP_SIZE); + + for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) + if (tags & (1 << tag)) + tag_set(node, tag, offset); + offset += n; + + while (offset == RADIX_TREE_MAP_SIZE) { + if (node == parent) + break; + offset = node->offset; + child = node; + node = node->parent; + rcu_assign_pointer(node->slots[offset], + node_to_entry(child)); + offset++; + } + if ((node == parent) && (offset == end)) + return 0; + } + + nomem: + /* Shouldn't happen; did user forget to preload? */ + /* TODO: free all the allocated nodes */ + WARN_ON(1); + return -ENOMEM; +} #endif /** @@ -1081,8 +1180,10 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, child = rcu_dereference_raw(node->slots[offset]); } - if ((child == NULL) || (child == RADIX_TREE_RETRY)) + if (!child) goto restart; + if (child == RADIX_TREE_RETRY) + break; } while (radix_tree_is_internal_node(child)); /* Update the iterator state */ diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index 4c66acc..d9e8155 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -356,6 +356,31 @@ static void multiorder_join(void) } } +static void __multiorder_split(int old_order, int new_order) +{ + RADIX_TREE(tree, GFP_KERNEL); + void **slot; + struct radix_tree_iter iter; + + item_insert_order(&tree, 0, old_order); + radix_tree_tag_set(&tree, 0, 2); + radix_tree_split(&tree, 0, new_order); + radix_tree_for_each_slot(slot, &tree, &iter, 0) { + radix_tree_replace_slot(slot, item_create(iter.index)); + } + + item_kill_tree(&tree); +} + +static void multiorder_split(void) +{ + int i, j; + + for (i = 9; i < 19; i++) + for (j = 0; j < i; j++) + __multiorder_split(i, j); +} + void multiorder_checks(void) { int i; @@ -374,4 +399,5 @@ void multiorder_checks(void) multiorder_iteration(); multiorder_tagged_iteration(); multiorder_join(); + multiorder_split(); } -- 2.10.2 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2016-11-16 22:35 UTC|newest] Thread overview: 152+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-11-17 0:16 [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 06/28] Add benchmark Matthew Wilcox 2016-11-17 0:16 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox 2016-11-17 0:16 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox [this message] 2016-11-17 0:16 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox 2016-11-17 0:16 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-18 11:56 ` Konstantin Khlebnikov 2016-11-18 11:56 ` Konstantin Khlebnikov 2016-11-17 0:16 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox 2016-11-17 0:16 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox 2016-11-17 0:16 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox 2016-11-17 0:16 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:16 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox 2016-11-17 0:16 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox 2016-11-17 0:16 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 19:38 ` Matthew Wilcox 2016-11-17 19:38 ` Matthew Wilcox 2016-11-17 22:17 ` Ross Zwisler 2016-11-17 22:17 ` Ross Zwisler 2016-11-18 4:24 ` Matthew Wilcox 2016-11-18 4:24 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 06/28] Add benchmark Matthew Wilcox 2016-11-17 0:17 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox 2016-11-17 0:17 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-18 11:47 ` Konstantin Khlebnikov 2016-11-18 11:47 ` Konstantin Khlebnikov 2016-11-18 16:31 ` Matthew Wilcox 2016-11-18 16:31 ` Matthew Wilcox 2016-11-18 17:56 ` Konstantin Khlebnikov 2016-11-18 17:56 ` Konstantin Khlebnikov 2016-11-18 20:23 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-18 11:50 ` Konstantin Khlebnikov 2016-11-18 11:50 ` Konstantin Khlebnikov 2016-11-18 16:34 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox 2016-11-17 0:17 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox 2016-11-17 0:17 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox 2016-11-17 0:17 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox 2016-11-18 11:52 ` Konstantin Khlebnikov 2016-11-18 13:43 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox 2016-11-17 0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox 2016-11-17 0:17 ` Matthew Wilcox
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1479341856-30320-14-git-send-email-mawilcox@linuxonhyperv.com \ --to=mawilcox@linuxonhyperv.com \ --cc=akpm@linux-foundation.org \ --cc=kirill.shutemov@linux.intel.com \ --cc=koct9i@gmail.com \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=ross.zwisler@linux.intel.com \ --cc=willy@linux.intel.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.