oops, corrupted memory again!

[J. Eric Roskos]

> >Now, if only somebody would invent an architecture where all objects,
> >including dynamicly allocated objects, are isolated in memory, then any
> >subscript error would cause an immediate memory fault.
>
>    If I'm not mistaken, this was done on the iAPX432, using a capability-
> based addressing scheme.  Dimmed the lights.  You could probably construct
> such an environment on the 80286, but no one does, probably for efficiency
> reasons.

One problem with the 432's approach was that it was very extreme; I don't
think it's good to say "the 432 tried these approaches and it was too slow,
therefore the checking can't be efficiently implemented."

I posted some comments in here (net.arch) about a week ago on apparently
the same subject, but nobody replied in net.arch to it (although I got a
couple of replies by mail).  Of the people who replied by mail, one (whose
technical knowledge I have a high opinion of) pointed out that C compilers
exist where subscript/pointer checking is done in software, and that thus
it would seem likely that similar checking could be done in hardware.

The way you could do it (which was a point the 2 people replying seemed to
agree upon) was that, associated with all pointers, you should have a
"minimum address" and "maximum address" for the object being pointed to.
Bear in mind that in C array names are just constant pointers, so
constructs like a[i] can use this method as well as plain pointer
references such as *p.  If p is a pointer of type t, then to use p you
will have to first assign it a value by referencing an existing object, or
by creating a new one:

	typedef <whatever> t;
	t  a[100];
	t  *p;

	p = a;                  (1)
	p = &a[40];             (2)
	p = (t *)malloc(300);   (3)

In case 1 and 2, you can easily set p.base to &a[0], and p.bound to
&a[99], and set p.pointer to &a for (1) and to &a[40].  So p then carries
around with it the range of valid addresses it can point to.  (Note that
nothing says anything about what a pointer in C has to look like, so
p can easily be a 3-word struct-like object, and if you were building a
new machine to support such things, you could make the machine have
3-word address registers).

In case 3, you could have malloc set the base and bound -- though if
malloc is written in C then you'd have to provide some way to reference
the base and bound fields from within the language -- so things like
malloc would also work.  I had originally thought that some
counterexamples existed, but one of the respondants (John Gilmore) pointed
out that really the counterexamples involved essentially semantically
inconsistent uses of the pointers (e.g., having 2 pointers around and
changing the bounds on 1 of them).

In any case, if you change p, e.g. p++, then you'd change what I called
p.pointer above, and leave p.base and p.bound alone.  If you generated an
effective address which was outside [p.base .. p.bound], then you'd
generate an addressing fault.

I don't think this checking would be that slow, although on a machine with
a narrow bus (especially those like the 8088 where you are already
fetching pointers through multiple bus cycles) fetching the range
attributes of the pointer would increase the bus time by a factor of 3.
It would also reduce the number of register variables you could have, if
you kept the bounds in registers also -- I think it would work best if you
had a machine that had registers set aside specifically for pointer
checking.  On a machine such as the 3280*, which does quadword reads from
memory because the data bus is very wide, the bus overhead would be much
less.  So the checking by this method would probably not be that bad
(certainly not as bad as the 432, which I believe had to sometimes fetch
several descriptor objects in order to validate references) at least on
larger machines (and after all, microprocessors are getting larger all the
time in terms of width of the bus, etc.).

-----
*I cite this machine because I'm more familiar with it; I suspect probably
 other machines like Vaxes have similarly wide buses.
-- 
E. Roskos