Hidden read of indeterminate memory

[Holger Hasselbach]

[Annex J.2 Undefined behavior]
- The value of the object allocated by the malloc function is used
(7.20.3.3).
- The value of any bytes in a new object allocated by the realloc
function beyond the size of the old object are used (7.20.3.4).

Something like this (include and checkings omitted):

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;

a = p[4];

is obviously undefined, because p[4] was not initialised. But what
happens for the "hidden" read access when realloc'ing the memory:

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;

p = realloc(p, sizeof(*p) * 10);

where p[3] and p[4] are moved to the new memory location, when it is a
new location, of course? The same applies for memmove and memcpy.

My assumptions are:

- The values of the bytes are not "used" in the sense of the above
definition for undefined behavior.

- The library functions do their work on arrays of bytes, which is
always well defined for any object type even for indeterminate values.
OTOH, there is no exception in the above definition: "value of any
bytes [...] are used".

- Thinking of it, the same would apply for the padding inside structs
that could only be initialised by accessing the struct as an array of
bytes. OTOH, there could be a deeper reason for the existence of
calloc()...

What do you mean?


Holger

 

[Chris Torek]

Something like this (include and checkings omitted):

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;
a = p[4];

is obviously undefined, because p[4] was not initialised. But what
happens for the "hidden" read access when realloc'ing the memory:

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;
p = realloc(p, sizeof(*p) * 10);

where p[3] and p[4] are moved to the new memory location, when it is a
new location, of course? The same applies for memmove and memcpy.

The C standard is, in a way, "of two minds" about bit-patterns in
uninitialized memory, including memory from malloc(). (Uninitialized
automatic objects have the same problem, along with -- as you
mention -- padding inside initialized struct objects.) Reading
them produces undefined behavior, yet memcpy() must necessarily be
able to copy them.

The solution to this dilemma lies in the properties of "unsigned
char". There are no trap representations in "unsigned char", and
the bytes that "unsigned char"s are -- even if this is more than
8 bits long -- cover all the bits in any sub-object. This implies,
even if the standard does not say outright (and I have not checked
to see whether it does), that even an uninitialized object's
undefined-behavior values can be inspected in a defined-behavior
manner simply by breaking the object down into its component
"unsigned char" bytes. The bit patterns in each such byte never
produce undefined behavior.

Then, as long as mempcy() and friends -- including realloc() --
deal with these unintialized locations "as if" by using unsigned
char to copy the bit patterns, no undefined behavior occurs. Of
course, nothing can be said about the objects' undefined values
staying the same across such copies. In this particular sense they
are sort of Schroedinger's Cats of values: the only way to find
out if they are unchanged across a memcpy() is to inspect them,
and inspecting them gives undefined behavior, so that you no longer
know if an uninspected-copy might have changed them after all.

(And here we thought there was no quantum physics involved in C
programming...! )

 

[Malcolm]

The library functions do their work on arrays of bytes, which is
always well defined for any object type even for indeterminate values.
OTOH, there is no exception in the above definition: "value of any
bytes [...] are used".

This is the answer. If you are writing memcpy() in C, then it is necessary
to cast to an array of unsigned char to avoid trap representations.

Of course, normally memcpy() won't be implemented in C, and it will be
possible to move memory in greater quanties than one byte at a time without
problems.

 

[pete]

Something like this (include and checkings omitted):

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;
a = p[4];

is obviously undefined, because p[4] was not initialised. But what
happens for the "hidden" read access when realloc'ing the memory:

p = malloc(sizeof(*p) * 5);
p[0] = 1; p[1] = 1; p[2] = 1;
p = realloc(p, sizeof(*p) * 10);

where p[3] and p[4] are moved to the new memory location, when it is a
new location, of course? The same applies for memmove and memcpy.

The C standard is, in a way, "of two minds" about bit-patterns in
uninitialized memory, including memory from malloc(). (Uninitialized
automatic objects have the same problem, along with -- as you
mention -- padding inside initialized struct objects.) Reading
them produces undefined behavior, yet memcpy() must necessarily be
able to copy them.

The solution to this dilemma lies in the properties of "unsigned
char". There are no trap representations in "unsigned char", and
the bytes that "unsigned char"s are -- even if this is more than
8 bits long -- cover all the bits in any sub-object. This implies,
even if the standard does not say outright (and I have not checked
to see whether it does), that even an uninitialized object's
undefined-behavior values can be inspected in a defined-behavior
manner simply by breaking the object down into its component
"unsigned char" bytes. The bit patterns in each such byte never
produce undefined behavior.

