Greets, Scott! Maybe we'll catch each other at BLU someday... (if I
ever make it...)
> > Keep your eyes peeled for another patch from Scott (I e-mailed him
> > this AM with some comments about the current code, and within 20
> > minutes he had e-mailed me back saying he had a working patch running
> > on his system... I may code my own version for kicks, but you'll
> > probably see one from him on the list much sooner ;->
>
> Well, here's the problem, as pointed out to me this afternoon by Mr. Linus
> Torvalds: symlink traversal is inherently recursive. We can rewrite the
> tail recursion as iteration (which my morning patch did), but symlinks in
> the middle of paths require mid-recursion. You need to keep a stack
> around *somewhere* to handle this.
Yeah, I read Linus's message, and have been wrestling with various
pseudo-code algorithms for a little while, trying to show how this
thing can be done iteratively. A basic model (similar to the one
givcen by Linus):
dentry *lookup_dentry(char *name)
{
dentry *here, *newhere;
if (*name=='/') {
here = get_root();
here++;
} else {
here = get_cwd();
}
/* "here" will always point to either a directory,
a symlink, or a file. */
for(;;) {
subname = get_first_part_of(name);
if (!subname)
break; /* we've exhausted the name passed to us */
name += strlen(subname);
for ( ; *name=='/' ; name++); /* lob off spare /'s */
if (!IS_DIR(newhere->inode))
return -EEXIST;
newhere = lookup_within_directory(here, subname);
while (IS_SYMLINK(newhere.inode)) {
newhere = traverse_one_step(newhere);
if (!newhere)
return -EEXIST;
}
here = newhere;
/* Now, "here" is either a dir or a file. If a file,
then we detect /path/file/bogus-path above.
If a directory, we're set... either the given
path is exhausted and the loop breaks, or
there's more to look up using l_w_d() */
}
return here;
}
The only problem is in coding traverse_one_step: that "one step" is a
symlink of arbitrary length, any component of which may itself be a
symlink which needs expansion.
So I'm now pondering a linked-list expansion scheme, where the head of
lookup_dentry convers the pathname into a linked list; then the whole
"while() { traverse_one_step }" loop could be replaced by an
if (IS_SYMLINK(here)) {
expand_linked_list(currentlistnode,here);
continue;
}
(the components introduced could naturally include ".."'s as well as a
"/" entry to force the lookup back to the user's root, and any
components that are themselves symlinks won't be expanded until
they're reached by the nice flat'n'iterative for(;;) loop.
Dynamicly allocating memory to build up a doubly-linked list could be
(relatively) time-consuming, however, compared with more
stack-oriented approaches, so we need to question whether that
trade-off would be worthwhile. It could possibly be replaced with a
little string-handling black magic (I've become quite good at that
recently).
> I agree with Linus that the Right Thing
> may have to wait until 2.3.x, but if the no-tail-recursion partial fix
> proves useful, perhaps that will be included in 2.2.x.
Don't think there's much doubt about that; we're talking about a
significant change to the dentry system's gritty underbelly...
Adam
-- You crucify all honesty \\Adam D. Bradley artdodge@cs.bu.edu No signs you see do you believe \\Boston University Computer Science And all your words just twist and turn\\ Grad Student and Linux Hacker Reviving just to crash and burn \\ <>< ---------> Why can't you listen as love screams everywhere? <--------
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu