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