spin_lock: add cross cache lines checking

Modern x86 CPU won't hold whole memory bus when executing 'lock' prefixed instructions unless the instruction destination is crossing 2 cache lines. If so, it is disaster of system performance.

Actually if the lock is not in the 'packed' structure, gcc places it safely under x86 arch. But seems add this checking in CONFIG_DEBUG_LOCK_ALLOC is harmless.

btw, change SPIN_BUG_ON macro a little for style complain.

Inspired-by Andi Kleen <[email protected]>

Signed-off-by Alex Shi <[email protected]>

---

arch/x86/include/asm/cache.h +2 -0

index 48f99f1..79d146e 100644
@@ -7,6 +7,8 @@
 #define L1_CACHE_SHIFT	(CONFIG_X86_L1_CACHE_SHIFT)
 #define L1_CACHE_BYTES	(1 << L1_CACHE_SHIFT)
 
+#define L1_CACHE_SIZE_MASK	(~(L1_CACHE_BYTES - 1)UL)
+
 #define __read_mostly __attribute__((__section__(".data..read_mostly")))
 
 #define INTERNODE_CACHE_SHIFT CONFIG_X86_INTERNODE_CACHE_SHIFT

include/asm-generic/cache.h +2 -0

index 1bfcfe5..244e528 100644
@@ -9,4 +9,6 @@
 #define L1_CACHE_SHIFT		5
 #define L1_CACHE_BYTES		(1 << L1_CACHE_SHIFT)
 
+#define L1_CACHE_SIZE_MASK     (~(L1_CACHE_BYTES - 1)UL)
+
 #endif /* __ASM_GENERIC_CACHE_H */

lib/spinlock_debug.c +10 -2

index 5f3eacd..554dcda 100644
@@ -13,6 +13,12 @@
 #include <linux/delay.h>
 #include <linux/module.h>
 
