Parent pointers

Parent pointers

[Allison Henderson]

Hi all,

I've been doing some digging on adding parent pointers to xfs and wanted 
to send a note to folks here to get peoples opinions on it.  I got in 
touch with Brian Foster not too long ago and he had some code partially 
done from about a year or so ago (looks like it has patches from Dave 
Chinner and Mark Tinguely as well).  So I am hoping to be able to use 
what we have so far to create something updated and finished out.  I am 
still pretty new to the xfs code, so at the moment I am still just going 
through old discussion threads, and reviewing the patches.  But for the 
most part I just wanted to see what people thought and get everyone on 
board with the idea.  Suggestions and feedback are much appreciated. 
Thank you!!

Allison Henderson

Re: Parent pointers

[Carlos Maiolino]

Hi,

On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
> Hi all,
> 
> I've been doing some digging on adding parent pointers to xfs and wanted to
> send a note to folks here to get peoples opinions on it.

Are you talking about parent pointers in the BTrees?



> I got in touch
> with Brian Foster not too long ago and he had some code partially done from
> about a year or so ago (looks like it has patches from Dave Chinner and Mark
> Tinguely as well).  So I am hoping to be able to use what we have so far to
> create something updated and finished out.  I am still pretty new to the xfs
> code, so at the moment I am still just going through old discussion threads,
> and reviewing the patches.  But for the most part I just wanted to see what
> people thought and get everyone on board with the idea.  Suggestions and
> feedback are much appreciated. Thank you!!
> 

It will be better if you can describe in more details if you have any specific
goal with this, and/or what kind of improvement you expect to have with it,
adding something new without a reason, is usually not well received.

Cheers

-- 
Carlos

Re: Parent pointers

[Eric Sandeen]

On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
> Hi,
> 
> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
>> Hi all,
>>
>> I've been doing some digging on adding parent pointers to xfs and wanted to
>> send a note to folks here to get peoples opinions on it.
> 
> Are you talking about parent pointers in the BTrees?
> 

No, see [RFC 00/17] RFC parent inode pointers. for example, from long
ago.

"Parent inode support allow XFS to quickly derive a file name and
path from the mount point. This can aid in directory/path policies
and can help relocate items during filesystem shrink."

It has a long and ... difficult history.

-Eric
 
>> I got in touch
>> with Brian Foster not too long ago and he had some code partially done from
>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
>> Tinguely as well).  So I am hoping to be able to use what we have so far to
>> create something updated and finished out.  I am still pretty new to the xfs
>> code, so at the moment I am still just going through old discussion threads,
>> and reviewing the patches.  But for the most part I just wanted to see what
>> people thought and get everyone on board with the idea.  Suggestions and
>> feedback are much appreciated. Thank you!!
>>
> 
> It will be better if you can describe in more details if you have any specific
> goal with this, and/or what kind of improvement you expect to have with it,
> adding something new without a reason, is usually not well received.
> 
> Cheers
> 

Re: Parent pointers

[Allison Henderson]

On 7/14/2017 7:04 AM, Eric Sandeen wrote:
>
>
> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
>> Hi,
>>
>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
>>> Hi all,
>>>
>>> I've been doing some digging on adding parent pointers to xfs and wanted to
>>> send a note to folks here to get peoples opinions on it.
>>
>> Are you talking about parent pointers in the BTrees?
>>
>
> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
> ago.
>
> "Parent inode support allow XFS to quickly derive a file name and
> path from the mount point. This can aid in directory/path policies
> and can help relocate items during filesystem shrink."
>
> It has a long and ... difficult history.
>
> -Eric
Right, so to expand on Eric's answer, it looks like Dave and Brian had 
been working on some improvements based on that set, but it's not quite 
finished yet.  The idea is that we add an extended attribute to keep 
track of the parents inode and generation, and also the child entries 
offset, and filename. So in this solution the EA is name={parent inode 
#, parent inode generation, dirent offset}, value={dirent filename}.

My goal at the moment is just to get it compiling again and finish out 
some of the sub routines that maintain it.  It looks like it hasn't had 
much attention in a while, so I wanted to let people know the direction 
I'm planning to move in before I get too far in.

Allison
>
>>> I got in touch
>>> with Brian Foster not too long ago and he had some code partially done from
>>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
>>> Tinguely as well).  So I am hoping to be able to use what we have so far to
>>> create something updated and finished out.  I am still pretty new to the xfs
>>> code, so at the moment I am still just going through old discussion threads,
>>> and reviewing the patches.  But for the most part I just wanted to see what
>>> people thought and get everyone on board with the idea.  Suggestions and
>>> feedback are much appreciated. Thank you!!
>>>
>>
>> It will be better if you can describe in more details if you have any specific
>> goal with this, and/or what kind of improvement you expect to have with it,
>> adding something new without a reason, is usually not well received.
>>
>> Cheers
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: Parent pointers

[Eric Sandeen]

On 07/14/2017 12:44 PM, Allison Henderson wrote:
> On 7/14/2017 7:04 AM, Eric Sandeen wrote:
>>
>>
>> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
>>> Hi,
>>>
>>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
>>>> Hi all,
>>>>
>>>> I've been doing some digging on adding parent pointers to xfs and wanted to
>>>> send a note to folks here to get peoples opinions on it.
>>>
>>> Are you talking about parent pointers in the BTrees?
>>>
>>
>> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
>> ago.
>>
>> "Parent inode support allow XFS to quickly derive a file name and
>> path from the mount point. This can aid in directory/path policies
>> and can help relocate items during filesystem shrink."
>>
>> It has a long and ... difficult history.
>>
>> -Eric
> Right, so to expand on Eric's answer, it looks like Dave and Brian had been working on some improvements based on that set, but it's not quite finished yet.  The idea is that we add an extended attribute to keep track of the parents inode and generation, and also the child entries offset, and filename. So in this solution the EA is name={parent inode #, parent inode generation, dirent offset}, value={dirent filename}.
> 
> My goal at the moment is just to get it compiling again and finish out some of the sub routines that maintain it.  It looks like it hasn't had much attention in a while, so I wanted to let people know the direction I'm planning to move in before I get too far in.

If you're forward-porting that 17-patch set from Mark, I'd suggest first reading Dave's
response to it - IIRC it amounted to a firm NAK.  it also highlights the complexity
of this undertaking, and may explain why nobody has gotten it done (yet) :)

-Eric
 
> Allison
>>
>>>> I got in touch
>>>> with Brian Foster not too long ago and he had some code partially done from
>>>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
>>>> Tinguely as well).  So I am hoping to be able to use what we have so far to
>>>> create something updated and finished out.  I am still pretty new to the xfs
>>>> code, so at the moment I am still just going through old discussion threads,
>>>> and reviewing the patches.  But for the most part I just wanted to see what
>>>> people thought and get everyone on board with the idea.  Suggestions and
>>>> feedback are much appreciated. Thank you!!
>>>>
>>>
>>> It will be better if you can describe in more details if you have any specific
>>> goal with this, and/or what kind of improvement you expect to have with it,
>>> adding something new without a reason, is usually not well received.
>>>
>>> Cheers
>>>
>> -- 
>> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
> -- 
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Parent pointers

[Brian Foster]

