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