Re: symlinks.

C. Scott Ananian (cananian@lcs.mit.edu)
Tue, 14 Apr 1998 07:02:14 -0400 (EDT)


On Tue, 14 Apr 1998, Adam D. Bradley wrote:

> On Tue, 14 Apr 1998, C. Scott Ananian wrote:
> > On Tue, 14 Apr 1998, C. Scott Ananian wrote:
> >
> > > Regarding the hullaballo about stack usage on follow_symlink depth limits:
> > > From my reading of the code, it does not seem as if do_follow_symlink is
> > > recursive at all. It is called in an for(ever) loop in lookup_dentry()
> > > in fs/namei.c; it only goes down one link per invocation, and pushes
> > > nothing onto the stack.
> >
> > OK, I was wrong. The calls are recursive: lookup_dentry() calls
> > do_follow_link() which (in the filesystem-dependent code) calls
> > lookup_dentry again, which will call do_follow_link() again. So it is
> > recursive. BUT IT DOESN'T HAVE TO BE.
> >
> > I'm like to change the semantics so that the filesystem-dependant
> > follow_symlink() function calls lookup_dentry with follow=0.
> > We could then replace the recursion with a loop in do_follow_symlink().
>
> Hmm... comments in the code (fs/namei.c) claim:
>
> * The new code replaces the old recursive symlink resolution with
> * an iterative one (in case of non-nested symlink chains). It does
> * this by looking up the symlink name from the particular filesystem,
> * and then follows this name as if it were a user-supplied one. This
> * is done solely in the VFS level, such that <fs>_follow_link() is not
> * used any more and could be removed in future. As a side effect,
> * dir_namei(), _namei() and follow_link() are now replaced with a single
> * function lookup_dentry() that can handle all the special cases of the former
> * code.
>
> So it looks like lookup_dentry is written with iterative behavior in
> mind, but if your analysis of the code is right, then do_follow_link
> is still recursing, which it shouldn't. (quick check of ext2 code -
> yup.) So we should be able to get this behavior by simply changing
> lookup_dentry(x,y,1) to lookup_dentry(x,y,0) in individual
> <fs>_follow_link()'s, right?
>
> Looks like AFFS, Coda, ext2, ISO, minix, NFS, proc. romfs, sysv, and
> ufs implement follow_link's...

Righty-o. Patch shortly.

> It's also seems odd (IMHO) that the comments claim the link-following
> is iterative, but the link-limit is enforced in follow_link (which
> appears to have been done with the old recursive scheme in mind.) It
> seems to me the "for(;;)" in lookup_dentry() should be replaced with a
> link-limiting loop instead.

I think the code was *half* fixed. I don't know what the code used to
look like, but my guess is that lookup_dentry used to invoke *itself*
directly to handle embedded symlinks in paths. i.e. a/b/c where b was a
symlink would fetch b and then recurse to handle b/c. I think you'd have
to do some old-kernel surfing to know for sure. Or we could just ask
Linus. ;-)

The 'for (;;)' in lookup_dentry is handling the individual components of
the path. It has very little to do with symlinks.

> > We could then use Tarjan's algorithm to accurately detect loops without
> > false-positives.
>
> That's the one with the "chaser" that advances once for every two
> advances of the "real", right? (detects loop within 2n?)

Right. I'm running this on my machine as I write this. As soon as diff
is finished, I'll mail out the patch.

> Don't know if Linus would accept this at the moment (given the code
> freeze), since it changes the semantics of inode->i_op->follow_link().
> But (IMVVVHO) it's The Right Thing To Do - it removes recursion from
> the kernel (which is stack-limited) and opens up both greater
> configurability (allowing ambiguous depth won't overflow the stack)
> and the ability to do real loop detection.

> It also would (I think) bring the code into alignment with the
> documentation, although we all know the proverb about when the code
> and docs disagree ;-)

I agree. The patch is very short: do_follow_link() is the only major
function changed, apart from the 1->0 argument changes in
<fs>_follow_link. Linus, if you want to wait until 2.3.X for this, I
understand. The real motivation for the patch was the report that
the standard 'bind' distribution wouldn't compile on linux because of the
way the symlinks were nested.

Another code/doc disagreement is in fs/umsdos/symlink.c, where the
necessity of follow_link is questioned. Apparently the VFS used to
synthesize a follow_link operation from readlink if follow_link was not
supplied. This would be trivial to implement, *but* creating a
follow_link from readlink requires a path-size limit. Since the whole
point of the follow_link rewrite was to remove hard limits, I did not add
the readlink fallback. Filesystem authors should suck up and write a real
follow_link function. It's not hard.
--Scott
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cananian@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu