fs/xfs/libxfs/xfs_rtbitmap.c

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