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