<div style="font-family: arial, helvetica, sans-serif"><font size="2">I've just sent a code review request to llvm-commits. <div><br></div><div>--kcc <br><br><div class="gmail_quote">On Mon, Jun 18, 2012 at 2:39 PM, Kostya Serebryany <span dir="ltr"><<a href="mailto:kcc@google.com" target="_blank">kcc@google.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="font-family:arial,helvetica,sans-serif"><font size="2">Hello llvmdev, <div><br></div><div>I would like to propose and discuss yet another dynamic tool, which we call MemorySanitizer (msan). </div>
<div>The main goal of the tool is to detect uses of uninitialized memory (the major feature of Valgrind/Memcheck not covered by AddressSanitizer). </div>
<div>It will also find use-after-destruction-but-before-free in C++.</div><div><br></div><div>The algorithm of the tool is similar to that of Memcheck (<a href="http://static.usenix.org/event/usenix05/tech/general/full_papers/seward/seward.pdf" target="_blank">http://static.usenix.org/event/usenix05/tech/general/full_papers/seward/seward.pdf</a>). </div>
<div>We associate a few shadow bits with every byte of the application memory, </div><div>poison the shadow of the malloc-ed or alloca-ed memory, </div><div>load the shadow bits on every memory read, </div><div>propagate the shadow bits through some of the arithmetic instruction (including MOV), </div>
<div>store the shadow bits on every memory write,</div><div>report a bug on some other instructions (e.g. JMP) if the associated shadow is poisoned. </div><div><br></div><div>But there are differences too. </div><div><br>
</div><div>The first and the major one: compiler instrumentation instead of binary instrumentation.</div>
<div>This gives us much better register allocation (function-wide instead of local), </div><div>possible compiler optimizations (static analysis can prove that some accesses always read initialized memory),</div><div>and a fast start-up. </div>
<div>
Our preliminary measurements show 3x-4x slowdown; compare it to Memchecks's 20x and DrMemory's 10x. </div><div>(See <a href="http://groups.csail.mit.edu/commit/papers/2011/bruening-cgo11-drmemory.pdf" target="_blank">http://groups.csail.mit.edu/commit/papers/2011/bruening-cgo11-drmemory.pdf</a> for those numbers). </div>
<div>But this brings the major issue as well: msan needs to see all program events, including system calls and reads/writes in system libraries, </div><div>so we either need to compile *everything* with msan or use a binary translation component to instrument pre-built libraries (with DynamoRIO? PIN?). </div>
<div><br></div><div>Question: is there any usable project in LLVM land which performs binary instrumentation (x86->LLVM->x86), either statically or dynamically?</div><div><br></div><div>Another difference from Memcheck is that we propose to use 8 shadow bits per byte of application memory and use a</div>
<div>direct shadow mapping (for 64-bit linux that is just clearing 46-th bit of the application memory address). </div><div>This greatly simplifies the instrumentation code and avoids races on shadow updates</div><div>(Memcheck is single-threaded so races are not a concern there.</div>
<div>Memcheck uses 2 shadow bits per byte with a slow path storage that uses 8 bits per byte).</div><div><br></div><div>Suggestions? Objections? </div><div>Unless there is a general resentment against msan, we will soon start sending the code for review.</div>
<div>(we already have a bit messy implementation, which at the top level looks very much like asan and tsan, and even shares some code with them.</div><div>The major difference here is that the compiler part is relatively more complicated than asan/tsan and run-time part is very simple).</div>
<div><br></div><div><br></div><div>FAQ:</div><div> Q. Why can't we combine msan and asan? </div><div> A: Valgrind/Memcheck and DrMemory do exactly that -- and pay large performance and memory costs. </div><div> Addressability checker (like asan) requires little shadow memory, but needs large redzone around allocated objects. </div>
<div> Tools that track uninitialized/tainted data need bit-per-bit shadow in worst case, but don't need redzones. </div><div> So, if we merge the tools together we multiply the memory overheads.</div><div>
The instrumentation costs in a combined tool are mostly added to each other (e.g. asan needs to poison redzones and msan needs to propagate shadow through arithmetic insns). </div><div><br></div><div>Thanks, </div>
<div>
<br></div><div>--kcc </div>
</font></div>
</blockquote></div><br></div></font></div>