ialloc.c 33.7 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 802
struct inode *ext4_new_inode(handle_t *handle, struct inode *dir, int mode,
			     const struct qstr *qstr)
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
	if (sbi->s_log_groups_per_flex && test_opt(sb, OLDALLOC)) {
834
		ret2 = find_group_flex(sb, dir, &group);
835
		if (ret2 == -1) {
836
			ret2 = find_group_other(sb, dir, &group, mode);
837
			if (ret2 == 0 && once) {
838
				once = 0;
839 840 841
				printk(KERN_NOTICE "ext4: find_group_flex "
				       "failed, fallback succeeded dir %lu\n",
				       dir->i_ino);
842
			}
843
		}
844 845 846
		goto got_group;
	}

847
	if (S_ISDIR(mode)) {
848
		if (test_opt(sb, OLDALLOC))
849
			ret2 = find_group_dir(sb, dir, &group);
850
		else
851
			ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
852
	} else
853
		ret2 = find_group_other(sb, dir, &group, mode);
854

855
got_group:
856
	EXT4_I(dir)->i_last_alloc_group = group;
857
	err = -ENOSPC;
858
	if (ret2 == -1)
859 860
		goto out;

861
	for (i = 0; i < ngroups; i++) {
862 863
		err = -EIO;

A
Aneesh Kumar K.V 已提交
864
		gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
865 866 867
		if (!gdp)
			goto fail;

A
Aneesh Kumar K.V 已提交
868 869 870
		brelse(inode_bitmap_bh);
		inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
		if (!inode_bitmap_bh)
871 872 873 874 875
			goto fail;

		ino = 0;

repeat_in_this_group:
876
		ino = ext4_find_next_zero_bit((unsigned long *)
A
Aneesh Kumar K.V 已提交
877 878 879
					      inode_bitmap_bh->b_data,
					      EXT4_INODES_PER_GROUP(sb), ino);

880
		if (ino < EXT4_INODES_PER_GROUP(sb)) {
881

A
Aneesh Kumar K.V 已提交
882 883 884
			BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
			err = ext4_journal_get_write_access(handle,
							    inode_bitmap_bh);
885 886 887
			if (err)
				goto fail;

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

911
			if (++ino < EXT4_INODES_PER_GROUP(sb))
912 913 914 915 916 917 918 919 920 921
				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.
		 */
922
		if (++group == ngroups)
923 924 925 926 927 928
			group = 0;
	}
	err = -ENOSPC;
	goto out;

got:
A
Andreas Dilger 已提交
929 930 931
	/* 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 已提交
932
		struct buffer_head *block_bitmap_bh;
A
Andreas Dilger 已提交
933

A
Aneesh Kumar K.V 已提交
934 935 936
		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 已提交
937
		if (err) {
A
Aneesh Kumar K.V 已提交
938
			brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
939 940 941 942
			goto fail;
		}

		free = 0;
943
		ext4_lock_group(sb, group);
A
Andreas Dilger 已提交
944 945 946
		/* 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 已提交
947
			gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
948
			ext4_free_blks_set(sb, gdp, free);
949 950
			gdp->bg_checksum = ext4_group_desc_csum(sbi, group,
								gdp);
A
Andreas Dilger 已提交
951
		}
952
		ext4_unlock_group(sb, group);
A
Andreas Dilger 已提交
953 954 955

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

A
Aneesh Kumar K.V 已提交
961
		brelse(block_bitmap_bh);
A
Andreas Dilger 已提交
962 963 964
		if (err)
			goto fail;
	}
A
Aneesh Kumar K.V 已提交
965 966
	BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
967 968
	if (err)
		goto fail;
969 970 971 972 973 974

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

975 976
	if (sbi->s_log_groups_per_flex) {
		flex_group = ext4_flex_group(sbi, group);
977
		atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
978 979
	}

980
	inode->i_uid = current_fsuid();
981
	if (test_opt(sb, GRPID))
982 983 984 985 986 987
		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
988
		inode->i_gid = current_fsgid();
989 990
	inode->i_mode = mode;

A
Andreas Dilger 已提交
991
	inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
992 993
	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
K
Kalpak Shah 已提交
994 995
	inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
						       ext4_current_time(inode);
996 997 998 999 1000

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

1001
	/*
1002 1003 1004
	 * 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
1005
	 */
1006 1007
	ei->i_flags =
		ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
1008 1009 1010
	ei->i_file_acl = 0;
	ei->i_dtime = 0;
	ei->i_block_group = group;
1011
	ei->i_last_alloc_group = ~0;
1012

1013
	ext4_set_inode_flags(inode);
1014
	if (IS_DIRSYNC(inode))
1015
		ext4_handle_sync(handle);
A
Al Viro 已提交
1016 1017 1018 1019
	if (insert_inode_locked(inode) < 0) {
		err = -EINVAL;
		goto fail_drop;
	}
1020 1021 1022 1023
	spin_lock(&sbi->s_next_gen_lock);
	inode->i_generation = sbi->s_next_generation++;
	spin_unlock(&sbi->s_next_gen_lock);

1024
	ei->i_state = EXT4_STATE_NEW;
K
Kalpak Shah 已提交
1025 1026

	ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
1027 1028

	ret = inode;
1029
	if (vfs_dq_alloc_inode(inode)) {
1030 1031 1032 1033
		err = -EDQUOT;
		goto fail_drop;
	}

1034
	err = ext4_init_acl(handle, inode, dir);
1035 1036 1037
	if (err)
		goto fail_free_drop;

1038
	err = ext4_init_security(handle, inode, dir);
1039 1040 1041
	if (err)
		goto fail_free_drop;

1042
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
1043
		/* set extent flag only for directory, file and normal symlink*/
1044
		if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1045 1046 1047
			EXT4_I(inode)->i_flags |= EXT4_EXTENTS_FL;
			ext4_ext_tree_init(handle, inode);
		}
A
Alex Tomas 已提交
1048
	}
1049

1050 1051 1052 1053 1054 1055
	err = ext4_mark_inode_dirty(handle, inode);
	if (err) {
		ext4_std_error(sb, err);
		goto fail_free_drop;
	}

1056
	ext4_debug("allocating inode %lu\n", inode->i_ino);
1057
	trace_ext4_allocate_inode(inode, dir, mode);
1058 1059
	goto really_out;
fail:
1060
	ext4_std_error(sb, err);
1061 1062 1063 1064
out:
	iput(inode);
	ret = ERR_PTR(err);
really_out:
A
Aneesh Kumar K.V 已提交
1065
	brelse(inode_bitmap_bh);
1066 1067 1068
	return ret;

fail_free_drop:
1069
	vfs_dq_free_inode(inode);
1070 1071

fail_drop:
1072
	vfs_dq_drop(inode);
1073 1074
	inode->i_flags |= S_NOQUOTA;
	inode->i_nlink = 0;
A
Al Viro 已提交
1075
	unlock_new_inode(inode);
1076
	iput(inode);
A
Aneesh Kumar K.V 已提交
1077
	brelse(inode_bitmap_bh);
1078 1079 1080 1081
	return ERR_PTR(err);
}

/* Verify that we are loading a valid orphan from disk */
1082
struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1083
{
1084
	unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1085
	ext4_group_t block_group;
1086
	int bit;
1087
	struct buffer_head *bitmap_bh;
1088
	struct inode *inode = NULL;
1089
	long err = -EIO;
1090 1091 1092

	/* Error cases - e2fsck has already cleaned up for us */
	if (ino > max_ino) {
1093
		ext4_warning(sb, __func__,
1094
			     "bad orphan ino %lu!  e2fsck was run?", ino);
1095
		goto error;
1096 1097
	}

1098 1099
	block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
	bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1100
	bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1101
	if (!bitmap_bh) {
1102
		ext4_warning(sb, __func__,
1103
			     "inode bitmap error for orphan %lu", ino);
1104
		goto error;
1105 1106 1107 1108 1109 1110
	}

	/* 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.
	 */
1111 1112 1113 1114 1115 1116 1117
	if (!ext4_test_bit(bit, bitmap_bh->b_data))
		goto bad_orphan;

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

1118 1119 1120 1121 1122 1123 1124 1125
	/*
	 * 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;

1126 1127 1128 1129 1130 1131 1132 1133 1134
	if (NEXT_ORPHAN(inode) > max_ino)
		goto bad_orphan;
	brelse(bitmap_bh);
	return inode;

iget_failed:
	err = PTR_ERR(inode);
	inode = NULL;
bad_orphan:
1135
	ext4_warning(sb, __func__,
1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146
		     "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);
1147
		printk(KERN_NOTICE "i_nlink=%u\n", inode->i_nlink);
1148
		/* Avoid freeing blocks if we got a bad deleted inode */
1149
		if (inode->i_nlink == 0)
1150 1151 1152 1153
			inode->i_blocks = 0;
		iput(inode);
	}
	brelse(bitmap_bh);
1154 1155
error:
	return ERR_PTR(err);
1156 1157
}

1158
unsigned long ext4_count_free_inodes(struct super_block *sb)
1159 1160
{
	unsigned long desc_count;
1161
	struct ext4_group_desc *gdp;
1162
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1163 1164
#ifdef EXT4FS_DEBUG
	struct ext4_super_block *es;
1165 1166 1167
	unsigned long bitmap_count, x;
	struct buffer_head *bitmap_bh = NULL;

1168
	es = EXT4_SB(sb)->s_es;
1169 1170 1171
	desc_count = 0;
	bitmap_count = 0;
	gdp = NULL;
1172
	for (i = 0; i < ngroups; i++) {
1173
		gdp = ext4_get_group_desc(sb, i, NULL);
1174 1175
		if (!gdp)
			continue;
1176
		desc_count += ext4_free_inodes_count(sb, gdp);
1177
		brelse(bitmap_bh);
1178
		bitmap_bh = ext4_read_inode_bitmap(sb, i);
1179 1180 1181
		if (!bitmap_bh)
			continue;

1182
		x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
E
Eric Sandeen 已提交
1183
		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1184
			i, ext4_free_inodes_count(sb, gdp), x);
1185 1186 1187
		bitmap_count += x;
	}
	brelse(bitmap_bh);
1188 1189 1190
	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);
1191 1192 1193
	return desc_count;
#else
	desc_count = 0;
1194
	for (i = 0; i < ngroups; i++) {
1195
		gdp = ext4_get_group_desc(sb, i, NULL);
1196 1197
		if (!gdp)
			continue;
1198
		desc_count += ext4_free_inodes_count(sb, gdp);
1199 1200 1201 1202 1203 1204 1205
		cond_resched();
	}
	return desc_count;
#endif
}

/* Called at mount-time, super-block is locked */
1206
unsigned long ext4_count_dirs(struct super_block * sb)
1207 1208
{
	unsigned long count = 0;
1209
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1210

1211
	for (i = 0; i < ngroups; i++) {
1212
		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1213 1214
		if (!gdp)
			continue;
1215
		count += ext4_used_dirs_count(sb, gdp);
1216 1217 1218
	}
	return count;
}