| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20190328181106.22887-11-longman@redhat.com>
Date: Thu, 28 Mar 2019 14:11:04 -0400
From: Waiman Long <longman@...hat.com>
To: Peter Zijlstra <peterz@...radead.org>,
Ingo Molnar <mingo@...hat.com>,
Will Deacon <will.deacon@....com>,
Thomas Gleixner <tglx@...utronix.de>
Cc: linux-kernel@...r.kernel.org, x86@...nel.org,
Davidlohr Bueso <dave@...olabs.net>,
Linus Torvalds <torvalds@...ux-foundation.org>,
Tim Chen <tim.c.chen@...ux.intel.com>,
Waiman Long <longman@...hat.com>
Subject: [PATCH 10/12] locking/rwsem: Merge owner into count on x86-64
With separate count and owner, there are timing windows where the two
values are inconsistent. That can cause problem when trying to figure
out the exact state of the rwsem. For instance, a RT task will stop
optimistic spinning if the lock is acquired by a writer but the owner
field isn't set yet. That can be solved by combining the count and
owner together in a single atomic value.
On 32-bit architectures, there aren't enough bits to hold both.
64-bit architectures, however, can have enough bits to do that. For
x86-64, the physical address can use up to 52 bits. That is 4PB of
memory. That leaves 12 bits available for other use. The task structure
pointer is aligned to the L1 cache size. That means another 6 bits (64
bytes cacheline) will be available. Reserving 2 bits for status flags,
we will have 16 bits for the reader count. That can supports up to
(64k-1) readers.
The owner value will still be duplicated in the owner field as that
will ease debugging when looking at core dump.
This change is currently enabled for x86-64 only. Other 64-bit
architectures may be enabled in the future if the need arises.
With a locking microbenchmark running on 5.1 based kernel, the total
locking rates (in kops/s) on a 8-socket IvyBridge-EX system with
writer-only locking threads and then equal numbers of readers and writers
(mixed) before patch and after this and subsequent related patches were
as follows:
Before Patch After Patch
# of Threads wlock mixed wlock mixed
------------ ----- ----- ----- -----
1 30,422 31,034 30,323 30,379
2 6,427 6,684 7,804 9,436
4 6,742 6,738 7,568 8,268
8 7,092 7,222 5,679 7,041
16 6,882 7,163 6,848 7,652
32 7,458 7,316 7,975 2,189
64 7,906 520 8,269 534
128 1,680 425 8,047 448
In the single thread case, the complex write-locking operation does
introduce a little bit of overhead (about 0.3%). For the contended cases,
except for some anomalies in the data, there is no evidence that this
change will adversely impact performance.
When running the same microbenchmark with RT locking threads instead,
we got the following results:
Before Patch After Patch
# of Threads wlock mixed wlock mixed
------------ ----- ----- ----- -----
2 4,065 3,642 4,756 5,062
4 2,254 1,907 3,460 2,496
8 2,386 964 3,012 1,964
16 2,095 1,596 3,083 1,862
32 2,388 530 3,717 359
64 1,424 322 4,060 401
128 1,642 510 4,488 628
It is obvious that RT tasks can benefit pretty significantly with this set
of patches.
Signed-off-by: Waiman Long <longman@...hat.com>
---
kernel/locking/rwsem-xadd.c | 11 +++-
kernel/locking/rwsem.h | 117 ++++++++++++++++++++++++++++++++----
2 files changed, 114 insertions(+), 14 deletions(-)
diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index 79d52624a00d..8d352c375e60 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -26,11 +26,11 @@
/*
* Guide to the rw_semaphore's count field.
*
- * When the RWSEM_WRITER_LOCKED bit in count is set, the lock is owned
- * by a writer.
+ * When any of the RWSEM_WRITER_MASK bits in count is set, the lock is
+ * owned by a writer.
*
* The lock is owned by readers when
- * (1) the RWSEM_WRITER_LOCKED isn't set in count,
+ * (1) none of the RWSEM_WRITER_MASK bits is set in count,
* (2) some of the reader bits are set in count, and
* (3) the owner field has RWSEM_READ_OWNED bit set.
*
@@ -46,6 +46,11 @@
void __init_rwsem(struct rw_semaphore *sem, const char *name,
struct lock_class_key *key)
{
+ /*
+ * We should support at least (4k-1) concurrent readers
+ */
+ BUILD_BUG_ON(sizeof(long) * 8 - RWSEM_READER_SHIFT < 12);
+
#ifdef CONFIG_DEBUG_LOCK_ALLOC
/*
* Make sure we are not reinitializing a held semaphore:
diff --git a/kernel/locking/rwsem.h b/kernel/locking/rwsem.h
index 789e8d270260..f7449e82a9da 100644
--- a/kernel/locking/rwsem.h
+++ b/kernel/locking/rwsem.h
@@ -41,25 +41,80 @@
#endif
/*
- * The definition of the atomic counter in the semaphore:
+ * Enable the merging of owner into count for x86_64 only.
+ */
+#ifdef CONFIG_X86_64
+#define RWSEM_MERGE_OWNER_TO_COUNT
+#endif
+
+/*
+ * With separate count and owner, there are timing windows where the two
+ * values are inconsistent. That can cause problem when trying to figure
+ * out the exact state of the rwsem. That can be solved by combining
+ * the count and owner together in a single atomic value.
+ *
+ * On 64-bit architectures, the owner task structure pointer can be
+ * compressed and combined with reader count and other status flags.
+ * A simple compression method is to map the virtual address back to
+ * the physical address by subtracting PAGE_OFFSET. On 32-bit
+ * architectures, the long integer value just isn't big enough for
+ * combining owner and count. So they remain separate.
+ *
+ * For x86-64, the physical address can use up to 52 bits. That is 4PB
+ * of memory. That leaves 12 bits available for other use. The task
+ * structure pointer is also aligned to the L1 cache size. That means
+ * another 6 bits (64 bytes cacheline) will be available. Reserving
+ * 2 bits for status flags, we will have 16 bits for the reader count.
+ * That can supports up to (64k-1) readers.
+ *
+ * On x86-64, the bit definitions of the count are:
+ *
+ * Bit 0 - waiters present bit
+ * Bit 1 - lock handoff bit
+ * Bits 2-47 - compressed task structure pointer
+ * Bits 48-63 - 16-bit reader counts
+ *
+ * On other 64-bit architectures, the bit definitions are:
*
- * Bit 0 - writer locked bit
- * Bit 1 - waiters present bit
- * Bit 2 - lock handoff bit
- * Bits 3-7 - reserved
- * Bits 8-X - 24-bit (32-bit) or 56-bit reader count
+ * Bit 0 - waiters present bit
+ * Bit 1 - lock handoff bit
+ * Bits 2-6 - reserved
+ * Bit 7 - writer lock bit
+ * Bits 8-63 - 56-bit reader counts
+ *
+ * On 32-bit architectures, the bit definitions of the count are:
+ *
+ * Bit 0 - waiters present bit
+ * Bit 1 - lock handoff bit
+ * Bits 2-6 - reserved
+ * Bit 7 - writer lock bit
+ * Bits 8-31 - 24-bit reader counts
*
* atomic_long_fetch_add() is used to obtain reader lock, whereas
* atomic_long_cmpxchg() will be used to obtain writer lock.
*/
-#define RWSEM_WRITER_LOCKED (1UL << 0)
-#define RWSEM_FLAG_WAITERS (1UL << 1)
-#define RWSEM_FLAG_HANDOFF (1UL << 2)
+#define RWSEM_FLAG_WAITERS (1UL << 0)
+#define RWSEM_FLAG_HANDOFF (1UL << 1)
+
+#ifdef RWSEM_MERGE_OWNER_TO_COUNT
+
+#ifdef __PHYSICAL_MASK_SHIFT
+#define RWSEM_PA_MASK_SHIFT __PHYSICAL_MASK_SHIFT
+#else
+#define RWSEM_PA_MASK_SHIFT 52
+#endif
+#define RWSEM_READER_SHIFT (RWSEM_PA_MASK_SHIFT - L1_CACHE_SHIFT + 2)
+#define RWSEM_WRITER_MASK ((1UL << RWSEM_READER_SHIFT) - 4)
+#define RWSEM_WRITER_LOCKED rwsem_owner_count(current)
+#else /* RWSEM_MERGE_OWNER_TO_COUNT */
+#define RWSEM_WRITER_MASK (1UL << 7)
#define RWSEM_READER_SHIFT 8
+#define RWSEM_WRITER_LOCKED RWSEM_WRITER_MASK
+#endif /* RWSEM_MERGE_OWNER_TO_COUNT */
+
#define RWSEM_READER_BIAS (1UL << RWSEM_READER_SHIFT)
#define RWSEM_READER_MASK (~(RWSEM_READER_BIAS - 1))
-#define RWSEM_WRITER_MASK RWSEM_WRITER_LOCKED
#define RWSEM_LOCK_MASK (RWSEM_WRITER_MASK|RWSEM_READER_MASK)
#define RWSEM_READ_FAILED_MASK (RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS|\
RWSEM_FLAG_HANDOFF)
@@ -72,6 +127,22 @@
#define RWSEM_COUNT_WLOCKED_OR_HANDOFF(c) \
((c) & (RWSEM_WRITER_MASK | RWSEM_FLAG_HANDOFF))
+/*
+ * Task structure pointer compression (64-bit only):
+ * (owner - PAGE_OFFSET) >> (L1_CACHE_SHIFT - 2)
+ */
+static inline unsigned long rwsem_owner_count(struct task_struct *owner)
+{
+ return ((unsigned long)owner - PAGE_OFFSET) >> (L1_CACHE_SHIFT - 2);
+}
+
+static inline unsigned long rwsem_count_owner(long count)
+{
+ unsigned long writer = (unsigned long)count & RWSEM_WRITER_MASK;
+
+ return writer ? (writer << (L1_CACHE_SHIFT - 2)) + PAGE_OFFSET : 0;
+}
+
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
/*
* All writes to owner are protected by WRITE_ONCE() to make sure that
@@ -79,7 +150,12 @@
* the owner value concurrently without lock. Read from owner, however,
* may not need READ_ONCE() as long as the pointer value is only used
* for comparison and isn't being dereferenced.
+ *
+ * On 32-bit architectures, the owner and count are separate. On 64-bit
+ * architectures, however, the writer task structure pointer is written
+ * to the count as well in addition to the owner field.
*/
+
static inline void rwsem_set_owner(struct rw_semaphore *sem)
{
WRITE_ONCE(sem->owner, current);
@@ -90,10 +166,26 @@ static inline void rwsem_clear_owner(struct rw_semaphore *sem)
WRITE_ONCE(sem->owner, NULL);
}
+#ifdef RWSEM_MERGE_OWNER_TO_COUNT
+/*
+ * Get the owner value from count to have early access to the task structure.
+ * Owner from sem->count should includes the RWSEM_ANONYMOUSLY_OWNED bit
+ * from sem->owner.
+ */
+static inline struct task_struct *rwsem_get_owner(struct rw_semaphore *sem)
+{
+ unsigned long cowner = rwsem_count_owner(atomic_long_read(&sem->count));
+ unsigned long sowner = (unsigned long)READ_ONCE(sem->owner);
+
+ return (struct task_struct *) (cowner
+ ? cowner | (sowner & RWSEM_ANONYMOUSLY_OWNED) : sowner);
+}
+#else /* !RWSEM_MERGE_OWNER_TO_COUNT */
static inline struct task_struct *rwsem_get_owner(struct rw_semaphore *sem)
{
return READ_ONCE(sem->owner);
}
+#endif /* RWSEM_MERGE_OWNER_TO_COUNT */
/*
* The task_struct pointer of the last owning reader will be left in
@@ -285,6 +377,9 @@ static inline void __down_write(struct rw_semaphore *sem)
RWSEM_WRITER_LOCKED)))
rwsem_down_write_failed(sem);
rwsem_set_owner(sem);
+#ifdef RWSEM_MERGE_OWNER_TO_COUNT
+ DEBUG_RWSEMS_WARN_ON(sem->owner != rwsem_get_owner(sem), sem);
+#endif
}
static inline int __down_write_killable(struct rw_semaphore *sem)
@@ -335,7 +430,7 @@ static inline void __up_write(struct rw_semaphore *sem)
DEBUG_RWSEMS_WARN_ON(sem->owner != current, sem);
rwsem_clear_owner(sem);
- tmp = atomic_long_fetch_add_release(-RWSEM_WRITER_LOCKED, &sem->count);
+ tmp = atomic_long_fetch_and_release(~RWSEM_WRITER_MASK, &sem->count);
if (unlikely(tmp & RWSEM_FLAG_WAITERS))
rwsem_wake(sem, tmp);
}
--
2.18.1
Powered by blists - more mailing lists