ialloc.c 34.0 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
/*
 * 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 */
68 69
unsigned ext4_init_inode_bitmap(struct super_block *sb, struct buffer_head *bh,
				ext4_group_t block_group,
A
Andreas Dilger 已提交
70 71 72 73 74 75 76 77 78
				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)) {
79
		ext4_error(sb, __func__, "Checksum bad for group %u",
A
Andreas Dilger 已提交
80
			   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
	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 111 112 113 114 115
		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 - "
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
	ext4_lock_group(sb, block_group);
A
Andreas Dilger 已提交
129
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
130
		ext4_init_inode_bitmap(sb, bh, block_group, desc);
131
		set_bitmap_uptodate(bh);
132
		set_buffer_uptodate(bh);
133
		ext4_unlock_group(sb, block_group);
A
Aneesh Kumar K.V 已提交
134
		unlock_buffer(bh);
135
		return bh;
A
Andreas Dilger 已提交
136
	}
137
	ext4_unlock_group(sb, block_group);
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	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);
154 155 156
	if (bh_submit_read(bh) < 0) {
		put_bh(bh);
		ext4_error(sb, __func__,
157
			    "Cannot read inode bitmap - "
158
			    "block_group = %u, inode_bitmap = %llu",
159 160 161
			    block_group, bitmap_blk);
		return NULL;
	}
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
	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.
 */
181
void ext4_free_inode(handle_t *handle, struct inode *inode)
182
{
183
	struct super_block *sb = inode->i_sb;
184 185 186 187
	int is_directory;
	unsigned long ino;
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *bh2;
188
	ext4_group_t block_group;
189
	unsigned long bit;
190 191
	struct ext4_group_desc *gdp;
	struct ext4_super_block *es;
192
	struct ext4_sb_info *sbi;
193
	int fatal = 0, err, count, cleared;
194 195

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

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

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

	is_directory = S_ISDIR(inode->i_mode);

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

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

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

	/* Ok, now we can actually update the inode bitmaps.. */
248 249
	cleared = ext4_clear_bit_atomic(ext4_group_lock_ptr(sb, block_group),
					bit, bitmap_bh->b_data);
250
	if (!cleared)
251 252
		ext4_error(sb, "ext4_free_inode",
			   "bit already cleared for inode %lu", ino);
253
	else {
254
		gdp = ext4_get_group_desc(sb, block_group, &bh2);
255 256

		BUFFER_TRACE(bh2, "get_write_access");
257
		fatal = ext4_journal_get_write_access(handle, bh2);
258 259 260
		if (fatal) goto error_return;

		if (gdp) {
261
			ext4_lock_group(sb, block_group);
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);
267 268 269 270 271 272 273
				if (sbi->s_log_groups_per_flex) {
					ext4_group_t f;

					f = ext4_flex_group(sbi, block_group);
					atomic_dec(&sbi->s_flex_groups[f].free_inodes);
				}

274
			}
A
Andreas Dilger 已提交
275 276
			gdp->bg_checksum = ext4_group_desc_csum(sbi,
							block_group, gdp);
277
			ext4_unlock_group(sb, block_group);
278 279 280 281
			percpu_counter_inc(&sbi->s_freeinodes_counter);
			if (is_directory)
				percpu_counter_dec(&sbi->s_dirs_counter);

282
			if (sbi->s_log_groups_per_flex) {
283 284 285 286
				ext4_group_t f;

				f = ext4_flex_group(sbi, block_group);
				atomic_inc(&sbi->s_flex_groups[f].free_inodes);
287
			}
288
		}
289 290
		BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
		err = ext4_handle_dirty_metadata(handle, NULL, bh2);
291 292
		if (!fatal) fatal = err;
	}
293 294
	BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
295 296 297 298 299
	if (!fatal)
		fatal = err;
	sb->s_dirt = 1;
error_return:
	brelse(bitmap_bh);
300
	ext4_std_error(sb, fatal);
301 302 303 304 305 306 307 308 309 310 311 312
}

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

322
	freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
323 324 325
	avefreei = freei / ngroups;

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

342 343 344 345 346 347 348 349 350 351
#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);
352
	ext4_group_t ngroups = ext4_get_groups_count(sb);
353 354 355 356 357 358 359 360
	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;

361
	n_fbg_groups = (ngroups + flex_size - 1) >>
362 363 364
		sbi->s_log_groups_per_flex;

find_close_to_parent:
365
	flexbg_free_blocks = atomic_read(&flex_group[best_flex].free_blocks);
366
	flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;
367
	if (atomic_read(&flex_group[best_flex].free_inodes) &&
368 369 370 371 372 373 374 375 376 377 378 379
	    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;

380
		flexbg_free_blocks = atomic_read(&flex_group[i].free_blocks);
381 382 383
		flex_freeb_ratio = flexbg_free_blocks * 100 / blocks_per_flex;

		if (flex_freeb_ratio > free_block_ratio &&
384
		    (atomic_read(&flex_group[i].free_inodes))) {
385 386 387 388
			best_flex = i;
			goto found_flexbg;
		}

389 390 391 392
		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)))
393 394 395
			best_flex = i;
	}

396 397
	if (!atomic_read(&flex_group[best_flex].free_inodes) ||
	    !atomic_read(&flex_group[best_flex].free_blocks))
398 399 400 401 402
		return -1;

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

	return -1;
out:
	return 0;
}

415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
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.
 */
void get_orlov_stats(struct super_block *sb, ext4_group_t g,
		       int flex_size, struct orlov_stats *stats)
{
	struct ext4_group_desc *desc;
430
	struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
431

432 433 434 435 436 437
	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;
	}
438

439 440 441 442 443 444 445 446 447
	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;
448 449 450
	}
}

451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
/*
 * 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
466
 * Parent's group is preferred, if it doesn't satisfy these
467 468 469 470 471
 * 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).
 */

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

491
	ngroups = real_ngroups;
492
	if (flex_size > 1) {
493
		ngroups = (real_ngroups + flex_size - 1) >>
494 495 496
			sbi->s_log_groups_per_flex;
		parent_group >>= sbi->s_log_groups_per_flex;
	}
497 498 499 500

	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
	avefreei = freei / ngroups;
	freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
501
	avefreeb = freeb;
A
Andrew Morton 已提交
502
	do_div(avefreeb, ngroups);
503 504
	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);

505 506 507
	if (S_ISDIR(mode) &&
	    ((parent == sb->s_root->d_inode) ||
	     (EXT4_I(parent)->i_flags & EXT4_TOPDIR_FL))) {
508
		int best_ndir = inodes_per_group;
509
		int ret = -1;
510

511 512 513 514 515 516 517
		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));
518
		parent_group = (unsigned)grp % ngroups;
519
		for (i = 0; i < ngroups; i++) {
520 521 522
			g = (parent_group + i) % ngroups;
			get_orlov_stats(sb, g, flex_size, &stats);
			if (!stats.free_inodes)
523
				continue;
524
			if (stats.used_dirs >= best_ndir)
525
				continue;
526
			if (stats.free_inodes < avefreei)
527
				continue;
528
			if (stats.free_blocks < avefreeb)
529
				continue;
530
			grp = g;
531
			ret = 0;
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
			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++) {
551
			if (grp+i >= real_ngroups)
552 553 554 555 556 557
				break;
			desc = ext4_get_group_desc(sb, grp+i, NULL);
			if (desc && ext4_free_inodes_count(sb, desc)) {
				*group = grp+i;
				return 0;
			}
558 559 560 561 562
		}
		goto fallback;
	}

	max_dirs = ndirs / ngroups + inodes_per_group / 16;
563 564 565 566 567 568 569 570 571 572 573 574 575 576
	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;
	}
577 578

	for (i = 0; i < ngroups; i++) {
579 580 581
		grp = (parent_group + i) % ngroups;
		get_orlov_stats(sb, grp, flex_size, &stats);
		if (stats.used_dirs >= max_dirs)
582
			continue;
583
		if (stats.free_inodes < min_inodes)
584
			continue;
585
		if (stats.free_blocks < min_blocks)
586
			continue;
587
		goto found_flex_bg;
588 589 590
	}

fallback:
591
	ngroups = real_ngroups;
592
	avefreei = freei / ngroups;
593
fallback_retry:
594
	parent_group = EXT4_I(parent)->i_block_group;
595
	for (i = 0; i < ngroups; i++) {
596 597
		grp = (parent_group + i) % ngroups;
		desc = ext4_get_group_desc(sb, grp, NULL);
598
		if (desc && ext4_free_inodes_count(sb, desc) &&
599 600
		    ext4_free_inodes_count(sb, desc) >= avefreei) {
			*group = grp;
601
			return 0;
602
		}
603 604 605 606 607 608 609 610
	}

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

	return -1;
}

