FreeBSD/Linux Kernel Cross Reference
sys/fs/jfs/jfs_extent.c

     /*
      *   Copyright (c) International Business Machines Corp., 2000-2002
      *
      *   This program is free software;  you can redistribute it and/or modify
      *   it under the terms of the GNU General Public License as published by
      *   the Free Software Foundation; either version 2 of the License, or 
      *   (at your option) any later version.
      * 
      *   This program is distributed in the hope that it will be useful,
     *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
     *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
     *   the GNU General Public License for more details.
     *
     *   You should have received a copy of the GNU General Public License
     *   along with this program;  if not, write to the Free Software 
     *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
     */
    
    #include <linux/fs.h>
    #include "jfs_incore.h"
    #include "jfs_dmap.h"
    #include "jfs_extent.h"
    #include "jfs_debug.h"
    
    /*
     * forward references
     */
    static int extBalloc(struct inode *, s64, s64 *, s64 *);
    #ifdef _NOTYET
    static int extBrealloc(struct inode *, s64, s64, s64 *, s64 *);
    #endif
    static s64 extRoundDown(s64 nb);
    
    /*
     * external references
     */
    extern int dbExtend(struct inode *, s64, s64, s64);
    extern int jfs_commit_inode(struct inode *, int);
    
    
    #define DPD(a)          (printk("(a): %d\n",(a)))
    #define DPC(a)          (printk("(a): %c\n",(a)))
    #define DPL1(a)                                 \
    {                                               \
            if ((a) >> 32)                          \
                    printk("(a): %x%08x  ",(a));    \
            else                                    \
                    printk("(a): %x  ",(a) << 32);  \
    }
    #define DPL(a)                                  \
    {                                               \
            if ((a) >> 32)                          \
                    printk("(a): %x%08x\n",(a));    \
            else                                    \
                    printk("(a): %x\n",(a) << 32);  \
    }
    
    #define DPD1(a)         (printk("(a): %d  ",(a)))
    #define DPX(a)          (printk("(a): %08x\n",(a)))
    #define DPX1(a)         (printk("(a): %08x  ",(a)))
    #define DPS(a)          (printk("%s\n",(a)))
    #define DPE(a)          (printk("\nENTERING: %s\n",(a)))
    #define DPE1(a)          (printk("\nENTERING: %s",(a)))
    #define DPS1(a)         (printk("  %s  ",(a)))
    
    
    /*
     * NAME:        extAlloc()
     *
     * FUNCTION:    allocate an extent for a specified page range within a
     *              file.
     *
     * PARAMETERS:
     *      ip      - the inode of the file.
     *      xlen    - requested extent length.
     *      pno     - the starting page number with the file.
     *      xp      - pointer to an xad.  on entry, xad describes an
     *                extent that is used as an allocation hint if the
     *                xaddr of the xad is non-zero.  on successful exit,
     *                the xad describes the newly allocated extent.
     *      abnr    - boolean_t indicating whether the newly allocated extent
     *                should be marked as allocated but not recorded.
     *
     * RETURN VALUES:
     *      0       - success
     *      EIO     - i/o error.
     *      ENOSPC  - insufficient disk resources.
     */
    int
    extAlloc(struct inode *ip, s64 xlen, s64 pno, xad_t * xp, boolean_t abnr)
    {
            struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
            s64 nxlen, nxaddr, xoff, hint, xaddr = 0;
            int rc;
            int xflag;
    
            /* This blocks if we are low on resources */
            txBeginAnon(ip->i_sb);
    
           /* Avoid race with jfs_commit_inode() */
           down(&JFS_IP(ip)->commit_sem);
   
           /* validate extent length */
           if (xlen > MAXXLEN)
                   xlen = MAXXLEN;
   
           /* get the page's starting extent offset */
           xoff = pno << sbi->l2nbperpage;
   
           /* check if an allocation hint was provided */
           if ((hint = addressXAD(xp))) {
                   /* get the size of the extent described by the hint */
                   nxlen = lengthXAD(xp);
   
                   /* check if the hint is for the portion of the file
                    * immediately previous to the current allocation
                    * request and if hint extent has the same abnr
                    * value as the current request.  if so, we can
                    * extend the hint extent to include the current
                    * extent if we can allocate the blocks immediately
                    * following the hint extent.
                    */
                   if (offsetXAD(xp) + nxlen == xoff &&
                       abnr == ((xp->flag & XAD_NOTRECORDED) ? TRUE : FALSE))
                           xaddr = hint + nxlen;
   
                   /* adjust the hint to the last block of the extent */
                   hint += (nxlen - 1);
           }
   
           /* allocate the disk blocks for the extent.  initially, extBalloc()
            * will try to allocate disk blocks for the requested size (xlen). 
            * if this fails (xlen contigious free blocks not avaliable), it'll
            * try to allocate a smaller number of blocks (producing a smaller
            * extent), with this smaller number of blocks consisting of the
            * requested number of blocks rounded down to the next smaller
            * power of 2 number (i.e. 16 -> 8).  it'll continue to round down
            * and retry the allocation until the number of blocks to allocate
            * is smaller than the number of blocks per page.
            */
           nxlen = xlen;
           if ((rc = extBalloc(ip, hint ? hint : INOHINT(ip), &nxlen, &nxaddr))) {
                   up(&JFS_IP(ip)->commit_sem);
                   return (rc);
           }
   
           /* determine the value of the extent flag */
           xflag = (abnr == TRUE) ? XAD_NOTRECORDED : 0;
   
           /* if we can extend the hint extent to cover the current request, 
            * extend it.  otherwise, insert a new extent to
            * cover the current request.
            */
           if (xaddr && xaddr == nxaddr)
                   rc = xtExtend(0, ip, xoff, (int) nxlen, 0);
           else
                   rc = xtInsert(0, ip, xflag, xoff, (int) nxlen, &nxaddr, 0);
   
           /* if the extend or insert failed, 
            * free the newly allocated blocks and return the error.
            */
           if (rc) {
                   dbFree(ip, nxaddr, nxlen);
                   up(&JFS_IP(ip)->commit_sem);
                   return (rc);
           }
   
           /* update the number of blocks allocated to the file */
           ip->i_blocks += LBLK2PBLK(ip->i_sb, nxlen);
   
           /* set the results of the extent allocation */
           XADaddress(xp, nxaddr);
           XADlength(xp, nxlen);
           XADoffset(xp, xoff);
           xp->flag = xflag;
   
           mark_inode_dirty(ip);
           set_cflag(COMMIT_Syncdata, ip);
   
           up(&JFS_IP(ip)->commit_sem);
           /*
            * COMMIT_SyncList flags an anonymous tlock on page that is on
            * sync list.
            * We need to commit the inode to get the page written disk.
            */
           if (test_and_clear_cflag(COMMIT_Synclist,ip))
                   jfs_commit_inode(ip, 0);
   
           return (0);
   }
   
   
   #ifdef _NOTYET
   /*
    * NAME:        extRealloc()
    *
    * FUNCTION:    extend the allocation of a file extent containing a
    *              partial back last page.
    *
    * PARAMETERS:
    *      ip      - the inode of the file.
    *      cp      - cbuf for the partial backed last page.
    *      xlen    - request size of the resulting extent.
    *      xp      - pointer to an xad. on successful exit, the xad
    *                describes the newly allocated extent.
    *      abnr    - boolean_t indicating whether the newly allocated extent
    *                should be marked as allocated but not recorded.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    *      ENOSPC  - insufficient disk resources.
    */
   int extRealloc(struct inode *ip, s64 nxlen, xad_t * xp, boolean_t abnr)
   {
           struct super_block *sb = ip->i_sb;
           s64 xaddr, xlen, nxaddr, delta, xoff;
           s64 ntail, nextend, ninsert;
           int rc, nbperpage = JFS_SBI(sb)->nbperpage;
           int xflag;
   
           /* This blocks if we are low on resources */
           txBeginAnon(ip->i_sb);
   
           down(&JFS_IP(ip)->commit_sem);
           /* validate extent length */
           if (nxlen > MAXXLEN)
                   nxlen = MAXXLEN;
   
           /* get the extend (partial) page's disk block address and
            * number of blocks.
            */
           xaddr = addressXAD(xp);
           xlen = lengthXAD(xp);
           xoff = offsetXAD(xp);
   
           /* if the extend page is abnr and if the request is for
            * the extent to be allocated and recorded, 
            * make the page allocated and recorded.
            */
           if ((xp->flag & XAD_NOTRECORDED) && !abnr) {
                   xp->flag = 0;
                   if ((rc = xtUpdate(0, ip, xp)))
                           goto exit;
           }
   
           /* try to allocated the request number of blocks for the
            * extent.  dbRealloc() first tries to satisfy the request
            * by extending the allocation in place. otherwise, it will
            * try to allocate a new set of blocks large enough for the
            * request.  in satisfying a request, dbReAlloc() may allocate
            * less than what was request but will always allocate enough
            * space as to satisfy the extend page.
            */
           if ((rc = extBrealloc(ip, xaddr, xlen, &nxlen, &nxaddr)))
                   goto exit;
   
           delta = nxlen - xlen;
   
           /* check if the extend page is not abnr but the request is abnr
            * and the allocated disk space is for more than one page.  if this
            * is the case, there is a miss match of abnr between the extend page
            * and the one or more pages following the extend page.  as a result,
            * two extents will have to be manipulated. the first will be that
            * of the extent of the extend page and will be manipulated thru
            * an xtExtend() or an xtTailgate(), depending upon whether the
            * disk allocation occurred as an inplace extension.  the second
            * extent will be manipulated (created) through an xtInsert() and
            * will be for the pages following the extend page.
            */
           if (abnr && (!(xp->flag & XAD_NOTRECORDED)) && (nxlen > nbperpage)) {
                   ntail = nbperpage;
                   nextend = ntail - xlen;
                   ninsert = nxlen - nbperpage;
   
                   xflag = XAD_NOTRECORDED;
           } else {
                   ntail = nxlen;
                   nextend = delta;
                   ninsert = 0;
   
                   xflag = xp->flag;
           }
   
           /* if we were able to extend the disk allocation in place,
            * extend the extent.  otherwise, move the extent to a
            * new disk location.
            */
           if (xaddr == nxaddr) {
                   /* extend the extent */
                   if ((rc = xtExtend(0, ip, xoff + xlen, (int) nextend, 0))) {
                           dbFree(ip, xaddr + xlen, delta);
                           goto exit;
                   }
           } else {
                   /*
                    * move the extent to a new location:
                    *
                    * xtTailgate() accounts for relocated tail extent;
                    */
                   if ((rc = xtTailgate(0, ip, xoff, (int) ntail, nxaddr, 0))) {
                           dbFree(ip, nxaddr, nxlen);
                           goto exit;
                   }
           }
   
   
           /* check if we need to also insert a new extent */
           if (ninsert) {
                   /* perform the insert.  if it fails, free the blocks
                    * to be inserted and make it appear that we only did
                    * the xtExtend() or xtTailgate() above.
                    */
                   xaddr = nxaddr + ntail;
                   if (xtInsert (0, ip, xflag, xoff + ntail, (int) ninsert,
                                 &xaddr, 0)) {
                           dbFree(ip, xaddr, (s64) ninsert);
                           delta = nextend;
                           nxlen = ntail;
                           xflag = 0;
                   }
           }
   
           /* update the inode with the number of blocks allocated */
           ip->i_blocks += LBLK2PBLK(sb, delta);
   
           /* set the return results */
           XADaddress(xp, nxaddr);
           XADlength(xp, nxlen);
           XADoffset(xp, xoff);
           xp->flag = xflag;
   
           mark_inode_dirty(ip);
   exit:
           up(&JFS_IP(ip)->commit_sem);
           return (rc);
   }
   #endif                  /* _NOTYET */
   
   
   /*
    * NAME:        extHint()
    *
    * FUNCTION:    produce an extent allocation hint for a file offset.
    *
    * PARAMETERS:
    *      ip      - the inode of the file.
    *      offset  - file offset for which the hint is needed.
    *      xp      - pointer to the xad that is to be filled in with
    *                the hint.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    */
   int extHint(struct inode *ip, s64 offset, xad_t * xp)
   {
           struct super_block *sb = ip->i_sb;
           struct xadlist xadl;
           struct lxdlist lxdl;
           lxd_t lxd;
           s64 prev;
           int rc, nbperpage = JFS_SBI(sb)->nbperpage;
   
           /* init the hint as "no hint provided" */
           XADaddress(xp, 0);
   
           /* determine the starting extent offset of the page previous
            * to the page containing the offset.
            */
           prev = ((offset & ~POFFSET) >> JFS_SBI(sb)->l2bsize) - nbperpage;
   
           /* if the offsets in the first page of the file,
            * no hint provided.
            */
           if (prev < 0)
                   return (0);
   
           /* prepare to lookup the previous page's extent info */
           lxdl.maxnlxd = 1;
           lxdl.nlxd = 1;
           lxdl.lxd = &lxd;
           LXDoffset(&lxd, prev)
               LXDlength(&lxd, nbperpage);
   
           xadl.maxnxad = 1;
           xadl.nxad = 0;
           xadl.xad = xp;
   
           /* perform the lookup */
           if ((rc = xtLookupList(ip, &lxdl, &xadl, 0)))
                   return (rc);
   
           /* check if not extent exists for the previous page.  
            * this is possible for sparse files.
            */
           if (xadl.nxad == 0) {
   //              assert(ISSPARSE(ip));
                   return (0);
           }
   
           /* only preserve the abnr flag within the xad flags
            * of the returned hint.
            */
           xp->flag &= XAD_NOTRECORDED;
   
           assert(xadl.nxad == 1);
           assert(lengthXAD(xp) == nbperpage);
   
           return (0);
   }
   
   
   /*
    * NAME:        extRecord()
    *
    * FUNCTION:    change a page with a file from not recorded to recorded.
    *
    * PARAMETERS:
    *      ip      - inode of the file.
    *      cp      - cbuf of the file page.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    *      ENOSPC  - insufficient disk resources.
    */
   int extRecord(struct inode *ip, xad_t * xp)
   {
           int rc;
   
           txBeginAnon(ip->i_sb);
   
           down(&JFS_IP(ip)->commit_sem);
   
           /* update the extent */
           rc = xtUpdate(0, ip, xp);
   
           up(&JFS_IP(ip)->commit_sem);
           return (rc);
   }
   
   
   #ifdef _NOTYET
   /*
    * NAME:        extFill()
    *
    * FUNCTION:    allocate disk space for a file page that represents
    *              a file hole.
    *
    * PARAMETERS:
    *      ip      - the inode of the file.
    *      cp      - cbuf of the file page represent the hole.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    *      ENOSPC  - insufficient disk resources.
    */
   int extFill(struct inode *ip, xad_t * xp)
   {
           int rc, nbperpage = JFS_SBI(ip->i_sb)->nbperpage;
           s64 blkno = offsetXAD(xp) >> ip->i_blksize;
   
   //      assert(ISSPARSE(ip));
   
           /* initialize the extent allocation hint */
           XADaddress(xp, 0);
   
           /* allocate an extent to fill the hole */
           if ((rc = extAlloc(ip, nbperpage, blkno, xp, FALSE)))
                   return (rc);
   
           assert(lengthPXD(xp) == nbperpage);
   
           return (0);
   }
   #endif                  /* _NOTYET */
   
   
   /*
    * NAME:        extBalloc()
    *
    * FUNCTION:    allocate disk blocks to form an extent.
    *
    *              initially, we will try to allocate disk blocks for the
    *              requested size (nblocks).  if this fails (nblocks 
    *              contigious free blocks not avaliable), we'll try to allocate
    *              a smaller number of blocks (producing a smaller extent), with
    *              this smaller number of blocks consisting of the requested
    *              number of blocks rounded down to the next smaller power of 2
    *              number (i.e. 16 -> 8).  we'll continue to round down and
    *              retry the allocation until the number of blocks to allocate
    *              is smaller than the number of blocks per page.
    *              
    * PARAMETERS:
    *      ip       - the inode of the file.
    *      hint     - disk block number to be used as an allocation hint.
    *      *nblocks - pointer to an s64 value.  on entry, this value specifies
    *                 the desired number of block to be allocated. on successful
    *                 exit, this value is set to the number of blocks actually
    *                 allocated.
    *      blkno    - pointer to a block address that is filled in on successful
    *                 return with the starting block number of the newly 
    *                 allocated block range.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    *      ENOSPC  - insufficient disk resources.
    */
   static int
   extBalloc(struct inode *ip, s64 hint, s64 * nblocks, s64 * blkno)
   {
           struct jfs_inode_info *ji = JFS_IP(ip);
           struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
           s64 nb, nblks, daddr, max;
           int rc, nbperpage = sbi->nbperpage;
           struct bmap *bmp = sbi->bmap;
           int ag;
   
           /* get the number of blocks to initially attempt to allocate.
            * we'll first try the number of blocks requested unless this
            * number is greater than the maximum number of contigious free
            * blocks in the map. in that case, we'll start off with the 
            * maximum free.
            */
           max = (s64) 1 << bmp->db_maxfreebud;
           if (*nblocks >= max && *nblocks > nbperpage)
                   nb = nblks = (max > nbperpage) ? max : nbperpage;
           else
                   nb = nblks = *nblocks;
   
           /* try to allocate blocks */
           while ((rc = dbAlloc(ip, hint, nb, &daddr))) {
                   /* if something other than an out of space error,
                    * stop and return this error.
                    */
                   if (rc != ENOSPC)
                           return (rc);
   
                   /* decrease the allocation request size */
                   nb = min(nblks, extRoundDown(nb));
   
                   /* give up if we cannot cover a page */
                   if (nb < nbperpage)
                           return (rc);
           }
   
           *nblocks = nb;
           *blkno = daddr;
   
           if (S_ISREG(ip->i_mode) && (ji->fileset == FILESYSTEM_I)) {
                   ag = BLKTOAG(daddr, sbi);
                   if (ji->active_ag == -1) {
                           atomic_inc(&bmp->db_active[ag]);
                           ji->active_ag = ag;
                   } else if (ji->active_ag != ag) {
                           atomic_dec(&bmp->db_active[ji->active_ag]);
                           atomic_inc(&bmp->db_active[ag]);
                           ji->active_ag = ag;
                   }
           }
   
           return (0);
   }
   
   
   #ifdef _NOTYET
   /*
    * NAME:        extBrealloc()
    *
    * FUNCTION:    attempt to extend an extent's allocation.
    *
    *              initially, we will try to extend the extent's allocation
    *              in place.  if this fails, we'll try to move the extent
    *              to a new set of blocks. if moving the extent, we initially
    *              will try to allocate disk blocks for the requested size
    *              (nnew).  if this fails  (nnew contigious free blocks not
    *              avaliable), we'll try  to allocate a smaller number of
    *              blocks (producing a smaller extent), with this smaller
    *              number of blocks consisting of the requested number of
    *              blocks rounded down to the next smaller power of 2
    *              number (i.e. 16 -> 8).  we'll continue to round down and
    *              retry the allocation until the number of blocks to allocate
    *              is smaller than the number of blocks per page.
    *              
    * PARAMETERS:
    *      ip       - the inode of the file.
    *      blkno    - starting block number of the extents current allocation.
    *      nblks    - number of blocks within the extents current allocation.
    *      newnblks - pointer to a s64 value.  on entry, this value is the
    *                 the new desired extent size (number of blocks).  on
    *                 successful exit, this value is set to the extent's actual
    *                 new size (new number of blocks).
    *      newblkno - the starting block number of the extents new allocation.
    *
    * RETURN VALUES:
    *      0       - success
    *      EIO     - i/o error.
    *      ENOSPC  - insufficient disk resources.
    */
   static int
   extBrealloc(struct inode *ip,
               s64 blkno, s64 nblks, s64 * newnblks, s64 * newblkno)
   {
           int rc;
   
           /* try to extend in place */
           if ((rc = dbExtend(ip, blkno, nblks, *newnblks - nblks)) == 0) {
                   *newblkno = blkno;
                   return (0);
           } else {
                   if (rc != ENOSPC)
                           return (rc);
           }
   
           /* in place extension not possible.  
            * try to move the extent to a new set of blocks.
            */
           return (extBalloc(ip, blkno, newnblks, newblkno));
   }
   #endif                  /* _NOTYET */
   
   
   /*
    * NAME:        extRoundDown()
    *
    * FUNCTION:    round down a specified number of blocks to the next
    *              smallest power of 2 number.
    *
    * PARAMETERS:
    *      nb      - the inode of the file.
    *
    * RETURN VALUES:
    *      next smallest power of 2 number.
    */
   static s64 extRoundDown(s64 nb)
   {
           int i;
           u64 m, k;
   
           for (i = 0, m = (u64) 1 << 63; i < 64; i++, m >>= 1) {
                   if (m & nb)
                           break;
           }
   
           i = 63 - i;
           k = (u64) 1 << i;
           k = ((k - 1) & nb) ? k : k >> 1;
   
           return (k);
   }

Cache object: 0f8a5ff91fec6c21c83e30629620c373