Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1608382 > unrolled thread
| Started by | Dmitry Vyukov <dvyukov@google.com> |
|---|---|
| First post | 2017-03-24 13:50 +0100 |
| Last post | 2017-03-27 15:50 +0200 |
| Articles | 20 on this page of 37 — 5 participants |
Back to article view | Back to linux.kernel
re: locking/atomic: Introduce atomic_try_cmpxchg() Dmitry Vyukov <dvyukov@google.com> - 2017-03-24 13:50 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Dmitry Vyukov <dvyukov@google.com> - 2017-03-24 15:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 15:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 17:50 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@amacapital.net> - 2017-03-24 18:00 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 18:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Dmitry Vyukov <dvyukov@google.com> - 2017-03-24 19:00 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 19:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 19:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@kernel.org> - 2017-03-24 20:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-24 20:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@amacapital.net> - 2017-03-24 20:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 21:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 21:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@amacapital.net> - 2017-03-24 21:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Dmitry Vyukov <dvyukov@google.com> - 2017-03-24 19:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 19:10 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 19:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@amacapital.net> - 2017-03-24 19:50 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-24 20:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 22:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-25 09:00 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-25 19:10 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-25 19:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-25 19:40 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-25 22:20 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-25 23:10 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-27 12:00 +0200
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-25 19:40 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 21:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Andy Lutomirski <luto@kernel.org> - 2017-03-24 21:30 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 22:10 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-24 20:10 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-24 21:50 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Linus Torvalds <torvalds@linux-foundation.org> - 2017-03-24 22:00 +0100
Re: locking/atomic: Introduce atomic_try_cmpxchg() Peter Zijlstra <peterz@infradead.org> - 2017-03-27 14:20 +0200
Re: locking/atomic: Introduce atomic_try_cmpxchg() Dmitry Vyukov <dvyukov@google.com> - 2017-03-27 15:50 +0200
Page 1 of 2 [1] 2 Next page →
| From | Dmitry Vyukov <dvyukov@google.com> |
|---|---|
| Date | 2017-03-24 13:50 +0100 |
| Subject | re: locking/atomic: Introduce atomic_try_cmpxchg() |
| Message-ID | <towPg-1DH-13@gated-at.bofh.it> |
Hi,
I've come across:
commit a9ebf306f52c756c4f9e50ee9a60cd6389d71344
Author: Peter Zijlstra
Date: Wed Feb 1 16:39:38 2017 +0100
locking/atomic: Introduce atomic_try_cmpxchg()
The primitive has subtle difference with all other implementation that
I know of, and can lead to very subtle bugs. Some time ago I've spent
several days debugging a memory corruption caused by similar
implementation. Consider a classical lock-free stack push:
node->next = atomic_read(&head);
do {
} while (!atomic_try_cmpxchg(&head, &node->next, node));
This code is broken with the current implementation, the problem is
with unconditional update of *__po here:
#define __atomic64_try_cmpxchg(type, _p, _po, _n) \
({
\
typeof(_po) __po = (_po); \
typeof(*(_po)) __o = *__po; \
*__po = atomic64_cmpxchg##type((_p), __o, (_n)); \
(*__po == __o);
\
})
In case of success it writes the same value back into *__po, but in
case of cmpxchg success we might have lose ownership of some memory
locations and potentially over what __po has pointed to. The same
holds for the re-read of *__po.
The problem is very easy to overlook in user code (not saying about
the case when developer is already familiar with different semantics
of similar functions (e.g. C/C++ atomic operations, or gcc/clang
atomic builtins)). For this reason cmpxchg implementations usually
update comparand only in case of failure. So I would suggest to change
it to a safer and less surprising alternative:
diff --git a/arch/x86/include/asm/cmpxchg.h b/arch/x86/include/asm/cmpxchg.h
index fb961db51a2a..81fb985f51f4 100644
--- a/arch/x86/include/asm/cmpxchg.h
+++ b/arch/x86/include/asm/cmpxchg.h
@@ -212,7 +212,8 @@ extern void __add_wrong_size(void)
default: \
__cmpxchg_wrong_size(); \
} \
- *_old = __old; \
+ if (!success) \
+ *_old = __old; \
success; \
})
diff --git a/include/linux/atomic.h b/include/linux/atomic.h
index aae5953817d6..f8098157f7c8 100644
--- a/include/linux/atomic.h
+++ b/include/linux/atomic.h
@@ -1023,8 +1023,11 @@ static inline int atomic_dec_if_positive(atomic_t *v)
({ \
typeof(_po) __po = (_po); \
typeof(*(_po)) __o = *__po; \
- *__po = atomic64_cmpxchg##type((_p), __o, (_n)); \
- (*__po == __o); \
+ typeof(*(_po)) __v = atomic64_cmpxchg##type((_p), __o, (_n)); \
+ if (__v == __o) \
+ return true; \
+ *__po = __v; \
+ return false; \
})
[toc] | [next] | [standalone]
| From | Dmitry Vyukov <dvyukov@google.com> |
|---|---|
| Date | 2017-03-24 15:30 +0100 |
| Message-ID | <toyo1-2Pm-5@gated-at.bofh.it> |
| In reply to | #1608382 |
On Fri, Mar 24, 2017 at 3:21 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 01:44:00PM +0100, Dmitry Vyukov wrote:
>>
>> The primitive has subtle difference with all other implementation that
>> I know of, and can lead to very subtle bugs. Some time ago I've spent
>> several days debugging a memory corruption caused by similar
>> implementation. Consider a classical lock-free stack push:
>>
>> node->next = atomic_read(&head);
>> do {
>> } while (!atomic_try_cmpxchg(&head, &node->next, node));
>>
>> This code is broken with the current implementation, the problem is
>> with unconditional update of *__po here:
>
> Indeed. I had only considered stack local variables when I wrote that.
>
>> So I would suggest to change it to a safer and less surprising
>> alternative:
>>
>> diff --git a/arch/x86/include/asm/cmpxchg.h b/arch/x86/include/asm/cmpxchg.h
>> index fb961db51a2a..81fb985f51f4 100644
>> --- a/arch/x86/include/asm/cmpxchg.h
>> +++ b/arch/x86/include/asm/cmpxchg.h
>> @@ -212,7 +212,8 @@ extern void __add_wrong_size(void)
>> default: \
>> __cmpxchg_wrong_size(); \
>> } \
>> - *_old = __old; \
>> + if (!success) \
>> + *_old = __old; \
>> success; \
>> })
>
> I've no immediate objection, I'll double check what, if anything, it
> does for code gen.
>
>> diff --git a/include/linux/atomic.h b/include/linux/atomic.h
>> index aae5953817d6..f8098157f7c8 100644
>> --- a/include/linux/atomic.h
>> +++ b/include/linux/atomic.h
>> @@ -1023,8 +1023,11 @@ static inline int atomic_dec_if_positive(atomic_t *v)
>> ({ \
>> typeof(_po) __po = (_po); \
>> typeof(*(_po)) __o = *__po; \
>> - *__po = atomic64_cmpxchg##type((_p), __o, (_n)); \
>> - (*__po == __o); \
>> + typeof(*(_po)) __v = atomic64_cmpxchg##type((_p), __o, (_n)); \
>> + if (__v == __o) \
>> + return true; \
>> + *__po = __v; \
>> + return false; \
>> })
>
> Can you actually use return in statement-expressions?
Dunno. Just wanted to show the idea.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 15:30 +0100 |
| Message-ID | <toyo1-2Pm-7@gated-at.bofh.it> |
| In reply to | #1608382 |
On Fri, Mar 24, 2017 at 01:44:00PM +0100, Dmitry Vyukov wrote:
>
> The primitive has subtle difference with all other implementation that
> I know of, and can lead to very subtle bugs. Some time ago I've spent
> several days debugging a memory corruption caused by similar
> implementation. Consider a classical lock-free stack push:
>
> node->next = atomic_read(&head);
> do {
> } while (!atomic_try_cmpxchg(&head, &node->next, node));
>
> This code is broken with the current implementation, the problem is
> with unconditional update of *__po here:
Indeed. I had only considered stack local variables when I wrote that.
> So I would suggest to change it to a safer and less surprising
> alternative:
>
> diff --git a/arch/x86/include/asm/cmpxchg.h b/arch/x86/include/asm/cmpxchg.h
> index fb961db51a2a..81fb985f51f4 100644
> --- a/arch/x86/include/asm/cmpxchg.h
> +++ b/arch/x86/include/asm/cmpxchg.h
> @@ -212,7 +212,8 @@ extern void __add_wrong_size(void)
> default: \
> __cmpxchg_wrong_size(); \
> } \
> - *_old = __old; \
> + if (!success) \
> + *_old = __old; \
> success; \
> })
I've no immediate objection, I'll double check what, if anything, it
does for code gen.
> diff --git a/include/linux/atomic.h b/include/linux/atomic.h
> index aae5953817d6..f8098157f7c8 100644
> --- a/include/linux/atomic.h
> +++ b/include/linux/atomic.h
> @@ -1023,8 +1023,11 @@ static inline int atomic_dec_if_positive(atomic_t *v)
> ({ \
> typeof(_po) __po = (_po); \
> typeof(*(_po)) __o = *__po; \
> - *__po = atomic64_cmpxchg##type((_p), __o, (_n)); \
> - (*__po == __o); \
> + typeof(*(_po)) __v = atomic64_cmpxchg##type((_p), __o, (_n)); \
> + if (__v == __o) \
> + return true; \
> + *__po = __v; \
> + return false; \
> })
Can you actually use return in statement-expressions?
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 17:50 +0100 |
| Message-ID | <toAzw-4jh-17@gated-at.bofh.it> |
| In reply to | #1608473 |
On Fri, Mar 24, 2017 at 03:21:40PM +0100, Peter Zijlstra wrote:
> On Fri, Mar 24, 2017 at 01:44:00PM +0100, Dmitry Vyukov wrote:
> > So I would suggest to change it to a safer and less surprising
> > alternative:
> >
> > diff --git a/arch/x86/include/asm/cmpxchg.h b/arch/x86/include/asm/cmpxchg.h
> > index fb961db51a2a..81fb985f51f4 100644
> > --- a/arch/x86/include/asm/cmpxchg.h
> > +++ b/arch/x86/include/asm/cmpxchg.h
> > @@ -212,7 +212,8 @@ extern void __add_wrong_size(void)
> > default: \
> > __cmpxchg_wrong_size(); \
> > } \
> > - *_old = __old; \
> > + if (!success) \
> > + *_old = __old; \
> > success; \
> > })
>
> I've no immediate objection, I'll double check what, if anything, it
> does for code gen.
So the first snipped I tested regressed like so:
0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>:
0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx
2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx
5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21>
7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx
9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e>
b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx
e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax
12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a>
16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx
18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2>
1a: c3 retq 1a: ff c1 inc %ecx
1c: 75 03 jne 21 <T_refcount_inc+0x21>
1e: 0f 0b ud2
20: c3 retq
21: c3 retq
Which is rather unfortunate...
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Date | 2017-03-24 18:00 +0100 |
| Message-ID | <toAJc-4pW-11@gated-at.bofh.it> |
| In reply to | #1608665 |
On Fri, Mar 24, 2017 at 9:41 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 03:21:40PM +0100, Peter Zijlstra wrote:
>> On Fri, Mar 24, 2017 at 01:44:00PM +0100, Dmitry Vyukov wrote:
>
>> > So I would suggest to change it to a safer and less surprising
>> > alternative:
>> >
>> > diff --git a/arch/x86/include/asm/cmpxchg.h b/arch/x86/include/asm/cmpxchg.h
>> > index fb961db51a2a..81fb985f51f4 100644
>> > --- a/arch/x86/include/asm/cmpxchg.h
>> > +++ b/arch/x86/include/asm/cmpxchg.h
>> > @@ -212,7 +212,8 @@ extern void __add_wrong_size(void)
>> > default: \
>> > __cmpxchg_wrong_size(); \
>> > } \
>> > - *_old = __old; \
>> > + if (!success) \
>> > + *_old = __old; \
>> > success; \
>> > })
>>
>> I've no immediate objection, I'll double check what, if anything, it
>> does for code gen.
>
> So the first snipped I tested regressed like so:
>
>
> 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>:
> 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx
> 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx
> 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21>
> 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx
> 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e>
> b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx
> e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax
> 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
> 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a>
> 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx
> 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2>
> 1a: c3 retq 1a: ff c1 inc %ecx
> 1c: 75 03 jne 21 <T_refcount_inc+0x21>
> 1e: 0f 0b ud2
> 20: c3 retq
> 21: c3 retq
Can you re-send the better asm you got earlier?
If I pretend to be a dumb compiler, I wonder if you'd get better results with:
if (!success) {
*_old = __old;
return false;
} else {
return true;
}
or however you jam that into a statement expression. That way you
aren't relying on the compiler to merge the branches.
>
> Which is rather unfortunate...
--
Andy Lutomirski
AMA Capital Management, LLC
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 18:30 +0100 |
| Message-ID | <toBcd-4QJ-5@gated-at.bofh.it> |
| In reply to | #1608678 |
On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote:
> > So the first snipped I tested regressed like so:
> >
> >
> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>:
> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx
> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx
> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21>
> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx
> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e>
> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx
> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax
> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a>
> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx
> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2>
> > 1a: c3 retq 1a: ff c1 inc %ecx
> > 1c: 75 03 jne 21 <T_refcount_inc+0x21>
> > 1e: 0f 0b ud2
> > 20: c3 retq
> > 21: c3 retq
>
> Can you re-send the better asm you got earlier?
On the left?
> If I pretend to be a dumb compiler, I wonder if you'd get better results with:
>
> if (!success) {
> *_old = __old;
> return false;
> } else {
> return true;
> }
>
> or however you jam that into a statement expression. That way you
> aren't relying on the compiler to merge the branches.
I tried a few variants, but nothing really made it better.
Find the tiny.c file below; I'm using:
gcc (Debian 6.3.0-5) 6.3.0 20170124
it has both an inline and an stmt-expr try_cmpxchg variant to play with;
the 'expected' output is at the bottom (same as above left).
Note that clang doesn't compile this stuff due to missing features.
---
/* gcc -Os -std=gnu99 -fno-strict-overflow -falign-jumps=1 -falign-loops=1 -c tiny.c; objdump -dr tiny.o */
typedef _Bool bool;
static inline bool try_cmpxchg(unsigned int *ptr, unsigned int *val, unsigned int new)
{
unsigned int old = *val;
bool success;
asm volatile("lock cmpxchgl %[new], %[ptr]"
: "=@ccz" (success),
[ptr] "+m" (*ptr),
[old] "+a" (old)
: [new] "r" (new)
: "memory");
// if (!success)
*val = old;
return success;
}
#define __try_cmpxchg(_ptr, _pold, _new) \
({ \
bool success; \
__typeof__(_ptr) _old = (_pold); \
__typeof__(*(_ptr)) __old = *_old; \
__typeof__(*(_ptr)) __new = (_new); \
volatile unsigned int * __ptr = (volatile unsigned int *)(_ptr);\
\
asm volatile("lock cmpxchgl %[new], %[ptr]" \
: "=@ccz" (success), \
[ptr] "+m" (*__ptr), \
[old] "+a" (__old) \
: [new] "r" (__new) \
: "memory"); \
/* if (!success) */ \
*_old = __old; \
success; \
})
#define EXCEPTION_VALUE(val, handler) asm volatile ("ud2 # %0" : : "r" (val))
#define UINT_MAX (~0U)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
static inline void refcount_inc(unsigned int *r)
{
unsigned int new, val = *(unsigned int volatile *)r;
do {
if (unlikely(val == UINT_MAX)) /* saturated */
return;
if (unlikely(!val)) /* use-after-free */
goto exception;
/* cannot overflow because we already checked UINT_MAX */
new = val + 1;
} while (unlikely(!try_cmpxchg(r, &val, new)));
if (unlikely(new == UINT_MAX))
exception: EXCEPTION_VALUE(val, __refcount_warn);
}
void T_refcount_inc(unsigned int *r)
{
refcount_inc(r);
}
/*
0: 8b 07 mov (%rdi),%eax
2: 83 f8 ff cmp $0xffffffff,%eax
5: 74 13 je 1a <T_refcount_inc+0x1a>
7: 85 c0 test %eax,%eax
9: 74 0d je 18 <T_refcount_inc+0x18>
b: 8d 50 01 lea 0x1(%rax),%edx
e: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
12: 75 ee jne 2 <T_refcount_inc+0x2>
14: ff c2 inc %edx
16: 75 02 jne 1a <T_refcount_inc+0x1a>
18: 0f 0b ud2
1a: c3 retq
*/
[toc] | [prev] | [next] | [standalone]
| From | Dmitry Vyukov <dvyukov@google.com> |
|---|---|
| Date | 2017-03-24 19:00 +0100 |
| Message-ID | <toBFg-50v-17@gated-at.bofh.it> |
| In reply to | #1608703 |
On Fri, Mar 24, 2017 at 6:23 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote:
>> > So the first snipped I tested regressed like so:
>> >
>> >
>> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>:
>> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx
>> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx
>> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21>
>> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx
>> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e>
>> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx
>> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax
>> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
>> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a>
>> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx
>> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2>
>> > 1a: c3 retq 1a: ff c1 inc %ecx
>> > 1c: 75 03 jne 21 <T_refcount_inc+0x21>
>> > 1e: 0f 0b ud2
>> > 20: c3 retq
>> > 21: c3 retq
>>
>> Can you re-send the better asm you got earlier?
>
> On the left?
>
>> If I pretend to be a dumb compiler, I wonder if you'd get better results with:
>>
>> if (!success) {
>> *_old = __old;
>> return false;
>> } else {
>> return true;
>> }
>>
>> or however you jam that into a statement expression. That way you
>> aren't relying on the compiler to merge the branches.
>
> I tried a few variants, but nothing really made it better.
>
> Find the tiny.c file below; I'm using:
>
> gcc (Debian 6.3.0-5) 6.3.0 20170124
>
> it has both an inline and an stmt-expr try_cmpxchg variant to play with;
> the 'expected' output is at the bottom (same as above left).
>
> Note that clang doesn't compile this stuff due to missing features.
>
> ---
>
> /* gcc -Os -std=gnu99 -fno-strict-overflow -falign-jumps=1 -falign-loops=1 -c tiny.c; objdump -dr tiny.o */
>
> typedef _Bool bool;
>
> static inline bool try_cmpxchg(unsigned int *ptr, unsigned int *val, unsigned int new)
> {
> unsigned int old = *val;
> bool success;
>
> asm volatile("lock cmpxchgl %[new], %[ptr]"
> : "=@ccz" (success),
> [ptr] "+m" (*ptr),
> [old] "+a" (old)
> : [new] "r" (new)
> : "memory");
>
> // if (!success)
> *val = old;
>
> return success;
> }
>
> #define __try_cmpxchg(_ptr, _pold, _new) \
> ({ \
> bool success; \
> __typeof__(_ptr) _old = (_pold); \
> __typeof__(*(_ptr)) __old = *_old; \
> __typeof__(*(_ptr)) __new = (_new); \
> volatile unsigned int * __ptr = (volatile unsigned int *)(_ptr);\
> \
> asm volatile("lock cmpxchgl %[new], %[ptr]" \
> : "=@ccz" (success), \
> [ptr] "+m" (*__ptr), \
> [old] "+a" (__old) \
> : [new] "r" (__new) \
> : "memory"); \
> /* if (!success) */ \
> *_old = __old; \
> success; \
> })
>
> #define EXCEPTION_VALUE(val, handler) asm volatile ("ud2 # %0" : : "r" (val))
>
> #define UINT_MAX (~0U)
>
> #define likely(x) __builtin_expect(!!(x), 1)
> #define unlikely(x) __builtin_expect(!!(x), 0)
>
> static inline void refcount_inc(unsigned int *r)
> {
> unsigned int new, val = *(unsigned int volatile *)r;
>
> do {
> if (unlikely(val == UINT_MAX)) /* saturated */
> return;
>
> if (unlikely(!val)) /* use-after-free */
> goto exception;
>
> /* cannot overflow because we already checked UINT_MAX */
> new = val + 1;
>
> } while (unlikely(!try_cmpxchg(r, &val, new)));
>
> if (unlikely(new == UINT_MAX))
> exception: EXCEPTION_VALUE(val, __refcount_warn);
> }
>
> void T_refcount_inc(unsigned int *r)
> {
> refcount_inc(r);
> }
>
> /*
> 0: 8b 07 mov (%rdi),%eax
> 2: 83 f8 ff cmp $0xffffffff,%eax
> 5: 74 13 je 1a <T_refcount_inc+0x1a>
> 7: 85 c0 test %eax,%eax
> 9: 74 0d je 18 <T_refcount_inc+0x18>
> b: 8d 50 01 lea 0x1(%rax),%edx
> e: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
> 12: 75 ee jne 2 <T_refcount_inc+0x2>
> 14: ff c2 inc %edx
> 16: 75 02 jne 1a <T_refcount_inc+0x1a>
> 18: 0f 0b ud2
> 1a: c3 retq
> */
This seems to help ;)
#define try_cmpxchg(ptr, pold, new) __atomic_compare_exchange_n(ptr,
pold, new, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 19:20 +0100 |
| Message-ID | <toBYD-5oX-45@gated-at.bofh.it> |
| In reply to | #1608736 |
On Fri, Mar 24, 2017 at 06:51:15PM +0100, Dmitry Vyukov wrote: > On Fri, Mar 24, 2017 at 6:23 PM, Peter Zijlstra <peterz@infradead.org> wrote: > > On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote: > >> > So the first snipped I tested regressed like so: > >> > > >> > > >> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>: > >> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx > >> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx > >> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21> > >> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx > >> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e> > >> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx > >> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax > >> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi) > >> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a> > >> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx > >> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2> > >> > 1a: c3 retq 1a: ff c1 inc %ecx > >> > 1c: 75 03 jne 21 <T_refcount_inc+0x21> > >> > 1e: 0f 0b ud2 > >> > 20: c3 retq > >> > 21: c3 retq > >> > This seems to help ;) > > #define try_cmpxchg(ptr, pold, new) __atomic_compare_exchange_n(ptr, pold, new, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) That gets me: 0000000000000000 <T_refcount_inc>: 0: 8b 07 mov (%rdi),%eax 2: 89 44 24 fc mov %eax,-0x4(%rsp) 6: 8b 44 24 fc mov -0x4(%rsp),%eax a: 83 f8 ff cmp $0xffffffff,%eax d: 74 1c je 2b <T_refcount_inc+0x2b> f: 85 c0 test %eax,%eax 11: 75 07 jne 1a <T_refcount_inc+0x1a> 13: 8b 44 24 fc mov -0x4(%rsp),%eax 17: 0f 0b ud2 19: c3 retq 1a: 8d 50 01 lea 0x1(%rax),%edx 1d: 8b 44 24 fc mov -0x4(%rsp),%eax 21: f0 0f b1 17 lock cmpxchg %edx,(%rdi) 25: 75 db jne 2 <T_refcount_inc+0x2> 27: ff c2 inc %edx 29: 74 e8 je 13 <T_refcount_inc+0x13> 2b: c3 retq Which is even worse... (I did double check it actually compiled)
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 19:20 +0100 |
| Message-ID | <toBYE-5oX-53@gated-at.bofh.it> |
| In reply to | #1608803 |
On Fri, Mar 24, 2017 at 07:08:38PM +0100, Peter Zijlstra wrote: > On Fri, Mar 24, 2017 at 06:51:15PM +0100, Dmitry Vyukov wrote: > > On Fri, Mar 24, 2017 at 6:23 PM, Peter Zijlstra <peterz@infradead.org> wrote: > > > On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote: > > >> > So the first snipped I tested regressed like so: > > >> > > > >> > > > >> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>: > > >> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx > > >> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx > > >> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21> > > >> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx > > >> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e> > > >> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx > > >> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax > > >> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi) > > >> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a> > > >> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx > > >> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2> > > >> > 1a: c3 retq 1a: ff c1 inc %ecx > > >> > 1c: 75 03 jne 21 <T_refcount_inc+0x21> > > >> > 1e: 0f 0b ud2 > > >> > 20: c3 retq > > >> > 21: c3 retq > > >> > > > This seems to help ;) > > > > #define try_cmpxchg(ptr, pold, new) __atomic_compare_exchange_n(ptr, pold, new, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) > > That gets me: > > 0000000000000000 <T_refcount_inc>: > 0: 8b 07 mov (%rdi),%eax > 2: 89 44 24 fc mov %eax,-0x4(%rsp) > 6: 8b 44 24 fc mov -0x4(%rsp),%eax > a: 83 f8 ff cmp $0xffffffff,%eax > d: 74 1c je 2b <T_refcount_inc+0x2b> > f: 85 c0 test %eax,%eax > 11: 75 07 jne 1a <T_refcount_inc+0x1a> > 13: 8b 44 24 fc mov -0x4(%rsp),%eax > 17: 0f 0b ud2 > 19: c3 retq > 1a: 8d 50 01 lea 0x1(%rax),%edx > 1d: 8b 44 24 fc mov -0x4(%rsp),%eax > 21: f0 0f b1 17 lock cmpxchg %edx,(%rdi) > 25: 75 db jne 2 <T_refcount_inc+0x2> > 27: ff c2 inc %edx > 29: 74 e8 je 13 <T_refcount_inc+0x13> > 2b: c3 retq > > > Which is even worse... (I did double check it actually compiled) Not to mention we cannot use the C11 atomics in kernel because we want to be able to runtime patch LOCK prefixes when only 1 CPU is available.
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@kernel.org> |
|---|---|
| Date | 2017-03-24 20:20 +0100 |
| Message-ID | <toCUF-63a-3@gated-at.bofh.it> |
| In reply to | #1608809 |
On Fri, Mar 24, 2017 at 11:13 AM, Peter Zijlstra <peterz@infradead.org> wrote: > On Fri, Mar 24, 2017 at 07:08:38PM +0100, Peter Zijlstra wrote: >> On Fri, Mar 24, 2017 at 06:51:15PM +0100, Dmitry Vyukov wrote: >> > On Fri, Mar 24, 2017 at 6:23 PM, Peter Zijlstra <peterz@infradead.org> wrote: >> > > On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote: >> > >> > So the first snipped I tested regressed like so: >> > >> > >> > >> > >> > >> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>: >> > >> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx >> > >> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx >> > >> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21> >> > >> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx >> > >> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e> >> > >> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx >> > >> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax >> > >> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi) >> > >> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a> >> > >> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx >> > >> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2> >> > >> > 1a: c3 retq 1a: ff c1 inc %ecx >> > >> > 1c: 75 03 jne 21 <T_refcount_inc+0x21> >> > >> > 1e: 0f 0b ud2 >> > >> > 20: c3 retq >> > >> > 21: c3 retq >> > >> >> >> > This seems to help ;) >> > >> > #define try_cmpxchg(ptr, pold, new) __atomic_compare_exchange_n(ptr, pold, new, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) >> >> That gets me: >> >> 0000000000000000 <T_refcount_inc>: >> 0: 8b 07 mov (%rdi),%eax >> 2: 89 44 24 fc mov %eax,-0x4(%rsp) >> 6: 8b 44 24 fc mov -0x4(%rsp),%eax >> a: 83 f8 ff cmp $0xffffffff,%eax >> d: 74 1c je 2b <T_refcount_inc+0x2b> >> f: 85 c0 test %eax,%eax >> 11: 75 07 jne 1a <T_refcount_inc+0x1a> >> 13: 8b 44 24 fc mov -0x4(%rsp),%eax >> 17: 0f 0b ud2 >> 19: c3 retq >> 1a: 8d 50 01 lea 0x1(%rax),%edx >> 1d: 8b 44 24 fc mov -0x4(%rsp),%eax >> 21: f0 0f b1 17 lock cmpxchg %edx,(%rdi) >> 25: 75 db jne 2 <T_refcount_inc+0x2> >> 27: ff c2 inc %edx >> 29: 74 e8 je 13 <T_refcount_inc+0x13> >> 2b: c3 retq >> >> >> Which is even worse... (I did double check it actually compiled) > > Not to mention we cannot use the C11 atomics in kernel because we want > to be able to runtime patch LOCK prefixes when only 1 CPU is available. Is this really a show-stopper? I bet that objtool could be persuaded to emit a list of the locations of all those LOCK prefixes. --Andy
[toc] | [prev] | [next] | [standalone]
| From | Linus Torvalds <torvalds@linux-foundation.org> |
|---|---|
| Date | 2017-03-24 20:30 +0100 |
| Message-ID | <toD4l-679-1@gated-at.bofh.it> |
| In reply to | #1608895 |
On Fri, Mar 24, 2017 at 12:16 PM, Andy Lutomirski <luto@kernel.org> wrote:
>>
>> Not to mention we cannot use the C11 atomics in kernel because we want
>> to be able to runtime patch LOCK prefixes when only 1 CPU is available.
>
> Is this really a show-stopper? I bet that objtool could be persuaded
> to emit a list of the locations of all those LOCK prefixes.
I doubt it's a show-stopper, if only because nobody cares about UP any
more. Not even the embedded world does.
That said, I'm not convinced that there will ever really be a reason
for the kernel to use the C11 atomics. They just aren't any better
than what we can do ourselves.
The reason for C11 atomics is "portably good atomics". We use
"architecture-specific good atomics" instead, and are willing to
maintain that. We will *have* to maintain that in the forseeable
future anyway, for legacy compiler issues.
So any C11 atomics use by the kernel is realistically at least a
decade away if it *ever* happens.
Don't even worry about it. Planning decades ahead for some detail like
that is stupid.
Linus
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Date | 2017-03-24 20:30 +0100 |
| Message-ID | <toD4n-679-55@gated-at.bofh.it> |
| In reply to | #1608907 |
On Fri, Mar 24, 2017 at 12:20 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Fri, Mar 24, 2017 at 12:16 PM, Andy Lutomirski <luto@kernel.org> wrote: >>> >>> Not to mention we cannot use the C11 atomics in kernel because we want >>> to be able to runtime patch LOCK prefixes when only 1 CPU is available. >> >> Is this really a show-stopper? I bet that objtool could be persuaded >> to emit a list of the locations of all those LOCK prefixes. > > I doubt it's a show-stopper, if only because nobody cares about UP any > more. Not even the embedded world does. > > That said, I'm not convinced that there will ever really be a reason > for the kernel to use the C11 atomics. They just aren't any better > than what we can do ourselves. > > The reason for C11 atomics is "portably good atomics". We use > "architecture-specific good atomics" instead, and are willing to > maintain that. We will *have* to maintain that in the forseeable > future anyway, for legacy compiler issues. In theory, though, the compiler could optimize based on its knowledge of what the C11 atomics do. ISTR reading about a few optimizations that were already starting to be developed. Using asm goto seems okay, too, but it's a lot more tedious is less friendly to the optimizers. --Andy
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 21:20 +0100 |
| Message-ID | <toDQK-6Kj-17@gated-at.bofh.it> |
| In reply to | #1608907 |
On Fri, Mar 24, 2017 at 12:20:37PM -0700, Linus Torvalds wrote: > I doubt it's a show-stopper, if only because nobody cares about UP any > more. Not even the embedded world does. For some obscure reason we recently introduced a variant for virt people. Where it would need memory barriers against the hypervisor, but having only a single vCPU not against itself.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 21:20 +0100 |
| Message-ID | <toDQK-6Kj-15@gated-at.bofh.it> |
| In reply to | #1608895 |
On Fri, Mar 24, 2017 at 12:16:11PM -0700, Andy Lutomirski wrote: > On Fri, Mar 24, 2017 at 11:13 AM, Peter Zijlstra <peterz@infradead.org> wrote: > > Not to mention we cannot use the C11 atomics in kernel because we want > > to be able to runtime patch LOCK prefixes when only 1 CPU is available. > > Is this really a show-stopper? I bet that objtool could be persuaded > to emit a list of the locations of all those LOCK prefixes. Ah, but its not _all_ LOCK prefixes. Some are needed even on UP, because against hardware instead of other CPUs. Or again hypervisor instead of other vCPU.
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Date | 2017-03-24 21:30 +0100 |
| Message-ID | <toE0q-6Pe-5@gated-at.bofh.it> |
| In reply to | #1608948 |
On Fri, Mar 24, 2017 at 1:14 PM, Peter Zijlstra <peterz@infradead.org> wrote: > On Fri, Mar 24, 2017 at 12:16:11PM -0700, Andy Lutomirski wrote: >> On Fri, Mar 24, 2017 at 11:13 AM, Peter Zijlstra <peterz@infradead.org> wrote: > >> > Not to mention we cannot use the C11 atomics in kernel because we want >> > to be able to runtime patch LOCK prefixes when only 1 CPU is available. >> >> Is this really a show-stopper? I bet that objtool could be persuaded >> to emit a list of the locations of all those LOCK prefixes. > > Ah, but its not _all_ LOCK prefixes. Some are needed even on UP, because > against hardware instead of other CPUs. Or again hypervisor instead of > other vCPU. > Make a table of mandatory lock prefixes and assume all the others (due to C11 atomics, etc) can be omitted on UP? I'm curious, though, whether anyone actually compiles an x86 SMP kernel, runs it on UP, and cares about performance these days. --Andy
[toc] | [prev] | [next] | [standalone]
| From | Dmitry Vyukov <dvyukov@google.com> |
|---|---|
| Date | 2017-03-24 19:20 +0100 |
| Message-ID | <toBYE-5oX-61@gated-at.bofh.it> |
| In reply to | #1608803 |
On Fri, Mar 24, 2017 at 7:08 PM, Peter Zijlstra <peterz@infradead.org> wrote: > On Fri, Mar 24, 2017 at 06:51:15PM +0100, Dmitry Vyukov wrote: >> On Fri, Mar 24, 2017 at 6:23 PM, Peter Zijlstra <peterz@infradead.org> wrote: >> > On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote: >> >> > So the first snipped I tested regressed like so: >> >> > >> >> > >> >> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>: >> >> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx >> >> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx >> >> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21> >> >> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx >> >> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e> >> >> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx >> >> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax >> >> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi) >> >> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a> >> >> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx >> >> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2> >> >> > 1a: c3 retq 1a: ff c1 inc %ecx >> >> > 1c: 75 03 jne 21 <T_refcount_inc+0x21> >> >> > 1e: 0f 0b ud2 >> >> > 20: c3 retq >> >> > 21: c3 retq >> >> > >> This seems to help ;) >> >> #define try_cmpxchg(ptr, pold, new) __atomic_compare_exchange_n(ptr, pold, new, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) > > That gets me: > > 0000000000000000 <T_refcount_inc>: > 0: 8b 07 mov (%rdi),%eax > 2: 89 44 24 fc mov %eax,-0x4(%rsp) > 6: 8b 44 24 fc mov -0x4(%rsp),%eax > a: 83 f8 ff cmp $0xffffffff,%eax > d: 74 1c je 2b <T_refcount_inc+0x2b> > f: 85 c0 test %eax,%eax > 11: 75 07 jne 1a <T_refcount_inc+0x1a> > 13: 8b 44 24 fc mov -0x4(%rsp),%eax > 17: 0f 0b ud2 > 19: c3 retq > 1a: 8d 50 01 lea 0x1(%rax),%edx > 1d: 8b 44 24 fc mov -0x4(%rsp),%eax > 21: f0 0f b1 17 lock cmpxchg %edx,(%rdi) > 25: 75 db jne 2 <T_refcount_inc+0x2> > 27: ff c2 inc %edx > 29: 74 e8 je 13 <T_refcount_inc+0x13> > 2b: c3 retq > > > Which is even worse... (I did double check it actually compiled) For me gcc 7.0.1 generates: 0000000000000330 <T_refcount_inc1>: 330: 55 push %rbp 331: 8b 07 mov (%rdi),%eax 333: 48 89 e5 mov %rsp,%rbp 336: 83 f8 ff cmp $0xffffffff,%eax 339: 74 12 je 34d <T_refcount_inc1+0x1d> 33b: 85 c0 test %eax,%eax 33d: 74 10 je 34f <T_refcount_inc1+0x1f> 33f: 8d 50 01 lea 0x1(%rax),%edx 342: f0 0f b1 17 lock cmpxchg %edx,(%rdi) 346: 75 ee jne 336 <T_refcount_inc1+0x6> 348: 83 fa ff cmp $0xffffffff,%edx 34b: 74 04 je 351 <T_refcount_inc1+0x21> 34d: 5d pop %rbp 34e: c3 retq 34f: 31 c0 xor %eax,%eax 351: 0f 0b ud2 353: 5d pop %rbp 354: c3 retq with: if (!success) \ *_old = __old; \ 0000000000000320 <T_refcount_inc1>: 320: 8b 0f mov (%rdi),%ecx 322: 55 push %rbp 323: 48 89 e5 mov %rsp,%rbp 326: 83 f9 ff cmp $0xffffffff,%ecx 329: 74 2d je 358 <T_refcount_inc1+0x38> 32b: 85 c9 test %ecx,%ecx 32d: 74 25 je 354 <T_refcount_inc1+0x34> 32f: 8d 71 01 lea 0x1(%rcx),%esi 332: 89 c8 mov %ecx,%eax 334: f0 0f b1 37 lock cmpxchg %esi,(%rdi) 338: 89 c2 mov %eax,%edx 33a: 74 20 je 35c <T_refcount_inc1+0x3c> 33c: 83 fa ff cmp $0xffffffff,%edx 33f: 74 17 je 358 <T_refcount_inc1+0x38> 341: 85 d2 test %edx,%edx 343: 74 0f je 354 <T_refcount_inc1+0x34> 345: 8d 72 01 lea 0x1(%rdx),%esi 348: 89 d0 mov %edx,%eax 34a: f0 0f b1 37 lock cmpxchg %esi,(%rdi) 34e: 74 0a je 35a <T_refcount_inc1+0x3a> 350: 89 c2 mov %eax,%edx 352: eb e8 jmp 33c <T_refcount_inc1+0x1c> 354: 31 c9 xor %ecx,%ecx 356: 0f 0b ud2 358: 5d pop %rbp 359: c3 retq 35a: 89 d1 mov %edx,%ecx 35c: 83 fe ff cmp $0xffffffff,%esi 35f: 74 f5 je 356 <T_refcount_inc1+0x36> 361: 5d pop %rbp 362: c3 retq with __atomic_compare_exchange_n: exactly the same as the original code. But I don't have an answer for runtime patching of LOCK. Looks like something to fix in gcc.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 19:10 +0100 |
| Message-ID | <toBOY-5jj-73@gated-at.bofh.it> |
| In reply to | #1608703 |
On Fri, Mar 24, 2017 at 07:00:25PM +0100, Peter Zijlstra wrote:
> static inline bool try_cmpxchg2(unsigned int *ptr, unsigned int *val, unsigned int new)
> {
> unsigned int old = *val;
> bool success;
>
> asm volatile goto("lock cmpxchgl %[new], %[ptr]; "
> "jnz %[label]"
> : /* no output */
> : [ptr] "+m" (*ptr),
> [old] "+a" (old)
> [new] "r" (new)
> : "memory"
> : label);
> return 1;
>
> label:
> *val = old;
> return 0;
> }
N/m, I'm apparently so tired I didn't see the compiler errors :/
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-24 19:20 +0100 |
| Message-ID | <toBOY-5jj-75@gated-at.bofh.it> |
| In reply to | #1608703 |
On Fri, Mar 24, 2017 at 06:23:42PM +0100, Peter Zijlstra wrote:
> I tried a few variants, but nothing really made it better.
>
> Find the tiny.c file below; I'm using:
>
> gcc (Debian 6.3.0-5) 6.3.0 20170124
>
> it has both an inline and an stmt-expr try_cmpxchg variant to play with;
> the 'expected' output is at the bottom (same as above left).
>
> Note that clang doesn't compile this stuff due to missing features.
>
static inline bool try_cmpxchg2(unsigned int *ptr, unsigned int *val, unsigned int new)
{
unsigned int old = *val;
bool success;
asm volatile goto("lock cmpxchgl %[new], %[ptr]; "
"jnz %[label]"
: /* no output */
: [ptr] "+m" (*ptr),
[old] "+a" (old)
[new] "r" (new)
: "memory"
: label);
return 1;
label:
*val = old;
return 0;
}
generates better code than the @cc output with extra if (!success), but
not as good as the original.
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Date | 2017-03-24 19:50 +0100 |
| Message-ID | <toCrE-5z0-7@gated-at.bofh.it> |
| In reply to | #1608703 |
On Fri, Mar 24, 2017 at 10:23 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 09:54:46AM -0700, Andy Lutomirski wrote:
>> > So the first snipped I tested regressed like so:
>> >
>> >
>> > 0000000000000000 <T_refcount_inc>: 0000000000000000 <T_refcount_inc>:
>> > 0: 8b 07 mov (%rdi),%eax 0: 8b 17 mov (%rdi),%edx
>> > 2: 83 f8 ff cmp $0xffffffff,%eax 2: 83 fa ff cmp $0xffffffff,%edx
>> > 5: 74 13 je 1a <T_refcount_inc+0x1a> 5: 74 1a je 21 <T_refcount_inc+0x21>
>> > 7: 85 c0 test %eax,%eax 7: 85 d2 test %edx,%edx
>> > 9: 74 0d je 18 <T_refcount_inc+0x18> 9: 74 13 je 1e <T_refcount_inc+0x1e>
>> > b: 8d 50 01 lea 0x1(%rax),%edx b: 8d 4a 01 lea 0x1(%rdx),%ecx
>> > e: f0 0f b1 17 lock cmpxchg %edx,(%rdi) e: 89 d0 mov %edx,%eax
>> > 12: 75 ee jne 2 <T_refcount_inc+0x2> 10: f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
>> > 14: ff c2 inc %edx 14: 74 04 je 1a <T_refcount_inc+0x1a>
>> > 16: 75 02 jne 1a <T_refcount_inc+0x1a> 16: 89 c2 mov %eax,%edx
>> > 18: 0f 0b ud2 18: eb e8 jmp 2 <T_refcount_inc+0x2>
>> > 1a: c3 retq 1a: ff c1 inc %ecx
>> > 1c: 75 03 jne 21 <T_refcount_inc+0x21>
>> > 1e: 0f 0b ud2
>> > 20: c3 retq
>> > 21: c3 retq
>>
>> Can you re-send the better asm you got earlier?
>
> On the left?
Apparently I'm just blind this morning.
*/
After playing with it a bit, I found some of the problem: you're
passing val into EXCEPTION_VALUE, which keeps it live. If I get rid
of that, the generated code is great.
I haven't found a way to convince GCC that, in the success case, eax
isn't clobbered. I wrote this:
static inline bool try_cmpxchg(unsigned int *ptr, unsigned int *val,
unsigned int new)
{
unsigned int old = *val;
bool success;
asm volatile("lock cmpxchgl %[new], %[ptr]"
: "=@ccz" (success),
[ptr] "+m" (*ptr),
[old] "+a" (old)
: [new] "r" (new)
: "memory");
if (!success) {
*val = old;
} else {
if (*val != old) {
*val = old;
__builtin_unreachable();
} else {
/*
* Damnit, GCC, I want you to realize that this
* is happening but to avoid emitting the store.
*/
*val = old; /* <-- here */
}
}
return success;
}
The "here" line is the problematic code that breaks certain use cases,
and it obviously needn't have any effect in the generated code, but
I'm having trouble getting GCC to generate good code without it.
Is there some hack like if __builtin_is_unescaped(*val) *val = old;
that would work?
--Andy
[toc] | [prev] | [next] | [standalone]
| From | Linus Torvalds <torvalds@linux-foundation.org> |
|---|---|
| Date | 2017-03-24 20:20 +0100 |
| Message-ID | <toCUG-63a-25@gated-at.bofh.it> |
| In reply to | #1608865 |
On Fri, Mar 24, 2017 at 11:45 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>
> Is there some hack like if __builtin_is_unescaped(*val) *val = old;
> that would work?
See my recent email suggesting a completely different interface, which
avoids this problem.
My interface generates:
0000000000000000 <T_refcount_inc>:
0: 8b 07 mov (%rdi),%eax
2: 83 f8 ff cmp $0xffffffff,%eax
5: 74 12 je 19 <T_refcount_inc+0x19>
7: 85 c0 test %eax,%eax
9: 74 0a je 15 <T_refcount_inc+0x15>
b: 8d 50 01 lea 0x1(%rax),%edx
e: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
12: 75 ee jne 2 <T_refcount_inc+0x2>
14: c3 retq
15: 31 c0 xor %eax,%eax
17: 0f 0b ud2
19: c3 retq
for PeterZ's test-case, which seems optimal.
Of course, PeterZ used -Os, which isn't actually very natural for the
kernel. Using -O2 I get something else. It turns out that my macro
should use
if (likely(__txchg_success)) goto success_label;
(that "likely()" is criticial) to make gcc not try to optimize for the
looping case.
So with that "likely()" fixed, with -O2 I get:
0000000000000000 <T_refcount_inc>:
0: 8b 07 mov (%rdi),%eax
2: 83 f8 ff cmp $0xffffffff,%eax
5: 74 0d je 14 <T_refcount_inc+0x14>
7: 85 c0 test %eax,%eax
9: 74 12 je 1d <T_refcount_inc+0x1d>
b: 8d 50 01 lea 0x1(%rax),%edx
e: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
12: 75 02 jne 16 <T_refcount_inc+0x16>
14: f3 c3 repz retq
16: 83 f8 ff cmp $0xffffffff,%eax
19: 75 ec jne 7 <T_refcount_inc+0x7>
1b: f3 c3 repz retq
1d: 31 c0 xor %eax,%eax
1f: 0f 0b ud2
21: c3 retq
which again looks pretty optimal (it did indeed actually generate
bigger but potentially higher-performance code by making the good case
be a fallthrough, and the unlikely case be a _forward_ jump that will
be predicted not-taken in the absense of other rpediction information.
(Of course, this also depends on the exact behavior that PeterZ's code
had, namely an exception for use-after-free, but a silent saturation)
Linus
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | linux.kernel
csiph-web