[RFC PATCH 67/76] ssdfs: extents b-tree specialized operations

[Viacheslav Dubeyko <slava@dubeyko.com>]

Extents b-tree implements API:
(1) create - create extents b-tree
(2) destroy - destroy extents b-tree
(3) flush - flush dirty extents b-tree
(4) prepare_volume_extent - convert requested offset into extent
(5) recommend_migration_extent - find extent recommended for migration
(6) add_extent - add extent into the extents b-tree
(7) move_extent - move extent from one segment into another one
(8) truncate - truncate extent b-tree

Signed-off-by: Viacheslav Dubeyko <slava@dubeyko.com>
CC: Viacheslav Dubeyko <viacheslav.dubeyko@bytedance.com>
CC: Luka Perkov <luka.perkov@sartura.hr>
CC: Bruno Banelli <bruno.banelli@sartura.hr>
---
 fs/ssdfs/extents_tree.c | 3519 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 3519 insertions(+)

diff --git a/fs/ssdfs/extents_tree.c b/fs/ssdfs/extents_tree.c
index a13e7d773e7d..f978ef0cca12 100644
--- a/fs/ssdfs/extents_tree.c
+++ b/fs/ssdfs/extents_tree.c
@@ -3368,3 +3368,3522 @@ int ssdfs_prepare_empty_fork(u64 blk,
 
 	return 0;
 }
