rwsem: performance optimizations

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +0 -0

new file mode 100644
index 0000000..20fd3f0

include/linux/mcslock.h new file +36 -0

+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*
+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)

We want to add optimistic spinning to rwsems because
the writer rwsem does not perform as well as mutexes. Tim noticed that for exim (mail server) workloads, when reverting commit 4fc3f1d6 and Davidlohr noticed it when converting the i_mmap_mutex to a rwsem in some aim7 workloads. We've noticed that the biggest difference
is when we fail to acquire a mutex in the fastpath, optimistic spinning comes in to play and we can avoid a large amount of unnecessary sleeping and overhead of moving tasks in and out of wait queue.

Allowing optimistic spinning before putting the writer on the wait queue reduces wait queue contention and provided greater chance for the rwsem to get acquired. With these changes, rwsem is on par with mutex.

Reviewed-by Ingo Molnar <[email protected]>

Reviewed-by Peter Zijlstra <[email protected]>

Reviewed-by Peter Hurley <[email protected]>

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/rwsem.h |    6 +-
 kernel/rwsem.c        |   19 +++++-
 lib/rwsem.c           |  203 ++++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 207 insertions(+), 21 deletions(-)

include/linux/rwsem.h +2 -0

index 0616ffe..ef5a83a 100644
@@ -26,6 +26,8 @@ struct rw_semaphore {
 	long			count;
 	raw_spinlock_t		wait_lock;
 	struct list_head	wait_list;
+	struct task_struct	*owner; /* write owner */
+	void			*spin_mlock;

Quoted 4 lines

+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.

A (very) short blurb about what an MCS lock is would be nice here.

Quoted 5 lines · Ingo Molnar

Quoted 4 lines

+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.

Quoted 1 line

A (very) short blurb about what an MCS lock is would be nice here.

A while back I suggested including a link to something like:

http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf

Its a fairly concise write-up of the idea; only 6 pages. The sad part about linking to the web is that links tend to go dead after a while.

Quoted 5 lines · Ingo Molnar

Quoted 4 lines

+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.

Quoted 1 line

A (very) short blurb about what an MCS lock is would be nice here.

A while back I suggested including a link to something like:

http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf

Its a fairly concise write-up of the idea; only 6 pages. The sad part about linking to the web is that links tend to go dead after a while.

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h new file +8 -0

+               return;
+       }
+       ACCESS_ONCE(prev->next) = node;
+       smp_wmb();
+       /* Wait until the lock holder passes the lock down */
+       while (!ACCESS_ONCE(node->locked))
+               arch_mutex_cpu_relax();
+}

Quoted 42 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +24 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;

include/linux/mcslock.h line 30

Quoted 6 lines

include/linux/mcslock.h new file +6 -0

+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 43 lines · Jason Low

Quoted 42 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +24 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;

Quoted 8 lines

include/linux/mcslock.h line 30

Quoted 6 lines

include/linux/mcslock.h new file +6 -0

+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

I don't follow, the whole idea is to spin on the local variable.

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Quoted 54 lines · Jason Low

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 6 lines

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Yes, that's true, but we need to flag the lock as acquired (the node's lock is initially set to unlocked), otherwise others trying to acquire the lock can spin forever:

	/* Wait until the lock holder passes the lock down */
	while (!ACCESS_ONCE(node->locked))
		arch_mutex_cpu_relax();

The ->locked variable in this implementation refers to if the lock is acquired, and *not* to if busy-waiting is necessary.

Quoted 66 lines · Davidlohr Bueso

Quoted 54 lines · Jason Low

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 6 lines

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Yes, that's true, but we need to flag the lock as acquired (the node's lock is initially set to unlocked), otherwise others trying to acquire the lock can spin forever:

Quoted 6 lines

	/* Wait until the lock holder passes the lock down */
	while (!ACCESS_ONCE(node->locked))
		arch_mutex_cpu_relax();

The ->locked variable in this implementation refers to if the lock is acquired, and *not* to if busy-waiting is necessary.

hmm, others threads acquiring the lock will be spinning on their own local nodes, not this node's node->locked. And if prev == NULL, the current thread won't be reading it's node->lock either since we return. So what other thread is going to be reading this node's node->lock?

Thanks,
Jason

Quoted 70 lines · Davidlohr Bueso

Quoted 54 lines · Jason Low

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 6 lines

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Yes, that's true, but we need to flag the lock as acquired (the node's lock is initially set to unlocked), otherwise others trying to acquire the lock can spin forever:

	/* Wait until the lock holder passes the lock down */
	while (!ACCESS_ONCE(node->locked))
		arch_mutex_cpu_relax();

Quoted 2 lines

The ->locked variable in this implementation refers to if the lock is acquired, and *not* to if busy-waiting is necessary.

hmm, others threads acquiring the lock will be spinning on their own local nodes, not this node's node->locked.

And if prev == NULL, the
current thread won't be reading it's node->lock either since we return. So what other thread is going to be reading this node's node->lock?

Thanks,
Jason

Quoted 79 lines · Jason Low

Quoted 66 lines · Davidlohr Bueso

Quoted 54 lines · Jason Low

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 6 lines

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Yes, that's true, but we need to flag the lock as acquired (the node's lock is initially set to unlocked), otherwise others trying to acquire the lock can spin forever:

Quoted 6 lines

	/* Wait until the lock holder passes the lock down */
	while (!ACCESS_ONCE(node->locked))
		arch_mutex_cpu_relax();

The ->locked variable in this implementation refers to if the lock is acquired, and *not* to if busy-waiting is necessary.

hmm, others threads acquiring the lock will be spinning on their own local nodes, not this node's node->locked. And if prev == NULL, the current thread won't be reading it's node->lock either since we return. So what other thread is going to be reading this node's node->lock?

Quoted 2 lines

Thanks,
Jason

I think setting node->locked = 1 for the prev==NULL case is not necessary functionally, but was done for semantics consistency.

