@@ -8207,3 +8207,3138 @@ int ssdfs_btree_node_change_index(struct ssdfs_btree_node *node,
return err;
}
+
+/*
+ * ssdfs_btree_root_node_delete_index() - delete index record from root node
+ * @node: node object
+ * @position: position in the node of the deleting index record
+ *
+ * This method tries to delete the index record from the root node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_root_node_delete_index(struct ssdfs_btree_node *node,
+ u16 position)
+{
+ size_t index_size = sizeof(struct ssdfs_btree_index);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+ BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+ SSDFS_DBG("index 0: node_id %u; index 1: node_id %u\n",
+ cpu_to_le32(node->raw.root_node.header.node_ids[0]),
+ cpu_to_le32(node->raw.root_node.header.node_ids[1]));
+ SSDFS_DBG("node_id %u, position %u\n",
+ node->node_id, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (node->index_area.index_count > node->index_area.index_capacity) {
+ SSDFS_ERR("index_count %u > index_capacity %u\n",
+ node->index_area.index_count,
+ node->index_area.index_capacity);
+ return -ERANGE;
+ }
+
+ if (position >= node->index_area.index_count) {
+ SSDFS_ERR("invalid position %u, index_count %u\n",
+ position,
+ node->index_area.index_count);
+ return -ERANGE;
+ }
+
+ if (node->index_area.index_count == 0) {
+ SSDFS_WARN("index_count == 0\n");
+ return -ERANGE;
+ }
+
+ switch (position) {
+ case SSDFS_ROOT_NODE_LEFT_LEAF_NODE:
+ if ((position + 1) < node->index_area.index_count) {
+ node->index_area.start_hash = node->index_area.end_hash;
+ ssdfs_memcpy(&node->raw.root_node.indexes[position],
+ 0, index_size,
+ &node->raw.root_node.indexes[position + 1],
+ 0, index_size,
+ index_size);
+ memset(&node->raw.root_node.indexes[position + 1], 0xFF,
+ index_size);
+ node->raw.root_node.header.node_ids[position + 1] =
+ cpu_to_le32(U32_MAX);
+ } else {
+ node->index_area.start_hash = U64_MAX;
+ node->index_area.end_hash = U64_MAX;
+ memset(&node->raw.root_node.indexes[position], 0xFF,
+ index_size);
+ node->raw.root_node.header.node_ids[position] =
+ cpu_to_le32(U32_MAX);
+ }
+ break;
+
+ case SSDFS_ROOT_NODE_RIGHT_LEAF_NODE:
+ node->index_area.end_hash = node->index_area.start_hash;
+ memset(&node->raw.root_node.indexes[position], 0xFF,
+ index_size);
+ node->raw.root_node.header.node_ids[position] =
+ cpu_to_le32(U32_MAX);
+ break;
+
+ default:
+ BUG();
+ }
+
+ node->index_area.index_count--;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node->index_area.index_count %u\n",
+ node->index_area.index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_delete_tail_index() - delete the tail index record
+ * @node: node object
+ * @position: position in the node of the deleting index record
+ * @ptr: index record before @position [out]
+ *
+ * This method tries to delete the tail index record from the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_btree_common_node_delete_tail_index(struct ssdfs_btree_node *node,
+ u16 position,
+ struct ssdfs_btree_index_key *ptr)
+{
+ size_t index_size = sizeof(struct ssdfs_btree_index_key);
+ struct page *page;
+ u32 page_index;
+ u32 page_off;
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !ptr);
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+ BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+ SSDFS_DBG("node_id %u, position %u\n",
+ node->node_id, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if ((position + 1) != node->index_area.index_count) {
+ SSDFS_ERR("cannot delete index: "
+ "position %u, index_count %u\n",
+ position,
+ node->index_area.index_count);
+ return -ERANGE;
+ }
+
+ err = ssdfs_define_memory_page(node, &node->index_area,
+ position,
+ &page_index, &page_off);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to define memory page: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, position, err);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(page_index >= U32_MAX);
+ BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("page_index %u > pvec_size %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+
+ if ((page_off + index_size) > PAGE_SIZE) {
+ SSDFS_ERR("invalid page_off %u\n",
+ page_off);
+ return -ERANGE;
+ }
+
+ page = node->content.pvec.pages[page_index];
+ ssdfs_lock_page(page);
+ ssdfs_memset_page(page, page_off, PAGE_SIZE,
+ 0xFF, index_size);
+ ssdfs_unlock_page(page);
+
+ if (position == 0)
+ memset(ptr, 0xFF, index_size);
+ else {
+ err = ssdfs_define_memory_page(node, &node->index_area,
+ position - 1,
+ &page_index, &page_off);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to define memory page: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, position - 1, err);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(page_index >= U32_MAX);
+ BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("page_index %u > pvec_size %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+
+ page = node->content.pvec.pages[page_index];
+ ssdfs_lock_page(page);
+ ssdfs_memcpy_from_page(ptr, 0, index_size,
+ page, page_off, PAGE_SIZE,
+ index_size);
+ ssdfs_unlock_page(page);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy: err %d\n", err);
+ return err;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_remove_index() - remove the index record
+ * @node: node object
+ * @position: position in the node of the deleting index record
+ * @ptr: index record on @position after deletion [out]
+ *
+ * This method tries to delete the index record from the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_btree_common_node_remove_index(struct ssdfs_btree_node *node,
+ u16 position,
+ struct ssdfs_btree_index_key *ptr)
+{
+ struct ssdfs_btree_index_key buffer;
+ struct page *page;
+ void *kaddr;
+ u32 page_index;
+ u32 page_off;
+ u16 cur_pos = position;
+ u8 index_size;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !ptr);
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+ BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+ SSDFS_DBG("node_id %u, position %u\n",
+ node->node_id, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (!((position + 1) < node->index_area.index_count)) {
+ SSDFS_ERR("cannot remove index: "
+ "position %u, index_count %u\n",
+ position,
+ node->index_area.index_count);
+ return -ERANGE;
+ }
+
+ index_size = node->index_area.index_size;
+ if (index_size != sizeof(struct ssdfs_btree_index_key)) {
+ SSDFS_ERR("invalid index_size %u\n",
+ index_size);
+ return -ERANGE;
+ }
+
+ do {
+ u32 rest_capacity;
+ u32 moving_count;
+ u32 moving_bytes;
+
+ err = ssdfs_define_memory_page(node, &node->index_area,
+ cur_pos,
+ &page_index, &page_off);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to define memory page: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, cur_pos, err);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("cur_pos %u, page_index %u, page_off %u\n",
+ cur_pos, page_index, page_off);
+
+ BUG_ON(page_index >= U32_MAX);
+ BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ rest_capacity = PAGE_SIZE - (page_off + index_size);
+ rest_capacity /= index_size;
+
+ moving_count = node->index_area.index_count - (cur_pos + 1);
+ moving_count = min_t(u32, moving_count, rest_capacity);
+ moving_bytes = moving_count * index_size;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("rest_capacity %u, index_count %u, "
+ "moving_count %u, moving_bytes %u\n",
+ rest_capacity,
+ node->index_area.index_count,
+ moving_count, moving_bytes);
+
+ if ((page_off + index_size) > PAGE_SIZE) {
+ SSDFS_WARN("invalid offset: "
+ "page_off %u, index_size %u\n",
+ page_off, index_size);
+ return -ERANGE;
+ }
+
+ if ((page_off + moving_bytes) > PAGE_SIZE) {
+ SSDFS_WARN("invalid offset: "
+ "page_off %u, moving_bytes %u\n",
+ page_off, moving_bytes);
+ return -ERANGE;
+ }
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("page_index %u > pvec_size %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ page = node->content.pvec.pages[page_index];
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!page);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ ssdfs_lock_page(page);
+ kaddr = kmap_local_page(page);
+
+ if (moving_count == 0) {
+ err = ssdfs_memcpy(&buffer, 0, index_size,
+ kaddr, page_off, PAGE_SIZE,
+ index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy: err %d\n", err);
+ goto finish_copy;
+ }
+
+ memset((u8 *)kaddr + page_off, 0xFF, index_size);
+ } else {
+ err = ssdfs_memcpy(&buffer, 0, index_size,
+ kaddr, page_off, PAGE_SIZE,
+ index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy: err %d\n", err);
+ goto finish_copy;
+ }
+
+ err = ssdfs_memmove(kaddr,
+ page_off, PAGE_SIZE,
+ kaddr,
+ page_off + index_size, PAGE_SIZE,
+ moving_bytes);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to move: err %d\n", err);
+ goto finish_copy;
+ }
+
+ memset((u8 *)kaddr + page_off + moving_bytes,
+ 0xFF, index_size);
+ }
+
+ if (cur_pos == position) {
+ err = ssdfs_memcpy(ptr, 0, index_size,
+ kaddr, page_off, PAGE_SIZE,
+ index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy: err %d\n", err);
+ goto finish_copy;
+ }
+ }
+
+finish_copy:
+ flush_dcache_page(page);
+ kunmap_local(kaddr);
+ ssdfs_unlock_page(page);
+
+ if (unlikely(err))
+ return err;
+
+ if (cur_pos != position) {
+ err = ssdfs_define_memory_page(node, &node->index_area,
+ cur_pos - 1,
+ &page_index, &page_off);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to define memory page: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, cur_pos - 1, err);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("cur_pos %u, page_index %u, page_off %u\n",
+ cur_pos, page_index, page_off);
+
+ BUG_ON(page_index >= U32_MAX);
+ BUG_ON(page_off >= U32_MAX);
+
+ if ((page_off + index_size) > PAGE_SIZE) {
+ SSDFS_WARN("invalid offset: "
+ "page_off %u, index_size %u\n",
+ page_off, index_size);
+ return -ERANGE;
+ }
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("page_index %u > pvec_size %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ page = node->content.pvec.pages[page_index];
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!page);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ ssdfs_lock_page(page);
+ err = ssdfs_memcpy_to_page(page, page_off, PAGE_SIZE,
+ &buffer, 0, index_size,
+ index_size);
+ ssdfs_unlock_page(page);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy: err %d\n", err);
+ return err;
+ }
+ }
+
+ cur_pos += moving_count + 1;
+ } while (cur_pos < node->index_area.index_count);
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_delete_index() - delete the index record
+ * @node: node object
+ * @position: position in the node of the deleting index record
+ *
+ * This method tries to delete the index record from the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ */
+int ssdfs_btree_common_node_delete_index(struct ssdfs_btree_node *node,
+ u16 position)
+{
+ struct ssdfs_btree_index_key buffer;
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+ BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+ SSDFS_DBG("node_id %u, position %u, index_count %u\n",
+ node->node_id, position,
+ node->index_area.index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (node->index_area.index_count > node->index_area.index_capacity) {
+ SSDFS_ERR("index_count %u > index_capacity %u\n",
+ node->index_area.index_count,
+ node->index_area.index_capacity);
+ return -ERANGE;
+ }
+
+ if (node->index_area.index_count == 0) {
+ SSDFS_WARN("index_count == 0\n");
+ return -ERANGE;
+ }
+
+ if (position >= node->index_area.index_count) {
+ SSDFS_ERR("invalid index place: "
+ "position %u, index_count %u\n",
+ position,
+ node->index_area.index_count);
+ return -ERANGE;
+ }
+
+ if ((position + 1) == node->index_area.index_count) {
+ err = ssdfs_btree_common_node_delete_tail_index(node, position,
+ &buffer);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete index: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, position, err);
+ return err;
+ }
+ } else {
+ err = ssdfs_btree_common_node_remove_index(node, position,
+ &buffer);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to remove index: "
+ "node_id %u, position %u, err %d\n",
+ node->node_id, position, err);
+ return err;
+ }
+ }
+
+ node->index_area.index_count--;
+
+ switch (node->tree->type) {
+ case SSDFS_INODES_BTREE:
+ /* keep the index range unchanged */
+ goto finish_common_node_delete_index;
+
+ default:
+ /* continue logic */
+ break;
+ }
+
+ if (node->index_area.index_count == 0) {
+ node->index_area.start_hash = U64_MAX;
+ node->index_area.end_hash = U64_MAX;
+ } else {
+ if (position == 0) {
+ node->index_area.start_hash =
+ le64_to_cpu(buffer.index.hash);
+ } else if (position == node->index_area.index_count) {
+ node->index_area.end_hash =
+ le64_to_cpu(buffer.index.hash);
+ }
+ }
+
+finish_common_node_delete_index:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("start_hash %llx, end_hash %llx, "
+ "index_count %u, index_capacity %u\n",
+ node->index_area.start_hash,
+ node->index_area.end_hash,
+ node->index_area.index_count,
+ node->index_area.index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return 0;
+}
+
+/*
+ * need_shrink_index_area() - check that index area should be shrinked
+ * @node: node object
+ * @new_size: new size of the node after shrinking [out]
+ */
+static
+bool need_shrink_index_area(struct ssdfs_btree_node *node, u32 *new_size)
+{
+ u16 index_area_min_size;
+ u16 count, capacity;
+ u8 index_size;
+ bool need_check_size = false;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !node->tree || !new_size);
+
+ SSDFS_DBG("node_id %u\n", node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ *new_size = U32_MAX;
+ index_area_min_size = node->tree->index_area_min_size;
+
+ down_read(&node->header_lock);
+ count = node->index_area.index_count;
+ capacity = node->index_area.index_capacity;
+ index_size = node->index_area.index_size;
+ if (capacity == 0)
+ err = -ERANGE;
+ if (count > capacity)
+ err = -ERANGE;
+ up_read(&node->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_WARN("count %u > capacity %u\n",
+ count, capacity);
+ return false;
+ }
+
+ if (index_area_min_size == 0 || index_area_min_size % index_size) {
+ SSDFS_WARN("invalid index size: "
+ "index_area_min_size %u, index_size %u\n",
+ index_area_min_size, index_size);
+ return false;
+ }
+
+ if (count == 0)
+ need_check_size = true;
+ else
+ need_check_size = ((capacity / count) >= 2);
+
+ if (need_check_size) {
+ *new_size = (capacity / 2) * index_size;
+ if (*new_size >= index_area_min_size)
+ return true;
+ else
+ *new_size = U32_MAX;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("count %u, capacity %u, index_size %u, "
+ "index_area_min_size %u, new_size %u\n",
+ count, capacity, index_size,
+ index_area_min_size, *new_size);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return false;
+}
+
+/*
+ * ssdfs_btree_node_delete_index() - delete existing index
+ * @node: node object
+ * @hash: hash value
+ *
+ * This method tries to delete index for @hash from node's
+ * index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENODATA - node's index area doesn't contain index for @hash.
+ * %-ENOENT - node hasn't the index area.
+ * %-EFAULT - corrupted node's index area.
+ * %-EACCES - node is under initialization yet.
+ */
+int ssdfs_btree_node_delete_index(struct ssdfs_btree_node *node,
+ u64 hash)
+{
+ struct ssdfs_fs_info *fsi;
+ int node_type;
+ u16 found = U16_MAX;
+ u16 count;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !node->tree || !node->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+ SSDFS_DBG("node_id %u, hash %llx\n",
+ node->node_id, hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = node->tree->fsi;
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u hasn't index area\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ENOENT;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ if (hash == U64_MAX) {
+ SSDFS_ERR("invalid hash %llx\n", hash);
+ return -ERANGE;
+ }
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ node_type = atomic_read(&node->type);
+ if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+ node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+ SSDFS_ERR("invalid node type %#x\n",
+ node_type);
+ return -ERANGE;
+ }
+
+ if (node_type == SSDFS_BTREE_ROOT_NODE) {
+ down_read(&node->full_lock);
+ down_write(&node->header_lock);
+
+ err = ssdfs_find_index_by_hash(node, &node->index_area,
+ hash, &found);
+ if (err == -EEXIST) {
+ /* hash == found hash */
+ err = 0;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find an index: "
+ "node_id %u, hash %llx, err %d\n",
+ node->node_id, hash, err);
+ goto finish_change_root_node;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(found == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = ssdfs_btree_root_node_delete_index(node, found);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete index: "
+ "node_id %u, node_type %#x, "
+ "found_index %u, err %d\n",
+ node->node_id, node_type,
+ found, err);
+ }
+
+finish_change_root_node:
+ up_write(&node->header_lock);
+ up_read(&node->full_lock);
+
+ if (unlikely(err))
+ return err;
+ } else {
+ down_write(&node->full_lock);
+ down_write(&node->header_lock);
+
+ err = ssdfs_find_index_by_hash(node, &node->index_area,
+ hash, &found);
+ if (err == -EEXIST) {
+ /* hash == found hash */
+ err = 0;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find an index: "
+ "node_id %u, hash %llx, err %d\n",
+ node->node_id, hash, err);
+ up_write(&node->header_lock);
+ up_write(&node->full_lock);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(found == U16_MAX);
+
+ SSDFS_DBG("index_count %u, found %u\n",
+ node->index_area.index_count, found);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ count = node->index_area.index_count - found;
+ err = ssdfs_lock_index_range(node, found, count);
+ BUG_ON(err == -ENODATA);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to lock index range: "
+ "start %u, count %u, err %d\n",
+ found, count, err);
+ up_write(&node->header_lock);
+ up_write(&node->full_lock);
+ return err;
+ }
+
+ downgrade_write(&node->full_lock);
+
+ err = ssdfs_btree_common_node_delete_index(node, found);
+ ssdfs_unlock_index_range(node, found, count);
+
+ if (!err)
+ err = ssdfs_set_dirty_index_range(node, found, count);
+
+ up_write(&node->header_lock);
+ up_read(&node->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete index: "
+ "node_id %u, node_type %#x, "
+ "found_index %u, err %d\n",
+ node->node_id, node_type,
+ found, err);
+ }
+ }
+
+ ssdfs_set_node_update_cno(node);
+ set_ssdfs_btree_node_dirty(node);
+
+ if (node_type != SSDFS_BTREE_ROOT_NODE) {
+ u32 new_size;
+
+ if (need_shrink_index_area(node, &new_size)) {
+ err = ssdfs_btree_node_resize_index_area(node,
+ new_size);
+ if (err == -ENOSPC) {
+ err = 0;
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("index area cannot be resized: "
+ "node_id %u\n", node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to resize index area: "
+ "node_id %u, new_size %u, err %d\n",
+ node->node_id, new_size, err);
+ return err;
+ }
+ }
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("start_hash %llx, end_hash %llx, "
+ "index_count %u, index_capacity %u\n",
+ node->index_area.start_hash,
+ node->index_area.end_hash,
+ node->index_area.index_count,
+ node->index_area.index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return 0;
+}
+
+/*
+ * ssdfs_move_root2common_node_index_range() - move index range (root -> common)
+ * @src: source node
+ * @src_start: starting index in the source node
+ * @dst: destination node
+ * @dst_start: starting index in the destination node
+ * @count: count of indexes in the range
+ *
+ * This method tries to move the index range from the source node
+ * into destination one.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_move_root2common_node_index_range(struct ssdfs_btree_node *src,
+ u16 src_start,
+ struct ssdfs_btree_node *dst,
+ u16 dst_start, u16 count)
+{
+ struct ssdfs_fs_info *fsi;
+ int i, j;
+ int upper_bound;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!src || !dst);
+ BUG_ON(!src->tree || !src->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&src->tree->lock));
+
+ if (!is_ssdfs_btree_node_index_area_exist(src)) {
+ SSDFS_DBG("src node %u hasn't index area\n",
+ src->node_id);
+ return -EINVAL;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(dst)) {
+ SSDFS_DBG("dst node %u hasn't index area\n",
+ dst->node_id);
+ return -EINVAL;
+ }
+
+ if (atomic_read(&src->type) != SSDFS_BTREE_ROOT_NODE) {
+ SSDFS_ERR("invalid src node type %#x\n",
+ atomic_read(&src->type));
+ return -EINVAL;
+ }
+
+ SSDFS_DBG("src_node %u, src_start %u, "
+ "dst_node %u, dst_start %u, "
+ "count %u\n",
+ src->node_id, src_start,
+ dst->node_id, dst_start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = src->tree->fsi;
+
+ if (src_start >= SSDFS_BTREE_ROOT_NODE_INDEX_COUNT) {
+ SSDFS_ERR("invalid src_start %u\n",
+ src_start);
+ return -ERANGE;
+ }
+
+ if (count == 0) {
+ SSDFS_ERR("count is zero\n");
+ return -ERANGE;
+ }
+
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CREATED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CREATED);
+
+ count = min_t(u16, count,
+ SSDFS_BTREE_ROOT_NODE_INDEX_COUNT - src_start);
+
+ upper_bound = src_start + count;
+ for (i = src_start, j = dst_start; i < upper_bound; i++, j++) {
+ struct ssdfs_btree_index_key index;
+
+ down_write(&src->full_lock);
+
+ err = __ssdfs_btree_root_node_extract_index(src, i,
+ &index);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail extract index: "
+ "index %u, err %d\n",
+ i, err);
+ }
+
+ up_write(&src->full_lock);
+
+ if (unlikely(err)) {
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CORRUPTED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CORRUPTED);
+ return err;
+ }
+
+ down_write(&dst->full_lock);
+
+ down_write(&dst->header_lock);
+ err = ssdfs_btree_common_node_add_index(dst, j, &index);
+ up_write(&dst->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert index: "
+ "index %u, err %d\n",
+ j, err);
+ }
+
+ up_write(&dst->full_lock);
+
+ if (unlikely(err)) {
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CORRUPTED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CORRUPTED);
+ return err;
+ }
+ }
+
+ for (i = 0; i < count; i++) {
+ down_write(&src->full_lock);
+
+ down_write(&src->header_lock);
+ err = ssdfs_btree_root_node_delete_index(src, src_start);
+ up_write(&src->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to delete index: "
+ "index %u, err %d\n",
+ i, err);
+ }
+
+ up_write(&src->full_lock);
+
+ if (unlikely(err)) {
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CORRUPTED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CORRUPTED);
+ return err;
+ }
+ }
+
+ ssdfs_set_node_update_cno(src);
+ set_ssdfs_btree_node_dirty(src);
+
+ ssdfs_set_node_update_cno(dst);
+ set_ssdfs_btree_node_dirty(dst);
+
+ return 0;
+}
+
+/*
+ * ssdfs_copy_index_range_in_buffer() - copy index range in buffer
+ * @node: node object
+ * @start: starting index in the node
+ * @count: requested count of indexes in the range
+ * @area_offset: offset of the index area in the node
+ * @index_size: size of the index in bytes
+ * @buf: pointer on buffer
+ * @range_len: pointer on value of count of indexes in the buffer [out]
+ *
+ * This method tries to copy the index range into the buffer.
+ * If a current memory page of node contains lesser amount of indexes
+ * then @range_len will contain real number of indexes in the @buf.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_copy_index_range_in_buffer(struct ssdfs_btree_node *node,
+ u16 start, u16 count,
+ u32 area_offset, u16 index_size,
+ struct ssdfs_btree_index_key *buf,
+ u16 *range_len)
+{
+ struct page *page;
+ u32 offset;
+ u32 page_index;
+ u32 page_off;
+ u32 copy_bytes;
+#ifdef CONFIG_SSDFS_DEBUG
+ int i;
+#endif /* CONFIG_SSDFS_DEBUG */
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !buf || !range_len);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ SSDFS_DBG("node %u hasn't index area\n",
+ node->node_id);
+ return -EINVAL;
+ }
+
+ SSDFS_DBG("node %u, start %u, count %u\n",
+ node->node_id, start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (count == 0) {
+ SSDFS_ERR("count is zero\n");
+ return -ERANGE;
+ }
+
+ *range_len = U16_MAX;
+
+ offset = area_offset + (start * index_size);
+ page_index = offset / PAGE_SIZE;
+ page_off = offset % PAGE_SIZE;
+
+ *range_len = PAGE_SIZE - page_off;
+ *range_len /= index_size;
+ *range_len = min_t(u32, *range_len, (u32)count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("offset %u, page_index %u, page_off %u\n",
+ offset, page_index, page_off);
+ SSDFS_DBG("start %u, count %u, range_len %u\n",
+ start, count, *range_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (*range_len == 0) {
+ SSDFS_ERR("range_len == 0\n");
+ return -ERANGE;
+ }
+
+ copy_bytes = *range_len * index_size;
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("invalid page_index: "
+ "page_index %u, pagevec %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+
+ page = node->content.pvec.pages[page_index];
+
+ if (!page) {
+ SSDFS_ERR("page is NULL\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_memcpy_from_page(buf, 0, PAGE_SIZE,
+ page, page_off, PAGE_SIZE,
+ copy_bytes);
+ if (unlikely(err)) {
+ SSDFS_ERR("buffer is too small: "
+ "range_len %u, index_size %u, "
+ "buf_size %lu\n",
+ *range_len, index_size,
+ PAGE_SIZE);
+ return err;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ for (i = 0; i < *range_len; i++) {
+ SSDFS_DBG("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(buf[i].node_id),
+ buf[i].node_type,
+ buf[i].height,
+ le16_to_cpu(buf[i].flags),
+ le64_to_cpu(buf[i].index.hash),
+ le64_to_cpu(buf[i].index.extent.seg_id),
+ le32_to_cpu(buf[i].index.extent.logical_blk),
+ le32_to_cpu(buf[i].index.extent.len));
+ }
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return 0;
+}
+
+/*
+ * ssdfs_save_index_range_in_node() - save index range in the node
+ * @node: node object
+ * @start: starting index in the node
+ * @count: requested count of indexes in the range
+ * @area_offset: offset of the index area in the node
+ * @index_size: size of the index in bytes
+ * @buf: pointer on buffer
+ *
+ * This method tries to save the index range from @buf into @node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_save_index_range_in_node(struct ssdfs_btree_node *node,
+ u16 start, u16 count,
+ u32 area_offset, u16 index_size,
+ struct ssdfs_btree_index_key *buf)
+{
+ struct page *page;
+ u32 offset;
+ u32 page_index;
+ u32 page_off;
+ int i;
+ u16 copied = 0;
+ u32 sub_range_len = 0;
+ int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !buf);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ SSDFS_DBG("node %u hasn't index area\n",
+ node->node_id);
+ return -EINVAL;
+ }
+
+ SSDFS_DBG("node %u, start %u, count %u\n",
+ node->node_id, start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (count == 0) {
+ SSDFS_ERR("count is zero\n");
+ return -ERANGE;
+ }
+
+ i = start;
+
+ while (count > 0) {
+ offset = area_offset + (i * index_size);
+ page_index = offset / PAGE_SIZE;
+ page_off = offset % PAGE_SIZE;
+
+ sub_range_len = PAGE_SIZE - page_off;
+ sub_range_len /= index_size;
+ sub_range_len = min_t(u32, sub_range_len, count);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("i %d, offset %u, page_index %u, "
+ "page_off %u, sub_range_len %u\n",
+ i, offset, page_index,
+ page_off, sub_range_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (sub_range_len == 0) {
+ SSDFS_ERR("invalid sub_range_len: "
+ "i %d, count %u, "
+ "page_index %u, page_off %u, "
+ "sub_range_len %u\n",
+ i, count, page_index, page_off,
+ sub_range_len);
+ return -ERANGE;
+ }
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("invalid page_index: "
+ "page_index %u, pagevec %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+
+ page = node->content.pvec.pages[page_index];
+
+ if (!page) {
+ SSDFS_ERR("page is NULL\n");
+ return -ERANGE;
+ }
+
+ if ((page_off + (sub_range_len * index_size)) > PAGE_SIZE) {
+ SSDFS_ERR("out of page: "
+ "page_off %u, sub_range_len %u, "
+ "index_size %u, page_size %lu\n",
+ page_off, sub_range_len, index_size,
+ PAGE_SIZE);
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("i %u, count %u, page_index %u, "
+ "page_off %u, copied %u, sub_range_len %u\n",
+ i, count, page_index,
+ page_off, copied, sub_range_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = ssdfs_memcpy_to_page(page, page_off, PAGE_SIZE,
+ buf, copied * index_size, PAGE_SIZE,
+ sub_range_len * index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("out of page: "
+ "sub_range_len %u, index_size %u, "
+ "page_size %lu\n",
+ sub_range_len, index_size,
+ PAGE_SIZE);
+ return err;
+ }
+
+ err = ssdfs_set_dirty_index_range(node, i,
+ (u16)sub_range_len);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to set dirty index range: "
+ "start %u, len %u, err %d\n",
+ i, sub_range_len, err);
+ return err;
+ }
+
+ i += sub_range_len;
+ copied += sub_range_len;
+ count -= sub_range_len;
+ };
+
+ return 0;
+}
+
+/*
+ * ssdfs_clear_index_range_in_node() - clear index range in the node
+ * @node: node object
+ * @start: starting index in the node
+ * @count: requested count of indexes in the range
+ * @area_offset: offset of the index area in the node
+ * @index_size: size of the index in bytes
+ *
+ * This method tries to clear the index range into @node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_clear_index_range_in_node(struct ssdfs_btree_node *node,
+ u16 start, u16 count,
+ u32 area_offset, u16 index_size)
+{
+ struct page *page;
+ u32 offset;
+ u32 page_index;
+ u32 page_off;
+ int i;
+ u32 sub_range_len = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+ BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+ if (!is_ssdfs_btree_node_index_area_exist(node)) {
+ SSDFS_DBG("node %u hasn't index area\n",
+ node->node_id);
+ return -EINVAL;
+ }
+
+ SSDFS_DBG("node %u, start %u, count %u\n",
+ node->node_id, start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (count == 0) {
+ SSDFS_ERR("count is zero\n");
+ return -ERANGE;
+ }
+
+ i = start;
+
+ while (count > 0) {
+ offset = area_offset + (i * index_size);
+ page_index = offset / PAGE_SIZE;
+ page_off = offset % PAGE_SIZE;
+
+ sub_range_len = PAGE_SIZE - page_off;
+ sub_range_len /= index_size;
+ sub_range_len = min_t(u32, sub_range_len, count);
+
+ if (sub_range_len == 0) {
+ SSDFS_ERR("invalid sub_range_len: "
+ "i %d, count %u, "
+ "page_index %u, page_off %u, "
+ "sub_range_len %u\n",
+ i, count, page_index, page_off,
+ sub_range_len);
+ return -ERANGE;
+ }
+
+ if ((sub_range_len * index_size) > PAGE_SIZE) {
+ SSDFS_ERR("out of page: "
+ "sub_range_len %u, index_size %u, "
+ "page_size %lu\n",
+ sub_range_len, index_size,
+ PAGE_SIZE);
+ return -ERANGE;
+ }
+
+ if (page_index >= pagevec_count(&node->content.pvec)) {
+ SSDFS_ERR("invalid page_index: "
+ "page_index %u, pagevec %u\n",
+ page_index,
+ pagevec_count(&node->content.pvec));
+ return -ERANGE;
+ }
+
+ page = node->content.pvec.pages[page_index];
+
+ if (!page) {
+ SSDFS_ERR("page is NULL\n");
+ return -ERANGE;
+ }
+
+ if ((page_off + (sub_range_len * index_size)) > PAGE_SIZE) {
+ SSDFS_ERR("out of page: "
+ "page_off %u, sub_range_len %u, "
+ "index_size %u, page_size %lu\n",
+ page_off, sub_range_len, index_size,
+ PAGE_SIZE);
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("start %u, count %u, page_index %u, "
+ "page_off %u, sub_range_len %u\n",
+ start, count, page_index,
+ page_off, sub_range_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ ssdfs_memset_page(page, page_off, PAGE_SIZE,
+ 0xFF, sub_range_len * index_size);
+
+ i += sub_range_len;
+ count -= sub_range_len;
+ };
+
+ return 0;
+}
+
+/*
+ * ssdfs_move_common2common_node_index_range() - move index range
+ * @src: source node
+ * @src_start: starting index in the source node
+ * @dst: destination node
+ * @dst_start: starting index in the destination node
+ * @count: count of indexes in the range
+ *
+ * This method tries to move the index range from the common node
+ * @src into the common node @dst.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ */
+static
+int ssdfs_move_common2common_node_index_range(struct ssdfs_btree_node *src,
+ u16 src_start,
+ struct ssdfs_btree_node *dst,
+ u16 dst_start, u16 count)
+{
+ struct ssdfs_fs_info *fsi;
+ struct ssdfs_btree_index_key *buf;
+ u16 i, j;
+ u32 src_offset, dst_offset;
+ u32 src_area_size, dst_area_size;
+ u16 index_size;
+ u16 src_index_count, dst_index_count;
+ u16 dst_index_capacity;
+ u64 src_start_hash, src_end_hash;
+ u64 dst_start_hash, dst_end_hash;
+ u16 processed = 0;
+ u16 copied = 0;
+ u16 rest_unmoved = 0;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!src || !dst);
+ BUG_ON(!src->tree || !src->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&src->tree->lock));
+
+ if (!is_ssdfs_btree_node_index_area_exist(src)) {
+ SSDFS_DBG("src node %u hasn't index area\n",
+ src->node_id);
+ return -EINVAL;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(dst)) {
+ SSDFS_DBG("dst node %u hasn't index area\n",
+ dst->node_id);
+ return -EINVAL;
+ }
+
+ SSDFS_DBG("src_node %u, src_start %u, "
+ "dst_node %u, dst_start %u, "
+ "count %u\n",
+ src->node_id, src_start,
+ dst->node_id, dst_start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = src->tree->fsi;
+
+ if (count == 0) {
+ SSDFS_ERR("count is zero\n");
+ return -ERANGE;
+ }
+
+ buf = ssdfs_btree_node_kzalloc(PAGE_SIZE, GFP_KERNEL);
+ if (!buf) {
+ SSDFS_ERR("fail to allocate buffer\n");
+ return -ERANGE;
+ }
+
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CREATED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CREATED);
+
+ down_read(&src->header_lock);
+ src_offset = src->index_area.offset;
+ src_area_size = src->index_area.area_size;
+ index_size = src->index_area.index_size;
+ src_index_count = src->index_area.index_count;
+ src_start_hash = src->index_area.start_hash;
+ src_end_hash = src->index_area.end_hash;
+ up_read(&src->header_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("src_node %u, index_count %u, count %u\n",
+ src->node_id, src_index_count, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ down_read(&dst->header_lock);
+ dst_offset = dst->index_area.offset;
+ dst_area_size = dst->index_area.area_size;
+ dst_index_count = dst->index_area.index_count;
+ dst_index_capacity = dst->index_area.index_capacity;
+ dst_start_hash = dst->index_area.start_hash;
+ dst_end_hash = dst->index_area.end_hash;
+ up_read(&dst->header_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("dst_node %u, index_count %u, "
+ "count %u, dst_index_capacity %u\n",
+ dst->node_id, dst_index_count,
+ count, dst_index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if ((src_start + count) > src_index_count) {
+ err = -ERANGE;
+ SSDFS_ERR("invalid count: "
+ "src_start %u, count %u, "
+ "src_index_count %u\n",
+ src_start, count, src_index_count);
+ goto finish_index_moving;
+ }
+
+ if ((dst_index_count + count) > dst_index_capacity) {
+ err = -ERANGE;
+ SSDFS_ERR("invalid count: "
+ "dst_index_count %u, count %u, "
+ "dst_index_capacity %u\n",
+ dst_index_count, count,
+ dst_index_capacity);
+ goto finish_index_moving;
+ }
+
+ i = src_start;
+ j = dst_start;
+
+ down_write(&src->full_lock);
+ err = ssdfs_lock_whole_index_area(src);
+ downgrade_write(&src->full_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to lock source's index area: err %d\n",
+ err);
+ goto unlock_src_node;
+ }
+
+ down_write(&dst->full_lock);
+ err = ssdfs_lock_whole_index_area(dst);
+ downgrade_write(&dst->full_lock);
+
+ if (unlikely(err)) {
+ ssdfs_unlock_whole_index_area(src);
+ SSDFS_ERR("fail to lock destination's index area: err %d\n",
+ err);
+ goto unlock_dst_node;
+ }
+
+ if (dst_start == 0 && dst_start != dst_index_count) {
+ down_write(&dst->header_lock);
+ err = ssdfs_shift_range_right2(dst, &dst->index_area,
+ index_size,
+ 0, dst_index_count,
+ count);
+ up_write(&dst->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to shift index range right: "
+ "dst_node %u, index_count %u, "
+ "shift %u, err %d\n",
+ dst->node_id, dst_index_count,
+ count, err);
+ goto unlock_index_area;
+ }
+ } else if (dst_start != dst_index_count) {
+ err = -ERANGE;
+ SSDFS_ERR("dst_start %u != dst_index_count %u\n",
+ dst_start, dst_index_count);
+ SSDFS_ERR("source (start_hash %llx, end_hash %llx), "
+ "destination (start_hash %llx, end_hash %llx)\n",
+ src_start_hash, src_end_hash,
+ dst_start_hash, dst_end_hash);
+ goto unlock_index_area;
+ }
+
+ while (processed < count) {
+ u16 range_len = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("i %u, j %u, processed %u, "
+ "count %u, range_len %u\n",
+ i, j, processed, count, range_len);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ err = ssdfs_copy_index_range_in_buffer(src, i,
+ count - processed,
+ src_offset,
+ index_size,
+ buf,
+ &range_len);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy index range in buffer: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+ err = ssdfs_save_index_range_in_node(dst, j, range_len,
+ dst_offset, index_size,
+ buf);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to save index range into node: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+ i += range_len;
+ j += range_len;
+ processed += range_len;
+ }
+
+ err = ssdfs_clear_index_range_in_node(src, src_start, count,
+ src_offset, index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to clear the source node's index range: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+ down_write(&dst->header_lock);
+ dst->index_area.index_count += processed;
+ err = __ssdfs_init_index_area_hash_range(dst,
+ dst->index_area.index_count,
+ &dst->index_area.start_hash,
+ &dst->index_area.end_hash);
+ up_write(&dst->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to set the destination node's index range: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+ if ((src_start + processed) < src_index_count) {
+ i = src_start + processed;
+ j = src_start;
+
+ rest_unmoved = src_index_count - (src_start + processed);
+ copied = 0;
+
+ while (copied < rest_unmoved) {
+ u16 range_len = 0;
+
+ err = ssdfs_copy_index_range_in_buffer(src, i,
+ rest_unmoved - copied,
+ src_offset,
+ index_size,
+ buf,
+ &range_len);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to copy index range in buffer: "
+ "err %d\n", err);
+ goto finish_source_correction;
+ }
+
+ err = ssdfs_save_index_range_in_node(src, j, range_len,
+ src_offset,
+ index_size,
+ buf);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to save index range into node: "
+ "err %d\n", err);
+ goto finish_source_correction;
+ }
+
+finish_source_correction:
+ if (unlikely(err))
+ goto unlock_index_area;
+
+ i += range_len;
+ j += range_len;
+ copied += range_len;
+ }
+
+ err = ssdfs_clear_index_range_in_node(src,
+ src_start + processed,
+ rest_unmoved,
+ src_offset, index_size);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to clear the src node's index range: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+ err = ssdfs_set_dirty_index_range(src, src_start,
+ rest_unmoved);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to set dirty index range: "
+ "start %u, len %u, err %d\n",
+ src_start, rest_unmoved, err);
+ goto unlock_index_area;
+ }
+ }
+
+ down_write(&src->header_lock);
+ src->index_area.index_count -= processed;
+ err = __ssdfs_init_index_area_hash_range(src,
+ src->index_area.index_count,
+ &src->index_area.start_hash,
+ &src->index_area.end_hash);
+ up_write(&src->header_lock);
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to set the source node's hash range: "
+ "err %d\n", err);
+ goto unlock_index_area;
+ }
+
+unlock_index_area:
+ ssdfs_unlock_whole_index_area(dst);
+ ssdfs_unlock_whole_index_area(src);
+
+unlock_dst_node:
+ up_read(&dst->full_lock);
+
+unlock_src_node:
+ up_read(&src->full_lock);
+
+finish_index_moving:
+ if (unlikely(err)) {
+ atomic_set(&src->state, SSDFS_BTREE_NODE_CORRUPTED);
+ atomic_set(&dst->state, SSDFS_BTREE_NODE_CORRUPTED);
+ } else {
+ ssdfs_set_node_update_cno(src);
+ set_ssdfs_btree_node_dirty(src);
+
+ ssdfs_set_node_update_cno(dst);
+ set_ssdfs_btree_node_dirty(dst);
+ }
+
+ ssdfs_btree_node_kfree(buf);
+ return err;
+}
+
+/*
+ * ssdfs_btree_node_move_index_range() - move index range
+ * @src: source node
+ * @src_start: starting index in the source node
+ * @dst: destination node
+ * @dst_start: starting index in the destination node
+ * @count: count of indexes in the range
+ *
+ * This method tries to move the index range from @src into @dst.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENOENT - index area is absent.
+ */
+int ssdfs_btree_node_move_index_range(struct ssdfs_btree_node *src,
+ u16 src_start,
+ struct ssdfs_btree_node *dst,
+ u16 dst_start, u16 count)
+{
+ int src_type, dst_type;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!src || !dst);
+ BUG_ON(!rwsem_is_locked(&src->tree->lock));
+
+ SSDFS_DBG("src_node %u, src_start %u, "
+ "dst_node %u, dst_start %u, "
+ "count %u\n",
+ src->node_id, src_start,
+ dst->node_id, dst_start, count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (atomic_read(&src->state)) {
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&src->state));
+ return -ERANGE;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(src)) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("src node %u hasn't index area\n",
+ src->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ENOENT;
+ }
+
+ switch (atomic_read(&dst->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&dst->state));
+ return -ERANGE;
+ }
+
+ if (!is_ssdfs_btree_node_index_area_exist(dst)) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("dst node %u hasn't index area\n",
+ dst->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ENOENT;
+ }
+
+ src_type = atomic_read(&src->type);
+ switch (src_type) {
+ case SSDFS_BTREE_ROOT_NODE:
+ case SSDFS_BTREE_INDEX_NODE:
+ case SSDFS_BTREE_HYBRID_NODE:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid src node type %#x\n",
+ src_type);
+ return -ERANGE;
+ }
+
+ dst_type = atomic_read(&dst->type);
+ switch (dst_type) {
+ case SSDFS_BTREE_HYBRID_NODE:
+ case SSDFS_BTREE_INDEX_NODE:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid dst node type %#x\n",
+ dst_type);
+ return -ERANGE;
+ }
+
+ if (src_type == SSDFS_BTREE_ROOT_NODE) {
+ err = ssdfs_move_root2common_node_index_range(src, src_start,
+ dst, dst_start,
+ count);
+ } else {
+ err = ssdfs_move_common2common_node_index_range(src, src_start,
+ dst, dst_start,
+ count);
+ }
+
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to move index range: err %d\n",
+ err);
+ }
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_node_check_result_for_search() - check search result for search
+ * @search: btree search object
+ */
+static
+int ssdfs_btree_node_check_result_for_search(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *node;
+ u64 update_cno;
+ u64 start_hash, end_hash;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search || !search->node.child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ node = search->node.child;
+
+ down_read(&node->header_lock);
+ update_cno = node->update_cno;
+ start_hash = node->items_area.start_hash;
+ end_hash = node->items_area.end_hash;
+ up_read(&node->header_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search (state %#x, search_cno %llu, "
+ "start_hash %llx, end_hash %llx), "
+ "node (update_cno %llu, "
+ "start_hash %llx, end_hash %llx)\n",
+ search->result.state,
+ search->result.search_cno,
+ search->request.start.hash,
+ search->request.end.hash,
+ update_cno, start_hash, end_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_VALID_ITEM:
+ if (search->result.search_cno < update_cno) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_OBSOLETE_RESULT;
+ return -EAGAIN;
+ }
+
+ if (search->request.start.hash < start_hash &&
+ search->request.start.hash > end_hash) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_OBSOLETE_RESULT;
+ return -EAGAIN;
+ }
+
+ return 0;
+
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+ if (search->result.search_cno < update_cno) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_OBSOLETE_RESULT;
+ return -EAGAIN;
+ }
+
+ return 0;
+
+ case SSDFS_BTREE_SEARCH_UNKNOWN_RESULT:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_SEARCH_FAILURE:
+ case SSDFS_BTREE_SEARCH_EMPTY_RESULT:
+ case SSDFS_BTREE_SEARCH_OBSOLETE_RESULT:
+ search->result.state = SSDFS_BTREE_SEARCH_UNKNOWN_RESULT;
+ break;
+
+ case SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE:
+ SSDFS_DBG("search result requests to add a node already\n");
+ break;
+
+ case SSDFS_BTREE_SEARCH_PLEASE_DELETE_NODE:
+ SSDFS_WARN("unexpected search result state\n");
+ search->result.state = SSDFS_BTREE_SEARCH_UNKNOWN_RESULT;
+ break;
+
+ default:
+ SSDFS_WARN("invalid search result state\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search->result.state %#x\n",
+ search->result.state);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_check_hash_range() - check necessity to do search
+ * @node: pointer on node object
+ * @items_count: items count in the node
+ * @items_capacity: node's capacity for items
+ * @start_hash: items' area starting hash
+ * @end_hash: items' area ending hash
+ * @search: pointer on search request object
+ *
+ * This method tries to check the necessity to do
+ * the real search in the node..
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE - internal error.
+ * %-ENODATA - requested range is out of the node.
+ * %-ENOMEM - unable to allocate memory.
+ */
+int ssdfs_btree_node_check_hash_range(struct ssdfs_btree_node *node,
+ u16 items_count,
+ u16 items_capacity,
+ u64 start_hash,
+ u64 end_hash,
+ struct ssdfs_btree_search *search)
+{
+ u16 vacant_items;
+ bool have_enough_space;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node || !search);
+
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "search (start_hash %llx, end_hash %llx), "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ start_hash, end_hash,
+ search->request.start.hash, search->request.end.hash,
+ atomic_read(&node->state), node->node_id,
+ atomic_read(&node->height), search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ vacant_items = items_capacity - items_count;
+ have_enough_space = search->request.count <= vacant_items;
+
+ switch (RANGE_WITHOUT_INTERSECTION(search->request.start.hash,
+ search->request.end.hash,
+ start_hash, end_hash)) {
+ case 0:
+ /* ranges have intersection */
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("ranges have intersection\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+ break;
+
+ case -1: /* range1 < range2 */
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("range1 < range2\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+ if (have_enough_space) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND;
+ } else {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ }
+
+ search->result.err = -ENODATA;
+ search->result.start_index = 0;
+ search->result.count = search->request.count;
+ search->result.search_cno =
+ ssdfs_current_cno(node->tree->fsi->sb);
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_RANGE:
+ case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+ /* do nothing */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(search->result.buf);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ search->result.buf_state =
+ SSDFS_BTREE_SEARCH_UNKNOWN_BUFFER_STATE;
+ search->result.buf = NULL;
+ search->result.buf_size = 0;
+ search->result.items_in_buffer = 0;
+ break;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search->result.start_index %u, "
+ "search->result.state %#x, "
+ "search->result.err %d\n",
+ search->result.start_index,
+ search->result.state,
+ search->result.err);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -ENODATA;
+
+ case 1: /* range1 > range2 */
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("range1 > range2\n");
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (have_enough_space) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_OUT_OF_RANGE;
+ } else {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_PLEASE_ADD_NODE;
+ }
+
+ search->result.err = -ENODATA;
+ search->result.start_index = items_count;
+ search->result.count = search->request.count;
+ search->result.search_cno =
+ ssdfs_current_cno(node->tree->fsi->sb);
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_RANGE:
+ case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+ /* do nothing */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(search->result.buf);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ search->result.buf_state =
+ SSDFS_BTREE_SEARCH_UNKNOWN_BUFFER_STATE;
+ search->result.buf = NULL;
+ search->result.buf_size = 0;
+ search->result.items_in_buffer = 0;
+ break;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search->result.start_index %u, "
+ "search->result.state %#x, "
+ "search->result.err %d\n",
+ search->result.start_index,
+ search->result.state,
+ search->result.err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return -ENODATA;
+
+ default:
+ BUG();
+ }
+
+ if (!RANGE_HAS_PARTIAL_INTERSECTION(search->request.start.hash,
+ search->request.end.hash,
+ start_hash, end_hash)) {
+ SSDFS_ERR("invalid request: "
+ "request (start_hash %llx, end_hash %llx), "
+ "node (start_hash %llx, end_hash %llx)\n",
+ search->request.start.hash,
+ search->request.end.hash,
+ start_hash, end_hash);
+ return -ERANGE;
+ }
+
+ if (items_count == 0) {
+ search->result.state =
+ SSDFS_BTREE_SEARCH_OUT_OF_RANGE;
+
+ search->result.err = -ENODATA;
+ search->result.start_index = 0;
+ search->result.count = search->request.count;
+ search->result.search_cno =
+ ssdfs_current_cno(node->tree->fsi->sb);
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_RANGE:
+ case SSDFS_BTREE_SEARCH_CHANGE_ITEM:
+ /* do nothing */
+ break;
+
+ default:
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(search->result.buf);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ search->result.buf_state =
+ SSDFS_BTREE_SEARCH_UNKNOWN_BUFFER_STATE;
+ search->result.buf = NULL;
+ search->result.buf_size = 0;
+ search->result.items_in_buffer = 0;
+ break;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("search->result.start_index %u, "
+ "search->result.state %#x, "
+ "search->result.err %d\n",
+ search->result.start_index,
+ search->result.state,
+ search->result.err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ return -ENODATA;
+ }
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_find_item() - find the item in the node
+ * @search: btree search object
+ *
+ * This method tries to find an item in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENODATA - node doesn't contain item for the requested hash.
+ * %-ENOENT - node hasn't the items area.
+ * %-ENOSPC - node hasn't free space.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ * %-EOPNOTSUPP - specialized searching method doesn't been implemented
+ */
+int ssdfs_btree_node_find_item(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *node;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_search(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (!node->node_ops || !node->node_ops->find_item) {
+ SSDFS_WARN("unable to search in the node\n");
+ return -EOPNOTSUPP;
+ }
+
+ down_read(&node->full_lock);
+ err = node->node_ops->find_item(node, search);
+ up_read(&node->full_lock);
+
+ if (err == -ENODATA) {
+ u16 items_count;
+ u16 items_capacity;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u "
+ "hasn't item for request "
+ "(start_hash %llx, end_hash %llx)\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ALLOCATE_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ items_capacity = node->items_area.items_capacity;
+ up_read(&node->header_lock);
+
+ if (items_count >= items_capacity) {
+ err = -ENOSPC;
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node hasn't free space: "
+ "items_count %u, "
+ "items_capacity %u\n",
+ items_count,
+ items_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+ search->result.err = -ENODATA;
+ }
+ break;
+
+ default:
+ search->result.err = err;
+ break;
+ }
+ } else if (err == -EAGAIN) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u "
+ "hasn't all items for request "
+ "(start_hash %llx, end_hash %llx)\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ } else if (err == -ENOENT) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u hasn't items area\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find: "
+ "node %u, "
+ "request (start_hash %llx, end_hash %llx), "
+ "err %d\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ }
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_node_find_range() - find the range in the node
+ * @search: btree search object
+ *
+ * This method tries to find a range of items in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENODATA - node doesn't contain items for the requested range.
+ * %-ENOENT - node hasn't the items area.
+ * %-ENOSPC - node hasn't free space.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ * %-EOPNOTSUPP - specialized searching method doesn't been implemented
+ */
+int ssdfs_btree_node_find_range(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_btree_node *node;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_search(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (!node->node_ops || !node->node_ops->find_range) {
+ SSDFS_WARN("unable to search in the node\n");
+ return -EOPNOTSUPP;
+ }
+
+ down_read(&node->full_lock);
+ err = node->node_ops->find_range(node, search);
+ up_read(&node->full_lock);
+
+ if (err == -ENODATA) {
+ u16 items_count;
+ u16 items_capacity;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u "
+ "hasn't item for request "
+ "(start_hash %llx, end_hash %llx)\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->request.type) {
+ case SSDFS_BTREE_SEARCH_ALLOCATE_ITEM:
+ case SSDFS_BTREE_SEARCH_ADD_ITEM:
+ down_read(&node->header_lock);
+ items_count = node->items_area.items_count;
+ items_capacity = node->items_area.items_capacity;
+ up_read(&node->header_lock);
+
+ if (items_count >= items_capacity) {
+ err = -ENOSPC;
+ search->result.err = -ENODATA;
+ }
+ break;
+
+ default:
+ search->result.err = err;
+ break;
+ }
+ } else if (err == -EAGAIN) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u "
+ "hasn't all items for request "
+ "(start_hash %llx, end_hash %llx)\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+ } else if (err == -ENOENT) {
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u hasn't items area\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ } else if (unlikely(err)) {
+ SSDFS_ERR("fail to find: "
+ "node %u, "
+ "request (start_hash %llx, end_hash %llx), "
+ "err %d\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ }
+
+ return err;
+}
+
+/*
+ * ssdfs_btree_node_check_result_for_alloc() - check search result for alloc
+ * @search: btree search object
+ */
+static inline
+int ssdfs_btree_node_check_result_for_alloc(struct ssdfs_btree_search *search)
+{
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_VALID_ITEM:
+ return -EEXIST;
+
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_WARN("invalid search result state %#x\n",
+ search->result.state);
+ return -ERANGE;
+ }
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_allocate_item() - allocate the item in the node
+ * @search: btree search object
+ *
+ * This method tries to allocate an item in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EEXIST - item is used already.
+ * %-ENOSPC - item is out of node.
+ * %-ENOENT - node hasn't the items area.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ */
+int ssdfs_btree_node_allocate_item(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_fs_info *fsi;
+ struct ssdfs_btree_node *node;
+ u16 flags;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+ BUG_ON(search->request.start.hash > search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#else
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree || !node->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = node->tree->fsi;
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_alloc(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (node->node_ops && node->node_ops->allocate_item) {
+ err = node->node_ops->allocate_item(node, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to allocate item: err %d\n",
+ err);
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.search_cno = U64_MAX;
+ search->result.start_index = U16_MAX;
+ search->result.count = U16_MAX;
+ return err;
+ }
+ } else
+ return -EOPNOTSUPP;
+
+ spin_lock(&node->descriptor_lock);
+ search->result.search_cno = ssdfs_current_cno(fsi->sb);
+ node->update_cno = search->result.search_cno;
+ flags = le16_to_cpu(node->node_index.flags);
+ flags &= ~SSDFS_BTREE_INDEX_SHOW_EMPTY_NODE;
+ node->node_index.flags = cpu_to_le16(flags);
+ spin_unlock(&node->descriptor_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node->update_cno %llu\n",
+ search->result.search_cno);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ set_ssdfs_btree_node_dirty(node);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_allocate_range() - allocate the range in the node
+ * @search: btree search object
+ *
+ * This method tries to allocate a range of items in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EEXIST - range of items is used already.
+ * %-ENOSPC - range is out of node.
+ * %-ENOENT - node hasn't the items area.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ */
+int ssdfs_btree_node_allocate_range(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_fs_info *fsi;
+ struct ssdfs_btree_node *node;
+ u16 flags;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+ BUG_ON(search->request.start.hash > search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#else
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree || !node->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = node->tree->fsi;
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_alloc(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (node->node_ops && node->node_ops->allocate_range) {
+ err = node->node_ops->allocate_range(node, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to allocate item: err %d\n",
+ err);
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.search_cno = U64_MAX;
+ search->result.start_index = U16_MAX;
+ search->result.count = U16_MAX;
+ return err;
+ }
+ } else
+ return -EOPNOTSUPP;
+
+ spin_lock(&node->descriptor_lock);
+ search->result.search_cno = ssdfs_current_cno(fsi->sb);
+ node->update_cno = search->result.search_cno;
+ flags = le16_to_cpu(node->node_index.flags);
+ flags &= ~SSDFS_BTREE_INDEX_SHOW_EMPTY_NODE;
+ node->node_index.flags = cpu_to_le16(flags);
+ spin_unlock(&node->descriptor_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node->update_cno %llu\n",
+ search->result.search_cno);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ set_ssdfs_btree_node_dirty(node);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_check_result_for_insert() - check search result for insert
+ * @search: btree search object
+ */
+static inline
+int ssdfs_btree_node_check_result_for_insert(struct ssdfs_btree_search *search)
+{
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ switch (search->result.state) {
+ case SSDFS_BTREE_SEARCH_VALID_ITEM:
+ return -EEXIST;
+
+ case SSDFS_BTREE_SEARCH_POSSIBLE_PLACE_FOUND:
+ case SSDFS_BTREE_SEARCH_OUT_OF_RANGE:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_WARN("invalid search result state\n");
+ return -ERANGE;
+ }
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_insert_item() - insert the item in the node
+ * @search: btree search object
+ *
+ * This method tries to insert an item in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-EEXIST - item exists.
+ * %-ENOSPC - node hasn't free space.
+ * %-EFBIG - some items were pushed out from the node.
+ * %-ENOENT - node hasn't the items area.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ * %-EOPNOTSUPP - specialized insert method doesn't been implemented
+ */
+int ssdfs_btree_node_insert_item(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_fs_info *fsi;
+ struct ssdfs_btree_node *node;
+ u16 flags;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+ BUG_ON(search->request.start.hash > search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#else
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree || !node->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = node->tree->fsi;
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("free_space %u\n", node->items_area.free_space);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_insert(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (!node->node_ops || !node->node_ops->insert_item) {
+ SSDFS_WARN("unable to insert item\n");
+ return -EOPNOTSUPP;
+ }
+
+ err = node->node_ops->insert_item(node, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert: "
+ "node %u, "
+ "request (start_hash %llx, end_hash %llx), "
+ "err %d\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ return err;
+ }
+
+ spin_lock(&node->descriptor_lock);
+ search->result.search_cno = ssdfs_current_cno(fsi->sb);
+ node->update_cno = search->result.search_cno;
+ flags = le16_to_cpu(node->node_index.flags);
+ flags &= ~SSDFS_BTREE_INDEX_SHOW_EMPTY_NODE;
+ node->node_index.flags = cpu_to_le16(flags);
+ spin_unlock(&node->descriptor_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node->update_cno %llu\n",
+ search->result.search_cno);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ set_ssdfs_btree_node_dirty(node);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ return 0;
+}
+
+/*
+ * ssdfs_btree_node_insert_range() - insert the range in the node
+ * @search: btree search object
+ *
+ * This method tries to insert a range of items in the node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL - invalid input.
+ * %-ERANGE - internal error.
+ * %-ENOSPC - node hasn't free space.
+ * %-EFBIG - some items were pushed out from the node.
+ * %-ENOENT - node hasn't the items area.
+ * %-EACCES - node is under initialization yet.
+ * %-EAGAIN - search object contains obsolete result.
+ */
+int ssdfs_btree_node_insert_range(struct ssdfs_btree_search *search)
+{
+ struct ssdfs_fs_info *fsi;
+ struct ssdfs_btree_node *node;
+ u16 flags;
+ int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!search);
+ BUG_ON(search->request.start.hash > search->request.end.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#else
+ SSDFS_DBG("type %#x, flags %#x, "
+ "start_hash %llx, end_hash %llx, "
+ "state %#x, node_id %u, height %u, "
+ "parent %p, child %p\n",
+ search->request.type, search->request.flags,
+ search->request.start.hash, search->request.end.hash,
+ search->node.state, search->node.id,
+ search->node.height, search->node.parent,
+ search->node.child);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ node = search->node.child;
+ if (!node) {
+ SSDFS_WARN("child node is NULL\n");
+ return -ERANGE;
+ }
+
+#ifdef CONFIG_SSDFS_DEBUG
+ BUG_ON(!node->tree || !node->tree->fsi);
+ BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ fsi = node->tree->fsi;
+
+ switch (atomic_read(&node->state)) {
+ case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node %u is under initialization\n",
+ node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+ return -EACCES;
+
+ case SSDFS_BTREE_NODE_INITIALIZED:
+ case SSDFS_BTREE_NODE_DIRTY:
+ /* expected state */
+ break;
+
+ default:
+ SSDFS_ERR("invalid node state %#x\n",
+ atomic_read(&node->state));
+ return -ERANGE;
+ }
+
+ if (!is_btree_search_node_desc_consistent(search)) {
+ SSDFS_WARN("node descriptor is inconsistent\n");
+ return -ERANGE;
+ }
+
+ err = ssdfs_btree_node_check_result_for_insert(search);
+ if (err)
+ return err;
+
+ switch (atomic_read(&node->items_area.state)) {
+ case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+ /* expected state */
+ break;
+
+ case SSDFS_BTREE_NODE_AREA_ABSENT:
+ SSDFS_WARN("items area is absent: node_id %u\n",
+ search->node.id);
+ return -ENOENT;
+
+ default:
+ SSDFS_WARN("invalid items area state: node_id %u\n",
+ search->node.id);
+ return -ERANGE;
+ }
+
+ if (!node->node_ops || !node->node_ops->insert_range) {
+ SSDFS_WARN("unable to insert range\n");
+ return -EOPNOTSUPP;
+ }
+
+ err = node->node_ops->insert_range(node, search);
+ if (unlikely(err)) {
+ SSDFS_ERR("fail to insert: "
+ "node %u, "
+ "request (start_hash %llx, end_hash %llx), "
+ "err %d\n",
+ node->node_id,
+ search->request.start.hash,
+ search->request.end.hash,
+ err);
+
+ search->result.state = SSDFS_BTREE_SEARCH_FAILURE;
+ search->result.err = err;
+ return err;
+ }
+
+ spin_lock(&node->descriptor_lock);
+ search->result.search_cno = ssdfs_current_cno(fsi->sb);
+ node->update_cno = search->result.search_cno;
+ flags = le16_to_cpu(node->node_index.flags);
+ flags &= ~SSDFS_BTREE_INDEX_SHOW_EMPTY_NODE;
+ node->node_index.flags = cpu_to_le16(flags);
+ spin_unlock(&node->descriptor_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+ SSDFS_DBG("node->update_cno %llu\n",
+ search->result.search_cno);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+ set_ssdfs_btree_node_dirty(node);
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+ SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+ return 0;
+}
B-tree node implements search, allocation, and insert item or range of items in the node: (1) find_item - find item in b-tree node (2) find_range - find range of items in b-tree node (3) allocate_item - allocate item in b-tree node (4) allocate_range - allocate range of items in b-tree node (5) insert_item - insert/add item into b-tree node (6) insert_range - insert/add range of items into b-tree node 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_node.c | 3135 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3135 insertions(+)