Talk:Call stack

From Wikipedia, the free encyclopedia

You have new messages (last change).
 This article is part of a WikiProject to improve Wikipedia's articles related to Computer science. For guidelines see WikiProject Computer science and Wikipedia:Contributing FAQ.


Contents

[edit] Merging with other wikipedia articles

I disagree with the merging proposal, just put references

  • I also think it's not good to merge this with Subroutine. Subroutine is a basic programming concept whose main audience would be relatively unfamiliar with programming. The stack is an advanced topic about internals related to storage allocation, debugging, compiling, exception handling and other things beyond subroutines. -R. S. Shaw 20:22, 28 July 2005 (UTC)

[edit] Stuff to merge in

If anyone wants to merge, here is a (low quality) article I wrote for our company wiki, which explains how a function stack is managed in detail. It's not yet encyclopedic quality.

The stack of a process is a data structure that manages several things:

  • Storage for lexical variable containers
  • Control flow management, especially the BSR type calls
  • Parameter passing
  • Function return value passing

[edit] Stack Structure

The stack structure is very simple

  • Preallocated memory region
  • Base pointer
  • Stack pointer

The base pointer always stays the same.

It's a LIFO structure - when more data is added to the stack, the stack pointer increases to mark it's end.

When data is removed, the stack pointer decreases.

All data is stored in preallocated space.

[edit] Scopes in the stack

In order to understand the way the stack is used for running high level langauges, two fundamental scoping principals must be understood

[edit] The Lexical Scope

Lexical scoping has to do with the place of definition - what blocks are nested in what other blocks.

It is namespace oriented.

[edit] The Dynamic Scope

Dynamic scoping has to do with the call chain - which function called which other function.

[edit] An example

   int fib (int n) {
       if (n < 2) {
           return n;
       }
       
       return fib(n-1) + fib(n-2);
   }
   
   void foo (int n) {
       int f = fib(n);
       printf("fib(%d) = %d", n, f);
   }

The lexical scopes in this example are illustrated by the fact that each function has it's own lexical variable called <n>.

The dynamic scope is illustrated by the fact that foo calls fib, and fib calls itself.

The stack for these calls is constructed as follows:

  1. foo is called with a number:
    • Space on the stack is allocated for foo's return value
    • A pointer to the instruction after the call to foo is placed on the stack
    • The single parameter to foo is placed on the stack
    • The instruction pointer is set to the address of foo
  2. foo's lexical scope is "entered":
    • space for the integer f is allocated on the stack
  3. fib is called with a number:
    • space on the stack is allocated for fib's return value
    • the pointer to the instruction after the call to fib, in this case the assignment to f is placed on the stack
    • the single parameter to fib, n, is placed on the tack
    • the instruction pointer is set to the address of fib
    • fib checks if the number is smaller than 2
      • If it is
        • The space allocated for fib's return value is set to n
        • fib's storage (parameters, lexical variables) are deleted from the stack
        • the instruction pointer is set to the pointer to the place after the call, as found on the stack
      • If it isn't
        • two callls to fib are made, like illustrated, and the sum of their return values is returned
  4. fib returns a value
  5. the instruction after the call to fib in foo is cleans up the return value, and eventually assigns the value to the space in the variable f (also on the stack)
  6. the a call to printf is made, much like the call to fib
  7. foo's lexical scope is "left"
    • the storage space for 'f' is deleted from the stack

By analyzing this data structure, programs like pstack can look at the pointers to the callers, and the instruction pointer register, and determine the functions the places in the code belong to.

From then on, the function pointers are looked up in the symbol table, and resolved to names. The type information can then be used to unpack the allocated spaces on the stack. If the full core of the program is available, these parameters can be recursively traversed, pretty printed, displayed, and so forth.

Analyzing structures such as the stack is the job of the debugger.

[edit] alloca

Alloca works by dynamically allocating additional arbitrary space on the stack for any purpose. This memory does not need to be deleted, because when the function is left, the stack space will be resused for calls to other functions eventually.

This is also why it's wrong to give any other function data alllocated using alloca.

[edit] Block structures

Lexical variables are allocated in this manner:

   void foo()
   {
       int x;  /* allocates 1*sizeOf(int) on the stack  */
   
       int moose[10];    /* allocates 1*sizeOf(int*) + 10*sizeOf(int) on the stack,  */
                         /* and places the pointer to the 10 ints inside the         */
                         /* one int*                                                 */
   
       for (x = 0; x < 10; x++)
       {
           int y;      /* 1*sizeOf(int) allocated on the stack every time the   */
                       /* loop body is executed                                 */
       
       } /* before the new block the stack end pointer is decremented, and y's space is reused */
   }
   /*    When the function returns, the stack is decremented by 1*sizeOf(int) +  */
   /*    1*sizeOf(int*) + 10*sizeOf(int) here, to account for the lexical        */
   /*    variables (x and moose[10]) in the function's body.                     */
   
   /*    For every call to foo(), x and moose[10] will be allocated and   */
   /*    deallocated once.  y will be allocated and deallocated 10 times  */

[edit] Structural details

The actual structure of the stack varies greatly from platform to platform.

It should be noted that to support things like 'alloca' more annotation on the structure needs to be kept, and the top of the stack frame must be known at all times in order to account for the dynamicity.

These details are beyond the concept illustrated here, and only assembley programmers and compiler/debugger authors should really care about this anyway.

[edit] Stack overflow

The stack has a limited amount of preallocated space.

Scenarios when too much space is needed include

  • Deeply recursive call chains
  • Call chains to functions with large amounts of lexical variable data
  • Heavy use of alloca

When the stack space is exhausted, the program can no longer make calls to functions.

Furthermore, in some situations stack space is needed just to throw an error, so these situations get very ugly very fast.

