rgrp.c 63.4 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;
Bob Peterson's avatar
Bob Peterson committed
84
85
	struct gfs2_bitmap *bi = rbm_bi(rbm);
	unsigned int buflen = bi->bi_len;
86
	const unsigned int bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
87

Bob Peterson's avatar
Bob Peterson committed
88
89
	byte1 = bi->bi_bh->b_data + bi->bi_offset + (rbm->offset / GFS2_NBBY);
	end = bi->bi_bh->b_data + bi->bi_offset + buflen;
90

91
	BUG_ON(byte1 >= end);
92

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

95
	if (unlikely(!valid_change[new_state * 4 + cur_state])) {
96
97
98
		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",
Bob Peterson's avatar
Bob Peterson committed
99
		       (unsigned long long)rbm->rgd->rd_addr, bi->bi_start);
100
		printk(KERN_WARNING "GFS2: bi_offset=0x%x bi_len=0x%x\n",
Bob Peterson's avatar
Bob Peterson committed
101
		       bi->bi_offset, bi->bi_len);
102
		dump_stack();
103
		gfs2_consist_rgrpd(rbm->rgd);
104
105
106
107
		return;
	}
	*byte1 ^= (cur_state ^ new_state) << bit;

Bob Peterson's avatar
Bob Peterson committed
108
109
	if (do_clone && bi->bi_clone) {
		byte2 = bi->bi_clone + 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
{
Bob Peterson's avatar
Bob Peterson committed
124
125
	struct gfs2_bitmap *bi = rbm_bi(rbm);
	const u8 *buffer = bi->bi_bh->b_data + bi->bi_offset;
126
	const u8 *byte;
127
128
	unsigned int bit;

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

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

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**
 * 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[] = {
157
158
159
160
		[0] = 0xffffffffffffffffULL,
		[1] = 0xaaaaaaaaaaaaaaaaULL,
		[2] = 0x5555555555555555ULL,
		[3] = 0x0000000000000000ULL,
161
162
163
164
165
166
167
	};
	tmp = le64_to_cpu(*ptr) ^ search[state];
	tmp &= (tmp >> 1);
	tmp &= mask;
	return tmp;
}

Bob Peterson's avatar
Bob Peterson committed
168
169
170
171
172
173
174
175
176
177
178
179
/**
 * 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)
{
180
	u64 startblk = gfs2_rbm_to_block(&rs->rs_rbm);
Bob Peterson's avatar
Bob Peterson committed
181
182
183
184
185
186
187
188

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

189
190
191
/**
 * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
 *       a block in a given allocation state.
192
 * @buf: the buffer that holds the bitmaps
193
 * @len: the length (in bytes) of the buffer
194
 * @goal: start search at this block's bit-pair (within @buffer)
195
 * @state: GFS2_BLKST_XXX the state of the block we're looking for.
196
197
198
 *
 * 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
199
200
201
202
203
 * 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
204
 * always ok to read a complete multiple of 64 bits at the end
205
 * of the block in case the end is no aligned to a natural boundary.
206
207
208
209
 *
 * Return: the block number (bitmap buffer scope) that was found
 */

210
211
static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
		       u32 goal, u8 state)
212
{
213
214
215
216
	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;
217
	u64 mask = 0x5555555555555555ULL;
218
219
220
221
222
223
224
	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) {
225
		tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
226
		ptr++;
227
	}
228
229
230
231
232
233
234
	/* 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--;
235
	bit = __ffs64(tmp);
236
237
	bit /= 2;	/* two bits per entry in the bitmap */
	return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
238
239
}

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
/**
 * 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;

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

Bob Peterson's avatar
Bob Peterson committed
262
	rbm->bii = 0;
263
264
	rbm->offset = (u32)(rblock);
	/* Check if the block is within the first block */
Bob Peterson's avatar
Bob Peterson committed
265
	if (rbm->offset < rbm_bi(rbm)->bi_blocks)
266
267
268
269
270
		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;
Bob Peterson's avatar
Bob Peterson committed
271
272
	rbm->bii = rbm->offset / rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
	rbm->offset -= rbm->bii * rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
273
274
275
	return 0;
}

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
/**
 * gfs2_rbm_incr - increment an rbm structure
 * @rbm: The rbm with rgd already set correctly
 *
 * This function takes an existing rbm structure and increments it to the next
 * viable block offset.
 *
 * Returns: If incrementing the offset would cause the rbm to go past the
 *          end of the rgrp, true is returned, otherwise false.
 *
 */

