[RFC PATCH] docs: add README.atomic

[RFC PATCH] docs: add README.atomic

[Andre Przywara]

Recently there were some discussions about the nature and guarantees of
the atomic primitives that Xen provides.
This README.atomic file tries to document our expectations in those
functions and macros.

Signed-off-by: Andre Przywara <andre.przywara@arm.com>
---
Hi,

as mentioned in my previous mail, I consider this more of a discussion
base that an actual patch. I am by no means an expert in this area, so
part of this exercise here is to write down my understanding and see it
corrected by more knowledgable people ;-)

Cheers,
Andre.

 docs/README.atomic | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)
 create mode 100644 docs/README.atomic

diff --git a/docs/README.atomic b/docs/README.atomic
new file mode 100644
index 0000000..57ec59b
--- /dev/null
+++ b/docs/README.atomic
@@ -0,0 +1,116 @@
+Atomic operations in Xen
+========================
+
+Data structures in Xen memory which can be accessed by multiple CPUs
+at the same time need to be protected against getting corrupted.
+The easiest way to do this is using a lock (spinlock in Xen's case),
+that guarantees that only one CPU can access that memory at a given point
+in time, also allows protecting whole data structures against becoming
+inconsistent. For most use cases this should be the way to go and programmers
+should stop reading here.
+
+However sometimes taking and releasing a lock is too costly or creates
+deadlocks or potential contention, so some lockless accesses are used.
+Those atomic accesses need to be done very carefully to be correct.
+
+Xen offers three kinds of atomic primitives that deal with those accesses:
+
+ACCESS_ONCE()
+-------------
+A macro basically casting the access to a volatile data type. That prevents
+the compiler from accessing that memory location multiple times, effectively
+caching this value (either in a register or on the stack).
+In terms of atomicity this prevents inconsistent values for a certain shared
+variable if used multiple times across the same function, as the compiler is
+normally free to re-read the value from memory at any time - given that it
+doesn't know that another entity might change this value. Consider the
+following code:
+===========
+        int x = shared_pointer->counter;
+
+        some_var = x + something_else;
+        function_call(x);
+===========
+The compiler is free to actually *not* use a local variable, instead derefence
+the pointer and directly access the shared memory twice when using the value
+of "x" in the assignment and in the function call. Now if some other CPU
+changes the value of "counter" meanwhile, the value of "x" is different,
+which violates the program semantic. The compiler is not to blame here,
+because it cannot know that this memory could change behind its back.
+The solution here is to use ACCESS_ONCE, which casts the access with the
+"volatile" keyword, thus making sure that the compiler knows that
+accessing this memory has side effects, so it needs to cache the value:
+===========
+        int x = ACCESS_ONCE(shared_pointer->counter);
+
+        some_var = x + something_else;
+        function_call(x);
+===========
+
+What ACCESS_ONCE does *not* guarantee though is this access is done in a
+single instruction, so complex or non-native or unaligned data types are
+not guaranteed to be atomic. If for instance counter would be a 64-bit value
+on a 32-bit system, the compiler would probably generate two load instructions,
+which could end up in reading a wrong value if some other CPU changes the other
+half of the variable in between those two reads.
+However accessing _aligned and native_ data types is guaranteed to be atomic
+in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
+these conditions are met.
+We expect a variable to be aligned if it comes from a non-packed struct or
+some other compiler-generated address, as sane compilers will not generate
+unaligned accesses by default.
+Extra care must be taken however if the address is coming from a crafted
+pointer or some address passed in by a non-trusted source (guests).
+
+read_atomic()/write_atomic()
+----------------------------
+read_atomic() and write_atomic() are macros that make sure that the access
+to this variable happens using a single machine instruction. This guarantees
+the access to be atomic when the address is aligned (on all architectures
+supported by Xen).
+For most practical cases the generated code does not differ from what
+the compiler would generate anyway, but it makes sure that a change to an
+unsuitable data type would break compilation, also it annotates this access
+as being potentially concurrent (to a human reader).
+Also this macro does not check whether the address is actually aligned,
+though it is assumed that the compiler only generates aligned addresses
+unless being told otherwise explicitly. In the latter case it would be the
+responsibility of the coder to ensure atomicity using other means.
+
+atomic_read()/atomic_write() (and other variants starting with "atomic_")
+-------------------------------------------------------------------------
+(Not to be confused with the above!)
+Those (group of) functions work on a special atomic_t data type, which wraps
+an "int" in a structure to avoid accidential messing with the data type
+(for instance due to implicit casts). As a side effect this guarantees that
+this variable is aligned (though this would apply to most other "int"
+declarations as well). This special data type also makes sure that any
+accesses are only valid using those special accessor functions, which
+make sure that the atomic property is always preserved.
+On top of the basic read/write accesses this also provides read-modify-write
+primitives which use architecture specific means to guarantee atomic accesses
+(atomic_inc(), atomic_dec_and_test(), ...).
+
+
+It has to be noted that following the letters of the C standard a
+standards-compliant compiler has quite some freedom to generate code which
+would make a lot of accesses non-atomic (for instance splitting a 32-bit
+read into a series of four 8-bit reads).
+However a sane compiler, especially when following a certain ABI, would
+for instance always try to align variables and use as few machine
+instructions as possible, so for practical purposes most accesses are
+actually atomic without further ado, especially when being confined to
+certain architectures (like x86, ARM and ARM64 in Xen).
+
+So for practical purposes we assume a sane compiler to be used for Xen,
+with the following properties:
+- Compiler generated addresses for native-data-typed variables are aligned.
+- Simple read/write accesses to a native and aligned data type from compiler
+  generated addresses are done using a single machine instruction.
+
+This makes read and write accesses to ints and longs (and their respective
+unsigned counter parts) naturally atomic.
+However it would be beneficial to use atomic primitives anyway to annotate
+the code as being concurrent and to prevent silent breakage when changing
+the code. Modern compilers tend to optimize quite well, often resulting in
+the same code to be generated for both the annotated and naive version.
-- 
2.9.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Stefano Stabellini]

