by Al Viro

[permalink] [raw]

On Wed, 22 Apr 2015 22:05:53 +0100 Al Viro <[email protected]> wrote:

> On Wed, Apr 22, 2015 at 09:12:38PM +0100, Al Viro wrote:
> > On Wed, Apr 22, 2015 at 07:07:59PM +0100, Al Viro wrote:
> > > And one more: may_follow_link() is now potentially oopsable. Look: suppose
> > > we've reached the link in RCU mode, just as it got unlinked. link->dentry
> > > has become negative and may_follow_link() steps into
> > > /* Allowed if owner and follower match. */
> > > inode = link->dentry->d_inode;
> > > if (uid_eq(current_cred()->fsuid, inode->i_uid))
> > > return 0;
> > > Oops... Incidentally, I suspect that your __read_seqcount_retry() in
> > > follow_link() might be lacking a barrier; why isn't full read_seqcount_retry()
> > > needed?

Blind copy-paste error I suspect.

> > >
> > > FWIW, I would rather fetch ->d_inode *and* checked ->seq proir to calling
> > > get_link(), and passed inode to it as an explicit argument. And passed it
> > > to may_follow_link() as well...
> >
> > Hrm... You know, something really weird is going on here. Where are
> > you setting nd->seq? I don't see anything in follow_link() doing that.

follow_link calls link_path_walk -> walk_component -> lookup_fast which sets
nd->seq. Is that not enough? I guess not when nd_jump_link is called. Is
that what I missed?

> > And nd->seq _definitely_ needs setting if you want to stay in RCU mode -
> > at that point it matches the dentry of symlink, not that of nd->path
> > (== parent directory). Neil, could you tell me which kernel you'd been
> > testing (ideally - commit ID is a public git tree), what config and what
> > tests had those been?

The 'devel' branch of git://neil.brown.name/md, which is based on 4.0-rc7.

Tests have been fairly causal so far, making sure I can follow symlinks on a
small variety of filesystems, and running a particular test which repeatedly
stats a large number of non-existent files with paths that go through a
symlink.

>
> FWIW, there's a wart that had been annoying me for quite a while, and it
> might be related to dealing with that properly. Namely, walk_component()
> calling conventions. We have walk_component(nd, &path, follow), which can
> * return -E..., and leave us with pathwalk terminated; path contains
> junk, and so does nd->path.
> * return 0, update nd->path, nd->inode and nd->seq. The contents
> of path is in undefined state - it might be unchanged, it might be equal to
> nd->path (and not pinned down, RCU mode or not). In any case, callers do
> not touch it afterwards. That's the normal case.
> * return 1, update nd->seq, leave nd->path and nd->inode unchanged and
> set path pointing to our symlink. nd->seq matches path, not nd->path.
>
> In all cases the original contents of path is ignored - it's purely 'out'
> parameter, but compiler can't establish that on its own; it _might_ be
> left untouched. In all cases when its contents survives we don't look at
> it afterwards, but proving that requires a non-trivial analysis.
>
> And in case when we return 1 (== symlink to be followed), we bugger nd->seq.
> It's left as we need it for unlazy_walk() (and after unlazy_walk() we don't
> care about it at all), so currently everything works, but if we want to
> stay in RCU mode for symlink traversal, we _will_ need ->d_seq of parent
> directory.
>
> I wonder if the right way to solve that would be to drop the path argument
> entirely and store the bugger in nameidata. As in
> union {
> struct qstr last;
> struct path link;
> };
> ...
> union {
> int last_type;
> unsigned link_seq;
> };
> in struct nameidata. We never need both at the same time; after
> walk_component() (or its analogue in do_last()) we don't need the component
> name anymore. That way walk_component() would not trash nd->seq when
> finding a symlink...
>
> It would also shrink the stack footprint a bit - local struct path next
> in link_path_walk() would be gone, along with the same thing in path_lookupat()
> and friends. Not a lot of win (4 pointers total), but it might be enough
> to excuse putting ->d_seq of root in there, along with ->link.dentry->d_inode,
> to avoid rechecking its ->d_seq. As the matter of fact, we do have an
> odd number of 32bit fields in there, so ->d_seq of root would fit nicely...
>
> Comments?

One thing that is clear to me is that I don't really understand all the
handling of 'seq' numbers, making me unable to comment usefully.
I'll try to go through the current code and you current patch with that issue
in mind and make sure I do understand it. Then I'll try to comment.

Meanwhile, I like your suggestion in separate email to legitimize the whole
symlink stack when unlazy_walk is needed. One reason that I didn't even try
that originally is that it was not practical to walk the stack to find
everything that needed legitimizing. Now that you have that in an explicit
stack it is at least work looking into.

Thanks,
NeilBrown

Attachments:

(No filename) (811.00 B)
OpenPGP digital signature

2015-04-23 18:08:07

by Al Viro

[permalink] [raw]

Subject: Re: [RFC][PATCHSET] non-recursive link_path_walk() and reducing stack footprint

