rgrp.c 62.9 KB
Newer Older
David Teigland's avatar
David Teigland committed
1
2
/*
 * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
3
 * Copyright (C) 2004-2008 Red Hat, Inc.  All rights reserved.
David Teigland's avatar
David Teigland committed
4
5
6
 *
 * This copyrighted material is made available to anyone wishing to use,
 * modify, copy, or redistribute it subject to the terms and conditions
7
 * of the GNU General Public License version 2.
David Teigland's avatar
David Teigland committed
8
9
10
11
12
13
 */

#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/completion.h>
#include <linux/buffer_head.h>
14
#include <linux/fs.h>
15
#include <linux/gfs2_ondisk.h>
16
#include <linux/prefetch.h>
17
#include <linux/blkdev.h>
18
#include <linux/rbtree.h>
Steven Whitehouse's avatar
Steven Whitehouse committed
19
#include <linux/random.h>
David Teigland's avatar
David Teigland committed
20
21

#include "gfs2.h"
22
#include "incore.h"
David Teigland's avatar
David Teigland committed
23
24
25
26
27
28
29
30
#include "glock.h"
#include "glops.h"
#include "lops.h"
#include "meta_io.h"
#include "quota.h"
#include "rgrp.h"
#include "super.h"
#include "trans.h"
31
#include "util.h"
32
#include "log.h"
33
#include "inode.h"
Steven Whitehouse's avatar
Steven Whitehouse committed
34
#include "trace_gfs2.h"
David Teigland's avatar
David Teigland committed
35

Steven Whitehouse's avatar
Steven Whitehouse committed
36
#define BFITNOENT ((u32)~0)
37
#define NO_BLOCK ((u64)~0)
38

39
40
41
42
43
44
45
46
47
48
#if BITS_PER_LONG == 32
#define LBITMASK   (0x55555555UL)
#define LBITSKIP55 (0x55555555UL)
#define LBITSKIP00 (0x00000000UL)
#else
#define LBITMASK   (0x5555555555555555UL)
#define LBITSKIP55 (0x5555555555555555UL)
#define LBITSKIP00 (0x0000000000000000UL)
#endif

49
50
51
/*
 * These routines are used by the resource group routines (rgrp.c)
 * to keep track of block allocation.  Each block is represented by two
52
53
54
55
56
57
 * bits.  So, each byte represents GFS2_NBBY (i.e. 4) blocks.
 *
 * 0 = Free
 * 1 = Used (not metadata)
 * 2 = Unlinked (still in use) inode
 * 3 = Used (metadata)
58
59
60
61
 */

static const char valid_change[16] = {
	        /* current */
62
	/* n */ 0, 1, 1, 1,
63
	/* e */ 1, 0, 0, 0,
64
	/* w */ 0, 0, 0, 1,
65
66
67
	        1, 0, 0, 0
};

68
69
70
71
static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 minext,
                         const struct gfs2_inode *ip, bool nowrap);


72
73
/**
 * gfs2_setbit - Set a bit in the bitmaps
74
75
 * @rbm: The position of the bit to set
 * @do_clone: Also set the clone bitmap, if it exists
76
77
78
79
 * @new_state: the new state of the block
 *
 */

80
static inline void gfs2_setbit(const struct gfs2_rbm *rbm, bool do_clone,
81
			       unsigned char new_state)
82
{
83
	unsigned char *byte1, *byte2, *end, cur_state;
84
85
	unsigned int buflen = rbm->bi->bi_len;
	const unsigned int bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
86

87
88
	byte1 = rbm->bi->bi_bh->b_data + rbm->bi->bi_offset + (rbm->offset / GFS2_NBBY);
	end = rbm->bi->bi_bh->b_data + rbm->bi->bi_offset + buflen;
89

90
	BUG_ON(byte1 >= end);
91

92
	cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
93

94
	if (unlikely(!valid_change[new_state * 4 + cur_state])) {
95
96
97
98
99
100
101
		printk(KERN_WARNING "GFS2: buf_blk = 0x%x old_state=%d, "
		       "new_state=%d\n", rbm->offset, cur_state, new_state);
		printk(KERN_WARNING "GFS2: rgrp=0x%llx bi_start=0x%x\n",
		       (unsigned long long)rbm->rgd->rd_addr,
		       rbm->bi->bi_start);
		printk(KERN_WARNING "GFS2: bi_offset=0x%x bi_len=0x%x\n",
		       rbm->bi->bi_offset, rbm->bi->bi_len);
102
		dump_stack();
103
		gfs2_consist_rgrpd(rbm->rgd);
104
105
106
107
		return;
	}
	*byte1 ^= (cur_state ^ new_state) << bit;

108
109
	if (do_clone && rbm->bi->bi_clone) {
		byte2 = rbm->bi->bi_clone + rbm->bi->bi_offset + (rbm->offset / GFS2_NBBY);
110
111
112
		cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
		*byte2 ^= (cur_state ^ new_state) << bit;
	}
113
114
115
116
}

