This message generated a parse failure. Raw output follows here. Please use 'back' to navigate. From devnull@lkml.org Thu Apr 25 10:21:37 2024 Received: from entropy.muc.muohio.edu (entropy.muc.muohio.edu [134.53.193.10]) by herbie.ucs.indiana.edu (8.8.8/8.8.8) with ESMTP id FAA25358 for ; Thu, 16 Apr 1998 05:02:01 -0500 (EST) Received: from vger.rutgers.edu (root@vger.rutgers.edu [128.6.190.2]) by entropy.muc.muohio.edu (8.8.7/8.8.7) with ESMTP id GAA19454; Thu, 16 Apr 1998 06:01:35 -0400 Received: by vger.rutgers.edu id <970956-214>; Thu, 16 Apr 1998 05:52:41 -0400 Received: from [194.219.21.65] ([194.219.21.65]:54140 "EHLO eetaa.gr" ident: "NO-IDENT-SERVICE") by vger.rutgers.edu with ESMTP id <970957-214>; Thu, 16 Apr 1998 05:52:20 -0400 Received: from zircon (gf@zircon.eetaa.gr [194.219.21.54]) by eetaa.gr (8.8.5/8.8.5) with SMTP id MAA24707; Thu, 16 Apr 1998 12:56:02 +0300 (EET DST) Message-Id: <3535D5B1.493B168D@eetaa.gr> Date: Thu, 16 Apr 1998 12:56:01 +0300 From: George Famelis Organization: EETAA SA (Athens) X-Mailer: Mozilla 3.01Gold (X11; I; Linux 2.0.30 i486) Mime-Version: 1.0 To: linux-kernel@vger.rutgers.edu Cc: gf@eetaa.gr Subject: Re: PATCH: smart symlink loop detection. References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Orcpt: rfc822;linux-kernel@vger.rutgers.edu Sender: owner-linux-kernel@vger.rutgers.edu Precedence: bulk X-Loop: majordomo@vger.rutgers.edu Hi : C. Scot 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. > : Adam D. Bradley > 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): > Let me try to show that there is no middle recursion and that we allways we have tail recursion. Here are some definitions: := || # a File Identifier := || # a Directory Identifier := || # an Unresolved File Name (i.e some components may be symlinks) := || || "/" # an Unresolved Path := "/" || "/" # a Real Path (i.e. it has no components that are symlinks) := || # a Real File Name (i.e. the one with no symlink components) := || The contents of is a and the contents of is a . Our problem is to find the for a given . I assume that get_cwd() returns the of Current Working Directory For the loop detection we need something unique and I suggest that per file system the inode of the at hand is unique. If this is true (I don't know if this holds for all types of file systems) we can have the pair {FileSystem, inode-number} to be the thinks we remember for all the inodes we have visited. For any given there are two cases: Case 1) is a relative name (i.e. not starting with a "/") => get_cwd() + is in Case 2 format Case 2) is an absolute name => we can always starting from the begining to split it in one of the forms Case 2.a) or Case 2.b) or Case 2.c) In case 2.a we are done. In cases 2.b,2.c we call the loop detecting algorithm with the triple {FileSystem, inode-number_of(} if a loop is found then we are done else if contains an absolute name then the new to check is (Case 2.b.1) => new := => (Case 2) (Case 2.c.1) => new := => (Case 2) else contains a relative name and the new is (Case 2.b.2) => new := => (Case 2) (Case 2.c.2) => new := => (Case 2) In any case we continue either from the begining of the new (Cases 2.[bc].1) or from the end of of the new (Cases 2.[bc].2) So in any case we have an iteration. Let me modify what Adam D. Bradley wrote + char *PathStart; + char *SaveStr(char *, ...); + void FreeStr(char *); /* Free what SaveStr has allocated */ + char *GetNameOf(dentry *); + char *SymlinkValue(dentry *); /* where the symlink points to */ + void LoopDetectInit(); + void LoopTrail(dentry *); /* remember the places where we have been */ + bool LoopDetect(dentry *); > dentry *lookup_dentry(char *name) > { > dentry *here, *newhere; + char *IdentAtHand; + char *Symlink; > + /* Do not FreeStr(name) here is not ours */ > if (*name=='/') { + PathStart = SaveStr(name); + name = PathStart; + name++; > - here = get_root(); + newhere = get_root(); > - here++; > } else { > newhere = get_cwd(); + ItemAtHand = GetNameOf(newhere); + PathStart = SaveStr(ItemAtHand, name) + name = &PathStart[strlen(ItemAthand)]; + FreeStr (ItemAtHand); > } > /* "here" will always point to either a directory, > a symlink, or a file. */ > + LoopDetectInit(); + LoopTrail(newhere); > for(;;) { + here = newhere; + ItemAthand = name; > 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)) + if (!IS_DIR(here->inode)) > - return -EEXIST; + goto Failed; > > newhere = lookup_within_directory(here, subname); > + LoopTrail(newhere); + if (!IS_SYMLINK(newhere->inode) + continue; + + /* now we have a symlink */ + if (LoopDetect(newhere)) + goto Failed; + + Symlink = SymlinkValue(newhere->inode); + if (*Symlink == "/") { /* an absolute path */ + name = SaveStr(Symlink, "/", name); + FreeStr(SymLink); + FreeStr(name); + newhere = get_root(); + goto Restart; + } else { /* a relative path */ + *ItemAtHand = '\0'; + ItemAtHand = PathStart; + PathStart = SaveStr(PathStart, SymLink, "/", name); + FreeStr (SymLink); + FreeStr (name); + name = &PathStart[strlen(ItemAtHand)]; + FreeStr (ItemAtHand); + newhere = here; /* we continue to be at the same place */ + continue; + } > - 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() */ > } > + FreeStr(ItemAtHand); + FreeStr(name); + /* PathStart contains the Real Path of argument given */ > return here; + Failed: + FreeStr(ItemAtHand); + FreeStr(PathStart); + FreeStr(name); + PathStart = NULL; + return (dentry *)NULL; > } > Regards, George - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu