Policy: alloca vs. malloc?

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Policy: alloca vs. malloc?

Carlos O'Donell-4
Community,

A recent discussion about alloc vs. malloc has sparked the
creation of some additional policy to help guide developers
when making the choice.

The current text is here:
http://sourceware.org/glibc/wiki/Style_and_Conventions#Alloca_vs._Malloc

Reproduced here for discussion purposes:
~~~
== Alloca vs. Malloc ==

The use of alloca vs. malloc must be evaluated on a case-by-case basis. There are many things to consider when looking at using alloca or malloc.

Here are some things to consider when deciding whether to use alloca or malloc:

 * Do not use alloca to create an array whose size {{{S}}} is such that {{{! libc_use_alloca (S)}}}, as large arrays like that may bypass stack-overflow checking.

 * If the storage may need to outlive the current function, then obviously alloca cannot be used.

 * If the API does not allow returning a memory-allocation failure indication such as {{{ENOMEM}}}, then alloca may be preferable, as malloc can fail.

 * If this is a hot path with a small allocation, prefer alloca, as it is typically much faster.

 * When growing a buffer, either on the stack or on the heap, watch out for integer overflow when calculating the new size. Such overflow should be treated as allocation failure than letting the integer wrap around.

 * If the size of the buffer is directly or indirectly under user control, consider imposing a maximum to help make denial-of-service attacks more difficult.

 * If this is a hot path and the allocation size is typically small but may be large, and is known in advance, you can use the following  pattern:
{{{
    bool use_alloca = __libc_use_alloca (bufsize);
    struct foo *buf = use_alloca ? alloca (bufsize) : malloc (bufsize);
    do_work_with (buf, bufsize);
    if (! use_alloca)
      free (buf);
}}}

  This use of alloca is a memory optimization.  That is, the above {{{alloca}}} example is almost equivalent to the following:
{{{
    struct foo buffer[__MAX_ALLOCA_CUTOFF / sizeof (struct foo)];
    bool use_auto = bufsize <= sizeof buffer;
    struct foo *buf = use_auto ? buffer : malloc (bufsize);
    do_work_with (buf, bufsize);
    if (! use_auto)
      free (buf);
}}}
  except that the {{{alloca}}} version consumes only the stack space needed, rather than always consuming approximately {{{__MAX_ALLOCA_CUTOFF}}} bytes. Note that this isn't quite equivalent to the previous example because {{{__libc_use_alloca}}} limits alloca to {{{PTHREAD_STACK_MIN/4}}} (which may be bigger than {{{__MAX_ALLOCA_CUTOFF}}}) or {{{<thread stack size>/4}}}, the latter having a maximum bound of {{{__MAX_ALLOCA_CUTOFF}}}.

 * If the amount of storage is not known in advance but may grow without bound, you can start with a small buffer on the stack and switch to malloc if it is not large enough.  For example:

{{{
    struct foo buffer[__MAX_ALLOCA_CUTOFF / sizeof (struct foo)];
    struct foo *buf = buffer;
    size_t bufsize = sizeof buffer;
    void *allocated = NULL;
    size_t needed;
    while (bufsize < (needed = do_work_with (buf, bufsize)))
      {
        buf = realloc (allocated, needed);
        if (! buf)
          {
            needed = 0;
            break;
          }
        allocated = buf;
        bufsize = needed;
      }
    free (allocated);
    return needed; /* This is zero on allocation failure.  */
}}}

 * You can also grow a single buffer on the stack, so long as it does not get too large, by using {{{extend_alloca}}}.  This is a memory optimization of the previous example, just as {{{alloca}}} is a memory optimization of a local array.  For example:

{{{
    size_t bufsize = 256;
    struct foo *buf = alloca (bufsize);
    void *allocated = NULL;
    size_t needed;
    while (bufsize < (needed = do_work_with (buf, bufsize)))
      {
        if (__libc_use_alloca (needed))
          buf = extend_alloca (buf, bufsize, needed);
        else
          {
            buf = realloc (allocated, needed);
            if (! buf)
              {
                needed = 0;
                break;
              }
            bufsize = needed;
          }
      }
    free (allocated);
    return needed; /* This is zero on allocation failure.  */
}}}

 * To boost performance a bit in the typical case of the above examples, you can use {{{__builtin_expect}}}, e.g., {{{if (__builtin_expect (use_alloca, 1))}}} instead of just {{{if (use_alloca)}}}.

At present there is no magic bullet of special procedure for selecting alloca vs. malloc, if there was then we could encode it into this wiki or into a macro.
~~~

Comments?

Cheers,
Carlos.
--
Carlos O'Donell
Mentor Graphics / CodeSourcery
[hidden email]
[hidden email]
+1 (613) 963 1026
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Siddhesh Poyarekar
On 7 June 2012 22:59, Carlos O'Donell <[hidden email]> wrote:
>  * If this is a hot path and the allocation size is typically small but may be large, and is known in advance, you can use
> the following  pattern:
> {{{
>    bool use_alloca = __libc_use_alloca (bufsize);
>    struct foo *buf = use_alloca ? alloca (bufsize) : malloc (bufsize);

There should be a check here to ensure that buf is not NULL.

>    do_work_with (buf, bufsize);
>    if (! use_alloca)
>      free (buf);
> }}}


>  This use of alloca is a memory optimization.  That is, the above {{{alloca}}} example is almost equivalent to the following:
> {{{
>    struct foo buffer[__MAX_ALLOCA_CUTOFF / sizeof (struct foo)];
>    bool use_auto = bufsize <= sizeof buffer;
>    struct foo *buf = use_auto ? buffer : malloc (bufsize);
>    do_work_with (buf, bufsize);
>    if (! use_auto)
>      free (buf);
> }}}
>  except that the {{{alloca}}} version consumes only the stack space needed, rather than always consuming approximately {{{__MAX_ALLOCA_CUTOFF}}} bytes. Note that this isn't quite equivalent to the previous example because {{{__libc_use_alloca}}} limits alloca to {{{PTHREAD_STACK_MIN/4}}} (which may be bigger than {{{__MAX_ALLOCA_CUTOFF}}}) or {{{<thread stack size>/4}}}, the latter having a maximum bound of {{{__MAX_ALLOCA_CUTOFF}}}.

This is unnecessary and even wrong. This code allocates both, on stack
as well as on heap. That is not what the cutoff selection code above
will do -- you'll have only one of the two. Also, there's never really
a case where all of the __MAX_ALLOCA_CUTOFF is allocated, so the only
'memory optimization' to speak of here is the malloc chunk overhead on
the heap, which isn't much to brag about.


--
Siddhesh Poyarekar
http://siddhesh.in
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Paul Eggert
On 06/07/2012 02:55 AM, Jakub Jelinek wrote:
> __libc_use_alloca does actually more than that, it isn't a fixed limit
> comparison, but if the size is larger than PTHREAD_STACK_MIN / 4,
> it limits use of alloca to current thread stack size / 4 (and
> __MAX_ALLOCA_CUTOFF as a maximum).

Thanks, I fixed this by changing __MAX_ALLOCA_CUTOFF to 4000 in the
example.

On 06/07/2012 07:59 PM, Siddhesh Poyarekar wrote:
> There should be a check here to ensure that buf is not NULL.

Thanks, I fixed that in the wiki.

> the only
> 'memory optimization' to speak of here is the malloc chunk overhead on
> the heap, which isn't much to brag about.

