Re: alloca avoidance patches

[Adhemerval Zanella <adhemerval dot zanella at linaro dot org>]

On 19/06/2017 14:33, Szabolcs Nagy wrote:
> On 19/06/17 17:47, Joseph Myers wrote:
>> It seems to me that we need a clear definition of what stack frame size 
>> glibc can assume is safe (so that we can aim to eliminate alloca and VLAs 
>> unless the compiler can see they are bounded, and use -Wstack-usage= for 
>> building glibc to make sure no function uses too much stack).
> 
> my experience with musl is that the tricky recursive
> unbounded stack usage cases are not possible to catch
> with -Wstack-usage= (details below) and that it warns
> about several seemingly unbounded vlas that are clearly
> bounded after some manual analysis, i expect glibc
> would be similar.
> 
> 
> in musl the rule is that calling into libc will not
> use more than 16K stack on any target.
> (the actual value in practice is around 9K for
> long double conversion functions on some targets)
> (and i think there is a less strict rule that
> as-safe calls that may appear in signal handlers
> should not use more than 6K stack which affect
> the SIGSTKSZ definition)
> 
> this is complicated by callback apis (when the libc
> can be entered several times), and allocation that
> is compile time controlled by the caller (execl
> copies the argument pointers to an array on the stack,
> this is not accounted as libc stack use) and the compiler
> can break the guarantee when it inlines and allocates
> stack for the sum of disjunct code paths instead of the max.
> 
> there are two known cases where the rule is violated:
> the recursive implementation of nftw can use more stack
> (though it is still bounded by the PATH_MAX limit musl
> enforces) and there is a known issue in the tre regcomp
> implementation which recursively walks its regex ast
> (depth is only limited by a big ast node limit i think)
> 
> in case of glibc there are other considerations like
> lazy binding increases libc stack use because simd
> regs are saved which have to be taken into account for
> a musl-style general stack limit guarantee.

On glibc side another issues are glob and fnmatch.  On glob side it is
mainly due to GNU extensions, where GLOB_TILDE expands the search path
to potentially large buffers than PATH_MAX and GLOB_BRACE which 
potentially calls glob recursively. GLIBC tries to avoid too much stack
allocation through the stack accountability (through alloca_account), but
it is fragile and hacky seems it requires a lot of boilerplate to manage
buffers. My patchset proposal to refactor it try to use dynarray to
manage buffer, but it does not solve the recursive allocation call
(which in this specific case I think it is a user issue since recursive
is driven the input pattern).

Fnmatch at other side is just subpar algorithm that double allocates the
buffer in wide-character form and it could be avoid with a better
implementation (there are some discussion on BZ#14185).