development/Win32/vld/src/callstack.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //  $Id: callstack.cpp,v 1.20 2006/11/18 03:12:34 dmouldin Exp $
   3 //
   4 //  Visual Leak Detector - CallStack Class Implementations
   5 //  Copyright (c) 2005-2006 Dan Moulding
   6 //
   7 //  This library is free software; you can redistribute it and/or
   8 //  modify it under the terms of the GNU Lesser General Public
   9 //  License as published by the Free Software Foundation; either
  10 //  version 2.1 of the License, or (at your option) any later version.
  11 //
  12 //  This library is distributed in the hope that it will be useful,
  13 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 //  Lesser General Public License for more details.
  16 //
  17 //  You should have received a copy of the GNU Lesser General Public
  18 //  License along with this library; if not, write to the Free Software
  19 //  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 //
  21 //  See COPYING.txt for the full terms of the GNU Lesser General Public License.
  22 //
  23 ////////////////////////////////////////////////////////////////////////////////
  24
  25 #include <cassert>
  26 #include <windows.h>
  27 #define __out_xcount(x) // Workaround for the specstrings.h bug in the Platform SDK.
  28 #define DBGHELP_TRANSLATE_TCHAR
  29 #include <dbghelp.h>    // Provides symbol handling services.
  30 #define VLDBUILD
  31 #include "callstack.h"  // This class' header.
  32 #include "utility.h"    // Provides various utility functions.
  33 #include "vldheap.h"    // Provides internal new and delete operators.
  34 #include "vldint.h"     // Provides access to VLD internals.
  35
  36 #define MAXSYMBOLNAMELENGTH 256
  37
  38 // Imported global variables.
  39 extern HANDLE             currentprocess;
  40 extern HANDLE             currentthread;
  41 extern CRITICAL_SECTION   stackwalklock;
  42 extern CRITICAL_SECTION   symbollock;
  43
  44 // Constructor - Initializes the CallStack with an initial size of zero and one
  45 //   Chunk of capacity.
  46 //
  47 CallStack::CallStack ()
  48 {
  49     m_capacity   = CALLSTACKCHUNKSIZE;
  50     m_size       = 0;
  51     m_status     = 0x0;
  52     m_store.next = NULL;
  53     m_topchunk   = &m_store;
  54     m_topindex   = 0;
  55 }
  56
  57 // Copy Constructor - For efficiency, we want to avoid ever making copies of
  58 //   CallStacks (only pointer passing or reference passing should be performed).
  59 //   The sole purpose of this copy constructor is to ensure that no copying is
  60 //   being done inadvertently.
  61 //
  62 CallStack::CallStack (const CallStack &)
  63 {
  64     // Don't make copies of CallStacks!
  65     assert(FALSE);
  66 }
  67
  68 // Destructor - Frees all memory allocated to the CallStack.
  69 //
  70 CallStack::~CallStack ()
  71 {
  72     CallStack::chunk_t *chunk = m_store.next;
  73     CallStack::chunk_t *temp;
  74
  75     while (chunk) {
  76         temp = chunk;
  77         chunk = temp->next;
  78         delete temp;
  79     }
  80 }
  81
  82 // operator = - Assignment operator. For efficiency, we want to avoid ever
  83 //   making copies of CallStacks (only pointer passing or reference passing
  84 //   should be performed). The sole purpose of this assignment operator is to
  85 //   ensure that no copying is being done inadvertently.
  86 //
  87 CallStack& CallStack::operator = (const CallStack &)
  88 {
  89     // Don't make copies of CallStacks!
  90     assert(FALSE);
  91     return *this;
  92 }
  93
  94 // operator == - Equality operator. Compares the CallStack to another CallStack
  95 //   for equality. Two CallStacks are equal if they are the same size and if
  96 //   every frame in each is identical to the corresponding frame in the other.
  97 //
  98 //  other (IN) - Reference to the CallStack to compare the current CallStack
  99 //    against for equality.
 100 //
 101 //  Return Value:
 102 //
 103 //    Returns true if the two CallStacks are equal. Otherwise returns false.
 104 //
 105 BOOL CallStack::operator == (const CallStack &other) const
 106 {
 107     const CallStack::chunk_t *chunk = &m_store;
 108     UINT32                    index;
 109     const CallStack::chunk_t *otherchunk = &other.m_store;
 110     const CallStack::chunk_t *prevchunk = NULL;
 111
 112     if (m_size != other.m_size) {
 113         // They can't be equal if the sizes are different.
 114         return FALSE;
 115     }
 116
 117     // Walk the chunk list and within each chunk walk the frames array until we
 118     // either find a mismatch, or until we reach the end of the call stacks.
 119     while (prevchunk != m_topchunk) {
 120         for (index = 0; index < ((chunk == m_topchunk) ? m_topindex : CALLSTACKCHUNKSIZE); index++) {
 121             if (chunk->frames[index] != otherchunk->frames[index]) {
 122                 // Found a mismatch. They are not equal.
 123                 return FALSE;
 124             }
 125         }
 126         prevchunk = chunk;
 127         chunk = chunk->next;
 128         otherchunk = otherchunk->next;
 129     }
 130
 131     // Reached the end of the call stacks. They are equal.
 132     return TRUE;
 133 }
 134
 135 // operator [] - Random access operator. Retrieves the frame at the specified
 136 //   index.
 137 //
 138 //   Note: We give up a bit of efficiency here, in favor of efficiency of push
 139 //     operations. This is because walking of a CallStack is done infrequently
 140 //     (only if a leak is found), whereas pushing is done very frequently (for
 141 //     each frame in the program's call stack when the program allocates some
 142 //     memory).
 143 //
 144 //  - index (IN): Specifies the index of the frame to retrieve.
 145 //
 146 //  Return Value:
 147 //
 148 //    Returns the program counter for the frame at the specified index. If the
 149 //    specified index is out of range for the CallStack, the return value is
 150 //    undefined.
 151 //
 152 SIZE_T CallStack::operator [] (UINT32 index) const
 153 {
 154     UINT32                    count;
 155     const CallStack::chunk_t *chunk = &m_store;
 156     UINT32                    chunknumber = index / CALLSTACKCHUNKSIZE;
 157
 158     for (count = 0; count < chunknumber; count++) {
 159         chunk = chunk->next;
 160     }
 161
 162     return chunk->frames[index % CALLSTACKCHUNKSIZE];
 163 }
 164
 165 // clear - Resets the CallStack, returning it to a state where no frames have
 166 //   been pushed onto it, readying it for reuse.
 167 //
 168 //   Note: Calling this function does not release any memory allocated to the
 169 //     CallStack. We give up a bit of memory-usage efficiency here in favor of
 170 //     performance of push operations.
 171 //
 172 //  Return Value:
 173 //
 174 //    None.
 175 //
 176 VOID CallStack::clear ()
 177 {
 178     m_size     = 0;
 179     m_topchunk = &m_store;
 180     m_topindex = 0;
 181 }
 182
 183 // dump - Dumps a nicely formatted rendition of the CallStack, including
 184 //   symbolic information (function names and line numbers) if available.
 185 //
 186 //   Note: The symbol handler must be initialized prior to calling this
 187 //     function.
 188 //
 189 //  - showinternalframes (IN): If true, then all frames in the CallStack will be
 190 //      dumped. Otherwise, frames internal to the heap will not be dumped.
 191 //
 192 //  Return Value:
 193 //
 194 //    None.
 195 //
 196 VOID CallStack::dump (BOOL showinternalframes) const
 197 {
 198     DWORD            displacement;
 199     DWORD64          displacement64;
 200     BOOL             foundline;
 201     UINT32           frame;
 202     SYMBOL_INFO     *functioninfo;
 203     LPWSTR           functionname;
 204     SIZE_T           programcounter;
 205     IMAGEHLP_LINE64  sourceinfo = { 0 };
 206     BYTE             symbolbuffer [sizeof(SYMBOL_INFO) + (MAXSYMBOLNAMELENGTH * sizeof(WCHAR)) - 1] = { 0 };
 207
 208     if (m_status & CALLSTACK_STATUS_INCOMPLETE) {
 209         // This call stack appears to be incomplete. Using StackWalk64 may be
 210         // more reliable.
 211         report(L"    HINT: The following call stack may be incomplete. Setting \"StackWalkMethod\"\n"
 212                L"      in the vld.ini file to \"safe\" instead of \"fast\" may result in a more\n"
 213                L"      complete stack trace.\n");
 214     }
 215
 216     // Initialize structures passed to the symbol handler.
 217     functioninfo = (SYMBOL_INFO*)&symbolbuffer;
 218     functioninfo->SizeOfStruct = sizeof(SYMBOL_INFO);
 219     functioninfo->MaxNameLen = MAXSYMBOLNAMELENGTH;
 220     sourceinfo.SizeOfStruct = sizeof(IMAGEHLP_LINE64);
 221
 222     // Iterate through each frame in the call stack.
 223     for (frame = 0; frame < m_size; frame++) {
 224         // Try to get the source file and line number associated with
 225         // this program counter address.
 226         programcounter = (*this)[frame];
 227         EnterCriticalSection(&symbollock);
 228         if ((foundline = SymGetLineFromAddrW64(currentprocess, programcounter, &displacement, &sourceinfo)) == TRUE) {
 229             if (!showinternalframes) {
 230                 _wcslwr_s(sourceinfo.FileName, wcslen(sourceinfo.FileName) + 1);
 231                 if (wcsstr(sourceinfo.FileName, L"afxmem.cpp") ||
 232                     wcsstr(sourceinfo.FileName, L"dbgheap.c") ||
 233                     wcsstr(sourceinfo.FileName, L"malloc.c") ||
 234                     wcsstr(sourceinfo.FileName, L"new.cpp") ||
 235                     wcsstr(sourceinfo.FileName, L"newaop.cpp")) {
 236                     // Don't show frames in files internal to the heap.
 237                     continue;
 238                 }
 239             }
 240         }
 241
 242         // Try to get the name of the function containing this program
 243         // counter address.
 244         if (SymFromAddrW(currentprocess, (*this)[frame], &displacement64, functioninfo)) {
 245             functionname = functioninfo->Name;
 246         }
 247         else {
 248             functionname = L"(Function name unavailable)";
 249         }
 250         LeaveCriticalSection(&symbollock);
 251
 252         // Display the current stack frame's information.
 253         if (foundline) {
 254             report(L"    %s (%d): %s\n", sourceinfo.FileName, sourceinfo.LineNumber, functionname);
 255         }
 256         else {
 257             report(L"    " ADDRESSFORMAT L" (File and line number not available): ", (*this)[frame]);
 258             report(L"%s\n", functionname);
 259         }
 260     }
 261 }
 262
 263 // push_back - Pushes a frame's program counter onto the CallStack. Pushes are
 264 //   always appended to the back of the chunk list (aka the "top" chunk).
 265 //
 266 //   Note: This function will allocate additional memory as necessary to make
 267 //     room for new program counter addresses.
 268 //
 269 //  - programcounter (IN): The program counter address of the frame to be pushed
 270 //      onto the CallStack.
 271 //
 272 //  Return Value:
 273 //
 274 //    None.
 275 //
 276 VOID CallStack::push_back (const SIZE_T programcounter)
 277 {
 278     CallStack::chunk_t *chunk;
 279
 280     if (m_size == m_capacity) {
 281         // At current capacity. Allocate additional storage.
 282         chunk = new CallStack::chunk_t;
 283         chunk->next = NULL;
 284         m_topchunk->next = chunk;
 285         m_topchunk = chunk;
 286         m_topindex = 0;
 287         m_capacity += CALLSTACKCHUNKSIZE;
 288     }
 289     else if (m_topindex == CALLSTACKCHUNKSIZE) {
 290         // There is more capacity, but not in this chunk. Go to the next chunk.
 291         // Note that this only happens if this CallStack has previously been
 292         // cleared (clearing resets the data, but doesn't give up any allocated
 293         // space).
 294         m_topchunk = m_topchunk->next;
 295         m_topindex = 0;
 296     }
 297
 298     m_topchunk->frames[m_topindex++] = programcounter;
 299     m_size++;
 300 }
 301
 302 // getstacktrace - Traces the stack as far back as possible, or until 'maxdepth'
 303 //   frames have been traced. Populates the CallStack with one entry for each
 304 //   stack frame traced.
 305 //
 306 //   Note: This function uses a very efficient method to walk the stack from
 307 //     frame to frame, so it is quite fast. However, unconventional stack frames
 308 //     (such as those created when frame pointer omission optimization is used)
 309 //     will not be successfully walked by this function and will cause the
 310 //     stack trace to terminate prematurely.
 311 //
 312 //  - maxdepth (IN): Maximum number of frames to trace back.
 313 //
 314 //  - framepointer (IN): Frame (base) pointer at which to begin the stack trace.
 315 //      If NULL, then the stack trace will begin at this function.
 316 //
 317 //  Return Value:
 318 //
 319 //    None.
 320 //
 321 VOID FastCallStack::getstacktrace (UINT32 maxdepth, SIZE_T *framepointer)
 322 {
 323     UINT32  count = 0;
 324
 325     if (framepointer == NULL) {
 326         // Begin the stack trace with the current frame. Obtain the current
 327         // frame pointer.
 328         FRAMEPOINTER(framepointer);
 329     }
 330
 331     while (count < maxdepth) {
 332         if ((SIZE_T*)*framepointer < framepointer) {
 333             if ((SIZE_T*)*framepointer == NULL) {
 334                 // Looks like we reached the end of the stack.
 335                 break;
 336             }
 337             else {
 338                 // Invalid frame pointer. Frame pointer addresses should always
 339                 // increase as we move up the stack.
 340                 m_status |= CALLSTACK_STATUS_INCOMPLETE;
 341                 break;
 342             }
 343         }
 344         if ((SIZE_T)*framepointer & (sizeof(SIZE_T*) - 1)) {
 345             // Invalid frame pointer. Frame pointer addresses should always
 346             // be aligned to the size of a pointer. This probably means that
 347             // we've encountered a frame that was created by a module built with
 348             // frame pointer omission (FPO) optimization turned on.
 349             m_status |= CALLSTACK_STATUS_INCOMPLETE;
 350             break;
 351         }
 352         if (IsBadReadPtr((SIZE_T*)*framepointer, sizeof(SIZE_T*))) {
 353             // Bogus frame pointer. Again, this probably means that we've
 354             // encountered a frame built with FPO optimization.
 355             m_status |= CALLSTACK_STATUS_INCOMPLETE;
 356             break;
 357         }
 358         count++;
 359         push_back(*(framepointer + 1));
 360         framepointer = (SIZE_T*)*framepointer;
 361     }
 362 }
 363
 364 // getstacktrace - Traces the stack as far back as possible, or until 'maxdepth'
 365 //   frames have been traced. Populates the CallStack with one entry for each
 366 //   stack frame traced.
 367 //
 368 //   Note: This function uses a documented Windows API to walk the stack. This
 369 //     API is supposed to be the most reliable way to walk the stack. It claims
 370 //     to be able to walk stack frames that do not follow the conventional stack
 371 //     frame layout. However, this robustness comes at a cost: it is *extremely*
 372 //     slow compared to walking frames by following frame (base) pointers.
 373 //
 374 //  - maxdepth (IN): Maximum number of frames to trace back.
 375 //
 376 //  - framepointer (IN): Frame (base) pointer at which to begin the stack trace.
 377 //      If NULL, then the stack trace will begin at this function.
 378 //
 379 //  Return Value:
 380 //
 381 //    None.
 382 //
 383 VOID SafeCallStack::getstacktrace (UINT32 maxdepth, SIZE_T *framepointer)
 384 {
 385     DWORD        architecture;
 386     CONTEXT      context;
 387     UINT32       count = 0;
 388     STACKFRAME64 frame;
 389     SIZE_T       programcounter;
 390     SIZE_T       stackpointer;
 391
 392     if (framepointer == NULL) {
 393         // Begin the stack trace with the current frame. Obtain the current
 394         // frame pointer.
 395         FRAMEPOINTER(framepointer);
 396     }
 397
 398     // Get the required values for initialization of the STACKFRAME64 structure
 399     // to be passed to StackWalk64(). Required fields are AddrPC and AddrFrame.
 400 #if defined(_M_IX86) || defined(_M_X64)
 401     architecture   = X86X64ARCHITECTURE;
 402     programcounter = *(framepointer + 1);
 403     stackpointer   = *framepointer;  // An approximation.
 404     context.BPREG  = *framepointer;
 405     context.IPREG  = programcounter;
 406     context.SPREG  = stackpointer;
 407 #else
 408 // If you want to retarget Visual Leak Detector to another processor
 409 // architecture then you'll need to provide architecture-specific code to
 410 // obtain the program counter and stack pointer from the given frame pointer.
 411 #error "Visual Leak Detector is not supported on this architecture."
 412 #endif // _M_IX86 || _M_X64
 413
 414     // Initialize the STACKFRAME64 structure.
 415     memset(&frame, 0x0, sizeof(frame));
 416     frame.AddrFrame.Offset = *framepointer;
 417     frame.AddrFrame.Mode   = AddrModeFlat;
 418     frame.AddrPC.Offset    = programcounter;
 419     frame.AddrPC.Mode      = AddrModeFlat;
 420     frame.AddrStack.Offset = stackpointer;
 421     frame.AddrStack.Mode   = AddrModeFlat;
 422
 423     // Walk the stack.
 424     EnterCriticalSection(&stackwalklock);
 425     while (count < maxdepth) {
 426         count++;
 427         if (!StackWalk64(architecture, currentprocess, currentthread, &frame, &context, NULL,
 428                          SymFunctionTableAccess64, SymGetModuleBase64, NULL)) {
 429             // Couldn't trace back through any more frames.
 430             break;
 431         }
 432         if (frame.AddrFrame.Offset == 0) {
 433             // End of stack.
 434             break;
 435         }
 436
 437         // Push this frame's program counter onto the CallStack.
 438         push_back((SIZE_T)frame.AddrPC.Offset);
 439     }
 440     LeaveCriticalSection(&stackwalklock);
 441 }