Making Fatal Hidden Assumptions

[Keith Thompson]

Why? It's not that difficult to define the behavior of a program that
"uses" such an address other than by dereferencing, and no problem to
leave the behavior undefined for dereferencing

The problem is pointer arithmetic. For example, given:

#define BUFFER_SIZE /* some big number */
int buf[BUFFER_SIZE];
int *ptr = buf + BUFFER_SIZE;
int offset = /* some number */

Requiring (ptr + offset - offset == ptr) probably wouldn't be too much
of a burden for most systems, but requiring (ptr + offset > ptr) could
cause problems. Given the current requirements, buf can be placed
anywhere in memory; there just (on some systems) needs to be a single
extra byte just past the end of the array. Requiring out-of-bounds
pointer arithmetic to work "correctly" in all cases could be much more
burdensome.

And avoiding creating invalid pointers really isn't all that
difficult.

 

[Andrew Reilly]

I thought we were talking about C.

We were. Sure, you can put a pointer into a register argument.

The point is that you can't take the address of a register state variable,
so you can't pass that "by reference" as a way to get multiple return
values out of a function.

Specifically;

double foo(double **pp)
{
double *p = *pp;
result = *p++;
if (result > 0.0) result += *p++;
*pp = p;
return result;
}

void bar(double info[], int N)
{
register double state = 0.0;
register double *p = info;
while (--N >= 0)
state -= foo(&p);
}

Doesn't work, because &p doesn't work.

Another way to make this sort of thing "nice" (as far as code
factorization goes) is either dynamic scoping or nested function
definitions. Then you could have:

void bar(double info[], int N)
{
register double state = 0.0;
register double *p = info;
double foo() {
double result = *p++;
if (result > 0.0) result += *p++;
return result;
}
while (--N >= 0)
state -= foo();
}

That puts more limitations on code structure: you may well want to build
a library of foo-like mutators, and use them in functions other than
bar(). Multiple return values would help with that, by making the state
mutation explicit.

Cheers,

 

[Keith Thompson]

We were. Sure, you can put a pointer into a register argument.

"void foo(int & x)" is a syntax error in C.

 

[Andrew Reilly]

But that would have locked out machines that strictly separate pointers
and non-pointers, in the sense that you can not load a pointer in a
non-pointer register and the other way around. Note also that on the
AS/400 a pointer is longer than any integer, so doing arithmetic on them
in integer registers would require quite a lot.

You don't have to do that at all. As you said, AS/400 uses long,
decorative pointers that are longer than integers. So no one's going
to notice if what your C compiler calls a pointer is actually a (base,
index) tuple, underneath. Being object/capability machines, these
tuples point to whole arrays, not just individual bytes or words. The
compilers could quite easily have managed all of C's pointer arithmetic as
actual arithmetic, using integers and indices, and only used or formed
real AS/400 pointers when the code did memory references (as base[index]).
There's no need for pointer arithmetic outside this model, against
different "base" pointers, so that's a straw-man argument.

Cheers,

 

[Andrew Reilly]

Why? It's not that difficult to define the behavior of a program that
"uses" such an address other than by dereferencing, and no problem to
leave the behavior undefined for dereferencing

The problem is pointer arithmetic. For example, given:

#define BUFFER_SIZE /* some big number */
int buf[BUFFER_SIZE];
int *ptr = buf + BUFFER_SIZE;
int offset = /* some number */

Requiring (ptr + offset - offset == ptr) probably wouldn't be too much
of a burden for most systems, but requiring (ptr + offset > ptr) could
cause problems.

This is a really lame argument, IMO.

Given that we're working with fixed-word-length machines, rather than
scheme's bignums, p + offset > p doesn't even necessarily hold for
integers, so why should it hold more rigerously for pointers? Wrap-around
or overflow is a fact of life for fixed-range machines. You just deal
with it. Don't go too close to the edge, or make damn sure you're
checking for it when you do.

