Need help understanding segmented stack and stack splitting

[Rob Thornton]

I've been searching as best I can but most search attempts ended up with
results about: stack data structures, stack overflow (the website) or
stacks as they relate to groups of objects in video games. Not very helpful.

I did come across this article from Ian Lance Taylor on the gcc wiki which
talks about an implementation: http://gcc.gnu.org/wiki/SplitStacks but it
didn't really answer much for me.

I also came across this article by Dave Cheney but it raised as many
questions as it answered:
http://dave.cheney.net/2013/06/02/why-is-a-goroutines-stack-infinite

When a Go program starts, it's my understanding that the OS allocates an
amount of stack space (between 1-8mb, typically, depending on the
OS/architecture). In a single thread if a program requests more stack space
but the frame pointer would exceed the stack segment then the result would
be a stack overflow. However, in Go a new stack would be created on the
heap to prevent this from happening. If you continually straddle this
boundary between the heap allocated stack and the "true" system allocated
stack, it would be called stack splitting?

I have read http://golang.org/doc/faq#goroutines but it's not clear
specifically what is meant by a segmented stack. Is a segmented stack
having one or more heap allocated stacks on top of the system allocated
stack or is it how goroutines have their own mini-stack segments?

I'm very (emphasis on VERY) new to assembly but my understanding is that
the stack pointer is an internal CPU register. When a stack overflow would
occur and the program responds by requesting more stack space from the
heap, must the stack pointer now be maintained by the Go program rather
than a CPU register? This would be an assembly based stack data structure
(linked list)? Or I am I way off base now?

[Ian Lance Taylor]

Post by Rob Thornton
When a Go program starts, it's my understanding that the OS allocates an
amount of stack space (between 1-8mb, typically, depending on the
OS/architecture). In a single thread if a program requests more stack space
but the frame pointer would exceed the stack segment then the result would
be a stack overflow. However, in Go a new stack would be created on the heap
to prevent this from happening. If you continually straddle this boundary
between the heap allocated stack and the "true" system allocated stack, it
would be called stack splitting?

The "stack splitting" is the allocation of the stack on the heap.
When that happens, the stack has been split. This does not happen in
a conventional C program.

Note that Go normally does not run on the system allocated thread
stack, but always runs on its own heap allocated stacks. Note also
that for 1.3 we are likely to switch to growable stacks, in which the
stack is grown as needed but not normally split except perhaps in some
special cases.

Post by Rob Thornton
I have read http://golang.org/doc/faq#goroutines but it's not clear
specifically what is meant by a segmented stack. Is a segmented stack having
one or more heap allocated stacks on top of the system allocated stack or is
it how goroutines have their own mini-stack segments?

Goroutines always use heap allocated stacks.

Post by Rob Thornton
I'm very (emphasis on VERY) new to assembly but my understanding is that the
stack pointer is an internal CPU register. When a stack overflow would occur
and the program responds by requesting more stack space from the heap, must
the stack pointer now be maintained by the Go program rather than a CPU
register? This would be an assembly based stack data structure (linked
list)? Or I am I way off base now?

The stack pointer is a register. When a goroutine splits the stack,
it updates the stack pointer. So, yes, the stack pointer is
maintained by the Go program, and, yes, the stack pointer is a CPU
register. The two statements are not incompatible.

Ian

[Rob Thornton]

Thank you, Ian this clears up most of my confusion on the subject. I do
have a couple more points I hope you can clear up for me.

Post by Rob Thornton

Post by Rob Thornton
When a Go program starts, it's my understanding that the OS allocates an
amount of stack space (between 1-8mb, typically, depending on the
OS/architecture). In a single thread if a program requests more stack

space

Post by Rob Thornton
but the frame pointer would exceed the stack segment then the result

would

Post by Rob Thornton
be a stack overflow. However, in Go a new stack would be created on the

heap

Post by Rob Thornton
to prevent this from happening. If you continually straddle this

boundary

Post by Rob Thornton
between the heap allocated stack and the "true" system allocated stack,

it

Post by Rob Thornton
would be called stack splitting?

The "stack splitting" is the allocation of the stack on the heap.
When that happens, the stack has been split. This does not happen in
a conventional C program.
Note that Go normally does not run on the system allocated thread
stack, but always runs on its own heap allocated stacks. Note also
that for 1.3 we are likely to switch to growable stacks, in which the
stack is grown as needed but not normally split except perhaps in some
special cases.

Regarding Go normally only using the heap allocated stack, do you mind my
asking why you wouldn't utilize any of the thread based stack? I am
assuming you're making a trade off between wasting said memory and
complexity?

Post by Rob Thornton

