btrfs: implement delayed dir index insertion and deletion
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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
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