Chapter 2
Stack Memory
2.1 Values and Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Stack .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 The Call Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 The Return Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Function Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Local Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4 Value Address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.5 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.6 Retrieving Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Visibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5.1 Draw Call Stack I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5.2 Draw Call Stack II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.3 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Answers .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6.1 Draw Call Stack I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6.2 Draw Call Stack II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6.3 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Examine the Call Stack with DDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1 Values and Addresses
In a computer, programs and data must be stored somewhere called storage. Without
storage, a computer has nothing to compute. Storage can be divided into volatile and non-
volatile. Volatile storage requires electricity, and can keep data only when a computer is
turned on. Volatile storage is usually called “memory”. Non-volatile storage persists when a
computer is turned off or rebooted: for example, flash memory or hard disks. Flash memory
is also called a solid-state disk or SSD.
A typical laptop computer today has several GB memory. G means “giga” and is the
metric system prefix for 1 billion. B means “byte” and is a sequence of 8 bits. Each bit can
store either 0 or 1. If a laptop has 8 GB of memory, the computer can store 64 billion bits
in memory. As a reference, the world’s population was about 7 billion in 2013.
A computer’s memory is organized into address-value pairs. These pairs are analogous
to street addresses and the families that live there. Consider the following scenario:
• The Jones family lives at One Silicon Street.
• The Smith family lives at Two Silicon Street.
• The Brown family lives at Three Silicon Street.
• The Taylor family lives at Four Silicon Street.
• The Clark family lives at Five Silicon Street.
We can express this information in a table:
9
10 Intermediate C Programming
Address Family
One Jones
Two Smith
Three Brown
Four Taylor
Five Clark
In a computer’s memory, each location stores either a zero or a one—something like the
following:
• Zero is stored at the first location.
• Zero is stored at the second location.
• One is stored at the third location.
• Zero is stored at the fourth location.
• One is stored at the fifth location.
We can also express this as a table:
Address Value
First Zero
Second Zero
Third One
Fourth Zero
Fifth One
Programmers usually consider more than one bit at a time. For the time being, let us
set aside the size of data. Instead, assume that each piece of data occupies one unit of
memory. Operating systems guarantee that everything has a unique and positive address.
The address is never zero or negative. The symbol NULL is defined as the zero address
and indicates an invalid address. It would be impossible to remember the addresses of
all of the bits of memory that a computer program manipulates. Early computer science
pioneers found an elegant solution: Create symbols, such as counter or sum to refer to the
relevant bits of memory. If the value stored corresponding to a symbol may change during
the program’s execution, this symbol is called a variable. The symbols have meaning to
humans writing computer programs, and compilers (such as gcc) convert these symbols
into addresses. The final computer program manipulates the values, and does not see the
symbols. Inside a computer’s memory, there are only addresses and values. This was a major
early innovation in easing the task of writing computer programs. The following figure shows
the relationships between symbols and addresses:
source code .c or .h files executable program
human readable −→ computer readable
symbols compiler addresses
Consider the following sample code:
int a = 5;1
double b = 6.7;2
char z = ’c’;3
The relationship between symbol, address, and value may look something like this inside
a computer’s memory:
Symbol Address Value
a 100 5
b 131 6.7
z 145 ‘c’
Stack Memory 11
A programmer has no control over the addresses—that is the job of the operating system
(e.g., Linux) and the compiler. Programmers do not need to know the addresses of a, b, or
z as long as the following rules are observed:
• Each piece of data has a unique address.
• The address cannot be zero (NULL) or negative.
• The compiler can convert symbols to addresses.
2.2 Stack
Modern computers usually organize volatile memory into three types:
1. stack memory
2. heap memory
3. program memory
The first two store data and the last stores the machine code of computer programs.
This chapter focuses on stack memory. Heap memory will be explained in a later chapter.
Before talking about stack memory, we must first introduce the concept of a stack.
Technical terms in computing are often related to the everyday meanings of the words
that they comprise. “Stack” is no exception. Ever heard of a “stack of books”? The easiest
way to add a book to a stack of books is to place it on top of the stack. The easiest way to
remove will be from the top. Thus, the first book to be removed from the stack will be the
last book previously placed on the stack. Computer scientists refer to this arrangement as
“last in, first out” (or “first in, last out”). Placing an item is called push, and removing an
item is called pop.
The stack concept is used in everyday life. To wear both socks and shoes, the socks must
go on before the shoes—push the socks, push the shoes. Then, to remove both the socks
and the shoes, the shoes come off before the socks—pop the shoes, pop the socks. The order
is reversed and this is characteristic of “last in, first out”.
Stack memory strictly follows first in, last out. New data enters the stack memory at the
top, and data are always removed from the top. It would be equivalent to add and remove
data from the bottom (i.e., it is still first in, last out); however, by convention, we use the
top instead of the bottom. The concept is the same. Data are pushed onto the top of the
stack and, later, popped from the top of the stack. Fig. 2.1 illustrates these two operations
of stack memory.
2.3 The Call Stack
2.3.1 The Return Location
How do computers use stack memory? Consider the following code snippet:
void f1 ( void)1
// void before f1 means no returned value2
// void in the p arenthes es means no a rgument3
{4
// ...5
12 Intermediate C Programming
720
386
-15
46
945
(a)
(b)
653
push
653
720
386
-15
46
945
653
720
386
-15
46
945
pop
720
386
-15
46
945
653
bottom
top
FIGURE 2.1: Pushing and popping data on a stack. (a) Originally, the top of the stack
stores the number 720. The number 653 is pushed onto the top of the stack. (b) Data are
retrieved (popped) from the stack. Pushes and pops can only occur at the top of the stack.
Although this figure illustrates the idea with integers, a stack is a general concept and can
manage any type of data.
}6
void f2 ( void)7
{8
f1 () ;9
// program continues from here after f1 finishes10
}11
The function f2 calls f1 at line 10. After f1 finishes its work, the program continues
running f2 from the line after f1. Fig. 2.2 illustrates the flow of the program.
FIGURE 2.2: The flow of the program as indicated by the numbers 1, 2, and 3.
Imagine that a mark is inserted right below the place where f1 is called, as shown in
Fig. 2.3. This mark tells the program where it should continue after f1 finishes. It is called
the “return location”, meaning that this is the place where the program should continue
after the function f1 returns (i.e., after f1 finishes its work).
A function is finished when it executes the return statement—anything below this
statement is ignored. Consider the following example:
void f( void )1
{2
i f (...)3
Stack Memory 13
FIGURE 2.3: The return location is the place where the program continues after the
function f1 returns.
{4
// ...5
return ;6
// the program will never reach here7
}8
// else not needed9
// ...10
return ;11
// the program will never reach here12
}13
In this function, if the condition at line 3 is true, then the function will execute the1
return at line 6. In this case, anything at line 7 is ignored and the program continues2
from the return location. However, if the condition at line 3 is false, then the function will3
execute the code at line 9. Note that it is not necessary to have an else at line 9. When the4
function reaches line 11, a return is executed, and the function stops—line 12 is ignored.5
Here, “ignored” means that the code is not executed when the program runs. Even though6
lines 7 and 12 are never executed, if they contain any syntax errors, the source code will7
not compile. Next, let’s consider three functions:8
void f1 ( void)9
{10
// ...11
}12
13
void f2 ( void)14
{15
f1 () ;16
// line after calling f1 , return location B17
// ...18
}19
20
void f3 ( void)21
{22
f2 () ;23
// line after calling f2 , return location A24
// ...25
}26
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.