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