rgrp.c 59 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>
David Teigland's avatar
David Teigland committed
19
20

#include "gfs2.h"
21
#include "incore.h"
David Teigland's avatar
David Teigland committed
22
23
24
25
26
27
28
29
#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"
30
#include "util.h"
31
#include "log.h"
32
#include "inode.h"
Steven Whitehouse's avatar
Steven Whitehouse committed
33
#include "trace_gfs2.h"
David Teigland's avatar
David Teigland committed
34

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

38
39
40
41
42
43
44
45
46
47
#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

48
49
50
/*
 * These routines are used by the resource group routines (rgrp.c)
 * to keep track of block allocation.  Each block is represented by two
51
52
53
54
55
56
 * 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)
57
58
59
60
 */

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

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


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

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

86
87
	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;
88

89
	BUG_ON(byte1 >= end);
90

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

93
	if (unlikely(!valid_change[new_state * 4 + cur_state])) {
94
95
96
97
98
99
100
		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);
101
		dump_stack();
102
		gfs2_consist_rgrpd(rbm->rgd);
103
104
105
106
		return;
	}
	*byte1 ^= (cur_state ^ new_state) << bit;

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

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

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

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

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

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

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

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

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

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

238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
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
/**
 * 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;
	u32 goal = (u32)rblock;
	int x;

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

	for (x = 0; x < rbm->rgd->rd_length; x++) {
		rbm->bi = rbm->rgd->rd_bits + x;
		if (goal < (rbm->bi->bi_start + rbm->bi->bi_len) * GFS2_NBBY) {
			rbm->offset = goal - (rbm->bi->bi_start * GFS2_NBBY);
			break;
		}
	}

	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;

332
	n_unaligned = len & 3;
333
334
335
336
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
	/* 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;
}

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

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

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

411
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
412
413
414
415
416
417
418
419
420
421
422

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

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

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

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

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

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

Steven Whitehouse's avatar
Steven Whitehouse committed
462
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
463
{
Steven Whitehouse's avatar
Steven Whitehouse committed
464
	struct rb_node *n, *next;
465
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
466
467

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

505
	spin_lock(&sdp->sd_rindex_spin);
506
507
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
508
	spin_unlock(&sdp->sd_rindex_spin);
509
510

	return rgd;
David Teigland's avatar
David Teigland committed
511
512
513
514
}

/**
 * gfs2_rgrpd_get_next - get the next RG
515
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
516
517
518
519
520
521
 *
 * Returns: The next rgrp
 */

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

539
540
541
542
543
544
545
546
547
548
549
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;
	}
}

550
551
552
553
554
555
/**
 * 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
556
557
558
559
560
561
562
	struct gfs2_blkreserv *res;

	if (ip->i_res)
		return 0;

	res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!res)
563
		return -ENOMEM;
564

565
	RB_CLEAR_NODE(&res->rs_node);
566

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

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

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

	if (!gfs2_rs_active(rs))
		return;

596
	rgd = rs->rs_rbm.rgd;
597
	trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
598
	rb_erase(&rs->rs_node, &rgd->rd_rstree);
599
	RB_CLEAR_NODE(&rs->rs_node);
Bob Peterson's avatar
Bob Peterson committed
600
601
602

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

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

620
621
622
623
624
625
	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
626
627
628
629
}

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

666
void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
667
{
668
	struct rb_node *n;
David Teigland's avatar
David Teigland committed
669
670
671
	struct gfs2_rgrpd *rgd;
	struct gfs2_glock *gl;

672
673
	while ((n = rb_first(&sdp->sd_rindex_tree))) {
		rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
David Teigland's avatar
David Teigland committed
674
675
		gl = rgd->rd_gl;

676
		rb_erase(n, &sdp->sd_rindex_tree);
David Teigland's avatar
David Teigland committed
677
678

		if (gl) {
679
			spin_lock(&gl->gl_spin);
680
			gl->gl_object = NULL;
681
			spin_unlock(&gl->gl_spin);
682
			gfs2_glock_add_to_lru(gl);
David Teigland's avatar
David Teigland committed
683
684
685
			gfs2_glock_put(gl);
		}

686
		gfs2_free_clones(rgd);
David Teigland's avatar
David Teigland committed
687
		kfree(rgd->rd_bits);
Bob Peterson's avatar
Bob Peterson committed
688
		return_all_reservations(rgd);
689
		kmem_cache_free(gfs2_rgrpd_cachep, rgd);
David Teigland's avatar
David Teigland committed
690
691
692
	}
}

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

719
720
721
	if (!length)
		return -EINVAL;

722
	rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
David Teigland's avatar
David Teigland committed
723
724
725
	if (!rgd->rd_bits)
		return -ENOMEM;

726
	bytes_left = rgd->rd_bitbytes;
David Teigland's avatar
David Teigland committed
727
728
729
730

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

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

		bytes_left -= bytes;
	}

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

	return 0;
}

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

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

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

	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
827
828
	sdp->sd_rgrps++;
	return 0;
829
830
}

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

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

846
847
848
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

849
	error = gfs2_internal_read(ip, (char *)&buf, &pos,
850
				   sizeof(struct gfs2_rindex));
851
852
853

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

855
	rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
856
857
858
859
860
	error = -ENOMEM;
	if (!rgd)
		return error;

	rgd->rd_sbd = sdp;
861
862
863
864
865
	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
866
	spin_lock_init(&rgd->rd_rsspin);
867

868
869
	error = compute_bitstructs(rgd);
	if (error)
870
		goto fail;
871

872
	error = gfs2_glock_get(sdp, rgd->rd_addr,
873
874
			       &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
	if (error)
875
		goto fail;
876
877

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

	error = 0; /* someone else read in the rgrp; free it and ignore it */
889
	gfs2_glock_put(rgd->rd_gl);
890
891
892
893

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

904
static int gfs2_ri_update(struct gfs2_inode *ip)
David Teigland's avatar
David Teigland committed
905
{
906
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
David Teigland's avatar
David Teigland committed
907
908
	int error;

909
	do {
910
		error = read_rindex_entry(ip);
911
912
913
914
	} while (error == 0);

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

916
	sdp->sd_rindex_uptodate = 1;
917
918
	return 0;
}
David Teigland's avatar
David Teigland committed
919
920

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

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

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

	return error;
}

962
static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
963
964
{
	const struct gfs2_rgrp *str = buf;
965
	u32 rg_flags;
966

967
	rg_flags = be32_to_cpu(str->rg_flags);
968
	rg_flags &= ~GFS2_RDF_MASK;
969
970
	rgd->rd_flags &= GFS2_RDF_MASK;
	rgd->rd_flags |= rg_flags;
971
	rgd->rd_free = be32_to_cpu(str->rg_free);
972
	rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
973
	rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
974
975
}

976
static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
977
978
979
{
	struct gfs2_rgrp *str = buf;

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

988
989
990
991
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;
	return 1;
}

static void gfs2_rgrp_ondisk2lvb(struct gfs2_rgrp_lvb *rgl, const void *buf)