From: "Wilcox, Matthew R" <matthew.r.wilcox@intel.com> To: NeilBrown <neilb@suse.com>, Ross Zwisler <ross.zwisler@linux.intel.com>, Andrew Morton <akpm@linux-foundation.org>, Jan Kara <jack@suse.cz> Cc: "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>, "linux-fsdevel@vger.kernel.org" <linux-fsdevel@vger.kernel.org>, "linux-mm@kvack.org" <linux-mm@kvack.org> Subject: RE: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries. Date: Mon, 29 Feb 2016 14:41:55 +0000 [thread overview] Message-ID: <100D68C7BA14664A8938383216E40DE0421D3AE9@FMSMSX114.amr.corp.intel.com> (raw) In-Reply-To: <145663616977.3865.9772784012366988314.stgit@notabene> So based on the bottom two bits, we can tell what this entry is: 00 - data pointer 01 - indirect entry (pointer to another level of the radix tree) 10 - exceptional entry 11 - locked exceptional entry I was concerned that this patch would clash with the support for multi-order entries in the radix tree, but after some thought, I now believe that it doesn't. The multi-order entries changes permit finding data pointers or exceptional entries in the tree where before only indirect entries could be found, but with the changes to radix_tree_is_indirect_ptr below, everything should work fine. -----Original Message----- From: NeilBrown [mailto:neilb@suse.com] Sent: Saturday, February 27, 2016 9:09 PM To: Ross Zwisler; Wilcox, Matthew R; Andrew Morton; Jan Kara Cc: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org; linux-mm@kvack.org Subject: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries. A pointer to a radix_tree_node will always have the 'exception' bit cleared, so if the exception bit is set the value cannot be an indirect pointer. Thus it is safe to make the 'indirect bit' available to store extra information in exception entries. This patch adds a 'PTR_MASK' and a value is only treated as an indirect (pointer) entry the 2 ls-bits are '01'. The change in radix-tree.c ensures the stored value still looks like an indirect pointer, and saves a load as well. We could swap the two bits and so keep all the exectional bits contigious. But I have other plans for that bit.... Signed-off-by: NeilBrown <neilb@suse.com> --- include/linux/radix-tree.h | 11 +++++++++-- lib/radix-tree.c | 2 +- 2 files changed, 10 insertions(+), 3 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 968150ab8a1c..450c12b546b7 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -40,8 +40,13 @@ * Indirect pointer in fact is also used to tag the last pointer of a node * when it is shrunk, before we rcu free the node. See shrink code for * details. + * + * To allow an exception entry to only lose one bit, we ignore + * the INDIRECT bit when the exception bit is set. So an entry is + * indirect if the least significant 2 bits are 01. */ #define RADIX_TREE_INDIRECT_PTR 1 +#define RADIX_TREE_INDIRECT_MASK 3 /* * A common use of the radix tree is to store pointers to struct pages; * but shmem/tmpfs needs also to store swap entries in the same tree: @@ -53,7 +58,8 @@ static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); + return ((unsigned long)ptr & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR; } /*** radix-tree API starts here ***/ @@ -221,7 +227,8 @@ static inline void *radix_tree_deref_slot_protected(void **pslot, */ static inline int radix_tree_deref_retry(void *arg) { - return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR); + return unlikely(((unsigned long)arg & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR); } /** diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6b79e9026e24..37d4643ab5c0 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1305,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * to force callers to retry. */ if (root->height == 0) - *((unsigned long *)&to_free->slots[0]) |= + *((unsigned long *)&to_free->slots[0]) = RADIX_TREE_INDIRECT_PTR; radix_tree_node_free(to_free);
WARNING: multiple messages have this Message-ID (diff)
From: "Wilcox, Matthew R" <matthew.r.wilcox@intel.com> To: NeilBrown <neilb@suse.com>, Ross Zwisler <ross.zwisler@linux.intel.com>, Andrew Morton <akpm@linux-foundation.org>, Jan Kara <jack@suse.cz> Cc: "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>, "linux-fsdevel@vger.kernel.org" <linux-fsdevel@vger.kernel.org>, "linux-mm@kvack.org" <linux-mm@kvack.org> Subject: RE: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries. Date: Mon, 29 Feb 2016 14:41:55 +0000 [thread overview] Message-ID: <100D68C7BA14664A8938383216E40DE0421D3AE9@FMSMSX114.amr.corp.intel.com> (raw) In-Reply-To: <145663616977.3865.9772784012366988314.stgit@notabene> [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain; charset="utf-8", Size: 3723 bytes --] So based on the bottom two bits, we can tell what this entry is: 00 - data pointer 01 - indirect entry (pointer to another level of the radix tree) 10 - exceptional entry 11 - locked exceptional entry I was concerned that this patch would clash with the support for multi-order entries in the radix tree, but after some thought, I now believe that it doesn't. The multi-order entries changes permit finding data pointers or exceptional entries in the tree where before only indirect entries could be found, but with the changes to radix_tree_is_indirect_ptr below, everything should work fine. -----Original Message----- From: NeilBrown [mailto:neilb@suse.com] Sent: Saturday, February 27, 2016 9:09 PM To: Ross Zwisler; Wilcox, Matthew R; Andrew Morton; Jan Kara Cc: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org; linux-mm@kvack.org Subject: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries. A pointer to a radix_tree_node will always have the 'exception' bit cleared, so if the exception bit is set the value cannot be an indirect pointer. Thus it is safe to make the 'indirect bit' available to store extra information in exception entries. This patch adds a 'PTR_MASK' and a value is only treated as an indirect (pointer) entry the 2 ls-bits are '01'. The change in radix-tree.c ensures the stored value still looks like an indirect pointer, and saves a load as well. We could swap the two bits and so keep all the exectional bits contigious. But I have other plans for that bit.... Signed-off-by: NeilBrown <neilb@suse.com> --- include/linux/radix-tree.h | 11 +++++++++-- lib/radix-tree.c | 2 +- 2 files changed, 10 insertions(+), 3 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 968150ab8a1c..450c12b546b7 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -40,8 +40,13 @@ * Indirect pointer in fact is also used to tag the last pointer of a node * when it is shrunk, before we rcu free the node. See shrink code for * details. + * + * To allow an exception entry to only lose one bit, we ignore + * the INDIRECT bit when the exception bit is set. So an entry is + * indirect if the least significant 2 bits are 01. */ #define RADIX_TREE_INDIRECT_PTR 1 +#define RADIX_TREE_INDIRECT_MASK 3 /* * A common use of the radix tree is to store pointers to struct pages; * but shmem/tmpfs needs also to store swap entries in the same tree: @@ -53,7 +58,8 @@ static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); + return ((unsigned long)ptr & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR; } /*** radix-tree API starts here ***/ @@ -221,7 +227,8 @@ static inline void *radix_tree_deref_slot_protected(void **pslot, */ static inline int radix_tree_deref_retry(void *arg) { - return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR); + return unlikely(((unsigned long)arg & RADIX_TREE_INDIRECT_MASK) + == RADIX_TREE_INDIRECT_PTR); } /** diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6b79e9026e24..37d4643ab5c0 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1305,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * to force callers to retry. */ if (root->height == 0) - *((unsigned long *)&to_free->slots[0]) |= + *((unsigned long *)&to_free->slots[0]) = RADIX_TREE_INDIRECT_PTR; radix_tree_node_free(to_free); N§²æìr¸zǧu©²Æ {\béì¹»\x1c®&Þ)îÆi¢Ø^nr¶Ý¢j$½§$¢¸\x05¢¹¨è§~'.)îÄÃ,yèm¶ÿÃ\f%{±j+ðèצj)Z·
next prev parent reply other threads:[~2016-02-29 14:42 UTC|newest] Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-02-28 5:09 [PATCH 0/3] RFC improvements to radix-tree related to DAX NeilBrown 2016-02-28 5:09 ` NeilBrown 2016-02-28 5:09 ` [PATCH 3/3] radix-tree: support locking of individual exception entries NeilBrown 2016-02-28 5:09 ` NeilBrown 2016-02-28 5:30 ` kbuild test robot 2016-02-28 6:27 ` NeilBrown 2016-03-03 13:10 ` Jan Kara 2016-03-03 13:10 ` Jan Kara 2016-03-03 23:51 ` NeilBrown 2016-03-03 23:51 ` NeilBrown 2016-03-04 10:14 ` NeilBrown 2016-03-04 10:14 ` NeilBrown 2016-03-04 12:31 ` Jan Kara 2016-03-04 12:31 ` Jan Kara 2016-03-09 2:13 ` NeilBrown 2016-02-28 5:09 ` [PATCH 2/3] radix-tree: make 'indirect' bit available to " NeilBrown 2016-02-28 5:09 ` NeilBrown 2016-02-29 14:41 ` Wilcox, Matthew R [this message] 2016-02-29 14:41 ` Wilcox, Matthew R 2016-03-01 21:59 ` Ross Zwisler 2016-03-01 21:59 ` Ross Zwisler 2016-02-28 5:09 ` [PATCH 1/3] DAX: move RADIX_DAX_ definitions to dax.c NeilBrown 2016-02-28 5:09 ` NeilBrown 2016-02-29 14:28 ` Wilcox, Matthew R 2016-02-29 17:46 ` Ross Zwisler 2016-02-29 17:46 ` Ross Zwisler
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=100D68C7BA14664A8938383216E40DE0421D3AE9@FMSMSX114.amr.corp.intel.com \ --to=matthew.r.wilcox@intel.com \ --cc=akpm@linux-foundation.org \ --cc=jack@suse.cz \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=neilb@suse.com \ --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.