0

I am running Arch Linux, 64bit latest update on one of my computers. I am currently a Computer Science student and we had a test yesterday where we were to implement a dynamic stack using linked lists. I am now interested in learning how the stack in my computer is built, however I am unable to find any "stack.c" with comments on my Arch Linux computer. Where is the stack programming located? I understand how the stack creates memory but I want to actually see the code and maybe play around with it myself.

8
  • 2
    stack is a concept I guess every program that need it would program it. in a compiled C (or whatever) program "stack" refer to stacked address of function called. – Archemar Feb 4 at 14:16
  • 2
    Depending on the platform “the stack” is a hardware concept. – phg Feb 4 at 14:38
  • 1
    The stack is used to manage the args and return address of functions when they are called. So the code to manage the stack cannot be implemented as library functions -- they can't be called to make a stack frame to call themselves. The stack frame is essentially a construct of how the compiler emits assembler/machine code in response to a C function call (and also to how it destroys each frame after use). – Paul_Pedant Feb 4 at 16:29
  • 1
    @Archemar Good comment on the ambiguity. Stack for user data is just a data collection that implements LIFO (last in, first out), using an array or a linked list. The "Execution stack" is a very specific LIFO for nesting function calls, with exact specifications for specific architectures. – Paul_Pedant Feb 4 at 23:26
  • 1
    cseducators.stackexchange.com/q/6788/8837 may be useful... Which links to stackoverflow.com/q/19351451/3700414 – Rusi Feb 17 at 3:20
6

The term "stack" is overloaded. Some possible interpretations include:

  1. A "stack" is an abstraction over a set of data structures that provide Last-In-First-Out (LIFO) access to the elements that it contains.
  2. There are realizations of the "stack" abstraction. The linked-list based stack that you developed in your class is one such realization. It is not the only realization. For example, it's also possible to build a stack using an array.
  3. The runtime activation stack --- the stack used to manage function calls and returns during the execution of a thread in a program --- is another realization of the "stack" abstraction. It's behavior is similar to an array-based stack.

In terms of (3) a "chunk" of memory is allocated to each running thread in a program. As functions get called and return within those thread, they push and pop "stack frames" ("elements" on the runtime activation stack) from the stack that is associated with thread. The specifics of what is contained within a stack frame differ between hardware architectures. In general, stack frames contain:

  • The return address of the the caller
  • Some or all of the parameters to the function (depends on the hardware architecture, the number of parameters, and their size)
  • Local variables defined within the function.
  • The state of registers that are used by the function, but whose values need to be restored before the function returns.

Because the number of parameters, the number and size of the local variables within a function, and what registers need to be saved differ from function to function, stack frames do not have a constant size.

There is no stack.c to examine because the code that manages the activation record stack is generated by the compilers that build programs on a function-by-function basis. Compilers generate the instructions to trigger function calls. As the compiler produces a program's instructions, it knows:

  • What hardware instruction is used to trigger a function call, and what affect that instruction has on the stack (e.g., does it automatically store the return address, does it adjust the register that tracks the "top" of the stack).
  • If any parameters in the call are stored on the stack, where those parameters will be in terms of the "top" of the stack.
  • The size of the local variables within the function, and location of those variables in relation to the "top" of the stack (and the compiler uses this to adjust the register that keeps track of the "top" of the stack).
  • The registers the function is using and when they need to be saved/restored
  • What hardware instruction is used to trigger a return from a function call, and what affect that instruction has on the stack.

Compilers follow a well-established set of rules (calling conventions) for the hardware architecture so that programs composed of different pieces built by different compilers can interoperate.

Note that although the runtime activation stack (3) is a realization of the "stack" abstraction (1), aside from the concept of pushing/popping records, it bear little resemblance to a linked-based implementation.

0

As mentioned already, a stack is a generic data type, there are likely a number of stack implementations on any given general-purpose OS. There is no single stack that would be the stack, unless perhaps you're a system level programmer, in which case the hardware call stack is probably it. Maybe.

OpenSSL has a stack.h, the library implements a stack data structure. Perhaps that is the one you found. C++ also has a standard container std::stack. (The file might be called just stack, which on my Linux refers to stl_stack.h.) Usually you wouldn't have the source code files for libraries installed, since they are of no use to someone who is not in the task of modifying that library. Even the headers are only needed to compile something that uses the library.

3
  • Then what allocates memory for my variables in a program? If I create a C program that defined "int x = 5;", it is stored in the stack. What allocates memory, stores the variable in the memory and later retrieves it as well as pops it of the stack? You and other people here are saying "there is no 'one true stack'", I get that. I am looking for "A stack, any stack really" that is professionally made on my linux system. My guess is one of those stacks do the things I ask questions about in this comment. – linker Feb 7 at 17:57
  • What allocates memory, stores the variable in the memory and later retrieves it as well as pops it off the stack? The running program, as generated by the compiler. – Andy Dalton Feb 7 at 17:59
  • 3
    "What allocates memory, stores the variable in the memory and later retrieves it as well as pops it off the stack?" -- Variables can be stored in memory even without a stack. But if we're talking about local variables to a function, then it's the code generated by the compiler that deals with that. Partly using CPU instructions made for stack manipulation, or at least a CPU register dedicated for just that. Also, if we're talking function calls, the platform-specific ABI comes into play. That's a somewhat different kind of stack than one you'd implement yourself with linked lists. – ilkkachu Feb 7 at 18:15

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.