Skip to content

Instantly share code, notes, and snippets.

@cpq
Last active September 19, 2024 11:01
Show Gist options
  • Save cpq/8598782 to your computer and use it in GitHub Desktop.
Save cpq/8598782 to your computer and use it in GitHub Desktop.
Why stack grows down

Why stack grows down

Any running process has several memory regions: code, read-only data, read-write data, et cetera. Some regions, such as code and read-only data, are static and do not change over time. Other regions are dynamic: they can expand and shrink. Usually there are two such regions: dynamic read-write data region, called heap, and a region called stack. Heap holds dynamic memory allocations, and stack is mostly used for keeping function frames.

Both stack and heap can grow. An OS doesn't know in advance whether stack or heap will be used predominantly. Therefore, an OS must layout these two memory regions in a way to guarantee maximum space for both. And here is the solution:

  1. Layout static memory regions at the edges of process's virtual memory
  2. Put heap and stack on edges too, and let them grow towards each other: one grows up, one grows down

This solution is reflected in a hardware design: most CPUs have support for stack, and it grows down. For example, 32-bit Linux implements this layout in the following way:

  • code, shared libraries and read-only data are mapped at the beginning of the memory
  • then goes heap that grows up
  • kernel is mapped at the last 1G
  • stack starts at kernel's lower boundary and grows down

Here's the simplified illustration of the memory map (Windows uses similar layout):

|---| DLLs | code | data | heap |-->      <---| stack | kernel |
0                                                     3G       4G
(first page is never mapped to catch NULL dereferences)

That is fine for single-threaded programs. Multi-threading requires separate stack for each thread. Therefore, main thread's stack begins at it's usual place - at the kernel boundary. Next thread's stack starts from some offset that defines the maximum stack size of the main thread. Thread API allows to set stack size.

|---| DLLs | code | data | heap |-->    <--| stack 2 |  <--| stack 1 | kernel |
0                                                                    3G      4G

Many threads can consume a lot of virtual space, which can be a problem on 32-bit machine. E.g. a program with 2000 threads, each taking a default of 1M stack size, eats about 2G or virtual memory, leaving very little space for heap. In such case, thread stack size should be reduced.

In the majority of modern architectures, stack grows down. However, there are some processors (e.g. B5000) where stack grows up. Some architecrures (e.g. System Z, RCA1802A) allow to choose stack direction. SEAforth/GreenArrays, SPARC processors have cyclical stack.

Author: Sergey Lyubka, January 2014
Corrected by: Vsevolod Stakhov, January 2014
Corrected by: Peter Sovietov, January 2014

@vikash009
Copy link

Can you give same explanation after swapping the position of heap and stack ? Means stack grows up and heap grows down.

@xujiezhige
Copy link

It’s really useful, Thank you!

@neduard
Copy link

neduard commented Nov 7, 2018

Thanks for the explanation!

@JollyFrogs
Copy link

JollyFrogs commented Feb 2, 2019

The reason that the stack grows down dates back to April 1974 when Intel released its 8080 (8-bit) processor which influenced the design of the first x86 processor, the 8086. The architect of the 8080 processor, Stanley Mazor, explains why the stack was chosen to grow down as follows on the 8080 (which influenced the design of the first x86 processor - the 8086): "The stack pointer was chosen to run 'downhill' (with the stack advancing toward lower memory) to simplify indexing into the stack from the user's program (positive indexing) and to simplify displaying the contents of the stack from a front panel". The reason that modern CPUs (including the x86-64 range of 64-bit processors) still have a stack growing down is because they are of the same x86 architecture as the 8086 and remain backward compatible to the 8086.

@KES777
Copy link

KES777 commented Apr 26, 2019

The original link for that @JollyFrogs quotes: http://tcm.computerhistory.org/ComputerTimeline/Chap37_intel_CS2.pdf

But that quote: to run 'downhill' to simplify indexing into the stack from the user's program does not answer how indexing is simplified

@funnyboys
Copy link

Thanks for sharing, your post is very clear and useful!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment