ialloc.c 37.2 KB
Newer Older
1
/*
2
 *  linux/fs/ext4/ialloc.c
3 4 5 6 7 8 9 10 11 12 13 14 15 16
 *
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *
 *  BSD ufs-inspired inode and directory allocation by
 *  Stephen Tweedie (sct@redhat.com), 1993
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 */

#include <linux/time.h>
#include <linux/fs.h>
17
#include <linux/jbd2.h>
18 19 20 21 22 23
#include <linux/stat.h>
#include <linux/string.h>
#include <linux/quotaops.h>
#include <linux/buffer_head.h>
#include <linux/random.h>
#include <linux/bitops.h>
24
#include <linux/blkdev.h>
25
#include <asm/byteorder.h>
26

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

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

34 35 36 37 38 39 40 41 42 43 44 45 46 47
/*
 * ialloc.c contains the inodes allocation and deallocation routines
 */

/*
 * The free inodes are managed by bitmaps.  A file system contains several
 * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
 * block for inodes, N blocks for the inode table and data blocks.
 *
 * The file system contains group descriptors which are located after the
 * super block.  Each descriptor contains the number of the bitmap block and
 * the free blocks count in the block.
 */

A
Andreas Dilger 已提交
48 49 50 51 52
/*
 * To avoid calling the atomic setbit hundreds or thousands of times, we only
 * need to use it within a single byte (to ensure we get endianness right).
 * We can use memset for the rest of the bitmap as there are no other users.
 */
53
void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
A
Andreas Dilger 已提交
54 55 56 57 58 59 60 61 62 63 64 65 66 67
{
	int i;

	if (start_bit >= end_bit)
		return;

	ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
	for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
		ext4_set_bit(i, bitmap);
	if (i < end_bit)
		memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
}

/* Initializes an uninitialized inode bitmap */
68 69 70 71
static unsigned ext4_init_inode_bitmap(struct super_block *sb,
				       struct buffer_head *bh,
				       ext4_group_t block_group,
				       struct ext4_group_desc *gdp)
A
Andreas Dilger 已提交
72 73 74 75 76 77 78 79
{
	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)) {
80
		ext4_error(sb, "Checksum bad for group %u", block_group);
81 82 83
		ext4_free_blks_set(sb, gdp, 0);
		ext4_free_inodes_set(sb, gdp, 0);
		ext4_itable_unused_set(sb, gdp, 0);
A
Andreas Dilger 已提交
84 85 86 87 88
		memset(bh->b_data, 0xff, sb->s_blocksize);
		return 0;
	}

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

	return EXT4_INODES_PER_GROUP(sb);
}
94 95 96 97 98 99 100 101

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

108
	desc = ext4_get_group_desc(sb, block_group, NULL);
109
	if (!desc)
110
		return NULL;
111

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

123
	lock_buffer(bh);
124 125 126 127
	if (bitmap_uptodate(bh)) {
		unlock_buffer(bh);
		return bh;
	}
128

129
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
130
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
131
		ext4_init_inode_bitmap(sb, bh, block_group, desc);
132
		set_bitmap_uptodate(bh);
133
		set_buffer_uptodate(bh);
134
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
135
		unlock_buffer(bh);
136
		return bh;
A
Andreas Dilger 已提交
137
	}
138
	ext4_unlock_group(sb, block_group);
139

140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
	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.
	 */
155
	trace_ext4_load_inode_bitmap(sb, block_group);
156
	set_bitmap_uptodate(bh);
157 158
	if (bh_submit_read(bh) < 0) {
		put_bh(bh);
159
		ext4_error(sb, "Cannot read inode bitmap - "
160
			    "block_group = %u, inode_bitmap = %llu",
161 162 163
			    block_group, bitmap_blk);
		return NULL;
	}
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
	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.
 */
183
void ext4_free_inode(handle_t *handle, struct inode *inode)
184
{
185
	struct super_block *sb = inode->i_sb;
186 187 188 189
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
190
	ext4_group_t block_group;
191
	unsigned long bit;
192 193
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
194
	struct ext4_sb_info *sbi;
195
	int fatal = 0, err, count, cleared;
196 197

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

	ino = inode->i_ino;
215
	ext4_debug("freeing inode %lu\n", ino);
216
	trace_ext4_free_inode(inode);
217 218 219 220 221

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

	is_directory = S_ISDIR(inode->i_mode);

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

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

	BUFFER_TRACE(bitmap_bh, "get_write_access");
244
	fatal = ext4_journal_get_write_access(handle, bitmap_bh);
245 246 247
	if (fatal)
		goto error_return;

248 249 250
	fatal = -ESRCH;
	gdp = ext4_get_group_desc(sb, block_group, &bh2);
	if (gdp) {
251
		BUFFER_TRACE(bh2, "get_write_access");
252
		fatal = ext4_journal_get_write_access(handle, bh2);
253 254 255 256 257 258 259
	}
	ext4_lock_group(sb, block_group);
	cleared = ext4_clear_bit(bit, bitmap_bh->b_data);
	if (fatal || !cleared) {
		ext4_unlock_group(sb, block_group);
		goto out;
	}
260

261 262 263 264 265 266
	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);
267
	}
268 269
	gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
	ext4_unlock_group(sb, block_group);
270

271 272 273
	percpu_counter_inc(&sbi->s_freeinodes_counter);
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t f = ext4_flex_group(sbi, block_group);
274

275 276 277
		atomic_inc(&sbi->s_flex_groups[f].free_inodes);
		if (is_directory)
			atomic_dec(&sbi->s_flex_groups[f].used_dirs);
278
	}
279 280 281 282 283 284 285 286
	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;
T
Theodore Ts'o 已提交
287
		ext4_mark_super_dirty(sb);
288 289 290
	} else
		ext4_error(sb, "bit already cleared for inode %lu", ino);

291 292
error_return:
	brelse(bitmap_bh);
293
	ext4_std_error(sb, fatal);
294 295 296 297 298 299 300 301 302 303 304 305
}

/*
 * 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.
 */
306 307
static int find_group_dir(struct super_block *sb, struct inode *parent,
				ext4_group_t *best_group)
308
{
309
	ext4_group_t ngroups = ext4_get_groups_count(sb);
310
	unsigned int freei, avefreei;
311
	struct ext4_group_desc *desc, *best_desc = NULL;
312 313
	ext4_group_t group;
	int ret = -1;
314

315
	freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
316 317 318
	avefreei = freei / ngroups;

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

335 336 337 338 339 340 341 342 343 344
#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 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);
345
	ext4_group_t ngroups = ext4_get_groups_count(sb);
346 347 348 349 350 351 352 353
	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;

354
	n_fbg_groups = (ngroups + flex_size - 1) >>
355 356 357
		sbi->s_log_groups_per_flex;

find_close_to_parent:
358
	flexbg_free_blocks = atomic_read(&flex_group[best_flex].free_blocks);
359
	flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;
360
	if (atomic_read(&flex_group[best_flex].free_inodes) &&
361 362 363 364 365 366 367 368 369 370 371 372
	    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;

373
		flexbg_free_blocks = atomic_read(&flex_group[i].free_blocks);
374 375 376
		flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;

		if (flex_freeb_ratio > free_block_ratio &&
377
		    (atomic_read(&flex_group[i].free_inodes))) {
378 379 380 381
			best_flex = i;
			goto found_flexbg;
		}

382 383 384 385
		if ((atomic_read(&flex_group[best_flex].free_inodes) == 0) ||
		    ((atomic_read(&flex_group[i].free_blocks) >
		      atomic_read(&flex_group[best_flex].free_blocks)) &&
		     atomic_read(&flex_group[i].free_inodes)))
386 387 388
			best_flex = i;
	}

389 390
	if (!atomic_read(&flex_group[best_flex].free_inodes) ||
	    !atomic_read(&flex_group[best_flex].free_blocks))
391 392 393 394 395
		return -1;

found_flexbg:
	for (i = best_flex * flex_size; i < ngroups &&
		     i < (best_flex + 1) * flex_size; i++) {
396
		desc = ext4_get_group_desc(sb, i, NULL);
397
		if (ext4_free_inodes_count(sb, desc)) {
398 399 400 401 402 403 404 405 406 407
			*best_group = i;
			goto out;
		}
	}

	return -1;
out:
	return 0;
}

