Alloca for run-time stack allocation

[gmhwxi]

Assigning a safe type for alloca may be a bit trick. Here is a reasonable attempt:

fun alloca
  {dummy:addr}{n:int}
  (pf: void@dummy | n: size_t (n) )
: [l:addr] (bytes(n) @ l, bytes(n) @ l -> void@dummy | ptr (l))

The use of 'dummy' is to make sure that the allocated stack-memory disappears once the function 'foo' returns:

fun foo() = let
//
var dummy: void = ()
val (pfat, fpf | p) = alloca (view@dummy | i2sz(1024))
prval () = view@dummy := fpf (pfat)
//
in
  // nothing
end // end of [foo]

[Brandon Barker]

My C knowledge is not very good here. I see that the linear interface for alloca prevents the behavior I'm about to ask about, but let us say the interface was not linear and we did:

val p = alloca (i2sz(1024))

In C, the memory pointed to by p would be freed when the function returns. Does this mean that such an interface would allow a memory leak on the stack, even though it is not possible (as far as I know) to have a memory leak on the stack in C?

[gmhwxi]

This type of error is commonly referred to as dangling pointers.

[gmhwxi]

Leak means that a resource should be freed but not freed.
Dangling pointer is the opposite: trying to access memory that has been freed.

[Brandon Barker]

I admit it has been a while since I've heard that term. But, above you said "The use of 'dummy' is to make sure that the allocated stack-memory disappears once the function 'foo' returns", which seems to imply you could get some sort of leak if you didn't use this construction.

Also, my impression is that since p is also allocated within the function, it is also on the stack, and would be freed at the same time as the memory it points to: when the function returns. However, I now see this could be a problem if you were assigning to a pointer that was not on "the same level" in the stack. Then you would be in dangling pointer territory.

[gmhwxi]

Freeing is not an issue here: Whenever a call to foo returns, everything on its stack is freed.

The type for alloca makes sure that you will not accidentally create a dangling pointer: The proof
for view@dummy is tracked by the type system of ATS; this proof must be present for
'foo' to return in a type-safe manner. The alloca-related stuff is piggy-backed on the proof for view@dummy.

[Ian Denhardt]

There's another serious pitfall with using alloca - the stack is
generally *very* small, and as per the man page, if there isn't enough
stack, behavior is undefined. You'd somehow have to account for the size
of the remainder of the stack to use this safely. You can cause stack
overflow problems without this just by creating very large objects on
the stack, or very very deep recursion, but dynamically allocating stack
memory requires extra caution - my general rule of thumb for using it in
C is never.

Just my $0.02.

-Ian

Quoting gmhwxi (2014-02-14 11:10:08)

> --
> You received this message because you are subscribed to the Google
> Groups "ats-lang-users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to ats-lang-user...@googlegroups.com.
> To post to this group, send email to ats-lan...@googlegroups.com.
> To view this discussion on the web visit
> [1]https://groups.google.com/d/msgid/ats-lang-users/c03bb9b5-0bd7-4fe2-
> acb0-2f3fb6724bad%40googlegroups.com.
>
> References
>
> 1. https://groups.google.com/d/msgid/ats-lang-users/c03bb9b5-0bd7-4fe2-acb0-2f3fb6724bad%40googlegroups.com

[gmhwxi]

However, if you think about it, using alloca is not really any riskier than
using general recursion.

[Ian Denhardt]

Well, not unless your recursive function has more than a page worth of
local variables. In practice, most C implementations have a page after
the stack that is unmapped, so that if you overflow you'll get a page
fault, rather than trampling on something else. This is typically called
a "guard page". If your code ends up not touching this page at all,
which can happen if you have a huge stack allocated array and start

The trouble with alloca is that you can't always tell easily by looking
at the code whether or not this is possible. Before the C99 standard,
you had to declare all of your local variables at the top of the
function. The rationale for this was that it would make it obvious at a
glance how much stack space it was using.

Because each function call is going to write a return address to the
stack, you don't have to worry about skipping the guard page across
function calls, so simply asking "is this function using more than a
page of stack space?" is enough to decide whether or not you should
worry. With alloca, this is harder to understand, since the space used
is dependant on values only known at runtime.

It is possible to use alloca safely, but it is very error prone, and the
cases in which there aren't better solutions are at least rare, if they
even really exist. Checking that you don't end up using an invalid
pointer is a good step, but for alloca to really be safe, this needs to
be addressed as well. It's *possible* to hit this with generic
recursing, but general recursion is much less error prone in that
regard.

-Ian

Quoting gmhwxi (2014-02-14 12:08:10)

> > an email to [1]ats-lang-user...@googlegroups.com.

> > To post to this group, send email to

> [2]ats-lan...@googlegroups.com.

> > To view this discussion on the web visit

> > [1][3]https://groups.google.com/d/msgid/ats-lang-users/
> c03bb9b5-0bd7-4fe2-
> > acb0-2f3fb6724bad%[4]40googlegroups.com.
> >
> > References
> >
> > 1. [5]https://groups.google.com/d/
> msgid/ats-lang-users/c03bb9b5-0bd7-4fe2-acb0-2f3fb6724bad%
> 40googlegroups.com

>
> --
> You received this message because you are subscribed to the Google
> Groups "ats-lang-users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to ats-lang-user...@googlegroups.com.
> To post to this group, send email to ats-lan...@googlegroups.com.
> To view this discussion on the web visit

> [6]https://groups.google.com/d/msgid/ats-lang-users/822a8253-637e-4fcf-
> 9408-eb86bfda2fec%40googlegroups.com.
>
> References
>
> 1. javascript:/
> 2. javascript:/
> 3. https://groups.google.com/d/msgid/ats-lang-users/c03bb9b5-0bd7-4fe2-
> 4. http://40googlegroups.com/
> 5. https://groups.google.com/d/msgid/ats-lang-users/c03bb9b5-0bd7-4fe2-acb0-2f3fb6724bad%40googlegroups.com
> 6. https://groups.google.com/d/msgid/ats-lang-users/822a8253-637e-4fcf-9408-eb86bfda2fec%40googlegroups.com

[gmhwxi]

So if I use alloca to allocate a small number of bytes (say, 100), it should
be no riskier than general recursion, right? To a large extent, malloca is designed
for that purpose.

To me, the real danger of alloca (or malloca) in C is that it is very easy to
introduce dangling pointers. But this danger is essentially eliminated in ATS.
I don't use alloca in ATS much because it does not work well with inlining or
tail-recursion.

[gmhwxi]

I did a "fancy" example on alloca:

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/qa-list-195.dats

Given a list, the function list2array_filter filters out all the elements in a given list that satisfy a predicate
and then returns an array that stores these elements. The implementation of the function first filters out
the satisfying elements and stores them in a list allocated on stack (via alloca); then it creates an array to
store these elements. The stack-allocated list is automatically freed at once when list2array_filter returns.