C Stack allocation

[sandeep]

int array[2][3] = { { 0, 1, 2 }, { 3, 4, 5 } }; int *p = &array[0] [3];
// no problem int *q = &array[1][0]; // no problem assert (p == q);
// no problem assert (*q == 3); // no problem assert (*p
== 3); // U.B.; p not dereferenceable

No, he actually wrote the following:

int array[2][3] = { { 0, 1, 2 }, { 3, 4, 5 } }; int *p =
&array[0][3]; // no problem int *q = &array[1][0]; // no
problem assert (p == q); // no problem assert (*q == 3);
// no problem assert (*p == 3); // U.B.; p not
dereferenceable

Please figure out how to keep your newsreader from mangling quoted text.

Sorry about that, I just hit reply and that was what came out.

You need to understand what "undefined behavior" means. It doesn't mean
"the program will crash". It means, to quote C99 3.4.3:

behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this International Standard imposes
no requirements

"imposes no requirements". Nothing more, nothing less.

I would expect an undefined behavior to be segmentation fault, memory or
files overwritten, etc. If a program behaves correctly on all compilers,
I would call that a defined behavior!

The behavior is undefined *because the standard doesn't define the
behavior*. If you disagree, show us where the standard defines the
behavior.

My understanding is that it is *guaranteed* that a multidimensional array
will be stored in a contiguous block of memory in rowmajor order. This is
certainly what my textbook says. Perhaps Mr. Sosmanji is making another
obscure point though?

 

[Dann Corbit]

Eric Sosman writes:
int array[2][3] = { { 0, 1, 2 }, { 3, 4, 5 } }; int *p = &array[0]
[3];
// no problem int *q = &array[1][0]; // no problem assert (p
== q);
// no problem assert (*q == 3); // no problem
assert (*p
== 3); // U.B.; p not dereferenceable

No, he actually wrote the following:

int array[2][3] = { { 0, 1, 2 }, { 3, 4, 5 } }; int *p =
&array[0][3]; // no problem int *q = &array[1][0]; // no
problem assert (p == q); // no problem assert (*q == 3);
// no problem assert (*p == 3); // U.B.; p not
dereferenceable

Please figure out how to keep your newsreader from mangling quoted text.

Sorry about that, I just hit reply and that was what came out.

You need to understand what "undefined behavior" means. It doesn't mean
"the program will crash". It means, to quote C99 3.4.3:

behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this International Standard imposes
no requirements

"imposes no requirements". Nothing more, nothing less.

I would expect an undefined behavior to be segmentation fault, memory or
files overwritten, etc. If a program behaves correctly on all compilers,
I would call that a defined behavior!

The behavior is undefined *because the standard doesn't define the
behavior*. If you disagree, show us where the standard defines the
behavior.

My understanding is that it is *guaranteed* that a multidimensional array
will be stored in a contiguous block of memory in rowmajor order. This is
certainly what my textbook says. Perhaps Mr. Sosmanji is making another
obscure point though?

A compiler vendor is free to (for instance) trigger a core dump when you
access an array bounds out of range.

It may seem silly in this sense (since there is another data point right
under the pointer given reasonable assumptions). However, I think it
could easily be a nice feature. If you access an array a[2][2] with
either index >= 2, it is likely it is a programming error and a core
dump will likely be helpful.

The point is that access the array in a method that is not defined might
do what you expect (give you the next element). Or it could cause a
core dump or it could cause your computer to start whistling dixie and
jumping about the room.

Just because you cannot envision a behavior that does not make sense to
you does not mean that the behavior is not possible or even that the
behavior is not desirable.

 

[Keith Thompson]

Keith Thompson writes: [...]

You need to understand what "undefined behavior" means. It doesn't mean
"the program will crash". It means, to quote C99 3.4.3:

behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this International Standard imposes
no requirements

"imposes no requirements". Nothing more, nothing less.

I would expect an undefined behavior to be segmentation fault, memory or
files overwritten, etc. If a program behaves correctly on all compilers,
I would call that a defined behavior!

Then your expectation is incorrect. That quite simply is not what the
phrase "undefined behavior" means. Please re-read what I wrote above,
and do not assume that any preconceived notions you might have are
necessarily correct, no matter how much sense they seem to make to you.

My understanding is that it is *guaranteed* that a multidimensional array
will be stored in a contiguous block of memory in rowmajor order. This is
certainly what my textbook says. Perhaps Mr. Sosmanji is making another
obscure point though?

Your understanding about the way multidimensional arrays are allocated
is correct. It follows from the fact that 1-dimensional arrays are
contiguous with no gaps (I don't actually have chapter-and-verse for
that off the top of my head) and that multidimensional arrays are
nothing more than arrays of arrays.

But it doesn't follow from this that an array indexing operation can
extend beyond the bounds of the array on which it's based.

The indexing operator [] is defined in terms of pointer arithmetic,
specifically the "+" operator whose operands are a pointer and
an integer (x[y] is equivalent to *(x+y)). The semantics of "+"
are explained in C99 6.5.6p8. In particular:

If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the
array object, the evaluation shall not produce an overflow;
otherwise, the behavior is undefined. If the result points one
past the last element of the array object, it shall not be used
as the operand of a unary * operator that is evaluated.

Given the code in question:

int array[2][3] = { { 0, 1, 2 }, { 3, 4, 5 } };
int *p = &array[0][3]; // no problem

the "pointer operand" is ``&array[0]'', and the RHS of the implicit
"+" is 3. The "same array object" is the 0th element of ``array'',
which is of type int[3]. The addition itself is ok, since it
yields a pointer one past the last element of the array object,
but the behavior of dereferencing it is undefined. Yes, there's an
int object at that location, namely array[1][0], but *that doesn't
mean you can dereference the pointer*.

If the standard doesn't define the behavior, the behavior is
undefined (unless the implementation chooses to define it).

As for *why* it's not defined, here's an example. Suppose a
given CPU has an indexed addressing mode that allows an offset to
be specified in some particularly efficient way, but only for
offsets up to N bytes. For larger offsets, you need to perform
an explicit addition, which costs a couple of extra instructions
and some extra time. If the compiler sees an expression arr[x]
and it knows that x is no bigger than N bytes, it can use the more
efficient addressing mode. If x happens to be bigger than N,
then it doesn't work properly (maybe it wraps around, maybe it
melts the CPU). In effect, you lied to the compiler, implicitly
claiming that arr[x] doesn't go beyond the bounds of arr. And the
sad part is that you wrote the code 10 years ago, and it's worked
"correctly" ever since then, but it failed last week when the code
was recompiled for a new platform.

I'm not saying that this specific scenario is the rationale for
not defining array indexing beyond the bounds of an array, but this
is the general kind of thing you need to worry about -- or rather,
that you don't need to worry about if you stick to what the language
actually guarantees.

Incidentally, I realized after I snipped the quoted text that the C
code was mangled again. Please consult the documentation for your
newsreader and find out how to stop it from doing that.

 

[Anand Hariharan]

  7 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.

(Paragraph 7 doesn't appear in the C99 standard; it's more of a
clarification than new semantics.  Both C99 and N1256 have similar
wording for relational operators (<, <=, >, >=)).
(...)
For example, the following program could produce any of three possible
outputs:

#include <stdio.h>
int main(void)
{
    int x;
    int y;
    if (&y == &x + 1) {
        puts("&y == &x + 1");
    }
    else if (&x == &y + 1) {
        puts("&x == &y + 1");
    }
    else {
        puts("x and y are not adjacent");
    }
    return 0;

}

Are you saying &obj + 1 is no longer a constraint violation, or that
it never a constraint violation?

- Anand

 

[Ben Bacarisse]

  7 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.

(Paragraph 7 doesn't appear in the C99 standard; it's more of a
clarification than new semantics.  Both C99 and N1256 have similar
wording for relational operators (<, <=, >, >=)).
(...)
For example, the following program could produce any of three possible
outputs:

#include <stdio.h>
int main(void)
{
    int x;
    int y;
    if (&y == &x + 1) {
        puts("&y == &x + 1");
    }
    else if (&x == &y + 1) {
        puts("&x == &y + 1");
    }
    else {
        puts("x and y are not adjacent");
    }
    return 0;

}

Are you saying &obj + 1 is no longer a constraint violation, or that
it never [was] a constraint violation?

It has never been a constraint violation though I am not sure that's
what you mean (CVs must give rise to diagnostic messages from the
implementation).

It certainly does not invoke undefined behaviour. It has always been
perfectly legal to form the pointer that points just past the end of an
array or just past a single object. Accessing an object /using/ that
pointer has been undefined since the first C standard (1989).

 

[Nick]

I would expect an undefined behavior to be segmentation fault, memory or
files overwritten, etc.

Then you'd be wrong. That's why it's "undefined" - if it always did
particular things it would be defined as doing that.

If a program behaves correctly on all compilers,
I would call that a defined behavior!

But tomorrow a compiler, or an architecture, or both may come along
where it doesn't work that way: through accident, choice or because it's
not actually possible.

 

[Nick Keighley]

I would expect an undefined behavior to be segmentation fault, memory or
files overwritten, etc. If a program behaves correctly on all compilers,
I would call that a defined behavior!

it is meaningless to say "behaves correctly" as no correct behaviour
is defined!

My understanding is that it is *guaranteed* that a multidimensional array
will be stored in a contiguous block of memory in rowmajor order. This is
certainly what my textbook says. Perhaps Mr. Sosmanji is making another
obscure point though?

it is rude to intentionally mispell people's names

 

[James Kuyper]

it is meaningless to say "behaves correctly" as no correct behaviour
is defined!

It would be more accurate to say that when the behavior of a program is
undefined by the C standard, there's no behavior it could possibly have
that would be incorrect, at least not as far as the C standard is
concerned. Some other relevant standard, or the compiler's own
documentation, might define the behavior, but that still leaves the
behavior undefined, because of the peculiar definition the C standard
gives to the phrase "undefined behavior".

The user may have unjustified expectations about what the behavior
should be (as sandeep has in this case). If it doesn't behave as he
expected it to, he may be disappointed or annoyed. If it does behave as
he expected, he may derive unjustified confidence in the validity of his
code (as sandeep has done). But either way, it's correct behavior,
because it doesn't violate any requirements imposed upon it by the C
standard - because there are no such requirements.

 

[Ben Bacarisse]

[...] Perhaps Mr. Sosmanji is making another
obscure point though?

it is rude to intentionally mispell people's names

To be fair, the -ji suffix is a mark of respect and it is not considered
(by those that use it) to be altering the name itself.

 

[Anand Hariharan]

Are you saying &obj + 1 is no longer a constraint violation, or that
it never [was] a constraint violation?

It has never been a constraint violation though I am not sure that's
what you mean (CVs must give rise to diagnostic messages from the
implementation).

It certainly does not invoke undefined behaviour.  It has always been
perfectly legal to form the pointer that points just past the end of an
array or just past a single object.  Accessing an object /using/ that
pointer has been undefined since the first C standard (1989).

I did mean constraint violation -- Until Keith's post, I have never
tried to do pointer arithmetic on the address of (individual)
automatic variables, and have always believed it was a no-no. I have
been aware of the one past the last element of array, but did not know
it was okay to assume the single object as a single element array.

I'll admit I still do not see merit in the language allowing this.

- Anand

 

[Anand Hariharan]

it is rude to intentionally mispell people's names

It is stupid to attribute rudeness where respect was intended:

http://en.wikibooks.org/wiki/Hindi_Lessons/Lesson_2

- Anand

 

[bart.c]

The user may have unjustified expectations about what the behavior should
be (as sandeep has in this case). If it doesn't behave as he expected it
to, he may be disappointed or annoyed.

Does it mean I can't have code like this:

int a[2][3][4];
int b[2][3][4];
int i,j,k, *p;

p=(int*)a; /* step through 3d-array an element at a time */

for (i=1; i<=24; ++i)
*p++=i*10;

memcpy(b,a,sizeof(int)*24); /* and a byte at a time */

for (i=0; i<2; ++i)
for (j=0; j<3; ++j)
for (k=0; k<4; ++k)
printf("b[%d,%d,%d]=%d\n",i,j,k,b[j][k]);

 

[Eric Sosman]

[...]
I did mean constraint violation -- Until Keith's post, I have never
tried to do pointer arithmetic on the address of (individual)
automatic variables, and have always believed it was a no-no. I have
been aware of the one past the last element of array, but did not know
it was okay to assume the single object as a single element array.

I'll admit I still do not see merit in the language allowing this.

Consider strlen("") for a moment. The literal generates a
nameless object one byte long (the byte is '\0'). The strlen()
function wants to do pointer arithmetic on its parameter. So
we need a way to do arithmetic on pointers to single objects.

