0

I have looked in several places such as here but none explain in detail the structs used for implementing the stack itself (the place where "tasks" (processes/threads) store their nested call information and such). Is it a linked list, or is it an array, or something else? I can't seem to find this information, but diagrammatically they always show it as a large memory block (virtual memory) where the beginning is the heap and the end is the stack. But this is virtual memory we're dealing with, which has all kinds of data structures around it such as pagination. So the question is what exactly is the implementation of the stack on top of all this? I can't help but think it must be a linked list.

The reason is, if you have multiple processes each with their own stack, how is this implemented?

Here we seem to be getting somewhere:

Each process has its own stack for use when it is running in the kernel; in current kernels, that stack is sized at either 8KB or (on 64-bit systems) 16KB of memory. The stack lives in directly-mapped kernel memory, so it must be physically contiguous.

  • 1
    A stack is neither a linked list nor an array - it's a stack (FILO). – Panki Dec 3 '19 at 8:57
  • Getting Somewhere" is not true. User processes have their stack in user-space: you can find the standard process stack allocation using ulimit -a. My Linux Mint shows 8192 KB (8 MB). The stack for a user process in the kernel is used only for the top part of the stack when it has already invoked a system call. That's why it is so small -- kernel routines don't stack very deeply. – Paul_Pedant Dec 5 '19 at 0:20
  • "Multiple processes with their own stack?" Processes have their own memory, protected from access by other user processes. Their stack is just part of that memory, no different to static memory or heap. It has its own dedicated register (SP) which is saved (with a lot of other stuff) whenever a process switch occurs. – Paul_Pedant Dec 5 '19 at 14:04
  • OK, the stack for a user process in kernel space has to be physically contiguous because the kernel does not participate in virtual memory. The process's own stack has entirely contiguous addresses in process space, but not in physical memory. For any page that is swapped out, it has NO physical address memory anyway; if it gets swapped in, the virtual memory is mapped to give the illusion that the contiguous process space looks correct, even though the physical pages are not adjacent. Nothing special about stack there either. – Paul_Pedant Dec 5 '19 at 14:11
1

A stack is effectively an array -- it contains a bunch of words in contiguous memory, There is an important restriction -- it can only grow and shrink at one end (hence FILO -- First In Last Out) which is also LIFO.

Important difference from array too: Processor stack is logically split into Frames, and (unlike arrays), each frame can be a different size from any of the others.

Each frame contains what needs to be stored when you make a function call, including:

  • The return address where the called function jumps, to continue in the calling function.
  • Space to hold any return value.
  • A copy of each parameter being passed to the called function.
  • Copies of the CPU registers, so that the register optimisation in the separate functions don't interfere.

If you ever wondered how a function can recurse and yet use the same names for all its parameters and local variables in each level, the answer is that all of them have addresses relative to their current stack frame.

The stack frame structure is defined differently for each processor architecture, to adopt the most natural way of storing things. There isn't a "Linux" stack -- Intel and AMD and Sparc will all have their own definition. Remember you can download pre-compiled libraries that your local compiler has to know how to call from your own code.

A Stack is also a generic data structure in its own right. For example, if you are parsing the source of a language like C or SQL or XML that allows nested block constructs, then it is natural to make a stack of the blocks you are inside as you go. You wouldn't want to do that using the process stack: it's the thing you are parsing that has block structures, not your own code that needs to recurse.

The stack for each process is just a part of its user process memory. Typically, the user address space runs from -8MB to 0 to (say) 60MB. The stack starts at -16 and grows downwards (increasingly negative). Global and static memory assigned by the compiler is upwards from 0, and any heap allocation grows above the fixed memory. The code is somewhere separate (for protection reasons). It doesn't do the virtual storage system any harm to map your negative address range into paged memory.

| improve this answer | |
  • Is the user-process memory stack contiguous or a linked list? – Lance Pollard Dec 5 '19 at 3:08
  • The user-process stack is contiguous memory (my first sentence) and has sequential word addresses (which may be ascending or descending). It also cannot (in most OS) be extended while a process is running. That would be very difficult to do, because it would need to be a system call, which would itself need a stack frame to be added to the stack you want to extend. And if it failed, you would also need a stack frame to call something to report the failure. Not going there. – Paul_Pedant Dec 5 '19 at 13:59
  • 1
    Stacks do grow, without a system call — accessing a page below the current stack causes a page fault, and the kernel grows the stack. If it can’t, it indicates failure using SIGSEGV; processes which expect to handle that need to set up an alternate stack beforehand, using sigaltstack. – Stephen Kitt Dec 6 '19 at 11:22
  • Seems to be true in Linux, not necessarily in Unix. There was an errno for something like ESTACKOFLOW last time I used DEC-Alpha, HP-UX and NT. In any case, automatic stack extension just means realising another VM page, until it violates ulimit stack_size. If that is unlimited, it carries on until vm_size, or until the system kills the process as OOM. Even saying base grows up from 0 and stack grows down from ~0 is a fudge: they are just different virtual mapping into real memory, unless and until you actually consume the quintillion bytes in between them. – Paul_Pedant Dec 6 '19 at 21:26
  • 1
    The question is specifically about Linux, I focused on that. My experience on other OSs is that overflowing the stack also leads to SIGSEGV or its equivalent; perhaps you’re thinking of EOVERFLOW, but that’s not used for stack overflows. You’re right about the meaning of growing the stack, but note that on Linux at least the stack can’t grow to vm_size: the kernel won’t grow the stack if it would overwrite something else, and you’ll hit the mmap area first. – Stephen Kitt Dec 9 '19 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.