Quoted 80 lines · Tim Chen

Quoted 79 lines · Jason Low

Quoted 66 lines · Davidlohr Bueso

Quoted 54 lines · Jason Low

Quoted 53 lines · Davidlohr Bueso

Quoted 51 lines · Jason Low

Quoted 38 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +20 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+       struct mcs_spin_node *next;
+       int               locked;       /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{

include/linux/mcslock.h line 30

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+       struct mcs_spin_node *prev;
+
+       /* Init node */
+       node->locked = 0;
+       node->next   = NULL;
+
+       prev = xchg(lock, node);
+       if (likely(prev == NULL)) {
+               /* Lock acquired */
+               node->locked = 1;

If we don't spin on the local node, is it necessary to set this variable?

Quoted 6 lines

Quoted 1 line

I don't follow, the whole idea is to spin on the local variable.

If prev == NULL, doesn't that mean it won't proceed to spin on the variable because the lock is already free and we call return? In that case where we directly acquire the lock, I was wondering if it is necessary to set node->locked = 1.

Yes, that's true, but we need to flag the lock as acquired (the node's lock is initially set to unlocked), otherwise others trying to acquire the lock can spin forever:

Quoted 6 lines

	/* Wait until the lock holder passes the lock down */
	while (!ACCESS_ONCE(node->locked))
		arch_mutex_cpu_relax();

The ->locked variable in this implementation refers to if the lock is acquired, and *not* to if busy-waiting is necessary.

hmm, others threads acquiring the lock will be spinning on their own local nodes, not this node's node->locked. And if prev == NULL, the current thread won't be reading it's node->lock either since we return. So what other thread is going to be reading this node's node->lock?

Quoted 5 lines

Quoted 2 lines

Thanks,
Jason

I think setting node->locked = 1 for the prev==NULL case is not necessary functionally, but was done for semantics consistency.

Okay, that would makes sense for consistency because we always first set node->lock = 0 at the top of the function.

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
       struct mcs_spin_node *prev;

       /* Init node */
       node->next   = NULL;

       prev = xchg(lock, node);
       if (likely(prev == NULL)) {
               /* Lock acquired */
               return;

       }
       node->locked = 0;
       ACCESS_ONCE(prev->next) = node;
       smp_wmb();
       /* Wait until the lock holder passes the lock down */
       while (!ACCESS_ONCE(node->locked))
               arch_mutex_cpu_relax();
}

Quoted 4 lines

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

I suppose we can save one single assignment. The gain is probably not noticeable as once we set node->next to NULL, node->locked is likely in local cache line and the assignment operation is cheap.

Quoted 5 lines · Tim Chen

Quoted 4 lines

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

Quoted 3 lines

I suppose we can save one single assignment. The gain is probably not noticeable as once we set node->next to NULL, node->locked is likely in local cache line and the assignment operation is cheap.

Would be nice to have this as a separate, add-on patch. Every single instruction removal that has no downside is an upside!

You can add a comment that explains it.

Would be nice to have this as a separate, add-on patch. Every single instruction removal that has no downside is an upside!

You can add a comment that explains it.

checkpatch.pl should really warn about that; and it appears there code in there for that; however:

# grep -C3 smp_mb scripts/checkpatch.pl 

# check for memory barriers without a comment.
                if ($line =~ /\b(mb|rmb|wmb|read_barrier_depends|smp_mb|smp_rmb|smp_wmb|smp_read_barrier_depends)\(/) {
                        if (!ctx_has_comment($first_line, $linenr)) {
                                CHK("MEMORY_BARRIER",
                                    "memory barrier without comment\n" . $herecurr);

# scripts/checkpatch.pl -f kernel/mutex.c 2>&1 | grep memory
#

so that appears to be completely broken :/

Joe, any clue what's up with that?

It's a CHK test, so it's only tested with --strict

$ scripts/checkpatch.pl -f --strict kernel/mutex.c 2>&1 | grep memory
CHECK: memory barrier without comment
CHECK: memory barrier without comment

It could be changed to WARN so it's always on.

Quoted 7 lines · Joe Perches

It's a CHK test, so it's only tested with --strict

$ scripts/checkpatch.pl -f --strict kernel/mutex.c 2>&1 | grep memory
CHECK: memory barrier without comment
CHECK: memory barrier without comment

It could be changed to WARN so it's always on.

Yes please, we can't be too careful with memory barriers.

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Joe Perches

It's a CHK test, so it's only tested with --strict

$ scripts/checkpatch.pl -f --strict kernel/mutex.c 2>&1 | grep memory
CHECK: memory barrier without comment
CHECK: memory barrier without comment

Quoted 3 lines

Quoted 1 line

It could be changed to WARN so it's always on.

Yes please, we can't be too careful with memory barriers.

I'll send the patch separately.

It seems a pretty noisy test.
There are 13 hits just in arch/x86/kernel/

Peter Zijlstra prefers that comments be required near uses of memory barriers.

Change the message level for memory barrier uses from a --strict test only to a normal WARN so it's always emitted.

This might produce false positives around insertions of memory barriers when a comment is outside the patch context block.

And checkpatch is still stupid, it only looks for existence of any comment, not at the comment content.

Suggested-by Peter Zijlstra <[email protected]>

Signed-off-by Joe Perches <[email protected]>

Quoted 9 lines · Joe Perches

Peter Zijlstra prefers that comments be required near uses of memory barriers.

Change the message level for memory barrier uses from a --strict test only to a normal WARN so it's always emitted.

This might produce false positives around insertions of memory barriers when a comment is outside the patch context block.

One would argue that in that case they're too far away in any case :-)

Quoted 2 lines

And checkpatch is still stupid, it only looks for existence of any comment, not at the comment content.

Could we try and alleviate this by giving a slightly more verbose warning?

Maybe something like:

memory barrier without comment; please refer to the pairing barrier and describe the ordering requirements.

That would make it seem as if all barriers are SMP no?

Maybe just refer to Documentation/memory-barriers.txt and/or say something like "please document appropriately"

Quoted 1 line · Joe Perches

That would make it seem as if all barriers are SMP no?

I would think any memory barrier is ordering against someone else; if not smp then a device/hardware -- like for instance the hardware page table walker.

Barriers are fundamentally about order; and order only makes sense if there's more than 1 party to the game.

Quoted 2 lines

Maybe just refer to Documentation/memory-barriers.txt and/or say something like "please document appropriately"

Documentation/memory-barriers.txt is always good; appropriately doesn't seem to quantify anything much at all. Someone might think:

/* */
smp_mb();

appropriate...

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +45 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*

include/linux/mcslock.h new file +3 -0

+}
+
+#endif

kernel/mutex.c +7 -51

index 6d647ae..1b6ba3f 100644
@@ -25,6 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
+#include <linux/mcslock.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,

@@ -111,54 +112,9 @@ EXPORT_SYMBOL(mutex_lock);
  * more or less simultaneously, the spinners need to acquire a MCS lock
  * first before spinning on the owner field.
  *
- * We don't inline mspin_lock() so that perf can correctly account for the
- * time spent in this lock function.
  */
-struct mspin_node {
-	struct mspin_node *next ;
-	int		  locked;	/* 1 if lock acquired */
-};
-#define	MLOCK(mutex)	((struct mspin_node **)&((mutex)->spin_mlock))
 
-static noinline
-void mspin_lock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *prev;
-
-	/* Init node */
-	node->locked = 0;
-	node->next   = NULL;
-
-	prev = xchg(lock, node);
-	if (likely(prev == NULL)) {
-		/* Lock acquired */
-		node->locked = 1;
-		return;
-	}
-	ACCESS_ONCE(prev->next) = node;
-	smp_wmb();
-	/* Wait until the lock holder passes the lock down */
-	while (!ACCESS_ONCE(node->locked))
-		arch_mutex_cpu_relax();
-}
-
-static void mspin_unlock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *next = ACCESS_ONCE(node->next);
-
-	if (likely(!next)) {
-		/*
-		 * Release the lock by setting it to NULL
-		 */
-		if (cmpxchg(lock, node, NULL) == node)
-			return;
-		/* Wait until the next pointer is set */
-		while (!(next = ACCESS_ONCE(node->next)))
-			arch_mutex_cpu_relax();
-	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
-}
+#define	MLOCK(mutex)	((struct mcs_spin_node **)&((mutex)->spin_mlock))
 
 /*
  * Mutex spinning code migrated from kernel/sched/core.c

@@ -448,7 +404,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	for (;;) {
 		struct task_struct *owner;
-		struct mspin_node  node;
+		struct mcs_spin_node  node;
 
 		if (!__builtin_constant_p(ww_ctx == NULL) && ww_ctx->acquired > 0) {
 			struct ww_mutex *ww;

@@ -470,10 +426,10 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
-		mspin_lock(MLOCK(lock), &node);
+		mcs_spin_lock(MLOCK(lock), &node);
 		owner = ACCESS_ONCE(lock->owner);
 		if (owner && !mutex_spin_on_owner(lock, owner)) {
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(MLOCK(lock), &node);
 			goto slowpath;
 		}
 

@@ -488,11 +444,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 			}
 
 			mutex_set_owner(lock);
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(MLOCK(lock), &node);
 			preempt_enable();
 			return 0;
 		}
-		mspin_unlock(MLOCK(lock), &node);
+		mcs_spin_unlock(MLOCK(lock), &node);
 
 		/*
 		 * When there's no owner, we might have preempted between the

Signature · 9 lines

1.7.4.4



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 2 lines

Barriers are fundamentally about order; and order only makes sense if there's more than 1 party to the game.

Oddly enough, there is one exception that proves the rule... On Itanium, suppose we have the following code, with x initially equal to zero:

CPU 1: ACCESS_ONCE(x) = 1;

CPU 2: r1 = ACCESS_ONCE(x); r2 = ACCESS_ONCE(x);

Itanium architects have told me that it really is possible for CPU 2 to see r1==1 and r2==0. Placing a memory barrier between CPU 2's pair of fetches prevents this, but without any other memory barrier to pair with.

Quoted 6 lines · Paul E. McKenney

Quoted 2 lines

Barriers are fundamentally about order; and order only makes sense if there's more than 1 party to the game.

Oddly enough, there is one exception that proves the rule... On Itanium, suppose we have the following code, with x initially equal to zero:

Quoted 7 lines

CPU 1: ACCESS_ONCE(x) = 1;

CPU 2: r1 = ACCESS_ONCE(x); r2 = ACCESS_ONCE(x);

Itanium architects have told me that it really is possible for CPU 2 to see r1=1 and r2=0. Placing a memory barrier between CPU 2's pair of fetches prevents this, but without any other memory barrier to pair with.

Oh man.. its really past time to sink that itanic already.

I suppose it allows the cpu to reorder the reads in its pipeline and the memory barrier disallows this. Curious.. does our memory-barriers.txt file mention this 'fun' fact?

Would be nice to have this as a separate, add-on patch. Every single instruction removal that has no downside is an upside!

Quoted 2 lines · Ingo Molnar

Would be nice to have this as a separate, add-on patch. Every single instruction removal that has no downside is an upside!

Okay, so here is a patch. Tim, would you like to add this to v7?

...
Subject: MCS lock: Remove and reorder unnecessary assignments in mcs_spin_lock()

In mcs_spin_lock(), if (likely(prev == NULL)) is true, then the lock is free and we won't spin on the local node. In that case, we don't have to assign node->locked because it won't be used. We can also move the node->locked = 0 assignment so that it occurs after the if (likely(prev == NULL)) check.

This might also help make it clearer as to how the node->locked variable is used in MCS locks.

Signed-off-by Jason Low <[email protected]>

---
 include/linux/mcslock.h |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)

include/linux/mcslock.h +0 -1

index 20fd3f0..1167d57 100644
@@ -21,15 +21,14 @@ void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
 	struct mcs_spin_node *prev;
 
 	/* Init node */
-	node->locked = 0;
 	node->next   = NULL;
 

Quoted 63 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +45 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*

include/linux/mcslock.h line 55

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();

Shouldn't the memory barrier precede the "ACCESS_ONCE(next->locked) = 1;"? Maybe in an "else" clause of the prior "if" statement, given that the cmpxchg() does it otherwise.

Otherwise, in the case where the "if" conditionn is false, the critical section could bleed out past the unlock.

Quoted 44 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +26 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+

include/linux/mcslock.h line 34

Quoted 8 lines

include/linux/mcslock.h new file +8 -0

+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();

Quoted 11 lines

include/linux/mcslock.h new file +11 -0

+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*

include/linux/mcslock.h line 55

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();

Shouldn't the memory barrier precede the "ACCESS_ONCE(next->locked) = 1;"? Maybe in an "else" clause of the prior "if" statement, given that the cmpxchg() does it otherwise.

Otherwise, in the case where the "if" conditionn is false, the critical section could bleed out past the unlock.

Thanx, Paul

BTW, is the above memory barrier necessary? It seems like the xchg instruction already provided a memory barrier.

Now if we made the changes that Jason suggested:

        /* Init node */

(quoted diff) +1 -2

-       node->locked = 0;
        node->next   = NULL;
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
-               node->locked = 1;
                return;
        }
