Re: [Xen-devel] [RFC PATCH] docs: add README.atomic

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 13.06.17 at 17:25, <andre.przywara@xxxxxxx> 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@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel