ext3-extents-2.6.15.patch

非常经典的一个分布式系统

+	
+	if (path) {
+		struct ext3_extent *ex;
+		depth = path->p_depth;
+		
+		/* try to predict block placement */
+		if ((ex = path[depth].p_ext))
+			return ex->ee_start + (block - ex->ee_block);
+
+		/* it looks index is empty
+		 * try to find starting from index itself */
+		if (path[depth].p_bh)
+			return path[depth].p_bh->b_blocknr;
+	}
+
+	/* OK. use inode's group */
+	bg_start = (ei->i_block_group * EXT3_BLOCKS_PER_GROUP(inode->i_sb)) +
+		le32_to_cpu(EXT3_SB(inode->i_sb)->s_es->s_first_data_block);
+	colour = (current->pid % 16) *
+			(EXT3_BLOCKS_PER_GROUP(inode->i_sb) / 16);
+	return bg_start + colour + block;
+}
+
+static int ext3_new_block_cb(handle_t *handle, struct ext3_extents_tree *tree,
+			     struct ext3_ext_path *path,
+			     struct ext3_extent *ex, int *err)
+{
+	struct inode *inode = tree->inode;
+	int newblock, goal;
+	
+	EXT_ASSERT(path);
+	EXT_ASSERT(ex);
+	EXT_ASSERT(ex->ee_start);
+	EXT_ASSERT(ex->ee_len);
+	
+	/* reuse block from the extent to order data/metadata */
+	newblock = ex->ee_start++;
+	ex->ee_len--;
+	if (ex->ee_len == 0) {
+		ex->ee_len = 1;
+		/* allocate new block for the extent */
+		goal = ext3_ext_find_goal(inode, path, ex->ee_block);
+		ex->ee_start = ext3_new_block(handle, inode, goal, err);
+		ex->ee_start_hi = 0;
+		if (ex->ee_start == 0) {
+			/* error occured: restore old extent */
+			ex->ee_start = newblock;
+			return 0;
+		}
+	}
+	return newblock;
+}
+
+static struct ext3_extents_helpers ext3_blockmap_helpers = {
+	.get_write_access	= ext3_get_inode_write_access,
+	.mark_buffer_dirty	= ext3_mark_buffer_dirty,
+	.mergable		= ext3_ext_mergable,
+	.new_block		= ext3_new_block_cb,
+	.remove_extent		= ext3_remove_blocks,
+	.remove_extent_credits	= ext3_remove_blocks_credits,
+};
+
+void ext3_init_tree_desc(struct ext3_extents_tree *tree,
+			 struct inode *inode)
+{
+	tree->inode = inode;
+	tree->root = (void *) EXT3_I(inode)->i_data;
+	tree->buffer = (void *) inode;
+	tree->buffer_len = sizeof(EXT3_I(inode)->i_data);
+	tree->cex = (struct ext3_ext_cache *) &EXT3_I(inode)->i_cached_extent;
+	tree->ops = &ext3_blockmap_helpers;
+}
+
+int ext3_ext_get_block(handle_t *handle, struct inode *inode,
+		       long iblock, struct buffer_head *bh_result,
+		       int create, int extend_disksize)
+{
+	struct ext3_ext_path *path = NULL;
+	struct ext3_extent newex;
+	struct ext3_extent *ex;
+	int goal, newblock, err = 0, depth;
+	struct ext3_extents_tree tree;
+
+	clear_buffer_new(bh_result);
+	ext3_init_tree_desc(&tree, inode);
+	ext_debug(&tree, "block %d requested for inode %u\n",
+		  (int) iblock, (unsigned) inode->i_ino);
+	down(&EXT3_I(inode)->truncate_sem);
+
+	/* check in cache */
+	if ((goal = ext3_ext_in_cache(&tree, iblock, &newex))) {
+		if (goal == EXT3_EXT_CACHE_GAP) {
+			if (!create) {
+				/* block isn't allocated yet and
+				 * user don't want to allocate it */
+				goto out2;
+			}
+			/* we should allocate requested block */
+		} else if (goal == EXT3_EXT_CACHE_EXTENT) {
+			/* block is already allocated */
+			newblock = iblock - newex.ee_block + newex.ee_start;
+			goto out;
+		} else {
+			EXT_ASSERT(0);
+		}
+	}
+
+	/* find extent for this block */
+	path = ext3_ext_find_extent(&tree, iblock, NULL);
+	if (IS_ERR(path)) {
+		err = PTR_ERR(path);
+		path = NULL;
+		goto out2;
+	}
+
+	depth = EXT_DEPTH(&tree);
+
+	/*
+	 * consistent leaf must not be empty
+	 * this situations is possible, though, _during_ tree modification
+	 * this is why assert can't be put in ext3_ext_find_extent()
+	 */
+	EXT_ASSERT(path[depth].p_ext != NULL || depth == 0);
+
+	if ((ex = path[depth].p_ext)) {
+		/* if found exent covers block, simple return it */
+		if (iblock >= ex->ee_block && iblock < ex->ee_block + ex->ee_len) {
+			newblock = iblock - ex->ee_block + ex->ee_start;
+			ext_debug(&tree, "%d fit into %d:%d -> %d\n",
+				  (int) iblock, ex->ee_block, ex->ee_len,
+				  newblock);
+			ext3_ext_put_in_cache(&tree, ex->ee_block,
+					      ex->ee_len, ex->ee_start,
+					      EXT3_EXT_CACHE_EXTENT);
+			goto out;
+		}
+	}
+
+	/*
+	 * requested block isn't allocated yet
+	 * we couldn't try to create block if create flag is zero 
+	 */
+	if (!create) {
+		/* put just found gap into cache to speedup subsequest reqs */
+		ext3_ext_put_gap_in_cache(&tree, path, iblock);
+		goto out2;
+	}
+
+	/* allocate new block */
+	goal = ext3_ext_find_goal(inode, path, iblock);
+	newblock = ext3_new_block(handle, inode, goal, &err);
+	if (!newblock)
+		goto out2;
+	ext_debug(&tree, "allocate new block: goal %d, found %d\n",
+		  goal, newblock);
+
+	/* try to insert new extent into found leaf and return */
+	newex.ee_block = iblock;
+	newex.ee_start = newblock;
+	newex.ee_start_hi = 0;
+	newex.ee_len = 1;
+	err = ext3_ext_insert_extent(handle, &tree, path, &newex);
+	if (err)
+		goto out2;
+	
+	if (extend_disksize && inode->i_size > EXT3_I(inode)->i_disksize)
+		EXT3_I(inode)->i_disksize = inode->i_size;
+
+	/* previous routine could use block we allocated */
+	newblock = newex.ee_start;
+	set_buffer_new(bh_result);
+
+	ext3_ext_put_in_cache(&tree, newex.ee_block, newex.ee_len,
+			      newex.ee_start, EXT3_EXT_CACHE_EXTENT);
+out:
+	ext3_ext_show_leaf(&tree, path);
+	map_bh(bh_result, inode->i_sb, newblock);
+out2:
+	if (path) {
+		ext3_ext_drop_refs(path);
+		kfree(path);
+	}
+	up(&EXT3_I(inode)->truncate_sem);
+
+	return err;	
+}
+
+void ext3_ext_truncate(struct inode * inode, struct page *page)
+{
+	struct address_space *mapping = inode->i_mapping;
+	struct super_block *sb = inode->i_sb;
+	struct ext3_extents_tree tree;
+	unsigned long last_block;
+	handle_t *handle;
+	int err = 0;
+
+	ext3_init_tree_desc(&tree, inode);
+
+	/*
+	 * probably first extent we're gonna free will be last in block
+	 */
+	err = ext3_writepage_trans_blocks(inode) + 3;
+	handle = ext3_journal_start(inode, err);
+	if (IS_ERR(handle)) {
+		if (page) {
+			clear_highpage(page);
+			flush_dcache_page(page);
+			unlock_page(page);
+			page_cache_release(page);
+		}
+		return;
+	}
+
+	if (page)
+		ext3_block_truncate_page(handle, page, mapping, inode->i_size);
+
+	down(&EXT3_I(inode)->truncate_sem);
+	ext3_ext_invalidate_cache(&tree);
+
+	/* 
+	 * TODO: optimization is possible here
+	 * probably we need not scaning at all,
+	 * because page truncation is enough
+	 */
+	if (ext3_orphan_add(handle, inode))
+		goto out_stop;
+
+	/* we have to know where to truncate from in crash case */
+	EXT3_I(inode)->i_disksize = inode->i_size;
+	ext3_mark_inode_dirty(handle, inode);
+
+	last_block = (inode->i_size + sb->s_blocksize - 1) >>
+			EXT3_BLOCK_SIZE_BITS(sb);
+	err = ext3_ext_remove_space(&tree, last_block, EXT_MAX_BLOCK);
+	
+	/* In a multi-transaction truncate, we only make the final
+	 * transaction synchronous */
+	if (IS_SYNC(inode))
+		handle->h_sync = 1;
+
+out_stop:
+	/*
+	 * If this was a simple ftruncate(), and the file will remain alive
+	 * then we need to clear up the orphan record which we created above.
+	 * However, if this was a real unlink then we were called by
+	 * ext3_delete_inode(), and we allow that function to clean up the
+	 * orphan info for us.
+	 */
+	if (inode->i_nlink)
+		ext3_orphan_del(handle, inode);
+
+	up(&EXT3_I(inode)->truncate_sem);
+	ext3_journal_stop(handle);
+}
+
+/*
+ * this routine calculate max number of blocks we could modify
+ * in order to allocate new block for an inode
+ */
+int ext3_ext_writepage_trans_blocks(struct inode *inode, int num)
+{
+	struct ext3_extents_tree tree;
+	int needed;
+	
+	ext3_init_tree_desc(&tree, inode);
+	
+	needed = ext3_ext_calc_credits_for_insert(&tree, NULL);
+
+	/* caller want to allocate num blocks */
+	needed *= num;
+	
+#ifdef CONFIG_QUOTA
+	/* 
+	 * FIXME: real calculation should be here
+	 * it depends on blockmap format of qouta file
+	 */
+	needed += 2 * EXT3_SINGLEDATA_TRANS_BLOCKS;
+#endif
+
+	return needed;
+}
+
+void ext3_extents_initialize_blockmap(handle_t *handle, struct inode *inode)
+{
+	struct ext3_extents_tree tree;
+
+	ext3_init_tree_desc(&tree, inode);
+	ext3_extent_tree_init(handle, &tree);
+}
+
+int ext3_ext_calc_blockmap_metadata(struct inode *inode, int blocks)
+{
+	struct ext3_extents_tree tree;
+
+	ext3_init_tree_desc(&tree, inode);
+	return ext3_ext_calc_metadata_amount(&tree, blocks);
+}
+	
+static int
+ext3_ext_store_extent_cb(struct ext3_extents_tree *tree,
+			 struct ext3_ext_path *path,
+			 struct ext3_ext_cache *newex)
+{
+	struct ext3_extent_buf *buf = (struct ext3_extent_buf *) tree->private;
+
+	if (newex->ec_type != EXT3_EXT_CACHE_EXTENT)
+		return EXT_CONTINUE;
+
+	if (buf->err < 0)
+		return EXT_BREAK;
+	if (buf->cur - buf->buffer + sizeof(*newex) > buf->buflen)
+		return EXT_BREAK;
+
+	if (!copy_to_user(buf->cur, newex, sizeof(*newex))) {
+		buf->err++;
+		buf->cur += sizeof(*newex);
+	} else {
+		buf->err = -EFAULT;
+		return EXT_BREAK;
+	}
+	return EXT_CONTINUE;
+}
+
+static int
+ext3_ext_collect_stats_cb(struct ext3_extents_tree *tree,
+			  struct ext3_ext_path *path,
+			  struct ext3_ext_cache *ex)
+{
+	struct ext3_extent_tree_stats *buf =
+		(struct ext3_extent_tree_stats *) tree->private;
+	int depth;
+
+	if (ex->ec_type != EXT3_EXT_CACHE_EXTENT)
+		return EXT_CONTINUE;
+
+	depth = EXT_DEPTH(tree);
+	buf->extents_num++;
+	if (path[depth].p_ext == EXT_FIRST_EXTENT(path[depth].p_hdr))
+		buf->leaf_num++;
+	return EXT_CONTINUE;
+}
+
+int ext3_ext_ioctl(struct inode *inode, struct file *filp, unsigned int cmd,
+		   unsigned long arg)
+{
+	int err = 0;
+
+	if (!(EXT3_I(inode)->i_flags & EXT3_EXTENTS_FL))
+		return -EINVAL;
+
+	if (cmd == EXT3_IOC_GET_EXTENTS) {
+		struct ext3_extent_buf buf;
+		struct ext3_extents_tree tree;
+
+		if (copy_from_user(&buf, (void *) arg, sizeof(buf)))
+			return -EFAULT;
+
+		ext3_init_tree_desc(&tree, inode);
+		buf.cur = buf.buffer;
+		buf.err = 0;
+		tree.private = &buf;
+		down(&EXT3_I(inode)->truncate_sem);
+		err = ext3_ext_walk_space(&tree, buf.start, EXT_MAX_BLOCK,
+					  ext3_ext_store_extent_cb);
+		up(&EXT3_I(inode)->truncate_sem);
+		if (err == 0)
+			err = buf.err;
+	} else if (cmd == EXT3_IOC_GET_TREE_STATS) {
+		struct ext3_extent_tree_stats buf;
+		struct ext3_extents_tree tree;
+
+		ext3_init_tree_desc(&tree, inode);
+		down(&EXT3_I(inode)->truncate_sem);
+		buf.depth = EXT_DEPTH(&tree);
+		buf.extents_num = 0;
+		buf.leaf_num = 0;
+		tree.private = &buf;
+		err = ext3_ext_walk_space(&tree, 0, EXT_MAX_BLOCK,
+					  ext3_ext_collect_stats_cb);
+		up(&EXT3_I(inode)->truncate_sem);
+		if (!err)
+			err = copy_to_user((void *) arg, &buf, sizeof(buf));
+	} else if (cmd == EXT3_IOC_GET_TREE_DEPTH) {
+		struct ext3_extents_tree tree;
+		ext3_init_tree_desc(&tree, inode);
+		down(&EXT3_I(inode)->truncate_sem);
+		err = EXT_DEPTH(&tree);
+		up(&EXT3_I(inode)->truncate_sem);
+	}
+
+	return err;
+}
+
+EXPORT_SYMBOL(ext3_init_tree_desc);
+EXPORT_SYMBOL(ext3_mark_inode_dirty);
+EXPORT_SYMBOL(ext3_ext_invalidate_cache);
+EXPORT_SYMBOL(ext3_ext_insert_extent);
+EXPORT_SYMBOL(ext3_ext_walk_space);
+EXPORT_SYMBOL(ext3_ext_find_goal);
+EXPORT_SYMBOL(ext3_ext_calc_credits_for_insert);
Index: linux-2.6.16.21-0.8/fs/ext3/ialloc.c
===================================================================
--- linux-2.6.16.21-0.8.orig/fs/ext3/ialloc.c
+++ linux-2.6.16.21-0.8/fs/ext3/ialloc.c
@@ -598,7 +598,7 @@ got:
 	ei->i_dir_start_lookup = 0;
 	ei->i_disksize = 0;
 