408 409 410 411 412 413 414 415 416 417 418
struct orlov_stats {
	__u32 free_inodes;
	__u32 free_blocks;
	__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.
 */
419 420
static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
			    int flex_size, struct orlov_stats *stats)
421 422
{
	struct ext4_group_desc *desc;
423
	struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
424

425 426 427 428 429 430
	if (flex_size > 1) {
		stats->free_inodes = atomic_read(&flex_group[g].free_inodes);
		stats->free_blocks = atomic_read(&flex_group[g].free_blocks);
		stats->used_dirs = atomic_read(&flex_group[g].used_dirs);
		return;
	}
431

432 433 434 435 436 437 438 439 440
	desc = ext4_get_group_desc(sb, g, NULL);
	if (desc) {
		stats->free_inodes = ext4_free_inodes_count(sb, desc);
		stats->free_blocks = ext4_free_blks_count(sb, desc);
		stats->used_dirs = ext4_used_dirs_count(sb, desc);
	} else {
		stats->free_inodes = 0;
		stats->free_blocks = 0;
		stats->used_dirs = 0;
441 442 443
	}
}

444 445 446 447 448 449 450 451 452 453 454 455 456 457 458
/*
 * 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
459
 * Parent's group is preferred, if it doesn't satisfy these
460 461 462 463 464
 * 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).
 */

465
static int find_group_orlov(struct super_block *sb, struct inode *parent,
466 467
			    ext4_group_t *group, int mode,
			    const struct qstr *qstr)
