rgrp.c 59.9 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
 * __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_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
567
568
569
570
571
572
573
 * @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
574
575
576
		gfs2_rs_deltree(ip->i_res);
		trace_gfs2_rs(ip, ip->i_res, TRACE_RS_DELETE);
		BUG_ON(ip->i_res->rs_free);
577
578
579
580
581
582
		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
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
/**
 * 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);
}

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

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

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

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

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

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

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

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

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

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

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

		bytes_left -= bytes;
	}

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

	return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return error;
}

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

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

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

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

926
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
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
982
/**
983
984
 * 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
985
986
987
988
989
990
991
 *
 * 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
 */

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