15
$\begingroup$

In C there is a concept of trap representations, or non-value representations. If such a value is produced or used, immediate undefined behavior is invoked. This is one of the dangers of using uninitialized memory as there might be a trap representation.

However, for what reason would a language or implementation have a concept of a trap representation in the first place? Why would the behavior not be defined every one of the finite number of possible values of the finite number of bits in a type?

$\endgroup$
2
  • 2
    $\begingroup$ Note that Itanium had a extra bit on registers to mark it as uninitialized. A C compiler would have to guarantee initialization or have the hardware trap on uninitialized register uses. $\endgroup$
    – prosfilaes
    Commented Jul 10, 2023 at 14:08
  • 2
    $\begingroup$ @prosfilaes - there are other examples, some of which predate the design of the C language, e.g. on the PDP-1 there is a bit in pointers that indicates that the value pointed to is another pointer that should also be dereferenced, continuing until a pointer is found without the bit set. This means that dereferencing a pointer may cause undefined behaviour (e.g. an infinite loop) depending not only on the value of the pointer itself, but also the contents of the memory it points to. The specification authors were clearly cautious that future hardware may also have similarly odd behaviours. $\endgroup$
    – occipita
    Commented Jul 12, 2023 at 19:30

8 Answers 8

21
$\begingroup$

Trap representations are usually a property of the underlying hardware. If they exist, a programming language has to choose a behaviour:

  1. Ensure that every value is initialised to a non-trap value and that trap representations cannot be generated by user code (e.g. Java takes this approach).

  2. Define exact results of operating on trap representations (and perhaps thereby exclude classes of hardware from being able to support the language).

  3. Declare that the behaviour of trap representations is outside the specification of the language (e.g. C and C++).

The third approach is consistent with performance-oriented languages where the overhead of (1) is unacceptable.

Note that in most cases, platforms are allowed to specify behaviour which the language definition leaves undefined - that can move platform-specific programs from category (3) to category (2). In practice, that's often useful because not all programs need to be portable.

$\endgroup$
13
  • $\begingroup$ This has always been my understanding. $\endgroup$
    – Barmar
    Commented Jul 10, 2023 at 14:55
  • $\begingroup$ I agree, and must admit that I find the whole idea of having something predefined that will cause undefined behaviour if referenced somewhat troubling... in the same way that I find proofs of the non-existence of God or assertions that an arbitrary image must contain an encrypted steganographic message troubling. $\endgroup$ Commented Jul 10, 2023 at 18:56
  • 1
    $\begingroup$ Another reason for 3 is, C was designed to be suitable for OS kernels and device drivers, which often must do things like access absolute memory addresses. $\endgroup$
    – Davislor
    Commented Jul 11, 2023 at 18:44
  • 1
    $\begingroup$ @MarkMorganLloyd: The term "Undefined Behavior" means nothing more than that the Standard waives jurisdiction over a the behavior of a construct. It does not imply judgment as to whether some ways of processing a construct might make an implication suitable for wider or narrower ranges of tasks than other ways of processing it. $\endgroup$
    – supercat
    Commented Jul 11, 2023 at 22:57
  • 1
    $\begingroup$ @supercat "Undefined behaviour" does not just mean that the behaviour "of a construct" is undefined, but that the entire behaviour of a program is undefined if at least one instance of undefined behaviour occurred during execution. C compilers do perform optimizations today that are only valid if constraints hold that were inferred from "if this condition wouldn't be true, this other line in the program would have caused undefined behaviour." $\endgroup$ Commented Jul 12, 2023 at 11:24
13
$\begingroup$

One example is that some computers would trap if an invalid bit pattern were loaded into one of the pointer registers (such as the segment selector of an 80286 protected-mode far pointer, necessary on 16-bit Windows or OS/2). It would be difficult or impossible to detect these in advance, since user code could not examine the segment descriptor tables. The C standards committee did not want to constrain implementations from implementing these pointers in the most efficient way.

$\endgroup$
6
$\begingroup$

One example of a where an implementation could use this is signalling NaN.

Some implementations have a concept of 'signalling NaN' with unconventional behavior, such as raising a signal upon being encountered by the FPU. A concept of trap representation permits this, as a signalling NaN could just be a trap representation, whose 'undefined' (by the C standard) behavior is defined by the implementation to raise a signal.

Related Stack Overflow answer

$\endgroup$
4
$\begingroup$

It is sometimes not possible to initialize the value to the meaningful value when variable is first declared. While some languages would conveniently put 0, null or false for you, these values may pass as good when they are not. Some value throwing error immediately when used looks like a better candidate to initialize such fields.

This can also be done also with std::optional (.value() on empty optional throws the assertion error).

Of course this may only be efficient enough if supported by the hardware. Checking on purpose if we are maybe operating with "forbidden value" every time may not be good for performance reasons.

