Jump to page: 1 26  
Page
Thread overview
Making alloca more safe
Nov 16, 2009
Denis Koroskin
Nov 16, 2009
Walter Bright
Nov 16, 2009
bearophile
Nov 16, 2009
dsimcha
Nov 16, 2009
Denis Koroskin
Nov 16, 2009
Yigal Chripun
Nov 16, 2009
Denis Koroskin
Nov 16, 2009
dsimcha
Nov 16, 2009
Denis Koroskin
Nov 16, 2009
dsimcha
Nov 16, 2009
Frank Benoit
Nov 16, 2009
Walter Bright
Nov 16, 2009
bearophile
Nov 16, 2009
dsimcha
Nov 16, 2009
Walter Bright
Nov 16, 2009
grauzone
Nov 16, 2009
Walter Bright
Nov 16, 2009
Derek Parnell
Nov 16, 2009
Walter Bright
Nov 16, 2009
bearophile
Nov 16, 2009
Walter Bright
Nov 17, 2009
bearophile
Nov 17, 2009
Max Samukha
Nov 17, 2009
Walter Bright
Nov 17, 2009
dsimcha
D2 front-end for LLVM (Was: Re: Making alloca more safe)
Nov 17, 2009
bearophile
Nov 17, 2009
Walter Bright
Nov 17, 2009
Sean Kelly
Nov 17, 2009
Sean Kelly
Nov 17, 2009
Walter Bright
Nov 19, 2009
BCS
Nov 17, 2009
Max Samukha
Nov 19, 2009
BCS
Nov 20, 2009
Walter Bright
Nov 20, 2009
BCS
Nov 20, 2009
Walter Bright
Nov 20, 2009
BCS
Nov 20, 2009
Walter Bright
Nov 22, 2009
BCS
Nov 22, 2009
Walter Bright
Nov 23, 2009
BCS
Nov 25, 2009
Walter Bright
Nov 16, 2009
Adam D. Ruppe
November 16, 2009
C standard library alloca function has an undefined behavior when requested size is large enough to cause a stack overflow, but many (good) implementations return null instead. So does DMD, for example. I believe it would be even better to go ahead and enforce D implementation to return a GC allocated chunk of memory instead of null in that case. It will not incur any performance hit in 99.9% of the cases and prevent a bug from being happen in the rest. It will also make writing code using it easier (and more safe), since you don't have to worry about possible stack overflow/null-dereference.
November 16, 2009
Denis Koroskin wrote:
> C standard library alloca function has an undefined behavior when requested size is large enough to cause a stack overflow, but many (good) implementations return null instead. So does DMD, for example. I believe it would be even better to go ahead and enforce D implementation to return a GC allocated chunk of memory instead of null in that case. It will not incur any performance hit in 99.9% of the cases and prevent a bug from being happen in the rest. It will also make writing code using it easier (and more safe), since you don't have to worry about possible stack overflow/null-dereference.

I'm a little reluctant to do this because alloca is supposed to be a low level routine, not one that has a dependency on the rather large and complex gc. A person using alloca is expecting stack allocation, and that it goes away after the function exits. Switching arbitrarily to the gc will not be detected and may hide a programming error (asking for a gigantic piece of memory is not anticipated for alloca, and could be caused by an overflow or logic error in calculating its size).

And secondly, I wish to emphasize that a null pointer seg fault is not an unsafe thing. It does not lead to memory corruption. It simply stops the program.
November 16, 2009
Walter Bright:

> A person using alloca is expecting stack allocation, and that it goes away after the function exits. Switching arbitrarily to the gc will not be detected and may hide a programming error (asking for a gigantic piece of memory is not anticipated for alloca, and could be caused by an overflow or logic error in calculating its size).

There's another solution, that I'd like to see more often used in Phobos: you can add another function to Phobos, let's call it salloca (safe alloca) that does what Denis Koroskin asks for (it's a very simple function).

