Tagged pointers in the XArray

Tagged pointers in the XArray

[Matthew Wilcox]

I find myself caught between two traditions.

On the one hand, the radix tree has been calling the page cache dirty &
writeback bits "tags" for over a decade.

On the other hand, using some of the bits _in a pointer_ as a tag has been
common practice since at least the 1960s.
https://en.wikipedia.org/wiki/Tagged_pointer and
https://en.wikipedia.org/wiki/31-bit

EROFS wants to use tagged pointers in the radix tree / xarray.  Right now,
they're building them by hand, which is predictably grotty-looking.
I think it's reasonable to provide this functionality as part of the
XArray API, _but_ it's confusing to have two different things called tags.

I've done my best to document my way around this, but if we want to rename
the things that the radix tree called tags to avoid the problem entirely,
now is the time to do it.  Anybody got a Good Idea?

commit e2f06dd921a072bcc021fc7224a216d2c1b88b54
Author: Matthew Wilcox <willy@infradead.org>
Date:   Tue Aug 28 14:37:22 2018 -0400

    xarray: Add support for tagged pointers
    
    EROFS wants to tag its pointers rather than use XArray tags.  This is
    a new usecase which seems reasonable to support.
    
    Signed-off-by: Matthew Wilcox <willy@infradead.org>

diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
index bc0c43f49efe..215bd468cae7 100644
--- a/Documentation/core-api/xarray.rst
+++ b/Documentation/core-api/xarray.rst
@@ -41,6 +41,12 @@ When you retrieve an entry from the XArray, you can check whether it is
 a value entry by calling :c:func:`xa_is_value`, and convert it back to
 an integer by calling :c:func:`xa_to_value`.
 
+Some users want to tag their pointers without using the tag bits described
+above.  They can call :c:func:`xa_tag_pointer` to create an entry with
+a tag, :c:func:`xa_untag_pointer` to turn a tagged entry back into an
+untagged pointer and :c:func:`xa_pointer_tag` to retrieve the tag of
+an entry.
+
 The XArray does not support storing :c:func:`IS_ERR` pointers as some
 conflict with value entries or internal entries.
 
diff --git a/drivers/staging/erofs/Kconfig b/drivers/staging/erofs/Kconfig
index 96f614934df1..663b755bf2fb 100644
--- a/drivers/staging/erofs/Kconfig
+++ b/drivers/staging/erofs/Kconfig
@@ -2,7 +2,7 @@
 
 config EROFS_FS
 	tristate "EROFS filesystem support"