$\endgroup$
4
  • 1
    $\begingroup$ Related to this answer $\endgroup$
    – CPlus
    Commented Jul 10, 2023 at 7:36
  • $\begingroup$ Audrius, that would require having code that detects undefined behaviour in every possible situation, which could be quite expensive. Maybe not in this case, but in other cases. $\endgroup$
    – gnasher729
    Commented Jul 10, 2023 at 13:47
  • $\begingroup$ I would disagree that "undefined behavior" is a weird concept - it is behavior that the C/C++ language specifications do not make any requirements about. If the application, the compiler and the operating environment agree, they are perfectly free to define the behaviors themselves (and many times, especially with low level code, that sort of thing is necessary) $\endgroup$
    – poncho
    Commented Jul 10, 2023 at 14:12
  • 2
    $\begingroup$ @poncho: What is a weird concept is that some compiler writers insist that the Standard's waiver of jurisdiction over a construct implies a judgment that the construct is erronous rather than merely being less than 100% portable. $\endgroup$
    – supercat
    Commented Jul 11, 2023 at 4:05
4
$\begingroup$

Because the number of bits in a type may not be well defined

For most processors, operating with variables which are the processor's word length is most efficient. This maps directly onto the processor's register representation. If you have an "int" type which is the processor's word length though, you will get different ranges of values depending on the processor you compile for.

Because "safe" behaviour for trap values can be unknowable by anyone but the coder

Consider a state machine. If the state variable enumeration is outside the range of possible states, what should happen? Do we set the state variable back to some valid state? If so, which? Do we close the program? Reset the processor?

Making this "undefined" puts the onus onto the code author to explicitly define behaviour.

Because different processors may behave differently

Consider an integer at maximum, which you increment by 1. Should the value wrap around to zero, or limit at maximum? Different processors may have different opinions on that, and trying to define the behaviour in the language will make one or other processor a bad fit for the language. If this is undefined, it becomes a task for the compiler author on that processor to define it, and for the code author to handle the situation appropriately.

Because hardware features can have many side effects on the processor

If you write to a register which is intended to reset the processor on sending an appropriate value, the effect is clear!

Because the same operation can be valid or invalid in different situations

If you dereference an invalid pointer, what happens? If it's out of range of physical memory, some processors may throw an exception. Some will run perfectly normally and simply return all ones because the data bus is (normally) pulled high and no device has set a value. On an OS which manages memory, the OS will restrict pointer accesses by user programs to only addresses within their memory space - which may be virtual memory, so the process of dereferencing memory becomes yet more complex. And still for these OSes, device drivers are typically permitted to access memory which user programs cannot.

The range of possible operations is just too wide and too varied to define this in the language.