/**
 * gfs2_testbit - test a bit in the bitmaps
117
 * @rbm: The bit to test
118
 *
119
 * Returns: The two bit block state of the requested bit
120
121
 */

122
static inline u8 gfs2_testbit(const struct gfs2_rbm *rbm)
123
{
124
125
	const u8 *buffer = rbm->bi->bi_bh->b_data + rbm->bi->bi_offset;
	const u8 *byte;
126
127
	unsigned int bit;

128
129
	byte = buffer + (rbm->offset / GFS2_NBBY);
	bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
130

131
	return (*byte >> bit) & GFS2_BIT_MASK;
132
133
}

134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/**
 * gfs2_bit_search
 * @ptr: Pointer to bitmap data
 * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
 * @state: The state we are searching for
 *
 * We xor the bitmap data with a patter which is the bitwise opposite
 * of what we are looking for, this gives rise to a pattern of ones
 * wherever there is a match. Since we have two bits per entry, we
 * take this pattern, shift it down by one place and then and it with
 * the original. All the even bit positions (0,2,4, etc) then represent
 * successful matches, so we mask with 0x55555..... to remove the unwanted
 * odd bit positions.
 *
 * This allows searching of a whole u64 at once (32 blocks) with a
 * single test (on 64 bit arches).
 */

static inline u64 gfs2_bit_search(const __le64 *ptr, u64 mask, u8 state)
{
	u64 tmp;
	static const u64 search[] = {
156
157
158
159
		[0] = 0xffffffffffffffffULL,
		[1] = 0xaaaaaaaaaaaaaaaaULL,
		[2] = 0x5555555555555555ULL,
		[3] = 0x0000000000000000ULL,
160
161
162
163
164
165
166
	};
	tmp = le64_to_cpu(*ptr) ^ search[state];
	tmp &= (tmp >> 1);
	tmp &= mask;
	return tmp;
}

Bob Peterson's avatar
Bob Peterson committed
167
168
169
170
171
172
173
174
175
176
177
178
/**
 * rs_cmp - multi-block reservation range compare
 * @blk: absolute file system block number of the new reservation
 * @len: number of blocks in the new reservation
 * @rs: existing reservation to compare against
 *
 * returns: 1 if the block range is beyond the reach of the reservation
 *         -1 if the block range is before the start of the reservation
 *          0 if the block range overlaps with the reservation
 */
static inline int rs_cmp(u64 blk, u32 len, struct gfs2_blkreserv *rs)
{
179
	u64 startblk = gfs2_rbm_to_block(&rs->rs_rbm);
Bob Peterson's avatar
Bob Peterson committed
180
181
182
183
184
185
186
187

	if (blk >= startblk + rs->rs_free)
		return 1;
	if (blk + len - 1 < startblk)
		return -1;
	return 0;
}

188
189
190
/**
 * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
 *       a block in a given allocation state.
191
 * @buf: the buffer that holds the bitmaps
192
 * @len: the length (in bytes) of the buffer
193
 * @goal: start search at this block's bit-pair (within @buffer)
194
 * @state: GFS2_BLKST_XXX the state of the block we're looking for.
195
196
197
 *
 * Scope of @goal and returned block number is only within this bitmap buffer,
 * not entire rgrp or filesystem.  @buffer will be offset from the actual
198
199
200
201
202
 * beginning of a bitmap block buffer, skipping any header structures, but
 * headers are always a multiple of 64 bits long so that the buffer is
 * always aligned to a 64 bit boundary.
 *
 * The size of the buffer is in bytes, but is it assumed that it is
203
 * always ok to read a complete multiple of 64 bits at the end
204
 * of the block in case the end is no aligned to a natural boundary.
205
206
207
208
 *
 * Return: the block number (bitmap buffer scope) that was found
 */

209
210
static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
		       u32 goal, u8 state)
211
{
212
213
214
215
	u32 spoint = (goal << 1) & ((8*sizeof(u64)) - 1);
	const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
	const __le64 *end = (__le64 *)(buf + ALIGN(len, sizeof(u64)));
	u64 tmp;
216
	u64 mask = 0x5555555555555555ULL;
217
218
219
220
221
222
223
	u32 bit;

	/* Mask off bits we don't care about at the start of the search */
	mask <<= spoint;
	tmp = gfs2_bit_search(ptr, mask, state);
	ptr++;
	while(tmp == 0 && ptr < end) {
224
		tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
225
		ptr++;
226
	}
227
228
229
230
231
232
233
	/* Mask off any bits which are more than len bytes from the start */
	if (ptr == end && (len & (sizeof(u64) - 1)))
		tmp &= (((u64)~0) >> (64 - 8*(len & (sizeof(u64) - 1))));
	/* Didn't find anything, so return */
	if (tmp == 0)
		return BFITNOENT;
	ptr--;
234
	bit = __ffs64(tmp);
235
236
	bit /= 2;	/* two bits per entry in the bitmap */
	return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
237
238
}

