fs/jfs/jfs_extent.c

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