C Stack allocation

[Ben Bacarisse]

To clarify what my difficulty was:

int a;

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

Any finite set of constructs can be detected but is the general rule
that you would want to detect? Would you allow or forbid:

int x;
scanf("%d", &x);
&a + x;

? What about:

void *vp = &a;
(int *)vp + 10;

? What would you allow or forbid inside f:

void f(int *arg);
f(&a);
f(&a + 1); /* arg[-1] is not UB inside f */

?

I suppose that grammar is kept simple by simply treating the
address of a single object as a rvalue of a pointer type.

What else might it be? You can't be suggesting that &a itself should be
prohibited?

 

[Anand Hariharan]

Any finite set of constructs can be detected but is the general rule
that you would want to detect?  Would you allow or forbid:

  int x;
  scanf("%d", &x);
  &a + x;

Forbid as CV (I was actually advocating even &a + 0 as CV).

?  What about:

  void *vp = &a;
  (int *)vp + 10;

?  What would you allow or forbid inside f:

UB, but not CV (I'd given something extremely similar as an example,
but it was snipped above).

  void f(int *arg);
  f(&a);
  f(&a + 1); /* arg[-1] is not UB inside f */

?

Forbid as CV.

What else might it be?  You can't be suggesting that &a itself should be
prohibited?

Of course not.

Am suggesting that using the address of a single object (so long as
the implementation can definitively see it as such) in an expression
that does arithmetic with it be prohibited. I suppose one can shoot
holes, and so I am willing to refine this based on what y'all throw at
me.

- Anand

 

[Keith Thompson]

To clarify what my difficulty was:

int a; [snip]
/* 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.

Constraint violations must be detected during compilation, or at
least before execution, because a diagnostic is required.

int n = 0;
&a + n; /* ok */
n = 1;
&a + n; /* ok */
n = 100;
&a + n; /* UB */

If you want to make this kind of thing a constraint violation, the
compiler would need to distinguish between ``&a + n'' and ``&a + n''
depending on the current run-time value of n. So unless you want
to ban *all* pointer arithmetic on the address of a single object,
you can't make it a constraint violatoin.

Suppose you have a function that works on an array, taking as
arguments the address of the first element and the number of elements
(this is of course very common). Currently, it's perfectly valid
to call it with the address of a single object and a count of 1.

It's also not possible in general to determine whether a given pointer
value is the address of a single object or of an array element:

int n = whatever;

void func(int *p)
{
p + n; /* What does p point to? What is the value of n? */
}

int obj;
int arr[10];
func(&obj);
func(arr);

You can't make ``p + n'' a constraint violation for the first call
and not for the second. And though many optimizing compilers perform
dataflow analysis to determine where a particular value came from,
such analysis can't always be done, rigorously defining the cases
in which it can or must be done is very difficult, and there are
currently no rules in the C standard that require such analysis.

It's much easier to treat standalone objects as single-element arrays
than not to do so.

 

[Ben Bacarisse]

Forbid as CV (I was actually advocating even &a + 0 as CV).


UB, but not CV (I'd given something extremely similar as an example,
but it was snipped above).

OK, so people who want to use &a + 1 can do so by writing

(int *)(void *)&a + 1

or is the temporary pointer required?

Am suggesting that using the address of a single object (so long as
the implementation can definitively see it as such) in an expression
that does arithmetic with it be prohibited. I suppose one can shoot
holes, and so I am willing to refine this based on what y'all throw at
me.

What's the point? You just force people to use a complex method to get
the pointer they want.

 

[Anand Hariharan]

OK, so people who want to use &a + 1 can do so by writing

  (int *)(void *)&a + 1

or is the temporary pointer required?



What's the point?  You just force people to use a complex method to get
the pointer they want.

Now we are getting to what I have been ranting about viz., *WHY* would
anyone *WANT* that? Why was the new clause incorporated in the
standard to explicitly allow programmers do that? What is the merit
here?

NB: I understand it is the simpler choice here.

 

[Keith Thompson]

Now we are getting to what I have been ranting about viz., *WHY* would
anyone *WANT* that? Why was the new clause incorporated in the
standard to explicitly allow programmers do that? What is the merit
here?

