X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/05d2bbcedef006859e4bd5a4de2fee2fdb1b7030..84ef30ec63c4dcbcbdebd8dec2777adcc4332cef:/usr/src/sys/ufs/ffs/ufs_lookup.c

diff --git a/usr/src/sys/ufs/ffs/ufs_lookup.c b/usr/src/sys/ufs/ffs/ufs_lookup.c
index d3db509c64..de8227466b 100644
--- a/usr/src/sys/ufs/ffs/ufs_lookup.c
+++ b/usr/src/sys/ufs/ffs/ufs_lookup.c
@@ -1,4 +1,4 @@
-/*	ufs_lookup.c	4.32	82/12/21	*/
+/*	ufs_lookup.c	6.3	83/12/03	*/
 
 #include "../h/param.h"
 #include "../h/systm.h"
@@ -11,6 +11,7 @@
 #include "../h/conf.h"
 #include "../h/uio.h"
 #include "../h/nami.h"
+#include "../h/kernel.h"
 
 struct	buf *blkatoff();
 int	dirchk = 0;
@@ -79,7 +80,8 @@ namei(func, flag, follow)
 	int slotfreespace;		/* amount of space free in slot */
 	int slotneeded;			/* size of the entry we're seeking */
 /* */
-	int dirsize;
+	int numdirpasses;		/* strategy for directory search */
+	int endsearch;			/* offset to end directory search */
 	int prevoff;			/* u.u_offset of previous entry */
 	int nlink = 0;			/* number of symbolic links taken */
 	struct inode *pdp;		/* saved dp during symlink work */