static bool gfs2_rbm_incr(struct gfs2_rbm *rbm)
{
	if (rbm->offset + 1 < rbm_bi(rbm)->bi_blocks) { /* in the same bitmap */
		rbm->offset++;
		return false;
	}
	if (rbm->bii == rbm->rgd->rd_length - 1) /* at the last bitmap */
		return true;

	rbm->offset = 0;
	rbm->bii++;
	return false;
}

302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
/**
 * 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)
{
	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;
323
		if (gfs2_rbm_incr(rbm))
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
			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;
Bob Peterson's avatar
Bob Peterson committed
354
	struct gfs2_bitmap *bi;
355
356
357
358
359

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

360
	n_unaligned = len & 3;
361
362
	/* Start is now byte aligned */
	while (len > 3) {
Bob Peterson's avatar
Bob Peterson committed
363
364
365
366
367
368
		bi = rbm_bi(&rbm);
		start = bi->bi_bh->b_data;
		if (bi->bi_clone)
			start = bi->bi_clone;
		end = start + bi->bi_bh->b_size;
		start += bi->bi_offset;
369
370
371
372
373
374
375
376
377
		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);
378
379
		if (gfs2_rbm_from_block(&rbm, block + chunk_size)) {
			n_unaligned = 0;
380
			break;
381
382
383
384
385
		}
		if (ptr) {
			n_unaligned = 3;
			break;
		}
386
387
388
389
390
391
392
393
394
395
		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;
}

396
397
/**
 * gfs2_bitcount - count the number of bits in a certain state
398
 * @rgd: the resource group descriptor
399
400
401
402
403
404
405
 * @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
 */

406
407
static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
			 unsigned int buflen, u8 state)
