Re: bounds checking

Re: bounds checking

[Jeffrey A Law]

  In message <34d325a50.5f8@htbrug.net.HCC.nl>you write:
  > Hello Jeff,
  > 
  > Richard Jones and I want to integrate the bounds-checking patch into the
  > official gcc release. I did sent an assignment papers to Richard Stallman.
  > Richard Jones did not but will do this soon.
  > The bounds-checking patch lets you include runtime check's into the code.
  > These checks work on pointers and array indices. I have include the patch
  > to the extend.texi file. This will explain in much more detail the patch.
  > 
  > What do we have to do next to include this patch into the official release?
It would be interesting to know how your work differs from Greg's
since he's done a bounded pointer implementation.

If they don't overlap in functionality, then we can/should consider
the patches separately.

If they do overlap, then we'll need to evaluate both and select
one for inclusion.  

I'm going to try and read both specs in the next few days, but your
input would be greatly appreciated -- you two know more about these
things than I do :-)

I believe Gary's specs were posted to egcs recently.  Herman, can
you post yours to egcs too?

jeff

Re: bounds checking

[Greg McGary]

Jeffrey A Law <law@hurl.cygnus.com> writes:

> Haj.Ten.Brugge@net.HCC.nl (Herman ten Brugge) writes:
> > Richard Jones and I want to integrate the bounds-checking patch into the
> > official gcc release.

> It would be interesting to know how your work differs from Greg's
> since he's done a bounded pointer implementation.
> 
> If they don't overlap in functionality, then we can/should consider
> the patches separately.
> 
> If they do overlap, then we'll need to evaluate both and select
> one for inclusion.  

FYI, in the conclusion of Richard W.M. Jones's (RWMJ) report on his
bounds-checking work, he speculated about alternative bounds checking
implementations, and suggested that bounded pointers would perform
best of all--that's what initially inspired me to pursue BPs in gcc.
None of the problems with BPs that RWMJ cited in his report turned out
to be significant:

1) GCC likes pointers to fit into registers:
   Multi-word BPs are handled in a way analogous to complex numbers.
   The three words of a BP can be assigned to registers independently.	

2) The size of static objects is not always known at compile time:
   GCC generates references to the extent of a variable as foo.extent.
   GCC generates definitions of foo.extent at the time it
   compiles foo, or if foo is in an unchecked library, ld (or collect)
   can synthesize the foo.extent symbol.

3) These pointers are incompatible with code compiled by other compilers ...
   and with code compiled by GCC with bounds checking switched off:
   BPs can be selectively disabled for declarations that represent
   unchecked code.  BPs have their bounds automatically stripped when
   passed as an unchecked function arg, or assigned to an unchecked
   pointer variable.

Here are the differences between BPs and RWMJ's gcc-2.7.2 based
implementation, as of a year and a half ago.  (I don't know what new
work RWMJ might have done since then):

* BPs only check prior to pointer dereference & array reference;
  RWMJ's stuff checks pointer deref, array ref, as well as all pointer
  and array index arithmetic.

  Since BPs always know the bounds of their referent object and never
  need to do a table lookup, checking at dereference time is
  sufficient.  Checking arithmetic is unnecessary.

* BPs change the size of pointers to occupy three-words (value base &
  extent), so all information needed to check a pointer travels with
  the pointer so object descriptor tables need never be used.

  RWJM's pointers are of conventional size, however in order to check
  arithmetic, the pointer must be resolved to an object descriptor,
  requiring a table lookup.  While more efficient, BPs can impact
  external interfaces when pointer sizes don't agree, though there are
  work-abounds for that situation.

* BPs offer the finest grained checking.  As I recall, RWMJ's pointers
  are only guaranteed to remain within the outermost object.  E.g., if
  you have a structure that contains an array member, a single
  object-table entry describes the whole structure, so you couldn't
  tell if an access to the array member walked off the end into
  neighboring structure members, so long as it remained within the
  structure.

