// profiler.c
//
// Time-stamp: <28/04/02 09:06:12 keuchel@netwave.de>
//
// Rewritten by Stephane Rouleau <s.rouleau@videotron.ca>. 

#include <windows.h>

#include <tchar.h>
#include <stdio.h>

#include "profiler.h"

#if !defined( _UNDER_CE )
#  define PROFILE_WITH_EXCEPTIONS
#else
#  undef PROFILE_WITH_EXCEPTIONS
#endif

#define MAXTHREADS       32
#define MAXCALLS       8000
#define MAXSTACK        500
#define MAXCHILD        160
#define CHILDCHUNK      160

#define pctszPROFILER_KEY              _T("Software\\CEProfiler")
#define pctszPROFILER_TIMING           _T("Profile")
#define pctszPROFILER_CHILDREN         _T("ProfileChildren")
#define pctszPROFILER_UNIQUE_REPORTS   _T("UniqueReports")

typedef struct _childtime {
   __int64  time;          // Time spent in this child (from the parent)
   DWORD    addr;          // addr of the child
   DWORD    count;         // # of times that we used this child.
} CHILDTIME;

typedef struct _callent {
  __int64   time;                // Cumulative time, including children
  __int64   childtime;           // Cumulative time spent in children
  CHILDTIME *paChildren;         // Time spent in the children...
  DWORD     addr;                // approximate function start address
  DWORD     count;               // call count
  int       iChildCount;         // count in array of childs
  int       iChildCapacity;      // Space allocated in array
} CALLENT;                       // sizeof: 16

// We leave the CALLENT array unsorted (so the stack object can point to it
// directly), and use this to do binary searches. We store the addr here as
// well to speed up comparisons.
typedef struct _callentidx {
   DWORD    addr;
   CALLENT  *pCall;
} CALLENTIDX;

typedef struct tagSTACK {
   __int64  start;         // Time we entered the function
   CALLENT  *pCall;        // Associated call record; includes function addr
#if defined( PROFILE_WITH_EXCEPTIONS )
   DWORD    frameptr;      // Parent frame ptr
#endif
   DWORD    retaddr;       // Return address; unused on SH3
} STACK;

// Similar to a TLS but "home-made" -- we don't have anywhere to store the
// thread's TLS index, so we'd have to look for it everytime.  Instead we
// store the thread's state in here.
typedef struct tagTHREAD_STATE {
   STACK    aStack[MAXSTACK];  // MAXSTACK * 16
   DWORD    dwThreadID;        // 4
   DWORD    dwStackIndex;      // 4
} THREAD_STATE;                //

static HANDLE           sthHeap;
static CALLENT          *stpCalls;
static CALLENTIDX       *stpCallsIndex;
static THREAD_STATE     *stpThreads;
static DWORD            stdwThreadCount;
static int              stiCallCount;
static CRITICAL_SECTION xLock;
static BOOL             stboProfileTiming = TRUE;
static BOOL             stboProfileChildren = TRUE;

// Returns TRUE if the key's not there
static BOOL stboReadRegistryBoolean(const TCHAR *pctszKey,
                                    const TCHAR *pctszValue) {
   BOOL boValue = TRUE;
   HKEY hKey;

   if( RegOpenKeyEx(HKEY_LOCAL_MACHINE, pctszKey,
                    0, 0, &hKey) == ERROR_SUCCESS )  {
      DWORD dwType, dwSize, dwData;

      dwSize = sizeof(DWORD);

      if( RegQueryValueEx(hKey, pctszValue, NULL, &dwType, (LPBYTE) &dwData,
                          &dwSize) == ERROR_SUCCESS ) {
         boValue = dwData ? TRUE : FALSE;
      }

      RegCloseKey(hKey);
   }

   return boValue;
}

// dwAddr:  function calling penter (or close enough)
// dwAddr2: return addr of function calling penter (SH3: invalid)

static THREAD_STATE *stpGetThreadState() {
   static BOOL stboInitialized;
   DWORD  dwThreadID;
   BOOL   boFailure;
   DWORD  dwThreadIndex = 0;
   THREAD_STATE *pState = stpThreads;

   if( !stboInitialized ) {
      stboInitialized = TRUE;

      stboProfileTiming = stboReadRegistryBoolean(pctszPROFILER_KEY,
                                                  pctszPROFILER_TIMING);
      stboProfileChildren = stboReadRegistryBoolean(pctszPROFILER_KEY,
                                                    pctszPROFILER_CHILDREN);

      InitializeCriticalSection(&xLock);

      sthHeap  = HeapCreate(0, 0, 0);
      stpCalls = HeapAlloc(sthHeap, HEAP_ZERO_MEMORY,
                           sizeof(CALLENT) * MAXCALLS);
      stpCallsIndex = HeapAlloc(sthHeap, HEAP_ZERO_MEMORY,
                                sizeof(CALLENTIDX) * MAXCALLS);

      if( !(stpCalls && stpCallsIndex) ) {
         // This way we save a bunch of "ifs" down the line.
         exit(EXIT_FAILURE);
      }

      //atexit(__profiler_dump);
   }

   dwThreadID = GetCurrentThreadId();
   EnterCriticalSection(&xLock);

   while( dwThreadIndex < stdwThreadCount &&
          pState->dwThreadID != dwThreadID )
      ++dwThreadIndex, ++pState;

   if( dwThreadIndex == stdwThreadCount ) {
      if( dwThreadIndex < MAXTHREADS ) {
         // HeapAlloc does not call SetLastError on failure; ReAlloc does.
         if( !stpThreads ) {
            stpThreads = HeapAlloc(sthHeap, HEAP_ZERO_MEMORY,
                                   sizeof(THREAD_STATE));
            boFailure  = stpThreads == NULL;
         } else {
            stpThreads = HeapReAlloc(sthHeap, HEAP_ZERO_MEMORY, stpThreads,
                                     (dwThreadIndex+1) * sizeof(THREAD_STATE));
            boFailure  = GetLastError() != NO_ERROR;
         }

         if( boFailure ) {
            pState = NULL;
         } else {
            pState = &stpThreads[stdwThreadCount++];

            pState->dwThreadID = dwThreadID;
         }
      } else {
         pState = NULL;
      }
   } else {
      // NOP -- we have the proper thread state object.
   }

   LeaveCriticalSection(&xLock);

   return pState;
}

static CALLENTIDX *find_callent(DWORD dwAddr) {
   // Copy of STL's lower_bound()
   int iHalf;
   CALLENTIDX *pMiddle;
   CALLENTIDX *pFirst = stpCallsIndex;
   int iCount = stiCallCount;

  while (iCount > 0) {
    iHalf   = iCount >> 1;
    pMiddle = pFirst + iHalf;

    if (pMiddle->addr < dwAddr) {
       pFirst = ++pMiddle;
       iCount = iCount - iHalf - 1;
    } else {
       iCount = iHalf;
    }
  }

  return (pFirst - stpCallsIndex < MAXCALLS) ? pFirst : NULL;
}

void __stdcall __handle_penter(DWORD dwAddr, DWORD dwAddr2
#if defined( PROFILE_WITH_EXCEPTIONS
                               , DWORD dwParentFrame
#endif
                               ) {
   int          i;
   DWORD        dwIndex;
   CALLENTIDX   *pCallIdx;
   THREAD_STATE *pState = stpGetThreadState();
   CALLENT      *pCall = stpCalls;

   if( !pState )
      return;

   // Always increment -- this way on exit we know when we're back within our
   // stack limit.
   dwIndex = pState->dwStackIndex++;

   if( dwIndex >= MAXSTACK )
      return;

   // Associate function record
   EnterCriticalSection(&xLock);

   pCallIdx = find_callent(dwAddr);

   if( pCallIdx ) {
      if( pCallIdx->addr != dwAddr ) {
         i = stiCallCount - (pCallIdx - stpCallsIndex);

         if( i ) {
            memmove(pCallIdx + 1, pCallIdx, i * sizeof(CALLENTIDX));
         }

         pCallIdx->pCall         = &stpCalls[stiCallCount++];
         pCallIdx->pCall->addr   = pCallIdx->addr = dwAddr;
      }

      pState->aStack[dwIndex].pCall = pCallIdx->pCall;

      ++pCallIdx->pCall->count;
   } else {
      pState->aStack[dwIndex].pCall = NULL;
   }

   LeaveCriticalSection(&xLock);

   if( stboProfileTiming )
      QueryPerformanceCounter((LARGE_INTEGER *) &pState->aStack[dwIndex].start);

   pState->aStack[dwIndex].retaddr  = dwAddr2;

#if defined( PROFILE_WITH_EXCEPTIONS )
   pState->aStack[dwIndex].frameptr = dwParentFrame;
#endif
}

