Re: Ancient history

Nick Maclaren wrote:

> In article <fZCdnctIVOMw0zbfRVn-uw@comcast.com>,
> glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

>>Nick Maclaren wrote:

>>>All of that is true, and I have similar experiences, but the issue
>>>here IS the abstraction. C's model of arrays and areas of data
>>>is precisely that of a pointer to the start - with no length
>>>included or includable.

>>I always thought it was possible to do in C, but there doesn't seem
>>much interest in actually doing it. If a pointer holds origin, current
>>offset, and length then it is possible to do bounds checking even with
>>pointer arithmetic.

> No. As I have posted before, it ISN'T possible in C, for reasons I
> explain in my Objects diatribe. There is more than is in that
> document, too, including C99's introduction of intptr_t, but that
> gives a good start.

I haven't looked into C99 that much yet, so I won't say anything
about that.

> The best that is possible in C is the following:

> A reference is checked that it refers to a correctly aligned
> segment of memory wholly contained within a single allocation
> (i.e. a definition, result of malloc etc.)

> A pointer value that is operated on using only the pointer
> operations defined in the standard (i.e. not intptr_t or any
> of the numerous permitted extensions) does not change a pointer
> into one allocation into a pointer into another.

Yes, that is what I assume.

I am mostly considering programming errors, that is, accidents.
It should also catch buffer overflow problems, assuming, as you
say, that standard operations are used.

> You CANNOT block overflows from one subsection of an allocation
> into another, in general, without changing the standard drastically.

I think I agree with this, too. The system sees allocation, not
suballocation. If the programmer want something else, it has to
be allocated that way.

> Equally badly, where languages like Fortran 77 can have reliable
> bounds checking for a small, constant overhead per reference,
> the situation in C is such that the overhead is generally log(N)
> with a larger constant, where N is the number of non-definition
> allocations (often a million plus). Ouch.

For Fortran 77, and much of later Fortran versions, I believe you
can only check going outside an actual array, not that some subscripts
are out of bounds. It is still legal, for example, to pass a two
dimensional array to a subroutine with a one dimensional dummy argument.
It is also legal to pass an array element to a subroutine with an array
dummy and access the elements of the array after that element.

> Oh, and hardware support wouldn't help, unless it was designed entirely
> for C's bizarre rules - which changed quite radically between K&R C,
> C89 and C99. Think pointer validity and weep.

Other than speed, I was pretty happy with segment selectors in
the x86 architecture. Even the 64K segment size didn't bother me
all that much. With a big segment descriptor cache it could even
have been fast.

>>I was interested in the possibility of a C compiler targeting JVM,
>>which has those restrictions. There are some additional complications
>>regarding struct and union, but for a large fraction of C code it should
>>be possible.

> It depends how you define "a large fraction". In particular, it
> doesn't include any program that uses any form of the X Windowing
> System, or any program which includes a fancy memory management
> system or "dump/restore" system.

I think I define it by number of programs, not weighted by size.

>>>It is possible to build an abstraction on top of that which includes
>>>both the pointer and its size, but that is a separate model. Many
>>>of the more robust C programs do precisely that - which is precisely
>>>using C as a semi-portable assembler, as it was designed for.

(snip)

-- glen
Received on Thu Sep 29 21:43:26 2005