| Message ID | 20180828222727.GD11400@bombadil.infradead.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Tagged pointers in the XArray | expand |
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,
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_
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. :)
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
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?
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)
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>