ext3-extents-2.6.15.patch

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

+	needed = EXT3_ALLOC_NEEDED + 2;
+
+	/* index split. we may need:
+	 *   allocate intermediate indexes and new leaf
+	 *   change two blocks at each level, but root
+	 *   modify root block (inode)
+	 */
+	needed += (depth * EXT3_ALLOC_NEEDED) + (2 * depth) + 1;
+
+	return needed;
+}
+
+static int
+ext3_ext_split_for_rm(handle_t *handle, struct ext3_extents_tree *tree,
+		      struct ext3_ext_path *path, unsigned long start,
+		      unsigned long end)
+{
+	struct ext3_extent *ex, tex;
+	struct ext3_ext_path *npath;
+	int depth, creds, err;
+
+	depth = EXT_DEPTH(tree);
+	ex = path[depth].p_ext;
+	EXT_ASSERT(ex);
+	EXT_ASSERT(end < ex->ee_block + ex->ee_len - 1);
+	EXT_ASSERT(ex->ee_block < start);
+
+	/* calculate tail extent */
+	tex.ee_block = end + 1;
+	EXT_ASSERT(tex.ee_block < ex->ee_block + ex->ee_len);
+	tex.ee_len = ex->ee_block + ex->ee_len - tex.ee_block;
+
+	creds = ext3_ext_calc_credits_for_insert(tree, path);
+	handle = ext3_ext_journal_restart(handle, creds);
+	if (IS_ERR(handle))
+		return PTR_ERR(handle);
+	
+	/* calculate head extent. use primary extent */
+	err = ext3_ext_get_access(handle, tree, path + depth);
+	if (err)
+		return err;
+	ex->ee_len = start - ex->ee_block;
+	err = ext3_ext_dirty(handle, tree, path + depth);
+	if (err)
+		return err;
+
+	/* FIXME: some callback to free underlying resource
+	 * and correct ee_start? */
+	ext_debug(tree, "split extent: head %u:%u, tail %u:%u\n",
+		  ex->ee_block, ex->ee_len, tex.ee_block, tex.ee_len);
+
+	npath = ext3_ext_find_extent(tree, ex->ee_block, NULL);
+	if (IS_ERR(npath))
+		return PTR_ERR(npath);
+	depth = EXT_DEPTH(tree);
+	EXT_ASSERT(npath[depth].p_ext->ee_block == ex->ee_block);
+	EXT_ASSERT(npath[depth].p_ext->ee_len == ex->ee_len);
+
+	err = ext3_ext_insert_extent(handle, tree, npath, &tex);
+	ext3_ext_drop_refs(npath);
+	kfree(npath);
+
+	return err;
+}
+
+static int
+ext3_ext_rm_leaf(handle_t *handle, struct ext3_extents_tree *tree,
+		 struct ext3_ext_path *path, unsigned long start,
+		 unsigned long end)
+{
+	struct ext3_extent *ex, *fu = NULL, *lu, *le;
+	int err = 0, correct_index = 0;
+	int depth = EXT_DEPTH(tree), credits;
+	struct ext3_extent_header *eh;
+	unsigned a, b, block, num;
+
+	ext_debug(tree, "remove [%lu:%lu] in leaf\n", start, end);
+	if (!path[depth].p_hdr)
+		path[depth].p_hdr = EXT_BLOCK_HDR(path[depth].p_bh);
+	eh = path[depth].p_hdr;
+	EXT_ASSERT(eh);
+	EXT_ASSERT(eh->eh_entries <= eh->eh_max);
+	EXT_ASSERT(eh->eh_magic == EXT3_EXT_MAGIC);
+	
+	/* find where to start removing */
+	le = ex = EXT_LAST_EXTENT(eh);
+	while (ex != EXT_FIRST_EXTENT(eh)) {
+		if (ex->ee_block <= end)
+			break;
+		ex--;
+	}
+
+	if (start > ex->ee_block && end < ex->ee_block + ex->ee_len - 1) {
+		/* removal of internal part of the extent requested
+		 * tail and head must be placed in different extent
+		 * so, we have to insert one more extent */
+		path[depth].p_ext = ex;
+		return ext3_ext_split_for_rm(handle, tree, path, start, end);
+	}
+	
+	lu = ex;
+	while (ex >= EXT_FIRST_EXTENT(eh) && ex->ee_block + ex->ee_len > start) {
+		ext_debug(tree, "remove ext %u:%u\n", ex->ee_block, ex->ee_len);
+		path[depth].p_ext = ex;
+	
+		a = ex->ee_block > start ? ex->ee_block : start;
+		b = ex->ee_block + ex->ee_len - 1 < end ?
+			ex->ee_block + ex->ee_len - 1 : end;
+		
+		ext_debug(tree, "  border %u:%u\n", a, b);
+
+		if (a != ex->ee_block && b != ex->ee_block + ex->ee_len - 1) {
+			block = 0;
+			num = 0;
+			BUG();
+		} else if (a != ex->ee_block) {
+			/* remove tail of the extent */
+			block = ex->ee_block;
+			num = a - block;
+		} else if (b != ex->ee_block + ex->ee_len - 1) {
+			/* remove head of the extent */
+			block = a;
+			num = b - a;
+		} else {
+			/* remove whole extent: excelent! */
+			block = ex->ee_block; 
+			num = 0;
+			EXT_ASSERT(a == ex->ee_block &&
+				   b == ex->ee_block + ex->ee_len - 1);
+		}
+
+		if (ex == EXT_FIRST_EXTENT(eh))
+			correct_index = 1;
+
+		credits = 1;
+		if (correct_index)
+			credits += (EXT_DEPTH(tree) * EXT3_ALLOC_NEEDED) + 1;
+		if (tree->ops->remove_extent_credits)
+			credits+=tree->ops->remove_extent_credits(tree,ex,a,b);
+		
+		handle = ext3_ext_journal_restart(handle, credits);
+		if (IS_ERR(handle)) {
+			err = PTR_ERR(handle);
+			goto out;
+		}
+
+		err = ext3_ext_get_access(handle, tree, path + depth);
+		if (err)
+			goto out;
+
+		if (tree->ops->remove_extent)
+			err = tree->ops->remove_extent(tree, ex, a, b);
+		if (err)
+			goto out;
+
+		if (num == 0) {
+			/* this extent is removed entirely mark slot unused */
+			ex->ee_start = ex->ee_start_hi = 0;
+			eh->eh_entries--;
+			fu = ex;
+		}
+
+		ex->ee_block = block;
+		ex->ee_len = num;
+
+		err = ext3_ext_dirty(handle, tree, path + depth);
+		if (err)
+			goto out;
+
+		ext_debug(tree, "new extent: %u:%u:%u\n",
+			  ex->ee_block, ex->ee_len, ex->ee_start);
+		ex--;
+	}
+
+	if (fu) {
+		/* reuse unused slots */
+		while (lu < le) {
+			if (lu->ee_start) {
+				*fu = *lu;
+				lu->ee_start = lu->ee_start_hi = 0;
+				fu++;
+			}
+			lu++;
+		}
+	}
+
+	if (correct_index && eh->eh_entries)
+		err = ext3_ext_correct_indexes(handle, tree, path);
+
+	/* if this leaf is free, then we should
+	 * remove it from index block above */
+	if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
+		err = ext3_ext_rm_idx(handle, tree, path + depth);
+
+out:
+	return err;
+}
+
+
+static struct ext3_extent_idx *
+ext3_ext_last_covered(struct ext3_extent_header *hdr, unsigned long block)
+{
+	struct ext3_extent_idx *ix;
+	
+	ix = EXT_LAST_INDEX(hdr);
+	while (ix != EXT_FIRST_INDEX(hdr)) {
+		if (ix->ei_block <= block)
+			break;
+		ix--;
+	}
+	return ix;
+}
+
+/*
+ * returns 1 if current index have to be freed (even partial)
+ */
+static int inline
+ext3_ext_more_to_rm(struct ext3_ext_path *path)
+{
+	EXT_ASSERT(path->p_idx);
+
+	if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
+		return 0;
+
+	/*
+	 * if truncate on deeper level happened it it wasn't partial
+	 * so we have to consider current index for truncation
+	 */
+	if (path->p_hdr->eh_entries == path->p_block)
+		return 0;
+	return 1;
+}
+
+int ext3_ext_remove_space(struct ext3_extents_tree *tree,
+			  unsigned long start, unsigned long end)
+{
+	struct inode *inode = tree->inode;
+	struct super_block *sb = inode->i_sb;
+	int depth = EXT_DEPTH(tree);
+	struct ext3_ext_path *path;
+	handle_t *handle;
+	int i = 0, err = 0;
+
+	ext_debug(tree, "space to be removed: %lu:%lu\n", start, end);
+
+	/* probably first extent we're gonna free will be last in block */
+	handle = ext3_journal_start(inode, depth + 1);
+	if (IS_ERR(handle))
+		return PTR_ERR(handle);
+
+	ext3_ext_invalidate_cache(tree);
+
+	/*
+	 * we start scanning from right side freeing all the blocks
+	 * after i_size and walking into the deep
+	 */
+	path = kmalloc(sizeof(struct ext3_ext_path) * (depth + 1), GFP_KERNEL);
+	if (IS_ERR(path)) {
+		ext3_error(sb, __FUNCTION__, "Can't allocate path array");
+		ext3_journal_stop(handle);
+		return -ENOMEM;
+	}
+	memset(path, 0, sizeof(struct ext3_ext_path) * (depth + 1));
+	path[i].p_hdr = EXT_ROOT_HDR(tree);
+	
+	while (i >= 0 && err == 0) {
+		if (i == depth) {
+			/* this is leaf block */
+			err = ext3_ext_rm_leaf(handle, tree, path, start, end);
+			/* root level have p_bh == NULL, brelse() eats this */
+			brelse(path[i].p_bh);
+			i--;
+			continue;
+		}
+		
+		/* this is index block */
+		if (!path[i].p_hdr) {
+			ext_debug(tree, "initialize header\n");
+			path[i].p_hdr = EXT_BLOCK_HDR(path[i].p_bh);
+		}
+
+		EXT_ASSERT(path[i].p_hdr->eh_entries <= path[i].p_hdr->eh_max);
+		EXT_ASSERT(path[i].p_hdr->eh_magic == EXT3_EXT_MAGIC);
+		
+		if (!path[i].p_idx) {
+			/* this level hasn't touched yet */
+			path[i].p_idx =
+				ext3_ext_last_covered(path[i].p_hdr, end);
+			path[i].p_block = path[i].p_hdr->eh_entries + 1;
+			ext_debug(tree, "init index ptr: hdr 0x%p, num %d\n",
+				  path[i].p_hdr, path[i].p_hdr->eh_entries);
+		} else {
+			/* we've already was here, see at next index */
+			path[i].p_idx--;
+		}
+
+		ext_debug(tree, "level %d - index, first 0x%p, cur 0x%p\n",
+			  i, EXT_FIRST_INDEX(path[i].p_hdr),
+			  path[i].p_idx);
+		if (ext3_ext_more_to_rm(path + i)) {
+			/* go to the next level */
+			ext_debug(tree, "move to level %d (block %d)\n",
+				  i + 1, path[i].p_idx->ei_leaf);
+			memset(path + i + 1, 0, sizeof(*path));
+			path[i+1].p_bh = sb_bread(sb, path[i].p_idx->ei_leaf);
+			if (!path[i+1].p_bh) {
+				/* should we reset i_size? */
+				err = -EIO;
+				break;
+			}
+			/* put actual number of indexes to know is this
+			 * number got changed at the next iteration */
+			path[i].p_block = path[i].p_hdr->eh_entries;
+			i++;
+		} else {
+			/* we finish processing this index, go up */
+			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
+				/* index is empty, remove it
+				 * handle must be already prepared by the
+				 * truncatei_leaf() */
+				err = ext3_ext_rm_idx(handle, tree, path + i);
+			}
+			/* root level have p_bh == NULL, brelse() eats this */
+			brelse(path[i].p_bh);
+			i--;
+			ext_debug(tree, "return to level %d\n", i);
+		}
+	}
+
+	/* TODO: flexible tree reduction should be here */
+	if (path->p_hdr->eh_entries == 0) {
+		/*
+		 * truncate to zero freed all the tree
+		 * so, we need to correct eh_depth
+		 */
+		err = ext3_ext_get_access(handle, tree, path);
+		if (err == 0) {
+			EXT_ROOT_HDR(tree)->eh_depth = 0;
+			EXT_ROOT_HDR(tree)->eh_max = ext3_ext_space_root(tree);
+			err = ext3_ext_dirty(handle, tree, path);
+		}
+	}
+	ext3_ext_tree_changed(tree);
+
+	kfree(path);
+	ext3_journal_stop(handle);
+
+	return err;
+}
+
+int ext3_ext_calc_metadata_amount(struct ext3_extents_tree *tree, int blocks)
+{
+	int lcap, icap, rcap, leafs, idxs, num;
+
+	rcap = ext3_ext_space_root(tree);
+	if (blocks <= rcap) {
+		/* all extents fit to the root */
+		return 0;
+	}
+
+	rcap = ext3_ext_space_root_idx(tree);
+	lcap = ext3_ext_space_block(tree);
+	icap = ext3_ext_space_block_idx(tree);
+
+	num = leafs = (blocks + lcap - 1) / lcap;
+	if (leafs <= rcap) {
+		/* all pointers to leafs fit to the root */
+		return leafs;
+	}
+
+	/* ok. we need separate index block(s) to link all leaf blocks */
+	idxs = (leafs + icap - 1) / icap;
+	do {
+		num += idxs;
+		idxs = (idxs + icap - 1) / icap;
+	} while (idxs > rcap);
+
+	return num;
+}
+
+/*
+ * called at mount time
+ */
+void ext3_ext_init(struct super_block *sb)
+{
+	/*
+	 * possible initialization would be here
+	 */
+
+	if (test_opt(sb, EXTENTS)) {
+		printk("EXT3-fs: file extents enabled");
+#ifdef AGRESSIVE_TEST
+		printk(", agressive tests");
+#endif
+#ifdef CHECK_BINSEARCH
+		printk(", check binsearch");
+#endif
+		printk("\n");
+	}
+}
+
+/*
+ * called at umount time
+ */
+void ext3_ext_release(struct super_block *sb)
+{
+}
+
+/************************************************************************
+ * VFS related routines
+ ************************************************************************/
+
+static int ext3_get_inode_write_access(handle_t *handle, void *buffer)
+{
+	/* we use in-core data, not bh */
+	return 0;
+}
+
+static int ext3_mark_buffer_dirty(handle_t *handle, void *buffer)
+{
+	struct inode *inode = buffer;
+	return ext3_mark_inode_dirty(handle, inode);
+}
+
+static int ext3_ext_mergable(struct ext3_extent *ex1,
+			     struct ext3_extent *ex2)
+{
+	/* FIXME: support for large fs */
+	if (ex1->ee_start + ex1->ee_len == ex2->ee_start)
+		return 1;
+	return 0;
+}
+
+static int
+ext3_remove_blocks_credits(struct ext3_extents_tree *tree,
+			   struct ext3_extent *ex,
+			   unsigned long from, unsigned long to)
+{
+	int needed;
+	
+	/* at present, extent can't cross block group */;
+	needed = 4; /* bitmap + group desc + sb + inode */
+
+#ifdef CONFIG_QUOTA
+	needed += 2 * EXT3_SINGLEDATA_TRANS_BLOCKS;
+#endif
+	return needed;
+}
+
+static int
+ext3_remove_blocks(struct ext3_extents_tree *tree,
+		   struct ext3_extent *ex,
+		   unsigned long from, unsigned long to)
+{
+	int needed = ext3_remove_blocks_credits(tree, ex, from, to);
+	handle_t *handle = ext3_journal_start(tree->inode, needed);
+	struct buffer_head *bh;
+	int i;
+
+	if (IS_ERR(handle))
+		return PTR_ERR(handle);
+	if (from >= ex->ee_block && to == ex->ee_block + ex->ee_len - 1) {
+		/* tail removal */
+		unsigned long num, start;
+		num = ex->ee_block + ex->ee_len - from;
+		start = ex->ee_start + ex->ee_len - num;
+		ext_debug(tree, "free last %lu blocks starting %lu\n",
+			  num, start);
+		for (i = 0; i < num; i++) {
+			bh = sb_find_get_block(tree->inode->i_sb, start + i);
+			ext3_forget(handle, 0, tree->inode, bh, start + i);
+		}
+		ext3_free_blocks(handle, tree->inode, start, num);
+	} else if (from == ex->ee_block && to <= ex->ee_block + ex->ee_len - 1) {
+		printk("strange request: removal %lu-%lu from %u:%u\n",
+		       from, to, ex->ee_block, ex->ee_len);
+	} else {
+		printk("strange request: removal(2) %lu-%lu from %u:%u\n",
+		       from, to, ex->ee_block, ex->ee_len);
+	}
+	ext3_journal_stop(handle);
+	return 0;
+}
+
+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;