> On Tue, 14 Apr 1998, C. Scott Ananian wrote:
> >
> > > Essentially, what your patch does is to just remove the tail-recursion,
> > > which may be a good thing to do in itself, but it doesn't remove the
> > > mid-recursion.
> >
> > Let me think more about this and see if I can't come up with a more
> > elegant solution. [I can't believe I overlooked the mid-recursion.]
>
> Note that I personally do not find anything wrong with recursion, when
> used sparingly. Especially in this case recursion just makes things _so_
> much easier that not using recursion is not a very good idea in my
> opinion, unless it can be done in a really clean way.
Right. If I can avoid the recursion we can get rid of any hard limit of
symlink nesting depth, though, which conceptually is a Good Thing. If I
have to trash the code to make this happen, it's a Bad Thing.
> I don't dislike your patch: it does what it does really well, and arguably
> the tail recursion removal is a good thing in many ways. There is nothing
> wrong with having a mixture of recursion and iteration - especially as the
> tail removal probably tends to make the "average depth" much less in most
> cases.
>
> So I don't actually object to your patch, while I also don't think it is
> necessarily needed. I don't like having two ways to do the same thing, but
> that mild dislike is balanced by a mild liking of the lower average depth.
> So I'm fairly neutral on this patch.
Well, at the very least I should put in the mid-recursion depth limit to
avoid trashing the stack. That wouldn't be hard; I didn't get rid of
current->link_depth. Then we can have unlimited depth tail recursion, at
least. I don't know enough about how the 'bind' distribution was set up
to know if this would fix the reported problems, but it might.
> A patch that tries to remove the mid-recursion would be a lot more
> involved, and this is why I suspected I wouldn't accept such a patch
> before 2.3.x. And I might not accept it even then, if only because I
> suspect the recursive algorithm is so much simpler.
>
> So maybe the hybrid approach is the right one. Who knows? I don't have any
> strong opinions either way, but this is worth discussing.
Let me try to outline what the hybrid approach would require. If anyone
has better ideas, let me know.
The basic problem is that followlink can not necessarily be implemented as
lookup_dentry(readlink()). [arguments omitted; you get my point] /proc
at least has problems with this, it tries to be clever. There's also an
inherent path length limit which one would have to avoid.
*However* we only care about the <fs>_follow_link implementations that
*do* call lookup_dentry with some string. The funny stuff in
proc_follow_link does not recurse into lookup_dentry, so we've no troubles
with it.
What seems to be required is the following: those <fs>_follow_link
implementations that call lookup_dentry could be rewritten to instead
return the *arguments it would have passed to lookup_dentry*. We can then
move the actual iteration into lookup_dentry, removing all the recursion
*and* not requiring a stack. Extreme cleverness is required to avoid
limiting the path string length.
In short, I believe this is do-able without any recursion, but Linus is
correct, it requires more extensive code changes.
I will attempt to implement this to find out exactly how hairy it would be
and post the patch when I am done. Is there any linux-kernel consensus on
whether the hybrid approach of my first patch is useful irregardless of
the status of this second?
[and can the person who reported the 'bind' distribution problems
elaborate on the directory structure employed so that we can tell whether
the hybrid approach does fix that buglet?]
[I'll post another patch with just documentation fixes to clarify namei.c,
now that we all understand what's going on. fs/umsdos/symlink.c has a
comment that should be nuked, too.]
--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