ialloc.c 30.9 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
#include "ext4.h"
#include "ext4_jbd2.h"
28 29
#include "xattr.h"
#include "acl.h"
A
Andreas Dilger 已提交
30
#include "group.h"
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/*
 * 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 已提交
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
/*
 * 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.
 */
void mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
{
	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 */
66 67
unsigned ext4_init_inode_bitmap(struct super_block *sb, struct buffer_head *bh,
				ext4_group_t block_group,
A
Andreas Dilger 已提交
68 69 70 71 72 73 74 75 76
				struct ext4_group_desc *gdp)
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);

	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. */
	if (!ext4_group_desc_csum_verify(sbi, block_group, gdp)) {
77
		ext4_error(sb, __func__, "Checksum bad for group %u",
A
Andreas Dilger 已提交
78
			   block_group);
79 80 81
		ext4_free_blks_set(sb, gdp, 0);
		ext4_free_inodes_set(sb, gdp, 0);
		ext4_itable_unused_set(sb, gdp, 0);
A
Andreas Dilger 已提交
82 83 84 85 86
		memset(bh->b_data, 0xff, sb->s_blocksize);
		return 0;
	}

	memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
87
	mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), sb->s_blocksize * 8,
A
Andreas Dilger 已提交
88 89 90 91
			bh->b_data);

	return EXT4_INODES_PER_GROUP(sb);
}
92 93 94 95 96 97 98 99

/*
 * 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 *
100
ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
101
{
102
	struct ext4_group_desc *desc;
103
	struct buffer_head *bh = NULL;
104
	ext4_fsblk_t bitmap_blk;
105

106
	desc = ext4_get_group_desc(sb, block_group, NULL);
107
	if (!desc)
108 109 110 111 112 113
		return NULL;
	bitmap_blk = ext4_inode_bitmap(sb, desc);
	bh = sb_getblk(sb, bitmap_blk);
	if (unlikely(!bh)) {
		ext4_error(sb, __func__,
			    "Cannot read inode bitmap - "
114
			    "block_group = %u, inode_bitmap = %llu",
115 116 117
			    block_group, bitmap_blk);
		return NULL;
	}
118
	if (bitmap_uptodate(bh))
119 120
		return bh;

121
	lock_buffer(bh);
122 123 124 125
	if (bitmap_uptodate(bh)) {
		unlock_buffer(bh);
		return bh;
	}
126
	spin_lock(sb_bgl_lock(EXT4_SB(sb), block_group));
A
Andreas Dilger 已提交
127
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
128
		ext4_init_inode_bitmap(sb, bh, block_group, desc);
129
		set_bitmap_uptodate(bh);
130
		set_buffer_uptodate(bh);
131
		spin_unlock(sb_bgl_lock(EXT4_SB(sb), block_group));
A
Aneesh Kumar K.V 已提交
132
		unlock_buffer(bh);
133
		return bh;
A
Andreas Dilger 已提交
134
	}
135
	spin_unlock(sb_bgl_lock(EXT4_SB(sb), block_group));
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
	if (buffer_uptodate(bh)) {
		/*
		 * if not uninit if bh is uptodate,
		 * bitmap is also uptodate
		 */
		set_bitmap_uptodate(bh);
		unlock_buffer(bh);
		return bh;
	}
	/*
	 * submit the buffer_head for read. We can
	 * safely mark the bitmap as uptodate now.
	 * We do it here so the bitmap uptodate bit
	 * get set with buffer lock held.
	 */
	set_bitmap_uptodate(bh);
152 153 154
	if (bh_submit_read(bh) < 0) {
		put_bh(bh);
		ext4_error(sb, __func__,
155
			    "Cannot read inode bitmap - "
156
			    "block_group = %u, inode_bitmap = %llu",
157 158 159
			    block_group, bitmap_blk);
		return NULL;
	}
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
	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.
 */
179
void ext4_free_inode(handle_t *handle, struct inode *inode)
180
{
181
	struct super_block *sb = inode->i_sb;
182 183 184 185
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
186
	ext4_group_t block_group;
187
	unsigned long bit;
188 189
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
190
	struct ext4_sb_info *sbi;
191
	int fatal = 0, err, count, cleared;
192
	ext4_group_t flex_group;
193 194

	if (atomic_read(&inode->i_count) > 1) {
195 196
		printk(KERN_ERR "ext4_free_inode: inode has count=%d\n",
		       atomic_read(&inode->i_count));
197 198 199
		return;
	}
	if (inode->i_nlink) {
200 201
		printk(KERN_ERR "ext4_free_inode: inode has nlink=%d\n",
		       inode->i_nlink);
202 203 204
		return;
	}
	if (!sb) {
205 206
		printk(KERN_ERR "ext4_free_inode: inode on "
		       "nonexistent device\n");
207 208
		return;
	}
209
	sbi = EXT4_SB(sb);
210 211

	ino = inode->i_ino;
212
	ext4_debug("freeing inode %lu\n", ino);
213 214 215 216 217
	trace_mark(ext4_free_inode,
		   "dev %s ino %lu mode %d uid %lu gid %lu bocks %llu",
		   sb->s_id, inode->i_ino, inode->i_mode,
		   (unsigned long) inode->i_uid, (unsigned long) inode->i_gid,
		   (unsigned long long) inode->i_blocks);
218 219 220 221 222

	/*
	 * Note: we must free any quota before locking the superblock,
	 * as writing the quota to disk may need the lock as well.
	 */
223
	vfs_dq_init(inode);
224
	ext4_xattr_delete_inode(handle, inode);
225 226
	vfs_dq_free_inode(inode);
	vfs_dq_drop(inode);
227 228 229 230

	is_directory = S_ISDIR(inode->i_mode);

	/* Do this BEFORE marking the inode not in use or returning an error */
231
	clear_inode(inode);
232

233 234
	es = EXT4_SB(sb)->s_es;
	if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
235 236
		ext4_error(sb, "ext4_free_inode",
			   "reserved or nonexistent inode %lu", ino);
237 238
		goto error_return;
	}
239 240
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
241
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
242 243 244 245
	if (!bitmap_bh)
		goto error_return;

	BUFFER_TRACE(bitmap_bh, "get_write_access");
246
	fatal = ext4_journal_get_write_access(handle, bitmap_bh);
247 248 249 250
	if (fatal)
		goto error_return;

	/* Ok, now we can actually update the inode bitmaps.. */
251 252 253 254
	spin_lock(sb_bgl_lock(sbi, block_group));
	cleared = ext4_clear_bit(bit, bitmap_bh->b_data);
	spin_unlock(sb_bgl_lock(sbi, block_group));
	if (!cleared)
255 256
		ext4_error(sb, "ext4_free_inode",
			   "bit already cleared for inode %lu", ino);
257
	else {
258
		gdp = ext4_get_group_desc(sb, block_group, &bh2);
259 260

		BUFFER_TRACE(bh2, "get_write_access");
261
		fatal = ext4_journal_get_write_access(handle, bh2);
262 263 264 265
		if (fatal) goto error_return;

		if (gdp) {
			spin_lock(sb_bgl_lock(sbi, block_group));
266 267 268 269 270 271
			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);
			}
A
Andreas Dilger 已提交
272 273
			gdp->bg_checksum = ext4_group_desc_csum(sbi,
							block_group, gdp);
274 275 276 277 278
			spin_unlock(sb_bgl_lock(sbi, block_group));
			percpu_counter_inc(&sbi->s_freeinodes_counter);
			if (is_directory)
				percpu_counter_dec(&sbi->s_dirs_counter);

279 280 281 282 283 284
			if (sbi->s_log_groups_per_flex) {
				flex_group = ext4_flex_group(sbi, block_group);
				spin_lock(sb_bgl_lock(sbi, flex_group));
				sbi->s_flex_groups[flex_group].free_inodes++;
				spin_unlock(sb_bgl_lock(sbi, flex_group));
			}
285
		}
286 287
		BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
		err = ext4_handle_dirty_metadata(handle, NULL, bh2);
288 289
		if (!fatal) fatal = err;
	}
