How is a kernel notified when a process needs new pages for stack frames?

Question

I understand that a MMU on a chip takes virtual addresses and converts them into physical memory address. The MMU does the following:

(1) Consults the page table specific to the process

(2) If page corresponding to the virtual address is in resident set then translates the address into a physical address

(3) If page corresponding to the virtual address is NOT in resident set then generates page fault to be handled by the Kernel

Now, I understand page creation and deletion for several sections of a process require system calls such as brk(), sbrk(), mmap(), and munmap(). So Kernel will always get an opportunity to update the page table of the process whenever these system calls are made.

However a running process may increase the stack area by asking for the stack pointer %rsp to be reduced by 10,000 which may require several pages of allocation to accommodate the increase in stack depth.

If my understanding of MMU is correct above then in case of %rsp change the MMU will not generate a page fault (because the address is not in the process table to begin with). What does the MMU do in this situation to notify the Kernel?

Answer 1

A running process may increase the stack area by asking for the stack pointer %rsp to be reduced by 10,000 which may require several pages of allocation to accommodate the increase in stack depth.

If my understanding of MMU is correct above then in case of %rsp change the MMU will not generate a page fault (because the address is not in the process table to begin with). What does the MMU do in this situation to notify the Kernel?

Changing %rsp never causes pages faults. Page faults only occur when memory is read or written.

Touching unmapped pages will always trigger a page fault, but the kernel's page-fault handler can decide it was a "valid" page-fault and grow the logical mapping + wire the page into the hardware page tables. Or decide it's "invalid" and deliver a SIGSEGV.

Stack growth is a special case. Normally a page fault can only be valid if it's inside an existing mapping (e.g. lazy allocation, copy on write, or the page was paged out to swap space or whatever file is backing it). There are "soft" or "hard" page faults that you get because the logical state of mappings doesn't have to match the hardware page tables. See How is Stack memory allocated when using 'push' or 'sub' x86 instructions? for more details.

Some implementations have a special case to extend the stack mapping. Others do not, and map the entire stack region in advance. Then the page faults will work the same way as for mmap(). Calling mmap() is exactly how pthread stacks are allocated. At least, this is the default when you create a pthread using glibc. By contrast, the stack for the initial thread is created by the kernel, implementing special cases that allow it to grow. For further discussion about how Linux grows stacks, see below.

If you jump over the end of the stack, it is entirely possible you could cause stray accesses into a different mapping. I.e. you can corrupt that memory without triggering any page fault. This is a "stack clash" security vulnerability. Malicious input can make that happen by for example causing a very large alloca or C99 variable-length array to be allocated, making the stack pointer skip over stuff.

The way to guarantee you detect all such stack overflows is to 1) map a "guard page" at the end of the stack 2) probe a page at a time when you allocate stack memory. At the time of writing, GCC does not fully support generating stack probes.

The x86-64 System V ABI does not require stack-probes for correctness in growing the stack by more than 1 page at a time. Hence gcc would only ever emit stack probes if you explicitly told it to. (I think the ABIs Linux uses on most non-x86 architectures are the same.) On Linux, stack probes are only needed to make sure the program faults if trying to grow the stack past the end of the stack size limit.

(Fun fact: Windows does need to touch each page sequentially when allocating a big array on the stack. Compilers targeting Windows do need to always emit stack probes for correctness when moving the stack pointer by more than a page, or by a variable amount that could be larger than a page.)

Why bother growing the stack?

Using a fixed size stack mapping appears to have at least one disadvantage. When you create such a stack using mmap(), although it does not allocate physical memory, Linux counts this as "committed" memory.

By default, Linux allows RAM+swap to be overcommitted, but uses heuristics to refuse "obvious overcommits of address space". When you actually try to use more memory than you have RAM+swap, the "Out Of Memory killer" (OOM) will start choosing running programs to slaughter, until you have enough memory. It is possible to configure different policies, e.g. refuse allocations which would lead to commiting more than RAM/2 + swap.

See vm.overcommit_memory and vm.overcommit_ratio.

This consideration is also mentioned in the Windows blog article below. Perhaps the differences in implementation are one of the contributing factors in complaints about Linux overcommit and the OOM killer :-).

[C runtimes such as glibc] could make most of it initially non-writable/non-readable, and change that on faults, but then you'd need signal handlers and this solution is not acceptable in a POSIX threads implementation because it would interfere with the application's signal handlers. -- User "R.." on StackOverflow

Linux provided an alternative mechanism, MAP_GROWSDOWN. It is mostly equivalent to the quote above, but implemented in the kernel. This is what the kernel uses when creating the initial stack for a process. However, this only really makes sense because Linux also reserves virtual memory for the main stack to grow, up to the value of ulimit -s. Some of the "magic" that makes this work safely + correctly is not available via mmap(MAP_GROWSDOWN), so it's not usable for thread stacks. Otherwise it would be a valid option.

"R.." goes on to suggest a kernel change to support on-demand commit for thread stacks.

Assorted references:

• LLVM on Linux did not implement stack probes. This became a prominent issue for the memory-safe Rust language, which is now resolved ("for all tier-1 platforms").
• Some sources mention that GCC implements stack probes, but only if you pass -fstack-check. "Unfortunately, -fstack-check is actually not well suited for our purposes" for several reasons.
• More recently: "Most targets do not fully support stack clash protection. However, on those targets -fstack-clash-protection will protect dynamic stack allocations. -fstack-clash-protection may also provide limited protection for static stack allocations if the target supports -fstack-check=specific".
• CVE-2010-2240 - where Linux finally realized the need to add a guard page in MAP_GROWSDOWN.
• StackClash in 2017 - where Linux finally realized one page is not enough if you do not have stack probes.
• Obligatory LWN.net article on StackClash.
• Windows' implementation is explained as part of a blog post by Raymond Chen: https://devblogs.microsoft.com/oldnewthing/?p=29563