fs/gfs2/rgrp.c

   1 /*
   2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
   3  * Copyright (C) 2004-2007 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 #include <linux/slab.h>
  11 #include <linux/spinlock.h>
  12 #include <linux/completion.h>
  13 #include <linux/buffer_head.h>
  14 #include <linux/fs.h>
  15 #include <linux/gfs2_ondisk.h>
  16 #include <linux/lm_interface.h>
  17
  18 #include "gfs2.h"
  19 #include "incore.h"
  20 #include "glock.h"
  21 #include "glops.h"
  22 #include "lops.h"
  23 #include "meta_io.h"
  24 #include "quota.h"
  25 #include "rgrp.h"
  26 #include "super.h"
  27 #include "trans.h"
  28 #include "ops_file.h"
  29 #include "util.h"
  30 #include "log.h"
  31 #include "inode.h"
  32
  33 #define BFITNOENT ((u32)~0)
  34 #define NO_BLOCK ((u64)~0)
  35
  36 /*
  37  * These routines are used by the resource group routines (rgrp.c)
  38  * to keep track of block allocation.  Each block is represented by two
  39  * bits.  So, each byte represents GFS2_NBBY (i.e. 4) blocks.
  40  *
  41  * 0 = Free
  42  * 1 = Used (not metadata)
  43  * 2 = Unlinked (still in use) inode
  44  * 3 = Used (metadata)
  45  */
  46
  47 static const char valid_change[16] = {
  48                 /* current */
  49         /* n */ 0, 1, 1, 1,
  50         /* e */ 1, 0, 0, 0,
  51         /* w */ 0, 0, 0, 1,
  52                 1, 0, 0, 0
  53 };
  54
  55 static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
  56                         unsigned char old_state, unsigned char new_state);
  57
  58 /**
  59  * gfs2_setbit - Set a bit in the bitmaps
  60  * @buffer: the buffer that holds the bitmaps
  61  * @buflen: the length (in bytes) of the buffer
  62  * @block: the block to set
  63  * @new_state: the new state of the block
  64  *
  65  */
  66
  67 static void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  68                         unsigned int buflen, u32 block,
  69                         unsigned char new_state)
  70 {
  71         unsigned char *byte, *end, cur_state;
  72         unsigned int bit;
  73
  74         byte = buffer + (block / GFS2_NBBY);
  75         bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
  76         end = buffer + buflen;
  77
  78         gfs2_assert(rgd->rd_sbd, byte < end);
  79
  80         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
  81
  82         if (valid_change[new_state * 4 + cur_state]) {
  83                 *byte ^= cur_state << bit;
  84                 *byte |= new_state << bit;
  85         } else
  86                 gfs2_consist_rgrpd(rgd);
  87 }
  88
  89 /**
  90  * gfs2_testbit - test a bit in the bitmaps
  91  * @buffer: the buffer that holds the bitmaps
  92  * @buflen: the length (in bytes) of the buffer
  93  * @block: the block to read
  94  *
  95  */
  96
  97 static unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  98                                   unsigned int buflen, u32 block)
  99 {
 100         unsigned char *byte, *end, cur_state;
 101         unsigned int bit;
 102
 103         byte = buffer + (block / GFS2_NBBY);
 104         bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
 105         end = buffer + buflen;
 106
 107         gfs2_assert(rgd->rd_sbd, byte < end);
 108
 109         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
 110
 111         return cur_state;
 112 }
 113
 114 /**
 115  * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
 116  *       a block in a given allocation state.
 117  * @buffer: the buffer that holds the bitmaps
 118  * @buflen: the length (in bytes) of the buffer
 119  * @goal: start search at this block's bit-pair (within @buffer)
 120  * @old_state: GFS2_BLKST_XXX the state of the block we're looking for.
 121  *
 122  * Scope of @goal and returned block number is only within this bitmap buffer,
 123  * not entire rgrp or filesystem.  @buffer will be offset from the actual
 124  * beginning of a bitmap block buffer, skipping any header structures.
 125  *
 126  * Return: the block number (bitmap buffer scope) that was found
 127  */
 128
 129 static u32 gfs2_bitfit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
 130                             unsigned int buflen, u32 goal,
 131                             unsigned char old_state)
 132 {
 133         unsigned char *byte, *end, alloc;
 134         u32 blk = goal;
 135         unsigned int bit;
 136
 137         byte = buffer + (goal / GFS2_NBBY);
 138         bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
 139         end = buffer + buflen;
 140         alloc = (old_state == GFS2_BLKST_FREE) ? 0x55 : 0;
 141
 142         while (byte < end) {
 143                 /* If we're looking for a free block we can eliminate all
 144                    bitmap settings with 0x55, which represents four data
 145                    blocks in a row.  If we're looking for a data block, we can
 146                    eliminate 0x00 which corresponds to four free blocks. */
 147                 if ((*byte & 0x55) == alloc) {
 148                         blk += (8 - bit) >> 1;
 149
 150                         bit = 0;
 151                         byte++;
 152
 153                         continue;
 154                 }
 155
 156                 if (((*byte >> bit) & GFS2_BIT_MASK) == old_state)
 157                         return blk;
 158
 159                 bit += GFS2_BIT_SIZE;
 160                 if (bit >= 8) {
 161                         bit = 0;
 162                         byte++;
 163                 }
 164
 165                 blk++;
 166         }
 167
 168         return BFITNOENT;
 169 }
 170
 171 /**
 172  * gfs2_bitcount - count the number of bits in a certain state
 173  * @buffer: the buffer that holds the bitmaps
 174  * @buflen: the length (in bytes) of the buffer
 175  * @state: the state of the block we're looking for
 176  *
 177  * Returns: The number of bits
 178  */
 179
 180 static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, unsigned char *buffer,
 181                               unsigned int buflen, unsigned char state)
 182 {
 183         unsigned char *byte = buffer;
 184         unsigned char *end = buffer + buflen;
 185         unsigned char state1 = state << 2;
 186         unsigned char state2 = state << 4;
 187         unsigned char state3 = state << 6;
 188         u32 count = 0;
 189
 190         for (; byte < end; byte++) {
 191                 if (((*byte) & 0x03) == state)
 192                         count++;
 193                 if (((*byte) & 0x0C) == state1)
 194                         count++;
 195                 if (((*byte) & 0x30) == state2)
 196                         count++;
 197                 if (((*byte) & 0xC0) == state3)
 198                         count++;
 199         }
 200
 201         return count;
 202 }
 203
 204 /**
 205  * gfs2_rgrp_verify - Verify that a resource group is consistent
 206  * @sdp: the filesystem
 207  * @rgd: the rgrp
 208  *
 209  */
 210
 211 void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
 212 {
 213         struct gfs2_sbd *sdp = rgd->rd_sbd;
 214         struct gfs2_bitmap *bi = NULL;
 215         u32 length = rgd->rd_length;
 216         u32 count[4], tmp;
 217         int buf, x;
 218
 219         memset(count, 0, 4 * sizeof(u32));
 220
 221         /* Count # blocks in each of 4 possible allocation states */
 222         for (buf = 0; buf < length; buf++) {
 223                 bi = rgd->rd_bits + buf;
 224                 for (x = 0; x < 4; x++)
 225                         count[x] += gfs2_bitcount(rgd,
 226                                                   bi->bi_bh->b_data +
 227                                                   bi->bi_offset,
 228                                                   bi->bi_len, x);
 229         }
 230
 231         if (count[0] != rgd->rd_rg.rg_free) {
 232                 if (gfs2_consist_rgrpd(rgd))
 233                         fs_err(sdp, "free data mismatch:  %u != %u\n",
 234                                count[0], rgd->rd_rg.rg_free);
 235                 return;
 236         }
 237
 238         tmp = rgd->rd_data -
 239                 rgd->rd_rg.rg_free -
 240                 rgd->rd_rg.rg_dinodes;
 241         if (count[1] + count[2] != tmp) {
 242                 if (gfs2_consist_rgrpd(rgd))
 243                         fs_err(sdp, "used data mismatch:  %u != %u\n",
 244                                count[1], tmp);
 245                 return;
 246         }
 247
 248         if (count[3] != rgd->rd_rg.rg_dinodes) {
 249                 if (gfs2_consist_rgrpd(rgd))
 250                         fs_err(sdp, "used metadata mismatch:  %u != %u\n",
 251                                count[3], rgd->rd_rg.rg_dinodes);
 252                 return;
 253         }
 254
 255         if (count[2] > count[3]) {
 256                 if (gfs2_consist_rgrpd(rgd))
 257                         fs_err(sdp, "unlinked inodes > inodes:  %u\n",
 258                                count[2]);
 259                 return;
 260         }
 261
 262 }
 263
 264 static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
 265 {
 266         u64 first = rgd->rd_data0;
 267         u64 last = first + rgd->rd_data;
 268         return first <= block && block < last;
 269 }
 270
 271 /**
 272  * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 273  * @sdp: The GFS2 superblock
 274  * @n: The data block number
 275  *
 276  * Returns: The resource group, or NULL if not found
 277  */
 278
 279 struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk)
 280 {
 281         struct gfs2_rgrpd *rgd;
 282
 283         spin_lock(&sdp->sd_rindex_spin);
 284
 285         list_for_each_entry(rgd, &sdp->sd_rindex_mru_list, rd_list_mru) {
 286                 if (rgrp_contains_block(rgd, blk)) {
 287                         list_move(&rgd->rd_list_mru, &sdp->sd_rindex_mru_list);
 288                         spin_unlock(&sdp->sd_rindex_spin);
 289                         return rgd;
 290                 }
 291         }
 292
 293         spin_unlock(&sdp->sd_rindex_spin);
 294
 295         return NULL;
 296 }
 297
 298 /**
 299  * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
 300  * @sdp: The GFS2 superblock
 301  *
 302  * Returns: The first rgrp in the filesystem
 303  */
 304
 305 struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
 306 {
 307         gfs2_assert(sdp, !list_empty(&sdp->sd_rindex_list));
 308         return list_entry(sdp->sd_rindex_list.next, struct gfs2_rgrpd, rd_list);
 309 }
 310
 311 /**
 312  * gfs2_rgrpd_get_next - get the next RG
 313  * @rgd: A RG
 314  *
 315  * Returns: The next rgrp
 316  */
 317
 318 struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
 319 {
 320         if (rgd->rd_list.next == &rgd->rd_sbd->sd_rindex_list)
 321                 return NULL;
 322         return list_entry(rgd->rd_list.next, struct gfs2_rgrpd, rd_list);
 323 }
 324
 325 static void clear_rgrpdi(struct gfs2_sbd *sdp)
 326 {
 327         struct list_head *head;
 328         struct gfs2_rgrpd *rgd;
 329         struct gfs2_glock *gl;
 330
 331         spin_lock(&sdp->sd_rindex_spin);
 332         sdp->sd_rindex_forward = NULL;
 333         head = &sdp->sd_rindex_recent_list;
 334         while (!list_empty(head)) {
 335                 rgd = list_entry(head->next, struct gfs2_rgrpd, rd_recent);
 336                 list_del(&rgd->rd_recent);
 337         }
 338         spin_unlock(&sdp->sd_rindex_spin);
 339
 340         head = &sdp->sd_rindex_list;
 341         while (!list_empty(head)) {
 342                 rgd = list_entry(head->next, struct gfs2_rgrpd, rd_list);
 343                 gl = rgd->rd_gl;
 344
 345                 list_del(&rgd->rd_list);
 346                 list_del(&rgd->rd_list_mru);
 347
 348                 if (gl) {
 349                         gl->gl_object = NULL;
 350                         gfs2_glock_put(gl);
 351                 }
 352
 353                 kfree(rgd->rd_bits);
 354                 kfree(rgd);
 355         }
 356 }
 357
 358 void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
 359 {
 360         mutex_lock(&sdp->sd_rindex_mutex);
 361         clear_rgrpdi(sdp);
 362         mutex_unlock(&sdp->sd_rindex_mutex);
 363 }
 364
 365 static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
 366 {
 367         printk(KERN_INFO "  ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
 368         printk(KERN_INFO "  ri_length = %u\n", rgd->rd_length);
 369         printk(KERN_INFO "  ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
 370         printk(KERN_INFO "  ri_data = %u\n", rgd->rd_data);
 371         printk(KERN_INFO "  ri_bitbytes = %u\n", rgd->rd_bitbytes);
 372 }
 373
 374 /**
 375  * gfs2_compute_bitstructs - Compute the bitmap sizes
 376  * @rgd: The resource group descriptor
 377  *
 378  * Calculates bitmap descriptors, one for each block that contains bitmap data
 379  *
 380  * Returns: errno
 381  */
 382
 383 static int compute_bitstructs(struct gfs2_rgrpd *rgd)
 384 {
 385         struct gfs2_sbd *sdp = rgd->rd_sbd;
 386         struct gfs2_bitmap *bi;
 387         u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
 388         u32 bytes_left, bytes;
 389         int x;
 390
 391         if (!length)
 392                 return -EINVAL;
 393
 394         rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
 395         if (!rgd->rd_bits)
 396                 return -ENOMEM;
 397
 398         bytes_left = rgd->rd_bitbytes;
 399
 400         for (x = 0; x < length; x++) {
 401                 bi = rgd->rd_bits + x;
 402
 403                 /* small rgrp; bitmap stored completely in header block */
 404                 if (length == 1) {
 405                         bytes = bytes_left;
 406                         bi->bi_offset = sizeof(struct gfs2_rgrp);
 407                         bi->bi_start = 0;
 408                         bi->bi_len = bytes;
 409                 /* header block */
 410                 } else if (x == 0) {
 411                         bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
 412                         bi->bi_offset = sizeof(struct gfs2_rgrp);
 413                         bi->bi_start = 0;
 414                         bi->bi_len = bytes;
 415                 /* last block */
 416                 } else if (x + 1 == length) {
 417                         bytes = bytes_left;
 418                         bi->bi_offset = sizeof(struct gfs2_meta_header);
 419                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
 420                         bi->bi_len = bytes;
 421                 /* other blocks */
 422                 } else {
 423                         bytes = sdp->sd_sb.sb_bsize -
 424                                 sizeof(struct gfs2_meta_header);
 425                         bi->bi_offset = sizeof(struct gfs2_meta_header);
 426                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
 427                         bi->bi_len = bytes;
 428                 }
 429
 430                 bytes_left -= bytes;
 431         }
 432
 433         if (bytes_left) {
 434                 gfs2_consist_rgrpd(rgd);
 435                 return -EIO;
 436         }
 437         bi = rgd->rd_bits + (length - 1);
 438         if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
 439                 if (gfs2_consist_rgrpd(rgd)) {
 440                         gfs2_rindex_print(rgd);
 441                         fs_err(sdp, "start=%u len=%u offset=%u\n",
 442                                bi->bi_start, bi->bi_len, bi->bi_offset);
 443                 }
 444                 return -EIO;
 445         }
 446
 447         return 0;
 448 }
 449
 450 /**
 451  * gfs2_ri_total - Total up the file system space, according to the rindex.
 452  *
 453  */
 454 u64 gfs2_ri_total(struct gfs2_sbd *sdp)
 455 {
 456         u64 total_data = 0;
 457         struct inode *inode = sdp->sd_rindex;
 458         struct gfs2_inode *ip = GFS2_I(inode);
 459         char buf[sizeof(struct gfs2_rindex)];
 460         struct file_ra_state ra_state;
 461         int error, rgrps;
 462
 463         mutex_lock(&sdp->sd_rindex_mutex);
 464         file_ra_state_init(&ra_state, inode->i_mapping);
 465         for (rgrps = 0;; rgrps++) {
 466                 loff_t pos = rgrps * sizeof(struct gfs2_rindex);
 467
 468                 if (pos + sizeof(struct gfs2_rindex) >= ip->i_di.di_size)
 469                         break;
 470                 error = gfs2_internal_read(ip, &ra_state, buf, &pos,
 471                                            sizeof(struct gfs2_rindex));
 472                 if (error != sizeof(struct gfs2_rindex))
 473                         break;
 474                 total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
 475         }
 476         mutex_unlock(&sdp->sd_rindex_mutex);
 477         return total_data;
 478 }
 479
 480 static void gfs2_rindex_in(struct gfs2_rgrpd *rgd, const void *buf)
 481 {
 482         const struct gfs2_rindex *str = buf;
 483
 484         rgd->rd_addr = be64_to_cpu(str->ri_addr);
 485         rgd->rd_length = be32_to_cpu(str->ri_length);
 486         rgd->rd_data0 = be64_to_cpu(str->ri_data0);
 487         rgd->rd_data = be32_to_cpu(str->ri_data);
 488         rgd->rd_bitbytes = be32_to_cpu(str->ri_bitbytes);
 489 }
 490
 491 /**
 492  * read_rindex_entry - Pull in a new resource index entry from the disk
 493  * @gl: The glock covering the rindex inode
 494  *
 495  * Returns: 0 on success, error code otherwise
 496  */
 497
 498 static int read_rindex_entry(struct gfs2_inode *ip,
 499                              struct file_ra_state *ra_state)
 500 {
 501         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 502         loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
 503         char buf[sizeof(struct gfs2_rindex)];
 504         int error;
 505         struct gfs2_rgrpd *rgd;
 506
 507         error = gfs2_internal_read(ip, ra_state, buf, &pos,
 508                                    sizeof(struct gfs2_rindex));
 509         if (!error)
 510                 return 0;
 511         if (error != sizeof(struct gfs2_rindex)) {
 512                 if (error > 0)
 513                         error = -EIO;
 514                 return error;
 515         }
 516
 517         rgd = kzalloc(sizeof(struct gfs2_rgrpd), GFP_NOFS);
 518         error = -ENOMEM;
 519         if (!rgd)
 520                 return error;
 521
 522         mutex_init(&rgd->rd_mutex);
 523         lops_init_le(&rgd->rd_le, &gfs2_rg_lops);
 524         rgd->rd_sbd = sdp;
 525
 526         list_add_tail(&rgd->rd_list, &sdp->sd_rindex_list);
 527         list_add_tail(&rgd->rd_list_mru, &sdp->sd_rindex_mru_list);
 528
 529         gfs2_rindex_in(rgd, buf);
 530         error = compute_bitstructs(rgd);
 531         if (error)
 532                 return error;
 533
 534         error = gfs2_glock_get(sdp, rgd->rd_addr,
 535                                &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
 536         if (error)
 537                 return error;
 538
 539         rgd->rd_gl->gl_object = rgd;
 540         rgd->rd_rg_vn = rgd->rd_gl->gl_vn - 1;
 541         rgd->rd_flags |= GFS2_RDF_CHECK;
 542         return error;
 543 }
 544
 545 /**
 546  * gfs2_ri_update - Pull in a new resource index from the disk
 547  * @ip: pointer to the rindex inode
 548  *
 549  * Returns: 0 on successful update, error code otherwise
 550  */
 551
 552 static int gfs2_ri_update(struct gfs2_inode *ip)
 553 {
 554         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 555         struct inode *inode = &ip->i_inode;
 556         struct file_ra_state ra_state;
 557         u64 rgrp_count = ip->i_di.di_size;
 558         int error;
 559
 560         if (do_div(rgrp_count, sizeof(struct gfs2_rindex))) {
 561                 gfs2_consist_inode(ip);
 562                 return -EIO;
 563         }
 564
 565         clear_rgrpdi(sdp);
 566
 567         file_ra_state_init(&ra_state, inode->i_mapping);
 568         for (sdp->sd_rgrps = 0; sdp->sd_rgrps < rgrp_count; sdp->sd_rgrps++) {
 569                 error = read_rindex_entry(ip, &ra_state);
 570                 if (error) {
 571                         clear_rgrpdi(sdp);
 572                         return error;
 573                 }
 574         }
 575
 576         sdp->sd_rindex_vn = ip->i_gl->gl_vn;
 577         return 0;
 578 }
 579
 580 /**
 581  * gfs2_ri_update_special - Pull in a new resource index from the disk
 582  *
 583  * This is a special version that's safe to call from gfs2_inplace_reserve_i.
 584  * In this case we know that we don't have any resource groups in memory yet.
 585  *
 586  * @ip: pointer to the rindex inode
 587  *
 588  * Returns: 0 on successful update, error code otherwise
 589  */
 590 static int gfs2_ri_update_special(struct gfs2_inode *ip)
 591 {
 592         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 593         struct inode *inode = &ip->i_inode;
 594         struct file_ra_state ra_state;
 595         int error;
 596
 597         file_ra_state_init(&ra_state, inode->i_mapping);
 598         for (sdp->sd_rgrps = 0;; sdp->sd_rgrps++) {
 599                 /* Ignore partials */
 600                 if ((sdp->sd_rgrps + 1) * sizeof(struct gfs2_rindex) >
 601                     ip->i_di.di_size)
 602                         break;
 603                 error = read_rindex_entry(ip, &ra_state);
 604                 if (error) {
 605                         clear_rgrpdi(sdp);
 606                         return error;
 607                 }
 608         }
 609
 610         sdp->sd_rindex_vn = ip->i_gl->gl_vn;
 611         return 0;
 612 }
 613
 614 /**
 615  * gfs2_rindex_hold - Grab a lock on the rindex
 616  * @sdp: The GFS2 superblock
 617  * @ri_gh: the glock holder
 618  *
 619  * We grab a lock on the rindex inode to make sure that it doesn't
 620  * change whilst we are performing an operation. We keep this lock
 621  * for quite long periods of time compared to other locks. This
 622  * doesn't matter, since it is shared and it is very, very rarely
 623  * accessed in the exclusive mode (i.e. only when expanding the filesystem).
 624  *
 625  * This makes sure that we're using the latest copy of the resource index
 626  * special file, which might have been updated if someone expanded the
 627  * filesystem (via gfs2_grow utility), which adds new resource groups.
 628  *
 629  * Returns: 0 on success, error code otherwise
 630  */
 631
 632 int gfs2_rindex_hold(struct gfs2_sbd *sdp, struct gfs2_holder *ri_gh)
 633 {
 634         struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
 635         struct gfs2_glock *gl = ip->i_gl;
 636         int error;
 637
 638         error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, ri_gh);
 639         if (error)
 640                 return error;
 641
 642         /* Read new copy from disk if we don't have the latest */
 643         if (sdp->sd_rindex_vn != gl->gl_vn) {
 644                 mutex_lock(&sdp->sd_rindex_mutex);
 645                 if (sdp->sd_rindex_vn != gl->gl_vn) {
 646                         error = gfs2_ri_update(ip);
 647                         if (error)
 648                                 gfs2_glock_dq_uninit(ri_gh);
 649                 }
 650                 mutex_unlock(&sdp->sd_rindex_mutex);
 651         }
 652
 653         return error;
 654 }
 655
 656 static void gfs2_rgrp_in(struct gfs2_rgrp_host *rg, const void *buf)
 657 {
 658         const struct gfs2_rgrp *str = buf;
 659
 660         rg->rg_flags = be32_to_cpu(str->rg_flags);
 661         rg->rg_free = be32_to_cpu(str->rg_free);
 662         rg->rg_dinodes = be32_to_cpu(str->rg_dinodes);
 663         rg->rg_igeneration = be64_to_cpu(str->rg_igeneration);
 664 }
 665
 666 static void gfs2_rgrp_out(const struct gfs2_rgrp_host *rg, void *buf)
 667 {
 668         struct gfs2_rgrp *str = buf;
 669
 670         str->rg_flags = cpu_to_be32(rg->rg_flags);
 671         str->rg_free = cpu_to_be32(rg->rg_free);
 672         str->rg_dinodes = cpu_to_be32(rg->rg_dinodes);
 673         str->__pad = cpu_to_be32(0);
 674         str->rg_igeneration = cpu_to_be64(rg->rg_igeneration);
 675         memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
 676 }
 677
 678 /**
 679  * gfs2_rgrp_bh_get - Read in a RG's header and bitmaps
 680  * @rgd: the struct gfs2_rgrpd describing the RG to read in
 681  *
 682  * Read in all of a Resource Group's header and bitmap blocks.
 683  * Caller must eventually call gfs2_rgrp_relse() to free the bitmaps.
 684  *
 685  * Returns: errno
 686  */
 687
 688 int gfs2_rgrp_bh_get(struct gfs2_rgrpd *rgd)
 689 {
 690         struct gfs2_sbd *sdp = rgd->rd_sbd;
 691         struct gfs2_glock *gl = rgd->rd_gl;
 692         unsigned int length = rgd->rd_length;
 693         struct gfs2_bitmap *bi;
 694         unsigned int x, y;
 695         int error;
 696
 697         mutex_lock(&rgd->rd_mutex);
 698
 699         spin_lock(&sdp->sd_rindex_spin);
 700         if (rgd->rd_bh_count) {
 701                 rgd->rd_bh_count++;
 702                 spin_unlock(&sdp->sd_rindex_spin);
 703                 mutex_unlock(&rgd->rd_mutex);
 704                 return 0;
 705         }
 706         spin_unlock(&sdp->sd_rindex_spin);
 707
 708         for (x = 0; x < length; x++) {
 709                 bi = rgd->rd_bits + x;
 710                 error = gfs2_meta_read(gl, rgd->rd_addr + x, 0, &bi->bi_bh);
 711                 if (error)
 712                         goto fail;
 713         }
 714
 715         for (y = length; y--;) {
 716                 bi = rgd->rd_bits + y;
 717                 error = gfs2_meta_wait(sdp, bi->bi_bh);
 718                 if (error)
 719                         goto fail;
 720                 if (gfs2_metatype_check(sdp, bi->bi_bh, y ? GFS2_METATYPE_RB :
 721                                               GFS2_METATYPE_RG)) {
 722                         error = -EIO;
 723                         goto fail;
 724                 }
 725         }
 726
 727         if (rgd->rd_rg_vn != gl->gl_vn) {
 728                 gfs2_rgrp_in(&rgd->rd_rg, (rgd->rd_bits[0].bi_bh)->b_data);
 729                 rgd->rd_rg_vn = gl->gl_vn;
 730         }
 731
 732         spin_lock(&sdp->sd_rindex_spin);
 733         rgd->rd_free_clone = rgd->rd_rg.rg_free;
 734         rgd->rd_bh_count++;
 735         spin_unlock(&sdp->sd_rindex_spin);
 736
 737         mutex_unlock(&rgd->rd_mutex);
 738
 739         return 0;
 740
 741 fail:
 742         while (x--) {
 743                 bi = rgd->rd_bits + x;
 744                 brelse(bi->bi_bh);
 745                 bi->bi_bh = NULL;
 746                 gfs2_assert_warn(sdp, !bi->bi_clone);
 747         }
 748         mutex_unlock(&rgd->rd_mutex);
 749
 750         return error;
 751 }
 752
 753 void gfs2_rgrp_bh_hold(struct gfs2_rgrpd *rgd)
 754 {
 755         struct gfs2_sbd *sdp = rgd->rd_sbd;
 756
 757         spin_lock(&sdp->sd_rindex_spin);
 758         gfs2_assert_warn(rgd->rd_sbd, rgd->rd_bh_count);
 759         rgd->rd_bh_count++;
 760         spin_unlock(&sdp->sd_rindex_spin);
 761 }
 762
 763 /**
 764  * gfs2_rgrp_bh_put - Release RG bitmaps read in with gfs2_rgrp_bh_get()
 765  * @rgd: the struct gfs2_rgrpd describing the RG to read in
 766  *
 767  */
 768
 769 void gfs2_rgrp_bh_put(struct gfs2_rgrpd *rgd)
 770 {
 771         struct gfs2_sbd *sdp = rgd->rd_sbd;
 772         int x, length = rgd->rd_length;
 773
 774         spin_lock(&sdp->sd_rindex_spin);
 775         gfs2_assert_warn(rgd->rd_sbd, rgd->rd_bh_count);
 776         if (--rgd->rd_bh_count) {
 777                 spin_unlock(&sdp->sd_rindex_spin);
 778                 return;
 779         }
 780
 781         for (x = 0; x < length; x++) {
 782                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
 783                 kfree(bi->bi_clone);
 784                 bi->bi_clone = NULL;
 785                 brelse(bi->bi_bh);
 786                 bi->bi_bh = NULL;
 787         }
 788
 789         spin_unlock(&sdp->sd_rindex_spin);
 790 }
 791
 792 void gfs2_rgrp_repolish_clones(struct gfs2_rgrpd *rgd)
 793 {
 794         struct gfs2_sbd *sdp = rgd->rd_sbd;
 795         unsigned int length = rgd->rd_length;
 796         unsigned int x;
 797
 798         for (x = 0; x < length; x++) {
 799                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
 800                 if (!bi->bi_clone)
 801                         continue;
 802                 memcpy(bi->bi_clone + bi->bi_offset,
 803                        bi->bi_bh->b_data + bi->bi_offset, bi->bi_len);
 804         }
 805
 806         spin_lock(&sdp->sd_rindex_spin);
 807         rgd->rd_free_clone = rgd->rd_rg.rg_free;
 808         spin_unlock(&sdp->sd_rindex_spin);
 809 }
 810
 811 /**
 812  * gfs2_alloc_get - get the struct gfs2_alloc structure for an inode
 813  * @ip: the incore GFS2 inode structure
 814  *
 815  * Returns: the struct gfs2_alloc
 816  */
 817
 818 struct gfs2_alloc *gfs2_alloc_get(struct gfs2_inode *ip)
 819 {
 820         struct gfs2_alloc *al = &ip->i_alloc;
 821
 822         /* FIXME: Should assert that the correct locks are held here... */
 823         memset(al, 0, sizeof(*al));
 824         return al;
 825 }
 826
 827 /**
 828  * try_rgrp_fit - See if a given reservation will fit in a given RG
 829  * @rgd: the RG data
 830  * @al: the struct gfs2_alloc structure describing the reservation
 831  *
 832  * If there's room for the requested blocks to be allocated from the RG:
 833  *   Sets the $al_rgd field in @al.
 834  *
 835  * Returns: 1 on success (it fits), 0 on failure (it doesn't fit)
 836  */
 837
 838 static int try_rgrp_fit(struct gfs2_rgrpd *rgd, struct gfs2_alloc *al)
 839 {
 840         struct gfs2_sbd *sdp = rgd->rd_sbd;
 841         int ret = 0;
 842
 843         if (rgd->rd_rg.rg_flags & GFS2_RGF_NOALLOC)
 844                 return 0;
 845
 846         spin_lock(&sdp->sd_rindex_spin);
 847         if (rgd->rd_free_clone >= al->al_requested) {
 848                 al->al_rgd = rgd;
 849                 ret = 1;
 850         }
 851         spin_unlock(&sdp->sd_rindex_spin);
 852
 853         return ret;
 854 }
 855
 856 /**
 857  * try_rgrp_unlink - Look for any unlinked, allocated, but unused inodes
 858  * @rgd: The rgrp
 859  *
 860  * Returns: The inode, if one has been found
 861  */
 862
 863 static struct inode *try_rgrp_unlink(struct gfs2_rgrpd *rgd, u64 *last_unlinked)
 864 {
 865         struct inode *inode;
 866         u32 goal = 0, block;
 867         u64 no_addr;
 868
 869         for(;;) {
 870                 if (goal >= rgd->rd_data)
 871                         break;
 872                 block = rgblk_search(rgd, goal, GFS2_BLKST_UNLINKED,
 873                                      GFS2_BLKST_UNLINKED);
 874                 if (block == BFITNOENT)
 875                         break;
 876                 /* rgblk_search can return a block < goal, so we need to
 877                    keep it marching forward. */
 878                 no_addr = block + rgd->rd_data0;
 879                 goal++;
 880                 if (*last_unlinked != NO_BLOCK && no_addr <= *last_unlinked)
 881                         continue;
 882                 *last_unlinked = no_addr;
 883                 inode = gfs2_inode_lookup(rgd->rd_sbd->sd_vfs, DT_UNKNOWN,
 884                                           no_addr, -1);
 885                 if (!IS_ERR(inode))
 886                         return inode;
 887         }
 888
 889         rgd->rd_flags &= ~GFS2_RDF_CHECK;
 890         return NULL;
 891 }
 892
 893 /**
 894  * recent_rgrp_first - get first RG from "recent" list
 895  * @sdp: The GFS2 superblock
 896  * @rglast: address of the rgrp used last
 897  *
 898  * Returns: The first rgrp in the recent list
 899  */
 900
 901 static struct gfs2_rgrpd *recent_rgrp_first(struct gfs2_sbd *sdp,
 902                                             u64 rglast)
 903 {
 904         struct gfs2_rgrpd *rgd = NULL;
 905
 906         spin_lock(&sdp->sd_rindex_spin);
 907
 908         if (list_empty(&sdp->sd_rindex_recent_list))
 909                 goto out;
 910
 911         if (!rglast)
 912                 goto first;
 913
 914         list_for_each_entry(rgd, &sdp->sd_rindex_recent_list, rd_recent) {
 915                 if (rgd->rd_addr == rglast)
 916                         goto out;
 917         }
 918
 919 first:
 920         rgd = list_entry(sdp->sd_rindex_recent_list.next, struct gfs2_rgrpd,
 921                          rd_recent);
 922 out:
 923         spin_unlock(&sdp->sd_rindex_spin);
 924         return rgd;
 925 }
 926
 927 /**
 928  * recent_rgrp_next - get next RG from "recent" list
 929  * @cur_rgd: current rgrp
 930  * @remove:
 931  *
 932  * Returns: The next rgrp in the recent list
 933  */
 934
 935 static struct gfs2_rgrpd *recent_rgrp_next(struct gfs2_rgrpd *cur_rgd,
 936                                            int remove)
 937 {
 938         struct gfs2_sbd *sdp = cur_rgd->rd_sbd;
 939         struct list_head *head;
 940         struct gfs2_rgrpd *rgd;
 941
 942         spin_lock(&sdp->sd_rindex_spin);
 943
 944         head = &sdp->sd_rindex_recent_list;
 945
 946         list_for_each_entry(rgd, head, rd_recent) {
 947                 if (rgd == cur_rgd) {
 948                         if (cur_rgd->rd_recent.next != head)
 949                                 rgd = list_entry(cur_rgd->rd_recent.next,
 950                                                  struct gfs2_rgrpd, rd_recent);
 951                         else
 952                                 rgd = NULL;
 953
 954                         if (remove)
 955                                 list_del(&cur_rgd->rd_recent);
 956
 957                         goto out;
 958                 }
 959         }
 960
 961         rgd = NULL;
 962         if (!list_empty(head))
 963                 rgd = list_entry(head->next, struct gfs2_rgrpd, rd_recent);
 964
 965 out:
 966         spin_unlock(&sdp->sd_rindex_spin);
 967         return rgd;
 968 }
 969
 970 /**
 971  * recent_rgrp_add - add an RG to tail of "recent" list
 972  * @new_rgd: The rgrp to add
 973  *
 974  */
 975
 976 static void recent_rgrp_add(struct gfs2_rgrpd *new_rgd)
 977 {
 978         struct gfs2_sbd *sdp = new_rgd->rd_sbd;
 979         struct gfs2_rgrpd *rgd;
 980         unsigned int count = 0;
 981         unsigned int max = sdp->sd_rgrps / gfs2_jindex_size(sdp);
 982
 983         spin_lock(&sdp->sd_rindex_spin);
 984
 985         list_for_each_entry(rgd, &sdp->sd_rindex_recent_list, rd_recent) {
 986                 if (rgd == new_rgd)
 987                         goto out;
 988
 989                 if (++count >= max)
 990                         goto out;
 991         }
 992         list_add_tail(&new_rgd->rd_recent, &sdp->sd_rindex_recent_list);
 993
 994 out:
 995         spin_unlock(&sdp->sd_rindex_spin);
 996 }
 997
 998 /**
 999  * forward_rgrp_get - get an rgrp to try next from full list
1000  * @sdp: The GFS2 superblock
1001  *
1002  * Returns: The rgrp to try next
1003  */
1004
1005 static struct gfs2_rgrpd *forward_rgrp_get(struct gfs2_sbd *sdp)
1006 {
1007         struct gfs2_rgrpd *rgd;
1008         unsigned int journals = gfs2_jindex_size(sdp);
1009         unsigned int rg = 0, x;
1010
1011         spin_lock(&sdp->sd_rindex_spin);
1012
1013         rgd = sdp->sd_rindex_forward;
1014         if (!rgd) {
1015                 if (sdp->sd_rgrps >= journals)
1016                         rg = sdp->sd_rgrps * sdp->sd_jdesc->jd_jid / journals;
1017
1018                 for (x = 0, rgd = gfs2_rgrpd_get_first(sdp); x < rg;
1019                      x++, rgd = gfs2_rgrpd_get_next(rgd))
1020                         /* Do Nothing */;
1021
1022                 sdp->sd_rindex_forward = rgd;
1023         }
1024
1025         spin_unlock(&sdp->sd_rindex_spin);
1026
1027         return rgd;
1028 }
1029
1030 /**
1031  * forward_rgrp_set - set the forward rgrp pointer
1032  * @sdp: the filesystem
1033  * @rgd: The new forward rgrp
1034  *
1035  */
1036
1037 static void forward_rgrp_set(struct gfs2_sbd *sdp, struct gfs2_rgrpd *rgd)
1038 {
1039         spin_lock(&sdp->sd_rindex_spin);
1040         sdp->sd_rindex_forward = rgd;
1041         spin_unlock(&sdp->sd_rindex_spin);
1042 }
1043
1044 /**
1045  * get_local_rgrp - Choose and lock a rgrp for allocation
1046  * @ip: the inode to reserve space for
1047  * @rgp: the chosen and locked rgrp
1048  *
1049  * Try to acquire rgrp in way which avoids contending with others.
1050  *
1051  * Returns: errno
1052  */
1053
1054 static struct inode *get_local_rgrp(struct gfs2_inode *ip, u64 *last_unlinked)
1055 {
1056         struct inode *inode = NULL;
1057         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1058         struct gfs2_rgrpd *rgd, *begin = NULL;
1059         struct gfs2_alloc *al = &ip->i_alloc;
1060         int flags = LM_FLAG_TRY;
1061         int skipped = 0;
1062         int loops = 0;
1063         int error;
1064
1065         /* Try recently successful rgrps */
1066
1067         rgd = recent_rgrp_first(sdp, ip->i_last_rg_alloc);
1068
1069         while (rgd) {
1070                 error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE,
1071                                            LM_FLAG_TRY, &al->al_rgd_gh);
1072                 switch (error) {
1073                 case 0:
1074                         if (try_rgrp_fit(rgd, al))
1075                                 goto out;
1076                         if (rgd->rd_flags & GFS2_RDF_CHECK)
1077                                 inode = try_rgrp_unlink(rgd, last_unlinked);
1078                         gfs2_glock_dq_uninit(&al->al_rgd_gh);
1079                         if (inode)
1080                                 return inode;
1081                         rgd = recent_rgrp_next(rgd, 1);
1082                         break;
1083
1084                 case GLR_TRYFAILED:
1085                         rgd = recent_rgrp_next(rgd, 0);
1086                         break;
1087
1088                 default:
1089                         return ERR_PTR(error);
1090                 }
1091         }
1092
1093         /* Go through full list of rgrps */
1094
1095         begin = rgd = forward_rgrp_get(sdp);
1096
1097         for (;;) {
1098                 error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE, flags,
1099                                           &al->al_rgd_gh);
1100                 switch (error) {
1101                 case 0:
1102                         if (try_rgrp_fit(rgd, al))
1103                                 goto out;
1104                         if (rgd->rd_flags & GFS2_RDF_CHECK)
1105                                 inode = try_rgrp_unlink(rgd, last_unlinked);
1106                         gfs2_glock_dq_uninit(&al->al_rgd_gh);
1107                         if (inode)
1108                                 return inode;
1109                         break;
1110
1111                 case GLR_TRYFAILED:
1112                         skipped++;
1113                         break;
1114
1115                 default:
1116                         return ERR_PTR(error);
1117                 }
1118
1119                 rgd = gfs2_rgrpd_get_next(rgd);
1120                 if (!rgd)
1121                         rgd = gfs2_rgrpd_get_first(sdp);
1122
1123                 if (rgd == begin) {
1124                         if (++loops >= 3)
1125                                 return ERR_PTR(-ENOSPC);
1126                         if (!skipped)
1127                                 loops++;
1128                         flags = 0;
1129                         if (loops == 2)
1130                                 gfs2_log_flush(sdp, NULL);
1131                 }
1132         }
1133
1134 out:
1135         ip->i_last_rg_alloc = rgd->rd_addr;
1136
1137         if (begin) {
1138                 recent_rgrp_add(rgd);
1139                 rgd = gfs2_rgrpd_get_next(rgd);
1140                 if (!rgd)
1141                         rgd = gfs2_rgrpd_get_first(sdp);
1142                 forward_rgrp_set(sdp, rgd);
1143         }
1144
1145         return NULL;
1146 }
1147
1148 /**
1149  * gfs2_inplace_reserve_i - Reserve space in the filesystem
1150  * @ip: the inode to reserve space for
1151  *
1152  * Returns: errno
1153  */
1154
1155 int gfs2_inplace_reserve_i(struct gfs2_inode *ip, char *file, unsigned int line)
1156 {
1157         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1158         struct gfs2_alloc *al = &ip->i_alloc;
1159         struct inode *inode;
1160         int error = 0;
1161         u64 last_unlinked = NO_BLOCK;
1162
1163         if (gfs2_assert_warn(sdp, al->al_requested))
1164                 return -EINVAL;
1165
1166 try_again:
1167         /* We need to hold the rindex unless the inode we're using is
1168            the rindex itself, in which case it's already held. */
1169         if (ip != GFS2_I(sdp->sd_rindex))
1170                 error = gfs2_rindex_hold(sdp, &al->al_ri_gh);
1171         else if (!sdp->sd_rgrps) /* We may not have the rindex read in, so: */
1172                 error = gfs2_ri_update_special(ip);
1173
1174         if (error)
1175                 return error;
1176
1177         inode = get_local_rgrp(ip, &last_unlinked);
1178         if (inode) {
1179                 if (ip != GFS2_I(sdp->sd_rindex))
1180                         gfs2_glock_dq_uninit(&al->al_ri_gh);
1181                 if (IS_ERR(inode))
1182                         return PTR_ERR(inode);
1183                 iput(inode);
1184                 gfs2_log_flush(sdp, NULL);
1185                 goto try_again;
1186         }
1187
1188         al->al_file = file;
1189         al->al_line = line;
1190
1191         return 0;
1192 }
1193
1194 /**
1195  * gfs2_inplace_release - release an inplace reservation
1196  * @ip: the inode the reservation was taken out on
1197  *
1198  * Release a reservation made by gfs2_inplace_reserve().
1199  */
1200
1201 void gfs2_inplace_release(struct gfs2_inode *ip)
1202 {
1203         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1204         struct gfs2_alloc *al = &ip->i_alloc;
1205
1206         if (gfs2_assert_warn(sdp, al->al_alloced <= al->al_requested) == -1)
1207                 fs_warn(sdp, "al_alloced = %u, al_requested = %u "
1208                              "al_file = %s, al_line = %u\n",
1209                              al->al_alloced, al->al_requested, al->al_file,
1210                              al->al_line);
1211
1212         al->al_rgd = NULL;
1213         gfs2_glock_dq_uninit(&al->al_rgd_gh);
1214         if (ip != GFS2_I(sdp->sd_rindex))
1215                 gfs2_glock_dq_uninit(&al->al_ri_gh);
1216 }
1217
1218 /**
1219  * gfs2_get_block_type - Check a block in a RG is of given type
1220  * @rgd: the resource group holding the block
1221  * @block: the block number
1222  *
1223  * Returns: The block type (GFS2_BLKST_*)
1224  */
1225
1226 unsigned char gfs2_get_block_type(struct gfs2_rgrpd *rgd, u64 block)
1227 {
1228         struct gfs2_bitmap *bi = NULL;
1229         u32 length, rgrp_block, buf_block;
1230         unsigned int buf;
1231         unsigned char type;
1232
1233         length = rgd->rd_length;
1234         rgrp_block = block - rgd->rd_data0;
1235
1236         for (buf = 0; buf < length; buf++) {
1237                 bi = rgd->rd_bits + buf;
1238                 if (rgrp_block < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1239                         break;
1240         }
1241
1242         gfs2_assert(rgd->rd_sbd, buf < length);
1243         buf_block = rgrp_block - bi->bi_start * GFS2_NBBY;
1244
1245         type = gfs2_testbit(rgd, bi->bi_bh->b_data + bi->bi_offset,
1246                            bi->bi_len, buf_block);
1247
1248         return type;
1249 }
1250
1251 /**
1252  * rgblk_search - find a block in @old_state, change allocation
1253  *           state to @new_state
1254  * @rgd: the resource group descriptor
1255  * @goal: the goal block within the RG (start here to search for avail block)
1256  * @old_state: GFS2_BLKST_XXX the before-allocation state to find
1257  * @new_state: GFS2_BLKST_XXX the after-allocation block state
1258  *
1259  * Walk rgrp's bitmap to find bits that represent a block in @old_state.
1260  * Add the found bitmap buffer to the transaction.
1261  * Set the found bits to @new_state to change block's allocation state.
1262  *
1263  * This function never fails, because we wouldn't call it unless we
1264  * know (from reservation results, etc.) that a block is available.
1265  *
1266  * Scope of @goal and returned block is just within rgrp, not the whole
1267  * filesystem.
1268  *
1269  * Returns:  the block number allocated
1270  */
1271
1272 static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
1273                         unsigned char old_state, unsigned char new_state)
1274 {
1275         struct gfs2_bitmap *bi = NULL;
1276         u32 length = rgd->rd_length;
1277         u32 blk = 0;
1278         unsigned int buf, x;
1279
1280         /* Find bitmap block that contains bits for goal block */
1281         for (buf = 0; buf < length; buf++) {
1282                 bi = rgd->rd_bits + buf;
1283                 if (goal < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1284                         break;
1285         }
1286
1287         gfs2_assert(rgd->rd_sbd, buf < length);
1288
1289         /* Convert scope of "goal" from rgrp-wide to within found bit block */
1290         goal -= bi->bi_start * GFS2_NBBY;
1291
1292         /* Search (up to entire) bitmap in this rgrp for allocatable block.
1293            "x <= length", instead of "x < length", because we typically start
1294            the search in the middle of a bit block, but if we can't find an
1295            allocatable block anywhere else, we want to be able wrap around and
1296            search in the first part of our first-searched bit block.  */
1297         for (x = 0; x <= length; x++) {
1298                 if (bi->bi_clone)
1299                         blk = gfs2_bitfit(rgd, bi->bi_clone + bi->bi_offset,
1300                                           bi->bi_len, goal, old_state);
1301                 else
1302                         blk = gfs2_bitfit(rgd,
1303                                           bi->bi_bh->b_data + bi->bi_offset,
1304                                           bi->bi_len, goal, old_state);
1305                 if (blk != BFITNOENT)
1306                         break;
1307
1308                 /* Try next bitmap block (wrap back to rgrp header if at end) */
1309                 buf = (buf + 1) % length;
1310                 bi = rgd->rd_bits + buf;
1311                 goal = 0;
1312         }
1313
1314         if (blk != BFITNOENT && old_state != new_state) {
1315                 gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1316                 gfs2_setbit(rgd, bi->bi_bh->b_data + bi->bi_offset,
1317                             bi->bi_len, blk, new_state);
1318                 if (bi->bi_clone)
1319                         gfs2_setbit(rgd, bi->bi_clone + bi->bi_offset,
1320                                     bi->bi_len, blk, new_state);
1321         }
1322
1323         return (blk == BFITNOENT) ? blk : (bi->bi_start * GFS2_NBBY) + blk;
1324 }
1325
1326 /**
1327  * rgblk_free - Change alloc state of given block(s)
1328  * @sdp: the filesystem
1329  * @bstart: the start of a run of blocks to free
1330  * @blen: the length of the block run (all must lie within ONE RG!)
1331  * @new_state: GFS2_BLKST_XXX the after-allocation block state
1332  *
1333  * Returns:  Resource group containing the block(s)
1334  */
1335
1336 static struct gfs2_rgrpd *rgblk_free(struct gfs2_sbd *sdp, u64 bstart,
1337                                      u32 blen, unsigned char new_state)
1338 {
1339         struct gfs2_rgrpd *rgd;
1340         struct gfs2_bitmap *bi = NULL;
1341         u32 length, rgrp_blk, buf_blk;
1342         unsigned int buf;
1343
1344         rgd = gfs2_blk2rgrpd(sdp, bstart);
1345         if (!rgd) {
1346                 if (gfs2_consist(sdp))
1347                         fs_err(sdp, "block = %llu\n", (unsigned long long)bstart);
1348                 return NULL;
1349         }
1350
1351         length = rgd->rd_length;
1352
1353         rgrp_blk = bstart - rgd->rd_data0;
1354
1355         while (blen--) {
1356                 for (buf = 0; buf < length; buf++) {
1357                         bi = rgd->rd_bits + buf;
1358                         if (rgrp_blk < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1359                                 break;
1360                 }
1361
1362                 gfs2_assert(rgd->rd_sbd, buf < length);
1363
1364                 buf_blk = rgrp_blk - bi->bi_start * GFS2_NBBY;
1365                 rgrp_blk++;
1366
1367                 if (!bi->bi_clone) {
1368                         bi->bi_clone = kmalloc(bi->bi_bh->b_size,
1369                                                GFP_NOFS | __GFP_NOFAIL);
1370                         memcpy(bi->bi_clone + bi->bi_offset,
1371                                bi->bi_bh->b_data + bi->bi_offset,
1372                                bi->bi_len);
1373                 }
1374                 gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1375                 gfs2_setbit(rgd, bi->bi_bh->b_data + bi->bi_offset,
1376                             bi->bi_len, buf_blk, new_state);
1377         }
1378
1379         return rgd;
1380 }
1381
1382 /**
1383  * gfs2_alloc_data - Allocate a data block
1384  * @ip: the inode to allocate the data block for
1385  *
1386  * Returns: the allocated block
1387  */
1388
1389 u64 gfs2_alloc_data(struct gfs2_inode *ip)
1390 {
1391         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1392         struct gfs2_alloc *al = &ip->i_alloc;
1393         struct gfs2_rgrpd *rgd = al->al_rgd;
1394         u32 goal, blk;
1395         u64 block;
1396
1397         if (rgrp_contains_block(rgd, ip->i_di.di_goal_data))
1398                 goal = ip->i_di.di_goal_data - rgd->rd_data0;
1399         else
1400                 goal = rgd->rd_last_alloc_data;
1401
1402         blk = rgblk_search(rgd, goal, GFS2_BLKST_FREE, GFS2_BLKST_USED);
1403         BUG_ON(blk == BFITNOENT);
1404         rgd->rd_last_alloc_data = blk;
1405
1406         block = rgd->rd_data0 + blk;
1407         ip->i_di.di_goal_data = block;
1408
1409         gfs2_assert_withdraw(sdp, rgd->rd_rg.rg_free);
1410         rgd->rd_rg.rg_free--;
1411
1412         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1413         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1414
1415         al->al_alloced++;
1416
1417         gfs2_statfs_change(sdp, 0, -1, 0);
1418         gfs2_quota_change(ip, +1, ip->i_inode.i_uid, ip->i_inode.i_gid);
1419
1420         spin_lock(&sdp->sd_rindex_spin);
1421         rgd->rd_free_clone--;
1422         spin_unlock(&sdp->sd_rindex_spin);
1423
1424         return block;
1425 }
1426
1427 /**
1428  * gfs2_alloc_meta - Allocate a metadata block
1429  * @ip: the inode to allocate the metadata block for
1430  *
1431  * Returns: the allocated block
1432  */
1433
1434 u64 gfs2_alloc_meta(struct gfs2_inode *ip)
1435 {
1436         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1437         struct gfs2_alloc *al = &ip->i_alloc;
1438         struct gfs2_rgrpd *rgd = al->al_rgd;
1439         u32 goal, blk;
1440         u64 block;
1441
1442         if (rgrp_contains_block(rgd, ip->i_di.di_goal_meta))
1443                 goal = ip->i_di.di_goal_meta - rgd->rd_data0;
1444         else
1445                 goal = rgd->rd_last_alloc_meta;
1446
1447         blk = rgblk_search(rgd, goal, GFS2_BLKST_FREE, GFS2_BLKST_USED);
1448         BUG_ON(blk == BFITNOENT);
1449         rgd->rd_last_alloc_meta = blk;
1450
1451         block = rgd->rd_data0 + blk;
1452         ip->i_di.di_goal_meta = block;
1453
1454         gfs2_assert_withdraw(sdp, rgd->rd_rg.rg_free);
1455         rgd->rd_rg.rg_free--;
1456
1457         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1458         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1459
1460         al->al_alloced++;
1461
1462         gfs2_statfs_change(sdp, 0, -1, 0);
1463         gfs2_quota_change(ip, +1, ip->i_inode.i_uid, ip->i_inode.i_gid);
1464         gfs2_trans_add_unrevoke(sdp, block);
1465
1466         spin_lock(&sdp->sd_rindex_spin);
1467         rgd->rd_free_clone--;
1468         spin_unlock(&sdp->sd_rindex_spin);
1469
1470         return block;
1471 }
1472
1473 /**
1474  * gfs2_alloc_di - Allocate a dinode
1475  * @dip: the directory that the inode is going in
1476  *
1477  * Returns: the block allocated
1478  */
1479
1480 u64 gfs2_alloc_di(struct gfs2_inode *dip, u64 *generation)
1481 {
1482         struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1483         struct gfs2_alloc *al = &dip->i_alloc;
1484         struct gfs2_rgrpd *rgd = al->al_rgd;
1485         u32 blk;
1486         u64 block;
1487
1488         blk = rgblk_search(rgd, rgd->rd_last_alloc_meta,
1489                            GFS2_BLKST_FREE, GFS2_BLKST_DINODE);
1490         BUG_ON(blk == BFITNOENT);
1491
1492         rgd->rd_last_alloc_meta = blk;
1493
1494         block = rgd->rd_data0 + blk;
1495
1496         gfs2_assert_withdraw(sdp, rgd->rd_rg.rg_free);
1497         rgd->rd_rg.rg_free--;
1498         rgd->rd_rg.rg_dinodes++;
1499         *generation = rgd->rd_rg.rg_igeneration++;
1500         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1501         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1502
1503         al->al_alloced++;
1504
1505         gfs2_statfs_change(sdp, 0, -1, +1);
1506         gfs2_trans_add_unrevoke(sdp, block);
1507
1508         spin_lock(&sdp->sd_rindex_spin);
1509         rgd->rd_free_clone--;
1510         spin_unlock(&sdp->sd_rindex_spin);
1511
1512         return block;
1513 }
1514
1515 /**
1516  * gfs2_free_data - free a contiguous run of data block(s)
1517  * @ip: the inode these blocks are being freed from
1518  * @bstart: first block of a run of contiguous blocks
1519  * @blen: the length of the block run
1520  *
1521  */
1522
1523 void gfs2_free_data(struct gfs2_inode *ip, u64 bstart, u32 blen)
1524 {
1525         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1526         struct gfs2_rgrpd *rgd;
1527
1528         rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
1529         if (!rgd)
1530                 return;
1531
1532         rgd->rd_rg.rg_free += blen;
1533
1534         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1535         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1536
1537         gfs2_trans_add_rg(rgd);
1538
1539         gfs2_statfs_change(sdp, 0, +blen, 0);
1540         gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
1541 }
1542
1543 /**
1544  * gfs2_free_meta - free a contiguous run of data block(s)
1545  * @ip: the inode these blocks are being freed from
1546  * @bstart: first block of a run of contiguous blocks
1547  * @blen: the length of the block run
1548  *
1549  */
1550
1551 void gfs2_free_meta(struct gfs2_inode *ip, u64 bstart, u32 blen)
1552 {
1553         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1554         struct gfs2_rgrpd *rgd;
1555
1556         rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
1557         if (!rgd)
1558                 return;
1559
1560         rgd->rd_rg.rg_free += blen;
1561
1562         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1563         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1564
1565         gfs2_trans_add_rg(rgd);
1566
1567         gfs2_statfs_change(sdp, 0, +blen, 0);
1568         gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
1569         gfs2_meta_wipe(ip, bstart, blen);
1570 }
1571
1572 void gfs2_unlink_di(struct inode *inode)
1573 {
1574         struct gfs2_inode *ip = GFS2_I(inode);
1575         struct gfs2_sbd *sdp = GFS2_SB(inode);
1576         struct gfs2_rgrpd *rgd;
1577         u64 blkno = ip->i_no_addr;
1578
1579         rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_UNLINKED);
1580         if (!rgd)
1581                 return;
1582         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1583         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1584         gfs2_trans_add_rg(rgd);
1585 }
1586
1587 static void gfs2_free_uninit_di(struct gfs2_rgrpd *rgd, u64 blkno)
1588 {
1589         struct gfs2_sbd *sdp = rgd->rd_sbd;
1590         struct gfs2_rgrpd *tmp_rgd;
1591
1592         tmp_rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_FREE);
1593         if (!tmp_rgd)
1594                 return;
1595         gfs2_assert_withdraw(sdp, rgd == tmp_rgd);
1596
1597         if (!rgd->rd_rg.rg_dinodes)
1598                 gfs2_consist_rgrpd(rgd);
1599         rgd->rd_rg.rg_dinodes--;
1600         rgd->rd_rg.rg_free++;
1601
1602         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1603         gfs2_rgrp_out(&rgd->rd_rg, rgd->rd_bits[0].bi_bh->b_data);
1604
1605         gfs2_statfs_change(sdp, 0, +1, -1);
1606         gfs2_trans_add_rg(rgd);
1607 }
1608
1609
1610 void gfs2_free_di(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip)
1611 {
1612         gfs2_free_uninit_di(rgd, ip->i_no_addr);
1613         gfs2_quota_change(ip, -1, ip->i_inode.i_uid, ip->i_inode.i_gid);
1614         gfs2_meta_wipe(ip, ip->i_no_addr, 1);
1615 }
1616
1617 /**
1618  * gfs2_rlist_add - add a RG to a list of RGs
1619  * @sdp: the filesystem
1620  * @rlist: the list of resource groups
1621  * @block: the block
1622  *
1623  * Figure out what RG a block belongs to and add that RG to the list
1624  *
1625  * FIXME: Don't use NOFAIL
1626  *
1627  */
1628
1629 void gfs2_rlist_add(struct gfs2_sbd *sdp, struct gfs2_rgrp_list *rlist,
1630                     u64 block)
1631 {
1632         struct gfs2_rgrpd *rgd;
1633         struct gfs2_rgrpd **tmp;
1634         unsigned int new_space;
1635         unsigned int x;
1636
1637         if (gfs2_assert_warn(sdp, !rlist->rl_ghs))
1638                 return;
1639
1640         rgd = gfs2_blk2rgrpd(sdp, block);
1641         if (!rgd) {
1642                 if (gfs2_consist(sdp))
1643                         fs_err(sdp, "block = %llu\n", (unsigned long long)block);
1644                 return;
1645         }
1646
1647         for (x = 0; x < rlist->rl_rgrps; x++)
1648                 if (rlist->rl_rgd[x] == rgd)
1649                         return;
1650
1651         if (rlist->rl_rgrps == rlist->rl_space) {
1652                 new_space = rlist->rl_space + 10;
1653
1654                 tmp = kcalloc(new_space, sizeof(struct gfs2_rgrpd *),
1655                               GFP_NOFS | __GFP_NOFAIL);
1656
1657                 if (rlist->rl_rgd) {
1658                         memcpy(tmp, rlist->rl_rgd,
1659                                rlist->rl_space * sizeof(struct gfs2_rgrpd *));
1660                         kfree(rlist->rl_rgd);
1661                 }
1662
1663                 rlist->rl_space = new_space;
1664                 rlist->rl_rgd = tmp;
1665         }
1666
1667         rlist->rl_rgd[rlist->rl_rgrps++] = rgd;
1668 }
1669
1670 /**
1671  * gfs2_rlist_alloc - all RGs have been added to the rlist, now allocate
1672  *      and initialize an array of glock holders for them
1673  * @rlist: the list of resource groups
1674  * @state: the lock state to acquire the RG lock in
1675  * @flags: the modifier flags for the holder structures
1676  *
1677  * FIXME: Don't use NOFAIL
1678  *
1679  */
1680
1681 void gfs2_rlist_alloc(struct gfs2_rgrp_list *rlist, unsigned int state,
1682                       int flags)
1683 {
1684         unsigned int x;
1685
1686         rlist->rl_ghs = kcalloc(rlist->rl_rgrps, sizeof(struct gfs2_holder),
1687                                 GFP_NOFS | __GFP_NOFAIL);
1688         for (x = 0; x < rlist->rl_rgrps; x++)
1689                 gfs2_holder_init(rlist->rl_rgd[x]->rd_gl,
1690                                 state, flags,
1691                                 &rlist->rl_ghs[x]);
1692 }
1693
1694 /**
1695  * gfs2_rlist_free - free a resource group list
1696  * @list: the list of resource groups
1697  *
1698  */
1699
1700 void gfs2_rlist_free(struct gfs2_rgrp_list *rlist)
1701 {
1702         unsigned int x;
1703
1704         kfree(rlist->rl_rgd);
1705
1706         if (rlist->rl_ghs) {
1707                 for (x = 0; x < rlist->rl_rgrps; x++)
1708                         gfs2_holder_uninit(&rlist->rl_ghs[x]);
1709                 kfree(rlist->rl_ghs);
1710         }
1711 }
1712