239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
/**
 * gfs2_rbm_from_block - Set the rbm based upon rgd and block number
 * @rbm: The rbm with rgd already set correctly
 * @block: The block number (filesystem relative)
 *
 * This sets the bi and offset members of an rbm based on a
 * resource group and a filesystem relative block number. The
 * resource group must be set in the rbm on entry, the bi and
 * offset members will be set by this function.
 *
 * Returns: 0 on success, or an error code
 */

static int gfs2_rbm_from_block(struct gfs2_rbm *rbm, u64 block)
{
	u64 rblock = block - rbm->rgd->rd_data0;
255
	u32 x;
256
257
258
259
260
261

	if (WARN_ON_ONCE(rblock > UINT_MAX))
		return -EINVAL;
	if (block >= rbm->rgd->rd_data0 + rbm->rgd->rd_data)
		return -E2BIG;

262
263
264
265
266
267
268
269
270
271
272
273
	rbm->bi = rbm->rgd->rd_bits;
	rbm->offset = (u32)(rblock);
	/* Check if the block is within the first block */
	if (rbm->offset < (rbm->bi->bi_start + rbm->bi->bi_len) * GFS2_NBBY)
		return 0;

	/* Adjust for the size diff between gfs2_meta_header and gfs2_rgrp */
	rbm->offset += (sizeof(struct gfs2_rgrp) -
			sizeof(struct gfs2_meta_header)) * GFS2_NBBY;
	x = rbm->offset / rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
	rbm->offset -= x * rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
	rbm->bi += x;
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
	return 0;
}

/**
 * gfs2_unaligned_extlen - Look for free blocks which are not byte aligned
 * @rbm: Position to search (value/result)
 * @n_unaligned: Number of unaligned blocks to check
 * @len: Decremented for each block found (terminate on zero)
 *
 * Returns: true if a non-free block is encountered
 */

static bool gfs2_unaligned_extlen(struct gfs2_rbm *rbm, u32 n_unaligned, u32 *len)
{
	u64 block;
	u32 n;
	u8 res;

	for (n = 0; n < n_unaligned; n++) {
		res = gfs2_testbit(rbm);
		if (res != GFS2_BLKST_FREE)
			return true;
		(*len)--;
		if (*len == 0)
			return true;
		block = gfs2_rbm_to_block(rbm);
		if (gfs2_rbm_from_block(rbm, block + 1))
			return true;
	}

	return false;
}

/**
 * gfs2_free_extlen - Return extent length of free blocks
 * @rbm: Starting position
 * @len: Max length to check
 *
 * Starting at the block specified by the rbm, see how many free blocks
 * there are, not reading more than len blocks ahead. This can be done
 * using memchr_inv when the blocks are byte aligned, but has to be done
 * on a block by block basis in case of unaligned blocks. Also this
 * function can cope with bitmap boundaries (although it must stop on
 * a resource group boundary)
 *
 * Returns: Number of free blocks in the extent
 */

static u32 gfs2_free_extlen(const struct gfs2_rbm *rrbm, u32 len)
{
	struct gfs2_rbm rbm = *rrbm;
	u32 n_unaligned = rbm.offset & 3;
	u32 size = len;
	u32 bytes;
	u32 chunk_size;
	u8 *ptr, *start, *end;
	u64 block;

	if (n_unaligned &&
	    gfs2_unaligned_extlen(&rbm, 4 - n_unaligned, &len))
		goto out;

336
	n_unaligned = len & 3;
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
	/* Start is now byte aligned */
	while (len > 3) {
		start = rbm.bi->bi_bh->b_data;
		if (rbm.bi->bi_clone)
			start = rbm.bi->bi_clone;
		end = start + rbm.bi->bi_bh->b_size;
		start += rbm.bi->bi_offset;
		BUG_ON(rbm.offset & 3);
		start += (rbm.offset / GFS2_NBBY);
		bytes = min_t(u32, len / GFS2_NBBY, (end - start));
		ptr = memchr_inv(start, 0, bytes);
		chunk_size = ((ptr == NULL) ? bytes : (ptr - start));
		chunk_size *= GFS2_NBBY;
		BUG_ON(len < chunk_size);
		len -= chunk_size;
		block = gfs2_rbm_to_block(&rbm);
353
354
		if (gfs2_rbm_from_block(&rbm, block + chunk_size)) {
			n_unaligned = 0;
355
			break;
356
357
358
359
360
		}
		if (ptr) {
			n_unaligned = 3;
			break;
		}
361
362
363
364
365
366
367
368
369
370
		n_unaligned = len & 3;
	}

	/* Deal with any bits left over at the end */
	if (n_unaligned)
		gfs2_unaligned_extlen(&rbm, n_unaligned, &len);
out:
	return size - len;
}

