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
22namespace __esan {
23
24//===-- Struct field access counter runtime -------------------------------===//
25
26// This should be kept consistent with LLVM's EfficiencySanitizer StructInfo.
27struct 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).
41struct CacheFragInfo {
42  const char *UnitName;
43  u32 NumStructs;
44  StructInfo *Structs;
45};
46
47struct 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.
54typedef AddrHashMap<StructCounter, 31051> StructHashMap;
55struct Context {
56  StructHashMap StructMap;
57  u32 NumStructs;
58  u64 TotalCount; // The total access count of all structs.
59};
60static Context *Ctx;
61
62static 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.
71static 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
80static 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
117static 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
131static 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
147static 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
174void 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
181void 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
188void 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
197int finalizeCacheFrag() {
198  VPrintf(2, "in esan::%s\n", __FUNCTION__);
199  return 0;
200}
201
202void 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
209