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