I don't think traps have anything to with it.

If the standard committee doesn't care about what happens
when you try to inspect uninitialized objects,
then that's all that it takes to invoke undefined behavior
from trying to inspect an uninitialized object.
A mechanism involving other more familiar
types of undefined behavior, is not required.

N869
6.7.8 Initialization
[#10] If an object that has automatic storage duration is
not initialized explicitly, its value is indeterminate.

new.c is undefined behavior, right ?

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
unsigned char byte;

printf("%u\n", (unsigned)byte);
return 0;
}

/* END new.c */

 

[Jack Klein]

I don't think traps have anything to with it.

If the standard committee doesn't care about what happens
when you try to inspect uninitialized objects,
then that's all that it takes to invoke undefined behavior
from trying to inspect an uninitialized object.
A mechanism involving other more familiar
types of undefined behavior, is not required.

N869
6.7.8 Initialization
[#10] If an object that has automatic storage duration is
not initialized explicitly, its value is indeterminate.

new.c is undefined behavior, right ?

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
unsigned char byte;

printf("%u\n", (unsigned)byte);
return 0;
}

/* END new.c */

No, it is not.

Any object value, even one which is not a valid value representation
for the type of object it inhabits, may be inspected freely as
individual unsigned chars.

Paragraph 4 of 6.2.6.1 (C99) makes this clear, before paragraph 5
introduces the concept of trap representations. And even there in
paragraph 5, an exemption is specifically made for lvalues of
character type.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Chris Torek]

I don't think traps have anything to with it.

Sure they do. Consider:

extern void use(double);

void f(void) {
double x; /* uninitialized and therefore a signalling NaN */

use(x);
}

Here the uninitialized value in "x" really, actually, does cause
a SIGFPE floating-point exception on real, actual systems. This
is the kind of reasoning that leads one to put "reading uninitialized
objects' values produces undefined behavior" in a standard.

If the standard committee doesn't care about what happens
when you try to inspect uninitialized objects,
then that's all that it takes to invoke undefined behavior
from trying to inspect an uninitialized object.
A mechanism involving other more familiar
types of undefined behavior, is not required.

This is also true: once the Standard says "this produces undefined
behavior", you are stuck (unless and until a future standard or
Defect Report or Technical Corrigendum changes it anyway).

But, as I said, the Standard is in a way "of two minds" about
"unsigned char" values, because one can write a strictly conforming
memcpy()-like function thus:

void *like_memcpy(void *dst, const void *src, size_t len) {
size_t i;
unsigned char *d = dst, const *s = src;

for (i = 0; i < n; i++)
d = s;
return dst;
}

and then we can have a union containing structures:

void f(void) {
union {
struct { double x; } a;
struct { double x, y; } b;
} u, v;

u.a.x = 3.14159;
/* u.b.y remains uninitialized and is actaully a signalling NaN */
like_memcpy(&v, &u, sizeof v);
-> /* ... */
}

At the marked line, v.b.y is a bitwise copy of the signalling NaN
in u.b.y, and is itself a signalling NaN. The Standard claims that
reading either of u.b.y or v.b.y produces undefined behavior (and
on our real, actual system, reading either one delivers a SIGFPE);
but the Standard requires that like_memcpy() work anyway, even
though it reads the bytes making up u.b.y.

In the C99 draft I use, this special dispensation for "unsigned
char" is given out in section 6.1.2.8 ("Representations of types").

N869
6.7.8 Initialization
[#10] If an object that has automatic storage duration is
not initialized explicitly, its value is indeterminate.

new.c is undefined behavior, right ?

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
unsigned char byte;

printf("%u\n", (unsigned)byte);
return 0;
}

Per that section, it produces undefined behavior. Per 6.1.2.8
(probably a different number in your draft), however, it does *not*
produce undefined behavior, because we have put the object
representation of this indeterminate value into an (array of 1
element of type) unsigned char. (The "array of 1" part here is
true for all ordinary objects: given T obj, &obj is suitable for
assignment to a pointer P of type "T *", and then used as if only
the one element P[0] exists. 6.1.2.8 talks about an array of type
"unsigned char[n]" holding "object representations".)