Post by Rob Thornton
I have read http://golang.org/doc/faq#goroutines but it's not clear
specifically what is meant by a segmented stack. Is a segmented stack

having

Post by Rob Thornton
one or more heap allocated stacks on top of the system allocated stack

or is

Post by Rob Thornton
it how goroutines have their own mini-stack segments?

Goroutines always use heap allocated stacks.

Post by Rob Thornton
I'm very (emphasis on VERY) new to assembly but my understanding is that

the

Post by Rob Thornton
stack pointer is an internal CPU register. When a stack overflow would

occur

Post by Rob Thornton
and the program responds by requesting more stack space from the heap,

must

Post by Rob Thornton
the stack pointer now be maintained by the Go program rather than a CPU
register? This would be an assembly based stack data structure (linked
list)? Or I am I way off base now?

The stack pointer is a register. When a goroutine splits the stack,
it updates the stack pointer. So, yes, the stack pointer is
maintained by the Go program, and, yes, the stack pointer is a CPU
register. The two statements are not incompatible.

After reading your answer I felt quite foolish because the answer should
have been clear.

Post by Rob Thornton
Ian

[Aram Hăvărneanu]

Post by Rob Thornton
Regarding Go normally only using the heap allocated stack, do you
mind my asking why you wouldn't utilize any of the thread based
stack?

There is no other stack. The runtime creates threads passing them
a pointer to an already allocated block of memory to use for their
stacks. That block of memory comes from the heap (an exception is
obviously made for the initial thread of a program, which's stack
is controlled by the operating system). This stack is used for g0,
the scheduler stack. It's also used on Windows and Solaris for
making system calls (in reality just calls into a C library).

Post by Rob Thornton
After reading your answer I felt quite foolish because the answer
should have been clear.

Just a note, Go programs manipulate the stack pointer, but every C
program does as well.

[Dave Cheney]

Post by Rob Thornton
Thank you, Ian this clears up most of my confusion on the subject. I do
have a couple more points I hope you can clear up for me.

Post by Rob Thornton

Post by Rob Thornton
When a Go program starts, it's my understanding that the OS allocates

an

Post by Rob Thornton
amount of stack space (between 1-8mb, typically, depending on the
OS/architecture). In a single thread if a program requests more stack

space

Post by Rob Thornton
but the frame pointer would exceed the stack segment then the result

would

Post by Rob Thornton
be a stack overflow. However, in Go a new stack would be created on the

heap

Post by Rob Thornton
to prevent this from happening. If you continually straddle this

boundary

Post by Rob Thornton
between the heap allocated stack and the "true" system allocated stack,

it

Post by Rob Thornton
would be called stack splitting?

The "stack splitting" is the allocation of the stack on the heap.
When that happens, the stack has been split. This does not happen in
a conventional C program.
Note that Go normally does not run on the system allocated thread
stack, but always runs on its own heap allocated stacks. Note also
that for 1.3 we are likely to switch to growable stacks, in which the
stack is grown as needed but not normally split except perhaps in some
special cases.

Regarding Go normally only using the heap allocated stack, do you mind my
asking why you wouldn't utilize any of the thread based stack? I am
assuming you're making a trade off between wasting said memory and
complexity?

In addition to what Aram has said it is important to emphasise that memory
is not wasted if it is not used.

Ie, in C if I malloc 8mb of memory from the heap essentially nothing
happens. You get a pointer, but the operating system generally defers
actually satisfying that request until you start to read or write to that
memory range. The larger the requested allocation, the more the operating
system will delay fulfilling the promise until absolutely necessary.

Post by Rob Thornton

Post by Rob Thornton

Post by Rob Thornton
I have read http://golang.org/doc/faq#goroutines but it's not clear
specifically what is meant by a segmented stack. Is a segmented stack

having

Post by Rob Thornton
one or more heap allocated stacks on top of the system allocated stack

or is

Post by Rob Thornton
it how goroutines have their own mini-stack segments?

Goroutines always use heap allocated stacks.

Post by Rob Thornton
I'm very (emphasis on VERY) new to assembly but my understanding is

that the

Post by Rob Thornton
stack pointer is an internal CPU register. When a stack overflow would

occur

Post by Rob Thornton
and the program responds by requesting more stack space from the heap,

must

Post by Rob Thornton
the stack pointer now be maintained by the Go program rather than a CPU
register? This would be an assembly based stack data structure (linked
list)? Or I am I way off base now?

The stack pointer is a register. When a goroutine splits the stack,
it updates the stack pointer. So, yes, the stack pointer is
maintained by the Go program, and, yes, the stack pointer is a CPU
register. The two statements are not incompatible.

After reading your answer I felt quite foolish because the answer should
have been clear.

Post by Rob Thornton
Ian

[Rob Thornton]

