Why does a stack overflow occur at varying stack usage each run instead of a fixed amount?

Question

I am running a program with a recursive call on a Debian OS. My stack size is

-s: stack size (kbytes)             8192

As far as I've learned, the stack size must be fixed, and should be the same that must be allocated to a program at every run unless it is explicitly changed with ulimit.

The recursive function is a decrements a given number until it reaches 0. This is written in Rust.

fn print_till_zero(x: &mut i32) {
    *x -= 1;
    println!("Variable is {}", *x);
    while *x != 0 {
        print_till_zero(x);
    }
}

and the value is passed as

static mut Y: i32 = 999999999;
unsafe {
    print_till_zero(&mut Y);
}

Since the stack allocated to the program is fixed, and theoretically must not change, I was expecting a stack overflow at the same value each time, but it is not, which means the stack allocation is variadic.

Run 1:

====snip====
Variable is 999895412
Variable is 999895411

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Run 2:

====snip====
Variable is 999895352
Variable is 999895351

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Although the difference is subtle, shouldn't it be ideally causing the stack overflow at the same variable? Why is it happening at different times, implying different stack size for each run? This is not specific to Rust; a similar behavior is observed in C:

#pragma GCC push_options
#pragma GCC optimize ("O0")
#include<stdio.h>
void rec(int i){
    printf("%d,",i);
    rec(i-1);
    fflush(stdout);
}
int main(){
setbuf(stdout,NULL);
rec(1000000);
}
#pragma GCC pop_options

Output:

Run 1:

738551,738550,[1]    7052 segmentation fault

Run 2:

738438,738437,[1]    7125 segmentation fault

Overflow will only happen when the stack page-faults. That is when the stack pointer runs into an unloaded / unowned page. Where the stack starts need not be on a exact page boundary but can depend on where the program is loaded so the overflow condition (page fault) trigger will be different. — Richard Critten, Mar 24 '17 at 07:11
Does [this](http://stackoverflow.com/questions/31180563/why-are-stackoverflow-errors-chaotic) look similar? — Art, Mar 24 '17 at 07:16
@RichardCritten So any page outside the allocated stack size must be an unowned page right? Please correct me if I'm wrong. — nohup, Mar 24 '17 at 07:16
It will depends on which way the stack grows. It might grow into your program static data or heap. This will depend on architecture and implementation details. For example the implementer may place a guard-page at the end of the stack frame. We are very close to Undefined Behaviour is Undefined Behaviour and any explanation will need the target hardware and implementation details. — Richard Critten, Mar 24 '17 at 07:30
For your Rust implementation, you don't need to declare a **static** mutable. A local variable would work just as well, avoiding the need for `unsafe` code as well. — Shepmaster, Mar 24 '17 at 13:22

score 16 · Accepted Answer · edited May 23 '17 at 10:30

16

Most probably this is due to ASLR.

The base address of the stack is randomized at each run to make certain types of exploits more difficult; on Linux this has a granularity of 16 bytes (which is the biggest alignment requirement on x86 and almost any other platform I know).

On the other hand, the page size is (normally) 4 KB on x86, and the system detects the stack overflow when you touch the first forbidden page; this means that you'll always have available a partial page first (with the offset depending from ASLR), and then two full pages before the system detects a stack overflow. Hence the total usable stack size is at least the 8192 bytes you requested, plus the first partial page, whose available size is different at each run.¹

All this in the "regular" case where the offset is nonzero; if you are very lucky and the random offset is zero you probably get exactly two pages.

edited May 23 '17 at 10:30

Community

1
1

answered Mar 24 '17 at 07:17

Matteo Italia

123,740
17
206
299

16 bytes is actually the most restrictive alignment requirement on x86 AFAIK. – Matteo Italia Mar 24 '17 at 07:27
sorry I accidentally deleted my comment, so adding it here again. I was asking, if stack is randomized, shouldn't it be aligned to the page for efficient access? Thank you for the update. – nohup Mar 24 '17 at 07:30
1

It only need to be aligned for the most restrictive data type. – Richard Critten Mar 24 '17 at 07:35
1

As I said, it's enough that it's 16 byte aligned (so the most picky SSE types can be pushed correctly aligned); page boundaries aren't particularly interesting for quick stack access - stack is accessed virtually at every offset (sensible for the target type) during execution, where it begins doesn't hold much importance as long as it is aligned. – Matteo Italia Mar 24 '17 at 07:36
4

Verified it by disabling `ASLR` in `/proc/sys/kernel/randomize_va_space` and the result is consistent now. Thanks again. – nohup Mar 24 '17 at 07:53
3

@nohup just in case you didn't re-enable ASLR after testing, you definitely should. ASLR is a key security protection and shouldn't be disabled. – Shepmaster Mar 24 '17 at 13:23
1

Thank you @Shepmaster. I've enabled it back.I was learning a bit of systems programming, and was just curious. – nohup Mar 24 '17 at 16:38

Why does a stack overflow occur at varying stack usage each run instead of a fixed amount?

1 Answers1