On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> On 07/14/2017 12:44 PM, Allison Henderson wrote:
> > On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> >>
> >>
> >> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
> >>> Hi,
> >>>
> >>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
> >>>> Hi all,
> >>>>
> >>>> I've been doing some digging on adding parent pointers to xfs and wanted to
> >>>> send a note to folks here to get peoples opinions on it.
> >>>
> >>> Are you talking about parent pointers in the BTrees?
> >>>
> >>
> >> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
> >> ago.
> >>
> >> "Parent inode support allow XFS to quickly derive a file name and
> >> path from the mount point. This can aid in directory/path policies
> >> and can help relocate items during filesystem shrink."
> >>
> >> It has a long and ... difficult history.
> >>
> >> -Eric
> > Right, so to expand on Eric's answer, it looks like Dave and Brian had been working on some improvements based on that set, but it's not quite finished yet.  The idea is that we add an extended attribute to keep track of the parents inode and generation, and also the child entries offset, and filename. So in this solution the EA is name={parent inode #, parent inode generation, dirent offset}, value={dirent filename}.
> > 
> > My goal at the moment is just to get it compiling again and finish out some of the sub routines that maintain it.  It looks like it hasn't had much attention in a while, so I wanted to let people know the direction I'm planning to move in before I get too far in.
> 
> If you're forward-porting that 17-patch set from Mark, I'd suggest first reading Dave's
> response to it - IIRC it amounted to a firm NAK.  it also highlights the complexity
> of this undertaking, and may explain why nobody has gotten it done (yet) :)
> 

The patches that came from me (to Allison) were last sent to me directly
from Dave. I know he had some objections to the original design, but my
understanding was that he had incorporated fixes for those issues in his
modifications to Mark's original series (such as the xattr format and
whatnot), but the series wasn't completely done yet in terms of
supporting all possible directory operations. (It's probably a good idea
to review that old thread anyways just to confirm, unless Dave catches
this and is able to chime in one way or the other.)

I basically just forwarded ported Dave's patches to more recent kernels
and added a couple minor fixes as I had combed through the existing
code. I never really got to adding anything of substance before Allison
volunteered to take over the series.

FWIW, I think there was some mention of porting some of the operations
over to the deferred ops infrastructure, but it's not clear to me off
the top of my head how important (or appropriate) that is. It's
something to keep in mind, in any event. IIRC there were also missing
Signed-off-by's required for some of Mark's original patches. IMO, the
best next step might be to just finish off the implementation as-is such
that we could have a fairly functional RFC to put on the list and hash
out whether there are in fact any remaining design hurdles, but others
might have a different opinion on that. :)

Brian

> -Eric
>  
> > Allison
> >>
> >>>> I got in touch
> >>>> with Brian Foster not too long ago and he had some code partially done from
> >>>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
> >>>> Tinguely as well).  So I am hoping to be able to use what we have so far to
> >>>> create something updated and finished out.  I am still pretty new to the xfs
> >>>> code, so at the moment I am still just going through old discussion threads,
> >>>> and reviewing the patches.  But for the most part I just wanted to see what
> >>>> people thought and get everyone on board with the idea.  Suggestions and
> >>>> feedback are much appreciated. Thank you!!
> >>>>
> >>>
> >>> It will be better if you can describe in more details if you have any specific
> >>> goal with this, and/or what kind of improvement you expect to have with it,
> >>> adding something new without a reason, is usually not well received.
> >>>
> >>> Cheers
> >>>
> >> -- 
> >> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> >> the body of a message to majordomo@vger.kernel.org
> >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >>
> > -- 
> > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Eric Sandeen]

On 07/14/2017 02:07 PM, Brian Foster wrote:
> On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
>> On 07/14/2017 12:44 PM, Allison Henderson wrote:
>>> On 7/14/2017 7:04 AM, Eric Sandeen wrote:
>>>>
>>>>
>>>> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
>>>>> Hi,
>>>>>
>>>>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
>>>>>> Hi all,
>>>>>>
>>>>>> I've been doing some digging on adding parent pointers to xfs and wanted to
>>>>>> send a note to folks here to get peoples opinions on it.
>>>>>
>>>>> Are you talking about parent pointers in the BTrees?
>>>>>
>>>>
>>>> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
>>>> ago.
>>>>
>>>> "Parent inode support allow XFS to quickly derive a file name and
>>>> path from the mount point. This can aid in directory/path policies
>>>> and can help relocate items during filesystem shrink."
>>>>
>>>> It has a long and ... difficult history.
>>>>
>>>> -Eric
>>> Right, so to expand on Eric's answer, it looks like Dave and Brian had been working on some improvements based on that set, but it's not quite finished yet.  The idea is that we add an extended attribute to keep track of the parents inode and generation, and also the child entries offset, and filename. So in this solution the EA is name={parent inode #, parent inode generation, dirent offset}, value={dirent filename}.
>>>
>>> My goal at the moment is just to get it compiling again and finish out some of the sub routines that maintain it.  It looks like it hasn't had much attention in a while, so I wanted to let people know the direction I'm planning to move in before I get too far in.
>>
>> If you're forward-porting that 17-patch set from Mark, I'd suggest first reading Dave's
>> response to it - IIRC it amounted to a firm NAK.  it also highlights the complexity
>> of this undertaking, and may explain why nobody has gotten it done (yet) :)
>>
> 
> The patches that came from me (to Allison) were last sent to me directly
> from Dave. 

Oh, ok.  I didn't know we were talking about off-list patches, sorry if I
missed that.  I thought Allison was looking at the 17-patch series on the list,
and wanted to make sure this wouldn't be a false start.  :)

Thanks,
-Eric

Re: Parent pointers

[Darrick J. Wong]

On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> > On 07/14/2017 12:44 PM, Allison Henderson wrote:
> > > On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> > >>
> > >>
> > >> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
> > >>> Hi,
> > >>>
> > >>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
> > >>>> Hi all,
> > >>>>
> > >>>> I've been doing some digging on adding parent pointers to xfs and wanted to
> > >>>> send a note to folks here to get peoples opinions on it.
> > >>>
> > >>> Are you talking about parent pointers in the BTrees?
> > >>>
> > >>
> > >> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
> > >> ago.
> > >>
> > >> "Parent inode support allow XFS to quickly derive a file name and
> > >> path from the mount point. This can aid in directory/path policies
> > >> and can help relocate items during filesystem shrink."
> > >>
> > >> It has a long and ... difficult history.
> > >>
> > >> -Eric

Woot, time to dive in. :)

> > > Right, so to expand on Eric's answer, it looks like Dave and Brian
> > > had been working on some improvements based on that set, but it's
> > > not quite finished yet.  The idea is that we add an extended
> > > attribute to keep track of the parents inode and generation, and

Well, a lot of attributes, in the case of multiply hardlinked files.
One concern I have is that since a file can be hardlinked 2^32 times and
path components have a maximum length of 255 bytes, we'll have to be
careful about not overflowing di_anextents as a part of making a
potentially huge attribute tree.

> > > also the child entries offset, and filename. So in this solution
> > > the EA is name={parent inode #, parent inode generation, dirent
> > > offset}, value={dirent filename}.

This (the disk format) is probably the most important part to get
settled.  FWIW, I've recaptured three of the previous discussions of
parent pointers -- Lachlan McIlroy's code dump in 2009[1], Mark
Tinguely's 2013 attempt[2] and 2014 attempt[3] at discussing patches.
For those of you following along at home, the gmane link mentioned in
[3] is the link at [1].

