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

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

File: fs/ext3/balloc.c
Instrumentation mode: function-decision-multicondition
TER: 66 % (386/582)

Start/	End/
True	False	-	Line	Source
			1	/*
			2	*  linux/fs/ext3/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 <linux/time.h>
			16	#include <linux/capability.h>
			17	#include <linux/fs.h>
			18	#include <linux/jbd.h>
			19	#include <linux/ext3_fs.h>
			20	#include <linux/ext3_jbd.h>
			21	#include <linux/quotaops.h>
			22	#include <linux/buffer_head.h>
			23
			24	/*
			25	* balloc.c contains the blocks allocation and deallocation routines
			26	*/
			27
			28	/*
			29	* The free blocks are managed by bitmaps.  A file system contains several
			30	* blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
			31	* block for inodes, N blocks for the inode table and data blocks.
			32	*
			33	* The file system contains group descriptors which are located after the
			34	* super block.  Each descriptor contains the number of the bitmap block and
			35	* the free blocks count in the block.  The descriptors are loaded in memory
			36	* when a file system is mounted (see ext3_read_super).
			37	*/
			38
			39
			40	#define in_range(b, first, len)   ((b) >= (first) && (b) <= (first) + (len) - 1)
			41
1698E4	0		42	struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
			43	unsigned int block_group,
			44	struct buffer_head ** bh)
			45	{
			46	unsigned long group_desc;
			47	unsigned long offset;
			48	struct ext3_group_desc * desc;
			49	struct ext3_sb_info *sbi = EXT3_SB(sb);
			50
0	1698E4	-	51	if (block_group >= sbi->s_groups_count) {
			52	ext3_error (sb, "ext3_get_group_desc",
			53	"block_group >= groups_count - "
			54	"block_group = %d, groups_count = %lu",
			55	block_group, sbi->s_groups_count);
			56
0		-	57	return NULL;
			58	}
			59	smp_rmb();
			60
			61	group_desc = block_group >> EXT3_DESC_PER_BLOCK_BITS(sb);
			62	offset = block_group & (EXT3_DESC_PER_BLOCK(sb) - 1);
0	1698E4	-	63	if (!sbi->s_group_desc[group_desc]) {
			64	ext3_error (sb, "ext3_get_group_desc",
			65	"Group descriptor not loaded - "
			66	"block_group = %d, group_desc = %lu, desc = %lu",
			67	block_group, group_desc, offset);
0		-	68	return NULL;
			69	}
			70
			71	desc = (struct ext3_group_desc *) sbi->s_group_desc[group_desc]->b_data;
8319E3	8662E3		72	if (bh)
			73	*bh = sbi->s_group_desc[group_desc];
1698E4			74	return desc + offset;
			75	}
			76
			77	/*
			78	* Read the bitmap for a given block_group, reading into the specified
			79	* slot in the superblock's bitmap cache.
			80	*
			81	* Return buffer_head on success or NULL in case of failure.
			82	*/
			83	static struct buffer_head *
