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.
The term "stack" is overloaded. Some possible interpretations include:
- 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.
- 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.
- 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.
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.