NB: I understand it is the simpler choice here.

It's there to document and standardize existing practice.

C has never distinguished between a pointer to a single object and
a pointer to an object that happens to be an element of an array; an
object is an object. It would be impractically difficult to do so,
unless we introduced two sets of pointer types, one that points only
to array elements (and is therefore usable with pointer arithmetic)
and one that can point to any object and cannot be used with pointer
arithmetic. (The latter would be similar to the kind of pointers we
see in languages that don't support pointer arithmetic.)

Now that I think about it, a new kind of pointer that *only* points
to an object and cannot be used to compute pointers to nearby objects
(presumably members of the same array) is an interesting idea. If I
were designing a new C-like language from scratch, I might consider
making pointer types *not* subject to arithmetic by default. If you
want to perform pointer arithmetic, you need to add an "indexed"
keyword to the declaration. The address of a single object can
only be a non-indexed pointer (though you might be able to use a
cast to convert it to an indexed pointer).

But adding such a feature would be a radical change to the language,
breaking almost all existing code and requiring parts of the library
to be redesigned. It ain't gonna happen (and I'm certainly not
advocating it).

Not being able to perform pointer arithmetic on pointers to single
objects would not, by itself, be a great loss IMHO. But the language
changes that would be necessary to *enforce* such a restriction
would be far more expensive.

 

[Anand Hariharan]

(...) [Anand]

Am suggesting that using the address of a single object (so long as
the implementation can definitively see it as such) in an expression
that does arithmetic with it be prohibited.  I suppose one can shoot
holes, and so I am willing to refine this based on what y'all throw at
me.

[/Anand]

Now we are getting to what I have been ranting about viz., *WHY* would
anyone *WANT* that?  Why was the new clause incorporated in the
standard to explicitly allow programmers do that?  What is the merit
here?

NB: I understand it is the simpler choice here.

It's there to document and standardize existing practice.

C has never distinguished between a pointer to a single object and
a pointer to an object that happens to be an element of an array; an
object is an object.  It would be impractically difficult to do so,
unless we introduced two sets of pointer types, one that points only
to array elements (and is therefore usable with pointer arithmetic)
and one that can point to any object and cannot be used with pointer
arithmetic.  (The latter would be similar to the kind of pointers we
see in languages that don't support pointer arithmetic.)

Now that I think about it, a new kind of pointer that *only* points
to an object and cannot be used to compute pointers to nearby objects
(presumably members of the same array) is an interesting idea.  If I
were designing a new C-like language from scratch, I might consider
making pointer types *not* subject to arithmetic by default.  If you
want to perform pointer arithmetic, you need to add an "indexed"
keyword to the declaration.  The address of a single object can
only be a non-indexed pointer (though you might be able to use a
cast to convert it to an indexed pointer).

But adding such a feature would be a radical change to the language,
breaking almost all existing code and requiring parts of the library
to be redesigned.  It ain't gonna happen (and I'm certainly not
advocating it).

Not being able to perform pointer arithmetic on pointers to single
objects would not, by itself, be a great loss IMHO.  But the language
changes that would be necessary to *enforce* such a restriction
would be far more expensive.

You are over-thinking this. What I ask is not anything remotely as
expensive, definitely not meriting a new keyword or a significant
language change. In fact, as Ben showed in his post, what I propose
would be fairly easy to subvert (only requiring some additional
syntax), and I am not convinced that anyone would have a valid use-
case to subvert it.

Let me reproduce what I wrote earlier, this time also indicating what
I would like it to be:

int a;
int *p = &a;
extern int n;

p; /* Okay */
p + 1; /* Okay */
p + 100; /* UB, but not CV */
p + n; /* May or may not be UB */

&a; /* Okay */
&a + 0; /* Currently neither UB nor CV, but should be CV */
&a + 1; /* Currently neither UB nor CV, but should be CV */
&a + 100; /* Currently neither UB nor CV, but should be CV */
&a + n; /* May or may not be UB. Currently not CV, but should be CV
*/


What I am convinced about:
* That's how the language is.
* The language stays simple.

What I am not convinced yet [NB: In all the below statements,
prepositions such as 'it', 'this' etc refers to "doing pointer
arithmetic on a pointer value yielded by applying the unary & operator
on a single object"]:
* Why anyone would want to do this.
* Why ratify the language defintion by incorporating a new clause in
the standard that actually highlights a language loophole and pretty
much gives license to a programmer to do this.
* Why it is insurmountably difficult for an implementation to
identify this. Or impossible without changing the language in a
drastic or incompatible way?
* How requiring an implementation to issue a diagnostic when it
detects this would seriously impact existing code -- code that one
could argue is already broken.


thank you for listening,
- Anand Hariharan

 

[Keith Thompson]

You are over-thinking this. What I ask is not anything remotely as
expensive, definitely not meriting a new keyword or a significant
language change. In fact, as Ben showed in his post, what I propose
would be fairly easy to subvert (only requiring some additional
syntax), and I am not convinced that anyone would have a valid use-
case to subvert it.

Let me reproduce what I wrote earlier, this time also indicating what
I would like it to be:

int a;
int *p = &a;
extern int n;

p; /* Okay */
p + 1; /* Okay */
p + 100; /* UB, but not CV */
p + n; /* May or may not be UB */

Ok, so far that's the way it is now (as you know).

&a; /* Okay */
&a + 0; /* Currently neither UB nor CV, but should be CV */
&a + 1; /* Currently neither UB nor CV, but should be CV */
&a + 100; /* Currently neither UB nor CV, but should be CV */
&a + n; /* May or may not be UB. Currently not CV, but should be CV
*/

Let me try to state it a bit more precisely.

Constraint (proposed):

The operand of any arithmetic operation shall not be of the
form &obj, where obj is an identifier that is the name of
a declared object. (Presumably it should also apply to any
member of a struct or union.) Note: This affects operations
of the form pointer+integer, integer+pointer, pointer-integer,
and pointer-pointer.

What I am convinced about:
* That's how the language is.

I don't know what you mean by this. You explicitly acknowledged above
that this *isn't* how the language is ("Currently neither UB nor CV").
Can you clarify this point?

* The language stays simple.

But not quite as simple as it is now; it requires a new restriction to
be added to the existing language.

It also means that two expressions with exactly the same type and
value would be treated very differently: pointer arithmetic on ``&a''
is a constraint violation, but pointer arithmetic on ``p'' is ok.
That's not a fatal flaw, but I'm uncomfortable with the idea.
(Note that there's already a case of this: a constant 0 yields a
null pointer when converted to a pointer type, but a non-constant
expression of type int with the value 0 may or may not do so.
I'm not a big fan of that either, but we're firmly stuck with it.)

What I am not convinced yet [NB: In all the below statements,
prepositions such as 'it', 'this' etc refers to "doing pointer
arithmetic on a pointer value yielded by applying the unary & operator
on a single object"]:
* Why anyone would want to do this.

Suppose you have a function that takes two pointers, one to the first
element of an array on which it's to act and one just past the last
element of the same array. (Think C++ iterators.) To process an array:

some_type arr[N];
func(arr, arr+N);

To process a single object:

some_type obj;
func(&obj, &obj+1);

Why forbid this useful construct?

* Why ratify the language defintion by incorporating a new clause in
the standard that actually highlights a language loophole and pretty
much gives license to a programmer to do this.

Um, why not?

"Trust the programmer." -- C99 Rationale, page 3.

* Why it is insurmountably difficult for an implementation to
identify this. Or impossible without changing the language in a
drastic or incompatible way?

Ok, it's not terribly difficult to add a very limited check for this
kind of thing. But it's far too easy to work around the check.
If you could change the language in a way that would detect such
errors with some reliability, it would be worth considering.
But under your proposal, as soon as you copy an address into a
pointer variable, there's no trace of its origin and any "misuse"
is undetectable.

* How requiring an implementation to issue a diagnostic when it
detects this would seriously impact existing code -- code that one
could argue is already broken.

It would be interesting to look for examples of pointer arithmetic
on single object addresses in existing code, and determine how
many cases are deliberate and how many are unintentionally broken.
I have no idea what the results of such a survey might be.

 

[Keith Thompson]

What I am not convinced yet [NB: In all the below statements,
prepositions such as 'it', 'this' etc refers to "doing pointer
arithmetic on a pointer value yielded by applying the unary & operator
on a single object"]:
* Why anyone would want to do this.

Suppose you have a function that takes two pointers, one to the first
element of an array on which it's to act and one just past the last
element of the same array. (Think C++ iterators.) To process an array:

some_type arr[N];
func(arr, arr+N);

To process a single object:

some_type obj;
func(&obj, &obj+1);

Why forbid this useful construct?

* Why ratify the language defintion by incorporating a new clause in
the standard that actually highlights a language loophole and pretty
much gives license to a programmer to do this.

Um, why not?

"Trust the programmer." -- C99 Rationale, page 3.

[...]

To put it a bit more succinctly: The language has guaranteed,
at least since 1989, that single objects may be treated as
single-element arrays. Programmers are entitled to rely on that
guarantee.

 

[Anand Hariharan]

Ok, so far that's the way it is now (as you know).


Let me try to state it a bit more precisely.

Constraint (proposed):

The operand of any arithmetic operation shall not be of the
form &obj, where obj is an identifier that is the name of
a declared object.  (Presumably it should also apply to any
member of a struct or union.)  Note: This affects operations
of the form pointer+integer, integer+pointer, pointer-integer,
and pointer-pointer.

Couldn't have worded it better myself. Thank you, Keith.

I don't know what you mean by this.  You explicitly acknowledged above
that this *isn't* how the language is ("Currently neither UB nor CV").
Can you clarify this point?

Looks like I lost a sentence or two between my example code and the
"What I am and am not convinced about". Sorry for the confusion.

I was taking stock of the 'debate', trying to objectively summarise
both sides. So what I said under "What I am convinced about", and
when I said "That's how the language is" above, they were identical in
vein to your "Ok, so far that's the way it is now (as you know)".

But not quite as simple as it is now; it requires a new restriction to
be added to the existing language.

Please see my above clarification; I was trying to meet both sides by
saying that by leaving the language as-is, it stays simple.

It also means that two expressions with exactly the same type and
value would be treated very differently: pointer arithmetic on ``&a''
is a constraint violation, but pointer arithmetic on ``p'' is ok.
That's not a fatal flaw, but I'm uncomfortable with the idea.
(Note that there's already a case of this: a constant 0 yields a
null pointer when converted to a pointer type, but a non-constant
expression of type int with the value 0 may or may not do so.
I'm not a big fan of that either, but we're firmly stuck with it.)

Let me try and understand what you say above. Are you saying the
assert below will fail?

int i = 0;
assert( NULL == (void *)i );

What I am not convinced yet [NB: In all the below statements,
prepositions such as 'it', 'this' etc refers to "doing pointer
arithmetic on a pointer value yielded by applying the unary & operator
on a single object"]:
  * Why anyone would want to do this.

Suppose you have a function that takes two pointers, one to the first
element of an array on which it's to act and one just past the last
element of the same array.  (Think C++ iterators.)  To process an array:

    some_type arr[N];
    func(arr, arr+N);

To process a single object:

    some_type obj;
    func(&obj, &obj+1);

Why forbid this useful construct?

Agreed.

  * Why ratify the language defintion by incorporating a new clause in
the standard that actually highlights a language loophole and pretty
much gives license to a programmer to do this.

Um, why not?

"Trust the programmer." -- C99 Rationale, page 3.

Okay.

I'd also like to clarify that I didn't mean to insinuate that the
*purpose* of inserting the new clause was to highlight the loophole.
I was taken by surprise when I saw your example in

Ok, it's not terribly difficult to add a very limited check for this
kind of thing.  But it's far too easy to work around the check.
If you could change the language in a way that would detect such
errors with some reliability, it would be worth considering.
But under your proposal, as soon as you copy an address into a
pointer variable, there's no trace of its origin and any "misuse"
is undetectable.


It would be interesting to look for examples of pointer arithmetic
on single object addresses in existing code, and determine how
many cases are deliberate and how many are unintentionally broken.
I have no idea what the results of such a survey might be.

My takeaway was that it would not impact any code, but as you have
demonstrated, it certainly would widen the rift between C and C++ and/
or break C code that is reasonably idiomatic of C++.


thank you,
- Anand

 

[Seebs]

Let me try and understand what you say above. Are you saying the
assert below will fail?

int i = 0;
assert( NULL == (void *)i );

No.

He's saying it *MAY* fail. I believe it's implementation-defined how
integers are converted to pointers, and whether or not it happens
successfully...

-s

 

[Keith Thompson]

No.

He's saying it *MAY* fail. I believe it's implementation-defined how
integers are converted to pointers, and whether or not it happens
successfully...

Right.

The definition of a"null pointer constant" says that "integer constant
expression with the value 0", when converted to a pointer type, yields a
null pointer. This does not apply to non-constant integer expressions,
even with the same value; such conversions are indeed
implementation-defined.

See C99 6.3.2.3p3 and p5.

 

[Keith Thompson]

Suppose you have a function that takes two pointers, one to the first
element of an array on which it's to act and one just past the last
element of the same array.  (Think C++ iterators.)  To process an array:

    some_type arr[N];
    func(arr, arr+N);

To process a single object:

    some_type obj;
    func(&obj, &obj+1);

Why forbid this useful construct?
Agreed.

[...]
My takeaway was that it would not impact any code, but as you have
demonstrated, it certainly would widen the rift between C and C++ and/
or break C code that is reasonably idiomatic of C++.

I didn't mean to overemphasize the C++ aspect of this. The idea of
passing a pointer to just past the end of an array was inspired by
C++ iterators, but it's purely a C idea (though I don't think I've
seen it used very often). My problem with banning &obj+1 is that
it would wide the rift between C and C, not between C and C++.

 

[Twixer Xev]

On Jun 10, 5:09 pm, Keith Thompson<[email protected]> wrote:

[...]
I didn't mean to overemphasize the C++ aspect of this. The idea of
passing a pointer to just past the end of an array was inspired by
C++ iterators, but it's purely a C idea (though I don't think I've
seen it used very often). My problem with banning&obj+1 is that
it would wide the rift between C and C, not between C and C++.

The use of sentinel pointers (e.g. one offset past the end of an array,
or more generally, one offset past the last desired iteration element)
definitely predates c++ iterators. It was used commonly to optimize
certain tight loops, where loop counters were not referenced within
the loop body. This reduced the overhead from two adds/increments (loop
counter and pointer) to a single add/increment (pointer) per iteration,
with the loop condition being (pointer != sentinel).

That is the primary reason why this construct can never be removed from
the C language. The fact that programmers can abuse this special purpose
pointer, through dereferencing, is covered explicitly in the standard.
It is not a problem and therefore needs no solution.

 

[Keith Thompson]

On Jun 10, 5:09 pm, Keith Thompson<[email protected]> wrote:

[...]
I didn't mean to overemphasize the C++ aspect of this. The idea of
passing a pointer to just past the end of an array was inspired by
C++ iterators, but it's purely a C idea (though I don't think I've
seen it used very often). My problem with banning&obj+1 is that
it would wide the rift between C and C, not between C and C++.

The use of sentinel pointers (e.g. one offset past the end of an array,
or more generally, one offset past the last desired iteration element)
definitely predates c++ iterators. It was used commonly to optimize
certain tight loops, where loop counters were not referenced within
the loop body. This reduced the overhead from two adds/increments (loop
counter and pointer) to a single add/increment (pointer) per iteration,
with the loop condition being (pointer != sentinel).

That is the primary reason why this construct can never be removed from
the C language. The fact that programmers can abuse this special purpose
pointer, through dereferencing, is covered explicitly in the standard.
It is not a problem and therefore needs no solution.

To be clear, the suggestion (which wasn't mine) wasn't to forbid
computing a pointer one past the end of an array. It was to remove
the permission to treat a standalone object as single-element array
for purposes of pointer arithmetic. Such a change wouldn't remove
the ability to use sentinel pointers; it would only remove the
special case of using them on single objects.

 

[Twixer Xev]

On Jun 10, 5:09 pm, Keith Thompson<[email protected]> wrote:

[...]

To be clear, the suggestion (which wasn't mine) wasn't to forbid
computing a pointer one past the end of an array. It was to remove
the permission to treat a standalone object as single-element array
for purposes of pointer arithmetic. Such a change wouldn't remove
the ability to use sentinel pointers; it would only remove the
special case of using them on single objects.

I didn't mean to imply that it was your suggestion. Sorry if I came
across that way.

There are other problems with the suggestion that would break a lot
of legacy code (and turn the language into something noticeably
different). One that comes to mind has to do with the loose type system
that we enjoy in the C language, which leads to very efficient code
generation.

Consider the case where we have a single object and we pass its
address to a function. Let's go even further and assume that the
called function is outside the current translation unit. The compiler
has no way of distinguishing the "mode" of pointer we are passing to
the function (i.e. a single-object versus array "mode" pointer). The
only recourse would be to add a new qualifier so that the pointer
can be disambiguated outside the translation unit. A new qualifier
means rewriting the standard libraries to deal with a new case for
pointer arithmetic. This would by analogous to forcing all single-
object pointers to be like C++ references; this is a restriction that
most people would not accept in a language as versatile as C.

Casting between pointers to different types also becomes cumbersome
if such restrictions are in place. This one is also easy to reason
about, in terms of what it would do to the language.

 

[Keith Thompson]

On 06/10/2010 04:47 PM, Keith Thompson wrote:
[...]

To be clear, the suggestion (which wasn't mine) wasn't to forbid
computing a pointer one past the end of an array. It was to remove
the permission to treat a standalone object as single-element array
for purposes of pointer arithmetic. Such a change wouldn't remove
the ability to use sentinel pointers; it would only remove the
special case of using them on single objects.

I didn't mean to imply that it was your suggestion. Sorry if I came
across that way.

Don't worry, you didn't imply that; I was just trying to make
sure that *I* didn't imply it. (And only for reasons of proper
attribution.)

There are other problems with the suggestion that would break a lot
of legacy code (and turn the language into something noticeably
different). One that comes to mind has to do with the loose type system
that we enjoy in the C language, which leads to very efficient code
generation.

Consider the case where we have a single object and we pass its
address to a function.

The proposal only applied to &obj being the direct operand of "+" or
"-". Once you copy the pointer value to a pointer object, you can do
whatever arithmetic you like on it.

[snip]

 

[Twixer Xev]

On 06/11/2010 12:37 AM, Keith Thompson wrote:
[...]

The proposal only applied to&obj being the direct operand of "+" or
"-". Once you copy the pointer value to a pointer object, you can do
whatever arithmetic you like on it.

By precedence rules, &obj is already an rvalue pointer by the time that
arithmetic on that pointer is encountered. The only way that I can see
to implement the proposed constraint is to classify pointers as single-
object references or array pointers, which opens up the aforementioned
problems.

 

[Anand Hariharan]

On 06/11/2010 12:37 AM, Keith Thompson wrote:
[...]

The proposal only applied to&obj being the direct operand of "+" or
"-".  Once you copy the pointer value to a pointer object, you can do
whatever arithmetic you like on it.

By precedence rules, &obj is already an rvalue pointer by the time that
arithmetic on that pointer is encountered. The only way that I can see
to implement the proposed constraint is to classify pointers as single-
object references or array pointers, which opens up the aforementioned
problems.

No, that's not the only way. See Keith's formal wording/specification
of my proposed constraint in <[email protected]>

Anyway, a valid case has been made for &obj + 1, and the whole issue
is moot.

- Anand

 

[Richard Bos]

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.

One reason is that it makes it a lot easier to create generic functions
which can deal with arrays of all size, including 1. In many cases you
don't want to have to create a whole new array just to deal with a
single object. For example, a function

void invert_pixel_colours(struct *rgb_pixel, size_t num_pixels)

can deal with both

invert_pixel_colours(bitmap, width*height);

_and_

invert_pixel_colours(&contrast_colour, 1);

without you having to either write two functions, or use a hack like

{
struct rgb_pixel temp[1];
temp[0]=contrast_colour;
invert_pixel_colours(temp, 1);
contrast_colour=temp[0];
}

Richard