ialloc.c 37.1 KB
Newer Older
1
/*
2
 *  linux/fs/ext4/ialloc.c
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
 *
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *
 *  BSD ufs-inspired inode and directory allocation by
 *  Stephen Tweedie (sct@redhat.com), 1993
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 */

#include <linux/time.h>
#include <linux/fs.h>
#include <linux/stat.h>
#include <linux/string.h>
#include <linux/quotaops.h>
#include <linux/buffer_head.h>
#include <linux/random.h>
#include <linux/bitops.h>
23
#include <linux/blkdev.h>
24
#include <asm/byteorder.h>
25

26 27
#include "ext4.h"
#include "ext4_jbd2.h"
28 29 30
#include "xattr.h"
#include "acl.h"

31 32
#include <trace/events/ext4.h>

33 34 35 36 37 38 39 40 41 42 43 44 45 46
/*
 * ialloc.c contains the inodes allocation and deallocation routines
 */

/*
 * The free inodes are managed by bitmaps.  A file system contains several
 * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
 * block for inodes, N blocks for the inode table and data blocks.
 *
 * The file system contains group descriptors which are located after the
 * super block.  Each descriptor contains the number of the bitmap block and
 * the free blocks count in the block.
 */

A
Andreas Dilger 已提交
47 48 49 50 51
/*
 * To avoid calling the atomic setbit hundreds or thousands of times, we only
 * need to use it within a single byte (to ensure we get endianness right).
 * We can use memset for the rest of the bitmap as there are no other users.
 */
52
void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
A
Andreas Dilger 已提交
53 54 55 56 57 58 59 60 61 62 63 64 65 66
{
	int i;

	if (start_bit >= end_bit)
		return;

	ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
	for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
		ext4_set_bit(i, bitmap);
	if (i < end_bit)
		memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
}

/* Initializes an uninitialized inode bitmap */
67 68 69 70
static unsigned ext4_init_inode_bitmap(struct super_block *sb,
				       struct buffer_head *bh,
				       ext4_group_t block_group,
				       struct ext4_group_desc *gdp)
A
Andreas Dilger 已提交
71
{
72
	struct ext4_group_info *grp;
73
	struct ext4_sb_info *sbi = EXT4_SB(sb);
A
Andreas Dilger 已提交
74 75 76 77
	J_ASSERT_BH(bh, buffer_locked(bh));

	/* If checksum is bad mark all blocks and inodes use to prevent
	 * allocation, essentially implementing a per-group read-only flag. */
78
	if (!ext4_group_desc_csum_verify(sb, block_group, gdp)) {
79
		ext4_error(sb, "Checksum bad for group %u", block_group);
80
		grp = ext4_get_group_info(sb, block_group);
81 82 83
		if (!EXT4_MB_GRP_BBITMAP_CORRUPT(grp))
			percpu_counter_sub(&sbi->s_freeclusters_counter,
					   grp->bb_free);
84
		set_bit(EXT4_GROUP_INFO_BBITMAP_CORRUPT_BIT, &grp->bb_state);
85 86 87 88 89 90
		if (!EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			int count;
			count = ext4_free_inodes_count(sb, gdp);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
91
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
A
Andreas Dilger 已提交
92 93 94 95
		return 0;
	}

	memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
96
	ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), sb->s_blocksize * 8,
A
Andreas Dilger 已提交
97
			bh->b_data);
98 99
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
100
	ext4_group_desc_csum_set(sb, block_group, gdp);
A
Andreas Dilger 已提交
101 102 103

	return EXT4_INODES_PER_GROUP(sb);
}
104

105 106 107 108 109 110 111 112 113 114
void ext4_end_bitmap_read(struct buffer_head *bh, int uptodate)
{
	if (uptodate) {
		set_buffer_uptodate(bh);
		set_bitmap_uptodate(bh);
	}
	unlock_buffer(bh);
	put_bh(bh);
}

115 116 117 118 119 120 121
/*
 * Read the inode allocation bitmap for a given block_group, reading
 * into the specified slot in the superblock's bitmap cache.
 *
 * Return buffer_head of bitmap on success or NULL.
 */
static struct buffer_head *
122
ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
123
{
124
	struct ext4_group_desc *desc;
125
	struct buffer_head *bh = NULL;
126
	ext4_fsblk_t bitmap_blk;
127
	struct ext4_group_info *grp;
128
	struct ext4_sb_info *sbi = EXT4_SB(sb);
129

130
	desc = ext4_get_group_desc(sb, block_group, NULL);
131
	if (!desc)
132
		return NULL;
133

134 135 136
	bitmap_blk = ext4_inode_bitmap(sb, desc);
	bh = sb_getblk(sb, bitmap_blk);
	if (unlikely(!bh)) {
137
		ext4_error(sb, "Cannot read inode bitmap - "
138
			    "block_group = %u, inode_bitmap = %llu",
139 140 141
			    block_group, bitmap_blk);
		return NULL;
	}
142
	if (bitmap_uptodate(bh))
143
		goto verify;
144

145
	lock_buffer(bh);
146 147
	if (bitmap_uptodate(bh)) {
		unlock_buffer(bh);
148
		goto verify;
149
	}
150

151
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
152
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
153
		ext4_init_inode_bitmap(sb, bh, block_group, desc);
154
		set_bitmap_uptodate(bh);
155
		set_buffer_uptodate(bh);
156
		set_buffer_verified(bh);
157
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
158
		unlock_buffer(bh);
159
		return bh;
A
Andreas Dilger 已提交
160
	}
