fs/xfs/xfs_rtalloc.c

   1 /*
   2  * Copyright (c) 2000-2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * 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 the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir.h"
  28 #include "xfs_dir2.h"
  29 #include "xfs_dmapi.h"
  30 #include "xfs_mount.h"
  31 #include "xfs_bmap_btree.h"
  32 #include "xfs_alloc_btree.h"
  33 #include "xfs_ialloc_btree.h"
  34 #include "xfs_dir_sf.h"
  35 #include "xfs_dir2_sf.h"
  36 #include "xfs_attr_sf.h"
  37 #include "xfs_dinode.h"
  38 #include "xfs_inode.h"
  39 #include "xfs_btree.h"
  40 #include "xfs_ialloc.h"
  41 #include "xfs_alloc.h"
  42 #include "xfs_bmap.h"
  43 #include "xfs_rtalloc.h"
  44 #include "xfs_fsops.h"
  45 #include "xfs_error.h"
  46 #include "xfs_rw.h"
  47 #include "xfs_inode_item.h"
  48 #include "xfs_trans_space.h"
  49
  50
  51 /*
  52  * Prototypes for internal functions.
  53  */
  54
  55
  56 STATIC int xfs_rtallocate_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  57                 xfs_extlen_t, xfs_buf_t **, xfs_fsblock_t *);
  58 STATIC int xfs_rtany_summary(xfs_mount_t *, xfs_trans_t *, int, int,
  59                 xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, int *);
  60 STATIC int xfs_rtcheck_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  61                 xfs_extlen_t, int, xfs_rtblock_t *, int *);
  62 STATIC int xfs_rtfind_back(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  63                 xfs_rtblock_t, xfs_rtblock_t *);
  64 STATIC int xfs_rtfind_forw(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  65                 xfs_rtblock_t, xfs_rtblock_t *);
  66 STATIC int xfs_rtget_summary( xfs_mount_t *, xfs_trans_t *, int,
  67                 xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, xfs_suminfo_t *);
  68 STATIC int xfs_rtmodify_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  69                 xfs_extlen_t, int);
  70 STATIC int xfs_rtmodify_summary(xfs_mount_t *, xfs_trans_t *, int,
  71                 xfs_rtblock_t, int, xfs_buf_t **, xfs_fsblock_t *);
  72
  73 /*
  74  * Internal functions.
  75  */
  76
  77 /*
  78  * xfs_lowbit32: get low bit set out of 32-bit argument, -1 if none set.
  79  */
  80 STATIC int
  81 xfs_lowbit32(
  82         __uint32_t      v)
  83 {
  84         if (v)
  85                 return ffs(v) - 1;
  86         return -1;
  87 }
  88
  89 /*
  90  * Allocate space to the bitmap or summary file, and zero it, for growfs.
  91  */
  92 STATIC int                              /* error */
  93 xfs_growfs_rt_alloc(
  94         xfs_mount_t     *mp,            /* file system mount point */
  95         xfs_extlen_t    oblocks,        /* old count of blocks */
  96         xfs_extlen_t    nblocks,        /* new count of blocks */
  97         xfs_ino_t       ino)            /* inode number (bitmap/summary) */
  98 {
  99         xfs_fileoff_t   bno;            /* block number in file */
 100         xfs_buf_t       *bp;            /* temporary buffer for zeroing */
 101         int             cancelflags;    /* flags for xfs_trans_cancel */
 102         int             committed;      /* transaction committed flag */
 103         xfs_daddr_t     d;              /* disk block address */
 104         int             error;          /* error return value */
 105         xfs_fsblock_t   firstblock;     /* first block allocated in xaction */
 106         xfs_bmap_free_t flist;          /* list of freed blocks */
 107         xfs_fsblock_t   fsbno;          /* filesystem block for bno */
 108         xfs_inode_t     *ip;            /* pointer to incore inode */
 109         xfs_bmbt_irec_t map;            /* block map output */
 110         int             nmap;           /* number of block maps */
 111         int             resblks;        /* space reservation */
 112         xfs_trans_t     *tp;            /* transaction pointer */
 113
 114         /*
 115          * Allocate space to the file, as necessary.
 116          */
 117         while (oblocks < nblocks) {
 118                 tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ALLOC);
 119                 resblks = XFS_GROWFSRT_SPACE_RES(mp, nblocks - oblocks);
 120                 cancelflags = 0;
 121                 /*
 122                  * Reserve space & log for one extent added to the file.
 123                  */
 124                 if ((error = xfs_trans_reserve(tp, resblks,
 125                                 XFS_GROWRTALLOC_LOG_RES(mp), 0,
 126                                 XFS_TRANS_PERM_LOG_RES,
 127                                 XFS_DEFAULT_PERM_LOG_COUNT)))
 128                         goto error_exit;
 129                 cancelflags = XFS_TRANS_RELEASE_LOG_RES;
 130                 /*
 131                  * Lock the inode.
 132                  */
 133                 if ((error = xfs_trans_iget(mp, tp, ino, 0, XFS_ILOCK_EXCL, &ip)))
 134                         goto error_exit;
 135                 XFS_BMAP_INIT(&flist, &firstblock);
 136                 /*
 137                  * Allocate blocks to the bitmap file.
 138                  */
 139                 nmap = 1;
 140                 cancelflags |= XFS_TRANS_ABORT;
 141                 error = xfs_bmapi(tp, ip, oblocks, nblocks - oblocks,
 142                         XFS_BMAPI_WRITE | XFS_BMAPI_METADATA, &firstblock,
 143                         resblks, &map, &nmap, &flist);
 144                 if (!error && nmap < 1)
 145                         error = XFS_ERROR(ENOSPC);
 146                 if (error)
 147                         goto error_exit;
 148                 /*
 149                  * Free any blocks freed up in the transaction, then commit.
 150                  */
 151                 error = xfs_bmap_finish(&tp, &flist, firstblock, &committed);
 152                 if (error)
 153                         goto error_exit;
 154                 xfs_trans_commit(tp, XFS_TRANS_RELEASE_LOG_RES, NULL);
 155                 /*
 156                  * Now we need to clear the allocated blocks.
 157                  * Do this one block per transaction, to keep it simple.
 158                  */
 159                 cancelflags = 0;
 160                 for (bno = map.br_startoff, fsbno = map.br_startblock;
 161                      bno < map.br_startoff + map.br_blockcount;
 162                      bno++, fsbno++) {
 163                         tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ZERO);
 164                         /*
 165                          * Reserve log for one block zeroing.
 166                          */
 167                         if ((error = xfs_trans_reserve(tp, 0,
 168                                         XFS_GROWRTZERO_LOG_RES(mp), 0, 0, 0)))
 169                                 goto error_exit;
 170                         /*
 171                          * Lock the bitmap inode.
 172                          */
 173                         if ((error = xfs_trans_iget(mp, tp, ino, 0, XFS_ILOCK_EXCL,
 174                                         &ip)))
 175                                 goto error_exit;
 176                         /*
 177                          * Get a buffer for the block.
 178                          */
 179                         d = XFS_FSB_TO_DADDR(mp, fsbno);
 180                         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d,
 181                                 mp->m_bsize, 0);
 182                         if (bp == NULL) {
 183                                 error = XFS_ERROR(EIO);
 184                                 goto error_exit;
 185                         }
 186                         memset(XFS_BUF_PTR(bp), 0, mp->m_sb.sb_blocksize);
 187                         xfs_trans_log_buf(tp, bp, 0, mp->m_sb.sb_blocksize - 1);
 188                         /*
 189                          * Commit the transaction.
 190                          */
 191                         xfs_trans_commit(tp, 0, NULL);
 192                 }
 193                 /*
 194                  * Go on to the next extent, if any.
 195                  */
 196                 oblocks = map.br_startoff + map.br_blockcount;
 197         }
 198         return 0;
 199 error_exit:
 200         xfs_trans_cancel(tp, cancelflags);
 201         return error;
 202 }
 203
 204 /*
 205  * Attempt to allocate an extent minlen<=len<=maxlen starting from
 206  * bitmap block bbno.  If we don't get maxlen then use prod to trim
 207  * the length, if given.  Returns error; returns starting block in *rtblock.
 208  * The lengths are all in rtextents.
 209  */
 210 STATIC int                              /* error */
 211 xfs_rtallocate_extent_block(
 212         xfs_mount_t     *mp,            /* file system mount point */
 213         xfs_trans_t     *tp,            /* transaction pointer */
 214         xfs_rtblock_t   bbno,           /* bitmap block number */
 215         xfs_extlen_t    minlen,         /* minimum length to allocate */
 216         xfs_extlen_t    maxlen,         /* maximum length to allocate */
 217         xfs_extlen_t    *len,           /* out: actual length allocated */
 218         xfs_rtblock_t   *nextp,         /* out: next block to try */
 219         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 220         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 221         xfs_extlen_t    prod,           /* extent product factor */
 222         xfs_rtblock_t   *rtblock)       /* out: start block allocated */
 223 {
 224         xfs_rtblock_t   besti;          /* best rtblock found so far */
 225         xfs_rtblock_t   bestlen;        /* best length found so far */
 226         xfs_rtblock_t   end;            /* last rtblock in chunk */
 227         int             error;          /* error value */
 228         xfs_rtblock_t   i;              /* current rtblock trying */
 229         xfs_rtblock_t   next;           /* next rtblock to try */
 230         int             stat;           /* status from internal calls */
 231
 232         /*
 233          * Loop over all the extents starting in this bitmap block,
 234          * looking for one that's long enough.
 235          */
 236         for (i = XFS_BLOCKTOBIT(mp, bbno), besti = -1, bestlen = 0,
 237                 end = XFS_BLOCKTOBIT(mp, bbno + 1) - 1;
 238              i <= end;
 239              i++) {
 240                 /*
 241                  * See if there's a free extent of maxlen starting at i.
 242                  * If it's not so then next will contain the first non-free.
 243                  */
 244                 error = xfs_rtcheck_range(mp, tp, i, maxlen, 1, &next, &stat);
 245                 if (error) {
 246                         return error;
 247                 }
 248                 if (stat) {
 249                         /*
 250                          * i for maxlen is all free, allocate and return that.
 251                          */
 252                         error = xfs_rtallocate_range(mp, tp, i, maxlen, rbpp,
 253                                 rsb);
 254                         if (error) {
 255                                 return error;
 256                         }
 257                         *len = maxlen;
 258                         *rtblock = i;
 259                         return 0;
 260                 }
 261                 /*
 262                  * In the case where we have a variable-sized allocation
 263                  * request, figure out how big this free piece is,
 264                  * and if it's big enough for the minimum, and the best
 265                  * so far, remember it.
 266                  */
 267                 if (minlen < maxlen) {
 268                         xfs_rtblock_t   thislen;        /* this extent size */
 269
 270                         thislen = next - i;
 271                         if (thislen >= minlen && thislen > bestlen) {
 272                                 besti = i;
 273                                 bestlen = thislen;
 274                         }
 275                 }
 276                 /*
 277                  * If not done yet, find the start of the next free space.
 278                  */
 279                 if (next < end) {
 280                         error = xfs_rtfind_forw(mp, tp, next, end, &i);
 281                         if (error) {
 282                                 return error;
 283                         }
 284                 } else
 285                         break;
 286         }
 287         /*
 288          * Searched the whole thing & didn't find a maxlen free extent.
 289          */
 290         if (minlen < maxlen && besti != -1) {
 291                 xfs_extlen_t    p;      /* amount to trim length by */
 292
 293                 /*
 294                  * If size should be a multiple of prod, make that so.
 295                  */
 296                 if (prod > 1 && (p = do_mod(bestlen, prod)))
 297                         bestlen -= p;
 298                 /*
 299                  * Allocate besti for bestlen & return that.
 300                  */
 301                 error = xfs_rtallocate_range(mp, tp, besti, bestlen, rbpp, rsb);
 302                 if (error) {
 303                         return error;
 304                 }
 305                 *len = bestlen;
 306                 *rtblock = besti;
 307                 return 0;
 308         }
 309         /*
 310          * Allocation failed.  Set *nextp to the next block to try.
 311          */
 312         *nextp = next;
 313         *rtblock = NULLRTBLOCK;
 314         return 0;
 315 }
 316
 317 /*
 318  * Allocate an extent of length minlen<=len<=maxlen, starting at block
 319  * bno.  If we don't get maxlen then use prod to trim the length, if given.
 320  * Returns error; returns starting block in *rtblock.
 321  * The lengths are all in rtextents.
 322  */
 323 STATIC int                              /* error */
 324 xfs_rtallocate_extent_exact(
 325         xfs_mount_t     *mp,            /* file system mount point */
 326         xfs_trans_t     *tp,            /* transaction pointer */
 327         xfs_rtblock_t   bno,            /* starting block number to allocate */
 328         xfs_extlen_t    minlen,         /* minimum length to allocate */
 329         xfs_extlen_t    maxlen,         /* maximum length to allocate */
 330         xfs_extlen_t    *len,           /* out: actual length allocated */
 331         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 332         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 333         xfs_extlen_t    prod,           /* extent product factor */
 334         xfs_rtblock_t   *rtblock)       /* out: start block allocated */
 335 {
 336         int             error;          /* error value */
 337         xfs_extlen_t    i;              /* extent length trimmed due to prod */
 338         int             isfree;         /* extent is free */
 339         xfs_rtblock_t   next;           /* next block to try (dummy) */
 340
 341         ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 342         /*
 343          * Check if the range in question (for maxlen) is free.
 344          */
 345         error = xfs_rtcheck_range(mp, tp, bno, maxlen, 1, &next, &isfree);
 346         if (error) {
 347                 return error;
 348         }
 349         if (isfree) {
 350                 /*
 351                  * If it is, allocate it and return success.
 352                  */
 353                 error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
 354                 if (error) {
 355                         return error;
 356                 }
 357                 *len = maxlen;
 358                 *rtblock = bno;
 359                 return 0;
 360         }
 361         /*
 362          * If not, allocate what there is, if it's at least minlen.
 363          */
 364         maxlen = next - bno;
 365         if (maxlen < minlen) {
 366                 /*
 367                  * Failed, return failure status.
 368                  */
 369                 *rtblock = NULLRTBLOCK;
 370                 return 0;
 371         }
 372         /*
 373          * Trim off tail of extent, if prod is specified.
 374          */
 375         if (prod > 1 && (i = maxlen % prod)) {
 376                 maxlen -= i;
 377                 if (maxlen < minlen) {
 378                         /*
 379                          * Now we can't do it, return failure status.
 380                          */
 381                         *rtblock = NULLRTBLOCK;
 382                         return 0;
 383                 }
 384         }
 385         /*
 386          * Allocate what we can and return it.
 387          */
 388         error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
 389         if (error) {
 390                 return error;
 391         }
 392         *len = maxlen;
 393         *rtblock = bno;
 394         return 0;
 395 }
 396
 397 /*
 398  * Allocate an extent of length minlen<=len<=maxlen, starting as near
 399  * to bno as possible.  If we don't get maxlen then use prod to trim
 400  * the length, if given.  The lengths are all in rtextents.
 401  */
 402 STATIC int                              /* error */
 403 xfs_rtallocate_extent_near(
 404         xfs_mount_t     *mp,            /* file system mount point */
 405         xfs_trans_t     *tp,            /* transaction pointer */
 406         xfs_rtblock_t   bno,            /* starting block number to allocate */
 407         xfs_extlen_t    minlen,         /* minimum length to allocate */
 408         xfs_extlen_t    maxlen,         /* maximum length to allocate */
 409         xfs_extlen_t    *len,           /* out: actual length allocated */
 410         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 411         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 412         xfs_extlen_t    prod,           /* extent product factor */
 413         xfs_rtblock_t   *rtblock)       /* out: start block allocated */
 414 {
 415         int             any;            /* any useful extents from summary */
 416         xfs_rtblock_t   bbno;           /* bitmap block number */
 417         int             error;          /* error value */
 418         int             i;              /* bitmap block offset (loop control) */
 419         int             j;              /* secondary loop control */
 420         int             log2len;        /* log2 of minlen */
 421         xfs_rtblock_t   n;              /* next block to try */
 422         xfs_rtblock_t   r;              /* result block */
 423
 424         ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 425         /*
 426          * If the block number given is off the end, silently set it to
 427          * the last block.
 428          */
 429         if (bno >= mp->m_sb.sb_rextents)
 430                 bno = mp->m_sb.sb_rextents - 1;
 431         /*
 432          * Try the exact allocation first.
 433          */
 434         error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen, len,
 435                 rbpp, rsb, prod, &r);
 436         if (error) {
 437                 return error;
 438         }
 439         /*
 440          * If the exact allocation worked, return that.
 441          */
 442         if (r != NULLRTBLOCK) {
 443                 *rtblock = r;
 444                 return 0;
 445         }
 446         bbno = XFS_BITTOBLOCK(mp, bno);
 447         i = 0;
 448         log2len = xfs_highbit32(minlen);
 449         /*
 450          * Loop over all bitmap blocks (bbno + i is current block).
 451          */
 452         for (;;) {
 453                 /*
 454                  * Get summary information of extents of all useful levels
 455                  * starting in this bitmap block.
 456                  */
 457                 error = xfs_rtany_summary(mp, tp, log2len, mp->m_rsumlevels - 1,
 458                         bbno + i, rbpp, rsb, &any);
 459                 if (error) {
 460                         return error;
 461                 }
 462                 /*
 463                  * If there are any useful extents starting here, try
 464                  * allocating one.
 465                  */
 466                 if (any) {
 467                         /*
 468                          * On the positive side of the starting location.
 469                          */
 470                         if (i >= 0) {
 471                                 /*
 472                                  * Try to allocate an extent starting in
 473                                  * this block.
 474                                  */
 475                                 error = xfs_rtallocate_extent_block(mp, tp,
 476                                         bbno + i, minlen, maxlen, len, &n, rbpp,
 477                                         rsb, prod, &r);
 478                                 if (error) {
 479                                         return error;
 480                                 }
 481                                 /*
 482                                  * If it worked, return it.
 483                                  */
 484                                 if (r != NULLRTBLOCK) {
 485                                         *rtblock = r;
 486                                         return 0;
 487                                 }
 488                         }
 489                         /*
 490                          * On the negative side of the starting location.
 491                          */
 492                         else {          /* i < 0 */
 493                                 /*
 494                                  * Loop backwards through the bitmap blocks from
 495                                  * the starting point-1 up to where we are now.
 496                                  * There should be an extent which ends in this
 497                                  * bitmap block and is long enough.
 498                                  */
 499                                 for (j = -1; j > i; j--) {
 500                                         /*
 501                                          * Grab the summary information for
 502                                          * this bitmap block.
 503                                          */
 504                                         error = xfs_rtany_summary(mp, tp,
 505                                                 log2len, mp->m_rsumlevels - 1,
 506                                                 bbno + j, rbpp, rsb, &any);
 507                                         if (error) {
 508                                                 return error;
 509                                         }
 510                                         /*
 511                                          * If there's no extent given in the
 512                                          * summary that means the extent we
 513                                          * found must carry over from an
 514                                          * earlier block.  If there is an
 515                                          * extent given, we've already tried
 516                                          * that allocation, don't do it again.
 517                                          */
 518                                         if (any)
 519                                                 continue;
 520                                         error = xfs_rtallocate_extent_block(mp,
 521                                                 tp, bbno + j, minlen, maxlen,
 522                                                 len, &n, rbpp, rsb, prod, &r);
 523                                         if (error) {
 524                                                 return error;
 525                                         }
 526                                         /*
 527                                          * If it works, return the extent.
 528                                          */
 529                                         if (r != NULLRTBLOCK) {
 530                                                 *rtblock = r;
 531                                                 return 0;
 532                                         }
 533                                 }
 534                                 /*
 535                                  * There weren't intervening bitmap blocks
 536                                  * with a long enough extent, or the
 537                                  * allocation didn't work for some reason
 538                                  * (i.e. it's a little * too short).
 539                                  * Try to allocate from the summary block
 540                                  * that we found.
 541                                  */
 542                                 error = xfs_rtallocate_extent_block(mp, tp,
 543                                         bbno + i, minlen, maxlen, len, &n, rbpp,
 544                                         rsb, prod, &r);
 545                                 if (error) {
 546                                         return error;
 547                                 }
 548                                 /*
 549                                  * If it works, return the extent.
 550                                  */
 551                                 if (r != NULLRTBLOCK) {
 552                                         *rtblock = r;
 553                                         return 0;
 554                                 }
 555                         }
 556                 }
 557                 /*
 558                  * Loop control.  If we were on the positive side, and there's
 559                  * still more blocks on the negative side, go there.
 560                  */
 561                 if (i > 0 && (int)bbno - i >= 0)
 562                         i = -i;
 563                 /*
 564                  * If positive, and no more negative, but there are more
 565                  * positive, go there.
 566                  */
 567                 else if (i > 0 && (int)bbno + i < mp->m_sb.sb_rbmblocks - 1)
 568                         i++;
 569                 /*
 570                  * If negative or 0 (just started), and there are positive
 571                  * blocks to go, go there.  The 0 case moves to block 1.
 572                  */
 573                 else if (i <= 0 && (int)bbno - i < mp->m_sb.sb_rbmblocks - 1)
 574                         i = 1 - i;
 575                 /*
 576                  * If negative or 0 and there are more negative blocks,
 577                  * go there.
 578                  */
 579                 else if (i <= 0 && (int)bbno + i > 0)
 580                         i--;
 581                 /*
 582                  * Must be done.  Return failure.
 583                  */
 584                 else
 585                         break;
 586         }
 587         *rtblock = NULLRTBLOCK;
 588         return 0;
 589 }
 590
 591 /*
 592  * Allocate an extent of length minlen<=len<=maxlen, with no position
 593  * specified.  If we don't get maxlen then use prod to trim
 594  * the length, if given.  The lengths are all in rtextents.
 595  */
 596 STATIC int                              /* error */
 597 xfs_rtallocate_extent_size(
 598         xfs_mount_t     *mp,            /* file system mount point */
 599         xfs_trans_t     *tp,            /* transaction pointer */
 600         xfs_extlen_t    minlen,         /* minimum length to allocate */
 601         xfs_extlen_t    maxlen,         /* maximum length to allocate */
 602         xfs_extlen_t    *len,           /* out: actual length allocated */
 603         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 604         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 605         xfs_extlen_t    prod,           /* extent product factor */
 606         xfs_rtblock_t   *rtblock)       /* out: start block allocated */
 607 {
 608         int             error;          /* error value */
 609         int             i;              /* bitmap block number */
 610         int             l;              /* level number (loop control) */
 611         xfs_rtblock_t   n;              /* next block to be tried */
 612         xfs_rtblock_t   r;              /* result block number */
 613         xfs_suminfo_t   sum;            /* summary information for extents */
 614
 615         ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 616         /*
 617          * Loop over all the levels starting with maxlen.
 618          * At each level, look at all the bitmap blocks, to see if there
 619          * are extents starting there that are long enough (>= maxlen).
 620          * Note, only on the initial level can the allocation fail if
 621          * the summary says there's an extent.
 622          */
 623         for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) {
 624                 /*
 625                  * Loop over all the bitmap blocks.
 626                  */
 627                 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
 628                         /*
 629                          * Get the summary for this level/block.
 630                          */
 631                         error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
 632                                 &sum);
 633                         if (error) {
 634                                 return error;
 635                         }
 636                         /*
 637                          * Nothing there, on to the next block.
 638                          */
 639                         if (!sum)
 640                                 continue;
 641                         /*
 642                          * Try allocating the extent.
 643                          */
 644                         error = xfs_rtallocate_extent_block(mp, tp, i, maxlen,
 645                                 maxlen, len, &n, rbpp, rsb, prod, &r);
 646                         if (error) {
 647                                 return error;
 648                         }
 649                         /*
 650                          * If it worked, return that.
 651                          */
 652                         if (r != NULLRTBLOCK) {
 653                                 *rtblock = r;
 654                                 return 0;
 655                         }
 656                         /*
 657                          * If the "next block to try" returned from the
 658                          * allocator is beyond the next bitmap block,
 659                          * skip to that bitmap block.
 660                          */
 661                         if (XFS_BITTOBLOCK(mp, n) > i + 1)
 662                                 i = XFS_BITTOBLOCK(mp, n) - 1;
 663                 }
 664         }
 665         /*
 666          * Didn't find any maxlen blocks.  Try smaller ones, unless
 667          * we're asking for a fixed size extent.
 668          */
 669         if (minlen > --maxlen) {
 670                 *rtblock = NULLRTBLOCK;
 671                 return 0;
 672         }
 673         /*
 674          * Loop over sizes, from maxlen down to minlen.
 675          * This time, when we do the allocations, allow smaller ones
 676          * to succeed.
 677          */
 678         for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) {
 679                 /*
 680                  * Loop over all the bitmap blocks, try an allocation
 681                  * starting in that block.
 682                  */
 683                 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
 684                         /*
 685                          * Get the summary information for this level/block.
 686                          */
 687                         error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
 688                                                   &sum);
 689                         if (error) {
 690                                 return error;
 691                         }
 692                         /*
 693                          * If nothing there, go on to next.
 694                          */
 695                         if (!sum)
 696                                 continue;
 697                         /*
 698                          * Try the allocation.  Make sure the specified
 699                          * minlen/maxlen are in the possible range for
 700                          * this summary level.
 701                          */
 702                         error = xfs_rtallocate_extent_block(mp, tp, i,
 703                                         XFS_RTMAX(minlen, 1 << l),
 704                                         XFS_RTMIN(maxlen, (1 << (l + 1)) - 1),
 705                                         len, &n, rbpp, rsb, prod, &r);
 706                         if (error) {
 707                                 return error;
 708                         }
 709                         /*
 710                          * If it worked, return that extent.
 711                          */
 712                         if (r != NULLRTBLOCK) {
 713                                 *rtblock = r;
 714                                 return 0;
 715                         }
 716                         /*
 717                          * If the "next block to try" returned from the
 718                          * allocator is beyond the next bitmap block,
 719                          * skip to that bitmap block.
 720                          */
 721                         if (XFS_BITTOBLOCK(mp, n) > i + 1)
 722                                 i = XFS_BITTOBLOCK(mp, n) - 1;
 723                 }
 724         }
 725         /*
 726          * Got nothing, return failure.
 727          */
 728         *rtblock = NULLRTBLOCK;
 729         return 0;
 730 }
 731
 732 /*
 733  * Mark an extent specified by start and len allocated.
 734  * Updates all the summary information as well as the bitmap.
 735  */
 736 STATIC int                              /* error */
 737 xfs_rtallocate_range(
 738         xfs_mount_t     *mp,            /* file system mount point */
 739         xfs_trans_t     *tp,            /* transaction pointer */
 740         xfs_rtblock_t   start,          /* start block to allocate */
 741         xfs_extlen_t    len,            /* length to allocate */
 742         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 743         xfs_fsblock_t   *rsb)           /* in/out: summary block number */
 744 {
 745         xfs_rtblock_t   end;            /* end of the allocated extent */
 746         int             error;          /* error value */
 747         xfs_rtblock_t   postblock;      /* first block allocated > end */
 748         xfs_rtblock_t   preblock;       /* first block allocated < start */
 749
 750         end = start + len - 1;
 751         /*
 752          * Assume we're allocating out of the middle of a free extent.
 753          * We need to find the beginning and end of the extent so we can
 754          * properly update the summary.
 755          */
 756         error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
 757         if (error) {
 758                 return error;
 759         }
 760         /*
 761          * Find the next allocated block (end of free extent).
 762          */
 763         error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
 764                 &postblock);
 765         if (error) {
 766                 return error;
 767         }
 768         /*
 769          * Decrement the summary information corresponding to the entire
 770          * (old) free extent.
 771          */
 772         error = xfs_rtmodify_summary(mp, tp,
 773                 XFS_RTBLOCKLOG(postblock + 1 - preblock),
 774                 XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
 775         if (error) {
 776                 return error;
 777         }
 778         /*
 779          * If there are blocks not being allocated at the front of the
 780          * old extent, add summary data for them to be free.
 781          */
 782         if (preblock < start) {
 783                 error = xfs_rtmodify_summary(mp, tp,
 784                         XFS_RTBLOCKLOG(start - preblock),
 785                         XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
 786                 if (error) {
 787                         return error;
 788                 }
 789         }
 790         /*
 791          * If there are blocks not being allocated at the end of the
 792          * old extent, add summary data for them to be free.
 793          */
 794         if (postblock > end) {
 795                 error = xfs_rtmodify_summary(mp, tp,
 796                         XFS_RTBLOCKLOG(postblock - end),
 797                         XFS_BITTOBLOCK(mp, end + 1), 1, rbpp, rsb);
 798                 if (error) {
 799                         return error;
 800                 }
 801         }
 802         /*
 803          * Modify the bitmap to mark this extent allocated.
 804          */
 805         error = xfs_rtmodify_range(mp, tp, start, len, 0);
 806         return error;
 807 }
 808
 809 /*
 810  * Return whether there are any free extents in the size range given
 811  * by low and high, for the bitmap block bbno.
 812  */
 813 STATIC int                              /* error */
 814 xfs_rtany_summary(
 815         xfs_mount_t     *mp,            /* file system mount structure */
 816         xfs_trans_t     *tp,            /* transaction pointer */
 817         int             low,            /* low log2 extent size */
 818         int             high,           /* high log2 extent size */
 819         xfs_rtblock_t   bbno,           /* bitmap block number */
 820         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 821         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 822         int             *stat)          /* out: any good extents here? */
 823 {
 824         int             error;          /* error value */
 825         int             log;            /* loop counter, log2 of ext. size */
 826         xfs_suminfo_t   sum;            /* summary data */
 827
 828         /*
 829          * Loop over logs of extent sizes.  Order is irrelevant.
 830          */
 831         for (log = low; log <= high; log++) {
 832                 /*
 833                  * Get one summary datum.
 834                  */
 835                 error = xfs_rtget_summary(mp, tp, log, bbno, rbpp, rsb, &sum);
 836                 if (error) {
 837                         return error;
 838                 }
 839                 /*
 840                  * If there are any, return success.
 841                  */
 842                 if (sum) {
 843                         *stat = 1;
 844                         return 0;
 845                 }
 846         }
 847         /*
 848          * Found nothing, return failure.
 849          */
 850         *stat = 0;
 851         return 0;
 852 }
 853
 854 /*
 855  * Get a buffer for the bitmap or summary file block specified.
 856  * The buffer is returned read and locked.
 857  */
 858 STATIC int                              /* error */
 859 xfs_rtbuf_get(
 860         xfs_mount_t     *mp,            /* file system mount structure */
 861         xfs_trans_t     *tp,            /* transaction pointer */
 862         xfs_rtblock_t   block,          /* block number in bitmap or summary */
 863         int             issum,          /* is summary not bitmap */
 864         xfs_buf_t       **bpp)          /* output: buffer for the block */
 865 {
 866         xfs_buf_t       *bp;            /* block buffer, result */
 867         xfs_daddr_t     d;              /* disk addr of block */
 868         int             error;          /* error value */
 869         xfs_fsblock_t   fsb;            /* fs block number for block */
 870         xfs_inode_t     *ip;            /* bitmap or summary inode */
 871
 872         ip = issum ? mp->m_rsumip : mp->m_rbmip;
 873         /*
 874          * Map from the file offset (block) and inode number to the
 875          * file system block.
 876          */
 877         error = xfs_bmapi_single(tp, ip, XFS_DATA_FORK, &fsb, block);
 878         if (error) {
 879                 return error;
 880         }
 881         ASSERT(fsb != NULLFSBLOCK);
 882         /*
 883          * Convert to disk address for buffer cache.
 884          */
 885         d = XFS_FSB_TO_DADDR(mp, fsb);
 886         /*
 887          * Read the buffer.
 888          */
 889         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 890                                    mp->m_bsize, 0, &bp);
 891         if (error) {
 892                 return error;
 893         }
 894         ASSERT(bp && !XFS_BUF_GETERROR(bp));
 895         *bpp = bp;
 896         return 0;
 897 }
 898
 899 #ifdef DEBUG
 900 /*
 901  * Check that the given extent (block range) is allocated already.
 902  */
 903 STATIC int                              /* error */
 904 xfs_rtcheck_alloc_range(
 905         xfs_mount_t     *mp,            /* file system mount point */
 906         xfs_trans_t     *tp,            /* transaction pointer */
 907         xfs_rtblock_t   bno,            /* starting block number of extent */
 908         xfs_extlen_t    len,            /* length of extent */
 909         int             *stat)          /* out: 1 for allocated, 0 for not */
 910 {
 911         xfs_rtblock_t   new;            /* dummy for xfs_rtcheck_range */
 912
 913         return xfs_rtcheck_range(mp, tp, bno, len, 0, &new, stat);
 914 }
 915 #endif
 916
 917 #ifdef DEBUG
 918 /*
 919  * Check whether the given block in the bitmap has the given value.
 920  */
 921 STATIC int                              /* 1 for matches, 0 for not */
 922 xfs_rtcheck_bit(
 923         xfs_mount_t     *mp,            /* file system mount structure */
 924         xfs_trans_t     *tp,            /* transaction pointer */
 925         xfs_rtblock_t   start,          /* bit (block) to check */
 926         int             val)            /* 1 for free, 0 for allocated */
 927 {
 928         int             bit;            /* bit number in the word */
 929         xfs_rtblock_t   block;          /* bitmap block number */
 930         xfs_buf_t       *bp;            /* buf for the block */
 931         xfs_rtword_t    *bufp;          /* pointer into the buffer */
 932         /* REFERENCED */
 933         int             error;          /* error value */
 934         xfs_rtword_t    wdiff;          /* difference between bit & expected */
 935         int             word;           /* word number in the buffer */
 936         xfs_rtword_t    wval;           /* word value from buffer */
 937
 938         block = XFS_BITTOBLOCK(mp, start);
 939         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 940         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
 941         word = XFS_BITTOWORD(mp, start);
 942         bit = (int)(start & (XFS_NBWORD - 1));
 943         wval = bufp[word];
 944         xfs_trans_brelse(tp, bp);
 945         wdiff = (wval ^ -val) & ((xfs_rtword_t)1 << bit);
 946         return !wdiff;
 947 }
 948 #endif  /* DEBUG */
 949
 950 #if 0
 951 /*
 952  * Check that the given extent (block range) is free already.
 953  */
 954 STATIC int                              /* error */
 955 xfs_rtcheck_free_range(
 956         xfs_mount_t     *mp,            /* file system mount point */
 957         xfs_trans_t     *tp,            /* transaction pointer */
 958         xfs_rtblock_t   bno,            /* starting block number of extent */
 959         xfs_extlen_t    len,            /* length of extent */
 960         int             *stat)          /* out: 1 for free, 0 for not */
 961 {
 962         xfs_rtblock_t   new;            /* dummy for xfs_rtcheck_range */
 963
 964         return xfs_rtcheck_range(mp, tp, bno, len, 1, &new, stat);
 965 }
 966 #endif
 967
 968 /*
 969  * Check that the given range is either all allocated (val = 0) or
 970  * all free (val = 1).
 971  */
 972 STATIC int                              /* error */
 973 xfs_rtcheck_range(
 974         xfs_mount_t     *mp,            /* file system mount point */
 975         xfs_trans_t     *tp,            /* transaction pointer */
 976         xfs_rtblock_t   start,          /* starting block number of extent */
 977         xfs_extlen_t    len,            /* length of extent */
 978         int             val,            /* 1 for free, 0 for allocated */
 979         xfs_rtblock_t   *new,           /* out: first block not matching */
 980         int             *stat)          /* out: 1 for matches, 0 for not */
 981 {
 982         xfs_rtword_t    *b;             /* current word in buffer */
 983         int             bit;            /* bit number in the word */
 984         xfs_rtblock_t   block;          /* bitmap block number */
 985         xfs_buf_t       *bp;            /* buf for the block */
 986         xfs_rtword_t    *bufp;          /* starting word in buffer */
 987         int             error;          /* error value */
 988         xfs_rtblock_t   i;              /* current bit number rel. to start */
 989         xfs_rtblock_t   lastbit;        /* last useful bit in word */
 990         xfs_rtword_t    mask;           /* mask of relevant bits for value */
 991         xfs_rtword_t    wdiff;          /* difference from wanted value */
 992         int             word;           /* word number in the buffer */
 993
 994         /*
 995          * Compute starting bitmap block number
 996          */
 997         block = XFS_BITTOBLOCK(mp, start);
 998         /*
 999          * Read the bitmap block.
1000          */
1001         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1002         if (error) {
1003                 return error;
1004         }
1005         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1006         /*
1007          * Compute the starting word's address, and starting bit.
1008          */
1009         word = XFS_BITTOWORD(mp, start);
1010         b = &bufp[word];
1011         bit = (int)(start & (XFS_NBWORD - 1));
1012         /*
1013          * 0 (allocated) => all zero's; 1 (free) => all one's.
1014          */
1015         val = -val;
1016         /*
1017          * If not starting on a word boundary, deal with the first
1018          * (partial) word.
1019          */
1020         if (bit) {
1021                 /*
1022                  * Compute first bit not examined.
1023                  */
1024                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1025                 /*
1026                  * Mask of relevant bits.
1027                  */
1028                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1029                 /*
1030                  * Compute difference between actual and desired value.
1031                  */
1032                 if ((wdiff = (*b ^ val) & mask)) {
1033                         /*
1034                          * Different, compute first wrong bit and return.
1035                          */
1036                         xfs_trans_brelse(tp, bp);
1037                         i = XFS_RTLOBIT(wdiff) - bit;
1038                         *new = start + i;
1039                         *stat = 0;
1040                         return 0;
1041                 }
1042                 i = lastbit - bit;
1043                 /*
1044                  * Go on to next block if that's where the next word is
1045                  * and we need the next word.
1046                  */
1047                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1048                         /*
1049                          * If done with this block, get the next one.
1050                          */
1051                         xfs_trans_brelse(tp, bp);
1052                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1053                         if (error) {
1054                                 return error;
1055                         }
1056                         b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1057                         word = 0;
1058                 } else {
1059                         /*
1060                          * Go on to the next word in the buffer.
1061                          */
1062                         b++;
1063                 }
1064         } else {
1065                 /*
1066                  * Starting on a word boundary, no partial word.
1067                  */
1068                 i = 0;
1069         }
1070         /*
1071          * Loop over whole words in buffers.  When we use up one buffer
1072          * we move on to the next one.
1073          */
1074         while (len - i >= XFS_NBWORD) {
1075                 /*
1076                  * Compute difference between actual and desired value.
1077                  */
1078                 if ((wdiff = *b ^ val)) {
1079                         /*
1080                          * Different, compute first wrong bit and return.
1081                          */
1082                         xfs_trans_brelse(tp, bp);
1083                         i += XFS_RTLOBIT(wdiff);
1084                         *new = start + i;
1085                         *stat = 0;
1086                         return 0;
1087                 }
1088                 i += XFS_NBWORD;
1089                 /*
1090                  * Go on to next block if that's where the next word is
1091                  * and we need the next word.
1092                  */
1093                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1094                         /*
1095                          * If done with this block, get the next one.
1096                          */
1097                         xfs_trans_brelse(tp, bp);
1098                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1099                         if (error) {
1100                                 return error;
1101                         }
1102                         b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1103                         word = 0;
1104                 } else {
1105                         /*
1106                          * Go on to the next word in the buffer.
1107                          */
1108                         b++;
1109                 }
1110         }
1111         /*
1112          * If not ending on a word boundary, deal with the last
1113          * (partial) word.
1114          */
1115         if ((lastbit = len - i)) {
1116                 /*
1117                  * Mask of relevant bits.
1118                  */
1119                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1120                 /*
1121                  * Compute difference between actual and desired value.
1122                  */
1123                 if ((wdiff = (*b ^ val) & mask)) {
1124                         /*
1125                          * Different, compute first wrong bit and return.
1126                          */
1127                         xfs_trans_brelse(tp, bp);
1128                         i += XFS_RTLOBIT(wdiff);
1129                         *new = start + i;
1130                         *stat = 0;
1131                         return 0;
1132                 } else
1133                         i = len;
1134         }
1135         /*
1136          * Successful, return.
1137          */
1138         xfs_trans_brelse(tp, bp);
1139         *new = start + i;
1140         *stat = 1;
1141         return 0;
1142 }
1143
1144 /*
1145  * Copy and transform the summary file, given the old and new
1146  * parameters in the mount structures.
1147  */
1148 STATIC int                              /* error */
1149 xfs_rtcopy_summary(
1150         xfs_mount_t     *omp,           /* old file system mount point */
1151         xfs_mount_t     *nmp,           /* new file system mount point */
1152         xfs_trans_t     *tp)            /* transaction pointer */
1153 {
1154         xfs_rtblock_t   bbno;           /* bitmap block number */
1155         xfs_buf_t       *bp;            /* summary buffer */
1156         int             error;          /* error return value */
1157         int             log;            /* summary level number (log length) */
1158         xfs_suminfo_t   sum;            /* summary data */
1159         xfs_fsblock_t   sumbno;         /* summary block number */
1160
1161         bp = NULL;
1162         for (log = omp->m_rsumlevels - 1; log >= 0; log--) {
1163                 for (bbno = omp->m_sb.sb_rbmblocks - 1;
1164                      (xfs_srtblock_t)bbno >= 0;
1165                      bbno--) {
1166                         error = xfs_rtget_summary(omp, tp, log, bbno, &bp,
1167                                 &sumbno, &sum);
1168                         if (error)
1169                                 return error;
1170                         if (sum == 0)
1171                                 continue;
1172                         error = xfs_rtmodify_summary(omp, tp, log, bbno, -sum,
1173                                 &bp, &sumbno);
1174                         if (error)
1175                                 return error;
1176                         error = xfs_rtmodify_summary(nmp, tp, log, bbno, sum,
1177                                 &bp, &sumbno);
1178                         if (error)
1179                                 return error;
1180                         ASSERT(sum > 0);
1181                 }
1182         }
1183         return 0;
1184 }
1185
1186 /*
1187  * Searching backward from start to limit, find the first block whose
1188  * allocated/free state is different from start's.
1189  */
1190 STATIC int                              /* error */
1191 xfs_rtfind_back(
1192         xfs_mount_t     *mp,            /* file system mount point */
1193         xfs_trans_t     *tp,            /* transaction pointer */
1194         xfs_rtblock_t   start,          /* starting block to look at */
1195         xfs_rtblock_t   limit,          /* last block to look at */
1196         xfs_rtblock_t   *rtblock)       /* out: start block found */
1197 {
1198         xfs_rtword_t    *b;             /* current word in buffer */
1199         int             bit;            /* bit number in the word */
1200         xfs_rtblock_t   block;          /* bitmap block number */
1201         xfs_buf_t       *bp;            /* buf for the block */
1202         xfs_rtword_t    *bufp;          /* starting word in buffer */
1203         int             error;          /* error value */
1204         xfs_rtblock_t   firstbit;       /* first useful bit in the word */
1205         xfs_rtblock_t   i;              /* current bit number rel. to start */
1206         xfs_rtblock_t   len;            /* length of inspected area */
1207         xfs_rtword_t    mask;           /* mask of relevant bits for value */
1208         xfs_rtword_t    want;           /* mask for "good" values */
1209         xfs_rtword_t    wdiff;          /* difference from wanted value */
1210         int             word;           /* word number in the buffer */
1211
1212         /*
1213          * Compute and read in starting bitmap block for starting block.
1214          */
1215         block = XFS_BITTOBLOCK(mp, start);
1216         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1217         if (error) {
1218                 return error;
1219         }
1220         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1221         /*
1222          * Get the first word's index & point to it.
1223          */
1224         word = XFS_BITTOWORD(mp, start);
1225         b = &bufp[word];
1226         bit = (int)(start & (XFS_NBWORD - 1));
1227         len = start - limit + 1;
1228         /*
1229          * Compute match value, based on the bit at start: if 1 (free)
1230          * then all-ones, else all-zeroes.
1231          */
1232         want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1233         /*
1234          * If the starting position is not word-aligned, deal with the
1235          * partial word.
1236          */
1237         if (bit < XFS_NBWORD - 1) {
1238                 /*
1239                  * Calculate first (leftmost) bit number to look at,
1240                  * and mask for all the relevant bits in this word.
1241                  */
1242                 firstbit = XFS_RTMAX((xfs_srtblock_t)(bit - len + 1), 0);
1243                 mask = (((xfs_rtword_t)1 << (bit - firstbit + 1)) - 1) <<
1244                         firstbit;
1245                 /*
1246                  * Calculate the difference between the value there
1247                  * and what we're looking for.
1248                  */
1249                 if ((wdiff = (*b ^ want) & mask)) {
1250                         /*
1251                          * Different.  Mark where we are and return.
1252                          */
1253                         xfs_trans_brelse(tp, bp);
1254                         i = bit - XFS_RTHIBIT(wdiff);
1255                         *rtblock = start - i + 1;
1256                         return 0;
1257                 }
1258                 i = bit - firstbit + 1;
1259                 /*
1260                  * Go on to previous block if that's where the previous word is
1261                  * and we need the previous word.
1262                  */
1263                 if (--word == -1 && i < len) {
1264                         /*
1265                          * If done with this block, get the previous one.
1266                          */
1267                         xfs_trans_brelse(tp, bp);
1268                         error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1269                         if (error) {
1270                                 return error;
1271                         }
1272                         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1273                         word = XFS_BLOCKWMASK(mp);
1274                         b = &bufp[word];
1275                 } else {
1276                         /*
1277                          * Go on to the previous word in the buffer.
1278                          */
1279                         b--;
1280                 }
1281         } else {
1282                 /*
1283                  * Starting on a word boundary, no partial word.
1284                  */
1285                 i = 0;
1286         }
1287         /*
1288          * Loop over whole words in buffers.  When we use up one buffer
1289          * we move on to the previous one.
1290          */
1291         while (len - i >= XFS_NBWORD) {
1292                 /*
1293                  * Compute difference between actual and desired value.
1294                  */
1295                 if ((wdiff = *b ^ want)) {
1296                         /*
1297                          * Different, mark where we are and return.
1298                          */
1299                         xfs_trans_brelse(tp, bp);
1300                         i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1301                         *rtblock = start - i + 1;
1302                         return 0;
1303                 }
1304                 i += XFS_NBWORD;
1305                 /*
1306                  * Go on to previous block if that's where the previous word is
1307                  * and we need the previous word.
1308                  */
1309                 if (--word == -1 && i < len) {
1310                         /*
1311                          * If done with this block, get the previous one.
1312                          */
1313                         xfs_trans_brelse(tp, bp);
1314                         error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1315                         if (error) {
1316                                 return error;
1317                         }
1318                         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1319                         word = XFS_BLOCKWMASK(mp);
1320                         b = &bufp[word];
1321                 } else {
1322                         /*
1323                          * Go on to the previous word in the buffer.
1324                          */
1325                         b--;
1326                 }
1327         }
1328         /*
1329          * If not ending on a word boundary, deal with the last
1330          * (partial) word.
1331          */
1332         if (len - i) {
1333                 /*
1334                  * Calculate first (leftmost) bit number to look at,
1335                  * and mask for all the relevant bits in this word.
1336                  */
1337                 firstbit = XFS_NBWORD - (len - i);
1338                 mask = (((xfs_rtword_t)1 << (len - i)) - 1) << firstbit;
1339                 /*
1340                  * Compute difference between actual and desired value.
1341                  */
1342                 if ((wdiff = (*b ^ want) & mask)) {
1343                         /*
1344                          * Different, mark where we are and return.
1345                          */
1346                         xfs_trans_brelse(tp, bp);
1347                         i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1348                         *rtblock = start - i + 1;
1349                         return 0;
1350                 } else
1351                         i = len;
1352         }
1353         /*
1354          * No match, return that we scanned the whole area.
1355          */
1356         xfs_trans_brelse(tp, bp);
1357         *rtblock = start - i + 1;
1358         return 0;
1359 }
1360
1361 /*
1362  * Searching forward from start to limit, find the first block whose
1363  * allocated/free state is different from start's.
1364  */
1365 STATIC int                              /* error */
1366 xfs_rtfind_forw(
1367         xfs_mount_t     *mp,            /* file system mount point */
1368         xfs_trans_t     *tp,            /* transaction pointer */
1369         xfs_rtblock_t   start,          /* starting block to look at */
1370         xfs_rtblock_t   limit,          /* last block to look at */
1371         xfs_rtblock_t   *rtblock)       /* out: start block found */
1372 {
1373         xfs_rtword_t    *b;             /* current word in buffer */
1374         int             bit;            /* bit number in the word */
1375         xfs_rtblock_t   block;          /* bitmap block number */
1376         xfs_buf_t       *bp;            /* buf for the block */
1377         xfs_rtword_t    *bufp;          /* starting word in buffer */
1378         int             error;          /* error value */
1379         xfs_rtblock_t   i;              /* current bit number rel. to start */
1380         xfs_rtblock_t   lastbit;        /* last useful bit in the word */
1381         xfs_rtblock_t   len;            /* length of inspected area */
1382         xfs_rtword_t    mask;           /* mask of relevant bits for value */
1383         xfs_rtword_t    want;           /* mask for "good" values */
1384         xfs_rtword_t    wdiff;          /* difference from wanted value */
1385         int             word;           /* word number in the buffer */
1386
1387         /*
1388          * Compute and read in starting bitmap block for starting block.
1389          */
1390         block = XFS_BITTOBLOCK(mp, start);
1391         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1392         if (error) {
1393                 return error;
1394         }
1395         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1396         /*
1397          * Get the first word's index & point to it.
1398          */
1399         word = XFS_BITTOWORD(mp, start);
1400         b = &bufp[word];
1401         bit = (int)(start & (XFS_NBWORD - 1));
1402         len = limit - start + 1;
1403         /*
1404          * Compute match value, based on the bit at start: if 1 (free)
1405          * then all-ones, else all-zeroes.
1406          */
1407         want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1408         /*
1409          * If the starting position is not word-aligned, deal with the
1410          * partial word.
1411          */
1412         if (bit) {
1413                 /*
1414                  * Calculate last (rightmost) bit number to look at,
1415                  * and mask for all the relevant bits in this word.
1416                  */
1417                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1418                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1419                 /*
1420                  * Calculate the difference between the value there
1421                  * and what we're looking for.
1422                  */
1423                 if ((wdiff = (*b ^ want) & mask)) {
1424                         /*
1425                          * Different.  Mark where we are and return.
1426                          */
1427                         xfs_trans_brelse(tp, bp);
1428                         i = XFS_RTLOBIT(wdiff) - bit;
1429                         *rtblock = start + i - 1;
1430                         return 0;
1431                 }
1432                 i = lastbit - bit;
1433                 /*
1434                  * Go on to next block if that's where the next word is
1435                  * and we need the next word.
1436                  */
1437                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1438                         /*
1439                          * If done with this block, get the previous one.
1440                          */
1441                         xfs_trans_brelse(tp, bp);
1442                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1443                         if (error) {
1444                                 return error;
1445                         }
1446                         b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1447                         word = 0;
1448                 } else {
1449                         /*
1450                          * Go on to the previous word in the buffer.
1451                          */
1452                         b++;
1453                 }
1454         } else {
1455                 /*
1456                  * Starting on a word boundary, no partial word.
1457                  */
1458                 i = 0;
1459         }
1460         /*
1461          * Loop over whole words in buffers.  When we use up one buffer
1462          * we move on to the next one.
1463          */
1464         while (len - i >= XFS_NBWORD) {
1465                 /*
1466                  * Compute difference between actual and desired value.
1467                  */
1468                 if ((wdiff = *b ^ want)) {
1469                         /*
1470                          * Different, mark where we are and return.
1471                          */
1472                         xfs_trans_brelse(tp, bp);
1473                         i += XFS_RTLOBIT(wdiff);
1474                         *rtblock = start + i - 1;
1475                         return 0;
1476                 }
1477                 i += XFS_NBWORD;
1478                 /*
1479                  * Go on to next block if that's where the next word is
1480                  * and we need the next word.
1481                  */
1482                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1483                         /*
1484                          * If done with this block, get the next one.
1485                          */
1486                         xfs_trans_brelse(tp, bp);
1487                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1488                         if (error) {
1489                                 return error;
1490                         }
1491                         b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1492                         word = 0;
1493                 } else {
1494                         /*
1495                          * Go on to the next word in the buffer.
1496                          */
1497                         b++;
1498                 }
1499         }
1500         /*
1501          * If not ending on a word boundary, deal with the last
1502          * (partial) word.
1503          */
1504         if ((lastbit = len - i)) {
1505                 /*
1506                  * Calculate mask for all the relevant bits in this word.
1507                  */
1508                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1509                 /*
1510                  * Compute difference between actual and desired value.
1511                  */
1512                 if ((wdiff = (*b ^ want) & mask)) {
1513                         /*
1514                          * Different, mark where we are and return.
1515                          */
1516                         xfs_trans_brelse(tp, bp);
1517                         i += XFS_RTLOBIT(wdiff);
1518                         *rtblock = start + i - 1;
1519                         return 0;
1520                 } else
1521                         i = len;
1522         }
1523         /*
1524          * No match, return that we scanned the whole area.
1525          */
1526         xfs_trans_brelse(tp, bp);
1527         *rtblock = start + i - 1;
1528         return 0;
1529 }
1530
1531 /*
1532  * Mark an extent specified by start and len freed.
1533  * Updates all the summary information as well as the bitmap.
1534  */
1535 STATIC int                              /* error */
1536 xfs_rtfree_range(
1537         xfs_mount_t     *mp,            /* file system mount point */
1538         xfs_trans_t     *tp,            /* transaction pointer */
1539         xfs_rtblock_t   start,          /* starting block to free */
1540         xfs_extlen_t    len,            /* length to free */
1541         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
1542         xfs_fsblock_t   *rsb)           /* in/out: summary block number */
1543 {
1544         xfs_rtblock_t   end;            /* end of the freed extent */
1545         int             error;          /* error value */
1546         xfs_rtblock_t   postblock;      /* first block freed > end */
1547         xfs_rtblock_t   preblock;       /* first block freed < start */
1548
1549         end = start + len - 1;
1550         /*
1551          * Modify the bitmap to mark this extent freed.
1552          */
1553         error = xfs_rtmodify_range(mp, tp, start, len, 1);
1554         if (error) {
1555                 return error;
1556         }
1557         /*
1558          * Assume we're freeing out of the middle of an allocated extent.
1559          * We need to find the beginning and end of the extent so we can
1560          * properly update the summary.
1561          */
1562         error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
1563         if (error) {
1564                 return error;
1565         }
1566         /*
1567          * Find the next allocated block (end of allocated extent).
1568          */
1569         error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
1570                 &postblock);
1571         /*
1572          * If there are blocks not being freed at the front of the
1573          * old extent, add summary data for them to be allocated.
1574          */
1575         if (preblock < start) {
1576                 error = xfs_rtmodify_summary(mp, tp,
1577                         XFS_RTBLOCKLOG(start - preblock),
1578                         XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
1579                 if (error) {
1580                         return error;
1581                 }
1582         }
1583         /*
1584          * If there are blocks not being freed at the end of the
1585          * old extent, add summary data for them to be allocated.
1586          */
1587         if (postblock > end) {
1588                 error = xfs_rtmodify_summary(mp, tp,
1589                         XFS_RTBLOCKLOG(postblock - end),
1590                         XFS_BITTOBLOCK(mp, end + 1), -1, rbpp, rsb);
1591                 if (error) {
1592                         return error;
1593                 }
1594         }
1595         /*
1596          * Increment the summary information corresponding to the entire
1597          * (new) free extent.
1598          */
1599         error = xfs_rtmodify_summary(mp, tp,
1600                 XFS_RTBLOCKLOG(postblock + 1 - preblock),
1601                 XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
1602         return error;
1603 }
1604
1605 /*
1606  * Read and return the summary information for a given extent size,
1607  * bitmap block combination.
1608  * Keeps track of a current summary block, so we don't keep reading
1609  * it from the buffer cache.
1610  */
1611 STATIC int                              /* error */
1612 xfs_rtget_summary(
1613         xfs_mount_t     *mp,            /* file system mount structure */
1614         xfs_trans_t     *tp,            /* transaction pointer */
1615         int             log,            /* log2 of extent size */
1616         xfs_rtblock_t   bbno,           /* bitmap block number */
1617         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
1618         xfs_fsblock_t   *rsb,           /* in/out: summary block number */
1619         xfs_suminfo_t   *sum)           /* out: summary info for this block */
1620 {
1621         xfs_buf_t       *bp;            /* buffer for summary block */
1622         int             error;          /* error value */
1623         xfs_fsblock_t   sb;             /* summary fsblock */
1624         int             so;             /* index into the summary file */
1625         xfs_suminfo_t   *sp;            /* pointer to returned data */
1626
1627         /*
1628          * Compute entry number in the summary file.
1629          */
1630         so = XFS_SUMOFFS(mp, log, bbno);
1631         /*
1632          * Compute the block number in the summary file.
1633          */
1634         sb = XFS_SUMOFFSTOBLOCK(mp, so);
1635         /*
1636          * If we have an old buffer, and the block number matches, use that.
1637          */
1638         if (rbpp && *rbpp && *rsb == sb)
1639                 bp = *rbpp;
1640         /*
1641          * Otherwise we have to get the buffer.
1642          */
1643         else {
1644                 /*
1645                  * If there was an old one, get rid of it first.
1646                  */
1647                 if (rbpp && *rbpp)
1648                         xfs_trans_brelse(tp, *rbpp);
1649                 error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1650                 if (error) {
1651                         return error;
1652                 }
1653                 /*
1654                  * Remember this buffer and block for the next call.
1655                  */
1656                 if (rbpp) {
1657                         *rbpp = bp;
1658                         *rsb = sb;
1659                 }
1660         }
1661         /*
1662          * Point to the summary information & copy it out.
1663          */
1664         sp = XFS_SUMPTR(mp, bp, so);
1665         *sum = *sp;
1666         /*
1667          * Drop the buffer if we're not asked to remember it.
1668          */
1669         if (!rbpp)
1670                 xfs_trans_brelse(tp, bp);
1671         return 0;
1672 }
1673
1674 /*
1675  * Set the given range of bitmap bits to the given value.
1676  * Do whatever I/O and logging is required.
1677  */
1678 STATIC int                              /* error */
1679 xfs_rtmodify_range(
1680         xfs_mount_t     *mp,            /* file system mount point */
1681         xfs_trans_t     *tp,            /* transaction pointer */
1682         xfs_rtblock_t   start,          /* starting block to modify */
1683         xfs_extlen_t    len,            /* length of extent to modify */
1684         int             val)            /* 1 for free, 0 for allocated */
1685 {
1686         xfs_rtword_t    *b;             /* current word in buffer */
1687         int             bit;            /* bit number in the word */
1688         xfs_rtblock_t   block;          /* bitmap block number */
1689         xfs_buf_t       *bp;            /* buf for the block */
1690         xfs_rtword_t    *bufp;          /* starting word in buffer */
1691         int             error;          /* error value */
1692         xfs_rtword_t    *first;         /* first used word in the buffer */
1693         int             i;              /* current bit number rel. to start */
1694         int             lastbit;        /* last useful bit in word */
1695         xfs_rtword_t    mask;           /* mask o frelevant bits for value */
1696         int             word;           /* word number in the buffer */
1697
1698         /*
1699          * Compute starting bitmap block number.
1700          */
1701         block = XFS_BITTOBLOCK(mp, start);
1702         /*
1703          * Read the bitmap block, and point to its data.
1704          */
1705         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1706         if (error) {
1707                 return error;
1708         }
1709         bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1710         /*
1711          * Compute the starting word's address, and starting bit.
1712          */
1713         word = XFS_BITTOWORD(mp, start);
1714         first = b = &bufp[word];
1715         bit = (int)(start & (XFS_NBWORD - 1));
1716         /*
1717          * 0 (allocated) => all zeroes; 1 (free) => all ones.
1718          */
1719         val = -val;
1720         /*
1721          * If not starting on a word boundary, deal with the first
1722          * (partial) word.
1723          */
1724         if (bit) {
1725                 /*
1726                  * Compute first bit not changed and mask of relevant bits.
1727                  */
1728                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1729                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1730                 /*
1731                  * Set/clear the active bits.
1732                  */
1733                 if (val)
1734                         *b |= mask;
1735                 else
1736                         *b &= ~mask;
1737                 i = lastbit - bit;
1738                 /*
1739                  * Go on to the next block if that's where the next word is
1740                  * and we need the next word.
1741                  */
1742                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1743                         /*
1744                          * Log the changed part of this block.
1745                          * Get the next one.
1746                          */
1747                         xfs_trans_log_buf(tp, bp,
1748                                 (uint)((char *)first - (char *)bufp),
1749                                 (uint)((char *)b - (char *)bufp));
1750                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1751                         if (error) {
1752                                 return error;
1753                         }
1754                         first = b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1755                         word = 0;
1756                 } else {
1757                         /*
1758                          * Go on to the next word in the buffer
1759                          */
1760                         b++;
1761                 }
1762         } else {
1763                 /*
1764                  * Starting on a word boundary, no partial word.
1765                  */
1766                 i = 0;
1767         }
1768         /*
1769          * Loop over whole words in buffers.  When we use up one buffer
1770          * we move on to the next one.
1771          */
1772         while (len - i >= XFS_NBWORD) {
1773                 /*
1774                  * Set the word value correctly.
1775                  */
1776                 *b = val;
1777                 i += XFS_NBWORD;
1778                 /*
1779                  * Go on to the next block if that's where the next word is
1780                  * and we need the next word.
1781                  */
1782                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1783                         /*
1784                          * Log the changed part of this block.
1785                          * Get the next one.
1786                          */
1787                         xfs_trans_log_buf(tp, bp,
1788                                 (uint)((char *)first - (char *)bufp),
1789                                 (uint)((char *)b - (char *)bufp));
1790                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1791                         if (error) {
1792                                 return error;
1793                         }
1794                         first = b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1795                         word = 0;
1796                 } else {
1797                         /*
1798                          * Go on to the next word in the buffer
1799                          */
1800                         b++;
1801                 }
1802         }
1803         /*
1804          * If not ending on a word boundary, deal with the last
1805          * (partial) word.
1806          */
1807         if ((lastbit = len - i)) {
1808                 /*
1809                  * Compute a mask of relevant bits.
1810                  */
1811                 bit = 0;
1812                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1813                 /*
1814                  * Set/clear the active bits.
1815                  */
1816                 if (val)
1817                         *b |= mask;
1818                 else
1819                         *b &= ~mask;
1820                 b++;
1821         }
1822         /*
1823          * Log any remaining changed bytes.
1824          */
1825         if (b > first)
1826                 xfs_trans_log_buf(tp, bp, (uint)((char *)first - (char *)bufp),
1827                         (uint)((char *)b - (char *)bufp - 1));
1828         return 0;
1829 }
1830
1831 /*
1832  * Read and modify the summary information for a given extent size,
1833  * bitmap block combination.
1834  * Keeps track of a current summary block, so we don't keep reading
1835  * it from the buffer cache.
1836  */
1837 STATIC int                              /* error */
1838 xfs_rtmodify_summary(
1839         xfs_mount_t     *mp,            /* file system mount point */
1840         xfs_trans_t     *tp,            /* transaction pointer */
1841         int             log,            /* log2 of extent size */
1842         xfs_rtblock_t   bbno,           /* bitmap block number */
1843         int             delta,          /* change to make to summary info */
1844         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
1845         xfs_fsblock_t   *rsb)           /* in/out: summary block number */
1846 {
1847         xfs_buf_t       *bp;            /* buffer for the summary block */
1848         int             error;          /* error value */
1849         xfs_fsblock_t   sb;             /* summary fsblock */
1850         int             so;             /* index into the summary file */
1851         xfs_suminfo_t   *sp;            /* pointer to returned data */
1852
1853         /*
1854          * Compute entry number in the summary file.
1855          */
1856         so = XFS_SUMOFFS(mp, log, bbno);
1857         /*
1858          * Compute the block number in the summary file.
1859          */
1860         sb = XFS_SUMOFFSTOBLOCK(mp, so);
1861         /*
1862          * If we have an old buffer, and the block number matches, use that.
1863          */
1864         if (rbpp && *rbpp && *rsb == sb)
1865                 bp = *rbpp;
1866         /*
1867          * Otherwise we have to get the buffer.
1868          */
1869         else {
1870                 /*
1871                  * If there was an old one, get rid of it first.
1872                  */
1873                 if (rbpp && *rbpp)
1874                         xfs_trans_brelse(tp, *rbpp);
1875                 error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1876                 if (error) {
1877                         return error;
1878                 }
1879                 /*
1880                  * Remember this buffer and block for the next call.
1881                  */
1882                 if (rbpp) {
1883                         *rbpp = bp;
1884                         *rsb = sb;
1885                 }
1886         }
1887         /*
1888          * Point to the summary information, modify and log it.
1889          */
1890         sp = XFS_SUMPTR(mp, bp, so);
1891         *sp += delta;
1892         xfs_trans_log_buf(tp, bp, (uint)((char *)sp - (char *)XFS_BUF_PTR(bp)),
1893                 (uint)((char *)sp - (char *)XFS_BUF_PTR(bp) + sizeof(*sp) - 1));
1894         return 0;
1895 }
1896
1897 /*
1898  * Visible (exported) functions.
1899  */
1900
1901 /*
1902  * Grow the realtime area of the filesystem.
1903  */
1904 int
1905 xfs_growfs_rt(
1906         xfs_mount_t     *mp,            /* mount point for filesystem */
1907         xfs_growfs_rt_t *in)            /* growfs rt input struct */
1908 {
1909         xfs_rtblock_t   bmbno;          /* bitmap block number */
1910         xfs_buf_t       *bp;            /* temporary buffer */
1911         int             cancelflags;    /* flags for xfs_trans_cancel */
1912         int             error;          /* error return value */
1913         xfs_inode_t     *ip;            /* bitmap inode, used as lock */
1914         xfs_mount_t     *nmp;           /* new (fake) mount structure */
1915         xfs_drfsbno_t   nrblocks;       /* new number of realtime blocks */
1916         xfs_extlen_t    nrbmblocks;     /* new number of rt bitmap blocks */
1917         xfs_drtbno_t    nrextents;      /* new number of realtime extents */
1918         uint8_t         nrextslog;      /* new log2 of sb_rextents */
1919         xfs_extlen_t    nrsumblocks;    /* new number of summary blocks */
1920         uint            nrsumlevels;    /* new rt summary levels */
1921         uint            nrsumsize;      /* new size of rt summary, bytes */
1922         xfs_sb_t        *nsbp;          /* new superblock */
1923         xfs_extlen_t    rbmblocks;      /* current number of rt bitmap blocks */
1924         xfs_extlen_t    rsumblocks;     /* current number of rt summary blks */
1925         xfs_sb_t        *sbp;           /* old superblock */
1926         xfs_fsblock_t   sumbno;         /* summary block number */
1927         xfs_trans_t     *tp;            /* transaction pointer */
1928
1929         sbp = &mp->m_sb;
1930         /*
1931          * Initial error checking.
1932          */
1933         if (mp->m_rtdev_targp || mp->m_rbmip == NULL ||
1934             (nrblocks = in->newblocks) <= sbp->sb_rblocks ||
1935             (sbp->sb_rblocks && (in->extsize != sbp->sb_rextsize)))
1936                 return XFS_ERROR(EINVAL);
1937         /*
1938          * Read in the last block of the device, make sure it exists.
1939          */
1940         error = xfs_read_buf(mp, mp->m_rtdev_targp,
1941                         XFS_FSB_TO_BB(mp, in->newblocks - 1),
1942                         XFS_FSB_TO_BB(mp, 1), 0, &bp);
1943         if (error)
1944                 return error;
1945         ASSERT(bp);
1946         xfs_buf_relse(bp);
1947         /*
1948          * Calculate new parameters.  These are the final values to be reached.
1949          */
1950         nrextents = nrblocks;
1951         do_div(nrextents, in->extsize);
1952         nrbmblocks = roundup_64(nrextents, NBBY * sbp->sb_blocksize);
1953         nrextslog = xfs_highbit32(nrextents);
1954         nrsumlevels = nrextslog + 1;
1955         nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks;
1956         nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
1957         nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
1958         /*
1959          * New summary size can't be more than half the size of
1960          * the log.  This prevents us from getting a log overflow,
1961          * since we'll log basically the whole summary file at once.
1962          */
1963         if (nrsumblocks > (mp->m_sb.sb_logblocks >> 1))
1964                 return XFS_ERROR(EINVAL);
1965         /*
1966          * Get the old block counts for bitmap and summary inodes.
1967          * These can't change since other growfs callers are locked out.
1968          */
1969         rbmblocks = XFS_B_TO_FSB(mp, mp->m_rbmip->i_d.di_size);
1970         rsumblocks = XFS_B_TO_FSB(mp, mp->m_rsumip->i_d.di_size);
1971         /*
1972          * Allocate space to the bitmap and summary files, as necessary.
1973          */
1974         if ((error = xfs_growfs_rt_alloc(mp, rbmblocks, nrbmblocks,
1975                         mp->m_sb.sb_rbmino)))
1976                 return error;
1977         if ((error = xfs_growfs_rt_alloc(mp, rsumblocks, nrsumblocks,
1978                         mp->m_sb.sb_rsumino)))
1979                 return error;
1980         nmp = NULL;
1981         /*
1982          * Loop over the bitmap blocks.
1983          * We will do everything one bitmap block at a time.
1984          * Skip the current block if it is exactly full.
1985          * This also deals with the case where there were no rtextents before.
1986          */
1987         for (bmbno = sbp->sb_rbmblocks -
1988                      ((sbp->sb_rextents & ((1 << mp->m_blkbit_log) - 1)) != 0);
1989              bmbno < nrbmblocks;
1990              bmbno++) {
1991                 /*
1992                  * Allocate a new (fake) mount/sb.
1993                  */
1994                 nmp = kmem_alloc(sizeof(*nmp), KM_SLEEP);
1995                 *nmp = *mp;
1996                 nsbp = &nmp->m_sb;
1997                 /*
1998                  * Calculate new sb and mount fields for this round.
1999                  */
2000                 nsbp->sb_rextsize = in->extsize;
2001                 nsbp->sb_rbmblocks = bmbno + 1;
2002                 nsbp->sb_rblocks =
2003                         XFS_RTMIN(nrblocks,
2004                                   nsbp->sb_rbmblocks * NBBY *
2005                                   nsbp->sb_blocksize * nsbp->sb_rextsize);
2006                 nsbp->sb_rextents = nsbp->sb_rblocks;
2007                 do_div(nsbp->sb_rextents, nsbp->sb_rextsize);
2008                 nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents);
2009                 nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1;
2010                 nrsumsize =
2011                         (uint)sizeof(xfs_suminfo_t) * nrsumlevels *
2012                         nsbp->sb_rbmblocks;
2013                 nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
2014                 nmp->m_rsumsize = nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
2015                 /*
2016                  * Start a transaction, get the log reservation.
2017                  */
2018                 tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_FREE);
2019                 cancelflags = 0;
2020                 if ((error = xfs_trans_reserve(tp, 0,
2021                                 XFS_GROWRTFREE_LOG_RES(nmp), 0, 0, 0)))
2022                         goto error_exit;
2023                 /*
2024                  * Lock out other callers by grabbing the bitmap inode lock.
2025                  */
2026                 if ((error = xfs_trans_iget(mp, tp, 0, mp->m_sb.sb_rbmino,
2027                                 XFS_ILOCK_EXCL, &ip)))
2028                         goto error_exit;
2029                 ASSERT(ip == mp->m_rbmip);
2030                 /*
2031                  * Update the bitmap inode's size.
2032                  */
2033                 mp->m_rbmip->i_d.di_size =
2034                         nsbp->sb_rbmblocks * nsbp->sb_blocksize;
2035                 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
2036                 cancelflags |= XFS_TRANS_ABORT;
2037                 /*
2038                  * Get the summary inode into the transaction.
2039                  */
2040                 if ((error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rsumino,
2041                                 0, XFS_ILOCK_EXCL, &ip)))
2042                         goto error_exit;
2043                 ASSERT(ip == mp->m_rsumip);
2044                 /*
2045                  * Update the summary inode's size.
2046                  */
2047                 mp->m_rsumip->i_d.di_size = nmp->m_rsumsize;
2048                 xfs_trans_log_inode(tp, mp->m_rsumip, XFS_ILOG_CORE);
2049                 /*
2050                  * Copy summary data from old to new sizes.
2051                  * Do this when the real size (not block-aligned) changes.
2052                  */
2053                 if (sbp->sb_rbmblocks != nsbp->sb_rbmblocks ||
2054                     mp->m_rsumlevels != nmp->m_rsumlevels) {
2055                         error = xfs_rtcopy_summary(mp, nmp, tp);
2056                         if (error)
2057                                 goto error_exit;
2058                 }
2059                 /*
2060                  * Update superblock fields.
2061                  */
2062                 if (nsbp->sb_rextsize != sbp->sb_rextsize)
2063                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSIZE,
2064                                 nsbp->sb_rextsize - sbp->sb_rextsize);
2065                 if (nsbp->sb_rbmblocks != sbp->sb_rbmblocks)
2066                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBMBLOCKS,
2067                                 nsbp->sb_rbmblocks - sbp->sb_rbmblocks);
2068                 if (nsbp->sb_rblocks != sbp->sb_rblocks)
2069                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBLOCKS,
2070                                 nsbp->sb_rblocks - sbp->sb_rblocks);
2071                 if (nsbp->sb_rextents != sbp->sb_rextents)
2072                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTENTS,
2073                                 nsbp->sb_rextents - sbp->sb_rextents);
2074                 if (nsbp->sb_rextslog != sbp->sb_rextslog)
2075                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSLOG,
2076                                 nsbp->sb_rextslog - sbp->sb_rextslog);
2077                 /*
2078                  * Free new extent.
2079                  */
2080                 bp = NULL;
2081                 error = xfs_rtfree_range(nmp, tp, sbp->sb_rextents,
2082                         nsbp->sb_rextents - sbp->sb_rextents, &bp, &sumbno);
2083                 if (error)
2084                         goto error_exit;
2085                 /*
2086                  * Mark more blocks free in the superblock.
2087                  */
2088                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS,
2089                         nsbp->sb_rextents - sbp->sb_rextents);
2090                 /*
2091                  * Free the fake mp structure.
2092                  */
2093                 kmem_free(nmp, sizeof(*nmp));
2094                 nmp = NULL;
2095                 /*
2096                  * Update mp values into the real mp structure.
2097                  */
2098                 mp->m_rsumlevels = nrsumlevels;
2099                 mp->m_rsumsize = nrsumsize;
2100                 /*
2101                  * Commit the transaction.
2102                  */
2103                 xfs_trans_commit(tp, 0, NULL);
2104         }
2105         return 0;
2106
2107         /*
2108          * Error paths come here.
2109          */
2110 error_exit:
2111         if (nmp)
2112                 kmem_free(nmp, sizeof(*nmp));
2113         xfs_trans_cancel(tp, cancelflags);
2114         return error;
2115 }
2116
2117 /*
2118  * Allocate an extent in the realtime subvolume, with the usual allocation
2119  * parameters.  The length units are all in realtime extents, as is the
2120  * result block number.
2121  */
2122 int                                     /* error */
2123 xfs_rtallocate_extent(
2124         xfs_trans_t     *tp,            /* transaction pointer */
2125         xfs_rtblock_t   bno,            /* starting block number to allocate */
2126         xfs_extlen_t    minlen,         /* minimum length to allocate */
2127         xfs_extlen_t    maxlen,         /* maximum length to allocate */
2128         xfs_extlen_t    *len,           /* out: actual length allocated */
2129         xfs_alloctype_t type,           /* allocation type XFS_ALLOCTYPE... */
2130         int             wasdel,         /* was a delayed allocation extent */
2131         xfs_extlen_t    prod,           /* extent product factor */
2132         xfs_rtblock_t   *rtblock)       /* out: start block allocated */
2133 {
2134         int             error;          /* error value */
2135         xfs_inode_t     *ip;            /* inode for bitmap file */
2136         xfs_mount_t     *mp;            /* file system mount structure */
2137         xfs_rtblock_t   r;              /* result allocated block */
2138         xfs_fsblock_t   sb;             /* summary file block number */
2139         xfs_buf_t       *sumbp;         /* summary file block buffer */
2140
2141         ASSERT(minlen > 0 && minlen <= maxlen);
2142         mp = tp->t_mountp;
2143         /*
2144          * If prod is set then figure out what to do to minlen and maxlen.
2145          */
2146         if (prod > 1) {
2147                 xfs_extlen_t    i;
2148
2149                 if ((i = maxlen % prod))
2150                         maxlen -= i;
2151                 if ((i = minlen % prod))
2152                         minlen += prod - i;
2153                 if (maxlen < minlen) {
2154                         *rtblock = NULLRTBLOCK;
2155                         return 0;
2156                 }
2157         }
2158         /*
2159          * Lock out other callers by grabbing the bitmap inode lock.
2160          */
2161         error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2162         if (error) {
2163                 return error;
2164         }
2165         sumbp = NULL;
2166         /*
2167          * Allocate by size, or near another block, or exactly at some block.
2168          */
2169         switch (type) {
2170         case XFS_ALLOCTYPE_ANY_AG:
2171                 error = xfs_rtallocate_extent_size(mp, tp, minlen, maxlen, len,
2172                                 &sumbp, &sb, prod, &r);
2173                 break;
2174         case XFS_ALLOCTYPE_NEAR_BNO:
2175                 error = xfs_rtallocate_extent_near(mp, tp, bno, minlen, maxlen,
2176                                 len, &sumbp, &sb, prod, &r);
2177                 break;
2178         case XFS_ALLOCTYPE_THIS_BNO:
2179                 error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen,
2180                                 len, &sumbp, &sb, prod, &r);
2181                 break;
2182         default:
2183                 ASSERT(0);
2184         }
2185         if (error) {
2186                 return error;
2187         }
2188         /*
2189          * If it worked, update the superblock.
2190          */
2191         if (r != NULLRTBLOCK) {
2192                 long    slen = (long)*len;
2193
2194                 ASSERT(*len >= minlen && *len <= maxlen);
2195                 if (wasdel)
2196                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_RES_FREXTENTS, -slen);
2197                 else
2198                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, -slen);
2199         }
2200         *rtblock = r;
2201         return 0;
2202 }
2203
2204 /*
2205  * Free an extent in the realtime subvolume.  Length is expressed in
2206  * realtime extents, as is the block number.
2207  */
2208 int                                     /* error */
2209 xfs_rtfree_extent(
2210         xfs_trans_t     *tp,            /* transaction pointer */
2211         xfs_rtblock_t   bno,            /* starting block number to free */
2212         xfs_extlen_t    len)            /* length of extent freed */
2213 {
2214         int             error;          /* error value */
2215         xfs_inode_t     *ip;            /* bitmap file inode */
2216         xfs_mount_t     *mp;            /* file system mount structure */
2217         xfs_fsblock_t   sb;             /* summary file block number */
2218         xfs_buf_t       *sumbp;         /* summary file block buffer */
2219
2220         mp = tp->t_mountp;
2221         /*
2222          * Synchronize by locking the bitmap inode.
2223          */
2224         error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2225         if (error) {
2226                 return error;
2227         }
2228 #if defined(__KERNEL__) && defined(DEBUG)
2229         /*
2230          * Check to see that this whole range is currently allocated.
2231          */
2232         {
2233                 int     stat;           /* result from checking range */
2234
2235                 error = xfs_rtcheck_alloc_range(mp, tp, bno, len, &stat);
2236                 if (error) {
2237                         return error;
2238                 }
2239                 ASSERT(stat);
2240         }
2241 #endif
2242         sumbp = NULL;
2243         /*
2244          * Free the range of realtime blocks.
2245          */
2246         error = xfs_rtfree_range(mp, tp, bno, len, &sumbp, &sb);
2247         if (error) {
2248                 return error;
2249         }
2250         /*
2251          * Mark more blocks free in the superblock.
2252          */
2253         xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
2254         /*
2255          * If we've now freed all the blocks, reset the file sequence
2256          * number to 0.
2257          */
2258         if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
2259             mp->m_sb.sb_rextents) {
2260                 if (!(ip->i_d.di_flags & XFS_DIFLAG_NEWRTBM))
2261                         ip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2262                 *(__uint64_t *)&ip->i_d.di_atime = 0;
2263                 xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
2264         }
2265         return 0;
2266 }
2267
2268 /*
2269  * Initialize realtime fields in the mount structure.
2270  */
2271 int                             /* error */
2272 xfs_rtmount_init(
2273         xfs_mount_t     *mp)    /* file system mount structure */
2274 {
2275         xfs_buf_t       *bp;    /* buffer for last block of subvolume */
2276         xfs_daddr_t     d;      /* address of last block of subvolume */
2277         int             error;  /* error return value */
2278         xfs_sb_t        *sbp;   /* filesystem superblock copy in mount */
2279
2280         sbp = &mp->m_sb;
2281         if (sbp->sb_rblocks == 0)
2282                 return 0;
2283         if (mp->m_rtdev_targp == NULL) {
2284                 cmn_err(CE_WARN,
2285         "XFS: This filesystem has a realtime volume, use rtdev=device option");
2286                 return XFS_ERROR(ENODEV);
2287         }
2288         mp->m_rsumlevels = sbp->sb_rextslog + 1;
2289         mp->m_rsumsize =
2290                 (uint)sizeof(xfs_suminfo_t) * mp->m_rsumlevels *
2291                 sbp->sb_rbmblocks;
2292         mp->m_rsumsize = roundup(mp->m_rsumsize, sbp->sb_blocksize);
2293         mp->m_rbmip = mp->m_rsumip = NULL;
2294         /*
2295          * Check that the realtime section is an ok size.
2296          */
2297         d = (xfs_daddr_t)XFS_FSB_TO_BB(mp, mp->m_sb.sb_rblocks);
2298         if (XFS_BB_TO_FSB(mp, d) != mp->m_sb.sb_rblocks) {
2299                 cmn_err(CE_WARN, "XFS: realtime mount -- %llu != %llu",
2300                         (unsigned long long) XFS_BB_TO_FSB(mp, d),
2301                         (unsigned long long) mp->m_sb.sb_rblocks);
2302                 return XFS_ERROR(E2BIG);
2303         }
2304         error = xfs_read_buf(mp, mp->m_rtdev_targp,
2305                                 d - XFS_FSB_TO_BB(mp, 1),
2306                                 XFS_FSB_TO_BB(mp, 1), 0, &bp);
2307         if (error) {
2308                 cmn_err(CE_WARN,
2309         "XFS: realtime mount -- xfs_read_buf failed, returned %d", error);
2310                 if (error == ENOSPC)
2311                         return XFS_ERROR(E2BIG);
2312                 return error;
2313         }
2314         xfs_buf_relse(bp);
2315         return 0;
2316 }
2317
2318 /*
2319  * Get the bitmap and summary inodes into the mount structure
2320  * at mount time.
2321  */
2322 int                                     /* error */
2323 xfs_rtmount_inodes(
2324         xfs_mount_t     *mp)            /* file system mount structure */
2325 {
2326         int             error;          /* error return value */
2327         xfs_sb_t        *sbp;
2328
2329         sbp = &mp->m_sb;
2330         if (sbp->sb_rbmino == NULLFSINO)
2331                 return 0;
2332         error = xfs_iget(mp, NULL, sbp->sb_rbmino, 0, 0, &mp->m_rbmip, 0);
2333         if (error)
2334                 return error;
2335         ASSERT(mp->m_rbmip != NULL);
2336         ASSERT(sbp->sb_rsumino != NULLFSINO);
2337         error = xfs_iget(mp, NULL, sbp->sb_rsumino, 0, 0, &mp->m_rsumip, 0);
2338         if (error) {
2339                 VN_RELE(XFS_ITOV(mp->m_rbmip));
2340                 return error;
2341         }
2342         ASSERT(mp->m_rsumip != NULL);
2343         return 0;
2344 }
2345
2346 /*
2347  * Pick an extent for allocation at the start of a new realtime file.
2348  * Use the sequence number stored in the atime field of the bitmap inode.
2349  * Translate this to a fraction of the rtextents, and return the product
2350  * of rtextents and the fraction.
2351  * The fraction sequence is 0, 1/2, 1/4, 3/4, 1/8, ..., 7/8, 1/16, ...
2352  */
2353 int                                     /* error */
2354 xfs_rtpick_extent(
2355         xfs_mount_t     *mp,            /* file system mount point */
2356         xfs_trans_t     *tp,            /* transaction pointer */
2357         xfs_extlen_t    len,            /* allocation length (rtextents) */
2358         xfs_rtblock_t   *pick)          /* result rt extent */
2359 {
2360         xfs_rtblock_t   b;              /* result block */
2361         int             error;          /* error return value */
2362         xfs_inode_t     *ip;            /* bitmap incore inode */
2363         int             log2;           /* log of sequence number */
2364         __uint64_t      resid;          /* residual after log removed */
2365         __uint64_t      seq;            /* sequence number of file creation */
2366         __uint64_t      *seqp;          /* pointer to seqno in inode */
2367
2368         error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2369         if (error)
2370                 return error;
2371         ASSERT(ip == mp->m_rbmip);
2372         seqp = (__uint64_t *)&ip->i_d.di_atime;
2373         if (!(ip->i_d.di_flags & XFS_DIFLAG_NEWRTBM)) {
2374                 ip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2375                 *seqp = 0;
2376         }
2377         seq = *seqp;
2378         if ((log2 = xfs_highbit64(seq)) == -1)
2379                 b = 0;
2380         else {
2381                 resid = seq - (1ULL << log2);
2382                 b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >>
2383                     (log2 + 1);
2384                 if (b >= mp->m_sb.sb_rextents)
2385                         b = do_mod(b, mp->m_sb.sb_rextents);
2386                 if (b + len > mp->m_sb.sb_rextents)
2387                         b = mp->m_sb.sb_rextents - len;
2388         }
2389         *seqp = seq + 1;
2390         xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
2391         *pick = b;
2392         return 0;
2393 }
2394
2395 #ifdef DEBUG
2396 /*
2397  * Debug code: print out the value of a range in the bitmap.
2398  */
2399 void
2400 xfs_rtprint_range(
2401         xfs_mount_t     *mp,            /* file system mount structure */
2402         xfs_trans_t     *tp,            /* transaction pointer */
2403         xfs_rtblock_t   start,          /* starting block to print */
2404         xfs_extlen_t    len)            /* length to print */
2405 {
2406         xfs_extlen_t    i;              /* block number in the extent */
2407
2408         printk("%Ld: ", (long long)start);
2409         for (i = 0; i < len; i++)
2410                 printk("%d", xfs_rtcheck_bit(mp, tp, start + i, 1));
2411         printk("\n");
2412 }
2413
2414 /*
2415  * Debug code: print the summary file.
2416  */
2417 void
2418 xfs_rtprint_summary(
2419         xfs_mount_t     *mp,            /* file system mount structure */
2420         xfs_trans_t     *tp)            /* transaction pointer */
2421 {
2422         xfs_suminfo_t   c;              /* summary data */
2423         xfs_rtblock_t   i;              /* bitmap block number */
2424         int             l;              /* summary information level */
2425         int             p;              /* flag for printed anything */
2426         xfs_fsblock_t   sb;             /* summary block number */
2427         xfs_buf_t       *sumbp;         /* summary block buffer */
2428
2429         sumbp = NULL;
2430         for (l = 0; l < mp->m_rsumlevels; l++) {
2431                 for (p = 0, i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
2432                         (void)xfs_rtget_summary(mp, tp, l, i, &sumbp, &sb, &c);
2433                         if (c) {
2434                                 if (!p) {
2435                                         printk("%Ld-%Ld:", 1LL << l,
2436                                                 XFS_RTMIN((1LL << l) +
2437                                                           ((1LL << l) - 1LL),
2438                                                          mp->m_sb.sb_rextents));
2439                                         p = 1;
2440                                 }
2441                                 printk(" %Ld:%d", (long long)i, c);
2442                         }
2443                 }
2444                 if (p)
2445                         printk("\n");
2446         }
2447         if (sumbp)
2448                 xfs_trans_brelse(tp, sumbp);
2449 }
2450 #endif  /* DEBUG */