Ultimately, then, the motivation for undefined behavior on the use
of uninitialized values (including trap representations) collides
with the motivation for allowing "unsigned char" to access the
bytes making up any object, including objects only partially
initialized (such as u.b, whose x member overlaps that of u.a).
I claim that one of these must win, and the one that must win is
the latter. But -- as I noted earlier -- no one can use this to
any useful effect in any (pure) C program, as they merely get a
"Schrodinger's Cat" (as it were) in the object representation
resulting from this kind of inspection of such an uninitialized
variable. ("Impure" or non-portable C code might use it to see
whether, for instance, the operating system on which the C system
runs clears pages before handing them out, or leaves cleartext
passwords and such accessible.)

 

[pete]

I don't think traps have anything to with it.

Sure they do. Consider:

extern void use(double);

void f(void) {
double x; /* uninitialized and therefore a signalling NaN */

use(x);
}

Here the uninitialized value in "x" really, actually, does cause
a SIGFPE floating-point exception on real, actual systems. This
is the kind of reasoning that leads one to put "reading uninitialized
objects' values produces undefined behavior" in a standard.

If the standard committee doesn't care about what happens
when you try to inspect uninitialized objects,
then that's all that it takes to invoke undefined behavior
from trying to inspect an uninitialized object.
A mechanism involving other more familiar
types of undefined behavior, is not required.

This is also true: once the Standard says "this produces undefined
behavior", you are stuck (unless and until a future standard or
Defect Report or Technical Corrigendum changes it anyway).

But, as I said, the Standard is in a way "of two minds" about
"unsigned char" values, because one can write a strictly conforming
memcpy()-like function thus:

void *like_memcpy(void *dst, const void *src, size_t len) {
size_t i;
unsigned char *d = dst, const *s = src;

for (i = 0; i < n; i++)
d = s;
return dst;
}

and then we can have a union containing structures:

void f(void) {
union {
struct { double x; } a;
struct { double x, y; } b;
} u, v;

u.a.x = 3.14159;
/* u.b.y remains uninitialized and is actaully a signalling NaN */
like_memcpy(&v, &u, sizeof v);
-> /* ... */
}

At the marked line, v.b.y is a bitwise copy of the signalling NaN
in u.b.y, and is itself a signalling NaN. The Standard claims that
reading either of u.b.y or v.b.y produces undefined behavior (and
on our real, actual system, reading either one delivers a SIGFPE);
but the Standard requires that like_memcpy() work anyway, even
though it reads the bytes making up u.b.y.

In the C99 draft I use, this special dispensation for "unsigned
char" is given out in section 6.1.2.8 ("Representations of types").

N869
6.7.8 Initialization
[#10] If an object that has automatic storage duration is
not initialized explicitly, its value is indeterminate.

new.c is undefined behavior, right ?

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
unsigned char byte;

printf("%u\n", (unsigned)byte);
return 0;
}

Per that section, it produces undefined behavior. Per 6.1.2.8
(probably a different number in your draft), however, it does *not*
produce undefined behavior, because we have put the object
representation of this indeterminate value into an (array of 1
element of type) unsigned char. (The "array of 1" part here is
true for all ordinary objects: given T obj, &obj is suitable for
assignment to a pointer P of type "T *", and then used as if only
the one element P[0] exists. 6.1.2.8 talks about an array of type
"unsigned char[n]" holding "object representations".)

Ultimately, then, the motivation for undefined behavior on the use
of uninitialized values (including trap representations) collides
with the motivation for allowing "unsigned char" to access the
bytes making up any object, including objects only partially
initialized (such as u.b, whose x member overlaps that of u.a).
I claim that one of these must win, and the one that must win is
the latter. But -- as I noted earlier -- no one can use this to
any useful effect in any (pure) C program, as they merely get a
"Schrodinger's Cat" (as it were) in the object representation
resulting from this kind of inspection of such an uninitialized
variable. ("Impure" or non-portable C code might use it to see
whether, for instance, the operating system on which the C system
runs clears pages before handing them out, or leaves cleartext
passwords and such accessible.)

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

 

[Kevin D. Quitt]

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

Please trim your posts, and no, you're not right. Using the value of any
unsigned char is always defined behaviour.

 

[Holger Hasselbach]

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

As far as I understand it now, thanks to the excellent explanations
from Chris, the C system of object storage can be expressed in three
layers.

Layer 3: Interpretation - Used values
Layer 2: Representation - Pure binary, unsigned char
Layer 1: Storage - Hardware