Given the current requirements, buf can be placed
anywhere in memory; there just (on some systems) needs to be a single
extra byte just past the end of the array. Requiring out-of-bounds
pointer arithmetic to work "correctly" in all cases could be much more
burdensome.

Correctness depends on what you're trying to do. The one-byte-extra
argument doesn't help the fact that the flat memory model of C will still
"work OK" even if buf[BUFFER_SIZE-1] occupies the very last word in the
address space of the machine: there's no room for even that single byte
extra. Sure, in that instance, ptr = buf + BUFFER_SIZE will equal 0, and
your pointer comparison may break if you do it carelessly, but ptr[-1]
will still point to the last word in the array, and there are no dumb
restrictions against iterating backwards through the array, or forwards
with non-unit stride.

And avoiding creating invalid pointers really isn't all that difficult.

No, of course it isn't. Just use pointers as object handles, and do your
pointer arithmetic with integers. Whoopee: exactly the same syntax and
semantics as Pascal and Java. I wonder why we bothered with pointers in
the first place?

 

[Andrew Reilly]

"void foo(int & x)" is a syntax error in C.

I didn't use that syntax. I believe that Arthur was probably confused by
the use of the term "pass by reference", for which the C idiom is to pass
(by value) a pointer to the argument, which doesn't work if the argument
is a register variable.

Now: did you have a useful point to make?

 

