CTC++ Coverage Report - Execution Profile    #908/1532

Files Summary | Functions Summary | Execution Profile | Index | No Index
First | Previous | Next | Last

File: fs/ext3/ialloc.c
Instrumentation mode: function-decision-multicondition
TER: 39 % (140/356)

Start/	End/
True	False	-	Line	Source
			1	/*
			2	*  linux/fs/ext3/ialloc.c
			3	*
			4	* Copyright (C) 1992, 1993, 1994, 1995
			5	* Remy Card (card@masi.ibp.fr)
			6	* Laboratoire MASI - Institut Blaise Pascal
			7	* Universite Pierre et Marie Curie (Paris VI)
			8	*
			9	*  BSD ufs-inspired inode and directory allocation by
			10	*  Stephen Tweedie (sct@redhat.com), 1993
			11	*  Big-endian to little-endian byte-swapping/bitmaps by
			12	*        David S. Miller (davem@caip.rutgers.edu), 1995
			13	*/
			14
			15	#include <linux/time.h>
			16	#include <linux/fs.h>
			17	#include <linux/jbd.h>
			18	#include <linux/ext3_fs.h>
			19	#include <linux/ext3_jbd.h>
			20	#include <linux/stat.h>
			21	#include <linux/string.h>
			22	#include <linux/quotaops.h>
			23	#include <linux/buffer_head.h>
			24	#include <linux/random.h>
			25	#include <linux/bitops.h>
			26
			27	#include <asm/byteorder.h>
			28
			29	#include "xattr.h"
			30	#include "acl.h"
			31
			32	/*
			33	* ialloc.c contains the inodes allocation and deallocation routines
			34	*/
			35
			36	/*
			37	* The free inodes are managed by bitmaps.  A file system contains several
			38	* blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
			39	* block for inodes, N blocks for the inode table and data blocks.
			40	*
			41	* The file system contains group descriptors which are located after the
			42	* super block.  Each descriptor contains the number of the bitmap block and
			43	* the free blocks count in the block.
			44	*/
			45
			46
			47	/*
			48	* Read the inode allocation bitmap for a given block_group, reading
			49	* into the specified slot in the superblock's bitmap cache.
			50	*
			51	* Return buffer_head of bitmap on success or NULL.
			52	*/
			53	static struct buffer_head *
1287E3	0		54	read_inode_bitmap(struct super_block * sb, unsigned long block_group)
			55	{
			56	struct ext3_group_desc *desc;
			57	struct buffer_head *bh = NULL;
			58
			59	desc = ext3_get_group_desc(sb, block_group, NULL);
0	1287E3	-	60	if (!desc)
0		-	61	goto error_out;
			62
			63	bh = sb_bread(sb, le32_to_cpu(desc->bg_inode_bitmap));
0	1287E3	-	64	if (!bh)
			65	ext3_error(sb, "read_inode_bitmap",
			66	"Cannot read inode bitmap - "
			67	"block_group = %lu, inode_bitmap = %u",
			68	block_group, le32_to_cpu(desc->bg_inode_bitmap));
			69	error_out:
1287E3			70	return bh;
			71	}
			72
			73	/*
			74	* NOTE! When we get the inode, we're the only people
			75	* that have access to it, and as such there are no
			76	* race conditions we have to worry about. The inode
			77	* is not on the hash-lists, and it cannot be reached
			78	* through the filesystem because the directory entry
			79	* has been deleted earlier.
			80	*
			81	* HOWEVER: we must make sure that we get no aliases,
			82	* which means that we have to call "clear_inode()"
			83	* _before_ we mark the inode not in use in the inode
			84	* bitmaps. Otherwise a newly created file might use
			85	* the same inode number (not actually the same pointer
			86	* though), and then we'd have two inodes sharing the
			87	* same inode number and space on the harddisk.
			88	*/