Sorry, I don't follow.  Both versions use the same amount of heap memory.
When using the stack, the alloca version allocates fewer bytes than the
non-alloca version.  Granted, this is not a huge amount of memory savings
(it's bounded by the size of the local array) but it does save some space.

I tried to clarify this by changing the wording to the following:

   Use of {{{alloca}}} is a memory optimization. That is, the above example
   is close in behavior to the following, except that the {{{alloca}}}
   version consumes only the stack space needed, rather than always consuming
   approximately 4000 bytes on the stack.

Also, I removed one of the examples with a fixed-size array (the point
is made sufficently in one example; it doesn't need two).  And I changed
the example with a growing stack-array to fix some other problems.  Here's
the new example.  It's tricker than what I'd like but the issue is
a tricky one....

=====

* If the amount of storage is not known in advance but may grow without bound, you can start with a small buffer on the stack and switch to malloc if it gets to be too large for the stack. While the storage is on the stack, you can grow it by using extend_alloca. For example:

    struct foo buffer[10];
    struct foo *buf = buffer;
    size_t bufsize = sizeof buffer;
    void *allocated = NULL;
    size_t needed;
    while (bufsize < (needed = do_work_with (buf, bufsize)))
      {
        if (__libc_use_alloca (needed))
          {
            size_t size = bufsize;
            void *newbuf = extend_alloca (buf, bufsize, needed);
            buf = memmove (newbuf, buf, size);
          }
        else
          {
            void *newbuf = realloc (allocated, needed);
            if (! newbuf)
              {
                needed = 0;
                break;
              }
            if (! allocated)
              memcpy (newbuf, buf, bufsize);
            buf = allocated = newbuf;
            bufsize = needed;
          }
      }
    free (allocated);
    return needed; /* This is zero on allocation failure.  */
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Siddhesh Poyarekar
On 8 June 2012 11:54, Paul Eggert <[hidden email]> wrote:

>> the only
>> 'memory optimization' to speak of here is the malloc chunk overhead on
>> the heap, which isn't much to brag about.
>
> Sorry, I don't follow.  Both versions use the same amount of heap memory.
> When using the stack, the alloca version allocates fewer bytes than the
> non-alloca version.  Granted, this is not a huge amount of memory savings
> (it's bounded by the size of the local array) but it does save some space.
>
> I tried to clarify this by changing the wording to the following:
>
>   Use of {{{alloca}}} is a memory optimization. That is, the above example
>   is close in behavior to the following, except that the {{{alloca}}}
>   version consumes only the stack space needed, rather than always consuming
>   approximately 4000 bytes on the stack.

I thought you meant memory optimization to be alloca vs malloc when
you could have done a malloc straight away, which is why I mentioned
the chunk overhead being the only saving. Your clarification above
seems to imply savings due to doing alloca when one could have
declared a local array of the max size. Is that what it is? It
probably needs to be even clearer, something like:

    Use of {{{alloca}}} is a memory optimization compared to having a
local array on stack...


--
Siddhesh Poyarekar
http://siddhesh.in
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Paul Eggert
On 06/07/2012 11:38 PM, Siddhesh Poyarekar wrote:
>     Use of {{{alloca}}} is a memory optimization compared to having a
> local array on stack..

Thanks, I've included that wording in the wiki.
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Pedro Alves-7
In reply to this post by Carlos O'Donell-4
On 06/07/2012 06:29 PM, Carlos O'Donell wrote:

>  * When growing a buffer, either on the stack or on the heap, watch out for integer overflow when calculating the new size. Such overflow should be treated as allocation failure than letting the integer wrap around.
>
>  * If the size of the buffer is directly or indirectly under user control, consider imposing a maximum to help make denial-of-service attacks more difficult.


These appear to not really be "alloca vs malloc" material, but general guides that'd
better fit a different section.

--
Pedro Alves
Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Jeff Law
On 06/08/2012 03:40 AM, Pedro Alves wrote:
> On 06/07/2012 06:29 PM, Carlos O'Donell wrote:
>
>>   * When growing a buffer, either on the stack or on the heap, watch out for integer overflow when calculating the new size. Such overflow should be treated as allocation failure than letting the integer wrap around.
>>
>>   * If the size of the buffer is directly or indirectly under user control, consider imposing a maximum to help make denial-of-service attacks more difficult.
>
>
> These appear to not really be "alloca vs malloc" material, but general guides that'd
> better fit a different section.
True, but a integer overflow feeding alloca can be turned into an
exploit relatively easily as can an allocation where the size of the
buffer is directly or indirectly under user control.

I think they're important enough to mention in the alloca section given
the numerous problems this kind of stuff has led to.

Jeff

Reply | Threaded
Open this post in threaded view
|

Re: Policy: alloca vs. malloc?

Pedro Alves-7
On 06/08/2012 02:26 PM, Jeff Law wrote:

> On 06/08/2012 03:40 AM, Pedro Alves wrote:
>> On 06/07/2012 06:29 PM, Carlos O'Donell wrote:
>>
>>>   * When growing a buffer, either on the stack or on the heap, watch out for integer overflow when calculating the new size. Such overflow should be treated as allocation failure than letting the integer wrap around.
>>>
>>>   * If the size of the buffer is directly or indirectly under user control, consider imposing a maximum to help make denial-of-service attacks more difficult.
>>
>>
>> These appear to not really be "alloca vs malloc" material, but general guides that'd
>> better fit a different section.
> True, but a integer overflow feeding alloca can be turned into an exploit relatively easily as can an allocation where the size of the buffer is directly or indirectly under user control.


Note the sentence says "either on the stack or on the heap".

> I think they're important enough to mention in the alloca section given the numerous problems this kind of stuff has led to.


This is not an "how to use alloca" section, but a "choose alloca or malloc ?" policy
section.  Those two points don't weigh on that decision.
You first decide which mechanism to use based on the other points, and then there's the
question of using the mechanism properly, but that is a separate question.
The advice quote above could be put on a "on alloca" or "on memory allocation"
or "on memory management and security" section just below, or some such, which could
even mention more things.

Just IMO anyway.

--
Pedro Alves