/* *  linux/fs/ext2/inode.c * * Copyright (C) 1992, 1993, 1994, 1995 * Remy Card (card@masi.ibp.fr) * Laboratoire MASI - Institut Blaise Pascal * Universite Pierre et Marie Curie (Paris VI) * *  from * *  linux/fs/minix/inode.c * *  Copyright (C) 1991, 1992  Linus Torvalds * *  Goal-directed block allocation by Stephen Tweedie * 	(sct@dcs.ed.ac.uk), 1993, 1998 *  Big-endian to little-endian byte-swapping/bitmaps by *        David S. Miller (davem@caip.rutgers.edu), 1995 *  64-bit file support on 64-bit platforms by Jakub Jelinek * 	(jj@sunsite.ms.mff.cuni.cz) * *  Assorted race fixes, rewrite of ext2_get_block() by Al Viro, 2000 */ #include <linux/smp_lock.h>#include <linux/time.h>#include <linux/highuid.h>#include <linux/pagemap.h>#include <linux/quotaops.h>#include <linux/module.h>#include <linux/writeback.h>#include <linux/buffer_head.h>#include <linux/mpage.h>#include "ext2.h"#include "acl.h"#include "xip.h" MODULE_AUTHOR("Remy Card and others");MODULE_DESCRIPTION("Second Extended Filesystem");MODULE_LICENSE("GPL"); static int ext2_update_inode(struct inode * inode, int do_sync); /* * Test whether an inode is a fast symlink. */static inline int ext2_inode_is_fast_symlink(struct inode *inode){	int ea_blocks = EXT2_I(inode)->i_file_acl ?		(inode->i_sb->s_blocksize >> 9) : 0; 	return (S_ISLNK(inode->i_mode) &&		inode->i_blocks - ea_blocks == 0);} /* * Called at each iput(). * * The inode may be "bad" if ext2_read_inode() saw an error from * ext2_get_inode(), so we need to check that to avoid freeing random disk * blocks. */void ext2_put_inode(struct inode *inode){	if (!is_bad_inode(inode))		ext2_discard_prealloc(inode);} /* * Called at the last iput() if i_nlink is zero. */void ext2_delete_inode (struct inode * inode){	truncate_inode_pages(&inode->i_data, 0); 	if (is_bad_inode(inode))		goto no_delete;	EXT2_I(inode)->i_dtime	= get_seconds();	mark_inode_dirty(inode);	ext2_update_inode(inode, inode_needs_sync(inode)); 	inode->i_size = 0;	if (inode->i_blocks)		ext2_truncate (inode);	ext2_free_inode (inode); 	return;no_delete:	clear_inode(inode);	/* We must guarantee clearing of inode... */} void ext2_discard_prealloc (struct inode * inode){#ifdef EXT2_PREALLOCATE	struct ext2_inode_info *ei = EXT2_I(inode);	write_lock(&ei->i_meta_lock);	if (ei->i_prealloc_count) {		unsigned short total = ei->i_prealloc_count;		unsigned long block = ei->i_prealloc_block;		ei->i_prealloc_count = 0;		ei->i_prealloc_block = 0;		write_unlock(&ei->i_meta_lock);		ext2_free_blocks (inode, block, total);		return;	} else		write_unlock(&ei->i_meta_lock);#endif} static int ext2_alloc_block (struct inode * inode, unsigned long goal, int *err){#ifdef EXT2FS_DEBUG	static unsigned long alloc_hits, alloc_attempts;#endif	unsigned long result;  #ifdef EXT2_PREALLOCATE	struct ext2_inode_info *ei = EXT2_I(inode);	write_lock(&ei->i_meta_lock);	if (ei->i_prealloc_count &&	    (goal == ei->i_prealloc_block || goal + 1 == ei->i_prealloc_block))	{		result = ei->i_prealloc_block++;		ei->i_prealloc_count--;		write_unlock(&ei->i_meta_lock);		ext2_debug ("preallocation hit (%lu/%lu).\n",			    ++alloc_hits, ++alloc_attempts);	} else {		write_unlock(&ei->i_meta_lock);		ext2_discard_prealloc (inode);		ext2_debug ("preallocation miss (%lu/%lu).\n",			    alloc_hits, ++alloc_attempts);		if (S_ISREG(inode->i_mode))			result = ext2_new_block (inode, goal, 				 &ei->i_prealloc_count,				 &ei->i_prealloc_block, err);		else			result = ext2_new_block(inode, goal, NULL, NULL, err);	}#else	result = ext2_new_block (inode, goal, 0, 0, err);#endif	return result;} typedef struct {	__le32	*p;	__le32	key;	struct buffer_head *bh;} Indirect; static inline void add_chain(Indirect *p, struct buffer_head *bh, __le32 *v){	p->key = *(p->p = v);	p->bh = bh;} static inline int verify_chain(Indirect *from, Indirect *to){	while (from <= to && from->key == *from->p)		from++;	return (from > to);} /** *	ext2_block_to_path - parse the block number into array of offsets *	@inode: inode in question (we are only interested in its superblock) *	@i_block: block number to be parsed *	@offsets: array to store the offsets in *      @boundary: set this non-zero if the referred-to block is likely to be *             followed (on disk) by an indirect block. *	To store the locations of file's data ext2 uses a data structure common *	for UNIX filesystems - tree of pointers anchored in the inode, with *	data blocks at leaves and indirect blocks in intermediate nodes. *	This function translates the block number into path in that tree - *	return value is the path length and @offsets[n] is the offset of *	pointer to (n+1)th node in the nth one. If @block is out of range *	(negative or too large) warning is printed and zero returned. * *	Note: function doesn't find node addresses, so no IO is needed. All *	we need to know is the capacity of indirect blocks (taken from the *	inode->i_sb). */ /* * Portability note: the last comparison (check that we fit into triple * indirect block) is spelled differently, because otherwise on an * architecture with 32-bit longs and 8Kb pages we might get into trouble * if our filesystem had 8Kb blocks. We might use long long, but that would * kill us on x86. Oh, well, at least the sign propagation does not matter - * i_block would have to be negative in the very beginning, so we would not * get there at all. */ static int ext2_block_to_path(struct inode *inode,			long i_block, int offsets[4], int *boundary){	int ptrs = EXT2_ADDR_PER_BLOCK(inode->i_sb);	int ptrs_bits = EXT2_ADDR_PER_BLOCK_BITS(inode->i_sb);	const long direct_blocks = EXT2_NDIR_BLOCKS,		indirect_blocks = ptrs,		double_blocks = (1 << (ptrs_bits * 2));	int n = 0;	int final = 0; 	if (i_block < 0) {		ext2_warning (inode->i_sb, "ext2_block_to_path", "block < 0");	} else if (i_block < direct_blocks) {		offsets[n++] = i_block;		final = direct_blocks;	} else if ( (i_block -= direct_blocks) < indirect_blocks) {		offsets[n++] = EXT2_IND_BLOCK;		offsets[n++] = i_block;		final = ptrs;	} else if ((i_block -= indirect_blocks) < double_blocks) {		offsets[n++] = EXT2_DIND_BLOCK;		offsets[n++] = i_block >> ptrs_bits;		offsets[n++] = i_block & (ptrs - 1);		final = ptrs;	} else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) {		offsets[n++] = EXT2_TIND_BLOCK;		offsets[n++] = i_block >> (ptrs_bits * 2);		offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1);		offsets[n++] = i_block & (ptrs - 1);		final = ptrs;	} else {		ext2_warning (inode->i_sb, "ext2_block_to_path", "block > big");	}	if (boundary)		*boundary = (i_block & (ptrs - 1)) == (final - 1);	return n;} /** *	ext2_get_branch - read the chain of indirect blocks leading to data *	@inode: inode in question *	@depth: depth of the chain (1 - direct pointer, etc.) *	@offsets: offsets of pointers in inode/indirect blocks *	@chain: place to store the result *	@err: here we store the error value * *	Function fills the array of triples <key, p, bh> and returns %NULL *	if everything went OK or the pointer to the last filled triple *	(incomplete one) otherwise. Upon the return chain[i].key contains *	the number of (i+1)-th block in the chain (as it is stored in memory, *	i.e. little-endian 32-bit), chain[i].p contains the address of that *	number (it points into struct inode for i==0 and into the bh->b_data *	for i>0) and chain[i].bh points to the buffer_head of i-th indirect *	block for i>0 and NULL for i==0. In other words, it holds the block *	numbers of the chain, addresses they were taken from (and where we can *	verify that chain did not change) and buffer_heads hosting these *	numbers. * *	Function stops when it stumbles upon zero pointer (absent block) *		(pointer to last triple returned, *@err == 0) *	or when it gets an IO error reading an indirect block *		(ditto, *@err == -EIO) *	or when it notices that chain had been changed while it was reading *		(ditto, *@err == -EAGAIN) *	or when it reads all @depth-1 indirect blocks successfully and finds *	the whole chain, all way to the data (returns %NULL, *err == 0). */static Indirect *ext2_get_branch(struct inode *inode,				 int depth,				 int *offsets,				 Indirect chain[4],				 int *err){	struct super_block *sb = inode->i_sb;	Indirect *p = chain;	struct buffer_head *bh; 	*err = 0;	/* i_data is not going away, no lock needed */	add_chain (chain, NULL, EXT2_I(inode)->i_data + *offsets);	if (!p->key)		goto no_block;	while (--depth) {		bh = sb_bread(sb, le32_to_cpu(p->key));		if (!bh)			goto failure;		read_lock(&EXT2_I(inode)->i_meta_lock);		if (!verify_chain(chain, p))			goto changed;		add_chain(++p, bh, (__le32*)bh->b_data + *++offsets);		read_unlock(&EXT2_I(inode)->i_meta_lock);		if (!p->key)			goto no_block;	}	return NULL; changed:	read_unlock(&EXT2_I(inode)->i_meta_lock);	brelse(bh);	*err = -EAGAIN;	goto no_block;failure:	*err = -EIO;no_block:	return p;} /** *	ext2_find_near - find a place for allocation with sufficient locality *	@inode: owner *	@ind: descriptor of indirect block. * *	This function returns the prefered place for block allocation. *	It is used when heuristic for sequential allocation fails. *	Rules are: *	  + if there is a block to the left of our position - allocate near it. *	  + if pointer will live in indirect block - allocate near that block. *	  + if pointer will live in inode - allocate in the same cylinder group. * * In the latter case we colour the starting block by the callers PID to * prevent it from clashing with concurrent allocations for a different inode * in the same block group.   The PID is used here so that functionally related * files will be close-by on-disk. * *	Caller must make sure that @ind is valid and will stay that way. */ static unsigned long ext2_find_near(struct inode *inode, Indirect *ind){	struct ext2_inode_info *ei = EXT2_I(inode);	__le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data;	__le32 *p;	unsigned long bg_start;	unsigned long colour; 	/* Try to find previous block */	for (p = ind->p - 1; p >= start; p--)		if (*p)			return le32_to_cpu(*p); 	/* No such thing, so let's try location of indirect block */	if (ind->bh)		return ind->bh->b_blocknr; 	/*	 * It is going to be refered from inode itself? OK, just put it into	 * the same cylinder group then.	 */	bg_start = (ei->i_block_group * EXT2_BLOCKS_PER_GROUP(inode->i_sb)) +		le32_to_cpu(EXT2_SB(inode->i_sb)->s_es->s_first_data_block);	colour = (current->pid % 16) *			(EXT2_BLOCKS_PER_GROUP(inode->i_sb) / 16);	return bg_start + colour;} /** *	ext2_find_goal - find a prefered place for allocation. *	@inode: owner *	@block:  block we want *	@chain:  chain of indirect blocks *	@partial: pointer to the last triple within a chain *	@goal:	place to store the result. * *	Normally this function find the prefered place for block allocation, *	stores it in *@goal and returns zero. If the branch had been changed *	under us we return -EAGAIN. */ static inline int ext2_find_goal(struct inode *inode,				 long block,				 Indirect chain[4],				 Indirect *partial,				 unsigned long *goal){	struct ext2_inode_info *ei = EXT2_I(inode);	write_lock(&ei->i_meta_lock);	if ((block == ei->i_next_alloc_block + 1) && ei->i_next_alloc_goal) {		ei->i_next_alloc_block++;		ei->i_next_alloc_goal++;	} 	if (verify_chain(chain, partial)) {		/*		 * try the heuristic for sequential allocation,		 * failing that at least try to get decent locality.		 */		if (block == ei->i_next_alloc_block)			*goal = ei->i_next_alloc_goal;		if (!*goal)			*goal = ext2_find_near(inode, partial);		write_unlock(&ei->i_meta_lock);		return 0;	}	write_unlock(&ei->i_meta_lock);	return -EAGAIN;} /** *	ext2_alloc_branch - allocate and set up a chain of blocks. *	@inode: owner *	@num: depth of the chain (number of blocks to allocate) *	@offsets: offsets (in the blocks) to store the pointers to next. *	@branch: place to store the chain in. * *	This function allocates @num blocks, zeroes out all but the last one, *	links them into chain and (if we are synchronous) writes them to disk. *	In other words, it prepares a branch that can be spliced onto the *	inode. It stores the information about that chain in the branch[], in *	the same format as ext2_get_branch() would do. We are calling it after *	we had read the existing part of chain and partial points to the last *	triple of that (one with zero ->key). Upon the exit we have the same *	picture as after the successful ext2_get_block(), excpet that in one *	place chain is disconnected - *branch->p is still zero (we did not *	set the last link), but branch->key contains the number that should *	be placed into *branch->p to fill that gap. * *	If allocation fails we free all blocks we've allocated (and forget *	their buffer_heads) and return the error value the from failed *	ext2_alloc_block() (normally -ENOSPC). Otherwise we set the chain *	as described above and return 0. */ static int ext2_alloc_branch(struct inode *inode,			     int num,			     unsigned long goal,			     int *offsets,			     Indirect *branch){	int blocksize = inode->i_sb->s_blocksize;	int n = 0;	int err;	int i;	int parent = ext2_alloc_block(inode, goal, &err); 	branch[0].key = cpu_to_le32(parent);	if (parent) for (n = 1; n < num; n++) {		struct buffer_head *bh;		/* Allocate the next block */		int nr = ext2_alloc_block(inode, parent, &err);		if (!nr)			break;		branch[n].key = cpu_to_le32(nr);		/*		 * Get buffer_head for parent block, zero it out and set 		 * the pointer to new one, then send parent to disk.		 */		bh = sb_getblk(inode->i_sb, parent);		if (!bh) {			err = -EIO;			break;		}		lock_buffer(bh);		memset(bh->b_data, 0, blocksize);		branch[n].bh = bh;		branch[n].p = (__le32 *) bh->b_data + offsets[n];		*branch[n].p = branch[n].key;		set_buffer_uptodate(bh);		unlock_buffer(bh);		mark_buffer_dirty_inode(bh, inode);		/* We used to sync bh here if IS_SYNC(inode).		 * But we now rely upon generic_osync_inode()		 * and b_inode_buffers.  But not for directories.		 */		if (S_ISDIR(inode->i_mode) && IS_DIRSYNC(inode))			sync_dirty_buffer(bh);		parent = nr;	}	if (n == num)		return 0; 	/* Allocation failed, free what we already allocated */	for (i = 1; i < n; i++)		bforget(branch[i].bh);	for (i = 0; i < n; i++)		ext2_free_blocks(inode, le32_to_cpu(branch[i].key), 1);	return err;} /** *	ext2_splice_branch - splice the allocated branch onto inode. *	@inode: owner *	@block: (logical) number of block we are adding *	@chain: chain of indirect blocks (with a missing link - see *		ext2_alloc_branch) *	@where: location of missing link *	@num:   number of blocks we are adding * *	This function verifies that chain (up to the missing link) had not *	changed, fills the missing link and does all housekeeping needed in *	inode (->i_blocks, etc.). In case of success we end up with the full *	chain to new block and return 0. Otherwise (== chain had been changed) *	we free the new blocks (forgetting their buffer_heads, indeed) and *	return -EAGAIN. */ static inline int ext2_splice_branch(struct inode *inode,				     long block,				     Indirect chain[4],				     Indirect *where,				     int num){	struct ext2_inode_info *ei = EXT2_I(inode);	int i; 	/* Verify that place we are splicing to is still there and vacant */

Lines 1–500 of 1308. Load more