ialloc.c 35.5 KB
Newer Older
1
/*
2
 *  linux/fs/ext4/ialloc.c
3 4 5 6 7 8 9 10 11 12 13 14 15 16
 *
 * 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>
17
#include <linux/jbd2.h>
18 19 20 21 22 23
#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>
24
#include <linux/blkdev.h>
25
#include <asm/byteorder.h>
26

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

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

34 35 36 37 38 39 40 41 42 43 44 45 46 47
/*
 * 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 已提交
48 49 50 51 52
/*
 * 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.
 */
53
void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
A
Andreas Dilger 已提交
54 55 56 57 58 59 60 61 62 63 64 65 66 67
{
	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 */
68 69 70 71
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 已提交
72 73 74 75 76
{
	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. */
77
	if (!ext4_group_desc_csum_verify(sb, block_group, gdp)) {
78
		ext4_error(sb, "Checksum bad for group %u", block_group);
79
		ext4_free_group_clusters_set(sb, gdp, 0);
80 81
		ext4_free_inodes_set(sb, gdp, 0);
		ext4_itable_unused_set(sb, gdp, 0);
A
Andreas Dilger 已提交
82
		memset(bh->b_data, 0xff, sb->s_blocksize);
83 84
		ext4_inode_bitmap_csum_set(sb, block_group, gdp, bh,
					   EXT4_INODES_PER_GROUP(sb) / 8);
A
Andreas Dilger 已提交
85 86 87 88
		return 0;
	}

	memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
89
	ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), sb->s_blocksize * 8,
A
Andreas Dilger 已提交
90
			bh->b_data);
91 92
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
93
	ext4_group_desc_csum_set(sb, block_group, gdp);
A
Andreas Dilger 已提交
94 95 96

	return EXT4_INODES_PER_GROUP(sb);
}
97

98 99 100 101 102 103 104 105 106 107
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);
}

108 109 110 111 112 113 114
/*
 * 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 *
115
ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
116
{
117
	struct ext4_group_desc *desc;
118
	struct buffer_head *bh = NULL;
119
	ext4_fsblk_t bitmap_blk;
120

121
	desc = ext4_get_group_desc(sb, block_group, NULL);
122
	if (!desc)
123
		return NULL;
124

125 126 127
	bitmap_blk = ext4_inode_bitmap(sb, desc);
	bh = sb_getblk(sb, bitmap_blk);
	if (unlikely(!bh)) {
128
		ext4_error(sb, "Cannot read inode bitmap - "
129
			    "block_group = %u, inode_bitmap = %llu",
130 131 132
			    block_group, bitmap_blk);
		return NULL;
	}
133
	if (bitmap_uptodate(bh))
134
		goto verify;
135

136
	lock_buffer(bh);
137 138
	if (bitmap_uptodate(bh)) {
		unlock_buffer(bh);
139
		goto verify;
140
	}
141

142
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
143
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
144
		ext4_init_inode_bitmap(sb, bh, block_group, desc);
145
		set_bitmap_uptodate(bh);
146
		set_buffer_uptodate(bh);
147
		set_buffer_verified(bh);
148
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
149
		unlock_buffer(bh);
150
		return bh;
A
Andreas Dilger 已提交
151
	}
152
	ext4_unlock_group(sb, block_group);
153

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

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);
		return NULL;
	}
	ext4_unlock_group(sb, block_group);
	set_buffer_verified(bh);
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
	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.
 */
211
void ext4_free_inode(handle_t *handle, struct inode *inode)
212
{
213
	struct super_block *sb = inode->i_sb;
214 215 216 217
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
218
	ext4_group_t block_group;
219
	unsigned long bit;
220 221
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
222
	struct ext4_sb_info *sbi;
223
	int fatal = 0, err, count, cleared;
224

225 226 227
	if (!sb) {
		printk(KERN_ERR "EXT4-fs: %s:%d: inode on "
		       "nonexistent device\n", __func__, __LINE__);
228 229
		return;
	}
230 231 232 233
	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));
234 235
		return;
	}
236 237 238
	if (inode->i_nlink) {
		ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n",
			 __func__, __LINE__, inode->i_ino, inode->i_nlink);
239 240
		return;
	}
241
	sbi = EXT4_SB(sb);
242 243

	ino = inode->i_ino;