* BPs are implemented in both the C and C++ front-ends.  So far,
  RWMJ's stuff is only implemented in the C front-end, though it could
  work just as well in C++.

* BPs are much more runtime efficient, since no object descriptor
  table lookups are required.  Efficiency is unimportant for some
  applications but vital for others, in particular for embedded
  systems.  Speed is also important for long-running applications
  where the bugs only show up after significant run time.

Per Bothner has recently suggested a hybrid implementation where BPs
(what he calls "fat pointers") are used internally, but thin pointers
are used for all external interfaces, requiring that descriptors be
looked-up when a pointer crosses the boundary from unchecked into
checked code.  I still favor pure BPs, since I have found the problems
of pointer size to be minimal for code of reasonably good quality
(i.e., bad code is that which assumes (sizeof (void*) == sizeof (int)),
or contains many pointer/integer casts.  When faced with bad code, I
find it is a good opportunity to fix those flaws as a prerequisite for
running BPs, but not everyone who wishes to use bounds-checking will
have the freedom to fix such programs), and the problems of mixing BP
and non BP code to be solvable.

I have been working with Ulrich Drepper to create a BP GNU C library.
Despite the differences in pointer sizes, it has been my experience
that BPs can mix with unchecked libraries, provided that GCC is told
that the library's declarations should be considered to have unbounded
pointers.  There are several ways to accomplish this--see the spec for
details.

I think that about covers it from my perspective.  I'll chime in again
if I think of anything else.  Herman & Richard should correct me if I
have misrepresented or underrepresented their work in any way.

Greg

Re: bounds checking

[Joe Buck]

> 1) GCC likes pointers to fit into registers:
>    Multi-word BPs are handled in a way analogous to complex numbers.
>    The three words of a BP can be assigned to registers independently.	

I'm not crazy about the idea of adding one magic type at a time that is
handled like complex numbers.  It would be preferable to just handle all
structs like complex numbers (C++ performance would then immediately
greatly improve).  If this is done, multi-field bounded pointers are
just a special case.  This is a big change, but is it really harder than
doing all the equivalent work, but only using it for certain special
types (complex and BP's)?

Re: bounds checking

[Toon Moene]

Joe Buck wrote:

>  I'm not crazy about the idea of adding one magic type at
>  a time that is handled like complex numbers.  It would
>  be preferable to just handle all structs like complex
>  numbers (C++ performance would then immediately greatly
>  improve).  If this is done, multi-field bounded pointers
>  are just a special case.  This is a big change, but is
>  it really harder than doing all the equivalent work, but
>  only using it for certain special types (complex and
>  BP's)?

Can I second this ?  In the mean time, doing this in a general  
fashion might track down why COMPLEX doesn't work on some  
architectures ...

A large minority of Fortran users is heavily punished (in run-time  
performance) because g77 has to revert to its own break-down of  
complex arithmetic because the backend's cannot be trusted.

(see http://www.cygnus.com/ml/egcs-bugs/1998-Apr/0245.html for an  
example).

Cheers,
Toon.

Re: bounds checking

[Greg McGary]

Toon Moene <toon@moene.indiv.nluug.nl> writes:

> Joe Buck wrote:
> >  I'm not crazy about the idea of adding one magic type at
> >  a time that is handled like complex numbers.  It would
> >  be preferable to just handle all structs like complex
> >  numbers (C++ performance would then immediately greatly
> >  improve).  If this is done, multi-field bounded pointers
> >  are just a special case.  This is a big change, but is
> >  it really harder than doing all the equivalent work, but
> >  only using it for certain special types (complex and
> >  BP's)?
> 
> Can I second this ?  In the mean time, doing this in a general  
> fashion might track down why COMPLEX doesn't work on some  
> architectures ...

I'll even third it!  I'm always in favor of general extensible
mechanisms.  How about a new variety of CONCAT that stores the number
of elements in XEXP (x, 0)?  The mode would still allow you to
distinguish complex/BP/whatever.

Re: Bounds checking

[Greg McGary]

Tristan Gingold <tgi@netgem.com> writes:

> > Checked and unchecked code may be mixed to the extent that checked and
> > unchecked code don't share aggregates (structs & arrays) containing
> > pointers whose size & layout change based on the size of pointers.
> 
> Just a question (as the author of Checker):  how will you manage stdio
> (for example) ?

You definitely put your finger on a problem area.  stdio is tough for
a couple reasons:
1) Layout of FILE is visible in getc & putc for some implemenations of stdio.
2) Printf & scanf accept varargs having pointer type.

The only ways I know to handle this is to
1) provide hand-written thunks (not the best way)
2) explicitly qualify the stdio interfaces as having unbounded
   pointers using the __unbounded cv-qualifier & attribute.
   (a better way, but requires hacking header files)
3) build stdio with bounded pointers (best if you have stdio source)

Greg

Re: Bounds checking

[Greg McGary]

Nigel.Horne@marconicomms.com writes:

> Is anyone planning to port http://www-ala.doc.ic.ac.uk/~phjk/BoundsChecking.html
> from gcc-2.7.2 to gcc-2.95? (And if not why not :-)

FYI, I am working on bounds checking in gcc at this very moment,
however I am using a completely different approach.  My work uses
bounded (a/k/a/ "fat") pointers.  Instead of the usual single-word
pointer, BPs are three-word records containing pointer value, base and
extent.  The pointer value is checked against base & extent at the
time of dereference.

Checked and unchecked code may be mixed to the extent that checked and
unchecked code don't share aggregates (structs & arrays) containing
pointers whose size & layout change based on the size of pointers.
When a file is compiled with bounded pointers, gcc attaches a special
prefix to the names of functions that accept pointer arguments or
return pointer values.  If the function's signature has only simple
pointers to scalars or aggregates that don't have pointers, then gcc
can automatically generate a thunk to translate between BP and non-BP
versions of the function.  For each function defined with BPs, gcc
generates a non-BP version that adds bounds to pointer args, calls the
BP version, then strips away bounds from return value.  For extern
functions that might be defined as non-BP, gcc generates a BP version
that does the opposite.  Thunks are only generated when it is safe to
do so: Functions that have argument or return values that are
aggregates or pointers to aggregates whose element sizes & layouts
change based on the size of pointers will not get automatically
generated thunks.  If such functions are shared between checked and
unchecked code, there will be undefined symbols at link time which
must be resolved by either shifting the boundary between checked and
unchecked code, or by manually writing thunks to rewrite argument and
return-value aggregates.  Thunks are only of concern in mixed
environments.  For applications where all source code is available,
thunks are not needed.  For device code where the size of
pointers in memory-mapped registers or shared data structures cannot
change, it is possible to designate pointers as `__unbounded', which
can be used as a qualifier or attribute.

I am working on the gcc trunk (2.96) and have finished most of the
C-tree hacking code working well enough to pass most of c-torture with
fat pointers, but with no actual bounds checks yet.  I am almost done
with the thunk generation pass.  After I have thunks, I can test
building and running some application code, such as GNU fileutils,
textutils and sh-utils linked with an unchecked libc.  After that
works, then I'll build a checked glibc, making mods to the
assembler-language interfaces (mostly string functions and system
calls) as required.

After that, I'll do C++, then maybe Java and/or Chill.

IMO, the implementation you cite above is severely crippled with
regard to runtime and space overhead.  My earlier implementation of
bounded pointers (based on 2.7.2) ran with approx. 75% space and time
overhead on i386 and i960 without any optimizations to eliminate
redundant checks.  With optimizations, I hope to shave space & time
overhead to as little as 25%.  By comparison, the bounds checking
implementation you cite has over 500% time overhead and over 100% space
overhead, making it unsuitable for many real-world applications,
particularly embedded & realtime ones.

Greg

Re: Bounds checking

[Greg McGary]

Tristan Gingold <tgi@netgem.com> writes:

> > Checked and unchecked code may be mixed to the extent that checked and
> > unchecked code don't share aggregates (structs & arrays) containing
> > pointers whose size & layout change based on the size of pointers.
> 
> Just a question (as the author of Checker):  how will you manage stdio
> (for example) ?

You definitely put your finger on a problem area.  stdio is tough for
a couple reasons:
1) Layout of FILE is visible in getc & putc for some implemenations of stdio.
2) Printf & scanf accept varargs having pointer type.

The only ways I know to handle this is to
1) provide hand-written thunks (not the best way)
2) explicitly qualify the stdio interfaces as having unbounded
   pointers using the __unbounded cv-qualifier & attribute.
   (a better way, but requires hacking header files)
3) build stdio with bounded pointers (best if you have stdio source)

Greg

Re: Bounds checking

[Greg McGary]

Nigel.Horne@marconicomms.com writes:

> Is anyone planning to port http://www-ala.doc.ic.ac.uk/~phjk/BoundsChecking.html
> from gcc-2.7.2 to gcc-2.95? (And if not why not :-)

FYI, I am working on bounds checking in gcc at this very moment,
however I am using a completely different approach.  My work uses
bounded (a/k/a/ "fat") pointers.  Instead of the usual single-word
pointer, BPs are three-word records containing pointer value, base and
extent.  The pointer value is checked against base & extent at the
time of dereference.

Checked and unchecked code may be mixed to the extent that checked and
unchecked code don't share aggregates (structs & arrays) containing
pointers whose size & layout change based on the size of pointers.
When a file is compiled with bounded pointers, gcc attaches a special
prefix to the names of functions that accept pointer arguments or
return pointer values.  If the function's signature has only simple
pointers to scalars or aggregates that don't have pointers, then gcc
can automatically generate a thunk to translate between BP and non-BP
versions of the function.  For each function defined with BPs, gcc
generates a non-BP version that adds bounds to pointer args, calls the
BP version, then strips away bounds from return value.  For extern
functions that might be defined as non-BP, gcc generates a BP version
that does the opposite.  Thunks are only generated when it is safe to
do so: Functions that have argument or return values that are
aggregates or pointers to aggregates whose element sizes & layouts
change based on the size of pointers will not get automatically
generated thunks.  If such functions are shared between checked and
unchecked code, there will be undefined symbols at link time which
must be resolved by either shifting the boundary between checked and
unchecked code, or by manually writing thunks to rewrite argument and
return-value aggregates.  Thunks are only of concern in mixed
environments.  For applications where all source code is available,
thunks are not needed.  For device code where the size of
pointers in memory-mapped registers or shared data structures cannot
change, it is possible to designate pointers as `__unbounded', which
can be used as a qualifier or attribute.