+
+/*
+ * ssdfs_extents_tree_add_inline_fork() - add the inline fork into the tree
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to add the inline fork into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - inline tree hasn't room for the new fork.
+ * %-EEXIST     - fork exists in the tree.
+ */
+static
+int ssdfs_extents_tree_add_inline_fork(struct ssdfs_extents_btree_info *tree,
+				       struct ssdfs_btree_search *search)
+{
+	struct ssdfs_raw_fork *cur;
+	size_t fork_size = sizeof(struct ssdfs_raw_fork);
+	s64 forks_count, forks_capacity;
+	int private_flags;
+	u64 start_hash;
+	u16 start_index;
+	u64 hash1, hash2;
+	u64 len;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->inline_forks) {
+		SSDFS_ERR("empty inline tree %p\n",
+			  tree->inline_forks);
+		return -ERANGE;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+	if (!tree->owner) {
+		SSDFS_ERR("empty owner inode\n");
+		return -ERANGE;
+	}
+
+	private_flags = atomic_read(&tree->owner->private_flags);
+
+	forks_capacity = SSDFS_INLINE_FORKS_COUNT;
+	if (private_flags & SSDFS_INODE_HAS_XATTR_BTREE)
+		forks_capacity--;
+	if (private_flags & SSDFS_INODE_HAS_EXTENTS_BTREE) {
+		SSDFS_ERR("the extents tree is generic\n");
+		return -ERANGE;
+	}
+
+	if (forks_count > forks_capacity) {
+		SSDFS_WARN("extents tree is corrupted: "
+			   "forks_count %llu, forks_capacity %llu\n",
+			   (u64)forks_count, (u64)forks_capacity);
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	} else if (forks_count == forks_capacity) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("inline tree hasn't room for the new fork: "
+			  "forks_count %llu, forks_capacity %llu\n",
+			  (u64)forks_count, (u64)forks_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOSPC;
+	}
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+	case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search result's state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	if (start_hash != le64_to_cpu(search->raw.fork.start_offset)) {
+		SSDFS_ERR("corrupted fork: "
+			  "start_hash %llx, "
+			  "fork (start %llu, blks_count %llu)\n",
+			  start_hash,
+			  le64_to_cpu(search->raw.fork.start_offset),
+			  le64_to_cpu(search->raw.fork.blks_count));
+		return -ERANGE;
+	}
+
+	start_index = search->result.start_index;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("start_index %u, forks_count %lld, "
+		  "forks_capacity %lld\n",
+		  start_index, forks_count, forks_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (forks_count == 0) {
+		if (start_index != 0) {
+			SSDFS_ERR("invalid start_index %u\n",
+				  start_index);
+			return -ERANGE;
+		}
+
+		cur = &tree->inline_forks[start_index];
+
+		ssdfs_memcpy(cur, 0, fork_size,
+			     &search->raw.fork, 0, fork_size,
+			     fork_size);
+	} else {
+		if (start_index >= forks_capacity) {
+			SSDFS_ERR("start_index %u >= forks_capacity %llu\n",
+				  start_index, (u64)forks_capacity);
+			return -ERANGE;
+		}
+
+		cur = &tree->inline_forks[start_index];
+
+		if ((start_index + 1) <= forks_count) {
+			err = ssdfs_memmove(tree->inline_forks,
+					    (start_index + 1) * fork_size,
+					    forks_capacity * fork_size,
+					    tree->inline_forks,
+					    start_index * fork_size,
+					    forks_capacity * fork_size,
+					    (forks_count - start_index) *
+						fork_size);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to move: err %d\n", err);
+				return err;
+			}
+
+			ssdfs_memcpy(cur, 0, fork_size,
+				     &search->raw.fork, 0, fork_size,
+				     fork_size);
+
+			hash1 = le64_to_cpu(search->raw.fork.start_offset);
+			len = le64_to_cpu(search->raw.fork.blks_count);
+
+			cur = &tree->inline_forks[start_index + 1];
+			hash2 = le64_to_cpu(cur->start_offset);
+
+			if (!((hash1 + len) <= hash2)) {
+				SSDFS_WARN("fork is corrupted: "
+					   "hash1 %llu, len %llu, "
+					   "hash2 %llu\n",
+					   hash1, len, hash2);
+				atomic_set(&tree->state,
+					SSDFS_EXTENTS_BTREE_CORRUPTED);
+				return -ERANGE;
+			}
+		} else {
+			ssdfs_memcpy(cur, 0, fork_size,
+				     &search->raw.fork, 0, fork_size,
+				     fork_size);
+
+			if (start_index > 0) {
+				cur = &tree->inline_forks[start_index - 1];
+
+				hash1 = le64_to_cpu(cur->start_offset);
+				len = le64_to_cpu(cur->blks_count);
+				hash2 =
+				    le64_to_cpu(search->raw.fork.start_offset);
+
+				if (!((hash1 + len) <= hash2)) {
+					SSDFS_WARN("fork is corrupted: "
+						   "hash1 %llu, len %llu, "
+						   "hash2 %llu\n",
+						   hash1, len, hash2);
+					atomic_set(&tree->state,
+						SSDFS_EXTENTS_BTREE_CORRUPTED);
+					return -ERANGE;
+				}
+			}
+		}
+	}
+
+	forks_count = atomic64_inc_return(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("forks_count %lld\n", forks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (forks_count > forks_capacity) {
+		SSDFS_WARN("forks_count is too much: "
+			   "count %lld, capacity %lld\n",
+			   forks_count, forks_capacity);
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	}
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_add_fork() - add the fork into the tree
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to add the generic fork into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-EEXIST     - fork exists in the tree.
+ */
+static
+int ssdfs_extents_tree_add_fork(struct ssdfs_extents_btree_info *tree,
+				struct ssdfs_btree_search *search)
+{
+	s64 forks_count;
+	u64 start_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->generic_tree) {
+		SSDFS_ERR("empty generic tree %p\n",
+			  tree->generic_tree);
+		return -ERANGE;
+	}
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+	case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+	case SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE:
+	case SSDFS_BTREE_SEARCH_OBSOLETE_RESULT:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search result's state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	if (start_hash != le64_to_cpu(search->raw.fork.start_offset)) {
+		SSDFS_ERR("corrupted fork: "
+			  "start_hash %llx, "
+			  "fork (start %llu, blks_count %llu)\n",
+			  start_hash,
+			  le64_to_cpu(search->raw.fork.start_offset),
+			  le64_to_cpu(search->raw.fork.blks_count));
+		return -ERANGE;
+	}
+
+	err = ssdfs_btree_add_item(tree->generic_tree, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to add the fork into the tree: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("forks_count %lld\n", forks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (forks_count >= S64_MAX) {
+		SSDFS_WARN("forks_count is too much\n");
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	}
+
+	err = ssdfs_btree_synchronize_root_node(tree->generic_tree,
+						tree->root);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to synchronize the root node: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	return 0;
+}
+
+/*
+ * ssdfs_invalidate_inline_tail_forks() - invalidate inline tail forks
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to invalidate inline tail forks.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_invalidate_inline_tail_forks(struct ssdfs_extents_btree_info *tree,
+					struct ssdfs_btree_search *search)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_fork *cur;
+	ino_t ino;
+	s64 forks_count;
+	int lower_bound, upper_bound;
+	int i, j;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	if (search->request.type != SSDFS_BTREE_SEARCH_INVALIDATE_TAIL) {
+		SSDFS_DBG("nothing should be done\n");
+		return 0;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+	forks_count = atomic64_read(&tree->forks_count);
+
+	lower_bound = search->result.start_index + 1;
+	upper_bound = forks_count - 1;
+
+	for (i = upper_bound; i >= lower_bound; i--) {
+		u64 calculated = 0;
+		u64 blks_count;
+
+		cur = &tree->inline_forks[i];
+
+		if (atomic64_read(&tree->forks_count) == 0) {
+			SSDFS_ERR("invalid forks_count\n");
+			return -ERANGE;
+		} else
+			atomic64_dec(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("forks_count %lld\n",
+			  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		blks_count = le64_to_cpu(cur->blks_count);
+		if (blks_count == 0 || blks_count >= U64_MAX) {
+			memset(cur, 0xFF, sizeof(struct ssdfs_raw_fork));
+			continue;
+		}
+
+		for (j = SSDFS_INLINE_EXTENTS_COUNT - 1; j >= 0; j--) {
+			struct ssdfs_raw_extent *extent;
+			u32 len;
+
+			extent = &cur->extents[j];
+			len = le32_to_cpu(extent->len);
+
+			if (len == 0 || len >= U32_MAX) {
+				memset(extent, 0xFF,
+					sizeof(struct ssdfs_raw_extent));
+				continue;
+			}
+
+			if ((calculated + len) > blks_count) {
+				atomic_set(&tree->state,
+					   SSDFS_EXTENTS_BTREE_CORRUPTED);
+				SSDFS_ERR("corrupted extent: "
+					  "calculated %llu, len %u, "
+					  "blks %llu\n",
+					  calculated, len, blks_count);
+				return -ERANGE;
+			}
+
+			err = ssdfs_shextree_add_pre_invalid_extent(shextree,
+								    ino,
+								    extent);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add pre-invalid "
+					  "(seg_id %llu, blk %u, "
+					  "len %u), err %d\n",
+				    le64_to_cpu(extent->seg_id),
+				    le32_to_cpu(extent->logical_blk),
+				    len, err);
+				return err;
+			}
+
+			calculated += len;
+
+			memset(extent, 0xFF, sizeof(struct ssdfs_raw_extent));
+		}
+
+		if (calculated != blks_count) {
+			atomic_set(&tree->state,
+				   SSDFS_EXTENTS_BTREE_CORRUPTED);
+			SSDFS_ERR("calculated %llu != blks %llu\n",
+				  calculated, blks_count);
+			return -ERANGE;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_change_inline_fork() - change inline fork
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to change the existing inline fork.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - fork doesn't exist in the tree.
+ */
+static
+int ssdfs_extents_tree_change_inline_fork(struct ssdfs_extents_btree_info *tree,
+					  struct ssdfs_btree_search *search)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_fork *cur;
+	size_t fork_size = sizeof(struct ssdfs_raw_fork);
+	ino_t ino;
+	u64 start_hash;
+	int private_flags;
+	s64 forks_count, forks_capacity;
+	u16 start_index;
+	u64 start_offset;
+	u64 blks_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->inline_forks) {
+		SSDFS_ERR("empty inline tree %p\n",
+			  tree->inline_forks);
+		return -ERANGE;
+	}
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+	case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search object state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	start_offset = le64_to_cpu(search->raw.fork.start_offset);
+	blks_count = le64_to_cpu(search->raw.fork.blks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("start_hash %llx, fork (start %llu, blks_count %llu)\n",
+		  start_hash, start_offset, blks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (search->request.type) {
+	case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+		if ((start_offset + blks_count) != start_hash) {
+			SSDFS_ERR("invalid request: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash, start_offset, blks_count);
+			return -ERANGE;
+		}
+		break;
+
+	default:
+		if (start_hash < start_offset ||
+		    start_hash >= (start_offset + blks_count)) {
+			SSDFS_ERR("corrupted fork: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash, start_offset, blks_count);
+			return -ERANGE;
+		}
+		break;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("BEFORE: forks_count %lld\n",
+		  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (!tree->owner) {
+		SSDFS_ERR("empty owner inode\n");
+		return -ERANGE;
+	}
+
+	private_flags = atomic_read(&tree->owner->private_flags);
+
+	forks_capacity = SSDFS_INLINE_FORKS_COUNT;
+	if (private_flags & SSDFS_INODE_HAS_XATTR_BTREE)
+		forks_capacity--;
+	if (private_flags & SSDFS_INODE_HAS_EXTENTS_BTREE) {
+		SSDFS_ERR("the extents tree is generic\n");
+		return -ERANGE;
+	}
+
+	if (forks_count > forks_capacity) {
+		SSDFS_WARN("extents tree is corrupted: "
+			   "forks_count %lld, forks_capacity %lld\n",
+			   forks_count, forks_capacity);
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	} else if (forks_count == 0) {
+		SSDFS_ERR("empty tree\n");
+		return -ENODATA;
+	}
+
+	start_index = search->result.start_index;
+
+	if (start_index >= forks_count) {
+		SSDFS_ERR("start_index %u >= forks_count %lld\n",
+			  start_index, forks_count);
+		return -ENODATA;
+	}
+
+	cur = &tree->inline_forks[start_index];
+	ssdfs_memcpy(cur, 0, fork_size,
+		     &search->raw.fork, 0, fork_size,
+		     fork_size);
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+
+	err = ssdfs_invalidate_inline_tail_forks(tree, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to invalidate inline tail forks: "
+			  "err %d\n", err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("AFTER: forks_count %lld\n",
+		  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_change_fork() - change the fork
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to change the existing generic fork.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - fork doesn't exist in the tree.
+ */
+static
+int ssdfs_extents_tree_change_fork(struct ssdfs_extents_btree_info *tree,
+				   struct ssdfs_btree_search *search)
+{
+	u64 start_hash;
+	u64 start_offset;
+	u64 blks_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->generic_tree) {
+		SSDFS_ERR("empty generic tree %p\n",
+			  tree->generic_tree);
+		return -ERANGE;
+	}
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+		/* continue logic */
+		break;
+
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+	case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+		/* extent has been merged into the existing fork */
+		search->result.state = SSDFS_BTREE_SEARCH_VALID_ITEM;
+		search->result.err = 0;
+		break;
+
+	default:
+		SSDFS_ERR("invalid search object state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	start_offset = le64_to_cpu(search->raw.fork.start_offset);
+	blks_count = le64_to_cpu(search->raw.fork.blks_count);
+
+	switch (search->request.type) {
+	case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+		if (start_hash < start_offset ||
+		    start_hash >= (start_offset + blks_count)) {
+			SSDFS_ERR("corrupted fork: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash, start_offset, blks_count);
+			return -ERANGE;
+		}
+		break;
+
+	case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+		if (start_hash != (start_offset + blks_count)) {
+			SSDFS_ERR("corrupted fork: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash, start_offset, blks_count);
+			return -ERANGE;
+		}
+		break;
+
+	default:
+		SSDFS_ERR("unexpected request type %#x\n",
+			  search->request.type);
+		return -ERANGE;
+	}
+
+	err = ssdfs_btree_change_item(tree->generic_tree, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to change the fork into the tree: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_add_extent_nolock() - add extent into the tree
+ * @tree: extents tree
+ * @blk: logical block number
+ * @extent: new extent
+ * @search: search object
+ *
+ * This method tries to add @extent into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-EEXIST     - extent exists in the tree.
+ */
+static
+int ssdfs_extents_tree_add_extent_nolock(struct ssdfs_extents_btree_info *tree,
+					 u64 blk,
+					 struct ssdfs_raw_extent *extent,
+					 struct ssdfs_btree_search *search)
+{
+	s64 forks_count;
+	u32 init_flags = SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			 SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+	u32 len;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !extent || !search);
+	BUG_ON(!tree->owner);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		err = ssdfs_extents_tree_find_inline_fork(tree, blk, search);
+		if (err == -ENOENT) {
+			/*
+			 * Fork doesn't exist for requested extent.
+			 * It needs to create a new fork.
+			 */
+		} else if (err == -ENODATA) {
+			/*
+			 * Fork doesn't contain the requested extent.
+			 * It needs to add a new extent.
+			 */
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find the inline fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_add_extent;
+		} else {
+			err = -EEXIST;
+			SSDFS_ERR("block exists already: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_add_extent;
+		}
+
+		if (err == -ENOENT) {
+add_new_inline_fork:
+			ssdfs_debug_btree_search_object(search);
+
+			if (forks_count > 0)
+				search->result.start_index += 1;
+
+			err = ssdfs_prepare_empty_fork(blk, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare empty fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			ssdfs_debug_btree_search_object(search);
+
+			err = ssdfs_add_extent_into_fork(blk, extent, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			ssdfs_debug_btree_search_object(search);
+
+			search->request.type = SSDFS_BTREE_SEARCH_ADD_ITEM;
+			err = ssdfs_extents_tree_add_inline_fork(tree, search);
+			if (err == -ENOSPC) {
+				err = ssdfs_migrate_inline2generic_tree(tree);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to migrate the tree: "
+						  "err %d\n",
+						  err);
+					goto finish_add_extent;
+				} else {
+					ssdfs_btree_search_init(search);
+					search->request.type =
+						SSDFS_BTREE_SEARCH_FIND_ITEM;
+					search->request.flags = init_flags;
+					search->request.start.hash = blk;
+					search->request.end.hash = blk + len - 1;
+					search->request.count = 1;
+					goto try_to_add_into_generic_tree;
+				}
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to add fork: err %d\n", err);
+				goto finish_add_extent;
+			}
+		} else {
+			err = ssdfs_add_extent_into_fork(blk, extent, search);
+			if (err == -ENOSPC) {
+				/* try to add a new fork */
+				goto add_new_inline_fork;
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+			err = ssdfs_extents_tree_change_inline_fork(tree,
+								   search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to change fork: err %d\n", err);
+				goto finish_add_extent;
+			}
+		}
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+try_to_add_into_generic_tree:
+		err = ssdfs_btree_find_item(tree->generic_tree, search);
+		if (err == -ENOENT) {
+			/*
+			 * Fork doesn't exist for requested extent.
+			 * It needs to create a new fork.
+			 */
+		} else if (err == -ENODATA) {
+			/*
+			 * Fork doesn't contain the requested extent.
+			 * It needs to add a new extent.
+			 */
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find the fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_add_extent;
+		} else {
+			err = -EEXIST;
+			SSDFS_ERR("block exists already: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_add_extent;
+		}
+
+		if (err == -ENOENT) {
+add_new_generic_fork:
+			ssdfs_debug_btree_search_object(search);
+
+			if (forks_count > 0)
+				search->result.start_index += 1;
+
+			err = ssdfs_prepare_empty_fork(blk, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare empty fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			err = ssdfs_add_extent_into_fork(blk, extent, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			search->request.type = SSDFS_BTREE_SEARCH_ADD_ITEM;
+			err = ssdfs_extents_tree_add_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add fork: err %d\n", err);
+				goto finish_add_extent;
+			}
+		} else {
+			err = ssdfs_add_extent_into_fork(blk, extent, search);
+			if (err == -ENOSPC || err == -ENODATA) {
+				/* try to add a new fork */
+				goto add_new_generic_fork;
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_add_extent;
+			}
+
+			search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+			err = ssdfs_extents_tree_change_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to change fork: err %d\n", err);
+				goto finish_add_extent;
+			}
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		goto finish_add_extent;
+	}
+
+finish_add_extent:
+	return err;
+}
+
+/*
+ * __ssdfs_extents_tree_add_extent() - add extent into the tree
+ * @tree: extents tree
+ * @blk: logical block number
+ * @extent: new extent
+ * @search: search object
+ *
+ * This method tries to add @extent into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-EEXIST     - extent exists in the tree.
+ */
+int __ssdfs_extents_tree_add_extent(struct ssdfs_extents_btree_info *tree,
+				    u64 blk,
+				    struct ssdfs_raw_extent *extent,
+				    struct ssdfs_btree_search *search)
+{
+	struct ssdfs_inode_info *ii;
+	u32 init_flags = SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			 SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+	u32 len;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !extent || !search);
+	BUG_ON(!tree->owner);
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	ii = tree->owner;
+
+	down_write(&ii->lock);
+	down_write(&tree->lock);
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+	len = le32_to_cpu(extent->len);
+
+	if (len == 0) {
+		err = -ERANGE;
+		SSDFS_ERR("empty extent\n");
+		goto finish_add_extent;
+	}
+
+	if (need_initialize_extent_btree_search(blk, search)) {
+		ssdfs_btree_search_init(search);
+		search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+		search->request.flags = init_flags;
+		search->request.start.hash = blk;
+		search->request.end.hash = blk + len - 1;
+		/* no information about forks count */
+		search->request.count = 0;
+	}
+
+	ssdfs_debug_btree_search_object(search);
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		goto finish_add_extent;
+	};
+
+	err = ssdfs_extents_tree_add_extent_nolock(tree, blk, extent, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to add extent: "
+			  "blk %llu, err %d\n",
+			  blk, err);
+		goto finish_add_extent;
+	}
+
+finish_add_extent:
+	up_write(&tree->lock);
+	up_write(&ii->lock);
+
+	ssdfs_btree_search_forget_parent_node(search);
+	ssdfs_btree_search_forget_child_node(search);
+
+	ssdfs_debug_extents_btree_object(tree);
+
+	return err;
+}
+
+/*
+ * ssdfs_change_extent_in_fork() - change extent in the fork
+ * @blk: logical block number
+ * @extent: extent object
+ * @search: search object
+ *
+ * This method tries to change @extent in the fork.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the fork.
+ */
+static
+int ssdfs_change_extent_in_fork(u64 blk,
+				struct ssdfs_raw_extent *extent,
+				struct ssdfs_btree_search *search)
+{
+	struct ssdfs_raw_fork *fork;
+	struct ssdfs_raw_extent *cur_extent = NULL;
+	struct ssdfs_raw_extent buf;
+	u64 start_offset;
+	u64 blks_count;
+	u32 len1, len2, len_diff;
+	u64 cur_blk;
+	int i;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!extent || !search);
+
+	SSDFS_DBG("blk %llu, extent %p, search %p\n",
+		  blk, extent, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_EMPTY_RESULT:
+		SSDFS_DBG("no fork in search object\n");
+		return -ENODATA;
+
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search object state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_size != sizeof(struct ssdfs_raw_fork) ||
+	    search->result.items_in_buffer != 1) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	fork = &search->raw.fork;
+	start_offset = le64_to_cpu(fork->start_offset);
+	blks_count = le64_to_cpu(fork->blks_count);
+	len1 = le32_to_cpu(extent->len);
+
+	if (start_offset >= U64_MAX || blks_count >= U64_MAX) {
+		SSDFS_ERR("invalid fork state: "
+			  "start_offset %llu, blks_count %llu\n",
+			  start_offset, blks_count);
+		return -ERANGE;
+	}
+
+	if (blk >= U64_MAX || len1 >= U32_MAX) {
+		SSDFS_ERR("invalid extent: "
+			  "blk %llu, len %u\n",
+			  blk, len1);
+		return -ERANGE;
+	}
+
+	if (start_offset <= blk && blk < (start_offset + blks_count)) {
+		/*
+		 * Expected state
+		 */
+	} else {
+		SSDFS_ERR("extent is out of fork: \n"
+			  "fork (start %llu, blks_count %llu), "
+			  "extent (blk %llu, len %u)\n",
+			  start_offset, blks_count,
+			  blk, len1);
+		return -ENODATA;
+	}
+
+	cur_blk = le64_to_cpu(fork->start_offset);
+	for (i = 0; i < SSDFS_INLINE_EXTENTS_COUNT; i++) {
+		len2 = le32_to_cpu(fork->extents[i].len);
+
+		if (cur_blk == blk) {
+			/* extent is found */
+			cur_extent = &fork->extents[i];
+			break;
+		} else if (blk < cur_blk) {
+			SSDFS_ERR("invalid extent: "
+				  "blk %llu, cur_blk %llu\n",
+				  blk, cur_blk);
+			return -ERANGE;
+		} else if (len2 >= U32_MAX || len2 == 0) {
+			/* empty extent */
+			break;
+		} else {
+			/* it needs to check the next extent */
+			cur_blk += len2;
+		}
+	}
+
+	if (!cur_extent) {
+		SSDFS_ERR("fail to find the extent: blk %llu\n",
+			  blk);
+		return -ENODATA;
+	}
+
+	if (le32_to_cpu(extent->len) == 0) {
+		SSDFS_ERR("empty extent: "
+			  "seg_id %llu, logical_blk %u, len %u\n",
+			  le64_to_cpu(extent->seg_id),
+			  le32_to_cpu(extent->logical_blk),
+			  le32_to_cpu(extent->len));
+		return -ERANGE;
+	}
+
+	ssdfs_memcpy(&buf, 0, sizeof(struct ssdfs_raw_extent),
+		     cur_extent, 0, sizeof(struct ssdfs_raw_extent),
+		     sizeof(struct ssdfs_raw_extent));
+	ssdfs_memcpy(cur_extent, 0, sizeof(struct ssdfs_raw_extent),
+		     extent, 0, sizeof(struct ssdfs_raw_extent),
+		     sizeof(struct ssdfs_raw_extent));
+
+	len2 = le32_to_cpu(buf.len);
+
+	if (len2 < len1) {
+		/* old extent is shorter */
+		len_diff = len1 - len2;
+		blks_count += len_diff;
+		fork->blks_count = cpu_to_le64(blks_count);
+	} else if (len2 > len1) {
+		/* old extent is larger */
+		len_diff = len2 - len1;
+
+		if (blks_count <= len_diff) {
+			SSDFS_ERR("blks_count %llu <= len_diff %u\n",
+				  blks_count, len_diff);
+			return -ERANGE;
+		}
+
+		blks_count -= len_diff;
+		fork->blks_count = cpu_to_le64(blks_count);
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_change_extent() - change extent in the tree
+ * @tree: extents tree
+ * @blk: logical block number
+ * @extent: extent object
+ * @search: search object
+ *
+ * This method tries to change @extent in the @tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the tree.
+ */
+int ssdfs_extents_tree_change_extent(struct ssdfs_extents_btree_info *tree,
+				     u64 blk,
+				     struct ssdfs_raw_extent *extent,
+				     struct ssdfs_btree_search *search)
+{
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !extent || !search);
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+
+	if (need_initialize_extent_btree_search(blk, search)) {
+		ssdfs_btree_search_init(search);
+		search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+		search->request.flags =
+			SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+		search->request.start.hash = blk;
+		search->request.end.hash = blk;
+		search->request.count = 1;
+	}
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		down_write(&tree->lock);
+
+		err = ssdfs_extents_tree_find_inline_fork(tree, blk, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to find the inline fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_inline_fork;
+		}
+
+		err = ssdfs_change_extent_in_fork(blk, extent, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change extent in fork: err %d\n",
+				  err);
+			goto finish_change_inline_fork;
+		}
+
+		search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+
+		err = ssdfs_extents_tree_change_inline_fork(tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change inline fork: err %d\n", err);
+			goto finish_change_inline_fork;
+		}
+
+finish_change_inline_fork:
+		up_write(&tree->lock);
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		down_read(&tree->lock);
+
+		err = ssdfs_btree_find_item(tree->generic_tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to find the fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_generic_fork;
+		}
+
+		err = ssdfs_change_extent_in_fork(blk, extent, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change extent in fork: err %d\n",
+				  err);
+			goto finish_change_generic_fork;
+		}
+
+		search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+
+		err = ssdfs_extents_tree_change_fork(tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change fork: err %d\n", err);
+			goto finish_change_generic_fork;
+		}
+
+finish_change_generic_fork:
+		up_read(&tree->lock);
+
+		ssdfs_btree_search_forget_parent_node(search);
+		ssdfs_btree_search_forget_child_node(search);
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		break;
+	}
+
+	return err;
+}
+
+/*
+ * ssdfs_shrink_found_extent() - shrink found extent
+ * @old_extent: old state of extent
+ * @found_extent: shrinking extent [in|out]
+ */
+static inline
+int ssdfs_shrink_found_extent(struct ssdfs_raw_extent *old_extent,
+			      struct ssdfs_raw_extent *found_extent)
+{
+	u64 seg_id1, seg_id2;
+	u32 logical_blk1, logical_blk2;
+	u32 len1, len2;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!old_extent || !found_extent);
+
+	SSDFS_DBG("old_extent %p, found_extent %p\n",
+		  old_extent, found_extent);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	seg_id1 = le64_to_cpu(old_extent->seg_id);
+	logical_blk1 = le32_to_cpu(old_extent->logical_blk);
+	len1 = le32_to_cpu(old_extent->len);
+
+	seg_id2 = le64_to_cpu(found_extent->seg_id);
+	logical_blk2 = le32_to_cpu(found_extent->logical_blk);
+	len2 = le32_to_cpu(found_extent->len);
+
+	if (seg_id1 != seg_id2) {
+		SSDFS_ERR("invalid segment ID: "
+			  "old_extent (seg_id %llu, "
+			  "logical_blk %u, len %u), "
+			  "found_extent (seg_id %llu, "
+			  "logical_blk %u, len %u)\n",
+			  seg_id1, logical_blk1, len1,
+			  seg_id2, logical_blk2, len2);
+		return -ERANGE;
+	}
+
+	if (logical_blk1 != logical_blk2) {
+		SSDFS_ERR("invalid old extent: "
+			  "old_extent (seg_id %llu, "
+			  "logical_blk %u, len %u), "
+			  "found_extent (seg_id %llu, "
+			  "logical_blk %u, len %u)\n",
+			  seg_id1, logical_blk1, len1,
+			  seg_id2, logical_blk2, len2);
+		return -ERANGE;
+	} else {
+		if (len1 > len2) {
+			SSDFS_ERR("invalid length of old extent: "
+				  "old_extent (seg_id %llu, "
+				  "logical_blk %u, len %u), "
+				  "found_extent (seg_id %llu, "
+				  "logical_blk %u, len %u)\n",
+				  seg_id1, logical_blk1, len1,
+				  seg_id2, logical_blk2, len2);
+			return -ERANGE;
+		} else if (len1 < len2) {
+			/* shrink extent */
+			found_extent->len = cpu_to_le32(len2 - len1);
+		} else {
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("extent is empty: "
+				  "old_extent (seg_id %llu, "
+				  "logical_blk %u, len %u), "
+				  "found_extent (seg_id %llu, "
+				  "logical_blk %u, len %u)\n",
+				  seg_id1, logical_blk1, len1,
+				  seg_id2, logical_blk2, len2);
+#endif /* CONFIG_SSDFS_DEBUG */
+			return -ENODATA;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_delete_extent_in_fork() - delete extent from the fork
+ * @blk: logical block number
+ * @search: search object
+ *
+ * This method tries to delete extent from the fork.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the tree.
+ * %-EFAULT     - fail to create the hole in the fork.
+ */
+static
+int ssdfs_delete_extent_in_fork(u64 blk,
+				struct ssdfs_btree_search *search,
+				struct ssdfs_raw_extent *extent)
+{
+	struct ssdfs_raw_fork *fork;
+	struct ssdfs_raw_extent *cur_extent = NULL;
+	size_t extent_size = sizeof(struct ssdfs_raw_extent);
+	u64 start_offset;
+	u64 blks_count;
+	u64 cur_blk;
+	u32 len;
+	int i;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!search || !extent);
+
+	SSDFS_DBG("blk %llu, search %p\n",
+		  blk, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_EMPTY_RESULT:
+		SSDFS_DBG("no fork in search object\n");
+		return -ENODATA;
+
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search object state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_size != sizeof(struct ssdfs_raw_fork) ||
+	    search->result.items_in_buffer != 1) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	fork = &search->raw.fork;
+	start_offset = le64_to_cpu(fork->start_offset);
+	blks_count = le64_to_cpu(fork->blks_count);
+
+	if (start_offset >= U64_MAX || blks_count >= U64_MAX) {
+		SSDFS_ERR("invalid fork state: "
+			  "start_offset %llu, blks_count %llu\n",
+			  start_offset, blks_count);
+		return -ENODATA;
+	}
+
+	if (blk >= U64_MAX) {
+		SSDFS_ERR("invalid request: blk %llu\n",
+			  blk);
+		return -ERANGE;
+	}
+
+	if (start_offset <= blk && blk < (start_offset + blks_count)) {
+		/*
+		 * Expected state
+		 */
+	} else {
+		SSDFS_ERR("blk %llu is out of fork\n",
+			  blk);
+		return -ERANGE;
+	}
+
+	cur_blk = le64_to_cpu(fork->start_offset);
+	for (i = 0; i < SSDFS_INLINE_EXTENTS_COUNT; i++) {
+		len = le32_to_cpu(fork->extents[i].len);
+
+		if (cur_blk == blk) {
+			/* extent is found */
+			cur_extent = &fork->extents[i];
+			break;
+		} else if (blk < cur_blk) {
+			SSDFS_ERR("invalid extent: "
+				  "blk %llu, cur_blk %llu\n",
+				  blk, cur_blk);
+			return -ERANGE;
+		} else if (len >= U32_MAX || len == 0) {
+			/* empty extent */
+			break;
+		} else {
+			/* it needs to check the next extent */
+			cur_blk += len;
+		}
+	}
+
+	if (!cur_extent) {
+		SSDFS_ERR("fail to find the extent: blk %llu\n",
+			  blk);
+		return -ERANGE;
+	}
+
+	ssdfs_memcpy(extent, 0, extent_size,
+		     cur_extent, 0, extent_size,
+		     extent_size);
+
+	len = le32_to_cpu(fork->extents[i].len);
+
+	if (i < (SSDFS_INLINE_EXTENTS_COUNT - 1)) {
+		err = ssdfs_memmove(fork->extents,
+				    i * extent_size,
+				    SSDFS_INLINE_EXTENTS_COUNT * extent_size,
+				    fork->extents,
+				    (i + 1) * extent_size,
+				    SSDFS_INLINE_EXTENTS_COUNT * extent_size,
+				    (SSDFS_INLINE_EXTENTS_COUNT - i) *
+					extent_size);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to move: err %d\n", err);
+			return err;
+		}
+	} else {
+		memset(&fork->extents[i], 0xFF, extent_size);
+	}
+
+	if (len >= U32_MAX || len == 0) {
+		/*
+		 * Do nothing. Empty extent.
+		 */
+	} else if (blks_count < len) {
+		SSDFS_ERR("blks_count %llu < len %u\n",
+			  blks_count, len);
+		return -ERANGE;
+	}
+
+	blks_count -= len;
+	fork->blks_count = cpu_to_le64(blks_count);
+
+	if (blks_count == 0) {
+		fork->start_offset = cpu_to_le64(U64_MAX);
+		SSDFS_DBG("empty fork\n");
+		return -ENODATA;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_move_extent() - move extent (ZNS SSD)
+ * @tree: extents tree
+ * @blk: logical block number
+ * @old_extent: old extent object
+ * @new_extent: new extent object
+ * @search: search object
+ *
+ * This method tries to change @old_extent on @new_extent in the @tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the tree.
+ */
+int ssdfs_extents_tree_move_extent(struct ssdfs_extents_btree_info *tree,
+				   u64 blk,
+				   struct ssdfs_raw_extent *old_extent,
+				   struct ssdfs_raw_extent *new_extent,
+				   struct ssdfs_btree_search *search)
+{
+	struct ssdfs_raw_extent extent;
+	u64 new_blk;
+	u32 len;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !old_extent || !new_extent || !search);
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+
+	if (need_initialize_extent_btree_search(blk, search)) {
+		ssdfs_btree_search_init(search);
+		search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+		search->request.flags =
+			SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+		search->request.start.hash = blk;
+		search->request.end.hash = blk;
+		search->request.count = 1;
+	}
+
+	down_write(&tree->lock);
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		err = ssdfs_extents_tree_find_inline_fork(tree, blk, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to find the inline fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		}
+
+		err = ssdfs_delete_extent_in_fork(blk, search,
+						  &extent);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete extent in fork: err %d\n",
+				  err);
+			goto finish_change_fork;
+		}
+
+		err = ssdfs_shrink_found_extent(old_extent, &extent);
+		if (err == -ENODATA) {
+			/*
+			 * Extent is empty. Do nothing.
+			 */
+			err = 0;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to shrink extent: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		} else {
+			len = le32_to_cpu(old_extent->len);
+			new_blk = blk + len;
+
+			err = ssdfs_add_extent_into_fork(new_blk,
+							 &extent,
+							 search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_change_fork;
+			}
+
+			ssdfs_debug_btree_search_object(search);
+
+			search->request.type = SSDFS_BTREE_SEARCH_ADD_ITEM;
+			err = ssdfs_extents_tree_add_inline_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add fork: err %d\n", err);
+				goto finish_change_fork;
+			}
+		}
+
+		err = ssdfs_extents_tree_add_extent_nolock(tree, blk,
+							   new_extent,
+							   search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to add extent: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		}
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		err = ssdfs_btree_find_item(tree->generic_tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to find the fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		}
+
+		err = ssdfs_delete_extent_in_fork(blk, search,
+						  &extent);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete extent in fork: err %d\n",
+				  err);
+			goto finish_change_fork;
+		}
+
+		err = ssdfs_shrink_found_extent(old_extent, &extent);
+		if (err == -ENODATA) {
+			/*
+			 * Extent is empty. Do nothing.
+			 */
+			err = 0;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to shrink extent: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		} else {
+			len = le32_to_cpu(old_extent->len);
+			new_blk = blk + len;
+
+			err = ssdfs_add_extent_into_fork(new_blk,
+							 &extent,
+							 search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent into fork: "
+					  "err %d\n",
+					  err);
+				goto finish_change_fork;
+			}
+
+			ssdfs_debug_btree_search_object(search);
+
+			err = ssdfs_extents_tree_add_extent_nolock(tree,
+								   new_blk,
+								   &extent,
+								   search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add extent: "
+					  "blk %llu, err %d\n",
+					  new_blk, err);
+				goto finish_change_fork;
+			}
+		}
+
+		err = ssdfs_extents_tree_add_extent_nolock(tree, blk,
+							   new_extent,
+							   search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to add extent: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_change_fork;
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		break;
+	}
+
+finish_change_fork:
+	up_write(&tree->lock);
+
+	ssdfs_btree_search_forget_parent_node(search);
+	ssdfs_btree_search_forget_child_node(search);
+
+	ssdfs_debug_extents_btree_object(tree);
+
+	return err;
+}
+
+/*
+ * ssdfs_truncate_extent_in_fork() - truncate the extent in the fork
+ * @blk: logical block number
+ * @new_len: new length of the extent
+ * @search: search object
+ * @fork: truncated fork [out]
+ *
+ * This method tries to truncate the extent in the fork.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - no extents in the fork.
+ * %-ENOSPC     - invalid @new_len of the extent.
+ * %-EFAULT     - extent doesn't exist in the fork.
+ */
+static
+int ssdfs_truncate_extent_in_fork(u64 blk, u32 new_len,
+				  struct ssdfs_btree_search *search,
+				  struct ssdfs_raw_fork *fork)
+{
+	struct ssdfs_raw_fork *cur_fork;
+	struct ssdfs_raw_extent *cur_extent = NULL;
+	u64 start_offset;
+	u64 blks_count;
+	u32 len, len_diff;
+	u64 cur_blk;
+	u64 rest_len;
+	u32 logical_blk;
+	int i, j;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON( !search || !fork);
+
+	SSDFS_DBG("blk %llu, new_len %u, search %p\n",
+		  blk, new_len, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_EMPTY_RESULT:
+		SSDFS_DBG("no fork in search object\n");
+		return -EFAULT;
+
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid search object state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_size != sizeof(struct ssdfs_raw_fork) ||
+	    search->result.items_in_buffer != 1) {
+		SSDFS_ERR("invalid search buffer state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	memset(fork, 0xFF, sizeof(struct ssdfs_raw_fork));
+
+	cur_fork = &search->raw.fork;
+	start_offset = le64_to_cpu(cur_fork->start_offset);
+	blks_count = le64_to_cpu(cur_fork->blks_count);
+
+	if (start_offset >= U64_MAX || blks_count >= U64_MAX) {
+		SSDFS_ERR("invalid fork state: "
+			  "start_offset %llu, blks_count %llu\n",
+			  start_offset, blks_count);
+		return -ERANGE;
+	}
+
+	if (blks_count == 0) {
+		SSDFS_ERR("empty fork: blks_count %llu\n",
+			  blks_count);
+		return -ENODATA;
+	}
+
+	if (blk >= U64_MAX) {
+		SSDFS_ERR("invalid extent: blk %llu\n",
+			  blk);
+		return -ERANGE;
+	}
+
+	if (start_offset <= blk && blk < (start_offset + blks_count)) {
+		/*
+		 * Expected state
+		 */
+	} else {
+		SSDFS_ERR("extent is out of fork: \n"
+			  "fork (start %llu, blks_count %llu), "
+			  "extent (blk %llu, len %u)\n",
+			  start_offset, blks_count,
+			  blk, new_len);
+		return -EFAULT;
+	}
+
+	cur_blk = le64_to_cpu(cur_fork->start_offset);
+	for (i = 0; i < SSDFS_INLINE_EXTENTS_COUNT; i++) {
+		len = le32_to_cpu(cur_fork->extents[i].len);
+
+		if (len >= U32_MAX || len == 0) {
+			/* empty extent */
+			break;
+		} else if (cur_blk <= blk && blk < (cur_blk + len)) {
+			/* extent is found */
+			cur_extent = &cur_fork->extents[i];
+			break;
+		} else if (blk < cur_blk) {
+			SSDFS_ERR("invalid extent: "
+				  "blk %llu, cur_blk %llu\n",
+				  blk, cur_blk);
+			return -EFAULT;
+		} else {
+			/* it needs to check the next extent */
+			cur_blk += len;
+		}
+	}
+
+	if (!cur_extent) {
+		SSDFS_ERR("fail to find the extent: blk %llu\n",
+			  blk);
+		return -EFAULT;
+	}
+
+	rest_len = blks_count - (blk - start_offset);
+
+	if (new_len > rest_len) {
+		SSDFS_ERR("fail to grow extent's size: "
+			  "rest_len %llu, new_len %u\n",
+			  rest_len, new_len);
+		return -ENOSPC;
+	} else if (new_len == rest_len) {
+		SSDFS_WARN("nothing should be done: "
+			   "rest_len %llu, new_len %u\n",
+			   rest_len, new_len);
+		return 0;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(i >= SSDFS_INLINE_EXTENTS_COUNT);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fork->start_offset = cpu_to_le64(blk);
+	fork->blks_count = cpu_to_le64(0);
+
+	for (j = 0; i < SSDFS_INLINE_EXTENTS_COUNT; i++) {
+		cur_extent = &cur_fork->extents[i];
+		len = le32_to_cpu(cur_extent->len);
+
+		if ((cur_blk + len) < blk) {
+			/* pass on this extent */
+			continue;
+		} else if ((blk + new_len) <= cur_blk) {
+			ssdfs_memcpy(&fork->extents[j],
+				     0, sizeof(struct ssdfs_raw_extent),
+				     cur_extent,
+				     0, sizeof(struct ssdfs_raw_extent),
+				     sizeof(struct ssdfs_raw_extent));
+			le64_add_cpu(&fork->blks_count, len);
+			j++;
+
+			/* clear extent */
+			memset(cur_extent, 0xFF,
+				sizeof(struct ssdfs_raw_extent));
+		} else {
+#ifdef CONFIG_SSDFS_DEBUG
+			BUG_ON((blk - cur_blk) >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+			len_diff = len - (u32)(blk - cur_blk);
+
+			if (len_diff <= new_len) {
+				/*
+				 * leave the extent unchanged
+				 */
+			} else {
+				len_diff = (cur_blk + len) - (blk + new_len);
+
+				fork->extents[j].seg_id = cur_extent->seg_id;
+				logical_blk =
+					le32_to_cpu(cur_extent->logical_blk);
+				logical_blk += len - len_diff;
+				fork->extents[j].logical_blk =
+						cpu_to_le32(logical_blk);
+				fork->extents[j].len = cpu_to_le32(len_diff);
+				le64_add_cpu(&fork->blks_count, len_diff);
+				j++;
+
+				/* shrink extent */
+				cur_extent->len = cpu_to_le32(len - len_diff);
+			}
+		}
+
+		cur_blk += len;
+
+		if (cur_blk >= (start_offset + blks_count))
+			break;
+	}
+
+	blks_count -= rest_len - new_len;
+
+	if (blks_count == 0) {
+		cur_fork->blks_count = cpu_to_le64(0);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("empty fork: blks_count %llu\n",
+			  blks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		return -ENODATA;
+	} else
+		cur_fork->blks_count = cpu_to_le64(blks_count);
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_delete_inline_fork() - delete inline fork
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to delete the inline fork from the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - fork doesn't exist in the tree.
+ * %-ENOENT     - no more forks in the tree.
+ */
+static
+int ssdfs_extents_tree_delete_inline_fork(struct ssdfs_extents_btree_info *tree,
+					  struct ssdfs_btree_search *search)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_fork *fork;
+	size_t fork_size = sizeof(struct ssdfs_raw_fork);
+	size_t inline_forks_size = fork_size * SSDFS_INLINE_FORKS_COUNT;
+	ino_t ino;
+	u64 start_hash;
+	s64 forks_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->inline_forks) {
+		SSDFS_ERR("empty inline tree %p\n",
+			  tree->inline_forks);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	if (!search->result.buf) {
+		SSDFS_ERR("empty buffer pointer\n");
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+
+	switch (search->result.state) {
+	case SSDFS_BTREE_SEARCH_VALID_ITEM:
+		if (start_hash != le64_to_cpu(search->raw.fork.start_offset)) {
+			SSDFS_ERR("corrupted fork: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash,
+				  le64_to_cpu(search->raw.fork.start_offset),
+				  le64_to_cpu(search->raw.fork.blks_count));
+			return -ERANGE;
+		}
+		break;
+
+	case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+		if (start_hash >= le64_to_cpu(search->raw.fork.start_offset)) {
+			SSDFS_ERR("corrupted fork: "
+				  "start_hash %llx, "
+				  "fork (start %llu, blks_count %llu)\n",
+				  start_hash,
+				  le64_to_cpu(search->raw.fork.start_offset),
+				  le64_to_cpu(search->raw.fork.blks_count));
+			return -ERANGE;
+		}
+		break;
+
+	default:
+		SSDFS_WARN("unexpected result state %#x\n",
+			   search->result.state);
+		return -ERANGE;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+	if (forks_count == 0) {
+		SSDFS_DBG("empty tree\n");
+		return -ENOENT;
+	} else if (forks_count > SSDFS_INLINE_FORKS_COUNT) {
+		SSDFS_ERR("invalid forks count %lld\n",
+			  forks_count);
+		return -ERANGE;
+	} else
+		atomic64_dec(&tree->forks_count);
+
+	if (search->result.start_index >= forks_count) {
+		SSDFS_ERR("invalid search result: "
+			  "start_index %u, forks_count %lld\n",
+			  search->result.start_index,
+			  forks_count);
+		return -ENODATA;
+	}
+
+	err = ssdfs_invalidate_inline_tail_forks(tree, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to invalidate inline tail forks: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	if (search->result.start_index < (forks_count - 1)) {
+		u16 index = search->result.start_index;
+
+		err = ssdfs_memmove(tree->inline_forks,
+				    (size_t)index * fork_size,
+				    inline_forks_size,
+				    tree->inline_forks,
+				    (size_t)(index + 1) * fork_size,
+				    inline_forks_size,
+				    (forks_count - index) * fork_size);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to move: err %d\n", err);
+			return err;
+		}
+
+		index = forks_count - 1;
+		fork = &tree->inline_forks[index];
+		memset(fork, 0xFF, sizeof(struct ssdfs_raw_fork));
+	}
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("forks_count %lld\n", forks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (forks_count == 0) {
+		SSDFS_DBG("tree is empty now\n");
+	} else if (forks_count < 0) {
+		SSDFS_WARN("invalid forks_count %lld\n",
+			   forks_count);
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_delete_fork() - delete generic fork
+ * @tree: extents tree
+ * @search: search object
+ *
+ * This method tries to delete the generic fork from the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - fork doesn't exist in the tree.
+ * %-ENOENT     - no more forks in the tree.
+ */
+static
+int ssdfs_extents_tree_delete_fork(struct ssdfs_extents_btree_info *tree,
+				   struct ssdfs_btree_search *search)
+{
+	u64 start_hash;
+	s64 forks_count;
+	u64 blks_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->generic_tree) {
+		SSDFS_ERR("empty generic tree %p\n",
+			  tree->generic_tree);
+		return -ERANGE;
+	}
+
+	if (search->result.state != SSDFS_BTREE_SEARCH_VALID_ITEM) {
+		SSDFS_ERR("invalid search result's state %#x\n",
+			  search->result.state);
+		return -ERANGE;
+	}
+
+	if (search->result.buf_state != SSDFS_BTREE_SEARCH_INLINE_BUFFER) {
+		SSDFS_ERR("invalid buf_state %#x\n",
+			  search->result.buf_state);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	if (start_hash != le64_to_cpu(search->raw.fork.start_offset)) {
+		SSDFS_ERR("corrupted fork: "
+			  "start_hash %llx, "
+			  "fork (start %llu, blks_count %llu)\n",
+			  start_hash,
+			  le64_to_cpu(search->raw.fork.start_offset),
+			  le64_to_cpu(search->raw.fork.blks_count));
+		return -ERANGE;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+	if (forks_count == 0) {
+		SSDFS_DBG("empty tree\n");
+		return -ENOENT;
+	}
+
+	if (search->result.start_index >= forks_count) {
+		SSDFS_ERR("invalid search result: "
+			  "start_index %u, forks_count %lld\n",
+			  search->result.start_index,
+			  forks_count);
+		return -ENODATA;
+	}
+
+	blks_count = le64_to_cpu(search->raw.fork.blks_count);
+	if (!(blks_count == 0 || blks_count >= U64_MAX)) {
+		SSDFS_ERR("fork is empty: "
+			  "blks_count %llu\n",
+			  blks_count);
+		return -ERANGE;
+	}
+
+	err = ssdfs_btree_delete_item(tree->generic_tree,
+				      search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to delete the fork from the tree: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("forks_count %lld\n", forks_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (forks_count == 0) {
+		SSDFS_DBG("tree is empty now\n");
+		return -ENOENT;
+	} else if (forks_count < 0) {
+		SSDFS_WARN("invalid forks_count %lld\n",
+			   forks_count);
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		return -ERANGE;
+	}
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	return 0;
+}
+
+/*
+ * ssdfs_migrate_generic2inline_tree() - convert generic tree into inline
+ * @tree: extents tree
+ *
+ * This method tries to convert the generic tree into inline one.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - the tree cannot be converted into inline again.
+ */
+static
+int ssdfs_migrate_generic2inline_tree(struct ssdfs_extents_btree_info *tree)
+{
+	struct ssdfs_raw_fork inline_forks[SSDFS_INLINE_FORKS_COUNT];
+	struct ssdfs_btree_search *search;
+	size_t fork_size = sizeof(struct ssdfs_raw_fork);
+	s64 forks_count, forks_capacity;
+	u64 start_hash = 0, end_hash = 0;
+	u64 blks_count = 0;
+	int private_flags;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p\n", tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	forks_count = atomic64_read(&tree->forks_count);
+
+	if (!tree->owner) {
+		SSDFS_ERR("empty owner inode\n");
+		return -ERANGE;
+	}
+
+	private_flags = atomic_read(&tree->owner->private_flags);
+
+	forks_capacity = SSDFS_INLINE_FORKS_COUNT;
+	if (private_flags & SSDFS_INODE_HAS_XATTR_BTREE)
+		forks_capacity--;
+
+	if (private_flags & SSDFS_INODE_HAS_INLINE_EXTENTS) {
+		SSDFS_ERR("the extents tree is not generic\n");
+		return -ERANGE;
+	}
+
+	if (forks_count > forks_capacity) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("forks_count %lld > forks_capacity %lld\n",
+			  forks_count, forks_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOSPC;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(tree->inline_forks || !tree->generic_tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	tree->generic_tree = NULL;
+
+	search = ssdfs_btree_search_alloc();
+	if (!search) {
+		SSDFS_ERR("fail to allocate btree search object\n");
+		return -ENOMEM;
+	}
+
+	ssdfs_btree_search_init(search);
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_RANGE;
+	search->request.flags = 0;
+	search->request.start.hash = U64_MAX;
+	search->request.end.hash = U64_MAX;
+	search->request.count = 0;
+
+	err = ssdfs_btree_get_head_range(&tree->buffer.tree,
+					 forks_count, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to extract forks: "
+			  "forks_count %lld, err %d\n",
+			  forks_count, err);
+		goto finish_process_range;
+	} else if (forks_count != search->result.items_in_buffer) {
+		err = -ERANGE;
+		SSDFS_ERR("forks_count %lld != items_in_buffer %u\n",
+			  forks_count,
+			  search->result.items_in_buffer);
+		goto finish_process_range;
+	}
+
+	if (search->result.state != SSDFS_BTREE_SEARCH_VALID_ITEM) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid search result's state %#x\n",
+			  search->result.state);
+		goto finish_process_range;
+	}
+
+	memset(inline_forks, 0xFF, fork_size * SSDFS_INLINE_FORKS_COUNT);
+
+	if (search->result.buf_size != (fork_size * forks_count) ||
+	    search->result.items_in_buffer != forks_count) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid search result: "
+			  "buf_size %zu, items_in_buffer %u, "
+			  "forks_count %lld\n",
+			  search->result.buf_size,
+			  search->result.items_in_buffer,
+			  forks_count);
+		goto finish_process_range;
+	}
+
+	switch (search->result.buf_state) {
+	case SSDFS_BTREE_SEARCH_INLINE_BUFFER:
+		ssdfs_memcpy(inline_forks,
+			     0, fork_size * SSDFS_INLINE_FORKS_COUNT,
+			     &search->raw.fork,
+			     0, fork_size,
+			     fork_size);
+		break;
+
+	case SSDFS_BTREE_SEARCH_EXTERNAL_BUFFER:
+		if (!search->result.buf) {
+			err = -ERANGE;
+			SSDFS_ERR("empty buffer\n");
+			goto finish_process_range;
+		}
+
+		err = ssdfs_memcpy(inline_forks,
+				   0, fork_size * SSDFS_INLINE_FORKS_COUNT,
+				   search->result.buf,
+				   0, search->result.buf_size,
+				   fork_size * forks_count);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to copy: err %d\n", err);
+			goto finish_process_range;
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid buffer's state %#x\n",
+			  search->result.buf_state);
+		goto finish_process_range;
+	}
+
+	start_hash = le64_to_cpu(inline_forks[0].start_offset);
+	if (forks_count > 1) {
+		end_hash =
+		    le64_to_cpu(inline_forks[forks_count - 1].start_offset);
+		blks_count =
+		    le64_to_cpu(inline_forks[forks_count - 1].blks_count);
+	} else {
+		end_hash = start_hash;
+		blks_count = le64_to_cpu(inline_forks[0].blks_count);
+	}
+
+	if (blks_count == 0 || blks_count >= U64_MAX) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid blks_count %llu\n",
+			  blks_count);
+		goto finish_process_range;
+	}
+
+	end_hash += blks_count - 1;
+
+	search->request.type = SSDFS_BTREE_SEARCH_DELETE_RANGE;
+	search->request.flags = SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+				SSDFS_BTREE_SEARCH_HAS_VALID_COUNT |
+				SSDFS_BTREE_SEARCH_NOT_INVALIDATE;
+	search->request.start.hash = start_hash;
+	search->request.end.hash = end_hash;
+	search->request.count = forks_count;
+
+	err = ssdfs_btree_delete_range(&tree->buffer.tree, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to delete range: "
+			  "start_hash %llx, end_hash %llx, count %u, "
+			  "err %d\n",
+			  search->request.start.hash,
+			  search->request.end.hash,
+			  search->request.count,
+			  err);
+		goto finish_process_range;
+	}
+
+	if (!is_ssdfs_btree_empty(&tree->buffer.tree)) {
+		err = -ERANGE;
+		SSDFS_WARN("extents tree is not empty\n");
+		atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_CORRUPTED);
+		goto finish_process_range;
+	}
+
+	err = ssdfs_btree_destroy_node_range(&tree->buffer.tree,
+					     0);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to destroy nodes' range: err %d\n",
+			  err);
+		goto finish_process_range;
+	}
+
+finish_process_range:
+	ssdfs_btree_search_free(search);
+
+	if (unlikely(err))
+		return err;
+
+	ssdfs_btree_destroy(&tree->buffer.tree);
+
+	err = ssdfs_memcpy(tree->buffer.forks,
+			   0, fork_size * SSDFS_INLINE_FORKS_COUNT,
+			   inline_forks,
+			   0, fork_size * SSDFS_INLINE_FORKS_COUNT,
+			   fork_size * forks_count);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to copy: err %d\n", err);
+		return err;
+	}
+
+	atomic_set(&tree->type, SSDFS_INLINE_FORKS_ARRAY);
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	tree->inline_forks = tree->buffer.forks;
+
+	atomic64_set(&tree->forks_count, forks_count);
+
+	atomic_and(~SSDFS_INODE_HAS_EXTENTS_BTREE,
+		   &tree->owner->private_flags);
+	atomic_or(SSDFS_INODE_HAS_INLINE_EXTENTS,
+		  &tree->owner->private_flags);
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_truncate_extent() - truncate the extent in the tree
+ * @tree: extent tree
+ * @blk: logical block number
+ * @new_len: new length of the extent
+ * @search: search object
+ *
+ * This method tries to truncate the extent in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the tree.
+ * %-ENOSPC     - invalid @new_len of the extent.
+ * %-EFAULT     - fail to create the hole in the fork.
+ */
+int ssdfs_extents_tree_truncate_extent(struct ssdfs_extents_btree_info *tree,
+					u64 blk, u32 new_len,
+					struct ssdfs_btree_search *search)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_fork fork;
+	u64 blks_count;
+	ino_t ino;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !search);
+
+	SSDFS_DBG("tree %p, search %p, blk %llu, new_len %u\n",
+		  tree, search, blk, new_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+
+	if (need_initialize_extent_btree_search(blk, search)) {
+		ssdfs_btree_search_init(search);
+		search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+		search->request.flags =
+			SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+		search->request.start.hash = blk;
+		search->request.end.hash = blk;
+		search->request.count = 1;
+	}
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		down_write(&tree->lock);
+
+		err = ssdfs_extents_tree_find_inline_fork(tree, blk, search);
+		if (err == -ENODATA) {
+			switch (search->result.state) {
+			case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+				/* hole case -> continue truncation */
+				break;
+
+			case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+				/* inflation case -> nothing has to be done */
+				err = 0;
+				goto finish_truncate_inline_fork;
+
+			default:
+				SSDFS_ERR("fail to find the inline fork: "
+					  "blk %llu, err %d\n",
+					  blk, err);
+				goto finish_truncate_inline_fork;
+			}
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find the inline fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_truncate_inline_fork;
+		}
+
+		switch (search->result.state) {
+		case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+			search->request.type =
+				SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+			err = ssdfs_extents_tree_delete_inline_fork(tree,
+								   search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to delete fork: err %d\n", err);
+				goto finish_truncate_inline_fork;
+			}
+			break;
+
+		case SSDFS_BTREE_SEARCH_VALID_ITEM:
+			err = ssdfs_truncate_extent_in_fork(blk, new_len,
+							    search, &fork);
+			if (err == -ENODATA) {
+				/*
+				 * The truncating  fork is empty.
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to change extent in fork: "
+					  "err %d\n",
+					  err);
+				goto finish_truncate_inline_fork;
+			}
+
+			if (err == -ENODATA) {
+				search->request.type =
+					SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+				err =
+				    ssdfs_extents_tree_delete_inline_fork(tree,
+									search);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to delete fork: "
+						  "err %d\n", err);
+					goto finish_truncate_inline_fork;
+				}
+			} else {
+				search->request.type =
+					SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+				err =
+				    ssdfs_extents_tree_change_inline_fork(tree,
+									search);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to change fork: "
+						  "err %d\n", err);
+					goto finish_truncate_inline_fork;
+				}
+			}
+
+			blks_count = le64_to_cpu(fork.blks_count);
+
+			if (blks_count == 0 || blks_count >= U64_MAX) {
+				/*
+				 * empty fork -> do nothing
+				 */
+			} else {
+				err =
+				    ssdfs_shextree_add_pre_invalid_fork(shextree,
+									ino,
+									&fork);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to pre-invalidate: "
+						  "(start_offset %llu, "
+						  "blks_count %llu), err %d\n",
+						le64_to_cpu(fork.start_offset),
+						le64_to_cpu(fork.blks_count),
+						err);
+					goto finish_truncate_inline_fork;
+				}
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid result state %#x\n",
+				  search->result.state);
+			goto finish_truncate_inline_fork;
+		}
+
+finish_truncate_inline_fork:
+		up_write(&tree->lock);
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		down_read(&tree->lock);
+
+		err = ssdfs_btree_find_item(tree->generic_tree, search);
+		if (err == -ENODATA) {
+			switch (search->result.state) {
+			case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+				/* hole case -> continue truncation */
+				break;
+
+			case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+			case SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE:
+				if (is_last_leaf_node_found(search)) {
+					/*
+					 * inflation case
+					 * nothing has to be done
+					 */
+					err = 0;
+					goto finish_truncate_generic_fork;
+				} else {
+					/*
+					 * hole case
+					 * continue truncation
+					 */
+				}
+				break;
+
+			default:
+				SSDFS_ERR("fail to find the fork: "
+					  "blk %llu, err %d\n",
+					  blk, err);
+				goto finish_truncate_generic_fork;
+			}
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find the fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_truncate_generic_fork;
+		}
+
+		switch (search->result.state) {
+		case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+			search->request.type =
+				SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+			err = ssdfs_extents_tree_delete_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to delete fork: err %d\n", err);
+				goto finish_truncate_generic_fork;
+			}
+			break;
+
+		case SSDFS_BTREE_SEARCH_VALID_ITEM:
+			err = ssdfs_truncate_extent_in_fork(blk, new_len,
+							    search, &fork);
+			if (err == -ENODATA) {
+				/*
+				 * The truncating fork is empty.
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to change extent in fork: "
+					  "err %d\n", err);
+				goto finish_truncate_generic_fork;
+			}
+
+			if (err == -ENODATA) {
+				search->request.type =
+					SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+				err = ssdfs_extents_tree_delete_fork(tree,
+								     search);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to delete fork: "
+						  "err %d\n", err);
+					goto finish_truncate_generic_fork;
+				}
+			} else {
+				search->request.type =
+					SSDFS_BTREE_SEARCH_INVALIDATE_TAIL;
+				err = ssdfs_extents_tree_change_fork(tree,
+								     search);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to change fork: "
+						  "err %d\n", err);
+					goto finish_truncate_generic_fork;
+				}
+			}
+
+			blks_count = le64_to_cpu(fork.blks_count);
+
+			if (blks_count == 0 || blks_count >= U64_MAX) {
+				/*
+				 * empty fork -> do nothing
+				 */
+			} else {
+				err =
+				 ssdfs_shextree_add_pre_invalid_fork(shextree,
+								     ino,
+								     &fork);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to pre-invalidate: "
+						  "(start_offset %llu, "
+						  "blks_count %llu), err %d\n",
+						le64_to_cpu(fork.start_offset),
+						le64_to_cpu(fork.blks_count),
+						err);
+					goto finish_truncate_generic_fork;
+				}
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid result state %#x\n",
+				  search->result.state);
+			goto finish_truncate_generic_fork;
+		}
+
+finish_truncate_generic_fork:
+		up_read(&tree->lock);
+
+		ssdfs_btree_search_forget_parent_node(search);
+		ssdfs_btree_search_forget_child_node(search);
+
+		if (unlikely(err))
+			return err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("forks_count %lld\n",
+			  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (!err &&
+		    need_migrate_generic2inline_btree(tree->generic_tree, 1)) {
+			down_write(&tree->lock);
+			err = ssdfs_migrate_generic2inline_tree(tree);
+			up_write(&tree->lock);
+
+			if (err == -ENOSPC) {
+				/* continue to use the generic tree */
+				err = 0;
+				SSDFS_DBG("unable to re-create inline tree\n");
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to re-create inline tree: "
+					  "err %d\n",
+					  err);
+			}
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		break;
+	}
+
+	return err;
+}
+
+static int
+ssdfs_extents_tree_delete_inline_extent(struct ssdfs_extents_btree_info *tree,
+					u64 blk,
+					struct ssdfs_raw_extent *extent,
+					struct ssdfs_btree_search *search)
+{
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !extent || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+
+	err = ssdfs_extents_tree_find_inline_fork(tree, blk, search);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to find the inline fork: "
+			  "blk %llu, err %d\n",
+			  blk, err);
+		return err;
+	}
+
+	err = ssdfs_delete_extent_in_fork(blk, search, extent);
+	if (err == -ENODATA) {
+		/*
+		 * The fork doesn't contain any extents.
+		 */
+	} else if (unlikely(err)) {
+		SSDFS_ERR("fail to delete extent in fork: err %d\n",
+			  err);
+		return err;
+	}
+
+	if (err == -ENODATA) {
+		search->request.type = SSDFS_BTREE_SEARCH_DELETE_ITEM;
+		err = ssdfs_extents_tree_delete_inline_fork(tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete fork: err %d\n", err);
+			return err;
+		}
+	} else {
+		search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+		err = ssdfs_extents_tree_change_inline_fork(tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change fork: err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_delete_extent() - delete extent from the tree
+ * @tree: extents tree
+ * @blk: logical block number
+ * @search: search object
+ *
+ * This method tries to delete extent from the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - extent doesn't exist in the tree.
+ * %-EFAULT     - fail to create the hole in the fork.
+ */
+int ssdfs_extents_tree_delete_extent(struct ssdfs_extents_btree_info *tree,
+				     u64 blk,
+				     struct ssdfs_btree_search *search)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_extent extent;
+	ino_t ino;
+	u32 len;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi || !search);
+
+	SSDFS_DBG("tree %p, search %p, blk %llu\n",
+		  tree, search, blk);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+
+	if (need_initialize_extent_btree_search(blk, search)) {
+		ssdfs_btree_search_init(search);
+		search->request.type = SSDFS_BTREE_SEARCH_FIND_ITEM;
+		search->request.flags =
+			SSDFS_BTREE_SEARCH_HAS_VALID_HASH_RANGE |
+			SSDFS_BTREE_SEARCH_HAS_VALID_COUNT;
+		search->request.start.hash = blk;
+		search->request.end.hash = blk;
+		search->request.count = 1;
+	}
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		down_write(&tree->lock);
+
+		err = ssdfs_extents_tree_delete_inline_extent(tree,
+							      blk,
+							      &extent,
+							      search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete inline extent: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_delete_inline_extent;
+		}
+
+		len = le32_to_cpu(extent.len);
+
+		if (len == 0 || len >= U32_MAX) {
+			/*
+			 * empty extent -> do nothing
+			 */
+		} else {
+			err = ssdfs_shextree_add_pre_invalid_extent(shextree,
+								    ino,
+								    &extent);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add pre-invalid extent "
+					  "(seg_id %llu, blk %u, len %u), "
+					  "err %d\n",
+					  le64_to_cpu(extent.seg_id),
+					  le32_to_cpu(extent.logical_blk),
+					  len, err);
+				goto finish_delete_inline_extent;
+			}
+		}
+
+finish_delete_inline_extent:
+		up_write(&tree->lock);
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		down_read(&tree->lock);
+
+		err = ssdfs_btree_find_item(tree->generic_tree, search);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to find the fork: "
+				  "blk %llu, err %d\n",
+				  blk, err);
+			goto finish_delete_generic_extent;
+		}
+
+		err = ssdfs_delete_extent_in_fork(blk, search,
+						  &extent);
+		if (err == -ENODATA) {
+			/*
+			 * The fork doesn't contain any extents.
+			 */
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to delete extent in fork: err %d\n",
+				  err);
+			goto finish_delete_generic_extent;
+		}
+
+		if (err == -ENODATA) {
+			search->request.type = SSDFS_BTREE_SEARCH_DELETE_ITEM;
+			err = ssdfs_extents_tree_delete_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to delete fork: err %d\n", err);
+				goto finish_delete_generic_extent;
+			}
+		} else {
+			search->request.type = SSDFS_BTREE_SEARCH_CHANGE_ITEM;
+			err = ssdfs_extents_tree_change_fork(tree, search);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to change fork: err %d\n", err);
+				goto finish_delete_generic_extent;
+			}
+		}
+
+finish_delete_generic_extent:
+		up_read(&tree->lock);
+
+		ssdfs_btree_search_forget_parent_node(search);
+		ssdfs_btree_search_forget_child_node(search);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("forks_count %lld\n",
+			  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (!err &&
+		    need_migrate_generic2inline_btree(tree->generic_tree, 1)) {
+			down_write(&tree->lock);
+			err = ssdfs_migrate_generic2inline_tree(tree);
+			up_write(&tree->lock);
+
+			if (err == -ENOSPC) {
+				/* continue to use the generic tree */
+				err = 0;
+				SSDFS_DBG("unable to re-create inline tree\n");
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to re-create inline tree: "
+					  "err %d\n",
+					  err);
+			}
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		break;
+	}
+
+	return err;
+}
+
+/*
+ * ssdfs_delete_all_inline_forks() - delete all inline forks
+ * @tree: extents tree
+ *
+ * This method tries to delete all inline forks in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOENT     - empty tree.
+ */
+static
+int ssdfs_delete_all_inline_forks(struct ssdfs_extents_btree_info *tree)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_shared_extents_tree *shextree;
+	struct ssdfs_raw_fork *fork;
+	struct ssdfs_raw_extent *extent;
+	u64 forks_count;
+	ino_t ino;
+	int i, j;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !tree->fsi);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p\n", tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = tree->fsi;
+	shextree = fsi->shextree;
+
+	if (!shextree) {
+		SSDFS_ERR("shared extents tree is absent\n");
+		return -ERANGE;
+	}
+
+	ino = tree->owner->vfs_inode.i_ino;
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's type %#x\n",
+			  atomic_read(&tree->type));
+		return -ERANGE;
+	}
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	if (!tree->inline_forks) {
+		SSDFS_ERR("empty inline forks %p\n",
+			  tree->inline_forks);
+		return -ERANGE;
+	}
+
+	forks_count = atomic64_read(&tree->forks_count);
+	if (forks_count == 0) {
+		SSDFS_DBG("empty tree\n");
+		return -ENOENT;
+	} else if (forks_count > SSDFS_INLINE_FORKS_COUNT) {
+		atomic_set(&tree->state,
+			   SSDFS_EXTENTS_BTREE_CORRUPTED);
+		SSDFS_ERR("extents tree is corupted: "
+			  "forks_count %llu",
+			  forks_count);
+		return -ERANGE;
+	}
+
+	for (i = 0; i < forks_count; i++) {
+		u64 blks_count;
+		u64 calculated = 0;
+
+		fork = &tree->inline_forks[i];
+		blks_count = le64_to_cpu(fork->blks_count);
+
+		if (blks_count == 0 || blks_count >= U64_MAX) {
+			atomic_set(&tree->state,
+				   SSDFS_EXTENTS_BTREE_CORRUPTED);
+			SSDFS_ERR("corrupted fork: blks_count %llu\n",
+				  blks_count);
+			return -ERANGE;
+		}
+
+		for (j = SSDFS_INLINE_EXTENTS_COUNT - 1; j >= 0; j--) {
+			u32 len;
+
+			extent = &fork->extents[j];
+			len = le32_to_cpu(extent->len);
+
+			if (len == 0 || len >= U32_MAX)
+				continue;
+
+			if ((calculated + len) > blks_count) {
+				atomic_set(&tree->state,
+					   SSDFS_EXTENTS_BTREE_CORRUPTED);
+				SSDFS_ERR("corrupted extent: "
+					  "calculated %llu, len %u, "
+					  "blks %llu\n",
+					  calculated, len, blks_count);
+				return -ERANGE;
+			}
+
+			err = ssdfs_shextree_add_pre_invalid_extent(shextree,
+								    ino,
+								    extent);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to add pre-invalid extent "
+					  "(seg_id %llu, blk %u, len %u), "
+					  "err %d\n",
+					  le64_to_cpu(extent->seg_id),
+					  le32_to_cpu(extent->logical_blk),
+					  len, err);
+				return err;
+			}
+		}
+
+		if (calculated != blks_count) {
+			atomic_set(&tree->state,
+				   SSDFS_EXTENTS_BTREE_CORRUPTED);
+			SSDFS_ERR("calculated %llu != blks_count %llu\n",
+				  calculated, blks_count);
+			return -ERANGE;
+		}
+	}
+
+	memset(tree->inline_forks, 0xFF,
+		sizeof(struct ssdfs_raw_fork) * SSDFS_INLINE_FORKS_COUNT);
+
+	atomic_set(&tree->state, SSDFS_EXTENTS_BTREE_DIRTY);
+	return 0;
+}
+
+/*
+ * ssdfs_extents_tree_delete_all() - delete all forks in the tree
+ * @tree: extents tree
+ *
+ * This method tries to delete all forks in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+int ssdfs_extents_tree_delete_all(struct ssdfs_extents_btree_info *tree)
+{
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree);
+
+	SSDFS_DBG("tree %p\n", tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&tree->state)) {
+	case SSDFS_EXTENTS_BTREE_CREATED:
+	case SSDFS_EXTENTS_BTREE_INITIALIZED:
+	case SSDFS_EXTENTS_BTREE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid extent tree's state %#x\n",
+			  atomic_read(&tree->state));
+		return -ERANGE;
+	};
+
+	switch (atomic_read(&tree->type)) {
+	case SSDFS_INLINE_FORKS_ARRAY:
+		down_write(&tree->lock);
+		err = ssdfs_delete_all_inline_forks(tree);
+		if (!err)
+			atomic64_set(&tree->forks_count, 0);
+		up_write(&tree->lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("forks_count %lld\n",
+			  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete all inline forks: "
+				  "err %d\n",
+				  err);
+		}
+		break;
+
+	case SSDFS_PRIVATE_EXTENTS_BTREE:
+		down_write(&tree->lock);
+		err = ssdfs_btree_delete_all(tree->generic_tree);
+		if (!err) {
+			atomic64_set(&tree->forks_count, 0);
+
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("forks_count %lld\n",
+				  atomic64_read(&tree->forks_count));
+#endif /* CONFIG_SSDFS_DEBUG */
+		}
+		up_write(&tree->lock);
+
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete the all forks: "
+				  "err %d\n",
+				  err);
+		}
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid extents tree type %#x\n",
+			  atomic_read(&tree->type));
+		break;
+	}
+
+	return err;
+}
-- 
2.34.1