bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andy Wingo]

Hello,

The following transcript indicates a problem with the stack growth
direction check, present at functions.m4:328 in autoconf 2.68:

  wingo@badger:/tmp$ cat foo.c 
  int
  find_stack_direction ()
  {
    static char *addr = 0;
    auto char dummy;
    if (addr == 0)
      {
        addr = &dummy;
        return find_stack_direction ();
      }
    else
      return (&dummy > addr) ? 1 : -1;
  }

  int
  main ()
  {
    return find_stack_direction () < 0;
  }
  wingo@badger:/tmp$ gcc -O1 -o test foo.c
  wingo@badger:/tmp$ ./test; echo $?
  1
  wingo@badger:/tmp$ gcc -O3 -o test foo.c
  wingo@badger:/tmp$ ./test; echo $?
  0
  $ gcc --version
  gcc (Debian 4.6.0-13) 4.6.1 20110611 (prerelease)
  Copyright (C) 2011 Free Software Foundation, Inc.
  This is free software; see the source for copying conditions.  There is NO
  warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

As you see, the check (on an x86-64 system) gives the correct result at
-O1 but not at -O3.

(I don't actually use this check from _AC_LIBOBJ_ALLOCA, but Guile has
the exact same test to check for stack growth direction, so it's the
same issue.  Reported by Marco Maggi.)

Looking a bit more closely at this, I find the assembly to be a bit odd
here:

    00000000004004a0 <find_stack_direction>:
      4004a0:	mov    0x2003f9(%rip),%rax        # 6008a0 <addr.1586>
      4004a7:	test   %rax,%rax
      4004aa:	je     4004c0 <find_stack_direction+0x20>
      4004ac:	lea    -0x2(%rsp),%rdx
      4004b1:	cmp    %rdx,%rax
      4004b4:	sbb    %eax,%eax
      4004b6:	and    $0x2,%eax
      4004b9:	sub    $0x1,%eax
      4004bc:	retq   
      4004bd:	nopl   (%rax)
      4004c0:	lea    -0x2(%rsp),%rax
      4004c5:	lea    -0x1(%rsp),%rdx
      4004ca:	cmp    %rdx,%rax
      4004cd:	mov    %rax,0x2003cc(%rip)        # 6008a0 <addr.1586>
      4004d4:	sbb    %eax,%eax
      4004d6:	and    $0x2,%eax
      4004d9:	sub    $0x1,%eax
      4004dc:	retq   
      4004dd:	nop
      4004de:	nop
      4004df:	nop

As you can see there is no call.  The test will always be true, thus the
second branch is always taken.  I don't know what allows GCC to do this
inlining.  Could it be a GCC bug?  Every time I think I have a GCC bug
I'm wrong, though :)

I tried changing the test to the following:

  int
  find_stack_direction (char *addr)
  {
    char dummy;
    if (addr == 0)
      return find_stack_direction (&dummy);
    else
      return (&dummy > addr) ? 1 : -1;
  }

  int
  main ()
  {
    return find_stack_direction (0) < 0;
  }

But I get the same behavior.

Andy
-- 
http://wingolog.org/

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andrew W. Nosenko]

On Fri, Jun 17, 2011 at 13:21, Andy Wingo <wingo@pobox.com> wrote:
> Hello,
>
> The following transcript indicates a problem with the stack growth
> direction check, present at functions.m4:328 in autoconf 2.68:
>
>  wingo@badger:/tmp$ cat foo.c
>  int
>  find_stack_direction ()
>  {
>    static char *addr = 0;

Try to rewrite this line as
        volatile static char *addr = 0;
It should help.

>    auto char dummy;
>    if (addr == 0)
>      {
>        addr = &dummy;
>        return find_stack_direction ();
>      }
>    else
>      return (&dummy > addr) ? 1 : -1;
>  }
>
>  int
>  main ()
>  {
>    return find_stack_direction () < 0;
>  }


>  wingo@badger:/tmp$ gcc -O1 -o test foo.c
>  wingo@badger:/tmp$ ./test; echo $?
>  1
>  wingo@badger:/tmp$ gcc -O3 -o test foo.c
>  wingo@badger:/tmp$ ./test; echo $?
>  0
>  $ gcc --version
>  gcc (Debian 4.6.0-13) 4.6.1 20110611 (prerelease)
>  Copyright (C) 2011 Free Software Foundation, Inc.
>  This is free software; see the source for copying conditions.  There is NO
>  warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
>
> As you see, the check (on an x86-64 system) gives the correct result at
> -O1 but not at -O3.
>
> (I don't actually use this check from _AC_LIBOBJ_ALLOCA, but Guile has
> the exact same test to check for stack growth direction, so it's the
> same issue.  Reported by Marco Maggi.)
>
> Looking a bit more closely at this, I find the assembly to be a bit odd
> here:
>
>    00000000004004a0 <find_stack_direction>:
>      4004a0:   mov    0x2003f9(%rip),%rax        # 6008a0 <addr.1586>
>      4004a7:   test   %rax,%rax
>      4004aa:   je     4004c0 <find_stack_direction+0x20>
>      4004ac:   lea    -0x2(%rsp),%rdx
>      4004b1:   cmp    %rdx,%rax
>      4004b4:   sbb    %eax,%eax
>      4004b6:   and    $0x2,%eax
>      4004b9:   sub    $0x1,%eax
>      4004bc:   retq
>      4004bd:   nopl   (%rax)
>      4004c0:   lea    -0x2(%rsp),%rax
>      4004c5:   lea    -0x1(%rsp),%rdx
>      4004ca:   cmp    %rdx,%rax
>      4004cd:   mov    %rax,0x2003cc(%rip)        # 6008a0 <addr.1586>
>      4004d4:   sbb    %eax,%eax
>      4004d6:   and    $0x2,%eax
>      4004d9:   sub    $0x1,%eax
>      4004dc:   retq
>      4004dd:   nop
>      4004de:   nop
>      4004df:   nop
>
> As you can see there is no call.  The test will always be true, thus the
> second branch is always taken.  I don't know what allows GCC to do this
> inlining.  Could it be a GCC bug?  Every time I think I have a GCC bug
> I'm wrong, though :)

No.  It indeed traceable.  Just start from main() and you will have
full trace even with pen and paper.

>
> I tried changing the test to the following:
>
>  int
>  find_stack_direction (char *addr)
>  {
>    char dummy;
>    if (addr == 0)
>      return find_stack_direction (&dummy);
>    else
>      return (&dummy > addr) ? 1 : -1;
>  }
>
>  int
>  main ()
>  {
>    return find_stack_direction (0) < 0;
>  }
>
> But I get the same behavior.

Just because it still traceable :-)  And modern Gcc is smart enough
for do it :-)

-- 
Andrew W. Nosenko <andrew.w.nosenko@gmail.com>

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andy Wingo]

Hi,

On Sat 18 Jun 2011 22:25, "Andrew W. Nosenko" <andrew.w.nosenko@gmail.com> writes:

> On Fri, Jun 17, 2011 at 13:21, Andy Wingo <wingo@pobox.com> wrote:
>>  wingo@badger:/tmp$ cat foo.c
>>  int
>>  find_stack_direction ()
>>  {
>>    static char *addr = 0;
>
> Try to rewrite this line as
>         volatile static char *addr = 0;
> It should help.

It didn't, unfortunately.

This issue can be reproduced on a stock Debian unstable system with
gcc-4.6, btw.

>> I don't know what allows GCC to do this inlining.  Could it be a GCC
>> bug?  Every time I think I have a GCC bug I'm wrong, though :)
>
> No.  It indeed traceable.  Just start from main() and you will have
> full trace even with pen and paper.

Apologies for the ignorant question, but what does "trace" mean? :)

Regards,

Andy
-- 
http://wingolog.org/

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andrew W. Nosenko]

On Sun, Jun 19, 2011 at 22:03, Andy Wingo <wingo@pobox.com> wrote:
> Hi,
>
> On Sat 18 Jun 2011 22:25, "Andrew W. Nosenko" <andrew.w.nosenko@gmail.com> writes:
>
>> On Fri, Jun 17, 2011 at 13:21, Andy Wingo <wingo@pobox.com> wrote:
>>>  wingo@badger:/tmp$ cat foo.c
>>>  int
>>>  find_stack_direction ()
>>>  {
>>>    static char *addr = 0;
>>
>> Try to rewrite this line as
>>         volatile static char *addr = 0;
>> It should help.
>
> It didn't, unfortunately.

You are right.  I marked the underlying char as volatile instead of
the pointer itself.
The proper version seems
    static char* volatile addr;
but ATM I have no compiler around for verify that.

Hope, in 3-4 hours I will have ability to verify my guess and have
proper verified results.

> This issue can be reproduced on a stock Debian unstable system with
> gcc-4.6, btw.
>
>>> I don't know what allows GCC to do this inlining.  Could it be a GCC
>>> bug?  Every time I think I have a GCC bug I'm wrong, though :)
>>
>> No.  It indeed traceable.  Just start from main() and you will have
>> full trace even with pen and paper.
>
> Apologies for the ignorant question, but what does "trace" mean? :)

"Trace" means that you may "a priory" trace/predict the whole control
flow without actual running the code.  Therefore, highly optimizing
compiler may reduce whole function call to the simple constant.  From
your description, Gcc occur smart enough for remove the recursion but
not enough for simplify to the simple constant.


-- 
Andrew W. Nosenko <andrew.w.nosenko@gmail.com>

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andrew W. Nosenko]

On Mon, Jun 20, 2011 at 11:25, Andrew W. Nosenko
<andrew.w.nosenko@gmail.com> wrote:
> On Sun, Jun 19, 2011 at 22:03, Andy Wingo <wingo@pobox.com> wrote:
>> Hi,
>>
>> On Sat 18 Jun 2011 22:25, "Andrew W. Nosenko" <andrew.w.nosenko@gmail.com> writes:
>>
>>> On Fri, Jun 17, 2011 at 13:21, Andy Wingo <wingo@pobox.com> wrote:
>>>>  wingo@badger:/tmp$ cat foo.c
>>>>  int
>>>>  find_stack_direction ()
>>>>  {
>>>>    static char *addr = 0;
>>>
>>> Try to rewrite this line as
>>>         volatile static char *addr = 0;
>>> It should help.
>>
>> It didn't, unfortunately.
>
> You are right.  I marked the underlying char as volatile instead of
> the pointer itself.
> The proper version seems
>    static char* volatile addr;
> but ATM I have no compiler around for verify that.
>

The
    static char* volatile addr;
doesn't help also.

Gcc continues to think that it has rights to inline the inner
find_stack_direction() and messes the check as consequence.

Solution: make Gcc unable to inline the function call.

One of possible ways to achieve it: call the inner through volatile pointer.

typedef int (*func_t)();
int find_stack_direction ();

volatile func_t f = &find_stack_direction;

int
find_stack_direction ()
{
    static char *addr = 0;
    auto char dummy;
    if (addr == 0)
    {
        addr = &dummy;
        return f();
    }
    else
        return (&dummy > addr) ? 1 : -1;
}

int
main ()
{
    int r = find_stack_direction ();
    return r < 0;
}


It's not the single way, but just first that come to minds.

-- 
Andrew W. Nosenko <andrew.w.nosenko@gmail.com>

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Paul Eggert]

Does it work to use the following test program instead?

int
find_stack_direction (char *addr)
{
  char dummy;
  return (! addr ? find_stack_direction (&dummy)
          : addr < &dummy ? 1 : -1);
}

int
main (void)
{
  return find_stack_direction (0) < 0;
}

This, essentially, is the fix I just pushed into the GNU
autoconf trunk, here:

http://git.savannah.gnu.org/cgit/autoconf.git/commit/?id=b1747413a80add0271d6909aecfdc2b638456257

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andy Wingo]