On Tue, 13 Jun 2017, Andre Przywara wrote:
> Recently there were some discussions about the nature and guarantees of
> the atomic primitives that Xen provides.
> This README.atomic file tries to document our expectations in those
> functions and macros.
> 
> Signed-off-by: Andre Przywara <andre.przywara@arm.com>
> ---
> Hi,
> 
> as mentioned in my previous mail, I consider this more of a discussion
> base that an actual patch. I am by no means an expert in this area, so
> part of this exercise here is to write down my understanding and see it
> corrected by more knowledgable people ;-)
> 
> Cheers,
> Andre.
> 
>  docs/README.atomic | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 116 insertions(+)
>  create mode 100644 docs/README.atomic
> 
> diff --git a/docs/README.atomic b/docs/README.atomic
> new file mode 100644
> index 0000000..57ec59b
> --- /dev/null
> +++ b/docs/README.atomic
> @@ -0,0 +1,116 @@
> +Atomic operations in Xen
> +========================
> +
> +Data structures in Xen memory which can be accessed by multiple CPUs
> +at the same time need to be protected against getting corrupted.
> +The easiest way to do this is using a lock (spinlock in Xen's case),
> +that guarantees that only one CPU can access that memory at a given point
> +in time, also allows protecting whole data structures against becoming
> +inconsistent. For most use cases this should be the way to go and programmers
> +should stop reading here.
> +
> +However sometimes taking and releasing a lock is too costly or creates
> +deadlocks or potential contention, so some lockless accesses are used.
> +Those atomic accesses need to be done very carefully to be correct.
> +
> +Xen offers three kinds of atomic primitives that deal with those accesses:
> +
> +ACCESS_ONCE()
> +-------------
> +A macro basically casting the access to a volatile data type. That prevents
> +the compiler from accessing that memory location multiple times, effectively
> +caching this value (either in a register or on the stack).
> +In terms of atomicity this prevents inconsistent values for a certain shared
> +variable if used multiple times across the same function, as the compiler is
> +normally free to re-read the value from memory at any time - given that it
> +doesn't know that another entity might change this value. Consider the
> +following code:
> +===========
> +        int x = shared_pointer->counter;
> +
> +        some_var = x + something_else;
> +        function_call(x);
> +===========
> +The compiler is free to actually *not* use a local variable, instead derefence
> +the pointer and directly access the shared memory twice when using the value
> +of "x" in the assignment and in the function call. Now if some other CPU
> +changes the value of "counter" meanwhile, the value of "x" is different,
> +which violates the program semantic. The compiler is not to blame here,
> +because it cannot know that this memory could change behind its back.
> +The solution here is to use ACCESS_ONCE, which casts the access with the
> +"volatile" keyword, thus making sure that the compiler knows that
> +accessing this memory has side effects, so it needs to cache the value:
> +===========
> +        int x = ACCESS_ONCE(shared_pointer->counter);
> +
> +        some_var = x + something_else;
> +        function_call(x);
> +===========
> +
> +What ACCESS_ONCE does *not* guarantee though is this access is done in a
> +single instruction, so complex or non-native or unaligned data types are
> +not guaranteed to be atomic. If for instance counter would be a 64-bit value
> +on a 32-bit system, the compiler would probably generate two load instructions,
> +which could end up in reading a wrong value if some other CPU changes the other
> +half of the variable in between those two reads.
> +However accessing _aligned and native_ data types is guaranteed to be atomic
> +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
> +these conditions are met.
> +We expect a variable to be aligned if it comes from a non-packed struct or
> +some other compiler-generated address, as sane compilers will not generate
> +unaligned accesses by default.
> +Extra care must be taken however if the address is coming from a crafted
> +pointer or some address passed in by a non-trusted source (guests).
> +
> +read_atomic()/write_atomic()
> +----------------------------
> +read_atomic() and write_atomic() are macros that make sure that the access
> +to this variable happens using a single machine instruction. This guarantees
> +the access to be atomic when the address is aligned (on all architectures
> +supported by Xen).
> +For most practical cases the generated code does not differ from what
> +the compiler would generate anyway, but it makes sure that a change to an
> +unsuitable data type would break compilation, also it annotates this access
> +as being potentially concurrent (to a human reader).
> +Also this macro does not check whether the address is actually aligned,
> +though it is assumed that the compiler only generates aligned addresses
> +unless being told otherwise explicitly. In the latter case it would be the
> +responsibility of the coder to ensure atomicity using other means.
> +
> +atomic_read()/atomic_write() (and other variants starting with "atomic_")
> +-------------------------------------------------------------------------
> +(Not to be confused with the above!)
> +Those (group of) functions work on a special atomic_t data type, which wraps
> +an "int" in a structure to avoid accidential messing with the data type
> +(for instance due to implicit casts). As a side effect this guarantees that
> +this variable is aligned (though this would apply to most other "int"
> +declarations as well). This special data type also makes sure that any
> +accesses are only valid using those special accessor functions, which
> +make sure that the atomic property is always preserved.
> +On top of the basic read/write accesses this also provides read-modify-write
> +primitives which use architecture specific means to guarantee atomic accesses
> +(atomic_inc(), atomic_dec_and_test(), ...).
> +
> +
> +It has to be noted that following the letters of the C standard a
> +standards-compliant compiler has quite some freedom to generate code which
> +would make a lot of accesses non-atomic (for instance splitting a 32-bit
> +read into a series of four 8-bit reads).
> +However a sane compiler, especially when following a certain ABI, would
> +for instance always try to align variables and use as few machine
> +instructions as possible, so for practical purposes most accesses are
> +actually atomic without further ado, especially when being confined to
> +certain architectures (like x86, ARM and ARM64 in Xen).
> +
> +So for practical purposes we assume a sane compiler to be used for Xen,
> +with the following properties:
> +- Compiler generated addresses for native-data-typed variables are aligned.
> +- Simple read/write accesses to a native and aligned data type from compiler
> +  generated addresses are done using a single machine instruction.
> +
> +This makes read and write accesses to ints and longs (and their respective
> +unsigned counter parts) naturally atomic.
> +However it would be beneficial to use atomic primitives anyway to annotate
> +the code as being concurrent and to prevent silent breakage when changing
> +the code. Modern compilers tend to optimize quite well, often resulting in
> +the same code to be generated for both the annotated and naive version.

By "atomic primitives" you mean atomic_read()/atomic_write() or
read_atomic()/write_atomic(), correct? If so, it makes a lot of sense to
me.

Thanks for writing this down!

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Jan Beulich]

>>> On 13.06.17 at 17:25, <andre.przywara@arm.com> wrote:
> as mentioned in my previous mail, I consider this more of a discussion
> base that an actual patch. I am by no means an expert in this area, so
> part of this exercise here is to write down my understanding and see it
> corrected by more knowledgable people ;-)

Nevertheless please follow submission guidelines and send _to_
the list, _cc_-ing maintainers and other relevant people.

> --- /dev/null
> +++ b/docs/README.atomic

I'm not overly happy with that name. Perhaps something line
atomic.txt? Also I guess this would rather belong under docs/misc/,
at least based on what's there already.

> @@ -0,0 +1,116 @@
> +Atomic operations in Xen
> +========================
> +
> +Data structures in Xen memory which can be accessed by multiple CPUs
> +at the same time need to be protected against getting corrupted.
> +The easiest way to do this is using a lock (spinlock in Xen's case),
> +that guarantees that only one CPU can access that memory at a given point
> +in time, also allows protecting whole data structures against becoming
> +inconsistent. For most use cases this should be the way to go and programmers
> +should stop reading here.

As further down you talk about lockless approaches only, please
also mention r/w write locking above.

> +However sometimes taking and releasing a lock is too costly or creates
> +deadlocks or potential contention, so some lockless accesses are used.
> +Those atomic accesses need to be done very carefully to be correct.
> +
> +Xen offers three kinds of atomic primitives that deal with those accesses:
> +
> +ACCESS_ONCE()
> +-------------

For this I think we should first of all settle whether we want to stay
with this or use READ_ONCE() / WRITE_ONCE() which modern Linux
prefers.

> +A macro basically casting the access to a volatile data type. That prevents
> +the compiler from accessing that memory location multiple times, effectively
> +caching this value (either in a register or on the stack).
> +In terms of atomicity this prevents inconsistent values for a certain shared
> +variable if used multiple times across the same function, as the compiler is
> +normally free to re-read the value from memory at any time - given that it
> +doesn't know that another entity might change this value. Consider the
> +following code:
> +===========
> +        int x = shared_pointer->counter;
> +
> +        some_var = x + something_else;
> +        function_call(x);
> +===========
> +The compiler is free to actually *not* use a local variable, instead derefence
> +the pointer and directly access the shared memory twice when using the value
> +of "x" in the assignment and in the function call. Now if some other CPU
> +changes the value of "counter" meanwhile, the value of "x" is different,
> +which violates the program semantic. The compiler is not to blame here,
> +because it cannot know that this memory could change behind its back.
> +The solution here is to use ACCESS_ONCE, which casts the access with the
> +"volatile" keyword, thus making sure that the compiler knows that
> +accessing this memory has side effects, so it needs to cache the value:
> +===========
> +        int x = ACCESS_ONCE(shared_pointer->counter);
> +
> +        some_var = x + something_else;
> +        function_call(x);
> +===========
> +
> +What ACCESS_ONCE does *not* guarantee though is this access is done in a
> +single instruction, so complex or non-native or unaligned data types are
> +not guaranteed to be atomic. If for instance counter would be a 64-bit value
> +on a 32-bit system, the compiler would probably generate two load instructions,
> +which could end up in reading a wrong value if some other CPU changes the other
> +half of the variable in between those two reads.
> +However accessing _aligned and native_ data types is guaranteed to be atomic
> +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
> +these conditions are met.

As mentioned before, such a guarantee does not exist. Please only
state what is really the case, i.e. we _expect_ compilers to behave
this way.

> +We expect a variable to be aligned if it comes from a non-packed struct or
> +some other compiler-generated address, as sane compilers will not generate
> +unaligned accesses by default.

This, otoh, can be tightened, I think: If I'm not mistaken the
language standard and/or the per-architecture ABIs require data
to be naturally aligned unless specifically overridden.

> +Extra care must be taken however if the address is coming from a crafted
> +pointer or some address passed in by a non-trusted source (guests).

We shouldn't be accessing guest memory with other than the
designated helpers anyway, so I think this part doesn't belong
here.

> +read_atomic()/write_atomic()
> +----------------------------
> +read_atomic() and write_atomic() are macros that make sure that the access
> +to this variable happens using a single machine instruction. This guarantees
> +the access to be atomic when the address is aligned (on all architectures
> +supported by Xen).
> +For most practical cases the generated code does not differ from what
> +the compiler would generate anyway, but it makes sure that a change to an
> +unsuitable data type would break compilation, also it annotates this access
> +as being potentially concurrent (to a human reader).
> +Also this macro does not check whether the address is actually aligned,
> +though it is assumed that the compiler only generates aligned addresses
> +unless being told otherwise explicitly. In the latter case it would be the
> +responsibility of the coder to ensure atomicity using other means.

For both groups above please also mention that there are no
ordering implications (i.e. not implicit or explicit barriers).

> +atomic_read()/atomic_write() (and other variants starting with "atomic_")
> +-------------------------------------------------------------------------
> +(Not to be confused with the above!)
> +Those (group of) functions work on a special atomic_t data type, which wraps
> +an "int" in a structure to avoid accidential messing with the data type
> +(for instance due to implicit casts). As a side effect this guarantees that
> +this variable is aligned (though this would apply to most other "int"
> +declarations as well).

There's nothing special here at all - declaring a variable of either
plain int or atomic_t with the __packed attribute will render the
field unaligned.

> This special data type also makes sure that any
> +accesses are only valid using those special accessor functions, which
> +make sure that the atomic property is always preserved.

"make sure" is too strong a statement, as we can't prevent people
to access the sole structure member directly (and iirc there is code
doing so, if not in Xen then at least in Linux). I'd suggest "which is
intended to help make sure".

> +On top of the basic read/write accesses this also provides read-modify-write
> +primitives which use architecture specific means to guarantee atomic accesses
> +(atomic_inc(), atomic_dec_and_test(), ...).

I'd prefer "updates" instead of "accesses".

> +It has to be noted that following the letters of the C standard a
> +standards-compliant compiler has quite some freedom to generate code which
> +would make a lot of accesses non-atomic (for instance splitting a 32-bit
> +read into a series of four 8-bit reads).
> +However a sane compiler, especially when following a certain ABI, would
> +for instance always try to align variables and use as few machine
> +instructions as possible, so for practical purposes most accesses are
> +actually atomic without further ado, especially when being confined to
> +certain architectures (like x86, ARM and ARM64 in Xen).
> +
> +So for practical purposes we assume a sane compiler to be used for Xen,
> +with the following properties:
> +- Compiler generated addresses for native-data-typed variables are aligned.
> +- Simple read/write accesses to a native and aligned data type from compiler
> +  generated addresses are done using a single machine instruction.
> +
> +This makes read and write accesses to ints and longs (and their respective
> +unsigned counter parts) naturally atomic.

Ah, you say here some of what I've been missing earlier on. I think
this discussion really belongs into the ACCESS_ONCE() section, as the
other two aren't affected by it.

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Stefano Stabellini]

