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 25
#include <linux/cred.h>

26
#include <asm/byteorder.h>
27

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

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

35 36 37 38 39 40 41 42 43 44 45 46 47 48
/*
 * 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.
 */

49 50 51 52 53
/*
 * 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.
 */
54
void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
55 56 57 58 59 60 61 62 63 64 65 66 67 68
{
	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 */
69
static int ext4_init_inode_bitmap(struct super_block *sb,
70 71 72
				       struct buffer_head *bh,
				       ext4_group_t block_group,
				       struct ext4_group_desc *gdp)
73
{
74
	struct ext4_group_info *grp;
75
	struct ext4_sb_info *sbi = EXT4_SB(sb);
76 77 78 79
	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. */
80
	if (!ext4_group_desc_csum_verify(sb, block_group, gdp)) {
81
		grp = ext4_get_group_info(sb, block_group);
82 83 84
		if (!EXT4_MB_GRP_BBITMAP_CORRUPT(grp))
			percpu_counter_sub(&sbi->s_freeclusters_counter,
					   grp->bb_free);
85
		set_bit(EXT4_GROUP_INFO_BBITMAP_CORRUPT_BIT, &grp->bb_state);
86 87 88 89 90 91
		if (!EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) {
			int count;
			count = ext4_free_inodes_count(sb, gdp);
			percpu_counter_sub(&sbi->s_freeinodes_counter,
					   count);
		}
92
		set_bit(EXT4_GROUP_INFO_IBITMAP_CORRUPT_BIT, &grp->bb_state);
93
		return -EFSBADCRC;
94 95 96
	}

	memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
97
	ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), sb->s_blocksize * 8,
98
			bh->b_data);
99 100
	ext4_inode_bitmap_csum_set(sb, block_group, gdp, bh,
				   EXT4_INODES_PER_GROUP(sb) / 8);
101
	ext4_group_desc_csum_set(sb, block_group, gdp);
102

103
	return 0;
104
}
105

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

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 151
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;
}

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

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

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

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

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

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

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

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

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

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

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

	is_directory = S_ISDIR(inode->i_mode);

	/* Do this BEFORE marking the inode not in use or returning an error */
Al Viro's avatar
Al Viro committed
304
	ext4_clear_inode(inode);
305

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

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

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

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

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

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

383 384
error_return:
	brelse(bitmap_bh);
385
	ext4_std_error(sb, fatal);
386 387
}

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

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

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

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

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

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

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

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

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

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

	/*
	 * 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;
	}
551 552

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

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

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

	return -1;
}

593
static int find_group_other(struct super_block *sb, struct inode *parent,
Al Viro's avatar
Al Viro committed
594
			    ext4_group_t *group, umode_t mode)
595
{
596
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
597
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
598
	struct ext4_group_desc *desc;
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 634 635
	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;
636
		return find_group_orlov(sb, parent, group, mode, NULL);
637
	}
638 639 640 641

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

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

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

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

	return -1;
}

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 732 733
/*
 * 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;
}

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

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

769 770 771
	if (unlikely(ext4_forced_shutdown(EXT4_SB(dir->i_sb))))
		return ERR_PTR(-EIO);

772 773 774
	if ((ext4_encrypted_inode(dir) ||
	     DUMMY_ENCRYPTION_ENABLED(EXT4_SB(dir->i_sb))) &&
	    (S_ISREG(mode) || S_ISDIR(mode) || S_ISLNK(mode))) {
775
		err = fscrypt_get_encryption_info(dir);
776 777
		if (err)
			return ERR_PTR(err);
778
		if (!fscrypt_has_encryption_key(dir))
779
			return ERR_PTR(-ENOKEY);
780 781 782 783 784
		if (!handle)
			nblocks += EXT4_DATA_TRANS_BLOCKS(dir->i_sb);
		encrypt = 1;
	}

785
	sb = dir->i_sb;
786
	ngroups = ext4_get_groups_count(sb);
787
	trace_ext4_request_inode(dir, mode);
788 789 790
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
791 792
	ei = EXT4_I(inode);
	sbi = EXT4_SB(sb);
793

794
	/*
795
	 * Initialize owners and quota early so that we don't have to account
796 797 798 799 800 801 802 803 804 805 806 807 808
	 * 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);
Li Xi's avatar
Li Xi committed
809

Kaho Ng's avatar
Kaho Ng committed
810
	if (ext4_has_feature_project(sb) &&
Li Xi's avatar
Li Xi committed
811 812 813 814 815
	    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);

816 817 818
	err = dquot_initialize(inode);
	if (err)
		goto out;
819

820 821 822
	if (!goal)
		goal = sbi->s_inode_goal;

823
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
824 825 826 827 828 829
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

830 831 832
	if (S_ISDIR(mode))
		ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
	else
833
		ret2 = find_group_other(sb, dir, &group, mode);
834

835
got_group:
836
	EXT4_I(dir)->i_last_alloc_group = group;
837
	err = -ENOSPC;
838
	if (ret2 == -1)
839 840
		goto out;

841 842 843 844 845
	/*
	 * 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.
	 */
846
	for (i = 0; i < ngroups; i++, ino = 0) {
847 848
		err = -EIO;

Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
849
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
850
		if (!gdp)
851
			goto out;
852

853 854 855 856 857 858 859 860 861
		/*
		 * Check free inodes count before loading bitmap.
		 */
		if (ext4_free_inodes_count(sb, gdp) == 0) {
			if (++group == ngroups)
				group = 0;
			continue;
		}

862 863 864 865 866 867 868 869
		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;
		}

Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
870 871
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
872
		/* Skip groups with suspicious inode tables */
873 874 875
		if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp) ||
		    IS_ERR(inode_bitmap_bh)) {
			inode_bitmap_bh = NULL;
876 877 878 879
			if (++group == ngroups)
				group = 0;
			continue;
		}
880 881

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

got:
931 932
	BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
933 934 935 936
	if (err) {
		ext4_std_error(sb, err);
		goto out;
	}
937

938 939 940 941 942 943 944
	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;
	}

945
	/* We may have to initialize the block bitmap if it isn't already */
946
	if (ext4_has_group_desc_csum(sb) &&
947
	    gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
948
		struct buffer_head *block_bitmap_bh;
949

Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
950
		block_bitmap_bh = ext4_read_block_bitmap(sb, group);
951 952
		if (IS_ERR(block_bitmap_bh)) {
			err = PTR_ERR(block_bitmap_bh);
953 954
			goto out;
		}
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
955 956
		BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
		err = ext4_journal_get_write_access(handle, block_bitmap_bh);
957
		if (err) {
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
958
			brelse(block_bitmap_bh);
959 960
			ext4_std_error(sb, err);
			goto out;
961 962
		}

963 964 965
		BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
		err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);

966
		/* recheck and clear flag under lock if we still need to */
967
		ext4_lock_group(sb, group);
968
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
969
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
970
			ext4_free_group_clusters_set(sb, gdp,
971
				ext4_free_clusters_after_init(sb, group, gdp));
972
			ext4_block_bitmap_csum_set(sb, group, gdp,
973
						   block_bitmap_bh);
974
			ext4_group_desc_csum_set(sb, group, gdp);
975
		}
976
		ext4_unlock_group(sb, group);
977
		brelse(block_bitmap_bh);
978

979 980 981 982
		if (err) {
			ext4_std_error(sb, err);
			goto out;
		}
983
	}
984 985

	/* Update the relevant bg descriptor fields */
986
	if (ext4_has_group_desc_csum(sb)) {
987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004