8

Given an array of type foo_t[n] and a set of n threads, where each of the n threads reads and modifies a different element of the array, do I need to explicitly synchronize modifications of the array or can I assume that concurrently modifying members of the array is well-defined behavior? Does it matter how large foo_t is / what alignment it has?

fuz
  • 88,405
  • 25
  • 200
  • 352
  • 2
    Two distinct elements of an array are two distinct objects, hence two distinct memory locations. Concurrent / unsynchronized access to different memory locations is guaranteed to be safe. (C11) Pre-C11, I think it's not safe. Prior to C11, C was mostly thread-agnostic. – dyp Jun 21 '14 at 23:34
  • 1
    @dyp What if foo_t is smaller than the wordsize and the machine is only capable of word-sized memory access. Wouldn't a modification of one member potentially also write parts of the adjacent members? – fuz Jun 21 '14 at 23:37
  • @FUZxxl: In that case foo_t would likely be padded to word size. – Ed S. Jun 21 '14 at 23:37
  • I think it had to emit thread-safe code in that case. But, as I said, only >= C11. – dyp Jun 21 '14 at 23:38
  • 1
    @EdS. That's odd. On such a machine, strings wouldn't work then... – fuz Jun 21 '14 at 23:38
  • @FUZxxl: a "word" is simply a unit of data. It has no defined size. A byte is also not defined to be 8 bits. Strings will always "work". – Ed S. Jun 21 '14 at 23:40
  • The DS9K probably can access individual bytes, but only 3-byte-packs in a thread-safe way. – dyp Jun 21 '14 at 23:40
  • @EdS. I can decide what type foo_t is. POSIX requires that CHAR_BIT is 8 and that an array of chars does not contain padding inbetween. Please clarify what you mean with "foo_t would likely be padded to word size" when for some foo_t, this cannot be. – fuz Jun 22 '14 at 00:05
  • You're right, I was assuming some different sort of structure for `foo_t`, not sure why. – Ed S. Jun 22 '14 at 00:39
  • @EdS. Does POSIX make any guarantees about how large a structure has to be to guarantee modification without modification of adjacent data? – fuz Jun 22 '14 at 01:51
  • @EdS. C11 apparently guarantees well-definedness here. See my own answer. – fuz Jun 22 '14 at 02:20

1 Answers1

6

What I try to do is well-defined behavior.

See ISO/IEC 9899:2011 §5.1.2.4.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.

Note that this language was introduced with C11 to make optimizations that cause bugs like this illegal. Pre-C11 compilers may not abide to this rule.

fuz
  • 88,405
  • 25
  • 200
  • 352
  • I wonder how strictly compilers actually adhere to this. Does any compiler do a word-sized write to update a character in a string , in a single-threaded program, but change to byte-sized writes in a multithreaded system? – M.M Jun 22 '14 at 02:35
  • @MattMcNabb I seriously don't know. – fuz Jun 22 '14 at 09:52
  • The note is based on the C11's threads. So the same might not be followed by POSIX's thread implementation. – P.P Jun 24 '14 at 09:45
  • @BlueMoon Thank you for this notice, but as far as I understood, this behavior is mandated by the C11 memory model. I would be very surprised if POSIX.1 violated the C11 memory model, usually POSIX.1 makes even more guarantees than C. – fuz Jun 24 '14 at 10:27
  • Of course POSIX defers to ISO C in all cases. But pthreads doesn't come under ISO C (just like many system calls). C11's threads is a different implementation. For example, a compiler can support both and yet pthreads implementation may not behave in the same way as C11's threads for an equivalent functionality. So you might want to consult POSIX manual rather than C. – P.P Jun 24 '14 at 10:32
  • @BlueMoon Thanks for the notice. Do you have any idea if POSIX makes a similar guarantee? – fuz Jun 24 '14 at 10:32
  • Hmm..no, will have to read the docs on POSIX memory model. Not sure where among many pdfs that would be defined though :) – P.P Jun 24 '14 at 10:36
  • The question can be rephrased as whether each element of an array is considered as a distinct object. The answer is *yes*. C11 has (C99 states the same) `For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.`. So `foo_t a[2]` is same as `foo_t a1` and `foo_t2` in C, which I believe is also followed by POSIX. There's no explicit memory model stated by POSIX.[cont] – P.P Jun 25 '14 at 20:47
  • The best I could find was this: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html which says there's such thing defined by POSIX. In addition, I have tested with 256 threads, each modify a unique element of an array (`int a[256]`) with random value, serially, squares etc. I have results are accurate as if they were modifying separate elements and produce correct results. So you can reasonably assume that what C11 defines is what's already followed by POSIX. Besides, C11 threads mostly based on POSIX threads. – P.P Jun 25 '14 at 20:52
  • I find interesting the attitude, expressed in the linked thread, that in cases where a platform's natural behavior is useful and necessary but would preclude optimizations that older compilers wouldn't have considered, compilers should by default optimize in such fashion as to break such code, rather than refraining from such optimizations in the absence of a directive which states that all places where it would be dangerous have been marked using new directives created for that purpose and a compiler may thus safely optimize all other places. – supercat Jul 25 '16 at 20:42