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_rtxnum_t    start,          /* starting rtext to look at */
  99         xfs_rtxnum_t    limit,          /* last rtext to look at */
 100         xfs_rtxnum_t    *rtx)           /* out: start rtext 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         int             error;          /* error value */
 107         xfs_rtxnum_t    firstbit;       /* first useful bit in the word */
 108         xfs_rtxnum_t    i;              /* current bit number rel. to start */
 109         xfs_rtxnum_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         unsigned int    word;           /* word number in the buffer */
 114
 115         /*
 116          * Compute and read in starting bitmap block for starting block.
 117          */
 118         block = xfs_rtx_to_rbmblock(mp, start);
 119         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 120         if (error) {
 121                 return error;
 122         }
 123
 124         /*
 125          * Get the first word's index & point to it.
 126          */
 127         word = xfs_rtx_to_rbmword(mp, start);
 128         b = xfs_rbmblock_wordptr(bp, 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                         *rtx = 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
 176                         word = mp->m_blockwsize - 1;
 177                         b = xfs_rbmblock_wordptr(bp, 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                         *rtx = 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
 222                         word = mp->m_blockwsize - 1;
 223                         b = xfs_rbmblock_wordptr(bp, 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                         *rtx = 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         *rtx = 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  */
 268 int
 269 xfs_rtfind_forw(
 270         xfs_mount_t     *mp,            /* file system mount point */
 271         xfs_trans_t     *tp,            /* transaction pointer */
 272         xfs_rtxnum_t    start,          /* starting rtext to look at */
 273         xfs_rtxnum_t    limit,          /* last rtext to look at */
 274         xfs_rtxnum_t    *rtx)           /* out: start rtext found */
 275 {
 276         xfs_rtword_t    *b;             /* current word in buffer */
 277         int             bit;            /* bit number in the word */
 278         xfs_fileoff_t   block;          /* bitmap block number */
 279         struct xfs_buf  *bp;            /* buf for the block */
 280         int             error;          /* error value */
 281         xfs_rtxnum_t    i;              /* current bit number rel. to start */
 282         xfs_rtxnum_t    lastbit;        /* last useful bit in the word */
 283         xfs_rtxnum_t    len;            /* length of inspected area */
 284         xfs_rtword_t    mask;           /* mask of relevant bits for value */
 285         xfs_rtword_t    want;           /* mask for "good" values */
 286         xfs_rtword_t    wdiff;          /* difference from wanted value */
 287         unsigned int    word;           /* word number in the buffer */
 288
 289         /*
 290          * Compute and read in starting bitmap block for starting block.
 291          */
 292         block = xfs_rtx_to_rbmblock(mp, start);
 293         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 294         if (error) {
 295                 return error;
 296         }
 297
 298         /*
 299          * Get the first word's index & point to it.
 300          */
 301         word = xfs_rtx_to_rbmword(mp, start);
 302         b = xfs_rbmblock_wordptr(bp, word);
 303         bit = (int)(start & (XFS_NBWORD - 1));
 304         len = limit - start + 1;
 305         /*
 306          * Compute match value, based on the bit at start: if 1 (free)
 307          * then all-ones, else all-zeroes.
 308          */
 309         want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
 310         /*
 311          * If the starting position is not word-aligned, deal with the
 312          * partial word.
 313          */
 314         if (bit) {
 315                 /*
 316                  * Calculate last (rightmost) bit number to look at,
 317                  * and mask for all the relevant bits in this word.
 318                  */
 319                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 320                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 321                 /*
 322                  * Calculate the difference between the value there
 323                  * and what we're looking for.
 324                  */
 325                 if ((wdiff = (*b ^ want) & mask)) {
 326                         /*
 327                          * Different.  Mark where we are and return.
 328                          */
 329                         xfs_trans_brelse(tp, bp);
 330                         i = XFS_RTLOBIT(wdiff) - bit;
 331                         *rtx = start + i - 1;
 332                         return 0;
 333                 }
 334                 i = lastbit - bit;
 335                 /*
 336                  * Go on to next block if that's where the next word is
 337                  * and we need the next word.
 338                  */
 339                 if (++word == mp->m_blockwsize && i < len) {
 340                         /*
 341                          * If done with this block, get the previous one.
 342                          */
 343                         xfs_trans_brelse(tp, bp);
 344                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 345                         if (error) {
 346                                 return error;
 347                         }
 348
 349                         word = 0;
 350                         b = xfs_rbmblock_wordptr(bp, word);
 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                         *rtx = 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 == mp->m_blockwsize && 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
 395                         word = 0;
 396                         b = xfs_rbmblock_wordptr(bp, word);
 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                         *rtx = 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         *rtx = 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         xfs_rtsumoff_t  so;             /* index into the summary file */
 459         xfs_suminfo_t   *sp;            /* pointer to returned data */
 460         unsigned int    infoword;
 461
 462         /*
 463          * Compute entry number in the summary file.
 464          */
 465         so = xfs_rtsumoffs(mp, log, bbno);
 466         /*
 467          * Compute the block number in the summary file.
 468          */
 469         sb = xfs_rtsumoffs_to_block(mp, so);
 470         /*
 471          * If we have an old buffer, and the block number matches, use that.
 472          */
 473         if (*rbpp && *rsb == sb)
 474                 bp = *rbpp;
 475         /*
 476          * Otherwise we have to get the buffer.
 477          */
 478         else {
 479                 /*
 480                  * If there was an old one, get rid of it first.
 481                  */
 482                 if (*rbpp)
 483                         xfs_trans_brelse(tp, *rbpp);
 484                 error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
 485                 if (error) {
 486                         return error;
 487                 }
 488                 /*
 489                  * Remember this buffer and block for the next call.
 490                  */
 491                 *rbpp = bp;
 492                 *rsb = sb;
 493         }
 494         /*
 495          * Point to the summary information, modify/log it, and/or copy it out.
 496          */
 497         infoword = xfs_rtsumoffs_to_infoword(mp, so);
 498         sp = xfs_rsumblock_infoptr(bp, infoword);
 499         if (delta) {
 500                 uint first = (uint)((char *)sp - (char *)bp->b_addr);
 501
 502                 *sp += delta;
 503                 if (mp->m_rsum_cache) {
 504                         if (*sp == 0 && log == mp->m_rsum_cache[bbno])
 505                                 mp->m_rsum_cache[bbno]++;
 506                         if (*sp != 0 && log < mp->m_rsum_cache[bbno])
 507                                 mp->m_rsum_cache[bbno] = log;
 508                 }
 509                 xfs_trans_log_buf(tp, bp, first, first + sizeof(*sp) - 1);
 510         }
 511         if (sum)
 512                 *sum = *sp;
 513         return 0;
 514 }
 515
 516 int
 517 xfs_rtmodify_summary(
 518         xfs_mount_t     *mp,            /* file system mount structure */
 519         xfs_trans_t     *tp,            /* transaction pointer */
 520         int             log,            /* log2 of extent size */
 521         xfs_fileoff_t   bbno,           /* bitmap block number */
 522         int             delta,          /* change to make to summary info */
 523         struct xfs_buf  **rbpp,         /* in/out: summary block buffer */
 524         xfs_fileoff_t   *rsb)           /* in/out: summary block number */
 525 {
 526         return xfs_rtmodify_summary_int(mp, tp, log, bbno,
 527                                         delta, rbpp, rsb, NULL);
 528 }
 529
 530 /*
 531  * Set the given range of bitmap bits to the given value.
 532  * Do whatever I/O and logging is required.
 533  */
 534 int
 535 xfs_rtmodify_range(
 536         xfs_mount_t     *mp,            /* file system mount point */
 537         xfs_trans_t     *tp,            /* transaction pointer */
 538         xfs_rtxnum_t    start,          /* starting rtext to modify */
 539         xfs_rtxlen_t    len,            /* length of extent to modify */
 540         int             val)            /* 1 for free, 0 for allocated */
 541 {
 542         xfs_rtword_t    *b;             /* current word in buffer */
 543         int             bit;            /* bit number in the word */
 544         xfs_fileoff_t   block;          /* bitmap block number */
 545         struct xfs_buf  *bp;            /* buf for the block */
 546         int             error;          /* error value */
 547         xfs_rtword_t    *first;         /* first used word in the buffer */
 548         int             i;              /* current bit number rel. to start */
 549         int             lastbit;        /* last useful bit in word */
 550         xfs_rtword_t    mask;           /* mask o frelevant bits for value */
 551         unsigned int    word;           /* word number in the buffer */
 552
 553         /*
 554          * Compute starting bitmap block number.
 555          */
 556         block = xfs_rtx_to_rbmblock(mp, start);
 557         /*
 558          * Read the bitmap block, and point to its data.
 559          */
 560         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 561         if (error) {
 562                 return error;
 563         }
 564
 565         /*
 566          * Compute the starting word's address, and starting bit.
 567          */
 568         word = xfs_rtx_to_rbmword(mp, start);
 569         first = b = xfs_rbmblock_wordptr(bp, word);
 570         bit = (int)(start & (XFS_NBWORD - 1));
 571         /*
 572          * 0 (allocated) => all zeroes; 1 (free) => all ones.
 573          */
 574         val = -val;
 575         /*
 576          * If not starting on a word boundary, deal with the first
 577          * (partial) word.
 578          */
 579         if (bit) {
 580                 /*
 581                  * Compute first bit not changed and mask of relevant bits.
 582                  */
 583                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 584                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 585                 /*
 586                  * Set/clear the active bits.
 587                  */
 588                 if (val)
 589                         *b |= mask;
 590                 else
 591                         *b &= ~mask;
 592                 i = lastbit - bit;
 593                 /*
 594                  * Go on to the next block if that's where the next word is
 595                  * and we need the next word.
 596                  */
 597                 if (++word == mp->m_blockwsize && i < len) {
 598                         /*
 599                          * Log the changed part of this block.
 600                          * Get the next one.
 601                          */
 602                         xfs_trans_log_buf(tp, bp,
 603                                 (uint)((char *)first - (char *)bp->b_addr),
 604                                 (uint)((char *)b - (char *)bp->b_addr));
 605                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 606                         if (error) {
 607                                 return error;
 608                         }
 609
 610                         word = 0;
 611                         first = b = xfs_rbmblock_wordptr(bp, word);
 612                 } else {
 613                         /*
 614                          * Go on to the next word in the buffer
 615                          */
 616                         b++;
 617                 }
 618         } else {
 619                 /*
 620                  * Starting on a word boundary, no partial word.
 621                  */
 622                 i = 0;
 623         }
 624         /*
 625          * Loop over whole words in buffers.  When we use up one buffer
 626          * we move on to the next one.
 627          */
 628         while (len - i >= XFS_NBWORD) {
 629                 /*
 630                  * Set the word value correctly.
 631                  */
 632                 *b = val;
 633                 i += XFS_NBWORD;
 634                 /*
 635                  * Go on to the next block if that's where the next word is
 636                  * and we need the next word.
 637                  */
 638                 if (++word == mp->m_blockwsize && i < len) {
 639                         /*
 640                          * Log the changed part of this block.
 641                          * Get the next one.
 642                          */
 643                         xfs_trans_log_buf(tp, bp,
 644                                 (uint)((char *)first - (char *)bp->b_addr),
 645                                 (uint)((char *)b - (char *)bp->b_addr));
 646                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 647                         if (error) {
 648                                 return error;
 649                         }
 650
 651                         word = 0;
 652                         first = b = xfs_rbmblock_wordptr(bp, word);
 653                 } else {
 654                         /*
 655                          * Go on to the next word in the buffer
 656                          */
 657                         b++;
 658                 }
 659         }
 660         /*
 661          * If not ending on a word boundary, deal with the last
 662          * (partial) word.
 663          */
 664         if ((lastbit = len - i)) {
 665                 /*
 666                  * Compute a mask of relevant bits.
 667                  */
 668                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
 669                 /*
 670                  * Set/clear the active bits.
 671                  */
 672                 if (val)
 673                         *b |= mask;
 674                 else
 675                         *b &= ~mask;
 676                 b++;
 677         }
 678         /*
 679          * Log any remaining changed bytes.
 680          */
 681         if (b > first)
 682                 xfs_trans_log_buf(tp, bp,
 683                         (uint)((char *)first - (char *)bp->b_addr),
 684                         (uint)((char *)b - (char *)bp->b_addr - 1));
 685         return 0;
 686 }
 687
 688 /*
 689  * Mark an extent specified by start and len freed.
 690  * Updates all the summary information as well as the bitmap.
 691  */
 692 int
 693 xfs_rtfree_range(
 694         xfs_mount_t     *mp,            /* file system mount point */
 695         xfs_trans_t     *tp,            /* transaction pointer */
 696         xfs_rtxnum_t    start,          /* starting rtext to free */
 697         xfs_rtxlen_t    len,            /* length to free */
 698         struct xfs_buf  **rbpp,         /* in/out: summary block buffer */
 699         xfs_fileoff_t   *rsb)           /* in/out: summary block number */
 700 {
 701         xfs_rtxnum_t    end;            /* end of the freed extent */
 702         int             error;          /* error value */
 703         xfs_rtxnum_t    postblock;      /* first rtext freed > end */
 704         xfs_rtxnum_t    preblock;       /* first rtext freed < start */
 705
 706         end = start + len - 1;
 707         /*
 708          * Modify the bitmap to mark this extent freed.
 709          */
 710         error = xfs_rtmodify_range(mp, tp, start, len, 1);
 711         if (error) {
 712                 return error;
 713         }
 714         /*
 715          * Assume we're freeing out of the middle of an allocated extent.
 716          * We need to find the beginning and end of the extent so we can
 717          * properly update the summary.
 718          */
 719         error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
 720         if (error) {
 721                 return error;
 722         }
 723         /*
 724          * Find the next allocated block (end of allocated extent).
 725          */
 726         error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
 727                 &postblock);
 728         if (error)
 729                 return error;
 730         /*
 731          * If there are blocks not being freed at the front of the
 732          * old extent, add summary data for them to be allocated.
 733          */
 734         if (preblock < start) {
 735                 error = xfs_rtmodify_summary(mp, tp,
 736                         XFS_RTBLOCKLOG(start - preblock),
 737                         xfs_rtx_to_rbmblock(mp, preblock), -1, rbpp, rsb);
 738                 if (error) {
 739                         return error;
 740                 }
 741         }
 742         /*
 743          * If there are blocks not being freed at the end of the
 744          * old extent, add summary data for them to be allocated.
 745          */
 746         if (postblock > end) {
 747                 error = xfs_rtmodify_summary(mp, tp,
 748                         XFS_RTBLOCKLOG(postblock - end),
 749                         xfs_rtx_to_rbmblock(mp, end + 1), -1, rbpp, rsb);
 750                 if (error) {
 751                         return error;
 752                 }
 753         }
 754         /*
 755          * Increment the summary information corresponding to the entire
 756          * (new) free extent.
 757          */
 758         error = xfs_rtmodify_summary(mp, tp,
 759                 XFS_RTBLOCKLOG(postblock + 1 - preblock),
 760                 xfs_rtx_to_rbmblock(mp, preblock), 1, rbpp, rsb);
 761         return error;
 762 }
 763
 764 /*
 765  * Check that the given range is either all allocated (val = 0) or
 766  * all free (val = 1).
 767  */
 768 int
 769 xfs_rtcheck_range(
 770         xfs_mount_t     *mp,            /* file system mount point */
 771         xfs_trans_t     *tp,            /* transaction pointer */
 772         xfs_rtxnum_t    start,          /* starting rtext number of extent */
 773         xfs_rtxlen_t    len,            /* length of extent */
 774         int             val,            /* 1 for free, 0 for allocated */
 775         xfs_rtxnum_t    *new,           /* out: first rtext not matching */
 776         int             *stat)          /* out: 1 for matches, 0 for not */
 777 {
 778         xfs_rtword_t    *b;             /* current word in buffer */
 779         int             bit;            /* bit number in the word */
 780         xfs_fileoff_t   block;          /* bitmap block number */
 781         struct xfs_buf  *bp;            /* buf for the block */
 782         int             error;          /* error value */
 783         xfs_rtxnum_t    i;              /* current bit number rel. to start */
 784         xfs_rtxnum_t    lastbit;        /* last useful bit in word */
 785         xfs_rtword_t    mask;           /* mask of relevant bits for value */
 786         xfs_rtword_t    wdiff;          /* difference from wanted value */
 787         unsigned int    word;           /* word number in the buffer */
 788
 789         /*
 790          * Compute starting bitmap block number
 791          */
 792         block = xfs_rtx_to_rbmblock(mp, start);
 793         /*
 794          * Read the bitmap block.
 795          */
 796         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 797         if (error) {
 798                 return error;
 799         }
 800
 801         /*
 802          * Compute the starting word's address, and starting bit.
 803          */
 804         word = xfs_rtx_to_rbmword(mp, start);
 805         b = xfs_rbmblock_wordptr(bp, word);
 806         bit = (int)(start & (XFS_NBWORD - 1));
 807         /*
 808          * 0 (allocated) => all zero's; 1 (free) => all one's.
 809          */
 810         val = -val;
 811         /*
 812          * If not starting on a word boundary, deal with the first
 813          * (partial) word.
 814          */
 815         if (bit) {
 816                 /*
 817                  * Compute first bit not examined.
 818                  */
 819                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 820                 /*
 821                  * Mask of relevant bits.
 822                  */
 823                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 824                 /*
 825                  * Compute difference between actual and desired value.
 826                  */
 827                 if ((wdiff = (*b ^ val) & mask)) {
 828                         /*
 829                          * Different, compute first wrong bit and return.
 830                          */
 831                         xfs_trans_brelse(tp, bp);
 832                         i = XFS_RTLOBIT(wdiff) - bit;
 833                         *new = start + i;
 834                         *stat = 0;
 835                         return 0;
 836                 }
 837                 i = lastbit - bit;
 838                 /*
 839                  * Go on to next block if that's where the next word is
 840                  * and we need the next word.
 841                  */
 842                 if (++word == mp->m_blockwsize && i < len) {
 843                         /*
 844                          * If done with this block, get the next one.
 845                          */
 846                         xfs_trans_brelse(tp, bp);
 847                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 848                         if (error) {
 849                                 return error;
 850                         }
 851
 852                         word = 0;
 853                         b = xfs_rbmblock_wordptr(bp, word);
 854                 } else {
 855                         /*
 856                          * Go on to the next word in the buffer.
 857                          */
 858                         b++;
 859                 }
 860         } else {
 861                 /*
 862                  * Starting on a word boundary, no partial word.
 863                  */
 864                 i = 0;
 865         }
 866         /*
 867          * Loop over whole words in buffers.  When we use up one buffer
 868          * we move on to the next one.
 869          */
 870         while (len - i >= XFS_NBWORD) {
 871                 /*
 872                  * Compute difference between actual and desired value.
 873                  */
 874                 if ((wdiff = *b ^ val)) {
 875                         /*
 876                          * Different, compute first wrong bit and return.
 877                          */
 878                         xfs_trans_brelse(tp, bp);
 879                         i += XFS_RTLOBIT(wdiff);
 880                         *new = start + i;
 881                         *stat = 0;
 882                         return 0;
 883                 }
 884                 i += XFS_NBWORD;
 885                 /*
 886                  * Go on to next block if that's where the next word is
 887                  * and we need the next word.
 888                  */
 889                 if (++word == mp->m_blockwsize && i < len) {
 890                         /*
 891                          * If done with this block, get the next one.
 892                          */
 893                         xfs_trans_brelse(tp, bp);
 894                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 895                         if (error) {
 896                                 return error;
 897                         }
 898
 899                         word = 0;
 900                         b = xfs_rbmblock_wordptr(bp, word);
 901                 } else {
 902                         /*
 903                          * Go on to the next word in the buffer.
 904                          */
 905                         b++;
 906                 }
 907         }
 908         /*
 909          * If not ending on a word boundary, deal with the last
 910          * (partial) word.
 911          */
 912         if ((lastbit = len - i)) {
 913                 /*
 914                  * Mask of relevant bits.
 915                  */
 916                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
 917                 /*
 918                  * Compute difference between actual and desired value.
 919                  */
 920                 if ((wdiff = (*b ^ val) & mask)) {
 921                         /*
 922                          * Different, compute first wrong bit and return.
 923                          */
 924                         xfs_trans_brelse(tp, bp);
 925                         i += XFS_RTLOBIT(wdiff);
 926                         *new = start + i;
 927                         *stat = 0;
 928                         return 0;
 929                 } else
 930                         i = len;
 931         }
 932         /*
 933          * Successful, return.
 934          */
 935         xfs_trans_brelse(tp, bp);
 936         *new = start + i;
 937         *stat = 1;
 938         return 0;
 939 }
 940
 941 #ifdef DEBUG
 942 /*
 943  * Check that the given extent (block range) is allocated already.
 944  */
 945 STATIC int                              /* error */
 946 xfs_rtcheck_alloc_range(
 947         xfs_mount_t     *mp,            /* file system mount point */
 948         xfs_trans_t     *tp,            /* transaction pointer */
 949         xfs_rtxnum_t    start,          /* starting rtext number of extent */
 950         xfs_rtxlen_t    len)            /* length of extent */
 951 {
 952         xfs_rtxnum_t    new;            /* dummy for xfs_rtcheck_range */
 953         int             stat;
 954         int             error;
 955
 956         error = xfs_rtcheck_range(mp, tp, start, len, 0, &new, &stat);
 957         if (error)
 958                 return error;
 959         ASSERT(stat);
 960         return 0;
 961 }
 962 #else
 963 #define xfs_rtcheck_alloc_range(m,t,b,l)        (0)
 964 #endif
 965 /*
 966  * Free an extent in the realtime subvolume.  Length is expressed in
 967  * realtime extents, as is the block number.
 968  */
 969 int                                     /* error */
 970 xfs_rtfree_extent(
 971         xfs_trans_t     *tp,            /* transaction pointer */
 972         xfs_rtxnum_t    start,          /* starting rtext number to free */
 973         xfs_rtxlen_t    len)            /* length of extent freed */
 974 {
 975         int             error;          /* error value */
 976         xfs_mount_t     *mp;            /* file system mount structure */
 977         xfs_fsblock_t   sb;             /* summary file block number */
 978         struct xfs_buf  *sumbp = NULL;  /* summary file block buffer */
 979
 980         mp = tp->t_mountp;
 981
 982         ASSERT(mp->m_rbmip->i_itemp != NULL);
 983         ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
 984
 985         error = xfs_rtcheck_alloc_range(mp, tp, start, len);
 986         if (error)
 987                 return error;
 988
 989         /*
 990          * Free the range of realtime blocks.
 991          */
 992         error = xfs_rtfree_range(mp, tp, start, len, &sumbp, &sb);
 993         if (error) {
 994                 return error;
 995         }
 996         /*
 997          * Mark more blocks free in the superblock.
 998          */
 999         xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
1000         /*
1001          * If we've now freed all the blocks, reset the file sequence
1002          * number to 0.
1003          */
1004         if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
1005             mp->m_sb.sb_rextents) {
1006                 if (!(mp->m_rbmip->i_diflags & XFS_DIFLAG_NEWRTBM))
1007                         mp->m_rbmip->i_diflags |= XFS_DIFLAG_NEWRTBM;
1008                 *(uint64_t *)&VFS_I(mp->m_rbmip)->i_atime = 0;
1009                 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
1010         }
1011         return 0;
1012 }
1013
1014 /*
1015  * Free some blocks in the realtime subvolume.  rtbno and rtlen are in units of
1016  * rt blocks, not rt extents; must be aligned to the rt extent size; and rtlen
1017  * cannot exceed XFS_MAX_BMBT_EXTLEN.
1018  */
1019 int
1020 xfs_rtfree_blocks(
1021         struct xfs_trans        *tp,
1022         xfs_fsblock_t           rtbno,
1023         xfs_filblks_t           rtlen)
1024 {
1025         struct xfs_mount        *mp = tp->t_mountp;
1026         xfs_rtxnum_t            start;
1027         xfs_filblks_t           len;
1028         xfs_extlen_t            mod;
1029
1030         ASSERT(rtlen <= XFS_MAX_BMBT_EXTLEN);
1031
1032         len = xfs_rtb_to_rtxrem(mp, rtlen, &mod);
1033         if (mod) {
1034                 ASSERT(mod == 0);
1035                 return -EIO;
1036         }
1037
1038         start = xfs_rtb_to_rtxrem(mp, rtbno, &mod);
1039         if (mod) {
1040                 ASSERT(mod == 0);
1041                 return -EIO;
1042         }
1043
1044         return xfs_rtfree_extent(tp, start, len);
1045 }
1046
1047 /* Find all the free records within a given range. */
1048 int
1049 xfs_rtalloc_query_range(
1050         struct xfs_mount                *mp,
1051         struct xfs_trans                *tp,
1052         const struct xfs_rtalloc_rec    *low_rec,
1053         const struct xfs_rtalloc_rec    *high_rec,
1054         xfs_rtalloc_query_range_fn      fn,
1055         void                            *priv)
1056 {
1057         struct xfs_rtalloc_rec          rec;
1058         xfs_rtxnum_t                    rtstart;
1059         xfs_rtxnum_t                    rtend;
1060         xfs_rtxnum_t                    high_key;
1061         int                             is_free;
1062         int                             error = 0;
1063
1064         if (low_rec->ar_startext > high_rec->ar_startext)
1065                 return -EINVAL;
1066         if (low_rec->ar_startext >= mp->m_sb.sb_rextents ||
1067             low_rec->ar_startext == high_rec->ar_startext)
1068                 return 0;
1069
1070         high_key = min(high_rec->ar_startext, mp->m_sb.sb_rextents - 1);
1071
1072         /* Iterate the bitmap, looking for discrepancies. */
1073         rtstart = low_rec->ar_startext;
1074         while (rtstart <= high_key) {
1075                 /* Is the first block free? */
1076                 error = xfs_rtcheck_range(mp, tp, rtstart, 1, 1, &rtend,
1077                                 &is_free);
1078                 if (error)
1079                         break;
1080
1081                 /* How long does the extent go for? */
1082                 error = xfs_rtfind_forw(mp, tp, rtstart, high_key, &rtend);
1083                 if (error)
1084                         break;
1085
1086                 if (is_free) {
1087                         rec.ar_startext = rtstart;
1088                         rec.ar_extcount = rtend - rtstart + 1;
1089
1090                         error = fn(mp, tp, &rec, priv);
1091                         if (error)
1092                                 break;
1093                 }
1094
1095                 rtstart = rtend + 1;
1096         }
1097
1098         return error;
1099 }
1100
1101 /* Find all the free records. */
1102 int
1103 xfs_rtalloc_query_all(
1104         struct xfs_mount                *mp,
1105         struct xfs_trans                *tp,
1106         xfs_rtalloc_query_range_fn      fn,
1107         void                            *priv)
1108 {
1109         struct xfs_rtalloc_rec          keys[2];
1110
1111         keys[0].ar_startext = 0;
1112         keys[1].ar_startext = mp->m_sb.sb_rextents - 1;
1113         keys[0].ar_extcount = keys[1].ar_extcount = 0;
1114
1115         return xfs_rtalloc_query_range(mp, tp, &keys[0], &keys[1], fn, priv);
1116 }
1117
1118 /* Is the given extent all free? */
1119 int
1120 xfs_rtalloc_extent_is_free(
1121         struct xfs_mount                *mp,
1122         struct xfs_trans                *tp,
1123         xfs_rtxnum_t                    start,
1124         xfs_rtxlen_t                    len,
1125         bool                            *is_free)
1126 {
1127         xfs_rtxnum_t                    end;
1128         int                             matches;
1129         int                             error;
1130
1131         error = xfs_rtcheck_range(mp, tp, start, len, 1, &end, &matches);
1132         if (error)
1133                 return error;
1134
1135         *is_free = matches;
1136         return 0;
1137 }
1138
1139 /*
1140  * Compute the number of rtbitmap blocks needed to track the given number of rt
1141  * extents.
1142  */
1143 xfs_filblks_t
1144 xfs_rtbitmap_blockcount(
1145         struct xfs_mount        *mp,
1146         xfs_rtbxlen_t           rtextents)
1147 {
1148         return howmany_64(rtextents, NBBY * mp->m_sb.sb_blocksize);
1149 }
1150
1151 /*
1152  * Compute the number of rtbitmap words needed to populate every block of a
1153  * bitmap that is large enough to track the given number of rt extents.
1154  */
1155 unsigned long long
1156 xfs_rtbitmap_wordcount(
1157         struct xfs_mount        *mp,
1158         xfs_rtbxlen_t           rtextents)
1159 {
1160         xfs_filblks_t           blocks;
1161
1162         blocks = xfs_rtbitmap_blockcount(mp, rtextents);
1163         return XFS_FSB_TO_B(mp, blocks) >> XFS_WORDLOG;
1164 }