[LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Allison Henderson]

Hi everyone!

Recently I have been working towards adding a new parent pointer patch 
set to xfs.  Briefly summarized, goal of the feature is to enable an 
application to quickly derive an inodes path from the mount point by 
storing information about the inodes parent(s) in an extended attribute. 
  Currently, I am aware of the intent to use the feature as part of an 
online scrub and repair feature.  Looking forward however, I would like 
to know about any other future coding intents that might make use of 
this feature.  For example, optimizing file system shrink or exportfs 
operations?  Are there certain interfaces or test cases that would be 
helpful to have?  I know the patch set has had a complicated history, so 
ideally being aware of how folks may go about using it may help to 
construct test cases to route out flaws sooner rather than later.

Thank you!

Allison Henderson

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Amir Goldstein]

On Wed, Jan 31, 2018 at 5:56 AM, Allison Henderson
<allison.henderson@oracle.com> wrote:
> Hi everyone!
>

Hi Allison!

> Recently I have been working towards adding a new parent pointer patch set
> to xfs.  Briefly summarized, goal of the feature is to enable an application
> to quickly derive an inodes path from the mount point by storing information
> about the inodes parent(s) in an extended attribute.  Currently, I am aware
> of the intent to use the feature as part of an online scrub and repair
> feature.  Looking forward however, I would like to know about any other
> future coding intents that might make use of this feature.  For example,
> optimizing file system shrink or exportfs operations?  Are there certain
> interfaces or test cases that would be helpful to have?

Parent pointers are going to be useful for exportfs reconnect operations.

The interesting test cases are decoding of directory file handles with
cold inode cache, where the decoded file handle is of a directory that
is nested inside a deep and wide directory tree.

Similarly, decoding a 'connectable' non-dir file handle for nfs export
of type 'subtree_check' also requires reconnecting the parent dir.

As far as I can tell, there are two relevant interfaces that could be improved
by parent pointers.

1. get_parent()+get_name()
These methods are used to get subdir's name in parent dir.
get_name() is not currently implemented in xfs.
get_name() has a default implementation of linear search on parent
directory entries.
parent pointers could improve this implementation from O(# parent entries)
to O(# parent xattrs), without the need to change the interface.
I advocated storing directory parent pointer also with a constant key (without
parent inode and offset), so that get_name() could be improved to O(1).

2. fh_to_parent()+get_name()
These methods are used to get a non-dir name in parent dir.
fh_to_parent() is implemented in xfs only if file handle was encoded as
'connectable' (FILEID_INO32_GEN_PARENT).
The problem with 'connectable' file handles from nfsd perspective is that
are not unique in some filesystems (xfs included).
With parent pointers, there is a potential to implement 'connectable' and
unique file handles, but that requires improving the interface.

If filesystem were to provide a parents iterator interface, something like:
get_acceptable_parent(child, acceptable, context)
then xfs could iterate inode parents and call the nfsd_acceptable() callback.
For filesystems that support get_acceptable_parent(), there is no need to
encode a 'connectable' non unique file handle.

I am not sure how much of a problem the 'subtree_check' and non-unique
file handle is for nfsd (CC nfsd folks for that), but I know I can make good use
of that in overlayfs, as well as with an optimized get_name() implementation.

Cheers,
Amir.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[J. Bruce Fields]

On Wed, Jan 31, 2018 at 09:34:52AM +0200, Amir Goldstein wrote:
> If filesystem were to provide a parents iterator interface, something like:
> get_acceptable_parent(child, acceptable, context)
> then xfs could iterate inode parents and call the nfsd_acceptable() callback.
> For filesystems that support get_acceptable_parent(), there is no need to
> encode a 'connectable' non unique file handle.
> 
> I am not sure how much of a problem the 'subtree_check' and non-unique
> file handle is for nfsd (CC nfsd folks for that), but I know I can make good use
> of that in overlayfs, as well as with an optimized get_name() implementation.

I hate subtree-checking and wish people would just stop trying to export
subtrees.

That said, anything that makes it less painful is probably good.

And, yes, the fact that filehandles can change when a file is renamed
across directories can be a problem for people using subtree checking.

--b.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Amir Goldstein]

On Wed, Jan 31, 2018 at 5:30 PM, J. Bruce Fields <bfields@fieldses.org> wrote:
> On Wed, Jan 31, 2018 at 09:34:52AM +0200, Amir Goldstein wrote:
>> If filesystem were to provide a parents iterator interface, something like:
>> get_acceptable_parent(child, acceptable, context)
>> then xfs could iterate inode parents and call the nfsd_acceptable() callback.
>> For filesystems that support get_acceptable_parent(), there is no need to
>> encode a 'connectable' non unique file handle.
>>
>> I am not sure how much of a problem the 'subtree_check' and non-unique
>> file handle is for nfsd (CC nfsd folks for that), but I know I can make good use
>> of that in overlayfs, as well as with an optimized get_name() implementation.
>
> I hate subtree-checking and wish people would just stop trying to export
> subtrees.
>
> That said, anything that makes it less painful is probably good.
>
> And, yes, the fact that filehandles can change when a file is renamed
> across directories can be a problem for people using subtree checking.
>

Let's talk about your feeling about 'subtree_check' ...

I hate security in general and wish that users would let us develop cool
stuff and stop worrying so much about their hopeless quest for secure
systems ;-)

