rgrp.c 60.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>
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

Bob Peterson's avatar
Bob Peterson committed
38
39
40
#define RSRV_CONTENTION_FACTOR 4
#define RGRP_RSRV_MAX_CONTENDERS 2

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

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

70
static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
71
			unsigned char old_state,
72
			struct gfs2_bitmap **rbi);
73

74
75
/**
 * gfs2_setbit - Set a bit in the bitmaps
76
77
78
 * @rgd: the resource group descriptor
 * @buf2: the clone buffer that holds the bitmaps
 * @bi: the bitmap structure
79
80
81
82
83
 * @block: the block to set
 * @new_state: the new state of the block
 *
 */

84
85
86
static inline void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buf2,
			       struct gfs2_bitmap *bi, u32 block,
			       unsigned char new_state)
87
{
88
	unsigned char *byte1, *byte2, *end, cur_state;
89
	unsigned int buflen = bi->bi_len;
90
	const unsigned int bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
91

92
93
	byte1 = bi->bi_bh->b_data + bi->bi_offset + (block / GFS2_NBBY);
	end = bi->bi_bh->b_data + bi->bi_offset + buflen;
94

95
	BUG_ON(byte1 >= end);
96

97
	cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
98

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

	if (buf2) {
116
		byte2 = buf2 + bi->bi_offset + (block / GFS2_NBBY);
117
118
119
		cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
		*byte2 ^= (cur_state ^ new_state) << bit;
	}
120
121
122
123
}

/**
 * gfs2_testbit - test a bit in the bitmaps
124
 * @rgd: the resource group descriptor
125
126
127
128
129
130
 * @buffer: the buffer that holds the bitmaps
 * @buflen: the length (in bytes) of the buffer
 * @block: the block to read
 *
 */

131
132
133
static inline unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd,
					 const unsigned char *buffer,
					 unsigned int buflen, u32 block)
134
{
135
136
	const unsigned char *byte, *end;
	unsigned char cur_state;
137
138
139
140
141
142
143
144
145
146
147
148
149
	unsigned int bit;

	byte = buffer + (block / GFS2_NBBY);
	bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
	end = buffer + buflen;

	gfs2_assert(rgd->rd_sbd, byte < end);

	cur_state = (*byte >> bit) & GFS2_BIT_MASK;

	return cur_state;
}

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

Bob Peterson's avatar
Bob Peterson committed
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
/**
 * 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)
{
	u64 startblk = gfs2_rs_startblk(rs);

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

/**
 * rs_find - Find a rgrp multi-block reservation that contains a given block
 * @rgd: The rgrp
 * @rgblk: The block we're looking for, relative to the rgrp
 */
static struct gfs2_blkreserv *rs_find(struct gfs2_rgrpd *rgd, u32 rgblk)
{
	struct rb_node **newn;
	int rc;
	u64 fsblk = rgblk + rgd->rd_data0;

	spin_lock(&rgd->rd_rsspin);
	newn = &rgd->rd_rstree.rb_node;
	while (*newn) {
		struct gfs2_blkreserv *cur =
			rb_entry(*newn, struct gfs2_blkreserv, rs_node);
		rc = rs_cmp(fsblk, 1, cur);
		if (rc < 0)
			newn = &((*newn)->rb_left);
		else if (rc > 0)
			newn = &((*newn)->rb_right);
		else {
			spin_unlock(&rgd->rd_rsspin);
			return cur;
		}
	}
	spin_unlock(&rgd->rd_rsspin);
	return NULL;
}

234
235
236
/**
 * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
 *       a block in a given allocation state.
237
 * @buf: the buffer that holds the bitmaps
238
 * @len: the length (in bytes) of the buffer
239
 * @goal: start search at this block's bit-pair (within @buffer)
240
 * @state: GFS2_BLKST_XXX the state of the block we're looking for.
241
242
243
 *
 * 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
244
245
246
247
248
 * 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
249
 * always ok to read a complete multiple of 64 bits at the end
250
 * of the block in case the end is no aligned to a natural boundary.
251
252
253
254
 *
 * Return: the block number (bitmap buffer scope) that was found
 */

