rgrp.c 62.8 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
353
354
355
356
357
358
359
360
361
362
363
364
365
366
	/* 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);
		gfs2_rbm_from_block(&rbm, block + chunk_size);
		n_unaligned = 3;
		if (ptr)
			break;
		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;
}

367
368
/**
 * gfs2_bitcount - count the number of bits in a certain state
369
 * @rgd: the resource group descriptor
370
371
372
373
374
375
376
 * @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
 */

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

	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
401
402
403
404
405
406
407
408
409
410
/**
 * 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;
411
	u32 length = rgd->rd_length;
412
	u32 count[4], tmp;
David Teigland's avatar
David Teigland committed
413
414
	int buf, x;

415
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
416
417
418
419
420
421
422
423
424
425
426

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

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

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

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

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

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

Steven Whitehouse's avatar
Steven Whitehouse committed
466
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
467
{
Steven Whitehouse's avatar
Steven Whitehouse committed
468
	struct rb_node *n, *next;
469
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
470
471

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

509
	spin_lock(&sdp->sd_rindex_spin);
510
511
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
512
	spin_unlock(&sdp->sd_rindex_spin);
513
514

	return rgd;
David Teigland's avatar
David Teigland committed
515
516
517
518
}

/**
 * gfs2_rgrpd_get_next - get the next RG
519
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
520
521
522
523
524
525
 *
 * Returns: The next rgrp
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
{
526
527
528
529
530
531
532
533
534
535
	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
536
		return NULL;
537
538
539
540
	}
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
	spin_unlock(&sdp->sd_rindex_spin);
	return rgd;
David Teigland's avatar
David Teigland committed
541
542
}

543
544
545
546
547
548
549
550
551
552
553
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;
	}
}

554
555
556
557
558
559
/**
 * 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)
{
Bob Peterson's avatar
Bob Peterson committed
560
561
562
563
564
565
566
	struct gfs2_blkreserv *res;

	if (ip->i_res)
		return 0;

	res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!res)
567
		return -ENOMEM;
568

569
	RB_CLEAR_NODE(&res->rs_node);
570

571
	down_write(&ip->i_rw_mutex);
Bob Peterson's avatar
Bob Peterson committed
572
573
574
575
	if (ip->i_res)
		kmem_cache_free(gfs2_rsrv_cachep, res);
	else
		ip->i_res = res;
576
	up_write(&ip->i_rw_mutex);
577
	return 0;
578
579
}

580
static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
581
{
582
583
584
	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),
585
		       rs->rs_rbm.offset, rs->rs_free);
Bob Peterson's avatar
Bob Peterson committed
586
587
}

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

	if (!gfs2_rs_active(rs))
		return;

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

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

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

624
625
626
627
628
629
	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
630
631
632
633
}

/**
 * gfs2_rs_delete - delete a multi-block reservation
634
635
636
637
638
639
640
 * @ip: The inode for this reservation
 *
 */
void gfs2_rs_delete(struct gfs2_inode *ip)
{
	down_write(&ip->i_rw_mutex);
	if (ip->i_res) {
641
		gfs2_rs_deltree(ip, ip->i_res);
Bob Peterson's avatar
Bob Peterson committed
642
		BUG_ON(ip->i_res->rs_free);
643
644
645
646
647
648
		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
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
/**
 * 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);
665
		__rs_deltree(NULL, rs);
Bob Peterson's avatar
Bob Peterson committed
666
667
668
669
	}
	spin_unlock(&rgd->rd_rsspin);
}

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

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

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

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

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

697
698
699
700
701
702
703
704
705
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
706
707
708
709
710
711
712
713
714
715
716
717
718
/**
 * 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;
719
	u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
720
	u32 bytes_left, bytes;
David Teigland's avatar
David Teigland committed
721
722
	int x;

723
724
725
	if (!length)
		return -EINVAL;

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

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

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

735
		bi->bi_flags = 0;
David Teigland's avatar
David Teigland committed
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
		/* 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);
752
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
753
754
755
			bi->bi_len = bytes;
		/* other blocks */
		} else {
756
757
			bytes = sdp->sd_sb.sb_bsize -
				sizeof(struct gfs2_meta_header);
David Teigland's avatar
David Teigland committed
758
			bi->bi_offset = sizeof(struct gfs2_meta_header);
759
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
760
761
762
763
764
765
766
767
768
769
770
			bi->bi_len = bytes;
		}

		bytes_left -= bytes;
	}

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

	return 0;
}

783
784
/**
 * gfs2_ri_total - Total up the file system space, according to the rindex.
785
 * @sdp: the filesystem
786
787
788
789
790
791
792
793
794
795
796
797
798
 *
 */
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);

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

Bob Peterson's avatar
Bob Peterson committed
810
static int rgd_insert(struct gfs2_rgrpd *rgd)
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
{
	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
826
			return -EEXIST;
827
828
829
830
	}

	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
831
832
	sdp->sd_rgrps++;
	return 0;
833
834
}

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

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

850
851
852
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

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

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

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

	rgd->rd_sbd = sdp;
865
866
867
868
869
	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
870
	spin_lock_init(&rgd->rd_rsspin);
871

872
873
	error = compute_bitstructs(rgd);
	if (error)
874
		goto fail;
875

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

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

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

fail:
	kfree(rgd->rd_bits);
	kmem_cache_free(gfs2_rgrpd_cachep, rgd);
898
899
900
901
902
903
904
	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
905
906
907
 * Returns: 0 on successful update, error code otherwise
 */

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

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

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

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

/**
925
 * gfs2_rindex_update - Update the rindex if required
David Teigland's avatar
David Teigland committed
926
927
928
929
930
931
932
933
934
935
936
937
 * @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.
 *
938
 * Returns: 0 on succeess, error code otherwise
David Teigland's avatar
David Teigland committed
939
940
 */

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

	/* Read new copy from disk if we don't have the latest */
950
	if (!sdp->sd_rindex_uptodate) {
951
952
953
		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
954
				return error;
955
956
			unlock_required = 1;
		}
957
		if (!sdp->sd_rindex_uptodate)
David Teigland's avatar
David Teigland committed
958
			error = gfs2_ri_update(ip);
959
960
		if (unlock_required)
			gfs2_glock_dq_uninit(&ri_gh);
David Teigland's avatar
David Teigland committed
961
962
963
964
965
	}

	return error;
}

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

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

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

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

992
993
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 ||
	    rgl->rl_igeneration != str->rg_igeneration)
		return 0;