Re: Ancient history

From: glen herrmannsfeldt (gah_at_ugcs.caltech.edu)
Date: 06/13/05 

Date: Sun, 12 Jun 2005 23:40:14 -0700

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

Relevant Pages

  • Re: allocating memory for array of pointers to char
    ... >> checking up on allocation and so on, the types of your objects are ... > pointer inside a linked-list element. ... > typedef struct listelem_t { ... "value" is a pointer to an array of unknown length. ...
    (comp.lang.c)
  • Re: Newbie on the lose.. How to add an unknown length dataset to an array
    ... allocation, it does require enough virtual memory to hold twice the ... consisting of one of these records plus a pointer. ... Having read all the data into the list, I know the size of the array ... and your pointer method makes good sense from since it dosen't ...
    (comp.lang.fortran)
  • Re: Newbie on the lose.. How to add an unknown length dataset to an array
    ... allocation than with the reallocation approach. ... when I'm reading data of unknown size into an array, ... consisting of one of these records plus a pointer. ...
    (comp.lang.fortran)
  • Re: allocating space for Node**
    ... you should avoid this style of allocation. ... >my image is pointed to by "source" pointer, to allocate space for the table i ... CArray is a bit clumsy for 2D arrays because there's a problem with assignment ... Given you haven't constructed the array elements, ...
    (microsoft.public.vc.mfc)
  • Re: contiguity of arrays
    ... >> crosses segment boundaries. ... >> known to point to elements of that array can use ... standard decided to define the validity of pointer math in terms of the ...
    (comp.lang.c)
Quantcast