macOS: Shim all malloc zones.

base/allocator/malloc_zone_functions_mac.cc

+// Copyright 2017 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/malloc_zone_functions_mac.h"
+
+#include "base/atomicops.h"
+#include "base/synchronization/lock.h"
+
+namespace base {
+namespace allocator {
+
+MallocZoneFunctions g_malloc_zones[kMaxZoneCount];
+MallocZoneFunctions::MallocZoneFunctions() {}
+
+void StoreZoneFunctions(ChromeMallocZone* zone,
+                        MallocZoneFunctions* functions) {
+  functions->malloc = zone->malloc;
+  functions->calloc = zone->calloc;
+  functions->valloc = zone->valloc;
+  functions->free = zone->free;
+  functions->realloc = zone->realloc;
+  functions->size = zone->size;
+  CHECK(functions->malloc && functions->calloc && functions->valloc &&
+        functions->free && functions->realloc && functions->size);
+
+  // These functions might be nullptr.
+  functions->batch_malloc = zone->batch_malloc;
+  functions->batch_free = zone->batch_free;
+
+  if (zone->version >= 5) {
+    // Not all custom malloc zones have a memalign.
+    functions->memalign = zone->memalign;
+  }
+  if (zone->version >= 6) {
+    // This may be nullptr.
+    functions->free_definite_size = zone->free_definite_size;
+  }
+
+  functions->context = zone;
+}
+
+namespace {
+
+// All modifications to g_malloc_zones are gated behind this lock.
+// Dispatch to a malloc zone does not need to acquire this lock.
+base::Lock* GetLock() {

[Primiano Tucci (use gerrit), 2017/02/23 00:40:18]

do you really need all this locking here? Isn't easier to just make it so that
all the zone replacements are done from the same thread and just add a
threadchecker here?

[erikchen, 2017/02/23 01:43:14]

Actually, the new Task Scheduler doesn't guarantee thread-affinity, just
ordering. Adding a usage requirement in the header [which would only loosely be
enforced by dchecks/checks] add complexity to the interface for no benefit,
whereas using a lock ensures correctness, and doesn't pollute the interface.]
Note that there's no real performance hit, since there's not going to be
contention on this lock.

[Primiano Tucci (use gerrit), 2017/02/23 11:19:41]

Well depends wheteher you use SingleThreadTaskRunner or just a seqTaskRunner.
My worry is not about contention, is just when possible I prefer to not think
about thread safety (by guaranteeing that everything happens on a thread)
instead of trying to deal with it. Nothing is more thread safe than things that
happen on a single thread :)
Ahyhow, not strongly opinionated on this, so feel free to keep this.

[erikchen, 2017/02/23 20:06:44]

There's no way to guarantee things happen on a single thread without
high-performance-impact checks. Locks guarantee that we have the right behavior,
regardless of how consumers use us.

[Primiano Tucci (use gerrit), 2017/02/23 21:06:07]

ThreadChecker (and SequenceChecker) have zero cost in production as they are
dcheck-only, which is usually IMHO a reasonable compromise.
locks induce people to make false assumptions on the threadsafety of the code,
using it for use-cases it was never designed to deal with. By experience they
are never a problem at the time you land the CL. but one day, 6 months from now,
somebody will refactor this code (or add some other calls).
to be clear, i'm perfectly fine today with this, but my warn is that one day
you'll see a bug on this :)

I prefer explicit "this code doesn't support multi-thread scenario" because it
discourage future people (sometimes that being future-myself) from doing
adventurous things.

+  static base::Lock* g_lock = new base::Lock;
+  return g_lock;
+}
+
+int g_zone_count = 0;
+bool g_zeroed = false;
+
+bool IsMallocZoneAlreadyStoredLockAcquired(ChromeMallocZone* zone) {

[Primiano Tucci (use gerrit), 2017/02/23 00:40:18]

I think the naming pattern in the rest of the codebase is xxxLocked not
xxxLockAcquired:

cs stats:
\b\w+Locked\( -f:third_party -> 723 resuts
\b\w+LockAcquired\( -f:third_party -> 8 resuts

[erikchen, 2017/02/23 01:43:14]

Done.

+  GetLock()->AssertAcquired();
+  for (int i = 0; i < g_zone_count; ++i) {
+    if (g_malloc_zones[i].context == reinterpret_cast<void*>(zone))
+      return true;
+  }
+  return false;
+}
+
+}  // namespace
+
+void StoreMallocZone(ChromeMallocZone* zone) {
+  base::AutoLock l(*GetLock());
+  if (!g_zeroed) {
+    g_zeroed = true;
+    memset(g_malloc_zones, 0, sizeof(g_malloc_zones));

[Primiano Tucci (use gerrit), 2017/02/23 00:40:18]

why you need this? global structs and pods are zero-initialized by default.
maybe just add a static_assert(is_pod(g_malloc_zones)) to make sure that won't
accidentally become a dynamic initializer.

[erikchen, 2017/02/23 01:43:14]

This isn't pod. Notice that MallocZoneFunctions has an explicit constructor. See
my response to your previous set of comments. But you're right that we don't
need to initialize this array.

[Primiano Tucci (use gerrit), 2017/02/23 11:19:41]

Uhm, this means that g_malloc_zones will likely cause an initializer, which is:
- forbidden by the style guide (see below)
- going to be intercepted by Nico's static intializer's check in the main
waterfall (there is no check in CQ) and cause a revert, unless the compiler is
smart enough to figure out that the ctor doesn't really require a static
initializer (but, as per above, you shouldn't rely on that.

From style guide:
Variables of class type with static storage duration are forbidden (...)
Objects with static storage duration, including global variables, static
variables, static class member variables, and function static variables, must be
Plain Old Data (POD): only ints, chars, floats, or pointers, or arrays/structs
of POD.

Also, I just realized that by having a default ctor for MallocZoneFunctions that
does nothing, you are essentially preventing the global struct to be zero
initialized. This explains why the existing code didn't hit the static
initialzier check. 

In summary, I think the cleanest thing to do is to drop that constructor, make
MallocZoneFunctions a POD, and initialize with {} in the places where is not
used as a global.

[erikchen, 2017/02/23 20:06:44]

1. Our custom clang module forces us to make a default constructor because there
are >= 10 members.
2. Default constructor means non-POD
3. + Global = static initializers.
AFAICT, there's no way to turn off the custom clang warning. This seems like an
issue with our custom clang plugin. I'll chat with erg@. 

That being said, given that we want a global array, I actually think it's
slightly better for us to dynamically allocate the space [lower binary size].
I've gone ahead and done this.

[Primiano Tucci (use gerrit), 2017/02/23 21:06:07]

Alright I see, there seems to be a problem in our constraints. essentially:
- clang plugin requires a struct with too many field to have an explicit ctor.
- the only way to avoid static initializers for a stuct is to not have a ctor.
Will start a thread on chromium-dev about this.
zero-initialized data does not cause any binary increase. See discussion in:
https://groups.google.com/a/chromium.org/d/msg/project-trim/vfX5Ohn1Ees/gLLZ2...
okay for me, but you just added an extra layer of indirection when accessing the
array.
Proof here:
https://gist.github.com/primiano/2473ac16db614ffa1fc1f33b4dc0e15b
(yes, I am nerdsnipable that easily :P)

essentially accessing an heap allocated array requires to first fetch the
pointer into a register, and then use the register+off*displacement mov to
read/write.
Instead when accessing a global object you can directly do the math based on the
the instruction pointer, because in position in dependent code, the array will
be laid out at a fixed distance from the IP of the current instruction ;-)

Having said that this still is okay to me. Just saying because you were the one
obsessed with perf impact of AcquireLoad/ReleaseStore :) 

+  }
+  if (IsMallocZoneAlreadyStoredLockAcquired(zone))
+    return;
+
+  if (g_zone_count == kMaxZoneCount)
+    return;
+
+  StoreZoneFunctions(zone, &g_malloc_zones[g_zone_count]);
+  ++g_zone_count;
+  base::subtle::MemoryBarrier();

[Primiano Tucci (use gerrit), 2017/02/23 00:40:18]

This memory barrier is not enough in theory and is non-necessary in practice on
x86-TSO (but we don't want to rely on this because TSan will slap us).

What you really want to guarantee here is that the |context| is the last field
getting written. so that on the reader side either you read a null context or
(non-null context AND consistent function ptrs).
The way you epxress this is by making |context| a subtle::AtomicWord and by
doing a ReleaseStore here (well, in StoreZoneFunctions) AND an AcquireLoad in
GetFunctionsForZone.

Now, I say this is non necessary on x86-TSO because, in the Total Store Order
model,  the reordering engine guarantees that stores and loads appear to be
always linearized, and the only visible thing that can happen IIRC is that
stores get reorder w.r.t loads.

But you don't want to think to this micro-architecture detail and depend about
all this (also because in the meantime the compiler could take other reordering
licenses). Thankfully you don't need to. in fact if you look at the x86
implementation both AcquireLoad and REleaseStore are just conventional load and
store operations (+ the required volatile and such to keep to compiler quiet) :)

[erikchen, 2017/02/23 01:43:14]

Sorry, but I disagree on  both points. Comments inline.
Not quite. Your suggestion is a stronger guarantee than we need. We just need to
ensure that each malloc-zone that we've shimmed will see a consistent result for
the MallocZoneFunctions that has the appropriate |context|. This just means that
we need a memory barrier before inserting the shim. I commented on this in the
header file.
This potentially has very significant performance implications [depends on
implementation of AcquireLoad/ReleaseStore], which is why I've avoided it.
ia-64 allows all sorts of reorderings.

https://en.wikipedia.org/wiki/Memory_ordering
As you've noted, it's very hard to get correct semantics for AcquireLoad and
ReleaseStore, whereas MemoryBarrier is very well defined. 

I'll try to come online early tomorrow so we can discuss live.. 

[Primiano Tucci (use gerrit), 2017/02/23 11:19:41]

No need to be sorry :)
Let me see if I visualize the problem correctly before we discuss the solution.
My understanding is that, in the very essence, the problem we have is the
following (I'm deliberately ignoring the "array" part and considering the
simpler case of 1-item array):
on one writer thread you do:
g_zone.malloc_function_ptr = ....
g_zone.calloc_function_ptr = ....
g_zone.context = ....

On the reader thread (in allocator_shim_default_dispatch_to_mac_zoned_malloc.cc)
if (g_zone.context != nullptr)
  .. use the fields of the zone such as malloc_function_ptr

So my understanding is that either you don't want to see the zone being
populated, or you want to see it populated consistently. 
is this right? or am I misunderstanding the problem?
Yup saw that.
There are no performance implication on AcquireLoad/ReleaseStore on x86/x86_64
(which are the only archs we care about on Mac). AFAIL there is a penalty on
Linux desktop, but that's a bug and just because we are using a mismatching
sysroot (crbug.com/592903) 
Correct, but ia-64 == itanium != x86_64. 
(I know, but... ia-32 == x86. Lovely isn't it?)

 
Precisely. That confirms my point. You did just look at the wrong column :)
amd64 is what you want to look for here. the "amd" part is irrelevant and
historic. amd64 == x86_64 (regardless of the brand, Intel or AMD)

(And to add more excitement, since we are on the topic, amd64 is also often
referred to as x64)
Also AcquireLoad and ReleaseStore semantic is "well defined". But I don't want
to get lost in linguistic or phylosophical discussions, so I guess what you
meant here is: "MemoryBarrier" is easier to reason about than Acquire/Release
semantics. Which I agree. but still MB itself is hard to reason about.

MB guarantees:
- that all the stores before the barrier are committed and are seen by other
threads before the next writers AND 
- all the reads after the barrier won't be reordered with the one before *on the
current thread*

Unfortunately, if my understanding of the problem is correct, this MB is still
not enough to guarantee what you need (unless, again, you assume the x86/64 TSO
model). With a memory barrier, the following linearization of the code above is
possible:

W -> Writer thread
R -> Reader thread

W: g_zone.malloc = ...
R: g_zone.context
W: g_zone.context = ...
R: g_zone.malloc
W: MemoryBarrier

Essentially, the MB does NOT guarantee that the stores will NOT be reordered
before hitting the barrier (if you think about that, a MB cannot have
retroactive effect). Hence the other thread can still see the writes in opposite
order.
I created a repro that you can compile and run for this example here:

https://gist.github.com/primiano/0936c4740a28a26d22d41fff8abb0e6e

If you run that code on x86/64 it will never hit the race, even if you remove
completely the memory barrier.
If you run that code on arm (which, as noted in the wikipedia page you linked,
has a weaker ordering model) it will fail even in presence of the one memory
barrier.

Which is the reason why both Acq/Rel and MB are under the "subtle" namespace and
the reason why we strongly discourage the use of atomic and use only locks.
However, I agree with you, that for this specific case, a lock is a no-go. By
direct experience when writing the  Linux shim I know that even one extra mfence
in the malloc path will be detected by the perf waterfall (true story:
https://codereview.chromium.org/1777363002/)

(Also, in all this, we are completely ignoring optimizations that the compiler
does on top, which are often the biggest reason why you want
base::subtle::*Load/Store)
Yup happy to talk live. I will be later today anyways.

[Primiano Tucci (use gerrit), 2017/02/23 17:47:16]

Erik and I had a chat offline, summarizing here.
There is a causality relationship that I was not seeing.
Essentially I was worrying about the case when another thread starts seeing the
stores before we actually get to the MemoryBarrier. That would be a problem and
that is the repro I did create in that snippet above.
However, this cannot happen here. The only code that reads the malloc functions
is triggered when the malloc zone is replaced, which happens after this point.
So nothing can see the stores before this point, hence the MB here is correct as
you only want to guarantee that whatever happens next sees everything you have
written, but you don't have to worry about what happens before.
(unrelatedly, there is a possibility that ASan will still bark on this, because
it won't be able to infer this causality. but let's not worry about this until
this happens first)

+}
+
+bool IsMallocZoneAlreadyStored(ChromeMallocZone* zone) {
+  base::AutoLock l(*GetLock());
+  return IsMallocZoneAlreadyStoredLockAcquired(zone);
+}
+
+int GetMallocZoneCountForTesting() {
+  base::AutoLock l(*GetLock());
+  return g_zone_count;
+}
+
+void ClearAllMallocZonesForTesting() {
+  base::AutoLock l(*GetLock());
+  memset(g_malloc_zones, 0, sizeof(g_malloc_zones));
+  g_zone_count = 0;
+  g_zeroed = false;

[Primiano Tucci (use gerrit), 2017/02/23 00:40:18]

as per the comment above I don't think you need this g_zeroed. But if you end up
really needing it, I find quite hard to believe that this is = false, since you
just memset-ed it to 0 two lines above :)

[erikchen, 2017/02/23 01:43:14]

removed.

+}
+
+}  // namespace allocator
+}  // namespace base