C / C++ / MFC

Re: confused about system stack

4-Jun-06 22:54

Hello everyone,

I am confused about the term "stack" which the system will use -- there are so many items we call them "stack". Suppose when we invoke a function, we will push the parameters and return address into a "stack", so that when the function returns, it can find the address to proceed correctly. Is it the same as a data structure "stack".

When we create a variable using malloc or new, we also say that it is allocated on "heap" other than on "stack", is heap also something like a stack in ternally (but has a different term)? And for local variables, when they are created, we say it is created on stack (for example, int i, j; ), it seems that each function has a separate stack?

Another confusing thing is thinking about stack and segment together, like the code segment, data segment of the program (which you can see when debugging your application), are the segments also some stacks (since when local variables are on code segment, we also say local variables are on stack, so I think maybe segment is implemented as stack)?

Besides the "stacks" I presented above, are there any other stacks which system will utilize?

Please forgive asking a simple question. Smile | :)

regards,
George

Viorel.5-Jun-06 0:19

5-Jun-06 0:19

My viewpoint is the following:

When you start a C++ program, it consists of four parts: the code segment, the data segment; a unique heap area; a unique stack area.

The code segment contains microprocessor instructions obtained after successful compilation.

The data segment contains at least data declared with "static" modifier, as well as quoted strings.

When you call a function, for instance "f(1,2,3)", then the arguments 1, 2 and 3 are pushed on the stack (the particular order depends on some factors). Also a return address (the address of the next instruction, after your "f(1,2,3)") is pushed on the stack. Within the function, when you access an argument, you actually access a value from the stack. When the function finishes and returns back to the pushed address, the pushed values are popped from the stack and are lost, and the stack returns to its previous state.

Push and pop operations are performed by microprocessor using special pointer, stored in a register, which points to the top of the stack.

If you call a function again, the same stack is re-used.

If you have some local variables in your function, they are allocated on the same stack, somewhere above the pushed parameters and return address. That’s why you can crash your program if you access local variables incorrectly. For instance, by accessing a local array using invalid index.

Local variables declared with "static" modifier are allocated in data segment instead of the stack. This way, the value of static local variables is preserved between function calls.

If you call functions recursively, or use too large local variables, the stack becomes full.

When you use new operator or malloc function, data are allocated from the heap area. In contrast with the stack area, which are automatically cleared back when you return from a function, the heap-allocated data must be release explicitly, using delete or free.

If you allocate too much data or forget to release unneeded ones, the heap area becomes full. If you uses invalid pointers, you can corrupt the heap area.

So, there is a single stack and a single heap shared by your functions, and each program has its own stack and heap.

Windows applications also can allocate data in a specific manner using system functions like GlobalAlloc and others.

That is my vision on stack and heap.

George_George5-Jun-06 1:38

5-Jun-06 1:38

Thank you Viorel,

> "each program has its own stack and heap"

Do you mean each process will has one unique stack and unique heap? So, different threads in the same process will share the stack and heap?

In your reply, you have never mentioned global variables and const variables. Will they be on data segment or on heap?

regards,
George

-- modified at 7:42 Monday 5th June, 2006

Viorel.5-Jun-06 2:05

5-Jun-06 2:05

In multithreading application each of the thread in the same process will have its own stack. (That's why the functions like CreateThread or _beginthread have an optional argument for stack's size).

But the heap area is common for all of the threads. As a result, access to common heap data, as well as to common data segment, must be "synchronized". When you build multithreading applications, it is important to specify the correct compiler options (like "Runtime library"), otherwise shared data will be unexpectedly corrupted.

Global and constant variables are allocated in data segment. Actually this segment can be divided into constant data and changeable data. Compiler can apply some microprocessor’s or OS features in order to detect violation of constant data.

George_George5-Jun-06 2:24

5-Jun-06 2:24

Thank you very much Viorel!

I am a further question, as you mentioned before, each process will have a separate heap. So, if I use new operator on different process, they will be allocated on different heap. Correct? (a little more conflicts with my previous understanding, since I think new operator will access the same memory range to find an empty slot for different processes -- the range is common to all processes -- to allocate space, so the space allocated by new for different process may be next to each other).

> "When you build multithreading applications, it is important to specify the correct compiler options (like "Runtime library"), otherwise shared data will be unexpectedly corrupted."

I understand that synchronization control between threads are important. But I have not found any relationship between your above statements and synchronization control between threads. What are your points in above statements?

regards,
George

-- modified at 8:27 Monday 5th June, 2006

Viorel.5-Jun-06 3:18