+#define SPIN_BUG_ON(cond, lock, msg) {if (unlikely(cond)) spin_bug(lock, msg); }
+
+#define is_cross_lines(p)						\
+	(((unsigned long)(p) & L1_CACHE_SIZE_MASK) !=			\
+	(((unsigned long)(p) + sizeof(*p) - 1) & L1_CACHE_SIZE_MASK))	\
+
 void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name,
 			  struct lock_class_key *key)
 {

@@ -22,6 +28,8 @@ void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name,
 	 */
 	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
 	lockdep_init_map(&lock->dep_map, name, key, 0);
+	SPIN_BUG_ON(is_cross_lines(lock->raw_lock), lock,
+			"!!! the lock cross cache lines !!!");
 #endif
 	lock->raw_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
 	lock->magic = SPINLOCK_MAGIC;

@@ -40,6 +48,8 @@ void __rwlock_init(rwlock_t *lock, const char *name,
 	 */
 	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
 	lockdep_init_map(&lock->dep_map, name, key, 0);
+	SPIN_BUG_ON(is_cross_lines(lock->raw_lock), lock,
+			"!!! the lock cross cache lines !!!");
 #endif
 	lock->raw_lock = (arch_rwlock_t) __ARCH_RW_LOCK_UNLOCKED;
 	lock->magic = RWLOCK_MAGIC;

@@ -75,8 +85,6 @@ static void spin_bug(raw_spinlock_t *lock, const char *msg)
 	spin_dump(lock, msg);
 }
 
-#define SPIN_BUG_ON(cond, lock, msg) if (unlikely(cond)) spin_bug(lock, msg)
-
 static inline void
 debug_spin_lock_before(raw_spinlock_t *lock)
 {

Oops.
Sorry, the patch is not tested well! will update it later.

From 28745c1970a61a1420d388660cd9dcc619cd38ba Mon Sep 17 00:00:00 2001

Quoted 2 lines · Alex Shi

Oops.
Sorry, the patch is not tested well! will update it later.

corrected version:
==========

Quoted 1 line

From 28745c1970a61a1420d388660cd9dcc619cd38ba Mon Sep 17 00:00:00 2001

From: Alex Shi <[email protected]>
Date: Mon, 5 Mar 2012 13:03:35 +0800
Subject: [PATCH] lockdep: add cross cache lines checking

Modern x86 CPU won't hold whole memory bus when executing 'lock' prefixed instructions unless the instruction destination is crossing 2 cache lines. If so, it is disaster of system performance.

Actually if the lock is not in the 'packed' structure, gcc places it safely under x86 arch. But seems add this checking in CONFIG_DEBUG_LOCK_ALLOC is harmless.

Inspired-by Andi Kleen <[email protected]>

Signed-off-by Alex Shi <[email protected]>

---
 arch/x86/include/asm/cache.h |    2 +
 include/asm-generic/cache.h  |    2 +
 lib/spinlock_debug.c         |   76 ++++++++++++++++++++++-------------------
 3 files changed, 45 insertions(+), 35 deletions(-)

arch/x86/include/asm/cache.h +2 -0

index 48f99f1..63c2316 100644
@@ -7,6 +7,8 @@
 #define L1_CACHE_SHIFT	(CONFIG_X86_L1_CACHE_SHIFT)
 #define L1_CACHE_BYTES	(1 << L1_CACHE_SHIFT)
 
+#define L1_CACHE_SIZE_MASK	(~(L1_CACHE_BYTES - 1))
+
 #define __read_mostly __attribute__((__section__(".data..read_mostly")))
 
 #define INTERNODE_CACHE_SHIFT CONFIG_X86_INTERNODE_CACHE_SHIFT

include/asm-generic/cache.h +2 -0

index 1bfcfe5..6f8eb29 100644
@@ -9,4 +9,6 @@
 #define L1_CACHE_SHIFT		5
 #define L1_CACHE_BYTES		(1 << L1_CACHE_SHIFT)
 
+#define L1_CACHE_SIZE_MASK     (~(L1_CACHE_BYTES - 1))
+
 #endif /* __ASM_GENERIC_CACHE_H */

lib/spinlock_debug.c +41 -35

index 5f3eacd..938a145 100644
@@ -13,41 +13,9 @@
 #include <linux/delay.h>
 #include <linux/module.h>
 
-void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name,
-			  struct lock_class_key *key)
-{
-#ifdef CONFIG_DEBUG_LOCK_ALLOC
-	/*
-	 * Make sure we are not reinitializing a held lock:
-	 */
-	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
-	lockdep_init_map(&lock->dep_map, name, key, 0);
-#endif
-	lock->raw_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
-	lock->magic = SPINLOCK_MAGIC;
-	lock->owner = SPINLOCK_OWNER_INIT;
-	lock->owner_cpu = -1;
-}
-
-EXPORT_SYMBOL(__raw_spin_lock_init);
-
-void __rwlock_init(rwlock_t *lock, const char *name,
-		   struct lock_class_key *key)
-{
-#ifdef CONFIG_DEBUG_LOCK_ALLOC
-	/*
-	 * Make sure we are not reinitializing a held lock:
-	 */
-	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
-	lockdep_init_map(&lock->dep_map, name, key, 0);
-#endif
-	lock->raw_lock = (arch_rwlock_t) __ARCH_RW_LOCK_UNLOCKED;
-	lock->magic = RWLOCK_MAGIC;
-	lock->owner = SPINLOCK_OWNER_INIT;
-	lock->owner_cpu = -1;
-}
-
-EXPORT_SYMBOL(__rwlock_init);
+#define is_cross_lines(p)						\
+	(((unsigned long)(p) & L1_CACHE_SIZE_MASK) !=			\
+	(((unsigned long)(p) + sizeof(*p) - 1) & L1_CACHE_SIZE_MASK))	\
 
 static void spin_dump(raw_spinlock_t *lock, const char *msg)
 {

@@ -296,3 +264,41 @@ void do_raw_write_unlock(rwlock_t *lock)
 	debug_write_unlock(lock);
 	arch_write_unlock(&lock->raw_lock);
 }
+
+void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name,
+			  struct lock_class_key *key)
+{
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	/*
+	 * Make sure we are not reinitializing a held lock:
+	 */
+	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
+	lockdep_init_map(&lock->dep_map, name, key, 0);
+	SPIN_BUG_ON(is_cross_lines(&lock->raw_lock), lock,
+			"!!! the lock cross cache lines !!!");
+#endif
+	lock->raw_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
+	lock->magic = SPINLOCK_MAGIC;
+	lock->owner = SPINLOCK_OWNER_INIT;
+	lock->owner_cpu = -1;
+}
+EXPORT_SYMBOL(__raw_spin_lock_init);
+
+void __rwlock_init(rwlock_t *lock, const char *name,
+		   struct lock_class_key *key)
+{
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	/*
+	 * Make sure we are not reinitializing a held lock:
+	 */
+	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
+	lockdep_init_map(&lock->dep_map, name, key, 0);
+	RWLOCK_BUG_ON(is_cross_lines(&lock->raw_lock), lock,
+			"!!! the lock cross cache lines !!!");
+#endif
+	lock->raw_lock = (arch_rwlock_t) __ARCH_RW_LOCK_UNLOCKED;
+	lock->magic = RWLOCK_MAGIC;
+	lock->owner = SPINLOCK_OWNER_INIT;
+	lock->owner_cpu = -1;
+}
+EXPORT_SYMBOL(__rwlock_init);

Subject: [PATCH] lockdep: add cross cache lines checking

Modern x86 CPU won't hold whole memory bus when executing 'lock' prefixed instructions unless the instruction destination is crossing 2 cache lines. If so, it is disaster of system performance.

Actually if the lock is not in the 'packed' structure, gcc places it safely under x86 arch. But seems add this checking in CONFIG_DEBUG_LOCK_ALLOC is harmless.

Quoted 7 lines · Alex Shi

Subject: [PATCH] lockdep: add cross cache lines checking

Modern x86 CPU won't hold whole memory bus when executing 'lock' prefixed instructions unless the instruction destination is crossing 2 cache lines. If so, it is disaster of system performance.

Quoted 3 lines

Actually if the lock is not in the 'packed' structure, gcc places it safely under x86 arch. But seems add this checking in CONFIG_DEBUG_LOCK_ALLOC is harmless.

Have you tried making this a compile-time check using __alignof__? I would say that any spinlock in a packed data structure is basically a bug, even more so on most other architectures besides x86.

Quoted 8 lines · Arnd Bergmann

Quoted 7 lines · Alex Shi

Subject: [PATCH] lockdep: add cross cache lines checking

Modern x86 CPU won't hold whole memory bus when executing 'lock' prefixed instructions unless the instruction destination is crossing 2 cache lines. If so, it is disaster of system performance.

Quoted 8 lines

Quoted 3 lines

Actually if the lock is not in the 'packed' structure, gcc places it safely under x86 arch. But seems add this checking in CONFIG_DEBUG_LOCK_ALLOC is harmless.

Have you tried making this a compile-time check using __alignof__? I would say that any spinlock in a packed data structure is basically a bug, even more so on most other architectures besides x86.

agreed.

Thanks,

Ingo

Quoted 5 lines

Quoted 5 lines

Have you tried making this a compile-time check using __alignof__? I would say that any spinlock in a packed data structure is basically a bug, even more so on most other architectures besides x86.

I have one concern and one questions here:
concern: maybe the lock is in a well designed 'packed' struct, and it is safe for cross lines issue. but __alignof__ will return 1;

struct abc{
	raw_spinlock_t lock1;
	char 		a;
	char		b;
}__attribute__((packed));

Since the lock is the first object of struct, usually it is well placed.

question: I am a idiot on gcc, I tried some parameters of gcc " --param l1-cache-line-size=1 -mno-align-double" and can not make a cross lines variable without 'packed' structure, but I still don't find a grantee why gcc can avoid the cross line variable if it's not in 'packed' structure?

Quoted 5 lines

agreed.

Thanks,

Ingo

I have one concern and one questions here:
concern: maybe the lock is in a well designed 'packed' struct, and it is safe for cross lines issue. but __alignof__ will return 1;

struct abc{
        raw_spinlock_t lock1;
        char            a;
        char            b;
}__attribute__((packed));

Since the lock is the first object of struct, usually it is well placed.

Quoted 11 lines · Alex Shi