[1] http://oss.sgi.com/archives/xfs/2009-01/msg01068.html
[2] http://oss.sgi.com/archives/xfs/2013-04/msg00214.html
[3] https://www.spinics.net/lists/xfs/msg25175.html

The latest round of parent pointer patches is (I think) in the form of
an off-list patchset that Brian (and now Allison) are cleaning up for
reposting, which hopefully happens soon because I feel rather ill at
ease discussing off-list code that lacks S-o-b's.

Anyway, the current proposal is to create a new xattr namespace
(ATTR_PARENT) and to fill it with (parent_ino, parent_gen,
dirent_offset) => (dirent name) attributes:

struct xfs_parent_name_rec {
	__be64	p_ino;
	__be32	p_gen;
	__be32	p_diroffset;
};

p_diroffset is really a directory datapointer, not a raw byte offset.

We also have an incore data structure of:

struct xfs_parent_name_irec {
	__uint64_t	p_ino;
	__uint32_t	p_gen;
	__uint32_t	p_diroffset;
	const char	*p_name;
	__uint32_t	p_namelen;
};

I think p_ino ought to be xfs_ino_t and not uint64_t, and p_diroffset
ought to be xfs_dir2_dataptr_t instead of uint32_t.

> > > My goal at the moment is just to get it compiling again and finish
> > > out some of the sub routines that maintain it.  It looks like it
> > > hasn't had much attention in a while, so I wanted to let people
> > > know the direction I'm planning to move in before I get too far
> > > in.

<nod>

> > If you're forward-porting that 17-patch set from Mark, I'd suggest
> > first reading Dave's response to it - IIRC it amounted to a firm
> > NAK.  it also highlights the complexity of this undertaking, and may
> > explain why nobody has gotten it done (yet) :)
> > 
> 
> The patches that came from me (to Allison) were last sent to me directly
> from Dave. I know he had some objections to the original design, but my
> understanding was that he had incorporated fixes for those issues in his
> modifications to Mark's original series (such as the xattr format and

>From what I can tell, he seems to have taken Mark's patches to pass dir
offsets back from the dirent manipulation functions and then started
writing a simple implementation of stuffing the attrs into the attr
tree.

> whatnot), but the series wasn't completely done yet in terms of
> supporting all possible directory operations. (It's probably a good idea
> to review that old thread anyways just to confirm, unless Dave catches
> this and is able to chime in one way or the other.)

(Or jump in the fray out once he's back from sabbatical.)

> I basically just forwarded ported Dave's patches to more recent kernels
> and added a couple minor fixes as I had combed through the existing
> code. I never really got to adding anything of substance before Allison
> volunteered to take over the series.
> 
> FWIW, I think there was some mention of porting some of the operations
> over to the deferred ops infrastructure, but it's not clear to me off
> the top of my head how important (or appropriate) that is.

Most of the users of xfs_trans_roll seem to be buried in the xattr code.
For example, _attr_set can end up rolling a transaction after converting
an attr fork from short format to leaf format before retrying the attr
add operation, but we don't use log redo items (er, defer_ops items) to
make sure log recovery will restart the attr add operation if we crash
before the final _trans_commit after calling _attr_{leaf,node}_addname.

In the case of a regular xattr set operation this wouldn't have been a
big deal because the fsetxattr call wouldn't have returned, so all the
user could possibly see is an inode with a perhaps unnecessarily large
xattr fork.  Now that we need to set xattrs in the same transaction
chain as a directory operation, it becomes very important that log
recovery gain the ability to resume an xattr add operation no matter
where the log stopped.  Creating a directory can become this longwinded
pile of updates:

- Allocate directory block, map into data fork, chain rmap update, add
  directory entry, chain pptr update;
- Add rmap entry for new directory block (more chaining to fix
  freelist), finish first rmap update;
- Allocate xattr block for short->leaf conversion, map into attr fork,
  chain rmap update; chain xattr add operation;
- Add rmap entry for new xattr block (more chaining to fix freelist),
  finish second rmap update;
- Add xattr entry to file, finish xattr add operation;
- Finish pptr update.

Basically, I think someone's going to have to go audit all the uses of
xfs_trans_roll in the attr code to figure out which operations need redo
items, and how to cram everything toegether into a single xfs_defer_ops,
rather than sprinkling them around the attr code like we do now, because
redo items cannot be deferred from one defer_ops to another.

> It's something to keep in mind, in any event. IIRC there were also
> missing Signed-off-by's required for some of Mark's original patches.

That's also a problem; unless someone can get Mark to supply them, we
probably have to get someone to rewrite them.  At a bare minimum I think
we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare
uint32_t.

> IMO, the best next step might be to just finish off the implementation
> as-is such that we could have a fairly functional RFC to put on the
> list and hash out whether there are in fact any remaining design
> hurdles, but others might have a different opinion on that. :)

Agreed.

> Brian
> 
> > -Eric
> >  
> > > Allison
> > >>
> > >>>> I got in touch
> > >>>> with Brian Foster not too long ago and he had some code partially done from
> > >>>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
> > >>>> Tinguely as well).  So I am hoping to be able to use what we have so far to
> > >>>> create something updated and finished out.  I am still pretty new to the xfs
> > >>>> code, so at the moment I am still just going through old discussion threads,
> > >>>> and reviewing the patches.  But for the most part I just wanted to see what
> > >>>> people thought and get everyone on board with the idea.  Suggestions and
> > >>>> feedback are much appreciated. Thank you!!
> > >>>>
> > >>>
> > >>> It will be better if you can describe in more details if you have any specific
> > >>> goal with this, and/or what kind of improvement you expect to have with it,
> > >>> adding something new without a reason, is usually not well received.
> > >>>
> > >>> Cheers
> > >>>
> > >> -- 
> > >> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > >> the body of a message to majordomo@vger.kernel.org
> > >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > >>
> > > -- 
> > > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > > 
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: Parent pointers

[Tinguely, Mark]

-----Original Message-----
From: linux-xfs-owner@vger.kernel.org [mailto:linux-xfs-owner@vger.kernel.org] On Behalf Of Darrick J. Wong
Sent: Friday, July 14, 2017 5:47 PM
To: Brian Foster <bfoster@redhat.com>
Cc: Eric Sandeen <sandeen@sandeen.net>; Allison Henderson <allison.henderson@oracle.com>; cmaiolino@redhat.com; linux-xfs@vger.kernel.org
Subject: Re: Parent pointers

On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> > On 07/14/2017 12:44 PM, Allison Henderson wrote:
> > > On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> > >>

<parent inode pointers returneth messages deleted>

> It's something to keep in mind, in any event. IIRC there were also 
> missing Signed-off-by's required for some of Mark's original patches.

That's also a problem; unless someone can get Mark to supply them, we probably have to get someone to rewrite them.  At a bare minimum I think we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare uint32_t.

Me says:
The community can do what they want.  If you want to start with that code, permission for S-O-B: me (snickers at the pun)

> IMO, the best next step might be to just finish off the implementation 
> as-is such that we could have a fairly functional RFC to put on the 
> list and hash out whether there are in fact any remaining design 
> hurdles, but others might have a different opinion on that. :)

No one is asking me but I will add, IMO (definitely disclaiming the storage group and HPE):
 the PIP costs outweigh the benefits.
   Adding the redundant filename for recovery and an occasional output of the path pushes the cost to be *totally unreasonable*.
    If I had a say, I don't and won't, I would NAK any implementation that included it.
 Implementing with extended attributes is the wrong, wrong, wrong choice. It was done for hysterical :) reasons and even that appeasement bit me in the asterisk.

