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