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

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

File: fs/ext2/balloc.c
Instrumentation mode: function-decision-multicondition
TER: 0 % ( 0/280)

Start/	End/
True	False	-	Line	Source
			1	/*
			2	*  linux/fs/ext2/balloc.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	*  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
			10	*  Big-endian to little-endian byte-swapping/bitmaps by
			11	*        David S. Miller (davem@caip.rutgers.edu), 1995
			12	*/
			13
			14	#include <linux/config.h>
			15	#include "ext2.h"
			16	#include <linux/quotaops.h>
			17	#include <linux/sched.h>
			18	#include <linux/buffer_head.h>
			19	#include <linux/capability.h>
			20
			21	/*
			22	* balloc.c contains the blocks allocation and deallocation routines
			23	*/
			24
			25	/*
			26	* The free blocks are managed by bitmaps.  A file system contains several
			27	* blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
			28	* block for inodes, N blocks for the inode table and data blocks.
			29	*
			30	* The file system contains group descriptors which are located after the
			31	* super block.  Each descriptor contains the number of the bitmap block and
			32	* the free blocks count in the block.  The descriptors are loaded in memory
			33	* when a file system is mounted (see ext2_read_super).
			34	*/
			35
			36
			37	#define in_range(b, first, len)   ((b) >= (first) && (b) <= (first) + (len) - 1)
			38
0	0	-	39	struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb,
			40	unsigned int block_group,
			41	struct buffer_head ** bh)
			42	{
			43	unsigned long group_desc;
			44	unsigned long offset;
			45	struct ext2_group_desc * desc;
			46	struct ext2_sb_info *sbi = EXT2_SB(sb);
			47
0	0	-	48	if (block_group >= sbi->s_groups_count) {
			49	ext2_error (sb, "ext2_get_group_desc",
			50	"block_group >= groups_count - "
			51	"block_group = %d, groups_count = %lu",
			52	block_group, sbi->s_groups_count);
			53
0		-	54	return NULL;
			55	}
			56
			57	group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
			58	offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
0	0	-	59	if (!sbi->s_group_desc[group_desc]) {
			60	ext2_error (sb, "ext2_get_group_desc",
			61	"Group descriptor not loaded - "
			62	"block_group = %d, group_desc = %lu, desc = %lu",
			63	block_group, group_desc, offset);
0		-	64	return NULL;
			65	}
			66
			67	desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data;
0	0	-	68	if (bh)
			69	*bh = sbi->s_group_desc[group_desc];
0		-	70	return desc + offset;
			71	}
			72
			73	/*
			74	* Read the bitmap for a given block_group, reading into the specified
			75	* slot in the superblock's bitmap cache.
			76	*
			77	* Return buffer_head on success or NULL in case of failure.
			78	*/
			79	static struct buffer_head *
0	0	-	80	read_block_bitmap(struct super_block *sb, unsigned int block_group)
			81	{
			82	struct ext2_group_desc * desc;
			83	struct buffer_head * bh = NULL;
			84
			85	desc = ext2_get_group_desc (sb, block_group, NULL);
0	0	-	86	if (!desc)
0		-	87	goto error_out;
			88	bh = sb_bread(sb, le32_to_cpu(desc->bg_block_bitmap));
0	0	-	89	if (!bh)
			90	ext2_error (sb, "read_block_bitmap",
			91	"Cannot read block bitmap - "
			92	"block_group = %d, block_bitmap = %u",
			93	block_group, le32_to_cpu(desc->bg_block_bitmap));
			94	error_out:
0		-	95	return bh;
			96	}
			97
			98	/*
			99	* Set sb->s_dirt here because the superblock was "logically" altered.  We
			100	* need to recalculate its free blocks count and flush it out.
			101	*/
