alloca() problem

php.internals

Ilia A.

22 years ago
There is a rather nasty crash possible in PHP due to the usage of the alloca() function as can be demonstrated by bug #28064. Simpler bug replication case: php -r ' $a = str_repeat("a", 1024 * 1024 * 6); defined($a); ' The problem is the result of missing checks to determine if alloca() had worked or not. The problem is further compounded by the fact that alloca() is a dangerous function that will not always return NULL on failure, making the return value check unreliable (read alloca manpage excerpt below). In PHP4 this function is only used about 7 times, while PHP5 uses it a little more frequently about 38 times. I think it would be best if do_alloca was made to use emalloc that can safely handle allocation failures. Alloca() is already an emalloc wrapper on Apple, HPUX, Windows, Netware. Excerpt from alloca manpage: NOTES ON THE GNU VERSION Normally, gcc translates calls to alloca by inlined code. This is not done when either the -ansi or the -fno-builtin option is given. But beware! By default the glibc version of <stdlib.h> includes <alloca.h> and that contains the line # define alloca(size) __builtin_alloca (size) with messy consequences if one has a private version of this function. The fact that the code is inlined, means that it is impossible to take the address of this function, or to change its behaviour by linking with a different library. The inlined code often consists of a single instruction adjusting the stack pointer, and does not check for stack overflow. Thus, there is no NULL error return. BUGS The alloca function is machine and compiler dependent. On many systems its implementation is buggy. Its use is discouraged. On many systems alloca cannot be used inside the list of arguments of a function call, because the stack space reserved by alloca would appear on the stack in the middle of the space for the function arguments Ilia

Ard Biesheuvel

