View mode: basic / threaded / horizontal-split · Log in · Help
November 16, 2009
Making alloca more safe
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
Re: Making alloca more safe
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
Re: Making alloca more safe
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
Re: Making alloca more safe
== 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
Re: Making alloca more safe
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
Re: Making alloca more safe
== 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
Re: Making alloca more safe
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
Re: Making alloca more safe
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
Re: Making alloca more safe
== 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
Re: Making alloca more safe
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
Top | Discussion index | About this forum | D home