static CHILDTIME *find_child(CALLENT *pCaller, DWORD dwAddr) {
   int iHalf;
   CHILDTIME *pMiddle;
   CHILDTIME *pFirst = pCaller->paChildren;
   int iCount = pCaller->iChildCount;

   while (iCount > 0) {
      iHalf   = iCount >> 1;
      pMiddle = pFirst + iHalf;

      if (pMiddle->addr < dwAddr) {
         pFirst = ++pMiddle;
         iCount = iCount - iHalf - 1;
      } else {
         iCount = iHalf;
      }
   }

   return pFirst;
}

static CHILDTIME *insert_child(CALLENT *pCaller, CHILDTIME *pChild,
                               DWORD addr) {
   BOOL boFailure;
   int iIndex = pChild - pCaller->paChildren;
   int iCount;

   if( pCaller->iChildCount == pCaller->iChildCapacity ) {
      if( pCaller->iChildCapacity == MAXCHILD )
         return NULL;

      if( !pCaller->paChildren ) {
         pCaller->paChildren = HeapAlloc(sthHeap, HEAP_ZERO_MEMORY,
                                         CHILDCHUNK * sizeof(CHILDTIME));
         boFailure = pCaller->paChildren == NULL;
      } else {
         pCaller->paChildren = HeapReAlloc(sthHeap, HEAP_ZERO_MEMORY,
                                           pCaller->paChildren,
                                          (pCaller->iChildCapacity+CHILDCHUNK) *
                                           sizeof(CHILDTIME));
         boFailure = GetLastError() != NO_ERROR;
      }

      // HeapAlloc does not call SetLastError on failure; ReAlloc does.
      if( boFailure ) {
         DebugBreak();

         return NULL;
      }

      pCaller->iChildCapacity += CHILDCHUNK;
      pChild = pCaller->paChildren + iIndex;
   }

   iCount = pCaller->iChildCount - iIndex;

   if( iCount ) {
      memmove(pChild + 1, pChild, iCount * sizeof(CHILDTIME));
   }

   ++pCaller->iChildCount;
   pChild->addr   = addr;
   pChild->time   = 0;
   pChild->count  = 0;

   return pChild;
}