+       node->locked = 0;
        ACCESS_ONCE(prev->next) = node;
        smp_wmb();

We are probably still okay as other cpus do not read the value of node->locked, which is a local variable.

Quoted 45 lines · Paul E. McKenney

Quoted 44 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +26 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+

Quoted 8 lines

include/linux/mcslock.h line 34

Quoted 8 lines

include/linux/mcslock.h new file +8 -0

+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();

BTW, is the above memory barrier necessary? It seems like the xchg instruction already provided a memory barrier.

Now if we made the changes that Jason suggested:

        /* Init node */

(quoted diff) +1 -2

-       node->locked = 0;
        node->next   = NULL;
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
-               node->locked = 1;
                return;
        }
+       node->locked = 0;
        ACCESS_ONCE(prev->next) = node;
        smp_wmb();

We are probably still okay as other cpus do not read the value of node->locked, which is a local variable.

Tim

Quoted 3 lines

include/linux/mcslock.h line 37

Quoted 3 lines

include/linux/mcslock.h new file +3 -0

+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();

Quoted 23 lines

Quoted 8 lines

include/linux/mcslock.h new file +8 -0

+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*

include/linux/mcslock.h line 55

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();

Shouldn't the memory barrier precede the "ACCESS_ONCE(next->locked) = 1;"? Maybe in an "else" clause of the prior "if" statement, given that the cmpxchg() does it otherwise.

Quoted 5 lines

Otherwise, in the case where the "if" conditionn is false, the critical section could bleed out past the unlock.

Thanx, Paul

Quoted 75 lines · Tim Chen

Quoted 45 lines · Paul E. McKenney

Quoted 44 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +26 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+

Quoted 8 lines

include/linux/mcslock.h line 34

Quoted 8 lines

include/linux/mcslock.h new file +8 -0

+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();

BTW, is the above memory barrier necessary? It seems like the xchg instruction already provided a memory barrier.

Now if we made the changes that Jason suggested:

        /* Init node */

(quoted diff) +1 -2

-       node->locked = 0;
        node->next   = NULL;
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
-               node->locked = 1;
                return;
        }
+       node->locked = 0;
        ACCESS_ONCE(prev->next) = node;
        smp_wmb();

Quoted 2 lines

We are probably still okay as other cpus do not read the value of node->locked, which is a local variable.

I don't immediately see the need for the smp_wmb() in either case.

Quoted 4 lines

Quoted 4 lines

include/linux/mcslock.h line 37

Quoted 4 lines

include/linux/mcslock.h new file +3 -0

+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();

However, you do need a full memory barrier here in order to ensure that you see the effects of the previous lock holder's critical section.

Quoted 76 lines · Paul E. McKenney

Quoted 75 lines · Tim Chen

Quoted 45 lines · Paul E. McKenney

Quoted 44 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c          |   58 +++++-----------------------------------------
 2 files changed, 65 insertions(+), 51 deletions(-)
 create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +26 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+

Quoted 8 lines

include/linux/mcslock.h line 34

Quoted 8 lines

include/linux/mcslock.h new file +8 -0

+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();

BTW, is the above memory barrier necessary? It seems like the xchg instruction already provided a memory barrier.

Now if we made the changes that Jason suggested:

        /* Init node */

(quoted diff) +1 -2

-       node->locked = 0;
        node->next   = NULL;
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
-               node->locked = 1;
                return;
        }
+       node->locked = 0;
        ACCESS_ONCE(prev->next) = node;
        smp_wmb();

Quoted 4 lines

Quoted 2 lines

We are probably still okay as other cpus do not read the value of node->locked, which is a local variable.

I don't immediately see the need for the smp_wmb() in either case.

Thinking a bit more, the following could happen in Jason's initial patch proposal. In this case variable "prev" referenced by CPU1 points to "node" referenced by CPU2

	CPU 1 (calling lock)			CPU 2 (calling unlock)
	ACCESS_ONCE(prev->next) = node
						*next = ACCESS_ONCE(node->next);
						ACCESS_ONCE(next->locked) = 1;
	node->locked = 0;

Then we will be spinning forever on CPU1 as we overwrite the lock passed from CPU2 before we check it. The original code assign "node->locked = 0" before xchg does not have this issue. Doing the following change of moving smp_wmb immediately after node->locked assignment (suggested by Jason)

	node->locked = 0;
	smp_wmb();
	ACCESS_ONCE(prev->next) = node;