On Wed, 14 Jun 2017, Jan Beulich wrote:
> > +What ACCESS_ONCE does *not* guarantee though is this access is done in a
> > +single instruction, so complex or non-native or unaligned data types are
> > +not guaranteed to be atomic. If for instance counter would be a 64-bit value
> > +on a 32-bit system, the compiler would probably generate two load instructions,
> > +which could end up in reading a wrong value if some other CPU changes the other
> > +half of the variable in between those two reads.
> > +However accessing _aligned and native_ data types is guaranteed to be atomic
> > +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
> > +these conditions are met.
> 
> As mentioned before, such a guarantee does not exist. Please only
> state what is really the case, i.e. we _expect_ compilers to behave
> this way.

Regarding compilers support: do we state clearly in any docs or website
what are the compilers we actually support? I think this would be the
right opportunity to do it.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Jan Beulich]

>>> Stefano Stabellini <sstabellini@kernel.org> 06/14/17 8:45 PM >>>
>On Wed, 14 Jun 2017, Jan Beulich wrote:
>> > +What ACCESS_ONCE does *not* guarantee though is this access is done in a
>> > +single instruction, so complex or non-native or unaligned data types are
>> > +not guaranteed to be atomic. If for instance counter would be a 64-bit value
>> > +on a 32-bit system, the compiler would probably generate two load instructions,
>> > +which could end up in reading a wrong value if some other CPU changes the other
>> > +half of the variable in between those two reads.
>> > +However accessing _aligned and native_ data types is guaranteed to be atomic
>> > +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
>> > +these conditions are met.
>> 
>> As mentioned before, such a guarantee does not exist. Please only
>> state what is really the case, i.e. we _expect_ compilers to behave
>> this way.
>
>Regarding compilers support: do we state clearly in any docs or website
>what are the compilers we actually support? I think this would be the
>right opportunity to do it.

