Allocator shim skeleton + Linux impl behind a build flag

base/allocator/allocator_shim.cc

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/allocator/allocator_shim.h"
+
+#include <errno.h>
+#include <unistd.h>
+
+#include <new>
+
+#include "base/atomicops.h"
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/threading/platform_thread.h"
+#include "build/build_config.h"
+
+// No calls to malloc / new in this file. They would would cause re-entrancy of
+// the shim, which is hard to deal with. Keep this code as simple as possible
+// and don't use any external C++ object here, not even //base ones. Even if
+// they are safe to use today, in future they might be refactored.
+
+namespace {
+
+using namespace base;
+
+const allocator::AllocatorDispatch* volatile g_chain_head =

[Nico, 2016/03/08 03:08:42]

why volatile?

should this be an atomicptr?

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

Removed volatile and switched to AtomicWord after lot of thoughts.
Here's the braindump.
I originally wrote the reply below because I was convinced I still needed
volatile. By the time I reached the end I changed my mind (in essence: this is
my rationale. If you don't like I have another, better, one :P):

On 2016/03/08 03:08:42, Nico wrote:
Now, this is the real reason why I waited for a compiler-master-of-puppets on
this cl :-)
So my rationale for the volatile here is:
 - InsertAllocationDispatch is, by design, guaranteed to be called on the same
thread, so I don't have to worry about races on insertion (good).
 - However, I want to guarantee that when you InsertAllocationDispatch from
thread X, thread Y does always see the sequence of [update next pointer, update
chain head] in this order, as that guarantees that Y either sees the old chain
head, or the new chain head properly setup.

Now I am convinced that from an OOO execution viewpoint, the MemoryBarrier in
InsertAllocatorDispatch is enough (The dispatch functions are supposed to be
static and indefinitely-lived anyways, so I don't think I need any
happens-before semantic w.r.t. the Insert).
However, I don't know if the compiler can do some unexpected optimization when
accessing g_chain_head.
Not even sure which optimizations we are talking about, but in my naive mind,
volatile is a way to tell the compiler "mind your business with this var".
Hmm is your suggestion that this should be volatile AND atomicptr, or atomicptr
should be enough.
I speculated on the fact that on all architectures we care about, writing a
pointer word is intrinstically atomic. But now that you let me think more about
this, you are right, I should have used AtomicWord (where NoBarrier_Load/Store
really end up just dereferencing a pointer anyways IIRC).

My question on volatile still remains though. Having established this should be
AtomicWord, should this be Atomic AND volatile, or am I over-worrying about the
volatile part?

Edit 1h later: just looked at the code and it seems that NoBarrier_Load/Store
have volatile in the signature, so I believe that having this switched to
AtomicPtr catches three birds with a stone:
 - I don't have to speculate anymore about r/w ptr-size being intrinsically
atomic.
 - I think I don't need a volatile anymore at this point.
 - I have the unique opportunity to make a nerdy pun with birds and volatile :-)
<img src="self_high_five.gif">

+    &allocator::AllocatorDispatch::default_dispatch;
+
+bool g_call_new_handler_on_malloc_failure = false;
+subtle::Atomic32 g_new_handler_lock = 0;
+
+// In theory this should be just base::ThreadChecker. But we can't afford
+// the luxury of a LazyInstance<ThreadChecker> here as it would cause a new().
+bool CalledOnValidThread() {
+  static PlatformThreadId thread_id = kInvalidThreadId;
+  if (thread_id == kInvalidThreadId)

[Nico, 2016/03/08 03:08:42]

This looks racy for the first few calls. Does it matter?

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

Oh you are right. fail.
I made a new version using a CAS, which if I am reasoning correctly, should
guarantee that in case of a race one of the two threads will hit the DCHECK.

P.S. If my reasoning is correct, we should probably benchmark and update
thread_checker_impl.cc. I suspect a single CAS is more efficient than a lock
acquire + release as in  thread_checker_impl.cc, but right now have no data to
back this hypothesis.
In my case I really don't have alternatives as I can't afford a base::Lock here
:)
but maybe we just found a way to make debug builds slightly faster.