That said, I don't believe they will listen to us cool reckless guys.
So despite your feeling, I am guessing that 'subtree_check' is here to stay
and that nfsd should strive to a solution of unique and connectable
file handles from filesystems that can support it.

The question is: is the interface I proposed going to be adequate for
'subtree_check' requirement. Meaning, with current 'subtree_check'
implementation, the decoded dentry is guarantied to have the same
parent that was used for encoding the non-dir, although it does not
guaranty to get the exact same alias. With the interface I proposed
get_acceptable_parent() could decode an alias that is not even
under the original parent directory. Do you see that as a problem?

Cheers,
Amir.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[J. Bruce Fields]

On Wed, Jan 31, 2018 at 06:09:43PM +0200, Amir Goldstein wrote:
> On Wed, Jan 31, 2018 at 5:30 PM, J. Bruce Fields <bfields@fieldses.org> wrote:
> > On Wed, Jan 31, 2018 at 09:34:52AM +0200, Amir Goldstein wrote:
> >> If filesystem were to provide a parents iterator interface, something like:
> >> get_acceptable_parent(child, acceptable, context)
> >> then xfs could iterate inode parents and call the nfsd_acceptable() callback.
> >> For filesystems that support get_acceptable_parent(), there is no need to
> >> encode a 'connectable' non unique file handle.
> >>
> >> I am not sure how much of a problem the 'subtree_check' and non-unique
> >> file handle is for nfsd (CC nfsd folks for that), but I know I can make good use
> >> of that in overlayfs, as well as with an optimized get_name() implementation.
> >
> > I hate subtree-checking and wish people would just stop trying to export
> > subtrees.
> >
> > That said, anything that makes it less painful is probably good.
> >
> > And, yes, the fact that filehandles can change when a file is renamed
> > across directories can be a problem for people using subtree checking.
> >
> 
> Let's talk about your feeling about 'subtree_check' ...
> 
> I hate security in general and wish that users would let us develop cool
> stuff and stop worrying so much about their hopeless quest for secure
> systems ;-)

I wasn't clear.  I agree that we need subtree-checking as long as we
allow exports of subtrees.  What I dislike is exporting subtrees in the
first place.  If you only export entire superblocks, enforcement of
export access becomes much simpler and more reliable.

> The question is: is the interface I proposed going to be adequate for
> 'subtree_check' requirement. Meaning, with current 'subtree_check'
> implementation, the decoded dentry is guarantied to have the same
> parent that was used for encoding the non-dir, although it does not
> guaranty to get the exact same alias. With the interface I proposed
> get_acceptable_parent() could decode an alias that is not even
> under the original parent directory. Do you see that as a problem?