22 years ago
Ilia Alshanetsky wrote:
> There is a rather nasty crash possible in PHP due to the usage of the alloca() > function as can be demonstrated by bug #28064. > Simpler bug replication case: > php -r ' $a = str_repeat("a", 1024 * 1024 * 6); defined($a); ' >
The following two fragments will lead to virtually identical code: void foo() { char bar[2048]; ... } and void foo() { char *bar = alloca(2048); .... They both start out by moving the stack pointer down 2k to leave enough room for bar, and they will both crash in a similar way if the stack doesn't have enough room available. I think that not alloca() itself but its improper use is the problem here. Any function will cause a crash if you call it when your stack is full. Just be sensible about when (not to) use it.
-- Ard

Ilia A.

22 years ago
Virtually all current uses involve some form of user input, which means that the user can exploit the problem. When bar[2048] is used to create a buffer of a certain known size that never change, with alloca a buffer of undermined size is created in most cases. The only 'safe' way to use the function would be to put it inside a wrapper that would check the size against some preset limit and based on that determine if alloca or emalloc should be used. The length would also need to be stored to allow the free wrapper to determine if efree() is needed. These safety checks may offset the miniscule speed advantage gained by using alloca anyway, especially when the length is being calculated inside alloca call. Ilia

Sterling Hughes

22 years ago
On Mon, 14 Jun 2004 12:10:46 -0400, Ilia Alshanetsky <ilia@prohost.org> wrote:
> > Virtually all current uses involve some form of user input, which means that > the user can exploit the problem. When bar[2048] is used to create a buffer > of a certain known size that never change, with alloca a buffer of undermined > size is created in most cases. > > The only 'safe' way to use the function would be to put it inside a wrapper > that would check the size against some preset limit and based on that > determine if alloca or emalloc should be used. The length would also need to > be stored to allow the free wrapper to determine if efree() is needed. These > safety checks may offset the miniscule speed advantage gained by using alloca > anyway, especially when the length is being calculated inside alloca call. >
Calling malloc is generally not that expensive as you would hope that the operating system would give you reasonable locality in the cases where i've seen alloca() used. Doing a stack size check is still dangerous, simply because you don't know what has been previously allocated off the stack, nor do you know what will be allocated off the stack further down within the function. Calling do_alloca() to avoid a heap access is a bottom drawer optimization, and yields very little when it comes to improving php's memory usage patterns (as opposed to a fix block allocator)... ie, i agree with ilia - it should just be hosed. -sterling

Andi Gutmans

22 years ago
Ilia, alloca() is very important for the executor loop and functions which where performance is very important (mainly the Zend Engine). I don't see any convincing reason not to use it in the way it is being used today. If there are any specific places you find problematic and want to discuss let me know. Andi At 12:10 PM 6/14/2004 -0400, Ilia Alshanetsky wrote:

Ilia A.

22 years ago
Andi, Well, majority of the places where it is used right now can be abused through user input. PHP 4/5: overly long constant names defined(str_repeat("a", 1024 * 1024 * 6)); PHP5: overly long class & method names PHP5: overly long function name PHP5/Interbase: too many arguments passed to some functions. PHP5/pcntl: too many arguments passed to pcntl_exec() PHP5/wddx: long datetime field. PHP5/SOAP: some instances where length is could be too long (if request/response is doctored) Ilia On June 15, 2004 06:10 pm, you wrote:

Ard Biesheuvel

22 years ago
Ilia Alshanetsky wrote:
> PHP5/Interbase: too many arguments passed to some functions.
The function in question alloca()tes a 4 pointers times the number of args which is kept in an unsigned short. This means the allocated memory can at most be 1M. While this seems a lot to allocate on the stack, I think it shouldn't be problem.
-- Ard

Hartmut Holzgraefe

22 years ago
Ard Biesheuvel wrote:
> Ilia Alshanetsky wrote: > >> PHP5/Interbase: too many arguments passed to some functions. > > > The function in question alloca()tes a 4 pointers times the number of > args which is kept in an unsigned short. This means the allocated memory > can at most be 1M. > > While this seems a lot to allocate on the stack, I think it shouldn't be > problem. >
Even when running threaded in ZTS mode? Per thread stacks are not necessarily that big ...
-- Hartmut Holzgraefe <hartmut@php.net>

Ilia A.

22 years ago
On June 16, 2004 12:15 pm, Ard Biesheuvel wrote:
> Ilia Alshanetsky wrote: > > PHP5/Interbase: too many arguments passed to some functions. > > The function in question alloca()tes a 4 pointers times the number of > args which is kept in an unsigned short. This means the allocated memory > can at most be 1M. > > While this seems a lot to allocate on the stack, I think it shouldn't be > problem.
True, but if PHP is as an apache module several simultaneous call could very well exhaust the stack. Ilia

Sterling Hughes

22 years ago
So, oddly enough while responding to this, gmail is showing me Zend advertisements - just thought you should know you are getting your money's worth :) I'll buy that alloca() is harmless in the places the executor uses it (*), php segvs on highly recursive functions, worrying about overly long function names won't keep anyone up at night. But the real issue is the other areas ilia mentions, where it just isn't worth it. -Sterling (*) Although I think its a bottom drawer optimization that something like the Zend optimizer invalidates. On Wed, 16 Jun 2004 01:10:16 +0300, Andi Gutmans <andi@zend.com> wrote:

Andi Gutmans

22 years ago
At 08:45 AM 6/16/2004 -0700, Sterling Hughes wrote:
>I'll buy that alloca() is harmless in the places the executor uses it >(*), php segvs on highly recursive functions, worrying about overly >long function names won't keep anyone up at night. But the real issue >is the other areas ilia mentions, where it just isn't worth it. > >-Sterling >(*) Although I think its a bottom drawer optimization that something >like the Zend optimizer invalidates.
Nope, the Zend optimizer can't invalidate that because in any case, emalloc() of Ts vs. alloca() of Ts is slower no matter what you optimize. As I suggested, I think we should look at this on a case to case basis. Any places which don't require alloca() and/or aren't sort functions which return immediately but may lead to a deep function call stack (besides the executor) should be thought about. Nothing urgent though and as I'm on vacation it might take me a while to answer although I'm trying to check email on a daily basis. Andi

Andi Gutmans

22 years ago
At 07:39 AM 6/16/2004 -0400, Ilia Alshanetsky wrote:
>Andi, > >Well, majority of the places where it is used right now can be abused through >user input. > >PHP 4/5: overly long constant names defined(str_repeat("a", 1024 * 1024 * 6)); >PHP5: overly long class & method names >PHP5: overly long function name
I don't quite understand how this can be abused by user input (unless maybe the developer is doing something very weird). In class/method/function names alloca() is important because of the strtolower() which is crucial for performance. Allocating dynamic memory each time sucks. Then again we could add an extra if() and use a static buffer if the name is reasonable length but I'm not sure it's worth the effort and uglier code.
>PHP5/Interbase: too many arguments passed to some functions. >PHP5/pcntl: too many arguments passed to pcntl_exec() >PHP5/wddx: long datetime field. >PHP5/SOAP: some instances where length is could be too long (if >request/response is doctored)
These places might benefit from going to emalloc(). They should like places which are slow anyway so I'm not sure the extra allocation would be a big deal. Thanks for the overview. Andi