Stefan Monnier said:
But such a representation of pointers is unnecessarily costly for the usual
case of a pointer to a single object. Some C compilers use such tricks to
get a "safe" implementation, but the runtime cost is very significant
(we're talking more than a factor 2 slowdown).
Pointers which are run-time distinguished from integers, and which
contain bounds information are essential to computers and languages
that are secure. We've known this for decades, and the ideas have
been tested thoroughly in implementations such as the lisp machine.
A more recent idea is the inclusion of small floating point length
descriptors within the pointer itself. The idea is that every pointer
contain, in addition to a full-address location in memory, a sixteen
bit or so origin and length descriptor. For example, such a
descriptor could consist of three fields, a block-size field (exponent
of the length), a count of the number of blocks in the object
(mantissa of the length) and a finger field (mechanism for identifying
the origin of the object in units of blocks).
With such a scheme, we can represent block-size aligned data
structures with high efficiency of memory use (1.5% wasted memory
space), guarantee that no references take place outside the object,
allow pointer arithmetic within the object, and do fine grained
allocation at the word level for objects less than 32 words.
Here's what an object identifier and pointer to a sub-word of the
object look like:
6 5 5 42-64 bits
******|*****|*****|******** ---- *******************
E B F pointer within object
Let C = the pointer field zeroing the bottom E+1 bits
This tells you that the object is of size B x 2**E words
That the object is word aligned on memory boundaries of size 2**E
That the beginning of the object is at location C - F x 2**E
That the end of the object is at location C - (B - F) x 2**E
In my opinion, schemes such as this combine the best of flat address
space and object bounds checking.