$\endgroup$
6
  • 1
    $\begingroup$ Different implementations having different widths for int isn't a reason for one of the implementations to have an int bit-pattern that traps when you use it in addition. A 16-bit and an 18-bit machine can each use any of the 2^16 or 2^18 possible values of int, assuming they're both 2's complement. The usual reason for integer trap representations is 1's complement, where instead of being -0 or an alternate encoding of 0, it's invalid to have a bit pattern with all the bits set, and signed arithmetic instructions will trap on it. $\endgroup$ Commented Jul 12, 2023 at 13:09
  • 1
    $\begingroup$ Signed integer overflow UB is separate from trap representations. So is bad-pointer UB. $\endgroup$ Commented Jul 12, 2023 at 13:11
  • $\begingroup$ @PeterCordes: On some platforms without anything resembling a carry flag, multi-precision arithmetic may be facilitated if code leaves a bit unused at the top of the lower words of a value, or (depending on the platform) requires that the top bit of a lower word be duplicated as the bottom bit of the word above it. Computations with integers having invalid bit patterns may not be "trapped", but might behave unpredictably. $\endgroup$
    – supercat
    Commented Jul 12, 2023 at 21:30
  • 1
    $\begingroup$ @supercat: True, but that's not what this answer is claiming. It's talking about C source that uses int when that's the processors register width. $\endgroup$ Commented Jul 12, 2023 at 22:23
  • $\begingroup$ @PeterCordes: The principle could apply with int on a machine with e.g. a 12-bit register width and no carry flag (I don't know how the 12-bit PDP machines handled multi-precision arithmetic), and to the unsigned type on ones'-complement machines which may require that the upper bit be zero. $\endgroup$
    – supercat
    Commented Jul 12, 2023 at 22:37
3
$\begingroup$

If a hardware platform's largest integer type is smaller than 32 bits, and it doesn't support multi-precision arithmetic using a carry flag, the most efficient way to support the C standard's mandated larger integer types may be to leave the top bit of the lower words of each value clear, so as to allow code to easily add part of a value and determine whether it would have generated a carry out. Addition of X2:X1:X0 to Y2:Y1:Y0 to yield result Z2:Z1:Z0 on a 16-bit platform could be done via something like:

temp1 = X0+Y0;
temp2 = temp1 >> 15;
Z0 = temp1 & 0x7FFF;
temp2 += X1;
temp2 += Y1;
temp1 = temp2 >> 16;
Z1 = temp2 & 0x7FFF;
temp1 += X2;
temp1 += Y2;
Z2 = temp1;

Note that if bit 15 of X0, Y0, X1, or Y1 was set before performing an addition operation, that may result in the computed value being grossly wrong.

The Standard waives jurisdiction over how an implementation should process such cases by classifying problematic bit patterns as "trap representation" and waiving any jurisdiction over how implementations behave when code attempts to process them.

Note that the Standard's allowance for implementations that target unusual platforms handling corner cases in weird and unpredictable ways is not intended to imply that programs which are intended solely for use on more conventional platforms should not be written in ways that exploit the semantics of such platforms. In the language the C Standard was chartered to describe, the phrase "non-portable or erroneous" is used, among other things, to describe actions which the Committee would have expected 99% of C implementations to process in 100% consistent fashion.

$\endgroup$
2
$\begingroup$

One reason is hardware compatibility. C needs to work on systems like Itanium with its not-a-thing (NaT) bit. Or on those that recognize invalid pointer representations (possible if the address size is different from the register size) and trap them.

$\endgroup$
3
  • 1
    $\begingroup$ CHERI is one architecture (architectural feature, strictly) in which in-memory representations of pointers may be invalid and unusable. $\endgroup$ Commented Jul 11, 2023 at 7:31
  • $\begingroup$ Invalid-pointer UB is a separate thing from trap representations in the C standard. IIRC, it's UB to even create a pointer that isn't pointing inside an object or to one-past-the-end, or that's misaligned. So even pointer math on pointers that aren't to valid C objects is outside what the ISO C standard defines. (Implementations suitable for systems programming normally do allow pointer math to work like programmers expect for treating all of RAM as an array, though.) $\endgroup$ Commented Jul 12, 2023 at 13:16
  • $\begingroup$ @PeterCordes: The notion of "work like programmers expect" sound a bit like the maligned "DWIM" (Do What I Mean). A better description would be that such implementations use an abstraction model in which the state of every object of type T whose address is observable is fully encapsulated at all times in the bit patterns held by of sizeof(T) bytes starting at the object's address, and avoid optimizing transforms that might deviate from that model in ways that would cause problems, and are attentive to evidence that certain transformations would be dangerous and should thus be avoided. $\endgroup$
    – supercat
    Commented Jul 12, 2023 at 15:28
1
$\begingroup$

A value is stored in a sequence of n bits. There are 2^n possible bit combinations. If the number of possible values is not a power of two then bit combinations are possible which are not legal values, and we call them trap representations.

For example an enum with three possible values would have to have a trap representation. You except that

if (x == case1 || x == case2 || x == case3)

should always be evaluated as true, but if you somehow manage to have a different bit pattern in x, then this wouldn't or shouldn't be the case.

$\endgroup$
7
  • 1
    $\begingroup$ No, that's simply out-of-range values, which don't ordinarily cause a processor trap. $\endgroup$ Commented Jul 10, 2023 at 17:32
  • $\begingroup$ @TobySpeight A trap representation is not the same thing as a processor trap. It's an oddity of the design of C that enum types don't have trap representations (unless the underlying integer type does). Pointers in C do typically have trap representations, and you don't necessarily get a hardware trap when you try to dereference a trap representation: you might get unpredictable content or cause unpredictable effects instead if the pointer happens to contain the address of some control structures or some memory-mapped hardware. $\endgroup$ Commented Jul 10, 2023 at 21:02
  • $\begingroup$ @Gilles'SO-stopbeingevil': On the flip side, bool may cause weird and nonsensical behavior if the underlying bit representation has anything other than the least-significant bit set. For example, given int1 = bool1; if (int1 < 2) array1[int1] = 2; a compiler might generate code which would unconditionally store 1 to the element of array[1] indexed by the bottom byte of bool1, without testing whether it was less than 2. $\endgroup$
    – supercat
    Commented Jul 11, 2023 at 22:50
  • $\begingroup$ @supercat: related re: bool with an invalid bit-pattern: Does the C++ standard allow for an uninitialized bool to crash a program? - yes, violating the ABI can lead to crashes. Formally I'm not 100% sure whether to class this as a "trap representation" for bool or something else, like "uninitialized". $\endgroup$ Commented Jul 12, 2023 at 13:22
  • $\begingroup$ @PeterCordes: Given that such a bit pattern can occur as a result of writing a bool object using an unsigned char*, and that an object whose value has been written via unsigned char* is not "uninitialized", I can't think of any way in which "trap representation" is less accurate than any other term I can imagine. $\endgroup$
    – supercat
    Commented Jul 12, 2023 at 15:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .