Stack probe puzzle

Help
3

As @matklad pointed out, the issue is that Linux preserves 256 pages of memory between the stack and heap to prevent stack clashes. However, it’s unclear how the heap was mapped near the stack. This is intriguing since Linux on x86 and arm64 uses a non-legacy memory layout when both the stack and heap grow down (see arch_pick_mmap_layout()).

So they shouldn’t meet unless the stack is overflown.

The answer is in zig’s PageAllocator. It’s trying to increase memory addresses, while mmap() trying to decrease them. First argument to mmap() which is address hint – a preference where to place memory in VA-space.

In most cases hint will be ineffective, because of the following reasons:

  • zig doesn’t use hint of first allocation (hint=0)
  • first allocation happens before zig’s stardart library

After the first allocation, next_hint points to the memory region allocated before zig, making the hint ineffective for subsequent allocations.
You can confirm this using the following command:

$ strace -e trace=mmap ./.zig-cache/o/.../fuzz lsm_forest 11137203625256914804 2
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff83a04000
mmap(0xffff83a05000, 136978432, ...) = 0xffff7b762000
mmap(0xffff83a04000, 4096, ...)      = 0xffff7b761000
mmap(0xffff7b762000, 4096, ...)      = 0xffff7b760000
mmap(0xffff7b761000, 4096, ...)      = 0xffff7b75f000
mmap(0xffff7b760000, 4096, ...)      = 0xffff7b75e000
mmap(0xffff7b75f000, 8192, ...)      = 0xffff7b760000 <-- address increased
mmap(0xffff7b762000, 12288, ...)     = 0xffff7b75c000
mmap(0xffff7b75f000, 20480, ...)     = 0xffff7b757000
mmap(0xffff7b75c000, 40960, ...)     = 0xffff7b74d000
mmap(0xffff7b757000, 77824, ...)     = 0xffff7b73a000
mmap(0xffff7b74d000, 151552, ...)    = 0xffff7b715000
mmap(0xffff7b73a000, 299008, ...)    = 0xffff7b6cc000
mmap(0xffff7b715000, 598016, ...)    = 0xffff7b63a000

But still sometimes this hint can increase allocation pointer if memory range that it points to was already freed, and there is enough space in it. So this explains how heap addresses can clash with stack although Linux tries only to decrease them.

Next, verify that mmap()ing memory near the stack that wasn’t fully allocated yet results in SIGSEGV. Linux refuses to mount physical pages because it breaks the “256 pages rule”.

#include <stdio.h>
#include <stdint.h>
#include <alloca.h>
#include <sys/mman.h>

#define MEGABYTE (1024 * 1024)
#define DEFAULT_STACKSIZE (128 * 1024)
#define PAGE_SIZE 4096

int main() {
    // Reading current stack pointer
    int local_var = 0;
    void *sp = &local_var;
    printf("Current stack pointer: %p\n", sp);

    void *word_aligned_sp = (int *)((size_t)sp & ~( sizeof(int) - 1 ));
    void *page_aligned_sp = (int *)((size_t)sp & ~( PAGE_SIZE - 1 ));

    // Allocating 1 page near stack region
    void *stack_allocated_page = mmap(
        page_aligned_sp - MEGABYTE - DEFAULT_STACKSIZE,
        PAGE_SIZE,
        PROT_READ | PROT_WRITE,
        MAP_ANON | MAP_PRIVATE,
        0,
        0);
    printf("Page allocates at: %p\n", stack_allocated_page);
    printf("Diff with sp: %lu\n", (int64_t)sp - (int64_t)stack_allocated_page);

    // This will generate SIGSEGV
    alloca(512 * 1024);
}

Now you have SIGSEGV without actually overflowing the stack.

I would say it should be fixed in zig standart library, because it seems to me that it trying to fight Linux memory-manager.

10 Likes