3491E3	0		84	read_block_bitmap(struct super_block *sb, unsigned int block_group)
			85	{
			86	struct ext3_group_desc * desc;
			87	struct buffer_head * bh = NULL;
			88
			89	desc = ext3_get_group_desc (sb, block_group, NULL);
0	3491E3	-	90	if (!desc)
0		-	91	goto error_out;
			92	bh = sb_bread(sb, le32_to_cpu(desc->bg_block_bitmap));
0	3491E3	-	93	if (!bh)
			94	ext3_error (sb, "read_block_bitmap",
			95	"Cannot read block bitmap - "
			96	"block_group = %d, block_bitmap = %u",
			97	block_group, le32_to_cpu(desc->bg_block_bitmap));
			98	error_out:
3491E3			99	return bh;
			100	}
			101	/*
			102	* The reservation window structure operations
			103	* --------------------------------------------
			104	* Operations include:
			105	* dump, find, add, remove, is_empty, find_next_reservable_window, etc.
			106	*
			107	* We use sorted double linked list for the per-filesystem reservation
			108	* window list. (like in vm_region).
			109	*
			110	* Initially, we keep those small operations in the abstract functions,
			111	* so later if we need a better searching tree than double linked-list,
			112	* we could easily switch to that without changing too much
			113	* code.
			114	*/
			115	#if 0
			116	static void __rsv_window_dump(struct rb_root *root, int verbose,
			117	const char *fn)
			118	{
			119	struct rb_node *n;
			120	struct ext3_reserve_window_node *rsv, *prev;
			121	int bad;
			122
			123	restart:
			124	n = rb_first(root);
			125	bad = 0;
			126	prev = NULL;
			127
			128	printk("Block Allocation Reservation Windows Map (%s):\n", fn);
			129	while (n) {
			130	rsv = list_entry(n, struct ext3_reserve_window_node, rsv_node);
			131	if (verbose)
			132	printk("reservation window 0x%p "
			133	"start:  %d, end:  %d\n",
			134	rsv, rsv->rsv_start, rsv->rsv_end);
			135	if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
			136	printk("Bad reservation %p (start >= end)\n",
			137	rsv);
			138	bad = 1;
			139	}
			140	if (prev && prev->rsv_end >= rsv->rsv_start) {
			141	printk("Bad reservation %p (prev->end >= start)\n",
			142	rsv);
			143	bad = 1;
			144	}
			145	if (bad) {
			146	if (!verbose) {
			147	printk("Restarting reservation walk in verbose mode\n");
			148	verbose = 1;
			149	goto restart;
			150	}
			151	}
			152	n = rb_next(n);
			153	prev = rsv;
			154	}
			155	printk("Window map complete.\n");
			156	if (bad)
			157	BUG();
			158	}
			159	#define rsv_window_dump(root, verbose) \
			160	__rsv_window_dump((root), (verbose), __FUNCTION__)
			161	#else
			162	#define rsv_window_dump(root, verbose) do {} while (0)
			163	#endif
			164
			165	static int
2269E3	0		166	goal_in_my_reservation(struct ext3_reserve_window *rsv, int goal,
			167	unsigned int group, struct super_block * sb)
			168	{
			169	unsigned long group_first_block, group_last_block;
			170
			171	group_first_block = le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block) +
			172	group * EXT3_BLOCKS_PER_GROUP(sb);
			173	group_last_block = group_first_block + EXT3_BLOCKS_PER_GROUP(sb) - 1;
			174
			175	if ((rsv->_rsv_start > group_last_block) ||
12969	2257E3		176	(rsv->_rsv_end < group_first_block))
8661			176	(T) || (_)
4308			176	(F) || (T)
	2257E3		176	(F) || (F)
12969			177	return 0;
			178	if ((goal >= 0) && ((goal + group_first_block < rsv->_rsv_start)
562511	1694E3		179	|| (goal + group_first_block > rsv->_rsv_end)))
538921			179	(T) && ((T) || (_))
23590			179	(T) && ((F) || (T))
	1663E3		179	(T) && ((F) || (F))
	30935		179	(F) && ((_) || (_))
562511			180	return 0;
1694E3			181	return 1;
			182	}
			183
			184	/*
			185	* Find the reserved window which includes the goal, or the previous one
			186	* if the goal is not in any window.
			187	* Returns NULL if there are no windows or if all windows start after the goal.
			188	*/
			189	static struct ext3_reserve_window_node *
1133E3	0		190	search_reserve_window(struct rb_root *root, unsigned long goal)
			191	{
			192	struct rb_node *n = root->rb_node;
			193	struct ext3_reserve_window_node *rsv;
			194
0	1133E3	-	195	if (!n)
0		-	196	return NULL;
			197
			198	do {
			199	rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
			200
2940E3	1498E3		201	if (goal < rsv->rsv_start)
			202	n = n->rb_left;
1435E3	62671		203	else if (goal > rsv->rsv_end)
			204	n = n->rb_right;
			205	else
62671			206	return rsv;
3306E3	1070E3		207	} while (n);
			208	/*
			209	* We've fallen off the end of the tree: the goal wasn't inside
			210	* any particular node.  OK, the previous node must be to one
			211	* side of the interval containing the goal.  If it's the RHS,
			212	* we need to back up one.
			213	*/
57391	1012E3		214	if (rsv->rsv_start > goal) {
			215	n = rb_prev(&rsv->rsv_node);
			216	rsv = rb_entry(n, struct ext3_reserve_window_node, rsv_node);
			217	}
1070E3			218	return rsv;
			219	}
			220
