git.oblomov.eu Git - linux-2.6/blob - fs/jfs/jfs_extent.c

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