When I started learning C programming a few years ago, my tutor taught me similar to most of the tutors around the world. She said me the very basic things like any int datatype is of 2 bytes memory. If the following is my code,
#include"stdio.h"
#include"conio.h"
void main()
{
clrscr();
int i,n;
n = 0;
for(i=0;i<3;i++)
n = n + i;
printf("%d",n); //obviously it prints 3
getch();
}
she will explain like what I have written below. Here my teacher starts off her class yet again. . .
Listen students. Here we have two integer values. So let us draw two boxes each of 2 bytes memory.The first box be the memory space of i and the second box be that of n. At
n = 0;
0 gets stored into the box n. As the control gets into the loop, 0 gets stored into the box i intially.0 0
Now the condition is checked. i < 3. Condition gets true. So now the value of n changes from 0 to n+i i.e., 0+0=0. The first iteration then ends after the increment statement. Now i gets incremented to 1. So our picture becomes like this.
1 0
And now i < 3 again. Condtion gets true. n changes from 0 to n + i i.e., 0+1=1. Don't forget the increment my dears. Only then our iteration gets completed. i++ makes our i to 2 now. And the picture will now look like
2 1
She will go on similarly step by step and will complete when both the boxes get 3, 3 values.
So thats it kids. After we get our boxes like this
3 3
the value of n gets printed on the screen.
3
By that time, I was merely like a kid nodding its head when a teacher claims earth as a circular mass. I never asked her any questions. I felt logically she was perfect. But now I am plentiful of queries. If there is a statement like n = n + i;
, won't there be a conflict as both the destination space and the operation space is the same n box? Will the operations be done with the help of any default temporary space for calculations? What will happen if I use a recursive code like the following snippet.
int factorial(int n)
{
if(n < 2)
{
return n;
}
else
{
n = n * factorial(n - 1);
return n;
}
}
How could it be possible to use a single n box as my tutor taught? Won't a new n box be created whenever factorial(n - 1)
is called? If I am right, how could the computer know which n box value to be returned? Somebody help me please. I am pulling of hairs from ma head!
Best Answer
Yes, exactly. Each time you call a function, additional memory is set aside for the function arguments and local variables.
Let's drop a couple of levels below C and talk about how a compiled program is laid out in memory1. We're going to assume a 32-bit, x86-like system for this discussion.
While the details vary from platform to platform, the general concepts are the same for most systems you're likely to work on. When a compiled program is loaded into memory, it's usually divided up into several logical segments; one segment contains the machine code, another contains constant (read-only) data items, another contains space for non-constant, global data items, another contains space for the stack, another contains the space for the heap, etc. The general layout looks something like the following (taken from this page):
As your program runs, it uses the stack to store function arguments and local variables, along with some program state (previous frame pointer, address to the next instruction). On x86-like systems, the stack grows "downwards", towards decreasing addresses. Among the registers2 provided, there are usually two to keep track of what's on the stack. There's the stack pointer, which points to the most recent item on the stack, and the frame pointer3, which points to the current stack frame. A stack frame is a region of the stack that contains the arguments and local variables for the current function, along with any saved program state:
On the systems I'm familiar with, the function arguments and program state are stored "above" the location stored in the frame pointer, and local variables are stored "below" it. Within the generated assembly code, arguments and variables are referred to by their offset from the address stored in the frame pointer. On x86. it would look something like
The first function argument is stored 8 bytes "above" the address value stored in the frame pointer
%ebp
, while the first local variable would be 4 bytes "below" it (note that this assumes a 32-bit system).The exact size of the frame depends on how many arguments and local variables need to be stored, although the platform may also require it to be aligned to certain boundary (IOW, the size of the frame must be a multiple of some number of bytes, usually 4 or 8, sometimes 16; for the purposes of this discussion, we're not going to worry about alignment).
Suppose your
factorial
function is called with an argument value of 3:A new stack frame will be set up that looks something like this:
where the "return address" is the address of the instruction immediately following the function call in the caller (in this case, it would be the instruction that assigns the result of
factorial(3)
tox
).Since there are no local variables, no space is allocated for them in the stack frame. Now, since
n
is not less than 2, you execute the lineThis means
factorial
is called again, this time with an argument value of 2. A new stack frame is createdn
is still not less than 2, so we callfactorial
again with an argument of 1:1
is less than 2, so we execute the lineThe common convention for returning values from functions is to write the value to a particular register. On x86, integer values are returned through register
%eax
, so the compiled code will do something likeNow register
%eax
will contain the value1
.When the function returns, the stack and frame pointers are restored to their previous values (the stack contents are left as-is):
So now we need to execute the remainder of
which will look something like4
Once again, we return
n
and exit the function, bringing us back to the previous call:Lather, rinse, repeat. The value returned in
%eax
(2
) is multiplied by the value in the argument8(%ebp)
(3
), and we write6
back to%eax
.Now, the C language definition says nothing about stacks, or stack frames, or registers, or anything like that; it only specifies the behavior of variables within a program, not how to implement that behavior. However, much of C's design is based on what most computer systems already provide (this is what people mean when they say that C is "close to the hardware"), so this is a very natural way of implementing that behavior. If you were working on a machine that had no stack, C programs would be somewhat more difficult to implement.
1. By which I mean a virtual address space, which is an idealized model of memory that your program sees; the OS and memory controllers will map this idealized model to physical RAM.
2. A register is a memory cell on the CPU itself. There are usually several special-purpose registers (program counter, stack pointer, frame pointer) and some number of general-purpose registers. Reading and writing to registers is faster than reading and writing to RAM.
3. On 32-bit x86, the stack pointer register is
esp
and the frame pointer register isebp
(a.k.a. the base pointer). On 64-bit x86, they're namedrsp
andrbp
.4. This is how the compiled code on my system does it, anyway.