ialloc.c 38.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
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
		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);
92
		return -EFSBADCRC;
A
Andreas Dilger 已提交
93 94 95
	}

	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
	return 0;
A
Andreas Dilger 已提交
103
}
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 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 150
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;
}

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

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

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

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

186
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
187
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
188
		err = ext4_init_inode_bitmap(sb, bh, block_group, desc);
189
		set_bitmap_uptodate(bh);
190
		set_buffer_uptodate(bh);
191
		set_buffer_verified(bh);
192
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
193
		unlock_buffer(bh);
194 195
		if (err)
			goto out;
196
		return bh;
A
Andreas Dilger 已提交
197
	}
198
	ext4_unlock_group(sb, block_group);
199

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

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

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

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

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

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

	is_directory = S_ISDIR(inode->i_mode);

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

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

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

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

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

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

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

379 380
error_return:
	brelse(bitmap_bh);
381
	ext4_std_error(sb, fatal);
382 383
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return -1;
}

589
static int find_group_other(struct super_block *sb, struct inode *parent,
A
Al Viro 已提交
590
			    ext4_group_t *group, umode_t mode)
591
{
592
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
593
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
594
	struct ext4_group_desc *desc;
595 596 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
	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;
632
		return find_group_orlov(sb, parent, group, mode, NULL);
633
	}
634 635 636 637

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

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

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

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

	return -1;
}

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

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

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

765 766 767 768 769 770 771 772 773 774 775 776 777
	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;
	}

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

787 788 789 790 791 792 793 794 795 796 797 798 799 800 801
	/*
	 * 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);
802 803 804
	err = dquot_initialize(inode);
	if (err)
		goto out;
805

806 807 808
	if (!goal)
		goal = sbi->s_inode_goal;

809
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
810 811 812 813 814 815
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

L
Lukas Czerner 已提交
816 817 818
	if (S_ISDIR(mode))
		ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
	else
819
		ret2 = find_group_other(sb, dir, &group, mode);
820

821
got_group:
822
	EXT4_I(dir)->i_last_alloc_group = group;
823
	err = -ENOSPC;
824
	if (ret2 == -1)
825 826
		goto out;

827 828 829 830 831
	/*
	 * 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.
	 */
832
	for (i = 0; i < ngroups; i++, ino = 0) {
833 834
		err = -EIO;

A
Aneesh Kumar K.V 已提交
835
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
836
		if (!gdp)
837
			goto out;
838

839 840 841 842 843 844 845 846 847
		/*
		 * Check free inodes count before loading bitmap.
		 */
		if (ext4_free_inodes_count(sb, gdp) == 0) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

848 849 850 851 852 853 854 855
		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 已提交
856 857
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
858
		/* Skip groups with suspicious inode tables */
859 860 861
		if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp) ||
		    IS_ERR(inode_bitmap_bh)) {
			inode_bitmap_bh = NULL;
862 863 864 865
			if (++group == ngroups)
				group = 0;
			continue;
		}
866 867

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

got:
917 918
	BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
919 920 921 922
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
923

924 925 926 927 928 929 930
	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 已提交
931
	/* We may have to initialize the block bitmap if it isn't already */
932
	if (ext4_has_group_desc_csum(sb) &&
A
Andreas Dilger 已提交
933
	    gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
934
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
935

A
Aneesh Kumar K.V 已提交
936
		block_bitmap_bh = ext4_read_block_bitmap(sb, group);
937 938
		if (IS_ERR(block_bitmap_bh)) {
			err = PTR_ERR(block_bitmap_bh);
939 940
			goto out;
		}
A
Aneesh Kumar K.V 已提交
941 942
		BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
		err = ext4_journal_get_write_access(handle, block_bitmap_bh);
A
Andreas Dilger 已提交
943
		if (err) {
A
Aneesh Kumar K.V 已提交
944
			brelse(block_bitmap_bh);
945 946
			ext4_std_error(sb, err);
			goto out;
A
Andreas Dilger 已提交
947 948
		}

949 950 951
		BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
		err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);