646223	646223		89	void ext3_free_inode (handle_t *handle, struct inode * inode)
			90	{
			91	struct super_block * sb = inode->i_sb;
			92	int is_directory;
			93	unsigned long ino;
			94	struct buffer_head *bitmap_bh = NULL;
			95	struct buffer_head *bh2;
			96	unsigned long block_group;
			97	unsigned long bit;
			98	struct ext3_group_desc * gdp;
			99	struct ext3_super_block * es;
			100	struct ext3_sb_info *sbi;
			101	int fatal = 0, err;
			102
0	646223	-	103	if (atomic_read(&inode->i_count) > 1) {
			104	printk ("ext3_free_inode: inode has count=%d\n",
			105	atomic_read(&inode->i_count));
0		-	106	return;
			107	}
0	646223	-	108	if (inode->i_nlink) {
			109	printk ("ext3_free_inode: inode has nlink=%d\n",
			110	inode->i_nlink);
0		-	111	return;
			112	}
0	646223	-	113	if (!sb) {
			114	printk("ext3_free_inode: inode on nonexistent device\n");
0		-	115	return;
			116	}
			117	sbi = EXT3_SB(sb);
			118
			119	ino = inode->i_ino;
			120	ext3_debug ("freeing inode %lu\n", ino);
0	646223	-	120	do-while (0)
			121
			122	/*
			123	* Note: we must free any quota before locking the superblock,
			124	* as writing the quota to disk may need the lock as well.
			125	*/
			126	DQUOT_INIT(inode);
0	646223	-	126	do-while (0)
			127	ext3_xattr_delete_inode(handle, inode);
			128	DQUOT_FREE_INODE(inode);
0	646223	-	128	do-while (0)
			129	DQUOT_DROP(inode);
0	646223	-	129	do-while (0)
			130
			131	is_directory = S_ISDIR(inode->i_mode);
			132
			133	/* Do this BEFORE marking the inode not in use or returning an error */
			134	clear_inode (inode);
			135
			136	es = EXT3_SB(sb)->s_es;
0	646223	-	137	if (ino < EXT3_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
0		-	137	T || _
0		-	137	F || T
	646223		137	F || F
			138	ext3_error (sb, "ext3_free_inode",
			139	"reserved or nonexistent inode %lu", ino);
0		-	140	goto error_return;
			141	}
			142	block_group = (ino - 1) / EXT3_INODES_PER_GROUP(sb);
			143	bit = (ino - 1) % EXT3_INODES_PER_GROUP(sb);
			144	bitmap_bh = read_inode_bitmap(sb, block_group);
0	646223	-	145	if (!bitmap_bh)
0		-	146	goto error_return;
			147
			148	BUFFER_TRACE(bitmap_bh, "get_write_access");
0	646223	-	148	do-while (0)
			149	fatal = ext3_journal_get_write_access(handle, bitmap_bh);
0	646223	-	150	if (fatal)
0		-	151	goto error_return;
			152
			153	/* Ok, now we can actually update the inode bitmaps.. */
0	646223	-	154	if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
			155	bit, bitmap_bh->b_data))
			156	ext3_error (sb, "ext3_free_inode",
			157	"bit already cleared for inode %lu", ino);
			158	else {
			159	gdp = ext3_get_group_desc (sb, block_group, &bh2);
			160
			161	BUFFER_TRACE(bh2, "get_write_access");
0	646223	-	161	do-while (0)
			162	fatal = ext3_journal_get_write_access(handle, bh2);
0	646223	-	163	if (fatal) goto error_return;
0		-	163	goto error_return
			164
646223	0	-	165	if (gdp) {
			166	spin_lock(sb_bgl_lock(sbi, block_group));
			166	do
0	646223	-	166	do-while (0)
0	646223	-	166	do-while (0)
			167	gdp->bg_free_inodes_count = cpu_to_le16(
			168	le16_to_cpu(gdp->bg_free_inodes_count) + 1);
23519	622704		169	if (is_directory)
			170	gdp->bg_used_dirs_count = cpu_to_le16(
			171	le16_to_cpu(gdp->bg_used_dirs_count) - 1);
			172	spin_unlock(sb_bgl_lock(sbi, block_group));
			172	do
0	646223	-	172	do-while (0)
0	646223	-	172	do-while (0)
			173	percpu_counter_inc(&sbi->s_freeinodes_counter);
23519	622704		174	if (is_directory)
			175	percpu_counter_dec(&sbi->s_dirs_counter);
			176
			177	}
			178	BUFFER_TRACE(bh2, "call ext3_journal_dirty_metadata");
0	646223	-	178	do-while (0)
			179	err = ext3_journal_dirty_metadata(handle, bh2);
646223	0	-	180	if (!fatal) fatal = err;
			181	}
			182	BUFFER_TRACE(bitmap_bh, "call ext3_journal_dirty_metadata");
0	646223	-	182	do-while (0)
			183	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
646223	0	-	184	if (!fatal)
			185	fatal = err;
			186	sb->s_dirt = 1;
			187	error_return:
			188	brelse(bitmap_bh);
			189	ext3_std_error(sb, fatal);
0	646223	-	189	if (( fatal ))
0	646223	-	189	do-while (0)
			190	}
			191
			192	/*
			193	* There are two policies for allocating an inode.  If the new inode is
			194	* a directory, then a forward search is made for a block group with both
			195	* free space and a low directory-to-inode ratio; if that fails, then of
			196	* the groups with above-average free space, that group with the fewest
			197	* directories already is chosen.
			198	*
			199	* For other inodes, search forward from the parent directory\'s block
			200	* group to find a free inode.
			201	*/
0	0	-	202	static int find_group_dir(struct super_block *sb, struct inode *parent)
			203	{
			204	int ngroups = EXT3_SB(sb)->s_groups_count;
			205	int freei, avefreei;
			206	struct ext3_group_desc *desc, *best_desc = NULL;
			207	struct buffer_head *bh;
			208	int group, best_group = -1;
			209
			210	freei = percpu_counter_read_positive(&EXT3_SB(sb)->s_freeinodes_counter);
			211	avefreei = freei / ngroups;
			212
0	0	-	213	for (group = 0; group < ngroups; group++) {
			214	desc = ext3_get_group_desc (sb, group, &bh);
0	0	-	215	if (!desc || !desc->bg_free_inodes_count)
0		-	215	T || _
0		-	215	F || T
	0	-	215	F || F
0		-	216	continue;
0	0	-	217	if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)
0		-	218	continue;
			219	if (!best_desc ||
			220	(le16_to_cpu(desc->bg_free_blocks_count) >
0	0	-	221	le16_to_cpu(best_desc->bg_free_blocks_count))) {
0		-	221	T || (_)
0		-	221	F || (T)
	0	-	221	F || (F)
			222	best_group = group;
			223	best_desc = desc;
			224	}
			225	}
0		-	226	return best_group;
			227	}
			228
			229	/*
			230	* Orlov's allocator for directories.
			231	*
			232	* We always try to spread first-level directories.
			233	*
			234	* If there are blockgroups with both free inodes and free blocks counts
			235	* not worse than average we return one with smallest directory count.
			236	* Otherwise we simply return a random group.
			237	*
			238	* For the rest rules look so:
			239	*
			240	* It's OK to put directory into a group unless
			241	* it has too many directories already (max_dirs) or
			242	* it has too few free inodes left (min_inodes) or
			243	* it has too few free blocks left (min_blocks) or
			244	* it's already running too large debt (max_debt).
			245	* Parent's group is prefered, if it doesn't satisfy these
			246	* conditions we search cyclically through the rest. If none
			247	* of the groups look good we just look for a group with more
			248	* free inodes than average (starting at parent's group).
			249	*
			250	* Debt is incremented each time we allocate a directory and decremented
			251	* when we allocate an inode, within 0--255.
			252	*/
			253
			254	#define INODE_COST 64
			255	#define BLOCK_COST 256
			256
