Skip to contentSkip to conversation

btrfs: implement delayed dir index insertion and deletion

RFC PATCH In review Miao Xie 2 participants 3 messages Dec 1, 2010 – Dec 6, 2010 Btrfs file system

lore
Share & tools
lore

Miao Xie

author
#0 lore raw

RFC PATCH 4/4 btrfs: implement delayed dir index insertion and deletion

Compare with Ext3/4, the performance of file creation and deletion on btrfs is very poor. the reason is that btrfs must do a lot of b+ tree insertions, such as inode item, directory name item, directory name index and so on.

If we can do some delayed b+ tree insertion or deletion, we can improve the performance, so we made this patch which implemented delayed directory name index insertion and deletion.

Implementation:
- Every transaction has two rb-tree, one is used to manage the directory name index which is going to be inserted into b+ tree, and the other is used to manage the directory name index which is going to be deleted from b+ tree.
- When we want to insert a directory name index into b+ tree, we just add the information into the inserting rb-tree.
And when the number of directory name index touches the upper limit (The max number of the directory name index that can be stored in a leaf), we start inserting manipulation and insert those directory name index into the b+ tree.
- When we want to delete a directory name index from the b+ tree, we search it in the inserting rb-tree at first. If we look it up, just drop it. If not, add the key of it into the deleting rb-tree.
Similar to the inserting rb-tree, the number of directory name index touches the upper limit, we start deleting manipulation and delete those directory name index from the b+ tree.
- If we want to commit transaction, we do inserting/deleting manipulation and insert/delete all the directory name indexs which are in the rb-tree into/from the b+ tree.
- when we want to read directory entry, we will do deleting manipulation and delete all the directory name indexs of the file/directory it contains from the b+ tree. And then read directory entries in the b+ tree. At the end read directory entries which is in the inserting rb-tree.

I did a quick test by the benchmark tool[1] and found we can improve the performance of file creation by ~9%, and file deletion by ~13%.

Before applying this patch:
Create files:

	Total files: 50000
	Total time: 1.188547
	Average time: 0.000024
Delete files:
	Total files: 50000
	Total time: 1.662012
	Average time: 0.000033

After applying this patch:
Create files:

	Total files: 50000
	Total time: 1.083526
	Average time: 0.000022
Delete files:
	Total files: 50000
	Total time: 1.439360
	Average time: 0.000029

[1] http://marc.info/?l=linux-btrfs&m=128212635122920&q=p3

---
 fs/btrfs/Makefile            |    2 +-
 fs/btrfs/btrfs_inode.h       |    2 +
 fs/btrfs/ctree.c             |   13 +-
 fs/btrfs/ctree.h             |   15 +-
 fs/btrfs/delayed-dir-index.c |  790 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/delayed-dir-index.h |   92 +++++
 fs/btrfs/dir-item.c          |   24 +-
 fs/btrfs/extent-tree.c       |   21 ++
 fs/btrfs/inode.c             |   80 +++--
 fs/btrfs/transaction.c       |    9 +
 fs/btrfs/transaction.h       |    2 +
 11 files changed, 995 insertions(+), 55 deletions(-)
 create mode 100644 fs/btrfs/delayed-dir-index.c
 create mode 100644 fs/btrfs/delayed-dir-index.h
fs/btrfs/Makefile +1 -1
index a35eb36..1f7696a 100644
@@ -7,4 +7,4 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
 	   extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
 	   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
 	   export.o tree-log.o acl.o free-space-cache.o zlib.o \
-	   compression.o delayed-ref.o relocation.o
+	   compression.o delayed-ref.o relocation.o delayed-dir-index.o
fs/btrfs/btrfs_inode.h +2 -0
index 6ad63f1..3d03a17 100644
@@ -162,6 +162,8 @@ struct btrfs_inode {
 	struct inode vfs_inode;
 };
 
+extern unsigned char btrfs_filetype_table[];
+
 static inline struct btrfs_inode *BTRFS_I(struct inode *inode)
 {
 	return container_of(inode, struct btrfs_inode, vfs_inode);
fs/btrfs/ctree.c +4 -9
index 9ac1715..08f4339 100644
@@ -38,10 +38,6 @@ static int balance_node_right(struct btrfs_trans_handle *trans,
 			      struct extent_buffer *src_buf);
 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		   struct btrfs_path *path, int level, int slot);
-static int setup_items_for_insert(struct btrfs_trans_handle *trans,
-			struct btrfs_root *root, struct btrfs_path *path,
-			struct btrfs_key *cpu_key, u32 *data_size,
-			u32 total_data, u32 total_size, int nr);
 
 
 struct btrfs_path *btrfs_alloc_path(void)
@@ -3680,11 +3676,10 @@ out:
  * to save stack depth by doing the bulk of the work in a function
  * that doesn't call btrfs_search_slot
  */
-static noinline_for_stack int
-setup_items_for_insert(struct btrfs_trans_handle *trans,
-		      struct btrfs_root *root, struct btrfs_path *path,
-		      struct btrfs_key *cpu_key, u32 *data_size,
-		      u32 total_data, u32 total_size, int nr)
+int setup_items_for_insert(struct btrfs_trans_handle *trans,
+			   struct btrfs_root *root, struct btrfs_path *path,
+			   struct btrfs_key *cpu_key, u32 *data_size,
+			   u32 total_data, u32 total_size, int nr)
 {
 	struct btrfs_item *item;
 	int i;
fs/btrfs/ctree.h +14 -1
index 5c44cf4..84eab48 100644
@@ -870,7 +870,10 @@ struct btrfs_fs_info {
 	/* logical->physical extent mapping */
 	struct btrfs_mapping_tree mapping_tree;
 
-	/* block reservation for extent, checksum and root tree */
+	/*
+	 * block reservation for extent, checksum, root tree and
+	 * delayed dir index item
+	 */
 	struct btrfs_block_rsv global_block_rsv;
 	/* block reservation for delay allocation */
 	struct btrfs_block_rsv delalloc_block_rsv;
@@ -2163,6 +2166,12 @@ int btrfs_delalloc_reserve_metadata(struct inode *inode, u64 num_bytes);
 void btrfs_delalloc_release_metadata(struct inode *inode, u64 num_bytes);
 int btrfs_delalloc_reserve_space(struct inode *inode, u64 num_bytes);
 void btrfs_delalloc_release_space(struct inode *inode, u64 num_bytes);
+int btrfs_delayed_dir_index_reserve_metadata(struct btrfs_trans_handle *trans,
+					     struct btrfs_root *root,
+					     int num_items);
+void btrfs_delayed_dir_index_release_metadata(struct btrfs_trans_handle *trans,
+					      struct btrfs_root *root,
+					      int num_items);
 void btrfs_init_block_rsv(struct btrfs_block_rsv *rsv);
 struct btrfs_block_rsv *btrfs_alloc_block_rsv(struct btrfs_root *root);
 void btrfs_free_block_rsv(struct btrfs_root *root,
@@ -2254,6 +2263,10 @@ static inline int btrfs_del_item(struct btrfs_trans_handle *trans,
 	return btrfs_del_items(trans, root, path, path->slots[0], 1);
 }
 
+int setup_items_for_insert(struct btrfs_trans_handle *trans,
+			   struct btrfs_root *root, struct btrfs_path *path,
+			   struct btrfs_key *cpu_key, u32 *data_size,
+			   u32 total_data, u32 total_size, int nr);
 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
 		      *root, struct btrfs_key *key, void *data, u32 data_size);
 int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
fs/btrfs/delayed-dir-index.c new file +790 -0

790 lines not on this page · raw message

fs/btrfs/delayed-dir-index.h new file +92 -0

92 lines not on this page · raw message

fs/btrfs/dir-item.c +4 -20
index d2d23b6..588e1fb 100644
@@ -182,6 +182,8 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
 	path = btrfs_alloc_path();
 	path->leave_spinning = 1;
 
+	btrfs_cpu_key_to_disk(&disk_key, location);
+
 	data_size = sizeof(*dir_item) + name_len;
 	dir_item = insert_with_overflow(trans, root, path, &key, data_size,
 					name, name_len);
@@ -193,7 +195,6 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
 	}
 
 	leaf = path->nodes[0];
-	btrfs_cpu_key_to_disk(&disk_key, location);
 	btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
 	btrfs_set_dir_type(leaf, dir_item, type);
 	btrfs_set_dir_data_len(leaf, dir_item, 0);
@@ -212,25 +213,8 @@ second_insert:
 	}
 	btrfs_release_path(root, path);
 
-	dir_item = kmalloc(sizeof(*dir_item) + name_len, GFP_KERNEL | GFP_NOFS);
-	if (!dir_item) {
-		ret2 = -ENOMEM;
-		goto out;
-	}
-
-	btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY);
-	key.offset = index;
-
-	btrfs_cpu_key_to_disk(&disk_key, location);
-	dir_item->location = disk_key;
-	dir_item->transid = cpu_to_le64(trans->transid);
-	dir_item->data_len = 0;
-	dir_item->name_len = cpu_to_le16(name_len);
-	dir_item->type = type;
-	memcpy((char *)(dir_item + 1), name, name_len);
-	ret2 = btrfs_insert_dir_index_item(trans, root, &key, path, dir_item,
-					   sizeof(*dir_item) + name_len);
-	kfree(dir_item);
+	ret2 = btrfs_insert_delayed_dir_index(trans, root, name, name_len,
+					      dir, &disk_key, type, index);
 out:
 	btrfs_free_path(path);
 	if (ret)
fs/btrfs/extent-tree.c +21 -0
index ddaf634..70c4c34 100644
@@ -4043,6 +4043,27 @@ void btrfs_delalloc_release_space(struct inode *inode, u64 num_bytes)
 	btrfs_free_reserved_data_space(inode, num_bytes);
 }
 
+int btrfs_delayed_dir_index_reserve_metadata(struct btrfs_trans_handle *trans,
+					     struct btrfs_root *root,
+					     int num_items)
+{
+	struct btrfs_block_rsv *src_rsv = get_block_rsv(trans, root);
+	struct btrfs_block_rsv *dst_rsv = &root->fs_info->global_block_rsv;
+	u64 num_bytes = calc_trans_metadata_size(root, num_items);
+
+	return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
+}
+
+void btrfs_delayed_dir_index_release_metadata(struct btrfs_trans_handle *trans,
+					      struct btrfs_root *root,
+					      int num_items)
+{
+	u64 num_bytes = calc_trans_metadata_size(root, num_items);
+
+	btrfs_block_rsv_release(root, &root->fs_info->global_block_rsv,
+				num_bytes);
+}
+
 static int update_block_group(struct btrfs_trans_handle *trans,
 			      struct btrfs_root *root,
 			      u64 bytenr, u64 num_bytes, int alloc)
fs/btrfs/inode.c +56 -24

144 lines not on this page · raw message

fs/btrfs/transaction.c +9 -0
index f50e931..9d16181 100644
@@ -78,6 +78,8 @@ static noinline int join_transaction(struct btrfs_root *root)
 		cur_trans->delayed_refs.run_delayed_start = 0;
 		spin_lock_init(&cur_trans->delayed_refs.lock);
 