161
	ext4_unlock_group(sb, block_group);
162

163 164 165 166 167 168 169
	if (buffer_uptodate(bh)) {
		/*
		 * if not uninit if bh is uptodate,
		 * bitmap is also uptodate
		 */
		set_bitmap_uptodate(bh);
		unlock_buffer(bh);
170
		goto verify;
171 172
	}
	/*
173
	 * submit the buffer_head for reading
174
	 */
175
	trace_ext4_load_inode_bitmap(sb, block_group);
176 177
	bh->b_end_io = ext4_end_bitmap_read;
	get_bh(bh);
178
	submit_bh(READ | REQ_META | REQ_PRIO, bh);
179 180
	wait_on_buffer(bh);
	if (!buffer_uptodate(bh)) {
181
		put_bh(bh);
182
		ext4_error(sb, "Cannot read inode bitmap - "
183 184
			   "block_group = %u, inode_bitmap = %llu",
			   block_group, bitmap_blk);
185 186
		return NULL;
	}
187 188 189 190 191 192 193 194 195 196

verify:
	ext4_lock_group(sb, block_group);
	if (!buffer_verified(bh) &&
	    !ext4_inode_bitmap_csum_verify(sb, block_group, desc, bh,
					   EXT4_INODES_PER_GROUP(sb) / 8)) {
		ext4_unlock_group(sb, block_group);
		put_bh(bh);
		ext4_error(sb, "Corrupt inode bitmap - block_group = %u, "
			   "inode_bitmap = %llu", block_group, bitmap_blk);
197
		grp = ext4_get_group_info(sb, block_group);
198 199 200 201 202 203
		if (!EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			int count;
			count = ext4_free_inodes_count(sb, desc);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
204
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
205 206 207 208
		return NULL;
	}
	ext4_unlock_group(sb, block_group);
	set_buffer_verified(bh);
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
	return bh;
}

/*
 * NOTE! When we get the inode, we're the only people
 * that have access to it, and as such there are no
 * race conditions we have to worry about. The inode
 * is not on the hash-lists, and it cannot be reached
 * through the filesystem because the directory entry
 * has been deleted earlier.
 *
 * HOWEVER: we must make sure that we get no aliases,
 * which means that we have to call "clear_inode()"
 * _before_ we mark the inode not in use in the inode
 * bitmaps. Otherwise a newly created file might use
 * the same inode number (not actually the same pointer
 * though), and then we'd have two inodes sharing the
 * same inode number and space on the harddisk.
 */
228
void ext4_free_inode(handle_t *handle, struct inode *inode)
229
{
230
	struct super_block *sb = inode->i_sb;
231 232 233 234
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
235
	ext4_group_t block_group;
236
	unsigned long bit;
237 238
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
239
	struct ext4_sb_info *sbi;
240
	int fatal = 0, err, count, cleared;
241
	struct ext4_group_info *grp;
242

243 244 245
	if (!sb) {
		printk(KERN_ERR "EXT4-fs: %s:%d: inode on "
		       "nonexistent device\n", __func__, __LINE__);
246 247
		return;
	}
248 249 250 251
	if (atomic_read(&inode->i_count) > 1) {
		ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: count=%d",
			 __func__, __LINE__, inode->i_ino,
			 atomic_read(&inode->i_count));
252 253
		return;
	}
254 255 256
	if (inode->i_nlink) {
		ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n",
			 __func__, __LINE__, inode->i_ino, inode->i_nlink);
257 258
		return;
	}
259
	sbi = EXT4_SB(sb);
260 261

	ino = inode->i_ino;
262
	ext4_debug("freeing inode %lu\n", ino);
263
	trace_ext4_free_inode(inode);
264 265 266 267 268

	/*
	 * Note: we must free any quota before locking the superblock,
	 * as writing the quota to disk may need the lock as well.
	 */
269
	dquot_initialize(inode);
270
	ext4_xattr_delete_inode(handle, inode);
271
	dquot_free_inode(inode);
272
	dquot_drop(inode);
273 274 275 276

	is_directory = S_ISDIR(inode->i_mode);

	/* Do this BEFORE marking the inode not in use or returning an error */
A
Al Viro 已提交
277
	ext4_clear_inode(inode);
278

279 280
	es = EXT4_SB(sb)->s_es;
	if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
281
		ext4_error(sb, "reserved or nonexistent inode %lu", ino);
282 283
		goto error_return;
	}
284 285
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
286
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
287 288 289
	/* Don't bother if the inode bitmap is corrupt. */
	grp = ext4_get_group_info(sb, block_group);
	if (unlikely(EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) || !bitmap_bh)
290 291 292
		goto error_return;

	BUFFER_TRACE(bitmap_bh, "get_write_access");
293
	fatal = ext4_journal_get_write_access(handle, bitmap_bh);
294 295 296
	if (fatal)
		goto error_return;

297 298 299
	fatal = -ESRCH;
	gdp = ext4_get_group_desc(sb, block_group, &bh2);
	if (gdp) {
300
		BUFFER_TRACE(bh2, "get_write_access");
301
		fatal = ext4_journal_get_write_access(handle, bh2);
302 303
	}
	ext4_lock_group(sb, block_group);
304
	cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data);
305 306 307 308
	if (fatal || !cleared) {
		ext4_unlock_group(sb, block_group);
		goto out;
	}
309

310 311 312 313 314 315
	count = ext4_free_inodes_count(sb, gdp) + 1;
	ext4_free_inodes_set(sb, gdp, count);
	if (is_directory) {
		count = ext4_used_dirs_count(sb, gdp) - 1;
		ext4_used_dirs_set(sb, gdp, count);
		percpu_counter_dec(&sbi->s_dirs_counter);
316
	}
317 318
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
319
	ext4_group_desc_csum_set(sb, block_group, gdp);
320
	ext4_unlock_group(sb, block_group);
321

322 323 324
	percpu_counter_inc(&sbi->s_freeinodes_counter);
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t f = ext4_flex_group(sbi, block_group);
325

326 327 328
		atomic_inc(&sbi->s_flex_groups[f].free_inodes);
		if (is_directory)
			atomic_dec(&sbi->s_flex_groups[f].used_dirs);
329
	}
330 331 332 333 334 335 336 337
	BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
	fatal = ext4_handle_dirty_metadata(handle, NULL, bh2);
out:
	if (cleared) {
		BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
		err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
		if (!fatal)
			fatal = err;
338
	} else {
339
		ext4_error(sb, "bit already cleared for inode %lu", ino);
340
		if (gdp && !EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
341 342 343 344 345
			int count;
			count = ext4_free_inodes_count(sb, gdp);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
346 347
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
	}
348

349 350
error_return:
	brelse(bitmap_bh);
351
	ext4_std_error(sb, fatal);
352 353
}

354
struct orlov_stats {
355
	__u64 free_clusters;
356 357 358 359 360 361 362 363 364
	__u32 free_inodes;
	__u32 used_dirs;
};

/*
 * Helper function for Orlov's allocator; returns critical information
 * for a particular block group or flex_bg.  If flex_size is 1, then g
 * is a block group number; otherwise it is flex_bg number.
 */
365 366
static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
			    int flex_size, struct orlov_stats *stats)
367 368
{
	struct ext4_group_desc *desc;
369
	struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
370

371 372
	if (flex_size > 1) {
		stats->free_inodes = atomic_read(&flex_group[g].free_inodes);
373
		stats->free_clusters = atomic64_read(&flex_group[g].free_clusters);
374 375 376
		stats->used_dirs = atomic_read(&flex_group[g].used_dirs);
		return;
	}
377

378 379 380
	desc = ext4_get_group_desc(sb, g, NULL);
	if (desc) {
		stats->free_inodes = ext4_free_inodes_count(sb, desc);
381
		stats->free_clusters = ext4_free_group_clusters(sb, desc);
382 383 384
		stats->used_dirs = ext4_used_dirs_count(sb, desc);
	} else {
		stats->free_inodes = 0;
385
		stats->free_clusters = 0;
386
		stats->used_dirs = 0;
387 388 389
	}
}

390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
/*
 * Orlov's allocator for directories.
 *
 * We always try to spread first-level directories.
 *
 * If there are blockgroups with both free inodes and free blocks counts
 * not worse than average we return one with smallest directory count.
 * Otherwise we simply return a random group.
 *
 * For the rest rules look so:
 *
 * It's OK to put directory into a group unless
 * it has too many directories already (max_dirs) or
 * it has too few free inodes left (min_inodes) or
 * it has too few free blocks left (min_blocks) or
405
 * Parent's group is preferred, if it doesn't satisfy these
406 407 408 409 410
 * conditions we search cyclically through the rest. If none
 * of the groups look good we just look for a group with more
 * free inodes than average (starting at parent's group).
 */

411
static int find_group_orlov(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
412
			    ext4_group_t *group, umode_t mode,
413
			    const struct qstr *qstr)
414
{
415
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
416
	struct ext4_sb_info *sbi = EXT4_SB(sb);
417
	ext4_group_t real_ngroups = ext4_get_groups_count(sb);
418
	int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
419
	unsigned int freei, avefreei, grp_free;
420
	ext4_fsblk_t freeb, avefreec;
421
	unsigned int ndirs;
422
	int max_dirs, min_inodes;
423
	ext4_grpblk_t min_clusters;
424
	ext4_group_t i, grp, g, ngroups;
425
	struct ext4_group_desc *desc;
426 427
	struct orlov_stats stats;
	int flex_size = ext4_flex_bg_size(sbi);
428
	struct dx_hash_info hinfo;
429

430
	ngroups = real_ngroups;
431
	if (flex_size > 1) {
432
		ngroups = (real_ngroups + flex_size - 1) >>
433 434 435
			sbi->s_log_groups_per_flex;
		parent_group >>= sbi->s_log_groups_per_flex;
	}
436 437 438

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
439 440
	freeb = EXT4_C2B(sbi,
		percpu_counter_read_positive(&sbi->s_freeclusters_counter));
441 442
	avefreec = freeb;
	do_div(avefreec, ngroups);
443 444
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

445
	if (S_ISDIR(mode) &&
446
	    ((parent == d_inode(sb->s_root)) ||
447
	     (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
448
		int best_ndir = inodes_per_group;
449
		int ret = -1;
450

451 452 453 454 455 456
		if (qstr) {
			hinfo.hash_version = DX_HASH_HALF_MD4;
			hinfo.seed = sbi->s_hash_seed;
			ext4fs_dirhash(qstr->name, qstr->len, &hinfo);
			grp = hinfo.hash;
		} else
457
			grp = prandom_u32();
458
		parent_group = (unsigned)grp % ngroups;
459
		for (i = 0; i < ngroups; i++) {
460 461 462
			g = (parent_group + i) % ngroups;
			get_orlov_stats(sb, g, flex_size, &stats);
			if (!stats.free_inodes)
463
				continue;
464
			if (stats.used_dirs >= best_ndir)
465
				continue;
466
			if (stats.free_inodes < avefreei)
467
				continue;
468
			if (stats.free_clusters < avefreec)
469
				continue;
470
			grp = g;
471
			ret = 0;
472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
			best_ndir = stats.used_dirs;
		}
		if (ret)
			goto fallback;
	found_flex_bg:
		if (flex_size == 1) {
			*group = grp;
			return 0;
		}

		/*
		 * We pack inodes at the beginning of the flexgroup's
		 * inode tables.  Block allocation decisions will do
		 * something similar, although regular files will
		 * start at 2nd block group of the flexgroup.  See
		 * ext4_ext_find_goal() and ext4_find_near().
		 */
		grp *= flex_size;
		for (i = 0; i < flex_size; i++) {
491
			if (grp+i >= real_ngroups)
492 493 494 495 496 497
				break;
			desc = ext4_get_group_desc(sb, grp+i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = grp+i;
				return 0;
			}
498 499 500 501 502
		}
		goto fallback;
	}

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
503 504 505
	min_inodes = avefreei - inodes_per_group*flex_size / 4;
	if (min_inodes < 1)
		min_inodes = 1;
506
	min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
507 508 509 510 511 512 513 514 515 516

	/*
	 * Start looking in the flex group where we last allocated an
	 * inode for this parent directory
	 */
	if (EXT4_I(parent)->i_last_alloc_group != ~0) {
		parent_group = EXT4_I(parent)->i_last_alloc_group;
		if (flex_size > 1)
			parent_group >>= sbi->s_log_groups_per_flex;
	}
517 518

	for (i = 0; i < ngroups; i++) {
519 520 521
		grp = (parent_group + i) % ngroups;
		get_orlov_stats(sb, grp, flex_size, &stats);
		if (stats.used_dirs >= max_dirs)
522
			continue;
523
		if (stats.free_inodes < min_inodes)
524
			continue;
525
		if (stats.free_clusters < min_clusters)
526
			continue;
527
		goto found_flex_bg;
528 529 530
	}

fallback:
531
	ngroups = real_ngroups;
532
	avefreei = freei / ngroups;
533
fallback_retry:
534
	parent_group = EXT4_I(parent)->i_block_group;
535
	for (i = 0; i < ngroups; i++) {
536 537
		grp = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, grp, NULL);
538 539 540 541 542 543
		if (desc) {
			grp_free = ext4_free_inodes_count(sb, desc);
			if (grp_free && grp_free >= avefreei) {
				*group = grp;
				return 0;
			}
544
		}
545 546 547 548 549 550 551 552
	}

	if (avefreei) {
		/*
		 * The free-inodes counter is approximate, and for really small
		 * filesystems the above test can fail to find any blockgroups
		 */
		avefreei = 0;
553
		goto fallback_retry;
554 555 556 557 558
	}

	return -1;
}

559
static int find_group_other(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
560
			    ext4_group_t *group, umode_t mode)
561
{
562
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
563
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
564
	struct ext4_group_desc *desc;
565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
	int flex_size = ext4_flex_bg_size(EXT4_SB(sb));

	/*
	 * Try to place the inode is the same flex group as its
	 * parent.  If we can't find space, use the Orlov algorithm to
	 * find another flex group, and store that information in the
	 * parent directory's inode information so that use that flex
	 * group for future allocations.
	 */
	if (flex_size > 1) {
		int retry = 0;

	try_again:
		parent_group &= ~(flex_size-1);
		last = parent_group + flex_size;
		if (last > ngroups)
			last = ngroups;
		for  (i = parent_group; i < last; i++) {
			desc = ext4_get_group_desc(sb, i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = i;
				return 0;
			}
		}
		if (!retry && EXT4_I(parent)->i_last_alloc_group != ~0) {
			retry = 1;
			parent_group = EXT4_I(parent)->i_last_alloc_group;
			goto try_again;
		}
		/*
		 * If this didn't work, use the Orlov search algorithm
		 * to find a new flex group; we pass in the mode to
		 * avoid the topdir algorithms.
		 */
		*group = parent_group + flex_size;
		if (*group > ngroups)
			*group = 0;
602
		return find_group_orlov(sb, parent, group, mode, NULL);
603
	}
604 605 606 607

	/*
	 * Try to place the inode in its parent directory
	 */
608 609
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
610
	if (desc && ext4_free_inodes_count(sb, desc) &&
611
	    ext4_free_group_clusters(sb, desc))
612
		return 0;
613 614 615 616 617 618 619 620 621 622

	/*
	 * We're going to place this inode in a different blockgroup from its
	 * parent.  We want to cause files in a common directory to all land in
	 * the same blockgroup.  But we want files which are in a different
	 * directory which shares a blockgroup with our parent to land in a
	 * different blockgroup.
	 *
	 * So add our directory's i_ino into the starting point for the hash.
	 */
623
	*group = (*group + parent->i_ino) % ngroups;
624 625 626 627 628 629

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
630 631 632 633
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
634
		if (desc && ext4_free_inodes_count(sb, desc) &&
635
		    ext4_free_group_clusters(sb, desc))
636
			return 0;
637 638 639 640 641 642
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
643
	*group = parent_group;
644
	for (i = 0; i < ngroups; i++) {
645 646 647
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
648
		if (desc && ext4_free_inodes_count(sb, desc))
649
			return 0;
650 651 652 653 654
	}

	return -1;
}

655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699
/*
 * In no journal mode, if an inode has recently been deleted, we want
 * to avoid reusing it until we're reasonably sure the inode table
 * block has been written back to disk.  (Yes, these values are
 * somewhat arbitrary...)
 */
#define RECENTCY_MIN	5
#define RECENTCY_DIRTY	30

static int recently_deleted(struct super_block *sb, ext4_group_t group, int ino)
{
	struct ext4_group_desc	*gdp;
	struct ext4_inode	*raw_inode;
	struct buffer_head	*bh;
	unsigned long		dtime, now;
	int	inodes_per_block = EXT4_SB(sb)->s_inodes_per_block;
	int	offset, ret = 0, recentcy = RECENTCY_MIN;

	gdp = ext4_get_group_desc(sb, group, NULL);
	if (unlikely(!gdp))
		return 0;

	bh = sb_getblk(sb, ext4_inode_table(sb, gdp) +
		       (ino / inodes_per_block));
	if (unlikely(!bh) || !buffer_uptodate(bh))
		/*
		 * If the block is not in the buffer cache, then it
		 * must have been written out.
		 */
		goto out;

	offset = (ino % inodes_per_block) * EXT4_INODE_SIZE(sb);
	raw_inode = (struct ext4_inode *) (bh->b_data + offset);
	dtime = le32_to_cpu(raw_inode->i_dtime);
	now = get_seconds();
	if (buffer_dirty(bh))
		recentcy += RECENTCY_DIRTY;

	if (dtime && (dtime < now) && (now < dtime + recentcy))
		ret = 1;
out:
	brelse(bh);
	return ret;
}

700 701 702 703 704 705 706 707 708 709
/*
 * There are two policies for allocating an inode.  If the new inode is
 * a directory, then a forward search is made for a block group with both
 * free space and a low directory-to-inode ratio; if that fails, then of
 * the groups with above-average free space, that group with the fewest
 * directories already is chosen.
 *
 * For other inodes, search forward from the parent directory's block
 * group to find a free inode.
 */
710 711 712 713
struct inode *__ext4_new_inode(handle_t *handle, struct inode *dir,
			       umode_t mode, const struct qstr *qstr,
			       __u32 goal, uid_t *owner, int handle_type,
			       unsigned int line_no, int nblocks)
714 715
{
	struct super_block *sb;
A
Aneesh Kumar K.V 已提交
716 717
	struct buffer_head *inode_bitmap_bh = NULL;
	struct buffer_head *group_desc_bh;
718
	ext4_group_t ngroups, group = 0;
719
	unsigned long ino = 0;
720 721
	struct inode *inode;
	struct ext4_group_desc *gdp = NULL;
722 723
	struct ext4_inode_info *ei;
	struct ext4_sb_info *sbi;
724
	int ret2, err = 0;
725
	struct inode *ret;
726
	ext4_group_t i;
727
	ext4_group_t flex_group;
728
	struct ext4_group_info *grp;
729 730 731 732 733 734

	/* Cannot create files in a deleted directory */
	if (!dir || !dir->i_nlink)
		return ERR_PTR(-EPERM);

	sb = dir->i_sb;
735
	ngroups = ext4_get_groups_count(sb);
736
	trace_ext4_request_inode(dir, mode);
737 738 739
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
740 741
	ei = EXT4_I(inode);
	sbi = EXT4_SB(sb);
742

743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759
	/*
	 * Initalize owners and quota early so that we don't have to account
	 * for quota initialization worst case in standard inode creating
	 * transaction
	 */
	if (owner) {
		inode->i_mode = mode;
		i_uid_write(inode, owner[0]);
		i_gid_write(inode, owner[1]);
	} else if (test_opt(sb, GRPID)) {
		inode->i_mode = mode;
		inode->i_uid = current_fsuid();
		inode->i_gid = dir->i_gid;
	} else
		inode_init_owner(inode, dir, mode);
	dquot_initialize(inode);

760 761 762
	if (!goal)
		goal = sbi->s_inode_goal;

763
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
764 765 766 767 768 769
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

L
Lukas Czerner 已提交
770 771 772
	if (S_ISDIR(mode))
		ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
	else
773
		ret2 = find_group_other(sb, dir, &group, mode);
774

775
got_group:
776
	EXT4_I(dir)->i_last_alloc_group = group;
777
	err = -ENOSPC;
778
	if (ret2 == -1)
779 780
		goto out;

781 782 783 784 785
	/*
	 * Normally we will only go through one pass of this loop,
	 * unless we get unlucky and it turns out the group we selected
	 * had its last inode grabbed by someone else.
	 */
786
	for (i = 0; i < ngroups; i++, ino = 0) {
787 788
		err = -EIO;

A
Aneesh Kumar K.V 已提交
789
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
790
		if (!gdp)
791
			goto out;
792

793 794 795 796 797 798 799 800 801
		/*
		 * Check free inodes count before loading bitmap.
		 */
		if (ext4_free_inodes_count(sb, gdp) == 0) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

802 803 804 805 806 807 808 809
		grp = ext4_get_group_info(sb, group);
		/* Skip groups with already-known suspicious inode tables */
		if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

A
Aneesh Kumar K.V 已提交
810 811
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
812 813 814 815 816 817
		/* Skip groups with suspicious inode tables */
		if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp) || !inode_bitmap_bh) {
			if (++group == ngroups)
				group = 0;
			continue;
		}
818 819

repeat_in_this_group:
820
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
821 822
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);
823 824
		if (ino >= EXT4_INODES_PER_GROUP(sb))
			goto next_group;
825 826 827 828 829
		if (group == 0 && (ino+1) < EXT4_FIRST_INO(sb)) {
			ext4_error(sb, "reserved inode found cleared - "
				   "inode=%lu", ino + 1);
			continue;
		}
830 831 832 833 834
		if ((EXT4_SB(sb)->s_journal == NULL) &&
		    recently_deleted(sb, group, ino)) {
			ino++;
			goto next_inode;
		}
835 836 837
		if (!handle) {
			BUG_ON(nblocks <= 0);
			handle = __ext4_journal_start_sb(dir->i_sb, line_no,
838 839
							 handle_type, nblocks,
							 0);
840 841
			if (IS_ERR(handle)) {
				err = PTR_ERR(handle);
842 843
				ext4_std_error(sb, err);
				goto out;
844 845
			}
		}
846 847
		BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
		err = ext4_journal_get_write_access(handle, inode_bitmap_bh);
848 849 850 851
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
852 853 854 855 856 857
		ext4_lock_group(sb, group);
		ret2 = ext4_test_and_set_bit(ino, inode_bitmap_bh->b_data);
		ext4_unlock_group(sb, group);
		ino++;		/* the inode bitmap is zero-based */
		if (!ret2)
			goto got; /* we grabbed the inode! */
858
next_inode:
859 860
		if (ino < EXT4_INODES_PER_GROUP(sb))
			goto repeat_in_this_group;
861 862 863
next_group:
		if (++group == ngroups)
			group = 0;
864 865 866 867 868
	}
	err = -ENOSPC;
	goto out;

got:
869 870
	BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
871 872 873 874
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
875

876 877 878 879 880 881 882
	BUFFER_TRACE(group_desc_bh, "get_write_access");
	err = ext4_journal_get_write_access(handle, group_desc_bh);
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}

A
Andreas Dilger 已提交
883
	/* We may have to initialize the block bitmap if it isn't already */
884
	if (ext4_has_group_desc_csum(sb) &&
A
Andreas Dilger 已提交
885
	    gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
886
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
887

A
Aneesh Kumar K.V 已提交
888
		block_bitmap_bh = ext4_read_block_bitmap(sb, group);
889 890 891 892
		if (!block_bitmap_bh) {
			err = -EIO;
			goto out;
		}
A
Aneesh Kumar K.V 已提交
893 894
		BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
		err = ext4_journal_get_write_access(handle, block_bitmap_bh);
A
Andreas Dilger 已提交
895
		if (err) {
A
Aneesh Kumar K.V 已提交
896
			brelse(block_bitmap_bh);
897 898
			ext4_std_error(sb, err);
			goto out;
A
Andreas Dilger 已提交
899 900
		}

901 902 903
		BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
		err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);

A
Andreas Dilger 已提交
904
		/* recheck and clear flag under lock if we still need to */
905
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
906
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
907
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
908
			ext4_free_group_clusters_set(sb, gdp,
909
				ext4_free_clusters_after_init(sb, group, gdp));
910
			ext4_block_bitmap_csum_set(sb, group, gdp,
911
						   block_bitmap_bh);
912
			ext4_group_desc_csum_set(sb, group, gdp);
A
Andreas Dilger 已提交
913
		}
914
		ext4_unlock_group(sb, group);
915
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
916

917 918 919 920
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
A
Andreas Dilger 已提交
921
	}
922 923

	/* Update the relevant bg descriptor fields */
924
	if (ext4_has_group_desc_csum(sb)) {
925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944
		int free;
		struct ext4_group_info *grp = ext4_get_group_info(sb, group);

		down_read(&grp->alloc_sem); /* protect vs itable lazyinit */
		ext4_lock_group(sb, group); /* while we modify the bg desc */
		free = EXT4_INODES_PER_GROUP(sb) -
			ext4_itable_unused_count(sb, gdp);
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
			free = 0;
		}
		/*
		 * Check the relative inode number against the last used
		 * relative inode number in this group. if it is greater
		 * we need to update the bg_itable_unused count
		 */
		if (ino > free)
			ext4_itable_unused_set(sb, gdp,
					(EXT4_INODES_PER_GROUP(sb) - ino));
		up_read(&grp->alloc_sem);
945 946
	} else {
		ext4_lock_group(sb, group);
947
	}
948

949 950 951 952 953 954 955 956 957
	ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1);
	if (S_ISDIR(mode)) {
		ext4_used_dirs_set(sb, gdp, ext4_used_dirs_count(sb, gdp) + 1);
		if (sbi->s_log_groups_per_flex) {
			ext4_group_t f = ext4_flex_group(sbi, group);

			atomic_inc(&sbi->s_flex_groups[f].used_dirs);
		}
	}
958 959 960
	if (ext4_has_group_desc_csum(sb)) {
		ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
					   EXT4_INODES_PER_GROUP(sb) / 8);
961
		ext4_group_desc_csum_set(sb, group, gdp);
962
	}
963
	ext4_unlock_group(sb, group);
964

A
Aneesh Kumar K.V 已提交
965 966
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
967 968 969 970
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
971 972 973 974 975

	percpu_counter_dec(&sbi->s_freeinodes_counter);
	if (S_ISDIR(mode))
		percpu_counter_inc(&sbi->s_dirs_counter);

976 977
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
978
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
979
	}
980

A
Andreas Dilger 已提交
981
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
982 983
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
984 985
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
986 987 988 989 990

	memset(ei->i_data, 0, sizeof(ei->i_data));
	ei->i_dir_start_lookup = 0;
	ei->i_disksize = 0;

991
	/* Don't inherit extent flag from directory, amongst others. */
992 993
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
994 995 996
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
997
	ei->i_last_alloc_group = ~0;
998

999 1000
	/* If the directory encrypted, then we should encrypt the inode. */
	if ((S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) &&
1001 1002
	    (ext4_encrypted_inode(dir) ||
	     DUMMY_ENCRYPTION_ENABLED(sbi)))
1003 1004
		ext4_set_inode_flag(inode, EXT4_INODE_ENCRYPT);

1005
	ext4_set_inode_flags(inode);
1006
	if (IS_DIRSYNC(inode))
1007
		ext4_handle_sync(handle);
A
Al Viro 已提交
1008
	if (insert_inode_locked(inode) < 0) {
1009 1010 1011 1012 1013
		/*
		 * Likely a bitmap corruption causing inode to be allocated
		 * twice.
		 */
		err = -EIO;
1014 1015 1016
		ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
			   inode->i_ino);
		goto out;
A
Al Viro 已提交
1017
	}
1018 1019 1020 1021
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

1022
	/* Precompute checksum seed for inode metadata */
1023
	if (ext4_has_metadata_csum(sb)) {
1024 1025 1026 1027 1028 1029 1030 1031 1032
		__u32 csum;
		__le32 inum = cpu_to_le32(inode->i_ino);
		__le32 gen = cpu_to_le32(inode->i_generation);
		csum = ext4_chksum(sbi, sbi->s_csum_seed, (__u8 *)&inum,
				   sizeof(inum));
		ei->i_csum_seed = ext4_chksum(sbi, csum, (__u8 *)&gen,
					      sizeof(gen));
	}

1033
	ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
1034
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
1035 1036

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
T
Tao Ma 已提交
1037 1038 1039
	ei->i_inline_off = 0;
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_INLINE_DATA))
		ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA);
1040
	ret = inode;
1041 1042
	err = dquot_alloc_inode(inode);
	if (err)
1043 1044
		goto fail_drop;

1045
	err = ext4_init_acl(handle, inode, dir);
1046 1047 1048
	if (err)
		goto fail_free_drop;

1049
	err = ext4_init_security(handle, inode, dir, qstr);
1050 1051 1052
	if (err)
		goto fail_free_drop;

1053
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
1054
		/* set extent flag only for directory, file and normal symlink*/
1055
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1056
			ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1057 1058
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1059
	}
1060

1061 1062 1063 1064 1065
	if (ext4_handle_valid(handle)) {
		ei->i_sync_tid = handle->h_transaction->t_tid;
		ei->i_datasync_tid = handle->h_transaction->t_tid;
	}

1066 1067 1068 1069 1070 1071
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1072
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1073
	trace_ext4_allocate_inode(inode, dir, mode);
A
Aneesh Kumar K.V 已提交
1074
	brelse(inode_bitmap_bh);
1075 1076 1077
	return ret;

fail_free_drop:
1078
	dquot_free_inode(inode);
1079
fail_drop:
1080
	clear_nlink(inode);
A
Al Viro 已提交
1081
	unlock_new_inode(inode);
1082 1083 1084
out:
	dquot_drop(inode);
	inode->i_flags |= S_NOQUOTA;
1085
	iput(inode);
A
Aneesh Kumar K.V 已提交
1086
	brelse(inode_bitmap_bh);
1087 1088 1089 1090
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1091
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1092
{
1093
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1094
	ext4_group_t block_group;
1095
	int bit;
1096
	struct buffer_head *bitmap_bh;
1097
	struct inode *inode = NULL;
1098
	long err = -EIO;
1099 1100 1101

	/* Error cases - e2fsck has already cleaned up for us */
	if (ino > max_ino) {
1102
		ext4_warning(sb, "bad orphan ino %lu!  e2fsck was run?", ino);
1103
		goto error;
1104 1105
	}

1106 1107
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1108
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1109
	if (!bitmap_bh) {
1110
		ext4_warning(sb, "inode bitmap error for orphan %lu", ino);
1111
		goto error;
1112 1113 1114 1115 1116 1117
	}

	/* Having the inode bit set should be a 100% indicator that this
	 * is a valid orphan (no e2fsck run on fs).  Orphans also include
	 * inodes that were being truncated, so we can't check i_nlink==0.
	 */
1118 1119 1120 1121 1122 1123 1124
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

	inode = ext4_iget(sb, ino);
	if (IS_ERR(inode))
		goto iget_failed;

1125 1126 1127 1128 1129 1130 1131 1132
	/*
	 * If the orphans has i_nlinks > 0 then it should be able to be
	 * truncated, otherwise it won't be removed from the orphan list
	 * during processing and an infinite loop will result.
	 */
	if (inode->i_nlink && !ext4_can_truncate(inode))
		goto bad_orphan;

1133 1134 1135 1136 1137 1138 1139 1140 1141
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1142
	ext4_warning(sb, "bad orphan inode %lu!  e2fsck was run?", ino);
1143
	printk(KERN_WARNING "ext4_test_bit(bit=%d, block=%llu) = %d\n",
1144 1145
	       bit, (unsigned long long)bitmap_bh->b_blocknr,
	       ext4_test_bit(bit, bitmap_bh->b_data));
1146
	printk(KERN_WARNING "inode=%p\n", inode);
1147
	if (inode) {
1148
		printk(KERN_WARNING "is_bad_inode(inode)=%d\n",
1149
		       is_bad_inode(inode));
1150
		printk(KERN_WARNING "NEXT_ORPHAN(inode)=%u\n",
1151
		       NEXT_ORPHAN(inode));
1152 1153
		printk(KERN_WARNING "max_ino=%lu\n", max_ino);
		printk(KERN_WARNING "i_nlink=%u\n", inode->i_nlink);
1154
		/* Avoid freeing blocks if we got a bad deleted inode */
1155
		if (inode->i_nlink == 0)
1156 1157 1158 1159
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1160 1161
error:
	return ERR_PTR(err);
1162 1163
}

1164
unsigned long ext4_count_free_inodes(struct super_block *sb)
1165 1166
{
	unsigned long desc_count;
1167
	struct ext4_group_desc *gdp;
1168
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1169 1170
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1171 1172 1173
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1174
	es = EXT4_SB(sb)->s_es;
1175 1176 1177
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1178
	for (i = 0; i < ngroups; i++) {
1179
		gdp = ext4_get_group_desc(sb, i, NULL);
1180 1181
		if (!gdp)
			continue;
1182
		desc_count += ext4_free_inodes_count(sb, gdp);
1183
		brelse(bitmap_bh);
1184
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1185 1186 1187
		if (!bitmap_bh)
			continue;

1188 1189
		x = ext4_count_free(bitmap_bh->b_data,
				    EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1190
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1191
			(unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
1192 1193 1194
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1195 1196 1197
	printk(KERN_DEBUG "ext4_count_free_inodes: "
	       "stored = %u, computed = %lu, %lu\n",
	       le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
1198 1199 1200
	return desc_count;
#else
	desc_count = 0;
1201
	for (i = 0; i < ngroups; i++) {
1202
		gdp = ext4_get_group_desc(sb, i, NULL);
1203 1204
		if (!gdp)
			continue;
1205
		desc_count += ext4_free_inodes_count(sb, gdp);
1206 1207 1208 1209 1210 1211 1212
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1213
unsigned long ext4_count_dirs(struct super_block * sb)
1214 1215
{
	unsigned long count = 0;
1216
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1217

1218
	for (i = 0; i < ngroups; i++) {
1219
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1220 1221
		if (!gdp)
			continue;
1222
		count += ext4_used_dirs_count(sb, gdp);
1223 1224 1225
	}
	return count;
}
1226 1227 1228 1229 1230 1231 1232

/*
 * Zeroes not yet zeroed inode table - just write zeroes through the whole
 * inode table. Must be called without any spinlock held. The only place
 * where it is called from on active part of filesystem is ext4lazyinit
 * thread, so we do not need any special locks, however we have to prevent
 * inode allocation from the current group, so we take alloc_sem lock, to
1233
 * block ext4_new_inode() until we are finished.
1234
 */
1235
int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262
				 int barrier)
{
	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_group_desc *gdp = NULL;
	struct buffer_head *group_desc_bh;
	handle_t *handle;
	ext4_fsblk_t blk;
	int num, ret = 0, used_blks = 0;

	/* This should not happen, but just to be sure check this */
	if (sb->s_flags & MS_RDONLY) {
		ret = 1;
		goto out;
	}

	gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
	if (!gdp)
		goto out;

	/*
	 * We do not need to lock this, because we are the only one
	 * handling this flag.
	 */
	if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_ZEROED))
		goto out;

1263
	handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279
	if (IS_ERR(handle)) {
		ret = PTR_ERR(handle);
		goto out;
	}

	down_write(&grp->alloc_sem);
	/*
	 * If inode bitmap was already initialized there may be some
	 * used inodes so we need to skip blocks with used inodes in
	 * inode table.
	 */
	if (!(gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)))
		used_blks = DIV_ROUND_UP((EXT4_INODES_PER_GROUP(sb) -
			    ext4_itable_unused_count(sb, gdp)),
			    sbi->s_inodes_per_block);

1280
	if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
1281 1282 1283
		ext4_error(sb, "Something is wrong with group %u: "
			   "used itable blocks: %d; "
			   "itable unused count: %u",
1284 1285 1286
			   group, used_blks,
			   ext4_itable_unused_count(sb, gdp));
		ret = 1;
1287
		goto err_out;
1288 1289
	}

1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308
	blk = ext4_inode_table(sb, gdp) + used_blks;
	num = sbi->s_itb_per_group - used_blks;

	BUFFER_TRACE(group_desc_bh, "get_write_access");
	ret = ext4_journal_get_write_access(handle,
					    group_desc_bh);
	if (ret)
		goto err_out;

	/*
	 * Skip zeroout if the inode table is full. But we set the ZEROED
	 * flag anyway, because obviously, when it is full it does not need
	 * further zeroing.
	 */
	if (unlikely(num == 0))
		goto skip_zeroout;

	ext4_debug("going to zero out inode table in group %d\n",
		   group);
1309
	ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1310 1311
	if (ret < 0)
		goto err_out;
1312 1313
	if (barrier)
		blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1314 1315 1316 1317

skip_zeroout:
	ext4_lock_group(sb, group);
	gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
1318
	ext4_group_desc_csum_set(sb, group, gdp);
1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331
	ext4_unlock_group(sb, group);

	BUFFER_TRACE(group_desc_bh,
		     "call ext4_handle_dirty_metadata");
	ret = ext4_handle_dirty_metadata(handle, NULL,
					 group_desc_bh);

err_out:
	up_write(&grp->alloc_sem);
	ext4_journal_stop(handle);
out:
	return ret;
}