290 291
	BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
292 293 294 295 296
	if (!fatal)
		fatal = err;
	sb->s_dirt = 1;
error_return:
	brelse(bitmap_bh);
297
	ext4_std_error(sb, fatal);
298 299 300 301 302 303 304 305 306 307 308 309
}

/*
 * 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.
 */
310 311
static int find_group_dir(struct super_block *sb, struct inode *parent,
				ext4_group_t *best_group)
312
{
313
	ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
314
	unsigned int freei, avefreei;
315
	struct ext4_group_desc *desc, *best_desc = NULL;
316 317
	ext4_group_t group;
	int ret = -1;
318

319
	freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
320 321 322
	avefreei = freei / ngroups;

	for (group = 0; group < ngroups; group++) {
323
		desc = ext4_get_group_desc(sb, group, NULL);
324
		if (!desc || !ext4_free_inodes_count(sb, desc))
325
			continue;
326
		if (ext4_free_inodes_count(sb, desc) < avefreei)
327 328
			continue;
		if (!best_desc ||
329 330
		    (ext4_free_blks_count(sb, desc) >
		     ext4_free_blks_count(sb, best_desc))) {
331
			*best_group = group;
332
			best_desc = desc;
333
			ret = 0;
334 335
		}
	}
336
	return ret;
337 338
}

339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
#define free_block_ratio 10

static int find_group_flex(struct super_block *sb, struct inode *parent,
			   ext4_group_t *best_group)
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_group_desc *desc;
	struct buffer_head *bh;
	struct flex_groups *flex_group = sbi->s_flex_groups;
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
	ext4_group_t parent_fbg_group = ext4_flex_group(sbi, parent_group);
	ext4_group_t ngroups = sbi->s_groups_count;
	int flex_size = ext4_flex_bg_size(sbi);
	ext4_group_t best_flex = parent_fbg_group;
	int blocks_per_flex = sbi->s_blocks_per_group * flex_size;
	int flexbg_free_blocks;
	int flex_freeb_ratio;
	ext4_group_t n_fbg_groups;
	ext4_group_t i;

	n_fbg_groups = (sbi->s_groups_count + flex_size - 1) >>
		sbi->s_log_groups_per_flex;

find_close_to_parent:
	flexbg_free_blocks = flex_group[best_flex].free_blocks;
	flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;
	if (flex_group[best_flex].free_inodes &&
	    flex_freeb_ratio > free_block_ratio)
		goto found_flexbg;

	if (best_flex && best_flex == parent_fbg_group) {
		best_flex--;
		goto find_close_to_parent;
	}

	for (i = 0; i < n_fbg_groups; i++) {
		if (i == parent_fbg_group || i == parent_fbg_group - 1)
			continue;

		flexbg_free_blocks = flex_group[i].free_blocks;
		flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;

		if (flex_freeb_ratio > free_block_ratio &&
		    flex_group[i].free_inodes) {
			best_flex = i;
			goto found_flexbg;
		}

387
		if (flex_group[best_flex].free_inodes == 0 ||
388 389 390 391 392 393 394 395 396 397 398 399 400 401
		    (flex_group[i].free_blocks >
		     flex_group[best_flex].free_blocks &&
		     flex_group[i].free_inodes))
			best_flex = i;
	}

	if (!flex_group[best_flex].free_inodes ||
	    !flex_group[best_flex].free_blocks)
		return -1;

found_flexbg:
	for (i = best_flex * flex_size; i < ngroups &&
		     i < (best_flex + 1) * flex_size; i++) {
		desc = ext4_get_group_desc(sb, i, &bh);
402
		if (ext4_free_inodes_count(sb, desc)) {
403 404 405 406 407 408 409 410 411 412
			*best_group = i;
			goto out;
		}
	}

	return -1;
out:
	return 0;
}

413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
/*
 * 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
 * it's already running too large debt (max_debt).
429
 * Parent's group is preferred, if it doesn't satisfy these
430 431 432 433 434 435 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).
 *
 * Debt is incremented each time we allocate a directory and decremented
 * when we allocate an inode, within 0--255.
 */

