[x86] Access off the bottom of stack causes a segfault?

[x86] Access off the bottom of stack causes a segfault?

[Chris Lattner]

My compiler is generating accesses off the bottom of the stack (address
below %esp).  Is there some funny kernel interaction that I should be
aware of with this?  I'm periodically getting segfaults.

Example:

int main() {
   int test[4000];
...
   return 0;
}

Generated code:
        .intel_syntax
...
main:
        mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
        mov %EBP, %ESP                        # Set up EBP
        sub %ESP, 16004                       # Finally adjust ESP
        lea %EAX, DWORD PTR [%EBP - 16000]    # Get the address of the array
...
        mov %EAX, 0                           # Setup return value
        mov %ESP, %EBP                        # restore ESP
        mov %EBP, DWORD PTR [%ESP - 16004]    # Restore EBP from stack
        ret

This seems like perfectly valid X86 code (though unconventional), but it
is causing segfaults pretty consistently (on the first instruction).
Does the linux kernel assume that page faults will be above the stack
pointer if the stack needs to be expanded?

Thanks,

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [x86] Access off the bottom of stack causes a segfault?

[Davide Libenzi]

On Tue, 14 Oct 2003, Chris Lattner wrote:

>
> My compiler is generating accesses off the bottom of the stack (address
> below %esp).  Is there some funny kernel interaction that I should be
> aware of with this?  I'm periodically getting segfaults.
>
> Example:
>
> int main() {
>    int test[4000];
> ...
>    return 0;
> }
>
> Generated code:
>         .intel_syntax
> ...
> main:
>         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
                         ^^^^^^^^^^^^

Yes, this is the problem (even Windows does that IIRC).



- Davide

Re: [x86] Access off the bottom of stack causes a segfault?

[Chris Lattner]

> > Generated code:
> >         .intel_syntax
> > ...
> > main:
> >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
>                          ^^^^^^^^^^^^
>
> Yes, this is the problem (even Windows does that IIRC).

Ok, I realize what's going on here.  The question is, why does the linux
kernel consider this to be a bug?  Where (in the X86 specs) is it
documented that it's illegal to access off the bottom of the stack?

My compiler does a nice leaf function optimization where it does not even
bother to adjust the stack for leaf functions, which eliminates the adds
and subtracts entirely from these (common) functions.  This completely
invalidates the optimization.

Since I'm going to have to live with lots of preexisting kernels, it looks
like I'm going to have to disable it entirely, which is disappointing.
I'm still curious though why this is thought to be illegal.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [x86] Access off the bottom of stack causes a segfault?

[Davide Libenzi]

On Tue, 14 Oct 2003, Chris Lattner wrote:

> > > Generated code:
> > >         .intel_syntax
> > > ...
> > > main:
> > >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
> >                          ^^^^^^^^^^^^
> >
> > Yes, this is the problem (even Windows does that IIRC).
>
> Ok, I realize what's going on here.  The question is, why does the linux
> kernel consider this to be a bug?  Where (in the X86 specs) is it
> documented that it's illegal to access off the bottom of the stack?
>
> My compiler does a nice leaf function optimization where it does not even
> bother to adjust the stack for leaf functions, which eliminates the adds
> and subtracts entirely from these (common) functions.  This completely
> invalidates the optimization.
>
> Since I'm going to have to live with lots of preexisting kernels, it looks
> like I'm going to have to disable it entirely, which is disappointing.
> I'm still curious though why this is thought to be illegal.

I don't know, I didn't code it :) I discovered it a few months ago while I
was doing some portable code to measure the maximum stack growth of our
software. I was doing something like:

	memset(%esp - SAFE, 'S', SIZE);

and it was puking on me on both Linux and Windows. An alloca+memset solved
the problem in both environments.



- Davide

Re: [x86] Access off the bottom of stack causes a segfault?

[Richard B. Johnson]

On Tue, 14 Oct 2003, Chris Lattner wrote:

