FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Call stack

In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. (The active subroutines are those which have been called but have not yet completed execution by returning.) This kind of stack is also known as an execution stack, control stack, function stack, or run-time stack, and is often abbreviated to just "the stack". Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ... A computer program is a collection of instructions that describe a task, or set of tasks, to be carried out by a computer. ...


A call stack is often used for several related purposes, but the main reason for having one is to keep track of the point to which each active subroutine should return control when it finishes executing. If, for example, a subroutine DrawSquare calls a subroutine DrawLine from four different places, the code of DrawLine must have a way of knowing which place to return to. This is typically done by code for each call within DrawSquare putting the address of the instruction after the particular call statement (the "return address") into the call stack. In computer science, a memory address is a unique identifier for a memory location at which a CPU or other device can store a piece of data for later retrieval. ... In computer science, an instruction typically refers to a single operation of a processor within a computer architecture. ... A statement is the minimal unit of structuring in imperative programming languages. ... In both conventional and electronic messaging, a return address is an explicit inclusion of the address of the person sending the message. ...


Since the call stack is organized as a stack, the caller pushes the return address onto the stack, and the called subroutine, when it finishes, pops the return address off the call stack (and transfers control to that address). If a called subroutine calls on to yet another subroutine, it will push its return address onto the call stack, and so on, with the information stacking up and unstacking as the program dictates. If the pushing consumes all of the space allocated for the call stack, an error called a stack overflow occurs. Adding a subroutine's entry to the call stack is sometimes called winding; conversely, removing entries is unwinding. Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... A stack overflow occurs when too many functions are called in a computer program. ...


There is usually exactly one call stack associated with a running program (or more accurately, with each task or thread of a process), although additional stacks may be created for signal handling or cooperative multitasking (as with setcontext). Since there is only one in this important context, it can be referred to as the stack (implicitly, "of the task"). A task is an execution path through address space. In other words, a set of program instructions that is loaded in memory. ... A thread in computer science is short for a thread of execution. ... This article or section does not cite its references or sources. ... A signal is an asynchronous event transmitted between one process and another. ... In computing, cooperative multitasking (or non-preemptive multitasking) is a form of multitasking in which multiple tasks execute by voluntarily ceding control to other tasks at programmer-defined points within each task. ... setcontext is one of a family of C library functions (the others being getcontext, makecontext and swapcontext) used for context control. ...


In high-level programming languages, the specifics of the call stack are usually hidden from the programmer. They are given access only to the list of functions, and not the memory on the stack itself. Most assembly languages on the other hand, require programmers to be involved with manipulating the stack. The actual details of the stack in a programming language depend upon the compiler, operating system, and the available instruction set. A high-level programming language is a programming language that, in comparison to low-level programming languages, may be more abstract, easier to use, or more portable across platforms. ... An assembly language is a low-level language used in the writing of computer programs. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... This article is about the computing term. ... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... An instruction set, or instruction set architecture (ISA), describes the aspects of a computer architecture visible to a programmer, including the native datatypes, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O (if any). ...

Contents

Functions of the call stack

As noted above, the primary purpose of a call stack is:

  • Storing the return address – When a subroutine is called, the location of the instruction to return to needs to be saved somewhere. Using a stack to save the return address has important advantages over alternatives. One is that each task has its own stack, and thus the subroutine can be reentrant, that is, can be active simultaneously for different tasks doing different things. Another benefit is that recursion is automatically supported. When a function calls itself recursively, a return address needs to be stored for each activation of the function so that it can later be used to return from the function activation. This capability is automatic with a stack.

A call stack may serve additional functions, depending on the language, operating system, and machine environment. Among them can be: A computer program or routine is described as reentrant if it is designed in such a way that a single copy of the programs instructions in memory can be shared by multiple users or separate processes. ... A common method of simplification is to divide a problem into subproblems of the same type. ...

  • Local data storage – A subroutine frequently needs memory space for storing the values of local variables, the variables that are known only within the active subroutine and do not retain values after it returns. It is often convenient to allocate space for this use by simply moving the top of the stack by enough to provide the space. This is very fast to do compared with, say, a heap allocation. Note that each separate activation of a subroutine gets its own separate space in the stack for locals.
  • Parameter passing – Subroutines often require that values for parameters be supplied to them by the code which calls them, and it is not uncommon that space for these parameters may be laid out in the call stack. Generally if there are only a few small parameters, processor registers will be used to pass the values, but if there are more parameters than can be handled this way, memory space will be needed. The call stack works well as a place for these parameters, especially since each call to a subroutine, which will have differing values for parameters, will be given separate space on the call stack for those values.
  • Evaluation stack – Operands for arithmetic or logical operations are most often placed into register and operated on there. However, in some situations the operands may be stacked up to an arbitrary depth, which means something more than registers must be used. The stack of such operands, rather like that in an RPN calculator, is called an evaluation stack, and may occupy space in the call stack.
  • Pointer to current instance - Some object-oriented languages (e.g., C++), store the this pointer along with function arguments in the call stack when invoking methods. The this pointer points to the object instance to which the method to be invoked to is associated with. The this pointer is an essential part of the execution context in object oriented languages, since it provides access to private data owned by the current object. The this pointer links layers used in object-oriented design with layers (types of stack frames) of the run-time call stack.
  • Enclosing subroutine context - Some programming languages (e.g., Pascal and Ada) support nested subroutines, allowing an inner routine to access the context of its outer enclosing routine, i.e., the parameters and local variables within the scope of the outer routine. Such languages typically allow inner routines to call themselves recursively, resulting in multiple call stacks for the inner routines invocations, all of which point to the same outer routine context. This type of call frame is also known as a display.
  • Other return state – Besides the return address, in some environments there may be other machine or software states that need to be restored when a subroutine returns. This might include things like privilege level, exception handling information, arithmetic modes, and so on. If needed, this may be stored in the call stack just as the return address is.

The typical call stack is used for the return address, locals, and parameters (known as a call frame). In some environments there may be more or fewer functions assigned to the call stack. In the Forth programming language, for example, only the return address and local variables are stored on the call stack (which in that environment is named the return stack); parameters are stored on a separate data stack. Most Forths also have a third stack for floating point parameters. In computer science, a local variable is a variable that is given local scope. ... In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. ... A parameter is a variable which can be accepted by a subroutine. ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to commonly used values—typically, the values being in the midst of a calculation at a given point in time. ... Reverse Polish notation (RPN) , also known as postfix notation, is an arithmetic formula notation, derived from the Polish notation introduced in 1920 by the Polish mathematician Jan Łukasiewicz. ... An object-oriented programming language is one that allows or encourages, to some degree, object-oriented programming methods. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose, high-level programming language with low-level facilities. ... In many object-oriented programming languages, this (or self) is a keyword which is used to refer to the object on which the currently executing method has been invoked. ... WordNet gives four main senses for the English noun object: a physical entity; something that is within the grasp of the senses; an aim, target or objective — see Object (task); a grammatical Object — either a direct object or an indirect object the focus of cognitions or feelings. ... An object is fundamental concept in object-oriented programming. ... Layer may refer to: Look up Layer in Wiktionary, the free dictionary. ... It has been suggested that this article or section be merged into Object-oriented analysis and design. ... Pascal is an imperative computer programming language, developed in 1970 by Niklaus Wirth as a language particularly suitable for structured programming. ... Ada is a structured, statically typed imperative computer programming language designed by a team led by Jean Ichbiah of CII Honeywell Bull under contract by the US Navy during 1977–1983. ... // In computer programming, a nested function (or nested procedure/subroutine) is a function which is lexically (textually) encapsulated within another function. ... Forth is a programming language and programming environment, initially developed by Charles H. Moore at the US National Radio Astronomy Observatory in the early 1970s. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ...


Structure

A call stack is composed of stack frames (sometimes called activation records). Each stack frame corresponds to a call to a subroutine which has not yet terminated with a return. For example, if a subroutine named DrawLine is currently running, having just been called by a subroutine DrawSquare, the top part of the call stack might be laid out like this:

The stack frame at the top of the stack is for the currently executing routine. In the most common approach the stack frame includes space for the local variables of the routine, the return address back to the routine's caller, and the parameter values passed into the routine. The memory locations within a frame are often accessed via a register called the stack pointer, which also serves to indicate the current top of the stack. Alternatively, memory within the frame may be accessed via a separate register, often termed the frame pointer, which typically points to some fixed point in the frame structure, such as the location for the return address. Image File history File links No higher resolution available. ...


Stack frames are not all the same size. Different subroutines have differing numbers of parameters, so that part of the stack frame will be different for different subroutines, although usually fixed across all activations of a particular subroutine. Similarly, the amount of space needed for local variables will be different for different subroutines. In fact, some languages support dynamic allocations of memory for local variables on the stack, in which case the size of the locals area will vary from activation to activation of a subroutine, and is not known when the subroutine is compiled. In the latter case, access via a frame pointer, rather than via the stack pointer, is usually necessary since the offsets from the stack top to values such as the return address would not be known at compile time. This article is about the computing term. ...


In many systems a stack frame has a field to contain the previous value of the frame pointer register, the value it had while the caller was executing. For example, in the diagram above, the stack frame of DrawLine would have a memory location holding the frame pointer value that DrawSquare uses. The value is saved upon entry to the subroutine and restored for the return. Having such a field in a known location in the stack frame allows code to access each frame successively underneath the currently executing routine's frame.


Programming languages that support nested subroutines have a field in the call frame that points to the call frame of the outer routine that invoked the inner (nested) routine. This is also called a display. This pointer provides the inner routine (as well as any other inner routines it may invoke) access to the parameters and local variables of the outer invoking routine. A nested function is a function which can only be called from its parent function. ...