#if defined( PROFILE_WITH_EXCEPTIONS )
DWORD __stdcall __handle_return(DWORD dwParentFrame) {
#else
DWORD __stdcall __handle_return(void) {
#endif
   DWORD       dwIndex;
   CHILDTIME   *pChild;
   CALLENT     *pThisCall, *pParentCall;
   __int64     TimeEnd;
   __int64     TimeElapsed = 0;

   THREAD_STATE *pState = stpGetThreadState();

   if( !pState )
      return 0;                        // ??

   dwIndex = --pState->dwStackIndex;

   if( dwIndex >= MAXSTACK )
      return 0;                        // ??

#if defined( PROFILE_WITH_EXCEPTIONS )
   while( dwIndex && pState->aStack[dwIndex].frameptr != dwParentFrame )
      --dwIndex;
#endif

   if( pState->aStack[dwIndex].pCall ) {
      if( stboProfileTiming ) {
         QueryPerformanceCounter((LARGE_INTEGER *) &TimeEnd);

         TimeElapsed = TimeEnd - pState->aStack[dwIndex].start;

         EnterCriticalSection(&xLock);

         pThisCall = pState->aStack[dwIndex].pCall;
         pThisCall->time += TimeElapsed;

         // Update the previous's function "child time" total
         if( dwIndex && pState->aStack[dwIndex-1].pCall ) {
            pParentCall = pState->aStack[dwIndex-1].pCall;

            pParentCall->childtime += TimeElapsed;

            // Keep an accurate tab per children?
            if( stboProfileChildren ) {
               pChild = find_child(pParentCall, pThisCall->addr);

               if( !(pChild && pChild->addr == pThisCall->addr) ) {
                  pChild = insert_child(pParentCall, pChild, pThisCall->addr);
               }

               if( pChild ) {
                  pChild->time += TimeElapsed;
                  ++pChild->count;
               }
            }
         }

         LeaveCriticalSection(&xLock);
      }
   }

   return pState->aStack[dwIndex].retaddr;
}

static int __cdecl callent_cmp_count(const CALLENT *p1, const CALLENT *p2) {
   return (int) (p2->count - p1->count);
}

static int __cdecl callent_cmp_time(const CALLENT *p1, const CALLENT *p2) {
   return (int) (p2->time - p1->time);
}

void __cdecl __profiler_dump() {
   TCHAR tszFileName[256];
   HANDLE hFile;
   char szBuf[256];
   DWORD dwWritten;
   TCHAR tszModule[256];
   int cnt = 0;
   __int64     total, child, freq;
   CALLENT     *pCurrent, *pEnd;
   CHILDTIME   *pCurrentChild, *pEndChild;

   int (__cdecl *pfnCompareFunc)(const CALLENT *, const CALLENT *);

   if( stboProfileTiming ) {
      QueryPerformanceFrequency((LARGE_INTEGER *) &freq);
   }

   DeleteCriticalSection(&xLock);

   /* Always use the same filename? */
   if( stboReadRegistryBoolean(pctszPROFILER_KEY,
                               pctszPROFILER_UNIQUE_REPORTS) ) {
      while(1) {
         wsprintf(tszFileName, _T("\\profile%d.txt"), cnt++);
         if(GetFileAttributes(tszFileName) == (DWORD) -1)
            break;
      }
   } else {
      lstrcpy(tszFileName, _T("\\profile.txt"));
   }

   hFile = CreateFile(tszFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS,
                      FILE_ATTRIBUTE_NORMAL, NULL);

   if( hFile == INVALID_HANDLE_VALUE) {
      GetLastError();
      return;
   }

   GetModuleFileName(NULL, tszModule,
                     sizeof(tszModule) / sizeof(*tszFileName));

#if defined( UNICODE )
   sprintf(szBuf, "# Profile of %ls\n", tszModule);
#else
   sprintf(szBuf, "# Profile of %s\n", tszModule);
#endif

   WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf), &dwWritten, NULL);

   sprintf(szBuf, "# Timer resolution: %I64u\n", freq);
   WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf), &dwWritten, NULL);

   pfnCompareFunc = stboProfileTiming ? callent_cmp_time : callent_cmp_count;
   qsort(stpCalls, stiCallCount, sizeof(CALLENT), pfnCompareFunc);

   pEnd = stpCalls + stiCallCount;

   if( stboProfileTiming ) {
      for( pCurrent = stpCalls; pCurrent < pEnd; ++pCurrent ) {
         total = pCurrent->time;
         child = pCurrent->childtime;

         sprintf(szBuf, "%08x:%lu:%I64u:%I64u\n", pCurrent->addr,
                 pCurrent->count, total, child);

         WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf),
                   &dwWritten, NULL);

         if( stboProfileChildren && pCurrent->paChildren ) {
            pEndChild = pCurrent->paChildren + pCurrent->iChildCount;

            for( pCurrentChild = pCurrent->paChildren;
                 pCurrentChild < pEndChild; ++pCurrentChild ) {
               sprintf(szBuf, "C> %08x:%lu:%I64u\n", pCurrentChild->addr,
                       pCurrentChild->count, pCurrentChild->time);

               WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf),
                         &dwWritten, NULL);
            }
         }
      }
   } else {
      for( pCurrent = stpCalls; pCurrent < pEnd; ++pCurrent ) {
         sprintf(szBuf, "%08x:%lu\n", pCurrent->addr, pCurrent->count);

         WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf),
                   &dwWritten, NULL);

         if( stboProfileChildren && pCurrent->paChildren ) {
            pEndChild = pCurrent->paChildren + pCurrent->iChildCount;

            for( pCurrentChild = pCurrent->paChildren;
                 pCurrentChild < pEndChild; ++pCurrentChild ) {
               sprintf(szBuf, "C> %08x:%lu\n", pCurrentChild->addr,
                       pCurrentChild->count);

               WriteFile(hFile, szBuf, strlen(szBuf) * sizeof(*szBuf),
                         &dwWritten, NULL);
            }
         }
      }
   }

   CloseHandle(hFile);

#if 0
   HeapDestroy(sthHeap);               // Free everything at once.
#endif
}

/*
   $Log: profiler.c $
   Revision 1.3  2002/04/15 23:43:47  Stephane
   When exceptions are enabled, we need to work a bit harder to make sure we are
   going back to the proper function.
   Revision 1.2  2002/04/15 17:00:51  Stephane
   Modified to support profiling of multiple threads, and recursion support.
   Generate profile file in ANSI, not Unicode for convenience.
   PROFILE_TIMING is decided at runtime now; not compile time, by using the
   registry.
   Also modified to produce time spent in child functions.
   Revision 1.1  2002/03/07 15:28:36  Stephane
   Initial revision
*/