#define INODE_COST 64
#define BLOCK_COST 256

441 442
static int find_group_orlov(struct super_block *sb, struct inode *parent,
				ext4_group_t *group)
443
{
444
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
445 446
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_super_block *es = sbi->s_es;
447
	ext4_group_t ngroups = sbi->s_groups_count;
448
	int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
449
	unsigned int freei, avefreei;
450 451
	ext4_fsblk_t freeb, avefreeb;
	ext4_fsblk_t blocks_per_dir;
452 453
	unsigned int ndirs;
	int max_debt, max_dirs, min_inodes;
454
	ext4_grpblk_t min_blocks;
455
	ext4_group_t i;
456
	struct ext4_group_desc *desc;
457 458 459 460

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
	freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
461
	avefreeb = freeb;
A
Andrew Morton 已提交
462
	do_div(avefreeb, ngroups);
463 464 465
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

	if ((parent == sb->s_root->d_inode) ||
466
	    (EXT4_I(parent)->i_flags & EXT4_TOPDIR_FL)) {
467
		int best_ndir = inodes_per_group;
468 469
		ext4_group_t grp;
		int ret = -1;
470

471 472
		get_random_bytes(&grp, sizeof(grp));
		parent_group = (unsigned)grp % ngroups;
473
		for (i = 0; i < ngroups; i++) {
474 475
			grp = (parent_group + i) % ngroups;
			desc = ext4_get_group_desc(sb, grp, NULL);
476
			if (!desc || !ext4_free_inodes_count(sb, desc))
477
				continue;
478
			if (ext4_used_dirs_count(sb, desc) >= best_ndir)
479
				continue;
480
			if (ext4_free_inodes_count(sb, desc) < avefreei)
481
				continue;
482
			if (ext4_free_blks_count(sb, desc) < avefreeb)
483
				continue;
484 485
			*group = grp;
			ret = 0;
486
			best_ndir = ext4_used_dirs_count(sb, desc);
487
		}
488 489
		if (ret == 0)
			return ret;
490 491 492
		goto fallback;
	}

L
Laurent Vivier 已提交
493
	blocks_per_dir = ext4_blocks_count(es) - freeb;
A
Andrew Morton 已提交
494
	do_div(blocks_per_dir, ndirs);
495 496 497

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
	min_inodes = avefreei - inodes_per_group / 4;
498
	min_blocks = avefreeb - EXT4_BLOCKS_PER_GROUP(sb) / 4;
499

500
	max_debt = EXT4_BLOCKS_PER_GROUP(sb);
A
Andrew Morton 已提交
501
	max_debt /= max_t(int, blocks_per_dir, BLOCK_COST);
502 503 504 505 506 507 508 509
	if (max_debt * INODE_COST > inodes_per_group)
		max_debt = inodes_per_group / INODE_COST;
	if (max_debt > 255)
		max_debt = 255;
	if (max_debt == 0)
		max_debt = 1;

	for (i = 0; i < ngroups; i++) {
510 511
		*group = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
512
		if (!desc || !ext4_free_inodes_count(sb, desc))
513
			continue;
514
		if (ext4_used_dirs_count(sb, desc) >= max_dirs)
515
			continue;
516
		if (ext4_free_inodes_count(sb, desc) < min_inodes)
517
			continue;
518
		if (ext4_free_blks_count(sb, desc) < min_blocks)
519
			continue;
520
		return 0;
521 522 523 524
	}

fallback:
	for (i = 0; i < ngroups; i++) {
525 526
		*group = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
527 528
		if (desc && ext4_free_inodes_count(sb, desc) &&
			ext4_free_inodes_count(sb, desc) >= avefreei)
529
			return 0;
530 531 532 533 534 535 536 537 538 539 540 541 542 543
	}

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

	return -1;
}

544 545
static int find_group_other(struct super_block *sb, struct inode *parent,
				ext4_group_t *group)