could avoid the problem, but will need closer scrutiny to see if there are other pitfalls if wmb happen before

	ACCESS_ONCE(prev->next) = node;

Quoted 6 lines

Quoted 3 lines

Quoted 3 lines

include/linux/mcslock.h line 37

Quoted 3 lines

include/linux/mcslock.h new file +3 -0

+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();

However, you do need a full memory barrier here in order to ensure that you see the effects of the previous lock holder's critical section.

Is it necessary to add a memory barrier after acquiring the lock if the previous lock holder execute smp_wmb before passing the lock?

Quoted 1 line · Joe Perches

That would make it seem as if all barriers are SMP no?

I would think any memory barrier is ordering against someone else; if not smp then a device/hardware -- like for instance the hardware page table walker.

Barriers are fundamentally about order; and order only makes sense if there's more than 1 party to the game.

Yep. The previous lock holder's smp_wmb() won't keep either the compiler or the CPU from reordering things for the new lock holder. They could for example reorder the critical section to precede the node->locked check, which would be very bad.

Quoted 4 lines · Paul E. McKenney

Yep. The previous lock holder's smp_wmb() won't keep either the compiler or the CPU from reordering things for the new lock holder. They could for example reorder the critical section to precede the node->locked check, which would be very bad.

Paul, Tim, Longman,

How would you like the proposed changes below?

---
Subject: [PATCH] MCS: optimizations and barrier corrections

Delete the node->locked = 1 assignment if the lock is free as it won't be used.

Delete the smp_wmb() in mcs_spin_lock() and add a full memory barrier at the end of the mcs_spin_lock() function. As Paul McKenney suggested, "you do need a full memory barrier here in order to ensure that you see the effects of the previous lock holder's critical section." And in the mcs_spin_unlock(), move the memory barrier so that it is before the "ACCESS_ONCE(next->locked) = 1;".

Signed-off-by Jason Low <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 include/linux/mcslock.h |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

include/linux/mcslock.h +1 -2

index 20fd3f0..edd57d2 100644
@@ -26,15 +26,14 @@ void mcs_spin_lock(struct mcs_spin_node **lock,
 struct mcs_spin_node *node)
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
-               /* Lock acquired */
-               node->locked = 1;
+               /* Lock acquired. No need to set node->locked since it

won't be used */

                return;
        }
        ACCESS_ONCE(prev->next) = node;

include/linux/mcslock.h +1 -1

-       smp_wmb();
        /* Wait until the lock holder passes the lock down */
        while (!ACCESS_ONCE(node->locked))
                arch_mutex_cpu_relax();
+       smp_mb();
 }
 
 static void mcs_spin_unlock(struct mcs_spin_node **lock, struct

mcs_spin_node *node)

include/linux/mcslock.h +1 -1

@@ -51,8 +50,8 @@ static void mcs_spin_unlock(struct mcs_spin_node
 **lock, struct mcs_spin_node *n
                while (!(next = ACCESS_ONCE(node->next)))
                        arch_mutex_cpu_relax();
        }
-       ACCESS_ONCE(next->locked) = 1;
        smp_wmb();
+       ACCESS_ONCE(next->locked) = 1;
 }
 

#endif

Quoted 4 lines · Paul E. McKenney

Yep. The previous lock holder's smp_wmb() won't keep either the compiler or the CPU from reordering things for the new lock holder. They could for example reorder the critical section to precede the node->locked check, which would be very bad.

Paul, Tim, Longman,

How would you like the proposed changes below?

---
Subject: [PATCH] MCS: optimizations and barrier corrections

Delete the node->locked = 1 assignment if the lock is free as it won't be used.

Delete the smp_wmb() in mcs_spin_lock() and add a full memory barrier at the end of the mcs_spin_lock() function. As Paul McKenney suggested, "you do need a full memory barrier here in order to ensure that you see the effects of the previous lock holder's critical section." And in the mcs_spin_unlock(), move the memory barrier so that it is before the "ACCESS_ONCE(next->locked) = 1;".

Signed-off-by Jason Low <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 include/linux/mcslock.h |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

include/linux/mcslock.h +1 -2

index 20fd3f0..edd57d2 100644
@@ -26,15 +26,14 @@ void mcs_spin_lock(struct mcs_spin_node **lock,
 struct mcs_spin_node *node)
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
-               /* Lock acquired */
-               node->locked = 1;
+               /* Lock acquired. No need to set node->locked since it

won't be used */

                return;
        }
        ACCESS_ONCE(prev->next) = node;

include/linux/mcslock.h +1 -1

-       smp_wmb();
        /* Wait until the lock holder passes the lock down */
        while (!ACCESS_ONCE(node->locked))
                arch_mutex_cpu_relax();
+       smp_mb();
 }
 
 static void mcs_spin_unlock(struct mcs_spin_node **lock, struct

mcs_spin_node *node)

include/linux/mcslock.h +1 -1

@@ -51,8 +50,8 @@ static void mcs_spin_unlock(struct mcs_spin_node
 **lock, struct mcs_spin_node *n
                while (!(next = ACCESS_ONCE(node->next)))
                        arch_mutex_cpu_relax();
        }
-       ACCESS_ONCE(next->locked) = 1;
        smp_wmb();
+       ACCESS_ONCE(next->locked) = 1;
 }
 

#endif

Signature · 1 line

1.7.1

Quoted 78 lines · Paul E. McKenney

Quoted 63 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Signed-off-by Tim Chen<[email protected]>

Signed-off-by Davidlohr Bueso<[email protected]>

---
  include/linux/mcslock.h |   58 +++++++++++++++++++++++++++++++++++++++++++++++
  kernel/mutex.c          |   58 +++++-----------------------------------------
  2 files changed, 65 insertions(+), 51 deletions(-)

create mode 100644 include/linux/mcslock.h

include/linux/mcslock.h new file +45 -0

new file mode 100644
index 0000000..20fd3f0
@@ -0,0 +1,58 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ */
+#ifndef __LINUX_MCSLOCK_H
+#define __LINUX_MCSLOCK_H
+
+struct mcs_spin_node {
+	struct mcs_spin_node *next;
+	int		  locked;	/* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)
+{
+	struct mcs_spin_node *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*

include/linux/mcslock.h line 55

Quoted 10 lines

include/linux/mcslock.h new file +10 -0

+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();

Shouldn't the memory barrier precede the "ACCESS_ONCE(next->locked) = 1;"? Maybe in an "else" clause of the prior "if" statement, given that the cmpxchg() does it otherwise.

Quoted 2 lines

Otherwise, in the case where the "if" conditionn is false, the critical section could bleed out past the unlock.

Yes, I agree with you that the smp_wmb should be moved before ACCESS_ONCE to prevent critical section from bleeding. Copying Waiman who is the original author of the mcs code to see if he has any comments on things we may have missed.

Tim

Quoted 7 lines · Jason Low

Quoted 4 lines · Paul E. McKenney

Yep. The previous lock holder's smp_wmb() won't keep either the compiler or the CPU from reordering things for the new lock holder. They could for example reorder the critical section to precede the node->locked check, which would be very bad.

Quoted 3 lines

Paul, Tim, Longman,

How would you like the proposed changes below?

Could you point me at what this applies to? I can find flaws looking at random pieces, given a little luck, but at some point I need to look at the whole thing. ;-)

Quoted 7 lines · Peter Zijlstra

Quoted 1 line · Joe Perches

That would make it seem as if all barriers are SMP no?

I would think any memory barrier is ordering against someone else; if not smp then a device/hardware -- like for instance the hardware page table walker.

Quoted 2 lines

Barriers are fundamentally about order; and order only makes sense if there's more than 1 party to the game.

But not necessarily more than 1 kind of parties. It is perfectly possible to have a barrier against other threads running the same function.

Quoted 12 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
         struct mcs_spin_node *prev;

         /* Init node */
         node->locked = 0;
         node->next   = NULL;

Quoted 11 lines

         prev = xchg(lock, node);
         if (likely(prev == NULL)) {
                 /* Lock acquired. No need to set node->locked since it
won't be used */
                 return;
         }
         ACCESS_ONCE(prev->next) = node;
         /* Wait until the lock holder passes the lock down */
         while (!ACCESS_ONCE(node->locked))
                 arch_mutex_cpu_relax();
         smp_mb();

Quoted 7 lines

}

static void mcs_spin_unlock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
         struct mcs_spin_node *next = ACCESS_ONCE(node->next);

Quoted 5 lines

         if (likely(!next)) {
                 /*
                  * Release the lock by setting it to NULL
                  */
                 if (cmpxchg(lock, node, NULL) == node)

Quoted 8 lines

                         return;
                 /* Wait until the next pointer is set */
                 while (!(next = ACCESS_ONCE(node->next)))
                         arch_mutex_cpu_relax();
         }
         smp_wmb();
         ACCESS_ONCE(next->locked) = 1;
}

Quoted 12 lines · Jason Low

Quoted 12 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
         struct mcs_spin_node *prev;

         /* Init node */
         node->locked = 0;
         node->next   = NULL;

Quoted 11 lines

Quoted 11 lines

         prev = xchg(lock, node);
         if (likely(prev == NULL)) {
                 /* Lock acquired. No need to set node->locked since it
won't be used */
                 return;
         }
         ACCESS_ONCE(prev->next) = node;
         /* Wait until the lock holder passes the lock down */
         while (!ACCESS_ONCE(node->locked))
                 arch_mutex_cpu_relax();
         smp_mb();

I wonder if a memory barrier is really needed here.

Quoted 9 lines · Jason Low

Quoted 4 lines · Paul E. McKenney

Yep. The previous lock holder's smp_wmb() won't keep either the compiler or the CPU from reordering things for the new lock holder. They could for example reorder the critical section to precede the node->locked check, which would be very bad.

Paul, Tim, Longman,

Quoted 1 line

How would you like the proposed changes below?

Could you point me at what this applies to? I can find flaws looking at random pieces, given a little luck, but at some point I need to look at the whole thing. ;-)

Thanx, Paul

Quoted 54 lines

---
Subject: [PATCH] MCS: optimizations and barrier corrections

Delete the node->locked = 1 assignment if the lock is free as it won't be used.

Delete the smp_wmb() in mcs_spin_lock() and add a full memory barrier at the end of the mcs_spin_lock() function. As Paul McKenney suggested, "you do need a full memory barrier here in order to ensure that you see the effects of the previous lock holder's critical section." And in the mcs_spin_unlock(), move the memory barrier so that it is before the "ACCESS_ONCE(next->locked) = 1;".

Signed-off-by Jason Low <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 include/linux/mcslock.h |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

include/linux/mcslock.h +1 -2

index 20fd3f0..edd57d2 100644
@@ -26,15 +26,14 @@ void mcs_spin_lock(struct mcs_spin_node **lock,
 struct mcs_spin_node *node)
 
        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
-               /* Lock acquired */
-               node->locked = 1;
+               /* Lock acquired. No need to set node->locked since it

won't be used */

                return;
        }
        ACCESS_ONCE(prev->next) = node;

include/linux/mcslock.h +1 -1

-       smp_wmb();
        /* Wait until the lock holder passes the lock down */
        while (!ACCESS_ONCE(node->locked))
                arch_mutex_cpu_relax();
+       smp_mb();
 }
 
 static void mcs_spin_unlock(struct mcs_spin_node **lock, struct

mcs_spin_node *node)

include/linux/mcslock.h +1 -1

@@ -51,8 +50,8 @@ static void mcs_spin_unlock(struct mcs_spin_node
 **lock, struct mcs_spin_node *n
                while (!(next = ACCESS_ONCE(node->next)))
                        arch_mutex_cpu_relax();
        }
-       ACCESS_ONCE(next->locked) = 1;
        smp_wmb();
+       ACCESS_ONCE(next->locked) = 1;
 }
 

Quoted 4 lines

#endif

Signature · 1 line

1.7.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 24 lines · Waiman Long

Quoted 23 lines · Jason Low

Quoted 23 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
          struct mcs_spin_node *prev;

          /* Init node */
          node->locked = 0;
          node->next   = NULL;

          prev = xchg(lock, node);
          if (likely(prev == NULL)) {
                  /* Lock acquired. No need to set node->locked since it
won't be used */
                  return;
          }
          ACCESS_ONCE(prev->next) = node;
          /* Wait until the lock holder passes the lock down */
          while (!ACCESS_ONCE(node->locked))
                  arch_mutex_cpu_relax();
          smp_mb();

Quoted 1 line

I wonder if a memory barrier is really needed here.

If the compiler can reorder the while (!ACCESS_ONCE(node->locked)) check so that the check occurs after an instruction in the critical section, then the barrier may be necessary.

Quoted 25 lines · Jason Low

Quoted 24 lines · Waiman Long

Quoted 23 lines · Jason Low

Quoted 23 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
          struct mcs_spin_node *prev;

          /* Init node */
          node->locked = 0;
          node->next   = NULL;

          prev = xchg(lock, node);
          if (likely(prev == NULL)) {
                  /* Lock acquired. No need to set node->locked since it
won't be used */
                  return;
          }
          ACCESS_ONCE(prev->next) = node;
          /* Wait until the lock holder passes the lock down */
          while (!ACCESS_ONCE(node->locked))
                  arch_mutex_cpu_relax();
          smp_mb();

Quoted 5 lines

Quoted 1 line

I wonder if a memory barrier is really needed here.

If the compiler can reorder the while (!ACCESS_ONCE(node->locked)) check so that the check occurs after an instruction in the critical section, then the barrier may be necessary.

In that case, just a barrier() call should be enough.

Quoted 31 lines · Waiman Long

Quoted 30 lines · Jason Low

Quoted 24 lines · Waiman Long

Quoted 12 lines · Jason Low

Quoted 12 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
           struct mcs_spin_node *prev;

           /* Init node */
           node->locked = 0;
           node->next   = NULL;

Quoted 11 lines

Quoted 11 lines

           prev = xchg(lock, node);
           if (likely(prev == NULL)) {
                   /* Lock acquired. No need to set node->locked since it
won't be used */
                   return;
           }
           ACCESS_ONCE(prev->next) = node;
           /* Wait until the lock holder passes the lock down */
           while (!ACCESS_ONCE(node->locked))
                   arch_mutex_cpu_relax();
           smp_mb();

Quoted 1 line

I wonder if a memory barrier is really needed here.

If the compiler can reorder the while (!ACCESS_ONCE(node->locked)) check so that the check occurs after an instruction in the critical section, then the barrier may be necessary.

Quoted 1 line

In that case, just a barrier() call should be enough.

The cpu could still be executing out of order load instruction from the critical section before checking node->locked? Probably smp_mb() is still needed.

Tim

Quoted 37 lines · Tim Chen

Quoted 26 lines · Waiman Long

Quoted 25 lines · Jason Low

Quoted 24 lines · Waiman Long

Quoted 23 lines · Jason Low

Quoted 23 lines

Also, below is what the mcs_spin_lock() and mcs_spin_unlock() functions would look like after applying the proposed changes.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
           struct mcs_spin_node *prev;

           /* Init node */
           node->locked = 0;
           node->next   = NULL;

           prev = xchg(lock, node);
           if (likely(prev == NULL)) {
                   /* Lock acquired. No need to set node->locked since it
won't be used */
                   return;
           }
           ACCESS_ONCE(prev->next) = node;
           /* Wait until the lock holder passes the lock down */
           while (!ACCESS_ONCE(node->locked))
                   arch_mutex_cpu_relax();
           smp_mb();

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

I wonder if a memory barrier is really needed here.

If the compiler can reorder the while (!ACCESS_ONCE(node->locked)) check so that the check occurs after an instruction in the critical section, then the barrier may be necessary.

In that case, just a barrier() call should be enough.

The cpu could still be executing out of order load instruction from the critical section before checking node->locked? Probably smp_mb() is still needed.

Quoted 1 line

Tim

But this is the lock function, a barrier() call should be enough to prevent the critical section from creeping up there. We certainly need some kind of memory barrier at the end of the unlock function.

-Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 9 lines · Waiman Long

Quoted 6 lines

The cpu could still be executing out of order load instruction from the critical section before checking node->locked? Probably smp_mb() is still needed.

Tim

But this is the lock function, a barrier() call should be enough to prevent the critical section from creeping up there. We certainly need some kind of memory barrier at the end of the unlock function.

I may be missing something. My understanding is that barrier only prevents the compiler from rearranging instructions, but not for cpu out of order execution (as in smp_mb). So cpu could read memory in the next critical section, before node->locked is true, (i.e. unlock has been completed). If we only have a simple barrier at end of mcs_lock, then say the code on CPU1 is

	mcs_lock
	x = 1;
	...
	x = 2;
	mcs_unlock

and CPU 2 is

	mcs_lock
	y = x;
	...
	mcs_unlock

We expect y to be 2 after the "y = x" assignment. But we we may execute the code as

	CPU1		CPU2
		
	x = 1;
	...		y = x;  ( y=1, out of order load)
	x = 2
	mcs_unlock
			Check node->locked==true
			continue executing critical section (y=1 when we expect y=2)