Thanks Aram and Dave. I think answers all my original questions!

One last curiousity:

Dave, in your article you stated that a goroutine has a 4096 byte stack. Is
this because it is the typical page size for most operating systems? In the
case of SPARC, where I believe the page size is doubled to 8192 bytes,
would the stack size be increased to match?

Post by Dave Cheney

Post by Rob Thornton
Thank you, Ian this clears up most of my confusion on the subject. I do
have a couple more points I hope you can clear up for me.

Post by Rob Thornton

Post by Rob Thornton
When a Go program starts, it's my understanding that the OS allocates

an

Post by Rob Thornton
amount of stack space (between 1-8mb, typically, depending on the
OS/architecture). In a single thread if a program requests more stack

space

Post by Rob Thornton
but the frame pointer would exceed the stack segment then the result

would

Post by Rob Thornton
be a stack overflow. However, in Go a new stack would be created on

the heap

Post by Rob Thornton
to prevent this from happening. If you continually straddle this

boundary

Post by Rob Thornton
between the heap allocated stack and the "true" system allocated

stack, it

Post by Rob Thornton
would be called stack splitting?

The "stack splitting" is the allocation of the stack on the heap.
When that happens, the stack has been split. This does not happen in
a conventional C program.
Note that Go normally does not run on the system allocated thread
stack, but always runs on its own heap allocated stacks. Note also
that for 1.3 we are likely to switch to growable stacks, in which the
stack is grown as needed but not normally split except perhaps in some
special cases.

Regarding Go normally only using the heap allocated stack, do you mind my
asking why you wouldn't utilize any of the thread based stack? I am
assuming you're making a trade off between wasting said memory and
complexity?

In addition to what Aram has said it is important to emphasise that memory
is not wasted if it is not used.
Ie, in C if I malloc 8mb of memory from the heap essentially nothing
happens. You get a pointer, but the operating system generally defers
actually satisfying that request until you start to read or write to that
memory range. The larger the requested allocation, the more the operating
system will delay fulfilling the promise until absolutely necessary.

Post by Rob Thornton

Post by Rob Thornton

Post by Rob Thornton
I have read http://golang.org/doc/faq#goroutines but it's not clear
specifically what is meant by a segmented stack. Is a segmented stack

having

Post by Rob Thornton
one or more heap allocated stacks on top of the system allocated stack

or is

Post by Rob Thornton
it how goroutines have their own mini-stack segments?

Goroutines always use heap allocated stacks.

Post by Rob Thornton
I'm very (emphasis on VERY) new to assembly but my understanding is

that the

Post by Rob Thornton
stack pointer is an internal CPU register. When a stack overflow would

occur

Post by Rob Thornton
and the program responds by requesting more stack space from the heap,

must

Post by Rob Thornton
the stack pointer now be maintained by the Go program rather than a

CPU

Post by Rob Thornton
register? This would be an assembly based stack data structure (linked
list)? Or I am I way off base now?

The stack pointer is a register. When a goroutine splits the stack,
it updates the stack pointer. So, yes, the stack pointer is
maintained by the Go program, and, yes, the stack pointer is a CPU
register. The two statements are not incompatible.

After reading your answer I felt quite foolish because the answer should
have been clear.

Post by Rob Thornton
Ian

[Aram Hăvărneanu]

The goroutine stack size is 8kB now, not 4kB as before. This means
that each stack uses 8kB of address space. Most goroutines still
only use 4kB of physical memory though. The operating system will
only map the second page when it faults as the user (code) tries
to access it the first time.

On a potential SPARC, goroutines would probably start with 8kB
stacks which would use 8k of physical memory, as the page size is
8kB. There's no requirement that stack size be a multiple of page
size, however, it can be smaller. The operating system will map
memory in page-size increments, but the Go memory allocator can
allocate space for stacks of any size.

It's no different than amd64 2MB pages. A single 2MB page can back
many stack segments; stack segments can be very small.

[Rob Thornton]

Excellent, thank you very much Aram!

Rob

Post by Aram Hăvărneanu
The goroutine stack size is 8kB now, not 4kB as before. This means
that each stack uses 8kB of address space. Most goroutines still
only use 4kB of physical memory though. The operating system will
only map the second page when it faults as the user (code) tries
to access it the first time.
On a potential SPARC, goroutines would probably start with 8kB
stacks which would use 8k of physical memory, as the page size is
8kB. There's no requirement that stack size be a multiple of page
size, however, it can be smaller. The operating system will map
memory in page-size increments, but the Go memory allocator can
allocate space for stacks of any size.
It's no different than amd64 2MB pages. A single 2MB page can back
many stack segments; stack segments can be very small.
--
Aram Hăvărneanu