0	0	-	102	static int reserve_blocks(struct super_block *sb, int count)
			103	{
			104	struct ext2_sb_info *sbi = EXT2_SB(sb);
			105	struct ext2_super_block *es = sbi->s_es;
			106	unsigned free_blocks;
			107	unsigned root_blocks;
			108
			109	free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
			110	root_blocks = le32_to_cpu(es->s_r_blocks_count);
			111
0	0	-	112	if (free_blocks < count)
			113	count = free_blocks;
			114
			115	if (free_blocks < root_blocks + count && !capable(CAP_SYS_RESOURCE) &&
			116	sbi->s_resuid != current->fsuid &&
0	0	-	117	(sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
0		-	117	T && T && T && (T || _)
0		-	117	T && T && T && (F || T)
	0	-	117	T && T && T && (F || F)
	0	-	117	T && T && F && (_ || _)
	0	-	117	T && F && _ && (_ || _)
	0	-	117	F && _ && _ && (_ || _)
			118	/*
			119	* We are too close to reserve and we are not privileged.
			120	* Can we allocate anything at all?
			121	*/
0	0	-	122	if (free_blocks > root_blocks)
			123	count = free_blocks - root_blocks;
			124	else
0		-	125	return 0;
			126	}
			127
			128	percpu_counter_mod(&sbi->s_freeblocks_counter, -count);
			129	sb->s_dirt = 1;
0		-	130	return count;
			131	}
			132
0	0	-	133	static void release_blocks(struct super_block *sb, int count)
			134	{
0	0	-	135	if (count) {
			136	struct ext2_sb_info *sbi = EXT2_SB(sb);
			137
			138	percpu_counter_mod(&sbi->s_freeblocks_counter, count);
			139	sb->s_dirt = 1;
			140	}
			141	}
			142
0	0	-	143	static int group_reserve_blocks(struct ext2_sb_info *sbi, int group_no,
			144	struct ext2_group_desc *desc, struct buffer_head *bh, int count)
			145	{
			146	unsigned free_blocks;
			147
0	0	-	148	if (!desc->bg_free_blocks_count)
0		-	149	return 0;
			150
			151	spin_lock(sb_bgl_lock(sbi, group_no));
			151	do
0	0	-	151	do-while (0)
0	0	-	151	do-while (0)
			152	free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
0	0	-	153	if (free_blocks < count)
			154	count = free_blocks;
			155	desc->bg_free_blocks_count = cpu_to_le16(free_blocks - count);
			156	spin_unlock(sb_bgl_lock(sbi, group_no));
			156	do
0	0	-	156	do-while (0)
0	0	-	156	do-while (0)
			157	mark_buffer_dirty(bh);
0		-	158	return count;
			159	}
			160
0	0	-	161	static void group_release_blocks(struct super_block *sb, int group_no,
			162	struct ext2_group_desc *desc, struct buffer_head *bh, int count)
			163	{
0	0	-	164	if (count) {
			165	struct ext2_sb_info *sbi = EXT2_SB(sb);
			166	unsigned free_blocks;
			167
			168	spin_lock(sb_bgl_lock(sbi, group_no));
			168	do
0	0	-	168	do-while (0)
0	0	-	168	do-while (0)
			169	free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
			170	desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count);
			171	spin_unlock(sb_bgl_lock(sbi, group_no));
			171	do
0	0	-	171	do-while (0)
0	0	-	171	do-while (0)
			172	sb->s_dirt = 1;
			173	mark_buffer_dirty(bh);
			174	}
			175	}
			176
			177	/* Free given blocks, update quota and i_blocks field */
