Policy: alloca vs. malloc?

[Carlos O'Donell <carlos_odonell at mentor dot com>]

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
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026