244
	ext4_debug("freeing inode %lu\n", ino);
245
	trace_ext4_free_inode(inode);
246 247 248 249 250

	/*
	 * Note: we must free any quota before locking the superblock,
	 * as writing the quota to disk may need the lock as well.
	 */
251
	dquot_initialize(inode);
252
	ext4_xattr_delete_inode(handle, inode);
253
	dquot_free_inode(inode);
254
	dquot_drop(inode);
255 256 257 258

	is_directory = S_ISDIR(inode->i_mode);

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

261 262
	es = EXT4_SB(sb)->s_es;
	if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
263
		ext4_error(sb, "reserved or nonexistent inode %lu", ino);
264 265
		goto error_return;
	}
266 267
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
268
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
269 270 271 272
	if (!bitmap_bh)
		goto error_return;

	BUFFER_TRACE(bitmap_bh, "get_write_access");
273
	fatal = ext4_journal_get_write_access(handle, bitmap_bh);
274 275 276
	if (fatal)
		goto error_return;

277 278 279
	fatal = -ESRCH;
	gdp = ext4_get_group_desc(sb, block_group, &bh2);
	if (gdp) {
280
		BUFFER_TRACE(bh2, "get_write_access");
281
		fatal = ext4_journal_get_write_access(handle, bh2);
282 283
	}
	ext4_lock_group(sb, block_group);
284
	cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data);
285 286 287 288
	if (fatal || !cleared) {
		ext4_unlock_group(sb, block_group);
		goto out;
	}
289

290 291 292 293 294 295
	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);
296
	}
297 298
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
299
	ext4_group_desc_csum_set(sb, block_group, gdp);
300
	ext4_unlock_group(sb, block_group);
301

302 303 304
	percpu_counter_inc(&sbi->s_freeinodes_counter);
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t f = ext4_flex_group(sbi, block_group);
305

306 307 308
		atomic_inc(&sbi->s_flex_groups[f].free_inodes);
		if (is_directory)
			atomic_dec(&sbi->s_flex_groups[f].used_dirs);
309
	}
310 311 312 313 314 315 316 317 318 319 320
	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;
	} else
		ext4_error(sb, "bit already cleared for inode %lu", ino);

321 322
error_return:
	brelse(bitmap_bh);
323
	ext4_std_error(sb, fatal);
324 325
}

326
struct orlov_stats {
327
	__u64 free_clusters;
328 329 330 331 332 333 334 335 336
	__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.
 */
337 338
static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
			    int flex_size, struct orlov_stats *stats)
339 340
{
	struct ext4_group_desc *desc;
341
	struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
342

343 344
	if (flex_size > 1) {
		stats->free_inodes = atomic_read(&flex_group[g].free_inodes);
345
		stats->free_clusters = atomic64_read(&flex_group[g].free_clusters);
346 347 348
		stats->used_dirs = atomic_read(&flex_group[g].used_dirs);
		return;
	}
349

350 351 352
	desc = ext4_get_group_desc(sb, g, NULL);
	if (desc) {
		stats->free_inodes = ext4_free_inodes_count(sb, desc);
353
		stats->free_clusters = ext4_free_group_clusters(sb, desc);
354 355 356
		stats->used_dirs = ext4_used_dirs_count(sb, desc);
	} else {
		stats->free_inodes = 0;
357
		stats->free_clusters = 0;
358
		stats->used_dirs = 0;
359 360 361
	}
}

362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
/*
 * 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
377
 * Parent's group is preferred, if it doesn't satisfy these
378 379 380 381 382
 * 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).
 */

383
static int find_group_orlov(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
384
			    ext4_group_t *group, umode_t mode,
385
			    const struct qstr *qstr)