Good luck.

--Mark Tinguely 
  not representing anyone but myself.

Re: Parent pointers

[Brian Foster]

On Fri, Jul 14, 2017 at 03:46:58PM -0700, Darrick J. Wong wrote:
> On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> > On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> > > On 07/14/2017 12:44 PM, Allison Henderson wrote:
> > > > On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> > > >>
> > > >>
> > > >> On 07/14/2017 03:50 AM, Carlos Maiolino wrote:
> > > >>> Hi,
> > > >>>
> > > >>> On Thu, Jul 13, 2017 at 04:25:25PM -0700, Allison Henderson wrote:
> > > >>>> Hi all,
> > > >>>>
> > > >>>> I've been doing some digging on adding parent pointers to xfs and wanted to
> > > >>>> send a note to folks here to get peoples opinions on it.
> > > >>>
> > > >>> Are you talking about parent pointers in the BTrees?
> > > >>>
> > > >>
> > > >> No, see [RFC 00/17] RFC parent inode pointers. for example, from long
> > > >> ago.
> > > >>
> > > >> "Parent inode support allow XFS to quickly derive a file name and
> > > >> path from the mount point. This can aid in directory/path policies
> > > >> and can help relocate items during filesystem shrink."
> > > >>
> > > >> It has a long and ... difficult history.
> > > >>
> > > >> -Eric
> 
> Woot, time to dive in. :)
> 
> > > > Right, so to expand on Eric's answer, it looks like Dave and Brian
> > > > had been working on some improvements based on that set, but it's
> > > > not quite finished yet.  The idea is that we add an extended
> > > > attribute to keep track of the parents inode and generation, and
> 
> Well, a lot of attributes, in the case of multiply hardlinked files.
> One concern I have is that since a file can be hardlinked 2^32 times and
> path components have a maximum length of 255 bytes, we'll have to be
> careful about not overflowing di_anextents as a part of making a
> potentially huge attribute tree.
> 
> > > > also the child entries offset, and filename. So in this solution
> > > > the EA is name={parent inode #, parent inode generation, dirent
> > > > offset}, value={dirent filename}.
> 
> This (the disk format) is probably the most important part to get
> settled.  FWIW, I've recaptured three of the previous discussions of
> parent pointers -- Lachlan McIlroy's code dump in 2009[1], Mark
> Tinguely's 2013 attempt[2] and 2014 attempt[3] at discussing patches.
> For those of you following along at home, the gmane link mentioned in
> [3] is the link at [1].
> 
> [1] http://oss.sgi.com/archives/xfs/2009-01/msg01068.html
> [2] http://oss.sgi.com/archives/xfs/2013-04/msg00214.html
> [3] https://www.spinics.net/lists/xfs/msg25175.html
> 
> The latest round of parent pointer patches is (I think) in the form of
> an off-list patchset that Brian (and now Allison) are cleaning up for
> reposting, which hopefully happens soon because I feel rather ill at
> ease discussing off-list code that lacks S-o-b's.
> 
> Anyway, the current proposal is to create a new xattr namespace
> (ATTR_PARENT) and to fill it with (parent_ino, parent_gen,
> dirent_offset) => (dirent name) attributes:
> 
> struct xfs_parent_name_rec {
> 	__be64	p_ino;
> 	__be32	p_gen;
> 	__be32	p_diroffset;
> };
> 
> p_diroffset is really a directory datapointer, not a raw byte offset.
> 
> We also have an incore data structure of:
> 
> struct xfs_parent_name_irec {
> 	__uint64_t	p_ino;
> 	__uint32_t	p_gen;
> 	__uint32_t	p_diroffset;
> 	const char	*p_name;
> 	__uint32_t	p_namelen;
> };
> 
> I think p_ino ought to be xfs_ino_t and not uint64_t, and p_diroffset
> ought to be xfs_dir2_dataptr_t instead of uint32_t.
> 
> > > > My goal at the moment is just to get it compiling again and finish
> > > > out some of the sub routines that maintain it.  It looks like it
> > > > hasn't had much attention in a while, so I wanted to let people
> > > > know the direction I'm planning to move in before I get too far
> > > > in.
> 
> <nod>
> 
> > > If you're forward-porting that 17-patch set from Mark, I'd suggest
> > > first reading Dave's response to it - IIRC it amounted to a firm
> > > NAK.  it also highlights the complexity of this undertaking, and may
> > > explain why nobody has gotten it done (yet) :)
> > > 
> > 
> > The patches that came from me (to Allison) were last sent to me directly
> > from Dave. I know he had some objections to the original design, but my
> > understanding was that he had incorporated fixes for those issues in his
> > modifications to Mark's original series (such as the xattr format and
> 
> From what I can tell, he seems to have taken Mark's patches to pass dir
> offsets back from the dirent manipulation functions and then started
> writing a simple implementation of stuffing the attrs into the attr
> tree.
> 
> > whatnot), but the series wasn't completely done yet in terms of
> > supporting all possible directory operations. (It's probably a good idea
> > to review that old thread anyways just to confirm, unless Dave catches
> > this and is able to chime in one way or the other.)
> 
> (Or jump in the fray out once he's back from sabbatical.)
> 
> > I basically just forwarded ported Dave's patches to more recent kernels
> > and added a couple minor fixes as I had combed through the existing
> > code. I never really got to adding anything of substance before Allison
> > volunteered to take over the series.
> > 
> > FWIW, I think there was some mention of porting some of the operations
> > over to the deferred ops infrastructure, but it's not clear to me off
> > the top of my head how important (or appropriate) that is.
> 
> Most of the users of xfs_trans_roll seem to be buried in the xattr code.
> For example, _attr_set can end up rolling a transaction after converting
> an attr fork from short format to leaf format before retrying the attr
> add operation, but we don't use log redo items (er, defer_ops items) to
> make sure log recovery will restart the attr add operation if we crash
> before the final _trans_commit after calling _attr_{leaf,node}_addname.
> 
> In the case of a regular xattr set operation this wouldn't have been a
> big deal because the fsetxattr call wouldn't have returned, so all the
> user could possibly see is an inode with a perhaps unnecessarily large
> xattr fork.  Now that we need to set xattrs in the same transaction
> chain as a directory operation, it becomes very important that log
> recovery gain the ability to resume an xattr add operation no matter
> where the log stopped.  Creating a directory can become this longwinded
> pile of updates:
> 

Ok, thanks for the summary. So we have some transaction ordering down in
the xattr code that might no longer be sufficient to provide atomicity
in the context of parent pointers (via directory operations). I see that
the current patch series increases the transaction size to accommodate
parent pointers, but that doesn't help us deal with those situations
where the transaction is rolled into a new one.

> - Allocate directory block, map into data fork, chain rmap update, add
>   directory entry, chain pptr update;
> - Add rmap entry for new directory block (more chaining to fix
>   freelist), finish first rmap update;
> - Allocate xattr block for short->leaf conversion, map into attr fork,
>   chain rmap update; chain xattr add operation;
> - Add rmap entry for new xattr block (more chaining to fix freelist),
>   finish second rmap update;
> - Add xattr entry to file, finish xattr add operation;
> - Finish pptr update.
> 
> Basically, I think someone's going to have to go audit all the uses of
> xfs_trans_roll in the attr code to figure out which operations need redo
> items, and how to cram everything toegether into a single xfs_defer_ops,
> rather than sprinkling them around the attr code like we do now, because
> redo items cannot be deferred from one defer_ops to another.
> 

Indeed. I wonder whether we may have other options here as well, such as
a higher level reordering/refactoring or allocation of necessary blocks
in the directory code. I.e., I'm handwaving here, but perhaps following
a model similar to how inode chunks are allocated in a separate
transaction or directory operations are allowed in situations where an
allocation is not (to limit deferring to where it is only necessary, for
example). This would all be easier to reason about (IMO) with a
functionally complete RFC series, though.

Brian

> > It's something to keep in mind, in any event. IIRC there were also
> > missing Signed-off-by's required for some of Mark's original patches.
> 
> That's also a problem; unless someone can get Mark to supply them, we
> probably have to get someone to rewrite them.  At a bare minimum I think
> we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare
> uint32_t.
> 
> > IMO, the best next step might be to just finish off the implementation
> > as-is such that we could have a fairly functional RFC to put on the
> > list and hash out whether there are in fact any remaining design
> > hurdles, but others might have a different opinion on that. :)
> 
> Agreed.
> 
> > Brian
> > 
> > > -Eric
> > >  
> > > > Allison
> > > >>
> > > >>>> I got in touch
> > > >>>> with Brian Foster not too long ago and he had some code partially done from
> > > >>>> about a year or so ago (looks like it has patches from Dave Chinner and Mark
> > > >>>> Tinguely as well).  So I am hoping to be able to use what we have so far to
> > > >>>> create something updated and finished out.  I am still pretty new to the xfs
> > > >>>> code, so at the moment I am still just going through old discussion threads,
> > > >>>> and reviewing the patches.  But for the most part I just wanted to see what
> > > >>>> people thought and get everyone on board with the idea.  Suggestions and
> > > >>>> feedback are much appreciated. Thank you!!
> > > >>>>
> > > >>>
> > > >>> It will be better if you can describe in more details if you have any specific
> > > >>> goal with this, and/or what kind of improvement you expect to have with it,
> > > >>> adding something new without a reason, is usually not well received.
> > > >>>
> > > >>> Cheers
> > > >>>
> > > >> -- 
> > > >> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > > >> the body of a message to majordomo@vger.kernel.org
> > > >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > > >>
> > > > -- 
> > > > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > > > the body of a message to majordomo@vger.kernel.org
> > > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > > > 
> > > --
> > > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Brian Foster]