> > > Generated code:
> > >         .intel_syntax
> > > ...
> > > main:
> > >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
> >                          ^^^^^^^^^^^^
> >
> > Yes, this is the problem (even Windows does that IIRC).
>
> Ok, I realize what's going on here.  The question is, why does the linux
> kernel consider this to be a bug?  Where (in the X86 specs) is it
> documented that it's illegal to access off the bottom of the stack?
>
> My compiler does a nice leaf function optimization where it does not even
> bother to adjust the stack for leaf functions, which eliminates the adds
> and subtracts entirely from these (common) functions.  This completely
> invalidates the optimization.
>
> Since I'm going to have to live with lots of preexisting kernels, it looks
> like I'm going to have to disable it entirely, which is disappointing.
> I'm still curious though why this is thought to be illegal.
>
> -Chris

Any interrupt causes the return address to be pushed onto the
stack. This will overwrite any data you've put there. In principle,
in user-mode, you can write below the stack-pointer because an
interrupt uses the kernel stack. However, your data will still
get corrupted by signal delivery, etc. So as to not corrupt your
user-mode stack, the kernel calls your signal code, just like
a nested call. This means the new return address will be below
the non-signal user-mode stack-pointer value. This will surely
corrupt anything you have written below the stack-pointer.


Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: [x86] Access off the bottom of stack causes a segfault?

[Chris Lattner]

> Any interrupt causes the return address to be pushed onto the
> stack. This will overwrite any data you've put there. In principle,
> in user-mode, you can write below the stack-pointer because an
> interrupt uses the kernel stack. However, your data will still
> get corrupted by signal delivery, etc. So as to not corrupt your
> user-mode stack, the kernel calls your signal code, just like
> a nested call. This means the new return address will be below
> the non-signal user-mode stack-pointer value. This will surely
> corrupt anything you have written below the stack-pointer.

Thanks to everyone for all of the answers. :)  I guess the moral of the
story is to not perform leaf function optimization on X86.  At least
frame-pointer elimination is still safe.

Thanks again,

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [x86] Access off the bottom of stack causes a segfault?

[Jamie Lokier]

Chris Lattner wrote:
> Thanks to everyone for all of the answers. :)  I guess the moral of the
> story is to not perform leaf function optimization on X86.  At least
> frame-pointer elimination is still safe.

Chris,

You _can_ do the leaf optimisation, but you have to be more careful.

Firstly, you'll need to use sigaltstack() to ensure signals are not
delivered on the current stack.

Secondly, you'll need to install a SIGSEGV signal handler which
detects when the kernel doesn't like you accessing below %esp, and
forces the vma to expand by manipulating %esp and doing some accesses,
then returns.

-- Jamie

Re: [x86] Access off the bottom of stack causes a segfault?

[Mikael Pettersson]

Chris Lattner writes:
 > > > Generated code:
 > > >         .intel_syntax
 > > > ...
 > > > main:
 > > >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
 > >                          ^^^^^^^^^^^^
 > >
 > > Yes, this is the problem (even Windows does that IIRC).
 > 
 > Ok, I realize what's going on here.  The question is, why does the linux
 > kernel consider this to be a bug?  Where (in the X86 specs) is it
 > documented that it's illegal to access off the bottom of the stack?

Signal handlers.

 > My compiler does a nice leaf function optimization where it does not even
 > bother to adjust the stack for leaf functions, which eliminates the adds
 > and subtracts entirely from these (common) functions.  This completely
 > invalidates the optimization.

The common definition of a leaf function is one that does
not need an activation record. Whether you call another
function or not is immaterial, it's the stack allocation
that counts. Your code is using an implicit activation
record, which, as you've found out, doesn't work.

If you desperately need to clobber below %esp (which is a bug
except on x86-64) then you can use sigaltstack() and SA_ONSTACK
in sigaction() to force signal handlers off your stack. Doing
this safely requires C library specific hacks. (Why? Because
not all sigaction() calls are in _your_ code, typically.)

Re: [x86] Access off the bottom of stack causes a segfault?

[Brian Gerst]

Chris Lattner wrote:

