rgrp.c 66 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
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

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

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

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

41
42
43
44
45
46
47
48
49
50
#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

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

62
63
64
65
66
struct gfs2_extent {
	struct gfs2_rbm rbm;
	u32 len;
};

67
68
static const char valid_change[16] = {
	        /* current */
69
	/* n */ 0, 1, 1, 1,
70
	/* e */ 1, 0, 0, 0,
71
	/* w */ 0, 0, 0, 1,
72
73
74
	        1, 0, 0, 0
};

75
76
77
static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 *minext,
			 const struct gfs2_inode *ip, bool nowrap,
			 const struct gfs2_alloc_parms *ap);
78
79


80
81
/**
 * gfs2_setbit - Set a bit in the bitmaps
82
83
 * @rbm: The position of the bit to set
 * @do_clone: Also set the clone bitmap, if it exists
84
85
86
87
 * @new_state: the new state of the block
 *
 */

88
static inline void gfs2_setbit(const struct gfs2_rbm *rbm, bool do_clone,
89
			       unsigned char new_state)
90
{
91
	unsigned char *byte1, *byte2, *end, cur_state;
Bob Peterson's avatar
Bob Peterson committed
92
93
	struct gfs2_bitmap *bi = rbm_bi(rbm);
	unsigned int buflen = bi->bi_len;
94
	const unsigned int bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
95

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

99
	BUG_ON(byte1 >= end);
100

101
	cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
102

103
	if (unlikely(!valid_change[new_state * 4 + cur_state])) {
104
105
106
107
108
109
		pr_warn("buf_blk = 0x%x old_state=%d, new_state=%d\n",
			rbm->offset, cur_state, new_state);
		pr_warn("rgrp=0x%llx bi_start=0x%x\n",
			(unsigned long long)rbm->rgd->rd_addr, bi->bi_start);
		pr_warn("bi_offset=0x%x bi_len=0x%x\n",
			bi->bi_offset, bi->bi_len);
110
		dump_stack();
111
		gfs2_consist_rgrpd(rbm->rgd);
112
113
114
115
		return;
	}
	*byte1 ^= (cur_state ^ new_state) << bit;

Bob Peterson's avatar
Bob Peterson committed
116
117
	if (do_clone && bi->bi_clone) {
		byte2 = bi->bi_clone + bi->bi_offset + (rbm->offset / GFS2_NBBY);
118
119
120
		cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
		*byte2 ^= (cur_state ^ new_state) << bit;
	}
121
122
123
124
}

/**
 * gfs2_testbit - test a bit in the bitmaps
125
 * @rbm: The bit to test
126
 *
127
 * Returns: The two bit block state of the requested bit
128
129
 */

130
static inline u8 gfs2_testbit(const struct gfs2_rbm *rbm)
131
{
Bob Peterson's avatar
Bob Peterson committed
132
133
	struct gfs2_bitmap *bi = rbm_bi(rbm);
	const u8 *buffer = bi->bi_bh->b_data + bi->bi_offset;
134
	const u8 *byte;
135
136
	unsigned int bit;

137
138
	byte = buffer + (rbm->offset / GFS2_NBBY);
	bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
139

140
	return (*byte >> bit) & GFS2_BIT_MASK;
141
142
}

143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/**
 * 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[] = {
165
166
167
168
		[0] = 0xffffffffffffffffULL,
		[1] = 0xaaaaaaaaaaaaaaaaULL,
		[2] = 0x5555555555555555ULL,
		[3] = 0x0000000000000000ULL,
169
170
171
172
173
174
175
	};
	tmp = le64_to_cpu(*ptr) ^ search[state];
	tmp &= (tmp >> 1);
	tmp &= mask;
	return tmp;
}

Bob Peterson's avatar
Bob Peterson committed
176
177
178
179
180
181
182
183
184
185
186
187
/**
 * 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)
{
188
	u64 startblk = gfs2_rbm_to_block(&rs->rs_rbm);
Bob Peterson's avatar
Bob Peterson committed
189
190
191
192
193
194
195
196

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

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

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

248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
/**
 * 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
270
	rbm->bii = 0;
271
272
	rbm->offset = (u32)(rblock);
	/* Check if the block is within the first block */
Bob Peterson's avatar
Bob Peterson committed
273
	if (rbm->offset < rbm_bi(rbm)->bi_blocks)
274
275
276
277
278
		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
279
280
	rbm->bii = rbm->offset / rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
	rbm->offset -= rbm->bii * rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
281
282
283
	return 0;
}

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

310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
/**
 * 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;
331
		if (gfs2_rbm_incr(rbm))
332
333
334
335
336
337
338
339
			return true;
	}

	return false;
}

/**
 * gfs2_free_extlen - Return extent length of free blocks
340
 * @rrbm: Starting position
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
 * @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
362
	struct gfs2_bitmap *bi;
363
364
365
366
367

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

368
	n_unaligned = len & 3;
369
370
	/* Start is now byte aligned */
	while (len > 3) {
Bob Peterson's avatar
Bob Peterson committed
371
372
373
374
375
376
		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;
377
378
379
380
381
382
383
384
385
		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);
386
387
		if (gfs2_rbm_from_block(&rbm, block + chunk_size)) {
			n_unaligned = 0;
388
			break;
389
390
391
392
393
		}
		if (ptr) {
			n_unaligned = 3;
			break;
		}
394
395
396
397
398
399
400
401
402
403
		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;
}

404
405
/**
 * gfs2_bitcount - count the number of bits in a certain state
406
 * @rgd: the resource group descriptor
407
408
409
410
411
412
413
 * @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
 */

414
415
static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
			 unsigned int buflen, u8 state)