1055E3	1055E3		221	void ext3_rsv_window_add(struct super_block *sb,
			222	struct ext3_reserve_window_node *rsv)
			223	{
			224	struct rb_root *root = &EXT3_SB(sb)->s_rsv_window_root;
			225	struct rb_node *node = &rsv->rsv_node;
			226	unsigned int start = rsv->rsv_start;
			227
			228	struct rb_node ** p = &root->rb_node;
			229	struct rb_node * parent = NULL;
			230	struct ext3_reserve_window_node *this;
			231
4096E3	1055E3		232	while (*p)
			233	{
			234	parent = *p;
			235	this = rb_entry(parent, struct ext3_reserve_window_node, rsv_node);
			236
2779E3	1316E3		237	if (start < this->rsv_start)
			238	p = &(*p)->rb_left;
1316E3	0	-	239	else if (start > this->rsv_end)
			240	p = &(*p)->rb_right;
			241	else
			242	BUG();
			243	}
			244
			245	rb_link_node(node, parent, p);
			246	rb_insert_color(node, root);
			247	}
			248
1055E3	1055E3		249	static void rsv_window_remove(struct super_block *sb,
			250	struct ext3_reserve_window_node *rsv)
			251	{
			252	rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
			253	rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
			254	rsv->rsv_alloc_hit = 0;
			255	rb_erase(&rsv->rsv_node, &EXT3_SB(sb)->s_rsv_window_root);
			256	}
			257
7676E3	0		258	static inline int rsv_is_empty(struct ext3_reserve_window *rsv)
			259	{
			260	/* a valid reservation end block could not be 0 */
7676E3			261	return (rsv->_rsv_end == EXT3_RESERVE_WINDOW_NOT_ALLOCATED);
			262	}
80079	80079		263	void ext3_init_block_alloc_info(struct inode *inode)
			264	{
			265	struct ext3_inode_info *ei = EXT3_I(inode);
			266	struct ext3_block_alloc_info *block_i = ei->i_block_alloc_info;
			267	struct super_block *sb = inode->i_sb;
			268
			269	block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
80079	0	-	270	if (block_i) {
			271	struct ext3_reserve_window_node *rsv = &block_i->rsv_window_node;
			272
			273	rsv->rsv_start = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
			274	rsv->rsv_end = EXT3_RESERVE_WINDOW_NOT_ALLOCATED;
			275
			276	/*
			277	* if filesystem is mounted with NORESERVATION, the goal
			278	* reservation window size is set to zero to indicate
			279	* block reservation is off
			280	*/
0	80079	-	281	if (!test_opt(sb, RESERVATION))
			282	rsv->rsv_goal_size = 0;
			283	else
			284	rsv->rsv_goal_size = EXT3_DEFAULT_RESERVE_BLOCKS;
			285	rsv->rsv_alloc_hit = 0;
			286	block_i->last_alloc_logical_block = 0;
			287	block_i->last_alloc_physical_block = 0;
			288	}
			289	ei->i_block_alloc_info = block_i;
			290	}
			291
6411E3	2030E3		292	void ext3_discard_reservation(struct inode *inode)
			293	{
			294	struct ext3_inode_info *ei = EXT3_I(inode);
			295	struct ext3_block_alloc_info *block_i = ei->i_block_alloc_info;
			296	struct ext3_reserve_window_node *rsv;
			297	spinlock_t *rsv_lock = &EXT3_SB(inode->i_sb)->s_rsv_window_lock;
			298
4381E3	2030E3		299	if (!block_i)
4381E3			300	return;
			301
			302	rsv = &block_i->rsv_window_node;
930617	1099E3		303	if (!rsv_is_empty(&rsv->rsv_window)) {
			304	spin_lock(rsv_lock);
			304	do
0	930617	-	304	do-while (0)
0	930617	-	304	do-while (0)
930617	0	-	305	if (!rsv_is_empty(&rsv->rsv_window))
			306	rsv_window_remove(inode->i_sb, rsv);
			307	spin_unlock(rsv_lock);
			307	do
0	930617	-	307	do-while (0)
0	930617	-	307	do-while (0)
			308	}
			309	}
			310
			311	/* Free given blocks, update quota and i_blocks field */
1102E3	0		312	void ext3_free_blocks_sb(handle_t *handle, struct super_block *sb,
			313	unsigned long block, unsigned long count,
			314	int *pdquot_freed_blocks)
			315	{
			316	struct buffer_head *bitmap_bh = NULL;
			317	struct buffer_head *gd_bh;
			318	unsigned long block_group;
			319	unsigned long bit;
			320	unsigned long i;
			321	unsigned long overflow;
			322	struct ext3_group_desc * desc;
			323	struct ext3_super_block * es;
			324	struct ext3_sb_info *sbi;
			325	int err = 0, ret;
			326	unsigned group_freed;
			327
			328	*pdquot_freed_blocks = 0;
			329	sbi = EXT3_SB(sb);
			330	es = sbi->s_es;
			331	if (block < le32_to_cpu(es->s_first_data_block) ||
			332	block + count < block ||
0	1102E3	-	333	block + count > le32_to_cpu(es->s_blocks_count)) {
0		-	333	T || _ || _
0		-	333	F || T || _
0		-	333	F || F || T
	1102E3		333	F || F || F
			334	ext3_error (sb, "ext3_free_blocks",
			335	"Freeing blocks not in datazone - "
			336	"block = %lu, count = %lu", block, count);
0		-	337	goto error_return;
			338	}
			339
			340	ext3_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
0	1102E3	-	340	do-while (0)
			341
			342	do_more:
			343	overflow = 0;
			344	block_group = (block - le32_to_cpu(es->s_first_data_block)) /
			345	EXT3_BLOCKS_PER_GROUP(sb);
			346	bit = (block - le32_to_cpu(es->s_first_data_block)) %
			347	EXT3_BLOCKS_PER_GROUP(sb);
			348	/*
			349	* Check to see if we are freeing blocks across a group
			350	* boundary.
			351	*/
0	1102E3	-	352	if (bit + count > EXT3_BLOCKS_PER_GROUP(sb)) {
			353	overflow = bit + count - EXT3_BLOCKS_PER_GROUP(sb);
			354	count -= overflow;
			355	}
			356	brelse(bitmap_bh);
			357	bitmap_bh = read_block_bitmap(sb, block_group);
0	1102E3	-	358	if (!bitmap_bh)
0		-	359	goto error_return;
			360	desc = ext3_get_group_desc (sb, block_group, &gd_bh);
0	1102E3	-	361	if (!desc)
0		-	362	goto error_return;
			363
			364	if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
			365	in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
			366	in_range (block, le32_to_cpu(desc->bg_inode_table),
			367	sbi->s_itb_per_group) ||
0	1102E3	-	368	in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
0		-	368	(T && T) || (_ && _) || (_ && _) || (_ && _)
0		-	368	(T && F) || (T && T) || (_ && _) || (_ && _)
0		-	368	(T && F) || (T && F) || (T && T) || (_ && _)
0		-	368	(T && F) || (T && F) || (T && F) || (T && T)
0		-	368	(T && F) || (T && F) || (F && _) || (T && T)
0		-	368	(T && F) || (F && _) || (T && T) || (_ && _)
0		-	368	(T && F) || (F && _) || (T && F) || (T && T)
0		-	368	(T && F) || (F && _) || (F && _) || (T && T)
0		-	368	(F && _) || (T && T) || (_ && _) || (_ && _)
0		-	368	(F && _) || (T && F) || (T && T) || (_ && _)
0		-	368	(F && _) || (T && F) || (T && F) || (T && T)
0		-	368	(F && _) || (T && F) || (F && _) || (T && T)
0		-	368	(F && _) || (F && _) || (T && T) || (_ && _)
0		-	368	(F && _) || (F && _) || (T && F) || (T && T)
0		-	368	(F && _) || (F && _) || (F && _) || (T && T)
	0	-	368	(T && F) || (T && F) || (T && F) || (T && F)
	0	-	368	(T && F) || (T && F) || (T && F) || (F && _)
	0	-	368	(T && F) || (T && F) || (F && _) || (T && F)
	0	-	368	(T && F) || (T && F) || (F && _) || (F && _)
	0	-	368	(T && F) || (F && _) || (T && F) || (T && F)
	0	-	368	(T && F) || (F && _) || (T && F) || (F && _)
	0	-	368	(T && F) || (F && _) || (F && _) || (T && F)
	0	-	368	(T && F) || (F && _) || (F && _) || (F && _)
	0	-	368	(F && _) || (T && F) || (T && F) || (T && F)
	0	-	368	(F && _) || (T && F) || (T && F) || (F && _)
	0	-	368	(F && _) || (T && F) || (F && _) || (T && F)
	0	-	368	(F && _) || (T && F) || (F && _) || (F && _)
	1102E3		368	(F && _) || (F && _) || (T && F) || (T && F)
	0	-	368	(F && _) || (F && _) || (T && F) || (F && _)
	0	-	368	(F && _) || (F && _) || (F && _) || (T && F)
	0	-	368	(F && _) || (F && _) || (F && _) || (F && _)
			369	sbi->s_itb_per_group))
			370	ext3_error (sb, "ext3_free_blocks",
			371	"Freeing blocks in system zones - "
			372	"Block = %lu, count = %lu",
			373	block, count);
			374
			375	/*
			376	* We are about to start releasing blocks in the bitmap,
			377	* so we need undo access.
			378	*/
			379	/* @@@ check errors */
			380	BUFFER_TRACE(bitmap_bh, "getting undo access");