468
{
469
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
470
	struct ext4_sb_info *sbi = EXT4_SB(sb);
471
	ext4_group_t real_ngroups = ext4_get_groups_count(sb);
472
	int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
473
	unsigned int freei, avefreei;
474
	ext4_fsblk_t freeb, avefreeb;
475
	unsigned int ndirs;
476
	int max_dirs, min_inodes;
477
	ext4_grpblk_t min_blocks;
478
	ext4_group_t i, grp, g, ngroups;
479
	struct ext4_group_desc *desc;
480 481
	struct orlov_stats stats;
	int flex_size = ext4_flex_bg_size(sbi);
482
	struct dx_hash_info hinfo;
483

484
	ngroups = real_ngroups;
485
	if (flex_size > 1) {
486
		ngroups = (real_ngroups + flex_size - 1) >>
487 488 489
			sbi->s_log_groups_per_flex;
		parent_group >>= sbi->s_log_groups_per_flex;
	}
490 491 492 493

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
	freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
494
	avefreeb = freeb;
A
Andrew Morton 已提交
495
	do_div(avefreeb, ngroups);
496 497
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

498 499
	if (S_ISDIR(mode) &&
	    ((parent == sb->s_root->d_inode) ||
500
	     (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
501
		int best_ndir = inodes_per_group;
502
		int ret = -1;
503

504 505 506 507 508 509 510
		if (qstr) {
			hinfo.hash_version = DX_HASH_HALF_MD4;
			hinfo.seed = sbi->s_hash_seed;
			ext4fs_dirhash(qstr->name, qstr->len, &hinfo);
			grp = hinfo.hash;
		} else
			get_random_bytes(&grp, sizeof(grp));
511
		parent_group = (unsigned)grp % ngroups;
512
		for (i = 0; i < ngroups; i++) {
513 514 515
			g = (parent_group + i) % ngroups;
			get_orlov_stats(sb, g, flex_size, &stats);
			if (!stats.free_inodes)
516
				continue;
517
			if (stats.used_dirs >= best_ndir)
518
				continue;
519
			if (stats.free_inodes < avefreei)
520
				continue;
521
			if (stats.free_blocks < avefreeb)
522
				continue;
523
			grp = g;
524
			ret = 0;
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543
			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++) {
544
			if (grp+i >= real_ngroups)
545 546 547 548 549 550
				break;
			desc = ext4_get_group_desc(sb, grp+i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = grp+i;
				return 0;
			}
551 552 553 554 555
		}
		goto fallback;
	}

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
556 557 558 559 560 561 562 563 564 565 566 567 568 569
	min_inodes = avefreei - inodes_per_group*flex_size / 4;
	if (min_inodes < 1)
		min_inodes = 1;
	min_blocks = avefreeb - EXT4_BLOCKS_PER_GROUP(sb)*flex_size / 4;

	/*
	 * 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;
	}
570 571

	for (i = 0; i < ngroups; i++) {
572 573 574
		grp = (parent_group + i) % ngroups;
		get_orlov_stats(sb, grp, flex_size, &stats);
		if (stats.used_dirs >= max_dirs)
575
			continue;
576
		if (stats.free_inodes < min_inodes)
577
			continue;
578
		if (stats.free_blocks < min_blocks)
579
			continue;
580
		goto found_flex_bg;
581 582 583
	}

fallback:
584
	ngroups = real_ngroups;
585
	avefreei = freei / ngroups;
586
fallback_retry:
587
	parent_group = EXT4_I(parent)->i_block_group;
588
	for (i = 0; i < ngroups; i++) {
589 590
		grp = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, grp, NULL);
591
		if (desc && ext4_free_inodes_count(sb, desc) &&
592 593
		    ext4_free_inodes_count(sb, desc) >= avefreei) {
			*group = grp;
594
			return 0;
595
		}
596 597 598 599 600 601 602 603
	}

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

	return -1;
}

610
static int find_group_other(struct super_block *sb, struct inode *parent,
611
			    ext4_group_t *group, int mode)
612
{
613
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
614
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
615
	struct ext4_group_desc *desc;
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
	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;
653
		return find_group_orlov(sb, parent, group, mode, NULL);
654
	}
655 656 657 658

	/*
	 * Try to place the inode in its parent directory
	 */
659 660
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
661 662
	if (desc && ext4_free_inodes_count(sb, desc) &&
			ext4_free_blks_count(sb, desc))
663
		return 0;
664 665 666 667 668 669 670 671 672 673

	/*
	 * 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.
	 */
674
	*group = (*group + parent->i_ino) % ngroups;
675 676 677 678 679 680

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
681 682 683 684
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
685 686
		if (desc && ext4_free_inodes_count(sb, desc) &&
				ext4_free_blks_count(sb, desc))
687
			return 0;
688 689 690 691 692 693
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
694
	*group = parent_group;
695
	for (i = 0; i < ngroups; i++) {
696 697 698
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
699
		if (desc && ext4_free_inodes_count(sb, desc))
700
			return 0;
701 702 703 704 705
	}

	return -1;
}

706 707
/*
 * claim the inode from the inode bitmap. If the group
708
 * is uninit we need to take the groups's ext4_group_lock
709 710
 * and clear the uninit flag. The inode bitmap update
 * and group desc uninit flag clear should be done
711
 * after holding ext4_group_lock so that ext4_read_inode_bitmap
712 713 714 715 716 717 718 719
 * 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);
720
	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
721 722
	struct ext4_group_desc *gdp = ext4_get_group_desc(sb, group, NULL);

723 724 725 726 727 728 729 730
	/*
	 * We have to be sure that new inode allocation does not race with
	 * inode table initialization, because otherwise we may end up
	 * allocating and writing new inode right before sb_issue_zeroout
	 * takes place and overwriting our new inode with zeroes. So we
	 * take alloc_sem to prevent it.
	 */
	down_read(&grp->alloc_sem);
731
	ext4_lock_group(sb, group);
732 733 734 735 736 737 738 739
	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)) {
740
		ext4_unlock_group(sb, group);
741
		up_read(&grp->alloc_sem);
742
		ext4_error(sb, "reserved inode or inode > inodes count - "
743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
			   "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);
781 782 783
		if (sbi->s_log_groups_per_flex) {
			ext4_group_t f = ext4_flex_group(sbi, group);

784
			atomic_inc(&sbi->s_flex_groups[f].used_dirs);
785
		}
786 787 788
	}
	gdp->bg_checksum = ext4_group_desc_csum(sbi, group, gdp);
err_ret:
789
	ext4_unlock_group(sb, group);
790
	up_read(&grp->alloc_sem);
791 792 793
	return retval;
}