416
{
417
418
419
420
421
	const u8 *byte = buffer;
	const u8 *end = buffer + buflen;
	const u8 state1 = state << 2;
	const u8 state2 = state << 4;
	const u8 state3 = state << 6;
422
	u32 count = 0;
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437

	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
438
439
440
441
442
443
444
445
446
447
/**
 * 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;
448
	u32 length = rgd->rd_length;
449
	u32 count[4], tmp;
David Teigland's avatar
David Teigland committed
450
451
	int buf, x;

452
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
453
454
455
456
457
458
459
460
461
462
463

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

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

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

479
	if (count[2] + count[3] != rgd->rd_dinodes) {
David Teigland's avatar
David Teigland committed
480
		if (gfs2_consist_rgrpd(rgd))
481
			fs_err(sdp, "used metadata mismatch:  %u != %u\n",
482
			       count[2] + count[3], rgd->rd_dinodes);
David Teigland's avatar
David Teigland committed
483
484
485
486
		return;
	}
}

487
static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
David Teigland's avatar
David Teigland committed
488
{
489
490
	u64 first = rgd->rd_data0;
	u64 last = first + rgd->rd_data;
491
	return first <= block && block < last;
David Teigland's avatar
David Teigland committed
492
493
494
495
496
}

/**
 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 * @sdp: The GFS2 superblock
497
498
 * @blk: The data block number
 * @exact: True if this needs to be an exact match
David Teigland's avatar
David Teigland committed
499
500
501
502
 *
 * Returns: The resource group, or NULL if not found
 */

Steven Whitehouse's avatar
Steven Whitehouse committed
503
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
504
{
Steven Whitehouse's avatar
Steven Whitehouse committed
505
	struct rb_node *n, *next;
506
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
507
508

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

546
	spin_lock(&sdp->sd_rindex_spin);
547
548
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
549
	spin_unlock(&sdp->sd_rindex_spin);
550
551

	return rgd;
David Teigland's avatar
David Teigland committed
552
553
554
555
}

/**
 * gfs2_rgrpd_get_next - get the next RG
556
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
557
558
559
560
561
562
 *
 * Returns: The next rgrp
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
{
563
564
565
566
567
568
569
570
571
572
	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
573
		return NULL;
574
575
576
577
	}
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
	spin_unlock(&sdp->sd_rindex_spin);
	return rgd;
David Teigland's avatar
David Teigland committed
578
579
}

580
581
582
583
584
585
586
void check_and_update_goal(struct gfs2_inode *ip)
{
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
	if (!ip->i_goal || gfs2_blk2rgrpd(sdp, ip->i_goal, 1) == NULL)
		ip->i_goal = ip->i_no_addr;
}

587
588
589
590
591
592
593
594
595
596
597
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;
	}
}

598
599
600
601
602
603
/**
 * 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
604
	int error = 0;
Bob Peterson's avatar
Bob Peterson committed
605

Abhijith Das's avatar
Abhijith Das committed
606
	down_write(&ip->i_rw_mutex);
Bob Peterson's avatar
Bob Peterson committed
607
	if (ip->i_res)
Abhijith Das's avatar
Abhijith Das committed
608
		goto out;
609

Abhijith Das's avatar
Abhijith Das committed
610
611
612
613
614
	ip->i_res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!ip->i_res) {
		error = -ENOMEM;
		goto out;
	}
615

Abhijith Das's avatar
Abhijith Das committed
616
617
	RB_CLEAR_NODE(&ip->i_res->rs_node);
out:
618
	up_write(&ip->i_rw_mutex);
619
	return error;
620
621
}

622
static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
623
{
624
625
626
	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),
627
		       rs->rs_rbm.offset, rs->rs_free);
Bob Peterson's avatar
Bob Peterson committed
628
629
}

630
/**
Bob Peterson's avatar
Bob Peterson committed
631
632
633
634
 * __rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
635
static void __rs_deltree(struct gfs2_blkreserv *rs)
Bob Peterson's avatar
Bob Peterson committed
636
637
638
639
640
641
{
	struct gfs2_rgrpd *rgd;

	if (!gfs2_rs_active(rs))
		return;

642
	rgd = rs->rs_rbm.rgd;
643
	trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
644
	rb_erase(&rs->rs_node, &rgd->rd_rstree);
645
	RB_CLEAR_NODE(&rs->rs_node);
Bob Peterson's avatar
Bob Peterson committed
646
647

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

650
		/* return reserved blocks to the rgrp */
651
652
		BUG_ON(rs->rs_rbm.rgd->rd_reserved < rs->rs_free);
		rs->rs_rbm.rgd->rd_reserved -= rs->rs_free;
653
654
655
656
657
		/* The rgrp extent failure point is likely not to increase;
		   it will only do so if the freed blocks are somehow
		   contiguous with a span of free blocks that follows. Still,
		   it will force the number to be recalculated later. */
		rgd->rd_extfail_pt += rs->rs_free;
Bob Peterson's avatar
Bob Peterson committed
658
		rs->rs_free = 0;
Bob Peterson's avatar
Bob Peterson committed
659
		clear_bit(GBF_FULL, &bi->bi_flags);
Bob Peterson's avatar
Bob Peterson committed
660
661
662
663
664
665
666
667
	}
}

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

672
673
674
	rgd = rs->rs_rbm.rgd;
	if (rgd) {
		spin_lock(&rgd->rd_rsspin);
675
		__rs_deltree(rs);
676
677
		spin_unlock(&rgd->rd_rsspin);
	}
Bob Peterson's avatar
Bob Peterson committed
678
679
680
681
}

/**
 * gfs2_rs_delete - delete a multi-block reservation
682
 * @ip: The inode for this reservation
683
 * @wcount: The inode's write count, or NULL
684
685
 *
 */
