[esan|cfrag] Compute the struct field access difference ratio

[zhaoqin]

Summary

Computes the struct field access variation based on each field access
count.

Adds a flag to control the report thresholds.

Updates struct-simple.cpp with variance report output.

[zhaoqin]

Rebase to the ToT, and apply clang-format

[aizatsky]

lib/esan/cache_frag.cpp

43–44

Is variance a well-established term here? If not, we need to find something else.
Variance has a very strict meaning in my mind: "variance is the expectation of the squared deviation of a random variable from its mean".

62

As far as I can see you compute this:

Log[t, v1 / (v2 + 1) / t]

Is this right?

This is equivalent to:

Log[t, v1/(v2+1)]-1

So lets:

a) document this formula
b) maybe get rid of this -1? Would simplify things.

62

If my assumption about formula is right, then how about logratio as a metric name?

64

Let's add Threshold as a parameter.

66

Why + 1? Because of 0 values?

What do you imagine computeVarianceScore(v1, 0, t) look like?

108

I'm not sure that adding log-ratios together is a good thing to do. Do you have any reasoning why you do it this way?

[zhaoqin]

PTAL

lib/esan/cache_frag.cpp

62

changed the algorithm a bit with an added weight, not sure if logratio is still suitable.

62

add comment about the formula.
The reason I have -1 is to make the score 0 if the two values are similar, so it is still 0 even with adding some weight, add comment.

66

Yes, it is for handling 0.
for computeVarianceScore(v1, 0, t), it should be roughly the same as computeVarianceScore(v1, 1, t)
The rationale of computeVarianceScore is to evaluate how far apart the two value are.
so the variance score for (v1, 0) should be closest to the score of (v1, 1).
Use condition instead.

108

You are right, I add weight in the computeVarianceScore, so it is no longer a simple log-ratios.

[zhaoqin]

lib/esan/cache_frag.cpp

43–44

oops, missed this comment, how about just Difference?

[zhaoqin]

Rename variance to difference

[aizatsky]

lib/esan/cache_frag.cpp

62

Before we move to the weight, let's discuss logarithm base for a while.

Obviously:

log(T, V1/V2) = log2(v1/v2) / log2(T)

So changing T would just change a constant factor for all measurements. Why not statically fix it?

Maybe just use log2(v1/v2) without base? you could use __builtin_clzll for that.

63

As for weight, can you please share your thinking why do you need it?

66

Is there a "-1" now?

68

Let's rename Threshold to Base.

73

if (Val2 > Val1) { swap(Val1, Val2); }

You won't need the Weight then.

80

In any case I suggest you extract a simple FastLog function.

[zhaoqin]

lib/esan/cache_frag.cpp

62

The major reason is to have a runtime flag for T is that I am not sure what's the right way to evaluate the variation of the struct field counts.
I want the overall score for the variation having a few features:

1. The bigger the difference is, the higher the score should be: e.g., { 2^20, 1, 2^20 } should have higher score than { 2^10, 2^8, 2^10, 2^8, 2^10, 2^8, ... }
2. The higher the count value is, the higher the score should be: e.g., { 2^20, 2^10 } should have higher score than {2^10, 1}.

It looks like I should not use log to compute at all, which gets rid of the count factor, maybe a simple ratio should work, e.g., V1/V2/Base

63

For two pairs of value: (2^20, 2^10), and (2^10, 1), I want to say (2^20, 2^10) worth more attention, and so should have a higher score.
Now use V1/V2/Base, so do not need weight.

66

I used the while (Ratio > Threshold) to make the score 0, probably not a good idea, make the code look different from the algo. Update it.

80

stop using log

[zhaoqin]

Use v1/v2/base to calculate the difference score.

[aizatsky]

lib/esan/cache_frag.cpp

44

Let's call it ratio then.

53

If we are sticking to a ratio, then Sum(ratios) doesn't make lots of sense.

This is the whole-program metric, right?

How about considering (one of) the following metrics (Ci - counts, Ri - ratio):

1. Sum(Abs(Ci - C{i+1}))? - Total "Assymetry". You can divide it by TotalCount to get a relative metric.

2. Max(Ri) (Mean, Median, StdDev, GeomMean)

BTW if you want this in sooner, I suggest you remove TotalDifference from this CL altogether, and let's figure it out in a separate one?

62

The only reason to use log is to make huge differences look smaller. I suspect that this is not your case - you want huge differences look huge, because CPUs are linear. I approve the use of the linear scale.

69

Unless there is an overflow concern (which there shouldn't be, right?), I suggest storing the unscaled ratio. You can always introduce scaling when you print.

[zhaoqin]

lib/esan/cache_frag.cpp

53

Removed.

62

ack

[zhaoqin]

PTAL

[zhaoqin]

update the comment about computing the difference ratio.

lib/esan/cache_frag.cpp

 //===-- cache_frag.cpp ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of EfficiencySanitizer, a family of performance tuners.
 //
 // This file contains cache fragmentation-specific code.
 //===----------------------------------------------------------------------===//
 
 #include "esan.h"
+#include "esan_flags.h"
 #include "sanitizer_common/sanitizer_addrhashmap.h"
 #include "sanitizer_common/sanitizer_placement_new.h"
+#include <string.h>
 
 namespace __esan {
 
 //===-- Struct field access counter runtime -------------------------------===//
 
 // This should be kept consistent with LLVM's EfficiencySanitizer StructInfo.
 struct StructInfo {
   const char *StructName;
   u32 NumFields;
   u64 *FieldCounters;
   const char **FieldTypeNames;
 };
 
 // This should be kept consistent with LLVM's EfficiencySanitizer CacheFragInfo.
 // The tool-specific information per compilation unit (module).
 struct CacheFragInfo {
   const char *UnitName;
   u32 NumStructs;
   StructInfo *Structs;
 };
 
 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.
 typedef AddrHashMap<StructCounter, 31051> StructHashMap;
 struct Context {
   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);
     }
   }
 }
 
 static void unregisterStructInfo(CacheFragInfo *CacheFrag) {
   // FIXME: if the library is unloaded before finalizeCacheFrag, we should
   // collect the result for later report.
   for (u32 i = 0; i < CacheFrag->NumStructs; ++i) {
     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 bool Reported = false;
+  if (Ctx->NumStructs == 0 && !Reported) {
+    Reported = true;
+    reportStructSummary();
   }
-
-static void reportStructSummary() {
-  // FIXME: iterate StructHashMap and generate the final report.
-  Report("%s is not finished: nothing yet to report\n", SanitizerToolName);
 }
 
 //===-- 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);
 }
 
 void initializeCacheFrag() {
   VPrintf(2, "in esan::%s\n", __FUNCTION__);
   // 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;
 }
 
 } // namespace __esan

lib/esan/esan_flags.inc

 // ESAN_FLAG(Type, Name, DefaultValue, Description)
 // See COMMON_FLAG in sanitizer_flags.inc for more details.
 
 // Cross-tool options:
 ESAN_FLAG(int, cache_line_size, 64,
           "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.")

test/esan/TestCases/struct-simple.cpp

int main(int argc, char **argv) {
   s.s1 = 0;
   d.d1 = 0;
   d.d2 = 0;
   part1();
   part2();
   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

test/esan/TestCases/verbose-simple.c

 // RUN: %clang_esan_frag -O0 %s -o %t 2>&1
 // RUN: %env_esan_opts=verbosity=1 %run %t 2>&1 | FileCheck %s
 
 int main(int argc, char **argv) {
   // CHECK:      in esan::initializeLibrary
   // (There can be a re-exec for stack limit here.)
   // CHECK:      Shadow scale=2 offset=0x440000000000
   // CHECK-NEXT: Shadow #0: [110000000000-114000000000) (256GB)
   // 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;
 }