+		btrfs_init_delayed_dir_index_root(
+					&cur_trans->delayed_dir_index);
 		INIT_LIST_HEAD(&cur_trans->pending_snapshots);
 		list_add_tail(&cur_trans->list, &root->fs_info->trans_list);
 		extent_io_tree_init(&cur_trans->dirty_pages,
@@ -1286,9 +1288,16 @@ int btrfs_commit_transaction(struct btrfs_trans_handle *trans,
 	} while (cur_trans->num_writers > 1 ||
 		 (should_grow && cur_trans->num_joined != joined));
 
+	btrfs_run_delayed_dir_index(trans, root, NULL,
+				    BTRFS_DELAYED_INS_AND_DEL_ITEM, 1);
+
 	ret = create_pending_snapshots(trans, root->fs_info);
 	BUG_ON(ret);
 
+	ret = btrfs_run_delayed_dir_index(trans, root, NULL,
+					  BTRFS_DELAYED_INS_AND_DEL_ITEM, 1);
+	BUG_ON(ret);
+
 	ret = btrfs_run_delayed_refs(trans, root, (unsigned long)-1);
 	BUG_ON(ret);
 
fs/btrfs/transaction.h +2 -0
index f104b57..b8ddfe3 100644
@@ -20,6 +20,7 @@
 #define __BTRFS_TRANSACTION__
 #include "btrfs_inode.h"
 #include "delayed-ref.h"
+#include "delayed-dir-index.h"
 
 struct btrfs_transaction {
 	u64 transid;
@@ -41,6 +42,7 @@ struct btrfs_transaction {
 	wait_queue_head_t commit_wait;
 	struct list_head pending_snapshots;
 	struct btrfs_delayed_ref_root delayed_refs;
+	struct btrfs_delayed_dir_index_root delayed_dir_index;
 };
 
 struct btrfs_trans_handle {
Signature · 1 line
1.7.0.1
#1 lore raw

Excerpts from Miao Xie's message of 2010-12-01 03:09:35 -0500:

Quoted 7 lines

Compare with Ext3/4, the performance of file creation and deletion on btrfs is very poor. the reason is that btrfs must do a lot of b+ tree insertions, such as inode item, directory name item, directory name index and so on.

If we can do some delayed b+ tree insertion or deletion, we can improve the performance, so we made this patch which implemented delayed directory name index insertion and deletion.

Many thanks for working on this. It's a difficult problem and these patches look very clean.

I think you can get more improvement if you also do this delayed scheme for the inode items themselves.

The hard part of these delayed implementations is always the throttling,

+ if (delayed_root->count >= root->leafsize / sizeof(*dir_item))
+ btrfs_run_delayed_dir_index(trans, root, NULL,
+ BTRFS_DELAYED_INSERT_ITEM, 0);
+

Have you experimented with other values here?

I need to take a hard look at the locking and do some benchmarking on larger machines. I'm a little worried about increased lock contention, but I think we can get around it by breaking up the rbtrees a little later on if we need to.

-chris

author
#2 lore raw
Quoted 9 lines · Chris Mason

Excerpts from Miao Xie's message of 2010-12-01 03:09:35 -0500:

Quoted 7 lines

Compare with Ext3/4, the performance of file creation and deletion on btrfs is very poor. the reason is that btrfs must do a lot of b+ tree insertions, such as inode item, directory name item, directory name index and so on.

If we can do some delayed b+ tree insertion or deletion, we can improve the performance, so we made this patch which implemented delayed directory name index insertion and deletion.

Quoted 5 lines

Many thanks for working on this. It's a difficult problem and these patches look very clean.

I think you can get more improvement if you also do this delayed scheme for the inode items themselves.

I think I can try to do it later.

Quoted 8 lines

The hard part of these delayed implementations is always the throttling,

fs/btrfs/delayed-dir-index.c new file +4 -0
+    if (delayed_root->count>= root->leafsize / sizeof(*dir_item))
+        btrfs_run_delayed_dir_index(trans, root, NULL,
+                        BTRFS_DELAYED_INSERT_ITEM, 0);
+

Have you experimented with other values here?

Yes, I have tried to set it to other values(such as 40, 100), or remove this check. Though the performance becomes better as the number increases, the reserved space that fs needs become larger, if the fs space is not enough, btrfs will call shrink_delalloc(), the performance drops rapidly.

Maybe we can use a background work thread to do b+ tree insertion and deletion, and implement it just like dirty page write back mechanism.

Quoted 4 lines

I need to take a hard look at the locking and do some benchmarking on larger machines. I'm a little worried about increased lock contention, but I think we can get around it by breaking up the rbtrees a little later on if we need to.

Yes, we can create rb-tree for every directory.

Thanks
Miao