At the very least we state somewhere what gcc versions we support. However,
I can't see the relation of such a statement to the discussion here.

Jan



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Stefano Stabellini]

On Wed, 14 Jun 2017, Jan Beulich wrote:
> >>> Stefano Stabellini <sstabellini@kernel.org> 06/14/17 8:45 PM >>>
> >On Wed, 14 Jun 2017, Jan Beulich wrote:
> >> > +What ACCESS_ONCE does *not* guarantee though is this access is done in a
> >> > +single instruction, so complex or non-native or unaligned data types are
> >> > +not guaranteed to be atomic. If for instance counter would be a 64-bit value
> >> > +on a 32-bit system, the compiler would probably generate two load instructions,
> >> > +which could end up in reading a wrong value if some other CPU changes the other
> >> > +half of the variable in between those two reads.
> >> > +However accessing _aligned and native_ data types is guaranteed to be atomic
> >> > +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
> >> > +these conditions are met.
> >> 
> >> As mentioned before, such a guarantee does not exist. Please only
> >> state what is really the case, i.e. we _expect_ compilers to behave
> >> this way.
> >
> >Regarding compilers support: do we state clearly in any docs or website
> >what are the compilers we actually support? I think this would be the
> >right opportunity to do it.
> 
> At the very least we state somewhere what gcc versions we support. However,
> I can't see the relation of such a statement to the discussion here.

The relation is that our "compiler expectations" shape what compilers we
support.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Jan Beulich]