23700	0		257	static int find_group_orlov(struct super_block *sb, struct inode *parent)
			258	{
			259	int parent_group = EXT3_I(parent)->i_block_group;
			260	struct ext3_sb_info *sbi = EXT3_SB(sb);
			261	struct ext3_super_block *es = sbi->s_es;
			262	int ngroups = sbi->s_groups_count;
			263	int inodes_per_group = EXT3_INODES_PER_GROUP(sb);
			264	int freei, avefreei;
			265	int freeb, avefreeb;
			266	int blocks_per_dir, ndirs;
			267	int max_debt, max_dirs, min_blocks, min_inodes;
			268	int group = -1, i;
			269	struct ext3_group_desc *desc;
			270	struct buffer_head *bh;
			271
			272	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
			273	avefreei = freei / ngroups;
			274	freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
			275	avefreeb = freeb / ngroups;
			276	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
			277
			278	if ((parent == sb->s_root->d_inode) ||
0	23700	-	279	(EXT3_I(parent)->i_flags & EXT3_TOPDIR_FL)) {
0		-	279	(T) || (_)
0		-	279	(F) || (T)
	23700		279	(F) || (F)
			280	int best_ndir = inodes_per_group;
			281	int best_group = -1;
			282
			283	get_random_bytes(&group, sizeof(group));
			284	parent_group = (unsigned)group % ngroups;
0	0	-	285	for (i = 0; i < ngroups; i++) {
			286	group = (parent_group + i) % ngroups;
			287	desc = ext3_get_group_desc (sb, group, &bh);
0	0	-	288	if (!desc || !desc->bg_free_inodes_count)
0		-	288	T || _
0		-	288	F || T
	0	-	288	F || F
0		-	289	continue;
0	0	-	290	if (le16_to_cpu(desc->bg_used_dirs_count) >= best_ndir)
0		-	291	continue;
0	0	-	292	if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)
0		-	293	continue;
0	0	-	294	if (le16_to_cpu(desc->bg_free_blocks_count) < avefreeb)
0		-	295	continue;
			296	best_group = group;
			297	best_ndir = le16_to_cpu(desc->bg_used_dirs_count);
			298	}
0	0	-	299	if (best_group >= 0)
0		-	300	return best_group;
0		-	301	goto fallback;
			302	}
			303
			304	blocks_per_dir = (le32_to_cpu(es->s_blocks_count) - freeb) / ndirs;
			305
			306	max_dirs = ndirs / ngroups + inodes_per_group / 16;
			307	min_inodes = avefreei - inodes_per_group / 4;
			308	min_blocks = avefreeb - EXT3_BLOCKS_PER_GROUP(sb) / 4;
			309
			310	max_debt = EXT3_BLOCKS_PER_GROUP(sb) / max(blocks_per_dir, BLOCK_COST);
0	23700	-	311	if (max_debt * INODE_COST > inodes_per_group)
			312	max_debt = inodes_per_group / INODE_COST;
0	23700	-	313	if (max_debt > 255)
			314	max_debt = 255;
0	23700	-	315	if (max_debt == 0)
			316	max_debt = 1;
			317
29785	0	-	318	for (i = 0; i < ngroups; i++) {
			319	group = (parent_group + i) % ngroups;
			320	desc = ext3_get_group_desc (sb, group, &bh);
0	29785	-	321	if (!desc || !desc->bg_free_inodes_count)
0		-	321	T || _
0		-	321	F || T
	29785		321	F || F
0		-	322	continue;
3798	25987		323	if (le16_to_cpu(desc->bg_used_dirs_count) >= max_dirs)
3798			324	continue;
2287	23700		325	if (le16_to_cpu(desc->bg_free_inodes_count) < min_inodes)
2287			326	continue;
0	23700	-	327	if (le16_to_cpu(desc->bg_free_blocks_count) < min_blocks)
0		-	328	continue;
23700			329	return group;
			330	}
			331
			332	fallback:
0	0	-	333	for (i = 0; i < ngroups; i++) {
			334	group = (parent_group + i) % ngroups;
			335	desc = ext3_get_group_desc (sb, group, &bh);
0	0	-	336	if (!desc || !desc->bg_free_inodes_count)
0		-	336	T || _
0		-	336	F || T
	0	-	336	F || F
0		-	337	continue;
0	0	-	338	if (le16_to_cpu(desc->bg_free_inodes_count) >= avefreei)
0		-	339	return group;
			340	}
			341
0	0	-	342	if (avefreei) {
			343	/*
			344	* The free-inodes counter is approximate, and for really small
			345	* filesystems the above test can fail to find any blockgroups
			346	*/
			347	avefreei = 0;
0		-	348	goto fallback;
			349	}
			350
0		-	351	return -1;
			352	}
			353
617897	0		354	static int find_group_other(struct super_block *sb, struct inode *parent)
			355	{
			356	int parent_group = EXT3_I(parent)->i_block_group;
			357	int ngroups = EXT3_SB(sb)->s_groups_count;
			358	struct ext3_group_desc *desc;
			359	struct buffer_head *bh;
			360	int group, i;
			361
			362	/*
			363	* Try to place the inode in its parent directory
			364	*/
			365	group = parent_group;
			366	desc = ext3_get_group_desc (sb, group, &bh);
			367	if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
59171	558726		368	le16_to_cpu(desc->bg_free_blocks_count))
59171			368	T && (T) && (T)
	557024		368	T && (T) && (F)
	1702		368	T && (F) && (_)
	0	-	368	F && (_) && (_)
59171			369	return group;
			370
			371	/*
			372	* We're going to place this inode in a different blockgroup from its
			373	* parent.  We want to cause files in a common directory to all land in
			374	* the same blockgroup.  But we want files which are in a different
			375	* directory which shares a blockgroup with our parent to land in a
			376	* different blockgroup.
			377	*
			378	* So add our directory's i_ino into the starting point for the hash.
			379	*/
			380	group = (group + parent->i_ino) % ngroups;
			381
			382	/*
			383	* Use a quadratic hash to find a group with a free inode and some free
			384	* blocks.
			385	*/
785766	7444		386	for (i = 1; i < ngroups; i <<= 1) {
			387	group += i;
9657	776109		388	if (group >= ngroups)
			389	group -= ngroups;
			390	desc = ext3_get_group_desc (sb, group, &bh);
			391	if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
551282	234484		392	le16_to_cpu(desc->bg_free_blocks_count))
551282			392	T && (T) && (T)
	234341		392	T && (T) && (F)
	143		392	T && (F) && (_)
	0	-	392	F && (_) && (_)
551282			393	return group;
			394	}
			395
			396	/*
			397	* That failed: try linear search for a free inode, even if that group
			398	* has no free blocks.
			399	*/
			400	group = parent_group;
7444	0	-	401	for (i = 0; i < ngroups; i++) {
0	7444	-	402	if (++group >= ngroups)
			403	group = 0;
			404	desc = ext3_get_group_desc (sb, group, &bh);
7444	0	-	405	if (desc && le16_to_cpu(desc->bg_free_inodes_count))
7444			405	T && (T)
	0	-	405	T && (F)
	0	-	405	F && (_)
7444			406	return group;
			407	}
			408
0		-	409	return -1;
			410	}
			411
			412	/*
			413	* There are two policies for allocating an inode.  If the new inode is
			414	* a directory, then a forward search is made for a block group with both
			415	* free space and a low directory-to-inode ratio; if that fails, then of
			416	* the groups with above-average free space, that group with the fewest
			417	* directories already is chosen.
			418	*
			419	* For other inodes, search forward from the parent directory's block
			420	* group to find a free inode.
			421	*/
641597	0		422	struct inode *ext3_new_inode(handle_t *handle, struct inode * dir, int mode)
			423	{
			424	struct super_block *sb;
			425	struct buffer_head *bitmap_bh = NULL;
			426	struct buffer_head *bh2;
			427	int group;
			428	unsigned long ino = 0;
			429	struct inode * inode;
			430	struct ext3_group_desc * gdp = NULL;
			431	struct ext3_super_block * es;
			432	struct ext3_inode_info *ei;
			433	struct ext3_sb_info *sbi;
			434	int err = 0;
			435	struct inode *ret;
			436	int i;
			437
			438	/* Cannot create files in a deleted directory */
0	641597	-	439	if (!dir || !dir->i_nlink)
0		-	439	T || _
0		-	439	F || T
	641597		439	F || F
0		-	440	return ERR_PTR(-EPERM);
			441
			442	sb = dir->i_sb;
			443	inode = new_inode(sb);
0	641597	-	444	if (!inode)
0		-	445	return ERR_PTR(-ENOMEM);
			446	ei = EXT3_I(inode);
			447
			448	sbi = EXT3_SB(sb);
			449	es = sbi->s_es;
23700	617897		450	if (S_ISDIR(mode)) {
0	23700	-	451	if (test_opt (sb, OLDALLOC))
			452	group = find_group_dir(sb, dir);
			453	else
			454	group = find_group_orlov(sb, dir);
			455	} else
			456	group = find_group_other(sb, dir);
			457
			458	err = -ENOSPC;
0	641597	-	459	if (group == -1)
0		-	460	goto out;
			461
641597	0	-