make triply indirected blocks work

SCCS-vsn: sys/ufs/lfs/lfs_balloc.c 7.21

diff --git a/usr/src/sys/ufs/lfs/lfs_balloc.c b/usr/src/sys/ufs/lfs/lfs_balloc.c
index bbcdc04..e73827d 100644 (file)
--- a/usr/src/sys/ufs/lfs/lfs_balloc.c
+++ b/usr/src/sys/ufs/lfs/lfs_balloc.c
@@ -4,7 +4,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %sccs.include.redist.c%
  *

- *     @(#)lfs_balloc.c        7.20 (Berkeley) %G%
+ *     @(#)lfs_balloc.c        7.21 (Berkeley) %G%

  */
 
 #include <sys/param.h>
  */
 
 #include <sys/param.h>


@@ -27,6 +27,27 @@
  * Bmap converts a the logical block number of a file to its physical block
  * number on the disk. The conversion is done by using the logical block
  * number to index into the array of block pointers described by the dinode.
  * Bmap converts a the logical block number of a file to its physical block
  * number on the disk. The conversion is done by using the logical block
  * number to index into the array of block pointers described by the dinode.

+ *
+ * LFS has a different version of bmap from FFS because of a naming conflict.
+ * In FFS, meta blocks are given real disk addresses at allocation time, and
+ * are linked into the device vnode, using a logical block number which is
+ * the same as the physical block number.  This can't be done by LFS because
+ * blocks aren't given disk addresses until they're written, so there's no
+ * way to distinguish the meta-data blocks for one file from any other file.
+ * This means that meta-data blocks have to be on the vnode for the file so
+ * they can be found, and have to have "names" different from the standard
+ * data blocks.  To do this, we divide the name space into positive and
+ * negative block numbers, and give the meta-data blocks negative logical
+ * numbers.
+ *
+ * The mapping for meta-data blocks is as follows (assuming a 4K block size):
+ *
+ * -1 -- single indirect
+ * -2 -- double indirect:
+ *             single indirect blocks -4, -1027
+ * -3 -- triple indirect:
+ *             double indirect blocks -1028, -2051
+ *             single indirect blocks -2052, -(1M + 2052 - 1)

  */
 int
 lfs_bmap(vp, bn, vpp, bnp)
  */
 int
 lfs_bmap(vp, bn, vpp, bnp)


@@ -38,12 +59,10 @@ lfs_bmap(vp, bn, vpp, bnp)
        register struct inode *ip;
        register struct lfs *fs;
        register daddr_t nb;
        register struct inode *ip;
        register struct lfs *fs;
        register daddr_t nb;

-       struct vnode *devvp;

        struct buf *bp;
        struct buf *bp;

-       daddr_t *bap, daddr;
-       daddr_t lbn_ind;
-       int j, off, sh;
-       int error;
+       struct vnode *devvp;
+       daddr_t *bap, daddr, lbn_ind, doing_a_triple;
+       int error, j, off, sh, sh_ind;

 
        /*
         * Check for underlying vnode requests and ensure that logical
 
        /*
         * Check for underlying vnode requests and ensure that logical


@@ -54,43 +73,35 @@ lfs_bmap(vp, bn, vpp, bnp)
                *vpp = ip->i_devvp;
        if (bnp == NULL)
                return (0);
                *vpp = ip->i_devvp;
        if (bnp == NULL)
                return (0);

-printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
-       fs = ip->i_lfs;
-
-       /*
-        * We access all blocks in the cache, even indirect blocks by means
-        * of a logical address. Indirect blocks (single, double, triple) all
-        * have negative block numbers. The first NDADDR blocks are direct
-        * blocks, the first NIADDR negative blocks are the indirect block
-        * pointers.  The single, double and triple indirect blocks in the
-        * inode * are addressed: -1, -2 and -3 respectively.  
-        *
-        * XXX
-        * We don't handle triple indirect at all.
-        *
-        * XXX
-        * This panic shouldn't be here???
-        */
-       if (bn < 0)
-               panic("lfs_bmap: negative indirect block number %d", bn);

 
 

+#ifdef VERBOSE
+printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
+#endif

        /* The first NDADDR blocks are direct blocks. */
        if (bn < NDADDR) {
                nb = ip->i_db[bn];
        /* The first NDADDR blocks are direct blocks. */
        if (bn < NDADDR) {
                nb = ip->i_db[bn];

-               if (nb == 0) {
+               if (nb == LFS_UNUSED_DADDR)

                        *bnp = UNASSIGNED;
                        *bnp = UNASSIGNED;

-                       return (0);
-               }
-               *bnp = nb;
+               else
+                       *bnp = nb;

                return (0);
        }
 
                return (0);
        }
 

-       /* Determine the number of levels of indirection. */
+       /* 
+        * The first NIADDR negative blocks are the indirect block pointers.
+        * Determine the number of levels of indirection.  After this loop
+        * is done, sh indicates the number of data blocks possible at the
+        * given level of indirection, lbn_ind is the logical block number
+        * of the next indirect block to retrieve, and NIADDR - j is the
+        * number of levels of indirection needed to locate the requested
+        * block.
+        */
+       fs = ip->i_lfs;

        sh = 1;
        bn -= NDADDR;
        lbn_ind = 0;
        for (j = NIADDR; j > 0; j--) {
        sh = 1;
        bn -= NDADDR;
        lbn_ind = 0;
        for (j = NIADDR; j > 0; j--) {

-               lbn_ind--;
+               --lbn_ind;

                sh *= NINDIR(fs);
                if (bn < sh)
                        break;
                sh *= NINDIR(fs);
                if (bn < sh)
                        break;


@@ -99,25 +110,48 @@ printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
        if (j == 0)
                return (EFBIG);
 
        if (j == 0)
                return (EFBIG);
 

-       /* Fetch through the indirect blocks. */
-       vp = ITOV(ip);
+       /* 
+        * Fetch through the indirect blocks.  At each iteration, off is the
+        * offset into the bap array which is an array of disk addresses at
+        * the current level of indirection.
+        */
+       bap = ip->i_ib;
+       bp = NULL;

        devvp = VFSTOUFS(vp->v_mount)->um_devvp;
        devvp = VFSTOUFS(vp->v_mount)->um_devvp;

-       for (off = NIADDR - j, bap = ip->i_ib; j <= NIADDR; j++) {
-               if((daddr = bap[off]) == 0) {
+       off = NIADDR - j;
+       doing_a_triple = 0;
+       for (; j <= NIADDR; j++) {
+               /*
+                * In LFS, it's possible to have a block appended to a file
+                * for which the meta-blocks have not yet been allocated.
+                * This is a win if the file never gets written or if the
+                * file's growing.
+                */
+               if ((daddr = bap[off]) == 0) {

                        daddr = UNASSIGNED;
                        break;
                }
                        daddr = UNASSIGNED;
                        break;
                }

+               /*
+                * Read in the appropriate indirect block.  LFS can't do a
+                * bread because bread knows that FFS will hand it the device
+                * vnode, not the file vnode, so the b_dev and b_blkno would
+                * be wrong.
+                *
+                * XXX
+                * This REALLY needs to be fixed, at the very least it needs
+                * to be rethought when the buffer cache goes away.
+                */

                if (bp)
                        brelse(bp);
                bp = getblk(vp, lbn_ind, fs->lfs_bsize);
                if (bp->b_flags & (B_DONE | B_DELWRI)) {
                        trace(TR_BREADHIT, pack(vp, size), lbn_ind);
                } else {
                if (bp)
                        brelse(bp);
                bp = getblk(vp, lbn_ind, fs->lfs_bsize);
                if (bp->b_flags & (B_DONE | B_DELWRI)) {
                        trace(TR_BREADHIT, pack(vp, size), lbn_ind);
                } else {

-                       trace(TR_BREADMISS, pack(vp, size), lbn_ind);
-                       bp->b_blkno = daddr;

                        bp->b_flags |= B_READ;
                        bp->b_flags |= B_READ;

+                       bp->b_blkno = daddr;

                        bp->b_dev = devvp->v_rdev;
                        (devvp->v_op->vop_strategy)(bp);
                        bp->b_dev = devvp->v_rdev;
                        (devvp->v_op->vop_strategy)(bp);

+                       trace(TR_BREADMISS, pack(vp, size), lbn_ind);

                        curproc->p_stats->p_ru.ru_inblock++;    /* XXX */
                        if (error = biowait(bp)) {
                                brelse(bp);
                        curproc->p_stats->p_ru.ru_inblock++;    /* XXX */
                        if (error = biowait(bp)) {
                                brelse(bp);


@@ -127,7 +161,40 @@ printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
                bap = bp->b_un.b_daddr;
                sh /= NINDIR(fs);
                off = (bn / sh) % NINDIR(fs);
                bap = bp->b_un.b_daddr;
                sh /= NINDIR(fs);
                off = (bn / sh) % NINDIR(fs);

-               lbn_ind  = -(NIADDR + 1 + off);
+
+               /*
+                * Ahem.  Now the disgusting part.  We have to figure out
+                * the logical block number for the next meta-data block.
+                * There are really three equations...  Note the clever
+                * use of the doing_a_triple variable to hold the last
+                * offset into the block of pointers.
+                */
+               switch(j) {
+               case 1:
+                       /* The triple indirect block found in the inode. */
+                       doing_a_triple = off;
+                       lbn_ind = -(NIADDR + 1 + off + NINDIR(fs));
+                       break;
+               case 2:
+                       /*
+                        * The double indirect block found after indirecting
+                        * through a triple indirect block.
+                        */
+                       if (doing_a_triple)
+                               lbn_ind = -((doing_a_triple + 2) * NINDIR(fs) +
+                                   NIADDR + 1);
+
+                       /* The double indirect block found in the inode. */
+                       else
+                               lbn_ind = -(NIADDR + 1 + off);
+                       break;
+               case 3:
+                       /*
+                        * A single indirect block; lbn_ind isn't used again,
+                        * so don't do anything.
+                        */
+                       break;
+               }

        }
        if (bp)
                brelse(bp);
        }
        if (bp)
                brelse(bp);