686
void gfs2_rs_delete(struct gfs2_inode *ip, atomic_t *wcount)
687
688
{
	down_write(&ip->i_rw_mutex);
689
	if (ip->i_res && ((wcount == NULL) || (atomic_read(wcount) <= 1))) {
690
		gfs2_rs_deltree(ip->i_res);
Bob Peterson's avatar
Bob Peterson committed
691
		BUG_ON(ip->i_res->rs_free);
692
693
694
695
696
697
		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
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
/**
 * 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);
714
		__rs_deltree(rs);
Bob Peterson's avatar
Bob Peterson committed
715
716
717
718
	}
	spin_unlock(&rgd->rd_rsspin);
}

719
void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
720
{
721
	struct rb_node *n;
David Teigland's avatar
David Teigland committed
722
723
724
	struct gfs2_rgrpd *rgd;
	struct gfs2_glock *gl;

725
726
	while ((n = rb_first(&sdp->sd_rindex_tree))) {
		rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
David Teigland's avatar
David Teigland committed
727
728
		gl = rgd->rd_gl;

729
		rb_erase(n, &sdp->sd_rindex_tree);
David Teigland's avatar
David Teigland committed
730
731

		if (gl) {
732
			spin_lock(&gl->gl_spin);
733
			gl->gl_object = NULL;
734
			spin_unlock(&gl->gl_spin);
735
			gfs2_glock_add_to_lru(gl);
David Teigland's avatar
David Teigland committed
736
737
738
			gfs2_glock_put(gl);
		}

739
		gfs2_free_clones(rgd);
David Teigland's avatar
David Teigland committed
740
		kfree(rgd->rd_bits);
Bob Peterson's avatar
Bob Peterson committed
741
		return_all_reservations(rgd);
742
		kmem_cache_free(gfs2_rgrpd_cachep, rgd);
David Teigland's avatar
David Teigland committed
743
744
745
	}
}

746
747
static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
{
748
749
750
751
752
	pr_info("ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
	pr_info("ri_length = %u\n", rgd->rd_length);
	pr_info("ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
	pr_info("ri_data = %u\n", rgd->rd_data);
	pr_info("ri_bitbytes = %u\n", rgd->rd_bitbytes);
753
754
}

David Teigland's avatar
David Teigland committed
755
756
757
758
759
760
761
762
763
764
765
766
767
/**
 * 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;
768
	u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
769
	u32 bytes_left, bytes;
David Teigland's avatar
David Teigland committed
770
771
	int x;

772
773
774
	if (!length)
		return -EINVAL;

775
	rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
David Teigland's avatar
David Teigland committed
776
777
778
	if (!rgd->rd_bits)
		return -ENOMEM;

779
	bytes_left = rgd->rd_bitbytes;
David Teigland's avatar
David Teigland committed
780
781
782
783

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

784
		bi->bi_flags = 0;
David Teigland's avatar
David Teigland committed
785
786
787
788
789
790
		/* 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;
791
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
792
793
794
795
796
797
		/* 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;
798
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
799
800
801
802
		/* last block */
		} else if (x + 1 == length) {
			bytes = bytes_left;
			bi->bi_offset = sizeof(struct gfs2_meta_header);
803
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
804
			bi->bi_len = bytes;
805
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
806
807
		/* other blocks */
		} else {
808
809
			bytes = sdp->sd_sb.sb_bsize -
				sizeof(struct gfs2_meta_header);
David Teigland's avatar
David Teigland committed
810
			bi->bi_offset = sizeof(struct gfs2_meta_header);
811
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
812
			bi->bi_len = bytes;
813
			bi->bi_blocks = bytes * GFS2_NBBY;
David Teigland's avatar
David Teigland committed
814
815
816
817
818
819
820
821
822
823
		}

		bytes_left -= bytes;
	}

	if (bytes_left) {
		gfs2_consist_rgrpd(rgd);
		return -EIO;
	}
	bi = rgd->rd_bits + (length - 1);
824
	if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
David Teigland's avatar
David Teigland committed
825
		if (gfs2_consist_rgrpd(rgd)) {
826
			gfs2_rindex_print(rgd);
David Teigland's avatar
David Teigland committed
827
828
829
830
831
832
833
834
835
			fs_err(sdp, "start=%u len=%u offset=%u\n",
			       bi->bi_start, bi->bi_len, bi->bi_offset);
		}
		return -EIO;
	}

	return 0;
}

