<!-- saved from url=(0022)http://internet.e-mail -->
<!-- saved from url=(0022)http://internet.e-mail -->
<!--------------------------------------------------------------------------->
<!-- INTRODUCTION
The Code Project article submission template (HTML version)
Using this template will help us post your article sooner. To use, just
follow the 3 easy steps below:
1. Fill in the article description details
2. Add links to your images and downloads
3. Include the main article text
That's all there is to it! All formatting will be done by our submission
scripts and style sheets.
-->
<!--------------------------------------------------------------------------->
<!-- IGNORE THIS SECTION -->
<!-- http://www.codeproject.com/styles/global.css -->
<html>
<head>
<title>The Code Project</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type=text/css href="http://www.codeproject.com/styles/global.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<!--------------------------------------------------------------------------->
<!------------------------------- STEP 1 --------------------------->
<!-- Fill in the details (CodeProject will reformat this section for you) -->
<pre>
Title: Playing with the stack
Author: Chavdar Dimitrov
Email: chavdar.dimitrov@sirma.bg
Environment: VC++ 5.0-6.0, Borland C++ 5.02-5.5, Borland C++ Builder 6, NT 4.0, Windows 2000, Win95/98
Keywords: Stack, Trace, Profiling, Dump, Disassembler, Stack frame, frame pointer
Level: Beginner
Description: An article describing how a C++ compiler uses the stack. As an example a simple class is described that is
able to extract function calling information from the stack in a compiler independent way.
Section Miscellaneous
SubSection General
</pre>
<hr width=100% noshade>
<!------------------------------- STEP 2 --------------------------->
<!-- Include download and sample image information. -->
<ul class=download>
<li><a href="stackdumper.rar">Download source - 897 Kb</a></li>
</ul>
<!------------------------------- STEP 3 --------------------------->
<!-- Add the article text. Please use simple formatting (<h2>, <p> etc) -->
<p>In this essay I am going to show you how the most commonly used C++ compilers (MSVC and Borland) use the stack.
Beginners will learn how the stack is used, what the function stack frame is, what the stack frame pointer is and how to use
this information in order to get a function stack trace.<br>
I hope that the more advanced readers will find some interesting information, too.<br>
As an example, a simple class named <code>StackDumper</code> is described.<br>
The class <code>StackDumper</code> has a method that browses the thread's stack and allows you to save
in a text file the names (or addresses in the worst case) of all functions executed before the <code>foo</code> is called.
As a side effect of this functionality you will be able to ask the <code>StackDumper</code> whether <code>foo</code>
is called from <code>foo1</code>. <br>
The task became a little bit complicated by my intention to create a class that is not dependent on any
particular compiler. If you download the article demo you will find three projects - for MSVC++ 6, for Borland C++ 5.02 and
for Borland C++ Bulder 6.<br><br>
If you are using the VC++ compiler there is an easy and already described way to implement this functionality.
John Panzer has published in the C/C++ Users Journal, January 1999, his essay "Automatic Code Instrumentation". <br>
Shortly, he uses the <code>/Gh</code> compiler switch to force the compiler to generate a call to a
<code>_penter</code> function at the start of each client function. From inside <code>_penter</code> the
address of the caller is retrieved and stored in a parallel stack. It also records the function entry time.
Afterwards the original return address of
the caller is replaced by the address of a user function. This function is used for profiling purposes.
When it is called it records the function exit time and restores the original return address of the caller.<br>
This is the main idea.You can download the essay from <a href= http://www.johnpanzer.com/aci_cuj/index.html>here</a>.<br>
Obvoiusly this approach uses a Microsoft-specific compiler switch.<br>
Due to the parallel stack support a special attention should be paid to the case when an exception occurs
in one of the profiled functions.<br>
The compiler generates a hidden call to the <code>_penter</code> function in all user functions which is not
very flexible because you may not want to collect information about every function.<br><br>
The same functionality can be implemented by the well known concept of stack backtrace.<br>
The idea is to use the stack frame that each function builds on the stack to trace the calling sequence.
This approach is compiler independent (at least it works with both MSVC and Borland compilers), but also it
imposes some limitations. Most compilers provide options to compile a function without prolog and epilog
code. For example functions declared with <code>__declspec(naked)</code> attribute will be compiled by
MSVC++ and Borland C++ compilers without prolog and epilog code. The same effect can be reached by specifying some
compiler options for optimizations. For example the <code>/Oy</code> switch of Microsoft compiler suppresses the creation
of frame pointers on the call stack.<br><br>
In this essay I take for granted that the program is compiled without any optimisations or "special" compiler switches.
<h3> 1. How the stack is used? </h3>
<h3>1.1. Stack frame and frame pointer</h3>
Here is a brief explanation for those of you who are not familiar with the way the stack is used during function calls.<br>
The more advanced readers can skip this section.<br>
When a function is called its arguments are pushed first on the stack depending on the calling convention.<br>
Then the <code>call</code> instruction is executed. It pushes the return address on the stack.<br>
The first instruction of the function is <code>push ebp</code> - the base pointer is pushed.<br>
The stack pointer is moved in the ebp, than esp is decremented to make room on the stack for the local variables of the function.<br>
So for every called function the following information is built on the stack:<br>
<p align=center><img src="stackdumper/stackdumper.gif" alt="Sample Image" width=400 height=200></p>
<p align=center><b>Figure 1.</b></p>
This information is called "stack frame". The register <code>ebp</code> has a special meaning. It is called "frame pointer".
The frame pointer is initialized at the function start by the standard prolog code and stays unchanged during function execution.<br>
The value of the previous function frame pointer is restored when the current function exits(epilog).<br>
How the frame pointer is used?<br>
The compiler uses the frame pointer to refer to local variables and parameters of a function(if any).<br>
1. <code>*(ebp)</code> is the value of the frame pointer of the caller;<br>
2. <code>*(ebp+4)</code> is the return address(the place in the caller body where execution will continue after the callee returns);<br>
3. <code>*(ebp+4+4*i)</code> is the value of i-th function argument (1 based, assuming that each argument takes 4 bytes);<br>
4. <code>*(ebp-offset)</code> refers to local variables.<br><br>
You can see this operation in the following simple example:
<pre>
int func(int nArg1, int nArg2)
{
int n[3];
return nArg1;
}
int main()
{
func(0,1);
return 1;
}
</pre>
The Borland C++ 5.02 compiler generates the following assembly code(__cdecl calling convention -
the arguments are pushed on the stack from right to left, the caller cleans the stack. More information about calling convention can
be found <a href=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/HTML/_core_calling_conventions.3a_.overview.asp>here</a>):
<pre>
Dissassembly of main:
00401110 55 push ebp <--store the ebp register on the stack
00401111 8B EC mov ebp, esp <--current stack pointer in ebp
00401113 6A 01 push 1 <--the arguments of func are pushed on the stack
from right to left
00401115 6A 00 push 0
00401117 E8 EC FF FF FF call func <--this call pushes the return address (0040111C) on the stack
0040111C 83 C4 08 add esp, 8 <-- __cdecl calling convention => caller have to clean the space
that arguments used on the stack. Every push decrements the stack pointer and every
pop increments it by the size of the operand. Two ints are pushed on the
stack => the stack pointer has to be increased by 8.
0040111F B8 01 00 00 00 mov eax, 1 <-- the return value of main goes in eax
00401124 5D pop ebp <-- ebp is restored
00401125 C3 ret
Dissassembly of func:
00401108 55 push ebp |<-- prolog.
00401109 8B EC mov ebp, esp |
0040110B 83 C4 F4 add esp, -0x0c <-- make room for 3*4 bytes for the local variable n on the stack
0040110E 8B 45 08 mov eax, [ebp+0x08] <-- move the return value (nArg1) in eax
00401111 8B E5 mov esp, ebp |<-- epilog. epb contains the caller frame ptr
00401113 5D pop ebp |
00401114 C3 ret
</pre>
<h3>1.2. Callstack</h3>
It is not very hard to see how the stack frame of a function can be used to get the caller address of this function.
As I have mentioned before <code>*(ebp+4)</code> points to the return address of the function.<br>
This address is inside the body of the caller.<br>
<h3>1.2.1. How to get the starting address of the caller?</h3>
<b>Approach1: Prolog searching</b><br><br>
We supposed that all functions are compiled with a prolog and an epilog. Having an address inside the function, we just have to
search for the byte sequence <code>55 8B EC</code>. As you can see from the dissassembly above these are the opcodes of the prolog.<br>
Let's call them "prolog signature".<br>
Unfortunately there is a problem.<br>
The same sequence of bytes could appear in an instruction encoding.<br>
For example the instruction <code>mov eax, EC8B55h</code> has the following instruction encoding: <code>B8 55 8B EC 00</code>.
Obviously when we are searching the prolog signature byte by byte we will find the signature somewhere inside the mov
instruction.<br>
Note:<br>
In my experience the method of searching the prolog signature in most cases works fine. To keep things simple you can skip the
next section.<br>
Note end.<br>
Well, I don't have an ellegant solution to the above described problem.<br>
For that reason I am going to kill a mosquito with a nuclear bomb :-).<br><br>
<b>Approach2: Backwards disassembling</b><br><br>
Given an address inside the body of a function, it is quite enough to find the address of the previous instrucion.<br>
This task cannot be solved without knowing the instruction format. We need a disassembler to do this.<br>
You can find in the source a function called <code>FindAddressOfPrevInstruction</code>:<br>
<pre>
#define MAX_INTEL_INSTRUCTION_LEN 15
DWORD FindAddressOfPrevInstruction(DWORD EIP, PUCHAR instr)
{
DWORD Addr = EIP-MAX_INTEL_INSTRUCTION_LEN;
DWORD PrevAddr;
unsigned long res;
do
{
PrevAddr=Addr;
res = Disasm32(&Addr, instr);
} while(Addr < EIP);
EIP=PrevAddr;
return EIP;
}
</pre>
I think this function is straightforward. Having this function it is easy to find the prolog signature in a more precise way - you just
have to disassemble backwards until you find the prolog signature.<br><br>
<h3>1.2.2. Tracing the stack</h3>
As you can see from Figure 1. every function stack frame contains a pointer to the callers frame which contains a pointer
to its caller frame and so on.
In fact we have a list of stack frames which can be used to find the callstack of every called function.<br>
But still there is an important question:<br>
When do we have to stop stack browsing, or, in other words, when does this list begin?<br><br>
I think we can find the answer if we take a look at the process and thread starting routines which resides in <code>kernel32.dll</code>.<br>
When Windows creates a process and its main thread it performs an internal call to the <code>CreateProcess</code> API.<br>
<code>CreateProcess</code> on the other hand invokes an internal routine in kernel32.dll named <code>BaseProcessStart</code>.<br>
Here is the dissasembly (under the condition that you have kernel32.pdb):<br>
<pre>
KERNEL32!BaseProcessStartThunk:
77e8d2e4 xor ebp,ebp <-- Look here!
77e8d2e6 push eax
77e8d2e7 push 0x0 <-- This can be interpreted as a return address
KERNEL32!BaseProcessStart:
77e8d2e9 push ebp <-- This is a normal stack frame. But the previous frame ptr is zeroed a few lines above
77e8d2ea mov ebp,esp
77e8d2ec push 0xff
...snip...
77e8d323 call dword ptr [ebp+0x8] <-- call the entry point of our process(for example mainCRTStartup)
77e8d326 jmp KERNEL32!BaseProcessStart+0x3d (77eb6624)
</pre>
Similar things are happening in each call to the <code>CreateThread</code> API:
<pre>
KERNEL32!BaseThreadStartThunk:
77e964cb xor ebp,ebp
77e964cd push ebx
77e964ce push eax
77e964cf push 0x0
KERNEL32!BaseThreadStart:
77e964d1 55 push ebp
77e964d2 8bec mov ebp,esp
77e964d4 6aff push 0xff
...snip...
77e9651d ff750c push dword ptr [ebp+0xc] <-- push the argument to ThreadFunc
77e96520 ff5508 call dword ptr [ebp+0x8] <-- DWORD WINAPI ThreadFunc( LPVOID );
77e96523 50 push eax
77e96524 e805000000 call KERNEL32!ExitThread (77e9652e)
77e96529 e923f10000 jmp KERNEL32!BaseThreadStart+0x81 (77ea5651)
</pre>
Judjing from the examples above I think we can conclude that stack frames tracing can stop when either the return address or the old ebp
turns to zero.
<h3>1.3. "Called from" functionality</h3>
Up to now we know how to create a callstack list (a list of addresses of functions). <br>
I would like to say a few words about the following question:<br><br>
Is it possible to implement a method that will allow the following C++ functionality?<br><br>
<pre>
retType foo(arguments)
{
if (foo_is_called_from_functionX)
doThings
else
doOtherThings
return whateverHasToBeReturned
}
</pre>
Two additional questions arise here:<br><br>
<h3>1.3.1 Do we need such a functionality?</h3>
This functionality could be considered as a new type of C++ runtime information. <br>
Since it is not implemented in the C++ standard it is probably useless...<br>
In my opinion this is a theoretical question and it should be the subject of a separate discussion.<br>
<br>
<h3>1.3.2. How to implement this functionality?</h3>
Since we know the call stack of <code>foo</code> it may seems trivial to browse the caller addresses searching for the address
of <code>functionX</code>. <br>
Unfortunately things are not so simple. The main difficulty is how to get the address of <code>functionX</code>.
<code>functionX</code> can be a class member (virtual or nonvirtual) function.<br> There is no way to get the "real" address of a function
from inside a C++ program. By "real address" I mean the relative virtual address where the compiler placed the function body.<br>
In most cases when you get a function address from inside a C++ program it does not appear to be a real address,
but rather an address in some virtual or thunking table.<br>
On the other hand it is definitelly clear that callstack addresses are real addresses.<br>
So what can we do in this case?<br>
The only simple solution I have found is to use function names instead of their addresses. This is because there is a relatively easy way(s)
to find the address of a function, having given its name. This will allow us to implement the above function as follows:
<pre>
retType foo(arguments)
{
if (IsCalledFrom("functionX") || IsCalledFrom("A::member1"))
doThings
else
doOtherThings
return whateverHasToBeReturned
}
</pre>
Now the question is how to find the address of a function given its name.<br>
There are two common ways to do this:<br><br>
<b>1. The development environment provides libraries that allow working with symbolic information.</b><br><br>
For example Microsoft provides the debug help library named DbgHelp (prior to Windows 2000 the
library was known as Image Help Library). The library contains functions for working with
symbolic information, for example <code>SymGetSymFromName</code>, <code>SymFromName</code> etc.<br>
As an example of using the DbgHelp library here is the function <code>getFuncInfo</code> you can find in the source.<br>
As far as I know, Borland provides a similar library named Borland Debug Hook Library, that can be used to extract information
from Borland debug symbol (.tds) files.
Unfortunatelly there is no much information on the net about how to use this library. You can download it from
<a href= http://codecentral.borland.com/codecentral/ccweb.exe/listing?id=14513>here</a>.
<br><br>
<b>2. Working with .map files</b><br><br>
Both Microsoft VC++ and Borland C++ compilers are able to generate map files.<br>
Generally speaking map files are text files that contain information about functions (and variables) in a module and their addresses.<br>
For example here is a snippet of a .map file generated by the Borland C++ 5.02 compiler:
<pre>
0001:000006F5 StackDumper::DumpStack(unsigned int)
0001:00000694 StackDumper::GetCallerAddr(long)
0001:000006C5 StackDumper::GetFuncAddr(unsigned long)
0001:000005FC StackDumper::StackDumper()
0001:00000639 StackDumper::~StackDumper()
</pre>
The important thing here is that the addresses are logical addresses. For example 0001:00000639 means that the destructor
<code>StackDumper::~StackDumper()</code> resides in the first section in the PE file at offset 0x639 in that section.
In the source you can find a simple function (written by Matt Pietrek) that converts linear addresses to logical addresses.<br>
Using this function you can convert the addresses from the stack trace into logical addresses that can be found in the map file.<br>
Having the logical address you just have to parse tha .map file in order to find the function name.
<br><br>
As a conclusion I have to say that I don't have any idea about how to implement the IsCalledFrom functionality in your release builds -
when you don't have neither debug information nor a map file generated(or you don't want to distribute such information with your program).<br><br>
<h3> 2. Exit thunks </h3>
In this section I will describe how to use the stack frame information in order to implement exit thunks.<br>
An exit thunk is a function that is invoked immediatelly after the <code>ret</code> instruction of the function for which the
thunk is installed.<br>
Exit thunks can be used for example in profiling applications. Here they are implemented just as another example of how to use the
stack frame information.<br>
The idea is very simple - in order to install an exit thunk we just have to declare a local variable: <code>StackDumper varName(true)</code>
(<code>true</code> means "use exit thunk") in the body of the function for which we want to install the thunk.<br>
The destructor <code>StackDumper::~StackDumper()</code> first saves the original return address of the function(i.e. <code>foo</code>)
where <code>StackDumper</code> is declared in a static local variable in <code>StackDumper</code>.<br>
Afterwards it replaces the return address of <code>foo</code> with the address of the <code>ExitThunk</code>. This causes
the <code>ret</code> instruction of <code>foo</code> to pass the control to the beginning of the <code>ExitThunk</code>.<br>
(Note that the destructor is the right place to perform this replacement. If we raplace the function return address in the
constructor(for instance) subsequent calls to the <code>DumpStack</code> function will generate erroneous stack trace information.)<br>
This is not a common function call - the <code>ret</code> instruction has poped the return address from the stack (which is now the
address of <code>ExitThunk</code>) and a jump is performed. So if <code>ExitThunk</code> builds a standard stack frame this frame will
not contain a return address.<br>
Another problem is that <code>ExitThunk</code> has to be "invisible" - it should not touch the registers, especially eax - where
the <code>foo</code> has placed its return value (if any).<br>
If <code>ExitThunk</code> is a standard function it will have something like this at the beginning(MSVC, Debug):
<pre>
50: void main()
51: {
004010F2 55 push ebp
004010F3 8B EC mov ebp,esp
004010F5 6A FF push 0FFh
004010F7 68 F0 30 41 00 push offset $L49591 (004130f0)
004010FC 64 A1 00 00 00 00 mov eax,fs:[00000000] <----Look here: The eax register is
changed and there is nothing you can do!!!
00401102 50 push eax
00401103 64 89 25 00 00 00 00 mov dword ptr fs:[0],esp
...
</pre>
You see that <code>ExitThunk</code> could not be a normal function.<br>
This is the reason for which this function must be declared <code>naked</code>.<br>
>From MSDN: "For functions declared with the naked attribute, the compiler generates code without prolog and epilog code.
You can use this feature to write your own prolog/epilog code using inline assembler code."<br>
Fortunately the three compilers I have tested the examples with (BC++ 5.02, BCB6, MSVC6) support naked function calls.<br>
(For Borland C++ 5.02 users this is probably a surprise. This was not documented. ;-))).<br>
This is the solution of the above mentioned problems.<br>
So the implementation of <code>ExitThunk</code> could be the follows:<br>
<pre>
/* static */
void __declspec(naked) StackDumper::ExitThunk()
{
__asm
{
push ebp
mov ebp, esp
sub esp, 4 //make room for one local variable
pushad
}
DoTheWork();
long temp;
temp = origRetAddr;
__asm{
popad
mov esi, temp
mov esp,ebp
pop ebp
jmp esi //I don't have return value on the stack -> can not use ret here.
}
}
</pre>
Well, that's all folks!
<h3> Acknowledgements </h3>
I would like to thank to mamaich for his help on disassembling issues!<br>
<br>
<font class="infobar">
Note about source compilation.<br>
In order to compile inline assembler source code with the Borland C++ 5.02 you will need the Turbo Assembler (tasm32.exe).<br>
The tasm32.exe is not included in Borland C++ 5.02 distribution. If you have BC++ Builder you will find the tasm32.exe in the bin folder.
</font>
</p>
<!------------------------------- That's it! --------------------------->
</body>
</html>
Submit an article or tip