546
{
547 548
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
	ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
549
	struct ext4_group_desc *desc;
550
	ext4_group_t i;
551 552 553 554

	/*
	 * Try to place the inode in its parent directory
	 */
555 556
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
557 558
	if (desc && ext4_free_inodes_count(sb, desc) &&
			ext4_free_blks_count(sb, desc))
559
		return 0;
560 561 562 563 564 565 566 567 568 569

	/*
	 * 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.
	 */
570
	*group = (*group + parent->i_ino) % ngroups;
571 572 573 574 575 576

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
577 578 579 580
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
581 582
		if (desc && ext4_free_inodes_count(sb, desc) &&
				ext4_free_blks_count(sb, desc))
583
			return 0;
584 585 586 587 588 589
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
590
	*group = parent_group;
591
	for (i = 0; i < ngroups; i++) {
592 593 594
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
595
		if (desc && ext4_free_inodes_count(sb, desc))
596
			return 0;
597 598 599 600 601
	}

	return -1;
}

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 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 672 673 674
/*
 * claim the inode from the inode bitmap. If the group
 * is uninit we need to take the groups's sb_bgl_lock
 * and clear the uninit flag. The inode bitmap update
 * and group desc uninit flag clear should be done
 * after holding sb_bgl_lock so that ext4_read_inode_bitmap
 * doesn't race with the ext4_claim_inode
 */
