www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - llvm's SAFECode bounds checking algorithm

reply Walter Bright <newshound1 digitalmars.com> writes:
http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf

What it does is rewrites the program to install runtime checks on 
pointers to ensure no array bounds overflows.

It indicates to me the effort being poured into C to try to make it 
memory safe, and how memory safety has become a huge issue in 
programming. We are on the right track with D with our focus on making D 
proveably memory safe.
Aug 20 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Walter:


 http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf
 We are on the right track with D with our focus on making D 
 proveably memory safe.


The paper strategy uses Automatic Pool Allocation:


Automatic Pool Allocation [13] is a fully automatic compile-time transformation
that partitions memory into pools corresponding to a compile-time partitioning
of objects computed by a pointer analysis. It tries to create pools that are as
fine-grained and short-lived as possible. It merges all the target objects of a
pointer into a single pool, thus ensuring that there is a unique pool
corresponding to each pointer.<



We have shown previously that Automatic Pool Allocation can significantly
improve memory hierarchy performance for a wide range of programs and does not
noticeably hurt performance in other cases [13]. It's compilation times are
quite low (less than 3 seconds for programs up to 200K lines of code), and are
a small fraction of the time taken by GCC to compile the same programs.<


It sounds useful for D compilers too, to improve and reduce the run-time work
of the D GC.
(That "it's" is wrong I think.)

The reference [13] is this one:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.9873&rep=rep1&type=pdf

Bye,
bearophile
Aug 20 2011
prev sibling next sibling parent Paulo Pinto <pjmlp progtools.org> writes:
Am 20.08.2011 17:40, schrieb Walter Bright:

 http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf

 What it does is rewrites the program to install runtime checks on
 pointers to ensure no array bounds overflows.

 It indicates to me the effort being poured into C to try to make it
 memory safe, and how memory safety has become a huge issue in
 programming. We are on the right track with D with our focus on making D
 proveably memory safe.


I think that he way arrays decay into pointers and how easy pointer 
arithmetic is in C and by consequense in C++ were very usefull on its 
day. But they lead us to the current situation where they open the door 
to exploits and software malfunction.

The people that argument that good programmers avoid such errors, 
usually forget that there are lots of not so good programmers or huge
teams developing software, which leads to these types of errors.

The last decade saw a rise in safe languages, and now people start to 
understand that actually safe languages are also quite good to develop in.

I am conviced that C and C++ are the last of their kind, in what 
concerns unsafe languages. The next major system programming will be 
mostly safe with escape holes for the dirty parts. Funny enough, we 
could have got that a few decades ago had computing not gone the C way.


Still with the amount of legacy code we have, it is nice to see effort
being spent improving C and C++ safety, even though they look a bit
like patching. It only takes you so far.

--
Paulo
Aug 20 2011
prev sibling parent reply Robert Clipsham <robert octarineparrot.com> writes:
On 20/08/2011 16:40, Walter Bright wrote:

 http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf

 What it does is rewrites the program to install runtime checks on
 pointers to ensure no array bounds overflows.

 It indicates to me the effort being poured into C to try to make it
 memory safe, and how memory safety has become a huge issue in
 programming. We are on the right track with D with our focus on making D
 proveably memory safe.


<pushingTheBoatOut>

Given that a large part of D should be writable using  safe, perhaps we 
should look into making  safe default and having to explicitly write 
 system or  trusted for a function? This is obviously a no-go in D's 
current state (most of phobos/druntime aren't appropriately annotated 
and I believe there are a good few things that  safe forbids but 
could/should permit), but it would be cool to say "D is memory safe by 
default, the programmer has to explicitly state if it's not". Perhaps 
this could be done with a compiler switch for now to see how well it 
works in the real world/evaluate whether it's actually doable/what needs 
doing to make it doable.

</pushingTheBoatOut>

-- 
Robert
http://octarineparrot.com/
Aug 21 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/21/2011 12:55 PM, Robert Clipsham wrote:

 On 20/08/2011 16:40, Walter Bright wrote:

 http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf

 What it does is rewrites the program to install runtime checks on
 pointers to ensure no array bounds overflows.

 It indicates to me the effort being poured into C to try to make it
 memory safe, and how memory safety has become a huge issue in
 programming. We are on the right track with D with our focus on making D
 proveably memory safe.


 <pushingTheBoatOut>

 Given that a large part of D should be writable using  safe, perhaps we
 should look into making  safe default and having to explicitly write
  system or  trusted for a function? This is obviously a no-go in D's
 current state (most of phobos/druntime aren't appropriately annotated
 and I believe there are a good few things that  safe forbids but
 could/should permit), but it would be cool to say "D is memory safe by
 default, the programmer has to explicitly state if it's not". Perhaps
 this could be done with a compiler switch for now to see how well it
 works in the real world/evaluate whether it's actually doable/what needs
 doing to make it doable.

 </pushingTheBoatOut>


If  safe is declared the default, first  safe, and attributes/storage 
classes in general, need to be properly redesigned and implemented imho.

Eg:

int main() safe{
     int a;
     //auto p=&a;     // disallowed by dmd
     auto p=&(0?a:a); // allowed by dmd
}

I have filed a bug for this.


alias  system int F();
 safe:
int foo()  system;
static assert(is(typeof(foo)!=F));

and

 safe:
int foo()  system;
alias  system int F();
static assert(is(typeof(foo)==F));


The compiler does not currently catch this, because afaik the _parser_ 
is responsible for the detection of conflicting storage classes. I'd say 
that a declaration of the form

 safe:
int foo()  system;

should actually compile, but make foo a  system function. Then eg: a 
module with  safe as the default could be made by just adding ' safe': 
at its beginning. (or, if safe ends up being the default, the same would 
hold for  system:)

What _does_ work on the other hand is
 safe:
 system: int foo();  safe:


There are also such monsters as

pure alias int F();

and

alias auto bar=1;


I really think the way STCs are handled needs a (re)design.
Aug 21 2011
prev sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 21.08.2011, 12:55 Uhr, schrieb Robert Clipsham  
<robert octarineparrot.com>:


 On 20/08/2011 16:40, Walter Bright wrote:

 http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.pdf

 What it does is rewrites the program to install runtime checks on
 pointers to ensure no array bounds overflows.

 It indicates to me the effort being poured into C to try to make it
 memory safe, and how memory safety has become a huge issue in
 programming. We are on the right track with D with our focus on making D
 proveably memory safe.


 <pushingTheBoatOut>

 Given that a large part of D should be writable using  safe, perhaps we  
 should look into making  safe default and having to explicitly write  
  system or  trusted for a function? This is obviously a no-go in D's  
 current state (most of phobos/druntime aren't appropriately annotated  
 and I believe there are a good few things that  safe forbids but  
 could/should permit), but it would be cool to say "D is memory safe by  
 default, the programmer has to explicitly state if it's not". Perhaps  
 this could be done with a compiler switch for now to see how well it  
 works in the real world/evaluate whether it's actually doable/what needs  
 doing to make it doable.

 </pushingTheBoatOut>


This sounds very good to me, because I usually don't *need* to write  
unsafe code. I'd like to hear if people who are in unsafe territory all  
day could live with that.
Aug 21 2011