On Sat, Jul 15, 2017 at 04:36:27PM +0000, Tinguely, Mark wrote:
> -----Original Message-----
> From: linux-xfs-owner@vger.kernel.org [mailto:linux-xfs-owner@vger.kernel.org] On Behalf Of Darrick J. Wong
> Sent: Friday, July 14, 2017 5:47 PM
> To: Brian Foster <bfoster@redhat.com>
> Cc: Eric Sandeen <sandeen@sandeen.net>; Allison Henderson <allison.henderson@oracle.com>; cmaiolino@redhat.com; linux-xfs@vger.kernel.org
> Subject: Re: Parent pointers
> 
> On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> > On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> > > On 07/14/2017 12:44 PM, Allison Henderson wrote:
> > > > On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> > > >>
> 
> <parent inode pointers returneth messages deleted>
> 
> > It's something to keep in mind, in any event. IIRC there were also 
> > missing Signed-off-by's required for some of Mark's original patches.
> 
> That's also a problem; unless someone can get Mark to supply them, we probably have to get someone to rewrite them.  At a bare minimum I think we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare uint32_t.
> 
> Me says:
> The community can do what they want.  If you want to start with that code, permission for S-O-B: me (snickers at the pun)
> 

Thanks Mark. I guess we can add Mark's Signed-off-by to those patches he
originally authored and that solves that problem. :)

> > IMO, the best next step might be to just finish off the implementation 
> > as-is such that we could have a fairly functional RFC to put on the 
> > list and hash out whether there are in fact any remaining design 
> > hurdles, but others might have a different opinion on that. :)
> 
> No one is asking me but I will add, IMO (definitely disclaiming the storage group and HPE):
>  the PIP costs outweigh the benefits.
>    Adding the redundant filename for recovery and an occasional output of the path pushes the cost to be *totally unreasonable*.
>     If I had a say, I don't and won't, I would NAK any implementation that included it.
>  Implementing with extended attributes is the wrong, wrong, wrong choice. It was done for hysterical :) reasons and even that appeasement bit me in the asterisk.
> 

Could you elaborate on this a bit? I haven't gone through all of the old
discussions and it's been a while since I've even reviewed the recent
code, but on a quick look at the links Darrick posted, it appears the
old implementation incorporated the "first" parent pointer direct in the
inode with a fallback to xattrs for inodes with multiple parents whereas
the updated implementation uses xattrs outright (and as a result is able
to incorporate the dentry name in the xattr). Is that an accurate
summary?

If so, is the performance concern really the use of xattrs or the fact
that the name is included (or some combination of both)? For example,
would you consider a situation where pp's are entirely isolated to
shortform xattrs much worse than the direct pp approach? It seems to me
that the inline approach could still be considered as an optimization
(i.e., maybe an incore cache) if performance does prove to be a problem.
Maybe we could also consider something where (somehow, handwaving again
;) some number of pp xattrs are always shortform and thus remain within
the inode.

IOW, I think performance is a valid concern, but this should probably
1.) follow correctness and 2.) be more dictated by testing (another
really good reason to try and finish off the current rfc IMO) where we
can consider various, potentially problematic situations. We're bound to
have workloads where pretty much every file is hardlinked more than once
(think glusterfs), for example.

Brian

> Good luck.
> 
> --Mark Tinguely 
>   not representing anyone but myself.
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Mark Tinguely]

On 07/17/2017 09:49 AM, Brian Foster wrote:
> On Sat, Jul 15, 2017 at 04:36:27PM +0000, Tinguely, Mark wrote:
>> -----Original Message-----
>> From: linux-xfs-owner@vger.kernel.org [mailto:linux-xfs-owner@vger.kernel.org] On Behalf Of Darrick J. Wong
>> Sent: Friday, July 14, 2017 5:47 PM
>> To: Brian Foster <bfoster@redhat.com>
>> Cc: Eric Sandeen <sandeen@sandeen.net>; Allison Henderson <allison.henderson@oracle.com>; cmaiolino@redhat.com; linux-xfs@vger.kernel.org
>> Subject: Re: Parent pointers
>>
>> On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
>>> On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
>>>> On 07/14/2017 12:44 PM, Allison Henderson wrote:
>>>>> On 7/14/2017 7:04 AM, Eric Sandeen wrote:
>> <parent inode pointers returneth messages deleted>
>>
>>> It's something to keep in mind, in any event. IIRC there were also
>>> missing Signed-off-by's required for some of Mark's original patches.
>> That's also a problem; unless someone can get Mark to supply them, we probably have to get someone to rewrite them.  At a bare minimum I think we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare uint32_t.
>>
>> Me says:
>> The community can do what they want.  If you want to start with that code, permission for S-O-B: me (snickers at the pun)
>>
> Thanks Mark. I guess we can add Mark's Signed-off-by to those patches he
> originally authored and that solves that problem. :)
>
>>> IMO, the best next step might be to just finish off the implementation
>>> as-is such that we could have a fairly functional RFC to put on the
>>> list and hash out whether there are in fact any remaining design
>>> hurdles, but others might have a different opinion on that. :)
>> No one is asking me but I will add, IMO (definitely disclaiming the storage group and HPE):
>>   the PIP costs outweigh the benefits.
>>     Adding the redundant filename for recovery and an occasional output of the path pushes the cost to be *totally unreasonable*.
>>      If I had a say, I don't and won't, I would NAK any implementation that included it.
>>   Implementing with extended attributes is the wrong, wrong, wrong choice. It was done for hysterical :) reasons and even that appeasement bit me in the asterisk.
>>
> Could you elaborate on this a bit? I haven't gone through all of the old
> discussions and it's been a while since I've even reviewed the recent
> code, but on a quick look at the links Darrick posted, it appears the
> old implementation incorporated the "first" parent pointer direct in the
> inode with a fallback to xattrs for inodes with multiple parents whereas
> the updated implementation uses xattrs outright (and as a result is able
> to incorporate the dentry name in the xattr). Is that an accurate
> summary?
>
> If so, is the performance concern really the use of xattrs or the fact
> that the name is included (or some combination of both)? For example,
> would you consider a situation where pp's are entirely isolated to
> shortform xattrs much worse than the direct pp approach? It seems to me
> that the inline approach could still be considered as an optimization
> (i.e., maybe an incore cache) if performance does prove to be a problem.
> Maybe we could also consider something where (somehow, handwaving again
> ;) some number of pp xattrs are always shortform and thus remain within
> the inode.
I disagree with both saving the name and using xattrs.