static int ext4_claim_inode(struct super_block *sb,
			struct buffer_head *inode_bitmap_bh,
			unsigned long ino, ext4_group_t group, int mode)
{
	int free = 0, retval = 0, count;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_group_desc *gdp = ext4_get_group_desc(sb, group, NULL);

	spin_lock(sb_bgl_lock(sbi, group));
	if (ext4_set_bit(ino, inode_bitmap_bh->b_data)) {
		/* not a free inode */
		retval = 1;
		goto err_ret;
	}
	ino++;
	if ((group == 0 && ino < EXT4_FIRST_INO(sb)) ||
			ino > EXT4_INODES_PER_GROUP(sb)) {
		spin_unlock(sb_bgl_lock(sbi, group));
		ext4_error(sb, __func__,
			   "reserved inode or inode > inodes count - "
			   "block_group = %u, inode=%lu", group,
			   ino + group * EXT4_INODES_PER_GROUP(sb));
		return 1;
	}
	/* If we didn't allocate from within the initialized part of the inode
	 * table then we need to initialize up to this inode. */
	if (EXT4_HAS_RO_COMPAT_FEATURE(sb, EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) {

		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
			/* When marking the block group with
			 * ~EXT4_BG_INODE_UNINIT we don't want to depend
			 * on the value of bg_itable_unused even though
			 * mke2fs could have initialized the same for us.
			 * Instead we calculated the value below
			 */

			free = 0;
		} else {
			free = EXT4_INODES_PER_GROUP(sb) -
				ext4_itable_unused_count(sb, gdp);
		}

		/*
		 * 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));
	}
	count = ext4_free_inodes_count(sb, gdp) - 1;
	ext4_free_inodes_set(sb, gdp, count);
	if (S_ISDIR(mode)) {
		count = ext4_used_dirs_count(sb, gdp) + 1;
		ext4_used_dirs_set(sb, gdp, count);
	}
	gdp->bg_checksum = ext4_group_desc_csum(sbi, group, gdp);
err_ret:
	spin_unlock(sb_bgl_lock(sbi, group));
	return retval;
}

675 676 677 678 679 680 681 682 683 684
/*
 * 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.
 */
685
struct inode *ext4_new_inode(handle_t *handle, struct inode *dir, int mode)
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 group = 0;
691
	unsigned long ino = 0;
692 693 694
	struct inode *inode;
	struct ext4_group_desc *gdp = NULL;
	struct ext4_super_block *es;
695 696
	struct ext4_inode_info *ei;
	struct ext4_sb_info *sbi;
697
	int ret2, err = 0;
698
	struct inode *ret;
699 700
	ext4_group_t i;
	int free = 0;
701
	static int once = 1;
702
	ext4_group_t flex_group;
703 704 705 706 707 708

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

	sb = dir->i_sb;
709 710
	trace_mark(ext4_request_inode, "dev %s dir %lu mode %d", sb->s_id,
		   dir->i_ino, mode);
711 712 713
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
714
	ei = EXT4_I(inode);
715

716
	sbi = EXT4_SB(sb);
717
	es = sbi->s_es;
718 719 720

	if (sbi->s_log_groups_per_flex) {
		ret2 = find_group_flex(sb, dir, &group);
721 722
		if (ret2 == -1) {
			ret2 = find_group_other(sb, dir, &group);
723 724
			if (ret2 == 0 && once)
				once = 0;
725 726 727 728
				printk(KERN_NOTICE "ext4: find_group_flex "
				       "failed, fallback succeeded dir %lu\n",
				       dir->i_ino);
		}
729 730 731
		goto got_group;
	}

732
	if (S_ISDIR(mode)) {
733
		if (test_opt(sb, OLDALLOC))
734
			ret2 = find_group_dir(sb, dir, &group);
735
		else
736
			ret2 = find_group_orlov(sb, dir, &group);
737
	} else
738
		ret2 = find_group_other(sb, dir, &group);
739

740
got_group:
741
	err = -ENOSPC;
742
	if (ret2 == -1)
743 744 745 746 747
		goto out;

	for (i = 0; i < sbi->s_groups_count; i++) {
		err = -EIO;

A
Aneesh Kumar K.V 已提交
748
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
749 750 751
		if (!gdp)
			goto fail;

A
Aneesh Kumar K.V 已提交
752 753 754
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
		if (!inode_bitmap_bh)
755 756 757 758 759
			goto fail;

		ino = 0;

repeat_in_this_group:
760
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
761 762 763
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);

764
		if (ino < EXT4_INODES_PER_GROUP(sb)) {
765

A
Aneesh Kumar K.V 已提交
766 767 768
			BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
			err = ext4_journal_get_write_access(handle,
							    inode_bitmap_bh);
769 770 771
			if (err)
				goto fail;

772 773 774 775 776 777 778
			BUFFER_TRACE(group_desc_bh, "get_write_access");
			err = ext4_journal_get_write_access(handle,
								group_desc_bh);
			if (err)
				goto fail;
			if (!ext4_claim_inode(sb, inode_bitmap_bh,
						ino, group, mode)) {
779
				/* we won it */
A
Aneesh Kumar K.V 已提交
780
				BUFFER_TRACE(inode_bitmap_bh,
781 782
					"call ext4_handle_dirty_metadata");
				err = ext4_handle_dirty_metadata(handle,
A
Aneesh Kumar K.V 已提交
783 784
								 inode,
							inode_bitmap_bh);
785 786
				if (err)
					goto fail;
787 788
				/* zero bit is inode number 1*/
				ino++;
789 790 791
				goto got;
			}
			/* we lost it */
A
Aneesh Kumar K.V 已提交
792
			ext4_handle_release_buffer(handle, inode_bitmap_bh);
793
			ext4_handle_release_buffer(handle, group_desc_bh);
794

795
			if (++ino < EXT4_INODES_PER_GROUP(sb))
796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812
				goto repeat_in_this_group;
		}

		/*
		 * This case is possible in concurrent environment.  It is very
		 * rare.  We cannot repeat the find_group_xxx() call because
		 * that will simply return the same blockgroup, because the
		 * group descriptor metadata has not yet been updated.
		 * So we just go onto the next blockgroup.
		 */
		if (++group == sbi->s_groups_count)
			group = 0;
	}
	err = -ENOSPC;
	goto out;

got:
A
Andreas Dilger 已提交
813 814 815
	/* We may have to initialize the block bitmap if it isn't already */
	if (EXT4_HAS_RO_COMPAT_FEATURE(sb, EXT4_FEATURE_RO_COMPAT_GDT_CSUM) &&
	    gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
A
Aneesh Kumar K.V 已提交
816
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
817

A
Aneesh Kumar K.V 已提交
818 819 820
		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 已提交
821
		if (err) {
A
Aneesh Kumar K.V 已提交
822
			brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
823 824 825 826 827 828 829 830
			goto fail;
		}

		free = 0;
		spin_lock(sb_bgl_lock(sbi, group));
		/* recheck and clear flag under lock if we still need to */
		if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
			free = ext4_free_blocks_after_init(sb, group, gdp);
A
Aneesh Kumar K.V 已提交
831
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
832
			ext4_free_blks_set(sb, gdp, free);
833 834
			gdp->bg_checksum = ext4_group_desc_csum(sbi, group,
								gdp);
A
Andreas Dilger 已提交
835 836 837 838 839
		}
		spin_unlock(sb_bgl_lock(sbi, group));

		/* Don't need to dirty bitmap block if we didn't change it */
		if (free) {
A
Aneesh Kumar K.V 已提交
840
			BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
841
			err = ext4_handle_dirty_metadata(handle,
A
Aneesh Kumar K.V 已提交
842
							NULL, block_bitmap_bh);
A
Andreas Dilger 已提交
843 844
		}

A
Aneesh Kumar K.V 已提交
845
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
846 847 848
		if (err)
			goto fail;
	}
