<div dir="ltr">FTR: we have similar changes in our branch of libstdc++: <a href="http://gcc.gnu.org/viewcvs/gcc?view=revision&revision=207517">http://gcc.gnu.org/viewcvs/gcc?view=revision&revision=207517</a><div>These annotations helped us detect ~15 bugs, and counting. </div>
<div><br></div><div>--kcc </div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Feb 4, 2014 at 9:51 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 dir="ltr"><br><div class="gmail_extra">Hi Marshall, <br><br><div class="gmail_quote"><div class="">On Tue, Feb 4, 2014 at 9:00 PM, Marshall Clow <span dir="ltr"><<a href="mailto:mclow.lists@gmail.com" target="_blank">mclow.lists@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div>
<div>On Jan 15, 2014, at 1:53 AM, Kostya Serebryany <<a href="mailto:kcc@google.com" target="_blank">kcc@google.com</a>> wrote:</div><br></div><blockquote type="cite"><div dir="ltr"><div>Marshall, </div><div>
<div>Any chance to start the review this month?</div><div>Slightly updated patch attached.</div><div>FYI: we applied the same approach to libstdc++, ran various tests and found dozens of bugs. </div>
<div>These annotations also help to achieve more precise leak detection with LeakSanitizer. </div><div><a href="https://code.google.com/p/address-sanitizer/wiki/ContainerOverflow" target="_blank">https://code.google.com/p/address-sanitizer/wiki/ContainerOverflow</a><br>
</div></div></div></blockquote><div><br></div>Kostya —</div><div><br></div><div>First off, I’m sorry for the slow response.</div></div></blockquote><div><br></div></div><div>np, I was having some other fun :) </div><div class="">
<div><br></div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div>Second, I’m very much in favor of adding these capabilities to the standard library.</div>
<div><br></div><div>Third, looking over this code, it seems to me to be a lot of changes. </div></div></blockquote><div><br></div></div><div>This is sadly so... </div><div class=""><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div>You seem to tracking all the changes for the storage in vector, discriminating between insertions, deletions, growth and shrinkage. That seems overly complicated to me.</div><div><br>
</div><div>Thinking about invariants; we know that std::vector maintains a block of memory</div><div>bounded by <span style="white-space:pre-wrap"> </span>[data(), data()+(sizeof(value_type)*capacity())),</div><div>of which the block<span style="white-space:pre-wrap"> </span>[data(), data()+(sizeof(value_type)*size))</div>
<div>is actually in use.</div></div></blockquote><div><br></div></div><div>Correct. </div><div class=""><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><br></div><div>Why not just turn off “inside the block” ASAN checking upon entry to routines that modify the vector, and reestablish it upon return?</div></div></blockquote></div><div>
Because asan-off and asan-on have complexity O(capacity()). </div>
<div>At every point of time the vector looks like GGGGGGPBBB, </div><div>where G is good 8-bytes, B is bad 8-bytes and P is a single partially good 8-byte word.</div><div>The status of every 8 bytes in application is encoded in a single byte in shadow. </div>
<div>turn-off or turn-on operation will require to write capacity()/8 bytes to the shadow.</div><div class=""><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><br></div><div>So, for push_back() (as an example), we could write:</div><div><br></div><div><div>template <class _Tp, class _Allocator></div><div>inline _LIBCPP_INLINE_VISIBILITY</div>
<div>void</div><div>vector<_Tp, _Allocator>::push_back(const_reference __x)</div><div>{</div><div> __turn_off_ASAN_internal_for(data());</div><div> if (this->__end_ != this->__end_cap())</div><div> {</div>
<div> __alloc_traits::construct(this->__alloc(),</div><div> _VSTD::__to_raw_pointer(this->__end_), __x);</div><div> ++this->__end_;</div><div> }</div><div> else</div>
<div> __push_back_slow_path(__x);</div><div> __turn_on_ASAN_internal_for(data(), data()+size()); // or whatever parameters ASAN needs</div><div>}</div><div><br></div></div><div>[ In actuality, I wouldn’t do it this way, I’d put the calls in the constructor/destructor of an object; that way fast returns and exceptions would not interfere, but you get the idea. ]</div>
<div><br></div><div><br></div><div><div><blockquote type="cite"><div dir="ltr"><div>
</div><div>If this patch has any chance to get committed eventually, I'd like to understand your preference regarding the testing. </div><div>One approach is to test it with asan: then all you need is to run all existing vector tests built with<br>
</div><div>clang -fsanitize=address -D_LIBCPP_ADDRESS_SANITIZER_ANNOTATIONS</div><div>But this will tie the testing process to clang, I am not sure if that is acceptable for you (totally ok for me).</div><div>Another approach is to provide a fake standalone implementation of __sanitizer_annotate_contiguous_container;</div>
<div>it will be a slightly less accurate testing, but will not depend on clang. </div></div></blockquote><div><br></div></div>I think to test this we’ll have to augment the libc++ test process.</div><div>It currently has two kinds of tests - ones that fail to compile, and ones that compile and run successfully.</div>
<div>We’ll either need a third kind of test, one that is supposed to fail at runtime, -or-, an ASAN hook to catch ASAN errors and record them.</div><div>I’m leaning towards the first one - I don’t think we want to deliberately invoke undefined behavior (which is what this is), and expect anything further from the test.</div>
</div></blockquote><div><br></div></div><div>Some tests could be "ones that compile and run successfully"</div><div>We can validate the shadow of the vector using __asan_memory_region_is_poisoned. </div><div>I have a test that does various operations on vector and then calls this:</div>
<div><br></div><div><div>extern "C" bool __asan_address_is_poisoned(void *addr);</div><div class=""><div><br></div><div>template <class T> void TestVector(std::vector<T> &v) {</div><div> if (v.capacity() == 0) return;</div>
</div><div> char *beg = (char*)v.data();</div><div class=""><div> char *end = beg + v.capacity() * sizeof(T);</div><div> char *mid = beg + v.size() * sizeof(T);</div><div> for (char *p = beg; p < mid; p++)</div><div>
assert(!__asan_address_is_poisoned(p));</div>
<div> for (char *p = mid ; p < end; p++)</div><div> assert(__asan_address_is_poisoned(p));</div><div>}</div></div></div><div><br></div><div>I'd also like to have at least a couple of tests that are supposed to fail at runtime, </div>
<div>just like the lit-style tests we have for the rest of LLVM.</div><div><br></div><div>In both cases we will need to test libc++ with the fresh clang compiler (which supports asan and asan's annotations)</div><div>
Will this work? </div><div><br></div><div>--kcc </div><div><div class="h5"><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><br></div><div>What do you think?</div><div><br></div><div>— Marshall</div><div><br></div><div><blockquote type="cite"><div><div><div dir="ltr"><div><br></div><div>Thanks,</div>
<div><br></div><div>--kcc </div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Tue, Dec 10, 2013 at 6:07 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr">Here is another version; this time I've been able to build and run Chromium with libc++ and these annotations.<div><br></div><div>--kcc </div></div><div><div><div class="gmail_extra">
<br><br><div class="gmail_quote">
On Mon, Dec 9, 2013 at 6:58 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div>Marshall, </div>Here is a more complete patch for asan vector annotations. <div>It passes all tests in libcxx/test/containers/sequences/vector, but doesn't yet work on larger programs (I tried Chrome).</div>
<div>Two questions: </div><div> 1. Does it look like something potentially committable? </div><div> 2. Would you suggest some bigger test suite specifically targeted to test std::vector?</div><div><br></div><div>Thanks, </div>
<div><br></div><div>--kcc <br><div><br></div></div></div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Nov 20, 2013 at 6:35 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Attached is an intermediate patch that passes my tests (also attached). Few questions: <div>
<br></div><div>
The patch gets a bit too verbose and it has a few repetitions, e.g. we have this snippet repeated multiple times:</div>
<div><div>+ __annotate_contiguous_container(data(), data() + capacity(),</div><div>+ data() + size(), data() + size() + 1);</div><div><br></div>
<div>WDYT about adding a private method to vector like this (and a couple more)?</div>
<div><br></div><div>void __annotate_size_increase(size_t __n) {</div><div><div> __annotate_contiguous_container(data(), data() + capacity(),</div><div> data() + size(), data() + size() + __n);</div>
</div><div>}</div><div><br></div><div>In order to test the annotation properly I need to do something like this as often as possible: </div><div><div>template <class T> void TestVector(std::vector<T> &v) { </div>
<div> if (v.capacity() == 0) return; </div><div> char *beg = (char*)&v.front(); </div><div> char *end = beg + v.capacity() * sizeof(T); </div>
<div> char *mid = beg + v.size() * sizeof(T); </div><div> for (char *p = beg; p < mid; p++) </div><div> assert(!__asan_address_is_poisoned(p)); </div>
<div> for (char *p = mid ; p < end; p++) </div><div> assert(__asan_address_is_poisoned(p)); </div><div>} </div>
</div><div><br></div><div>Is it possible to add code like this as another private method of vector (under some ifdef)?</div><div><br></div><div>--kcc </div></div></div><div><div class="gmail_extra">
<br><br><div class="gmail_quote">
On Tue, Nov 19, 2013 at 1:57 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><br>
> Do you like the idea?<br>
<br>
</div>Yes - very much so.<br>
<div><br>
> Any comments about the prototype patch?<br>
<br>
</div>Yes.<br>
<br>
1) I would implement it with inline functions other than macros.<br>
<br>
Like this:<br>
<br>
<br>
extern "C" void __sanitizer_annotate_contiguous_container(void *, void *, void *, void *);<br>
void inline __annotate_contiguous container<br>
( const void *__beg, const void *__end, const void *__old_mid, const void *new_mid )<br>
#if __has_feature(address_sanitizer)<br>
{ __sanitizer_annotate_contiguous_container(beg, end, old_mid, new_mid); }<br>
#else<br>
{}<br>
#endif<br></blockquote><div><br></div></div><div>Makes sense, see below. </div><div>We''l probably want to move __annotate_contiguous container into a separate file so that both string and vector use it.</div><div>
But let's do the whole thing with vector before moving to string. </div><div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
2) I'd like more information about what __sanitizer_annotate_contiguous_container does ;-)<br></blockquote><div><br></div></div><div>In short, it [un]poisons the parts of shadow memory that correspond to the container's memory. </div>
<div>More details in compiler-rt files: include/sanitizer/common_interface_defs.h and lib/asan/asan_poisoning.cc</div><div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><br>
> Any suggestion how to test these annotations in libc++ (we need some kind of DEATH tests)?<br>
<br>
</div>We already have failing tests in libc++.<br>
they are named XXXX.fail.cpp.<br></blockquote><div><br></div></div><div>These are tests that fail to compile. </div><div>for asan annotations we need tests that build and run, and then either fail at run-time or check the state of shadow. </div>
<div>Like these:</div><div><div>compiler-rt/lib/asan/lit_tests/TestCases/contiguous_container.cc</div><div>compiler-rt/lib/asan/lit_tests/TestCases/contiguous_container_crash.cc</div></div><div><br></div><div>Suggestions?</div>
<div><br></div><div>--kcc </div><div><br></div><div><div>--- include/vector (revision 195116)</div><div>+++ include/vector (working copy)</div><div>@@ -288,6 +288,16 @@</div><div> </div><div> _LIBCPP_BEGIN_NAMESPACE_STD</div>
<div> </div><div>+extern "C" void __sanitizer_annotate_contiguous_container(</div><div>+ const void *, const void *, const void *, const void *);</div><div>+void inline __annotate_contiguous_container</div><div>
+ (const void *__beg, const void *__end, const void *__old_mid, const void *__new_mid)</div><div>+#if __has_feature(address_sanitizer)</div><div>+ { __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); }</div>
<div>+#else</div><div>+ {}</div><div>+#endif</div><div>+</div><div> template <bool></div><div> class __vector_base_common</div><div> {</div><div>@@ -1525,7 +1535,12 @@</div><div><div> // __v.push_back(_VSTD::forward<_Up>(__x));</div>
<div> __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));</div><div> __v.__end_++;</div><div>+ if (data())</div></div><div>+ __annotate_contiguous_container(</div>
<div>
<div>+ data(), data() + capacity(), data() + size(), data() + capacity());</div><div> __swap_out_circular_buffer(__v);</div></div><div>+ __annotate_contiguous_container(data(), data() + capacity(),</div><div>
<div>+ data() + capacity(), data() + size());</div>
<div> }</div><div> </div></div></div><div><br></div><div><br></div></div></div></div>
</blockquote></div><br></div>
</div></blockquote></div><br></div>
</div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div><span><vector_asan.patch></span></blockquote></div><br></div></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div>