fs/jfs/jfs_extent.c

   1 /*
   2  *   Copyright (C) International Business Machines Corp., 2000-2003
   3  *
   4  *   This program is free software;  you can redistribute it and/or modify
   5  *   it under the terms of the GNU General Public License as published by
   6  *   the Free Software Foundation; either version 2 of the License, or
   7  *   (at your option) any later version.
   8  *
   9  *   This program is distributed in the hope that it will be useful,
  10  *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
  11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
  12  *   the GNU General Public License for more details.
  13  *
  14  *   You should have received a copy of the GNU General Public License
  15  *   along with this program;  if not, write to the Free Software
  16  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  17  */
  18
  19 #include <linux/fs.h>
  20 #include "jfs_incore.h"
  21 #include "jfs_superblock.h"
  22 #include "jfs_dmap.h"
  23 #include "jfs_extent.h"
  24 #include "jfs_debug.h"
  25
  26 /*
  27  * forward references
  28  */
  29 static int extBalloc(struct inode *, s64, s64 *, s64 *);
  30 #ifdef _NOTYET
  31 static int extBrealloc(struct inode *, s64, s64, s64 *, s64 *);
  32 #endif
  33 static s64 extRoundDown(s64 nb);
  34
  35 /*
  36  * external references
  37  */
  38 extern int jfs_commit_inode(struct inode *, int);
  39
  40
  41 #define DPD(a)          (printk("(a): %d\n",(a)))
  42 #define DPC(a)          (printk("(a): %c\n",(a)))
  43 #define DPL1(a)                                 \
  44 {                                               \
  45         if ((a) >> 32)                          \
  46                 printk("(a): %x%08x  ",(a));    \
  47         else                                    \
  48                 printk("(a): %x  ",(a) << 32);  \
  49 }
  50 #define DPL(a)                                  \
  51 {                                               \
  52         if ((a) >> 32)                          \
  53                 printk("(a): %x%08x\n",(a));    \
  54         else                                    \
  55                 printk("(a): %x\n",(a) << 32);  \
  56 }
  57
  58 #define DPD1(a)         (printk("(a): %d  ",(a)))
  59 #define DPX(a)          (printk("(a): %08x\n",(a)))
  60 #define DPX1(a)         (printk("(a): %08x  ",(a)))
  61 #define DPS(a)          (printk("%s\n",(a)))
  62 #define DPE(a)          (printk("\nENTERING: %s\n",(a)))
  63 #define DPE1(a)          (printk("\nENTERING: %s",(a)))
  64 #define DPS1(a)         (printk("  %s  ",(a)))
  65
  66
  67 /*
  68  * NAME:        extAlloc()
  69  *
  70  * FUNCTION:    allocate an extent for a specified page range within a
  71  *              file.
  72  *
  73  * PARAMETERS:
  74  *      ip      - the inode of the file.
  75  *      xlen    - requested extent length.
  76  *      pno     - the starting page number with the file.
  77  *      xp      - pointer to an xad.  on entry, xad describes an
  78  *                extent that is used as an allocation hint if the
  79  *                xaddr of the xad is non-zero.  on successful exit,
  80  *                the xad describes the newly allocated extent.
  81  *      abnr    - boolean_t indicating whether the newly allocated extent
  82  *                should be marked as allocated but not recorded.
  83  *
  84  * RETURN VALUES:
  85  *      0       - success
  86  *      -EIO    - i/o error.
  87  *      -ENOSPC - insufficient disk resources.
  88  */
  89 int
  90 extAlloc(struct inode *ip, s64 xlen, s64 pno, xad_t * xp, boolean_t abnr)
  91 {
  92         struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
  93         s64 nxlen, nxaddr, xoff, hint, xaddr = 0;
  94         int rc;
  95         int xflag;
  96
  97         /* This blocks if we are low on resources */
  98         txBeginAnon(ip->i_sb);
  99
 100         /* Avoid race with jfs_commit_inode() */
 101         down(&JFS_IP(ip)->commit_sem);
 102
 103         /* validate extent length */
 104         if (xlen > MAXXLEN)
 105                 xlen = MAXXLEN;
 106
 107         /* get the page's starting extent offset */
 108         xoff = pno << sbi->l2nbperpage;
 109
 110         /* check if an allocation hint was provided */
 111         if ((hint = addressXAD(xp))) {
 112                 /* get the size of the extent described by the hint */
 113                 nxlen = lengthXAD(xp);
 114
 115                 /* check if the hint is for the portion of the file
 116                  * immediately previous to the current allocation
 117                  * request and if hint extent has the same abnr
 118                  * value as the current request.  if so, we can
 119                  * extend the hint extent to include the current
 120                  * extent if we can allocate the blocks immediately
 121                  * following the hint extent.
 122                  */
 123                 if (offsetXAD(xp) + nxlen == xoff &&
 124                     abnr == ((xp->flag & XAD_NOTRECORDED) ? TRUE : FALSE))
 125                         xaddr = hint + nxlen;
 126
 127                 /* adjust the hint to the last block of the extent */
 128                 hint += (nxlen - 1);
 129         }
 130
 131         /* allocate the disk blocks for the extent.  initially, extBalloc()
 132          * will try to allocate disk blocks for the requested size (xlen).
 133          * if this fails (xlen contigious free blocks not avaliable), it'll
 134          * try to allocate a smaller number of blocks (producing a smaller
 135          * extent), with this smaller number of blocks consisting of the
 136          * requested number of blocks rounded down to the next smaller
 137          * power of 2 number (i.e. 16 -> 8).  it'll continue to round down
 138          * and retry the allocation until the number of blocks to allocate
 139          * is smaller than the number of blocks per page.
 140          */
 141         nxlen = xlen;
 142         if ((rc = extBalloc(ip, hint ? hint : INOHINT(ip), &nxlen, &nxaddr))) {
 143                 up(&JFS_IP(ip)->commit_sem);
 144                 return (rc);
 145         }
 146
 147         /* determine the value of the extent flag */
 148         xflag = (abnr == TRUE) ? XAD_NOTRECORDED : 0;
 149
 150         /* if we can extend the hint extent to cover the current request,
 151          * extend it.  otherwise, insert a new extent to
 152          * cover the current request.
 153          */
 154         if (xaddr && xaddr == nxaddr)
 155                 rc = xtExtend(0, ip, xoff, (int) nxlen, 0);
 156         else
 157                 rc = xtInsert(0, ip, xflag, xoff, (int) nxlen, &nxaddr, 0);
 158
 159         /* if the extend or insert failed,
 160          * free the newly allocated blocks and return the error.
 161          */
 162         if (rc) {
 163                 dbFree(ip, nxaddr, nxlen);
 164                 up(&JFS_IP(ip)->commit_sem);
 165                 return (rc);
 166         }
 167
 168         /* update the number of blocks allocated to the file */
 169         ip->i_blocks += LBLK2PBLK(ip->i_sb, nxlen);
 170
 171         /* set the results of the extent allocation */
 172         XADaddress(xp, nxaddr);
 173         XADlength(xp, nxlen);
 174         XADoffset(xp, xoff);
 175         xp->flag = xflag;
 176
 177         mark_inode_dirty(ip);
 178
 179         up(&JFS_IP(ip)->commit_sem);
 180         /*
 181          * COMMIT_SyncList flags an anonymous tlock on page that is on
 182          * sync list.
 183          * We need to commit the inode to get the page written disk.
 184          */
 185         if (test_and_clear_cflag(COMMIT_Synclist,ip))
 186                 jfs_commit_inode(ip, 0);
 187
 188         return (0);
 189 }
 190
 191
 192 #ifdef _NOTYET
 193 /*
 194  * NAME:        extRealloc()
 195  *
 196  * FUNCTION:    extend the allocation of a file extent containing a
 197  *              partial back last page.
 198  *
 199  * PARAMETERS:
 200  *      ip      - the inode of the file.
 201  *      cp      - cbuf for the partial backed last page.
 202  *      xlen    - request size of the resulting extent.
 203  *      xp      - pointer to an xad. on successful exit, the xad
 204  *                describes the newly allocated extent.
 205  *      abnr    - boolean_t indicating whether the newly allocated extent
 206  *                should be marked as allocated but not recorded.
 207  *
 208  * RETURN VALUES:
 209  *      0       - success
 210  *      -EIO    - i/o error.
 211  *      -ENOSPC - insufficient disk resources.
 212  */
 213 int extRealloc(struct inode *ip, s64 nxlen, xad_t * xp, boolean_t abnr)
 214 {
 215         struct super_block *sb = ip->i_sb;
 216         s64 xaddr, xlen, nxaddr, delta, xoff;
 217         s64 ntail, nextend, ninsert;
 218         int rc, nbperpage = JFS_SBI(sb)->nbperpage;
 219         int xflag;
 220
 221         /* This blocks if we are low on resources */
 222         txBeginAnon(ip->i_sb);
 223
 224         down(&JFS_IP(ip)->commit_sem);
 225         /* validate extent length */
 226         if (nxlen > MAXXLEN)
 227                 nxlen = MAXXLEN;
 228
 229         /* get the extend (partial) page's disk block address and
 230          * number of blocks.
 231          */
 232         xaddr = addressXAD(xp);
 233         xlen = lengthXAD(xp);
 234         xoff = offsetXAD(xp);
 235
 236         /* if the extend page is abnr and if the request is for
 237          * the extent to be allocated and recorded,
 238          * make the page allocated and recorded.
 239          */
 240         if ((xp->flag & XAD_NOTRECORDED) && !abnr) {
 241                 xp->flag = 0;
 242                 if ((rc = xtUpdate(0, ip, xp)))
 243                         goto exit;
 244         }
 245
 246         /* try to allocated the request number of blocks for the
 247          * extent.  dbRealloc() first tries to satisfy the request
 248          * by extending the allocation in place. otherwise, it will
 249          * try to allocate a new set of blocks large enough for the
 250          * request.  in satisfying a request, dbReAlloc() may allocate
 251          * less than what was request but will always allocate enough
 252          * space as to satisfy the extend page.
 253          */
 254         if ((rc = extBrealloc(ip, xaddr, xlen, &nxlen, &nxaddr)))
 255                 goto exit;
 256
 257         delta = nxlen - xlen;
 258
 259         /* check if the extend page is not abnr but the request is abnr
 260          * and the allocated disk space is for more than one page.  if this
 261          * is the case, there is a miss match of abnr between the extend page
 262          * and the one or more pages following the extend page.  as a result,
 263          * two extents will have to be manipulated. the first will be that
 264          * of the extent of the extend page and will be manipulated thru
 265          * an xtExtend() or an xtTailgate(), depending upon whether the
 266          * disk allocation occurred as an inplace extension.  the second
 267          * extent will be manipulated (created) through an xtInsert() and
 268          * will be for the pages following the extend page.
 269          */
 270         if (abnr && (!(xp->flag & XAD_NOTRECORDED)) && (nxlen > nbperpage)) {
 271                 ntail = nbperpage;
 272                 nextend = ntail - xlen;
 273                 ninsert = nxlen - nbperpage;
 274
 275                 xflag = XAD_NOTRECORDED;
 276         } else {
 277                 ntail = nxlen;
 278                 nextend = delta;
 279                 ninsert = 0;
 280
 281                 xflag = xp->flag;
 282         }
 283
 284         /* if we were able to extend the disk allocation in place,
 285          * extend the extent.  otherwise, move the extent to a
 286          * new disk location.
 287          */
 288         if (xaddr == nxaddr) {
 289                 /* extend the extent */
 290                 if ((rc = xtExtend(0, ip, xoff + xlen, (int) nextend, 0))) {
 291                         dbFree(ip, xaddr + xlen, delta);
 292                         goto exit;
 293                 }
 294         } else {
 295                 /*
 296                  * move the extent to a new location:
 297                  *
 298                  * xtTailgate() accounts for relocated tail extent;
 299                  */
 300                 if ((rc = xtTailgate(0, ip, xoff, (int) ntail, nxaddr, 0))) {
 301                         dbFree(ip, nxaddr, nxlen);
 302                         goto exit;
 303                 }
 304         }
 305
 306
 307         /* check if we need to also insert a new extent */
 308         if (ninsert) {
 309                 /* perform the insert.  if it fails, free the blocks
 310                  * to be inserted and make it appear that we only did
 311                  * the xtExtend() or xtTailgate() above.
 312                  */
 313                 xaddr = nxaddr + ntail;
 314                 if (xtInsert (0, ip, xflag, xoff + ntail, (int) ninsert,
 315                               &xaddr, 0)) {
 316                         dbFree(ip, xaddr, (s64) ninsert);
 317                         delta = nextend;
 318                         nxlen = ntail;
 319                         xflag = 0;
 320                 }
 321         }
 322
 323         /* update the inode with the number of blocks allocated */
 324         ip->i_blocks += LBLK2PBLK(sb, delta);
 325
 326         /* set the return results */
 327         XADaddress(xp, nxaddr);
 328         XADlength(xp, nxlen);
 329         XADoffset(xp, xoff);
 330         xp->flag = xflag;
 331
 332         mark_inode_dirty(ip);
 333 exit:
 334         up(&JFS_IP(ip)->commit_sem);
 335         return (rc);
 336 }
 337 #endif                  /* _NOTYET */
 338
 339
 340 /*
 341  * NAME:        extHint()
 342  *
 343  * FUNCTION:    produce an extent allocation hint for a file offset.
 344  *
 345  * PARAMETERS:
 346  *      ip      - the inode of the file.
 347  *      offset  - file offset for which the hint is needed.
 348  *      xp      - pointer to the xad that is to be filled in with
 349  *                the hint.
 350  *
 351  * RETURN VALUES:
 352  *      0       - success
 353  *      -EIO    - i/o error.
 354  */
 355 int extHint(struct inode *ip, s64 offset, xad_t * xp)
 356 {
 357         struct super_block *sb = ip->i_sb;
 358         struct xadlist xadl;
 359         struct lxdlist lxdl;
 360         lxd_t lxd;
 361         s64 prev;
 362         int rc, nbperpage = JFS_SBI(sb)->nbperpage;
 363
 364         /* init the hint as "no hint provided" */
 365         XADaddress(xp, 0);
 366
 367         /* determine the starting extent offset of the page previous
 368          * to the page containing the offset.
 369          */
 370         prev = ((offset & ~POFFSET) >> JFS_SBI(sb)->l2bsize) - nbperpage;
 371
 372         /* if the offsets in the first page of the file,
 373          * no hint provided.
 374          */
 375         if (prev < 0)
 376                 return (0);
 377
 378         /* prepare to lookup the previous page's extent info */
 379         lxdl.maxnlxd = 1;
 380         lxdl.nlxd = 1;
 381         lxdl.lxd = &lxd;
 382         LXDoffset(&lxd, prev)
 383             LXDlength(&lxd, nbperpage);
 384
 385         xadl.maxnxad = 1;
 386         xadl.nxad = 0;
 387         xadl.xad = xp;
 388
 389         /* perform the lookup */
 390         if ((rc = xtLookupList(ip, &lxdl, &xadl, 0)))
 391                 return (rc);
 392
 393         /* check if not extent exists for the previous page.
 394          * this is possible for sparse files.
 395          */
 396         if (xadl.nxad == 0) {
 397 //              assert(ISSPARSE(ip));
 398                 return (0);
 399         }
 400
 401         /* only preserve the abnr flag within the xad flags
 402          * of the returned hint.
 403          */
 404         xp->flag &= XAD_NOTRECORDED;
 405
 406         if(xadl.nxad != 1 || lengthXAD(xp) != nbperpage) {
 407                 jfs_error(ip->i_sb, "extHint: corrupt xtree");
 408                 return -EIO;
 409         }
 410
 411         return (0);
 412 }
 413
 414
 415 /*
 416  * NAME:        extRecord()
 417  *
 418  * FUNCTION:    change a page with a file from not recorded to recorded.
 419  *
 420  * PARAMETERS:
 421  *      ip      - inode of the file.
 422  *      cp      - cbuf of the file page.
 423  *
 424  * RETURN VALUES:
 425  *      0       - success
 426  *      -EIO    - i/o error.
 427  *      -ENOSPC - insufficient disk resources.
 428  */
 429 int extRecord(struct inode *ip, xad_t * xp)
 430 {
 431         int rc;
 432
 433         txBeginAnon(ip->i_sb);
 434
 435         down(&JFS_IP(ip)->commit_sem);
 436
 437         /* update the extent */
 438         rc = xtUpdate(0, ip, xp);
 439
 440         up(&JFS_IP(ip)->commit_sem);
 441         return rc;
 442 }
 443
 444
 445 #ifdef _NOTYET
 446 /*
 447  * NAME:        extFill()
 448  *
 449  * FUNCTION:    allocate disk space for a file page that represents
 450  *              a file hole.
 451  *
 452  * PARAMETERS:
 453  *      ip      - the inode of the file.
 454  *      cp      - cbuf of the file page represent the hole.
 455  *
 456  * RETURN VALUES:
 457  *      0       - success
 458  *      -EIO    - i/o error.
 459  *      -ENOSPC - insufficient disk resources.
 460  */
 461 int extFill(struct inode *ip, xad_t * xp)
 462 {
 463         int rc, nbperpage = JFS_SBI(ip->i_sb)->nbperpage;
 464         s64 blkno = offsetXAD(xp) >> ip->i_blksize;
 465
 466 //      assert(ISSPARSE(ip));
 467
 468         /* initialize the extent allocation hint */
 469         XADaddress(xp, 0);
 470
 471         /* allocate an extent to fill the hole */
 472         if ((rc = extAlloc(ip, nbperpage, blkno, xp, FALSE)))
 473                 return (rc);
 474
 475         assert(lengthPXD(xp) == nbperpage);
 476
 477         return (0);
 478 }
 479 #endif                  /* _NOTYET */
 480
 481
 482 /*
 483  * NAME:        extBalloc()
 484  *
 485  * FUNCTION:    allocate disk blocks to form an extent.
 486  *
 487  *              initially, we will try to allocate disk blocks for the
 488  *              requested size (nblocks).  if this fails (nblocks
 489  *              contigious free blocks not avaliable), we'll try to allocate
 490  *              a smaller number of blocks (producing a smaller extent), with
 491  *              this smaller number of blocks consisting of the requested
 492  *              number of blocks rounded down to the next smaller power of 2
 493  *              number (i.e. 16 -> 8).  we'll continue to round down and
 494  *              retry the allocation until the number of blocks to allocate
 495  *              is smaller than the number of blocks per page.
 496  *
 497  * PARAMETERS:
 498  *      ip       - the inode of the file.
 499  *      hint     - disk block number to be used as an allocation hint.
 500  *      *nblocks - pointer to an s64 value.  on entry, this value specifies
 501  *                 the desired number of block to be allocated. on successful
 502  *                 exit, this value is set to the number of blocks actually
 503  *                 allocated.
 504  *      blkno    - pointer to a block address that is filled in on successful
 505  *                 return with the starting block number of the newly
 506  *                 allocated block range.
 507  *
 508  * RETURN VALUES:
 509  *      0       - success
 510  *      -EIO    - i/o error.
 511  *      -ENOSPC - insufficient disk resources.
 512  */
 513 static int
 514 extBalloc(struct inode *ip, s64 hint, s64 * nblocks, s64 * blkno)
 515 {
 516         struct jfs_inode_info *ji = JFS_IP(ip);
 517         struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
 518         s64 nb, nblks, daddr, max;
 519         int rc, nbperpage = sbi->nbperpage;
 520         struct bmap *bmp = sbi->bmap;
 521         int ag;
 522
 523         /* get the number of blocks to initially attempt to allocate.
 524          * we'll first try the number of blocks requested unless this
 525          * number is greater than the maximum number of contigious free
 526          * blocks in the map. in that case, we'll start off with the
 527          * maximum free.
 528          */
 529         max = (s64) 1 << bmp->db_maxfreebud;
 530         if (*nblocks >= max && *nblocks > nbperpage)
 531                 nb = nblks = (max > nbperpage) ? max : nbperpage;
 532         else
 533                 nb = nblks = *nblocks;
 534
 535         /* try to allocate blocks */
 536         while ((rc = dbAlloc(ip, hint, nb, &daddr))) {
 537                 /* if something other than an out of space error,
 538                  * stop and return this error.
 539                  */
 540                 if (rc != -ENOSPC)
 541                         return (rc);
 542
 543                 /* decrease the allocation request size */
 544                 nb = min(nblks, extRoundDown(nb));
 545
 546                 /* give up if we cannot cover a page */
 547                 if (nb < nbperpage)
 548                         return (rc);
 549         }
 550
 551         *nblocks = nb;
 552         *blkno = daddr;
 553
 554         if (S_ISREG(ip->i_mode) && (ji->fileset == FILESYSTEM_I)) {
 555                 ag = BLKTOAG(daddr, sbi);
 556                 if (ji->active_ag == -1) {
 557                         atomic_inc(&bmp->db_active[ag]);
 558                         ji->active_ag = ag;
 559                 } else if (ji->active_ag != ag) {
 560                         atomic_dec(&bmp->db_active[ji->active_ag]);
 561                         atomic_inc(&bmp->db_active[ag]);
 562                         ji->active_ag = ag;
 563                 }
 564         }
 565
 566         return (0);
 567 }
 568
 569
 570 #ifdef _NOTYET
 571 /*
 572  * NAME:        extBrealloc()
 573  *
 574  * FUNCTION:    attempt to extend an extent's allocation.
 575  *
 576  *              initially, we will try to extend the extent's allocation
 577  *              in place.  if this fails, we'll try to move the extent
 578  *              to a new set of blocks. if moving the extent, we initially
 579  *              will try to allocate disk blocks for the requested size
 580  *              (nnew).  if this fails  (nnew contigious free blocks not
 581  *              avaliable), we'll try  to allocate a smaller number of
 582  *              blocks (producing a smaller extent), with this smaller
 583  *              number of blocks consisting of the requested number of
 584  *              blocks rounded down to the next smaller power of 2
 585  *              number (i.e. 16 -> 8).  we'll continue to round down and
 586  *              retry the allocation until the number of blocks to allocate
 587  *              is smaller than the number of blocks per page.
 588  *
 589  * PARAMETERS:
 590  *      ip       - the inode of the file.
 591  *      blkno    - starting block number of the extents current allocation.
 592  *      nblks    - number of blocks within the extents current allocation.
 593  *      newnblks - pointer to a s64 value.  on entry, this value is the
 594  *                 the new desired extent size (number of blocks).  on
 595  *                 successful exit, this value is set to the extent's actual
 596  *                 new size (new number of blocks).
 597  *      newblkno - the starting block number of the extents new allocation.
 598  *
 599  * RETURN VALUES:
 600  *      0       - success
 601  *      -EIO    - i/o error.
 602  *      -ENOSPC - insufficient disk resources.
 603  */
 604 static int
 605 extBrealloc(struct inode *ip,
 606             s64 blkno, s64 nblks, s64 * newnblks, s64 * newblkno)
 607 {
 608         int rc;
 609
 610         /* try to extend in place */
 611         if ((rc = dbExtend(ip, blkno, nblks, *newnblks - nblks)) == 0) {
 612                 *newblkno = blkno;
 613                 return (0);
 614         } else {
 615                 if (rc != -ENOSPC)
 616                         return (rc);
 617         }
 618
 619         /* in place extension not possible.
 620          * try to move the extent to a new set of blocks.
 621          */
 622         return (extBalloc(ip, blkno, newnblks, newblkno));
 623 }
 624 #endif                  /* _NOTYET */
 625
 626
 627 /*
 628  * NAME:        extRoundDown()
 629  *
 630  * FUNCTION:    round down a specified number of blocks to the next
 631  *              smallest power of 2 number.
 632  *
 633  * PARAMETERS:
 634  *      nb      - the inode of the file.
 635  *
 636  * RETURN VALUES:
 637  *      next smallest power of 2 number.
 638  */
 639 static s64 extRoundDown(s64 nb)
 640 {
 641         int i;
 642         u64 m, k;
 643
 644         for (i = 0, m = (u64) 1 << 63; i < 64; i++, m >>= 1) {
 645                 if (m & nb)
 646                         break;
 647         }
 648
 649         i = 63 - i;
 650         k = (u64) 1 << i;
 651         k = ((k - 1) & nb) ? k : k >> 1;
 652
 653         return (k);
 654 }