I am working on the gcc trunk (2.96) and have finished most of the
C-tree hacking code working well enough to pass most of c-torture with
fat pointers, but with no actual bounds checks yet.  I am almost done
with the thunk generation pass.  After I have thunks, I can test
building and running some application code, such as GNU fileutils,
textutils and sh-utils linked with an unchecked libc.  After that
works, then I'll build a checked glibc, making mods to the
assembler-language interfaces (mostly string functions and system
calls) as required.

After that, I'll do C++, then maybe Java and/or Chill.

IMO, the implementation you cite above is severely crippled with
regard to runtime and space overhead.  My earlier implementation of
bounded pointers (based on 2.7.2) ran with approx. 75% space and time
overhead on i386 and i960 without any optimizations to eliminate
redundant checks.  With optimizations, I hope to shave space & time
overhead to as little as 25%.  By comparison, the bounds checking
implementation you cite has over 500% time overhead and over 100% space
overhead, making it unsuitable for many real-world applications,
particularly embedded & realtime ones.

Greg

Bounds Checking

[Sebastien Loisel]

Hello.

I noticed a one month old thread about bounds checking for gcc. This would be 
very useful to many of us. The thread mostly discussed fat pointers and some 
other hacks which were less clear to me. I would like to point out that Richard 
Jones and Paul Kelly a long time ago (1995) released patches for gcc 2.7.0 (and 
then to 2.7.1 and 2.7.2) for fine grained bounds checking. According to the web 
page, the method they use preserves binary compatibility and does not result in 
ridiculous slowdowns.