Bye,
bearophile
November 16, 2009
== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> Denis Koroskin wrote:
> > C standard library alloca function has an undefined behavior when requested size is large enough to cause a stack overflow, but many (good) implementations return null instead. So does DMD, for example. I believe it would be even better to go ahead and enforce D implementation to return a GC allocated chunk of memory instead of null in that case. It will not incur any performance hit in 99.9% of the cases and prevent a bug from being happen in the rest. It will also make writing code using it easier (and more safe), since you don't have to worry about possible stack overflow/null-dereference.
> I'm a little reluctant to do this because alloca is supposed to be a low
> level routine, not one that has a dependency on the rather large and
> complex gc. A person using alloca is expecting stack allocation, and
> that it goes away after the function exits. Switching arbitrarily to the
> gc will not be detected and may hide a programming error (asking for a
> gigantic piece of memory is not anticipated for alloca, and could be
> caused by an overflow or logic error in calculating its size).
> And secondly, I wish to emphasize that a null pointer seg fault is not
> an unsafe thing. It does not lead to memory corruption. It simply stops
> the program.

Yes, but it stops the program in such a way that it's very hard to figure out why/where it died.  The solution, which I've wanted for a while and I think others have proposed, is for DMD to implicitly assert that every pointer is non-null before dereferencing it when in debug mode.
November 16, 2009
On Mon, 16 Nov 2009 17:01:32 +0300, dsimcha <dsimcha@yahoo.com> wrote:

> == Quote from Walter Bright (newshound1@digitalmars.com)'s article
>> Denis Koroskin wrote:
>> > C standard library alloca function has an undefined behavior when
>> > requested size is large enough to cause a stack overflow, but many
>> > (good) implementations return null instead. So does DMD, for example.  
>> I
>> > believe it would be even better to go ahead and enforce D  
>> implementation
>> > to return a GC allocated chunk of memory instead of null in that case.
>> > It will not incur any performance hit in 99.9% of the cases and  
>> prevent
>> > a bug from being happen in the rest. It will also make writing code
>> > using it easier (and more safe), since you don't have to worry about
>> > possible stack overflow/null-dereference.
>> I'm a little reluctant to do this because alloca is supposed to be a low
>> level routine, not one that has a dependency on the rather large and
>> complex gc. A person using alloca is expecting stack allocation, and
>> that it goes away after the function exits. Switching arbitrarily to the
>> gc will not be detected and may hide a programming error (asking for a
>> gigantic piece of memory is not anticipated for alloca, and could be
>> caused by an overflow or logic error in calculating its size).
>> And secondly, I wish to emphasize that a null pointer seg fault is not
>> an unsafe thing. It does not lead to memory corruption. It simply stops
>> the program.
>
> Yes, but it stops the program in such a way that it's very hard to figure out
> why/where it died.  The solution, which I've wanted for a while and I think others
> have proposed, is for DMD to implicitly assert that every pointer is non-null
> before dereferencing it when in debug mode.

... or use the type system to enforce all/most of the pointers to be non-null.
November 16, 2009
== Quote from Denis Koroskin (2korden@gmail.com)'s article
> On Mon, 16 Nov 2009 17:01:32 +0300, dsimcha <dsimcha@yahoo.com> wrote:
> > == Quote from Walter Bright (newshound1@digitalmars.com)'s article
> >> Denis Koroskin wrote:
> >> > C standard library alloca function has an undefined behavior when requested size is large enough to cause a stack overflow, but many (good) implementations return null instead. So does DMD, for example.
> >> I
> >> > believe it would be even better to go ahead and enforce D
> >> implementation
> >> > to return a GC allocated chunk of memory instead of null in that case. It will not incur any performance hit in 99.9% of the cases and
> >> prevent
> >> > a bug from being happen in the rest. It will also make writing code using it easier (and more safe), since you don't have to worry about possible stack overflow/null-dereference.
> >> I'm a little reluctant to do this because alloca is supposed to be a low
> >> level routine, not one that has a dependency on the rather large and
> >> complex gc. A person using alloca is expecting stack allocation, and
> >> that it goes away after the function exits. Switching arbitrarily to the
> >> gc will not be detected and may hide a programming error (asking for a
> >> gigantic piece of memory is not anticipated for alloca, and could be
> >> caused by an overflow or logic error in calculating its size).
> >> And secondly, I wish to emphasize that a null pointer seg fault is not
> >> an unsafe thing. It does not lead to memory corruption. It simply stops
> >> the program.
> >
> > Yes, but it stops the program in such a way that it's very hard to
> > figure out
> > why/where it died.  The solution, which I've wanted for a while and I
> > think others
> > have proposed, is for DMD to implicitly assert that every pointer is
> > non-null
> > before dereferencing it when in debug mode.
> ... or use the type system to enforce all/most of the pointers to be non-null.