A
Andreas Dilger 已提交
952
		/* recheck and clear flag under lock if we still need to */
953
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
954
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
955
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
956
			ext4_free_group_clusters_set(sb, gdp,
957
				ext4_free_clusters_after_init(sb, group, gdp));
958
			ext4_block_bitmap_csum_set(sb, group, gdp,
959
						   block_bitmap_bh);
960
			ext4_group_desc_csum_set(sb, group, gdp);
A
Andreas Dilger 已提交
961
		}
962
		ext4_unlock_group(sb, group);
963
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
964

965 966 967 968
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
A
Andreas Dilger 已提交
969
	}
970 971

	/* Update the relevant bg descriptor fields */
972
	if (ext4_has_group_desc_csum(sb)) {
973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992
		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);
993 994
	} else {
		ext4_lock_group(sb, group);
995
	}
996

997 998 999 1000 1001 1002 1003 1004 1005
	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);
		}
	}
1006 1007 1008
	if (ext4_has_group_desc_csum(sb)) {
		ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
					   EXT4_INODES_PER_GROUP(sb) / 8);
1009
		ext4_group_desc_csum_set(sb, group, gdp);
1010
	}
1011
	ext4_unlock_group(sb, group);
1012

A
Aneesh Kumar K.V 已提交
1013 1014
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
1015 1016 1017 1018
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
1019 1020 1021 1022 1023

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

1024 1025
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
1026
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
1027
	}
1028

A
Andreas Dilger 已提交
1029
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
1030 1031
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
1032 1033
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
1034 1035 1036 1037 1038

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

1039
	/* Don't inherit extent flag from directory, amongst others. */
1040 1041
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
1042 1043 1044
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
1045
	ei->i_last_alloc_group = ~0;
1046

1047
	ext4_set_inode_flags(inode);
1048
	if (IS_DIRSYNC(inode))
1049
		ext4_handle_sync(handle);
A
Al Viro 已提交
1050
	if (insert_inode_locked(inode) < 0) {
1051 1052 1053 1054 1055
		/*
		 * Likely a bitmap corruption causing inode to be allocated
		 * twice.
		 */
		err = -EIO;
1056 1057 1058
		ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
			   inode->i_ino);
		goto out;
A
Al Viro 已提交
1059
	}
1060 1061 1062 1063
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

1064
	/* Precompute checksum seed for inode metadata */
1065
	if (ext4_has_metadata_csum(sb)) {
1066 1067 1068 1069 1070 1071 1072 1073 1074
		__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));
	}

1075
	ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
1076
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
1077 1078

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
T
Tao Ma 已提交
1079
	ei->i_inline_off = 0;
1080
	if (ext4_has_feature_inline_data(sb))
T
Tao Ma 已提交
1081
		ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA);
1082
	ret = inode;
1083 1084
	err = dquot_alloc_inode(inode);
	if (err)
1085 1086
		goto fail_drop;

1087
	err = ext4_init_acl(handle, inode, dir);
1088 1089 1090
	if (err)
		goto fail_free_drop;

1091
	err = ext4_init_security(handle, inode, dir, qstr);
1092 1093 1094
	if (err)
		goto fail_free_drop;

1095
	if (ext4_has_feature_extents(sb)) {
1096
		/* set extent flag only for directory, file and normal symlink*/
1097
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1098
			ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1099 1100
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1101
	}
1102

1103 1104 1105 1106 1107
	if (ext4_handle_valid(handle)) {
		ei->i_sync_tid = handle->h_transaction->t_tid;
		ei->i_datasync_tid = handle->h_transaction->t_tid;
	}

1108 1109 1110 1111 1112 1113
	if (encrypt) {
		err = ext4_inherit_context(dir, inode);
		if (err)
			goto fail_free_drop;
	}

