Implement address sanitizer (ASAN) support

[bstrie]

Backstory: being Valgrind-clean is a blocker for 1.0 (#13217). But Valgrind gives us tons of false positives (#5856) because of a specific tactic used by LLVM to generate optimized code (http://llvm.org/bugs/show_bug.cgi?id=12319). Neither LLVM nor Valgrind are incorrect here, so this is unlikely to ever be resolved (#5856 (comment)). And the overall volume of false positives is so great that we often succumb to just turning off Valgrind entirely to get any work done (#13217 (comment)).

There is an alternative: ASAN, which is integrated into LLVM and designed to produce no false positives in addition to being relatively low on runtime overhead (https://address-sanitizer.googlecode.com/files/address_sanity_checker.pdf). It is sponsored by Google and used in Chromium to great effect. But adding support is nontrivial:

This really needs to be refiled as "implement address sanitizer support" which is a huge project. It's not useful without frontend support, and IMO it's too much complexity to add to librustc in the current state it's in. Sanitizers would need to be added for all the unsafe intrinsics along with unsafe pointer dereferencing. It's not going to map well to the sanitizers used by Clang, since Rust does everything in the libraries with the basic compiler intrinsics. It doesn't have a language feature for unsafe indexing of arrays, etc.

#749 (comment)

Not only would ASAN support be a tremendous task, it would also ideally never generate any hits for Rust code. However, unsafe code exists, and developers can (and will (and have (we just don't know it yet))) get it wrong. More lines of defense are always valuable.

If you're looking for a very challenging and long-term but (IMO) very important Rust-related project to test your skills, this is the project for you.

[jdm]

See comments in #749, too.

[vadimcn]

I've had ASAN mostly working a while ago. I can make it work again, if this is considered an important feature... Personally, I am not convinced that this is worth doing just for unsafe blocks.
Or is the goal to validate Rust internals, as #13217 would seem to imply?

[vadimcn]

At this point, I expect the biggest stumbling block to be integration with Rust memory allocator:

• At the very least, ASAN needs to hook into allocator API so it can update its internal memory validity map. ASAN runtime library exports symbols to override malloc, free etc, when linking statically, and it dynamically detours msvcrt's malloc in case of dynamic linking, but it does not handle non-standard memory allocators (like jemalloc). We could add support on our end, though, by putting poison/unpoison calls into liballoc.
• For best results, however, we should use ASAN's custom memory allocator, which has extra debugging features like putting recently deallocated blocks into quarantine (otherwise, it might miss dangling pointer dereferences, if the block gets immediately allocated for something else).
  The easiest way to do this would be to fall back to using malloc when ASAN is active.

It seems to me that unless we want to ship a special "debug" version of liballoc, we are going to have to make these switches at runtime, which is going to cost us at least one extra branch on each operation.

cc @thestinger

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#670