Re: support array bounds checking

[Greg McGary <gkm at eng dot ascend dot com>]

Per Bothner <bothner@pacbell.net> writes:

> Greg McGary <gkm@eng.ascend.com> writes:
> 
> > I know that you (Per) have a prejudice against fat pointers, but they
> > are the only approach that ensures reasonable performance.
> 
> Somehow I find this hard to believe.  I don't see how Pure
> could be using "fat pointers", hence they must be using some
> variant of thin pointers.  Pure has gotten rich by bounds-checking
> using thin pointers;  ergo thin pointers can be useful in the
> real world.

Some background is needed so we can be sure we're talking about the
same thing.  Purify checks that memory references are to valid
addresses, and that data is initialized before being read.  Purify
will not detect if a pointer intended for one data structure reads
from an unrelated data structure.  Purify won't catch a wild pointer
reference, as long as that reference happens to be to some valid
address.

Bounded pointers check that all pointer references (and by extension,
array references) occur within the object to which the pointer was
originally seated.  This is much finer grain of checking than done by
Purify.  E.g., a couple years ago, bounded pointers in gcc-2.7.2
caught a bug in GNU tr where a pointer walked off the front of an
array, and this was after tr had been tested with Purify many times.

I think that purify-style memory checking as implemented by Checker
and -fcheck-memory-usage complements bounded pointer checks nicely,
since they each catch different kinds of bugs.  Bounded pointers alone
won't catch references through dangling pointers.  Purify-style checks
won't catch cases where a pointer to one data-structure bleeds into
another.  Does purify put small invalid-data bumpers around data
structures?  If so, that that will only catch incremental overruns.
Also, Purify can't insert such bumpers in structs without altering
layout, nor can it easily manage its valid-memory bits in such a case.

Here's something that BPs will catch, but Purify won't:

	struct foo {
	    int a[3];
	    int b;
	};

	void
	bar (struct foo *foop)
	{
	    return foop->a[3];
	}

> The key discriminator between thin-pointer and fat-pointer approaches
> is not parameters and function results, since we can compile functions
> to have dual entry points, using a smart linker.   The real issue is
> whether pointer fields in structures are fat or thin.  Likewise, if
> the elements of pointer arrays are thin or fat.  In the approach I
> advocate, fields use thin pointers.  In your approach, fields
> use fat pointers.  This breaks binary compatibility, which makes
> it too much of a hassle to use, hence "real-world bounds violations 
> will not be caught."

If the data structure is manipulated only by functions that are
fat-pointer aware, why cripple the program by forcing thin pointers in
data structures everywhere?  IMO, your fears about binary
compatibility with BPs are exaggerated, though surely valid in
pathological cases.  A couple years ago, I built two X11 applications
where all the app code had BPs while libc and the
X libs did not.  In practice, I had no trouble mixing them.  Whether
pointers within aggregates can be fat or are forced to be thin should
at least be an option.

Greg