>>> Stefano Stabellini <sstabellini@kernel.org> 06/15/17 2:27 AM >>>
>On Wed, 14 Jun 2017, Jan Beulich wrote:
>> >>> Stefano Stabellini <sstabellini@kernel.org> 06/14/17 8:45 PM >>>
>> >On Wed, 14 Jun 2017, Jan Beulich wrote:
>> >> > +What ACCESS_ONCE does *not* guarantee though is this access is done in a
>> >> > +single instruction, so complex or non-native or unaligned data types are
>> >> > +not guaranteed to be atomic. If for instance counter would be a 64-bit value
>> >> > +on a 32-bit system, the compiler would probably generate two load instructions,
>> >> > +which could end up in reading a wrong value if some other CPU changes the other
>> >> > +half of the variable in between those two reads.
>> >> > +However accessing _aligned and native_ data types is guaranteed to be atomic
>> >> > +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
>> >> > +these conditions are met.
>> >> 
>> >> As mentioned before, such a guarantee does not exist. Please only
>> >> state what is really the case, i.e. we _expect_ compilers to behave
>> >> this way.
>> >
>> >Regarding compilers support: do we state clearly in any docs or website
>> >what are the compilers we actually support? I think this would be the
>> >right opportunity to do it.
>> 
>> At the very least we state somewhere what gcc versions we support. However,
>> I can't see the relation of such a statement to the discussion here.
>
>The relation is that our "compiler expectations" shape what compilers we
>support.

I don't view it this way - we implicitly support unknown future versions of gcc,
and we can't know if they might break our assumptions.

Jan



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Andre Przywara]

Hi Jan,

thanks for spending your time on this mind boggling exercise!

On 14/06/17 10:12, Jan Beulich wrote:
>>>> On 13.06.17 at 17:25, <andre.przywara@arm.com> wrote:
>> as mentioned in my previous mail, I consider this more of a discussion
>> base that an actual patch. I am by no means an expert in this area, so
>> part of this exercise here is to write down my understanding and see it
>> corrected by more knowledgable people ;-)
> 
> Nevertheless please follow submission guidelines and send _to_
> the list, _cc_-ing maintainers and other relevant people.

Sure.

>> --- /dev/null
>> +++ b/docs/README.atomic
> 
> I'm not overly happy with that name. Perhaps something line
> atomic.txt? Also I guess this would rather belong under docs/misc/,
> at least based on what's there already.

I was just looking at doc/README.*, but sure I can move and rename it.