If anyone is going to implement this (and I certainly hope it will happen), it 
seems that Richard and Paul's work should be checked out. However, I have never 
tried it myself so I can't really answer any questions.

http://www-ala.doc.ic.ac.uk/~phjk/BoundsChecking.html

Sebastien Loisel -- McGill University -- Sun Microsystems
http://www.math.mcgill.ca/~loisel/

Re: Bounds Checking

[Philipp Thomas]

On Tue, 17 Aug 1999 16:24:23 -0700 (PDT), Sebastien Loisel
<Sebastien.Loisel@Eng.Sun.COM> wrote:

>other hacks which were less clear to me. I would like to point out that Richard 
>Jones and Paul Kelly a long time ago (1995) released patches for gcc 2.7.0 (and 
>then to 2.7.1 and 2.7.2)

Yes, I know. I contacted Richard and some months ago he notified me that he
had finally got all that was needed to assign that work to the FSF done. 

Someone from Belgium (Herman ten Brugge, if I remember correctly) has
already ported those patches to egcs and last I read he is porting those
patches to gcc 2.95.

If you search the archives you will find his mail (I don't have his email
address) and maybe you would like to contact him directly.


-- 
Philipp Thomas          SuSE GmbH              phone    +49-911-3247130
pthomas@suse.de         Schanzaeckerstr. 10      fax    +49-911-3206727
http://www.suse.de      D-90443 Nuremberg, Germany

Re: Bounds Checking

[Philipp Thomas]

On Tue, 17 Aug 1999 16:24:23 -0700 (PDT), Sebastien Loisel
<Sebastien.Loisel@Eng.Sun.COM> wrote:

>other hacks which were less clear to me. I would like to point out that Richard 
>Jones and Paul Kelly a long time ago (1995) released patches for gcc 2.7.0 (and 
>then to 2.7.1 and 2.7.2)

Yes, I know. I contacted Richard and some months ago he notified me that he
had finally got all that was needed to assign that work to the FSF done. 

Someone from Belgium (Herman ten Brugge, if I remember correctly) has
already ported those patches to egcs and last I read he is porting those
patches to gcc 2.95.

If you search the archives you will find his mail (I don't have his email
address) and maybe you would like to contact him directly.


-- 
Philipp Thomas          SuSE GmbH              phone    +49-911-3247130
pthomas@suse.de         Schanzaeckerstr. 10      fax    +49-911-3206727
http://www.suse.de      D-90443 Nuremberg, Germany

Bounds Checking

[Sebastien Loisel]

Hello.

I noticed a one month old thread about bounds checking for gcc. This would be 
very useful to many of us. The thread mostly discussed fat pointers and some 
other hacks which were less clear to me. I would like to point out that Richard 
Jones and Paul Kelly a long time ago (1995) released patches for gcc 2.7.0 (and 
then to 2.7.1 and 2.7.2) for fine grained bounds checking. According to the web 
page, the method they use preserves binary compatibility and does not result in 
ridiculous slowdowns.

If anyone is going to implement this (and I certainly hope it will happen), it 
seems that Richard and Paul's work should be checked out. However, I have never 
tried it myself so I can't really answer any questions.

http://www-ala.doc.ic.ac.uk/~phjk/BoundsChecking.html

Sebastien Loisel -- McGill University -- Sun Microsystems
http://www.math.mcgill.ca/~loisel/