+    thread_id = PlatformThread::CurrentId();
+  return thread_id == PlatformThread::CurrentId();
+}
+
+inline size_t GetPageSize() {
+  static size_t pagesize = 0;
+  if (!pagesize)
+    pagesize = sysconf(_SC_PAGESIZE);
+  return pagesize;
+}
+
+// Calls the std::new handler thread-safely. Returns true if a new_handler was
+// set and called, false if no new_handler was set.
+bool CallNewHandler() {
+  // TODO(primiano): C++11 has introduced ::get_new_handler() which is supposed
+  // to be thread safe and would avoid the spinlock boilerplate here. However
+  // it doesn't seem to be available yet in the Linux chroot headers yet.
+  std::new_handler nh;
+  {
+    while (subtle::Acquire_CompareAndSwap(&g_new_handler_lock, 0, 1))
+      PlatformThread::YieldCurrentThread();
+    nh = std::set_new_handler(0);
+    ignore_result(std::set_new_handler(nh));
+    subtle::Release_Store(&g_new_handler_lock, 0);
+  }
+  if (!nh)
+    return false;
+  (*nh)();
+  return true;  // Assume the new_handler will abort if it fails.

[Nico, 2016/03/08 03:08:42]

This should probably mention that we don't want new handlers that throw
bad_alloc (no exceptions etc)

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

Oh right. (std::new_handler is such an utopistic API btw.. "The new-handler
function may try to make more storage available" yeahhh)

+}
+
+}  // namespace
+
+namespace base {
+namespace allocator {
+
+void SetCallNewHandlerOnMallocFailure(bool value) {
+  g_call_new_handler_on_malloc_failure = value;
+}
+
+void* UncheckedAlloc(size_t size) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  return chain_head->alloc_function(size, chain_head);
+}
+
+void InsertAllocatorDispatch(AllocatorDispatch* dispatch) {
+  // Ensure this is always called on the same thread.
+  DCHECK(CalledOnValidThread());
+
+  dispatch->next = g_chain_head;
+
+  // This function does not guarantee to be thread-safe w.r.t. concurrent
+  // insertions, but still has to guarantee that all the threads always
+  // see a consistent chain, hence the MemoryBarrier() below.
+  // InsertAllocatorDispatch() is NOT a fastpath, as opposite to malloc(), so
+  // we don't really want this to be a release-store with a corresponding
+  // acquire-load during malloc().
+  base::subtle::MemoryBarrier();
+
+  g_chain_head = dispatch;
+}
+
+}  // namespace allocator
+}  // namespace base
+
+// THe Shim* functions below are the entry-points into the shim-layer and

[Nico, 2016/03/08 03:08:42]

s/THe/The/

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

Done.

+// are supposed to be invoked / aliased by the allocator_shim_override_*
+// headers to route the malloc / new symbols through the shim layer.
+extern "C" {
+
+// The general pattern for allocations is:
+// - Try to allocate, if succeded return the pointer.
+// - If the allocation failed:
+//   - Call the std::new_handler if it was a C++ allocation.
+//   - Call the std::new_handler if it was a malloc() (or calloc() or similar)
+//     AND SetCallNewHandlerOnMallocFailure(true).
+//   - If the std::new_handler is NOT set just return nullptr.
+//   - If the std::new_handler is set:
+//     - Assume it will abort() if it fails (very likely the new_handler will
+//       just suicide priting a message).
+//     - Assume it did succeed if it returns, in which case reattempt the alloc.
+
+void* ShimCppNew(size_t size) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  void* ptr;
+  do {
+    ptr = chain_head->alloc_function(size, chain_head);
+  } while (!ptr && CallNewHandler());

[Nico, 2016/03/08 03:08:42]

Do we currently have new handlers that try to free up memory and then call
again? Is this loop really needed? 

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

both tcmalloc [1] and the win_shim [2] do this.
I think the rationale is: in theory a new handler could return true to say "I
freed up some memory, trust me, try again and you will get !=nullptr this time,
pinky swear"

Realistically the handler will just suicide. If that doesn't happen, the most
reasonable thing we can do here, to comply both with the utopistic world (new
handler will free memory, ha!) API and safety (never return null) is keep
looping until some memory becomes available.

From a more practical viewpoint, I like to stick the current behavior,
regardless of the reason, I feel this CL is adventurous enough :)


[1]
https://chromium.googlesource.com/chromium/src/+/f7b03f4b26ee936818a896f244d5...
[2]
https://chromium.googlesource.com/chromium/src/+/f7b03f4b26ee936818a896f244d5...

+  return ptr;
+}
+
+void ShimCppDelete(void* address) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  return chain_head->free_function(address, chain_head);
+}
+
+void* ShimMalloc(size_t size) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  void* ptr;
+  do {
+    ptr = chain_head->alloc_function(size, chain_head);
+  } while (!ptr && g_call_new_handler_on_malloc_failure && CallNewHandler());
+  return ptr;
+}
+
+void* ShimCalloc(size_t n, size_t size) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  void* ptr;
+  do {
+    ptr = chain_head->alloc_zero_initialized_function(n, size, chain_head);

[Nico, 2016/03/08 03:08:42]

Since the wrapper is called calloc and the c function is called calloc, maybe
call the member fn calloc too? (as-is is fine too i suppose; calloc isn't a
great name :-P)

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

Yeah I think this is mostly driven by:
 - my long standing hate towards calloc (both the name and the silly two-arg
signature). 
 - a headache I had while developing this, when I typoed /calloc/alloc/ and had
to blur my eyes to figure out the missing c.

No strong opinion, can do this change it in the final pathcset once everything
is clear. Up to your preference really.

+  } while (!ptr && g_call_new_handler_on_malloc_failure && CallNewHandler());
+  return ptr;
+}
+
+void* ShimRealloc(void* address, size_t size) {
+  // realloc(size == 0) means free() and might return a nullptr. We should
+  // not call the std::new_handler in that case, though.
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  void* ptr;
+  do {
+    ptr = chain_head->realloc_function(address, size, chain_head);
+  } while (!ptr && size && g_call_new_handler_on_malloc_failure &&
+           CallNewHandler());
+  return ptr;
+}
+
+void* ShimMemalign(size_t alignment, size_t size) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  void* ptr;
+  do {
+    ptr = chain_head->alloc_aligned_function(alignment, size, chain_head);
+  } while (!ptr && g_call_new_handler_on_malloc_failure && CallNewHandler());
+  return ptr;
+}
+
+int ShimPosixMemalign(void** res, size_t alignment, size_t size) {
+  // posix_memalign is supposed to check the arguments. See tc_posix_memalign()
+  // in tc_malloc.cc.
+  if (((alignment % sizeof(void*)) != 0) ||
+      ((alignment & (alignment - 1)) != 0) || (alignment == 0)) {
+    return EINVAL;
+  }
+  void* ptr = ShimMemalign(alignment, size);
+  *res = ptr;
+  return ptr ? 0 : ENOMEM;
+}
+
+void* ShimValloc(size_t size) {
+  return ShimMemalign(GetPageSize(), size);

[Nico, 2016/03/08 03:08:42]

If this doesn't call through to valloc, why have this as part of this interface?
do we call valloc anywhere?

[Primiano Tucci (use gerrit), 2016/03/08 20:54:05]

The deal is: we want to expose the full malloc/valloc family as we want to be
sure that everything reaches into the same allocator at the end. We don't want
to end up in a situation where malloc/free are from tcmalloc, and valloc from
libc.
However, while we want to *expose* valloc, there is no need to plumb it all the
way through the allocator (read: require that from the final *dispatch*
interface) as valloc can be really implemented on top of memalign.

Essentially there is a mismatching between the number of functions we expose to
clients (malloc/free/valloc/pvalloc) and the internal functions required from
the dispatchers (the AllocatorDispatch interface).
The mismatch is: the minimum set of functions (required from the dispatcher)
that allows to implement the full malloc/valloc/pvalloc family consistently.
Not sure we have it in the codebase, but we have to cover the case of chrome
calling a third_party library (e.g. libcups) which calls it, in which case we
want that to be still hooked properly.

+}
+
+void* ShimPvalloc(size_t size) {
+  // pvalloc(0) should allocate one page, according to its man page.
+  if (size == 0) {
+    size = GetPageSize();
+  } else {
+    size = (size + GetPageSize() - 1) & ~(GetPageSize() - 1);
+  }
+  return ShimMemalign(GetPageSize(), size);
+}
+
+void ShimFree(void* address) {
+  const allocator::AllocatorDispatch* const chain_head = g_chain_head;
+  return chain_head->free_function(address, chain_head);
+}
+
+}  // extern "C"
+
+// Cpp symbols (new / delete) should always be routed through the shim layer.
+#include "base/allocator/allocator_shim_override_cpp_symbols.h"
+
+// Ditto for plain malloc() / calloc() / free() etc. symbols.
+#include "base/allocator/allocator_shim_override_libc_symbols.h"
+
+// In the case of tcmalloc we also want to plumb into the glibc hooks
+// to avoid that allocations made in glibc itself (e.g., strdup()) get
+// accidentally performed on the glibc heap instead of the tcmalloc one.
+#if defined(USE_TCMALLOC)
+#include "base/allocator/allocator_shim_override_glibc_weak_symbols.h"
+#endif
+
+// Cross-checks.
+
+#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
+#error The allocator shim should not be compiled when building for memory tools.
+#endif
+
+#if (defined(__GNUC__) && defined(__EXCEPTIONS)) || \
+    (defined(_HAS_EXCEPTIONS) && _HAS_EXCEPTIONS)
+#error This code cannot be used when exceptions are turned on.
+#endif