>
> IOW, I think performance is a valid concern, but this should probably
> 1.) follow correctness and 2.) be more dictated by testing (another
> really good reason to try and finish off the current rfc IMO) where we
> can consider various, potentially problematic situations. We're bound to
> have workloads where pretty much every file is hardlinked more than once
> (think glusterfs), for example.
>
> Brian
>
OMG! Sigh ...
>> Good luck.
x2
>>
>> --Mark Tinguely
>>    not representing anyone but myself.
>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Dave Chinner]

On Mon, Jul 17, 2017 at 10:48:16AM -0400, Brian Foster wrote:
> On Fri, Jul 14, 2017 at 03:46:58PM -0700, Darrick J. Wong wrote:
> > On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> > From what I can tell, he seems to have taken Mark's patches to pass dir
> > offsets back from the dirent manipulation functions and then started
> > writing a simple implementation of stuffing the attrs into the attr
> > tree.

Yup, that's the idea.

> > > FWIW, I think there was some mention of porting some of the operations
> > > over to the deferred ops infrastructure, but it's not clear to me off
> > > the top of my head how important (or appropriate) that is.
> > 
> > Most of the users of xfs_trans_roll seem to be buried in the xattr code.
> > For example, _attr_set can end up rolling a transaction after converting
> > an attr fork from short format to leaf format before retrying the attr
> > add operation, but we don't use log redo items (er, defer_ops items) to
> > make sure log recovery will restart the attr add operation if we crash
> > before the final _trans_commit after calling _attr_{leaf,node}_addname.
> > 
> > In the case of a regular xattr set operation this wouldn't have been a
> > big deal because the fsetxattr call wouldn't have returned, so all the
> > user could possibly see is an inode with a perhaps unnecessarily large
> > xattr fork.  Now that we need to set xattrs in the same transaction
> > chain as a directory operation, it becomes very important that log
> > recovery gain the ability to resume an xattr add operation no matter
> > where the log stopped.  Creating a directory can become this longwinded
> > pile of updates:
> > 
> 
> Ok, thanks for the summary. So we have some transaction ordering down in
> the xattr code that might no longer be sufficient to provide atomicity
> in the context of parent pointers (via directory operations).

We already have xattr operations that are not atomic with directory
entry creation - security xattrs (default ACL, etc). This can mean
that after a crash and recovery, we have a newly created file
without any security xattr on it.

This is a long standing problem - it bites SGI's HSM (DMF) all the
time, so rather than fixing the problem 10+ years ago, they added a
post-boot inode scan (via bulkstat) to find inodes that didn't have
a DMF xattr.

The original parent pointer patchset also had this problem the
moment xattrs were required (i.e. first hardlink) - the creation of
the pp xattr was not atomic with the dirent creation. To solve this
problem, I started by moving the xattr creation into the transaction
context of the dirent.

> I see that
> the current patch series increases the transaction size to accommodate
> parent pointers, but that doesn't help us deal with those situations
> where the transaction is rolled into a new one.

Right, I hadn't got that far. The plan effective was to get a proof
of concept running with the xattr creation within the directory
creation xact context and get that working, knowing that it still
wasn't properly atomic. This was done before we had deferred ops,
and my thinking at the time was to add an intent/done pair of ops
to tell recovery it needed to add an xattr to the dirent once the
xattr was inside the dirent context. i.e.

	- move xattr inside dirent ctx
	- add pp intent
	- roll transaction
	- add pp xattr
	- roll final xattr transaction rather than commit
	- add pp done
	- commit dir ctx transaction.

This doesn't help us with security context xattrs, though, so
when deferred ops came along, it made much more sense to me to
make the adding of an xattr a deferred op so we could use the same
mechanism for adding all the required xattrs to the inode atomically
and so have a mechanism for recovery to replay them appropriately.

> > - Allocate directory block, map into data fork, chain rmap update, add
> >   directory entry, chain pptr update;
> > - Add rmap entry for new directory block (more chaining to fix
> >   freelist), finish first rmap update;
> > - Allocate xattr block for short->leaf conversion, map into attr fork,
> >   chain rmap update; chain xattr add operation;
> > - Add rmap entry for new xattr block (more chaining to fix freelist),
> >   finish second rmap update;
> > - Add xattr entry to file, finish xattr add operation;
> > - Finish pptr update.
> > 
> > Basically, I think someone's going to have to go audit all the uses of
> > xfs_trans_roll in the attr code to figure out which operations need redo
> > items, and how to cram everything toegether into a single xfs_defer_ops,
> > rather than sprinkling them around the attr code like we do now, because
> > redo items cannot be deferred from one defer_ops to another.

Probably should handle that when we dup the transaction just before
the roll, right?

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: Parent pointers

[Darrick J. Wong]