386
{
387
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
388
	struct ext4_sb_info *sbi = EXT4_SB(sb);
389
	ext4_group_t real_ngroups = ext4_get_groups_count(sb);
390
	int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
391
	unsigned int freei, avefreei, grp_free;
392
	ext4_fsblk_t freeb, avefreec;
393
	unsigned int ndirs;
394
	int max_dirs, min_inodes;
395
	ext4_grpblk_t min_clusters;
396
	ext4_group_t i, grp, g, ngroups;
397
	struct ext4_group_desc *desc;
398 399
	struct orlov_stats stats;
	int flex_size = ext4_flex_bg_size(sbi);
400
	struct dx_hash_info hinfo;
401

402
	ngroups = real_ngroups;
403
	if (flex_size > 1) {
404
		ngroups = (real_ngroups + flex_size - 1) >>
405 406 407
			sbi->s_log_groups_per_flex;
		parent_group >>= sbi->s_log_groups_per_flex;
	}
408 409 410

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
411 412
	freeb = EXT4_C2B(sbi,
		percpu_counter_read_positive(&sbi->s_freeclusters_counter));
413 414
	avefreec = freeb;
	do_div(avefreec, ngroups);
415 416
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

417 418
	if (S_ISDIR(mode) &&
	    ((parent == sb->s_root->d_inode) ||
419
	     (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
420
		int best_ndir = inodes_per_group;
421
		int ret = -1;
422

423 424 425 426 427 428 429
		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
			get_random_bytes(&grp, sizeof(grp));
430
		parent_group = (unsigned)grp % ngroups;
431
		for (i = 0; i < ngroups; i++) {
432 433 434
			g = (parent_group + i) % ngroups;
			get_orlov_stats(sb, g, flex_size, &stats);
			if (!stats.free_inodes)
435
				continue;
436
			if (stats.used_dirs >= best_ndir)
437
				continue;
438
			if (stats.free_inodes < avefreei)
439
				continue;
440
			if (stats.free_clusters < avefreec)
441
				continue;
442
			grp = g;
443
			ret = 0;
444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462
			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++) {
463
			if (grp+i >= real_ngroups)
464 465 466 467 468 469
				break;
			desc = ext4_get_group_desc(sb, grp+i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = grp+i;
				return 0;
			}
470 471 472 473 474
		}
		goto fallback;
	}

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
475 476 477
	min_inodes = avefreei - inodes_per_group*flex_size / 4;
	if (min_inodes < 1)
		min_inodes = 1;
478
	min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
479 480 481 482 483 484 485 486 487 488

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

	for (i = 0; i < ngroups; i++) {
491 492 493
		grp = (parent_group + i) % ngroups;
		get_orlov_stats(sb, grp, flex_size, &stats);
		if (stats.used_dirs >= max_dirs)
494
			continue;
495
		if (stats.free_inodes < min_inodes)
496
			continue;
497
		if (stats.free_clusters < min_clusters)
498
			continue;
499
		goto found_flex_bg;
500 501 502
	}

fallback:
503
	ngroups = real_ngroups;
504
	avefreei = freei / ngroups;
505
fallback_retry:
506
	parent_group = EXT4_I(parent)->i_block_group;
507
	for (i = 0; i < ngroups; i++) {
508 509
		grp = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, grp, NULL);
510 511 512 513 514 515
		if (desc) {
			grp_free = ext4_free_inodes_count(sb, desc);
			if (grp_free && grp_free >= avefreei) {
				*group = grp;
				return 0;
			}
516
		}
517 518 519 520 521 522 523 524
	}

	if (avefreei) {
		/*
		 * The free-inodes counter is approximate, and for really small
		 * filesystems the above test can fail to find any blockgroups
		 */
		avefreei = 0;
525
		goto fallback_retry;
526 527 528 529 530
	}

	return -1;
}

531
static int find_group_other(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
532
			    ext4_group_t *group, umode_t mode)
533
{
534
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
535
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
536
	struct ext4_group_desc *desc;
537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573
	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;
574
		return find_group_orlov(sb, parent, group, mode, NULL);
575
	}
576 577 578 579

	/*
	 * Try to place the inode in its parent directory
	 */
580 581
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
582
	if (desc && ext4_free_inodes_count(sb, desc) &&
583
	    ext4_free_group_clusters(sb, desc))
584
		return 0;
585 586 587 588 589 590 591 592 593 594

	/*
	 * 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.
	 */
595
	*group = (*group + parent->i_ino) % ngroups;
596 597 598 599 600 601

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
602 603 604 605
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
606
		if (desc && ext4_free_inodes_count(sb, desc) &&
607
		    ext4_free_group_clusters(sb, desc))
608
			return 0;
609 610 611 612 613 614
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
615
	*group = parent_group;
616
	for (i = 0; i < ngroups; i++) {
617 618 619
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
620
		if (desc && ext4_free_inodes_count(sb, desc))
621
			return 0;
622 623 624 625 626
	}

	return -1;
}