0	1102E3	-	380	do-while (0)
			381	err = ext3_journal_get_undo_access(handle, bitmap_bh);
0	1102E3	-	382	if (err)
0		-	383	goto error_return;
			384
			385	/*
			386	* We are about to modify some metadata.  Call the journal APIs
			387	* to unshare ->b_data if a currently-committing transaction is
			388	* using it
			389	*/
			390	BUFFER_TRACE(gd_bh, "get_write_access");
0	1102E3	-	390	do-while (0)
			391	err = ext3_journal_get_write_access(handle, gd_bh);
0	1102E3	-	392	if (err)
0		-	393	goto error_return;
			394
			395	jbd_lock_bh_state(bitmap_bh);
			396
2354E3	1102E3		397	for (i = 0, group_freed = 0; i < count; i++) {
			398	/*
			399	* An HJ special.  This is expensive...
			400	*/
			401	#ifdef CONFIG_JBD_DEBUG
			402	jbd_unlock_bh_state(bitmap_bh);
			403	{
			404	struct buffer_head *debug_bh;
			405	debug_bh = sb_find_get_block(sb, block + i);
			406	if (debug_bh) {
			407	BUFFER_TRACE(debug_bh, "Deleted!");
			408	if (!bh2jh(bitmap_bh)->b_committed_data)
			409	BUFFER_TRACE(debug_bh,
			410	"No commited data in bitmap");
			411	BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
			412	__brelse(debug_bh);
			413	}
			414	}
			415	jbd_lock_bh_state(bitmap_bh);
			416	#endif
1300	2352E3		417	if (need_resched()) {
			418	jbd_unlock_bh_state(bitmap_bh);
			419	cond_resched();
			420	jbd_lock_bh_state(bitmap_bh);
			421	}
			422	/* @@@ This prevents newly-allocated data from being
			423	* freed and then reallocated within the same
			424	* transaction.
			425	*
			426	* Ideally we would want to allow that to happen, but to
			427	* do so requires making journal_forget() capable of
			428	* revoking the queued write of a data block, which
			429	* implies blocking on the journal lock.  *forget()
			430	* cannot block due to truncate races.
			431	*
			432	* Eventually we can fix this by making journal_forget()
			433	* return a status indicating whether or not it was able
			434	* to revoke the buffer.  On successful revoke, it is
			435	* safe not to set the allocation bit in the committed
			436	* bitmap, because we know that there is no outstanding
			437	* activity on the buffer any more and so it is safe to
			438	* reallocate it.
			439	*/
			440	BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
0	2354E3	-	440	do-while (0)
			441	J_ASSERT_BH(bitmap_bh,
0	2354E3	-	441	if (! ( bh2jh ( bitmap_bh ) -> b_committed..
0	2354E3	-	441	do-while (0)
			442	bh2jh(bitmap_bh)->b_committed_data != NULL);
			443	ext3_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
			444	bh2jh(bitmap_bh)->b_committed_data);
			445
			446	/*
			447	* We clear the bit in the bitmap after setting the committed
			448	* data bit, because this is the reverse order to that which
			449	* the allocator uses.
			450	*/
			451	BUFFER_TRACE(bitmap_bh, "clear bit");
0	2354E3	-	451	do-while (0)
0	2354E3	-	452	if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
			453	bit + i, bitmap_bh->b_data)) {
			454	jbd_unlock_bh_state(bitmap_bh);
			455	ext3_error(sb, __FUNCTION__,
			456	"bit&nb