From: Viacheslav Dubeyko <slava@dubeyko.com>
To: linux-fsdevel@vger.kernel.org
Cc: viacheslav.dubeyko@bytedance.com, luka.perkov@sartura.hr,
bruno.banelli@sartura.hr, Viacheslav Dubeyko <slava@dubeyko.com>
Subject: [RFC PATCH 49/76] ssdfs: b-tree API implementation
Date: Fri, 24 Feb 2023 17:09:00 -0800 [thread overview]
Message-ID: <20230225010927.813929-50-slava@dubeyko.com> (raw)
In-Reply-To: <20230225010927.813929-1-slava@dubeyko.com>
Generalized b-tree functionality implements API:
(1) create - create empty b-tree object
(2) destroy - destroy b-tree object
(3) flush - flush dirty b-tree object
(4) find_item - find item in b-tree hierarchy
(5) find_range - find range of items in b-tree hierarchy
(6) allocate_item - allocate item in existing b-tree's node
(7) allocate_range - allocate range of items in existing b-tree's node
(8) add_item - add item into b-tree
(9) add_range - add range of items into b-tree
(10) change_item - change existing item in b-tree
(11) delete_item - delete item from b-tree
(12) delete_range - delete range of items from b-tree
(13) delete_all - delete all items from 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/btree.c | 3713 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 3713 insertions(+)
diff --git a/fs/ssdfs/btree.c b/fs/ssdfs/btree.c
index d7778cdb67a1..f88f599a72df 100644
--- a/fs/ssdfs/btree.c
+++ b/fs/ssdfs/btree.c
@@ -4072,3 +4072,3716 @@ int ssdfs_btree_delete_node(struct ssdfs_btree *tree,
return err;
}
+
+/*
+ * node_needs_in_additional_check() - does it need to check the node?
+ * @err: error code
+ * @search: search object
+ */
+static inline
+bool node_needs_in_additional_check(int err,
+ struct ssdfs_btree_search *search)
+{
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return err == -ENODATA &&
+ search->result.state == SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+}
+
+/*
+ * ssdfs_btree_switch_on_hybrid_parent_node() - change current node
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to change the current node on hybrid parent one.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ * %-ENODATA - item can be added.
+ * %-ENOENT - no space for a new item.
+ */
+static
+int ssdfs_btree_switch_on_hybrid_parent_node(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *node;
+ int state;
+ u64 start_hash, end_hash;
+ u16 items_count, items_capacity;
+ u16 free_items;
+ u16 flags;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+
+ SSDFS_DBG("tree %p, type %#x, "
+ "request->type %#x, request->flags %#x, "
+ "result->err %d, result->state %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type,
+ search->request.type, search->request.flags,
+ search->result.err,
+ search->result.state,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (search->result.err != -ENODATA) {
+ SSDFS_ERR("unexpected result's error %d\n",
+ search->result.err);
+ return -ERANGE;
+ }
+
+ if (search->result.state != SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE) {
+ SSDFS_ERR("unexpected result's state %#x\n",
+ search->result.state);
+ return -ERANGE;
+ }
+
+ if (search->request.start.hash == U64_MAX ||
+ search->request.end.hash == U64_MAX) {
+ SSDFS_ERR("invalid request: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+ return -ERANGE;
+ }
+
+ node = search->node.child;
+ if (!node) {
+ node = search->node.parent;
+
+ if (!node) {
+ SSDFS_ERR("corrupted search request: "
+ "child and parent nodes are NULL\n");
+ return -ERANGE;
+ }
+
+ if (atomic_read(&node->type) == SSDFS_BTREE_ROOT_NODE) {
+ SSDFS_DBG("parent is root node\n");
+ return -ENOENT;
+ } else {
+ SSDFS_ERR("corrupted search request: "
+ "child nodes is NULL\n");
+ return -ERANGE;
+ }
+ }
+
+ if (atomic_read(&node->type) == SSDFS_BTREE_ROOT_NODE) {
+ SSDFS_DBG("child is root node\n");
+ return -ENOENT;
+ }
+
+ state = atomic_read(&node->items_area.state);
+ if (state != SSDFS_BTREE_NODE_ITEMS_AREA_EXIST) {
+ SSDFS_ERR("invalid items area's state %#x\n",
+ state);
+ return -ERANGE;
+ }
+
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ items_capacity = node->items_area.items_capacity;
+ start_hash = node->items_area.start_hash;
+ end_hash = node->items_area.end_hash;
+ up_read(&node->header_lock);
+
+ if (start_hash == U64_MAX || end_hash == U64_MAX) {
+ SSDFS_ERR("corrupted items area: "
+ "start_hash %llx, end_hash %llx\n",
+ start_hash, end_hash);
+ return -ERANGE;
+ }
+
+ if (start_hash > end_hash) {
+ SSDFS_ERR("corrupted items area: "
+ "start_hash %llx, end_hash %llx\n",
+ start_hash, end_hash);
+ return -ERANGE;
+ }
+
+ if (items_count > items_capacity) {
+ SSDFS_ERR("corrupted items area: "
+ "items_count %u, items_capacity %u\n",
+ items_count, items_capacity);
+ return -ERANGE;
+ }
+
+ free_items = items_capacity - items_count;
+
+ if (free_items != 0) {
+ SSDFS_WARN("invalid free_items %u, "
+ "items_count %u, items_capacity %u\n",
+ free_items, items_count, items_capacity);
+ return -ERANGE;
+ }
+
+ node = search->node.parent;
+ if (!node) {
+ SSDFS_ERR("corrupted search request: parent node is NULL\n");
+ return -ERANGE;
+ }
+
+ switch (atomic_read(&node->type)) {
+ case SSDFS_BTREE_ROOT_NODE:
+ case SSDFS_BTREE_INDEX_NODE:
+ /* nothing can be done */
+ SSDFS_DBG("node is root or index\n");
+ return -ENOENT;
+
+ case SSDFS_BTREE_HYBRID_NODE:
+ /* it needs to check the node's state */
+ break;
+
+ case SSDFS_BTREE_LEAF_NODE:
+ SSDFS_WARN("btree is corrupted: "
+ "leaf node %u cannot be the parent\n",
+ node->node_id);
+ return -ERANGE;
+
+ default:
+ SSDFS_ERR("invalid node's type %#x\n",
+ atomic_read(&node->type));
+ return -ERANGE;
+ }
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_WARN("invalid node's %u state %#x\n",
+ node->node_id,
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ flags = atomic_read(&node->flags);
+
+ if (!(flags & SSDFS_BTREE_NODE_HAS_ITEMS_AREA)) {
+ SSDFS_WARN("hybrid node %u hasn't items area\n",
+ node->node_id);
+ return -ENOENT;
+ }
+
+ ssdfs_btree_search_define_child_node(search, node);
+
+ spin_lock(&node->descriptor_lock);
+ ssdfs_btree_search_define_parent_node(search, node->parent_node);
+ spin_unlock(&node->descriptor_lock);
+
+ ssdfs_memcpy(&search->node.found_index,
+ 0, sizeof(struct ssdfs_btree_index_key),
+ &node->node_index,
+ 0, sizeof(struct ssdfs_btree_index_key),
+ sizeof(struct ssdfs_btree_index_key));
+
+ err = ssdfs_btree_node_convert_index2id(tree, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to convert index to ID: "
+ "node %u, height %u\n",
+ node->node_id,
+ atomic_read(&node->height));
+ return err;
+ }
+
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ items_capacity = node->items_area.items_capacity;
+ start_hash = node->items_area.start_hash;
+ end_hash = node->items_area.end_hash;
+ up_read(&node->header_lock);
+
+ free_items = items_capacity - items_count;
+
+ if (free_items == 0) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is exhausted: free_items %u, "
+ "items_count %u, items_capacity %u\n",
+ node->node_id,
+ free_items, items_count, items_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ return -ENOENT;
+ }
+
+ if (items_count == 0) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is empty: free_items %u, "
+ "items_count %u, items_capacity %u\n",
+ node->node_id,
+ free_items, items_count, items_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_node_check;
+ }
+
+ if (search->request.start.hash < start_hash) {
+ if (search->request.end.hash < start_hash) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("request (start_hash %llx, end_hash %llx), "
+ "area (start_hash %llx, end_hash %llx)\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ start_hash, end_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_node_check;
+ } else {
+ SSDFS_ERR("invalid request: "
+ "request (start_hash %llx, end_hash %llx), "
+ "area (start_hash %llx, end_hash %llx)\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ start_hash, end_hash);
+ return -ERANGE;
+ }
+ }
+
+finish_node_check:
+ search->node.state = SSDFS_BTREE_SEARCH_FOUND_LEAF_NODE_DESC;
+ search->result.state = SSDFS_BTREE_SEARCH_OUT_OF_RANGE;
+ search->result.err = -ENODATA;
+
+ if (items_count == 0)
+ search->result.start_index = 0;
+ else
+ search->result.start_index = items_count;
+
+ search->result.count = search->request.count;
+ search->result.search_cno = ssdfs_current_cno(tree->fsi->sb);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node_id %u, items_count %u, items_capacity %u, "
+ "start_hash %llx, end_hash %llx\n",
+ node->node_id, items_count, items_capacity,
+ start_hash, end_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return -ENODATA;
+}
+
+/*
+ * __ssdfs_btree_find_item() - find item into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to find an item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENODATA - item hasn't been found
+ * %-ENOSPC - node hasn't free space.
+ */
+static
+int __ssdfs_btree_find_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+ BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_FIND_ITEM:
+ case SSDFS_BTREE_SEARCH_ALLOCATE_ITEM:
+ case SSDFS_BTREE_SEARCH_ALLOCATE_RANGE:
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_RANGE:
+ case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+ case SSDFS_BTREE_SEARCH_DELETE_ITEM:
+ case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try to find an item */
+ } else if (err == -ENOENT) {
+ err = -ENODATA;
+ search->result.err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("index node was found\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ err = ssdfs_btree_switch_on_hybrid_parent_node(tree,
+ search);
+ if (err == -ENODATA)
+ goto finish_search_item;
+ else if (err == -ENOENT) {
+ err = -ENODATA;
+ goto finish_search_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to switch on parent node: "
+ "err %d\n", err);
+ } else {
+ err = -ENODATA;
+ goto finish_search_item;
+ }
+ break;
+
+ default:
+ /* do nothing */
+ break;
+ }
+
+ goto finish_search_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_search_item;
+ }
+
+ if (search->request.type == SSDFS_BTREE_SEARCH_ADD_ITEM) {
+try_another_node:
+ err = ssdfs_btree_node_find_item(search);
+ if (node_needs_in_additional_check(err, search)) {
+ search->result.err = -ENODATA;
+ err = ssdfs_btree_switch_on_hybrid_parent_node(tree,
+ search);
+ if (err == -ENODATA)
+ goto finish_search_item;
+ else if (err == -ENOENT) {
+ err = -ENODATA;
+ goto finish_search_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to switch on parent node: "
+ "err %d\n", err);
+ goto finish_search_item;
+ } else {
+ err = -ENODATA;
+ goto finish_search_item;
+ }
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_search_item;
+ } else
+ goto try_another_node;
+ }
+ } else {
+try_find_item_again:
+ err = ssdfs_btree_node_find_item(search);
+ if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_search_item;
+ } else
+ goto try_find_item_again;
+ }
+ }
+
+ if (err == -EAGAIN) {
+ if (search->result.items_in_buffer > 0 &&
+ search->result.state == SSDFS_BTREE_SEARCH_VALID_ITEM) {
+ /* finish search */
+ err = 0;
+ search->result.err = 0;
+ goto finish_search_item;
+ } else {
+ err = -ENODATA;
+ SSDFS_DBG("node hasn't requested data\n");
+ goto finish_search_item;
+ }
+ } else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("unable to find item: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_search_item;
+ } else if (err == -ENOSPC) {
+ err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ SSDFS_DBG("index node was found\n");
+ goto finish_search_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find item: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_search_item;
+ }
+
+finish_search_item:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search->result.state %#x, err %d\n",
+ search->result.state, err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_find_item() - find item into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to find an item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENODATA - item hasn't been found
+ */
+int ssdfs_btree_find_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+
+ SSDFS_DBG("tree %p, type %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ down_read(&tree->lock);
+ err = __ssdfs_btree_find_item(tree, search);
+ up_read(&tree->lock);
+
+ return err;
+}
+
+/*
+ * __ssdfs_btree_find_range() - find a range of items into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to find a range of item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int __ssdfs_btree_find_range(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+ BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_FIND_RANGE:
+ case SSDFS_BTREE_SEARCH_ADD_RANGE:
+ case SSDFS_BTREE_SEARCH_DELETE_RANGE:
+ case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+try_next_search:
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try to find an item */
+ } else if (err == -ENOENT) {
+ err = -ENODATA;
+ search->result.err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ SSDFS_DBG("index node was found\n");
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ err = ssdfs_btree_switch_on_hybrid_parent_node(tree,
+ search);
+ if (err == -ENODATA) {
+ /*
+ * do nothing
+ */
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to switch on parent node: "
+ "err %d\n", err);
+ } else {
+ /* finish search */
+ err = -ENODATA;
+ }
+ break;
+
+ default:
+ /* do nothing */
+ break;
+ }
+
+ goto finish_search_range;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_search_range;
+ }
+
+ if (search->request.type == SSDFS_BTREE_SEARCH_ADD_RANGE) {
+try_another_node:
+ err = ssdfs_btree_node_find_range(search);
+
+ if (node_needs_in_additional_check(err, search)) {
+ search->result.err = -ENODATA;
+ err = ssdfs_btree_switch_on_hybrid_parent_node(tree,
+ search);
+ if (err == -ENODATA)
+ goto finish_search_range;
+ else if (unlikely(err)) {
+ SSDFS_ERR("fail to switch on parent node: "
+ "err %d\n", err);
+ goto finish_search_range;
+ } else {
+ /* finish search */
+ err = -ENODATA;
+ goto finish_search_range;
+ }
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_search_range;
+ } else
+ goto try_another_node;
+ }
+ } else {
+try_find_range_again:
+ err = ssdfs_btree_node_find_range(search);
+ if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_search_range;
+ } else
+ goto try_find_range_again;
+ }
+ }
+
+ if (err == -EAGAIN) {
+ if (search->result.items_in_buffer > 0 &&
+ search->result.state == SSDFS_BTREE_SEARCH_VALID_ITEM) {
+ /* finish search */
+ err = 0;
+ search->result.err = 0;
+ goto finish_search_range;
+ } else {
+ err = 0;
+ search->node.state = SSDFS_BTREE_SEARCH_NODE_DESC_EMPTY;
+ SSDFS_DBG("try next search\n");
+ goto try_next_search;
+ }
+ } else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("unable to find range: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_search_range;
+ } else if (err == -ENOSPC) {
+ err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ SSDFS_DBG("index node was found\n");
+ goto finish_search_range;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find range: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_search_range;
+ }
+
+finish_search_range:
+ return err;
+}
+
+/*
+ * ssdfs_btree_find_range() - find a range of items into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to find a range of item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_find_range(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+
+ SSDFS_DBG("tree %p, type %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ down_read(&tree->lock);
+ err = __ssdfs_btree_find_range(tree, search);
+ up_read(&tree->lock);
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_allocate_item() - allocate item into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to allocate the item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_allocate_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ if (search->request.type != SSDFS_BTREE_SEARCH_ALLOCATE_ITEM) {
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+try_next_search:
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try the old search result */
+ } else if (err == -ENOENT) {
+ err = -ENODATA;
+ search->result.err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("index node was found\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ up_read(&tree->lock);
+ err = ssdfs_btree_insert_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert node: err %d\n",
+ err);
+ goto finish_allocate_item;
+ }
+
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try the old search result */
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_allocate_item;
+ }
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_allocate_item;
+ }
+
+try_allocate_item:
+ err = ssdfs_btree_node_allocate_item(search);
+ if (err == -EAGAIN) {
+ err = 0;
+ search->node.state = SSDFS_BTREE_SEARCH_NODE_DESC_EMPTY;
+ goto try_next_search;
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_allocate_item;
+ } else
+ goto try_allocate_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to allocate item: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_allocate_item;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_allocate_item:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_allocate_range() - allocate range of items into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to allocate the range of items into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_allocate_range(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ if (search->request.type != SSDFS_BTREE_SEARCH_ALLOCATE_RANGE) {
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+try_next_search:
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try the old search result */
+ } else if (err == -ENOENT) {
+ err = -ENODATA;
+ search->result.err = -ENODATA;
+ search->result.state = SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("index node was found\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ up_read(&tree->lock);
+ err = ssdfs_btree_insert_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert node: err %d\n",
+ err);
+ goto finish_allocate_range;
+ }
+
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try the old search result */
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_allocate_range;
+ }
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_allocate_range;
+ }
+
+try_allocate_range:
+ err = ssdfs_btree_node_allocate_range(search);
+ if (err == -EAGAIN) {
+ err = 0;
+ search->node.state = SSDFS_BTREE_SEARCH_NODE_DESC_EMPTY;
+ goto try_next_search;
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_allocate_range;
+ } else
+ goto try_allocate_range;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to allocate range: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_allocate_range;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_allocate_range:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * need_update_parent_node() - check necessity to update index in parent node
+ * @search: search object
+ */
+static inline
+bool need_update_parent_node(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *child;
+ u64 start_hash;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ start_hash = search->request.start.hash;
+
+ child = search->node.child;
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return need_update_parent_index_area(start_hash, child);
+}
+
+/*
+ * ssdfs_btree_update_index_in_parent_node() - update index in parent node
+ * @tree: btree object
+ * @search: search object [in|out]
+ * @ptr: hierarchy object
+ *
+ * This method tries to update an index in parent nodes.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_btree_update_index_in_parent_node(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search,
+ struct ssdfs_btree_hierarchy *ptr)
+{
+ int cur_height, tree_height;
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !ptr);
+ BUG_ON(!rwsem_is_locked(&tree->lock));
+
+ SSDFS_DBG("tree %p, hierarchy %p\n",
+ tree, ptr);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_height = atomic_read(&tree->height);
+ if (tree_height <= 0) {
+ SSDFS_ERR("invalid tree_height %u\n",
+ tree_height);
+ return -ERANGE;
+ }
+
+ for (cur_height = 0; cur_height < tree_height; cur_height++) {
+ err = ssdfs_btree_process_level_for_update(ptr,
+ cur_height,
+ search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to process the tree's level: "
+ "cur_height %u, err %d\n",
+ cur_height, err);
+ return err;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_add_item() - add item into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to add the item into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EEXIST - item exists in the tree.
+ */
+int ssdfs_btree_add_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_hierarchy *hierarchy = NULL;
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ if (search->request.type != SSDFS_BTREE_SEARCH_ADD_ITEM) {
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+try_find_item:
+ err = __ssdfs_btree_find_item(tree, search);
+ if (!err) {
+ err = -EEXIST;
+ SSDFS_ERR("item exists in the tree: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+ goto finish_add_item;
+ } else if (err == -ENODATA) {
+ err = 0;
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+ /* position in node was found */
+ break;
+ case SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE:
+ /* none node is able to store the new item */
+ break;
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid search result: "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ search->result.state);
+ goto finish_add_item;
+ };
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find item: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_item;
+ }
+
+ if (search->result.state == SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE) {
+ up_read(&tree->lock);
+ err = ssdfs_btree_insert_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert node: err %d\n",
+ err);
+ goto finish_add_item;
+ }
+
+ err = __ssdfs_btree_find_item(tree, search);
+ if (!err) {
+ err = -EEXIST;
+ SSDFS_ERR("item exists in the tree: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+ goto finish_add_item;
+ } else if (err == -ENODATA) {
+ err = 0;
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+ /* position in node was found */
+ break;
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid search result: "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ search->result.state);
+ goto finish_add_item;
+ };
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find item: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_item;
+ }
+ }
+
+try_insert_item:
+ err = ssdfs_btree_node_insert_item(search);
+ if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_add_item;
+ } else
+ goto try_insert_item;
+ } else if (err == -EFBIG) {
+ int state = search->result.state;
+
+ err = 0;
+
+ if (state != SSDFS_BTREE_SEARCH_PLEASE_MOVE_BUF_CONTENT) {
+ err = -ERANGE;
+ SSDFS_WARN("invalid search's result state %#x\n",
+ state);
+ goto finish_add_item;
+ } else
+ goto try_find_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to insert item: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_item;
+ }
+
+ if (need_update_parent_node(search)) {
+ hierarchy = ssdfs_btree_hierarchy_allocate(tree);
+ if (!hierarchy) {
+ err = -ENOMEM;
+ SSDFS_ERR("fail to allocate tree levels' array\n");
+ goto finish_add_item;
+ }
+
+ err = ssdfs_btree_check_hierarchy_for_update(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ atomic_set(&search->node.child->state,
+ SSDFS_BTREE_NODE_CORRUPTED);
+ SSDFS_ERR("fail to prepare hierarchy information : "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+ err = ssdfs_btree_update_index_in_parent_node(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to update index records: "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+finish_update_parent:
+ ssdfs_btree_hierarchy_free(hierarchy);
+
+ if (unlikely(err))
+ goto finish_add_item;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_add_item:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_add_range() - add a range of items into btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to add the range of items into the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EEXIST - range exists in the tree.
+ */
+int ssdfs_btree_add_range(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_hierarchy *hierarchy = NULL;
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ if (search->request.type != SSDFS_BTREE_SEARCH_ADD_RANGE) {
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+try_find_range:
+ err = __ssdfs_btree_find_range(tree, search);
+ if (!err) {
+ err = -EEXIST;
+ SSDFS_ERR("range exists in the tree: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+ goto finish_add_range;
+ } else if (err == -ENODATA) {
+ err = 0;
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ /* position in node was found */
+ break;
+ case SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE:
+ /* none node is able to store the new range */
+ break;
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid search result: "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ search->result.state);
+ goto finish_add_range;
+ };
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find range: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_range;
+ }
+
+ if (search->result.state == SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE) {
+ up_read(&tree->lock);
+ err = ssdfs_btree_insert_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert node: err %d\n",
+ err);
+ goto finish_add_range;
+ }
+
+ err = __ssdfs_btree_find_range(tree, search);
+ if (!err) {
+ err = -EEXIST;
+ SSDFS_ERR("range exists in the tree: "
+ "start_hash %llx, end_hash %llx\n",
+ search->request.start.hash,
+ search->request.end.hash);
+ goto finish_add_range;
+ } else if (err == -ENODATA) {
+ err = 0;
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+ /* position in node was found */
+ break;
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid search result: "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ search->result.state);
+ goto finish_add_range;
+ };
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find range: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_range;
+ }
+ }
+
+try_insert_range:
+ err = ssdfs_btree_node_insert_range(search);
+ if (err == -EAGAIN) {
+ err = 0;
+ goto try_find_range;
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_add_range;
+ } else
+ goto try_insert_range;
+ } else if (err == -EFBIG) {
+ int state = search->result.state;
+
+ err = 0;
+
+ if (state != SSDFS_BTREE_SEARCH_PLEASE_MOVE_BUF_CONTENT) {
+ err = -ERANGE;
+ SSDFS_WARN("invalid search's result state %#x\n",
+ state);
+ goto finish_add_range;
+ } else
+ goto try_find_range;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to insert item: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_add_range;
+ }
+
+ if (need_update_parent_node(search)) {
+ hierarchy = ssdfs_btree_hierarchy_allocate(tree);
+ if (!hierarchy) {
+ err = -ENOMEM;
+ SSDFS_ERR("fail to allocate tree levels' array\n");
+ goto finish_add_range;
+ }
+
+ err = ssdfs_btree_check_hierarchy_for_update(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ atomic_set(&search->node.child->state,
+ SSDFS_BTREE_NODE_CORRUPTED);
+ SSDFS_ERR("fail to prepare hierarchy information : "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+ err = ssdfs_btree_update_index_in_parent_node(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to update index records: "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+finish_update_parent:
+ ssdfs_btree_hierarchy_free(hierarchy);
+
+ if (unlikely(err))
+ goto finish_add_range;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_add_range:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_change_item() - change an existing item in the btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to change the existing item in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_change_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_hierarchy *hierarchy = NULL;
+ int tree_state;
+ int tree_height;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+ case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+ /* expected type */
+ break;
+
+ default:
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ tree_height = atomic_read(&tree->height);
+ if (tree_height <= 0) {
+ SSDFS_ERR("invalid tree_height %u\n",
+ tree_height);
+ return -ERANGE;
+ }
+
+ down_read(&tree->lock);
+
+try_next_search:
+ err = ssdfs_btree_find_leaf_node(tree, search);
+ if (err == -EEXIST) {
+ err = 0;
+ /* try the old search result */
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find leaf node: err %d\n",
+ err);
+ goto finish_change_item;
+ }
+
+try_change_item:
+ err = ssdfs_btree_node_change_item(search);
+ if (err == -EAGAIN) {
+ err = 0;
+ search->node.state = SSDFS_BTREE_SEARCH_NODE_DESC_EMPTY;
+ goto try_next_search;
+ } else if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_change_item;
+ } else
+ goto try_change_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to change item: "
+ "start_hash %llx, end_hash %llx, "
+ "err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_change_item;
+ }
+
+ if (need_update_parent_node(search)) {
+ hierarchy = ssdfs_btree_hierarchy_allocate(tree);
+ if (!hierarchy) {
+ err = -ENOMEM;
+ SSDFS_ERR("fail to allocate tree levels' array\n");
+ goto finish_change_item;
+ }
+
+ err = ssdfs_btree_check_hierarchy_for_update(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ atomic_set(&search->node.child->state,
+ SSDFS_BTREE_NODE_CORRUPTED);
+ SSDFS_ERR("fail to prepare hierarchy information : "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+ err = ssdfs_btree_update_index_in_parent_node(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to update index records: "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+finish_update_parent:
+ ssdfs_btree_hierarchy_free(hierarchy);
+
+ if (unlikely(err))
+ goto finish_change_item;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_change_item:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_delete_item() - delete an existing item in the btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to delete the existing item in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_delete_item(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_hierarchy *hierarchy = NULL;
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_DELETE_ITEM:
+ case SSDFS_BTREE_SEARCH_INVALIDATE_TAIL:
+ /* expected type */
+ break;
+
+ default:
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+ err = __ssdfs_btree_find_item(tree, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find item: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_delete_item;
+ }
+
+try_delete_item:
+ err = ssdfs_btree_node_delete_item(search);
+ if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_delete_item;
+ } else
+ goto try_delete_item;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to delete item: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ goto finish_delete_item;
+ }
+
+ if (search->result.state == SSDFS_BTREE_SEARCH_PLEASE_DELETE_NODE) {
+ up_read(&tree->lock);
+ err = ssdfs_btree_delete_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete btree node: "
+ "node_id %llu, err %d\n",
+ (u64)search->node.id, err);
+ goto finish_delete_item;
+ }
+ } else if (need_update_parent_node(search)) {
+ hierarchy = ssdfs_btree_hierarchy_allocate(tree);
+ if (!hierarchy) {
+ err = -ENOMEM;
+ SSDFS_ERR("fail to allocate tree levels' array\n");
+ goto finish_delete_item;
+ }
+
+ err = ssdfs_btree_check_hierarchy_for_update(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ atomic_set(&search->node.child->state,
+ SSDFS_BTREE_NODE_CORRUPTED);
+ SSDFS_ERR("fail to prepare hierarchy information : "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+ err = ssdfs_btree_update_index_in_parent_node(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to update index records: "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+finish_update_parent:
+ ssdfs_btree_hierarchy_free(hierarchy);
+
+ if (unlikely(err))
+ goto finish_delete_item;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+finish_delete_item:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_delete_range() - delete a range of items in the btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to delete a range of existing items in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_delete_range(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_hierarchy *hierarchy = NULL;
+ int tree_state;
+ bool need_continue_deletion = false;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#else
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "request->type %#x, request->flags %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ tree, tree->type, tree_state,
+ search->request.type, search->request.flags,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_request_valid(search)) {
+ SSDFS_ERR("invalid search object\n");
+ return -EINVAL;
+ }
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_DELETE_RANGE:
+ case SSDFS_BTREE_SEARCH_DELETE_ALL:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid request type %#x\n",
+ search->request.type);
+ return -EINVAL;
+ }
+
+ down_read(&tree->lock);
+
+try_delete_next_range:
+ err = __ssdfs_btree_find_range(tree, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find range: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ up_read(&tree->lock);
+ return err;
+ }
+
+try_delete_range_again:
+ err = ssdfs_btree_node_delete_range(search);
+ if (err == -EACCES) {
+ struct ssdfs_btree_node *node = search->node.child;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = SSDFS_WAIT_COMPLETION(&node->init_end);
+ if (unlikely(err)) {
+ SSDFS_ERR("node init failed: "
+ "err %d\n", err);
+ goto finish_delete_range;
+ } else
+ goto try_delete_range_again;
+ }
+
+finish_delete_range:
+ if (err == -EAGAIN) {
+ /* the range have to be deleted in the next node */
+ err = 0;
+ need_continue_deletion = true;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to delete range: "
+ "start_hash %llx, end_hash %llx, err %d\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+ up_read(&tree->lock);
+ return err;
+ }
+
+ if (search->result.state == SSDFS_BTREE_SEARCH_PLEASE_DELETE_NODE) {
+ up_read(&tree->lock);
+ err = ssdfs_btree_delete_node(tree, search);
+ down_read(&tree->lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete btree node: "
+ "node_id %llu, err %d\n",
+ (u64)search->node.id, err);
+ goto fail_delete_range;
+ }
+ } else if (need_update_parent_node(search)) {
+ hierarchy = ssdfs_btree_hierarchy_allocate(tree);
+ if (!hierarchy) {
+ err = -ENOMEM;
+ SSDFS_ERR("fail to allocate tree levels' array\n");
+ goto fail_delete_range;
+ }
+
+ err = ssdfs_btree_check_hierarchy_for_update(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ atomic_set(&search->node.child->state,
+ SSDFS_BTREE_NODE_CORRUPTED);
+ SSDFS_ERR("fail to prepare hierarchy information : "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+ err = ssdfs_btree_update_index_in_parent_node(tree, search,
+ hierarchy);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to update index records: "
+ "err %d\n",
+ err);
+ goto finish_update_parent;
+ }
+
+finish_update_parent:
+ ssdfs_btree_hierarchy_free(hierarchy);
+
+ if (unlikely(err))
+ goto fail_delete_range;
+ }
+
+ if (need_continue_deletion) {
+ need_continue_deletion = false;
+ goto try_delete_next_range;
+ }
+
+ atomic_set(&tree->state, SSDFS_BTREE_DIRTY);
+
+fail_delete_range:
+ up_read(&tree->lock);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_debug_btree_object(tree);
+
+#ifdef CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK
+ ssdfs_check_btree_consistency(tree);
+#endif /* CONFIG_SSDFS_BTREE_STRICT_CONSISTENCY_CHECK */
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_delete_all() - delete all items in the btree
+ * @tree: btree object
+ * @search: search object [in|out]
+ *
+ * This method tries to delete all items in the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_delete_all(struct ssdfs_btree *tree)
+{
+ struct ssdfs_btree_search *search;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("tree %p\n", tree);
+#else
+ SSDFS_DBG("tree %p\n", tree);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ 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_DELETE_ALL;
+ search->request.start.hash = 0;
+ search->request.end.hash = U64_MAX;
+
+ err = ssdfs_btree_delete_range(tree, search);
+ if (unlikely(err))
+ SSDFS_ERR("fail to delete all items: err %d\n", err);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ ssdfs_btree_search_free(search);
+ return err;
+}
+
+/*
+ * ssdfs_btree_get_head_range() - extract head range of the tree
+ * @tree: btree object
+ * @expected_len: expected length of the range
+ * @search: search object
+ *
+ * This method tries to extract a head range of items from the tree.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EAGAIN - expected length of the range is not extracted
+ */
+int ssdfs_btree_get_head_range(struct ssdfs_btree *tree,
+ u32 expected_len,
+ struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *node;
+ struct ssdfs_btree_index_key key;
+ int tree_state;
+ u64 hash;
+ u32 buf_size;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "expected_len %u\n",
+ tree, tree->type, tree_state,
+ expected_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ down_read(&tree->lock);
+
+ err = ssdfs_btree_radix_tree_find(tree,
+ SSDFS_BTREE_ROOT_NODE_ID,
+ &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find root node: err %d\n",
+ err);
+ goto finish_get_range;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_get_range;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ err = -ERANGE;
+ SSDFS_WARN("root node hasn't index area\n");
+ goto finish_get_range;
+ }
+
+ if (is_ssdfs_btree_node_index_area_empty(node))
+ goto finish_get_range;
+
+ down_read(&node->full_lock);
+ err = __ssdfs_btree_root_node_extract_index(node,
+ SSDFS_ROOT_NODE_LEFT_LEAF_NODE,
+ &key);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to get index: err %d\n",
+ err);
+ goto finish_get_range;
+ }
+
+ hash = le64_to_cpu(key.index.hash);
+ if (hash >= U64_MAX) {
+ err = -ERANGE;
+ SSDFS_ERR("invalid hash\n");
+ goto finish_get_range;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("hash %llx\n", hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ 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 = hash;
+ search->request.end.hash = hash;
+ search->request.count = 1;
+
+ err = __ssdfs_btree_find_item(tree, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find the item: "
+ "hash %llx, err %d\n",
+ hash, err);
+ goto finish_get_range;
+ }
+
+ buf_size = expected_len * tree->max_item_size;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(expected_len >= U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = ssdfs_btree_node_extract_range(search->result.start_index,
+ (u16)expected_len,
+ search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to extract the range: "
+ "start_index %u, expected_len %u, err %d\n",
+ search->result.start_index,
+ expected_len, err);
+ goto finish_get_range;
+ }
+
+ if (expected_len != search->result.count) {
+ err = -EAGAIN;
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("expected_len %u != search->result.count %u\n",
+ expected_len, search->result.count);
+#endif /* CONFIG_SSDFS_DEBUG */
+ }
+
+finish_get_range:
+ up_read(&tree->lock);
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_extract_range() - extract range from the node
+ * @tree: btree object
+ * @start_index: start index in the node
+ * @count: count of items in the range
+ * @search: search object
+ *
+ * This method tries to extract a range of items from the found node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_extract_range(struct ssdfs_btree *tree,
+ u16 start_index, u16 count,
+ struct ssdfs_btree_search *search)
+{
+ int tree_state;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x, "
+ "start_index %u, count %u\n",
+ tree, tree->type, tree_state,
+ start_index, count);
+
+ ssdfs_debug_btree_object(tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ down_read(&tree->lock);
+
+ err = ssdfs_btree_node_extract_range(start_index, count,
+ search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to extract the range: "
+ "start_index %u, count %u, err %d\n",
+ start_index, count, err);
+ goto finish_get_range;
+ }
+
+finish_get_range:
+ up_read(&tree->lock);
+
+ return err;
+}
+
+/*
+ * is_ssdfs_btree_empty() - check that btree is empty
+ * @tree: btree object
+ */
+bool is_ssdfs_btree_empty(struct ssdfs_btree *tree)
+{
+ struct ssdfs_btree_node *node;
+ struct ssdfs_btree_index_key key1, key2;
+ int tree_state;
+ u32 node_id1, node_id2;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x\n",
+ tree, tree->type, tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return false;
+ }
+
+ down_read(&tree->lock);
+
+ err = ssdfs_btree_radix_tree_find(tree,
+ SSDFS_BTREE_ROOT_NODE_ID,
+ &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find root node: err %d\n",
+ err);
+ goto finish_check_tree;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_check_tree;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ err = -ERANGE;
+ SSDFS_WARN("root node hasn't index area\n");
+ goto finish_check_tree;
+ }
+
+ if (is_ssdfs_btree_node_index_area_empty(node))
+ goto finish_check_tree;
+
+ down_read(&node->full_lock);
+ err = __ssdfs_btree_root_node_extract_index(node,
+ SSDFS_ROOT_NODE_LEFT_LEAF_NODE,
+ &key1);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to get index: err %d\n",
+ err);
+ goto finish_check_tree;
+ }
+
+ node_id1 = le32_to_cpu(key1.node_id);
+ if (node_id1 == SSDFS_BTREE_NODE_INVALID_ID) {
+ SSDFS_WARN("index is invalid\n");
+ goto finish_check_tree;
+ }
+
+ down_read(&node->full_lock);
+ err = __ssdfs_btree_root_node_extract_index(node,
+ SSDFS_ROOT_NODE_RIGHT_LEAF_NODE,
+ &key2);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to get index: err %d\n",
+ err);
+ goto finish_check_tree;
+ }
+
+ node_id2 = le32_to_cpu(key2.node_id);
+ if (node_id2 != SSDFS_BTREE_NODE_INVALID_ID) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ }
+
+ err = ssdfs_btree_radix_tree_find(tree, node_id1, &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find node: node_id %u, err %d\n",
+ node_id1, err);
+ goto finish_check_tree;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_check_tree;
+ }
+
+ switch (atomic_read(&node->type)) {
+ case SSDFS_BTREE_LEAF_NODE:
+ if (!is_ssdfs_btree_node_items_area_empty(node)) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ } else {
+ /* empty node */
+ goto finish_check_tree;
+ }
+ break;
+
+ case SSDFS_BTREE_HYBRID_NODE:
+ if (!is_ssdfs_btree_node_items_area_empty(node)) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ } else if (!is_ssdfs_btree_node_index_area_empty(node)) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ } else {
+ /* empty node */
+ goto finish_check_tree;
+ }
+ break;
+
+ case SSDFS_BTREE_INDEX_NODE:
+ err = -EEXIST;
+ goto finish_check_tree;
+
+ case SSDFS_BTREE_ROOT_NODE:
+ err = -ERANGE;
+ SSDFS_WARN("node %u has root node type\n",
+ node_id1);
+ goto finish_check_tree;
+
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid node type %#x\n",
+ atomic_read(&node->type));
+ goto finish_check_tree;
+ }
+
+finish_check_tree:
+ up_read(&tree->lock);
+
+ return err ? false : true;
+}
+
+/*
+ * need_migrate_generic2inline_btree() - is it time to migrate?
+ * @tree: btree object
+ * @items_threshold: items migration threshold
+ */
+bool need_migrate_generic2inline_btree(struct ssdfs_btree *tree,
+ int items_threshold)
+{
+ struct ssdfs_btree_node *node;
+ struct ssdfs_btree_index_key key1, key2;
+ int tree_state;
+ u32 node_id1, node_id2;
+ u16 items_count;
+ bool need_migrate = false;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, type %#x, state %#x\n",
+ tree, tree->type, tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return false;
+ }
+
+ down_read(&tree->lock);
+
+ err = ssdfs_btree_radix_tree_find(tree,
+ SSDFS_BTREE_ROOT_NODE_ID,
+ &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find root node: err %d\n",
+ err);
+ goto finish_check_tree;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_check_tree;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ err = -ERANGE;
+ SSDFS_WARN("root node hasn't index area\n");
+ goto finish_check_tree;
+ }
+
+ if (is_ssdfs_btree_node_index_area_empty(node))
+ goto finish_check_tree;
+
+ down_read(&node->full_lock);
+ err = __ssdfs_btree_root_node_extract_index(node,
+ SSDFS_ROOT_NODE_LEFT_LEAF_NODE,
+ &key1);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to get index: err %d\n",
+ err);
+ goto finish_check_tree;
+ }
+
+ node_id1 = le32_to_cpu(key1.node_id);
+ if (node_id1 == SSDFS_BTREE_NODE_INVALID_ID) {
+ SSDFS_WARN("index is invalid\n");
+ goto finish_check_tree;
+ }
+
+ down_read(&node->full_lock);
+ err = __ssdfs_btree_root_node_extract_index(node,
+ SSDFS_ROOT_NODE_RIGHT_LEAF_NODE,
+ &key2);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to get index: err %d\n",
+ err);
+ goto finish_check_tree;
+ }
+
+ node_id2 = le32_to_cpu(key2.node_id);
+ if (node_id2 != SSDFS_BTREE_NODE_INVALID_ID) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ }
+
+ err = ssdfs_btree_radix_tree_find(tree, node_id1, &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find node: node_id %u, err %d\n",
+ node_id1, err);
+ goto finish_check_tree;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_check_tree;
+ }
+
+ switch (atomic_read(&node->type)) {
+ case SSDFS_BTREE_LEAF_NODE:
+ if (!is_ssdfs_btree_node_items_area_empty(node)) {
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ up_read(&node->header_lock);
+
+ if (items_count <= items_threshold) {
+ /* time to migrate */
+ need_migrate = true;
+ }
+
+ goto finish_check_tree;
+ } else {
+ /* empty node */
+ goto finish_check_tree;
+ }
+ break;
+
+ case SSDFS_BTREE_HYBRID_NODE:
+ if (is_ssdfs_btree_node_index_area_empty(node) &&
+ !is_ssdfs_btree_node_items_area_empty(node)) {
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ up_read(&node->header_lock);
+
+ if (items_count <= items_threshold) {
+ /* time to migrate */
+ need_migrate = true;
+ }
+
+ goto finish_check_tree;
+ } else if (!is_ssdfs_btree_node_index_area_empty(node)) {
+ err = -EEXIST;
+ goto finish_check_tree;
+ } else {
+ /* empty node */
+ goto finish_check_tree;
+ }
+ break;
+
+ case SSDFS_BTREE_INDEX_NODE:
+ err = -EEXIST;
+ goto finish_check_tree;
+
+ case SSDFS_BTREE_ROOT_NODE:
+ err = -ERANGE;
+ SSDFS_WARN("node %u has root node type\n",
+ node_id1);
+ goto finish_check_tree;
+
+ default:
+ err = -ERANGE;
+ SSDFS_ERR("invalid node type %#x\n",
+ atomic_read(&node->type));
+ goto finish_check_tree;
+ }
+
+finish_check_tree:
+ up_read(&tree->lock);
+
+ return need_migrate;
+}
+
+/*
+ * ssdfs_btree_synchronize_root_node() - synchronize root node state
+ * @tree: btree object
+ * @root: root node
+ */
+int ssdfs_btree_synchronize_root_node(struct ssdfs_btree *tree,
+ struct ssdfs_btree_inline_root_node *root)
+{
+ int tree_state;
+ struct ssdfs_btree_node *node;
+ u16 items_count;
+ int height;
+ size_t ids_array_size = sizeof(__le32) *
+ SSDFS_BTREE_ROOT_NODE_INDEX_COUNT;
+ size_t indexes_size = sizeof(struct ssdfs_btree_index) *
+ SSDFS_BTREE_ROOT_NODE_INDEX_COUNT;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !root);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ tree_state = atomic_read(&tree->state);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("tree %p, root %p, type %#x, state %#x\n",
+ tree, root, tree->type, tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (tree_state) {
+ case SSDFS_BTREE_CREATED:
+ case SSDFS_BTREE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG();
+#else
+ SSDFS_WARN("invalid tree state %#x\n",
+ tree_state);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ERANGE;
+ }
+
+ down_read(&tree->lock);
+
+ err = ssdfs_btree_radix_tree_find(tree,
+ SSDFS_BTREE_ROOT_NODE_ID,
+ &node);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to find root node: err %d\n",
+ err);
+ goto finish_synchronize_root;
+ } else if (!node) {
+ err = -ERANGE;
+ SSDFS_ERR("node is NULL\n");
+ goto finish_synchronize_root;
+ }
+
+ down_read(&node->header_lock);
+ height = atomic_read(&node->tree->height);
+ root->header.height = (u8)height;
+ items_count = node->index_area.index_count;
+ root->header.items_count = cpu_to_le16(items_count);
+ root->header.flags = (u8)atomic_read(&node->flags);
+ root->header.type = (u8)atomic_read(&node->type);
+ ssdfs_memcpy(root->header.node_ids,
+ 0, ids_array_size,
+ node->raw.root_node.header.node_ids,
+ 0, ids_array_size,
+ ids_array_size);
+ ssdfs_memcpy(root->indexes, 0, indexes_size,
+ node->raw.root_node.indexes, 0, indexes_size,
+ indexes_size);
+ up_read(&node->header_lock);
+
+ spin_lock(&node->tree->nodes_lock);
+ root->header.upper_node_id =
+ cpu_to_le32(node->tree->upper_node_id);
+ spin_unlock(&node->tree->nodes_lock);
+
+finish_synchronize_root:
+ up_read(&tree->lock);
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_get_next_hash() - get next node's starting hash
+ * @tree: btree object
+ * @search: search object
+ * @next_hash: next node's starting hash [out]
+ */
+int ssdfs_btree_get_next_hash(struct ssdfs_btree *tree,
+ struct ssdfs_btree_search *search,
+ u64 *next_hash)
+{
+ struct ssdfs_btree_node *parent;
+ struct ssdfs_btree_node_index_area area;
+ struct ssdfs_btree_index_key index_key;
+ u64 old_hash = U64_MAX;
+ int type;
+ spinlock_t *lock;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!tree || !search || !next_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ old_hash = le64_to_cpu(search->node.found_index.index.hash);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search %p, next_hash %p, old (node %u, hash %llx)\n",
+ search, next_hash, search->node.id, old_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ *next_hash = U64_MAX;
+
+ parent = search->node.parent;
+
+ if (!parent) {
+ SSDFS_ERR("node pointer is NULL\n");
+ return -ERANGE;
+ }
+
+ type = atomic_read(&parent->type);
+
+ down_read(&tree->lock);
+
+ do {
+ u16 found_pos;
+
+ err = -ENOENT;
+
+ down_read(&parent->full_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("old_hash %llx\n", old_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ down_read(&parent->header_lock);
+ ssdfs_memcpy(&area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ &parent->index_area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ sizeof(struct ssdfs_btree_node_index_area));
+ err = ssdfs_find_index_by_hash(parent, &area,
+ old_hash,
+ &found_pos);
+ up_read(&parent->header_lock);
+
+ if (err == -EEXIST) {
+ /* hash == found hash */
+ err = 0;
+ } else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("unable to find the index position: "
+ "old_hash %llx\n",
+ old_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_index_search;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find the index position: "
+ "old_hash %llx, err %d\n",
+ old_hash, err);
+ goto finish_index_search;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(found_pos == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ found_pos++;
+
+ if (found_pos >= area.index_count) {
+ err = -ENOENT;
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("index area is finished: "
+ "found_pos %u, area.index_count %u\n",
+ found_pos, area.index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_index_search;
+ }
+
+ if (type == SSDFS_BTREE_ROOT_NODE) {
+ err = __ssdfs_btree_root_node_extract_index(parent,
+ found_pos,
+ &index_key);
+ } else {
+ err = __ssdfs_btree_common_node_extract_index(parent,
+ &area,
+ found_pos,
+ &index_key);
+ }
+
+finish_index_search:
+ up_read(&parent->full_lock);
+
+ if (err == -ENOENT) {
+ if (type == SSDFS_BTREE_ROOT_NODE) {
+ SSDFS_DBG("no more next hashes\n");
+ goto finish_get_next_hash;
+ }
+
+ spin_lock(&parent->descriptor_lock);
+ old_hash = le64_to_cpu(parent->node_index.index.hash);
+ spin_unlock(&parent->descriptor_lock);
+
+ /* try next parent */
+ lock = &parent->descriptor_lock;
+ spin_lock(lock);
+ parent = parent->parent_node;
+ spin_unlock(lock);
+ lock = NULL;
+
+ if (!parent) {
+ err = -ERANGE;
+ SSDFS_ERR("node pointer is NULL\n");
+ goto finish_get_next_hash;
+ }
+ } else if (err == -ENODATA) {
+ SSDFS_DBG("unable to find the index position\n");
+ goto finish_get_next_hash;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to extract index key: "
+ "index_position %u, err %d\n",
+ found_pos, err);
+ ssdfs_debug_show_btree_node_indexes(parent->tree,
+ parent);
+ goto finish_get_next_hash;
+ } else {
+ /* next hash has been found */
+ err = 0;
+ *next_hash = le64_to_cpu(index_key.index.hash);
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("next_hash %llx\n", *next_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ goto finish_get_next_hash;
+ }
+
+ type = atomic_read(&parent->type);
+ } while (parent != NULL);
+
+finish_get_next_hash:
+ up_read(&tree->lock);
+
+ return err;
+}
+
+void ssdfs_debug_show_btree_node_indexes(struct ssdfs_btree *tree,
+ struct ssdfs_btree_node *parent)
+{
+#ifdef CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK
+ struct ssdfs_btree_node_index_area area;
+ struct ssdfs_btree_index_key index_key;
+ int type;
+ int i;
+ int err = 0;
+
+ BUG_ON(!tree || !parent);
+
+ type = atomic_read(&parent->type);
+
+ if (!is_ssdfs_btree_node_index_area_exist(parent)) {
+ SSDFS_ERR("corrupted node %u\n",
+ parent->node_id);
+ BUG();
+ }
+
+ if (is_ssdfs_btree_node_index_area_empty(parent)) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u has empty index area\n",
+ parent->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return;
+ }
+
+ down_read(&parent->full_lock);
+
+ down_read(&parent->header_lock);
+ ssdfs_memcpy(&area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ &parent->index_area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ sizeof(struct ssdfs_btree_node_index_area));
+ up_read(&parent->header_lock);
+
+ for (i = 0; i < area.index_count; i++) {
+ if (type == SSDFS_BTREE_ROOT_NODE) {
+ err = __ssdfs_btree_root_node_extract_index(parent,
+ i,
+ &index_key);
+ } else {
+ err = __ssdfs_btree_common_node_extract_index(parent,
+ &area, i,
+ &index_key);
+ }
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to extract index key: "
+ "index_position %d, err %d\n",
+ i, err);
+ goto finish_index_processing;
+ }
+
+ SSDFS_ERR("index %d, node_id %u, "
+ "node_type %#x, height %u, "
+ "flags %#x, hash %llx, seg_id %llu, "
+ "logical_blk %u, len %u\n",
+ i,
+ le32_to_cpu(index_key.node_id),
+ index_key.node_type,
+ index_key.height,
+ le16_to_cpu(index_key.flags),
+ le64_to_cpu(index_key.index.hash),
+ le64_to_cpu(index_key.index.extent.seg_id),
+ le32_to_cpu(index_key.index.extent.logical_blk),
+ le32_to_cpu(index_key.index.extent.len));
+ }
+
+finish_index_processing:
+ up_read(&parent->full_lock);
+
+ ssdfs_show_btree_node_info(parent);
+#endif /* CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK */
+}
+
+#ifdef CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK
+static
+void ssdfs_debug_btree_check_indexes(struct ssdfs_btree *tree,
+ struct ssdfs_btree_node *parent)
+{
+ struct ssdfs_btree_node *child = NULL;
+ struct ssdfs_btree_node_index_area area;
+ struct ssdfs_btree_index_key index_key;
+ int type;
+ u32 node_id1, node_id2;
+ u64 start_hash1 = U64_MAX;
+ u64 start_hash2 = U64_MAX;
+ u64 prev_hash = U64_MAX;
+ int i;
+ int err = 0;
+
+ BUG_ON(!tree || !parent);
+
+ type = atomic_read(&parent->type);
+
+ switch (type) {
+ case SSDFS_BTREE_ROOT_NODE:
+ case SSDFS_BTREE_INDEX_NODE:
+ case SSDFS_BTREE_HYBRID_NODE:
+ if (!is_ssdfs_btree_node_index_area_exist(parent)) {
+ SSDFS_ERR("corrupted node %u\n",
+ parent->node_id);
+ ssdfs_show_btree_node_info(parent);
+ BUG();
+ }
+ break;
+
+ case SSDFS_BTREE_LEAF_NODE:
+ /* do nothing */
+ return;
+
+ default:
+ BUG();
+ }
+
+ if (is_ssdfs_btree_node_index_area_empty(parent)) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u has empty index area\n",
+ parent->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return;
+ }
+
+ down_read(&parent->full_lock);
+
+ down_read(&parent->header_lock);
+ ssdfs_memcpy(&area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ &parent->index_area,
+ 0, sizeof(struct ssdfs_btree_node_index_area),
+ sizeof(struct ssdfs_btree_node_index_area));
+ up_read(&parent->header_lock);
+
+ node_id1 = parent->node_id;
+
+ for (i = 0; i < area.index_count; i++) {
+ if (type == SSDFS_BTREE_ROOT_NODE) {
+ err = __ssdfs_btree_root_node_extract_index(parent,
+ i,
+ &index_key);
+ } else {
+ err = __ssdfs_btree_common_node_extract_index(parent,
+ &area, i,
+ &index_key);
+ }
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to extract index key: "
+ "index_position %d, err %d\n",
+ i, err);
+ goto finish_index_processing;
+ }
+
+ node_id2 = le32_to_cpu(index_key.node_id);
+ start_hash1 = le64_to_cpu(index_key.index.hash);
+
+ up_read(&parent->full_lock);
+
+ err = ssdfs_btree_radix_tree_find(tree, node_id2, &child);
+
+ if (err || !child) {
+ SSDFS_ERR("node_id %u is absent\n",
+ node_id2);
+ goto continue_tree_check;
+ }
+
+ switch (atomic_read(&child->type)) {
+ case SSDFS_BTREE_INDEX_NODE:
+ if (!is_ssdfs_btree_node_index_area_exist(child)) {
+ SSDFS_ERR("corrupted node %u\n",
+ child->node_id);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ if (node_id1 == node_id2) {
+ SSDFS_WARN("node_id1 %u == node_id2 %u\n",
+ node_id1, node_id2);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ down_read(&child->header_lock);
+ start_hash2 = child->index_area.start_hash;
+ up_read(&child->header_lock);
+ break;
+
+ case SSDFS_BTREE_HYBRID_NODE:
+ if (!is_ssdfs_btree_node_index_area_exist(child)) {
+ SSDFS_ERR("corrupted node %u\n",
+ child->node_id);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ if (!is_ssdfs_btree_node_items_area_exist(child)) {
+ SSDFS_ERR("corrupted node %u\n",
+ child->node_id);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ if (node_id1 == node_id2) {
+ down_read(&child->header_lock);
+ start_hash2 = child->items_area.start_hash;
+ up_read(&child->header_lock);
+ } else {
+ down_read(&child->header_lock);
+ start_hash2 = child->index_area.start_hash;
+ up_read(&child->header_lock);
+ }
+ break;
+
+ case SSDFS_BTREE_LEAF_NODE:
+ if (!is_ssdfs_btree_node_items_area_exist(child)) {
+ SSDFS_ERR("corrupted node %u\n",
+ child->node_id);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ if (node_id1 == node_id2) {
+ SSDFS_WARN("node_id1 %u == node_id2 %u\n",
+ node_id1, node_id2);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ down_read(&child->header_lock);
+ start_hash2 = child->items_area.start_hash;
+ up_read(&child->header_lock);
+ break;
+
+ default:
+ BUG();
+ }
+
+ if (start_hash1 != start_hash2) {
+ SSDFS_WARN("parent: node_id %u, "
+ "index %d, hash %llx, "
+ "child: node_id %u, type %#x, "
+ "start_hash %llx\n",
+ node_id1, i, start_hash1,
+ node_id2, atomic_read(&child->type),
+ start_hash2);
+ ssdfs_debug_show_btree_node_indexes(tree,
+ parent);
+ ssdfs_show_btree_node_info(parent);
+ ssdfs_show_btree_node_info(child);
+ BUG();
+ }
+
+ if (i > 1) {
+ if (prev_hash >= start_hash1) {
+ SSDFS_WARN("node_id %u, index_position %d, "
+ "prev_hash %llx >= hash %llx\n",
+ node_id1, i,
+ prev_hash, start_hash1);
+ ssdfs_debug_show_btree_node_indexes(tree,
+ parent);
+ BUG();
+ }
+ }
+
+continue_tree_check:
+ prev_hash = start_hash1;
+
+ down_read(&parent->full_lock);
+ }
+
+finish_index_processing:
+ up_read(&parent->full_lock);
+}
+#endif /* CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK */
+
+void ssdfs_check_btree_consistency(struct ssdfs_btree *tree)
+{
+#ifdef CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK
+ struct radix_tree_iter iter1, iter2;
+ void **slot1;
+ void **slot2;
+ struct ssdfs_btree_node *node1;
+ struct ssdfs_btree_node *node2;
+ u32 node_id1, node_id2;
+ u64 start_hash1, start_hash2;
+ u64 end_hash1, end_hash2;
+ u16 items_count;
+ u16 index_position;
+ bool is_exist = false;
+ int err;
+
+ BUG_ON(!tree);
+
+ down_read(&tree->lock);
+
+ rcu_read_lock();
+ radix_tree_for_each_slot(slot1, &tree->nodes, &iter1,
+ SSDFS_BTREE_ROOT_NODE_ID) {
+ node1 = SSDFS_BTN(radix_tree_deref_slot(slot1));
+
+ if (!node1)
+ continue;
+
+ if (is_ssdfs_btree_node_pre_deleted(node1)) {
+ SSDFS_DBG("node %u has pre-deleted state\n",
+ node1->node_id);
+ continue;
+ }
+
+ rcu_read_unlock();
+
+ ssdfs_debug_btree_check_indexes(tree, node1);
+
+ switch (atomic_read(&node1->type)) {
+ case SSDFS_BTREE_ROOT_NODE:
+ rcu_read_lock();
+ continue;
+
+ case SSDFS_BTREE_INDEX_NODE:
+ case SSDFS_BTREE_HYBRID_NODE:
+ if (!is_ssdfs_btree_node_index_area_exist(node1)) {
+ SSDFS_ERR("corrupted node %u\n",
+ node1->node_id);
+ ssdfs_show_btree_node_info(node1);
+ BUG();
+ }
+
+ down_read(&node1->header_lock);
+ start_hash1 = node1->index_area.start_hash;
+ end_hash1 = node1->index_area.end_hash;
+ up_read(&node1->header_lock);
+ break;
+
+ case SSDFS_BTREE_LEAF_NODE:
+ if (!is_ssdfs_btree_node_items_area_exist(node1)) {
+ SSDFS_ERR("corrupted node %u\n",
+ node1->node_id);
+ ssdfs_show_btree_node_info(node1);
+ BUG();
+ }
+
+ down_read(&node1->header_lock);
+ start_hash1 = node1->items_area.start_hash;
+ end_hash1 = node1->items_area.end_hash;
+ up_read(&node1->header_lock);
+ break;
+
+ default:
+ BUG();
+ }
+
+ SSDFS_DBG("node %u, type %#x, "
+ "start_hash %llx, end_hash %llx\n",
+ node1->node_id, atomic_read(&node1->type),
+ start_hash1, end_hash1);
+
+ err = ssdfs_btree_node_find_index_position(node1->parent_node,
+ start_hash1,
+ &index_position);
+ if (unlikely(err)) {
+ SSDFS_WARN("fail to find the index position: "
+ "search_hash %llx, err %d\n",
+ start_hash1, err);
+ ssdfs_show_btree_node_info(node1);
+ BUG();
+ }
+
+ node_id1 = node1->node_id;
+
+ down_read(&node1->header_lock);
+ start_hash1 = node1->items_area.start_hash;
+ end_hash1 = node1->items_area.end_hash;
+ items_count = node1->items_area.items_count;
+ up_read(&node1->header_lock);
+
+ if (start_hash1 >= U64_MAX && end_hash1 >= U64_MAX) {
+ if (items_count == 0) {
+ /*
+ * empty node
+ */
+ rcu_read_lock();
+ continue;
+ } else {
+ SSDFS_WARN("node_id %u, "
+ "start_hash1 %llx, end_hash1 %llx\n",
+ node_id1, start_hash1, end_hash1);
+ ssdfs_show_btree_node_info(node1);
+ BUG();
+ }
+ } else if (start_hash1 >= U64_MAX || end_hash1 >= U64_MAX) {
+ SSDFS_WARN("node_id %u, "
+ "start_hash1 %llx, end_hash1 %llx\n",
+ node_id1, start_hash1, end_hash1);
+ ssdfs_show_btree_node_info(node1);
+ BUG();
+ }
+
+ rcu_read_lock();
+ radix_tree_for_each_slot(slot2, &tree->nodes, &iter2,
+ SSDFS_BTREE_ROOT_NODE_ID) {
+ node2 = SSDFS_BTN(radix_tree_deref_slot(slot2));
+
+ if (!node2)
+ continue;
+
+ if (is_ssdfs_btree_node_pre_deleted(node2)) {
+ SSDFS_DBG("node %u has pre-deleted state\n",
+ node2->node_id);
+ continue;
+ }
+
+ rcu_read_unlock();
+
+ is_exist = is_ssdfs_btree_node_items_area_exist(node2);
+
+ switch (atomic_read(&node2->type)) {
+ case SSDFS_BTREE_ROOT_NODE:
+ case SSDFS_BTREE_INDEX_NODE:
+ rcu_read_lock();
+ continue;
+
+ case SSDFS_BTREE_HYBRID_NODE:
+ case SSDFS_BTREE_LEAF_NODE:
+ if (!is_exist) {
+ SSDFS_ERR("corrupted node %u\n",
+ node2->node_id);
+ ssdfs_show_btree_node_info(node2);
+ BUG();
+ }
+ break;
+
+ default:
+ BUG();
+ }
+
+ node_id2 = node2->node_id;
+
+ if (node_id1 == node_id2) {
+ rcu_read_lock();
+ continue;
+ }
+
+ down_read(&node2->header_lock);
+ start_hash2 = node2->items_area.start_hash;
+ end_hash2 = node2->items_area.end_hash;
+ items_count = node2->items_area.items_count;
+ up_read(&node2->header_lock);
+
+ if (start_hash2 >= U64_MAX && end_hash2 >= U64_MAX) {
+ if (items_count == 0) {
+ /*
+ * empty node
+ */
+ rcu_read_lock();
+ continue;
+ } else {
+ SSDFS_WARN("node_id %u, "
+ "start_hash2 %llx, "
+ "end_hash2 %llx\n",
+ node_id2,
+ start_hash2,
+ end_hash2);
+ ssdfs_show_btree_node_info(node2);
+ BUG();
+ }
+ } else if (start_hash2 >= U64_MAX ||
+ end_hash2 >= U64_MAX) {
+ SSDFS_WARN("node_id %u, start_hash2 %llx, "
+ "end_hash2 %llx\n",
+ node_id2, start_hash2, end_hash2);
+ ssdfs_show_btree_node_info(node2);
+ BUG();
+ }
+
+ if (RANGE_HAS_PARTIAL_INTERSECTION(start_hash1,
+ end_hash1,
+ start_hash2,
+ end_hash2)) {
+ SSDFS_WARN("there is intersection: "
+ "node_id %u (start_hash %llx, "
+ "end_hash %llx), "
+ "node_id %u (start_hash %llx, "
+ "end_hash %llx)\n",
+ node_id1, start_hash1, end_hash1,
+ node_id2, start_hash2, end_hash2);
+ ssdfs_debug_show_btree_node_indexes(tree,
+ node1->parent_node);
+ ssdfs_show_btree_node_info(node1);
+ ssdfs_show_btree_node_info(node2);
+ BUG();
+ }
+
+ rcu_read_lock();
+ }
+
+ rcu_read_lock();
+ }
+ rcu_read_unlock();
+
+ up_read(&tree->lock);
+#endif /* CONFIG_SSDFS_BTREE_CONSISTENCY_CHECK */
+}
+
+void ssdfs_debug_btree_object(struct ssdfs_btree *tree)
+{
+#ifdef CONFIG_SSDFS_DEBUG
+ struct radix_tree_iter iter;
+ void **slot;
+ struct ssdfs_btree_node *node;
+
+ BUG_ON(!tree);
+
+ down_read(&tree->lock);
+
+ SSDFS_DBG("STATIC DATA: "
+ "type %#x, owner_ino %llu, node_size %u, "
+ "pages_per_node %u, node_ptr_size %u, "
+ "index_size %u, item_size %u, "
+ "min_item_size %u, max_item_size %u, "
+ "index_area_min_size %u, create_cno %llu, "
+ "fsi %p\n",
+ tree->type, tree->owner_ino,
+ tree->node_size, tree->pages_per_node,
+ tree->node_ptr_size, tree->index_size,
+ tree->item_size, tree->min_item_size,
+ tree->max_item_size, tree->index_area_min_size,
+ tree->create_cno, tree->fsi);
+
+ SSDFS_DBG("OPERATIONS: "
+ "desc_ops %p, btree_ops %p\n",
+ tree->desc_ops, tree->btree_ops);
+
+ SSDFS_DBG("MUTABLE DATA: "
+ "state %#x, flags %#x, height %d, "
+ "upper_node_id %u\n",
+ atomic_read(&tree->state),
+ atomic_read(&tree->flags),
+ atomic_read(&tree->height),
+ tree->upper_node_id);
+
+ SSDFS_DBG("tree->lock %d, nodes_lock %d\n",
+ rwsem_is_locked(&tree->lock),
+ spin_is_locked(&tree->nodes_lock));
+
+ rcu_read_lock();
+ radix_tree_for_each_slot(slot, &tree->nodes, &iter,
+ SSDFS_BTREE_ROOT_NODE_ID) {
+ node = SSDFS_BTN(radix_tree_deref_slot(slot));
+
+ if (!node)
+ continue;
+
+ SSDFS_DBG("NODE: node_id %u, state %#x, "
+ "type %#x, height %d, refs_count %d\n",
+ node->node_id,
+ atomic_read(&node->state),
+ atomic_read(&node->type),
+ atomic_read(&node->height),
+ atomic_read(&node->refs_count));
+
+ SSDFS_DBG("INDEX_AREA: state %#x, "
+ "offset %u, size %u, "
+ "index_size %u, index_count %u, "
+ "index_capacity %u, "
+ "start_hash %llx, end_hash %llx\n",
+ atomic_read(&node->index_area.state),
+ node->index_area.offset,
+ node->index_area.area_size,
+ node->index_area.index_size,
+ node->index_area.index_count,
+ node->index_area.index_capacity,
+ node->index_area.start_hash,
+ node->index_area.end_hash);
+
+ SSDFS_DBG("ITEMS_AREA: state %#x, "
+ "offset %u, size %u, free_space %u, "
+ "item_size %u, min_item_size %u, "
+ "max_item_size %u, items_count %u, "
+ "items_capacity %u, "
+ "start_hash %llx, end_hash %llx\n",
+ atomic_read(&node->items_area.state),
+ node->items_area.offset,
+ node->items_area.area_size,
+ node->items_area.free_space,
+ node->items_area.item_size,
+ node->items_area.min_item_size,
+ node->items_area.max_item_size,
+ node->items_area.items_count,
+ node->items_area.items_capacity,
+ node->items_area.start_hash,
+ node->items_area.end_hash);
+ }
+ rcu_read_unlock();
+
+ up_read(&tree->lock);
+#endif /* CONFIG_SSDFS_DEBUG */
+}
--
2.34.1
next prev parent reply other threads:[~2023-02-25 1:19 UTC|newest]
Thread overview: 82+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-02-25 1:08 [RFC PATCH 00/76] SSDFS: flash-friendly LFS file system for ZNS SSD Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 01/76] ssdfs: introduce SSDFS on-disk layout Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 02/76] ssdfs: key file system declarations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 03/76] ssdfs: implement raw device operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 04/76] ssdfs: implement super operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 05/76] ssdfs: implement commit superblock operation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 06/76] ssdfs: segment header + log footer operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 07/76] ssdfs: basic mount logic implementation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 08/76] ssdfs: search last actual superblock Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 09/76] ssdfs: internal array/sequence primitives Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 10/76] ssdfs: introduce PEB's block bitmap Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 11/76] ssdfs: block bitmap search operations implementation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 12/76] ssdfs: block bitmap modification " Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 13/76] ssdfs: introduce PEB block bitmap Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 14/76] ssdfs: PEB block bitmap modification operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 15/76] ssdfs: introduce segment block bitmap Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 16/76] ssdfs: introduce segment request queue Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 17/76] ssdfs: introduce offset translation table Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 18/76] ssdfs: flush " Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 19/76] ssdfs: offset translation table API implementation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 20/76] ssdfs: introduce PEB object Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 21/76] ssdfs: introduce PEB container Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 22/76] ssdfs: create/destroy " Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 23/76] ssdfs: PEB container API implementation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 24/76] ssdfs: PEB read thread's init logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 25/76] ssdfs: block bitmap initialization logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 26/76] ssdfs: offset translation table " Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 27/76] ssdfs: read/readahead logic of PEB's thread Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 28/76] ssdfs: PEB flush thread's finite state machine Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 29/76] ssdfs: commit log logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 30/76] ssdfs: commit log payload Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 31/76] ssdfs: process update request Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 32/76] ssdfs: process create request Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 33/76] ssdfs: create log logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 34/76] ssdfs: auxilairy GC threads logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 35/76] ssdfs: introduce segment object Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 36/76] ssdfs: segment object's add data/metadata operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 37/76] ssdfs: segment object's update/invalidate data/metadata Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 38/76] ssdfs: introduce PEB mapping table Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 39/76] ssdfs: flush " Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 40/76] ssdfs: convert/map LEB to PEB functionality Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 41/76] ssdfs: support migration scheme by PEB state Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 42/76] ssdfs: PEB mapping table thread logic Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 43/76] ssdfs: introduce PEB mapping table cache Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 44/76] ssdfs: PEB mapping table cache's modification operations Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 45/76] ssdfs: introduce segment bitmap Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 46/76] ssdfs: segment bitmap API implementation Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 47/76] ssdfs: introduce b-tree object Viacheslav Dubeyko
2023-02-25 1:08 ` [RFC PATCH 48/76] ssdfs: add/delete b-tree node Viacheslav Dubeyko
2023-02-25 1:09 ` Viacheslav Dubeyko [this message]
2023-02-25 1:09 ` [RFC PATCH 50/76] ssdfs: introduce b-tree node object Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 51/76] ssdfs: flush " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 52/76] ssdfs: b-tree node index operations Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 53/76] ssdfs: search/allocate/insert b-tree node operations Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 54/76] ssdfs: change/delete " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 55/76] ssdfs: range operations of b-tree node Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 56/76] ssdfs: introduce b-tree hierarchy object Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 57/76] ssdfs: check b-tree hierarchy for add operation Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 58/76] ssdfs: check b-tree hierarchy for update/delete operation Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 59/76] ssdfs: execute b-tree hierarchy modification Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 60/76] ssdfs: introduce inodes b-tree Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 61/76] ssdfs: inodes b-tree node operations Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 62/76] ssdfs: introduce dentries b-tree Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 63/76] ssdfs: dentries b-tree specialized operations Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 64/76] ssdfs: dentries b-tree node's " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 65/76] ssdfs: introduce extents queue object Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 66/76] ssdfs: introduce extents b-tree Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 67/76] ssdfs: extents b-tree specialized operations Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 68/76] ssdfs: search extent logic in extents b-tree node Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 69/76] ssdfs: add/change/delete extent " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 70/76] ssdfs: introduce invalidated extents b-tree Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 71/76] ssdfs: find item in " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 72/76] ssdfs: modification operations of " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 73/76] ssdfs: implement inode operations support Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 74/76] ssdfs: implement directory " Viacheslav Dubeyko
2023-02-25 1:09 ` [RFC PATCH 75/76] ssdfs: implement file " Viacheslav Dubeyko
2023-02-25 3:01 ` Matthew Wilcox
2023-02-26 23:42 ` [External] " Viacheslav A.Dubeyko
2023-02-25 1:09 ` [RFC PATCH 76/76] introduce SSDFS file system Viacheslav Dubeyko
2023-02-27 13:53 ` [RFC PATCH 00/76] SSDFS: flash-friendly LFS file system for ZNS SSD Stefan Hajnoczi
2023-02-27 22:59 ` [External] " Viacheslav A.Dubeyko
2023-02-28 13:59 ` Stefan Hajnoczi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230225010927.813929-50-slava@dubeyko.com \
--to=slava@dubeyko.com \
--cc=bruno.banelli@sartura.hr \
--cc=linux-fsdevel@vger.kernel.org \
--cc=luka.perkov@sartura.hr \
--cc=viacheslav.dubeyko@bytedance.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).