linux/fs/xfs/libxfs/xfs_rtbitmap.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
   4 * All Rights Reserved.
   5 */
   6#include "xfs.h"
   7#include "xfs_fs.h"
   8#include "xfs_shared.h"
   9#include "xfs_format.h"
  10#include "xfs_log_format.h"
  11#include "xfs_trans_resv.h"
  12#include "xfs_bit.h"
  13#include "xfs_mount.h"
  14#include "xfs_inode.h"
  15#include "xfs_bmap.h"
  16#include "xfs_trans.h"
  17#include "xfs_rtalloc.h"
  18#include "xfs_error.h"
  19
  20/*
  21 * Realtime allocator bitmap functions shared with userspace.
  22 */
  23
  24/*
  25 * Real time buffers need verifiers to avoid runtime warnings during IO.
  26 * We don't have anything to verify, however, so these are just dummy
  27 * operations.
  28 */
  29static void
  30xfs_rtbuf_verify_read(
  31        struct xfs_buf  *bp)
  32{
  33        return;
  34}
  35
  36static void
  37xfs_rtbuf_verify_write(
  38        struct xfs_buf  *bp)
  39{
  40        return;
  41}
  42
  43const struct xfs_buf_ops xfs_rtbuf_ops = {
  44        .name = "rtbuf",
  45        .verify_read = xfs_rtbuf_verify_read,
  46        .verify_write = xfs_rtbuf_verify_write,
  47};
  48
  49/*
  50 * Get a buffer for the bitmap or summary file block specified.
  51 * The buffer is returned read and locked.
  52 */
  53int
  54xfs_rtbuf_get(
  55        xfs_mount_t     *mp,            /* file system mount structure */
  56        xfs_trans_t     *tp,            /* transaction pointer */
  57        xfs_rtblock_t   block,          /* block number in bitmap or summary */
  58        int             issum,          /* is summary not bitmap */
  59        struct xfs_buf  **bpp)          /* output: buffer for the block */
  60{
  61        struct xfs_buf  *bp;            /* block buffer, result */
  62        xfs_inode_t     *ip;            /* bitmap or summary inode */
  63        xfs_bmbt_irec_t map;
  64        int             nmap = 1;
  65        int             error;          /* error value */
  66
  67        ip = issum ? mp->m_rsumip : mp->m_rbmip;
  68
  69        error = xfs_bmapi_read(ip, block, 1, &map, &nmap, 0);
  70        if (error)
  71                return error;
  72
  73        if (XFS_IS_CORRUPT(mp, nmap == 0 || !xfs_bmap_is_written_extent(&map)))
  74                return -EFSCORRUPTED;
  75
  76        ASSERT(map.br_startblock != NULLFSBLOCK);
  77        error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
  78                                   XFS_FSB_TO_DADDR(mp, map.br_startblock),
  79                                   mp->m_bsize, 0, &bp, &xfs_rtbuf_ops);
  80        if (error)
  81                return error;
  82
  83        xfs_trans_buf_set_type(tp, bp, issum ? XFS_BLFT_RTSUMMARY_BUF
  84                                             : XFS_BLFT_RTBITMAP_BUF);
  85        *bpp = bp;
  86        return 0;
  87}
  88
  89/*
  90 * Searching backward from start to limit, find the first block whose
  91 * allocated/free state is different from start's.
  92 */
  93int
  94xfs_rtfind_back(
  95        xfs_mount_t     *mp,            /* file system mount point */
  96        xfs_trans_t     *tp,            /* transaction pointer */
  97        xfs_rtblock_t   start,          /* starting block to look at */
  98        xfs_rtblock_t   limit,          /* last block to look at */
  99        xfs_rtblock_t   *rtblock)       /* out: start block found */
 100{
 101        xfs_rtword_t    *b;             /* current word in buffer */
 102        int             bit;            /* bit number in the word */
 103        xfs_rtblock_t   block;          /* bitmap block number */
 104        struct xfs_buf  *bp;            /* buf for the block */
 105        xfs_rtword_t    *bufp;          /* starting word in buffer */
 106        int             error;          /* error value */
 107        xfs_rtblock_t   firstbit;       /* first useful bit in the word */
 108        xfs_rtblock_t   i;              /* current bit number rel. to start */
 109        xfs_rtblock_t   len;            /* length of inspected area */
 110        xfs_rtword_t    mask;           /* mask of relevant bits for value */
 111        xfs_rtword_t    want;           /* mask for "good" values */
 112        xfs_rtword_t    wdiff;          /* difference from wanted value */
 113        int             word;           /* word number in the buffer */
 114
 115        /*
 116         * Compute and read in starting bitmap block for starting block.
 117         */
 118        block = XFS_BITTOBLOCK(mp, start);
 119        error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 120        if (error) {
 121                return error;
 122        }
 123        bufp = bp->b_addr;
 124        /*
 125         * Get the first word's index & point to it.
 126         */
 127        word = XFS_BITTOWORD(mp, start);
 128        b = &bufp[word];
 129        bit = (int)(start & (XFS_NBWORD - 1));
 130        len = start - limit + 1;
 131        /*
 132         * Compute match value, based on the bit at start: if 1 (free)
 133         * then all-ones, else all-zeroes.
 134         */
 135        want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
 136        /*
 137         * If the starting position is not word-aligned, deal with the
 138         * partial word.
 139         */
 140        if (bit < XFS_NBWORD - 1) {
 141                /*
 142                 * Calculate first (leftmost) bit number to look at,
 143                 * and mask for all the relevant bits in this word.
 144                 */
 145                firstbit = XFS_RTMAX((xfs_srtblock_t)(bit - len + 1), 0);
 146                mask = (((xfs_rtword_t)1 << (bit - firstbit + 1)) - 1) <<
 147                        firstbit;
 148                /*
 149                 * Calculate the difference between the value there
 150                 * and what we're looking for.
 151                 */
 152                if ((wdiff = (*b ^ want) & mask)) {
 153                        /*
 154                         * Different.  Mark where we are and return.
 155                         */
 156                        xfs_trans_brelse(tp, bp);
 157                        i = bit - XFS_RTHIBIT(wdiff);
 158                        *rtblock = start - i + 1;
 159                        return 0;
 160                }
 161                i = bit - firstbit + 1;
 162                /*
 163                 * Go on to previous block if that's where the previous word is
 164                 * and we need the previous word.
 165                 */
 166                if (--word == -1 && i < len) {
 167                        /*
 168                         * If done with this block, get the previous one.
 169                         */
 170                        xfs_trans_brelse(tp, bp);
 171                        error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
 172                        if (error) {
 173                                return error;
 174                        }
 175                        bufp = bp->b_addr;
 176                        word = XFS_BLOCKWMASK(mp);
 177                        b = &bufp[word];
 178                } else {
 179                        /*
 180                         * Go on to the previous word in the buffer.
 181                         */
 182                        b--;
 183                }
 184        } else {
 185                /*
 186                 * Starting on a word boundary, no partial word.
 187                 */
 188                i = 0;
 189        }
 190        /*
 191         * Loop over whole words in buffers.  When we use up one buffer
 192         * we move on to the previous one.
 193         */
 194        while (len - i >= XFS_NBWORD) {
 195                /*
 196                 * Compute difference between actual and desired value.
 197                 */
 198                if ((wdiff = *b ^ want)) {
 199                        /*
 200                         * Different, mark where we are and return.
 201                         */
 202                        xfs_trans_brelse(tp, bp);
 203                        i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
 204                        *rtblock = start - i + 1;
 205                        return 0;
 206                }
 207                i += XFS_NBWORD;
 208                /*
 209                 * Go on to previous block if that's where the previous word is
 210                 * and we need the previous word.
 211                 */
 212                if (--word == -1 && i < len) {
 213                        /*
 214                         * If done with this block, get the previous one.
 215                         */
 216                        xfs_trans_brelse(tp, bp);
 217                        error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
 218                        if (error) {
 219                                return error;
 220                        }
 221                        bufp = bp->b_addr;
 222                        word = XFS_BLOCKWMASK(mp);
 223                        b = &bufp[word];
 224                } else {
 225                        /*
 226                         * Go on to the previous word in the buffer.
 227                         */
 228                        b--;
 229                }
 230        }
 231        /*
 232         * If not ending on a word boundary, deal with the last
 233         * (partial) word.
 234         */
 235        if (len - i) {
 236                /*
 237                 * Calculate first (leftmost) bit number to look at,
 238                 * and mask for all the relevant bits in this word.
 239                 */
 240                firstbit = XFS_NBWORD - (len - i);
 241                mask = (((xfs_rtword_t)1 << (len - i)) - 1) << firstbit;
 242                /*
 243                 * Compute difference between actual and desired value.
 244                 */
 245                if ((wdiff = (*b ^ want) & mask)) {
 246                        /*
 247                         * Different, mark where we are and return.
 248                         */
 249                        xfs_trans_brelse(tp, bp);
 250                        i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
 251                        *rtblock = start - i + 1;
 252                        return 0;
 253                } else
 254                        i = len;
 255        }
 256        /*
 257         * No match, return that we scanned the whole area.
 258         */
 259        xfs_trans_brelse(tp, bp);
 260        *rtblock = start - i + 1;
 261        return 0;
 262}
 263
 264/*
 265 * Searching forward from start to limit, find the first block whose
 266 * allocated/free state is different from start's.
 267 */
 268int
 269xfs_rtfind_forw(
 270        xfs_mount_t     *mp,            /* file system mount point */
 271        xfs_trans_t     *tp,            /* transaction pointer */
 272        xfs_rtblock_t   start,          /* starting block to look at */
 273        xfs_rtblock_t   limit,          /* last block to look at */
 274        xfs_rtblock_t   *rtblock)       /* out: start block found */
 275{
 276        xfs_rtword_t    *b;             /* current word in buffer */
 277        int             bit;            /* bit number in the word */
 278        xfs_rtblock_t   block;          /* bitmap block number */
 279        struct xfs_buf  *bp;            /* buf for the block */
 280        xfs_rtword_t    *bufp;          /* starting word in buffer */
 281        int             error;          /* error value */
 282        xfs_rtblock_t   i;              /* current bit number rel. to start */
 283        xfs_rtblock_t   lastbit;        /* last useful bit in the word */
 284        xfs_rtblock_t   len;            /* length of inspected area */
 285        xfs_rtword_t    mask;           /* mask of relevant bits for value */
 286        xfs_rtword_t    want;           /* mask for "good" values */
 287        xfs_rtword_t    wdiff;          /* difference from wanted value */
 288        int             word;           /* word number in the buffer */
 289
 290        /*
 291         * Compute and read in starting bitmap block for starting block.
 292         */
 293        block = XFS_BITTOBLOCK(mp, start);
 294        error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 295        if (error) {
 296                return error;
 297        }
 298        bufp = bp->b_addr;
 299        /*
 300         * Get the first word's index & point to it.
 301         */
 302        word = XFS_BITTOWORD(mp, start);
 303        b = &bufp[word];
 304        bit = (int)(start & (XFS_NBWORD - 1));
 305        len = limit - start + 1;
 306        /*
 307         * Compute match value, based on the bit at start: if 1 (free)
 308         * then all-ones, else all-zeroes.
 309         */
 310        want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
 311        /*
 312         * If the starting position is not word-aligned, deal with the
 313         * partial word.
 314         */
 315        if (bit) {
 316                /*
 317                 * Calculate last (rightmost) bit number to look at,
 318                 * and mask for all the relevant bits in this word.
 319                 */
 320                lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 321                mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 322                /*
 323                 * Calculate the difference between the value there
 324                 * and what we're looking for.
 325                 */
 326                if ((wdiff = (*b ^ want) & mask)) {
 327                        /*
 328                         * Different.  Mark where we are and return.
 329                         */
 330                        xfs_trans_brelse(tp, bp);
 331                        i = XFS_RTLOBIT(wdiff) - bit;
 332                        *rtblock = start + i - 1;
 333                        return 0;
 334                }
 335                i = lastbit - bit;
 336                /*
 337                 * Go on to next block if that's where the next word is
 338                 * and we need the next word.
 339                 */
 340                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 341                        /*
 342                         * If done with this block, get the previous one.
 343                         */
 344                        xfs_trans_brelse(tp, bp);
 345                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 346                        if (error) {
 347                                return error;
 348                        }
 349                        b = bufp = bp->b_addr;
 350                        word = 0;
 351                } else {
 352                        /*
 353                         * Go on to the previous word in the buffer.
 354                         */
 355                        b++;
 356                }
 357        } else {
 358                /*
 359                 * Starting on a word boundary, no partial word.
 360                 */
 361                i = 0;
 362        }
 363        /*
 364         * Loop over whole words in buffers.  When we use up one buffer
 365         * we move on to the next one.
 366         */
 367        while (len - i >= XFS_NBWORD) {
 368                /*
 369                 * Compute difference between actual and desired value.
 370                 */
 371                if ((wdiff = *b ^ want)) {
 372                        /*
 373                         * Different, mark where we are and return.
 374                         */
 375                        xfs_trans_brelse(tp, bp);
 376                        i += XFS_RTLOBIT(wdiff);
 377                        *rtblock = start + i - 1;
 378                        return 0;
 379                }
 380                i += XFS_NBWORD;
 381                /*
 382                 * Go on to next block if that's where the next word is
 383                 * and we need the next word.
 384                 */
 385                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 386                        /*
 387                         * If done with this block, get the next one.
 388                         */
 389                        xfs_trans_brelse(tp, bp);
 390                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 391                        if (error) {
 392                                return error;
 393                        }
 394                        b = bufp = bp->b_addr;
 395                        word = 0;
 396                } else {
 397                        /*
 398                         * Go on to the next word in the buffer.
 399                         */
 400                        b++;
 401                }
 402        }
 403        /*
 404         * If not ending on a word boundary, deal with the last
 405         * (partial) word.
 406         */
 407        if ((lastbit = len - i)) {
 408                /*
 409                 * Calculate mask for all the relevant bits in this word.
 410                 */
 411                mask = ((xfs_rtword_t)1 << lastbit) - 1;
 412                /*
 413                 * Compute difference between actual and desired value.
 414                 */
 415                if ((wdiff = (*b ^ want) & mask)) {
 416                        /*
 417                         * Different, mark where we are and return.
 418                         */
 419                        xfs_trans_brelse(tp, bp);
 420                        i += XFS_RTLOBIT(wdiff);
 421                        *rtblock = start + i - 1;
 422                        return 0;
 423                } else
 424                        i = len;
 425        }
 426        /*
 427         * No match, return that we scanned the whole area.
 428         */
 429        xfs_trans_brelse(tp, bp);
 430        *rtblock = start + i - 1;
 431        return 0;
 432}
 433
 434/*
 435 * Read and/or modify the summary information for a given extent size,
 436 * bitmap block combination.
 437 * Keeps track of a current summary block, so we don't keep reading
 438 * it from the buffer cache.
 439 *
 440 * Summary information is returned in *sum if specified.
 441 * If no delta is specified, returns summary only.
 442 */
 443int
 444xfs_rtmodify_summary_int(
 445        xfs_mount_t     *mp,            /* file system mount structure */
 446        xfs_trans_t     *tp,            /* transaction pointer */
 447        int             log,            /* log2 of extent size */
 448        xfs_rtblock_t   bbno,           /* bitmap block number */
 449        int             delta,          /* change to make to summary info */
 450        struct xfs_buf  **rbpp,         /* in/out: summary block buffer */
 451        xfs_fsblock_t   *rsb,           /* in/out: summary block number */
 452        xfs_suminfo_t   *sum)           /* out: summary info for this block */
 453{
 454        struct xfs_buf  *bp;            /* buffer for the summary block */
 455        int             error;          /* error value */
 456        xfs_fsblock_t   sb;             /* summary fsblock */
 457        int             so;             /* index into the summary file */
 458        xfs_suminfo_t   *sp;            /* pointer to returned data */
 459
 460        /*
 461         * Compute entry number in the summary file.
 462         */
 463        so = XFS_SUMOFFS(mp, log, bbno);
 464        /*
 465         * Compute the block number in the summary file.
 466         */
 467        sb = XFS_SUMOFFSTOBLOCK(mp, so);
 468        /*
 469         * If we have an old buffer, and the block number matches, use that.
 470         */
 471        if (*rbpp && *rsb == sb)
 472                bp = *rbpp;
 473        /*
 474         * Otherwise we have to get the buffer.
 475         */
 476        else {
 477                /*
 478                 * If there was an old one, get rid of it first.
 479                 */
 480                if (*rbpp)
 481                        xfs_trans_brelse(tp, *rbpp);
 482                error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
 483                if (error) {
 484                        return error;
 485                }
 486                /*
 487                 * Remember this buffer and block for the next call.
 488                 */
 489                *rbpp = bp;
 490                *rsb = sb;
 491        }
 492        /*
 493         * Point to the summary information, modify/log it, and/or copy it out.
 494         */
 495        sp = XFS_SUMPTR(mp, bp, so);
 496        if (delta) {
 497                uint first = (uint)((char *)sp - (char *)bp->b_addr);
 498
 499                *sp += delta;
 500                if (mp->m_rsum_cache) {
 501                        if (*sp == 0 && log == mp->m_rsum_cache[bbno])
 502                                mp->m_rsum_cache[bbno]++;
 503                        if (*sp != 0 && log < mp->m_rsum_cache[bbno])
 504                                mp->m_rsum_cache[bbno] = log;
 505                }
 506                xfs_trans_log_buf(tp, bp, first, first + sizeof(*sp) - 1);
 507        }
 508        if (sum)
 509                *sum = *sp;
 510        return 0;
 511}
 512
 513int
 514xfs_rtmodify_summary(
 515        xfs_mount_t     *mp,            /* file system mount structure */
 516        xfs_trans_t     *tp,            /* transaction pointer */
 517        int             log,            /* log2 of extent size */
 518        xfs_rtblock_t   bbno,           /* bitmap block number */
 519        int             delta,          /* change to make to summary info */
 520        struct xfs_buf  **rbpp,         /* in/out: summary block buffer */
 521        xfs_fsblock_t   *rsb)           /* in/out: summary block number */
 522{
 523        return xfs_rtmodify_summary_int(mp, tp, log, bbno,
 524                                        delta, rbpp, rsb, NULL);
 525}
 526
 527/*
 528 * Set the given range of bitmap bits to the given value.
 529 * Do whatever I/O and logging is required.
 530 */
 531int
 532xfs_rtmodify_range(
 533        xfs_mount_t     *mp,            /* file system mount point */
 534        xfs_trans_t     *tp,            /* transaction pointer */
 535        xfs_rtblock_t   start,          /* starting block to modify */
 536        xfs_extlen_t    len,            /* length of extent to modify */
 537        int             val)            /* 1 for free, 0 for allocated */
 538{
 539        xfs_rtword_t    *b;             /* current word in buffer */
 540        int             bit;            /* bit number in the word */
 541        xfs_rtblock_t   block;          /* bitmap block number */
 542        struct xfs_buf  *bp;            /* buf for the block */
 543        xfs_rtword_t    *bufp;          /* starting word in buffer */
 544        int             error;          /* error value */
 545        xfs_rtword_t    *first;         /* first used word in the buffer */
 546        int             i;              /* current bit number rel. to start */
 547        int             lastbit;        /* last useful bit in word */
 548        xfs_rtword_t    mask;           /* mask o frelevant bits for value */
 549        int             word;           /* word number in the buffer */
 550
 551        /*
 552         * Compute starting bitmap block number.
 553         */
 554        block = XFS_BITTOBLOCK(mp, start);
 555        /*
 556         * Read the bitmap block, and point to its data.
 557         */
 558        error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 559        if (error) {
 560                return error;
 561        }
 562        bufp = bp->b_addr;
 563        /*
 564         * Compute the starting word's address, and starting bit.
 565         */
 566        word = XFS_BITTOWORD(mp, start);
 567        first = b = &bufp[word];
 568        bit = (int)(start & (XFS_NBWORD - 1));
 569        /*
 570         * 0 (allocated) => all zeroes; 1 (free) => all ones.
 571         */
 572        val = -val;
 573        /*
 574         * If not starting on a word boundary, deal with the first
 575         * (partial) word.
 576         */
 577        if (bit) {
 578                /*
 579                 * Compute first bit not changed and mask of relevant bits.
 580                 */
 581                lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 582                mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 583                /*
 584                 * Set/clear the active bits.
 585                 */
 586                if (val)
 587                        *b |= mask;
 588                else
 589                        *b &= ~mask;
 590                i = lastbit - bit;
 591                /*
 592                 * Go on to the next block if that's where the next word is
 593                 * and we need the next word.
 594                 */
 595                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 596                        /*
 597                         * Log the changed part of this block.
 598                         * Get the next one.
 599                         */
 600                        xfs_trans_log_buf(tp, bp,
 601                                (uint)((char *)first - (char *)bufp),
 602                                (uint)((char *)b - (char *)bufp));
 603                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 604                        if (error) {
 605                                return error;
 606                        }
 607                        first = b = bufp = bp->b_addr;
 608                        word = 0;
 609                } else {
 610                        /*
 611                         * Go on to the next word in the buffer
 612                         */
 613                        b++;
 614                }
 615        } else {
 616                /*
 617                 * Starting on a word boundary, no partial word.
 618                 */
 619                i = 0;
 620        }
 621        /*
 622         * Loop over whole words in buffers.  When we use up one buffer
 623         * we move on to the next one.
 624         */
 625        while (len - i >= XFS_NBWORD) {
 626                /*
 627                 * Set the word value correctly.
 628                 */
 629                *b = val;
 630                i += XFS_NBWORD;
 631                /*
 632                 * Go on to the next block if that's where the next word is
 633                 * and we need the next word.
 634                 */
 635                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 636                        /*
 637                         * Log the changed part of this block.
 638                         * Get the next one.
 639                         */
 640                        xfs_trans_log_buf(tp, bp,
 641                                (uint)((char *)first - (char *)bufp),
 642                                (uint)((char *)b - (char *)bufp));
 643                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 644                        if (error) {
 645                                return error;
 646                        }
 647                        first = b = bufp = bp->b_addr;
 648                        word = 0;
 649                } else {
 650                        /*
 651                         * Go on to the next word in the buffer
 652                         */
 653                        b++;
 654                }
 655        }
 656        /*
 657         * If not ending on a word boundary, deal with the last
 658         * (partial) word.
 659         */
 660        if ((lastbit = len - i)) {
 661                /*
 662                 * Compute a mask of relevant bits.
 663                 */
 664                mask = ((xfs_rtword_t)1 << lastbit) - 1;
 665                /*
 666                 * Set/clear the active bits.
 667                 */
 668                if (val)
 669                        *b |= mask;
 670                else
 671                        *b &= ~mask;
 672                b++;
 673        }
 674        /*
 675         * Log any remaining changed bytes.
 676         */
 677        if (b > first)
 678                xfs_trans_log_buf(tp, bp, (uint)((char *)first - (char *)bufp),
 679                        (uint)((char *)b - (char *)bufp - 1));
 680        return 0;
 681}
 682
 683/*
 684 * Mark an extent specified by start and len freed.
 685 * Updates all the summary information as well as the bitmap.
 686 */
 687int
 688xfs_rtfree_range(
 689        xfs_mount_t     *mp,            /* file system mount point */
 690        xfs_trans_t     *tp,            /* transaction pointer */
 691        xfs_rtblock_t   start,          /* starting block to free */
 692        xfs_extlen_t    len,            /* length to free */
 693        struct xfs_buf  **rbpp,         /* in/out: summary block buffer */
 694        xfs_fsblock_t   *rsb)           /* in/out: summary block number */
 695{
 696        xfs_rtblock_t   end;            /* end of the freed extent */
 697        int             error;          /* error value */
 698        xfs_rtblock_t   postblock;      /* first block freed > end */
 699        xfs_rtblock_t   preblock;       /* first block freed < start */
 700
 701        end = start + len - 1;
 702        /*
 703         * Modify the bitmap to mark this extent freed.
 704         */
 705        error = xfs_rtmodify_range(mp, tp, start, len, 1);
 706        if (error) {
 707                return error;
 708        }
 709        /*
 710         * Assume we're freeing out of the middle of an allocated extent.
 711         * We need to find the beginning and end of the extent so we can
 712         * properly update the summary.
 713         */
 714        error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
 715        if (error) {
 716                return error;
 717        }
 718        /*
 719         * Find the next allocated block (end of allocated extent).
 720         */
 721        error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
 722                &postblock);
 723        if (error)
 724                return error;
 725        /*
 726         * If there are blocks not being freed at the front of the
 727         * old extent, add summary data for them to be allocated.
 728         */
 729        if (preblock < start) {
 730                error = xfs_rtmodify_summary(mp, tp,
 731                        XFS_RTBLOCKLOG(start - preblock),
 732                        XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
 733                if (error) {
 734                        return error;
 735                }
 736        }
 737        /*
 738         * If there are blocks not being freed at the end of the
 739         * old extent, add summary data for them to be allocated.
 740         */
 741        if (postblock > end) {
 742                error = xfs_rtmodify_summary(mp, tp,
 743                        XFS_RTBLOCKLOG(postblock - end),
 744                        XFS_BITTOBLOCK(mp, end + 1), -1, rbpp, rsb);
 745                if (error) {
 746                        return error;
 747                }
 748        }
 749        /*
 750         * Increment the summary information corresponding to the entire
 751         * (new) free extent.
 752         */
 753        error = xfs_rtmodify_summary(mp, tp,
 754                XFS_RTBLOCKLOG(postblock + 1 - preblock),
 755                XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
 756        return error;
 757}
 758
 759/*
 760 * Check that the given range is either all allocated (val = 0) or
 761 * all free (val = 1).
 762 */
 763int
 764xfs_rtcheck_range(
 765        xfs_mount_t     *mp,            /* file system mount point */
 766        xfs_trans_t     *tp,            /* transaction pointer */
 767        xfs_rtblock_t   start,          /* starting block number of extent */
 768        xfs_extlen_t    len,            /* length of extent */
 769        int             val,            /* 1 for free, 0 for allocated */
 770        xfs_rtblock_t   *new,           /* out: first block not matching */
 771        int             *stat)          /* out: 1 for matches, 0 for not */
 772{
 773        xfs_rtword_t    *b;             /* current word in buffer */
 774        int             bit;            /* bit number in the word */
 775        xfs_rtblock_t   block;          /* bitmap block number */
 776        struct xfs_buf  *bp;            /* buf for the block */
 777        xfs_rtword_t    *bufp;          /* starting word in buffer */
 778        int             error;          /* error value */
 779        xfs_rtblock_t   i;              /* current bit number rel. to start */
 780        xfs_rtblock_t   lastbit;        /* last useful bit in word */
 781        xfs_rtword_t    mask;           /* mask of relevant bits for value */
 782        xfs_rtword_t    wdiff;          /* difference from wanted value */
 783        int             word;           /* word number in the buffer */
 784
 785        /*
 786         * Compute starting bitmap block number
 787         */
 788        block = XFS_BITTOBLOCK(mp, start);
 789        /*
 790         * Read the bitmap block.
 791         */
 792        error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 793        if (error) {
 794                return error;
 795        }
 796        bufp = bp->b_addr;
 797        /*
 798         * Compute the starting word's address, and starting bit.
 799         */
 800        word = XFS_BITTOWORD(mp, start);
 801        b = &bufp[word];
 802        bit = (int)(start & (XFS_NBWORD - 1));
 803        /*
 804         * 0 (allocated) => all zero's; 1 (free) => all one's.
 805         */
 806        val = -val;
 807        /*
 808         * If not starting on a word boundary, deal with the first
 809         * (partial) word.
 810         */
 811        if (bit) {
 812                /*
 813                 * Compute first bit not examined.
 814                 */
 815                lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 816                /*
 817                 * Mask of relevant bits.
 818                 */
 819                mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 820                /*
 821                 * Compute difference between actual and desired value.
 822                 */
 823                if ((wdiff = (*b ^ val) & mask)) {
 824                        /*
 825                         * Different, compute first wrong bit and return.
 826                         */
 827                        xfs_trans_brelse(tp, bp);
 828                        i = XFS_RTLOBIT(wdiff) - bit;
 829                        *new = start + i;
 830                        *stat = 0;
 831                        return 0;
 832                }
 833                i = lastbit - bit;
 834                /*
 835                 * Go on to next block if that's where the next word is
 836                 * and we need the next word.
 837                 */
 838                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 839                        /*
 840                         * If done with this block, get the next one.
 841                         */
 842                        xfs_trans_brelse(tp, bp);
 843                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 844                        if (error) {
 845                                return error;
 846                        }
 847                        b = bufp = bp->b_addr;
 848                        word = 0;
 849                } else {
 850                        /*
 851                         * Go on to the next word in the buffer.
 852                         */
 853                        b++;
 854                }
 855        } else {
 856                /*
 857                 * Starting on a word boundary, no partial word.
 858                 */
 859                i = 0;
 860        }
 861        /*
 862         * Loop over whole words in buffers.  When we use up one buffer
 863         * we move on to the next one.
 864         */
 865        while (len - i >= XFS_NBWORD) {
 866                /*
 867                 * Compute difference between actual and desired value.
 868                 */
 869                if ((wdiff = *b ^ val)) {
 870                        /*
 871                         * Different, compute first wrong bit and return.
 872                         */
 873                        xfs_trans_brelse(tp, bp);
 874                        i += XFS_RTLOBIT(wdiff);
 875                        *new = start + i;
 876                        *stat = 0;
 877                        return 0;
 878                }
 879                i += XFS_NBWORD;
 880                /*
 881                 * Go on to next block if that's where the next word is
 882                 * and we need the next word.
 883                 */
 884                if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 885                        /*
 886                         * If done with this block, get the next one.
 887                         */
 888                        xfs_trans_brelse(tp, bp);
 889                        error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 890                        if (error) {
 891                                return error;
 892                        }
 893                        b = bufp = bp->b_addr;
 894                        word = 0;
 895                } else {
 896                        /*
 897                         * Go on to the next word in the buffer.
 898                         */
 899                        b++;
 900                }
 901        }
 902        /*
 903         * If not ending on a word boundary, deal with the last
 904         * (partial) word.
 905         */
 906        if ((lastbit = len - i)) {
 907                /*
 908                 * Mask of relevant bits.
 909                 */
 910                mask = ((xfs_rtword_t)1 << lastbit) - 1;
 911                /*
 912                 * Compute difference between actual and desired value.
 913                 */
 914                if ((wdiff = (*b ^ val) & mask)) {
 915                        /*
 916                         * Different, compute first wrong bit and return.
 917                         */
 918                        xfs_trans_brelse(tp, bp);
 919                        i += XFS_RTLOBIT(wdiff);
 920                        *new = start + i;
 921                        *stat = 0;
 922                        return 0;
 923                } else
 924                        i = len;
 925        }
 926        /*
 927         * Successful, return.
 928         */
 929        xfs_trans_brelse(tp, bp);
 930        *new = start + i;
 931        *stat = 1;
 932        return 0;
 933}
 934
 935#ifdef DEBUG
 936/*
 937 * Check that the given extent (block range) is allocated already.
 938 */
 939STATIC int                              /* error */
 940xfs_rtcheck_alloc_range(
 941        xfs_mount_t     *mp,            /* file system mount point */
 942        xfs_trans_t     *tp,            /* transaction pointer */
 943        xfs_rtblock_t   bno,            /* starting block number of extent */
 944        xfs_extlen_t    len)            /* length of extent */
 945{
 946        xfs_rtblock_t   new;            /* dummy for xfs_rtcheck_range */
 947        int             stat;
 948        int             error;
 949
 950        error = xfs_rtcheck_range(mp, tp, bno, len, 0, &new, &stat);
 951        if (error)
 952                return error;
 953        ASSERT(stat);
 954        return 0;
 955}
 956#else
 957#define xfs_rtcheck_alloc_range(m,t,b,l)        (0)
 958#endif
 959/*
 960 * Free an extent in the realtime subvolume.  Length is expressed in
 961 * realtime extents, as is the block number.
 962 */
 963int                                     /* error */
 964xfs_rtfree_extent(
 965        xfs_trans_t     *tp,            /* transaction pointer */
 966        xfs_rtblock_t   bno,            /* starting block number to free */
 967        xfs_extlen_t    len)            /* length of extent freed */
 968{
 969        int             error;          /* error value */
 970        xfs_mount_t     *mp;            /* file system mount structure */
 971        xfs_fsblock_t   sb;             /* summary file block number */
 972        struct xfs_buf  *sumbp = NULL;  /* summary file block buffer */
 973
 974        mp = tp->t_mountp;
 975
 976        ASSERT(mp->m_rbmip->i_itemp != NULL);
 977        ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
 978
 979        error = xfs_rtcheck_alloc_range(mp, tp, bno, len);
 980        if (error)
 981                return error;
 982
 983        /*
 984         * Free the range of realtime blocks.
 985         */
 986        error = xfs_rtfree_range(mp, tp, bno, len, &sumbp, &sb);
 987        if (error) {
 988                return error;
 989        }
 990        /*
 991         * Mark more blocks free in the superblock.
 992         */
 993        xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
 994        /*
 995         * If we've now freed all the blocks, reset the file sequence
 996         * number to 0.
 997         */
 998        if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
 999            mp->m_sb.sb_rextents) {
1000                if (!(mp->m_rbmip->i_d.di_flags & XFS_DIFLAG_NEWRTBM))
1001                        mp->m_rbmip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
1002                *(uint64_t *)&VFS_I(mp->m_rbmip)->i_atime = 0;
1003                xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
1004        }
1005        return 0;
1006}
1007
1008/* Find all the free records within a given range. */
1009int
1010xfs_rtalloc_query_range(
1011        struct xfs_trans                *tp,
1012        struct xfs_rtalloc_rec          *low_rec,
1013        struct xfs_rtalloc_rec          *high_rec,
1014        xfs_rtalloc_query_range_fn      fn,
1015        void                            *priv)
1016{
1017        struct xfs_rtalloc_rec          rec;
1018        struct xfs_mount                *mp = tp->t_mountp;
1019        xfs_rtblock_t                   rtstart;
1020        xfs_rtblock_t                   rtend;
1021        int                             is_free;
1022        int                             error = 0;
1023
1024        if (low_rec->ar_startext > high_rec->ar_startext)
1025                return -EINVAL;
1026        if (low_rec->ar_startext >= mp->m_sb.sb_rextents ||
1027            low_rec->ar_startext == high_rec->ar_startext)
1028                return 0;
1029        high_rec->ar_startext = min(high_rec->ar_startext,
1030                        mp->m_sb.sb_rextents - 1);
1031
1032        /* Iterate the bitmap, looking for discrepancies. */
1033        rtstart = low_rec->ar_startext;
1034        while (rtstart <= high_rec->ar_startext) {
1035                /* Is the first block free? */
1036                error = xfs_rtcheck_range(mp, tp, rtstart, 1, 1, &rtend,
1037                                &is_free);
1038                if (error)
1039                        break;
1040
1041                /* How long does the extent go for? */
1042                error = xfs_rtfind_forw(mp, tp, rtstart,
1043                                high_rec->ar_startext, &rtend);
1044                if (error)
1045                        break;
1046
1047                if (is_free) {
1048                        rec.ar_startext = rtstart;
1049                        rec.ar_extcount = rtend - rtstart + 1;
1050
1051                        error = fn(tp, &rec, priv);
1052                        if (error)
1053                                break;
1054                }
1055
1056                rtstart = rtend + 1;
1057        }
1058
1059        return error;
1060}
1061
1062/* Find all the free records. */
1063int
1064xfs_rtalloc_query_all(
1065        struct xfs_trans                *tp,
1066        xfs_rtalloc_query_range_fn      fn,
1067        void                            *priv)
1068{
1069        struct xfs_rtalloc_rec          keys[2];
1070
1071        keys[0].ar_startext = 0;
1072        keys[1].ar_startext = tp->t_mountp->m_sb.sb_rextents - 1;
1073        keys[0].ar_extcount = keys[1].ar_extcount = 0;
1074
1075        return xfs_rtalloc_query_range(tp, &keys[0], &keys[1], fn, priv);
1076}
1077
1078/* Is the given extent all free? */
1079int
1080xfs_rtalloc_extent_is_free(
1081        struct xfs_mount                *mp,
1082        struct xfs_trans                *tp,
1083        xfs_rtblock_t                   start,
1084        xfs_extlen_t                    len,
1085        bool                            *is_free)
1086{
1087        xfs_rtblock_t                   end;
1088        int                             matches;
1089        int                             error;
1090
1091        error = xfs_rtcheck_range(mp, tp, start, len, 1, &end, &matches);
1092        if (error)
1093                return error;
1094
1095        *is_free = matches;
1096        return 0;
1097}
1098