794 795 796 797 798 799 800 801 802 803
/*
 * 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.
 */
804
struct inode *ext4_new_inode(handle_t *handle, struct inode *dir, int mode,
805
			     const struct qstr *qstr, __u32 goal)
806 807
{
	struct super_block *sb;
A
Aneesh Kumar K.V 已提交
808 809
	struct buffer_head *inode_bitmap_bh = NULL;
	struct buffer_head *group_desc_bh;
810
	ext4_group_t ngroups, group = 0;
811
	unsigned long ino = 0;
812 813
	struct inode *inode;
	struct ext4_group_desc *gdp = NULL;
814 815
	struct ext4_inode_info *ei;
	struct ext4_sb_info *sbi;
816
	int ret2, err = 0;
817
	struct inode *ret;
818 819
	ext4_group_t i;
	int free = 0;
820
	static int once = 1;
821
	ext4_group_t flex_group;
822 823 824 825 826 827

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

	sb = dir->i_sb;
828
	ngroups = ext4_get_groups_count(sb);
829
	trace_ext4_request_inode(dir, mode);
830 831 832
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
833 834
	ei = EXT4_I(inode);
	sbi = EXT4_SB(sb);
835

836 837 838
	if (!goal)
		goal = sbi->s_inode_goal;

839
	if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
840 841 842 843 844 845
		group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
		ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
		ret2 = 0;
		goto got_group;
	}

846
	if (sbi->s_log_groups_per_flex && test_opt(sb, OLDALLOC)) {
847
		ret2 = find_group_flex(sb, dir, &group);
848
		if (ret2 == -1) {
849
			ret2 = find_group_other(sb, dir, &group, mode);
850
			if (ret2 == 0 && once) {
851
				once = 0;
852 853 854
				printk(KERN_NOTICE "ext4: find_group_flex "
				       "failed, fallback succeeded dir %lu\n",
				       dir->i_ino);
855
			}
856
		}
857 858 859
		goto got_group;
	}

860
	if (S_ISDIR(mode)) {
861
		if (test_opt(sb, OLDALLOC))
862
			ret2 = find_group_dir(sb, dir, &group);
863
		else
864
			ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
865
	} else
866
		ret2 = find_group_other(sb, dir, &group, mode);
867

868
got_group:
869
	EXT4_I(dir)->i_last_alloc_group = group;
870
	err = -ENOSPC;
871
	if (ret2 == -1)
872 873
		goto out;

874
	for (i = 0; i < ngroups; i++, ino = 0) {
875 876
		err = -EIO;

A
Aneesh Kumar K.V 已提交
877
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
878 879 880
		if (!gdp)
			goto fail;

A
Aneesh Kumar K.V 已提交
881 882 883
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
		if (!inode_bitmap_bh)
884 885 886
			goto fail;

repeat_in_this_group:
887
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
888 889 890
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);

891
		if (ino < EXT4_INODES_PER_GROUP(sb)) {
892

A
Aneesh Kumar K.V 已提交
893 894 895
			BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
			err = ext4_journal_get_write_access(handle,
							    inode_bitmap_bh);
896 897 898
			if (err)
				goto fail;

899 900 901 902 903 904 905
			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)) {
906
				/* we won it */
A
Aneesh Kumar K.V 已提交
907
				BUFFER_TRACE(inode_bitmap_bh,
908 909
					"call ext4_handle_dirty_metadata");
				err = ext4_handle_dirty_metadata(handle,
910
								 NULL,
A
Aneesh Kumar K.V 已提交
911
							inode_bitmap_bh);
912 913
				if (err)
					goto fail;
914 915
				/* zero bit is inode number 1*/
				ino++;
916 917 918
				goto got;
			}
			/* we lost it */