Yes, but this would greatly increase the complexity of the type system, which is already getting too complex.  A simple implicit assert would solve the problem 90% as well for 10% of the complexity.
November 16, 2009
dsimcha schrieb:
> Yes, but it stops the program in such a way that it's very hard to figure out why/where it died.  The solution, which I've wanted for a while and I think others have proposed, is for DMD to implicitly assert that every pointer is non-null before dereferencing it when in debug mode.

This would be great. The compiler could also optimize those away in cases of repeated access without ref assign in between

void foo( Object o){
  o.toString(); // o !is null checked
  o.toHash();   // o !is null not checked, because already done
}
November 16, 2009
bearophile wrote:
> Walter Bright:
> 
>> A person using alloca is expecting stack allocation, and that it goes away after the function exits. Switching arbitrarily to the gc will not be detected and may hide a programming error (asking for a gigantic piece of memory is not anticipated for alloca, and could be caused by an overflow or logic error in calculating its size).
> 
> There's another solution, that I'd like to see more often used in Phobos: you can add another function to Phobos, let's call it salloca (safe alloca) that does what Denis Koroskin asks for (it's a very simple function).

Can't be written. Try it.

Andrei
November 16, 2009
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> bearophile wrote:
> > Walter Bright:
> >
> >> A person using alloca is expecting stack allocation, and
> >> that it goes away after the function exits. Switching arbitrarily to the
> >> gc will not be detected and may hide a programming error (asking for a
> >> gigantic piece of memory is not anticipated for alloca, and could be
> >> caused by an overflow or logic error in calculating its size).
> >
> > There's another solution, that I'd like to see more often used in Phobos: you
can add another function to Phobos, let's call it salloca (safe alloca) that does
what Denis Koroskin asks for (it's a very simple function).
> Can't be written. Try it.
> Andrei

As a side note, my TempAlloc allocator was intended all along to be a safer and more flexible allocation scheme that was almost as efficient as call stack allocation, and does fall back on heap allocation, or creating a new non-contiguous chunk, when it runs out of space.  Also, I think I'll be able to fix the GC scanning issue  by fiddling with pointer offset info if/when my precise heap scanning patch gets into druntime.  If/when TempAlloc can be made both safe and efficient w.r.t. GC scanning, I'd nominate it for inclusion in Phobos.
November 16, 2009
On Mon, 16 Nov 2009 19:27:41 +0300, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> bearophile wrote:
>> Walter Bright:
>>
>>> A person using alloca is expecting stack allocation, and that it goes away after the function exits. Switching arbitrarily to the gc will not be detected and may hide a programming error (asking for a gigantic piece of memory is not anticipated for alloca, and could be caused by an overflow or logic error in calculating its size).
>>  There's another solution, that I'd like to see more often used in Phobos: you can add another function to Phobos, let's call it salloca (safe alloca) that does what Denis Koroskin asks for (it's a very simple function).
>
> Can't be written. Try it.
>
> Andrei

It's tricky. It can't be written *without a compiler support*, because it is considered special for a compiler (it always inlines the call to it). It could be written otherwise.

I was thinking about proposing either an inline keyword in a language (one that would enforce function inlining, rather than suggesting it to compiler), or allways inline all the functions that make use of alloca. Without either of them, it is impossible to create wrappers around alloca (for example, one that create arrays on stack type-safely and without casts):

T[] array_alloca(T)(size_t size) { ... }

or one that would return GC-allocated memory when stack allocation fails:

void* salloca(size_t size) {
    void* ptr = alloca(size);
    if (ptr is null) return (new void[size]).ptr;

    return ptr;
}
« First   ‹ Prev
1 2 3 4 5 6