5-Jun-06 3:18

Each process has its own "memory space". From one process, you cannot easily access data from another process. As a result, when you use new operator, you obtain a memory fragment which belongs to this process only.

Even if in one process the pointer returned by new operator is, for example, 0x30000, it is possible that another process will get the same value in its new call. But changes made in one process via this pointer do not affect another process. This is because of separated memory spaces. So the 0x30000 address in both processes points to different "physical locations". On microprocessor/system level, there is an automatic procedure for conversion between pointer's values ("virtual address") to "physical address". For instance, the 0x30000 address is converted to the 0x7800000 physical address in the first process, and to 0xAB00000 physical address in the second one, from your, let's say, 1 GBytes of memory.

Also it should be considered that if a process requests more memory that physically is available, then some parts of other processes can be temporary discarded to disk. Probably this is what is called "paging file".

C++ libraries usually are delivered in both versions -- for single-threaded and multi-threaded application. This is for performance reason: single-threaded application does not require redundant synchronization. For instance, there is a version for new operator for single-threading, and another for multi-threading. I just wanted to point that the system functions for single-threading will usually not work in multi-threading mode, so the proper compiler configuration is required in order to avoid heap corruption.

For your own functions, you have to provide your own synchronization. In Windows, there is a series of objects ("critical section", "mutex", etc.) for doing this.

George_George5-Jun-06 3:38

5-Jun-06 3:38

Thank you Viorel!

Your reply is excellent!! I think both data segment and heap are used to provide global access through a process (that is, compared with stack, variable will disappear when function returns, but in data segment or in heap, variable will be valid and accessible through the life-cycle of a process). My question is that, why system needs to divide global data access through a process into data segment and heap -- they are both used for the same purpose (global data access through a process), what are the different functions between them?

regards,
George

Viorel.5-Jun-06 3:58

5-Jun-06 3:58

Data segment is a storage for named variables, declared like "int x = 0;" or "static int x = 0;" outside functions, or as "static int x = 0;" inside functions. Data segment also stores initial value of arrays, like "Hello, World!" for strings, or {1, 2, 3} for integer arrays. This data segment is allocated once, when process starts, and the number of variables here cannot grow.

(One more thing which is stored in data segment is "virtual tables" of classes having virtual functions).

Heap area is for unnamed variables, allocated only when you explicitly call new or related. So the number of variables varies here during program execution.

While variables declared in global data segment can be accessed by name, the variables allocated in heap have to be accessed by pointers or references.

So the main difference between global data segment and heap is that the size of data segment is fixed, while the data allocated in the heap can vary.

That is my understanding.

George_George6-Jun-06 19:07

6-Jun-06 19:07

Thank you Viorel!

I agree with all of your great points. Except that, you think we do not access the variable on heap by its name. I think all types of variables are accessed by name.

For example,

int* pi = new int [5];

variable pi is allocated on heap, but later when we want to access this variable, we also use the variable name "pi", right? Why you say we do not access variable by its name if the variables are on heap?

> "Heap area is for unnamed variables"

regards,
George

Viorel.6-Jun-06 20:58

6-Jun-06 20:58

In declarations like

int * pi = new int[5];

you actually have two variables. First is pi, which is a pointer. It is allocated on the stack (in case of functions) or in data segment (if is outside of functions). The size of pi is usually four bytes. Another variable is the array allocated by new in heap area. This variable has no name, by has an address (for instance 0x1234), returned by new, which is assigned to the pi variable. The size of this array is twenty bytes.

Therefore the content of the pi variable is the address of the array, but not the content of array. When you use pi, you actually denote the address -- 0x1234. For instance, when you call a function, f(pi), you pass the 0x1234 value to the function, but not the content of array.

When you use delete pi, the unnamed array is deleted, but the pi variable is still available for another assignments.

In order to work with the referenced values via pointer, you use expressions like pi[3] or *(pi+3).

Actually, in case of data allocated on the heap, you can simulate an assignment of a name, using references. For instance:

int * z = new int;
int & r = *z;

In this case, r is a synonym for the integer allocated on the heap, and the usage of r will be treated as an access to this integer. For instance, r = 200 will assign a new value to that integer. Here, z still denotes an address, but r denotes the value on the heap. So, now that integer has a name -- r;

Internally, references are stored as pointers, i.e. they contain addresses of referenced variables. They are a convenient way for working with addresses, because "r" is simpler than "*z".

Therefore we can say that references offer a way for assigning names to variables allocated on the heap.

That is the picture in my opinion.

George_George6-Jun-06 21:21