On Sat 18 Jun 2011 23:42, Paul Eggert <eggert@cs.ucla.edu> writes:

> Does it work to use the following test program instead?
>
> int
> find_stack_direction (char *addr)
> {
>   char dummy;
>   return (! addr ? find_stack_direction (&dummy)
>           : addr < &dummy ? 1 : -1);
> }
>
> int
> main (void)
> {
>   return find_stack_direction (0) < 0;
> }

No, this program also exhibits the same incorrect behavior, for purposes
of stack growth checking.

Andy
-- 
http://wingolog.org/

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Paul Eggert]

On 06/19/11 12:01, Andy Wingo wrote:
> No, this program also exhibits the same incorrect behavior, for purposes
> of stack growth checking.

Thanks, I guess we'll have to turn it up a notch.  How about the
following test program?

int
find_stack_direction (int *addr, int depth)
{
  int dir, dummy = 0;
  if (! addr)
    addr = &dummy;
  *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
  dir = depth ? find_stack_direction (addr, depth - 1) : 0;
  return dir + dummy;
}

int
main (int argc, char **argv)
{
  return find_stack_direction (0, argc + !argv + 20) < 0;
}


This program is reflected in my most recent patch, here:

http://git.savannah.gnu.org/cgit/autoconf.git/commit/?id=6cd9f12520b0d6f76d3230d7565feba1ecf29497

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Ralf Wildenhues]

Hello Paul,

* Paul Eggert wrote on Mon, Jun 20, 2011 at 07:35:37AM CEST:
> On 06/19/11 12:01, Andy Wingo wrote:
> > No, this program also exhibits the same incorrect behavior, for purposes
> > of stack growth checking.
> 
> Thanks, I guess we'll have to turn it up a notch.  How about the
> following test program?
> 
> int
> find_stack_direction (int *addr, int depth)
> {
>   int dir, dummy = 0;
>   if (! addr)
>     addr = &dummy;
>   *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
>   dir = depth ? find_stack_direction (addr, depth - 1) : 0;
>   return dir + dummy;
> }
> 
> int
> main (int argc, char **argv)
> {
>   return find_stack_direction (0, argc + !argv + 20) < 0;
> }

If you don't use volatile, the compiler is pretty much free to give you
whatever answer it likes today.  I'm not sure whether it's required to
give the right answer with volatile, given that you're still comparing
pointers that C does not allow you to compare, but the above looks more
obfuscated than the simplest code using volatile would.

Thanks,
Ralf

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Paul Eggert]

On 06/19/11 23:35, Ralf Wildenhues wrote:
> If you don't use volatile, the compiler is pretty much free to give you
> whatever answer it likes today.

It's true that the test relies on undefined behavior, and so the
compiler is free to do whatever it wants, but I don't see how
adding "volatile" helps, for this particular test.  Whatever reasoning
the compiler can do without "volatile", it can also do with "volatile",
for this test.

(I have more confidence in the revised test, because this
time I actually ran it on an x86-64 host with GCC 4.6.0.  :-)

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andrew W. Nosenko]

On Mon, Jun 20, 2011 at 09:50, Paul Eggert <eggert@cs.ucla.edu> wrote:
> On 06/19/11 23:35, Ralf Wildenhues wrote:
>> If you don't use volatile, the compiler is pretty much free to give you
>> whatever answer it likes today.
>
> It's true that the test relies on undefined behavior, and so the
> compiler is free to do whatever it wants, but I don't see how
> adding "volatile" helps, for this particular test.  Whatever reasoning
> the compiler can do without "volatile", it can also do with "volatile",
> for this test.

I just marked a volatile the underlying char instead of the pointer.
I will check the right (as I think) markup and send the result in 3-4 hours.

>
> (I have more confidence in the revised test, because this
> time I actually ran it on an x86-64 host with GCC 4.6.0.  :-)
>
>



-- 
Andrew W. Nosenko <andrew.w.nosenko@gmail.com>

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Andy Wingo]

On Mon 20 Jun 2011 07:35, Paul Eggert <eggert@cs.ucla.edu> writes:

> On 06/19/11 12:01, Andy Wingo wrote:
>> No, this program also exhibits the same incorrect behavior, for purposes
>> of stack growth checking.
>
> Thanks, I guess we'll have to turn it up a notch.  How about the
> following test program?

Works for me.  It's very nasty though :-P

Andy
-- 
http://wingolog.org/

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1236 bytes --]

[adding bug-gnulib]

On 06/19/2011 11:35 PM, Paul Eggert wrote:
> On 06/19/11 12:01, Andy Wingo wrote:
>> No, this program also exhibits the same incorrect behavior, for purposes
>> of stack growth checking.
> 
> Thanks, I guess we'll have to turn it up a notch.  How about the
> following test program?
> 
> int
> find_stack_direction (int *addr, int depth)
> {
>   int dir, dummy = 0;
>   if (! addr)
>     addr = &dummy;
>   *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
>   dir = depth ? find_stack_direction (addr, depth - 1) : 0;
>   return dir + dummy;
> }
> 
> int
> main (int argc, char **argv)
> {
>   return find_stack_direction (0, argc + !argv + 20) < 0;
> }
> 
> 
> This program is reflected in my most recent patch, here:
> 
> http://git.savannah.gnu.org/cgit/autoconf.git/commit/?id=6cd9f12520b0d6f76d3230d7565feba1ecf29497

Hmm, we'll need to backport this improved stack-direction testing to
gnulib and libsigsegv, then, since your previous autoconf patch (which
has been defeated by newer gcc optimization) was lifted from gnulib's
c-stack stack-direction probe.

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Paul Eggert]

On 06/20/11 10:54, Eric Blake wrote:

> Hmm, we'll need to backport this improved stack-direction testing to
> gnulib and libsigsegv, then,

Makes sense.  I just pushed this gnulib patch, to do that part.

Testing this is not something for the fainthearted, as it requires
access to all sorts of strange hosts.  However, it does seem to
defeat GCC 4.6.0's tail-recursion optimization (-O0 through -O4)
on my platform, which is what is wanted.

From 0b27a9d67f2d300bd54e4037bd4df0e329eb4dac Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 20 Jun 2011 14:59:13 -0700
Subject: [PATCH 1/2] c-stack: stop worrying about stack direction

* lib/c-stack.c (find_stack_direction): Remove.
(segv_handler): Don't worry about stack direction growth, as it's
too much of a pain to configure this correctly, given how compilers
are optimizing-away our stack-growth detection code.  Instead, assume
that any access to just before or just after the stack is OK.
* m4/c-stack.m4 (AC_SYS_XSI_STACK_OVERFLOW_HEURISTIC):
Don't require AC_FUNC_ALLOCA; no longer needed.
---
 ChangeLog     |   11 +++++++++++
 lib/c-stack.c |   25 +++----------------------
 m4/c-stack.m4 |    5 ++---
 3 files changed, 16 insertions(+), 25 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 1758d67..d595489 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2011-06-20  Paul Eggert  <eggert@cs.ucla.edu>
+
+	c-stack: stop worrying about stack direction
+	* lib/c-stack.c (find_stack_direction): Remove.
+	(segv_handler): Don't worry about stack direction growth, as it's
+	too much of a pain to configure this correctly, given how compilers
+	are optimizing-away our stack-growth detection code.  Instead, assume
+	that any access to just before or just after the stack is OK.
+	* m4/c-stack.m4 (AC_SYS_XSI_STACK_OVERFLOW_HEURISTIC):
+	Don't require AC_FUNC_ALLOCA; no longer needed.
+
 2011-06-20  Eric Blake  <eblake@redhat.com>
 
 	test-stat: don't allocate PATH_MAX bytes
diff --git a/lib/c-stack.c b/lib/c-stack.c
index 7f0f488..e48b97c 100644
--- a/lib/c-stack.c
+++ b/lib/c-stack.c
@@ -223,22 +223,6 @@ c_stack_action (void (*action) (int))
 
 #elif HAVE_SIGALTSTACK && HAVE_DECL_SIGALTSTACK && HAVE_STACK_OVERFLOW_HANDLING
 