627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671
/*
 * 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;
}

672 673 674 675 676 677 678 679 680 681
/*
 * 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.
 */
682 683 684 685
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)
686 687
{
	struct super_block *sb;
A
Aneesh Kumar K.V 已提交
688 689
	struct buffer_head *inode_bitmap_bh = NULL;
	struct buffer_head *group_desc_bh;
690
	ext4_group_t ngroups, group = 0;
691
	unsigned long ino = 0;
692 693
	struct inode *inode;
	struct ext4_group_desc *gdp = NULL;
694 695
	struct ext4_inode_info *ei;
	struct ext4_sb_info *sbi;
696
	int ret2, err = 0;
697
	struct inode *ret;
698
	ext4_group_t i;
699
	ext4_group_t flex_group;
700 701 702 703 704 705

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

	sb = dir->i_sb;
706
	ngroups = ext4_get_groups_count(sb);
707
	trace_ext4_request_inode(dir, mode);
708 709 710
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
711 712
	ei = EXT4_I(inode);
	sbi = EXT4_SB(sb);
713

714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730
	/*
	 * 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);

731 732 733
	if (!goal)
		goal = sbi->s_inode_goal;

734
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
735 736 737 738 739 740
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

L
Lukas Czerner 已提交
741 742 743
	if (S_ISDIR(mode))
		ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
	else
744
		ret2 = find_group_other(sb, dir, &group, mode);
745

746
got_group:
747
	EXT4_I(dir)->i_last_alloc_group = group;
748
	err = -ENOSPC;
749
	if (ret2 == -1)
750 751
		goto out;

752 753 754 755 756
	/*
	 * 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.
	 */
757
	for (i = 0; i < ngroups; i++, ino = 0) {
758 759
		err = -EIO;

A
Aneesh Kumar K.V 已提交
760
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
761
		if (!gdp)
762
			goto out;
763

764 765 766 767 768 769 770 771 772
		/*
		 * Check free inodes count before loading bitmap.
		 */
		if (ext4_free_inodes_count(sb, gdp) == 0) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

A
Aneesh Kumar K.V 已提交
773 774 775
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
		if (!inode_bitmap_bh)
776
			goto out;
777 778

repeat_in_this_group:
779
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
780 781
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);
782 783
		if (ino >= EXT4_INODES_PER_GROUP(sb))
			goto next_group;
784 785 786 787 788
		if (group == 0 && (ino+1) < EXT4_FIRST_INO(sb)) {
			ext4_error(sb, "reserved inode found cleared - "
				   "inode=%lu", ino + 1);
			continue;
		}
789 790 791 792 793
		if ((EXT4_SB(sb)->s_journal == NULL) &&
		    recently_deleted(sb, group, ino)) {
			ino++;
			goto next_inode;
		}
794 795 796
		if (!handle) {
			BUG_ON(nblocks <= 0);
			handle = __ext4_journal_start_sb(dir->i_sb, line_no,
797 798
							 handle_type, nblocks,
							 0);
799 800
			if (IS_ERR(handle)) {
				err = PTR_ERR(handle);
801 802
				ext4_std_error(sb, err);
				goto out;
803 804
			}
		}
805 806
		BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
		err = ext4_journal_get_write_access(handle, inode_bitmap_bh);
807 808 809 810
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
811 812 813 814 815 816
		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! */
817
next_inode:
818 819
		if (ino < EXT4_INODES_PER_GROUP(sb))
			goto repeat_in_this_group;
820 821 822
next_group:
		if (++group == ngroups)
			group = 0;
823 824 825 826 827
	}
	err = -ENOSPC;
	goto out;

got:
828 829
	BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
830 831 832 833
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
834

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

A
Aneesh Kumar K.V 已提交
840 841 842
		block_bitmap_bh = ext4_read_block_bitmap(sb, group);
		BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
		err = ext4_journal_get_write_access(handle, block_bitmap_bh);
A
Andreas Dilger 已提交
843
		if (err) {
A
Aneesh Kumar K.V 已提交
844
			brelse(block_bitmap_bh);
845 846
			ext4_std_error(sb, err);
			goto out;
A
Andreas Dilger 已提交
847 848
		}