408
{
409
410
411
412
413
	const u8 *byte = buffer;
	const u8 *end = buffer + buflen;
	const u8 state1 = state << 2;
	const u8 state2 = state << 4;
	const u8 state3 = state << 6;
414
	u32 count = 0;
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429

	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
430
431
432
433
434
435
436
437
438
439
/**
 * 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;
440
	u32 length = rgd->rd_length;
441
	u32 count[4], tmp;
David Teigland's avatar
David Teigland committed
442
443
	int buf, x;

444
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
445
446
447
448
449
450
451
452
453
454
455

	/* 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);
	}

456
	if (count[0] != rgd->rd_free) {
David Teigland's avatar
David Teigland committed
457
458
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "free data mismatch:  %u != %u\n",
459
			       count[0], rgd->rd_free);
David Teigland's avatar
David Teigland committed
460
461
462
		return;
	}

463
	tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
464
	if (count[1] != tmp) {
David Teigland's avatar
David Teigland committed
465
466
467
468
469
470
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "used data mismatch:  %u != %u\n",
			       count[1], tmp);
		return;
	}

471
	if (count[2] + count[3] != rgd->rd_dinodes) {
David Teigland's avatar
David Teigland committed
472
		if (gfs2_consist_rgrpd(rgd))
473
			fs_err(sdp, "used metadata mismatch:  %u != %u\n",
474
			       count[2] + count[3], rgd->rd_dinodes);
David Teigland's avatar
David Teigland committed
475
476
477
478
		return;
	}
}

479
static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
David Teigland's avatar
David Teigland committed
480
{
481
482
	u64 first = rgd->rd_data0;
	u64 last = first + rgd->rd_data;
483
	return first <= block && block < last;
David Teigland's avatar
David Teigland committed
484
485
486
487
488
}

/**
 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 * @sdp: The GFS2 superblock
489
490
 * @blk: The data block number
 * @exact: True if this needs to be an exact match
David Teigland's avatar
David Teigland committed
491
492
493
494
 *
 * Returns: The resource group, or NULL if not found
 */

Steven Whitehouse's avatar
Steven Whitehouse committed
495
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
496
{
Steven Whitehouse's avatar
Steven Whitehouse committed
497
	struct rb_node *n, *next;
498
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
499
500

	spin_lock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
501
502
503
504
	n = sdp->sd_rindex_tree.rb_node;
	while (n) {
		cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
		next = NULL;
505
		if (blk < cur->rd_addr)
Steven Whitehouse's avatar
Steven Whitehouse committed
506
			next = n->rb_left;
507
		else if (blk >= cur->rd_data0 + cur->rd_data)
Steven Whitehouse's avatar
Steven Whitehouse committed
508
509
			next = n->rb_right;
		if (next == NULL) {
David Teigland's avatar
David Teigland committed
510
			spin_unlock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
511
512
513
514
515
516
			if (exact) {
				if (blk < cur->rd_addr)
					return NULL;
				if (blk >= cur->rd_data0 + cur->rd_data)
					return NULL;
			}
517
			return cur;
David Teigland's avatar
David Teigland committed
518
		}
Steven Whitehouse's avatar
Steven Whitehouse committed
519
		n = next;
David Teigland's avatar
David Teigland committed
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
	}
	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)
{
535
536
537
	const struct rb_node *n;
	struct gfs2_rgrpd *rgd;

538
	spin_lock(&sdp->sd_rindex_spin);
539
540
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
541
	spin_unlock(&sdp->sd_rindex_spin);
542
543

	return rgd;
David Teigland's avatar
David Teigland committed
544
545
546
547
}

/**
 * gfs2_rgrpd_get_next - get the next RG
548
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
549
550
551
552
553
554
 *
 * Returns: The next rgrp
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
{
555
556
557
558
559
560
561
562
563
564
	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
565
		return NULL;
566
567
568
569
	}
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
	spin_unlock(&sdp->sd_rindex_spin);
	return rgd;
David Teigland's avatar
David Teigland committed
570
571
}

572
573
574
575
576
577
578
579
580
581
582
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;
	}
}

583
584
585
586
587
588
/**
 * 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
589
	int error = 0;
Bob Peterson's avatar
Bob Peterson committed
590

Abhijith Das's avatar
Abhijith Das committed
591
	down_write(&ip->i_rw_mutex);
Bob Peterson's avatar
Bob Peterson committed
592
	if (ip->i_res)
Abhijith Das's avatar
Abhijith Das committed
593
		goto out;
594

Abhijith Das's avatar
Abhijith Das committed
595
596
597
598
599
	ip->i_res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!ip->i_res) {
		error = -ENOMEM;
		goto out;
	}
600

Abhijith Das's avatar
Abhijith Das committed
601
602
	RB_CLEAR_NODE(&ip->i_res->rs_node);
out:
603
	up_write(&ip->i_rw_mutex);
604
	return error;
605
606
}

607
static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
608
{
609
610
611
	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),
612
		       rs->rs_rbm.offset, rs->rs_free);
Bob Peterson's avatar
Bob Peterson committed
613
614
}

615
/**
Bob Peterson's avatar
Bob Peterson committed
616
617
618
619
 * __rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
620
static void __rs_deltree(struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
621
622
623
624
625
626
{
	struct gfs2_rgrpd *rgd;

	if (!gfs2_rs_active(rs))
		return;

627
	rgd = rs->rs_rbm.rgd;
628
	trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
629
	rb_erase(&rs->rs_node, &rgd->rd_rstree);
630
	RB_CLEAR_NODE(&rs->rs_node);
Bob Peterson's avatar
Bob Peterson committed
631
632

	if (rs->rs_free) {
Bob Peterson's avatar
Bob Peterson committed
633
634
		struct gfs2_bitmap *bi = rbm_bi(&rs->rs_rbm);

635
		/* return reserved blocks to the rgrp */
636
637
		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
638
		rs->rs_free = 0;
Bob Peterson's avatar
Bob Peterson committed
639
		clear_bit(GBF_FULL, &bi->bi_flags);
Bob Peterson's avatar
Bob Peterson committed
640
641
642
643
644
645
646
647
648
		smp_mb__after_clear_bit();
	}
}

/**
 * gfs2_rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
649
void gfs2_rs_deltree(struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
650
651
652
{
	struct gfs2_rgrpd *rgd;

653
654
655
	rgd = rs->rs_rbm.rgd;
	if (rgd) {
		spin_lock(&rgd->rd_rsspin);
656
		__rs_deltree(rs);
657
658
		spin_unlock(&rgd->rd_rsspin);
	}
Bob Peterson's avatar
Bob Peterson committed
659
660
661
662
}

/**
 * gfs2_rs_delete - delete a multi-block reservation
663
664
665
666
667
 * @ip: The inode for this reservation
 *
 */