-	depends on BROKEN
+	depends on BLOCK
 	help
 	  EROFS(Enhanced Read-Only File System) is a lightweight
 	  read-only file system with modern designs (eg. page-sized
diff --git a/drivers/staging/erofs/utils.c b/drivers/staging/erofs/utils.c
index 595cf90af9bb..bdee9bd09f11 100644
--- a/drivers/staging/erofs/utils.c
+++ b/drivers/staging/erofs/utils.c
@@ -35,7 +35,6 @@ static atomic_long_t erofs_global_shrink_cnt;
 
 #ifdef CONFIG_EROFS_FS_ZIP
 
-/* radix_tree and the future XArray both don't use tagptr_t yet */
 struct erofs_workgroup *erofs_find_workgroup(
 	struct super_block *sb, pgoff_t index, bool *tag)
 {
@@ -47,9 +46,8 @@ struct erofs_workgroup *erofs_find_workgroup(
 	rcu_read_lock();
 	grp = radix_tree_lookup(&sbi->workstn_tree, index);
 	if (grp != NULL) {
-		*tag = radix_tree_exceptional_entry(grp);
-		grp = (void *)((unsigned long)grp &
-			~RADIX_TREE_EXCEPTIONAL_ENTRY);
+		*tag = xa_pointer_tag(grp);
+		grp = xa_untag_pointer(grp);
 
 		if (erofs_workgroup_get(grp, &oldcount)) {
 			/* prefer to relax rcu read side */
@@ -83,9 +81,7 @@ int erofs_register_workgroup(struct super_block *sb,
 	sbi = EROFS_SB(sb);
 	erofs_workstn_lock(sbi);
 
-	if (tag)
-		grp = (void *)((unsigned long)grp |
-			1UL << RADIX_TREE_EXCEPTIONAL_SHIFT);
+	grp = xa_tag_pointer(grp, tag);
 
 	err = radix_tree_insert(&sbi->workstn_tree,
 		grp->index, grp);
@@ -131,9 +127,7 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi,
 
 	for (i = 0; i < found; ++i) {
 		int cnt;
-		struct erofs_workgroup *grp = (void *)
-			((unsigned long)batch[i] &
-				~RADIX_TREE_EXCEPTIONAL_ENTRY);
+		struct erofs_workgroup *grp = xa_untag_pointer(batch[i]);
 
 		first_index = grp->index + 1;
 
@@ -150,8 +144,8 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi,
 #endif
 			continue;
 
-		if (radix_tree_delete(&sbi->workstn_tree,
-			grp->index) != grp) {
+		if (xa_untag_pointer(radix_tree_delete(&sbi->workstn_tree,
+			grp->index)) != grp) {
 #ifdef EROFS_FS_HAS_MANAGED_CACHE
 skip:
 			erofs_workgroup_unfreeze(grp, 1);
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index c74556ea4258..d1b383f3063f 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -24,7 +24,7 @@
  *
  * 00: Pointer entry
  * 10: Internal entry
- * x1: Value entry
+ * x1: Value entry or tagged pointer
  *
  * Attempting to store internal entries in the XArray is a bug.
  *
@@ -150,6 +150,54 @@ static inline int xa_err(void *entry)
 	return 0;
 }
 
+/**
+ * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
+ * @p: Plain pointer.
+ * @tag: Tag value (0, 1 or 3).
+ *
+ * If the user of the XArray prefers, they can tag their pointers instead
+ * of storing value entries.  Three tags are available (0, 1 and 3).
+ * These are distinct from the xa_tag_t as they are not replicated up
+ * through the array and cannot be searched for.
+ *
+ * Context: Any context.
+ * Return: An XArray entry.
+ */
+static inline void *xa_tag_pointer(void *p, unsigned long tag)
+{
+	return (void *)((unsigned long)p | tag);
+}
+
+/**
+ * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
+ * @entry: XArray entry.
+ *
+ * If you have stored a tagged pointer in the XArray, call this function
+ * to get the untagged version of the pointer.
+ *
+ * Context: Any context.
+ * Return: A pointer.
+ */
+static inline void *xa_untag_pointer(void *entry)
+{
+	return (void *)((unsigned long)entry & ~3UL);
+}
+
+/**
+ * xa_pointer_tag() - Get the tag stored in an XArray entry.
+ * @entry: XArray entry.
+ *
+ * If you have stored a tagged pointer in the XArray, call this function
+ * to get the tag of that pointer.
+ *
+ * Context: Any context.
+ * Return: A tag.
+ */
+static inline unsigned int xa_pointer_tag(void *entry)
+{
+	return (unsigned long)entry & 3UL;
+}
+
 typedef unsigned __bitwise xa_tag_t;
 #define XA_TAG_0		((__force xa_tag_t)0U)
 #define XA_TAG_1		((__force xa_tag_t)1U)

Re: Tagged pointers in the XArray

[Randy Dunlap]

Just a question, please...

On 08/28/2018 03:27 PM, Matthew Wilcox wrote:
> 
> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
> index c74556ea4258..d1b383f3063f 100644
> --- a/include/linux/xarray.h
> +++ b/include/linux/xarray.h
> @@ -150,6 +150,54 @@ static inline int xa_err(void *entry)
>  	return 0;
>  }
>  
> +/**
> + * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
> + * @p: Plain pointer.
> + * @tag: Tag value (0, 1 or 3).
> + *

What's wrong with a tag value of 2?

and what happens when one is used?  [I don't see anything preventing that.]


> + * If the user of the XArray prefers, they can tag their pointers instead
> + * of storing value entries.  Three tags are available (0, 1 and 3).
> + * These are distinct from the xa_tag_t as they are not replicated up
> + * through the array and cannot be searched for.
> + *
> + * Context: Any context.
> + * Return: An XArray entry.
> + */
> +static inline void *xa_tag_pointer(void *p, unsigned long tag)
> +{
> +	return (void *)((unsigned long)p | tag);
> +}
> +
> +/**
> + * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
> + * @entry: XArray entry.
> + *
> + * If you have stored a tagged pointer in the XArray, call this function
> + * to get the untagged version of the pointer.
> + *
> + * Context: Any context.
> + * Return: A pointer.
> + */
> +static inline void *xa_untag_pointer(void *entry)
> +{
> +	return (void *)((unsigned long)entry & ~3UL);
> +}
> +
> +/**
> + * xa_pointer_tag() - Get the tag stored in an XArray entry.
> + * @entry: XArray entry.
> + *
> + * If you have stored a tagged pointer in the XArray, call this function
> + * to get the tag of that pointer.
> + *
> + * Context: Any context.
> + * Return: A tag.
> + */
> +static inline unsigned int xa_pointer_tag(void *entry)
> +{
> +	return (unsigned long)entry & 3UL;
> +}

thanks,
-- 
~Randy

Re: Tagged pointers in the XArray

[Matthew Wilcox]

On Tue, Aug 28, 2018 at 03:39:01PM -0700, Randy Dunlap wrote:
> Just a question, please...
> 
> On 08/28/2018 03:27 PM, Matthew Wilcox wrote:
> > 
> > diff --git a/include/linux/xarray.h b/include/linux/xarray.h
> > index c74556ea4258..d1b383f3063f 100644
> > --- a/include/linux/xarray.h
> > +++ b/include/linux/xarray.h
> > @@ -150,6 +150,54 @@ static inline int xa_err(void *entry)
> >  	return 0;
> >  }
> >  
> > +/**
> > + * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
> > + * @p: Plain pointer.
> > + * @tag: Tag value (0, 1 or 3).
> > + *
> 
> What's wrong with a tag value of 2?

That conflicts with the XArray's internal entries and you get a WARN_ON
when you try to store it in the array.

> and what happens when one is used?  [I don't see anything preventing that.]

Right, there's nothing preventing you from using the value 5 or 19
or 16777216 either ... I did put in a WARN_ON_ONCE to begin with, but
decided that was unnecessary.

Right now our only user uses 0 and 1, so even documenting 3 as a
possibility isn't _necessary_, but some day somebody is going to want
to add FILE_NOT_FOUND
https://thedailywtf.com/articles/What_Is_Truth_0x3f_

Re: Tagged pointers in the XArray

[Randy Dunlap]

On 08/28/2018 04:03 PM, Matthew Wilcox wrote:
> On Tue, Aug 28, 2018 at 03:39:01PM -0700, Randy Dunlap wrote:
>> Just a question, please...
>>
>> On 08/28/2018 03:27 PM, Matthew Wilcox wrote:
>>>
>>> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
>>> index c74556ea4258..d1b383f3063f 100644
>>> --- a/include/linux/xarray.h
>>> +++ b/include/linux/xarray.h
>>> @@ -150,6 +150,54 @@ static inline int xa_err(void *entry)
>>>  	return 0;
>>>  }
>>>  
>>> +/**
>>> + * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
>>> + * @p: Plain pointer.
>>> + * @tag: Tag value (0, 1 or 3).
>>> + *
>>
>> What's wrong with a tag value of 2?
> 
> That conflicts with the XArray's internal entries and you get a WARN_ON
> when you try to store it in the array.
> 
>> and what happens when one is used?  [I don't see anything preventing that.]
> 
> Right, there's nothing preventing you from using the value 5 or 19
> or 16777216 either ... I did put in a WARN_ON_ONCE to begin with, but
> decided that was unnecessary.
> 
> Right now our only user uses 0 and 1, so even documenting 3 as a
> possibility isn't _necessary_, but some day somebody is going to want
> to add FILE_NOT_FOUND
> https://thedailywtf.com/articles/What_Is_Truth_0x3f_
> 

Thanks.  :)

-- 
~Randy

Re: Tagged pointers in the XArray

[Gao Xiang]

[-- Attachment #1: Type: text/plain, Size: 1846 bytes --]

Hi,

On 2018/8/29 6:27, Matthew Wilcox wrote:
> I find myself caught between two traditions.
>
> On the one hand, the radix tree has been calling the page cache dirty &
> writeback bits "tags" for over a decade.
>
> On the other hand, using some of the bits _in a pointer_ as a tag has been
> common practice since at least the 1960s.
> https://en.wikipedia.org/wiki/Tagged_pointer and
> https://en.wikipedia.org/wiki/31-bit

Personally I think this topic makes sense. These two `tags' are totally
different actually.

> EROFS wants to use tagged pointers in the radix tree / xarray.  Right now,
> they're building them by hand, which is predictably grotty-looking.
> I think it's reasonable to provide this functionality as part of the
> XArray API, _but_ it's confusing to have two different things called tags.
>
> I've done my best to document my way around this, but if we want to rename
> the things that the radix tree called tags to avoid the problem entirely,
> now is the time to do it.  Anybody got a Good Idea?

As Matthew pointed out, it is a good chance to rename one of them.


In addition to that, I am also looking forward to a better general
tagged pointer
implementation to wrap up operations for all these tags and restrict the
number of tag bits
at compile time. It is also useful to mark its usage and clean up these
magic masks
though the implementation could look a bit simple.

If you folks think the general tagged pointer is meaningless, please
ignore my words....
However according to my EROFS coding experience, code with different
kind of tagged
pointers by hand (directly use magic masks) will be in a mess, but it
also seems
unnecessary to introduce independent operations for each kind of tagged
pointers.


In the end, I also hope someone interested in this topic and thanks in
advance... :)


Thanks,
Gao Xiang

[-- Attachment #2: Type: text/html, Size: 11175 bytes --]

Re: Tagged pointers in the XArray

[Gao Xiang]

Hi,

On 2018/8/29 6:27, Matthew Wilcox wrote:
> I find myself caught between two traditions.
>
> On the one hand, the radix tree has been calling the page cache dirty &
> writeback bits "tags" for over a decade.
>
> On the other hand, using some of the bits _in a pointer_ as a tag has been
> common practice since at least the 1960s.
> https://en.wikipedia.org/wiki/Tagged_pointer and
> https://en.wikipedia.org/wiki/31-bit

Personally I think this topic makes sense. These two `tags' are totally
different actually.

> EROFS wants to use tagged pointers in the radix tree / xarray.  Right now,
> they're building them by hand, which is predictably grotty-looking.
> I think it's reasonable to provide this functionality as part of the
> XArray API, _but_ it's confusing to have two different things called tags.
>
> I've done my best to document my way around this, but if we want to rename
> the things that the radix tree called tags to avoid the problem entirely,
> now is the time to do it.  Anybody got a Good Idea?

As Matthew pointed out, it is a good chance to rename one of them.


In addition to that, I am also looking forward to a better general
tagged pointer
implementation to wrap up operations for all these tags and restrict the
number of tag bits
at compile time. It is also useful to mark its usage and clean up these
magic masks
though the implementation could look a bit simple.

If you folks think the general tagged pointer is meaningless, please
ignore my words....
However according to my EROFS coding experience, code with different
kind of tagged
pointers by hand (directly use magic masks) will be in a mess, but it
also seems
unnecessary to introduce independent operations for each kind of tagged
pointers.


In the end, I also hope someone interested in this topic and thanks in
advance... :)


Thanks,
Gao Xiang

Re: Tagged pointers in the XArray

[Matthew Wilcox]

On Tue, Aug 28, 2018 at 03:27:27PM -0700, Matthew Wilcox wrote:
> I find myself caught between two traditions.
> 
> On the one hand, the radix tree has been calling the page cache dirty &
> writeback bits "tags" for over a decade.
> 
> On the other hand, using some of the bits _in a pointer_ as a tag has been
> common practice since at least the 1960s.
> https://en.wikipedia.org/wiki/Tagged_pointer and
> https://en.wikipedia.org/wiki/31-bit
> 
> EROFS wants to use tagged pointers in the radix tree / xarray.  Right now,
> they're building them by hand, which is predictably grotty-looking.
> I think it's reasonable to provide this functionality as part of the
> XArray API, _but_ it's confusing to have two different things called tags.
> 
> I've done my best to document my way around this, but if we want to rename
> the things that the radix tree called tags to avoid the problem entirely,
> now is the time to do it.  Anybody got a Good Idea?

I have two ideas now.

First, we could rename radix tree tags to xarray marks.  That is,

xa_mark_t
xa_set_mark()
xas_clear_mark()
xas_for_each_marked() { }
xa_marked()
etc

Second, we could call the tagged pointers typed pointers.  That is,

void *xa_mk_type(void *p, unsigned int type);
void *xa_to_ptr(void *entry);
int xa_ptr_type(void *entry);

Any better ideas, or violent revulsion to either of the above ideas?