[FFmpeg-devel] [PATCH] avutil/crc: always use precalculated CRC tables for known polynomials

[Mark Thompson]

On 24/10/17 00:52, Michael Niedermayer wrote:
> Hi
> 
> On Mon, Oct 23, 2017 at 04:43:19PM +0100, Mark Thompson wrote:
>> On 23/10/17 03:56, Michael Niedermayer wrote:
>>> the initialization should be thread safe as it never writes a different
>>> value in the same spot
>>
>> This is not true; please be very careful with assumptions like this.
>>
>> The C standard calls this a data race and it is undefined behaviour.
> 
> Thats interresting, we definitly do not want undefined behavior
> can you quote the relevant parts of the C standard
> which make writing the same value, a data race ?
> 
> I was not aware of this if its true.
> Also i dont immedeatly see this in the "latest" draft i am looking at
> atm
> 
> What i see is this:
> 4 Two expression evaluations conflict if one of them modifies a memory location and the
>   other one reads or modifies the same memory location.
> ...
> 25 The execution of a program contains a data race if it contains two conflicting actions in
>    different threads, at least one of which is not atomic, and neither happens before the
>    other. Any such data race results in undefined behavior.
> 
> This seems carefully worded to not include writing the same value.
> As "modification" implies change which does not occur when writing the
> same value.

All writes are modifications.

See section 3.1 note 2:
"""
3 NOTE 2   "Modify"€™ includes the case where the new value being stored is the same as the previous value.
"""

>> It is not just a theoretical concern, either - on architectures with destructive write-hint instructions ("fill cache line with unspecified data without loading it from memory, because I'm about to overwrite all of it", exactly what you want to use (and therefore the compiler will generate) to avoid pointless loads when overwriting a large table) other threads can and do see different contents transiently when the same data is written to the location.
> 
> This might violate:
> 27 NOTE 13 Compiler transformations that introduce assignments to a potentially shared memory location
>    that would not be modified by the abstract machine are generally precluded by this standard, since such an
>    assignment might overwrite another assignment by a different thread in cases in which an abstract machine
>    execution would not have encountered a data race. This includes implementations of data member
>    assignment that overwrite adjacent members in separate memory locations. We also generally preclude
>    reordering of atomic loads in cases in which the atomics in question may alias, since this may violate the
>    "visible sequence" rules.

Yes, in order to match the behaviour of the abstract machine the transformation requires that the region in question is:
* Not atomic: if atomic, another thread would be allowed to observe the intermediate state directly.
* Overwritten entirely: if not overwritten entirely, other data would be touched which should not be, and that could be observed by another thread.
* Without external ordering: if external synchronisation were present, another thread would be able to read values on one or other side of that boundary without a data race and observe an inconsistent state.

The CRC table construction satisfies all of these conditions.

Thanks,

- Mark