2.6.39-rc5-git2 boot crashs

Quoted 5 lines · Ingo Molnar

Quoted 2 lines · Ingo Molnar
* Thomas Gleixner <[email protected]> wrote:

Quoted 7 lines

Quoted 5 lines
Quoted 2 lines
But I rather suspect, that CONFIG_SLUB=y is the thing we need to look at. The lockless fastpath cmpxchg comes to my mind.
Hm, and CONFIG_X86_ELAN, as Linus noted, has an impact on the cmpxchg implementation.
Walter, could you please test the patch below on a failing kernel?

This patch will likely make the bug go away.

Ingo

Thomas Gleixner

2011-05-04 11:11 UTC #20 lore raw

Quoted 8 lines · Ingo Molnar

Quoted 2 lines · Thomas Gleixner
But I rather suspect, that CONFIG_SLUB=y is the thing we need to look at. The lockless fastpath cmpxchg comes to my mind.
Hm, and CONFIG_X86_ELAN, as Linus noted, has an impact on the cmpxchg implementation.

Exactly. With ELAN CONFIG_X86_CMPXCHG64 is not set. When I disable ELAN it's set.

Quoted 5 lines

Quoted 2 lines
Either we generate broken code with that ELAN caused options or that combo triggers some hidden problem in SLUB.
Note that the crash went away with SLUB_DEBUG=y and PAGEALLOC=y and SLUB_DEBUG=y would certainly narrow any lockless-SLUB race windows.

Well, it's pretty simple:

CONFIG_X86_CMPXCHG64=y compiles this_cpu_generic_cmpxchg_double() into:

    28f7:       89 f9                   mov    %edi,%ecx
    28f9:       8b 3e                   mov    (%esi),%edi
    28fb:       89 45 e4                mov    %eax,-0x1c(%ebp)
    28fe:       89 c3                   mov    %eax,%ebx
    2900:       8b 45 f0                mov    -0x10(%ebp),%eax
    2903:       64 0f c7 0f             cmpxchg8b %fs:(%edi)
    2907:       0f 94 c0                sete   %al
    290a:       84 c0                   test   %al,%al
    290c:       88 45 e4                mov    %al,-0x1c(%ebp)
    290f:       74 a4                   je     28b5 <kmem_cache_alloc+0x29>

while CONFIG_X86_CMPXCHG64=n results in:

    28b0:       8b 03                   mov    (%ebx),%eax
    28b2:       64 8b 30                mov    %fs:(%eax),%esi
    28b5:       39 d6                   cmp    %edx,%esi
    28b7:       75 d2                   jne    288b <kmem_cache_alloc+0x26>
    28b9:       64 8b 50 04             mov    %fs:0x4(%eax),%edx
    28bd:       39 ca                   cmp    %ecx,%edx
    28bf:       75 ca                   jne    288b <kmem_cache_alloc+0x26>
    28c1:       8b 4b 14                mov    0x14(%ebx),%ecx
    28c4:       8b 0c 0e                mov    (%esi,%ecx,1),%ecx
    28c7:       64 89 08                mov    %ecx,%fs:(%eax)
    28ca:       8b 03                   mov    (%ebx),%eax
    28cc:       42                      inc    %edx
    28cd:       64 89 50 04             mov    %edx,%fs:0x4(%eax)

And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.

I'm still trying to understand that macro hell which actually generates that code. I always thought that George Anzingers macro maze was horrible, but that's even worse.

Thanks,

tglx

Pekka Enberg

2011-05-04 11:17 UTC #21 lore raw

Quoted 51 lines · Thomas Gleixner

Quoted 8 lines · Ingo Molnar
Quoted 2 lines · Thomas Gleixner
But I rather suspect, that CONFIG_SLUB=y is the thing we need to look at. The lockless fastpath cmpxchg comes to my mind.
Hm, and CONFIG_X86_ELAN, as Linus noted, has an impact on the cmpxchg implementation.
Exactly. With ELAN CONFIG_X86_CMPXCHG64 is not set. When I disable ELAN it's set.
Quoted 5 lines
Quoted 2 lines
Either we generate broken code with that ELAN caused options or that combo triggers some hidden problem in SLUB.
Note that the crash went away with SLUB_DEBUG=y and PAGEALLOC=y and SLUB_DEBUG=y would certainly narrow any lockless-SLUB race windows.
Well, it's pretty simple:
CONFIG_X86_CMPXCHG64=y compiles this_cpu_generic_cmpxchg_double() into:
28f7: 89 f9 mov %edi,%ecx
28f9: 8b 3e mov (%esi),%edi 28fb: 89 45 e4 mov %eax,-0x1c(%ebp) 28fe: 89 c3 mov %eax,%ebx
2900: 8b 45 f0 mov -0x10(%ebp),%eax 2903: 64 0f c7 0f cmpxchg8b %fs:(%edi) 2907: 0f 94 c0 sete %al
290a: 84 c0 test %al,%al
290c: 88 45 e4 mov %al,-0x1c(%ebp) 290f: 74 a4 je 28b5 <kmem_cache_alloc+0x29>
while CONFIG_X86_CMPXCHG64=n results in:
28b0: 8b 03 mov (%ebx),%eax 28b2: 64 8b 30 mov %fs:(%eax),%esi 28b5: 39 d6 cmp %edx,%esi
28b7: 75 d2 jne 288b <kmem_cache_alloc+0x26> 28b9: 64 8b 50 04 mov %fs:0x4(%eax),%edx 28bd: 39 ca cmp %ecx,%edx
28bf: 75 ca jne 288b <kmem_cache_alloc+0x26> 28c1: 8b 4b 14 mov 0x14(%ebx),%ecx 28c4: 8b 0c 0e mov (%esi,%ecx,1),%ecx 28c7: 64 89 08 mov %ecx,%fs:(%eax) 28ca: 8b 03 mov (%ebx),%eax 28cc: 42 inc %edx
28cd: 64 89 50 04 mov %edx,%fs:0x4(%eax)

Quoted 7 lines

And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.
I'm still trying to understand that macro hell which actually generates that code. I always thought that George Anzingers macro maze was horrible, but that's even worse.

I'm adding Christoph and Tejun to CC.

Tejun Heo

maintainer

2011-05-04 11:27 UTC #22 lore raw

Hello,

Quoted 33 lines · Pekka Enberg

Quoted 32 lines · Thomas Gleixner
On Wed, 4 May 2011, Ingo Molnar wrote:
Well, it's pretty simple:
CONFIG_X86_CMPXCHG64=y compiles this_cpu_generic_cmpxchg_double() into:
28f7: 89 f9 mov %edi,%ecx
28f9: 8b 3e mov (%esi),%edi 28fb: 89 45 e4 mov %eax,-0x1c(%ebp) 28fe: 89 c3 mov %eax,%ebx
2900: 8b 45 f0 mov -0x10(%ebp),%eax 2903: 64 0f c7 0f cmpxchg8b %fs:(%edi) 2907: 0f 94 c0 sete %al
290a: 84 c0 test %al,%al
290c: 88 45 e4 mov %al,-0x1c(%ebp) 290f: 74 a4 je 28b5 <kmem_cache_alloc+0x29>
while CONFIG_X86_CMPXCHG64=n results in:
28b0: 8b 03 mov (%ebx),%eax 28b2: 64 8b 30 mov %fs:(%eax),%esi 28b5: 39 d6 cmp %edx,%esi
28b7: 75 d2 jne 288b <kmem_cache_alloc+0x26> 28b9: 64 8b 50 04 mov %fs:0x4(%eax),%edx 28bd: 39 ca cmp %ecx,%edx
28bf: 75 ca jne 288b <kmem_cache_alloc+0x26> 28c1: 8b 4b 14 mov 0x14(%ebx),%ecx 28c4: 8b 0c 0e mov (%esi,%ecx,1),%ecx 28c7: 64 89 08 mov %ecx,%fs:(%eax) 28ca: 8b 03 mov (%ebx),%eax 28cc: 42 inc %edx
28cd: 64 89 50 04 mov %edx,%fs:0x4(%eax)

Quoted 3 lines

Quoted 3 lines
And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.

Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?

Thanks.

Signature · 1 line

tejun

Pekka Enberg

2011-05-04 12:51 UTC #23 lore raw

Hi Tejun,

Quoted 4 lines · Tejun Heo

Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?

There's no __this_cpu_cmpxchg_double() usage in mm/slub.c so I don't think it's that simple.

Ingo Molnar

2011-05-04 12:57 UTC #24 lore raw

Quoted 10 lines · Pekka Enberg

Hi Tejun,
Quoted 4 lines · Tejun Heo
Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?
There's no __this_cpu_cmpxchg_double() usage in mm/slub.c so I don't think it's that simple.

Well, AFAICS the problem is:

earth4:~/tip> grep cmpxchg mm/slub.c

		if (unlikely(!this_cpu_cmpxchg_double(
		if (unlikely(!this_cpu_cmpxchg_double(

Where this macro resolves to:

# define this_cpu_cmpxchg_double_8(pcp1, pcp2, oval1, oval2, nval1, nval2) \
_this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)

where:

#define _this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \

({                                                                      \
        int ret__;                                                      \
        preempt_disable();                                              \
        ret__ = __this_cpu_generic_cmpxchg_double(pcp1, pcp2,           \
                        oval1, oval2, nval1, nval2);                    \
        preempt_enable();

where:

#define __this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \

({                                                                      \
        int __ret = 0;                                                  \
        if (__this_cpu_read(pcp1) == (oval1) &&                         \
                         __this_cpu_read(pcp2)  == (oval2)) {           \
                __this_cpu_write(pcp1, (nval1));                        \
                __this_cpu_write(pcp2, (nval2));                        \
                __ret = 1;                                              \
        }                                                               \
        (__ret);                                                        \

})

With is both IRQ and SMP unsafe.

Thanks,

Ingo

Thomas Gleixner

2011-05-04 13:03 UTC #25 lore raw

Quoted 46 lines · Ingo Molnar

Quoted 10 lines · Pekka Enberg
Hi Tejun,
Quoted 4 lines · Tejun Heo
Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?
There's no __this_cpu_cmpxchg_double() usage in mm/slub.c so I don't think it's that simple.
Well, AFAICS the problem is:
earth4:~/tip> grep cmpxchg mm/slub.c
		if (unlikely(!this_cpu_cmpxchg_double(
		if (unlikely(!this_cpu_cmpxchg_double(
Where this macro resolves to:
# define this_cpu_cmpxchg_double_8(pcp1, pcp2, oval1, oval2, nval1, nval2) \
_this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
where:
#define _this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \
({                                                                      \
        int ret__;                                                      \
        preempt_disable();                                              \
        ret__ = __this_cpu_generic_cmpxchg_double(pcp1, pcp2,           \
                        oval1, oval2, nval1, nval2);                    \
        preempt_enable();                                              
where:
#define __this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \
({                                                                      \
        int __ret = 0;                                                  \
        if (__this_cpu_read(pcp1) == (oval1) &&                         \
                         __this_cpu_read(pcp2)  == (oval2)) {           \
                __this_cpu_write(pcp1, (nval1));                        \
                __this_cpu_write(pcp2, (nval2));                        \
                __ret = 1;                                              \
        }                                                               \
        (__ret);                                                        \

Quoted 3 lines

})
With is both IRQ and SMP unsafe.

SMP is not an issue because that's cpu local access, but it's irq/softirq unsafe. See my other mail.

Thanks,

tglx

Thomas Gleixner

2011-05-04 13:01 UTC #26 lore raw

Link http://lkml.kernel.org/r/alpine.LFD.2.02.1105041539050.3005@ionos open here

Quoted 8 lines · Tejun Heo

Quoted 3 lines
Quoted 3 lines
And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.
Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?

No, the problem is that ELAN prevents the cmpxchg8b, but keeps CONFIG_CMPXCHG_LOCAL=y which then results in the unprotected code for the following reason:

this_cpu_cmpxchg_double()

-> __pcpu_double_call_return_bool

-> this_cpu_cmpxchg_double_4

Which on x86 expands to

-> percpu_cmpxchg8b_double() when CONFIG_X86_CMPXCHG64=y

With CONFIG_X86_CMPXCHG64=n it expands to the default:

_this_cpu_generic_cmpxchg_double() in linux/percpu.h

#define _this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \

({                                                                      \
        int ret__;                                                      \
        preempt_disable();                                              \
        ret__ = __this_cpu_generic_cmpxchg_double(pcp1, pcp2,           \
                        oval1, oval2, nval1, nval2);                    \
        preempt_enable();                                               \
        ret__;                                                          \

})

And:

#define __this_cpu_generic_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2) \

({                                                                      \
        int __ret = 0;                                                  \
        if (__this_cpu_read(pcp1) == (oval1) &&                         \
                         __this_cpu_read(pcp2)  == (oval2)) {           \
                __this_cpu_write(pcp1, (nval1));                        \
                __this_cpu_write(pcp2, (nval2));                        \
                __ret = 1;                                              \
        }                                                               \
        (__ret);                                                        \

})

So now that failing config has CONFIG_PREEMPT=n which makes preempt_disable / enable a nop.

So preemption is not the problem, but what about interrupts and softirqs ?

So the question is whether CMPXCHG_LOCAL for x86 wants to depend on X86_CMPXCHG64.

The other solution is to use irqsafe_cpu_cmpxchg_double() instead of this_cpu_cmpxchg_double() in slub.c.

This will not hurt the X86_CMPXCHG64=y case, but keep the expansion to the above __this_cpu_generic_cmpxchg_double working.

Which makes me even wonder some more whether we need that whole CMPXCHG_LOCAL #ifdeffery in slub.c at all.

Thanks,

tglx

Tejun Heo

maintainer

2011-05-04 13:20 UTC #27 lore raw

Hello,

Quoted 13 lines · Thomas Gleixner

Quoted 8 lines · Tejun Heo
Quoted 3 lines
Quoted 3 lines
And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.
Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?
No, the problem is that ELAN prevents the cmpxchg8b, but keeps CONFIG_CMPXCHG_LOCAL=y which then results in the unprotected code for the following reason:

...

Quoted 5 lines

So the question is whether CMPXCHG_LOCAL for x86 wants to depend on X86_CMPXCHG64.
The other solution is to use irqsafe_cpu_cmpxchg_double() instead of this_cpu_cmpxchg_double() in slub.c.

I think this is the root cause. CMPXCHG_LOCAL is an optimization flag, indicating that the processor provides fast local cmpxchg, it doesn't say anything about local synchronization properties and if the code required irq exclusion, it should have used irqsafe_cpu_cmpxchg_double() whether the processor supports it natively or not, so there's the bug. Pekka, can you please change the offending cmpxchg_double() to irqsafe variant?

As for CMPXCHG_LOCAL being set spuriously, maybe introduce CMPXCHG_DOUBLE_LOCAL? I don't know. It's pretty nasty to implement different high-level code paths depending on CPU features. We can't even determine whether the feature will be actually available at compile time. But, then again, it might incur noticeable slowdown for cases where the generic implementation is used. Has anyone measured the difference against before the whole this_cpu conversion?

Thanks.

Signature · 1 line

tejun

Thomas Gleixner

2011-05-04 14:10 UTC #28 lore raw

Quoted 23 lines · Tejun Heo

Hello,
Quoted 13 lines · Thomas Gleixner
Quoted 8 lines · Tejun Heo
Quoted 3 lines
Quoted 3 lines
And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.
Hmmm... if it's a race caused by preemtion enabled where it shouldn't be, it's most likely the wrong type of this_cpu_cmpxchg_double() being used in SLUB? ie. __this_cpu_cmpxchg_double() where it should have been this_cpu_cmpxchg_double()? Christoph?
No, the problem is that ELAN prevents the cmpxchg8b, but keeps CONFIG_CMPXCHG_LOCAL=y which then results in the unprotected code for the following reason:
...
Quoted 5 lines
So the question is whether CMPXCHG_LOCAL for x86 wants to depend on X86_CMPXCHG64.
The other solution is to use irqsafe_cpu_cmpxchg_double() instead of this_cpu_cmpxchg_double() in slub.c.

Quoted 7 lines

I think this is the root cause. CMPXCHG_LOCAL is an optimization flag, indicating that the processor provides fast local cmpxchg, it doesn't say anything about local synchronization properties and if the code required irq exclusion, it should have used irqsafe_cpu_cmpxchg_double() whether the processor supports it natively or not, so there's the bug. Pekka, can you please change the offending cmpxchg_double() to irqsafe variant?

Patch below. Ingo, can you test that please ?

Quoted 2 lines

As for CMPXCHG_LOCAL being set spuriously, maybe introduce CMPXCHG_DOUBLE_LOCAL? I don't know. It's pretty nasty to implement

Oh no, please not another CONFIG_WTF and more #ifdeffery.

Quoted 3 lines

different high-level code paths depending on CPU features. We can't even determine whether the feature will be actually available at compile time. But, then again, it might incur noticeable slowdown for

Right, and the x86 implementation should not do

#ifdef CONFIG_X86_CMPXCHG64
#define percpu_cmpxchg8b_double(pcp1, o1, o2, n1, n2) #endif

And let the code fallback to the generic variant. It should have an #else path using the the cmpxchg64_local() implementation which has alternatives for runtime selection of cmpxchg8b or the cli protected emulation.

Quoted 2 lines

cases where the generic implementation is used. Has anyone measured the difference against before the whole this_cpu conversion?

Yes, that really wants to be done. The whole CMPXCHG_LOCAL ifdeffery should have been avoided in the first place. this_cpu_cmpxchg can really be implemented with preempt_enable/disable and the irqsafe variant in any case.

Thanks,

tglx

--------->
Subject: slub-hmm.patch
From: Thomas Gleixner <[email protected]>
Date: Wed, 04 May 2011 15:38:19 +0200

Signed-off-by Thomas Gleixner <[email protected]>

---
 include/linux/percpu.h |    2 +-
 mm/slub.c              |    4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

include/linux/percpu.h +1 -1

Index: linux-2.6/include/linux/percpu.h
===================================================================
@@ -948,7 +948,7 @@ do {									\
 	irqsafe_generic_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
 # endif
 # define irqsafe_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)	\
-	__pcpu_double_call_return_int(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
+	__pcpu_double_call_return_bool(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
 #endif
 
 #endif /* __LINUX_PERCPU_H */

mm/slub.c +2 -2

Index: linux-2.6/mm/slub.c
===================================================================
@@ -1940,7 +1940,7 @@ redo:
 		 * Since this is without lock semantics the protection is only against
 		 * code executing on this cpu *not* from access by other cpus.
 		 */
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				object, tid,
 				get_freepointer(s, object), next_tid(tid)))) {

@@ -2145,7 +2145,7 @@ redo:
 		set_freepointer(s, object, c->freelist);
 
 #ifdef CONFIG_CMPXCHG_LOCAL
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				c->freelist, tid,
 				object, next_tid(tid)))) {

Ingo Molnar

2011-05-04 14:14 UTC #29 lore raw

Quoted 1 line · Thomas Gleixner

Patch below. Ingo, can you test that please ?

Sure - test underway.

Thanks,

Ingo

Ingo Molnar

2011-05-04 14:36 UTC #30 lore raw

PATCH 1/1 slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 6 lines · Ingo Molnar

Quoted 1 line · Thomas Gleixner
Patch below. Ingo, can you test that please ?
Sure - test underway.

Ok, the patch below is looking really good - the test would have crashed on the bad kernel. I think we can consider the regression fixed:

Acked-and-tested-by Ingo Molnar <[email protected]>

I'll keep it running some more to make really sure it's fixed, plus it would be nice if Walter tested your fix as well.

Thanks,

Ingo

----------------->

Quoted 1 line

From c22bd309573330e33a77c329405d9473fc14f1cb Mon Sep 17 00:00:00 2001

From: Thomas Gleixner <[email protected]>
Date: Wed, 4 May 2011 15:38:19 +0200
Subject: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Signed-off-by Thomas Gleixner <[email protected]>

Cc Pekka Enberg <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Jens Axboe <[email protected]>

Cc werner <[email protected]>

Cc Christoph Lameter <[email protected]>

Cc Tejun Heo <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

---
 include/linux/percpu.h |    2 +-
 mm/slub.c              |    4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

include/linux/percpu.h +1 -1

index 3a5c444..8b97308 100644
@@ -948,7 +948,7 @@ do {									\
 	irqsafe_generic_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
 # endif
 # define irqsafe_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)	\
-	__pcpu_double_call_return_int(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
+	__pcpu_double_call_return_bool(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
 #endif
 
 #endif /* __LINUX_PERCPU_H */

mm/slub.c +2 -2

index 94d2a33..9d2e5e4 100644
@@ -1940,7 +1940,7 @@ redo:
 		 * Since this is without lock semantics the protection is only against
 		 * code executing on this cpu *not* from access by other cpus.
 		 */
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				object, tid,
 				get_freepointer(s, object), next_tid(tid)))) {

@@ -2145,7 +2145,7 @@ redo:
 		set_freepointer(s, object, c->freelist);
 
 #ifdef CONFIG_CMPXCHG_LOCAL
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				c->freelist, tid,
 				object, next_tid(tid)))) {

Christoph Lameter

Acked-by on v1 1/1

2011-05-04 14:42 UTC #31 lore raw

Re: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 7 lines · Ingo Molnar

Ok, the patch below is looking really good - the test would have crashed on the bad kernel. I think we can consider the regression fixed:
Acked-and-tested-by Ingo Molnar <[email protected]>
I'll keep it running some more to make really sure it's fixed, plus it would be nice if Walter tested your fix as well.

Looks good and is exactly what I have here.

Acked-by Christoph Lameter <[email protected]>

Ingo Molnar

2011-05-04 16:31 UTC #32 lore raw

Re: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 9 lines · Ingo Molnar

Quoted 6 lines · Ingo Molnar
Quoted 1 line · Thomas Gleixner
Patch below. Ingo, can you test that please ?
Sure - test underway.

Quoted 7 lines

Ok, the patch below is looking really good - the test would have crashed on the bad kernel. I think we can consider the regression fixed:
Acked-and-tested-by Ingo Molnar <[email protected]>
I'll keep it running some more to make really sure it's fixed, plus it would be nice if Walter tested your fix as well.

Stopped the test after 2 hours uptime - i think we can consider the crash fixed.

Thanks,

Ingo

Ben Greear

2011-05-04 21:56 UTC #33 lore raw

Re: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 4 lines · Ingo Molnar

Quoted 1 line
From c22bd309573330e33a77c329405d9473fc14f1cb Mon Sep 17 00:00:00 2001
From: Thomas Gleixner<[email protected]>
Date: Wed, 4 May 2011 15:38:19 +0200
Subject: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

This patch appears to fix the crashes I was seeing on my 32-bit Atom system.

It would crash within 30 seconds of booting every time before this patch...

Thanks,
Ben

Signature · 2 lines

Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com

Linus Torvalds

2011-05-04 22:01 UTC #34 lore raw

Re: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 5 lines · Ben Greear

This patch appears to fix the crashes I was seeing on my 32-bit Atom system.
It would crash within 30 seconds of booting every time before this patch...

Oh, well - I already committed it and pushed out, otherwise I'd have added that piece of information to the commit log.

But it's good to know that others had seen this too, just never realized what was going on.

Btw, that does seem to imply that your kernel config is somewhat odd. We _should_ be using cmpxchg8b natively if you compile for anything newer than PPro, and that includes atom.

Did you perhaps say "compile for Pentium" (which is pretty close to Atom in some respects - but we don't trust that all Pentium-class CPU's have cmpxchg8b, even if the Intel ones all should).

Regardless, it's pushed out and should be in current -git, apart from any possible mirroring delays there may be that may b eholdin git up from actually being visible on the public kernel.org machines yet.

Linus

Ben Greear

2011-05-04 22:25 UTC #35 lore raw

Re: [PATCH] slub: Fix the lockless code on 32-bit platforms with no 64-bit cmpxchg

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Ben Greear
This patch appears to fix the crashes I was seeing on my 32-bit Atom system.
It would crash within 30 seconds of booting every time before this patch...
Oh, well - I already committed it and pushed out, otherwise I'd have added that piece of information to the commit log.

No worries...I'm just happy to finally be able to boot .39 :)

Quoted 10 lines

But it's good to know that others had seen this too, just never realized what was going on.
Btw, that does seem to imply that your kernel config is somewhat odd. We _should_ be using cmpxchg8b natively if you compile for anything newer than PPro, and that includes atom.
Did you perhaps say "compile for Pentium" (which is pretty close to Atom in some respects - but we don't trust that all Pentium-class CPU's have cmpxchg8b, even if the Intel ones all should).

Well, yes. I'm compiling for 'M586' it seems, plus SMP, pre-empt, etc.

Maybe it's time to move to a newer processor family!

Thanks,
Ben

Signature · 2 lines

Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com

Christoph Lameter

2011-05-04 14:19 UTC #36 lore raw

include/linux/percpu.h do { \ · line 954

Quoted 13 lines · Thomas Gleixner

Index: linux-2.6/include/linux/percpu.h
===================================================================

include/linux/percpu.h +1 -1

@@ -948,7 +948,7 @@ do {									\
 	irqsafe_generic_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
 # endif
 # define irqsafe_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)	\
-	__pcpu_double_call_return_int(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
+	__pcpu_double_call_return_bool(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
 #endif
 
 #endif /* __LINUX_PERCPU_H */

Looking at the same thing here testing a similar patch. This should go separately as a bug fix.

Quoted 15 lines

Index: linux-2.6/mm/slub.c
===================================================================

mm/slub.c +1 -1

@@ -1940,7 +1940,7 @@ redo:
 		 * Since this is without lock semantics the protection is only against
 		 * code executing on this cpu *not* from access by other cpus.
 		 */
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				object, tid,
 				get_freepointer(s, object), next_tid(tid)))) {

mm/slub.c redo: · line 2151

Quoted 8 lines

mm/slub.c +1 -1

@@ -2145,7 +2145,7 @@ redo:
 		set_freepointer(s, object, c->freelist);
 
 #ifdef CONFIG_CMPXCHG_LOCAL
-		if (unlikely(!this_cpu_cmpxchg_double(
+		if (unlikely(!irqsafe_cpu_cmpxchg_double(
 				s->cpu_slab->freelist, s->cpu_slab->tid,
 				c->freelist, tid,
 				object, next_tid(tid)))) {

Ok as a basic fix since it does not change the code generated for the common x86 and other.

My version also takes out the CONFIG_CMPXCHG_LOCAL.

We could make the above two patches and then make the CONFIG_CMPXCHG_LOCAL removal a separate one (since it requires some benchmarking).

Tejun Heo

maintainer

2011-05-04 14:25 UTC #37 lore raw

Hello,

Quoted 7 lines · Thomas Gleixner

Quoted 2 lines
cases where the generic implementation is used. Has anyone measured the difference against before the whole this_cpu conversion?
Yes, that really wants to be done. The whole CMPXCHG_LOCAL ifdeffery should have been avoided in the first place. this_cpu_cmpxchg can really be implemented with preempt_enable/disable and the irqsafe variant in any case.

Yeah, slub code looks pretty scary with the #ifdefs. IIUC, the problem was that cmpxchg_double is an optimization for fast path which was already very light weight and an extra locked op or irq on/off would have made considerable difference.

The cmpxchg_double optimization made the fast path go quite faster when CPU supports it but it may as well slow things down considerably if CPU doesn't, due to extra irq on/off's. Anyways, here's hoping that the slow down is acceptable compared to the base code without cmpxchg_double and the ugliness can be removed.

Thanks.

Signature · 1 line

tejun

Christoph Lameter

2011-05-04 14:35 UTC #38 lore raw

Quoted 5 lines · Tejun Heo

The cmpxchg_double optimization made the fast path go quite faster when CPU supports it but it may as well slow things down considerably if CPU doesn't, due to extra irq on/off's. Anyways, here's hoping that the slow down is acceptable compared to the base code without cmpxchg_double and the ugliness can be removed.

I think we are all in agreement. First path to fix the percpu macros:

Subject: percpu: Fix irqsafe_cpu_cmpxchg_double

The function in the macro was not updated when the function was given a bool return value.

Signed-off-by Christoph Lameter <[email protected]>

---
 include/linux/percpu.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

include/linux/percpu.h +1 -1

Index: linux-2.6/include/linux/percpu.h
===================================================================
@@ -948,7 +948,7 @@ do {									\
 	irqsafe_generic_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
 # endif
 # define irqsafe_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)	\
-	__pcpu_double_call_return_int(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
+	__pcpu_double_call_return_bool(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
 #endif
 
 #endif /* __LINUX_PERCPU_H */

Ingo Molnar

2011-05-04 15:21 UTC #39 lore raw

Quoted 8 lines · Christoph Lameter

Quoted 5 lines · Tejun Heo
The cmpxchg_double optimization made the fast path go quite faster when CPU supports it but it may as well slow things down considerably if CPU doesn't, due to extra irq on/off's. Anyways, here's hoping that the slow down is acceptable compared to the base code without cmpxchg_double and the ugliness can be removed.

Quoted 8 lines

I think we are all in agreement. First path to fix the percpu macros:
Subject: percpu: Fix irqsafe_cpu_cmpxchg_double
The function in the macro was not updated when the function was given a bool return value.
Signed-off-by Christoph Lameter <[email protected]>

Note, the final commit needs to have a proper Reported-by and explanation about how this was triggered, to fairly credit all the hard work done by Werner ...

Thanks,

Ingo

Thomas Gleixner

2011-05-04 14:46 UTC #40 lore raw

Quoted 11 lines · Tejun Heo

Hello,
Quoted 7 lines · Thomas Gleixner
Quoted 2 lines
cases where the generic implementation is used. Has anyone measured the difference against before the whole this_cpu conversion?
Yes, that really wants to be done. The whole CMPXCHG_LOCAL ifdeffery should have been avoided in the first place. this_cpu_cmpxchg can really be implemented with preempt_enable/disable and the irqsafe variant in any case.

Quoted 8 lines

Yeah, slub code looks pretty scary with the #ifdefs. IIUC, the problem was that cmpxchg_double is an optimization for fast path which was already very light weight and an extra locked op or irq on/off would have made considerable difference.
The cmpxchg_double optimization made the fast path go quite faster when CPU supports it but it may as well slow things down considerably if CPU doesn't, due to extra irq on/off's. Anyways, here's hoping

Not really.

CMPXCHG_LOCAL=n

	local_irq_save();
	  handle_everything();
	local_irq_restore();

vs.

CMPXCHG_LOCAL=y

	do_prep();
	local_irq_save();
	  emulate_cmpxchg();
	local_irq_restore();
	do_rest();

So you have local irq disable/enable in both cases. So for the case where you don't have a local cmpxchg8b/16b available it's not worse versus irq disable/enable than now. It just has the possible repeat case when stuff changed between the prep and the actual cmpxchg, which is the same problem when cmpxchg8b/16 is available.

Thanks,

tglx

Christoph Lameter

2011-05-04 15:00 UTC #41 lore raw

Quoted 5 lines

So you have local irq disable/enable in both cases. So for the case where you don't have a local cmpxchg8b/16b available it's not worse versus irq disable/enable than now. It just has the possible repeat case when stuff changed between the prep and the actual cmpxchg, which is the same problem when cmpxchg8b/16 is available.

Right there is only the tid management that is added. Hope I am fast enough to at least get one patch in (not very well tested):

Subject: slub: Remove CONFIG_CMPXCHG_LOCAL ifdeffery

Remove the #ifdefs. This means that the irqsafe_cpu_cmpxchg_double() is used everywhere.

There may be performance implications since:

A. We now have to manage a transaction ID for all arches

B. The interrupt holdoff for arches not supporting CONFIG_CMPXCHG_LOCAL is reduced to a very short irqoff section.

There are no multiple irqoff/irqon sequences as a result of this change. Even in the fallback case we only have to do one disable and enable like before.

Signed-off-by Christoph Lameter <[email protected]>

---
 include/linux/slub_def.h |    2 -
 mm/slub.c                |   56 -----------------------------------------------
 2 files changed, 58 deletions(-)

include/linux/slub_def.h +0 -2

Index: linux-2.6/include/linux/slub_def.h
===================================================================
@@ -37,9 +37,7 @@ enum stat_item {
 
 struct kmem_cache_cpu {
 	void **freelist;	/* Pointer to next available object */
-#ifdef CONFIG_CMPXCHG_LOCAL
 	unsigned long tid;	/* Globally unique transaction id */
-#endif
 	struct page *page;	/* The slab from which we are allocating */
 	int node;		/* The node of the page (or -1 for debug) */
 #ifdef CONFIG_SLUB_STATS

mm/slub.c +0 ~~-56~~

203 lines not on this page · raw message

Linus Torvalds

2011-05-04 15:14 UTC #42 lore raw

Quoted 3 lines · Christoph Lameter

Right there is only the tid management that is added. Hope I am fast enough to at least get one patch in (not very well tested):

So the thing that worries me about this is non-x86 architectures.

Have we verified that the generic routines are ok for all architectures? Has somebody checked the memory barriers in particular? Things that work on x86 may not work on non-x86. Everything should be per-cpu _except_ for the initialization, I think, but that should be double-checked.

I guess the initialization happens so early that we don't really need to worry about it, but I'd still like somebody to really double- and triple-check it for me.

My gut reaction would be: let's do the minimal patch that just fixes things to do irqsafe_cpu_cmpxchg_double() for 2.6.39, and then let's remove the #ifdef'fery in -rc1. Or make _really_ sure that things are ok for platforms that never even triggered the CMPXCHG_LOCAL case before.

Hmm?

Linus

Christoph Lameter

2011-05-04 15:28 UTC #43 lore raw

Quoted 9 lines · Linus Torvalds

Quoted 3 lines · Christoph Lameter
Right there is only the tid management that is added. Hope I am fast enough to at least get one patch in (not very well tested):
So the thing that worries me about this is non-x86 architectures.
Have we verified that the generic routines are ok for all architectures? Has somebody checked the memory barriers in particular?

There are no memory barriers used. The barrier() here is a compiler hint to not keep data across it. This is dealing with concurrency issues on the *same* cpu due to preemption and irqs. It avoids the interrupt disable. There no memory barrier issues for code running on a single cpu. The cpu is always guaranteed to have a consistent view of the data.

There is an additional patchset that also uses a cmpxchg_double for the slowpath. There barrier issues may arise because concurrent access is possible but that is likely to be merged only in 2.6.41. The cmpxchg_double in that case is a locked operation.

Quoted 3 lines

Things that work on x86 may not work on non-x86. Everything should be per-cpu _except_ for the initialization, I think, but that should be double-checked.

The fallback path is using interrupt disable / enable. This must be working on all arches AFAICT.

Quoted 7 lines

My gut reaction would be: let's do the minimal patch that just fixes things to do irqsafe_cpu_cmpxchg_double() for 2.6.39, and then let's remove the #ifdef'fery in -rc1. Or make _really_ sure that things are ok for platforms that never even triggered the CMPXCHG_LOCAL case before.
Hmm?

Ok. Pekka can put that patch in for the next round of merges?

Linus Torvalds

2011-05-04 15:38 UTC #44 lore raw

Quoted 3 lines · Christoph Lameter

There are no memory barriers used. The barrier() here is a compiler hint to not keep data across it.

Go back and read my email, please.

The lack of memory barriers is exactly what I worry about.

Look at the initialization path. The "tid" thing is _not_ purely cpu-local.

Linus

Christoph Lameter

2011-05-04 16:08 UTC #45 lore raw

Quoted 10 lines · Linus Torvalds

Quoted 3 lines · Christoph Lameter
There are no memory barriers used. The barrier() here is a compiler hint to not keep data across it.
Go back and read my email, please.
The lack of memory barriers is exactly what I worry about.
Look at the initialization path. The "tid" thing is _not_ purely cpu-local.

kmem_cache_create() only hands the pointer to the slab cache back after the percpu values have been initialized. In order to do an allocation one needs to have the pointer to the slab cache.

You think that accesses to struct kmem_cache_cpu by other cpus could require memory barriers? But this is what both SLAB and SLUB already do today even before these modification. Nor do we have memory barriers for the same situation in the page allocator.

Pekka Enberg

2011-05-04 15:45 UTC #46 lore raw

Quoted 9 lines · Christoph Lameter

Quoted 7 lines
My gut reaction would be: let's do the minimal patch that just fixes things to do irqsafe_cpu_cmpxchg_double() for 2.6.39, and then let's remove the #ifdef'fery in -rc1. Or make _really_ sure that things are ok for platforms that never even triggered the CMPXCHG_LOCAL case before.
Hmm?
Ok. Pekka can put that patch in for the next round of merges?

Sure. Who's taking care of the minimal fix for .39?

Linus Torvalds

2011-05-04 15:59 UTC #47 lore raw

Quoted 2 lines · Pekka Enberg

Sure. Who's taking care of the minimal fix for .39?

I'll take it. I'm just hoping to also get Werner's tested-by for it.

I'm pretty confident this is it, though, so if I don't get it by the end of the day I'll just apply it regardless with just a reported-by from him.

Linus

Linus Torvalds

2011-05-04 18:20 UTC #48 lore raw

Quoted 6 lines · Linus Torvalds

I'll take it. I'm just hoping to also get Werner's tested-by for it.
I'm pretty confident this is it, though, so if I don't get it by the end of the day I'll just apply it regardless with just a reported-by from him.

So I'm still waiting for the tested-by, but in the meantime I wrote a changelog. And part of that changelog reads:

[ Btw, that whole "generic code defaults to no protection" design just
sounds stupid - if the code needs no protection, there is no reason to use "cmpxchg_double" to begin with. So we should probably just remove
the unprotected version entirely as pointless. - Linus ]

which really sums up the whole thing.

The current "this_cpu_cmpxchg_double()" implementation is just incredibly idiotic. There is absolutely _no_ point to having that function at all. Why does it exist?

I can kind of see the point of the "preempt" version, although I'm not entirely convinced of that either. But the notion of having a "cmpxchg" function that isn't atomic even on a single CPU just makes me go "f*ck that, whoever wrote that is just a moron".

If the function doesn't need atomicity, you're really better off just writing it out. It's going to be faster on pretty much all architectures using just regular load/store instructions.

Linus

Christoph Lameter

2011-05-04 18:49 UTC #49 lore raw

Quoted 8 lines · Linus Torvalds

So I'm still waiting for the tested-by, but in the meantime I wrote a changelog. And part of that changelog reads:
[ Btw, that whole "generic code defaults to no protection" design just
sounds stupid - if the code needs no protection, there is no reason to use "cmpxchg_double" to begin with. So we should probably just remove
the unprotected version entirely as pointless. - Linus ]

The unprotected version is the __this_cpu_cmpxchg_double? That currently has no user and could be removed. But all other functions also have __ variants so it was put there for symmetries sake.

Quoted 5 lines

which really sums up the whole thing.
The current "this_cpu_cmpxchg_double()" implementation is just incredibly idiotic. There is absolutely _no_ point to having that function at all. Why does it exist?

this_cpu_cmpxchg_double() affords protection against preemption but not irqs. In the allocator case we have to deal with interrupts so its not useful there. Other code that can guarantee that nothing runs from irq context can use this function and then the fallback handling on other arches can avoid disabling and enabling interrupts which is required by irqsafe_cpu_cmpxchg_double().

Quoted 8 lines

I can kind of see the point of the "preempt" version, although I'm not entirely convinced of that either. But the notion of having a "cmpxchg" function that isn't atomic even on a single CPU just makes me go "f*ck that, whoever wrote that is just a moron".
If the function doesn't need atomicity, you're really better off just writing it out. It's going to be faster on pretty much all architectures using just regular load/store instructions.

The unlocked cmpxchg8b/16b is quite fast on x86. The __ function allows the use of cmpxchg8b on x86 and the fallback (and therefore longer) code on other archs.

But I see the point that __this_cpu_cmpxchg double is pretty useless. There is no user and so it could be removed.

Linus Torvalds

2011-05-04 19:08 UTC #50 lore raw

Quoted 4 lines · Christoph Lameter

The unprotected version is the __this_cpu_cmpxchg_double? That currently has no user and could be removed. But all other functions also have __ variants so it was put there for symmetries sake.

No, I'm talking about the regular "this_cpu_cmpxchg_double" with no underscores.

Why the f*!@ does that exist?

Why the f*%^ do you have to write "irqsafe", when the whole concept DOES NOT MAKE SENSE without the "irqsafe"?

Why did we have this bug in the first place, in other words? The whole interface was mis-designed, and pretty much designed to cause bugs.

I think we should remove every single version of "this_cpu_cmpxchg_double" except for two: the per-cpu one and the SMP-safe one.

And the per-cpu one doesn't mention "irqsafe" or "preempt" or anything like that, because the whole function makes no sense except when it is irq-safe and preempt-safe.

So I think the fact that we need to say "irqsafe" is a bug. Plain and simple.

The whole (and ONLY) point of "cmpxchg" is atomicity.

This is not like "add one to something". That's an operation that makes sense outside of atomicity issues. But "cmpxchg" is all about being atomic.

Linus

Christoph Lameter

2011-05-04 19:30 UTC #51 lore raw

Quoted 9 lines · Linus Torvalds

Quoted 4 lines · Christoph Lameter
The unprotected version is the __this_cpu_cmpxchg_double? That currently has no user and could be removed. But all other functions also have __ variants so it was put there for symmetries sake.
No, I'm talking about the regular "this_cpu_cmpxchg_double" with no underscores.
Why the f*!@ does that exist?

Because it is useful if the per cpu serialization only requires safety from preemption during the cmpxchg.

Quoted 2 lines

Why the f*%^ do you have to write "irqsafe", when the whole concept DOES NOT MAKE SENSE without the "irqsafe"?

Because that is how the other irq safe this_cpu_xxx functions are named and I tried to keep it consistent.

Quoted 3 lines

I think we should remove every single version of "this_cpu_cmpxchg_double" except for two: the per-cpu one and the SMP-safe one.

The smp safe one would be cmpxchg_double() then. This is part of a future patchset and would be named like other fully atomic ops. Would not be part of include/linux/percpu.h because it is not a per cpu related function.

Quoted 3 lines

And the per-cpu one doesn't mention "irqsafe" or "preempt" or anything like that, because the whole function makes no sense except when it is irq-safe and preempt-safe.

It does make sense because arches that do not have the hardware capabilities must use fallback implementations that can be faster if f.e. irqs must not be disabled. And this_cpu_xxx ops are usually used in performance critical paths.

Quoted 7 lines

So I think the fact that we need to say "irqsafe" is a bug. Plain and simple.
The whole (and ONLY) point of "cmpxchg" is atomicity.
This is not like "add one to something". That's an operation that makes sense outside of atomicity issues. But "cmpxchg" is all about being atomic.

The naming convention came about from the existing this_cpu_xxx operations (and yes those starting with the problem of the increment). To do it differently now just for this function would make it more difficult to comprehend for someone already familiar with this_cpu operations on per cpu data.

Linus Torvalds

2011-05-04 19:45 UTC #52 lore raw

Quoted 3 lines · Christoph Lameter

The naming convention came about from the existing this_cpu_xxx operations

You're missing my point.

An "add" operation makes sense even if it isn't atomic, because atomicity isn't a part of the definition of "add".

But cmpxchg DOES NOT MAKE SENSE without atomicity guarantees.

The whole operation is about atomicity.

Having a version that isn't atomic is STUPID. It's misleading. It's _wrong_.

In contrast, having a non-atomic "add" version is understandable.

So when you say "naming convention", you're missing the much bigger naming convention. Namely the "cmpxchg" part!

Linus

Christoph Lameter

2011-05-04 20:04 UTC #53 lore raw

Quoted 11 lines · Linus Torvalds

Quoted 3 lines · Christoph Lameter
The naming convention came about from the existing this_cpu_xxx operations
You're missing my point.
An "add" operation makes sense even if it isn't atomic, because atomicity isn't a part of the definition of "add".
But cmpxchg DOES NOT MAKE SENSE without atomicity guarantees.

This is not a real cmpxchg after all. Its not atomic in the sense of other functions. Its only "percpu atomic" if you want it that way. This is *not* a full cmpxchg_double().

Quoted 3 lines

The whole operation is about atomicity.
Having a version that isn't atomic is STUPID. It's misleading. It's _wrong_.

Its "atomic" in the sense that it is an instruction that is either executed or not in total and that fact alone allow the avoiding of synchronization for preemption and interrupts. We just push as much processing as possible into this single instruction and then we dont have to worry about preemption or interrupts while this function is executed by the processor.

Quoted 4 lines

In contrast, having a non-atomic "add" version is understandable.
So when you say "naming convention", you're missing the much bigger naming convention. Namely the "cmpxchg" part!

Well this is not really a true cmpxchg. There is no lock prefix.

The semantics of the this_cpu_xxx functions are not atomic but only per cpu atomic. That per cpu atomicity can require only the exclusion of preemption or the exclusion of interrupts.

In extreme cases we dont care about preemption or interrupts interfering with the operation. We just want to opportunistically take advantage of sophisticated instructions if they are available (f.e. for accurate vm counters). Or we may have some other external means of serialization (like lock or we already disabled preemption). Thats what the __ operations are for.

Maybe I should have pushed the cmpxchg_double() before the this_cpu_cmpxchg to avoid these misunderstandings

Here is the patch for the fullly atomic cmpxchg_double() which will be needed for making the non per cpu specific processing lockless later:

Subject: x86: Add support for cmpxchg_double

A simple implementation that only supports the word size and does not have a fallback mode (would require a spinlock).

And 32 and 64 bit support for cmpxchg_double. cmpxchg double uses the cmpxchg8b or cmpxchg16b instruction on x86 processors to compare and swap 2 machine words. This allows lockless algorithms to move more context information through critical sections.

Set a flag CONFIG_CMPXCHG_DOUBLE to signal the support of that feature during kernel builds.

Signed-off-by Christoph Lameter <[email protected]>

---
 arch/x86/Kconfig.cpu              |    3 ++
 arch/x86/include/asm/cmpxchg_32.h |   46 ++++++++++++++++++++++++++++++++++++++
 arch/x86/include/asm/cmpxchg_64.h |   45 +++++++++++++++++++++++++++++++++++++
 arch/x86/include/asm/cpufeature.h |    1
 4 files changed, 95 insertions(+)

arch/x86/include/asm/cmpxchg_64.h +45 -0

Index: linux-2.6/arch/x86/include/asm/cmpxchg_64.h
===================================================================
@@ -151,4 +151,49 @@ extern void __cmpxchg_wrong_size(void);
 	cmpxchg_local((ptr), (o), (n));					\
 })
 
+#define cmpxchg16b(ptr, o1, o2, n1, n2)				\
+({								\
+	char __ret;						\
+	__typeof__(o2) __junk;					\
+	__typeof__(*(ptr)) __old1 = (o1);			\
+	__typeof__(o2) __old2 = (o2);				\
+	__typeof__(*(ptr)) __new1 = (n1);			\
+	__typeof__(o2) __new2 = (n2);				\
+	asm volatile(LOCK_PREFIX_HERE "lock; cmpxchg16b (%%rsi);setz %1" \
+		       : "=d"(__junk), "=a"(__ret)		\
+		       : "S"(ptr), "b"(__new1),	"c"(__new2),	\
+		         "a"(__old1), "d"(__old2));		\
+	__ret; })
+
+
+#define cmpxchg16b_local(ptr, o1, o2, n1, n2)			\
+({								\
+	char __ret;						\
+	__typeof__(o2) __junk;					\
+	__typeof__(*(ptr)) __old1 = (o1);			\
+	__typeof__(o2) __old2 = (o2);				\
+	__typeof__(*(ptr)) __new1 = (n1);			\
+	__typeof__(o2) __new2 = (n2);				\
+	asm volatile("cmpxchg16b (%%rsi)\n\t\tsetz %1\n\t"	\
+		       : "=d"(__junk)_, "=a"(__ret)		\
+		       : "S"((ptr)), "b"(__new1), "c"(__new2),	\
+ 		         "a"(__old1), "d"(__old2));		\
+	__ret; })
+
+#define cmpxchg_double(ptr, o1, o2, n1, n2)				\
+({									\
+	BUILD_BUG_ON(sizeof(*(ptr)) != 8);				\
+	VM_BUG_ON((unsigned long)(ptr) % 16);				\
+	cmpxchg16b((ptr), (o1), (o2), (n1), (n2));			\
+})
+
+#define cmpxchg_double_local(ptr, o1, o2, n1, n2)			\
+({									\
+	BUILD_BUG_ON(sizeof(*(ptr)) != 8);				\
+	VM_BUG_ON((unsigned long)(ptr) % 16);				\
+	cmpxchg16b_local((ptr), (o1), (o2), (n1), (n2));		\
+})
+
+#define system_has_cmpxchg_double() cpu_has_cx16
+
 #endif /* _ASM_X86_CMPXCHG_64_H */

arch/x86/include/asm/cmpxchg_32.h +46 -0

50 lines not on this page · raw message

arch/x86/Kconfig.cpu +3 -0

Index: linux-2.6/arch/x86/Kconfig.cpu
===================================================================
@@ -308,6 +308,9 @@ config X86_CMPXCHG
 config CMPXCHG_LOCAL
 	def_bool X86_64 || (X86_32 && !M386)
 
+config CMPXCHG_DOUBLE
+	def_bool X86_64 || (X86_32 && !M386)
+
 config X86_L1_CACHE_SHIFT
 	int
 	default "7" if MPENTIUM4 || MPSC

arch/x86/include/asm/cpufeature.h +1 -0

Index: linux-2.6/arch/x86/include/asm/cpufeature.h
===================================================================
@@ -286,6 +286,7 @@ extern const char * const x86_power_flag
 #define cpu_has_hypervisor	boot_cpu_has(X86_FEATURE_HYPERVISOR)
 #define cpu_has_pclmulqdq	boot_cpu_has(X86_FEATURE_PCLMULQDQ)
 #define cpu_has_perfctr_core	boot_cpu_has(X86_FEATURE_PERFCTR_CORE)
+#define cpu_has_cx16		boot_cpu_has(X86_FEATURE_CX16)
 
 #if defined(CONFIG_X86_INVLPG) || defined(CONFIG_X86_64)
 # define cpu_has_invlpg		1

[email protected]

2011-05-04 20:24 UTC #54 lore raw

Quoted 7 lines · Christoph Lameter

Quoted 1 line · Linus Torvalds
But cmpxchg DOES NOT MAKE SENSE without atomicity guarantees.
This is not a real cmpxchg after all. Its not atomic in the sense of other functions. Its only "percpu atomic" if you want it that way. This is *not* a full cmpxchg_double().

Calling it a cmpxchg when it doesn't have the primary distinguishing property of a hardware cmpxchg is just loading a bullet in the chamber and inviting kernel hackers to point it at their feet...

Christoph Lameter

2011-05-04 20:33 UTC #55 lore raw

Quoted 5 lines · On Wed, 4 May 2011, [email protected] wrote:

Quoted 4 lines · Christoph Lameter
Quoted 1 line · Linus Torvalds
But cmpxchg DOES NOT MAKE SENSE without atomicity guarantees.

Quoted 7 lines

Quoted 3 lines
This is not a real cmpxchg after all. Its not atomic in the sense of other functions. Its only "percpu atomic" if you want it that way. This is *not* a full cmpxchg_double().
Calling it a cmpxchg when it doesn't have the primary distinguishing property of a hardware cmpxchg is just loading a bullet in the chamber and inviting kernel hackers to point it at their feet...

It does have most of the distinguishing characterstics but the lock-prefixless cmpxchg8b/16b (which is quite fast) is used in a unique way here in a percpu fastdpath. Thats why we have the strange naming this_cpu_cmpxchg_double etc.

Ingo Molnar

2011-05-04 20:49 UTC #56 lore raw

Quoted 6 lines · Christoph Lameter

Quoted 3 lines
Calling it a cmpxchg when it doesn't have the primary distinguishing property of a hardware cmpxchg is just loading a bullet in the chamber and inviting kernel hackers to point it at their feet...
It does have most of the distinguishing characterstics but the lock-prefixless cmpxchg8b/16b (which is quite fast) [...]

6 cycles for CMPXCHG8B versus 19 cycles for LOCK CMPXCHG8B, on Nehalem.

And note that it's not really true that the LOCK prefix-less CMPXCHG8B is not
atomic: the write is atomic if the target word is naturally aligned, on i586 and upwards ...

So in practice, unless the SLUB variables are misaligned, the lock prefix-less CMPXCHG8B *IS* atomic.

Non-atomicity is a special case of a weird special case.

Quoted 2 lines

[...] is used in a unique way here in a percpu fastdpath. Thats why we have the strange naming this_cpu_cmpxchg_double etc.

Furthermore, we never used cmpxchg in the kernel without expecting atomicity.

Uniquely strange, unintuitive naming == invitation for strange bugs.

And guess what, we had a strange bug here. Can you possibly see any connection?

Thanks,

Ingo

Linus Torvalds

2011-05-04 21:07 UTC #57 lore raw

Quoted 3 lines · Christoph Lameter

Maybe I should have pushed the cmpxchg_double() before the this_cpu_cmpxchg to avoid these misunderstandings

Christoph, the only mis-understanding is yours.

I understand perfectly that the percpu cmpxchg isn't SMP-atomic. We all know that.

The problem is that cmpxchg *IS*NOT*AN*CMPXCHG*AT*ALL*. Not even on UP.

It's something totally different.

Linus

Linus Torvalds

2011-05-04 21:20 UTC #58 lore raw

Quoted 2 lines · Linus Torvalds

The problem is that cmpxchg *IS*NOT*AN*CMPXCHG*AT*ALL*. Not even on UP.

Btw, the really sad thing is that as far as I can tell, the cmpxchg64_local() function that we define actually gets this *right*, with a helper function that actually works (and disables interrupts) and all the alternative_io() stuff to then use the right instruction automatically if the CPU supports it, rather than making it a hardcoded decision.

But we don't use it, because the "percpu_cmpxchg8b_double()" code rolls its own inferior version, and has slightly different semantics (ie the whole "return value success" thing).

So close, but yet so far.

Linus

Thomas Gleixner

2011-05-04 21:41 UTC #59 lore raw

Quoted 12 lines · Linus Torvalds

Quoted 2 lines · Linus Torvalds
The problem is that cmpxchg *IS*NOT*AN*CMPXCHG*AT*ALL*. Not even on UP.
Btw, the really sad thing is that as far as I can tell, the cmpxchg64_local() function that we define actually gets this *right*, with a helper function that actually works (and disables interrupts) and all the alternative_io() stuff to then use the right instruction automatically if the CPU supports it, rather than making it a hardcoded decision.

Quoted 3 lines

But we don't use it, because the "percpu_cmpxchg8b_double()" code rolls its own inferior version, and has slightly different semantics (ie the whole "return value success" thing).

Yeah, I tripped over that as well. And the new shiny extra CONFIG_CMPXCHG_DOUBLE misfeature Christoph nailed together is just ignoring it as well. It's just more useless #ifdef and CONFIG bloat.

That whole this_cpu_* stuff seems to be designed by committee. A quick grep shows that max. 10% of the implemented macro hell is actually used. Can we get rid of all unused ones and bring them back when they are actually required?

Thanks,

tglx

Tejun Heo

maintainer

2011-05-05 09:54 UTC #60 lore raw

Hey,

Quoted 8 lines · Thomas Gleixner

Yeah, I tripped over that as well. And the new shiny extra CONFIG_CMPXCHG_DOUBLE misfeature Christoph nailed together is just ignoring it as well. It's just more useless #ifdef and CONFIG bloat.
That whole this_cpu_* stuff seems to be designed by committee. A quick grep shows that max. 10% of the implemented macro hell is actually used. Can we get rid of all unused ones and bring them back when they are actually required?

What happened there was more of lack of design rather than too much design. At first it were a few ops with only two variants - preemption protected default one and __ prefixed unprotected one. Then came the irqsafe ops and then the whole kinda exploded on itself with all the different ops.

Cleaning up percpu accessors has been on my todo list for some time now. The this_cpu_*() thing is still in its infancy and there aren't many users and the existing ones are mostly in the core, so cleaning things up should be relatively easy. Things which I've been considering are...

1. Static and dynamic accessors.

We have two sets of percpu accessors. Originally, one set was for static percpu variables and the other for dynamic ones. Since the percpu allocator reimplementation, there's no distinction between static and dynamic and the new this_cpu_*() functions don't distinguish them. We need to unify the duplicate ones. There's nothing much to decide about this. It just needs to be done.

2. this_cpu_*()

This one is more tricky. General cleanup aside...

this_cpu_*() ops currently come in three flavors and the naming convention is rather confusing. __this_cpu for no protection, this_cpu for preemtion disabled and irqsafe_cpu for irq protected. IIUC it was intended to loosely match the naming convention of spinlocks but I'm not sure whether that's beneficial in this case.

The biggest problem, as shown by this bug, is that it's error-prone. Percpu ops as they currently stand don't have lockdep protection for accessing contexts. There's nothing protecting percpu vars being accessed from wrong contexts. I think adding lockdep protection should be doable and should be done, but it would be much better if it's safer by default.

The problem is aggravated by the fact that, on x86 where most of developement and testing happens, there's no difference between __this_cpu_*(), this_cpu_*() and irqsafe_cpu_*(). They're one and the same, so testing coverage suffers. We can avoid this by adding a debug option which forces the generic versions whether the arch ones are there or not, but it does raise the question - do we really need all these different confusing variants?

For x86, it doesn't matter. There are some corner cases with cmpxchg_[double] but I don't think we would be in any trouble just using the generic ones for them. The problem is with other archs where local atomic ops haven't been or, for most load-store architectures, can't be implemented. We might say "eh... screw them" and let them use the generic ones but the problem is that this_cpu_*() tend to be used in extremely hot paths where extra irq on/off's can show up as significant overhead.

The thing that I want gone the most is the irqsafe_ variant. It would be much nicer/safer if this_cpu_*() is atomic against everything. If the caller is gonna take care of exclusion from the enclosing area (this is a valid use case when there's a series of operations to be done including but not limited to multiple this_cpu ops), it can use __this_cpu_*() ones.

The reason to disable preemtion instead of IRQ is two-fold - First, preemption can be disabled for longer period than IRQ. Second, depending on CPU, toggling preemption is significantly cheaper than toggling preemption. For this_cpu ops, the first one doesn't apply. It's always very short, so the only thing that needs to be considered is the overhead of toggling protection.

So, to avoid suffering performance penalty from this_cpu_*() conversion, architectures can choose one of the followings.

1. Implement arch specific this_cpu_*() ops. This would be the better way but unfortunately many architectures simply can't. :-(

2. Make irq toggling as cheap as preemption toggling. This can be achieved by implementing IRQ masking in software. I played with it a bit on x86 last year. I didn't get to finish it and it would have taken me some time to iron out weird failures but it didn't seem too difficult and as irq on/off is quite expensive on a lot of CPUs, this might bring overall performance benefit.

For many archs, #2 would be the only choice and if we're gonna do that I think it would be best to do it on x86 too. It involves changes to common code too and x86 has the highest test/development coverage.

I don't feel brave enough to remove preemption protected ones without first somehow taking care of non-x86 archs. The preemption disabled ones are used for statistics in net, block, irq and fs and simply switching to irq protected ones is likely to noticeably hurt many non-x86 archs. Maybe the ones which really matter can implement at least _add() and we can get away without doing soft irq masking.

Anyways, that's what I've been thinking. I'll get to it in the next devel cycle or the one after that. What do you guys think about soft irq masking idea?

Thanks.

--
tejun

Ingo Molnar

2011-05-05 10:18 UTC #61 lore raw

Quoted 10 lines · Tejun Heo

2. Make irq toggling as cheap as preemption toggling. This can be achieved by implementing IRQ masking in software. I played with it a bit on x86 last year. I didn't get to finish it and it would have taken me some time to iron out weird failures but it didn't seem too difficult and as irq on/off is quite expensive on a lot of CPUs, this might bring overall performance benefit.
For many archs, #2 would be the only choice and if we're gonna do that I think it would be best to do it on x86 too. It involves changes to common code too and x86 has the highest test/development coverage.

We played with this in -rt on and off but note that -rt doesnt do this right now. Interestingly, most of the irq-disable wrappery and state tracking code for that is upstream already, via the lockdep irq state tracking patches. (Surprise! :-)

The disadvantages:

- register pressure increases, the pushf+cli+popf sequence has no register side-effects, while soft flags inevitably disturb register allocations. *possibly* quite low with the modern percpu implementation, but this has to be measured very carefuly, with disassembly.

- icache size increases - the percpu ops are larger than the minimal pushf+cli+popfl sequence. Again, this too has to be measured both via vmlinux size analysis and via perf stat --repeat icache pressure runs.

[ This is also an assymetric cost: it increases the cost of the cache-cold
case, while most of the benefits are in the cache-hot case. ]

- irq replay becomes common and there's extra cost due to that. Also we are not ready to replay some types of irqs (lapic timer), at least with current code. So there's some ongoing maintenance cost there.

The benefits are:

- lockdep is already tracking irqs on/off sections rather carefully, so we know all the places that play with irqs and the ongoing maintenance cost is shared with what we'd have to do with lockdep anyway.

- on Nehalem a "PUSHF; CLI; POPF" sequence is 18 cycles, a soft sequence would be more like 2 cycles. So we win around 15 cycles per sequence in the fast path - minus collateral slowpath cost above ... which are not directly comparable.

- Stock mainline would become a truly hard RT irq handlers kernel which never ever disables hardirqs. Big wow factor and precision guided, laser mounted sharks!

I probably missed a few factors, but these are the main concerns.

My firm judgement: "Dunno".

Thanks,

Ingo

Thomas Gleixner

2011-05-05 10:45 UTC #62 lore raw

Quoted 11 lines · Tejun Heo

2. Make irq toggling as cheap as preemption toggling. This can be achieved by implementing IRQ masking in software. I played with it a bit on x86 last year. I didn't get to finish it and it would have taken me some time to iron out weird failures but it didn't seem too difficult and as irq on/off is quite expensive on a lot of CPUs, this might bring overall performance benefit.
For many archs, #2 would be the only choice and if we're gonna do that I think it would be best to do it on x86 too. It involves changes to common code too and x86 has the highest test/development coverage.

Quoted 6 lines

I don't feel brave enough to remove preemption protected ones without first somehow taking care of non-x86 archs. The preemption disabled ones are used for statistics in net, block, irq and fs and simply switching to irq protected ones is likely to noticeably hurt many non-x86 archs. Maybe the ones which really matter can implement at least _add() and we can get away without doing soft irq masking.

There it's fine when we have certain use cases which just need preemption protection, but the function name should be clear about it and we should only have the functions which are actually required instead of every possible flavour of _OP.

Quoted 3 lines

Anyways, that's what I've been thinking. I'll get to it in the next devel cycle or the one after that. What do you guys think about soft irq masking idea?

It's doable, we played around with that in rt already and put it aside again :)

You need to do the check at the vector entry and then reinject the vector on local_irq_enable/restore(), so that's mostly hackery in the ASM entry code which includes to fixup the pushed flags so the reti wont reeneable interrupts.

That's halfways easy to do on x86, not sure about other architectures, and you have to carefully weigh the actual benefit against the overhead in the slow path case plus the inevitable hackery you need in each architecture implementation.

No strong opinion, but definitely worthwhile to toy with it :)

Thanks,

tglx

Christoph Lameter

2011-05-05 18:20 UTC #63 lore raw

Quoted 3 lines · Tejun Heo

Anyways, that's what I've been thinking. I'll get to it in the next devel cycle or the one after that. What do you guys think about soft irq masking idea?

Great idea. Would make the whole irq on/off business much cheaper.

Ingo Molnar

2011-05-05 19:14 UTC #64 lore raw

Quoted 7 lines · Christoph Lameter

Quoted 3 lines · Tejun Heo
Anyways, that's what I've been thinking. I'll get to it in the next devel cycle or the one after that. What do you guys think about soft irq masking idea?
Great idea. Would make the whole irq on/off business much cheaper.

The tradeoffs are *not at all* clear and the result (on x86) is not 'much cheaper', at all ...

In particular the irq-enable path gets complicated by the need to check the flag and call a hardirq handling function in that case - a far cry from the single-byte POPF instruction. It will be somewhat cheaper cycle-wise - but the code gets bloated, so the instruction cache impact has to be measured carefully. (See my other mail for details.)

There's also the fact that PUSHF+CLI+POPF sequence has been getting cheaper all the time with newer hardware generations. CLI+STI is even cheaper, 10 cycles both on Intel and AMD CPUs. So it's an optimization that might get narrower and narrower with every CPU generation.

Thanks,

Ingo

werner

author

2011-05-05 19:53 UTC #65 lore raw

In reply to Linus Torvalds

Quoted 7 lines · On Thu, 5 May 2011 11:54:21 +0200 Tejun Heo <[email protected]> wrote:

Hey,
Quoted 4 lines · Thomas Gleixner
Yeah, I tripped over that as well. And the new shiny extra CONFIG_CMPXCHG_DOUBLE misfeature Christoph nailed together is just ignoring it as well. It's just more useless #ifdef and CONFIG bloat.

Quoted 7 lines

Quoted 4 lines
That whole this_cpu_* stuff seems to be designed by committee. A quick grep shows that max. 10% of the implemented macro hell is actually used. Can we get rid of all unused ones and bring them back when they are actually required?
What happened there was more of lack of design rather than too much design.

........

From the sight of an user, not of an programmer, my opinion about more and more config options and the design is:

As the 1st step, for can be compiled generic kernels
at all, the kernel should have (and has) the ability, to discover at run-time , what hardware the individual user has, and to use only the corresponding kernel subroutines. F.ex. if subroutines for ELAN or MOORESTON were compiled also, then the kernel ignore them simply, if on run-time it discovers that the user has a 486 computer.

Then, in a 2nd step considering this, any
configuration of the arch is becoming obsolete and should be reduced so much as possible. It was useful in the time of papertapes and punched cards to can pick out what one need, but nowaday we have enough memory that the kernel can be compiled ALWAYS including everything, and on run-time the kernel discovers and use only what's present.
For the case if users in poorer countries have a 486
with 8 MB storage (long time ago I used Slackware on such computers), one should CAN alternatively choice to compile and deliver also small kernels. But as default - or spoken more generally if is compiled a huge kernel - then at run-time it simply should ignore what's absent and used what's present. This means, in this general case, ANY user configuration of hardware is obsolete, and as default should be compiled everything (and into the kernel, not as module, in-/output devices which nowadays can happen as boot devices inclusive for an installation). One should reduce the configuration to a very few number of basical items - such as, with/without PEA; low-memory system (that parameter is the only what matters for make impossible an huge everythingyes kernel); slow system.

There is a very good analogon to this. Some distros
have a very complicated configurator, difficult for advanced user and impossible to install Linux for beginners. F.ex., SUSE has an elefantous poissen-green installer, with thousands of options and very mis-understandable, in what I (trying to help someone two weeks ago) was unable to create an install/root partition without to be sure not to loose the existing partition. This is a complete misconcept, hinders people to use Linux, put users in risk by a mistake loose his existing partition/files, and should be dumped completely !!! Principally, the installation can be automatical and thus have to be automatical; little adaptions the user can make later in the KDE control center. My distro, intended to be maximal easy, has no interactive installer at all, and produces a very good working system in 99% of the cases, full-automatically. For example, for what any partition configuration ?? The 1:4 LZMA-packed iso, unfold, gives a 20 GB system. Thus, the install program can search alone where to find 20 GB, without any question to the user. It searches on the primary, then on the secondary hard disk for 20GB unpartioned space; if not found, then it resizes and/or moves existing partitions to get 20 GB free, and then install the sistem. If really all disks are full with files, it goes in the rescue system with mc , and the user should delete some videos etc and restart the instellation. Even the keyboard language, system language, user name, internet id/passwords are found and installed automatically - the install program reads them out from any (in 99% existing) pre-existing Windows, Linux or Minix installation on the computer.

Thus, when I read many comments here in the kernel
threads, I feel that the most kernel configs should be removed and the kernel should find out itself at run time what hardware is existing. Also, the functions of things like udev and hal should be automatized. It is a sick concept, that the kernel itself find all hardware, but one need an externel program like hal to interprete the kernel messages and install the hardware, what the kernel can and should do itself. Each kernel version simply should include an updated table, of existing/known hardware and their most adequade Linux drivers, and then, during identifying hardware at boot or hotplug, set up everything to use it.

The kernel is becoming more and more complicated, and
before people loosing themselves in details, one should make it most easy possible, for the users and for the maintainers, and throw out unnecessary and too complicated or misconcepted things. Because at the same time more and more new hardware surges, and also the kernel config becomes more and more big, there is no alternative and should be started most early possible, to automatize and improve the kernel's runtime autoconfig and auto-hardware-managing habilities. And REDUCE THE HUMAN-DEPENDING PRE-CONFIG TO THE MINIMUM POSSIBLE. This satisfies also that Linux is tecnically good, but have to become more easy for the use-by-anybody. This should be considered for the whole politics/direction in what is going the kernel development.

---
Professional hosting for everyone - http://www.host.ru

Christoph Lameter

2011-05-05 20:09 UTC #66 lore raw

Quoted 6 lines · werner

As the 1st step, for can be compiled generic kernels at all, the kernel
should have (and has) the ability, to discover at run-time , what hardware the individual user has, and to use only the corresponding kernel subroutines. F.ex. if subroutines for ELAN or MOORESTON were compiled also, then the kernel ignore them simply, if on run-time it discovers that the user has a 486 computer.

Yes indeed the kernel can detect that. And the code has fallback for the case that the processor flags indicate that cmpxchg16b is not supported.

However, in this case the kernel configuration at build time was set in such a way (!CMPXCHG64 support but CMPXCHG_LOCAL) that generic fallback functions were used at compile time instead of the x86 assembly that can do the fallback with run time detection. Thus the code to do the fallback was not compiled in. Frankly, I was not aware that such a case existed where one could disable cmpxchg64 in this way and was expecting that the runtime detection would always be compiled in for the CMPXCHG_LOCAL case.

werner

author

2011-05-05 21:12 UTC #67 lore raw

Quoted 13 lines · On Thu, 5 May 2011 15:09:04 -0500 (CDT) Christoph Lameter <[email protected]> wrote:

Quoted 7 lines · werner
As the 1st step, for can be compiled generic kernels
at all, the kernel
should have (and has) the ability, to discover at run-time , what hardware the individual user has, and to use only the corresponding kernel subroutines. F.ex. if subroutines for ELAN or MOORESTON were compiled also, then the kernel ignore them simply, if on run-time it discovers that the user has a 486 computer.
Yes indeed the kernel can detect that. And the code has fallback for the case that the processor flags indicate that cmpxchg16b is not supported.

Quoted 9 lines

However, in this case the kernel configuration at build time was set in such a way (!CMPXCHG64 support but CMPXCHG_LOCAL) that generic fallback functions were used at compile time instead of the x86 assembly that can do the fallback with run time detection. Thus the code to do the fallback was not compiled in. Frankly, I was not aware that such a case existed where one could disable cmpxchg64 in this way and was expecting that the runtime detection would always be compiled in for the CMPXCHG_LOCAL case.

Thus, things gone wrong because it's only half-consequent. One should compile everything, and at runtime the kernel itself detect the existing hardware and decides/uses just what it need.

My (and many other users) mind on configuration is very simple: I switch everything on, so that the kernel has everything available, and in run-time it uses just what's existing on the individual computer of the user.

Just if there occured an human configuration error, so that something at run-time wasnt available, then one should improve the above explained manner of use, reducing human need/influence, compiling everything, and improving the kernel's runtime detection and use/selection of its adequade modules.

I saw plenty people (specially, beginners) loosing all their files by overformating or repartitioning the harddisk within a too-complicated installer. Many interactive installers are not good understandable. And many simple users don't know nothing about harddisks, partitions, etc. You know all details inside your washmachine, and you need to know it for use it ?? Linux has to work also for stupid people. Thus, the partitioning / formatting process of the installation is a good example what CAN and HAS TO BE full-automatized, in order to reduce human errors. If a typical distro is 5 GB or 20 GB big, then the installer can and has to manage it, silently and alone, to find or desocupy this space (and more if possible) anywhere on a harddisk, silently and by itself, so that it installs problemless for beginners (while 'specialists' before the installation can desocupy a certain space of the harddisk which then the installer will find and use).

90% of the config options, users don't know for what they are. Instead of more and more new config features in, EVERY CONFIG PARAMETER WHAT THE KERNEL CAN DETECT AT RUN TIME (at the beginning of booting) SHOULD BE THROWED OUT. And the kernel should be compiled 'everythingyes' as default. Even then, with all exotic (but nowadays happening) boot-necessary input/output hardware included, my vmlinuz is only 10 MB big. Sufficient memory for run this (together with an initrd for an installer) nowadays should exist on almost all computers. All other, not-boot necessary modules are perhaps 50 MB, and since the Atari time with 20 MB harddisks passed, there is NO REASON FOR COMPILE SMALL THE KERNEL. Even on Android phones, compiling the kernel / modules 50 MB big but using often only a part, dont hurt. But for emergency, instead of completely configless, one could let 2 options for the kernel config: normal, small (below 16 M memory).
Provisorically, one could but one should not include
such a raw-selection menu in the kernel config, because to check and maintain the dependences of their various single config parameters would be big extra work. Instead of this, one should rigorously make more and more config parameters definitively obsolete and reduce them by improving the corresponding runtime ability of the kernel.
---
Professional hosting for everyone - http://www.host.ru

Thomas Gleixner

2011-05-05 22:27 UTC #68 lore raw

Quoted 10 lines · werner

90% of the config options, users don't know for what they are. Instead of more and more new config features in, EVERY CONFIG PARAMETER WHAT THE KERNEL CAN DETECT AT RUN TIME (at the beginning of booting) SHOULD BE THROWED OUT.
And the kernel should be compiled 'everythingyes' as default. Even then,
with all exotic (but nowadays happening) boot-necessary input/output hardware
included, my vmlinuz is only 10 MB big. Sufficient memory for run this
(together with an initrd for an installer) nowadays should exist on almost all computers. All other, not-boot necessary modules are perhaps 50 MB, and since the Atari time with 20 MB harddisks passed, there is NO REASON FOR COMPILE SMALL THE KERNEL. Even on Android phones, compiling the kernel / modules 50 MB

Quoted 8 lines

big but using often only a part, dont hurt. But for emergency, instead of completely configless, one could let 2 options for the kernel config: normal,
small (below 16 M memory). Provisorically, one could but one should not
include such a raw-selection menu in the kernel config, because to check and maintain the dependences of their various single config parameters would be
big extra work. Instead of this, one should rigorously make more and more
config parameters definitively obsolete and reduce them by improving the corresponding runtime ability of the kernel.

Have a look outside of the x86 and "smartphone brag with your GBs of RAM" world and you'll see that there are

- systems which really care about size reductions which are measured in kilobytes.

- systems where runtime detection is impossible

- systems where runtime detection is complete overkill in various
aspects: boottime, memory footprint ...

And you CANNOT put those requirements under a single CONFIG_VERY_SMALL=y fits it all thing simply because embedded devices have those fundamental different requirements vs. drivers, filesystems ....

Aside of that config options are a pretty useful mechanism to debug problems.

And in the context of that particular case you are barking up the completely wrong tree. The facts that

- slub used the wrong macro

- the CONFIG dependent x86 implementation of that this_cpu_* mess was crap to begin with

are not an argument at all to go and impose a 100MB/50MB/16MB or whatever arbitrary choice you make limit of CONFIG_FITS_IT_ALL_* approach.

That simply does not work.

Thanks,

tglx

A message that is not in the archive (sent off-list or not yet received): [email protected]

werner

author

2011-05-05 06:46 UTC #72 lore raw

Just now I compiled 2.6.39-rc6-git1 (including still
the patchs by hand because not yet included), its also OK, good running, without all these problems. :)

Yes, I continue with my everythingyesconfig, which all the time and also now
after this patchs gives good generic kernels for the distro, working good on my
server and on the laptops of the neighbours except that sometimes
(instead of ELAN) I'll make 486 binaries. And now put the package on the mirrors because everything is OK, and I dont need to switch on and off the server so that they can sync, and the users can use the now working packages of 2.6.39-rcX , which have many new drivers and other good improvements.

Like since years, I continue to compile new versions since -rc1 and report problems. But it was very important that Linus take care of these problems now, because nobody else searched for the reasons. These bugs in logfs and in slub.c and percpu.h probably were processor-type / arch independent, and would have given problems for the most users, so that they could not have been ignored.
wl

=======================================================

Quoted 5 lines · On Thu, 5 May 2011 08:02:04 +0200 Ingo Molnar <[email protected]> wrote:

Quoted 1 line · werner
I'll test the patchs with a 486 config, switching off ELAN.

Quoted 9 lines

I think you can skip all those other test suggestions in this thread - as you confirmed in this email the root cause of your crashes has been found.
So the best testing you could do would be for you to resume testing whatever original config you were using on your system, and make sure there's really no crashes left - and report any other regressions you might see.
Thanks,
Ingo

"werner" <[email protected]>
---
Professional hosting for everyone - http://www.host.ru

Ingo Molnar

2011-05-04 16:50 UTC #73 lore raw

Quoted 3 lines · Linus Torvalds

My gut reaction would be: let's do the minimal patch that just fixes things to do irqsafe_cpu_cmpxchg_double() for 2.6.39, and then let's remove the #ifdef'fery in -rc1. [...]

Looks like the sanest option IMHO, -rc7 is pretty late for anything than a few-liner patch.

Quoted 2 lines

[...] Or make _really_ sure that things are ok for platforms that never even triggered the CMPXCHG_LOCAL case before.

Considering that the status quo was !CMPXCHG_LOCAL in v2.6.38 and that lockless SLUB is an x86-only affair right now:

 $ git grep CMPXCHG_LOCAL arch/
 arch/um/Kconfig.x86:config CMPXCHG_LOCAL
 arch/x86/Kconfig.cpu:config CMPXCHG_LOCAL

There should be no problem with other architectures, right?

Thanks,

Ingo

Thomas Gleixner

2011-05-04 17:12 UTC #74 lore raw

Quoted 9 lines · Ingo Molnar

Quoted 3 lines · Linus Torvalds
My gut reaction would be: let's do the minimal patch that just fixes things to do irqsafe_cpu_cmpxchg_double() for 2.6.39, and then let's remove the #ifdef'fery in -rc1. [...]
Looks like the sanest option IMHO, -rc7 is pretty late for anything than a few-liner patch.

Agreed.

Quoted 11 lines

Quoted 2 lines
[...] Or make _really_ sure that things are ok for platforms that never even triggered the CMPXCHG_LOCAL case before.
Considering that the status quo was !CMPXCHG_LOCAL in v2.6.38 and that lockless SLUB is an x86-only affair right now:
 $ git grep CMPXCHG_LOCAL arch/
 arch/um/Kconfig.x86:config CMPXCHG_LOCAL
 arch/x86/Kconfig.cpu:config CMPXCHG_LOCAL
There should be no problem with other architectures, right?

No, they use the local_irq disabled path which is pretty much the same as in 38.

Thanks,

tglx

Pekka Enberg

2011-05-04 15:41 UTC #75 lore raw

Quoted 9 lines · Christoph Lameter

Subject: slub: Remove CONFIG_CMPXCHG_LOCAL ifdeffery
Remove the #ifdefs. This means that the irqsafe_cpu_cmpxchg_double() is used everywhere.
There may be performance implications since:
A. We now have to manage a transaction ID for all arches

Quoted 7 lines

B. The interrupt holdoff for arches not supporting CONFIG_CMPXCHG_LOCAL is reduced to a very short irqoff section.
There are no multiple irqoff/irqon sequences as a result of this change. Even in the fallback case we only have to do one disable and enable like before.
Signed-off-by Christoph Lameter <[email protected]>

This doesn't apply cleanly on top of slab/next which has some of your cleanup patches applied. There's some CONFIG_PREEMPT conflicts so I'd rather you rediffed it yourself.

Pekka

Ingo Molnar

2011-05-04 13:23 UTC #76 lore raw

Quoted 2 lines · Thomas Gleixner

Which makes me even wonder some more whether we need that whole CMPXCHG_LOCAL #ifdeffery in slub.c at all.

I always found that #ifdeffery rather repulsive.

Thanks,

Ingo

Christoph Lameter

2011-05-04 14:21 UTC #77 lore raw

Quoted 2 lines · Thomas Gleixner

So the question is whether CMPXCHG_LOCAL for x86 wants to depend on X86_CMPXCHG64.

Right.

Quoted 8 lines

The other solution is to use irqsafe_cpu_cmpxchg_double() instead of this_cpu_cmpxchg_double() in slub.c.
This will not hurt the X86_CMPXCHG64=y case, but keep the expansion to the above __this_cpu_generic_cmpxchg_double working.
Which makes me even wonder some more whether we need that whole CMPXCHG_LOCAL #ifdeffery in slub.c at all.

Hmmm... I have not measured it but it would certainly be nice to get rid of it. The period of irq disablement is then reduced in the fastpath too. However, we need to do additional tid checking (which should be fast).

The following patch does that and runs here in kvm

---
 include/linux/percpu.h   |    2 -
 include/linux/slub_def.h |    2 -
 mm/slub.c                |   60 +----------------------------------------------
 3 files changed, 3 insertions(+), 61 deletions(-)

include/linux/percpu.h +1 -1

Index: linux-2.6/include/linux/percpu.h
===================================================================
@@ -948,7 +948,7 @@ do {									\
 	irqsafe_generic_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
 # endif
 # define irqsafe_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)	\
-	__pcpu_double_call_return_int(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
+	__pcpu_double_call_return_bool(irqsafe_cpu_cmpxchg_double_, (pcp1), (pcp2), (oval1), (oval2), (nval1), (nval2))
 #endif
 
 #endif /* __LINUX_PERCPU_H */

include/linux/slub_def.h +0 -2

Index: linux-2.6/include/linux/slub_def.h
===================================================================
@@ -37,9 +37,7 @@ enum stat_item {
 
 struct kmem_cache_cpu {
 	void **freelist;	/* Pointer to next available object */
-#ifdef CONFIG_CMPXCHG_LOCAL
 	unsigned long tid;	/* Globally unique transaction id */
-#endif
 	struct page *page;	/* The slab from which we are allocating */
 	int node;		/* The node of the page (or -1 for debug) */
 #ifdef CONFIG_SLUB_STATS

mm/slub.c +2 ~~-58~~

213 lines not on this page · raw message

Christoph Lameter

2011-05-04 14:04 UTC #78 lore raw

In reply to Pekka Enberg

Quoted 35 lines · Pekka Enberg

Quoted 35 lines
Well, it's pretty simple:
CONFIG_X86_CMPXCHG64=y compiles this_cpu_generic_cmpxchg_double() into:
28f7: 89 f9 mov %edi,%ecx
28f9: 8b 3e mov (%esi),%edi 28fb: 89 45 e4 mov %eax,-0x1c(%ebp) 28fe: 89 c3 mov %eax,%ebx
2900: 8b 45 f0 mov -0x10(%ebp),%eax 2903: 64 0f c7 0f cmpxchg8b %fs:(%edi) 2907: 0f 94 c0 sete %al
290a: 84 c0 test %al,%al
290c: 88 45 e4 mov %al,-0x1c(%ebp) 290f: 74 a4 je 28b5 <kmem_cache_alloc+0x29>
while CONFIG_X86_CMPXCHG64=n results in:
28b0: 8b 03 mov (%ebx),%eax 28b2: 64 8b 30 mov %fs:(%eax),%esi 28b5: 39 d6 cmp %edx,%esi
28b7: 75 d2 jne 288b <kmem_cache_alloc+0x26> 28b9: 64 8b 50 04 mov %fs:0x4(%eax),%edx 28bd: 39 ca cmp %ecx,%edx
28bf: 75 ca jne 288b <kmem_cache_alloc+0x26> 28c1: 8b 4b 14 mov 0x14(%ebx),%ecx 28c4: 8b 0c 0e mov (%esi,%ecx,1),%ecx 28c7: 64 89 08 mov %ecx,%fs:(%eax) 28ca: 8b 03 mov (%ebx),%eax 28cc: 42 inc %edx
28cd: 64 89 50 04 mov %edx,%fs:0x4(%eax)
And that code runs with preemption enabled. So when the task gets preempted _BEFORE_ it has actuallty written back the data, then the race window is wide open.

Quoted 5 lines

Quoted 3 lines
I'm still trying to understand that macro hell which actually generates that code. I always thought that George Anzingers macro maze was horrible, but that's even worse.
I'm adding Christoph and Tejun to CC.

The above should not happen. If a kernel config indicates that there is no cmpxchg16b/cmpxchg8b available then we need to not compile the path that uses cmpxchg8b/cmpxchg16b. Guess we need CMPXCHG_DOUBLE_LOCAL or so.

Tejun Heo

maintainer

2011-05-04 14:08 UTC #79 lore raw

Hello, Christoph.

Quoted 3 lines · Christoph Lameter

The above should not happen. If a kernel config indicates that there is no cmpxchg16b/cmpxchg8b available then we need to not compile the path that uses cmpxchg8b/cmpxchg16b. Guess we need CMPXCHG_DOUBLE_LOCAL or so.

But regardless of that, if the code requires irq safety it should be using irqsafe_* operations. CMPXCHG_LOCAL is an optimization hint and doesn't necessarily imply stronger synchronization guarantees. In addition, there's no downside to using irqsafe_* variant when CPU actually supports cmpxchg[_double]. So, let's first fix that and think about CMPXCHG[_DOUBLE]_LOCAL or whatnot later.

Thank you.

Signature · 1 line

tejun

Thomas Gleixner

2011-05-04 14:21 UTC #80 lore raw

Quoted 4 lines · Christoph Lameter

The above should not happen. If a kernel config indicates that there is no cmpxchg16b/cmpxchg8b available then we need to not compile the path that uses cmpxchg8b/cmpxchg16b. Guess we need CMPXCHG_DOUBLE_LOCAL or so.

Oh no, you have perfectly fine replacements for that in percpu.h with irqsafe and preempt safe versions. So why adding another CONFIG from hell which creates even more ifdef mess ?

The whole CONFIG_CMPXCHG_LOCAL ifdeffery in slub.c is horrible and I think it's not necessary at all for two reasons:

1) irqsafe_cpu_cmpxchg() can be emulated cheap and we still have the advantatage of shorter irq disabled sections. And the difference between the current CONFIG_CMPXCHG_LOCAL=n and using the emulation macros with the short irqsave/restore around the access is probably not measurable at all.

2) that would actually test the code under all possible combinations and not splitting the tester base into x86 and !x86. So that bug would have been avoided in the first place.

Thanks,

tglx

Ingo Molnar

2011-05-04 10:13 UTC #81 lore raw