On Mon, Jul 17, 2017 at 10:33:12AM -0500, Mark Tinguely wrote:
> On 07/17/2017 09:49 AM, Brian Foster wrote:
> >On Sat, Jul 15, 2017 at 04:36:27PM +0000, Tinguely, Mark wrote:
> >>-----Original Message-----
> >>From: linux-xfs-owner@vger.kernel.org [mailto:linux-xfs-owner@vger.kernel.org] On Behalf Of Darrick J. Wong
> >>Sent: Friday, July 14, 2017 5:47 PM
> >>To: Brian Foster <bfoster@redhat.com>
> >>Cc: Eric Sandeen <sandeen@sandeen.net>; Allison Henderson <allison.henderson@oracle.com>; cmaiolino@redhat.com; linux-xfs@vger.kernel.org
> >>Subject: Re: Parent pointers
> >>
> >>On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> >>>On Fri, Jul 14, 2017 at 01:46:27PM -0500, Eric Sandeen wrote:
> >>>>On 07/14/2017 12:44 PM, Allison Henderson wrote:
> >>>>>On 7/14/2017 7:04 AM, Eric Sandeen wrote:
> >><parent inode pointers returneth messages deleted>
> >>
> >>>It's something to keep in mind, in any event. IIRC there were also
> >>>missing Signed-off-by's required for some of Mark's original patches.
> >>That's also a problem; unless someone can get Mark to supply them, we probably have to get someone to rewrite them.  At a bare minimum I think we explicitly have to pass back a xfs_dir2_dataptr_t, not a bare uint32_t.
> >>
> >>Me says:
> >>The community can do what they want.  If you want to start with that code, permission for S-O-B: me (snickers at the pun)
> >>
> >Thanks Mark. I guess we can add Mark's Signed-off-by to those patches he
> >originally authored and that solves that problem. :)
> >
> >>>IMO, the best next step might be to just finish off the implementation
> >>>as-is such that we could have a fairly functional RFC to put on the
> >>>list and hash out whether there are in fact any remaining design
> >>>hurdles, but others might have a different opinion on that. :)
> >>No one is asking me but I will add, IMO (definitely disclaiming the storage group and HPE):
> >>  the PIP costs outweigh the benefits.
> >>    Adding the redundant filename for recovery and an occasional output of the path pushes the cost to be *totally unreasonable*.
> >>     If I had a say, I don't and won't, I would NAK any implementation that included it.
> >>  Implementing with extended attributes is the wrong, wrong, wrong choice. It was done for hysterical :) reasons and even that appeasement bit me in the asterisk.
> >>
> >Could you elaborate on this a bit? I haven't gone through all of the old
> >discussions and it's been a while since I've even reviewed the recent
> >code, but on a quick look at the links Darrick posted, it appears the
> >old implementation incorporated the "first" parent pointer direct in the
> >inode with a fallback to xattrs for inodes with multiple parents whereas
> >the updated implementation uses xattrs outright (and as a result is able
> >to incorporate the dentry name in the xattr). Is that an accurate
> >summary?
> >
> >If so, is the performance concern really the use of xattrs or the fact
> >that the name is included (or some combination of both)? For example,
> >would you consider a situation where pp's are entirely isolated to
> >shortform xattrs much worse than the direct pp approach? It seems to me
> >that the inline approach could still be considered as an optimization
> >(i.e., maybe an incore cache) if performance does prove to be a problem.
> >Maybe we could also consider something where (somehow, handwaving again
> >;) some number of pp xattrs are always shortform and thus remain within
> >the inode.

I'd rather not do that, since a certain filesystem is, uh, extending its
ability to store extended attributes (with biases to keep inline data
and ACLs and such inside the inode).  Now they have two different places
where keys can hide and three places where values can get stuffed, and
it's ... a complicated mess.

Better just to leave the existing da btree structure that we understand,
unless we find that the cost is so outrageous that it becomes worth
breaking all our brains.  As it is, fixing the existing atomicity
problems w.r.t. xattrs will be invasive enough.

> I disagree with both saving the name and using xattrs.

FWIW I disagree with /not/ storing the name, because my vision for
parent pointers is to store backrefs that are rich enough that we can
(ideally) reconstruct the damaged parts of the directory tree or (worst
case) feed lost+found better names.

(Though, we have enough cooks now that I encourage everyone with
differing goals to speak up.)

> >IOW, I think performance is a valid concern, but this should probably
> >1.) follow correctness and 2.) be more dictated by testing (another
> >really good reason to try and finish off the current rfc IMO) where we
> >can consider various, potentially problematic situations. We're bound to
> >have workloads where pretty much every file is hardlinked more than once
> >(think glusterfs), for example.

Agree.

> >Brian
> >
> OMG! Sigh ...
> >>Good luck.
> x2

Thanks!

--D

> >>
> >>--Mark Tinguely
> >>   not representing anyone but myself.
> >>
> >>
> >>--
> >>To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> >>the body of a message to majordomo@vger.kernel.org
> >>More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Darrick J. Wong]

On Tue, Jul 18, 2017 at 08:14:07AM +1000, Dave Chinner wrote:
> On Mon, Jul 17, 2017 at 10:48:16AM -0400, Brian Foster wrote:
> > On Fri, Jul 14, 2017 at 03:46:58PM -0700, Darrick J. Wong wrote:
> > > On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> > > From what I can tell, he seems to have taken Mark's patches to pass dir
> > > offsets back from the dirent manipulation functions and then started
> > > writing a simple implementation of stuffing the attrs into the attr
> > > tree.
> 
> Yup, that's the idea.
> 
> > > > FWIW, I think there was some mention of porting some of the operations
> > > > over to the deferred ops infrastructure, but it's not clear to me off
> > > > the top of my head how important (or appropriate) that is.
> > > 
> > > Most of the users of xfs_trans_roll seem to be buried in the xattr code.
> > > For example, _attr_set can end up rolling a transaction after converting
> > > an attr fork from short format to leaf format before retrying the attr
> > > add operation, but we don't use log redo items (er, defer_ops items) to
> > > make sure log recovery will restart the attr add operation if we crash
> > > before the final _trans_commit after calling _attr_{leaf,node}_addname.
> > > 
> > > In the case of a regular xattr set operation this wouldn't have been a
> > > big deal because the fsetxattr call wouldn't have returned, so all the
> > > user could possibly see is an inode with a perhaps unnecessarily large
> > > xattr fork.  Now that we need to set xattrs in the same transaction
> > > chain as a directory operation, it becomes very important that log
> > > recovery gain the ability to resume an xattr add operation no matter
> > > where the log stopped.  Creating a directory can become this longwinded
> > > pile of updates:
> > > 
> > 
> > Ok, thanks for the summary. So we have some transaction ordering down in
> > the xattr code that might no longer be sufficient to provide atomicity
> > in the context of parent pointers (via directory operations).
> 
> We already have xattr operations that are not atomic with directory
> entry creation - security xattrs (default ACL, etc). This can mean
> that after a crash and recovery, we have a newly created file
> without any security xattr on it.
> 
> This is a long standing problem - it bites SGI's HSM (DMF) all the
> time, so rather than fixing the problem 10+ years ago, they added a
> post-boot inode scan (via bulkstat) to find inodes that didn't have
> a DMF xattr.

<nod>

That reminds me, Ted was asking what _check_xfs_test_fs (in xfstests)
does.  Judging from the nonexistent xfs_repair_ipaths command, I'm
guessing that program fixed up pptr xattrs if they were
broken/missing/whatever?

> The original parent pointer patchset also had this problem the
> moment xattrs were required (i.e. first hardlink) - the creation of
> the pp xattr was not atomic with the dirent creation. To solve this
> problem, I started by moving the xattr creation into the transaction
> context of the dirent.
> 
> > I see that
> > the current patch series increases the transaction size to accommodate
> > parent pointers, but that doesn't help us deal with those situations
> > where the transaction is rolled into a new one.
> 
> Right, I hadn't got that far. The plan effective was to get a proof
> of concept running with the xattr creation within the directory
> creation xact context and get that working, knowing that it still
> wasn't properly atomic. This was done before we had deferred ops,
> and my thinking at the time was to add an intent/done pair of ops
> to tell recovery it needed to add an xattr to the dirent once the
> xattr was inside the dirent context. i.e.
> 
> 	- move xattr inside dirent ctx
> 	- add pp intent
> 	- roll transaction
> 	- add pp xattr
> 	- roll final xattr transaction rather than commit
> 	- add pp done
> 	- commit dir ctx transaction.
> 
> This doesn't help us with security context xattrs, though, so
> when deferred ops came along, it made much more sense to me to
> make the adding of an xattr a deferred op so we could use the same
> mechanism for adding all the required xattrs to the inode atomically
> and so have a mechanism for recovery to replay them appropriately.