0	0	-	178	void ext2_free_blocks (struct inode * inode, unsigned long block,
			179	unsigned long count)
			180	{
			181	struct buffer_head *bitmap_bh = NULL;
			182	struct buffer_head * bh2;
			183	unsigned long block_group;
			184	unsigned long bit;
			185	unsigned long i;
			186	unsigned long overflow;
			187	struct super_block * sb = inode->i_sb;
			188	struct ext2_sb_info * sbi = EXT2_SB(sb);
			189	struct ext2_group_desc * desc;
			190	struct ext2_super_block * es = sbi->s_es;
			191	unsigned freed = 0, group_freed;
			192
			193	if (block < le32_to_cpu(es->s_first_data_block) ||
			194	block + count < block ||
0	0	-	195	block + count > le32_to_cpu(es->s_blocks_count)) {
0		-	195	T || _ || _
0		-	195	F || T || _
0		-	195	F || F || T
	0	-	195	F || F || F
			196	ext2_error (sb, "ext2_free_blocks",
			197	"Freeing blocks not in datazone - "
			198	"block = %lu, count = %lu", block, count);
0		-	199	goto error_return;
			200	}
			201
			202	ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
			203
			204	do_more:
			205	overflow = 0;
			206	block_group = (block - le32_to_cpu(es->s_first_data_block)) /
			207	EXT2_BLOCKS_PER_GROUP(sb);
			208	bit = (block - le32_to_cpu(es->s_first_data_block)) %
			209	EXT2_BLOCKS_PER_GROUP(sb);
			210	/*
			211	* Check to see if we are freeing blocks across a group
			212	* boundary.
			213	*/
0	0	-	214	if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) {
			215	overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb);
			216	count -= overflow;
			217	}
			218	brelse(bitmap_bh);
			219	bitmap_bh = read_block_bitmap(sb, block_group);
0	0	-	220	if (!bitmap_bh)
0		-	221	goto error_return;
			222
			223	desc = ext2_get_group_desc (sb, block_group, &bh2);
0	0	-	224	if (!desc)
0		-	225	goto error_return;
			226
			227	if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
			228	in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
			229	in_range (block, le32_to_cpu(desc->bg_inode_table),
			230	sbi->s_itb_per_group) ||
0	0	-	231	in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
0		-	231	(T && T) || (_ && _) || (_ && _) || (_ && _)
0		-	231	(T && F) || (T && T) || (_ && _) || (_ && _)
0		-	231	(T && F) || (T && F) || (T && T) || (_ && _)
0		-	231	(T && F) || (T && F) || (T && F) || (T && T)
0		-	231	(T && F) || (T && F) || (F && _) || (T && T)
0		-	231	(T && F) || (F && _) || (T && T) || (_ && _)
0		-	231	(T && F) || (F && _) || (T && F) || (T && T)
0		-	231	(T && F) || (F && _) || (F && _) || (T && T)
0		-	231	(F && _) || (T && T) || (_ && _) || (_ && _)
0		-	231	(F && _) || (T && F) || (T && T) || (_ && _)
0		-	231	(F && _) || (T && F) || (T && F) || (T && T)
0		-	231	(F && _) || (T && F) || (F && _) || (T && T)
0		-	231	(F && _) || (F && _) || (T && T) || (_ && _)
0		-	231	(F && _) || (F && _) || (T && F) || (T && T)
0		-	231	(F && _) || (F && _) || (F && _) || (T && T)
	0	-	231	(T && F) || (T && F) || (T && F) || (T && F)
	0	-	231	(T && F) || (T && F) || (T && F) || (F && _)
	0	-	231	(T && F) || (T && F) || (F && _) || (T && F)
	0	-	231	(T && F) || (T && F) || (F && _) || (F && _)
	0	-	231	(T && F) || (F && _) || (T && F) || (T && F)
	0	-	231	(T && F) || (F && _) || (T && F) || (F && _)
	0	-	231	(T && F) || (F && _) || (F && _) || (T && F)
	0	-	231	(T && F) || (F && _) || (F && _) || (F && _)
	0	-	231	(F && _) || (T && F) || (T && F) || (T && F)
	0	-	231	(F && _) || (T && F) || (T && F) || (F && _)
	0	-	231	(F && _) || (T && F) || (F && _) || (T && F)
	0	-	231	(F && _) || (T && F) || (F && _) || (F && _)
	0	-	231	(F && _) || (F && _) || (T && F) || (T && F)
	0	-	231	(F && _) || (F && _) || (T && F) || (F && _)
	0	-	231	(F && _) || (F && _) || (F && _) || (T && F)
	0	-	231	(F && _) || (F && _) || (F && _) || (F && _)
			232	sbi->s_itb_per_group))
			233	ext2_error (sb, "ext2_free_blocks",
			234	"Freeing blocks in system zones - "
			235	"Block = %lu, count = %lu",
			236	block, count);
			237