void gfs2_rs_delete(struct gfs2_inode *ip)
{
668
669
	struct inode *inode = &ip->i_inode;

670
	down_write(&ip->i_rw_mutex);
671
	if (ip->i_res && atomic_read(&inode->i_writecount) <= 1) {
672
		gfs2_rs_deltree(ip->i_res);
Bob Peterson's avatar
Bob Peterson committed
673
		BUG_ON(ip->i_res->rs_free);
674
675
676
677
678
679
		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
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
/**
 * 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);
696
		__rs_deltree(rs);
Bob Peterson's avatar
Bob Peterson committed
697
698
699
700
	}
	spin_unlock(&rgd->rd_rsspin);
}

701
void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
702
{
703
	struct rb_node *n;
David Teigland's avatar
David Teigland committed
704
705
706
	struct gfs2_rgrpd *rgd;
	struct gfs2_glock *gl;

707
708
	while ((n = rb_first(&sdp->sd_rindex_tree))) {
		rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
David Teigland's avatar
David Teigland committed
709
710
		gl = rgd->rd_gl;

711
		rb_erase(n, &sdp->sd_rindex_tree);
David Teigland's avatar
David Teigland committed
712
713

		if (gl) {
714
			spin_lock(&gl->gl_spin);
715
			gl->gl_object = NULL;
716
			spin_unlock(&gl->gl_spin);
717
			gfs2_glock_add_to_lru(gl);
David Teigland's avatar
David Teigland committed
718
719
720
			gfs2_glock_put(gl);
		}

721
		gfs2_free_clones(rgd);
David Teigland's avatar
David Teigland committed
722
		kfree(rgd->rd_bits);
Bob Peterson's avatar
Bob Peterson committed
723
		return_all_reservations(rgd);
724
		kmem_cache_free(gfs2_rgrpd_cachep, rgd);
David Teigland's avatar
David Teigland committed
725
726
727
	}
}

728
729
730
731
732
733
734
735
736
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
737
738
739
740
741
742
743
744
745
746
747
748
749
/**
 * 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;
750
	u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
751
	u32 bytes_left, bytes;
David Teigland's avatar
David Teigland committed
752
753
	int x;

754
755
756
	if (!length)
		return -EINVAL;

757
	rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
David Teigland's avatar
David Teigland committed
758
759
760
	if (!rgd->rd_bits)
		return -ENOMEM;

761
	bytes_left = rgd->rd_bitbytes;
David Teigland's avatar
David Teigland committed
762
763
764
765

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

766
		bi->bi_flags = 0;
David Teigland's avatar
David Teigland committed
767
768
769
770
771
772
		/* 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;
773
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
774
775
776
777
778
779
		/* 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;
780
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
781
782
783
784
		/* last block */
		} else if (x + 1 == length) {
			bytes = bytes_left;
			bi->bi_offset = sizeof(struct gfs2_meta_header);
785
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
786
			bi->bi_len = bytes;
787
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
788
789
		/* other blocks */
		} else {
790
791
			bytes = sdp->sd_sb.sb_bsize -
				sizeof(struct gfs2_meta_header);
David Teigland's avatar
David Teigland committed
792
			bi->bi_offset = sizeof(struct gfs2_meta_header);
793
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
794
			bi->bi_len = bytes;
795
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
796
797
798
799
800
801
802
803
804
805
		}

		bytes_left -= bytes;
	}

	if (bytes_left) {
		gfs2_consist_rgrpd(rgd);
		return -EIO;
	}
	bi = rgd->rd_bits + (length - 1);
806
	if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
David Teigland's avatar
David Teigland committed
807
		if (gfs2_consist_rgrpd(rgd)) {
808
			gfs2_rindex_print(rgd);
David Teigland's avatar
David Teigland committed
809
810
811
812
813
814
815
816
817
			fs_err(sdp, "start=%u len=%u offset=%u\n",
			       bi->bi_start, bi->bi_len, bi->bi_offset);
		}
		return -EIO;
	}

	return 0;
}

818
819
/**
 * gfs2_ri_total - Total up the file system space, according to the rindex.
820
 * @sdp: the filesystem
821
822
823
824
825
826
827
828
829
830
831
832
833
 *
 */
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);