A
Aneesh Kumar K.V 已提交
919
			ext4_handle_release_buffer(handle, inode_bitmap_bh);
920
			ext4_handle_release_buffer(handle, group_desc_bh);
921

922
			if (++ino < EXT4_INODES_PER_GROUP(sb))
923 924 925 926 927 928 929 930 931 932
				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.
		 */
933
		if (++group == ngroups)
934 935 936 937 938 939
			group = 0;
	}
	err = -ENOSPC;
	goto out;

got:
A
Andreas Dilger 已提交
940 941 942
	/* 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 已提交
943
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
944

A
Aneesh Kumar K.V 已提交
945 946 947
		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 已提交
948
		if (err) {
A
Aneesh Kumar K.V 已提交
949
			brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
950 951 952 953
			goto fail;
		}

		free = 0;
954
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
955 956 957
		/* 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 已提交
958
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
959
			ext4_free_blks_set(sb, gdp, free);
960 961
			gdp->bg_checksum = ext4_group_desc_csum(sbi, group,
								gdp);
A
Andreas Dilger 已提交
962
		}
963
		ext4_unlock_group(sb, group);
A
Andreas Dilger 已提交
964 965 966

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

A
Aneesh Kumar K.V 已提交
972
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
973 974 975
		if (err)
			goto fail;
	}
A
Aneesh Kumar K.V 已提交
976 977
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
978 979
	if (err)
		goto fail;
980 981 982 983

	percpu_counter_dec(&sbi->s_freeinodes_counter);
	if (S_ISDIR(mode))
		percpu_counter_inc(&sbi->s_dirs_counter);
T
Theodore Ts'o 已提交
984
	ext4_mark_super_dirty(sb);
985

986 987
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
988
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
989 990
	}

991 992 993
	if (test_opt(sb, GRPID)) {
		inode->i_mode = mode;
		inode->i_uid = current_fsuid();
994 995
		inode->i_gid = dir->i_gid;
	} else
996
		inode_init_owner(inode, dir, mode);
997

A
Andreas Dilger 已提交
998
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
999 1000
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
1001 1002
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
1003 1004 1005 1006 1007

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

1008
	/*
1009 1010 1011
	 * 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
1012
	 */
1013 1014
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
1015 1016 1017
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
1018
	ei->i_last_alloc_group = ~0;
1019

1020
	ext4_set_inode_flags(inode);
1021
	if (IS_DIRSYNC(inode))
1022
		ext4_handle_sync(handle);
A
Al Viro 已提交
1023 1024 1025 1026
	if (insert_inode_locked(inode) < 0) {
		err = -EINVAL;
		goto fail_drop;
	}
1027 1028 1029 1030
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

1031
	ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
1032
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
1033 1034

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
1035 1036

	ret = inode;
1037
	dquot_initialize(inode);
1038 1039
	err = dquot_alloc_inode(inode);
	if (err)
1040 1041
		goto fail_drop;

1042
	err = ext4_init_acl(handle, inode, dir);
1043 1044 1045
	if (err)
		goto fail_free_drop;

1046
	err = ext4_init_security(handle, inode, dir, qstr);
1047 1048 1049
	if (err)
		goto fail_free_drop;

1050
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
1051
		/* set extent flag only for directory, file and normal symlink*/
1052
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1053
			ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1054 1055
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1056
	}
1057

1058 1059 1060 1061 1062
	if (ext4_handle_valid(handle)) {
		ei->i_sync_tid = handle->h_transaction->t_tid;
		ei->i_datasync_tid = handle->h_transaction->t_tid;
	}

1063 1064 1065 1066 1067 1068
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1069
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1070
	trace_ext4_allocate_inode(inode, dir, mode);
1071 1072
	goto really_out;
fail:
1073
	ext4_std_error(sb, err);
1074 1075 1076 1077
out:
	iput(inode);
	ret = ERR_PTR(err);
really_out:
A
Aneesh Kumar K.V 已提交
1078
	brelse(inode_bitmap_bh);
1079 1080 1081
	return ret;

fail_free_drop:
1082
	dquot_free_inode(inode);
1083 1084

fail_drop:
1085
	dquot_drop(inode);
1086 1087
	inode->i_flags |= S_NOQUOTA;
	inode->i_nlink = 0;
A
Al Viro 已提交
1088
	unlock_new_inode(inode);
1089
	iput(inode);
A
Aneesh Kumar K.V 已提交
1090
	brelse(inode_bitmap_bh);
1091 1092 1093 1094
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1095
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1096
{
1097
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1098
	ext4_group_t block_group;
1099
	int bit;
1100
	struct buffer_head *bitmap_bh;
1101
	struct inode *inode = NULL;
1102
	long err = -EIO;
1103 1104 1105

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

1110 1111
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1112
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1113
	if (!bitmap_bh) {
1114
		ext4_warning(sb, "inode bitmap error for orphan %lu", ino);
1115
		goto error;
1116 1117 1118 1119 1120 1121
	}

	/* 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.
	 */
1122 1123 1124 1125 1126 1127 1128
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1129 1130 1131 1132 1133 1134 1135 1136
	/*
	 * 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;

1137 1138 1139 1140 1141 1142 1143 1144 1145
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1146
	ext4_warning(sb, "bad orphan inode %lu!  e2fsck was run?", ino);
1147 1148 1149 1150 1151 1152 1153 1154 1155 1156
	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);
1157
		printk(KERN_NOTICE "i_nlink=%u\n", inode->i_nlink);
1158
		/* Avoid freeing blocks if we got a bad deleted inode */
1159
		if (inode->i_nlink == 0)
1160 1161 1162 1163
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1164 1165
error:
	return ERR_PTR(err);
1166 1167
}

1168
unsigned long ext4_count_free_inodes(struct super_block *sb)
1169 1170
{
	unsigned long desc_count;
1171
	struct ext4_group_desc *gdp;
1172
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1173 1174
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1175 1176 1177
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1178
	es = EXT4_SB(sb)->s_es;
1179 1180 1181
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1182
	for (i = 0; i < ngroups; i++) {
1183
		gdp = ext4_get_group_desc(sb, i, NULL);
1184 1185
		if (!gdp)
			continue;
1186
		desc_count += ext4_free_inodes_count(sb, gdp);
1187
		brelse(bitmap_bh);
1188
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1189 1190 1191
		if (!bitmap_bh)
			continue;

1192
		x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1193
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1194
			(unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
1195 1196 1197
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1198 1199 1200
	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);
1201 1202 1203
	return desc_count;
#else
	desc_count = 0;
1204
	for (i = 0; i < ngroups; i++) {
1205
		gdp = ext4_get_group_desc(sb, i, NULL);
1206 1207
		if (!gdp)
			continue;
1208
		desc_count += ext4_free_inodes_count(sb, gdp);
1209 1210 1211 1212 1213 1214 1215
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1216
unsigned long ext4_count_dirs(struct super_block * sb)
1217 1218
{
	unsigned long count = 0;
1219
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1220

1221
	for (i = 0; i < ngroups; i++) {
1222
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1223 1224
		if (!gdp)
			continue;
1225
		count += ext4_used_dirs_count(sb, gdp);
1226 1227 1228
	}
	return count;
}
1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282

/*
 * 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
 * block ext4_claim_inode until we are finished.
 */
extern int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
				 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;

	handle = ext4_journal_start_sb(sb, 1);
	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);

1283 1284 1285 1286 1287 1288 1289
	if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
		ext4_error(sb, "Something is wrong with group %u\n"
			   "Used itable blocks: %d"
			   "itable unused count: %u\n",
			   group, used_blks,
			   ext4_itable_unused_count(sb, gdp));
		ret = 1;
1290
		goto err_out;
1291 1292
	}

1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311
	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);
1312
	ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1313 1314
	if (ret < 0)
		goto err_out;
1315 1316
	if (barrier)
		blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334

skip_zeroout:
	ext4_lock_group(sb, group);
	gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
	gdp->bg_checksum = ext4_group_desc_csum(sbi, group, gdp);
	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;
}