849 850 851
		BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
		err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);

A
Andreas Dilger 已提交
852
		/* recheck and clear flag under lock if we still need to */
853
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
854
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
855
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
856
			ext4_free_group_clusters_set(sb, gdp,
857
				ext4_free_clusters_after_init(sb, group, gdp));
858
			ext4_block_bitmap_csum_set(sb, group, gdp,
859
						   block_bitmap_bh);
860
			ext4_group_desc_csum_set(sb, group, gdp);
A
Andreas Dilger 已提交
861
		}
862
		ext4_unlock_group(sb, group);
863
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
864

865 866 867 868
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
A
Andreas Dilger 已提交
869
	}
870 871 872

	BUFFER_TRACE(group_desc_bh, "get_write_access");
	err = ext4_journal_get_write_access(handle, group_desc_bh);
873 874 875 876
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
877 878

	/* Update the relevant bg descriptor fields */
879
	if (ext4_has_group_desc_csum(sb)) {
880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899
		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);
900 901
	} else {
		ext4_lock_group(sb, group);
902
	}
903

904 905 906 907 908 909 910 911 912
	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);
		}
	}
913 914 915
	if (ext4_has_group_desc_csum(sb)) {
		ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
					   EXT4_INODES_PER_GROUP(sb) / 8);
916
		ext4_group_desc_csum_set(sb, group, gdp);
917
	}
918
	ext4_unlock_group(sb, group);
919

A
Aneesh Kumar K.V 已提交
920 921
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
922 923 924 925
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
926 927 928 929 930

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

931 932
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
933
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
934
	}
935

A
Andreas Dilger 已提交
936
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
937 938
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
939 940
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
941 942 943 944 945

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

946
	/* Don't inherit extent flag from directory, amongst others. */
947 948
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
949 950 951
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
952
	ei->i_last_alloc_group = ~0;
953

954
	ext4_set_inode_flags(inode);
955
	if (IS_DIRSYNC(inode))
956
		ext4_handle_sync(handle);
A
Al Viro 已提交
957
	if (insert_inode_locked(inode) < 0) {
958 959 960 961 962
		/*
		 * Likely a bitmap corruption causing inode to be allocated
		 * twice.
		 */
		err = -EIO;
963 964 965
		ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
			   inode->i_ino);
		goto out;
A
Al Viro 已提交
966
	}
967 968 969 970
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

971 972 973 974 975 976 977 978 979 980 981 982
	/* Precompute checksum seed for inode metadata */
	if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
			EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
		__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));
	}

983
	ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
984
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
985 986

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
987

T
Tao Ma 已提交
988 989 990 991
	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);

992
	ret = inode;
993 994
	err = dquot_alloc_inode(inode);
	if (err)
995 996
		goto fail_drop;

997
	err = ext4_init_acl(handle, inode, dir);
998 999 1000
	if (err)
		goto fail_free_drop;

1001
	err = ext4_init_security(handle, inode, dir, qstr);
1002 1003 1004
	if (err)
		goto fail_free_drop;

1005
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
1006
		/* set extent flag only for directory, file and normal symlink*/
1007
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1008
			ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1009 1010
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1011
	}
1012

1013 1014 1015 1016 1017
	if (ext4_handle_valid(handle)) {
		ei->i_sync_tid = handle->h_transaction->t_tid;
		ei->i_datasync_tid = handle->h_transaction->t_tid;
	}

1018 1019 1020 1021 1022 1023
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1024
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1025
	trace_ext4_allocate_inode(inode, dir, mode);
A
Aneesh Kumar K.V 已提交
1026
	brelse(inode_bitmap_bh);
1027 1028 1029
	return ret;

fail_free_drop:
1030
	dquot_free_inode(inode);
1031
fail_drop:
1032
	clear_nlink(inode);
A
Al Viro 已提交
1033
	unlock_new_inode(inode);
1034 1035 1036
out:
	dquot_drop(inode);
	inode->i_flags |= S_NOQUOTA;
1037
	iput(inode);
A
Aneesh Kumar K.V 已提交
1038
	brelse(inode_bitmap_bh);
