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                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
 676                 /*
 677                  * Set/clear the active bits.
 678                  */
 679                 if (val)
 680                         *b |= mask;
 681                 else
 682                         *b &= ~mask;
 683                 b++;
 684         }
 685         /*
 686          * Log any remaining changed bytes.
 687          */
 688         if (b > first)
 689                 xfs_trans_log_buf(tp, bp, (uint)((char *)first - (char *)bufp),
 690                         (uint)((char *)b - (char *)bufp - 1));
 691         return 0;
 692 }
 693
 694 /*
 695  * Mark an extent specified by start and len freed.
 696  * Updates all the summary information as well as the bitmap.
 697  */
 698 int
 699 xfs_rtfree_range(
 700         xfs_mount_t     *mp,            /* file system mount point */
 701         xfs_trans_t     *tp,            /* transaction pointer */
 702         xfs_rtblock_t   start,          /* starting block to free */
 703         xfs_extlen_t    len,            /* length to free */
 704         xfs_buf_t       **rbpp,         /* in/out: summary block buffer */
 705         xfs_fsblock_t   *rsb)           /* in/out: summary block number */
 706 {
 707         xfs_rtblock_t   end;            /* end of the freed extent */
 708         int             error;          /* error value */
 709         xfs_rtblock_t   postblock;      /* first block freed > end */
 710         xfs_rtblock_t   preblock;       /* first block freed < start */
 711
 712         end = start + len - 1;
 713         /*
 714          * Modify the bitmap to mark this extent freed.
 715          */
 716         error = xfs_rtmodify_range(mp, tp, start, len, 1);
 717         if (error) {
 718                 return error;
 719         }
 720         /*
 721          * Assume we're freeing out of the middle of an allocated extent.
 722          * We need to find the beginning and end of the extent so we can
 723          * properly update the summary.
 724          */
 725         error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
 726         if (error) {
 727                 return error;
 728         }
 729         /*
 730          * Find the next allocated block (end of allocated extent).
 731          */
 732         error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
 733                 &postblock);
 734         if (error)
 735                 return error;
 736         /*
 737          * If there are blocks not being freed at the front of the
 738          * old extent, add summary data for them to be allocated.
 739          */
 740         if (preblock < start) {
 741                 error = xfs_rtmodify_summary(mp, tp,
 742                         XFS_RTBLOCKLOG(start - preblock),
 743                         XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
 744                 if (error) {
 745                         return error;
 746                 }
 747         }
 748         /*
 749          * If there are blocks not being freed at the end of the
 750          * old extent, add summary data for them to be allocated.
 751          */
 752         if (postblock > end) {
 753                 error = xfs_rtmodify_summary(mp, tp,
 754                         XFS_RTBLOCKLOG(postblock - end),
 755                         XFS_BITTOBLOCK(mp, end + 1), -1, rbpp, rsb);
 756                 if (error) {
 757                         return error;
 758                 }
 759         }
 760         /*
 761          * Increment the summary information corresponding to the entire
 762          * (new) free extent.
 763          */
 764         error = xfs_rtmodify_summary(mp, tp,
 765                 XFS_RTBLOCKLOG(postblock + 1 - preblock),
 766                 XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
 767         return error;
 768 }
 769
 770 /*
 771  * Check that the given range is either all allocated (val = 0) or
 772  * all free (val = 1).
 773  */
 774 int
 775 xfs_rtcheck_range(
 776         xfs_mount_t     *mp,            /* file system mount point */
 777         xfs_trans_t     *tp,            /* transaction pointer */
 778         xfs_rtblock_t   start,          /* starting block number of extent */
 779         xfs_extlen_t    len,            /* length of extent */
 780         int             val,            /* 1 for free, 0 for allocated */
 781         xfs_rtblock_t   *new,           /* out: first block not matching */
 782         int             *stat)          /* out: 1 for matches, 0 for not */
 783 {
 784         xfs_rtword_t    *b;             /* current word in buffer */
 785         int             bit;            /* bit number in the word */
 786         xfs_rtblock_t   block;          /* bitmap block number */
 787         xfs_buf_t       *bp;            /* buf for the block */
 788         xfs_rtword_t    *bufp;          /* starting word in buffer */
 789         int             error;          /* error value */
 790         xfs_rtblock_t   i;              /* current bit number rel. to start */
 791         xfs_rtblock_t   lastbit;        /* last useful bit in word */
 792         xfs_rtword_t    mask;           /* mask of relevant bits for value */
 793         xfs_rtword_t    wdiff;          /* difference from wanted value */
 794         int             word;           /* word number in the buffer */
 795
 796         /*
 797          * Compute starting bitmap block number
 798          */
 799         block = XFS_BITTOBLOCK(mp, start);
 800         /*
 801          * Read the bitmap block.
 802          */
 803         error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 804         if (error) {
 805                 return error;
 806         }
 807         bufp = bp->b_addr;
 808         /*
 809          * Compute the starting word's address, and starting bit.
 810          */
 811         word = XFS_BITTOWORD(mp, start);
 812         b = &bufp[word];
 813         bit = (int)(start & (XFS_NBWORD - 1));
 814         /*
 815          * 0 (allocated) => all zero's; 1 (free) => all one's.
 816          */
 817         val = -val;
 818         /*
 819          * If not starting on a word boundary, deal with the first
 820          * (partial) word.
 821          */
 822         if (bit) {
 823                 /*
 824                  * Compute first bit not examined.
 825                  */
 826                 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 827                 /*
 828                  * Mask of relevant bits.
 829                  */
 830                 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 831                 /*
 832                  * Compute difference between actual and desired value.
 833                  */
 834                 if ((wdiff = (*b ^ val) & mask)) {
 835                         /*
 836                          * Different, compute first wrong bit and return.
 837                          */
 838                         xfs_trans_brelse(tp, bp);
 839                         i = XFS_RTLOBIT(wdiff) - bit;
 840                         *new = start + i;
 841                         *stat = 0;
 842                         return 0;
 843                 }
 844                 i = lastbit - bit;
 845                 /*
 846                  * Go on to next block if that's where the next word is
 847                  * and we need the next word.
 848                  */
 849                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 850                         /*
 851                          * If done with this block, get the next one.
 852                          */
 853                         xfs_trans_brelse(tp, bp);
 854                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 855                         if (error) {
 856                                 return error;
 857                         }
 858                         b = bufp = bp->b_addr;
 859                         word = 0;
 860                 } else {
 861                         /*
 862                          * Go on to the next word in the buffer.
 863                          */
 864                         b++;
 865                 }
 866         } else {
 867                 /*
 868                  * Starting on a word boundary, no partial word.
 869                  */
 870                 i = 0;
 871         }
 872         /*
 873          * Loop over whole words in buffers.  When we use up one buffer
 874          * we move on to the next one.
 875          */
 876         while (len - i >= XFS_NBWORD) {
 877                 /*
 878                  * Compute difference between actual and desired value.
 879                  */
 880                 if ((wdiff = *b ^ val)) {
 881                         /*
 882                          * Different, compute first wrong bit and return.
 883                          */
 884                         xfs_trans_brelse(tp, bp);
 885                         i += XFS_RTLOBIT(wdiff);
 886                         *new = start + i;
 887                         *stat = 0;
 888                         return 0;
 889                 }
 890                 i += XFS_NBWORD;
 891                 /*
 892                  * Go on to next block if that's where the next word is
 893                  * and we need the next word.
 894                  */
 895                 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 896                         /*
 897                          * If done with this block, get the next one.
 898                          */
 899                         xfs_trans_brelse(tp, bp);
 900                         error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 901                         if (error) {
 902                                 return error;
 903                         }
 904                         b = bufp = bp->b_addr;
 905                         word = 0;
 906                 } else {
 907                         /*
 908                          * Go on to the next word in the buffer.
 909                          */
 910                         b++;
 911                 }
 912         }
 913         /*
 914          * If not ending on a word boundary, deal with the last
 915          * (partial) word.
 916          */
 917         if ((lastbit = len - i)) {
 918                 /*
 919                  * Mask of relevant bits.
 920                  */
 921                 mask = ((xfs_rtword_t)1 << lastbit) - 1;
 922                 /*
 923                  * Compute difference between actual and desired value.
 924                  */
 925                 if ((wdiff = (*b ^ val) & mask)) {
 926                         /*
 927                          * Different, compute first wrong bit and return.
 928                          */
 929                         xfs_trans_brelse(tp, bp);
 930                         i += XFS_RTLOBIT(wdiff);
 931                         *new = start + i;
 932                         *stat = 0;
 933                         return 0;
 934                 } else
 935                         i = len;
 936         }
 937         /*
 938          * Successful, return.
 939          */
 940         xfs_trans_brelse(tp, bp);
 941         *new = start + i;
 942         *stat = 1;
 943         return 0;
 944 }
 945
 946 #ifdef DEBUG
 947 /*
 948  * Check that the given extent (block range) is allocated already.
 949  */
 950 STATIC int                              /* error */
 951 xfs_rtcheck_alloc_range(
 952         xfs_mount_t     *mp,            /* file system mount point */
 953         xfs_trans_t     *tp,            /* transaction pointer */
 954         xfs_rtblock_t   bno,            /* starting block number of extent */
 955         xfs_extlen_t    len)            /* length of extent */
 956 {
 957         xfs_rtblock_t   new;            /* dummy for xfs_rtcheck_range */
 958         int             stat;
 959         int             error;
 960
 961         error = xfs_rtcheck_range(mp, tp, bno, len, 0, &new, &stat);
 962         if (error)
 963                 return error;
 964         ASSERT(stat);
 965         return 0;
 966 }
 967 #else
 968 #define xfs_rtcheck_alloc_range(m,t,b,l)        (0)
 969 #endif
 970 /*
 971  * Free an extent in the realtime subvolume.  Length is expressed in
 972  * realtime extents, as is the block number.
 973  */
 974 int                                     /* error */
 975 xfs_rtfree_extent(
 976         xfs_trans_t     *tp,            /* transaction pointer */
 977         xfs_rtblock_t   bno,            /* starting block number to free */
 978         xfs_extlen_t    len)            /* length of extent freed */
 979 {
 980         int             error;          /* error value */
 981         xfs_mount_t     *mp;            /* file system mount structure */
 982         xfs_fsblock_t   sb;             /* summary file block number */
 983         xfs_buf_t       *sumbp = NULL;  /* summary file block buffer */
 984
 985         mp = tp->t_mountp;
 986
 987         ASSERT(mp->m_rbmip->i_itemp != NULL);
 988         ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
 989
 990         error = xfs_rtcheck_alloc_range(mp, tp, bno, len);
 991         if (error)
 992                 return error;
 993
 994         /*
 995          * Free the range of realtime blocks.
 996          */
 997         error = xfs_rtfree_range(mp, tp, bno, len, &sumbp, &sb);
 998         if (error) {
 999                 return error;
1000         }
1001         /*
1002          * Mark more blocks free in the superblock.
1003          */
1004         xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
1005         /*
1006          * If we've now freed all the blocks, reset the file sequence
1007          * number to 0.
1008          */
1009         if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
1010             mp->m_sb.sb_rextents) {
1011                 if (!(mp->m_rbmip->i_d.di_flags & XFS_DIFLAG_NEWRTBM))
1012                         mp->m_rbmip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
1013                 *(uint64_t *)&VFS_I(mp->m_rbmip)->i_atime = 0;
1014                 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
1015         }
1016         return 0;
1017 }
1018
1019 /* Find all the free records within a given range. */
1020 int
1021 xfs_rtalloc_query_range(
1022         struct xfs_trans                *tp,
1023         struct xfs_rtalloc_rec          *low_rec,
1024         struct xfs_rtalloc_rec          *high_rec,
1025         xfs_rtalloc_query_range_fn      fn,
1026         void                            *priv)
1027 {
1028         struct xfs_rtalloc_rec          rec;
1029         struct xfs_mount                *mp = tp->t_mountp;
1030         xfs_rtblock_t                   rtstart;
1031         xfs_rtblock_t                   rtend;
1032         xfs_rtblock_t                   rem;
1033         int                             is_free;
1034         int                             error = 0;
1035
1036         if (low_rec->ar_startblock > high_rec->ar_startblock)
1037                 return -EINVAL;
1038         else if (low_rec->ar_startblock == high_rec->ar_startblock)
1039                 return 0;
1040
1041         /* Iterate the bitmap, looking for discrepancies. */
1042         rtstart = low_rec->ar_startblock;
1043         rem = high_rec->ar_startblock - rtstart;
1044         while (rem) {
1045                 /* Is the first block free? */
1046                 error = xfs_rtcheck_range(mp, tp, rtstart, 1, 1, &rtend,
1047                                 &is_free);
1048                 if (error)
1049                         break;
1050
1051                 /* How long does the extent go for? */
1052                 error = xfs_rtfind_forw(mp, tp, rtstart,
1053                                 high_rec->ar_startblock - 1, &rtend);
1054                 if (error)
1055                         break;
1056
1057                 if (is_free) {
1058                         rec.ar_startblock = rtstart;
1059                         rec.ar_blockcount = rtend - rtstart + 1;
1060
1061                         error = fn(tp, &rec, priv);
1062                         if (error)
1063                                 break;
1064                 }
1065
1066                 rem -= rtend - rtstart + 1;
1067                 rtstart = rtend + 1;
1068         }
1069
1070         return error;
1071 }
1072
1073 /* Find all the free records. */
1074 int
1075 xfs_rtalloc_query_all(
1076         struct xfs_trans                *tp,
1077         xfs_rtalloc_query_range_fn      fn,
1078         void                            *priv)
1079 {
1080         struct xfs_rtalloc_rec          keys[2];
1081
1082         keys[0].ar_startblock = 0;
1083         keys[1].ar_startblock = tp->t_mountp->m_sb.sb_rblocks;
1084         keys[0].ar_blockcount = keys[1].ar_blockcount = 0;
1085
1086         return xfs_rtalloc_query_range(tp, &keys[0], &keys[1], fn, priv);
1087 }
1088
1089 /*
1090  * Verify that an realtime block number pointer doesn't point off the
1091  * end of the realtime device.
1092  */
1093 bool
1094 xfs_verify_rtbno(
1095         struct xfs_mount        *mp,
1096         xfs_rtblock_t           rtbno)
1097 {
1098         return rtbno < mp->m_sb.sb_rblocks;
1099 }