libxfs/xfs_rtbitmap.c

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