>My compiler is generating accesses off the bottom of the stack (address
>below %esp).  Is there some funny kernel interaction that I should be
>aware of with this?  I'm periodically getting segfaults.
>
>Example:
>
>int main() {
>   int test[4000];
>...
>   return 0;
>}
>
>Generated code:
>        .intel_syntax
>...
>main:
>        mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
>        mov %EBP, %ESP                        # Set up EBP
>        sub %ESP, 16004                       # Finally adjust ESP
>        lea %EAX, DWORD PTR [%EBP - 16000]    # Get the address of the array
>...
>        mov %EAX, 0                           # Setup return value
>        mov %ESP, %EBP                        # restore ESP
>        mov %EBP, DWORD PTR [%ESP - 16004]    # Restore EBP from stack
>        ret
>
>This seems like perfectly valid X86 code (though unconventional), but it
>is causing segfaults pretty consistently (on the first instruction).
>Does the linux kernel assume that page faults will be above the stack
>pointer if the stack needs to be expanded?
>
>Thanks,
>
>-Chris
>
>  
>
 From arch/i386/mm/fault.c:
                /*
                 * accessing the stack below %esp is always a bug.
                 * The "+ 32" is there due to some instructions (like
                 * pusha) doing post-decrement on the stack and that
                 * doesn't show up until later..
                 */
                if (address + 32 < regs->esp)
                        goto bad_area;

--
                Brian Gerst

Re: [x86] Access off the bottom of stack causes a segfault?

[Chris Lattner]

On Tue, 14 Oct 2003, Chris Lattner wrote:
> Generated code:
>         .intel_syntax
> ...
> main:
>         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
>         mov %EBP, %ESP                        # Set up EBP
>         sub %ESP, 16004                       # Finally adjust ESP
>         lea %EAX, DWORD PTR [%EBP - 16000]    # Get the address of the array
> ...
>         mov %EAX, 0                           # Setup return value
>         mov %ESP, %EBP                        # restore ESP
>         mov %EBP, DWORD PTR [%ESP - 16004]    # Restore EBP from stack
>         ret

Ok, I found my own "answer": arch/i386/mm/fault.c:

                /*
                 * accessing the stack below %esp is always a bug.
                 * The "+ 32" is there due to some instructions (like
                 * pusha) doing post-decrement on the stack and that
                 * doesn't show up until later..
                 */
                if (address + 32 < regs->esp)
                        goto bad_area;

Why exactly is accessing the stack below %esp always a bug?

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [x86] Access off the bottom of stack causes a segfault?

[Petr Vandrovec]

On Tue, Oct 14, 2003 at 01:49:04PM -0500, Chris Lattner wrote:
> On Tue, 14 Oct 2003, Chris Lattner wrote:
> > Generated code:
> >         .intel_syntax
> > ...
> > main:
> >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
> >         mov %EBP, %ESP                        # Set up EBP
> >         sub %ESP, 16004                       # Finally adjust ESP
> >         lea %EAX, DWORD PTR [%EBP - 16000]    # Get the address of the array
> > ...
> >         mov %EAX, 0                           # Setup return value
> >         mov %ESP, %EBP                        # restore ESP
> >         mov %EBP, DWORD PTR [%ESP - 16004]    # Restore EBP from stack
> >         ret
> 
> Ok, I found my own "answer": arch/i386/mm/fault.c:
> 
>                 /*
>                  * accessing the stack below %esp is always a bug.
>                  * The "+ 32" is there due to some instructions (like
>                  * pusha) doing post-decrement on the stack and that
>                  * doesn't show up until later..
>                  */
>                 if (address + 32 < regs->esp)
>                         goto bad_area;
> 
> Why exactly is accessing the stack below %esp always a bug?

Any signal can overwrite any value stored below %esp. In kernel
any interrupt/exception can overwrite any value stored below %esp.
Your compiler is broken....
							Petr Vandrovec

Re: [x86] Access off the bottom of stack causes a segfault?

[Chris Lattner]

> > Why exactly is accessing the stack below %esp always a bug?
>
> Any signal can overwrite any value stored below %esp. In kernel
> any interrupt/exception can overwrite any value stored below %esp.
> Your compiler is broken....

