ext3-extents-2.6.15.patch

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

+	/* zero-tree has no leaf blocks at all */
+	if (depth == 0)
+		return EXT_MAX_BLOCK;
+
+	/* go to index block */
+	depth--;
+	
+	while (depth >= 0) {
+		if (path[depth].p_idx !=
+		    EXT_LAST_INDEX(path[depth].p_hdr))
+			return path[depth].p_idx[1].ei_block;
+		depth--;        
+	}
+
+	return EXT_MAX_BLOCK;
+}
+
+/*
+ * if leaf gets modified and modified extent is first in the leaf
+ * then we have to correct all indexes above
+ * TODO: do we need to correct tree in all cases?
+ */
+int ext3_ext_correct_indexes(handle_t *handle, struct ext3_extents_tree *tree,
+			     struct ext3_ext_path *path)
+{
+	struct ext3_extent_header *eh;
+	int depth = EXT_DEPTH(tree);	
+	struct ext3_extent *ex;
+	unsigned long border;
+	int k, err = 0;
+	
+	eh = path[depth].p_hdr;
+	ex = path[depth].p_ext;
+	EXT_ASSERT(ex);
+	EXT_ASSERT(eh);
+	
+	if (depth == 0) {
+		/* there is no tree at all */
+		return 0;
+	}
+	
+	if (ex != EXT_FIRST_EXTENT(eh)) {
+		/* we correct tree if first leaf got modified only */
+		return 0;
+	}
+	
+	/*
+	 * TODO: we need correction if border is smaller then current one
+	 */
+	k = depth - 1;
+	border = path[depth].p_ext->ee_block;
+	if ((err = ext3_ext_get_access(handle, tree, path + k)))
+		return err;
+	path[k].p_idx->ei_block = border;
+	if ((err = ext3_ext_dirty(handle, tree, path + k)))
+		return err;
+
+	while (k--) {
+		/* change all left-side indexes */
+		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
+			break;
+		if ((err = ext3_ext_get_access(handle, tree, path + k)))
+			break;
+		path[k].p_idx->ei_block = border;
+		if ((err = ext3_ext_dirty(handle, tree, path + k)))
+			break;
+	}
+
+	return err;
+}
+
+static int inline
+ext3_can_extents_be_merged(struct ext3_extents_tree *tree,
+			   struct ext3_extent *ex1,
+			   struct ext3_extent *ex2)
+{
+	if (ex1->ee_block + ex1->ee_len != ex2->ee_block)
+		return 0;
+
+#ifdef AGRESSIVE_TEST
+	if (ex1->ee_len >= 4)
+		return 0;
+#endif
+
+	if (!tree->ops->mergable)
+		return 1;
+
+	return tree->ops->mergable(ex1, ex2);
+}
+
+/*
+ * this routine tries to merge requsted extent into the existing
+ * extent or inserts requested extent as new one into the tree,
+ * creating new leaf in no-space case
+ */
+int ext3_ext_insert_extent(handle_t *handle, struct ext3_extents_tree *tree,
+			   struct ext3_ext_path *path,
+			   struct ext3_extent *newext)
+{
+	struct ext3_extent_header * eh;
+	struct ext3_extent *ex, *fex;
+	struct ext3_extent *nearex; /* nearest extent */
+	struct ext3_ext_path *npath = NULL;
+	int depth, len, err, next;
+
+	EXT_ASSERT(newext->ee_len > 0);
+	depth = EXT_DEPTH(tree);
+	ex = path[depth].p_ext;
+	EXT_ASSERT(path[depth].p_hdr);
+
+	/* try to insert block into found extent and return */
+	if (ex && ext3_can_extents_be_merged(tree, ex, newext)) {
+		ext_debug(tree, "append %d block to %d:%d (from %d)\n",
+			  newext->ee_len, ex->ee_block, ex->ee_len,
+			  ex->ee_start);
+		if ((err = ext3_ext_get_access(handle, tree, path + depth)))
+			return err;
+		ex->ee_len += newext->ee_len;
+		eh = path[depth].p_hdr;
+		nearex = ex;
+		goto merge;
+	}
+
+repeat:
+	depth = EXT_DEPTH(tree);
+	eh = path[depth].p_hdr;
+	if (eh->eh_entries < eh->eh_max)
+		goto has_space;
+
+	/* probably next leaf has space for us? */
+	fex = EXT_LAST_EXTENT(eh);
+	next = ext3_ext_next_leaf_block(tree, path);
+	if (newext->ee_block > fex->ee_block && next != EXT_MAX_BLOCK) {
+		ext_debug(tree, "next leaf block - %d\n", next);
+		EXT_ASSERT(!npath);
+		npath = ext3_ext_find_extent(tree, next, NULL);
+		if (IS_ERR(npath))
+			return PTR_ERR(npath);
+		EXT_ASSERT(npath->p_depth == path->p_depth);
+		eh = npath[depth].p_hdr;
+		if (eh->eh_entries < eh->eh_max) {
+			ext_debug(tree,	"next leaf isnt full(%d)\n",
+				  eh->eh_entries);
+			path = npath;
+			goto repeat;
+		}
+		ext_debug(tree, "next leaf hasno free space(%d,%d)\n",
+			  eh->eh_entries, eh->eh_max);
+	}
+
+	/*
+	 * there is no free space in found leaf
+	 * we're gonna add new leaf in the tree
+	 */
+	err = ext3_ext_create_new_leaf(handle, tree, path, newext);
+	if (err)
+		goto cleanup;
+	depth = EXT_DEPTH(tree);
+	eh = path[depth].p_hdr;
+
+has_space:
+	nearex = path[depth].p_ext;
+
+	if ((err = ext3_ext_get_access(handle, tree, path + depth)))
+		goto cleanup;
+
+	if (!nearex) {
+		/* there is no extent in this leaf, create first one */
+		ext_debug(tree, "first extent in the leaf: %d:%d:%d\n",
+			  newext->ee_block, newext->ee_start,
+			  newext->ee_len);
+		path[depth].p_ext = EXT_FIRST_EXTENT(eh);
+	} else if (newext->ee_block > nearex->ee_block) {
+		EXT_ASSERT(newext->ee_block != nearex->ee_block);
+		if (nearex != EXT_LAST_EXTENT(eh)) {
+			len = EXT_MAX_EXTENT(eh) - nearex;
+			len = (len - 1) * sizeof(struct ext3_extent);
+			len = len < 0 ? 0 : len;
+			ext_debug(tree, "insert %d:%d:%d after: nearest 0x%p, "
+				  "move %d from 0x%p to 0x%p\n",
+				  newext->ee_block, newext->ee_start,
+				  newext->ee_len,
+				  nearex, len, nearex + 1, nearex + 2);
+			memmove(nearex + 2, nearex + 1, len);
+		}
+		path[depth].p_ext = nearex + 1;
+	} else {
+		EXT_ASSERT(newext->ee_block != nearex->ee_block);
+		len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext3_extent);
+		len = len < 0 ? 0 : len;
+		ext_debug(tree, "insert %d:%d:%d before: nearest 0x%p, "
+			  "move %d from 0x%p to 0x%p\n",
+			  newext->ee_block, newext->ee_start, newext->ee_len,
+			  nearex, len, nearex + 1, nearex + 2);
+		memmove(nearex + 1, nearex, len);
+		path[depth].p_ext = nearex;
+	}
+
+	eh->eh_entries++;
+	nearex = path[depth].p_ext;
+	nearex->ee_block = newext->ee_block;
+	nearex->ee_start = newext->ee_start;
+	nearex->ee_len = newext->ee_len;
+	/* FIXME: support for large fs */
+	nearex->ee_start_hi = 0;
+
+merge:
+	/* try to merge extents to the right */
+	while (nearex < EXT_LAST_EXTENT(eh)) {
+		if (!ext3_can_extents_be_merged(tree, nearex, nearex + 1))
+			break;
+		/* merge with next extent! */
+		nearex->ee_len += nearex[1].ee_len;
+		if (nearex + 1 < EXT_LAST_EXTENT(eh)) {
+			len = (EXT_LAST_EXTENT(eh) - nearex - 1) *
+				sizeof(struct ext3_extent);
+			memmove(nearex + 1, nearex + 2, len);
+		}
+		eh->eh_entries--;
+		EXT_ASSERT(eh->eh_entries > 0);
+	}
+
+	/* try to merge extents to the left */
+
+	/* time to correct all indexes above */
+	err = ext3_ext_correct_indexes(handle, tree, path);
+	if (err)
+		goto cleanup;
+
+	err = ext3_ext_dirty(handle, tree, path + depth);
+
+cleanup:
+	if (npath) {
+		ext3_ext_drop_refs(npath);
+		kfree(npath);
+	}
+	ext3_ext_tree_changed(tree);
+	ext3_ext_invalidate_cache(tree);
+	return err;
+}
+
+int ext3_ext_walk_space(struct ext3_extents_tree *tree, unsigned long block,
+			unsigned long num, ext_prepare_callback func)
+{
+	struct ext3_ext_path *path = NULL;
+	struct ext3_ext_cache cbex;
+	struct ext3_extent *ex;
+	unsigned long next, start = 0, end = 0;
+	unsigned long last = block + num;
+	int depth, exists, err = 0;
+
+	EXT_ASSERT(tree);
+	EXT_ASSERT(func);
+	EXT_ASSERT(tree->inode);
+	EXT_ASSERT(tree->root);
+
+	while (block < last && block != EXT_MAX_BLOCK) {
+		num = last - block;
+		/* find extent for this block */
+		path = ext3_ext_find_extent(tree, block, path);
+		if (IS_ERR(path)) {
+			err = PTR_ERR(path);
+			path = NULL;
+			break;
+		}
+
+		depth = EXT_DEPTH(tree);
+		EXT_ASSERT(path[depth].p_hdr);
+		ex = path[depth].p_ext;
+		next = ext3_ext_next_allocated_block(path);
+
+		exists = 0;
+		if (!ex) {
+			/* there is no extent yet, so try to allocate
+			 * all requested space */
+			start = block;
+			end = block + num;
+		} else if (ex->ee_block > block) {
+			/* need to allocate space before found extent */
+			start = block;
+			end = ex->ee_block;
+			if (block + num < end)
+				end = block + num;
+		} else if (block >= ex->ee_block + ex->ee_len) {
+			/* need to allocate space after found extent */
+			start = block;
+			end = block + num;
+			if (end >= next)
+				end = next;
+		} else if (block >= ex->ee_block) {
+			/* 
+			 * some part of requested space is covered
+			 * by found extent
+			 */
+			start = block;
+			end = ex->ee_block + ex->ee_len;
+			if (block + num < end)
+				end = block + num;
+			exists = 1;
+		} else {
+			BUG();
+		}
+		EXT_ASSERT(end > start);
+
+		if (!exists) {
+			cbex.ec_block = start;
+			cbex.ec_len = end - start;
+			cbex.ec_start = 0;
+			cbex.ec_type = EXT3_EXT_CACHE_GAP;
+		} else {
+			cbex.ec_block = ex->ee_block;
+			cbex.ec_len = ex->ee_len;
+			cbex.ec_start = ex->ee_start;
+			cbex.ec_type = EXT3_EXT_CACHE_EXTENT;
+		}
+
+		EXT_ASSERT(cbex.ec_len > 0);
+		EXT_ASSERT(path[depth].p_hdr);
+		err = func(tree, path, &cbex);
+		ext3_ext_drop_refs(path);
+
+		if (err < 0)
+			break;
+		if (err == EXT_REPEAT)
+			continue;
+		else if (err == EXT_BREAK) {
+			err = 0;
+			break;
+		}
+
+		if (EXT_DEPTH(tree) != depth) {
+			/* depth was changed. we have to realloc path */
+			kfree(path);
+			path = NULL;
+		}
+
+		block = cbex.ec_block + cbex.ec_len;
+	}
+
+	if (path) {
+		ext3_ext_drop_refs(path);
+		kfree(path);
+	}
+
+	return err;
+}
+
+static inline void
+ext3_ext_put_in_cache(struct ext3_extents_tree *tree, __u32 block,
+		      __u32 len, __u32 start, int type)
+{
+	EXT_ASSERT(len > 0);
+	if (tree->cex) {
+		tree->cex->ec_type = type;
+		tree->cex->ec_block = block;
+		tree->cex->ec_len = len;
+		tree->cex->ec_start = start;
+	}
+}
+
+/*
+ * this routine calculate boundaries of the gap requested block fits into
+ * and cache this gap
+ */
+static inline void
+ext3_ext_put_gap_in_cache(struct ext3_extents_tree *tree,
+			  struct ext3_ext_path *path,
+			  unsigned long block)
+{
+	int depth = EXT_DEPTH(tree);
+	unsigned long lblock, len;
+	struct ext3_extent *ex;
+
+	if (!tree->cex)
+		return;
+
+	ex = path[depth].p_ext;
+	if (ex == NULL) {
+		/* there is no extent yet, so gap is [0;-] */
+		lblock = 0;
+		len = EXT_MAX_BLOCK;
+		ext_debug(tree, "cache gap(whole file):");
+	} else if (block < ex->ee_block) {
+		lblock = block;
+		len = ex->ee_block - block;
+		ext_debug(tree, "cache gap(before): %lu [%lu:%lu]",
+			  (unsigned long) block,
+			  (unsigned long) ex->ee_block,
+			  (unsigned long) ex->ee_len);
+	} else if (block >= ex->ee_block + ex->ee_len) {
+		lblock = ex->ee_block + ex->ee_len;
+		len = ext3_ext_next_allocated_block(path);
+		ext_debug(tree, "cache gap(after): [%lu:%lu] %lu",
+			  (unsigned long) ex->ee_block,
+			  (unsigned long) ex->ee_len,
+			  (unsigned long) block);
+		EXT_ASSERT(len > lblock);
+		len = len - lblock;
+	} else {
+		lblock = len = 0;
+		BUG();
+	}
+
+	ext_debug(tree, " -> %lu:%lu\n", (unsigned long) lblock, len);
+	ext3_ext_put_in_cache(tree, lblock, len, 0, EXT3_EXT_CACHE_GAP);
+}
+
+static inline int
+ext3_ext_in_cache(struct ext3_extents_tree *tree, unsigned long block,
+		  struct ext3_extent *ex)
+{
+	struct ext3_ext_cache *cex = tree->cex;
+
+	/* is there cache storage at all? */
+	if (!cex)
+		return EXT3_EXT_CACHE_NO;
+
+	/* has cache valid data? */
+	if (cex->ec_type == EXT3_EXT_CACHE_NO)
+		return EXT3_EXT_CACHE_NO;
+
+	EXT_ASSERT(cex->ec_type == EXT3_EXT_CACHE_GAP ||
+		   cex->ec_type == EXT3_EXT_CACHE_EXTENT);
+	if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) {
+		ex->ee_block = cex->ec_block;
+		ex->ee_start = cex->ec_start;
+		ex->ee_start_hi = 0;
+		ex->ee_len = cex->ec_len;
+		ext_debug(tree, "%lu cached by %lu:%lu:%lu\n",
+			  (unsigned long) block,
+			  (unsigned long) ex->ee_block,
+			  (unsigned long) ex->ee_len,
+			  (unsigned long) ex->ee_start);
+		return cex->ec_type;
+	}
+
+	/* not in cache */
+	return EXT3_EXT_CACHE_NO;
+}
+
+/*
+ * routine removes index from the index block
+ * it's used in truncate case only. thus all requests are for
+ * last index in the block only
+ */
+int ext3_ext_rm_idx(handle_t *handle, struct ext3_extents_tree *tree,
+		    struct ext3_ext_path *path)
+{
+	struct buffer_head *bh;
+	int err;
+	
+	/* free index block */
+	path--;
+	EXT_ASSERT(path->p_hdr->eh_entries);
+	if ((err = ext3_ext_get_access(handle, tree, path)))
+		return err;
+	path->p_hdr->eh_entries--;
+	if ((err = ext3_ext_dirty(handle, tree, path)))
+		return err;
+	ext_debug(tree, "index is empty, remove it, free block %d\n",
+		  path->p_idx->ei_leaf);
+	bh = sb_find_get_block(tree->inode->i_sb, path->p_idx->ei_leaf);
+	ext3_forget(handle, 1, tree->inode, bh, path->p_idx->ei_leaf);
+	ext3_free_blocks(handle, tree->inode, path->p_idx->ei_leaf, 1);
+	return err;
+}
+
+int ext3_ext_calc_credits_for_insert(struct ext3_extents_tree *tree,
+				     struct ext3_ext_path *path)
+{
+	int depth = EXT_DEPTH(tree);
+	int needed;
+
+	if (path) {
+		/* probably there is space in leaf? */
+		if (path[depth].p_hdr->eh_entries < path[depth].p_hdr->eh_max)
+			return 1;
+	}
+	
+	/*
+	 * the worste case we're expecting is creation of the
+	 * new root (growing in depth) with index splitting
+	 * for splitting we have to consider depth + 1 because
+	 * previous growing could increase it
+	 */
+	depth = depth + 1;
+
+	/* 
+	 * growing in depth:
+	 * block allocation + new root + old root
+	 */