1039 1040 1041 1042
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1043
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1044
{
1045
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1046
	ext4_group_t block_group;
1047
	int bit;
1048
	struct buffer_head *bitmap_bh;
1049
	struct inode *inode = NULL;
1050
	long err = -EIO;
1051 1052 1053

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

1058 1059
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1060
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1061
	if (!bitmap_bh) {
1062
		ext4_warning(sb, "inode bitmap error for orphan %lu", ino);
1063
		goto error;
1064 1065 1066 1067 1068 1069
	}

	/* 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.
	 */
1070 1071 1072 1073 1074 1075 1076
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1077 1078 1079 1080 1081 1082 1083 1084
	/*
	 * 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;

1085 1086 1087 1088 1089 1090 1091 1092 1093
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1094
	ext4_warning(sb, "bad orphan inode %lu!  e2fsck was run?", ino);
1095
	printk(KERN_WARNING "ext4_test_bit(bit=%d, block=%llu) = %d\n",
1096 1097
	       bit, (unsigned long long)bitmap_bh->b_blocknr,
	       ext4_test_bit(bit, bitmap_bh->b_data));
1098
	printk(KERN_WARNING "inode=%p\n", inode);
1099
	if (inode) {
1100
		printk(KERN_WARNING "is_bad_inode(inode)=%d\n",
1101
		       is_bad_inode(inode));
1102
		printk(KERN_WARNING "NEXT_ORPHAN(inode)=%u\n",
1103
		       NEXT_ORPHAN(inode));
1104 1105
		printk(KERN_WARNING "max_ino=%lu\n", max_ino);
		printk(KERN_WARNING "i_nlink=%u\n", inode->i_nlink);
1106
		/* Avoid freeing blocks if we got a bad deleted inode */
1107
		if (inode->i_nlink == 0)
1108 1109 1110 1111
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1112 1113
error:
	return ERR_PTR(err);
1114 1115
}

1116
unsigned long ext4_count_free_inodes(struct super_block *sb)
1117 1118
{
	unsigned long desc_count;
1119
	struct ext4_group_desc *gdp;
1120
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1121 1122
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1123 1124 1125
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1126
	es = EXT4_SB(sb)->s_es;
1127 1128 1129
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1130
	for (i = 0; i < ngroups; i++) {
1131
		gdp = ext4_get_group_desc(sb, i, NULL);
1132 1133
		if (!gdp)
			continue;
1134
		desc_count += ext4_free_inodes_count(sb, gdp);
1135
		brelse(bitmap_bh);
1136
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1137 1138 1139
		if (!bitmap_bh)
			continue;

1140 1141
		x = ext4_count_free(bitmap_bh->b_data,
				    EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1142
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1143
			(unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
1144 1145 1146
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1147 1148 1149
	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);
1150 1151 1152
	return desc_count;
#else
	desc_count = 0;
1153
	for (i = 0; i < ngroups; i++) {
1154
		gdp = ext4_get_group_desc(sb, i, NULL);
1155 1156
		if (!gdp)
			continue;
1157
		desc_count += ext4_free_inodes_count(sb, gdp);
1158 1159 1160 1161 1162 1163 1164
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1165
unsigned long ext4_count_dirs(struct super_block * sb)
1166 1167
{
	unsigned long count = 0;
1168
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1169

1170
	for (i = 0; i < ngroups; i++) {
1171
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1172 1173
		if (!gdp)
			continue;
1174
		count += ext4_used_dirs_count(sb, gdp);
1175 1176 1177
	}
	return count;
}
1178 1179 1180 1181 1182 1183 1184

/*
 * 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
1185
 * block ext4_new_inode() until we are finished.
1186
 */
1187
int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214
				 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;

1215
	handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231
	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);

1232
	if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
1233 1234 1235
		ext4_error(sb, "Something is wrong with group %u: "
			   "used itable blocks: %d; "
			   "itable unused count: %u",
1236 1237 1238
			   group, used_blks,
			   ext4_itable_unused_count(sb, gdp));
		ret = 1;
1239
		goto err_out;
1240 1241
	}

1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260
	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);
1261
	ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1262 1263
	if (ret < 0)
		goto err_out;
1264 1265
	if (barrier)
		blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1266 1267 1268 1269

skip_zeroout:
	ext4_lock_group(sb, group);
	gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
1270
	ext4_group_desc_csum_set(sb, group, gdp);
1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
	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;
}