A
Aneesh Kumar K.V 已提交
849 850
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
851 852
	if (err)
		goto fail;
853 854 855 856 857 858

	percpu_counter_dec(&sbi->s_freeinodes_counter);
	if (S_ISDIR(mode))
		percpu_counter_inc(&sbi->s_dirs_counter);
	sb->s_dirt = 1;

859 860 861 862 863 864 865
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
		spin_lock(sb_bgl_lock(sbi, flex_group));
		sbi->s_flex_groups[flex_group].free_inodes--;
		spin_unlock(sb_bgl_lock(sbi, flex_group));
	}

866
	inode->i_uid = current_fsuid();
867
	if (test_opt(sb, GRPID))
868 869 870 871 872 873
		inode->i_gid = dir->i_gid;
	else if (dir->i_mode & S_ISGID) {
		inode->i_gid = dir->i_gid;
		if (S_ISDIR(mode))
			mode |= S_ISGID;
	} else
874
		inode->i_gid = current_fsgid();
875 876
	inode->i_mode = mode;

A
Andreas Dilger 已提交
877
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
878 879
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
880 881
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
882 883 884 885 886

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

887
	/*
888 889 890
	 * Don't inherit extent flag from directory, amongst others. We set
	 * extent flag on newly created directory and file only if -o extent
	 * mount option is specified
891
	 */
892 893
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
894 895 896 897
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;

898
	ext4_set_inode_flags(inode);
899
	if (IS_DIRSYNC(inode))
900
		ext4_handle_sync(handle);
A
Al Viro 已提交
901 902 903 904
	if (insert_inode_locked(inode) < 0) {
		err = -EINVAL;
		goto fail_drop;
	}
905 906 907 908
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

909
	ei->i_state = EXT4_STATE_NEW;
K
Kalpak Shah 已提交
910 911

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
912 913

	ret = inode;
914
	if (vfs_dq_alloc_inode(inode)) {
915 916 917 918
		err = -EDQUOT;
		goto fail_drop;
	}

919
	err = ext4_init_acl(handle, inode, dir);
920 921 922
	if (err)
		goto fail_free_drop;

923
	err = ext4_init_security(handle, inode, dir);
924 925 926
	if (err)
		goto fail_free_drop;

927
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
928
		/* set extent flag only for directory, file and normal symlink*/
929
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
930 931 932
			EXT4_I(inode)->i_flags |= EXT4_EXTENTS_FL;
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
933
	}
934

935 936 937 938 939 940
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

941
	ext4_debug("allocating inode %lu\n", inode->i_ino);
942 943
	trace_mark(ext4_allocate_inode, "dev %s ino %lu dir %lu mode %d",
		   sb->s_id, inode->i_ino, dir->i_ino, mode);
944 945
	goto really_out;
fail:
946
	ext4_std_error(sb, err);
947 948 949 950
out:
	iput(inode);
	ret = ERR_PTR(err);
really_out:
A
Aneesh Kumar K.V 已提交
951
	brelse(inode_bitmap_bh);
