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