255
256
static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
		       u32 goal, u8 state)
257
{
258
259
260
261
	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;
262
	u64 mask = 0x5555555555555555ULL;
263
264
265
266
267
268
269
270
271
	u32 bit;

	BUG_ON(state > 3);

	/* 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) {
272
		tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
273
		ptr++;
274
	}
275
276
277
278
279
280
281
	/* 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--;
282
	bit = __ffs64(tmp);
283
284
	bit /= 2;	/* two bits per entry in the bitmap */
	return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
285
286
287
288
}

/**
 * gfs2_bitcount - count the number of bits in a certain state
289
 * @rgd: the resource group descriptor
290
291
292
293
294
295
296
 * @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
 */

297
298
static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
			 unsigned int buflen, u8 state)
299
{
300
301
302
303
304
	const u8 *byte = buffer;
	const u8 *end = buffer + buflen;
	const u8 state1 = state << 2;
	const u8 state2 = state << 4;
	const u8 state3 = state << 6;
305
	u32 count = 0;
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320

	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
321
322
323
324
325
326
327
328
329
330
/**
 * 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;
331
	u32 length = rgd->rd_length;
332
	u32 count[4], tmp;
David Teigland's avatar
David Teigland committed
333
334
	int buf, x;

335
	memset(count, 0, 4 * sizeof(u32));
David Teigland's avatar
David Teigland committed
336
337
338
339
340
341
342
343
344
345
346

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

347
	if (count[0] != rgd->rd_free) {
David Teigland's avatar
David Teigland committed
348
349
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "free data mismatch:  %u != %u\n",
350
			       count[0], rgd->rd_free);
David Teigland's avatar
David Teigland committed
351
352
353
		return;
	}

354
	tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
355
	if (count[1] != tmp) {
David Teigland's avatar
David Teigland committed
356
357
358
359
360
361
		if (gfs2_consist_rgrpd(rgd))
			fs_err(sdp, "used data mismatch:  %u != %u\n",
			       count[1], tmp);
		return;
	}

362
	if (count[2] + count[3] != rgd->rd_dinodes) {
David Teigland's avatar
David Teigland committed
363
		if (gfs2_consist_rgrpd(rgd))
364
			fs_err(sdp, "used metadata mismatch:  %u != %u\n",
365
			       count[2] + count[3], rgd->rd_dinodes);
David Teigland's avatar
David Teigland committed
366
367
368
369
		return;
	}
}

370
static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
David Teigland's avatar
David Teigland committed
371
{
372
373
	u64 first = rgd->rd_data0;
	u64 last = first + rgd->rd_data;
374
	return first <= block && block < last;
David Teigland's avatar
David Teigland committed
375
376
377
378
379
}

/**
 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
 * @sdp: The GFS2 superblock
380
381
 * @blk: The data block number
 * @exact: True if this needs to be an exact match
David Teigland's avatar
David Teigland committed
382
383
384
385
 *
 * Returns: The resource group, or NULL if not found
 */

Steven Whitehouse's avatar
Steven Whitehouse committed
386
struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
David Teigland's avatar
David Teigland committed
387
{
Steven Whitehouse's avatar
Steven Whitehouse committed
388
	struct rb_node *n, *next;
389
	struct gfs2_rgrpd *cur;
David Teigland's avatar
David Teigland committed
390
391

	spin_lock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
392
393
394
395
	n = sdp->sd_rindex_tree.rb_node;
	while (n) {
		cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
		next = NULL;
396
		if (blk < cur->rd_addr)
Steven Whitehouse's avatar
Steven Whitehouse committed
397
			next = n->rb_left;
398
		else if (blk >= cur->rd_data0 + cur->rd_data)
Steven Whitehouse's avatar
Steven Whitehouse committed
399
400
			next = n->rb_right;
		if (next == NULL) {
David Teigland's avatar
David Teigland committed
401
			spin_unlock(&sdp->sd_rindex_spin);
Steven Whitehouse's avatar
Steven Whitehouse committed
402
403
404
405
406
407
			if (exact) {
				if (blk < cur->rd_addr)
					return NULL;
				if (blk >= cur->rd_data0 + cur->rd_data)
					return NULL;
			}
408
			return cur;
David Teigland's avatar
David Teigland committed
409
		}
Steven Whitehouse's avatar
Steven Whitehouse committed
410
		n = next;
David Teigland's avatar
David Teigland committed
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
	}
	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)
{
426
427
428
	const struct rb_node *n;
	struct gfs2_rgrpd *rgd;

429
	spin_lock(&sdp->sd_rindex_spin);
430
431
	n = rb_first(&sdp->sd_rindex_tree);
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
432
	spin_unlock(&sdp->sd_rindex_spin);
433
434

	return rgd;
David Teigland's avatar
David Teigland committed
435
436
437
438
}

/**
 * gfs2_rgrpd_get_next - get the next RG
439
 * @rgd: the resource group descriptor
David Teigland's avatar
David Teigland committed
440
441
442
443
444
445
 *
 * Returns: The next rgrp
 */

struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
{
446
447
448
449
450
451
452
453
454
455
	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
456
		return NULL;
457
458
459
460
	}
	rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
	spin_unlock(&sdp->sd_rindex_spin);
	return rgd;
David Teigland's avatar
David Teigland committed
461
462
}

463
464
465
466
467
468
469
470
471
472
473
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;
	}
}

474
475
476
477
478
479
480
/**
 * 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)
{
	int error = 0;
Bob Peterson's avatar
Bob Peterson committed
481
482
483
484
485
486
487
488
	struct gfs2_blkreserv *res;

	if (ip->i_res)
		return 0;

	res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
	if (!res)
		error = -ENOMEM;
489
490

	down_write(&ip->i_rw_mutex);
Bob Peterson's avatar
Bob Peterson committed
491
492
493
494
	if (ip->i_res)
		kmem_cache_free(gfs2_rsrv_cachep, res);
	else
		ip->i_res = res;
495
496
497
498
	up_write(&ip->i_rw_mutex);
	return error;
}

Bob Peterson's avatar
Bob Peterson committed
499
500
501
502
503
504
505
static void dump_rs(struct seq_file *seq, struct gfs2_blkreserv *rs)
{
	gfs2_print_dbg(seq, "  r: %llu s:%llu b:%u f:%u\n",
		       rs->rs_rgd->rd_addr, gfs2_rs_startblk(rs), rs->rs_biblk,
		       rs->rs_free);
}

506
/**
Bob Peterson's avatar
Bob Peterson committed
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
 * __rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
static void __rs_deltree(struct gfs2_blkreserv *rs)
{
	struct gfs2_rgrpd *rgd;

	if (!gfs2_rs_active(rs))
		return;

	rgd = rs->rs_rgd;
	/* We can't do this: The reason is that when the rgrp is invalidated,
	   it's in the "middle" of acquiring the glock, but the HOLDER bit
	   isn't set yet:
	   BUG_ON(!gfs2_glock_is_locked_by_me(rs->rs_rgd->rd_gl));*/
	trace_gfs2_rs(NULL, rs, TRACE_RS_TREEDEL);

	if (!RB_EMPTY_ROOT(&rgd->rd_rstree))
		rb_erase(&rs->rs_node, &rgd->rd_rstree);
	BUG_ON(!rgd->rd_rs_cnt);
	rgd->rd_rs_cnt--;

	if (rs->rs_free) {
		/* return reserved blocks to the rgrp and the ip */
		BUG_ON(rs->rs_rgd->rd_reserved < rs->rs_free);
		rs->rs_rgd->rd_reserved -= rs->rs_free;
		rs->rs_free = 0;
		clear_bit(GBF_FULL, &rs->rs_bi->bi_flags);
		smp_mb__after_clear_bit();
	}
	/* We can't change any of the step 1 or step 2 components of the rs.
	   E.g. We can't set rs_rgd to NULL because the rgd glock is held and
	   dequeued through this pointer.
	   Can't: atomic_set(&rs->rs_sizehint, 0);
	   Can't: rs->rs_requested = 0;
	   Can't: rs->rs_rgd = NULL;*/
	rs->rs_bi = NULL;
	rs->rs_biblk = 0;
}

/**
 * gfs2_rs_deltree - remove a multi-block reservation from the rgd tree
 * @rs: The reservation to remove
 *
 */
void gfs2_rs_deltree(struct gfs2_blkreserv *rs)
{
	struct gfs2_rgrpd *rgd;

	if (!gfs2_rs_active(rs))
		return;

	rgd = rs->rs_rgd;
	spin_lock(&rgd->rd_rsspin);
	__rs_deltree(rs);
	spin_unlock(&rgd->rd_rsspin);
}

/**
 * gfs2_rs_delete - delete a multi-block reservation
568
569
570
571
572
573
574
 * @ip: The inode for this reservation
 *
 */
void gfs2_rs_delete(struct gfs2_inode *ip)
{
	down_write(&ip->i_rw_mutex);
	if (ip->i_res) {
Bob Peterson's avatar
Bob Peterson committed
575
576
577
		gfs2_rs_deltree(ip->i_res);
		trace_gfs2_rs(ip, ip->i_res, TRACE_RS_DELETE);
		BUG_ON(ip->i_res->rs_free);
578
579
580
581
582
583
		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
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
/**
 * 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);
		__rs_deltree(rs);
	}
	spin_unlock(&rgd->rd_rsspin);
}

605
void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
606
{
607
	struct rb_node *n;
David Teigland's avatar
David Teigland committed
608
609
610
	struct gfs2_rgrpd *rgd;
	struct gfs2_glock *gl;

611
612
	while ((n = rb_first(&sdp->sd_rindex_tree))) {
		rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
David Teigland's avatar
David Teigland committed
613
614
		gl = rgd->rd_gl;

615
		rb_erase(n, &sdp->sd_rindex_tree);
David Teigland's avatar
David Teigland committed
616
617

		if (gl) {
618
			spin_lock(&gl->gl_spin);
619
			gl->gl_object = NULL;
620
			spin_unlock(&gl->gl_spin);
621
			gfs2_glock_add_to_lru(gl);
David Teigland's avatar
David Teigland committed
622
623
624
			gfs2_glock_put(gl);
		}

625
		gfs2_free_clones(rgd);
David Teigland's avatar
David Teigland committed
626
		kfree(rgd->rd_bits);
Bob Peterson's avatar
Bob Peterson committed
627
		return_all_reservations(rgd);
628
		kmem_cache_free(gfs2_rgrpd_cachep, rgd);
David Teigland's avatar
David Teigland committed
629
630
631
	}
}

632
633
634
635
636
637
638
639
640
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
641
642
643
644
645
646
647
648
649
650
651
652
653
/**
 * 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;
654
	u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
655
	u32 bytes_left, bytes;
David Teigland's avatar
David Teigland committed
656
657
	int x;

658
659
660
	if (!length)
		return -EINVAL;

661
	rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
David Teigland's avatar
David Teigland committed
662
663
664
	if (!rgd->rd_bits)
		return -ENOMEM;

665
	bytes_left = rgd->rd_bitbytes;
David Teigland's avatar
David Teigland committed
666
667
668
669

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

670
		bi->bi_flags = 0;
David Teigland's avatar
David Teigland committed
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
		/* 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);
687
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
688
689
690
			bi->bi_len = bytes;
		/* other blocks */
		} else {
691
692
			bytes = sdp->sd_sb.sb_bsize -
				sizeof(struct gfs2_meta_header);
David Teigland's avatar
David Teigland committed
693
			bi->bi_offset = sizeof(struct gfs2_meta_header);
694
			bi->bi_start = rgd->rd_bitbytes - bytes_left;
David Teigland's avatar
David Teigland committed
695
696
697
698
699
700
701
702
703
704
705
			bi->bi_len = bytes;
		}

		bytes_left -= bytes;
	}

	if (bytes_left) {
		gfs2_consist_rgrpd(rgd);
		return -EIO;
	}
	bi = rgd->rd_bits + (length - 1);
706
	if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