952 953 954
	return ret;

fail_free_drop:
955
	vfs_dq_free_inode(inode);
956 957

fail_drop:
958
	vfs_dq_drop(inode);
959 960
	inode->i_flags |= S_NOQUOTA;
	inode->i_nlink = 0;
A
Al Viro 已提交
961
	unlock_new_inode(inode);
962
	iput(inode);
A
Aneesh Kumar K.V 已提交
963
	brelse(inode_bitmap_bh);
964 965 966 967
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
968
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
969
{
970
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
971
	ext4_group_t block_group;
972
	int bit;
973
	struct buffer_head *bitmap_bh;
974
	struct inode *inode = NULL;
975
	long err = -EIO;
976 977 978

	/* Error cases - e2fsck has already cleaned up for us */
	if (ino > max_ino) {
979
		ext4_warning(sb, __func__,
980
			     "bad orphan ino %lu!  e2fsck was run?", ino);
981
		goto error;
982 983
	}

984 985
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
986
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
987
	if (!bitmap_bh) {
988
		ext4_warning(sb, __func__,
989
			     "inode bitmap error for orphan %lu", ino);
990
		goto error;
991 992 993 994 995 996
	}

	/* 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.
	 */
997 998 999 1000 1001 1002 1003
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1004 1005 1006 1007 1008 1009 1010 1011
	/*
	 * 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;

1012 1013 1014 1015 1016 1017 1018 1019 1020
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1021
	ext4_warning(sb, __func__,
1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032
		     "bad orphan inode %lu!  e2fsck was run?", ino);
	printk(KERN_NOTICE "ext4_test_bit(bit=%d, block=%llu) = %d\n",
	       bit, (unsigned long long)bitmap_bh->b_blocknr,
	       ext4_test_bit(bit, bitmap_bh->b_data));
	printk(KERN_NOTICE "inode=%p\n", inode);
	if (inode) {
		printk(KERN_NOTICE "is_bad_inode(inode)=%d\n",
		       is_bad_inode(inode));
		printk(KERN_NOTICE "NEXT_ORPHAN(inode)=%u\n",
		       NEXT_ORPHAN(inode));
		printk(KERN_NOTICE "max_ino=%lu\n", max_ino);
1033
		printk(KERN_NOTICE "i_nlink=%u\n", inode->i_nlink);
1034
		/* Avoid freeing blocks if we got a bad deleted inode */
1035
		if (inode->i_nlink == 0)
1036 1037 1038 1039
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1040 1041
error:
	return ERR_PTR(err);
1042 1043
}

1044
unsigned long ext4_count_free_inodes(struct super_block *sb)
1045 1046
{
	unsigned long desc_count;
1047
	struct ext4_group_desc *gdp;
1048
	ext4_group_t i;
1049 1050
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1051 1052 1053
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1054
	es = EXT4_SB(sb)->s_es;
1055 1056 1057
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1058
	for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
1059
		gdp = ext4_get_group_desc(sb, i, NULL);
1060 1061
		if (!gdp)
			continue;
1062
		desc_count += ext4_free_inodes_count(sb, gdp);
1063
		brelse(bitmap_bh);
1064
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1065 1066 1067
		if (!bitmap_bh)
			continue;

1068
		x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1069
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1070
			i, ext4_free_inodes_count(sb, gdp), x);
1071 1072 1073
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1074 1075 1076
	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);
1077 1078 1079
	return desc_count;
#else
	desc_count = 0;
1080
	for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
1081
		gdp = ext4_get_group_desc(sb, i, NULL);
1082 1083
		if (!gdp)
			continue;
1084
		desc_count += ext4_free_inodes_count(sb, gdp);
1085 1086 1087 1088 1089 1090 1091
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1092
unsigned long ext4_count_dirs(struct super_block * sb)
1093 1094
{
	unsigned long count = 0;
1095
	ext4_group_t i;
1096

1097
	for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
1098
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1099 1100
		if (!gdp)
			continue;
1101
		count += ext4_used_dirs_count(sb, gdp);
1102 1103 1104
	}
	return count;
}