On the bottom is the hardware with the physical memory where the data
is stored and read from. Physical means, as usual, a real machine or a
virtual simulated one. It doesn't matter. The storage has to use the
provided addressing scheme and the memory format, e.g. the number of
bits per address.

On the second layer is the C data representation, based on a pure
binary representation with any bit used, no padding and no traps. It
is the compiler writer's task to provide the mapping between this
representation and the storage. For most of todays computers it is a
simple 1:1 mapping, because they are binary with a flat memory of a
given bitwidth. But there could be a computer that uses three states
per bit: 0, 1 and 2. The 'bit' would then be a ternary digit, a, erm,
'tit'. But because the representation is already an abstraction from
the hardware, it is possible to write a conforming compiler for this
system by implementing the mapping between the representation's bits
and the storage's tits. It could be a 1:1 mapping with simply ignoring
the third state, or it could be a compressed mapping with some fancy
calculations using the powers of 2 and 3.

On the third layer is the interpretation, the working with the values.
When you make an assignment like p=NULL, you are working with the
value NULL. The values are based on the representation, and there is a
mapping between them. It is the second level of abstraction. The
abstraction goes so far that there can be different representations
for the same value. When you make a compare of these values, they are
required to compare as equal, because the comparision is defined on
the interpretation layer, not on the representation layer.

Layer 3: NULL == NULL p == a
Layer 2: 0x00000000 != 0xffffffff memcmp(&p, &a, sizeof(p)) != 0

And of course there can be the trap representations without a mapping
to the interpretation at all. Obviously, the same representation maps
to different values for different object types, the mapping is
type-sensitive.

All C object types are working in layer 3. Working with those objects
is always working with values that are mapped from the representation
before a read and mapped to the representation after the write.

Layer 3: +-- Write p = a; Read <-+
V |
Layer 2: xxxxxxxx xxxxxxxx

All objects including unsigned char, with the only exception that the
mapping between layer 2 and 3 is a must-have 1:1 for this type,
without any traps. Thus unsigned char provides a direct access to the
representation even for indeterminate data.

Both layers 2 and 3 are pure abstractions. They can be mapped 1:1 down
to layer 1, but it is also possible to have 3 completely different
representations of data on each layer.

Layer 3: p = 0; (Value 0)
Layer 2: 0xffffffff (Binary representation of a NULL pointer)
Layer 1: All tits 2 (0 mapped to 1-tit, 1 mapped to 2-tit)

Because layer 2 is a pure mapping without any data context, and all C
functionality happen in layer 3 with the context and traps, it makes
sense to allow undefined behaviour only on layer 3, not on layer 2.
This is what Chris meant with Schrodinger: You can move the
representation data of an object with unsigned char arrays and compare
the representation as equal, but you can't compare the object values
on layer 3 (except for unsigned char itself) when the data is
indeterminate. As soon as you read it you have undefined behaviour,
including the spontaneous change of the previously read values. Thus
you know that the values should be equal, but you can't prove it.


Did I get it right? Or halfway right? Or right with some
over-interpretation?


Holger

 

[pete]

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

Also, are you saying that there is no such thing as an
indeterminate unsigned char value ?

 

[Jeremy Yallop]

Please trim your posts, and no, you're not right. Using the value of any
unsigned char is always defined behaviour.

I think that "unspecified" is right. For instance, consider reading
from a union member of type unsigned char after writing to a different
member (of type float, say). The bit pattern of the object must yield
a valid value when interpreted as unsigned char, but /which/ value
depends on the representation that the implementation uses for float.

Jeremy.

 

[Chris Torek]

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

This one I leave to the Tea-Leaf Readers in comp.std.c. It is
not a particularly useful thing to do; without some particularly
good reason to try to tease "produces unspecified behavior" apart
from "obtains (and thus in a sense determines) an indeterminate
value", I am simply not going to bother -- particularly since I am
still using a C99 draft, and the precise wording may have changed.

 

[pete]

This one I leave to the Tea-Leaf Readers in comp.std.c. It is
not a particularly useful thing to do; without some particularly
good reason to try to tease "produces unspecified behavior" apart
from "obtains (and thus in a sense determines) an indeterminate
value", I am simply not going to bother -- particularly since I am
still using a C99 draft, and the precise wording may have changed.

According to:
1 the definition of undefined behavior
2 the fact that uninitialized objects have indeterminate value

I don't think that a program is required to reserve storage
for an uninitialized object,
unless the address is of the object is taken.

 

[Ben Pfaff]