-	ei->i_flags = EXT3_I(dir)->i_flags & ~EXT3_INDEX_FL;
+	ei->i_flags = EXT3_I(dir)->i_flags & ~(EXT3_INDEX_FL|EXT3_EXTENTS_FL);
 	if (S_ISLNK(mode))
 		ei->i_flags &= ~(EXT3_IMMUTABLE_FL|EXT3_APPEND_FL);
 	/* dirsync only applies to directories */
@@ -642,6 +642,18 @@ got:
 	if (err)
 		goto fail_free_drop;
 
+	if (test_opt(sb, EXTENTS) && S_ISREG(inode->i_mode)) {
+		EXT3_I(inode)->i_flags |= EXT3_EXTENTS_FL;
+		ext3_extents_initialize_blockmap(handle, inode);
+		if (!EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_EXTENTS)) {
+			err = ext3_journal_get_write_access(handle, EXT3_SB(sb)->s_sbh);
+			if (err) goto fail;
+			EXT3_SET_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_EXTENTS);
+			BUFFER_TRACE(EXT3_SB(sb)->s_sbh, "call ext3_journal_dirty_metadata");
+			err = ext3_journal_dirty_metadata(handle, EXT3_SB(sb)->s_sbh);
+		}
+	}
+
 	err = ext3_mark_inode_dirty(handle, inode);
 	if (err) {
 		ext3_std_error(sb, err);
Index: linux-2.6.16.21-0.8/fs/ext3/inode.c
===================================================================
--- linux-2.6.16.21-0.8.orig/fs/ext3/inode.c
+++ linux-2.6.16.21-0.8/fs/ext3/inode.c
@@ -40,7 +40,7 @@
 #include "iopen.h"
 #include "acl.h"
 
-static int ext3_writepage_trans_blocks(struct inode *inode);
+int ext3_writepage_trans_blocks(struct inode *inode);
 
 /*
  * Test whether an inode is a fast symlink.
@@ -788,6 +788,17 @@ out:
 	return err;
 }
 
+static inline int
+ext3_get_block_wrap(handle_t *handle, struct inode *inode, long block,
+		    struct buffer_head *bh, int create, int extend_disksize)
+{
+	if (EXT3_I(inode)->i_flags & EXT3_EXTENTS_FL)
+		return ext3_ext_get_block(handle, inode, block, bh, create,
+					  extend_disksize);
+	return ext3_get_block_handle(handle, inode, block, bh, create,
+				     extend_disksize);
+}
+
 static int ext3_get_block(struct inode *inode, sector_t iblock,
 			struct buffer_head *bh_result, int create)
 {
@@ -798,8 +809,8 @@ static int ext3_get_block(struct inode *
 		handle = ext3_journal_current_handle();
 		J_ASSERT(handle != 0);
 	}
-	ret = ext3_get_block_handle(handle, inode, iblock,
-				bh_result, create, 1);
+	ret = ext3_get_block_wrap(handle, inode, iblock,
+				  bh_result, create, 1);
 	return ret;
 }
 
@@ -843,7 +854,7 @@ ext3_direct_io_get_blocks(struct inode *
 
 get_block:
 	if (ret == 0)
-		ret = ext3_get_block_handle(handle, inode, iblock,
+		ret = ext3_get_block_wrap(handle, inode, iblock,
 					bh_result, create, 0);
 	bh_result->b_size = (1 << inode->i_blkbits);
 	return ret;
@@ -863,7 +874,7 @@ struct buffer_head *ext3_getblk(handle_t
 	dummy.b_state = 0;
 	dummy.b_blocknr = -1000;
 	buffer_trace_init(&dummy.b_history);
-	*errp = ext3_get_block_handle(handle, inode, block, &dummy, create, 1);
+	*e