371
372
/**
 * gfs2_bitcount - count the number of bits in a certain state
373
 * @rgd: the resource group descriptor
374
375
376
377
378
379
380
 * @buffer: the buffer that holds the bitmaps
 * @buflen: the length (in bytes) of the buffer
 * @state: the state of the block we're looking for
 *
 * Returns: The number of bits
 */

381
382
static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
			 unsigned int buflen, u8 state)
383
{
384
385
386
387
388
	const u8 *byte = buffer;
	const u8 *end = buffer + buflen;
	const u8 state1 = state << 2;
	const u8 state2 = state << 4;
	const u8 state3 = state << 6;
389
	u32 count = 0;
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404

	for (; byte < end; byte++) {
		if (((*byte) & 0x03) == state)
			count++;
		if (((*byte) & 0x0C) == state1)
			count++;
		if (((*byte) & 0x30) == state2)
			count++;
		if (((*byte) & 0xC0) == state3)
			count++;
	}

	return count;
}

David Teigland's avatar
David Teigland committed
405
406
407
408
409
410
411
412
413
414
/**
 * gfs2_rgrp_verify - Verify that a resource group is consistent
 * @rgd: the rgrp
 *
 */

void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
{
	struct gfs2_sbd *sdp = rgd->rd_sbd;
	struct gfs2_bitmap *bi = NULL;
415
	u32 length = rgd->rd_length;
416
	u32 count[4], tmp;
David Teigland's avatar
David Teigland committed
417
418
	int buf, x;

419
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
420
421
422
423
424
425
426
427
428
429
430

	/* Count # blocks in each of 4 possible allocation states */
	for (buf = 0; buf < length; buf++) {
		bi = rgd->rd_bits + buf;
		for (x = 0; x < 4; x++)
			count[x] += gfs2_bitcount(rgd,
						  bi->bi_bh->b_data +
						  bi->bi_offset,
						  bi->bi_len, x);
	}

431
	if (count[0] != rgd->rd_free) {
David Teigland's avatar
David Teigland committed
432
433
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "free data mismatch:  %u != %u\n",
434
			       count[0], rgd->rd_free);
David Teigland's avatar
David Teigland committed
435
436
437
		return;
	}

438
	tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
439
	if (count[1] != tmp) {
David Teigland's avatar
David Teigland committed
440
441
442
443
444
445
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "used data mismatch:  %u != %u\n",
			       count[1], tmp);
		return;
	}

446
	if (count[2] + count[3] != rgd->rd_dinodes) {
David Teigland's avatar
David Teigland committed
447
		if (gfs2_consist_rgrpd(rgd))
448
			fs_err(sdp, "used metadata mismatch:  %u != %u\n",
449
			       count[2] + count[3], rgd->rd_dinodes);
David Teigland's avatar
David Teigland committed
450
451
452
453
		return;
	}
}

454
static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
David Teigland's avatar
David Teigland committed
455
{
456
457
	u64 first = rgd->rd_data0;
	u64 last = first + rgd->rd_data;
458
	return first <= block && block < last;
David Teigland's avatar
David Teigland committed
459
460
461
462
463
}

/**
 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 * @sdp: The GFS2 superblock
464
465
 * @blk: The data block number
 * @exact: True if this needs to be an exact match
David Teigland's avatar
David Teigland committed
466
467
468
469
 *
 * Returns: The resource group, or NULL if not found
 */

Steven Whitehouse's avatar
Steven Whitehouse committed
470
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
471
{
Steven Whitehouse's avatar
Steven Whitehouse committed
472
	struct rb_node *n, *next;
473
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
474
475

	spin_lock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
476
477
478
479
	n = sdp->sd_rindex_tree.rb_node;
	while (n) {
		cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
		next = NULL;
480
		if (blk < cur->rd_addr)
Steven Whitehouse's avatar
Steven Whitehouse committed
481
			next = n->rb_left;
482
		else if (blk >= cur->rd_data0 + cur->rd_data)
Steven Whitehouse's avatar
Steven Whitehouse committed
483
484
			next = n->rb_right;
		if (next == NULL) {
David Teigland's avatar
David Teigland committed
485
			spin_unlock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
486
487
488
489
490
491
			if (exact) {
				if (blk < cur->rd_addr)
					return NULL;
				if (blk >= cur->rd_data0 + cur->rd_data)
					return NULL;
			}
492
			return cur;
David Teigland's avatar
David Teigland committed
493
		}
Steven Whitehouse's avatar
Steven Whitehouse committed
494
		n = next;
David Teigland's avatar
David Teigland committed
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
	}
	spin_unlock(&sdp->sd_rindex_spin);

	return NULL;
}

