![[LWN Logo]](/images/lwn.banner.gif)
Date: Tue, 14 Apr 1998 07:54:56 -0400 (EDT)
From: "C. Scott Ananian" <cananian@lcs.mit.edu>
To: linux-kernel@vger.rutgers.edu
Subject: PATCH: smart symlink loop detection.
The attached patch replaces the hard-coded 5-symlink nesting limit with
an implementation of Tarjan's algorithm to accurately and exactly detect
symlink loops. The code now matches the documentation at the head of
fs/namei.c. The semantics of follow_link have been changed: each call to
<fs>_follow_link should return the dentry pointed to by the symlink,
instead of recursing to find the final dentry in the chain. This simply
means that the follow argument to lookup_dentry should be zero, not one.
A hard-limit of 4096 nested-symlinks has been left in to prevent possible
denial-of-service attacks. I think 4096 linked links should be enough for
any reasonable purpose. ;-)
((struct task_struct *)current)->link_count is not needed anymore after
application of this patch, but I wasn't quite sure how to remove it from
the SPARC code (asm-sparc*/asm_offsets.h), so I played it safe and didn't
remove it.
Linus, this patch has been thoroughly tested, but if you want to put this
off until 2.3.x, I understand. The 'good reason' to put it in for 2.2.x
is that 'bind' reportedly will not compile on linux because of the symlink
nesting in the standard distribution.
---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
diff -ruHp -X badboys linux-orig/fs/namei.c linux-2.1.95/fs/namei.c
--- linux-orig/fs/namei.c Tue Apr 14 00:40:20 1998
+++ linux-2.1.95/fs/namei.c Tue Apr 14 07:38:05 1998
@@ -44,12 +44,10 @@
* 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.
+ * and then follows this name as if it were a user-supplied one.
+ * 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.
*
* With the new dcache, the pathname is stored at each inode, at least as
* long as the refcount of the inode is positive. As a side effect, the
@@ -77,6 +75,17 @@
* semantics. See the comments in "open_namei" and "do_link" below.
*/
+/* [14-Apr-98 C. Scott Ananian <cananian@alumni.princeton.edu>]
+ * Rewrote do_follow_symlink to use an interative, rather than recursive,
+ * algorithm. Removed the hard limit on symlink nesting depth.
+ * Note that filesystems must implement both <fs>_readlink() and
+ * <fs>_follow_link. We cannot synthesize readlink() from follow_link
+ * without imposing path length restrictions.
+ *
+ * SEMANTICS CHANGE:
+ * <fs>_follow_link should always pass follow_link=0 to lookup_dentry.
+ */
+
static char * quicklist = NULL;
static int quickcount = 0;
struct semaphore quicklock = MUTEX;
@@ -300,23 +309,53 @@ static struct dentry * real_lookup(struc
static struct dentry * do_follow_link(struct dentry *base, struct dentry *dentry)
{
- struct inode * inode = dentry->d_inode;
-
- if (inode && inode->i_op && inode->i_op->follow_link) {
- if (current->link_count < 5) {
- struct dentry * result;
-
- current->link_count++;
- /* This eats the base */
- result = inode->i_op->follow_link(dentry, base);
- current->link_count--;
+ struct dentry * tarjan_dentry = dget(dentry);
+ struct dentry * tarjan_base = dget(base);
+ int i, odd = 0;
+
+ for (i=0; ; i++) {
+ struct inode * inode = dentry->d_inode;
+ struct dentry * result;
+
+ if (!(inode && inode->i_op && inode->i_op->follow_link))
+ break; /* not a symlink */
+
+ /* dereference the symlink */
+ /* [follow_link does dput(base).] */
+ result = inode->i_op->follow_link(dentry, base);
+ dput(dentry);
+ dentry = result;
+ if (IS_ERR(dentry))
+ goto err_out;
+ base = dget(dentry->d_parent);
+ odd = !odd;
+
+ /* check for loops */
+ if (!odd) {
+ struct inode * t_inode=tarjan_dentry->d_inode;
+ struct dentry * t_result;
+ /* follow link eats base */
+ t_result = t_inode->i_op->
+ follow_link(tarjan_dentry, tarjan_base);
+ dput(tarjan_dentry);
+ tarjan_dentry = t_result;
+ tarjan_base = dget(tarjan_dentry->d_parent);
+ }
+
+ /* if dentry==tarjan_dentry then we've found a loop */
+ /* [limit of 4096 prevents denial-of-service attacks] */
+ if (dentry==tarjan_dentry || i>4096) {
dput(dentry);
- return result;
+ dentry = ERR_PTR(-ELOOP);
+ break;
}
- dput(dentry);
- dentry = ERR_PTR(-ELOOP);
}
+
+ /* Not a symlink. Don't follow any more. */
dput(base);
+err_out:
+ dput(tarjan_dentry);
+ dput(tarjan_base);
return dentry;
}
diff -ruHp -X badboys linux-orig/fs/affs/symlink.c linux-2.1.95/fs/affs/symlink.c
--- linux-orig/fs/affs/symlink.c Tue Apr 14 00:40:32 1998
+++ linux-2.1.95/fs/affs/symlink.c Tue Apr 14 02:20:46 1998
@@ -150,7 +150,7 @@ affs_follow_link(struct dentry *dentry,
}
buffer[i] = '\0';
affs_brelse(bh);
- base = lookup_dentry(buffer,base,1);
+ base = lookup_dentry(buffer,base,0);
kfree(buffer);
return base;
}
diff -ruHp -X badboys linux-orig/fs/autofs/symlink.c linux-2.1.95/fs/autofs/symlink.c
--- linux-orig/fs/autofs/symlink.c Tue Apr 14 00:40:32 1998
+++ linux-2.1.95/fs/autofs/symlink.c Tue Apr 14 02:21:53 1998
@@ -32,7 +32,7 @@ static struct dentry * autofs_follow_lin
struct autofs_symlink *sl;
sl = (struct autofs_symlink *)dentry->d_inode->u.generic_ip;
- return lookup_dentry(sl->data, base, 1);
+ return lookup_dentry(sl->data, base, 0);
}
struct inode_operations autofs_symlink_inode_operations = {
diff -ruHp -X badboys linux-orig/fs/coda/symlink.c linux-2.1.95/fs/coda/symlink.c
--- linux-orig/fs/coda/symlink.c Tue Apr 14 00:40:35 1998
+++ linux-2.1.95/fs/coda/symlink.c Tue Apr 14 02:22:47 1998
@@ -115,7 +115,7 @@ ENTRY;
memcpy(path, mem, len);
path[len] = 0;
- base = lookup_dentry(path, base, 1);
+ base = lookup_dentry(path, base, 0);
kfree(path);
return base;
}
diff -ruHp -X badboys linux-orig/fs/ext2/symlink.c linux-2.1.95/fs/ext2/symlink.c
--- linux-orig/fs/ext2/symlink.c Tue Apr 14 00:40:23 1998
+++ linux-2.1.95/fs/ext2/symlink.c Tue Apr 14 01:28:20 1998
@@ -68,7 +68,7 @@ static struct dentry * ext2_follow_link(
link = bh->b_data;
}
UPDATE_ATIME(inode);
- base = lookup_dentry(link, base, 1);
+ base = lookup_dentry(link, base, 0);
if (bh)
brelse(bh);
return base;
diff -ruHp -X badboys linux-orig/fs/isofs/symlink.c linux-2.1.95/fs/isofs/symlink.c
--- linux-orig/fs/isofs/symlink.c Tue Apr 14 00:40:22 1998
+++ linux-2.1.95/fs/isofs/symlink.c Tue Apr 14 02:18:23 1998
@@ -76,7 +76,7 @@ static struct dentry * isofs_follow_link
return ERR_PTR(-ELOOP);
}
- base = lookup_dentry(pnt, base, 1);
+ base = lookup_dentry(pnt, base, 0);
kfree(pnt);
return base;
diff -ruHp -X badboys linux-orig/fs/minix/symlink.c linux-2.1.95/fs/minix/symlink.c
--- linux-orig/fs/minix/symlink.c Tue Apr 14 00:40:21 1998
+++ linux-2.1.95/fs/minix/symlink.c Tue Apr 14 02:17:21 1998
@@ -52,7 +52,7 @@ static struct dentry * minix_follow_link
return ERR_PTR(-EIO);
}
UPDATE_ATIME(inode);
- base = lookup_dentry(bh->b_data, base, 1);
+ base = lookup_dentry(bh->b_data, base, 0);
brelse(bh);
return base;
}
diff -ruHp -X badboys linux-orig/fs/nfs/symlink.c linux-2.1.95/fs/nfs/symlink.c
--- linux-orig/fs/nfs/symlink.c Tue Apr 14 00:40:23 1998
+++ linux-2.1.95/fs/nfs/symlink.c Tue Apr 14 02:18:54 1998
@@ -94,7 +94,7 @@ nfs_follow_link(struct dentry * dentry,
path[len] = 0;
kfree(mem);
- result = lookup_dentry(path, base, 1);
+ result = lookup_dentry(path, base, 0);
kfree(path);
out:
return result;
diff -ruHp -X badboys linux-orig/fs/proc/proc_devtree.c linux-2.1.95/fs/proc/proc_devtree.c
--- linux-orig/fs/proc/proc_devtree.c Tue Apr 14 00:40:21 1998
+++ linux-2.1.95/fs/proc/proc_devtree.c Tue Apr 14 02:16:51 1998
@@ -73,7 +73,7 @@ static struct dentry *devtree_follow_lin
de = (struct proc_dir_entry *) dentry->inode->u.generic_ip;
link = (char *) de->data;
- return lookup_dentry(link, base, 1);
+ return lookup_dentry(link, base, 0);
}
static int devtree_readlink(struct dentry *dentry, char *buffer, int buflen)
diff -ruHp -X badboys linux-orig/fs/proc/root.c linux-2.1.95/fs/proc/root.c
--- linux-orig/fs/proc/root.c Tue Apr 14 00:40:20 1998
+++ linux-2.1.95/fs/proc/root.c Tue Apr 14 02:15:14 1998
@@ -387,7 +387,7 @@ static struct dentry * proc_self_follow_
char tmp[30];
sprintf(tmp, "%d", current->pid);
- return lookup_dentry(tmp, base, 1);
+ return lookup_dentry(tmp, base, 0);
}
int proc_readlink(struct dentry * dentry, char * buffer, int buflen)
@@ -429,7 +429,7 @@ struct dentry * proc_follow_link(struct
if (de->readlink_proc)
len = de->readlink_proc(de, page);
- d = lookup_dentry(page, base, 1);
+ d = lookup_dentry(page, base, 0);
free_page((unsigned long) page);
return d;
}
diff -ruHp -X badboys linux-orig/fs/romfs/inode.c linux-2.1.95/fs/romfs/inode.c
--- linux-orig/fs/romfs/inode.c Tue Apr 14 00:40:32 1998
+++ linux-2.1.95/fs/romfs/inode.c Tue Apr 14 02:21:25 1998
@@ -469,7 +469,7 @@ static struct dentry *romfs_follow_link(
} else
link[len] = 0;
- dentry = lookup_dentry(link, base, 1);
+ dentry = lookup_dentry(link, base, 0);
kfree(link);
if (0) {
diff -ruHp -X badboys linux-orig/fs/sysv/symlink.c linux-2.1.95/fs/sysv/symlink.c
--- linux-orig/fs/sysv/symlink.c Tue Apr 14 00:40:26 1998
+++ linux-2.1.95/fs/sysv/symlink.c Tue Apr 14 02:19:42 1998
@@ -58,7 +58,7 @@ static struct dentry *sysv_follow_link(s
return ERR_PTR(-EIO);
}
UPDATE_ATIME(inode);
- base = lookup_dentry(bh->b_data, base, 1);
+ base = lookup_dentry(bh->b_data, base, 0);
brelse(bh);
return base;
}
diff -ruHp -X badboys linux-orig/fs/ufs/ufs_symlink.c linux-2.1.95/fs/ufs/ufs_symlink.c
--- linux-orig/fs/ufs/ufs_symlink.c Tue Apr 14 00:40:32 1998
+++ linux-2.1.95/fs/ufs/ufs_symlink.c Tue Apr 14 02:20:17 1998
@@ -103,7 +103,7 @@ ufs_follow_link(struct dentry * dentry,
} else /* fast symlink */ {
link = (char *)&(inode->u.ufs_i.i_u1.i_symlink[0]);
}
- base = lookup_dentry(link, base, 1);
+ base = lookup_dentry(link, base, 0);
brelse (bh);
return base;
}
diff -ruHp -X badboys linux-orig/fs/umsdos/symlink.c linux-2.1.95/fs/umsdos/symlink.c
--- linux-orig/fs/umsdos/symlink.c Tue Apr 14 00:40:25 1998
+++ linux-2.1.95/fs/umsdos/symlink.c Tue Apr 14 02:24:05 1998
@@ -128,7 +128,7 @@ static struct dentry *UMSDOS_followlink(
} else
symname[len] = 0;
- dentry = lookup_dentry(symname, base, 1);
+ dentry = lookup_dentry(symname, base, 0);
kfree(symname);
if (0) {
diff -ruHp -X badboys linux-orig/CREDITS linux-2.1.95/CREDITS
--- linux-orig/CREDITS Tue Apr 14 07:42:11 1998
+++ linux/CREDITS Tue Apr 14 07:43:30 1998
@@ -39,6 +39,7 @@
P: 1024/85AD9EED AD C0 49 08 91 67 DF D7 FA 04 1A EE 09 E8 44 B0
D: Unix98 pty support.
D: APM update to 1.2 spec.
+D: do_follow_link() rewrite to support deeply-nested symlinks.
N: Erik Andersen
E: andersee@debian.org
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu