ialloc.c 38.4 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
static int ext4_init_inode_bitmap(struct super_block *sb,
68 69 70
				       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
		grp = ext4_get_group_info(sb, block_group);
80 81 82
		if (!EXT4_MB_GRP_BBITMAP_CORRUPT(grp))
			percpu_counter_sub(&sbi->s_freeclusters_counter,
					   grp->bb_free);
83
		set_bit(EXT4_GROUP_INFO_BBITMAP_CORRUPT_BIT, &grp->bb_state);
84 85 86 87 88 89
		if (!EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			int count;
			count = ext4_free_inodes_count(sb, gdp);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
90
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
91
		return -EFSBADCRC;
A
Andreas Dilger 已提交
92 93 94
	}

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

101
	return 0;
A
Andreas Dilger 已提交
102
}
103

104 105 106 107 108 109 110 111 112 113
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);
}

114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
static int ext4_validate_inode_bitmap(struct super_block *sb,
				      struct ext4_group_desc *desc,
				      ext4_group_t block_group,
				      struct buffer_head *bh)
{
	ext4_fsblk_t	blk;
	struct ext4_group_info *grp = ext4_get_group_info(sb, block_group);
	struct ext4_sb_info *sbi = EXT4_SB(sb);

	if (buffer_verified(bh))
		return 0;
	if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp))
		return -EFSCORRUPTED;

	ext4_lock_group(sb, block_group);
	blk = ext4_inode_bitmap(sb, desc);
	if (!ext4_inode_bitmap_csum_verify(sb, block_group, desc, bh,
					   EXT4_INODES_PER_GROUP(sb) / 8)) {
		ext4_unlock_group(sb, block_group);
		ext4_error(sb, "Corrupt inode bitmap - block_group = %u, "
			   "inode_bitmap = %llu", block_group, blk);
		grp = ext4_get_group_info(sb, block_group);
		if (!EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			int count;
			count = ext4_free_inodes_count(sb, desc);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
		return -EFSBADCRC;
	}
	set_buffer_verified(bh);
	ext4_unlock_group(sb, block_group);
	return 0;
}

150 151 152 153 154 155 156
/*
 * 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 *
157
ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
158
{
159
	struct ext4_group_desc *desc;
160
	struct buffer_head *bh = NULL;
161
	ext4_fsblk_t bitmap_blk;
162
	int err;
163

164
	desc = ext4_get_group_desc(sb, block_group, NULL);
165
	if (!desc)
166
		return ERR_PTR(-EFSCORRUPTED);
167

168 169 170
	bitmap_blk = ext4_inode_bitmap(sb, desc);
	bh = sb_getblk(sb, bitmap_blk);
	if (unlikely(!bh)) {
171
		ext4_error(sb, "Cannot read inode bitmap - "
172
			    "block_group = %u, inode_bitmap = %llu",
173
			    block_group, bitmap_blk);
174
		return ERR_PTR(-EIO);
175
	}
176
	if (bitmap_uptodate(bh))
177
		goto verify;
178

179
	lock_buffer(bh);
180 181
	if (bitmap_uptodate(bh)) {
		unlock_buffer(bh);
182
		goto verify;
183
	}
184

185
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
186
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
187
		err = ext4_init_inode_bitmap(sb, bh, block_group, desc);
188
		set_bitmap_uptodate(bh);
189
		set_buffer_uptodate(bh);
190
		set_buffer_verified(bh);
191
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
192
		unlock_buffer(bh);
193 194 195
		if (err) {
			ext4_error(sb, "Failed to init inode bitmap for group "
				   "%u: %d", block_group, err);
196
			goto out;
197
		}
198
		return bh;
A
Andreas Dilger 已提交
199
	}
200
	ext4_unlock_group(sb, block_group);
201

202 203 204 205 206 207 208
	if (buffer_uptodate(bh)) {
		/*
		 * if not uninit if bh is uptodate,
		 * bitmap is also uptodate
		 */
		set_bitmap_uptodate(bh);
		unlock_buffer(bh);
209
		goto verify;
210 211
	}
	/*
212
	 * submit the buffer_head for reading
213
	 */
214
	trace_ext4_load_inode_bitmap(sb, block_group);
215 216
	bh->b_end_io = ext4_end_bitmap_read;
	get_bh(bh);
217
	submit_bh(READ | REQ_META | REQ_PRIO, bh);
218 219
	wait_on_buffer(bh);
	if (!buffer_uptodate(bh)) {
220
		put_bh(bh);
221
		ext4_error(sb, "Cannot read inode bitmap - "
222 223
			   "block_group = %u, inode_bitmap = %llu",
			   block_group, bitmap_blk);
224
		return ERR_PTR(-EIO);
225
	}
226 227

verify:
228 229 230
	err = ext4_validate_inode_bitmap(sb, desc, block_group, bh);
	if (err)
		goto out;
231
	return bh;
232 233 234
out:
	put_bh(bh);
	return ERR_PTR(err);
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
}

/*
 * 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.
 */
253
void ext4_free_inode(handle_t *handle, struct inode *inode)
254
{
255
	struct super_block *sb = inode->i_sb;
256 257 258 259
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
260
	ext4_group_t block_group;
261
	unsigned long bit;
262 263
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
264
	struct ext4_sb_info *sbi;
265
	int fatal = 0, err, count, cleared;
266
	struct ext4_group_info *grp;
267

268 269 270
	if (!sb) {
		printk(KERN_ERR "EXT4-fs: %s:%d: inode on "
		       "nonexistent device\n", __func__, __LINE__);
271 272
		return;
	}
273 274 275 276
	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));
277 278
		return;
	}
279 280 281
	if (inode->i_nlink) {
		ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n",
			 __func__, __LINE__, inode->i_ino, inode->i_nlink);
282 283
		return;
	}
284
	sbi = EXT4_SB(sb);
285 286

	ino = inode->i_ino;
287
	ext4_debug("freeing inode %lu\n", ino);
288
	trace_ext4_free_inode(inode);
289 290 291 292 293

	/*
	 * Note: we must free any quota before locking the superblock,
	 * as writing the quota to disk may need the lock as well.
	 */
294
	dquot_initialize(inode);
295
	ext4_xattr_delete_inode(handle, inode);
296
	dquot_free_inode(inode);
297
	dquot_drop(inode);
298 299 300 301

	is_directory = S_ISDIR(inode->i_mode);

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

304 305
	es = EXT4_SB(sb)->s_es;
	if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
306
		ext4_error(sb, "reserved or nonexistent inode %lu", ino);
307 308
		goto error_return;
	}
309 310
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
311
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
312 313
	/* Don't bother if the inode bitmap is corrupt. */
	grp = ext4_get_group_info(sb, block_group);
314 315 316 317 318 319 320
	if (IS_ERR(bitmap_bh)) {
		fatal = PTR_ERR(bitmap_bh);
		bitmap_bh = NULL;
		goto error_return;
	}
	if (unlikely(EXT4_MB_GRP_IBITMAP_CORRUPT(grp))) {
		fatal = -EFSCORRUPTED;
321
		goto error_return;
322
	}
323 324

	BUFFER_TRACE(bitmap_bh, "get_write_access");
325
	fatal = ext4_journal_get_write_access(handle, bitmap_bh);
326 327 328
	if (fatal)
		goto error_return;

329 330 331
	fatal = -ESRCH;
	gdp = ext4_get_group_desc(sb, block_group, &bh2);
	if (gdp) {
332
		BUFFER_TRACE(bh2, "get_write_access");
333
		fatal = ext4_journal_get_write_access(handle, bh2);
334 335
	}
	ext4_lock_group(sb, block_group);
336
	cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data);
337 338 339 340
	if (fatal || !cleared) {
		ext4_unlock_group(sb, block_group);
		goto out;
	}
341

342 343 344 345 346 347
	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);
348
	}
349 350
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
351
	ext4_group_desc_csum_set(sb, block_group, gdp);
352
	ext4_unlock_group(sb, block_group);
353

354 355 356
	percpu_counter_inc(&sbi->s_freeinodes_counter);
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t f = ext4_flex_group(sbi, block_group);
357

358 359 360
		atomic_inc(&sbi->s_flex_groups[f].free_inodes);
		if (is_directory)
			atomic_dec(&sbi->s_flex_groups[f].used_dirs);
361
	}
362 363 364 365 366 367 368 369
	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;
370
	} else {
371
		ext4_error(sb, "bit already cleared for inode %lu", ino);
372
		if (gdp && !EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
373 374 375 376 377
			int count;
			count = ext4_free_inodes_count(sb, gdp);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
378 379
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
	}
380

381 382
error_return:
	brelse(bitmap_bh);
383
	ext4_std_error(sb, fatal);
384 385
}

386
struct orlov_stats {
387
	__u64 free_clusters;
388 389 390 391 392 393 394 395 396
	__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.
 */
397 398
static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
			    int flex_size, struct orlov_stats *stats)
399 400
{
	struct ext4_group_desc *desc;
401
	struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
402

403 404
	if (flex_size > 1) {
		stats->free_inodes = atomic_read(&flex_group[g].free_inodes);
405
		stats->free_clusters = atomic64_read(&flex_group[g].free_clusters);
406 407 408
		stats->used_dirs = atomic_read(&flex_group[g].used_dirs);
		return;
	}
409

410 411 412
	desc = ext4_get_group_desc(sb, g, NULL);
	if (desc) {
		stats->free_inodes = ext4_free_inodes_count(sb, desc);
413
		stats->free_clusters = ext4_free_group_clusters(sb, desc);
414 415 416
		stats->used_dirs = ext4_used_dirs_count(sb, desc);
	} else {
		stats->free_inodes = 0;
417
		stats->free_clusters = 0;
418
		stats->used_dirs = 0;
419 420 421
	}
}

422 423 424 425 426 427 428 429 430 431 432 433 434 435 436
/*
 * 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
437
 * Parent's group is preferred, if it doesn't satisfy these
438 439 440 441 442
 * 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).
 */

443
static int find_group_orlov(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
444
			    ext4_group_t *group, umode_t mode,
445
			    const struct qstr *qstr)
446
{
447
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
448
	struct ext4_sb_info *sbi = EXT4_SB(sb);
449
	ext4_group_t real_ngroups = ext4_get_groups_count(sb);
450
	int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
451
	unsigned int freei, avefreei, grp_free;
452
	ext4_fsblk_t freeb, avefreec;
453
	unsigned int ndirs;
454
	int max_dirs, min_inodes;
455
	ext4_grpblk_t min_clusters;
456
	ext4_group_t i, grp, g, ngroups;
457
	struct ext4_group_desc *desc;
458 459
	struct orlov_stats stats;
	int flex_size = ext4_flex_bg_size(sbi);
460
	struct dx_hash_info hinfo;
461

462
	ngroups = real_ngroups;
463
	if (flex_size > 1) {
464
		ngroups = (real_ngroups + flex_size - 1) >>
465 466 467
			sbi->s_log_groups_per_flex;
		parent_group >>= sbi->s_log_groups_per_flex;
	}
468 469 470

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
471 472
	freeb = EXT4_C2B(sbi,
		percpu_counter_read_positive(&sbi->s_freeclusters_counter));
473 474
	avefreec = freeb;
	do_div(avefreec, ngroups);
475 476
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

477
	if (S_ISDIR(mode) &&
478
	    ((parent == d_inode(sb->s_root)) ||
479
	     (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
480
		int best_ndir = inodes_per_group;
481
		int ret = -1;
482

483 484 485 486 487 488
		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
489
			grp = prandom_u32();
490
		parent_group = (unsigned)grp % ngroups;
491
		for (i = 0; i < ngroups; i++) {
492 493 494
			g = (parent_group + i) % ngroups;
			get_orlov_stats(sb, g, flex_size, &stats);
			if (!stats.free_inodes)
495
				continue;
496
			if (stats.used_dirs >= best_ndir)
497
				continue;
498
			if (stats.free_inodes < avefreei)
499
				continue;
500
			if (stats.free_clusters < avefreec)
501
				continue;
502
			grp = g;
503
			ret = 0;
504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
			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++) {
523
			if (grp+i >= real_ngroups)
524 525 526 527 528 529
				break;
			desc = ext4_get_group_desc(sb, grp+i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = grp+i;
				return 0;
			}
530 531 532 533 534
		}
		goto fallback;
	}

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
535 536 537
	min_inodes = avefreei - inodes_per_group*flex_size / 4;
	if (min_inodes < 1)
		min_inodes = 1;
538
	min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
539 540 541 542 543 544 545 546 547 548

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

	for (i = 0; i < ngroups; i++) {
551 552 553
		grp = (parent_group + i) % ngroups;
		get_orlov_stats(sb, grp, flex_size, &stats);
		if (stats.used_dirs >= max_dirs)
554
			continue;
555
		if (stats.free_inodes < min_inodes)
556
			continue;
557
		if (stats.free_clusters < min_clusters)
558
			continue;
559
		goto found_flex_bg;
560 561 562
	}

fallback:
563
	ngroups = real_ngroups;
564
	avefreei = freei / ngroups;
565
fallback_retry:
566
	parent_group = EXT4_I(parent)->i_block_group;
567
	for (i = 0; i < ngroups; i++) {
568 569
		grp = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, grp, NULL);
570 571 572 573 574 575
		if (desc) {
			grp_free = ext4_free_inodes_count(sb, desc);
			if (grp_free && grp_free >= avefreei) {
				*group = grp;
				return 0;
			}
576
		}
577 578 579 580 581 582 583 584
	}

	if (avefreei) {
		/*
		 * The free-inodes counter is approximate, and for really small
		 * filesystems the above test can fail to find any blockgroups
		 */
		avefreei = 0;
585
		goto fallback_retry;
586 587 588 589 590
	}

	return -1;
}

591
static int find_group_other(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
592
			    ext4_group_t *group, umode_t mode)
593
{
594
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
595
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
596
	struct ext4_group_desc *desc;
597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633
	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;
634
		return find_group_orlov(sb, parent, group, mode, NULL);
635
	}
636 637 638 639

	/*
	 * Try to place the inode in its parent directory
	 */
640 641
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
642
	if (desc && ext4_free_inodes_count(sb, desc) &&
643
	    ext4_free_group_clusters(sb, desc))
644
		return 0;
645 646 647 648 649 650 651 652 653 654

	/*
	 * 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.
	 */
655
	*group = (*group + parent->i_ino) % ngroups;
656 657 658 659 660 661

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
662 663 664 665
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
666
		if (desc && ext4_free_inodes_count(sb, desc) &&
667
		    ext4_free_group_clusters(sb, desc))
668
			return 0;
669 670 671 672 673 674
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
675
	*group = parent_group;
676
	for (i = 0; i < ngroups; i++) {
677 678 679
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
680
		if (desc && ext4_free_inodes_count(sb, desc))
681
			return 0;
682 683 684 685 686
	}

	return -1;
}

687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731
/*
 * 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;
}

732 733 734 735 736 737 738 739 740 741
/*
 * 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.
 */
742 743 744 745
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)
746 747
{
	struct super_block *sb;
A
Aneesh Kumar K.V 已提交
748 749
	struct buffer_head *inode_bitmap_bh = NULL;
	struct buffer_head *group_desc_bh;
750
	ext4_group_t ngroups, group = 0;
751
	unsigned long ino = 0;
752 753
	struct inode *inode;
	struct ext4_group_desc *gdp = NULL;
754 755
	struct ext4_inode_info *ei;
	struct ext4_sb_info *sbi;
756
	int ret2, err;
757
	struct inode *ret;
758
	ext4_group_t i;
759
	ext4_group_t flex_group;
760
	struct ext4_group_info *grp;
761
	int encrypt = 0;
762 763 764 765 766

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

767 768 769 770 771 772 773 774 775 776 777 778 779
	if ((ext4_encrypted_inode(dir) ||
	     DUMMY_ENCRYPTION_ENABLED(EXT4_SB(dir->i_sb))) &&
	    (S_ISREG(mode) || S_ISDIR(mode) || S_ISLNK(mode))) {
		err = ext4_get_encryption_info(dir);
		if (err)
			return ERR_PTR(err);
		if (ext4_encryption_info(dir) == NULL)
			return ERR_PTR(-EPERM);
		if (!handle)
			nblocks += EXT4_DATA_TRANS_BLOCKS(dir->i_sb);
		encrypt = 1;
	}

780
	sb = dir->i_sb;
781
	ngroups = ext4_get_groups_count(sb);
782
	trace_ext4_request_inode(dir, mode);
783 784 785
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
786 787
	ei = EXT4_I(inode);
	sbi = EXT4_SB(sb);
788

789 790 791 792 793 794 795 796 797 798 799 800 801 802 803
	/*
	 * 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);
L
Li Xi 已提交
804 805 806 807 808 809 810

	if (EXT4_HAS_RO_COMPAT_FEATURE(sb, EXT4_FEATURE_RO_COMPAT_PROJECT) &&
	    ext4_test_inode_flag(dir, EXT4_INODE_PROJINHERIT))
		ei->i_projid = EXT4_I(dir)->i_projid;
	else
		ei->i_projid = make_kprojid(&init_user_ns, EXT4_DEF_PROJID);

811 812 813
	err = dquot_initialize(inode);
	if (err)
		goto out;
814

815 816 817
	if (!goal)
		goal = sbi->s_inode_goal;

818
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
819 820 821 822 823 824
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

L
Lukas Czerner 已提交
825 826 827
	if (S_ISDIR(mode))
		ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
	else
828
		ret2 = find_group_other(sb, dir, &group, mode);
829

830
got_group:
831
	EXT4_I(dir)->i_last_alloc_group = group;
832
	err = -ENOSPC;
833
	if (ret2 == -1)
834 835
		goto out;

836 837 838 839 840
	/*
	 * 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.
	 */
841
	for (i = 0; i < ngroups; i++, ino = 0) {
842 843
		err = -EIO;

A
Aneesh Kumar K.V 已提交
844
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
845
		if (!gdp)
846
			goto out;
847

848 849 850 851 852 853 854 855 856
		/*
		 * Check free inodes count before loading bitmap.
		 */
		if (ext4_free_inodes_count(sb, gdp) == 0) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

857 858 859 860 861 862 863 864
		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 已提交
865 866
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
867
		/* Skip groups with suspicious inode tables */
868 869 870
		if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp) ||
		    IS_ERR(inode_bitmap_bh)) {
			inode_bitmap_bh = NULL;
871 872 873 874
			if (++group == ngroups)
				group = 0;
			continue;
		}
875 876

repeat_in_this_group:
877
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
878 879
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);
880 881
		if (ino >= EXT4_INODES_PER_GROUP(sb))
			goto next_group;
882 883 884 885 886
		if (group == 0 && (ino+1) < EXT4_FIRST_INO(sb)) {
			ext4_error(sb, "reserved inode found cleared - "
				   "inode=%lu", ino + 1);
			continue;
		}
887 888 889 890 891
		if ((EXT4_SB(sb)->s_journal == NULL) &&
		    recently_deleted(sb, group, ino)) {
			ino++;
			goto next_inode;
		}
892 893 894
		if (!handle) {
			BUG_ON(nblocks <= 0);
			handle = __ext4_journal_start_sb(dir->i_sb, line_no,
895 896
							 handle_type, nblocks,
							 0);
897 898
			if (IS_ERR(handle)) {
				err = PTR_ERR(handle);
899 900
				ext4_std_error(sb, err);
				goto out;
901 902
			}
		}
903 904
		BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
		err = ext4_journal_get_write_access(handle, inode_bitmap_bh);
905 906 907 908
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
909 910 911 912 913 914
		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! */
915
next_inode:
916 917
		if (ino < EXT4_INODES_PER_GROUP(sb))
			goto repeat_in_this_group;
918 919 920
next_group:
		if (++group == ngroups)
			group = 0;
921 922 923 924 925
	}
	err = -ENOSPC;
	goto out;

got:
926 927
	BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
928 929 930 931
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
932

933 934 935 936 937 938 939
	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 已提交
940
	/* We may have to initialize the block bitmap if it isn't already */
941
	if (ext4_has_group_desc_csum(sb) &&
A
Andreas Dilger 已提交
942
	    gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
943
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
944

A
Aneesh Kumar K.V 已提交
945
		block_bitmap_bh = ext4_read_block_bitmap(sb, group);
946 947
		if (IS_ERR(block_bitmap_bh)) {
			err = PTR_ERR(block_bitmap_bh);
948 949
			goto out;
		}
A
Aneesh Kumar K.V 已提交
950 951
		BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
		err = ext4_journal_get_write_access(handle, block_bitmap_bh);
A
Andreas Dilger 已提交
952
		if (err) {
A
Aneesh Kumar K.V 已提交
953
			brelse(block_bitmap_bh);
954 955
			ext4_std_error(sb, err);
			goto out;
A
Andreas Dilger 已提交
956 957
		}

958 959 960
		BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
		err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);

A
Andreas Dilger 已提交
961
		/* recheck and clear flag under lock if we still need to */
962
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
963
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
964
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
965
			ext4_free_group_clusters_set(sb, gdp,
966
				ext4_free_clusters_after_init(sb, group, gdp));
967
			ext4_block_bitmap_csum_set(sb, group, gdp,
968
						   block_bitmap_bh);
969
			ext4_group_desc_csum_set(sb, group, gdp);
A
Andreas Dilger 已提交
970
		}
971
		ext4_unlock_group(sb, group);
972
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
973

974 975 976 977
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
A
Andreas Dilger 已提交
978
	}
979 980

	/* Update the relevant bg descriptor fields */
981
	if (ext4_has_group_desc_csum(sb)) {
982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
		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);
1002 1003
	} else {
		ext4_lock_group(sb, group);
1004
	}
1005

1006 1007 1008 1009 1010 1011 1012 1013 1014
	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);
		}
	}
1015 1016 1017
	if (ext4_has_group_desc_csum(sb)) {
		ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
					   EXT4_INODES_PER_GROUP(sb) / 8);
1018
		ext4_group_desc_csum_set(sb, group, gdp);
1019
	}
1020
	ext4_unlock_group(sb, group);
1021

A
Aneesh Kumar K.V 已提交
1022 1023
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
1024 1025 1026 1027
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
1028 1029 1030 1031 1032

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

1033 1034
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
1035
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
1036
	}
1037

A
Andreas Dilger 已提交
1038
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
1039 1040
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
1041 1042
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
1043 1044 1045 1046 1047

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

1048
	/* Don't inherit extent flag from directory, amongst others. */
1049 1050
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
1051 1052 1053
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
1054
	ei->i_last_alloc_group = ~0;
1055

1056
	ext4_set_inode_flags(inode);
1057
	if (IS_DIRSYNC(inode))
1058
		ext4_handle_sync(handle);
A
Al Viro 已提交
1059
	if (insert_inode_locked(inode) < 0) {
1060 1061 1062 1063 1064
		/*
		 * Likely a bitmap corruption causing inode to be allocated
		 * twice.
		 */
		err = -EIO;
1065 1066 1067
		ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
			   inode->i_ino);
		goto out;
A
Al Viro 已提交
1068
	}
1069 1070 1071 1072
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

1073
	/* Precompute checksum seed for inode metadata */
1074
	if (ext4_has_metadata_csum(sb)) {
1075 1076 1077 1078 1079 1080 1081 1082 1083
		__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));
	}

1084
	ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
1085
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
1086 1087

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
T
Tao Ma 已提交
1088
	ei->i_inline_off = 0;
1089
	if (ext4_has_feature_inline_data(sb))
T
Tao Ma 已提交
1090
		ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA);
1091
	ret = inode;
1092 1093
	err = dquot_alloc_inode(inode);
	if (err)
1094 1095
		goto fail_drop;

1096
	err = ext4_init_acl(handle, inode, dir);
1097 1098 1099
	if (err)
		goto fail_free_drop;

1100
	err = ext4_init_security(handle, inode, dir, qstr);
1101 1102 1103
	if (err)
		goto fail_free_drop;

1104
	if (ext4_has_feature_extents(sb)) {
1105
		/* set extent flag only for directory, file and normal symlink*/
1106
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1107
			ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1108 1109
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1110
	}
1111

1112 1113 1114 1115 1116
	if (ext4_handle_valid(handle)) {
		ei->i_sync_tid = handle->h_transaction->t_tid;
		ei->i_datasync_tid = handle->h_transaction->t_tid;
	}

1117 1118 1119 1120 1121 1122
	if (encrypt) {
		err = ext4_inherit_context(dir, inode);
		if (err)
			goto fail_free_drop;
	}

1123 1124 1125 1126 1127 1128
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1129
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1130
	trace_ext4_allocate_inode(inode, dir, mode);
A
Aneesh Kumar K.V 已提交
1131
	brelse(inode_bitmap_bh);
1132 1133 1134
	return ret;

fail_free_drop:
1135
	dquot_free_inode(inode);
1136
fail_drop:
1137
	clear_nlink(inode);
A
Al Viro 已提交
1138
	unlock_new_inode(inode);
1139 1140 1141
out:
	dquot_drop(inode);
	inode->i_flags |= S_NOQUOTA;
1142
	iput(inode);
A
Aneesh Kumar K.V 已提交
1143
	brelse(inode_bitmap_bh);
