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