<nod>

> > > - Allocate directory block, map into data fork, chain rmap update, add
> > >   directory entry, chain pptr update;
> > > - Add rmap entry for new directory block (more chaining to fix
> > >   freelist), finish first rmap update;
> > > - Allocate xattr block for short->leaf conversion, map into attr fork,
> > >   chain rmap update; chain xattr add operation;
> > > - Add rmap entry for new xattr block (more chaining to fix freelist),
> > >   finish second rmap update;
> > > - Add xattr entry to file, finish xattr add operation;
> > > - Finish pptr update.
> > > 
> > > Basically, I think someone's going to have to go audit all the uses of
> > > xfs_trans_roll in the attr code to figure out which operations need redo
> > > items, and how to cram everything toegether into a single xfs_defer_ops,
> > > rather than sprinkling them around the attr code like we do now, because
> > > redo items cannot be deferred from one defer_ops to another.
> 
> Probably should handle that when we dup the transaction just before
> the roll, right?

Something like that.  Ideally, I think I'd like to have two xattr redo
items: "add key => value" and "remove key", where "add key" would first
ensure xattr space, roll, and then actually add the attr & value.  A big
problem with that scheme is that we then have to log the value, which
could be ... tough.

--D

> 
> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Parent pointers

[Dave Chinner]

On Mon, Jul 17, 2017 at 04:10:03PM -0700, Darrick J. Wong wrote:
> On Tue, Jul 18, 2017 at 08:14:07AM +1000, Dave Chinner wrote:
> > On Mon, Jul 17, 2017 at 10:48:16AM -0400, Brian Foster wrote:
> > > On Fri, Jul 14, 2017 at 03:46:58PM -0700, Darrick J. Wong wrote:
> > > > On Fri, Jul 14, 2017 at 03:07:41PM -0400, Brian Foster wrote:
> > > > From what I can tell, he seems to have taken Mark's patches to pass dir
> > > > offsets back from the dirent manipulation functions and then started
> > > > writing a simple implementation of stuffing the attrs into the attr
> > > > tree.
> > 
> > Yup, that's the idea.
> > 
> > > > > FWIW, I think there was some mention of porting some of the operations
> > > > > over to the deferred ops infrastructure, but it's not clear to me off
> > > > > the top of my head how important (or appropriate) that is.
> > > > 
> > > > Most of the users of xfs_trans_roll seem to be buried in the xattr code.
> > > > For example, _attr_set can end up rolling a transaction after converting
> > > > an attr fork from short format to leaf format before retrying the attr
> > > > add operation, but we don't use log redo items (er, defer_ops items) to
> > > > make sure log recovery will restart the attr add operation if we crash
> > > > before the final _trans_commit after calling _attr_{leaf,node}_addname.
> > > > 
> > > > In the case of a regular xattr set operation this wouldn't have been a
> > > > big deal because the fsetxattr call wouldn't have returned, so all the
> > > > user could possibly see is an inode with a perhaps unnecessarily large
> > > > xattr fork.  Now that we need to set xattrs in the same transaction
> > > > chain as a directory operation, it becomes very important that log
> > > > recovery gain the ability to resume an xattr add operation no matter
> > > > where the log stopped.  Creating a directory can become this longwinded
> > > > pile of updates:
> > > > 
> > > 
> > > Ok, thanks for the summary. So we have some transaction ordering down in
> > > the xattr code that might no longer be sufficient to provide atomicity
> > > in the context of parent pointers (via directory operations).
> > 
> > We already have xattr operations that are not atomic with directory
> > entry creation - security xattrs (default ACL, etc). This can mean
> > that after a crash and recovery, we have a newly created file
> > without any security xattr on it.
> > 
> > This is a long standing problem - it bites SGI's HSM (DMF) all the
> > time, so rather than fixing the problem 10+ years ago, they added a
> > post-boot inode scan (via bulkstat) to find inodes that didn't have
> > a DMF xattr.
> 
> <nod>
> 
> That reminds me, Ted was asking what _check_xfs_test_fs (in xfstests)
> does.  Judging from the nonexistent xfs_repair_ipaths command, I'm
> guessing that program fixed up pptr xattrs if they were
> broken/missing/whatever?

I can't remember - there was an aborted parent pointer
implementation committed to Irix 6.5.27 that had some userspace
tools written for it. That implementation was aborted because the
inode generation number was not in the on-disk PP format and so
lookups would find the wrong parent inode if it raced with unlinks.
ISTR that xfs_repair_ipaths was a standalone dev tool used to
check/rebuild parent paths as that functionality hadn't been added
to xfs_repair yet...

> > > > - Allocate directory block, map into data fork, chain rmap update, add
> > > >   directory entry, chain pptr update;
> > > > - Add rmap entry for new directory block (more chaining to fix
> > > >   freelist), finish first rmap update;
> > > > - Allocate xattr block for short->leaf conversion, map into attr fork,
> > > >   chain rmap update; chain xattr add operation;
> > > > - Add rmap entry for new xattr block (more chaining to fix freelist),
> > > >   finish second rmap update;
> > > > - Add xattr entry to file, finish xattr add operation;
> > > > - Finish pptr update.
> > > > 
> > > > Basically, I think someone's going to have to go audit all the uses of
> > > > xfs_trans_roll in the attr code to figure out which operations need redo
> > > > items, and how to cram everything toegether into a single xfs_defer_ops,
> > > > rather than sprinkling them around the attr code like we do now, because
> > > > redo items cannot be deferred from one defer_ops to another.
> > 
> > Probably should handle that when we dup the transaction just before
> > the roll, right?
> 
> Something like that.  Ideally, I think I'd like to have two xattr redo
> items: "add key => value" and "remove key", where "add key" would first
> ensure xattr space, roll, and then actually add the attr & value.  A big
> problem with that scheme is that we then have to log the value, which
> could be ... tough.

Well, there's a couple of things to remember here:
	1. we already log the attribute value in the modified
	   buffer if it is inserted inline.
	2. we don't log the attribute values for remote attributes,
	   but instead do a sync write after allocation but before
	   we commit the transaction.

For parent pointers, the attribute value is always going to be less
than 255 bytes, so it will always be inline and so logging the
name/value pair in the redo item is, IMO, not going to be an issue
for parent pointers.

For security attributes it might be a different story - how big do
default ACLs and security labels get, anyway?  Maybe one we can
simply suck it up (i.e. burn log bandwidth) given how rare huge
attributes tend to be?

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Parent pointers

[Allison Henderson]

Hi all,

I've been doing some digging on adding parent pointers to xfs and wanted 
to send a note to folks here to get peoples opinions on it.  I got in 
touch with Brian Foster not too long ago and he had some code partially 
done from about a year or so ago (looks like it has patches from Dave 
Chinner and Mark Tinguely as well).  So I am hoping to be able to use 
what we have so far to create something updated and finished out.  I am 
still pretty new to the xfs code, so at the moment I am still just going 
through old discussion threads, and reviewing the patches.  But for the 
most part I just wanted to see what people thought and get everyone on 
board with the idea.  Suggestions and feedback are much appreciated. 
Thank you!!

Allison Henderson