All right, maybe that's not convincing: We could claim that
the literal produces something that "really is" a one-byte array,
somehow different from a stand-alone byte. So let's try

int value;
fread(&value, sizeof value, 1, stream);

The variable `value' is not part of an array, yet fread() surely
wants to do pointer arithmetic on its first parameter. If that
arithmetic were not well-defined for pointers to isolated objects,
we'd either need to forbid the use of fread() on single variables
or somehow come up with two versions of the function.

The equivalence of single objects to one-element arrays (for
purposes of pointer arithmetic) isn't a Dramatically! Wonderful!
Feature! Everyone! Should! Use! Every! Day!, but a "regularization"
that makes a lot of special cases become non-special and thus
simplifies the language.

 

[Anand Hariharan]

[...]
I did mean constraint violation -- Until Keith's post, I have never
tried to do pointer arithmetic on the address of (individual)
automatic variables, and have always believed it was a no-no.  I have
been aware of the one past the last element of array, but did not know
it was okay to assume the single object as a single element array.

I'll admit I still do not see merit in the language allowing this.

     Consider strlen("") for a moment.  The literal generates a
nameless object one byte long (the byte is '\0').  The strlen()
function wants to do pointer arithmetic on its parameter.  So
we need a way to do arithmetic on pointers to single objects.

     All right, maybe that's not convincing: We could claim that
the literal produces something that "really is" a one-byte array,
somehow different from a stand-alone byte.  So let's try

        int value;
        fread(&value, sizeof value, 1, stream);

The variable `value' is not part of an array, yet fread() surely
wants to do pointer arithmetic on its first parameter.  If that
arithmetic were not well-defined for pointers to isolated objects,
we'd either need to forbid the use of fread() on single variables
or somehow come up with two versions of the function.

The prototype/implementation of fread has its first parameter/argument
as a void *. Notwithstanding that there are static code checkers
(e.g., Coverity) that will go several levels deep to see if pointer
arithmetic is being done on a Singleton, a typical implementation will
only see pointer arithmetic being done on a variable of pointer type.
To me, this example is similar to (or as convincing as) the example of
the one byte string literal you have above.

On the other hand, for an expression such as &obj + n, an
implementation can readily see that the address of a single variable
is taken, and pointer arithmetic is being done on it (even if the
integer literal is either zero or, as I have come to learn in this
case, one). I'd say it is not very different from sizeof array versus
sizeof &obj (in terms of how the implementation sees it).

- Anand

 

[Anand Hariharan]

Probably "ignorance" rather than "stupidity".

Perfectly understandable to not know something; not so to pass
judgment (to the opposite effect!) without knowing what it means. Am
sure no malice was intended.

 I guess it's similar to the
Japanese "-san" suffix?

Yes (just like the second paragraph in the wikibooks link above
suggests).

- Anand

 

[Ben Bacarisse]

Are you saying &obj + 1 is no longer a constraint violation, or that
it never [was] a constraint violation?

It has never been a constraint violation though I am not sure that's
what you mean (CVs must give rise to diagnostic messages from the
implementation).

It certainly does not invoke undefined behaviour.  It has always been
perfectly legal to form the pointer that points just past the end of an
array or just past a single object.  Accessing an object /using/ that
pointer has been undefined since the first C standard (1989).

I did mean constraint violation -- Until Keith's post, I have never
tried to do pointer arithmetic on the address of (individual)
automatic variables, and have always believed it was a no-no.[/QUOTE]

Making it a CV would have been difficult. CVs must be diagnosed by the
implementation and it's not clear what one would pick as the actual
constraint that is being violated. I'm not in any way advocating it --
I am just explaining why I thought it unlikely that you meant CV rather
than UB.

I have
been aware of the one past the last element of array, but did not know
it was okay to assume the single object as a single element array.

I'll admit I still do not see merit in the language allowing this.

Well, you can use the fact like this:

unsigned char *end = (unsigned char *)(&obj + 1);
for (unsigned char *cp = (unsigned char *)&obj; cp < end; cp++)
printf("[%x]", *cp);

to print an object's representation, though the same effect can be had
using sizeof. I think the main reason is the lack of a good reason to
treat

int x;
int a[1];

as significantly different in terms of pointing to the objects involved.

 

