Index: lib/esan/cache_frag.cpp =================================================================== --- lib/esan/cache_frag.cpp +++ lib/esan/cache_frag.cpp @@ -13,8 +13,10 @@ //===----------------------------------------------------------------------===// #include "esan.h" +#include "esan_flags.h" #include "sanitizer_common/sanitizer_addrhashmap.h" #include "sanitizer_common/sanitizer_placement_new.h" +#include namespace __esan { @@ -38,8 +40,8 @@ struct StructCounter { StructInfo *Struct; - u64 Count; // The total access count of the struct. - u32 Variance; // Variance score for the struct layout access. + u64 Count; // The total access count of the struct. + u64 Difference; // Difference score for the struct layout access. }; // We use StructHashMap to keep track of an unique copy of StructCounter. @@ -48,21 +50,96 @@ StructHashMap StructMap; u32 NumStructs; u64 TotalCount; // The total access count of all structs. + u64 TotalDifference; }; static Context *Ctx; +static void reportStructSummary() { + Report("%s: total count = %llu, total difference = %llu\n", SanitizerToolName, + Ctx->TotalCount, Ctx->TotalDifference); +} + +// We evaluate how much difference between the access counts of the two adjacent +// struct fields. +// The formula for calculating the difference score is (log(T, V1/V2) - 1) * V1 +// if V1 is greater than V2. +// * "- 1": making the difference score 0 if the two counts are close in value, +// * "* V2": added weight for how imporant the difference is. +static u64 computeDifferenceScore(u64 Val1, u64 Val2, u32 Threshold) { + u64 Ratio, Weight; + u64 Score = 0; + if (Threshold <= 1) + Threshold = 2; + if (Val1 > Val2) { + Ratio = (Val2 == 0) ? Val1 : (Val1 / Val2); + Weight = Val1; + } else { + Ratio = (Val1 == 0) ? Val2 : (Val2 / Val1); + Weight = Val2; + } + while (Ratio > Threshold) { + ++Score; + Ratio /= Threshold; + } + return Score * Weight; +} + +static void reportStructCounter(StructHashMap::Handle &Handle) { + const char *type, *start, *end; + StructInfo *Struct = Handle->Struct; + // Union field address calculation is done via bitcast instead of GEP, + // so the count for union is always 0. + // We skip the union report to avoid confusion. + if (strncmp(Struct->StructName, "union.", 6) == 0) + return; + // Remove the '.' after class/struct during print. + if (strncmp(Struct->StructName, "class.", 6) == 0) { + type = "class"; + start = &Struct->StructName[6]; + } else { + type = "struct"; + start = &Struct->StructName[7]; + } + // Remove the suffixes with '#' during print. + end = strchr(start, '#'); + CHECK(end != nullptr); + Report(" %s %.*s\n", type, end - start, start); + Report(" count = %llu, difference = %llu\n", Handle->Count, + Handle->Difference); + for (u32 i = 0; i < Struct->NumFields; ++i) { + Report(" #%2u: count = %llu,\t type = %s\n", i, Struct->FieldCounters[i], + Struct->FieldTypeNames[i]); + } +} + +static void computeStructDifference(StructHashMap::Handle &Handle) { + Handle->Difference = 0; + Handle->Count = Handle->Struct->FieldCounters[0]; + for (u32 i = 1; i < Handle->Struct->NumFields; ++i) { + Handle->Count += Handle->Struct->FieldCounters[i]; + Handle->Difference += computeDifferenceScore( + Handle->Struct->FieldCounters[i - 1], Handle->Struct->FieldCounters[i], + (u32)getFlags()->difference_threshold); + } + Ctx->TotalCount += Handle->Count; + Ctx->TotalDifference += Handle->Difference; + if (Handle->Difference >= (u64)getFlags()->report_threshold || + Verbosity() >= 2) + reportStructCounter(Handle); +} + static void registerStructInfo(CacheFragInfo *CacheFrag) { for (u32 i = 0; i < CacheFrag->NumStructs; ++i) { StructInfo *Struct = &CacheFrag->Structs[i]; StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters); if (H.created()) { - VPrintf(2, " Register %s: %u fields\n", - Struct->StructName, Struct->NumFields); + VPrintf(2, " Register %s: %u fields\n", Struct->StructName, + Struct->NumFields); H->Struct = Struct; ++Ctx->NumStructs; } else { - VPrintf(2, " Duplicated %s: %u fields\n", - Struct->StructName, Struct->NumFields); + VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName, + Struct->NumFields); } } } @@ -74,34 +151,37 @@ StructInfo *Struct = &CacheFrag->Structs[i]; StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters, true); if (H.exists()) { - VPrintf(2, " Unregister %s: %u fields\n", - Struct->StructName, Struct->NumFields); + VPrintf(2, " Unregister %s: %u fields\n", Struct->StructName, + Struct->NumFields); + // FIXME: we should move this call to finalizeCacheFrag once we can + // iterate over the hash map there. + computeStructDifference(H); --Ctx->NumStructs; } else { - VPrintf(2, " Duplicated %s: %u fields\n", - Struct->StructName, Struct->NumFields); + VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName, + Struct->NumFields); } } -} - -static void reportStructSummary() { - // FIXME: iterate StructHashMap and generate the final report. - Report("%s is not finished: nothing yet to report\n", SanitizerToolName); + static bool Reported = false; + if (Ctx->NumStructs == 0 && !Reported) { + Reported = true; + reportStructSummary(); + } } //===-- Init/exit functions -----------------------------------------------===// void processCacheFragCompilationUnitInit(void *Ptr) { CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr; - VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", - __FUNCTION__, CacheFrag->UnitName, CacheFrag->NumStructs); + VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__, + CacheFrag->UnitName, CacheFrag->NumStructs); registerStructInfo(CacheFrag); } void processCacheFragCompilationUnitExit(void *Ptr) { CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr; - VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", - __FUNCTION__, CacheFrag->UnitName, CacheFrag->NumStructs); + VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__, + CacheFrag->UnitName, CacheFrag->NumStructs); unregisterStructInfo(CacheFrag); } @@ -110,13 +190,12 @@ // We use placement new to initialize Ctx before C++ static initializaion. // We make CtxMem 8-byte aligned for atomic operations in AddrHashMap. static u64 CtxMem[sizeof(Context) / sizeof(u64) + 1]; - Ctx = new(CtxMem) Context(); + Ctx = new (CtxMem) Context(); Ctx->NumStructs = 0; } int finalizeCacheFrag() { VPrintf(2, "in esan::%s\n", __FUNCTION__); - reportStructSummary(); return 0; } Index: lib/esan/esan_flags.inc =================================================================== --- lib/esan/esan_flags.inc +++ lib/esan/esan_flags.inc @@ -23,3 +23,18 @@ "The number of bytes in a cache line. For the working-set tool, this " "cannot be changed without also changing the compiler " "instrumentation.") + +//===----------------------------------------------------------------------===// +// Cache Fragmentation tool options +//===----------------------------------------------------------------------===// + +// The difference information of a struct is reported if the struct's difference +// score is greater than the report_threshold. +ESAN_FLAG(int, report_threshold, 1<<20, "Cache-frag tool: the struct difference" + " score threshold for reporting.") + +// This controls how much difference between two consecutive struct field +// counts is considered significant. +ESAN_FLAG(int, difference_threshold, 512, "Cache-frag tool: two consecutive " + " struct field counts are considered significantly different if the " + " ratio of those two counts is greater than difference_threshold.") Index: test/esan/TestCases/struct-simple.cpp =================================================================== --- test/esan/TestCases/struct-simple.cpp +++ test/esan/TestCases/struct-simple.cpp @@ -138,22 +138,52 @@ return 0; // CHECK: in esan::finalizeLibrary // CHECK-NEXT: in esan::finalizeCacheFrag - // CHECK-NEXT: {{.*}}EfficiencySanitizer is not finished: nothing yet to report // CHECK-NEXT: in esan::processCompilationUnitExit // CHECK-NEXT: in esan::processCacheFragCompilationUnitExit: {{.*}}struct-simple.cpp with 5 class(es)/struct(s) // CHECK-NEXT: Unregister class.C#3#14#13#13: 3 fields + // CHECK-NEXT: {{.*}} class C + // CHECK-NEXT: {{.*}} count = 5, difference = 0 + // CHECK-NEXT: {{.*}} # 0: count = 2, type = %struct.anon = type { i32, i32 } + // CHECK-NEXT: {{.*}} # 1: count = 2, type = %union.anon = type { double } + // CHECK-NEXT: {{.*}} # 2: count = 1, type = [10 x i8] // CHECK-NEXT: Unregister struct.anon#2#11#11: 2 fields + // CHECK-NEXT: {{.*}} struct anon + // CHECK-NEXT: {{.*}} count = 2, difference = 0 + // CHECK-NEXT: {{.*}} # 0: count = 1, type = i32 + // CHECK-NEXT: {{.*}} # 1: count = 1, type = i32 // CHECK-NEXT: Unregister union.anon#1#3: 1 fields // CHECK-NEXT: Unregister struct.S#2#11#11: 2 fields + // CHECK-NEXT: {{.*}} struct S + // CHECK-NEXT: {{.*}} count = 2, difference = 0 + // CHECK-NEXT: {{.*}} # 0: count = 2, type = i32 + // CHECK-NEXT: {{.*}} # 1: count = 0, type = i32 // CHECK-NEXT: Unregister struct.D#3#11#11#11: 3 fields + // CHECK-NEXT: {{.*}} struct D + // CHECK-NEXT: {{.*}} count = 2, difference = 0 + // CHECK-NEXT: {{.*}} # 0: count = 1, type = i32 + // CHECK-NEXT: {{.*}} # 1: count = 1, type = i32 + // CHECK-NEXT: {{.*}} # 2: count = 0, type = i32 // CHECK-NEXT: in esan::processCompilationUnitExit // CHECK-NEXT: in esan::processCacheFragCompilationUnitExit: {{.*}}struct-simple.cpp with 0 class(es)/struct(s) // CHECK-NEXT: in esan::processCompilationUnitExit // CHECK-NEXT: in esan::processCacheFragCompilationUnitExit: {{.*}}struct-simple.cpp with 5 class(es)/struct(s) // CHECK-NEXT: Unregister struct.A#2#11#11: 2 fields + // CHECK-NEXT: {{.*}} struct A + // CHECK-NEXT: {{.*}} count = 2049, difference = 2048 + // CHECK-NEXT: {{.*}} # 0: count = 2048, type = i32 + // CHECK-NEXT: {{.*}} # 1: count = 1, type = i32 // CHECK-NEXT: Unregister struct.B#2#3#2: 2 fields + // CHECK-NEXT: {{.*}} struct B + // CHECK-NEXT: {{.*}} count = 2097153, difference = 4194304 + // CHECK-NEXT: {{.*}} # 0: count = 1, type = float + // CHECK-NEXT: {{.*}} # 1: count = 2097152, type = double // CHECK-NEXT: Unregister union.U#1#3: 1 fields // CHECK-NEXT: Duplicated struct.S#2#11#11: 2 fields // CHECK-NEXT: Unregister struct.D#2#11#11: 2 fields + // CHECK-NEXT: {{.*}} struct D + // CHECK-NEXT: {{.*}} count = 1, difference = 0 + // CHECK-NEXT: {{.*}} # 0: count = 1, type = i32 + // CHECK-NEXT: {{.*}} # 1: count = 0, type = i32 + // CHECK-NEXT: {{.*}}EfficiencySanitizer: total count = 2099214, total difference = 4196352 } #endif // MAIN Index: test/esan/TestCases/verbose-simple.c =================================================================== --- test/esan/TestCases/verbose-simple.c +++ test/esan/TestCases/verbose-simple.c @@ -9,6 +9,6 @@ // CHECK-NEXT: Shadow #1: [124000000000-12c000000000) (512GB) // CHECK-NEXT: Shadow #2: [148000000000-150000000000) (512GB) // CHECK-NEXT: in esan::finalizeLibrary - // CHECK-NEXT: {{.*}}EfficiencySanitizer is not finished: nothing yet to report + // CHECK-NEXT: {{.*}}EfficiencySanitizer: total count = 0, total difference = 0 return 0; }