bitops: add _local bitops
Subsystems (6)
PATCH 1/1 bitops: add _local bitops
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
At Peter Anvin's suggestion, add _local bitops for this purpose:
define them as non-atomics for x86 and (for now) atomics for everyone else.
Uses are not restricted to virtualization: they might be useful to communicate with an interrupt handler if we know that it's running on the same CPU.
---
Link to previous discussion:
http://www.spinics.net/lists/kvm/msg72241.html
Documentation/atomic_ops.txt | 19 ++++++ arch/x86/include/asm/bitops.h | 1 + include/asm-generic/bitops.h | 1 + include/asm-generic/bitops/local-atomic.h | 92 +++++++++++++++++++++++++++++ include/asm-generic/bitops/local.h | 85 ++++++++++++++++++++++++++ include/linux/bitops.h | 8 +++ 6 files changed, 206 insertions(+), 0 deletions(-) create mode 100644 include/asm-generic/bitops/local-atomic.h create mode 100644 include/asm-generic/bitops/local.h
Documentation/atomic_ops.txt +19 -0
@@ -520,6 +520,25 @@ The __clear_bit_unlock version is non-atomic, however it still implements unlock barrier semantics. This can be useful if the lock itself is protecting the other bits in the word. +Local versions of the bitmask operations are also provided. They are used in +contexts where the operations need to be performed atomically with respect to +the local CPU, but no other CPU accesses the bitmask. This assumption makes it +possible to avoid the need for SMP protection and use less expensive atomic +operations in the implementation. +They have names similar to the above bitmask operation interfaces, +except that _local is sufficed to the interface name. + + void set_bit_local(unsigned long nr, volatile unsigned long *addr); + void clear_bit_local(unsigned long nr, volatile unsigned long *addr); + void change_bit_local(unsigned long nr, volatile unsigned long *addr); + int test_and_set_bit_local(unsigned long nr, volatile unsigned long *addr); + int test_and_clear_bit_local(unsigned long nr, volatile unsigned long *addr); + int test_and_change_bit_local(unsigned long nr, volatile unsigned long *addr); + +These local variants are useful for example if the bitmask may be accessed from +a local intrerrupt, or from a hypervisor on the same CPU if running in a VM. +These local variants also do not have any special memory barrier semantics. + Finally, there are non-atomic versions of the bitmask operations provided. They are used in contexts where some other higher-level SMP locking scheme is being used to protect the bitmask, and thus less
arch/x86/include/asm/bitops.h +1 -0
@@ -509,6 +509,7 @@ static __always_inline int fls64(__u64 x)#include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic-setbit.h> +#include <asm-generic/bitops/local.h> #endif /* __KERNEL__ */ #endif /* _ASM_X86_BITOPS_H */
include/asm-generic/bitops.h +1 -0
@@ -40,5 +40,6 @@#include <asm-generic/bitops/non-atomic.h> #include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic.h> +#include <asm-generic/bitops/local-atomic.h> #endif /* __ASM_GENERIC_BITOPS_H */
include/asm-generic/bitops/local-atomic.h new file +92 -0
92 lines not on this page · raw message
include/asm-generic/bitops/local.h new file +85 -0
85 lines not on this page · raw message
include/linux/bitops.h +8 -0
@@ -197,5 +197,13 @@ extern unsigned long find_last_bit(const unsigned long *addr, unsigned long size);#endif +/** +* Include the generic version for local atomics unless +* an architecture overrides it. +* */ +#ifndef HAVE_ASM_BITOPS_LOCAL +#include "include/asm-generic/bitops/local-atomic.h" +#endif +#endif /* __KERNEL__ */ #endif
Signature · 1 line
MST
H. Peter Anvin
reviewerQuoted 10 lines · Michael S. Tsirkin
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
At Peter Anvin's suggestion, add
_localbitops for this purpose:
define them as non-atomics for x86 and (for now) atomics for everyone else.
Quoted 5 lines
Uses are not restricted to virtualization: they might be useful to communicate with an interrupt handler if we know that it's running on the same CPU.
Signed-off-by Michael S. Tsirkin <[email protected]>
I don't think you can use the x86 nonatomics as-is, because they don't contain optimization barriers.
-hpa
Quoted 7 lines · Michael S. Tsirkin
Documentation/atomic_ops.txt | 19 ++++++ arch/x86/include/asm/bitops.h | 1 + include/asm-generic/bitops.h | 1 + include/asm-generic/bitops/local-atomic.h | 92 +++++++++++++++++++++++++++++ include/asm-generic/bitops/local.h | 85 ++++++++++++++++++++++++++ include/linux/bitops.h | 8 +++ 6 files changed, 206 insertions(+), 0 deletions(-)
Unless I'm misreading the patch, you have two versions of the same file here, where one version should be enough.
Both versions look fine to me though, so if you remove one of them:
Documentation/atomic_ops.txt The __clear_bit_unlock version is non-atomic, however it still implements · line 529
Quoted 8 lines · Michael S. Tsirkin
Documentation/atomic_ops.txt +7
-0+Local versions of the bitmask operations are also provided. They are used in +contexts where the operations need to be performed atomically with respect to +the local CPU, but no other CPU accesses the bitmask. This assumption makes it +possible to avoid the need for SMP protection and use less expensive atomic +operations in the implementation. +They have names similar to the above bitmask operation interfaces, +except that _local is sufficed to the interface name.
suffixed (better: appended)
Signature · 1 line
error compiling committee.c: too many arguments to function
Quoted 15 lines · H. Peter Anvin
Quoted 14 lines · Michael S. Tsirkin
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
At Peter Anvin's suggestion, add
_localbitops for this purpose:
define them as non-atomics for x86 and (for now) atomics for everyone else.Uses are not restricted to virtualization: they might be useful to communicate with an interrupt handler if we know that it's running on the same CPU.
Quoted 6 lines
Quoted 1 line
Signed-off-by Michael S. Tsirkin <[email protected]>I don't think you can use the x86 nonatomics as-is, because they don't contain optimization barriers.
-hpa
You are right of course. So I'll remove bitops/local.h move the code to x86/ and open-code.
Signature · 1 line
MST
Quoted 15 lines · H. Peter Anvin
Quoted 14 lines · Michael S. Tsirkin
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
At Peter Anvin's suggestion, add
_localbitops for this purpose:
define them as non-atomics for x86 and (for now) atomics for everyone else.Uses are not restricted to virtualization: they might be useful to communicate with an interrupt handler if we know that it's running on the same CPU.
Quoted 6 lines
Quoted 1 line
Signed-off-by Michael S. Tsirkin <[email protected]>I don't think you can use the x86 nonatomics as-is, because they don't contain optimization barriers.
-hpa
Just adding a memory clobber to asm will be enough, right?
Signature · 1 line
MST
H. Peter Anvin
reviewerQuoted 3 lines · Michael S. Tsirkin
Just adding a memory clobber to asm will be enough, right?
Yes.
-hpa
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
Quoted 15 lines · H. Peter Anvin
Quoted 14 lines · Michael S. Tsirkin
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
At Peter Anvin's suggestion, add
_localbitops for this purpose:
define them as non-atomics for x86 and (for now) atomics for everyone else.Uses are not restricted to virtualization: they might be useful to communicate with an interrupt handler if we know that it's running on the same CPU.
Quoted 6 lines
Quoted 1 line
Signed-off-by Michael S. Tsirkin <[email protected]>I don't think you can use the x86 nonatomics as-is, because they don't contain optimization barriers.
-hpa
By the way, clear_bit on x86 does not seem to contain an optimization barrier - is my reading correct? Lock prefix does not affect the compiler, right?
H. Peter Anvin
reviewerQuoted 4 lines · Michael S. Tsirkin
By the way,
clear_biton x86 does not seem to contain an optimization barrier - is my reading correct? Lock prefix does not affect the compiler, right?
Yes, as it clearly states in the comment:
* clear_bit() is atomic and may not be reordered. However, it does
* not contain a memory barrier, so if it is used for locking purposes,
* you should call smp_mb__before_clear_bit() and/orsmp_mb__after_clear_bit()
* in order to ensure changes are visible on other processors.
There is clear_bit_unlock() which has the barrier semantics.
-hpa
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
Quoted 14 lines · H. Peter Anvin
Quoted 4 lines · Michael S. Tsirkin
By the way,
clear_biton x86 does not seem to contain an optimization barrier - is my reading correct? Lock prefix does not affect the compiler, right?Yes, as it clearly states in the comment:
*
clear_bit()is atomic and may not be reordered. However, it does
* not contain a memory barrier, so if it is used for locking purposes,
* you should callsmp_mb__before_clear_bit()and/orsmp_mb__after_clear_bit()
* in order to ensure changes are visible on other processors.
Quoted 3 lines
There is
clear_bit_unlock()which has the barrier semantics.-hpa
Well it talks about a memory barrier, not an
optimization barrier.
If compiler reorders code, changes will appear in
the wrong order on the current processor,
not just on other processors, no?
Sorry if I'm confused about this point, this is what Documentation/atomic_ops.txt made me believe:
<quote>
For example consider the following code: while (a > 0) do_something(); If the compiler can prove that do_something() does not store to the variable a, then the compiler is within its rights transforming this to the following: tmp = a; if (a > 0) for (;;) do_something();
</quote>
Quoted 4 lines
Signature · 3 lines
-- H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
H. Peter Anvin
reviewerQuoted 4 lines · Michael S. Tsirkin
Well it talks about a memory barrier, not an
optimization barrier.
Same thing.
Quoted 3 lines
If compiler reorders code, changes will appear in
the wrong order on the current processor,
not just on other processors, no?
Yes.
For your _local I would just copy the atomic bitops but remote the locks in most cases.
-hpa
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
Quoted 7 lines · H. Peter Anvin
Quoted 4 lines · Michael S. Tsirkin
Well it talks about a memory barrier, not an
optimization barrier.Same thing.
I see. So it really should say 'any barrier', right? Documentation/atomic_ops.txt goes to great length to distinguish between the two and we probably should not confuse things.
Quoted 5 lines
Quoted 3 lines
If compiler reorders code, changes will appear in
the wrong order on the current processor,
not just on other processors, no?Yes.
So this seems to contradict what the comment says:
clear_bit() is atomic and may not be reordered.
and you say compiler *can* reorder it, and below
you should call smp_mb__before_clear_bit() and/or * smp_mb__after_clear_bit() in order to ensure changes are visible on other processors.
and in fact this is not enough, you also need to call barrier() to ensure changes are visible on the same processor in the correct order.
Quoted 4 lines
For your
_localI would just copy the atomic bitops but remote the locks in most cases.-hpa
Right, I sent v2 that does exactly this.
My question about documentation for change_bit
is an unrelated one: to me, it looks like the documentation for change_bit does not match the implementation, or at least is somewhat confusing.
Quoted 3 lines
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
Quoted 5 lines · On Wed, 9 May 2012 16:45:29 +0300 "Michael S. Tsirkin" <[email protected]> wrote:
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
Well. It adds more complexity, makes the kernel harder to understand and maintain and introduces more opportunities for developers to add bugs. So from that point of view, the best way of handling this patch is to delete it.
Presumably the patch offers some benefit to offest all those costs. But you didn't tell us what that benefit is, so we cannot make a decision.
IOW: numbers, please. Convincing ones, for realistic test cases.
Secondly: can KVM just use __set_bit() and friends? I suspect those interfaces happen to meet your requirements. At least on architectures you care about.
H. Peter Anvin
reviewerQuoted 5 lines · Andrew Morton
Secondly: can KVM just use
__set_bit()and friends? I suspect those interfaces happen to meet your requirements. At least on architectures you care about.
__set_bit() and friends right now don't have optimization barriers, meaning the compiler is free to move them around.
-hpa
Quoted 14 lines · Andrew Morton
Quoted 5 lines · On Wed, 9 May 2012 16:45:29 +0300 "Michael S. Tsirkin" <[email protected]> wrote:
kvm needs to update some hypervisor variables atomically in a sense that the operation can't be interrupted in the middle. However the hypervisor always runs on the same CPU so it does not need any memory barrier or lock prefix.
Well. It adds more complexity, makes the kernel harder to understand and maintain and introduces more opportunities for developers to add bugs. So from that point of view, the best way of handling this patch is to delete it.
Quoted 5 lines
Presumably the patch offers some benefit to offest all those costs. But you didn't tell us what that benefit is, so we cannot make a decision.
IOW: numbers, please. Convincing ones, for realistic test cases.
I can try but in practice it's not an optimization.
What kvm needs is a guarantee that a memory update will be done in a single instruction.
Quoted 3 lines
Secondly: can KVM just use
__set_bit()and friends? I suspect those interfaces happen to meet your requirements. At least on architectures you care about.
Sigh. I started with this, but then Avi Kivity said that he's worried about someone changing __test_and_clear_bit on x86
such that the change won't be atomic (single instruction) anymore. So I put inline asm into kvm.c. This drew comment from Peter that maintaining separate asm code in kvm.c adds too much maintainance overhead so I should implement _local, add asm-generic fallback and put it all in generic code.
In practice ATM any of the above will work. We probably don't even need to add barrier() calls since what we do afterwards is apic access which has an optimization barrier anyway. But I'm fine with adding them in there just in case if that's what people want.
However, since we've come full circle, I'd like to have a discussion on what, exactly, is acceptable to all maintainers.
Avi, Andrew, Peter, could you please comment?
Signature · 1 line
MST
H. Peter Anvin
reviewerQuoted 6 lines · Michael S. Tsirkin
In practice ATM any of the above will work. We probably don't even need to add
barrier()calls since what we do afterwards is apic access which has an optimization barrier anyway. But I'm fine with adding them in there just in case if that's what people want.
If you have the optimization barrier anyway, then I'd be fine with you just using __test_and_clear_bit() and add to a comment in arch/x86/include/asm/bitops.h that KVM needs it to be locally atomic.
-hpa
Quoted 8 lines · H. Peter Anvin
Quoted 6 lines · Michael S. Tsirkin
In practice ATM any of the above will work. We probably don't even need to add
barrier()calls since what we do afterwards is apic access which has an optimization barrier anyway. But I'm fine with adding them in there just in case if that's what people want.
Quoted 5 lines
If you have the optimization barrier anyway, then I'd be fine with you just using
__test_and_clear_bit()and add to a comment inarch/x86/include/asm/bitops.hthat KVM needs it to be locally atomic.-hpa
Sounds good. Avi?
Quoted 9 lines · Michael S. Tsirkin
Quoted 8 lines · H. Peter Anvin
Quoted 6 lines · Michael S. Tsirkin
In practice ATM any of the above will work. We probably don't even need to add
barrier()calls since what we do afterwards is apic access which has an optimization barrier anyway. But I'm fine with adding them in there just in case if that's what people want.
Quoted 7 lines
Quoted 5 lines
If you have the optimization barrier anyway, then I'd be fine with you just using
__test_and_clear_bit()and add to a comment inarch/x86/include/asm/bitops.hthat KVM needs it to be locally atomic.-hpa
Sounds good. Avi?
Okay.
Signature · 1 line
error compiling committee.c: too many arguments to function
Quoted 20 lines · Michael S. Tsirkin
Documentation/atomic_ops.txt +12
-0@@ -520,6 +520,25 @@ The __clear_bit_unlock version is non-atomic, however it still implements unlock barrier semantics. This can be useful if the lock itself is protecting the other bits in the word. +Local versions of the bitmask operations are also provided. They are used in +contexts where the operations need to be performed atomically with respect to +the local CPU, but no other CPU accesses the bitmask. This assumption makes it +possible to avoid the need for SMP protection and use less expensive atomic +operations in the implementation. +They have names similar to the above bitmask operation interfaces, +except that _local is sufficed to the interface name. + + void set_bit_local(unsigned long nr, volatile unsigned long *addr); + void clear_bit_local(unsigned long nr, volatile unsigned long *addr); + void change_bit_local(unsigned long nr, volatile unsigned long *addr); + int test_and_set_bit_local(unsigned long nr, volatile unsigned long *addr);
Documentation/atomic_ops.txt The __clear_bit_unlock version is non-atomic, however it still implements · line 544
Quoted 10 lines
Documentation/atomic_ops.txt +7
-0+ int test_and_clear_bit_local(unsigned long nr, volatile unsigned long *addr); + int test_and_change_bit_local(unsigned long nr, volatile unsigned long *addr); + +These local variants are useful for example if the bitmask may be accessed from +a local intrerrupt, or from a hypervisor on the same CPU if running in a VM. +These local variants also do not have any special memory barrier semantics. + Finally, there are non-atomic versions of the bitmask operations provided. They are used in contexts where some other higher-level SMP locking scheme is being used to protect the bitmask, and thus less
For this bit:
Rob
Signature · 2 lines
GNU/Linux isn't: Linux=GPLv2, GNU=GPLv3+, they can't share code. Either it's "mere aggregation", or a license violation. Pick one.
Quoted 8 lines · H. Peter Anvin
Quoted 6 lines · Michael S. Tsirkin
In practice ATM any of the above will work. We probably don't even need to add
barrier()calls since what we do afterwards is apic access which has an optimization barrier anyway. But I'm fine with adding them in there just in case if that's what people want.
Quoted 5 lines
If you have the optimization barrier anyway, then I'd be fine with you just using
__test_and_clear_bit()and add to a comment inarch/x86/include/asm/bitops.hthat KVM needs it to be locally atomic.
What is it used for ? IE. Is this strictly a requirement of x86 KVM ?
Cheers,
Ben.