Ah, ok.  That makes sense.  Thanks!

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [x86] Access off the bottom of stack causes a segfault?

[Richard B. Johnson]

On Tue, 14 Oct 2003, Chris Lattner wrote:

>
> My compiler is generating accesses off the bottom of the stack (address
> below %esp).  Is there some funny kernel interaction that I should be
> aware of with this?  I'm periodically getting segfaults.
>
> Example:
>
> int main() {
>    int test[4000];
> ...
>    return 0;
> }
>
> Generated code:
>         .intel_syntax
> ...
> main:
>         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack

BAM **INTERRUPT** writes return address below stack-pointer.

>         mov %EBP, %ESP                        # Set up EBP
>         sub %ESP, 16004                       # Finally adjust ESP
>         lea %EAX, DWORD PTR [%EBP - 16000]    # Get the address of the array
> ...
>         mov %EAX, 0                           # Setup return value
>         mov %ESP, %EBP                        # restore ESP
>         mov %EBP, DWORD PTR [%ESP - 16004]    # Restore EBP from stack

BAM **You get bad data, overwritten by interrupt**

>         ret
>
> This seems like perfectly valid X86 code (though unconventional), but it
> is causing segfaults pretty consistently (on the first instruction).
> Does the linux kernel assume that page faults will be above the stack
> pointer if the stack needs to be expanded?
>
> Thanks,
>
> -Chris

Well it is perfectly bad code. You can't access data elements
below the stack-pointer because that's where the return address
form interrupts, etc., will go. If you write there, you overwrite
that information, in particular an interrupt overwrites what
you put there. You do 'own' that address space, but you
can't use it in a program.

This script shows how to allocate stack-data without running
into that problem.


#!/bin/bash
#
#  Using only assembly and not any 'C' stuff, this allocates
#  64k on the stack and writes to it.
#
FNAME=/tmp/tmp
cat <<EOF >${FNAME}.S
.section	.text
.global	_start
.type	_start,@function
_start:	pushl	%ebp		# Save
	movl	%esp, %ebp	# Save SP
	subl	\$0x10000,%esp	# 64 k on the stack
	movl	\$0, (%esp)	# Write there
	movl	%ebp, %esp	# Original SP
	popl	%ebp		# Restore
	movl	\$0x01, %eax	# Exit function
	movl	\$0x00, %ebx	# Exit code
	int	\$0x80
1:	jmp	1b		# Hard stop
.end
EOF
as -o ${FNAME}.o ${FNAME}.S
ld -o ${FNAME} ${FNAME}.o
rm -f core
${FNAME}
if [ -f "core" ] ; then echo "Something's bad!" ; else echo "Okay!" ; fi
#

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: [x86] Access off the bottom of stack causes a segfault?

[H. Peter Anvin]

Followup to:  <Pine.LNX.4.53.0310141510590.2211@chaos>
By author:    "Richard B. Johnson" <root@chaos.analogic.com>
In newsgroup: linux.dev.kernel
> 
> > main:
> >         mov DWORD PTR [%ESP - 16004], %EBP    # Save EBP to stack
> 
> BAM **INTERRUPT** writes return address below stack-pointer.
> 

Since we're in user mode, interrupts don't matter, but signals have
the same effect.

Note that this is a matter of the ABI definition.  For example, in the
x86-64 ABI there is a designated region of well-defined size below
%rsp called the redzone, which signals aren't allowed to clobber.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

Re: [x86] Access off the bottom of stack causes a segfault?

[Eric W. Biederman]

Chris Lattner <sabre@nondot.org> writes:

> My compiler is generating accesses off the bottom of the stack (address
> below %esp).  Is there some funny kernel interaction that I should be
> aware of with this?  I'm periodically getting segfaults.

Beyond the signal thing.  You are using a demand grown vma for the
stack, and using it past where it has grown.  If you grow the vma
deliberately you can use more of it.  But using more area than
you have allocated for the stack is most certainly a bug.


Eric