fs/gfs2/rgrp.c

   1 /*
   2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
   3  * Copyright (C) 2004-2008 Red Hat, Inc.  All rights reserved.
   4  *
   5  * This copyrighted material is made available to anyone wishing to use,
   6  * modify, copy, or redistribute it subject to the terms and conditions
   7  * of the GNU General Public License version 2.
   8  */
   9
  10 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  11
  12 #include <linux/slab.h>
  13 #include <linux/spinlock.h>
  14 #include <linux/completion.h>
  15 #include <linux/buffer_head.h>
  16 #include <linux/fs.h>
  17 #include <linux/gfs2_ondisk.h>
  18 #include <linux/prefetch.h>
  19 #include <linux/blkdev.h>
  20 #include <linux/rbtree.h>
  21 #include <linux/random.h>
  22
  23 #include "gfs2.h"
  24 #include "incore.h"
  25 #include "glock.h"
  26 #include "glops.h"
  27 #include "lops.h"
  28 #include "meta_io.h"
  29 #include "quota.h"
  30 #include "rgrp.h"
  31 #include "super.h"
  32 #include "trans.h"
  33 #include "util.h"
  34 #include "log.h"
  35 #include "inode.h"
  36 #include "trace_gfs2.h"
  37
  38 #define BFITNOENT ((u32)~0)
  39 #define NO_BLOCK ((u64)~0)
  40
  41 #if BITS_PER_LONG == 32
  42 #define LBITMASK   (0x55555555UL)
  43 #define LBITSKIP55 (0x55555555UL)
  44 #define LBITSKIP00 (0x00000000UL)
  45 #else
  46 #define LBITMASK   (0x5555555555555555UL)
  47 #define LBITSKIP55 (0x5555555555555555UL)
  48 #define LBITSKIP00 (0x0000000000000000UL)
  49 #endif
  50
  51 /*
  52  * These routines are used by the resource group routines (rgrp.c)
  53  * to keep track of block allocation.  Each block is represented by two
  54  * bits.  So, each byte represents GFS2_NBBY (i.e. 4) blocks.
  55  *
  56  * 0 = Free
  57  * 1 = Used (not metadata)
  58  * 2 = Unlinked (still in use) inode
  59  * 3 = Used (metadata)
  60  */
  61
  62 struct gfs2_extent {
  63         struct gfs2_rbm rbm;
  64         u32 len;
  65 };
  66
  67 static const char valid_change[16] = {
  68                 /* current */
  69         /* n */ 0, 1, 1, 1,
  70         /* e */ 1, 0, 0, 0,
  71         /* w */ 0, 0, 0, 1,
  72                 1, 0, 0, 0
  73 };
  74
  75 static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 *minext,
  76                          const struct gfs2_inode *ip, bool nowrap);
  77
  78
  79 /**
  80  * gfs2_setbit - Set a bit in the bitmaps
  81  * @rbm: The position of the bit to set
  82  * @do_clone: Also set the clone bitmap, if it exists
  83  * @new_state: the new state of the block
  84  *
  85  */
  86
  87 static inline void gfs2_setbit(const struct gfs2_rbm *rbm, bool do_clone,
  88                                unsigned char new_state)
  89 {
  90         unsigned char *byte1, *byte2, *end, cur_state;
  91         struct gfs2_bitmap *bi = rbm_bi(rbm);
  92         unsigned int buflen = bi->bi_len;
  93         const unsigned int bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
  94
  95         byte1 = bi->bi_bh->b_data + bi->bi_offset + (rbm->offset / GFS2_NBBY);
  96         end = bi->bi_bh->b_data + bi->bi_offset + buflen;
  97
  98         BUG_ON(byte1 >= end);
  99
 100         cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
 101
 102         if (unlikely(!valid_change[new_state * 4 + cur_state])) {
 103                 pr_warn("buf_blk = 0x%x old_state=%d, new_state=%d\n",
 104                         rbm->offset, cur_state, new_state);
 105                 pr_warn("rgrp=0x%llx bi_start=0x%x\n",
 106                         (unsigned long long)rbm->rgd->rd_addr, bi->bi_start);
 107                 pr_warn("bi_offset=0x%x bi_len=0x%x\n",
 108                         bi->bi_offset, bi->bi_len);
 109                 dump_stack();
 110                 gfs2_consist_rgrpd(rbm->rgd);
 111                 return;
 112         }
 113         *byte1 ^= (cur_state ^ new_state) << bit;
 114
 115         if (do_clone && bi->bi_clone) {
 116                 byte2 = bi->bi_clone + bi->bi_offset + (rbm->offset / GFS2_NBBY);
 117                 cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
 118                 *byte2 ^= (cur_state ^ new_state) << bit;
 119         }
 120 }
 121
 122 /**
 123  * gfs2_testbit - test a bit in the bitmaps
 124  * @rbm: The bit to test
 125  *
 126  * Returns: The two bit block state of the requested bit
 127  */
 128
 129 static inline u8 gfs2_testbit(const struct gfs2_rbm *rbm)
 130 {
 131         struct gfs2_bitmap *bi = rbm_bi(rbm);
 132         const u8 *buffer = bi->bi_bh->b_data + bi->bi_offset;
 133         const u8 *byte;
 134         unsigned int bit;
 135
 136         byte = buffer + (rbm->offset / GFS2_NBBY);
 137         bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
 138
 139         return (*byte >> bit) & GFS2_BIT_MASK;
 140 }
 141
 142 /**
 143  * gfs2_bit_search
 144  * @ptr: Pointer to bitmap data
 145  * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
 146  * @state: The state we are searching for
 147  *
 148  * We xor the bitmap data with a patter which is the bitwise opposite
 149  * of what we are looking for, this gives rise to a pattern of ones
 150  * wherever there is a match. Since we have two bits per entry, we
 151  * take this pattern, shift it down by one place and then and it with
 152  * the original. All the even bit positions (0,2,4, etc) then represent
 153  * successful matches, so we mask with 0x55555..... to remove the unwanted
 154  * odd bit positions.
 155  *
 156  * This allows searching of a whole u64 at once (32 blocks) with a
 157  * single test (on 64 bit arches).
 158  */
 159
 160 static inline u64 gfs2_bit_search(const __le64 *ptr, u64 mask, u8 state)
 161 {
 162         u64 tmp;
 163         static const u64 search[] = {
 164                 [0] = 0xffffffffffffffffULL,
 165                 [1] = 0xaaaaaaaaaaaaaaaaULL,
 166                 [2] = 0x5555555555555555ULL,
 167                 [3] = 0x0000000000000000ULL,
 168         };
 169         tmp = le64_to_cpu(*ptr) ^ search[state];
 170         tmp &= (tmp >> 1);
 171         tmp &= mask;
 172         return tmp;
 173 }
 174
 175 /**
 176  * rs_cmp - multi-block reservation range compare
 177  * @blk: absolute file system block number of the new reservation
 178  * @len: number of blocks in the new reservation
 179  * @rs: existing reservation to compare against
 180  *
 181  * returns: 1 if the block range is beyond the reach of the reservation
 182  *         -1 if the block range is before the start of the reservation
 183  *          0 if the block range overlaps with the reservation
 184  */
 185 static inline int rs_cmp(u64 blk, u32 len, struct gfs2_blkreserv *rs)
 186 {
 187         u64 startblk = gfs2_rbm_to_block(&rs->rs_rbm);
 188
 189         if (blk >= startblk + rs->rs_free)
 190                 return 1;
 191         if (blk + len - 1 < startblk)
 192                 return -1;
 193         return 0;
 194 }
 195
 196 /**
 197  * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
 198  *       a block in a given allocation state.
 199  * @buf: the buffer that holds the bitmaps
 200  * @len: the length (in bytes) of the buffer
 201  * @goal: start search at this block's bit-pair (within @buffer)
 202  * @state: GFS2_BLKST_XXX the state of the block we're looking for.
 203  *
 204  * Scope of @goal and returned block number is only within this bitmap buffer,
 205  * not entire rgrp or filesystem.  @buffer will be offset from the actual
 206  * beginning of a bitmap block buffer, skipping any header structures, but
 207  * headers are always a multiple of 64 bits long so that the buffer is
 208  * always aligned to a 64 bit boundary.
 209  *
 210  * The size of the buffer is in bytes, but is it assumed that it is
 211  * always ok to read a complete multiple of 64 bits at the end
 212  * of the block in case the end is no aligned to a natural boundary.
 213  *
 214  * Return: the block number (bitmap buffer scope) that was found
 215  */
 216
 217 static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
 218                        u32 goal, u8 state)
 219 {
 220         u32 spoint = (goal << 1) & ((8*sizeof(u64)) - 1);
 221         const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
 222         const __le64 *end = (__le64 *)(buf + ALIGN(len, sizeof(u64)));
 223         u64 tmp;
 224         u64 mask = 0x5555555555555555ULL;
 225         u32 bit;
 226
 227         /* Mask off bits we don't care about at the start of the search */
 228         mask <<= spoint;
 229         tmp = gfs2_bit_search(ptr, mask, state);
 230         ptr++;
 231         while(tmp == 0 && ptr < end) {
 232                 tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
 233                 ptr++;
 234         }
 235         /* Mask off any bits which are more than len bytes from the start */
 236         if (ptr == end && (len & (sizeof(u64) - 1)))
 237                 tmp &= (((u64)~0) >> (64 - 8*(len & (sizeof(u64) - 1))));
 238         /* Didn't find anything, so return */
 239         if (tmp == 0)
 240                 return BFITNOENT;
 241         ptr--;
 242         bit = __ffs64(tmp);
 243         bit /= 2;       /* two bits per entry in the bitmap */
 244         return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
 245 }
 246
 247 /**
 248  * gfs2_rbm_from_block - Set the rbm based upon rgd and block number
 249  * @rbm: The rbm with rgd already set correctly
 250  * @block: The block number (filesystem relative)
 251  *
 252  * This sets the bi and offset members of an rbm based on a
 253  * resource group and a filesystem relative block number. The
 254  * resource group must be set in the rbm on entry, the bi and
 255  * offset members will be set by this function.
 256  *
 257  * Returns: 0 on success, or an error code
 258  */
 259
 260 static int gfs2_rbm_from_block(struct gfs2_rbm *rbm, u64 block)
 261 {
 262         u64 rblock = block - rbm->rgd->rd_data0;
 263
 264         if (WARN_ON_ONCE(rblock > UINT_MAX))
 265                 return -EINVAL;
 266         if (block >= rbm->rgd->rd_data0 + rbm->rgd->rd_data)
 267                 return -E2BIG;
 268
 269         rbm->bii = 0;
 270         rbm->offset = (u32)(rblock);
 271         /* Check if the block is within the first block */
 272         if (rbm->offset < rbm_bi(rbm)->bi_blocks)
 273                 return 0;
 274
 275         /* Adjust for the size diff between gfs2_meta_header and gfs2_rgrp */
 276         rbm->offset += (sizeof(struct gfs2_rgrp) -
 277                         sizeof(struct gfs2_meta_header)) * GFS2_NBBY;
 278         rbm->bii = rbm->offset / rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
 279         rbm->offset -= rbm->bii * rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
 280         return 0;
 281 }
 282
 283 /**
 284  * gfs2_rbm_incr - increment an rbm structure
 285  * @rbm: The rbm with rgd already set correctly
 286  *
 287  * This function takes an existing rbm structure and increments it to the next
 288  * viable block offset.
 289  *
 290  * Returns: If incrementing the offset would cause the rbm to go past the
 291  *          end of the rgrp, true is returned, otherwise false.
 292  *
 293  */
 294
 295 static bool gfs2_rbm_incr(struct gfs2_rbm *rbm)
 296 {
 297         if (rbm->offset + 1 < rbm_bi(rbm)->bi_blocks) { /* in the same bitmap */
 298                 rbm->offset++;
 299                 return false;
 300         }
 301         if (rbm->bii == rbm->rgd->rd_length - 1) /* at the last bitmap */
 302                 return true;
 303
 304         rbm->offset = 0;
 305         rbm->bii++;
 306         return false;
 307 }
 308
 309 /**
 310  * gfs2_unaligned_extlen - Look for free blocks which are not byte aligned
 311  * @rbm: Position to search (value/result)
 312  * @n_unaligned: Number of unaligned blocks to check
 313  * @len: Decremented for each block found (terminate on zero)
 314  *
 315  * Returns: true if a non-free block is encountered
 316  */
 317
 318 static bool gfs2_unaligned_extlen(struct gfs2_rbm *rbm, u32 n_unaligned, u32 *len)
 319 {
 320         u32 n;
 321         u8 res;
 322
 323         for (n = 0; n < n_unaligned; n++) {
 324                 res = gfs2_testbit(rbm);
 325                 if (res != GFS2_BLKST_FREE)
 326                         return true;
 327                 (*len)--;
 328                 if (*len == 0)
 329                         return true;
 330                 if (gfs2_rbm_incr(rbm))
 331                         return true;
 332         }
 333
 334         return false;
 335 }
 336
 337 /**
 338  * gfs2_free_extlen - Return extent length of free blocks
 339  * @rrbm: Starting position
 340  * @len: Max length to check
 341  *
 342  * Starting at the block specified by the rbm, see how many free blocks
 343  * there are, not reading more than len blocks ahead. This can be done
 344  * using memchr_inv when the blocks are byte aligned, but has to be done
 345  * on a block by block basis in case of unaligned blocks. Also this
 346  * function can cope with bitmap boundaries (although it must stop on
 347  * a resource group boundary)
 348  *
 349  * Returns: Number of free blocks in the extent
 350  */
 351
 352 static u32 gfs2_free_extlen(const struct gfs2_rbm *rrbm, u32 len)
 353 {
 354         struct gfs2_rbm rbm = *rrbm;
 355         u32 n_unaligned = rbm.offset & 3;
 356         u32 size = len;
 357         u32 bytes;
 358         u32 chunk_size;
 359         u8 *ptr, *start, *end;
 360         u64 block;
 361         struct gfs2_bitmap *bi;
 362
 363         if (n_unaligned &&
 364             gfs2_unaligned_extlen(&rbm, 4 - n_unaligned, &len))
 365                 goto out;
 366
 367         n_unaligned = len & 3;
 368         /* Start is now byte aligned */
 369         while (len > 3) {
 370                 bi = rbm_bi(&rbm);
 371                 start = bi->bi_bh->b_data;
 372                 if (bi->bi_clone)
 373                         start = bi->bi_clone;
 374                 end = start + bi->bi_bh->b_size;
 375                 start += bi->bi_offset;
 376                 BUG_ON(rbm.offset & 3);
 377                 start += (rbm.offset / GFS2_NBBY);
 378                 bytes = min_t(u32, len / GFS2_NBBY, (end - start));
 379                 ptr = memchr_inv(start, 0, bytes);
 380                 chunk_size = ((ptr == NULL) ? bytes : (ptr - start));
 381                 chunk_size *= GFS2_NBBY;
 382                 BUG_ON(len < chunk_size);
 383                 len -= chunk_size;
 384                 block = gfs2_rbm_to_block(&rbm);
 385                 if (gfs2_rbm_from_block(&rbm, block + chunk_size)) {
 386                         n_unaligned = 0;
 387                         break;
 388                 }
 389                 if (ptr) {
 390                         n_unaligned = 3;
 391                         break;
 392                 }
 393                 n_unaligned = len & 3;
 394         }
 395
 396         /* Deal with any bits left over at the end */
 397         if (n_unaligned)
 398                 gfs2_unaligned_extlen(&rbm, n_unaligned, &len);
 399 out:
 400         return size - len;
 401 }
 402
 403 /**
 404  * gfs2_bitcount - count the number of bits in a certain state
 405  * @rgd: the resource group descriptor
 406  * @buffer: the buffer that holds the bitmaps
 407  * @buflen: the length (in bytes) of the buffer
 408  * @state: the state of the block we're looking for
 409  *
 410  * Returns: The number of bits
 411  */
 412
 413 static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
 414                          unsigned int buflen, u8 state)
 415 {
 416         const u8 *byte = buffer;
 417         const u8 *end = buffer + buflen;
 418         const u8 state1 = state << 2;
 419         const u8 state2 = state << 4;
 420         const u8 state3 = state << 6;
 421         u32 count = 0;
 422
 423         for (; byte < end; byte++) {
 424                 if (((*byte) & 0x03) == state)
 425                         count++;
 426                 if (((*byte) & 0x0C) == state1)
 427                         count++;
 428                 if (((*byte) & 0x30) == state2)
 429                         count++;
 430                 if (((*byte) & 0xC0) == state3)
 431                         count++;
 432         }
 433
 434         return count;
 435 }
 436
 437 /**
 438  * gfs2_rgrp_verify - Verify that a resource group is consistent
 439  * @rgd: the rgrp
 440  *
 441  */
 442
 443 void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
 444 {
 445         struct gfs2_sbd *sdp = rgd->rd_sbd;
 446         struct gfs2_bitmap *bi = NULL;
 447         u32 length = rgd->rd_length;
 448         u32 count[4], tmp;
 449         int buf, x;
 450
 451         memset(count, 0, 4 * sizeof(u32));
 452
 453         /* Count # blocks in each of 4 possible allocation states */
 454         for (buf = 0; buf < length; buf++) {
 455                 bi = rgd->rd_bits + buf;
 456                 for (x = 0; x < 4; x++)
 457                         count[x] += gfs2_bitcount(rgd,
 458                                                   bi->bi_bh->b_data +
 459                                                   bi->bi_offset,
 460                                                   bi->bi_len, x);
 461         }
 462
 463         if (count[0] != rgd->rd_free) {
 464                 if (gfs2_consist_rgrpd(rgd))
 465                         fs_err(sdp, "free data mismatch:  %u != %u\n",
 466                                count[0], rgd->rd_free);
 467                 return;
 468         }
 469
 470         tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
 471         if (count[1] != tmp) {
 472                 if (gfs2_consist_rgrpd(rgd))
 473                         fs_err(sdp, "used data mismatch:  %u != %u\n",
 474                                count[1], tmp);
 475                 return;
 476         }
 477
 478         if (count[2] + count[3] != rgd->rd_dinodes) {
 479                 if (gfs2_consist_rgrpd(rgd))
 480                         fs_err(sdp, "used metadata mismatch:  %u != %u\n",
 481                                count[2] + count[3], rgd->rd_dinodes);
 482                 return;
 483         }
 484 }
 485
 486 /**
 487  * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 488  * @sdp: The GFS2 superblock
 489  * @blk: The data block number
 490  * @exact: True if this needs to be an exact match
 491  *
 492  * Returns: The resource group, or NULL if not found
 493  */
 494
 495 struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
 496 {
 497         struct rb_node *n, *next;
 498         struct gfs2_rgrpd *cur;
 499
 500         spin_lock(&sdp->sd_rindex_spin);
 501         n = sdp->sd_rindex_tree.rb_node;
 502         while (n) {
 503                 cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
 504                 next = NULL;
 505                 if (blk < cur->rd_addr)
 506                         next = n->rb_left;
 507                 else if (blk >= cur->rd_data0 + cur->rd_data)
 508                         next = n->rb_right;
 509                 if (next == NULL) {
 510                         spin_unlock(&sdp->sd_rindex_spin);
 511                         if (exact) {
 512                                 if (blk < cur->rd_addr)
 513                                         return NULL;
 514                                 if (blk >= cur->rd_data0 + cur->rd_data)
 515                                         return NULL;
 516                         }
 517                         return cur;
 518                 }
 519                 n = next;
 520         }
 521         spin_unlock(&sdp->sd_rindex_spin);
 522
 523         return NULL;
 524 }
 525
 526 /**
 527  * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
 528  * @sdp: The GFS2 superblock
 529  *
 530  * Returns: The first rgrp in the filesystem
 531  */
 532
 533 struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
 534 {
 535         const struct rb_node *n;
 536         struct gfs2_rgrpd *rgd;
 537
 538         spin_lock(&sdp->sd_rindex_spin);
 539         n = rb_first(&sdp->sd_rindex_tree);
 540         rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
 541         spin_unlock(&sdp->sd_rindex_spin);
 542
 543         return rgd;
 544 }
 545
 546 /**
 547  * gfs2_rgrpd_get_next - get the next RG
 548  * @rgd: the resource group descriptor
 549  *
 550  * Returns: The next rgrp
 551  */
 552
 553 struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
 554 {
 555         struct gfs2_sbd *sdp = rgd->rd_sbd;
 556         const struct rb_node *n;
 557
 558         spin_lock(&sdp->sd_rindex_spin);
 559         n = rb_next(&rgd->rd_node);
 560         if (n == NULL)
 561                 n = rb_first(&sdp->sd_rindex_tree);
 562
 563         if (unlikely(&rgd->rd_node == n)) {
 564                 spin_unlock(&sdp->sd_rindex_spin);
 565                 return NULL;
 566         }
 567         rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
 568         spin_unlock(&sdp->sd_rindex_spin);
 569         return rgd;
 570 }
 571
 572 void check_and_update_goal(struct gfs2_inode *ip)
 573 {
 574         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 575         if (!ip->i_goal || gfs2_blk2rgrpd(sdp, ip->i_goal, 1) == NULL)
 576                 ip->i_goal = ip->i_no_addr;
 577 }
 578
 579 void gfs2_free_clones(struct gfs2_rgrpd *rgd)
 580 {
 581         int x;
 582
 583         for (x = 0; x < rgd->rd_length; x++) {
 584                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
 585                 kfree(bi->bi_clone);
 586                 bi->bi_clone = NULL;
 587         }
 588 }
 589
 590 /**
 591  * gfs2_rsqa_alloc - make sure we have a reservation assigned to the inode
 592  *                 plus a quota allocations data structure, if necessary
 593  * @ip: the inode for this reservation
 594  */
 595 int gfs2_rsqa_alloc(struct gfs2_inode *ip)
 596 {
 597         return gfs2_qa_alloc(ip);
 598 }
 599
 600 static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
 601 {
 602         gfs2_print_dbg(seq, "  B: n:%llu s:%llu b:%u f:%u\n",
 603                        (unsigned long long)rs->rs_inum,
 604                        (unsigned long long)gfs2_rbm_to_block(&rs->rs_rbm),
 605                        rs->rs_rbm.offset, rs->rs_free);
 606 }
 607
 608 /**
 609  * __rs_deltree - remove a multi-block reservation from the rgd tree
 610  * @rs: The reservation to remove
 611  *
 612  */
 613 static void __rs_deltree(struct gfs2_blkreserv *rs)
 614 {
 615         struct gfs2_rgrpd *rgd;
 616
 617         if (!gfs2_rs_active(rs))
 618                 return;
 619
 620         rgd = rs->rs_rbm.rgd;
 621         trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
 622         rb_erase(&rs->rs_node, &rgd->rd_rstree);
 623         RB_CLEAR_NODE(&rs->rs_node);
 624
 625         if (rs->rs_free) {
 626                 u64 last_block = gfs2_rbm_to_block(&rs->rs_rbm) +
 627                                  rs->rs_free - 1;
 628                 struct gfs2_rbm last_rbm = { .rgd = rs->rs_rbm.rgd, };
 629                 struct gfs2_bitmap *start, *last;
 630
 631                 /* return reserved blocks to the rgrp */
 632                 BUG_ON(rs->rs_rbm.rgd->rd_reserved < rs->rs_free);
 633                 rs->rs_rbm.rgd->rd_reserved -= rs->rs_free;
 634                 /* The rgrp extent failure point is likely not to increase;
 635                    it will only do so if the freed blocks are somehow
 636                    contiguous with a span of free blocks that follows. Still,
 637                    it will force the number to be recalculated later. */
 638                 rgd->rd_extfail_pt += rs->rs_free;
 639                 rs->rs_free = 0;
 640                 if (gfs2_rbm_from_block(&last_rbm, last_block))
 641                         return;
 642                 start = rbm_bi(&rs->rs_rbm);
 643                 last = rbm_bi(&last_rbm);
 644                 do
 645                         clear_bit(GBF_FULL, &start->bi_flags);
 646                 while (start++ != last);
 647         }
 648 }
 649
 650 /**
 651  * gfs2_rs_deltree - remove a multi-block reservation from the rgd tree
 652  * @rs: The reservation to remove
 653  *
 654  */
 655 void gfs2_rs_deltree(struct gfs2_blkreserv *rs)
 656 {
 657         struct gfs2_rgrpd *rgd;
 658
 659         rgd = rs->rs_rbm.rgd;
 660         if (rgd) {
 661                 spin_lock(&rgd->rd_rsspin);
 662                 __rs_deltree(rs);
 663                 BUG_ON(rs->rs_free);
 664                 spin_unlock(&rgd->rd_rsspin);
 665         }
 666 }
 667
 668 /**
 669  * gfs2_rsqa_delete - delete a multi-block reservation and quota allocation
 670  * @ip: The inode for this reservation
 671  * @wcount: The inode's write count, or NULL
 672  *
 673  */
 674 void gfs2_rsqa_delete(struct gfs2_inode *ip, atomic_t *wcount)
 675 {
 676         down_write(&ip->i_rw_mutex);
 677         if ((wcount == NULL) || (atomic_read(wcount) <= 1))
 678                 gfs2_rs_deltree(&ip->i_res);
 679         up_write(&ip->i_rw_mutex);
 680         gfs2_qa_delete(ip, wcount);
 681 }
 682
 683 /**
 684  * return_all_reservations - return all reserved blocks back to the rgrp.
 685  * @rgd: the rgrp that needs its space back
 686  *
 687  * We previously reserved a bunch of blocks for allocation. Now we need to
 688  * give them back. This leave the reservation structures in tact, but removes
 689  * all of their corresponding "no-fly zones".
 690  */
 691 static void return_all_reservations(struct gfs2_rgrpd *rgd)
 692 {
 693         struct rb_node *n;
 694         struct gfs2_blkreserv *rs;
 695
 696         spin_lock(&rgd->rd_rsspin);
 697         while ((n = rb_first(&rgd->rd_rstree))) {
 698                 rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
 699                 __rs_deltree(rs);
 700         }
 701         spin_unlock(&rgd->rd_rsspin);
 702 }
 703
 704 void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
 705 {
 706         struct rb_node *n;
 707         struct gfs2_rgrpd *rgd;
 708         struct gfs2_glock *gl;
 709
 710         while ((n = rb_first(&sdp->sd_rindex_tree))) {
 711                 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
 712                 gl = rgd->rd_gl;
 713
 714                 rb_erase(n, &sdp->sd_rindex_tree);
 715
 716                 if (gl) {
 717                         glock_clear_object(gl, rgd);
 718                         gfs2_rgrp_brelse(rgd);
 719                         gfs2_glock_put(gl);
 720                 }
 721
 722                 gfs2_free_clones(rgd);
 723                 return_all_reservations(rgd);
 724                 kfree(rgd->rd_bits);
 725                 rgd->rd_bits = NULL;
 726                 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
 727         }
 728 }
 729
 730 static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
 731 {
 732         pr_info("ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
 733         pr_info("ri_length = %u\n", rgd->rd_length);
 734         pr_info("ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
 735         pr_info("ri_data = %u\n", rgd->rd_data);
 736         pr_info("ri_bitbytes = %u\n", rgd->rd_bitbytes);
 737 }
 738
 739 /**
 740  * gfs2_compute_bitstructs - Compute the bitmap sizes
 741  * @rgd: The resource group descriptor
 742  *
 743  * Calculates bitmap descriptors, one for each block that contains bitmap data
 744  *
 745  * Returns: errno
 746  */
 747
 748 static int compute_bitstructs(struct gfs2_rgrpd *rgd)
 749 {
 750         struct gfs2_sbd *sdp = rgd->rd_sbd;
 751         struct gfs2_bitmap *bi;
 752         u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
 753         u32 bytes_left, bytes;
 754         int x;
 755
 756         if (!length)
 757                 return -EINVAL;
 758
 759         rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
 760         if (!rgd->rd_bits)
 761                 return -ENOMEM;
 762
 763         bytes_left = rgd->rd_bitbytes;
 764
 765         for (x = 0; x < length; x++) {
 766                 bi = rgd->rd_bits + x;
 767
 768                 bi->bi_flags = 0;
 769                 /* small rgrp; bitmap stored completely in header block */
 770                 if (length == 1) {
 771                         bytes = bytes_left;
 772                         bi->bi_offset = sizeof(struct gfs2_rgrp);
 773                         bi->bi_start = 0;
 774                         bi->bi_len = bytes;
 775                         bi->bi_blocks = bytes * GFS2_NBBY;
 776                 /* header block */
 777                 } else if (x == 0) {
 778                         bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
 779                         bi->bi_offset = sizeof(struct gfs2_rgrp);
 780                         bi->bi_start = 0;
 781                         bi->bi_len = bytes;
 782                         bi->bi_blocks = bytes * GFS2_NBBY;
 783                 /* last block */
 784                 } else if (x + 1 == length) {
 785                         bytes = bytes_left;
 786                         bi->bi_offset = sizeof(struct gfs2_meta_header);
 787                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
 788                         bi->bi_len = bytes;
 789                         bi->bi_blocks = bytes * GFS2_NBBY;
 790                 /* other blocks */
 791                 } else {
 792                         bytes = sdp->sd_sb.sb_bsize -
 793                                 sizeof(struct gfs2_meta_header);
 794                         bi->bi_offset = sizeof(struct gfs2_meta_header);
 795                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
 796                         bi->bi_len = bytes;
 797                         bi->bi_blocks = bytes * GFS2_NBBY;
 798                 }
 799
 800                 bytes_left -= bytes;
 801         }
 802
 803         if (bytes_left) {
 804                 gfs2_consist_rgrpd(rgd);
 805                 return -EIO;
 806         }
 807         bi = rgd->rd_bits + (length - 1);
 808         if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
 809                 if (gfs2_consist_rgrpd(rgd)) {
 810                         gfs2_rindex_print(rgd);
 811                         fs_err(sdp, "start=%u len=%u offset=%u\n",
 812                                bi->bi_start, bi->bi_len, bi->bi_offset);
 813                 }
 814                 return -EIO;
 815         }
 816
 817         return 0;
 818 }
 819
 820 /**
 821  * gfs2_ri_total - Total up the file system space, according to the rindex.
 822  * @sdp: the filesystem
 823  *
 824  */
 825 u64 gfs2_ri_total(struct gfs2_sbd *sdp)
 826 {
 827         u64 total_data = 0;
 828         struct inode *inode = sdp->sd_rindex;
 829         struct gfs2_inode *ip = GFS2_I(inode);
 830         char buf[sizeof(struct gfs2_rindex)];
 831         int error, rgrps;
 832
 833         for (rgrps = 0;; rgrps++) {
 834                 loff_t pos = rgrps * sizeof(struct gfs2_rindex);
 835
 836                 if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
 837                         break;
 838                 error = gfs2_internal_read(ip, buf, &pos,
 839                                            sizeof(struct gfs2_rindex));
 840                 if (error != sizeof(struct gfs2_rindex))
 841                         break;
 842                 total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
 843         }
 844         return total_data;
 845 }
 846
 847 static int rgd_insert(struct gfs2_rgrpd *rgd)
 848 {
 849         struct gfs2_sbd *sdp = rgd->rd_sbd;
 850         struct rb_node **newn = &sdp->sd_rindex_tree.rb_node, *parent = NULL;
 851
 852         /* Figure out where to put new node */
 853         while (*newn) {
 854                 struct gfs2_rgrpd *cur = rb_entry(*newn, struct gfs2_rgrpd,
 855                                                   rd_node);
 856
 857                 parent = *newn;
 858                 if (rgd->rd_addr < cur->rd_addr)
 859                         newn = &((*newn)->rb_left);
 860                 else if (rgd->rd_addr > cur->rd_addr)
 861                         newn = &((*newn)->rb_right);
 862                 else
 863                         return -EEXIST;
 864         }
 865
 866         rb_link_node(&rgd->rd_node, parent, newn);
 867         rb_insert_color(&rgd->rd_node, &sdp->sd_rindex_tree);
 868         sdp->sd_rgrps++;
 869         return 0;
 870 }
 871
 872 /**
 873  * read_rindex_entry - Pull in a new resource index entry from the disk
 874  * @ip: Pointer to the rindex inode
 875  *
 876  * Returns: 0 on success, > 0 on EOF, error code otherwise
 877  */
 878
 879 static int read_rindex_entry(struct gfs2_inode *ip)
 880 {
 881         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 882         const unsigned bsize = sdp->sd_sb.sb_bsize;
 883         loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
 884         struct gfs2_rindex buf;
 885         int error;
 886         struct gfs2_rgrpd *rgd;
 887
 888         if (pos >= i_size_read(&ip->i_inode))
 889                 return 1;
 890
 891         error = gfs2_internal_read(ip, (char *)&buf, &pos,
 892                                    sizeof(struct gfs2_rindex));
 893
 894         if (error != sizeof(struct gfs2_rindex))
 895                 return (error == 0) ? 1 : error;
 896
 897         rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
 898         error = -ENOMEM;
 899         if (!rgd)
 900                 return error;
 901
 902         rgd->rd_sbd = sdp;
 903         rgd->rd_addr = be64_to_cpu(buf.ri_addr);
 904         rgd->rd_length = be32_to_cpu(buf.ri_length);
 905         rgd->rd_data0 = be64_to_cpu(buf.ri_data0);
 906         rgd->rd_data = be32_to_cpu(buf.ri_data);
 907         rgd->rd_bitbytes = be32_to_cpu(buf.ri_bitbytes);
 908         spin_lock_init(&rgd->rd_rsspin);
 909
 910         error = compute_bitstructs(rgd);
 911         if (error)
 912                 goto fail;
 913
 914         error = gfs2_glock_get(sdp, rgd->rd_addr,
 915                                &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
 916         if (error)
 917                 goto fail;
 918
 919         rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lksb.sb_lvbptr;
 920         rgd->rd_flags &= ~(GFS2_RDF_UPTODATE | GFS2_RDF_PREFERRED);
 921         if (rgd->rd_data > sdp->sd_max_rg_data)
 922                 sdp->sd_max_rg_data = rgd->rd_data;
 923         spin_lock(&sdp->sd_rindex_spin);
 924         error = rgd_insert(rgd);
 925         spin_unlock(&sdp->sd_rindex_spin);
 926         if (!error) {
 927                 glock_set_object(rgd->rd_gl, rgd);
 928                 rgd->rd_gl->gl_vm.start = (rgd->rd_addr * bsize) & PAGE_MASK;
 929                 rgd->rd_gl->gl_vm.end = PAGE_ALIGN((rgd->rd_addr +
 930                                                     rgd->rd_length) * bsize) - 1;
 931                 return 0;
 932         }
 933
 934         error = 0; /* someone else read in the rgrp; free it and ignore it */
 935         gfs2_glock_put(rgd->rd_gl);
 936
 937 fail:
 938         kfree(rgd->rd_bits);
 939         rgd->rd_bits = NULL;
 940         kmem_cache_free(gfs2_rgrpd_cachep, rgd);
 941         return error;
 942 }
 943
 944 /**
 945  * set_rgrp_preferences - Run all the rgrps, selecting some we prefer to use
 946  * @sdp: the GFS2 superblock
 947  *
 948  * The purpose of this function is to select a subset of the resource groups
 949  * and mark them as PREFERRED. We do it in such a way that each node prefers
 950  * to use a unique set of rgrps to minimize glock contention.
 951  */
 952 static void set_rgrp_preferences(struct gfs2_sbd *sdp)
 953 {
 954         struct gfs2_rgrpd *rgd, *first;
 955         int i;
 956
 957         /* Skip an initial number of rgrps, based on this node's journal ID.
 958            That should start each node out on its own set. */
 959         rgd = gfs2_rgrpd_get_first(sdp);
 960         for (i = 0; i < sdp->sd_lockstruct.ls_jid; i++)
 961                 rgd = gfs2_rgrpd_get_next(rgd);
 962         first = rgd;
 963
 964         do {
 965                 rgd->rd_flags |= GFS2_RDF_PREFERRED;
 966                 for (i = 0; i < sdp->sd_journals; i++) {
 967                         rgd = gfs2_rgrpd_get_next(rgd);
 968                         if (!rgd || rgd == first)
 969                                 break;
 970                 }
 971         } while (rgd && rgd != first);
 972 }
 973
 974 /**
 975  * gfs2_ri_update - Pull in a new resource index from the disk
 976  * @ip: pointer to the rindex inode
 977  *
 978  * Returns: 0 on successful update, error code otherwise
 979  */
 980
 981 static int gfs2_ri_update(struct gfs2_inode *ip)
 982 {
 983         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 984         int error;
 985
 986         do {
 987                 error = read_rindex_entry(ip);
 988         } while (error == 0);
 989
 990         if (error < 0)
 991                 return error;
 992
 993         if (RB_EMPTY_ROOT(&sdp->sd_rindex_tree)) {
 994                 fs_err(sdp, "no resource groups found in the file system.\n");
 995                 return -ENOENT;
 996         }
 997         set_rgrp_preferences(sdp);
 998
 999         sdp->sd_rindex_uptodate = 1;
1000         return 0;
1001 }
1002
1003 /**
1004  * gfs2_rindex_update - Update the rindex if required
1005  * @sdp: The GFS2 superblock
1006  *
1007  * We grab a lock on the rindex inode to make sure that it doesn't
1008  * change whilst we are performing an operation. We keep this lock
1009  * for quite long periods of time compared to other locks. This
1010  * doesn't matter, since it is shared and it is very, very rarely
1011  * accessed in the exclusive mode (i.e. only when expanding the filesystem).
1012  *
1013  * This makes sure that we're using the latest copy of the resource index
1014  * special file, which might have been updated if someone expanded the
1015  * filesystem (via gfs2_grow utility), which adds new resource groups.
1016  *
1017  * Returns: 0 on succeess, error code otherwise
1018  */
1019
1020 int gfs2_rindex_update(struct gfs2_sbd *sdp)
1021 {
1022         struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
1023         struct gfs2_glock *gl = ip->i_gl;
1024         struct gfs2_holder ri_gh;
1025         int error = 0;
1026         int unlock_required = 0;
1027
1028         /* Read new copy from disk if we don't have the latest */
1029         if (!sdp->sd_rindex_uptodate) {
1030                 if (!gfs2_glock_is_locked_by_me(gl)) {
1031                         error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, &ri_gh);
1032                         if (error)
1033                                 return error;
1034                         unlock_required = 1;
1035                 }
1036                 if (!sdp->sd_rindex_uptodate)
1037                         error = gfs2_ri_update(ip);
1038                 if (unlock_required)
1039                         gfs2_glock_dq_uninit(&ri_gh);
1040         }
1041
1042         return error;
1043 }
1044
1045 static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
1046 {
1047         const struct gfs2_rgrp *str = buf;
1048         u32 rg_flags;
1049
1050         rg_flags = be32_to_cpu(str->rg_flags);
1051         rg_flags &= ~GFS2_RDF_MASK;
1052         rgd->rd_flags &= GFS2_RDF_MASK;
1053         rgd->rd_flags |= rg_flags;
1054         rgd->rd_free = be32_to_cpu(str->rg_free);
1055         rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
1056         rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
1057 }
1058
1059 static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
1060 {
1061         struct gfs2_rgrp *str = buf;
1062
1063         str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
1064         str->rg_free = cpu_to_be32(rgd->rd_free);
1065         str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
1066         str->__pad = cpu_to_be32(0);
1067         str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
1068         memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
1069 }
1070
1071 static int gfs2_rgrp_lvb_valid(struct gfs2_rgrpd *rgd)
1072 {
1073         struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
1074         struct gfs2_rgrp *str = (struct gfs2_rgrp *)rgd->rd_bits[0].bi_bh->b_data;
1075
1076         if (rgl->rl_flags != str->rg_flags || rgl->rl_free != str->rg_free ||
1077             rgl->rl_dinodes != str->rg_dinodes ||
1078             rgl->rl_igeneration != str->rg_igeneration)
1079                 return 0;
1080         return 1;
1081 }
1082
1083 static void gfs2_rgrp_ondisk2lvb(struct gfs2_rgrp_lvb *rgl, const void *buf)
1084 {
1085         const struct gfs2_rgrp *str = buf;
1086
1087         rgl->rl_magic = cpu_to_be32(GFS2_MAGIC);
1088         rgl->rl_flags = str->rg_flags;
1089         rgl->rl_free = str->rg_free;
1090         rgl->rl_dinodes = str->rg_dinodes;
1091         rgl->rl_igeneration = str->rg_igeneration;
1092         rgl->__pad = 0UL;
1093 }
1094
1095 static void update_rgrp_lvb_unlinked(struct gfs2_rgrpd *rgd, u32 change)
1096 {
1097         struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
1098         u32 unlinked = be32_to_cpu(rgl->rl_unlinked) + change;
1099         rgl->rl_unlinked = cpu_to_be32(unlinked);
1100 }
1101
1102 static u32 count_unlinked(struct gfs2_rgrpd *rgd)
1103 {
1104         struct gfs2_bitmap *bi;
1105         const u32 length = rgd->rd_length;
1106         const u8 *buffer = NULL;
1107         u32 i, goal, count = 0;
1108
1109         for (i = 0, bi = rgd->rd_bits; i < length; i++, bi++) {
1110                 goal = 0;
1111                 buffer = bi->bi_bh->b_data + bi->bi_offset;
1112                 WARN_ON(!buffer_uptodate(bi->bi_bh));
1113                 while (goal < bi->bi_len * GFS2_NBBY) {
1114                         goal = gfs2_bitfit(buffer, bi->bi_len, goal,
1115                                            GFS2_BLKST_UNLINKED);
1116                         if (goal == BFITNOENT)
1117                                 break;
1118                         count++;
1119                         goal++;
1120                 }
1121         }
1122
1123         return count;
1124 }
1125
1126
1127 /**
1128  * gfs2_rgrp_bh_get - Read in a RG's header and bitmaps
1129  * @rgd: the struct gfs2_rgrpd describing the RG to read in
1130  *
1131  * Read in all of a Resource Group's header and bitmap blocks.
1132  * Caller must eventually call gfs2_rgrp_brelse() to free the bitmaps.
1133  *
1134  * Returns: errno
1135  */
1136
1137 static int gfs2_rgrp_bh_get(struct gfs2_rgrpd *rgd)
1138 {
1139         struct gfs2_sbd *sdp = rgd->rd_sbd;
1140         struct gfs2_glock *gl = rgd->rd_gl;
1141         unsigned int length = rgd->rd_length;
1142         struct gfs2_bitmap *bi;
1143         unsigned int x, y;
1144         int error;
1145
1146         if (rgd->rd_bits[0].bi_bh != NULL)
1147                 return 0;
1148
1149         for (x = 0; x < length; x++) {
1150                 bi = rgd->rd_bits + x;
1151                 error = gfs2_meta_read(gl, rgd->rd_addr + x, 0, 0, &bi->bi_bh);
1152                 if (error)
1153                         goto fail;
1154         }
1155
1156         for (y = length; y--;) {
1157                 bi = rgd->rd_bits + y;
1158                 error = gfs2_meta_wait(sdp, bi->bi_bh);
1159                 if (error)
1160                         goto fail;
1161                 if (gfs2_metatype_check(sdp, bi->bi_bh, y ? GFS2_METATYPE_RB :
1162                                               GFS2_METATYPE_RG)) {
1163                         error = -EIO;
1164                         goto fail;
1165                 }
1166         }
1167
1168         if (!(rgd->rd_flags & GFS2_RDF_UPTODATE)) {
1169                 for (x = 0; x < length; x++)
1170                         clear_bit(GBF_FULL, &rgd->rd_bits[x].bi_flags);
1171                 gfs2_rgrp_in(rgd, (rgd->rd_bits[0].bi_bh)->b_data);
1172                 rgd->rd_flags |= (GFS2_RDF_UPTODATE | GFS2_RDF_CHECK);
1173                 rgd->rd_free_clone = rgd->rd_free;
1174                 /* max out the rgrp allocation failure point */
1175                 rgd->rd_extfail_pt = rgd->rd_free;
1176         }
1177         if (cpu_to_be32(GFS2_MAGIC) != rgd->rd_rgl->rl_magic) {
1178                 rgd->rd_rgl->rl_unlinked = cpu_to_be32(count_unlinked(rgd));
1179                 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl,
1180                                      rgd->rd_bits[0].bi_bh->b_data);
1181         }
1182         else if (sdp->sd_args.ar_rgrplvb) {
1183                 if (!gfs2_rgrp_lvb_valid(rgd)){
1184                         gfs2_consist_rgrpd(rgd);
1185                         error = -EIO;
1186                         goto fail;
1187                 }
1188                 if (rgd->rd_rgl->rl_unlinked == 0)
1189                         rgd->rd_flags &= ~GFS2_RDF_CHECK;
1190         }
1191         return 0;
1192
1193 fail:
1194         while (x--) {
1195                 bi = rgd->rd_bits + x;
1196                 brelse(bi->bi_bh);
1197                 bi->bi_bh = NULL;
1198                 gfs2_assert_warn(sdp, !bi->bi_clone);
1199         }
1200
1201         return error;
1202 }
1203
1204 static int update_rgrp_lvb(struct gfs2_rgrpd *rgd)
1205 {
1206         u32 rl_flags;
1207
1208         if (rgd->rd_flags & GFS2_RDF_UPTODATE)
1209                 return 0;
1210
1211         if (cpu_to_be32(GFS2_MAGIC) != rgd->rd_rgl->rl_magic)
1212                 return gfs2_rgrp_bh_get(rgd);
1213
1214         rl_flags = be32_to_cpu(rgd->rd_rgl->rl_flags);
1215         rl_flags &= ~GFS2_RDF_MASK;
1216         rgd->rd_flags &= GFS2_RDF_MASK;
1217         rgd->rd_flags |= (rl_flags | GFS2_RDF_CHECK);
1218         if (rgd->rd_rgl->rl_unlinked == 0)
1219                 rgd->rd_flags &= ~GFS2_RDF_CHECK;
1220         rgd->rd_free = be32_to_cpu(rgd->rd_rgl->rl_free);
1221         rgd->rd_free_clone = rgd->rd_free;
1222         rgd->rd_dinodes = be32_to_cpu(rgd->rd_rgl->rl_dinodes);
1223         rgd->rd_igeneration = be64_to_cpu(rgd->rd_rgl->rl_igeneration);
1224         return 0;
1225 }
1226
1227 int gfs2_rgrp_go_lock(struct gfs2_holder *gh)
1228 {
1229         struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
1230         struct gfs2_sbd *sdp = rgd->rd_sbd;
1231
1232         if (gh->gh_flags & GL_SKIP && sdp->sd_args.ar_rgrplvb)
1233                 return 0;
1234         return gfs2_rgrp_bh_get(rgd);
1235 }
1236
1237 /**
1238  * gfs2_rgrp_brelse - Release RG bitmaps read in with gfs2_rgrp_bh_get()
1239  * @rgd: The resource group
1240  *
1241  */
1242
1243 void gfs2_rgrp_brelse(struct gfs2_rgrpd *rgd)
1244 {
1245         int x, length = rgd->rd_length;
1246
1247         for (x = 0; x < length; x++) {
1248                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
1249                 if (bi->bi_bh) {
1250                         brelse(bi->bi_bh);
1251                         bi->bi_bh = NULL;
1252                 }
1253         }
1254
1255 }
1256
1257 /**
1258  * gfs2_rgrp_go_unlock - Unlock a rgrp glock
1259  * @gh: The glock holder for the resource group
1260  *
1261  */
1262
1263 void gfs2_rgrp_go_unlock(struct gfs2_holder *gh)
1264 {
1265         struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
1266         int demote_requested = test_bit(GLF_DEMOTE, &gh->gh_gl->gl_flags) |
1267                 test_bit(GLF_PENDING_DEMOTE, &gh->gh_gl->gl_flags);
1268
1269         if (rgd && demote_requested)
1270                 gfs2_rgrp_brelse(rgd);
1271 }
1272
1273 int gfs2_rgrp_send_discards(struct gfs2_sbd *sdp, u64 offset,
1274                              struct buffer_head *bh,
1275                              const struct gfs2_bitmap *bi, unsigned minlen, u64 *ptrimmed)
1276 {
1277         struct super_block *sb = sdp->sd_vfs;
1278         u64 blk;
1279         sector_t start = 0;
1280         sector_t nr_blks = 0;
1281         int rv;
1282         unsigned int x;
1283         u32 trimmed = 0;
1284         u8 diff;
1285
1286         for (x = 0; x < bi->bi_len; x++) {
1287                 const u8 *clone = bi->bi_clone ? bi->bi_clone : bi->bi_bh->b_data;
1288                 clone += bi->bi_offset;
1289                 clone += x;
1290                 if (bh) {
1291                         const u8 *orig = bh->b_data + bi->bi_offset + x;
1292                         diff = ~(*orig | (*orig >> 1)) & (*clone | (*clone >> 1));
1293                 } else {
1294                         diff = ~(*clone | (*clone >> 1));
1295                 }
1296                 diff &= 0x55;
1297                 if (diff == 0)
1298                         continue;
1299                 blk = offset + ((bi->bi_start + x) * GFS2_NBBY);
1300                 while(diff) {
1301                         if (diff & 1) {
1302                                 if (nr_blks == 0)
1303                                         goto start_new_extent;
1304                                 if ((start + nr_blks) != blk) {
1305                                         if (nr_blks >= minlen) {
1306                                                 rv = sb_issue_discard(sb,
1307                                                         start, nr_blks,
1308                                                         GFP_NOFS, 0);
1309                                                 if (rv)
1310                                                         goto fail;
1311                                                 trimmed += nr_blks;
1312                                         }
1313                                         nr_blks = 0;
1314 start_new_extent:
1315                                         start = blk;
1316                                 }
1317                                 nr_blks++;
1318                         }
1319                         diff >>= 2;
1320                         blk++;
1321                 }
1322         }
1323         if (nr_blks >= minlen) {
1324                 rv = sb_issue_discard(sb, start, nr_blks, GFP_NOFS, 0);
1325                 if (rv)
1326                         goto fail;
1327                 trimmed += nr_blks;
1328         }
1329         if (ptrimmed)
1330                 *ptrimmed = trimmed;
1331         return 0;
1332
1333 fail:
1334         if (sdp->sd_args.ar_discard)
1335                 fs_warn(sdp, "error %d on discard request, turning discards off for this filesystem", rv);
1336         sdp->sd_args.ar_discard = 0;
1337         return -EIO;
1338 }
1339
1340 /**
1341  * gfs2_fitrim - Generate discard requests for unused bits of the filesystem
1342  * @filp: Any file on the filesystem
1343  * @argp: Pointer to the arguments (also used to pass result)
1344  *
1345  * Returns: 0 on success, otherwise error code
1346  */
1347
1348 int gfs2_fitrim(struct file *filp, void __user *argp)
1349 {
1350         struct inode *inode = file_inode(filp);
1351         struct gfs2_sbd *sdp = GFS2_SB(inode);
1352         struct request_queue *q = bdev_get_queue(sdp->sd_vfs->s_bdev);
1353         struct buffer_head *bh;
1354         struct gfs2_rgrpd *rgd;
1355         struct gfs2_rgrpd *rgd_end;
1356         struct gfs2_holder gh;
1357         struct fstrim_range r;
1358         int ret = 0;
1359         u64 amt;
1360         u64 trimmed = 0;
1361         u64 start, end, minlen;
1362         unsigned int x;
1363         unsigned bs_shift = sdp->sd_sb.sb_bsize_shift;
1364
1365         if (!capable(CAP_SYS_ADMIN))
1366                 return -EPERM;
1367
1368         if (!test_bit(SDF_JOURNAL_LIVE, &sdp->sd_flags))
1369                 return -EROFS;
1370
1371         if (!blk_queue_discard(q))
1372                 return -EOPNOTSUPP;
1373
1374         if (copy_from_user(&r, argp, sizeof(r)))
1375                 return -EFAULT;
1376
1377         ret = gfs2_rindex_update(sdp);
1378         if (ret)
1379                 return ret;
1380
1381         start = r.start >> bs_shift;
1382         end = start + (r.len >> bs_shift);
1383         minlen = max_t(u64, r.minlen,
1384                        q->limits.discard_granularity) >> bs_shift;
1385
1386         if (end <= start || minlen > sdp->sd_max_rg_data)
1387                 return -EINVAL;
1388
1389         rgd = gfs2_blk2rgrpd(sdp, start, 0);
1390         rgd_end = gfs2_blk2rgrpd(sdp, end, 0);
1391
1392         if ((gfs2_rgrpd_get_first(sdp) == gfs2_rgrpd_get_next(rgd_end))
1393             && (start > rgd_end->rd_data0 + rgd_end->rd_data))
1394                 return -EINVAL; /* start is beyond the end of the fs */
1395
1396         while (1) {
1397
1398                 ret = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE, 0, &gh);
1399                 if (ret)
1400                         goto out;
1401
1402                 if (!(rgd->rd_flags & GFS2_RGF_TRIMMED)) {
1403                         /* Trim each bitmap in the rgrp */
1404                         for (x = 0; x < rgd->rd_length; x++) {
1405                                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
1406                                 ret = gfs2_rgrp_send_discards(sdp,
1407                                                 rgd->rd_data0, NULL, bi, minlen,
1408                                                 &amt);
1409                                 if (ret) {
1410                                         gfs2_glock_dq_uninit(&gh);
1411                                         goto out;
1412                                 }
1413                                 trimmed += amt;
1414                         }
1415
1416                         /* Mark rgrp as having been trimmed */
1417                         ret = gfs2_trans_begin(sdp, RES_RG_HDR, 0);
1418                         if (ret == 0) {
1419                                 bh = rgd->rd_bits[0].bi_bh;
1420                                 rgd->rd_flags |= GFS2_RGF_TRIMMED;
1421                                 gfs2_trans_add_meta(rgd->rd_gl, bh);
1422                                 gfs2_rgrp_out(rgd, bh->b_data);
1423                                 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, bh->b_data);
1424                                 gfs2_trans_end(sdp);
1425                         }
1426                 }
1427                 gfs2_glock_dq_uninit(&gh);
1428
1429                 if (rgd == rgd_end)
1430                         break;
1431
1432                 rgd = gfs2_rgrpd_get_next(rgd);
1433         }
1434
1435 out:
1436         r.len = trimmed << bs_shift;
1437         if (copy_to_user(argp, &r, sizeof(r)))
1438                 return -EFAULT;
1439
1440         return ret;
1441 }
1442
1443 /**
1444  * rs_insert - insert a new multi-block reservation into the rgrp's rb_tree
1445  * @ip: the inode structure
1446  *
1447  */
1448 static void rs_insert(struct gfs2_inode *ip)
1449 {
1450         struct rb_node **newn, *parent = NULL;
1451         int rc;
1452         struct gfs2_blkreserv *rs = &ip->i_res;
1453         struct gfs2_rgrpd *rgd = rs->rs_rbm.rgd;
1454         u64 fsblock = gfs2_rbm_to_block(&rs->rs_rbm);
1455
1456         BUG_ON(gfs2_rs_active(rs));
1457
1458         spin_lock(&rgd->rd_rsspin);
1459         newn = &rgd->rd_rstree.rb_node;
1460         while (*newn) {
1461                 struct gfs2_blkreserv *cur =
1462                         rb_entry(*newn, struct gfs2_blkreserv, rs_node);
1463
1464                 parent = *newn;
1465                 rc = rs_cmp(fsblock, rs->rs_free, cur);
1466                 if (rc > 0)
1467                         newn = &((*newn)->rb_right);
1468                 else if (rc < 0)
1469                         newn = &((*newn)->rb_left);
1470                 else {
1471                         spin_unlock(&rgd->rd_rsspin);
1472                         WARN_ON(1);
1473                         return;
1474                 }
1475         }
1476
1477         rb_link_node(&rs->rs_node, parent, newn);
1478         rb_insert_color(&rs->rs_node, &rgd->rd_rstree);
1479
1480         /* Do our rgrp accounting for the reservation */
1481         rgd->rd_reserved += rs->rs_free; /* blocks reserved */
1482         spin_unlock(&rgd->rd_rsspin);
1483         trace_gfs2_rs(rs, TRACE_RS_INSERT);
1484 }
1485
1486 /**
1487  * rg_mblk_search - find a group of multiple free blocks to form a reservation
1488  * @rgd: the resource group descriptor
1489  * @ip: pointer to the inode for which we're reserving blocks
1490  * @ap: the allocation parameters
1491  *
1492  */
1493
1494 static void rg_mblk_search(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip,
1495                            const struct gfs2_alloc_parms *ap)
1496 {
1497         struct gfs2_rbm rbm = { .rgd = rgd, };
1498         u64 goal;
1499         struct gfs2_blkreserv *rs = &ip->i_res;
1500         u32 extlen;
1501         u32 free_blocks = rgd->rd_free_clone - rgd->rd_reserved;
1502         int ret;
1503         struct inode *inode = &ip->i_inode;
1504
1505         if (S_ISDIR(inode->i_mode))
1506                 extlen = 1;
1507         else {
1508                 extlen = max_t(u32, atomic_read(&rs->rs_sizehint), ap->target);
1509                 extlen = clamp(extlen, RGRP_RSRV_MINBLKS, free_blocks);
1510         }
1511         if ((rgd->rd_free_clone < rgd->rd_reserved) || (free_blocks < extlen))
1512                 return;
1513
1514         /* Find bitmap block that contains bits for goal block */
1515         if (rgrp_contains_block(rgd, ip->i_goal))
1516                 goal = ip->i_goal;
1517         else
1518                 goal = rgd->rd_last_alloc + rgd->rd_data0;
1519
1520         if (WARN_ON(gfs2_rbm_from_block(&rbm, goal)))
1521                 return;
1522
1523         ret = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, &extlen, ip, true);
1524         if (ret == 0) {
1525                 rs->rs_rbm = rbm;
1526                 rs->rs_free = extlen;
1527                 rs->rs_inum = ip->i_no_addr;
1528                 rs_insert(ip);
1529         } else {
1530                 if (goal == rgd->rd_last_alloc + rgd->rd_data0)
1531                         rgd->rd_last_alloc = 0;
1532         }
1533 }
1534
1535 /**
1536  * gfs2_next_unreserved_block - Return next block that is not reserved
1537  * @rgd: The resource group
1538  * @block: The starting block
1539  * @length: The required length
1540  * @ip: Ignore any reservations for this inode
1541  *
1542  * If the block does not appear in any reservation, then return the
1543  * block number unchanged. If it does appear in the reservation, then
1544  * keep looking through the tree of reservations in order to find the
1545  * first block number which is not reserved.
1546  */
1547
1548 static u64 gfs2_next_unreserved_block(struct gfs2_rgrpd *rgd, u64 block,
1549                                       u32 length,
1550                                       const struct gfs2_inode *ip)
1551 {
1552         struct gfs2_blkreserv *rs;
1553         struct rb_node *n;
1554         int rc;
1555
1556         spin_lock(&rgd->rd_rsspin);
1557         n = rgd->rd_rstree.rb_node;
1558         while (n) {
1559                 rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
1560                 rc = rs_cmp(block, length, rs);
1561                 if (rc < 0)
1562                         n = n->rb_left;
1563                 else if (rc > 0)
1564                         n = n->rb_right;
1565                 else
1566                         break;
1567         }
1568
1569         if (n) {
1570                 while ((rs_cmp(block, length, rs) == 0) && (&ip->i_res != rs)) {
1571                         block = gfs2_rbm_to_block(&rs->rs_rbm) + rs->rs_free;
1572                         n = n->rb_right;
1573                         if (n == NULL)
1574                                 break;
1575                         rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
1576                 }
1577         }
1578
1579         spin_unlock(&rgd->rd_rsspin);
1580         return block;
1581 }
1582
1583 /**
1584  * gfs2_reservation_check_and_update - Check for reservations during block alloc
1585  * @rbm: The current position in the resource group
1586  * @ip: The inode for which we are searching for blocks
1587  * @minext: The minimum extent length
1588  * @maxext: A pointer to the maximum extent structure
1589  *
1590  * This checks the current position in the rgrp to see whether there is
1591  * a reservation covering this block. If not then this function is a
1592  * no-op. If there is, then the position is moved to the end of the
1593  * contiguous reservation(s) so that we are pointing at the first
1594  * non-reserved block.
1595  *
1596  * Returns: 0 if no reservation, 1 if @rbm has changed, otherwise an error
1597  */
1598
1599 static int gfs2_reservation_check_and_update(struct gfs2_rbm *rbm,
1600                                              const struct gfs2_inode *ip,
1601                                              u32 minext,
1602                                              struct gfs2_extent *maxext)
1603 {
1604         u64 block = gfs2_rbm_to_block(rbm);
1605         u32 extlen = 1;
1606         u64 nblock;
1607         int ret;
1608
1609         /*
1610          * If we have a minimum extent length, then skip over any extent
1611          * which is less than the min extent length in size.
1612          */
1613         if (minext) {
1614                 extlen = gfs2_free_extlen(rbm, minext);
1615                 if (extlen <= maxext->len)
1616                         goto fail;
1617         }
1618
1619         /*
1620          * Check the extent which has been found against the reservations
1621          * and skip if parts of it are already reserved
1622          */
1623         nblock = gfs2_next_unreserved_block(rbm->rgd, block, extlen, ip);
1624         if (nblock == block) {
1625                 if (!minext || extlen >= minext)
1626                         return 0;
1627
1628                 if (extlen > maxext->len) {
1629                         maxext->len = extlen;
1630                         maxext->rbm = *rbm;
1631                 }
1632 fail:
1633                 nblock = block + extlen;
1634         }
1635         ret = gfs2_rbm_from_block(rbm, nblock);
1636         if (ret < 0)
1637                 return ret;
1638         return 1;
1639 }
1640
1641 /**
1642  * gfs2_rbm_find - Look for blocks of a particular state
1643  * @rbm: Value/result starting position and final position
1644  * @state: The state which we want to find
1645  * @minext: Pointer to the requested extent length (NULL for a single block)
1646  *          This is updated to be the actual reservation size.
1647  * @ip: If set, check for reservations
1648  * @nowrap: Stop looking at the end of the rgrp, rather than wrapping
1649  *          around until we've reached the starting point.
1650  *
1651  * Side effects:
1652  * - If looking for free blocks, we set GBF_FULL on each bitmap which
1653  *   has no free blocks in it.
1654  * - If looking for free blocks, we set rd_extfail_pt on each rgrp which
1655  *   has come up short on a free block search.
1656  *
1657  * Returns: 0 on success, -ENOSPC if there is no block of the requested state
1658  */
1659
1660 static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 *minext,
1661                          const struct gfs2_inode *ip, bool nowrap)
1662 {
1663         struct buffer_head *bh;
1664         int initial_bii;
1665         u32 initial_offset;
1666         int first_bii = rbm->bii;
1667         u32 first_offset = rbm->offset;
1668         u32 offset;
1669         u8 *buffer;
1670         int n = 0;
1671         int iters = rbm->rgd->rd_length;
1672         int ret;
1673         struct gfs2_bitmap *bi;
1674         struct gfs2_extent maxext = { .rbm.rgd = rbm->rgd, };
1675
1676         /* If we are not starting at the beginning of a bitmap, then we
1677          * need to add one to the bitmap count to ensure that we search
1678          * the starting bitmap twice.
1679          */
1680         if (rbm->offset != 0)
1681                 iters++;
1682
1683         while(1) {
1684                 bi = rbm_bi(rbm);
1685                 if ((ip == NULL || !gfs2_rs_active(&ip->i_res)) &&
1686                     test_bit(GBF_FULL, &bi->bi_flags) &&
1687                     (state == GFS2_BLKST_FREE))
1688                         goto next_bitmap;
1689
1690                 bh = bi->bi_bh;
1691                 buffer = bh->b_data + bi->bi_offset;
1692                 WARN_ON(!buffer_uptodate(bh));
1693                 if (state != GFS2_BLKST_UNLINKED && bi->bi_clone)
1694                         buffer = bi->bi_clone + bi->bi_offset;
1695                 initial_offset = rbm->offset;
1696                 offset = gfs2_bitfit(buffer, bi->bi_len, rbm->offset, state);
1697                 if (offset == BFITNOENT)
1698                         goto bitmap_full;
1699                 rbm->offset = offset;
1700                 if (ip == NULL)
1701                         return 0;
1702
1703                 initial_bii = rbm->bii;
1704                 ret = gfs2_reservation_check_and_update(rbm, ip,
1705                                                         minext ? *minext : 0,
1706                                                         &maxext);
1707                 if (ret == 0)
1708                         return 0;
1709                 if (ret > 0) {
1710                         n += (rbm->bii - initial_bii);
1711                         goto next_iter;
1712                 }
1713                 if (ret == -E2BIG) {
1714                         rbm->bii = 0;
1715                         rbm->offset = 0;
1716                         n += (rbm->bii - initial_bii);
1717                         goto res_covered_end_of_rgrp;
1718                 }
1719                 return ret;
1720
1721 bitmap_full:    /* Mark bitmap as full and fall through */
1722                 if ((state == GFS2_BLKST_FREE) && initial_offset == 0)
1723                         set_bit(GBF_FULL, &bi->bi_flags);
1724
1725 next_bitmap:    /* Find next bitmap in the rgrp */
1726                 rbm->offset = 0;
1727                 rbm->bii++;
1728                 if (rbm->bii == rbm->rgd->rd_length)
1729                         rbm->bii = 0;
1730 res_covered_end_of_rgrp:
1731                 if ((rbm->bii == 0) && nowrap)
1732                         break;
1733                 n++;
1734 next_iter:
1735                 if (n >= iters)
1736                         break;
1737         }
1738
1739         if (minext == NULL || state != GFS2_BLKST_FREE)
1740                 return -ENOSPC;
1741
1742         /* If the extent was too small, and it's smaller than the smallest
1743            to have failed before, remember for future reference that it's
1744            useless to search this rgrp again for this amount or more. */
1745         if ((first_offset == 0) && (first_bii == 0) &&
1746             (*minext < rbm->rgd->rd_extfail_pt))
1747                 rbm->rgd->rd_extfail_pt = *minext;
1748
1749         /* If the maximum extent we found is big enough to fulfill the
1750            minimum requirements, use it anyway. */
1751         if (maxext.len) {
1752                 *rbm = maxext.rbm;
1753                 *minext = maxext.len;
1754                 return 0;
1755         }
1756
1757         return -ENOSPC;
1758 }
1759
1760 /**
1761  * try_rgrp_unlink - Look for any unlinked, allocated, but unused inodes
1762  * @rgd: The rgrp
1763  * @last_unlinked: block address of the last dinode we unlinked
1764  * @skip: block address we should explicitly not unlink
1765  *
1766  * Returns: 0 if no error
1767  *          The inode, if one has been found, in inode.
1768  */
1769
1770 static void try_rgrp_unlink(struct gfs2_rgrpd *rgd, u64 *last_unlinked, u64 skip)
1771 {
1772         u64 block;
1773         struct gfs2_sbd *sdp = rgd->rd_sbd;
1774         struct gfs2_glock *gl;
1775         struct gfs2_inode *ip;
1776         int error;
1777         int found = 0;
1778         struct gfs2_rbm rbm = { .rgd = rgd, .bii = 0, .offset = 0 };
1779
1780         while (1) {
1781                 down_write(&sdp->sd_log_flush_lock);
1782                 error = gfs2_rbm_find(&rbm, GFS2_BLKST_UNLINKED, NULL, NULL,
1783                                       true);
1784                 up_write(&sdp->sd_log_flush_lock);
1785                 if (error == -ENOSPC)
1786                         break;
1787                 if (WARN_ON_ONCE(error))
1788                         break;
1789
1790                 block = gfs2_rbm_to_block(&rbm);
1791                 if (gfs2_rbm_from_block(&rbm, block + 1))
1792                         break;
1793                 if (*last_unlinked != NO_BLOCK && block <= *last_unlinked)
1794                         continue;
1795                 if (block == skip)
1796                         continue;
1797                 *last_unlinked = block;
1798
1799                 error = gfs2_glock_get(sdp, block, &gfs2_iopen_glops, CREATE, &gl);
1800                 if (error)
1801                         continue;
1802
1803                 /* If the inode is already in cache, we can ignore it here
1804                  * because the existing inode disposal code will deal with
1805                  * it when all refs have gone away. Accessing gl_object like
1806                  * this is not safe in general. Here it is ok because we do
1807                  * not dereference the pointer, and we only need an approx
1808                  * answer to whether it is NULL or not.
1809                  */
1810                 ip = gl->gl_object;
1811
1812                 if (ip || queue_work(gfs2_delete_workqueue, &gl->gl_delete) == 0)
1813                         gfs2_glock_put(gl);
1814                 else
1815                         found++;
1816
1817                 /* Limit reclaim to sensible number of tasks */
1818                 if (found > NR_CPUS)
1819                         return;
1820         }
1821
1822         rgd->rd_flags &= ~GFS2_RDF_CHECK;
1823         return;
1824 }
1825
1826 /**
1827  * gfs2_rgrp_congested - Use stats to figure out whether an rgrp is congested
1828  * @rgd: The rgrp in question
1829  * @loops: An indication of how picky we can be (0=very, 1=less so)
1830  *
1831  * This function uses the recently added glock statistics in order to
1832  * figure out whether a parciular resource group is suffering from
1833  * contention from multiple nodes. This is done purely on the basis
1834  * of timings, since this is the only data we have to work with and
1835  * our aim here is to reject a resource group which is highly contended
1836  * but (very important) not to do this too often in order to ensure that
1837  * we do not land up introducing fragmentation by changing resource
1838  * groups when not actually required.
1839  *
1840  * The calculation is fairly simple, we want to know whether the SRTTB
1841  * (i.e. smoothed round trip time for blocking operations) to acquire
1842  * the lock for this rgrp's glock is significantly greater than the
1843  * time taken for resource groups on average. We introduce a margin in
1844  * the form of the variable @var which is computed as the sum of the two
1845  * respective variences, and multiplied by a factor depending on @loops
1846  * and whether we have a lot of data to base the decision on. This is
1847  * then tested against the square difference of the means in order to
1848  * decide whether the result is statistically significant or not.
1849  *
1850  * Returns: A boolean verdict on the congestion status
1851  */
1852
1853 static bool gfs2_rgrp_congested(const struct gfs2_rgrpd *rgd, int loops)
1854 {
1855         const struct gfs2_glock *gl = rgd->rd_gl;
1856         const struct gfs2_sbd *sdp = gl->gl_name.ln_sbd;
1857         struct gfs2_lkstats *st;
1858         u64 r_dcount, l_dcount;
1859         u64 l_srttb, a_srttb = 0;
1860         s64 srttb_diff;
1861         u64 sqr_diff;
1862         u64 var;
1863         int cpu, nonzero = 0;
1864
1865         preempt_disable();
1866         for_each_present_cpu(cpu) {
1867                 st = &per_cpu_ptr(sdp->sd_lkstats, cpu)->lkstats[LM_TYPE_RGRP];
1868                 if (st->stats[GFS2_LKS_SRTTB]) {
1869                         a_srttb += st->stats[GFS2_LKS_SRTTB];
1870                         nonzero++;
1871                 }
1872         }
1873         st = &this_cpu_ptr(sdp->sd_lkstats)->lkstats[LM_TYPE_RGRP];
1874         if (nonzero)
1875                 do_div(a_srttb, nonzero);
1876         r_dcount = st->stats[GFS2_LKS_DCOUNT];
1877         var = st->stats[GFS2_LKS_SRTTVARB] +
1878               gl->gl_stats.stats[GFS2_LKS_SRTTVARB];
1879         preempt_enable();
1880
1881         l_srttb = gl->gl_stats.stats[GFS2_LKS_SRTTB];
1882         l_dcount = gl->gl_stats.stats[GFS2_LKS_DCOUNT];
1883
1884         if ((l_dcount < 1) || (r_dcount < 1) || (a_srttb == 0))
1885                 return false;
1886
1887         srttb_diff = a_srttb - l_srttb;
1888         sqr_diff = srttb_diff * srttb_diff;
1889
1890         var *= 2;
1891         if (l_dcount < 8 || r_dcount < 8)
1892                 var *= 2;
1893         if (loops == 1)
1894                 var *= 2;
1895
1896         return ((srttb_diff < 0) && (sqr_diff > var));
1897 }
1898
1899 /**
1900  * gfs2_rgrp_used_recently
1901  * @rs: The block reservation with the rgrp to test
1902  * @msecs: The time limit in milliseconds
1903  *
1904  * Returns: True if the rgrp glock has been used within the time limit
1905  */
1906 static bool gfs2_rgrp_used_recently(const struct gfs2_blkreserv *rs,
1907                                     u64 msecs)
1908 {
1909         u64 tdiff;
1910
1911         tdiff = ktime_to_ns(ktime_sub(ktime_get_real(),
1912                             rs->rs_rbm.rgd->rd_gl->gl_dstamp));
1913
1914         return tdiff > (msecs * 1000 * 1000);
1915 }
1916
1917 static u32 gfs2_orlov_skip(const struct gfs2_inode *ip)
1918 {
1919         const struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1920         u32 skip;
1921
1922         get_random_bytes(&skip, sizeof(skip));
1923         return skip % sdp->sd_rgrps;
1924 }
1925
1926 static bool gfs2_select_rgrp(struct gfs2_rgrpd **pos, const struct gfs2_rgrpd *begin)
1927 {
1928         struct gfs2_rgrpd *rgd = *pos;
1929         struct gfs2_sbd *sdp = rgd->rd_sbd;
1930
1931         rgd = gfs2_rgrpd_get_next(rgd);
1932         if (rgd == NULL)
1933                 rgd = gfs2_rgrpd_get_first(sdp);
1934         *pos = rgd;
1935         if (rgd != begin) /* If we didn't wrap */
1936                 return true;
1937         return false;
1938 }
1939
1940 /**
1941  * fast_to_acquire - determine if a resource group will be fast to acquire
1942  *
1943  * If this is one of our preferred rgrps, it should be quicker to acquire,
1944  * because we tried to set ourselves up as dlm lock master.
1945  */
1946 static inline int fast_to_acquire(struct gfs2_rgrpd *rgd)
1947 {
1948         struct gfs2_glock *gl = rgd->rd_gl;
1949
1950         if (gl->gl_state != LM_ST_UNLOCKED && list_empty(&gl->gl_holders) &&
1951             !test_bit(GLF_DEMOTE_IN_PROGRESS, &gl->gl_flags) &&
1952             !test_bit(GLF_DEMOTE, &gl->gl_flags))
1953                 return 1;
1954         if (rgd->rd_flags & GFS2_RDF_PREFERRED)
1955                 return 1;
1956         return 0;
1957 }
1958
1959 /**
1960  * gfs2_inplace_reserve - Reserve space in the filesystem
1961  * @ip: the inode to reserve space for
1962  * @ap: the allocation parameters
1963  *
1964  * We try our best to find an rgrp that has at least ap->target blocks
1965  * available. After a couple of passes (loops == 2), the prospects of finding
1966  * such an rgrp diminish. At this stage, we return the first rgrp that has
1967  * atleast ap->min_target blocks available. Either way, we set ap->allowed to
1968  * the number of blocks available in the chosen rgrp.
1969  *
1970  * Returns: 0 on success,
1971  *          -ENOMEM if a suitable rgrp can't be found
1972  *          errno otherwise
1973  */
1974
1975 int gfs2_inplace_reserve(struct gfs2_inode *ip, struct gfs2_alloc_parms *ap)
1976 {
1977         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1978         struct gfs2_rgrpd *begin = NULL;
1979         struct gfs2_blkreserv *rs = &ip->i_res;
1980         int error = 0, rg_locked, flags = 0;
1981         u64 last_unlinked = NO_BLOCK;
1982         int loops = 0;
1983         u32 skip = 0;
1984
1985         if (sdp->sd_args.ar_rgrplvb)
1986                 flags |= GL_SKIP;
1987         if (gfs2_assert_warn(sdp, ap->target))
1988                 return -EINVAL;
1989         if (gfs2_rs_active(rs)) {
1990                 begin = rs->rs_rbm.rgd;
1991         } else if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, ip->i_goal)) {
1992                 rs->rs_rbm.rgd = begin = ip->i_rgd;
1993         } else {
1994                 check_and_update_goal(ip);
1995                 rs->rs_rbm.rgd = begin = gfs2_blk2rgrpd(sdp, ip->i_goal, 1);
1996         }
1997         if (S_ISDIR(ip->i_inode.i_mode) && (ap->aflags & GFS2_AF_ORLOV))
1998                 skip = gfs2_orlov_skip(ip);
1999         if (rs->rs_rbm.rgd == NULL)
2000                 return -EBADSLT;
2001
2002         while (loops < 3) {
2003                 rg_locked = 1;
2004
2005                 if (!gfs2_glock_is_locked_by_me(rs->rs_rbm.rgd->rd_gl)) {
2006                         rg_locked = 0;
2007                         if (skip && skip--)
2008                                 goto next_rgrp;
2009                         if (!gfs2_rs_active(rs)) {
2010                                 if (loops == 0 &&
2011                                     !fast_to_acquire(rs->rs_rbm.rgd))
2012                                         goto next_rgrp;
2013                                 if ((loops < 2) &&
2014                                     gfs2_rgrp_used_recently(rs, 1000) &&
2015                                     gfs2_rgrp_congested(rs->rs_rbm.rgd, loops))
2016                                         goto next_rgrp;
2017                         }
2018                         error = gfs2_glock_nq_init(rs->rs_rbm.rgd->rd_gl,
2019                                                    LM_ST_EXCLUSIVE, flags,
2020                                                    &rs->rs_rgd_gh);
2021                         if (unlikely(error))
2022                                 return error;
2023                         if (!gfs2_rs_active(rs) && (loops < 2) &&
2024                             gfs2_rgrp_congested(rs->rs_rbm.rgd, loops))
2025                                 goto skip_rgrp;
2026                         if (sdp->sd_args.ar_rgrplvb) {
2027                                 error = update_rgrp_lvb(rs->rs_rbm.rgd);
2028                                 if (unlikely(error)) {
2029                                         gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2030                                         return error;
2031                                 }
2032                         }
2033                 }
2034
2035                 /* Skip unuseable resource groups */
2036                 if ((rs->rs_rbm.rgd->rd_flags & (GFS2_RGF_NOALLOC |
2037                                                  GFS2_RDF_ERROR)) ||
2038                     (loops == 0 && ap->target > rs->rs_rbm.rgd->rd_extfail_pt))
2039                         goto skip_rgrp;
2040
2041                 if (sdp->sd_args.ar_rgrplvb)
2042                         gfs2_rgrp_bh_get(rs->rs_rbm.rgd);
2043
2044                 /* Get a reservation if we don't already have one */
2045                 if (!gfs2_rs_active(rs))
2046                         rg_mblk_search(rs->rs_rbm.rgd, ip, ap);
2047
2048                 /* Skip rgrps when we can't get a reservation on first pass */
2049                 if (!gfs2_rs_active(rs) && (loops < 1))
2050                         goto check_rgrp;
2051
2052                 /* If rgrp has enough free space, use it */
2053                 if (rs->rs_rbm.rgd->rd_free_clone >= ap->target ||
2054                     (loops == 2 && ap->min_target &&
2055                      rs->rs_rbm.rgd->rd_free_clone >= ap->min_target)) {
2056                         ip->i_rgd = rs->rs_rbm.rgd;
2057                         ap->allowed = ip->i_rgd->rd_free_clone;
2058                         return 0;
2059                 }
2060 check_rgrp:
2061                 /* Check for unlinked inodes which can be reclaimed */
2062                 if (rs->rs_rbm.rgd->rd_flags & GFS2_RDF_CHECK)
2063                         try_rgrp_unlink(rs->rs_rbm.rgd, &last_unlinked,
2064                                         ip->i_no_addr);
2065 skip_rgrp:
2066                 /* Drop reservation, if we couldn't use reserved rgrp */
2067                 if (gfs2_rs_active(rs))
2068                         gfs2_rs_deltree(rs);
2069
2070                 /* Unlock rgrp if required */
2071                 if (!rg_locked)
2072                         gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2073 next_rgrp:
2074                 /* Find the next rgrp, and continue looking */
2075                 if (gfs2_select_rgrp(&rs->rs_rbm.rgd, begin))
2076                         continue;
2077                 if (skip)
2078                         continue;
2079
2080                 /* If we've scanned all the rgrps, but found no free blocks
2081                  * then this checks for some less likely conditions before
2082                  * trying again.
2083                  */
2084                 loops++;
2085                 /* Check that fs hasn't grown if writing to rindex */
2086                 if (ip == GFS2_I(sdp->sd_rindex) && !sdp->sd_rindex_uptodate) {
2087                         error = gfs2_ri_update(ip);
2088                         if (error)
2089                                 return error;
2090                 }
2091                 /* Flushing the log may release space */
2092                 if (loops == 2)
2093                         gfs2_log_flush(sdp, NULL, NORMAL_FLUSH);
2094         }
2095
2096         return -ENOSPC;
2097 }
2098
2099 /**
2100  * gfs2_inplace_release - release an inplace reservation
2101  * @ip: the inode the reservation was taken out on
2102  *
2103  * Release a reservation made by gfs2_inplace_reserve().
2104  */
2105
2106 void gfs2_inplace_release(struct gfs2_inode *ip)
2107 {
2108         struct gfs2_blkreserv *rs = &ip->i_res;
2109
2110         if (gfs2_holder_initialized(&rs->rs_rgd_gh))
2111                 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2112 }
2113
2114 /**
2115  * gfs2_get_block_type - Check a block in a RG is of given type
2116  * @rgd: the resource group holding the block
2117  * @block: the block number
2118  *
2119  * Returns: The block type (GFS2_BLKST_*)
2120  */
2121
2122 static unsigned char gfs2_get_block_type(struct gfs2_rgrpd *rgd, u64 block)
2123 {
2124         struct gfs2_rbm rbm = { .rgd = rgd, };
2125         int ret;
2126
2127         ret = gfs2_rbm_from_block(&rbm, block);
2128         WARN_ON_ONCE(ret != 0);
2129
2130         return gfs2_testbit(&rbm);
2131 }
2132
2133
2134 /**
2135  * gfs2_alloc_extent - allocate an extent from a given bitmap
2136  * @rbm: the resource group information
2137  * @dinode: TRUE if the first block we allocate is for a dinode
2138  * @n: The extent length (value/result)
2139  *
2140  * Add the bitmap buffer to the transaction.
2141  * Set the found bits to @new_state to change block's allocation state.
2142  */
2143 static void gfs2_alloc_extent(const struct gfs2_rbm *rbm, bool dinode,
2144                              unsigned int *n)
2145 {
2146         struct gfs2_rbm pos = { .rgd = rbm->rgd, };
2147         const unsigned int elen = *n;
2148         u64 block;
2149         int ret;
2150
2151         *n = 1;
2152         block = gfs2_rbm_to_block(rbm);
2153         gfs2_trans_add_meta(rbm->rgd->rd_gl, rbm_bi(rbm)->bi_bh);
2154         gfs2_setbit(rbm, true, dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
2155         block++;
2156         while (*n < elen) {
2157                 ret = gfs2_rbm_from_block(&pos, block);
2158                 if (ret || gfs2_testbit(&pos) != GFS2_BLKST_FREE)
2159                         break;
2160                 gfs2_trans_add_meta(pos.rgd->rd_gl, rbm_bi(&pos)->bi_bh);
2161                 gfs2_setbit(&pos, true, GFS2_BLKST_USED);
2162                 (*n)++;
2163                 block++;
2164         }
2165 }
2166
2167 /**
2168  * rgblk_free - Change alloc state of given block(s)
2169  * @sdp: the filesystem
2170  * @bstart: the start of a run of blocks to free
2171  * @blen: the length of the block run (all must lie within ONE RG!)
2172  * @new_state: GFS2_BLKST_XXX the after-allocation block state
2173  *
2174  * Returns:  Resource group containing the block(s)
2175  */
2176
2177 static struct gfs2_rgrpd *rgblk_free(struct gfs2_sbd *sdp, u64 bstart,
2178                                      u32 blen, unsigned char new_state)
2179 {
2180         struct gfs2_rbm rbm;
2181         struct gfs2_bitmap *bi, *bi_prev = NULL;
2182
2183         rbm.rgd = gfs2_blk2rgrpd(sdp, bstart, 1);
2184         if (!rbm.rgd) {
2185                 if (gfs2_consist(sdp))
2186                         fs_err(sdp, "block = %llu\n", (unsigned long long)bstart);
2187                 return NULL;
2188         }
2189
2190         gfs2_rbm_from_block(&rbm, bstart);
2191         while (blen--) {
2192                 bi = rbm_bi(&rbm);
2193                 if (bi != bi_prev) {
2194                         if (!bi->bi_clone) {
2195                                 bi->bi_clone = kmalloc(bi->bi_bh->b_size,
2196                                                       GFP_NOFS | __GFP_NOFAIL);
2197                                 memcpy(bi->bi_clone + bi->bi_offset,
2198                                        bi->bi_bh->b_data + bi->bi_offset,
2199                                        bi->bi_len);
2200                         }
2201                         gfs2_trans_add_meta(rbm.rgd->rd_gl, bi->bi_bh);
2202                         bi_prev = bi;
2203                 }
2204                 gfs2_setbit(&rbm, false, new_state);
2205                 gfs2_rbm_incr(&rbm);
2206         }
2207
2208         return rbm.rgd;
2209 }
2210
2211 /**
2212  * gfs2_rgrp_dump - print out an rgrp
2213  * @seq: The iterator
2214  * @gl: The glock in question
2215  *
2216  */
2217
2218 void gfs2_rgrp_dump(struct seq_file *seq, const struct gfs2_glock *gl)
2219 {
2220         struct gfs2_rgrpd *rgd = gl->gl_object;
2221         struct gfs2_blkreserv *trs;
2222         const struct rb_node *n;
2223
2224         if (rgd == NULL)
2225                 return;
2226         gfs2_print_dbg(seq, " R: n:%llu f:%02x b:%u/%u i:%u r:%u e:%u\n",
2227                        (unsigned long long)rgd->rd_addr, rgd->rd_flags,
2228                        rgd->rd_free, rgd->rd_free_clone, rgd->rd_dinodes,
2229                        rgd->rd_reserved, rgd->rd_extfail_pt);
2230         spin_lock(&rgd->rd_rsspin);
2231         for (n = rb_first(&rgd->rd_rstree); n; n = rb_next(&trs->rs_node)) {
2232                 trs = rb_entry(n, struct gfs2_blkreserv, rs_node);
2233                 dump_rs(seq, trs);
2234         }
2235         spin_unlock(&rgd->rd_rsspin);
2236 }
2237
2238 static void gfs2_rgrp_error(struct gfs2_rgrpd *rgd)
2239 {
2240         struct gfs2_sbd *sdp = rgd->rd_sbd;
2241         fs_warn(sdp, "rgrp %llu has an error, marking it readonly until umount\n",
2242                 (unsigned long long)rgd->rd_addr);
2243         fs_warn(sdp, "umount on all nodes and run fsck.gfs2 to fix the error\n");
2244         gfs2_rgrp_dump(NULL, rgd->rd_gl);
2245         rgd->rd_flags |= GFS2_RDF_ERROR;
2246 }
2247
2248 /**
2249  * gfs2_adjust_reservation - Adjust (or remove) a reservation after allocation
2250  * @ip: The inode we have just allocated blocks for
2251  * @rbm: The start of the allocated blocks
2252  * @len: The extent length
2253  *
2254  * Adjusts a reservation after an allocation has taken place. If the
2255  * reservation does not match the allocation, or if it is now empty
2256  * then it is removed.
2257  */
2258
2259 static void gfs2_adjust_reservation(struct gfs2_inode *ip,
2260                                     const struct gfs2_rbm *rbm, unsigned len)
2261 {
2262         struct gfs2_blkreserv *rs = &ip->i_res;
2263         struct gfs2_rgrpd *rgd = rbm->rgd;
2264         unsigned rlen;
2265         u64 block;
2266         int ret;
2267
2268         spin_lock(&rgd->rd_rsspin);
2269         if (gfs2_rs_active(rs)) {
2270                 if (gfs2_rbm_eq(&rs->rs_rbm, rbm)) {
2271                         block = gfs2_rbm_to_block(rbm);
2272                         ret = gfs2_rbm_from_block(&rs->rs_rbm, block + len);
2273                         rlen = min(rs->rs_free, len);
2274                         rs->rs_free -= rlen;
2275                         rgd->rd_reserved -= rlen;
2276                         trace_gfs2_rs(rs, TRACE_RS_CLAIM);
2277                         if (rs->rs_free && !ret)
2278                                 goto out;
2279                         /* We used up our block reservation, so we should
2280                            reserve more blocks next time. */
2281                         atomic_add(RGRP_RSRV_ADDBLKS, &rs->rs_sizehint);
2282                 }
2283                 __rs_deltree(rs);
2284         }
2285 out:
2286         spin_unlock(&rgd->rd_rsspin);
2287 }
2288
2289 /**
2290  * gfs2_set_alloc_start - Set starting point for block allocation
2291  * @rbm: The rbm which will be set to the required location
2292  * @ip: The gfs2 inode
2293  * @dinode: Flag to say if allocation includes a new inode
2294  *
2295  * This sets the starting point from the reservation if one is active
2296  * otherwise it falls back to guessing a start point based on the
2297  * inode's goal block or the last allocation point in the rgrp.
2298  */
2299
2300 static void gfs2_set_alloc_start(struct gfs2_rbm *rbm,
2301                                  const struct gfs2_inode *ip, bool dinode)
2302 {
2303         u64 goal;
2304
2305         if (gfs2_rs_active(&ip->i_res)) {
2306                 *rbm = ip->i_res.rs_rbm;
2307                 return;
2308         }
2309
2310         if (!dinode && rgrp_contains_block(rbm->rgd, ip->i_goal))
2311                 goal = ip->i_goal;
2312         else
2313                 goal = rbm->rgd->rd_last_alloc + rbm->rgd->rd_data0;
2314
2315         gfs2_rbm_from_block(rbm, goal);
2316 }
2317
2318 /**
2319  * gfs2_alloc_blocks - Allocate one or more blocks of data and/or a dinode
2320  * @ip: the inode to allocate the block for
2321  * @bn: Used to return the starting block number
2322  * @nblocks: requested number of blocks/extent length (value/result)
2323  * @dinode: 1 if we're allocating a dinode block, else 0
2324  * @generation: the generation number of the inode
2325  *
2326  * Returns: 0 or error
2327  */
2328
2329 int gfs2_alloc_blocks(struct gfs2_inode *ip, u64 *bn, unsigned int *nblocks,
2330                       bool dinode, u64 *generation)
2331 {
2332         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2333         struct buffer_head *dibh;
2334         struct gfs2_rbm rbm = { .rgd = ip->i_rgd, };
2335         unsigned int ndata;
2336         u64 block; /* block, within the file system scope */
2337         int error;
2338
2339         gfs2_set_alloc_start(&rbm, ip, dinode);
2340         error = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, NULL, ip, false);
2341
2342         if (error == -ENOSPC) {
2343                 gfs2_set_alloc_start(&rbm, ip, dinode);
2344                 error = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, NULL, NULL, false);
2345         }
2346
2347         /* Since all blocks are reserved in advance, this shouldn't happen */
2348         if (error) {
2349                 fs_warn(sdp, "inum=%llu error=%d, nblocks=%u, full=%d fail_pt=%d\n",
2350                         (unsigned long long)ip->i_no_addr, error, *nblocks,
2351                         test_bit(GBF_FULL, &rbm.rgd->rd_bits->bi_flags),
2352                         rbm.rgd->rd_extfail_pt);
2353                 goto rgrp_error;
2354         }
2355
2356         gfs2_alloc_extent(&rbm, dinode, nblocks);
2357         block = gfs2_rbm_to_block(&rbm);
2358         rbm.rgd->rd_last_alloc = block - rbm.rgd->rd_data0;
2359         if (gfs2_rs_active(&ip->i_res))
2360                 gfs2_adjust_reservation(ip, &rbm, *nblocks);
2361         ndata = *nblocks;
2362         if (dinode)
2363                 ndata--;
2364
2365         if (!dinode) {
2366                 ip->i_goal = block + ndata - 1;
2367                 error = gfs2_meta_inode_buffer(ip, &dibh);
2368                 if (error == 0) {
2369                         struct gfs2_dinode *di =
2370                                 (struct gfs2_dinode *)dibh->b_data;
2371                         gfs2_trans_add_meta(ip->i_gl, dibh);
2372                         di->di_goal_meta = di->di_goal_data =
2373                                 cpu_to_be64(ip->i_goal);
2374                         brelse(dibh);
2375                 }
2376         }
2377         if (rbm.rgd->rd_free < *nblocks) {
2378                 pr_warn("nblocks=%u\n", *nblocks);
2379                 goto rgrp_error;
2380         }
2381
2382         rbm.rgd->rd_free -= *nblocks;
2383         if (dinode) {
2384                 rbm.rgd->rd_dinodes++;
2385                 *generation = rbm.rgd->rd_igeneration++;
2386                 if (*generation == 0)
2387                         *generation = rbm.rgd->rd_igeneration++;
2388         }
2389
2390         gfs2_trans_add_meta(rbm.rgd->rd_gl, rbm.rgd->rd_bits[0].bi_bh);
2391         gfs2_rgrp_out(rbm.rgd, rbm.rgd->rd_bits[0].bi_bh->b_data);
2392         gfs2_rgrp_ondisk2lvb(rbm.rgd->rd_rgl, rbm.rgd->rd_bits[0].bi_bh->b_data);
2393
2394         gfs2_statfs_change(sdp, 0, -(s64)*nblocks, dinode ? 1 : 0);
2395         if (dinode)
2396                 gfs2_trans_add_unrevoke(sdp, block, *nblocks);
2397
2398         gfs2_quota_change(ip, *nblocks, ip->i_inode.i_uid, ip->i_inode.i_gid);
2399
2400         rbm.rgd->rd_free_clone -= *nblocks;
2401         trace_gfs2_block_alloc(ip, rbm.rgd, block, *nblocks,
2402                                dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
2403         *bn = block;
2404         return 0;
2405
2406 rgrp_error:
2407         gfs2_rgrp_error(rbm.rgd);
2408         return -EIO;
2409 }
2410
2411 /**
2412  * __gfs2_free_blocks - free a contiguous run of block(s)
2413  * @ip: the inode these blocks are being freed from
2414  * @bstart: first block of a run of contiguous blocks
2415  * @blen: the length of the block run
2416  * @meta: 1 if the blocks represent metadata
2417  *
2418  */
2419
2420 void __gfs2_free_blocks(struct gfs2_inode *ip, u64 bstart, u32 blen, int meta)
2421 {
2422         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2423         struct gfs2_rgrpd *rgd;
2424
2425         rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
2426         if (!rgd)
2427                 return;
2428         trace_gfs2_block_alloc(ip, rgd, bstart, blen, GFS2_BLKST_FREE);
2429         rgd->rd_free += blen;
2430         rgd->rd_flags &= ~GFS2_RGF_TRIMMED;
2431         gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2432         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2433         gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2434
2435         /* Directories keep their data in the metadata address space */
2436         if (meta || ip->i_depth)
2437                 gfs2_meta_wipe(ip, bstart, blen);
2438 }
2439
2440 /**
2441  * gfs2_free_meta - free a contiguous run of data block(s)
2442  * @ip: the inode these blocks are being freed from
2443  * @bstart: first block of a run of contiguous blocks
2444  * @blen: the length of the block run
2445  *
2446  */
2447
2448 void gfs2_free_meta(struct gfs2_inode *ip, u64 bstart, u32 blen)
2449 {
2450         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2451
2452         __gfs2_free_blocks(ip, bstart, blen, 1);
2453         gfs2_statfs_change(sdp, 0, +blen, 0);
2454         gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
2455 }
2456
2457 void gfs2_unlink_di(struct inode *inode)
2458 {
2459         struct gfs2_inode *ip = GFS2_I(inode);
2460         struct gfs2_sbd *sdp = GFS2_SB(inode);
2461         struct gfs2_rgrpd *rgd;
2462         u64 blkno = ip->i_no_addr;
2463
2464         rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_UNLINKED);
2465         if (!rgd)
2466                 return;
2467         trace_gfs2_block_alloc(ip, rgd, blkno, 1, GFS2_BLKST_UNLINKED);
2468         gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2469         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2470         gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2471         update_rgrp_lvb_unlinked(rgd, 1);
2472 }
2473
2474 static void gfs2_free_uninit_di(struct gfs2_rgrpd *rgd, u64 blkno)
2475 {
2476         struct gfs2_sbd *sdp = rgd->rd_sbd;
2477         struct gfs2_rgrpd *tmp_rgd;
2478
2479         tmp_rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_FREE);
2480         if (!tmp_rgd)
2481                 return;
2482         gfs2_assert_withdraw(sdp, rgd == tmp_rgd);
2483
2484         if (!rgd->rd_dinodes)
2485                 gfs2_consist_rgrpd(rgd);
2486         rgd->rd_dinodes--;
2487         rgd->rd_free++;
2488
2489         gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2490         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2491         gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2492         update_rgrp_lvb_unlinked(rgd, -1);
2493
2494         gfs2_statfs_change(sdp, 0, +1, -1);
2495 }
2496
2497
2498 void gfs2_free_di(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip)
2499 {
2500         gfs2_free_uninit_di(rgd, ip->i_no_addr);
2501         trace_gfs2_block_alloc(ip, rgd, ip->i_no_addr, 1, GFS2_BLKST_FREE);
2502         gfs2_quota_change(ip, -1, ip->i_inode.i_uid, ip->i_inode.i_gid);
2503         gfs2_meta_wipe(ip, ip->i_no_addr, 1);
2504 }
2505
2506 /**
2507  * gfs2_check_blk_type - Check the type of a block
2508  * @sdp: The superblock
2509  * @no_addr: The block number to check
2510  * @type: The block type we are looking for
2511  *
2512  * Returns: 0 if the block type matches the expected type
2513  *          -ESTALE if it doesn't match
2514  *          or -ve errno if something went wrong while checking
2515  */
2516
2517 int gfs2_check_blk_type(struct gfs2_sbd *sdp, u64 no_addr, unsigned int type)
2518 {
2519         struct gfs2_rgrpd *rgd;
2520         struct gfs2_holder rgd_gh;
2521         int error = -EINVAL;
2522
2523         rgd = gfs2_blk2rgrpd(sdp, no_addr, 1);
2524         if (!rgd)
2525                 goto fail;
2526
2527         error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_SHARED, 0, &rgd_gh);
2528         if (error)
2529                 goto fail;
2530
2531         if (gfs2_get_block_type(rgd, no_addr) != type)
2532                 error = -ESTALE;
2533
2534         gfs2_glock_dq_uninit(&rgd_gh);
2535 fail:
2536         return error;
2537 }
2538
2539 /**
2540  * gfs2_rlist_add - add a RG to a list of RGs
2541  * @ip: the inode
2542  * @rlist: the list of resource groups
2543  * @block: the block
2544  *
2545  * Figure out what RG a block belongs to and add that RG to the list
2546  *
2547  * FIXME: Don't use NOFAIL
2548  *
2549  */
2550
2551 void gfs2_rlist_add(struct gfs2_inode *ip, struct gfs2_rgrp_list *rlist,
2552                     u64 block)
2553 {
2554         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2555         struct gfs2_rgrpd *rgd;
2556         struct gfs2_rgrpd **tmp;
2557         unsigned int new_space;
2558         unsigned int x;
2559
2560         if (gfs2_assert_warn(sdp, !rlist->rl_ghs))
2561                 return;
2562
2563         if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, block))
2564                 rgd = ip->i_rgd;
2565         else
2566                 rgd = gfs2_blk2rgrpd(sdp, block, 1);
2567         if (!rgd) {
2568                 fs_err(sdp, "rlist_add: no rgrp for block %llu\n", (unsigned long long)block);
2569                 return;
2570         }
2571         ip->i_rgd = rgd;
2572
2573         for (x = 0; x < rlist->rl_rgrps; x++)
2574                 if (rlist->rl_rgd[x] == rgd)
2575                         return;
2576
2577         if (rlist->rl_rgrps == rlist->rl_space) {
2578                 new_space = rlist->rl_space + 10;
2579
2580                 tmp = kcalloc(new_space, sizeof(struct gfs2_rgrpd *),
2581                               GFP_NOFS | __GFP_NOFAIL);
2582
2583                 if (rlist->rl_rgd) {
2584                         memcpy(tmp, rlist->rl_rgd,
2585                                rlist->rl_space * sizeof(struct gfs2_rgrpd *));
2586                         kfree(rlist->rl_rgd);
2587                 }
2588
2589                 rlist->rl_space = new_space;
2590                 rlist->rl_rgd = tmp;
2591         }
2592
2593         rlist->rl_rgd[rlist->rl_rgrps++] = rgd;
2594 }
2595
2596 /**
2597  * gfs2_rlist_alloc - all RGs have been added to the rlist, now allocate
2598  *      and initialize an array of glock holders for them
2599  * @rlist: the list of resource groups
2600  * @state: the lock state to acquire the RG lock in
2601  *
2602  * FIXME: Don't use NOFAIL
2603  *
2604  */
2605
2606 void gfs2_rlist_alloc(struct gfs2_rgrp_list *rlist, unsigned int state)
2607 {
2608         unsigned int x;
2609
2610         rlist->rl_ghs = kmalloc(rlist->rl_rgrps * sizeof(struct gfs2_holder),
2611                                 GFP_NOFS | __GFP_NOFAIL);
2612         for (x = 0; x < rlist->rl_rgrps; x++)
2613                 gfs2_holder_init(rlist->rl_rgd[x]->rd_gl,
2614                                 state, 0,
2615                                 &rlist->rl_ghs[x]);
2616 }
2617
2618 /**
2619  * gfs2_rlist_free - free a resource group list
2620  * @rlist: the list of resource groups
2621  *
2622  */
2623
2624 void gfs2_rlist_free(struct gfs2_rgrp_list *rlist)
2625 {
2626         unsigned int x;
2627
2628         kfree(rlist->rl_rgd);
2629
2630         if (rlist->rl_ghs) {
2631                 for (x = 0; x < rlist->rl_rgrps; x++)
2632                         gfs2_holder_uninit(&rlist->rl_ghs[x]);
2633                 kfree(rlist->rl_ghs);
2634                 rlist->rl_ghs = NULL;
2635         }
2636 }
2637