-/* Direction of the C runtime stack.  This function is
-   async-signal-safe.  */
-
-# if STACK_DIRECTION
-#  define find_stack_direction(ptr) STACK_DIRECTION
-# else
-#  if ! SIGINFO_WORKS || HAVE_XSI_STACK_OVERFLOW_HEURISTIC
-static int
-find_stack_direction (char const *addr)
-{
-  char dummy;
-  return ! addr ? find_stack_direction (&dummy) : addr < &dummy ? 1 : -1;
-}
-#  endif
-# endif
-
 # if SIGINFO_WORKS
 
 /* Handle a segmentation violation and exit.  This function is
@@ -266,17 +250,14 @@ segv_handler (int signo, siginfo_t *info,
   if (0 < info->si_code)
     {
       /* If the faulting address is within the stack, or within one
-         page of the stack end, assume that it is a stack
-         overflow.  */
+         page of the stack, assume that it is a stack overflow.  */
       ucontext_t const *user_context = context;
       char const *stack_base = user_context->uc_stack.ss_sp;
       size_t stack_size = user_context->uc_stack.ss_size;
       char const *faulting_address = info->si_addr;
-      size_t s = faulting_address - stack_base;
       size_t page_size = sysconf (_SC_PAGESIZE);
-      if (find_stack_direction (NULL) < 0)
-        s += page_size;
-      if (s < stack_size + page_size)
+      size_t s = faulting_address - stack_base + page_size;
+      if (s < stack_size + 2 * page_size)
         signo = 0;
 
 #   if DEBUG
diff --git a/m4/c-stack.m4 b/m4/c-stack.m4
index d613fa8..8d34048 100644
--- a/m4/c-stack.m4
+++ b/m4/c-stack.m4
@@ -7,11 +7,10 @@
 
 # Written by Paul Eggert.
 
