btrfs: implement delayed inode items operation

Changelog V4 -> V5:
- Fix the race on adding the delayed node to the inode, which is spotted by Chris Mason.
- Merge Chris Mason's incremental patch into this patch.
- Fix deadlock between readdir() and memory fault, which is reported by Itaru Kitayama.

Changelog V3 -> V4:
- Fix nested lock, which is reported by Itaru Kitayama, by updating space cache inode in time.

Changelog V2 -> V3:
- Fix the race between the delayed worker and the task which does delayed items balance, which is reported by Tsutomu Itoh.
- Modify the patch address David Sterba's comment.
- Fix the bug of the cpu recursion spinlock, reported by Chris Mason

Changelog V1 -> V2:
- break up the global rb-tree, use a list to manage the delayed nodes, which is created for every directory and file, and used to manage the delayed directory name index items and the delayed inode item.
- introduce a worker to deal with the delayed nodes.

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/deletion and delayed inode update.

Implementation:
- introduce a delayed root object into the filesystem, that use two lists to manage the delayed nodes which are created for every file/directory. One is used to manage all the delayed nodes that have delayed items. And the other is used to manage the delayed nodes which is waiting to be dealt with by the work thread.
- Every delayed node 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.
- introduce a worker to deal with the delayed operation. This worker is used to deal with the works of the delayed directory name index items insertion and deletion and the delayed inode update.
When the delayed items is beyond the lower limit, we create works for some delayed nodes and insert them into the work queue of the worker, and then go back.
When the delayed items is beyond the upper bound, we create works for all the delayed nodes that haven't been dealt with, and insert them into the work queue of the worker, and then wait for that the untreated items is below some threshold value.
- When we want to insert a directory name index into b+ tree, we just add the information into the delayed inserting rb-tree.
And then we check the number of the delayed items and do delayed items balance. (The balance policy is above.)
- 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 delayed deleting rb-tree.
Similar to the delayed inserting rb-tree, we also check the number of the delayed items and do delayed items balance.
(The same to inserting manipulation)
- When we want to update the metadata of some inode, we cached the data of the inode into the delayed node. the worker will flush it into the b+ tree after dealing with the delayed insertion and deletion.
- We will move the delayed node to the tail of the list after we access the delayed node, By this way, we can cache more delayed items and merge more inode updates.
- If we want to commit transaction, we will deal with all the delayed node.
- the delayed node will be freed when we free the btrfs inode.
- Before we log the inode items, we commit all the directory name index items and the delayed inode update.

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

Before applying this patch:
Create files:

	Total files: 50000
	Total time: 1.096108
	Average time: 0.000022
Delete files:
	Total files: 50000
	Total time: 1.510403
	Average time: 0.000030

After applying this patch:
Create files:

	Total files: 50000
	Total time: 0.932899
	Average time: 0.000019
Delete files:
	Total files: 50000
	Total time: 1.215732
	Average time: 0.000024

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

Many thanks to Kitayama, Itoh, Sterba and Chris!

---
 fs/btrfs/Makefile        |    2 +-
 fs/btrfs/btrfs_inode.h   |    5 +
 fs/btrfs/ctree.c         |   14 +-
 fs/btrfs/ctree.h         |   24 +-
 fs/btrfs/delayed-inode.c | 1665 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/delayed-inode.h |  142 ++++
 fs/btrfs/dir-item.c      |   32 +-
 fs/btrfs/disk-io.c       |   49 ++-
 fs/btrfs/disk-io.h       |    1 +
 fs/btrfs/extent-tree.c   |   18 +-
 fs/btrfs/inode.c         |  114 +++-
 fs/btrfs/ioctl.c         |    2 +-
 fs/btrfs/super.c         |   10 +-
 fs/btrfs/transaction.c   |   43 ++-
 fs/btrfs/transaction.h   |    2 +
 fs/btrfs/tree-log.c      |    7 +
 16 files changed, 2041 insertions(+), 89 deletions(-)
 create mode 100644 fs/btrfs/delayed-inode.c
 create mode 100644 fs/btrfs/delayed-inode.h

index 31610ea..a8411c2 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 lzo.o \
-	   compression.o delayed-ref.o relocation.o
+	   compression.o delayed-ref.o relocation.o delayed-inode.o

index ccc991c..ef3baa8 100644
@@ -22,6 +22,7 @@
 #include "extent_map.h"
 #include "extent_io.h"
 #include "ordered-data.h"
+#include "delayed-inode.h"
 
 /* in memory btrfs inode */
 struct btrfs_inode {

@@ -159,9 +160,13 @@ struct btrfs_inode {
 	 */
 	unsigned force_compress:4;
 
+	struct btrfs_delayed_node *delayed_node;
+
 	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);

index b5baff0..6e3e4c3 100644
@@ -38,11 +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)
 {

@@ -3688,11 +3683,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;

index 8b4b9d1..a068edc 100644
@@ -868,6 +868,7 @@ struct btrfs_block_group_cache {
 struct reloc_control;
 struct btrfs_device;
 struct btrfs_fs_devices;
+struct btrfs_delayed_root;
 struct btrfs_fs_info {
 	u8 fsid[BTRFS_FSID_SIZE];
 	u8 chunk_tree_uuid[BTRFS_UUID_SIZE];

@@ -894,7 +895,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;

@@ -1021,6 +1025,7 @@ struct btrfs_fs_info {
 	 * for the sys_munmap function call path
 	 */
 	struct btrfs_workers fixup_workers;
+	struct btrfs_workers delayed_workers;
 	struct task_struct *transaction_kthread;
 	struct task_struct *cleaner_kthread;
 	int thread_pool_size;

@@ -1078,6 +1083,8 @@ struct btrfs_fs_info {
 
 	/* filesystem state */
 	u64 fs_state;
+
+	struct btrfs_delayed_root *delayed_root;
 };
 
 /*

@@ -2095,6 +2102,13 @@ static inline bool btrfs_mixed_space_info(struct btrfs_space_info *space_info)
 }
 
 /* extent-tree.c */
+static inline u64 btrfs_calc_trans_metadata_size(struct btrfs_root *root,
+						 int num_items)
+{
+	return (root->leafsize + root->nodesize * (BTRFS_MAX_LEVEL - 1)) *
+		3 * num_items;
+}
+
 void btrfs_put_block_group(struct btrfs_block_group_cache *cache);
 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, unsigned long count);

@@ -2286,6 +2300,8 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p);
 struct btrfs_path *btrfs_alloc_path(void);
 void btrfs_free_path(struct btrfs_path *p);
 void btrfs_set_path_blocking(struct btrfs_path *p);
+void btrfs_clear_path_blocking(struct btrfs_path *p,
+			       struct extent_buffer *held);
 void btrfs_unlock_up_safe(struct btrfs_path *p, int level);
 
 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,

@@ -2297,6 +2313,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,

@@ -2358,7 +2378,7 @@ int btrfs_set_root_node(struct btrfs_root_item *item,
 /* dir-item.c */
 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans,
 			  struct btrfs_root *root, const char *name,
-			  int name_len, u64 dir,
+			  int name_len, struct inode *dir,
 			  struct btrfs_key *location, u8 type, u64 index);
 struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
 					     struct btrfs_root *root,

index f0cad5a..696c793 100644
@@ -124,8 +124,9 @@ int btrfs_insert_xattr_item(struct btrfs_trans_handle *trans,
  * to use for the second index (if one is created).
  */
 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
-			  *root, const char *name, int name_len, u64 dir,
-			  struct btrfs_key *location, u8 type, u64 index)
+			  *root, const char *name, int name_len,
+			  struct inode *dir, struct btrfs_key *location,
+			  u8 type, u64 index)
 {
 	int ret = 0;
 	int ret2 = 0;

@@ -137,13 +138,17 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
 	struct btrfs_disk_key disk_key;
 	u32 data_size;
 
-	key.objectid = dir;
+	key.objectid = dir->i_ino;
 	btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY);
 	key.offset = btrfs_name_hash(name, name_len);
 
 	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
 	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);

@@ -155,7 +160,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);

@@ -174,24 +178,8 @@ second_insert:
 	}
 	btrfs_release_path(root, path);
 
-	btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY);
-	key.offset = index;
-	dir_item = insert_with_overflow(trans, root, path, &key, data_size,
-					name, name_len);
-	if (IS_ERR(dir_item)) {
-		ret2 = PTR_ERR(dir_item);
-		goto out;
-	}
-	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);
-	btrfs_set_dir_name_len(leaf, dir_item, name_len);
-	btrfs_set_dir_transid(leaf, dir_item, trans->transid);
-	name_ptr = (unsigned long)(dir_item + 1);
-	write_extent_buffer(leaf, name, name_ptr, name_len);
-	btrfs_mark_buffer_dirty(leaf);
+	ret2 = btrfs_insert_delayed_dir_index(trans, root, name, name_len, dir,
+					      &disk_key, type, index);
 out:
 	btrfs_free_path(path);
 	if (ret)

index 07b20dc..aca35af 100644
@@ -71,6 +71,7 @@ int btrfs_insert_dev_radix(struct btrfs_root *root,
 			   u64 block_start,
 			   u64 num_blocks);
 void btrfs_btree_balance_dirty(struct btrfs_root *root, unsigned long nr);
+void __btrfs_btree_balance_dirty(struct btrfs_root *root, unsigned long nr);
 int btrfs_free_fs_root(struct btrfs_fs_info *fs_info, struct btrfs_root *root);
 void btrfs_mark_buffer_dirty(struct extent_buffer *buf);
 void btrfs_mark_buffer_dirty_nonblocking(struct extent_buffer *buf);

index 42061d2..cb5c7dc 100644
@@ -3905,12 +3905,6 @@ static void release_global_block_rsv(struct btrfs_fs_info *fs_info)
 	WARN_ON(fs_info->chunk_block_rsv.reserved > 0);
 }
 
-static u64 calc_trans_metadata_size(struct btrfs_root *root, int num_items)
-{
-	return (root->leafsize + root->nodesize * (BTRFS_MAX_LEVEL - 1)) *
-		3 * num_items;
-}
-
 int btrfs_trans_reserve_metadata(struct btrfs_trans_handle *trans,
 				 struct btrfs_root *root,
 				 int num_items)

@@ -3921,7 +3915,7 @@ int btrfs_trans_reserve_metadata(struct btrfs_trans_handle *trans,
 	if (num_items == 0 || root->fs_info->chunk_root == root)
 		return 0;
 
-	num_bytes = calc_trans_metadata_size(root, num_items);
+	num_bytes = btrfs_calc_trans_metadata_size(root, num_items);
 	ret = btrfs_block_rsv_add(trans, root, &root->fs_info->trans_block_rsv,
 				  num_bytes);
 	if (!ret) {

@@ -3960,14 +3954,14 @@ int btrfs_orphan_reserve_metadata(struct btrfs_trans_handle *trans,
 	 * If all of the metadata space is used, we can commit
 	 * transaction and use space it freed.
 	 */
-	u64 num_bytes = calc_trans_metadata_size(root, 4);
+	u64 num_bytes = btrfs_calc_trans_metadata_size(root, 4);
 	return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
 }
 
 void btrfs_orphan_release_metadata(struct inode *inode)
 {
 	struct btrfs_root *root = BTRFS_I(inode)->root;
-	u64 num_bytes = calc_trans_metadata_size(root, 4);
+	u64 num_bytes = btrfs_calc_trans_metadata_size(root, 4);
 	btrfs_block_rsv_release(root, root->orphan_block_rsv, num_bytes);
 }
 

@@ -3981,7 +3975,7 @@ int btrfs_snap_reserve_metadata(struct btrfs_trans_handle *trans,
 	 * two for root back/forward refs, two for directory entries
 	 * and one for root of the snapshot.
 	 */
-	u64 num_bytes = calc_trans_metadata_size(root, 5);
+	u64 num_bytes = btrfs_calc_trans_metadata_size(root, 5);
 	dst_rsv->space_info = src_rsv->space_info;
 	return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
 }

@@ -4008,7 +4002,7 @@ int btrfs_delalloc_reserve_metadata(struct inode *inode, u64 num_bytes)
 	nr_extents = atomic_read(&BTRFS_I(inode)->outstanding_extents) + 1;
 	if (nr_extents > BTRFS_I(inode)->reserved_extents) {
 		nr_extents -= BTRFS_I(inode)->reserved_extents;
-		to_reserve = calc_trans_metadata_size(root, nr_extents);
+		to_reserve = btrfs_calc_trans_metadata_size(root, nr_extents);
 	} else {
 		nr_extents = 0;
 		to_reserve = 0;

@@ -4054,7 +4048,7 @@ void btrfs_delalloc_release_metadata(struct inode *inode, u64 num_bytes)
 
 	to_free = calc_csum_metadata_size(inode, num_bytes);
 	if (nr_extents > 0)
-		to_free += calc_trans_metadata_size(root, nr_extents);
+		to_free += btrfs_calc_trans_metadata_size(root, nr_extents);
 
 	btrfs_block_rsv_release(root, &root->fs_info->delalloc_block_rsv,
 				to_free);

index 5fdb2ab..b200e07 100644
@@ -333,7 +333,7 @@ static noinline int create_subvol(struct btrfs_root *root,
 	BUG_ON(ret);
 
 	ret = btrfs_insert_dir_item(trans, root,
-				    name, namelen, dir->i_ino, &key,
+				    name, namelen, dir, &key,
 				    BTRFS_FT_DIR, index);
 	if (ret)
 		goto fail;

index db0a827..593ce8a 100644
@@ -40,6 +40,7 @@
 #include <linux/magic.h>
 #include <linux/slab.h>
 #include "compat.h"
+#include "delayed-inode.h"
 #include "ctree.h"
 #include "disk-io.h"
 #include "transaction.h"

@@ -1163,10 +1164,14 @@ static int __init init_btrfs_fs(void)
 	if (err)
 		goto free_extent_io;
 
-	err = btrfs_interface_init();
+	err = btrfs_delayed_inode_init();
 	if (err)
 		goto free_extent_map;
 
+	err = btrfs_interface_init();
+	if (err)
+		goto free_delayed_inode;
+
 	err = register_filesystem(&btrfs_fs_type);
 	if (err)
 		goto unregister_ioctl;

@@ -1176,6 +1181,8 @@ static int __init init_btrfs_fs(void)
 
 unregister_ioctl:
 	btrfs_interface_exit();
+free_delayed_inode:
+	btrfs_delayed_inode_exit();
 free_extent_map:
 	extent_map_exit();
 free_extent_io:

@@ -1192,6 +1199,7 @@ free_sysfs:
 static void __exit exit_btrfs_fs(void)
 {
 	btrfs_destroy_cachep();
+	btrfs_delayed_inode_exit();
 	extent_map_exit();
 	extent_io_exit();
 	btrfs_interface_exit();

index 229a594..a4a441f 100644
@@ -115,6 +115,8 @@ int btrfs_commit_transaction_async(struct btrfs_trans_handle *trans,
 				   int wait_for_unblock);
 int btrfs_end_transaction_throttle(struct btrfs_trans_handle *trans,
 				   struct btrfs_root *root);
+int btrfs_end_transaction_dmeta(struct btrfs_trans_handle *trans,
+				struct btrfs_root *root);
 int btrfs_should_end_transaction(struct btrfs_trans_handle *trans,
 				 struct btrfs_root *root);
 void btrfs_throttle(struct btrfs_root *root);

index a4bbb85..e8a2e95 100644
@@ -2775,6 +2775,13 @@ static int btrfs_log_inode(struct btrfs_trans_handle *trans,
 		max_key.type = (u8)-1;
 	max_key.offset = (u64)-1;
 
+	ret = btrfs_commit_inode_delayed_items(trans, root, inode);
+	if (ret) {
+		btrfs_free_path(path);
+		btrfs_free_path(dst_path);
+		return ret;
+	}
+
 	mutex_lock(&BTRFS_I(inode)->log_mutex);
 
 	/*

1.7.3.1

Hi,

there's one thing I want to bring up. It's not related to delayed functionality itself but to git tree base of the patch.

There's a merge conflict when your patch is applied directly onto Linus' tree, and not when on Chris' one.

On Thu, Mar 24, 2011 at 07:41:31PM +0800, Miao Xie wrote:
...

Author: Nick Piggin <[email protected]>
Date:   Fri Jan 7 17:49:49 2011 +1100

@@ -6495,6 +6495,13 @@ struct inode *btrfs_alloc_inode(struct super_block *sb)
        return inode;
 }
 
+static void btrfs_i_callback(struct rcu_head *head)
+{
+       struct inode *inode = container_of(head, struct inode, i_rcu);
+       INIT_LIST_HEAD(&inode->i_dentry);
+       kmem_cache_free(btrfs_inode_cachep, BTRFS_I(inode));
+}
+
 void btrfs_destroy_inode(struct inode *inode)
 {
        struct btrfs_ordered_extent *ordered;

@@ -6564,7 +6571,7 @@ void btrfs_destroy_inode(struct inode *inode)
        inode_tree_del(inode);
        btrfs_drop_extent_cache(inode, 0, (u64)-1, 0);
 free:
-       kmem_cache_free(btrfs_inode_cachep, BTRFS_I(inode));
+       call_rcu(&inode->i_rcu, btrfs_i_callback);
 }
 
 

Excerpts from Miao Xie's message of 2011-03-24 07:41:31 -0400:

This does do much better than v4, but I'm still hitting oom with stress.sh -n 50. I tried a bunch of variations but haven't been able to get it quite right. I think I need to hold off on this one and get the 2.6.39 pull request out.

I'll setup a .40 tree that has this in it and we can fix the ooms. This is a great base for the work, and I'd like to add more items to the delay, especially the initial inode insertions.

-chris

Hi Miao,

Chris' stress test, stress.sh -n 50 -c /mnt/linux-2.6 /mnt gave me another lockdep splat (see below). I applied your V5 patches on top of the next-rc branch.

I haven't triggered it in my actual testing, but do you think we can iterate a list of block groups in an lockless manner using rcu?

index 2164296..f40ff4e 100644
@@ -740,6 +740,7 @@ struct btrfs_space_info {
 	struct list_head block_groups[BTRFS_NR_RAID_TYPES];
 	spinlock_t lock;
 	struct rw_semaphore groups_sem;
+	struct srcu_struct groups_srcu;
 	atomic_t caching_threads;
 };
 

index 9e4c9f4..22d6dbb 100644
@@ -3003,6 +3003,7 @@ static int update_space_info(struct btrfs_fs_info *info, u64 flags,
 	for (i = 0; i < BTRFS_NR_RAID_TYPES; i++)
 		INIT_LIST_HEAD(&found->block_groups[i]);
 	init_rwsem(&found->groups_sem);
+	init_srcu_struct(&found->groups_srcu);
 	spin_lock_init(&found->lock);
 	found->flags = flags & (BTRFS_BLOCK_GROUP_DATA |
 				BTRFS_BLOCK_GROUP_SYSTEM |

@@ -4853,6 +4854,7 @@ static noinline int find_free_extent(struct btrfs_trans_handle *trans,
 				     int data)
 {
 	int ret = 0;
+	int idx;
 	struct btrfs_root *root = orig_root->fs_info->extent_root;
 	struct btrfs_free_cluster *last_ptr = NULL;
 	struct btrfs_block_group_cache *block_group = NULL;

@@ -4929,7 +4931,7 @@ ideal_cache:
 		if (block_group && block_group_bits(block_group, data) &&
 		    (block_group->cached != BTRFS_CACHE_NO ||
 		     search_start == ideal_cache_offset)) {
-			down_read(&space_info->groups_sem);
+			idx = srcu_read_lock(&space_info->groups_srcu);
 			if (list_empty(&block_group->list) ||
 			    block_group->ro) {
 				/*

@@ -4939,7 +4941,7 @@ ideal_cache:
 				 * valid
 				 */
 				btrfs_put_block_group(block_group);
-				up_read(&space_info->groups_sem);
+				srcu_read_unlock(&space_info->groups_srcu, idx);
 			} else {
 				index = get_block_group_index(block_group);
 				goto have_block_group;

@@ -4949,8 +4951,8 @@ ideal_cache:
 		}
 	}
 search:
-	down_read(&space_info->groups_sem);
-	list_for_each_entry(block_group, &space_info->block_groups[index],
+	idx = srcu_read_lock(&space_info->groups_srcu);
+	list_for_each_entry_rcu(block_group, &space_info->block_groups[index],
 			    list) {
 		u64 offset;
 		int cached;

@@ -5197,8 +5199,8 @@ loop:
 		BUG_ON(index != get_block_group_index(block_group));
 		btrfs_put_block_group(block_group);
 	}
-	up_read(&space_info->groups_sem);
-
+	srcu_read_unlock(&space_info->groups_srcu, idx);
+	
 	if (!ins->objectid && ++index < BTRFS_NR_RAID_TYPES)
 		goto search;
 

=========================================================
[ INFO: possible irq lock inversion dependency detected ]
2.6.36-v5+ #2
---------------------------------------------------------
kswapd0/49 just changed the state of lock:
(&delayed_node->mutex){+.+.-.}, at: [<ffffffff812131f7>] btrfs_remove_delayed_node+0x3e/0xd2
but this lock took another, RECLAIM_FS-READ-unsafe lock in the past:
(&found->groups_sem){++++.+}

and interrupts could create inverse lock ordering between them.

other info that might help us debug this:
2 locks held by kswapd0/49:
#0: (shrinker_rwsem){++++..}, at: [<ffffffff810e242a>] shrink_slab+0x3d/0x164 #1: (iprune_sem){++++.-}, at: [<ffffffff811316d0>] shrink_icache_memory+0x4d/0x213

the shortest dependencies between 2nd lock and 1st lock:

 -> (&found->groups_sem){++++.+} ops: 1334 {
    HARDIRQ-ON-W at:
                          [<ffffffff81075ec0>] __lock_acquire+0x346/0xda6
                          [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                          [<ffffffff814c6a2a>] down_write+0x55/0x9b
                          [<ffffffff811c352a>] __link_block_group+0x5a/0x83
                          [<ffffffff811ca562>] btrfs_read_block_groups+0x2fb/0x56c
                          [<ffffffff811d4921>] open_ctree+0xf78/0x14ab
                          [<ffffffff811bafdf>] btrfs_get_sb+0x236/0x467
                          [<ffffffff8111f25e>] vfs_kern_mount+0xbd/0x1a7
                          [<ffffffff8111f3b0>] do_kern_mount+0x4d/0xed
                          [<ffffffff8113668d>] do_mount+0x74e/0x7c5
                          [<ffffffff8113678c>] sys_mount+0x88/0xc2
                          [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
    HARDIRQ-ON-R at:
                          [<ffffffff81075e98>] __lock_acquire+0x31e/0xda6
                          [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                          [<ffffffff814c6abc>] down_read+0x4c/0x91
                          [<ffffffff811cb5b2>] find_free_extent+0x3ec/0xa86
                          [<ffffffff811cbd00>] btrfs_reserve_extent+0xb4/0x142
                          [<ffffffff811cbef5>] btrfs_alloc_free_block+0x167/0x2b2
                          [<ffffffff811be610>] __btrfs_cow_block+0x103/0x346
                          [<ffffffff811bedb8>] btrfs_cow_block+0x101/0x110
                          [<ffffffff811c05d8>] btrfs_search_slot+0x143/0x513
                          [<ffffffff811c1495>] btrfs_insert_empty_items+0x6a/0xbc
                          [<ffffffff811ffb68>] btrfs_insert_orphan_item+0x5d/0x75
                          [<ffffffff811df1a1>] btrfs_orphan_add+0x139/0x152
                          [<ffffffff811e0dd3>] btrfs_setattr+0xff/0x253
                          [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                          [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                          [<ffffffff81127a77>] do_last+0x579/0x57e
                          [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                          [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                          [<ffffffff8111af8f>] sys_open+0x20/0x22
                          [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
    SOFTIRQ-ON-W at:
                          [<ffffffff81075ee1>] __lock_acquire+0x367/0xda6
                          [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                          [<ffffffff814c6a2a>] down_write+0x55/0x9b
                          [<ffffffff811c352a>] __link_block_group+0x5a/0x83
                          [<ffffffff811ca562>] btrfs_read_block_groups+0x2fb/0x56c
                          [<ffffffff811d4921>] open_ctree+0xf78/0x14ab
                          [<ffffffff811bafdf>] btrfs_get_sb+0x236/0x467
                          [<ffffffff8111f25e>] vfs_kern_mount+0xbd/0x1a7
                          [<ffffffff8111f3b0>] do_kern_mount+0x4d/0xed
                          [<ffffffff8113668d>] do_mount+0x74e/0x7c5
                          [<ffffffff8113678c>] sys_mount+0x88/0xc2
                          [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
    SOFTIRQ-ON-R at:
                          [<ffffffff81075ee1>] __lock_acquire+0x367/0xda6
                          [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                          [<ffffffff814c6abc>] down_read+0x4c/0x91
                          [<ffffffff811cb5b2>] find_free_extent+0x3ec/0xa86
                          [<ffffffff811cbd00>] btrfs_reserve_extent+0xb4/0x142
                          [<ffffffff811cbef5>] btrfs_alloc_free_block+0x167/0x2b2
                          [<ffffffff811be610>] __btrfs_cow_block+0x103/0x346
                          [<ffffffff811bedb8>] btrfs_cow_block+0x101/0x110
                          [<ffffffff811c05d8>] btrfs_search_slot+0x143/0x513
                          [<ffffffff811c1495>] btrfs_insert_empty_items+0x6a/0xbc
                          [<ffffffff811ffb68>] btrfs_insert_orphan_item+0x5d/0x75
                          [<ffffffff811df1a1>] btrfs_orphan_add+0x139/0x152
                          [<ffffffff811e0dd3>] btrfs_setattr+0xff/0x253
                          [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                          [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                          [<ffffffff81127a77>] do_last+0x579/0x57e
                          [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                          [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                          [<ffffffff8111af8f>] sys_open+0x20/0x22
                          [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
    RECLAIM_FS-ON-R at:
                             [<ffffffff81074292>] mark_held_locks+0x52/0x70
                             [<ffffffff81074354>] lockdep_trace_alloc+0xa4/0xc2
                             [<ffffffff810db873>] __alloc_pages_nodemask+0x96/0x841
                             [<ffffffff81105bcb>] alloc_pages_current+0xa7/0xca
                             [<ffffffff810d4d91>] __page_cache_alloc+0x85/0x8c
                             [<ffffffff810ddef6>] __do_page_cache_readahead+0xb5/0x19d
                             [<ffffffff810ddfff>] ra_submit+0x21/0x25
                             [<ffffffff810de3b9>] ondemand_readahead+0x1b6/0x1c9
                             [<ffffffff810de4b2>] page_cache_sync_readahead+0x3d/0x3f
                             [<ffffffff8120798d>] load_free_space_cache+0x262/0x671
                             [<ffffffff811c886f>] cache_block_group+0x97/0x233
                             [<ffffffff811cb63f>] find_free_extent+0x479/0xa86
                             [<ffffffff811cbd00>] btrfs_reserve_extent+0xb4/0x142
                             [<ffffffff811cbef5>] btrfs_alloc_free_block+0x167/0x2b2
                             [<ffffffff811be610>] __btrfs_cow_block+0x103/0x346
                             [<ffffffff811bedb8>] btrfs_cow_block+0x101/0x110
                             [<ffffffff811c05d8>] btrfs_search_slot+0x143/0x513
                             [<ffffffff811c1495>] btrfs_insert_empty_items+0x6a/0xbc
                             [<ffffffff811ffb68>] btrfs_insert_orphan_item+0x5d/0x75
                             [<ffffffff811df1a1>] btrfs_orphan_add+0x139/0x152
                             [<ffffffff811e0dd3>] btrfs_setattr+0xff/0x253
                             [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                             [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                             [<ffffffff81127a77>] do_last+0x579/0x57e
                             [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                             [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                             [<ffffffff8111af8f>] sys_open+0x20/0x22
                             [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
    INITIAL USE at:
                         [<ffffffff81075f37>] __lock_acquire+0x3bd/0xda6
                         [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                         [<ffffffff814c6a2a>] down_write+0x55/0x9b
                         [<ffffffff811c352a>] __link_block_group+0x5a/0x83
                         [<ffffffff811ca562>] btrfs_read_block_groups+0x2fb/0x56c
                         [<ffffffff811d4921>] open_ctree+0xf78/0x14ab
                         [<ffffffff811bafdf>] btrfs_get_sb+0x236/0x467
                         [<ffffffff8111f25e>] vfs_kern_mount+0xbd/0x1a7
                         [<ffffffff8111f3b0>] do_kern_mount+0x4d/0xed
                         [<ffffffff8113668d>] do_mount+0x74e/0x7c5
                         [<ffffffff8113678c>] sys_mount+0x88/0xc2
                         [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
  }
  ... key      at: [<ffffffff82924fb8>] __key.40112+0x0/0x8
  ... acquired at:
   [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
   [<ffffffff814c6abc>] down_read+0x4c/0x91
   [<ffffffff811cb48a>] find_free_extent+0x2c4/0xa86
   [<ffffffff811cbd00>] btrfs_reserve_extent+0xb4/0x142
   [<ffffffff811cbef5>] btrfs_alloc_free_block+0x167/0x2b2
   [<ffffffff811be610>] __btrfs_cow_block+0x103/0x346
   [<ffffffff811bedb8>] btrfs_cow_block+0x101/0x110
   [<ffffffff811c05d8>] btrfs_search_slot+0x143/0x513
   [<ffffffff811cf58b>] btrfs_lookup_inode+0x2f/0x8f
   [<ffffffff812123e5>] btrfs_update_delayed_inode+0x75/0x135
   [<ffffffff8121306e>] btrfs_async_run_delayed_node_done+0xd5/0x194
   [<ffffffff811fb48e>] worker_loop+0x198/0x4dd
   [<ffffffff81061a60>] kthread+0x9d/0xa5
   [<ffffffff81003c14>] kernel_thread_helper+0x4/0x10

-> (&delayed_node->mutex){+.+.-.} ops: 8932 {
HARDIRQ-ON-W at:

                        [<ffffffff81075ec0>] __lock_acquire+0x346/0xda6
                        [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                        [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
                        [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
                        [<ffffffff81211fb4>] btrfs_delayed_update_inode+0x45/0x101
                        [<ffffffff811dc5a3>] btrfs_update_inode+0x2e/0x129
                        [<ffffffff811e0c9a>] btrfs_truncate+0x43d/0x477
                        [<ffffffff810dfb22>] vmtruncate+0x44/0x52
                        [<ffffffff811e0ed6>] btrfs_setattr+0x202/0x253
                        [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                        [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                        [<ffffffff81127a77>] do_last+0x579/0x57e
                        [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                        [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                        [<ffffffff8111af8f>] sys_open+0x20/0x22
                        [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
   SOFTIRQ-ON-W at:
                        [<ffffffff81075ee1>] __lock_acquire+0x367/0xda6
                        [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                        [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
                        [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
                        [<ffffffff81211fb4>] btrfs_delayed_update_inode+0x45/0x101
                        [<ffffffff811dc5a3>] btrfs_update_inode+0x2e/0x129
                        [<ffffffff811e0c9a>] btrfs_truncate+0x43d/0x477
                        [<ffffffff810dfb22>] vmtruncate+0x44/0x52
                        [<ffffffff811e0ed6>] btrfs_setattr+0x202/0x253
                        [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                        [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                        [<ffffffff81127a77>] do_last+0x579/0x57e
                        [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                        [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                        [<ffffffff8111af8f>] sys_open+0x20/0x22
                        [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
   IN-RECLAIM_FS-W at:
                           [<ffffffff81075f1f>] __lock_acquire+0x3a5/0xda6
                           [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                           [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
                           [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
                           [<ffffffff812131f7>] btrfs_remove_delayed_node+0x3e/0xd2
                           [<ffffffff811d77aa>] btrfs_destroy_inode+0x2ae/0x2d4
                           [<ffffffff81130dc1>] destroy_inode+0x2f/0x45
                           [<ffffffff811312ca>] dispose_list+0xaa/0xdf
                           [<ffffffff81131866>] shrink_icache_memory+0x1e3/0x213
                           [<ffffffff810e24cd>] shrink_slab+0xe0/0x164
                           [<ffffffff810e4619>] balance_pgdat+0x2e8/0x50b
                           [<ffffffff810e4bbc>] kswapd+0x380/0x3c0
                           [<ffffffff81061a60>] kthread+0x9d/0xa5
                           [<ffffffff81003c14>] kernel_thread_helper+0x4/0x10
   INITIAL USE at:
                       [<ffffffff81075f37>] __lock_acquire+0x3bd/0xda6
                       [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
                       [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
                       [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
                       [<ffffffff81211fb4>] btrfs_delayed_update_inode+0x45/0x101
                       [<ffffffff811dc5a3>] btrfs_update_inode+0x2e/0x129
                       [<ffffffff811e0c9a>] btrfs_truncate+0x43d/0x477
                       [<ffffffff810dfb22>] vmtruncate+0x44/0x52
                       [<ffffffff811e0ed6>] btrfs_setattr+0x202/0x253
                       [<ffffffff8113201e>] notify_change+0x1a2/0x29d
                       [<ffffffff8111bf08>] do_truncate+0x6c/0x89
                       [<ffffffff81127a77>] do_last+0x579/0x57e
                       [<ffffffff81129502>] do_filp_open+0x215/0x5ae
                       [<ffffffff8111aec0>] do_sys_open+0x60/0xfc
                       [<ffffffff8111af8f>] sys_open+0x20/0x22
                       [<ffffffff81002ddb>] system_call_fastpath+0x16/0x1b
 }
 ... key      at: [<ffffffff82925450>] __key.31289+0x0/0x8
 ... acquired at:
   [<ffffffff810749bf>] check_usage_forwards+0x71/0x7e
   [<ffffffff81074162>] mark_lock+0x18c/0x26a
   [<ffffffff81075f1f>] __lock_acquire+0x3a5/0xda6
   [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
   [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
   [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
   [<ffffffff812131f7>] btrfs_remove_delayed_node+0x3e/0xd2
   [<ffffffff811d77aa>] btrfs_destroy_inode+0x2ae/0x2d4
   [<ffffffff81130dc1>] destroy_inode+0x2f/0x45
   [<ffffffff811312ca>] dispose_list+0xaa/0xdf
   [<ffffffff81131866>] shrink_icache_memory+0x1e3/0x213
   [<ffffffff810e24cd>] shrink_slab+0xe0/0x164
   [<ffffffff810e4619>] balance_pgdat+0x2e8/0x50b
   [<ffffffff810e4bbc>] kswapd+0x380/0x3c0
   [<ffffffff81061a60>] kthread+0x9d/0xa5
   [<ffffffff81003c14>] kernel_thread_helper+0x4/0x10


stack backtrace:
Pid: 49, comm: kswapd0 Not tainted 2.6.36-v5+ #2
Call Trace:
 [<ffffffff8107493d>] print_irq_inversion_bug+0x124/0x135
 [<ffffffff810749bf>] check_usage_forwards+0x71/0x7e
 [<ffffffff8107494e>] ? check_usage_forwards+0x0/0x7e
 [<ffffffff81074162>] mark_lock+0x18c/0x26a
 [<ffffffff81075f1f>] __lock_acquire+0x3a5/0xda6
 [<ffffffff81076911>] ? __lock_acquire+0xd97/0xda6
 [<ffffffff812131f7>] ? btrfs_remove_delayed_node+0x3e/0xd2
 [<ffffffff81076a3d>] lock_acquire+0x11d/0x143
 [<ffffffff812131f7>] ? btrfs_remove_delayed_node+0x3e/0xd2
 [<ffffffff812131f7>] ? btrfs_remove_delayed_node+0x3e/0xd2
 [<ffffffff814c6291>] __mutex_lock_common+0x5a/0x444
 [<ffffffff812131f7>] ? btrfs_remove_delayed_node+0x3e/0xd2
 [<ffffffff81074604>] ? trace_hardirqs_on+0xd/0xf
 [<ffffffff814c6730>] mutex_lock_nested+0x39/0x3e
 [<ffffffff812131f7>] btrfs_remove_delayed_node+0x3e/0xd2
 [<ffffffff811d77aa>] btrfs_destroy_inode+0x2ae/0x2d4
 [<ffffffff81130dc1>] destroy_inode+0x2f/0x45
 [<ffffffff811312ca>] dispose_list+0xaa/0xdf
 [<ffffffff81131866>] shrink_icache_memory+0x1e3/0x213
 [<ffffffff810e24cd>] shrink_slab+0xe0/0x164
 [<ffffffff810e4619>] balance_pgdat+0x2e8/0x50b
 [<ffffffff810e4bbc>] kswapd+0x380/0x3c0
 [<ffffffff81062032>] ? autoremove_wake_function+0x0/0x39
 [<ffffffff810e483c>] ? kswapd+0x0/0x3c0
 [<ffffffff81061a60>] kthread+0x9d/0xa5
 [<ffffffff81003c14>] kernel_thread_helper+0x4/0x10
 [<ffffffff81038cd9>] ? finish_task_switch+0x70/0xb9
 [<ffffffff814c8880>] ? restore_args+0x0/0x30
 [<ffffffff810619c3>] ? kthread+0x0/0xa5
 [<ffffffff81003c10>] ? kernel_thread_helper+0x0/0x10

I got it. It is because the allocation flag of the metadata's page cache, which is stored in the btree inode's i_mapping, was set to be GFP_HIGHUSER_MOVABLE. So if we allocate pages for btree's page cache, this lockdep warning will be triggered.

I think even without my patch, this lockdep warning can also be triggered, btrfs_evict_inode() do the similar operations like what I do in the btrfs_destroy_inode().
Task1 Kswap0 task
open()

    ...
    btrfs_search_slot()
      ...
      btrfs_cow_block()
	...
	alloc_page()
	  wait for reclaiming
					shrink_slab()
					  ...
					  shrink_icache_memory()
					    ...
					    btrfs_evict_inode()
					      ...
					      btrfs_search_slot()

If the path is locked by task1, the deadlock happens.

So the btree's page cache is different with the file's page cache, it can not allocate pages by GFP_HIGHUSER_MOVABLE flag.

I will make a separate patch to fix it.

May be we can use it, but AFAIK, the write-side of the sleepable RCU is quite slow. Though the operations of the block group list are few, I think we should do some test to check the performance regression.

Thanks
Miao

Hi Miao,

Ok. balance_pgdat() calls shrink_slab() with GFP_KERNEL so it's still possible for the kswapd0 to call prune_icache(), no? I still see the lockdep warning even with your patch that clears __GFP_FS in open_ctree().

itaru

sorry for my mistake. The above explanation is wrong, it has no business with kswap thread. The correct explanation is

Task1
open()

     ...
     btrfs_search_slot()
       ...
       btrfs_cow_block()

...
alloc_page()
do_try_to_free_pages()
shrink_slab()
...
shrink_icache_memory()
...
btrfs_evict_inode()
...
btrfs_search_slot()

If the path is locked by task1, the deadlock happens.

So balance_pgdat() is impossible to trigger the lockdep. (My clearing __GFP_FS patch's changelog is also wrong.)

I see, except btree's page cache, free space cache's page cache is also special, can not use __GFP_FS flag.

Thanks
Miao

Excerpts from Miao Xie's message of 2011-03-27 07:44:06 -0400:

Ok, I've got your first patch already, I'll add a hunk for the free space cache too. Most of the allocations we're doing are explicitly with GFP_NOFS, so it is just supporting allocations and readahead that should be causing trouble.

Thanks!

-chris