/**
 * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
 * @sdp: The GFS2 superblock
 *
 * Returns: The first rgrp in the filesystem
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
{
510
511
512
	const struct rb_node *n;
	struct gfs2_rgrpd *rgd;

513
	spin_lock(&sdp->sd_rindex_spin);
514
515
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
516
	spin_unlock(&sdp->sd_rindex_spin);
517
518

	return rgd;
David Teigland's avatar
David Teigland committed
519
520
521
522
}

/**
 * gfs2_rgrpd_get_next - get the next RG
523
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
524
525
526
527
528
529
 *
 * Returns: The next rgrp
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
{
530
531
532
533
534
535
536
537
538
539
	struct gfs2_sbd *sdp = rgd->rd_sbd;
	const struct rb_node *n;

	spin_lock(&sdp->sd_rindex_spin);
	n = rb_next(&rgd->rd_node);
	if (n == NULL)
		n = rb_first(&sdp->sd_rindex_tree);

	if (unlikely(&rgd->rd_node == n)) {
		spin_unlock(&sdp->sd_rindex_spin);
David Teigland's avatar
David Teigland committed
540
		return NULL;
541
542
543
544
	}
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
	spin_unlock(&sdp->sd_rindex_spin);
	return rgd;
David Teigland's avatar
David Teigland committed
545
546
}

547
548
549
550
551
552
553
554
555
556
557
void gfs2_free_clones(struct gfs2_rgrpd *rgd)
{
	int x;

	for (x = 0; x < rgd->rd_length; x++) {
		struct gfs2_bitmap *bi = rgd->rd_bits + x;
		kfree(bi->bi_clone);
		bi->bi_clone = NULL;
	}
}

558
559
560
561
562
563
/**
 * gfs2_rs_alloc - make sure we have a reservation assigned to the inode
 * @ip: the inode for this reservation
 */
int gfs2_rs_alloc(struct gfs2_inode *ip)
{
Abhijith Das's avatar
Abhijith Das committed
564
	int error = 0;
Bob Peterson's avatar
Bob Peterson committed
565

Abhijith Das's avatar
Abhijith Das committed
566
	down_write(&ip->i_rw_mutex);
Bob Peterson's avatar
Bob Peterson committed
567
	if (ip->i_res)
Abhijith Das's avatar
Abhijith Das committed
568
		goto out;
569

Abhijith Das's avatar
Abhijith Das committed
570
571
572
573
574
	ip->i_res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!ip->i_res) {
		error = -ENOMEM;
		goto out;
	}
575

Abhijith Das's avatar
Abhijith Das committed
576
577
	RB_CLEAR_NODE(&ip->i_res->rs_node);
out:
578
	up_write(&ip->i_rw_mutex);
579
	return 0;
580
581
}

582
static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
583
{
584
585
586
	gfs2_print_dbg(seq, "  B: n:%llu s:%llu b:%u f:%u\n",
		       (unsigned long long)rs->rs_inum,
		       (unsigned long long)gfs2_rbm_to_block(&rs->rs_rbm),
587
		       rs->rs_rbm.offset, rs->rs_free);
Bob Peterson's avatar
Bob Peterson committed
588
589
}

590
/**
Bob Peterson's avatar
Bob Peterson committed
591
592
593
594
 * __rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
595
static void __rs_deltree(struct gfs2_inode *ip, struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
596
597
598
599
600
601
{
	struct gfs2_rgrpd *rgd;

	if (!gfs2_rs_active(rs))
		return;

602
	rgd = rs->rs_rbm.rgd;
603
	trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
604
	rb_erase(&rs->rs_node, &rgd->rd_rstree);
605
	RB_CLEAR_NODE(&rs->rs_node);
Bob Peterson's avatar
Bob Peterson committed
606
607
608

	if (rs->rs_free) {
		/* return reserved blocks to the rgrp and the ip */
609
610
		BUG_ON(rs->rs_rbm.rgd->rd_reserved < rs->rs_free);
		rs->rs_rbm.rgd->rd_reserved -= rs->rs_free;
Bob Peterson's avatar
Bob Peterson committed
611
		rs->rs_free = 0;
612
		clear_bit(GBF_FULL, &rs->rs_rbm.bi->bi_flags);
Bob Peterson's avatar
Bob Peterson committed
613
614
615
616
617
618
619
620
621
		smp_mb__after_clear_bit();
	}
}

/**
 * gfs2_rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
622
void gfs2_rs_deltree(struct gfs2_inode *ip, struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
623
624
625
{
	struct gfs2_rgrpd *rgd;

626
627
628
629
630
631
	rgd = rs->rs_rbm.rgd;
	if (rgd) {
		spin_lock(&rgd->rd_rsspin);
		__rs_deltree(ip, rs);
		spin_unlock(&rgd->rd_rsspin);
	}
Bob Peterson's avatar
Bob Peterson committed
632
633
634
635
}

/**
 * gfs2_rs_delete - delete a multi-block reservation
636
637
638
639
640
641
642
 * @ip: The inode for this reservation
 *
 */
