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>," linux-nvdimm@lists.01.org Subject: Re: [PATCH 02/10] radix-tree: make 'indirect' bit available to exception entries. Date: Mon, 21 Mar 2016 13:34:58 -0400 [thread overview] Message-ID: <20160321173458.GO23727@linux.intel.com> (raw) In-Reply-To: <1458566575-28063-3-git-send-email-jack@suse.cz> On Mon, Mar 21, 2016 at 02:22:47PM +0100, Jan Kara wrote: > 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'. Nitpick: it's called INDIRECT_MASK, not PTR_MASK. > 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. typo "exceptional" > But I have other plans for that bit.... > > Signed-off-by: NeilBrown <neilb@suse.com> > Signed-off-by: Jan Kara <jack@suse.cz> > --- > 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 d08d6ec3bf53..2bc8c5829441 100644 > --- a/include/linux/radix-tree.h > +++ b/include/linux/radix-tree.h > @@ -41,8 +41,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: > @@ -54,7 +59,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 ***/ > @@ -222,7 +228,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 1624c4117961..c6af1a445b67 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -1412,7 +1412,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; I have a patch currently in my tree which has the same effect, but looks a little neater: diff --git a/lib/radix-tree.c b/lib/radix-tree.c index b77c31c..06dfed5 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -70,6 +70,8 @@ struct radix_tree_preload { }; static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; +#define RADIX_TREE_RETRY ((void *)1) + static inline void *ptr_to_indirect(void *ptr) { return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); @@ -934,7 +936,7 @@ restart: } slot = rcu_dereference_raw(node->slots[offset]); - if (slot == NULL) + if ((slot == NULL) || (slot == RADIX_TREE_RETRY)) goto restart; offset = follow_sibling(node, &slot, offset); if (!radix_tree_is_indirect_ptr(slot)) @@ -1443,8 +1455,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * to force callers to retry. */ if (!radix_tree_is_indirect_ptr(slot)) - *((unsigned long *)&to_free->slots[0]) |= - RADIX_TREE_INDIRECT_PTR; + to_free->slots[0] = RADIX_TREE_RETRY; radix_tree_node_free(to_free); } What do you think to doing it this way? It might be slightly neater to replace the first hunk with this: #define RADIX_TREE_RETRY ((void *)RADIX_TREE_INDIRECT_PTR) I also considered putting that define in radix-tree.h instead of radix-tree.c, but on the whole I don't think it'll be useful outside radix-tree.h. _______________________________________________ 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> Subject: Re: [PATCH 02/10] radix-tree: make 'indirect' bit available to exception entries. Date: Mon, 21 Mar 2016 13:34:58 -0400 [thread overview] Message-ID: <20160321173458.GO23727@linux.intel.com> (raw) In-Reply-To: <1458566575-28063-3-git-send-email-jack@suse.cz> On Mon, Mar 21, 2016 at 02:22:47PM +0100, Jan Kara wrote: > 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'. Nitpick: it's called INDIRECT_MASK, not PTR_MASK. > 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. typo "exceptional" > But I have other plans for that bit.... > > Signed-off-by: NeilBrown <neilb@suse.com> > Signed-off-by: Jan Kara <jack@suse.cz> > --- > 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 d08d6ec3bf53..2bc8c5829441 100644 > --- a/include/linux/radix-tree.h > +++ b/include/linux/radix-tree.h > @@ -41,8 +41,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: > @@ -54,7 +59,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 ***/ > @@ -222,7 +228,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 1624c4117961..c6af1a445b67 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -1412,7 +1412,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; I have a patch currently in my tree which has the same effect, but looks a little neater: diff --git a/lib/radix-tree.c b/lib/radix-tree.c index b77c31c..06dfed5 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -70,6 +70,8 @@ struct radix_tree_preload { }; static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; +#define RADIX_TREE_RETRY ((void *)1) + static inline void *ptr_to_indirect(void *ptr) { return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); @@ -934,7 +936,7 @@ restart: } slot = rcu_dereference_raw(node->slots[offset]); - if (slot == NULL) + if ((slot == NULL) || (slot == RADIX_TREE_RETRY)) goto restart; offset = follow_sibling(node, &slot, offset); if (!radix_tree_is_indirect_ptr(slot)) @@ -1443,8 +1455,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * to force callers to retry. */ if (!radix_tree_is_indirect_ptr(slot)) - *((unsigned long *)&to_free->slots[0]) |= - RADIX_TREE_INDIRECT_PTR; + to_free->slots[0] = RADIX_TREE_RETRY; radix_tree_node_free(to_free); } What do you think to doing it this way? It might be slightly neater to replace the first hunk with this: #define RADIX_TREE_RETRY ((void *)RADIX_TREE_INDIRECT_PTR) I also considered putting that define in radix-tree.h instead of radix-tree.c, but on the whole I don't think it'll be useful outside radix-tree.h.
next prev parent reply other threads:[~2016-03-21 23:45 UTC|newest] Thread overview: 86+ 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 [this message] 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 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
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=20160321173458.GO23727@linux.intel.com \ --to=willy@linux.intel.com \ --cc=jack@suse.cz \ --cc=linux-fsdevel@vger.kernel.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.