C99 Language Lawyer Needed

The program below came up during some tests. The question is, is it well-defined by the C99 language? It appears to clearly be undefined behavior by C11 and C++11.

struct {
  int f0:4;
  int f1:4;
} s;

int main (void) {
  (s.f0 = 0) + (s.f1 = 0);
  return 0;
}

21 Replies to “C99 Language Lawyer Needed”

  1. Even in C11, the reasoning is slightly tenuous. Here is what paragraph 3 in 3.14 says:

    NOTE 2 A bit-field and an adjacent non-bit-field member are in separate memory locations. The same applies to two bit-fields, if one is declared inside a nested structure declaration and the other is not, or if the two are separated by a zero-length bit-field declaration, or if they are separated by a non-bit-field member declaration. It is not safe to concurrently update two non-atomic bit-fields in the same structure if all members declared between them are also (non-zero-length) bit-fields, no matter what the sizes of those intervening bit-fields happen to be.

    It says nothing about sequence points, only about concurrency.

    Paragraph 2 in 6.5 says:

    If a side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined. […]

    This paragraph only speaks of scalar objects. A bit-field is not a scalar object. The meaning in 6.5 paragraph 2 would be clearer if it used “memory location” in place of “scalar object”, since “memory location” stands for “scalar object or contiguous sequence of bit-fields”.

    With the current formulation, we can only infer that the intention was to forbid the posted program from the fact that unsequenced updates to the same bit-field are clearly forbidden. Technically speaking, 6.5:2 does not apply to bit-fields.

  2. Michael, agreed!

    Pascal, when I last spent quality time with the C++11 document I took away that:

    – Much of the “sequenced before” and “sequenced after” language in the memory model applies both to inter-thread and intra-thread sequencing

    – It is clearly intended that unsynchronized accesses to adjascent bitfields race

    Of course I could be wrong in the details and will need to dig in again…

  3. Here is another quote from the C++11 standard:

    »[ Example: A structure declared as

    struct {
    char a;
    int b:5,
    c:11,
    :0,
    d:8;
    struct {int ee:8;} e;
    }

    contains four separate memory locations: The field a and bit-fields d and e.ee
    are each separate memory locations, and can be modified concurrently without
    interfering with each other. The bit-fields b and c together constitute the
    fourth memory location. The bit-fields b and c cannot be concurrently modified,
    but b and a, for example, can be. — end example ]«

    There is also a huge thread on the Linux Kernel Mailing List about this issue, see:

    http://thread.gmane.org/gmane.linux.ports.ia64/21974

  4. Octoploid: both the example from the standard and the LKML thread only seem to be about concurrency, though, unless John remembers where he saw that the rules for concurrency also defined what is allowed between sequence points.

  5. In the C++11 standard, 1.9 para 13 is where “Sequenced before” gets defined. It’s not clear that this ties in with the threading rules, but it does say that “The execution of unsequenced evaluations can overlap” so that does make the original example sound like undefined behaviour.

    Searching for bit field in the C99 standard, I don’t see anything that specifies how they should be treated in this kind of situation. It’s clear that f0 and f1 may (but don’t have to) be packed into the same byte, but I didn’t see any discussion of the semantics of this kind of update.

  6. Mike G., C99 says that multiple updates (or a read and an update) to an lvalue in between sequence points results in undefined behavior.

    But it’s not clear to me that these bitfields constitute a single lvalue even if, as you say, they clearly are permitted to be packed into a single byte.

  7. regehr, right – “are they a single lvalue” is what I was looking for (and not finding).

    But that doesn’t mean much – there could be a footnote somewhere that states they aren’t but doesn’t mention bit fields…

  8. I spent a while trying to get a program like this to actually misbehave under a common compiler, and was unsuccessful. Of course that doesn’t mean anything, but it may turn out that this behavior happens to be benign regardless of the standard.

  9. This seems well-defined for the same reason (s[0] = 0) + (s[1] = 0) would be. There is nothing special about bit-fields that would make this expression undefined. In particular, s.f0 and s.f1 are distinct objects with distinct storage (their storage locations may overlap, but that’s not relevant — unlike with unions, for which an explicit rule exists).

    I’ve tried to argue on comp.std.c that the wording of 6.5p2 (the sequence point rule) implies that s.f0 and s.f1 do modify the same object twice — namely “s” — but as someone pointed out, this would prohibit array element assignment too, which isn’t reasonable. C11 explicitly rewords 6.5p2 so the case of updating members of the same struct isn’t illegal, and it seems obvious C99 intended the same interpretation.

    In short, I think the compiler just has to make this work, regardless of how it decides to store f0 and f1.

  10. @Pascal: I don’t think 6.5p2 would be “clearer” if it read “memory location” instead of “scalar object” — it would change the meaning of the rule to explicitly rule out this case. There is no way to “port” this interpretation to C99, however, because C99 6.5p2 talks about objects only and has no concept of adjacent bit fields as a memory location.

    @Mike G: actually, s.f0 and s.f1 *must* be packed into the same byte on most platforms, AFAICT. This is because 6.7.2.1p10 states that “An implementation may allocate any addressable storage unit large enough to hold a bit-field. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit.” If the platform’s “byte” is 8 bits and nothing smaller is addressable (as is the case for most platforms), then it cannot allocate anything smaller than a byte to hold either f0 or f1, and enough space remains in that location to pack the other member too. What happens if bitfields do not fit, or how to treat the alignment of the storage unit, is left to the implementation.

  11. The discussion on comp.std.c has been interesting; in C11, the expression is undefined behavior if the evaluation of the subexpressions occurs in different threads of execution, because then it’s a data race. If a processor pipeline is allowed as a thread of execution (and I don’t see why not) then it at least seems the case that this expression *might* invoke UB on some C11 implementations.

    This does not apply to C99, though, because it doesn’t allow this form of UB. And even on C11 it would be, in programmer terms, a dick move from the compiler if it shrugged its shoulders and said “well, processor pipeline, what can you do” and unleashed the nasal demons just for writing that expression down and not studying the DeathStation 9000 manual sufficiently closely. The effort needed to make this code safe even under those circumstances seems to be reasonably small.

  12. Thanks Jeroen, I’ll go read comp.std.c. I usually avoid it since something about the collective personality there disagrees with me…

    Definitely it would be nasty for the compiler to exploit this. On the other hand, unfriendly exploitation of undefined behavior is hardly a new thing.

  13. I’m sorry. “I think I mentioned the pipeline once, but I got away with it.” 🙂 For purposes of standards wrangling, though, it’s always permissible to drag in a real-world concept if it can be shown to be consistent with the standard. As an extreme example, a C11 implementation could forcibly parallelize calculations that can be parallelized according to the standard. Probably no real-world C implementation would do this, but if it’s conceivable under the standard, and it causes UB, then there’s the possibility of UB, and that was what the question’s about.

    And yes, comp.std.c is not like comp.lang.c at all. If comp.lang.c is a battlefield, comp.std.c is a fencing academy. The fact that it sees vastly less traffic helps, of course.

  14. John, this is an interesting question.

    The issue here is two or more objects (e.g., bit-fields) potentially sharing the same “storage unit”

    Sentence 1409/1410:
    http://c0x.coding-guidelines.com/6.7.2.1.html

    coupled with the the meaning of “overlaps in any way” in:

    C11/C99 6.5.16.1p3
    Sentence 1304: http://c0x.coding-guidelines.com/6.5.16.1.html

    “If the value being stored in an object is read from another object that overlaps in any way
    the storage of the first object, then the overlap shall be exact …”

    Does overlap refer to storage units, just the bits allocated to the bit-field object (making the behavior well defined) or something else?

    If it refers to a storage unit then the overlap would appear to be exact, making the behavior well defined.

    I will ask WG14 people what they think.

  15. 6.5.16.1p3 cannot possibly apply here because “the value being stored” is in both cases a suitably-converted 0, and not “read from another object”. Regardless of storage, the bit-fields are clearly distinct objects. This section describes the semantics of assignment, not general object access.

    If we read the value from the other bit-field, but then the expression invokes UB by simple sequence point violation. If we read the value from a bit-field not involved in this expression, then the discussion about storage would apply. I think that, since bit-fields are distinct objects and hence distinct “regions of data storage” (the standard’s definition of an object) even if they also occupy the same storage unit, 6.5.16.1p3 would not invoke UB for bit-field assignments. To interpret this section otherwise would make all assignments from a bit-field to an adjacent bit-field illegal, which I’m pretty sure is not what the standard is going for.

  16. Thinking a bit more, the only way you could use 6.5.16.1p3 to make adjacent bit-field assignments illegal is if you used the following interpretation:
    – Adjacent bit-fields overlap each other in storage since they’re in the same storage unit; but
    – This overlap is not exact because their *storage* within that unit is not the same.
    This seems deliberately contrived, measuring with two yardsticks. Either contend that the overlap is exact because it’s the same storage unit, or there’s no overlap at all because the region of data storage is distinct. Either way would avoid it.

    I prefer the latter interpretation because the first still poses a problem: if the bit-fields are not of the same type, assignment is still undefined because, even though the overlap is exact, the types are not compatible (the other requirement of 6.5.16.1p3). Give the poor bit-fields a break. 🙂

  17. Jeroen, I am guilty of answering a modified form of the original question (which I think is defined because all the relevant wordings talk about objects and not their storage).

    My explanation applies to the case of the following statement appearing in the above code:

    s.f0 = s.f1;

Comments are closed.