So we get y to be 1 when we expect that it should be 2. Adding smp_mb after the node->locked check in lock code

            ACCESS_ONCE(prev->next) = node;
            /* Wait until the lock holder passes the lock down */
            while (!ACCESS_ONCE(node->locked))
                     arch_mutex_cpu_relax();
            smp_mb();

should prevent this scenario.

Thanks.
Tim

Quoted 51 lines · Tim Chen

Quoted 9 lines · Waiman Long

Quoted 6 lines

The cpu could still be executing out of order load instruction from the critical section before checking node->locked? Probably smp_mb() is still needed.

Tim

But this is the lock function, a barrier() call should be enough to prevent the critical section from creeping up there. We certainly need some kind of memory barrier at the end of the unlock function.

I may be missing something. My understanding is that barrier only prevents the compiler from rearranging instructions, but not for cpu out of order execution (as in smp_mb). So cpu could read memory in the next critical section, before node->locked is true, (i.e. unlock has been completed). If we only have a simple barrier at end of mcs_lock, then say the code on CPU1 is

	mcs_lock
	x = 1;
	...
	x = 2;
	mcs_unlock

and CPU 2 is

	mcs_lock
	y = x;
	...
	mcs_unlock

We expect y to be 2 after the "y = x" assignment. But we we may execute the code as

	CPU1		CPU2
		
	x = 1;
	...		y = x;  ( y=1, out of order load)
	x = 2
	mcs_unlock
			Check node->locked==true
			continue executing critical section (y=1 when we expect y=2)

So we get y to be 1 when we expect that it should be 2. Adding smp_mb after the node->locked check in lock code

            ACCESS_ONCE(prev->next) = node;
            /* Wait until the lock holder passes the lock down */
            while (!ACCESS_ONCE(node->locked))
                     arch_mutex_cpu_relax();
            smp_mb();

Quoted 4 lines

should prevent this scenario.

Thanks.
Tim

If the lock and unlock functions are done right, there should be no overlap of critical section. So it is job of the lock/unlock functions to make sure that critical section code won't leak out. There should be some kind of memory barrier at the beginning of the lock function and the end of the unlock function.

The critical section also likely to have branches. The CPU may speculatively execute code on the 2 branches, but one of them will be discarded once the branch condition is known. Also arch_mutex_cpu_relax() is a compiler barrier by itself. So we may not need a barrier() after all. The while statement is a branch instruction, any code after that can only be speculatively executed and cannot be committed until the branch is done.

In x86, the smp_mb() function translated to a mfence instruction which cost time. That is why I try to get rid of it if it is not necessary.

Quoted 16 lines · Tim Chen

Okay, that would makes sense for consistency because we always first set node->lock = 0 at the top of the function.

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
        struct mcs_spin_node *prev;

        /* Init node */
        node->next   = NULL;

Quoted 6 lines

        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
                return;
        }
        node->locked = 0;

Quoted 20 lines · Jason Low

Quoted 18 lines · Tim Chen

Okay, that would makes sense for consistency because we always first set node->lock = 0 at the top of the function.

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
        struct mcs_spin_node *prev;

        /* Init node */
        node->next   = NULL;

Quoted 6 lines

Quoted 6 lines

        prev = xchg(lock, node);
        if (likely(prev == NULL)) {
                /* Lock acquired */
                return;
        }
        node->locked = 0;

You can remove the locked flag setting statement inside if (prev == NULL), but you can't clear the locked flag after xchg(). In the interval between xchg() and locked=0, the previous lock owner may come in and set the flag. Now if your clear it, the thread will loop forever. You have to clear it before xchg().

Quoted 7 lines · Waiman Long

If the lock and unlock functions are done right, there should be no overlap of critical section. So it is job of the lock/unlock functions to make sure that critical section code won't leak out. There should be some kind of memory barrier at the beginning of the lock function and the end of the unlock function.

Quoted 7 lines

The critical section also likely to have branches. The CPU may speculatively execute code on the 2 branches, but one of them will be discarded once the branch condition is known. Also arch_mutex_cpu_relax() is a compiler barrier by itself. So we may not need a barrier() after all. The while statement is a branch instruction, any code after that can only be speculatively executed and cannot be committed until the branch is done.

But the condition code may be checked after speculative execution? The condition may not be true during speculative execution and only turns true when we check the condition, and take that branch?

The thing that bothers me is without memory barrier after the while statement, we could speculatively execute before affirming the lock is in acquired state. Then when we check the lock, the lock is set to acquired state in the mean time.
We could be loading some memory entry *before*
the node->locked has been set true. I think a smp_rmb (if not a smp_mb) should be set after the while statement.

Quoted 26 lines · Waiman Long

Quoted 18 lines · Jason Low

Quoted 17 lines · Tim Chen

Okay, that would makes sense for consistency because we always first set node->lock = 0 at the top of the function.

If we prefer to optimize this a bit though, perhaps we can first move the node->lock = 0 so that it gets executed after the "if (likely(prev == NULL)) {}" code block and then delete "node->lock = 1" inside the code block.

static noinline
void mcs_spin_lock(struct mcs_spin_node **lock, struct mcs_spin_node *node)

{
         struct mcs_spin_node *prev;

         /* Init node */
         node->next   = NULL;

Quoted 6 lines

Quoted 6 lines

         prev = xchg(lock, node);
         if (likely(prev == NULL)) {
                 /* Lock acquired */
                 return;
         }
         node->locked = 0;

Quoted 5 lines

You can remove the locked flag setting statement inside if (prev == NULL), but you can't clear the locked flag after xchg(). In the interval between xchg() and locked=0, the previous lock owner may come in and set the flag. Now if your clear it, the thread will loop forever. You have to clear it before xchg().

Yes, in my most recent version, I left locked = 0 in its original place so that the xchg() can act as a barrier for it.

The other option would have been to put another barrier after locked =
0. I went with leaving locked = 0 in its original place so that we don't need that extra barrier.