1144 1145 1146 1147
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1148
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1149
{
1150
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1151
	ext4_group_t block_group;
1152
	int bit;
1153
	struct buffer_head *bitmap_bh;
1154
	struct inode *inode = NULL;
1155
	long err = -EIO;
1156 1157 1158

	/* Error cases - e2fsck has already cleaned up for us */
	if (ino > max_ino) {
1159
		ext4_warning(sb, "bad orphan ino %lu!  e2fsck was run?", ino);
1160
		err = -EFSCORRUPTED;
1161
		goto error;
1162 1163
	}

1164 1165
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1166
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1167 1168 1169 1170
	if (IS_ERR(bitmap_bh)) {
		err = PTR_ERR(bitmap_bh);
		ext4_warning(sb, "inode bitmap error %ld for orphan %lu",
			     ino, err);
1171
		goto error;
1172 1173 1174 1175 1176 1177
	}

	/* 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.
	 */
1178 1179 1180 1181 1182 1183 1184
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1185 1186 1187 1188 1189 1190 1191 1192
	/*
	 * 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;

1193 1194 1195 1196 1197 1198 1199 1200 1201
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1202
	ext4_warning(sb, "bad orphan inode %lu!  e2fsck was run?", ino);
1203
	printk(KERN_WARNING "ext4_test_bit(bit=%d, block=%llu) = %d\n",
1204 1205
	       bit, (unsigned long long)bitmap_bh->b_blocknr,
	       ext4_test_bit(bit, bitmap_bh->b_data));
1206
	printk(KERN_WARNING "inode=%p\n", inode);
1207
	if (inode) {
1208
		printk(KERN_WARNING "is_bad_inode(inode)=%d\n",
1209
		       is_bad_inode(inode));
1210
		printk(KERN_WARNING "NEXT_ORPHAN(inode)=%u\n",
1211
		       NEXT_ORPHAN(inode));
1212 1213
		printk(KERN_WARNING "max_ino=%lu\n", max_ino);
		printk(KERN_WARNING "i_nlink=%u\n", inode->i_nlink);
1214
		/* Avoid freeing blocks if we got a bad deleted inode */
1215
		if (inode->i_nlink == 0)
1216 1217 1218 1219
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1220 1221
error:
	return ERR_PTR(err);
1222 1223
}

1224
unsigned long ext4_count_free_inodes(struct super_block *sb)
1225 1226
{
	unsigned long desc_count;
1227
	struct ext4_group_desc *gdp;
1228
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1229 1230
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1231 1232 1233
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1234
	es = EXT4_SB(sb)->s_es;
1235 1236 1237
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1238
	for (i = 0; i < ngroups; i++) {
1239
		gdp = ext4_get_group_desc(sb, i, NULL);
1240 1241
		if (!gdp)
			continue;
1242
		desc_count += ext4_free_inodes_count(sb, gdp);
1243
		brelse(bitmap_bh);
1244
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1245 1246
		if (IS_ERR(bitmap_bh)) {
			bitmap_bh = NULL;
1247
			continue;
1248
		}
1249

1250 1251
		x = ext4_count_free(bitmap_bh->b_data,
				    EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1252
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1253
			(unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
1254 1255 1256
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1257 1258 1259
	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);
1260 1261 1262
	return desc_count;
#else
	desc_count = 0;
1263
	for (i = 0; i < ngroups; i++) {
1264
		gdp = ext4_get_group_desc(sb, i, NULL);
1265 1266
		if (!gdp)
			continue;
1267
		desc_count += ext4_free_inodes_count(sb, gdp);
1268 1269 1270 1271 1272 1273 1274
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1275
unsigned long ext4_count_dirs(struct super_block * sb)
1276 1277
{
	unsigned long count = 0;
1278
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1279

1280
	for (i = 0; i < ngroups; i++) {
1281
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1282 1283
		if (!gdp)
			continue;
1284
		count += ext4_used_dirs_count(sb, gdp);
1285 1286 1287
	}
	return count;
}
1288 1289 1290 1291 1292 1293 1294

/*
 * 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
1295
 * block ext4_new_inode() until we are finished.
1296
 */
1297
int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324
				 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;

1325
	handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341
	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);

1342
	if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
1343 1344 1345
		ext4_error(sb, "Something is wrong with group %u: "
			   "used itable blocks: %d; "
			   "itable unused count: %u",
1346 1347 1348
			   group, used_blks,
			   ext4_itable_unused_count(sb, gdp));
		ret = 1;
1349
		goto err_out;
1350 1351
	}

1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370
	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);
1371
	ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1372 1373
	if (ret < 0)
		goto err_out;
1374 1375
	if (barrier)
		blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1376 1377 1378 1379

skip_zeroout:
	ext4_lock_group(sb, group);
	gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
1380
	ext4_group_desc_csum_set(sb, group, gdp);
1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393
	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;
}