ext3-extents-2.6.15.patch

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

Index: linux-2.6.16.21-0.8/fs/ext3/extents.c
===================================================================
--- /dev/null
+++ linux-2.6.16.21-0.8/fs/ext3/extents.c
@@ -0,0 +1,2359 @@
+/*
+ * Copyright(c) 2003, 2004, 2005, Cluster File Systems, Inc, [e-mail]
+ * Written by Alex Tomas <[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_ext_walk_space() sould not use ext3_ext_find_extent()
+ *   - ext3_ext_calc_credits() could take 'mergable' into account
+ *   - ext3*_error() should be used in some situations
+ *   - find_goal() [to be tested and improved]
+ *   - smart tree reduction
+ *   - arch-independence
+ *     common on-disk format for big/little-endian arch
+ */
+
+#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 inline int ext3_ext_check_header(struct ext3_extent_header *eh)
+{
+	if (eh->eh_magic != EXT3_EXT_MAGIC) {
+		printk(KERN_ERR "EXT3-fs: invalid magic = 0x%x\n",
+		       (unsigned)eh->eh_magic);
+		return -EIO;
+	}
+	if (eh->eh_max == 0) {
+		printk(KERN_ERR "EXT3-fs: invalid eh_max = %u\n",
+		       (unsigned)eh->eh_max);
+		return -EIO;
+	}
+	if (eh->eh_entries > eh->eh_max) {
+		printk(KERN_ERR "EXT3-fs: invalid eh_entries = %u\n",
+		       (unsigned)eh->eh_entries);
+		return -EIO;
+	}
+	return 0;
+}
+
+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;
+}
+
+static int inline
+ext3_ext_get_access_for_root(handle_t *h, struct ext3_extents_tree *tree)
+{
+	if (tree->ops->get_write_access)
+		return tree->ops->get_write_access(h,tree->buffer);
+	else
+		return 0;
+}
+
+static int inline
+ext3_ext_mark_root_dirty(handle_t *h, struct ext3_extents_tree *tree)
+{
+	if (tree->ops->mark_buffer_dirty)
+		return tree->ops->mark_buffer_dirty(h,tree->buffer);
+	else
+		return 0;
+}
+
+/*
+ * could return:
+ *  - EROFS
+ *  - ENOMEM
+ */
+static int ext3_ext_get_access(handle_t *handle,
+			       struct ext3_extents_tree *tree,
+			       struct ext3_ext_path *path)
+{
+	int err;
+
+	if (path->p_bh) {
+		/* path points to block */
+		err = ext3_journal_get_write_access(handle, path->p_bh);
+	} else {
+		/* path points to leaf/index in inode body */
+		err = ext3_ext_get_access_for_root(handle, tree);
+	}
+	return err;
+}
+
+/*
+ * could return:
+ *  - EROFS
+ *  - ENOMEM
+ *  - EIO
+ */
+static int ext3_ext_dirty(handle_t *handle, struct ext3_extents_tree *tree,
+			  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_ext_mark_root_dirty(handle, tree);
+	}
+	return err;
+}
+
+static int inline
+ext3_ext_new_block(handle_t *handle, struct ext3_extents_tree *tree,
+		   struct ext3_ext_path *path, struct ext3_extent *ex,
+		   int *err)
+{
+	int goal, depth, newblock;
+	struct inode *inode;
+
+	EXT_ASSERT(tree);
+	if (tree->ops->new_block)
+		return tree->ops->new_block(handle, tree, path, ex, err);
+
+	inode = tree->inode;
+	depth = EXT_DEPTH(tree);
+	if (path && depth > 0) {
+		goal = path[depth-1].p_block;
+	} else {
+		struct ext3_inode_info *ei = EXT3_I(inode);
+		unsigned long bg_start;
+		unsigned long colour;
+
+		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);
+		goal = bg_start + colour;
+	}
+
+	newblock = ext3_new_block(handle, inode, goal, err);
+	return newblock;
+}
+
+static inline void ext3_ext_tree_changed(struct ext3_extents_tree *tree)
+{
+	struct ext3_extent_header *neh = EXT_ROOT_HDR(tree);
+	neh->eh_generation = ((EXT_FLAGS(neh) & ~EXT_FLAGS_CLR_UNKNOWN) << 24) |
+			     (EXT_HDR_GEN(neh) + 1);
+}
+
+static inline int ext3_ext_space_block(struct ext3_extents_tree *tree)
+{
+	int size;
+
+	size = (tree->inode->i_sb->s_blocksize -
+		sizeof(struct ext3_extent_header)) /
+				sizeof(struct ext3_extent);
+#ifdef AGRESSIVE_TEST
+	size = 6;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_block_idx(struct ext3_extents_tree *tree)
+{
+	int size;
+
+	size = (tree->inode->i_sb->s_blocksize -
+		sizeof(struct ext3_extent_header)) /
+				sizeof(struct ext3_extent_idx);
+#ifdef AGRESSIVE_TEST
+	size = 5;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_root(struct ext3_extents_tree *tree)
+{
+	int size;
+
+	size = (tree->buffer_len - sizeof(struct ext3_extent_header)) /
+			sizeof(struct ext3_extent);
+#ifdef AGRESSIVE_TEST
+	size = 3;
+#endif
+	return size;
+}
+
+static inline int ext3_ext_space_root_idx(struct ext3_extents_tree *tree)
+{
+	int size;
+
+	size = (tree->buffer_len - sizeof(struct ext3_extent_header)) /
+			sizeof(struct ext3_extent_idx);
+#ifdef AGRESSIVE_TEST
+	size = 4;
+#endif
+	return size;
+}
+
+static void ext3_ext_show_path(struct ext3_extents_tree *tree,
+			       struct ext3_ext_path *path)
+{
+#ifdef EXT_DEBUG
+	int k, l = path->p_depth;
+
+	ext_debug(tree, "path:");
+	for (k = 0; k <= l; k++, path++) {
+		if (path->p_idx) {
+			ext_debug(tree, "  %d->%d", path->p_idx->ei_block,
+				  path->p_idx->ei_leaf);
+		} else if (path->p_ext) {
+			ext_debug(tree, "  %d:%d:%d",
+				  path->p_ext->ee_block,
+				  path->p_ext->ee_len,
+				  path->p_ext->ee_start);
+		} else
+			ext_debug(tree, "  []");
+	}
+	ext_debug(tree, "\n");
+#endif
+}
+
+static void ext3_ext_show_leaf(struct ext3_extents_tree *tree,
+			       struct ext3_ext_path *path)
+{
+#ifdef EXT_DEBUG
+	int depth = EXT_DEPTH(tree);
+	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 < eh->eh_entries; i++, ex++) {
+		ext_debug(tree, "%d:%d:%d ",
+			  ex->ee_block, ex->ee_len, ex->ee_start);
+	}
+	ext_debug(tree, "\n");
+#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
+ */
+static inline void
+ext3_ext_binsearch_idx(struct ext3_extents_tree *tree,
+		       struct ext3_ext_path *path, int block)
+{
+	struct ext3_extent_header *eh = path->p_hdr;
+	struct ext3_extent_idx *ix;
+	int l = 0, k, r;
+
+	EXT_ASSERT(eh->eh_magic == EXT3_EXT_MAGIC);
+	EXT_ASSERT(eh->eh_entries <= eh->eh_max);
+	EXT_ASSERT(eh->eh_entries > 0);
+
+	ext_debug(tree, "binsearch for %d(idx):  ", block);
+
+	path->p_idx = ix = EXT_FIRST_INDEX(eh);
+
+	r = k = eh->eh_entries;
+	while (k > 1) {
+		k = (r - l) / 2;
+		if (block < ix[l + k].ei_block)
+			r -= k;
+		else
+			l += k;
+		ext_debug(tree, "%d:%d:%d ", k, l, r);
+	}
+
+	ix += l;
+	path->p_idx = ix;
+	ext_debug(tree," -> %d->%d ",path->p_idx->ei_block,path->p_idx->ei_leaf);
+
+	while (l++ < r) {
+		if (block < ix->ei_block) 
+			break;
+		path->p_idx = ix++;
+	}
+	ext_debug(tree, "  -> %d->%d\n", path->p_idx->ei_block,
+		  path->p_idx->ei_leaf);
+
+#ifdef CHECK_BINSEARCH 
+	{
+		struct ext3_extent_idx *chix;
+
+		chix = ix = EXT_FIRST_INDEX(eh);
+		for (k = 0; k < eh->eh_entries; k++, ix++) {
+			if (k != 0 && ix->ei_block <= ix[-1].ei_block) {
+				printk("k=%d, ix=0x%p, first=0x%p\n", k,
+				       ix, EXT_FIRST_INDEX(eh));
+				printk("%u <= %u\n",
+				       ix->ei_block,ix[-1].ei_block);
+			}
+			EXT_ASSERT(k == 0 || ix->ei_block > ix[-1].ei_block);
+			if (block < ix->ei_block) 
+				break;
+			chix = ix;
+		}
+		EXT_ASSERT(chix == path->p_idx);
+	}
+#endif
+}
+
+/*
+ * binary search for closest extent by given block
+ */
+static inline void
+ext3_ext_binsearch(struct ext3_extents_tree *tree,
+		   struct ext3_ext_path *path, int block)
+{
+	struct ext3_extent_header *eh = path->p_hdr;
+	struct ext3_extent *ex;
+	int l = 0, k, r;
+
+	EXT_ASSERT(eh->eh_magic == EXT3_EXT_MAGIC);
+	EXT_ASSERT(eh->eh_entries <= eh->eh_max);
+
+	if (eh->eh_entries == 0) {
+		/*
+		 * this leaf is empty yet:
+		 *  we get such a leaf in split/add case
+		 */
+		return;
+	}
+	
+	ext_debug(tree, "binsearch for %d:  ", block);
+
+	path->p_ext = ex = EXT_FIRST_EXTENT(eh);
+
+	r = k = eh->eh_entries;
+	while (k > 1) {
+		k = (r - l) / 2;
+		if (block < ex[l + k].ee_block)
+			r -= k;
+		else
+			l += k;
+		ext_debug(tree, "%d:%d:%d ", k, l, r);
+	}
+
+	ex += l;
+	path->p_ext = ex;
+	ext_debug(tree, "  -> %d:%d:%d ", path->p_ext->ee_block,
+		  path->p_ext->ee_start, path->p_ext->ee_len);
+
+	while (l++ < r) {
+		if (block < ex->ee_block) 
+			break;
+		path->p_ext = ex++;
+	}
+	ext_debug(tree, "  -> %d:%d:%d\n", path->p_ext->ee_block,
+		  path->p_ext->ee_start, path->p_ext->ee_len);
+
+#ifdef CHECK_BINSEARCH 
+	{
+		struct ext3_extent *chex;
+
+		chex = ex = EXT_FIRST_EXTENT(eh);
+		for (k = 0; k < eh->eh_entries; k++, ex++) {
+			EXT_ASSERT(k == 0 || ex->ee_block > ex[-1].ee_block);
+			if (block < ex->ee_block) 
+				break;
+			chex = ex;
+		}
+		EXT_ASSERT(chex == path->p_ext);
+	}
+#endif
+}
+
+int ext3_extent_tree_init(handle_t *handle, struct ext3_extents_tree *tree)
+{
+	struct ext3_extent_header *eh;
+
+	BUG_ON(tree->buffer_len == 0);
+	ext3_ext_get_access_for_root(handle, tree);
+	eh = EXT_ROOT_HDR(tree);
+	eh->eh_depth = 0;
+	eh->eh_entries = 0;
+	eh->eh_magic = EXT3_EXT_MAGIC;
+	eh->eh_max = ext3_ext_space_root(tree);
+	ext3_ext_mark_root_dirty(handle, tree);
+	ext3_ext_invalidate_cache(tree);
+	return 0;
+}
+
+struct ext3_ext_path *
+ext3_ext_find_extent(struct ext3_extents_tree *tree, int block,
+		     struct ext3_ext_path *path)
+{
+	struct ext3_extent_header *eh;
+	struct buffer_head *bh;
+	int depth, i, ppos = 0;
+
+	EXT_ASSERT(tree);
+	EXT_ASSERT(tree->inode);
+	EXT_ASSERT(tree->root);
+
+	eh = EXT_ROOT_HDR(tree);
+	EXT_ASSERT(eh);
+	if (ext3_ext_check_header(eh)) {
+		/* don't free previously allocated path
+		 * -- caller should take care */
+		path = NULL;
+		goto err;
+	}
+
+	i = depth = EXT_DEPTH(tree);
+	EXT_ASSERT(eh->eh_max);
+	EXT_ASSERT(eh->eh_magic == EXT3_EXT_MAGIC);
+	
+	/* account possible depth increase */
+	if (!path) {
+		path = kmalloc(sizeof(struct ext3_ext_path) * (depth + 2),
+			       GFP_NOFS);
+		if (!path)
+			return ERR_PTR(-ENOMEM);
+	}
+	memset(path, 0, sizeof(struct ext3_ext_path) * (depth + 1));
+	path[0].p_hdr = eh;
+
+	/* walk through the tree */
+	while (i) {
+		ext_debug(tree, "depth %d: num %d, max %d\n",
+			  ppos, eh->eh_entries, eh->eh_max);
+		ext3_ext_binsearch_idx(tree, path + ppos, block);
+		path[ppos].p_block = path[ppos].p_idx->ei_leaf;
+		path[ppos].p_depth = i;
+		path[ppos].p_ext = NULL;
+
+		bh = sb_bread(tree->inode->i_sb, path[ppos].p_block);
+		if (!bh)
+			goto err;
+
+		eh = EXT_BLOCK_HDR(bh);
+		ppos++;
+		EXT_ASSERT(ppos <= depth);
+		path[ppos].p_bh = bh;
+		path[ppos].p_hdr = eh;
+		i--;
+