contrib/compiler-rt/lib/esan/cache_frag.cpp

   1 //===-- cache_frag.cpp ----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is a part of EfficiencySanitizer, a family of performance tuners.
  11 //
  12 // This file contains cache fragmentation-specific code.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "esan.h"
  16 #include "esan_flags.h"
  17 #include "sanitizer_common/sanitizer_addrhashmap.h"
  18 #include "sanitizer_common/sanitizer_common.h"
  19 #include "sanitizer_common/sanitizer_placement_new.h"
  20 #include <string.h>
  21
  22 namespace __esan {
  23
  24 //===-- Struct field access counter runtime -------------------------------===//
  25
  26 // This should be kept consistent with LLVM's EfficiencySanitizer StructInfo.
  27 struct StructInfo {
  28   const char *StructName;
  29   u32 Size;
  30   u32 NumFields;
  31   u32 *FieldOffset;           // auxiliary struct field info.
  32   u32 *FieldSize;             // auxiliary struct field info.
  33   const char **FieldTypeName; // auxiliary struct field info.
  34   u64 *FieldCounters;
  35   u64 *ArrayCounter;
  36   bool hasAuxFieldInfo() { return FieldOffset != nullptr; }
  37 };
  38
  39 // This should be kept consistent with LLVM's EfficiencySanitizer CacheFragInfo.
  40 // The tool-specific information per compilation unit (module).
  41 struct CacheFragInfo {
  42   const char *UnitName;
  43   u32 NumStructs;
  44   StructInfo *Structs;
  45 };
  46
  47 struct StructCounter {
  48   StructInfo *Struct;
  49   u64 Count; // The total access count of the struct.
  50   u64 Ratio; // Difference ratio for the struct layout access.
  51 };
  52
  53 // We use StructHashMap to keep track of an unique copy of StructCounter.
  54 typedef AddrHashMap<StructCounter, 31051> StructHashMap;
  55 struct Context {
  56   StructHashMap StructMap;
  57   u32 NumStructs;
  58   u64 TotalCount; // The total access count of all structs.
  59 };
  60 static Context *Ctx;
  61
  62 static void reportStructSummary() {
  63   // FIXME: provide a better struct field access summary report.
  64   Report("%s: total struct field access count = %llu\n", SanitizerToolName,
  65          Ctx->TotalCount);
  66 }
  67
  68 // FIXME: we are still exploring proper ways to evaluate the difference between
  69 // struct field counts.  Currently, we use a simple formula to calculate the
  70 // difference ratio: V1/V2.
  71 static inline u64 computeDifferenceRatio(u64 Val1, u64 Val2) {
  72   if (Val2 > Val1) {
  73     Swap(Val1, Val2);
  74   }
  75   if (Val2 == 0)
  76     Val2 = 1;
  77   return (Val1 / Val2);
  78 }
  79
  80 static void reportStructCounter(StructHashMap::Handle &Handle) {
  81   const u32 TypePrintLimit = 512;
  82   const char *type, *start, *end;
  83   StructInfo *Struct = Handle->Struct;
  84   // Union field address calculation is done via bitcast instead of GEP,
  85   // so the count for union is always 0.
  86   // We skip the union report to avoid confusion.
  87   if (strncmp(Struct->StructName, "union.", 6) == 0)
  88     return;
  89   // Remove the '.' after class/struct during print.
  90   if (strncmp(Struct->StructName, "class.", 6) == 0) {
  91     type = "class";
  92     start = &Struct->StructName[6];
  93   } else {
  94     type = "struct";
  95     start = &Struct->StructName[7];
  96   }
  97   // Remove the suffixes with '#' during print.
  98   end = strchr(start, '#');
  99   CHECK(end != nullptr);
 100   Report("  %s %.*s\n", type, end - start, start);
 101   Report("   size = %u, count = %llu, ratio = %llu, array access = %llu\n",
 102          Struct->Size, Handle->Count, Handle->Ratio, *Struct->ArrayCounter);
 103   if (Struct->hasAuxFieldInfo()) {
 104     for (u32 i = 0; i < Struct->NumFields; ++i) {
 105       Report("   #%2u: offset = %u,\t size = %u,"
 106              "\t count = %llu,\t type = %.*s\n",
 107              i, Struct->FieldOffset[i], Struct->FieldSize[i],
 108              Struct->FieldCounters[i], TypePrintLimit, Struct->FieldTypeName[i]);
 109     }
 110   } else {
 111     for (u32 i = 0; i < Struct->NumFields; ++i) {
 112       Report("   #%2u: count = %llu\n", i, Struct->FieldCounters[i]);
 113     }
 114   }
 115 }
 116
 117 static void computeStructRatio(StructHashMap::Handle &Handle) {
 118   Handle->Ratio = 0;
 119   Handle->Count = Handle->Struct->FieldCounters[0];
 120   for (u32 i = 1; i < Handle->Struct->NumFields; ++i) {
 121     Handle->Count += Handle->Struct->FieldCounters[i];
 122     Handle->Ratio += computeDifferenceRatio(
 123         Handle->Struct->FieldCounters[i - 1], Handle->Struct->FieldCounters[i]);
 124   }
 125   Ctx->TotalCount += Handle->Count;
 126   if (Handle->Ratio >= (u64)getFlags()->report_threshold ||
 127       (Verbosity() >= 1 && Handle->Count > 0))
 128     reportStructCounter(Handle);
 129 }
 130
 131 static void registerStructInfo(CacheFragInfo *CacheFrag) {
 132   for (u32 i = 0; i < CacheFrag->NumStructs; ++i) {
 133     StructInfo *Struct = &CacheFrag->Structs[i];
 134     StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters);
 135     if (H.created()) {
 136       VPrintf(2, " Register %s: %u fields\n", Struct->StructName,
 137               Struct->NumFields);
 138       H->Struct = Struct;
 139       ++Ctx->NumStructs;
 140     } else {
 141       VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName,
 142               Struct->NumFields);
 143     }
 144   }
 145 }
 146
 147 static void unregisterStructInfo(CacheFragInfo *CacheFrag) {
 148   // FIXME: if the library is unloaded before finalizeCacheFrag, we should
 149   // collect the result for later report.
 150   for (u32 i = 0; i < CacheFrag->NumStructs; ++i) {
 151     StructInfo *Struct = &CacheFrag->Structs[i];
 152     StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters, true);
 153     if (H.exists()) {
 154       VPrintf(2, " Unregister %s: %u fields\n", Struct->StructName,
 155               Struct->NumFields);
 156       // FIXME: we should move this call to finalizeCacheFrag once we can
 157       // iterate over the hash map there.
 158       computeStructRatio(H);
 159       --Ctx->NumStructs;
 160     } else {
 161       VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName,
 162               Struct->NumFields);
 163     }
 164   }
 165   static bool Reported = false;
 166   if (Ctx->NumStructs == 0 && !Reported) {
 167     Reported = true;
 168     reportStructSummary();
 169   }
 170 }
 171
 172 //===-- Init/exit functions -----------------------------------------------===//
 173
 174 void processCacheFragCompilationUnitInit(void *Ptr) {
 175   CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr;
 176   VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__,
 177           CacheFrag->UnitName, CacheFrag->NumStructs);
 178   registerStructInfo(CacheFrag);
 179 }
 180
 181 void processCacheFragCompilationUnitExit(void *Ptr) {
 182   CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr;
 183   VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__,
 184           CacheFrag->UnitName, CacheFrag->NumStructs);
 185   unregisterStructInfo(CacheFrag);
 186 }
 187
 188 void initializeCacheFrag() {
 189   VPrintf(2, "in esan::%s\n", __FUNCTION__);
 190   // We use placement new to initialize Ctx before C++ static initializaion.
 191   // We make CtxMem 8-byte aligned for atomic operations in AddrHashMap.
 192   static u64 CtxMem[sizeof(Context) / sizeof(u64) + 1];
 193   Ctx = new (CtxMem) Context();
 194   Ctx->NumStructs = 0;
 195 }
 196
 197 int finalizeCacheFrag() {
 198   VPrintf(2, "in esan::%s\n", __FUNCTION__);
 199   return 0;
 200 }
 201
 202 void reportCacheFrag() {
 203   VPrintf(2, "in esan::%s\n", __FUNCTION__);
 204   // FIXME: Not yet implemented.  We need to iterate over all of the
 205   // compilation unit data.
 206 }
 207
 208 } // namespace __esan