@@ -159,8 +161,8 @@ dirloop2:
 	 * e.g. like "/." or ".".
 	 */
 	if (u.u_dent.d_name[0] == 0) {
-		if (flag) {
-			u.u_error = ENOENT;
+		if (flag || lockparent) {
+			u.u_error = EISDIR;
 			goto bad;
 		}
 		brelse(nbp);
@@ -179,10 +181,38 @@ dirloop2:
 		slotfreespace = 0;
 		slotneeded = DIRSIZ(&u.u_dent);
 	}
+	/*
+	 * If this is the same directory that this process
+	 * previously searched, pick up where we last left off.
+	 * We cache only lookups as these are the most common,
+	 * and have the greatest payoff. Caching CREATE has little
+	 * benefit as it usually must search the entire directory
+	 * to determine that the entry does not exist. Caching the
+	 * location of the last DELETE has not reduced profiling time
+	 * and hence has been removed in the interest of simplicity.
+	 */
+	if (flag != LOOKUP || dp->i_number != u.u_ncache.nc_inumber ||
+	    dp->i_dev != u.u_ncache.nc_dev) {
+		u.u_offset = 0;
+		numdirpasses = 1;
+	} else {
+		if (dp->i_mtime >= u.u_ncache.nc_time) {
+			u.u_ncache.nc_prevoffset &= ~(DIRBLKSIZ - 1);
+			u.u_ncache.nc_time = time.tv_sec;
+		}
+		u.u_offset = u.u_ncache.nc_prevoffset;
+		entryoffsetinblock = blkoff(fs, u.u_offset);
+		if (entryoffsetinblock != 0) {
+			bp = blkatoff(dp, u.u_offset, (char **)0);
+			if (bp == 0)
+				goto bad;
+		}
+		numdirpasses = 2;
+	}
+	endsearch = roundup(dp->i_size, DIRBLKSIZ);
 
-	dirsize = roundup(dp->i_size, DIRBLKSIZ);
-	u.u_offset = 0;
-	while (u.u_offset < dirsize) {
+searchloop:
+	while (u.u_offset < endsearch) {
 		/*
 		 * If offset is on a block boundary,
 		 * read the next directory block.
@@ -273,6 +303,16 @@ dirloop2:
 		u.u_offset += ep->d_reclen;
 		entryoffsetinblock += ep->d_reclen;
 	}
+	/*
+	 * If we started in the middle of the directory and failed 
+	 * to find our target, we must check the beginning as well.
+	 */
+	if (numdirpasses == 2) {
+		numdirpasses--;
+		u.u_offset = 0;
+		endsearch = u.u_ncache.nc_prevoffset;
+		goto searchloop;
+	}
 /* notfound: */
 	/*
 	 * If creating, and at end of pathname and current
@@ -294,9 +334,10 @@ dirloop2:
 		 * If we found a slot, then the new entry can be
 		 * put in the range [u.u_offset..u.u_offset+u.u_count)
 		 */
-		if (slotstatus == NONE)
+		if (slotstatus == NONE) {
+			u.u_offset = roundup(dp->i_size, DIRBLKSIZ);
 			u.u_count = 0;
-		else {
+		} else {
 			u.u_offset = slotoffset;
 			u.u_count = slotsize;
 		}
@@ -329,8 +370,19 @@ found:
 	}
 
 	/*
-	 * Found component in pathname; save directory
-	 * entry in u.u_dent, and release directory buffer.
+	 * Found component in pathname.
+	 * If final component of path name, save information
+	 * in the cache as to where the entry was found.
+	 */
+	if (*cp == '\0' && flag == LOOKUP) {
+		u.u_ncache.nc_prevoffset = u.u_offset;
+		u.u_ncache.nc_inumber = dp->i_number;
+		u.u_ncache.nc_dev = dp->i_dev;
+		u.u_ncache.nc_time = time.tv_sec;
+	}
+	/*
+	 * Save directory entry in u.u_dent,
+	 * and release directory buffer.
 	 */
 	bcopy((caddr_t)ep, (caddr_t)&u.u_dent, (u_int)DIRSIZ(ep));
 	brelse(bp);
@@ -428,18 +480,39 @@ found:
 	}
 
 	/*
-	 * Check for symbolic link, which may require us
-	 * to massage the name before we continue translation.
-	 * To avoid deadlock have to unlock the current directory,
-	 * but don't iput it because we may need it again (if
-	 * the symbolic link is relative to .).  Instead save
-	 * it (unlocked) as pdp.
+	 * Check for symbolic link, which may require us to massage the
+	 * name before we continue translation.  We do not `iput' the
+	 * directory because we may need it again if the symbolic link
+	 * is relative to the current directory.  Instead we save it
+	 * unlocked as "pdp".  We must get the target inode before unlocking
+	 * the directory to insure that the inode will not be removed
+	 * before we get it.  We prevent deadlock by always fetching
+	 * inodes from the root, moving down the directory tree. Thus
+	 * when following backward pointers ".." we must unlock the
+	 * parent directory before getting the requested directory.
+	 * There is a potential race condition here if both the current
+	 * and parent directories are removed before the `iget' for the
+	 * inode associated with ".." returns.  We hope that this occurs
+	 * infrequently since we cannot avoid this race condition without
+	 * implementing a sophisticated deadlock detection algorithm.
+	 * Note also that this simple deadlock detection scheme will not
+	 * work if the file system has any hard links other than ".."
+	 * that point backwards in the directory structure.
 	 */
 	pdp = dp;
-	iunlock(pdp);
-	dp = iget(dp->i_dev, fs, u.u_dent.d_ino);
-	if (dp == NULL)
-		goto bad2;
+	if (bcmp(u.u_dent.d_name, "..", 3) == 0) {
+		iunlock(pdp);	/* race to get the inode */
+		dp = iget(dp->i_dev, fs, u.u_dent.d_ino);
+		if (dp == NULL)
+			goto bad2;
+	} else if (dp->i_number == u.u_dent.d_ino) {
+		dp->i_count++;	/* we want ourself, ie "." */
+	} else {
+		dp = iget(dp->i_dev, fs, u.u_dent.d_ino);
+		iunlock(pdp);
+		if (dp == NULL)
+			goto bad2;
+	}
 	fs = dp->i_fs;
 
 	/*
@@ -537,7 +610,7 @@ direnter(ip)
 {
 	register struct direct *ep, *nep;
 	struct buf *bp;
-	int loc, freespace;
+	int loc, spacefree, error = 0;
 	u_int dsize;
 	int newentrysize;
 	char *dirbuf;
@@ -555,10 +628,10 @@ direnter(ip)
 		if (u.u_offset&(DIRBLKSIZ-1))
 			panic("wdir: newblk");
 		u.u_dent.d_reclen = DIRBLKSIZ;
-		(void) rdwri(UIO_WRITE, u.u_pdir, (caddr_t)&u.u_dent,
+		error = rdwri(UIO_WRITE, u.u_pdir, (caddr_t)&u.u_dent,
 		    newentrysize, u.u_offset, 1, (int *)0);
 		iput(u.u_pdir);
-		return;
+		return (error);
 	}
 
 	/*
@@ -580,12 +653,12 @@ direnter(ip)
 
 	/*
 	 * Get the block containing the space for the new directory
-	 * entry.
+	 * entry.  Should return error by result instead of u.u_error.
 	 */
 	bp = blkatoff(u.u_pdir, u.u_offset, (char **)&dirbuf);
 	if (bp == 0) {
 		iput(u.u_pdir);
-		return;
+		return (u.u_error);
 	}
 
 	/*
@@ -596,7 +669,7 @@ direnter(ip)
 	 */
 	ep = (struct direct *)dirbuf;
 	dsize = DIRSIZ(ep);
-	freespace = ep->d_reclen - dsize;
+	spacefree = ep->d_reclen - dsize;
 	for (loc = ep->d_reclen; loc < u.u_count; ) {
 		nep = (struct direct *)(dirbuf + loc);
 		if (ep->d_ino) {
@@ -605,10 +678,10 @@ direnter(ip)
 			ep = (struct direct *)((char *)ep + dsize);
 		} else {
 			/* overwrite; nothing there; header is ours */
-			freespace += dsize;	
+			spacefree += dsize;	
 		}
 		dsize = DIRSIZ(nep);
-		freespace += nep->d_reclen - dsize;
+		spacefree += nep->d_reclen - dsize;
 		loc += nep->d_reclen;
 		bcopy((caddr_t)nep, (caddr_t)ep, dsize);
 	}
@@ -617,13 +690,13 @@ direnter(ip)
 	 * copy in the new entry, and write out the block.
 	 */
 	if (ep->d_ino == 0) {
-		if (freespace + dsize < newentrysize)
+		if (spacefree + dsize < newentrysize)
 			panic("wdir: compact1");
-		u.u_dent.d_reclen = freespace + dsize;
+		u.u_dent.d_reclen = spacefree + dsize;
 	} else {
-		if (freespace < newentrysize)
+		if (spacefree < newentrysize)
 			panic("wdir: compact2");
-		u.u_dent.d_reclen = freespace;
+		u.u_dent.d_reclen = spacefree;
 		ep->d_reclen = dsize;
 		ep = (struct direct *)((char *)ep + dsize);
 	}
@@ -631,6 +704,7 @@ direnter(ip)
 	bwrite(bp);
 	u.u_pdir->i_flag |= IUPD|ICHG;
 	iput(u.u_pdir);
+	return (error);
 }
 
 /*
@@ -662,7 +736,6 @@ dirremove()
 		/*
 		 * Collapse new free space into previous entry.
 		 */
-		u.u_error = 0;	/* XXX */
 		bp = blkatoff(dp, (int)(u.u_offset - u.u_count), (char **)&ep);
 		if (bp == 0)
 			return (0);
@@ -722,30 +795,102 @@ blkatoff(ip, offset, res)
 /*
  * Check if a directory is empty or not.
  * Inode supplied must be locked.
+ *
+ * Using a struct dirtemplate here is not precisely
+ * what we want, but better than using a struct direct.
+ *
+ * NB: does not handle corrupted directories.
  */
 dirempty(ip)
 	register struct inode *ip;
 {
 	register off_t off;
-	struct direct dbuf;
-	register struct direct *dp = &dbuf;
+	struct dirtemplate dbuf;
+	register struct direct *dp = (struct direct *)&dbuf;
 	int error, count;
+#define	MINDIRSIZ (sizeof (struct dirtemplate) / 2)
 
 	for (off = 0; off < ip->i_size; off += dp->d_reclen) {
-		error = rdwri(UIO_READ, ip, (caddr_t)dp,
-			sizeof (struct direct), off, 1, &count);
-		count = sizeof (struct direct) - count;
-#define	MINDIRSIZ (sizeof (struct direct) - (MAXNAMLEN + 1))
-		if (error || count < MINDIRSIZ || count < DIRSIZ(dp))
+		error = rdwri(UIO_READ, ip, (caddr_t)dp, MINDIRSIZ,
+		    off, 1, &count);
+		/*
+		 * Since we read MINDIRSIZ, residual must
+		 * be 0 unless we're at end of file.
+		 */
+		if (error || count != 0)
 			return (0);
+		/* skip empty entries */
 		if (dp->d_ino == 0)
 			continue;
+		/* accept only "." and ".." */
+		if (dp->d_namlen > 2)
+			return (0);
 		if (dp->d_name[0] != '.')
 			return (0);
-		if (dp->d_namlen == 1 ||
-		    (dp->d_namlen == 2 && dp->d_name[1] == '.'))
+		/*
+		 * At this point d_namlen must be 1 or 2.
+		 * 1 implies ".", 2 implies ".." if second
+		 * char is also "."
+		 */
+		if (dp->d_namlen == 1 || dp->d_name[1] == '.')
 			continue;
 		return (0);
 	}
 	return (1);
 }
+
+/*
+ * Check if source directory is in the path of the target directory.
+ * Target is supplied locked, source is unlocked.
+ * The target is always iput() before returning.
+ */
+checkpath(source, target)
+	struct inode *source, *target;
+{
+	struct dirtemplate dirbuf;
+	register struct inode *ip;
+	int error = 0;
+
+	ip = target;
+	if (ip->i_number == source->i_number) {
+		error = EEXIST;
+		goto out;
+	}
+	if (ip->i_number == ROOTINO)
+		goto out;
+
+	for (;;) {
+		if ((ip->i_mode&IFMT) != IFDIR) {
+			error = ENOTDIR;
+			break;
+		}
+		error = rdwri(UIO_READ, ip, (caddr_t)&dirbuf,
+			sizeof (struct dirtemplate), (off_t)0, 1, (int *)0);
+		if (error != 0)
+			break;
+		if (dirbuf.dotdot_namlen != 2 ||
+		    bcmp(dirbuf.dotdot_name, "..", 3) != 0) {
+			error = ENOTDIR;
+			break;
+		}
+		if (dirbuf.dotdot_ino == source->i_number) {
+			error = EINVAL;
+			break;
+		}
+		if (dirbuf.dotdot_ino == ROOTINO)
+			break;
+		iput(ip);
+		ip = iget(ip->i_dev, ip->i_fs, dirbuf.dotdot_ino);
+		if (ip == NULL) {
+			error = u.u_error;
+			break;
+		}
+	}
+
+out:
+	if (error == ENOTDIR)
+		printf("checkpath: .. not a directory\n");
+	if (ip != NULL)
+		iput(ip);
+	return (error);
+}