I have one concern and one questions here:
concern: maybe the lock is in a well designed 'packed' struct, and it is safe for cross lines issue. but __alignof__ will return 1;

struct abc{
        raw_spinlock_t lock1;
        char            a;
        char            b;
}__attribute__((packed));

Since the lock is the first object of struct, usually it is well placed.

No, it's actually not. The structure has an external alignment of 1, so if you have an array of these or put it into another struct like

struct xyz {
	char x;
	struct abc a;
};

then it will be misaligned. Thre is no such thing as a well designed 'packed' struct. The only reason to use packing is to describe structures we have no control over such as hardware layouts and on-wire formats that have unusal alignments, and those will never have a spinlock on them.

Arnd

Understand. thx. So is the following checking that your wanted?
===

include/linux/rwlock.h +0 -0

index bc2994e..64828a3 100644
@@ -21,10 +21,12 @@
 do {								\

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

struct foo f1;

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

I think the check should be (__alignof__(lock) < __alignof__(rwlock_t)), otherwise it will still pass when you have structure with attribute((packed,aligned(2)))

Quoted 15 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

struct foo f1;

Quoted 2 lines

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.

Quoted 3 lines

I think the check should be (__alignof__(lock) < __alignof__(rwlock_t)), otherwise it will still pass when you have structure with attribute((packed,aligned(2)))

reasonable!

Quoted 17 lines

Quoted 16 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

struct foo f1;

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

Quoted 5 lines

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.

what's your opinion of this, Ingo?

Quoted 29 lines · Alex Shi

Quoted 3 lines

I think the check should be (__alignof__(lock) < __alignof__(rwlock_t)), otherwise it will still pass when you have structure with attribute((packed,aligned(2)))

reasonable!

Quoted 22 lines

Quoted 12 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

Quoted 4 lines

struct foo f1;

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.

Quoted 1 line

what's your opinion of this, Ingo?

Dunno. How many real bugs have you found via this patch?

Thanks,

Ingo

Quoted 31 lines · Ingo Molnar

Quoted 29 lines · Alex Shi

Quoted 3 lines

I think the check should be (__alignof__(lock) < __alignof__(rwlock_t)), otherwise it will still pass when you have structure with attribute((packed,aligned(2)))

reasonable!

Quoted 22 lines

Quoted 12 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

Quoted 4 lines

struct foo f1;

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.

Quoted 3 lines

Quoted 1 line

what's your opinion of this, Ingo?

Dunno. How many real bugs have you found via this patch?

None. Guess stupid code was shot in lkml reviewing. But if the patch in, it is helpful to block stupid code in developing.

Quoted 32 lines · Alex Shi

Quoted 31 lines · Ingo Molnar

Quoted 29 lines · Alex Shi

Quoted 3 lines

I think the check should be (__alignof__(lock) < __alignof__(rwlock_t)), otherwise it will still pass when you have structure with attribute((packed,aligned(2)))

reasonable!

Quoted 22 lines

Quoted 12 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

Quoted 4 lines

struct foo f1;

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.

Quoted 6 lines

Quoted 3 lines

Quoted 1 line

what's your opinion of this, Ingo?

Dunno. How many real bugs have you found via this patch?

None. Guess stupid code was shot in lkml reviewing. But if the patch in, it is helpful to block stupid code in developing.

The question is, if in the last 10 years not a single such case made it through to today's 15 million lines of kernel code, why should we add the check now?

If it was a simple build time check then maybe, but judging by the discussion it does not seem so simple, does it?

Thanks,

Ingo

Quoted 14 lines

1, it is alignof bug for default gcc on my fc15 and Ubuntu 11.10 etc?

struct sub {
        int  raw_lock;
        char a;
};
struct foo {
        struct sub z;
        int slk;
        char y;
}__attribute__((packed));

struct foo f1;

Quoted 2 lines

__alignof__(f1.z.raw_lock) is 4, but its address actually can align on one byte.

That looks like correct behavior, because the alignment of raw_lock inside of struct sub is still 4. But it does mean that there can be cases where the compile-time check is not sufficient, so we might want the run-time check as well, at least under some config option.