For some purposes, the stack frame of a subroutine and that of its caller can be considered to overlap, the overlap consisting of the area where the parameters are passed from the caller to the callee. In some environments, the caller pushes each argument onto the stack, thus extending its stack frame, then invokes the callee. In other environments, the caller has a preallocated area at the top of its stack frame to hold the arguments it supplies to other subroutines it calls. This area is sometimes termed the outgoing arguments area or callout area. Under this approach, the size of the area is calculated by the compiler to be the largest needed by any called subroutine.


Use

Call site processing

Usually the call stack manipulation needed at the site of a call to a subroutine is minimal (which is good since there can be many call sites for each subroutine to be called). The values for the actual arguments are evaluated at the call site, since they are specific to the particular call, and either pushed onto the stack or placed into registers, as determined by the calling convention being used. The actual call instruction, such as "Branch and Link," is then typically executed to transfer control to the code of the target subroutine. To meet Wikipedias quality standards, this article or section may require cleanup. ...


Callee processing

In the called subroutine, the first code executed is usually termed the subroutine prologue, since it does the necessary housekeeping before the code for the statements of the routine is begun. In assembly language programming, the function prologue is a few lines of code which appear at the beginning of a function, which prepare the stack and registers for use within the function. ...


The prologue will commonly save the return address left in a register by the call instruction by pushing the value onto the call stack. Similarly, the current stack pointer and/or frame pointer values may be pushed. Alternatively, some instruction set architectures automatically provide comparable functionality as part of the action of the call instruction itself, and in such an environment the prologue need not do this.


If frame pointers are being used, the prologue will typically set the new value of the frame pointer register from the stack pointer. Space on the stack for local variables can then be allocated by incrementally changing the stack pointer.


The Forth programming language allows explicit winding of the call stack (called there the "return stack"). The Scheme programming language allows the winding of special frames on the stack through a "dynamic wind". Forth is a programming language and programming environment, initially developed by Charles H. Moore at the US National Radio Astronomy Observatory in the early 1970s. ... The Scheme programming language is a functional programming language and a dialect of Lisp. ...


Return processing

When a subroutine is ready to return, it executes an epilogue analogous to the prologue. This will typically restore saved register values (such as the frame pointer value) from the stack frame, pop the entire stack frame off the stack by changing the stack pointer value, and finally branch to the instruction at the return address. Under many calling conventions the items popped off the stack by the epilogue include the original argument values, in which case there usually is no further processing back in the caller. With some conventions, however, it is the caller's responsibility to remove the arguments from the stack after the return.


Unwinding

Returning from the called function will pop the top frame off of the stack, perhaps leaving a return value.


The stack must also be unwound during exception handling. To support exceptions, the stack frame will contain one (or more) entries to indicate exception handlers. When an exception is thrown, the stack is unwound until an exception handler that is prepared to handle the exception is found. Common Lisp allows control of what happens when the stack is unwound by using the unwind-protect special operator. Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of some condition that changes the normal flow of execution. ... Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ...


When applying a continuation, the stack is unwound and then rewound with the stack of the continuation. This is not the only way to implement continuations; for example, using multiple, explicit stacks, application of a continuation can simply activate its stack and wind a value to be passed. In computing, a continuation is a representation of the execution state of a program (for example, the call stack or values of variables) at a certain point. ...


Security

The mixing of control flow data affecting the execution of code (return addresses, saved frame pointers) and simple program 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). In computer security, an exploit is a piece of software, a chunk of data, or sequence of commands that take advantage of a bug, glitch or vulnerability in order to get unintended or unanticipated behavior out of computer software, hardware, or something electronic (usually computerized). ... In computer security and programming, a buffer overflow, or buffer overrun, is a programming error which may result in a memory access exception and program termination, or in the event of the user being malicious, a breach of system security. ...


See also

In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. ... It has been suggested that this article or section be merged with Function stack. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

External links

  • Stack Frame Allocation on MSDN

  Results from FactBites:
 
Using a call stack hash to record the state of a process invention (521 words)
Using a call stack hash to record the state of a process
In embodiments of the invention, selected aspects of a process' call stacks are hashed, and the hash is used to capture the execution state of the process in a concise form and with minimal impact on the performance of the process and with no modification to the process code.
In an embodiment of the invention, the identities of modules on the call stack are hashed in combination with some but not all offset information to minimize the affect of patches and minor changes to the code, and improve the ability to discriminate different execution paths.
Stack (data structure) - Wikipedia, the free encyclopedia (3040 words)
Stack pointers may point to the origin of a stack or to a limited range of addresses either above or below the origin (depending on the direction in which the stack grows); however, the stack pointer cannot cross the origin of the stack.
Stacks are either visualized growing from the bottom up (like real-world stacks), or, with the top of the stack in a fixed position (see image), a coin holder ([1]) or growing from left to right, so that "topmost" becomes "rightmost".
A stack is usually represented in computers by a block of memory cells, with the "bottom" at a fixed location, and the stack pointer holding the address of the current "top" cell in the stack.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m