ext3-extents-2.6.18-vanilla.patch

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

Index: linux-2.6.18.8/fs/ext3/dir.c
===================================================================
--- linux-2.6.18.8.orig/fs/ext3/dir.c	2007-02-24 00:52:30.000000000 +0100
+++ linux-2.6.18.8/fs/ext3/dir.c	2007-07-17 09:18:14.000000000 +0200
@@ -131,8 +131,7 @@ static int ext3_readdir(struct file * fi
 		struct buffer_head *bh = NULL;
 
 		map_bh.b_state = 0;
-		err = ext3_get_blocks_handle(NULL, inode, blk, 1,
-						&map_bh, 0, 0);
+		err = ext3_get_blocks_wrap(NULL, inode, blk, 1, &map_bh, 0, 0);
 		if (err > 0) {
 			page_cache_readahead(sb->s_bdev->bd_inode->i_mapping,
 				&filp->f_ra,
Index: linux-2.6.18.8/fs/ext3/extents.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.18.8/fs/ext3/extents.c	2007-07-17 11:08:59.000000000 +0200
@@ -0,0 +1,2272 @@
+/*
+ * Copyright (c) 2003-2006, Cluster File Systems, Inc, [e-mail]
+ * Written by Alex Tomas <[e-mail]>
+ *
+ * Architecture independence:
+ *   Copyright (c) 2005, Bull S.A.
+ *   Written by Pierre Peiffer <[e-mail]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public Licens
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
+ */
+
+/*
+ * Extents support for EXT3
+ *
+ * TODO:
+ *   - ext3*_error() should be used in some situations
+ *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
+ *   - smart tree reduction
+ */
+
+#include <linux/module.h>
+#include <linux/fs.h>
+#include <linux/time.h>
+#include <linux/ext3_jbd.h>
+#include <linux/jbd.h>
+#include <linux/smp_lock.h>
+#include <linux/highuid.h>
+#include <linux/pagemap.h>
+#include <linux/quotaops.h>
+#include <linux/string.h>
+#include <linux/slab.h>
+#include <linux/ext3_extents.h>
+#include <asm/uaccess.h>
+
+
+static handle_t *ext3_ext_journal_restart(handle_t *handle, int needed)
+{
+	int err;
+
+	if (handle->h_buffer_credits > needed)
+		return handle;
+	if (!ext3_journal_extend(handle, needed))
+		return handle;
+	err = ext3_journal_restart(handle, needed);
+
+	return handle;
+}
+
+/*
+ * could return:
+ *  - EROFS
+ *  - ENOMEM
+ */
+static int ext3_ext_get_access(handle_t *handle, struct inode *inode,
+				struct ext3_ext_path *path)
+{
+	if (path->p_bh) {
+		/* path points to block */
+		return ext3_journal_get_write_access(handle, path->p_bh);
+	}
+	/* path points to leaf/index in inode body */
+	/* we use in-core data, no need to protect them */
+	return 0;
+}
+
+/*
+ * could return:
+ *  - EROFS
+ *  - ENOMEM
+ *  - EIO
+ */
+static int ext3_ext_dirty(handle_t *handle, struct inode *inode,
+				struct ext3_ext_path *path)
+{
+	int err;
+	if (path->p_bh) {
+		/* path points to block */
+		err = ext3_journal_dirty_metadata(handle, path->p_bh);
+	} else {
+		/* path points to leaf/index in inode body */
+		err = ext3_mark_inode_dirty(handle, inode);
+	}
+	return err;
+}
+
+static int ext3_ext_find_goal(struct inode *inode,
+			      struct ext3_ext_path *path,
+			      unsigned long block)
+{
+	struct ext3_inode_info *ei = EXT3_I(inode);
+	unsigned long bg_start;
+	unsigned long colour;
+	int depth;
+
+	if (path) {
+		struct ext3_extent *ex;
+		depth = path->p_depth;
+
+		/* try to predict block placement */
+		if ((ex = path[depth].p_ext))
+			return le32_to_cpu(ex->ee_start)
+					+ (block - le32_to_cpu(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_ext_new_block(handle_t *handle, struct inode *inode,
+			struct ext3_ext_path *path,
+			struct ext3_extent *ex, int *err)
+{
+	int goal, newblock;
+
+	goal = ext3_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
+	newblock = ext3_new_block(handle, inode, goal, err);
+	return newblock;
+}
+
+static inline int ext3_ext_space_block(struct inode *inode)
+{
+	int size;
+
+	size = (inode->i_sb->s_blocksize - sizeof(struct ext3_extent_header))
+			/ sizeof(struct ext3_extent);
+#ifdef AGRESSIVE_TEST
+	if (size > 6)
+		size = 6;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_block_idx(struct inode *inode)
+{
+	int size;
+
+	size = (inode->i_sb->s_blocksize - sizeof(struct ext3_extent_header))
+			/ sizeof(struct ext3_extent_idx);
+#ifdef AGRESSIVE_TEST
+	if (size > 5)
+		size = 5;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_root(struct inode *inode)
+{
+	int size;
+
+	size = sizeof(EXT3_I(inode)->i_data);
+	size -= sizeof(struct ext3_extent_header);
+	size /= sizeof(struct ext3_extent);
+#ifdef AGRESSIVE_TEST
+	if (size > 3)
+		size = 3;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_root_idx(struct inode *inode)
+{
+	int size;
+
+	size = sizeof(EXT3_I(inode)->i_data);
+	size -= sizeof(struct ext3_extent_header);
+	size /= sizeof(struct ext3_extent_idx);
+#ifdef AGRESSIVE_TEST
+	if (size > 4)
+		size = 4;
+#endif
+	return size;
+}
+
+static inline int
+ext3_ext_max_entries(struct inode *inode, int depth)
+{
+	int max;
+
+	if (depth == ext_depth(inode)) {
+		if (depth == 0)
+			max = ext3_ext_space_root(inode);
+		else
+			max = ext3_ext_space_root_idx(inode);
+	} else {
+		if (depth == 0)
+			max = ext3_ext_space_block(inode);
+		else
+			max = ext3_ext_space_block_idx(inode);
+	}
+
+	return max;
+}
+
+static int __ext3_ext_check_header(const char *function, struct inode *inode,
+					struct ext3_extent_header *eh,
+					int depth)
+{
+	const char *error_msg = NULL;
+	int max = 0;
+
+	if (unlikely(eh->eh_magic != cpu_to_le16(EXT3_EXT_MAGIC))) {
+		error_msg = "invalid magic";
+		goto corrupted;
+	}
+	if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
+		error_msg = "unexpected eh_depth";
+		goto corrupted;
+	}
+	if (unlikely(eh->eh_max == 0)) {
+		error_msg = "invalid eh_max";
+		goto corrupted;
+	}
+	max = ext3_ext_max_entries(inode, depth);
+#ifdef AGRESSIVE_TEST
+	if (eh->eh_max > 3) {
+		/* inode probably got extent without defining AGRESSIVE_TEST */
+		max = eh->eh_max;
+	}
+#endif
+	if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
+		error_msg = "too large eh_max";
+		goto corrupted;
+	}
+	if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
+		error_msg = "invalid eh_entries";
+		goto corrupted;
+	}
+	return 0;
+
+corrupted:
+	ext3_error(inode->i_sb, function,
+			"bad header in inode #%lu: %s - magic %x, "
+			"entries %u, max %u(%u), depth %u(%u)",
+			inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic),
+			le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
+			max, le16_to_cpu(eh->eh_depth), depth);
+
+	return -EIO;
+}
+
+#define ext3_ext_check_header(inode,eh,depth)	\
+	__ext3_ext_check_header(__FUNCTION__,inode,eh,depth)
+
+#ifdef EXT_DEBUG
+static void ext3_ext_show_path(struct inode *inode, struct ext3_ext_path *path)
+{
+	int k, l = path->p_depth;
+
+	ext_debug(inode, "path:");
+	for (k = 0; k <= l; k++, path++) {
+		if (path->p_idx) {
+		  ext_debug(inode, "  %d->%d", le32_to_cpu(path->p_idx->ei_block),
+			    le32_to_cpu(path->p_idx->ei_leaf));
+		} else if (path->p_ext) {
+			ext_debug(inode, "  %d:%d:%d",
+				  le32_to_cpu(path->p_ext->ee_block),
+				  le16_to_cpu(path->p_ext->ee_len),
+				  le32_to_cpu(path->p_ext->ee_start));
+		} else
+			ext_debug(inode, "  []");
+	}
+	ext_debug(inode, "\n");
+}
+
+static void ext3_ext_show_leaf(struct inode *inode, struct ext3_ext_path *path)
+{
+	int depth = ext_depth(inode);
+	struct ext3_extent_header *eh;
+	struct ext3_extent *ex;
+	int i;
+
+	if (!path)
+		return;
+
+	eh = path[depth].p_hdr;
+	ex = EXT_FIRST_EXTENT(eh);
+
+	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
+		ext_debug(inode, "%d:%d:%d ", le32_to_cpu(ex->ee_block),
+			  le16_to_cpu(ex->ee_len),
+			  le32_to_cpu(ex->ee_start));
+	}
+	ext_debug(inode, "\n");
+}
+#else
+#define ext3_ext_show_path(inode,path)
+#define ext3_ext_show_leaf(inode,path)
+#endif
+
+static void ext3_ext_drop_refs(struct ext3_ext_path *path)
+{
+	int depth = path->p_depth;
+	int i;
+
+	for (i = 0; i <= depth; i++, path++)
+		if (path->p_bh) {
+			brelse(path->p_bh);
+			path->p_bh = NULL;
+		}
+}
+
+/*
+ * binary search for closest index by given block
+ * the header must be checked before calling this
+ */
+static void
+ext3_ext_binsearch_idx(struct inode *inode, struct ext3_ext_path *path, int block)
+{
+	struct ext3_extent_header *eh = path->p_hdr;
+	struct ext3_extent_idx *r, *l, *m;
+
+	ext_debug(inode, "binsearch for %d(idx):  ", block);
+
+	l = EXT_FIRST_INDEX(eh) + 1;
+	r = EXT_FIRST_INDEX(eh) + le16_to_cpu(eh->eh_entries) - 1;
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		if (block < le32_to_cpu(m->ei_block))
+			r = m - 1;
+		else
+			l = m + 1;
+		ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l, l->ei_block,
+				m, m->ei_block, r, r->ei_block);
+	}
+
+	path->p_idx = l - 1;
+	ext_debug(inode, "  -> %d->%d ", le32_to_cpu(path->p_idx->ei_block),
+		  le32_to_cpu(path->p_idx->ei_leaf));
+
+#ifdef CHECK_BINSEARCH
+	{
+		struct ext3_extent_idx *chix, *ix;
+		int k;
+
+		chix = ix = EXT_FIRST_INDEX(eh);
+		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
+		  if (k != 0 &&
+		      le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
+				printk("k=%d, ix=0x%p, first=0x%p\n", k,
+					ix, EXT_FIRST_INDEX(eh));
+				printk("%u <= %u\n",
+				       le32_to_cpu(ix->ei_block),
+				       le32_to_cpu(ix[-1].ei_block));
+			}
+			BUG_ON(k && le32_to_cpu(ix->ei_block)
+				           <= le32_to_cpu(ix[-1].ei_block));
+			if (block < le32_to_cpu(ix->ei_block))
+				break;
+			chix = ix;
+		}
+		BUG_ON(chix != path->p_idx);
+	}
+#endif
+
+}
+
+/*
+ * binary search for closest extent by given block
+ * the header must be checked before calling this
+ */
+static void
+ext3_ext_binsearch(struct inode *inode, struct ext3_ext_path *path, int block)
+{
+	struct ext3_extent_header *eh = path->p_hdr;
+	struct ext3_extent *r, *l, *m;
+
+	if (eh->eh_entries == 0) {
+		/*
+		 * this leaf is empty yet:
+		 *  we get such a leaf in split/add case
+		 */
+		return;
+	}
+
+	ext_debug(inode, "binsearch for %d:  ", block);
+
+	l = EXT_FIRST_EXTENT(eh) + 1;
+	r = EXT_FIRST_EXTENT(eh) + le16_to_cpu(eh->eh_entries) - 1;
+
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		if (block < le32_to_cpu(m->ee_block))
+			r = m - 1;
+		else
+			l = m + 1;
+		ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l, l->ee_block,
+				m, m->ee_block, r, r->ee_block);
+	}
+
+	path->p_ext = l - 1;
+	ext_debug(inode, "  -> %d:%d:%d ",
+		        le32_to_cpu(path->p_ext->ee_block),
+		        le32_to_cpu(path->p_ext->ee_start),
+		        le16_to_cpu(path->p_ext->ee_len));
+
+#ifdef CHECK_BINSEARCH
+	{
+		struct ext3_extent *chex, *ex;
+		int k;
+
+		chex = ex = EXT_FIRST_EXTENT(eh);
+		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
+			BUG_ON(k && le32_to_cpu(ex->ee_block)
+				          <= le32_to_cpu(ex[-1].ee_block));
+			if (block < le32_to_cpu(ex->ee_block))
+				break;
+			chex = ex;
+		}
+		BUG_ON(chex != path->p_ext);
+	}
+#endif
+
+}
+
+int ext3_ext_tree_init(handle_t *handle, struct inode *inode)
+{
+	struct ext3_extent_header *eh;
+
+	eh = ext_inode_hdr(inode);
+	eh->eh_depth = 0;
+	eh->eh_entries = 0;
+	eh->eh_magic = cpu_to_le16(EXT3_EXT_MAGIC);
+	eh->eh_max = cpu_to_le16(ext3_ext_space_root(inode));
+	ext3_mark_inode_dirty(handle, inode);
+	ext3_ext_invalidate_cache(inode);
+	return 0;
+}
+
+struct ext3_ext_path *
+ext3_ext_find_extent(struct inode *inode, int block, struct ext3_ext_path *path)
+{