>> @@ -0,0 +1,116 @@
>> +Atomic operations in Xen
>> +========================
>> +
>> +Data structures in Xen memory which can be accessed by multiple CPUs
>> +at the same time need to be protected against getting corrupted.
>> +The easiest way to do this is using a lock (spinlock in Xen's case),
>> +that guarantees that only one CPU can access that memory at a given point
>> +in time, also allows protecting whole data structures against becoming
>> +inconsistent. For most use cases this should be the way to go and programmers
>> +should stop reading here.
> 
> As further down you talk about lockless approaches only, please
> also mention r/w write locking above.

What do you mean with "r/w write locking" here? Does Xen's rwlock_t use
some lockless tricks?

>> +However sometimes taking and releasing a lock is too costly or creates
>> +deadlocks or potential contention, so some lockless accesses are used.
>> +Those atomic accesses need to be done very carefully to be correct.
>> +
>> +Xen offers three kinds of atomic primitives that deal with those accesses:
>> +
>> +ACCESS_ONCE()
>> +-------------
> 
> For this I think we should first of all settle whether we want to stay
> with this or use READ_ONCE() / WRITE_ONCE() which modern Linux
> prefers.

Sure.

>> +A macro basically casting the access to a volatile data type. That prevents
>> +the compiler from accessing that memory location multiple times, effectively
>> +caching this value (either in a register or on the stack).
>> +In terms of atomicity this prevents inconsistent values for a certain shared
>> +variable if used multiple times across the same function, as the compiler is
>> +normally free to re-read the value from memory at any time - given that it
>> +doesn't know that another entity might change this value. Consider the
>> +following code:
>> +===========
>> +        int x = shared_pointer->counter;
>> +
>> +        some_var = x + something_else;
>> +        function_call(x);
>> +===========
>> +The compiler is free to actually *not* use a local variable, instead derefence
>> +the pointer and directly access the shared memory twice when using the value
>> +of "x" in the assignment and in the function call. Now if some other CPU
>> +changes the value of "counter" meanwhile, the value of "x" is different,
>> +which violates the program semantic. The compiler is not to blame here,
>> +because it cannot know that this memory could change behind its back.
>> +The solution here is to use ACCESS_ONCE, which casts the access with the
>> +"volatile" keyword, thus making sure that the compiler knows that
>> +accessing this memory has side effects, so it needs to cache the value:
>> +===========
>> +        int x = ACCESS_ONCE(shared_pointer->counter);
>> +
>> +        some_var = x + something_else;
>> +        function_call(x);
>> +===========
>> +
>> +What ACCESS_ONCE does *not* guarantee though is this access is done in a
>> +single instruction, so complex or non-native or unaligned data types are
>> +not guaranteed to be atomic. If for instance counter would be a 64-bit value
>> +on a 32-bit system, the compiler would probably generate two load instructions,
>> +which could end up in reading a wrong value if some other CPU changes the other
>> +half of the variable in between those two reads.
>> +However accessing _aligned and native_ data types is guaranteed to be atomic
>> +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
>> +these conditions are met.
> 
> As mentioned before, such a guarantee does not exist. Please only
> state what is really the case, i.e. we _expect_ compilers to behave
> this way.

Do you mean the guarantee of using a single machine instruction to
access variables?
For the "aligned access to native data types" there are explicit
architectural guarantees:
Intel manual volume 3, chapter 8.1.1 Guaranteed Atomic Operations
ARMv7 ARM, chapter A3.5.3  Atomicity in the ARM architecture
ARMv8 ARM, chapter B2.6.1  Requirements for single-copy atomicity
(I will probably add those references to the document anyway)

>> +We expect a variable to be aligned if it comes from a non-packed struct or
>> +some other compiler-generated address, as sane compilers will not generate
>> +unaligned accesses by default.
> 
> This, otoh, can be tightened, I think: If I'm not mistaken the
> language standard and/or the per-architecture ABIs require data
> to be naturally aligned unless specifically overridden.

That's true and indeed worth to be mentioned here.

>> +Extra care must be taken however if the address is coming from a crafted
>> +pointer or some address passed in by a non-trusted source (guests).
> 
> We shouldn't be accessing guest memory with other than the
> designated helpers anyway, so I think this part doesn't belong
> here.

Agreed.

>> +read_atomic()/write_atomic()
>> +----------------------------
>> +read_atomic() and write_atomic() are macros that make sure that the access
>> +to this variable happens using a single machine instruction. This guarantees
>> +the access to be atomic when the address is aligned (on all architectures
>> +supported by Xen).
>> +For most practical cases the generated code does not differ from what
>> +the compiler would generate anyway, but it makes sure that a change to an
>> +unsuitable data type would break compilation, also it annotates this access
>> +as being potentially concurrent (to a human reader).
>> +Also this macro does not check whether the address is actually aligned,
>> +though it is assumed that the compiler only generates aligned addresses
>> +unless being told otherwise explicitly. In the latter case it would be the
>> +responsibility of the coder to ensure atomicity using other means.
> 
> For both groups above please also mention that there are no
> ordering implications (i.e. not implicit or explicit barriers).

Good point.

>> +atomic_read()/atomic_write() (and other variants starting with "atomic_")
>> +-------------------------------------------------------------------------
>> +(Not to be confused with the above!)
>> +Those (group of) functions work on a special atomic_t data type, which wraps
>> +an "int" in a structure to avoid accidential messing with the data type
>> +(for instance due to implicit casts). As a side effect this guarantees that
>> +this variable is aligned (though this would apply to most other "int"
>> +declarations as well).
> 
> There's nothing special here at all - declaring a variable of either
> plain int or atomic_t with the __packed attribute will render the
> field unaligned.

Which is true indeed. So I will remove this last sentence.

>> This special data type also makes sure that any
>> +accesses are only valid using those special accessor functions, which
>> +make sure that the atomic property is always preserved.
> 
> "make sure" is too strong a statement, as we can't prevent people
> to access the sole structure member directly (and iirc there is code
> doing so, if not in Xen then at least in Linux). I'd suggest "which is
> intended to help make sure".

Yes - and that would match the word "accidental" above.

>> +On top of the basic read/write accesses this also provides read-modify-write
>> +primitives which use architecture specific means to guarantee atomic accesses
>> +(atomic_inc(), atomic_dec_and_test(), ...).
> 
> I'd prefer "updates" instead of "accesses".
> 
>> +It has to be noted that following the letters of the C standard a
>> +standards-compliant compiler has quite some freedom to generate code which
>> +would make a lot of accesses non-atomic (for instance splitting a 32-bit
>> +read into a series of four 8-bit reads).
>> +However a sane compiler, especially when following a certain ABI, would
>> +for instance always try to align variables and use as few machine
>> +instructions as possible, so for practical purposes most accesses are
>> +actually atomic without further ado, especially when being confined to
>> +certain architectures (like x86, ARM and ARM64 in Xen).
>> +
>> +So for practical purposes we assume a sane compiler to be used for Xen,
>> +with the following properties:
>> +- Compiler generated addresses for native-data-typed variables are aligned.
>> +- Simple read/write accesses to a native and aligned data type from compiler
>> +  generated addresses are done using a single machine instruction.
>> +
>> +This makes read and write accesses to ints and longs (and their respective
>> +unsigned counter parts) naturally atomic.
> 
> Ah, you say here some of what I've been missing earlier on. I think
> this discussion really belongs into the ACCESS_ONCE() section, as the
> other two aren't affected by it.

Yes, will do.

Thanks for having actually read this ;-) and the comments!