I understand you to mean that the use
of an indeterminate unsigned char value,
is unspecified behavior.
Is that right ?

If the use of an indeterminate unsigned char value is undefined,
instead of unspecified, then memcpy() of a structure type is
generally undefined. Because this is an absurdity, I conclude
that use of indeterminate unsigned char values is not undefined.

 

[glen herrmannsfeldt]

pete wrote:

(snip)

According to:
1 the definition of undefined behavior
2 the fact that uninitialized objects have indeterminate value

I don't think that a program is required to reserve storage
for an uninitialized object,
unless the address is of the object is taken.

Maybe not.

One I did hear about, and posted in another, unrelated, thread,
was a system that initially mapped the same page of real memory
to all allocated virtual memory, and marked that page read only.

When it was actually written to, a new, read/write page is
allocated, the page tables are changed, and the data is written
into that page.

The unexpected effect came when someone wanted to test the
speed of memory access, minimizing the effect of a cache.

The test program malloc()'ed a large region of memory and
continually accessed it. It was enough larger than the cache
that it was expected all access to go to real memory.

As it didn't seem to matter what the data was, nothing was
ever written to the memory. Well, only one real page was
allocated, small enough to fit in the cache, and so the cache
speed was measured.

It might be possible on some systems to initially map such
pages so that they couldn't be read, and have undesirable
side effects. It doesn't seem much harder, though, to map
to a single page, assuming that a paging system is in use.

There are unexpected effects that can occur when memory is
read without first being written. Because of the cases where
this could happen, unintentionally, in real programs, systems
should make sure that the effects aren't too bad.

Padding bytes of structures, for example, are normally not
written, yet one could reasonably expect to be able to copy
a structure with memcpy().

-- glen

 

[pete]

If the use of an indeterminate unsigned char value is undefined,
instead of unspecified, then memcpy() of a structure type is
generally undefined. Because this is an absurdity, I conclude
that use of indeterminate unsigned char values is not undefined.

The body of the definition of memcpy need only obey the rules of C,
if it's written in C, and it need not be written in C.

If it turns out that memcpy can't be portably written in C,
it doesn't matter much. It doesn't change any C programs.
Dan Pop has pointed out that the string functions in the
standard library can't be written in portable C.
But that only makes a difference if you're trying to write
a library string function in portable C.
I don't know how important that is;
I don't know anybody who is trying to do that.

 

[Ben Pfaff]

The body of the definition of memcpy need only obey the rules of C,
if it's written in C, and it need not be written in C.

If it turns out that memcpy can't be portably written in C,
it doesn't matter much. It doesn't change any C programs.
Dan Pop has pointed out that the string functions in the
standard library can't be written in portable C.

Really. Why not?

 

[pete]

Really. Why not?

Because, according to the definition of 'string',
it's possible for a string to span several unrelated arrays,
in which case, walking a pointer along such a string,
would overrun an array boundary.

At the time, Dan Pop was specifically refering
to string functions which dealt with strings.
Those functions take pointers to strings as arguments,
instead of pointers to arrays.

 

[pete]

The undefined behavior caused by the use of an indeterminate value is
due to possible trap representations. But the unsigned char is
guaranteed to have no trap representation.


The program is always required to reserve storage to hold an object
USED in it. Are you talking about optimization?


Yes. But your code is not a s.c. program whose output depends on an
unspecified value.


There is no wording to say that it's undefined in C99; C90 says that
all uses of an indeterminate value result in undefined behavior,
which differs from C99.

Thank you.

 

[Chris Torek]

As far as I understand it now, thanks to the excellent explanations
from Chris, the C system of object storage can be expressed in three
layers.

Layer 3: Interpretation - Used values
Layer 2: Representation - Pure binary, unsigned char
Layer 1: Storage - Hardware

This is certainly a workable (and nice, and concise) model that
fits with what the Standard requires. Whether it is the only
possible model, i.e., completely isomorphic to what the C99 standard
says, I am not sure -- but it is much more *usable* than the C99
wording.

[rest snipped]

[Incidentally, the usual contraction for a ternary digit is "trit".
Theoretically, the "most efficient" hardware representation might
be to use base e, and 3 is closer to e (3-2.71828... < 0.3) than
it is to 2 (2.71828...-2 > 0.7), so base-3 (trinary or ternary)
computers might be "more efficient" than base-2 (binary). It is
not clear whether C would be a good language for ternary computing,
though.]