From: "Jan Beulich" <JBeulich@novell.com>
To: "xen-devel@lists.xensource.com" <xen-devel@lists.xensource.com>
Subject: [PATCH] x86: improve scalability of rwlock implementation
Date: Fri, 25 Mar 2011 17:01:31 +0000 [thread overview]
Message-ID: <4D8CD87B02000078000386FB@vpn.id2.novell.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 5548 bytes --]
>From an abstract perspective, it should be possible to replace normal
spin locks with the write version of rwlocks without correctness
issues. The implementation so far had a very small probability of not
scaling beyond 128 CPUs (which would become more significant if
aforementioned replacement was done), since the sign bit of a 32-bit
integer is being used to determine various conditions, and 129 or more
CPUs simultaneously subtracting RW_LOCK_BIAS from a single lock would
cause an undetected overflow.
Therefore, the bias gets adjusted so that it can cover up to 2048
CPUs, and the lock structure gets widened to account for the unlikely
case of getting built for and run on a system with even more CPUs.
While touching this code, I also used the same .subsection approach
that was already used elsewhere to eliminate taken branches from the
fast paths.
And the output constraints of the affected asm()-s got fixed to use
"+" rather than "=".
Signed-off-by: Jan Beulich <jbeulich@novell.com>
--- a/xen/include/asm-x86/spinlock.h
+++ b/xen/include/asm-x86/spinlock.h
@@ -31,39 +31,67 @@ static always_inline int _raw_spin_trylo
return (oldval > 0);
}
-typedef struct {
+#if NR_CPUS <= 2048
+
+typedef union {
volatile int lock;
+ volatile int write;
+} raw_rwlock_t;
+
+#define RW_LOCK_BIAS 0x00100000
+#define READ_LOCK_SUFFIX "l"
+#define WRITE_LOCK_ADD(n) "addl %" #n ","
+#define WRITE_LOCK_SUB(n) "subl %" #n ","
+#define WRITE_LOCK_CMP(n) "%" #n
+
+#else
+
+typedef union {
+ volatile s64 lock;
+ struct {
+ volatile u32 read;
+ volatile s32 write;
+ };
} raw_rwlock_t;
-#define RW_LOCK_BIAS 0x01000000
+#define RW_LOCK_BIAS (1L << 32)
+#define READ_LOCK_SUFFIX "q"
+#define WRITE_LOCK_ADD(n) "incl"
+#define WRITE_LOCK_SUB(n) "decl"
+#define WRITE_LOCK_CMP(n) "$1"
+
+#endif
+
#define _RAW_RW_LOCK_UNLOCKED /*(raw_rwlock_t)*/ { RW_LOCK_BIAS }
static always_inline void _raw_read_lock(raw_rwlock_t *rw)
{
asm volatile (
- "1: lock; decl %0 \n"
- " jns 3f \n"
- " lock; incl %0 \n"
- "2: rep; nop \n"
- " cmpl $1,%0 \n"
- " js 2b \n"
- " jmp 1b \n"
- "3:"
- : "=m" (rw->lock) : : "memory" );
+ "1: lock; dec" READ_LOCK_SUFFIX " %0\n"
+ " js 3f \n"
+ " .subsection 1 \n"
+ "3: lock; inc" READ_LOCK_SUFFIX " %0\n"
+ "2: rep; nop \n"
+ " cmp" READ_LOCK_SUFFIX " $1,%0 \n"
+ " js 2b \n"
+ " jmp 1b \n"
+ " .subsection 0 \n"
+ : "+m" (rw->lock) : : "memory" );
}
static always_inline void _raw_write_lock(raw_rwlock_t *rw)
{
asm volatile (
- "1: lock; subl %1,%0 \n"
- " jz 3f \n"
- " lock; addl %1,%0 \n"
- "2: rep; nop \n"
- " cmpl %1,%0 \n"
- " jne 2b \n"
- " jmp 1b \n"
- "3:"
- : "=m" (rw->lock) : "i" (RW_LOCK_BIAS) : "memory" );
+ "1: lock; " WRITE_LOCK_SUB(1) " %0\n"
+ " jnz 3f \n"
+ " .subsection 1 \n"
+ "3: lock; " WRITE_LOCK_ADD(1) " %0\n"
+ "2: rep; nop \n"
+ " cmpl " WRITE_LOCK_CMP(1) ", %0\n"
+ " jne 2b \n"
+ " jmp 1b \n"
+ " .subsection 0 \n"
+ : "+m" (rw->write) : "i" (RW_LOCK_BIAS) : "memory" );
}
static always_inline int _raw_write_trylock(raw_rwlock_t *rw)
@@ -71,12 +99,12 @@ static always_inline int _raw_write_tryl
int rc;
asm volatile (
- " lock; subl %2,%0 \n"
- " jz 1f \n"
- " lock; addl %2,%0 \n"
- " dec %1 \n"
+ " lock; " WRITE_LOCK_SUB(2) " %0\n"
+ " jz 1f \n"
+ " lock; " WRITE_LOCK_ADD(2) " %0\n"
+ " dec %1 \n"
"1:"
- : "=m" (rw->lock), "=r" (rc) : "i" (RW_LOCK_BIAS), "1" (1)
+ : "+m" (rw->write), "=r" (rc) : "i" (RW_LOCK_BIAS), "1" (1)
: "memory" );
return rc;
@@ -85,18 +113,24 @@ static always_inline int _raw_write_tryl
static always_inline void _raw_read_unlock(raw_rwlock_t *rw)
{
asm volatile (
- "lock ; incl %0"
- : "=m" ((rw)->lock) : : "memory" );
+ " lock ; inc" READ_LOCK_SUFFIX " %0"
+ : "+m" (rw->lock) : : "memory" );
}
static always_inline void _raw_write_unlock(raw_rwlock_t *rw)
{
asm volatile (
- "lock ; addl %1,%0"
- : "=m" ((rw)->lock) : "i" (RW_LOCK_BIAS) : "memory" );
+ " lock ; " WRITE_LOCK_ADD(1) " %0"
+ : "+m" (rw->write) : "i" (RW_LOCK_BIAS) : "memory" );
}
#define _raw_rw_is_locked(x) ((x)->lock < RW_LOCK_BIAS)
-#define _raw_rw_is_write_locked(x) ((x)->lock <= 0)
+#define _raw_rw_is_write_locked(x) ((x)->write <= 0)
+
+#undef READ_LOCK_SUFFIX
+#undef WRITE_LOCK_ADD
+#undef WRITE_LOCK_SUB
+#undef WRITE_LOCK_CMP
+
#endif /* __ASM_SPINLOCK_H */
[-- Attachment #2: x86-rwlock-scalability.patch --]
[-- Type: text/plain, Size: 5544 bytes --]
>From an abstract perspective, it should be possible to replace normal
spin locks with the write version of rwlocks without correctness
issues. The implementation so far had a very small probability of not
scaling beyond 128 CPUs (which would become more significant if
aforementioned replacement was done), since the sign bit of a 32-bit
integer is being used to determine various conditions, and 129 or more
CPUs simultaneously subtracting RW_LOCK_BIAS from a single lock would
cause an undetected overflow.
Therefore, the bias gets adjusted so that it can cover up to 2048
CPUs, and the lock structure gets widened to account for the unlikely
case of getting built for and run on a system with even more CPUs.
While touching this code, I also used the same .subsection approach
that was already used elsewhere to eliminate taken branches from the
fast paths.
And the output constraints of the affected asm()-s got fixed to use
"+" rather than "=".
Signed-off-by: Jan Beulich <jbeulich@novell.com>
--- a/xen/include/asm-x86/spinlock.h
+++ b/xen/include/asm-x86/spinlock.h
@@ -31,39 +31,67 @@ static always_inline int _raw_spin_trylo
return (oldval > 0);
}
-typedef struct {
+#if NR_CPUS <= 2048
+
+typedef union {
volatile int lock;
+ volatile int write;
+} raw_rwlock_t;
+
+#define RW_LOCK_BIAS 0x00100000
+#define READ_LOCK_SUFFIX "l"
+#define WRITE_LOCK_ADD(n) "addl %" #n ","
+#define WRITE_LOCK_SUB(n) "subl %" #n ","
+#define WRITE_LOCK_CMP(n) "%" #n
+
+#else
+
+typedef union {
+ volatile s64 lock;
+ struct {
+ volatile u32 read;
+ volatile s32 write;
+ };
} raw_rwlock_t;
-#define RW_LOCK_BIAS 0x01000000
+#define RW_LOCK_BIAS (1L << 32)
+#define READ_LOCK_SUFFIX "q"
+#define WRITE_LOCK_ADD(n) "incl"
+#define WRITE_LOCK_SUB(n) "decl"
+#define WRITE_LOCK_CMP(n) "$1"
+
+#endif
+
#define _RAW_RW_LOCK_UNLOCKED /*(raw_rwlock_t)*/ { RW_LOCK_BIAS }
static always_inline void _raw_read_lock(raw_rwlock_t *rw)
{
asm volatile (
- "1: lock; decl %0 \n"
- " jns 3f \n"
- " lock; incl %0 \n"
- "2: rep; nop \n"
- " cmpl $1,%0 \n"
- " js 2b \n"
- " jmp 1b \n"
- "3:"
- : "=m" (rw->lock) : : "memory" );
+ "1: lock; dec" READ_LOCK_SUFFIX " %0\n"
+ " js 3f \n"
+ " .subsection 1 \n"
+ "3: lock; inc" READ_LOCK_SUFFIX " %0\n"
+ "2: rep; nop \n"
+ " cmp" READ_LOCK_SUFFIX " $1,%0 \n"
+ " js 2b \n"
+ " jmp 1b \n"
+ " .subsection 0 \n"
+ : "+m" (rw->lock) : : "memory" );
}
static always_inline void _raw_write_lock(raw_rwlock_t *rw)
{
asm volatile (
- "1: lock; subl %1,%0 \n"
- " jz 3f \n"
- " lock; addl %1,%0 \n"
- "2: rep; nop \n"
- " cmpl %1,%0 \n"
- " jne 2b \n"
- " jmp 1b \n"
- "3:"
- : "=m" (rw->lock) : "i" (RW_LOCK_BIAS) : "memory" );
+ "1: lock; " WRITE_LOCK_SUB(1) " %0\n"
+ " jnz 3f \n"
+ " .subsection 1 \n"
+ "3: lock; " WRITE_LOCK_ADD(1) " %0\n"
+ "2: rep; nop \n"
+ " cmpl " WRITE_LOCK_CMP(1) ", %0\n"
+ " jne 2b \n"
+ " jmp 1b \n"
+ " .subsection 0 \n"
+ : "+m" (rw->write) : "i" (RW_LOCK_BIAS) : "memory" );
}
static always_inline int _raw_write_trylock(raw_rwlock_t *rw)
@@ -71,12 +99,12 @@ static always_inline int _raw_write_tryl
int rc;
asm volatile (
- " lock; subl %2,%0 \n"
- " jz 1f \n"
- " lock; addl %2,%0 \n"
- " dec %1 \n"
+ " lock; " WRITE_LOCK_SUB(2) " %0\n"
+ " jz 1f \n"
+ " lock; " WRITE_LOCK_ADD(2) " %0\n"
+ " dec %1 \n"
"1:"
- : "=m" (rw->lock), "=r" (rc) : "i" (RW_LOCK_BIAS), "1" (1)
+ : "+m" (rw->write), "=r" (rc) : "i" (RW_LOCK_BIAS), "1" (1)
: "memory" );
return rc;
@@ -85,18 +113,24 @@ static always_inline int _raw_write_tryl
static always_inline void _raw_read_unlock(raw_rwlock_t *rw)
{
asm volatile (
- "lock ; incl %0"
- : "=m" ((rw)->lock) : : "memory" );
+ " lock ; inc" READ_LOCK_SUFFIX " %0"
+ : "+m" (rw->lock) : : "memory" );
}
static always_inline void _raw_write_unlock(raw_rwlock_t *rw)
{
asm volatile (
- "lock ; addl %1,%0"
- : "=m" ((rw)->lock) : "i" (RW_LOCK_BIAS) : "memory" );
+ " lock ; " WRITE_LOCK_ADD(1) " %0"
+ : "+m" (rw->write) : "i" (RW_LOCK_BIAS) : "memory" );
}
#define _raw_rw_is_locked(x) ((x)->lock < RW_LOCK_BIAS)
-#define _raw_rw_is_write_locked(x) ((x)->lock <= 0)
+#define _raw_rw_is_write_locked(x) ((x)->write <= 0)
+
+#undef READ_LOCK_SUFFIX
+#undef WRITE_LOCK_ADD
+#undef WRITE_LOCK_SUB
+#undef WRITE_LOCK_CMP
+
#endif /* __ASM_SPINLOCK_H */
[-- Attachment #3: Type: text/plain, Size: 138 bytes --]
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel
reply other threads:[~2011-03-25 17:01 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4D8CD87B02000078000386FB@vpn.id2.novell.com \
--to=jbeulich@novell.com \
--cc=xen-devel@lists.xensource.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).