void gfs2_rs_delete(struct gfs2_inode *ip)
{
	down_write(&ip->i_rw_mutex);
	if (ip->i_res) {
643
		gfs2_rs_deltree(ip, ip->i_res);
Bob Peterson's avatar
Bob Peterson committed
644
		BUG_ON(ip->i_res->rs_free);
645
646
647
648
649
650
		kmem_cache_free(gfs2_rsrv_cachep, ip->i_res);
		ip->i_res = NULL;
	}
	up_write(&ip->i_rw_mutex);
}

Bob Peterson's avatar
Bob Peterson committed
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
/**
 * return_all_reservations - return all reserved blocks back to the rgrp.
 * @rgd: the rgrp that needs its space back
 *
 * We previously reserved a bunch of blocks for allocation. Now we need to
 * give them back. This leave the reservation structures in tact, but removes
 * all of their corresponding "no-fly zones".
 */
static void return_all_reservations(struct gfs2_rgrpd *rgd)
{
	struct rb_node *n;
	struct gfs2_blkreserv *rs;

	spin_lock(&rgd->rd_rsspin);
	while ((n = rb_first(&rgd->rd_rstree))) {
		rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
667
		__rs_deltree(NULL, rs);
Bob Peterson's avatar
Bob Peterson committed
668
669
670
671
	}
	spin_unlock(&rgd->rd_rsspin);
}

672
void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
673
{
674
	struct rb_node *n;
David Teigland's avatar
David Teigland committed
675
676
677
	struct gfs2_rgrpd *rgd;
	struct gfs2_glock *gl;

678
679
	while ((n = rb_first(&sdp->sd_rindex_tree))) {
		rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
David Teigland's avatar
David Teigland committed
680
681
		gl = rgd->rd_gl;

682
		rb_erase(n, &sdp->sd_rindex_tree);
David Teigland's avatar
David Teigland committed
683
684

		if (gl) {
685
			spin_lock(&gl->gl_spin);
686
			gl->gl_object = NULL;
687
			spin_unlock(&gl->gl_spin);
688
			gfs2_glock_add_to_lru(gl);
David Teigland's avatar
David Teigland committed
689
690
691
			gfs2_glock_put(gl);
		}

692
		gfs2_free_clones(rgd);
David Teigland's avatar
David Teigland committed
693
		kfree(rgd->rd_bits);
Bob Peterson's avatar
Bob Peterson committed
694
		return_all_reservations(rgd);
695
		kmem_cache_free(gfs2_rgrpd_cachep, rgd);
David Teigland's avatar
David Teigland committed
696
697
698
	}
}