[Arthur J. O'Dwyer]

I didn't use that syntax. I believe that Arthur was probably confused
by the use of the term "pass by reference"

Well, I certainly wasn't confused by it! As far as I could tell,
you hadn't been talking about C since several posts back --- in my post,
I quoted context referring to "multiple return values" and reference
parameters --- the latter present in C++ but not C, and the former
present in very few C-like languages.

In case you hadn't noticed, this thread has for a long time been
crossposted to two groups in which C++ is topical, and one group in
which its apparent subject (language design) is topical. If you guys
want to talk about standard C, why don't you do that, and forget all
about pass-by-reference, multiple return values, AS/400 machine code,
and whatever other topics this thread has drifted through on its way
here?

I've removed c.p and c.a.e from the crosspost list. Feel free to go
back to discussing standard C now.

-Arthur

 

[Andrew Reilly]

I've removed c.p and c.a.e from the crosspost list. Feel free to go
back to discussing standard C now.

Aah, well I'm only reading the thread in comp.arch.embedded.

Cheers,

 

[pemo]

CBFalconer wrote:

#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))

int xstrlen (const char *s) {
const char *p; /* 5 */
int d;

p = s - 1;
do {
p++; /* 10 */
if ((((int) p) & (SW - 1)) == 0) {
do {
d = *((int *) p);
p += SW;
} while (!hasNulByte (d)); /* 15 */
p -= SW;
}
} while (*p != 0);
return p - s;
} /* 20 */

Let us start with line 1! The constants appear to require that
sizeof(int) be 4, and that CHAR_BIT be precisely 8. I haven't
really looked too closely, and it is possible that the ~x term
allows for larger sizeof(int), but nothing allows for larger
CHAR_BIT. A further hidden assumption is that there are no trap
values in the representation of an int. Its functioning is
doubtful when sizeof(int) is less that 4. At the least it will
force promotion to long, which will seriously affect the speed.

This is an ingenious and speedy way of detecting a zero byte within
an int, provided the preconditions are met. There is nothing wrong
with it, PROVIDED we know when it is valid.

<snip>

Just incase it hasn't been mentioned [a rather long thread to check!], and
might be useful, Google has an interesting summary on finding a nul in a
word by one Scott Douglass - posted to c.l.c back in 1993.

"Here's the summary of the responses I got to my query asking for the
trick of finding a nul in a long word and other bit tricks."

http://tinyurl.com/m7uw9

 

[Michael Wojcik]

I must have missed the bit in the C Rationale where the committee
wrote, "We did this for the AS/400". They probably thought it was
obvious, since no other architecture could ever have the same
requirements and support C.

OK, define the behavior of all non-dereferencing accesses on
invalid pointers. Be sure to account for systems with non-linear
address spaces, since nothing else in the C standard excludes them.

Yup. The AS/400 has a set of opcodes for manipulating integers, and
a different set for manipulating pointers. Nothing in C currently
requires it to treat the latter like the former, and I don't see any
reason why it should. (Indeed, I admit to being mystified by Andrew
Reilly's position; what would be gained by requiring that C implemen-
tations have defined behavior for invalid pointers? How is leaving
invalid pointer access undefined by the standard "constraining" C?)

Surely there's some way to catch and ignore the trap from loading an
invalid pointer, though.

No, there is not. The "trap" (a machine check, actually) can be
caught, and it can be responded to, by application code; but ignoring
it is not one of the options. On the AS/400, only LIC (Licensed
Internal Code) can bypass memory protection, and the C implementation
is not LIC.

The AS/400 uses a Single-Level Store. It has *one* large virtual
address space for all user-mode objects in the system: all jobs (the
equivalent of processes), all files, all resources of whatever sort.
It enforces access restrictions not by giving each process its own
virtual address space, but by dynamically granting jobs access to
"materialized" subspaces. (This doesn't apply to processes running
under PACE, AIUI, but that's a special case.)

I mean, it stops _somewhere_ even as it is now,

Yes, it stops: if the machine check isn't handled by the application,
the job is paused and a message is sent to the appropriate message
queue, where a user or operator can respond to it.

That happens under LIC control. The C implementation can't override
it; if it could, it'd be violating the system's security model.

Of course, the C implementation could emulate some other machine with
less-vigilant pointer handling by generating some intermediate
representation and interpreting it at runtime. That would have made
the early AS/400s unusably slow, rather than just annoyingly slow,
for C programs.

But in any case a favorite maxim of comp.lang.c applies here: what
the AS/400, or any other extant implementation, does *does not
matter* to the C standard. If we decommissioned all AS/400s today,
there might be a new architecture tomorrow with some other good
reason for disallowing operations on invalid pointers in C.

--
Michael Wojcik (e-mail address removed)

The lecturer was detailing a proof on the blackboard. He started to say,
"From the above it is obvious that ...". Then he stepped back and thought
deeply for a while. Then he left the room. We waited. Five minutes
later he returned smiling and said, "Yes, it is obvious", and continued
to outline the proof. -- John O'Gorman

 

[Michael Wojcik]

You don't have to do that at all. As you said, AS/400 uses long,
decorative pointers that are longer than integers. So no one's going
to notice if what your C compiler calls a pointer is actually a (base,
index) tuple, underneath. Being object/capability machines, these
tuples point to whole arrays, not just individual bytes or words. The
compilers could quite easily have managed all of C's pointer arithmetic as
actual arithmetic, using integers and indices, and only used or formed
real AS/400 pointers when the code did memory references (as base[index]).

That would break inter-language calls, which were an absolute
necessity in early AS/400 C implementations (notably EPM C), as they
were unable to use some system facilities (such as communications)
directly.

Prior to the ILE environment, there was no "linker" as such for most
(all?) AS/400 application programming languages. Source files were
compiled into separate program objects (*PGM objects) in the
filesystem. Calls with external linkage were resolved dynamically.
(This is closer to the external-call model COBOL uses, actually, so
it made sense for the 400's primary audience.)

It would have been a real mess if the C implementation had to figure
out, on every external call passing a pointer, whether the target was
C (and so could use special fake C pointers) or not (and so needed
real AS/400 pointers). Putting this burden on the C programmer would
not have improved the situation.

And, of course, pointers in aggregate data types would pose a real
problem. If a C program wanted to define a struct that corresponded
to a COBOL group item, that would've been a right pain. Obviously,
it's an implementation-specific task anyway, but on most implementa-
tions it's pretty straightforward provided the COBOL item doesn't use
any of COBOL's oddball data types.

That doesn't mean it couldn't have been done, of course, but it would
have made C - already not a member of the popular crowd on the '400
playground - too cumbersome for all but the most determined fans.

As the Rationale notes, one of the guiding principles behind C is to
do things the way the machine wants to do them. That introduces many
incompatibilities between implementations, but has rewards of its own.
Since C is rather unusual among HLLs in this respect, why not let it
stick to its guns rather than asking it to ape all those other
languages by hiding the machine behind its own set-dressing?

 

[Jordan Abel]

I must have missed the bit in the C Rationale where the committee
wrote, "We did this for the AS/400". They probably thought it was
obvious, since no other architecture could ever have the same
requirements and support C.


OK, define the behavior of all non-dereferencing accesses on invalid
pointers. Be sure to account for systems with non-linear address
spaces, since nothing else in the C standard excludes them.

unspecified result, implementation-defined, compares equal, unspecified
result, unspecified result.

There, that was easy.

Yup. The AS/400 has a set of opcodes for manipulating integers, and a
different set for manipulating pointers. Nothing in C currently
requires it to treat the latter like the former, and I don't see any
reason why it should. (Indeed, I admit to being mystified by Andrew
Reilly's position; what would be gained by requiring that C implemen-
tations have defined behavior for invalid pointers? How is leaving
invalid pointer access undefined by the standard "constraining" C?)

It constrains code, in a way. Existing code is more important than
existing implementations, right?

No, there is not. The "trap" (a machine check, actually) can be
caught, and it can be responded to, by application code; but ignoring
it is not one of the options.

You can't "catch it and do nothing"? What are you expected to _do_ about
an invalid or protected address being loaded [not dereferenced], anyway?
What _can_ you do, having caught the machine check? What responses are
typical?

On the AS/400, only LIC (Licensed Internal Code) can bypass memory
protection, and the C implementation is not LIC.

The AS/400 uses a Single-Level Store. It has *one* large virtual
address space for all user-mode objects in the system: all jobs (the
equivalent of processes), all files, all resources of whatever sort.
It enforces access restrictions not by giving each process its own
virtual address space, but by dynamically granting jobs access to
"materialized" subspaces. (This doesn't apply to processes running
under PACE, AIUI, but that's a special case.)

And why is anything but a dereference an "access" to the protected
address?

Yes, it stops: if the machine check isn't handled by the application,

What can the application do in the handler? Why couldn't a C
implementation cause all C programs to have a handler that does
something reasonable?

the job is paused and a message is sent to the appropriate message
queue, where a user or operator can respond to it.

That happens under LIC control. The C implementation can't override
it; if it could, it'd be violating the system's security model.

I didn't say override. I said ignore. Since it's not a dereference, no
harm actually done. Why does loading a protected address into a register
violate security?

 

[Dik T. Winter]

> > No, there is not. The "trap" (a machine check, actually) can be
> > caught, and it can be responded to, by application code; but ignoring
> > it is not one of the options.

>
> You can't "catch it and do nothing"? What are you expected to _do_ about
> an invalid or protected address being loaded [not dereferenced], anyway?
> What _can_ you do, having caught the machine check? What responses are
> typical?

Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what
is p after that line of code? Nothing useful, because nothing was
assigned to it. Well, the second line also traps, but what is the
sense in doing nothing here? If you do nothing p is still just as
undefined as before that line.

 

[Andrew Reilly]

Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

How about:

int a[10];
foo(a + 1);

where

foo(int *p)
{
p -= 1;
/* do something with p[0]..p[9] */
}

The first line of code traps, you want to ignore that trap, so what
is p after that line of code? Nothing useful, because nothing was
assigned to it. Well, the second line also traps, but what is the
sense in doing nothing here? If you do nothing p is still just as
undefined as before that line.

Does p -= 1 still trap, in the first line of foo, given the way that it's
called in the main routine?

If not, how could foo() be compiled in a separate unit, in the AS/400
scenario that you described earlier?

If it does trap, why? It's not forming an "illegal" pointer, even for the
AS/400 world.

If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?

What if my algorithm's natural expression is to refer to p[0]..p[-9], and
expects to be handed a pointer to the last element of a[]?

The significant difference of C, to other languages (besides the
assembly language of most architectures) is that you can form, store, and
use as arguments pointers into the middle of "objects". Given that
difference, the memory model is obvious, and the constraint imposed by the
"undefined" elements of the standard (laboured in this thread)
unreasonably onerous. IMO. YMMV.

Cheers,

 

[Dik T. Winter]

> On Thu, 23 Mar 2006 12:33:51 +0000, Dik T. Winter wrote: ....
> How about:
> int a[10];
> foo(a + 1);
> where
>
> foo(int *p)
> {
> p -= 1;
> /* do something with p[0]..p[9] */
> } ....
> Does p -= 1 still trap, in the first line of foo, given the way that it's
> called in the main routine?

Why should it?

> If not, how could foo() be compiled in a separate unit, in the AS/400
> scenario that you described earlier?

It was not me who described it, but I see no reason why that should be
impossible. Consider a pointer as a combination of the indication of a
region and an index into that region.

> If it does trap, why? It's not forming an "illegal" pointer, even for the
> AS/400 world.

It does not trap.

> If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?

Because the latter creates an invalid pointer.

> What if my algorithm's natural expression is to refer to p[0]..p[-9], and
> expects to be handed a pointer to the last element of a[]?

No problem.

> The significant difference of C, to other languages (besides the
> assembly language of most architectures) is that you can form, store, and
> use as arguments pointers into the middle of "objects".

That was also possible in Algol 68. But I see no problem with it on
a machine like the AS/400.

(As an example from Algol 68:
'int' a[1:10, 1:10, 1:10];
'ref' 'int' aa = a[2:6, 3:7,4];
the latter points to a two-dimensional slice...)

 

[Jordan Abel]

No, there is not. The "trap" (a machine check, actually) can be
caught, and it can be responded to, by application code; but ignoring
it is not one of the options.

You can't "catch it and do nothing"? What are you expected to _do_ about
an invalid or protected address being loaded [not dereferenced], anyway?
What _can_ you do, having caught the machine check? What responses are
typical?

Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what is
p after that line of code? Nothing useful, because nothing was
assigned to it.

Why not?

I guess my point is, why are you not allowed to hold an address in a
register regardless of whether you would be allowed to access the memory
at that address? That seems like a stupid architecture in the first
place. It's not "security", it's bad design masquerading as security. If
the goal is to protect an area of memory from being accessed, block
programs from _accessing_ it, not from talking about it.

Well, the second line also traps, but what is the sense in doing
nothing here? If you do nothing p is still just as undefined as
before that line.

Only under the current standard. Using the fact that it's undefined to
justify it being undefined is begging the question.

 

[Keith Thompson]

Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what is
p after that line of code? Nothing useful, because nothing was
assigned to it.

Why not?

Because the trap occurred before the value was assigned to p.

I guess my point is, why are you not allowed to hold an address in a
register regardless of whether you would be allowed to access the memory
at that address?

Because it catches errors as early as possible.

Why do you want to create an address that you're not allowed to
dereference?

That seems like a stupid architecture in the first
place. It's not "security", it's bad design masquerading as security. If
the goal is to protect an area of memory from being accessed, block
programs from _accessing_ it, not from talking about it.

Presumably it does both.

The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think
the AS/400 architecture is stupid, that's your privilege. If you want
to write code that creates addresses outside the bounds of an array,
nobody is going to stop you; you'll just have to look somewhere other
than the C standard for guarantees that your code will behave the way
you want it to.

Your argument, I suppose, is that the C standard *should* guarantee
the behavior. That may or may not be a good idea -- but I think we
can guarantee that nothing is going to change until and unless someone
comes up with a concrete proposal. I'm not going to do it myself,
because I'm satisfied with the standard as it is (at least in this
area). If you do so, you can expect a great deal of argument about
what behavior should be guaranteed and what should be left
implementation-defined (or even undefined).

 

[Andrew Reilly]

Because it catches errors as early as possible.

No, it doesn't. It breaks idioms where no error or illegal access would
occur.

Why do you want to create an address that you're not allowed to
dereference?

Because the ability to do so is implied by the syntax of pointer
arithmetic.

This restriction (undefined semantics IS a restriction) makes
pointer-walking versions of algorithms second-class citizens to otherwize
equivalent indexed versions of algorithms.

void
foo(int *p, int n)
{
for (; --n >= 0
p[n] = n;
}

is "legal" and "defined" on all architectures, but the equivalent with a
pointer cursor isn't:

void
foo(int *p, int n)
{
p += n-1;
for (; --n >= 0
*p-- = n;
}

I suppose that this is the root of my surprise and annoyance on
discovering what the standard says. These versions *should* be
equivalent, and equivalently well-defined.

The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think the
AS/400 architecture is stupid, that's your privilege. If you want to
write code that creates addresses outside the bounds of an array, nobody
is going to stop you; you'll just have to look somewhere other than the
C standard for guarantees that your code will behave the way you want it
to.

Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?

Your argument, I suppose, is that the C standard *should* guarantee the
behavior. That may or may not be a good idea -- but I think we can
guarantee that nothing is going to change until and unless someone comes
up with a concrete proposal. I'm not going to do it myself, because I'm
satisfied with the standard as it is (at least in this area). If you do
so, you can expect a great deal of argument about what behavior should
be guaranteed and what should be left implementation-defined (or even
undefined).

Yeah, but I expect most of that argument to go away, as all of the AS/400
wanna-be C coders drift off to use Java or .NET instead, leaving C a niche
language, doing the low-level systems programming that it was designed for.

 

[Andrew Reilly]

int a[10];
foo(a + 1);
where

foo(int *p)
{
p -= 1;
/* do something with p[0]..p[9] */
} ...
Does p -= 1 still trap, in the first line of foo, given the way that it's
called in the main routine?

Why should it?

It shouldn't. But if the comment (and the code) went off to do somthing
with p[1]..p[10], and the main line passed a, rather than a+1, you're
saying that it would trap. The coder, therefore, can't use a perfectly
reasonalble idiom (base shifting), even though the syntax, and the
semantics implied by that syntax, allow it.

It was not me who described it, but I see no reason why that should be
impossible. Consider a pointer as a combination of the indication of a
region and an index into that region.

I *was* considering a pointer as a combination of the indication of a
region and an index into that region. In C, that index is a *signed*
integer. If the hardware has a problem with that, and causes a trap if
the index component is set to a negative value, then the implementation
should go to some lengths to preserve the impression that it works anyway.

It does not trap.

But the author of the foo() function (as modified above) can't know that.

Because the latter creates an invalid pointer.

But the author of foo() can't know that. This argument started because it
was pointed out that p -= 1 produced undefined behaviour. It is clear
that the behaviour *could* be very well defined. That it isn't is the
root of the discussion.

What if my algorithm's natural expression is to refer to p[0]..p[-9],
and expects to be handed a pointer to the last element of a[]?

No problem.

It is a problem if those elements are accessed with a walking pointer,
rather than with an array index; something that the syntax of C and
most of it's idioms and historical code implies are equivalent.

 

[Keith Thompson]

No, it doesn't. It breaks idioms where no error or illegal access would
occur.


Because the ability to do so is implied by the syntax of pointer
arithmetic.

No, it's not implied by the syntax, any more than the ability to
compute MAX_INT + 1 is implied by the syntax of addition.

[snip]

Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?

Sure, go ahead.