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;
hasAuxFieldInfo__esan::StructInfo36 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
reportStructSummary()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.
computeDifferenceRatio(u64 Val1,u64 Val2)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
reportStructCounter(StructHashMap::Handle & Handle)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
computeStructRatio(StructHashMap::Handle & Handle)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
registerStructInfo(CacheFragInfo * CacheFrag)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
unregisterStructInfo(CacheFragInfo * CacheFrag)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
processCacheFragCompilationUnitInit(void * Ptr)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
processCacheFragCompilationUnitExit(void * Ptr)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
initializeCacheFrag()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
finalizeCacheFrag()197 int finalizeCacheFrag() {
198 VPrintf(2, "in esan::%s\n", __FUNCTION__);
199 return 0;
200 }
201
reportCacheFrag()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
209