-# serial 12
+# serial 13
 
 AC_DEFUN([AC_SYS_XSI_STACK_OVERFLOW_HEURISTIC],
-  [# for STACK_DIRECTION
-   AC_REQUIRE([AC_FUNC_ALLOCA])
+  [
    AC_REQUIRE([AC_CANONICAL_HOST])
    AC_CHECK_FUNCS_ONCE([setrlimit])
    AC_CHECK_HEADERS_ONCE([ucontext.h])
-- 
1.7.4.4


From 61fe84158820aeffed6c64c4e839e18a14a1bf45 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 20 Jun 2011 15:03:03 -0700
Subject: [PATCH 2/2] alloca: port to compilers that can optimize like GCC
 4.6.0

* lib/alloca.c (find_stack_direction): New signature, taken from
Autoconf git.  This works with GCC 4.6.0.  This code should never
be used with GCC 4.6.0 itself, as GCC has alloca, but it might
be used with other compilers that optimize as well as GCC 4.6.0 does.
(alloca): Adjust to new signature.
* m4/alloca.m4 (__AC_LIBOBJ_ALLOCA) [Autoconf version < 2.69]:
New macro, which patches Autoconf in a similar way.
---
 ChangeLog    |    9 ++++++
 lib/alloca.c |   31 ++++++----------------
 m4/alloca.m4 |   79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 96 insertions(+), 23 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index d595489..967c8b7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
 2011-06-20  Paul Eggert  <eggert@cs.ucla.edu>
 
+	alloca: port to compilers that can optimize like GCC 4.6.0
+	* lib/alloca.c (find_stack_direction): New signature, taken from
+	Autoconf git.  This works with GCC 4.6.0.  This code should never
+	be used with GCC 4.6.0 itself, as GCC has alloca, but it might
+	be used with other compilers that optimize as well as GCC 4.6.0 does.
+	(alloca): Adjust to new signature.
+	* m4/alloca.m4 (__AC_LIBOBJ_ALLOCA) [Autoconf version < 2.69]:
+	New macro, which patches Autoconf in a similar way.
+
 	c-stack: stop worrying about stack direction
 	* lib/c-stack.c (find_stack_direction): Remove.
 	(segv_handler): Don't worry about stack direction growth, as it's
diff --git a/lib/alloca.c b/lib/alloca.c
index 2f5e27e..c7e91ab 100644
--- a/lib/alloca.c
+++ b/lib/alloca.c
@@ -93,25 +93,15 @@ long i00afunc ();
 static int stack_dir;           /* 1 or -1 once known.  */
 #   define STACK_DIR    stack_dir
 
-static void
-find_stack_direction (char **ptr)
+static int
+find_stack_direction (int *addr, int depth)
 {
-  auto char dummy;              /* To get stack address.  */
-
-  if (*ptr == NULL)
-    {                           /* Initial entry.  */
-      *ptr = ADDRESS_FUNCTION (dummy);
-
-      find_stack_direction (ptr);  /* Recurse once.  */
-    }
-  else
-    {
-      /* Second entry.  */
-      if (ADDRESS_FUNCTION (dummy) > *ptr)
-        stack_dir = 1;          /* Stack grew upward.  */
-      else
-        stack_dir = -1;         /* Stack grew downward.  */
-    }
+  int dir, dummy = 0;
+  if (! addr)
+    addr = &dummy;
+  *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
+  dir = depth ? find_stack_direction (addr, depth - 1) : 0;
+  return dir + dummy;
 }
 
 #  endif /* STACK_DIRECTION == 0 */
@@ -154,10 +144,7 @@ alloca (size_t size)
 
 #  if STACK_DIRECTION == 0
   if (STACK_DIR == 0)           /* Unknown growth direction.  */
-    {
-      char *addr = NULL;        /* Address of first `dummy', once known.  */
-      find_stack_direction (&addr);
-    }
+    STACK_DIR = find_stack_direction (NULL, (size & 1) + 20);
 #  endif
 
   /* Reclaim garbage, defined as all alloca'd storage that
diff --git a/m4/alloca.m4 b/m4/alloca.m4
index 689da75..891fc8b 100644
--- a/m4/alloca.m4
+++ b/m4/alloca.m4
@@ -1,4 +1,4 @@
-# alloca.m4 serial 11
+# alloca.m4 serial 12
 dnl Copyright (C) 2002-2004, 2006-2007, 2009-2011 Free Software Foundation,
 dnl Inc.
 dnl This file is free software; the Free Software Foundation
@@ -42,3 +42,80 @@ AC_DEFUN([gl_FUNC_ALLOCA],
 # Prerequisites of lib/alloca.c.
 # STACK_DIRECTION is already handled by AC_FUNC_ALLOCA.
 AC_DEFUN([gl_PREREQ_ALLOCA], [:])
+
+# This works around a bug in autoconf <= 2.68.
+# See <http://lists.gnu.org/archive/html/bug-gnulib/2011-06/msg00277.html>.
+
+m4_version_prereq([2.69], [] ,[
+
+# This is taken from the following Autoconf patch:
+# http://git.savannah.gnu.org/cgit/autoconf.git/commit/?id=6cd9f12520b0d6f76d3230d7565feba1ecf29497
+
+# _AC_LIBOBJ_ALLOCA
+# -----------------
+# Set up the LIBOBJ replacement of `alloca'.  Well, not exactly
+# AC_LIBOBJ since we actually set the output variable `ALLOCA'.
+# Nevertheless, for Automake, AC_LIBSOURCES it.
+m4_define([_AC_LIBOBJ_ALLOCA],
+[# The SVR3 libPW and SVR4 libucb both contain incompatible functions
+# that cause trouble.  Some versions do not even contain alloca or
+# contain a buggy version.  If you still want to use their alloca,
+# use ar to extract alloca.o from them instead of compiling alloca.c.
+AC_LIBSOURCES(alloca.c)
+AC_SUBST([ALLOCA], [\${LIBOBJDIR}alloca.$ac_objext])dnl
+AC_DEFINE(C_ALLOCA, 1, [Define to 1 if using `alloca.c'.])
+
+AC_CACHE_CHECK(whether `alloca.c' needs Cray hooks, ac_cv_os_cray,
+[AC_EGREP_CPP(webecray,
+[#if defined CRAY && ! defined CRAY2
+webecray
+#else
+wenotbecray
+#endif
+], ac_cv_os_cray=yes, ac_cv_os_cray=no)])
+if test $ac_cv_os_cray = yes; then
+  for ac_func in _getb67 GETB67 getb67; do
+    AC_CHECK_FUNC($ac_func,
+		  [AC_DEFINE_UNQUOTED(CRAY_STACKSEG_END, $ac_func,
+				      [Define to one of `_getb67', `GETB67',
+				       `getb67' for Cray-2 and Cray-YMP
+				       systems. This function is required for
+				       `alloca.c' support on those systems.])
+    break])
+  done
+fi
+
+AC_CACHE_CHECK([stack direction for C alloca],
+	       [ac_cv_c_stack_direction],
+[AC_RUN_IFELSE([AC_LANG_SOURCE(
+[AC_INCLUDES_DEFAULT
+int
+find_stack_direction (int *addr, int depth)
+{
+  int dir, dummy = 0;
+  if (! addr)
+    addr = &dummy;
+  *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
+  dir = depth ? find_stack_direction (addr, depth - 1) : 0;
+  return dir + dummy;
+}
+
+int
+main (int argc, char **argv)
+{
+  return find_stack_direction (0, argc + !argv + 20) < 0;
+}])],
+	       [ac_cv_c_stack_direction=1],
+	       [ac_cv_c_stack_direction=-1],
+	       [ac_cv_c_stack_direction=0])])
+AH_VERBATIM([STACK_DIRECTION],
+[/* If using the C implementation of alloca, define if you know the
+   direction of stack growth for your system; otherwise it will be
+   automatically deduced at runtime.
+	STACK_DIRECTION > 0 => grows toward higher addresses
+	STACK_DIRECTION < 0 => grows toward lower addresses
+	STACK_DIRECTION = 0 => direction of growth unknown */
+@%:@undef STACK_DIRECTION])dnl
+AC_DEFINE_UNQUOTED(STACK_DIRECTION, $ac_cv_c_stack_direction)
+])# _AC_LIBOBJ_ALLOCA
+])
-- 
1.7.4.4

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Ralf Wildenhues]