834
		if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
835
			break;
836
		error = gfs2_internal_read(ip, buf, &pos,
837
838
839
					   sizeof(struct gfs2_rindex));
		if (error != sizeof(struct gfs2_rindex))
			break;
840
		total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
841
842
843
844
	}
	return total_data;
}

Bob Peterson's avatar
Bob Peterson committed
845
static int rgd_insert(struct gfs2_rgrpd *rgd)
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
{
	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
861
			return -EEXIST;
862
863
864
865
	}

	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
866
867
	sdp->sd_rgrps++;
	return 0;
868
869
}

David Teigland's avatar
David Teigland committed
870
/**
871
 * read_rindex_entry - Pull in a new resource index entry from the disk
872
 * @ip: Pointer to the rindex inode
David Teigland's avatar
David Teigland committed
873
 *
874
 * Returns: 0 on success, > 0 on EOF, error code otherwise
875
876
 */

877
static int read_rindex_entry(struct gfs2_inode *ip)
878
879
880
{
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
	loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
881
	struct gfs2_rindex buf;
882
883
884
	int error;
	struct gfs2_rgrpd *rgd;

885
886
887
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

888
	error = gfs2_internal_read(ip, (char *)&buf, &pos,
889
				   sizeof(struct gfs2_rindex));
890
891
892

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

894
	rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
895
896
897
898
899
	error = -ENOMEM;
	if (!rgd)
		return error;

	rgd->rd_sbd = sdp;
900
901
902
903
904
	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
905
	spin_lock_init(&rgd->rd_rsspin);
906

907
908
	error = compute_bitstructs(rgd);
	if (error)
909
		goto fail;
910

911
	error = gfs2_glock_get(sdp, rgd->rd_addr,
912
913
			       &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
	if (error)
914
		goto fail;
915
916

	rgd->rd_gl->gl_object = rgd;
917
	rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lksb.sb_lvbptr;
918
	rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
919
920
	if (rgd->rd_data > sdp->sd_max_rg_data)
		sdp->sd_max_rg_data = rgd->rd_data;
921
	spin_lock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
922
	error = rgd_insert(rgd);
923
	spin_unlock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
924
925
926
927
	if (!error)
		return 0;

	error = 0; /* someone else read in the rgrp; free it and ignore it */
928
	gfs2_glock_put(rgd->rd_gl);
929
930
931
932

fail:
	kfree(rgd->rd_bits);
	kmem_cache_free(gfs2_rgrpd_cachep, rgd);
933
934
935
936
937
938
939
	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
940
941
942
 * Returns: 0 on successful update, error code otherwise
 */

943
static int gfs2_ri_update(struct gfs2_inode *ip)
David Teigland's avatar
David Teigland committed
944
{
945
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
David Teigland's avatar
David Teigland committed
946
947
	int error;

948
	do {
949
		error = read_rindex_entry(ip);
950
951
952
953
	} while (error == 0);

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

955
	sdp->sd_rindex_uptodate = 1;
956
957
	return 0;
}
David Teigland's avatar
David Teigland committed
958
959

/**
960
 * gfs2_rindex_update - Update the rindex if required
David Teigland's avatar
David Teigland committed
961
962
963
964
965
966
967
968
969
970
971
972
 * @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.
 *
973
 * Returns: 0 on succeess, error code otherwise
David Teigland's avatar
David Teigland committed
974
975
 */

976
int gfs2_rindex_update(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
977
{
978
	struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
David Teigland's avatar
David Teigland committed
979
	struct gfs2_glock *gl = ip->i_gl;
980
981
	struct gfs2_holder ri_gh;
	int error = 0;
982
	int unlock_required = 0;
David Teigland's avatar
David Teigland committed
983
984

	/* Read new copy from disk if we don't have the latest */
985
	if (!sdp->sd_rindex_uptodate) {
986
987
988
		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
989
				return error;
990
991
			unlock_required = 1;
		}
992
		if (!sdp->sd_rindex_uptodate)
David Teigland's avatar
David Teigland committed
993
			error = gfs2_ri_update(ip);
994
995
		if (unlock_required)
			gfs2_glock_dq_uninit(&ri_gh);
David Teigland's avatar
David Teigland committed
996
997
998
999
1000
	}

	return error;
}