[edit] Tail Call Optimization

Tail call optimization works by omitting the stack frame of the caller when it is known that the caller will never be needed again. This is morally equivelent to using 'goto' into a function call. This can be applied by certain compilers in scenarios such as this:

   void moose () {
       int x = function_with_no_param();
   }
   
   int function_with_no_param () {
       int default_value = ...;
       return function_with_param(default_value);
   }
   
   int function_with_param (int default_value) {
       ...
       return x;
   }

When function_with_no_param makes the call to function_with_param, the stack frame for function_with_no_param can be thrown away, since there is nothing else for it to do. This can significantly save on stack space. For example, if you were to calculate the length of a linked list as such:

   int length (list) {
       return length_recursive(list, 0);
   }
   
   int length_recursive (list, offset);
       if (is_end(list)) {
           return offset;
       }
       return length_recursive(list->next, offset+1);
   }

and your compiler did tail call optimizations, then this example will use a constant amount of stack space no matter how long the list, somewhat like if you were to do a loop:

   int length (list) {
       int l;
       for (l = 0; !is_end(list); list = list->next) {
           l++;
       }
       return l;
   }

nuffin 12:32, September 12, 2005 (UTC)

[edit] Stack unwinding

The sentence mentioning "stack unwinding" may accurately summarise the stub article, but it not right. Stack unwinding is usually performed in the context of an exception, where control is transferred up the stack. The tricky part is making sure that you destruct and/or deallocate the appropriate objects. For example, see [1] or [2], just the first two hits for a google search on "stack unwinding". There are other contexts, e.g. stack unwinding for C code. So I think that this sentence needs to be removed now, and replaced soon with a proper treatment of "stack unwinding", which I'm sorry to say probably belongs in its own article. --Mike Van Emmerik 11:24, 21 January 2006 (UTC)

Agreed, and the section on winding; The Forth programming language allows explicit winding of the call stack (called there the "return stack"). is completely wrong. Forth doesn't work that way; there's no frame to wind or unwind. Alex 21:49, 28 March 2006 (UTC)

[edit] Moving to 'call stack'

I plan on moving this article to give it the title 'call stack' soon. This is the name by which the stack is usually known, as is made clear by, for instance, this data on Google hits for various exact phrases "X stack":

Phrase Hits Comments
"function stack" 7,620
"call stack" 170,000
"execution stack" 28,000
"control stack" 16,000
"call return stack" 551
"return stack" 23,200 (includes "call/return stack")
"return address stack" 5,280
"address stack" 8,700 (includes return address stack)
"procedure stack" 954
"data stack" 26,600
"parameter stack" 5,260
"frame stack" 7,020
"runtime stack" 11,800 (usually like "runtime stack overflow")

This should be done with a move, not a copy-paste, to preserve the edit history. (that may require help via WP:RM, or maybe not). There'll be a few fixups to do too. -R. S. Shaw 22:11, 16 February 2006 (UTC)

Sounds fine. Anything that makes it clear that the stacks primary purpose is tracking function returns, and not necessarily params/locals, is fine by me. --Mgreenbe 00:48, 17 February 2006 (UTC)


[edit] History

It would be nice to see some material about the history of these concepts. For instance, who came up with the concept (and the name) "activation record". I presume it must have appeared in the first Algol 60 implementation? Tsferreira 17:59, 13 March 2006 (UTC)

[edit] Return processing

In the recently added section "Return processing", the last sentence says essentially that there is typically no cleanup required by the caller. This is true for RISC processors. For CISC processors using PUSH and POP instructions, it is also true for the callee-pop calling convention, but not for the caller-pop convention. Or of course it is trivially true if there happen to be no arguments pushed, or the arguments are passed in registers (but when there are enough parameters, some arguments are passed on the stack anyway).

In other words, there is a large set of programs (CISC architecture, nonzero arguments, and caller-pop convention as used by C) for which this statement is misleading. I can't immediately think of a change that is compact but not misleading. --Mike Van Emmerik 00:42, 9 April 2006 (UTC)

I've revised it to cover this variation. -R. S. Shaw 21:17, 10 April 2006 (UTC)

[edit] Incorrect statement

Article currently reads "The mixing of code (return addresses) and data (parameters, return values) in a call stack is a security risk, possibly exploitable through buffer overflows (in which article the risk and exploitation are explained)."

This is clearly an attempted reference to the exploit of buffer overflows by overwriting return addresses, allowing the exploit to snag control of the process. However, return addresses are not code, so to say "code (return addresses)" is incorrect. Return addresses are data about code, but this is (clearly) not the same thing. I don't think there's a way to fix this without significantly expanding the Security section, or referencing a buffer overflow article. It also might be worth noting that many current architectures don't allow execution of code on the stack (ref W^X, for example), making this even more obviously wrong.

[edit] Evaluation Stack

I'm no true expert, but the call stack (also known as the environmental stack) is a different struture as the evaluation (arithmetic) stack.

It is true, that in some implementation they are mixed together, but this is a conceptual flaw of the implementation.

But as I said, I am no expert. As for my information source: http://www.sbql.pl/Topics/Environment%20stack.html

pl:Quintria

The functions of tracking calls, evaluatating arithmetic expressions, allocating temporary storage to a subroutine, and passing parameters are all separate functions. Each can be addressed by using a stack structure. The stacks used for these functions can all be separate, or can be brought together in any combination. The decision in an implementation to combine any or all of these stacks is an engineering decision, which will have better or worse efficiencies under different conditions. There is nothing conceptually wrong with combining any of these functions into the same stack. The functions are conceptually separate, but implementations can be more effective by combining some or all of them. -R. S. Shaw 18:42, 1 July 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../c/a/l/Talk%7ECall_stack_1187.html"