* Paul Eggert wrote on Tue, Jun 21, 2011 at 12:19:25AM CEST:
> Testing this is not something for the fainthearted, as it requires
> access to all sorts of strange hosts.  However, it does seem to
> defeat GCC 4.6.0's tail-recursion optimization (-O0 through -O4)
> on my platform, which is what is wanted.

It would be good to make sure GCC 4.6 whole program/link time
optimization doesn't defeat this (I haven't checked).

Thanks,
Ralf

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Paul Eggert]

On 06/21/11 12:43, Ralf Wildenhues wrote:
> It would be good to make sure GCC 4.6 whole program/link time
> optimization doesn't defeat this

It doesn't, at least, not on my platform (Fedora 14 x86-64 + GCC 4.6.0).

Re: bug in check for stack growth direction in _AC_LIBOBJ_ALLOCA

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 784 bytes --]

On 06/17/2011 04:21 AM, Andy Wingo wrote:
>   wingo@badger:/tmp$ gcc -O1 -o test foo.c
>   wingo@badger:/tmp$ ./test; echo $?
>   1
>   wingo@badger:/tmp$ gcc -O3 -o test foo.c
>   wingo@badger:/tmp$ ./test; echo $?
>   0

If I understand correctly, 0 is a correct result, just not optimal.

Improvements for getting the optimal result in spite of gcc
optimizations are welcome (the more we can determine at compile time,
the less work we have to do at runtime), but any correctly written
program should already handle the case of an indeterminate compile-time
probe (the probe should return 1 or -1 for known directions, and 0 for
undetermined direction).

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]