1 element cache per process saves 12% of namei cost!

[unix-history] / 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 d3db509..de82274 100644 (file)
--- 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"
 
 #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/conf.h"
 #include "../h/uio.h"
 #include "../h/nami.h"

+#include "../h/kernel.h"

 
 struct buf *blkatoff();
 int    dirchk = 0;
 
 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 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 */
        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) {
         * 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);
                        goto bad;
                }
                brelse(nbp);


@@ -179,10 +181,38 @@ dirloop2:
                slotfreespace = 0;
                slotneeded = DIRSIZ(&u.u_dent);
        }
                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.
                /*
                 * 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;
        }
                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
 /* 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 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;
                        u.u_count = 0;

-               else {
+               } else {

                        u.u_offset = slotoffset;
                        u.u_count = slotsize;
                }
                        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);
         */
        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;
         */
        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;
 
        /*
        fs = dp->i_fs;
 
        /*


@@ -537,7 +610,7 @@ direnter(ip)
 {
        register struct direct *ep, *nep;
        struct buf *bp;
 {
        register struct direct *ep, *nep;
        struct buf *bp;

-       int loc, freespace;
+       int loc, spacefree, error = 0;

        u_int dsize;
        int newentrysize;
        char *dirbuf;
        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;
                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);
                    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
 
        /*
         * 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);
         */
        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);
         */
        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) {
        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 */
                        ep = (struct direct *)((char *)ep + dsize);
                } else {
                        /* overwrite; nothing there; header is ours */

-                       freespace += dsize;     
+                       spacefree += dsize;     

                }
                dsize = DIRSIZ(nep);
                }
                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);
        }
                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) {
         * 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");
                        panic("wdir: compact1");

-               u.u_dent.d_reclen = freespace + dsize;
+               u.u_dent.d_reclen = spacefree + dsize;

        } else {
        } else {

-               if (freespace < newentrysize)
+               if (spacefree < newentrysize)

                        panic("wdir: compact2");
                        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);
        }
                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);
        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.
                 */
                /*
                 * 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);
                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.
 /*
  * 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;
  */
 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;
        int error, count;

+#define        MINDIRSIZ (sizeof (struct dirtemplate) / 2)

 
        for (off = 0; off < ip->i_size; off += dp->d_reclen) {
 
        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);
                        return (0);

+               /* skip empty entries */

                if (dp->d_ino == 0)
                        continue;
                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_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);
 }
                        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);
+}