0	0	-	238	for (i = 0, group_freed = 0; i < count; i++) {
0	0	-	239	if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
			240	bit + i, bitmap_bh->b_data)) {
			241	ext2_error(sb, __FUNCTION__,
			242	"bit already cleared for block %lu", block + i);
			243	} else {
			244	group_freed++;
			245	}
			246	}
			247
			248	mark_buffer_dirty(bitmap_bh);
0	0	-	249	if (sb->s_flags & MS_SYNCHRONOUS)
			250	sync_dirty_buffer(bitmap_bh);
			251
			252	group_release_blocks(sb, block_group, desc, bh2, group_freed);
			253	freed += group_freed;
			254
0	0	-	255	if (overflow) {
			256	block += count;
			257	count = overflow;
0		-	258	goto do_more;
			259	}
			260	error_return:
			261	brelse(bitmap_bh);
			262	release_blocks(sb, freed);
			263	DQUOT_FREE_BLOCK(inode, freed);
			264	}
			265
0	0	-	266	static int grab_block(spinlock_t *lock, char *map, unsigned size, int goal)
			267	{
			268	int k;
			269	char *p, *r;
			270
0	0	-	271	if (!ext2_test_bit(goal, map))
0	0	-	271	ternary-?: __builtin_constant_p ( ( goal ) )
0		-	272	goto got_it;
			273
			274	repeat:
0	0	-	275	if (goal) {
			276	/*
			277	* The goal was occupied; search forward for a free
			278	* block within the next XX blocks.
			279	*
			280	* end_goal is more or less random, but it has to be
			281	* less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
			282	* next 64-bit boundary is simple..
			283	*/
			284	k = (goal + 63) & ~63;
			285	goal = ext2_find_next_zero_bit(map, k, goal);
0	0	-	285	ternary-?: __builtin_constant_p ( k ) && ( k..
0	0	-	286	if (goal < k)
0		-	287	goto got_it;
			288	/*
			289	* Search in the remainder of the current group.
			290	*/
			291	}
			292
			293	p = map + (goal >> 3);
			294	r = memscan(p, 0, (size - goal + 7) >> 3);
			295	k = (r - map) << 3;
0	0	-	296	if (k < size) {
			297	/*
			298	* We have succeeded in finding a free byte in the block
			299	* bitmap.  Now search backwards to find the start of this
			300	* group of free blocks - won't take more than 7 iterations.
			301	*/
0	0	-	302	for (goal = k; goal && !ext2_test_bit (goal - 1, map); goal--)
0		-	302	T && !(F)
	0	-	302	T && !(T)
	0	-	302	F && !(_)
0	0	-	302	ternary-?: __builtin_constant_p ( ( goal - 1..
			303	;
0		-	304	goto got_it;
			305	}
			306
			307	k = ext2_find_next_zero_bit ((u32 *)map, size, goal);
0	0	-	307	ternary-?: __builtin_constant_p ( size ) && ( ..
0	0	-	308	if (k < size) {
			309	goal = k;
0		-	310	goto got_it;
			311	}
0		-	312	return -1;
			313	got_it:
0	0	-	314	if (ext2_set_bit_atomic(lock, goal, (void *) map))
0		-	315	goto repeat;
0		-	316	return goal;
			317	}
			318
			319	/*
			320	* ext2_new_block uses a goal block to assist allocation.  If the goal is
			321	* free, or there is a free block within 32 blocks of the goal, that block
			322	* is allocated.  Otherwise a forward search is made for a free block; within
			323	* each block group the search first looks for an entire free byte in the block
			324	* bitmap, and then for any free bit if that fails.
			325	* This function also updates quota and i_blocks field.
			326	*/
0	0	-	327	int ext2_new_block(struct inode *inode, unsigned long goal,
			328	u32 *prealloc_count, u32 *prealloc_block, int *err)
			329	{
			330	struct buffer_head *bitmap_bh = NULL;
			331	struct buffer_head *gdp_bh;   /* bh2 */
			332	struct ext2_group_desc *desc;
			333	int group_no;         /* i */
			334	int ret_block;         /* j */
			335	int group_idx;         /* k */
			336	int target_block;      /* tmp */
			337	int block = 0;
			338	struct super_block *sb = inode->i_sb;
			339	struct ext2_sb_info *sbi = EXT2_SB(sb);
			340	struct ext2_super_block *es = sbi->s_es;
			341	unsigned group_size = EXT2_BLOCKS_PER_GROUP(sb);
			342	unsigned prealloc_goal = es->s_prealloc_blocks;
			343	unsigned group_alloc = 0, es_alloc, dq_alloc;
			344	int nr_scanned_groups;
			345
0	0	-	346	if (!prealloc_goal--)
			347	prealloc_goal = EXT2_DEFAULT_PREALLOC_BLOCKS - 1;
0	0	-	348	if (!prealloc_count || *prealloc_count)
0		-	348	T || _
0		-	348	F || T
	0	-	348	F || F
			349	prealloc_goal = 0;
			350
0	0	-	351	if (DQUOT_ALLOC_BLOCK(inode, 1)) {
			352	*err = -EDQUOT;
0		-	353	goto out;
			354	}
			355
0	0	-	356	while (prealloc_goal && DQUOT_PREALLOC_BLOCK(inode, prealloc_goal))
0		-	356	T && T
	0	-	356	T && F
	0	-	356	F && _
			357	prealloc_goal--;
			358
			359	dq_alloc = prealloc_goal + 1;
			360	es_alloc = reserve_blocks(sb, dq_alloc);
0	0	-	361	if (!es_alloc) {
			362	*err = -ENOSPC;
0		-	363	goto out_dquot;
			364	}
			365
			366	ext2_debug ("goal=%lu.\n", goal);
			367
			368	if (goal < le32_to_cpu(es->s_first_data_block) ||
0	0	-	369	goal >= le32_to_cpu(es->s_blocks_count))
0		-	369	T || _
0		-	369	F || T
	0	-	369	F || F
			370	goal = le32_to_cpu(es->s_first_data_block);
			371	group_no = (goal - le32_to_cpu(es->s_first_data_block)) / group_size;
			372	desc = ext2_get_group_desc (sb, group_no, &gdp_bh);
0	0	-	373	if (!desc) {
			374	/*
			375	* gdp_bh may still be uninitialised.  But group_release_blocks
			376	* will not touch it because group_alloc is zero.
			377	*/
0		-	378	goto io_error;
			379	}
			380
			381	group_alloc = group_reserve_blocks(sbi, group_no, desc,
			382	gdp_bh, es_alloc);
0	0	-	383	if (group_alloc) {
			384	ret_block = ((goal - le32_to_cpu(es->s_first_data_block)) %
			385	group_size);
			386	brelse(bitmap_bh);
			387	bitmap_bh = read_block_bitmap(sb, group_no);
0	0	-	388	if (!bitmap_bh)
0		-	389	goto io_error;
			390
			391	ext2_debug("goal is at %d:%d.\n", group_no, ret_block);
			392
			393	ret_block = grab_block(sb_bgl_lock(sbi, group_no),
			394	bitmap_bh->b_data, group_size, ret_block);
0	0	-	395	if (ret_block >= 0)
0		-	396	goto got_block;
			397	group_release_blocks(sb, group_no, desc, gdp_bh, group_alloc);
			398	group_alloc = 0;
			399	}
			400
			401	ext2_debug ("Bit not found in block group %d.\n", group_no);
			402
			403	/*
			404	* Now search the rest of the groups.  We assume that
			405	* i and desc correctly point to the last group visited.
			406	*/
			407	nr_scanned_groups = 0;
			408	retry:
			409	for (group_idx = 0; !group_alloc &&
0	0	-	410	group_idx < sbi->s_groups_count; group_idx++) {
0		-	410	T && T
	0	-	410	T && F
	0	-	410	F && _
			411	group_no++;
0	0	-	412	if (group_no >= sbi->s_groups_count)
			413	group_no = 0;
			414	desc = ext2_get_group_desc(sb, group_no, &gdp_bh);
0	0	-	415	if (!desc)
0		-	416	goto io_error;
			417	group_alloc = group_reserve_blocks(sbi, group_no, desc,
			418	gdp_bh, es_alloc);
			419	}
0	0	-