1 krisbash 1.1 #include "config.h"
  2              
  3              #if defined(CONFIG_HAVE_BACKTRACE)
  4              
  5              #define PSAPI_VERSION 2
  6              
  7              #ifdef _MSC_VER
  8                  #include <windows.h>
  9                  #include <psapi.h>
 10                  #include <strsafe.h>
 11              #else
 12                  #include <execinfo.h>
 13                  #include <dlfcn.h>
 14                  #include <sys/types.h>
 15                  #include <sys/stat.h>
 16                  #include <unistd.h>
 17              #endif
 18              
 19              #include "Globals.h"
 20              #include "Frame.h"
 21              #include <pal/strings.h>
 22 krisbash 1.1 
 23              using namespace TestSystem;
 24              
 25              LocalModule FrameCache::s_modules[FrameCache::ModuleCount];
 26              size_t FrameCache::s_hash[HashSize];
 27              
 28              void FrameCache::Reset()
 29              {
 30              	m_spinlock = 0;
 31                  m_dataUsed = 0;
 32                  m_modulesUsed = 0;
 33                  m_addressUsed = 0;
 34                  m_startMask = 0;
 35              }
 36              
 37              bool FrameCache::ShouldFault(ptrdiff_t limit, ptrdiff_t attempt, _Out_ bool &filtered)
 38              {
 39                  Atomic_Lock(&m_spinlock);
 40              
 41                  //unsigned __int64 start = ReadTimeStampCounter();
 42                  int count = 0;
 43 krisbash 1.1     void **stackFrames = NULL;
 44              #ifdef _MSC_VER
 45                  void *actualStackFrames[DesiredFrames];
 46                  count = CaptureStackBackTrace(SkippedFrames, DesiredFrames, actualStackFrames, NULL);
 47                  stackFrames = actualStackFrames;
 48              #else
 49                  // backtrace does not let you specify skippedFrames, so here I am grabbing (SkippedFrames + DesiredFrames) 
 50                  // and then skipping the unneeded frames myself to have same behaviour both on windows and non-windows 
 51                  void *actualStackFrames[SkippedFrames + DesiredFrames];
 52                  count = backtrace(actualStackFrames, DesiredFrames + SkippedFrames);
 53                  stackFrames = actualStackFrames + SkippedFrames;
 54                  count = count - SkippedFrames;
 55              #endif
 56              
 57                  bool shouldFault = false;
 58                  filtered = false;
 59              
 60                  GetGlobals().GetStats().stackLookups++;
 61                  GetGlobals().GetStats().frameLookups += count;
 62              
 63                  //Process-local frame hash (avoids translation).
 64 krisbash 1.1     int newCount = 0;
 65                  for (int i = 0; i < count; i++)
 66                  {
 67                      size_t address = reinterpret_cast<size_t>(stackFrames[i]);
 68                      int hash = static_cast<int>(address & HashMask);
 69                      if (s_hash[hash] != address)
 70                      {
 71                          //Don't update the table yet.
 72                          //We may or may not actually fault this location.
 73                          stackFrames[newCount++] = reinterpret_cast<void *>(address);
 74                      }
 75                  }
 76                  GetGlobals().GetStats().frameHashHits += (count - newCount);
 77                  count = newCount;
 78              
 79                  for (int i = 0; i < count; i++)
 80                  {
 81                      size_t address = reinterpret_cast<size_t>(stackFrames[i]);
 82                      int hash = static_cast<int>(address & HashMask);
 83                      unsigned key = TranslateAddress(stackFrames[i]);
 84                      if (!FindRecord(key))
 85 krisbash 1.1         {
 86                          //If the attempt number is less than the previous one,
 87                          //  then this could be orphaned code.
 88                          if (attempt >= limit)
 89                          {
 90                              //Make sure the process-local hash table is updated.
 91                              s_hash[hash] = address;
 92                              shouldFault = true;
 93                              InsertRecord(key);
 94                          }
 95                          else
 96                          {
 97                              filtered = true;
 98                          }
 99                      }
100                      else
101                      {
102                          //Make sure the process-local hash table is updated.
103                          s_hash[hash] = address;
104                      }
105                  }
106 krisbash 1.1 
107                  //unsigned __int64 stop = ReadTimeStampCounter();
108                  //GetGlobals().GetStats().stackTicks += static_cast<unsigned>(stop - start);
109                  Atomic_Unlock(&m_spinlock);
110                  return shouldFault;
111              }
112              
113              unsigned FrameCache::TranslateAddress(_In_ void *pointer)
114              {
115                  size_t address = reinterpret_cast<size_t>(pointer);
116                  unsigned i;
117              
118                  //First check already known address ranges.
119                  for (i = 0; i < m_modulesUsed; i++)
120                  {
121                      LocalModule &local = s_modules[i];
122                      if (address >= local.base && address < local.end)
123                      {
124                          break;
125                      }
126                  }
127 krisbash 1.1 
128                  if (i == m_modulesUsed)
129                  {
130                  	char buffer[MAX_PATH] = "<unknown>";
131                  	DWORD sizeOfImage = 0;
132                  	void *baseOfDll = 0;
133              #ifdef _MSC_VER
134                      //Determine which module name this address belongs to.
135                      HMODULE handle;
136                      MODULEINFO info;
137              
138                      if (!GetModuleHandleEx(
139                                  GET_MODULE_HANDLE_EX_FLAG_FROM_ADDRESS |
140                                  GET_MODULE_HANDLE_EX_FLAG_UNCHANGED_REFCOUNT,
141                                  reinterpret_cast<LPCTSTR>(address),
142                                  &handle))
143                      {
144                          return 0;
145                      }
146              
147                      GetModuleFileNameA(handle, buffer, sizeof(buffer));
148 krisbash 1.1         K32GetModuleInformation(GetCurrentProcess(), handle, &info, sizeof(info));
149                      sizeOfImage = info.SizeOfImage;
150                      baseOfDll = info.lpBaseOfDll;
151              #else
152                      Dl_info myDlInfo;        
153                      if(!dladdr(pointer, &myDlInfo))
154                      {
155                      	return 0;
156                      }
157                      Strlcpy(buffer, myDlInfo.dli_fname, MAX_PATH);
158                      baseOfDll = myDlInfo.dli_fbase;
159                      struct stat dli_fname_stat;
160                      if(stat(buffer, &dli_fname_stat) != 0)
161                      {
162                      	return 0;
163                      }
164                      sizeOfImage = (DWORD)dli_fname_stat.st_size;
165              
166              #endif
167                      i = FindModule(buffer, sizeOfImage);
168                      LocalModule &local = s_modules[i];
169 krisbash 1.1         local.base = reinterpret_cast<size_t>(baseOfDll);
170              
171              #ifdef _MSC_VER
172                      local.end = local.base + sizeOfImage;
173              #else
174                      // on non-windows we have not found a way to get exact range of library loaded addresses in memory so it is better to  
175                      // keep updating the local.end as we know an address at a time. Also the current assumption here is that if a shared lib is loaded between addresses x to x + y
176                      // then there is no other shared library loaded in between (x, x+y) range; if this does not hold good; then we could be in trouble with the windows based approach of having local.base and local.end
177                      if(local.end < address)
178                      {
179                          local.end = address;
180                      }
181              #endif
182                  }
183              
184                  LocalModule &local = s_modules[i];
185                  GlobalModule &module = m_modules[i];
186                  size_t diff = address - local.base;
187                  unsigned offset = static_cast<unsigned>(diff);
188                  return offset + module.base;
189              }
190 krisbash 1.1 
191              unsigned FrameCache::FindModule(_In_z_ char *name, unsigned size)
192              {
193                  for (unsigned i = 0; i < m_modulesUsed; i++)
194                  {
195                      //N.B. This comparison must be case-insensitive.
196                      //  GetModuleFileName returns names with different cases.
197                      GlobalModule &module = m_modules[i];
198                      if (Strcasecmp(name, module.name) == 0 && size == module.size)
199                      {
200                          return i;
201                      }
202                  }
203              
204                  if (m_modulesUsed == ModuleCount)
205                  {
206                      throw Exception();
207                  }
208              
209                  //Not found, so create a new GlobalModule.
210                  unsigned i = m_modulesUsed++;
211 krisbash 1.1     GlobalModule &module = m_modules[i];
212                  Strlcpy(module.name, name, MAX_PATH);
213              
214                  module.base = m_addressUsed;
215                  module.size = size;
216                  m_addressUsed += size;
217                  return i;
218              }
219              
220              bool FrameCache::FindRecord(unsigned key)
221              {
222                  unsigned level = 0;
223              
224                  //The cache has no record in slot 0.
225                  //Bit i (0-15) in m_dataUsed indicates that slots [2^i, 2*2^i) are in use.
226                  unsigned sections = m_dataUsed;
227                  for (unsigned mask = m_startMask; sections != 0; mask >>= 1)
228                  {
229                      if ((sections & mask) == 0)
230                      {
231                          continue;
232 krisbash 1.1         }
233              
234                      sections &= ~mask;
235                      if (BinarySearch(key, mask, mask + mask))
236                      {
237                          GetGlobals().GetStats().frameHits[level]++;
238                          return true;
239                      }
240              
241                      level++;
242                  }
243              
244                  return false;
245              }
246              
247              bool FrameCache::BinarySearch(unsigned key, int low, int high)
248              {
249                  while (low < high - 1)
250                  {
251                      int middle = (low + high) >> 1;
252              #ifdef _MSC_VER
253 krisbash 1.1 #pragma prefast(push)
254              #pragma prefast(disable:26001)
255              #endif
256                      if (key >= m_data[middle].key)
257              #ifdef _MSC_VER
258              #pragma prefast(pop)
259              #endif
260                      {
261                          low = middle;
262                      }
263                      else
264                      {
265                          high = middle;
266                      }
267                  }
268              
269                  //Four possible outcomes:
270                  //1) key > everything. low == originalHigh - 1.
271                  //2) key < everything. high == originalLow + 1.
272                  //3) key is between two nodes.
273                  //4) key matches data[low].
274 krisbash 1.1     //
275                  //Total number of comparisons is 1 + log N.
276                  return key == m_data[low].key;
277              }
278              
279              void FrameCache::InsertRecord(unsigned key)
280              {
281                  GetGlobals().GetStats().frameInsertions++;
282              
283                  //Bump the count.
284                  //This determines which sections will be merged.
285                  if (m_dataUsed == CacheSize - 1)
286                  {
287                      //The cache is full.
288                      //Discard the bottom half completely.
289                      m_dataUsed = CacheLastSection;
290                  }
291              
292                  unsigned oldCount = m_dataUsed++;
293              
294                  //Determine the section to merge into.
295 krisbash 1.1     int low = m_dataUsed & ~oldCount;
296              
297                  if (static_cast<unsigned>(low) > m_startMask)
298                  {
299                      m_startMask = low;
300                  }
301              
302                  //Insert the record in the first slot in the merged range.
303                  m_data[low].key = key;
304              
305                  for (int src = 1; src != low; src += src)
306                  {
307                      MergeRecords(low, src, src); 
308                  }
309              }
310              
311              void FrameCache::MergeRecords(int low, int src, int size)
312              {
313                  //Merges [low, low+size) and [src, src+size) into [low, low+2*size).
314                  //Always copy from high to low.
315                  int cursor1 = low + size - 1;
316 krisbash 1.1     int cursor2 = src + size - 1;
317                  for (int dest = low + size + size - 1; dest >= low; dest--)
318                  {
319                      if (cursor2 < src)
320                      {
321                          //Optimization. The remaining items are already in place!
322                          return;
323                      }
324              
325                      if (cursor1 < low ||
326                          m_data[cursor1].key <= m_data[cursor2].key)
327                      {
328                          m_data[dest] = m_data[cursor2--];
329                      }
330                      else
331                      {
332                          m_data[dest] = m_data[cursor1--];
333                      }
334                  }
335              }
336              #endif