btrfs: Simplify locking

Hello, guys.

I've been looking through btrfs code and found out that the locking was quite interesting. The distinction between blocking and non-blocking locking is valid but is essentially attacing the same problem that CONFIG_MUTEX_SPIN_ON_OWNER addresses in generic manner.

It seemed that CONFIG_MUTEX_SPIN_ON_OWNER should be able to do it better as it actually knows whether the lock owner is running or not, so I did a few "dbench 50" runs with the complex locking removed.

The test machine is a dual core machine with 1 gig of memory. The filesystem is on OCZ vertex 64 gig SSD. I'm attaching the kernel config. Please note that CONFIG_MUTEX_SPIN_ON_OWNER is enabled only when lock debugging is disabled, but it will be enabled on virtually any production configuration.

The machine was idle during the dbench runs and CPU usages and context switches are calculated from /proc/stat over the dbench runs. The throughput is as reported by dbench.

         user  system  sirq    cxtsw throughput
before  14426  129332   345  1674004    171.7
after   14274  129036   308  1183346    172.119

So, the extra code isn't really helping anything. It's worse in every way. Are there some obscure reasons the custom locking should be kept around?

One thing to note is that the patch makes try_tree_lock and try_spin_lock identical. It might be benefical to apply owner spin logic to try_spin_lock. I'll test that one too and see whether it makes any difference.

Thanks.

---
 fs/btrfs/Makefile    |    2 
 fs/btrfs/ctree.c     |   16 +--
 fs/btrfs/extent_io.c |    3 
 fs/btrfs/extent_io.h |   12 --
 fs/btrfs/locking.c   |  233 ---------------------------------------------------
 fs/btrfs/locking.h   |   43 +++++++--
 6 files changed, 48 insertions(+), 261 deletions(-)

Index: work/fs/btrfs/ctree.c
===================================================================
@@ -1074,7 +1074,7 @@ static noinline int balance_level(struct
 
 	left = read_node_slot(root, parent, pslot - 1);
 	if (left) {
-		btrfs_tree_lock(left);
+		btrfs_tree_lock_nested(left, 1);
 		btrfs_set_lock_blocking(left);
 		wret = btrfs_cow_block(trans, root, left,
 				       parent, pslot - 1, &left);

@@ -1085,7 +1085,7 @@ static noinline int balance_level(struct
 	}
 	right = read_node_slot(root, parent, pslot + 1);
 	if (right) {
-		btrfs_tree_lock(right);
+		btrfs_tree_lock_nested(right, 2);
 		btrfs_set_lock_blocking(right);
 		wret = btrfs_cow_block(trans, root, right,
 				       parent, pslot + 1, &right);

@@ -1241,7 +1241,7 @@ static noinline int push_nodes_for_inser
 	if (left) {
 		u32 left_nr;
 
-		btrfs_tree_lock(left);
+		btrfs_tree_lock_nested(left, 1);
 		btrfs_set_lock_blocking(left);
 
 		left_nr = btrfs_header_nritems(left);

@@ -1291,7 +1291,7 @@ static noinline int push_nodes_for_inser
 	if (right) {
 		u32 right_nr;
 
-		btrfs_tree_lock(right);
+		btrfs_tree_lock_nested(right, 1);
 		btrfs_set_lock_blocking(right);
 
 		right_nr = btrfs_header_nritems(right);

@@ -2519,7 +2519,7 @@ static int push_leaf_right(struct btrfs_
 	if (right == NULL)
 		return 1;
 
-	btrfs_tree_lock(right);
+	btrfs_tree_lock_nested(right, 1);
 	btrfs_set_lock_blocking(right);
 
 	free_space = btrfs_leaf_free_space(root, right);

@@ -2772,7 +2772,7 @@ static int push_leaf_left(struct btrfs_t
 	if (left == NULL)
 		return 1;
 
-	btrfs_tree_lock(left);
+	btrfs_tree_lock_nested(left, 1);
 	btrfs_set_lock_blocking(left);
 
 	free_space = btrfs_leaf_free_space(root, left);

@@ -4420,7 +4420,7 @@ again:
 			ret = btrfs_try_spin_lock(next);
 			if (!ret) {
 				btrfs_set_path_blocking(path);
-				btrfs_tree_lock(next);
+				btrfs_tree_lock_nested(next, 1);
 				if (!force_blocking)
 					btrfs_clear_path_blocking(path, next);
 			}

@@ -4460,7 +4460,7 @@ again:
 			ret = btrfs_try_spin_lock(next);
 			if (!ret) {
 				btrfs_set_path_blocking(path);
-				btrfs_tree_lock(next);
+				btrfs_tree_lock_nested(next, 1);
 				if (!force_blocking)
 					btrfs_clear_path_blocking(path, next);
 			}

Index: work/fs/btrfs/extent_io.c
===================================================================
@@ -3171,8 +3171,7 @@ static struct extent_buffer *__alloc_ext
 		return NULL;
 	eb->start = start;
 	eb->len = len;
-	spin_lock_init(&eb->lock);
-	init_waitqueue_head(&eb->lock_wq);
+	mutex_init(&eb->lock);
 	INIT_RCU_HEAD(&eb->rcu_head);
 
 #if LEAK_DEBUG

Index: work/fs/btrfs/extent_io.h
===================================================================
@@ -2,6 +2,7 @@
 #define __EXTENTIO__
 
 #include <linux/rbtree.h>
+#include <linux/mutex.h>
 
 /* bits for the extent state */
 #define EXTENT_DIRTY 1

@@ -29,7 +30,6 @@
 
 /* these are bit numbers for test/set bit */
 #define EXTENT_BUFFER_UPTODATE 0
-#define EXTENT_BUFFER_BLOCKING 1
 #define EXTENT_BUFFER_DIRTY 2
 
 /* these are flags for extent_clear_unlock_delalloc */

@@ -129,14 +129,8 @@ struct extent_buffer {
 	struct list_head leak_list;
 	struct rcu_head rcu_head;
 
-	/* the spinlock is used to protect most operations */
-	spinlock_t lock;
-
-	/*
-	 * when we keep the lock held while blocking, waiters go onto
-	 * the wq
-	 */
-	wait_queue_head_t lock_wq;
+	/* used to protect most operations */
+	struct mutex lock;
 };
 
 static inline void extent_set_compress_type(unsigned long *bio_flags,

Index: work/fs/btrfs/Makefile
===================================================================
@@ -5,6 +5,6 @@ btrfs-y += super.o ctree.o extent-tree.o
 	   file-item.o inode-item.o inode-map.o disk-io.o \
 	   transaction.o inode.o file.o tree-defrag.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 \
+	   extent_io.o volumes.o async-thread.o ioctl.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

So, here's the patch to implement and use mutex_try_spin(), which applies the same owner spin logic to try locking. The result looks pretty good.

I re-ran all three. DFL is the current custom locking. SIMPLE is with only the previous patch applied. SPIN is both the previous and this patches applied.

       USER   SYSTEM   SIRQ    CXTSW  THROUGHPUT
DFL    14484  129368    390  1669102     171.955
SIMPLE 14483  128902    318  1187031     171.512
SPIN   14311  129222    347  1198166     174.904

DFL/SIMPLE results are more or less consistent with the previous run. SPIN seems to consume a bit more cpu than SIMPLE but shows discernably better throughput. I'm running SPIN again just in case but the result seems pretty consistent.

Thanks.

---
 fs/btrfs/locking.h    |    2 -
 include/linux/mutex.h |    1 
 kernel/mutex.c        |   58 ++++++++++++++++++++++++++++++++++++--------------
 3 files changed, 44 insertions(+), 17 deletions(-)

Index: work/fs/btrfs/locking.h
===================================================================
@@ -23,7 +23,7 @@
 
 static inline bool btrfs_try_spin_lock(struct extent_buffer *eb)
 {
-	return mutex_trylock(&eb->lock);
+	return mutex_tryspin(&eb->lock);
 }
 
 static inline void btrfs_tree_lock(struct extent_buffer *eb)

Index: work/include/linux/mutex.h
===================================================================
@@ -157,6 +157,7 @@ extern int __must_check mutex_lock_killa
  * Returns 1 if the mutex has been acquired successfully, and 0 on contention.
  */
 extern int mutex_trylock(struct mutex *lock);
+extern int mutex_tryspin(struct mutex *lock);
 extern void mutex_unlock(struct mutex *lock);
 extern int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
 

Here's another run.

SPIN 14377 129092 335 1189817 172.724

It's not as high as the last run, but given other runs I've been seeing, I think meaningful (ie. not measurement error) throughput advantage exists. That said, the difference definitely seems minor.

Thanks.

tejun

Excerpts from Tejun Heo's message of 2011-03-20 13:44:33 -0400:

Hi Tejun,

I went through a number of benchmarks with the explicit blocking/spinning code and back then it was still significantly faster than the adaptive spin. But, it is definitely worth doing these again, how many dbench procs did you use?

The biggest benefit to explicit spinning is that mutex_lock starts with might_sleep(), so we skip the cond_resched(). Do you have voluntary preempt on?

The long term goal was always to get rid of the blocking locks, I had a lot of code to track the top blockers and we had gotten rid of about 90% of them.

Thanks for looking at this

-chris

Hello, Chris.

It was dbench 50.

Ah, right, I of course forgot to actually attach the .config. I had CONFIG_PREEMPT, not CONFIG_PREEMPT_VOLUNTARY. I'll re-run with VOLUNTARY and see how its behavior changes.

Thanks.

tejun

Hello,

Here are the results with voluntary preemption. I've moved to a beefier machine for testing. It's dual Opteron 2347, so dual socket, eight core. The memory is limited to 1GiB to force IOs and the disk is the same OCZ Vertex 60gig SSD. /proc/stat is captured before and after "dbench 50".

I ran the following four setups.

DFL The current custom locking implementation.
SIMPLE Simple mutex conversion. The first patch in this thread.
SPIN SIMPLE + mutex_tryspin(). The second patch in this thread.
SPIN2 SPIN + mutex_tryspin() in btrfs_tree_lock(). Patch below.

SPIN2 should alleviate the voluntary preemption by might_sleep() in mutex_lock().

       USER   SYSTEM   SIRQ    CXTSW  THROUGHPUT
DFL    49427  458210   1433  7683488     642.947
SIMPLE 52836  471398   1427  3055384     705.369
SPIN   52267  473115   1467  3005603     705.369
SPIN2  52063  470453   1446  3092091     701.826

I'm running DFL again just in case but SIMPLE or SPIN seems to be a much better choice.

Thanks.

---
 fs/btrfs/locking.h |    2 ++
 1 file changed, 2 insertions(+)

Index: work/fs/btrfs/locking.h
===================================================================
@@ -28,6 +28,8 @@ static inline bool btrfs_try_spin_lock(s
 
 static inline void btrfs_tree_lock(struct extent_buffer *eb)
 {
+	if (mutex_tryspin(&eb->lock))
+		return;
 	mutex_lock(&eb->lock);
 }
 

Got 644.176 MB/sec, so yeah the custom locking is definitely worse than just using mutex.

Thanks.

tejun

Excerpts from Tejun Heo's message of 2011-03-21 12:59:55 -0400:

Very interesting. Ok, I'll definitely rerun my benchmarks as well. I used dbench extensively during the initial tuning, but you're forcing the memory low in order to force IO.

This case doesn't really hammer on the locks, it hammers on the transition from spinning to blocking. We want also want to compare dbench entirely in ram, which will hammer on the spinning portion.

-chris

Hello,

Here's re-run of DFL and SIMPLE with the memory restriction lifted. Memory is 4GiB and disk remains mostly idle with all CPUs running full.

       USER   SYSTEM   SIRQ    CXTSW  THROUGHPUT
DFL    59898  504517    377  6814245     782.295
SIMPLE 61090  493441    457  1631688     827.751

So, about the same picture.

Thanks.

tejun

Excerpts from Tejun Heo's message of 2011-03-21 14:11:24 -0400:

Ok, this impact of this is really interesting. If we have very short waits where there is no IO at all, this patch tends to lose. I ran with dbench 10 and got about 20% slower tput.

But, if we do any IO at all it wins by at least that much or more. I think we should take this patch and just work on getting rid of the scheduling with the mutex held where possible.

Tejun, could you please send the mutex_tryspin stuff in? If we can get a sob for that I can send the whole thing.

-chris

Hello, Chris.

I see.

I'm not sure whetehr mutex_tryspin() is justified at this point, and, even if so, how to proceed with it. Maybe we want to make mutex_trylock() perform owner spin by default without introducing a new API.

Given that the difference between SIMPLE and SPIN is small, I think it would be best to simply use mutex_trylock() for now. It's not gonna make much difference either way.

How do you want to proceed? I can prep patches doing the following.

- Convert CONFIG_DEBUG_LOCK_ALLOC to CONFIG_LOCKDEP.

- Drop locking.c and make the lock function simple wrapper around mutex operations. This makes blocking/unblocking noops.

- Remove all blocking/unblocking calls along with the API.

- Remove locking wrappers and use mutex API directly.

What do you think?

Thanks.

tejun

Excerpts from Tejun Heo's message of 2011-03-23 06:46:14 -0400:

I'll benchmark without it, but I think the cond_resched is going to have a pretty big impact. I'm digging up the related benchmarks I used during the initial adaptive spin work.

mutex_trylock is a good start.

I'd like to keep the blocking/unblocking calls for one release. I'd like to finally finish off my patches that do concurrent reads.

I'd also like to keep the wrappers until the concurrent reader locking is done.

Thanks for all the work.

-chris