[Eric Sosman]

[...]
I did mean constraint violation -- Until Keith's post, I have never
tried to do pointer arithmetic on the address of (individual)
automatic variables, and have always believed it was a no-no. I have
been aware of the one past the last element of array, but did not know
it was okay to assume the single object as a single element array.

I'll admit I still do not see merit in the language allowing this.

[...]

int value;
fread(&value, sizeof value, 1, stream);

The variable `value' is not part of an array, yet fread() surely
wants to do pointer arithmetic on its first parameter. If that
arithmetic were not well-defined for pointers to isolated objects,
we'd either need to forbid the use of fread() on single variables
or somehow come up with two versions of the function.

The prototype/implementation of fread has its first parameter/argument
as a void *.

Yes, but what difference does that make? Eventually fread()
will convert the void* to some other pointer type, and will want
to do arithmetic on that pointer type, and will need to be assured
that the arithmetic is well-defined. (If you're worried that fread()
might not be written in C, just substitute a user-written function
that might plausibly accept a pointer to an array element or to an
isolated variable.)

Notwithstanding that there are static code checkers
(e.g., Coverity) that will go several levels deep to see if pointer
arithmetic is being done on a Singleton, a typical implementation will
only see pointer arithmetic being done on a variable of pointer type.

... and needs to be sure that the arithmetic is well-defined.
The equivalence of single objects to one-element arrays ensures that
the arithmetic generates no surprises.

To me, this example is similar to (or as convincing as) the example of
the one byte string literal you have above.

On the other hand, for an expression such as&obj + n, an
implementation can readily see that the address of a single variable
is taken, and pointer arithmetic is being done on it (even if the
integer literal is either zero or, as I have come to learn in this
case, one). I'd say it is not very different from sizeof array versus
sizeof&obj (in terms of how the implementation sees it).

I don't understand your point here, and don't see the connection
to pointer arithmetic.

 

[Ben Bacarisse]

The user may have unjustified expectations about what the behavior
should be (as sandeep has in this case). If it doesn't behave as he
expected it to, he may be disappointed or annoyed.

Does it mean I can't have code like this:

int a[2][3][4];
int b[2][3][4];
int i,j,k, *p;

p=(int*)a; /* step through 3d-array an element at a time */

for (i=1; i<=24; ++i)
*p++=i*10;

No, most people would say that that is fine. 'a' is converted to a
pointer to the first element of the array; that is to a pointer to the
first of two objects each the size of 12 ints. The converted pointer
can range over this whole array just as the unconverted pointer would be
able to do.

Writing p = a[0][0]; is another matter. a[0][0] is an array of four
ints and the standard is pretty clear that p now points to the first
element of this four-int array so it can be used to access those four
ints alone (hence the UB involved in, say, a[0][0][4]).

The corner case is p = &a[0][0][0]; Is this a pointer to the first of
four ints or to the start of the whole array? I imagine a lot of text
can be written on both sides but I'd come down on the former simply
because I think of X and &X[0] as behaving the same when X is an
expression of array type. Obviously I mean in "normal" expression
contexts -- i.e. sizeof and & operands excluded.

memcpy(b,a,sizeof(int)*24); /* and a byte at a time */

a and b point to the whole array so there is no problem here either.

<snip>

 

[crisgoogle]

it is rude to intentionally mispell people's names

I _think_ you're being serious, so:

"ji" is an honourific suffix. Similar to the Japanese "san", with
which
maybe you're more familiar.

 

[Anand Hariharan]

     ... and needs to be sure that the arithmetic is well-defined.
The equivalence of single objects to one-element arrays ensures that
the arithmetic generates no surprises.

That statement together with Ben's explanation in
<0.5b440229ea48f8dc8a19.20100610143204BST.874ohbm2sr.fsf@bsb.me.uk>
proved sufficient explanation for me.


To clarify what my difficulty was:

int a;
int *p = &a;

p + 1; /* Okay */
p + 100; /* UB, but no CV */

&a; /* Okay */

/* My difficulty begins here */

&a + 0; /* Neither UB nor CV */
&a + 1; /* Neither UB nor CV */
&a + 100; /* UB, but not CV */

All three statements above can be detected as CV by an implementation,
IMHO. I suppose that grammar is kept simple by simply treating the
address of a single object as a rvalue of a pointer type.

- Anand