libxfs/xfs_rtbitmap.c

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