From: Matthew Wilcox <willy@linux.intel.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org> Cc: Ross Zwisler <ross.zwisler@linux.intel.com>, linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, Konstantin Khlebnikov <koct9i@gmail.com>, Kirill Shutemov <kirill.shutemov@linux.intel.com>, Jan Kara <jack@suse.com>, Neil Brown <neilb@suse.de>, Matthew Wilcox <willy@linux.intel.com> Subject: [PATCH v2 23/29] radix-tree: Rewrite radix_tree_tag_get Date: Thu, 14 Apr 2016 10:16:44 -0400 [thread overview] Message-ID: <1460643410-30196-24-git-send-email-willy@linux.intel.com> (raw) In-Reply-To: <1460643410-30196-1-git-send-email-willy@linux.intel.com> From: Ross Zwisler <ross.zwisler@linux.intel.com> Use the new multi-order support functions to rewrite radix_tree_tag_get() Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- lib/radix-tree.c | 44 ++++++++++++++++++-------------------------- 1 file changed, 18 insertions(+), 26 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index ee56562..b1ca744 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -831,45 +831,37 @@ EXPORT_SYMBOL(radix_tree_tag_clear); int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag) { - unsigned int height, shift; - struct radix_tree_node *node; + struct radix_tree_node *node, *parent; + unsigned long maxindex; + unsigned int shift; - /* check the root's tag bit */ if (!root_tag_get(root, tag)) return 0; - node = rcu_dereference_raw(root->rnode); + shift = radix_tree_load_root(root, &node, &maxindex); + if (index > maxindex) + return 0; if (node == NULL) return 0; - if (!radix_tree_is_indirect_ptr(node)) - return (index == 0); - node = indirect_to_ptr(node); - - height = node->path & RADIX_TREE_HEIGHT_MASK; - if (index > radix_tree_maxindex(height)) - return 0; + while (radix_tree_is_indirect_ptr(node)) { + int offset; - shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + shift -= RADIX_TREE_MAP_SHIFT; + offset = (index >> shift) & RADIX_TREE_MAP_MASK; - for ( ; ; ) { - int offset; + parent = indirect_to_ptr(node); + offset = radix_tree_descend(parent, &node, offset); - if (node == NULL) + if (!node) return 0; - node = indirect_to_ptr(node); - - offset = (index >> shift) & RADIX_TREE_MAP_MASK; - if (!tag_get(node, tag, offset)) + if (!tag_get(parent, tag, offset)) return 0; - if (height == 1) - return 1; - node = rcu_dereference_raw(node->slots[offset]); - if (!radix_tree_is_indirect_ptr(node)) - return 1; - shift -= RADIX_TREE_MAP_SHIFT; - height--; + if (node == RADIX_TREE_RETRY) + break; } + + return 1; } EXPORT_SYMBOL(radix_tree_tag_get); -- 2.8.0.rc3
WARNING: multiple messages have this Message-ID (diff)
From: Matthew Wilcox <willy@linux.intel.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org> Cc: Ross Zwisler <ross.zwisler@linux.intel.com>, linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, Konstantin Khlebnikov <koct9i@gmail.com>, Kirill Shutemov <kirill.shutemov@linux.intel.com>, Jan Kara <jack@suse.com>, Neil Brown <neilb@suse.de>, Matthew Wilcox <willy@linux.intel.com> Subject: [PATCH v2 23/29] radix-tree: Rewrite radix_tree_tag_get Date: Thu, 14 Apr 2016 10:16:44 -0400 [thread overview] Message-ID: <1460643410-30196-24-git-send-email-willy@linux.intel.com> (raw) In-Reply-To: <1460643410-30196-1-git-send-email-willy@linux.intel.com> From: Ross Zwisler <ross.zwisler@linux.intel.com> Use the new multi-order support functions to rewrite radix_tree_tag_get() Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- lib/radix-tree.c | 44 ++++++++++++++++++-------------------------- 1 file changed, 18 insertions(+), 26 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index ee56562..b1ca744 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -831,45 +831,37 @@ EXPORT_SYMBOL(radix_tree_tag_clear); int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag) { - unsigned int height, shift; - struct radix_tree_node *node; + struct radix_tree_node *node, *parent; + unsigned long maxindex; + unsigned int shift; - /* check the root's tag bit */ if (!root_tag_get(root, tag)) return 0; - node = rcu_dereference_raw(root->rnode); + shift = radix_tree_load_root(root, &node, &maxindex); + if (index > maxindex) + return 0; if (node == NULL) return 0; - if (!radix_tree_is_indirect_ptr(node)) - return (index == 0); - node = indirect_to_ptr(node); - - height = node->path & RADIX_TREE_HEIGHT_MASK; - if (index > radix_tree_maxindex(height)) - return 0; + while (radix_tree_is_indirect_ptr(node)) { + int offset; - shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + shift -= RADIX_TREE_MAP_SHIFT; + offset = (index >> shift) & RADIX_TREE_MAP_MASK; - for ( ; ; ) { - int offset; + parent = indirect_to_ptr(node); + offset = radix_tree_descend(parent, &node, offset); - if (node == NULL) + if (!node) return 0; - node = indirect_to_ptr(node); - - offset = (index >> shift) & RADIX_TREE_MAP_MASK; - if (!tag_get(node, tag, offset)) + if (!tag_get(parent, tag, offset)) return 0; - if (height == 1) - return 1; - node = rcu_dereference_raw(node->slots[offset]); - if (!radix_tree_is_indirect_ptr(node)) - return 1; - shift -= RADIX_TREE_MAP_SHIFT; - height--; + if (node == RADIX_TREE_RETRY) + break; } + + return 1; } EXPORT_SYMBOL(radix_tree_tag_get); -- 2.8.0.rc3 -- 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-04-14 14:17 UTC|newest] Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-04-14 14:16 [PATCH v2 00/29] Radix tree multiorder fixes Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 01/29] radix-tree: Introduce radix_tree_empty Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-05-03 14:24 ` Jan Kara 2016-05-03 14:24 ` Jan Kara 2016-04-14 14:16 ` [PATCH v2 02/29] radix tree test suite: Fix build Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 03/29] radix tree test suite: Add tests for radix_tree_locate_item() Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 04/29] radix tree test suite: Allow testing other fan-out values Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 05/29] radix tree test suite: keep regression test runs short Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 06/29] radix tree test suite: rebuild when headers change Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 07/29] radix-tree: remove unused looping macros Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 08/29] Introduce CONFIG_RADIX_TREE_MULTIORDER Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 09/29] radix-tree: Add missing sibling entry functionality Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 10/29] radix-tree: Fix sibling entry insertion Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 11/29] radix-tree: Fix deleting a multi-order entry through an alias Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 12/29] radix-tree: Remove restriction on multi-order entries Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 13/29] radix-tree: Introduce radix_tree_load_root() Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 14/29] radix-tree: Fix extending the tree for multi-order entries at offset 0 Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 15/29] radix tree test suite: Start adding multiorder tests Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 16/29] radix-tree: Fix several shrinking bugs with multiorder entries Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 17/29] radix-tree: Rewrite __radix_tree_lookup Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 18/29] radix-tree: Fix multiorder BUG_ON in radix_tree_insert Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 19/29] radix-tree: add support for multi-order iterating Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 20/29] radix tree test suite: multi-order iteration test Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 21/29] radix-tree: Rewrite radix_tree_tag_set Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 22/29] radix-tree: Rewrite radix_tree_tag_clear Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox [this message] 2016-04-14 14:16 ` [PATCH v2 23/29] radix-tree: Rewrite radix_tree_tag_get Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 24/29] radix-tree test suite: add multi-order tag test Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 25/29] radix-tree: Fix radix_tree_create for sibling entries Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 26/29] radix-tree: Rewrite radix_tree_locate_item Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 27/29] radix-tree: Fix radix_tree_range_tag_if_tagged() for multiorder entries Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 28/29] radix-tree: Fix radix_tree_dump() for multi-order entries Matthew Wilcox 2016-04-14 14:16 ` Matthew Wilcox 2016-04-14 14:16 ` [PATCH v2 29/29] radix-tree: Add copyright statements Matthew Wilcox 2016-04-14 14:16 ` 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=1460643410-30196-24-git-send-email-willy@linux.intel.com \ --to=willy@linux.intel.com \ --cc=akpm@linux-foundation.org \ --cc=jack@suse.com \ --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=neilb@suse.de \ --cc=ross.zwisler@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.