699
700
701
702
703
704
705
706
707
static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
{
	printk(KERN_INFO "  ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
	printk(KERN_INFO "  ri_length = %u\n", rgd->rd_length);
	printk(KERN_INFO "  ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
	printk(KERN_INFO "  ri_data = %u\n", rgd->rd_data);
	printk(KERN_INFO "  ri_bitbytes = %u\n", rgd->rd_bitbytes);
}

David Teigland's avatar
David Teigland committed
708
709
710
711
712
713
714
715
716
717
718
719
720
/**
 * gfs2_compute_bitstructs - Compute the bitmap sizes
 * @rgd: The resource group descriptor
 *
 * Calculates bitmap descriptors, one for each block that contains bitmap data
 *
 * Returns: errno
 */

static int compute_bitstructs(struct gfs2_rgrpd *rgd)
{
	struct gfs2_sbd *sdp = rgd->rd_sbd;
	struct gfs2_bitmap *bi;
721
	u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
722
	u32 bytes_left, bytes;
David Teigland's avatar
David Teigland committed
723
724
	int x;

725
726
727
	if (!length)
		return -EINVAL;

728
	rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
David Teigland's avatar
David Teigland committed
729
730
731
	if (!rgd->rd_bits)
		return -ENOMEM;

732
	bytes_left = rgd->rd_bitbytes;
David Teigland's avatar
David Teigland committed
733
734
735
736

	for (x = 0; x < length; x++) {
		bi = rgd->rd_bits + x;

737
		bi->bi_flags = 0;
David Teigland's avatar
David Teigland committed
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
		/* small rgrp; bitmap stored completely in header block */
		if (length == 1) {
			bytes = bytes_left;
			bi->bi_offset = sizeof(struct gfs2_rgrp);
			bi->bi_start = 0;
			bi->bi_len = bytes;
		/* header block */
		} else if (x == 0) {
			bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
			bi->bi_offset = sizeof(struct gfs2_rgrp);
			bi->bi_start = 0;
			bi->bi_len = bytes;
		/* last block */
		} else if (x + 1 == length) {
			bytes = bytes_left;
			bi->bi_offset = sizeof(struct gfs2_meta_header);
754
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
755
756
757
			bi->bi_len = bytes;
		/* other blocks */
		} else {
758
759
			bytes = sdp->sd_sb.sb_bsize -
				sizeof(struct gfs2_meta_header);
David Teigland's avatar
David Teigland committed
760
			bi->bi_offset = sizeof(struct gfs2_meta_header);
761
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
762
763
764
765
766
767
768
769
770
771
772
			bi->bi_len = bytes;
		}

		bytes_left -= bytes;
	}

	if (bytes_left) {
		gfs2_consist_rgrpd(rgd);
		return -EIO;
	}
	bi = rgd->rd_bits + (length - 1);
773
	if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
David Teigland's avatar
David Teigland committed
774
		if (gfs2_consist_rgrpd(rgd)) {
775
			gfs2_rindex_print(rgd);
David Teigland's avatar
David Teigland committed
776
777
778
779
780
781
782
783
784
			fs_err(sdp, "start=%u len=%u offset=%u\n",
			       bi->bi_start, bi->bi_len, bi->bi_offset);
		}
		return -EIO;
	}

	return 0;
}

785
786
/**
 * gfs2_ri_total - Total up the file system space, according to the rindex.
787
 * @sdp: the filesystem
788
789
790
791
792
793
794
795
796
797
798
799
800
 *
 */
u64 gfs2_ri_total(struct gfs2_sbd *sdp)
{
	u64 total_data = 0;	
	struct inode *inode = sdp->sd_rindex;
	struct gfs2_inode *ip = GFS2_I(inode);
	char buf[sizeof(struct gfs2_rindex)];
	int error, rgrps;

	for (rgrps = 0;; rgrps++) {
		loff_t pos = rgrps * sizeof(struct gfs2_rindex);

801
		if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
802
			break;
803
		error = gfs2_internal_read(ip, buf, &pos,
804
805
806
					   sizeof(struct gfs2_rindex));
		if (error != sizeof(struct gfs2_rindex))
			break;
807
		total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
808
809
810
811
	}
	return total_data;
}

Bob Peterson's avatar
Bob Peterson committed
812
static int rgd_insert(struct gfs2_rgrpd *rgd)
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
{
	struct gfs2_sbd *sdp = rgd->rd_sbd;
	struct rb_node **newn = &sdp->sd_rindex_tree.rb_node, *parent = NULL;

	/* Figure out where to put new node */
	while (*newn) {
		struct gfs2_rgrpd *cur = rb_entry(*newn, struct gfs2_rgrpd,
						  rd_node);

		parent = *newn;
		if (rgd->rd_addr < cur->rd_addr)
			newn = &((*newn)->rb_left);
		else if (rgd->rd_addr > cur->rd_addr)
			newn = &((*newn)->rb_right);
		else
Bob Peterson's avatar
Bob Peterson committed
828
			return -EEXIST;
829
830
831
832
	}

	rb_link_node(&rgd->rd_node, parent, newn);
	rb_insert_color(&rgd->rd_node, &sdp->sd_rindex_tree);
Bob Peterson's avatar
Bob Peterson committed
833
834
	sdp->sd_rgrps++;
	return 0;
835
836
}

David Teigland's avatar
David Teigland committed
837
/**
838
 * read_rindex_entry - Pull in a new resource index entry from the disk
839
 * @ip: Pointer to the rindex inode
David Teigland's avatar
David Teigland committed
840
 *
841
 * Returns: 0 on success, > 0 on EOF, error code otherwise
842
843
 */

844
static int read_rindex_entry(struct gfs2_inode *ip)
845
846
847
{
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
	loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
848
	struct gfs2_rindex buf;
849
850
851
	int error;
	struct gfs2_rgrpd *rgd;

852
853
854
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

855
	error = gfs2_internal_read(ip, (char *)&buf, &pos,
856
				   sizeof(struct gfs2_rindex));
857
858
859

	if (error != sizeof(struct gfs2_rindex))
		return (error == 0) ? 1 : error;
860

861
	rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
862
863
864
865
866
	error = -ENOMEM;
	if (!rgd)
		return error;

	rgd->rd_sbd = sdp;
867
868
869
870
871
	rgd->rd_addr = be64_to_cpu(buf.ri_addr);
	rgd->rd_length = be32_to_cpu(buf.ri_length);
	rgd->rd_data0 = be64_to_cpu(buf.ri_data0);
	rgd->rd_data = be32_to_cpu(buf.ri_data);
	rgd->rd_bitbytes = be32_to_cpu(buf.ri_bitbytes);
Bob Peterson's avatar
Bob Peterson committed
872
	spin_lock_init(&rgd->rd_rsspin);
873

874
875
	error = compute_bitstructs(rgd);
	if (error)
876
		goto fail;
877

878
	error = gfs2_glock_get(sdp, rgd->rd_addr,
879
880
			       &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
	if (error)
881
		goto fail;
882
883

	rgd->rd_gl->gl_object = rgd;
884
	rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lksb.sb_lvbptr;
885
	rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
886
887
	if (rgd->rd_data > sdp->sd_max_rg_data)
		sdp->sd_max_rg_data = rgd->rd_data;
888
	spin_lock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
889
	error = rgd_insert(rgd);
890
	spin_unlock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
891
892
893
894
	if (!error)
		return 0;

	error = 0; /* someone else read in the rgrp; free it and ignore it */
895
	gfs2_glock_put(rgd->rd_gl);
896
897
898
899

fail:
	kfree(rgd->rd_bits);
	kmem_cache_free(gfs2_rgrpd_cachep, rgd);
900
901
902
903
904
905
906
	return error;
}

/**
 * gfs2_ri_update - Pull in a new resource index from the disk
 * @ip: pointer to the rindex inode
 *
David Teigland's avatar
David Teigland committed
907
908
909
 * Returns: 0 on successful update, error code otherwise
 */

910
static int gfs2_ri_update(struct gfs2_inode *ip)
David Teigland's avatar
David Teigland committed
911
{
912
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
David Teigland's avatar
David Teigland committed
913
914
	int error;

915
	do {
916
		error = read_rindex_entry(ip);
917
918
919
920
	} while (error == 0);

	if (error < 0)
		return error;
David Teigland's avatar
David Teigland committed
921

922
	sdp->sd_rindex_uptodate = 1;
923
924
	return 0;
}
David Teigland's avatar
David Teigland committed
925
926

/**
927
 * gfs2_rindex_update - Update the rindex if required
David Teigland's avatar
David Teigland committed
928
929
930
931
932
933
934
935
936
937
938
939
 * @sdp: The GFS2 superblock
 *
 * We grab a lock on the rindex inode to make sure that it doesn't
 * change whilst we are performing an operation. We keep this lock
 * for quite long periods of time compared to other locks. This
 * doesn't matter, since it is shared and it is very, very rarely
 * accessed in the exclusive mode (i.e. only when expanding the filesystem).
 *
 * This makes sure that we're using the latest copy of the resource index
 * special file, which might have been updated if someone expanded the
 * filesystem (via gfs2_grow utility), which adds new resource groups.
 *
940
 * Returns: 0 on succeess, error code otherwise
David Teigland's avatar
David Teigland committed
941
942
 */

943
int gfs2_rindex_update(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
944
{
945
	struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
David Teigland's avatar
David Teigland committed
946
	struct gfs2_glock *gl = ip->i_gl;
947
948
	struct gfs2_holder ri_gh;
	int error = 0;
949
	int unlock_required = 0;
David Teigland's avatar
David Teigland committed
950
951

	/* Read new copy from disk if we don't have the latest */
952
	if (!sdp->sd_rindex_uptodate) {
953
954
955
		if (!gfs2_glock_is_locked_by_me(gl)) {
			error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, &ri_gh);
			if (error)
Bob Peterson's avatar
Bob Peterson committed
956
				return error;
957
958
			unlock_required = 1;
		}
959
		if (!sdp->sd_rindex_uptodate)
David Teigland's avatar
David Teigland committed
960
			error = gfs2_ri_update(ip);
961
962
		if (unlock_required)
			gfs2_glock_dq_uninit(&ri_gh);
David Teigland's avatar
David Teigland committed
963
964
965
966
967
	}

	return error;
}

968
static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
969
970
{
	const struct gfs2_rgrp *str = buf;
971
	u32 rg_flags;
972

973
	rg_flags = be32_to_cpu(str->rg_flags);
974
	rg_flags &= ~GFS2_RDF_MASK;
975
976
	rgd->rd_flags &= GFS2_RDF_MASK;
	rgd->rd_flags |= rg_flags;
977
	rgd->rd_free = be32_to_cpu(str->rg_free);
978
	rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
979
	rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
980
981
}

982
static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
983
984
985
{
	struct gfs2_rgrp *str = buf;

986
	str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
987
	str->rg_free = cpu_to_be32(rgd->rd_free);
988
	str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
989
	str->__pad = cpu_to_be32(0);
990
	str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
991
992
993
	memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
}

994
995
996
997
998
999
1000
static int gfs2_rgrp_lvb_valid(struct gfs2_rgrpd *rgd)
{
	struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
	struct gfs2_rgrp *str = (struct gfs2_rgrp *)rgd->rd_bits[0].bi_bh->b_data;

	if (rgl->rl_flags != str->rg_flags || rgl->rl_free != str->rg_free ||
	    rgl->rl_dinodes != str->rg_dinodes ||