That happens in the non-subtree-check case.  Filehandles really identify
inodes, not dentries.  We map them to dentries because we need to, but
the choice is fairly arbitrary.  As long as we're able to enforce
subtree_check, we're fine.  Iterating through the list of parents until
we find one that's under the export root sounds like it should
accomplish that.

--b.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Darrick J. Wong]

On Wed, Jan 31, 2018 at 09:34:52AM +0200, Amir Goldstein wrote:
> On Wed, Jan 31, 2018 at 5:56 AM, Allison Henderson
> <allison.henderson@oracle.com> wrote:
> > Hi everyone!
> >
> 
> Hi Allison!
> 
> > Recently I have been working towards adding a new parent pointer patch set
> > to xfs.  Briefly summarized, goal of the feature is to enable an application
> > to quickly derive an inodes path from the mount point by storing information
> > about the inodes parent(s) in an extended attribute.  Currently, I am aware
> > of the intent to use the feature as part of an online scrub and repair
> > feature.  Looking forward however, I would like to know about any other
> > future coding intents that might make use of this feature.  For example,
> > optimizing file system shrink or exportfs operations?  Are there certain
> > interfaces or test cases that would be helpful to have?
> 
> Parent pointers are going to be useful for exportfs reconnect operations.
> 
> The interesting test cases are decoding of directory file handles with
> cold inode cache, where the decoded file handle is of a directory that
> is nested inside a deep and wide directory tree.
> 
> Similarly, decoding a 'connectable' non-dir file handle for nfs export
> of type 'subtree_check' also requires reconnecting the parent dir.
> 
> As far as I can tell, there are two relevant interfaces that could be improved
> by parent pointers.
> 
> 1. get_parent()+get_name()
> These methods are used to get subdir's name in parent dir.
> get_name() is not currently implemented in xfs.
> get_name() has a default implementation of linear search on parent
> directory entries.
> parent pointers could improve this implementation from O(# parent entries)
> to O(# parent xattrs), without the need to change the interface.
> I advocated storing directory parent pointer also with a constant key (without
> parent inode and offset), so that get_name() could be improved to O(1).

I'm not sure what you mean by 'constant key' -- how can you have a
parent pointer without storing the parent inode?  Files can have
multiple directory parents, so I don't see how that would work in the
general case.

ATM the current proposal for xfs is to store this xattr in the system
namespace:

(parent_ino, parent_gen, parent_offset) -> dirent name

We need the long key to identify each parent pointer uniquely, and also
so that we can reconstruct directories.  Most files only have one
parent, so hopefully the performance will not be too awful, excepting
those hardlink farm backup systems.

> 2. fh_to_parent()+get_name()
> These methods are used to get a non-dir name in parent dir.
> fh_to_parent() is implemented in xfs only if file handle was encoded as
> 'connectable' (FILEID_INO32_GEN_PARENT).
> The problem with 'connectable' file handles from nfsd perspective is that
> are not unique in some filesystems (xfs included).
> With parent pointers, there is a potential to implement 'connectable' and
> unique file handles, but that requires improving the interface.
> 
> If filesystem were to provide a parents iterator interface, something like:
> get_acceptable_parent(child, acceptable, context)
> then xfs could iterate inode parents and call the nfsd_acceptable() callback.
> For filesystems that support get_acceptable_parent(), there is no need to
> encode a 'connectable' non unique file handle.

I think that could be done without too much effort.

--D

> I am not sure how much of a problem the 'subtree_check' and non-unique
> file handle is for nfsd (CC nfsd folks for that), but I know I can make good use
> of that in overlayfs, as well as with an optimized get_name() implementation.
> 
> Cheers,
> Amir.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Amir Goldstein]

On Wed, Jan 31, 2018 at 8:58 PM, Darrick J. Wong
<darrick.wong@oracle.com> wrote:
> On Wed, Jan 31, 2018 at 09:34:52AM +0200, Amir Goldstein wrote:
>> On Wed, Jan 31, 2018 at 5:56 AM, Allison Henderson
>> <allison.henderson@oracle.com> wrote:
>> > Hi everyone!
>> >
>>
>> Hi Allison!
>>
>> > Recently I have been working towards adding a new parent pointer patch set
>> > to xfs.  Briefly summarized, goal of the feature is to enable an application
>> > to quickly derive an inodes path from the mount point by storing information
>> > about the inodes parent(s) in an extended attribute.  Currently, I am aware
>> > of the intent to use the feature as part of an online scrub and repair
>> > feature.  Looking forward however, I would like to know about any other
>> > future coding intents that might make use of this feature.  For example,
>> > optimizing file system shrink or exportfs operations?  Are there certain
>> > interfaces or test cases that would be helpful to have?
>>
>> Parent pointers are going to be useful for exportfs reconnect operations.
>>
>> The interesting test cases are decoding of directory file handles with
>> cold inode cache, where the decoded file handle is of a directory that
>> is nested inside a deep and wide directory tree.
>>
>> Similarly, decoding a 'connectable' non-dir file handle for nfs export
>> of type 'subtree_check' also requires reconnecting the parent dir.
>>
>> As far as I can tell, there are two relevant interfaces that could be improved
>> by parent pointers.
>>
>> 1. get_parent()+get_name()
>> These methods are used to get subdir's name in parent dir.
>> get_name() is not currently implemented in xfs.
>> get_name() has a default implementation of linear search on parent
>> directory entries.
>> parent pointers could improve this implementation from O(# parent entries)
>> to O(# parent xattrs), without the need to change the interface.
>> I advocated storing directory parent pointer also with a constant key (without
>> parent inode and offset), so that get_name() could be improved to O(1).
>
> I'm not sure what you mean by 'constant key' -- how can you have a
> parent pointer without storing the parent inode?  Files can have
> multiple directory parents, so I don't see how that would work in the
> general case.
>
> ATM the current proposal for xfs is to store this xattr in the system
> namespace:
>
> (parent_ino, parent_gen, parent_offset) -> dirent name
>
> We need the long key to identify each parent pointer uniquely, and also
> so that we can reconstruct directories.  Most files only have one
> parent, so hopefully the performance will not be too awful, excepting
> those hardlink farm backup systems.
>

get_parent() is only called to get parent of a *directory* inode (i.e. "..").
The O(1) improvement is only for reconnecting directory file handle.
What I meant by storing the parent of a *directory* with 'constant key':

".." -> (parent_ino, parent_gen, parent_offset, dirent name)

On xfs list this idea was shot down because it special cases how
parent pointers are stored/read from directory inodes.
And I agree that for an optimization, benchmarks need to be presented.
Just putting all the options on the table for the discussion.

Cheers,
Amir.

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Darrick J. Wong]

On Tue, Jan 30, 2018 at 08:56:07PM -0700, Allison Henderson wrote:
> Hi everyone!
> 
> Recently I have been working towards adding a new parent pointer patch set
> to xfs.  Briefly summarized, goal of the feature is to enable an application
> to quickly derive an inodes path from the mount point by storing information
> about the inodes parent(s) in an extended attribute.  Currently, I am aware
> of the intent to use the feature as part of an online scrub and repair
> feature.

The online fs check use case is that we iterate every inode in the
filesystem from start to finish via file handles, and if we find some
damage it would be much more helpful to be able to report the file path
to userspace (e.g. "/foo/bar/file is corrupt" vs. "inode 325325 is
corrupt").

A second use is for xfs_repair and/or online fs repair -- instead of
dumping files orphaned by a destroyed directory in lost+found, we have
the possibility of rebuilding that directory by scanning all the inodes
to see which ones have parent pointers to the broken directory and then
rebuilding it from there.  Easy enough to do in xfs_repair, but will be
significantly more challenging to do it in the kernel <cough>.

The third use I can think of relates to past years' discussion of head
de-pop and pmem badblocks -- given a range of defective storage, we can
cross reference that with the reverse mapping to figure out which
(inode, offset) are affected, and try to use parent pointers to turn the
inode numbers into file paths.  We can also figure out if metadata is
affected and start a rebuild operation (though obviously if the rmap
data is affected then we're toast).

> Looking forward however, I would like to know about any other
> future coding intents that might make use of this feature.  For example,
> optimizing file system shrink or exportfs operations?  Are there certain

Not sure it'll help for fs shrink, but clearly the exportfs part of the
discussion has taken off. :)

> interfaces or test cases that would be helpful to have?  I know the patch
> set has had a complicated history, so ideally being aware of how folks may
> go about using it may help to construct test cases to route out flaws sooner
> rather than later.

I posted a userspace ioctl interface strawman here, implementing use
case #1 from above:
https://marc.info/?l=linux-xfs&m=151270557232472&w=2

Basic parent pointer iteration and path construction are provided in
userspace, bolted atop the in-kernel parent pointer iterator that
behaves similarly to the existing xfs file-handle attribute iterator.

--D

> 
> Thank you!
> 
> Allison Henderson

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Allison Henderson]

On 01/31/2018 11:46 AM, Darrick J. Wong wrote:
> On Tue, Jan 30, 2018 at 08:56:07PM -0700, Allison Henderson wrote:
>> Hi everyone!
>>
>> Recently I have been working towards adding a new parent pointer patch set
>> to xfs.  Briefly summarized, goal of the feature is to enable an application
>> to quickly derive an inodes path from the mount point by storing information
>> about the inodes parent(s) in an extended attribute.  Currently, I am aware
>> of the intent to use the feature as part of an online scrub and repair
>> feature.
> 
> The online fs check use case is that we iterate every inode in the
> filesystem from start to finish via file handles, and if we find some
> damage it would be much more helpful to be able to report the file path
> to userspace (e.g. "/foo/bar/file is corrupt" vs. "inode 325325 is
> corrupt").
> 
> A second use is for xfs_repair and/or online fs repair -- instead of
> dumping files orphaned by a destroyed directory in lost+found, we have
> the possibility of rebuilding that directory by scanning all the inodes
> to see which ones have parent pointers to the broken directory and then
> rebuilding it from there.  Easy enough to do in xfs_repair, but will be
> significantly more challenging to do it in the kernel <cough>.
> 
> The third use I can think of relates to past years' discussion of head
> de-pop and pmem badblocks -- given a range of defective storage, we can
> cross reference that with the reverse mapping to figure out which
> (inode, offset) are affected, and try to use parent pointers to turn the
> inode numbers into file paths.  We can also figure out if metadata is
> affected and start a rebuild operation (though obviously if the rmap
> data is affected then we're toast).
> 
>> Looking forward however, I would like to know about any other
>> future coding intents that might make use of this feature.  For example,
>> optimizing file system shrink or exportfs operations?  Are there certain
> 
> Not sure it'll help for fs shrink, but clearly the exportfs part of the
> discussion has taken off. :)
> 
>> interfaces or test cases that would be helpful to have?  I know the patch
>> set has had a complicated history, so ideally being aware of how folks may
>> go about using it may help to construct test cases to route out flaws sooner
>> rather than later.
> 
> I posted a userspace ioctl interface strawman here, implementing use
> case #1 from above:
> https://marc.info/?l=linux-xfs&m=151270557232472&w=2
> 
> Basic parent pointer iteration and path construction are provided in
> userspace, bolted atop the in-kernel parent pointer iterator that
> behaves similarly to the existing xfs file-handle attribute iterator.
> 
> --D

Yes, I think I have an earlier version of that patch in my tree already, 
so I'll make sure those work.  :-)

Thank you everyone for all your feedback, this gives me some more ideas 
of use cases I can run it through as it comes up.  Hoping to have 
another set of it out soon for people to look through.  Thanks all!

Allison

> 
>>
>> Thank you!
>>
>> Allison Henderson

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Dave Chinner]

On Wed, Jan 31, 2018 at 10:46:53AM -0800, Darrick J. Wong wrote:
> On Tue, Jan 30, 2018 at 08:56:07PM -0700, Allison Henderson wrote:
> > Hi everyone!
> > 
> > Recently I have been working towards adding a new parent pointer patch set
> > to xfs.  Briefly summarized, goal of the feature is to enable an application
> > to quickly derive an inodes path from the mount point by storing information
> > about the inodes parent(s) in an extended attribute.  Currently, I am aware
> > of the intent to use the feature as part of an online scrub and repair
> > feature.
> 
> The online fs check use case is that we iterate every inode in the
> filesystem from start to finish via file handles, and if we find some
> damage it would be much more helpful to be able to report the file path
> to userspace (e.g. "/foo/bar/file is corrupt" vs. "inode 325325 is
> corrupt").
> 
> A second use is for xfs_repair and/or online fs repair -- instead of
> dumping files orphaned by a destroyed directory in lost+found, we have
> the possibility of rebuilding that directory by scanning all the inodes
> to see which ones have parent pointers to the broken directory and then
> rebuilding it from there.  Easy enough to do in xfs_repair, but will be
> significantly more challenging to do it in the kernel <cough>.
> 
> The third use I can think of relates to past years' discussion of head
> de-pop and pmem badblocks -- given a range of defective storage, we can
> cross reference that with the reverse mapping to figure out which
> (inode, offset) are affected, and try to use parent pointers to turn the
> inode numbers into file paths.  We can also figure out if metadata is
> affected and start a rebuild operation (though obviously if the rmap
> data is affected then we're toast).
> 
> > Looking forward however, I would like to know about any other
> > future coding intents that might make use of this feature.  For example,
> > optimizing file system shrink or exportfs operations?  Are there certain
> 
> Not sure it'll help for fs shrink, but clearly the exportfs part of the
> discussion has taken off. :)

For shrink it would help identify the parent directories that need
to be modified when we move an inode. i.e. bulkstat to find inodes
that need moving, copy the data to a new inode, parent lookup to
find all the directories that need modifying, modify the dirents
to point to the new inode, delete old inode.

i.e. parent lookups are needed for an optimal 'bottom up' shrink
algorithm based on bulkstat and fsmap....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [LSF/MM TOPIC][LSF/MM ATTEND] Parent pointer future use cases

[Andreas Dilger]

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

On Jan 30, 2018, at 8:56 PM, Allison Henderson <allison.henderson@oracle.com> wrote:
> 
> Hi everyone!
> 
> Recently I have been working towards adding a new parent pointer patch set to xfs.  Briefly summarized, goal of the feature is to enable an application to quickly derive an inodes path from the mount point by storing information about the inodes parent(s) in an extended attribute.  Currently, I am aware of the intent to use the feature as part of an online scrub and repair feature.  Looking forward however, I would like to know about any other future coding intents that might make use of this feature.  For example, optimizing file system shrink or exportfs operations?  Are there certain interfaces or test cases that would be helpful to have?  I know the patch set has had a complicated history, so ideally being aware of how folks may go about using it may help to construct test cases to route out flaws sooner rather than later.

We have reverse inode->parent pointers in Lustre already, with a list of
{parent,name} tuples stored in a "link" xattr.  There is a userspace command
"lfs fid2path /mountpoint [FID]" that spits out a list of pathnames for a
filename relative to /mountpoint when the FID (inode number) is given.

Parent directory links are useful in several areas:
- better reporting in error messages (filename instead of inode number)
- generate pathnames for a hard-linked file for regular users, or tools like
  migration/rsync/tar so that they don't need to reverse engineer hard links
  by scanning the whole filesystem looking for matching inode numbers
- directory reconstruction in fsck, since each inode can use the xattr data
  re-attach itself to the namespace, including the directories themselves
  which contain a "link" xattr with their own name in the ".." directory
- being able to generate open file listings on the server from a list of
  FIDs (this is probably not useful for local filesystems)

Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]