617
static int find_group_other(struct super_block *sb, struct inode *parent,
618
			    ext4_group_t *group, int mode)
619
{
620
	ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
621
	ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
622
	struct ext4_group_desc *desc;
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
	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;
660
		return find_group_orlov(sb, parent, group, mode, 0);
661
	}
662 663 664 665

	/*
	 * Try to place the inode in its parent directory
	 */
666 667
	*group = parent_group;
	desc = ext4_get_group_desc(sb, *group, NULL);
668 669
	if (desc && ext4_free_inodes_count(sb, desc) &&
			ext4_free_blks_count(sb, desc))
670
		return 0;
671 672 673 674 675 676 677 678 679 680

	/*
	 * 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.
	 */
681
	*group = (*group + parent->i_ino) % ngroups;
682 683 684 685 686 687

	/*
	 * Use a quadratic hash to find a group with a free inode and some free
	 * blocks.
	 */
	for (i = 1; i < ngroups; i <<= 1) {
688 689 690 691
		*group += i;
		if (*group >= ngroups)
			*group -= ngroups;
		desc = ext4_get_group_desc(sb, *group, NULL);
692 693
		if (desc && ext4_free_inodes_count(sb, desc) &&
				ext4_free_blks_count(sb, desc))
694
			return 0;
695 696 697 698 699 700
	}

	/*
	 * That failed: try linear search for a free inode, even if that group
	 * has no free blocks.
	 */
701
	*group = parent_group;
702
	for (i = 0; i < ngroups; i++) {
703 704 705
		if (++*group >= ngroups)
			*group = 0;
		desc = ext4_get_group_desc(sb, *group, NULL);
706
		if (desc && ext4_free_inodes_count(sb, desc))
707
			return 0;
708 709 710 711 712
	}

	return -1;
}

713 714
/*
 * claim the inode from the inode bitmap. If the group
715
 * is uninit we need to take the groups's ext4_group_lock
716 717
 * and clear the uninit flag. The inode bitmap update
 * and group desc uninit flag clear should be done
718
 * after holding ext4_group_lock so that ext4_read_inode_bitmap
719 720 721 722 723 724 725 726 727 728
 * 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);

729
	ext4_lock_group(sb, group);
730 731 732 733 734 735 736 737
	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)) {
738
		ext4_unlock_group(sb, group);
739 740 741 742 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
		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);
779 780 781 782 783
		if (sbi->s_log_groups_per_flex) {
			ext4_group_t f = ext4_flex_group(sbi, group);

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

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

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

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

833 834 835
	if (!goal)
		goal = sbi->s_inode_goal;

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

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

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

865
got_group:
866
	EXT4_I(dir)->i_last_alloc_group = group;
867
	err = -ENOSPC;
868
	if (ret2 == -1)
869 870
		goto out;

871
	for (i = 0; i < ngroups; i++, ino = 0) {
872 873
		err = -EIO;

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

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

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

888
		if (ino < EXT4_INODES_PER_GROUP(sb)) {
889

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

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

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

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

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

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

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

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

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

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

988
	inode->i_uid = current_fsuid();
989
	if (test_opt(sb, GRPID))
990 991 992 993 994 995
		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
996
		inode->i_gid = current_fsgid();
997 998
	inode->i_mode = mode;

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

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

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

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

1032 1033
	ei->i_state_flags = 0;
	ext4_set_inode_state(inode, EXT4_STATE_NEW);
K
Kalpak Shah 已提交
1034 1035

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

	ret = inode;
1038
	if (vfs_dq_alloc_inode(inode)) {
1039 1040 1041 1042
		err = -EDQUOT;
		goto fail_drop;
	}

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

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

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

1059 1060 1061 1062 1063 1064
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

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

fail_free_drop:
1078
	vfs_dq_free_inode(inode);
1079 1080

fail_drop:
1081
	vfs_dq_drop(inode);
1082 1083
	inode->i_flags |= S_NOQUOTA;
	inode->i_nlink = 0;
A
Al Viro 已提交
1084
	unlock_new_inode(inode);
1085
	iput(inode);
A
Aneesh Kumar K.V 已提交
1086
	brelse(inode_bitmap_bh);
1087 1088 1089 1090
	return ERR_PTR(err);
}

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

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

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

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

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

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

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

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

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

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

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

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

1220
	for (i = 0; i < ngroups; i++) {
1221
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1222 1223
		if (!gdp)
			continue;
1224
		count += ext4_used_dirs_count(sb, gdp);
1225 1226 1227
	}
	return count;
}