On Thu, Apr 23, 2015 at 05:45:44PM +1000, NeilBrown wrote:

> follow_link calls link_path_walk -> walk_component -> lookup_fast which sets
> nd->seq. Is that not enough? I guess not when nd_jump_link is called. Is
> that what I missed?

No. Potential nd_jump_link() callers are just refusing to go there in lazy
mode, end of story. That's not the problem; see below.

> One thing that is clear to me is that I don't really understand all the
> handling of 'seq' numbers, making me unable to comment usefully.
> I'll try to go through the current code and you current patch with that issue
> in mind and make sure I do understand it. Then I'll try to comment.

OK, here's the basic theory behind the lazy pathwalk:

* during the entire exercise we never drop rcu_read_lock, therefore any
objects that have all references to them removed before RCU-delayed
freeing (inodes, dentries, superblocks and vfsmounts are among such)
that we might find in process won't be freed until after we are done.

* invariant we are keeping:
at some point between the beginning of walk and now the pathname
traversed so far would lead to nd->path, with nd->seq and nd->inode equal to
->d_seq and ->d_inode of the dentry in question.

* path_init() arranges for that to be true in the beginning of the walk.

* symlinks aside, walk_component() preserves that.
+ normal name components go through lookup_fast(), where we have
__d_lookup_rcu() find a child of current nd->path with matching
name and (atomically) picks ->d_seq of that child, which had the
name matching our component. Atomicity is provided by ->d_lock
on child. Then we proceed to pick ->d_inode (and verify that
->d_seq has not changed, thus making sure that ->d_inode value
at the moment when the name matched had been the same and child
is still hashed. Then we verify that parent's ->d_seq has not
changed, guaranteeing that parent hadn't been moved or unhashed
from the moment we'd found it until after we'd found its child.
Assuming nothing's mounted on top of that thing, and there's no
problem with ->d_revalidate()), that's it - we have new nd->seq,
nd->path and nd->inode satisfying our invariant for longer
piece of pathname.
+ "." needs nothing - we just stay where we are
+ ".." is handled by follow_dotdot_rcu(), which in the normal case
(no mountpoint crossing) picks ->d_parent of where we are,
fetches its ->d_inode and ->d_seq and verifies that our directory
still hadn't changed _its_ ->d_seq. The last part guarantees that
it hadn't been moved since the time we'd found it, and thus its
->d_parent had remained unchanged at least until that verification.
Therefore, it remained pinned all along, and it ->d_inode had
remained stable, including the moment when we fetched ->d_seq.
Which means that the value we had picked *and* its ->d_inode and
->d_seq would satisfy the invariant for the longer piece of
pathname.
+ mountpoint crossing towards leaves is handled in __follow_mount_rcu();
it is simple (->mnt_root never changes and is always pinned,
stabilizing its ->d_inode), but we might need to worry about
automount points *and* need to make sure that we stop right
there if mount_lock has been bumped. See commit b37199e6 for
the details on the last part - basically, making sure that false
negatives from __lookup_mnt() won't end up with hard error when
we walk into whatever had been under the mountpoint we'd missed.
+ mountpoint crossing towards root (in follow_dotdot_rcu()) is
similar, but there we obviously don't care about automounts.
Looking at it now, it might make sense to recheck mount_lock there
as well, though - potential danger is to hit the moment when
mnt_parent and mnt_mountpoint are out of sync, leaving us with
mismatched vfsmount,dentry pair. Generally, that will be caught
when we try to leave lazy mode (legitimize_mnt() will fail) or
to cross towards leaves, but the next crossing towards root
might be bogus as well, and we could end up with unwarranted hard
error. Should be very hard to hit, but it's easy enough to check
*and* backport, so it looks like a good idea for -stable. Linus,
do you have any objections against adding
if (read_seqretry(&mount_lock, nd->m_seq))
goto failed;
right after
if (!follow_up_rcu(&nd->path))
break;
in follow_dotdot_rcu()? It's a very narrow race with mount --move
and most of the time it ends up being completely harmless, but
it's possible to construct a case when we'll get a bogus hard error
instead of falling back to non-lazy walk... OTOH, anyone doing
that will get something inherently timing-dependent as the result,
lazy mode or not. I'm in favour of adding that check, but IMO it's
not a critical problem.

* if we find that we can't continue in lazy mode because some verification
fails, we just fail with -ECHILD. However, in cases when our current position
might be fine, but the next step can't be done in lazy mode, we attempt to
fall back to non-lazy without full restart that would be caused by -ECHILD.
That's what unlazy_walk() is. Of course, if we reach the end of walk we
need to leave the lazy mode as well (complete_walk()). Either can fail,
and such a failure means restart from scratch in non-lazy mode. We need
to grab references on vfsmount and dentry (or two dentries, when we have
parent and child to deal with). The interesting part is vfsmount - we need
to make sure we won't interfere with umount(2), having walked in that sucker
*after* umount(2) has checked that it's not busy. See legitimize_mnt() for
details; basically, we have umount(2) mark the "I've verified it's not busy
and it's going to be killed no matter what" with MNT_SYNC_UMOUNT and rely
on RCU delays on that path - if we find one of those, we undo the
increment of its refcount we'd just done, without having dropped
rcu_read_lock(). Full-blown mntput() is done only on mismatches that
had _not_ been marked that way.

BTW, something similar to the above probably needs to be turned into coherent
text, either in parallel to Documentation/filesystems/path-lookup.txt, or
as update to it.

The reason why walk_component() in your call chain won't suffice is simple -
it will fail this
/*
* This sequence count validates that the parent had no
* changes while we did the lookup of the dentry above.
*
* The memory barrier in read_seqcount_begin of child is
* enough, we can use __read_seqcount_retry here.
*/
if (__read_seqcount_retry(&parent->d_seq, nd->seq))
return -ECHILD;
in lookup_fast(), just before updating nd->seq to new value. Basically,
it has no way to tell if parent has been buggered to hell and back.

It's not _that_ hard to prevent - we just need to stop discarding the parent's
seq number in "need to follow a symlink" case of walk_component(). Will take
some massage, but not too much...

2015-04-24 06:35:47

On Mon, 4 May 2015 06:11:29 +0100 Al Viro <[email protected]> wrote:

> On Fri, Apr 24, 2015 at 02:42:03PM +0100, Al Viro wrote:
>
> > That avoids this spin_lock() on each absolute symlink at the price of extra
> > 32 bits in struct nameidata. It looks like doing on-demand reallocation
> > of nd->stack is the right way to go anyway, so the pressure on nameidata size
> > is going to be weaker and that might be the right way to go...
>
> OK, on-demand reallocation is done. What I have right now is
> * flat MAXSYMLINKS 40, no matter what kind of nesting there might
> be.
> * purely iterative link_path_walk().
> * no damn nameidata on stack for generic_readlink()
> * stack footprint of the entire thing independent from the nesting
> depth, and about on par with "no symlinks at all" case in mainline.
> * some massage towards RCU follow_link done (in the end of queue),
> but quite a bit more work remains.
>
> What I've got so far is in vfs.git#link_path_walk; I'm not too happy about
> posting a 70-chunk mailbomb, but it really will need review and testing.
> It survives xfstests and LTP with no regressions, but it will need
> serious profiling, etc., along with RTFS. I tried to keep it in reasonably
> small pieces, but there's a lot of them ;-/
>
> FWIW, I've a bit more reorganization plotted out, but it's not far from
> where we need to be for RCU follow_link. Some notes:
> * I don't believe we want to pass flags to ->follow_link() - it's
> much simpler to give the damn thing NULL for dentry in RCU case. In *all*
> cases where we might have a change to get the symlink body without blocking
> we can do that by inode alone. We obviously want to pass dentry and inode
> separately (and in case of fast symlinks we don't hit the filesystem at
> all), but that's it - flags isn't needed.
> * terminate_walk() should do bulk put_link(). So should the
> failure cases of complete_walk(). _Success_ of complete_walk() should
> be careful about legitimizing links - it *can* be called with one link
> on stack, and be followed by access to link body. Yes, really - do_last()
> in O_CREAT case.
> * do_last(), lookup_last() and mountpoint_last() ought to
> have put_link() done when called on non-empty stack (thus turning the loops
> into something like
> while ((err = lookup_last(nd)) > 0) {
> err = trailing_symlink(nd);
> if (err)
> break;
> }
> _After_ the point where they don't need to look at the last component of
> name, obviously.
> * I think we should leave terminate_walk() to callers in failure
> cases of walk_component() and handle_dots(), as well as get_link(). Makes
> life simpler in callers, actually. I'll play with that a bit more.
> * it might make sense to add the second flag to walk_component(),
> in addition to LOOKUP_FOLLOW, meaning "do put_link() once you are done looking
> at the name". In principle, it promises simpler logics with unlazy_walk(),
> but that's one area I'm still not entirely sure about. Will need to
> experiment a bit...
> * nd->seq clobbering will need to be dealt with, as discussed upthread.
> * I _really_ hate your "let's use the LSB of struct page * to tell
> if we need to kunmap()" approach. It's too damn ugly to live. _And_ it's
> trivial to avoid - all we need is to have (non-lazy) page_follow_link_light()
> and page_symlink() to remove __GFP_HIGHMEM from inode->i_mapping before
> ever asking to allocate pages there. That'll suffice, and it makes sense
> regardless of RCU work - that kmap/kunmap with potential for minutes in
> between (while waiting for stuck NFS server in the middle of symlink traversal)
> is simply wrong.

Thanks!
I'll have another look and see about adding what is needed for RCU symlink
support.

NeilBrown

Attachments:

(No filename) (811.00 B)
OpenPGP digital signature