836
837
/**
 * gfs2_ri_total - Total up the file system space, according to the rindex.
838
 * @sdp: the filesystem
839
840
841
842
843
844
845
846
847
848
849
850
851
 *
 */
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);

852
		if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
853
			break;
854
		error = gfs2_internal_read(ip, buf, &pos,
855
856
857
					   sizeof(struct gfs2_rindex));
		if (error != sizeof(struct gfs2_rindex))
			break;
858
		total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
859
860
861
862
	}
	return total_data;
}

Bob Peterson's avatar
Bob Peterson committed
863
static int rgd_insert(struct gfs2_rgrpd *rgd)
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
{
	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
879
			return -EEXIST;
880
881
882
883
	}

	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
884
885
	sdp->sd_rgrps++;
	return 0;
886
887
}

David Teigland's avatar
David Teigland committed
888
/**
889
 * read_rindex_entry - Pull in a new resource index entry from the disk
890
 * @ip: Pointer to the rindex inode
David Teigland's avatar
David Teigland committed
891
 *
892
 * Returns: 0 on success, > 0 on EOF, error code otherwise
893
894
 */

895
static int read_rindex_entry(struct gfs2_inode *ip)
896
897
{
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
898
	const unsigned bsize = sdp->sd_sb.sb_bsize;
899
	loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
900
	struct gfs2_rindex buf;
901
902
903
	int error;
	struct gfs2_rgrpd *rgd;

904
905
906
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

907
	error = gfs2_internal_read(ip, (char *)&buf, &pos,
908
				   sizeof(struct gfs2_rindex));
909
910
911

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

913
	rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
914
915
916
917
918
	error = -ENOMEM;
	if (!rgd)
		return error;

	rgd->rd_sbd = sdp;
919
920
921
922
923
	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
924
	spin_lock_init(&rgd->rd_rsspin);
925

926
927
	error = compute_bitstructs(rgd);
	if (error)
928
		goto fail;
929

930
	error = gfs2_glock_get(sdp, rgd->rd_addr,
931
932
			       &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
	if (error)
933
		goto fail;
934
935

	rgd->rd_gl->gl_object = rgd;
936
937
	rgd->rd_gl->gl_vm.start = rgd->rd_addr * bsize;
	rgd->rd_gl->gl_vm.end = rgd->rd_gl->gl_vm.start + (rgd->rd_length * bsize) - 1;
938
	rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lksb.sb_lvbptr;
939
	rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
940
941
	if (rgd->rd_data > sdp->sd_max_rg_data)
		sdp->sd_max_rg_data = rgd->rd_data;
942
	spin_lock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
943
	error = rgd_insert(rgd);
944
	spin_unlock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
945
946
947
948
	if (!error)
		return 0;

	error = 0; /* someone else read in the rgrp; free it and ignore it */
949
	gfs2_glock_put(rgd->rd_gl);
950
951
952
953

fail:
	kfree(rgd->rd_bits);
	kmem_cache_free(gfs2_rgrpd_cachep, rgd);
954
955
956
957
958
959
960
	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
961
962
963
 * Returns: 0 on successful update, error code otherwise
 */

964
static int gfs2_ri_update(struct gfs2_inode *ip)
David Teigland's avatar
David Teigland committed
965
{
966
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
David Teigland's avatar
David Teigland committed
967
968
	int error;

969
	do {
970
		error = read_rindex_entry(ip);
971
972
973
974
	} while (error == 0);

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

976
	sdp->sd_rindex_uptodate = 1;
977
978
	return 0;
}
David Teigland's avatar
David Teigland committed
979
980

/**
981
 * gfs2_rindex_update - Update the rindex if required
David Teigland's avatar
David Teigland committed
982
983
984
985
986
987
988
989
990
991
992
993
 * @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.
 *
994
 * Returns: 0 on succeess, error code otherwise
David Teigland's avatar
David Teigland committed
995
996
 */

997
int gfs2_rindex_update(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
998
{
999
	struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
David Teigland's avatar
David Teigland committed
1000
	struct gfs2_glock *gl = ip->i_gl;