David Teigland's avatar
David Teigland committed
707
		if (gfs2_consist_rgrpd(rgd)) {
708
			gfs2_rindex_print(rgd);
David Teigland's avatar
David Teigland committed
709
710
711
712
713
714
715
716
717
			fs_err(sdp, "start=%u len=%u offset=%u\n",
			       bi->bi_start, bi->bi_len, bi->bi_offset);
		}
		return -EIO;
	}

	return 0;
}

718
719
/**
 * gfs2_ri_total - Total up the file system space, according to the rindex.
720
 * @sdp: the filesystem
721
722
723
724
725
726
727
728
729
730
731
732
733
 *
 */
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);

734
		if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
735
			break;
736
		error = gfs2_internal_read(ip, buf, &pos,
737
738
739
					   sizeof(struct gfs2_rindex));
		if (error != sizeof(struct gfs2_rindex))
			break;
740
		total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
741
742
743
744
	}
	return total_data;
}

Bob Peterson's avatar
Bob Peterson committed
745
static int rgd_insert(struct gfs2_rgrpd *rgd)
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
{
	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
761
			return -EEXIST;
762
763
764
765
	}

	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
766
767
	sdp->sd_rgrps++;
	return 0;
768
769
}

David Teigland's avatar
David Teigland committed
770
/**
771
 * read_rindex_entry - Pull in a new resource index entry from the disk
772
 * @ip: Pointer to the rindex inode
David Teigland's avatar
David Teigland committed
773
 *
774
 * Returns: 0 on success, > 0 on EOF, error code otherwise
775
776
 */

777
static int read_rindex_entry(struct gfs2_inode *ip)
778
779
780
{
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
	loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
781
	struct gfs2_rindex buf;
782
783
784
	int error;
	struct gfs2_rgrpd *rgd;

785
786
787
	if (pos >= i_size_read(&ip->i_inode))
		return 1;

788
	error = gfs2_internal_read(ip, (char *)&buf, &pos,
789
				   sizeof(struct gfs2_rindex));
790
791
792

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

794
	rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
795
796
797
798
799
	error = -ENOMEM;
	if (!rgd)
		return error;

	rgd->rd_sbd = sdp;
800
801
802
803
804
	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
805
	spin_lock_init(&rgd->rd_rsspin);
806

807
808
	error = compute_bitstructs(rgd);
	if (error)
809
		goto fail;
810

811
	error = gfs2_glock_get(sdp, rgd->rd_addr,
812
813
			       &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
	if (error)
814
		goto fail;
815
816

	rgd->rd_gl->gl_object = rgd;
817
	rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lvb;
818
	rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
819
820
	if (rgd->rd_data > sdp->sd_max_rg_data)
		sdp->sd_max_rg_data = rgd->rd_data;
821
	spin_lock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
822
	error = rgd_insert(rgd);
823
	spin_unlock(&sdp->sd_rindex_spin);
Bob Peterson's avatar
Bob Peterson committed
824
825
826
827
	if (!error)
		return 0;

	error = 0; /* someone else read in the rgrp; free it and ignore it */
828
	gfs2_glock_put(rgd->rd_gl);
829
830
831
832

fail:
	kfree(rgd->rd_bits);
	kmem_cache_free(gfs2_rgrpd_cachep, rgd);
833
834
835
836
837
838
839
	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
840
841
842
 * Returns: 0 on successful update, error code otherwise
 */

843
static int gfs2_ri_update(struct gfs2_inode *ip)
David Teigland's avatar
David Teigland committed
844
{
845
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
David Teigland's avatar
David Teigland committed
846
847
	int error;

848
	do {
849
		error = read_rindex_entry(ip);
850
851
852
853
	} while (error == 0);

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

855
	sdp->sd_rindex_uptodate = 1;
856
857
	return 0;
}
David Teigland's avatar
David Teigland committed
858
859

/**
860
 * gfs2_rindex_update - Update the rindex if required
David Teigland's avatar
David Teigland committed
861
862
863
864
865
866
867
868
869
870
871
872
 * @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.
 *
873
 * Returns: 0 on succeess, error code otherwise
David Teigland's avatar
David Teigland committed
874
875
 */

876
int gfs2_rindex_update(struct gfs2_sbd *sdp)
David Teigland's avatar
David Teigland committed
877
{
878
	struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
David Teigland's avatar
David Teigland committed
879
	struct gfs2_glock *gl = ip->i_gl;
880
881
	struct gfs2_holder ri_gh;
	int error = 0;
882
	int unlock_required = 0;
David Teigland's avatar
David Teigland committed
883
884

	/* Read new copy from disk if we don't have the latest */
885
	if (!sdp->sd_rindex_uptodate) {
886
887
888
		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
889
				return error;
890
891
			unlock_required = 1;
		}
892
		if (!sdp->sd_rindex_uptodate)
David Teigland's avatar
David Teigland committed
893
			error = gfs2_ri_update(ip);
894
895
		if (unlock_required)
			gfs2_glock_dq_uninit(&ri_gh);
David Teigland's avatar
David Teigland committed
896
897
898
899
900
	}

	return error;
}

901
static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
902
903
{
	const struct gfs2_rgrp *str = buf;
904
	u32 rg_flags;
905

906
	rg_flags = be32_to_cpu(str->rg_flags);
907
	rg_flags &= ~GFS2_RDF_MASK;
908
909
	rgd->rd_flags &= GFS2_RDF_MASK;
	rgd->rd_flags |= rg_flags;
910
	rgd->rd_free = be32_to_cpu(str->rg_free);
911
	rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
912
	rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
913
914
}

915
static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
916
917
918
{
	struct gfs2_rgrp *str = buf;

919
	str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
920
	str->rg_free = cpu_to_be32(rgd->rd_free);
921
	str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
922
	str->__pad = cpu_to_be32(0);
923
	str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
924
925
926
	memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
}

927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
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)
{
	const struct gfs2_rgrp *str = buf;

	rgl->rl_magic = cpu_to_be32(GFS2_MAGIC);
	rgl->rl_flags = str->rg_flags;
	rgl->rl_free = str->rg_free;
	rgl->rl_dinodes = str->rg_dinodes;
	rgl->rl_igeneration = str->rg_igeneration;
	rgl->__pad = 0UL;
}

static void update_rgrp_lvb_unlinked(struct gfs2_rgrpd *rgd, u32 change)
{
	struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
	u32 unlinked = be32_to_cpu(rgl->rl_unlinked) + change;
	rgl->rl_unlinked = cpu_to_be32(unlinked);
}

static u32 count_unlinked(struct gfs2_rgrpd *rgd)
{
	struct gfs2_bitmap *bi;
	const u32 length = rgd->rd_length;
	const u8 *buffer = NULL;
	u32 i, goal, count = 0;

	for (i = 0, bi = rgd->rd_bits; i < length; i++, bi++) {
		goal = 0;
		buffer = bi->bi_bh->b_data + bi->bi_offset;
		WARN_ON(!buffer_uptodate(bi->bi_bh));
		while (goal < bi->bi_len * GFS2_NBBY) {
			goal = gfs2_bitfit(buffer, bi->bi_len, goal,
					   GFS2_BLKST_UNLINKED);
			if (goal == BFITNOENT)
				break;
			count++;
			goal++;
		}
	}

	return count;
}


David Teigland's avatar
David Teigland committed
983
/**
984
985
 * gfs2_rgrp_bh_get - Read in a RG's header and bitmaps
 * @rgd: the struct gfs2_rgrpd describing the RG to read in
David Teigland's avatar
David Teigland committed
986
987
988
989
990
991
992
 *
 * Read in all of a Resource Group's header and bitmap blocks.
 * Caller must eventually call gfs2_rgrp_relse() to free the bitmaps.
 *
 * Returns: errno
 */

993
int gfs2_rgrp_bh_get(struct gfs2_rgrpd *rgd)
David Teigland's avatar
David Teigland committed
994
995
996
{
	struct gfs2_sbd *sdp = rgd->rd_sbd;
	struct gfs2_glock *gl = rgd->rd_gl;
997
	unsigned int length = rgd->rd_length;
David Teigland's avatar
David Teigland committed
998
999
1000
	struct gfs2_bitmap *bi;
	unsigned int x, y;
	int error;