From 9dfeca2386c28762468cddb4c9e16bfa8f25a15e Mon Sep 17 00:00:00 2001 From: Derek Bruening Date: Wed, 25 May 2016 02:04:04 +0000 Subject: Add working set base runtime library 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. Reviewers: aizatsky Subscribers: kubabrecka, vitalybuka, zhaoqin, kcc, eugenis, llvm-commits Differential Revision: http://reviews.llvm.org/D20485 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@270650 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/esan/CMakeLists.txt | 3 +- lib/esan/esan.cpp | 27 +++++++++--- lib/esan/esan_interface_internal.h | 2 + lib/esan/working_set.cpp | 90 ++++++++++++++++++++++++++++++++++++++ lib/esan/working_set.h | 30 +++++++++++++ 5 files changed, 146 insertions(+), 6 deletions(-) create mode 100644 lib/esan/working_set.cpp create mode 100644 lib/esan/working_set.h (limited to 'lib/esan') diff --git a/lib/esan/CMakeLists.txt b/lib/esan/CMakeLists.txt index 5e4ee107a..029c13579 100644 --- a/lib/esan/CMakeLists.txt +++ b/lib/esan/CMakeLists.txt @@ -11,7 +11,8 @@ 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 diff --git a/lib/esan/esan.cpp b/lib/esan/esan.cpp index 746575f66..f4087bcf2 100644 --- a/lib/esan/esan.cpp +++ b/lib/esan/esan.cpp @@ -19,6 +19,7 @@ #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" { @@ -31,6 +32,15 @@ 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, @@ -57,6 +67,8 @@ void processRangeAccess(uptr PC, uptr Addr, int Size, bool IsWrite) { 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); } } @@ -113,10 +125,7 @@ static bool verifyShadowScheme() { 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); @@ -157,7 +166,7 @@ void initializeLibrary(ToolType Tool) { ::__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(); } @@ -165,6 +174,12 @@ void initializeLibrary(ToolType Tool) { initializeShadow(); initializeInterceptors(); + if (WhichTool == ESAN_CacheFrag) { + // FIXME: add runtime code for this tool + } else if (WhichTool == ESAN_WorkingSet) { + initializeWorkingSet(); + } + EsanIsInitialized = true; } @@ -175,6 +190,8 @@ int finalizeLibrary() { // 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; } diff --git a/lib/esan/esan_interface_internal.h b/lib/esan/esan_interface_internal.h index 577c7e3cf..83e0433c7 100644 --- a/lib/esan/esan_interface_internal.h +++ b/lib/esan/esan_interface_internal.h @@ -28,6 +28,8 @@ extern "C" { 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, diff --git a/lib/esan/working_set.cpp b/lib/esan/working_set.cpp new file mode 100644 index 000000000..3cee6155b --- /dev/null +++ b/lib/esan/working_set.cpp @@ -0,0 +1,90 @@ +//===-- 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 diff --git a/lib/esan/working_set.h b/lib/esan/working_set.h new file mode 100644 index 000000000..4b1bc1596 --- /dev/null +++ b/lib/esan/working_set.h @@ -0,0 +1,30 @@ +//===-- 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 -- cgit v1.2.3