1114 1115 1116 1117 1118 1119
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1120
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1121
	trace_ext4_allocate_inode(inode, dir, mode);
A
Aneesh Kumar K.V 已提交
1122
	brelse(inode_bitmap_bh);
1123 1124 1125
	return ret;

fail_free_drop:
1126
	dquot_free_inode(inode);
1127
fail_drop:
1128
	clear_nlink(inode);
A
Al Viro 已提交
1129
	unlock_new_inode(inode);
1130 1131 1132
out:
	dquot_drop(inode);
	inode->i_flags |= S_NOQUOTA;
1133
	iput(inode);
A
Aneesh Kumar K.V 已提交
1134
	brelse(inode_bitmap_bh);
1135 1136 1137 1138
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1139
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1140
{
1141
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1142
	ext4_group_t block_group;
1143
	int bit;
1144
	struct buffer_head *bitmap_bh;
1145
	struct inode *inode = NULL;
1146
	long err = -EIO;
1147 1148 1149

	/* Error cases - e2fsck has already cleaned up for us */
	if (ino > max_ino) {
1150
		ext4_warning(sb, "bad orphan ino %lu!  e2fsck was run?", ino);
1151
		err = -EFSCORRUPTED;
1152
		goto error;
1153 1154
	}

1155 1156
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1157
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1158 1159 1160 1161
	if (IS_ERR(bitmap_bh)) {
		err = PTR_ERR(bitmap_bh);
		ext4_warning(sb, "inode bitmap error %ld for orphan %lu",
			     ino, err);
1162
		goto error;
1163 1164 1165 1166 1167 1168
	}

	/* 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.
	 */
1169 1170 1171 1172 1173 1174 1175
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1176 1177 1178 1179 1180 1181 1182 1183
	/*
	 * 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;

1184 1185 1186 1187 1188 1189 1190 1191 1192
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

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

1215
unsigned long ext4_count_free_inodes(struct super_block *sb)
1216 1217
{
	unsigned long desc_count;
1218
	struct ext4_group_desc *gdp;
1219
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1220 1221
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1222 1223 1224
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1225
	es = EXT4_SB(sb)->s_es;
1226 1227 1228
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1229
	for (i = 0; i < ngroups; i++) {
1230
		gdp = ext4_get_group_desc(sb, i, NULL);
1231 1232
		if (!gdp)
			continue;
1233
		desc_count += ext4_free_inodes_count(sb, gdp);
1234
		brelse(bitmap_bh);
1235
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1236 1237
		if (IS_ERR(bitmap_bh)) {
			bitmap_bh = NULL;
1238
			continue;
1239
		}
1240

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

/* Called at mount-time, super-block is locked */
1266
unsigned long ext4_count_dirs(struct super_block * sb)
1267 1268
{
	unsigned long count = 0;
1269
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1270

1271
	for (i = 0; i < ngroups; i++) {
1272
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1273 1274
		if (!gdp)
			continue;
1275
		count += ext4_used_dirs_count(sb, gdp);
1276 1277 1278
	}
	return count;
}
1279 1280 1281 1282 1283 1284 1285

/*
 * 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
1286
 * block ext4_new_inode() until we are finished.
1287
 */
1288
int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315
				 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;

1316
	handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
	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);

1333
	if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
1334 1335 1336
		ext4_error(sb, "Something is wrong with group %u: "
			   "used itable blocks: %d; "
			   "itable unused count: %u",
1337 1338 1339
			   group, used_blks,
			   ext4_itable_unused_count(sb, gdp));
		ret = 1;
1340
		goto err_out;
1341 1342
	}

1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361
	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);
1362
	ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1363 1364
	if (ret < 0)
		goto err_out;
1365 1366
	if (barrier)
		blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1367 1368 1369 1370

skip_zeroout:
	ext4_lock_group(sb, group);
	gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
1371
	ext4_group_desc_csum_set(sb, group, gdp);
1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384
	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;
}