Messages in this thread | | | Date | Thu, 16 Apr 1998 14:19:56 -0400 (EDT) | From | "C. Scott Ananian" <> | Subject | Re: smart symlink loop detection. |
| |
On Thu, 16 Apr 1998 George Famelis <gf@eetaa.gr> wrote:
> : C. Scott Ananian > > > 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. [...] > Let me try to show that there is no middle recursion and that we allways > we have tail recursion.
I'm not sure what you're trying to prove here. If a filename is a/b/c, and b is a symlink, you have mid-recursion, by definition. In order to turn mid-recursion into iteration, you need some sort of stack. You can keep the stack either a) explicitly, or b) in the pathname (maintain a string indicating which pathname components are yet to be resolved). Either way, you have a stack.
Adam came up with an interesting idea where a linked list was used to make stack type (b) much cleaner. I'm worried that dynamic allocation in the kernel is Not A Good Thing, but I'm interested to see his implementation.
> Here are some definitions:
I think by inventing nomenclature, you've managed to confuse the issue entirely.
> Let me modify what Adam D. Bradley wrote
I don't think your algorithm properly handles a/b/c, where b is a symlink. It appears that you lose the trailing portion and return the expansion of a/b. --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
| |