linux-kernel - [not-a-PATCH 2/2] futex: eliminate instruction from hash

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1434978981-12831-2-git-send-email-linux@rasmusvillemoes.dk>
Date:	Mon, 22 Jun 2015 15:16:19 +0200
From:	Rasmus Villemoes <linux@...musvillemoes.dk>
To:	Andrew Morton <akpm@...ux-foundation.org>,
	Richard Weinberger <richard@....at>,
	"Peter Zijlstra (Intel)" <peterz@...radead.org>,
	Andy Lutomirski <luto@...capital.net>,
	Darren Hart <darren@...art.com>,
	Oleg Nesterov <oleg@...hat.com>,
	Michael Kerrisk <mtk.manpages@...il.com>
Cc:	Rasmus Villemoes <linux@...musvillemoes.dk>,
	linux-kernel@...r.kernel.org
Subject: [not-a-PATCH 2/2] futex: eliminate instruction from hash_futex

After initialization, futex_hashsize is only used in hash_futex, where
we subtract 1 to get the proper mask. So store that mask instead.

Or not: Unfortunately, this causes gcc to emit an 'and with memory op'
instead of doing a load which can happen at least somewhat in parallel
with the last few instructions computing hash, as this diff shows:

-:      48 8b 15 a5 61 e4 00    mov    0xe461a5(%rip),%rdx        # ffffffff81eff9f8 <__futex_data+0x8>
 :      31 c8                   xor    %ecx,%eax
 :      c1 c9 08                ror    $0x8,%ecx
 :      29 c8                   sub    %ecx,%eax
-:      48 83 ea 01             sub    $0x1,%rdx
-:      48 21 d0                and    %rdx,%rax
+:      23 05 9f 61 e4 00       and    0xe4619f(%rip),%eax        # ffffffff81eff9f8 <__futex_data+0x8>
 :      48 c1 e0 06             shl    $0x6,%rax
-:      48 03 05 84 61 e4 00    add    0xe46184(%rip),%rax        # ffffffff81eff9f0 <__futex_data>
+:      48 03 05 8c 61 e4 00    add    0xe4618c(%rip),%rax        # ffffffff81eff9f0 <__futex_data>
 :      c3                      retq

Not-signed-off-by: Rasmus Villemoes <linux@...musvillemoes.dk>
---
 kernel/futex.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index c5f33bf78293..22865bcbcae8 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -255,16 +255,16 @@ struct futex_hash_bucket {
 } ____cacheline_aligned_in_smp;
 
 /*
- * The base of the bucket array and its size are always used together
+ * The base of the bucket array and the mask are always used together
  * (after initialization only in hash_futex()), so ensure that they
  * reside in the same cacheline.
  */
 static struct {
 	struct futex_hash_bucket *queues;
-	unsigned long            hashsize;
+	u32                      mask;
 } __futex_data __read_mostly __aligned(16);
 #define futex_queues   (__futex_data.queues)
-#define futex_hashsize (__futex_data.hashsize)
+#define futex_hashmask (__futex_data.mask)
 
 
 static inline void futex_get_mm(union futex_key *key)
@@ -320,7 +320,7 @@ static struct futex_hash_bucket *hash_futex(union futex_key *key)
 	u32 hash = jhash2((u32*)&key->both.word,
 			  (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
 			  key->both.offset);
-	return &futex_queues[hash & (futex_hashsize - 1)];
+	return &futex_queues[hash & futex_hashmask];
 }
 
 /*
@@ -3035,6 +3035,7 @@ static int __init futex_init(void)
 {
 	unsigned int futex_shift;
 	unsigned long i;
+	unsigned long futex_hashsize;
 
 #if CONFIG_BASE_SMALL
 	futex_hashsize = 16;
@@ -3045,7 +3046,7 @@ static int __init futex_init(void)
 	futex_queues = alloc_large_system_hash("futex", sizeof(*futex_queues),
 					       futex_hashsize, 0,
 					       futex_hashsize < 256 ? HASH_SMALL : 0,
-					       &futex_shift, NULL,
+					       &futex_shift, &futex_hashmask,
 					       futex_hashsize, futex_hashsize);
 	futex_hashsize = 1UL << futex_shift;
 
-- 
2.1.3

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
Please read the FAQ at  http://www.tux.org/lkml/