From: Matthew Wilcox <willy@linux.intel.com> To: Jan Kara <jack@suse.cz> Cc: linux-fsdevel@vger.kernel.org, "Wilcox, Matthew R <matthew.r.wilcox@intel.com>, NeilBrown <neilb@suse.com>, Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>, linux-nvdimm@lists.01.org Subject: Re: [RFC v2] [PATCH 0/10] DAX page fault locking Date: Thu, 24 Mar 2016 06:00:54 -0400 [thread overview] Message-ID: <20160324100054.GA23915@linux.intel.com> (raw) In-Reply-To: <20160323150939.GK4512@quack.suse.cz> On Wed, Mar 23, 2016 at 04:09:39PM +0100, Jan Kara wrote: > So when looking through the fixes I was wondering: Are really sibling > entries worth it? Won't the result be simpler if we just used I realised we could slightly simplify the pattern in each walker so they don't have to explicitly care about sibling entries. It ends up saving 64 bytes of text on my .config, so I think it's worth it: diff --git a/lib/radix-tree.c b/lib/radix-tree.c index f0f2f49..779025f 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -99,20 +99,19 @@ static inline unsigned get_sibling_offset(struct radix_tree_node *parent, return ptr - parent->slots; } -static unsigned follow_sibling(struct radix_tree_node *parent, +static unsigned rt_next_level(struct radix_tree_node *parent, struct radix_tree_node **slot, unsigned offset) { - struct radix_tree_node *node = *slot; - - if (!radix_tree_is_indirect_ptr(node)) - return offset; - - node = indirect_to_ptr(node); - if (!is_sibling_entry(parent, node)) - return offset; + void **entry = rcu_dereference_raw(parent->slots[offset]); + if (radix_tree_is_indirect_ptr(entry)) { + uintptr_t siboff = entry - parent->slots; + if (siboff < RADIX_TREE_MAP_SIZE) { + offset = siboff; + entry = rcu_dereference_raw(parent->slots[offset]); + } + } - offset = (void **)node - parent->slots; - *slot = *(void **)node; + *slot = (void *)entry; return offset; } @@ -663,6 +662,8 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, shift = height * RADIX_TREE_MAP_SHIFT; for (;;) { + unsigned offset; + if (!node) return NULL; if (node == RADIX_TREE_RETRY) @@ -670,18 +671,14 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, if (!radix_tree_is_indirect_ptr(node)) break; node = indirect_to_ptr(node); - if (is_sibling_entry(parent, node)) { - slot = (void **)node; - node = rcu_dereference_raw(*slot); - break; - } BUG_ON(shift == 0); shift -= RADIX_TREE_MAP_SHIFT; BUG_ON(node->shift != shift); parent = node; - slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK); - node = rcu_dereference_raw(*slot); + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + offset = rt_next_level(parent, &node, offset); + slot = parent->slots + offset; } if (nodep) @@ -764,10 +761,9 @@ void *radix_tree_tag_set(struct radix_tree_root *root, offset = (index >> shift) & RADIX_TREE_MAP_MASK; slot = indirect_to_ptr(slot); - next = slot->slots[offset]; + offset = rt_next_level(slot, &next, offset); BUG_ON(!next); - offset = follow_sibling(slot, &next, offset); if (!tag_get(slot, tag, offset)) tag_set(slot, tag, offset); slot = next; @@ -819,10 +815,9 @@ void *radix_tree_tag_clear(struct radix_tree_root *root, BUG_ON(shift != slot->shift); offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; - slot = slot->slots[offset]; + offset = rt_next_level(node, &slot, offset); if (slot == NULL) goto out; - offset = follow_sibling(node, &slot, offset); } if (slot == NULL) @@ -892,11 +887,11 @@ int radix_tree_tag_get(struct radix_tree_root *root, node = indirect_to_ptr(node); offset = (index >> shift) & RADIX_TREE_MAP_MASK; - next = rcu_dereference_raw(node->slots[offset]); + offset = rt_next_level(node, &next, offset); + if (!next) return 0; - - offset = follow_sibling(node, &next, offset); + /* RADIX_TREE_RETRY is OK here; the tag is still valid */ if (!tag_get(node, tag, offset)) return 0; if (!radix_tree_is_indirect_ptr(next)) @@ -988,10 +983,9 @@ restart: goto restart; } - slot = rcu_dereference_raw(node->slots[offset]); + offset = rt_next_level(node, &slot, offset); if ((slot == NULL) || (slot == RADIX_TREE_RETRY)) goto restart; - offset = follow_sibling(node, &slot, offset); if (!radix_tree_is_indirect_ptr(slot)) break; if (shift == 0) _______________________________________________ Linux-nvdimm mailing list Linux-nvdimm@lists.01.org https://lists.01.org/mailman/listinfo/linux-nvdimm
WARNING: multiple messages have this Message-ID (diff)
From: Matthew Wilcox <willy@linux.intel.com> To: Jan Kara <jack@suse.cz> Cc: linux-fsdevel@vger.kernel.org, linux-nvdimm@lists.01.org, NeilBrown <neilb@suse.com>, "Wilcox, Matthew R" <matthew.r.wilcox@intel.com>, "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> Subject: Re: [RFC v2] [PATCH 0/10] DAX page fault locking Date: Thu, 24 Mar 2016 06:00:54 -0400 [thread overview] Message-ID: <20160324100054.GA23915@linux.intel.com> (raw) In-Reply-To: <20160323150939.GK4512@quack.suse.cz> On Wed, Mar 23, 2016 at 04:09:39PM +0100, Jan Kara wrote: > So when looking through the fixes I was wondering: Are really sibling > entries worth it? Won't the result be simpler if we just used I realised we could slightly simplify the pattern in each walker so they don't have to explicitly care about sibling entries. It ends up saving 64 bytes of text on my .config, so I think it's worth it: diff --git a/lib/radix-tree.c b/lib/radix-tree.c index f0f2f49..779025f 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -99,20 +99,19 @@ static inline unsigned get_sibling_offset(struct radix_tree_node *parent, return ptr - parent->slots; } -static unsigned follow_sibling(struct radix_tree_node *parent, +static unsigned rt_next_level(struct radix_tree_node *parent, struct radix_tree_node **slot, unsigned offset) { - struct radix_tree_node *node = *slot; - - if (!radix_tree_is_indirect_ptr(node)) - return offset; - - node = indirect_to_ptr(node); - if (!is_sibling_entry(parent, node)) - return offset; + void **entry = rcu_dereference_raw(parent->slots[offset]); + if (radix_tree_is_indirect_ptr(entry)) { + uintptr_t siboff = entry - parent->slots; + if (siboff < RADIX_TREE_MAP_SIZE) { + offset = siboff; + entry = rcu_dereference_raw(parent->slots[offset]); + } + } - offset = (void **)node - parent->slots; - *slot = *(void **)node; + *slot = (void *)entry; return offset; } @@ -663,6 +662,8 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, shift = height * RADIX_TREE_MAP_SHIFT; for (;;) { + unsigned offset; + if (!node) return NULL; if (node == RADIX_TREE_RETRY) @@ -670,18 +671,14 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, if (!radix_tree_is_indirect_ptr(node)) break; node = indirect_to_ptr(node); - if (is_sibling_entry(parent, node)) { - slot = (void **)node; - node = rcu_dereference_raw(*slot); - break; - } BUG_ON(shift == 0); shift -= RADIX_TREE_MAP_SHIFT; BUG_ON(node->shift != shift); parent = node; - slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK); - node = rcu_dereference_raw(*slot); + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + offset = rt_next_level(parent, &node, offset); + slot = parent->slots + offset; } if (nodep) @@ -764,10 +761,9 @@ void *radix_tree_tag_set(struct radix_tree_root *root, offset = (index >> shift) & RADIX_TREE_MAP_MASK; slot = indirect_to_ptr(slot); - next = slot->slots[offset]; + offset = rt_next_level(slot, &next, offset); BUG_ON(!next); - offset = follow_sibling(slot, &next, offset); if (!tag_get(slot, tag, offset)) tag_set(slot, tag, offset); slot = next; @@ -819,10 +815,9 @@ void *radix_tree_tag_clear(struct radix_tree_root *root, BUG_ON(shift != slot->shift); offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; - slot = slot->slots[offset]; + offset = rt_next_level(node, &slot, offset); if (slot == NULL) goto out; - offset = follow_sibling(node, &slot, offset); } if (slot == NULL) @@ -892,11 +887,11 @@ int radix_tree_tag_get(struct radix_tree_root *root, node = indirect_to_ptr(node); offset = (index >> shift) & RADIX_TREE_MAP_MASK; - next = rcu_dereference_raw(node->slots[offset]); + offset = rt_next_level(node, &next, offset); + if (!next) return 0; - - offset = follow_sibling(node, &next, offset); + /* RADIX_TREE_RETRY is OK here; the tag is still valid */ if (!tag_get(node, tag, offset)) return 0; if (!radix_tree_is_indirect_ptr(next)) @@ -988,10 +983,9 @@ restart: goto restart; } - slot = rcu_dereference_raw(node->slots[offset]); + offset = rt_next_level(node, &slot, offset); if ((slot == NULL) || (slot == RADIX_TREE_RETRY)) goto restart; - offset = follow_sibling(node, &slot, offset); if (!radix_tree_is_indirect_ptr(slot)) break; if (shift == 0)
next prev parent reply other threads:[~2016-03-24 10:00 UTC|newest] Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-03-21 13:22 [RFC v2] [PATCH 0/10] DAX page fault locking Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-21 13:22 ` [PATCH 01/10] DAX: move RADIX_DAX_ definitions to dax.c Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-21 17:25 ` Matthew Wilcox 2016-03-21 17:25 ` Matthew Wilcox 2016-03-21 13:22 ` [PATCH 02/10] radix-tree: make 'indirect' bit available to exception entries Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-21 17:34 ` Matthew Wilcox 2016-03-21 17:34 ` Matthew Wilcox 2016-03-22 9:12 ` Jan Kara 2016-03-22 9:12 ` Jan Kara 2016-03-22 9:27 ` Matthew Wilcox 2016-03-22 9:27 ` Matthew Wilcox 2016-03-22 10:37 ` Jan Kara 2016-03-22 10:37 ` Jan Kara 2016-03-23 16:41 ` Ross Zwisler 2016-03-23 16:41 ` Ross Zwisler 2016-03-24 12:31 ` Jan Kara 2016-03-24 12:31 ` Jan Kara 2016-03-21 13:22 ` [PATCH 03/10] dax: Remove complete_unwritten argument Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-23 17:12 ` Ross Zwisler 2016-03-23 17:12 ` Ross Zwisler 2016-03-24 12:32 ` Jan Kara 2016-03-24 12:32 ` Jan Kara 2016-03-21 13:22 ` [PATCH 04/10] dax: Fix data corruption for written and mmapped files Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-23 17:39 ` Ross Zwisler 2016-03-23 17:39 ` Ross Zwisler 2016-03-24 12:51 ` Jan Kara 2016-03-24 12:51 ` Jan Kara 2016-03-29 15:17 ` Ross Zwisler 2016-03-29 15:17 ` Ross Zwisler 2016-03-21 13:22 ` [PATCH 05/10] dax: Allow DAX code to replace exceptional entries Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-23 17:52 ` Ross Zwisler 2016-03-23 17:52 ` Ross Zwisler 2016-03-24 10:42 ` Jan Kara 2016-03-24 10:42 ` Jan Kara 2016-03-21 13:22 ` [PATCH 06/10] dax: Remove redundant inode size checks Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-23 21:08 ` Ross Zwisler 2016-03-23 21:08 ` Ross Zwisler 2016-03-21 13:22 ` [PATCH 07/10] dax: Disable huge page handling Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-23 20:50 ` Ross Zwisler 2016-03-23 20:50 ` Ross Zwisler 2016-03-24 12:56 ` Jan Kara 2016-03-24 12:56 ` Jan Kara 2016-03-21 13:22 ` [PATCH 08/10] dax: New fault locking Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-29 21:57 ` Ross Zwisler 2016-03-29 21:57 ` Ross Zwisler 2016-03-31 16:27 ` Jan Kara 2016-03-31 16:27 ` Jan Kara 2016-03-21 13:22 ` [PATCH 09/10] dax: Use radix tree entry lock to protect cow faults Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-21 19:11 ` Matthew Wilcox 2016-03-21 19:11 ` Matthew Wilcox 2016-03-22 7:03 ` Jan Kara 2016-03-22 7:03 ` Jan Kara 2016-03-29 22:18 ` Ross Zwisler 2016-03-29 22:18 ` Ross Zwisler 2016-03-21 13:22 ` [PATCH 10/10] dax: Remove i_mmap_lock protection Jan Kara 2016-03-21 13:22 ` Jan Kara 2016-03-29 22:17 ` Ross Zwisler 2016-03-29 22:17 ` Ross Zwisler 2016-03-21 17:41 ` [RFC v2] [PATCH 0/10] DAX page fault locking Matthew Wilcox 2016-03-21 17:41 ` Matthew Wilcox 2016-03-23 15:09 ` Jan Kara 2016-03-23 15:09 ` Jan Kara 2016-03-23 20:50 ` Matthew Wilcox 2016-03-23 20:50 ` Matthew Wilcox 2016-03-24 10:00 ` Matthew Wilcox [this message] 2016-03-24 10:00 ` Matthew Wilcox 2016-03-22 19:32 ` Ross Zwisler 2016-03-22 19:32 ` Ross Zwisler 2016-03-22 21:07 ` Toshi Kani 2016-03-22 21:07 ` Toshi Kani 2016-03-22 21:15 ` Dave Chinner 2016-03-22 21:15 ` Dave Chinner 2016-03-23 9:45 ` Jan Kara 2016-03-23 9:45 ` Jan Kara 2016-03-23 15:11 ` Toshi Kani 2016-03-23 15:11 ` Toshi Kani -- strict thread matches above, loose matches on Subject: below -- 2016-03-21 13:21 Jan Kara 2016-03-21 13:21 ` Jan Kara
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=20160324100054.GA23915@linux.intel.com \ --to=willy@linux.intel.com \ --cc=jack@suse.cz \ --cc=kirill.shutemov@linux.intel.com \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-nvdimm@lists.01.org \ /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.