Cheers,
Andre.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Stefano Stabellini]

On Thu, 15 Jun 2017, Jan Beulich wrote:
> >>> Stefano Stabellini <sstabellini@kernel.org> 06/15/17 2:27 AM >>>
> >On Wed, 14 Jun 2017, Jan Beulich wrote:
> >> >>> Stefano Stabellini <sstabellini@kernel.org> 06/14/17 8:45 PM >>>
> >> >On Wed, 14 Jun 2017, Jan Beulich wrote:
> >> >> > +What ACCESS_ONCE does *not* guarantee though is this access is done in a
> >> >> > +single instruction, so complex or non-native or unaligned data types are
> >> >> > +not guaranteed to be atomic. If for instance counter would be a 64-bit value
> >> >> > +on a 32-bit system, the compiler would probably generate two load instructions,
> >> >> > +which could end up in reading a wrong value if some other CPU changes the other
> >> >> > +half of the variable in between those two reads.
> >> >> > +However accessing _aligned and native_ data types is guaranteed to be atomic
> >> >> > +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
> >> >> > +these conditions are met.
> >> >> 
> >> >> As mentioned before, such a guarantee does not exist. Please only
> >> >> state what is really the case, i.e. we _expect_ compilers to behave
> >> >> this way.
> >> >
> >> >Regarding compilers support: do we state clearly in any docs or website
> >> >what are the compilers we actually support? I think this would be the
> >> >right opportunity to do it.
> >> 
> >> At the very least we state somewhere what gcc versions we support. However,
> >> I can't see the relation of such a statement to the discussion here.
> >
> >The relation is that our "compiler expectations" shape what compilers we
> >support.
> 
> I don't view it this way - we implicitly support unknown future versions of gcc,
> and we can't know if they might break our assumptions.

OK. In that case, in the same document or wikipage where we write about
gcc versions, it makes sense to write about compiler
assumptions/expectations too.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [RFC PATCH] docs: add README.atomic

[Jan Beulich]

>>> On 15.06.17 at 19:21, <andre.przywara@arm.com> wrote:
> On 14/06/17 10:12, Jan Beulich wrote:
>>>>> On 13.06.17 at 17:25, <andre.przywara@arm.com> wrote:
>>> @@ -0,0 +1,116 @@
>>> +Atomic operations in Xen
>>> +========================
>>> +
>>> +Data structures in Xen memory which can be accessed by multiple CPUs
>>> +at the same time need to be protected against getting corrupted.
>>> +The easiest way to do this is using a lock (spinlock in Xen's case),
>>> +that guarantees that only one CPU can access that memory at a given point
>>> +in time, also allows protecting whole data structures against becoming
>>> +inconsistent. For most use cases this should be the way to go and programmers
>>> +should stop reading here.
>> 
>> As further down you talk about lockless approaches only, please
>> also mention r/w write locking above.
> 
> What do you mean with "r/w write locking" here? Does Xen's rwlock_t use
> some lockless tricks?

No. My comment was about you mentioning spin locks, but not r/w
locks.

>>> +What ACCESS_ONCE does *not* guarantee though is this access is done in a
>>> +single instruction, so complex or non-native or unaligned data types are
>>> +not guaranteed to be atomic. If for instance counter would be a 64-bit value
>>> +on a 32-bit system, the compiler would probably generate two load instructions,
>>> +which could end up in reading a wrong value if some other CPU changes the other
>>> +half of the variable in between those two reads.
>>> +However accessing _aligned and native_ data types is guaranteed to be atomic
>>> +in the architectures supported by Xen, so ACCESS_ONCE is safe to use when
>>> +these conditions are met.
>> 
>> As mentioned before, such a guarantee does not exist. Please only
>> state what is really the case, i.e. we _expect_ compilers to behave
>> this way.
> 
> Do you mean the guarantee of using a single machine instruction to
> access variables?
> For the "aligned access to native data types" there are explicit
> architectural guarantees:
> Intel manual volume 3, chapter 8.1.1 Guaranteed Atomic Operations
> ARMv7 ARM, chapter A3.5.3  Atomicity in the ARM architecture
> ARMv8 ARM, chapter B2.6.1  Requirements for single-copy atomicity
> (I will probably add those references to the document anyway)

Sure, once the compiler emits what we hope for, all is fine. But once
again - the compiler is not required to do so, and hence there's no
such guarantee.

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel