[esan] Add working set base runtime library

[bruening]

Summary

Adds the base runtime library for the working set tool.
Adds slowpath code for updating the shadow memory.

To be added in the future:
+ Scan memory and report the total size.
+ Take samples for intermediate values.

[aizatsky]

lib/esan/working_set.cpp

34 ↗

(On Diff #57979)

Instead of bit fiddling, do you think a struct with bit fields would look better?

[bruening]

lib/esan/working_set.cpp

34 ↗

(On Diff #57979)

Hmm, the issue is that all of the code (not just this CL, but code that uses the other 6 bits) operates on the bits in a way that is not very amenable to using separate named fields: samples at each bit level accumulate into the bit to the left, we would still be creating masks for word-level and other operations (rather than hoping the compiler turns several field references into a single mask), etc. While a struct might help with this top-level documentation, I don't think it would easily help with the actual code, and the declared field names would not be referenced.

I know you haven't seen any other code operating on the shadow values yet, so how about this: let's hold that thought, and once you see some future code that operates on all the bits, if you have an idea for how to use named bitfields in the code we can revisit at that point?

[aizatsky]

lib/esan/esan.cpp

120 ↗

(On Diff #57979)

please introduce constants for these 2 & 6.

lib/esan/working_set.cpp

34 ↗

(On Diff #57979)

SG let's see it coming.

If bitfields wouldn't work, it might be beneficial to extract lower-level shadow memory interface that contains all bit-fiddling. Not sure how similar would it be to processRangeAccessWorkingSet, but in the future I'd like to see these low-level details more contained and better structured.

53 ↗

(On Diff #57979)

I don't really see a reason to do an if() check here. Why not blindly "*Shadow |= ShadowAccessedVal"? Is it really faster? I would guess that having a branch is not very good for performance?

[bruening]

lib/esan/working_set.cpp

53 ↗

(On Diff #57979)

The check is faster. In every shadow tool we have ever made it is faster to load, compare, and only store if the value is not already there, than to perform a blind store.

[bruening]

Add named constants for the shadow scale.

[filcab]

Doing some minor post-commit review. Please don't add svn properties unless they're really needed.

Thank you,

Filipe

compiler-rt/trunk/lib/esan/esan.cpp

169

We should just validate Tool at the start of initializeLibrary, and set WhichTool after we validated it. That way we know that WhichTool is either uninitialized or a valid tool. We should also remove the assignment to WhichTool from __esan_init and only do it here, in initializeLibrary (currently we're setting it twice (at least)).

compiler-rt/trunk/lib/esan/esan_interface_internal.h

32

I'd rather have something like ESAN_MaxTool or something. A more descriptive name than simply Max.

compiler-rt/trunk/lib/esan/working_set.cpp

52

Please, no magic constants. alignof(u32) would be better.

63

sizeof(u32)

64

I'd rather just have a u32 *ShadowWord = Shadow before this block, and just use that pointer.
It minimizes "line noise" and is more explicit on what we're doing.

69

And remember to update Shadow from ShadowWord, of course.

80

Do we want this to be a flag, then?
This seems weird. This should probably be set somewhere close to the mapping, since they're so tied to each other.
And we can just add a VReport to the initialization function to print it for a verbosity level higher than 1.

[filcab]

lib/esan/working_set.cpp

53 ↗

(On Diff #57979)

I'd guess we end up having lots of shared cache locations. If we were writing all the time, then we'd end up with lots of cache/memory traffic for no reason, and the lines would be marked as exclusive all the time.
(Unless there are some cache optimizations where it doesn't change the state (any more than a read would) if the bit pattern written to it is the same. I'm not sure these exist)

[bruening]

Please don't add svn properties unless they're really needed.

It was not clear what you were referring to. Looking at it it seems that there are some svn:eol-style properties being auto-added by git-svn. Turning off core.autocrlf should avoid this in the future. Looking around I see a number of existing files with this property (e.g., 7 files in lib/asan/) so this seems like a common problem and should probably be mentioned at http://llvm.org/docs/GettingStarted.html.

compiler-rt/trunk/lib/esan/CMakeLists.txt

 # Build for the EfficiencySanitizer runtime support library.
 
 add_custom_target(esan)
 
 set(ESAN_RTL_CFLAGS ${SANITIZER_COMMON_CFLAGS})
 append_rtti_flag(OFF ESAN_RTL_CFLAGS)
 
 include_directories(..)
 
 set(ESAN_SOURCES
   esan.cpp
   esan_flags.cpp
   esan_interface.cpp
-  esan_interceptors.cpp)
+  esan_interceptors.cpp
+  working_set.cpp)
 
 foreach (arch ${ESAN_SUPPORTED_ARCH})
   add_compiler_rt_runtime(clang_rt.esan
     STATIC
     ARCHS ${arch}
     SOURCES ${ESAN_SOURCES}
             $<TARGET_OBJECTS:RTInterception.${arch}>
             $<TARGET_OBJECTS:RTSanitizerCommon.${arch}>

compiler-rt/trunk/lib/esan/esan.cpp

 
 #include "esan.h"
 #include "esan_flags.h"
 #include "esan_interface_internal.h"
 #include "esan_shadow.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_flag_parser.h"
 #include "sanitizer_common/sanitizer_flags.h"
+#include "working_set.h"
 
 // See comment below.
 extern "C" {
 extern void __cxa_atexit(void (*function)(void));
 }
 
 namespace __esan {
 
 bool EsanIsInitialized;
 ToolType WhichTool;
 ShadowMapping Mapping;
 
+// Different tools use different scales within the same shadow mapping scheme.
+// The scale used here must match that used by the compiler instrumentation.
+// This array is indexed by the ToolType enum.
+static const uptr ShadowScale[] = {
+  0, // ESAN_None.
+  2, // ESAN_CacheFrag: 4B:1B, so 4 to 1 == >>2.
+  6, // ESAN_WorkingSet: 64B:1B, so 64 to 1 == >>6.
+};
+
 // We are combining multiple performance tuning tools under the umbrella of
 // one EfficiencySanitizer super-tool.  Most of our tools have very similar
 // memory access instrumentation, shadow memory mapping, libc interception,
 // etc., and there is typically more shared code than distinct code.
 //
 // We are not willing to dispatch on tool dynamically in our fastpath
 // instrumentation: thus, which tool to use is a static option selected
 // at compile time and passed to __esan_init().

 // C) Completely split the tools into separate sanitizers.
 
 void processRangeAccess(uptr PC, uptr Addr, int Size, bool IsWrite) {
   VPrintf(3, "in esan::%s %p: %c %p %d\n", __FUNCTION__, PC,
           IsWrite ? 'w' : 'r', Addr, Size);
   if (WhichTool == ESAN_CacheFrag) {
     // TODO(bruening): add shadow mapping and update shadow bits here.
     // We'll move this to cache_frag.cpp once we have something.
+  } else if (WhichTool == ESAN_WorkingSet) {
+    processRangeAccessWorkingSet(PC, Addr, Size, IsWrite);
   }
 }
 
 #if SANITIZER_DEBUG
 static bool verifyShadowScheme() {
   // Sanity checks for our shadow mapping scheme.
   uptr AppStart, AppEnd;
   if (Verbosity() >= 3) {
static bool verifyShadowScheme() {
   }
   return true;
 }
 #endif
 
 static void initializeShadow() {
   DCHECK(verifyShadowScheme());
 
-  if (WhichTool == ESAN_CacheFrag)
-    Mapping.initialize(2); // 4B:1B, so 4 to 1 == >>2.
-  else
-    UNREACHABLE("unknown tool shadow mapping");
+  Mapping.initialize(ShadowScale[WhichTool]);
 
   VPrintf(1, "Shadow scale=%d offset=%p\n", Mapping.Scale, Mapping.Offset);
 
   uptr ShadowStart, ShadowEnd;
   for (int i = 0; getShadowRegion(i, &ShadowStart, &ShadowEnd); ++i) {
     VPrintf(1, "Shadow #%d: [%zx-%zx) (%zuGB)\n", i, ShadowStart, ShadowEnd,
             (ShadowEnd - ShadowStart) >> 30);
 
void initializeLibrary(ToolType Tool) {
   initializeFlags();
 
   // Intercepting libc _exit or exit via COMMON_INTERCEPTOR_ON_EXIT only
   // finalizes on an explicit exit call by the app.  To handle a normal
   // exit we register an atexit handler.
   ::__cxa_atexit((void (*)())finalizeLibrary);
 
   VPrintf(1, "in esan::%s\n", __FUNCTION__);
-  if (WhichTool != ESAN_CacheFrag) {
+  if (WhichTool <= ESAN_None || WhichTool >= ESAN_Max) {
     Printf("ERROR: unknown tool %d requested\n", WhichTool);
     Die();
   }
 
   initializeShadow();
   initializeInterceptors();
 
+  if (WhichTool == ESAN_CacheFrag) {
+    // FIXME: add runtime code for this tool
+  } else if (WhichTool == ESAN_WorkingSet) {
+    initializeWorkingSet();
+  }
+
   EsanIsInitialized = true;
 }
 
 int finalizeLibrary() {
   VPrintf(1, "in esan::%s\n", __FUNCTION__);
   if (WhichTool == ESAN_CacheFrag) {
     // FIXME NYI: we need to add sampling + callstack gathering and have a
     // strategy for how to generate a final report.
     // We'll move this to cache_frag.cpp once we have something.
     Report("%s is not finished: nothing yet to report\n", SanitizerToolName);
+  } else if (WhichTool == ESAN_WorkingSet) {
+    return finalizeWorkingSet();
   }
   return 0;
 }
 
 void processCompilationUnitInit(void *Ptr) {
   VPrintf(2, "in esan::%s\n", __FUNCTION__);
 }
 
 // This is called when the containing module is unloaded.
 // For the main executable module, this is called after finalizeLibrary.
 void processCompilationUnitExit(void *Ptr) {
   VPrintf(2, "in esan::%s\n", __FUNCTION__);
 }
 
 } // namespace __esan

compiler-rt/trunk/lib/esan/esan_interface_internal.h

 
 extern "C" {
 
 // This should be kept consistent with LLVM's EfficiencySanitizerOptions.
 // The value is passed as a 32-bit integer by the compiler.
 typedef enum Type : u32 {
   ESAN_None = 0,
   ESAN_CacheFrag,
+  ESAN_WorkingSet,
+  ESAN_Max,
 } ToolType;
 
 // This function should be called at the very beginning of the process,
 // before any instrumented code is executed and before any call to malloc.
 SANITIZER_INTERFACE_ATTRIBUTE void __esan_init(ToolType Tool, void *Ptr);
 SANITIZER_INTERFACE_ATTRIBUTE void __esan_exit(void *Ptr);
 
 // The instrumentation module will insert a call to one of these routines prior

compiler-rt/trunk/lib/esan/working_set.h

+//===-- working_set.h -------------------------------------------*- C++ -*-===//
+//
+//                     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.
+//
+// Header for working-set-specific code.
+//===----------------------------------------------------------------------===//
+
+#ifndef WORKING_SET_H
+#define WORKING_SET_H
+
+#include "interception/interception.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
+
+namespace __esan {
+
+void initializeWorkingSet();
+int finalizeWorkingSet();
+void processRangeAccessWorkingSet(uptr PC, uptr Addr, SIZE_T Size,
+                                  bool IsWrite);
+
+} // namespace __esan
+
+#endif // WORKING_SET_H

compiler-rt/trunk/lib/esan/working_set.cpp

+//===-- working_set.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 working-set-specific code.
+//===----------------------------------------------------------------------===//
+
+#include "working_set.h"
+#include "esan.h"
+#include "esan_flags.h"
+#include "esan_shadow.h"
+
+// We shadow every cache line of app memory with one shadow byte.
+// - The highest bit of each shadow byte indicates whether the corresponding
+//   cache line has ever been accessed.
+// - The lowest bit of each shadow byte indicates whether the corresponding
+//   cache line was accessed since the last sample.
+// - The other bits can be used either for a single working set snapshot
+//   between two consecutive samples, or an aggregate working set snapshot
+//   over multiple sample periods (future work).
+// We live with races in accessing each shadow byte.
+typedef unsigned char byte;
+
+namespace __esan {
+
+// See the shadow byte layout description above.
+static const u32 TotalWorkingSetBitIdx = 7;
+static const u32 CurWorkingSetBitIdx = 0;
+static const byte ShadowAccessedVal =
+  (1 << TotalWorkingSetBitIdx) | (1 << CurWorkingSetBitIdx);
+
+void processRangeAccessWorkingSet(uptr PC, uptr Addr, SIZE_T Size,
+                                  bool IsWrite) {
+  if (Size == 0)
+    return;
+  SIZE_T I = 0;
+  uptr LineSize = getFlags()->cache_line_size;
+  // As Addr+Size could overflow at the top of a 32-bit address space,
+  // we avoid the simpler formula that rounds the start and end.
+  SIZE_T NumLines = Size / LineSize +
+    // Add any extra at the start or end adding on an extra line:
+    (LineSize - 1 + Addr % LineSize + Size % LineSize) / LineSize;
+  byte *Shadow = (byte *)appToShadow(Addr);
+  // Write shadow bytes until we're word-aligned.
+  while (I < NumLines && (uptr)Shadow % 4 != 0) {
+    if ((*Shadow & ShadowAccessedVal) != ShadowAccessedVal)
+      *Shadow |= ShadowAccessedVal;
+    ++Shadow;
+    ++I;
+  }
+  // Write whole shadow words at a time.
+  // Using a word-stride loop improves the runtime of a microbenchmark of
+  // memset calls by 10%.
+  u32 WordValue = ShadowAccessedVal | ShadowAccessedVal << 8 |
+    ShadowAccessedVal << 16 | ShadowAccessedVal << 24;
+  while (I + 4 <= NumLines) {
+    if ((*(u32*)Shadow & WordValue) != WordValue)
+      *(u32*)Shadow |= WordValue;
+    Shadow += 4;
+    I += 4;
+  }
+  // Write any trailing shadow bytes.
+  while (I < NumLines) {
+    if ((*Shadow & ShadowAccessedVal) != ShadowAccessedVal)
+      *Shadow |= ShadowAccessedVal;
+    ++Shadow;
+    ++I;
+  }
+}
+
+void initializeWorkingSet() {
+  // The shadow mapping assumes 64 so this cannot be changed.
+  CHECK(getFlags()->cache_line_size == 64);
+}
+
+int finalizeWorkingSet() {
+  // FIXME NYI: we need to add memory scanning to report the total lines
+  // touched, and later add sampling to get intermediate values.
+  Report("%s is not finished: nothing yet to report\n", SanitizerToolName);
+  return 0;
+}
+
+} // namespace __esan

compiler-rt/trunk/test/esan/TestCases/workingset-memset.cpp

+// RUN: %clang_esan_wset -O0 %s -o %t 2>&1
+// RUN: %run %t 2>&1 | FileCheck %s
+
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <assert.h>
+#include <string.h>
+
+int main(int argc, char **argv) {
+  const int size = 128*1024*1024;
+  char *p = (char *)mmap(0, size, PROT_READ | PROT_WRITE,
+                         MAP_ANON | MAP_PRIVATE, -1, 0);
+  // Test the slowpath at different cache line boundaries.
+  for (int i = 0; i < 630; i++)
+    memset((char *)p + 63*i, i, 63*i);
+  munmap(p, size);
+  return 0;
+  // FIXME: once the memory scan and size report is in place add it here.
+  // CHECK: {{.*}}EfficiencySanitizer is not finished: nothing yet to report
+}

compiler-rt/trunk/test/esan/lit.cfg

 # -*- Python -*-
 
 import os
 
 # Setup config name.
 config.name = 'EfficiencySanitizer' + config.name_suffix
 
 # Setup source root.
 config.test_source_root = os.path.dirname(__file__)
 
 # Setup default compiler flags used with -fsanitize=efficiency option.
 base_cflags = ([config.target_cflags] + config.debug_info_flags)
 base_cxxflags = config.cxx_mode_flags + base_cflags
 
 frag_cflags = (["-fsanitize=efficiency-cache-frag"] + base_cflags)
+wset_cflags = (["-fsanitize=efficiency-working-set"] + base_cflags)
 
 def build_invocation(compile_flags):
   return " " + " ".join([config.clang] + compile_flags) + " "
 
 config.substitutions.append( ("%clang_esan_frag ",
                               build_invocation(frag_cflags)) )
+config.substitutions.append( ("%clang_esan_wset ",
+                              build_invocation(wset_cflags)) )
 
 default_esan_opts = ''
 config.substitutions.append(('%env_esan_opts=',
                              'env ESAN_OPTIONS=' + default_esan_opts))
 
 # Default test suffixes.
 config.suffixes = ['.c', '.cpp']
 
 # EfficiencySanitizer tests are currently supported on Linux x86-64 only.
 if config.host_os not in ['Linux'] or config.target_arch != 'x86_64':
   config.unsupported = True